Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization

Summary

The paper presents a novel method for local Bayesian Optimisation. Instead of relying on estimates of the gradient of the black-box functions like earlier methods, the algorithm proposed in the paper minimises an upper bound on the objective function. The paper shows a connection between the proposed method and gradient descent, whose update rule can also be thought of as minimising a certain upper bound on function. The authors study the convergence of the proposed algorithm theoretically and empirically, and show it can develop improvement over existing baselines. Additionally, the authors propose a variant of the algorithm with an improved exploration strategy.

Strengths

The paper is generally well-written and I found the connection between MinUCB and Gradient Descent very appealing and nicely presented. Minimising UCB seems to be an interesting alternative to performing gradient steps, as it does not require the specification of the stepsize. Empirical results show that at least on a number of selected tasks, the algorithm delivers a non-negligible improvement in performance. Summing up the theoretical and empirical results of the paper, I believe their contribution is sufficient and I recommend accepting the paper.

Weaknesses

1. I belive Theorem 1 could use a proof sketch, currently just by reading the main body, it is impossible to understand where the result is coming from. 2. While authors acknowledge the existence of TuRBO and ARS, they do not empirically compare with them. It would be nice to see a comparison with those baselines, particularly with TuRBO, which is very popular. 3. In the related work, the authors mention the methods using additive models in high-dimensional Bayesian Optimisation but only cite relatively old papers (the newest one is from 2017). Since then, additive methods have seen much development. To make the section more up-to-date, it would be great if the authors would cite more recent work, such as [1] or [2]. [1] Ziomek, Juliusz Krzysztof, and Haitham Bou Ammar. "Are random decompositions all we need in high dimensional Bayesian optimisation?." International Conference on Machine Learning. PMLR, 2023. [2] Han, Eric, Ishank Arora, and Jonathan Scarlett. "High-dimensional Bayesian optimization via tree-structured additive models." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 9. 2021.

Questions

1. In the paper, the authors explain the UCB is most likely to be “small” around already queried points and thus conclude the algorithm is mostly local, however, potentially allows to make bigger steps if needed. I wonder what would happen if we explicitly constrained the algorithm to be local, e.g. via the trust region strategy of TuRBO? Would it be possible for authors to conduct a simple ablation study on at least one of the problems? Thus could help gauge whether the improvement delivered by the algorithm comes from better local optimisation or from occasionally switching to a more global search.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors explicitly state the lack of convergence guarantee for LA-MinUCB as a limitation.

Summary

This paper proposes and analysis a new local Bayesian optimisation scheme. The main idea is to replace the update of the current solution by minimising the upper confidence bound of the GP estimate (in the minimisation setting). The strategy is shown to obtain similar convergence rates as previous works. In addition, a "lookahead" variant of the algorithm is introduced. Finally, the proposed strategies are evaluated on synthetic benchmarks and RL tasks, showing competitive performance.

Strengths

*Originality*: The proposed algorithm is a variant of a prior approach (GIBO), which updates the iterate by minimising the UCB of the function instead if a local quadratic upper bound. The individual ideas are not necessarily novel (e.g. pessimistic estimates are quite commonly used in bandit/RL algorithms), but the combination with the local Bayesian optimisation scheme appears to be novel. *Quality*: * The obtained bounds are slightly worse than prior works, but on the upside do not require the knowledge of a Lipschitz bound. * The experiments show good performance on the synthetic benchmarks and RL tasks *Clarity*: * The algorithm and the motivation is clearly presented and overall the paper is well written, but would still benefit from polishing. However some details could be explained better as outlined below. *Significance*: Local Bayesian optimization schemes have been a very successful approach to zero-order (noisy) black box optimisation and the theoretical analysis of these algorithms is still lacking, although the ground work has been layed in the prior work by Wu et al (2024). The paper therefore contributes to this landscape and the results are relevant at least for the Bayesian optimisation community and may inform better optimisation algorithms more broadly; or encourage further improved bounds.

Weaknesses

My main concerns are the following: * The minimization of the UCB score in the step update appears to be global in nature. First, the range of min /argmin operations is never specified, e.g. in Algorithm 2, eq (4), (6), etc) which is confusing to the reader. Second, the authors claim that the acquisition step leads a "local" update (e.g. in lines 186-187, or the claim in 215 is not formally shown). What does it mean to be "local"? How is this formally proved? * While I agree with the general picture in Figure 1, and even if this is somewhat reflecting the general case, I believe one can construct kernels/examples where this "local" property is violated and the algorithm technically jumps to a different part of the domain (e.g. for linear kernel with near-zero slope, where observation data causes a sign switch and the step update moves to a different vertex of the domain). * Third, how can we efficiently find the minimizer of the UCB? We know that in general the UCB is not a convex function so finding the argmin is as hard as in global Bayesian optimization, without additional algorithmic constraints. * The discussion of prior works is lacking several works, e.g. the LineBO paper [1,2] which also provides local convergence guarantees based on a gradient descent scheme, and was shown in combination with trust regions. * The experiments lack several baselines (e.g. Turbo or LineBO) * The introduction of the Lookahead strategy in 7 is a bit out of the blue and not well connected to the remaining paper; and does not come with theoretical guarantees. How does this related/connected to Algorithm 1? * In general, the paper should better highlight the technical contributions and challenges related to the main result, and more formal/precise definitions of the problem setting and results. Minor remarks: * The abstract uses acronyms that have not been introduced (BO, GIBO). * The claim in line 28 that dimension 20 is a critical limit for Bayesian optimisation is somewhat arbitrary, even in lower dimensions convergence can be slow if the function is non-smooth etc. * Equation (2) and the surrounding discussion does not make sense to me: The right-hand side of (2) does not depend on x, and can therefore not used as acquisition function or to minimise over x. * The type setting of equation (1) looks odd - try using `\langle` and `\rangle` for the inner product. * Although not wrong, the discussion of UCB in line 164 is lightly miss-leading as the classical UCB approach is used in the maximization setting, and the corresponding quantity in the context of this paper would be the lower confidence bound (LCB). * 233: gamma is not defined * 241: What is n ? * 187: "view" -> "viewed". [1] Kirschner, J., Mutny, M., Hiller, N., Ischebeck, R., & Krause, A. (2019, May). Adaptive and safe Bayesian optimization in high dimensions via one-dimensional subspaces. In International Conference on Machine Learning (pp. 3429-3438). PMLR. [2] Kirschner, J., Mutný, M., Krause, A., Coello de Portugal, J., Hiller, N., & Snuverink, J. (2022). Tuning particle accelerators with safety constraints using Bayesian optimization. Physical Review Accelerators and Beams, 25(6), 062802.

Questions

Can you define what it means to be "local" and how the update step satisfies such a property?

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

The paper briefly discusses limitations, mainly the missing analysis of the lookahead approach.

Summary

The author proposed a local Bayesian optimization method using UCB to drive its iterates. The UCB step replaces the gradient descent step that is typically in such methods.

Strengths

The comparison of gradient-descent to UCB is very interesting. The author included analysis as well so there is enough content to the paper. The assumptions on kernels are interesting and not straightforward. Clearly, effort has been made to establish convergence, though I think some of the theorems in the appendix would be better labeled lemma.

Weaknesses

The biggest concern I have is that the algorithm is too similar to Bayesian optimization using UCB. The author tried to add more technical development such as the look-ahead algorithm. But the main difference from the proposed algorithm and GIBO is that the next iterate is found via UCB. In doing so, it's hard to argue the proposed algorithm is a gradient-based method anymore. And the proposed algorithm becomes too familiar.

Questions

1. Please proofread the paper to check grammar and spelling. For example, line 151, 161. 2. Line 171 "more likely to be lower than" should be "more likely to have a smaller value than". 3. Line 269 "minimize the minimum point?" 4. The gradient descent methods have a rich literature in how to choose the step size. It's not always $1/L$. The author should clarify on that point.

Rating

3

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

Summary

The paper presents an extension of a local Bayesian optimization strategy, specifically targeting methods based on gradient information (GIBO). GIBO-type algorithms operate through two stages: an exploitation step and an exploration step. The paper introduces two novel algorithms within this framework. In GIBO, the exploitation step is performed using gradient descent. The authors identify that gradient descent can be viewed as minimizing a quadratic upper bound. They further note that minimizing the tighter upper confidence bounds (UCB) can exploit more information from the GP surrogate model. Consequently, they replace the gradient descent step in GIBO with UCB minimization, resulting in a new algorithm named MinUCB. The paper provides a convergence analysis for MinUCB. The second algorithm modifies the exploration phase of GIBO to optimally query points using a look-ahead strategy, aligning with the new exploitation approach. Both algorithms are empirically evaluated on some established benchmarks.

Strengths

- The paper presents a clear, well-motivated, and relevant contribution to the field of local BO. - The related work is thoroughly discussed, situating the paper's contribution within the context of existing research. - The theoretical analysis is interesting and significantly strengthens the algorithmic contribution. - The proposed algorithms improve the state-of-the art for GIBO-style algorithms.

Weaknesses

## Main aspects **Locality**: In contrast to GIBO and MDP, the exploitation step is standard UCB. Therefore $x_{t+1}$ does not need to be in the local region around $x_{t}$. In fact this will only be the case if the algorithm is initialized in a region that is lower then the mean. I hypothesize that the "exploitation" step of MinUCB will explore globally until it finds a "promising region". I don't see this as a fundamental problem with the algorithm and may even allow MinUCB to switch between local and global exploration, which could be beneficial and avoid getting stuck in local optima. However, the paper does not discuss this behavior or explain why we should expect MinUCB to exhibit local-only exploration behavior. Including such a discussion and empirical investigations on how local MinUCB actually is could significantly improve the paper. **Empirical evaluation**: The empirical evaluation is limited, missing important details, and is generally not well executed. - The algorithm is evaluated on a subset of the problems in Nguyen et al. and does not introduce any new benchmarks. The low number of problems makes it hard to assess how efficient the algorithm really is, especially since the Hopper experiments seem problematic due to state normalization. No method is able to "solve" the hopper task, and the achieved reward is very low. - There are unexplained differences in the results on the synthetic benchmarks compared to those reported by Nguyen et al., where MDP and GIBO have similar performance after 500 evaluations. In the new results, GIBO outperforms MDP. - There are important details missing: 1. Batch sizes 2. Hyperpriors and hyperparameters - The code is not available for review, which hinders the evaluation of the experiments at the time of review. - The meaning of the error bars changes between plots. - A sensitivity study is missing. How sensitive is the algorithm to the choices of the newly introduced hyperparmeter, namely $\beta$ in the UCB? **Limitations**: The paper does not discuss the limitations of the proposed method and its evaluation. ## Minor - In Theorem 1, $n$ is never introduced. - The paper often cites arXiv preprints when peer-reviewed versions of the articles are available. - There are some grammar and spelling mistakes/inaccuracies: - "..solve _the_ high dimensional black-box.. problem" should be plural: "..solve high dimensional black-box.. problems" (there are many such problems). - "Gradient descent" should be lower case. - "large estimate to ensure _the_ convergence" should be: "large estimate to ensure convergence" (we are talking about general convergence behavior). - The typesetting of "L-smooth" is off, perhaps due to being typed in math mode. - Some words/abbreviations are typeset in math mode (e.g., in equation 3, "UCB"; in equation 5, "trace"). - Equation 1 is hard to parse due to the nested inequality and scalar product symbols. - Figure 3: "LA-MinUCB has consistently optimal performance." In what sense is the performance optimal? This claim seems premature and needs clarification.

Questions

1) In line 54 and later in the evaluation the authors claim "MPD ... can exhibits numerical instability.." but do not follow up on this claim. What numerical instabilities were observed? 2) Why limit the experiments to a subset of the problems in Nguyen et al.? 3) Why choose constant batch sizes and beta when the theory predicts choices with guaranteed convergence? Why deviate from the theoretically obtained values? 4) Why are the results on the synthetic benchmarks significantly different from those reported in Nguyen et al.? 5) How where the batch sizes chosen?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The limitations of the algorithm are not discussed and need to be addressed. For instance, the paper derives convergence for specific choices of beta and batch sizes, but chooses different values in the empirical results. This discrepancy raises the question of whether there is a gap between theory and practice. Discussing these limitations and the rationale behind the chosen parameters in the experiments would provide a more comprehensive understanding of the algorithm's performance and applicability.

reply to the author

Dear author, Thank you for the rebuttal. Sorry for the late reply. I understand your motivation. But algorithm-wise, it seems to me your algorithm is still UCB BO. Your rebuttal did not add any information that would refute this, in my opinion. Correct me if I am wrong. Even down to the choice of $\beta$ for convergence analysis. I understand how you have come to UCB from the gradient descent algorithms. But you end up with an existing algorithm, albeit with some tweaks. I appreciate a lot of the extra work you put in, but to me this is clearly an upgrade to UCB. Only now your convergence has actually been weakened to a gradient optimality (KKT) condition, which does not even guarantee a local minimum. I really appreciate the KKT condition, in accordance with the "local" emphasis. But in my humble opinion, going from a global algorithm (UCB) to a local algorithm is not necessarily an upgrade. I know you are just comparing to existing gradient descent type methods. But you have to compare to UCB because that's what you ultimately proposed. Correct me if I am wrong. Thank you.