Frank-Wolfe 方法在强凸集合上的更快收敛速率
本文探讨了强凸约束条件下的 Frank-Wolfe(FW)优化,展示了一个比标准 FW 更快的变体的更快收敛速度,证明了即使对于非凸而是半凸和局部 Lipschitz 的平滑函数,FW 也可以通过线搜索收敛到全局最优解,并且展示了在强凸约束集下,对于一般情况(平滑)的非凸函数,FW 带有线搜索以高概率收敛到一个 $O (1/t)$ 的速率上。
Nov, 2018
本文研究了 Frank-Wolfe 算法,提出了几个变体并分别给出了全局线性收敛性证明,证明了不同算法的收敛速度取决于几何量与条件数的乘积,这些算法在机器学习,子模优化等领域取得了实际应用。
Nov, 2015
本文介绍了两种新的 Frank-Wolfe 算法变体,用于随机有限和最小化。这些方法在凸和非凸目标函数方面,都具有最佳的收敛保证。同时,本文提出的两种方法都不需要永久收集大批量数据和完整确定性梯度,可用于优化机器学习等领域中的结构约束问题。
Apr, 2023
研究表明,当在具有 Lipschitz 梯度的强凸函数上应用梯度下降算法时,其收敛速度由函数的条件数决定且算法收敛速度类似于一个带有离开步骤的 Frank-Wolfe 算法。在对无约束情况的良好扩展中,算法的收敛速度由函数的条件数及多面体的某个特定条件数的乘积决定。本研究为这种类型多面体调整提出了新的方法,并且认为之前的相关方法是等价的,并可通过多面体的参数进行统一,从而实现算法的线性收敛。此外,对于凸二次目标,研究表明收敛速度取决于相应缩放多面体的条件数。
Dec, 2015
通过理论建立不同变体的 Frank-Wolfe(FW)算法的自适应步长,对一些机器学习及物理学问题,能够得到无需映射和保留稀疏性的优化,且对于具有无限曲率的自共轭函数,也可以获得全局收敛速率为 O (1/k) 或线性收敛速率的新的 FW 方法。
Feb, 2020
该研究提供了一个简单的证明,表明 Frank-Wolfe 算法在具有 Lipschitz 连续梯度的非凸目标上,以 O(1 /sqrt {t})的速率获得静止点。
Jul, 2016
本文介绍了一种零阶 Frank-Wolfe 算法,用于解决约束随机优化问题,该算法与基本 Frank-Wolfe 算法同样无需投影,且不需要计算梯度,可收敛于凸平滑约束下的优化目标函数。同时,本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数,本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4}),并在黑盒优化设置上进行实验,证明了其效果。
Oct, 2018
本文研究非凸随机优化和有限和优化问题中的 Frank-Wolfe 方法,并提出基于方差约减技术的新型非凸 Frank-Wolfe 方法,证明了其具有比传统方法更快的收敛速度。
Jul, 2016
本文提出了一种称为 1-SFW 的新的随机 Frank-Wolfe 算法,通过设计一种新颖的无偏动量估计器,实现了使用每次迭代的单个样品来优化,而无需仔细调整批量大小、步长、学习速率和其他复杂的超参数,并在随机凸优化、随机 DR 亚模拟最大化问题和一般的非凸设置中达到了最优收敛率。
Oct, 2019