The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Benign overfitting in linear regression
Open accessAbstract
The phenomenon of benign overfitting is one of the key mysteries uncovered by deep learning methodology: deep neural networks seem to predict well, even with a perfect fit to noisy training data. Motivated by this phenomenon, we consider when a perfect fit to training data in linear regression is compatible with accurate prediction. We give a characterization of linear regression problems for which the minimum norm interpolating prediction rule has near-optimal prediction accuracy. The characterization is in terms of two notions of the effective rank of the data covariance. It shows that overparameterization is essential for benign overfitting in this setting: the number of directions in parameter space that are unimportant for prediction must significantly exceed the sample size. By studying examples of data covariance properties that this characterization shows are required for benign overfitting, we find an important role for finite-dimensional data: the accuracy of the minimum norm interpolating prediction rule approaches the best possible accuracy for a much narrower range of properties of the data distribution when the data lie in an infinite-dimensional space vs. when the data lie in a finite-dimensional space with dimension that grows faster than the sample size.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
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
Understanding deep learning (still) requires rethinking generalization
Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2021) · Communications of the ACM · doi:10.1145/3446776 · Cited by 2,400
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
Reconciling modern machine-learning practice and the classical bias–variance trade-off
(2019) · Proceedings of the National Academy of Sciences · Cited by 1,956
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Bartlett, P. L., & Mendelson, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44581-1_15 · Cited by 1,949
Self-citationReconciling 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
Bartlett, P. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.661502 · Cited by 1,166
Self-citationSurprises in high-dimensional ridgeless least squares interpolation
Hastie, T., Montanari, A., Rosset, S., & Tibshirani, R. J. (2022) · The Annals of Statistics · doi:10.1214/21-aos2133 · Cited by 503
Hanson-Wright inequality and sub-gaussian concentration
Rudelson, M., & Vershynin, R. (2013) · Electronic Communications in Probability · doi:10.1214/ecp.v18-2865 · Cited by 502
Towards Understanding the Spectral Bias of Deep Learning
Cao, Y. J., Fang, Z., Wu, Y., Zhou, D., & Gu, Q. (2021) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2021/304 · Cited by 371
Breaking the Curse of Dimensionality with Convex Neural Networks
Bach, F. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.8690 · Cited by 295
Norm-Based Capacity Control in Neural Networks
Neyshabur, B., Tomioka, R., & Srebro, N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.00036 · Cited by 279
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatePreprint
Belkin, M., Hsu, D., & Mitra, P. P. (2018) · Cold Spring Harbor Laboratory Institutional Repository (Cold Spring Harbor Laboratory) · doi:10.48550/arxiv.1806.05161 · Cited by 270
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
Li, Y., & Liang, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1808.01204 · Cited by 257
Gradient descent optimizes over-parameterized deep ReLU networks
Zou, D., Cao, Y., Zhou, D., & Gu, Q. (2020) · Machine Learning · doi:10.1007/s10994-019-05839-6 · Cited by 227
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
Just interpolate: Kernel “Ridgeless” regression can generalizePreprint
Liang, T., & Rakhlin, A. (2020) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 196
Concentration inequalities and moment bounds for sample covariance operators
Koltchinskii, V., & Lounici, K. (2017) · Bernoulli · doi:10.3150/15-bej730 · Cited by 191
Size-independent sample complexity of neural networks
Golowich, N., Rakhlin, A., & Shamir, O. (2020) · Information and Inference: A Journal of the IMA · doi:10.1093/imaiai/iaz007 · Cited by 177
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
Harmless interpolation of noisy data in regression
Muthukumar, V., Vodrahalli, K., & Sahai, A. (2019) · 2019 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849614 · Cited by 162
Spectrally-normalized margin bounds for neural networks
Bartlett, P. L., Foster, D. J., & Telgarsky, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.08498 · Cited by 159
Self-citationBengio, Y., Roux, N. L., Vincent, P., Delalleau, O., & Marcotte, P. (2005) · Cited by 153
Efficient agnostic learning of neural networks with bounded fan-in
Lee, W. S., Bartlett, P. L., & Williamson, R. C. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556601 · Cited by 150
Self-citationLearnability with respect to fixed distributions
Benedek, G. M., & Itai, A. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90026-x · Cited by 145
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
Fat-shattering and the learnability of real-valued functions
Bartlett, P. L., Long, P. M., & Williamson, R. C. (1994) · Annual Conference on Computational Learning Theory (COLT) · doi:10.1145/180139.181158 · Cited by 117
Self-citationDiverse Neural Network Learns True Target FunctionsPreprint
Xie, B., Liang, Y., & Song, L. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.03131 · Cited by 107
Approximation beats concentration? An approximation view on inference with smooth radial kernelsPreprint
Belkin, M. (2018) · Annual Conference Computational Learning Theory · doi:10.48550/arxiv.1801.03437 · Cited by 79
Learning with a slowly changing distribution
Bartlett, P. L. (1992) · Conference on Learning Theory · doi:10.1145/130385.130412 · Cited by 53
Self-citationThe Hilbert Kernel Regression Estimate
Devroye, L., Györfi, L., & Krzyżak, A. (1998) · Journal of Multivariate Analysis · doi:10.1006/jmva.1997.1725 · Cited by 30
Cited by
Chicco, D., Warrens, M. J., & Jurman, G. (2021) · PeerJ Computer Science · doi:10.7717/peerj-cs.623 · Cited by 5,380
Shortcut learning in deep neural networks
Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., & Wichmann, F. A. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-00257-z · Cited by 2,224
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
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
Surprises in high-dimensional ridgeless least squares interpolation
Hastie, T., Montanari, A., Rosset, S., & Tibshirani, R. J. (2022) · The Annals of Statistics · doi:10.1214/21-aos2133 · Cited by 503
Metadata
- Authors
- Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2020-04-24
- Volume
- 117
- Issue
- 48
- Pages
- 30063-30070
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2954975122
- Cited by
- 547
- References
- 34
- FWCI
- 31.06
- 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.