Frank-Wolfe Beyond 1/t Convergence

We consider smooth convex minimization over compact convex sets, i.e., ${\min }_{x\in \mathcal{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ö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 $\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ölder error bounds, allows us to quantify the actual rates.