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

We would like to thank the reviewer for reading our paper and for mentioning relevant related work. We address each question/concern below.

Case of different length scales

The method of Berkenkamp (2019) cannot really handle kernels with differing length scales across coordinates. While technically A-GP-UCB can be applied to non-isotropic kernels, it decreases the lengthscale value for each coordinate at the same pace (e.g. see eq. 9 in (Berkenkamp, 2019)). As such, unless the initial length scales $\theta_0$ differ for each coordinate (which would imply strong some prior information on the relative importance of coordinates), A-GP-UCB utilises the same length scale value for each coordinate at each timestep, making it no better than an algorithm utilising the isotropic kernel. As such, our algorithm is not inferior to A-GP-UCB on that regard.

As we mention in Section 7, to the best of our knowledge, there have been no results in the literature deriving the MIG bounds for the non-isotropic kernels. If one were to obtain such bounds, we believe we could very easily extend our algorithm LB-GP-UCB to handle multiple unknown length scales, in the same way as we extended it to the case of simultaneously handling unknown norm and length scale. Such an algorithm would truly handle the non-isotropic case and would be able to potentially choose to fit a GP model with different length scale values, unlike A-GP-UCB.

Updating MIG bound

We would like to thank the reviewer for mentioning that the improved MIG bounds exist, as we were not aware of that fact. We will replace the MIG bounds with the improved ones in our Theorems.

Relation to Ziomek et al, 2024

The problem setting considered in (Ziomek et al, 2024) differs from ours, as they assumed there are a number of candidate hyperparameter values given to us at the start of the problem, making the problem much easier. Their proposed algorithm also scales with the MIG of the worst candidate and as such could be arbitrarly far from the optimal. We will add this discussion to the Related Work section.

Knowledge of Regret Bounds

One do not need the exact form of the regret bounds---the knowledge up to a constant is sufficient. The fact that the algorithm selects hyperparameters by the rule in line 3 is only used in two places in the proof of the Theorem 4.1 The first place is Lemma C.1., where the constants $C$ in the regret bounds cancel out. The second place is in line 472 - 474 on page 14, where we assume that for the regret bounds we must have $R(t+1) < R(t) + 2B$, since $2B$ is the highest instantaneous regret we can possibly suffer. If the order dependence is known, one can always find such a constant $C$ such that this constraint is respected.

While the lack of need for exact knowledge of $C$ might seem surprising at first glance, it is a direct result of the fact the regret bound for LB-GP-UCB is also derived up to a constant factor. Changing $C$ in the suspected regret bound does not affect the order dependence of the regret bound of LB-GP-UCB. This is a very interesting point and we are grateful to the reviewer for mentioning it. We will add a short discussion in the paper to clarify this.

Applicability of the MIG bounds from (Srinivas et al, 2009)

The results from Srinivas et al (2009) rely on uncertainty sampling to derive a bound on the sum of predictive variances for any strategy (the MIG bound). In fact, Srinivas et al (2009) use this MIG bound to derive a regret bound for the GP-UCB algorithm. If each of the GP-UCB base algorithms were run in isolation, these bounds clearly hold. These bounds must therefore also hold in the case, where datapoints are shared between algorithms, as variance is a non-increasing function of the number of conditioning datapoints.

Minor points

We would like to thank the reviewer for pointing out the typos and that Lemma 4 of [11] requires an additional assumption. We will correct the typos and explicitly restrict the statement to RBF or Matern kernel. We would also like to thank for pointing out more relevant, related work, we will add it to the related work section.

We would like to thank the reviewer for reading our submission, and pointing out the issues with writing. We will correct the writing errors pointed out by the reviewer and try to break long sentences into shorter ones. We agree that the algorithm is quite complex and it would be good to give more intuition to the readers. We plan to use the additional page in the camera-ready version to add a longer, more intuitive explanation of the regret balancing scheme with some easily-understandable figures.

When it comes to the definition of set $S_t^\theta$, in the pseudocode, it would be possible to drop the iteration subscript $t$ and just redefine the set at each iteration. However, we explicitly wanted to index this set by the current timestep $t$ and the hyperparameter value $\theta$, as this notation is very convienient later in the proofs.

We would like to thank the reviewer for reading our submission and providing feedback on our paper. We address each question/concern below:

(1) The methods used by [13] and [28] are equivalent to the MCMC baseline we compared against, where the hyperparameters are marginalised from the acqusition function using Monte Carlo samples (as we mention at the beginning of Section 5). [25] is an empirical study of robustness to misspecification of the prior on hyperparameters that does not provide any novel method of hyperparameter estimation. The codebase of [20] has been taken down from the web, and currently no publicly available implementation of their algorithm exists.

(2) We chose benchmarks with differing smoothness throughout the domain (Berkenkamp, Michalewicz) or those that exhibit "needle in a haystack" behaviour (such as Material Design problems), as typically used methods such as maximum likelihood tend to struggle on these kinds of problems. Our benchmarks were chosen to showcase how our method can be used to tackle problems with which existing methods struggle. Of course, if one were to chose lesschallenging benchmarks with constant smoothness throughout the domain, it is entirely possible the improvement delivered by LB-GP-UCB over MLE and other baseline would be smaller. We do not claim that our method would provide universal improvement across all sorts of benchmarks, but rather that MLE and MCMC can perform poorly on a certain class of problems on which our algorithm performs well. We will add this comment to the limitation section.

We would also like to emphasise that the paper proposing A-GP-UCB (published in JMLR, 2019) included only two empirical benchmarks, so we would argue that our experimental evaluation of four benchmarks meets the standard for papers, whose main contribution is theoretical. In fact, Reviewer YCMG mentions "Enough numerical evaluations are given (...)".

(3) The Berkenkamp function is a 1-dimensional synthetic function. We used a 5-dimensional version of the Michalewicz function. AGNP and CrossedBarrel are 5-dimensional and 4-dimensional real-world problems, respectively. We will amend the manuscript to include the dimensionality of each of the problems.

As we prove in the paper, LB-GP-UCB can recover performance "close" to the performance of GP-UCB optimiser with the oracle knowledge of the optimal length scale value. However, it is well-known that even the regret bound of this oracle optimiser would grow with the dimensionality of the problem and same is true for the LB-GP-UCB. To remedy that, one could enhance LB-GP-UCB optimiser in the same way as standard BO optimiser is being enhanced to perform well in high-dimensional spaces (e.g. by adding a Trust Region or decomposing the input space). These enhancements are orthogonal to our method.

(4) Yes, we do have wallclock times for our experiments. We provide them below and will update the script to include the exact wallclock times in the Appendix. All the times below are seconds, values after +/- are standard errors from accross the seeds.

Berkenkamp Function:

MLE : 438 +/- 0.66

A-GP-UCB : 443 +/- 1.51

LB-GP-UCB : 442 +/- 1.68

MCMC : 1653 +/- 25.99

Michalewicz Function:

MLE : 237 +/- 2.41

A-GP-UCB : 167 +/- 0.88

LB-GP-UCB : 181 +/- 0.47

MCMC : 3388 +/- 369.38

Crossed Barrel Materials Experiment:

MLE : 55 +/- 0.1

A-GP-UCB : 48 +/- 0.4

LB-GP-UCB : 48 +/- 0.5

MCMC : 471 +/- 25.2

AGNP Materials Experiment:

MLE : 53 +/- 0.05

A-GP-UCB : 49 +/- 0.18

LB-GP-UCB : 49 +/- 0.16

MCMC : 246 +/- 3.56

As such, LB-GP-UCB is faster than MLE on all benchmarks except for Berkenkamp Function, where it is 4 seconds ($\approx 1$ %) slower. MCMC is significantly slower than any other baseline.

We would like to thank the reviewer for reading our submission and for their appreciation for our theoretical analysis and empirical evaluation. We address each question/concern below.

Convergence of length-scales estimates In general, we consider the setting in which the function can arbitrarly change its smoothness throughout the domain. As such, it is impossible to guarantee correctness of the length scale estimation unless we cover the input space with an infinitely-dense grid---however, doing so would defeat the purpose of conducting sample-efficienct optimisation. Our algorithm side-steps the need for accurate length scale estimation by appriopriately balancing the regret. As such, we do not consider it a weakness that we do not solve the impossible task of precisely estimating length scales---instead, we propose an alternative approach that solves a practically-relevant problem.

Also, as shown in Figures 2 and 4, in practice, the length scale values typically selected by our algorithm are close to the estimates of optimal length scale value. As such, while we cannot guarantee the convergance of that estimator (which, as explained before, would be impossible in the considered setting), we observe reasonable convergence empirically.

Comparison to Exptected Improvement While it is true that EI does not require knowledge of the RKHS norm to compute the acqusition function, in practice, EI still requires the specification of output scale value $c$ for the kernel $c k(x,x^\prime)$. We have that $||f||_{ck} = \frac{||f||_{k}}{c}$, so if we do not know the RKHS norm, we still have one more parameter to find. Additionally, EI still requires knowledge of the length scale. Our algorithm can be used to remedy these problems also in the case of EI, where each of the base learners could be an instance of GP-EI instead of GP-UCB.

Comparison to Meta-Learning strategies The only previous work of which we are aware that solves the problem of unknown hyperparameters via meta-learning is the work of , which we cite in the related work section. They assume the training and target function were sampled from the same Gaussian Process prior, which is a different setting from ours, were we do not impose any prior on the black-box function.

We did not compare against meta-learning baselines, as such approaches are only applicable where one can easily find functions that are highly "similar" to the target functions. For the benchmarks we considered, it is not clear how to find such similar functions.

Case of unknown noise The problem of simultaneously estimating noise magnitude and length scale value is ill-posed as, for example, pointed by [Karvonen and Oates, 2023]. An intuitive way to see that this problem is ill-posed is by observing that if the function values we observe change rapidly, we can never know for sure if the change is caused by the true function $f(\cdot)$ changing rapidly (implying a short length scale value) or by the magnitude of noise being large and function changing slowly (implying long length scale value). As such, simultanous estimation of noise magnitude and kernel hyperparameters is likely impossible. However, we agree that we should comment on this, when discussing limitations. We will update the paper to reflect that.

Scalability Limitations Scalability to high-dimensional spaces and large datasets is a limitation of virtually all optimisation methods based on standard Gaussian Process models. These limitations are not particularly tied to the method we propose. However, for clarity, we will update the script to clearly mention those issues as a limitation of the standard Gaussian Process model and, by extension, a limitation of our algorithm, which relies on that model.

References Karvonen, Toni, and Chris J. Oates. "Maximum likelihood estimation in Gaussian process regression is ill-posed." Journal of Machine Learning Research 24.120 (2023): 1-47.