Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression
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 and initialization 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 , 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 and any finite horizon, under an explicit horizon-dependent stepsize chosen prior to execution; and (ii) for polynomially decaying spectra (), 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
| Bound | Panel A: Fast-Mode Index Component ( ) |
| Zou et al. (2021, Theorem 5.1) (Upper) | |
| Zou et al. (2021, Theorem 5.2) (Lower) | |
| Corollary 4.5 (Ours, Upper & Lower) | |
| Bound | Panel B: Slow-Mode Index Component ( ) |
| Zou et al. (2021, Theorem 5.1) (Upper) | |
| Zou et al. (2021, Theorem 5.2) (Lower) |
Stochastic Gradient Descent
Stochastic Gradient Descent (SGD) uses noisy, data-sampled gradients to train models and solve large-scale optimization problems.
See all 252 papers