# The Complexity of Finding Stationary Points with Stochastic Gradient Descent

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

## Key facts

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

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

- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Robust Multi-Task Learning with Excess Risks](https://mlsanity.com/paper/2402.02009/) (2024)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [ADOPT: Modified Adam Can Converge with Any β2 with the Optimal Rate](https://mlsanity.com/paper/2411.02853/) (2024)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach](https://mlsanity.com/paper/2306.08553/) (2023)
- [How to escape sharp minima with random perturbations](https://mlsanity.com/paper/2305.15659/) (2023)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems](https://mlsanity.com/paper/2210.09382/) (2022)
- [Quasi-optimal Reinforcement Learning with Continuous Actions](https://mlsanity.com/paper/2301.08940/) (2023)
- [Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits](https://mlsanity.com/paper/2110.04844/) (2021)
- [Generalizing Reward Modeling for Out-of-Distribution Preference Learning](https://mlsanity.com/paper/2402.14760/) (2024)
- [Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgery](https://mlsanity.com/paper/2510.22124/) (2025)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [A simplified convergence theory for Byzantine resilient stochastic gradient descent](https://mlsanity.com/paper/2208.11879/) (2022)
- [Quantized and Asynchronous Federated Learning](https://mlsanity.com/paper/2410.00242/) (2024)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling](https://mlsanity.com/paper/2502.14648/) (2025)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis](https://mlsanity.com/paper/2206.00632/) (2022)
- [Over-the-Air Federated Averaging with Limited Power and Privacy Budgets](https://mlsanity.com/paper/2305.03547/) (2023)
- [Momentum-Based Federated Reinforcement Learning with Interaction and Communication Efficiency](https://mlsanity.com/paper/2405.17471/) (2024)

## Abstract (arXiv)

We study the iteration complexity of stochastic gradient descent (SGD) for minimizing the gradient norm of smooth, possibly nonconvex functions. We provide several results, implying that the O(ε-4) upper bound of Ghadimi and Lan~citeghadimi2013stochastic (for making the average gradient norm less than ε) cannot be improved upon, unless a combination of additional assumptions is made. Notably, this holds even if we limit ourselves to convex quadratic functions. We also show that for nonconvex functions, the feasibility of minimizing gradients with SGD is surprisingly sensitive to the choice of optimality criteria.