Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization

By Thomas Desautels, Andreas Krause, Joel W. Burdick. 2012

511 citations recorded by the source corpus.

Can one parallelize complex exploration-exploitation tradeoffs? As an example, consider the problem of optimal high-throughput experimental design, where we wish to sequentially design batches of experiments in order to simultaneously learn a surrogate function mapping stimulus to response and identify the maximum of the function. We formalize the task as a multiarmed bandit problem, where the unknown payoff function is sampled from a Gaussian process (GP), and instead of a single arm, in each round we pull a batch of several arms in parallel. We develop GP-BUCB, a principled algorithm for choosing batches, based on the GP-UCB algorithm for sequential GP optimization. We prove a surprising result; as compared to the sequential approach, the cumulative regret of the parallel algorithm only increases by a constant factor independent of the batch size B. Our results provide rigorous theoretical support for exploiting parallelism in Bayesian global optimization. We demonstrate the effectiveness of our approach on two real-world applications.

Subfields: Optimization & Training, Probabilistic & Bayesian Methods

How researchers see this paper

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

In Optimization & Training

In Probabilistic & Bayesian Methods

Citations in the corpus

Tempered Sigmoid Activations for Deep Learning with Differential Privacy (2020, methodology): “For example, Table 3 shows how learning rates obtained through a hyperparameter search based on Batched Gaussian Process Bandits [8] vary across the non-DP and DP settings when training on FashionMNIST, but that the choice of optimizer (and in particular whether it is adaptive or not) does not influ”
Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, methodology): “Grid and random search are involved, while batched Gaussian process bandit optimization (Desautels et al., 2014) is the default mode for most scenarios.”
Benchmark and Survey of Automated Machine Learning Frameworks (2019, background): “…evaluations can be either ignored—if sampling a new candidate depends on a stochastic process (Bergstra et al., 2011; Kandasamy et al., 2018)— or imputed with a constant (Ginsbourger et al., 2010b) or simulated performance (Ginsbourger et al., 2010a; Snoek et al., 2012; Desautels et al., 2014).”
Survey on Automated Machine Learning (2019, background): “, 2014) can be parallelized with some efforts (Zinkevich et al., 2010; Desautels et al., 2014).”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “Finally, there also exist variants of these algorithms for the contextual bandits [153] (see Section VIII-D) and parallel querying [45] (see Section V-E).”
Google Vizier: A Service for Black-Box Optimization (2017, methodology): “Algorithm 1 is then used in the Batched Gaussian Process Bandits [8] algorithm.”
Capacity and Trainability in Recurrent Neural Networks (2016, methodology): “In order to train our models we employed a HP tuner that uses a Gaussian Process model similar to Spearmint (see Appendix, section on HP tuning and Desautels et al. (2014); Snoek et al. (2012) for related work).”
Modeling Task Relationships in Multi-task Learning with Multi-gate Mixture-of-Experts (2018, methodology): “The tuning algorithm is a Gaussian Process model similar to Spearmint as introduced in [14, 32].”
CMA-ES for Hyperparameter Optimization of Deep Neural Networks (2016, neutral): “…et al., 2012a) or by evaluating the optima of multiple acquisition functions concurrently (Hutter et al., 2012; Chevalier & Ginsbourger, 2013; Desautels et al., 2014), perfect parallelization appears difﬁcult to achieve since the decisions in each step depend on all data points gathered so…”
Neural Ranking Models with Weak Supervision (2017, background): “1 for more detail) using batched GP bandits with an expected improvement acquisition function [8].”
Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions (2015, methodology): “In order to extend this approach to the parallel setting, [17] noted that the predictive variance of a Gaussian process depends only on where observations are made, and not the observations themselves.”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, methodology): “Our analysis is based on Russo and Van Roy [31] and Srinivas et al. [36], and also uses some techniques from Desautels et al. [8].”
Batched Stochastic Bayesian Optimization via Combinatorial Constraints Design (2019, background): “Desautels et al. (2014) generalize this to batch queries.”
Learning to Learn without Gradient Descent by Gradient Descent (2016, methodology): “It is instructive to contrast this strategy with what is done in parallel Bayesian optimization (Desautels et al., 2014; Snoek et al., 2012).”
Recent Advances in Bayesian Optimization (2022, background): “An extension of GP-UCB is proposed to leverage the updated variance, encouraging more exploration [35].”
Sequential line search for efficient visual design optimization by crowds (2017, background): “, [Azimi et al. 2010; Desautels et al. 2014]) may be useful for reducing the entire latency.”