2016

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization

Li, Lisha, Jamieson, Kevin, DeSalvo, Giulia et al.

Understand

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.

Built on

The racing algorithm: Model selection for lazy learners
O. Maron and A. Moore · 1997
Earlier work this paper cites.
In defense of one-vs-all classification
R. Rifkin and A. Klautau · 2004
Earlier work this paper cites.
Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
E. Even-Dar, S. Mannor, and Y. Mansour · 2006
Earlier work this paper cites.
An empirical evaluation of deep architectures on problems with many factors of variation
H. Larochelle et al · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
A. Rahimi and B. Recht · 2007
Earlier work this paper cites.
Empirical Bernstein stopping
V. Mnih and J.-Y. Audibert · 2008
Earlier work this paper cites.
Pure exploration in multi-armed bandits problems
S. Bubeck, R. Munos, and G. Stoltz · 2009
Earlier work this paper cites.
Learning multiple layers of features from tiny images
A. Krizhevsky · 2009
Earlier work this paper cites.
Regret bounds for Gaussian process bandit problems
S. Grünewälder, J. Audibert, M. Opper, and J. Shawe–Taylor · 2010
Earlier work this paper cites.
Gaussian process optimization in the bandit setting: No regret and experimental design
N. Srinivas, A. Krause, M. Seeger, and S. M. Kakade · 2010
Earlier work this paper cites.
Oracle inequalities for computationally budgeted model selection
A. Agarwal, J. Duchi, P. L. Bartlett, and C. Levrard · 2011
Earlier work this paper cites.
Algorithms for hyper-parameter optimization
J. Bergstra, R. Bardenet, Y. Bengio, and B. Kegl · 2011
Earlier work this paper cites.
X-armed bandits
S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvari · 2011
Earlier work this paper cites.
Efficient multi-start strategies for local search algorithms
A. György and L. Kocsis · 2011
Earlier work this paper cites.
Sequential model-based optimization for general algorithm configuration
F. Hutter, H. Hoos, and K. Leyton-Brown · 2011
Earlier work this paper cites.
Reading digits in natural images with unsupervised feature learning
Y. Netzer et al · 2011
Earlier work this paper cites.

Similar

Information rates of nonparametric Gaussian process methods
A. van der Vaart and H. van Zanten · 2011
Cited alongside, same era.
Random search for hyper-parameter optimization
J. Bergstra and Y. Bengio · 2012
Cited alongside, same era.
Convolutional neural networks applied to house numbers digit classification
P. Sermanet, S. Chintala, and Y. LeCun · 2012
Cited alongside, same era.
Practical Bayesian optimization of machine learning algorithms
J. Snoek, H. Larochelle, and R. Adams · 2012
Cited alongside, same era.
Towards an empirical foundation for assessing Bayesian optimization of hyperparameters
K. Eggensperger et al · 2013
Cited alongside, same era.
Almost optimal exploration in multi-armed bandits
Z. Karnin, T. Koren, and O. Somekh · 2013
Cited alongside, same era.
Multi-task Bayesian optimization
K. Swersky, J. Snoek, and R. Adams · 2013
Cited alongside, same era.
Auto-weka: Combined selection and hyperparameter optimization of classification algorithms
C. Thornton et al · 2013
Cited alongside, same era.
Bayesian optimization in high dimensions via random embeddings
Z. Wang, M. Zoghi, F. Hutter, D. Matheson, and N. de Freitas · 2013
Cited alongside, same era.
Least squares revisited: Scalable approaches for multi-class prediction
A. Agarwal, S. Kakade, N. Karampatziakis, L. Song, and G. Valiant · 2014
Cited alongside, same era.
Gaussian process optimization with mutual information
E. Contal, V. Perchet, and N. Vayatis · 2014
Cited alongside, same era.
Using meta-learning to initialize Bayesian optimization of hyperparameters
M. Feurer, J. Springenberg, and F. Hutter · 2014
Cited alongside, same era.

Then

Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves
T. Domhan, J. T. Springenberg, and F. Hutter · 2015
Later among the works it cites.
Personal communication, 2015
M. Feurer · 2015
Later among the works it cites.
Efficient and robust automated machine learning
M. Feurer, A. Klein, K. Eggensperger, J. Springenberg, M. Blum, and F. Hutter · 2015
Later among the works it cites.
Non-stochastic best arm identification and hyperparameter optimization
K. Jamieson and A. Talwalkar · 2015
Later among the works it cites.
High dimensional Bayesian optimization and bandits via additive models
K. Kandasamy, J. Schneider, and B. Póczos · 2015
Later among the works it cites.
On the complexity of best arm identification in multi-armed bandit models
E. Kaufmann, O. Cappé, and A. Garivier · 2015
Later among the works it cites.
Fast cross-validation via sequential testing
T. Krueger, D. Panknin, and M. Braun · 2015
Later among the works it cites.
Automating model search for large scale machine learning,
E. Sparks, A. Talwalkar, D. Haas, M. J. Franklin, M. I. Jordan, and T. Kraska · 2015
Later among the works it cites.
Thoughts on massively scalable Gaussian processes
Original
A. G. Wilson, C. Dann, and H. Nickisch · 2015
Later among the works it cites.
The power of adaptivity in identifying statistical alternatives
K. G. Jamieson, D. Haas, and B. Recht · 2016
Closest in time.
Gaussian process bandit optimization with multi-fidelity evaluations
K. Kandasamy, G. Dasarathy, J. B. Oliva, J. G. Schneider, and B. Póczos · 2016
Closest in time.
Bayesian optimization with robust Bayesian neural networks
J. Springenberg, A. Klein, S. Falkner, and F. Hutter · 2016
Closest in time.
Optimization as estimation with Gaussian processes in bandit settings
Z. Wang, B. Zhou, and S. Jegelka · 2016
Closest in time.
Google Vizier: A service for black-box optimization
D. Golovin, B. Sonik, S. Moitra, G. Kochanski, J. Karro, and D.Sculley · 2017
Closest in time.
Multi-fidelity Bayesian optimization with continuous approximation
K. Kandasamy, G. Dasarathy, J. Schneider, and B. Póczos · 2017
Closest in time.
Hyperband: Bandit-based configuration evaluation for hyperparameter optimization
L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…