CobBO: Coordinate Backoff Bayesian Optimization with Two-Stage Kernels
Authors: Jian Tan
Niv Nayman
MengChang WANG
Rong Jin
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Bayesian Optimization

Abstract: Bayesian optimization is a popular method for optimizing expensive black-box functions. Yet it oftentimes struggles in high dimensions where a sufficient estimation of the global landscape requires more observations and the computation cost becomes prohibitively expensive.
We introduce Coordinate backoff Bayesian optimization (CobBO) with two-stage kernels to alleviate this problem.
In each iteration, a promising subset of coordinates is selected in the first stage, as past observed points in the full space are projected to the selected subspace adopting a simple kernel that sacrifices the approximation accuracy for computational efficiency.
Then in the second stage of the same iteration a more sophisticated kernel is applied for estimating the landscape in the selected low dimensional subspace where the computational cost becomes affordable. Effectively, this second stage kernel refines the approximation of the global landscape estimated by the first stage kernel through a sequence of observations in the local subspace. This refinement lasts until a stopping rule is met determining when to back off from a certain subspace and switch to another coordinate subset.
This decoupling significantly reduces the computational burden in high dimensions, while the two-stage kernels of the Gaussian process regressions fully leverage the observations in the whole space rather than only relying on observations in each coordinate subspace.
Extensive evaluations show that CobBO finds solutions comparable to or better than other state-of-the-art methods for dimensions ranging from tens to hundreds, while reducing the trial complexity and computational costs.

CobBO: Coordinate Backoff Bayesian Optimization with Two-Stage Kernels
Anonymous Author(s)
Affiliation Address email
Abstract
Bayesian optimization is popular method for optimizing expensive black-box functions. Yet it oftentimes struggles in high dimensions where the computation could be prohibitively expensive and sufficient estimation of the global landscape requires more observations. We introduce Coordinate backoff Bayesian optimiza- tion (CobBO) with two-stage kernels alleviate this problem. In each iteration, promising subset coordinates is selected in the first stage, as past observed points in the full space are projected to the selected subspace adopting simple kernel that sacrifices the approximation accuracy for computational efficiency. Then in the second stage of the same iteration a more sophisticated kernel applied for estimating the landscape in the selected low dimensional subspace where the com- putational cost becomes affordable. Effectively, this second stage kernel refines the approximation of the global landscape estimated by the first stage kernel through a sequence of observations in the local subspace. This refinement lasts until a stopping rule is met determining when back off from certain subspace and switch to another coordinate subset. This decoupling significantly reduces the com- putational burden in high dimensions, while the two-stage kernels of the Gaussian process regressions fully leverage the observations in the whole space rather than only relying observations in each coordinate subspace. Extensive evaluations show that CobBO finds solutions comparable to or better than other state-of-the-ard methods for dimensions ranging from tens to hundreds, while reducing the trial complexity and computational costs.
2
6
10
11
13
15
17
19
21
Introduction
22
23
Bayesian optimization (BO) has emerged as an effective zero-order paradigm for optimizing expen- sive black-box functions. The entire sequence of iterations rely only the function values of the already queried points without information on their derivatives. Though highly competitive low dimensions (e.g., the dimension D < 20 [15]), Bayesian optimization based on Gaussian Process (GP) regression has obstacles that impede its effectiveness, especially in high dimensions.
25
27
28
Approximation accuracy: GP regression assumes class of random functions in probability space 30 as surrogates that iteratively yicld posterior distributions by conditioning on the queried points. When suggesting query points, for complex functions with numerous local optima and saddle points 32 due to local fluctuations, always exactly using the values on the queried points as the conditional events may mismatch the function's 's local landscape by overemphasizing the approximation accuracy 34 of the global landscape.
38 Curse of dimensionality: As sample efficient method, Bayesian optimization often suffers from 37 high dimensions. Fitting the GP model (estimating the parameters, e-g., length_ scales [14]), comput- ing the Gaussian process posterior and optimizing the acquisition function in high dimensions all
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

25-
Acquisition optimization time
GP regression error (solid)
observe ved function volue (Costred)
20-
Exploradion
Exgloitation
1500
Vanila BD on Q
Laxs acturncei
Marcacccmaai
15
Cab80 on Qu
Capaue the
Capure the local landicape
global landscape
1000
10-
GP regress
CLidO usen
100
200 300
430 500
Iteration:
Iteration:
Figure I: Minimize the fluctuated Rastrigin function on [-5, 10 with 20 initial samples. [Left] Computation times for training the GP regression model and maximizing the acquisition function at each iteration. CobBO significantly reduces the execution time compared with a vanilla BO, e.g. x 13 faster in this case. [Right] The average error between the GP predictions before making queries and the true function values at the queried points (solid curves, the higher the better) and the best observed function value (dashed curves, the lower the better) at iteration t. CobBO captures the global landscape less accurately using the RBF kernel, and then explores selected subspaces S2 more accurately using the Matern kernel. This eventually better exploits the promising subspaces.
39 incur large computational costs. It also results in statistical insufficiency of exploration [11, 65]. As the GP regression's 's error grows with dimensions [8]. more samples are required to balance that in high dimensions, which could cubically increase the computational costs in the worst case [45].
40
41
To alleviate these issues, design coordinate backoff Bayesian optimization (CobBO) with two- stage kernels, by challenging a seemingly natural intuition stating that it is always better for Bayesian optimization have a more accurate approximation of the objective function all times. We demonstrate that this is not necessarily true, by showing that smoothing out local fluctuations and using the estimated function values instead of the true observations to serve the conditional events in selected subspaces can not only significantly reduce the computation time due to the curse of dimensionality but also help in capturing the large-scale properties of the objective function (xx)
43
45
47
48
49
Specifically, CobBO introduces the two-stage kernels with a stopping rule. The first stage of each iteration adopts simple kernel that sacrifices the approximation accuracy of fz) for computational efficiency. For example, by using a universal radial basis function (RBF) approximation without learnable parameters [50], CobBO can eliminate the model fitting time in the full space. It captures smooth approximation fxx) of the global landscape by interpolating the values of queried points projected to selected promising subspaces. These projected points serve as the conditional events for GP regression. In selected coordinate subspace, the second stage of the same iteration applies
51
53
54
55
58 a sophisticated kernel that can tolerate high computational cost in low dimensions. For example, CobBO uses the Automatic Relevance Determination (ARD) Matérn 5/2 kernel [40]. It refines the approximation of the local landscape by a sequence of observations determined by a stopping rule that backs off from a certain subspace and switches to another coordinate subset. addition, computing the Gaussian process posterior and optimizing the acquisition function are both efficiently conducted in the low dimensional subspaces, bypassing the curse of dimensionality.
57
58
59
60
61
82 For iteration i, instead of directly computing the Gaussian process posterior distribution
63 f())) M4 = {(x, v.)) x E 52 by conditioning on the observations y = =x;) at queried
64 points x; in the full space 12 c IR. for = 1,...,,,, ,,, we change the conditional events, and consider
{f(e) R (Pa, 2x), Ho) x Ω4 9 C C.)
85 for a projection function Ps.. (.) to random subspace 24 and an interpolation function R(:-) -), e.g..
66 using RBF approximation without learnable parameters [50] as the simple kernel for the first
67 stage. The projection (.) maps the queried points to virtual points on a subspace Ω2 of lower
68 dimension [51]. The interpolation function R(-,-) estimates the objective values at the virtual points
69 using the queried points and their values as specified by H.. The second stage within the subspace Ωt
70 uses the more sophisticated kernel, e.g., Matérn 5/2 kernel [40], which has number of parameters
71 that otherwise would be expensive to be learned in high dimensions.

---

72 This method can be viewed as a variant of block coordinate ascent tailored to Bayesian optimization by applying backoff stopping rules for switching coordinate blocks. While similar work exists [43, 48], CobBO differs by introducing the two-stage kernels and addressing the following three issues:
73
74
1. Selecting block of coordinates for ascending requires determining the block size well as the coordinates therein. CobBO selects the coordinate subsets by a multiplicatiie weights update method [2] to the preference probability associated with each coordinate. Thus, it samples more promising subspaces with higher probabilities.
76
78
79
2.
A coordinate subspace requires sufficient number of query points acting as the conditional events for the GP regression. CobBO leverages all observations in the whole space by interpolating the values of queried points projected selected promising subspaces, rather than simply starting from scratch in each subspace.
80
81
82
85
3. Querying a certain subspace, under some trial budget, comes at the expense of exploring other coordinate blocks. Yet prematurely shifting to different subspaces does not fully exploit the full potential of given subspace. Hence determining the number consecutive function queries within subspace makes a trade-off between exploration and exploitation. CobBO uses a stopping rule in each subspace to switch the selected coordinates. When consecutively querying data points in the same subspace, CobBO does not need to conduct the first-stage function approximation in the full space, which is far more efficient.
84
85
86
87
88
89
90
Through comprehensive evaluations, CobBO demonstrates appealing performance for dimensions ranging from tens to hundreds. It obtains comparable or better solutions with fewer queries, in comparison with the state-of-the-art methods, for most of the problems tested in Section 4.2.
91
82
2
Related work
Certain assumptions often imposed on the latent structure in high dimensions. Typical assumptions include low dimensional structures and additive structures. Their advantages manifest on problems with low dimension low effective dimension. However, these assumptions do not necessarily hold for non-separable functions with no redundant dimensions.
85
97
Low dimensional structure: The black-box function f is assumed to have a low effective dimen- sion [30, 58], e.g., f(z)= = g( (2x) with some function g(-) and a matrix & of x D.d << D. A number of different methods have been developed, including random embedding [66, 11, 63, 36,
99
101
44, 70, 5, 32], low-rank matrix recovery [11, 58), and learning subspaces by derivative informa-
102
tion [11, 13]. In contrast to existing work on subspace selections, c.g., Hashing enhaanee Subspace BO (HeSBO) [44], Mahalanobis kernel for linear embeddings [33], DROPOUT [35] and LineBO [29] (which receives special treatment in Appendix F), CobBO efficiently leverages all the observations in the whole space using the two-stage kernels and the stopping rule in each subspace for consecutive observations, rather than only relying on limited observations in each coordinate subspace. It exploits subspace structure from a perspective of block coordinate ascent, independent of the dimensions, different from some algorithms that are more suitable for low dimensions, e.g., BADS [1].
103
105
106
107
108
Additive structure: A decomposition assumption is often made by f(x) = = f(9 (as), with on defined over low-dimensional components. In this case, the effective dimensionality of the model is the largest dimension among all additive groups [45], which usually small. The Gaussian process is structured as an additive model [17, 28], c.g., projected-additive functions [36], ensemble Bayesian
109
110
111
112
113
optimization (EBO) [61], latent additive structural kernel learning (HDBBO) [65] and group additive
114
models [28, 36). However, learning the unknown structure incurs a considerable computational
115
cost [44], and is not applicable for non-separable functions, for which CobBO can still be applied.
116
Trust regions and space partitions: Trust region BO has been proven effective for high nigh-dimensional problems. A typical pattern is to alternate between global and local search regions. In the local trust regions, many efficient methods have been applied, e.g., local Gaussian models (TurBO [14)), adaptive search on mesh grid (BADS [1]) or quasi-Newton local optimization (BLOSSOM [41]).
118
119
120
TurBO [14] uses Thompson sampling to allocate samples across multiple regions. A related method is
121
to use space partitions, e.g., LA-MCTS[60] on Monte Carlo tree search algorithm to learn efficient
122
partitions. CobBO differs by selecting low dimensional subspaces. It can also incorporate trust
123
regions in the first-stage global approximation, as shown in the Appendix.
3

---

124 3
Algorithm
Without loss of generality, suppose that the goal is solve maximization problem x= argmax
fx) argmaxzze for a black-box function f f2 + IR. The domain is normalized ft = [0. 1]
126
127
with the coordinates indexed by / = 21, D).
128
For a sequence of points & = { 22, ,z with è indexing the most recent iteration, we observe
H. = { Dj [(x))) ==1 random subset C. C / of the coordinates is selected, forming a subspace Ω2 S 52 at iteration t. As variant of coordinate ascent, the subspace ft contains pivot
129
point V/, which presumably the maximum point x, = argmax f with M, = (=²").
131
132
CobBO may set V different from x to escape local optima. Then, BO is conducted within I2 while fixing all the other coordinates Cj = T Co, i.e, the complement of Ct.
135
Algorithm CobBO(f, T. T)
H4 + sample initial points and evaluate their values
2 V,, M, t Find the tuple with the maximal objective value in Hr,
(r 0 Initialize the number of consecutive failed queries
4 < Initialize a uniform preference distribution on the coordinates
for T to do
6
if switch Ω4-1 by the backoff stopping rule (Section 3.2) then
C - Sample promising coordinate block according to ne (Section 3.1)
8
S4 + Take the subspace of Q4 over the coordinate block C₁ such that V42 E 24
9
else
Sr + 9:-1
Le t Pa.
Project X2 onto Ω to obtain set of virtual points (Eq. D)
He R (e.HH.
Smooth function values on & by interpolation using He
13
p fo. (2)
Compute the posterior distribution the Gaussian process in S2
conditional on Hl.
( (x(H)) Suggest the next query Q4 (Section 3)
F++1 < argmax
Me41 Evaluate the black-box function Me+1 = fax411
if Vt+1 > M, then
V4+ < It+1, Me+1 + 1/++, 96+1 5-
else
V4+1 <- V,, M441 +- Mc, 9+11 + dr +1
T++1 < Update by multiplicative weights update method (Eq. 2)
21
He+1 +- He Ul(E+41, ((Z2411,6+1)) Re41 + Xr U(z+41
22 end
For BO in S4, we use Gaussian processes as the random surrogates f fo. (z) to describe the Bayesian statistics of (x) for E Ω4. At each iteration, the next query point is generated by solving
134
xt+1 argmax,en, Vien, ja, (w))=(((11,)) (x/))))
136
where the acquisition function (4x(14) incorporates the posterior distribution of the Gaussian processes H()) Typical acquisition functions include the expected improvement (EI) [42, 27], the upper confidence bound (UCB) [3, 54, 55], the entropy search [24, 25, 64], and the knowledge gradient [16, 53, 69].
137
138
139
Instead of directly computing the posterior distribution p(f(H()) we replace the conditional events H. by
140
He := R (Pa, (X,,, (4)) = ((ē,, i with an interpolation function R(.,.) and projection function Pa, (-), (x)
142
211)) (((0)
if C. if & C.
(1)

---

143
at coordinate j. It simply keeps the values of x whose corresponding coordinates are in C₁ and replaces the rest by the corresponding values of V₁, as illustrated in Fig.
144
Applying Pa. on X₂ and discarding duplicates generate new set of distinct virtual points Ar
145
146
(8 f2, $3,... F.), 5; E Q AA S Sist S The function values at d; E & are interpolated as D: R(; Hz) using the standard radial basis function [6. 7] and the observed points in Hy. It not only significantly reduces the GP regression time due to the efficiency of RBF [6] and the acquisition
147
148
149
function optimization in low dimensions [11], but also eventually improves the model accuracy using
150
the more sophisticated kernel applied on S2
Note that only a fraction of the points in & directly observe the exact function values. The function values on the rest ones in R are estimated by interpolation, which captures the landscape of f(x) by smoothing out the local fluctuations. To control the trade-off between the inaccurate estimations and the exact obser- vations in S2, we design a stopping rule that optimizes the number of consistent queries in
151
Observed points X
152
Vi at maximum
153
Virtual points X
154
Projection subspace 0l
RBF interpolation R(.-)
156
illstrated for virtual point
New point to be evaluated suggested by 80 Q2
158
Figure 2: Two-stage kernels: subspace projection and function value interpolation
160
Q. The more consistent queries conducted in a given subspace, the more accurate observations could be obtained, albeit at the expense of a smaller remaining budget for exploring other regions.
162
The key features of CobBO are listed in Algorithm 1, with more details in the following sections. Several auxiliary components are utilized and presented Appendix C to deal with a larger variety of problems and corner cases.
164
166
3.1 Block coordinate ascent and subspace selection
187 For Bayesian optimization, consider an infcasible assumption that each iteration can exactly maximize the function fxx) in 24. This is not possible for one iteration but only one can consistently query in Q4 since the points converge to the maximum, e.g., under the expected improvement acquisition function with fixed priors [59] and the convergence rate can be characterized for smooth functions
188
169
170
in the reproducing kernel Hilbert space [8]. However, even with this infeasible assumption, it is known that coordinate ascent with fixed blocks can cause stagnation at a non-critical point, e.g., for non din-diiffrentiable [67] or non-convex functions [49]. This motivates us to select subspace with variable-size coordinate block C, for each query. A good coordinate block can help the iterations to escape the trapped non- non-critical points. For example, one condition can be based the result in [21] that assumes f(x) to be differentiable and strictly quasi-convex over a collection of blocks. In practice, we do not restrict ourselves to these assumptions.
172
174
176
178
We induce a preference distribution ne over the coordinate set and sample a variable-size coordinate block Ct accordingly. This distribution is updated at iteration t through multiplicative weights update method [2]. Specifically, the values of n, at coordinates in C, starts off uniform and increase
179
180
in face of an improvement or decrease otherwise according to different multiplicative ratios >> 1
182
and B > 1, respectively,
i E C. and yt > M if j C and < M Wo,j = D Tt.j
1
Wi.j
Wh, = W(-1j
1/3
(2)
if G.
Dj=1 Wt.j
This update characterizes how likely coordinate block can generate promising search subspace. The multiplicative ratio a is chosen to be relatively large, e.g., a = 2.0, and 3 relatively small, e.g., 1.1, since the queries that improve the best observations ye > M, happen more rarely than the opposite yr I M,-1-
194
185
186
How to dynamically select the size |Cr|? It is known that Bayesian optimization works well for low dimensions [15]. Thus, we specify an upper bound for the dimension of the subspace (e.g- |C,| < 30). In principle, |C,] can be any random number in a finite set of possible block sizes C. This is different from the method that partitions the coordinates into fixed blocks and selects one according to, e.g.,
188
190
cyclic order [68], random sampling or Souss-louthwell [46].
5

---

192
3.2
Backoff stopping rule for consistent queries
193
Applying BO on Q4 requires strategy to determine the number of consecutive queries for making a sufficient progress. This strategy is based on previous observations, thus forming stopping rule. In principle, there are two different scenarios, exemplifying exploration and exploitation, respectively. Persistently querying a given subspace refrains from opportunistically exploring other coordinate combinations. Abruptly shifting to different subspaces does not fully exploit the potential of a given subspace.
194
195
197
199
CobBO designs a heuristic stopping rule compromise. It takes the above two scenarios into joint consideration, by considering not only the number of consecutive queries that fail to improve the objective function but also other factors including the improved difference M, M,-1, the point distance || æz-1ll, the query budget T and the problem dimension D). On the one hand, switching to another subspace 24+ (f Q4) prematurely without fully exploiting Q2 incurs an additional approximation error associated with the interpolation of observations in f2, projected to
200
201
202
203
204
205
On the other hand, it is also possible to over-exploit subspace, spending high query budget on marginal improvements around local optima. In order to mitigate this, even when a query leads to an improvement, other factors are considered for sampling a new subspace.
1.+1.
207
208
3.3
Theoretical Analysis
209
One can view our block coordinate selection approach in section 3.1 as combinatorial mixture of experts problem [10], where each coordinate single expert and the forecaster aims choosing the best combination of experts in each step. Under this view, we bound the regret of our selection method with respect to the policy of selecting the best (unknown) block of coordinates at each step.
210
211
212
213
Assume that there is a fixed optimal choice I for the block of coordinates to pick at all steps. This block is characterized by improving the objective function for the largest number of times among all the possible coordinate blocks when performing Bayesian optimization over the corresponding subspaces. The following particular design of losses expresses this cause:
214
215
216
log(ā) log(3)
if i E Ct and Vt > Mi-1
l,t
if i C and ye 1 M : a
if i & C.
217 as all the coordinates participating in the selected block incur the same loss that effectively rewards these coordinates for improving the objective and penalizes these for failing to improve the objective. All other coordinates that are not selected receive zero loss and remain untouched.
218
219
Note that â and 3 express the extent of reward and penalty, e.g. for â β we have losses of 221
b, 1,,, 13. Yet, ā is better chosen be larger than 3, since the frequency of improving the objective is expected to be smaller.
222
The loss received by the forecaster is to reflect the same motivation. This is done by averaging the losses of the individual coordinates in the selected block, so that the size of the block does not matter explicitly, i.c. bigger block should not incur more loss just due to its size but only due to its performance. Such that for each coordinate block I, C {I.-.. ... D} selected at time step f, the loss incurred by the forecaster is L,,z, |T.] Eiez, l, This is also the common loss incurred by all the coordinates participating in that block.
224
226
228
229
In each step we have the following multiplicative update rule of the weights associated with each coordinate (setting a = à and B = =f²" yields the update rule in Eq. 2):
230
if i C, and y/ > M if E G, and y I M if i & C.
Wt,; = W4-1, 6 Thit w1-1,
1/3"
(4)
The probability नr, of selecting certain coordinate block I, is induced by me specified next. Thus the expected cumulative loss of the foreceaster is:
Ly ΣΣΣ म
Σ lss TET.
[el
E=1 CEC I.

---

Assume the best coordinate block is I", then the corresponding cumulative loss is:
T
LT
4,
I
1E
We hence aim at bounding the regret Regretr
LT Li--
232 Theorem 1. Sample from the combinatorial space of all possible coordinate blocks I, E Ucec Se
233 with probability It = Ilie., "1.41//isse Ctes. 11,et W,,x- Then the update rule in Eq. 2 with â", 3 = and r log(ā.3) -1 D yields:
Regret, S O (1og(a3)
(5)
where " = IIIEI, Wh, 11 is the geometric mean of weights in block Z, The upper bound in Eq.
235
tight, as the lower bound can be shown to be of ((VT log(N)) [23] where the number of experts N Eeec Se S DDC|D in our combinatorial setup, as typically |C| < D.
236
237
238
In practice the direct sampling policy introduced in Theorem involves high computational costs due to the exponential growth of combinations in D. Thus CobBO suggests an alternative computationally efficient sampling policy with a linear growth in D.
240
241
Theorem 2. Sample a block size c with probability Pe and e coordinates without replacement
242
according to Tt.
Assume 3 {1), then the update rule in Eq. 2, with a = o", B = ,39 and
243
17
T(log( 63)2 (x)) 2 yields:
log
Regret+ S so (Viostaae) - log(p:)) -lo(m)))) - Tlog(DD)
(6)
where Pe > O for all e C and Ecec Pc = e.g., uniformly P. = -CI-1.The proof and detailed sampling policy are in Appendix A. The regret upper bound in Eq. 6 is tight, as the lower bound for
245
an easier setup can be shown to be of (lg))) [23]. The implication on is valid only for settings of very high dimensionality and low query budget. In particular, CobBO is designed for this kind of problems.
246
248
Remark: Similar analysis and results follow when incorporating consistent queries from Section 3.2 and sampling a new coordinate block once every several steps. This done by effectively performing less steps of aggregated temporal losses, shown in Appendix A.
250
252
4
Numerical Experiments
253
This section presents detailed ablation studies of the key components presented in Section 3 and comparisons with other algorithms.
4.1
Empirical analysis and ablation study
256
Ablation studies are designed study the contributions of the key components in Algorithm by experimenting with the Rastrigin function on [-5, 10]50 with 20 initial points. The best performing out of experiments for each configuration is presented in Figure 3.
257
Interpolation
Backoff stopping rule vs fixed consistent query
Fixed vs varying block sizes of the subspaces
Best observed value
1400
RBF(CobBO)
800
Backeff stopping rue (CobBO)
340-
Varying size (CobBO)
1200
IDW
Nearest neighbor
Connistent query
Conoistent query 8
1300
Fixed block size
Fined
1000
Connistent query
3000
Fixed block size 10
Consistent 2
Consistent query 1
(8)
(b)
400
(c)
0
100
200
300
400
500
200
300
Iterations
Iterations
258
Figure 3: Ablation study using Rastrigin [-5, 10)50 with 20 initial random samples
7

---

259
RBF interpolation: RBF calculation is time efficient. Specifically, this is much beneficial in high dimensions. Figure 1 (left) shows the computation time of plain Bayesian optimization compared to CobBO's. While the former applies GP regression using the Matérn kernel in the high dimensional space directly, the later applies RBF interpolation in the high dimensional space and GP regression with the Matérn kernel in the low dimensional subspace. This two-step composite kernel leads to significant speed-up. Other time efficient alternatives are, e.g., the inverse distance weighting [26] and the simple approach of assigning the value of the observed nearest neighbour. Figure 3 (a) shows that RBF is the most favorable.
260
262
263
264
266
267
Backoff stopping rule: CobBO applies stopping rule to query variable number of points in subspace Q4 (Section 3.2). To validate its effectiveness, we compare with schemes that use fixed budget of queries for S2. Figure 3 (b) shows that the stopping rule yields superior results.
268
289
270
Coordinate blocks of a varying size: CobBO selects a block of coordinates of a varying size Ce (Section 3. Figure 3 (c) shows that a varying size is better than fixed.
271
272
Preference probability over coordinates: For demonstrating the effectiveness of coordinate selection (Section 3.1), we artificially let the function value only depend on the first 25 coor-
Coordinate Selection: Probabiity and Entropy
274
Probability for selecting invective
276
dinates of its input and ignore the rest. It forms two separate sets of active and inactive coordi- nates, respectively. We expect CobBO to refrain from selecting inactive coordinates. Figure 4 shows the entropy of this preference probability
Scaled Entropy
0.56
8.5
278
0.
Probabiltt
279
280
04
Inactive Probabilty
2.00
281
T over coordinates and the overall probability
282
for picking active and inactive coordinate at each
0.8
283
iteration. We see that the entropy decreases, as
300
200
300
500
284
the preference distribution concentrates on the
Iterations
205
significant active coordinates.
Figure 4: The preference probability focuses on
active coordinates the entropy decreases
12D Lunar landing
30000
56D Additive function
1200
200D Levy function
25000
Value
800-
15000
600-
10000
400-
5000
200
250
500
750
1000
1250
1500
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Number of evaluations
Number of evaluations
Number of evaluations
12.5
14D Robot pushing
60D Rover trajectory planning
12.5
200D Ackley function
10.0
10.0
Value
7.5
Value
0.0
7.5
5.0
5.0
-2.5
2.5
2.5
-5.0
2000
4000
6000
8000
10000
5000
10000
15000
20000
0
2000
4000
6000
5000
10000
Number of evaluations
Number of evaluations
Number of evaluations
BADS
CobBO
TURBO
Diff-Evo
Figure 5: Performance over low (left) medium (middle) and high (right) dimensional problems
286
4.2
Comparisons with other methods
The default configuration for CobBO is specified in the supplementary materials. CobBO performs on par or outperforms a collection of state-of-the- thef-the-rtt art methods across the following experiments. Most of the experiments are conducted using the same settings as in TurBO [14], where it is compared with a comprehensive list of basclines, including BFGS, BOCK [47], BOHAMIANN, CMA-ES [22],
288
290
BOBYQA, EBO [61], GP-TS, HBO [44], Nelder-Mead and random search. To avoid repetitions,
292
we only show TuRBO and CMA-ES that achieve the best performance among this list and additionally
compare CobBO with BADS [1], REMBO [63], Differetial Evolution (Diff-Eve fiof-Evo) [56], Tree Parzen
294
Estimator (TPE) [4] and Adaptive TPE (ATPE) [12].
8

---

295
4.2.1
Low dimensional tests
296
To evaluate CobBO on low dimensional problems, we use the lunar landing [38, 14] and robot pushing [62], by following the setup in [14]. Confidence intervals (95%) over 30 independent experiments for each problem are shown in Fig. 5.
287
298
Lunar landing (maximization)): This controller learning problem (12 dimensions) is provided by the OpenAl gym [38] and evaluated in [14]. Each algorithm has 50 initial points and a budget of
300
1, 500 trials. TuRBO is configured with 5 trust regions and a batch size of 50 in [14]. Fig. 5 (upper
302
left) shows that, among the 30 independent tests, CobBO quickly exceeds 300 along some good
303
sample paths.
Robot pushing (maximization): This control problem (14 dimensions) is introduced in [62] and extensively tested in [14]. We follow the setting in [14], where TuRBO is configured with batch size of 50 and 15 trust regions, each of which has 30 initial points. Each experiment has a budget of 10, 000 evaluations. On average CobBO exceeds 10 within 5500 trials, shown in Fig. 5 (lower left).
304
306
308
309
4.2.2 High dimensional tests
Since the duration of each experiment in this section is long, confidence intervals (95%) over repeated 10 independent experiments for each problem are presented.
311
312
Additive latent structure (minimization)): As mentioned in Section 2, additive latent structures have been exploited in high dimensions. We construct an additive function of 56 dimensions, defined as fse(x) = Ax)ley(x1) + Lxvy + Rastrigin(x3) + Hartmann(x4) + Roseubrock(x3) (xx)), where the first three terms express the exact functions and domains described in Section 1, the Hartmann function on [0, 166 and the Rosenbrock and Schwefel functions on [-5, 10 10 and [-500, 500)2", respectively.
313
315
317
318
We compare CobBO with TPE, BADS, CMA-ES and TuRBO, each with 100 initial points. Specifi- cally. TuRBO is configured with 15 trust regions and a batch size 100. ATPE is excluded as it takes more than 24 hours per run to finish. The results are shown in Fig. 5 (upper middle), where CobBO quickly finds the best solution among the algorithms tested.
319
320
321
322
Rover trajectory planning (maximization)): This problem (60 dimensions) is introduced in [62].
323
The objective is to find a collision-avoiding trajectory of sequence consisting of 30 positions in 2-D plane. We compare CobBO with TuRBO, TPE and CMA-ES, each with a budget of 20, 000 evaluations and 200 initial points. TuRBO is configured with 15 trust regions and a batch size of
324
325
328
100, as in [14]. ATPE, BADS and REMBO are excluded for this problem and the following ones,
327
as they all take more than 24 hours per run. Fig. 5 (lower middle) shows that CobBO has a good performance.
328
329
The 200-dimensional Levy and Ackley functions (minimization)): We minimize the Levy and Ackley functions over [-5, 10 200 with 500 initial points. TuRBO is configured with 15 trust regions and a batch size of 100. These two problems are challenging and have no redundant dimensions. For Levy, in Fig. 5 (upper right), CobBO reaches 100.0 within 2, 000 trials, while CMA-ES and TuRBO obtain 200.0 after 8, 000 trials. TPE cannot find a comparable solution within 10, 000 trials this
331
332
333
334
case. For Ackley, in Fig. 5 (lower right), CobBO reaches the best solution among all of the algorithms tested.
335
Regarding running times, for Ackley, CobBO runs for 12.8 CPU hours and TuRBO-1 run for more
337
than 80 CPU hours or 9.6 GPU hours. Most other methods either cannot make any progress or find far worse solutions.
5
Conclusion
339
340
CobBO is a variant of coordinate ascent tailored for Bayesian optimization with stopping rule to switch coordinate subspaces. The sampling policy of subspaces is proven to have tight regret bounds
341
342
with respect to the best subspace in hindsight. Combining this projection on random subspaces with a two-stage kernels for function value interpolation and GP regression, we provide a practical Bayesian optimization method of affordable computational costs in high dimensions. Empirically, CobBO consistently finds comparable or better solutions with reduced trial complexity comparison with the state-of-the-a the- methods across variety of benchmarks.
343
345
9

---

References
347
348
[1] Luigi Acerbi and Wei Ji Ma. Practical bayesian optimization for model fitting with bayesian adaptive direct search. In Proceedings of the 31st International Conference on Neural Infor- mation Processing Systems, NIPS' 17, page 1834-1844, Red Hook, NY, USA, 2017. Curran Associates Inc.
350
352
[2] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method:
353
meta-algorithm and applications. Theory of Computing, 1(6):12 2012.
354
[3] Peter Auer. Using confidence bounds for exploitatinn-explortiin trade-offs. J. Mach. Learn. Res., 3 Mar. 2003.
355
356 [4] James S. Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlet, F, Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 2546-2554.
357
358
359
Curran Associates, Inc., 2011.
380
[5]
Mickaël Binois, David Ginsbourger, and Olivier Roustant. On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of Global Optimization. 76(1):69 January 2020.
381
362
383
[6] Martin D. Buhmann. Radial Basis Functions: Theory and Implementations. Cambridge
384
Monographs on Applied and Computational Mathematics. Cambridge University Press, 2003.
365
77]
Martin D. Buhmann and M. D. Buhmann. Radial Basis Functions. Cambridge University Press,
366
USA, 2003.
387
[8] Adam D. Bull. Convergence rates of efficient global optimization algorithms. Journal of
368
Machine Learning Research, 12(88))2879-290) 2011.
369
99
Roberto Calandra, André Seyfarth, Jan Peters, and Mare Peter Deisenroth. Bayesian optimiza- tion for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76(1):5-23, 2016.
370
371
372
100]
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[1I] Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional gaussian process bandits. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 1025-1033 Curran Associates, Inc., 2013.
375
377
378
[12] ElectricBrain. Blog: Learning to optimize, 2018
379
[13] David Eriksson, Kun Dong, Eric Lee, David Bindel, and Andrew G Wilson. Scaling gaussian process regression with derivatives. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Desa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6867-6877. Curran Associates, Inc., 2018
381
382
383
[14]
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. In Advances in Neural Information Processing Systems 32, pages 5496-5507. Curran Associates, Inc., 2019.
384
385
386
[15] Peter I. Frazier. A tutorial on bayesian optimization, 2018.
387
[16] Peter I. Frazier, Warren B. Powell, and Savas Dayanik. A growdetge-gradient policy for sequential information collection. SIAM J. Control Optim., 47(5):2410-2439, Sept. 2008
388
389
[17] Elad Gilboa, Yunus Saatçi, and John P. Cunningham. Scaling multidimensional Gaussian processes using projected additive approximations. In Proceedings of the 30th International Conference on International Conference on Machine Learning Volume 28, ICML' 13, page 1-454-1-46.. M0..1..MMRR.. JMLR.org, 2013.
390
391
392
393
[18]
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and D Sculley. Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1487-1495. 2017.
394
395
396
397
[19]
Rafael Gómez-Bombarele Jennifer N Wei, David Duvenaud, José Miguel Hernández- Benjamín Sänchez-LLngelling, Dennis Sheberla, Jorge Aguilera-Iparraguirre Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268-25 2018
398
389
400
401
[20] Javier Gonzalez, Zhenwen Dai, Philipp Hennig, and Neil Lawrence. Batch bayesian optimization via local penalization. In Arthur Gretton and Christian C. Robert, editors. Proceedings of the
10

---

403
19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings
404
of Machine Learning Research, pages -88-657, Cadiz, Spain, 09-11 May 2016. PMLR.
405
[1
Luigi Grippo and Marco Sciandrone. On the convergence of the block nonlinear gauss-seidel method under convex constraints. Operations Research Letters, 26 2000.
406
407
[22]
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolu- tion strategies. Evolutionary Computation, (22)155-115, June 2001.
409
[23]
David Haussler, Jyrki Kivinen, and Manfred K Warmuth. Tight worst-case loss bounds for predicting with expert advice. In European Conference on Computational Learning Theory,
410
411
pages 69-83. Springer, 1995.
412
[24] Philipp Hennig and Christian J. Schuler. Entropy search for information-efficient global optimization. J. Mach. Learn. Res., ((():1809-11837 June 2012.
413
414
[25]
José Miguel Henrández-Lobato, Matthew W. Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Proceedings of the 27th International Conference on Neural Information P Processing Systems - Volume 1, N.NISS 14,
415
416
417
page 918-926, Cambridge, MA, USA, 2014. MIT Press.
418
[26]
IDW, https: //en wikipedid a. org/ otg/oooi////ooooooooooo...o.o prriki/Inverer
[27] Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455-442 1998.
420
421
[28] Kirthevasan Kandasamy, Jeff Schneider, and Barnabás P6czos. High dimensional bayesian
422
optimization and bandits via additive models. In Proceedings of the 32nd International Confer- ence on International Conference on Machine Learning- Volume 37, ICML'15,, page 295-304. JogR.org. 2015.
423
425
[29]
Johannes Kirschner, Mojmir Mutny, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adaptive and safe Bayesian optimization in high dimensions via one-dimensional subspaces. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 3429-3438, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
426
427
428
429
430
[30] H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86(1):97-1M))
mar 1964.
[31] Rémi Lam, Matthias Poloczek, Peter Frazier, and Karen E Willcox. Advances in bayesian optimization with applications in aerospace engineering. In 2018 AIAA Non-Deterministic Approaches Conference, page 1656, 2018.
435
435
[32] 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, 2020.
438
437
438
[33] Ben Letham, Roberto Calandra, Akshara Rai, and Eytan Bakshy. Re-examining linear embed- dings for sigh-dimensional bayesian optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, vol- ume 33, pages 1546-1558. Curran Associates, Inc., 2020.
440
[34] Benjamin Letham, Brian Karrer, Guilherme Ottoni, Eytan Bakshy, et al. Constrained bayesian optimization with noisy experiments. Bayesian Analysis, 14(2):495-519, 2019.
443
444
[35]
Cheng Li, Sunil Gupta, Santu Rana, Vu Nguyen, Svetha Venkatesh, and Alistair Shilton. High dimensional bayesian optimization using dropout. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 2002-2102, 2017.
445
446
[36]
Chun-LLang Li, Kirthevasan Kandasamy, Barnabas Poczos, and Jeff Schneider. High dimen- sional bayesian optimization via restricted projection pursuit models. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 884-892, Cadiz, Spain, 09-11 May 2016. PMLR.
448
450
451
[37] Daniel J Lizotte, Tao Wang, Michael H Bowling, and Dale Schuurmans. Automatic gait optimization with gaussian process regression. In IJCAI, volume 7, pages 944-949, 2007.
453
454
[38]
LunarLander v2. https://est http://ygyoooo..i..... com/ coom/envs// wtte////s////aaeaeeeeee /LnnarLaannee-ve)
[39]
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Desa-Bianchi, and R. Gareett, editors, Advances in Neural Information Processing Systems
456
458
31, pages 1800-1809. Curran Associates, Inc., 2018
459
[40] Matern kernel. https://scikit learn. learn.ergg/ sstaale/mmchullssggnertteedd skklearn
gaussian_process kernels .attesn,tennn....n html.
11

---

461
[41] Mark McLeod, Michael A. Osborne, and Stephen J. Roberts. Optimization, fast and slow: Optimally switching between local and bayesian optimization. In ICML, 2018.
462
463
[42] J. Močkus. On bayesian methods for seeking the extremum. In G. I. Marchuk, editor, Optimiza- rion Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974, pages Heidelberg, 1975. Springer Berlin Heidelberg.
464
Berlin,
485
486
[43] Riccardo Moriconi, K. S. Sesh Kumar, and Marc Peter Deisenroth. High-dimensional bayesian optimization with projections using quantile gaussian processes. Optimization Letters, 14:51-64, 2020.
467
469
[44] Alexander Munteanu, Amin Nayebi, and Matthias Poloczek. A framework for Bayesian optimization in embedded subspaces. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4752-4761, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
470
471
472
473
474
[45]
Mojmir Mutny and Andreas Krause. Efficient high dimensional bayesian optimization with additivity and quadrature fourier features. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems Curran Associates, Inc., 2018.
476
31, pages
478
[46] Julie Nutini, Mark Schmidt, Issam H. Laradji. Michael Friedlander, and Hoyt Koepke. Coordi- nate descent converges faster with the gauss-southwell rule than random selection. ICML'15: Proceedings of the 32nd International Conference on International Conference on Machine Learning, 37, July 2015.
479
480
482
[47] Chang CoangYong Oh, Efstratios Gavves, and Max Welling. BOCK: Bayesian optimization with cylindrical kernels. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3868-3877, Stockholm, Sweden, 10-15 Jul 2018. PMLR. [48] Rafael Oliveira, Fernando Rocha, Lionel Out, Vitor Guizilini, Fabio Ramos, and Valdir Jr. Learning to race through coordinate descent bayesian optimisation. In IEEE International Conference Robotics and Automation (ICRA), February 2018.
483
484
485
487
489
[49]
M.J.D. Powell. On Search Directions for Minimization Algorithms. AERE-TP. AERE, Theoret-
490
ical Physics Division, 1972.
[50] Radial basis function. Attps://doces scipy. ottp///c/ssap///eeeeeeee//gggnee
482
scipy secipy.intee interpooatte Rbf html.
493
[11] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 1177-1184. Curran Associates, Inc., 2008
494
[52] Akshara Rai, Rika Antonova, Seungmoon Song, William Martin, Hartmut Geyer, and Christo- pher Atkeson. Bayesian optimization using domain knowledge on the atrias biped. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 1771-1778 IEEE, 2018.
497
498
489
[53] Warren Scott, Peter Frazier, and Warren Powell. The correlated knowledge gradient for simulation optimization of continuous parameters using gaussian process regression. SIAM Journal Optimization, 2163);996 2011.
501
502
503
[54] 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 International Conference on Machine Learning, ICML' 10, page 1015-1022, Madison, WI, USA, 2010.
504
505
506
[55] N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. Information- -hormattiontthooretic regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory,5865 585))33550-332655 2012.
508
509
510
[56] Rainer Storn and Kenneth Price. Differential evolution-a a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4):341-35, 1997.
512
513
[57] Sonja Surjanovic and Derek Bingham. Optimization test problems, 2013.
514
[58] Hemant Tyagi and Volkan Cevher. Learning non-parametric basis independent models from point queries via low-rank methods. Applied and Computational Harmonic Analysis, 37(3):389
515
412, 2014.
12

---

517
[59]
Emmanuel Vazquez and Julien Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. Journal of Statistical Planning and Inference, 140(11)33088 - 3095, 2010.
518
519
520
[60] Linnan Wang. Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using monte carlo tree search. ArXiv, abs/2007 2020.
521
522
61
Zi Wang. Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale bayesian optimization in sigh-dimensional spaces. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
524
525
[62] Zi Wang. Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale bayesian optimization in high-dimensionas spaces. In International Conference on Artificial Intelligence and Statistics, pages 745- 4444,55, 2018.
527
528
[63]
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Freitas. Bayesian optimization in billion dimensions via random embeddings. J. Artif. Int. Res., 55())36613387
530
Jan. 2016.
531
[64]
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3627-3635, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
532
539
534
535
[65]
Zi Wang, Chengtao Li, Stefanie Jegelka, and Pushmeet Kohli. Batched high-dimensional bayesian optimization via structural kernel learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML' 17, page 3656-3664. JMLR.org, 2017.
536
537
538
[66] Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, and Nando De Freitas. Bayesian optimization in high dimensions via random embeddings. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '13 page 1778-1784. AAAI Press, 2013.
539
540
541
677 J. Warga. Minimizing certain convex functions. Journal of the Society for Industrial and
543
Applied Mathematics, 11(3):588-593, 1963.
544
[68] Stephen Wright. Coordinate descent algorithms. Mathematical Programming: Series A and
B, June 2015.
[69]
Jian Wu and Peter I. Frazier. The parallel knowledge gradient method for batch bayesian optimization. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 3134-3142, Red Hook, NY, USA, 2016. Curran Associates Inc.
547
549
550
[70]
Miao Zhang, Huiqi Li, and Steven Su. High dimensional bayesian optimization via supervised dimension reduction. In Proceedings of the Twenty-Eights Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 4292-4298. International Joint Conferences on Artificial Intelligence Organization, 2019.
552
553
554
[71] Yichi Zhang, Daniel W Apley, and Wei Chen. Bayesian optimization for materials design with mixed quantitative and qualitative variables. Scientific reports, 10(1):1-13, 2020.
555
Broader Impact
556
As stated in [32], Bayesian optimization is powerful optimization technique used in wide range of industries and applications, such as robotics [37, 9, 52], internet tech companies [18, 34], designing novel molecules for pharmaceutics [19]. material design for increasing efficiency of solar cells [71], and acrospace engineering [31]. All of these settings have high- nigh-dimensional optimization problems, and advances in BO will reflect on improved capabilities on these fields as well. We have fully open- sourced our code for CobBO using the MIT license to be available for researchers and practitioners in these fields, and many others. The ability optimize a larger number of parameters than has previously been possible will bring further improvements to and further accelerate work in these
558
560
562
563
564
585
areas.
Checklist
586
567
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or
13

---

589
[N/A]. You are strongly encouraged to include justification to your answer. either by referencing the appropriate section of your paper or providing a brief inline description. For example:
570
Did you include the license to the code and datasets? [Yes] See Section ??.
572
Did you include the license to the code and datasets? [No] The code and the data are
573
proprietary. Did you include the license to the code and datasets? [N/A]
575
Please do not modify the questions and only use the provided macros for your answers. Note that the
578
Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
577
578
1. For all authors...
579
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 3.
(b) Did you describe the limitations of your work? [No]
582
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Broader Impact.
583
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
585
586
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.3.
586
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix A.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] In the supplemental material.
591
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Table 2 in the appendix, which contains the default hyperpa- rameters.
594
595
596
(c) Did you report error bars (e-g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Fig.5 and Fig.8-10.
587
(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 page 9, line 324.
599
600
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
602
(b) Did you mention the license of the assets? [Yes] MIT license; see the appendix.
603
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
604
(d) Did you discuss whether and how consent was obtained from people whose data you're
605
using/curating? [Yes] See Section 4.2.
606
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] It does not contain personal identifiable information or offensive content.
608
609
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
611
612
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
613
614
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rf1jxvub0zn", "reviewer": "Reviewer_eR6t", "summary": "This paper proposes a new High-dim BO framework inspired by Block coordinate ascent. Although similar, this paper differs from other works which leverages a low dimensional structure assumption in that it utilizes all the dimension in the function space. Aside from the overall scheme, its other contributions include (1) an update scheme for the coordinate sampling distribution; (2) a heuristic stopping rule to balance between exploiting current coordinate block and exploring new coordinate blocks; and (3) a theoretical analysis that upper bounds the total regret on a surrogate loss function. The framework shows some promising results when compared with other high-dim BO works.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "--Clarity\nThe paper is generally well written and easy to follow. I have some minor confusions:\n\n1. In the algorithm, the posterior is described as p(\\hat{f}| \\hat{H}). Is the posterior specified by a GP with low dimensional kernel or high dimensional kernel, but the length-scales on inactive coordinates are frozen (not learned)?.\n\n2. At the beginning of section 4.2, it was claimed that CobBO was compared to REMBO and ATPE but I don't see the comparison anywhere. Also, what would  BOHB be in Fig.5 ?\n\n--Originality\nThe motivation behind doing BO along a subset of coordinates has been explored many times in the literature. This paper argues that the proposed method, CobBO, \"efficiently leverages all the observations in the whole space ... rather than only relying on limited observations in each coordinate subspace\". As far as I understand, DROPOUT [35] also re-selects the active coordinates at every iteration (and fill in the remaining coordinates using some heuristic strategy), which guarantees making use of all coordinates in the long run. However, I believe that the proposed subspace selection algorithm is more informed due to the update scheme of the sampling distribution.\n--Quality\nMy main concern with this paper is that the theoretical analysis is not conventional (with respect to the BO literature). In my experience, BO regret analysis usually measures the regret on the objective function itself rather than a surrogate loss. It could be useful to assert that the sampling scheme will, in the asymptotic sense, always pick the right subspace to improve the objective the most number of times; but it does not inform us by how much does it improve the objective. It seems to me that the proposed regret bound is an analysis of the coordinate descent aspect alone, and is entirely independent of the optimization routine within each selected subspace (i.e., if I replace BO by something else, would anything change?). \n\nPlease refer to the Significance subsection for my comments on the experiments.\n\n--Significance\n1. For some experiments (e.g., Levy 200D and Ackley 200D), I don't think all methods have converged by the end of 10000 iterations. It would probably take longer to conclude that one is clearly superior to another. \n2. I would suggest some ablation study to show the effect of having variable coordinate block size |C_t| (as I understand, it is now capped at 30). On average, how many coordinates are sampled per iterations? Is there a lower bound to prevent the scheme from selecting none? How does it affect performance if we increase/decrease the upper bound?\n3. It was claimed that REMBO takes too long for Ackley 200D, but I dont see how it is the case if we limit the number of effective dimension (to be roughly the same as the average no. selected coordinates by CobBO)? Seems to me that both REMBO and CobBO optimize a low dimensional GP at every iteration with the same no. observations, so what makes one significantly slower than the other?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have described the Broader impact of this paper, which I find reasonable. I believe there would be no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "SGNTE6i2qi", "reviewer": "Reviewer_CYQL", "summary": "This paper aims at making Bayesian optimization scalable to problems with large dimensional inputs. The authors propose an approach that selects block coordinates of the input space to explore at each iteration. The authors provide some theoretical results to support the proposed approach, and report experimental results to demonstrate that the proposed approach can achieve better performance than existing approaches.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: \nThe main idea of the proposed approach is to use the multiplicative weights update method in Bayesian optimization. To my limited knowledge about Bayesian optimization, this is novel and thus the originality is reasonable. \n\n\nQuality:\nWhile the approach seems reasonable and the experimental results look promising, I have the following concerns about the paper. \n\n- The way they cite some of the existing works is not very precise, and thus I don't have a good impression of the quality of the work. For instance, [6] and [7] are the same book;  [26] on inverse distance weighting is Wikipedia; [32] and [33] are the same paper; [40] on Matern kernels is a webpage of scikit learn; [50] on radial basis functions is a webpage of scipy; [61] and [62] are the same paper; [64] and [65] are the same paper. \n\n- In lines 32-34, the authors say ``always exactly using the values on the queried points as the conditional events may mismatch the function’s local landscape by overemphasizing the approximation accuracy of the global landscape.'' Similar arguments are made in lines 43-48. I feel confused to see this argument. In GP regression, we usually assume noisy outputs, and the use of a regularized matrix inversion (where the regularizer is given by the noise variance) incorporates this assumption by automatically smoothing the outputs. \n\n- In line 57, the authors say ``CobBO uses the Automatic Relevance Determination (ARD) Matérn 5/2 kernel.'' But it is not clear how the authors specify the weights of this ARD kernel, as this is also not described in the supplementary. And the authors do not explain the value of the length scale parameter in the kernel. \n\n- In line 12 of Algorithm 1, there exists an RBF interpolation, denoted by $R$. The authors should describe the explicit from this interpolator. While the authors seem to explain that the RBF interpolation and GP regression are different, they are essentially the same approach. As such, RBF interpolation requires the computational complexity cubic to the data size. This point should also be discussed.\n\n- In line 14 of Algorithm 1, $\\Omega_t$ denotes the subspace spanned by the block coordinates $C_t$. I am wondering about how the authors specify the values for the coordinates in $\\Omega_t$ not selected in $C_t$. For instance, suppose the dimensions are $D = 4$ and $C_t = \\{1, 2\\}$. Then is $x \\in \\Omega_t$ given in the form $x = (x_1, x_2, 0, 0)$ by specifying the coordinates not in $C_t$ (i.e,. \\{3, 4\\}) to be zeros? This point is not clear from the presentation. If this is the case, the authors implicitly make an assumption about the optimal solution that some of their coordinates are zero. This is rather a strong assumption.\n\n- In Section 3.3, the authors define ``regret'' in terms of the selection of the best coordinate block. This regret is different from the regrets defined in terms of the global optimizer, usually analyzed in the Bayesian optimization literature. Therefore, the theoretical results of the paper do not really provide a theoretical guarantee for the proposed approach in terms of the convergence to the global optimizer.  \n\n- While the authors show the hyperparameter settings in Table 2 of the supplementary, some information is still missing, such as the acquisition function used and the length scales of the kernels in RBF interpolation and GP regression. \n\n\nClarity:\n- Since the authors omit the concrete expressions for many mathematical concepts (e.g., RBF interpolation and the subspace $\\Omega_t$), it is not very easy to deeply understand the mechanism of the proposed algorithm. Also, some key information for reproducing the experimental results is missing. \n\nSignificance:\n- There are many hyperparameters that need to be chosen in the proposed algorithm. (Table 2 in the supplementary shows an incomplete list of the hyperparameters.) If the performance of the proposed algorithm is sensitive to the choice of these parameters, the algorithm is not easy to be used by practitioners. This point is not clear from the paper. If this is the case, the significance of the proposed method is limited. \n\n- Also, as described above, it may be the case that the proposed approach implicitly assumes that some of the coordinates of the global optimizer are zeros. If this is the case, the proposed approach can only be applied to problems that satisfy this assumption, which may be restrictive.\n\n\n------------ Post rebuttal --------------\nAs the authors made some clarifications, I have increased my score to 5. Still, however, I'm not very convinced by the argument of the authors on regret analysis.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16 hours"}, "extra_text": {}}, {"review_id": "KJl7tsblCyX", "reviewer": "Reviewer_uzhR", "summary": "The authors have proposed a new algorithm for black box optimization called CobBO. At a fundamental level, the algorithm is the extension of classic block coordinate ascent to black box optimization using techniques from Bayesian Optimization. The algorithm focuses on a small subset of coordinates in every iteration. In the first step, it uses a simple kernel to interpolate the values of the function learnt at other points to the points in the subspace. In the next step, it uses a full fledged BO with a more sophisticated kernel in the subset to learn the function in this subspace. It balances exploration and exploitation between subspaces by using a backoff stopping rule. The authors have supported their case by extensive empirical studies and some theoretical results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n- The paper proposes an interesting algorithm to address the troubles that usually BO based methods face in high dimensional problems. While the basic concept of block coordinate ascent to address high dimensionality is already known and well studied, the authors apply this for BO and take care of several aspects to make it a practically usable algorithm.\n- The empirical evaluation of the algorithm seems quite extensive.\n\nQuestions for the authors:\n- The paper mentions that the scale of RBF is not tuned and is fixed before hand. I am curious as to how this choice affects the results. It is clear that one cannot set an arbitrary value as it might lead  to over smoothing or under smoothing. So is there a range where it works well and how is it chosen? Also how does this choice affect the results?\n- While the algorithm is clearly set in the noiseless regime (which is fine), I am curious as to what will happen in the noisy regime? Clearly some of aspects cannot be directly taken over since we would not have access to exact function values. How robust do you expect the algorithm to be to noise in the current version (only allowing for noisy updates of posterior and no additional adaption) ? I am curious because typically one would expect noise in real world scenarios and if the algorithm is sensitive it can break under the noise.\n- The description of Sec 3.1 and 3.2 is unclear. There are clarifying details in Appendix C, but overall I could not find one description of the algorithm where the choice of $C_t$ and the backoff is explicitly stated, as used in the experiments. If different versions outlined in Appendix C are used in different experiments, depending on the task, I don't think the comparison is fair since CobBO is allowed to make some changes depending on the function but others are not. I think it would be really helpful and clear if the stopping rule and choice of subspace is exactly mentioned in the main paper.\n- Could you elaborate the intuition behind the description of the stopping rule outlined in Appendix C? It seems like too precise a definition without sufficient description as to how the specific form was obtained.\n- Is the value $|C_t|$ chosen uniformly at random in $\\{1,2, \\dots, 30\\}$? \n- In the ablation study, when only of one parameters is studied, what is the value of the other ones which are kept constant?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies high-dimensional Bayesian optimization, and adapts block coordinate ascent to the BO context, which seems to be practically useful as supported by extensive empirical evidence. However, after the discussion phase there remain concerns among the committee in the significance of technical contributions: (1) The theoretical analysis serves only as a justification of the algorithm, focusing mainly on the coordinate descent aspect, not directly on the BO regret, hence making the theoretical contribution incremental. (2) The basic idea of coordinate ascent with BO has been explored in literature. The paper is built on such insight and focuses on how to informatively choose a subspace; however, the technical strength is not strongly supported by the existing theoretical analysis/justification. (3) There are a few clarity concerns raised in the reviews, which suggest that the paper could benefit from a major revision to address the above concerns.
Decision: Reject