Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis
Abstract
Polyak step size (PS) and Armijo line search (ALS) have received increasing attention in stochastic optimization, with encouraging empirical performance and theoretical guarantees. However, their convergence theory for stochastic heavy ball (SHB) methods remains limited. In this work, we develop a unified convergence analysis for SHB equipped with PS and ALS. To this end, we introduce a modified Armijo rule that closely parallels the Polyak step size, together with a decoupling analysis that isolates the historical dependence induced by momentum. For SHB with standard PS and ALS, we establish expected convergence for strongly convex, convex, and non-convex objectives without interpolation or restrictive conditions on the momentum parameter. Under interpolation or strong growth, we further strengthen the results to almost sure rates and last-iterate convergence. Moreover, for general settings beyond interpolation, we prove almost sure convergence to the exact optimum or to stationarity for SHB with diminishing variants of PS and ALS. These results provide a more comprehensive theoretical view of Polyak step size and Armijo line search for stochastic heavy ball methods.
Related
- Incremental Stability of Gradient Flows under Generalized Polyak-Łojasiewicz Inequalities and Its Implications for General Systems
- Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
- Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates
- Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
BibTeX
@misc{zhang2026stochastic,
title = {{Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis}},
author = {Jiawei Zhang and Qitan Shi and Yuantao Gu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36668},
eprint = {2609.36668},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36668},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis
AU - Jiawei Zhang
AU - Qitan Shi
AU - Yuantao Gu
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36668
UR - https://arxiv.org/abs/2609.36668
AB - Polyak step size (PS) and Armijo line search (ALS) have received increasing attention in stochastic optimization, with encouraging empirical performance and theoretical guarantees. However, their convergence theory for stochastic heavy ball (SHB) methods remains limited. In this work, we develop a unified convergence analysis for SHB equipped with PS and ALS. To this end, we introduce a modified Armijo rule that closely parallels the Polyak step size, together with a decoupling analysis that isolates the historical dependence induced by momentum. For SHB with standard PS and ALS, we establish expected convergence for strongly convex, convex, and non-convex objectives without interpolation or restrictive conditions on the momentum parameter. Under interpolation or strong growth, we further strengthen the results to almost sure rates and last-iterate convergence. Moreover, for general settings beyond interpolation, we prove almost sure convergence to the exact optimum or to stationarity for SHB with diminishing variants of PS and ALS. These results provide a more comprehensive theoretical view of Polyak step size and Armijo line search for stochastic heavy ball methods.
ER -