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