Good Classifiers are Abundant in the Interpolating Regime

Abstract

Within the machine learning community, the widely-used uniform convergence framework has been used to answer the question of how complex, over-parameterized models can generalize well to new data. This approach bounds the test error of the worst-case model one could have fit to the data, but it has fundamental limitations. Inspired by the statistical mechanics approach to learning, we formally define and develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers from several model classes. We apply our method to compute this distribution for several real and synthetic datasets, with both linear and random feature classification models. We find that test errors tend to concentrate around a small typical value ${\epsilon }^{\ast }$, which deviates substantially from the test error of the worst-case interpolating model on the same datasets, indicating that "bad" classifiers are extremely rare. We provide theoretical results in a simple setting in which we characterize the full asymptotic distribution of test errors, and we show that these indeed concentrate around a value ${\epsilon }^{\ast }$, which we also identify exactly. We then formalize a more general conjecture supported by our empirical findings. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice, and that approaches based on the statistical mechanics of learning may offer a promising alternative.

References in corpus (17)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• The Loss Surfaces of Multilayer Networks
• Benign Overfitting in Linear Regression
• On Exact Computation with an Infinitely Wide Neural Net
• Elliptical slice sampling
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• Uniform convergence may be unable to explain generalization in deep learning
• The Heavy-Tail Phenomenon in SGD
• Multiplicative noise and heavy tails in stochastic optimization
• Exact expressions for double descent and implicit regularization via surrogate random design
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• On the Approximation Properties of Random ReLU Features
• Integrals over Gaussians under Linear Domain Constraints