Curvature-Dependent Lower Bounds for Frank–Wolfe

Jannis Halbey, Christophe Roux, Sebastian Pokutta · 2026

Read Curvature-Dependent Lower Bounds for Frank–Wolfe by Jannis Halbey, Christophe Roux, Sebastian Pokutta (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10595.txt.

Description

Jannis Halbey and two colleagues establish curvature lower bounds for Frank-Wolfe. Frank-Wolfe achieves a convergence rate of order 1 over T for convex optimization over compact convex domains. That rate accelerates to order 1 over T squared when objective and feasible set are both strongly convex. Their 2026 paper establishes a lower bound of order T to the power minus p over p minus 1 for p at least 3. The bound holds under line search or short steps.

Prior work proved rates of that order over p-uniformly convex feasible sets, extending acceleration beyond strong convexity. Such sets interpolate between strongly convex sets and curved domains such as Lp balls. The authors stretch the lower bound to cover objectives satisfying a Hölderian error bound. The proofs analyze Frank-Wolfe iterates on instances. Hence they apply beyond the high-dimensional setting.

Catalog record

CREATORJannis Halbey, Christophe Roux, Sebastian Pokutta
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10595

Browse the full library · About the Tower of Babel