Testing for Overfitting
James Schmidt
High complexity models are notorious in machine learning for overfitting, a
phenomenon in which models well represent data but fail to generalize an
underlying data generating process. A typical procedure for circumventing
overfitting computes empirical risk on a holdout set and halts once (or flags
that/when) it begins to increase. Such practice often helps in outputting a
well-generalizing model, but justification for why it works is primarily
heuristic.
  We discuss the overfitting problem and explain why standard asymptotic and
concentration results do not hold for evaluation with training data. We then
proceed to introduce and argue for a hypothesis test by means of which both
model performance may be evaluated using training data, and overfitting
quantitatively defined and detected. We rely on said concentration bounds which
guarantee that empirical means should, with high probability, approximate their
true mean to conclude that they should approximate each other. We stipulate
conditions under which this test is valid, describe how the test may be used
for identifying overfitting, articulate a further nuance according to which
distributional shift may be flagged, and highlight an alternative notion of
learning which usefully captures generalization in the absence of uniform PAC
guarantees.