# Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD

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

## Key facts

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

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

- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Momentum Aggregation for Private Non-convex ERM](https://mlsanity.com/paper/2210.06328/) (2022)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times](https://mlsanity.com/paper/2101.04163/) (2021)
- [Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling](https://mlsanity.com/paper/2502.14648/) (2025)
- [Optimizing the Numbers of Queries and Replies in Federated Learning with Differential Privacy](https://mlsanity.com/paper/2107.01895/) (2021)
- [Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis](https://mlsanity.com/paper/2206.00632/) (2022)
- [AdamL: A fast adaptive gradient method incorporating loss function](https://mlsanity.com/paper/2312.15295/) (2023)
- [(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum](https://mlsanity.com/paper/2401.06738/) (2024)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [A Homogenization Approach for Gradient-Dominated Stochastic Optimization](https://mlsanity.com/paper/2308.10630/) (2023)
- [Central Limit Theorems for Stochastic Gradient Descent Quantile Estimators](https://mlsanity.com/paper/2503.02178/) (2025)
- [Explainable Learning Rate Regimes for Stochastic Optimization](https://mlsanity.com/paper/2508.13639/) (2025)
- [On the Limits of Momentum in Decentralized and Federated Optimization](https://mlsanity.com/paper/2511.20168/) (2025)

## Abstract (arXiv)

We study the convergence of Stochastic Gradient Descent (SGD) for strongly convex objective functions. We prove for all t a lower bound on the expected convergence rate after the t-th SGD iteration; the lower bound is over all possible sequences of diminishing step sizes. It implies that recently proposed sequences of step sizes at ICML 2018 and ICML 2019 are em universally close to optimal in that the expected convergence rate after em each iteration is within a factor 32 of our lower bound. This factor is independent of dimension d. We offer a framework for comparing with lower bounds in state-of-the-art literature and when applied to SGD for strongly convex objective functions our lower bound is a significant factor 775· d larger compared to existing work.