mlsanityData to 7 Oct 2026

Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation

arXiv 2504.01898 ↗First posted 2 Apr 2025cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We provide a general convergence theorem of an idealized stochastic Polyak step size called SPS^*. Besides convexity, we only assume a local expected gradient bound, that includes locally smooth and locally Lipschitz losses as special cases. We refer to SPS^* as idealized because it requires access to the loss for every training batch evaluated at a solution. It is also ideal, in that it achieves the optimal lower bound for globally Lipschitz function, and is the first Polyak step size to have an O(1/√t) anytime convergence in the smooth setting. We show how to combine SPS^* with momentum to achieve the same favorable rates for the last iterate. We conclude with several experiments to validate our theory, and a more practical setting showing how we can distill a teacher GPT-2 model into a smaller student model without any hyperparameter tuning.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 45 of its 68 references that are in the map. First posted on arXiv 2 Apr 2025.

Builds on

45 of 68 references.

References · 45

  1. 2015Distilling the Knowledge in a Neural Networkcited by 10,076
  2. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  3. 2014FitNets: Hints for Thin Deep Netscited by 1,619
  4. 2023Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizescited by 710
  5. 2021Knowledge distillation: A good teacher is patient and consistentcited by 255
  6. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  7. 2019SGD: General Analysis and Improved Ratescited by 206
  8. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  9. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  10. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  11. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  12. 2016Coin Betting and Parameter-Free Online Learningcited by 131
33 more
  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
  2. 2020Descending through a Crowded Valley - Benchmarking Deep Learning Optimizerscited by 118
  3. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  4. 2024The rising costs of training frontier AI modelscited by 91
  5. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  6. 2019Adaptive Gradient Descent without Descentcited by 79
  7. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  8. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  9. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  10. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  11. 2019Revisiting the Polyak step sizecited by 55
  12. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  13. 2022Making SGD Parameter-Freecited by 50
  14. 2019Training Neural Networks for and by Interpolationcited by 45
  15. 2022Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solutioncited by 40
  16. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  17. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  18. 2023MoMo: Momentum Models for Adaptive Learning Ratescited by 24
  19. 2023Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradientcited by 19
  20. 2022Cutting Some Slack for SGD with Adaptive Polyak Stepsizescited by 18
  21. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  22. 2022Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensionscited by 15
  23. 2023A Stochastic Proximal Polyak Step Sizecited by 15
  24. 2023Generalized Polyak Step Size for First Order Optimization with Momentumcited by 15
  25. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  26. 2022On the fast convergence of minibatch heavy ball momentumcited by 11
  27. 2024An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizescited by 10
  28. 2020The Power of Factorial Powers: New Parameter settings for (Stochastic) Optimizationcited by 8
  29. 2023Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERMcited by 8
  30. 2020Complexity Guarantees for Polyak Steps with Momentumcited by 7
  31. 2024Universal Gradient Methods for Stochastic Convex Optimizationcited by 4
  32. 2014An optimal variant of Kelley's cutting-plane methodcited by 2
  33. 2024Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descentcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Resultscited by 6
  2. 2025Taking the Road Less Scheduled with Adaptive Polyak Stepscited by 2
  3. 2025Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradientscited by 2
  4. 2026Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Schedulercited by 1
  5. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0