cs.LGNov 10, 2026

Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression

Authors: Qingyue Zhao, Xuheng Li, Quanquan Gu

Organizations: Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Abstract

We study the excess risk of constant-stepsize online stochastic gradient descent (SGD) with tail-averaging for high-dimensional linear regression. Building on the instance-dependent spectral framework of Zou et al. (2021), we establish matching initialization-explicit upper and lower bounds on the total excess risk of tail-averaged SGD in terms of the population covariance spectrum H\mathbf{H} and initialization w0−w∗\mathbf{w}_0-\mathbf{w}^* whenever a trajectory spectral feedback condition holds. Existing analyses exhibit a fundamental gap in the effective variance: the upper bound of Zou et al. (2021) retains an undamped contribution from the initial error in the head eigenspace I0:k†\mathbf{I}_{0:k^\dagger}, whereas their lower bound omits the variance induced by the head initialization altogether. We show that both the existing upper and lower bounds are loose: the single-hop fast-mode variance contribution from the head initialization is exponentially damped during the burn-in phase, whereas fourth-moment energy scattered from the head initialization into slow spectral modes during the early burn-in steps survives undamped into the averaging window. We prove that our spectral feedback condition is satisfied in two concrete constant-stepsize regimes: (i) for arbitrary covariance spectra H\mathbf{H} and any finite horizon, under an explicit horizon-dependent stepsize chosen prior to execution; and (ii) for polynomially decaying spectra λi≍i−aλ_i\asymp i^{-a} (a>1a>1), under a single horizon-independent positive stepsize. Finally, we complement these positive results with explicit one- and two-dimensional separation constructions proving an exponential-versus-polynomial gap in the lower bound of Zou et al. (2021) and showing why fourth-moment assumptions alone cannot determine the asymptotic exponential decay rate without additional structural conditions.

Figures & tables

Explore similar work

Aug 24, 2026

Stochastic gradient descent with initial regularization

We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order m−2log⁡2mm^{-2}\log^{2}m, where the number of training samples is of order mm. For another value of the source parameter, we obtain, for any ε>0ε>0, bounds of order m−3+εm^{-3+ε}, provided that the capacity parameter exceeds ε−1ε^{-1}. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.
May 23, 2025

Bias-Optimal Bounds for Stochastic Gradient Descent

The non-asymptotic analysis of Stochastic Gradient Descent (SGD) typically yields bounds that decompose into a bias term and a variance term. In this work, we focus on the bias component and study the extent to which SGD can match the optimal convergence behavior of deterministic gradient descent. Assuming only (strong) convexity and smoothness of the objective, we derive new bounds for the full range of constant step-sizes γL∈(0,2)γL \in (0,2). This includes critical and large step-size regimes that were previously unexplored without additional variance assumptions, in both the convex and strongly convex cases. Those bounds are bias-optimal, in the sense that the bias term coincides with the worst-case rate of gradient descent, for all non-critical step-sizes. For critical step-sizes, we show that no bounds can be obtained with an optimal bias term, but that this optimal bias can be approximated arbitrarily closely. As an immediate application, we provide new complexity bounds for the Stochastic Proximal algorithm, without the need of regularity assumptions.
Oct 31, 2026

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent γ∈(1/2,1)γ\in(1/2,1), a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order n1/2−γ+nγ−1n^{1/2-γ}+n^{γ-1} in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of γγ. The nonlinear bias contributes n1/2−γn^{1/2-γ} even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order n−(1−γ)/2n^{-(1-γ)/2} for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error ε\varepsilon on this example takes order ε−4\varepsilon^{-4} iterations for the best choice γ=3/4γ=3/4. Achieving both Gaussian approximation and relative mean variance-estimation errors at most ε\varepsilon uniformly over the model class requires at least order ε−6\varepsilon^{-6} iterations for every fixed γγ.