一种样本随机 Frank-Wolfe 算法

Oct, 2019

One Sample Stochastic Frank-Wolfe

Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, Amin Karbasi

TL;DR本文提出了一种称为 1-SFW 的新的随机 Frank-Wolfe 算法，通过设计一种新颖的无偏动量估计器，实现了使用每次迭代的单个样品来优化，而无需仔细调整批量大小、步长、学习速率和其他复杂的超参数，并在随机凸优化、随机 DR 亚模拟最大化问题和一般的非凸设置中达到了最优收敛率。

Abstract

One of the beauties of the projected gradient descent method lies in its rather simple mechanism and yet stable behavior with inexact, stochastic gradients, which has led to its wide-spread use in many machine learning applications. However, once we replace the projection operator with

projected gradient descent frank-wolfe method stochastic optimization unbiased momentum estimator convergence rate

发现论文，激发创造

无投影方差减少的随机优化

本研究利用一种新的方差降低技术，提出两种随机 Frank-Wolfe 算法变体，可在小于梯度下降算法的数据梯度评估次数下，获得更好的结果。

Feb, 2016

带有最佳效率和实用特性的约束优化方法

本文介绍了两种新的 Frank-Wolfe 算法变体，用于随机有限和最小化。这些方法在凸和非凸目标函数方面，都具有最佳的收敛保证。同时，本文提出的两种方法都不需要永久收集大批量数据和完整确定性梯度，可用于优化机器学习等领域中的结构约束问题。

Apr, 2023

面向无梯度和无投影的随机优化

本文介绍了一种零阶 Frank-Wolfe 算法，用于解决约束随机优化问题，该算法与基本 Frank-Wolfe 算法同样无需投影，且不需要计算梯度，可收敛于凸平滑约束下的优化目标函数。同时，本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数，本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4})，并在黑盒优化设置上进行实验，证明了其效果。

Oct, 2018

加速的随机无梯度投影方法

本文提出了一种加速的随机零阶 Frank-Wolfe 优化算法，通过使用 SPIDER/SpiderBoost 技术和一种新的动量加速技术，它可以在非凸优化中实现 O (d√nε⁻²) 的函数查询复杂度，并改进了现有最佳结果，同时在随机问题中实现了 O (dε⁻³) 的函数查询复杂度，同时提出了基于 STORM 的 Acc-SZOFW *，它不需要大批量也可以达到与 Acc-SZOFW 相同的函数查询复杂度。

Jul, 2020

随机条件梯度 ++

本文提出了一种用于非显式随机优化问题的算法 SFW ++，使用该算法可以快速收敛于全局最优解，并通过一些简单的结构扩展，可以优化跨不同优化问题的条件梯度方法。

Feb, 2019

随机 Frank-Wolfe 非凸优化方法

本文研究非凸随机优化和有限和优化问题中的 Frank-Wolfe 方法，并提出基于方差约减技术的新型非凸 Frank-Wolfe 方法，证明了其具有比传统方法更快的收敛速度。

Jul, 2016

Frank-Wolfe 算法的自共轭分析

通过理论建立不同变体的 Frank-Wolfe（FW）算法的自适应步长，对一些机器学习及物理学问题，能够得到无需映射和保留稀疏性的优化，且对于具有无限曲率的自共轭函数，也可以获得全局收敛速率为 O (1/k) 或线性收敛速率的新的 FW 方法。

Feb, 2020

Frank-Wolfe 方法自适应于误差界条件

本文表明，强凸集上使用 Frank-Wolfe 方法并加入步长搜索可以自适应地适用于问题的错误界限条件，从而获得更快的收敛速度。

Oct, 2018

Frank-Wolfe 方法在强凸集合上的更快收敛速率

在本篇论文中，我们考虑了在强凸集上进行的优化的特殊情况。我们证明，与一般情况的收敛速度为 1/t 相比，vanila FW 方法以 1/t² 的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导 FW 方法的多个快速收敛结果。

Jun, 2014

带有 CoreSet 保证的确定性非光滑 Frank Wolfe 算法

本文提出了一种新的 Frank-Wolfe (FW) 算法，可用于具有不光滑凸目标的最小化问题。该算法对包括 1-median、平衡发展、稀疏 PCA、图割和 L1 正则化支持向量机 (SVM) 在内的各种机器学习问题提供了核心集结果，它在时间复杂度上提供了近似解，不依赖于输入问题的大小。除了这些理论结果，我们还在实验中表明了该算法非常实用，有时也在处理大问题实例时提供重大的计算优势。

Aug, 2017