# Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate

arXiv: https://arxiv.org/abs/1806.05161 · HTML: https://mlsanity.com/paper/1806.05161/

## Key facts

- Cited by 99 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2018.

## Built on by (most cited first, 30 of 99)

- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [On Memorization of Large Language Models in Logical Reasoning](https://mlsanity.com/paper/2410.23123/) (2024)
- [Neural Collapse: A Review on Modelling Principles and Generalization](https://mlsanity.com/paper/2206.04041/) (2022)
- [Learning Curve Theory](https://mlsanity.com/paper/2102.04074/) (2021)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [RDA: Robust Domain Adaptation via Fourier Adversarial Attacking](https://mlsanity.com/paper/2106.02874/) (2021)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting](https://mlsanity.com/paper/2207.06569/) (2022)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization](https://mlsanity.com/paper/2107.12580/) (2021)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory](https://mlsanity.com/paper/2311.14646/) (2023)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [The worst of both worlds: A comparative analysis of errors in learning from data in psychology and machine learning](https://mlsanity.com/paper/2203.06498/) (2022)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression](https://mlsanity.com/paper/2202.09889/) (2022)
- [Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models](https://mlsanity.com/paper/2103.04554/) (2021)
- [On the Inconsistency of Kernel Ridgeless Regression in Fixed Dimensions](https://mlsanity.com/paper/2205.13525/) (2022)
- [ResMem: Learn what you can and memorize the rest](https://mlsanity.com/paper/2302.01576/) (2023)
- [InstanT: Semi-supervised Learning with Instance-dependent Thresholds](https://mlsanity.com/paper/2310.18910/) (2023)
- [Wide and Deep Neural Networks Achieve Optimality for Classification](https://mlsanity.com/paper/2204.14126/) (2022)
- [On the Convergence of Shallow Neural Network Training with Randomly Masked Neurons](https://mlsanity.com/paper/2112.02668/) (2021)
- [Monotonicity and Double Descent in Uncertainty Estimation with Gaussian Processes](https://mlsanity.com/paper/2210.07612/) (2022)
- [On the Lipschitz Constant of Deep Networks and Double Descent](https://mlsanity.com/paper/2301.12309/) (2023)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)

## Abstract (arXiv)

Many modern machine learning models are trained to achieve zero or near-zero training error in order to obtain near-optimal (but non-zero) test error. This phenomenon of strong generalization performance for "overfitted" / interpolated classifiers appears to be ubiquitous in high-dimensional data, having been observed in deep networks, kernel machines, boosting and random forests. Their performance is consistently robust even when the data contain large amounts of label noise. Very little theory is available to explain these observations. The vast majority of theoretical analyses of generalization allows for interpolation only when there is little or no label noise. This paper takes a step toward a theoretical foundation for interpolated classifiers by analyzing local interpolating schemes, including geometric simplicial interpolation algorithm and singularly weighted k-nearest neighbor schemes. Consistency or near-consistency is proved for these schemes in classification and regression problems. Moreover, the nearest neighbor schemes exhibit optimal rates under some standard statistical assumptions. Finally, this paper suggests a way to explain the phenomenon of adversarial examples, which are seemingly ubiquitous in modern machine learning, and also discusses some connections to kernel machines and random forests in the interpolated regime.