# Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent

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

## Key facts

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

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

- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation](https://mlsanity.com/paper/2110.11271/) (2021)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise](https://mlsanity.com/paper/2208.08567/) (2022)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization](https://mlsanity.com/paper/2110.07098/) (2021)
- [Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise](https://mlsanity.com/paper/2605.20999/) (2026)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences](https://mlsanity.com/paper/2512.13123/) (2025)
- [A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments](https://mlsanity.com/paper/2209.10866/) (2022)
- [Understanding Model Selection For Learning In Strategic Environments](https://mlsanity.com/paper/2402.07588/) (2024)
- [Demystifying the Myths and Legends of Nonconvex Convergence of SGD](https://mlsanity.com/paper/2310.12969/) (2023)
- [Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems](https://mlsanity.com/paper/2401.15890/) (2024)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules](https://mlsanity.com/paper/2608.25551/) (2026)
- [Formal guarantees for heuristic optimization algorithms used in machine learning](https://mlsanity.com/paper/2208.00502/) (2022)
- [High Probability Bounds for Stochastic Continuous Submodular Maximization](https://mlsanity.com/paper/2303.11937/) (2023)
- [Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learning](https://mlsanity.com/paper/2305.00254/) (2023)
- [Sample Complexity of Stochastic Optimization with Integer Variables](https://mlsanity.com/paper/2605.07239/) (2026)
- [High-Probability Convergence of SGD via Batched Updates](https://mlsanity.com/paper/2609.12765/) (2026)

## Abstract (arXiv)

We consider stochastic gradient descent algorithms for minimizing a non-smooth, strongly-convex function. Several forms of this algorithm, including suffix averaging, are known to achieve the optimal O(1/T) convergence rate in expectation. We consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. (2011) and prove that it achieves the optimal O(1/T) convergence rate with high probability. Our proof uses a recently developed generalization of Freedman's inequality. Finally, we compare several of these algorithms experimentally and show that this non-uniform averaging strategy outperforms many standard techniques, and with smaller variance.