Successive Halving and Hyperband

Evaluating a hyperparameter setting properly means training a model to (near) completion with it — but if you're comparing dozens or hundreds of candidate settings, training every one of them fully is enormously wasteful, since most candidates will turn out mediocre and could have been ruled out early. Successive halving exploits a simple observation: a candidate that is performing badly after a small fraction of training is very unlikely to become the best candidate by the end, so you can safely stop investing further compute in it long before training would normally finish.

The analogy: an elimination bracket, not a round-robin

A round-robin tournament has every competitor play every other competitor in full — thorough, but the number of games needed explodes with more competitors. An elimination bracket instead runs a quick round among all competitors, keeps only the winners, gives the survivors a slightly longer next round, and repeats — spending the bulk of the tournament's time on the competitors who have already proven themselves, rather than spreading equal time across everyone including those clearly out of contention. Successive halving runs hyperparameter candidates through exactly this kind of bracket, using "training progress so far" as the elimination criterion instead of a head-to-head match.

The halving schedule

Start with $n$ candidate hyperparameter settings, each given a small training budget $b$. After that budget, rank all $n$ by validation performance, keep only the top half, and double the training budget for that surviving half. Repeat until one (or a small handful) remains:

$$n \to n/2, \qquad b \to 2b \quad \text{at each round}$$

In words: every round, the number of surviving candidates is cut in half, while the training budget given to each survivor doubles — so the total compute spent per round stays roughly constant (half as many candidates, each getting twice the training), and the full original budget of $n$ candidates is spread across rounds rather than multiplied by them.

Hyperband adds one more layer: successive halving needs you to choose upfront how aggressively to eliminate (how many candidates to start with, how small the initial budget is), and get that choice wrong and you either eliminate promising-but-slow-starting candidates too early, or waste too much budget on the first round. Hyperband runs several different successive-halving "brackets" in parallel, each with a different aggressiveness setting, so the overall search hedges against picking the wrong elimination speed for the particular problem at hand.

Worked example 1: halving through three rounds

Start with $n=16$ candidates, initial budget $b=1$ epoch. Round 1: train all 16 for 1 epoch, keep the best 8. Round 2: train those 8 for $b=2$ epochs, keep the best 4. Round 3: train those 4 for $b=4$ epochs, keep the best 2. Round 4: train those 2 for $b=8$ epochs, keep the best 1. Total epochs spent: $16(1) + 8(2) + 4(4) + 2(8) = 16+16+16+16=64$ epochs — compare that to training all 16 candidates fully for, say, 8 epochs each, which would cost $16\times8=128$ epochs, exactly double, for a search that only ever gave its worst candidates 1 epoch to prove themselves before moving on.

Worked example 2: a candidate eliminated too early

Suppose one candidate's hyperparameters happen to make it a "slow starter" — mediocre after 1 epoch, but it would have become the best candidate by epoch 8 if given the chance. Successive halving with an aggressive initial budget of $b=1$ eliminates it in round 1, based on a signal that didn't reflect its long-run quality. This is the known failure mode of successive halving: it assumes performance rank after a small budget predicts performance rank after a large one, which usually holds but not always. Hyperband's parallel brackets, some with much larger initial budgets, hedge against exactly this by ensuring at least one bracket gives candidates more time before eliminating any of them.

What this means in practice

Successive halving and Hyperband are standard components of hyperparameter tuning libraries (Ray Tune, Optuna, and others implement them directly), and they're especially valuable when training a single candidate to completion is expensive — deep learning being the prototypical case. They pair naturally with random search for choosing the candidates in the first place: random search picks what to try, successive halving decides how much budget each try deserves.

Practice

1. Starting with 32 candidates and initial budget 1 epoch, list the number of survivors and their training budget at each round until 1 remains.
2. Why might a very aggressive first-round elimination (keeping only the top 10%) be risky?
3. In one sentence, what specific risk does Hyperband's use of multiple parallel brackets hedge against?