Batch Bayesian optimisation via density-ratio estimation with guarantees
Authors: Rafael Oliveira
Louis C. Tiao
Fabio Ramos
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian optimization
Gaussian processes
density-ratio estimation
regret bounds
approximate Bayesian inference

Abstract: Bayesian optimisation (BO) algorithms have shown remarkable success in applications involving expensive black-box functions. Traditionally BO has been set as a sequential decision-making process which estimates the utility of query points via an acquisition function and a prior over functions, such as a Gaussian process. Recently, however, a reformulation of BO via density-ratio estimation (BORE) allowed reinterpreting the acquisition function as a probabilistic binary classifier, removing the need for an explicit prior over functions and increasing scalability. In this paper, we present a theoretical analysis of BORE's regret and an extension of the algorithm with improved uncertainty estimates. We also show that BORE can be naturally extended to a batch optimisation setting by recasting the problem as approximate Bayesian inference. The resulting algorithms come equipped with theoretical performance guarantees and are assessed against other batch and sequential BO baselines in a series of experiments.

Batch Bayesian optimisation via density-ratio estimation with guarantees
Rafael Oliveira 122- rafael. oliveira@sydneey edu. au
Louis C. Tiao
louis tiao@sydney edu au
Fabio Ramos 3,1
f f ramos@sydney edu. au
Brain and Mind Centre, the University Sydney, Australia 2 ARRC Training Centre Data Analytics for Resources and Environments, Australia Schooo of Computer Science, the University of Sydney, Australia ANVIDIA, USA
Abstract
Bayesian optimisation (BO) algorithms have shown remarkable success in ap- plications involving expensive black-box functions. Traditionally BO has been set as a sequential cerision-making process which estimates the utility of query points via an acquisition function and a prior over functions. such as Gaussian process. Recently, however, a reformulation of BO via density-ratio estimation probabilistic binary
(BORE) allowed reinterpreting the acquisition function classifier, removing the need for an explicit prior over functions and increasing scalability. this paper, we present theoretical analysis of BORE's regret and an extension of the algorithm with improved uncertainty estimates. We also show BORE can be naturally extended a batch optimisation setting by recasting the problem as approximate Bayesian inference. The resulting algorithms come equipped with theoretical performance guarantees and are assessed against other batch and sequential BO baselines in a series of experiments.
Introduction
Bayesian optimisation (BO) algorithms provide flexible black-box optimisers for problems involving functions which are noisy or expensive evaluate [1]. Typical BO approaches place a probabilistic model over the objective function which is updated with every new observation in a sequential decision-making process. Most methods based on Gaussian process (GP) surrogates [2], which provide closed-fomn analytic expressions for the model's posterior distribution and allow for number of theoretical performance guarantees [3-5]. However, GP surrogates have number of limitations, such as not easily scaling to fiigh-dimessioall domains, high computational complexity and requiring a careful choice of covariance function and hyper-parameters [2]. Non-GP-based BO methods have also been proposed in the literature, such as BO methods based neural networks [6, 7] and random forests [8] regression models.
As an alternative to improving the model, Tiao et al. [9] focus on the acquisition function, which in BO frameworks represents the guide that takes the model predictions into account. They show that one can derive the acquisition function directly without an implicit model by reinterpreting
"Coresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the expected improvement [4, I] via a density-ratie estimation problem. Applying this perspective, the acquisition function can then be derived as classification model, which can be represented by flexible parametric models, such as deep neural networks, and efficiently trained via stochastic gradient descent. The resulting method, called Bayesian optimisation via density-rant ratiooo estimation (BORE) is then shown to outperform variety of traditional GP-based and non-Gi GP-GPP baselines.
Despite the significant performance gains, BORE has only been applied to a sequential setting and not much is known about the method's s theoretical guarantees. Batch BO methods have the potential to speed up optimisation in settings where multiple queries to the objective function can be evaluated simultaneously [10-13]. Given its flexibility to apply models which can scale to large datasets, it is therefore a natural question as whether BORE can be readily extended to the batch setting in computationally efficient way.
In this paper, we extend the BORE framework to the batch setting and analyse its theoretical performance. To derive theoretical guarantees, we first show that the original BORE can be improved by accounting for uncertainty in the classifier's predictions. We then propose a novel method, called BORE++, which uses an upper confidence bound over the classifier's predictions as its acquisition function. The method comes equipped with guarantees in the probabilistic least-squares setting. We provide extensions for both BORE and BORE+ to the batch setting. Lastly, we present experimental results demonstrating the performance of the proposed algorithms in practical optimisation problems.
2 Background
We consider global optimisation problem over a compact search space X' C Rd of the form:
x E argmin f(x),
xEX'
where X + R is assumed to be a black-box objective function, i.e., we have no access to gradients nor analytic formulations of it. In addition, we are only allowed to run up to T rounds of function evaluations, where we might collect single points or batches of observations y: fxx)) + er, which are corrupted by additive noise e,, for t E (l....,TT TT..
2.1 Bayesian optimisation
Bayesian optimisation (BO) algorithms approach the problem in Equation via sequential decision making [1]. At each iteration, BO selects a query point by maximising an acquisition function a:
X) argmaa (x XEX
(2)
The acquisition function encodes information provided by the observations collected so far D; := (x,, yi | using probabilistic model over f. typically Gaussian process (GP) [2], conditioned on the data. After collecting an observation Vr, the dataset is updated with the new query -oerr-ooseevvation pair D. = D U Xx, ye. This process then repeats for a given number of iterations T".
2.2 Bayesian optimisation via density-ratio estimation (BORE)
The expected improvement (EI) [4, 14] is a popular acquisition function in the BO literature and the basis for many BO algorithms. At each iteration 1, one can define = minjet Bt as incumbent target. El is then defined as:
(x](x|/,,ee == E/max (0. fxx) [De-1].
(3)
In the case a GP prior on f(P ~ GP( 11), the EI is available in closed form as a function of the GP posterior. However, the El may be reformulated without the need for a prior.
Under mild assumptions, Bergstra et [15] showed that the EI can be formulated as a density ratio between two probability distributions. Let f(x) := p(xly < T) represent the probability density over x E X conditioned on the observation y being below threshold E R. Conversely, let g(x) := p(xly > r). For [0, 1]. the 7-relative density ratio between these two densities is:
((x)
(x(x)= = 7E(x) + (1 (1-7))(xx x X,
(4)

---

Algorithm 1: BORE
for f (1...., ,T do
2
T == (7-1(7)
Fi == Tly ST] iE
Di-1 = (xi, zi} 1-1
t argmin, [D 1-1
X₁ E argmax XEX xx)
Yt f(x,) + c
end
noting that 7 = 0 leads to the ordinary probability density ratio definition, po(x) (x))/(()) Now we choose := Φ ())), where (ss) := ply S s) represents the cumulative distribution function of the marginal distribution of observations, for s RR and then replace T in Equation 3, Bergstra et al. [15] have shown that? (x) (x),. for X. Based this fact, Tiao et al. [9] showed:
(x) P.y (xx), E
(5)
where (x) := ply I T(x) can be approximated by probabilistic classifier trained with a proper scoring rule, such the binary cross-entropy loss:
Σ
log ग (x,) (x + (1 2;) log(1 (xx)).
(6)
Other examples of proper scoring rules include the least-squares loss, which leads to probabilistic
least-squares classifiers [16], and the zero-one loss. We refer the reader to Gneiting and Raftery [17] for a review and theoretical analysis on this topic.
BORE is summarised in Algorithm 1. As seen, the marginal observations distribution CDF (s)) == pvy S 8) is replaced by the empirical approximation .,(s) == ! Σ U[ S s) and its corresponding quantile function $-1 At each iteration, observations are labelled according to the estimated yth quantile т, and a classifier मं is trained by minimising the loss L[ [[r[D.] over the data points D.. A query point x, is chosen by maximising the classifier's probabilities, which in our case corresponds to maximising the expected improvement. A new observation is collected, and the algorithm continues running up to a given number of iterations T. As demonstrated, no explicit probabilistic model for is needed, only classifier, which can be efficiently trained via, e.g.. stochastic gradient descent.
3 Analysis of the BORE framework
In this section, we analyse limitations of the BORE framework modelling uncertainty and analyse its effects on the algorithm's 's performance. As presented in Section 2.2, at each iteration 2 1, the original BORE framework trains probabilistic classifier मं (x) to approximate ply T(x), where denotes the yth quantile of the marginal observations distribution, i.c., p(y S 7) y. This approach leads to a maximum likelihood estimate for the classifier â. which may not properly account for the uncertainty in the classifier's approximation.
Since BORE is based probabilistic classifiers, instead of regression models as in traditional BO frameworks [1], a natural first question to ask is whether a classifier can guide it to the global optimum of the objective function. The following lemma answers this question and is basis for our analysis.
Lemma 1. Let f X - R be a continuous function over compact space X. Assume that, for any x E X, we observe y = fxx) + C, where c i.i.d. noise with strictly monotonic cumulative distribution function & IR + [0. 1). Then, for any E R, we have:
argmax p(y 5 T(xx argmin f(x). XEX
xEX
NNoe that p(y S 8) = ply S 8 < dx, where we may assume p(x) uniform.
Bergsttaa et al. [15] and Tiao et al. [9] also rely the mild assumption that p(x y) = f(x) for all S

---

Proof. As the observation noise CDF is monotonic, by basic properties of the argmax, we have:
argmax ply <r|x, argmax (T(TT [(x)) argmin f(x),
(8)
XEx
xEX
xE
which concludes the proof.
According to this lemma, maximising class probabilities is equivalent optimising the objective function when the classifier is optimal, i.c.. it has perfect knowledge of f. This result holds for any given threshold E TR. We only make a mild assumption on the CDF of the observation noise t which is satisfied for any probability distribution with support covering the real line (e.g. Gaussian, Student-T, Cauchy, etc.).*
To analyse BORE's optimisation performance, we will aim to bound the algorithm's 's instant regret:
Tt f(x)) f(x",, 1,
and its cumulative version Ry = - Fr. Sub-linear bounds on Ry lead no-regret algorithm, R and minegT Tt R..
since lim T
Assuming that there is an optimal classifier "' : X - (0. 1]. which is such that x= "x(x) = ply s 7|x, f), for given T I. we can directly relate the classifier probabilities the objective function f values, since:
" (x(x) = p(U S 7/x, = + - f(x))
f(x) T -
(x)())
(10)
The existence of the inverse 2- 1 is ensured by the strict monotonicity assumption on &. in Lemma 1. Under this observation, the algorithm's regret at any iteration classifier probabilities:
1 can be bounded in terms of
Tt = f(x)) - f(x') = 26 2-' (x' - --- 2 (xx)) S LL(TT -xx)))))
(11)
where L. is any Lipschitz constant for Φ- which exists since X' compact. Therefore, we should be able to bound BORE's regret by analysing the approximation error for ã, at each iteration t 2 1.
Although approximation guarantees for classification algorithms under i.i.d. data settings are well known [18], each observation in BORE depends on the previous ones via the acquisition function. This process is also not necessarily stationary,
that we cannot apply known results for classifiers under stationary processes [19]. In the next section, we consider a particular setting for learning a classifier which allows us bound the prediction error under BORE's data-generating process.
3.1 Probabilistic least-squares classifiers
We consider the case probabilistic least-squares (PLS) classifiers [20, 21]. In particular, we model a probabilistic classifier π X' + [0. as element of reproducing kernel Hilbert space (RKHS) H associated with a positive-definit kernel : X x X' + R.. A RKHS is a space of functions equipped with inner product (., > and norm ||-IIk == ((. +)x [22]. For the purposes of this analysis, we will also assume that k(x, x) < 1, for all X This setting allows for both linear and non-parametric models. Gaussian assumptions but we are not restricted by Gaussianity in our analysis. If the kernel & is universal, as & is injective, can also see that the RKHS assumption allows for modelling any continuous function.
the function space would lead to GP-hased PL.S classifiers [2],
For a given R, a PLS classifier is obtained by minimising the regularised squared-error loss:
ft argmin TEH
1 - (xx)) + A||= t2 1,
(12)
where À > 0 is a given regularisation factor and 2; := 1/1 < r] E {0, In the RKHS case, the solution to the problem above available in closed form [23, 16] as:
(x) (x) T (K, AI) 2,,
121,
(13)
"This result could also easily extended to distributions with bounded support as long as their CDF monotonic within However, we keep the support as IR for simplicity, and the extension is left for future work. 'This assumption always be satisfied by proper scaling.

---

E R', K. := ( E R and == ( 2t R This PLS approximation may not yield valid classifier, since it is possi- ble that (x) $ [0, 1] for some x E X. However, it allows us to place a confidence interval on the optimal classifier's prediction, as presented in the following theorem, which based on theoretical results from the online learning literature [24, 25J. Our proofs can be found in the supplement.
where (x) =
Theorem 1. Given T E IR assume π(x) := l:(T - f(x)) is such that π E H. and || I b. Let fx be a X'valued discrete-tine stochastic process predictable with respect the filtration (3 Let { be a real-valued stochastic process such that Vi : 24 T(xx) is 1-sub-
Gaussian conditionally 1. for all t 2 1. Then, for any 8 (0,1), with probability at least
1 6, we have that:
VX E X
(x(x Rx (x)) - (x)) Vt V1
(14)
where 3,(0) ;= b v 2A log I+ X K, 1/2288), with |A| denoting the determinant of matrix A.
and (x == lx(xx)) k, (x) (K, (x),,, x XEX, t2 1.
3.2 Regret analysis for BORE
We now consider BORE with PLS classifier. For this analysis, we will assume ideal setting where T is fixed, possibly corresponding to the true yth quantile of the observations distribution. However, our results hold for any choice of E R and can therefore be assumed approximately hold for a varying T which is converging to a fixed value. In this setting, the algorithm's 's choices are: given by:
X E argmax 1
(15)
xEX
where सं. is the estimator in Equation 13. we can then apply Theorem I to the classifier- regret in Equation 11 obtain regret bound. For this result, we will also need the following quantity:
EN == max Cx
log JI + 1 Krl- N21,
(16)
where the maximisation is taken over the discrete of locations {x:) C X and KN [k(x,,,x) >)), This quantity denotes the maximum information gain of Gaussian process model after N observations. We are now ready to state our theoretical result regarding BORE's regret.
Theorem 2. Under the conditions in Theorem with probability at least
ó E (0, 1), the instant regret of the BORE algorithm with a PLS classifier after T 2 1 iterations is bounded by:
rt S L LL3 + xxx))xx)),,
(17)
and the cumulative regret by:
R S LoBr(1) (VATT + +2)T+ + Σ Exm-(x))
(18)
As Theorem 2 shows, the regret of the BORE algorithm in the PLS setting is comprised of two components. The first term is related to the regret of GP-UCB algorithm [see 26, Thr. 3] and its known to grow sub-linearly for a few popular kernels, such as the squared exponential and the Matérn class [3, 27]. The second term, however, reflects the uncertainty of the algorithm around the optimum location x". If the algorithm never samples at that location, this second summation might have mostly linear growth, which will not lead to a vanishing regret. In fact, if we consider Equation 13 kernel, we see that, as soon
and RKHS with a translation-invarian collected at a location x; * x", that location will constitute the maximum of the classifier output. Then the algorithm would keep returning to that same location, missing opportunities to sample at x*.
observation
is
worth noting that Theorem reflects the regret of BORE in an idealistic setting where the algorithm uses the optimal PLS estimator in the function space H. However, if we train parametric classifier, such as a neural network, via gradient descent, the behaviour will not necessarily be the same, and the algorithm might still achieve a good performance. In the original BORE paper, for instance, a parametric classifier is trained by minimising the binary cross-entropy loss [9] and leads to successful performance in experiments. Neural network models trained via stochastic gradient
5

---

descent are known to provide approximate samples of posterior distribution [28, 29]. instead of an optimal best-fit predictor, which might make BORE behave like Thompson sampling [30] (see discussion in the appendix). Nevertheless, Theorem still shows us that BORE may get stuck into local optima, which is not ideal for BO methods. the next section, we present an extension of the BORE framework which addresses this shortcoming.
4 BORE++: improved uncertainty estimates
As discussed in the previous section, the lack of uncertainty quantification in the estimation of the classifier for the original BORE might lead to sub-optimal performance. To address this shortcoming, we present an approach for uncertainty quantification in the BORE framework which leads to improvements in performance and theoretical optimality guarantees. Our approach is based on using an upper confidence bound (UCB) on the predicted class probabilities the acquisition function for BORE. Due to its improved uncertainty estimates, we call this approach BORE++.
4.1 Class-probability upper confidence bounds
We propose replacing t, in Algorithm 1 by an upper confidence bound which is such that:
VI 1, x ="(x)= I (x), Vx E X'
(19)
which with probability greater than 1 1- 8, given
1). Therefore, (x, represents an upper quantile over the optimal class probability nt (x). BORE+ selects X, argmax (x).
To derive upper confidence bound on classifier's predictions =(x), we can take few different approaches. For a parametric model mT. a Bayesian model updating the posterior D,) leads to corresponding predictive distribution over To (x). This is the case of ensemble models [31], for M
Di= Tax (x) with 0² ~ p(O(D.). Instead of using the expected class probability, however, BORE++ uses (empirical) quantile approximation for T to ensure Equation 19 holds. Bayesian neural networks [32], random forests [33], dropout methods, etc. [34], also constitute valid approaches for predictive uncertainty estimation. An alternative approach is to place a non non--onnnmaen paraamemtttic prior over x², such as a Gaussian process model [2], which allows for the modelling of uncertainty directly in the function space where "² lies. In the next section, we present a concrete derivation of BORE++ for the PLS classifier setting which takes the non-parametric perspective and allows us derive theoretical performance guarantees.
instance, where we approximate predictions p(y S Tr Tr|x,, D.) & A7
4.2 BORE+ with PLS classifiers
In the PLS setting, the result in Theorem gives us a closed-form expression for a classifier upper confidence bound satisfying the condition in Equation 19. Given 8 E (0, 1). we set:
(x) == min(1, max(0, #x(x) + (e())or E [o, 1]. x X
(20)
where o; and 3r are according to Theorem We then obtain the following result for BORE++
Theorem 3. Under the assumptions in Theorem 1, running the BORE++ algorithm with a PLS
classifier ne, as defined above yields, with probability at least - 6, instant regret bound of:
S (L)x(()),((x)) Vt 1,
(21)
and a cumulative regret bound after 2 iterations:
Rr S 4r VT +) E (VTVIVVEE+&G)))
(22)
According to Theorem 3, the regret of BORE++ vanishes if the maximum information gain &r grows sub-linearly, since limy Rx T = and min;er < Rr. Sub-linear growth is known T. to be achieved for popular kernels, such as the squared exponential, the Matérn family and linear kernels [3, 27]. This result also tells us that theoretically BORE++ performs no worse than GP-UCB since they share similar regret bounds [3, 26]. However, practice, the BORE++ framework offers a series of practical advantages over GP-UCB, such as no need for an explicit surrogate model, and a classifier which does not need to GP and can therefore be more flexible and scalable to high-diiensional problems and large amounts of data. The connection with GP-UCB, instead, brings us new insights into how the density-ratio BO algorithm can still share some of the well known guarantees of traditional BO methods.

---

5
Batch BORE
This section proposes extension of the BORE framework which allows for multiple queries to the objective function to be performed in parallel. Although many methods for batch BQ have been previously proposed in the literature, an approximate Bayesian inference problem. Instead of having to derive complex heuristics to approximate the utility of a batch of query points, we can view points in batch as samples from posterior probability distribution which uses the acquisition function as a likelihood.
here focus on approaching batch optimisation as
5.1 BORE batches via approximate inference
cewpiiisatooo---ineeeeeee perspective to BORE, we can formulate a batch BQ algorithm which does not require an explicit regression model for f. The classifier (xx 2 p(y S 7[x) naturally turns out as a likelihood function over query locations E X.. Since the search space X' is compact, we can assume a uniform prior distribution p(x) x 1. Also note that the normalisation constant in this case is simply fx p(y S 7[x)p(xx dx pvy S r) = Our posterior distribution then becomes:
Applying
{(x = p(x|y r) p S -)x)p(()
(23)
ply r)
Therefore, we formulate a batch version of BORE as an inference problem aiming for:
q-' argmin (gl(e)
(24)
'EP
where DKL. DKl((ale) (allé) denotes the Kullback-Leibler (KL) divergence between and É, and P represents the space of probability distributions over X. Sampling from e would allow us to obtain the points of interest in the search space, including the optimum x" and other locations where y S However, as the true ply S T|x) is unknown, we instead formulate a proxy inference problem with respect to a surrogate target distribution f. based on the classifier model. For BORE, set Pr (x) xc ft-1 while for BORE++ the setting is (x) x (x). In contrast to {xx o pvy S r[x). the normalisation constant for the surrogate distributions is unknown, leading us to proxy problem of minimising qe E argmin,,e7 ( (gllpt) at each iteration 2 1. This variational inference problem above can be efficiently solved via Stein variational gradient descent (SVGD) [35], described next.
5.2 Batch sampling via Stein variational gradient descent
In our implementation, we apply SVGD approximately sample a batch B, := ) J.M of M 1 points from p.. Other approximate inference algorithms could also be applied. One of the main advantages SVGD, however, that it encourages diversification in the batch, capturing the possible multimodality of p.. Given the batch locations, observations can be collected in parallel and then added to the dataset to update the classifier model.
SVGD is an approximate inference algorithm which represents a variational distribution g as a set of particles (x* )==1 [35]. The particles are initialised as i.i.d. samples from an arbitrary base distribution and then optimised via a sequence of smooth transformations towards the target distribution, which in our case corresponds to pt x T,-1, The SVGD steps are given by:
x f x + (x,)
i (I,...,,,,
(25)
1 M
(x) =
k(x[ log (,5())))( + V Vx kx/(x/ M
(26)
where i: X' x X R is positive-defintt kernel, and 0 is small step size. Intuitively,
the first term in the definition of ć, guides the particles to the modes of pt. while the second term encourages diversification by repelling nearby particles. Theoretical convergence guarantees [36, 37] and practical extensions, such as second-order methods [38, 39] and derivative-free approaches [40], have been proposed in the literature. Further details on SVGD can be found in Liu and Wang [35].
5.3 Regret bound for Batch BORE++ with PLS classifiers
We follow the derivations in Oliveira et al. [41] to derive a distributional regret bound for batch BORE++ with respect to its target sampling distribution E, which is presented in the following result.
7

---

Theorem 4. Under the same assumptions in Theorem 1, running batch BORE++ + with TT,ō set as in Equation 20, we obtain a bound on the instantaneous distributional regret:
Ft == Ex-p, [f - [x=elf(x)) s 21. [ot-1), t t2 1
(27)
1. and on the cumulative distributional regret at T 2 1: where Lx == maxxEX 7(x]
T R = 1=1
2 e O(VT(bVEr + VErEMT))
(28)
both of which hold with probability at least
8.
As in the case of non-batch BORE++, the distributional regret bounds for the batch algorithm also grow sub-linearly for most popular kernels, leading an asymptotically vanishing simple regret. Although different, to compare the distributional regret of batch BORE++ with the non-distributional regret bounds for BORE++ we may consider case where T is set the function minimum T := fxx') = minxex fxx and the observation noise is small. In this case, the batch sampling distribution would converge to a Dirac at the optimum, so that [f-e[((x))
f(x"). Compared to the regret of non-batch BORE++ (Theorem 3) after collecting an equivalent number of observations T == MT, the expected regret of the batch version of BORE+ after T iterations is then lower by factor of &r /SMrr, noting that &r S εr- Earr. Therefore, batch BORE+ should be able to achieve lower regret per runtime than sequential BORE++ with an equivalent number of observations.
Related work
Since their proposal by Schonlau et al. [42], batch Bayesian optimisation methods have appeared in various forms in the literature. Many methods are based on heuristics derived from estimates given by Gaussian process regression model [11, 12, 43J. Others are based on Monte Carlo estimates of multi-query acquisition functions [10, 131, optimising points over GP posterior samples [44], solving local optimisation problems [45], optimising over ensembles of acquisition functions [46]. Despite that, the prevalent approaches to batch BO are still based on a GP regression model, which require prior knowledge about the objective function and do not scale to nigh-dimensional problems. We instead take a different approach by viewing BO as a density-ratte estimation problem following the take
approach [47, 48] by applying Stein variational gradient descent, a non non-parametric approximate inference method [35], which has been recently combined with GP-based BO [49, 50]. Our theoretical results, however, are agnostic to the choice of inference algorithm. In contrast to traditional batch BO methods, the inference approach does require solving inter-dependent optimisation problems for each batch point, as in heuristic-based approaches [43, 11, 12), Monte Carlo integration over the GP posterior [10, 13], nor sampling from it [44]. SVGD allows batch selection to be solved in vectorised way, which can take advantage of hardware accelerators, such as GPUs.
BORE framework by Tiao et al. [9]. For batch design,
aetimisation-as-infeeee
7 Experiments
This section presents experiments assessing the theoretical results and demonstrating the practical performance of batch BORE on a series of global optimisation benchmarks. We compared our methods against GP-based BO baselines in both experiments sets. Additional experimental results, including the sequential setting (Appendix E), description of the experiments setup (Appendix E), and further discussions on theoretical aspects can be found in the supplementary material.
Theory assessment. We first present simulated experiments assessing the theoretical results in practice, testing BORE and BORE++ in the PLS setting. As baseline, we compare both methods against GP-UCB. This experiment was run by generating random base classifier in the RKHS Hy and then a corresponding objective function via the inverse noise CDF Φh The search space was set as a uniformly-sampler finite subset of the unit interval X' == [0. 1] C R. We applied the theory- settings for BORE++ (Section 2.2) and GP-UCB [25], while BORE employed the optimal PLS classifier (Equation 13).
CCode will be made available https: http//gttttttbtttee/g http::///..ttth./m/////////ttttt borhh--bbowwwteee with- guarantees
8

---

Sis-hump Camsel
BOSENIBOCK 10
107
107
30-1
4122 exEn
10
(MC)
BO-OP LP-EI
10
Botch BORE
300
200
20
170
300
154
Huramare
STYRUNSKI-TANG 7) 10
Anple nunt
10
10-1
100
-.0
2.01
303
110
150
2001
Figure 2: Performance synthetic benchmarks. Plots show the simple regret, i.e., minegr Tt, per iteration. Results were averaged over 5 trials, and shaded areas indicate the 95% confidence interval.
As the results in Figure 1 show, BORE using an optimal PLS classi- fier simply gets stuck at a its initial point, resulting in constant regret. BORE++, however, is able to progress in the optimisation problem towards the global optimum, outperforming the GP-UCB baseline.
10
Global optimisation benchmarks. We evaluated the proposed SVGD-based batch BORE method in a series of test functions for global optimisation comparing it against other BO baselines. In particular, for our comparisons, we ran the locally penalised El (LP- El) method [1] [] and the Monte Carlo based q-EI method [10], which are both based on the EI algorithm, like BORE. Results are presented in Figure 2. All methods ran for
500
1000
1500
2000
Number of evalustions
Figure 1: Regret in theory as- sessment experiment. Results were averaged over 10 trials, and the shaded area indicates the 95% confidence interval.?
200 iterations and used of batch size of 10 evaluations per iteration. Additional experimental details are deferred to the supplementary material.
As Figure 2 shows, batch BORE is able to outperform its baselines on most of the global optimisation benchmarks. We also note that, in some case, due to its complexity the LP-EI method becomes computationally infeasible after 100 iterations, having to be aborted halfway through the optimisation. Batch BORE, however, is able to maintain steady performance throughout its runs
Real-data benchmarks. Lastly, we compared the sequential version of BORE++ against BORE and other baselines, including traditional BO methods, such as GP-UCB and GP-HI [1], the Tree- structured Parzen Estimator (TPE) [15), and random search, real-data benchmarks. In particular, we assessed the algorithms on some of the same benchmarks present in the original BORE paper [9].
Results are presented in Figure 3. As the plots show, BORE++ presents significantly better perfor- mance than BORE in the probabilistic least-squares (PLS) setting (i.e., 3r := 0), as the theoretical results suggested. In fact, it is possible note that BORE (PLS) performs comparably to (or at times worse than) random search, indicating that the optimal least-squares classifier by itself is unable to properly capture the epistemic uncertainty. By using neural network classifier trained via gradient descent and a different loss function (cross-entropy), the original BORE is still able to achieve top performance in most benchmarks. Both BORE versions are only surpassed by traditional GP-based BO on the racing line optimisation problem, as observed in Tiao et al. [9], due to the inherent smoothness the problem, and in the final iterations of the neural architecture search problem by GP-EI. Interestingly, even though restricted to the kernel-basee PLS setting, we observe that BORE+ able to surpass the original BORE in the neural network param-prrr tuning problems (SLICE
I Linear interpolation is applicd to obtain the plotted confidence intervals when the number of trials is small.

---

mottho BORR
mochhd BORR
10
10F"
DORE++
stmple meree
BORE
Randon HE-UCM
atrsppl iegreed
DORE
Ranson
GI--DU
-0
101"
400
Reection
Seeation
(a) dlyper-prameee tuning Parkinson'ss 's dataset
(b)
tuning on CT slice dataset
BERKELEY
MK35T
2.8 10
DOII (PLA)
20 10
DIOHEE (PLS)
6
RGRFF+
24 10
DOTE
ROILE
simple regne
simpl regend
BO GP-UCB
2
TFB
DO GP
DO GP UCB
2,8 10-1
LEO G294
186 10
(c) Racing line optimisation
(d) Neural architecture search on MNIST data
Figure 3: Experimental results real-data benchmarks. The plots show each algorithm's simple
regret averaged across multiple runs. The shaded areas correspond to the 95% confidence intervals.
and PARKINSONS), while maintaining similar performance other tasks. These results confirm that improved uncertainty estimates can lead to practical performance gains.
8 Conclusion
This paper presented an extension of the BORE framework to the batch setting alongside the theo- retical analysis of the proposed extension and an improvement over the original BORE. Theoretical results in terms of regret bounds and experiments show that BORE methods are able to maintain performance guarantees while outperforming traditional BO baselines. The main purpose of this work, however, was establish the theoretical foundations for the analysis and derivation of new algorithmic frameworks for Bayesian optimisation via density-ratio estimation, equipping BO with new tools based on probabilistic classification, instead of regression models.
As future work, we plan to investigate the theoretical properties of BORE under different loss functions and analyse other batch design strategies, e.g., sampling methods for combinatorial domains. The theoretical contributions of this work can also be extended to other versions of BORE, such as its recent multi-objective version [51], and provide insights into other likelihood-free BO methods [52]. Finally, we consider integrating BORE+ with other probabilistic classification models equipped with predictive uncertainty estimates, such neural network ensembles [53], random forests [54], and Bayesian generalised linear models, which should lead to improvements in scalability and additional performance gains.
Acknowledgments, and Disclosure of Funding
Rafael Oliveira was supported by the Medical Research Future Fund Applied Artificial Intelligence in Health Care grant (MRFA1000097) by the Australian Department of Health and Aged Care.
10

---

References
[1] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando De Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104 2016.
[2]
Carl E. Rasmussen and Christopher K. Williams. Gaussian Processes for Machine Learning. The MIT Press, Cambridge, MA, 2006.
[3] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias Seeger. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. Proceedings of the 27th International Conference on Machine Learning (ICMI. 2010), pages 1015-1022, 2010.
[4] Adam D. Bull. Convergence Rates of Efficient Global Optimization Algorithms. Journal of Machine Learning Research (JMLR), 12:2879-2904, 2011.
[5] Zi Wang, Beomjoon Kim, and Leslie Kaelbling. Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior. In Conference on Neural Information Processing Systems, Montreal, Canada, 2018.
[6] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, M Patwary, Prabhat, and R Adams. Scalable Bayesian optimization using deep neural networks. In International Conference on Machine Learning (ICML), Lille, France, 2015.
[7] Jost Tobias Springenberg, Klein Aaron, Stefan Falkner, and Frank Hutter. Bayesian optimization with robust Bayesian neural networks. In Advances in Neural Information Processing Systems (NIPS), Barcelona, Spain, 2016.
[8] Frank Hutter, Holger H Hoos, and Kevin Leyton- Sequential model-based optimization for general algorithm configuration. In International conference on learning and intelligent optimization, pages 507-523. Springer, 2011.
[9] Louis Tiao, Aaron Klein, Matthias Seeger, Edwin V Bonilla, Cédric Archambeau, and Fabio Ramos. Bayesian Optimization by Density-Raie Estimation. In Proceedings of the 38th International Conference Machine Learning, Proceedings of Machine Learning Research. PMLR, Jul 2021.
[10] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In F. Pereira, J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems 25, pages 2951 195192 Curran Associates, Inc., 2012.
[11] Javier Gonzalez, Zhenwen Dai, Philipp Hennig, and Neil D. Lawrence. Batch Bayesian optimization via local penalization. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 648 667,, Cadiz, Spain, 2016
[12] Zi Wang, Chengtao Li, Stefanic Jegelka, and Pushmeet Kohli. Batched high-dimensional Bayesian optimization via structural kernel learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3656-3666 International Convention Centre, Sydney, Australia, 2017. PMLR.
[13] James T. Wilson, Frank Hutter, and Mare Peter Deisenroth. Maximizing acquisition functions for Bayesian optimization. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada, 2018
[14] D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13:455-492, 1998.
[15] James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for Hyper- parameter Optimization. Advances in Neural Information Processing Systems, pages 2546- 2554, 2011.
11

---

[16] Masashi Sugiyama, Hirotaka Hachiya, Makoto Yamada, Jaak Simm, and Hyunha Nam. Least- squares probabilisticc classifier: A computationally efficient alternative to kernel logistic regres- sion. In Proceedings of International Workshop on Statistical Machine Learning for Speech Processing (IWSM12012), Kyoto, Japan, 2012.
[17] Tilmann Gneiting and Adrian E Raftery. Strietly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):3593378 2007.
[18] Andrew R Barron. Approximation and estimation bounds for artificial neural networks, Machine learning, 14(1):115-13) 1994.
[19] Ingo Steinwart and Andreas Christmann. Fast learning from Non-i..d. observations. In Advances in Neural Information Processing Systems 22, pages 1768-1776, 2009.
[20] Reinhard Selten. Axiomatic characterization of the quadratic scoring rule. Experimental Economics, 1(1):43-62, 1998.
[21] A. K. Suykens and J. Vandewalle. Least squares support vector machine classifier. Neural Processing Letters, 9:293-300 1999.
[22] Bernhard Schölkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, Cambridge, Mass, 2002.
[23] Yasin Abbasi- Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Improved Algorithms for Linear Stochastic Bandits. In Advances in Neural Information Processing Systems (NIPS), pages 1-19, 2010.
[24] Yasin Abbasi-Yadkori. Online Learning for Linearly Parametrized Control Problems. Phd, University of Alberta, 2012.
[25] Audrey Durand, Odalric-Ambrym Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. Journal of Machine Learning Research, 19(1):550-68,, 2018.
[26] Sayak Ray Chowdhury and Aditya Gopalan. On Kernelized Multi-armed Bandits. In Proceed- ings of the 34th International Conference on Machine Learning (ICML), Sydney, Australia, 2017.
[27] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 82-90. PMLR, 13-15 Apr 2021.
[28] Johnathan M Bardsley, Antti Solonen, Heikki Haario, and Marko Laine. Randomize-thor then- optimize: A method for sampling from posterior distributions in nonlinear inverse problems. SIAM Journal on Scientific Computing, 36(4):A 1895 A1910, 2014.
[29] Stephan Mandt, Matthew D. Hoffman, and David M. Blei. Stochastic gradient descent as approximate Bayesian inference. Journal of Machine Learning Research, 18, 2017.
[30] Daniel Russo and Benjamin Van Roy. An Information-Theoredt Analysis of Thompson Sampling, Journal of Machine Learning Research (JMLR), 17:1-30, 2016.
[31] Lior Rokach. Ensemble-based classifiers. Artificial intelligence review, 33(1):1-39, 2010.
[32] William D Penny and Stephen J Roberts. Bayesian neural networks for classification: how useful is the evidence framework? Neural networks, 12(6)877-892, 1999.
[33] Yali Amit and Donald Geman. Shape quantization and recognition with randomized trees. Neural Computation, 97)):1455-5888 07 1997.
[34] Nicholas G. Polson and Vadim Sokolov. Deep learning: A Bayesian perspective. Bayesian Analysis, 12(4): 2017.
2017.
12

---

[35] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. In Advances in Neural Information Processing Systems (NIPS), 2016.
[36] Qiang Liu. Stein variational gradient descent as gradient flow. In Advances in Neural Informa- tion Processing Systems, pages 8854-8863, Long Beach, CA, USA, 2017.
[37] Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton. A non-asymplotic analysis for Stein variational gradient descent. In Advances in Neural Information Processing Systems, Vancouver, Canada, 2020.
[38] Gianluca Detommaso, Tiangang Cui, Alessio Spantini, Youssef Marzouk, and Robert Scheichl.
A Stein variational Newton method. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018). Montréal, Canada, 2018.
[39] Chang Liu, Jingwei Zhuo, Pengyu Cheng, Ruiyi Zhang, Jun Zhu, and Lawrence Carin. Under- standing and accelerating particle-base based variational inference. In 36th International Conference on Machine Learning (ICML 2019), Long Beach, CA, 2019.
[40] Jun Han and Qiang Liu. Stein variational gradient descent without gradient. In 35th International Conference on Machine Learning (ICML 2018), 2018.
[41] Rafael Oliveira, Lionel Ott, and Fabio Ramos. No-regret approximate inference via Bayesian optimisation. In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Seventl Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 2082-2092. PMIR,, 27-30 Jul 2021.
[42] Matthias Schonlau, William J. Welch, and Donald R. Jones. Global versus local search in constrained optimization of computer models. New Developments and Applications in Experimental Design, 34:11-25, 1998.
[43] Javad Azimi, Alan Fem, and Xiaoli Z. Fern. Batch Bayesian optimization via simulation matching. Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010 (NIPS 2010), 2010.
[44] Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabas Poczos. Paral- lelised Bayesian optimisation via Thompson sampling. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS), Lanzarote, Spain, 2018.
[45] David Eriksson, Michael Pearce, Jacob R Gardner, Ryan Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), 2019.
[46] Shuhan Zhang, Fan Yang. Changhao Yan, Dian Zhou, and Xuan Zeng. An efficient batch- constrained Bayesian optimization approach for analog circuit synthesis via multiobjective acquisition ensemble. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(1), 2022.
[47] Emanuel Todorov. General duality between optimal control and estimation. In Proceedings of the 47th IEEE Conference on Decision and Control, Caneun, Mexico, 2008
[48] Matthew Fellows, Anuj Mahajan, Tim G. Rudner, and Shimon Whiteson. VIREL: A variational inference framework for reinforcement learning. In 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019.
[49] Chengyue Gong, Jian Peng, and Qiang Liu. Quantile Stein Variational Gradient Descent for Batch Bayesian Optimization. In Proceedings of the 36th International Conference on Machine Learning, Long Beach, CA, USA, 2019.
[50] Rafael Oliveira, Lionel Ott, and Fabio Ramos. Distributional Bayesian optimisation for vari- ational inference on black-box simulators. In 2nd Symposium on Advances in Approximate Bayesian Inference, Vancouver, Canada, 2019.
[51] George De Ath, Tinkle Chugh, and Alma A. M. Rahat. MBORE: Multi-objective Bayesian optimisation by density-ratio estimation. GECCO '22 page 776-785, New York, NY, USA, 2022. Association for Computing Machinery.
13

---

[52] Jiaming Song, Lantao Yu, Willie Neiswanger, and Stefano Ermon. A general recipe for likelihood-free Bayesian optimization. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages PMLR, 17-23 Jul 2022.
[53] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles. In Neural Information Processing Systems (NIPS), 2017.
[54] Matej Balog and Yee Whye Teh. The Mondrian Process for Machine Learning. Technical report, University of Oxford, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [TODO]Code is planned to be made available after the paper publication.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See supplement.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Our focus is theory assessments rather than computational comparisons.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "poecck59cub", "reviewer": "Reviewer_HW2t", "summary": "The paper proposes an extension of BORE, BO based on the direct density-ratio estimation, and its regret analysis is also provided. The authors first derived a regret bound for the original BORE and mentioned a problematic term remains. Based on this observation, a UCB based extension, called BORE++, is proposed, and the authors revealed BORE++ has the same good regret convergence as the original GP-UCB.", "questions": "[1] In BORE++, how is \\sigma_t(x) in (23) estimated? It is seems described in 5.1 (empirical quantile), but I missed, in the end, which uncertainty estimation is employed, and how it affects the theoretical guarantee?\n\n[2]\n> Therefore, batch BORE++ should be able to achieve better performance than BORE++ while running the same number of function evaluations.\n\nThis is a bit counter-intuitive for me. In general, for each one of decision makings, the non-batch model can use a larger number of observations (The batch model can only use t observations during determining next M observations, while the non-batch model can gradually increase observations (e.g., to observe M-th observation, it can use t+(M-1) observations)). Therefore, the claim that the batch model achieve better performance than the non-batch model by the same number of observations is a bit surprising for me. Could you explain its rationale in more detail?", "limitations": "I could not find clear descriptions about current limitation.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-organized and easy to follow regardless of its technical complexity.\n\nOverall, I think that the regret analysis of this paper is informative for the community. The consequence is interesting (BORE has a problematic term and BORE++ can avoid it).\n\nEmpirical evaluation is a bit weak. It only shows the batch setting, though BORE++ would be a novel acquisition function even for the non-batch setting. More comprehensive evaluation with a standard acquisition functions would have been convincing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "peI8_a2-ACZ", "reviewer": "Reviewer_tUys", "summary": "The paper targets multiple problems. First, it develops the theoretical analysis (in particular the regret analysis) for the existing BORE framework by Tiao et al [9], helping to understand BORE's convergence property. Second, it addresses the non-convergence issue of BORE by proposing the method BORE++ which improves the uncertainty estimates combining with using an upper confidence bound (UCB) on the predicted class probabilities as the acquisition function to improve the convergence property. Finally, the paper proposes the batch BORE method along with its theoretical convergence analysis. Some numerical experiments are conducted to assess the theory developed and to compare the performance of the proposed batch BORE method with existing baselines.", "questions": "Apart from some comments mentioned in the Weaknesses section which the authors can response, I also have the additional following questions:\n\n•\tIn Section 7.1, Theory Assessment, when assessing the theoretical results of the proposed method BORE, BORE++ and GP-UCB, I'm just wondering what are the values of some parameters in these algorithms such as beta_t, L_{epsilon}, etc.? I saw that in the appendix, the experiment setup is described in detail, however, I couldn't find the information regarding some parameters listed in the previous sentence.\n\n•\tI would love to understand more about the performance of BORE++ versus BORE, in particularly for more objective functions.\n", "limitations": "Yes, the limitations are described. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n•\tThe paper is very well-written and clear. The proposed methods, the theoretical analysis and the discussion regarding the theoretical analysis are very well presented.\n\n•\tThe theoretical analysis for the BORE framework, the BORE++ method and the batch BORE method is very interesting. To the best of my knowledge, the analysis seems to be correct. The techniques used are new and can inspire future research works. I know these are difficult problems to perform theoretical analysis. I also like the fact that the paper tries to explain the impact of the theoretical analysis and discuss some assumptions used in the theoretical analysis.\n\n•\tAlthough limited, I also like that the paper tries to perform an experiment to assess the theoretical analysis.\n\n\nWeaknesses: In general, to me, the experiments are a bit weak/limited. Please find the detailed comments as follows.\n\n•\tExperiments are only conducted to compare the proposed Batch BORE method with existing baselines, and very limited experiments are conducted to compare the performance of BORE++ over baselines (e.g., BORE or GP-UCB).\n\n•\tFor the experiments that compare the proposed Batch BORE method with existing baselines, only synthetic objective functions are used, there are no real-world problems.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LBoBxxYFrln", "reviewer": "Reviewer_ect9", "summary": "The paper provides a regret analysis of previous work which re-formulated Bayesian optimization with expected improvement as optimization over the input space of a discriminative classifier (BORE). Assuming the discriminator $p(y \\le \\tau | x)$ is a member of a reproducing kernel Hilbert space (RKHS) allows modeling the discriminator using kernel least squares which in turn yields a high probability bound on the discriminator error. From this, bounds on instantaneous and cumulative regret follow. The paper then addresses BORE's potential for a non-vanishing cumulative regret by proposing a UCB-like variant BORE++ which achieves vanishing regret. Then, a batch variant of BORE++ utilizing Stein variational gradient descent is introduced, along with regret analysis, and synthetic and real-data experiments are conducted.", "questions": "* Does the result of theorem 3 only apply when the true $\\pi(x)$ is in the RKHS associated with the least-squares kernel?\n\n* How does the performance of BORE++ compare on standard benchmarks to other non-batch BO methods? Particularly, how does it compare to BORE wrt/ the experiments included in the original BORE paper?\n\n* The batch BORE++ guarantee relies on the Lipschitz constant $L_\\pi$ being bounded away from zero. However, this appears at odds with a decreasing $\\tau$ value to better identify the global minimum. Is there an adaptive schedule for $\\tau$ that can retain vanishing regret while locating the optimum?", "limitations": "There wasn't any discussion that I saw on the limitations of the BORE++ variants or potential negative societal impacts. For the former, some qualitative discussion of which black-box optimization settings BORE++ is preferable / not preferable to standard BO with EI would help.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n\n* The paper mostly appears to utilize previous results in Gaussian process-based Bayesian optimization, online learning, and an approximate inference guarantee in its development. In this sense, the technical contributions seem somewhat incremental.\n\nQuality\n\n* The experimental setup oddly doesn't include non-batch BORE++ which is a primary contribution of the paper. \n\n* For a batch method, I was a little underwhelmed by the experimental results. However, I do want to commend the authors for including two cases where the proposed method isn't the clear winner. \n\nClarity\n\n* The paper was generally very clear and easy to follow. \n\n* The authors might consider moving the SVGD description (sec 3.4) to the description of the batch alg (sec. 6) since it is not relevant prior to this point.\n\nSignificance\n\n* Had the experimental results been more thorough and clearer, the paper's impact might have been higher. Given that BORE is fairly recent and not very prevalent as a standard tool in BO, the significance of guarantees is maybe a question.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AyCbQ8cKMUm", "reviewer": "Reviewer_wzi1", "summary": "This paper presents BORE++ which improve uncertainty quantification over BORE. They present theoretical guarantees for the regret under certain conditions.", "questions": "Is BORE Bayesian? I understand that BORE follows the same sequential updating scheme as Bayesian optimisation. I struggle to see there is any prior in algorithm 1. So is BORE actually Bayesian or is it just probabilistic? \n\nFollowing up on this question, if there is no reversion to the prior: how does BORE ensure a trade-off between exploitation and exploration? Question out of curiosity. (I see you discuss this in lines 121-123 too)\n\n\"Bayesian neural networks [42], random forests [43], dropout methods, etc. [44], also constitute valid approaches for predictive uncertainty estimation.\" Can you elaborate what valid means here?\n", "limitations": "There are no immediate societal impacts to be discussed in this paper.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The related work section is short and should be more elaborate. The authors could consider placing it after the background section, where it should be easier to elaborate pointing to that section.\n\nTheorem 1 is for pi which is not a valid classifier. Can we say anything about the case where pi optimal with the cross-entropy loss?\n\nHow should I relate the bounds in Theorem 2 to GP-UCB with some kernels, when BORE does not have any kernel choice? Are these new bounds for BORE (with no kernel), or just the \"usual\" GP-UCB bounds in a new language?\n\nCan the authors explain that GP-UCB and BORE++ are fundamentally different? Phrased another way: if we use PLS classifer (as in 5.2), are they two parameterizations of the same mechanism?\n\nThe authors explain that BORE can be more flexible because no kernel or GP is needed. From my reading all theoretical guarantees assume a kernel on pi. \n\nFigure 1 needs more ticks on y-axis. \n\nIn general, the experimental section of this paper does not allow any conclusion to be drawn from it. It lacks in both width and depth.\n\nThis is a theoretical paper, but I am to be convinced by the authors that the contribution is substantial to the literature. Specifically, the authors should clearly state that the conditions they prove under are different from GP-UCB.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept