# Bayesian Optimistic Optimisation with Exponentially Decaying Regret

Hung Tran-The  Sunil Gupta  Santu Rana  Svetha Venkatesh

###### Abstract

Bayesian optimisation (BO) is a well-known efficient algorithm for finding the
global optimum of expensive, black-box functions. The current practical BO
algorithms have regret bounds ranging from
$\mathcal{O}(\frac{logN}{\sqrt{N}})$ to $\mathcal{O}(e^{-\sqrt{N}})$, where
$N$ is the number of evaluations. This paper explores the possibility of
improving the regret bound in the noiseless setting by intertwining concepts
from BO and tree-based optimistic optimisation which are based on partitioning
the search space. We propose the BOO algorithm, a first practical approach
which can achieve an exponential regret bound with order
$\mathcal{O}(N^{-\sqrt{N}})$ under the assumption that the objective function
is sampled from a Gaussian process with a Matérn kernel with smoothness
parameter $\nu>4+\frac{D}{2}$, where $D$ is the number of dimensions. We
perform experiments on optimisation of various synthetic functions and machine
learning hyperparameter tuning tasks and show that our algorithm outperforms
baselines.

Machine Learning, ICML

##  1 Introduction

We consider a global optimisation problem whose goal is to maximise $f(x)$
subject to $x\in\mathcal{X}\subset\mathbb{R}^{D}$, where $D$ is the number of
dimensions and $f$ is an expensive black-box functions that can only be
evaluated point-wise. The performance of a global optimisation algorithm is
typically evaluated using _simple regret_ , which is given as

$r_{N}=\text{sup}_{x\in\mathcal{X}}f(x)-\text{max}_{1\leq i\leq N}f(x_{i})$

where $x_{i}$ is the $i$-th sample, and $N$ is the number of function
evaluations. In this paper, we consider the case that the evaluation of $f$ is
noiseless.

Bayesian optimisation (BO) provides an efficient model-based solution for
global optimisation. The core idea is to transform a global optimisation
problem into a sequence of auxiliary optimisation problems of a surrogate
function called the acquisition function. The acquisition function is built
using a model of the function through its limited observations and recommends
the next function evaluation location. Regret analysis has been done for many
existing BO algorithms, and typically the regret is sub-linear following order
$\mathcal{O}\left(\sqrt{\frac{logN}{N}}\right)$ (Srinivas et al., 2012; Russo
et al., 2018). More recently, (Vakili et al., 2020) have improved this to
$\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$ under the noiseless setting.
However, a limitation of BO is that performing such a sequence of auxiliary
optimisation problems is expensive.

De Freitas et al. (2012) introduced a Gaussian process (GP) based scheme
called $\delta$-cover sampling as an alternative to the acquisition function
to trade-off exploration and exploitation. Their method samples the objective
function using a finite lattice within a feasible region and doubles the
density of points in the lattice at each iteration. However, even in moderate
dimensions, their algorithm is impractical since the lattice quickly becomes
too large to be sampled in a reasonable amount of time (as pointed out by
(Wang et al., 2014; Kawaguchi et al., 2016)).

An alternative practical approach for global optimisation is to consider tree-
based optimistic optimisation as in (Munos, 2011; Floudas, 2005). These
algorithms partition the search space into finer regions by building a
hierarchical tree. The key is to have efficient strategies to identify a set
of nodes that may contain the global optimum and then to successively reduce
and refine the search space to reach closer to the optimum. As example, DIRECT
algorithm (Jones et al., 1993) partitions the search space assuming a global
Lipschitz constant. Simultaneous Optimistic Optimisation (SOO) algorithm
(Munos, 2011) generalises this by using only local Lipschitz conditions
without requiring the knowledge of the Lipschitz global-metric. Under certain
assumptions, this algorithm shows the possibility of achieving an
exponentially diminishing regret $\mathcal{O}(e^{-\sqrt{N}})$. An additional
advantage of such algorithms is that we do not need to perform an auxiliary
non-convex optimisation of the acquisition functions as in BO which may be
difficult in cases that are high-dimensional (Kandasamy, 2015; Tran-The et
al., 2020) or have unbounded search spaces (Tran-The et al., 2020). However,
these optimistic algorithms are model-free, that is, they do not utilise the
function observations efficiently.

A natural extension to improve the sample efficiency is to incorporate a model
of the objective function into the optimistic strategy. Indeed, works that do
this include BaMSOO (Wang et al., 2014) and IMGPO (Kawaguchi et al., 2016).
Using a Gaussian process (Rasmussen & Williams, 2005) as a model of the
objective function, both algorithms avoid to evaluate the objective function
for points known to be sub-optimal with high probability. While BaMSOO has a
sub-linear regret bound, IMGPO can achieve an exponential regret bound.
However, despite this, IMGPO has not still overcome the worst-case regret
bound order $\mathcal{O}(e^{-\sqrt{N}})$ of SOO which does not use any model
of the objective function. A natural question is that _is there a practical
algorithm for global optimisation that can break this regret bound order
$\mathcal{O}(e^{-\sqrt{N}})$ under a mild assumption_?

In this paper, we propose a novel approach, which combines the strengths of
the tree-based optimistic optimisation methods and Bayesian optimisation to
achieve an improved regret bound $\mathcal{O}(N^{-\sqrt{N}})$ in the worst
case. Our main contributions are summarised as follows:

  * •

A GP-based optimistic optimisation algorithm using novel partitioning
procedure and function sampling;

  * •

Our algorithm has a worst-case regret bound of $\mathcal{O}(N^{-\sqrt{N}})$ in
the noiseless setting under the assumption that the objective function is
sampled from a Gaussian process with a Matérn kernel with smoothness parameter
$\nu>4+\frac{D}{2}$, where $N$ is the number of evaluations and $D$ is the
number of dimensions. Our algorithm avoids an auxiliary optimisation step at
each iteration in BO, and avoids the $\delta$-cover sampling in the approach
of De Freitas et al. (2012). To our best knowledge, without using an
$\delta$-cover sampling procedure which is impractical, this is the tightest
regret bound for BO algorithms;

  * •

To validate our algorithm in practice, we perform experiments on optimisation
of various synthetic functions and machine learning hyperparameter tuning
tasks and show that our algorithm outperforms baselines.

##  2 Related Works

In this section, we briefly review some related work additional to the work
mentioned in section 1.

In Bayesian optimisation literature, there exist also some works that use
tree-structure for the search space. While Wang et al. (2018) used a Mondrian
tree to partition the search space, a recent work by (Wang et al., 2020) used
a dynamic tree via $K$-means algorithm. However, these works focused on
improving BO’s performance empirically for large-scale data sets or high-
dimensions rather than to improve the regret bound.

There are two viewpoints for BO, Bayesian and non-Bayesian as pointed out by
Scarlett et al. (2017). In the non-Bayesian viewpoint, the function is treated
as fixed and unknown, and assumed to lie in a reproducing kernel Hilbert space
(RKHS). Under this viewpoint, Chowdhury & Gopalan (2017); Janz et al. (2020)
provided upper regret bounds while Scarlett et al. (2017) provided lower
regret bounds for BO with Matérn kernels. These bounds all are sub-linear.
Otherwise, in the Bayesian viewpoint where we assume that the underlying
function is random according to a GP, Kawaguchi et al. (2016) showed that BO
can obtain an exponential convergence rate. In this paper, we focus on the
Bayesian viewpoint and break the regret bound order of IMGPO (Kawaguchi et
al., 2016) under some mild assumptions.

The optimistic optimisation methods have also been extended to adapt to
different problem settings e.g., noisy setting (Valko et al., 2013; Grill et
al., 2015), high dimensional spaces (Qian & Yu, 2016; Al-Dujaili & Suresh,
2017), multi-objective optimisation (Al-Dujaili & Suresh, 2018) or multi-
fidelity black-box optimisation (Sen et al., 2018). Our work can be
complementary to these works and the integration of our solution with them may
be promising to improve their regret bounds.

##  3 Preliminaries

##### Bayesian Optimisation

The standard BO routine consists of two key steps: estimating the black-box
function from observations and maximizing an acquisition function to suggest
next function evaluation point.

Gaussian process is a popular choice for the first step. Formally, we have
$f(x)\sim\mathcal{GP}(m(x),k(x,x^{\prime}))$ where $m(x)$ and
$k(x,x^{\prime})$ are the mean and the covariance (or kernel) functions. Given
a set of observations $\mathcal{D}_{1:p}=\\{x_{i},y_{i}\\}_{i=1}^{p}$ under a
noiseless observation model $y_{i}=f(x_{i})$, the predictive distribution can
be derived as
$P(f(x)|\mathcal{D}_{1:p},x)=\mathcal{N}(\mu_{p+1}(x),\sigma_{p+1}^{2}(x))$,
where $\mu_{p+1}(x)=\textbf{k}^{T}K{}^{-1}\textbf{y}+m(x)$ and
$\sigma_{p+1}^{2}(x)=k(x,x)-\text{{k}}^{T}K^{-1}\textbf{k}$. In the above
expression we define $\textbf{k }=[k(x,x_{1}),...,k(x,x_{p})]^{T}$,
$K=[k(x_{i},x_{j})]_{1\leq i,j\leq p}$ and $\textbf{y}=[y_{1},\ldots,y_{p}]$.

Some well-known popular acquisition functions for the second step include
upper confidence bound (GP-UCB)(Srinivas et al., 2012), expected improvement
(EI) (Bull, 2011), Thompson sampling (TS) (Russo et al., 2018) and predictive
entropy search (PES) (Hernández-Lobato et al., 2014). Among them, GP-UCB is
given as $\mathcal{U}_{p}(x)=\mu_{p}(x)+\beta_{p}^{1/2}\sigma_{p}(x)$, where
$\beta_{p}$ is the parameter balancing between the exploration and
exploitation. We will use GP-UCB in our tree expansion scheme to determine the
node to be expanded.

In this paper, we focus on the popular class of Matérn kernels for Gaussian
process which is defined as

$k_{\nu}(x,x^{\prime})=\frac{\sigma^{2}}{\Gamma(\nu)2^{\nu-1}}(\frac{||x-x^{\prime}||_{2}}{\lambda})^{\nu}\mathcal{B}_{\nu}(\frac{||x-x^{\prime}||_{2}}{\lambda}),$

where $\Gamma$ denotes the Gamma function, $\mathcal{B}_{\nu}$ denotes the
modified Bessel function of the second kind, $\nu$ is a parameter controlling
the smoothness of the function and $\sigma^{2},\lambda$ are hyper-parameters
of the kernel. We assume that the hyper-parameters are fixed and known in
advance. However, our work can also be extended for the unknown hyper-
parameters of the Matérn kernel as in (Vakili et al., 2020) (for Bayesian
setting). Important special cases of $\nu$ include $\nu=\frac{1}{2}$ that
corresponds to the exponential kernel and $\nu\rightarrow\infty$ that
corresponds to the squared exponential kernel. The Matérn kernel is of
particular practical significance, since it offers a more suitable set of
assumptions for the modeling and optimisation of physical quantities ((Stein,
1999)).

##### Hierarchical Partition

We use the hierarchical partition of the search space as in (Munos, 2011).
Given a branch factor $m$, for any depth $h$, the search space $\mathcal{X}$
is partitioned into a set of $m^{h}$ sets $A_{h,i}$ (called cells), where
$0\leq i\leq m^{h}-1$. This partitioning is represented as a $m$-ary tree
structure where each cell $A_{h,i}$ corresponds to a node $(h,i)$. A node
$(h,i)$ has $m$ children nodes, indexed as $\\{(h+1,i_{j})\\}_{1\leq j\leq
m}$. The children nodes $\\{(h+1,i_{j}),1\leq j\leq m\\}$ form a partition of
the parent’s node $(h,i)$. The root of the tree corresponds to the whole
domain $\mathcal{X}$. The center of a cell $A_{h,i}$ is denoted by $c_{h,i}$
where $f$ and its upper confidence bound is evaluated.

##  4 Proposed BOO algorithm

###  4.1 Motivation

Most of tree-based optimistic optimisation algorithms like SOO, StoSOO (Valko
et al., 2013), BaMSOO and IMGPO face a _strict negative correlation_ between
the branch factor $m$ and the number of tree expansions given a fixed function
evaluation budget $N$. On the one hand, using a larger $m$ makes a tree finer,
which helps to reach closer to the optimum. On the other hand, having more
expansions in the tree also allows to create finer partitions in multiple
regions of the space. Thus both a larger branch factor and a larger number of
tree expansions allow an algorithm to get closer to the optimum. However, each
time a node is expanded, the algorithms such as SOO, StoSOO spend $m$ function
evaluations - one for each of the $m$ children and thus the number of tree
expansions is restricted to at most $\left\lfloor\frac{N}{m}\right\rfloor$.
Thus when $m$ increases, the number of tree expansions decreases. We call this
phenomenal the _strict negative correlation_ of tree-based optimistic
optimisation algorithms.

Using the assumption that the objective function is sampled from a GP prior,
BaMSOO and IMGPO reduce this negative correlation by evaluating the function
only at the children where the UCB value is greater than the best function
value observed thus far ($f^{+}$). However, the number of expansions is still
tied to the branch factor lying between $\left\lfloor\frac{N}{m}\right\rfloor$
and $N$.

We present a new approach which permits to untie the branch factor $m$ from
the number of tree expansions and hence, solves the strict negative
correlation of tree-based optimistic optimisation algorithms. By doing so, we
can exploit the use of a large $m$ to achieve finer partitions and achieves a
regret bound $\mathcal{O}(N^{-\sqrt{N}})$ improving upon current BO
algorithms.

###  4.2 BOO algorithm

Our algorithm is described in Algorithm 3 where we assume that the objective
function is a sample from GP as in Bayesian optimisation, however our approach
follows the principle of SOO which uses a hierarchical partitioning of the
search space $\mathcal{X}$. The main difference of the proposed BOO and
previous works lies in the partitioning procedure, the tree expansion
mechanism and the function sampling strategy.

Algorithm 1 The BOO Algorithm

Input: An evaluation budget $N$ and parameters $m,a,b\in\mathbb{N}$.
Initialisation: Set $\mathcal{T}_{0}=\\{(0,0)\\}$ (root node). Set $p=1$.
Sample initial points to build $\mathcal{D}_{0}$.

1: while True do

2: Set $v_{max}=-\infty$

3: for $h=0$ to min(depth($\mathcal{T}_{p}$), $h_{max}(p)$) do

4: Among all leaves $(h,j)$ of depth $h$, select
$(h,i)\in\text{argmax}_{(h,j)\in\mathcal{L}}\mathcal{U}_{p}(c_{h,j})$

5: if $\mathcal{U}_{p}(c_{h,i})\geq v_{max}$ then

6: Expand node $(h,i)$ by adding $m$ children $(h+1,i_{j})$ to tree
$\mathcal{T}_{p}$, using partitioning procedure $P(m;a,b)$

7: Evaluate $f(c_{h,i})$

8: Augment the data
$\mathcal{D}_{p}=\\{\mathcal{D}_{p-1},((c_{h,i},f(c_{h,i}))\\}$.

9: Fit the Gaussian process using $\mathcal{D}_{p}$

10: Update $v_{max}=\text{max}\\{f(c_{h,i}),v_{max}\\}$

11: Update $p=p+1$

12: if $p=N$ then

13: Return
$x(N)=\text{argmax}_{\\{c_{h,i})|(c_{h,i},f(c_{h,i}))\in\mathcal{D}_{N}\\}}f(c_{h,i})$

14: end if

15: end if

16: end for

17: end while

Figure 1: An illustration of partitioning procedure for $m=8$: (a) SOO methods
partition $a$ cell by dividing the longest side into $m$ equal parts; (b) our
method sets $m=a^{b}$ and partitions $a$ cell by dividing $b=3$ longest sides
into $a=2$ equal parts.

Figure 2: SOO samples the function at all $m$ children nodes while our
sampling strategy samples the function only at the parent node (the node
selected for expansion). As a result, our strategy requires only one function
evaluation irrespective of the value of $m$.

.

##### Partitioning Procedure

Unlike SOO based algorithms including BaMSOO and IMGPO which often divide a
cell into $m$ children cells along the longest side of the cell, we use a
novel partitioning procedure which exploits the particular decomposition of
the branch factor $m$. Given any $a\geq 2$, $1\leq b\leq D$ and $m=a^{b}$,
where $a,b,m\in\mathbb{N}$, our partitioning procedure, denoted by $P(m;a,b)$,
divides the cell along its $b$ longest dimensions into $a$ new cells (see
Figure 1). When $b=1$ then our procedure becomes simply the traditional
partitioning procedure as in SOO. When $b=D$, all dimensions of the cell are
divided which benefits our algorithm. We will explain this further in our
convergence analysis.

##### Tree Expansion Mechanism

The algorithm incrementally builds a tree $\mathcal{T}_{p}$ starting with a
node $\mathcal{T}_{0}=\\{(0,0)\\}$ for $p=1...N$, where $N$ is the evaluation
budget. At depth $h$, among all the leaf nodes, denoted by $\mathcal{L}$ of
the current tree, the algorithm selects the node with the maximum GP-UCB
value, defined as
$\mathcal{U}_{p}(c)=\mu_{p}(c)+\beta_{p}^{1/2}\sigma_{p}(c)$, where
$\beta_{p}^{1/2}=\sqrt{2log(\pi^{2}p^{3}/3\eta)}$ and $\eta\in(0,1)$. The tree
is expanded by adding $m$ children nodes to the selected node. To force the
depth of tree after $p$ expansions, we use a function $h_{max}(p)$ which is
also a parameter of the algorithm. We note that the algorithm uses GP-UCB
acquisition function to determine the candidate node, but it only performs a
maximisation on a finite, discrete set comprising the leaf nodes at the depth
in consideration.

##### Function Sampling Strategy

Once the node is selected for expansion, unlike previous works that evaluate
the objective function at children nodes, we propose to evaluate the objective
function only at that node without evaluating the function at its children
(see Figure 2).

By this sampling scheme, our algorithm allows to untie the branch factor $m$
from the number of tree expansions. As a result, it allows the use of a large
$m$ to achieve finer partitions and to reach closer to the optimum. In fact,
using a small $m$ as in previous optimistic optimisation methods also reaches
finer partitions, however it needs a large number of tree expansions, and thus
still needs a large number of evaluations. Consider an example where $m=2^{D}$
with $a=2$ and $b=D$. Using the partitioning procedure $P(m;2,D)$, our
algorithm partitions a node into $m$ cells with the same granularity. To reach
the same granularity as our method, SOO algorithm can use the partitioning
with $m=2$ and repeat it $D$ times. However, by this way, SOO always spends
$2^{D}$ function evaluations while our algorithm only uses one evaluation.
BamSOO and IMGPO algorithms have the similar problem although they improve
over SOO - they only evaluate the function at nodes $c$ that satisfy the
condition $\mathcal{U}(c)>f^{+}$ (best function value observed thus far) is
satisfied. In summary, to reach the same granularity as our method, these
algorithms need to spend $m^{\prime}$ evaluations, where $1\leq m^{\prime}\leq
2^{D}$ depending on the number of nodes c satisfying the condition
$\mathcal{U}(c)>f^{+}$. In contrast, our algorithm only spends one evaluation
for all cases regardless of the value of $m$. Together with our partitioning
procedure, we leverage this benefit to improve the regret bound for
optimisation.

##  5 Convergence Analysis

In this section, we theoretically analyse the convergence of our algorithm. We
start with assumptions about function $f$.

###  5.1 Assumptions

To guarantee the correctness of our algorithm, we use the following
assumptions.

######  Assumption 1.

The function $f$ sampled from $\text{GP}(0,k_{\nu})$, that is a zero mean GP
with a Matérn kernel $k_{\nu}$ with $\nu>4+\frac{D}{2}$, where $D$ is the
number of dimensions.

######  Assumption 2.

The objective function $f$ has a unique global maximum $x^{*}$.

The assumption of a unique maximiser holds with probability one in most non-
trivial cases (De Freitas et al., 2012). Under such assumptions, we obtain the
following property.

######  Property 1.

Assume that the function $f$ is sampled from GP($0,k_{\nu}$) satisfying the
Assumption 1 and 2. Then,

  1. 1.

$f(x^{*})-f(x)\leq L_{1}||x^{*}-x||^{2}_{2}$ for every $x\in\mathcal{X}$, for
some constant $L_{1}>0$,

  2. 2.

$f(x)\leq f(x^{*})-L_{2}||x-x^{*}||^{2}$ for every
$x\in\mathcal{B}(x^{*},\theta)$ for some constants $L_{2},\theta>0$,

  3. 3.

$f(x^{*})-\text{max}_{x\in\mathcal{X}\setminus\mathcal{B}(x^{*},\theta)}f(x)>\epsilon_{0}$
for some $\epsilon_{0}>0$.

We note that all constants $L_{1},L_{2}$ and $\epsilon_{0}$ are _unknown_. The
Property 1.2 can be considered as the quadratic behavior of the objective
function in the neighborhood of the optimum. This property holds for every
Matérn kernel with $\nu>2$ as argued by (De Freitas et al., 2012) and (Wang et
al., 2014). The result closest to ours is that of IMGPO (Kawaguchi et al.,
2016) that achieves an exponential regret bound $e^{-\sqrt{N}}$. However,
their work requires a type of quadratic behavior in the whole search space (as
represented in Assumption 2 in their paper) which is quite strong. Compared to
it, our assumption is weaker which only requires the quadratic behavior of the
function in a neighborhood of the optimum. Despite this, we will show that our
algorithm can improve their regret bound.

###  5.2 Convergence Analysis

For the theoretical guarantee, we follow the principle of the optimism in the
face of uncertainty as in (Munos, 2011). The basic idea is to construct the
set of expandable nodes at each depth $h$, called the expansion set. We do
this in Section 5.2.1. Quantifying the size of the expansion set is a key step
in this principle. We do this in Section 5.2.2. Finally, by using upper bounds
on the size of these sets, we derive the regret bounds in Section 5.2.3. All
proofs are provided in the Supplementary Material.

####  5.2.1 The expansion set

######  Definition 1.

Let the expansion set at depth $h$ be the set of all nodes that could be
potentially expanded before the optimal node at depth $h$ is selected for
expansion in Algorithm 1. Formally,

$I_{h}=\\{(h,i)|\exists h\leq p\leq N:\mathcal{U}_{p}(c_{h,i})\geq
f(x^{*})-\delta(h;a,b)\\}$

, where $\delta(h;a,b)$ is defined as

$\delta(h;a,b)=L_{1}Da^{-2\lfloor\frac{bh}{D}\rfloor},$

and $\mathcal{U}_{p}(c_{h,i})$ is the upper confidence bound at the center
$c_{h,i}$ of node $(h,i)$ after $p$ expansions.

We note that even though this definition uses $\delta(h;a,b)$ that depends on
the unknown metric $L_{1}$, our BOO algorithm does not need to know this
information. The reason we use
$\delta(h;a,b)=L_{1}Da^{-2\lfloor\frac{bh}{D}\rfloor}$ lies in the following
three observations of our partitioning procedure $P(m;a,b)$ in the search
space $\mathcal{X}$. We assume here that $\mathcal{X}=[0,1]^{D}$ (this can
always be achieved by scaling).

######  Lemma 1.

Given a cell $A_{h,i}$ at depth $h$, we have that

  1. 1.

the longest side of cell $A_{h,i}$ is at most
$a^{-\lfloor\frac{bh}{D}\rfloor}$, and

  2. 2.

the smallest side of cell $A_{h,i}$ is at least
$a^{-\lceil\frac{bh}{D}\rceil}$.

######  Lemma 2.

Given a cell $A_{h,i}$ at depth $h$, then we have that $\text{sup}_{x\in
A_{h,i}}||x-c_{h,i}||\leq D^{1/2}a^{-\lfloor\frac{bh}{D}\rfloor},$ where
$c_{h,i}$ is the center of cell $A_{h,i}$.

###### Proof.

By Lemma 1, the longest side of a cell at depth $h$ is at most
$a^{-\lfloor\frac{bh}{D}\rfloor}$. Therefore, $\text{sup}_{x\in
A_{h,i}}||x-c_{h,i}||\leq\sqrt{Da^{-2\lfloor\frac{bh}{D}\rfloor}}=D^{1/2}a^{-\lfloor\frac{bh}{D}\rfloor}$.
∎

We denote a node $(h,i^{*})$ as the _optimal node_ at depth $h$ if $x^{*}$
belongs to the cell $A_{h,i^{*}}$.

######  Lemma 3.

At a depth $h$, we have that $f(c_{h,i^{*}})\geq f(x^{*})-\delta(h;a,b).$

###### Proof.

By Property 1, $f(x^{*})-f(c_{h,i^{*}})\leq L_{1}||x^{*}-c_{h,i^{*}}||^{2}$.
By Lemma 2, $||x^{*}-c_{h,i^{*}}||\leq
D^{1/2}a^{-\lfloor\frac{bh}{D}\rfloor}=\sqrt{\delta(h;a,b)}/L_{1}$. Thus,
$f(x^{*})-f(c_{h,i^{*}})\leq L_{1}||x^{*}-c_{h,i^{*}}||^{2}\leq\delta(h;a,b)$.
∎

By Lemma 3 and the fact that $\mathcal{U}_{p}(c_{h,i})\geq f(c_{h,i})$ with
high probability, we have that $\mathcal{U}_{p}(c_{h,i})\geq
f(x^{*})-\delta(h;a,b)$ with high probability. It deduces that the global
maximum $x^{*}$ belongs to the expansion set at every depth with high
probability.

The expansion set at a depth $h$ in our approach differs from the ones in
works of (Munos, 2011; Wang et al., 2014; Kawaguchi et al., 2016) which is
defined as $I_{h}=\\{(h,i)|f(c_{h,i})\geq f(x^{*})-\delta(h;a,b)\\}$. More
precisely, set $I_{h}$ of their works is a smaller set than the set $I_{h}$ in
our work defined above because we have $\mathcal{U}_{p}(c_{h,i})\geq
f(c_{h,i})$ with high probability. This bigger $I_{h}$ directly might involve
unnecessary explorations and therefore, the algorithm may incur higher regret
than that of BamSOO and IMGPO. However, we solve this challenge by leveraging
our new partitioning procedure $P(m;a,b)$ with $b=D$, and some results from
(Kanagawa et al., 2018; Vakili et al., 2020) which are presented in the
following section.

####  5.2.2 An upper bound on the size of the expansion set

To quantify $|I_{h}|$, we use a concept called the near-optimality dimension
as in (Munos, 2011). In our context, we define the near-optimality dimension
as follows:

######  Definition 2.

The near-optimality dimension is defined as the smallest $d\geq 0$ such that
there exists $C>0$ such that for any $\delta(h;a,b)$, the maximal number of
disjoint balls the with largest size in a cell at depth $h$ with center in
$\mathcal{X}_{\delta(h;a,b)}$ is less than $C(\delta(h;a,b))^{d}$, where
$\mathcal{X}_{\delta(h;a,b)}=\\{x\in\mathcal{X}|\text{ }\mathcal{U}_{p}(x)\geq
f(x^{*})-\delta(h;a,b)\\}$.

With partitioning procedure $P(m;a,b)$ where $a=\mathcal{O}(N^{1/D})$ with
$b=D$, we will show $d=0$ (which is equivalent to prove $|I_{h}|\leq C$)
through the following Theorem 1.

######  Theorem 1 (Bound on Expansion Set Size).

Consider a partitioning procedure $P(m;a,b)$ where $a=\mathcal{O}(N^{1/D})$
and $b=D$. Then there exist constants $N_{1}>0$ and $C>0$ such that for every
for $N\geq N_{1}$ and $h\geq 2$, we have, $|I_{h}|\leq C$.

To prove Theorem 1, we estimate a bound on variance function $\sigma_{p}$ in
terms of the function $\delta(h-1;a,b)$ through the following lemma.

######  Lemma 4.

Assuming that node $(h,i)$ at the depth $h\geq 1$ is evaluated at the $p$-th
evaluation, where $p\geq h$. Thus,

$\sigma_{p}(c_{h,i})\leq C_{1}(\delta(h-1;a,b))^{\nu/2-D/4},$

where $C_{1}$ is a constant.

This lemma holds by applying some results about the closeness between the
samples from a GP (in Bayesian setting) and the elements of an RKHS (in non-
Bayesian setting) as in (Kanagawa et al., 2018; Vakili et al., 2020), to the
structured search space as in our approach. This technique is novel compared
to BaMSOO and IMGPO’s ones. We refer to our Supplementary Material in Section
3.

Using this result and the condition $\nu>4+D/2$, we achieve a constant bound
on the size of set $I_{h}$.

####  5.2.3 Bounding the simple regret

Next we use the upper bound on $|I_{h}|$ at every depth $h$ to derive a bound
on the simple regret $r_{N}$.

Let us use $h_{p}^{*}$ to denote the depth of the deepest expanded node in the
branch containing $x^{*}$ after $p$ expansions. Similar to the lemma 2 in
(Munos, 2011), we can bound the sum of $|I_{h}|$ as follows.

######  Lemma 5.

Assume that $f(c)\leq\mathcal{U}(c)$ for all centers $c$ of optimal nodes at
all depths $0\leq h\leq h_{max}(p)$ after $p$ expansions. Then for any depth
$0\leq h\leq h_{max}(p)$, whenever $p\geq h_{max}(p)\sum_{i=0}^{h}|I_{i}|$, we
have $h_{p}^{*}\geq h$.

We use $A_{p}$ to denote the set of all points evaluated by the algorithm and
all centers of optimal nodes of the tree $\mathcal{T}_{p}$ after $p$
evaluations.

######  Lemma 6.

Pick a $\eta\in(0,1)$. Set $\beta_{p}=2log(\pi^{2}p^{3}/3\eta)$ and
$\mathcal{L}_{p}(c)=\mu_{p}(c)-\beta^{1/2}_{p}\sigma_{p}(c)$. With probability
$1-\eta$, we have

$\mathcal{L}_{p}(c)\leq f(c)\leq\mathcal{U}_{p}(c),$

for every $p\geq 1$ and for every $c\in A_{p}$.

We now use Lemmas 3-6 to derive a simple regret for the proposed algorithm.
Here, the simple regret $r_{p}$ after $p$ expansions is defined as
$r_{p}=f(x^{*})-\text{max}_{1\leq i\leq p}f(x_{i})$, where $x_{i}$ is the
$i$-th sample.

######  Theorem 2 (Regret Bound).

Assume that there is a partitioning procedure $P(m;a,b)$ where
$a=\mathcal{O}(N^{1/D})$, $b=D$ and $2\leq m<\sqrt{N}-1$. Let the depth
function $h_{max}(p)=\sqrt{p}$. We consider $m^{2}<p\leq N$, and define $h(p)$
as the smallest integer $h$ such that $h\geq\frac{\sqrt{p}-m-1}{C}+2,$ where
$C$ is the constant defined by Theorem 1. Pick a $\eta\in(0,1)$. Then for
every $N\geq N_{1}$, the loss is bounded as

$\displaystyle r_{p}$ $\displaystyle\leq$
$\displaystyle\delta(\text{min}\\{h(p),\sqrt{p}+1\\};a,b)+$ $\displaystyle+$
$\displaystyle
4C_{1}\beta^{1/2}_{p}(\delta(\text{min}\\{h(p)-1,\sqrt{p}\\};a,b))^{\nu/2-D/4},$

with probability $1-\eta$, where $N_{1}$ is the constant defined in Theorem 1,
$C_{1}$ is the constant defined in lemma 4 and
$\beta_{N}=\sqrt{2log(\pi^{2}N^{3}/3\eta)}$.

###### Proof.

By Theorem 1, the definition of $h(p)$ and the facts that $|I_{0}|=1$ and
$|I_{1}|\leq m$, we have

$\displaystyle\sum_{l=0}^{h(p)-1}|I_{l}|$ $\displaystyle=$
$\displaystyle|I_{0}|+|I_{1}|+(|I_{2}|+...+|I|_{h(p)-1})$ $\displaystyle\leq$
$\displaystyle 1+m+C(h(p)-2)\leq\sqrt{p}$

Therefore, $\sum_{l=0}^{h(p)-1}|I_{l}|\leq\sqrt{p}$. By Lemma 5 when
$h(p)-1\leq h_{max}(p)=\sqrt{p}$, we have $h_{p}^{*}\geq h(p)-1$. If
$h(p)-1>\sqrt{p}$ then $h_{p}^{*}=h_{max}(p)=\sqrt{p}$ since the BOO algorithm
does not expand nodes beyond depth $h_{max}(p)$. Thus, in all cases,
$h_{p}^{*}\geq\text{min}\\{h(p)-1,\sqrt{p}\\}$.

Let $(h,j)$ be the deepest node in $\mathcal{T}_{p}$ that has been expanded by
the algorithm up to $p$ expansions. Thus $h\geq h_{p}^{*}$. By Algorithm 1, we
only expand a node when its GP-UCB value is larger than $v_{max}$ which is
updated at Line 10 of Algorithm 1. Thus, since the node $(h,j)$ has been
expanded, its GP-UCB value is at least as high as that of the some node
$(h_{p}^{*}+1,j)$ at depth $h_{p}^{*}+1$, such that (1) node $(h_{p}^{*}+1,o)$
has been evaluated at some $p^{\prime}$-th expansion before node $(h,j)$ and
(2)
$(h_{p}^{*}+1,o)\in\text{argmax}_{(h_{p}^{*}+1,i)\in\mathcal{L}}\mathcal{U}_{p^{\prime}}(c_{h_{p}^{*}+1,i})$
(see Line 4 of Algorithm 1).

Thus, by using Lemma 3 and Lemma 6, we can achieve with probability $1-\eta$
that
$f(x^{*})-U_{p}(c_{h,j})\leq\delta(h_{p}^{*}+1;a,b)+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$.

Further by Lemma 6, we have
$U_{p}(c_{h,j})=\mu_{p}(c_{h,j})+\beta^{1/2}_{p}\sigma_{p}(c_{h,j})=\mathcal{L}_{p}(c_{h,j})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,j})\leq
f(c_{h,j})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,j})$, with a probability $1-\eta$.

Combining these two results, we have
$f(x^{*})-f(c_{h,j})\leq\delta(h_{p}^{*}+1;a,b)+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,j})$
with a probability $1-\eta$.

Figure 3: Comparison of methods for Hartmann3 ($D=3$), Schwefel ($D=3$), and
Shekel ($D=4$) functions.

Finally, by using Lemma 4 to bound $\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
and $\sigma_{p}(c_{h,j})$ and using the fact that the function $\delta(*;a,b)$
decreases with their depths, we achieve

$\displaystyle r_{p}$ $\displaystyle\leq$ $\displaystyle f(x^{*})-f(c_{h,j})$
$\displaystyle\leq$
$\displaystyle\delta(\text{min}\\{h(p),\sqrt{p}+1\\};a,b)+$ $\displaystyle+$
$\displaystyle
4C_{1}\beta^{1/2}_{p}(\delta(\text{min}\\{h(p)-1,\sqrt{p}\\};a,b))^{\nu/2-D/4}$

with a probability $1-\eta$. We provide the complete proof in the
Supplementary Material. ∎

Finally, we present an improved and simpler expression for the regret bound
through the following corollary from Theorem 2.

######  Corollary 1.

Pick a $\eta\in(0,1)$. Then, there exists a constant $N_{2}>0$ such that for
every $N\geq N_{2}$, the simple regret of the proposed BOO algorithm with the
partitioning procedure $P(m;a,b)$ where
$a=\lfloor(\frac{\sqrt{N}}{2})^{\frac{1}{D}}\rfloor$, $b=D$, is bounded as

$r_{N}\leq\mathcal{O}(N^{-\sqrt{N}}),$

with probability $1-\eta$, where $N$ is the number of sampled points.

##### Remark 1.

A detailed expression for the regret bound of Corollary 1 is that
$r_{N}\leq\mathcal{O}(C_{1}L_{1}D/2^{D}N^{-\frac{\sqrt{N}}{CD}+\frac{2}{CD}-\frac{2}{D}})$,
where $C_{1}$ is a constant (defined in Lemma 4) given $L_{1}$ and $D$, and
$C$ is a constant (defined in Theorem 1) given $L1,L_{2},\eta$ and $\nu$. This
complete formula is extracted from the proof of Corollary 1 in Supplementary
Material.

##### Remark 2.

The closest result to ours is the regret bound of IMGPO which has the worst
case order $\mathcal{O}(e^{-\sqrt{N}})$. As can be seen, we have improved the
regret bound. Our result improves over previous works because we leverage a
large value of the branch factor $m$ and our new partitioning procedure with
$b=D$ where all dimensions of a cell are divided.

##  6 Experiments

To evaluate the performance of our BOO algorithm, we performed a set of
experiments involving optimisation of three benchmark functions and three real
applications. We compared our method against five baselines which have
theoretical guarantees: (1) GP-EI (Bull, 2011), (2) GP-UCB (Srinivas et al.,
2012), (3) SOO (Munos, 2011), (4) BaMSOO (Wang et al., 2014), (5) IMGPO
(Kawaguchi et al., 2016).

##### Experimental settings

All implementations are in Python. For each test function, we repeat the
experiments 15 times. We plot the mean and a confidence bound of one standard
deviation across all the runs. We used Matérn kernel with $\nu=4+(D+1)/2$
which satisfies our assumptions, and estimated the kernel hyper-parameters
automatically from data using Maximum Likelihood Estimation. All methods using
GP (including GP-EI, GP-UCB, BaMSOO, IMGPO and our method) were started from
randomly initialised points to train GP. For GP-EI and GP-UCB which follow the
standard BO, we used the DIRECT algorithm to maximise the acquisition
functions and computed $\beta_{t}$ for GP-UCB as suggested in (Srinivas et
al., 2012). For tree-based space partitioning methods, we follow their
implementations to set the branch factor $m$. Note that these methods use a
small $m$ due to the negative correlation. SOO and BaMSOO use $m=2$ while
IMGPO uses $m=3$. The depth of search tree $h_{max}(p)$ in SOO and BaMSOO was
set to $\sqrt{p}$ as suggested in (Munos, 2011; Wang et al., 2014). The
parameter $\Xi_{n}$ in IMGPO was set to 1.

Table 1: Average CPU time (in seconds) for the experiment with each test
function.

Algorithm | Hartmann | Shekel | Schwefel
---|---|---|---
GP-EI | 200.39 | 740.20 | 250.79
GP-UCB | 880.43 | 1640.87 | 180.96
SOO | 0.51 | 0.40 | 0.11
BaMSOO | 39.02 | 87.62 | 28.67
IMGPO | 23.23 | 80.53 | 34.65
BOO | 27.21 | 91.22 | 41.01

###  6.1 Optimisation of Benchmark Functions

Figure 4: Log prediction error on MNIST dataset for different algorithms
ElasticNet, MLP and XGBoost.

We first demonstrate the efficiency of our algorithm on standard benchmark
functions: Hartmann3 ($D=3$), Schwefel ($D=3$) and Shekel ($D=4$). The
evaluation metric is the log distance to the true optimum:
$log_{10}(f(x^{*})-f^{+})$, where $f^{+}$ is the best function value sampled
so far.

For our BOO algorithm, we choose parameters $m,a,b$ and $N$ as per Corollary 1
which suggests using $N$ so that
$a=\mathcal{O}((\frac{\sqrt{N}}{2})^{1/D})\geq 2$. For Hartmann3 ($D=3)$ and
Schwefel ($D=3$) we use partitioning procedure $P(8;2,3)$ with $N=200$. For
Shekel function ($D=4$), we use $P(16;2;4)$ with $N=800$ so that
$(\frac{\sqrt{N}}{2})^{1/D}\approx 2$. We follow Lemma 6 in our theoretical
analysis to set $\beta_{p}=2log(\pi^{2}p^{3}/3\eta)$, with $\eta=0.05$.

Figure 3 shows the performance of our algorithm compared to the baselines. Our
method outperforms all baselines for all considered synthetic functions in
general with only one exceptional case of Shekel function where GP-UCB
performs better our method. Compared to BaMSOO and IMGPO which are tree-based
optimisation algorithms, the efficiency of BOO is gained by using a large $m$
and sampling strategies similar to BO (as shown in Section 4.2). Compared to
GP-EI and GP-UCB, our algorithm takes advantage of searching a point to be
evaluated at each iteration. BOO searches it only in a promising region (as
done in Line 4 and 5 in Algorithm 1) rather in a whole search space. Moreover,
unlike GP-EI and GP-UCB, BOO avoids the searching by optimisation at each
iteration which cannot be obtained sufficiently and accurately given a limited
computation budget.

##### On Computational Effectiveness

Our method performs competitively against BaMSOO and IMGPO in terms of
computational effectiveness (as shown in Table 1). Our method uses a large
value of $m$ and hence it takes slightly more time to compute UCBs of all
nodes. It performs slower than IMGPO but much faster than GP-EI, GP-UCB which
require the maximisation of the acquisition function in a continuous space.

###  6.2 Hyperparameter Tuning for Machine Learning Models

To further validate the performance of our algorithm, we tune hyperparameter
tuning of three machine learning models on the MNIST dataset and Skin
Segmentation dataset, then plot the log prediction error.

##### Elastic Net

A regression method has the $L_{1}$ and $L_{2}$ regularisation parameters. We
tune $w_{1}$ and $w_{2}$ where $w_{1}>0$ expresses the magnitude of the
regularisation penalty while $w_{2}\in[0,1]$ expresses the ratio between the
two penalties. We tune $w_{1}$ in the normal space while $w_{2}$ is tuned in
an exponent space (base 10). The search space is the domain
$[0,1]\times[-3,-1]$. We implement the Elastic net model by using the function
SGDClassifier in the scikit-learn package.

##### Multilayer Perceptron (MLP)

We consider a 2-layer MLP with 512 neurons/layer and optimize three
hyperparameters: the learning rate $l$ and the $L_{2}$ norm regularisation
parameters $l_{r1}$ and $l_{r2}$ of the two layers (all tuned in the exponent
space (base 10)). The search space is $[-6,-1]^{3}$. The model is trained with
the Adam optimizer in 20 epochs with batch size 128.

Using MNIST dataset, we train the models with this hyperparameter setting
using the 55000 patterns and then test the model on the 10000 patterns. The
algorithms suggests a new hyperparameter setting based on the prediction
accuracy on the test dataset. We set $N=200$. We use $P(4;2,2)$ for ElasticNet
and $P(8;2,3)$ for MLP as per Corollary 1.

As seen in Figure 4, for Elastic Net, our algorithm outperforms the all
baselines. For MLP, our algorithm achieves slightly lower prediction errors
compared to the baselines because there is a little room to improve where the
prediction error of our method for MLP attains $1.8\%$.

Table 2: Hyperparameters for XGBoost. Variables | Min | Max
---|---|---
learning rate | 0.1 | 1
max depth | 5 | 15
subsample | 0.5 | 1
colsample | 0.1 | 1
gamma | 0 | 10

##### XGBoost classification

We demonstrate a classification task using XGBoost (Chen & Guestrin, 2016) on
a Skin Segmentation dataset
111https://archive.ics.uci.edu/ml/datasets/skin+segmentation. The Skin
Segmentation dataset is plit into $15\%$ for training and $85\%$ for testing
for a classification problem. There are 5 hyperarameters for XGBoost which is
summarized in Table 2. Our proposed BOO is the best solution, outperforming
all the baselines by a wide margin.

##  7 Conclusion

We have presented a first practical algorithm which can achieve an exponential
regret bound with tightest order $N^{-\sqrt{N}}$ for Baysian optimisation
under the assumption that the objective function is sampled from a Gaussian
process with a Matérn kernel with $\nu>4+\frac{D}{2}$. Our partitioning
procedure and the sampling strategy differ from the existing ones. We have
demonstrated the benefits of our algorithm on both synthetic and real world
experiments. In the future we plan to extend our work to high dimensions and
noisy setting.

## References

  * Al-Dujaili & Suresh (2017) Al-Dujaili, A. and Suresh, S.  Embedded bandits for large-scale black-box optimization.  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA_ , pp. 758–764, 2017.
  * Al-Dujaili & Suresh (2018) Al-Dujaili, A. and Suresh, S.  Multi-objective simultaneous optimistic optimization.  _Inf. Sci._ , 424:159–174, 2018.  doi: 10.1016/j.ins.2017.09.066.  URL https://doi.org/10.1016/j.ins.2017.09.066.
  * Bull (2011) Bull, A. D.  Convergence rates of efficient global optimization algorithms.  _J. Mach. Learn. Res._ , 12:2879–2904, November 2011.  ISSN 1532-4435.
  * Chen & Guestrin (2016) Chen, T. and Guestrin, C.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, pp. 785–794, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450342322.  doi: 10.1145/2939672.2939785.  URL https://doi.org/10.1145/2939672.2939785.
  * Chevalier et al. (2014) Chevalier, C., Ginsbourger, D., and Emery, X.  Corrected kriging update formulae for batch-sequential data assimilation.  In Pardo-Igúzquiza, E., Guardiola-Albert, C., Heredia, J., Moreno-Merino, L., Durán, J. J., and Vargas-Guzmán, J. A. (eds.), _Mathematics of Planet Earth_ , pp. 119–122, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * Chowdhury & Gopalan (2017) Chowdhury, S. R. and Gopalan, A.  On kernelized multi-armed bandits.  In Precup, D. and Teh, Y. W. (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 844–853, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.  URL http://proceedings.mlr.press/v70/chowdhury17a.html.
  * De Freitas et al. (2012) De Freitas, N., Smola, A. J., and Zoghi, M.  Exponential regret bounds for gaussian process bandits with deterministic observations.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , ICML’12, pp. 955–962, Madison, WI, USA, 2012. Omnipress.  ISBN 9781450312851.
  * Floudas (2005) Floudas, C. A.  _Deterministic Global Optimization: Theory, Methods and (NONCONVEX OPTIMIZATION AND ITS APPLICATIONS Volume 37) (Nonconvex Optimization and Its Applications)_.  Springer-Verlag, Berlin, Heidelberg, 2005.  ISBN 0792360141.
  * Grill et al. (2015) Grill, J.-B., Valko, M., Munos, R., and Munos, R.  Black-box optimization of noisy functions with unknown smoothness.  In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 28_ , pp. 667–675. Curran Associates, Inc., 2015.
  * Hernández-Lobato et al. (2014) Hernández-Lobato, J. M., Hoffman, M. W., and Ghahramani, Z.  Predictive entropy search for efficient global optimization of black-box functions.  In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q. (eds.), _Advances in Neural Information Processing Systems 27_ , pp. 918–926. Curran Associates, Inc., 2014.
  * Janz et al. (2020) Janz, D., Burt, D., and Gonzalez, J.  Bandit optimisation of functions in the matérn kernel rkhs.  In Chiappa, S. and Calandra, R. (eds.), _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pp. 2486–2495. PMLR, 26–28 Aug 2020.
  * Jones et al. (1993) Jones, D. R., Perttunen, C. D., and Stuckman, B. E.  Lipschitzian optimization without the lipschitz constant.  _J. Optim. Theory Appl._ , 79(1):157–181, October 1993.  ISSN 0022-3239.
  * Kanagawa et al. (2018) Kanagawa, M., Hennig, P., Sejdinovic, D., and Sriperumbudur, B. K.  Gaussian processes and kernel methods: A review on connections and equivalences, 2018.
  * Kandasamy (2015) Kandasamy.  High dimensional bayesian optimisation and bandits via additive models.  In _Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37_ , ICML’15, pp. 295–304. JMLR.org, 2015.
  * Kawaguchi et al. (2016) Kawaguchi, K., Kaelbling, L. P., and Lozano-Pérez, T.  Bayesian optimization with exponential convergence, 2016.  URL https://arxiv.org/abs/1604.01348.
  * Munos (2011) Munos, R.  Optimistic optimization of a deterministic function without the knowledge of its smoothness.  In Shawe-Taylor, J., Zemel, R. S., Bartlett, P. L., Pereira, F., and Weinberger, K. Q. (eds.), _Advances in Neural Information Processing Systems 24_ , pp. 783–791. Curran Associates, Inc., 2011.
  * Qian & Yu (2016) Qian, H. and Yu, Y.  Scaling simultaneous optimistic optimization for high-dimensional non-convex functions with low effective dimensions.  In _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA_ , pp. 2000–2006, 2016.
  * Rasmussen & Williams (2005) Rasmussen, C. E. and Williams, C. K. I.  _Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning)_.  The MIT Press, 2005.  ISBN 026218253X.
  * Russo et al. (2018) Russo, D., Roy, B. V., Kazerouni, A., Osband, I., and Wen, Z.  A tutorial on thompson sampling.  _Foundations and Trends in Machine Learning_ , 11(1):1–96, 2018.  doi: 10.1561/2200000070.
  * Scarlett et al. (2017) Scarlett, J., Bogunovic, I., and Cevher, V.  Lower bounds on regret for noisy Gaussian process bandit optimization.  In Kale, S. and Shamir, O. (eds.), _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pp. 1723–1742, Amsterdam, Netherlands, 07–10 Jul 2017\. PMLR.  URL http://proceedings.mlr.press/v65/scarlett17a.html.
  * Sen et al. (2018) Sen, R., Kandasamy, K., and Shakkottai, S.  Multi-fidelity black-box optimization with hierarchical partitions.  volume 80 of _Proceedings of Machine Learning Research_ , pp. 4538–4547, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Srinivas et al. (2012) Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W.  Information-theoretic regret bounds for gaussian process optimization in the bandit setting.  _IEEE Trans. Inf. Theor._ , 58(5):3250–3265, May 2012.  ISSN 0018-9448.  doi: 10.1109/TIT.2011.2182033.  URL http://dx.doi.org/10.1109/TIT.2011.2182033.
  * Stein (1999) Stein, M. L.  _Interpolation of spatial data_.  Springer Series in Statistics. Springer-Verlag, New York, 1999.  ISBN 0-387-98629-4.  doi: 10.1007/978-1-4612-1494-6.  URL http://dx.doi.org/10.1007/978-1-4612-1494-6.  Some theory for Kriging.
  * Tran-The et al. (2020) Tran-The, H., Gupta, S., Rana, S., Ha, H., and Venkatesh, S.  Sub-linear regret bounds for bayesian optimisation in unknown search spaces.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 16271–16281. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/bb073f2855d769be5bf191f6378f7150-Paper.pdf.
  * Tran-The et al. (2020) Tran-The, H., Gupta, S., Rana, S., and Venkatesh, S.  Trading convergence rate with computational budget in high dimensional bayesian optimization.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pp. 2425–2432, 2020.
  * Vakili et al. (2020) Vakili, S., Picheny, V., and Durrande, N.  Regret bounds for noise-free bayesian optimization, 2020.
  * Valko et al. (2013) Valko, M., Carpentier, A., and Munos, R.  Stochastic simultaneous optimistic optimization.  In _Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013_ , pp. 19–27, 2013\.
  * Wang et al. (2020) Wang, L., Fonseca, R., and Tian, Y.  Learning search space partition for black-box optimization using monte carlo tree search, 2020.
  * Wang et al. (2014) Wang, Z., Shakibi, B., Jin, L., and de Freitas, N.  Bayesian multi-scale optimistic optimization.  In _Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014_ , pp. 1005–1014, 2014.
  * Wang et al. (2018) Wang, Z., Gehring, C., Kohli, P., and Jegelka, S.  Batched large-scale bayesian optimization in high-dimensional spaces.  volume 84 of _Proceedings of Machine Learning Research_ , pp. 745–754, Playa Blanca, Lanzarote, Canary Islands, 09–11 Apr 2018. PMLR.
  * Wu & Schaback (1992) Wu, Z. and Schaback, R.  Local error estimates for radial basis function interpolation of scattered data.  _IMA J. Numer. Anal_ , 13:13–27, 1992.

Supplementary Material

##  Appendix 1 Review of SOO, BaMSOO, IMGPO algorithms

In the first section of the Supplementary Material, we provide the details of
SOO (Munos, 2011) and BamSOO (Wang et al., 2014). The main difference between
our proposed BOO algorithm and these algorithms are in the following blue
color lines.

Algorithm 2 The SOO Algorithm (Munos, 2011)

Input: Parameter $m$
Initialisation: Set $\mathcal{T}_{0}=\\{(0,0)\\}$ (root node). Set $p=1$.
Sample initial points to build $\mathcal{D}_{0}$.

1: while True do

2: Set $v_{max}=-\infty$

3: for $h=0$ to min(depth($\mathcal{T}_{p}$), $h_{max}(p)$) do

4: Among all leaves $(h,j)$ of depth $h$, select
$(h,i)\in\text{argmax}_{(h,j)\in\mathcal{L}}f(c_{h,j})$

5: if $f(c_{h,i})\geq v_{max}$ then

6: Expand node $(h,i)$ by adding $m$ children $(h+1,i_{j})$ to tree
$\mathcal{T}_{p}$

7: Evaluate all $m$ functional values $f(c_{h+1,i_{j}})$, where $(h+1,i_{j})$
are children of $(h,i)$

8: Update $v_{max}=f(c_{h,i})$

9: Update $p=p+1$

10: end if

11: end for

12: end while

Algorithm 3 The BaMSOO Algorithm (Wang et al., 2014)

Input: Parameter $m$
Initialisation: Set $g_{0,0}=f(c_{0,0})$, $f^{+}=g_{0,0}$, $t=1$, $p=1$,
$\mathcal{T}_{0}=\\{(0,0)\\}$ (root node). Sample initial points to build
$\mathcal{D}_{0}$.

1: while True do

2: Set $v_{max}=-\infty$

3: for $h=0$ to min(depth($\mathcal{T}_{p}$), $h_{max}(p)$) do

4: Among all leaves $(h,j^{\prime})$ of depth $h$, select
$(h,j)\in\text{argmax}_{(h,j^{\prime})\in\mathcal{L}}g(c_{h,j^{\prime}})$

5: if $g(c_{h,j})\geq v_{max}$ then

6: for $i=0$ to $k-1$ do

7: Update $p=p+1$

8: if $\mathcal{U}_{p}(c_{h+1,mj+i})\geq f^{+}$ then

9: Set $g(c_{h+1,mj+i})=f(c_{h+1,mj+i})$

10: Set $t=t+1$

11: $\mathcal{D}_{t}=\\{\mathcal{D}_{t-1},(c_{h+1,mj+i},g(c_{h+1,mj+i}))\\}$

12: else

13: Set $g(c_{h+1,mj+i})=\mathcal{L}_{p}(c_{h+1,mj+i})$

14: end if

15: if $g(c_{h+1,mj+i})>f^{+}$ then

16: Set $f^{+}=g(c_{h+1,mj+i})$

17: end if

18: end for

19: Add the children of $(h,j)$ to $\mathcal{T}_{p}$

20: Set $v_{max}=g(c_{h,j})$

21: end if

22: end for

23: end while

As we can see, SOO and BaMSOO select a node to be expanded at line 4 in each
algorithm. At depth $h$, among the leaf nodes, SOO selects the node with the
maximum functional value, BaMSOO selects the node with the maximum value of
function $g$. The function $g$ is defined at line 9 and line 13 in Algorithm
3. Otherwise, the proposed BOO selects the node with the maximum GP-UCB value.

Once a node is selected to be expanded, SOO needs to sample the function at
all $m$ children nodes (at line 7 in Algorithm 2), BamSOO needs to sample the
function at $m^{\prime}$ children nodes (at line 9 in Algorithm 3), where
$0\leq m^{\prime}\leq m$ depending on the condition at line 9 in Algorithm 3.
In the worst case, $m^{\prime}=m$, BamSOO spends $m$ evaluations like SOO.
Otherwise, our sampling strategy samples the function only at the parent node.
As a result, our strategy requires only one function evaluation irrespective
of the value of $m$. IMGPO (Kawaguchi et al., 2016) is quite similar to BaMSOO
except two differences. Frist, IMGPO do not force the tree to a maximum depth
of $h_{max}(p)$ like SOO, BamSOO. Second, IMGPO add a strategy to reduce the
computation when searching in the tree is inefficient. Please see their paper
(Kawaguchi et al., 2016) for details.

###  1.1 Strict Negative Correlation

As we discussed in section 4.1 of the main paper. Most of tree-based
optimistic optimisation algorithms like SOO, StoSOO (Valko et al., 2013),
BaMSOO and IMGPO face a _strict negative correlation_ between the branch
factor $m$ and the number of tree expansions given a fixed function evaluation
budget $N$. In this part, we provide a summary table showing the simple regret
(in the worst case) of these algorithms given a fixed function evaluation
budget $N$.

Algorithm | Simple Regret
---|---
SOO | $\mathcal{O}(e^{\sqrt{\frac{N}{m}}})$
BaMSOO | $\mathcal{O}((\frac{N}{m})^{-\frac{2\alpha}{D(4-\alpha)}})$
IMGPO | $\mathcal{O}(e^{\sqrt{\frac{N}{m}}})$
Table 3: The simple regret of SOO depends on the near-optimality dimension
$d$. If $d>0$ then the simple regret is sublinear, if $d=0$ then the simple
regret is exponential as we show in this table. BaMSOO has a sublinear rate
because it uses $d=D/\alpha-D/4$ where $\alpha=1$ or $2$. IMGPO uses a fixed
$m=3$. We here generalize their proof to any $m$.

The Table 3 shows the strict negative correlation of tree-based optimistic
optimisation algorithms like SOO, BamSOO, IMGPO. The larger $m$ is, the higher
the simple regret is. This explains why most of tree-based optimistic
optimisation algorithms often use a small value of $m$ like $m=2$, $m=3$. In
contrast, our algorithm leverages the large value of $m$ to improve the regret
bound.

##  Appendix 2 Proof of Lemma 1

######  Lemma 7 (Lemma 1 in the main paper).

Given any $(a,b)\in M(m)$ and a partitioning procedure $P(m;a,b)$, then

  1. 1.

the longest side of a cell at depth $h$ is at most
$a^{-\lfloor\frac{bh}{D}\rfloor}$, and

  2. 2.

the smallest side of a cell at depth $h$ is at least
$a^{-\lceil\frac{bh}{D}\rceil}$.

###### Proof.

We prove the statement by induction. At depth $h=1$, we partition the search
space $\mathcal{X}$ into $m=a^{b}$ cells using the partitioning procedure
$P(m;a,b)$. There are two cases on $b$.

  * •

$b=D$. Then the longest side of a cell at depth $h=1$ is
$1/a=a^{-\lfloor\frac{b}{D}\rfloor}$. Also, the smallest side of a cell at
depth $h=1$ is $1/a=a^{-\lceil\frac{b}{D}\rceil}$.

  * •

$b<D$. Then by the partitioning procedure, the longest side of a cell at depth
$h=1$ is still 1. $a^{-\lfloor\frac{b}{D}\rfloor}=a^{0}=1$. Hence, the longest
side of a cell at depth 1 is $a^{-\lfloor\frac{b}{D}\rfloor}$. Also, the
smallest side of a cell at depth $h=1$ is $1/a=a^{-\lceil\frac{b}{D}\rceil}$.

For both cases, the statement is true for $h=1$. We assume that the statement
is true for $h\geq 1$. We consider any cell at depth $h+1$. By our algorithm,
this cell is divided from a cell at depth $h$. Similar to the case $h=1$, we
also consider two cases on $b$.

  * •

$b=D$. By the inductive hypothesis, the longest side of a cell at depth $h$ is
at most $a^{-h}$. Then the longest side of a child cell of this cell is
$a^{-(h+1)}=a^{-\lfloor\frac{b(h+1)}{D}\rfloor}$. Also, the smallest side of a
child cell of this cell is $a^{-(h+1)}=a^{-\lceil\frac{b(h+1)}{D}\rceil}$.

  * •

$b<D$. By the inductive hypothesis, the longest side of a cell at depth $h$ is
at most $a^{-\lfloor\frac{bh}{D}\rfloor}$. If we divide a cell at depth $h$ by
the partitioning procedure, then the longest side of the sub-cell is at most
$a^{-\lfloor\frac{bh}{D}\rfloor}/a=a^{-1-\lfloor\frac{bh}{D}\rfloor}$.
However, since $b<D$, $\lfloor\frac{b(h+1)}{D}\rfloor\leq
1+\lfloor\frac{bh}{D}\rfloor$. It follows that
$a^{-1-\lfloor\frac{bh}{D}\rfloor}\leq a^{-\lfloor\frac{b(h+1)}{D}\rfloor}$.
Thus, the longest side of a cell at depth $h+1$ is at most
$a^{-\lfloor\frac{b(h+1)}{D}\rfloor}$.

Also, by the inductive hypothesis, the smallest side of a cell at depth $h$ is
at least $a^{-\lceil\frac{bh}{D}\rceil}$. If we divide a cell at depth $h$
then the smallest side of the sub-cell is at least
$a^{-\lceil\frac{bh}{D}\rceil}/a=a^{-\lceil\frac{bh}{D}\rceil-1}$. However,
since $b<D$, $\lceil\frac{bh}{D}\rceil+1\geq\lceil\frac{b(h+1)}{D}\rceil$. As
a result, $a^{-\lceil\frac{bh}{D}\rceil-1}\geq
a^{-\lceil\frac{b(h+1)}{D}\rceil}$. Thus, the smallest side of a cell at depth
$h+1$ is at least $a^{-\lfloor\frac{b(h+1)}{D}\rfloor}$.

Thus, the statement holds for every $h\geq 1$. ∎

##  Appendix 3 Proof of Lemma 4

To derive an upper bound on variance function $\sigma_{p}$ as in Lemma 4, we
use a concept, called the _fill distance_. Given a set of points
$\mathcal{D}_{p-1}$ , we define the fill distance
$\text{FD}(\mathcal{D}_{p-1},\mathcal{X})$ as the largest distance from any
point in $\mathcal{X}$ to the points in $\mathcal{D}_{p-1}$, as

$\text{FD}(\mathcal{D}_{p-1},\mathcal{X})=\text{sup}_{x\in\mathcal{X}}\text{inf}_{c_{i}\in
D_{p-1}}||x-c_{i}||.$

The following result, which is proven by Wu & Schaback (1992) [Theorem 5.14],
after is reviewed by Kanagawa et al. (2018) [Theorem 5.4], provides an upper
bound for the posterior variance in terms of the fill distance. It applies the
cases where the kernel whose RKHS is norm-equivalent to the Sobolev space.

######  Lemma 8 ((Wu & Schaback, 1992; Kanagawa et al., 2018)).

Let $k$ be a kernel on $\mathbb{R}^{d}$ whose RKHS is norm equivalent to the
Sobolev space. There exist constants $h_{0}>0$ and $C^{\prime}>0$ satisfying
the following: for any $x\in\mathcal{X}$ and any set of observations
$\mathcal{D}_{p-1}=\\{c_{1},c_{2},...,c_{p-1}\\}\in\mathcal{X}$ satisfying
$\text{FD}(\mathcal{D}_{p-1},\mathcal{X})\leq h_{0}$, we have

$\sigma_{p}(x)\leq
C^{\prime}\text{FD}(\mathcal{D}_{p-1},\mathcal{X}))^{\nu-D/2}.$

It was shown in (Bull, 2011) [Lemma 3] and in (Kanagawa et al., 2018) that the
Matérm kernels’s RKHS is norm-equivalent to the Sobolev space. Therefore,
Lemma 8 is correct all functions satisfying our Assumption 1 and 2 (in Baysian
setting).

Based on Lemma 8, we obtain the following result which is similar to Lemma 4
of Vakili et al. (2020) but for the Bayesian setting.

######  Lemma 9 (Based on Lemma 4 of Vakili et al. (2020)).

There exist constants $h_{0}>0$ and $C^{\prime}>0$ satisfying the following:
for any $x\in\mathcal{X}$ and any set of observations
$\mathcal{D}_{p-1}=\\{x_{1},x_{2},...,x_{p-1}\\}\in\mathcal{X}$ satisfying
$\text{FD}(\mathcal{D}_{p-1},\mathcal{X})\leq h_{0}$, we have

$\sigma_{p}(x)\leq\text{min}_{c_{i}\in\mathcal{D}_{p-1}}C^{\prime}||x-c_{i}||^{\nu-D/2}$

###### Proof.

The proof is very similar to their proof. We include it for the purpose of
being self-contained. For $x\in\mathcal{X}$, let $c_{i}\in\mathcal{D}_{p-1}$
be the closet point to $x$:
$||x-c_{j}||=\text{min}_{x_{i}\in\mathcal{D}_{p-1}}||x-c_{i}||$. Define
$\mathcal{X}^{\prime}=\mathcal{B}_{D}(c_{j},||x-c_{j}||)$, the $D$-dimensional
hyper-ball centered at $c_{j}$ with radius $||x-c_{j}||$. Let
$X"=\mathcal{D}_{p-1}\cap X^{\prime}$. The fill distance of the points $X"$ in
$X^{\prime}$ satisfies:

$\text{FD}(X",X^{\prime})=\text{sup}_{x^{\prime}\in
X^{\prime}}\text{inf}_{c_{i}\in
X"}||x^{\prime}-c_{i}||\leq\text{sup}_{x^{\prime}\in
X^{\prime}}||x^{\prime}-c_{j}||=||x-c_{j}||.$

Define $\mu^{\prime}(x)=\mathbb{E}[f(x)|X"]$ and
$k^{\prime}(x,x^{\prime})=\mathbb{E}[(f(x)-\mu^{\prime}(x))(f(x^{\prime})-\mu^{\prime}(x^{\prime}))|X"]$.
Let $\sigma^{\prime}(x)=\sqrt{k^{\prime}(x,x^{\prime})}$ be the predictive
standard deviation conditioned on observations $X"$. Applying Lemma 8 to
$\sigma^{\prime}(x)$, we have

$\sigma^{\prime}(x)\leq C^{\prime}\text{FD}(X",X^{\prime})^{\nu-D/2}\leq
C^{\prime}||x-c_{j}||^{\nu-D/2}.$

The lemma holds because $\sigma_{p}(x)\leq\sigma^{\prime}(x)$. This is the
decreasing monotonicity of the variance function. $\sigma^{\prime}(x)$ is
constructed from set $X^{\prime\prime}\subset\mathcal{D}_{p-1}$. A more formal
proof that $\sigma_{p}(x)\leq\sigma^{\prime}(x)$ can be found in (Chevalier et
al., 2014). ∎

Next, we apply this result to our context in which the set of the sampling
points $c_{i}$, $\mathcal{D}_{p-1}=\\{c_{1},...,c_{p-1}\\}$ , contains the
centers of cells $A_{h,i}$ of a tree structured search space.

Now we prove Lemma 4 in the main paper.

######  Lemma 10.

Assuming that node $c_{h,i}$ at the depth $h\geq 1$ was sampled at the $p$-th
expansion, where $p\geq h$, then we have that

$\sigma_{p}(c_{h,i})\leq C_{1}(\delta(h-1;a,b))^{\nu/2-D/4},$

where $C_{1}$ is a constant.

###### Proof.

By Lemma 9, for every $x\in\mathcal{X}$, we have that

$\sigma_{p}(x)\leq\text{min}_{c_{i}\in\mathcal{D}_{p-1}}C^{\prime}||x-c_{i}||^{\nu-D/2}$

where $C^{\prime}$ is a constant.

By assumption, node $c_{h,i}$ at depth $h$ is sampled at the $p$-th expansion,
where $p\geq h$. By hierarchical structure of the sampled points, node
$c_{h,i}$ is sampled only if its parent node was sampled. We denote this node
by $c_{h-1,j}$ which is at depth $h-1$ with some index $j$. It follows that

$\displaystyle\sigma_{p}(c_{h,i})$ $\displaystyle\leq$
$\displaystyle\text{min}_{c_{i}\in\mathcal{D}_{p-1}}C^{\prime}||c_{h,i}-c_{i}||^{\nu-D/2}$
$\displaystyle\leq$ $\displaystyle C^{\prime}||c_{h,i}-c_{h-1,j}||^{\nu-D/2}$
$\displaystyle\leq$ $\displaystyle
C^{\prime}(L_{1}D)^{D/4-\nu/2}(\delta(h-1;a,b))^{\nu/2-D/4},$

where in the first inequality, we apply Lemma 9. In the second inequality, we
use the property of $c_{h-1,j}\in\mathcal{D}_{p-1}$, hence
$\text{min}_{c_{i}\in\mathcal{D}_{p-1}}||c_{h,i}-c_{i}||^{v-D/2}\leq||c_{h,i}-c_{h-1,j}||^{v-D/2}$.
In the last inequality, we have that $c_{h,i}$ belongs to the cell $A_{h-1,j}$
with center $c_{h-1,j}$. Hence, distance $||c_{h,i}-c_{h-1,j}||$ must be
shorter than the diameter of that cell. By Lemma and the definition of
$\delta(h-1;a,b)=L_{1}Da^{-2\lfloor\frac{b(h-1)}{D}\rfloor}$, the last
inequality is proven.

Finally, by setting $C_{1}=C^{\prime}(L_{1}D)^{D/4-\nu/2}$, the lemma holds. ∎

##  Appendix 4 Proof of Theorem 1

To prove Theorem 1, we will involve two stages:

  * •

Stage 1: we first prove that if $N$ is large enough, then under some
assumptions, all the centers of nodes of expandable nodes will fall into the
ball $\mathcal{B}(x^{*},\theta)$ which is centered at $x^{*}$ with radius
$\theta$ as defined in Property 1. We prove this in the following Lemma 11.

  * •

Stage 2: when a set of expandable nodes fallen into the ball
$\mathcal{B}(x^{*},\theta)$, the quadratic behaviours of the objective
function surrounding the global optimum $x^{*}$ will occur. We exploit this
property to prove that $|I_{h}|\leq C$, where $C$ is some constant.

######  Lemma 11.

Assume Algorithm 1 uses partitioning procedure $P(m;a,b)$ where
$a=\mathcal{O}(N^{1/D})$ and $b=D$. Thus there exists a constant $N_{0}$ such
that for every $N\geq N_{0}$, if (1) node $(h,i)\in I_{h}$, where $h\geq 2$
and (2) $\mathcal{L}_{p}(c_{h,i})\leq f(c_{h,i})$ for every $h\leq p\leq N$,
then

$c_{h,i}\in\mathcal{B}(x^{*},\theta),$

where $\mathcal{B}(x^{*},\theta)$ is the ball centered at $x^{*}$ with radius
$\theta$, which is defined in Property 1.

###### Proof.

By definition, the expansion set $I_{h}=\\{(h,i)|\exists h\leq p\leq
N:\mathcal{U}_{p}(c_{h,i})\geq f(x^{*})-\delta(h;a,b)\\}$. Therefore, if node
$(h,i)\in I_{h}$ then there must exist some $h\leq p\leq N$ such that

$\displaystyle\mathcal{U}_{p}(c_{h,i})\geq f(x^{*})-\delta(h;a,b)$ (1)

On the other hand, for the same upper confidence bound
$\mathcal{U}_{p}(c_{h,i})$ of $f(c_{h,i})$ as above, we have that

$\displaystyle\mathcal{U}_{p}(c_{h,i})$ $\displaystyle=$
$\displaystyle\mu_{p}(c_{h,i})+\beta^{1/2}_{p}\sigma_{p}(c_{h,i})$ (2)
$\displaystyle=$
$\displaystyle\mu_{p}(c_{h,i})-\beta^{1/2}_{p}\sigma_{p}(c_{h,i})+2\beta^{1/2}_{p}\sigma_{p}(c_{h,i})$
(3) $\displaystyle=$
$\displaystyle\mathcal{L}_{p}(c_{h,i})+2\beta^{1/2}_{p}\sigma_{p}(c_{h,i})$
(4) $\displaystyle\leq$ $\displaystyle
f(c_{h,i})+2\beta^{1/2}_{p}\sigma_{p}(c_{h,i})$ (5) $\displaystyle\leq$
$\displaystyle f(c_{h,i})+2\beta^{1/2}_{p}C_{1}(\delta(p-1;a,b))^{\nu/2-D/4},$
(6)

where in Eq (5), we use the assumption that $\mathcal{L}_{p}(c_{h,i})\leq
f(c_{h,i})$. In Eq (6), we use Lemma 10.

Combining Eq (1) and Eq (7), we obtain

$\displaystyle f(x^{*})-f(c_{h,i})$ $\displaystyle\leq$ $\displaystyle
f(c_{h,i})+2\beta^{1/2}_{p}C_{1}(\delta(p-1;a,b))^{\nu/2-D/4}$ (7)
$\displaystyle=$ $\displaystyle
L_{1}Da^{-2\lfloor\frac{bh}{D}\rfloor}+2\beta^{1/2}_{p}C_{1}(L_{1}Da^{-2\lfloor\frac{b(h-1)}{D}\rfloor})^{\nu/2-D/4}$
(8) $\displaystyle=$ $\displaystyle
L_{1}Da^{-2h}+2\beta^{1/2}_{p}C_{1}(L_{1}D)^{\nu/2-D/4}a^{-(\nu-D/2)(h-1)},$
(9)

where Eq (8) uses the definition of $\delta(h;a,b)$ and Eq (9) uses the
assumption that $b=D$.

We continue to go further with Eq (9) by using the assumptions that
$a=\mathcal{O}(N^{1/D})$, $h\geq 2$ (from assumptions of Lemma 11), and
$\nu-D/2>4$ (from Assumption 1):

$\displaystyle f(x^{*})-f(c_{h,i})$ $\displaystyle\leq$ $\displaystyle
L_{1}Da^{-2h}+2\beta^{1/2}_{p}C_{1}(L_{1}D)^{\nu/2-D/4}a^{-(\nu-D/2)(h-1)}$
(10) $\displaystyle\leq$ $\displaystyle
L_{1}Da^{-4}+2\beta^{1/2}_{N}C_{1}(L_{1}D)^{\nu/2-D/4}a^{-4}$ (11)
$\displaystyle=$
$\displaystyle\frac{L_{1}D+2C_{1}(L_{1}D)^{\nu/2-D/4}\sqrt{2log(\pi^{2}N^{3}/3\eta)}}{a^{4}}$
(12) $\displaystyle=$
$\displaystyle\mathcal{O}(\frac{\sqrt{log(N/3\eta)}}{N^{4/D}}),$ (13)

where, in Eq (11), we use $h\geq 2$ and the increasing monotonicity of
function $\beta_{p}$. We recall that $\beta_{p}$ is the trade-off parameter
used on our BOO proposed. Formally,
$\beta_{p}=2log(\frac{\pi^{2}p^{3}}{3\eta})$, where $\eta\in(0,1)$. In Eq
(13), we use $a=\mathcal{O}(N^{1/d})$.

We have that $\frac{\sqrt{log(N/3\eta)}}{N^{4/D}}\rightarrow 0$ as
$N\rightarrow\infty$. Therefore, for any $\epsilon_{0}>0$, there exists a
constant $N_{0}>0$ such that for every $N\geq N_{0}$,
$f(x^{*})-f(c_{h,i})\leq\epsilon_{0}$. Thus, by definition of
$\mathcal{B}(x^{*},\theta)$ in Property 1,
$c_{h,i}\in\mathcal{B}(x^{*},\theta)$. ∎

We now start to prove Theorem 1.

######  Theorem 3.

Assume that the proposed BOO algorithm uses partitioning procedure $P(m;a,b)$
where $a=\mathcal{O}(N^{1/D})$ and $b=D$. We consider set $I_{h}$, where
$h\geq 2$ and assume that $\mathcal{L}_{p}(c_{h,i})\leq
f(c_{h,i})\leq\mathcal{U}_{p}(c_{h,i})$ for all node $(h,i)\in I_{h}$ and for
all $h\leq p\leq N$. Then there exist constants $N_{1}>0$ and $C>0$ such that
for every for $N\geq N_{1}$,

$|I_{h}|\leq C.$

###### Proof.

The proof involves three steps.

Step 1: for each node $(h,i)\in I_{h}$, we seek to bound gap
$||x^{*}-c_{h,i}||$.

By Lemma 11 and the assumptions of Lemma 3, there exists a constant $N_{0}$
such that for every $N\geq N_{0}$, for any $(h,i)\in I_{h}$ then
$c_{h,i}\in\mathcal{B}(x^{*},\theta)$. Hence following Property 1, for any
$(h,i)\in I_{h}$, the following result is guaranteed:

$\displaystyle L_{2}||x^{*}-c_{h,i}||^{2}\leq f(x^{*})-f(c_{h,i}).$ (14)

On the other hand, by definition of $I_{h}$, there exists $h\leq p\leq N$ such
that

$\displaystyle\mathcal{U}_{p}(c_{h,i})\geq f(x^{*})-\delta(h;a,b).$ (15)

Combining Eq (14) and Eq (15), we have that

$\displaystyle
L_{2}||x^{*}-c_{h,i}||^{2}\leq\mathcal{U}_{p}(c_{h,i})+\delta(h;a,b)-f(c_{h,i}).$
(16)

Similar to Lemma 11, we continue to analyze the right hand side of Eq (16) as
follows:

$\displaystyle L_{2}||x^{*}-c_{h,i}||^{2}$ $\displaystyle\leq$
$\displaystyle\mathcal{U}_{p}(c_{h,i})+\delta(h;a,b)-f(c_{h,i})$ (17)
$\displaystyle=$
$\displaystyle\mu_{p}(c_{h,i})+\beta^{1/2}_{p}\sigma_{p}(c_{h,i})+\delta(h;a,b)-f(c_{h,i})$
(18) $\displaystyle=$
$\displaystyle\mu_{p}(c_{h,i})-\beta^{1/2}_{p}\sigma_{p}(c_{h,i})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,i})+\delta(h;a,b)-f(c_{h,i})$
(19) $\displaystyle\leq$
$\displaystyle\mathcal{L}_{p}(c_{h,i})+2\beta^{1/2}_{p}\sigma_{p}(c_{h,i})+\delta(h;a,b)-f(c_{h,i})$
(20) $\displaystyle\leq$ $\displaystyle
2\beta^{1/2}_{p}\sigma_{p}(c_{h,i})+\delta(h;a,b)$ (21) $\displaystyle\leq$
$\displaystyle
2\beta^{1/2}_{p}C_{1}(\delta(p-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)$ (22)
$\displaystyle\leq$ $\displaystyle
2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b),$ (23)

where in Eq (18), we use the definition of $\mathcal{U}_{p}(c_{h,i})$, in Eq
(20), we use the definition of $\mathcal{L}_{p}(c_{h,i})$. In Eq (21), we use
the assumption that $\mathcal{L}_{p}(c_{h,i})\leq f(c_{h,i})$. In Eq (22), we
use Lemma 10. Finally, in the last inequality at Eq (23), we use the
decreasing monotonicity of function $\delta(h;a,b)$ and the increasing
monotonicity of function $\beta_{p}$. By assumption that $h\leq p\leq N$,
hence $\delta(p-1;a,b)\leq\delta(h-1;a,b)$ and
$\beta^{1/2}_{p}\leq\beta^{1/2}_{N}$. We recall that
$\delta(h;a,b)=L_{1}Da^{-2\lfloor\frac{bh}{D}\rfloor}$ as in Definition 1.

Thus, for any $(h,i)\in I_{h}$, where $h\geq 2$, we have that

$L_{2}||x^{*}-c_{h,i}||^{2}\leq
2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b).$

Step 2: Bounding $|I_{h}|$ using covering balls.

We let $\Omega_{h}$ be the set of nodes $(h,i)$ at depth $h$ generated by
partitioning procedure $P(m;a,b)$. From $\Omega_{h}$ we define set
$\overline{I}_{h}$ as

$\overline{I}_{h}=\\{(h,i)\in\Omega_{h}\text{ such that
}L_{2}||x^{*}-c_{h,i}||^{2}\leq
2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)\\}.$

By this definition, $I_{h}\subseteq\overline{I}_{h}$ which implies directly
that $|I|_{h}\leq|\overline{I}_{h}|$. Now we consider the set of points
$c_{h,i}$ of these nodes. This set is defined as

$\overline{P}_{h}=\\{c_{h,i}\in\mathcal{X}|(h,i)\in\overline{I}_{h}\\}.$

We can see that all the points of $\overline{P}_{h}$ are covered by a
hypersphere centered at $x^{*}$ with radius
$\sqrt{\frac{2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)}{L_{2}}}$.
We call this hypersphere $\mathcal{S}_{h}$.

On the other hand, by Lemma 3, the smallest side of a cell $A_{h,i}$ at depth
$h$ is at least $a^{\lceil-\frac{bh}{D}\rceil}$. Therefore, if we bound a
point $c_{h,i}\in\overline{I}_{h}$ by a $D$-ball centered $c_{h,i}$ with
radius $a^{\lceil-\frac{bh}{D}\rceil}/2$ then all these balls are disjoint.
Further, even if there are several centers $c_{h,i}$ of these balls lying on
the boundary of $\mathcal{S}_{h}$ then all these balls must be within the
hypersphere centered at $x^{*}$ with radius

$\sqrt{\frac{2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)}{L_{2}}}+a^{\lceil-\frac{bh}{D}\rceil}/2.$

Thus, $|\overline{P}_{h}|$ cannot exceed the number of disjoint balls which
fit in the hypersphere centered at $x^{*}$ with radius
$\sqrt{\frac{2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)}{L_{2}}}+a^{\lceil-\frac{bh}{D}\rceil}/2$.

The number of these disjoint balls cannot exceed the proportion of the volume
of the hypersphere of radius
$\sqrt{\frac{\delta(h)+2\beta^{1/2}_{N}C_{2}L^{-\nu+D/2}(\delta(h-1))^{\nu-D/2}}{C_{1}}}$
and the volume of small balls of radius $a^{\lceil-\frac{bh}{D}\rceil}/2$.
This proportion is measured by

$(\frac{\sqrt{\frac{2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)}{L_{2}}}+a^{\lceil-\frac{bh}{D}\rceil}/2}{a^{\lceil-\frac{bh}{D}\rceil}/2})^{D}.$

Thus, we have that

$\displaystyle|\overline{P}_{h}|$ $\displaystyle\leq$
$\displaystyle(\frac{\sqrt{\frac{2\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+\delta(h;a,b)}{L_{2}}}+a^{\lceil-\frac{bh}{D}\rceil}/2}{a^{\lceil-\frac{bh}{D}\rceil}/2})^{D}$
(24) $\displaystyle=$
$\displaystyle(\sqrt{\frac{4\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+2\delta(h;a,b)}{L_{2}a^{2\lceil-\frac{bh}{D}\rceil}}}+1)^{D}$
(25)

However, by definition of $\overline{I}_{h}$ and $\overline{P}_{h}$,
$|I_{h}|\leq|\overline{I}_{h}|=|\overline{P}_{h}|$. Therefore, we have

$|I_{h}|\leq(\sqrt{\frac{4\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+2\delta(h;a,b)}{L_{2}a^{2\lceil-\frac{bh}{D}\rceil}}}+1)^{D}.$

Step 3: proving that there exists a constant $C$ such that $|I_{h}|\leq C$.

Using the assumption that $b=D$, we have
$a^{\lceil-2\frac{bh}{D}\rceil}=a^{-2h}$, $\delta(h-1;a,b)=L_{1}Da^{-2(h-1)}$,
and $\delta(h;a,b)=L_{1}Da^{-2h}$. Replacing these results to Eq (25), we get

$\displaystyle|I_{h}|$ $\displaystyle\leq$
$\displaystyle(\sqrt{\frac{4\beta^{1/2}_{N}C_{1}(\delta(h-1;a,b))^{\nu/2-D/4}+2\delta(h;a,b)}{L_{2}a^{2\lceil-\frac{bh}{D}\rceil}}}+1)^{D}$
(26) $\displaystyle=$
$\displaystyle(\sqrt{\frac{4\beta^{1/2}_{N}C_{1}(L_{1}D)^{\nu/2-D/4}a^{-(\nu-D/2)(h-1)}+2L_{1}Da^{-2h}}{L_{2}a^{-2h}}}+1)^{D}$
(27) $\displaystyle=$
$\displaystyle(\sqrt{\frac{4C_{1}(L_{1}D)^{\nu/2-D/4}}{L_{2}}\times\beta^{1/2}_{N}\times
a^{2h-(\nu-D/2)(h-1)}+\frac{2L_{1}}{L_{2}}}+1)^{D}$ (28) $\displaystyle\leq$
$\displaystyle(\sqrt{\frac{4C_{1}(L_{1}D)^{\nu/2-D/4}}{L_{2}}\times\beta^{1/2}_{N}\times
a^{4+D/2-\nu}+\frac{2L_{1}}{L_{2}}}+1)^{D}$ (29) $\displaystyle=$
$\displaystyle C^{\prime}(\sqrt{log(N/3\eta)}\times N^{(4+D/2-\nu)/D})^{D/2}$
(30)

where, Eq (29) holds because $a^{2h-(\nu-D/2)(h-1)}\leq a^{4+D/2-\nu}$.
Indeed, by using the assumption that $\nu>4+D/2$ and $h\geq 2$, we have that

$\displaystyle a^{2h-(\nu-D/2)(h-1)}$ $\displaystyle=$ $\displaystyle
a^{h(2+D/2-\nu)+(\nu-D/2)}$ $\displaystyle\leq$ $\displaystyle
a^{2(2+D/2-\nu)+(\nu-D/2)}$ $\displaystyle=$ $\displaystyle a^{4+D/2-\nu}.$

For the last inequality at Eq (30), we use the assumption
$a=\mathcal{O}(N^{1/D})$, $\beta_{N}=2log(\pi^{2}N^{3}/3\eta)$, where
$\eta\in(0,1)$, and the fact that $\frac{4C_{1}(L_{1}D)^{\nu/2-D/4}}{L_{2}}$
and $\frac{2L_{1}}{L_{2}}$ are constants independent of $N$. Thus, such a
constant $C^{\prime}$ at Eq (30) exists.

Since $\nu>4+D/2$, we have that
$\frac{\sqrt{log(N/3\eta)}}{N^{\frac{\nu-D/2-4}{D}}}\rightarrow 0$ as
$N\rightarrow\infty$. Therefore $\sqrt{log(N/3\eta)}\times
N^{(4+D/2-\nu)/D}\rightarrow 0$ as $N\rightarrow\infty$. Thus, there exists
constant $N_{1}>0$ and $C>0$ such that for every $N\geq N_{1}$, $|I_{h}|\leq
C$ for every $h\geq 2$. ∎

##  Appendix 5 Proof of Lemma 5

Let $(h_{p}^{*}+1,i^{*})$ be an optimal node of depth $h_{p}^{*}+1$ (i.e.,
$x^{*}\in A_{h_{p}^{*}+1,i^{*}}$). We define a node $(h,i)$ at depth $h$ as
$\delta(h;a,b)$-optimal if $\mathcal{U}(c_{h,i})\geq
f(c_{h,i})-\delta(h;a,b)$. We obtains the following result.

######  Lemma 12.

Assume that $f(c_{h_{p}^{*}+1,i^{*}})\leq\mathcal{U}(c_{h_{p}^{*}+1,i^{*}})$.
Then any node $(h_{p}^{*}+1,i)$ of depth $h_{p}^{*}+1$ before
$(h_{p}^{*}+1,i^{*})$ is expanded, is $\delta(h_{p}^{*}+1;a,b)$-optimal.

###### Proof.

If the node $(h_{p}^{*}+1,i^{*})$ has not been expanded yet, then by Algorithm
1 (line 4) we have that
$\mathcal{U}(c_{h_{p}^{*}+1,i})\geq\mathcal{U}(c_{h_{p}^{*}+1,i^{*}})$.
Combining with the assumptions, we get

$\displaystyle\mathcal{U}(c_{h_{p}^{*}+1,i})$ $\displaystyle\geq$
$\displaystyle\mathcal{U}(c_{h_{p}^{*}+1,i^{*}})$ (31) $\displaystyle\geq$
$\displaystyle f(c_{h_{p}^{*}+1,i^{*}})$ (32) $\displaystyle\geq$
$\displaystyle f^{*}-\delta(h_{p}^{*}+1;a,b),$ (33)

where Eq (32) use the assumption that
$f(c_{h_{p}^{*}+1,i^{*}})\leq\mathcal{U}(c_{h_{p}^{*}+1,i^{*}})$, and Eq (33)
use Lemma 3. Thus, the lemma holds. ∎

From Lemma 12, we deduce that once an optimal node of depth $h$ is expanded,
it takes at most $|I_{h+1}|$ node expansions at depth $h+1$ before the optimal
node of depth $h+1$ is expanded. From that observation, we deduce the
following lemma (corresponding to Lemma 5 in the main paper.)

######  Lemma 13.

Assume that $f(c_{h,i})\leq\mathcal{U}(c_{h,i})$ for all optimal node $(h,i)$
at each depth $0\leq h\leq h_{max}(n)$. Then for any depth $0\leq h\leq
h_{max}(n)$, whenever $n\geq h_{max}(n)\sum_{i=0}^{h}|I_{i}|$, we have
$h^{*}_{n}\geq h$.

###### Proof.

We prove it by induction. For $h=0$, we have $h_{n}^{*}\geq 0$.

Assume that the proposition is true for all $o\leq h\leq h_{0}$ with
$h_{0}<h_{max}(n)$. Let us prove that it is also true for $h_{0}+1$. Let
$n\geq h_{max}(n)(|I_{0}|+|I_{1}|+...+|I_{h_{0}+1}|)$. Since $n\geq
h_{max}(n)(|I_{0}|+|I_{1}|+...+|I_{h_{0}}|)$, we have $h^{*}_{n}\geq h_{0}$.
If $h^{*}_{n}\geq h_{0}+1$ then the proof is finished. If $h^{*}_{n}=h_{0}$,
we consider the nodes of depth $h_{0}+1$ that are expanded. We have seen that
as long as the optimal node of depth $h_{0}+1$ is not expanded, any node of
depth $h_{0}+1$ that is expanded must be $\delta(h_{0}+1;a,b)$-optimal, i.e.,
belongs to $I_{h_{0}+1}$. Since there are $|I_{h_{0}+1}|$ of them, after
$h_{max}(n)|I_{h_{0}+1}|$ node expansions, the optimal one must be expanded,
thus $h^{*}_{n}\geq h_{0}+1$. ∎

##  Appendix 6 Proof of Lemma 6

We use $A_{p}$ to denote the set of all points evaluated by the algorithm and
all centers of optimal nodes of the tree $\mathcal{T}_{p}$ after $p$
evaluations.

######  Lemma 14.

Pick a $\eta\in(0,1)$. Set $\beta_{p}=2log(\pi^{2}p^{3}/3\eta)$ and
$\mathcal{L}_{p}(c)=\mu_{p}(c)-\beta^{1/2}_{p}\sigma_{p}(c)$. With probability
$1-\eta$, we have

$\mathcal{L}_{p}(c)\leq f(c)\leq\mathcal{U}_{p}(c),$

for every $p\geq 1$ and for every $c\in A_{p}$.

###### Proof.

After $p$ evaluations, there are at most $p$ evaluated points by the
algorithm. On the other hand, after $p$ evaluations, the deepest depth of the
tree $\mathcal{T}_{p}$ is $p$. In addition, at each depth, there is only one
optimal node which contains $x^{*}$. Therefore, there are at most $p$ centers
of optimal nodes which belong to tree $\mathcal{T}_{p}$. Thus, $|A_{p}|\leq
2p$.

The proof is similar to Lemma 5.1 in (Srinivas et al., 2012) and Lemma 4 in
(Wang et al., 2014) with the set $A_{p}$ (here we use the fact that $f$ is a
sample from the GP). If we let $\beta_{p}=2log(\pi^{2}p^{2}|A_{p}|/6\eta)$,
then with probability $1-\eta$, we have

$\mathcal{L}_{p}(c)\leq f(c)\leq\mathcal{U}_{p}(c),$

for every $p\geq 1$ and for every $c\in A_{p}$. Since $|A_{p}|\leq 2p$, we
will use $\beta_{p}=2log(\pi^{2}p^{3}/3\eta)$ instead and the lemma also holds
with this $\beta_{p}=2log(\pi^{2}p^{3}/3\eta)$. ∎

Lemma 6 implies that with probability $1-\eta$, all conditions
$\mathcal{L}_{p}(c)\leq f(c)\leq\mathcal{U}_{p}(c)$ in Lemma 4, Theorem 1, and
Lemma 5 in the main paper hold for every $1\leq p\leq N$.

##  Appendix 7 Proof of Theorem 2

######  Theorem 4 (Regret Bound).

Assume that there is a partitioning procedure $P(m;a,b)$ where
$a=\mathcal{O}(N^{1/D})$, $b=D$ and $2\leq m<\sqrt{N}-1$. Let the depth
function $h_{max}(p)=\sqrt{p}$. We consider $m^{2}<p\leq N$, and define $h(p)$
as the smallest integer $h$ such that

$h\geq\frac{\sqrt{p}-m-1}{C}+2,$

where $C$ is the constant defined by Theorem 1. Pick a $\eta\in(0,1)$. Then
for every $N\geq N_{1}$, the loss is bounded as

$\displaystyle r_{p}$ $\displaystyle\leq$
$\displaystyle\delta(\text{min}\\{h(p),\sqrt{p}+1\\};a,b)+4C_{1}\beta^{1/2}_{p}(\delta(\text{min}\\{h(p)-1,\sqrt{p}\\};a,b))^{\nu/2-D/4},$

with probability $1-\eta$, where $N_{1}$ is the constant defined in Theorem 1,
$C_{1}$ is the constant defined in lemma 4 and
$\beta_{N}=\sqrt{2log(\pi^{2}N^{3}/3\eta)}$.

###### Proof.

By Theorem 1, the definition of $h(p)$ and the facts that $|I_{0}|=1$ and
$|I_{1}|\leq m$, we have

$\displaystyle\sum_{l=0}^{h(p)-1}|I_{l}|$ $\displaystyle=$
$\displaystyle|I_{0}|+|I_{1}|+(|I_{2}|+...+|I|_{h(p)-1})$ $\displaystyle\leq$
$\displaystyle 1+m+C(h(p)-2)\leq\sqrt{p}$

Therefore, $\sum_{l=0}^{h(p)-1}|I_{l}|\leq\sqrt{p}$. By Lemma 5 when
$h(p)-1\leq h_{max}(p)=\sqrt{p}$, we have $h_{p}^{*}\geq h(p)-1$. If
$h(p)-1>\sqrt{p}$ then $h_{p}^{*}=h_{max}(p)=\sqrt{p}$ since the BOO algorithm
does not expand nodes beyond depth $h_{max}(p)$. Thus, in all cases,
$h_{p}^{*}\geq\text{min}\\{h(p)-1,\sqrt{p}\\}$.

Let $(h,j)$ be the deepest node in $\mathcal{T}_{p}$ that has been expanded by
the algorithm up to $p$ expansions. Thus $h\geq h_{p}^{*}$. By Algorithm 1, we
only expand a node when its GP-UCB value is larger than $v_{max}$ which is
updated at Line 10 of Algorithm 1. Thus, since the node $(h,j)$ has been
expanded, its GP-UCB value is at least as high as that of the some node
$(h_{p}^{*}+1,o)$ at depth $h_{p}^{*}+1$, such that

  * •

(1) node $(h_{p}^{*}+1,o)$ has been evaluated at some $p^{\prime}$-th
expansion before node $(h,j)$ and

  * •

(2)
$(h_{p}^{*}+1,o)\in\text{argmax}_{(h_{p}^{*}+1,i)\in\mathcal{L}}\mathcal{U}_{p^{\prime}}(c_{h_{p}^{*}+1,i})$
(see Line 4 of Algorithm 1).

We let node $(h_{p}^{*}+1,o^{*})$ be the optimal node at depth $h_{p}^{*}+1$.
With probability $1-\eta$,

$\displaystyle f(x^{*})-\delta(h_{p}^{*}+1;a,b)$ $\displaystyle\leq$
$\displaystyle f(c_{h_{p}^{*}+1,o^{*}})$ (34) $\displaystyle\leq$
$\displaystyle\mathcal{U}_{p^{\prime}}(c_{h_{p}^{*}+1,o^{*}})$ (35)
$\displaystyle\leq$ $\displaystyle\mathcal{U}_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
(36) $\displaystyle\leq$
$\displaystyle\mu_{p^{\prime}}(c_{h_{p}^{*}+1,o})+\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
(37) $\displaystyle\leq$
$\displaystyle\mu_{p^{\prime}}(c_{h_{p}^{*}+1,o})-\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
(38) $\displaystyle\leq$
$\displaystyle\mathcal{L}_{p^{\prime}}(c_{h_{p}^{*}+1,o})+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
(39) $\displaystyle\leq$ $\displaystyle
f(c_{h_{p}^{*}+1,o})+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
(40) $\displaystyle\leq$
$\displaystyle\mathcal{U}_{p}(c_{h,j})+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o}),$
(41)

where in Eq (34), we use Lemma 3. Eq (35) holds with probability $1-\eta$ by
using Lemma 6. In Eq (36), we use the above condition (2). Eq (37) uses the
definition of $\mathcal{U}_{p^{\prime}}$. Eq (39) uses the definition of
$\mathcal{L}_{p^{\prime}}$. Eq (40) holds with probability $1-\eta$ by using
Lemma 6. Finally, Eq (41) uses the updating condition at Line 5 and Line 10 of
Algorithm 1.

Eq (41) implies that with probability $1-\eta$,

$f(x^{*})-\mathcal{U}_{p}(c_{h,j})\leq\delta(h_{p}^{*}+1;a,b)+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o}).$

On the other hand, by Lemma 6, with probability $1-\eta$, we have

$\displaystyle U_{p}(c_{h,j})$ $\displaystyle=$
$\displaystyle\mu_{p}(c_{h,j})+\beta^{1/2}_{p}\sigma_{p}(c_{h,j})$
$\displaystyle=$
$\displaystyle\mathcal{L}_{p}(c_{h,j})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,j})$
$\displaystyle\leq$ $\displaystyle
f(c_{h,j})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,j})$

Combining these two results, we have

$f(x^{*})-f(c_{h,j})\leq\delta(h_{p}^{*}+1;a,b)+2\beta^{1/2}_{p^{\prime}}\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})+2\beta_{p}^{1/2}\sigma_{p}(c_{h,j}),$

with a probability $1-\eta$.

Finally, by using Lemma 4 to bound $\sigma_{p^{\prime}}(c_{h_{p}^{*}+1,o})$
and $\sigma_{p}(c_{h,j})$ and using the fact that the function $\delta(*;a,b)$
decreases with their depths, we achieve

$\displaystyle r_{p}$ $\displaystyle\leq$ $\displaystyle f(x^{*})-f(c_{h,j})$
$\displaystyle\leq$
$\displaystyle\delta(\text{min}\\{h(p),\sqrt{p}+1\\};a,b)+4C_{1}\beta^{1/2}_{p}(\delta(\text{min}\\{h(p)-1,\sqrt{p}\\};a,b))^{\nu/2-D/4}$

with a probability $1-\eta$. ∎

##  Appendix 8 Proof of Corollary 1

######  Corollary 2.

Pick a $\eta\in(0,1)$. There exists a constant $N_{2}>0$ such that for every
$N\geq N_{2}$ we have that the simple regret of the proposed BOO with the
partitioning procedure $P(m;a,b)$ where
$a=\lfloor(\frac{\sqrt{N}}{2})^{\frac{1}{D}}\rfloor$, $b=D$, is bounded as

$r_{N}\leq\mathcal{O}(N^{-\sqrt{N}}),$

with probability $1-\eta$.

###### Proof.

With $a=\lfloor(\frac{\sqrt{N}}{2})^{\frac{1}{D}}\rfloor$ and $b=D$,
$m=a^{b}\leq\sqrt{N}/2$. These conditions satisfy the assumptions of Theorem
2, therefore following Theorem 2 with probability $1-\eta$, we have that

$\displaystyle
r_{N}\leq\underbrace{\delta(\text{min}\\{h(N),\sqrt{N}+1\\};a,b)}_{\text{Term
1}}+\underbrace{4C_{1}\beta^{1/2}_{N}(\delta(\text{min}\\{h(N)-1,\sqrt{N}\\};a,b))^{\nu/2-D/4}}_{\text{Term
2}}.$

We consider Term 1. There are two cases:

(1) If $\text{min}\\{h(N),\sqrt{N}+1\\}=\sqrt{N}+1$ then
$\delta(\text{min}\\{h(N),\sqrt{N}+1\\};a,b)=\delta(\sqrt{N}+1;a,b)=L_{1}Da^{-2(\sqrt{N}+1)}\leq\mathcal{O}(N^{-\sqrt{N}})$
by replacing $a=\lfloor(\frac{\sqrt{N}}{2})^{\frac{1}{D}}\rfloor$.

(2) If $\text{min}\\{h(N),\sqrt{N}+1\\}=h(N)$. By definition of $h(N)$ in
Theorem 2,
$h(N)\geq\frac{\sqrt{N}-m-1}{C}+2\geq\frac{\sqrt{N}}{2C}-\frac{1}{C}+2$.
Therefore,
$\delta(\text{min}\\{h(N),\sqrt{N}+1\\};a,b)=\delta(h(N);a,b)=L_{1}Da^{-2h(N)}\leq\mathcal{O}(N^{-\sqrt{N}})$.

Thus, for both cases, Term 1 is bounded by $O(N^{-\sqrt{N}})$. We now consider
Term 2. There are also two cases:

(1) If $\text{min}\\{h(N)-1,\sqrt{N}\\}=\sqrt{N}$ then
$4C_{1}\beta^{1/2}_{N}(\delta(\text{min}\\{h(N)-1,\sqrt{N}\\};a,b))^{\nu/2-D/4}=4C_{1}\beta^{1/2}_{N}(\delta(\sqrt{N};a,b))^{\nu/2-D/4}=4C_{1}L_{1}D\beta^{1/2}_{N}a^{-2(\nu/2-D/4)\sqrt{N}}\leq
4C_{1}L_{1}D\beta^{1/2}_{N}a^{-4\sqrt{N}}$. In the last inequality, we use the
assumption that $\nu>4+D/2$. The component $a^{-4\sqrt{N}}$ with
$a=\lfloor(\frac{\sqrt{N}}{2})^{\frac{1}{D}}\rfloor$ dominates $\beta_{N}$
which is $\mathcal{O}(\sqrt{N})$. Therefore Term 2 is bounded by
$O(N^{-\sqrt{N}})$.

(2) If $\text{min}\\{h(N)-1,\sqrt{N}\\}=h(N)-1$. By definition of $h(N)$ in
Theorem 2,
$h(N)-1\geq\frac{\sqrt{N}-m-1}{C}+1\geq\frac{\sqrt{N}}{2C}-\frac{1}{C}+1$.
Then
$4C_{1}\beta^{1/2}_{N}(\delta(\text{min}\\{h(N)-1,\sqrt{N}\\};a,b))^{\nu/2-D/4}=4C_{1}\beta^{1/2}_{N}(\delta(h(N)-1;a,b))^{\nu/2-D/4}=4C_{1}L_{1}D\beta^{1/2}_{N}a^{-2(\nu/2-D/4)(h(N)-1)}\leq
4C_{1}L_{1}D\beta^{1/2}_{N}a^{-4(h(N)-1)}$. By the argument similar as above,
we have that Term 2 is bounded by $O(N^{-\sqrt{N}})$.

Finally, for all cases, we get that $r_{N}\leq O(N^{-\sqrt{N}})$ with
probability $1-\eta$. ∎

##  Appendix 9 Ablation study between function sampling and partitioning
procedure in the proposed BOO algorithm

To show this point, we have performed additional experiments with $m=64$ (see
Figure below). The left plot shows different partitioning procedures while
function sampling is fixed to our proposed scheme. We can see good improvement
when $b=D$ compared to $b=1$ case. The right plot compares BaMSOO with our
method which uses the proposed function sampling scheme but keeps using
BaMSOO’s partitioning procedure ($b=1$, $m=64$). In this case, we are not able
to outperform BaMSOO. However, our result for $b=D$ in the left plot is
significantly better than that of BaMSOO. This clearly shows that the effect
of partitioning procedure is higher than that of the function sampling.