多面体问题下的 Frank-Wolfe 算法:严格互补性和稀疏性的再探讨
本研究提出一种新颖的基于谱 Frank-Wolfe 算法来处理凸优化问题的方法,该算法采用快速计算梯度的少量特征向量,并在每次迭代中解决一个小规模的 SDP 问题,以克服传统 Frank-Wolfe 算法由于忽略特征值重合而导致的收敛缓慢的问题。研究表明,优化问题的严格互补性是证明各种算法(如谱 Frank-Wolfe 算法、投影梯度法及其加速版本)线性收敛的关键。
Jun, 2020
提出了一种改进的条件梯度方法来解决约束凸优化问题,针对多面体进行了相应的分析及优化,降低了每次迭代时的计算及内存开销,并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。
May, 2016
本文研究了 Frank-Wolfe 算法,提出了几个变体并分别给出了全局线性收敛性证明,证明了不同算法的收敛速度取决于几何量与条件数的乘积,这些算法在机器学习,子模优化等领域取得了实际应用。
Nov, 2015
研究表明,当在具有 Lipschitz 梯度的强凸函数上应用梯度下降算法时,其收敛速度由函数的条件数决定且算法收敛速度类似于一个带有离开步骤的 Frank-Wolfe 算法。在对无约束情况的良好扩展中,算法的收敛速度由函数的条件数及多面体的某个特定条件数的乘积决定。本研究为这种类型多面体调整提出了新的方法,并且认为之前的相关方法是等价的,并可通过多面体的参数进行统一,从而实现算法的线性收敛。此外,对于凸二次目标,研究表明收敛速度取决于相应缩放多面体的条件数。
Dec, 2015
在本篇论文中,我们考虑了在强凸集上进行的优化的特殊情况。我们证明,与一般情况的收敛速度为 1/t 相比,vanila FW 方法以 1/t² 的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导 FW 方法的多个快速收敛结果。
Jun, 2014
本文介绍了一种零阶 Frank-Wolfe 算法,用于解决约束随机优化问题,该算法与基本 Frank-Wolfe 算法同样无需投影,且不需要计算梯度,可收敛于凸平滑约束下的优化目标函数。同时,本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数,本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4}),并在黑盒优化设置上进行实验,证明了其效果。
Oct, 2018
通过使用近端原始对偶算法和 Frank-Wolfe 算法,结合线性最小化 oracle 和低效率近端图来求解包括离散优化问题松弛之后的凸凹鞍点问题 —— 一个优化复杂且具有挑战性的问题,本文展示了该算法在诸如机器学习和计算机视觉等方面的标签问题上的应用。
Jan, 2021
本研究将 Frank-Wolfe 算法拓展至解决约束光滑凸 - 凹鞍点问题,只需要访问线性最小化神谕。通过利用 FW 优化的最近进展,我们首次证明了 FW 类型的鞍点求解器在多面体上的收敛性,并探讨了其他收敛结果和 FW 算法理论基础的缺口。同时,通过应用结构化预测与组合惩罚以及涉及指数数量的匹配多面体游戏等问题的研究,探讨了没有已知有效替代方案的潜在应用。
Oct, 2016
通过理论建立不同变体的 Frank-Wolfe(FW)算法的自适应步长,对一些机器学习及物理学问题,能够得到无需映射和保留稀疏性的优化,且对于具有无限曲率的自共轭函数,也可以获得全局收敛速率为 O (1/k) 或线性收敛速率的新的 FW 方法。
Feb, 2020
本文提出了一种名为 Frank-Wolfe Augmented Lagrangian (FW-AL) 算法的优化方法,该算法利用线性一致性约束来优化在相交凸集中的光滑函数,仅需要对单个约束的线性最小化预言机进行访问,并证明了该算法在一般凸紧集和多面体上的收敛率。
Apr, 2018