mlsanityData to 13 Oct 2026

Harmless interpolation in regression and classification with structured features

arXiv 2111.05198 ↗First posted 9 Nov 2021stat.ML cs.LG math.STcited by 14

Not on the map. Why?

Abstract (arXiv)

Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. Inspired by this empirical observation, recent work has sought to understand this phenomenon of benign overfitting or harmless interpolation in the much simpler linear model. Previous theoretical work critically assumes that either the data features are statistically independent or the input data is high-dimensional; this precludes general nonparametric settings with structured feature maps. In this paper, we present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space. A key contribution is that our framework describes precise sufficient conditions on the data Gram matrix under which harmless interpolation occurs. Our results recover prior independent-features results (with a much simpler analysis), but they furthermore show that harmless interpolation can occur in more general settings such as features that are a bounded orthonormal system. Furthermore, our results show an asymptotic separation between classification and regression performance in a manner that was previously only shown for Gaussian features.

Key facts. Cited by 14 papers in the map (data through 13 Oct 2026). Builds on 31 of its 69 references that are in the map. First posted on arXiv 9 Nov 2021.

Builds on

31 of 69 references.

References · 31

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,666
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 920
  3. 2019Benign Overfitting in Linear Regressioncited by 545
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 510
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 411
  6. 2015An Introduction to Matrix Concentration Inequalitiescited by 394
  7. 2021Deep learning: a statistical viewpointcited by 240
  8. 2019Two models of double descent for weak featurescited by 195
  9. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  10. 2018To understand deep learning we need to understand kernel learningcited by 186
  11. 2019Linearized two-layers neural networks in high dimensioncited by 155
  12. 2020Benign overfitting in ridge regressioncited by 152
19 more
  1. 2020Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Taskscited by 137
  2. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 131
  3. 2020Generalisation error in learning with random features and the hidden manifold modelcited by 126
  4. 2019Harmless interpolation of noisy data in regressioncited by 121
  5. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  6. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  7. 2020Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regimecited by 95
  8. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  9. 2020Understanding Double Descent Requires a Fine-Grained Bias-Variance Decompositioncited by 75
  10. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 69
  11. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 56
  12. 2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
  13. 2018Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenoncited by 44
  14. 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
  15. 2020On the proliferation of support vectors in high dimensionscited by 32
  16. 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
  17. 2021Towards an Understanding of Benign Overfitting in Neural Networkscited by 29
  18. 2020What causes the test error? Going beyond bias-variance via ANOVAcited by 28
  19. 2020Sample complexity and effective dimension for regression on manifoldscited by 8

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 6; 2024: 2; 2025: 4.

14 papers.

Sort:

  1. 2022The Implicit Bias of Benign Overfittingcited by 38
  2. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  3. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  4. 2022The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspectivecited by 24
  5. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  6. 2023Strong inductive biases provably prevent harmless interpolationcited by 9
  7. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
  8. 2024High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularizationcited by 4
  9. 2023New Equivalences Between Interpolation and SVMs: Kernels and Structured Featurescited by 3
  10. 2023Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Modelscited by 3
  11. 2025A general technique for approximating high-dimensional empirical kernel matricescited by 3
  12. 2025Understanding Overparametrization in Survival Models through Interpolationcited by 2
2 more
  1. 2025A Ridge Too Far: Correcting Over-Shrinkage via Negative Regularizationcited by 0
  2. 2025Calibrated Principal Component Regressioncited by 0