Hyperparameter Search Hygiene
Why random search beats grid search, how early-stopping schedulers change the budget calculation, and the selection bias that makes the best run's reported score an overestimate.
Hyperparameter search is an experiment about experiments, and it inherits every statistical hazard of the underlying evaluation plus a few of its own. The largest of those is that the winner's score is biased upward by the act of choosing it, and almost nobody corrects for it.
Random beats grid, for a specific reason
Grid search over \(k\) values of each of \(d\) hyperparameters costs \(k^d\) trials and evaluates each individual hyperparameter at only \(k\) distinct values. Random search with the same budget evaluates each hyperparameter at as many distinct values as there are trials.
That matters because hyperparameter importance is highly unequal: typically one or two dominate and the rest barely matter (Bergstra and Bengio, 2012, Random Search for Hyper-Parameter Optimization, JMLR 13:281-305). Grid search spends most of its budget varying parameters that do not matter while sampling the important one coarsely. Random search covers the important dimension finely without knowing in advance which it is, which is why it is the correct default and grid search is not.
Bayesian optimisation improves on random search by modelling the response surface and sampling where the expected improvement is highest. It pays off when trials are expensive and the budget is moderate, and it adds sequential dependence, so it parallelises less cleanly than random search.
Early stopping changes the budget arithmetic
Successive halving allocates a small budget to many configurations, keeps the best fraction, and repeats with a larger budget. Hyperband runs several such brackets with different aggressiveness, hedging against the case where a configuration is slow to start but eventually best.
The gain is large: the same total compute evaluates far more configurations, because bad ones are killed early. The assumption is that early performance predicts final performance, which is usually true and fails specifically for configurations with long warmup or low learning rates that improve late. Hyperband's multiple brackets exist to bound that failure rather than to eliminate it.
The winner's curse
Run 200 configurations, take the best validation score, and report it. That number is biased upward, because selecting the maximum of 200 noisy estimates selects partly for genuine quality and partly for favourable noise. The more configurations searched and the noisier the evaluation, the larger the bias.
The correction is structural: hold out a third split, used once, to report the chosen configuration's performance. The validation set selects; the test set measures. Reporting the validation maximum as the model's performance is one of the most common overstatements in applied machine learning, and it is why a model's production performance so reliably comes in below its reported number.
When it breaks
Search space bounds are usually the binding constraint. If the optimum lies outside the range searched, no algorithm finds it, and the best trial sitting at a boundary is the diagnostic. Log-uniform sampling for learning rates and regularisation strengths matters too, since these span orders of magnitude and uniform sampling wastes nearly all trials in the top decade.
Tuning on the same data used for feature selection compounds the bias. Each selection step over the same split adds overfitting, and the total is worse than any single step suggests. Nested cross-validation is the correct procedure and is expensive enough that it is usually skipped and rarely acknowledged.
Results do not transfer across scale. Hyperparameters tuned at small scale often do not hold at large scale, which is the entire motivation for parameterisations designed to make them transfer. Tuning on a small model and applying to a large one is a reasonable default and an assumption that should be stated and spot-checked.
Parallel search and early stopping interact badly. Asynchronous successive halving must decide whether to stop a trial before all its peers have reported, so the comparison group is incomplete and the decision is noisier than the synchronous version. It parallelises far better, and the tradeoff should be a deliberate choice rather than a default inherited from a tutorial.
14 flashcards for this concept
Click a card to reveal the answer.