Publications

Search or filter publications

Filter by type:

Filter by publication type

Filter by year:

to

Results

  • Showing results for:
  • Reset all filters

Search results

  • Conference paper
    Ceran ET, Gunduz D, Gyorgy A, 2018,

    Average age of information with hybrid ARQ under a resource constraint

    , Wireless Communications and Networking Conference (WCNC), Publisher: IEEE, ISSN: 1525-3511

    Scheduling the transmission of status updates over an error-prone communication channel is studied in order to minimize the long-term average age of information (AoI) at the destination under a constraint on the average number of transmissions at the source node. After each transmission, the source receives an instantaneous ACK/NACK feedback, and decides on the next update without prior knowledge on the success of future transmissions. First, the optimal scheduling policy is studied under different feedback mechanisms when the channel statistics are known; in particular, the standard automatic repeat request (ARQ) and hybrid ARQ (HARQ) protocols are considered. Then, for an unknown environment, an average-cost reinforcement learning (RL) algorithm is proposed that learns the system parameters and the transmission policy in real time. The effectiveness of the proposed methods are verified through numerical simulations.
  • Journal article
    Huang R, Lattimore T, Gyorgy A, Szepesvari Cet al., 2017,

    Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities

    , Journal of Machine Learning Research, Vol: 18(145), Pages: 1-31, ISSN: 1532-4435

    Follow the leader (FTL) is a simple online learning algorithm that is known to perform well whenthe loss functions are convex and positively curved. In this paper we ask whether there are othersettings when FTL achieves low regret. In particular, we study the fundamental problem of linearprediction over a convex, compact domain with non-empty interior. Amongst other results, weprove that the curvature of the boundary of the domain can act as if the losses were curved: In thiscase, we prove that as long as the mean of the loss vectors have positive lengths bounded away fromzero, FTL enjoys logarithmic regret, while for polytope domains and stochastic data it enjoys finiteexpected regret. The former result is also extended to strongly convex domains by establishing anequivalence between the strong convexity of sets and the minimum curvature of their boundary,which may be of independent interest. Building on a previously known meta-algorithm, we alsoget an algorithm that simultaneously enjoys the worst-case guarantees and the smaller regret ofFTL when the data is ‘easy’. Finally, we show that such guarantees are achievable directly (e.g.,by the follow the regularized leader algorithm or by a shrinkage-based variant of FTL) when theconstraint set is an ellipsoid.
  • Conference paper
    Joulani P, Gyorgy A, Szepesvari C, 2017,

    A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds

    , 28th International Conference on Algorithmic Learning Theory
  • Conference paper
    Somuyiwa S, Gyorgy A, Gunduz D, 2017,

    Energy-efficient wireless content delivery with proactive caching

    , 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), Publisher: IEEE

    We propose an intelligent proactive content caching scheme to reduce the energy consumption in wireless downlink. We consider an online social network (OSN) setting where new contents are generated over time, and remain relevant to the user for a random lifetime. Contents are downloaded to the user equipment (UE) through a time-varying wireless channel at an energy cost that depends on the channel state and the number of contents downloaded. The user accesses the OSN at random time instants, and consumes all the relevant contents. To reduce the energy consumption, we propose proactive caching of contents under favorable channel conditions to a finite capacity cache memory. Assuming that the channel quality (or equivalently, the cost of downloading data) is memoryless over time slots, we show that the optimal caching policy, which may replace contents in the cache with shorter remaining lifetime with contents at the server that remain relevant longer, has a threshold structure with respect to the channel quality. Since the optimal policy is computationally demanding in practice, we introduce a simplified caching scheme and optimize its parameters using policy search. We also present two lower bounds on the energy consumption. We demonstrate through numerical simulations that the proposed caching scheme significantly reduces the energy consumption compared to traditional reactive caching tools, and achieves close- to-optimal performance for a wide variety of system parameters.
  • Conference paper
    Somuyiwa S, Gyorgy A, Gunduz D, 2017,

    Improved policy representation and policy search for proactive content caching in wireless networks

    , 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Publisher: IEEE

    We study the problem of proactively pushing contents into a finite capacity cache memory of a user equipment in order to reduce the long-term average energy consumption in a wireless network. We consider an online social network (OSN) framework, in which new contents are generated over time and each content remains relevant to the user for a random time period, called the lifetime of the content. The user accesses the OSN through a wireless network at random time instants to download and consume all the relevant contents. Downloading contents has an energy cost that depends on the channel state and the number of downloaded contents. Our aim is to reduce the long-term average energy consumption by proactively caching contents at favorable channel conditions. In previous work, it was shown that the optimal caching policy is infeasible to compute (even with the complete knowledge of a stochastic model describing the system), and a simple family of threshold policies was introduced and optimised using the finite difference method. In this paper we improve upon both components of this approach: we use linear function approximation (LFA) to better approximate the considered family of caching policies, and apply the REINFORCE algorithm to optimise its parameters. Numerical simulations show that the new approach provides reduction in both the average energy cost and the running time for policy optimisation.
  • Conference paper
    Joulani P, Gyorgy A, Szepesvari C, 2016,

    A unified modular analysis of online and stochastic optimization: adaptivity, optimism, non-convexity

    , 9th NIPS Workshop on Optimization for Machine Learning

    We present a simple unified analysis of adaptive Mirror Descent (MD) and Follow-the-Regularized-Leader (FTRL) algorithms for online and stochastic optimizationin (possibly infinite-dimensional) Hilbert spaces. The analysis is modular inthe sense that it completely decouples the effect of possible assumptions on theloss functions (such as smoothness, strong convexity, and non-convexity) andon the optimization regularizers (such as strong convexity, non-smooth penaltiesin composite-objective learning, and non-monotone step-size sequences). Wedemonstrate the power of this decoupling by obtaining generalized algorithms andimproved regret bounds for the so-called “adaptive optimistic online learning” set-ting. In addition, we simplify and extend a large body of previous work, includingseveral various AdaGrad formulations, composite-objective and implicit-updatealgorithms. In all cases, the results follow as simple corollaries within few linesof algebra. Finally, the decomposition enables us to obtain preliminary globalguarantees for limited classes of non-convex problems.
  • Conference paper
    Shaloudegi K, Gyorgy A, Szepesvari C, Xu Wet al., 2016,

    SDP relaxation with randomized rounding for energy disaggregation

    , The Thirtieth Annual Conference on Neural Information Processing Systems (NIPS), Publisher: Neutral Information Processing Systems Foundation, Inc.

    We develop a scalable, computationally efficient method for the task of energydisaggregation for home appliance monitoring. In this problem the goal is toestimate the energy consumption of each appliance over time based on the totalenergy-consumption signal of a household. The current state of the art is to modelthe problem as inference in factorial HMMs, and use quadratic programming tofind an approximate solution to the resulting quadratic integer program. Here wetake a more principled approach, better suited to integer programming problems,and find an approximate optimum by combining convex semidefinite relaxationsrandomized rounding, as well as a scalable ADMM method that exploits the specialstructure of the resulting semidefinite program. Simulation results both in syntheticand real-world datasets demonstrate the superiority of our method.
  • Conference paper
    Huang R, Lattimore T, Gyorgy A, Szepesvari Cet al., 2016,

    Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities

    , Advances in Neural Information Processing Systems 29 (NIPS 2016), Publisher: Neutral Information Processing Systems Foundation, Inc.

    The follow the leader (FTL) algorithm, perhaps the simplest of all online learningalgorithms, is known to perform well when the loss functions it is used on are positivelycurved. In this paper we ask whether there are other “lucky” settings whenFTL achieves sublinear, “small” regret. In particular, we study the fundamentalproblem of linear prediction over a non-empty convex, compact domain. Amongstother results, we prove that the curvature of the boundary of the domain can act asif the losses were curved: In this case, we prove that as long as the mean of the lossvectors have positive lengths bounded away from zero, FTL enjoys a logarithmicgrowth rate of regret, while, e.g., for polyhedral domains and stochastic data itenjoys finite expected regret. Building on a previously known meta-algorithm, wealso get an algorithm that simultaneously enjoys the worst-case guarantees and thebound available for FTL.
  • Conference paper
    Kern T, Gyorgy A, 2016,

    SVRG++ with non-uniform sampling

    , 9th NIPS Workshop on Optimization for Machine Learning, Publisher: Neural Information Processing Systems Foundation, Inc.

    SVRG++ is a recent randomized optimization algorithm designed to solve non-strongly convex smooth composite optimization problems in the large data regime.In this paper we combine SVRG++ with non-uniform sampling of the data points(already present in the original SVRG algorithm), leading to an algorithm with thebest sample complexity to date and state-of-the art empirical performance. Whilethe combination and the analysis of the algorithm is admittedly straightforward,our experimental results show significant improvement over the original SVRG++method with the new method outperforming all competitors on datasets where thesmoothness of the components varies. This demonstrates that, despite its simplicityand limited novelty, this extension is important in practice.
  • Conference paper
    Gyorgy A, Szepesvari C, 2016,

    Shifting Regret, Mirror Descent, and Matrices

    , International Conference on Machine Learning, Publisher: Journal of Machine Learning Research, Pages: 2943-2951, ISSN: 1532-4435

    We consider the problem of online prediction inchanging environments. In this framework theperformance of a predictor is evaluated as theloss relative to an arbitrarily changing predictor,whose individual components come from a baseclass of predictors. Typical results in the literatureconsider different base classes (experts, linearpredictors on the simplex, etc.) separately.Introducing an arbitrary mapping inside the mirrordecent algorithm, we provide a frameworkthat unifies and extends existing results. As anexample, we prove new shifting regret bounds formatrix prediction problems.
  • Conference paper
    Joulani P, Gyorgy A, Szepesvari C, 2016,

    Delay-Tolerant Online Convex Optimization: Unified Analysis and Adaptive-Gradient Algorithms

    , Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16), Publisher: AAAI

    We present a unified, black-box-style method for developingand analyzing online convex optimization (OCO) algorithmsfor full-information online learning in delayed-feedback environments.Our new, simplified analysis enables us to substantiallyimprove upon previous work and to solve a numberof open problems from the literature. Specifically, we developand analyze asynchronous AdaGrad-style algorithmsfrom the Follow-the-Regularized-Leader (FTRL) and MirrorDescentfamily that, unlike previous works, can handle projectionsand adapt both to the gradients and the delays, withoutrelying on either strong convexity or smoothness of theobjective function, or data sparsity. Our unified frameworkbuilds on a natural reduction from delayed-feedback to standard(non-delayed) online learning. This reduction, togetherwith recent unification results for OCO algorithms, allows usto analyze the regret of generic FTRL and Mirror-Descent algorithmsin the delayed-feedback setting in a unified mannerusing standard proof techniques. In addition, the reduction isexact and can be used to obtain both upper and lower boundson the regret in the delayed-feedback setting.
  • Conference paper
    Gyorgy A, Szcpesvari C, 2016,

    Shifting regret, mirror descent, and matrices

    , Pages: 4324-4332

    We consider the problem of online prediction in changing environments. In this framework the performance of a predictor is evaluated as the loss relative to an arbitrarily changing predictor, whose individual components come from a base class of predictors. Typical results in the literature consider different base classes (experts, linear predictors on the simplex, etc.) separately. Introducing an arbitrary mapping inside the mirror decent algorithm, we provide a framework that unifies and extends existing results. As an example, we prove new shifting regret bounds for matrix prediction problems.
  • Conference paper
    Hu X, Prashanth LA, Gyorgy A, Szepesvari Cet al., 2015,

    (Bandit) Convex Optimization with Biased Noisy Gradient Oracles

    , 8th NIPS Workshop on Optimization for Machine Learning

    For bandit convex optimization we propose a model, where a gradient estimation oracle acts as anintermediary between a noisy function evaluation oracle and the algorithms. The algorithms cancontrol the bias-variance tradeoff in the gradient estimates. We prove lower and upper bounds forthe minimax error of algorithms that interact with the objective function by controlling this oracle.The upper bounds replicate many existing results (capturing the essence of existing proofs) while thelower bounds put a limit on the achievable performance in this setup. In particular, our results implythat no algorithm can achieve the optimal minimax error rate in stochastic bandit smooth convexoptimization.
  • Conference paper
    Joulani P, Gyorgy A, Szepesvari C, 2015,

    Classification with Margin Constraints: A Unification with Applications to Optimization

    , 8th NIPS Workshop on Optimization for Machine Learning

    This paper introduces Classification with Margin Constraints (CMC), a simplegeneralization of cost-sensitive classification that unifies several learning settings.In particular, we show that a CMC classifier can be used, out of the box, to solveregression, quantile estimation, and several anomaly detection formulations. Onthe one hand, our reductions to CMC are at the loss level: the optimization problemto solve under the equivalent CMC setting is exactly the same as the optimizationproblem under the original (e.g. regression) setting. On the other hand,due to the close relationship between CMC and standard binary classification, theideas proposed for efficient optimization in binary classification naturally extendto CMC. As such, any improvement in CMC optimization immediately transfersto the domains reduced to CMC, without the need for new derivations or programs.To our knowledge, this unified view has been overlooked by the existingpractice in the literature, where an optimization technique (such as SMO or PEGASOS)is first developed for binary classification and then extended to otherproblem domains on a case-by-case basis. We demonstrate the flexibility of CMCby reducing two recent anomaly detection and quantile learning methods to CMC.
  • Conference paper
    Wu Y, György A, Szepesvari C, 2015,

    Online Learning with Gaussian Payoffs and Side Observations

    , 29th Annual Conference on Neural Information Processing Systems (NIPS), Publisher: Neural Information Processing Systems Foundation, Inc.
  • Journal article
    Pitt J, Busquets D, Riveret R, 2015,

    The pursuit of computational justice in open systems

    , AI & SOCIETY, Vol: 30, Pages: 359-378, ISSN: 0951-5666
  • Journal article
    Thajchayapong S, Barria JA, 2015,

    Spatial inference of traffic transition using micro-macro traffic variables

    , IEEE Transactions on Intelligent Transportation Systems, Vol: 16, Pages: 854-864, ISSN: 1524-9050

    This paper proposes an online traffic inference algorithm for road segments in which local traffic information cannot be directly observed. Using macro-micro traffic variables as inputs, the algorithm consists of three main operations. First, it uses interarrival time (time headway) statistics from upstream and downstream locations to spatially infer traffic transitions at an unsupervised piece of segment. Second, it estimates lane-level flow and occupancy at the same unsupervised target site. Third, it estimates individual lane-level shockwave propagation times on the segment. Using real-world closed-circuit television data, it is shown that the proposed algorithm outperforms previously proposed methods in the literature.
  • Journal article
    Blasco P, Gunduz D, 2015,

    Multi-Access Communications With Energy Harvesting: A Multi-Armed Bandit Model and the Optimality of the Myopic Policy

    , IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, Vol: 33, Pages: 585-597, ISSN: 0733-8716
  • Journal article
    Gomez-Vilardebo J, Gunduz D, 2015,

    Smart Meter Privacy for Multiple Users in the Presence of an Alternative Energy Source

    , IEEE Transactions on Information Forensics and Security, Vol: 10, Pages: 132-141, ISSN: 1556-6021
  • Journal article
    Orhan O, Gunduz D, Erkip E, 2014,

    Energy Harvesting Broadband Communication Systems With Processing Energy Cost

    , IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, Vol: 13, Pages: 6095-6107, ISSN: 1536-1276
  • Journal article
    Pitt J, Busquets D, Macbeth S, 2014,

    Distributive justice for self-organised common-pool resource management

    , ACM Transactions on Autonomous and Adaptive Systems, Vol: 9, Pages: 1-24, ISSN: 1556-4665

    In this article, we complement Elinor Ostrom’s institutional design principles for enduring common-pool resource management with Nicholas Rescher’s theory of distributive justice based on the canon of legitimate claims. Two of Ostrom’s principles are that the resource allocation method should be congruent with the local environment, and that those affected by the allocation method (the appropriators) should participate in its selection. However, these principles do not say anything explicitly about the fairness of the allocation method or the outcomes it produces: for this, we need a mechanism for distributive justice. Rescher identified a number of different mechanisms, each of which had both its merits and demerits, and instead maintained that distributive justice consisted in identifying the legitimate claims in context, accommodating multiple claims in case of plurality, and reconciling them in case of conflict. Accordingly, we specify a logical axiomatisation of the principles with the canon of legitimate claims, whereby a set of claims is each represented as a voting function, which collectively determine the rank order in which resources are allocated. The appropriators vote on the weight attached to the scoring functions, and so self-organise the allocation method, taking into account both the plurality of and conflict between the claims. Therefore, the appropriators exercise collective choice over the method, and the method itself is congruent with the local environment, taking into account both the resources available and the relative claims of the appropriators. Experiments with a variant of the linear public good game show that this pluralistic self-organising approach produces a better balance of utility and fairness (for agents that comply with the rules of the game) compared to monistic or fixed approaches, provide “fairness over time” (a series of ostensibly unfair individual allocations is revealed to be cumulatively fa
  • Journal article
    Garcia-Trevino ED, Barria JA, 2014,

    Structural generative descriptions for time series classification

    , IEEE Transactions on Cybernetics, Vol: 44, Pages: 1978-1991, ISSN: 1083-4419

    In this paper, we formulate a novel time series representation framework that captures the inherent data dependency of time series and that can be easily incorporated into existing statistical classification algorithms. The impact of the proposed data representation stage in the solution to the generic underlying problem of time series classification is investigated. The proposed framework, which we call structural generative descriptions moves the structural time series representation to the probability domain, and hence is able to combine statistical and structural pattern recognition paradigms in a novel fashion. Two algorithm instantiations based on the proposed framework are developed. The algorithms are tested and compared using different publicly available real-world benchmark data. Results reported in this paper show the potential of the proposed representation framework, which in the experiments investigated, performs better or comparable to state-of-the-art time series description techniques.
  • Journal article
    Murin Y, Dabora R, Gunduz D, 2014,

    On Joint Source-Channel Coding for Correlated Sources Over Multiple-Access Relay Channels

    , IEEE TRANSACTIONS ON INFORMATION THEORY, Vol: 60, Pages: 6231-6253, ISSN: 0018-9448
  • Journal article
    Tuncel E, Gunduz D, 2014,

    Identification and Lossy Reconstruction in Noisy Databases

    , IEEE TRANSACTIONS ON INFORMATION THEORY, Vol: 60, Pages: 822-831, ISSN: 0018-9448
  • Conference paper
    Deniz O, Serrano I, Bueno G, Kim T-Ket al., 2014,

    Fast Violence Detection in Video

    , The 9th International Conference on Computer Vision Theory and Applications (VISAPP)
  • Journal article
    Gunduz D, Stamatiou K, Michelusi N, Zorzi Met al., 2014,

    Designing Intelligent Energy Harvesting Communication Systems

    , IEEE COMMUNICATIONS MAGAZINE, Vol: 52, Pages: 210-216, ISSN: 0163-6804
  • Conference paper
    Petruzzi PE, Busquets D, Pitt J, 2014,

    Experiments with Social Capital in Multi-agent Systems

    , 17th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), Publisher: SPRINGER-VERLAG BERLIN, Pages: 18-33, ISSN: 0302-9743
  • Conference paper
    Tang D, Yu T, Kim T-K, 2013,

    Real-time Articulated Hand Pose Estimation using Semi-supervised Transductive Regression Forests

    , IEEE Int. Conf. on Computer Vision (ICCV)
  • Conference paper
    Pei Y, Kim T-K, Zha H, 2013,

    Unsupervised Random Forest Manifold Alignment for Lipreading

    , IEEE Int. Conf. on Computer Vision (ICCV)
  • Journal article
    Lee K, Su Y, Kim T-K, Demiris Yet al., 2013,

    A syntactic approach to robot imitation learning using probabilistic activity grammars

    , Robotics and Autonomous Systems, Vol: 61, Pages: 1323-1334, ISSN: 0921-8890

    This paper describes a syntactic approach to imitation learning that captures important task structures in the form of probabilistic activity grammars from a reasonably small number of samples under noisy conditions. We show that these learned grammars can be recursively applied to help recognize unforeseen, more complicated tasks that share underlying structures. The grammars enforce an observation to be consistent with the previously observed behaviors which can correct unexpected, out-of-context actions due to errors of the observer and/or demonstrator. To achieve this goal, our method (1) actively searches for frequently occurring action symbols that are subsets of input samples to uncover the hierarchical structure of the demonstration, and (2) considers the uncertainties of input symbols due to imperfect low-level detectors.We evaluate the proposed method using both synthetic data and two sets of real-world humanoid robot experiments. In our Towers of Hanoi experiment, the robot learns the important constraints of the puzzle after observing demonstrators solving it. In our Dance Imitation experiment, the robot learns 3 types of dances from human demonstrations. The results suggest that under reasonable amount of noise, our method is capable of capturing the reusable task structures and generalizing them to cope with recursions.

This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.

Request URL: http://www.imperial.ac.uk:80/respub/WEB-INF/jsp/search-t4-html.jsp Request URI: /respub/WEB-INF/jsp/search-t4-html.jsp Query String: id=405&limit=30&page=1&respub-action=search.html Current Millis: 1686239821470 Current Time: Thu Jun 08 16:57:01 BST 2023