How do successive halving and Hyperband allocate a fixed tuning budget?

## The resource dimension Both methods need a **budget knob**: something you can give a configuration less of to get a cheaper, noisier estimate of how good it would eventually be. Common choices are training epochs or iterations, the number of boosting rounds in a gradient-boosted ensemble, the size of a training subsample, or the number of cross-validation folds evaluated. Without such a knob neither method applies — that is the first thing to check before proposing them. ## Successive halving Parameters: a set of `n` sampled configurations, a starting budget `r` per configuration, and a cut factor `eta` (3 is the common default despite the name "halving", which implies 2). 1. Train all `n` configurations with budget `r`; score each. 2. Keep the top `n / eta`, discard the rest. 3. Multiply the budget by `eta`. 4. Repeat from step 1 until one configuration remains. With `eta = 3`, `n = 81`, `r = 1`: ``` 81 configs x 1 unit = 81 units 27 configs x 3 units = 81 units 9 configs x 9 units = 81 units 3 configs x 27 units = 81 units 1 config x 81 units = 81 units ``` Total about 405 budget units. Training all 81 configurations to full budget would cost 81 x 81 = 6561 units — roughly sixteen times more for the same final winner, *provided* the early rankings were informative. The equal cost per rung is not a coincidence: dividing the population by `eta` while multiplying the budget by `eta` holds the product constant, and that is the design. ## The n-versus-r dilemma For a fixed total budget `B`, you may run many configurations each briefly, or few configurations each at length. These are opposite bets: - **Aggressive** (large `n`, tiny `r`): broad coverage of the space, but ranking is decided on very short runs, so a configuration that converges slowly and finishes strongest can be eliminated at the first rung. - **Conservative** (small `n`, large `r`): rankings are trustworthy, but you only ever look at a few points in the space. Which is right depends on how strongly the low-budget ranking correlates with the full-budget ranking, and you do not know that in advance for a new problem. ## Hyperband Hyperband's answer is to refuse to guess. It runs a sequence of successive-halving **brackets**, indexed by `s`, each with its own `(n, r)` pair, and gives each bracket a comparable share of the total budget. The largest `s` is the most aggressive bracket — the most configurations, the smallest starting budget. As `s` decreases, brackets start with fewer configurations at larger budgets, and the `s = 0` bracket does no early stopping at all: it simply trains its configurations at full budget and picks the best. The number of brackets follows from the ratio of maximum to minimum budget, roughly `log_eta(R)` where `R` is the maximum budget one configuration may receive. Because one of those brackets matches whatever the true low-fidelity/high-fidelity relationship happens to be, Hyperband is only a logarithmic factor worse than having known the right aggressiveness up front — while a single badly chosen successive-halving run can be arbitrarily bad. The price is that the brackets you did not need still consumed budget. ## Practical notes Configurations for the brackets are usually drawn independently, which means Hyperband decides *how long to run* candidates but not *which candidates to try*. That is why hybrids exist that sample each bracket's configurations from a surrogate fitted to all completed rungs, keeping Hyperband's budget schedule and adding model-based sampling. Within a rung, all configurations can train in parallel, but the rung boundary is a synchronisation point: fast finishers wait for the slowest. Asynchronous successive halving removes that barrier by promoting a configuration as soon as it ranks in the top `1/eta` of the finished results at its rung, which keeps workers busy at the cost of promoting on partial rung information. Finally, remember what the score at each rung means. It is the model's quality *at that budget*, which is not the same as its eventual quality. Reporting the final survivor's small-budget score, or comparing configurations across different rungs, are both mistakes. ## What interviewers listen for That you name the budget knob explicitly, that you can produce the rung arithmetic, and that you can state the assumption both methods rest on — early ranking predicts late ranking — rather than presenting them as free speedups.