本文介绍了两种新的 Frank-Wolfe 算法变体,用于随机有限和最小化。这些方法在凸和非凸目标函数方面,都具有最佳的收敛保证。同时,本文提出的两种方法都不需要永久收集大批量数据和完整确定性梯度,可用于优化机器学习等领域中的结构约束问题。
Apr, 2023
本研究利用一种新的方差降低技术,提出两种随机 Frank-Wolfe 算法变体,可在小于梯度下降算法的数据梯度评估次数下,获得更好的结果。
Feb, 2016
本文介绍了一种零阶 Frank-Wolfe 算法,用于解决约束随机优化问题,该算法与基本 Frank-Wolfe 算法同样无需投影,且不需要计算梯度,可收敛于凸平滑约束下的优化目标函数。同时,本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数,本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4}),并在黑盒优化设置上进行实验,证明了其效果。
Oct, 2018
探讨在线变体的 Frank-Wolfe 算法,包括简单迭代更新和非自适应步长规则,研究凸和非凸损失的多个新结果,并基于对随机 Frank-Wolfe 算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为 O (log^3T/T) 和 O (log^2T/T) ; 此外,该在线算法即使在损失非凸的情况下也能收敛,以速率 O (1/T 的平方根) 找到时变 / 随机损失的稳态点。
Oct, 2015
本文研究了 Frank-Wolfe 算法,提出了几个变体并分别给出了全局线性收敛性证明,证明了不同算法的收敛速度取决于几何量与条件数的乘积,这些算法在机器学习,子模优化等领域取得了实际应用。
Nov, 2015
本文提出了一种称为 1-SFW 的新的随机 Frank-Wolfe 算法,通过设计一种新颖的无偏动量估计器,实现了使用每次迭代的单个样品来优化,而无需仔细调整批量大小、步长、学习速率和其他复杂的超参数,并在随机凸优化、随机 DR 亚模拟最大化问题和一般的非凸设置中达到了最优收敛率。
Oct, 2019
在本篇论文中,我们考虑了在强凸集上进行的优化的特殊情况。我们证明,与一般情况的收敛速度为 1/t 相比,vanila FW 方法以 1/t² 的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导 FW 方法的多个快速收敛结果。
Jun, 2014
本文提出了一种加速的随机零阶 Frank-Wolfe 优化算法,通过使用 SPIDER/SpiderBoost 技术和一种新的动量加速技术,它可以在非凸优化中实现 O (d√nε⁻²) 的函数查询复杂度,并改进了现有最佳结果,同时在随机问题中实现了 O (dε⁻³) 的函数查询复杂度,同时提出了基于 STORM 的 Acc-SZOFW *,它不需要大批量也可以达到与 Acc-SZOFW 相同的函数查询复杂度。
Jul, 2020
对于非凸、非光滑函数的关键点寻找问题,本文研究了三种基于梯度的方法 (梯度下降、近端更新、弗兰克 - 沃尔夫更新) 的行为,并证明了这些算法的收敛速率,同时也为连续亚解析函数证明了更快的收敛速率,优化后的算法具有更低的迭代成本,并通过应用于最佳子集选择、鲁棒估计、混合密度估计和形状阴影重建等问题,展示了方法和理论的实际效果。
Apr, 2018
该研究提供了一个简单的证明,表明 Frank-Wolfe 算法在具有 Lipschitz 连续梯度的非凸目标上,以 O(1 /sqrt {t})的速率获得静止点。
Jul, 2016