# Stochastic Gradient Descent with Polyak's Learning Rate

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

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

- [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)
- [A Stochastic Proximal Polyak Step Size](https://mlsanity.com/paper/2301.04935/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes](https://mlsanity.com/paper/2407.04358/) (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)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)

## Abstract (arXiv)

Stochastic gradient descent (SGD) for strongly convex functions converges at the rate bO(1/k). However, achieving good results in practice requires tuning the parameters (for example the learning rate) of the algorithm. In this paper we propose a generalization of the Polyak step size, used for subgradient methods, to Stochastic gradient descent. We prove a non-asymptotic convergence at the rate bO(1/k) with a rate constant which can be better than the corresponding rate constant for optimally scheduled SGD. We demonstrate that the method is effective in practice, and on convex optimization problems and on training deep neural networks, and compare to the theoretical rate.