The Parallel Knowledge Gradient Method for Batch Bayesian Optimization

By Jian Wu, Peter I. Frazier. 2016

251 citations recorded by the source corpus.

In many applications of black-box optimization, one can evaluate multiple points simultaneously, e.g. when evaluating the performances of several different neural network architectures in a parallel computing environment. In this paper, we develop a novel batch Bayesian optimization algorithm --- the parallel knowledge gradient method. By construction, this method provides the one-step Bayes-optimal batch of points to sample. We provide an efficient strategy for computing this Bayes-optimal batch of points, and we demonstrate that the parallel knowledge gradient method finds global optima significantly faster than previous batch Bayesian optimization algorithms on both synthetic test functions and when tuning hyperparameters of practical machine learning algorithms, especially when function evaluations are noisy.

Subfields: Artificial Intelligence

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

Citations in the corpus

Population Based Training of Neural Networks (2017, methodology): “…independent models in parallel to quicker update the Bayesian model (though potentially introducing bias) (Shah & Ghahramani, 2015; Gonz ´ alez et al., 2016; Wu & Frazier, 2016; Rasley et al., 2017; Golovin et al., 2017) – but these will still require multiple sequential model optimisations.”
Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020 (2021, background): “These baselines were meant to give participants a good starting point, but there are many other possible packages such as Ax/BoTorch [3, 4], Cornell-MOE [67], Dragonﬂy [37], Emukit [52], GPFlowOpt [41], GPyOpt [61], pycma [29], RBFOpt [10], RoBO [39], ProBO [50], and Spearmint [60].”
Maximizing acquisition functions for Bayesian optimization (2018, background): “D By marginalizing out nuisance variables f ( X \ X ) , L can be expressed as an expectation over functions f k themselves rather than over potential outcomes y k ∼ p ( y X , D ) .”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, methodology): “Hence, there has been a ﬂurry of recent activity in this area [7, 8, 10, 12, 17, 24, 34, 38–40].”
Constrained Bayesian Optimization with Noisy Experiments (2017, methodology): “Methods such as quantile EI (Picheny et al. 2013) and knowledge gradient (Scott et al. 2011, Wu and Frazier 2016, Wang et al. 2016) do not handle constraints, and so were not used in our comparison.”
Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization (2020, methodology): “To maximize q EHVI, we could therefore directly apply stochastic optimization methods, as has previously been done for single-outcome acquisition functions [60, 62].”
A Tutorial on Bayesian Optimization (2018, methodology): “…including multi-task optimization (Swersky et al., 2013; Toscano-Palmerin and Frazier, 2018), multi-ﬁdelity optimization speciﬁcally aimed at training deep neural networks (Klein et al., 2016), and parallel methods (Ginsbourger et al., 2007, 2010; Wang et al., 2016a; Wu and Frazier, 2016).”
Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space (2017, background): “Wu & Frazier (2016) propose the Parallel Knowledge Gradient Method which optimizes an acquisition function called the parallel knowledge gradient (q-KG), a measure of the expected incremental solution quality after q samples.”
Recent Advances in Bayesian Optimization (2022, methodology): “For example, parallelized PES [163] and KG [198] are developed to jointly identify a batch of points to probe in the next iteration, rendering, however, a poor scalability to the batch size.”
BoTorch: Programmable Bayesian Optimization in PyTorch (2019, methodology): “Alternatively, the inner problem can be discretized and the gradient computation of Wu & Frazier (2016) can be used.”
Scalable Global Optimization via Local Bayesian Optimization (2019, background): “While several batch acquisition functions have recently been proposed [9, 40, 50, 54, 55, 28, 18], these approaches do not scale to large batch sizes in practice.”
Parallelised Bayesian Optimisation via Thompson Sampling (2018, methodology): “Some methods become computationally prohibitive when there are a large number of workers and must resort to approximations [19, 38, 43, 46].”