Bayesian Optimisation, Successive Halving and Early Termination
When a trial costs hours, spend the trials sequentially: model the objective from the trials so far, choose the next one to balance exploration and exploitation, and kill trials that are clearly losing before they finish.
The problem, the obvious approach, and why it breaks
Every lesson starts where the work starts: someone has a problem, and the first model that comes to mind looks fine offline.
When each trial is expensive, how does the search use what it has already learned to place the next trial — and to stop a trial that is not going to win?
A speech team fine-tunes a pretrained acoustic model for a new language. One trial takes eleven GPU-hours. They have budget for about forty trials across six settings, and the last random search spent half of them on learning rates that diverged in the first epoch.
Run random search. It is robust, it parallelises perfectly, and it does not need any assumptions about the shape of the objective. Forty trials is forty independent draws.
Forty independent draws learn nothing from each other. The tenth trial does not know that the first nine all diverged above a certain learning rate, and draws from the same range.
- Forty independent draws learn nothing from each other. The tenth trial does not know that the first nine all diverged above a certain learning rate, and draws from the same range.
- Every trial runs to completion. A trial that is clearly worse than the current best after two of twelve epochs still burns the remaining ten, because nothing is watching.
- The budget produces a winner and no map: the team cannot say where the good region is, only which of forty points was best, and the next language starts from nothing.
What is being predicted, and from what data
This domain leads with these two. A target nobody defined precisely is a label nobody can trust, and a dataset nobody can describe is a model nobody can debug.
- Minimise word error rate on a held-out validation set of transcribed audio in the new language. The label is the human transcript.
- The search objective is validation error after fine-tuning, as a function of learning rate, warm-up, layer-freezing depth, batch size, dropout and weight decay.
- Two hundred hours of transcribed audio, split by speaker so no speaker appears in both training and validation (Group Split). A trial's objective is one number per completed run.
- Each trial also emits a validation curve per epoch, which the random search ignored and which contains most of the information about whether the trial will win.
How it actually works
Precisely enough to predict its behaviour — not a framework API.
- Bayesian optimisation keeps a surrogate model of the objective — a cheap statistical model fitted to the (config, score) pairs observed so far, most often a Gaussian process, which gives a predicted score and an uncertainty at every untried config. It replaces the expensive objective with something that can be queried thousands of times.
- An acquisition function turns the surrogate's prediction and uncertainty into a score for "how worthwhile is trying this next". Expected improvement, for example, is high where the surrogate predicts a good score (exploitation) and also where the surrogate is very uncertain (exploration). The next trial is the config that maximises acquisition; the result updates the surrogate; repeat. It is inherently sequential, because each choice depends on the last result.
- Successive halving attacks the other waste: start many trials with a small budget each (one epoch), keep the best fraction, give the survivors a larger budget, and repeat until one remains. It assumes a trial that is bad early will be bad late — which is mostly true for learning rate and often false for regularisation, which can look worse early and win late. Early termination is the same idea applied per trial: stop a run whose validation curve is below the median of completed runs at the same epoch.
A model of the objective
After five trials you know five points of a six-dimensional function. A Gaussian process fitted to them gives you a smooth guess at every other point, plus a band of uncertainty that is narrow near the observed points and wide far from them. That band is the whole trick: it tells the search where it does not know.
The acquisition function reads the guess and the band together. A point predicted to be excellent with a narrow band is worth exploiting. A point predicted to be mediocre with a very wide band is worth exploring, because the band includes excellent. The next trial maximises this; the result narrows the band there; the loop continues.
- 1Fit surrogate
Fit a cheap model to every (config, score) pair so far; it predicts a mean and an uncertainty at any config.
fails by A space with the wrong scale (linear instead of log for the learning rate) makes the surrogate's smoothness assumption false.
- 2Maximise acquisition
Score every candidate config by predicted improvement weighted by uncertainty; pick the maximum. This step is cheap and can search the space densely.
fails by An acquisition that weights exploration too little sits in the first good region it finds and never leaves.
- 3Run the trial
Train with the chosen config, on the training split, and score on the validation split. This is the expensive step and the only one that touches data.
fails by Seed noise on a small validation set makes the score a noisy observation the surrogate treats as exact.
- 4Update and repeat
Add the result, refit, choose again. Stop at the budget, or when the best predicted improvement is below what a trial costs.
fails by Stopping on "no improvement for three rounds" in a noisy objective stops early on a lucky plateau.
The loop touches the validation set once per iteration. Forty iterations is forty selections against the same labels — the optimism of the winner is the same as for any other search of forty trials, and the test set is still opened once, afterward.
Stopping trials that are losing
The other half of the budget goes to runs that were never going to win. Successive halving starts with, say, thirty-two configurations at one epoch each, keeps the best sixteen for two more epochs, the best eight for four, and so on. Most of the budget goes to the few survivors, and a full run is paid for only by configurations that earned it.
The price is the assumption that early rank predicts late rank. For the learning rate that is nearly always true: a divergent run is divergent at epoch one. For regularisation it is frequently false — a heavily regularised run trails at epoch two and wins at epoch twelve — and the halving rule will kill it before it can show that.
| Trigger | Symptom | Cause | Response |
|---|---|---|---|
| Patience set to one epoch | Every high-dropout or high-weight-decay configuration is killed; the winner is barely regularised | Regularised runs start slow by construction; the rule measured start speed, not final quality | Set patience from the learning curves of completed runs; let a sample of "losers" finish to measure the kill rule's false-negative rate |
| Validation curve is noisy per epoch | Good runs are killed on an unlucky epoch; the surviving set is partly random | A single-epoch reading is compared to a median with no smoothing | Compare a smoothed curve, or require the run to trail for several consecutive checks |
| Halving rung too coarse | The best configuration was eliminated at the first rung with sixteen others | Rung one gave each config too little budget to differentiate signal from warm-up | Start the first rung at the point where completed curves begin to separate, not at epoch one |
When the map is worth more than the winner
A random search produces a winner. A sequential search produces a winner and a surrogate — a fitted guess at the objective over the whole space, with a record of where it is confident. For the next language, the next quarter's data or the next model size, the surrogate is a starting point, and the winner is a single point that may no longer be right.
That reuse rests on an assumption that has to be checked rather than hoped: that the good region is a property of the model family and not of the particular dataset. When it is, the second search is short. When it is not, a surrogate that starts confident in the wrong place is worse than starting blind.
The region of hyperparameter space that won on this dataset is close to the region that will win on the next dataset of the same kind, so a surrogate warm-started from these trials points the next search in the right direction.
holds when The datasets are of similar size and modality, the model family and its preprocessing are unchanged, and the settings that mattered were optimisation settings, which depend more on the architecture than on the data.
breaks when The next dataset is much smaller or larger, which moves the best regularisation and batch size; the pretrained base changes; the settings that mattered were capacity settings, which depend on the data.
respond Discard the warm start and search from a wide prior. Keep the old trials as a record, not as evidence about the new data.
| Option | Quality | Cost | Operational | Note |
|---|---|---|---|---|
| Grid | Six settings makes any grid too coarse to be useful at forty trials; trivially parallel and readable. | |||
| Random | Robust and parallel; learns nothing between trials and runs every trial to completion. | |||
| Bayesian | Uses each result to place the next; sequential, with its own settings to get wrong. | |||
| Random + early termination | Keeps parallelism, saves most of the budget on losers; risks killing slow-starting configurations. |
caveat The scores assume an eleven-hour trial and six settings. At a four-second trial the cost column inverts — sequential overhead dominates — and at thirty settings the surrogate's quality falls toward random. Nothing in the matrix captures the value of the map a sequential method leaves behind, or the invisible loss from configurations that early termination killed.
How to build it
Most important first.
- Use a sequential method when a trial costs more than the overhead of choosing — hours, not seconds — and the number of settings is modest, roughly under twenty. Below that cost, random search is simpler and parallelises better.
- Give the surrogate the right space: log-scale for learning rate and weight decay, integer for layers and batch size, and a bounded range that excludes values already known to diverge. A surrogate over a badly shaped space wastes its early trials rediscovering the shape.
- Combine with early termination, but set the patience from the learning curves you have: a rule that kills after one epoch will kill every heavily regularised configuration before it has a chance.
- Record the surrogate's state along with the trials (Experiment Tracking). The map of the objective is the reusable output; the winner is the disposable one.
What to measure
Which number actually maps to the decision — and which numbers look relevant and are not.
- Best validation score as a function of cumulative GPU-hours, against the same curve for random search on the same budget. This is the number that says whether the method earned its complexity.
- The fraction of the budget spent on trials that were terminated early, and how many of those would have won — checked by occasionally letting a "losing" trial finish.
- Do not measure "trials to convergence" — a sequential method that converges in fifteen trials to a local optimum has not beaten a random search that found a better region in forty.
What must stay true after deployment
The field this whole domain exists for. A model is a set of assumptions with weights attached; these are the ones a monitor or a test should be checking.
- The objective is smooth enough in the search space that a surrogate can interpolate between trials; a setting whose effect is discontinuous — a layer count that changes the architecture — breaks the surrogate's assumption and should be searched separately.
- A trial that is behind at an early budget stays behind at full budget, to a degree the termination rule's patience accounts for; this holds for optimisation settings and often does not for regularisation.
- The validation set judging every trial was not read by the final report, and the sequential search's many evaluations against it carry the same selection optimism as any other search (Metric Uncertainty).
- Offline: rerun the search with a different seed for the surrogate's initial trials. A method that lands in a different region each time is exploring a noisy objective, and its winner should be treated as one sample.
- Online: the winning configuration is a fine-tuning recipe, and the deployed model is judged on production transcripts, not on the validation set that chose it (Offline vs Online Evaluation).
- Over time: when the next language arrives, start the surrogate from the previous language's trials and check whether the good region moved. If it did, the map was language-specific and its reuse value is smaller than hoped.
What can go wrong
- The surrogate is confident and wrong in a region it never sampled, because the early trials were all in one corner; the acquisition function keeps exploiting a local optimum and the search never leaves it.
- Early termination kills every configuration with high dropout at epoch two, and the winner is the least-regularised trial — which then overfits on the next language where the data is smaller.
- The objective is noisy across seeds and the surrogate treats a lucky seed as a good region, then spends five trials confirming the luck (Random Seeds).
- A sequential search cannot use forty machines at once; asynchronous variants exist and pay for parallelism with a less informed choice per trial.
- The surrogate and acquisition function are themselves choices with settings — kernel, prior, exploration weight — and they can be tuned badly. A method that exists to remove hand-tuning has introduced a smaller amount of it.
- Early termination saves budget in proportion to how aggressive it is, and loses good configurations in the same proportion. The saving is certain and the loss is invisible.
- "Bayesian optimisation finds the global optimum." It finds a good point within a budget, with a bias toward regions it has already sampled. Its surrogate is a guess about places it has never been.
- "Successive halving is strictly better — it evaluates more configs for the same budget." It evaluates more configs at low budget, which is a different question. Whether the answer transfers to full budget depends on which settings are being compared.
- "With a sequential method we can tune on the test set, since we only look at it once per trial." Once per trial is many times. The method is a loop over evaluations, and every evaluation is a use.
Where this applies
ML advice is stated as universal far more often than it is. These labels say what each claim is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- SCALE-SPECIFICThe methods in this lesson earn their overhead when a trial costs hours and the setting count is modest; for a model that trains in seconds, random search over thousands of trials is simpler, parallel and just as good.
- MODEL-SPECIFICEarly termination on learning curves assumes a run that trails early keeps trailing, which holds for learning-rate and optimizer settings and frequently fails for regularisation settings and for architectures with a long warm-up.
- SIMPLIFIEDThe surrogate is described as a Gaussian process with expected improvement, which is one of several choices; tree-structured estimators and random-forest surrogates behave differently in high dimensions and with categorical settings, and the exploration / exploitation picture here is the shape of the idea rather than any one implementation.
Where the depth lives
This domain teaches the model and hands the rest off by name.