Search or filter publications

Filter by type:

Filter by publication type

Filter by year:



  • 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,

    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

    , 2nd Content Caching and Delivery in Wireless Networks Workshop (CCDWN 2017), Publisher: IEEE

    We propose an intelligent proactive content cachingscheme to reduce the energy consumption in wireless downlink.We consider an online social network (OSN) setting where newcontents are generated over time, and remainrelevantto theuser for a random lifetime. Contents are downloaded to the userequipment (UE) through a time-varying wireless channel at anenergy cost that depends on the channel state and the number ofcontents downloaded. The user accesses the OSN at random timeinstants, and consumes all the relevant contents. To reduce theenergy consumption, we proposeproactive cachingof contentsunder favorable channel conditions to a finite capacity cachememory. Assuming that the channel quality (or equivalently, thecost of downloading data) is memoryless over time slots, we showthat the optimal caching policy, which may replace contents inthe cache with shorter remaining lifetime with contents at theserver that remain relevant longer, has a threshold structurewith respect to the channel quality. Since the optimal policy iscomputationally demanding in practice, we introduce a simplifiedcaching 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 proposedcaching scheme significantly reduces the energy consumptioncompared 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 con-tents into a finite capacity cache memory of a user equipmentin order to reduce the long-term average energy consumption ina wireless network. We consider an online social network (OSN)framework, in which new contents are generated over time andeach content remains relevant to the user for a random timeperiod, called thelifetimeof the content. The user accesses theOSN through a wireless network at random time instants todownload and consume all the relevant contents. Downloadingcontents has an energy cost that depends on the channel state andthe number of downloaded contents. Our aim is to reduce thelong-term average energy consumption by proactively cachingcontents at favorable channel conditions.In previous work, it was shown that the optimal caching policyis infeasible to compute (even with the complete knowledge of astochastic model describing the system), and a simple family ofthreshold policies was introduced and optimised using the finitedifference method. In this paper we improve upon both com-ponents of this approach: we use linear function approximation(LFA) to better approximate the considered family of cachingpolicies, and apply the REINFORCE algorithm to optimise itsparameters. Numerical simulations show that the new approachprovides reduction in both the average energy cost and therunning 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

    © 2016 by the author(s). 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, Pages: 854-864, ISSN: 1524-9050
  • 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

  • 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
    Kokuti A, Gelenbe E, 2014,

    Directional Navigation Improves Opportunistic Communication for Emergencies

    , Sensors, Vol: 14, Pages: 15387-15399, ISSN: 1424-8220

    We present a novel direction based shortest path search algorithm to guideevacuees during an emergency. It uses opportunistic communications (oppcomms) withlow-cost wearable mobile nodes that can exchange packets at close range of a few to sometens of meters without help of an infrastructure. The algorithm seeks the shortest path to exitswhich are safest with regard to a hazard, and is integrated into an autonomous EmergencySupport System (ESS) to guide evacuees in a built environment. The algorithm proposedthat ESSs are evaluated with the DBES (Distributed Building Evacuation Simulator) bysimulating a shopping centre where fire is spreading. The results show that the directionalpath finding algorithm can offer significant improvements for the evacuees.

  • Journal article
    Gelenbe E, 2014,

    Emergency Navigation without an Infrastructure

    , Sensors, Vol: 14, Pages: 15142-15162, ISSN: 1424-8220
  • Journal article
    Gelenbe E, Abdelrahman OH, 2014,

    Search in the Universe of Big Networks and Data

    , IEEE Network, Vol: 28, Pages: 20-25, ISSN: 0890-8044

    Searching in the Internet for some object characterisedby its attributes in the form of data, such as a hotel ina certain city whose price is less than something, is one of ourmost common activities when we access the Web. We discuss thisproblem in a general setting, and compute the average amount oftime and the energy it takes to find an object in an infinitely largesearch space. We consider the use of N search agents which actconcurrently. Both the case where the search agent knows whichway it needs to go to find the object, and the case where thesearch agent is perfectly ignorant and may even head away fromthe object being sought. We show that under mild conditionsregarding the randomness of the search and the use of a time-out,the search agent will always find the object despite the fact thatthe search space is infinite. We obtain a formula for the averagesearch time and the average energy expended by N search agentsacting concurrently and independently of each other. We see thatthe time-out itself can be used to minimise the search time andthe amount of energy that is consumed to find an object. Anapproximate formula is derived for the number of search agentsthat can help us guarantee that an object is found in a giventime, and we discuss how the competition between search agentsand other agents that try to hide the data object, can be usedby opposing parties to guarantee their own success.

  • Journal article
    Garcia-Trevino ED, Barria JA, 2014,

    Structural Generative Descriptions for Time Series Classification

  • 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
    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
  • Journal article
    Kim H, Park T, Gelenbe E, 2014,

    Identifying disease candidate genes via large-scale gene network analysis

  • Conference paper
    Gelenbe E, Han Q, 2014,

    Near-Optimal Emergency Evacuation with Rescuer Allocation

    , 12th IEEE International Conference on Pervasive Computing and Communication (PERCOM), Publisher: IEEE, Pages: 314-319, ISSN: 2474-2503

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: Request URI: /respub/WEB-INF/jsp/search-t4-html.jsp Query String: id=405&limit=30&respub-action=search.html Current Millis: 1582301996869 Current Time: Fri Feb 21 16:19:56 GMT 2020