Playing non-linear games with linear oracles

Dan Garber, Elad Hazan

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

8 Scopus citations

Abstract

Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are example of problems for which we have efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and admit significantly less efficient algorithms. This motivates the computational model of online decision making and optimization using a linear optimization oracle. In this computational model we give the first efficient decision making algorithm with optimal regret guarantees, answering an open question of [1], [2], in case the decision set is a polytope. We also give an extension of the algorithm for the partial information setting, i.e. the "bandit" model. Our method is based on a novel variant of the conditional gradient method, or Frank-Wolfe algorithm, that reduces the task of minimizing a smooth convex function over a domain to that of minimizing a linear objective. Whereas previous variants of this method give rise to approximation algorithms, we give such algorithm that converges exponentially faster and thus runs in polynomial-time for a large class of convex optimization problems over polyhedral sets, a result of independent interest.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages420-428
Number of pages9
DOIs
StatePublished - Dec 1 2013
Externally publishedYes
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Convex optimization
  • Online algorithms
  • Regret minimization

Fingerprint Dive into the research topics of 'Playing non-linear games with linear oracles'. Together they form a unique fingerprint.

  • Cite this

    Garber, D., & Hazan, E. (2013). Playing non-linear games with linear oracles. In Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 (pp. 420-428). [6686178] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.52