Work While They Sleep: Exploiting Evaluation Latency for Fully Bayesian Optimization
Authors: Gustavo Sutter, Alejandro Comas-Leon, David Holzmüller, Hao Wang, Luis Ricardez-Sandoval, Pascal Poupart, Agustinus Kristiadi
Organizations: Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada · Vector Institute, Toronto, ON, Canada · SODA Team, INRIA Saclay, Palaiseau, France · Department of Chemical Engineering, University of Waterloo, Waterloo, ON, Canada · Waterloo Institute for Nanotechnology, University of Waterloo, Waterloo, ON, Canada · Department of Computer Science, Western University, London, ON, Canada
Black-box optimization problems are ubiquitous across science and engineering, often dealing with expensive objective functions. This objective latency has two consequences during optimization: (i) the objective evaluation dominates execution time, and (ii) sample-efficient algorithms are crucial to accelerate development and avoid wasting resources. Bayesian optimization (BO) methods are the \textit{de facto} choice of planners for suggesting the next point to try. Standard BO fits the surrogate model's hyperparameters with a point estimate. Alternatively, a fully Bayesian approach uses model averaging to account for uncertainty over the hyperparameters, leading to better uncertainty estimates---useful in the low-data regime that is pervasive in BO. However, it is often prohibitively expensive and thus rarely used. In this work, we propose ELF-BO, an algorithm that uses the objective evaluation latency to headstart the computation of the next suggestion, allowing for fully Bayesian optimization without incurring substantial decision-time costs. This is done by sampling from the hyperparameter posterior \emph{while} the objective is being evaluated, only requiring reweighting of the samples once the objective value is observed. Across synthetic functions and real-world applications, we show that ELF-BO matches the performance of fully Bayesian methods while only incurring decision latency on par with or better than standard BO. Thus, ELF-BO makes fully Bayesian optimization practical in real-world use cases.
Figures & tables
Figure 1: Where the time goes in a sequential BO campaign. Each timeline shows the worker (the experiment or simulator evaluating f ) and the planner (the BO algorithm); thick segments denote busy time. Left: In standard fully Bayesian BO, the two alternate: the planner waits while f is evaluated, and the worker waits while the planner runs MCMC and optimizes the acquisition function. Right: ELF-BO runs MCMC while f is being evaluated, so once yt arrives, only a cheap importance reweighting and the acquisition optimization remain, greatly reducing decision latency.
Figure 2: Overview of ELF-BO . Fully Bayesian BO marginalizes the acquisition function over the GP hyperparameters θ , which requires MCMC after every new observation. We instead run it while the objective is still being evaluated. Left: (I) with the candidate xt dispatched and its value yt still pending, we sample {θ(m)} from the posterior given the data collected so far, p(θ∣Dt−1) , which is already available. Each sample gives a different GP fit, and hence a different posterior at xt . Right: (II) when yt arrives, each sample is reweighted by how well it predicted it, w(m)∝p(yt∣Dt−1,xt,θ(m)) , and (III) the per-sample acquisition functions α(x;Dt,θ(m)) are combined into the marginal acquisition α(x;Dt) used to pick the next candidate.
Figure 3: Standard benchmarks. Optimization performance of 15 synthetic functions. ELF-BO consistently follows Standard FBO on most functions, in many of which the fully Bayesian approaches achieve earlier convergence than MAP .
Figure 4: Real-world tasks. Results on three experimental datasets from the Olympus suite. Top: best GAP found versus iteration, with standard error shaded. ELF-BO converges as quickly and reliably as Standard FBO , while MAP lags and varies more across seeds. Bottom: mean decision latency versus area under GAP curve, with error bars showing the standard error over all steps. By sampling while the objective is evaluated, ELF-BO has area under GAP close to Standard FBO ’s at a latency similar to MAP ’s, more than 10 × lower than Standard FBO .
Figure 5: Deep kernel on real-world tasks. Results of the deep kernel on Olympus datasets. As in experiments with Matérn kernel, ELF-BO achieves Pareto optimality over Standard FBO and MAP , with an even more pronounced reduction in decision latency. See Appendix C for GAP curves.
Figure 6
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 8: Deep kernel on real-world tasks. Optimization curves of the deep kernel methods on Olympus datasets.
Institute of Informatics and Telecommunications, National Centre for Scientific Research "Demokritos", Agia Paraskevi, Greece. · Department of Mechanical Engineering and Aeronautics, University of Patras, Patras Greece. · Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece. +4