Two models of double descent for weak features

By Mikhail Belkin, Daniel J. Hsu, Ji Xu. 2019

413 citations recorded by the source corpus.

The "double descent" risk curve was recently proposed to qualitatively describe the out-of-sample prediction accuracy of variably-parameterized machine learning models. This article provides a precise mathematical analysis for the shape of this curve in two simple data models with the least squares/least norm predictor. Specifically, it is shown that the risk peaks when the number of features $p$ is close to the sample size $n$, but also that the risk decreases towards its minimum as $p$ increases beyond $n$. This behavior is contrasted with that of "prescient" models that select features in an a priori optimal order.

Subfields: Artificial Intelligence, Statistics and Probability, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Scaling & Learning Theory

Citations in the corpus

Scaling description of generalization with number of parameters in deep learning (2019, background): “2) [37, 38, 39] and on the asymptotic behavior of wide networks [40, 41, 42, 43].”
Deep double descent: where bigger models and more data hurt (2019, methodology): “A growing list of papers that theoretically analyze it in the tractable setting of linear least squares regression includes Belkin et al. (2019); Hastie et al. (2019); Bartlett et al. (2019); Muthukumar et al. (2019); Bibas et al. (2019); Mitra (2019); Mei & Montanari (2019).”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “An interesting line of work establish connection between kernel methods and neural networks and study the generalization abilities of kernel methods when the model interpolates the training data [19, 10, 11, 12, 38, 13].”
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation (2020, background): “Another line of research focuses on the generalization error of algorithms that fit the data perfectly (referred to as interpolating) [29, 10, 8, 20, 9, 25, 5, 7, 14, 21].”
Does learning require memorization? a short tale about a long tail (2019, methodology): “[8] shows empirically and also on simple synthetic models [9] that classical bias-variance trade-”
A jamming transition from under- to over-parametrization affects generalization in deep learning (2018, background): “Further theoretical studies on regression showed a precise mathematical description of the cusp behaviour in [30, 31, 32], albeit on models that are practically somewhat further away from modern neural networks.”
Benign overfitting in linear regression (2019, background): “diction rule with minimal expected squared error. After this work was presented at the NAS Colloquium on the Science of Deep Learning [2], we became aware of the concurrent work of Belkin, Hsu and Xu [6] and of Hastie, Montanari, Rosset and Tibshirani [13]. Belkin et al [6] calculated the excess ris”
Lightlike Neuromanifolds, Occam's Razor and Deep Learning (2019, background): “However, the empirical generalisation performance on a testing set resembles a double descent risk curve [6, 7], which goes down, up and down again as the number of free parameters increases from zero.”
Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, background): “In the wake of understanding the limitations of classical statistical learning approaches [8, 9, 10] this direction is witnessing a renewal of interest [11, 12, 10, 13, 10, 14, 15].”
Classification vs regression in overparameterized regimes: Does the loss function matter? (2020, background): “[8] Mikhail Belkin, Daniel Hsu, and Ji Xu.”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, background): “…statistical models can display \/\-shaped ( double descent ) risk curves as a function of model complexity, extending the classical U-shaped risk curves and having small or even the smallest risk in the overparametrized regime (Advani et al., 2020; Spigler et al., 2019; Belkin et al., 2019a).”
: "Statistical Modeling: The Two Cultures" (Statistical Science, 2001, 16(3), 199-231) (neutral): “…can now theoretically also be prescribed to over-parametrized learning regimes, where the number of nodes and edges is required to be far greater than the number of samples; the number of layers seems secondary to the sheer number of the weight parameters (Ma et al., 2018; Belkin et al., 2020).”
Finite Depth and Width Corrections to the Neural Tangent Kernel (2019, result): “Assuming this trajectory turns out to be data-dependent, our results suggest that the double descent curve [1, 2, 21] that trades oﬀ complexity vs. generalization error may display signiﬁcantly diﬀerent behaviors depending on the mode of network overparameterization.”
Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2019, neutral): “1 Proof of Theorem 8 The proof follows the approach developed by Cheng and Singer (2013) to determine the asymptotic spectral measure of symmetric kernel random matrices.”
Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited (2020, methodology): “(1989) and Bös et al. (1993) introduced the idea that generalization capability can be non-monotonic for neural networks in terms of the number of parameters (e.”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “Thus what we conclude is that in our studied asymptotic limit, the mechanism that provably gives rise to double descent from previous works Hastie et al. (2019); Belkin et al. (2019) might not translate to optimizing two-layer neural networks.”
The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve (2019, methodology): “The same papers also compute the double descent curve within other models, including over-specified linear model [HMRT19], and a Fourier series model [BHX19].”
The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization (2020, background): “Bubeck et al. [2019] study a binary classification problem under a statistical query setting and show that to train a robust classifier one need exponentially (in dimension d) many queries, while only polynomially many to train a standard one. As discussed in Section 1, the main difference between t”