mlsanityData to 14 Oct 2026

Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal

arXiv 2410.10384 ↗First posted 14 Oct 2024stat.ML cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

Bayesian Optimization (BO) is widely used for optimising black-box functions but requires us to specify the length scale hyperparameter, which defines the smoothness of the functions the optimizer will consider. Most current BO algorithms choose this hyperparameter by maximizing the marginal likelihood of the observed data, albeit risking misspecification if the objective function is less smooth in regions we have not yet explored. The only prior solution addressing this problem with theoretical guarantees was A-GP-UCB, proposed by Berkenkamp et al. (2019). This algorithm progressively decreases the length scale, expanding the class of functions considered by the optimizer. However, A-GP-UCB lacks a stopping mechanism, leading to over-exploration and slow convergence. To overcome this, we introduce Length scale Balancing (LB) - a novel approach, aggregating multiple base surrogate models with varying length scales. LB intermittently adds smaller length scale candidate values while retaining longer scales, balancing exploration and exploitation. We formally derive a cumulative regret bound of LB and compare it with the regret of an oracle BO algorithm using the optimal length scale. Denoting the factor by which the regret bound of A-GP-UCB was away from oracle as g(T), we show that LB is only log g(T) away from oracle regret. We also empirically evaluate our algorithm on synthetic and real-world benchmarks and show it outperforms A-GP-UCB, maximum likelihood estimation and MCMC.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 24 of its 41 references that are in the map. First posted on arXiv 14 Oct 2024.

Builds on

24 of 41 references.

References · 24

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2018Pyro: Deep Universal Probabilistic Programmingcited by 380
  3. 2017On Kernelized Multi-armed Banditscited by 352
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  5. 2021High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspacescited by 141
  6. 2016Corralling a Band of Bandit Algorithmscited by 100
  7. 2020HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisationcited by 83
  8. 2021Misspecified Gaussian Process Bandit Optimizationcited by 55
  9. 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 51
  10. 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 47
  11. 2023Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?cited by 36
  12. 2023Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisationcited by 32
12 more
  1. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 31
  2. 2018Regret bounds for meta Bayesian optimization with an unknown Gaussian process priorcited by 31
  3. 2023Self-Correcting Bayesian Optimization through Bayesian Active Learningcited by 22
  4. 2020Regret Balancing for Bandit and RL Model Selectioncited by 20
  5. 2021BOiLS: Bayesian Optimisation for Logic Synthesiscited by 18
  6. 2021Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applicationscited by 17
  7. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  8. 2022Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization (ZoMBI)cited by 14
  9. 2024Time-Varying Gaussian Process Bandits with Unknown Priorcited by 11
  10. 2021How Bayesian Should Bayesian Optimisation Be?cited by 5
  11. 2023Adaptation to Misspecified Kernel Regularity in Kernelised Banditscited by 5
  12. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 3.

7 papers.

  1. 2025Adaptive Prior Selection in Gaussian Process Bandits with Thompson Samplingcited by 2
  2. 2025Just One Layer Norm Guarantees Stable Extrapolationcited by 2
  3. 2025Informed Initialization for Bayesian Optimization and Active Learningcited by 2
  4. 2026Regret Analysis of Guided Diffusion for Black-Box Optimization over Structured Inputscited by 1
  5. 2024Vector Optimization with Gaussian Process Banditscited by 0
  6. 2026Online Sharp-Calibrated Bayesian Optimizationcited by 0
  7. 2026Bayesian Optimization of CVaR with Unknown Hyperparameterscited by 0