mlsanityData to 7 Oct 2026

Tight Regret Bounds for Bayesian Optimization in One Dimension

arXiv 1805.11792 ↗First posted 30 May 2018stat.ML cs.IT cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time T behaves as Omega(√T) and O(√Tlog T). This gives a tight characterization up to a √log T factor, and includes the first non-trivial lower bound for noisy BO. Our assumptions are satisfied, for example, by the squared exponential and Mat'ern-nu kernels, with the latter requiring nu > 2. Our results certify the near-optimality of existing bounds (Srinivas em et al., 2009) for the SE kernel, while proving them to be strictly suboptimal for the Mat'ern kernel with nu > 2.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 May 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 1; 2023: 3; 2024: 1; 2025: 6; 2026: 4.

20 papers.

Sort:

  1. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  2. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  3. 2021Neural Contextual Bandits without Regretcited by 40
  4. 2023The Behavior and Convergence of Local Bayesian Optimizationcited by 19
  5. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  6. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  7. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  8. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  9. 2022Lower Bounds on the Worst-Case Complexity of Efficient Global Optimizationcited by 7
  10. 2024Regret Analysis for Randomized Gaussian Process Upper Confidence Boundcited by 4
  11. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 3
  12. 2023Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimationcited by 2
8 more
  1. 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
  2. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
  3. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 2
  4. 2025Adaptive Prior Selection in Gaussian Process Bandits with Thompson Samplingcited by 1
  5. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  6. 2021LinEasyBO: Scalable Bayesian Optimization Approach for Analog Circuit Synthesis via One-Dimensional Subspacescited by 0
  7. 2023Generalization within in silico screeningcited by 0
  8. 2025Bayesian Optimization over Bounded Domains with the Beta Product Kernelcited by 0