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

Summary

This paper considers the Bayesian optimization (BO) problem under an unknown length scale and upper bound of the RKHS norm. The proposed algorithm LB-GP-UCB is designed to select length scale from certain candidates set adaptively. Furthermore, the algorithm eliminates some candidate length scales if certain conditions are met. The validity of the proposed algorithm is given both empirically and theoretically. Specifically, the proposed algorithm has a favorable property compared with the existing A-GP-UCB algorithm in the sense of regret optimality.

Strengths

- The motivation is well-discussed; specifically, I agree with the issue of the A-GP-UCB algorithm described in the Introduction. - From my view, the comparison with A-GP-UCB in the sense of regret optimality is interesting and novel. - Enough numerical evaluations are given, and the author also provides the anonymized codes with an easily reproducible style.

Weaknesses

- In contrast to the existing literature (Berkenkamp, 2019), the analysis is limited to where the length scale parameters are the same among each coordinate. This relates to the limitation of the practical applicability, and I think that the comparison with A-GP-UCB should be evaluated by noting this limitation. - The method how to calculate the quantity $R^{\theta}$ (Line 3), which contains MIG we only know the dependence of $T$ and $\theta$ of its upper bound, is ambiguous. As far as I see the proof of Lemma C.1 and the statement of Lemma 5.2 of Pacchiano et al., $R^{\theta}$ should be specified as the exact upper bound of regret; only the knowledge of the order of the regret upper bound is insufficient to specify $R^{\theta}$. If we cannot calculate the exact value or upper bound of $R^{\theta}$, this part can become a limitation, and the author at least should add the discussion. As far as I see the anonymized code, the numerical experiments are done by approximating the upper bound of MIG with the numerically optimized version of MIG (Hong et al, 2023). Even if we follow Hong et al, 2023, I believe that the exact version of the upper bound of MIG can be computed only when the input space $\mathcal{X}$ is finite and small. - To my understanding, the Ziomek's paper is closely related to your setting, and it seemed that some parts of your paper (e.g., Lemma A.2) borrow their ideas; however, the relation and comparison with their paper are not described in Related Works. Ziomek, Juliusz, Masaki Adachi, and Michael A. Osborne. "Beyond Lengthscales: No-regret Bayesian Optimisation With Unknown Hyperparameters Of Any Type." arXiv preprint arXiv:2402.01632 (2024). [Minor] - L108 $x^{\ast} = \max_{x \in \mathcal{X}}$ -> $x^{\ast} = \max_{x \in \mathcal{X}} f(x)$. - L110 ... value $\theta \in \mathbb{R}$ we denote -> ... value $\theta \in \mathbb{R}$. We denote - L117 ... them below:: -> ... them below: - L119 $\theta \in \\{0, \theta_0\\}$ -> $\theta \in (0, \theta_0]$. - L129 $\gamma(k^{\theta})\_{t-1}$ -> $\gamma_{t-1}(k^{\theta})$ - L129 $\frac{1}{2} \ln |I + \sigma_N^2 K_T^{\theta^{\ast}}|$ -> $\frac{1}{2} \ln |I + \sigma_N^{-2} K_T^{\theta}|$. - Footnote 1 and Lemma 4: This statement does not hold for any stationary kernel (see Assumption 2 in Bull [11]). I recommend the author explicitly assume RBF or Mat\'ern kernel in these statements. - Liu et al., 2023 related to your setting. Although the unknown hyperparameter they consider is different from the setting of your paper, I recommend adding their paper as the related work. - Liu, Yusha, and Aarti Singh. "Adaptation to Misspecified Kernel Regularity in Kernelised Bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

Questions

- Is there a possibility of extending the algorithm to a case where length scale parameters are different among each coordinate? - In Proposition 2.3, can the author update the Berkenkamp's MIG upper bound of Mat\'ern to $\tilde{O}(T^{\frac{d}{2\nu + d}})$? The recent result (Vakili et al., 2021) shows that the maximum information gain of Mat\'ern kernel increases with $\tilde{O}(T^{\frac{d}{2\nu + d}})$. Their results do not provide explicit dependence of $\theta$; however, by combining Theorem 3 of Vakili et al. and the eigendecay rate of the kernel with explicit dependence of $\theta$, I guess that $\gamma_T = \tilde{O}(\theta^{-2\nu + d} T^{\frac{d}{2\nu + d}})$ can be obtained. - Vakili, Sattar, Kia Khezeli, and Victor Picheny. "On information gain and regret bounds in gaussian process bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2021. - The exact upper bound of the MIG is obtained by relying on the uncertainty sampling as described in Section 5.1 of Srinivas's paper. Does any problem occur with using Srinivas's results in the author's analysis? - Srinivas, Niranjan, et al. "Gaussian process optimization in the bandit setting: No regret and experimental design." arXiv preprint arXiv:0912.3995 (2009).

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

- The analysis is limited to the case where the length scale parameters are the same among each coordinate. - No potential negative societal impact is seen.

Summary

This paper proposes a novel Bayesian optimization algorithm for the setting with unknown kernel lengthscale. The proposed approach improves upon prior work by running a logarithmic array of algorithms on exponentially decreasing lengthscales in combination with a regret balancing scheme. The paper proves a regret guarantee with an exponential improvement compared to prior work in the ratio of the regret compared to the oracle algorithm that knows the optimal lengthscale. The experimental evaluation also shows substantial improvements compared to prior the prior work.

Strengths

Originality: This paper introduces a clever regret balancing scheme to obtain a improved regret bound for Bayesian optimization with unknown kernel lengthscale. While the individual ideas already appear in prior work (e.g. regret balancing, and decreasing the lengthscale), the combination in this setting is novel. Quality & Clarity: The paper is overall well written but could benefit from careful proof reading (some suggestions below). The main idea is easy to follow and there is an extensive comparison to the prior work. The regret bound is a significant improvement over prior work. The experimental evaluation shows that the proposed approach outperforms the prior work. Significance: The findings are of high interest to the Bayesian optimization community (and users of Bayesian optimization) as selecting hyperparameter remains a major challenge. In particular, classical schemes (like marginal likelihood) tend to fail because there is too little data initially.

Weaknesses

The paper could use some polishing for English and punctuation (e.g. many sentences are quite long). In addition, the authors could provide more intuition (e.g. why regret balancing works, and the elimination scheme) and try to make the paper more accessible to readers not familiar with the tools used. Minors: * line 110: punctuation * Algorithm 1, line 7: Is there a simpler notation for the set $S_t^\theta$ ? * 209: Long sentence, unclear what "their" refers to. * 229: Wording/missing word "highest ? as possible"

Questions

N/A

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

The main limitation is that the approach so far only works for a scalar parameter that induces a natural nesting of Hilbert spaces.

Summary

This paper introduces LB-GP-UCB (Lengthscale Balancing GP-UCB), a Bayesian Optimization (BO) algorithm that proposes a new tuning of the covariance function hyperparameters. A regret bound is derived, with logarithmic improvement over A-GP-UCB, the most similar solution in the literature. Some numerical experiments also show improvements in practice.

Strengths

LB-GP-UCB is a significant improvement over A-GP-UCB, and constitutes an interesting step forward in the field of no-regret BO with unknown hyperparameters.

Weaknesses

My concerns are mostly related to the experimental part of the paper. **Missing Baselines**. In Section 6, the authors seem to discard many solutions addressing the problem of BO with unknown hyperparameters because they do not provide any theoretical analysis for their algorithms (see [13, 20, 25, 28] in the main paper). Although I understand that LB-GP-UCB comes with an additional, reassuring theoretical guarantee, its empirical performance should still be compared against some empirical algorithms at least. **Missing Benchmarks**. Only four benchmarks were considered, I think that is not enough for a comprehensive study of LB-GP-UCB's empirical behavior. I believe additional experiments should be run. **Impact of the Dimension $d$**. The dimensionality of the objective function may have an important impact on the performance of LB-GP-UCB. However, the dimensionality of the problems was not specified in the main text nor in the Appendix E entitled "Experimental Details". **Wall-Clock Time Comparison**. In Appendix E, it is mentionned that all experiments for every method (except MCMC) took up to 4 minutes to run, but I would be interested in the precise wall-clock time for each solution and each experiment. This is important as online estimation of the hyperparameters brings a computational overhead to the BO algorithm.

Questions

Here are some questions to spark the discussion with the authors. (1) Have you compared LB-GP-UCB to any of the algorithms presented in [13, 20, 25, 28]? If not, on what ground have you discarded them for your empirical evaluation? (2) Why have you chosen these 4 benchmarks? I know that the rebuttal period is very short, but I believe more experimental results on a variety of problems (e.g., different smoothness of the objective function, different dimensionality...) should be considered to strengthen Section 5. (3) What were the dimensionality for the considered benchmarks? Do you have any insight on how LB-GP-UCB would react to higher-dimensional problems? (4) Do you have the precise wall-clock times for each solution and each experiment?

Rating

6

Confidence

3

Soundness

2

Presentation

1

Contribution

3

Limitations

I believe the authors have properly addressed the limitations of their work.

Summary

This paper proposes an approach to deal with unknown hyper-parameters in Gaussian process upper confidence bound (GP-UCB) algorithms, a popular Bayesian optimisation (BO) strategy. The objective function is assumed to be a member of a reproducing kernel Hilbert space (RKHS) associated with a translation-invariant kernel class whose length-scale is unknown. Algorithms are proposed to adaptively estimate the unknown kernel length-scales and an upper bound on the RKHS norm of the objective function, which are common hyper-parameters for GP-UCB algorithms. Theoretical guarantees on the regret for the proposed algorithms are provided, which show that rate of the algorithm's cumulative regret to the regret of an algorithm with knowledge about the exact hyper-parameters are only logarithmic in contrast to previous approaches. Experimental results are presented comparing the regret of the proposed algorithms to typical hyper-parameter estimation strategies in the BO literature.

Strengths

* The paper builds well on existing theoretical results and a novel rigorous analysis. * Experimental results show improvements against existing popular hyper-parameter estimation strategies, bringing new insights. * Existing relevant literature seems well covered by related work section. * The text is well organised following a mostly clear structure.

Weaknesses

* It is unclear how close the estimated length-scale and RKHS norm are to their true values at each iteration. * There are no (theoretical) convergence results on the algorithm’s estimates, only the regret bounds. * The proposed algorithms are only compared against other GP-UCB strategies. It’d be interesting to see how they compare to other methods which do not require explicitly knowledge of the RKHS norm bound, for example, such as expected improvement algorithms. There are also no comparisons against meta-learning BO strategies. Even though they require prior data, it’d be interesting to see how close (or better) the performance of the proposed algorithms can get to them.

Questions

* Another important hyper-parameter that might affect GP-UCB algorithms' performance is the sub-Gaussian noise parameter upper bound. However, the paper presents no discussion about the noise parameter. I was wondering if the authors have considered estimation strategies for that hyper-parameter as well.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Discussions on the main limitations of the theoretical analysis are presented, but there are no discussions on scalability issues, such as problems involving high-dimensional data or large datasets, which often require low-rank GP approximations. There are also no discussions on noise hyper-parameters (i.e., the sub-Gaussian noise parameter), another important hyper-parameter that might be unknown for some applications.

Rebuttal Ack

Thank you for the clarifications. I am now positive about the paper and I have increased my score to 6.