CoChat
Sign Up
PreprintCited by 1

The DOI matches its DataCite record.

Benign Overfitting in Linear Regression

Bartlett, Peter L., Long, Philip M., Lugosi, Gábor, Tsigler, Alexander·2019·arXiv
DOI 10.48550/arxiv.1906.11300arXiv 1906.11300
Open this paper in CoChat — free account

Abstract

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 lies in an infinite dimensional space versus when the data lies in a finite dimensional space whose dimension grows faster than the sample size.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1906.11300

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

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

No references could be resolved yet.

Research works printed but not linked: 40

  1. Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Technical Report 1901.08584 [cs.LG], arXiv, 2019.
  2. Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53, 2017.
  3. P. L. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525-536, 1998.
  4. P. L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
  5. Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6240- 6249.
  6. Peter L Bartlett. Learning with a slowly changing distribution. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 243-252. ACM, 1992.
  7. Peter L. Bartlett. Accurate prediction from interpolation: A new challenge for statistical learning theory. Presentation at the National Academy of Sciences workshop, The Science of Deep Learning, March 14, 2019. https://youtu.be/1y2sB38T6FU, 2019.
  8. Peter L Bartlett, Philip M Long, and Robert C Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434-452, 1996.
  9. M. Belkin, D. Hsu, and P. Mitra. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate. In Proceedings of NIPS 2018, 2018.
  10. M. Belkin, A. Rakhlin, and A. B. Tsybakov. Does data interpolation contradict statistical optimality? Technical Report 1806.09471, arXiv, 2018.
  11. Mikhail Belkin. Approximation beats concentration? an approximation view on inference with smooth radial kernels. In COLT, pages 1348-1361, 2018.
  12. Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. Technical Report 1812.11118, arXiv, 2018.
  13. Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. Technical Report 1903.07571 [cs.LG], arXiv, 2019.
  14. Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In ICML, pages 541-549, 2018.
  15. Gyora M Benedek and Alon Itai. Learnability with respect to fixed distributions. Theoretical Computer Science, 86(2):377-389, 1991.
  16. Yoshua Bengio, Nicolas Le Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. In Y. Weiss, B. Schölkopf, and J. C. Platt, editors, Advances in Neural Information Processing Systems 18, pages 123-130. MIT Press, 2006.
  17. Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. Technical Report arXiv:1912.01198, arXiv, 2019. · arXiv
  18. C. A. Desoer and B. H. Whalen. A note on pseudoinverses. Journal of the Society of Industrial and Applied Mathematics, 11(1):442-446, 1963.
  19. L. Devroye, L. Györfi, and A. Krzyżak. The Hilbert kernel regression estimate. Journal of Multivariate Analysis, 65(2):209-227, 1998.
  20. Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. Technical Report 1811.03804 [cs.LG], arXiv, 2018.
  21. Simon S. Du, Barnabás Poczós, Xiyu Zhai, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. Technical Report 1810.02054 [cs.LG], arXiv, 2018.
  22. Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299. PMLR, 06-09 Jul 2018.
  23. Gene H. Golub and Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1996.
  24. Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. Technical Report 1903.08560 [math.ST], arXiv, 2019.
  25. Trevor Hastie, Robert Tibshirani, and Jerome H. Friedman. Elements of Statistical Learning. Springer, 2001.
  26. Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), 2018.
  27. Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 23(1):110-133, February 2017.
  28. W. S. Lee, P. L. Bartlett, and R. C. Williamson. Efficient agnostic learning of neural networks with bounded fan-in. IEEE Transactions on Information Theory, 42(6):2118-2132, 1996.
  29. Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Technical Report 1808.01204 [cs.LG], arXiv, 2018.
  30. Tengyuan Liang and Alexander Rakhlin. Just interpolate: kernel "ridgeless" regression can generalize. Technical Report 1808.00387, arXiv, 2018. To appear in Annals of Statistics.
  31. Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai. Harmless interpolation of noisy data in regression. Technical Report 1903.09139 [cs.LG], arXiv, 2019.
  32. Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376-1401, Paris, France, 03-06 Jul 2015. PMLR.
  33. Stephen Page and Steffen Grünewälder. Ivanov-regularised least-squares estimators over large RKHSs and their interpolation spaces. Technical Report arXiv:1706.03678 [math.ST], arXiv, June 2017. · arXiv
  34. Mark Rudelson and Roman Vershynin. Sampling from large matrices: an approach through geometric functional analysis. Journal of the ACM, 54(4):21, 2007.
  35. Mark Rudelson and Roman Vershynin. Hanson-Wright inequality and sub-gaussian concentra- tion. Electronic Communications in Probability, 18(82):1-9, 2013.
  36. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Yonina C. Eldar and Gitta Kutyniok, editors, Compressed Sensing: Theory and Applications, page 210-268. Cambridge University Press, 2012.
  37. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  38. Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. Technical Report 1611.03131 [cs.LG], arXiv, 2016.
  39. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
  40. Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. Technical Report arXiv:1811.08888, arXiv, 2018. · arXiv

Cited by

Sorted by citations

Metadata

Authors
Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A.
Venue
arXiv
Publisher
arXiv
Published
2019
DOI
10.48550/arxiv.1906.11300
arXiv
1906.11300
References
0
Type
Preprint
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/

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