Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?

Hwanwoo Kim, Chong Liu, Yuxin Chen

Abstract

Bayesian Optimization (BO) is a powerful framework for global optimization of expensive black-box functions. However, its theoretical guarantees often rely on the assumption that the acquisition function can be maximized exactly at each iteration—a task that is computationally intractable in practice. This paper bridges the gap between theory and practice by analyzing BO under inexact acquisition optimization. We provide new regret bounds for GP-UCB and GP-TS that account for approximation errors. Crucially, we prove that a simple random grid search with a size growing only linearly with the number of iterations is sufficient to achieve sublinear regret. Empirical results across synthetic and real-world benchmarks confirm that this simple approach is not only theoretically sound but also highly efficient, often outperforming more complex gradient-based solvers.

Introduction

The standard Bayesian Optimization loop involves two main components: a surrogate model (typically a Gaussian Process) and an acquisition function (e.g., UCB or Thompson Sampling). While the surrogate update is well-understood, the "inner optimization"—finding the global maximum of the acquisition function—presents a significant challenge. Acquisition functions are frequently non-convex and multi-modal, yet theoretical convergence proofs almost exclusively assume perfect maximization.

In practice, researchers use heuristics like random search, quasi-Newton methods (L-BFGS-B), or Nelder-Mead. This paper addresses the fundamental question: how much does this approximation error matter, and can we provide rigorous guarantees for the simple solvers used in the field?

Theoretical Framework: Quantifying Inexactness

To analyze the impact of imperfect optimization, the authors introduce the concept of Accumulated Inaccuracy ($M_T$). This metric captures the sum of the gaps between the true maximum of the acquisition function and the value obtained by the inexact solver over $T$ iterations.

By incorporating $M_T$ into the regret analysis, the paper derives new bounds for two major algorithms:

  1. GP-UCB: The cumulative regret is bounded by $\mathcal{O}(\gamma_T \sqrt{T} + M_T \sqrt{\gamma_T})$, where $\gamma_T$ represents the maximum information gain.
  2. GP-TS: Similar bounds are established, showing that sublinear regret is maintained as long as the errors do not accumulate too rapidly.

A key theoretical contribution is the analysis of Random Grid Search. Previous literature suggested that for Thompson Sampling to converge, the grid size needed to grow exponentially with the dimension ($t^{2d}$). This paper provides the first proof that a linear growth rate ($|X_t| = \Theta(t)$) is sufficient, significantly lowering the theoretical bar for practical implementation.

Empirical Evaluation

The authors conducted extensive experiments to compare the proposed linear random grid search ("Uniform") against standard optimization methods, including Conjugate Gradient (CG), Nelder-Mead (NM), and L-BFGS-B. The benchmarks included six synthetic functions (2D to 6D) and an 11D AutoML hyperparameter tuning task.

As shown in the regret plots, the Uniform random search method is highly competitive. In several cases, such as the Hartmann functions, it achieves lower cumulative regret than more sophisticated gradient-based methods. This suggests that the exploratory nature of random sampling is particularly well-suited for the multi-modal landscapes of acquisition functions.

Beyond performance, the computational cost is a critical factor in BO.

The timing data reveals that the Uniform method consistently maintains the lowest average runtime. In high-dimensional tasks like the 11D AutoML benchmark, the speedup is even more pronounced, allowing for faster iteration cycles without sacrificing the quality of the optimization.

Conclusion

This work demonstrates that Bayesian Optimization is remarkably resilient to inexactness in the inner optimization step. By proving that a simple, linearly growing random grid search is theoretically sufficient and empirically superior in terms of efficiency, the paper validates common practitioner intuition with rigorous analysis. Future research may build on this by exploring adaptive sampling strategies that dynamically balance the computational budget of the acquisition solver with the progress of the global optimization.

Summary updated

Abstract

Bayesian optimization (BO) is a widely used iterative algorithm for optimizing black-box functions. Each iteration requires maximizing an acquisition function, such as the upper confidence bound (UCB) or a sample path from the Gaussian process (GP) posterior, as in Thompson sampling (TS). However, finding an exact solution to these maximization problems is often intractable and computationally expensive. Reflecting such realistic situations, in this paper, we delve into the effect of inexact maximizers of the acquisition functions. Defining a measure of inaccuracy in acquisition solutions, we establish cumulative regret bounds for both GP-UCB and GP-TS without requiring exact solutions of acquisition function maximization. Our results show that under appropriate conditions on accumulated inaccuracy, inexact BO algorithms can still achieve sublinear cumulative regret. Motivated from such findings, we provide both theoretical justification and numerical validation for random grid search as an effective and computationally efficient acquisition function solver.
BibTeX
@inproceedings{kim2025bayesian,
  author = {Hwanwoo Kim and Chong Liu and Yuxin Chen},
  title = {{Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=d1zqR0eqSR},
}
Figure