Optimistic Optimization of Gaussian Process Samples
Authors: Julia Grosse
Cheng Zhang
Philipp Hennig
Venue: Accepted by TMLR ()

Abstract: Bayesian optimization is a popular formalism for global optimization, but its computational costs limit it to expensive-to-evaluate functions. A competing, computationally more effi- cient, global optimization framework is optimistic optimization, which exploits prior knowl- edge about the geometry of the search space in form of a dissimilarity function. We investi- gate to which degree the conceptual advantages of Bayesian Optimization can be combined with the computational efficiency of optimistic optimization. By mapping the kernel to a dissimilarity, we obtain an optimistic optimization algorithm for the Bayesian Optimization setting with a run-time of up to $O(N log N )$. As a high-level take-away we find that, when using stationary kernels on objectives of low evaluation cost, optimistic optimization can be preferable over Bayesian optimization, while for strongly coupled and parametric models, Bayesian optimization can perform much better, even at low evaluation cost. As a concep- tual takeaway, our results demonstrate that balancing exploration and exploitation under Gaussian process assumptions does not require computing a posterior.

Published in Transactions on Machine Learning Research (09/2023)
Optimistic Optimization of Gaussian Process Samples
Julia Grossc
Tübingen Al Center, University of Tübingen, Germany
Cheng Zhang
thenng.zhong@mmierrooff..cm
Microsoft Research, Cambridge, United Kingdom
Philipp Hennig
Tübingen Al Center, University of Tübingen, Germany
Reviewed on OpenReview: https: // openreview. net/ forum? id- KQ55T19kF3
Abstract
Bayesian optimizatiin is popular formalism for global optimization, but its computational costs limit it to expensive-to-evallen functions. A competing, computationally more effi- cient, global optimization framework is optámistic optimization, which exploits prior knowl- edge about the geometry of the search space in form of a dissimilarity function. We investi- gate to which degree the conceptual advantages of Bayesian Optimization can be combined with the computational efficiency optimistic optimization. By mapping the kernel to a dissimilarity, we obtaín an optimistic optimization algorithm for the Bayesian Optimization setting with a run-time of up O(N log N) in terms of number of function evaluations. As high-level take-away we find that, when using stationary kernels on objectives of low eval- uation cost, optimistic optimization can be preferable over Bayesian optimization, while for strongly coupled and parametric models, Bayesian optimization can perform much better, even at low evaluation cost. As a conceptual lakeaway, our results demonstrate that bal- ancing exploration and exploitation under Gaussian process assumptions does not require computing a posterior.
1 Introduction
Bayesian optimization (BO) (Shahriari et al., 2015) a popular and successful framework for global opti- mization. The foundation of most BO frameworks is a Gaussian Process (GP) regression method, whose kernel encodes prior knowledge about the objective function. This GP regressor provides posterior over the objective, probabilistic surrogate which one can then reason about the extremum, and its location. This can be done in variety of ways, e.g. by using the posterior to construct upper bounds (in GP-UCE Srinivas et al. (2009)), to estimate expected improvement (Močkus, 1975) or information gain (Hennig & Schuler, 2012; Wang & Jegelka, 2017).
The computational cost BO itself significant, and arises from at least two sources: First, exact GP inference has cost ((N3), where N is the number of observed function values ("samples"). Second, finding the next evaluation location requires continuous, numerical optimization of the acquisition function. Since this utility function is generally multimodal, optimization should, at least in principle, be carried out increasingly fine grid, which contributes up to ([V2d) costs (Salgia et al., 2021). A third source of cost be the construction of the acquisition function itself, but there are some popular choices, like GP-UCB, for which this step is essentially trivial sum of the mean and marginal standard--deviation constructed during inference, of negligible overhead. the cost individual function evaluations very high, then the overhead of BO irrelevant. But there are scenarios in which the cost of BO concern, namely when individual function evaluations are of intermediate cost, and (perhaps as direct consequence), the total number N of evaluations is sufficiently large to make the cubic cost of GP inference noticeable. An example are settings

---

Published in Transactions on Machine Learning Research (09/2023)
involving computer simulations runs, e.g. in robotics, biology, chemistry and human-compiteer interaction design.
Considering this "middle ground" between sample and computational efficiency, we study a competing frame- work for global optimization, optimistic optimization (00), which has drastically lower computational over- head. OO does not require computing an explicit global posterior on the objective. However, 00 can nevertheless leverage at least certain kinds of prior knowledge, captured in the form of Lipechitz condition with respect to greudo-metric, more generally a dissimilarity function. Functions from GP prior fulfill similar condition with respect to the canonical aseudo-metrie of the GP. This in effect produces map from GP prior one might otherwise use in BO to a (much more time-cfficient) 00 model, so that prior knowledge encoded in the GP can be leveraged without the intermediate step of (cubically expensive) GP regression. For noiseless observations, the resulting O0 algorithm achieves ( log N) computational cost.
In summary, we provide a practical map between BO to O0 for global optimization (Section 3), resulting in hybrid method we call GP-OO. We then contribute formal analysis of this method in terms of regret (Section 5), also pointing out limitations in the process. Experiments (Section 6) corroborate that the proposed GP-OO can be significantly more time-efficient than classical BO methods like GP-UCB and El in settings with low function evaluation costs.
2 Background
2.1 Bayesian Optimization (BO)
We consider maximizing a function f:: + R. Throughout, f demotes the maximum of the function, and x", the point where it is attained. k: X' x X' + R is a kernel function. The function f is assumed to be a sample from a GP GP(H, k). We assume that the GP is centered, i.e. p= 0. One has access to observations ys, where Y +N(0, A). The noiseless setting amounts to the assumption - 0. After each new observation the posterior over the function is updated:
[n(x)= (z) (K, (K,++M1 +1)
(1)
(x, = k(z)) x) kn) (K,, + k,,
(2)
h((,) )F= and K,, is the Gram matrix with Knij ki (x The posterior used to define an acquisition function a, (x) whose maximum the function evaluated next. For an overview of different options of acquisition functions see Frazier (2018). We will focus our analysis the choice of GP-UCB Srinivas et al. (2009), where
where yn = [W,..., yn] (x) = (M.
(x) = (x) + (2,
and 2 an appropriate constant. An advantage of GP-UCB over other choices comparatively simple structure, which facilitates not just implementation but also analysis. While other acquisition functions may well be more sample-effccient in concrete settings, this will not be important for what is to follow, because are primarily concerned with run-time complexity, where GP-UCB is one of the fastest possible choices of the classical BO methods. Furthermore, it is most similar to 00 from conceptual point of view as 00 also relies on upper bounds as outlined in the next paragraph.
2.2 Optimistic Optimization (00)
The optimistic optimization principle is used to optimize functions that are known to fulfill a local Lipschitz assumption with respect to a dissimilarity d X' x X' + R:
Yo E X [f(x)) - f(x)] s d()",x).
(3)
The method revolves around hierarchical partitioning of the search space X' that can be described by an infinite binary tree. Search can thus be implemented as fast descent through the tree, thus only involves evaluations a countable set of mesh points, in contrast to the local numerical optimization done within
2

---

Published in Transactions on Machine Learning Research (09/2023)
Figure 1: Optimistic optimization applied to a sample from a GP. The upper bounds are shown as horizontal bars. The vertical lines point to the evaluated locations.
Bayesian optimization. This is one the two reasons for the drastically shorter run-time costs of 00 over BO (the other being that does not require computing a GP posterior).
The root node corresponds to the entire search space Xo,, X and is named (0, 1). Consider node (t, at depth t. The left child (t + 2, 1) and right child (t 1, represent two subregions ((++122111 and 2(+1,22)) such that K(t.i) = 1,2122111 U ((++),2)), i.e. the tree covers the entire space. To indicate that a cell was explored at iteration n, we refer to it as X, Intuitively, it makes sense to select the cells in such a way that all points in coll are similar to each other and all similar points are in the same coll. Formally, this can be expressed as
(a) Va,y y E Mus (d(a,y) < 8(1)
(b) ( E X: d(=(.,))) < c(())) CR..
where 8(t) a decreasing sequence of diameters and e is a global constant. During search, the tree is build incrementally by adding the two children of a selected node. When new node (t, i) added, an observation is made at the center f(t.)) of the region X(.)) In each round, the leaf with the highest upper bound U(..) = fI(())) 5(t) is selected for expansion. Since f is assumed d, selecting nodes by U0, is a valid upper bound strategy (assuming noiscless observations). The sequence of 8(L) controls exploration. Therefore, the partitioning should be chosen in such way, that the d(t) can be small as possible The optimistic optimization principle is summarized in Algorithm 1 and Figure 1. Using a binary heap, the priority queue for the leaf nodes can be realized in O(N log N) if the budget N is known in advance.
be locally Lipschitz with respect
Algorithm The optimistic optimization principle.
1: procedure OPTIMISTIC OPTIMIZATION(S.
2: priority-queue + [[0,1)] //root node
3: for j = = to n do
4: Select node (t, with maximum U(. = f(z(e.)) + 6(t) from the priority-queue
Observe f 1,2 and f for the two children (t,
Caleulate child utilities U(412(11) = =[1044111))+
and U(4+1220 [x + 0((+1) 1).
Add children (t 1, 2i 1) and (t + 1,) to the priority-queue based on their utilities.
8: end for end procedure
This algorithm is batch method the sense that all children of a newly explored node are evaluated in each step. We assume batch size two, but other choices possible too and might be preferable in some
3

---

Published in Transactions on Machine Learning Research (09/2023)
applications, e.g. when parallel evaluation is possible. A conceptual difference to the upper bound in GP- UCB is that one here works with upper bounds for entire regions of the search space, not for individual points in it. Also, the exploration term o(t) in the upper bound is not updated based on new observations, but derived a priori. Nevertheless, the exploration term, aka. the uncortainty decreases during the search as the tree grows.
The hierarchical optimistic optimization principle has its origins in the Bandit setting. Bubeck et al. (2011) apply it in the noisy setting, Munos (2011) apply it in the noiseless setting and Kleinberg et al. (2008)
uses it with slightly different Lipschitz assumption. The assumptions on the dissimilarity d vary, e.g. some theoretical analyses require that it additionally is semi-metric, or metric. Munos (2011) introduces a variant of the principle, simultaneous optimistic optimization (S00), for situations in which the dissimilarity function is unknown. Valko et al. (2013) extend this idea to the noisy setting. The popular DiRect algorithm (Jones & Martins, 2021) also belongs to the family partitioning based global optimization algorithms, but does not allow for encoding of prior knowlodge on the smoothness of the function.
An interim summary: OO descends along search tree, i.e. in discrete sequence of steps, without numerical optimization, and only using local summary statistics, rather than updating a global posterior. This makes OO very fast, at least compared to Bayesian optimization. But the approach also has a downside: At least at first sight, it is not clear how to encode salient prior information about the global optimization problem into the algorithm. By contrast, many Bayesian optimization experts see the rich language of GP prior models as a key strength of the BO framework. The following section thus investigates formal connections between 00 and BO. The goal is to understand to which degree the structural language of a GP prior can be translated into the algorithmic efficiency of 00.
3 Gaussian Process Optimistic Optimization
The policy of 00 is based on measuring (dis)similarity in the input domain in terms of a pseudo-metric. It turns out that Gaussian process models or, more preciscly, kernels such a pseudo-metric (Section 3.1). We further show how the pseudo-metric can be used to obtain upper bounds on the supremum of the cell (Section 3.2), that allow for the application of the 00 principle in the BO setting. Section 3.3 is concerned with how to choose the cells and in Section 3.4 we illustrate the derived concept (GP-0O) on concrete examples.
be used immediately to define
3.1 Canonical aseudo-metric
The canonical pseudo-metric d: X' x X + E for a centered GP is defined as
d(z, y) (x= -
Vkxx + k(y. v) 2k(x, v)-
The relevance of the canonical pseudo-metris metric for optimization arises from the following deviation inequality (Pisier (1999), Theorem 4.7):
u2
Vu 0,P((((x) f()) 2 w) S 2exp
2d (x. y)²
The intriguing aspect of this inequality is that it relates distances [f(x) f(y) "along the ordinate" with distances d(z, y) "along the abscissa". This suggests that the inequality is informative for balancing exploita- tion ("progress along the ordinatc") with exploration ("progress along the abscissa"). From a conceptual point of view, the main motivation of this work consists in deriving an adaplive optimization algorithm, iee an optimization algorithm that able to trade-off exploration with exploitation based on observed func- tions values, relying on the above incquality instead of GP regression. The 00 principle well suited for this attempt due to its upper-bound based acquisition strategy with a simple additive structure of function observations and exploration terms.
4

---

Published in Transactions on Machine Learning Research (09/2023)
3.2 Upper bound on the supremum of cell
The first challenge in applying the optimistic optimization principle samples of GP consists in the probabilistic nature of the deviation inequality. To obtain valid upper bound for the maximal deviation in a cell supæex, an upper bound by introducing two simplifications: We discretize the search space X' into a finile number of points & and we introduce an independence assumption between the [f(x) - f(xn)]. Then we take a union bound approach:
the deviation for all points in the cell has to be bounded. We approximate such
P( sup 1f(z) f(xn)) 2 u) aEd,
(4)
Σ P(f(z)) f(2n)) 2 u)
(5)
u²
2 Σ exp
(6)
2d (d((x,1) y)
u²
1 2 exp(
(7)
21 X, )2
where A = max d(zn: 2). 2
(8)
The bounds have to hold at each step n, so we additionally take a union bound over the number of steps. This implies the following statement, that holds with high probability:
Vn: : sup 1f(x) (zx)) < 8//2 A(X.) =
(9)
where 3n are appropriate constants specified in the Supplements. The union bound approximation will be good if the f(x)) are (nearly) uncorrelated, or the size of the discretization |.8] is chosen sufficiently small. Otherwise the bounds are loose, which leads to over-exploration. Though approximate, this idea of neglecting correlations simplify the calculation of the expected supremum of dependent Gaussian variables is, for example, also done in Maximum Value Entropy Search (Wang & Jegelka, 2017) for BO and in related settings (Grosse et al., 2021). The other extreme, greedy approach with 8n 1 has also been taken in recent work (Rando et al., 2022). For stationary kernels, we experimented with hcuristical choices based on the lengthscale, see Appendix A.2.2. With generic chaining (Talagrand, 1996) it is possible to improve over the union bound approach. However, to the best of our knowledge state-of-the-ee et al., 2020) to optimize for tighter bounds require polynomial run-time in the number of points per cell for arbitrary kernel functions. For special cases, like a Wiener kernel (Talagrand, 2021) or Matérn kernel functions (Shekhar & Javidi, 2018) analytical attempls to derive chaining based upper bounds exist.
algorithms (Borst
3.3 Choosing how to partition
The second main step in applying the OO principle is to choose the cells and location of the centers in such a way that the diameters of the cells are as small as possible. For l children nodes, this is a metric k-center problem- - one of the classical NP-hard problems (Gonzalez, 1985). A greedy approximation consists in iteratively picking the & centers with the largest distance to the previously picked centers, and requires O((8)) time. The greedy procedure is guaranteed result in 2-approximation, and there is no polynomial time algorithm doing better (unless P=NP). Working with a greedy instead of the optimal partition scheme thereby leads to an additional factor of 2 in the below regret bound, but is not harmful in the sense that the scarch gets stuck in local optimum. Na-hardness also appears in the context of BO, c.g. the exploration term used in GP-UCB. And the acquisition functions of information-theoree Schuler, 2012), (Wang& & Jegelka, 2017) are related to the maximization of information gain, which is also a NP-hard problem.
BO methods (Hennig &
From an implementation perspective, is desirable constrain the partition to axis-parallel boxes. For some kernel functions, e.g. the polynomial kernel, requirement, (b) of the 00 principle cannot be fulfilled
5

---

Published in Transactions on Machine Learning Research (09/2023)
with axis parallel boxes. One nevertheless the algorithm, but it will clearly be less information- efficient. One may even consider randomized choice of centers, e.g- as done in Monte Carlo Tree Search (Chaslot et al., 2008). However, it still remains to calculate the maximal distance from a point in the cell X to the center Zn- The computational complexity of this part comparable to the numerical optimization of the acquisition function BO. An advantage is that the domain over which one optimizes shrinks in each step. A disadvantage, though, is that if the numerical optimization is suboptimal and the maximal distance within cell is underestimated, cells containing the optimum might get irreversibly pruned.
An important observation is that the partition scheme itself does not depend the objective f. but only the kernel/distane function (how the search tree grows, however, does depend on f). This opens up the possibility of finding a good partition and the corresponding maximal distances analytically. An important class of kernel-induced metries is formed by monotonic transformations of the Euclidean metric, i.e. d(x, y) g[1æ - -2l2)) where R + monotonically increasing. Many kernels used practice are this class, e.g. the square-cxponential kernel, the Matérn class of kernels, the rational-quadratic kernels and the Wiener kernel as well sums and products thereof. We refer to this class of kernels as K. For distances derived from kernels in K,, one apply the following regular partition scheme: At each step, cut along the longest dimension in order to obtain the two children cells with respect to the euclidean metric. Use the euclidean centers as centers. A point that maximizes the distance to the center will always be one of the 2 corner points in m dimensions. However, one only has to calculate the distance from the center to one of them. Thus, for this type of kernels, the costs reduce to (m) for the partition, or ON log N +N -N-m) = (N log N) in total. Kernels not in K. are e.g. polynomial or periodic kernels.
square exponential
Matérn 3/2
quadratic (regular)
quadratic (canonical)
GP-00 GP-UCB
Figure 2: Lower row: Cells and diameters A. Brighter colors indicate smaller diameters. Upper row: Sample from a GP and evaluation locations GP-OO and GP-UCB. Bright colors indicate higher function values.
3.4 GP-00
Motivated by the analysis above, we propose a variant of OO, which we call GP-OO. It consists in running Algorithm 1 with the utility U(n) = f()()) 3//2 A(Xx) in line 4, where A is defined in Eq. equation 8, Figure 2 shows the algorithm running on GP samples from squarc-exponential and a Matérn kernel with и = 2/3 on the domain [0, 50, as well as from a quadratic kernel on the domain 1J2. In regions with higher function values the partitions are finer. The Matérn kernel yields higher distances than the square exponential, leading to more exploration, reflecting that the samples are less smooth. By optimizing the partitions and centers of the cells with respect to the canonical pseudo-metric, larger parts of the search space be covered while keeping the cell diameters constant shown by the two examples with the

---

Published in Transactions on Machine Learning Research (09/2023)
quadratic kernel. However, as GP-OO is restricted evaluations grid, it usually requires more steps than GP-UCB to reach the optimum even if the grid is refined in the right regions.
4 Related Work
4.1 Work at the intersection of BO and 00
With the exception of Grill et al. (2018), the fundamental difference to all of this work is that we do not keep track of a GP-posterior, thus saving significant computational cost.
Work without the canonical pseudo-metric. BO methods have been combined with SOO (Munos (2011)), the version of O0 with unknown dissimilarity. In BamSOO, Wang et al. (2014) use GP-UCB to reduce the number of evaluations required when running SOO alone. By using SOO, they can in return reduce the optimization costs of the acquisition function. Gupta et al. (2021) improve upon the basic version of BamSOO by a more elaborate partitioning scheme: Instead of dividing a cell into children along the longest side of the cell, they divide along the longest dimensions into a cells, where b = k. Salgia et al. (2021) use a random walk based strategy on a tree to improve over the grid-based optimization of the GP-UCB acquisition function. For the Matérn and Squared Exponential kernel, they achieve order optimal regret, but the computational complexity is O(N4).
Work with the canonical pseudo-metric Shekhar & Javidi (2018) use the GP's canonical pseudo- metric to improve the numerical optimization by pruming the search regions. They additionally keep track of the posterior to only evaluate al. locations where posterior uncertainly exceeds the cell's upper bound. Rando et al. (2022) follow this approach and additionally introduce a Nyström approximation, which allows for approximate inference in O(Nada)) where deff is the effective dimension the search space. Contal et al. (2015) replace the GP-UCB bounds with bounds derived from the pseudo-metrie, but do not use a hierarchical approach, i.e. they construct bounds for individual points. They update the posterior and the exploration terms after every new observation.
Grill et al. (2018) apply the optimistic optimization principle to a one-dimensional Brownian walk. A minor difference is, that they evaluate cell at the corners of an interval and not in the center. There are cases, where this is advantagcous, c.g. think of samples from a GP with a polynomial or lincar kernel. However, the number corners scales exponentially with the dimension.
4.2 Work on scalable BO
TurBO (Eriksson et al., 2019) uses independent local GP models for a number of trust regions. Trust regions are shrinked or expanded based on heuristics capturing how much progress was made in the previous steps. A global Bandit strategy is used to decide in which of the trust regions to contimue the search. Due to the heuristics involved it is less amendable for theoretical analysis. Other approaches to speed up BO rely on Bayesian neural networks (Snock et al., 2015), lower dimensional embeddings (Wang et al., 2016). approximations to the GP (e.g. Jimenez & Katzfuss, 2022) or additive model assumptions (Han el al., 2021; Mutny& & Krause, 2018).
5 Regret
While computational and not sample efficiency is our main motivation to apply the 00 principle in the BO setting, we show that the resulting method nevertheless leads to non-trivial regret. In particular, is asymptotically regret-free the limit lim Rx /N. Here, Ry denotes the cumulative regret defined as Rx = Σ f(x*) (xx)
Building upon arguments from Munos (2011) and Shekhar & Javidi (2018), we obtain the following guarantee for the cumulative regret:
Proposition Let X be finite, e 10 and 3, 2 2lgg(2N Running GP-00 with Bn for a sample I from GP with mean function zero and covariance function k(Tr, x) the following regret bound holds with
7

---

Published in Transactions on Machine Learning Research (09/2023)
probability 1
RN S 31/2
Σ Alog
where 8 = mar.8....,,B and (nn) denotes the diameter of a cell evaluated at depth n.
A full proof is provided in the Supplements. The high-level idea is that either the explored cell X, contains the optimum x², then the simple regret [f(*)) - f(x) is trivially upper bounded by the maximal deviation ((,)) Or the cell does not contain the optimuu, but then then its utility was higher than the one of a node containing the optimum in its region, and thereby higher than the optimum itself. For the cumulative regret we assume the worst-case of a uniformly growing tree. For a broad class of kernels, the bound in Proposition 1 can be further specified:
Proposition Assume the GP's cononical pseudo-metre mettric d satisfies d(x, = C| vll.. where C' 0 O, 0,m/a 1. Running GP-O0 a finâte domain X' C [0, 11 with regular partitions, has worst-case cumulative regret RN of
Ó(N-~a/m (log N)a/m)
with high probability The Ō(:) notation supresses poly-logarithmic factors. In particular, for the squared exponential kernel and Matérn kernels with half- salf-integer values v 2 3/2, one has a = 1 and R Ó(N1-1/" (log (log l/m) For comparison, the regret in GP-UCB grows as Ö(v log(NN) for the squared exponential kernels and thereby scales better to higher dimensions. For the Matérn class, GP-UCB is guaranteed to have regret at most Ö(N 20+m(++1) ) for 2 1. Our bound is lighter, e.g., for the values y= = 3/2 or v = 5/2 often used in practice.
Shekhar Javidi (2018) establish regret bounds terms of the ncar-optimality dimension m. This measure is commonly used in optimistic optimization to characterize the size of the set of e-optimal points in terms of packing numbers. The near-optimality dimension does not only depend on the underlying metric, but also on the function f itself and is thereby random variable. Smaller values are associated with deeper growing trees, whereas larger values lead to more balanced, uniformly growing trees. Assuming the worst case of v = m, the bounds in Shekhar & Javidi (2018) become ((N1-a/m) for the Matérn class and match our worst-case bound. However, we restricted the analysis to finite domains X, and |X| enters our bound logarithmically.
Grill et al. (2018) showed that in the specific of Brownian motion, the tree built during optimistic optimization does not grow with the worst-case uniform rate.
6 Experiments
We empirically compare GP-OO to GP-UCB, EI, TurBO and DiRect in terms of regret and time, on synthetic, 3d samples from GPs, and Benchmark functions from Surjanovic & Bingham (2022). All ex- periments were performed ysis, we also report wall-clock runtimes. For GP-UCB and EI, we use implementations from Emukit (Paleyes et al., 2019; Gardner et al., 2018). For TurBO, we build upon the published code accesible at attps://github
desktop machine. Since computational efficiency is central to our anal-
However, we turn off the optimization of the lengthscale an noise scale and instead provide it with ground-trute values, for a fair comparison with the other methods that also have this information. Also, we changed TurBO's default batch size from 10 to make it the same GP-OOs. Other than that, we its default settings. For DiRect, use the python implementation available at https: https//ww......ooooee//////////a
6.1 Experiments on synthetic functions
Regular partitions. We begin with on-model experiments for common setting in Bayesian optimization, where GP-OO showcase its speed advantages: 20 samples from GP with squared exponential kernel
8

---

Published in Transactions on Machine Learning Research (09/2023)
(lengthscale = 0.2) the unit cube X' [0, For all experiments, the noise level for GP-UCB is set to a very small constant À = 0.0005 since assume noiseless observations. For GP-OO, we use 3n = 2 log 2 l/e) with a discretization of 1/1 points along each dimension. For additional heuristical choices B as well as constant choices of An E {0.1, 1, 10, 100), see Appendix. For GP-UCB, we use 3n = log(2 2 2 //e)) according to theory with grid search over the size of the discretization (.8] with values {1, 10, 100, 1000), as well constant values / in {1, 10, 100, 1000). For EI, we did grid search over the jitter parameter with values in {0.0001, 0.001, 0.01, 1). GP-OO and GP-UCB require the specification of confidence level that is set to 0.05 for both methods. Figure shows the simple regret min,"" and the average cumulative regret Rn/n in terms of number of function evaluations n. Figure 4 displays the runtime of GP-UCB, GP-OO and TurBO. In terms of number of function evaluations there is no improvement over the state-of-the art, however in terms of runtime GP-OO orders of magnitude faster than classical BO approaches and also improves over TurBO's runtime. In terms sample-eficiency, GP-OO improved over DiRect. This indicates that GP-0O can exploit the smoothness encoded in the prior. For a more dctailed comparison of DiRect and GP-OO, also Appendix A.3.
square exponential 0.2
GP-00
TurBO
El
GP-UCB
log mitl F'n
log Ra nn
Direct
random
-6
100
200
300
400
500
100
200
300
400
500
number of function evaluations n
Figure 3:
Best simple regret (left) and average cumulative regret (right) on synthetic functions sampled from
a GP.
2.0
overhead
0.010
GP-O0
TurBO
time in seconds
aoquisition
0.008
1.5
GP updating
0.006
0.004
0.5
0.002
0.000
0.0
200
400
600
800
1000
200
400
600
800
1000
iteration
iteration
Figure 4: Runtime per itcration [soconds] for on-model optimization of GP-samples. Left: Time for different components of GP-UCB iterations. Right: Total time per iteration (averaged batch size) for GP-00 and TurBO.
Non-regular partitions. For demonstration, we also explore setting with non-regular optimal partitions, where GP-OO can not perform as well. We sample 100 functions from a GP with quadratic kernel k(æ, y) (xTy)² with bias on the domain [-1, 1jS. We consider GP-UCB and GP-OO, once with euclidean partitions and once with partitions optimized with respect to the canonical metric. The exploration constant was set 3 = The results shown (Figure 5) show that is advantagcous optimize the partitioning schome with respect to the canonical metric. However, we restrict ourselves to partitions with axis-aligned cells, f.e. the perfectly correlated corner points with k(,,, y) 1 and d(x, y) end up in differrnt. cells. At this

---

Published in Transactions on Machine Learning Research (09/2023)
point, GP-UCB has clear advantage, as information can be shared across the search space between the corner points. Also, the run-time advantage decreases due to the numerical optimization of the partitions.
4
GP-UCB
0.05
overbead
GP-00 (canonical)
evaluation
3
GP-O0 (euclidesa)
0.01
acquisition
min regret
GP updating
2
0.03
0.02
0.01
0.00
0
10
20
30
40
50
10
20
30
40
50
iteration
iteration
Figure 5: Experiment with a quadratic kernel. Right: Wall-clock time with GP-UCB. Green line: Wall-clock
time with GP-00.
6.2 Experiments on benchmarks
We consider the minimization of common optimization benchmark functions, on domains with dimensions ranging from to 10. Since the functions are deterministic, and GP-OO is deterministic up to random tie breaks, we randomly sample 10 domains to obtain variation (see Supplements). Since evaluations of the benchmark functions are very cheap, we artifically simulated higher function evaluation costs by adding post-hoc costs from 0.001 to Second the evaluation times. We use a Matérn kernel with and length-scales recommended by Rando et al. (2022), who obtained them with grid search. For the exploration constant 3 we did grid search grid search for the jitter parameter with values as above. We use confidence level = 0.05. Figure 9 shows the minimal simple regret over the number of iterations and Figure 7 shows the minimal simple regret over time. The Supplements contain additional figures for function evaluation costs of 0.01 and 0.1 Seconds, as well as a figure showing cumulative run-times.
3/2
{0.1, 1, 10, 100} for GP-UCB and GP-OO. For EI, we did a
GP-OO competitve with the BO basod approaches on of the 12 benchmarks (Dixon-Price, Bohachevsky A, B and C, Ackely, Hartmann and Shekel. This even holds in number of function evaluations and not only wall-clock time. However, do not find consistent advantage outperformed by Direct. Since the benchmark functions are typically not within the RKHS, it cannnot be guranteed that GP-OO converges to the global optima. In particular on Rosenbrock and Beale, it happened that GP-OO got stuck in very bad local optimal. For DiRect this happend less, indicating that it was harmful to rely on the smoothness assumptions, when they are not fully met. TurBO is also less prone to get stuck local optima as has an in built critcrion for random restarts of trust regions once they converged to (local) optimum.
DiRect and in some cases GP-OO is
7 Conclusion
BO and O0 are closely connected through a mapping from the kernel-function to the canonical pscudo- metric. We showed that, for some kernels, this connection can be exploited derive a computationally efficient method for the BO setting that captures prior information. For common choices of kernels, like the Matérn class, outperform classical BО approaches, like GP-UCB and E1, if the objective function has low evaluation cost. In many cases, this simple approach achieves performance similar to scalable BO approaches highly optimized for runtime. On the other hand, the strong reliance on the prior assumptions without being able to adapt the hyperparameters of the prior on the fly, is currently still a limitation in practical scttings. setting, where one quickly wants find the maximum of synthetic GP sample, might already be interesting application cases of GP-OO: Grill et al. (2018) suggest to use Optimistic Optimization subroutine for Thompson sampling. Instead of sampling the function values from the posterior
10

---

Published in Transactions on Machine Learning Research (09/2023)
entire grid and then taking its maximum, one optimistic optimization and only samples the function values at the evaluation locations found with optimistic optimization. In this setting, the hyperparameters of the posterior are known. The same goes for BO algorithms like Maximum Entropy Search or Maximum Value Entropy Search, where, one has to generate distributions of the (location of the) maximum from 'on- model "samples from the posterior. Nonetheless, our work shows that the ability to use prior information in Bayesian optimization does not have to be expensive per se. Of particular conceptual importance the insight that optimization can be performed without explicitly tracking posterior.
Acknowledgments
This work was supported by Microsoft Research through its PhD Scholarship Programme, The authors thank the International Max Planck Rescarch School for Intelligent Systems (IMPRS-IS) for supporting Julia Grosse by non-financial means. Philipp Hennig and Julia Grosse gratefully acknowledge financial support by the European Research Council through ERC StG Action 757275 / PANAMA; the DFG Cluster of Excellence "Machine Learning- New Perspectives for Science", EXC 2064/1, project number 390727645; the German Federal Ministry of Education and Research (BMBF) through the Tübingen AI Center (FKZ: 011818039A); and funds from the Ministry of Science, Research and Arts of the State of Baden- Baden-Württenne Württemberg.
11

---

Published in Transactions on Machine Learning Research (09/2023)
Six-Hump Camel (dimension: 2)
Dixon-Price (dimension: 10)
Branin (din
E1
12.5
GP-UCB
2.5
TurBO
0.0
10.0
Direct
random
-25
GP-O0
5.0
5.0
2.5
-5
-7.
0.0
-10
12.5
-5.0
10
10a
10'
10
10
10a
Beale (dimension: 2)
Bohachevsky A (dimension: 2)
Bohachevsky (dimension: 2)
10
10
10
0
-5
-5
log of minimal simple regret
-10
-10
-15
-15
-15
10
10a
10
10a
10
10a
Bohachevsky C (dimension: 2)
Rosenbrock (dimension: 2)
Ackley (dimension: 2)
10
2.5
5
0.0
0
2.5
5.0
-5
10.0
10
-10
12.5
15
10a
10a
10a
10'
10ah
Hartmann (dimension: 3)
Trid (dimension: 4)
Shekel (dimension: 4)
2.5
-2.5
2.5
5.0
7.5
-5
-7. 7.5
10.0
10.0
-10
12.5
12.5
10a
103
10a
10a
10a
10a
number of function evaluations
Figure 6: Optimization performance (minimal function values found) in terms of number of iterations on common benchmarks with GP-OO, GO-UCB, EI, TurBO, DiRect, and random selection of evaluations 12

---

Published in Transactions on Machine Learning Research (09/2023)
Six- Hump Camel (dimension: 2)
Dixon-Price (dimension: 10)
Branin (dime
ucb
turbo
10.0
direct
7.5
random
2.5
gpoo
55.0
2.5
-5
-7.5
0.0
10.0
-10
12.5
-5.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
2.5
5.0
7.5
Beale (dimension: 2)
Bohachevsky A (dimension: 2)
Bohachevsky (dimension: 2)
10
10
-5
log of minimal simple regret
-10-
-00
-15
-5
2.5
5.0
7.5
2.5
5.0
7.5
5.0
7.5
Bohachevsky
(dimension: 2)
Rosenbrock (dimension: 2)
Ackley (dimension: 2)
10
2.5
0.0
0
2.5
5.0
-5
10.0
10
-10
12.5
15
5.0
Hartmann (dimension: 3)
Trid (dimension: 4)
Shekel (dimension: 4)
2.5
2.5
2.5
550
7.5
-5
- 7.5
10.0
10.0
-10
12.5
12.5
5.0
7.5
5.0
7.5
log time in seconds
Figure 7: Optimization performance (minimal function values found) in terms of wall clock time for simulated function evalution times of 1 Sccond on common benchmarks with GP-OO, GO-UCB, EI, TurBO, DiRect and random selection of evaluations.
13

---

Published in Transactions on Machine Learning Research (09/2023)
References
Sander Borst, Daniel Dadush, Neil Olver, and Makrand Sinha. Majorizing measures for the optimizer. ar. preprint 2r 18306, 2020.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed Bandits. Journal of Machine Learning Research, 12(5), 2011.
Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. Monte-Carlo tree search: A new framework for game ai. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 4, pp. 216 217, 2008.
Emile Contal, Cédric Malherbe, and Nicolas Vayatis. Optimization for Gaussian processes via chaining. arXiv preprinl or (rXic:510.005570 2015.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. Advances in neural information processing systems, 32, 2019.
Peter I Frazier. A tutorial on Bayesian optimization. arXiv preprint arXiv:1807.02811 2018
Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian Q Weinberger, and Andrew Gordon Wilson. GPy- Torch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration. Advances in Neural Information Processing Systems (NeurIPS), 2018:7576-7586, 2018.
Teofilo F Gonzalez, Clustering minimize the maximum intercluster distance. Theoretical computer science, 38:293-33 1985.
Jean-Bastien Grill, Michal Valko, and Rémi Munos. Optimistic optimization of a Brownian. Advances in Newral Information Processing Systems, 31, 2018.
Julía Grosse, Cheng Zhang, and Philipp Hennig. Probabilistic DAG search. In Uncertainly in Artificial Intelligence, pp. 1424 1433. PMLR, 2021.
Sunil Gupta, Santu Rana, Svetha Venkatesh, et al. Bayesian Optimistic Optimisation with Exponentially Decaying Regret. In International Conference on Machine Learning, pp. 10390 10400. PMLR, 2021.
Eric Han, Ishank Arora, and Jonathan Scarlett. High-dimensional Bayesian optimization via troe-structured additive models. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 7630- 7638, 2021.
Philipp Hennig and Christian J Schuler. Entropy Search for Tnformmttion-Fffiieen Global Optimization. Journal of Machine Learning Research, 13(6), 2012.
Felix Jimenez and Matthias Katzfuss. Scalable Bayesian optimization using Vecchia approximations of Gaussian processes. arXiv preprint arXio:2208.01459, 2022.
Donald R Jones and Joaquim RRA Martins. The direct algorithm: 25 years later. Journal of Global Optimization, 79(3):521-56) 16-56,211666111 2021.
Donald R Jones, Cary D Perttunen, and Bruce E Stuckman. Lipschitzian optimization without the lipschitz constant. Journal of optimization Theory and Applications, 79:157-184 1993.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits metric spaces. In Proceedings of the fortieth annual ACM sympostum on Theory of computing, pp. 681 690, 2008.
Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization techniques IFIP technical conference, pp. 400 404. Springer, 1975.
Rémi Munos. Optimistic optimization of a deterministic function without the knowledge of its smoothness. Advances in neuraa information processing systems, 24:783-799 -991, 2011.
14

---

Published in Transactions on Machine Learning Research (09/2023)
Mojmir Mutny and Andreas Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature fourier features. Advances in Newral Information Processing Systems, 31, 2018.
Andrei Paleyes, Mark Pullin, Maren Mahsereci, Neil Lawrence, and Javier González. Emulat ion of physical processes with emukit. In Second Workshop on Machine Learning and the Physical Sciences, NeurIPS, 2019.
Gilles Pisier. The volume of convez bodies and Banach space geometry, volume 94. Cambridge University Press, 1999.
Marco Rando, Luigi Carratino, Silvia Villa, and Lorenzo Rosasco. Ada-BKB: Scalable Gaussian Process Optimization on Contimuous Domains by Adaptive Discretization. In International Conference on Artéficial Intelligence and Statistics, pp. 7320-7348 PMLR, 2022.
Sudeep Salgia, Saltar Vakili, and Qing Zhao. Domain- Shhnaiinhrriniing based Bayesian Optimization Algorithm with Order-Optimal Regret Performance. In Thirty-Fiih Fifth. Conference on Neural Information Processing Systems, 2021.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan Adams, and Nando De Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148 175, 2015.
Shubhanshu Shekhar and Tara Javidi. Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics, 12(2):3829-387) 3874, 2018.
Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable Bayesian optimization using deep neural networks. In International conference on machine learning, pp. 2171-2180. PMLR, 2015.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint ar orXiv:0912.3905, 2009.
S. Surjanovic and D. Bingham. Virtual library of simulation experiments: Test functions and datasets. Retrieved May 16, 2022, from http: //ww: wwwpwwwwww...........www...p.... ca/-ssurjano, 2022.
Michel Talagrand. Majorizing measures: the generic chaining. The Annals of Probability, 2443):004 1996.
Michel Talagrand. Empirical processes, ii In Upper and Lower Bounds for Stochastic Processes, pp. 433 456. Springer, 2021.
Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultaneous optimistic optimization. In International Conference on Machine Learning, pp. 19 19-27. PMLR, 2013.
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian oniiaization. In International Conference on Machine Learning, pp. 3627-3635, PMLR, 2017.
Ziyu Wang, Babak Shakibi, Lin Jin, and Nando Freitas. Bayesian multi-scale optimistic optimization. Artificial Intelligence and Statisties, pp. 1015-1014. PMLR, 2014.
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian optimization in billion dimensions via random emboddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
15

---

Published in Transactions on Machine Learning Research (09/2023)
A Appendix
A.1
Theoretical Analysis
A.1.1 Background
The following three facts will be used during the analysis:
Deviation inequality For a sample g(0, k) from a centered GP with kernel function k holds
(- u1
Vu,F(11(z) f(v)) u) S 2exp
(-2d(r, y)²
(10)
where d(z, v) / (k22, k(y, v) 2k(2, v).
Hölder's incquality Let a,,... aN, b1, "h......, by be real numbers.
N
N Σ n=1
1/4
Janbal S
Σ n=1
Elanl")
by
(11)
with p.g and
3. Growth of Harmonic numbers The N-th Harmonic number HN >> in N:
2x=1 grows logarithmically
Hv Ollog N)
(12)
A.1.2 Upper bounds on the supremum of a cell
Lemma 1. Assume X' is finite and ~ GO k). Pick C (0,1) and set An
Then
Vn sup xe
ffx)) f(x,)) s 82/2 A(X,)
holds with probability 2 1 e. X, the cell visited al step n with center on and A(X,) supsex, d(x, xn).
Proof of Lemma 1. Fix n. Applying union bound and 10, one obtains for all Un
P(supsex, If(x) f(x,)) 2 un)
(13)
Σ P((((z) f(xn)) 2 un)
(14)
#EX,
un 2d 2d( (r, Fn )
<
exp
(15)
zEX
u 2A(Xx)) )2
< 2//K2 exp
(16)
For un 31/2A(X,)) it holds with probability 1- e/N, that supzex, [fxx) f(,n)) 2,11/220 A(x). Taking another union bound over N the statement holds.
A.1.3 Upper bound on the regret
Lemma 2. Running GP-OO with 8n as specified in Lemma and the canonical pscudo-metric d, the simple regret r, f - fn is bounded by al/2 A(X)) for all a with probability -
Proof of Lemma 2. This statement can be shown with typical arguments from the literature on optimistic optimization. We consider the cases x* E Xr and x" X, separately.
16

---

Published in Transactions on Machine Learning Research (09/2023)
Case 1: x² E Xn
In = f---- (f f(xx)1 (
(17)
by Lemma 1.
Case 2: x² Rn
Because In was explored nevertheless, there node Ix on the optimal path with I' E Rn that was explored at step n' n, such that
f(x,)) + 11/2A((1) 2 f(z,)) 3 (xx)))
(18)
Then, f(x.)) ((an))_f(a (xx,) 1 3 A(Xx)) For the regret obtains in combination with Lemma 1:
In = f fn $ [f(2²) f(xw)) + [f(xww - f(zn) -3/ 3//22 ( 3/ ((X))
(19)
(20)
$ A(X)) + 1////
(21)
(22)
Proposition Assume X is finite and f GP(O,, k).. Pick E (0, 1) and set B, (1/ For GP-OO with k ==2 children nodes, we obtain the following bound the cumulative regret
P(RN S B1/2
Σ A(llon])) 2
(23)
where (h) is the radius of a cell at depth h and 3 = m BN}.
Proof Proposition 1. Simple consequence from Lemma 2, where we assume the worst case a unformmy growing tree. The depth of node after n steps at least [log(n)] a uniformly growing tree.
A.1.4 Bounds for common kernels
The following analysis is restricted to GP's, where the canonical pscudo-metric d satisfics:
There exist C > 0, > such that d(x, y) S C||ar yllg, where || lll is the Euclidean norm. We additionally require m/a > 1, where m is the dimension of the domain.
Assumption 1.
According to Shekhar & Javidi (2018) the first part of Assumption 1 holds for the squared exponential kernel with C = 22/1, and the Matern kernels with half integer values. For 1/2, one has 1/2 and for all other half-integer values a =
Lemma 3. [Bubeck et al. (2011)) Assume that X' a m-dimensional hypercube [o. 1] and consider the dissimilarity d(z, v) = Cl| - y where C > 0, a > Define the partitioning by recursively splitting the hypercube in the middle along longest side (ties broken arbitrarily). One has
A(X.) S diam(())) S C(2
2a/m
for the cell Xr node depth
Proof of Lemma 3. See Example in Bubeck et al. (2011).
Proposition 2 Assume the GP's comonical pseudo-metric d satisfies d(zr, v) = -11æ-~v188 where C 0, 0, 0, 0.m/a 1. Running GP-OO on a finite domain X' c [0, 11 with regular partitions, one has worst-case cumulative regret Ry of
Ö(N1-a//m) (lo.://moooNNooo N)amm))
17

---

Published in Transactions on Machine Learning Research (09/2023)
with high probability. The Ó-) notation supresses goly-logarithmic factors.
Proof of Proposition 2 It follows from Proposition 1 that Rx E Ó A(Llogn)) with probability
1-6. It remains to bound Ex=1 A[Llogn]) For Equation (24), Lemma 3 and for Equation (29), we apply Hölder's inequality (11) with q m/a and p T-a/m
[logn
A[llgn]]) s C(2vm)
(24)
2a
N
log n-
$ C(2
(25)
2a/mm
NV
log
= -m(2mm) 22a/m
Σ
(26)
2a/m
n=
NV
log
Ci
(27)
20/m
n=1
C2
(28)
120mm
1-a/m m
1
m/a
a/m
I C1
(29)
na/m
=GN1-a/m H
(30)
where C1 = C(22mm)22//// and Hy being the N-th harmonic number. Together with (12), this implics:
A(llog|)) E O(N2-a/m (log N)a/m)
(31)
A.2 Additional experimental details
The experiments were implemented in Python 3.9.1. and run on a machine with macOS 12.3.1, a GHz Quad-Core Tntel Core i7 CPU and 32 GB RAM or on a machine with macOS 12.2.1, a 2,7 GHz Dual-Core Intel Core i5 CPU and 16 GB RAM in the case of the Experiment in Section 6.1.
A.2.1 Experiment with benchmark functions
Table lists the domains and hyperparameters used the experiment with the benchmark functions. We ran TurBO in its default configuration with trust regions and a batch size of 10. For each run, we sampled sub-domain by choosing uniformly at random new lower and upper boundaries for the intervals along each dimension, such that the new boundaries inbetween the previous ones and the location of the minimum. In this way, the location of the minimum stays the same as in the original domain.
Figure 9 shows the minimal function value found for the benchmark functions and Figure 10 the cumulative runtime. While in terms of number of function evaluations GP-OO does not improve over existing methods, it is the fastest.
18

---

Published in Transactions on Machine Learning Research (09/2023)
Six- Six-uump Camel (dimension: 2)
Dixon-Price (dimension: 10)
Branin (dime
12.5
ucb
turbo
10.0
direct
7.5
random
2.5
gpoo
-5.0
2.5
-5
-7.
0.0
-10
12.5
5.0
2.5
0.0
2.5
5.0
22.5
2.5
5.0
7.5
2.5
0.0
2.5
5.0
Beale (dimension: 2)
Bohachevsky (dimension: 2)
Bohachevsky (dimension: 2)
10
10
5
-5
-5
-5
log of minimal simple regret
-10
10
10
-15
15
-2.5
2.5
5.0
-2.5
0.0
22.5
0.0
5.0
Bohachevsky C (dimension: 2)
Rosenbrock (dimension: 2)
Ackley (dimension: 2)
0.0
2.5
5.0
-5
-5
10.0
-10
100
12.5
Hartmann (dimension: 3)
Trid (dimension: 1)
Shekel (dimension: 4)
2.5
2.5
2.5
5.0
7.5
-5
7.5
10.0
10.0
-10
12.5
12.5
2.5
2.5
2..5
5.0
log time in seconds
Figure 8: Minimal function values found on common benchmark datasetsfor simulated function evaluation costs of 0.1 Second.
19

---

Published in Transactions on Machine Learning Research (09/2023)
Six- Hixp Camel (dimension: 2)
Dixon-Price (dimension: 10)
Branin (dime
e1
12.5
ucb
turbo
10.0
direct
7.5
random
2.5
gpoo
55.0
2.5
-5
-7.3
0.0
10.00
-10
12.3
-5.0
5.0
2.5
0.0
2.5
5.0
5.0
2.5
0.0
2.5
5.0
Beale (dimension: 2)
Bohachevsky A (dimension: 2)
Bohachevsky (dimension: 2)
10
10
-5
-5
log of minimal simple regret
-10-
-10
-10
-15
155
-2.5
0.0
5.0
-2.5
0.0
5.0
-2.5
0.0
5.0
Bohachevsky C (dimension: 2)
Rosenbrock (dimension: 2)
Ackley (dimension: 2)
10
0.0
2.5
5.0
-5-
-5
10.0
100
-10
12.5
-15
5.00
22.5
5.0
Hartmann (dimension: 3)
Trid (dimension: 4)
Shekel (dimension: 4)
2.5
2.5
2.5
550
7.5
-5
7.5
10.0
10.0
-10
-2255
12.5
55.0
0.0
5..0
5.0
-5.0
2.5
5.0
log time in seconds
Figure 9: Minimal function values found on common benchmark datasets for simulated function evaluation costs of 0.01 Second.
20

---

Published in Transactions on Machine Learning Research (09/2023)
Six-Hump Camel (dimension: 2)
Dixon-Price (dimension: 10)
Branin (din
TurBO
10a
10a
10a
EI
GP-UCB
101
10
DiRent
10
10a
10a
GP-00
10
10
10
10
3
10-4
2500
5000
7500
10000
2500
5000
7500
10000
0
2500
5000
7500
10000
Beale (dimension: 2)
Rohachevsky
(dimension: 2)
Rohachevsky B (dimension:
10a
10a
10a
10
10
10
10
10
10
10
10-2
10
10
10 3
time in seconds
10
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
Bohachevsky C (dimension: 2)
Rosenbrock (dimension:
Ackley (dimension: 2)
10a
10a
10a
10
10a
10a
109
10a
10
10-1
10
10-2
10
10-2
10
10
10
10-1
10
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
Har Haartman (dimension: 3)
Trid (dimension: 4)
Shekel (dimensioo:: 4)
10a
10a
10a
10a
10
10a
10
10a
1
10-
10
10
10-3
10-3
10-3
10-4
10
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
number of function evaluations
Figure 10: Cumulative runtimes for common benchmark datasets.
21

---

Published in Transactions on Machine Learning Research (09/202))
Table 1: Hyperparameters for experiment with benchmark functions
Benchmark
Domain
Lengthscale
B (GP-UCB)
3 (GP-0O)
jitter (EI)
Branin
[-15, 15]2
0.5
100
0.001
Six-Humpe Haxe-ump-aa Camel
22
0.5
10
0.0001
Beale
4.52
1
0.1
100
0.0001
Bohachevsky a
1100, 100
1.7
0.1
10
1
Bohachevsky
-100,
1.7
10
0.1
Bohachevsky
1100,
1.7
0.0001
Rosenbrock
3,,3
0.7
100
0.0001
Ackley
35,
3.5
10
0.001
Hartmann
0,1]3
0.3
0.1
0.0001
Trid
16]
10.75
100
0.0001
Shekel
10]1
1.75
10
0.001
Dixonprice
10]10
2
10
0.1
0.1
22

---

Published in Transactions on Machine Learning Research (09/2023)
square exponential
Matern
heuristic
heuristic 2
heuristic 3
log mimi ITn
0.1
10
-1
-0
200
400
600
1000
200
400
600
800
1000
number of function evaluations n
Figure 11: Performance of GP-OO for different choices of Bn 20 samples from GP.
Table 2: Estimated probability that all upper bounds in a tree with 10 levels hold for samples from a GP.
square exponential
Matérn
heuristic heuristic 2
15%
0%
83%
94%
heuristic 3 14%
7%
A.2.2 Heuristical choice of
Figure 11 shows GP-OO's performance in the experiment synthetic samples from GP described in Section 6.1 for three heuristical choices of 3, and constant values of 3n 1,, 100, 1000). We performed the same analysis for a Malérn kernel with v 3/2. According to theory, the upper bounds hold for 3n = 2 (2 Xa N/e) with probability 1-6 e, but typically a full union bound over both the size of the domain and the total number of observations is too loose. The heuristics are inspired by the observation that the number of 'effectively independent" points in the domain is 1/1 along each dimension. the following, / denotes the lenghtscale and the dimension of the search domain. C is constant. that set to for the square exponential kernel and 3/2 for the Matérn kernel.
Heuristic 1: = 1 and &, = (1/1)
Heuristic 2: N = (C/1)² and &r = (C/I)2
Heuristic 3: N = 1000 (as we run the search for total of 1000 iterations) and &r (1/l)d
In addition, we empirically estimated the probability with which our heuristical choices for result in valid upper bounds. To do so, we sampled 100 functions from GP and for each sample build a fully balanced search tree up to depth 10. For each sampled function and each node, we checked if the upper-boune holds for the corresponding cell. The following table shows the percentage of samples for which all upper-bounds from depth 0 to depth 10 did hold. All functions were sampled on 25 x 25 x 25 grid with square exponential and Matérn kernel with lengthscale 0.2. is set 0.05, so one would expect 95% of the bounds to hold under a union bound approach. For the results, see Table 2. Higher percentages indicate the 3 is too conservative and lower percentages indicate that the optimization might be too greedy. We find that, even though the latter the case for our heuristics, this does not immediatly lead decreased search performance as shown by Figure 11.
A.3 Ablation: Does encoding the smoothness help?
We compare GP-00 to DiRect (Jones et al., 1993), a global optimization algorithm that also based on iterative refinement of axis-aligned rectangles. DiRect assumes that the function fulfills Lipschitz condi-
23

---

Published in Transactions on Machine Learning Research (09/2023)
Table 3: Discretization
dimnension/lenguusaale discrctization per dimension
3/1
3/0.1 3/0.05
2/0.5
2/0.05
2/0.005
1/0.5
1/0.05
1/0.005
40
100
200
500
1000
1000
2000
tion as well, however does not allow specify it. With the following experiment we investigate whether the Lipschitz assumption encoded in the prior allows GP-OO to improve over the performance of DiRect. To do so, compare both methods on 20 samples from GP prior with Matérn kernel (Figure 12) square exponential kernel (Figure 13) in different dimensions for different lengthscales. For GP-OO we set the exploration constant 3 to according to heuristic 1 described in the previous section. The confidence parameter c is set to 0.01. The domain is [o, 1] for dimension d. The functions sampled from the GPs are sampled over grids of different discretizations as specified in Table
We find that GP-OO can exploit the smoothness the prior, particular on domains with smaller length- scales, i.e. more local optimas. DiRect is known to converge slowly in the presence of many local optima it sometimes spends large number of function evaluations refining the grid around local optimum before reaching the basin of a global opt.mnum (Jones & Martins, 2021). Knowing the snest of the function might help GP-OO to reach a better trade-off here. For large lengthscales the advantage seems to disappear or even turns around on some samples. A potential reason could be a slight misspecification of the exploration constant beta. However, for this work the settings with small lengthscales are more relevant anyway, since in settings with large lengthscale BO preferable as one does not need many evaluations there and BO than scales sufficiently well.
24

---

Published in Transactions on Machine Learning Research (09/2023)
Matern
Direct GP-OO
dim: 3, 1: 1
dim: 3, I: 0.1
dim: 3,
10
10
10
10
10
500
2000
2000
diu:: 2, I: 0.5
dia: 2, I: 0.05
dim: 2, 1: 0.005
10"
10"
10a
(log) mitl I'
10-1_
10
10-1
750
25000
75000
diu:: 1, 1: 0.5
dim: 1, 1: 0.05
dim:
1, 1: 0.005
10a
10-1
10
10-1
100
150
200
250
750
1000
number of function evaluations n
Figure 12: Performance of GP-OO and DiRect 20 samples from GP with with Matérn kernel with different lengthscales and dimensions. The regret is normalized to [0, and the y-axis is semi- logrithogait with a linear threshold at 0.1.
25

---

Published in Transactions on Machine Learning Research (09/2023)
squared exponential
Direct GP-O0
dim: 3, 1: 1
dim: 3, 1: 0.1
dim: 3,
10
10-1
0
250
500
750
1000
2000
4000
2000
4000
dim: 2, 1: 0.5
dim: 2, 0.05
dim: 2, 0.005
10a
(log) mäll I'
10
10
10
100
150
200
250
500
750
1000
25000
50000
75000
100000
dim: 1, l: 0.5
dim:
1,
0.05
dim:
1,
0.005
109
10a
10
10
10-1
10
20
40
0
150
200
250
750
1000
number of function evaluations n
Figure 13: Performance of GP-OO and DiRect on 20 samples from GP with a with square exponential kernel with different lengthscales and dimensions. The regret is normalized to [0, 1] and the y-axis semi- logarithmic with a lincar threshold at 0.1.
26


Reviews:
[{"review_id": "fw4hqdrfQr", "reviewer": "Reviewer_qus2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Pros\n\nThe strength of the work lies in 1) discovering that by using canonical pseudo-metric, one can estimate the upper bound of a cell with a GP prior, thus connecting OO and BO. 2) The author also provided theoretical analysis on the upper bound and convergence rate cumulative regret. 3) The paper is mostly clearly written (except experiments).\n\n### Cons\n\nThe biggest weakness of the work is to require knowing the ground truth GP hyerparameters, which significantly limits the impact of the work. This is also mentioned by the authors in their Conclusion “On the other hand, the strong reliance on the prior assumptions without being able to adapt the hyperparameters of the prior on the fly, is currently still a limitation in practical settings”. Without this problem solved, I can’t see how the proposed method can be useful in practice. \n\nSecond, I am not sure I understand how the authors created the plots. For example, in Figure 6 and 7, what is the budget applied to all the methods? For me it should be either all the methods are allocated with the same time or with the same number of evaluations. But in both Figure 6 and 7, the methods all end up at a different budget. Why is that? Also, the experiments on benchmarks are also synthetic functions, which is a bit weak by current evaluation standards. More importantly, without real-world examples, it is hard to advertise why the setting that the authors study, is an important one. In the end, more detail or explanation about experiment setting will be helpful.\n\nBesides TurBO, there are some relevant works on scalable gaussian processes:\n- Wang, Ke, et al. \"Exact Gaussian processes on a million data points.\" Advances in neural information processing systems 32 (2019).\n- A. G. d. G. Matthews. Scalable Gaussian process inference using variational methods. PhD thesis, University of Cambridge, 2016\n- M. K. Titsias. Variational learning of inducing variables in sparse gaussian processes. In AISTATS, pages 567–574, 2009.\n- J. Hensman, N. Fusi, and N. D. Lawrence. Gaussian processes for big data. In UAI, 2013\n\n\nMinor questions:\n- Why in Figure 4 that TurBO had a sudden drop? And why is there a spike for GP-OO around 700 iterations?\n- Figure 2: Right columns, Left columns -> Bottom, Top columns? One plot of cells is all white color?\n- The left plot in Figure 4 and right plot in Figure 5 are of black and grey colors, for me it is harder to read the plot. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presented an optimization method under the optimistic optimization (OO) framework where the key idea is to partition the search space by a binary tree. The connection to GP comes in with the usage of canonical pseudo-metric (depends on the kernel function), which is used to bound the probabilities of $P(|f(x)-f(y)|>u)$ (Section 3.1, Pisier (1999), Theorem 4.7) and further an upper bound of a cell (Section 3.2). The upper bound of a cell is used in the OO framework to select which cell to expand.\n\nThe authors provided theoretical analysis of the upper bound of the cumulative regret (Proposition 1) and convergence rate of regret (Proposition 2). Besides, experiments on synthetic functions shows the proposed method is competitive, especially in the computation time.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I appreciate the connections that the authors draw between GP prior and OO, and also the theoretical analysis. But I  think without including the estimates of the GP hyerparameters, the proposed method can be hard to apply in practice. \n\nThe experiments are all on the synthetic functions, which make it less convincing. Also the experiment detail is missing and I find it hard to follow what is going on.\n\nA whole series work of scalable Gaussian Process is not discussed in the relevant work, nor in the evaluations. ", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "B1WzhAtugW", "reviewer": "Reviewer_ZH9C", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\n- Computational efficiency of acquisition functions in BO should be a practically important topic.\n\n- The proposed algorithm is simple to implement and seemingly easy to use.\n\nWeaknesses\n\n- Kernel hyper-parameter tuning are not provided, and sensitivity to kernel hyper-parameters is not clarified. \n\n- Technical descriptions are somewhat cluttered. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a black-box optimization algorithm called GP-OO (Gaussian process optimistic optimization). The algorithm divides the search space into disjoint cells and iteratively selects a cell having the highest upper bound. The technical main contribution would be in the upper bound based search algorithm based on combining a local Lipschitz assumption and the GP assumption for the underlying objective function. The computation is quite simple based on which the authors mainly claim computational efficiency (not the sample efficiency) of the proposed algorithm. The performance is demonstrated by synthetic and well-known benchmark functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not have critical concerns. Most of comments below are not significant issues.\n\n- How the kernel hyper-parameters of all the methods were selected in the experiments? How can using the setting by Rando be justified? \n\n- Figure 2 should be explained in more detail.\n  - In the caption, Left and Right are lower and upper?\n  - Why the bottom plot of Matern 3/2 is white?\n  - What is the difference between quadratic (regular) and quadratic (canonical)?\n  - square exponential and Matern is regular or canonical? \n  - The definition of 'regular' should be explicitly clarified. (using Euclid distance?)\n\n- In the proposed framework, is it valid to use the marginal likelihood of GP to select hyper-parameters? (though of-course it requires additional computational cost). \n\n- Relation with the well-known DIRECT algorithm might be informative to discuss.\n\n- For Sec6.1 (Experiments on synthetic functions), why time vs regret plot is not shown? Similar plots to Figure 7 should be informative for synthetic data as well. \n\n- In Figure 6 and 7, why the initial values are different for different methods?\n\n- Why the timing of finishing algorithms are different for each method? (both in iterations and wall-clock time) \n\n- Although the authors repeatedly claim computational efficiency of the proposed method rather than sample efficiency, results on Figure 6 and 7 (evaluating sample efficiency and computational efficiency, respectively) are not largely different. \n\n- Showing more detailed entire Algorithm with details such as the center selection, maximum distance calculation, and the partitioning procedure can be informative. Algorithm 1 is not specific for the proposed method. I first felt a bit difficulty to grasp the whole procedure of the proposed method.\n\n- The original OO (without GP) should be a good baseline to demonstrate benefit of the proposed method.\n\nMinor:\n\n- In Abstract, readers cannot find what 'N' means in O(N log N).\n\n- In introduction, after (Salgia et al., 2021), a missing period.\n\n- In my opinion, the title for section 3 should be more about the proposed method (e.g, simply, 'Gaussian process optimistic optimization') rather than current 'Connection between Bayesian and Optimistic Optimization', because most of technical details of the proposed method are described entirely in section 3 (not only in section 3.4).\n\n- What does 'budget N' means? The maximum number of iterations? (while in introduction, it is defined as the number of observed values). ", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yvcLOu9ZHT", "reviewer": "Reviewer_U8Ye", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. The paper is well-written and the contributions are presented clearly.\n2. The proposed algorithm is mathematically motivated and theoretical analysis is done on the regret. The computational aspects of the algorithm are also thoroughly discussed.\n3. The experimental results show that the algorithm is competitive with existing work but is less computationally heavy.\n\n## Weaknesses\n1. The baselines only include ones that rely primarily on GPs; however, the related work discusses other types of algorithms that are closer in spirit to the proposed algorithm.\n2. The dimension of the objectives used in the experiments is at most 10, fairly small.\nPlease see the next field for further comments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an optimization algorithm that bridges Bayesian optimization and optimistic optimization. In optimistic optimization, a pseudo-metric is used to define a binary search tree on which a UCB-like procedure is done, which results in a computational complexity of $O(N\\log N)$. The authors propose to use a pseudo-metric based on a Gaussian process with known kernel (often used in Bayesian optimization with computational complexity $O(N^3)$), which does not increase the computational complexity. Theoretical analysis is done on the regret of the algorithm. Experiments are carried out on BO benchmarks showing that the algorithm is competitive with existing methods but has lower computational burden.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In order of importance:\n1. Include a wider range of baselines in the experiments, in particular those discussed in Section 4.1 that already mix Bayesian optimization and optimistic optimization. \n2. It would strengthen the work to show results for dimensions in the hundreds (or maybe even thousands) as the proposed algorithm's cell splitting process is affected by the dimension.", "broader_impact_concerns": "As the paper is proposing a new optimization algorithm, I don't think there are any direct ethical implications. No broader impact statement is included.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers were satisfied with the clarifications provided by the authors and vote acceptance.
Decision: Accept (poster)