# Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimation

arXiv: https://arxiv.org/abs/2306.06844 · HTML: https://mlsanity.com/paper/2306.06844/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 62 references that are in the map.
- First posted on arXiv 12 Jun 2023.

## Builds on (most cited first, 21 of 21)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO](https://mlsanity.com/paper/2109.06716/) (2021)
- [HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation](https://mlsanity.com/paper/2012.03826/) (2020)
- [On Statistical Bias In Active Learning: How and When To Fix It](https://mlsanity.com/paper/2101.11665/) (2021)
- [Automated Reinforcement Learning (AutoRL): A Survey and Open Problems](https://mlsanity.com/paper/2201.03916/) (2022)
- [πBO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimization](https://mlsanity.com/paper/2204.11051/) (2022)
- [Provably Efficient Online Hyperparameter Optimization with Population-Based Bandits](https://mlsanity.com/paper/2002.02518/) (2020)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso](https://mlsanity.com/paper/2111.02790/) (2021)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Gryffin: An algorithm for Bayesian optimization of categorical variables informed by expert knowledge](https://mlsanity.com/paper/2003.12127/) (2020)
- [Self-Correcting Bayesian Optimization through Bayesian Active Learning](https://mlsanity.com/paper/2304.11005/) (2023)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Accelerating Experimental Design by Incorporating Experimenter Hunches](https://mlsanity.com/paper/1907.09065/) (2019)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)

## Built on by (most cited first, 2 of 2)

- [High Dimensional Bayesian Optimization using Lasso Variable Selection](https://mlsanity.com/paper/2504.01743/) (2025)
- [ORTHOBO: Orthogonal Bayesian Hyperparameter Optimization](https://mlsanity.com/paper/2605.06454/) (2026)

## Abstract (arXiv)

Gaussian process (GP) based Bayesian optimization (BO) is a powerful method for optimizing black-box functions efficiently. The practical performance and theoretical guarantees of this approach depend on having the correct GP hyperparameter values, which are usually unknown in advance and need to be estimated from the observed data. However, in practice, these estimations could be incorrect due to biased data sampling strategies used in BO. This can lead to degraded performance and break the sub-linear global convergence guarantee of BO. To address this issue, we propose a new BO method that can sub-linearly converge to the objective function's global optimum even when the true GP hyperparameters are unknown in advance and need to be estimated from the observed data. Our method uses a multi-armed bandit technique (EXP3) to add random data points to the BO process, and employs a novel training loss function for the GP hyperparameter estimation process that ensures consistent estimation. We further provide theoretical analysis of our proposed method. Finally, we demonstrate empirically that our method outperforms existing approaches on various synthetic and real-world problems.