PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization

Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, Ameet Talwalkar

arXiv:1603.06560v4cs.LGstat.ML

TL;DR

Hyperparameter optimization must identify effective configurations despite expensive training and poorly understood interactions among hyperparameters. Hyperband formulates the task as pure-exploration adaptive resource allocation, using early stopping across randomly sampled configurations. It provides theoretical guarantees and was 5× to 30× faster than popular Bayesian optimization algorithms across deep-learning and kernel-based problems.

  • Problem

    Hyperparameter optimization is difficult because model quality depends critically on hyperparameters, while evaluating many configurations is computationally expensive.

  • Method

    Hyperband formulates optimization as a pure-exploration non-stochastic infinite-armed bandit problem and adaptively allocates resources with principled early stopping.

  • Results

    5× to 30× faster than popular Bayesian optimization algorithms across a variety of deep-learning and kernel-based learning problems.

  • Takeaways & Limitations

    Hyperband adapts to unknown convergence rates and validation-loss behavior while evaluating orders-of-magnitude more configurations than black-box Bayesian procedures.

  • Takeaways & Limitations

    Configurations with drastically different convergence rates remain an open challenge because fair elimination comparisons may require adjusted resource allocations.

Abstract

from arXiv · show

Performance of machine learning algorithms depends critically on identifying a good set of hyperparameters. While recent approaches use Bayesian optimization to adaptively select configurations, we focus on speeding up random search through adaptive resource allocation and early-stopping. We formulate hyperparameter optimization as a pure-exploration non-stochastic infinite-armed bandit problem where a predefined resource like iterations, data samples, or features is allocated to randomly sampled configurations. We introduce a novel algorithm, Hyperband, for this framework and analyze its theoretical properties, providing several desirable guarantees. Furthermore, we compare Hyperband with popular Bayesian optimization methods on a suite of hyperparameter optimization problems. We observe that Hyperband can provide over an order-of-magnitude speedup over our competitor set on a variety of deep-learning and kernel-based learning problems.

1. Introduction

Hyperparameter optimization is difficult because model quality depends critically on interacting hyperparameters, while exhaustive or standard adaptive search can be computationally expensive. Hyperband addresses this by combining random configuration sampling with adaptive resource allocation and principled early stopping.

  • Motivation: Hyperparameters critically affect model quality, but their interactions are poorly understood and costly to optimize.Examples include architecture, regularization, and learning rate choices.
  • Motivation: Practitioners often use random or grid search because standard optimization techniques struggle with the growing complexity of machine-learning models.
  • Related approaches: Bayesian optimization adaptively selects configurations but must fit and optimize a high-dimensional, non-convex, potentially noisy function.
  • Adaptive evaluation: Adaptive configuration evaluation allocates more resources to promising configurations and quickly eliminates poor ones.Resources may include training-set size, feature count, or iterations.
  • Contribution: Hyperband formulates optimization as pure-exploration adaptive resource allocation over randomly sampled configurations and uses principled early stopping.The approach makes minimal assumptions and can evaluate orders-of-magnitude more configurations than black-box Bayesian procedures.
  • Results: 5× to 30× faster performance than popular Bayesian optimization algorithms was observed across deep-learning and kernel-based learning problems.The analysis also shows adaptation to unknown convergence rates and validation-loss behavior.

2. Related Work

Prior work studies adaptive configuration selection, adaptive evaluation, and pure-exploration bandits, but existing methods often rely on structural or convergence assumptions. Hyperband instead targets the non-stochastic setting and adapts to unknown distributions without parametric assumptions.

  • Hyperparameter optimization: Bayesian search methods model configuration performance probabilistically and include SMAC, TPE, and Spearmint.These methods use random forests, Parzen estimators, or Gaussian processes to guide configuration selection.
  • Hyperparameter optimization: Bayesian optimization can outperform random search empirically, but standard methods may perform similarly to random search in high-dimensional problems.
  • Adaptive evaluation: Adaptive evaluation methods early-stop poorly performing training procedures, but earlier approaches require parametric convergence assumptions or user-defined heuristics.Violating the assumptions can sharply reduce empirical performance, while heuristic correctness depends on a safety zone.
  • Hybrid methods: Hybrid methods combine adaptive configuration selection with adaptive evaluation, often using Gaussian-process models and assumptions about learning-curve convergence.
  • Bandit approaches: Halving-style bandit algorithms avoid explicit convergence behavior but suffer from the “n versus B/n” problem that Hyperband addresses.
  • Hyperband’s setting: Hyperband automatically adapts to an unknown distribution in the non-stochastic setting without parametric assumptions and can use any hyperparameter sampling approach.Its theoretical results assume sampled validation losses come from a stationary distribution.

3. Hyperband Algorithm

Hyperband uses SuccessiveHalving to allocate a fixed budget across multiple resource-versus-configuration tradeoffs. By cycling through brackets with different initial configuration counts and minimum resources, it addresses uncertainty about how quickly configurations become distinguishable.

  • Successive Halving: SuccessiveHalving uniformly evaluates configurations, discards the worst half, and repeats while allocating more resources to survivors.
  • Intuition: Envelope functions bound intermediate validation losses around terminal losses and shrink as more resources are allocated.Two configurations become distinguishable when their envelopes no longer overlap.
  • Intuition: More resources are needed when envelope functions are wider or terminal losses are closer together.
  • Allocation tradeoff: The optimal configuration count is unknown because envelope functions and the distribution of terminal losses are unavailable in practice.Slow convergence or similar-quality configurations favor fewer configurations, whereas quickly revealed quality favors a larger configuration count.
  • Hyperband: Hyperband evaluates several values of n for a fixed budget B, pairing larger n with smaller initial resource r and more aggressive early stopping.Its inner loop invokes SuccessiveHalving for each tradeoff.
  • Algorithm: Hyperband is presented as an algorithm with inputs R and η, using brackets that vary the resource-allocation schedule.

10 end

Hyperband combines SuccessiveHalving with multiple resource-allocation brackets to address the tradeoff between exploring configurations and training them deeply. It supports several resource types, adapts practical controls such as R and η, and performs competitively in the LeNet example while improving theoretical efficiency.

  • Algorithm design: Hyperband evaluates configurations through SuccessiveHalving while varying n and r across brackets to address the “n versus B/n” problem.Larger n means smaller initial resource r and more aggressive early stopping; the outer loop explores these alternatives.
  • Example application: In the LeNet experiment, R = 81 epochs and η = 3 produced five SuccessiveHalving brackets with different exploration-versus-budget tradeoffs.The search varied learning rate, batch size, and kernel counts for the two network layers.
  • Example application: Across 70 trials, standard Hyperband nearly matched the best individual bracket, s = 3, and outperformed uniform allocation, equivalent to random search.Neither the most aggressive bracket, s = 4, nor the least aggressive bracket, s = 0, was optimal in advance.
  • Resource types: Hyperband can allocate resources as iterations, training time, data-set size, or feature count, including feature subsampling for kernel approximations and deep-learning filters.Data-set subsampling can provide substantial speedups for methods with super-linear training times.
  • Hyperparameter settings: R is the maximum resource per configuration, while η controls the fraction discarded per elimination round and the resulting bracket structure.Smaller R is faster, whereas larger R provides a better guarantee of distinguishing configurations; η = 3 or 4 is recommended in practice.
  • Theoretical results: SuccessiveHalving needs only a small factor above optimal budget allocation, while Hyperband requires only logarithmic-factor overhead relative to SuccessiveHalving despite unknown convergence behavior.This supports Hyperband’s theoretical robustness without requiring knowledge of envelope functions or the distribution of configuration losses.

4. Hyperparameter Optimization Experiments

Experiments across deep-learning, kernel, and multi-dataset problems evaluate Hyperband with several resource types against random search and Bayesian optimization. Hyperband often delivers large speedups, but performance depends on dataset scale, bracket choice, and whether the maximum resource is known.

  • Experimental setup: Hyperband evaluates configurations using iterations, dataset subsamples, or feature samples, comparing against SMAC, TPE, Spearmint, random search, and random 2×.Spearmint is excluded when search spaces contain conditional hyperparameters.
  • Deep-learning experiments: Over 20× faster than random search, Hyperband consistently outperforms random 2× across three image datasets, while SMAC (early) reaches at most 7× speedup within the evaluation window.The first Hyperband result after 5R is often competitive with other searchers after 50R, and Hyperband is less variable across trials.
  • Deep-learning experiments: Repeating bracket s = 4 vastly outperforms other methods on CIFAR-10 and MRBI and nearly ties SMAC (early) for first on SVHN.The most exploratory bracket can be especially effective when configurations reveal quality after little resource.
  • Horizon choice: Finite-horizon Hyperband outperforms its infinite-horizon version within a 50R budget when the maximum resource is known.Infinite-horizon Hyperband underperforms initially because it must also tune the maximum resource and begins with less aggressive early stopping.

5. Theory

The theory formulates hyperparameter optimization as a pure-exploration infinite-armed bandit problem and analyzes Hyperband’s resource allocation and early-stopping guarantees. The results show adaptive performance across unknown convergence and sampling difficulty, including finite-horizon and stochastic special cases.

  • 5.1 Hyperparameter Optimization Problem Statement: Hyperband reduces hyperparameter optimization to pure-exploration resource allocation among randomly sampled configurations, using loss sequences indexed by resource levels.The formulation allows arbitrary continuous, discrete, or categorical configuration spaces and does not use structure relating configurations.
  • 5.1 Hyperparameter Optimization Problem Statement: Hyperband seeks a configuration within ν*−ν* of the optimum while drawing configurations as needed and minimizing total resources, without knowing convergence rates or the limit-loss distribution.The target is expressed as identifying x with ℓ*(x)−ν* small using as few total resources as possible.
  • 5.4 Finite Horizon Setting (R < ∞): The finite-horizon analysis extends the preceding discussion to settings where the maximum resource R is finite and known.Examples include increasing subsets of a full dataset, whose size bounds the available resource.
  • 5.3 Infinite Horizon Setting: SuccessiveHalving provides high-probability guarantees under specified budgets, and its required budget can be substantially smaller than uniform allocation.The comparison attributes the difference to allocating resources near the best arms rather than uniformly distinguishing a broad fraction of arms.
  • 5.3.2 A Parameterization of F and γ for Interpretability: SuccessiveHalving’s budget scales like ∆^-max{α,β}, versus ∆^-(α+β) for uniform allocation, when convergence and sampling difficulty are parameterized by α and β.The parameters capture slower convergence for larger α and greater difficulty sampling a good limit for larger β.
  • 5.3.3 Hyperband Guarantees: Hyperband addresses unknown α and β by selecting among resource-allocation trade-offs rather than requiring the optimal number of configurations or budget in advance.The supplied theory explicitly identifies unknown α and β as the reason neither fixed SuccessiveHalving choice is directly available in practice.
  • 5.3.3 Hyperband Guarantees: In the stochastic setting, Hyperband nearly matches known lower bounds up to poly-logarithmic factors and recovers established K-armed bandit sample-complexity results up to logarithmic factors.The guarantees include identifying an arm in a target best fraction and specialize to identifying the best arm when q=1/K.

6. Conclusion

The conclusion identifies distributed execution, differing configuration convergence rates, and non-random sampling as extensions of Hyperband. It notes both parallelization opportunities and unresolved challenges in making these extensions efficient and robust.

  • Distributed implementations: Hyperband can be parallelized because configurations are independently and randomly sampled, including by distributing SuccessiveHalving brackets across machines.Brackets can be launched asynchronously as machines become available.
  • Distributed implementations: Parallelizing a single bracket can reduce round time, but exponentially decreasing task counts may require a more sophisticated priority queue and introduce overhead.The issue arises when the maximum resource R can be computed on one machine.
  • Adjusting for different convergence rates: Generalizing Hyperband to configurations with drastically different convergence rates remains an open challenge.Such differences can arise from convergence-related hyperparameters or from comparing distinct model families.
  • Incorporating non-random sampling: Alternative sampling schemes, including quasi-random methods and meta-learning-informed priors, may improve Hyperband beyond simple random search.The conclusion proposes Sobol, Latin hypercube, and priors informed by previous experimentation as examples.

Appendix A. Additional Experimental Results

The appendix provides additional details for the experiments presented in Sections 3 and 4.

  • Additional experimental details for Sections 3 and 4 are provided in the appendix.

A.1 LeNet Experiment

The appendix identifies the LeNet experiment’s hyperparameter search space and records a constraint linking kernel counts across layers.

  • The LeNet experiment’s hyperparameter space is shown in Table 2, with Layer-1 kernels upper bounded by Layer-2 kernels.

A.2 Experiments Using Alex Krizhevsky’s CNN Architecture

These experiments evaluate Hyperband and an early-stopping alternative on a fixed convolutional architecture, using validation-loss monitoring and dynamic training resources. The setup specifies the architecture, search space, data splits, and termination schedule.

  • The experiments use the 18% model provided with cuda-convnet for CIFAR-10.
  • The CNN search space includes learning-rate reductions over a maximum iteration window, while some hyperparameters were excluded because of framework or dynamic-resource constraints.
  • Training and validation sets were sampled with balanced classes, while the original test sets were retained for evaluation across CIFAR-10, MRBI, and SVHN.
  • The comparison combines Hyperband with an early-stopping method that extrapolates intermediate validation-error learning curves and terminates configurations unlikely to beat the incumbent.The predicted terminal value is passed to the hyperparameter optimizer after early termination.
  • Validation loss was recorded every 400 iterations, and termination was checked three times during training at dataset-specific intervals.The reported comparison by total iterations is conservative because it excludes time spent fitting learning curves.

A.3 117 Data Sets Experiment

The 117-dataset experiment evaluates searchers under fixed resource and memory limits, using validation and test splits and repeated trials. Its setup also identifies important benchmark limitations arising from heterogeneous dataset sizes and resource scaling.

  • Each searcher was evaluated with a 3GB memory limit, a 6-minute timeout per configuration, and a one-hour window per dataset.Performance was aggregated across datasets using average method rank.
  • The benchmark introduces validation sets alongside training and test sets to reduce overfitting to test data, and reports both validation and test performance.
  • Figure 11 reports average test error across 10 trials, with error bars spanning the top and bottom quartiles for the model with the best validation error.
  • Each dataset-searcher pair was run for 20 trials with fixed data splits and different random seeds for each searcher and trial.
  • The benchmark’s heterogeneous training-set sizes and feature dimensions let random search test 600 configurations on some datasets but only dozens on others.
  • Hyperband’s subsampling advantage is limited on very small datasets, and subsampled training can defer memory errors that occur only when using the full dataset.

A.4 Kernel Classification Experiments

The kernel experiments examine resource-dependent hyperparameter spaces for regularized least squares and random-feature kernel approximation classification. They adjust regularization so the loss–penalty tradeoff remains stable as resources increase and summarize test error across repeated trials.

  • Kernel regularized least squares: The kernel least-squares experiment defines hyperparameters and ranges for the regularized classification search space.
  • Kernel regularized least squares: The cost term C is divided by sample count, while λ is set as the inverse of the scaled cost term.This keeps the tradeoff between summed squared error and the L2 penalty constant as the resource increases.
  • Evaluation: Figures 12 and 13 report average test error with top and bottom quartiles across 10 trials for the best models found in the two kernel experiments.Figure 12 concerns kernel regularized least squares, while Figure 13 concerns random-feature models found by each searcher.
  • Random features: The random-feature experiment defines hyperparameters and ranges for kernel approximation classification, including the number of sampled features.
  • Random features: The random-feature regularization term λ is divided by the number of features to preserve the squared-error–L2-penalty tradeoff as feature resources increase.

B.1 Proof of Theorem 1

The proof analyzes SuccessiveHalving under bounded convergence of arm losses, showing that sufficiently large budgets eliminate suboptimal arms while retaining the best arm or an arm within ε/2 of it. The final selected arm then satisfies an ε-accuracy guarantee.

  • The proof assumes each arm’s loss sequence converges to a terminal loss ν_i and uses a decreasing function γ to bound deviations from that limit.The function γ is defined as the pointwise smallest monotonically decreasing bound.
  • The terminal losses are ordered as ν_1 ≤ ν_2 ≤ ··· ≤ ν_n, and the theorem assumes the budget satisfies B ≥ z_SH.
  • After τ_i resources, arm i’s empirical loss exceeds the best arm’s empirical loss, so SuccessiveHalving eliminates it before or alongside arm 1.
  • If arm 1 is eliminated, every surviving arm has terminal loss at most ν_1 + ε/2.
  • The algorithm either retains arm 1 until selecting it or exits with an arm whose terminal loss is within ε/2 of ν_1.
  • The selected arm’s final empirical loss is within ε of the optimal terminal loss under the stated budget and convergence conditions.The proof combines an ε/4 estimation deviation with an ε/2 terminal-loss gap.

B.2 Proof of Lemma 2

The proof establishes the desired result by conditioning on high-probability events and handling the key inequality through separate cases. It then completes the argument with direct computations.

  • The proof first assumes two events whose intersection has probability at least 1−δ.
  • Under condition (∗), the argument analyzes the relevant maximum through separate cases determined by the relationship between ϵ and νi−ν1.
  • The case analysis establishes the desired result, after which direct computation completes the proof.

B.4 Uniform Allocation

This section analyzes uniform allocation by deriving upper bounds for selecting among randomly sampled configurations and showing that the resulting bound is tight. The proofs use configuration counts, approximation-error control, and budget allocation calculations.

  • Uniform Allocation: Proposition 10 analyzes n randomly sampled configurations trained with a common budget and selects the empirically smallest-loss configuration.The proposition relates the observed losses ℓj to limiting losses ℓ∗ through a uniform approximation bound γ(j) and a distribution function F.
  • Upper Bound: With probability at least 1−δ, the best sampled configuration's limiting loss is bounded using F −1(log(1/δ)/n), with an additional training-error contribution.
  • Budget Analysis: The analysis converts the measurement constraint B=nj into a choice of per-configuration training budget j and extends the accounting to staged resource allocation and generalized elimination rates.The staged proof tracks resources rk and sample counts nk, while γ(R)=0 makes the true loss available at the maximum resource.
  • Lower Bound: The upper bound for uniform allocation is tight: for any admissible F and decreasing γ, a loss sequence exists that requires the stated budget to avoid loss exceeding ϵ with high probability.
  • Proof Construction: The proof partitions configurations into intervals around a threshold bν and uses reflected losses to control empirical selection when configurations fall into neighboring intervals.The construction preserves |ℓj(x)−ℓ∗(x)|≤γ(j) and swaps the roles of the two upper intervals under reflection.
Loading 1603.06560v4…