Playing Non-linear Games with Linear Oracles
Playing Non-linear Games with Linear Oracles
复制标题
使用线性预言机玩非线性游戏
DOI：
10.1109/focs.2013.52
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Elad Hazan
中科院分区：
文献类型：
--
作者：
D. Garber;Elad Hazan
线性优化在算法上比非线性凸优化更简单。对矩阵多型，匹配的多面体和路径多型的线性优化是我们具有有效组合算法的问题的示例，但其非线性凸面对应物更难，并且承认效率较小。这激发了使用线性优化Oracle的在线决策制定和优化的计算模型。在此计算模型中，我们给出了最佳遗憾保证的第一个有效决策算法，以回答Kalai和Vempala，Hazan和Kale的开放问题，以防决策集是多门的。我们还为部分信息设置（即“ Bandit”模型）提供了算法的扩展。我们的方法基于条件梯度方法的新型变体或Frank-Wolfe算法，该方法可降低将平滑凸功能在域上最小化的任务，以最大程度地减少线性目标。尽管该方法的先前变体产生了近似算法，但我们给出了这种算法，该算法呈指数级的收敛速度，从而在多项式时间内运行，对于多面体集合的大量凸优化问题，这是独立利益的结果。
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 Kalai and Vempala, Hazan and Kale, 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.