The computational power of optimization in online learning

Elad Hazan, Tomer Koren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We consider the fundamental problem of prediction with expert advice where the experts are "optimizable": there is a black-box optimization oracle that can be used to compute, in constant time, the leading expert in retrospect at any point in time. In this setting, we give a novel online algorithm that atta?ins vanishing regret with respect to N experts in total Õ (√n)q computation time. We also give a lower bound showing that this running time cannot be improved (up to log factors) in the oracle model, thereby exhibiting a quadratic speedup as compared to the standard, oracle-free setting where the required time for vanishing rer gret is TpNq. These results demonstrate an exponential gap between the power of optimization in online learning and its power in statistical learning: in the latter, an optimization oracle-i.e., an efficient empirical risk minimizer-allows to learn a finite hypothesis class of size N in time Oplog Nq. We also study the implications of our results to learning in repeated zero-sum games, in a setting where the players have access to oracles that compute, in constant time, their bestresponse to any mixed strategy of their opponent. We show that the runtime required for approx?imating the minimax r value of the game in this setting is Tp Nq, yielding again a quadratic improvement upon the oracle-free setting, where r Θ(N) is known to be tight.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages128-141
Number of pages14
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Best-response dynamics
  • Learning in games
  • Local search
  • Online learning
  • Optimization oracles
  • Zero-sum games

Cite this

Hazan, E., & Koren, T. (2016). The computational power of optimization in online learning. In Y. Mansour, & D. Wichs (Eds.), STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 128-141). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897536