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.
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