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:
- 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.
- 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