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

Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
Apr 12, 2026Yijin Ni, Xiaoming HuoPolyak-Ruppert Averaging Covariance Estimation
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods
Jun 17, 2026Depen Morwani, Alexandru Meterez, Pranav Nair +1Stochastic Optimization Momentum Methods
1Harvard University · 2Kempner Institute at Harvard University · †: Work done while at Harvard.
Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
Sep 26, 2026Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5Polyak-Ruppert Averaging Stochastic Optimization
Independent Researcher · HSE University · MBZUAI +3

Apr 12, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

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