Playing non-linear games with linear oracles

Dan Garber, Elad Hazan

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

22 Scopus citations


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
Number of pages9
StatePublished - 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


Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Country/TerritoryUnited States
CityBerkeley, CA

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • Convex optimization
  • Online algorithms
  • Regret minimization


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

Cite this