Validation and Hyperparameter Search
Successive halving and Hyperband
Give every candidate a small budget, keep the best third, triple the budget, and repeat — elimination-tournament tuning that spends almost nothing on hopeless candidates.
- 8 min read
- 3 reading levels
- Published
Read these first
On this page 5
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
Successive halving runs a settings tournament: everyone gets a small budget, the best fraction advances, and each round the budget grows.
Think of a singing competition. Ten thousand hopefuls get thirty seconds each at the first audition. Nobody needs a full song to reject most of them. A few hundred advance to a two-minute round. Twelve reach the stage with the live band. The winner gets the full concert.
The scarce resource — judges' time — goes overwhelmingly to promising contestants, and almost none of it is wasted confirming that a weak singer is weak.
Why this had to be invented
Random search gives every configuration the full budget: train to completion, score, repeat. But most configurations are bad, and bad ones usually reveal themselves early. After a sliver of the data, or a few training rounds, they already trail hopelessly.
Paying full price to precisely measure how bad a loser is, hundreds of times, is where a blind search's money goes. The tournament reallocates it: measure everyone cheaply, then spend properly only on survivors. The budget — the thing rationed per round — can be training rows, boosting trees, or training epochs.
How it works
Real numbers from the code below: 333 random configurations, budget = training rows, keep the best third each round.
round 1: 333 candidates × 12 rows each ← everyone auditions cheaply
round 2: 111 candidates × 36 rows
round 3: 37 candidates × 108 rows
round 4: 13 candidates × 324 rows
round 5: 5 candidates × 972 rows
round 6: 2 candidates × 2916 rows ← finalists, near-full dataThe catch: some settings are slow starters — weak on tiny budgets, excellent on big ones. A strict tournament eliminates them in round one, unheard. Hyperband is the insurance policy. It runs several tournaments side by side. Some start with tiny budgets and huge fields; others start with bigger budgets and smaller fields. Slow starters get at least one fair draw.
A real example you have seen
Every audition-based reality show, every sports league with qualifiers before finals, every university shortlisting applications before interviews. Whenever judging everyone fully is unaffordable, civilisation invents successive halving.
Remember this
- Small budget for everyone → keep the best fraction → grow the budget → repeat.
- The budget can be rows, trees, or epochs — anything that makes a trial cheaper.
- Slow starters can be unfairly eliminated; Hyperband hedges with multiple tournaments.
What to learn next
- Optuna — pruning-as-a-service: this lesson's mathematics behind one callback.
- Random search — the proposal engine inside every bracket.
- Learning curves — the curves whose crossing behaviour decides if halving is safe.
Developer — Code and libraries.
Setup
pip install scikit-learn scipyOutputs verified with scikit-learn 1.7.2 and scipy 1.14.1 on CPU. This one takes about a minute — it is, after all, running a 333-candidate tournament.
Version note: in scikit-learn 1.7 the halving searches are still marked experimental, so the enable_halving_search_cv import below is mandatory — without it, the class does not exist.
A 333-candidate tournament for the price of a small grid
from scipy.stats import randint
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.experimental import enable_halving_search_cv # noqa: F401
from sklearn.model_selection import HalvingRandomSearchCV
X, y = make_classification(n_samples=4000, n_features=20, n_informative=8,
flip_y=0.05, random_state=6)
space = {"max_depth": randint(2, 20),
"min_samples_leaf": randint(1, 30),
"max_features": randint(2, 20)}
search = HalvingRandomSearchCV(
RandomForestClassifier(n_estimators=50, random_state=6),
space, resource="n_samples", factor=3, cv=3, random_state=6)
search.fit(X, y)
print("rounds played:", search.n_iterations_)
print("candidates per round:", search.n_candidates_)
print("rows given per round:", search.n_resources_)
print("best settings:", search.best_params_)
print("best CV accuracy:", round(search.best_score_, 3))rounds played: 6
candidates per round: [333, 111, 37, 13, 5, 2]
rows given per round: [12, 36, 108, 324, 972, 2916]
best settings: {'max_depth': 16, 'max_features': 7, 'min_samples_leaf': 2}
best CV accuracy: 0.883Three hundred and thirty-three configurations entered. A full random search over them at 3-fold CV would train roughly a thousand forests on all 4,000 rows; the tournament trained most of its models on 12–108 rows and reserved full-data treatment for two finalists.
The walkthrough
resource="n_samples" rations training rows. The other common choice is the number of boosting rounds or trees — for a model like LightGBM, resource="n_estimators" lets early rounds train tiny ensembles. Epoch-based budgets are the natural fit for neural networks.
factor=3 is the elimination rate: keep the top third, triple the budget. Larger factors are more aggressive — cheaper, but more brutal toward slow starters.
Round one trains on 12 rows. Absurdly small — deliberately. Those scores are nearly noise, but they need only separate the terrible from the plausible, and even 12 rows does some of that. The tournament's later rounds correct early luck among survivors.
HalvingGridSearchCV is the same tournament over an explicit grid. And scikit-learn has no Hyperband implementation — for the multi-tournament hedge, use Optuna's HyperbandPruner or Ray Tune.
Common mistakes
A budget that changes the problem. Halving assumes small-budget performance predicts full-budget performance. Rationing rows mostly satisfies that; rationing epochs interacts badly with learning-rate schedules that depend on total epochs (cosine schedules), making early scores actively misleading. Choose a resource whose small version is an honest preview.
Forgetting the experimental import. ImportError: cannot import name 'HalvingRandomSearchCV' — the enable_halving_search_cv line must run first. Tutorials that omit it break on copy-paste.
Comparing scores across rounds. A score earned on 12 rows and one earned on 2,916 rows are different measurements. Only best_score_ — from the final round — is worth quoting, and even that should be confirmed on an untouched test set.
Being aggressive with a noisy metric. With factor=4 or more and tiny first budgets, good candidates die to score noise in round one. If reruns with different seeds crown very different winners, lower the factor or raise min_resources.
Try it yourself
Rerun with factor=2 and factor=4. Compare total runtime, the round table, and the final score. Then set min_resources=500 — a fairer first audition — and see whether a different configuration survives to win.
What to learn next
- Optuna — pruning-as-a-service: this lesson's mathematics behind one callback.
- Random search — the proposal engine inside every bracket.
- Learning curves — the curves whose crossing behaviour decides if halving is safe.
Researcher — Mathematics and papers.
Successive halving
Given total budget $B$ and $n$ candidates, successive halving (SHA) proceeds in $\lceil \log_\eta n \rceil$ rounds with elimination factor $\eta$: each round runs the surviving $n_i$ candidates with per-candidate budget $r_i$, keeps the top $1/\eta$ fraction, and multiplies the budget by $\eta$. Total spend is $O(B)$ with per-round spend approximately equal — the geometric decay of candidates cancels the geometric growth of budgets.
Origins: Karnin, Koren and Somekh (2013) for multi-armed bandits; Jamieson and Talwalkar (2016), Non-stochastic best arm identification and hyperparameter optimization (AISTATS), for the hyperparameter setting. Their guarantee: under a mild condition on how quickly each arm's intermediate losses converge to its terminal loss, SHA finds a near-best arm using a budget within log factors of an oracle allocation that knew every learning curve in advance.
The slow-starter problem, formalised
SHA's condition fails when learning curves cross late: configuration $a$ trails $b$ at all small budgets but overtakes at large ones. With a single tournament, the choice of the initial per-candidate budget $r_{min}$ encodes an unverifiable assumption about how early curves become rankable.
Hyperband
Li, Jamieson, DeSalvo, Rostamizadeh and Talwalkar (2018), Hyperband: a novel bandit-based approach to hyperparameter optimization (JMLR 18), remove the assumption by grid-searching over it. With maximum per-candidate budget $R$ and $s_{max} = \lfloor \log_\eta R \rfloor$, Hyperband runs $s_{max} + 1$ SHA brackets indexed $s = s_{max}, \dots, 0$; bracket $s$ starts with
$$ n = \left\lceil \frac{s_{max}+1}{s+1}\, \eta^s \right\rceil \text{ candidates at initial budget } r = R\,\eta^{-s} $$
The most aggressive bracket auditions many candidates from tiny budgets; the most conservative bracket ($s=0$) is plain random search at full budget — the built-in hedge. Total cost is a $(s_{max}+1)$ factor over one SHA run, and the regret guarantee is within log factors of the best bracket in hindsight.
Asynchronous and hybrid descendants
- ASHA (Li et al., 2020, A system for massively parallel hyperparameter tuning, MLSys): promotion decisions made asynchronously as results arrive, eliminating the synchronisation barriers that idle workers at round boundaries; the standard at cluster scale.
- BOHB (Falkner, Klein and Hutter, 2018, ICML): Hyperband's scheduling with TPE-style model-based sampling replacing uniform draws — model-guided what to try, bandit-guided how long to run it. Consistently strong in AutoML benchmarks.
- Pruning in Optuna implements the same mathematics per-trial:
MedianPrunerapproximates SHA behaviour;HyperbandPrunerimplements the bracket structure.
Choosing along the search-method spectrum
| trials are… | curves rankable early? | tool |
|---|---|---|
| cheap, parallel | — | random search |
| expensive, few | — | Bayesian optimisation |
| mid-cost, partial results meaningful | yes | SHA / ASHA |
| mid-cost, rankability unknown | unsure | Hyperband / BOHB |
The methods compose rather than compete: modern tuners run model-based samplers for proposals with bandit-based schedulers for budgets, which is exactly the configuration the next lesson's library ships by default.
What to learn next
- Optuna — pruning-as-a-service: this lesson's mathematics behind one callback.
- Random search — the proposal engine inside every bracket.
- Learning curves — the curves whose crossing behaviour decides if halving is safe.