Momentum in large-batch training: Polyak enlarges the critical batch size, Nesterov improves data efficiency

Abstract

We study when and how momentum improves large-batch training in the one-pass regime, using power-law kernel regression as a tractable setting. We first characterize stochastic stability through the \emph{critical learning rate}, defined as the largest learning rate for stable training, and obtain ${\eta }_{\mathrm{SGD}}^{\mathrm{crit}}\eqsim 1$, ${\eta }_{\mathrm{Polyak}}^{\mathrm{crit}}\eqsim \min \{1,B(1-\beta )\}$, and ${\eta }_{\mathrm{Nesterov}}^{\mathrm{crit}}\eqsim \min \{1,B^q(1-\beta )\}$, where $B$ is the batch size, $\beta \in [0,1)$ is the momentum factor, and \(q>1\) is the capacity exponent governing spectral decay. Within the stable region, we derive scaling laws for the full risk dynamics, capturing the progression from an early transient through power-law decay to a noise floor. We then optimize the final-step risk under a fixed data budget, obtaining a three-regime phase diagram that reveals how the benefits of momentum change with batch size. Notably, Polyak enlarges the critical batch size, the largest batch size preserving the optimal small-batch data-scaling exponent, thereby allowing fewer sequential updates without sacrificing data efficiency. In contrast, Nesterov improves the optimal data-scaling exponent in the large-batch regime through look-ahead-induced suppression of noise amplification. Experiments on PLK regression quantitatively support the theoretical scaling predictions, while neural-network experiments provide qualitative evidence for the predicted batch-size dependence and stability behavior.

arXiv comment63 pages, 10 figures, 1 table. Revised proofs; added neural-network experiments