Non-stochastic Best Arm Identification and Hyperparameter Optimization

By Kevin G. Jamieson, Ameet Talwalkar. 2015

692 citations recorded by the source corpus.

Motivated by the task of hyperparameter optimization, we introduce the non-stochastic best-arm identification problem. Within the multi-armed bandit literature, the cumulative regret objective enjoys algorithms and analyses for both the non-stochastic and stochastic settings while to the best of our knowledge, the best-arm identification framework has only been considered in the stochastic setting. We introduce the non-stochastic setting under this framework, identify a known algorithm that is well-suited for this setting, and analyze its behavior. Next, by leveraging the iterative nature of standard machine learning algorithms, we cast hyperparameter optimization as an instance of non-stochastic best-arm identification, and empirically evaluate our proposed algorithm on this task. Our empirical results show that, by allocating more resources to promising hyperparameter settings, we typically achieve comparable test accuracies an order of magnitude faster than baseline methods.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Elucidating image-to-set prediction: An analysis of models, losses and datasets (2019, methodology): “HYPERBAND is a banditbased algorithm that speeds up random search via a more robust variant of the SUCCESSIVEHALVING early-stopping algorithm [22].”
Fine-Tuning Pretrained Language Models: Weight Initializations, Data Orders, and Early Stopping (2020, methodology): “Our algorithm is inspired by existing approaches to making hyperparameter search more efﬁcient by stopping some of the least promising experiments early (Jamieson & Talwalkar, 2016; Li et al., 2018).”
BOHB: Robust and Efficient Hyperparameter Optimization at Scale (2018, background): “Hyperband (Li et al., 2017) is a bandit strategy that dynamically allocates resources to a set of random configurations and uses successive halving (Jamieson & Talwalkar, 2016) to stop poorly performing configurations.”
Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, methodology): “SHA (Jamieson and Talwalkar, 2016) is based on multi-bandit problems (Karnin et al.”
Automated Machine Learning: State-of-The-Art and Open Challenges (2019, background): “It is shown that the successive halving outperforms the uniform budget allocation technique in terms of the computation time, and the number of iterations required [52].”
Benchmark and Survey of Automated Machine Learning Frameworks (2019, background): “SuccessiveHalving (Jamieson & Talwalkar, 2015) solves the selection of s via bandit learning.”
Survey on Automated Machine Learning (2019, background): “SuccessiveHalving (Jamieson and Talwalkar, 2015) solves the selection of s via bandit learning.”
Random Search and Reproducibility for Neural Architecture Search (2019, methodology): “These methods use Bayesian optimization [26; 24; 13], performance prediction [15; 10], or multi-armed bandits [22; 28; 29] to adaptively allocate resources to different configurations.”
Towards Automated Deep Learning: Efficient Joint Neural Architecture and Hyperparameter Search (2018, methodology): “Successive Halving evaluates a large number of conﬁgurations using a small minimum budget b min and continues to evaluate the best η − 1 (by default best-performing third) of these with the next budget η · b min .”
Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, methodology): “The pure-exploration multi-armed bandit problem has a long history in the stochastic setting (Bubeck and Cesa-Bianchi, 2012; Even-Dar et al., 2006), and was recently extended to the non-stochastic setting by Jamieson and Talwalkar (2015).”
Automated Machine Learning: From Principles to Practices (2018, methodology): “However, this method only addresses the coupling between 𝑤 and 𝛼 but the coupling problem in 𝑤 still remains.”
Techniques for Automated Machine Learning (2019, methodology): “To efficiently obtain the performance under a fixed budgets B, successive halving [11] assigns each configuration B n budgets and then select the best half with double budgets in the next Figure 4: The exploration tree for AutoMHL with”
Automated Machine Learning: Methods, Systems, Challenges (2019, positive): “, L out 0 ) = L i−1), (ii) Residual Networks [28], where previous layer outputs are summed (gi(L i−1, .”
Searching Better Architectures for Neural Machine Translation (2020, methodology): “We leverage one-shot model [34], [35] and successive halving [14] to deal with the large search space challenges.”
Symbolic Discovery of Optimization Algorithms (2023, background): “, 2022; Zoph and Le, 2017) and hyperparameter optimization (Dong et al., 2021; Hutter et al., 2011; Jamieson and Talwalkar, 2016; Li et al., 2017), etc.”
Fast Bayesian hyperparameter optimization on large datasets (2017, methodology): “In each iteration i , Hyperband samples n i conﬁgurations randomly and uses successive halving (Jamieson and Talwalkar, 2016) to discard hyperparameter conﬁgurations after evaluating them on subsets of the data.”