betaFeedback

WorksComputer Science

Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in 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\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.

Introduction

Understanding how first-order stochastic optimization generalizes in high- and infinite-dimensional feature spaces is a central theme in modern statistical learning theory. For offline empirical risk minimization in linear regression, Bartlett et al. [2] and Tsigler and Bartlett [33] characterized benign overfitting—when minimum-ℓ2\ell_2-norm interpolators and ridge regression generalize well despite fitting noisy training data—in terms of the effective ranks of the population data covariance operator H\mathbf{H} ([3, 11]). In the complementary setting of fresh-sample online stochastic approximation, Zou et al. [37] established an instance-dependent excess risk analysis for constant-stepsize stochastic gradient descent (SGD) with full iterate averaging, demonstrating that online SGD enjoys an implicit spectral regularization effect governed by a closely related spectral partition of H\mathbf{H} (while noting that for polynomially decaying spectra such as λi=i−2\lambda_i=i^{-2}, online SGD achieves vanishing excess risk by forgetting noisy labels rather than interpolating training data; see also Wu et al. (2025)).

In large-scale stochastic optimization, however, averaging all iterates from the initial point w0\mathbf{w}_0 suffers from slow polynomial decay of its deterministic drift bias 12∥E[w‾0:N]−w∗∥H2\frac{1}{2}\|\mathbb{E}[\overline{\mathbf{w}}_{0:N}]-\mathbf{w}^{*}\|_{\mathbf{H}}^{2}—decaying at best as O(N−2)O(N^{-2}) when ∥w0−w∗∥H−1<∞\|\mathbf{w}_0-\mathbf{w}^{*}\|_{\mathbf{H}^{-1}}<\infty (or in finite dimensions with λd>0\lambda_d>0), and even more slowly (e.g., Θ(N−3/2)\Theta(N^{-3/2}) when λi=i−2\lambda_i=i^{-2} and (w0−w∗)i2=i−2(\mathbf{w}_0-\mathbf{w}^{*})_i^2=i^{-2}) when slow spectral modes remain uncontracted. To accelerate the decay of initial error while preserving statistical efficiency, Rakhlin et al. [29] introduced suffix (tail) averaging for stochastic gradient descent, and Jain et al. [15, 14] developed its operator-theoretic analysis for least-squares linear regression; in modern deep learning and language model pretraining, its checkpoint-based counterpart Latest Weight Averaging (LAWA) ([16, 32]) averages recent checkpoints along the trajectory to achieve rapid training speedups. Tail-averaging discards the first ss iterates as a burn-in phase and averages the subsequent NN iterates:

w‾s:s+N=1N∑t=ss+N−1wt,wherewt=wt−1+γ(yt−⟨wt−1,xt⟩)xt.\overline{\mathbf{w}}_{s:s+N}=\frac{1}{N}\sum_{t=s}^{s+N-1}\mathbf{w}_t,\qquad\text{where}\qquad\mathbf{w}_t=\mathbf{w}_{t-1}+\gamma\left(\mathbf{y}_t-\langle\mathbf{w}_{t-1},\mathbf{x}_t\rangle\right)\mathbf{x}_t.

Zou et al. [37] extended their spectral excess risk analysis to tail-averaged SGD. Let {λi}i>1\{\lambda_i\}_{i>1} denote the eigenvalues of H\mathbf{H} in non-increasing order, and define the effective dimension cutoffs k∗=max⁡{k:λk≥(γN)−1}k^{*}=\max\{k:\lambda_k\geq(\gamma N)^{-1}\} and k†=max⁡{k:λk≥(γ(s+N))−1}k^{\dagger}=\max\{k:\lambda_k\geq(\gamma(s+N))^{-1}\}. Up to universal multiplicative constants, when the burn-in length satisfies s=Θ(N)s=\Theta(N), Zou et al. [37] upper-bounds the bias-induced variance contribution by

α(∥w0−w∗∥I0:k†2+(s+N)γ∥w0−w∗∥Hk†:∞2)Nγ(1−γαtr⁡(H))⋅(k∗N+Nγ2∑i>k∗λi2),(1)\frac{\alpha\left(\|\mathbf{w}_0-\mathbf{w}^{*}\|_{\mathbf{I}_{0:k^{\dagger}}}^{2}+(s+N)\gamma\|\mathbf{w}_0-\mathbf{w}^{*}\|_{\mathbf{H}_{k^{\dagger}:\infty}}^{2}\right)}{N\gamma(1-\gamma\alpha\operatorname{tr}(\mathbf{H}))}\cdot\left(\frac{k^{*}}{N}+N\gamma^{2}\sum_{i>k^{*}}\lambda_i^{2}\right), \tag*{(1)}

whereas their lower bound (Zou et al. [37]) yields only

β∥w0−w∗∥Hk†:∞2⋅(k∗N+Nγ2∑i>k∗λi2).(2)\beta\|\mathbf{w}_0-\mathbf{w}^{*}\|_{\mathbf{H}_{k^{\dagger}:\infty}}^{2}\cdot\left(\frac{k^{*}}{N}+N\gamma^{2}\sum_{i>k^{*}}\lambda_i^{2}\right). \tag*{(2)}

Comparing (1) and (2), Zou et al. [37] observed that the two bounds fail to match whenever the initial error w0−w∗\mathbf{w}_0-\mathbf{w}^{*} has significant energy in the head subspace I0:k†\mathbf{I}_{0:k^{\dagger}}, and conjectured that the upper bound (1) can be improved. The same discrepancy on the head initialization subspace persists in the exponential moving average (EMA) analysis of Li and Gu [20] and in the simplified diagonal covariance analysis of Meterez et al. [22].

Why Both Existing Upper and Lower Bounds Are Loose

In this paper, we show that closing the gap between (1) and (2) requires sharpening both the upper bound in Zou et al. [37] and the lower bound in Zou et al. [37]. Specifically, expanding the outer product in (1) between the initialization subspaces {I0:k†,Hk†:∞}\{\mathbf{I}_{0:k^{\dagger}},\mathbf{H}_{k^{\dagger}:\infty}\} and the fast and slow variance components {k∗/N,Nγ2∑i>k∗λi2}\{k^{*}/N,N\gamma^{2}\sum_{i>k^{*}}\lambda_i^{2}\} reveals two distinct physical mechanisms during the burn-in phase:

  1. Looseness in the Upper Bound (Undamped Fast-Mode Terms): The product term 1γN∥w0−w∗∥I0:k†2⋅k∗N\frac{1}{\gamma N}\|\mathbf{w}_0-\mathbf{w}^{*}\|_{\mathbf{I}_{0:k^{\dagger}}}^{2}\cdot\frac{k^{*}}{N} in (1) does not decay with the burn-in length ss. Consequently, even when

all eigenvalues satisfy λi≥(γN)−1\lambda_i \ge(\gamma N)^{-1} (k∗=dk^* = d and Hk∗:∞=0\mathbf{H}_{k^*:\infty} = 0), (1) predicts a polynomial rate O(d/(γN2))O(d/(\gamma N^2)) instead of exponential burn-in decay [14]. This looseness arises because prior upper-bound analyses drop the deterministic burn-in contraction acting on multiplicative gradient fluctuations after they are excited. Retaining the exact burn-in propagation shows that the single-hop (i≤k∗,j≤k∗i \le k^*, j \le k^*) contribution is exponentially damped in ss through (I−γH)s(w0−w∗)(\mathbf{I} - \gamma\mathbf{H})^s(\mathbf{w}_0 - \mathbf{w}^*) and a burn-in cross-spectral convolution (Theorems 4.1 and 4.2), while multi-hop feedback (including energy that scatters into slow modes i>k∗i > k^* and subsequently returns to fast modes) is absorbed into the total excess risk whenever our spectral feedback condition χs,N≤χ0<1\chi_{s,N} \le\chi_0 < 1 holds.

  1. Looseness in the Lower Bound (Burn-In Head-to-Tail Transfer): Conversely, whenever slow spectral modes i>k∗i > k^* exist (k∗<dk^* < d), the cross-interaction between the initial head error term (γN)−1∥w0−w∗∥0:k†2(\gamma N)^{-1}\|\mathbf{w}_0 - \mathbf{w}^*\|^2_{0:k^\dagger} and the slow-spectrum factor Nγ2∑i>k∗λi2N\gamma^2\sum_{i>k^*}\lambda_i^2 cannot be removed from the total-risk upper bound; instead, it is a genuine lower bound contribution missing from (2). During the first Θ(1/(γλj))\Theta(1/(\gamma\lambda_j)) steps of the burn-in phase, an initial error component along a fast eigenvector vj\mathbf{v}_j (j≤k†j \le k^\dagger) undergoes multiplicative gradient fluctuations (xtxtT−H)(wt−1−w∗)(\mathbf{x}_t\mathbf{x}_t^{\mathsf T} - \mathbf{H})(\mathbf{w}_{t-1} - \mathbf{w}^*). Under Assumption 3.4, this process scatters fourth-moment energy proportional to βγ∥w0−w∗∥0:k†2H\beta\gamma\|\mathbf{w}_0 - \mathbf{w}^*\|^2_{0:k^\dagger}\mathbf{H} across all eigendirections of H\mathbf{H}. While the single-hop energy scattered into fast modes (i≤k∗i \le k^*) decays over the remaining burn-in steps, the energy scattered into slow modes (i>k†i > k^\dagger, where λi<(γ(s+N))−1\lambda_i < (\gamma(s+N))^{-1}) experiences negligible contraction (1−γλi)2(s−1−t)≥e−2(1-\gamma\lambda_i)^{2(s-1-t)} \ge e^{-2} and survives undamped into the averaging window—even in two-dimensional noiseless Gaussian regression (Proposition 4.7(1)).

Main Contributions. Our main contributions are summarized as follows (see Table 1 in Section 4.3 for a detailed term-by-term comparison with Zou et al. [37]):

References

  1. [1]Bach, F. and Moulines, E. (2013). Non-strongly-convex smooth stochastic approximation with convergence rate \(O(1/n)\). In Advances in Neural Information Processing Systems (NeurIPS), vol. 26.
  2. [2]Bartlett, P. L., Long, P. M., Lugosi, G. and Tsigler, A. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences 117 30063–30070.DOI
  3. [3]Belkin, M., Hsu, D. and Xu, J. (2020). Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science 2 1167–1180.DOI
  4. [4]Berthier, R., Bach, F. and Gaillard, P. (2020). Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. In Advances in Neural Information Processing Systems (NeurIPS), vol. 33.arxiv.org/abs/2006.08212
  5. [5]Caponnetto, A. and De Vito, E. (2007). Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics 7 331–368.DOI
  6. [6]Chatterji, N. S. and Long, P. M. (2021). Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research 22 1–30.arxiv.org/abs/2004.12019
  7. [7]Défossez, A. and Bach, F. (2015). Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS).arxiv.org/abs/1412.0156
  8. [8]Dieuleveut, A. and Bach, F. (2016). Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics 44 1363–1399.DOI
  9. [9]Dieuleveut, A., Flammarion, N. and Bach, F. (2017). Harder, better, faster, stronger convergence rates for least-squares regression. Journal of Machine Learning Research 18 1–51.
  10. [11]Hastie, T., Montanari, A., Rosset, S. and Tibshirani, R. J. (2022). Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics 50 949–986.DOI
  11. [12]Hsu, D., Kakade, S. M. and Zhang, T. (2014). Random design analysis of ridge regression. Foundations of Computational Mathematics 14 569–600.
  12. [13]Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., Pillutla, V. K. and Sidford, A. (2017a). A Markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint arXiv:1710.09430 .DOI
  13. [14]Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P. and Sidford, A. (2018). Accelerating stochastic gradient descent for least squares regression. In Proceedings of the 31st Conference on Learning Theory (COLT). PMLR.arxiv.org/abs/1704.08227
  14. [15]Jain, P., Netrapalli, P., Kakade, S. M., Kidambi, R. and Sidford, A. (2017b). Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research 18 1–42.arxiv.org/abs/1610.03774
  15. [16]Kaddour, J. (2022). Stop wasting my time! Saving days of ImageNet and BERT training with latest weight averaging. arXiv preprint arXiv:2209.14981.arxiv.org/abs/2209.14981
  16. [17]Lakshminarayanan, C. and Szepesvári, C. (2018). Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR.
  17. [20]Li, X. and Gu, Q. (2025). Understanding SGD with exponential moving average: A case study in linear regression. arXiv preprint arXiv:2502.14123.arxiv.org/abs/2502.14123
  18. [21]Lin, L., Wu, J., Kakade, S. M., Bartlett, P. L. and Lee, J. D. (2024). Scaling laws in linear regression: Compute, parameters, and data. In Advances in Neural Information Processing Systems (NeurIPS), vol. 37. ArXiv preprint arXiv:2406.08466.arxiv.org/abs/2406.08466
  19. [22]Meterez, A., Morwani, D., Oncescu, C.-A., Wu, J., Pehlevan, C. and Kakade, S. M. (2025). A simplified analysis of SGD for linear regression with weight averaging. arXiv preprint arXiv:2506.15535.arxiv.org/abs/2506.15535
  20. [23]Meterez, A., Nair, P. A., Morwani, D., Pehlevan, C. and Kakade, S. M. (2026). Any-time pretraining: Horizon-free learning-rate schedules with weight averaging. arXiv preprint arXiv:2602.03702.arxiv.org/abs/2602.03702
  21. [24]Muthukumar, V., Narang, A., Subramanian, V., Belkin, M., Hsu, D. and Sahai, A. (2020). Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory 1 67–83.arxiv.org/abs/1903.09139
  22. [25]Nemirovski, A., Juditsky, A., Lan, G. and Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization 19 1574–1609.DOI
  23. [26]Paquette, C., Lee, K., Pedregosa, F. and Paquette, E. (2021). SGD in the large: Average-case analysis, asymptotics, and stepsize criticality. In Proceedings of the 34th Conference on Learning Theory (COLT). PMLR.arxiv.org/abs/2102.04396
  24. [27]Paquette, C., Paquette, E., Adlam, B. and Pennington, J. (2022). Implicit regularization or implicit conditioning? Exact risk trajectories of SGD in high dimensions. In Advances in Neural Information Processing Systems (NeurIPS), vol. 35.arxiv.org/abs/2206.07252
  25. [28]Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization 30 838–855.DOI
  26. [29]Rakhlin, A., Shamir, O. and Sridharan, K. (2012). Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Conference on Machine Learning (ICML).DOI
  27. [30]Robbins, H. and Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics 22 400–407.
  28. [31]Ruppert, D. (1988). Efficient estimations from a slowly convergent Robbins–Monro process. Technical Report 781, Cornell University Operations Research and Industrial Engineering.
  29. [32]Sanyal, S., Neerkaije, A., Kaddour, J., Kumar, A. and Sanghavi, S. (2023). Early weight averaging meets high learning rates for LLM pre-training. arXiv preprint arXiv:2306.03241.arxiv.org/abs/2306.03241
  30. [33]Tsigler, A. and Bartlett, P. L. (2023). Benign overfitting in ridge regression. Journal of Machine Learning Research 24 1–76.
  31. [34]Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.
  32. [37]Zou, D., Wu, J., Braverman, V., Gu, Q. and Kakade, S. M. (2021). Benign overfitting of constant-stepsize SGD for linear regression. In Proceedings of the 34th Conference on Learning Theory (COLT). PMLR. Full version: arXiv preprint arXiv:2103.12692.arxiv.org/abs/2103.12692

Paper details

vlnc:W_g89q3jkw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra, Gemini 4 Argon

View statement
Looking for related papers…
Contents