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

Yijin Ni; Xiaoming Huo

cs.LGApr 12, 2026

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

Authors: Yijin Ni, Xiaoming Huo

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

Abstract

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.

Figures & tables

Method	Rate	Hessian?	Online?	Reference
Online BM	$n^{-(1-\alpha)/4}$ ( $n^{-1/8}$ )	No	Yes	Zhu, Chen and Wu (2023)
Online BM (opt. $\beta$ )	$n^{-(1-\alpha)/3}$ ( $n^{-1/6}$ )	No	Yes	This paper
Traj. regression	$\mathbf{n^{-(1-\alpha)/2}}$ ( $\mathbf{n^{-1/4}}$ )	No	Yes	This paper
Online BM, Markovian	$n^{-(1-\alpha)/4}$ ( $n^{-1/8}$ )	No	Yes	Roy and Balasubramanian (2023)
Online BM, nonsmooth	$n^{-(1-\alpha)/4}$ ( $n^{-1/8}$ )	No	Yes	Jiang et al. (2025)
Equal BM	$n^{-(1-\alpha)/4}$ ( $n^{-1/8}$ )	No	No	Singh, Shukla and Vats (2025)

Table 1: Convergence rates for estimating

V

in operator norm. Here

\alpha\in(1/2,1)

is the learning-rate exponent. “Hessian?” indicates whether the method requires access to

H

H^{-1}

	Variance-limited ( $\beta_{0}$ , any $\rho$ )	Bias-balanced ( $\beta^{\dagger}$ , any $\rho$ )
Block growth $\beta$	$(1+\alpha)/(1-\alpha)\approx 3$	$(1+2\alpha)/(2(1-\alpha))\approx 2$
Number of blocks $b_{n}$	$\Theta(n^{1/4})$	$\Theta(n^{1/3})$
Rate	$n^{-1/8}$	$n^{-1/6}$

Table 2: Comparison of original and improved estimators at

\alpha=1/2+\varepsilon

Fig 1: Operator-norm error versus sample size

n

(log-log scale) for

\alpha\in\{0.55,0.60,0.70\}

. Blue circles: BM original (

\beta^{*}

\rho=1

). Green triangles: BM optimal (

\beta^{\dagger}

\rho=1

). Orange squares: BM burn-in (

\beta^{\dagger}

\rho=0.5

). Red diamonds: trajectory regression. Dotted lines: theoretical reference slopes

n^{-(1-\alpha)/4}

n^{-(1-\alpha)/3}

, and

n^{-(1-\alpha)/2}

Fig 2: Per-block bias (

\circ

, solid) and variance (

\square

, solid) as functions of block index

m

, for

\alpha=0.55

and

n=10^{5}

. Early blocks have large bias and contribute disproportionately to the estimation error. The vertical dotted line marks the burn-in cutoff (

\rho=0.5

); blocks to its right are retained.

Polyak-Ruppert Averaging

See all 8 papers

Apr 23, 2026

Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction

We study online inference and asymptotic covariance estimation for the stochastic gradient descent (SGD) algorithm. While classical methods (such as plug-in and batch-means estimators) are available, they either require inaccessible second-order (Hessian) information or suffer from slow convergence. To address these challenges, we propose a novel, fully online de-biased covariance estimator that eliminates the need for second-order derivatives while significantly improving estimation accuracy. Our method employs a bias-reduction technique to achieve a convergence rate of

n^{(α-1)/2} \sqrt{\log n}

, outperforming existing Hessian-free alternatives.

Ziyang Wei, Wanrong Zhu, Jingyang Lyu +1

Department of Statistics University of Chicago Chicago, IL 60637, USA · Department of Statistics University of California, Irvine Irvine, CA 92617, USA · Department of Statistics University of Wisconsin–Madison Madison, WI 53706, USA

Covariance Estimation Stochastic Gradient Descent

Ask PDF

Mar 2, 2026

Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

Stochastic gradient descent (SGD) is central to simulation optimization, stochastic programming, and online M-estimation, where sampling effort is a decision variable. We study the mini-batch gradient noise as a sampling-design object. Under exchangeable fresh-sampling mini-batches, the conditional covariance given the de Finetti directing measure mu is b^{-1} G_mu(theta), and under identifiability the projected population object is b^{-1} G*(theta) -- projected Fisher information for correctly specified likelihoods, the sandwich partner of the Hessian otherwise. This identification fixes the noise matrix entering the diffusion analysis of constant-step SGD: the raw iterate path has a deterministic fluid limit, and the sqrt(b/eta)-scaled fluctuations satisfy a functional CLT with noise covariance G*; near a nondegenerate optimum the limit is Ornstein-Uhlenbeck, and its Lyapunov covariance scaled by eta/b matches the linearized discrete recursion at leading order. Under a curvature-noise compatibility condition mu_F > 0, we prove 1/N mean-square upper bounds and an i.i.d. parametric Fisher van Trees lower bound of the same rate order, with oracle-complexity guarantees depending on an effective dimension d_eff and condition number kappa_F. Numerical experiments verify the identification and confirm the Lyapunov predictions in direct SGD.

Daniel Zantedeschi, Kumar Muthuraman

Muma College of Business, University of South Florida, Tampa, FL, USA · McCombs School of Business, University of Texas at Austin, Austin, TX, USA

Stochastic Gradient Descent Stochastic Optimization Convergence Oracle Complexity

Ask PDF

Sep 30, 2026

Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD

We prove a sharp Gaussian approximation for the invariant law of constant-stepsize SGD with bounded additive noise generated by an exogenous uniformly ergodic Markov chain. For a smooth, strongly convex objective with a Lipschitz Hessian and nondegenerate long-run noise covariance, the centered iterate normalized by the square root of the stepsize is

O(\sqrtα)

-close in 1-Wasserstein distance to its limiting Gaussian. The proof combines blockwise Gaussian comparison with long-run contraction. A four-state example gives a matching lower bound although the one-time noise marginal is symmetric and every nonzero-lag autocovariance vanishes. In this example, an adjacent third-order mixed moment produces the leading correction.

Junghoon Seo

PIT IN Corp., South Korea

Stochastic Approximation Stochastic Gradient Descent

Ask PDF

Abstract

Polyak-Ruppert Averaging

Explore similar work

Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction

Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD