When Momentum Helps Polyak--Ruppert Averaging

Alexandra Suvroikova; Darina Dvinskikh; Yuriy Dorn; Alexander Gasnikov

cs.LGOct 20, 2026

When Momentum Helps Polyak--Ruppert Averaging

Authors: Alexandra Suvroikova, Darina Dvinskikh, Yuriy Dorn, Alexander Gasnikov

Organizations: Independent researcher · HSE University · MSU AI Institute · Innopolis University

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\ggκ^2$ rounds but momentum only $m\ggκ$ , where $κ$ is the condition number, so at sample size $N$ the critical batch size grows from $Θ(\sqrt{N}/κ)$ to $Θ(\sqrt{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(\sqrtκ/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.

Figures & tables

Criterion in the $\mu$ direction	SGD	HB	NAG
Vanishing relative variance error	$m\gg\kappa$	$m\gg\sqrt{\kappa}$	$m\gg\sqrt{\kappa}$
Negligible normalized bias and relative variance error, $b=1$ , fixed $\theta\neq 0$	$m\gg\kappa^{2}$	$m\gg\kappa$	$m\gg\kappa$
Initialization-induced batch scale at fixed $N$ , up to constants	$\dfrac{\sqrt{N}}{\|\theta\|\kappa}$	$\dfrac{\sqrt{N}}{\|\theta\|\sqrt{\kappa}}$	$\dfrac{\sqrt{N}}{\|\theta\|\sqrt{\kappa}}$

Table 1: Calibration thresholds on the least-curved direction for full averages from a deterministic start.

Figure 1: Coverage of nominal

95\%

intervals against the batch size

b

at the fixed budget

N=2^{16}

, with

\kappa=1.5\times 10^{4}

. Panels (a) and (b) show the slowest and the stiffest Hessian eigendirection, and panel (c) the age coefficient. Curves are Gaussian coverage predictions based on finite-sample moments , and markers are simulated coverages. Bands show the

95\%

range of the Monte Carlo estimate.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Parameters	$\bm{\varrho}$	$\bm{c}$	$\bm{S_{\infty}:=\sum_{j\geq 0}r_{j}}$
SGD	$\alpha=\frac{1}{L}$	$1-\frac{1}{\kappa}$	$0$	$\kappa$
HB	$\alpha=\frac{4}{(\sqrt{L}+\sqrt{\mu})^{2}}$ , $\beta=\left(\frac{\varkappa-1}{\varkappa+1}\right)^{2}$	$\frac{\varkappa-1}{\varkappa+1}$	$1-\varrho$	$\varkappa$
NAG	$\alpha=\frac{1}{L}$ , $\beta=\gamma=\frac{\varkappa-1}{\varkappa+1}$	$1-\frac{1}{\varkappa}$	$\frac{1-\varrho}{2-\varrho}$	$\frac{2\varkappa^{2}}{\varkappa+1}$

Appendix

Table 2: Standard Parameter Policies and Least-Curved-Mode Response Constants

Target	Typical statement	What it resolves / what it hides
Optimization transient	$\left\lVert x_{k}-x_{\star}\right\rVert^{2}\leq\rho^{2k}\left\lVert x_{0}-x_{\star}\right\rVert^{2}+\cdots$	Burn-in and conditioning; not the law of the output.
Finite-budget risk	$\mathbb{E}\left\lVert\hat{x}_{N}-x_{\star}\right\rVert^{2}\leq c_{0}/N+\varepsilon_{N}$	Valid at every $N$ ; constants and directional uncertainty may be hidden.
Distributional limit	$\sqrt{N}(\hat{x}_{N}-x_{\star})\xrightarrow{\mathrm{d}}\mathcal{N}(0,V)$	local geometry and inference; says little about how large $N$ must be.
Offline expansion	$\widehat{x}^{\rm ERM}_{N}-x_{\star}=-[\nabla^{2}f(x_{\star})]^{-1}\bar{\eta}+\text{remainder}$	Law of the offline estimator on the same data, $\bar{\eta}$ being the empirical noise mean; says nothing about how an online method reaches it.

Appendix

Table 3: Four Non-Equivalent Meanings of Convergence

Description	MSE and confidence radius	Assumptions and required knowledge
Descent	$U_{\rm en}$ ; $\sqrt{U_{\rm en}/\delta}$	Smoothness, strong convexity, conditional variance; $\mu,L,R_{0},\sigma^{2}$ .
Contraction	$U_{\rm con}$ ; $\sqrt{U_{\rm con}/\delta}$	Additive quadratic model, finite variance; the same scalar knowledge.
moments	Equation 72 ; MSE without an asymptotic remainder	In addition $H,\Sigma,e_{0}$ ; for unknown $e_{0}$ the bound $R_{0}$ is used.
PR approximation	$\operatorname{tr}V_{\star}/N$ ; a Gaussian quantile only after controlling the center and the covariance	Not a finite-time upper bound.

Appendix

Table 4: Comparable Guarantees for One Averaged SGD Output

Quantity	Cross-validated $\bm{\lambda}$	Second $\bm{\lambda}$	Third $\bm{\lambda}$
$\kappa$ of $H$ , linear model	$1.5\times 10^{4}$	$1532$	$153$
$\kappa$ of $H$ at $x_{\star}$ , logistic model	$4.1\times 10^{4}$	$209$	$23$
$L/\mu$ with global constants, logistic model	$1.3\times 10^{5}$	$425$	$39$
Variance of log income explained by $\hat{f}$	$66\%$
Reduction of $\operatorname{tr}\Sigma$ by the control variate	factor $168$

Appendix

Table 5: Constants of the Census Experiments

Figure 2: (a) Predicted against observed coverage over all budgets, batch sizes, ridge levels, functionals, and methods. (b) Breakdown batch for the age coefficient against the budget: observed (markers) and predicted (lines); the dashed line is the gradient noise scale. (c) Relative variance excess along the eigenvectors of

H

N=2^{16}

and

b=4

(markers: Monte Carlo; lines: exact; grey band:

\pm 2

Monte Carlo standard errors). (d) Coverage for the age coefficient starting from the pilot mean (solid lines, filled markers) and from

x_{0}=0

(dashed lines, open markers); lines are predictions and markers Monte Carlo estimates.

Figure 3: Normalized mean squared error against the batch size at

N=2^{16}

and

\kappa=1.5\times 10^{4}

, for the functionals of Figure 1 . Lines show the values

h_{c}^{2}+v_{c}

, shaded bands

\pm 2

Monte Carlo standard errors for

500

replicates around them, and markers the Monte Carlo estimates. Gray horizontal dashed and dotted lines mark the PR level and twice that level.

Figure 4: (a, b) Kolmogorov distance to the standard normal law for untransformed income after (a) and PR (b) normalization; colors mark the methods, line styles the batch sizes, and the dotted line is the

5\%

critical value for

4000

draws. (c) Normalized gap to the ERM in the logistic model; the dotted line is the normalized error of the ERM, and bands are

\pm 2

Monte Carlo standard errors.

Batch	Method	Oracle	Plug-in	Batch means	Random scaling
$b=16$	SGD	$0.93$	$0.93$ $(1.0)$	$0.91$ $(0.95)$	$0.92$ $(1.1)$
	HB	$0.80$	$0.81$ $(1.0)$	$1.00$ $(6.9)$	$1.00$ $(4.4)$
	NAG	$0.94$	$0.94$ $(1.0)$	$0.96$ $(1.1)$	$0.95$ $(1.2)$
$b=2^{11}$	SGD	$0.00$	$0.00$ $(1.0)$	$0.91$ $(4.8)$	$1.00$ $(7.8)$
	HB	$0.01$	$0.01$ $(1.0)$	$0.95$ $(9.6)$	$1.00$ $(33)$
	NAG	$0.91$	$0.91$ $(1.0)$	$1.00$ $(12)$	$1.00$ $(7.6)$

Appendix

Table 6: Coverage and Relative Width of Practical Intervals

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

Apr 12, 2026

Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression

We study online covariance matrix estimation for Polyak--Ruppert averaged stochastic gradient descent (SGD). The online batch-means estimator of Zhu, Chen and Wu (2023) achieves an operator-norm convergence rate of

O(n^{-(1-α)/4})

, which yields

O(n^{-1/8})

at the optimal learning-rate exponent

α\rightarrow 1/2^+

. A rigorous per-block bias analysis reveals that re-tuning the block-growth parameter improves the batch-means rate to

O(n^{-(1-α)/3})

, achieving

O(n^{-1/6})

. The modified estimator requires no Hessian access and preserves

O(d^2)

memory. We provide a complete error decomposition into variance, stationarity bias, and nonlinearity bias components. A weighted-averaging variant that avoids hard truncation is also discussed. We establish the minimax rate

Θ(n^{-(1-α)/2})

for Hessian-free covariance estimation from the SGD trajectory: a Le Cam lower bound gives

Ω(n^{-(1-α)/2})

, and a trajectory-regression estimator--which estimates the Hessian by regressing SGD increments on iterates--achieves

O(n^{-(1-α)/2})

, matching the lower bound. The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.

Yijin Ni, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Polyak-Ruppert Averaging Covariance Estimation Minimax Estimation Stochastic Gradient Descent

Ask PDF

Jun 17, 2026

Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods

Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor

\sqrtκ

larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.

Depen Morwani, Alexandru Meterez, Pranav Nair +1

1Harvard University · 2Kempner Institute at Harvard University · †: Work done while at Harvard.

Stochastic Optimization Momentum Methods Stochastic Optimization Convergence Accelerated Gradient Methods Stochastic Gradient Descent

Ask PDF

Sep 26, 2026

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise

Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample comparison of clipped and unclipped Polyak-Ruppert averaged SGD under finite conditional

p

-th moments,

p\ge2

. Our main result gives explicit accuracy and confidence conditions under which, for

p>2

, the Gaussian term dominates the unclipped deviation bound, so clipping need not improve its leading order. By balancing clipping bias and concentration, we obtain a bound in which the heavy-tail correction depends logarithmically rather than polynomially on the inverse failure probability. At

p=2

, this improves the confidence dependence of the leading bound. We establish sharpness of the unclipped heavy-tail term through an exact one-dimensional quadratic recursion and extend the comparison to projected convex SGD. We also prove concrete costs of clipping: every fixed finite threshold increases asymptotic variance on a scalar Gaussian quadratic, while whole-gradient clipping can shift the limiting point under asymmetric noise.

Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5

Independent Researcher · HSE University · MBZUAI +3

Polyak-Ruppert Averaging Stochastic Optimization Gradient Clipping Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization

Ask PDF

Abstract

Stochastic Optimization

Explore similar work

Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression

Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise