# Complexity Guarantees for Polyak Steps with Momentum

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2020.

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

- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Adaptive Memory Momentum via a Model-Based Framework for Deep Learning Optimization](https://mlsanity.com/paper/2510.04988/) (2025)
- [Fix the Loss, Not the Radius: Rethinking the Adversarial Perturbation of Sharpness-Aware Minimization](https://mlsanity.com/paper/2605.10183/) (2026)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)
- [AutoGD: Automatic Learning Rate Selection for Gradient Descent](https://mlsanity.com/paper/2510.09923/) (2025)

## Abstract (arXiv)

In smooth strongly convex optimization, knowledge of the strong convexity parameter is critical for obtaining simple methods with accelerated rates. In this work, we study a class of methods, based on Polyak steps, where this knowledge is substituted by that of the optimal value, f_*. We first show slightly improved convergence bounds than previously known for the classical case of simple gradient descent with Polyak steps, we then derive an accelerated gradient method with Polyak steps and momentum, along with convergence guarantees.