Kriging is well-suited to parallelize optimization

By David Ginsbourger, Rodolphe Le Riche, Laurent Carraro. 2010

474 citations recorded by the source corpus.

The optimization of expensive-to-evaluate functions generally relies on metamodel-based exploration strategies. Many deterministic global optimization algorithms used in the field of computer experiments are based on Kriging (Gaussian process regression). Starting with a spatial predictor including a measure of uncertainty, they proceed by iteratively choosing the point maximizing a criterion which is a compromise between predicted performance and uncertainty. Distributing the evaluation of such numerically expensive objective functions on many processors is an appealing idea. Here we investigate a multi-points optimization criterion, the multipoints expected improvement (\(q-{\mathbb E}I\)), aimed at choosing several points at the same time. An analytical expression of the \(q-{\mathbb E}I\) is given when q = 2, and a consistent statistical estimate is given for the general case. We then propose two classes of heuristic strategies meant to approximately optimize the \(q-{\mathbb E}I\), and apply them to the classical Branin-Hoo test-case function. It is finally demonstrated within the covered example that the latter strategies perform as good as the best Latin Hypercubes and Uniform Designs ever found by simulation (2000 designs drawn at random for every q ∈ [1,10]).

Subfields: Computational Theory and Mathematics, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

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

In Computational Theory and Mathematics

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, methodology): “As GP+EI is the most popular combination for Bayesian optimization, improvements based on EI (Ginsbourger et al., 2010; Snoek et al., 2012) and GP-UCB (Hutter et al., 2012; Desautels et al., 2014) Parallelization on other acquisition functions (e.g. information-based function) and the combination…”
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).”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “[57] proposed several approaches based on imputing the results of currently running experiments.”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, methodology): “We compare it with four alternatives: (1) The strictly sequential GP-UCB algorithm (B = 1); (2) NRB-UCB, an approach that simply picks the maximizer of the GP-UCB score B times; (3) NTB-UCB, an approach that picks the top B scores according to the GP-UCB criterion; (4) A state of the art algorithm f”
A System for Massively Parallel Hyperparameter Tuning (2018, background): “Moreover, we note that Fabolas, along with most other Bayesian optimization approaches, can be parallelized using a constant liar (CL) type heuristic (Ginsbourger et al., 2010; González et al., 2016).”
D-VAE: A Variational Autoencoder for Directed Acyclic Graphs (2019, methodology): “[3], in each iteration, a batch of 50 points are proposed by sequentially maximizing the expected improvement (EI) acquisition function, using Kriging Believer [64] to assume labels for previously chosen points in the batch.”
A new acquisition function for Bayesian optimization based on the moment-generating function (2017, unknown): “See [11] for the detail.”
Hyperparameter optimization: Foundations, algorithms, best practices, and open challenges (2021, unknown): “Further ways to obtain n batch proposals are constant liar, Kriging believer (both described in Ginsbourger et al., 2010), and q-EI (Chevalier & Ginsbourger, 2013).”
Recent Advances in Bayesian Optimization (2022, background): “calculation of q-EI have been investigated in [54, 185].”
Sequential design of computer experiments for the estimation of a probability of failure (2010, background): “In some applications, the class of sequential algorithms must be further restricted: for instance, when K computer simulations can be run in parallel, algorithms that query batches of K evaluations at a time may be preferred (see, e.g. Ginsbourger et al., 2010).”
Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space (2017, background): “Ginsbourger et al. (Ginsbourger et al., 2010) proposed the following framework for parallel BO: given a set of current observations D I and pending experiments { x k } K k =1 , an additional set of fantasies D K = { ( x k , y k ) } K k =1 can be assumed to be the result of those pending experiments.”
Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search (2020, methodology): “…(Wang et al., 2020), evolutionary search (Real et al., 2019) and most of the batch Bayesian optimization approaches, such as Krigging believer (Ginsbourger et al., 2010), GP-BUCB (Desautels et al., 2014), B3O (Nguyen et al., 2016), GP-Thompson Sampling (Hernández-Lobato et al., 2017), and…”
A Tutorial on Bayesian Optimization (2018, methodology): “One innovation is the Constant Liar approximation to the parallel EI acquisition function (Ginsbourger et al., 2010), which chooses x sequentially by assuming that f(x) for j < i have been already observed, and have values equal to a constant (usually the expected value of f(x)) under the posterior.”
Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization (2020, background): “Most prior works in the MO setting use a sequential greedy approximation or heuristics [57, 66, 27, 9], but impute the unobserved outcomes with the posterior mean rather than integrating over the posterior [29].”