Practical Frank-Wolfe algorithms
Practical Frank-Wolfe algorithms
复制标题
实用 Frank-Wolfe 算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
V. Kolmogorov
中科院分区：
文献类型：
--
作者：
V. Kolmogorov
在过去的十年里，人们对Frank-Wolfe（FW）风格的方法重新产生了兴趣，用于优化多面体上的光滑凸函数。最近开发的技术的示例包括{em分解不变条件梯度}（DiCG）、{em混合条件梯度}（BCG）和{em具有面内方向的Frank-Wolfe}（IF-FW）方法。我们介绍这些技术的两个扩展。首先，我们使用{em工作集}策略增强DiCG，并展示如何使用{em阴影单纯形步骤}优化工作集。其次，我们将面内Frank-Wolfe方向概括为无法有效计算面的多面体，并且还描述了一个可以与几种FW风格技术结合使用的通用递归过程。实验结果表明，这些扩展是能够加快原始算法的数量级为某些应用程序。
In the last decade there has been a resurgence of interest in Frank-Wolfe (FW) style methods for optimizing a smooth convex function over a polytope. Examples of recently developed techniques include {em Decomposition-invariant Conditional Gradient} (DiCG), {em Blended Condition Gradient} (BCG), and {em Frank-Wolfe with in-face directions} (IF-FW) methods. We introduce two extensions of these techniques. First, we augment DiCG with the {em working set} strategy, and show how to optimize over the working set using {em shadow simplex steps}. Second, we generalize in-face Frank-Wolfe directions to polytopes in which faces cannot be efficiently computed, and also describe a generic recursive procedure that can be used in conjunction with several FW-style techniques. Experimental results indicate that these extensions are capable of speeding up original algorithms by orders of magnitude for certain applications.
行走在阴影中：约束最小化下降方向的新视角
DOI：
--
发表时间：
2020
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Mortagy, H;Gupta, S;Pokutta, S
通讯作者：
Pokutta, S