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

Abstract

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 $\hat{I}\pm$-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 $\epsilon$ in fewer than $\hat{I}\text{c◯}(\sqrt{L\mathrm{diam}(S{)}^2/\epsilon })$ iterations. Our lower bound partly matches the accelerated Frank-Wolfe theory of Garber and Hazan (2015) of $O(\sqrt{L(\mathrm{diam}(S{)}^2+1/\hat{I}{\pm }^2)/\epsilon })$. Second, we consider optimization over ${\hat{I}}^2$-smooth sets, finding that in the modestly smooth regime of ${\hat{I}}^2=\hat{I}\text{c◯}(1/\sqrt{\epsilon })$, no complexity improvement for span-based LMO methods is possible against either compact convex sets or strongly convex sets.

17 pages

Topics & keywords