Fast Convergence of Frank-Wolfe Algorithms on Polytopes
- 1 May 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 1463-1485
Abstract
We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function but not on any affine-dependent object like norms. For each one of the above algorithms, we derive rates of convergence ranging from sublinear to linear depending on the degree of the error bound. Funding: Research reported in this paper was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—The Berlin Mathematics Research Center MATH (EXC-2046/1, project ID 390685689, BMS Stipend). Research reported in this paper was also partially supported by the Bajaj Family Chair at the Tepper School of Business, Carnegie Mellon University.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Affine Invariant Convergence Rates of the Conditional Gradient MethodSIAM Journal on Optimization, 2023
- The condition number of a function relative to a setMathematical Programming, 2020
- An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix CompletionSIAM Journal on Optimization, 2017
- Linearly convergent away-step conditional gradient for non-strongly convex functionsMathematical Programming, 2016
- Analysis of the Convergence Rate for the Cyclic Projection Algorithm Applied to Basic Semialgebraic Convex SetsSIAM Journal on Optimization, 2014
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society Series B: Statistical Methodology, 1996
- Some comments on Wolfe's ‘away step’Mathematical Programming, 1986
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular ExtremalsSIAM Journal on Control and Optimization, 1979
- An extension of the frank and Wolfe method of feasible directionsMathematical Programming, 1974
- Constrained minimization methodsUSSR Computational Mathematics and Mathematical Physics, 1966