Local Bayesian optimization via maximizing probability of descent
Authors: Quan Nguyen
Kaiwen Wu
Jacob R. Gardner
Roman Garnett
Venue: NeurIPS 2022 Accept (2022)
Keywords: local optimization
Bayesian optimization
active learning

Abstract: Local optimization presents a promising approach to expensive, high-dimensional black-box optimization by sidestepping the need to globally explore the search space. For objective functions whose gradient cannot be evaluated directly, Bayesian optimization offers one solution -- we construct a probabilistic model of the objective, design a policy to learn about the gradient at the current location, and use the resulting information to navigate the objective landscape. Previous work has realized this scheme by minimizing the variance in the estimate of the gradient, then moving in the direction of the expected gradient. In this paper, we re-examine and refine this approach. We demonstrate that, surprisingly, the expected value of the gradient is not always the direction maximizing the probability of descent, and in fact, these directions may be nearly orthogonal. This observation then inspires an elegant optimization scheme seeking to maximize the probability of descent while moving in the direction of most-probable descent. Experiments on both synthetic and real-world objectives show that our method outperforms previous realizations of this optimization scheme and is competitive against other, significantly more complicated baselines.

Local Bayesian optimization via maximizing probability of descent
Quan Nguyen"
Kaiwen Wu Jacob R. Gardner Roman Garnett
Washington University in St. Louis Universityy of Pennsylvania
{quan, ggnuan,ganettt)vuuu @wustl.
[ upenn upenn.edu edu
Abstract
Local optimization presents a promising approach to expensive, high-dimensional black-box optimization by sidestepping the need globally explore the search space. For objective functions whose gradient cannot be evaluated directly, Bayesian optimization offers one solution we construct probabilistic model of the objective, design policy to learn about the gradient at the current location, and use the resulting information to navigate the objective landscape. Previous work has realized this scheme by minimizing the variance in the estimate of the gradient, then moving in the direction of the expected gradient. In this paper, we re-examine and refine this approach. We demonstrate that, surprisingly, the expected value of the gradient is not always the direction maximizing the probability of descent, and in fact, these directions may be nearly orthogonal. This observation then inspires an elegant optimization scheme seeking to maximize the probability descent while moving in the direction of most-prooabll descent. Experiments on both synthetic and real-world objectives show that our method outperforms previous realizations of this optimization scheme and is competitive against other, significantly more complicated baselines.
Introduction
The optimization of expensive-to-ewe to-evaluate, high- diabbeiinnsionll black-box functions is ubiquitous in machine learning, science, engineering, and beyond: examples range from hyperparameter tuning [21] and policy search in reinforcement learning [3, 7], to configuring physics simulations [14]. High-dimensional global optimization faces an inherent difficulty stemming from the curse of dimensionality, as a thorough exploration of the search space becomes exponentially more expensive. It is more feasible to seek to locally optimize these high-dimensional objective functions, as we can then sidestep this inherent burden. This true even in settings where we cannot directly observe the gradient of the objective function, as may appeal to sophisticated techniques such as Bayesian optimization to nonetheless learn about the gradient of the objective through noisy observations, and then use this knowledge to navigate the high-dimensional search space locally.
realization of this scheme has been proposed by Müller al. [18], where a Gaussian process (GP) used to model the objective function, and observations are designed to alternate between minimizing the variance- and thus uncertainty of the GP's estimate of the gradient of the objective at given location, then moving in the direction of the expected gradient. Although this approach seems natural, fails to account for some nuances the distribution of the directional derivative induced by the GP. Specifically, it turns out that beliefs about the gradient with identical uncertainty may nonetheless have different probabilities descent along the expected gradient. Further and perhaps surprisingly, the expected gradient is not necessarily the direction maximizing the probability of descent in fact, these
"Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

directions can be nearly orthogonal. In other words, simply minimizing the gradient variance and mov- ing the direction of the expected gradient may lead suboptimal (local) optimization performance.
With this insight, we propose a scheme for local Bayesian optimization that alternates between identifying the direction of most probable descent, then moving in that direction. 'he result is local optimizer that is efficient by design. To this end, we derive a closed-form solution for the direction of most probable descent at given location in the input space under GP belief about the objective function. We then design a corresponding closed-form acquisition function that optimizes (an upper bound of) the one-step maximum descent probability. Taken together, these components comprise an elegant and efficient optimization scheme. We demonstrate empirically that, across many synthetic and real-world functions, our method outperforms the aforementioned prior realization of this framework and is competitive against other, significantly more complicated baselines.
2 Preliminaries
We first introduce the problem setting and the local Bayesian optimization framework. We aim to numerically solve optimization problems of the form:
given Xo E D, find x arg min f f(x;; xED(xx)
where f: D - IR is the black-box objective function wish optimize locally from a starting point Xo. and D(xo) is the local region around x inside the domain D. We model the objective function as a black box, and only assume that we may obtain potentially noisy function evaluations f(x) + e, where s ~ N (0,,, o²), at locations of our choosing. We further assume the gradient cannot be measured directly, but only estimated from such noisy evaluations of the function. Finally, we consider the case where querying the objective is relatively expensive, limiting the number of times may be evaluated. This constraint on our querying budget requires strategically selecting where to evaluate during optimization.
Bayesian optimization (BO) one potential approach this problem that offers unparalleled sample efficiency. BO constructs a probabilistic model of the objective function, typically a Gaussian process (GP) [19], and uses this model to design the next point(s) to evaluate the objective. After each observation, the GP is updated to reflect our current belief about the objective, which is then used to inform future decisions. We refer the reader to Garnett [6] for thorough treatment of GPS and Bo.
2.1 Local Bayesian optimization
In many applications, the objective function f is high- digensimensional. The curse of dimensionality poses challenge for BO, it will take exponentially more function evaluations to sufficiently cover the search space and find the global optimum. It may be more fruitful, therefore, to instead pursue local optimization, where we aim descend from the current location, by probing the objective function in nearby regions to learn about its gradient.
It turns out the BO framework is particularly amenable to this idea, as GP belief on the objective function induces a joint GP belief with its gradient [19]. which we may use to guide local optimization. In particular, given GP belief about the objective function f with once-differentiable mean function covariance function K, the joint distribution of noisy function evaluations
μ and a observations (X. y) and the gradient of at some point is
(1>%)=)) - -N
] L ([
(x) [A(x)
X(X,x)VT VK(X,X)VT
V)(x,X)
Here, when placed in front of K, the differential operator V indicates that we are taking the derivative of K with respect to its first input; when placed behind K, it indicates the derivative is with respect to its second input. Conditioned on the observations yX,y), the posterior distribution of the derivative V f(x) may be obtained as:
f(V x, x) -N Ex),
where Xx Vp(x)= +
+o') (x-(x)))))))
(I)
Σx - VK(X, - -X(xxx

---

Given the ability to reason about the objective function gradient given noisy function observations, we may realize a Bayesian local optimization scheme as follows. From a current location x, we devise a policy that first designs observations seeking relevant information about the gradient (x(x), then, once satisfied, moves within the search space to new location (that is, update x) seeking to descend on the objective. A particular realization of this local BO scheme named GTBO was investigated by Müller et al. [18]. In that study, the authors choose to learn about V fx) by minimizing the uncertainty (quantified by the trace of the posterior covariance matrix) about the gradient, followed by moving in the direction the expected gradient. This algorithm may be thought of as simulating gradient descent, as it actively builds then follows noisy estimate of the gradient. Although effective, GIBO fails to account for nuances in our belief about the objective function gradient and may behave suboptimally during optimization as result. Our work addresses this gap by exploiting the rich structure in the belief about V (x( to design an elegant and principled policy for local BO.
2.2 Related work
We re-examine and extend the work of Müller et al. [18], who proposed using local BO for the purpose of policy search in reinforcement learning (RL). As mentioned, their proposed algorithm GIBO alternates between minimizing the variance of the estimate of the gradient this is analogous to the goal of A-optimality in optimal design and moving in the direction of the expected gradient. This scheme was shown to outperform baselines such as global BO using expected improvement [11] and the evolutionary algorithm CMA-ES [8] on several problems. Prior to this work, Mania et al. [16] noted that local black-box optimization is a promising approach for RL. They developed a simple algorithm, Augmented Random Search (ARS), that estimates the gradient of the objective via finite differencing and random perturbations; this simple method was competitive in their experiments on RL tasks. GIBO and ARS are the two main baselines that we will be comparing our method against.
As mentioned, scaling to high-dimensional problems has been an enduring challenge in the BO community, and there have been many proposals to make BO "more local" as way to relieve the burden of the curse of dimensionality. In particular, several lines of research have proposed restricting the search space to only specific regions, c.g., maintaining belief about the local optimum [1], using trust regions [5, 25], and forcing queries to stay close to past observations [13]. Among these, of note is the TuRBO algorithm [5], which expands and shrinks the size of its trust regions based on the optimization history within each region, and has been shown to achieve strong performance across many tasks. We include TuRBO as another baseline in experiments.
Other approaches have considered dynamically switching from global and gradient- -baed local optimization, particularly when local region is believed to contain the global optimum. For example, McLeod et al. [17] proposed alternating between global BO and using BFGS for local optimization when there is high certainty that we close to the global optimum. Diouane et al. [4] leveraged the same scheme to identify good local regions and uses a trust region-based policy for its local phase. Wang al. [26], on the other hand, proposed learning about which subregions of the search space are more likely to contain good objective values and should be locally exploited using Monte Carlo tree search, by recursively partitioning the space based optimization performance. The authors also showed that when combined with TuRBO, their algorithm achieves sate-of-the-as performance on a wide range of tasks. Our optimization method can replace the local optimizer in these approaches, and in general can act as subroutine within a larger framework relying on local optimization.
Tackling local optimization from probabilistic angle, our method belongs to larger class of probabilistic numerical methods; see chapter 4 of Hennig et al. [10] for a thorough discussion on probabilistic numerics for local optimization. Within this line of search are other efforts at leveraging probabilistic reasoning in optimization, including a Bayesian quasi-Newton algorithm that learns from noisy observations of the gradient [9], a probabilistic interpretation of the incremental proximal methods [2]. and probabilistic line searches [15].
We note that Le Roux et al. [12] arrived at similar update expression as our algorithm (see Sect. 3), though aiming at developing fast optimization algorithms for good generalization, a different problem from BO. Moreover, their derivation is devoted to justifying the natural gradient descent. In particular, they show that the descent direction maximizing the probability of not increasing generalization error is precisely the natural gradient direction.
3

---

3 Maximizing probability of descent
What behavior is desirable for a local optimization routine that values sample efficiency? We argue that we should seek to quickly identify directions that will, with high probability, yield progress on the objective function. Pursuing this idea requires reasoning about the probability that given direction leads "downhill" from a given location. Although one might guess that the direction most likely to lead downhill is always the (negative) expected gradient, this is not necessarily the case.
Consider the directional derivative of the objective J with respect to unit vector v at point x:
Vvf(x)= v fx),
which quantifies the rate of change of / at x along the direction of v. According to our GP belief, fx()) follows multivariate normal distribution, so the directional derivative Vv](x) is then:
p( (Vv)(()) x, v= -V lx: 1x: Exx),
where Hx and Ex are the mean and covariance matrix of the normal belief about fx)), as defined in Eq. (1). This distribution allows us to reason about the probability that we descend on the objective function by moving along the direction of v from x, which is simply the probability that the directional derivative is negative. Thus, we have the following definition.
Definition 3.1 (Descent probability and most probable descent direction). Given a unit vector v, the descent probability of the direction v at the location x is given by
Pr (V) < x
<0|x.v)
VV
where & is the CDF of the standard normal distribution. If v" achieves the maximum descent probability v² E arg max, Pr (VvJ(x) < 0 x, V), then we call v² a most probable descent direction.
Note that the definition Eq. (2) is scaling invariant. Thus, the length of v* does not matter since the descent probability only depends on its direction. Moreover, we note that descent probability depends on both the expected gradient 1xx and the gradient uncertainty Ex Therefore, learning about the gradient by minimizing uncertainty via the trace of the posterior covariance matrix (which does not consider the expected gradient) and moving in the direction of the negative expected gradient (which does not consider uncertainty in the gradient) in a decoupled manner may lead to suboptimal behavior. We first present a simple example to demonstrate the nuances that are not captured by this scheme and to motivate our proposed solution.
3.1 The (negative) expected gradient does not always maximize descent probability
In Fig. 1, we show polar plots of the descent probability Pr (x) < 0 x, v) with respect to different beliefs about the gradient. The angles in the polar plots are the angles between v and the vector [1, O Critically for the discussion below, the uncertainty in the gradient, measured by the trace of the covariance matrix, is identical for all three examples.
In the first example in the left panel of Fig. 1, the negative expected gradient happens to maximize the descent probability, and moving in this direction almost certain to lead downhill. In the middle panel, the expected gradient is the same as in the left panel, but the covariance matrix has been permuted. Here, the negative expected gradient again maximizes the descent probability; however, the largest descent probability is now much lower. In fact, there is non-negligible probability that the descent direction is in the opposite direction. This because most of the uncertainty we have about the gradient concentrates on the first element of fx which determines its direction. We note that the situation in the left panel is inarguably preferable to that in the middle panel, but distinguishing these two is impossible from uncertainty in V fx() alone.
Finally, in the right panel, the direction of the expected gradient has rotated with respect to that in the first two panels. Now the (negative) expected gradient is entirely different from the most probable descent direction. Intuitively, the variance in the first coordinate is much smaller than in the second coordinate, and thus the mean in the first coordinate is more likely to have the same sign as the true gradient. However, using negative expected gradient as a descent direction entirely ignores the uncertainty estimate in the gradient. This example shows that, when we reason about the descent of a function, the mean vector Hx and the covariance matrix Ex need to be jointly considered, as the probability of descent depends on both of these quantities (Eq. (2)).

---

90
90*
90*
135
1357
45*
135
45*
0.20. 020.4..8 6.
4.60
0
6.
0.2
0.20
180
160
180
descent probability
descent probability expected gradient
225
$15
225
315
270
210
270
(1-)
0.01 0
1
0
(1
0.5
0.01
0 1
W
0
0.01
Figure 1: Polar plots descent probability (blue). The most probable descent direction is marked in red. The direction of the (negative) expected gradient is marked in black. Left: the direction v* and the negative expected gradient match exactly. Center: given the same level of uncertainty, the maximum descent probability has reduced from near certainty to only 84%. Right: the expected gradient does not maximize the descent probability. See Sect. 3.1 for discussion.
3.2 Computing the most probable descent direction
In light of the above discussion, we propose local BO algorithm centered entirely around the local descent probability. As a first step, we show the following how to compute the most probable descent direction v* arg max, Pr (x) < 0 v) at given location given data.
Theorem 3.1. Suppose that the belief about the gradient is PVV xx N Ex),
where the posterior covariance Exx is positive definite. Then, the unique (up to scaling) most probable descent direction is
arg max Pr (x) <0|x.v)= = = - Px
v
with the corresponding maximum descent probability
max Pr (x+](x) < <0 x,
(VVVIXE 1xx)
Proof. As $ (-) is monotonie, reframe the problem as
Px
arg max Pr (x. < x, v) = arg max &
arg max
ΣxV
Next, we square the objective, and the maximizer is still the same (up to sign). That is, if v is the maximizer of the squared objective:
v U v E
arg max
then either v* or -v" maximizes the descent probability. Let Ex LL the Cholesky decompo- sition of Ex. where L has be nonsingular. A change of variable v = L gives
v U v
w WT H w
Exv
w w --
which is exactly the Rayleigh quotient of L- 1-'IXXI eigenvector L-1 Mx and corresponding eigenvalue 2 Σn1 ux Thus, the maximizer w is given by
Note that this is rank-1 matrix with top
w = L- fxx
Therefore, the maximizer to Eq. (3) - Ex f1x Plug both 1 Mx and -x p back into Eq. (2). It is easy to check that the direction along -xx My is the desired maximizer. L
5

---

Theorem 3.1 states that the most probable descent direction can be computed by simply solving a linear system. Being able to compute this quantity allows us always move within the search space in the direction that most likely improves the objective value, which, as we have seen, is not necessarily the negative expected gradient. This helps us to realize the "update" portion of our local BO algorithm, where we iteratively move from the current location x in the most probable descent direction v*. That is, we repeatedly update x with x + Ov", where å is a small constant that acts as step size. This procedure is iterative in that we do not take one single step along direction, but multiple small steps, always in the most probable descent direction at the current point, throughout. (Note that we do not observe the value of the objective function at any of these steps.)
is important that we stop this iterative procedure when it becomes uncertain whether we can continue to descend. This is because we aim to move to a new location that decreases the value of the objective function, and thus should only move when descent likely. A natural approach is to again use the maximum descent probability, which we can compute using Theorem 3.1. Specifically, we stop the iterative update when the maximum descent probability falls below a prespecified threshold
p.. Once we have stopped, the final updated x is the location move to at the current iteration of the BO loop. In our experiments, we set the step size to å = 0.001 and the descent probability threshold to p.- 65%, which we find to work well empirically.
3.3 Acquisition function via look-ahead maximum descent probability
When the maximum descent probability falls below the threshold p-, we begin selecting queries to learn about the gradient in the current location so as to maximize the probability of descent. Here we derive an acquisition function seeking data that will, in expectation, best improve the highest descent probability. For maximum flexibility, we consider the batch setting where we may gather multiple measurements simultaneously, although we only use the sequential case in our experiments.
In particular, the acquisition function we would like to use for a batch of potential query points Z is:
a Z)) By z max Pr (Vv < 0 x. Z)
(4)
= By z
+ (V x
where Mxiz and Exzz are the posterior mean and covariance of the belief about V (x),, conditioned on a batch of observations at Z and a previously collected training set (X,y) which we have omitted for notational clarity. Note that the second equality is due Theorem 3.1. The above acquisition function is exactly the look-ahead maximum descent probability. Namely, oo (Z) is the expected maximum descent probability after querying Z.
Unfortunately, this expectation is challenging to compute, so we opt for another acquisition function that approximates Eq. (4) via computing the expectation of upper bound:
a (Z)= = Eyjz |
(5)
We discard the (monotonic and concave) transformation given by the normal CDF and square root, thus optimizing an upper bound by Jensen's 's inequality. The advantage this acquisition function a is that, remarkably, it has closed-form expression, as we show below.
Note that 2x = fx + Exz (yz fzz), where yz ~ Nuzz Σz). Thus, the acquisition function in Eq. (5) is an expectation of a quadratic function over a Gaussian distribution. Let
LL Σz be the Cholesky decomposition of Σz and denote A ExzL Then, the acquisition function can be written as an expectation over a standard normal Ç:
(Z) E<>N((..) [HE + AC) Exiz (H + AC)
Expanding, we have:
(#x + AC) x (Mx + AC) = Mx " + 2 X S T ATELAA
The expectation of each term can be computed closed form. The first term is constant and the second term vanishes. Finally, the third term is the expectation of a quadratic form, yielding:
ox (Z) = 1xx 1x + (ATE E E

---

Algorithm Local BO via MPD
1: inputs starting location x, number of iterations N, number of samples for learning the gradient
M. step size ó, and minimum descent probability threshold p..
2: Initialize the GP.
.N 3: for = =0,... .......N do
4: Observe the objective value: y fxx t..
5: Update the training data 'D + D {(x, v)) and retrain the GP.
6: for m ,,..., M do
learning the gradient
7:
Query point: z" = arg maxx a(z).
8:
Observe the objective value: 1/2 f(z) +
9:
Update the training data D = D U {(z, v2)} and the GP.
end for
11:
while max, Pr (v) < x, > do b move by maximizing descent probability
12:
Compute the most probable descent direction v² +- arg max, Pr (V.](x) < <0|x.v] Move in the most probable descent direction: x t x 88". end while
13:
14:
15:
end for
This compact expression gives the closed-form solution to our acquisition function. Note that solving linear system with respect to Ex|Z be performed efficiently using low-rank updates to the Cholesky decomposition of Ex. Further, we may differentiate the acquisition function easily via automatic differentiation. This allows to optimize the acquisition function trivially using any gradient-based optimizer such as L-BFGS with restart.
This completes our algorithm, local BO via most-probable descent, or MPD, which is summarized in Alg. 1. The algorithm alternates between learning about the gradient of the objective function using the acquisition function discussed above, and then iteratively moving in the most probable descent direction until further progress is unlikely, as described Sect. 3.
Experiments
We now present results from extensive experiments that evaluate our method MPD against three baselines: (I) GIBO [18], which performs local BO by minimizing the trace of the posterior covariance matrix of the gradient and uses the expected gradient the update step; (2) ARS [16], which estimates
the gradient of the objective via finite difference with random perturbations; and (3) TuRBO [5]. trust region-based Bayesian optimization method.
Müller et al. [18] provide code implementation under the MIT license for GIBO, ARS, and various test objectives. We extend this codebase implement MPD and conduct our own numerical experiments. For the synthetic (Sect. 1) and reinforcement learning (Sect. 4.2) objectives, we use the provided experimental settings. For the other objectives (Sect. 4.3), we set the number of samples learn about the gradient per iteration M = 1. For each objective function tested, we run each algorithm ten times from the same set of starting points sampled from a Sobol sequence over the box-boundeed) domain. In each of the following plots, we show the progressive mean objective values as function of the number of queries with error bars indicating (plus or minus) one standard error. Experiments were performed on small cluster built from commodity hardware comprising approximately 200 Intel Xeon CPU cores (no GPUS), with approximately 10 GB of RAM available to each core. Our implementation is available at https: //github..ttttt// www/c//m////// woom//aaweee///eeoo /ooelleen/oollllle locallbo-oala
4.1 Synthetic objectives
Our first experiments involve maximizing, over the d-dimensional unit hypercube |0, 1]d, synthetic objective functions that are generated by drawing samples from GP with an RBF kernel. We refer to $4.1 of Müller et al. [18] for more details regarding the experimental setup. While Müller et [18] tested for dimensions up to 36, we opt for much higher-dimensional objectives: d E {25, 50, 100). Each run has a budget of 500 function evaluations. We visualize the results in Fig. 2, which shows that MPD was able to optimize these functions at faster rate than the other baselines. Note that the difference performance becomes larger as the dimensionality grows, indicating that our method scales well to high dimensions.
7

---

25D objective
50D objective
100D objective
objective valui
0
GIRD
TURBO
ARS
queries
Figure 2: Progressive optimized objective value on high-dimensione synthetic functions. MPD
consistently finds higher objective values faster than other baselines.
4D CartPole
16D Swimmer
33D Hopper
3,000
reward
2,000
2000
100
R..
1.000
MPD
-180
TUKBO
ARS
0-
500
1.000
1,500
2,000
2,000
4,000
6,000
8,000
# queries
Figure 3:
Progressive objective values observed on the MuJuCo tasks. MPD competitive on CartPole and Swimmer.
4.2 MuJoCo objectives
The second set of experiments reinforcement learning MuJoCo locomotion tasks [23], where each task involves learning a linear policy that maps states to actions to maximize the reward received from the learning environment. We use the 4 parameters, Swimmer-vl with 16, and Hopper-vl with 33, to evaluate the methods and show the re- sults in Fig. 3. MPD is competitive in the first tasks but progresses slower than the other baselines on Hopper-v1. We conduct thorough investigation into the cause of MPD's failure on the Hopper func- tion and present our findings in Appx. B. In short, the experiments on Hopper-v employ state nor- malization scheme (described in $3.3 of Müller et al. [18]) that leads to systematic differences in the behavior of GIBO and MPD. By controlling for the effect of state normalization in our comparison of the two algorithms, we find that the performance of GIBO and that of MPD are statistically comparable.
three environments in Müller et al. [18], CartPole-vl with
4.3 Other objective functions
We further evaluate method other real-world objective functions. The first functions represent inverse problems from physics and engineering. The first from electrical engineering, where we seek to maximize the fit of theoretical physical model of an electronic circuit to observed data. There are nine parameters in total, and we set the budget to 500 evaluations. The second is problem from cosmology [20], where we aim configure cosmological model/physical simulator to fit data observed from the Universe. In particular, our objective is to maximize the log likelihood of the physical model parameterized by various physics-related constants that are to tuned. We follow the setting in Eriksson et al. [5], which presents a harder optimization problem with 12 parameters and much larger bounds, and set the budget at 2000 evaluations. Our third objective function uses the rover trajectory planning problem [27]. This involves tuning the locations of 100 points on a wwo-iimensional space that map the trajectory
rover to minimize cost, thus making up a 200 200-dimensional optimization problem. We set the budget to be 1000 function evaluations.

---

9D map fitting
12D cosmo. constant
200D trajectory
XFP
800
1,000
objective valuee
-50
10X80
800
600
400
200
-50
100
200
300
500
500
500
1,000
1,500
2,000
200
000
000
500
1,000
queries
Figure 4:
Progressive objective values observed on real-world tasks. MPD is competitive against other baselines on all tasks.
Table 1:
Average terminal optimized objective values and standard errors of different variants of MPD. Results that are better than those our baseline GIBO are highlighted bold.
16D Swimmer (maximization)
12D cosmo. constant (maximization)
200D rover trajectory (minimization)
(p. 65%, 8 = 10-3)
360.50 (0.61)
23.997 (0.34)
89.89 (3.88)
GTBO
348.88 (10.11)
-55.25 (3.23)
152.77 (2.26)
trace + MPD
350.58 (9.35)
-27.72 (1.16)
84.17 (2.10)
MPD expected gradient
340.12 (12.75)
-21.24 (0.04)
293.08 (8.12)
(p- =50%)
342.36 (13.10)
-24.29 (0.10)
51.48 (3.44)
MPD p. =85%)
294.67 (38.16)
-31.08 (0.86)
142.63 (5.57)
MPD(P P. -95%)
15.97 (5.46)
-3..86 (0.25)
140.44 (6.95)
MPD = =10- 14-4)
362.06 (0.63)
-24.2 (0.53)
90.99 (3.29)
MPD 110-2)
350.15 (10.92)
-25.73 (0.39)
98.72 (4.42)
We visualize optimization performance these three objective functions in Fig. 4. Our proposed pol- icy MPD is consistently competitive against both GIBO and TuRBo. Most notably, in the cosmological constant learning problem, MPD able make significant progress immediately and ultimately outperforms its closest spiritual competitor GIBO.
4.4 Ablation study
We now present results from various ablation studies to offer insight into the components of our method MPD and its hyperparamcters, specifically the descent probability threshold pa (65% as the default) and the step size 5 (0.001 as the default), as described in Sect. 3.
First, one may reasonably ask which of the two novel components of MPD either the learning phase that seeks to maximize expected posterior descent probability, or the update phase that moves in the most probable descent direction responsible for the performance improvement compared GIBO. We address this question by comparing the performance of MPD against two variants: (1) trace + MPD, which learns about the gradient by minimizing the trace of the posterior covariance matrix and moves in the most probable descent direction, and (2) MPD expected gradient, which uses our scheme for identifying the most probable descent direction, then moves in the direction of the (negative) expected gradicnt. The second section of Tab. shows the average terminal objective values of these MPD variants on three tasks that MPD outperforms GIBO: Swimmer-vl. cosmological constant learning, and rover trajectory planning. We observe that swapping out either component of MPD does not consistently improve from GIBO as much as MPD does. This indicates that the two components of MPD algorithm work in tandem and both are needed to successfully realize our local BO scheme.
In particular, the components of our method are coupled: because the expected gradient and the most probable descent direction are not the same in general, spending evaluation budget to learn about one and then using the other to move may not work well. GIBO'S 's acquisiiin function minimizes the trace of the posterior covariance and therefore aims to make the expected gradient estimate more

---

accurate, but it is unclear whether it will necessarily estimate the most probable descent direction accurately. On the other hand, our acquisition function focuses on the one-step maximum descent probability directly. GIBO's "moving" policy, moving in the direction of the (negative) expected gradient (which may not be the most probable descent direction), may not necessarily benefit from having descent direction with a high descent probability (which could point in different direction), and is therefore incompatible with our acquisition function.
We also tested MPD with three other values for the minimum descent probability threshold p. E (50%, 85%, 95%} (described Sect. 3). The first variant with p. = 50% is less conservative when moving to new location than our default policy with p. = 65,, while the other two variants are more conservative. In the third section of Tab. 1, we observe that the more conservative variants of MPD are not competitive. For example, MPD(p. = 85%) sees a drop in performance on the Swimmer task, while (p = 95%) fails to make significant progress altogether. Interestingly, 50% also does not perform as well on the two Mujoco
while the less conservative policy with tasks, we do observe an increase in performance the rover trajectory planning problem. From our experiments, we find that this rover objective function is piecewise linear within most of its domain, making finding a descent direction "easier" and allowing a lower value of p. to perform better.
The interpretation of the threshold is quite natural: it sets a threshold of the minimum probability that we would make progress by moving to new location. Intuitively, this hyperparameter trades off robustness versus optimism, with higher thresholds spending more budget before moving, but being more confident in their moves. While p. 65% performs well in our experiments, a user can set their own threshold depending on their use case. As observed with the rover trajectory planning problem, if there are structures within the objective function that make it "easy" to find descent direction, MPD may benefit from lower threshold. We might also consider dynamically setting the value of p. based on recent optimization progress - that is, we might increase p. we believe that we are approaching a local optimum and therefore that finding a promising descent direction is becoming more challenging.
Finally, the lower section of Tab. shows the performance of the variants of MPD with two additional step sizes, 10m4 and 10 10-2 We observe that MPD with 5 = 10 occasionally fails to perform better than GIBO, illustrating the potentially detrimental effect of step size that is too large. This step size parameter 6 balances between faster convergence and taking steps that are too large, analogous to gradient descent, and may even be problem dependent. would be additionally interesting to analyze whether there are good "rules of thumb" for setting 5 based on the length scale of the GP, as smoother functions can likely support larger step sizes.
5 Conclusions
We develop a principled local Bayesian optimization framework that revolves around maximization of the probability of descending on the objective function. This novel scheme is realized with (1) an update rule that iteratively moves from the current location in the direction of maximum descent probability, and (2) a mathematically elegant, computationally convenient acquisition function that aims maximize the probability of descent prior to our next move. Our extensive experiments show that our policy outperforms natural baselines on a wide range of applications.
(Local) Bayesian optimization has seen wide range of applications across science, engineering, and beyond; an extensive annotated bibliography of these applications was compiled by Garnett [6] [appendix D]. However, it is possible to leverage BO for nefarious purposes well; concrete example is constructing adversarial attacks on machine learning models [22, 24]. Further, BO requires human expertise and ethical considerations in many important applications, and fully automated optimization systems may run the risk of perpetuating misaligned goals machine learning. The authors judge the potential positive impacts society resulting from better methods for local optimization to outweigh the potential negative impacts.
Acknowledgments and Disclosure of Funding
We thank Natalie Maus for her contribution to the initial stage of this work and the anonymous reviewers for their feedback during the review stage. QN and RG were supported by the National Science Foundation (NSF) under award numbers DAC-1940224, 114-144434, and 0AC-2118204 KW and JRG were supported by NSF award number 11S-2 115-2145644.
10

---

References
[1]
Riad Akrour, Dmitry Sorokin, Jan Peters, and Gerhard Neumann, Local Bayesian Optimization of Motor Skills. Proceedings of the 34th International Conference on Machine Learning, pages 41-50, 2017.
[2] Ömer Deniz. Akyildiz, Victor Elvira, and Joaquín Míguez. The Incremental Proximal Method: A Proba- bilistic Perspective. In 2018 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP). pages 4279-4283, IEEE, 2018
[3] Roberto Calandra, André Seyfarth, Jan Peters, and Mare Peter Deisenroth. Bayesian optimization for learning gaits under uncertainty. In Annals of Mathematics and Artificial Intelligence, volume 76, pages 5-23. Springer, 2016.
[4] Youssef Diouane, Victor Picheny, Rodolphe Le Riche, and Alexandre Scotto Di Perrotolo. TREGO: Trust-Region Framework for Efficient Global Optimization. 2021. arXiv preprint arXiv:2101.06800 [LL.
[5] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turmer, and Matthias Poloezek. Scalable Global Optimization via Local Bayesian Optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
[6] Roman Garnett. Bayesian Optimization. Cambridge University Press, 2022.
[7] Aditya Gopalan and Shic Mannor, Thompson Sampling for Learning Parameterized Markov Decision Processes. In Proceedings The 28th Conference on Learning Theory, volume 40, pages 861-898. PMLR, 2015.
[8] Nikolaus Hansen. The CMA Evolution Strategy: A Comparing Review. Towards New Evolationary Computation, pages 102, 2006.
[9] Philipp Hennig. Fast Probabilistic Optimization from Noisy Gradients. In Proceedings of the 30th International Conference on Machine Learning, pages 62-70, 2013.
[10] Philipp Hennig, Michael A. Osborne, and Hans P. Kersting. Probabilistic Numerics. Cambridge University Press, 2022.
[11] Donald R Jones, Matthias Schonlau, and William Welch. Efficient Global Optimization of Expensive Black-Bor Box Functions. Journal of Global Optimization, 1 13(4):455-499 1998.
[12] Nicolas Le Roux, Pierre-Antoine Manzagol, and Yoshua Bengio. Topmoumoute online natural gradient algorithm. In Advances in Neural Information Processing Systems, volume 20, 2007.
[13] Michael Y Li and Ryan P. Adams. Explainability constraints for bayesian optimization. 6th ICML Workshop on Automated Machine Learning, 2020.
[14] Wesley Maddox, Qing Feng, and Max Balandat. Optimizing Digg--Dieeniionll Physics Simulations via Composite Bayesian Optimization. Fourth Workshop on Machine Learning and the Physical Sciences (NeurIPS 2021). 2021.
[15] Maren Mahsereci and Philipp Hennig. Prohabilistic Line Searches for Stochastic Optimization. In Advances in Neural Information Processing Systems, volume 28, 2015.
[16] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search static linear policies is competitive for reinforcement learning. In Advances in Neural Information Processing Systems, volume 31, 2018.
[17] Mark McLeod, Stephen Roberts, and Michael A Osborne. Optimization, fast and slow: Optimally switching between local and bayesian optimization. In Proceedings of the 35th International Conference on Machine Learning, pages 3443-3452, 2018
[18] Sarah Müller, Alexander von Rohr, and Sebastian Trimpe. Local policy search with bayesian optimization. In Advances in Neural Information Processing Systems, volume 34, 2021.
[19] Carl Edward Rasmussen and Christopher Williams. Gaussian Processes for Machine Learning. The MIT Press, 2006.
[20] Beth A Reid, Will J Percival, Daniel 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(1):60 85, 2010.
11

---

[21] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical Bayesian Optimiztiinn of Machine Learning Algorithmss. In Advances in Neural Information Processing Systems, volume 25, 2012.
[22] Fnu Suya, Jianfeng Chi, David Evans, and Yuan Tian. Hybrid Batch Attacks: Finding Black-box Adversarial Examples with Limited Queries. In 29th USENIX Security Symposium (USENIX Security 20).
pages 1327-1344, 2020.
[23] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: physics engine for model-based control. In IEEE/RSJ International Conference Intelligent Robots and Systems, pages 5026 5033, 2012.
[24] Xingchen Wan, Henry Kenlay, Robin Ru, Arno Blaas, Michael A Osborne. and Xiaowen Dong- Adversarial Attacks on Graph Classifiers via Bayesian Optimisation. In Advances in Neural Information Processing Systems, volume 34, pages 6983-6996, 2021.
[25] Xingchen Wan, Nguyen, Huong Ha, Binxin Ru, Cong Lu, Michael Osborn.. Think global and act local: Bayesian optimisation over high-dimensinn dighddimensional categorical and mixed search spaces. In Proceedings of the 38th International Conference on Machine Learning, pages 1V663-10674 2021.
[26] Linnan Wang, Rodrigo Fonseca, and Yuandong Tian. Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search. In Advances in Neural Information Processing Systems, volume 33, pages 19511-19522, 2020.
[27] Zi Wang. Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched Large-scale Bayesian Optimization in High-dimensional Spaces. In Proceedings of the 21 International Conference on Artificial Intelligence and Staristics, pages 745-754, 2018.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The acquisition function used
(Sect. 3) is only an upper bound of the actual function like to optimize. (c) Did you discuss any potential negative societal impacts of your work? [Yes] See Sect.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sect. 3.
(b) Did you include complete proofs of all theoretical results? [Yes] See Sect. 3.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] See the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Sect. 4.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Sect. 4.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Sect. 4.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes] See Sect.
(b) Did you mention the license of the assets? [Yes] See Sect. 4.
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
See the supplemental material.
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [Yes] See the supplemental material.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See the supplemental material.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "rJLnslwJr-M", "reviewer": "Reviewer_ohQU", "summary": "The paper aims to improve Bayesian optimization in high-dimensional search spaces by proposing a new technique for local optimization. The authors build on prior work on local policy search with bayesian optimization (GIBO) by 1) showing that the expected value of the gradient may not coincide with the maximum probability of descent, and 2) proposing an optimization scheme which directly optimizes the probability of descent. In experiments, the approach tends to outperform GIBO as well as other more complicated baselines proposed in the literature.", "questions": "1. Do the authors have any intuition as to why swapping either of the components of MPD does not consistently improve over GIBO in the ablation study? Would we not have expected either one of the two components in isolation to already be an improvement? This may or may not be the case, but I would have liked the authors to give more intuition on this result.\n2. Have the authors considered additional ablation studies to quantify the advantages of MPD's local search when plugged as the local routine in McLeod et al. or Wang et al.? While not strictly within the scope of the paper, demonstrating the benefits of MPD as a general technique that can boost existing local optimization method would step up the impact of the paper.\n3. [key question] How did the authors come up with the default policy using p∗ = 65%? Since the ablation studies show that the results are to some extent sensitive to this choice, it is important to understand if 1) this is a general purpose default recommendation, and 2) how the recommendation was obtained (i.e., whether it was obtained on a given validation set before comparing to the baselines in Table 1).\n4. Have the authors also run ablation studies on the step size, which was set to δ = 0.001? Any insights on the impact of larger and lower step size values?\n5. Minor: Some of the compared baselines in Figure 2 do not seem to have fully \"converged\" (e.g., ARS on the 100D objective). If run for more queries, do all methods get to the same optimum? Do we observe any changes in ranking? While the used budget is arguably already very high, this would be interesting to confirm that on top of being the more query-efficient approach, MPD also tends to consistently converge to th best solution in the long run.\n6. Do the authors have any insights into what makes 33D Hopper so different from the other problems that lead MPD to be subpar compared to all three baselines? This is surprising as for very high dimensional spaces, the advantage of MPD was more pronounced on the synthetic functions.\n7. The evaluation considers number of queries on the x axis. What's the computational cost of the MPD local optimization step compared to baselines such as GIBO? What would the results look like with wall-clock time no the x axis?", "limitations": "The authors have adequately discussed the potential negative societal impact of the work, which coincides with the risks of any BO and generally AutoML black-box system (i.e., it can be exploited for malicious purposes). I agree with the authors that the benefits of the proposal outweight these risks.\n\nBeyond that, I believe the main limitations lie in the empirical section, due to some mixed results and the lack of clarity on the process that led to the choice of the method settings (probability of descent and delta). More details in the questions above. I am ready to increase my score if these questions are addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Clarity**\n\nThe paper was a pleasure to read. Very well-written, easy to follow and self-contained, with enough background on both general and local Bayesian optimization to bring the reader up to speed. It also includes great visualizations (Figure 1) that help build intuition on the behavior of the proposed approach.\n\n**Originality / Significance**\n\nThe problem of scaling up Bayesian optimization to high dimensional spaces is significant and the paper builds on the success of local optimization techniques. Showing that the most likely descent direction does not always coincide with the negative expected gradient is an interesting result, worth of value on its own even if unplugged from the resulting method.\n\nWhile to some extent the work incrementally builds on GIBO, the results improving the local optimization routine are general and can be plugged in any existing approach relying on local optimization (e.g., McLeod et al., Wang et al.). As such, the impact of the method is broader as improved results could potentially be observed for each of these baselines. For this reason, I would have liked to see experiments validating the hypothesis that the proposal is in fact a useful subroutine to replace previous local optimization across the board. This would have further increased the significance and breadth of impact of the paper.\n\n**Quality**\n\nThe paper's quality is overall high. The experimental evaluation is carefully carried out and includes ablation studies aiming at separating out the two key contributions of the proposed MPD approach (i.e., the learning phase or the update phase). From these results, it turns out that MPD does not perform consistently better against GIBO when one of the two new components is removed. This shows that both components need to be used in tandem to achieve improved results.\n\nThe proposal is theoretically grounded and the empirical evaluation is overall solid. The results show that the proposed approach tends to outperform baselines and particularly so as the dimensionality of the space grows on synthetic functions. While very promising and clearly outperforming baselines on these examples, the gap is not as pronounced on real-world objectives (Figure 3) and MPD is clearly worse on 33D Hopper. It is expected that not 100% of problems will show the benefits of MPD, but I would have liked the authors to elaborate and give intuition as to why there is such a clear drop in 33D Hopper.\n\nBeyond that, I particularly appreciated the results on interesting real-world problems. This sets an example for work in the BO space to evaluate the proposed methods beyond standard problems, such as those from hyperparameter optimization.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P5aKOSWjqrm", "reviewer": "Reviewer_Qcf8", "summary": "The paper develops a new approach for local Bayesian optimization by incorporating gradient into the Bayesian optimization as in the work by Muller et al [13] but instead of moving in the direction of the expected gradient, the paper proposes to identify the direction of most likely descent, and then move in that direction. To do so, the paper derives a closed-form solution for the direction of most likely descent at a given location in the input space under a GP belief about the objective function. A corresponding closed-form acquisition function that optimizes (an upper bound of) the one-step maximum descent probability is also developed to form the optimization scheme. Experiments on both synthetic and real-world tasks are conducted to demonstrate the performance of the proposed approach.\n\n################################ AFTER REBUTTAL ###################################\nThanks authors for your detailed response. I understand more about the behaviours of the proposed approach and I do not have any concerns about the Hopper function anymore. I have been thinking again about the work, and I think maybe I'm indeed picky, so I decided to increase my score to 6.", "questions": "Apart from my comments in the Weakness section which the authors can response, I have the following additional questions:\n\n•\tHow does the hyperparameter p^* affect the performance of the proposed approach?\n\n•\tWhat can be the reasons that the proposed approach performs badly for the objective function 33D Hopper?\n", "limitations": "The paper has some discussions on the societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is very well-written. All the concepts and the proposed approach are described clearly and easy to understand. The idea of incorporating the gradient information into the optimization process and move to the direction of most likely descent is sound and reasonable. Rigorous mathematical formulas are developed to derive the key components of the proposed approach (the direction of most likely descent and the acquisition function). The proposed approach has good performance in some objective functions.\n\nWeaknesses: Some of the weaknesses of the paper are as follows:\n\n•\tMaybe I'm picky but I think the idea is not too novel as it feels like it just fixes a particular issue of an existing BO approach. I do appreciate all the analysis conducted to show the issue of the approach in Muller et al [13] and all the derivations to find the most likely descent direction and to compute the new acquisition function. However, I normally expect the key idea to be more novel, and if it's not too novel, I expect the experiment results to be very impressive. In this case, the experiment results are not really that impressive. The proposed approach does have some very good performance on some objective functions; however, it also performs on par with other baselines in multiple objective functions, and it performs worse for some objective functions. \n\n•\tThe proposed approach is developed for the batch setting; however, only sequential setting (batch 1) is conducted in the experiments. \n\n•\tThe paper seems to lack of the discussion about some benchmarks on Bayesian optimization with gradient, for example the work Bayesian Optimization with Gradients by Wu et al (NeurIPS 2017).\n\n•\tI expect more sensitivity analysis and discussions on some hyperparameters of the proposed approach such as p^*.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IXBSnk3s9Ng", "reviewer": "Reviewer_stFc", "summary": "This paper studies local Bayesian optimization in which a GP surrogate is used to give a model for the gradient at a point, an acquisition function is used to select points that are informative about the gradient, and then gradient steps are taken to select the next point for evaluation. Past work has used information gain about gradient for acquisition, and the direction of negative expected gradient for taking the gradient step. This paper builds on that work by showing that it is better to move in the direction that maximizes the probability of descent, which because of posterior uncertainty in the gradient, is not necessarily the negative expected gradient. It shows how this quantity can be computed, and then proposes an analytic acquisition function that targets the same quantity. Empirical results show strong performance relative to the work that this builds on, as well as other related work in this same problem space.", "questions": "When we observe the new value f(x_{t+1}), do we always accept the move from x_{t} to x_{t+1} or do we accept it only if f(x_{t+1}) < f(x_{t})? I imagine that observing x_{t+1} will update the gradient information at x_{t}, so even if we do not accept the step and we repeat the acquisition optimization around the same x_{t} as in the previous optimization, we should take different steps. It sounds from the paper that we are always accepting steps, but I wonder if that is the best strategy.\n\nIs there anything about the 33D Hopper problem that explains why it performs worse?\n\nWas the RBF kernel ARD?\n\nThe paper gives results on sensitivity to p* but only for more conservative choices; what about e.g. 0.5?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found this paper to be very interesting. It studies an important problem (high-dimensional BO). While it does build directly on top of existing work and so does not present an entirely new approach to the problem, it gives a very insightful analysis into the failure cases for that existing work and does a great job at motivating the new method. The paper is very clearly written and the work is of high quality.\n\nThe new method is surprisingly elegant, and is strongly motivated by a very clear mathematical analysis as well as a great illustration in Fig. 1.\n\nThe empirical results are very strong and compare to what I think are the most appropriate baselines. An ablation study is included, as are real-world problems.\n\nBelow I give a few questions that I had that I expect other readers may be interested in as well, though I consider these all to be minor issues.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H6BvsC5W8Iz", "reviewer": "Reviewer_ogaD", "summary": "This paper proposes a local Bayesian optimization strategy via maximizing a probability of descent.  Unlike the previous work (Muller et al. 2021), this work computes the most likely descent direction by considering the problem of the expected gradient.  More precisely, as described in the paper, the expected gradient is not necessarily the direction maximizing the probability of descent.  The proposed method solves this problem by computing the most likely descent direction.  Finally, the authors demonstrate that the proposed method works well in various experiments.", "questions": "I would like to ask the authors some questions.\n\n1. In Line 88, a sentence, `Our work addresses this gap.` should be re-written.  Please clearly write the sentence by including what this gap is in the sentence.  I understand that it is not a final version, but please fix it in the final version.\n\n1. In Equation 4, why is an acquisition function over a batch of potential query points?  I think that an acquisition function over a single query is tested (as in Algorithm 1).\n\n1. Please add line numbers in Algorithm 1.\n\n1. In experiments, why are some results fluctuated?  Why are not the best minimum (or maximum) values plotted?", "limitations": "I do not think that this work has any negative societal impacts and any specific limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n+ It solves an interesting topic on local Bayesian optimization.\n\n+ It suggests a novel method by raising the drawbacks of the existing method.\n\n+ Experimental results do not always show the best results, which is very reasonable.  But please describe more thorough analyses on these results.\n\n## Weaknesses\n\n- I do not have specific weaknesses, but writing and presentation can be improved to clearly demonstrate the contributions of this work.\n\nPlease see the text box described below.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept