mlsanityData to 14 Oct 2026

Stochastic Polyak Stepsize with a Moving Target

arXiv 2106.11851 ↗First posted 22 Jun 2021cs.LG math.OCcited by 19

Not on the map. Why?

Abstract (arXiv)

We propose a new stochastic gradient method called MOTAPS (Moving Targetted Polyak Stepsize) that uses recorded past loss values to compute adaptive stepsizes. MOTAPS can be seen as a variant of the Stochastic Polyak (SP) which is also a method that also uses loss values to adjust the stepsize. The downside to the SP method is that it only converges when the interpolation condition holds. MOTAPS is an extension of SP that does not rely on the interpolation condition. The MOTAPS method uses n auxiliary variables, one for each data point, that track the loss value for each data point. We provide a global convergence theory for SP, an intermediary method TAPS, and MOTAPS by showing that they all can be interpreted as a special variant of online SGD. We also perform several numerical experiments on convex learning problems, and deep learning models for image classification and language translation. In all of our tasks we show that MOTAPS is competitive with the relevant baseline method.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 26 of its 46 references that are in the map. First posted on arXiv 22 Jun 2021.

Builds on

26 of 46 references.

References · 26

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Identity Mappings in Deep Residual Networkscited by 1,965
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  4. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  5. 2019SGD: General Analysis and Improved Ratescited by 207
  6. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  7. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  8. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  9. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  10. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  11. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  12. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
14 more
  1. 2016Gradient Descent Learns Linear Dynamical Systemscited by 79
  2. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  3. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  4. 2019Training Neural Networks for and by Interpolationcited by 45
  5. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  6. 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
  7. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
  8. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  9. 2020Sketched Newton-Raphsoncited by 14
  10. 2013Semi-Stochastic Gradient Descent Methodscited by 13
  11. 2019Stochastic Gradient Descent with Polyak's Learning Ratecited by 11
  12. 2015Optimizing Star-Convex Functionscited by 9
  13. 2016SDCA without Duality, Regularization, and Individual Convexitycited by 4
  14. 2021Comment on Stochastic Polyak Step-Size: Performance of ALI-Gcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 4; 2025: 3; 2026: 1.

19 papers.

Sort:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 133
  2. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  3. 2022Cutting Some Slack for SGD with Adaptive Polyak Stepsizescited by 18
  4. 2023Variational Inference with Gaussian Score Matchingcited by 17
  5. 2023Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Modelscited by 15
  6. 2022SP2: A Second Order Stochastic Polyak Methodcited by 13
  7. 2023Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERMcited by 8
  8. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  9. 2022Adaptive Learning Rates for Faster Stochastic Gradient Methodscited by 7
  10. 2023Locally Adaptive Federated Learningcited by 7
  11. 2025New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Resultscited by 6
  12. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
7 more
  1. 2024AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Sizecited by 3
  2. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  3. 2025Aligned Multi Objective Optimizationcited by 3
  4. 2024Towards Simple and Provable Parameter-Free Adaptive Gradient Methodscited by 2
  5. 2025Gradient Methods with Online Scaling Part II. Practical Aspectscited by 1
  6. 2023Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learningcited by 0
  7. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0