Frank-Wolfe Beyond 1/t Convergence
A local dual sharpness condition enables Frank-Wolfe to converge faster than 1/t on uniformly convex sets, bypassing standard lower bounds.
Published 2026Paris Poster Session 1 · Wed, Dec 9, 12:30 PM–2:30 PM local time · Paris Poster HallarXiv ↗OpenReview ↗
Only vote on papers you've read. Sign in with GitHub to vote.
The local dual sharpness condition elegantly kills the 1/t barrier through feasible-set geometry alone, though critics stress it lacks empirical LMO benchmarks, dataset counts, and practical verification for real-world feasible sets.
Abstract
We consider smooth convex minimization over compact convex sets, i.e., $\min_{x \in C} f(x)$ with the (vanilla) Frank-Wolfe algorithm. Well-known lower bounds establish a worst-case $Ω(1/t)$ primal-gap barrier in the general smooth convex case, and faster convergence usually requires favorable function properties such as Hölder 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 $Ω(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ölder error bounds, allows us to quantify the actual rates.