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

Daniel Zantedeschi; Kumar Muthuraman

stat.MLMar 2, 2026

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

Authors: Daniel Zantedeschi, Kumar Muthuraman

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

Abstract

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.

Figures & tables

Primitive	Status quo	This paper	Pointers
Mini-batch noise covariance	Exogenous / isotropic / heuristic $\Gamma$	Identified from sampling: $\mathrm{Cov}(g_{B})\propto b^{-1}G^{\star}(\theta)$ ; Fisher is a special case	Sec. 4 ; Thm. 4.3
Continuous-time limit	Postulated SDE with ad hoc $\mathbf{C}(\theta)$	Fluid limit (ODE) for raw iterates; functional CLT for $\sqrt{b/\eta}$ -scaled fluctuations with diffusion $G^{\star}(\theta)$	Sec. 5 ; Thm. 5.7
OU / Lyapunov equilibrium	Heuristic OU with ad hoc covariance	OU fluctuation limit at $\theta^{\star}$ ; Lyapunov balance $H^{\star}\Sigma_{U}+\Sigma_{U}H^{\star\top}=G^{\star}$ on fluctuation scale; linearized original-scale benchmark $\Sigma_{\eta}^{\mathrm{lin}}=(\eta/b)\Sigma_{U}+o(\eta/b)$ (Prop. 5.13 / Cor. 5.11 )	Sec. 5 ; Cor. 5.11
Metric for rates	Euclidean distance; $\kappa_{H}$ dominates	Identified statistical metric is the natural risk	Sec. 6 ; Thm. 6.5
Lower bounds	Euclidean oracle lower bounds	Information-theoretic lower bound in Fisher metric (van Trees)	Sec. 6 ; Prop. 6.8
Dimension notion	Ambient $d$	Effective dimension $d_{\eff}$ induced by $F^{\star}$ / $G^{\star}$	Sec. 6 ; Def. ( 40 )

Table 1: Positioning: primitives, contrasts, and where each appears in the paper.

Symbol	Meaning
$L(\theta)=\mathbb{E}[\ell(\theta;Z)]$	Population risk (loss)
$\psi(\theta;z)=\nabla_{\theta}\ell(\theta;z)$	Per-sample estimating equation (gradient)
$g_{B}(\theta)$	Mini-batch gradient estimator
$G(\theta)=\mathrm{Cov}(\psi(\theta;Z))$	Gradient covariance; $G^{\star}=\Pi G\Pi^{\top}$ projected
$F(\theta)=\mathbb{E}[s_{\theta}s_{\theta}^{\top}]$	Fisher information (likelihood case)
$F^{\star}(\theta^{\star})$	Projected Fisher; equals $G^{\star}(\theta^{\star})$ under correct specification

Table 2: Key notation. All quantities are evaluated locally at or near

\theta^{\star}

unless noted otherwise.

Panel of Figure 1 — Figure 1: Isotropic noise (left, dashed circle) vs. Fisher-aligned noise (right, solid ellipse) at the same total variance. Batch size rescales temperature but not shape.

Figure 2: Experiment 1: direct covariance identification under misspecification (probit DGP, logistic fit). Diagonal entries of the empirical mini-batch covariance vs. $b^{-1}\hat{J}^{\star}$ (projected score covariance at $\beta^{\star}$ ); relative Frobenius difference $\approx 0.05$ .

Figure 3: Experiment 2, 2D batch-size sweep: stationary variances vs.

b

(log scales); solid = simulation, dashed = fluctuation-scale Lyapunov prediction.

Figure 4: Experiment 2, 2D angle sweep: stationary variances vs. misalignment angle $\varphi$ . Bands show replicate variability; dashed curves are the discrete Lyapunov prediction.

Figure 5: Experiment 2, 2D rotation diagnostic: stationary covariance ellipses at three rotation angles. The geometric equilibrium tilts with

\varphi

; the isotropic trace-matched surrogate remains axis-aligned.

Figure 6: Experiment 2, 2D rotation diagnostic: cross-covariance

\Sigma_{12}

vs. rotation angle. Isotropic trace-matched noise fails to reproduce off-diagonal covariance; bands show

\pm 1

s.d. across seeds.

	Empirical Risk $\widehat{R}_{T}$		Lyapunov $R_{\infty}$		$\widehat{R}_{T}/R_{\infty}$
$T$	Aniso	Iso	Aniso	Iso	Aniso	Iso
300	$8.55\!\times\!10^{-4}$	$8.60\!\times\!10^{-4}$	$8.63\!\times\!10^{-4}$	$8.58\!\times\!10^{-4}$	0.991	1.002
800	$8.64\!\times\!10^{-4}$	$8.49\!\times\!10^{-4}$			1.002	0.990
2 000	$8.58\!\times\!10^{-4}$	$8.50\!\times\!10^{-4}$			0.995	0.992
5 000	$8.72\!\times\!10^{-4}$	$8.58\!\times\!10^{-4}$			1.010	1.001
10 000	$8.63\!\times\!10^{-4}$	$8.47\!\times\!10^{-4}$			1.000	0.987

Table 3: Experiment 3 (OU/Lyapunov plateau,

d=10

): empirical Fisher-metric risk vs. discrete Lyapunov prediction

R_{\infty}=\mathrm{Tr}(F^{\star}\Sigma_{\eta}^{\mathrm{lin}})

. Convergence ratios

\widehat{R}_{T}/R_{\infty}\to 1

confirm quantitative accuracy.

Figure 7: Experiment 4 (decaying step size,

d=10

). Left: Fisher-metric risk vs.

N

(log–log); slopes

\approx-1

. Right: Scaled risk

N\cdot\widehat{\mathrm{Risk}}

stabilizes; inset shows

C=\mathrm{Tr}(G^{\star}H^{-1})

Figure 8: Experiment 5 (directional variance amplification,

d=10

). Left: Directional second moments along top eigenvectors of

G^{\star}

. Right: Ratio of anisotropic to isotropic directional variances; ratios

>1

mirror the eigenvalue ordering of

G^{\star}

. Trace-matched isotropic noise preserves

\mathrm{Tr}(G^{\star})

but spreads residual risk uniformly; the identified anisotropic noise concentrates it along the top noise eigendirections.

Figure 9: Experiment 6 (fluctuation-scale collapse diagnostic; Theorem 5.7 ): scaled Fisher risk

(b/\eta)\,\widehat{\mathbb{E}}[\|\theta_{T}\|_{F^{\star}}^{2}]

stabilizes at the fluctuation-scale Lyapunov prediction

\mathrm{Tr}(F^{\star}\Sigma_{U})

(black line) across eight

(\eta,b)

configurations.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 10: Experiment B: approximate exchangeability. Stationary variances vs.

\varepsilon

(simulation bands vs. linear Lyapunov prediction).

Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) uses noisy, data-sampled gradients to train models and solve large-scale optimization problems.

See all 214 papers

Scaling Limits of Constant-Stepsize SGD at Flat Minima
Jul 17, 2026Jingyi Zhang, Cheng Mao, Debankur MukherjeeStochastic Optimization Convergence Flat Minima
Georgia Institute of Technology
Gaussian Limits for SGD Without Stationary Moments
Oct 4, 2026Xiaoli Li, Wei Biao WuStochastic Optimization Convergence Stochastic Gradient Descent
University of Chicago
Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
Sep 24, 2026Wei Biao WuNonconvex Stochastic Optimization Stochastic Optimization Convergence

Jul 17, 2026J/K move · Enter open · S save

Scaling Limits of Constant-Stepsize SGD at Flat Minima

Jingyi Zhang, Cheng Mao, Debankur Mukherjee

Georgia Institute of Technology

Stochastic Optimization Convergence Flat Minima Stochastic Gradient Descent

Open paper AskPDF arXiv

For stochastic gradient descent (SGD) with a constant stepsize

α

, the invariant law of the iterates, centered at a minimizer, describes the behavior of the algorithm over long time horizons. In the strongly convex case, this invariant law has the familiar

\sqrtα

scaling and a Gaussian limit as

α\downarrow 0

. We show that this behavior changes fundamentally for convex objectives

H

with flat minima and (sub)quadratic tails. More specifically, we study SGD with Markovian noise generated by a contractive driving chain. For every sufficiently small constant stepsize

α

, we prove existence, uniqueness, and geometric convergence to an augmented invariant law in a Wasserstein distance induced by an

α

-dependent metric. When the minimizer

x_\star

has local flatness exponent

m\ge2

, meaning that

\nabla^2 H(x)\asymp \lVert x-x_\star\rVert^{m-2} I_d

x\to x_\star

, we obtain a contraction bound with factor

1-cα^{m-1}

, where

c>0

is a constant. This recovers the factor

1-cα

in the quadratic case

m=2

. We then analyze the small-stepsize scaling limit. We show that the invariant law concentrates on the scale

α^{1/m}

and that the rescaled iterates converge weakly to the stationary distribution of the stochastic differential equation

dY_t=-h_0(Y_t)\,dt+Σ^{1/2}\,dB_t ,

where

h_0

is the limiting drift at the minimizer and

Σ

denotes the asymptotic covariance. This recovers the Gaussian limit when

m=2

and gives generally non-Gaussian stationary limits in the flat case

m>2

. Finally, we give corresponding results for coordinate-separable objectives with unequal flatness exponents.

Abstract

Stochastic Gradient Descent

Explore similar work

Scaling Limits of Constant-Stepsize SGD at Flat Minima

Gaussian Limits for SGD Without Stationary Moments

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds