A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
Dan Garber Technion - Israel Inst. of Tech. Elad Hazan Technion - Israel Inst. of Tech.
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 simple and efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and admits significantly less efficient algorithms. This motivates the computational model of convex optimization, including the offline, online and stochastic settings, using a linear optimization oracle. In this computational model we give several new results that improve over the previous state-of-the-art. Our main result is a novel conditional gradient algorithm for smooth and strongly convex optimization over polyhedral sets that performs only a single linear optimization step over the domain on each iteration and enjoys a linear convergence rate. This gives an exponential improvement in convergence rate over previous results.
中文速览
把投影步骤换成线性规划来做凸优化，在拟阵多面体、路径多面体等结构化约束上往往快得多，但以往的条件梯度（Frank-Wolfe）算法在光滑强凸目标下收敛很慢，在在线/随机场景下也要么收敛率次优，要么每轮需要多次线性规划调用。本文提出了一种新的条件梯度算法，针对多面体约束上的光滑强凸优化，每轮只需一次线性规划，就能实现线性收敛速率，相比此前最优结果在收敛阶上取得了指数级改进；在此基础上，作者进一步给出了首批在每轮仅调用一次线性规划的条件下同时达到最优遗憾界的在线凸优化算法，解决了 Kalai-Vempala 和 Hazan-Kale 提出的公开问题，并将这些结果推广到非光滑离线优化和随机优化，使条件梯度方法在这些场景下的收敛率与投影次梯度法持平。这项工作系统地将投影操作替换为更廉价的线性规划，同时在理论保证上不作任何妥协，为大规模结构化优化问题提供了切实可行的高效算法框架。
原文 arXiv:1301.4666;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1301.4666v6