# No-Regret Bayesian Optimization with Unknown Hyperparameters

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2019.

## Built on by (most cited first, 30 of 51)

- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Pre-trained Gaussian Processes for Bayesian Optimization](https://mlsanity.com/paper/2109.08215/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Self-Correcting Bayesian Optimization through Bayesian Active Learning](https://mlsanity.com/paper/2304.11005/) (2023)
- [Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applications](https://mlsanity.com/paper/2109.02606/) (2021)
- [GoSafeOpt: Scalable Safe Exploration for Global Optimization of Dynamical Systems](https://mlsanity.com/paper/2201.09562/) (2022)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Online Calibrated and Conformal Prediction Improves Bayesian Optimization](https://mlsanity.com/paper/2112.04620/) (2021)
- [Safe exploration in reproducing kernel Hilbert spaces](https://mlsanity.com/paper/2503.10352/) (2025)
- [Tuning Legged Locomotion Controllers via Safe Bayesian Optimization](https://mlsanity.com/paper/2306.07092/) (2023)
- [Batch Bayesian Optimization for Replicable Experimental Design](https://mlsanity.com/paper/2311.01195/) (2023)
- [Tuning Particle Accelerators with Safety Constraints using Bayesian Optimization](https://mlsanity.com/paper/2203.13968/) (2022)
- [Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal](https://mlsanity.com/paper/2410.10384/) (2024)
- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)
- [DUET: Optimizing Training Data Mixtures via Feedback from Unseen Evaluation Tasks](https://mlsanity.com/paper/2502.00270/) (2025)
- [Thompson Sampling via Fine-Tuning of LLMs](https://mlsanity.com/paper/2510.13328/) (2025)
- [Meta-Learning Hypothesis Spaces for Sequential Decision-making](https://mlsanity.com/paper/2202.00602/) (2022)
- [Sharp Calibrated Gaussian Processes](https://mlsanity.com/paper/2302.11961/) (2023)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [End-to-End Learning of Deep Kernel Acquisition Functions for Bayesian Optimization](https://mlsanity.com/paper/2111.00639/) (2021)
- [Lifelong Bandit Optimization: No Prior and No Regret](https://mlsanity.com/paper/2210.15513/) (2022)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)

## Abstract (arXiv)

Bayesian optimization (BO) based on Gaussian process models is a powerful paradigm to optimize black-box functions that are expensive to evaluate. While several BO algorithms provably converge to the global optimum of the unknown function, they assume that the hyperparameters of the kernel are known in advance. This is not the case in practice and misspecification often causes these algorithms to converge to poor local optima. In this paper, we present the first BO algorithm that is provably no-regret and converges to the optimum without knowledge of the hyperparameters. During optimization we slowly adapt the hyperparameters of stationary kernels and thereby expand the associated function class over time, so that the BO algorithm considers more complex function candidates. Based on the theoretical insights, we propose several practical algorithms that achieve the empirical sample efficiency of BO with online hyperparameter estimation, but retain theoretical convergence guarantees. We evaluate our method on several benchmark problems.