通过理论建立不同变体的 Frank-Wolfe(FW)算法的自适应步长,对一些机器学习及物理学问题,能够得到无需映射和保留稀疏性的优化,且对于具有无限曲率的自共轭函数,也可以获得全局收敛速率为 O (1/k) 或线性收敛速率的新的 FW 方法。
Feb, 2020
本文研究了 Frank-Wolfe 算法,提出了几个变体并分别给出了全局线性收敛性证明,证明了不同算法的收敛速度取决于几何量与条件数的乘积,这些算法在机器学习,子模优化等领域取得了实际应用。
Nov, 2015
本文介绍了两种新的 Frank-Wolfe 算法变体,用于随机有限和最小化。这些方法在凸和非凸目标函数方面,都具有最佳的收敛保证。同时,本文提出的两种方法都不需要永久收集大批量数据和完整确定性梯度,可用于优化机器学习等领域中的结构约束问题。
Apr, 2023
在本篇论文中,我们考虑了在强凸集上进行的优化的特殊情况。我们证明,与一般情况的收敛速度为 1/t 相比,vanila FW 方法以 1/t² 的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导 FW 方法的多个快速收敛结果。
Jun, 2014
本文探讨了强凸约束条件下的 Frank-Wolfe(FW)优化,展示了一个比标准 FW 更快的变体的更快收敛速度,证明了即使对于非凸而是半凸和局部 Lipschitz 的平滑函数,FW 也可以通过线搜索收敛到全局最优解,并且展示了在强凸约束集下,对于一般情况(平滑)的非凸函数,FW 带有线搜索以高概率收敛到一个 $O (1/t)$ 的速率上。
Nov, 2018
本文提出了一种新的 Frank-Wolfe (FW) 算法,可用于具有不光滑凸目标的最小化问题。该算法对包括 1-median、平衡发展、稀疏 PCA、图割和 L1 正则化支持向量机 (SVM) 在内的各种机器学习问题提供了核心集结果,它在时间复杂度上提供了近似解,不依赖于输入问题的大小。除了这些理论结果,我们还在实验中表明了该算法非常实用,有时也在处理大问题实例时提供重大的计算优势。
Aug, 2017
本文提出了一种用于非显式随机优化问题的算法 SFW ++,使用该算法可以快速收敛于全局最优解,并通过一些简单的结构扩展,可以优化跨不同优化问题的条件梯度方法。
Feb, 2019
本研究提出并分析了一种基于新的 away steps 方法的 Frank-Wolfe 方法变种,重点研究了在 Simplex 上的一般凸优化问题。 研究表明,该方法与传统的 away steps 可以达到相同的收敛速率和迭代次数,实验结果显示该方法比经典的 away steps 方法更快,而且精度不降。
Apr, 2013
我们研究了凸函数的平滑结构,通过将 Nesterov 和 Nemirovsky 在 1990 年代早期引入的强大概念(称为自共轭性)推广到更广泛的凸函数类,我们称之为广义自共轭函数。 这个概念使我们能够开发出设计 Newton 类型方法来解决凸优化问题的统一框架。
Mar, 2017
本研究将 Frank-Wolfe 算法拓展至解决约束光滑凸 - 凹鞍点问题,只需要访问线性最小化神谕。通过利用 FW 优化的最近进展,我们首次证明了 FW 类型的鞍点求解器在多面体上的收敛性,并探讨了其他收敛结果和 FW 算法理论基础的缺口。同时,通过应用结构化预测与组合惩罚以及涉及指数数量的匹配多面体游戏等问题的研究,探讨了没有已知有效替代方案的潜在应用。
Oct, 2016