# Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 52 references that are in the map.
- First posted on arXiv 16 May 2025.

## Builds on (most cited first, 27 of 27)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization](https://mlsanity.com/paper/1301.4666/) (2013)
- [Conditional Gradient Methods](https://mlsanity.com/paper/2211.14103/) (2022)
- [Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions](https://mlsanity.com/paper/1504.05002/) (2015)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Frank-Wolfe Splitting via Augmented Lagrangian Method](https://mlsanity.com/paper/1804.03176/) (2018)
- [Approximate Vanishing Ideal Computations at Scale](https://mlsanity.com/paper/2207.01236/) (2022)
- [An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms](https://mlsanity.com/paper/1312.7864/) (2013)
- [Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants](https://mlsanity.com/paper/1806.03430/) (2018)
- [Beyond Short Steps in Frank-Wolfe Algorithms](https://mlsanity.com/paper/2501.18773/) (2025)
- [Transversality and alternating projections for nonconvex sets](https://mlsanity.com/paper/1401.7569/) (2014)
- [The Cyclic Block Conditional Gradient Method for Convex Optimization Problems](https://mlsanity.com/paper/1502.03716/) (2015)
- [Square distance functions are Polyak-Lojasiewicz and vice-versa](https://mlsanity.com/paper/2301.10332/) (2023)
- [Efficient Learning in Polyhedral Games via Best Response Oracles](https://mlsanity.com/paper/2312.03696/) (2023)
- [The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control](https://mlsanity.com/paper/2407.11760/) (2024)
- [On the von Neumann and Frank-Wolfe Algorithms with Away Steps](https://mlsanity.com/paper/1507.04073/) (2015)
- [Affine invariant convergence rates of the conditional gradient method](https://mlsanity.com/paper/2112.06727/) (2021)
- [Accelerated Affine-Invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-Loop Step-Sizes](https://mlsanity.com/paper/2310.04096/) (2023)
- [Infeasibility and error bound imply finite convergence of alternating projections](https://mlsanity.com/paper/2008.03354/) (2020)
- [A Note on the Finite Convergence of Alternating Projections](https://mlsanity.com/paper/2008.06314/) (2020)
- [The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes](https://mlsanity.com/paper/2009.12685/) (2020)
- [Acceleration of Frank-Wolfe Algorithms with Open-Loop Step-Sizes](https://mlsanity.com/paper/2205.12838/) (2022)
- [Alternating Linear Minimization: Revisiting von Neumann's alternating projections](https://mlsanity.com/paper/2212.02933/) (2022)
- [Projection free methods on product domains](https://mlsanity.com/paper/2302.04839/) (2023)
- [Fast convergence of Frank-Wolfe algorithms on polytopes](https://mlsanity.com/paper/2406.18789/) (2024)

## Abstract (arXiv)

We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the pyramidal width and the vertex-facet distance, based on the condition numbers of individual polytope components. As a result, for convex objectives that are μ-Polyak-Lojasiewicz, we show linear convergence rates quantified in terms of the resulting condition numbers. We apply our results to the problem of approximately finding a feasible point in a polytope intersection in high-dimensions, and demonstrate the practical efficiency of our algorithms through empirical results.