# On the Global Linear Convergence of Frank-Wolfe Optimization Variants

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

## Key facts

- Cited by 77 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2015.

## Built on by (most cited first, 30 of 77)

- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [HardCoRe-NAS: Hard Constrained diffeRentiable Neural Architecture Search](https://mlsanity.com/paper/2102.11646/) (2021)
- [Discovering Diverse Nearly Optimal Policies with Successor Features](https://mlsanity.com/paper/2106.00669/) (2021)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Active Exploration via Experiment Design in Markov Chains](https://mlsanity.com/paper/2206.14332/) (2022)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond](https://mlsanity.com/paper/2110.14759/) (2021)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy](https://mlsanity.com/paper/2101.07564/) (2021)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Robust Multi-Object Tracking by Marginal Inference](https://mlsanity.com/paper/2208.03727/) (2022)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Approximate Vanishing Ideal Computations at Scale](https://mlsanity.com/paper/2207.01236/) (2022)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings](https://mlsanity.com/paper/2110.08105/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization](https://mlsanity.com/paper/2205.12751/) (2022)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport](https://mlsanity.com/paper/2103.05857/) (2021)

## Abstract (arXiv)

The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary. A simple less-known fix is to add the possibility to take 'away steps' during optimization, an operation that importantly does not require a feasibility oracle. In this paper, we highlight and clarify several variants of the Frank-Wolfe optimization algorithm that have been successfully applied in practice: away-steps FW, pairwise FW, fully-corrective FW and Wolfe's minimum norm point algorithm, and prove for the first time that they all enjoy global linear convergence, under a weaker condition than strong convexity of the objective. The constant in the convergence rate has an elegant interpretation as the product of the (classical) condition number of the function with a novel geometric quantity that plays the role of a 'condition number' of the constraint set. We provide pointers to where these algorithms have made a difference in practice, in particular with the flow polytope, the marginal polytope and the base polytope for submodular optimization.