# Interpolating Classifiers Make Few Mistakes arXiv: https://arxiv.org/abs/2101.11815 · HTML: https://mlsanity.com/paper/2101.11815/ ## 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 (most cited first, 15 of 15) - [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018) - [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019) - [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019) - [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018) - [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019) - [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020) - [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017) - [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019) - [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020) - [Neural Kernels Without Tangents](https://mlsanity.com/paper/2003.02237/) (2020) - [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016) - [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020) - [Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation](https://mlsanity.com/paper/2005.03991/) (2020) - [Diving into the shallows: a computational perspective on large-scale shallow learning](https://mlsanity.com/paper/1703.10622/) (2017) - [numpywren: serverless linear algebra](https://mlsanity.com/paper/1810.09679/) (2018) ## Built on by (most cited first, 22 of 22) - [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022) - [Discover and Cure: Concept-aware Mitigation of Spurious Correlation](https://mlsanity.com/paper/2305.00650/) (2023) - [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021) - [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021) - [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022) - [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023) - [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023) - [Is Importance Weighting Incompatible with Interpolating Classifiers?](https://mlsanity.com/paper/2112.12986/) (2021) - [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023) - [Patterns, predictions, and actions: A story about machine learning](https://mlsanity.com/paper/2102.05242/) (2021) - [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023) - [Sketched Ridgeless Linear Regression: The Role of Downsampling](https://mlsanity.com/paper/2302.01088/) (2023) - [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024) - [Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation](https://mlsanity.com/paper/2111.07041/) (2021) - [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024) - [Double and Single Descent in Causal Inference with an Application to High-Dimensional Synthetic Control](https://mlsanity.com/paper/2305.00700/) (2023) - [Overview of AdaBoost : Reconciling its views to better understand its dynamics](https://mlsanity.com/paper/2310.18323/) (2023) - [Separating Geometry from Probability in the Analysis of Generalization](https://mlsanity.com/paper/2604.19560/) (2026) - [Universal Prediction Band via Semi-Definite Programming](https://mlsanity.com/paper/2103.17203/) (2021) - [Kernel Interpolation as a Bayes Point Machine](https://mlsanity.com/paper/2110.04274/) (2021) - [Generalizability of Memorization Neural Networks](https://mlsanity.com/paper/2411.00372/) (2024) - [A Behavioral Framework for Data-Driven Modeling of Nonlinear Systems in Vector-Valued Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2605.07052/) (2026) ## 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.