Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the oracle complexity of smooth strongly convex minimization

Yoel Drori 1 Adrien Taylor 2
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
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 inaccuracy criteria. The new bounds match the known upper bounds up to a constant factor, and when the inaccuracy of a solution is measured by its distance to the solution set, the new lower bound exactly matches the upper bound obtained by the recent Information-Theoretic Exact Method, thereby establishing the exact oracle complexity for this class of problems.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Adrien Taylor <>
Submitted on : Monday, March 1, 2021 - 10:00:39 AM
Last modification on : Friday, March 5, 2021 - 3:28:57 AM

Links full text


  • HAL Id : hal-03154582, version 1
  • ARXIV : 2101.09740



Yoel Drori, Adrien Taylor. On the oracle complexity of smooth strongly convex minimization. 2021. ⟨hal-03154582⟩



Record views