Lazifying Conditional Gradient Algorithms
Lazifying Conditional Gradient Algorithms
复制标题
惰性条件梯度算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Daniel Zink
中科院分区：
文献类型：
--
作者：
Gábor Braun;S. Pokutta;Daniel Zink
条件梯度算法（也称为Frank-Wolfe算法）由于其简单性而流行，仅需要线性优化预言，最近它们也获得了在线学习的显着吸引力。虽然原则上很简单，但在许多情况下，线性优化预言的实际实现是昂贵的。我们展示了一个通用的方法来Lazify各种条件梯度算法，这在实际计算中会导致几个数量级的挂钟时间加速。这是通过使用更快的分离预言机而不是线性优化预言机来实现的，仅依赖于几个线性优化预言机调用。
Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.