mlsanityData to 14 Oct 2026

SP2: A Second Order Stochastic Polyak Method

arXiv 2207.08171 ↗First posted 17 Jul 2022cs.LG math.OCcited by 13

Not on the map. Why?

Abstract (arXiv)

Recently the "SP" (Stochastic Polyak step size) method has emerged as a competitive adaptive method for setting the step sizes of SGD. SP can be interpreted as a method specialized to interpolated models, since it solves the interpolation equations. SP solves these equation by using local linearizations of the model. We take a step further and develop a method for solving the interpolation equations that uses the local second-order approximation of the model. Our resulting method SP2 uses Hessian-vector products to speed-up the convergence of SP. Furthermore, and rather uniquely among second-order methods, the design of SP2 in no way relies on positive definite Hessian matrices or convexity of the objective function. We show SP2 is very competitive on matrix completion, non-convex test problems and logistic regression. We also provide a convergence theory on sums-of-quadratics.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 17 Jul 2022.

Builds on

26 of 39 references.

References · 26

  1. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  2. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  3. 2013A Literature Survey of Benchmark Functions For Global Optimization Problemscited by 77
  4. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  5. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  6. 2017Sub-sampled Cubic Regularization for Non-convex Optimizationcited by 63
  7. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  8. 2019Training Neural Networks for and by Interpolationcited by 45
  9. 2015A Linearly-Convergent Stochastic L-BFGS Algorithmcited by 39
  10. 2016Exact and Inexact Subsampled Newton Methods for Optimizationcited by 38
  11. 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
  12. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
14 more
  1. 2015Convergence rates of sub-sampled Newton methodscited by 33
  2. 2016A Multi-Batch L-BFGS Method for Machine Learningcited by 31
  3. 2016Stochastic Block BFGS: Squeezing More Curvature out of Datacited by 24
  4. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
  5. 2015SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimizationcited by 19
  6. 2021Stochastic Polyak Stepsize with a Moving Targetcited by 19
  7. 2014Global Convergence of Online Limited Memory BFGScited by 18
  8. 2022Cutting Some Slack for SGD with Adaptive Polyak Stepsizescited by 18
  9. 2017General Heuristics for Nonconvex Quadratically Constrained Quadratic Programmingcited by 17
  10. 2016Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descentcited by 15
  11. 2017IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Ratecited by 11
  12. 2021SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sumscited by 5
  13. 2019Convergence of Newton-MR under Inexact Hessian Informationcited by 3
  14. 2014Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 3; 2025: 0; 2026: 3.

13 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. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  4. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  5. 2022Adaptive Learning Rates for Faster Stochastic Gradient Methodscited by 7
  6. 2023Stochastic Gradient Descent with Preconditioned Polyak Step-sizecited by 7
  7. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
  8. 2023On the Interplay Between Stepsize Tuning and Progressive Sharpeningcited by 4
  9. 2024AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Sizecited by 3
  10. 2026Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameterscited by 2
  11. 2023Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learningcited by 0
  12. 2026Byzantine-Robust Optimization under (L0, L1)-Smoothnesscited by 0
1 more
  1. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0