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

Weakness 1: I belive Theorem 1 could use a proof sketch...

Response: We apologize for not including a proof sketch in the paper. The core tool we use in the paper is actually to prove the Lipshitz properties of various functions in Gaussian processes, i.e. the mean function $\mu(x)$, and the standard derivation function $\sigma(x)$. However, the difficulty is that the $\sigma(x)$ is not Lipshitz continuous under some conditions. We develop some tools to build a similar property for $\sigma(x)$ with some controllable error. We use the lipshitz properties of these function to build the following inequality: $f(x_{t+1})\le\min_{x\in \mathcal{X}}\mu(x)+\beta_{t}\sigma(x)\le f(\hat{x}^{t+1})+e_{t}<f(x_{t})+e_{t}$ where $\hat{x}^{t+1}=x_{t}-\eta_{t}\nabla \mu(x_{t})$, and stepsize $\eta_{t}$ decreases at a logarithmic rate with $t$, and error term $e_{t}$ will decrease to 0. $\hat{x}^{t+1}$ is actually the gradient descent point starting from $x_{t}$. This inequality will directly help to prove the final result, i.e. the gradient convergence result.

Weakness 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.

Response: We are sorry that our paper did not compare with these methods. We have added comparison results with TurBO in the experiment, please refer to the Fig 1,2,3 in the attached PDF for details.

Weakness 3: ...only cite relatively old papers ...

Response: We apologize for not citing the latest works. Relevant content will be added in future versions of the paper.

Question 1: ...I wonder what would happen if we explicitly constrained the algorithm to be local, e.g. via the trust region strategy of TuRBO? ...

Response: Thank you for your comment. We have added this type of experiments in Fig 4 in the PDF attached in the global rebuttal. We apply the trust region constrain on MinUCB, and find that adding the trust domain may actually lead to a worse result. We can explain from two aspects. On the one hand, the changes in the trust region are not timely. At the beginning, the radius of the trust region is small, which limits the search range. However, when approaching local optimum points, minimizing UCB often does not exceed the range of the trust region. The second aspect is that MinUCB itself can also be explained from the perspective of trust region, which can be refered to the third point of global rebuttal. So overall, as our method adopts the idea of trust region, it behaves local and can achieve good results.

We thank the reviewer for the constructive feedback. The suggestions and questions are briefly responded below.

Weakness 1 and Question 1: The minimization of the UCB score in the step update appears to be global in nature... The range of min /argmin operations is never specified... What does it mean to be "local"?

Response: Thank you for your comment. In this paper, we would like to emphasize that the term 'local' mentioned does not refer to limiting optimization within a small range, such as Turbo, but rather to the algorithm exhibiting local behavior. Although the minimization is performed globally on UCB, according to our explanation in the first point of global rebuttal, the standard deviation term $\beta\sigma(x)$ actually behaves as an additional penalty on the searching, which will limit the search to be near the current data set.

In our view, another main difference between global and local algorithm, is whether the algorithm attempts to conduct a global exploration. Local methods such as approximate gradient descent methods like GIBO or MPD, or other well-known Turbo methods, basically use greedy strategies to try to find a point with a lower function value than the previous iteration. They do not consider exploring the entire space to find possible global optimum. This strategy can ensure that each step has a descent and quickly converges to a local optimum point. This is because when we have a sequence $\\{f(x_1), ..., f(x_n), ...\\}$,Where $f(x_{i+1})<f(x_i)$, it can be mathematically proven that this sequence will eventually converge, and at the same time, $\\{x_i,i=1...\\}$ (or at least a subsequence of it) will also converge to a point $x^*$. Under these algorithms, this $x^*$ is likely to be a local optimum point or saddle point of the function. According to the first explanation of MinUCB in the global rebuttal, we can assume that MinUCB also uses this greedy strategy, and only concentrates on the descent of the function value, which ensures that MinUCB can converge to the local optimum points efficiently. MinUCB can also be explained through a trust region view, which can be seen the third point of global rebuttal.

Weakness 2: ...One can construct kernels/examples where this "local" property is violated...e.g. for linear kernel...

Response: Thank you for your comment. We believe that the example you mentioned, that is, under a linear kernel, it is indeed possible for the algorithms to have a large search distance . However in this example, the global optimum and the local optimum are the same (if the optimum is unique). When some local information about the Gaussian process is known, such as the current function value being higher than the Gaussian process prior mean, or the norm of gradient being large nearby, MinUCB and LA-MinUCB will have a relatively large search distance, as the local information indicates that the local optimum point is a certain distance away from the current point. However, this is not a global search, as it is only looking for a point that is better than the current point function value through the information of Gaussian process. This greedy strategy will quickly approach the local optimum point of the current region, which is also its advantage over other methods as it better utilizes the information of Gaussian process.

Weakness 3: How can we efficiently find the minimizer of the UCB?

Response: In our numerical experiments, we only used the built-in optimizer in Botorch without any special range restrictions, but it seems that there was no significant numerical instability when minimizing UCB. If the dimensionality is really high, we believe that the results of the previous iteration can be used as a starting point to find a better local optimum point of UCB, which can at least achieve better results compared to the previous step.

Weakness 4: ...Lacking several works, e.g. the LineBO paper...lack several baselines(e.g. Turbo or LineBO)

Response: We are very sorry for not including an introduction to the LineBO series of work. We will include it in future version of paper. We have added a comparison with TurBO in Fig 1,2,3 in the PDF attached to the rebuttal, but due to time constraints, we apologize that we may not be able to present the comparison results with LineBO in this rebuttal. We will add relevant experiments in future version of paper.

Weakness 5: The introduction of the Lookahead strategy...not well connected to the remaining paper...

Response: Thanks for your comment. As the main contribution of our paper is to bulid the relationship between gradient descent with minimizing UCB, and MinUCB still partially depend on the gradient (the local exploration), then is it possible to develop an algorithm that better utilize the concept of UCB? Thus we apply a look ahead strategy to build the LA-MinUCB, and the experimental results are also very competitive. Proving the convergence of LA-MinUCB should be an important research direction in the future.

Weakness 6: In general, the paper should better highlight the technical contributions and challenges related to the main result...

Response: We are sorry for not clearly describe our contributions and challenges in our paper. We think the main contribution of this paper, is exactly to build the relationship between minimizing UCB and gradient descent under the Gaussian process surrogate, and show that minimizing UCB will bring extra efficiency in local search. We also develop the algorithms MinUCB and LA-MinUCB to utilize this idea. The theoretical proof for MinUCB is a big chanllage and is technically not trivial. We have developed some tools to prove the convergence of this algorithm.

Weakness 7: Minor remarks

Response: We apologize for some of the inaccurate statements and will improve them in future versions of the paper. $\gamma$ is a coefficient in the matern kernel, and $n$ is the number of samples.

We thank the reviewer for the constructive feedback. The suggestions and questions are briefly responded below.

Weakness 1: Locality: I hypothesize that the "exploitation" step of MinUCB will explore globally until it finds a "promising region"... switch between local and global exploration

Response: Thank you for your comments and suggestions. We acknowledge a phenomenon that when the initial point value is higher than the prior mean, there may be a larger step size in the initial one or two exploitation step. However, this should be a fast local search instead of a global exploration. As we mentioned in the point 2,3 in global rebuttal, the local exploitation in each step is only to try find the point that have a lower value than the previous one, which does not involve global exploration idea. For the global-local balance, it's possible to use a mutistart strategy , which is similar as TurBO. However, we believe that the main contribution of this article is to propose the relationship between minimizing UCB and gradient descent under a Gaussian processes surrogate, and give the corresponding theory, so we do not emphasize the global-local balance in this paper.

Weakness 2 and Question 2,5: Empirical evaluation: details, no new benchmarks, error bars, open source code

Response: Thank you for your comments. In our experimental settings, we basically used the same settings as GIBO and MPD. For example, the hyperpriors is the uniform distribution on an interval and and hyperparameters is set the same as GIBO and MPD. For MinUCB, the batch size for local exploration is the data dimension $d$. For LA-MinUCB, we set the batch size as $d$ in synthetic experiments, and emperically find that when the batch size is chosen as $0.2d$ on the reinforcement learning task, the numerical experiments will have good result.

We apologize for the lack of experiments in the original submission. We have added other real world objectives mentioned in MPD [1]. The experimental results can be seen in Fig 3 in the pdf attached to the rebuttal.

The differnent error bar is mainly due to the significant differences between sampled functions in the synthetic data, and directly plotting will result in large variances at different points. So we applied scaling to achieve better visual effects. We are sorry for not making the code public because we are afraid that it may lead to the leakage of author information, but we guarantee that the experimental results are accurate, and will make it public after the acceptance of paper.

Weakness 3: Lack of sensitivity study

Response: We are sorry for the lack of sensitivity experiments, which will be included in future papers. The PDF for this rebuttal does not have enough space to place the results. Overall, the $\beta$ controls the convergence speed and final convergence result. When $\beta$ is relatively small, the convergence speed will be fast. However, the final convergence result may be slightly weaker than that when $\beta$ is large. This is quiet similar with the gradient descent with a large or small stepsize. Small $\beta$ means the local exploitation is more aggresive, but may lose some accuracy, which will cause the algorithm jump around the local optima.

Weakness 4 and Question 1,4: The difference between our experimental result and Nguyen. et al[1]

Response: Thank you for your comments. When we conducted experiments based on Nguyen's code , we found that the MPD method is very likely to stuck at a specific point, and the search results afterwards may even get worse. This phenomenon is particularly significant in synthetic experiments. The MPD results in our experiment are actually very similar to the previous results of Nguyen et al., that they both achieving good result after the first batch of point. However, GIBO performed better in subsequent searches, and is robustness in diffenrent experiments. We speculate that this may be due to randomness or other unknown settings.

Question 3: Why choose constant batch sizes and beta

Response：The reason for selecting a fixed batch size and $\beta$ is to compare with previous methods. The previous methods used fixed parameters, so we also use fixed parameters for reasonable comparison. Although it is theoretically necessary to increase the batch size and $\beta$ to ensure convergence, fixed parameters can actually achieve good results (although there is a small distance between the result and the true local optimum).

[1] Quan Nguyen, Kaiwen Wu, Jacob Gardner, and Roman Garnett. Local bayesian optimization via maximizing probability of descent. Advances in neural information processing systems, 35:13190–13202, 2022

We thank the reviewer for the constructive feedback. The suggestions and questions are briefly responded below.

Weakness : 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.

Response: Thanks for your comment. In our work, we focus on 'local' algorithm and show that the algorithm we propose, and specifically the acquisition function of minimizing UCB can provide an efficient local search approach. This is in contrast to the traditional minimization of LCB (on the minimization problem context), where the focus is to directly balance the trade-offs between exploration and exploitation for global optimization.

We achieve this by first build the relationship between minimizing UCB and gradient descent under the Gaussian process surrogate, and show that minimizing UCB from this view will bring extra efficiency in local search. This provides us with an interesting idea that if we replace gradient descent with minimizing UCB, we may propose alternative efficient local BO algorithms. That is why we propose our two algorithms, MinUCB and LA-MinUCB, to illustrate this idea. As you mentioned, the proposed algorithm is not a gradient-based method anymore, but this is actually our final goal. The point selection strategy in our algorithm, has a similar behaviour as the gradient descent. The coefficient $\beta$ in UCB controls the search area, that larger $\beta$ will force algorithm to search in a smaller area, this is just similar with the stepsize in gradient descent. Our algorithm design use the idea of previous approximate gradient algorithm, and we apply minimizing UCB to better utilize the Gaussian process, which allows our method to integrate the advantages of both aspects. This makes our methods look similar to UCB, but in fact there are fundamentally different, that we transform the UCB concept from a global one to a local one. The experimental results also indicate that this combination can bring significant performance improvements, demonstrating the effectiveness of our idea.

Question 1,2,3: grammar and spelling

Response : Thanks for correcting the spelling and grammar errors in the paper, and we will make all revisions in future versions of the paper.

Question 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.

Response: Thank you for your suggestion. In this paper, we mainly want to explain the relationship between minimizing UCB and gradient descent. Some concepts may not be expressed clearly, and we will revise the relevant description in future versions of the paper.

Dear Reviewer,

Thanks for your fast response and further clarification of your concern. We would like to appreciate your view and perspective on the UCB, which is quite relevant to our topic. We will answer your questions from the following three aspects:

Why we focus on a local approach?

In this paper, we want to emphasize that what we focus on is the local approach instead of searching the global optima. The reason is that, searching the global optima is nearly impossible in high dimensional case, which is so-called curse of dimensionality. Typical global algorithms will have poor performance on high-dimensional problems. Take traditional UCB BO algorithms as an example, that they try to balance exploration and exploitation through maximizing UCB or minimizing LCB. In high dimensional problem, this ‘exploration’ may become ‘over-exploration’. Traditional UCB BO uses almost all points to learn all uncertain parts of the function, making the algorithm approach the global optimum very slowly. This is also reflected in [1], that the regret bound of UCB BO will grow exponentially with data dimension $d$. Traditional UCB BO also performs poorly in high-dimensional experiments. According to your latest suggestions, we have applied traditional UCB BO on our synthetic experiments and found that this method can hardly achieve any high value in these experiments. Similar experimental results can be found in Wu et al. [2].

On the contrary, local approach, like approximate gradient methods [2,3] or trust region methods [4], only focus on searching in a small area, which effectively decrease the over-exploration. Besides, a local optimum can be found relatively quickly, and exponential sample complexity is only necessary if one wishes to enumerate all local optima [2]. Although local approach only focuses on local optimums, this type of method still outperforms traditional global methods in high-dimensional performance [2,3,4]. That is why we mainly focus on local optimization algorithms in high-dimensional problems. As global and local are two completely different concepts, the global method and local method cannot be equated.

How do we transform the traditional UCB concept into a local one?

According to the statements above, we need to look at the local approach (focused on local optimization), and specifically those based on approximated gradient descent, as they have been proved to be effective in local BO. Our objective is to improve the efficiency of this type of gradient based approach. We first realize that there is a relationship between minimizing UCB and gradient descent under the Gaussian process surrogate, and show that minimizing UCB will bring extra efficiency in local search. Minimizing UCB, as it is a rather conservative strategy and only focuses on local exploitation (please refer to viewpoint 1 of Global Rebuttal), is a new idea and is completely different with the concept in traditional UCB BO method (as traditional UCB still considers exploration). We replace gradient descent with minimizing UCB to obtain extra efficiency, and thus we propose our two algorithms, MinUCB and LA-MinUCB, to illustrate this idea.

It should also be noted that our MinUCB achieve a polynomial convergence rate with data dimension $d$, and this result is impossible to be obtained in traditional UCB BO. This is because traditional UCB BO will only converge at global optimum and its regret bound will grow exponentially with $d$. That's also why our method performs very well in high dimensions, and our results far exceed the original UCB BO in these cases.

How to do global search in high dimensional case?

As the traditional BO like UCB BO falls in high dimensional case, a local search with adaptive restarts (similar with TurBO [4]) or a mixed global local search with our local algorithm can be much more efficient. According to the results in [2], local search with multiple starting points can effectively approximate the global optimal value without a large difference, and is very competitive with global methods.

[1] Srinivas, Niranjan, et al. "Gaussian process optimization in the bandit setting: No regret and experimental design." arXiv preprint arXiv:0912.3995 (2009).

[2] Wu, Kaiwen, et al. "The behavior and convergence of local bayesian optimization." Advances in neural information processing systems 36 (2024).

[3] Müller, Sarah, Alexander von Rohr, and Sebastian Trimpe. "Local policy search with Bayesian optimization." Advances in Neural Information Processing Systems 34 (2021): 20708-20720.

[4] Eriksson, David, et al. "Scalable global optimization via local Bayesian optimization." Advances in neural information processing systems 32 (2019).