一种新的 Frank-Wolfe 算法。分析及其在大规模 SVM 训练的应用

MMApr, 2013

一种新的 Frank-Wolfe 算法。分析及其在大规模 SVM 训练的应用

A Novel Frank-Wolfe Algorithm. Analysis and Applications to Large-Scale SVM Training

Hector Allende, Emanuele Frandi, Ricardo Nanculef, Claudio Sartori

TL;DR本研究提出并分析了一种基于新的 away steps 方法的 Frank-Wolfe 方法变种，重点研究了在 Simplex 上的一般凸优化问题。研究表明，该方法与传统的 away steps 可以达到相同的收敛速率和迭代次数，实验结果显示该方法比经典的 away steps 方法更快，而且精度不降。

Abstract

Recently, there has been a renewed interest in the machine learning community for variants of a sparse greedy approximation procedure for concave optimization known as {the Frank-Wolfe (FW) method}. In particular, this procedure has been successfully applied to train large-scale instan

machine learning frank-wolfe method support vector machines convergence analysis model sparsity

发现论文，激发创造

关于 Frank-Wolfe 优化变量的全局线性收敛性

本文研究了 Frank-Wolfe 算法，提出了几个变体并分别给出了全局线性收敛性证明，证明了不同算法的收敛速度取决于几何量与条件数的乘积，这些算法在机器学习，子模优化等领域取得了实际应用。

Nov, 2015

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

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

Apr, 2023

Frank-Wolfe 算法的自共轭分析

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

Feb, 2020

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

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

Aug, 2017

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

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

Jun, 2014

用于神经网络优化的深度 Frank-Wolfe 算法

本研究提出了基于深度神经网络中复合近端框架的优化方法，该方法利用了深度神经网络的组合性质，并通过设计利用强大的凸优化算法，对于解决高维、非凸和非光滑优化问题提供了一种新的方法。

Nov, 2018

使用 Frank-Wolfe 优化方法训练支持向量机

本文提出两种改进的基于 Frank-Wolfe 算法的 SVM 构建方法，能够更高效地解决大规模数据集下的最小包络球问题。实验证明，相比之前的 CVM 方法，这两种方法在大多数情况下都具有更好的扩展性。

Dec, 2012

通过 Frank-Wolfe 实现学徒式学习

研究使用 Frank-Wolfe 算法解决无显式奖励函数的 Markov 决策过程中的学徒学习问题，提出将专家的特征期望投影到特征期望凸多面体上，使用凸优化的 FW 算法来优化目标函数，得到更紧的收敛界，尤其是当采用 “步进调整” 方法时，收敛速度线性快于 FW 算法，并且增加随机性能够避免对特征期望的精确估计。

Nov, 2019

一种样本随机 Frank-Wolfe 算法

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

Oct, 2019

Frank-Wolfe 算法求解鞍点问题

本研究将 Frank-Wolfe 算法拓展至解决约束光滑凸 - 凹鞍点问题，只需要访问线性最小化神谕。通过利用 FW 优化的最近进展，我们首次证明了 FW 类型的鞍点求解器在多面体上的收敛性，并探讨了其他收敛结果和 FW 算法理论基础的缺口。同时，通过应用结构化预测与组合惩罚以及涉及指数数量的匹配多面体游戏等问题的研究，探讨了没有已知有效替代方案的潜在应用。

Oct, 2016