# Beyond Short Steps in Frank-Wolfe Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2025.

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

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [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)
- [Local LMO is Secretly a Projection Method!](https://mlsanity.com/paper/2609.33383/) (2026)

## Abstract (arXiv)

We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank-Wolfe algorithms with step sizes that incorporate primal-dual guarantees, offering practical stopping criteria. We present a new Frank-Wolfe algorithm utilizing an optimistic framework and provide a primal-dual convergence proof. Additionally, we propose a generalized short-step strategy aimed at optimizing a computable primal-dual gap. Interestingly, this new generalized short-step strategy is also applicable to gradient descent algorithms beyond Frank-Wolfe methods. As a byproduct, our work revisits and refines primal-dual techniques for analyzing Frank-Wolfe algorithms, achieving tighter primal-dual convergence rates. Empirical results demonstrate that our optimistic algorithm outperforms existing methods, highlighting its practical advantages.