mlsanityData to 14 Oct 2026

On the Global Linear Convergence of Frank-Wolfe Optimization Variants

arXiv 1511.05932 ↗First posted 18 Nov 2015math.OC cs.LG stat.MLcited by 77

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 25; 2022: 20; 2023: 10; 2024: 3; 2025: 11; 2026: 8.

77 papers.

Sort:

By area:

  1. 2021Reward is enough for convex MDPscited by 84
  2. 2022Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfecited by 22
  3. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 21
  4. 2021Complexity of Linear Minimization and Projection on Some Setscited by 20
  5. 2021HardCoRe-NAS: Hard Constrained diffeRentiable Neural Architecture Searchcited by 20
  6. 2021Discovering Diverse Nearly Optimal Policies with Successor Featurescited by 20
  7. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  8. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  9. 2021Deep Graph Matching under Quadratic Constraintcited by 18
  10. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  11. 2021Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyondcited by 10
  12. 2023Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programmingcited by 10
38 more
  1. 2025Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Boundcited by 9
  2. 2021Frank-Wolfe with a Nearest Extreme Point Oraclecited by 8
  3. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  4. 2022Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimizationcited by 8
  5. 2024Online Convex Optimization with a Separation Oraclecited by 8
  6. 2021Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancycited by 7
  7. 2021Heavy Ball Momentum for Conditional Gradientcited by 7
  8. 2022Robust Multi-Object Tracking by Marginal Inferencecited by 7
  9. 2023Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Featurescited by 7
  10. 2021Linear Bandits on Uniformly Convex Setscited by 6
  11. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  12. 2022Approximate Vanishing Ideal Computations at Scalecited by 6
  13. 2021Parameter-free Locally Accelerated Conditional Gradientscited by 5
  14. 2021Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderingscited by 5
  15. 2021First-Order Methods for Convex Optimizationcited by 4
  16. 2022Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelizationcited by 4
  17. 2023Projection-Free Online Convex Optimization via Efficient Newton Iterationscited by 4
  18. 2021Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transportcited by 3
  19. 2022Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimatorcited by 3
  20. 2022Solving Constrained Variational Inequalities via a First-order Interior Point-based Methodcited by 3
  21. 2022Convex mixed-integer optimization with Frank-Wolfe methodscited by 3
  22. 2022Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oraclecited by 3
  23. 2023Faster Discrete Convex Function Minimization with Predictions: The M-Convex Casecited by 3
  24. 2025LITE: Efficiently Estimating Gaussian Probability of Maximalitycited by 3
  25. 2021Sparse solutions of the kernel herding algorithm by improved gradient approximationcited by 2
  26. 2021Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopescited by 2
  27. 2021Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Gamescited by 2
  28. 2022Accelerating Frank-Wolfe via Averaging Step Directionscited by 2
  29. 2022Boosting as Frank-Wolfecited by 2
  30. 2023On graph-based reentrancy-free semantic parsingcited by 2
  31. 2023Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Normcited by 2
  32. 2021Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Stepscited by 1
  33. 2022Conditional Gradients for the Approximate Vanishing Idealcited by 1
  34. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  35. 2022A Multistep Frank-Wolfe Methodcited by 1
  36. 2025First-Order Sparse Convex Optimization: Better Rates with Sparse Updatescited by 1
  37. 2025Scalable DC Optimization via Adaptive Frank-Wolfe Algorithmscited by 1
  38. 2026PolyFlow: Safe and Efficient Polytope-Constrained Flow Matching with Constraint Embedding and Projection-free Updatecited by 1

50 most cited of 77 All 77 (JSON)