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

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

Introduction

In modern machine learning, models often operate in the interpolation regime, where they possess more parameters than training data points and can achieve zero training error. While Stochastic Gradient Descent (SGD) is the standard tool for training these models, most theoretical analysis focuses on "single-pass" SGD (using each data point only once).

In practice, practitioners rely on multi-pass SGD, running many epochs over the same data. Existing theories for multi-pass SGD often provide "worst-case" bounds that fail to explain why the algorithm performs so well on specific, real-world data distributions. Furthermore, it has remained unclear how the generalization ability of SGD fundamentally differs from its deterministic counterpart, Gradient Descent (GD), when both can fit the training data perfectly. This paper provides a new theoretical framework to understand why multi-pass SGD generalizes well in overparameterized models, specifically for least squares regression.

Exact Risk Decomposition: SGD as "Noisy GD"

The authors employ operator methods to track the evolution of the "empirical error matrix" during training. A key technical breakthrough in this paper is the Exact Risk Decomposition. The authors mathematically prove that the excess risk of SGD can be split into two distinct parts:

  1. The risk of GD (using the same step size and iterations).
  2. A non-negative "fluctuation error" caused by the randomness of picking individual samples.

This decomposition ($\mathbb{E}_{SGD}[\mathcal{E}(\mathbf{w}_t)] = \mathcal{E}(\hat{\mathbf{w}}_t) + \text{FluctuationError}(\mathbf{w}_t)$) proves that for any given iteration and step size, GD will always have a lower (or equal) excess risk than SGD. The fluctuation error introduced by stochasticity is always a penalty to generalization on a per-step basis.

Risk evolution over steps for GD and SGD under different data covariance eigenspectrums.

Interestingly, in the "benign overfitting" regime—where noise is effectively hidden in low-variance dimensions—this fluctuation error actually vanishes as the number of iterations goes to infinity. This explains why running SGD for many epochs doesn't necessarily destroy generalization.

The Computational Trade-off

If GD always achieves better risk per iteration, why use SGD? The answer lies in computational efficiency. While GD is better "per iteration," it is computationally expensive because it calculates $n$ gradients per step. SGD only calculates one.

The authors provide an instance-dependent analysis, expressing their bounds as a function of the eigenspectrum of the data covariance matrix. This allows the theory to adapt to the specific "shape" of the data. They formalize a critical computational trade-off:

  • Iteration Complexity: To reach optimal risk, SGD requires more iterations than GD. For a polynomial data decay rate $r$, SGD needs roughly $\tilde{O}(n^{\max\{0.5, \frac{r}{r+1}\}})$ more iterations.
  • Gradient Complexity: Despite needing more steps, SGD is significantly faster overall. It requires $\tilde{O}(n^{\min\{0.5, \frac{1}{r+1}\}})$ fewer total stochastic gradient evaluations than GD to achieve the same generalization performance.
Comparison of Iteration Complexity and Gradient Complexity vs. Risk for GD and SGD.

Limitations and Future Directions

While this framework provides a clean lens through which to view the "cost of randomness" in optimization, it has limitations. The current analysis assumes SGD samples data with replacement, whereas practical implementations typically use shuffling (sampling without replacement). Additionally, the results are specific to least squares (linear regression) and primarily focus on constant stepsizes. Extending these instance-dependent bounds to non-linear neural networks and practical learning rate schedules remains an important challenge for future work.

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 provide an instance-dependent excess risk bound of multi-pass SGD 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