# Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

arXiv: https://arxiv.org/abs/2602.22608 · HTML: https://mlsanity.com/paper/2602.22608/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2026.

## Built on by (most cited first, 4 of 4)

- [The Agentic Researcher: A Practical Guide to AI-Assisted Research in Mathematics and Machine Learning](https://mlsanity.com/paper/2603.15914/) (2026)
- [Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent](https://mlsanity.com/paper/2605.08850/) (2026)
- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)
- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

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, L-strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of α-strongly convex constraint sets S, we demonstrate that one can construct hard ``zero-chain'' instances in the classical style of Nemirovski and Yudin. From our new approach to adversarial oracle construction, we prove that no such deterministic method can guarantee a final objective gap less than varepsilon in fewer than Omega(√L, diam(S)2/varepsilon) iterations. Our lower bound partly matches the accelerated Frank-Wolfe theory of Garber and Hazan (2015) of O(√L(diam(S)2+1/α2)/varepsilon). Second, we consider optimization over β-smooth sets, finding that in the modestly smooth regime of β=Omega(1/√varepsilon), no complexity improvement for span-based LMO methods is possible against either compact convex sets or strongly convex sets.