Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces
Authors: Leonard Papenmeier
Luigi Nardi
Matthias Poloczek
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian optimization
global optimization
Gaussian process
high-dimensional

Abstract: Recent advances have extended the scope of Bayesian optimization (BO) to expensive-to-evaluate black-box functions with dozens of dimensions, aspiring to unlock impactful applications, for example, in the life sciences, neural architecture search, and robotics. However, a closer examination reveals that the state-of-the-art methods for high-dimensional Bayesian optimization (HDBO) suffer from degrading performance as the number of dimensions increases, or even risk failure if certain unverifiable assumptions are not met. This paper proposes BAxUS that leverages a novel family of nested random subspaces to adapt the space it optimizes over to the problem. This ensures high performance while removing the risk of failure, which we assert via theoretical guarantees. A comprehensive evaluation demonstrates that BAxUS achieves better results than the state-of-the-art methods for a broad set of applications.

Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces
Leonard Papenmeier
Luigi Nardi Lund University, Stanford University, DBtune luigi. wtt.i..aadiccs..mm 1tth.se
Lund University leonard. papeemeeesseeeeeeeeeeeeeess se
Matthias Poloczek*
Amazon
San Francisco, CA 94105, USA
matpol@amazon.comm com
Abstract
Recent advances have extended the scope of Bayesian optimization (BO) expensive-to-evallee black-box functions with dozens of dimensions, aspiring to unlock impactful applications. for example, in the life sciences, neural architec- ture search, and robotics. However, closer examination reveals that the state-of- the-art methods for high-dimensional Bayesian optimization (HDBO) suffer from degrading performance as the number of dimensions increases or even risk failure if certain unverifiable assumptions are not met. This paper proposes BAXUS that leverages a novel family of nested random subspaces to adapt the space it opti- mizes over the problem. This ensures high performance while removing the risk of failure, which we assert via theoretical guarantees. A comprehensive eval- uation demonstrates that BAxUS achieves better results than the state-of-the-art methods for a broad set of applications.
Introduction
The optimization of expensive-to-evaauute black-box functions where derivative information is available has found many applications, for example in chemical engineering [11, 28, 31, 58, 60), materials science [23, 29, 30, 32, 52, 64, 68), aerospace engineering [39, 43], hyperparameter op- timization [5, 33, 38, 61], neural architecture search [36, 57], vehicle design [14, 34), hardware design [19, 49], drug discovery [51], robotics [12, 13, 41, 46, 54], and the life sciences [18, 59, 65]. Here increasing the number of dimensions (or parameters) of the optimization problem usually al- lows for better solutions. For example, by exposing more process parameters of chemical reaction, we obtain a more granular control the process; for design task, we may optimize a larger number of design decisions jointly; in robotics, we gain access more sophisticated control policies.
series of breakthroughs have recently pushed the envelope of tigh-dimmnssonal Bayesian opti- mization and facilitated wider adoption in science and engineering. The key challenge for further scaling the so-called curse of dimensionality. The complexity of the task finding an optimum grows exponentially with the number of dimensions [7, 22]. Recently, methods that rely local 'trust regions' have gained popularity. They usually achieve good performance for problems with up couple of dozen input parameters. However, observe that their performance degrades for higher-dimensionn problems. This is not surprising, given that trust regions have a smaller volume but still the full dimensionality of the problem. Other state-of-the-ar methods suppose the existence
The work was done before Matthias joined Amazon.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of a low- di--dmiensionl active subspace and enjoy great scalability if they find such space. The caveat that its existence usually not known for practical applications. Moreover, the user needs to "guess' good upper bound on its dimensionality to enjoy a good sample efficiency.
In this work, propose theoretically-foundee approach for high-dimensional Bayesian optimiza- tion, BAXUS (Bayesian optimization with adaptively expanding subspaces), that reliably achieves high performance on comprehensive of applications. BAXUS utilizes a family of nested embedded spaces to increase the dimensionality of the domain that it optimizes over as it collects more data. As byproduct, BAXUS can leverage an active subspace, if it exists, without requiring the user to "uess'' its dimensionality. BAXUS is based on a novel random linear subspace embed- ding that enables a more efficient optimization and has strong theoretical guarantees. We make the following contributions:
We develop BAXUS that reliably achieves excellent solutions on a broad set of high-dimensiooall tasks, outperforning the state-of-the-art.
2. We present a novel family of nested random embeddings that has the following properties: a) BAXUS' embedding provides larger worst-case guarantee for containing global optimum than the HESBO embedding proposed by [50]. b) The BAXUS embedding is an optimal sparse embedding, as defined in Def. 1. c) Its probability of containing an optimum converges to the one of the HESBO embedding as the input dimensionality D + oc.
3. We conduct a comprehensive evaluation on a representative collection of benchmarks that demon- strates that BAXUS outperforms the state-of-the-an methods.
The remainder of this paper is structured as follows. Section states the problem and discusses related work. Section 3 presents the BAXUS algorithm and the corresponding embedding. Section 4 evaluates BAXUS on a variety of benchmarks. We give concluding remarks in Section 5.
2 Background
The task is find a minimizer
x= arg min f(x), #Ex
where X' = 1-1, The objective function X E is an expensive-to- to-eluluate black- box function. Hence the number of function evaluations needed to find an optimizer is crucial. Evaluations may be subject to observational noise, i.c., f(x,) + with E; ~ ~ This work focuses on scalable high-dimensional Bayesian optimization, where the input dimensionality D is in the hundreds, and the sampling budget may comprise a thousand or more function evaluations.
Linear embeddings. A successful approach for HDBO is to assume the existence of an active subspace [17], i... there exist space C RRd with d, S D and function g : - R, such that for all a: g(Txx) (xx) where T E Rd. xD is projection matrix projecting æ onto 2 and de is the effective dimensionality of the problem. In practice, both d, and 2 are unknown.
REMBO (Random embedding BO) [71] and HESBO (Hashing-enhanned subspace BO) [50] try to capture this active subspace by randomly chosen linear subspace. Therefore, they generate a random projection matrix ST that maps from d-dimensional subspace y E IRd with d < D (the target space) to X. We call d the target dimensionality. For REMBO, each entry in ST is normally distributed. REMBO uses heuristic to determine hyperrectangle in ) that it optimizes over. Note that the bounded domain may not contain a point that maps to an optimizer of f. a risk aggravated by distortions introduced by the projection. [6, 8. 9] proposed ideas to mitigate the issue. HESBO's s random projection assigns one target dimension and sign (+1) to each input dimension. This embedding is inspired by the count-sketch algorithm [15] for estimating frequent items in data streams. The sparse projection matrix ST is binary except for the signs, and each row has exactly one non-zero entry. Even though this embedding avoids REMBO'S 's distortions, as the authors proved, it has a lower probability of containing the optimum [40]. ALEBO [40] uses a Mahalanobis kernel and imposes linear constraints on the acquisition function to avoid projecting outside of X.
Non-linear embeddings. Several works use autoencoders to learn non-linear spaces for optimiza- tion, trading in sample efficiency. Tripp et al. [67] change the training objective of a variational

---

autoencoder (VAE) [37] to make the target space more suitable for optimization. They give higher weight to berter-perfonming points when training the variational autoencoder (VAB) and show that this improves optimization. Moriconi et al. [47] incorporate the training of an autoencoder directly into the likelihood maximization of Gaussian process (GP) surrogate. The computational cost is cubic in the number of samples and the input dimension. Lu et al. [42] and Maus et al. [45] use autoencoders to learn embeddings of highly structured input spaces such as kernels or molecules. Other approaches include partial least squares [10] or sliced inverse regression [16].
High-dimensional BO in the input space. A popular approach to make HDBO in the input space feasible is trust regions (TRs) [22, 53, 55, 75]. The TuRBO algorithm [22] optimizes over bounded TRs instead of the global space, adapting their side lengths and the center points during the optimiza- tion process. By restricting function evaluations to trust regions, TuRBO addressed the problem of over-exploration; see [22] for details. Note that the TRs have full input dimensionality, which may impact TURBO's ' ability to scale to very large dimensions. Nonetheless, TURBO set a new state- of-the-art by scaling dozens input dimensions and thousands of function evaluations. Wan et al. [69] extended the idea of TRs to categorical and mixed spaces by using the Hamming dis- tance define the TR boundaries. SAASBO [20] uses sparse priors on the GP length scales which seems particularly valuable if the active subspace is axis-aligned. Indeed, SAASBO can outper- form TuRBO on certain benchmarks [20]. The cost of inference scales cubically with the number of function evaluations; thus, SAASBO is not expected to scale beyond small sampling budgets, which is confirmed by our experiments. Another line of research relies on the assumption that the input space has an additive structure [24, 35, 48, 72]. Additive GPs rely on computationally expen- sive sampling methods to learn decomposition of the input variables, which limits the scalability of such methods to problems of moderate dimensionalities and sampling budgets [22, 50]. Wang et al. [70] combined the meta-level algorithm LA-MCTS with TuRBO to improve optimization performance by learning hierarchical space partition.
In Sect. 4 we evaluate the performances of TURBO, SAASBO, ALEBO, and HESBO. Moreover, we study the popular CMA-ES [26] and random search [4].
3 The BAXUS algorithm
Wang et al. [71] showed that the REMBO embedding contains the optimum in the target space with probability one if d 2 de and if there are no bounds on the target and input spaces, i.e., )' = Rd and X' P For d < de. it is generally impossible to represent an optimum in X' for arbitrary I because S projects to a d-dimensional subspace in X. We call the probability of a target space to contain the optimum the success probubility. For d 2 de, there is a positive success probability that increases with [40, 71]. The main problem to set as small as possible to avoid the detrimental effects of the curse of dimensionality, while keeping it as large necessary to achieve a high probability for y containing an optimum.
In practice, the active subspace and its dimensionality are usually unknown. The performance of methods such as REMBO [71], HESBO [50], and ALEBO [40] depends on choosing d such that the success probability is high. Therefore, they implicitly rely on guessing the effective dimensionality de appropriately. We argue that choosing the target dimensionality is problematic in many practical applications. If chosen too small, the subspace cannot represent / sufficiently well. If it is chosen too large, the curse of dimensionality slows down the optimization.
The proposed algorithm, BAXUS, operates on target spaces of increasing dimensionality while pre- serving previous observations. Let dinit be the initial target dimensionality and m the total evaluation budget. BAXUS starts with a dime-nimeniio embedding that is increased over time until, after mp S m evaluations, it roughly reaches the input dimensionality D. With this strategy, we can leverage the efficiency of BO in low-dimensions spaces while guaranteeing to find an optimum in the limit. Increasing the target dimensionality is enabled by a novel embedding, which lets us carry over observations from previous, nower-dimension spaces. We further use a basba approach based on Eriksson et al. [22] to carry out optimization for high target dimensions effectively. BAXUS uses a GP surrogate [73] to model the function in the target space. Algorithm gives the pseudocode for BAXUS. Appendix B, we prove global convergence for BAXUS. We will now present the different components in detail.
target spaces into more high-dimensional target
3

---

Algorithm BAXUS
Input: b: new bins per dimension split, D: input dimension, mp evaluations by which the input dimension is reached.
Output: minimizer ax & arg men [(x)..
dg initial target dimensionality of the subspace given by Eq. (3).
2: Compute initial projection matrix ST y + X' by BAXUS embedding for D and do-
Sample initial data D {y) f f()Ty))), ... and fit the GP surrogate.
4: n. < O
5: while evaluation budget not exhausted do
6: + Linit
D Initialize the trust region
7: Calculate number of accepted "failures" as described
Sec. 3.4:
Tail
(1, (!TT {...
max
8:
while L > Limin and evaluation budget not exhausted do
9:
Find y by Thompson sampling TR, evaluate f(STy), and add to D.
10:
Re-fit the GP hyperparameters.
11:
Adjust trust region, see Section 3.2 for details.
12:
if' dn < D then
dn+1 f min (b + D). Increase ST by Algorithm 2.
14:
D See Appendix D
else
16:
Re-sample initial data and discard previous observations, d,+1 <- dn.
17:
18:
Return ST (arg mingeD y() or ST (arg minyeD [n(f(Sy)))
Return the best
observation in case observations without noise, or the best point according to posterior mean in case of noisy observations.
3.1 The sparse BAXUS subspace embedding
The BAXUS embedding uses a sparse projection matrix map from y to X. The number of non-zero entries in this matrix is equal to the input dimensionality D. Another embedding with this property is the HESBO embedding [50]. Given the and a target dimensionality d, HESBO samples target dimension (l.....d, d} and a sign E {+1} for each input dimension uniformly at random. Conversely, each target dimension has a set signed contributing input dimensions. We call the set of contributing input dimensions to target dimension bin. These relations implicitly define the embedding matrix E {0, (1, dx where each column has exactly one non-zero en- try [15]. In the HESBO embedding, the number of contributing input dimensions varies between 0 and D.
The interpretation of contributing input dimensions allows for an intuitive way to refine the embed- ding, which is shown in Figure 1. We update the embedding matrix such that contributing input dimensions of the target dimension are re-assigned to the current bin and b new bins. We then say that we split the corresponding target dimension. Importantly, this type of embedding allows for retaining observations (see Figure 1). Assume for example, that is the dimension to be split. The contributing input dimensions are re-assigned to yi and three new target dimensions yjs Mk. and y (here, b = 3); the observations can be retained by copying the value of the coordinate y/ to the coordinates Vj. yk. and y/. Thus, the observations are contained in the old and in the new target space. Algorithm describes the procedure in detail.
In the BAXUS embedding, we force each bin of a target dimension to have roughly the same num- ber of contributing input dimensions: the bin sizes differ by at most one. First, we create a random permutation of the input dimensions 1,.... ...., D. The list of input dimensions split into min (d, D) individual bins. If d does not divide D, not all bins can have the same size. We split the permutation of input dimensions such that the i-th bin has size DD/d] . i d DDd] S D. and D/d otherwise. The first bins have one additional element with this construction if d does not divide D. We further randomly assign a sign to each input dimension. The sign of the input dimensions and their assign- ment to target dimensions then implicitly define ST (see Figure 1). We now show that the BAXUS

---

Before Splitting
After Splitting
Input space
Target space
Input space
Target space
0
0.7
21
0.7
+1
0
+ 0.7
222
0.7
22
y1
0.7
ST=
0
+1
1/1
0.7
+ 0.3
233
0.3
1/2
0.3
0 -1
0.3
cdoy
0.3
274
0.3
354
y/3
0.3
0
0.3 375
split
0.3
Figure Observations are kept when increasing the target dimensionality. We give an example of the splitting method for D = 5 and d = 2. The first target dimension 11 has two contributing input dimensions, I1 and 22- 1/2 has three contributing input dimensions, 23. 24, and V5- By ST, point (0.7, 0.3)T in the target space is mapped to (-0.7, +0.7, -0.3, -0.3, -T.3)T in the input space. Assigning the fifth input dimension to a new target dimension and copying the function values from the second target dimension does not change the observation in the input space. The new ST is not shown but has one additional column with -1 the last row, and the last row of the second column is set to O.
embedding has strictly larger worst-case success probability than the HESBO embedding. We establish the following two definitions.
Definition (Sparse embedding matrix). A matrix S f0, +1]ØxD is sparse embedding matrix and only if each column in S has exactly one non-zero entry [74].
We formalize the event of "recovering an optimum" [40] as follows.
Definition 2 (Success of a sparse embedding). success of a random sparse embedding is the event Y* "All de active input dimensions are mapped to distinct target dimensions."
is important note that the definition of success is sufficient but necessary for the embedding to contain a global optimum. For example, the origin is a global optimum, then both embeddings contain it with probability one. In that sense, the above definition provides a worst-case guarantee. We refer to Definition 4 in Appendix A for formal definition of a sparse function. In Theorem 1, we give the worst-case success probability of the BAXUS embedding. All proof's have been deferred to Appendix A. Note that other than in the count-sketch algorithm [15], our hashing function is not pairwise independent. However, this does not affect our theoretical analysis.
Theorem 1 (Worst-case success probability of the BAXUS embedding). Let D be the input dimensionality and de the dimensionality of the embedding. Let Bemalt = D and Starge 1' be the small and large bin sizes. Then the probability of Y (see Definition 2) for the BAXUS embedding
Ene (d(1+ ( () (D-dBam)) ) 3mman P large
gda-i
D,d,d)
i
d.-i
(2.)
Figure 2 shows the worst-case success probabilities of the BAXUS and HESBO embeddings for three different settings of D. The worst-case success probability of the HESBO embedding is given by PH(Y ; d, de) = dl/((d - de )ldd)) (see [40] and Appendix A.3). is independent D but is shown for varying d-ranges different subplots. Except for when D > oc, the HESBO embedding always has a non-zer failure probability, i.c., of not containing given optimum. The BAXUS embedding ensures that the worst- case success probability is one for d = D. Discontinuities the curve of the BAXUS embedding occur due to the unequal bin sizes in the BAXUS embedding's 's worst-case success probability. The Figure is particularly striking when de is high: for
the r-axii, therefore the probabilities seem change between the
difference between the two embeddings example, for dg 20 HESBO requires d 1000 reach worst-case success probability of approximately 0.8, whereas the BAXUS embedding has a success probability of as soon as d = D. For finite D, HESBO's worst-case success probability is smaller than BAXUS' success probability.
Corollary 1. For D + oo, the worst-case success probability of the BAXUS embedding is
d!
lim P5(Y D de) = - -d-e))dd.
D-000
5

---

D=100, d.=20
D=500, d.=20
D=1000, d,=20
100
0.8
p(Y") D. d. de)
0.6
0.4
0.2
0.0
25
50
d 100 200
75
400
500
1000
d
BAxUS
HeSBO
Figure 2: The worst-case guarantees for the success probabilities p(Y'; D. d.) of the BAXUS and HESBO embeddings for different input dimensionatities, D=100 (left), D=500 (center), D=1000 (right), function of the target dimensionality d. The effective dimensionality is 20 The BAXUS embedding has higher worst-case success probability than the HESBO embedding. The improvement large for input dimensionalities in the low hundreds and still substantial for 1000D tasks. In accordance with the theoretical analysis, the difference vanishes as the input dimension D grows.
and hence matches HESBO's worst-case success probability Pu(Y" de).
We show that the BAXUS embedding is optimal among sparse embeddings.
Corollary 2. With the same input, target, and effective dimensionalities (D, d, and de), no sparse embedding has higher worst-case success probability than the BAXUS embedding.
3.2 Trust-region approach
Similar to TuRBO [22], BAXUS operates in trust regions (TRs). TRs hyper-rectangles in the input space. Their shape is determined by their base side length L and the GP length scales. The side length for each dimension is proportional the corresponding length scale of the GP kernel fitted to the data. The idea of this construction is that length scales indicate how quickly the function changes along the associated dimension. Thus, the TR is rescaled accordingly. The volume of TR is shrunk when TuRBO fails consecutive times to make progress, i.c., to find a better solution. If the algorithm consecutively makes progress for Teeeess 3 times, expands the TR. It restarts when the base side length L of the current TR falls below a threshold Luin = 2 2-7 In that case, it discards all observations for the TR and initializes a new TR on new samples. TRs enable TuRBO to focus on regions of the space close to the incumbent, i.e., the current best solution found by the algorithm. To choose the next evaluation point, TuRBO uses Thompson sampling [66], i.e., it draws realization of the GP set of candidate locations in the TR and then selects point of minimum sampled value.
TRs are an essential component of BAXUS because the target dimensionality usually grows expo- nentially during run of the algorithm. We use the same hyperparameter settings TuRBO [22] with the following modifications. First, we change the criterion for when to restart a TR. Instead of restarting TR when becomes too small, increase the target dimensionality by splitting each target dimension into several new bins unless BAXUS had already reached the input dimensionality. In this case, we reset the TR base side length the initial value and re-initialize the algorithm with new random set of initial observations. By resetting the base side length, we also avoid convergence to a particular local minimum as the covers large regions of the space again. TURBO solves this problem by allowing for multiple parallel TRs. Secondly, we change the number of accepted "failures" Tha such that BAXUS can roughly reach the input dimensionality in fixed number of evaluations as described in Section 3.4.

---

3.3 Splitting strategy
Starting in a low-dimensional embedded space, BAXUS successively grows the target dimension- ality to increase the probability of containing the optimum. By Corollary 2, it is optimal to keep the number of contributing imput dimensions in the target bins as equal as possible. At each split- ting point, BAXUS re-assigns the contributing input dimension of each target dimension. Hence the target dimensionality grows exponentially. The number of splits required to reach some input dimensionality D is logarithmic in D. Compared to the constant growth of the target dimensionality, BAxUS uses a larger evaluation budget in each split. The algorithm starts in target dimensional- ity dinit- After & splits, the target dimensionality is d2 dinic (b 1)a.
3,4 Controlling the number of accepted failures
BAXUS generally needs to reach high target dimensionalities to find the global optimum. As de- scribed in Section 3.2. BAXUS increases the target dimensionality when the TR base side length falls below the minimum threshold. For this to happen, the TR base length needs to be halved at
Luin times. Halving occurs if BAXUS consecutively fails Thail times in finding least k logg Lun
better function value. If, similarly to TuRBO, we set the number of accepted "failures" Thai to the current target dimensionality of the TR, we get the lower bound k- Thail on the number of function evaluations spent in that target dimensionality. This bound does not scale with the input dimension- ality D of the problem, i.e., the maximum target dimensionality is independent of D for fixed evaluation budget.
To enable BAXUS to reach any desired target dimensionality for the fixed evaluation budget, scale down Thail dependent on D, i.c., we adjust the lower bound. We choose to make it dependent on D as we guaranteed to find the global optimum if the final target space corresponds to the input space X' (see Appendix B). In contrast to imposing a hard limit on the number of function evaluations in target dimensionaliiy, scaling down the number of accepted "failures" has the advantage that we do not restrain BAXUS in cases where it finds better function values. The idea is to choose Thai dependent the current target dimensionality d: and such that BAXUS can reach any desired target dimensionality. For this, we assign a minimum evaluation budget m proportional to each target dimensionality d; such that Σ, m mp where mp is the evaluation budget until D is reached.
We calculate the number of splits n required to reach D by
D
D Rd diiit (b + 1)"h = n
logo+1
dini
with [-] indicating rounding to the nearest integer. The minimum evaluation budget for split is then found by multiplying mn with the "weight" of each target dimensionality: We assign each split a split budger m that is proportional to d,, such that Ei= m = mDD where my is the evaluation budget until D is reached:
de
b 1-mp- d; dnaal + 1) 1)
mf
MD
Σk=o
dx
Finally, we set the number Tia of accepted "failures" for the i-th target dimensionality d, such that (I) it just adheres to its split budget in the event that it never obtains a better function value, (2) is not larger than if we would use TURBO's choice, and (3) it is at least 1:
(1
m
Eail = max 1, min
.d.)
de
Setting the initial target dimension. Due to the rounding in Eq. (2) and the exponential growth of the target dimensionality, the final target dimensionality disic (b + 1)" might differ considerably from the input dimensionality D. This is undesirable as we might not reach 1) before depleting the
evaluation budget, or we might overestimate the evaluation budget for the final target dimensionality
d,. Therefore, we set the initial target dimensionality such that the final target dimensionality is as close to D as possible:
dami arg min | (b + 1)" DI,
(3)
(E(1.....b)
7

---

where n is given by Eq. (2). We note in passing that 1 I dam S b. An alternative to adjusting dam would be to fix the initial dg and adjust the growth factor
4 Experimental evaluation
In this section, we evaluate the performance of BAXUS on a 388D hyperparameter optimization task, a 124D design problem, and a collection of tasks that exhibit an active subspace. The BAXUS code is available at https: btttp:://itthb.. cot/LLoo///LLLAAUS
The experimental setup. We benchmark against TuRBO [22] with one and five trust regions, SAASBO [20], ALEBO [40], random search [4], CMA-ES [26], and HESBO [50], using the im- plementations provided by the respective authors with their settings, unless stated otherwise. For CMA-ES, we use the PYCMA [27] implementation. For HESBO and ALEBO, we use the Ax im- plementation [1]. To show the effect of different choices of d. we run HESBO and ALEBO with d = 10 and d = 20. We observed that ALEBO and SAASBO are constrained by their high runtime and memory consumption. The available hardware allowed up to 100 evaluations for SAASBO and 500 evaluations for ALEBO for each individual run. Larger sampling budgets higher target dimensions for ALEBO resulted in out-of-memory errors. We point out that limited scalability was expected for these two methods, whereas the other methods scaled to considerably larger budgets, as required for scalable BO. We initialize each optimizer, including BAXUS, with ten initial sam- ples and BAXUS with b 3 and mn 1000 and run 20 repeated trials. Plots show the mean performance with one standard error.
The benchmarks. We evaluate the selected algorithms six benchmarks that differ considerably in their characteristics. Following [71], we augment the BRANIN2 and HARTMANN6 functions with additional dummy dimensions that have no influence on the function value. We use the 388D SVM benchmark and the 124D soft-constraint version of the MOPTA08 benchmark proposed in [20]. We budget of 1000 evaluations for MOPTA08, BRANIN2, and HARTMANN6 and of 2000 evalua- tions for the other benchmarks. Moreover, we stopped for BRANIN2 and HARTMANNÓ when the simple regret dropped below ,001. We show results on additional noise-free benchmarks in Ap- pendices C.2 and C.3. We also tested the algorithms on the 300D LASSO-HIGH and the 1000D LASSO-HARI benchmarks from LASSOBENCH [59]. These benchmarks have an effective dimen- sionality of 5% of the input dimensionality, i.e., the LASSO-HIGH and LASSO-HARE benchmarks have 15 and 50 effective dimensions, respectively. To study the robustness to observational noise, we also tested on noisy variants of LASSO- HARD and LASSO-HIGH.
4.1 Experimental results
We begin with the six noise-free benchmarks. Fig. 3 summarizes the performances. On MOPTA08. a 124D vehicle design problem, SAASBO initially makes slightly faster progress than BAXUS, We suspect that this benchmark has high effective dimensionality. such that BAXUS first needs adapt the target dimensionality to make further progress. On the 388D SVM benchmark, BAXUS adapts to the appropriate target dimensionality where it can reach good function values faster than TURBO and CMA-ES. For this benchmark, Eriksson and Jankowiak [20] reported that SAASBO learned three active dimensions. Yet, the fact that ALEBO and HESBO seem to stagnate after a few hundred evaluations, while BAXUS, TURBO, and CMA-ES find better solutions, indicates that optimizing more of the 385 kernel length scales of the SVM benchmark allows for better solutions. On the 500D HARTMANN6, SAASBO performs best, closely followed by BAXUS. ALEBO and HESBO are competitive initially but converge to suboptimal solutions. HESBO, BAXUS, SAASBO, ALEBO all find excellent solutions on the BRANIN benchmark, with the latter algorithms converging faster.
Next, we examine the performances on the 1000D LASSO-HARI and the 300D LASSO-HIGH that exhibit active subspaces, here without observational noise. BAXUS achieves considerably better solutions than all state-of-thh-aar methods. We also note that TURBO and CMA-ES perform better than SAASBO and ALEBO. While one may expect BAXUS to outperform TURBO and CMA-ES on these tasks with high input dimensions, it is surprising that SAASBO, HESBO, and ALEBO are not able to benefit from the present active subspace. Here BAXUS's strategy to adaptively expand the nested subspace is superior. Another crucial observation that performances of BAXUS vary only slightly across runs. Thus, BAXUS is robust despite the stochastic construction of the
8

---

Mopta08
Branin2 (500D)
635
102
600
10:
0.175
350
107
Tuncton
025
0.125
10"
0.100
275
10a2
250
0.000
225
0.025
10-3
Lasso- Daaooor-rrrdl..o (1000D)
Esse--ligh (300D)
Barimannó (500D)
107
10
Jeggee
101
101-
10
500
1000
1500
2000
500
1000
1500
2000
200
4.00
600
800
1003
Number of function mnltuctions
Nember of function asslcations
Number of fonection ecalustions
BAXUS
TaRBO
Alebo (d-10 10)
HeSBO (d-10)
CMA ES
SaasBO
TuRBO-S
20)
(d-20)
Search
Figure 3: Top row: 124D MOPTA08 (): BAXUS obtains the best solutions, followed by TURBO and CMA-ES, 388D SvM (e): BAXUS outperforms the other methods from the start. 500D BRANIN (r): SAASBO. BAXUS, ALEBO, and HESBO find optimum: SAASBO and ALEBO converge fastest. Bottom row: 100D LASSO-HARD (I) and 300D LASSO-HIGH (c): BAXUS outperforms the baselines. SAASBO, ALEBO, and HESBO struggle. 500D HARTMANN6 (r):
SAASBO performs best, closely followed by BAXUS. The other methods show only slow progress stagnate.
Lasso-Hard, 1000D
Lasso-High, 300D
10
BAXUS
TuRBO
TuRBO-5
Regret
Regret
HeSBO (d-10)
HeSBO (d-20)
Aleho (d - 10)
(d
SaasBO
109
Random Search
Number of function evaluations
Number function evaluations
Figure 4: BAXUS outperforms the SOTA and in particular proves be robust to observational noise on the 1000D LASSO-HA -ARR (l) and the 300D LASSO-HEE HIGH (r). Note that CMA-ES performs considerably worse than on the noise-free versions of the benchmarks.
embedding, Across the broad collection of benchmarks, BAXUS is the only method to consistently achieve high performance.
Noisy benchmarks. We evaluate the algorithms also for tasks with observational noise. Fig. summarizes the results. We observe that BAXUS achieves considerably better solutions for any num- ber of observations than the competitors. Moreover, we note that the performances of SAASBO, CMA-ES, and HESBO (d = 20) degrade considerably on the LASSO-HIGH task compared to the noise-free formulation the task studied above. BAXUS' performance equally strong as for the noise-free case and keeps making progress after 1000 observations.

---

BAXUS embedding ablation study. To investigate whether the proposed family of nested ran- dom subspaces contributes the superior performance of BAXUS, we replaced the new embedding with similar family of nested HESBO embeddings. The results show that the proposed embedding provides a significant performance gain. Due space constraints, the results were moved Ap- pendix C.I.
5 Discussion
High-dimensional Bayesian optimization aspiring to unlock impactful applications broadly in science and industry. However, state-of-the-ar methods suffer from limited scalability in some cases, require practitioners to 'guss'' certain hyperparameters that critically impact the performance. This paper proposes BAXUS that works out-of-the- and achieves considerably better perfor- mance for high-dimensional problems, as the comprehensive evaluation shows. A key idea is to scale up the dimensionality of the target subspace that the algorithm optimizes over. We apply sim- ple strategy that we find to work well across the board. However, we expect substantial headroom in tailoring this strategy to specific applications, either using domain expertise or more sophisticated data-driven approach that, for example, learns suitable target space. Moreover, future work will explore extending BAXUS structured domains, particularly the combinatorial spaces common in materials sciences and drug discovery.
Societal impact. Bayesian optimization has recently become popular tool for tasks in drug dis- covery [51], chemical engineering [11, 28, 31, 58, 60]. materials science [23, 29, 30, 52, 64, 68], aerospace engineering [2, 39, 43], robotics [12, 13, 41, 46, 54]. and many more. This speaks to the progress that Bayesian optimization has made in becoming robust and reliable "off-the-shelf solver.' However, this promise is not yet fulfilled for the newer field of high-dimensional Bayesian optimization that allows optimization over hundreds of 'tunable levers.' The abovementioned appli- cations benefit from incorporating more such levers in the optimization: it allows for more detailed modeling of an aerospace design or more granular control of a chemical reaction, to give some examples. The evaluation shows that the performance of state-of-the-arr methods degenerates drasti- cally for such high dimensions if the application does not meet specific requirements. Adding insult to the injury, such requirements as the dimensionality of an active subspace cannot be determined beforehand.
The proposed algorithm achieves a robust performance over a broad collection of tasks and thus will become 'goto' optimizer for practitioners in other fields. Therefore, we released the BAXUS code.
Acknowledgments and Disclosure of Funding
Luigi Nardi was supported in part by affiliate members and other supporters of the Stanford DAWN project Ant Financial, Facebook, Google, Intel, Microsoft, NEC, SAP, Teradata, and VMware. Leonard Papenmeier and Luigi Nardi were partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. Luigi Nardi was partially supported by the Wallenberg Launch Pad (WALP) grant Dnr 2021.0348. The computations were also enabled by resources provided by the Swedish National Infrastructure for Computing (SNIC) at LUNARC, partially funded by the Swedish Research Council through grant agreement no. 2018-05973. We would like to thank Erik Hellsten from Lund University and Eddy de Weerd from the University Twente for valuable discussions.
10

---

References
[1] E. Bakshy, L. Dworkin, B. Karrer, K. Kashin, B. Letham, A. Murthy, and S. Singh. Ac: A domain-agnostic platform for adaptive experimentation. In Conference Neural Information Processing Systems, pages 1 1-8, 2018.
[2] R. Baptista and M. Poloczek. Bayesian optimization of combinatorial structures. In Interna- tional Conference on Machine Learning, pages 462-471. PMLR, 2018.
[3] E. Beckenbach and R. Bellman. Inequalities, volume 30. Springer Science Business Media, 2012.
[4] J. Bergstra and Y. Bengio. Random search for hyper- parammer optimization. Journal of machine learning research, 13(2), 2012.
[5] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for Hyper-Parameter Optimiza- tion. In Advances Neural Information Processing Systems (NeurIPS), volume 24. Curran Associates, Inc., 2011.
[6] M. Binois. Uncertainty quantification on Pareto fronts and high-dimensional strategies in Bayesian optimization, with applications in multi-objective automotive design. PhD thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2015.
[7] M. Binois and N. Wycoff. A survey high-dimensional Gaussian process modeling with application to Bayesian optimization. ACM Transactions on Evolutionary Learning and Opti- mization, 2(2):1 2022.
[8] M. Binois, D. Ginsbourger, and O. Roustant. A warped kernel improving robustness in Bayesian optimization via random embeddings. In International Conference on Learning and Intelligent Optimization (LION), pages 281 186. Springer, 2015.
[9] M. Binois, D. Ginsbourger, and Roustant. On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of global optimization, 76(1):69-90, 2020.
[10] M. A. Bouhlel, N. Bartoli, R. G. Regis, A. Otsmane, and J. Morlier. Efficient global optimiza- tion for high-dimensional constrained problems by using the Kriging models combined with the partial least squares method. Engineering Optimization, 50( 20228820033, 2018.
[11] B. Burger, P. M. Maffettone, V. V. Gusev, C. M. Aitchison, Y. Bai, X. Wang. X. Li, B. M. Alston, B. Li, R. Clowes, et al. A mobile robotic chemist. Nature, 583(7815):277-44, 2020.
[12] R. Calandra, N. Gopalan, A. Seyfarth, Peters, and M. Deisenroth. Bayesian Gait Optimiza- tion for Bipedal Locomotion. In P. M. Pardalos, M. G. Resende, C. Vogiatzis, and J. L. Wal- teros, editors, Learning and Intelligent Optimization, pages 274-290, Cham, 2014. Springer International Publishing.
[13] R. Calandra, A. Seyfarth, J. Peters, and M. P. Deisenroth. Bayesian optimization for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76(1):5-23, 2016.
[14] A. Candelieri, R. Perego, and F. Archetti. Bayesian Optimization of Pump Operations in Water Distribution Systems. Journal of Global Optimization, 71(1):213235, May 2018. ISSN 0925- 5001.
[15] M. Charikar, K. Chen, and M. Farach-Colton. Finding Frequent Items in Data Streams. In Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo, and M. Hennessy, editors, Automata, Languages and Programming, pages 693-703, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. ISBN 978-3-540-44465-4
[16] J. Chen, G. Zhu, C. Yuan, and Y. Huang. Semi-supervised Embedding Learning for High- dimensional Bayesian Optimization. arXiv preprint arXiv:2005. 14601, 2020.
[17] G. Constantine, Active Subspaces. Society for Industrial and Applied Mathematics, Philadel- phia, PA, 2015.

---

[18] Z. Cosenza, R. Astudillo, P. Frazier, K. Baar. and D. E. Block. Multi multi-Information Source Bayesian Optimization of Culture Media for Cellular Agriculture. Biotechnology and Bioengi- neering, 2022.
[19] A. Ejjeh, L. Medvinsky, A. Councilman, H. Nehra, S. Sharma, V. Adve, L. Nardi, E. Nurvi- tadhi, and R. A. Rutenbar. HPVM2FPGA: Enabling True Hardware- Agnostic FPGA Pro- gramming. In Proceedings of the 33rd IEEE International Conference Application-specijee Systems, Architectures, and Processors, 2022.
[20] D. Eriksson and M. Jankowiak. High-dimensional Bayesian optimization with sparse axis- aligned subspaces. In C. de Campos and M. H. Maathuis, editors, Proceedings of the Thirty- Seventh Conference on Uncertainly in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 493-503, PMLR, 27-30 Jul 2021.
[21] D. Eriksson and M. Poloczek. Scalable Constrained Bayesian Optimization. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics,, volume 130 of Proceedings of Machine Learning Research, pages 730-738. PMLR, 13-15 Apr 2021.
[22] D. Eriksson, M. Pearce, J. Gardner, R. D. Turner, and M. Poloczek. Scalable Global Optimiza- tion via Local Bayesian Optimization. In Advances in Neural Information Processing Systems (NeurIPS), pages 5496-5500 2019.
[23] P. I. Frazier and J. Wang. Bayesian Optimization for Materials Design, pages 45-75. Springer International Publishing, Cham, 2016. ISBN 978-3-319-23871-5.
[24] J. Gardner, C. Guo, K. Weinberger, R. Garnett, and R. Grosse. Discovering and exploiting addi- tive structure for Bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 1311-1319, 2017.
[25] R. L. Graham, D. E. Knuth, O. Patashnik, and S. Liu. Concrete mathematics: foundation for computer science. Computers in Physics, 3(5): 1989.
[26] N. Hansen and A. Ostermeier. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In Proceedings of IEEE International Conference on Evolutionary Computation (ICEC), pages 312-317, 1996.
[27] N. Hansen, Y. Akimoto, and P. Baudis. CMA-ES/pycma on Github. Zenodo, 21t:110.288//2modd.255566 Clause.
Feb. 2019, Last accessed: 05/09/2022. License: BSD-3-
[28] F. Hase, L. M. Roch, C. Kreisbeck, and A. Aspuru-Guzik. Phoenics: a Bayesian optimizer for chemistry, ACS central science, 4()): 134-1145, 2018.
[29] Häse, M. Aldeghi, R. J. Hickman, L. M. Roch, and A. Aspuru-Guzik. Gryffin: An algorithm for Bayesian optimization of categorical variables informed by expert knowledge. Applied Physics Reviews, 8(3):031406, 2021.
[30] H. C. Herbol, W. Hu, Frazier, P. Clancy, and M. Poloczek. Eflicient search of compositional space for hybrid organic- inorganic perovskites via Bayesian optimization. upj Computational Materials, 4(1):177,2018 2018.
[31] M. Hernández-Lobato
Requeima, E. O. Pyzer-Knaph and A. Aspuru-Guzin Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space. In Proceedings the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1470-1479 PMLR, 06-11 Aug 2017.
[32] 7. F. Hughes, M. A. Nguyen, J. Wang, Y. Liu, M. T. Swihart, M. Poloczek, P. I. Frazier, M. R. Knecht, and T. R. Walsh. Tuning materials-binding peptide sequences toward gold-and silver- binding selectivity with Bayesian optimization. ACS nano, (111):)18200182600 2021.
[33] C. Hvarfner, D. Stoll, A. Souza, L. Nardi, M. Lindauer, and F. Hutter. PiBO: Augmenting Ac- quisition Functions with User Beliefs for Bayesian Optimization. In International Conference on Learning Representations, 2022.
12

---

[34] D. R. Jones. Large-scale multi-disciplee disciplinary mass optimization in the auto industry. In MOPTA 2008 Conference (20 August 2008), 2008.
[35] K. Kandasamy, J. Schneider, and B. Póczos. High dimensional Bayesian optimisation and bandits via additive models. In International conference on machine learning (ICML), pages 295-304, 2015.
[36] K. Kandasamy, W. Neiswanger, J. Schneider, B. Poczos, and E. P. Xing. Neural Architec- ture Search with Bayesian Optimisation and Optimal Transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 31. Curran Associates, Inc., 2018.
[37] D. P. Kingma and M. Welling. Auto-Encoding Variational Bayes. In 2nd International Con- ference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Con- ference Track Proceedings, 2014.
[38] A. Klein, Falkner, Bartels, P. Hennig, and F. Hutter. Fast Bayesian Optimization of Ma- chine Learning Hyperparameters on Large Datasets. In A. Singh and J. Zhu, editors, Proceed- ings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 528-536. PMLR, 20-22 Apr 2017.
[39] R. LLm, M. Poloczek, P. Frazier, and K. E. Willcox. Advances in Bayesian optimization with applications in aerospace engineering. In 2018 AIAA Non -on-Deterministic Approaches Confer- ence, page 1656, 2018.
[40] B. Letham, R. Calandra, A. Rai, and E. Bakshy. Re-Examining Linear Embeddings for High- Dimensional Bayesian Optimization. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 1546-1558. Curran Associates, Inc., 2020.
[41] D. Lizotte, T. Wang, M. H. Bowling, D. Schuurmans, et al. Automatic Gait Optimization With Gaussian Process Regression. In IJCAI, volume 7, pages 944-949, 2007.
[42] X. Lu, J. Gonzalez, Z. Dai, and N. D. Lawrence. Structured Variationally Auto-encoded Opti- mization. J. G. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3273-3281. PMLR, 2018.
[43] T. W. Lukaczyk, P. Constantine, Palacios, and J. Alonso. Active subspaces for shape optimization. In 10th AIAA multidisciplinary design optimization conference, page 1171, 2014.
[44] A. W. Marshall, I. Olkin, and B. C. Arnold. Inequalities: theory of majorization and its applications, volume 143. Springer, 1979.
[45] N. Maus, H. T. Jones, J. S. Moore, M. J. Kusner, J. Bradshaw, and J. R. Gardner. Local latent space Bayesian optimization over structured inputs. arXiv, 2022.
[46] M. Mayr, Ahmad, K. I. Chatzilygeroudis, L. Nardi, and V. Krüger. Skill-based Multi- objective Reinforcement Learning of Industrial Robot Tasks with Planning and Knowledge Integration. CORR, abs/2203. 10033, 2022.
[47] R. Moriconi, M. P. Deisenroth, and K. Sesh Kumar. High-dimensional Bayesian optimiza- tion using low- dimensional feature spaces. Machine Learning, 109(9):1925-1) -993,, Sep 2020. ISSN 1573-0565.
[48] M. Mutny and A. Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. Advances in Neural Information Processing Systems, 31, 2018.
[49] L. Nardi, D. Koeplinger, and K. Olukotun. Practical design space exploration. In 2019 IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 347-358. IEEE, 2019.
[50] A. Nayebi, A. Munteanu, and M. Poloczek. A framework for Bayesian Optimization in Em- bedded Subspaces. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research (PMLR), pages 4762- PMLR, 09-15 Jun 2019.
13

---

[51] D. M. Negoescu, P. I. Frazier, and W. B. Powell. The Showledge-Gradienn Algorithm for Sequencing Experiments in Drug Discovery. INFORMS Journal on Computing, 23(3):346- 363, 2011.
[52] D. Packwood. Bayesian optimization for materials science. Springer.
[53] G. Pedrielli and S. H. Ng. G-STAR: A new kriging- trust region method for global optimization. In 2016 Winter Simulation Conference (WSC), pages 803-814. IEEE, 2016.
[54] A. Rai, R. Antonova, S. Song. W. Martin, Geyer, and C. 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.
[55] R. G. Regis. Trust regions in Kriging-basee based optimization with expected improvement. Engi- neering optimization, 48(6):1037-10533 2016.
[56] H. Robbins. A remark on stirling's formula. The American mathematical monthly, 62(1): 26-29, 1955.
[57] B. Ru, X. Wan, X. Dong, and M. Osborne. Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lchman Kernels. In International Conference on Learning Representationss 2021.
[58] A. M. Schweidtmann, A. D. Clayton, N. Holmes, F. Bradford, R. A. Bourne, and A. A. Lap- kin. Machine learning meets continuous flow chemistry: Automated optimization towards the Pareto front of multiple objectives. Chemical Engineering Journal, 352:277-282, 2018.
[59] K. Sehic, A. Gramfort, J. Salmon, and L. Nardi. LassoBench: A High-Dimensiona Hyperpa- rameter Optimization Benchmark Suite for Lasso. In First Conference on Automated Machine Learning (Main Track), 2022.
[60] B. J. Shields, J. Stevens, J. Li, M. Parasram, F. Damani, J. I. M. Alvarado, J. M. Janey, R. P. Adams, and A. G. Doyle. Bayesian reaction optimization as tool for chemical synthesis. Nature, 590(7844):89-96, 2021.
[61] J. Snoek, H. Larochelle, and R. P. Adams. Practical Bayesian Optimization of Machine Learn ing Algorithms. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[62] H. H. Sohrab. Basic real analysis, volume 231. Springer, 2003.
[63] J. Solis and R. J.-B. Wets. Minimization by Random Search Techniques. Mathematics of Operations Research, 6(1):19-30, 1981. ISSN 0364765X, 15265471.
[64] A. Souza, L. B. Oliveira, S. Hollatz, M. Feldman, K. Olukotun, J. M. Holton, A. E. Cohen, and L. Nardi. DeepFreak: Learning crystallography diffraction patterns with automated machine learning. arXiv preprint arXiv: 1DX.::1904.118.. 2019.
[65] I.. Tallorin, J. Wang, W. F. Kim, S. Sahu, N. M. Kosa, P. Yang. M. Thompson, M. K. Gilson, Frazier, M. Burkart, et al. Discovering de novo peptide substrates for enzymes using machine learning. Nature communications, 9(1):1-10, 2018.
[66] W. R. Thompson. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3/4):255-294, 1933. ISSN 00063444.
[67] A. Tripp, E. Daxberger, and J. M. Hernández-Lobato. Latent Space of Deep Generative Models via Weighted Retraining. In H. Larochelle, M. Ran- zato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 11259-11227 1272. Curran Associates, Inc., 2020.
Cample-Efficient Optimization in the
[68] T. Ueno, T. D. Rhone, Z. Hou, T. Mizoguchi, and K. Tsuda. COMBO: An efficient Bayesian optimization library for materials science. Materials Discovery, 4:18-21, 2016. ISSN 2352- 9245.
14

---

[69] X. Wan, V. Nguyen, H. Ha, B. Ru, C. Lu, and M. A. Osborne. Think Global and Act Lo- cal: Bayesian Optimisation over High-Ding Sige-Dimensional Categorical and Mixed Search Spaces. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 10663-10674. PMIR, 18-24 Jul 2021.
[70] L. Wang, R. Fonseca, and Y. Tian, Learning search space partition for black- box optimization using monte carlo tree search. Advances in Neural Information Processing Systems, 33:19511- 19522, 2020.
[71] Z. Wang, F. Hutter, M. Zoghi, D. Matheson, and N. de Feitas. Bayesian optimization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research (JAIR), 55:361-387, 2016.
[72] Z. Wang, C. Gehring, P. Kohli, and S. Jegelka. Batched large-scale Bayesian optimization in high-dimensional spaces. International Conference on Artificial Intelligence and Statistics, pages 745-754, 2018.
[73] C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
[74] D. P. Woodruff et al. Sketching as tool for numerical linear algebra. Foundations and Trends@ in l'heoretical Computer Science, 1011-2)11-177 2014.
[75] Zhou, Z. Yang, Y. Si, L. Kang, H. Li, M. Wang, and Z. Zhang. A trust-region parallel Bayesian optimization method for simulation-driven antenna design. IEEE Transactions on Antennas and Propagation, 69(7):3966-399) 2020.
15

---

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 descrihe the limitations of your work? [Yes] See Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 5.
(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]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix E.
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? [Yes] See Appendix E.
(b) Did you mention the license of the assets? [Yes] See Appendix E.
(c) Did you include any assets either in the supplemental material URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
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, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "Vo2t56KB97W", "reviewer": "Reviewer_355n", "summary": "The paper considers Bayesian optimization for sparse, axis-aligned functions over high-dimensional spaces (hundreds of dims). The proposed solution creates a lower-dimensional space by sub-selecting dimensions from the original input space. The lower-dimensional space is searched with Thompson sampling and trust regions. The dimensionality of the lower-dimensional space is increased over the course of the proposed algorithm. The paper shows that the probability of containment of the function's optimum by the proposed algorithm's lower-dimensional space is no worse than a recent high-dimensional Bayesian optimization approach, also for sparse, axis-aligned functions (HESBO). Further, a total input evaluation budget is appropriately split among the sequence of nested lower-dimensional spaces. The paper provides results on high-dimensional datasets.", "questions": "* Why is REMBO not included in the experimental comparison?\n\n* What is random in the \"random embedding\" Alg 2?\n\n* To what extent can the assumption of axis-aligned function be relaxed?", "limitations": "The paper does cover limitations and societal impacts to some degree in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n\n* The nested lower-dimensional spaces is a neat idea. I wish this direction was explored/pushed further in the paper.\n\nQuality\n\n* It wasn't obvious to me why REMBO was not included in the experimental comparison as it seems to be a natural competitor in this setting.\n\nClarity\n\n* The setup and algorithm description are generally clear. Some of the choices described in the splitting strategy, fail tolerance control, and initial target dimension weren't immediately intuitive. I couldn't parse the extent to which these were necessary for the proposed algorithm's effectiveness over competitors.\n\nSignificance\n\n* The general setting of high-dimensional black-box optimization is clearly important and effective general algorithms in this setting would be valuable for the community. The assumption of the function being axis-aligned is a strong one however.", "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": "K6TIMmwros", "reviewer": "Reviewer_4wPG", "summary": "The paper proposes to apply a simple adaptive dimensional reduction technique on Trust Region Bayesian Optimization (TuRBO) for high dimensional Bayesian optimization task which has low effective dimensionality. The algorithm improves the probability of containing the optimum in the embedding space over previous work Hashing-enhanced Subspace BO (HESBO) by enforcing the hashing from the input dimension to the low-dimensional embedding to be evenly distributed. The paper demonstrates the efficacy of the proposed algorithm with a comprehensive empirical study.", "questions": "1. I might have missed the part. How many independent trails are conducted for each algorithm during experiment?\n2. Could you provide results on the 60D Rover trajectory planning task that has been tested in TuRBO original experiment? I believe the task is available here https://github.com/zi-w/Ensemble-Bayesian-Optimization.\n", "limitations": "Not applied.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- ***Strengths***:\n1. Well-motivated algorithm design with the theoretical guarantee of its optimality over the existing HESBO in terms of probability of containing the optimal candidate in its embedding.\n2. The proposed embedding is well-integrated into the existing HDBO framework TuRBO with appropriate algorithmic modification. Ablation studies prove the efficacy of each part of the proposed algorithm. Theoretical analysis in the appendix also shows that it inherits TuRBO's convergency. \n\t\n- ***Weaknesses***:\n1. Some of the definitions and concepts are confusing. In lines 59-62, the definition of the active subspace seems to be incomplete.  If for all x, z = f(x), g(z) = z, then the effective dimensionality could always be 1 regardless of the structure of X. I suggest defining the subspace as in definition 1 of the REMBO paper which defines the effective subspace and effective dimensionality. For definition in lines 157 - 162, could the author specify the reference? The classical definition of count-sketch structure assumes the pair-wise independence of the hashing functions [Charikar et al. 2002]. This is how HESBO implements its dimension reduction.\n\t\t\n2. The classical count-sketch techniques rely on the pair-wise independencies of the hashing functions assigning input dimensions to different bins and the four-wise independencies of the sign assignment function as mentioned. The HESBO chooses the uniform random hashing which follows the assumption. The independency of hashing seems to be violated when BAxUS enforces that the input dimensions be evenly distributed to bins. Therefore, the original theoretical guarantee of the count-sketch structure probably does not hold in this case. The paper doesn't inherit the independency assumption on its count-sketch definition and lacks a discussion on this violation of independency of the hashing function.  \nIn practice the violation of independency might not hurt much as in expectation HESBO also distributes the input dimensions evenly to target dimensions and the downstream performance of the proposed embedding is strong. However, the missing independency downgrades the theoretical contribution of the paper due to its violation of classic count-sketch structure and lacks a discussion on it, especially when considering that the work is motivated to improve upon HESBO while doesn't inherit its advantage strictly.\n\t\n3. As far as I know TuRBO doesn't work well sometimes when only one trust region is operating and that motivates the TuRBO-m which is the m-trust-region variant of TuRBO (TuRBO-1) in the original paper. BAxUS lacks discussion over this problem. I expect a brief discussion over its choice of m and the corresponding implementation. \n\n4. The descriptions could be confusing as the notations are not well specified between line 138 and line 147. And deferring algorithm 2, which is a critical part of the algorithm, to the appendix might not be a good choice.\n\n*Reference*:\nCharikar, M., Chen, K. and Farach-Colton, M., 2002, July. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming (pp. 693-703). Springer, Berlin, Heidelberg.\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": "BP_Hd0g3QpH", "reviewer": "Reviewer_qmcj", "summary": "This paper proposes BaXus, which extends TRBO (trust region Bayesian optimization), by using not just trust regions but a linear embedding of varying dimensionality. The linear embedding is constructed via a count-sketch style embedding that produces effectively bins of data in each region of the input space. The dimensionality of the embedding can grow or shrink as part of the TRBO procedure, much like how in standard TRBO, the bounds of the space can change.", "questions": "What kind of interpolations are used for the lines in Fig. 2? They seem to not be linear?\n\nIs it possible to construct a situation where the Baxus embedding has either worse or the exact same success probability as HesBO? I know they converge in the limit but is there another situation where they can match?\n\nFig. 7: why is most of the improvement from BaxUs mostly at the beginning?\n\nL763: what is a top hat prior?\n\nFigs. 3 and 4: why do many of the Alebo and SAASBO evaluations seem to end early? Is this due to the increased cost of MCMC fitting? \n\n-\tFor example, Fig. 4 right: SAASBO seems to be cut at 100 evaluations rather than the 1000 evaluations fo the other methods. Also on hartmann500.\n\nL260: \\citet for [63]. \n\nL764: By ARD kernel, do you mean RBF ARD kernel or a Matern family?\n\nL770: Why so many random restarts for the GP fitting? Is this done for the TRBO and/or SAASBO models as well?\n\n", "limitations": "Mostly yes. Negative societal impliations of BayesOpt (e.g. weapons or bioweapons design) could also be mentioned. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: \nThis approach is a pretty clever combination of TRBO and embedding based approaches for high dimensional Bayes Opt. However, it ends up being very building block based, which isn’t necessarily a bad thing.\n\nComputing the success probability of the embedding and tying the primary idea back to well studied count sketch techniques does seem to be original to me.\n\nQuality:\n\nThe experimental evaluation and ablation studies do seem to be performed of a reasonably high quality and the plots are quite easy to parse.\n\nThe one set of high dimensional BayesOpt benchmarks that is probably missed in the experimental evaluation is that of LaMCTS (Wang et al, ’20), which uses a classifier to construct the trust regions for TRBO. It might be too much to ask for a comparison using BaxUs inside, but it seems like a fair comparison to use against standard TRBO + LaMCTS. \n\n-\tLaMCTS also has a slightly distinct and more interesting set of benchmarks which use MuJoCo environments, which are somewhat more interesting than simply adding dimensions into test problems like Branin.\n\nFig. 5 is very nice to see and seems to convincingly demonstrate that the Baxus embeddings perform better downstream than the HesBO embeddings, even inside of TRBO. \n\nClarity:\n\nIt’s really nice that the probability of computing the optimum is computable for this approach, even if it’s a bit more complicated than the HesBO expression.\n\nThe plots and writing are overall easy to parse. \n\nHowever, the error bars and the marks (e.g. triangles) on the plots are confusing to me. What are they and what do they represent?\n\nSignificance:\n\nBetter methods for high dimensional black box optimization are definitely quite significant and core to the NeuriPS community. \n\nI would have liked to have seen a more challenging benchmark task, such as control of MuJoCo environments (see quality comment). \n\nReferences:\n\nWang, L., Fonseca, R., and Tian, Y. (2020). Learning search space partition for black-box\noptimization using monte carlo tree search. In Advances in Neural Information Processing\nSystems, volume 33.\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": {}}]

Author rebuttal:

Decision: Accept