mlsanityData to 7 Oct 2026

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

arXiv 1909.00843 ↗First posted 2 Sep 2019cs.LG math.OC stat.MLcited by 25

Not on the map. Why?

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.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 7; 2024: 3; 2025: 1; 2026: 3.

25 papers.

Sort:

  1. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  2. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  3. 2021On the Convergence of Step Decay Step-Size for Stochastic Optimizationcited by 21
  4. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  5. 2021Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimationcited by 15
  6. 2023Faster Differentially Private Convex Optimization via Second-Order Methodscited by 13
  7. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  8. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 10
  9. 2022High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noisecited by 9
  10. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  11. 2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 8
  12. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
13 more
  1. 2021A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimizationcited by 5
  2. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  3. 2022A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environmentscited by 3
  4. 2024Understanding Model Selection For Learning In Strategic Environmentscited by 3
  5. 2023Demystifying the Myths and Legends of Nonconvex Convergence of SGDcited by 2
  6. 2024Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problemscited by 2
  7. 2025Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequencescited by 2
  8. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  9. 2022Formal guarantees for heuristic optimization algorithms used in machine learningcited by 0
  10. 2023High Probability Bounds for Stochastic Continuous Submodular Maximizationcited by 0
  11. 2023Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learningcited by 0
  12. 2026Sample Complexity of Stochastic Optimization with Integer Variablescited by 0
  13. 2026High-Probability Convergence of SGD via Batched Updatescited by 0