Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization

Training a neural network requires choosing hyperparameters — learning rate, batch size, number of layers, regularization strength — and the final model's quality depends critically on these choices. By 2016, practitioners had two main approaches:

• Random search: sample configurations uniformly and train each to completion. Simple and embarrassingly parallel, but it wastes enormous compute on configurations that are obviously bad after a few epochs.

• Bayesian optimization (SMAC, TPE, Spearmint): build a probabilistic model of the loss surface and adaptively choose the next configuration to try. Smarter than random, but each configuration is still trained to completion, and the surrogate model struggles in high-dimensional spaces.

Both approaches treat every configuration equally: whether a configuration is obviously terrible or potentially great, it gets the same training budget. The waste is staggering — most of the compute goes to configurations that never had a chance.

Given a fixed compute budget $B$, you face a fundamental tradeoff. You can either:

• Go wide: try many configurations $n$ with small average budget $B/n$ each. This works when bad configurations reveal themselves quickly (the loss curve diverges or plateaus early).

• Go deep: try few configurations with large average budget each. This works when configurations converge slowly and you need a long training run to distinguish good from great.

The optimal strategy depends on two unknowns: (1) how fast configurations converge (the envelope function $\gamma$), and (2) how often a random configuration is good (the distribution $F$ of terminal losses). Without knowing either, practitioners are guessing — and guessing wrong can waste orders of magnitude of compute.

Before understanding Hyperband, we need its inner subroutine: Successive Halving. The idea is exactly what the name says:

1. Start with $n$ randomly sampled configurations.
2. Allocate a small budget to each and train them all.
3. Evaluate the validation loss of each configuration.
4. Discard the worst $1/\eta$ fraction (typically the bottom two-thirds with $\eta = 3$).
5. Increase the budget for the survivors by a factor of $\eta$.
6. Repeat until one configuration remains.

Each round eliminates the weakest competitors and gives more resources to the survivors — exponentially more resources go to the most promising configurations. Think of it as a tournament bracket where losers are eliminated in each round and winners get promoted to longer matches.

Hyperband's insight is simple but powerful: instead of guessing the right n, try several values of n simultaneously. It runs Successive Halving multiple times, each with a different tradeoff between exploration (large $n$, small starting budget) and exploitation (small $n$, large starting budget). Each such run is called a bracket.

The algorithm requires just two inputs:

• $R$: the maximum resource per configuration (e.g. 81 epochs)
• $\eta$: the discard factor (default 3 — keep the top third each round)

From these, Hyperband computes $s_{\max} = \lfloor \log_\eta(R) \rfloor$ brackets. The most aggressive bracket ($s = s_{\max}$) starts with the most configurations and the smallest initial budget. The least aggressive bracket ($s = 0$) is just classical random search — every configuration gets $R$ resources.

Here is a concrete example with $R = 81$ and $\eta = 3$, giving $s_{\max} = 4$ brackets. Each bracket uses approximately the same total budget $B = (s_{\max} + 1) \times R = 405$:

Bracket $s = 4$ (most aggressive): Start with 81 configurations at 1 epoch each. After each round, keep the top third and triple the budget. Final round: 1 survivor at 81 epochs. This bracket explores broadly.

Bracket $s = 0$ (least aggressive): Start with 5 configurations at 81 epochs each. No early-stopping at all — pure random search. This bracket exploits deeply.

Brackets $s = 3, 2, 1$ interpolate between these extremes. Together, they cover every reasonable tradeoff. No matter which scenario you face — fast-converging or slow-converging — at least one bracket is near-optimal for it.

Hyperband frames hyperparameter optimization as a pure-exploration non-stochastic infinite-armed bandit problem. Here is the mapping:

• Each arm is a hyperparameter configuration sampled from the search space.
• Pulling an arm $k$ times means training that configuration for $k$ units of resource (epochs, data samples, features).
• The loss after $k$ pulls is the validation error of the partially trained model.
• The terminal loss $\nu_i = \lim_{k \to \infty} \ell_{i,k}$ is the validation error at convergence.
• The goal is to find the arm with the smallest terminal loss using as few total pulls as possible.

Unlike classical bandit problems where each arm gives a stochastic reward from a fixed distribution, here the losses are non-stochastic — the validation error after $k$ epochs is a deterministic function of the configuration and the training procedure. This makes the problem harder because we cannot estimate the terminal loss by averaging.

The theoretical analysis of Hyperband revolves around two unknown quantities:

• The envelope function $\gamma(j)$: a bound on how far the intermediate loss $\ell_{i,k}$ can be from the terminal loss $\nu_i$ after $k$ units of resource. A fast-decaying $\gamma$ means configurations converge quickly. Parameterized as $\gamma(j) \approx j^{-1/\alpha}$ where large $\alpha$ means slow convergence.

• The distribution $F$ of terminal losses: how often a randomly sampled configuration is good. Parameterized as $F(\nu^* + \varepsilon) \approx \varepsilon^{\beta}$ where large $\beta$ means good configurations are rare.

Successive Halving's budget scales like $\Delta^{-\max\{\alpha, \beta\}}$ while uniform allocation (random search) scales like $\Delta^{-(\alpha + \beta)}$ to achieve the same error $\Delta$. The gap can be enormous. Hyperband, without knowing $\alpha$ or $\beta$, achieves a budget within log factors of Successive Halving with the optimal bracket.

Deploying Hyperband in practice requires setting $R$ and $\eta$. Here are the authors' recommendations:

• Setting $R$: Use the natural maximum training budget for one configuration. For neural networks, a common rule-of-thumb number of epochs. For data subsampling, the full dataset size. Smaller $R$ gives faster results; larger $R$ gives better guarantees.

• Setting $\eta$: Values of 3 or 4 are recommended. Larger $\eta$ means more aggressive elimination (fewer rounds, faster, but higher risk of cutting good configurations). The theory suggests $\eta = e \approx 2.718$ is optimal, but 3 works well in practice.

• Number of brackets: Aim for approximately 5 brackets — enough to cover the range of tradeoffs without excessive overhead.

• Resource-dependent hyperparameters: If a hyperparameter should change with the resource (e.g. max tree depth with dataset size), try to decouple them. Hyperband struggles when the optimal setting at low resource differs from that at high resource.

A powerful aspect of Hyperband is that the "resource" need not be training iterations. Any quantity that correlates with model quality and whose cost scales can serve:

• Iterations/epochs: The most common. Train for $r$ epochs, evaluate, and decide.

• Dataset subsampling: Train on a random subset of the data. Especially effective for models with super-linear training time (like kernel methods), where 8× less data can mean 64× less compute.

• Feature subsampling: For random feature approximations of kernel methods, the number of random features serves as the resource.

• Time: Allocate wall-clock training time directly. Useful when different configurations have different per-epoch costs.

The only requirement is that model quality should generally improve (or at least not degrade) as the resource increases. Hyperband makes no assumption about how fast quality improves — it adapts to whatever rate it encounters.

The authors benchmarked Hyperband against SMAC, TPE, Spearmint, and random search on a diverse set of problems:

• CIFAR-10 CNN (8-dimensional search space): Hyperband was over 10× faster than all Bayesian methods. The first result after just $5R$ budget was competitive with results from other methods after $50R$.

• Kernel classification (6-dimensional): Hyperband evaluated 250+ configurations in the time it took competitors to evaluate 3, achieving 30× speedup over Bayesian methods and 70× over random search.

• 117 datasets (110-dimensional AutoML space): On the subset of 21 datasets where downsampling was effective, Hyperband outperformed all methods including random 2×.

• Random feature kernel approximation: Hyperband achieved 6× speedup — more modest because the 3-dimensional search space was low enough for random search to cover well.

A key finding: Hyperband's first result (after the first bracket) was often competitive with the final results of other methods that ran 10× longer. It was also less variable across trials, which is highly desirable in practice.

Today Hyperband is the default early-stopping scheduler in Ray Tune, Optuna, Keras Tuner, and Determined AI. Its conceptual children — BOHB, ASHA, PriorBand — continue to evolve. The bridge it built between bandit theory and AutoML remains one of the most productive cross-pollinations in modern machine learning.