# Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2018.

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

- [CausalLM is not optimal for in-context learning](https://mlsanity.com/paper/2308.06912/) (2023)
- [A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions](https://mlsanity.com/paper/2102.09924/) (2021)
- [A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions](https://mlsanity.com/paper/2108.04620/) (2021)
- [A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2104.00277/) (2021)
- [Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2112.07369/) (2021)
- [Sharp higher order convergence rates for the Adam optimizer](https://mlsanity.com/paper/2504.19426/) (2025)
- [Statistical Guarantees for High-Dimensional Stochastic Gradient Descent](https://mlsanity.com/paper/2510.12013/) (2025)
- [Central limit theorem for the averaged Adam optimizer](https://mlsanity.com/paper/2606.21433/) (2026)
- [On the Limits of Momentum in Decentralized and Federated Optimization](https://mlsanity.com/paper/2511.20168/) (2025)
- [The Role of Target Update Frequencies in Q-Learning](https://mlsanity.com/paper/2602.03911/) (2026)
- [Convergence rates for the RMSprop optimizer with full control of the hyperparameters](https://mlsanity.com/paper/2608.30382/) (2026)

## Abstract (arXiv)

The stochastic gradient descent (SGD) optimization algorithm plays a central role in a series of machine learning applications. The scientific literature provides a vast amount of upper error bounds for the SGD method. Much less attention as been paid to proving lower error bounds for the SGD method. It is the key contribution of this paper to make a step in this direction. More precisely, in this article we establish for every γ, nu ∈ (0,∞) essentially matching lower and upper bounds for the mean square error of the SGD process with learning rates (fracγn^nu)_n ∈ mathbbN associated to a simple quadratic stochastic optimization problem. This allows us to precisely quantify the mean square convergence rate of the SGD method in dependence on the asymptotic behavior of the learning rates.