Heavy-Ball Method under Randomized Schedules

Abstract

We study how predefined randomized parameter schedules accelerate the heavy-ball method on general smooth convex objectives. Our analysis distinguishes two levels of randomization: sampling gradient-evaluation times within intervals whose boundaries are deterministic, and additionally randomizing the time boundaries themselves. With deterministic time boundaries, we construct fixed-time and anytime schedules that achieve an expected last-iterate function value gap of order 𝒪(1/K^4/3); the anytime schedule also satisfies the same rate almost surely. We then use randomized time boundaries and obtain the improved last-iterate rate 𝒪(1/K^3/2), both in expectation and almost surely. To the best of our knowledge, this is the first global nonasymptotic convergence guarantee for the heavy-ball method on general smooth convex functions that improves polynomially over the classical 𝒪(1/K) rate. Our result shows that the heavy-ball method achieves a strictly better convergence rate than the best known result 𝒪(1/K^{log₂(1+√2)}) attainable by plain gradient descent with silver stepsize schedules.

Randomized average block coordinate descent method with heavy-ball momentum for tensor least squares problem under the t-product
Li-Lin Ji, Ni-Hong Ke, Jun-Feng Yin
arXiv13 Sep 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
Jianhao Ma, Jingzhao Zhang
arXiv8 Sep 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Sharp Initialization Guarantees for the Heavy-Ball Method
Kang Liu, Quanen Wu, Zhan Sun +3
arXiv7 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Non-Acceleration of the Heavy-Ball Method in 1D
Konstantinos Fotopoulos, Michael Helcig, Karl Deck +1
arXiv18 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Transformers with CoT Discover Heavy-Ball Acceleration Through Training
Yuxuan Cai, Yuan Cao
arXiv22 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{he2026heavyball,
  title = {{Heavy-Ball Method under Randomized Schedules}},
  author = {Chang He and Shuzhong Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.09743},
  eprint = {2609.09743},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.09743},
}

RIS

TY  - UNPB
TI  - Heavy-Ball Method under Randomized Schedules
AU  - Chang He
AU  - Shuzhong Zhang
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.09743
UR  - https://arxiv.org/abs/2609.09743
AB  - We study how predefined randomized parameter schedules accelerate the heavy-ball method on general smooth convex objectives. Our analysis distinguishes two levels of randomization: sampling gradient-evaluation times within intervals whose boundaries are deterministic, and additionally randomizing the time boundaries themselves. With deterministic time boundaries, we construct fixed-time and anytime schedules that achieve an expected last-iterate function value gap of order 𝒪(1/K^4/3); the anytime schedule also satisfies the same rate almost surely. We then use randomized time boundaries and obtain the improved last-iterate rate 𝒪(1/K^3/2), both in expectation and almost surely. To the best of our knowledge, this is the first global nonasymptotic convergence guarantee for the heavy-ball method on general smooth convex functions that improves polynomially over the classical 𝒪(1/K) rate. Our result shows that the heavy-ball method achieves a strictly better convergence rate than the best known result 𝒪(1/K^log_2(1+√2)) attainable by plain gradient descent with silver stepsize schedules.
ER  -

Abstract

Related

Cite