Hyperband

Hyperband's primary subroutine is Successive Halving (SHA), an aggressive early-stopping strategy. It allocates a budget (e.g., epochs, data subset size) to a set of configurations, evaluates them, discards the worst half, and doubles the budget for the survivors, repeating until one configuration remains. This rapidly culls poor performers.

• Process: Start with n configurations and a total budget B. After each round, keep the top 1/η configurations and increase their per-configuration budget by a factor of η.
• Efficiency: Avoids wasting full training cycles on clearly suboptimal hyperparameters.

Hyperband runs multiple Successive Halving instances, called brackets, in parallel, each with a different trade-off between the number of configurations (n) and the budget per configuration (b).

• Low-Fidelity Brackets: Many configurations evaluated with a very small budget (e.g., 1 epoch). Designed for broad exploration.
• High-Fidelity Brackets: Fewer configurations evaluated with a larger budget. Designed for fine-grained exploitation.
• Coverage: This systematic variation across the (n, b) space ensures the algorithm is robust and doesn't rely on a single, potentially unlucky, SHA run.

The algorithm dynamically decides where to invest computational resources. Instead of committing a fixed budget to every configuration upfront, it uses low-fidelity approximations (partial training) to make informed decisions.

• Key Insight: A configuration's performance after a few epochs is often correlated with its final performance. Hyperband exploits this correlation.
• Budget Variable: The resource can be training iterations, dataset size, or model complexity. This makes it adaptable beyond simple epoch-based stopping.
• Result: Computational cycles are shifted from poorly performing configurations to promising ones mid-search.

A major advantage of Hyperband is that it has no hyper-hyperparameters to tune for the search process itself, unlike Bayesian Optimization which requires choosing an acquisition function and kernel. The only required input is the maximum budget per configuration (R) and the proportion of configurations discarded each round (η, typically 3 or 4).

• Deterministic: For fixed R, η, and a random seed, Hyperband's execution path is fully determined.
• Simplicity: This makes it highly reproducible and easy to deploy as a default optimizer, removing a layer of configuration complexity for the ML engineer.

Hyperband provides a principled speedup over both random search and full sequential Bayesian optimization. Its efficiency is derived from its asymptotic optimality under certain assumptions.

• vs. Random Search: Can be 5x to 30x faster, as it stops poor configurations early.
• vs. Bayesian Optimization (BO): More efficient in high-dimensional spaces or with large numbers of parallel workers, as BO's surrogate model becomes a bottleneck.
• Practical Use: It is the default scheduler in libraries like Ray Tune and KerasTuner for its robust, out-of-the-box performance on deep learning tasks.

While powerful alone, Hyperband is often combined with model-based guidance to form BOHB (Bayesian Optimization and HyperBand). BOHB uses Hyperband's bracket structure to manage resources but replaces the random sampling at the start of each Successive Halving bracket with Bayesian Optimization.

• Synergy: Hyperband handles the resource allocation, while the surrogate model (a probabilistic model of performance) guides the selection of which configurations to try, leading to more intelligent exploration.
• Result: BOHB often outperforms both pure Hyperband and pure Bayesian Optimization, achieving state-of-the-art results in automated hyperparameter tuning.

Successive Halving is the foundational subroutine used by Hyperband. It is an aggressive, all-or-nothing resource allocation strategy. The algorithm works in rounds:

• A set of hyperparameter configurations is evaluated for a small, initial resource budget (e.g., a few training epochs).
• Only the top-performing half (or another fraction) of configurations are promoted to the next round.
• The resource budget for the survivors is doubled, and the process repeats until one configuration remains.

This creates a tournament-style elimination, rapidly discarding poor options. Hyperband's innovation is to run multiple Successive Halving brackets with different initial trade-offs between the number of configurations and the resources allocated to each.

Multi-Fidelity Optimization is the general strategy of using cheaper, low-fidelity approximations to guide a search for an optimum measured with high fidelity. In Hyperparameter Optimization (HPO), fidelities are proxies for final model performance. Common low-fidelity proxies include:

• Training on a subset of the data.
• Training for a reduced number of epochs.
• Training with lower image resolution or a smaller model.

Hyperband is a premier multi-fidelity algorithm. It dynamically allocates more resources (higher fidelity) only to the most promising configurations identified via low-fidelity evaluations. This is far more efficient than evaluating all configurations at full cost.

Hyperparameter Optimization (HPO) is the overarching problem that Hyperband solves. Hyperparameters are the settings that govern the model training process itself (e.g., learning rate, batch size, network depth). Unlike model parameters, they are not learned from data and must be set prior to training.

HPO algorithms search this space to maximize validation performance. Key search strategies include:

• Grid Search: Exhaustive but computationally prohibitive.
• Random Search: More efficient baseline.
• Bayesian Optimization: Model-guided, sample-efficient.
• Hyperband: Resource-efficient, based on early stopping.

Hyperband provides a robust, parallelizable baseline that often outperforms random search and can warm-start more complex methods like Bayesian Optimization.

Bayesian Optimization (BO) is a sample-efficient, sequential model-based optimization strategy. It is a primary alternative to Hyperband for HPO. Its core loop is:

1. Build a probabilistic surrogate model (e.g., a Gaussian Process) that predicts model performance for any hyperparameter configuration.
2. Use an acquisition function (e.g., Expected Improvement) to select the most promising next configuration to evaluate, balancing exploration and exploitation.
3. Evaluate the chosen configuration, update the surrogate model, and repeat.

While BO is highly sample-efficient, its sequential nature and model overhead can limit parallelism. Hyperband and BO are often combined: Hyperband can quickly narrow the search space, and BO can perform a refined search on the promising region identified.

Neural Architecture Search (NAS) automates the design of neural network architectures. It treats the network topology (e.g., types of layers, connections) as hyperparameters to be optimized. NAS search spaces are vast and evaluations are extremely expensive.

Hyperband is a critical algorithm for making NAS feasible. It is used as the outer-loop optimizer in many NAS frameworks to manage the resource-intensive training of candidate architectures. By using low-fidelity proxies like training for few epochs, Hyperband can quickly discard poorly designed networks. This approach is foundational in methods like ENAS (Efficient NAS) and is a component of DARTS when tuning hyper-hyperparameters.

Population-Based Training (PBT) is a hybrid algorithm that simultaneously trains and optimizes a population of models. Unlike Hyperband, which is a pure evaluation-and-elimination strategy, PBT allows models to learn and evolve during the search process.

Key mechanics of PBT:

• A population of models is trained in parallel.
• Periodically, poorly performing models are replaced by copying the weights from better performers (exploit).
• Their hyperparameters are then randomly perturbed (explore).

While Hyperband is non-adaptive (hyperparameters are fixed per configuration), PBT dynamically adapts hyperparameters during training. They represent two powerful but philosophically different approaches to automated adaptation: one based on efficient resource allocation, the other on evolutionary competition and online adaptation.