Curvature-Dependent Lower Bounds for Frank-Wolfe
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918508868141056 |
|---|---|
| author | Halbey, Jannis Roux, Christophe Pokutta, Sebastian |
| author_facet | Halbey, Jannis Roux, Christophe Pokutta, Sebastian |
| contents | The Frank-Wolfe algorithm achieves a convergence rate of $\mathcal{O}(1/T)$ for smooth convex optimization over compact convex domains, accelerating to $\mathcal{O}(1/T^2)$ when both the objective and the feasible set are strongly convex. This acceleration extends beyond strong convexity: Kerdreux et al. (2021a) proved rates of $\mathcal{O}(T^{-p/(p-1)})$ over $p$-uniformly convex feasible sets, a class that interpolates between strongly convex sets and more general curved domains such as $\ell_p$ balls. In this work, we establish a matching $Ω(T^{-p/(p-1)})$ lower bound for every $p\ge 3$ under exact line search or short steps, and extend the lower bound to objectives satisfying a Hölderian error bound. The proofs analyze the dynamics of Frank-Wolfe iterates on simple instances and hence are not limited to the high-dimensional setting, unlike information-theoretic lower bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10595 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Curvature-Dependent Lower Bounds for Frank-Wolfe Halbey, Jannis Roux, Christophe Pokutta, Sebastian Optimization and Control The Frank-Wolfe algorithm achieves a convergence rate of $\mathcal{O}(1/T)$ for smooth convex optimization over compact convex domains, accelerating to $\mathcal{O}(1/T^2)$ when both the objective and the feasible set are strongly convex. This acceleration extends beyond strong convexity: Kerdreux et al. (2021a) proved rates of $\mathcal{O}(T^{-p/(p-1)})$ over $p$-uniformly convex feasible sets, a class that interpolates between strongly convex sets and more general curved domains such as $\ell_p$ balls. In this work, we establish a matching $Ω(T^{-p/(p-1)})$ lower bound for every $p\ge 3$ under exact line search or short steps, and extend the lower bound to objectives satisfying a Hölderian error bound. The proofs analyze the dynamics of Frank-Wolfe iterates on simple instances and hence are not limited to the high-dimensional setting, unlike information-theoretic lower bounds. |
| title | Curvature-Dependent Lower Bounds for Frank-Wolfe |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.10595 |