mlsanityData to 7 Oct 2026

Cutting Some Slack for SGD with Adaptive Polyak Stepsizes

arXiv 2202.12328 ↗First posted 24 Feb 2022cs.LG math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

Tuning the step size of stochastic gradient descent is tedious and error prone. This has motivated the development of methods that automatically adapt the step size using readily available information. In this paper, we consider the family of SPS (Stochastic gradient with a Polyak Stepsize) adaptive methods. These are methods that make use of gradient and loss value at the sampled points to adaptively adjust the step size. We first show that SPS and its recent variants can all be seen as extensions of the Passive-Aggressive methods applied to nonlinear problems. We use this insight to develop new variants of the SPS method that are better suited to nonlinear models. Our new variants are based on introducing a slack variable into the interpolation equations. This single slack variable tracks the loss function across iterations and is used in setting a stable step size. We provide extensive numerical results supporting our new methods and a convergence theory.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 20 of its 37 references that are in the map. First posted on arXiv 24 Feb 2022.

Builds on

20 of 37 references.

References · 20

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  4. 2019On the Convergence of Adam and Beyondcited by 834
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  6. 2019SGD: General Analysis and Improved Ratescited by 206
  7. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  8. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  9. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  10. 2017Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradientscited by 136
  11. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  12. 2018Does data interpolation contradict statistical optimality?cited by 95
8 more
  1. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  2. 2019Training Neural Networks for and by Interpolationcited by 45
  3. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  4. 2019The importance of better models in stochastic optimizationcited by 32
  5. 2021Stochastic Polyak Stepsize with a Moving Targetcited by 19
  6. 2021Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimizationcited by 14
  7. 2020Sketched Newton-Raphsoncited by 13
  8. 2021Comment on Stochastic Polyak Step-Size: Performance of ALI-Gcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 10; 2024: 1; 2025: 3; 2026: 2.

18 papers.

Sort:

  1. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  2. 2023Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Modelscited by 15
  3. 2022SP2: A Second Order Stochastic Polyak Methodcited by 13
  4. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  5. 2023Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERMcited by 8
  6. 2022Adaptive Learning Rates for Faster Stochastic Gradient Methodscited by 7
  7. 2023Locally Adaptive Federated Learningcited by 7
  8. 2023Stochastic Gradient Descent with Preconditioned Polyak Step-sizecited by 7
  9. 2023A Model-Based Method for Minimizing CVaR and Beyondcited by 5
  10. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
  11. 2025Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillationcited by 5
  12. 2023On the Interplay Between Stepsize Tuning and Progressive Sharpeningcited by 4
6 more
  1. 2025Taking the Road Less Scheduled with Adaptive Polyak Stepscited by 2
  2. 2025Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradientscited by 2
  3. 2026Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Schedulercited by 1
  4. 2023Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learningcited by 0
  5. 2023Dual Gauss-Newton Directions for Deep Learningcited by 0
  6. 2026Step-Size Stability in Stochastic Optimization: A Theoretical Perspectivecited by 0