# On the oracle complexity of smooth strongly convex minimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2021.

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

- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Sharp higher order convergence rates for the Adam optimizer](https://mlsanity.com/paper/2504.19426/) (2025)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles](https://mlsanity.com/paper/2307.04679/) (2023)
- [Understanding Accelerated Gradient Methods: Lyapunov Analyses and Hamiltonian Assisted Interpretations](https://mlsanity.com/paper/2304.10063/) (2023)
- [Classification by Separating Hypersurfaces: An Entropic Approach](https://mlsanity.com/paper/2507.02732/) (2025)
- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)

## Abstract (arXiv)

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 by the same authors, thereby establishing the exact oracle complexity for this class of problems.