TY - GEN

T1 - Playing non-linear games with linear oracles

AU - Garber, Dan

AU - Hazan, Elad

PY - 2013

Y1 - 2013

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

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

KW - Convex optimization

KW - Online algorithms

KW - Regret minimization

UR - http://www.scopus.com/inward/record.url?scp=84893478740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893478740&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2013.52

DO - 10.1109/FOCS.2013.52

M3 - Conference contribution

AN - SCOPUS:84893478740

SN - 9780769551357

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 420

EP - 428

BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

Y2 - 27 October 2013 through 29 October 2013

ER -