Computational Overhead in Bayesian Optimization Acquisition Functions

30 concepts28 papers1 proposal

Bayesian Optimization (BO) is built on a simple promise: by spending more time "thinking" about where to sample next, we can drastically reduce the number of expensive evaluations needed to find an optimum. However, this "thinking time"—the computational overhead of the acquisition function—is not free. As acquisition functions have become more sophisticated, their internal complexity has created a new bottleneck where the time spent deciding on a sample can exceed the time saved by the sample's efficiency.

The Meta-Optimization Problem

At each step of BO, we solve a secondary optimization problem: maximizing an acquisition function $\alpha(x)$ to find the next query point. While early heuristics like Expected Improvement are cheap to compute, modern information-theoretic and lookahead methods require solving complex nested problems.

As Buathong et al. and Takeno et al. note, sophisticated strategies like the Knowledge Gradient or Max-value Entropy Search often require internal Monte Carlo sampling or numerical integration to estimate the global maximum. This creates a significant wall-clock penalty. If the objective function evaluation is relatively fast—such as a low-fidelity simulation or a small-scale machine learning model—the time the optimizer spends "reasoning" can become the dominant cost of the entire loop [Klein et al., Shahrooei et al.].

Sources of Latency

The overhead in modern BO typically stems from three mathematical challenges:

  1. Intractable Integrals: Information-theoretic methods like Entropy Search aim to reduce the uncertainty about the location or value of the optimum. Because these lack closed-form solutions, they often rely on discretization and Monte Carlo approximations that are computationally expensive [Metzen, Wang].
  2. Lookahead Complexity: Non-myopic methods improve efficiency by considering how a current sample will affect future decisions. However, Daulton et al. and Wu explain that integrating over all potential future observations and optimizing the resulting utility can turn a second-long decision into one that takes minutes or even hours.
  3. Joint Batch Optimization: When selecting multiple points to evaluate in parallel, the search space for the acquisition function grows exponentially. Wu and Frazier and Shah and Ghahramani highlight that calculating gradients for these joint distributions requires advanced techniques like Expectation Propagation, further increasing the computational burden.

The Efficiency Threshold

The utility of a complex acquisition function is governed by a simple trade-off: the time spent selecting a point must be a small fraction of the time required for a single system simulation [Ginsbourger et al.]. Picheny argues that if the target simulation is not "exceptionally expensive," the gains in sampling efficiency are outweighed by the search latency.

This is particularly critical in high-speed robotics or real-time systems. For example, Marco et al. found that the seconds required for Entropy Search to propose a new controller weight can become a bottleneck when the time between physical experiments needs to be minimized. Similarly, Acerbi points out that the overhead of fitting Gaussian Processes and optimizing acquisition functions can negate the benefits of active sampling if the underlying model is not sufficiently slow.

Mitigating the Bottleneck

To reclaim the speed of BO without sacrificing its intelligence, researchers have proposed several paths:

  • Principled Approximations: Instead of calculating exact information gain, methods like GIBBON [Moss et al.] and MUMBO [Moss et al.] derive lower bounds that are orders of magnitude faster to compute.
  • Alternative Surrogates: The authors of HORD [Ilievski et al.] suggest using deterministic Radial Basis Function surrogates instead of Gaussian Processes to reduce the internal mathematical complexity of proposing candidates.
  • Learned Acquisition Functions: A recent shift involves using machine learning to speed up the optimizer itself. Rakotoarison et al. introduced $\alpha$-PFN, which uses a transformer-based approach to perform Entropy Search via in-context learning, achieving 50x speedups by avoiding the need for Monte Carlo approximations entirely.

Ultimately, the goal of this research direction is to ensure that the "brain" of the optimizer remains an asset rather than a liability, allowing BO to be applied to a wider range of problems where every second of wall-clock time counts.

Key Foundational Work

Sequential design of computer experiments for the estimation of a probability of failure (2012) — contributed 1 concept elements to this direction.
Efficient Optimization for Autonomous Robotic Manipulation of Natural Objects (2014) — contributed 1 concept elements to this direction.
A Stepwise uncertainty reduction approach to constrained global optimization (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_acquisition_function_overhead_6d1bb83e,
  title = {acquisition function overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/acquisition-function-overhead/rdr_6d1bb83ec3e94184ad26fd1db6b6e6a8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_acquisition_function_overhead_6d1bb83e_v1,
  title = {acquisition function overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/acquisition-function-overhead/rdr_6d1bb83ec3e94184ad26fd1db6b6e6a8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake