Hyperparameter search without overfitting

The winner of a search is flattered

A hyperparameter search tries many settings, scores each on validation data and keeps the best. The trouble is that the best score of many noisy scores is biased upward, even if no setting has any skill. If $N$ settings each have a pure-noise score with standard deviation $\sigma$, the expected best one is about $\sigma\times z_N$, where $z_{10}=1.54$ and $z_{100}=2.51$. With an IC noise of $\sigma=0.02$, the winner of $100$ useless settings looks like $0.050$, a respectable signal that does not exist. Reporting the validation score of the winner as its performance is therefore optimistic, and the more settings you try, the worse it gets.

There are three honest remedies. First, keep a test set that the search never sees and report only its score. Second, use nested cross-validation: an outer loop sets aside a test fold, and inside each outer training set an inner loop runs the search. The outer scores measure the whole procedure, search included. Third, shrink the search: fewer settings, coarser grids and settings that matter. With $K_o$ outer folds, $K_i$ inner folds and $C$ candidates, nested validation needs $K_o(K_iC+1)$ fits, so budget for it. And before you search, ask whether the setting can matter at all.

• The max of noise is not noise: the best of many useless settings looks like skill.
• Nested validation scores the whole procedure, search included, for $K_o(K_iC+1)$ fits.
• Compare with the noise: a gain smaller than one standard error is not a finding.

Lab · what's graded

• The best of 100 useless settings15 pts
• The best of 1010 pts
• Fits of a grid search10 pts
• Fits of nested validation15 pts
• What is left to explain10 pts
• Which search is honest10 pts
• Nested validation10 pts
• Why the winner's score is inflated20 pts