Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization
Authors: Zheyi Fan
Wenyu Wang
Szu Hui Ng
Qingpei Hu
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian Optimization
Local Optimization
High dimensional
Minimizing upper confidence Bound
Primary area: optimization
TL;DR: We propose two local Bayesian optimziation algorithms to show that minimizing the UCB is better strategy than gradient descent in local search with a Gaussian process surrogate.

Abstract: Local Bayesian optimization is a promising practical approach to solve the high dimensional black-box function optimization problem. Among them is the approximated gradient class of methods, which implements a strategy similar to gradient descent. These methods have achieved good experimental results and theoretical guarantees. However, given the distributional properties of the Gaussian processes applied on these methods, there may be potential to further exploit the information of the Gaussian processes to facilitate the BO search. In this work, we develop the relationship between the steps of the gradient descent method and one that minimizes the Upper Confidence Bound (UCB), and show that the latter can be a better strategy than direct gradient descent when a Gaussian process is applied as a surrogate. Through this insight, we propose a new local Bayesian optimization algorithm, MinUCB, which replaces the gradient descent step with minimizing UCB in GIBO. We further show that MinUCB maintains a similar convergence rate with GIBO. We then improve the acquisition function of MinUCB further through a look ahead strategy, and obtain a more efficient algorithm LA-MinUCB. We apply our algorithms on different synthetic and real-world functions, and the results show the effectiveness of our method. Our algorithms also illustrate improvements on local search strategies from an upper bound perspective in Bayesian optimization, and provides a new direction for future algorithm design.

Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization
Zheyi Fan 1.2 Wenyu Wang Szu Hui Ng Qingpei Hu!
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, China "cchool of Mathematical Sciences, University of Chinese Academy of Sciences, China
Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore 1.2 [fanzheyi, qingpeihu) Camss ac cn, "{wangyy, issnss) @nus. edu.sg
Abstract
Local Bayesian optimization is promising practical approach to solve high dimen- sional black-box function optimization problem. Among them is the approximated gradient class of methods, which implements strategy similar to gradient descent. These methods have achieved good experimental results and theoretical guarantees. However, given the distributional properties of the Gaussian processes applied on these methods, there may be potential to further exploit the information of the Gaussian processes facilitate the Bayesian optimization search. this work, we develop the relationship between the steps of the gradient descent method and one that minimizes the Upper Confidence Bound (UCB), and show that the latter can be a better strategy than direct gradient descent when a Gaussian process is applied as surrogate. Through this insight, we propose new local Bayesian optimization al- gorithm, MinUCB, which replaces the gradient descent step with minimizing UCB GIBO [22]. We further show that MinUCB maintains similar convergence rate with GIBO. We then improve the acquisition function of MinUCB further through a look ahead strategy, and obtain a more efficient algorithm LA-MinUCB. We apply our algorithms on different synthetic and real-world functions, and the results show the effectiveness of our method. Our algorithms also illustrate improvements on local search strategies from upper bound perspective in Bayesian optimization, and provides a new direction for future algorithm design.
Introduction
Bayesian Optimization one of the most well-known black box function optimization methods, where objectives can be extremely expensive to evaluate, noisy, and multimodal. The high efficiency of Bayesian Optimization finding global optima leads to the widespread application various
research fields, such as hyperparameter tuning [10] 11 28
neural architecture search [26., chemical
experiment design [2], reinforcement learning 31 aerospace engineering [16]. However, the
performance of Bayesian optimization is limited by the input dimension d, as the theoretical regret
bound grows exponentially with input dimension (25] This difficulty hinders the application of Bayesian optimization when the actual dimension of problem is rather high [8].
There are various methods that have been proposed to handle this difficult task, including works that rely on some assumptions on the model structure, such as the assumption that the majority of the variables have no effect [6] or the kernel satisties an additive structure (9] Local Bayesian optimization methods, which focus on finding a local optima (instead of the global one), have also been a popular (and less restrictive) compromise to manage the curse of dimensionality. Representative
CCoresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

methods of these include those based on local trust region methods 77. local latent space [20]. and approximated gradient methods [22 23 36. Among them the approximate gradient method has demonstrated strong performance in practical applications compared with other methods. The approximate gradient method can be described as a two-stage algorithm, which loops through the following two processes: first sample points to decrease the uncertainty of the local area according to a local exploration acquisition function, and then moving to the next point with a trustworthy high reward through local exploitation acquisition function. Müller et al. [22] applied the idea of gradient descent and first proposed the GIBO algorithm, which was designed to alternate between sampling points to minimize the posterior variance of the gradient
given location, and then moving in the direction of the expected gradient. Nguyen et al. [23] proposed MPD, which improved the local exploitation acquisition function through defining the descent direction by maximizing the probability of descent, and designed corresponding local exploration acquisition function to match this strategy. Wu et al. [36] further provided the detailed proof on the local convergence of GIBO with a polynomial convergence rate, for both the noiseless and noisy cases.
Although the approximated gradient method has been shown to be practical in dealing with high- dimensional problems, there may be still some room to potentially improve on the current methods. We motivate the ideas for improvement with the following two questions.
1) We observe that GIBO only utilizes the posterior distributions of the gradient at a point, which will ignore most of the information provided by Gaussian process surrogate in the region, which may lead to an inefficient descent. MPD attempts to make better use of Gaussian processes by performing multi-step descent, but this strategy can exhibits numerical instability and may lead to suboptimal performance of the algorithm (as seen in Section R). This motivates us to think: is there a better local exploitation acquisition function that can ensure the algorithm fully utilizes Gaussian process information, and also guarantee the convergence to local optima points?
2) Do these acquisition functions necessarily need to depend on accurate gradient estimates at a point, or are there other acquisition functions that can improve the efficiency and still ensure local convergence?
In this paper, attempt to answer the above two questions through our two new local Bayesian optimization algorithms. To address the first question, we first develop the relationship between the step of the gradient descent method and minimizing the Upper Confidence Bound (UCB). When the Gaussian process is applied as the surrogate model, minimizing the UCB can usually achieve a point with a higher reward than simply doing gradient descent. Motivated by this idea, we propose our first algorithm, Local Bayesian Optimization through Minimizing UCB (MinUCB), which replaces gradient descent step with a step that minimizes the UCB in the GIBO algorithm. We show that MinUCB will also converge to local optima with a similar convergence rate as GIBO. This discovery is also meaningful as opens up possibilities for new designs on local Bayesian optimization algorithms. In this work we further apply the look ahead strategy to construct the local exploration acquisition function that is more compatible with minimizing the UCB, and propose our second algorithm, Look Ahead Bayesian Optimization through Minimizing UCB (LA-MinUCB). This algorithm is shown to be one step Bayesian optimal, and address our second question as local efficient BO acquisition function does not require the additional step and accuracy of gradient estimate. We implement extensive experiments to demonstrate the performance of our algorithms under different settings. The experimental results illustrate that our algorithms have better performance compared to other methods across many synthetic and real-world functions. We summarize our contributions as follows:
We develop the relationship between the gradient descent step and minimizing the UCB, and show that minimizing UCB is more efficient when the Gaussian process is the underlying surrogate.
We show that minimizing UCB is an efficient and accurate objective for local exploitation and propose MinUCB.
We improve the local exploration acquisition function of MinUCB and obtain more efficient local Bayesian optimization algorithm LA-MinUCB.
We apply different synthetic and real-world function on our algorithm, and the results show the effectiveness of our methods.
2

---

lundion
Aporosimated Gradient bound
Real function
Gradkett hound
Upser contidense bound
Usper car corficence bound
0.5
0,25
Our method
Previous mothod
0.5
0.25
0.5
0.75
1.25
1.5
-6
22
x
Figure I: This function f is sampled from GP(O, k(,, )), where k(r, x exp( x )²) with standard derivation of white noise 0.05. The dataset contains 2 points, which marked as black hollow circle. We attempt to search the next point from Xp- The left figure shows that UCB bound is much tighter than other two gradient based bounds, and the minimum points of UCB has the best performance. This shows that minimizing UCB in this example can achieve much better move lower point than the gradient descent approach. The right figure illustrates UCB across the design space. Here we see that it is small only near the sampled point, and increases as it moves further away, indicating that minimizing UCB can be viewed as local strategy.
Literature Review
High dimensional optimization is growing research area, where many different methods have been proposed to solve this problem, including Bayesian optimization methods. Among the BO methods, the most widely studied approach focuses on structured Gaussian processes, which imposes additional assumptions, such as low dimensional active spaces or additive spaces, on kernel function or data structure. This includes the Additive and ANOVA Models 44. in which the kernel of Gaussian process is defined through the summation of univariate kernels. This essentially decompose the original Gaussian process into a sum of low dimensional Gaussian processes, which facilitates computations and convergence 9 37 13 Another approach along these lines assumes that the objective function depends only on low dimensional subspace, and examples include hyperparameter optimization for neural networks (3. Most of these methods suppose a subspace is linear subspace of the original Euelidean space. Wang et 34 apply random linear embeddings to approximate this subspace and propose REMBO. Letham et al. [88] improve this and tries to fix over exploration of boundary and distortions in embedding through adaptive linear embeddings [8]. Other methods to learn the subspace structure include low-dimension matrix recovery 5 and nonlinear embeddings (21).
As mentioned in the Section [ another line of research to address the computational and high dimensional challenges is to compromise and focus the BO to be more local, limiting the search region facilitate computational feasibility and efficiency. Typical approaches along these lines look at incorporating the information about the local optimum restricting the problem to sequence of iteratively chosen -ie-dimensional sub-problems [4 using trust regions 7 32 20), which
expands and shrinks the size of its trust regions with information in each iteration, and approximated
gradient methods [22 23 36 Among them, the gradient based method MPD [23], proposed
by Nguyen et al. has demonstrated very strong performance compared with other local methods, including gradient based method GIBO [22], trust region method Turbo 7 and Augmented Random Search (ARS) 19). Given the promising performance of approximate gradient methods, we leverage and extend the works of GIBO and MPD, to provide a simplier and more general local BO approach that can perform as well.
3 Preliminaries
3.1 Bayesian Optimization
In this paper, we focus the problem of minimizing black-box function f(-):
min
fx)
xeX
3

---

We assume that no higher order information can be obtained from the oracle Serrth-Order-Oracke) where only i.i.d noisy function evaluations y = f(x) + E, (O, o²) can be observed. Here we focus on applying Bayesian optimization to solve the problem. BO is a surrogate based optimization approach where the objective function typically modeled with Gaussian process, and an acquisition function is constructed to sequentially determine next evaluation points in the optimization process.
3.2 Gaussian process and its derivatives
Currently Gaussian process (GP) is one of the most widely used surrogate model today as it has nice analytical form and is flexible capture various functional forms. A GP(m(x), k(xx, x is specified by its mean function m--) and kernel function k(--). Without loss of generality, we assume the mean function m(x) O. Suppose f is sampled from the (O k(x, x }), and we already have a dataset D = {x11 31), ..., (Xn, yn) and set XD = [X1,..,, Xnl. YD = [V/ Vi..... ynl then the posterior over f is also ())))(()) kND (x, x )), where
(x( = k(x, X ( (k X XD) + - kD x ) k(x, x ) k XD) (A: XD) -
(x) kD k x)
where XD) [k(x, x1),,... ki( xn)], ,(,,,)) k(x,Xo) XD)" and k(XD, XD) is the posi- tive definite kernel matrix [k:(x,,, X,) )a.jsn
It should be noted that if the kernel function k is differentiable, then the derivative of is also GP. Given the dataset D, The posterior of satisfies:
V GP(VPD(() Vkp(..)V'
In this work we only consider the noisy case, i.e. the standard derivation of white noise a > 0.
The relationship between gradient descent and minimizing UCB
We first review the traditional gradient descent approach. This approach is fundamentally based on the assumption of the smoothness of the function:
Definition 1. (Smoothness) A function f is L-smooth if and only for all X1 E X. we have
| fxx)) - v.((x))ll S L||x] - X21l2
Suppose the initial point is Xa, and function f()) is L-smooth, then we will have the following inequality:
f(x) f(x)) + (VI(xo), xo) + -1x x
(1)
This provides quadratic upper bound on f, and the minimum value of this upper bound is taken at x X₂ (xp). In the gradient descent approach, the minimum value of this upper bound is taken as the descent step, where L. is used as the step size in traditional gradient descent analysis. In this view gradient descent can treated as selecting the minimum point of this quadratic upper bound Eq.
As direct gradient information is not observable in practice, the upper bound Eq. 1 cannot be obtained. and approximate gradient methods instead attempt to derive looser upper bound based on Eq. I In GIBO [22 36], they replace the gradient V f(x)) with the derivative of the Gaussian process v up (x)) ). and apply the strategy x =
77 V up (x)) when the variance of this gradient is
small enough. According to the proof of Lemma 15 in (3). GIBO is also result of optimizing
different upper bound of f()). If x is chosen to be the form of upper bound is:
x Xo (DD(()))) and S 1
L. this
f(x) < f(x))
2 (x)(x)) V fxx)]l
(2)
If the approximation error of gradient ViD - V / ||2 small enough, , then the optimal vj is chosen as 1. This upper bound Eq. 2 is actually the local exploitation acquisition function of GIBO.

---

Algorithm 1: MinUCB: Local Bayesian Optimization through Minimizing UCB
Input: A black-box function f, and initial point x1
2 for { = 1,2, ..... T do
...,...?
3
X1 = x ...., xfI' E IR xd
#Resample multiple times on X;
4
X = arg minz Gunce (x,, Z) where Z E R xd
#Local exploration (sampling)
X = |
5
evaluate the black-box function on X, obtaining noisy measurements y
7
Dj = D:-1 U yX
X++1 arg minl MrD, (x) + (x)
#Local exploitation (step move)
end
Although these two bounds have intuitive application in the gradient descent, they do have some limitations. The first is the obtainment of the L-smooth coefficient. Although it possible to estimate the L-smooth coefficient through the Gaussian process, this estimation is expensive as it needs many samples, especially in high dimensional cases. The second is that these two bounds are relatively loose, and the minimum points of these two bounds tend to be too close to Xo- Upper bound Eq. (1 is quadratic and increase very fast when the point x is far from Xy, and upper bound Eq. (2) only allows the stepsize y to be less than 1. When L is unknown and we have to give it a large estimate to ensure convergence (usually in real case), the above phenomenon becomes more severe. Taking this view of gradient descent approaches
moving along the minimum of an upper bound of f()), then leads us to explore if it is possible to discover some tighter upper bounds, where the minimum point is lower than that in Eq. ① and Eq. 4 This can lead to find point with possible higher reward.
commonly used concept in Bayesian Optimzation is the upper confiedence bound (UCB), which is defined as followed:
UCB(x) (D(x) + (x
Previous work mainly focused maximizing UCB find the maximum value of function [29] However, it should be noted that UCB is also natural bound for function f()). UCB fully utilizes the posterior distribution of f(-), ), and give every point probabilistic bound depending on the coefficient
3. The standard deviation term oz (x) has an upper bound and will not grow faster than the quadratic
function, which means the UCB will not change drastically. This indicates that if we select x to be
arg min uD (x) + (x)
Then the function value fxx) more likely to have a smaller value than the points obtained through optimizing the upper bound Eq. ①T] and Eq. (2). This is because the points obtained by minimizing UCB can be further away from the initial point compared to simply gradient descent.
Fig ( shows a simple 1-dimension illustrative example. In this example, sample function from GP k(xx (z, )), where k(2,, x') exp(-1
(z - x' )²), and the standard deviation of white noise o = 0.05. Here we illustrate the search of the next point from To based on the upper bound perspective of three methods. Suppose we have already sampled two points. which are marked as black hollow circles. These two data points are selected through Central Finite Difference Approximations 27]. which is aimed to better estimate the gradient of (x(x)). In the left figure, the green line represent the real quadratic upper bound Fq. (1) at Xg. and the blue line is calculated through Eq. (2). The coefficient in UCB bound Eq. 3p is set as 3, which means that for any point x, the probability of fx) < U (C) is close to 99.9%. 9%. It can be seen from the left figure in Fig (1 that the UCB bound is much tighter than other two bounds, and the minimum point of the UCB bound has a much lower function value than the gradient based method. The right figure plots the UCB across the input space, and we see that the UCB changes relatively slowly and will reach infinity. Further we observe that UCB is only small near the sampled point, indicating that minimizing the UCB can be viewed as a local strategy. This simple example illustrates that with a Gaussian process function, minimizing UCB can achieve better point than the gradient methods, as UCB efficiently utilizes the information from Gaussian process. Based on these insights, we propose two new local Bayesian optimization algorithms, and demonstrate their performances in several numerical examples.
5

---

It should be noted that in MinUCB we resample multiple times on the local exploitation result X with batch size b(2) (line 3 in Algorithm lp. This step is mainly added to ensure the theoretical convergence of the algorithm. This step will typically be only a very small proportion of sampling 5 Local Bayesian Optimization through Minimizing UCB
The analysis the above section provides us with an important idea, that if we replace the gradient descent step with a step that minimizes a tighter upper bound such as UCB, we may be able to achieve a better result in local optimization. Our first algorithm, Local Bayesian Optimization through Minimizing UCB (MinUCB) (Algorithm []. is developed with this idea, and we show that minimizing the UCB for the step move is an efficient objective for the local exploitation, that can guarantee the convergence with an appropriate local exploration acquisition function.
(we list GIBO algorithm in Appendix for reference). In our approach, we adopt the same local exploration acquisition function to sample points as in GIBO (to keep that constant) (line 4 in Algorithm [ and only set the objective of local exploitation acquisition function that drives the step move to minimizing the UCB, instead
MinUCB can be viewed as modified version of GIBO 22 36
of gradient descent step X X 7/ V μDD (xt), as shown in line 8 in Algorithm [ We first introduce some notations here for better illustration of our algorithm. We define kp_z (X,, X:)
kp (x,, xx) - kD
( (x, (k (Z. Z) + - ko (Z. Xx), which is exactly the posterior variance of f(x,) conditioned on the dataset DD and a new input Z. Because the estimation of variance does not require y, we have omitted the symbol here. The local exploration acquisition function for sampling
is defined on this posterior variance:
O'race (x,, Z) = tr UzV x()
(5)
which is the trace of the posterior covariance matrix of the (xx) conditioned on the dataset and input. This trace quantifies the uncertainty of gradient V fxx). With a large batch size ((2) minimizing this trace will result in a lower uncertainty on the estimation of gradient. Although UCB doesn't involve gradient descent, we keep this step constant and argue that the candidates selected through this local exploration acquisition function will still efficiently decrease the uncertainty on this local area, which will benefit the local exploitation move when minimizing the UCB.
In the local exploitation part, the 3, controls the search area for each step. The larger the 3,, the closer X++1 will be the existing data point. Minimizing the UCB can bring performance improvements, and we show later in Section [ (Theorem 2 that MinUCB will have similar convergence rate as
GIBO with carefully selection on coefficients 3 and batch size b,") b!2)) The results of MinUCB can provide inspiration on the design for more efficient local Bayesian optimization algorithm, as shown in Section 7
points, especially in the high dimensional case.
6 Convergence Analysis of MinUCB
In this section, we establish a convergence analysis of MinUCB to demonstrate the effectiveness of using minimizing UCB as the objective of local exploitation. We prove that MinUCB has polynomial convergence rate, and this rate also exhibits a polynomial relationship with the input dimension, indicating that MinUCB performs very well in high-dimensional case. For the whole convergence proof of MinUCB, please refer to Appendix B.1-B.4. In our convergence analysis, we set mild assumption on kernel function k:
Assumption 1.
The kernel k((,-) is stationary, four times continuously differentiable, caattinuosyydifffeenntttio
strictly positive
definite, and bounded: maxxex k k(xx x) $
Many common kernels such as RBF kernel and Matérn kernel with y > 2 will satisfy this assumption. We also need the definition domain of Gaussian process is bounded:
Assumption 2. The Gaussian process [(x) is defined on bounded closed set X, i.e. there exist constant r > 0 that VX1, X2 E X. ||x] - x2lla 1 r.
The next we borrow the definition of Error function from Wu et al. 33 The Error function measures the maximum reduction of uncertainty about the gradient estimation x when there are data points Z without any extra dataset:

---

Definition 2. (Error function) Given input dimensionality d, kernel l and noise standard deviation we define the following error function:
Ba,k, (6)
inf tr tr(Vk(0,0)V Vk ZER
(6)
Based on the above assumptions, we develop the convergence theory for MinUCB:
Theorem 1. Suppose f is sampled from a zero mean Gaussian process with a continuously differ- entiable convariance function k(,,-), ), and k((;,) satisfies Assumption 1. Then after t iterations of MinUCB algorithm, with the batch size b and b,²) satisfies that
T
min |V((x)l22 v 1/251ST
8
+
8
Σ
Rn Fa (b,2)) 0 0 log
1 8)
T
(1)
T
1=1
==1
+
V/r
Br/21
2
π
E (7/)2)
where Be and mn are both decreasing sequence. They satisfies B, (3,)) and J. n
O(dy log 12d2
d ), and Be 22 x212
Proof Outline Theorem
From the definition of Xe+1.we can obtain fx++11 S. min JtD, (x) + 3:OD, (x) S UD, (fx+1) + BTOD, (x++1), where & is a pseudo gradient descent step. xx+1 X,
Ti V WDD (x.). The probability of the above inequality being true can be controlled by $t.
We try to build the relationship of jDD (x,) + B,OD, (xx) and jrD, (X++1) + BL (X+11).
We apply the local properties the mean function μpD (x) and standard deviation function oD, (x) (proved in Appendix B.1 and B.2), which is:
μDD (x++1) SHD. (x,) 7/ VPD, (x,11 + T VDD
2 oD. ($t+1) SetOD, (xx) + error (/D,, (x:)l1))
We bring the above relationship into the initial inequality, and use the triangle inequality to establish the relationship between VHD, (xx) and V fx.). After a few more simple steps of derivation, the final result can be obtained.
can be seen that the convergence of gradient [Vx(x;) ll2 heavily depend on the batch size b. and 6(2) The large batch size will accelerate the convergence, with the additional cost of sampling. The upper bound of E. (b) and its theoretical property can be referred in Wu et (36), and also list them at Appendix B.3, lemma 6-9. Thus if we combine the above result, the convergence rate of MinUCB is obtained:
Theorem 2. Suppose f is sampled from zero mean Gaussian process with continuously differen- tiable convariance function k(.,,), ) then if the kernel RBF kernel or Matérn kernel with ?y = 2.5,
and satisfy 3, = /2 log
z212 o batch size
log2 t
dd logg dt
(1)
t
and
(2)
12
dil
Then MinUCB will achieve the convergence rate of
Oloa 1 log
2
O(ad))
min T/2SiST
O log
2T
O log 4x)
0 log
d2 O(odān log du))
where n is the number of samples. Our method achieves similar results to Wu al. (36. except for some logarithmic term and the order of d. The dimension d in boundary is larger than that in
7

---

Algorithm 2: LA-MinUCB: Look Ahead Bayesian Optimization through Minimizing UCB
Input: A black-box function f.
2 for f = 1,2, T..,, do
3 X = arg minz Eyz minx UCB(x, D yz) where Z E Rbxxd #Local exploration
evaluate the black-box function on X. obtaining noisy measurements
D. = Di-1 U yX
X1+1 arg minx MDD (x) + (x)
#Local exploitation via minimizing UCB
7
3t-1 = fxx++1) +
D. = D, (x++1, M+41)
9 end
10 X7 arg minx uD, (x) + 3TOD,
Wu's work, which is because we also take the upper bound the L-smooth coefficient Gaussian process into consideration, while this upper bound also increases at the polynomial rate with the data dimension d, as seen in Theorem Bjin Appendix B. B. According to Theorem 2
we need to iteratively to guarantee the convergence of MinUCB. This phenomenon can explained that, when the algorithm approaches the local optima, the area around local optima will usually be flatter than other areas (as the gradient is near O). The algorithm needs more detailed local exploration to ensure better descent. The polynomial convergence rate demonstrates that our local exploitation strategy, minimizing UCB, is accurate and powerful. It can ensure the accuracy of the local search and fully utilize the information of Gaussian processes.
increase the UCB coefficient 3 and batch size " b(²)
Look Ahead Bayesian Optimization through Minimizing UCB
Our proposed MinUCB enjoy good theoretical properties and provide an alternative idea of minimiz- ing the UCB good way to progress the local search under Gaussian process surrogate. However, there are still improvements that can be made to the local exploration in MinUCB, Specifically, UCB itself does not require any gradient information, and the local exploration in MinUCB still focuses on learning the information a single current point. This under utilizes the Gaussian process surrogate, and the potential information in the local region. Based on the above, we focus here on selecting better local exploration acquisition function for minimizing UCB, which can help to accelerate the local Bayesian optimization.
In this section we apply look ahead strategy. The motivation here is to obtain desired candidates to improve the UCB bound, and help the next local exploitation achieve better results under an expec- tation view. With this idea we propose our second algorithm, Look Ahead Bayesian Optimization through Minimizing UCB (LA-MinUCB) (Algorithm 2
Suppose have the input Z and their labels yz (this part is unknown before sampled), we define Dz as Dz= = [(2,, v.). i = 1,.... b as the dataset formed through Z and yz- Then we define
UCB(x, D,-1, yz) = pD,_, (x) + BLOD, (x)
This is the upper confidence bound when we already have the dataset D,-1 U Dz, and we want to find the input Z to minimize the minimum point of UCB: miny UCB(x. D,-1. Z. yz). However, as the label yz is unknown, we can only choose to optimize it through its expectation. We adopt this look ahead predictive as the local exploration acquisition function in LA-MinUCB:
X
arg min Eyz min UCB(x, (,,(x,DD_11 D, Z,yz)
Z
Although the local exploration in LA-MinUCB does not need to be specified around certain point, is still necessary to have an local exploitation step. Local exploitation step may find point with current best reward, and will provide better foundation for subsequent local exploration.
LA-MinUCB a similar structure with traditional Knowledge Gradient except for the standard derivation term aD, (x). This standard derivation term behaved as regularization term, that force sampled points be not too far away from current area. This is because only when the selected points closer to the current optimal point, are they more likely learn which nearby area may

---

25D ocjective
50D objective
100D objective
2.5
rewrrrd
2.0
1.5
2.3
1.-
MiuCa
H93
GI6O
0.-
BJRDO
Figure 2: Progressive optimized reward on high- sigh-dimensional synthetic functions. LA-MinUCB demonstrates fast and accurate convergence compared to other methods.
4D CariPule
160 Swimme
33D Huppaer
540
350
Current bedt reward
300
500
802
400
302
300
150
Lovimiin
200
100
MBrUCB
100
1010
100
0350
Tarii
0-
600
1500
2000
2500
3500
Figure 3: Progressive optimized reward on the MuJuCo tasks. LA-MinUCB has consistently optimal performance.
contain smaller values, thereby achieving a greater decrease in the next exploitation step. This extra standard derivation term restrict the over-exploration of the original Knowledge Gradient to help it perform better exploitation. Benefiting from this property, LA-MinUCB is able to focus on doing local search and quickly find local optima points.
The significant advantage of using LA-MinUCB that its strategy has good theoretical properties:
Theorem 3. If only one iteration left and we can observe the function value through sampling, then the local exploration in LA-MinUCB is Bayes-optimal among all feasible policies.
The proof of this theorem listed in Appendix B.5. This indicates that LA-MinUCB is a greedy strategy, where in each step it use the optimal acquisition function to enhance the exploitation. From this perspective, LA-MinUCB is likely to be superior to MinUCB because LA-MinnCB is better prepared for the next step of exploitation. This is also reflected in our experiments results, which shows that LA-MinUCB have very competitive performance in numerical experiments and practical applications. Meanwhile, this also illustrates that good local Bayesian optimization algorithms can be constructed without the need for approximate gradients.
Experiments
In this section apply varies experimental settings assess the efficacy of our proposed two algorithms, Min-UCB and LA-MinUCB, relative to two established methodologies. These include two approximated gradient methods, (1) GIBO [22] and (2)MPD (23), which has shown strong performance in local Bayesian optimization methods, and one trust region based method (3) TurBO 77. Our code is based on Nguyen al. (23), where they provide the program of GIBO, MPD, and various of objective functions. Our experimental settings on synthetic (Sect. 4.1) and reinforcement learning (Sect. 4.2) objectives are same as their papers. Each algorithm executed a total of ten times for every objective function that we examine, initiating from an identical set of starting points sampled across the bounded domain via Sobol sequence. objective) and 3 (reinforcement learning objective). The figures shows the mean of current best reward on the number of queries with an error bar (defined through the standard derivation). Our experimental framework was executed on workstation of 20 Intel Xcon CPU cores, with a 32GB
illustrate the results Fig. (2) (synthetic

---

of memory. The codes can be viewed on hitps://gihub..cmmccmmie I/Mimmizzing- UCB] For more computational details. please refer Appendix A For more experimental results and ablation study, please refer to Appendix
8.1 Synthetic Objectives
In our first experiments, we focused on optimizing synthetic objective functions within the d- dimensional unit hypercube [o, 1] These functions were generated by sampling from a Gaussian Process (GP) with a Radial Basis Function (RBF) kemel. This Synthetic objective is first mentioned in Müller et al. [22], and for more comprehensive understanding of this experimental setup, please refer to $4.1 in their work. Each experiment was allocated a budget of 500 function evaluations. under the dimension {25, 50, 100) separately. The error bar here is defined as plus or minus 0.2 standard derivation for better illustration, as the functions sampled by Gaussian processes have significant differences. Fig. ② illustrates that our proposed LA-MinUCB and Min-UCB achieve highly competitive performance in both efficiency and accuracy, where LA-MinUCB is slightly better. The MPD ascent very rapidly at the beginning, but soon shows instability. Although each ascent applies the direction of maximum probability, considers multiple ascent in one iteration in the algorithm. This strategy may instead lead to small probability that the final point is greater than the original point, causing the algorithm to fall into suboptimal solutions. GIBO can achieve very close the real local optimum, but its strategy is too conservative, resulting in slow convergence. Similarly, when the dimensionality is particularly high, TurBO performs relatively poorly and does not have much competitiveness.
8.2 Reinforcement Learning Objective
In this experiment, we turned to reinforcement learning, specifically MuloCo-based locomotion tasks [30]. In these tasks, we try to learn linear policy that maps states into actions in order to maximize the rewards given by the learning environment. We adopt the experiments similar with Nguyen al. (23) including three environments: CartPole-vl with 4 parameters, Swimmer-vl I with 16 parameters, and Hopper-y1 with 33 parameters. The only difference is that we apply the 1opper-v1 without the state normalization, in Nguyen's 's work they show that this state normalization will cause a significant unstable change in the function value. The error bar here is defined as plus minus standard derivation. Our results, depicted in Fig. (3), show that LA-MinUCB has an excellent performance in all three cases. LA-MinUCB exhibits faster convergence speed and may achieve better local optima than other methods. Although MinUCB has also shown slightly better performance than GIBO, it is still not that efficient as LA- LA-MiBUCB. This reflects the powerful performance of LA-MinUCB real applications, and also indicates that efficient local Bayesian optimization algorithm can be designed without the estimation of gradient information.
9 Conclusion
In this paper we find the connection between gradient descent and minimizing the UCB, demon- strating that minimizing UCB is an efficient local exploitation strategy with the Gaussian Processes surrogate. We introduce MinUCB, an algorithm applying minimizing the UCB as the objective of local exploitation, that will converges to local optima within polynomial rate. By enhancing the local exploration acquisition function of MinUCB, we have developed a more advanced local Bayesian optimization algorithm, LA-MinUCB We have tested our algorithm on various synthetic and reinforcement learning objectives, and the results have confirmed the efficacy of our approaches.
In this article, we have not provided the convergence proof of the LA-MinUCB algorithm. One consideration is whether LA-MinUCB have better theoretical convergence rate compared to other methods, such as GIBO? Additionally, are there any other better local exploitation strategy in local Bayesian optimization? These will become interesting research directions the future.
10

---

Acknowledgments and Disclosure of Funding
Zheyi Fan and Qingpei Hu's work are partly supported by National Key Research and Development
Program of China (2021 YRA 1000300 and 2021 YFA YFA10000000 1000301)
Szu Hui Ng's work is supported in part by the Ministry of Education, Singapore (grant: R-266-000-
149-114).
References
[1] Riad Akrour, Dmitry Sorokin, Jan Peters, and Gerhard Neumann. Local bayesian optimization of motor skills. In International Conference on Machine Learning, pages 41-50. PMLR, 2017.
[2] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems, 33:21524-215386 2020.
[3] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
[4] Mickael Binois and Nathan Wycoff. A survey on high-dimensional gaussian process modeling with application bayesian optimization. ACM Transactions Evolutionary Learning and Optimization, 2(2):1-26, 2022.
[5] Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional gaussian process bandits. Advances in neural information processing systems, 26, 2013.
[6] David Eriksson and Martin Jankowiak. High-dimensional bayesian optimization with sparse axis-aligned subspaces. In Uncertainty in Artificial Intelligence, pages 493-503. PMLR, 2021.
[7] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
[8] Peter Frazier. A tutorial bayesian optimization. arXiv preprint arXiv:1807.02811 2018.
[9] Jacob Gardner, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. Discovering and exploiting additive structure for bayesian optimization. In Artificial Intelligence and Statistics, pages 1311-1319, PMLR, 2017.
[10] Jacob R Gardner, Matt Kusner, Zhixiang Eddie Xu, Kilian Weinberger, and John Cun- ningham. Bayesian optimization with inequality constraints. In ICML, volume 2014, pages 937- 945, 2014.
[11) Michael A Gelbart, Jasper Snoek, and Ryan P Adams. Bayesian optimization with unknown constraints. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, pages 250-259, 2014.
[12] Jeff Guo, Bojana Ranković, and Philippe Schwaller. Bayesian optimization for chemical reactions. Chimia, 77(1/2)31-388 2023.
[13] Eric Han, Ishank Arora, and Jonathan Scarlett. High-dimensional bayesian optimization via tree- structured additive models. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pages 7630-7638, 2021.
[14] Johannes Kirschner, Mojmir Mutny, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adaptive and safe bayesian optimization in high dimensions via -ie-dimensional subspaces. In International Conference on Machine Learning. pages 3429-3438. PMLR, 2019.
[15] Johannes Kirschner, Mojmir Mutný, Andreas Krause, Jaime Coello de Portugal, Nicole Hiller, and Jochem Snuverink. Tuning particle accelerators with safety constraints using bayesian optimization. Physical Review Accelerators and Beams. 2566))062202,2223 2022.

---

[16] Rémi Lam, Matthias Poloczek, Peter Frazier, and Karen E Willcox. Advances in bayesian optimization with applications in aerospace engineering. In 2018 AIAA Den-Deterministic Approaches Conference, page 1656, 2018.
[17] Armin Lederer, Jonas Umlauft, and Sandra Hirche. Uniform error bounds for gaussian process regression with application safe control. Advances in Neural Information Processing Systems, 32, 2019.
[18) Ben Letham, Roberto Calandra, Akshara Rai, and Eytan Bakshy. Re-examining linear embed- dings for high-dimensional bayesian optimization. Advances in neural information processing systems, 33:1546-1555 1558, 2020.
[19] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. Advances in neural information processing systems, 31, 2018.
[20] Natalie Maus, Haydn Jones, Juston Moore, Matt J Kusner, John Bradshaw, and Jacob Gardner. Local latent space bayesian optimization over structured inputs. Advances in neural information processing systems, 15:344005-34518 2022.
[21] Riccardo Moriconi. Mare Peter Deisenroth, and KS Sesh Kumar. High-dimensional bayesian optimization using low-dimensional feature spaces. Machine Learning, 109: 199:1995-994, 2020.
[22] Sarah Müller, Alexander von Rohr, and Sebastian Trimpe. Local policy search with bayesian optimization. Advances in Neural Information Processing Systems, 34:20708-20722) 2021.
[23] 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-11220 2022.
[24] Beth A Reid, Jill Percival, Daniel J Eisenstein, Licia Verde, David N Spergel, Ramin A Skibba, Neta Bahcall, Tamas Budavari, Joshua A Frieman, Masataka Fukugita, et al. Cosmological constraints from the clustering of the sloan digital sky survey dr7 luminous red galaxies. Monthly Notices of the Royal Astronomical Society, 404(())60-85,, 2010.
[25] Shubhanshu Shekhar and Tara Javidi. Significance of gradient information in bayesian opti- mization. In International Conference on Artificial Intelligence and Statistics, pages 2836-2844. PMLR, 2021.
[26] Yu Shen, Yang Li, Jian Zheng, Wentao Zhang, Peng Yao, Jixiang Li. Sen Yang, Ji Liu, and Bin Cui. Proxybo: Accelerating neural architecture search via bayesian optimization with zero-cost proxies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9792-9801, 2023.
[27] Wei Shyy. A study of finite difference approximations to steady-state, convection-dominate flow problems. Journal of Computational Physics, 57(3):415 4-8,, 1985.
[28] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
[29] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning. pages 1015-1022. Omnipress, 2010.
[30] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ international conference on intelligent robots and systems, pages 5026-5033. IEEE, 2012.
[31] Matteo Turchetta, Andreas Krause, and Sebastian Trimpe. Robust model-free reinforcement learning with multi-objective bayesian optimization. In 2020 IEEE international conference on robotics and automation (ICRA), pages 10702 10708. IEEE, 2020.
[32] Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A Osborne. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. In International Conference on Machine Learning, pages 10663-10674 PMLR, 2021.
12

---

[33] Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched scale bayesian optimization oig-dimensiioal spaces. In International Conference on Artificial Intelligence and Statistics, pages 745-754. PMLR, 2018.
[34] Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
[35] Jian Wu, Matthias Poloczek, Andrew G Wilson, and Peter Frazier. Bayesian optimization with gradients. Advances in neural information processing systems, 30, 2017.
[36] Kaiwen Wu, Kyurae Kim, Roman Garnett, and Jacob Gardner. The behavior and convergence of local bayesian optimization. Advances Neural Information Processing Systems, 36, 2024.
[37] Juliusz Krzysztof Ziomek and Haitham Bou Ammar. Are random decompositions all we need in high dimensional bayesian optimisation? In International Conference on Machine Learning, pages 43347-43366 PMLR, 2023.
13

---

Algorithm 3: GIBO
Input: A black-box function f
2 for f = 1,2,.... T..,To do
3
X = arg minz attace (x+, Z) where Z E Rboxd
#Local exploration (sampling)
evaluate the black-box function on X, obtaining noisy measurements
5
Dr = 1 1 U y)
X(+1 X; TJ HDD (x+)
#Local exploitation (step move)
end
A
Additional details of the algorithms
In this section we will provide additional details about proposed algorithms. First list the GIBO algorithm in the version of Wu et al. al.[36), as shown in Algorithm 3 MinUCB adopt the same local exploration acquisition function to sample points as in GIBO, and change the objective of local exploitation acquisition function into minimizing the UCB, instead of gradient descent step.
As for the computational problem of LA-MinUCB, the optimization for the local exploration acquisi- tion function is quite hard, as involves a nested optimization problem. To handle this task we use the idea of one-shot optimization in BoTorch (2). that transform the original problem into deterministic optimization problem with fixed sampling. This method first proposed to solve the optimization of Knowledge Gradient. However, considering that method is very similar Knowledge Gradient, their optimization method is also applicable to our problem. For more information about this one-shot optimization method, please refer the Section 4.2 in Balandat al. [2]
In our numerical experiment, which has been shown Section S we apply the same experimental settings with Müller et al. [2] and Nguyen et al. 23 The coefficients in GIBO and MPD are chosen as the optimal one, which are reported in their experiments or code. As for our MinUCB and
LA-MinUCB, we use fixed batch size in each experiment, i.e. ((1)_ (2) and by are unchanged in each experiment. The UCB coefficient 3 in MinUCB and LA-MinUCB fixed as 3, which has been shown to be able to balance the convergence speed and accuracy of the algorithm.
B Theoretical analysis for MinUCB and LA-MinUCB
In this section, we will present the theoretical results of the algorithms introduced the article. Sections B. B-B.4.4 provide the theoretical convergence proof for MinUCB, while B.5 discusses the theoretical properties of LA-MinUCB. Sections B. 1-B.3 serve as the preliminary theory for proving the convergence of MinUCB, mainly presenting the local smoothness properties of Gaussian processes, mean functions, and standard deviation functions, as well as the theoretical properties of approximate gradients. B.4 combines the above theories, connecting the minimization of UCB with gradient descent, and provides the convergence theorem for MinUCB. B.5 demonstrates that LA LA-MinUCB has one-step Bayesian optimality, illustrating the superiority of the algorithm.
B.1 The function smoothness in Gaussian Process and mean function
In this subsection we mainly build the theory for the smoothness of Gaussian process and mean function. Our convergence proof heavily depend on the smoothness analysis the Gaussian process, mean function and standard derivation function. These proof rely on the upper bound of Gaussian processes proposed by Lederer et [17, which related the Lipshitz continues coefficient on kernel function:
Lemma 1 (Lederer et al. 17 Consider a zero mean Gaussian process with a continuously dif- ferentiable convariance function k(;,"), and let La denote its Lipschitz constant the set X. with x 1|.. Then, with probability of at least 5, the supremum of sample function fxx of this Gaussian process is bounded by:
maximun extension max ex ||x-xxxi
(
sup fxx < xEX
2 2og
max XEX
k(x,x) + 12v max
max x), VrLL X
14

---

We use this lemma to build the upper bound on the L-smoothness coefficient on the Gaussian process and mean function:
Theorem 3 (Smoothness of Gaussian process), Consider a zero mean Gaussian process with continuousty differentiable convariance function k(,,-), and k(.,-) satisfies Assumption 1. We define the second-order partial derivative kaka (.,.) as
0+
k (x,xx) dr, x(x,x))
Let Di denote the Lipschitz constants of the second-order partial derivative 1: (1, the set X with maximum extension max ex ||x probability of at least 5, and B satisfies:
x 1l2. Then, a sample function f()) is B-smooth with
B
Σ
U3
where
2d2
Uig = V 2 log
max XEX
hB (x, x) + 12V Gd max
max xEX
ho (x, x), V /
8
Proof. We set the Hessian matrix of f(x) as
O5 021 f(x)
8²
Oz Bng f(x)
@
H(x)
[xx
Trgg (x)
H2
According to the equivalence of matrix norms, we have
[x()]] & [x(])]
Thus
8 < H I sup [ sup xEX
dx 0r, f(x))2
(8)
XEX
xEX
Then through applying Lemma 2, we have the following equation holds with probability at least 8/d2
sup xeX
0²
f(x) 1
2log
2d
(x. x)x 6d max
V (x, VrL
dis
dr,dx,
xEX
Then if we combine the Eq. (8) and Eq. 99. we will get the result of Theorem 1.
Theorem 4. supxex (xx) < L, then with the probability of at least for a dataset D, we
have
(1)
max xEX
[ND(X)] < v 2 log
max XEX
1( x x) L
Proof. For a dataset D, we have the mean function (x((x) and variance function (x).
x = arg max [x](x]]
xEX
[ND(x*) ) < [f(xx)) + (ND(x*) f(x*)]
S sup [xxx) (p -xx)))
(10)
xEX
15

---

For random variable ~ (0, 1), we have P([r) > c) S expl )
Thus with the probability of
least 1 2 have
(xoxx")-(xx" = log oo((x") - 2og max / /k(x,x) x)
(11)
8 xex
Combine the result of Eq least 1 8:
10 and Eq 11
have the following results with the probability of
max {
max xeX
|DD(
S V
2
xxx,))++++ +L
xEX
Theorem 5 (Smoothness of mean function). Consider a zero mean Gaussian process with a con- tinuously difserentiable convariance function k(;,-). and k(;s)) satisfies Assumption 1. Let Bug denote the Lipschitz constants of the second-order partial derivative kD (:,") on the set X. with maximum extension maxxxx Ex ||x x 112. Then, given dataset D, the mean function px(
is 3y-smooth with probability of at least 5, and B satisfies:
B S
1.J
where
d2
ViJ = V
2
max xEX
kas (x, x) + Lis
8
and Taj s11Pxex 8m, [(x)
8²
Proof. We set the Hessian matrix of (x( as
Bey UDD (DD()) (x)
on chr uD (x)
8a
Hx(x)=
8²
uDD xx)
Tosthed uD (x()))
0²
According to the equivalence of matrix norms, we have
[x]x s [|Hx(x)]FF
Thus we can apply Theorem 3 and get the following result probability of at least 5:
0 Dx. UD (x))2
8
8, < sup
(x)]l
sup [[ xEX
Σ
max(
dx,ūr, HD (x)))
xex
xex
j.j
(12)
where
82
max xeX
Hp (x)
5
22
max xex
hoby (x,x) + Lis
Oz,0x,
Here we need an additional Theorem give the upper bound on the L-smoothness coefficient on the posterior of f()), which is aim to bound the probability under specific L-smoothness coefficient.
16

---

Lemma 2. Consider zero mean Gaussian process with continuously differentiable convariance function k(;,), and let L denote its Lipschitz constant on the set X with maximum extension r = max ex |x - x l|2. Then, given a dataset D, we define the posterior of f(-) over dataset D as fo(.). With probability of at least 1 - 6, the supremum of a sample function fo(x) of this Gaussian process is bounded by:
(7)
sup (D(x)= 2
V
max 1( x) + 12 max max V /xxx x), VILk XEX
xEX
XEX
Proof. Note that for the covariance pseudo-metric d1(x,, = vk(x,z) k(x', 2k(xxx we have
kD (x, x) + k x') 2xx((x,))) =k(x, x) + 1(xx x') 21((x,
(k(x, X k(x (k()) - (,) -k(x', XD)))
<k(x,x) + ((x', x') 2xx
Then this Lemma can be proved in same way with Lemma B.1 in Lederer et al.
Theorem 6 (Smoothness of the posterior Gaussian process), Consider a zero mean Gaussian process with continuously differentiable convariance function k(..)). and k(;,-) satisfies Assumption 1. Let Los denote the Lipschitz constants of the second-order partial derivative k.ss (-.-) on the set X with maximum extension r = maxx,x'xx ||x - x 1|2- Then, sample function fD(.) is 3D-smooth with probability of at least 1 5, and B satisfies:
BD 1
02
i.j
where
4d
max V 10 (x, (x,x), x), VeLger XEX
Ü.j Lig + 2 2og
1- (x,, 12v 6d max
XEX
and Lij supxex
Ch, fxx)
8²
Proof. We set the Hessian matrix of fo(x) as
Oa org fx(x
Ø²
2² Ony Oer fx(x)
Hx(x)= =
Taadrr (x(x)
Sozdzs [x(x)
8a
J2 dx,0n, [x(x))2 S
Σ sup( 82
OD S sup [up]|H[(x)]l> sup [|)[()]l===== sup
xex dx,Ox, |D(x))²
xex
xex
xEX
f
(13)
The posterior fo(-) can be divided into two parts:
82
82
82
sup xEX
dr,0n [x()
S sup xeX
Fr,On, (x)
+ sup xex
Ox,0x, lx())
dx,ūtr, [D(
(14)
where
12 dw,du (x) 2.i (x,x'), According to Lemma we have the following result with probability at least 24
Dz, uD (x) is a zero mean Gaussian process with covariance function
82 òr,dx, fo(x) Oz MD(x))
8²
sup xeX
(15)
1dd
v 2log
max xex
(x, + 12v 6d max
max xEX
v
has (x,x),
VrL
17

---

Through the result of Lemma
with the probability of at least
2d
8²
2d
max
up
(x)
$
log
max x
h (x, x) + Lij
(16)
XEX
0x,0z 13
Combine the result of Eq
Eq
Eq
1S
and Eq
(16). this Theorem is proved.
B.2 Local smoothness in standard derivation function
In this subsection we attempt to build the smoothness theorem for standard derivation function (x)). However, (x) is not L-smoothness under some common kernels such as Gaussian kernel or Matérn kernel with ? = 2.5. However, we can proof that oD (x) may achieve a similar result with some small error term.
Here we define an event UL (fflf(() is L-smooth), and (x(x V |D(x)]|D; f(.) E UL) Lemma 3. For any X and datasel D, we have
(d(x|L) (x( P(U,(D)
max xxx,x) xER
Proof. According to the definition of (x()), we have
P(U: E(I(()) (ox))>)) EU) = - -ND(x)((D) oD(x)
Thus
oD(x|L) < 1
P(UL(D) xx(x
=od(x) + P(U (x)
Soo(x) + PD) 1) max V x(x,x) xER
Lemma 4. If P(ULID) D that satisfies
2, there exist constants 6₁ > 1 and 02 > independent of x and dataset
oD(x) S
Proof. According to the Markov inequality, we have
P(]((x) [x) > aD,, Et) -(
2 (x)
π a
For any event and B, we have P(AпB) P(A) - P(ANB)) 2
Thus we have
P(If(x) - -xxx)) a/. UL) = P(I((x) MD (x) > a, f() E (
P(UL(D)
P(I((x) MD( > aDD) - P(U)(D)
P(Un(D)
we set a = (x),,, we will have the following inequality
(x( 2 a
π
P(I((x) (x(x)) a(D, E Up)
π 21((1 - ((f()))(() ULID) op(x)
V 2
P(UL(D)
> (2 (2-))(1)) / [o((x) - 2
max P
18

---

So through the above analysis, we have
oD(x) S (c)0(( + ((U))D)
where = = x 2-2(111) (1) maxxEx / ((x.x)
1
Lemma 5. If (-)) is Ly smooth and P(ULID) > z1 then we have
3L + +34
oobxxx)))) S V
|x| x2l12v erl x Vko(x,, +
X1 102-x216
2
Proof.
π HoD(xi - [D((x|L)
UL) S =((S((x)) - -obb f() UL)
- [
+ (o(x=)IPP]) EU.)
As f(-) E Ur and (D(()) is Ln smooth.
L f(x1) s V x22 + X1 X2112
mD( ( (xI((1), + 11 ||x| x2112
3
< V +
|| x2112
2
L+3L
f(x))- - uD(xI) - fxx2) + (x(2)) << V)((2) VuD(Xe), x1 - Xx2 >
||x1 x221
2
L L+31
< [Vxx)) VpD(x))]2]1 xell2
||X] x2112
In similar way, we can prove
3L + Iep
fxx) (x1) f(x2) + (x(x)) 2 - [V - Vpo(x>)lellai - -xel22
|| x211
2
So through the above analysis, we have the following results
2 v π o oD
s E(I((x)) - mD(xI) - (xx2 + HD((x)) Ut)
3L + 3L
((IV)((2) VWD Et)) -x2l12 +
||x
X2
2
(x)) VHD(X2))12 D))
3L + 3L
|| - xx2122 +
||x] -x
P(UL(D)
2
(x2)) VIID [D)
31. 3
||x x2|12 +
[x] X2l13
P(UL(D)
2
3I. + 3 /4 ||x] x211
2 E(IVF((x)) ( - xx112 +
2
3L + 3L /
|x, xallay tr ((VKk((x,
||x]
x2
2
The second to the last line is because of Sauchy-Schwarz inequality: E(XI) E(XI 1) <
VE(X²) = EE(3).
19

---

B.3 Some properties about approximate gradient descent
In this subsection we list properties about approximate gradient descent, which is mainly from Wu et al.[36]. This part is also essential in our final convergence proof, as we will need to connect the previous approximate gradient descent method with our minimizing UCB to give the convergence speed of gradient.
We first borrow the definition of Error function from Wu's work. The Error function measures the maximum reduction uncertainty about the gradient estimation at x = 0 when there are data points Z without any extra dataset:
Definition 3. (Error function) Given input dimensionality d, kernel is and noise standard deviation o, we define the following error function:
o (b)
inf tr ZER
2)
(17)
This Error function actually bounds the variance of the estimated gradient, which can be seen in the following lemma:
Lemma 6. In the thh iterations in MinUCB, we have
tr tr(VkD, (,) S (b..k.((b,,) (b,2))
Proof. In the th step of MinUCB, the sampled candidates can be divided into two parts. One of them are sampled through local exploration acquisition function:
X = arg min Oitrace (X,, Z)
z
Suppose their corresponding label is y, and we set D2s = yx,y), then we can obtain:
tr tr(VkD, (x, V") S tr( Vr(V., (x,, )
The above inequality is mainly because the D2i is the subset of DD. Then through the same analysis with Lemma in Wu al. (36), prove that
tr ur(Vio (x, xx) x2) Ed,k.o (bb2))
which complete our proof.
To finish the convergence proof of MinUCB, need the following lemmas from Wu et al. (36], this lemmas give the upper bound of the estimation error of gradient, and the upper bound of Error function under common kernels RBF kernel and Matérn kernel with y 2.5.
Lemma 7. For any 0 S 5 < let C. = 2og
Then the inequalities
[xx) VUD. (x:) &. Cdr(V (Xt, X VT)
(18)
Lemma 8. let k(x1, X2) exp(
||x| || llz
be the RBF kernel. We have
Ed, (2md) = O(adm
Lemma 9. let k((,))) be the Matérn kernel. Then we have
(2md) O(adm=
B.4 Convergence proof of MinUCB
In this part we will show the convergence of MinUCB, which will use all the results in previous Subsections. The difficulty in proving the convergence is to build the relationship with previous approximate gradient methods and minimizing UCB. In this proof we try connect the function value on the gradient descent point and minimizing UCB point, and will need some smoothness properties on the Gaussian process, mean function and standard derivation function, which are provided in Subsection B.1 and B.2, To give the accurate convergence rate, we need the upper bound on the Error function, which is provided in Subsection B.3
We first give the basic convergence theorem on the
gradient for MinUCB:
20

---

Theorem 1. Suppose f is sampled zero mean Gaussian process with continuously differ- entiable convariance function k(;,-, and :(.,)) satisfies Assumption 1. Then after iterations of MinUCB algorithm, with the batch size (1) and b,²), it satisfies that
min T/2STST
[V S
8 T
B,o
+
8T
Σ
T
Rn Ean, (6,2) + 0 log )
V/T
T 1=1
T
+
BT/2
π
V
Ea,k, (b/722
VIT
2
where Bg and nn are both decreasing sequence. They satisfies Be (5,) and m Odd llg edd
d3) ), and Be = 2og =²4 8
Proof. According to the definition of X X arg min (x) (x),,
fxx+11 min UDD (x) + 3,0D, (x)
z
(19)
S yD, (8++1) + BLODD ($t+11
Where & is a special point & = x - 7 V up, (x.), which is a pseudo gradient descent step. We will use this & to build the connection between gradient descent and minimizing UCB. The 3 here is carefully chosen as Br 2
g²r²
guarantee
Σ P(f(x)) HD. (xi) 3,0D..,
Now we try to give the relationship between the UCB bound and Re+ Suppose the mean function MDD. (.) Ly,, smoothness (this coefficient will be given the subsequent parts), we will have
1DD. (8141) S (DD. (DD, (x,)+ < V VDD, (x1), 8e+1 > + Lue -xel2
2
(20)
Lp n/ VVD, (x:)
SpD,
2
Here we apply the results in Subsection B.2 and give the upper bound for the OD. ($++1). To simplify the symbols, we define tr( tr(Kk,, (x,, x,
n..
oD, (8+11 (8 + c2 (D;)
(x)o (x: + (x.+1 Le) (x.
PogP(UE (D))
3L, 3L ni V co (D.)
(x)00(xx(L1) + +ap " Th VHD. c1
2
3L,
3L V (x:))
(coo + e1 2 Th / (xD,
+ c11
2
2
+ cc2P(UE,ID.) + al P) 1) max v x(xxx)
xex
(21)
where the first line apply Lemma 3 The third line use Lemma 5 and the last line is achieved through L4 We now try to give the coefficient of Ly, and L., and these coefficients are all based on the smoothness coefficient of Gaussian process. First, according to Theorem 3 with the probability of at least 8.
for any i,j = 1,...,d, d, we have
8²
12d 8
Lij = sup
0x,0x f(x)
5 =/
2 2lo
max XEX
(x, (x, x)12 12v 12 6d max
max XEX
k (x, x), V LLr.
x
(22)
21

---

If we carefully choose Lyn and Le as
Ty
Σ V2.
La
Σ
oZ
where
x2t2d
Ve,5 V 2 log
1: (x, x) + Tag
XEX
d2
U1,53 Lig + 1 2 log
max / (x, 12v6d 6d max XEX
max
V 10
(x0
V rLb
xxX
According to Theorem 5
and
this guarantees that
P(WD. (-) is Lu, smooth) 2
P(UL, 2
t=1
and we also have P(UE, ID)) <
ममं.. Thus for the standard derivation term, their approximate error term is tend to be a very small value:
66
1 72
c2P(f() (D, (D.) all P()
1) max /k(x, 0
(23)
XERU
If combine Eq.
19 Eq.
20
Eq.
21 and Eq. (3)) and we also set 3, ei 3r and
Ve V x (..
obtain upper bound for f(x++1), and this upper bound is related
to the gradient:
1
Th VuD, (x, )1 + Bey nV (p,, + 3,0 (
f(x++1) S (x.) + (x),
2
t2
(x1) (x.)
1
// (xx )
"m 1IV (x.)
+ 3/ π 2
(D) 3,0
t2
Through simple analysis, have
[[V((x)) |VHD, (x: =
- - -1
(x (xx
V/. (xpp
and
IVV (x:)1l2 < VpD (x.) v/(x)) [V
Thus if we consider the Lemma 7 we can transform the previous upper bound into the following result with probability for any
f(x++1) S (x,) + (,0D, (xi)
nul ff
23,
a
2 Te Vfxx)
+ B/ V 2
33
π
Th + 3,0
t2
22

---

Based on the above result, we can further obtain the following results with probability 1 for any t>
1
+2 π (
f(x++1) - f(xx)) S MDD (x.) + (x,) f(x,)
2
+ V ạ
2 no [ 1
72
T The VV)x) +3? / 3,0
$ 23,00. (xi) 2 Mel ( 23,
Based on the above inequation, after steps in MinUCB algorithm, we can have the following result with probability of at least 1 8:
1 T
f(XT) - ((xo)
-
Σ
| -43, V T
+ Σ
3, (x1)
2
(=1
t=1
2 T + Ollog )
[=1
By organizing the above results, obtain
T
T
[
S f(xo) - f(xT)
+2 2 3,oD, (x1)
71
T
+
32
π
111 + O(log 1
2
(=1
T
2
2 11t
1
Σ
[|Vs(x))]2
-28r//
π
Vtt
<
V + 2
BioD, (xx) + 2T
Σ
Blnn + O(log /
2
t=1
t=1
2
1
Σ
Me
[[
23,11
/
< V +
B.OD,(X) + 2T
Σ
1 g) Blnen + O(log
t=T/2
Based on this inequality we can directly give the upper bound for the norm of gradient:
T
min T/2515T
[
B.
T
Tt
S
4
V
8
3,oD
+
4
Σ
nnn + 01 T
log 1
}
2
T
T
T 1=1
min T/2S15T
|
<
8
BiDD (xx)
+
8T
3acc + +0 1
log }
1
(24)
IT
T
T
n BT
2 VTT22
(25)
TT
Notice that in each step of MinUCB, do the repeated sampling at point xt, we denote DJ (()) {(x,, y!) ..., (x,, 2/. }} as this resampling set. We will have
TD. (xx) <
b (1)
23

---

Through Lemma 6 we can achieve
2a S (b;
We combine these two value into Eq. (24). which proves this theorem.
Theorem 2. Suppose f is sampled from zero mean Gaussian process with continuously differ- entiable convariance function k(r,-), then if the kernel Gaussian kernel Matérn kernel with
7 = 2.5, and satisfy 3t = / log 8
x²p²
batch size
log"t t
d dlog" dl
6(
((2)
and
dt2
MinUCB will achieve the convergence rate of
O(odåT T log
3 1
Oood))
min T/2SIST
[V <
O log
T O(adån log 4r)
0 log
Ly )) = Olodin log du
Proof. According to the proof of Theorem
we have
p2 + 1d12) = Oldylog
(26)
Through Lemma and we can bound Ea (b(2)) as Ed (b(2))
Thus if we
combline the result of Theorem and above error bounds, we will proof the results.
B.5 Theoretical property of LA-MinUCB
In this section we will provide the theoretical property for our LA-MinUCB algorithm, that LAA- MinUCB is Bayesian optimal if there only one iteration left. Our result proved in a similar way with the Proposition 2 in Wu et al. 35
Theorem 3. If only one iteration is left and we can observe the function value through sampling, then the local exploration LA-MinUCB is Bayes-optimal among all feasible policies.
Proof. Suppose that given budget of Nmax samples, i.e. may the algorithm for N iterations. Thus, letting II be the set of feasible policies ग. we can formulate our problem as follows:
inf ET REn
min HDD (x) + BNODY (x) xEX
We analyze this problem under the DP framework. We define our state space as S (PD. k.),p,, (--)) after iteration n it completely characterizes our belief on f. Under the DP framework, we will define the value function / as follows:
4 V"(() (s) = inf E²
min pDw (x) + (x) xxx
mell
for every (J,, k). The Bellman equation tells us that the value function can written recursively
(*(s) = min
Q" Z)
ZeR

---

where
(x, 2) = E [v=+ x =
and X is the new input in the n + 1sh step. At the same time, we also know that any policy x² whose
decisions satisfy
z " E arg
min (' Z)
(27)
ZER xd
is optimal. If we were to stop at iteration n + 1, then (ntl(5ntl) = minxex MD,,,1 (x)
+
Dat10D (x) and Eq. 27 reduces to
zt ((s) E arg
min E Z xd
min PD... (0 (x) + P = s, X Z xex
which is exactly the result of local exploration acquisition function of LA-MinUCB. This proves that the local exploration acquisition function in LA- is one-step Bayes-optimal.
C Additional experimental results
C.1 Experiements on other real-world objective functions and methods
We further evaluate our methods other real-world objective functions, which are the same as Nguyen et al. [23]. The initial pair of functions deals with inverse challenges typically found in physics and engineering disciplines. The first one is related to electrical engineering, where the goal is to optimize the alignment a theoretical model of an electronic circuit with actual data. This involves adjusting nine parameters, with limit of 500 evaluations for the optimization process. The second function addresses a cosmological issue 24], where the objective is to fine-tune a cosmological model or physical simulator match observational data from the cosmos. The focus is on maximizing the log likelihood of the model, which is influenced by various physical constants. We follow the setting in Eriksson al. 77, which presents harder optimization problem with 12 parameters and much larger bounds, and set the budget at 2000 evaluations. The third function concerns rover trajectory planning [33] It involves optimizing the placement of 100 points in a 2D space plot the rover's trajectory and reduce costs, creating a 200-dimensional optimization problem with budget of 1000 function evaluations. The experimental results are shown Fig 4 This experiment shows that LA-MinUCB remains the most competitive method, with its performance showing a significant improvement compared to other methods.
To demonstrate the performance difference between our method and the original UCB, we conducted simple experiment the synthetic functions introduced in Section 1. which is shown in Fig The parameters of the traditional UCB method were consistent with ours, with the UCB parameter set to 3. Under these settings, we compared the performance of these methods. The experiment showed that the performance of the traditional UCB was very limited across these three types of problems, struggling to find the maximum value of the function, and this issue became more severe as the data dimension increased. In contrast, our method exhibited good scalability with respect to dimensions, achieving favorable results across various dimensions. This indicates that through our proposed methods, we have transformed the traditional UCB concept into local optimization, achieving very good results and making a significant difference from the original UCB performance.
C.2 Ablation study
In the ablation study, we examine the impact of the core parameter /3 on MinUCB and LA-MinUCB. We consider three values for 8. which are 3, and 5. When is set to it indicates that the algorithm adopts a more aggressive strategy, allowing it to search for points with higher uncertainty during the descent step. Conversely, when 3 is set 5, the algorithm tends to be more conservative, favoring the search for points that are very likely to have function values less than the current best point. We list the experimental results on synthetic function defined in Section 8.1 under these three 3 values in Figure 7 and 8 The results show that when 3 is small, both MinUCB and LA-MinUCB are more likely to achieve better results the initial search phase. This is because a smaller beta value allows for a broader search range, increasing the chances of finding relatively good results early on. However, in the later stages of finding the optimal point, may be weaker than when 3 is larger. This is because an overly aggressive strategy can cause the algorithm to hover around the optimal
25

---

90 map ritting
120 cosmo. constant
2000 rever reojectoy
800
1000
100
80
600
-103
L-NinUG
MIBUC
-122
MFO
200
G300
200
Figure 4: Progressive objective values observed on real-world tasks. LA-MinUCB is competitive against other baselines on all tasks.
25D obyective
50D objective
100D objective
355
3.5-
MERUCS
1.0
UCS
0.5
0.5
-6.5
100
Figure 5: Progressive objective values observed on synthetic function. Our methods are much better than traditional UCB methods
Miri ITR 250 abjertion
1A Mini FR 25D alpettie
Carrent bost revard
2.3
100
300
25c
230
150 PEUCrOS
200
309
*guerios
Figure 6: Progressive objective values observed on synthetic function when D = 25.
Caroent bett reward
Cherent bett revard
300
Figure 7: Progressive objective values observed synthetic function when D 50.
26

---

MinuCB 300D objective
LA-MinUCE 100D abject
3.
3,0
B-1
2.5
p-3
Cureet best rewaid
2.5
R--
2.0
2.0
1.5
1.0
05
0.0
200 300
100
200
300
Figure 8: Progressive objective values observed on synthetic function when D = 100.
point without getting close. This can also be seen from the Theorem 2 which states that larger is a necessary factor for the algorithm to approach the extreme point. When 3 is set to 3, it represents more balanced outcome, achieving a good convergence rate while the optimal point also close to that when 8 is set to 5, making it a better choice.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, please refer our Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
Our Appendix B provide the detailed proof of our algorithms.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Please refer to experiment settings in Section The codes for the proposed algorithm and experiments will also be made publicly available upon publication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

reproducible, they Answer: [Yes]
Justification: The codes for the proposed algorithm and experiments will also be made publicly available upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.c cc/
public/guides/ htt.s//oooeaaaissoooooooooooooo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 /piiss.c/public//uiiees http:////guideee//oeeuuubtitiiii soriddeSubmsssioPoollll
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [No]
Justification: Our experiment in the article is completely consistent with Nguyen et al. 23 and specific details can be found in their article.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please refer to our experiments in Section 8.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to our experiments Section 8.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://ppe./.aaae......//p//aaaa
Answer: [Yes]
Justification:
The research conducted in the paper adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This study purely contributes to the technical vdnacementt of local Bayesian optimization algorithm and does have any societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Please refer to our experiment in Section 8.
Guidelines:
The answer NA means that the paper does existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's 's creators.
32

---

13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions NeurIPS Code of Ethics and the
and locations, and we expect authors to adhere guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "Qqcpj5nIHM", "reviewer": "Reviewer_9Krt", "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.\n\nIn 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.\n\nThe 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.", "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?\n2) Why limit the experiments to a subset of the problems in Nguyen et al.?\n3) Why choose constant batch sizes and beta when the theory predicts choices with guaranteed convergence? Why deviate from the theoretically obtained values?\n4) Why are the results on the synthetic benchmarks significantly different from those reported in Nguyen et al.?\n5) How where the batch sizes chosen?", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper presents a clear, well-motivated, and relevant contribution to the field of local BO.\n- The related work is thoroughly discussed, situating the paper's contribution within the context of existing research.\n- The theoretical analysis is interesting and significantly strengthens the algorithmic contribution. \n- The proposed algorithms improve the state-of-the art for GIBO-style algorithms.", "weaknesses": "## Main aspects\n\n**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.\n\n**Empirical evaluation**: The empirical evaluation is  limited, missing important details, and is generally not well executed.\n\n- 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.\n- 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.\n- There are important details missing:\n  1. Batch sizes\n  2. Hyperpriors and hyperparameters\n- The code is not available for review, which hinders the evaluation of the experiments at the time of review.\n- The meaning of the error bars changes between plots.\n- A sensitivity study is missing. How sensitive is the algorithm to the choices of the newly introduced hyperparmeter, namely $\\beta$ in the UCB?\n\n\n**Limitations**: The paper does not discuss the limitations of the proposed method and its evaluation.\n\n\n## Minor\n\n- In Theorem 1, $n$ is never introduced.\n- The paper often cites arXiv preprints when peer-reviewed versions of the articles are available.\n- There are some grammar and spelling mistakes/inaccuracies:\n  - \"..solve _the_ high dimensional black-box.. problem\" should be plural: \"..solve high dimensional black-box.. problems\" (there are many such problems).\n  - \"Gradient descent\" should be lower case.\n  - \"large estimate to ensure _the_ convergence\" should be: \"large estimate to ensure convergence\" (we are talking about general convergence behavior).\n- The typesetting of \"L-smooth\" is off, perhaps due to being typed in math mode.\n- Some words/abbreviations are typeset in math mode (e.g., in equation 3, \"UCB\"; in equation 5, \"trace\").\n- Equation 1 is hard to parse due to the nested inequality and scalar product symbols.\n- Figure 3: \"LA-MinUCB has consistently optimal performance.\" In what sense is the performance optimal? This claim seems premature and needs clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. The suggestions and questions are briefly responded below.\n\n**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\n\n**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.\n\n**Weakness 2 and Question 2,5**: Empirical evaluation: details, no new benchmarks, error bars, open source code\n\n**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. \n\nWe 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.\n\nThe 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.\nWe 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.\n\n**Weakness 3**: Lack of sensitivity study\n\n**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.\n\n**Weakness 4 and Question 1,4**: The difference between our experimental result and Nguyen. et al[1]\n\n**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.\n\n**Question 3**: Why choose constant batch sizes and beta\n\n**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).\n\n[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", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AaWVOoWoik", "reviewer": "Reviewer_csK6", "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.", "questions": "1. Please proofread the paper to check grammar and spelling. For example, line 151, 161.\n2. Line 171 \"more likely to be lower than\" should be \"more likely to have a smaller value than\".\n3. Line 269 \"minimize the minimum point?\"\n4. 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.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. The suggestions and questions are briefly responded below.\n\n**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.\n\n**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. \n\nWe 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.\n\n**Question 1,2,3**: grammar and spelling\n\n**Response** : Thanks for correcting the spelling and grammar errors in the paper, and we will make all revisions in future versions of the paper.\n\n**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.\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U2CzK3jpmY", "reviewer": "Reviewer_Zw3g", "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.", "questions": "Can you define what it means to be \"local\" and how the update step satisfies such a property?", "limitations": "The paper briefly discusses limitations, mainly the missing analysis of the lookahead approach.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "*Originality*: \nThe 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.\n\n*Quality*: \n* The obtained bounds are slightly worse than prior works, but on the upside do not require the knowledge of a Lipschitz bound.\n* The experiments show good performance on the synthetic benchmarks and RL tasks\n\n*Clarity*:\n* 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.\n\n*Significance*: \nLocal 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:\n\n* 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? \n* 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). \n* 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.\n* 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.\n* The experiments lack several baselines (e.g. Turbo or LineBO) \n* 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?\n* 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.\n\nMinor remarks:\n* The abstract uses acronyms that have not been introduced (BO, GIBO).\n* 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.\n* 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.\n* The type setting of equation (1) looks odd - try using `\\langle` and `\\rangle` for the inner product.\n* 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).\n* 233: gamma is not defined\n* 241: What is n ?\n* 187: \"view\" -> \"viewed\". \n\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. The suggestions and questions are briefly responded below.\n\n**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\"?\n\n**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. \n\nIn 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.\n\n**Weakness 2**: ...One can construct kernels/examples where this \"local\" property is violated...e.g. for linear kernel...\n\n**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.\n\n**Weakness 3**: How can we efficiently find the minimizer of the UCB?\n\n**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.\n\n**Weakness 4**: ...Lacking several works, e.g. the LineBO paper...lack several baselines(e.g. Turbo or LineBO)\n\n**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.\n\n**Weakness 5**: The introduction of the Lookahead strategy...not well connected to the remaining paper...\n\n**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.\n\n**Weakness 6**: In general, the paper should better highlight the technical contributions and challenges related to the main result...\n\n**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.\n\n**Weakness 7**: Minor remarks\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tSSEp8owzq", "reviewer": "Reviewer_TKiN", "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.", "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.", "limitations": "The authors explicitly state the lack of convergence guarantee for LA-MinUCB as a limitation.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n\n2. 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.\n\n3. 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].\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**: I belive Theorem 1 could use a proof sketch...\n\n**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:\n$$  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}$$\nwhere $\\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.\n\n**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.\n\n**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.\n\n**Weakness 3**: ...only cite relatively old papers ...\n\n**Response**: We apologize for not citing the latest works. Relevant content will be added in future versions of the paper.\n\n**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? ...\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their constructive comments and suggestions, which have brought great help to improve our paper. We would like to provide a clearer explanation of two aspects: the local behaviour and why our algorithms are local.

In this paper, we would like to emphasize that the term 'local' mentioned does not refer to limiting optimization within a small range or a specific interval, such as TurBO, but rather to the algorithm exhibiting local behavior. More specifically, the algorithm will only try to search points around the current dataset, without doing global exploration.

**The locality of minimizing UCB**:
Compared with minimizing LCB, minimizing the UCB is a very conservative strategy that places additional penalties on exploration. Specifically, LCB is small with small $\mu(x)$ or large $\beta\sigma(x)$, while UCB is only small when both $\mu(x)$ and $\beta\sigma(x)$ are small. If we consider a point that is far away from the current dataset. Since there has been no exploration around this point, $\beta\sigma(x)$ will be very large, which means that the minimum point of UCB will not be taken here.
So the meaning of minimizing UCB is that, it will search towards points with smaller $\mu(x)$, while $\beta\sigma(x)$ controls the search distance, forcing the search to be around the current dataset, which leads to minimizing UCB being a local strategy.

**Why MinUCB (Algorithm 1) is local?(gradient descent view)**:

Our MinUCB can be viewed as the enhanced version of gradient descent with a larger descent in each step. If we assume $x_{t}$ as the result of the $t^{th}$ local exploitation (step move, line 8 in Alg 1), then what we actually proved in Theorem 1 is 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 some error terms in the proof $e_{t}$ will decrease to 0. $\hat{x}^{t+1}$ is actually the gradient descent point starting from $x_{t}$. The above inequality shows that MinUCB also adopts a greedy strategy that it only tries to find a point that is better than previous one. This reflects the locality of MinUCB, as it only focuses on the reliable improvement in each step, instead of doing exploration to search potiential global optima like minimizing LCB. This greedy strategy also guarantees that MinUCB will converge to local optima with a polynomial speed.



**Why MinUCB (Algorithm 1) is local? (trust region view)**:

The trust region, which is defined in TurBO [1], is a hyperrectangle centered at the best solution found so far, and will shrink its size after too many consecutive “failures”, or expand it after many consecutive “successes”. The adjustment of trust region is trying to find a area, that the searching result $x$ in the area satisfies that $f(x)<f(x_{t})$ with a certain probability, where $x_{t}$ is current best point, so that the proportion of “successes” and “failures” can be controled. From this view, we can construct a variant of trust region through an upper confidence bound view:
$$  UCBTR_{x_{t}} \coloneqq \\{x|\mu(x)+\beta\sigma(x)<f(x_{t})\\}$$
This region is more conservative than the traditional trust region, as any points in this area will be lower than $f(x_{t})$ with a probability larger than $p$,  and $\beta$ controls this probabiliity $p$. Therefore, the local exploitation (step move, line 8 in Alg 1) can be viewed as searching the reliable minimum point in this trust region:
$$  \min_{x\in \mathcal{X}}\mu(x)+\beta\sigma(x)\le \mu(x_{t})+\beta\sigma(x_{t})\approx f(x_{t})$$
where the right approximation is guaranted through local exploration (sampling, line 4 in Alg 1), and this local exploration step will learn more local information around $x_{t}$, which will help to expand or shrink this area $UCBTR_{x_{t}}$. In this view MinUCB can be treated as a variant trust region method method like TurBO, where we replace the trust region with a probability subset. This probability subset is accurate and reliable, which brings additional efficiency in local searching.

**Why LA-MinUCB (Algorithm 2) is efficient?**:
Compared with MinUCB, LA-MinUCB adopts a more greedy stratgy in local exploration. In addition to learning local information, this local exploration step (line 3 in Alg 2) is aimed at obtaining better reliable minimum point in the next local exploitation through a look ahead strategy. This will possibily obtain a larger decreasement of function value than MinUCB in each step, which is also reflected in numerical experiments.

Meta-review: I am willing to recommend acceptance for this paper over the single reject. However I do think there are a few ways beyond what has already been discussed in review that the paper could be accepted:

- First, to the main criticism of the remaining negative review, why not simply run an off-the-shelf implementation of UCB, e.g. via a simple BoTorch BO loop or similar? The difference would presumably become extremely clear and immediately resolve this issue.

- Second, to reviewer 9Krt's final point, I would strongly recommend that the authors add an ablation study of \beta. This should be straightforward given the relative cheapness of these baselines.
Decision: Accept (poster)