Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance
Dimitris Oikonomou, Nicolas Loizou
Abstract
Stochastic gradient descent with momentum, also known as Stochastic Heavy Ball method (SHB), is one of the most popular algorithms for solving large-scale stochastic optimization problems in various machine learning tasks. In practical scenarios, tuning the step-size and momentum parameters of the method is a prohibitively expensive and time-consuming process. In this work, inspired by the recent advantages of stochastic Polyak step-size in the performance of stochastic gradient descent (SGD), we propose and explore new Polyak-type variants suitable for the update rule of the SHB method. In particular, using the Iterate Moving Average (IMA) viewpoint of SHB, we propose and analyze three novel step-size selections: MomSPS max , MomDecSPS, and MomAdaSPS. For MomSPS max , we provide convergence guarantees for SHB to a neighborhood of the solution for convex and smooth problems (without assuming interpolation). If interpolation is also satisfied, then using MomSPS max , SHB converges to the true solution at a fast rate matching the deterministic HB. The other two variants, MomDecSPS and MomAdaSPS, are the first adaptive step-size for SHB that guarantee convergence to the exact minimizer -without a priori knowledge of the problem parameters and without assuming interpolation. Our convergence analysis of SHB is tight and obtains the convergence guarantees of stochastic Polyak step-size for SGD as a special case. We supplement our analysis with experiments validating our theory and demonstrating the effectiveness and robustness of our algorithms. B i∈St ∇f i (x t ) is the mini-batch gradient. Here γ t > 0 is the step-size/learning rate at iteration t while β t ≥ 0 represents the momentum parameter.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
6 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Scheduler cites Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients
- Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Scheduler cites Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
- Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients cites Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
- Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients cites An Improved Analysis of Stochastic Gradient Descent with Momentum
- Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients cites A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
- Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients cites New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
- Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution cites Training Neural Networks for and by Interpolation
- Understanding MARS: When Scaling Momentum Provably Helps cites An Improved Analysis of Stochastic Gradient Descent with Momentum
- Enhancing Optimizer Stability: Momentum Adaptation of The NGN Step-size cites Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
- Enhancing Optimizer Stability: Momentum Adaptation of The NGN Step-size cites An Improved Analysis of Stochastic Gradient Descent with Momentum
- Enhancing Optimizer Stability: Momentum Adaptation of The NGN Step-size cites New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
- Stochastic Hamiltonian Gradient Methods for Smooth Games cites A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results cites Training Neural Networks for and by Interpolation
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results cites Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
Cited by top-tier papers6
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative ResultsFrancesco Orabona, Ryan D'OrazioNeurIPS 2025 · 9 citations
- Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)GradientsDimitris Oikonomou, Nicolas LoizouICML 2026 · 4 citations
- Enhancing Optimizer Stability: Momentum Adaptation of The NGN Step-sizeRustem Islamov, Niccolò Ajroldi, Antonio Orvieto, Aurélien LucchiNeurIPS 2025 · 1 citation
- Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded SchedulerDimitris Oikonomou, Nicolas LoizouICML 2026
- Understanding MARS: When Scaling Momentum Provably HelpsEgor Shulgin, Tamaz Gadaev, Sarit Khirirat, Peter RichtarikICML 2026
Builds on13
- A Unified Theory of Decentralized SGD with Changing Topology and Local UpdatesAnastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi et al.ICML 2020 · 623 citations
- An Improved Analysis of Stochastic Gradient Descent with MomentumYanli Liu, Yuan Gao, Wotao YinNeurIPS 2020 · 328 citations
- Training Neural Networks for and by InterpolationLeonard Berrada, Andrew Zisserman, M. Pawan KumarICML 2020 · 71 citations
- Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact SolutionAntonio Orvieto, Simon Lacoste-Julien, Nicolas LoizouNeurIPS 2022 · 57 citations
- Stochastic Hamiltonian Gradient Methods for Smooth GamesNicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau, Pascal Vincent et al.ICML 2020 · 54 citations
Related papers
- The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball MethodsWei Tao, Sheng Long, Gaowei Wu, Qing TaoICLR 2021 · 17 citations
- Generalized Polyak Step Size for First Order Optimization with MomentumXiaoyu Wang, Mikael Johansson, Tong ZhangICML 2023 · 32 citations
- Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic ModelsCourtney Paquette, Elliot PaquetteNeurIPS 2021 · 20 citations
- Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient NoiseRui Pan, Yuxing Liu, Xiaoyu Wang, Tong ZhangICLR 2024 · 10 citations
- Demystify Hyperparameters for Stochastic Optimization with Transferable RepresentationsJianhui Sun, Mengdi Huai, Kishlay Jha, Aidong ZhangKDD 2022 · 5 citations
