mlsanityData to 14 Oct 2026

Interpolating Classifiers Make Few Mistakes

arXiv 2101.11815 ↗First posted 28 Jan 2021stat.ML cs.LG cs.NAcited by 22

Not on the map. Why?

Abstract (arXiv)

This paper provides elementary analyses of the regret and generalization of minimum-norm interpolating classifiers (MNIC). The MNIC is the function of smallest Reproducing Kernel Hilbert Space norm that perfectly interpolates a label pattern on a finite data set. We derive a mistake bound for MNIC and a regularized variant that holds for all data sets. This bound follows from elementary properties of matrix inverses. Under the assumption that the data is independently and identically distributed, the mistake bound implies that MNIC generalizes at a rate proportional to the norm of the interpolating solution and inversely proportional to the number of data points. This rate matches similar rates derived for margin classifiers and perceptrons. We derive several plausible generative models where the norm of the interpolating classifier is bounded or grows at a rate sublinear in n. We also show that as long as the population class conditional distributions are sufficiently separable in total variation, then MNIC generalizes with a fast rate.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 15 of its 31 references that are in the map. First posted on arXiv 28 Jan 2021.

Builds on

15 of 31 references.

References · 15

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2019Benign Overfitting in Linear Regressioncited by 549
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  4. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  5. 2019Exact Gaussian Processes on a Million Data Pointscited by 119
  6. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  7. 2017FALKON: An Optimal Large Scale Kernel Methodcited by 84
  8. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  9. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  10. 2020Neural Kernels Without Tangentscited by 56
  11. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
  12. 2020A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifierscited by 44
3 more
  1. 2020Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximationcited by 39
  2. 2017Diving into the shallows: a computational perspective on large-scale shallow learningcited by 31
  3. 2018numpywren: serverless linear algebracited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 2; 2023: 8; 2024: 3; 2025: 0; 2026: 2.

22 papers.

Sort:

  1. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  2. 2023Discover and Cure: Concept-aware Mitigation of Spurious Correlationcited by 71
  3. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 57
  4. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
  5. 2022The Implicit Bias of Benign Overfittingcited by 38
  6. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  7. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  8. 2021Is Importance Weighting Incompatible with Interpolating Classifiers?cited by 19
  9. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  10. 2021Patterns, predictions, and actions: A story about machine learningcited by 14
  11. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  12. 2023Sketched Ridgeless Linear Regression: The Role of Downsamplingcited by 7
10 more
  1. 2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
  2. 2021Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolationcited by 6
  3. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
  4. 2023Double and Single Descent in Causal Inference with an Application to High-Dimensional Synthetic Controlcited by 4
  5. 2023Overview of AdaBoost : Reconciling its views to better understand its dynamicscited by 3
  6. 2026Separating Geometry from Probability in the Analysis of Generalizationcited by 3
  7. 2021Universal Prediction Band via Semi-Definite Programmingcited by 2
  8. 2021Kernel Interpolation as a Bayes Point Machinecited by 1
  9. 2024Generalizability of Memorization Neural Networkscited by 1
  10. 2026A Behavioral Framework for Data-Driven Modeling of Nonlinear Systems in Vector-Valued Reproducing Kernel Hilbert Spacescited by 0