Asynchronous Parallel Bayesian Optimisation via Thompson Sampling

By Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, Barnab'as P'oczos. 2017

32 citations recorded by the source corpus.

We design and analyse variations of the classical Thompson sampling (TS) procedure for Bayesian optimisation (BO) in settings where function evaluations are expensive, but can be performed in parallel. Our theoretical analysis shows that a direct application of the sequential Thompson sampling algorithm in either synchronous or asynchronous parallel settings yields a surprisingly powerful result: making $n$ evaluations distributed among $M$ workers is essentially equivalent to performing $n$ evaluations in sequence. Further, by modeling the time taken to complete a function evaluation, we show that, under a time constraint, asynchronously parallel TS achieves asymptotically lower regret than both the synchronous and sequential versions. These results are complemented by an experimental analysis, showing that asynchronous TS outperforms a suite of existing parallel BO algorithms in simulations and in a hyper-parameter tuning application in convolutional neural networks. In addition to these, the proposed procedure is conceptually and computationally much simpler than existing work for parallel BO.

Subfields: Artificial Intelligence, Management Science and Operations Research

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

Citations in the corpus

Survey on Automated Machine Learning (2019, background): “Alternatively, an uncompleted evaluation of a configuration can be modeled as the worst possible result (Kandasamy et al., 2017).”
A Tutorial on Thompson Sampling (2017, background): “Adaptations of Thompson sampling have now been successfully applied in a wide variety of domains, including revenue management [7], marketing [8], Monte Carlo tree search [9], A/B testing [10], Internet advertising [10, 11, 12], recommendation systems [13], hyperparameter tuning [14], and arcade gam”
Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning (2019, methodology): “Beyond those we used in our experiments, we can further mention recent resource-aware optimizers [2, 8], evolutionary-based techniques [18, 34] and virtually any core improvement of BO, be it related to the acquisition function [48] or efﬁcient parallelism [23, 47].”