# The Complexity of Making the Gradient Small in Stochastic Convex Optimization

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2019.

## Built on by (most cited first, 30 of 34)

- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Reproducibility in Optimization: Theoretical Framework and Limits](https://mlsanity.com/paper/2202.04598/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [On the Sample Complexity of Quantum Boltzmann Machine Learning](https://mlsanity.com/paper/2306.14969/) (2023)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance](https://mlsanity.com/paper/2404.01436/) (2024)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Regression under demographic parity constraints via unlabeled post-processing](https://mlsanity.com/paper/2407.15453/) (2024)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [Optimal Downsampling for Imbalanced Classification with Generalized Linear Models](https://mlsanity.com/paper/2410.08994/) (2024)
- [Stochastic Optimization with Optimal Importance Sampling](https://mlsanity.com/paper/2504.03560/) (2025)
- [Finding a stationary point of a stochastic convex problem](https://mlsanity.com/paper/2607.06883/) (2026)
- [Efficient Public Verification of Private ML via Regularization](https://mlsanity.com/paper/2512.04008/) (2025)
- [Randomized multi-class classification under system constraints: a unified approach via post-processing](https://mlsanity.com/paper/2512.14246/) (2025)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)

## Abstract (arXiv)

We give nearly matching upper and lower bounds on the oracle complexity of finding ε-stationary points (| nabla F(x) | ≤ε) in stochastic convex optimization. We jointly analyze the oracle complexity in both the local stochastic oracle model and the global oracle (or, statistical learning) model. This allows us to decompose the complexity of finding near-stationary points into optimization complexity and sample complexity, and reveals some surprising differences between the complexity of stochastic optimization versus learning. Notably, we show that in the global oracle/statistical learning model, only logarithmic dependence on smoothness is required to find a near-stationary point, whereas polynomial dependence on smoothness is necessary in the local stochastic oracle model. In other words, the separation in complexity between the two models can be exponential, and that the folklore understanding that smoothness is required to find stationary points is only weakly true for statistical learning. Our upper bounds are based on extensions of a recent "recursive regularization" technique proposed by Allen-Zhu (2018). We show how to extend the technique to achieve near-optimal rates, and in particular show how to leverage the extra information available in the global oracle model. Our algorithm for the global model can be implemented efficiently through finite sum methods, and suggests an interesting new computational-statistical tradeoff.