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

Ilja Kuzborskij, Csaba Szepesvári, Omar Rivasplata, Amal Rannen Triki, Razvan Pascanu

Abstract

Empirically, it has been observed that the performance of deep neural networks steadily improves as model size increases, contradicting classical views on overfitting. The "double descent" phenomenon has been proposed to reconcile this, suggesting that test error descends a second time in the overparameterized regime. This paper provides a careful study of learning dynamics for the least squares scenario, showing that the double descent curve is fundamentally driven by the optimization process. We derive an excess risk bound for the gradient descent solution that depends on the smallest non-zero eigenvalue of the feature covariance matrix. Our analysis allows us to decouple optimization and generalization error, revealing that in noiseless regression, double descent is explained solely by optimization-related quantities.

Introduction

In classical machine learning, the bias-variance tradeoff predicts a U-shaped test error curve: as model complexity increases, the model eventually overfits the training data, leading to poor generalization. However, modern deep learning models often exhibit a "double descent" (DD) behavior. As the number of parameters grows, the test error first follows the classical U-shape, peaks at the "interpolation threshold" (where the number of parameters equals the number of data points), and then descends again as the model becomes massively overparameterized.

While many theoretical explanations for DD focus on the properties of the minimum-norm solution (the Moore-Penrose pseudoinverse), this paper argues that the actual optimization trajectory of Gradient Descent (GD) is a critical, often overlooked factor. By analyzing the dynamics of GD, the authors show that the peak at the interpolation threshold is largely a consequence of the optimization landscape becoming ill-conditioned.

Theoretical Framework: The Eigenvalue Connection

The core of the paper's theoretical contribution is an excess risk bound for the GD solution of a least squares objective. The authors demonstrate that the excess risk is heavily controlled by the spectrum of the sample covariance matrix, specifically its smallest non-zero eigenvalue, denoted as $\lambda_{min}^+$.

As the number of features ($d$) approaches the number of training examples ($n$), the geometry of the optimization landscape changes. Using non-asymptotic random matrix theory, the authors show that $\lambda_{min}^+$ drops dramatically near the interpolation threshold ($d \approx n$). Because the convergence rate of Gradient Descent is determined by the conditioning of the covariance matrix, a very small $\lambda_{min}^+$ leads to extremely slow convergence.

This grid of plots illustrates how excess risk and optimization error evolve across feature dimensions for different iteration counts ($T$). The peak at the interpolation threshold is driven by the optimization error, which becomes more pronounced as the landscape becomes ill-conditioned.

The derived bound scales with $(1 - \alpha \lambda_{min}^+)^{2T}$, where $\alpha$ is the learning rate and $T$ is the number of iterations. This formula explicitly links the optimization time to the double descent curve: if $T$ is not large enough to compensate for a tiny $\lambda_{min}^+$, the optimization error spikes, creating the characteristic peak in the test error.

Empirical Evidence and Neural Networks

To validate their theory, the authors conducted experiments on both synthetic data and standard image datasets like MNIST and FashionMNIST. In the synthetic setting, they confirmed that the double descent peak in excess risk perfectly mirrors the U-shaped dip in $\lambda_{min}^+$.

In the neural network experiments, they trained Multi-Layer Perceptrons (MLPs) with varying widths on subsampled versions of MNIST ($n=1,000$). By treating the final layer as a least squares problem, they measured the $\lambda_{min}^+$ of the intermediary hidden activations throughout training. They found that:

  • The Peak is Real: Test error peaked exactly when the hidden layer width reached the number of training samples.
  • Conditioning Matters: At this same threshold, the $\lambda_{min}^+$ of the hidden features plummeted, confirming that the optimization difficulties predicted by their linear theory also occur in non-linear deep networks.
  • Architectural Mitigations: The study also explored how architecture affects conditioning. They found that extreme depth and bottlenecks crash $\lambda_{min}^+$, while skip connections (Residual Networks) help maintain a healthy eigenvalue profile, effectively smoothing out the optimization landscape and reducing the double descent peak.

Conclusion

This research shifts the perspective on double descent from a purely generalization-based phenomenon to one deeply rooted in optimization dynamics. By showing that the "interpolation peak" is often a result of slow convergence due to ill-conditioning, the authors provide a new lens through which to understand why certain architectures and optimization strategies generalize better than others. Future work will likely focus on how other common deep learning components, such as normalization layers and different loss functions, interact with the feature covariance spectrum to influence the double descent curve.

Summary updated

Abstract

Empirically it has been observed that the performance of deep neural networks steadily improves as we increase model size, contradicting the classical view on overfitting and generalization. Recently, the double descent phenomena 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 covariance matrix of the input features, via a functional form that has the double descent behavior. This gives a new perspective on the double descent curves reported in the literature. Our analysis of the excess risk allows to decouple the effect of optimization and generalization error. In particular, we find that in 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 work, shedding some light on a possible cause of this phenomena, at least in the considered least squares setting. We empirically explore if our predictions hold for neural networks, in particular whether the covariance of intermediary hidden activations has a similar behavior as the one predicted by our derivations.
BibTeX
@inproceedings{kuzborskij2021role,
  author = {Ilja Kuzborskij and Csaba Szepesvári 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