On the Role of Optimization in Double Descent: A Least Squares Study

Ilja Kuzborskij, Csaba Szepesvari, Omar Rivasplata, Amal Rannen-Triki, Razvan Pascanu

TL;DR

While the "double descent" phenomenon is often studied through the lens of analytic pseudo-inverse solutions, this paper demonstrates that the optimization process itself—specifically Gradient Descent—plays a crucial role. By analyzing the learning dynamics of least squares, the authors prove that excess risk is tightly controlled by the smallest non-zero eigenvalue of the feature covariance matrix. This eigenvalue naturally exhibits a U-shaped behavior that drives the double descent curve, even in completely noise-free settings.

What Problem Does This Paper Address?

In classical machine learning, we are taught that making a model too large for the available data leads to overfitting, resulting in a U-shaped test error curve. However, modern deep learning consistently contradicts this: massively overparameterized neural networks often generalize better as they scale. The "double descent" (DD) phenomenon reconciles this by showing that test error peaks at the interpolation threshold (where model size equals data size) and then descends again as the model grows further.

To understand why this happens, theorists have heavily studied linear least squares models. However, virtually all prior work has focused on the analytic Moore-Penrose pseudo-inverse solution. This ignores the actual optimization process—Gradient Descent (GD)—used to train real models. This paper bridges that gap by asking: How do the finite-time learning dynamics of Gradient Descent contribute to the double descent phenomenon?

Methods

The authors conduct a rigorous theoretical analysis of Gradient Descent applied to the least squares objective. Instead of looking at asymptotic or analytic solutions, they derive finite-time excess risk bounds for GD iterates.

Their approach hinges on tracking how the algorithm converges along the low-dimensional subspace spanned by the eigenvectors of the sample covariance matrix. They utilize random matrix theory (specifically, non-asymptotic extensions of the Bai-Yin law) to analyze the concentration of the smallest non-zero eigenvalue ($\lambda_{min}^+$) of this covariance matrix.

Finally, to see if their linear theory provides intuition for non-linear deep learning, they empirically evaluate shallow Multi-Layer Perceptrons (MLPs). They treat the final layer as a least squares problem and analyze the covariance spectrum of the intermediary hidden layer activations during training.

Datasets

  • Synthetic Data: Used to validate the theoretical bounds for linear regression under controlled noise and initialization conditions.
  • MNIST & FashionMNIST: Used for the empirical exploration of neural networks, specifically training MLPs on 1,000-sample subsets to easily observe the interpolation threshold.

Key Insights and Ideas

  • Optimization drives Double Descent in noise-free settings: In a perfectly noiseless linear regression scenario, the double descent curve is caused solely by optimization dynamics. The convergence rate of GD is bottlenecked by $\lambda_{min}^+$. Because $\lambda_{min}^+$ dips severely at the interpolation threshold, optimization slows down drastically, causing a spike in finite-time excess risk.
Excess risk and optimization error across feature dimensions showing the double descent peak.
  • Label noise amplifies the peak: When label noise is introduced, the excess risk bound gains a generalization error term that scales with $(\lambda_{min}^+)^{-2}$. This means the more noise in the dataset, the more aggressively the model fits that noise at the interpolation threshold, resulting in a much larger double descent peak.
  • The Bai-Yin Law explains the shape: Random matrix theory dictates that as the ratio of features to data points ($d/n$) approaches 1, the smallest non-zero eigenvalue approaches zero. As the model becomes highly overparameterized ($d \gg n$), $\lambda_{min}^+$ grows again, improving the conditioning of the problem and driving the "second descent."
  • Neural networks mimic this behavior internally: In empirical tests on MLPs, the $\lambda_{min}^+$ of the hidden layer features exhibits the exact same U-shaped dip at the interpolation threshold as predicted by the linear theory. Furthermore, architectural bottlenecks (like a narrow hidden layer) permanently worsen this conditioning, exacerbating the test error peak.

Key Results

  • Noise-Free Bound: The authors prove that the excess risk of GD is bounded by a term proportional to $(1 - \alpha \lambda_{min}^+)^{2T}$, where $\alpha$ is the learning rate and $T$ is the number of steps. This explicitly links the optimization error to the spectrum of the data.
  • Noisy Bound: With label variance $\sigma^2$, an additional term scaling with $4(\sigma^2/n)(\lambda_{min}^+)^{-2}$ appears, perfectly capturing the classic bias-variance trade-off spike at the interpolation threshold.
  • Empirical Alignment: When training an MLP on 1,000 MNIST examples, the test error peaks exactly when the hidden layer width reaches ~1,000 units. Simultaneously, the $\lambda_{min}^+$ of the hidden layer activations hits its absolute minimum, confirming the theoretical link between feature conditioning and the DD peak in practical architectures.
Test error and minimum eigenvalue dynamics for MNIST and FashionMNIST, demonstrating the correlation between eigenvalue dips and error peaks.

Limitations and Future Work

  • Linearity of Theory: The formal proofs are restricted to the linear least squares setting. While the empirical results on MLPs are compelling, the paper does not provide a rigorous mathematical proof for non-linear neural networks.
  • Future Work - NTK Connection: The authors suggest that adapting these results to deep learning could be achieved via the Neural Tangent Kernel (NTK) framework, which would require new concentration bounds for the NTK random feature covariance matrix.
  • Future Work - Architectural Impacts: The paper conjectures that different architectural choices (depth vs. width, skip connections, batch normalization) fundamentally alter double descent by changing the distribution of $\lambda_{min}^+$ in intermediary layers. Disentangling these factors is a prime target for future research.

Summary updated

Abstract

Empirically it has been observed that the performance of deep neural networks steadily improves with increased model size, contradicting the classical view on overfitting and generalization. Recently, the double descent phenomenon has been proposed to reconcile this observation with theory, suggesting that the test error has a second descent when the model becomes sufficiently overparameterized, as the model size itself acts as an implicit regularizer. In this paper we add to the growing body of work in this space, providing a careful study of learning dynamics as a function of model size for the least squares scenario. We show an excess risk bound for the gradient descent solution of the least squares objective. The bound depends on the smallest non-zero eigenvalue of the sample covariance matrix of the input features, via a functional form that has the double descent behaviour. This gives a new perspective on the double descent curves reported in the literature, as our analysis of the excess risk allows to decouple the effect of optimization and generalization error. In particular, we find that in the case of noiseless regression, double descent is explained solely by optimization-related quantities, which was missed in studies focusing on the Moore-Penrose pseudoinverse solution. We believe that our derivation provides an alternative view compared to existing works, shedding some light on a possible cause of this phenomenon, at least in the considered least squares setting. We empirically explore if our predictions hold for neural networks, in particular whether the spectrum of the sample covariance of features at intermediary hidden layers has a similar behaviour as the one predicted by our derivations in the least squares setting.
BibTeX
@inproceedings{kuzborskij2021role,
  author = {Ilja Kuzborskij and Csaba Szepesvari and Omar Rivasplata and Amal Rannen-Triki and Razvan Pascanu},
  title = {{On the Role of Optimization in Double Descent: A Least Squares Study}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=32eyjxaRxp},
}
Figure