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

Abstract

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.

Cited by in corpus (56)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• Prevalence of Neural Collapse during the terminal phase of deep learning training
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Does data interpolation contradict statistical optimality?
• Do We Need Zero Training Loss After Achieving Zero Training Error?
• The importance of better models in stochastic optimization
• A mean-field limit for certain deep neural networks
• Exact expressions for double descent and implicit regularization via surrogate random design
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Sharper bounds for uniformly stable algorithms
• Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
• Asymptotics of Ridge (less) Regression under General Source Condition
• A Model of Double Descent for High-dimensional Binary Linear Classification
• What causes the test error? Going beyond bias-variance via ANOVA
• The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers
• The Implicit Regularization of Ordinary Least Squares Ensembles
• How do infinite width bounded norm networks look in function space?
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Distributional Generalization: A New Kind of Generalization
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• On the Similarity between the Laplace and Neural Tangent Kernels
• How benign is benign overfitting?
• When Does Preconditioning Help or Hurt Generalization?
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Statistical Optimality of Interpolated Nearest Neighbor Algorithms
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• On Uniform Convergence and Low-Norm Interpolation Learning
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• A Deep Conditioning Treatment of Neural Networks
• Empirical Risk Minimization in the Interpolating Regime with Application to Neural Network Learning
• When does gradient descent with logistic loss find interpolating two-layer networks?
• A Limitation of the PAC-Bayes Framework
• DeepNNK: Explaining deep models and their generalization using polytope interpolation
• Which Minimizer Does My Neural Network Converge To?
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Improving the convergence of SGD through adaptive batch sizes
• Improved Classification Rates for Localized SVMs
• Provable Robust Classification via Learned Smoothed Densities
• The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data
• The Generalization Error of the Minimum-norm Solutions for Over-parameterized Neural Networks
• Generalization error of minimum weighted norm and kernel interpolation
• Dimension Independent Generalization Error by Stochastic Gradient Descent
• Predictive Model Degrees of Freedom in Linear Regression
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Over-parametrized neural networks as under-determined linear systems
• Jitter: Random Jittering Loss Function
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks
• Offline Contextual Bandits with Overparameterized Models
• Relative Flatness and Generalization
• Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression
• Identifying and Exploiting Structures for Reliable Deep Learning