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
    Huang R, Lattimore T, György A, Szepesvári Cet al., 2017,

    Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities

    , ISSN: 1532-4435

    © 2017 Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Follow the leader (FTL) is a simple online learning algorithm that is known to perform well when the loss functions are convex and positively curved. In this paper we ask whether there are other settings when FTL achieves low regret. In particular, we study the fundamental problem of linear prediction over a convex, compact domain with non-empty interior. Amongst other results, we prove that the curvature of the boundary of the domain can act as if the losses were curved: In this case, we prove that as long as the mean of the loss vectors have positive lengths bounded away from zero, FTL enjoys logarithmic regret, while for polytope domains and stochastic data it enjoys finite expected regret. The former result is also extended to strongly convex domains by establishing an equivalence 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 also get an algorithm that simultaneously enjoys the worst-case guarantees and the smaller regret of FTL 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 the constraint set is an ellipsoid.

  • 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, György A, Szepesvári C, 2017,

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

    , Publisher: PMLR, Pages: 681-720
  • CONFERENCE PAPER
    Somuyiwa SO, 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
  • CONFERENCE PAPER
    Somuyiwa SO, 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 (WiOpt), Publisher: IEEE
  • 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
    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
    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
    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
    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.

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

  • 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
  • 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
    Babaee A, Draief M, 2014,

    Distributed Multivalued Consensus

    , COMPUTER JOURNAL, Vol: 57, Pages: 1132-1140, ISSN: 0010-4620
  • CONFERENCE PAPER
    Bi H, Gelenbe E, 2014,

    Routing Diverse Evacuees with Cognitive Packets

    , 12th IEEE International Conference on Pervasive Computing and Communication (PERCOM), Publisher: IEEE, Pages: 291-296, ISSN: 2474-2503
  • CONFERENCE PAPER
    Deniz O, Serrano I, Bueno G, Kim T-Ket al., 2014,

    Fast Violence Detection in Video

    , 9th International Conference on Computer Vision Theory and Applications (VISAPP), Publisher: IEEE, Pages: 478-485
  • CONFERENCE PAPER
    Desmet A, Gelenbe E, 2014,

    Capacity Based Evacuation with Dynamic Exit Signs

    , 12th IEEE International Conference on Pervasive Computing and Communication (PERCOM), Publisher: IEEE, Pages: 332-337, ISSN: 2474-2503
  • JOURNAL ARTICLE
    Garcia-Trevino ES, Barria JA, 2014,

    Structural Generative Descriptions for Time Series Classification

    , IEEE TRANSACTIONS ON CYBERNETICS, Vol: 44, Pages: 1978-1991, ISSN: 2168-2267
  • 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
    Gelenbe E, Bi H, 2014,

    Emergency Navigation without an Infrastructure

    , SENSORS, Vol: 14, Pages: 15142-15162, ISSN: 1424-8220
  • 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
  • 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
  • JOURNAL ARTICLE
    Kim H, Park T, Gelenbe E, 2014,

    Identifying disease candidate genes via large-scale gene network analysis

    , INTERNATIONAL JOURNAL OF DATA MINING AND BIOINFORMATICS, Vol: 10, Pages: 175-188, ISSN: 1748-5673
  • JOURNAL ARTICLE
    Kokuti A, Gelenbe E, 2014,

    Directional Navigation Improves Opportunistic Communication for Emergencies

    , SENSORS, Vol: 14, Pages: 15387-15399, ISSN: 1424-8220
  • 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

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://wlsprd.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&respub-action=search.html Current Millis: 1524400504834 Current Time: Sun Apr 22 13:35:04 BST 2018