# Handbook of Convergence Theorems for (Stochastic) Gradient Methods

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

## Key facts

- Cited by 163 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2023.

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

- [ASGO: Adaptive Structured Gradient Optimization](https://mlsanity.com/paper/2503.20762/) (2025)
- [Provable convergence guarantees for black-box variational inference](https://mlsanity.com/paper/2306.03638/) (2023)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)
- [SteinDreamer: Variance Reduction for Text-to-3D Score Distillation via Stein Identity](https://mlsanity.com/paper/2401.00604/) (2023)
- [Super Consistency of Neural Network Landscapes and Learning Rate Transfer](https://mlsanity.com/paper/2402.17457/) (2024)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [On the Convergence of Black-Box Variational Inference](https://mlsanity.com/paper/2305.15349/) (2023)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [Batch and match: black-box variational inference with a score-based divergence](https://mlsanity.com/paper/2402.14758/) (2024)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent](https://mlsanity.com/paper/2410.11268/) (2024)
- [On the Sample Complexity of Quantum Boltzmann Machine Learning](https://mlsanity.com/paper/2306.14969/) (2023)
- [Attribute-to-Delete: Machine Unlearning via Datamodel Matching](https://mlsanity.com/paper/2410.23232/) (2024)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Plastic Learning with Deep Fourier Features](https://mlsanity.com/paper/2410.20634/) (2024)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [On the Complexity of First-Order Methods in Stochastic Bilevel Optimization](https://mlsanity.com/paper/2402.07101/) (2024)
- [HTMuon: Improving Muon via Heavy-Tailed Spectral Correction](https://mlsanity.com/paper/2603.10067/) (2026)
- [Knowledge Distillation Performs Partial Variance Reduction](https://mlsanity.com/paper/2305.17581/) (2023)
- [Theoretical Guarantees for Variational Inference with Fixed-Variance Mixture of Gaussians](https://mlsanity.com/paper/2406.04012/) (2024)
- [Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent](https://mlsanity.com/paper/2409.08770/) (2024)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Uncertainty Quantification with the Empirical Neural Tangent Kernel](https://mlsanity.com/paper/2502.02870/) (2025)
- [Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?](https://mlsanity.com/paper/2307.14642/) (2023)
- [An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes](https://mlsanity.com/paper/2407.04358/) (2024)
- [On the Convergence Rate of LoRA Gradient Descent](https://mlsanity.com/paper/2512.18248/) (2025)
- [Deriving Hyperparameter Scaling Laws via Modern Optimization Theory](https://mlsanity.com/paper/2603.15958/) (2026)

## Abstract (arXiv)

This is a handbook of simple proofs of the convergence of gradient and stochastic gradient descent type methods. We consider functions that are Lipschitz, smooth, convex, strongly convex, and/or Polyak-Lojasiewicz functions. Our focus is on ``good proofs'' that are also simple. Each section can be consulted separately. We start with proofs of gradient descent, then on stochastic variants, including minibatching and momentum. Then move on to nonsmooth problems with the subgradient method, the proximal gradient descent and their stochastic variants. Our focus is on global convergence rates and complexity rates. Some slightly less common proofs found here include that of SGD (Stochastic gradient descent) with a proximal step, with momentum, and with mini-batching without replacement.