Abstract
Bayesian optimisation requires fitting a Gaussian process model, which in turn requires specifying hyperparameters - most of the theoretical literature assumes those hyperparameters are known. The commonly used maximum likelihood estimator for hyperparameters of the Gaussian process is consistent only if the data fills the space uniformly, which does not have to be the case in Bayesian optimisation. Since no guarantees exist regarding the correctness of hyperparameter estimation, and those hyperparameters can significantly affect the Gaussian process fit, theoretical analysis of Bayesian optimisation with unknown hyperparameters is very challenging. Previously proposed algorithms with the no-regret property were only able to handle the special case of unknown lengthscales, reproducing kernel Hilbert space norm and applied only to the frequentist case. We propose a novel algorithm, PE-GP-UCB, which is the first algorithm enjoying the no-regret property in the case of unknown hyperparameters of arbitrary form, and which supports both Bayesian and frequentist settings. Our proof idea is novel and can easily be extended to other variants of Bayesian optimisation. We show this by extending our algorithm to the adversarially robust optimisation setting under unknown hyperparameters. Finally, we empirically evaluate our algorithm on a set of toy problems and show that it can outperform the maximum likelihood estimator.
Introduction
Bayesian Optimization (BO) is a powerful framework for optimizing expensive black-box functions. Central to BO is the Gaussian Process (GP) surrogate model, which relies on a "prior"—a set of hyperparameters defining the function's expected behavior, such as smoothness and variance. While theoretical analysis often assumes these hyperparameters are known, practical applications must estimate them, typically using Maximum Likelihood Estimation (MLE). However, MLE lacks consistency guarantees in the non-uniform sampling regimes characteristic of BO, especially in time-varying environments. This paper introduces PE-GP-UCB (Prior Elimination GP-UCB), the first algorithm to provide no-regret guarantees for unknown hyperparameters of any form in both Bayesian and frequentist settings.
Methodology
The PE-GP-UCB algorithm addresses hyperparameter uncertainty through two primary mechanisms:
- Double Optimism: Instead of relying on a single estimated model, the algorithm maintains a set of candidate priors. At each iteration, it selects the point $x$ and the prior from the candidate set that together maximize the Upper Confidence Bound (UCB). This "optimism in the face of uncertainty" extends to the model space itself.
- Prior Elimination: To prevent the algorithm from being misled by incorrect models, it employs a rigorous rejection mechanism. After each observation, the cumulative prediction error for each candidate prior is evaluated against a theoretically derived threshold. If a prior's error exceeds this threshold, it is permanently removed from the candidate set.
The theoretical foundation of this approach ensures that the "true" prior is never eliminated with high probability. If multiple priors remain, they must all be sufficiently consistent with the data to ensure low regret.
Experimental Evaluation
The researchers evaluated PE-GP-UCB against several baselines, including MLE-GP-UCB, Regret Balancing, and Fully Bayesian GP-UCB, across two main benchmarks:
- Synthetic Toy Problem: A stationary function optimized within a time-varying search space. This setup tests the algorithm's ability to handle non-stationarity induced by the environment. Eleven candidate priors were used, each with different mean function "hill" locations.
- Intel Temperature Dataset: A real-world challenge involving temperature readings from 50 sensors. The goal is to identify the sensor with the peak temperature at any given time, using priors derived from historical covariance data.
Key Results
PE-GP-UCB demonstrated significant advantages over traditional methods:
- Robustness to Model Mismatch: In the toy problem, MLE often converged to incorrect priors, leading to linear regret. In contrast, PE-GP-UCB successfully eliminated incorrect models and converged to the true prior.
- Superior Performance in Dynamic Settings: On the Intel dataset, PE-GP-UCB outperformed MLE and Regret Balancing. While MLE often committed to a prior that performed poorly over time, PE-GP-UCB's elimination strategy allowed it to favor more effective models.
- Theoretical and Empirical Alignment: The algorithm's sub-linear regret scaling (proportional to the square root of the number of priors) was empirically validated, showing it to be more efficient than standard "master algorithm" frameworks.
Discussion and Conclusion
PE-GP-UCB represents a significant step forward in making Bayesian Optimization more robust to hyperparameter uncertainty. By shifting the focus from reward-based comparison (like Regret Balancing) to prediction-error-based elimination, the algorithm achieves greater stability in non-stationary environments.
While the current framework scales well with the number of discrete priors, future work could address the challenges of continuous hyperparameter spaces and the computational overhead of maintaining multiple GP models. Nonetheless, the provided no-regret guarantees and strong empirical performance establish PE-GP-UCB as a principled approach for BO with unknown priors.
Summary updated