Intermediate28 min

Hyperparameter Search

Grid, random and Bayesian optimisation, successive halving, and budgeting search honestly.

Assumes you know

Hyperparameter Search

Intuition first

Parameters are learned from data. Hyperparameters are the settings you choose before learning: how strong the regularisation, how deep the tree, what learning rate, how many neighbours. They cannot be fitted by the training objective, because the training objective would just set regularisation to zero.

So they are chosen by trial: pick values, cross-validate, keep what scores best. That makes search an outer optimisation loop wrapped around the ordinary training loop, and it is subject to the same overfitting risk one level up. Every configuration you try is another draw from a noisy distribution, and the maximum of many noisy draws is biased upward.

Two things therefore matter: searching efficiently, and not fooling yourself about the result.

Grid search

Enumerate the Cartesian product of candidate values. Exhaustive, reproducible, and exponentially expensive:

\text{fits} = k \times \prod_{j=1}^{m} \lvert V_j \rvert

for $m$ hyperparameters with $\lvert V_j \rvert$ values each and $k$ folds.

Four hyperparameters with five values each, 5-fold CV:

5 \times 5^4 = 5 \times 625 = 3{,}125 \text{ fits}

Random search, and why it wins

Sample configurations at random from distributions instead of enumerating a grid. It is usually better for a fixed budget, for a reason that is worth understanding rather than memorising.

Why random beats grid: the effective dimension argumentAdvanced

Suppose you tune 5 hyperparameters but only 2 of them materially affect performance — the usual situation, since most models have one or two dominant knobs.

Grid search with 4 values per hyperparameter spends $4^5 = 1{,}024$ evaluations, but it only ever tries 4 distinct values of each important hyperparameter. The other 1,020 evaluations vary parameters that do not matter, re-testing the same 4 values of the ones that do.

Random search with the same 1,024 evaluations tries 1,024 distinct values of every hyperparameter, including the two that matter.

Now the probability argument. Suppose the top 5% of the range of an important hyperparameter is what you need to hit. With $N$ random draws, the chance of missing it every time is $(1 - 0.05)^N$ , so

\Prob(\text{at least one hit}) = 1 - 0.95^{N}

N = 20: \; 1 - 0.95^{20} = 1 - 0.358 = 0.642

N = 60: \; 1 - 0.95^{60} = 1 - 0.046 = 0.954

Sixty random draws give a 95% chance of landing in the best 5% of the range — and that figure is independent of how many hyperparameters you are tuning, because each draw samples every dimension simultaneously. Grid search's cost to achieve the same resolution grows exponentially in the number of dimensions.

Sampling on the right scale

\text{learning rate}: \quad \text{log-uniform over } [10^{-5},\, 10^{-1}]

\text{regularisation } \lambda: \quad \text{log-uniform over } [10^{-4},\, 10^{2}]

\text{tree depth}: \quad \text{uniform integer over } [2,\, 20]

Successive halving

Most configurations are visibly bad early. Successive halving exploits that: start many configurations with a small budget, keep the best fraction, give survivors more budget, repeat.

Successive halving. Many configurations start with a small budget; the worst half is discarded at each rung, so compute concentrates on promising candidates.

"Budget" is epochs, training-set fraction, or number of boosting rounds. Hyperband runs successive halving at several aggressiveness levels to hedge against discarding a slow-starting configuration too early.

Bayesian optimisation

Model the objective — validation score as a function of hyperparameters — with a surrogate, usually a Gaussian process or tree ensemble, then choose the next point to evaluate by maximising an acquisition function that balances exploration against exploitation.

Worth it when each evaluation is genuinely expensive, which in practice means minutes or more per fit. For fast models the overhead of fitting the surrogate exceeds the savings. The mechanics are derived in Bayesian Optimisation.

Solved problem 1 · Budgeting a search honestly

You have 6 hours of compute. One model fit takes 40 seconds. You want 5-fold cross-validation. Four hyperparameters to tune. Compare grid and random search, then estimate the selection optimism.

Step 1 — total fits affordable

6 \text{ hours} = 21{,}600 \text{ seconds}

\frac{21{,}600}{40} = 540 \text{ fits}

Step 2 — configurations, given 5-fold CV

\frac{540}{5} = 108 \text{ configurations}

Step 3 — what grid search can cover

With 4 hyperparameters, a grid of $g$ values each needs $g^4$ configurations:

g = 3: \; 3^4 = 81 \; \checkmark \qquad g = 4: \; 4^4 = 256 \; \times

So grid search affords only 3 values per hyperparameter. For a learning rate spanning $10^{-5}$ to $10^{-1}$ , three values means testing $10^{-5}, 10^{-3}, 10^{-1}$ — extremely coarse.

Step 4 — what random search gets for the same budget

108 configurations, each with a distinct value of all four hyperparameters. Using the formula from the derivation, the probability of landing in the best 5% of at least one important dimension is

1 - 0.95^{108} \approx 1 - 0.0038 = 0.996

Effectively certain, versus grid search's three coarse grid points.

Step 5 — estimate the selection optimism

Suppose the validation set is 2,000 rows and accuracy is near 0.85. Standard error of one configuration's estimate:

\text{SE} = \sqrt{\frac{0.85 \times 0.15}{2000}} = \sqrt{6.375 \times 10^{-5}} \approx 0.00798

Optimism from maximising over $m = 108$ noisy estimates:

\text{SE} \times \sqrt{2 \ln 108} = 0.00798 \times \sqrt{2 \times 4.682} = 0.00798 \times 3.06 \approx 0.0244

Step 6 — conclude

Random search, 108 configurations sampled log-uniformly where appropriate. And expect the winning cross-validation score to be roughly 2.4 accuracy points optimistic — so hold out a test set, or use nested CV, rather than reporting the search's own best score.

Answer

540 fits, 108 configurations. Grid search affords only 3 values per hyperparameter; random search gets 108 distinct values per dimension and a 99.6% chance of hitting a good region. Budget the optimism at about 2.4 points and reserve untouched data to measure it.

In code

python

import numpy as np
from scipy.stats import loguniform, randint
from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.model_selection import RandomizedSearchCV, StratifiedKFold, train_test_split
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=6000, n_features=25, n_informative=10,
                           random_state=0)
X_rest, X_test, y_rest, y_test = train_test_split(X, y, test_size=0.2,
                                                  stratify=y, random_state=0)

# Log-uniform for multiplicative parameters, integer-uniform for structural ones.
space = {
    "learning_rate": loguniform(1e-3, 3e-1),
    "max_leaf_nodes": randint(8, 128),
    "min_samples_leaf": randint(5, 80),
    "l2_regularization": loguniform(1e-6, 1e1),
}

search = RandomizedSearchCV(
    HistGradientBoostingClassifier(random_state=0),
    param_distributions=space,
    n_iter=60,
    cv=StratifiedKFold(5, shuffle=True, random_state=1),
    scoring="roc_auc",
    random_state=0,
    n_jobs=-1,
).fit(X_rest, y_rest)

print(f"best CV AUC   {search.best_score_:.4f}")
print(f"test AUC      {search.score(X_test, y_test):.4f}   <- the honest number")
print(f"optimism      {search.best_score_ - search.score(X_test, y_test):+.4f}")
for k, v in search.best_params_.items():
    print(f"  {k:20s} {v}")

The optimism line is the point. Print it every time, and it stops being a surprise.

Exercise 1

A colleague runs 2,000 random configurations on a 500-row validation set and reports 0.94 accuracy. What do you expect on new data?

Show solution

Substantially less. Two compounding problems.

Selection optimism. With 500 validation rows at accuracy near 0.94:

\text{SE} = \sqrt{\frac{0.94 \times 0.06}{500}} \approx \sqrt{1.128 \times 10^{-4}} \approx 0.0106

Maximising over 2,000 configurations:

0.0106 \times \sqrt{2 \ln 2000} = 0.0106 \times \sqrt{15.2} \approx 0.0106 \times 3.90 \approx 0.041

So roughly 4 points of pure selection optimism, putting the honest estimate near 0.90.

Validation set exhaustion. 2,000 evaluations against 500 rows is four configurations per row. At that ratio the winning configuration is substantially fitted to the validation set — it has effectively become a training set with 2,000 degrees of freedom available to exploit it.

What to do: retrain the chosen configuration and evaluate once on a genuinely untouched test set, and treat 0.94 as uninformative. For a number that has to be trusted, nested cross-validation. And reduce n_iter — with 500 rows, 2,000 configurations is far past the point where extra search buys anything real.

Exercise 2

Why does tuning a learning rate on a log scale matter more than tuning tree depth on a log scale?

Show solution

Because the two quantities have different natural geometry.

A learning rate acts multiplicatively on every update. The meaningful comparison between two rates is their ratio, not their difference: $0.001$ versus $0.01$ is a tenfold change in step size and will behave completely differently, while $0.09$ versus $0.10$ is an 11% change and behaves almost identically. Performance is roughly smooth in $\log(\text{lr})$ , so uniform sampling in log space places candidates evenly across regimes.

Sampled uniformly on $[10^{-5}, 10^{-1}]$ , about 90% of draws fall in $[0.01, 0.1]$ — a single regime — and the $10^{-4}$ region is sampled with probability about 0.001.

Tree depth is additive and bounded. It ranges over a small set of integers, perhaps 2 to 20, and each increment roughly doubles the number of leaves — so depth is already a logarithmic parameterisation of model capacity. Depth 4 to 5 is a meaningful change; there is no wide dynamic range to compress, and uniform integer sampling covers it evenly.

General rule: sample log-uniformly for parameters that span orders of magnitude and act multiplicatively — learning rates, regularisation strengths, variances, C in an SVM. Sample uniformly for bounded counts and structural integers — depth, number of neighbours, number of components.

Next: The No Free Lunch Theorem, which explains why no amount of search produces a model that is best everywhere.