# Increasing the Scope as You Learn:
Adaptive Bayesian Optimization in Nested Subspaces

Leonard Papenmeier
Lund University
<EMAIL_ADDRESS>
Luigi Nardi
Lund University, Stanford University, DBtune
<EMAIL_ADDRESS>
Matthias Poloczek
Amazon
San Francisco, CA 94105, USA
<EMAIL_ADDRESS>
The work was done before Matthias joined Amazon.

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

##  1 Introduction

The optimization of expensive-to-evaluate black-box functions where no
derivative information is available has found many applications, for example,
in chemical engineering [31, 60, 28, 58, 11], materials science [68, 23, 52,
64, 30, 29, 32], aerospace engineering [43, 39], hyperparameter optimization
[61, 38, 5, 33], neural architecture search [36, 57], vehicle design [34, 14],
hardware design [49, 19], drug discovery [51], robotics [41, 13, 54, 12, 46],
and the life sciences [65, 59, 18]. Here increasing the number of dimensions
(or parameters) of the optimization problem usually allows for better
solutions. For example, by exposing more process parameters of a chemical
reaction, we obtain a more granular control of the process; for a design task,
we may optimize a larger number of design decisions jointly; in robotics, we
gain access to more sophisticated control policies.

A series of breakthroughs have recently pushed the envelope of high-
dimensional Bayesian optimization and facilitated a wider adoption in science
and engineering. The key challenge for further scaling is the so-called curse
of dimensionality. The complexity of the task of finding an optimum grows
exponentially with the number of dimensions [7, 22]. Recently, methods that
rely on local ’trust regions’ have gained popularity. They usually achieve
good performance for problems with up to a couple of dozen input parameters.
However, we observe that their performance degrades for higher-dimensional
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-
art methods suppose the existence of a low-dimensional active subspace and
enjoy great scalability if they find such a space. The caveat is that its
existence is usually not known for practical applications. Moreover, the user
needs to ‘guess’ a good upper bound on its dimensionality to enjoy a good
sample efficiency.

In this work, we propose a theoretically-founded approach for high-dimensional
Bayesian optimization, BAxUS (Bayesian optimization with adaptively expanding
subspaces), that reliably achieves a high performance on a comprehensive set
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 a byproduct, BAxUS can leverage an active subspace, if it exists,
without requiring the user to ’guess’ its dimensionality. BAxUS is based on a
novel random linear subspace embedding that enables a more efficient
optimization and has strong theoretical guarantees. We make the following
contributions:

  1. 1.

We develop BAxUS that reliably achieves excellent solutions on a broad set of
high-dimensional tasks, outperforming the state-of-the-art.

  2. 2.

We present a novel family of nested random embeddings that has the following
properties: a) The BAxUS embedding provides a larger worst-case guarantee for
containing a 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\rightarrow\infty$.

  3. 3.

We conduct a comprehensive evaluation on a representative collection of
benchmarks that demonstrates that BAxUS outperforms the state-of-the-art
methods.

The remainder of this paper is structured as follows. Section 2 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 to find a minimizer

$\bm{x}^{*}\in\operatorname*{arg\,min}_{\bm{x}\in\mathcal{X}}f(\bm{x}),$

where $\mathcal{X}=[-1,+1]^{D}$. The objective function
$f:\mathcal{X}\rightarrow\mathbb{R}$ is an expensive-to-evaluate black-box
function. Hence the number of function evaluations needed to find an optimizer
is crucial. Evaluations may be subject to observational noise, i.e.,
$f(\bm{x}_{i})+\varepsilon_{i}$, with
$\varepsilon_{i}\sim\mathcal{N}(0,\sigma^{2})$. 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.e., there exist a space
$\mathcal{Z}\subseteq\mathbb{R}^{d_{e}}$, with $d_{e}\leq D$ and a function
$g:\mathcal{Z}\rightarrow\mathbb{R}$, such that for all $\bm{x}$:
$g(T\bm{x})=f(\bm{x})$ where $T\in\mathbb{R}^{d_{e}\times D}$ is a projection
matrix projecting $\bm{x}$ onto $\mathcal{Z}$ and $d_{e}$ is the _effective
dimensionality_ of the problem. In practice, both $d_{e}$ and $\mathcal{Z}$
are unknown.

REMBO (Random embedding BO) [71] and HeSBO (Hashing-enhanced subspace BO) [50]
try to capture this active subspace by a randomly chosen linear subspace.
Therefore, they generate a random projection matrix $S^{\intercal}$ that maps
from a $d$-dimensional subspace $\mathcal{Y}\in\mathbb{R}^{d}$ with $d\ll D$
(the _target space_) to $\mathcal{X}$. We call $d$ the _target
dimensionality_. For REMBO, each entry in $S^{\intercal}$ is normally
distributed. REMBO uses a heuristic to determine a hyperrectangle in
$\mathcal{Y}$ 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 random projection assigns one target dimension and sign
($\pm 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 $S^{\intercal}$ is binary except for the signs, and
each row has exactly one non-zero entry. Even though this embedding avoids
REMBO’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
$\mathcal{X}$.

#### Non-linear embeddings.

Several works use autoencoders to learn non-linear spaces for optimization,
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 better-performing points when
training the variational autoencoder (VAE) and show that this improves
optimization. Moriconi et al. [47] incorporate the training of an autoencoder
directly into the likelihood maximization of a 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
[55, 53, 22, 75]. The TuRBO algorithm [22] optimizes over bounded TRs instead
of the global space, adapting their side lengths and the center points during
the optimization 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 to dozens on 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 distance to 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 outperform 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 [35, 24, 72, 48]. Additive GPs rely on
computationally expensive sampling methods to learn a decomposition of the
input variables, which limits the scalability of such methods to problems of
moderate dimensionalities and sampling budgets [50, 22]. Wang et al. [70]
combined the meta-level algorithm LA-MCTS with TuRBO to improve optimization
performance by learning a 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 an optimum in the
target space with probability one if $d\geq d_{e}$ and if there are no bounds
on the target and input spaces, i.e., $\mathcal{Y}=\mathbb{R}^{d}$ and
$\mathcal{X}=\mathbb{R}^{D}$. For $d<d_{e}$, it is in general impossible to
represent an optimum in $\mathcal{X}$ for arbitrary $f$ because $S$ projects
to a $d$-dimensional subspace in $\mathcal{X}$. We call the probability of a
target space to contain the optimum the _success probability_. For $d\geq
d_{e}$, there is a positive success probability that increases with $d$ [40,
71]. The main problem is to set $d$ sufficiently small to avoid the
detrimental effects of the curse of dimensionality, while keeping it as large
as necessary to achieve a high probability that $\mathcal{Y}$ contains 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 $d_{e}$
appropriately. We argue that choosing the target dimensionality is problematic
in many practical applications. If chosen too small, the subspace cannot
represent $f$ sufficiently well. If it is chosen too large, the curse of
dimensionality slows down the optimization.

Algorithm 1 BAxUS

1:$b$: new bins per dimension split, $D$: input dimension, $m_{D}$: #
evaluations by which the input dimension is reached.

2:minimizer
$\bm{x}^{*}\in\operatorname*{arg\,min}_{\bm{x}\in\mathcal{X}}f(\bm{x})$.

3:$d_{0}$ $\leftarrow$ initial target dimensionality of the subspace given by
Eq. (4).

4:Compute initial projection matrix
$S^{\intercal}:\mathcal{Y}\rightarrow\mathcal{X}$ by BAxUS embedding for $D$
and $d_{0}$.

5:Sample initial data
$\mathcal{D}=\\{(\bm{y}_{1},f(S^{\intercal}\bm{y}_{1})),\ldots\\}$ and fit the
GP surrogate.

6:$n\leftarrow 0$

7:while evaluation budget not exhausted do

8: $L\leftarrow L_{\textrm{init}}$ $\triangleright$ Initialize the trust
region

9: Calculate number of accepted “failures” as described in Sec. 3.4:
$\tau_{\textrm{fail}}^{s}\leftarrow\max\left(1,\min\left(\left\lfloor\frac{m_{i}^{s}}{k}\right\rfloor,d_{n}\right)\right)$

10: while $L>L_{\min}$ and evaluation budget not exhausted do

11: Find $\bm{y}$ by Thompson sampling in TR, evaluate
$f(S^{\intercal}\bm{y})$, and add to $\mathcal{D}$.

12: Re-fit the GP hyperparameters.

13: Adjust trust region, see Section 3.2 for details.

14: if $d_{n}<D$ then

15: $d_{n+1}\leftarrow\min(d_{n}\cdot{}(b+1),D)$.

16: Increase $S^{\intercal}$ by Algorithm 2.$\triangleright$ See Appendix D

17: else

18: Re-sample initial data and discard previous observations,
$d_{n+1}\leftarrow d_{n}$.

19: $n\leftarrow n+1$

20:Return
$S^{\intercal}(\operatorname*{arg\,min}_{\bm{y}\in\mathcal{D}}f(S^{\intercal}\bm{y}))$
or
$S^{\intercal}(\operatorname*{arg\,min}_{\bm{y}\in\mathcal{D}}\mathbb{E}_{n}[f(S^{\intercal}\bm{y})])$.
$\triangleright$ Return the best observation in case of observations without
noise, or the best point according to posterior mean in case of noisy
observations.

The proposed algorithm, BAxUS, operates on target spaces of increasing
dimensionality while preserving previous observations. Let $d_{\textrm{init}}$
be the initial target dimensionality and $m$ the total evaluation budget.
BAxUS starts with a $d_{\textrm{init}}$-dimensional embedding that is
increased over time until, after $m_{D}\leq m$ evaluations, it roughly reaches
the input dimensionality $D$. With this strategy, we can leverage the
efficiency of BO in low-dimensional 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, lower-
dimensional target spaces into more high-dimensional target spaces. We further
use a TR-based 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 1 gives the
pseudocode for BAxUS. In Appendix B, we prove global convergence for BAxUS. We
will now present the different components in detail.

###  3.1 The sparse BAxUS subspace embedding

The BAxUS embedding uses a sparse projection matrix to map from $\mathcal{Y}$
to $\mathcal{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 $D$ and a target dimensionality $d$, HeSBO
samples a target dimension in $\\{1,\ldots,d\\}$ and a sign $\\{\pm 1\\}$ for
each input dimension uniformly at random. Conversely, each target dimension
has a set of signed contributing input dimensions. We call the set of
contributing input dimensions to a target dimension a _bin_. These relations
implicitly define the embedding matrix $S\in\\{0,\pm 1\\}^{d\times D}$, where
each column has exactly one non-zero entry [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 embedding, which is shown in Figure 1.

$S^{\intercal}=$${-1}$${0}$${+1}$${0}$${0}$${+1}$${0}$${-1}$${0}$${-1}$$\left(\vbox{\hrule
height=37.14246pt,depth=37.14246pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=37.14246pt,depth=37.14246pt,width=0.0pt}\right)$Input spaceBefore
SplittingTarget space\- 0.7\+ 0.7\+ 0.3\- 0.3\-
0.3$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$y_{1}$$y_{2}$split0.70.3Input
spaceAfter SplittingTarget space\- 0.7\+ 0.7\+ 0.3\- 0.3\-
0.3$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$y_{1}$$y_{2}$$y_{3}$0.70.30.3copy

Figure 1: 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 $y_{1}$ has two contributing input dimensions, $x_{1}$ and $x_{2}$.
$y_{2}$ has three contributing input dimensions, $x_{3}$, $x_{4}$, and
$x_{5}$. By $S^{\intercal}$, a point $(0.7,0.3)^{\intercal}$ in the target
space is mapped to $(-0.7,+0.7,+0.3,-0.3,-0.3)^{\intercal}$ 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 $S^{\intercal}$ is not shown but
has one additional column with $-1$ in the last row, and the last row of the
second column is set to 0.

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 $y_{i}$ is the dimension to be split. The contributing input
dimensions are re-assigned to $y_{i}$ and three new target dimensions $y_{j}$,
$y_{k}$, and $y_{l}$ (here, $b=3$); the observations can be retained by
copying the value of the coordinate $y_{i}$ to the coordinates $y_{j}$,
$y_{k}$, and $y_{l}$. Thus, the observations are contained in the old and in
the new target space. Algorithm 2 describes the procedure in detail.

In the BAxUS embedding, we force each bin of a target dimension to have
roughly the same number of contributing input dimensions: the bin sizes differ
by at most one. First, we create a random permutation of the input dimensions
$1,\ldots,D$. The list of input dimensions is 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 $\lceil D/d\rceil$, if $i+d\lfloor D/d\rfloor\leq D$, and $\lfloor
D/d\rfloor$ 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 assignment to
target dimensions then implicitly define $S^{\intercal}$ (see Figure 1). We
now show that the BAxUS embedding has a strictly larger worst-case success
probability than the HeSBO embedding. We establish the following two
definitions.

######  Definition 1 (Sparse embedding matrix).

A matrix $S\in\\{0,\pm 1\\}^{d\times D}$ is a _sparse embedding matrix_ if 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).

A success of a random sparse embedding is the event $Y^{*}=$ “All $d_{e}$
active input dimensions are mapped to distinct target dimensions.”

It is important to note that the definition of a success is sufficient but not
necessary for the embedding to contain a global optimum. For example, if 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 a formal definition of a sparse
function. In Theorem 1, we give the worst-case success probability of the
BAxUS embedding. All proofs 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 $d\geq d_{e}$ the dimensionality of
the embedding. Let
$\beta_{\textrm{small}}=\left\lfloor\frac{D}{d}\right\rfloor$ and
$\beta_{\textrm{large}}=\left\lceil\frac{D}{d}\right\rceil$ be the small and
large bin sizes. Then the probability of $Y^{*}$ (see Definition 2) for the
BAxUS embedding is

$p_{B}(Y^{*};D,d,d_{e})=\frac{\sum_{i=0}^{d_{e}}\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}\beta_{\textrm{small}}^{i}\beta_{\textrm{large}}^{d_{e}-i}}{\binom{D}{d_{e}}}.$
(1)

Figure 2 shows the worst-case success probabilities of the BAxUS and HeSBO
embeddings for three different settings of $D$.

svg-inkscape/success_probabilities_svg-tex.pdf_tex

Figure 2: The worst-case guarantees for the success probabilities
$p(Y^{*};D,d,d_{e})$ of the BAxUS and HeSBO embeddings for different input
dimensionalities, $D{=}100$ (left), $D{=}500$ (center), $D{=}1000$ (right), as
a function of the target dimensionality $d$. The effective dimensionality is
$d_{e}{=}20$. The BAxUS embedding has a higher worst-case success probability
than the HeSBO embedding. The improvement is 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.

The worst-case success probability of the HeSBO embedding is given by
$p_{H}(Y^{*};d,d_{e})=d!/((d-d_{e})!d^{d_{e}})$ (see [40] and Appendix A.3).
It is independent of $D$ but is shown for varying $d$-ranges on the $x$-axis,
therefore the probabilities seem to change between the different subplots. The
BAxUS embedding ensures that the worst-case success probability is one for
$d=D$. Discontinuities in the curve of the BAxUS embedding occur due to the
unequal bin sizes in the BAxUS embedding’s worst-case success probability. The
difference between the two embeddings in Figure 2 is particularly striking
when $d_{e}$ is high: for example, for $d_{e}=20$ HeSBO requires $d=1000$ to
reach a worst-case success probability of approximately $0.8$, whereas the
BAxUS embedding has a success probability of $1$ as soon as $d=D$. For finite
$D$, HeSBO’s worst-case success probability is smaller than BAxUS’ success
probability.

######  Corollary 1.

For $D\rightarrow\infty$, the worst-case success probability of the BAxUS
embedding is

$\lim_{D\rightarrow\infty}p_{B}(Y^{*};D,d,d_{e})=\frac{d!}{(d-d_{e})!d^{d_{e}}},$
(2)

and hence matches HeSBO’s worst-case success probability
$p_{H}(Y^{*};d,d_{e})$.

We show that the BAxUS embedding is optimal among sparse embeddings.

######  Corollary 2.

With the same input, target, and effective dimensionalities ($D$, $d$, and
$d_{e}$), no sparse embedding has a 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 are 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 to 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 a TR is shrunk when TuRBO fails
$\tau_{\textrm{fail}}$ consecutive times to make progress, i.e., to find a
better solution. If the algorithm consecutively makes progress for
$\tau_{\textrm{success}}=3$ times, it expands the TR. It restarts when the
base side length $L$ of the current TR falls below a threshold
$L_{\min}\coloneqq 2^{-7}$. In that case, it discards all observations for the
TR and initializes a new TR on new samples. TR 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 a realization of the GP on a set of
candidate locations in the TR and then selects a point of minimum sampled
value.

TR are an essential component of BAxUS because the target dimensionality
usually grows exponentially during a run of the algorithm. We use the same
hyperparameter settings as TuRBO [22] with the following modifications. First,
we change the criterion for when to restart a TR. Instead of restarting a TR
when it becomes too small, we increase the target dimensionality by splitting
each target dimension into several new bins unless BAxUS has already reached
the input dimensionality. In this case, we reset the TR base side length to
the initial value and re-initialize the algorithm with a new random set of
initial observations. By resetting the base side length, we also avoid
convergence to a particular local minimum as the TR 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”
$\tau_{\textrm{fail}}$, such that BAxUS can roughly reach the input
dimensionality in a 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 dimensionality to increase the probability of containing an optimum. By
Corollary 2, it is optimal to keep the number of contributing input dimensions
in the target bins as equal as possible. At each splitting point, the target
dimensionality grows exponentially. The number of splits required to reach
some input dimensionality $D$ is logarithmic in $D$. BAxUS uses a larger
evaluation budget in each split. Suppose that the algorithm starts in target
dimensionality $d_{\textrm{init}}$. Then, after $k$ splits, the target
dimensionality is $d_{k}=d_{\textrm{init}}(b+1)^{k}$.

###  3.4 Controlling the number of accepted failures

BAxUS needs to be able to reach high target dimensionalities to find a global
optimum. As described 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 least
$k=\left\lfloor\log_{\frac{1}{2}}\frac{L_{\textrm{min}}}{L_{\textrm{init}}}\right\rfloor$
times. Halving occurs if BAxUS consecutively fails $\tau_{\textrm{fail}}$
times in finding a better function value. If, similarly to TuRBO, we set the
number of accepted “failures” $\tau_{\textrm{fail}}$ to the current target
dimensionality of the TR, we get the lower bound $k\cdot\tau_{\textrm{fail}}$
on the number of function evaluations spent in that target dimensionality.
This bound does not scale with the input dimensionality $D$ of the problem,
i.e., the maximum target dimensionality is independent of $D$ for a fixed
evaluation budget.

To enable BAxUS to reach any desired target dimensionality for the fixed
evaluation budget, we scale down $\tau_{\textrm{fail}}$ dependent on $D$,
i.e., we adjust the lower bound. We choose to make it dependent on $D$ as we
are guaranteed that the target space contains all global optima if the final
target space corresponds to the input space $\mathcal{X}$ (see Appendix B). In
contrast to imposing a hard limit on the number of function evaluations in a
target dimensionality, 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 $\tau_{\textrm{fail}}$ dependent on the
current target dimensionality $d_{i}$ _and_ such that BAxUS can reach any
desired target dimensionality.

We calculate the number of splits $n$ required to reach $D$ by

$D\approx d_{\textrm{init}}\cdot{}(b+1)^{n}\Rightarrow
n=\left\lfloor\log_{b+1}\frac{D}{d_{\textrm{init}}}\right\rceil,$ (3)

with $\lfloor\cdot\rceil$ indicating rounding to the nearest integer. The
minimum evaluation budget for a split is then found by multiplying $m_{D}$
with the “weight” of each target dimensionality. We assign each split $i$ a
_split budget_ $m_{i}^{s}$ that is proportional to $d_{i}$, such that
$\sum_{i=0}^{n}m^{s}_{i}=m_{D}$, where $m_{D}$ is the budgeted number of
function evaluations until $D$ would be reached under the above assumptions:

$m^{s}_{i}=\left\lfloor
m_{D}\frac{d_{i}}{\sum_{k=0}^{n}d_{k}}\right\rceil=\left\lfloor\frac{b\cdot{}m_{D}\cdot{}d_{i}}{d_{\textrm{init}}((b+1)^{n+1}-1)}\right\rceil.$

Finally, we set the number $\tau_{\textrm{fail}}^{i}$ of accepted “failures”
for the $i$-th target dimensionality $d_{i}$ such that (1) it adheres to its
_split budget_ in the event that it never obtains a better function value, (2)
it is not larger than if we would use TuRBO’s choice $d_{i}$, and (3) it is at
least 1:

$\tau_{\textrm{fail}}^{i}=\max\left(1,\min\left(\left\lfloor\frac{m_{i}^{s}}{k}\right\rfloor,d_{i}\right)\right).$

#### Setting the initial target dimension.

Due to the rounding in Eq. (3) and the exponential growth of the target
dimensionality, the final target dimensionality
$d_{\textrm{init}}\cdot(b+1)^{n}$ might differ considerably from the input
dimensionality $D$. This is undesirable as we might not reach $D$ before
depleting the evaluation budget, or we might overestimate the evaluation
budget for the final target dimensionality $d_{n}$. Therefore, we set the
initial target dimensionality such that the final target dimensionality is as
close to $D$ as possible:

$d_{\textrm{init}}=\operatorname*{arg\,min}_{i\in\\{1,\ldots,b\\}}\left|i\cdot{}(b+1)^{n}-D\right|,$
(4)

where $n$ is given by Eq. (3). We point out that $1\leq d_{\textrm{init}}\leq
b$. An alternative to adjusting $d_{\textrm{init}}$ would be to fix the
initial $d_{0}$ and adjust the growth factor $b$.

##  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://github.com/LeoIV/BAxUS.

#### 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
implementations 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 implementation [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 function evaluations for
SAASBO and 500 function evaluations for Alebo for each individual run. Larger
sampling budgets or 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 samples and BAxUS with $b=3$ and $m_{D}=1000$ and run 20
repeated trials. Plots show the mean performance with one standard error.

#### The benchmarks.

We evaluate the selected algorithms on 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 set a budget of 1000
evaluations for Mopta08, Branin2, and Hartmann6 and of 2000 evaluations for
the other benchmarks. Moreover, we stopped for Branin2 and Hartmann6 when the
simple regret dropped below $.001$. We show results on additional noise-free
benchmarks in Appendices C.2 and C.3. We also tested the algorithms on the
300D Lasso-High and the 1000D Lasso-Hard benchmarks from LassoBench [59].
These benchmarks have an effective dimensionality of $5\%$ of the input
dimensionality, i.e., the Lasso-High and Lasso-Hard 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

svg-inkscape/lassomoptasvm_noiseless_svg-tex.pdf_tex

Figure 3:  Top row: 124D Mopta08 (l): BAxUS obtains the best solutions,
followed by TuRBO and CMA-ES. 388D Svm (c): BAxUS outperforms the other
methods from the start. 500D Branin (r): SAASBO, BAxUS, Alebo, and HeSBO find
an optimum; SAASBO and Alebo converge fastest. Bottom row: 100D Lasso-Hard (l)
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 or stagnate.

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 to 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-Hard and the 300D Lasso-
High that exhibit active subspaces, here without observational noise. BAxUS
achieves considerably better solutions than all state-of-the-art 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
is that performances of BAxUS vary only slightly across runs. Thus, BAxUS is
robust despite the stochastic construction of the 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. 4
summarizes the results. We observe that BAxUS achieves considerably better
solutions for any number 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 of
the task studied above. BAxUS’ performance is equally strong as for the noise-
free case and keeps making progress after 1000 observations.

svg-inkscape/lasso_hard_high_noisy_svg-tex.pdf_tex

Figure 4: BAxUS outperforms the SOTA and in particular proves to be robust to
observational noise on the 1000D Lasso-Hard (l) and the 300D Lasso-High (r).
Note that CMA-ES performs considerably worse than on the noise-free versions
of the benchmarks.

####  BAxUS embedding ablation study.

To investigate whether the proposed family of nested random subspaces
contributes to the superior performance of BAxUS, we replaced the new
embedding with a similar family of nested HeSBO embeddings. The results show
that the proposed embedding provides a significant performance gain. Due to
space constraints, the results were moved to Appendix C.1.

##  5 Discussion

HDBO is aspiring to unlock impactful applications broadly in science and
industry. However, state-of-the-art methods suffer from limited scalability
or, in some cases, require practitioners to ‘guess’ certain hyperparameters
that critically impact the performance. This paper proposes BAxUS that works
out-of-the-box and achieves considerably better performance 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 a simple 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 a more
sophisticated data-driven approach that, for example, learns a suitable target
space. Moreover, future work will explore extending BAxUS to structured
domains, particularly the combinatorial spaces common in materials sciences
and drug discovery.

#### Societal impact.

Bayesian optimization has recently become a popular tool for tasks in drug
discovery [51], chemical engineering [31, 60, 28, 58, 11], materials science
[68, 23, 52, 64, 30, 29], aerospace engineering [43, 2, 39], robotics [41, 13,
54, 12, 46], and many more. This speaks to the progress that Bayesian
optimization has made in becoming a 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 applications benefit from
incorporating more such levers in the optimization: it allows for more
detailed modeling of an aerospace design or a more granular control of a
chemical reaction, to give some examples. The evaluation shows that the
performance of state-of-the-art methods degenerates drastically 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 a ‘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 of Twente for valuable discussions.

## References

  * Bakshy et al. [2018] E. Bakshy, L. Dworkin, B. Karrer, K. Kashin, B. Letham, A. Murthy, and S. Singh.  Ae: A domain-agnostic platform for adaptive experimentation.  In _Conference on Neural Information Processing Systems_ , pages 1–8, 2018.
  * Baptista and Poloczek [2018] R. Baptista and M. Poloczek.  Bayesian optimization of combinatorial structures.  In _International Conference on Machine Learning_ , pages 462–471. PMLR, 2018.
  * Beckenbach and Bellman [2012] E. F. Beckenbach and R. Bellman.  _Inequalities_ , volume 30.  Springer Science & Business Media, 2012.
  * Bergstra and Bengio [2012] J. Bergstra and Y. Bengio.  Random search for hyper-parameter optimization.  _Journal of machine learning research_ , 13(2), 2012.
  * Bergstra et al. [2011] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl.  Algorithms for Hyper-Parameter Optimization.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 24. Curran Associates, Inc., 2011.
  * Binois [2015] 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.
  * Binois and Wycoff [2022] M. Binois and N. Wycoff.  A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization.  _ACM Transactions on Evolutionary Learning and Optimization_ , 2(2):1–26, 2022.
  * Binois et al. [2015] 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–286. Springer, 2015.
  * Binois et al. [2020] M. Binois, D. Ginsbourger, and O. Roustant.  On the choice of the low-dimensional domain for global optimization via random embeddings.  _Journal of global optimization_ , 76(1):69–90, 2020.
  * Bouhlel et al. [2018] M. A. Bouhlel, N. Bartoli, R. G. Regis, A. Otsmane, and J. Morlier.  Efficient global optimization for high-dimensional constrained problems by using the Kriging models combined with the partial least squares method.  _Engineering Optimization_ , 50(12):2038–2053, 2018.
  * Burger et al. [2020] 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):237–241, 2020.
  * Calandra et al. [2014] R. Calandra, N. Gopalan, A. Seyfarth, J. Peters, and M. P. Deisenroth.  Bayesian Gait Optimization for Bipedal Locomotion.  In P. M. Pardalos, M. G. Resende, C. Vogiatzis, and J. L. Walteros, editors, _Learning and Intelligent Optimization_ , pages 274–290, Cham, 2014. Springer International Publishing.
  * Calandra et al. [2016] 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.
  * Candelieri et al. [2018] A. Candelieri, R. Perego, and F. Archetti.  Bayesian Optimization of Pump Operations in Water Distribution Systems.  _Journal of Global Optimization_ , 71(1):213–235, May 2018.  ISSN 0925-5001.
  * Charikar et al. [2002] M. Charikar, K. Chen, and M. Farach-Colton.  Finding Frequent Items in Data Streams.  In P. 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-45465-6.
  * Chen et al. [2020] J. Chen, G. Zhu, C. Yuan, and Y. Huang.  Semi-supervised Embedding Learning for High-dimensional Bayesian Optimization.  _arXiv preprint arXiv:2005.14601_ , 2020.
  * Constantine [2015] P. G. Constantine.  _Active Subspaces_.  Society for Industrial and Applied Mathematics, Philadelphia, PA, 2015\.
  * Cosenza et al. [2022] Z. Cosenza, R. Astudillo, P. Frazier, K. Baar, and D. E. Block.  Multi-Information Source Bayesian Optimization of Culture Media for Cellular Agriculture.  _Biotechnology and Bioengineering_ , 2022.
  * Ejjeh et al. [2022] A. Ejjeh, L. Medvinsky, A. Councilman, H. Nehra, S. Sharma, V. Adve, L. Nardi, E. Nurvitadhi, and R. A. Rutenbar.  HPVM2FPGA: Enabling True Hardware-Agnostic FPGA Programming.  In _Proceedings of the 33rd IEEE International Conference on Application-specific Systems, Architectures, and Processors_ , 2022.
  * Eriksson and Jankowiak [2021] 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 Uncertainty in Artificial Intelligence_ , volume 161 of _Proceedings of Machine Learning Research_ , pages 493–503. PMLR, 27–30 Jul 2021.
  * Eriksson and Poloczek [2021] 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.
  * Eriksson et al. [2019] D. Eriksson, M. Pearce, J. Gardner, R. D. Turner, and M. Poloczek.  Scalable Global Optimization via Local Bayesian Optimization.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 5496–5507, 2019.
  * Frazier and Wang [2016] 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.
  * Gardner et al. [2017] J. Gardner, C. Guo, K. Weinberger, R. Garnett, and R. Grosse.  Discovering and exploiting additive structure for Bayesian optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1311–1319, 2017.
  * Graham et al. [1989] R. L. Graham, D. E. Knuth, O. Patashnik, and S. Liu.  Concrete mathematics: a foundation for computer science.  _Computers in Physics_ , 3(5):106–107, 1989.
  * Hansen and Ostermeier [1996] 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.
  * Hansen et al. [2019] N. Hansen, Y. Akimoto, and P. Baudis.  CMA-ES/pycma on Github.  Zenodo, DOI:10.5281/zenodo.2559634, Feb. 2019.  Last accessed: 05/09/2022. License: BSD-3-Clause.
  * Hase et al. [2018] F. Hase, L. M. Roch, C. Kreisbeck, and A. Aspuru-Guzik.  Phoenics: a Bayesian optimizer for chemistry.  _ACS central science_ , 4(9):1134–1145, 2018\.
  * Häse et al. [2021] F. 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\.
  * Herbol et al. [2018] H. C. Herbol, W. Hu, P. Frazier, P. Clancy, and M. Poloczek.  Efficient search of compositional space for hybrid organic–inorganic perovskites via Bayesian optimization.  _npj Computational Materials_ , 4(1):1–7, 2018\.
  * Hernández-Lobato et al. [2017] J. M. Hernández-Lobato, J. Requeima, E. O. Pyzer-Knapp, and A. Aspuru-Guzik.  Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1470–1479. PMLR, 06–11 Aug 2017.
  * Hughes et al. [2021] Z. E. 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_ , 15(11):18260–18269, 2021.
  * Hvarfner et al. [2022] C. Hvarfner, D. Stoll, A. Souza, L. Nardi, M. Lindauer, and F. Hutter.  PiBO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimization.  In _International Conference on Learning Representations_ , 2022.
  * Jones [2008] D. R. Jones.  Large-scale multi-disciplinary mass optimization in the auto industry.  In _MOPTA 2008 Conference (20 August 2008)_ , 2008.
  * Kandasamy et al. [2015] 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.
  * Kandasamy et al. [2018] K. Kandasamy, W. Neiswanger, J. Schneider, B. Poczos, and E. P. Xing.  Neural Architecture 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.
  * Kingma and Welling [2014] D. P. Kingma and M. Welling.  Auto-Encoding Variational Bayes.  In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , 2014.
  * Klein et al. [2017] A. Klein, S. Falkner, S. Bartels, P. Hennig, and F. Hutter.  Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets.  In A. Singh and J. Zhu, editors, _Proceedings 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.
  * Lam et al. [2018] R. Lam, M. Poloczek, P. Frazier, and K. E. Willcox.  Advances in Bayesian optimization with applications in aerospace engineering.  In _2018 AIAA Non-Deterministic Approaches Conference_ , page 1656, 2018.
  * Letham et al. [2020] 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.
  * Lizotte et al. [2007] D. J. 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.
  * Lu et al. [2018] X. Lu, J. Gonzalez, Z. Dai, and N. D. Lawrence.  Structured Variationally Auto-encoded Optimization.  In J. G. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3273–3281. PMLR, 2018\.
  * Lukaczyk et al. [2014] T. W. Lukaczyk, P. Constantine, F. Palacios, and J. J. Alonso.  Active subspaces for shape optimization.  In _10th AIAA multidisciplinary design optimization conference_ , page 1171, 2014.
  * Marshall et al. [1979] A. W. Marshall, I. Olkin, and B. C. Arnold.  _Inequalities: theory of majorization and its applications_ , volume 143.  Springer, 1979.
  * Maus et al. [2022] N. Maus, H. T. Jones, J. Moore, M. Kusner, J. Bradshaw, and J. R. Gardner.  Local latent space bayesian optimization over structured inputs.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Mayr et al. [2022] M. Mayr, F. 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.
  * Moriconi et al. [2020] R. Moriconi, M. P. Deisenroth, and K. S. Sesh Kumar.  High-dimensional Bayesian optimization using low-dimensional feature spaces.  _Machine Learning_ , 109(9):1925–1943, Sep 2020\.  ISSN 1573-0565.
  * Mutny and Krause [2018] M. Mutny and A. Krause.  Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Nardi et al. [2019] 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.
  * Nayebi et al. [2019] A. Nayebi, A. Munteanu, and M. Poloczek.  A framework for Bayesian Optimization in Embedded Subspaces.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research (PMLR)_ , pages 4752–4761. PMLR, 09–15 Jun 2019.
  * Negoescu et al. [2011] D. M. Negoescu, P. I. Frazier, and W. B. Powell.  The Knowledge-Gradient Algorithm for Sequencing Experiments in Drug Discovery.  _INFORMS Journal on Computing_ , 23(3):346–363, 2011.
  * Packwood [2017] D. Packwood.  _Bayesian Optimization for Materials Science_.  Springer, 2017.
  * Pedrielli and Ng [2016] G. Pedrielli and S. H. Ng.  G-STAR: A new kriging-based trust region method for global optimization.  In _2016 Winter Simulation Conference (WSC)_ , pages 803–814. IEEE, 2016.
  * Rai et al. [2018] A. Rai, R. Antonova, S. Song, W. Martin, H. 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.
  * Regis [2016] R. G. Regis.  Trust regions in Kriging-based optimization with expected improvement.  _Engineering optimization_ , 48(6):1037–1059, 2016.
  * Robbins [1955] H. Robbins.  A remark on stirling’s formula.  _The American mathematical monthly_ , 62(1):26–29, 1955.
  * Ru et al. [2021] B. Ru, X. Wan, X. Dong, and M. Osborne.  Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels.  In _International Conference on Learning Representations_ , 2021.
  * Schweidtmann et al. [2018] A. M. Schweidtmann, A. D. Clayton, N. Holmes, E. Bradford, R. A. Bourne, and A. A. Lapkin.  Machine learning meets continuous flow chemistry: Automated optimization towards the Pareto front of multiple objectives.  _Chemical Engineering Journal_ , 352:277–282, 2018.
  * Šehić et al. [2022] K. Šehić, A. Gramfort, J. Salmon, and L. Nardi.  LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso.  In _First Conference on Automated Machine Learning (Main Track)_ , 2022.
  * Shields et al. [2021] 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 a tool for chemical synthesis.  _Nature_ , 590(7844):89–96, 2021.
  * Snoek et al. [2012] J. Snoek, H. Larochelle, and R. P. Adams.  Practical Bayesian Optimization of Machine Learning Algorithms.  In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * Sohrab [2003] H. H. Sohrab.  _Basic real analysis_ , volume 231.  Springer, 2003.
  * Solis and Wets [1981] F. J. Solis and R. J.-B. Wets.  Minimization by Random Search Techniques.  _Mathematics of Operations Research_ , 6(1):19–30, 1981.  ISSN 0364765X, 15265471.
  * Souza et al. [2019] 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:1904.11834_ , 2019.
  * Tallorin et al. [2018] L. Tallorin, J. Wang, W. E. Kim, S. Sahu, N. M. Kosa, P. Yang, M. Thompson, M. K. Gilson, P. I. Frazier, M. D. Burkart, et al.  Discovering de novo peptide substrates for enzymes using machine learning.  _Nature communications_ , 9(1):1–10, 2018.
  * Thompson [1933] W. R. Thompson.  On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.  _Biometrika_ , 25(3/4):285–294, 1933.  ISSN 00063444.
  * Tripp et al. [2020] A. Tripp, E. Daxberger, and J. M. Hernández-Lobato.  Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 33, pages 11259–11272. Curran Associates, Inc., 2020.
  * Ueno et al. [2016] 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.
  * Wan et al. [2021] X. Wan, V. Nguyen, H. Ha, B. Ru, C. Lu, and M. A. Osborne.  Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 10663–10674. PMLR, 18–24 Jul 2021.
  * Wang et al. [2020] 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.
  * Wang et al. [2016] Z. Wang, F. Hutter, M. Zoghi, D. Matheson, and N. de Feitas.  Bayesian optimization in a billion dimensions via random embeddings.  _Journal of Artificial Intelligence Research (JAIR)_ , 55:361–387, 2016.
  * Wang et al. [2018] Z. Wang, C. Gehring, P. Kohli, and S. Jegelka.  Batched large-scale Bayesian optimization in high-dimensional spaces.  In _International Conference on Artificial Intelligence and Statistics_ , pages 745–754, 2018.
  * Williams and Rasmussen [2006] C. K. Williams and C. E. Rasmussen.  _Gaussian processes for machine learning_ , volume 2.  MIT press Cambridge, MA, 2006.
  * Woodruff et al. [2014] D. P. Woodruff et al.  Sketching as a tool for numerical linear algebra.  _Foundations and Trends® in Theoretical Computer Science_ , 10(1–2):1–157, 2014.
  * Zhou et al. [2020] J. 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–3981, 2020.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]  See Section 5.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]
See Section 5.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]  See
Appendix A.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]  See Appendix
E.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]  See
Appendix E.

    2. (b)

Did you mention the license of the assets? [Yes]  See Appendix E.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Theoretical foundation for the BAxUS embedding

For convenience, we re-state Definition 1 and Definition 2 from Section 3.

######  Definition 1 (Sparse embedding matrix).

A matrix $S\in\\{0,\pm 1\\}^{d\times D}$ is a _sparse embedding matrix_ if and
only if each column in $S$ has exactly one non-zero entry [74].

######  Definition 2 (Success of a sparse embedding).

A success of a random sparse embedding is the event $Y^{*}=$ “All $d_{e}$
active input dimensions are mapped to distinct target dimensions.”

We introduce the following two definitions.

######  Definition 3 (Optima-preserving sparse embedding).

A sparse embedding matrix is _optima-preserving_ if each target dimension
(i.e., each column in $S$) contains at most one active input dimension.

######  Definition 4 (Sparse function / function with an active subspace).

Let $\mathcal{X}=[-1,1]^{D}$. A function $f:\mathcal{X}\rightarrow\mathbb{R}$
has an _active subspace_ (or _effective subspace_ [71]), if there exist a
subspace (i.e., a space $\mathcal{Z}\subseteq\mathbb{R}^{d_{e}}$, with
$d_{e}\leq D$ where $d_{e}\in\mathbb{N}_{++}$ is the effective dimensionality
and $\mathbb{N}_{++}=\mathbb{N}\setminus\\{0\\}$) and a projection matrix
$S^{\intercal}\in\mathbb{R}^{D\times d_{e}}$, such that for any
$\bm{x}\in\mathcal{X}$ there exists a $\bm{z}\in\mathcal{Z}$ so that
$f(\bm{x})=f(S^{\intercal}\bm{z})$ and $d_{e}$ is the smallest integer with
this property. The function is called sparse if it has an active subspace and
$S^{\intercal}$ is a sparse embedding matrix and $\mathcal{Z}=[-1,1]^{d_{e}}$.

###  A.1 Proof of Theorem 1

We prove the worst-case success probability for the BAxUS embedding.

######  Theorem 1 (Worst-case success probability of the BAxUS embedding).

Let $D$ be the input dimensionality and $d\geq d_{e}$ the dimensionality of
the embedding. Let
$\beta_{\textrm{small}}=\left\lfloor\frac{D}{d}\right\rfloor$ and
$\beta_{\textrm{large}}=\left\lceil\frac{D}{d}\right\rceil$ be the small and
large bin sizes. Then the probability of $Y^{*}$ (see Definition 2) for the
BAxUS embedding is

$p_{B}(Y^{*};D,d,d_{e})=\frac{\sum_{i=0}^{d_{e}}\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}\beta_{\textrm{small}}^{i}\beta_{\textrm{large}}^{d_{e}-i}}{\binom{D}{d_{e}}}.$
(5)

###### Proof.

The assignment of input dimensions to target dimensions and the signs of the
input dimensions fully define the BAxUS embedding. Note that the signs do not
affect $p_{B}(Y^{*};D,d,d_{e})$ because they only correspond to “flipping” the
input dimension in the target space, and our construction ensures that the
value ranges are symmetric to the origin.

An assignment is optima-preserving if and only if it is possible to find a
point in $\mathcal{Y}$ that maps to an optimum in $\mathcal{X}$ for any $f$.
The “only if” is true because $f$ is assumed to be sparse with an active
subspace with $d_{e}$ active dimensions. This means that the optima in
$\mathcal{X}$ only change their function values along the $d_{e}$ active
dimensions. Suppose it is possible to find a point in $\mathcal{Y}$ that maps
to an arbitrary optimum in $\mathcal{X}$. In that case, the assignment is
optima-preserving because it can individually adjust all the $d_{e}$ active
dimensions in $\mathcal{X}$. However, this generally requires each active
input dimension to be mapped to a distinct target dimension (note that we
require being able to represent the optimum for _any_ $f$). Otherwise, there
would be at least two active input dimensions that cannot be changed
independently. Therefore, the probability of $Y^{*}$ equals the probability of
an optima-preserving assignment.

As all assignments are equally likely under the construction, the probability
of an assignment being optima-preserving is equal to the number of possible
optima-preserving assignments divided by the total number of assignments.
There are $\binom{D}{d_{e}}$ ways of distributing the $d_{e}$ active
dimensions across the $D$ positions, giving the denominator in Eq. (5).

Let us first assume that
$\beta_{\textrm{small}}=\beta_{\textrm{large}}=\beta$, i.e., all target
dimensions have the same number of input dimensions and $d$ divides $D$. We
refer to this case as the _balanced case_. There are $\binom{d}{d_{e}}$ ways
of distributing the $d_{e}$ active dimensions across the $d$ different target
dimensions. Given one active dimension, there are $\beta$ ways in which this
dimension can map to the target dimension. Therefore, for the balanced case,
the worst-case success probability is given by

$\displaystyle
p_{B}(Y^{*};D,d,d_{e})=\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}.$
(6)

Next, we generalize Eq. (6) for cases where $d$ does not divide $D$. We refer
to this case as the _near-balanced case_. In that case, there are two bin
sizes: $\beta_{\textrm{small}}$ and $\beta_{\textrm{large}}$ with
$\beta_{\textrm{large}}=\beta_{\textrm{small}}+1$. There are
$d\beta_{\textrm{large}}-D$ small bins (i.e., bins with bin size
$\beta_{\textrm{small}}$) and $D-d\beta_{\textrm{small}}$ large bins:
$D-d\beta_{\textrm{small}}$ gives the number of input dimensions that would
not be covered if all bins were small. Since $\beta_{\textrm{small}}$ and
$\beta_{\textrm{large}}$ differ by $1$, this also gives the number of bins
that have to be large. Conversely, if we only had large bins, we would cover
$d\beta_{\textrm{large}}-D$ too many input dimensions. Therefore, we need
$D-d\beta_{\textrm{small}}$ large and $d\beta_{\textrm{large}}-D$ small bins.

We consider all ways of distributing the $d_{e}$ active dimensions across the
the $d\beta_{\textrm{large}}-D$ small and $D-d\beta_{\textrm{small}}$ large
bins so that there is at most one active dimension in each bin. Recall that
this number gives the numerator in Eq. (5). For a conflict-free assignment, if
$i$ active dimensions are mapped to small bins, then $d_{e}-i$ active
dimensions must be assigned to large bins. There are
$\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}$
such assignments. Here we use that
$1+\beta_{\textrm{small}}=\beta_{\textrm{large}}$ holds for the near-balanced
case. Recall that each small bin has $\beta_{\textrm{small}}$ locations and
that each large bin has $\beta_{\textrm{large}}$ locations that an active
dimension can be assigned to. Because $0\leq i\leq d_{e}$ by construction, the
number of assignments that result in an optima-preserving embedding is

$\sum_{i=0}^{d_{e}}\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}\beta_{\textrm{small}}^{i}\beta_{\textrm{large}}^{d_{e}-i}.$

Note that we leverage the facts $\binom{0}{0}=1$, $\binom{0}{x}=0$ for all
$x\geq 1$, $\binom{y}{x}=0$ if $x>y\geq 0$, and $\binom{x}{0}=1$ for all $x$,
thus the sum is well defined. Recall that we already showed that the
denominator is $\binom{D}{d_{e}}$. Therefore, Eq. (5) gives the success
probability in the near-balanced case.

It is easy to see that Eq. (5) is equivalent to the near-balanced formulation
in Eq. (6) when $d$ divides $D$. When $d$ divides $D$,
$\beta_{\textrm{small}}=\beta_{\textrm{large}}=\beta$,
$d(1+\beta_{\textrm{small}})-D=d$, and $D-d\beta_{\textrm{small}}=0$.
Therefore, the worst-case success probability for the near-balanced case is
given by

$\displaystyle p_{B}(Y^{*};D,d,d_{e})$
$\displaystyle=\frac{\sum_{i=0}^{d_{e}}\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}\beta_{\textrm{small}}^{i}\beta_{\textrm{large}}^{d_{e}-i}}{\binom{D}{d_{e}}}$
$\displaystyle\overset{\beta_{\textrm{small}}=\beta_{\textrm{large}}}{=}\frac{\sum_{i=0}^{d_{e}}\binom{d}{i}\binom{0}{d_{e}-i}\beta^{i}\beta^{d_{e}-i}}{\binom{D}{d_{e}}}$
$\displaystyle=\frac{\beta^{d_{e}}\sum_{i=0}^{d_{e}}\binom{d}{i}\binom{0}{d_{e}-i}}{\binom{D}{d_{e}}}=\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}$

where the last equality is true because the sum is zero unless $i=d_{e}$.
∎

###  A.2 Proof of Corollary 2

We prove the optimality of the BAxUS embedding in terms of the worst-case
success probability.

######  Corollary 2.

With the same input, target, and effective dimensionalities ($D$, $d$, and
$d_{e}$), no sparse embedding has a higher worst-case success probability than
the BAxUS embedding.

###### Proof.

By Definition 1, an embedding matrix $S\in\\{0,\pm 1\\}^{D\times d}$ is sparse
if each row in $S$ has exactly one non-zero entry. Such an embedding can
always be interpreted as disjoint sets of signed input dimensions assigned to
different target dimensions: For the $n$-th input dimension, find the column
with the non-zero. The respective column gives the target dimension; the entry
in the matrix itself gives the sign. Conversely, each target dimension has a
set of contributing input dimensions, and we call the set of input dimensions
mapping to a target dimension a “bin”. The sign of the input dimensions does
not influence the success probability as it does not influence the ability of
an embedding to contain the optimum.

We will prove that the BAxUS embedding is optimal, i.e., every other sparse
embedding has a worst-case success probability that is lower or equal. We
start by giving the worst-case success probability for arbitrary bin sizes.

Let $\beta_{n}$ be the bin size of the $n$-th bin. By Definition 2, a success
is guaranteed if each bin contains at most one active input dimension.
Therefore, the worst-case success probability for arbitrary bin sizes has to
consider the number of cases where each bin contains at most one active input
dimension and the number of bins containing one active input dimension is
equal to the number of active input dimensions $d_{e}$. In a bin of size
$\beta_{i}$, the active input dimension can lie in $\beta_{i}$ different
locations. Bins not containing an active dimension do not contribute to the
worst-case success probability.

We suppose w.l.o.g. that $D\geq d$. Thus, every target dimension has at least
one input dimension. For each $n$ from $1$ to $d$, let the value $i_{n}$
indicate whether the $n$-th bin (or target dimension) contains an active
dimension ($i_{n}=1$) or not ($i_{n}=0$). The indicator variable
$\mathds{1}_{(\sum_{n=1}^{d}i_{n})=d_{e}}$ ensures that only cases where
exactly $d_{e}$ bins contain an active input dimension are counted. Note that
$\sum_{i_{1}=0}^{1}\sum_{i_{2}=0}^{1}\ldots\sum_{i_{d}=0}^{1}\mathds{1}_{(\sum_{n=1}^{d}i_{n})=d_{e}}=\binom{d}{d_{e}}$.
For each case where the $d_{e}$ active dimensions are assigned to $d_{e}$ out
of $d$ disjoint bins, the term $\prod_{n=1}^{d}\beta_{n}^{i_{n}}$ accounts for
the locations in which the active dimension can lie in the $n$-th bin. Other
cases do not contribute to the worst-case success probability. The exponent
ensures that only bins containing an active dimension contribute to the
denominator.

Then the worst-case success probability for arbitrary bin sizes is given by

$p_{\textrm{general}}(Y^{*};D,d,d_{e})=\frac{\overbrace{\sum_{i_{1}=0}^{1}\sum_{i_{2}=0}^{1}\ldots\sum_{i_{d}=0}^{1}\mathds{1}_{(\sum_{n=1}^{d}i_{n})=d_{e}}}^{=\binom{d}{d_{e}}}{\displaystyle\prod_{n=1}^{d}\beta_{n}^{i_{n}}}}{\binom{D}{d_{e}}},$
(7)

with $\beta_{n}>0$, $\sum_{n=1}^{d}\beta_{n}=D$, and $d\geq d_{e}$:

As in Theorem 1, the denominator of Eq. (7) gives all ways of assigning
$d_{e}$ active dimensions to $D$ input dimensions.

We now prove that any sparse embedding has a worst-case success probability
that is less or equal to the worst-case success probability of the BAxUS
embedding.

Let $\beta_{\textrm{small}}$, $\beta_{\textrm{large}}$, and
$p_{B}(Y^{*};D,d,d_{e})$ as in Theorem 1. Then,

$p_{\textrm{general}}(Y^{*};D,d,d_{e})\leq
p_{B}(Y^{*};D,d,d_{e})=\frac{\overbrace{\sum_{i=0}^{d_{e}}\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}}^{=\binom{d}{d_{e}}}\beta_{\textrm{small}}^{i}\beta_{\textrm{large}}^{d_{e}-i}}{\binom{D}{d_{e}}}.$
(8)

We refer the reader to the proof of Theorem 1 for an explanation of the
binomial coefficients. The fact that
$\sum_{i=0}^{d_{e}}\binom{d(1+\beta_{\textrm{small}})-D}{i}\binom{D-d\beta_{\textrm{small}}}{d_{e}-i}=\binom{d}{d_{e}}$
can be seen by noting that
$(d(1+\beta_{\textrm{small}})-D)+(D-d\beta_{\textrm{small}})=d$ and applying
Vandermonde’s convolution [25].

We will now prove that if $d$ divides $D$, then the product in the numerator
of Eq. (7) is maximized if all the factors are the same, i.e.,
$\beta=\frac{D}{d}$. We will then show that if $d$ does not divide $D$, the
integer-solution of maximal value is attained for
$\beta_{\textrm{large}}-\beta_{\textrm{small}}=1$.

#### First case ($d$ divides $D$)

We now show that the following holds for the term
$\prod_{n=1}^{d}\beta_{n}^{i_{n}}$ in the numerator of Eq. (7):
$\prod_{n=1}^{d}\beta_{n}^{i_{n}}\leq\beta^{d_{e}}$. The numerator in Eq. (7)
can also be written as $e_{d_{e}}(\beta_{1},\ldots,\beta_{d})$ where

$\displaystyle e_{d_{e}}(\beta_{1},\ldots,\beta_{d})$
$\displaystyle=\sum_{i_{1}<i_{2}<\ldots<i_{d_{e}}}\beta_{i_{1}}\beta_{i_{2}}\ldots\beta_{i_{d_{e}}}$
$\displaystyle=\sum_{i_{1}=0}^{1}\sum_{i_{2}=0}^{1}\ldots\sum_{i_{d}=0}^{1}\mathds{1}_{(\sum_{n=1}^{d}i_{n})=d_{e}}{\displaystyle\prod_{n=1}^{d}\beta_{n}^{i_{n}}}$

is the $d_{e}$-th elementary symmetric function of
$\beta_{1},\ldots,\beta_{d}$ [3]. Maclaurin’s inequality [3] states that

$\displaystyle\frac{e_{1}(\beta_{1},\ldots,\beta_{d})}{\binom{d}{1}}\geq\sqrt{\frac{e_{2}(\beta_{1},\ldots,\beta_{d})}{\binom{d}{2}}}\geq\ldots\geq\sqrt[d_{e}]{\frac{e_{d_{e}}(\beta_{1},\ldots,\beta_{d})}{\binom{d}{d_{e}}}}\geq\ldots\geq\sqrt[d]{\frac{e_{d}(\beta_{1},\ldots,\beta_{d})}{\binom{d}{d}}}.$
(9)

In particular,

$\displaystyle\frac{e_{1}(\beta_{1},\ldots,\beta_{d})}{\binom{d}{1}}=\frac{\sum_{i=1}^{d}\beta_{i}}{d}=\frac{D}{d}=\beta$
(10)

holds. Taking Eq. (9) and Eq. (10) to the power $d_{e}$ and multiplying by
$\binom{d}{d_{e}}$, we obtain

$\beta^{d_{e}}\binom{d}{d_{e}}\geq
e_{d_{e}}(\beta_{1},\ldots,\beta_{d})=\sum_{i_{1}=0}^{1}\sum_{i_{2}=0}^{1}\ldots\sum_{i_{d}=0}^{1}\mathds{1}_{(\sum_{n=1}^{d}i_{n})=d_{e}}{\displaystyle\prod_{n=1}^{d}\beta_{n}^{i_{n}}},$
(11)

with equality if and only if $\beta_{i}=\beta_{j}$ for
$i,j\in\\{1,\ldots,n\\}$ [3]. Therefore, the product in the numerator of Eq.
(7) is maximized if all factors are equal.

#### Second case ($d$ does not divide $D$)

However, if $d$ does not divide $D$, then $\beta$ is no integer which is not
feasible in our setting. The $d_{e}$-th elementary symmetric function
$e_{d_{e}}(\bm{\beta})$ (see Eq. (11)) is known to be _Schur-concave_ if
$\beta_{i}\geq 0$ holds for all $i$ [44]. This condition is met by $\beta$. We
use the following definition of [44]: A function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is called Schur-concave if
$\bm{\gamma}\prec\bm{\beta}$ implies $f(\bm{\gamma})\geq f(\bm{\beta})$. Here,
$\bm{\gamma}\prec\bm{\beta}$ means that $\bm{\beta}$ _majorizes_
$\bm{\gamma}$, i.e.,

$\sum_{i=1}^{k}\bm{\gamma}^{\downarrow}_{i}\leq\sum_{i=1}^{k}\bm{\beta}^{\downarrow}_{i}\quad\text{for
all
$k\in\\{1,\ldots,d\\}$},\quad\text{and}\quad\sum_{i=1}^{d}\bm{\gamma}_{i}=\sum_{i=1}^{d}\bm{\beta}_{i},$

where $\bm{\gamma}^{\downarrow}$ and $\bm{\beta}^{\downarrow}$ are the vectors
of all elements in $\bm{\gamma}$ and $\bm{\beta}$ in descending order [44].

We now show that there is no integer solution $\bm{\gamma}$ such that there is
a near-balanced solution that majorizes $\bm{\gamma}$.

For some near-balanced assignment $\bm{\beta}$ of small and large bins to the
$d$ target dimensions, consider the vector

$\bm{\beta}^{\downarrow}=\left(\underbrace{\overbrace{\left\lceil\frac{D}{d}\right\rceil}^{=\beta_{\textrm{large}}},\ldots,\left\lceil\frac{D}{d}\right\rceil}_{D-d\beta_{\textrm{small}}\text{
many}},\underbrace{\overbrace{\left\lfloor\frac{D}{d}\right\rfloor}^{=\beta_{\textrm{small}}},\ldots,\left\lfloor\frac{D}{d}\right\rfloor}_{d\beta_{\rm
large}-D\text{ many}}\right)$

of bin sizes in decreasing order. For any other BAxUS embedding given by some
permutation $\bm{\beta}^{\prime}$ of $\bm{\beta}$, it holds that
$\bm{\beta}^{\prime\downarrow}=\bm{\beta}^{\downarrow}$. Note that for any
assignment $\bm{\gamma}=\\{\bm{\gamma}_{1},\ldots,\bm{\gamma}_{d}\\}$ of bin
sizes over the $d$ target dimensions, it has to hold that

$\sum_{i=1}^{d}\bm{\gamma}_{i}=D;\,\bm{\gamma}_{i}\geq
0,\,i\in\\{1,\ldots,d\\};\,\bm{\gamma}\in\mathbb{N}_{0}^{d}.$

By assumption, since we are in the near-balanced case,
$\beta_{\textrm{small}}=\beta_{\textrm{large}}-1$.

Assume there exists an assignment of bin sizes $\bm{\gamma}$ that is not a
permutation of $\bm{\beta}$ such that $\bm{\gamma}\prec\bm{\beta}$, i.e.,

$\displaystyle\sum_{i=1}^{k}\bm{\gamma}^{\downarrow}_{i}\leq\sum_{i=1}^{k}\bm{\beta}^{\downarrow}_{i}\quad\text{for
all $k\in\\{1,\ldots,d\\}$},$ (12) and
$\displaystyle\sum_{i=1}^{d}\bm{\gamma}_{i}=\sum_{i=1}^{d}\bm{\beta}_{i},$
(13) and $\displaystyle\exists
j:\bm{\gamma}^{\downarrow}_{j}<\bm{\beta}^{\downarrow}_{j}.$ (14)

Let $\bm{\kappa}$ denote the (non-empty) set of such indices. Because the
elements of $\bm{\beta}$ and $\bm{\gamma}$ both sum up to $D$, it has to hold
for all $\kappa\in\bm{\kappa}$ that

$\displaystyle\sum_{i=1,i\neq\kappa}^{d}\bm{\gamma}^{\downarrow}_{i}>\sum_{i=1,i\neq\kappa}^{d}\bm{\beta}^{\downarrow}_{i}.$
(15)

Remember that $\bm{\beta}$ only contains elements of sizes $\beta_{\rm small}$
and $\beta_{\rm large}$ with $\beta_{\rm large}=\beta_{\rm small}-1$. Then,
Eq. (15) can only hold if either 1) $\bm{\gamma}$ contains more elements of
size $\beta_{\rm large}$ than $\bm{\beta}$ or 2) if it contains at least one
element that is larger than $\beta_{\rm large}$, the largest element in
$\bm{\beta}$.

Both cases lead to a contradiction. In the first case,

$\sum_{i=1}^{D-d\beta_{\rm
small}+1}\bm{\gamma}^{\downarrow}_{i}>\sum_{i=1}^{D-d\beta_{\rm
small}+1}\bm{\beta}^{\downarrow}_{i}\Rightarrow\bm{\gamma}\not\prec\bm{\beta}$

since at least the first $D-d\beta_{\rm small}+1$ elements of
$\bm{\gamma}^{\downarrow}$ are $\left\lceil\frac{D}{d}\right\rceil$ but only
the first $D-d\beta_{\rm small}$ elements of $\bm{\beta}^{\downarrow}$ are
$\left\lceil\frac{D}{d}\right\rceil$ and the $D-d\beta_{\rm small}+1$-th
element of $\bm{\beta}^{\downarrow}$ is
$\left\lceil\frac{D}{d}\right\rceil-1$.

In the second case, $\bm{\gamma}\not\prec\bm{\beta}$ because
$\bm{\gamma}^{\downarrow}_{1}>\bm{\beta}^{\downarrow}_{1}$. It follows that no
such $\bm{\gamma}$ exists. Therefore, the BAxUS embedding has a maximum worst-
case success probability among sparse embeddings. ∎

###  A.3 Proof of Corollary 1

######  Corollary 1.

For $D\rightarrow\infty$, the worst-case success probability of the BAxUS
embedding is

$\lim_{D\rightarrow\infty}p_{B}(Y^{*};D,d,d_{e})=\frac{d!}{(d-d_{e})!d^{d_{e}}},$
(16)

and hence matches HeSBO’s worst-case success probability
$p_{H}(Y^{*};d,d_{e})$.

###### Proof.

By Corollary 1, the following holds for arbitrary $1\leq d_{e}\leq d\leq D$
where $d,d_{e},D\in\mathbb{N}_{++}$:

$\frac{d!}{(d-d_{e})!d^{d_{e}}}\leq p_{B}(Y^{*};D,d,d_{e}),$

because $\frac{d!}{(d-d_{e})!d^{d_{e}}}$ is HeSBO’s worst-case success
probability and hence less or equal to the worst-case success probability of
BAxUS.

Furthermore, by the proof of Corollary 1,

$p_{B}(Y^{*};D,d,d_{e})\leq\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}},$

because $\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}$ is larger or
equal the worst-case success probability of any sparse embedding, among which
BAxUS is the embedding with maximum worst-case success probability and
$\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}=p_{B}(Y^{*};D,d,d_{e})$
if and only if $\beta_{\rm small}=\beta_{\rm large}$, i.e., $d$ divides $D$.

In summary, we have

$\frac{d!}{(d-d_{e})!d^{d_{e}}}\leq
p_{B}(Y^{*};D,d,d_{e})\leq\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}.$

We now show that, for fixed $d$ and $d_{e}$, the sequences
$\frac{d!}{(d-d_{e})!d^{d_{e}}}$ and
$\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}$ converge to the same
point as $D\rightarrow\infty$. We consider $\lim_{\beta\rightarrow\infty}$,
which is equivalent to $\lim_{D\rightarrow\infty}$ as $\beta=\frac{D}{d}$ and
$d$ is fixed. Note, that we can consider $\beta=\frac{D}{d}$ even though it is
not a valid success probability when $d$ does not divide $D$, since we are
only interested in bounding the true success probability. Then,

$\displaystyle\lim_{\beta\rightarrow\infty}\frac{\beta^{d_{e}}\binom{d}{d_{e}}}{\binom{D}{d_{e}}}$
$\displaystyle=\lim_{\beta\rightarrow\infty}\frac{\beta^{d_{e}}d!(D-d_{e})!}{D!(d-d_{e})!}$
(17) $\displaystyle=\lim_{\beta\rightarrow\infty}\frac{\beta^{d_{e}}d!(\beta
d-d_{e})!}{(\beta d)!(d-d_{e})!}$ (18)
$\displaystyle=\lim_{\beta\rightarrow\infty}\beta^{d_{e}}\frac{d!}{(d-d_{e})!}\frac{(\beta
d-d_{e})!}{(\beta d)!}$ (19) Applying Stirling’s approximation [25] to the
numerator and the denominator of the last factor, we obtain
$\displaystyle=\lim_{\beta\rightarrow\infty}\beta^{d_{e}}\frac{d!}{(d-d_{e})!}\frac{\sqrt{2\pi(\beta
d-d_{e})}\left(\frac{\beta d-d_{e}}{e}\right)^{\beta d-d_{e}}}{\sqrt{2\pi\beta
d}\left(\frac{\beta d}{e}\right)^{\beta d}}\frac{r(\beta d-d_{e})}{r(\beta
d)}$ (20)
$\displaystyle=\lim_{\beta\rightarrow\infty}\beta^{d_{e}}\frac{d!}{(d-d_{e})!}\sqrt{\frac{\beta
d-d_{e}}{\beta d}}e^{d_{e}}\frac{(\beta d-d_{e})^{\beta d-d_{e}}}{(\beta
d)^{\beta d}}\frac{r(\beta d-d_{e})}{r(\beta d)}$ (21)
$\displaystyle=\lim_{\beta\rightarrow\infty}\beta^{d_{e}}\frac{d!}{(d-d_{e})!}\sqrt{\frac{\beta
d-d_{e}}{\beta d}}e^{d_{e}}\left(\frac{\beta d-d_{e}}{\beta d}\right)^{\beta
d}\frac{1}{(\beta d-d_{e})^{d_{e}}}\frac{r(\beta d-d_{e})}{r(\beta d)}$ (22)
$\displaystyle=\lim_{\beta\rightarrow\infty}\frac{d!}{(d-d_{e})!}\sqrt{\frac{\beta
d-d_{e}}{\beta d}}e^{d_{e}}\left(\frac{\beta d-d_{e}}{\beta d}\right)^{\beta
d}\frac{\beta^{d_{e}}}{(\beta d-d_{e})^{d_{e}}}\frac{r(\beta d-d_{e})}{r(\beta
d)}$ (23)
$\displaystyle=\lim_{\beta\rightarrow\infty}\frac{d!}{(d-d_{e})!}\underbrace{\sqrt{\frac{\beta
d-d_{e}}{\beta d}}}_{\rightarrow 1}e^{d_{e}}\underbrace{\left(\frac{\beta
d-d_{e}}{\beta d}\right)^{\beta d}}_{\rightarrow
e^{-d_{e}}}\underbrace{\left(\frac{1}{d}\right)^{d_{e}}}_{=d^{-d_{e}}}\underbrace{\left(\frac{\beta
d}{\beta d-d_{e}}\right)^{d_{e}}}_{\rightarrow 1}\underbrace{\frac{r(\beta
d-d_{e})}{r(\beta d)}}_{\rightarrow 1}$ (24)
$\displaystyle=\frac{d!}{(d-d_{e})!d^{d_{e}}}$ (25)

where the following holds for the error term $r(x)$ of the Stirling
approximation [56]:

$\exp\left(\frac{1}{12x+1}\right)\leq r(x)\leq\exp\left(\frac{1}{12x}\right).$

Then, $\frac{r(\beta d-d_{e})}{r(\beta d)}\rightarrow 1$ for
$\beta\rightarrow\infty$ holds since

$\displaystyle\frac{r(\beta d-d_{e})}{r(\beta d)}$
$\displaystyle\leq\exp\left(\frac{1}{12(\beta d-d_{e})}-\frac{1}{12\beta
d+1}\right)$ (26)
$\displaystyle=\exp\left(\frac{12d_{e}+1}{12^{2}\beta^{2}d^{2}+12\beta
d-12^{2}\beta dd_{e}-12d_{e}}\right)$ (27)
$\displaystyle=\exp\left(\frac{d_{e}+\frac{1}{12}}{\beta d(12\beta
d+1-12d_{e})-d_{e}}\right),$ (28)

and

$\displaystyle\frac{r(\beta d-d_{e})}{r(\beta d)}$
$\displaystyle\geq\exp\left(\frac{1}{12(\beta d-d_{e})+1}-\frac{1}{12\beta
d}\right)$ (29)
$\displaystyle=\exp\left(\frac{12d_{e}-1}{12^{2}\beta^{2}d^{2}+12\beta
d-12^{2}\beta dd_{e}-12\beta d_{e}}\right)$ (30)
$\displaystyle=\exp\left(\frac{d_{e}-\frac{1}{12}}{\beta d(12\beta
d+1-12d_{e})-d_{e}}\right),$ (31)

which both go to $1$ as $\beta\rightarrow\infty$.

Hence, BAxUS’ worst-case success probability is bounded from below and above
by sequences that converge to the same point as $D\rightarrow\infty$. The
squeeze theorem (e.g., [62]) implies

$\lim_{D\rightarrow\infty}p_{B}(Y^{*};D,d,d_{e})=\frac{d!}{(d-d_{e})!d^{d_{e}}}.$

∎

##  Appendix B Consistency of BAxUS

We prove the global convergence of function values for BAxUS. The proof idea
is similar to Eriksson and Poloczek [21] but relaxes the assumption of a
unique global minimizer. By construction, $f$ is sparse (see Definition 4),
i.e., there exists a set of dimensions of $f$ that do not influence the
function value. Thus, an optimal solution stays optimal regardless of how
inactive dimensions are set. This is why we must relax the assumption of a
unique global minimizer in the input space. Instead, we assume a unique global
minimizer in the active subspace $\bm{z}^{*}\in\mathcal{Z}$ that can map to
arbitrarily many minimizers in the input space. Note that this assumption
covers the case when the target space corresponds to the input space, i.e.,
$d=D$.

######  Theorem 2 (BAxUS consistency).

With the following definitions:

  1. D1.

$\\{\bm{x}_{k}\\}_{k=1}^{\infty}$ is a sequence of points of decreasing
function value;

  2. D2.

$\bm{x}^{*}\in\operatorname*{arg\,min}_{\bm{x}\in\mathcal{X}}f(\bm{x})$ is a
minimizer in $\mathcal{X}$;

and under the following assumptions:

  1. A1.

$D$ is finite;

  2. A2.

$f$ is observed without noise;

  3. A3.

$f$ is sparse and bounded in $\mathcal{X}$, i.e.,
$\exists\,C\in\mathbb{R}_{++}$ s.t.
$|f(\bm{x})|<C\,\forall\,\bm{x}\in\mathcal{X}$;

  4. A4.

At least one of the minimizers $\bm{x}^{*}_{i}$ lies in a continuous region
with positive measure;

  5. A5.

Once BAxUS reached the input dimensionality $D$, the initial points
$\\{\bm{x}_{i}\\}_{i=1}^{n_{\textrm{init}}}$ after each TR restart for BAxUS
are chosen such that $\forall\delta\in\mathbb{R}_{++}$ and
$\bm{x}\in\mathcal{X}$, $\exists\,\nu(\bm{x},\delta)>0$:
$\mathbb{P}\left(\exists
i:||\bm{x}-\bm{x}_{i}||_{2}\leq\delta\right)\geq\nu(\bm{x},\delta)$, i.e., the
probability that at least one point in $\\{\bm{x}_{i}\\}_{i=1}^{n_{\rm init}}$
ends up in a ball centered at $\bm{x}$ with radius $\delta$ is at least
$\nu(\bm{x},\delta)$;

$f(\bm{x}_{k})$ converges to $f(\bm{x}^{*})$ with probability 1.

###### Proof.

We first show that BAxUS must eventually arrive at an embedding equivalent to
the input space. By Assumption A1, the number of accepted “failures” (i.e.,
the number of times BAxUS needs to fail in finding a better solution until the
TR base length is shrunk) is always finite since it is always bounded by the
target dimension ($\forall i\,\tau_{\rm fail}^{i}\leq d_{i}$) which is at most
equal to $D$ ($\forall i\,d_{i}\leq D$). By the facts that BAxUS considers any
sampled point an improvement only if it improves over the current best
solution by at least some constant $\gamma\in\mathbb{R}_{++}$ and that $f$ is
bounded (Assumption A3), BAxUS can only perform a finite number of function
evaluations without increasing the target dimensionality of its embedding.

Once BAxUS reaches $D$, it behaves like TuRBO [22] for which Eriksson and
Poloczek [21] proved global convergence assuming a unique global minimizer.
For the case $d_{e}<D$, we notice that multiple minima in the input space
occur due to inactive dimensions that do not influence the function value.

The remainder of our proof is based on the convergence theorem for global
search by Solis and Wets [63], which proves convergence of function values for
random search with possibly multiple minima. By considering the sequence

$\left\\{\bm{x^{\prime}}_{i}\in\operatorname*{arg\,min}_{\bm{\hat{x}}\in\\{\bm{x}_{k}\\}_{k=1}^{i}}f(\bm{\hat{x}})\right\\}_{i=1}^{\infty}$

of points of decreasing function values where $\\{\bm{x}_{k}\\}_{k=1}^{i}$ are
the observations up to the $i$-th function evaluation, Definition D1 is
satisfied. Additionally, by the fact that, at each TR restart, BAxUS performs
random restarts with uniform probability on $\mathcal{X}$, BAxUS satisfies the
assumptions of the theorem by Solis and Wets [63].

The theorem by Solis and Wets [63] states that for a sequence
$\\{\bm{x}_{k}\\}_{k=1}^{\infty}$ of sampling points with
$\varepsilon\in\mathbb{R}_{++}$,

$\displaystyle\lim_{k\rightarrow\infty}\mathbb{P}\left[\bm{x}_{k}\in
R_{\varepsilon}\right]=1$ $\displaystyle
R_{\varepsilon}=\\{\bm{x}\in\mathcal{X}:f(\bm{x})<\alpha+\varepsilon\\}$
$\displaystyle\alpha=\inf\\{t:v(\bm{x}\in\mathcal{X}:f(\bm{x})<t)>0\\}$

where $R_{\varepsilon}$ is the set of $\varepsilon$-optimal function values,
$\alpha$ is the _essential infimum_ , and $v$ is the Lebesgue measure. Note
that the essential infimum $\alpha$ is equal to the minimum if the minimizer
lies in a continuous region of positive measure, i.e.,
$\alpha=f(\bm{x}_{i}^{*})$. By Assumption A4 and by letting
$\varepsilon\rightarrow 0$, $f(\bm{x}_{k})$ converges to $f(\bm{x}_{i}^{*})$.
∎

##  Appendix C Additional empirical evaluations

###  C.1 Ablation study for the BAxUS embedding

We conduct an ablation study to investigate the difference between the BAxUS
and HeSBO embeddings. We run TuRBO of Eriksson et al. [22] in an embedded
subspace with the two different embeddings. We use a version of Ackley10 (ten
active dimensions, i.e., $d_{e}=10$), where we shift the optimum away from the
origin with a uniformly random vector $\bm{\delta}\in[-32.768,32.768]^{d_{e}}$
with $\delta_{i}\sim\mathcal{U}(-32.768,32.768)$. The function we optimize is
then

$\displaystyle
f_{\textrm{ShiftedAckley10}}(\bm{x})=f_{\textrm{Ackley10}}(\bm{x}+\bm{\delta}).$

We adjust the boundaries of the search space such that
$f_{\textrm{ShiftedAckley10}}$ is evaluated on the domain
$\mathcal{X}=[-32.768,32.768]^{d_{e}}$. The reason for shifting the optimum is
that the original Ackley function has its optimum at the origin. In that case,
any sparse embedding contains this optimum, even if all the active input
dimensions are mapped to the same target dimension.

We add 10 dummy dimensions, such that $D=30$ and set $d=20$. With this
problem-setting, the BAxUS and HeSBO embeddings have a probability of
approximately 0.27 and 0.07 of containing the optimum, respectively.

svg-inkscape/ablation_svg-tex.pdf_tex

Figure 5: Left: the BAxUS embedding gives better optimization performance on
the shifted Ackley10 function: TuRBO in embedded subspaces of the BAxUS and
HeSBO embeddings. The BAxUS embedding has a higher probability to contain the
optimum. Right: the distribution of the final incumbents (lower the better).
The horizontal bars show the median.

The left side of Figure 5 shows the incumbent mean for TuRBO in the two
different embedded subspaces. The shaded regions show one standard error.
TuRBO in an BAxUS embedding has significantly better optimization performance
than in a HeSBO embedding. The right side of Figure 5 shows the distributions
of the final incumbents and their median. The BAxUS embedding leads to a
significantly lower median and only rarely a similarly bad embedding as the
HeSBO method when combined with TuRBO.

We perform a two-sided Wilcoxon rank-sum statistical test to check the
difference between the best observed function values for the two embeddings.
The difference is significant with $p\approx 0.00001$.

The performance difference between the two embeddings depends on the
characteristics of the function and the different dimensionalities, the input
dimensionality $D$, the target dimensionality $d$, and the effective
dimensionality $d_{e}$. For problems with few active dimensions and many input
dimensions, the BAxUS and HeSBO embeddings become more similar (see Figure 2).
However, by Corollary 2, the BAxUS embedding is, in expectation and in terms
of the worst-case success probability, better than the HeSBO embedding for
arbitrary sparse functions.

For functions with an optimum at the origin, both embeddings contain that
optimum regardless of $d$: Even if all active input dimensions are mapped to
the same target dimension, the optimum in the input space can be reached by
“setting” this particular target dimension to zero.

####  TuRBO with BAxUS embedding vs. BAxUS.

We compare the simple idea of running TuRBO in a BAxUS embedding of fixed
target dimensionality with the BAxUS algorithm described in Section 3. We run
this simple approach for $11$ different target dimensionalities $d$
($2,10,20,\ldots,100$) on the Lasso-Hard benchmark and show the results with a
sequential color map in Figure 6. Only the first $d=2$-dimensional embedding
achieves the same initial speedup as BAxUS, which is expected as BAxUS starts
in a similarly low-dimensional initial embedding. However, the fixed embedding
cannot explore the input space sufficiently and has the worst final solution.
High-dimensional fixed embeddings have more freedom in exploring the input
space; however, they suffer from slower initial optimization performance.

BAxUS has the same initial speedup as the two-dimensional fixed embedding but
can explore the space further by increasing the dimensionality of its
embedding.

svg-inkscape/thesbo_vs_baxus_svg-tex.pdf_tex

Figure 6: An evaluation of BAxUS and TuRBO with BAxUS embeddings of different
target dimensionalities on Lasso-Hard: We run TuRBO with the BAxUS embedding
for fixed target dimensionalities $d=2,10,20,\ldots,100$ and compare to BAxUS.

Summing up, we observe that BAxUS achieves a better performance than TuRBO
with a fixed embedding dimensionality.

###  C.2 Evaluation on an additional Lasso benchmark

In addition to the synthetic Lasso-High and Lasso-Hard benchmarks studied in
Section 4, we evaluate BAxUS on the Lasso-DNA benchmark from LassoBench [59].
The Lasso-DNA benchmark is a biomedical classification task, taking binarized
DNA sequences as input [59].

svg-inkscape/lasso-dna_svg-tex.pdf_tex

Figure 7:  BAxUS and baselines on Lasso-DNA. As before, BAxUS makes
considerable progress in the beginning and converges faster than TuRBO and
CMA-ES.

Figure 7 shows the mean performance of BAxUS on the Lasso-DNA. Each line shows
the incumbent mean; the shaded regions around the lines show one standard
error. We see the same qualitative behavior as discussed in Section 4: BAxUS
reaches a good initial solution faster than any other method.

After a worse start, TuRBO finds slightly better solutions than BAxUS.

###  C.3 Evaluation on additional MuJoCo benchmarks

We evaluate BAxUS with the same baselines as in Section 4. We use the
implementation of [70]111https://github.com/facebookresearch/LA-
MCTS/blob/main/example/mujuco/functions.py, last accessed: 06/10/2022, in
particular we use the Gym environments Ant, Swimmer, Half-Cheetah, Hopper,
Walker 2D, and Humanoid 2D, all in version 2. For the 6392-dimensional
Humanoid benchmark, we limit the target dimensionality of BAxUS to 1000
dimensions to keep the split budgets sufficiently large. For the other
benchmarks, we do not limit the target dimensionality. Due to the high
variance between runs, we ran all methods for 50 different runs.

We summarize the results in Fig. 8. We observe that BAxUS obtains equal or
better solutions than the competitors on four out of six benchmarks. On the
120-dimensional Walker benchmark, BAxUS is the clear winner, followed by TuRBO
and CMA-ES. On the 888-dimensional Ant benchmark, HeSBO finds the best
solutions, followed by BAxUS that outperforms TuRBO and CMA-ES. For the
102-dimensional Half-Cheetah, TuRBO produces the best solutions, followed by
CMA-ES and BAxUS; here, the subspace-based approaches (Alebo and HeSBO) find
significantly worse solutions. For the 6392-dimensional Humanoid 2D, CMA-ES
obtains the best solutions, followed by BAxUS, Alebo, and HeSBO.

svg-inkscape/mujoco_svg-tex.pdf_tex

Figure 8: An evaluation of BAxUS and other methods on high-dimensional test
problems of MuJoCo.

##  Appendix D The nested family of random embeddings

We describe the method for increasing the target dimensionality under the
retention of the observations. Suppose that we have collected $n$ observations
and are in target dimension $d$ when Algorithm 2 is invoked. Algorithm 2 loops
over the target dimensions $1,\ldots,d$. For each target dimension, the
contributing input dimensions are randomly re-assigned to new bins of given
sizes. This can, for example, be realized by first randomly permuting the list
of contributing input dimensions, and then dividing the list into $b+1$ chunks
(bins). If the number of contributing input dimensions is less than $b+1$
(remember that $b$ is the number of _new_ bins), then it is not possible to
re-assign the contributing input dimensions to $b+1$ bins. Therefore, we re-
assign the contributing input dimensions to $\hat{b}=\min(b,l_{s}-1)$ new
bins, where $l_{s}$ is the number of contributing input dimensions to the
$s$-th target dimension. This also ensures that the target dimension never
grows larger than $D$ in the BAxUS embedding. We evenly distribute the $l_{s}$
contributing input dimensions across the $\hat{b}$ bins by again using the
BAxUS embedding. This gives a smaller (in terms of number of rows) projection
matrix $\tilde{S}^{\intercal}$ which we finally use to update $S^{\intercal}$:

Algorithm 2 Observation-preserving embedding increase

transposed embedding matrix $S^{\intercal}$, number of new bins per latent
dimension $b$, observed points $Y\in[-1,1]^{n\times d}$.

updated transposed embedding matrix $S^{\intercal}$ and updated observation
matrix $Y$

for $s\in\\{1,\ldots,d\\}$ do

$\bm{D}^{s}\leftarrow$ contributing input dimensions of $s$-th latent
dimension of the current embedding

$l_{s}\leftarrow|\bm{D}^{s}|$

$\hat{b}\leftarrow\min(b,l_{s}-1)$ $\triangleright$ If $l_{s}-1<b$, we can at
most create $l_{s}-1$ new bins.

Copy and append $s$-th column of $Y$ $\hat{b}$ times at the end of $Y$.

Add $\hat{b}$ zero columns at the end of $S^{\intercal}$.

$\bm{\sigma}\leftarrow$ signs of dimensions $\in\bm{D}^{s}$.

$\tilde{S}^{\intercal}\leftarrow$ Baxus-Embedding($l_{s}$, $\hat{b}+1$)
$\triangleright$ Re-assign input dims. equally222Equally means that all
$\hat{b}+1$ bins have roughly the same number of contributing input
dimensions. The number of contributing input dimensions to the different bins
differ by at most 1., $\tilde{S}^{\intercal}\in\\{0,\pm
1\\}^{l_{s}\times\hat{b}+1}$

for $i\in\\{1,\ldots,l_{s}\\},j\in\\{1,\ldots,\hat{b}+1\\}$ do

if $\tilde{S}^{\intercal}_{ij}\neq 0$ then

if $j>1$ then $\triangleright$ Move values that fall into new bins to end of
$S^{\intercal}$.

$S^{\intercal}_{\bm{D}^{s}_{i},\hat{d}-\hat{b}-1+j}\leftarrow\bm{\sigma}_{i}$
$\triangleright$ $\hat{d}$: columns of $S^{\intercal}$

$S^{\intercal}_{\bm{D}^{s}_{i},s}\leftarrow 0$ $\triangleright$ Set value in
“old” column to zero.

Return $S^{\intercal}$ and $Y$.

##  Appendix E Additional details on the implementation and the empirical
evaluation

We benchmark against SAASBO, TuRBO, HeSBO, Alebo, and CMA-ES:

  * •

For SAASBO, we use the implementation from [20]
(https://github.com/martinjankowiak/saasbo, license: none, last accessed:
05/09/2022).

  * •

For TuRBO, we use the implementation from [22] (https://github.com/uber-
research/TuRBO, license: Uber, last accessed: 05/09/2022).

  * •

For HeSBO and Alebo, we use the implementation from [40]
(https://github.com/facebookresearch/alebo, license: CC BY-NC 4.0, last
accessed: 05/09/2022).

  * •

For the Lasso benchmarks, we use the implementation from [59]
(https://github.com/ksehic/LassoBench, license: MIT and BSD-3-Clause, last
accessed: 05/09/2022).

We use GPyTorch (version 1.8.1) to train the GP with the following setup: We
place a top-hat prior on the Gaussian likelihood noise, the signal variance,
and the length scales of the Matérn 5/2 ARD kernel. The interval for the noise
is $[0.005,0.2]$, for the signal variance $[0.05,20]$, and for the
lengthscales $[0.005,10]$.

We evaluate on the synthetic Branin2333See
https://www.sfu.ca/~ssurjano/branin.html, last accessed: 05/09/2022 and
Hartmann6444See https://www.sfu.ca/~ssurjano/hart6.html, last accessed:
05/09/2022 functions. Since we augment the function with dummy dimensions, we
use the same domain for $x_{1}$ and $x_{2}$, namely $[-5,15]^{D}$ for Branin2
and $[0,1]^{D}$ for Hartmann6.

Similar to TuRBO, we sample a $\min(100d_{n},5000)$-element Sobol sequence on
which we minimize the posterior sample. To maximize the marginal log-
likelihood of the GP, we sample 100 initial hyperparameter configurations. The
ten best samples are further optimized using the Adam optimizer for $50$
steps.

We ran the experiments for approximately $15{,}000$ core hours on Intel Xeon
Gold 6130 CPUs provided by a compute cluster.

  *[BO]: Bayesian optimization
  *[HDBO]: high-dimensional Bayesian optimization
  *[VAE]: variational autoencoder
  *[GP]: Gaussian process
  *[TRs]: trust region
  *[TR]: trust region
  *[GPs]: Gaussian process