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

By Mikhail Belkin, Daniel J. Hsu, Partha P. Mitra. 2018

280 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

Citations in the corpus

What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation (2020, background): “Another line of research focuses on the generalization error of algorithms that fit the data perfectly (referred to as interpolating) [29, 10, 8, 20, 9, 25, 5, 7, 14, 21].”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, background): “This paper continues the line of work in (Belkin et al., 2018a,c; Belkin, 2018) on understanding theoretical mechanisms for the good out-of-sample performance of interpolation.”
Does data interpolation contradict statistical optimality? (2018, background): “The recent work of Belkin et al. (2018) proves the ﬁrst (to the best of our knowledge) non-asymptotic rates for interpolating procedures, yet the guarantees are suboptimal.”
A Kernel Perspective for Regularizing Deep Neural Networks (2018, unknown): “We note that a perfect ﬁt of the data with large complexity does not prevent generalization (see, e.g. , Belkin et al., 2018a;b); yet, such mechanisms are still poorly understood.”
Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation (2019, background): “These observations have led to recent theoretical activity[3, 4, 16].”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, background): “It has been shown that Gaussian kernel can achieve impressive accuracy on MNIST and CIFAR10 data without any explicit regularization (Zhang et al., 2017; Belkin et al., 2018b; Liang and Rakhlin, 2020) and that positive ridge regularization decreases the performance (Liang and Rakhlin, 2020).”
On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels (2019, background): “…work on nonparametric local rules (Belkin et al., 2018b,d), high-dimensional linear regression (Bartlett et al., 2019; Hastie et al., 2019), random features model (Ghorbani et al., 2019), and kernel (ridgeless) regression (Belkin et al., 2018c; Liang and Rakhlin, 2018; Rakhlin and Zhai, 2018).”
Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks (2019, background): “This is the subject of a few interesting recent papers [5], [37], [42]–[48].”
On the Similarity between the Laplace and Neural Tangent Kernels (2020, methodology): “NTK methods can be analyzed to explain many properties of neural networks in this limit, including their convergence in training and ability to generalize [8, 9, 13, 32].”
Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks (2020, background): “…generalization of overparame-terized neural networks as a consequence of the training procedure since stochastic gradient descent exhibits an implicit bias towards choosing the simplest functions that interpolate the training data (Belkin et al., 2018a;c; Luo et al., 2019; Jacot et al., 2018).”
Reconciling modern machine learning and the bias-variance trade-off (2018, result): “Recently, there has been an emerging recognition that certain interpolating predictors (not based on ERM) can indeed be statistically optimal or near-optimal [2, 4], which is compatible with our empirical observations in the interpolating regime.”