mlsanityData to 7 Oct 2026

Making SGD Parameter-Free

arXiv 2205.02160 ↗First posted 4 May 2022math.OC cs.LG stat.MLcited by 50

Not on the map. Why?

Abstract (arXiv)

We develop an algorithm for parameter-free stochastic convex optimization (SCO) whose rate of convergence is only a double-logarithmic factor larger than the optimal rate for the corresponding known-parameter setting. In contrast, the best previously known rates for parameter-free SCO are based on online parameter-free regret bounds, which contain unavoidable excess logarithmic terms compared to their known-parameter counterparts. Our algorithm is conceptually simple, has high-probability guarantees, and is also partially adaptive to unknown gradient norms, smoothness, and strong convexity. At the heart of our results is a novel parameter-free certificate for SGD step size choice, and a time-uniform concentration result that assumes no a-priori bounds on SGD iterates.

Key facts. Cited by 50 papers in the map (data through 7 Oct 2026). Builds on 22 of its 42 references that are in the map. First posted on arXiv 4 May 2022.

Builds on

22 of 42 references.

References · 22

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  4. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  5. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  6. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  7. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  8. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  9. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  10. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  11. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  12. 2019Revisiting the Polyak step sizecited by 55
10 more
  1. 2014Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximationscited by 46
  2. 2019Training Neural Networks for and by Interpolationcited by 45
  3. 2017Online Learning Without Prior Informationcited by 36
  4. 2014Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learningcited by 27
  5. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
  6. 2018L4: Practical loss-based stepsize adaptation for deep learningcited by 26
  7. 2019Adaptive scale-invariant online algorithms for learning linear modelscited by 19
  8. 2020Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Bettingcited by 19
  9. 2014Primal-dual subgradient methods for minimizing uniformly convex functionscited by 11
  10. 2020Statistical Adaptive Stochastic Gradient Methodscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 13; 2024: 15; 2025: 11; 2026: 9.

50 papers.

Sort:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
  2. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  3. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  4. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 41
  5. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  6. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  7. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  8. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  9. 2023Mechanic: A Learning Rate Tunercited by 20
  10. 2023Normalized Gradients for Allcited by 18
  11. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  12. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
38 more
  1. 2024Directional Smoothness and Gradient Methods: Convergence and Adaptivitycited by 15
  2. 2024Tuning-Free Stochastic Optimizationcited by 13
  3. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  4. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  5. 2024Fully Unconstrained Online Learningcited by 10
  6. 2024Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizescited by 6
  7. 2023Non-Uniform Smoothness for Gradient Descentcited by 5
  8. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
  9. 2024Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptionscited by 5
  10. 2025Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillationcited by 5
  11. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  12. 2024AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Sizecited by 3
  13. 2024Parameter-free Clipped Gradient Descent Meets Polyakcited by 3
  14. 2025DADA: Dual Averaging with Distance Adaptationcited by 3
  15. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  16. 2025LightSAM: Parameter-Agnostic Sharpness-Aware Minimizationcited by 2
  17. 2025Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimizationcited by 2
  18. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  19. 2024Towards Stability of Parameter-Free Optimizationcited by 1
  20. 2024Learning-Rate-Free Stochastic Optimization over Riemannian Manifoldscited by 1
  21. 2025AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descentcited by 1
  22. 2025Online Learning-guided Learning Rate Adaptation via Gradient Alignmentcited by 1
  23. 2025The Sample Complexity of Parameter-Free Stochastic Convex Optimizationcited by 1
  24. 2026Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimizationcited by 1
  25. 2024MCMC-driven learningcited by 0
  26. 2024State-free Reinforcement Learningcited by 0
  27. 2024Tuning-Free Coreset Markov Chain Monte Carlo via Hot DoGcited by 0
  28. 2025Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimizationcited by 0
  29. 2025Revisiting Learning Rate Controlcited by 0
  30. 2025Stochastic Adaptive Gradient Descent Without Descentcited by 0
  31. 2026Step-Size Stability in Stochastic Optimization: A Theoretical Perspectivecited by 0
  32. 2026Stochastic Auto-conditioned Fast Gradient Methods with Optimal Ratescited by 0
  33. 2026TSNN: A Non-parametric and Interpretable Framework for Traffic Time Series Forecastingcited by 0
  34. 2026Large-scale empirical tuning and comparison of default optimizers for variational inferencecited by 0
  35. 2026Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuningcited by 0
  36. 2026Clipping the Price of Adaptivity at the Tailcited by 0
  37. 2026Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Ratescited by 0
  38. 2026Parameter-Free Zeroth-Order Optimization with Ellipsoidal Samplingcited by 0