Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime

Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Sham M. Kakade

Abstract: Stochastic gradient descent (SGD) has achieved great success due to its superior performance in both optimization and generalization. Most of existing generalization analyses are made for single-pass SGD, which is a less practical variant compared to the commonly-used multi-pass SGD. Besides, theoretical analyses for multi-pass SGD often concern a worst-case instance in a class of problems, which may be pessimistic to explain the superior generalization ability for some particular problem instance. The goal of this paper is to sharply characterize the generalization of multi-pass SGD, by developing an instance-dependent excess risk bound for least squares in the interpolation regime, which is expressed as a function of the iteration number, stepsize, and data covariance. We show that the excess risk of SGD can be exactly decomposed into the excess risk of GD and a positive fluctuation error, suggesting that SGD always performs worse, instance-wisely, than GD, in generalization. On the other hand, we show that although SGD needs more iterations than GD to achieve the same level of excess risk, it saves the number of stochastic gradient evaluations, and therefore is preferable in terms of computational time.

Introduction

In modern machine learning, models are frequently "overparameterized," possessing more parameters ($d$) than training points ($n$). In this interpolation regime, models can achieve zero training error. While Stochastic Gradient Descent (SGD) is the standard optimization tool, theoretical understanding has largely lagged behind practice. Most existing guarantees focus on "single-pass" SGD, whereas practitioners almost exclusively use "multi-pass" variants. Furthermore, traditional "worst-case" analyses often fail to capture the nuances of specific problem instances. This work addresses these gaps by providing a sharp, instance-dependent characterization of multi-pass SGD generalization in the interpolation regime for least squares regression.

Methodology

The study focuses on least squares regression under the assumption of perfect data interpolation. The authors employ several novel analytical techniques:

  1. Risk Decomposition: Proving that SGD's excess risk is the sum of GD's risk and a "fluctuation error" stemming from gradient variance.
  2. Operator Methods: Developing tensor operator methods to track error covariance based on the empirical data distribution, facilitating the analysis of multi-pass sampling (with replacement).
  3. Ridge Regression Connection: Relating early-stopped GD performance to ridge regression bounds to leverage sophisticated tools from statistical learning theory.

To validate these theoretical findings, numerical simulations were conducted on synthetic linear tasks where features follow specific covariance spectra (e.g., $\lambda_i = i^{-2}$ or $\lambda_i = i^{-1} \log^{-2}(i+10)$). These experiments utilized overparameterized settings, such as $d=256$ and $n=128$.

Theoretical Insights and Results

The core contribution of this research is the exact decomposition of excess risk:

$$ExcessRisk(SGD) = ExcessRisk(GD) + FluctuationError$$

where the fluctuation error is strictly positive. This leads to several key insights:

  • GD as the Generalization Benchmark: For any fixed stepsize and iteration count, GD consistently achieves lower excess risk than SGD. The stochasticity inherent in SGD introduces a persistent error that hinders generalization performance on a per-iteration basis.
  • The Computational Efficiency Paradox: Despite GD's superior generalization per iteration, it is computationally expensive as it processes all $n$ points per step. The analysis reveals that to reach a target risk level, SGD requires significantly more iterations (e.g., $O(n^{1.5})$ for SGD vs $O(n)$ for GD when the spectrum decays slowly), but saves a factor of roughly $\sqrt{n}$ in total gradient evaluations. For a polynomially decaying spectrum $i^{-(1+r)}$, SGD reduces the number of required stochastic gradient evaluations by a factor of $\tilde{O}(n^{\min\{0.5, 1/(r+1)\}})$.
  • Stepsize and Overfitting: SGD requires significantly smaller stepsizes than GD to prevent the fluctuation error from diverging. The results also support the "benign overfitting" hypothesis, showing that noise can be effectively distributed across many unimportant dimensions in high-dimensional settings.
Numerical verification of risk bounds for GD and SGD across different learning rates and eigenvalue decay spectra.

As shown in the figure above, the dashed lines (GD) consistently lie below the solid lines (SGD) of the same color, confirming that GD generalizes better per iteration. The gap between the solid and dashed lines represents the "fluctuation error."

Conclusion and Limitations

This work provides a rigorous framework for understanding multi-pass SGD in the interpolation regime. However, certain limitations remain. The analysis assumes sampling with replacement, whereas "shuffling without replacement" is more common in practice but harder to model. Additionally, the findings are currently limited to linear least squares models. Extending these instance-dependent bounds to non-convex losses and deep neural networks remains a significant direction for future research. Finally, the assumption of a Gaussian prior on ground-truth weights, while technically convenient, is a constraint the authors aim to relax in future iterations.

Summary updated

Abstract

Stochastic gradient descent (SGD) has achieved great success due to its superior performance in both optimization and generalization. Most of existing generalization analyses are made for single-pass SGD, which is a less practical variant compared to the commonly-used multi-pass SGD. Besides, theoretical analyses for multi-pass SGD often concern a worst-case instance in a class of problems, which may be pessimistic to explain the superior generalization ability for some particular problem instance. The goal of this paper is to sharply characterize the generalization of multi-pass SGD, by developing an instance-dependent excess risk bound for least squares in the interpolation regime, which is expressed as a function of the iteration number, stepsize, and data covariance. We show that the excess risk of SGD can be exactly decomposed into the excess risk of GD and a positive fluctuation error, suggesting that SGD always performs worse, instance-wisely, than GD, in generalization. On the other hand, we show that although SGD needs more iterations than GD to achieve the same level of excess risk, it saves the number of stochastic gradient evaluations, and therefore is preferable in terms of computational time.
BibTeX
@inproceedings{zou2022risk,
  author = {Difan Zou and Jingfeng Wu and Vladimir Braverman and Quanquan Gu and Sham M. Kakade},
  title = {{Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=f966GJIEF9},
}
Figure