CFE 2020: Start Registration
View Submission - CMStatistics
Title: Good classifiers are abundant in the interpolating regime Authors:  Ryan Theisen - UC Berkeley (United States)
Jason Klusowski - Princeton University (United States) [presenting]
Michael Mahoney - UC Berkeley (United States)
Abstract: Within the machine learning community, the widely-used uniform convergence framework seeks to answer the question of how complex, over-parameterized models can generalize well to new data. This approach bounds the test error of the \emph{worst-case} model one could have fit to the data, which presents fundamental limitations. Inspired by the statistical mechanics' approach to learning, we formally define and develop a methodology to precisely compute 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 \emph{typical} value $\varepsilon^*$, 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 show that these indeed concentrate around a value $\varepsilon^*$, which we also identify exactly. 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.