Surprises in high-dimensional ridgeless least squares interpolation
Open accessThe DOI matches its Crossref record; 81 of the 81 references it cites were found in a registry or an index.
Abstract
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∈Rp are obtained by applying a linear transform to a vector of i.i.d. entries, xi=Σ1/2zi (with zi∈Rp); 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∈Rd, W∈Rp×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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(2016) · Cited by 11,679
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
Golub, G. H., Heath, M., & Wahba, G. (1979) · Technometrics · doi:10.1080/00401706.1979.10489751 · Cited by 3,934
A survey of cross-validation procedures for model selection
Arlot, S., & Célisse, A. (2010) · LillOA (Université de Lille (University Of Lille)) · Cited by 3,669
A survey of cross-validation procedures for model selection
Arlot, S., & Celisse, A. (2010) · Statistics Surveys · doi:10.1214/09-ss054 · Cited by 3,522
Craven, P., & Wahba, G. (1978) · Numerische Mathematik · doi:10.1007/bf01404567 · Cited by 3,388
Understanding deep learning requires rethinking generalization
Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2016) · arXiv · doi:10.48550/arxiv.1611.03530 · Cited by 2,838
Random Features for Large-Scale Kernel Machines
Rahimi, A., & Recht, B. (2007) · Cited by 2,783
Random Matrix Theory and Wireless Communications
Tulino, A. M., & Verdú, S. (2004) · Foundations and Trends™ in Communications and Information Theory · doi:10.1561/0100000001 · Cited by 2,034
Reconciling modern machine-learning practice and the classical bias–variance trade-off
(2019) · Proceedings of the National Academy of Sciences · Cited by 1,956
DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
Marčenko, V. A., & Pastur, L. A. (1967) · Mathematics of the USSR-Sbornik · doi:10.1070/sm1967v001n04abeh001994 · Cited by 1,713
Reconciling modern machine-learning practice and the classical bias–variance trade-off
Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1903070116 · Cited by 1,595
Neural Tangent Kernel: Convergence and Generalization in Neural Networks
Jacot, A., Gabriel, F., & Hongler, C. (2018) · arXiv · doi:10.48550/arxiv.1806.07572 · Cited by 1,562
Spectral Analysis of Large Dimensional Random Matrices
Bai, Z., & Silverstein, J. W. (2010) · Springer Series in Statistics · doi:10.1007/978-1-4419-0661-8 · Cited by 1,544
Smoothing noisy data with spline functions
Wahba, G. (1975) · Numerische Mathematik · doi:10.1007/bf01437407 · Cited by 1,443
Training with Noise is Equivalent to Tikhonov Regularization
Bishop, C. M. (1995) · Neural Computation · doi:10.1162/neco.1995.7.1.108 · Cited by 1,325
An Introduction to Random Matrices
Anderson, G. W., Guionnet, A., & Zeitouni, O. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511801334 · Cited by 1,281
On Early Stopping in Gradient Descent Learning
Yao, Y., Rosasco, L., & Caponnetto, A. (2007) · Constructive Approximation · doi:10.1007/s00365-006-0663-2 · Cited by 970
Topics in Random Matrix Theory
Tao, T. (2012) · Graduate Studies in Mathematics · doi:10.1090/gsm/132 · Cited by 868
The Entire Regularization Path for the Support Vector Machine
Hastie, T. J., Rosset, S., Tibshirani, R. J., & Zhu, J. (2004) · Journal of Machine Learning Research · Cited by 748
Self-citationA Convergence Theory for Deep Learning via Over-Parameterization
Allen-Zhu, Z., Li, Y., & Song, Z. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.03962 · Cited by 657
Time-frequency localization operators: a geometric phase space approach
Daubechies, I. (1988) · IEEE Transactions on Information Theory · doi:10.1109/18.9761 · Cited by 649
Strong Convergence of the Empirical Distribution of Eigenvalues of Large Dimensional Random Matrices
Silverstein, J. W. (1995) · Journal of Multivariate Analysis · doi:10.1006/jmva.1995.1083 · Cited by 560
Benign overfitting in linear regression
Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1907378117 · Cited by 547
The generalization error of random features regression: Precise asymptotics and double descent curve
Mei, S., & Montanari, A. (2019) · arXiv · doi:10.48550/arxiv.1908.05355 · Cited by 537
Limit of the Smallest Eigenvalue of a Large Dimensional Sample Covariance Matrix
Bai, Z. D., & Yin, Y. Q. (1993) · The Annals of Probability · doi:10.1214/aop/1176989118 · Cited by 519
Li, K.-C. (1987) · The Annals of Statistics · doi:10.1214/aos/1176350486 · Cited by 514
A mean field view of the landscape of two-layer neural networks
Mei, S., Montanari, A., & Nguyen, P.-M. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1806579115 · Cited by 500
Self-citationLocal Operator Theory, Random Matrices and Banach Spaces
(2001) · Handbook of the Geometry of Banach Spaces · doi:10.1016/s1874-5849(01)80010-3 · Cited by 432
Just interpolate: Kernel “Ridgeless” regression can generalize
Liang, T., & Rakhlin, A. (2020) · The Annals of Statistics · doi:10.1214/19-aos1849 · Cited by 397
Wide neural networks of any depth evolve as linear models under gradient descent *
Lee, J., Xiao, L., Schoenholz, S. S., Bahri, Y., Novak, R., Sohl-Dickstein, J., & Pennington, J. (2020) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/abc62b · Cited by 353
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Du, S. S., Zhai, X., Póczos, B., & Singh, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.02054 · Cited by 344
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal TransportPreprint
Chizat, L., & Bach, F. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09545 · Cited by 334
Two Models of Double Descent for Weak Features
Belkin, M., Hsu, D., & Xu, J. (2020) · SIAM Journal on Mathematics of Data Science · doi:10.1137/20m1336072 · Cited by 322
Boosting as a Regularized Path to a Maximum Margin Classifier
Rosset, S., Zhu, J., & Hastie, T. J. (2004) · Journal of Machine Learning Research · doi:10.5555/1005332.1016790 · Cited by 301
Self-citationHigh-dimensional dynamics of generalization error in neural networks
Advani, M. S., Saxe, A. M., & Sompolinsky, H. (2020) · Neural Networks · doi:10.1016/j.neunet.2020.08.022 · Cited by 289
Scaling description of generalization with number of parameters in deep learning
Geiger, M., Jacot, A., Spigler, S., Gabriel, F., Sagun, L., d’Ascoli, S., Biroli, G., Hongler, C., & Wyart, M. (2020) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ab633c · Cited by 239
Universality Laws for High-Dimensional Learning With Random Features
Hu, H. B., & Lu, Y. M. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3217698 · Cited by 238
On Lazy Training in Differentiable Programming
Chizat, L., Oyallon, E., & Bach, F. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.07956 · Cited by 235
Li, K.-C. (1986) · The Annals of Statistics · doi:10.1214/aos/1176350052 · Cited by 223
A jamming transition from under- to over-parametrization affects generalization in deep learning
Spigler, S., Geiger, M., d’Ascoli, S., Sagun, L., Biroli, G., & Wyart, M. (2019) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ab4c8b · Cited by 218
High-dimensional asymptotics of prediction: Ridge regression and classification
Dobriban, E., & Wager, S. (2018) · The Annals of Statistics · doi:10.1214/17-aos1549 · Cited by 211
To understand deep learning we need to understand kernel learning
Belkin, M., Ma, S., & Mandal, S. (2018) · arXiv · doi:10.48550/arxiv.1802.01396 · Cited by 201
Deep learning: a statistical viewpoint
Bartlett, P. L., Montanari, A., & Rakhlin, A. (2021) · Acta Numerica · doi:10.1017/s0962492921000027 · Cited by 200
Self-citationJust interpolate: Kernel “Ridgeless” regression can generalizePreprint
Liang, T., & Rakhlin, A. (2020) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 196
Eigenvectors of some large sample covariance matrix ensembles
Ledoit, O., & Péché, S. (2011) · Probability Theory and Related Fields · doi:10.1007/s00440-010-0298-3 · Cited by 195
Gradient Descent Finds Global Minima of Deep Neural Networks
Du, S. S., Lee, J. D., Li, H., Wang, L., & Zhai, X. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.03804 · Cited by 189
Benign overfitting in ridge regressionPreprint
Tsigler, A., & Bartlett, P. L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.14286 · Cited by 183
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
Zou, D., Cao, Y. J., Zhou, D., & Gu, Q. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.08888 · Cited by 175
On the Optimal Weighted $\ell_2$ Regularization in Overparameterized Linear RegressionPreprint
Wu, D. C.-Y., & Xu, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.05800 · Cited by 170
Early stopping and non-parametric regression: An optimal data-dependent stopping rule
Raskutti, G., Wainwright, M. J., & Yu, B. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.3574 · Cited by 167
Are All Layers Created Equal?Preprint
Zhang, C., Bengio, S., & Singer, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.01996 · Cited by 166
Characterizing Implicit Bias in Terms of Optimization Geometry
Gunasekar, S., Lee, J. D., Soudry, D., & Srebro, N. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.08246 · Cited by 160
Generalisation error in learning with random features and the hidden manifold model*
Gerace, F., Loureiro, B., Krząkała, F., Mézard, M., & Zdeborová, L. (2021) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ac3ae6 · Cited by 146
Does data interpolation contradict statistical optimality?Preprint
Belkin, M., Rakhlin, A., & Tsybakov, A. B. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.09471 · Cited by 142
Linearized two-layers neural networks in high dimension
Ghorbani, B., Mei, S., Misiakiewicz, T., & Montanari, A. (2021) · The Annals of Statistics · doi:10.1214/20-aos1990 · Cited by 142
Self-citationFinite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized RegimePreprint
Chatterji, N. S., & Long, P. M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.12019 · Cited by 142
The spectrum of kernel random matrices
Karoui, N. E. (2007) · Cited by 137
Nonlinear random matrix theory for deep learning*
Pennington, J., & Worah, P. (2019) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ab3bc3 · Cited by 130
The spectrum of kernel random matrices
Karoui, N. E. (2009) · The Annals of Statistics · doi:10.1214/08-aos648 · Cited by 123
Ridge regression and asymptotic minimax estimation over spheres of growing dimension
Dicker, L. H. (2015) · Bernoulli · doi:10.3150/14-bej609 · Cited by 108
Rotskoff, G. M., & Vanden‐Eijnden, E. (2018) · arXiv (Cornell University) · Cited by 100
Trainability and Accuracy of Neural Networks: An Interacting Particle System ApproachPreprint
Rotskoff, G. M., & Vanden‐Eijnden, E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.00915 · Cited by 93
Consistency of Interpolation with Laplace Kernels is a High-Dimensional PhenomenonPreprint
Rakhlin, A., & Zhai, X.-Y. (2018) · Annual Conference Computational Learning Theory · doi:10.48550/arxiv.1812.11167 · Cited by 89
The Gaussian equivalence of generative models for learning with shallow neural networksPreprint
Goldt, S., Loureiro, B., Reeves, G., Krząkała, F., Mézard, M., & Zdeborová, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.14709 · Cited by 85
On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of KernelsPreprint
Liang, T., Rakhlin, A., & Zhai, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.10292 · Cited by 83
A Note on Lazy Training in Supervised Differentiable ProgrammingPreprint
Chizat, L., & Bach, F. (2018) · arXiv (Cornell University) · Cited by 81
Functional approximation by feed-forward networks: a least-squares approach to generalization
Webb, A. R. (1994) · IEEE Transactions on Neural Networks · doi:10.1109/72.286908 · Cited by 78
Implicit Bias of Gradient Descent on Linear Convolutional Networks
Gunasekar, S., Lee, J., Soudry, D., & Srebro, N. (2018) · arXiv · doi:10.48550/arxiv.1806.00468 · Cited by 75
Montanari, A., Ruan, F., Sohn, Y., & Yan, J. (2025) · The Annals of Statistics · doi:10.1214/25-aos2489 · Cited by 75
Self-citationUniform Consistency of Cross-Validation Estimators for High-Dimensional Ridge Regression.
Patil, P., Wei, Y., Rinaldo, A., & Tibshirani, R. J. (2021) · International Conference on Artificial Intelligence and Statistics · Cited by 74
Self-citationTHE SPECTRUM OF RANDOM INNER-PRODUCT KERNEL MATRICES
Cheng, X., & Singer, A. (2013) · Random Matrices Theory and Application · doi:10.1142/s201032631350010x · Cited by 72
Adlam, B., & Pennington, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.06786 · Cited by 72
Mitochondrial DNA and genetic disease
Poulton, J. (1992) · BioEssays · doi:10.1002/bies.950141108 · Cited by 64
Kobak, D., Lomond, J., & Sanchez, B. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.10939 · Cited by 56
Asymptotics of Ridge (less) Regression under General Source ConditionPreprint
Richards, D., Mourtada, J., & Rosasco, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.06386 · Cited by 48
The spectral norm of random inner-product kernel matrices
Fan, Z., & Andrea Montanari, A. (2018) · Probability Theory and Related Fields · doi:10.1007/s00440-018-0830-4 · Cited by 45
Consistent Risk Estimation in Moderately High-Dimensional Linear Regression
Xu, J., Maleki, A., Rad, K. R., & Hsu, D. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3095375 · Cited by 25
The Entire Regularization Path for the Support Vector Machine
Rosset, S., Tibshirani, R. J., Zhu, J., & Hastie, T. J. (2004) · neural information processing systems · Cited by 23
Self-citationInterpolating Predictors in High-Dimensional Factor RegressionPreprint
Bunea, F., Strimas-Mackey, S., & Wegkamp, M. H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.02525 · Cited by 21
Consistent Risk Estimation in High-Dimensional Linear Regression
Xu, J., Maleki, A., & Rad, K. R. (2019) · Cited by 10
Cited by
Deep double descent: where bigger models and more data hurt*
Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., & Sutskever, I. (2021) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/ac3a74 · Cited by 565
Benign overfitting in linear regression
Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1907378117 · Cited by 547
The generalization error of random features regression: Precise asymptotics and double descent curve
Mei, S., & Montanari, A. (2019) · arXiv · doi:10.48550/arxiv.1908.05355 · Cited by 537
Cross-Validation: What Does It Estimate and How Well Does It Do It?
Bates, S., Hastie, T., & Tibshirani, R. (2024) · Journal of the American Statistical Association · doi:10.1080/01621459.2023.2197686 · Cited by 442
Self-citationPredictive inference with the jackknife+
Barber, R. F., Candès, E. J., Ramdas, A., & Tibshirani, R. J. (2021) · The Annals of Statistics · doi:10.1214/20-aos1965 · Cited by 351
Self-citation
Metadata
- Authors
- Hastie, T., Montanari, A., Rosset, S., & Tibshirani, R. J.
- Venue
- The Annals of Statistics
- Publisher
- Institute of Mathematical Statistics
- Published
- 2022-04-01
- Volume
- 50
- Issue
- 2
- Pages
- 949-986
- ISSN
- 0090-5364 (ISSN-L)
- OpenAlex
- W2923764619
- Cited by
- 503
- References
- 81
- FWCI
- 20.28
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.