# Frank-Wolfe Beyond 1/t Convergence

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

## Key facts

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

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

- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

We consider smooth convex minimization over compact convex sets, i.e., minx ∈ C f(x) with the (vanilla) Frank-Wolfe algorithm. Well-known lower bounds establish a worst-case Omega(1/t) primal-gap barrier in the general smooth convex case, and faster convergence usually requires favorable function properties such as H"older error bounds or strong convexity. We present a new Local Dual Sharpness (LDS) condition, essentially a property of the feasible region and its LMO, under which the Frank-Wolfe algorithm converges in o(1/t) for any smooth convex function, ruling out an Omega(1/t) lower bound under LDS. The condition is a generalization (and localization) of uniform convexity of sets and it is satisfied by any uniformly convex set. To our knowledge, this is the first unconditional o(1/t) convergence result for uniformly convex sets. Combining LDS with stronger function properties, e.g., a local variant of H"older error bounds, allows us to quantify the actual rates.