Space Partitioning with multiple models for Parallel Bayesian Optimization

International audienceBayesian Optimization (BO) is a global optimization framework that uses bayesian surrogate models such as Gaussian Processes (GP) to address black-box problems [1], [2] with costly-to-evaluate objective functions. Bayesian models and especially GPs are attractive for their ability to provide the uncertainty over their predictions. Using this information, one can build an indicator of utility for a point to be simulated. This indicator, named Infill Criterion (IC) or Acquisition Function(AF), is used to guide the optimization process and find valuable new point(s) to be exactly evaluated. Based on this procedure, Joneset al.[3] introduce the Efficient Global Optimization (EGO) algorithm that uses the Expected Improvement (EI) AF. Many approaches emerged from the idea of making EGO parallel. In particular, Ginsbourger et al.[4] introduced the q-dimensional EI criterion (q-EI), able to provide qcandidate points when optimized. In [5], Ginsbourger et al.write that even though q-EI and its optimization methods are mathematically founded, it is not ”mathematically tractable beyond a few dimensions”. This motivates the introduction of the Kriging Believer (KB) and Constant Liar (CL) heuristics also presented in [5]. The two heuristics allow to approximate the optimization of q-EI at a much lower time cost. EGO using q-EI is called q-EGO in the following. Many other approaches based on EI orq-EI are constructed. For example, in [6] the authors use Infinitesimal Perturbation Analysis (IPA) to construct a gradient estimator of the q-EI surface, and a multi-start heuristic to find the set of points to evaluate. Zhanet al.[7] use a niching strategy to locate several optimal areas of the single point EI. Marminet al.[8] write the analytical form of the multi-point EI gradient to be able to optimize the function with gradient information and reduce the computational cost compared to sequential heuristics or MonteCarlo sampling of [5]. However, none of the methods are efficient on parallel architectures including dozens of processing units. The creation of the batch of candidates is often time consuming, and the GP model fitting cost increases fast. The reference q-EGO algorithm has been experimented and driven to its limits in Briffoteauxet al.[9]. The analysis revealed that q-EGO performs well with small budgets (i.e. number of calls to the objective function) and small batches (q≤8). However, it suffers from early stagnation, poor scalability, and budget seems misspent since increasing q doesnot necessarily improve the final target for a given number of algorithm iterations (called cycles). The limits of q-EGO comes from at least two aspects: (1) we need to updateqtimes the model toprovideqcandidate and the Kriging model becomes extremely time consuming to fit as the size ofthe learning set is increased; (2) the way the candidates are selected is not suited for large batches