Bayesian Optimization (BO) is celebrated for its sample efficiency in optimizing expensive, black-box functions. In a textbook description, the loop is elegant: fit a Gaussian Process (GP) posterior over the objective function, compute an acquisition function (such as Upper Confidence Bound or Expected Improvement), and globally maximize this acquisition function to select the next evaluation point.
However, this idealized pipeline relies on two computationally intractable assumptions: an exact posterior distribution and a global optimization oracle for the acquisition function. As noted by Aditya Gopalan et al. in No-regret Algorithms for Multi-task Bayesian Optimization, maximizing the acquisition function is generally an NP-hard problem. In practice, practitioners substitute these exact oracles with approximations—using sparse GPs, local gradient-based search, or random grids.
This discrepancy raises a fundamental question: Why does Bayesian Optimization continue to work so well in practice despite these constant errors? A major research direction has emerged to prove the robustness of BO under inexact operations, bridging the gap between theoretical oracle assumptions and practical heuristics.
The Optimization Gap: Inexact Acquisition Maximization
Standard convergence proofs assume that the acquisition function is perfectly maximized at every iteration. If an algorithm selects a suboptimal point in the inner loop, the mathematical guarantees of the outer loop typically collapse. Ziyu Wang 0001 et al. highlighted this issue in Bayesian Multi-Scale Optimistic Optimization, demonstrating a severe disconnect between theoretical convergence rates and actual performance when heuristic solvers are introduced.
To quantify this loss, Jungtaek Kim et al. analyzed the instantaneous regret incurred by substituting global maximizers with local or multi-started local search in On Local Optimizers of Acquisition Functions in Bayesian Optimization. They proved that multi-starting can exponentially close the performance gap, but the broader question remained: can we guarantee global convergence under persistent optimization errors?
The core intuition for why BO survives inexact maximization lies in the concept of sublinear cumulative inaccuracy. In Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?, Hwanwoo Kim et al. proved that algorithms like GP-Upper Confidence Bound (GP-UCB) and Thompson Sampling maintain optimal convergence rates even if the inner optimization step is solved approximately.
The mechanism works because global convergence does not require perfection; it requires that the total accumulated error from the inexact solutions grows slower than the total number of iterations ($T$). As long as the inner solver captures a stable fraction of the true maximum at each step, the outer loop successfully navigates the exploration-exploitation trade-off. Remarkably, the authors demonstrate that a simple random grid search—with a grid size that scales only linearly over time—is theoretically sufficient to guarantee sublinear cumulative regret.
The Statistical Gap: Bounded Posterior Inference Error
The second oracle assumption is that we can compute or sample from the exact posterior distribution. For large datasets or high-dimensional spaces, exact GPs scale poorly, forcing the use of sparse variational approximations or Markov Chain Monte Carlo (MCMC) sampling. One might fear that a flawed posterior would mislead the acquisition function, causing cascading errors. However, theoretical frameworks show that BO is highly resilient to bounded inference errors.
The intuition here is that the error does not need to vanish over time; it merely needs to be bounded within a specific divergence threshold. Ziyi Huang et al. proved this in Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework, showing that Bayesian bandit algorithms can achieve optimal logarithmic regret even with a constant level of posterior approximation error, provided the error is controlled under certain $\alpha$-divergences. Because BO is inherently exploratory, small, bounded errors in the posterior mean or variance act like minor noise that the algorithm's exploration bonus can naturally absorb.
This principle applies across different approximation methods:
- Approximate Sampling: When using Thompson Sampling, drawing exact samples from the posterior is often impossible. Tom Huix et al. showed in Tight Regret and Complexity Bounds for Thompson Sampling via Langevin Monte Carlo that as long as the approximation error of an MCMC sampling chain is controlled through sufficient iterations, the global optimization performance remains theoretically optimal.
- Sparse Approximations: In Scalable Thompson Sampling using Sparse Gaussian Process Models, Sattar Vakili et al. established that sparse GP approximations achieve the same theoretical regret orders as exact methods, provided the number of inducing points grows at an appropriate rate relative to the observations. This matches the foundational statistical guarantees proven by Luke Travis et al. in Pointwise uncertainty quantification for sparse variational Gaussian process regression with a Brownian motion prior, confirming that sparse variational models can recover the true underlying function at optimal rates without degrading downstream optimization logic.
Asymmetries in Robustness: Why Strategy Matters
While algorithms like UCB and Thompson Sampling exhibit strong mathematical resilience to inexactness, this robustness does not universally extend to all acquisition strategies. Expected Improvement (EI) is a prominent example where robustness guarantees frequently break down.
As Dmitry Yarotsky demonstrated in Examples of inconsistency in optimization by expected improvement, when paired with highly smooth kernels (like the Gaussian kernel), EI can suffer from fundamental inconsistency. If the objective function matches certain patterns, the surrogate model may predict near-zero variance in unsampled regions. This causes the acquisition function to drop exponentially to zero, meaning the algorithm prematurely ceases exploration and fails to converge entirely—even with infinite iterations. Though Dmitry Yarotsky proved in a companion paper, Univariate interpolation by exponential functions and Gaussian RBFs for generic sets of nodes, that EI converges exponentially for functions analytic in a large enough domain, its sensitivity to the underlying mathematical structure makes it fragile under approximation.
This fragility creates a persistent gap in the literature:
- Proof Limitations: Extending robustness proofs under inexact optimization or transfer learning to EI remains an open challenge. As highlighted by Alistair Shilton et al. in Regret Bounds for Transfer Learning in Bayesian Optimisation and Vu Nguyen et al. in Regret for Expected Improvement over the Best-Observed Value and Stopping Condition, formal guarantees are largely restricted to UCB baselines because EI lacks the same structural tolerance to sub-optimal initialization and numerical errors.
- Landscape Complexity: The complex, multi-modal nature of posterior landscapes often exacerbates this issue. Taiwo A. Adebiyi et al. note in Optimizing Posterior Samples for Bayesian Optimization via Rootfinding that even robust acquisition strategies can fail if numerical optimization cannot handle highly "wiggly" posterior structures, a problem that severely impacts high-dimensional settings (Jiayu Zhao et al.).
- Human-in-the-Loop Constraints: This asymmetry also appears when humans alter the optimization loop. Masaki Adachi et al. showed in Looping in the Human: Collaborative and Explainable Bayesian Optimization that "no-harm" convergence guarantees—ensuring the algorithm converges even if a human expert provides faulty inputs—can be proven for UCB-based frameworks, but extending these protections to EI remains an unsolved problem.
Finally, this line of research highlights a curious paradox identified by Shion Takeno et al. in Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds: theoretical proofs often necessitate large, conservative confidence parameters to guarantee robustness, yet practitioners achieve better empirical results using small, heuristic values that technically lack these mathematical safety nets. Bridging this final gap remains an active frontier in understanding the boundaries of approximate Bayesian optimization.
Key Foundational Work
Examples of inconsistency in optimization by expected improvement (2013) — contributed 2 concept elements to this direction.
Bayesian Multi-Scale Optimistic Optimization (2014) — contributed 1 concept elements to this direction.
Univariate interpolation by exponential functions and Gaussian RBFs for generic sets of nodes (2013) — contributed 1 concept elements to this direction.