When Momentum Helps Polyak--Ruppert Averaging
Abstract
Polyak--Ruppert averaging gives SGD and momentum methods the same asymptotic covariance. We characterize how fast finite runs reach it and how far they can be parallelized. For strongly convex quadratics with additive noise, we prove an online--offline bridge: the empirical risk minimizer on the samples of a tail average is one Newton step from the tail-averaged query point of any online procedure. For SGD, heavy ball, and Nesterov's method with constant momentum, this step is a boundary term at the two ends of the tail and splits the gap to the offline estimator into center, covariance, and shape errors. Necessary and sufficient conditions show that, on the least curved direction, the center error sets the pace: SGD needs m≫κ2 rounds but momentum only m≫κ, where κ is the condition number, so at sample size N the critical batch size grows from Θ(√N/κ) to Θ(√(N/κ)). The covariance error separates the momentum methods: heavy ball has relative variance excess Θ(κ3/2/m) along the stiffest direction, whereas Nesterov has relative error O(√κ/m) in every direction. The shape error is method-independent by a Berry--Esseen bound uniform in κ and batch size, so confidence intervals are valid when the other two errors vanish. We further examine how the conclusions change under heavy-tailed or state-dependent noise and clipping, and establish a first-order comparison with ERM for nonlinear Nesterov averaging under explicit conditions.
Related
- Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
- Momentum in large-batch training: Polyak enlarges the critical batch size, Nesterov improves data efficiency
- When Does Momentum Help in Reinforcement Learning with Verifiable Rewards?
- The ballistic limit of the log-Sobolev constant equals the Polyak–Łojasiewicz constant
- Single-call Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
BibTeX
@misc{suvorikova2026when,
title = {{When Momentum Helps Polyak--Ruppert Averaging}},
author = {Alexandra Suvorikova and Darina Dvinskikh and Yuriy Dorn and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27990},
eprint = {2610.27990},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27990},
}
RIS
TY - UNPB
TI - When Momentum Helps Polyak--Ruppert Averaging
AU - Alexandra Suvorikova
AU - Darina Dvinskikh
AU - Yuriy Dorn
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.27990
UR - https://arxiv.org/abs/2610.27990
AB - Polyak--Ruppert averaging gives SGD and momentum methods the same asymptotic covariance. We characterize how fast finite runs reach it and how far they can be parallelized. For strongly convex quadratics with additive noise, we prove an online--offline bridge: the empirical risk minimizer on the samples of a tail average is one Newton step from the tail-averaged query point of any online procedure. For SGD, heavy ball, and Nesterov's method with constant momentum, this step is a boundary term at the two ends of the tail and splits the gap to the offline estimator into center, covariance, and shape errors. Necessary and sufficient conditions show that, on the least curved direction, the center error sets the pace: SGD needs m≫κ^2 rounds but momentum only m≫κ, where κ is the condition number, so at sample size N the critical batch size grows from Θ(√N/κ) to Θ(√(N/κ)). The covariance error separates the momentum methods: heavy ball has relative variance excess Θ(κ^3/2/m) along the stiffest direction, whereas Nesterov has relative error O(√κ/m) in every direction. The shape error is method-independent by a Berry--Esseen bound uniform in κ and batch size, so confidence intervals are valid when the other two errors vanish. We further examine how the conclusions change under heavy-tailed or state-dependent noise and clipping, and establish a first-order comparison with ERM for nonlinear Nesterov averaging under explicit conditions.
ER -