# New Analysis and Results for the Frank-Wolfe Method

arXiv: https://arxiv.org/abs/1307.0873 · HTML: https://mlsanity.com/paper/1307.0873/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2013.

## Built on by (most cited first, 17 of 17)

- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond](https://mlsanity.com/paper/2110.14759/) (2021)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Curriculum-based Asymmetric Multi-task Reinforcement Learning](https://mlsanity.com/paper/2211.03352/) (2022)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach](https://mlsanity.com/paper/2109.11135/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024)
- [A Multistep Frank-Wolfe Method](https://mlsanity.com/paper/2210.08110/) (2022)
- [Responsible AI (RAI) Games and Ensembles](https://mlsanity.com/paper/2310.18832/) (2023)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [A conditional gradient homotopy method with applications to Semidefinite Programming](https://mlsanity.com/paper/2207.03101/) (2022)
- [On Finite-Step Convergence of the Non-Greedy Algorithm and Proximal Alternating Minimization Method with Extrapolation for L1-Norm PCA](https://mlsanity.com/paper/2302.07712/) (2023)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [Learning the Right Layers: a Data-Driven Layer-Aggregation Strategy for Semi-Supervised Learning on Multilayer Graphs](https://mlsanity.com/paper/2306.00152/) (2023)
- [Federated Frank-Wolfe Algorithm](https://mlsanity.com/paper/2408.10090/) (2024)

## Abstract (arXiv)

We present new results for the Frank-Wolfe method (also known as the conditional gradient method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps and the so-called FW gaps. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions.