mlsanityData to 14 Oct 2026

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

arXiv 2506.11831 ↗First posted 13 Jun 2025stat.ML cs.LG stat.MEcited by 5

Not on the map. Why?

Abstract (arXiv)

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 by such findings, we provide both theoretical justification and numerical validation for random grid search as an effective and computationally efficient acquisition function solver.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 32 of its 55 references that are in the map. First posted on arXiv 13 Jun 2025.

Builds on

32 of 55 references.

References · 32

  1. 2018A Tutorial on Bayesian Optimizationcited by 744
  2. 2013Learning to Optimize Via Posterior Samplingcited by 256
  3. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 206
  4. 2018Neural Architecture Search with Bayesian Optimisation and Optimal Transportcited by 195
  5. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  6. 2021Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020cited by 148
  7. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
  8. 2020Neural Thompson Samplingcited by 128
  9. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  10. 2018Maximizing acquisition functions for Bayesian optimizationcited by 114
  11. 2019Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuningcited by 93
  12. 2021Adapting to Misspecification in Contextual Banditscited by 81
20 more
  1. 2015Bayesian optimization for materials designcited by 80
  2. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  3. 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
  4. 2019BayesNAS: A Bayesian Approach for Neural Architecture Searchcited by 68
  5. 2019Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonflycited by 67
  6. 2019Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variablescited by 66
  7. 2017Ensemble Samplingcited by 62
  8. 2021Misspecified Gaussian Process Bandit Optimizationcited by 55
  9. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  10. 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
  11. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  12. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  13. 2021Triangulation candidates for Bayesian optimizationcited by 11
  14. 2021The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oraclecited by 7
  15. 2023Introduction To Gaussian Process Regression In Bayesian Inverse Problems, With New ResultsOn Experimental Design For Weighted Error Measurescited by 6
  16. 2023When Combinatorial Thompson Sampling meets Approximation Regretcited by 6
  17. 2024Voronoi Candidates for Bayesian Optimizationcited by 5
  18. 2019Batched Stochastic Bayesian Optimization via Combinatorial Constraints Designcited by 4
  19. 2021Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximationscited by 4
  20. 2013Learning Policies for Contextual Submodular Predictioncited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Efficient optimization of expensive black-box simulators via marginal means, with application to neutrino detector designcited by 2
  2. 2025Bayesian Optimization on Networkscited by 0
  3. 2026BONSAI: Bayesian Optimization with Natural Simplicity and Interpretabilitycited by 0
  4. 2026Optimal Transport-based Permutation-Invariant Bayesian Optimization of Offshore Wind Farm Layoutscited by 0
  5. 2026Exploration strategies for Gaussian process bandit optimization with inference regret guaranteescited by 0