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.
Generative models are increasingly central to many de novo discovery pipelines, in which designs are generated at scale and filtered through virtual screens to determine a set of candidates to experimentally validate. While Bayesian optimization (BO) is a natural fit for this setting, as it uses past evaluations to guide future proposals, the computational overhead required for its sequential decision-making becomes a bottleneck when virtual screens are relatively cheap. We make BO practical in this regime by exploiting the unique combination of a linear model constrained to a spherical domain where high-dimensional latents concentrate. We build off recent work justifying the use of linear surrogates, while deriving nearly closed-form solutions to the surrogate modelling and acquisition problems that exploit spherical symmetry. The result is at least a 100x speedup over state-of-the art baselines, with matching or improved performance across molecular and image generation benchmarks. Altogether, our method makes BO a practical drop-in for de novo pipelines where it was previously too slow to consider.
Donney Fan, Colin Doumont, Aleksandra Kalisz +4
University of British Columbia · Vector Institute · Tübingen AI Center +3
Bayesian Optimization (BO) is widely adopted for data-efficient optimization in scientific and engineering applications, yet its computational cost is rarely evaluated alongside optimization performance. Here we present a systematic, compute-aware study of BO that evaluates surrogate models along two axes: optimization quality and computational frugality. Across eight benchmark functions and nine real-world datasets spanning materials science, mechanics, robotics, chemistry, and machine learning, we benchmark four surrogate models: Gaussian Processes, Random Forests, NGBoost, and Bayesian Adaptive Spline Surfaces. We show that Gaussian Process-based BO consistently incurs the highest time and memory overhead without delivering superior optimization or sample efficiency. In contrast, scalable alternatives achieve equal or better performance at a fraction of the computational cost. Motivated by these findings, we introduce a surrogate-recommendation framework that predicts the most suitable BO surrogate from inexpensive dataset characteristics. Together, these results establish FruBO as a reproducible, compute-aware baseline for Bayesian Optimization and provide practical guidance for surrogate selection under limited computational and experimental budgets.
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
Bayesian optimization (BO) is a popular technique for sample-efficient optimization of black-box functions. In many applications, the parameters being tuned come with a carefully engineered default configuration, and practitioners only want to deviate from this default when necessary. Standard BO, however, does not aim to minimize deviation from the default and, in practice, often pushes weakly relevant parameters to the boundary of the search space. This makes it difficult to distinguish between important and spurious changes and increases the burden of vetting recommendations when the optimization objective omits relevant operational considerations. We introduce BONSAI, a default-aware BO policy that prunes low-impact deviations from a default configuration while explicitly controlling the loss in acquisition value. BONSAI is compatible with a variety of acquisition functions, including expected improvement and upper confidence bound (GP-UCB). We theoretically bound the regret incurred by BONSAI, showing that, under appropriate conditions, it retains the no-regret property of vanilla GP-UCB and removes irrelevant changes. Across many real-world applications, we empirically find that BONSAI substantially reduces the number of non-default parameters in recommended configurations while maintaining competitive optimization performance with little effect on wall time. Its candidate-generation cost averages only 1.5× that of standard BO, compared with 7-34× for prior sparse-BO methods.
Samuel Daulton, David Eriksson, Maximilian Balandat +1