Work While They Sleep: Exploiting Evaluation Latency for Fully Bayesian Optimization

1 INTRODUCTION

• Expensive objective evaluations dominate optimization time and constrain how many evaluations are available, making sample-efficient BO important.A misspecified model can waste that limited evaluation budget by suggesting suboptimal queries.Source: §1 · p. 1
• BO acts as a planner that suggests the next query point for black-box functions encountered in science and engineering.The cited applications span science and engineering.Source: §1 · p. 1
• Standard BO fits Gaussian-process hyperparameters with a point estimate, using maximum likelihood or maximum a posteriori estimation.Examples of hyperparameters include lengthscale, output scale, deep-kernel parameters, and noise variance.Source: §1 · p. 1

ELF-BO (Ours)

• Figure 1 contrasts standard fully Bayesian BO’s alternating worker and planner waits with ELF-BO’s overlapping MCMC and objective evaluation.After the objective value arrives, ELF-BO retains importance reweighting and acquisition optimization as decision-time work.Source: Figure 1 · p. 2
• Point estimates can underestimate hyperparameter and objective uncertainty, a concern in low-data regimes; Bayesian neural networks also carry high decision-time computational overhead.The paper focuses on Gaussian processes despite the method’s stated applicability to Bayesian neural networks.Source: ELF-BO (Ours) · p. 2
• ELF-BO samples hyperparameters from the current posterior while the objective is evaluated, then reweights them using the observed value before combining acquisition functions.The reweighting weights are proportional to the predictive density of the pending evaluation result.Source: ELF-BO (Ours) · p. 2
• ELF-BO matches MCMC-based fully Bayesian BO on 15 benchmarks and three experimental datasets, with decision latency roughly 10× lower for a Matérn kernel and 70–110× lower for a deep kernel.Decision latency falls by more than two orders of magnitude as the dataset grows.Source: ELF-BO (Ours) · p. 2

2 PRELIMINARIES

• BO uses a surrogate to represent belief about the objective and an acquisition function to score the next query, repeating until the evaluation budget is exhausted.The objective is accessed through noisy observations.Source: §2 · pp. 2–3

2.1 GAUSSIAN PROCESSES

• A GP is specified by its mean and covariance functions and hyperparameters; conditioning on data gives a GP posterior that remains conditional on those hyperparameters.The hyperparameters include the mean and covariance function parameters and observation-noise variance.Source: §2.1 · p. 3

2.2 MODEL AVERAGING

• Model averaging integrates the GP posterior over hyperparameters, but the resulting hyperparameter posterior is non-Gaussian and lacks a closed-form normalizer.Monte Carlo methods approximate the integral with posterior samples; acquisition mixtures apply when the acquisition is linear in the predictive distribution, as for expected improvement.Source: §2.2 · p. 3
• Figure 2 shows ELF-BO sampling hyperparameters from the previous posterior while the candidate evaluation is pending, then reweighting samples by predictive density and combining their acquisitions.This yields the marginal acquisition used to choose the next candidate.Source: Figure 2 · p. 4

3 EVALUATION LATENCY FULLY BAYESIAN OPTIMIZATION

• The reweighted expectation uses the previous posterior as a proposal, with weights proportional to the new observation’s predictive likelihood under each hyperparameter sample.The identity assumes the updated posterior is absolutely continuous with respect to the previous posterior.Source: §3 · p. 4
• ELF-BO samples hyperparameters from the previous-step posterior while the objective runs, then reweights them after observing the result to compute the next suggestion.This moves MCMC sampling into objective-evaluation time, leaving only reweighting and averaging after the observation arrives.Source: §3 · pp. 4–5
• The approximation is reliable only when the previous posterior covers the updated posterior; low effective sample size signals that a few weights dominate and the estimate can collapse.Effective sample size is available immediately after the observation is received.Source: §3 · p. 5

3.1 DECISION LATENCY REDUCTION

• When objective-evaluation latency is at least the MCMC sampling time, sampling can finish during evaluation and the reweighting overhead is negligible in practice.Decision latency is the wall-clock time between an observation arriving and the next query being proposed.Source: §3.1 · p. 5
• On 15 synthetic functions, ELF-BO follows Standard FBO on most functions, and fully Bayesian approaches often converge earlier than MAP.The benchmark figure summarizes optimization performance across the functions.Source: Figure 3 · p. 6

4 RELATED WORK

• Earlier fully Bayesian BO work used MCMC hyperparameter averaging, with reported benefits over point-estimate methods and applications to high-dimensional BO and deep kernels.The cited literature also extends fully Bayesian BO to Bayesian neural networks, which the authors say could benefit from ELF-BO.Source: §4 · p. 6
• Asynchronous and delayed-feedback BO addresses pending evaluations through approaches such as local penalization, Thompson sampling, or pessimistic substitutions; ELF-BO instead targets single-evaluation settings.The paper describes this single-evaluation setting as common in real-world applications.Source: §4 · p. 6
• Across three Olympus experimental datasets, ELF-BO converges as quickly and reliably as Standard FBO, with area under GAP close to Standard FBO’s at latency similar to MAP’s and more than 10× below Standard FBO.Figure 4 plots best GAP by iteration above and mean decision latency against area under the GAP curve below.Source: Figure 4 · p. 7

5.1 STANDARD BENCHMARK FUNCTIONS

• The experiments use 15 noiseless synthetic benchmarks from 2 to 10 dimensions, with 100 optimization steps and 64 hyperparameter samples per step for MCMC methods.Source: §5.1 · p. 8
• On most of 15 standard benchmark functions, ELF-BO tracks Standard FBO closely, but the methods diverge on Michalewicz (d = 5).ELF-BO follows Standard FBO both when it outperforms MAP and when they are equivalent.Source: §5.1 · p. 8

5.2 REAL-WORLD APPLICATIONS

• The real-world evaluation uses three physical-experiment datasets as virtual libraries, with sequential optimization for 50 steps and 128 hyperparameter samples per step for Standard FBO and ELF-BO.Each task starts from 2d Sobol points.Source: §5.2 · p. 8
• Figure 6 shows Standard FBO decision latency increasing with observation-set size on Photo-WF3 while ELF-BO remains constant.Source: Figure 6 · p. 9
• On Olympus tasks, ELF-BO achieves Pareto dominance over Standard FBO and MAP, with performance on par with Standard FBO and suggestions more than 10× faster.Source: §5.2 · p. 9
• For deep-kernel Olympus tasks, ELF-BO stays under 1 s and reduces decision latency by 70–110× relative to Standard FBO while remaining competitive in sample efficiency.Figure 5 reports Pareto optimality over Standard FBO and MAP, with a more pronounced decision-latency reduction than with the Matérn kernel.Source: Figure 5 · p. 8, §5.2 · p. 9

Scaling with the number of observations

• On Photo-WF3 with a deep kernel, Standard FBO decision latency grows up to 24 minutes as observations increase, while ELF-BO remains nearly constant under 3 seconds.ELF-BO’s advantage applies as long as sampling fits within objective evaluation time; the figure indicates the evaluation time needed to fully hide sampling.Source: §6 · p. 9

Impact of effective sample size

• Michalewicz (d = 5) has lower effective sample size than Hartmann (d = 6) for most steps, and the lower values help explain its poorer tracking of Standard FBO.Effective sample size is available when the observation arrives and can flag steps where reweighted estimates may be less reliable.Source: §6 · p. 9

7 CONCLUSION

• ELF-BO draws hyperparameter samples using data available at dispatch and reweights them after the observation, removing MCMC from the time between function evaluations.Source: §7 · pp. 9–10
• Across 15 synthetic functions and three real-world datasets, ELF-BO matches MCMC-based fully Bayesian optimization on most tasks while keeping decision latency close to point-estimate BO times.Source: §7 · p. 10
• ELF-BO’s latency gains are observed when objective evaluations take longer than MCMC, and are absent for near-instant evaluations.The paper considers GP surrogates in the sequential setting.Source: §7 · p. 10

A PROOFS

• The identity assumes that each step’s hyperparameter posterior is absolutely continuous with respect to the previous step’s posterior.Source: A PROOFS · p. 13
• The proposition rewrites an expectation under the updated hyperparameter posterior as a weighted expectation under the previous posterior.Source: A PROOFS · p. 13
• The proof uses Bayes’ rule to express the updated posterior through the observed outcome and derive the importance weight.Source: A PROOFS · p. 13

B.1 REAL-WORLD APPLICATIONS

• HPLC sessions comprise 100 robotic experiments over roughly seven hours (~four minutes each), while photovoltaic batches take 18 hours and are evaluated sequentially.Figure 8 presents optimization curves for deep-kernel methods on Olympus datasets.Source: §B.1 · p. 13, Figure 8 · p. 14

B.2 DEEP KERNEL DETAILS

• The deep kernel applies a fixed-lengthscale Matérn covariance to an 8-dimensional neural embedding and has 16d+155 hyperparameters.Its embedding network has one 16-unit tanh hidden layer; the paper specifies zero-mean normal priors for its weights and biases.Source: §B.2 · p. 14

B.4 FURTHER EXPERIMENTAL DETAILS

• MAP deep kernels use four Adam restarts, while fully Bayesian runs use NUTS; scaling tests use 128 samples and Log-EI batches of 32.The NUTS run before the first BO step is excluded from latency results; acquisition optimization uses 10 restarts and 512 raw samples for continuous functions, and scores unused discrete rows in batches of 512.Source: §B.2 · p. 14, §B.4 · p. 14

B.3 COMPUTATIONAL RESOURCES

• Experiments use BoTorch 0.18.1 in Python, with synthetic benchmarks on an NVIDIA L40S and real-world experiments on an NVIDIA H100.Source: §B.3 · p. 14

• Figure 8 presents the complete GAP curves for the deep-kernel experiments described in Section 5.2.Source: C ADDITIONAL RESULTS · p. 14