# Accelerated Affine-Invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-Loop Step-Sizes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2023.

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

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

## Abstract (arXiv)

Recent papers have shown that the Frank-Wolfe algorithm (FW) with open-loop step-sizes exhibits rates of convergence faster than the iconic O(t-1) rate. In particular, when the minimizer of a strongly convex function over a polytope lies in the relative interior of a feasible region face, the FW with open-loop step-sizes ηt = fracℓt+ℓ for ℓ ∈ mathbbN≥ 2 has accelerated convergence O(t-2) in contrast to the rate Omega(t-1-ε) attainable with more complex line-search or short-step step-sizes. Given the relevance of this scenario in data science problems, research has grown to explore the settings enabling acceleration in open-loop FW. However, despite FW's well-known affine invariance, existing acceleration results for open-loop FW are affine-dependent. This paper remedies this gap in the literature by merging two recent research trajectories: affine invariance (Wirth et al., 2023b) and open-loop step-sizes (Pena, 2021). In particular, we extend all known non-affine-invariant convergence rates for FW with open-loop step-sizes to affine-invariant results.