No Free Lunch for Early Stopping

We show that, with a uniform prior on models having the same training error, early stopping at some fixed training error above the training error minimum results in an increase in expected generalization error.