On the oracle complexity of smooth strongly convex minimization

Adrien B. Taylor
Journal of Complexity, 68 (2021), pp. 101590 (to appear)

Abstract

We construct a family of functions suitable for establishing lower bounds on the oracle complexity of first-order minimization of smooth strongly-convex functions.
Based on this construction, we derive new lower bounds on the complexity of strongly-convex minimization under various accuracy criteria. The new bounds match the known upper bounds up to a constant factor, and when the accuracy of a solution is measured by its distance to the solution set, the new lower bound \emph{exactly} matches the upper bound attained by the recent Doubly Optimal Method, thereby establishing the exact complexity for this class of problems.