Recursive domain- and objective-adaptive Frank-Wolfe algorithm with convergence guarantees where optimization error scales with estimator accuracy and experiments show comparable performance with computational savings.
Frank-Wolfe Beyond 1/t Convergence
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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 $\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.
fields
math.OC 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A Recursive Domain- and Objective-Adaptive Frank-Wolfe Algorithm
Recursive domain- and objective-adaptive Frank-Wolfe algorithm with convergence guarantees where optimization error scales with estimator accuracy and experiments show comparable performance with computational savings.