HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 - ENS Paris, 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 Connect in order to contact the contributor
Submitted on : Monday, March 1, 2021 - 10:00:39 AM
Last modification on : Thursday, March 17, 2022 - 10:08:54 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