Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912928037339136 |
|---|---|
| author | Grimmer, Benjamin Liu, Ning |
| author_facet | Grimmer, Benjamin Liu, Ning |
| contents | We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smooth, strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of strongly convex constraint sets $S$, our main result proves that no such deterministic method can guarantee a final objective gap less than $\varepsilon$ in fewer than $Ω(\sqrt{L\, \mathrm{diam}(S)^2/\varepsilon})$ iterations. Our lower bound matches, up to constants, the accelerated Frank-Wolfe theory of Garber and Hazan (2015). Together, these establish this as the optimal complexity for deterministic LMO methods over strongly convex constraint sets. Second, we consider optimization over $β$-smooth sets, finding that in the modestly smooth regime of $β=Ω(1/\sqrt{\varepsilon})$, no complexity improvement for span-based LMO methods is possible against either compact convex sets or strongly convex sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22608 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets Grimmer, Benjamin Liu, Ning Optimization and Control We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smooth, strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of strongly convex constraint sets $S$, our main result proves that no such deterministic method can guarantee a final objective gap less than $\varepsilon$ in fewer than $Ω(\sqrt{L\, \mathrm{diam}(S)^2/\varepsilon})$ iterations. Our lower bound matches, up to constants, the accelerated Frank-Wolfe theory of Garber and Hazan (2015). Together, these establish this as the optimal complexity for deterministic LMO methods over strongly convex constraint sets. Second, we consider optimization over $β$-smooth sets, finding that in the modestly smooth regime of $β=Ω(1/\sqrt{\varepsilon})$, no complexity improvement for span-based LMO methods is possible against either compact convex sets or strongly convex sets. |
| title | Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.22608 |