# New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 44 references that are in the map.
- First posted on arXiv 26 May 2025.

## Builds on (most cited first, 24 of 24)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution](https://mlsanity.com/paper/2205.04583/) (2022)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [L4: Practical loss-based stepsize adaptation for deep learning](https://mlsanity.com/paper/1802.05074/) (2018)
- [Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity](https://mlsanity.com/paper/2409.14989/) (2024)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [Generalized Polyak Step Size for First Order Optimization with Momentum](https://mlsanity.com/paper/2305.12939/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Stochastic Gradient Descent with Polyak's Learning Rate](https://mlsanity.com/paper/1903.08688/) (2019)
- [A Study of Condition Numbers for First-Order Optimization](https://mlsanity.com/paper/2012.05782/) (2020)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [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)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Optimal first-order methods for convex functions with a quadratic upper bound](https://mlsanity.com/paper/2205.15033/) (2022)
- [Parameter-free Clipped Gradient Descent Meets Polyak](https://mlsanity.com/paper/2405.15010/) (2024)

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

- [Reinforced Generation of Combinatorial Structures: Hardness of Approximation](https://mlsanity.com/paper/2509.18057/) (2025)
- [Where Does Warm-Up Come From? Adaptive Scheduling for Norm-Constrained Optimizers](https://mlsanity.com/paper/2602.05813/) (2026)
- [Taking the Road Less Scheduled with Adaptive Polyak Steps](https://mlsanity.com/paper/2511.07767/) (2025)
- [Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients](https://mlsanity.com/paper/2512.02342/) (2025)
- [Step-Size Stability in Stochastic Optimization: A Theoretical Perspective](https://mlsanity.com/paper/2602.09842/) (2026)
- [Local LMO is Secretly a Projection Method!](https://mlsanity.com/paper/2609.33383/) (2026)

## Abstract (arXiv)

The Polyak stepsize has been proven to be a fundamental stepsize in convex optimization, giving near optimal gradient descent rates across a wide range of assumptions. The universality of the Polyak stepsize has also inspired many stochastic variants, with theoretical guarantees and strong empirical performance. Despite the many theoretical results, our understanding of the convergence properties and shortcomings of the Polyak stepsize or its variants is both incomplete and fractured across different analyses. We propose a new, unified, and simple perspective for the Polyak stepsize and its variants as gradient descent on a surrogate loss. We show that each variant is equivalent to minimize a surrogate function with stepsizes that adapt to a guaranteed local curvature. Our general surrogate loss perspective is then used to provide a unified analysis of existing variants across different assumptions. Moreover, we show a number of negative results proving that the non-convergence results in some of the upper bounds is indeed real.