Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression
Zhao et al.
Matching upper and lower bounds on the excess risk of constant-step tail-averaged SGD in high-dimensional linear regression, explicit in the covariance spectrum \(\mathbf{H}\) and the initial error.
Source published · In the Daily Brief of 12 November 2026
Filed under Optimization, Learning theory
Instance-dependent bounds for tail-averaged stochastic gradient descent, in the spectral framework of Zou et al. (2021), left a gap: the upper bound kept an undamped contribution from the initial error in the leading eigendirections, while the lower bound dropped that contribution entirely. The paper shows both were loose. The direct variance from the head initialisation is damped exponentially during burn-in, but fourth-moment energy scattered early into slow spectral modes survives into the averaging window.
Under a spectral feedback condition the authors obtain matching upper and lower bounds, and prove the condition holds in two regimes: any spectrum with a horizon-dependent step size fixed in advance, and polynomially decaying spectra \(\lambda_i \asymp i^{-a}\) with \(a > 1\) under a single horizon-free step size. Low-dimensional constructions show an exponential-versus-polynomial gap in the earlier lower bound, and that fourth-moment assumptions alone cannot fix the asymptotic decay rate.