  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 $\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 we show that these indeed concentrate around a value
$\varepsilon^*$, 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.
