# Fast convergence of Frank-Wolfe algorithms on polytopes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2024.

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

- [Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes](https://mlsanity.com/paper/2505.11259/) (2025)

## Abstract (arXiv)

We provide a template to derive 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.