# An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2013.

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

- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [Conditional Gradients for the Approximate Vanishing Ideal](https://mlsanity.com/paper/2202.03349/) (2022)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [Generating Structured Adversarial Attacks Using Frank-Wolfe Method](https://mlsanity.com/paper/2102.07360/) (2021)
- [Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes](https://mlsanity.com/paper/2505.11259/) (2025)

## Abstract (arXiv)

We study the linear convergence of variants of the Frank-Wolfe algorithms for some classes of strongly convex problems, using only affine-invariant quantities. As in Guelat & Marcotte (1986), we show the linear convergence of the standard Frank-Wolfe algorithm when the solution is in the interior of the domain, but with affine invariant constants. We also show the linear convergence of the away-steps variant of the Frank-Wolfe algorithm, but with constants which only depend on the geometry of the domain, and not any property of the location of the optimal solution. Running these algorithms does not require knowing any problem specific parameters.