# How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2018.

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

- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Rethinking Semi-Supervised Medical Image Segmentation: A Variance-Reduction Perspective](https://mlsanity.com/paper/2302.01735/) (2023)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [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)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator](https://mlsanity.com/paper/2104.14840/) (2021)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [On the Complexity of Finding Small Subgradients in Nonsmooth Optimization](https://mlsanity.com/paper/2209.10346/) (2022)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [Regression under demographic parity constraints via unlabeled post-processing](https://mlsanity.com/paper/2407.15453/) (2024)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)

## Abstract (arXiv)

Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives f(x). However, in terms of making the gradients small, the original SGD does not give an optimal rate, even when f(x) is convex. If f(x) is convex, to find a point with gradient norm varepsilon, we design an algorithm SGD3 with a near-optimal rate tildeO(varepsilon-2), improving the best known rate O(varepsilon-8/3) of [18]. If f(x) is nonconvex, to find its varepsilon-approximate local minimum, we design an algorithm SGD5 with rate tildeO(varepsilon-3.5), where previously SGD variants only achieve tildeO(varepsilon-4) [6, 15, 33]. This is no slower than the best known stochastic version of Newton's method in all parameter regimes [30].