The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Harmless interpolation of noisy data in regression
Open accessAbstract
A continuing mystery in understanding the empirical success of deep neural networks has been in their ability to achieve zero training error and yet generalize well, even when the training data is noisy and there are more parameters than data points. We investigate this "overparametrization" phenomena in the classical underdetermined linear regression problem, where all solutions that minimize training error interpolate the data, including noise. We give a bound on how well such interpolative solutions can generalize to fresh test data, and show that this bound generically decays to zero with the number of extra features, thus characterizing an explicit benefit of overparameterization. For appropriately sparse linear models, we provide a hybrid interpolating scheme (combining classical sparse recovery schemes with harmless noise-fitting) to achieve generalization error close to the bound on interpolative solutions.
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.
Integrity signals
Registry
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.
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?
An analog of model-wise double descent occurs even for linear models.
“However, an analog of model-wise double descent occurs even for linear models.”
From Deep double descent: where bigger models and more data hurt* (2021) · cites this paper as Muthukumar et al 2019
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
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
Flagged first, then by citations
Research works printed but not linked: 26
- soudry, 2018, The implicit bias of gradient descent on separable data, The Journal of Machine Learning Research, 19, 2822
- 10.1214/15-AOS1337 · DOI
- 10.1109/TIT.2011.2146090 · DOI
- 10.1214/08-AOS620 · DOI
- liang, 2018, Just interpolate: Kernel, ridgeless" regression can generalize " arXiv preprint arXiv 1808 00387
- 10.1201/9781420035933 · DOI
- hsu, 2012, Random design analysis of ridge regression, Conference on Learning Theory, 9
- pati, 1993, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, Signals Systems and Computers 1993 1993 Conference Record of The Twenty-Seventh Asilomar Conference on, 40
- 10.1109/TIT.2011.2173241 · DOI
- wilson, 2017, The marginal value of adaptive gradient methods in machine learning, Advances in neural information processing systems, 4148
- raskutti, 2010, Restricted eigenvalue properties for correlated gaussian designs, Journal of Machine Learning Research, 11, 2241
- 10.1109/TIT.2007.909108 · DOI
- 10.1109/TIT.2009.2032726 · DOI
- rahimi, 2008, Random features for large-scale kernel machines, Advances in neural information processing systems, 1177
- 10.1109/TIT.2010.2059891 · DOI
- 10.1109/TIT.2009.2032816 · DOI
- 10.1214/009053605000000282 · DOI
- li, 2018, Algorithmic regularization in overparameterized matrix sensing and neural networks with quadratic activations, Conference on Learning Theory, 2
- soltanolkotabi, 2018, Theoretical insights into the optimization landscape of over-parameterized shallow neural networks, IEEE Transactions on Information Theory
- 10.1109/72.788640 · DOI
- friedman, 0, The Elements of Statistical Learning, 1
- 10.1016/0885-064X(91)90002-F · DOI
- 10.1137/0609045 · DOI
- 10.1016/j.aim.2008.01.010 · DOI
- 10.1137/S003614450037906X · DOI
- bartlett, 0, EECS Technical Report
Cited by
Sorted by citations
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
Does learning require memorization? a short tale about a long tail
Feldman, V. (2020) · Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing · doi:10.1145/3357713.3384290 · Cited by 287
Memorizing without overfitting: Bias, variance, and interpolation in overparameterized models
Rocks, J. W., & Mehta, P. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.013201 · Cited by 74
Metadata
- Authors
- Muthukumar, V., Vodrahalli, K., & Sahai, A.
- Affiliations
- University of California, Berkeley (US)
- Venue
- 2019 IEEE International Symposium on Information Theory (ISIT)
- Publisher
- IEEE
- Published
- 2019-07
- Volume
- 1
- Issue
- 1
- Pages
- 2299-2303
- OpenAlex
- W2924580837
- Cited by
- 162
- References
- 1
- Citations by year
- 2026: 10 · 2025: 12 · 2024: 21 · 2023: 23 · 2022: 18 · 2021: 41 · 2020: 33 · 2019: 3
- FWCI
- 20.15
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE International Symposium on Information Theory (ISIT) (publishedVersion)
- IEEE Journal on Selected Areas in Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (144078, AST-144078, 1343398)
- Simons Institute for the Theory of Computing, University of California Berkeley
- Division of Electrical, Communications and Cyber Systems (ECCS-1343398)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Keywords
- noisy data, overparameterization, generalization error, sparse signal recovery, sparse linear models, deep neural network, training error
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
