Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression
cs.LG, math.OC, stat.ML
Submitted: 2026-11-10
Updated: 2026-11-10
Comments: 33 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the excess risk of constant-stepsize online stochastic gradient descent (SGD) with tail-averaging for high-dimensional linear regression.
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 and initialization w 0-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 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 and any finite horizon, under an explicit horizon-dependent stepsize chosen prior to execution; and (ii) for polynomially decaying spectra λ i i-a (a>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.
Sources
- A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
- Stop Wasting My Time! Saving Days of ImageNet and BERT Training with Latest Weight Averaging
- Functional Scaling Laws in Kernel Regression: Loss Dynamics and Learning Rate Schedules
- Risk Bounds of Accelerated SGD for Overparameterized Linear Regression
- Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression
- Scaling Laws in Linear Regression: Compute, Parameters, and Data
- A Simplified Analysis of SGD for Linear Regression with Weight Averaging
- Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averaging
- Early Weight Averaging meets High Learning Rates for LLM Pre-training
- Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization
- Benign Overfitting of Constant-Stepsize SGD for Linear Regression
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis