# SP2: A Second Order Stochastic Polyak Method

arXiv: https://arxiv.org/abs/2207.08171 · HTML: https://mlsanity.com/paper/2207.08171/

## 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 (most cited first, 26 of 26)

- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [A Literature Survey of Benchmark Functions For Global Optimization Problems](https://mlsanity.com/paper/1308.4008/) (2013)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [A Multi-Batch L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1605.06049/) (2016)
- [Stochastic Block BFGS: Squeezing More Curvature out of Data](https://mlsanity.com/paper/1603.09649/) (2016)
- [Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates](https://mlsanity.com/paper/1912.01597/) (2019)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [Global Convergence of Online Limited Memory BFGS](https://mlsanity.com/paper/1409.2045/) (2014)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming](https://mlsanity.com/paper/1703.07870/) (2017)
- [Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent](https://mlsanity.com/paper/1605.08370/) (2016)
- [IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1702.00709/) (2017)
- [SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums](https://mlsanity.com/paper/2106.10520/) (2021)
- [Convergence of Newton-MR under Inexact Hessian Information](https://mlsanity.com/paper/1909.06224/) (2019)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1412.1196/) (2014)

## Built on by (most cited first, 13 of 13)

- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad](https://mlsanity.com/paper/2403.02648/) (2024)
- [Adaptive Learning Rates for Faster Stochastic Gradient Methods](https://mlsanity.com/paper/2208.05287/) (2022)
- [Stochastic Gradient Descent with Preconditioned Polyak Step-size](https://mlsanity.com/paper/2310.02093/) (2023)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [On the Interplay Between Stepsize Tuning and Progressive Sharpening](https://mlsanity.com/paper/2312.00209/) (2023)
- [AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size](https://mlsanity.com/paper/2402.05264/) (2024)
- [Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameters](https://mlsanity.com/paper/2605.11838/) (2026)
- [Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learning](https://mlsanity.com/paper/2305.13664/) (2023)
- [Byzantine-Robust Optimization under (L0, L1)-Smoothness](https://mlsanity.com/paper/2603.12512/) (2026)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)

## 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.