Surprises in High-Dimensional Ridgeless Least Squares Interpolation
By Trevor J. Hastie, Andrea Montanari, Saharon Rosset, Robert Tibshirani. 2019
892 citations recorded by the source corpus.
Interpolators—estimators that achieve zero training error—have attracted growing attention in machine learning, mainly because state-of-the art neural networks appear to be models of this type. In this paper, we study minimum ℓ2 norm (“ridgeless”) interpolation least squares regression, focusing on the high-dimensional regime in which the number of unknown parameters p is of the same order as the number of samples n. We consider two different models for the feature distribution: a linear model, where the feature vectors xi∈ℝp are obtained by applying a linear transform to a vector of i.i.d. entries, xi = Σ1/2zi (with zi∈ℝp); and a nonlinear model, where the feature vectors are obtained by passing the input through a random one-layer neural network, xi = φ(Wzi) (with zi∈ℝd, W∈ℝp×d a matrix of i.i.d. entries, and φ an activation function acting componentwise on Wzi). We recover—in a precise quantitative way—several phenomena that have been observed in large-scale neural networks and kernel machines, including the “double descent” behavior of the prediction risk, and the potential benefits of overparametrization.
Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics, 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 Computational Mechanics
- Robert Tibshirani
- Percy Liang
- John C. Duchi
- Trevor J. Hastie
- Tengyu Ma
- Christopher R'e
- Florent Krzakala
- Lenka Zdeborov'a
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Jitendra Malik
- Ming-Hsuan Yang
- Xiaogang Wang
- Andrew Zisserman
- Bernt Schiele
In Mathematical Physics
- Vitaly Feldman
- E.J. Candes
- M. Soltanolkotabi
- Percy Liang
- Lucas K. Mentch
- Xialiang Dou
- Siyu Zhou
- Tengyuan Liang
In Scaling & Learning Theory
- Matthieu Wyart
- Mario Geiger
- Stefano Spigler
- Vitaly Feldman
- Tengyu Ma
- Arthur Jacot
- Greg Yang
- Jaehoon Lee
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): “Hastie et al. (2019) highlight that when the model is misspecified, the minimum of training error can occur for over-parameterized models 2.”
- 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): “Recent wave of interest in such methods has lead to new analyses of existing interpolating methods as well new algorithmic techniques [WOBM17; BRT18; BHM18; LR18; BMM18; RZ18; RZ19; BLLT19; BHX19; HMRT19; MVS19].”
- Benign overfitting in linear regression (2019, background): “ter 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 risk for certain linear models (a regression problem wi”
- Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits (2019, methodology): “The following result establishes the connections between the solution of gradient descent on neural networks (at local stationarity), and the kernel ridgeless regression (Belkin, Ma, and Mandal 2018; Liang and Rakhlin 2018; Hastie et al. 2019) with an adaptive kernel Ĥλ∞.”
- Precise Tradeoffs in Adversarial Training for Linear Regression (2020, background): “It is known that the plot of standard risk as a function of number of model complexity (1/δ = p/n) exhibits a so-called ‘double-descent’ behavior Belkin et al. (2018b,a); Hastie et al. (2019).”
- Dash: Semi-Supervised Learning with Dynamic Thresholding (2021, background): “Please note that this is a common property observed in training deep neural networks [Zhang et al., 2017, Allen-Zhu et al., 2019, Du et al., 2019, Arora et al., 2019, Chizat et al., 2019, Hastie et al., 2019, Yun et al., 2019].”
- Getting Better from Worse: Augmented Bagging and a Cautionary Tale of Variable Importance (2020, methodology): “The form of this covariance corresponds to that utilized frequently in the recent work by Mentch and Zhou (2019) and to the ‘beta-type 2’ setup utilized in Hastie et al. (2017). The original data was chosen to include n = 100 observations, p = 5 original signal features with β1 = · · · = β5 = 1, and”
- Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited (2020, background): “Dobriban & Wager (2018) and Hastie et al. (2019) have extensively studied over-parameterized ridge regression.”
- The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, methodology): “Similarly, Dobriban and Wager (2018) and later Hastie et al. (2019) proved that λ opt > 0 for any Σ in the asymptotic p, n → ∞ case while p/n = γ , based on the assumption that β is randomly oriented.”
- Cross-validation: what does it estimate and how well does it do it? (2021, background): “This quantity is also considered by Hastie et al. (2019) in a high-dimensional regression setting, but to the best of our knowledge has not been considered in the literature on estimation of prediction error.”
- Explaining neural scaling laws (2021, background): “In the supplement, we provide an in-depth derivation of this behavior and expressions for the leading contributions to L ( D, P ) − L ( P ) and L ( D, P ) − L ( D ).”
- On the Generalization Effects of Linear Transformations in Data Augmentation (2020, positive): “To gain insight into the effects of linear transformations, we consider a conceptually simple over-parametrized model proposed in Bartlett et al. (2019); Xie et al. (2020); Hastie et al. (2019) that captures the need to add more data as in image settings.”
- Dataset Meta-Learning from Kernel Ridge-Regression (2020, background): “Interestingly enough, we observe non-monotonicity for the linear kernel, owing to double descent phenomenon Hastie et al. (2019).”
- Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, methodology): “This model has seen a surge of interest recently, and a sharp asymptotic analysis was provided in the particular case of uncorrelated Gaussian data x ∼ N (0, ID) and φt = id in [11, 12] for ridge regression and generalised by [42, 44] for generic convex losses.”
- An Investigation of Why Overparameterization Exacerbates Spurious Correlations (2020, methodology): “, 2019) and shown analytically in highdimensional regression (Hastie et al., 2019; Bartlett et al., 2019; Mei & Montanari, 2019).”