Regret Bounds for Gaussian-Process Optimization in Large Domains
Authors: Manuel Wuthrich
Bernhard Schölkopf
Andreas Krause
Venue: NeurIPS 2021 Poster (2021)
Keywords: Gaussian Process
Bayesian optimization
Multi-armed bandits
regret bounds

Abstract: The goal of this paper is to characterize Gaussian-Process optimization in the setting where the function domain is large relative to the number of admissible function evaluations, i.e., where it is impossible to find the global optimum. We provide upper bounds on the suboptimality (Bayesian simple regret) of the solution found by optimization strategies that are closely related to the widely used expected improvement (EI) and upper confidence bound (UCB) algorithms. 
These regret bounds illuminate the relationship between the number of evaluations, the domain size (i.e. cardinality of finite domains / Lipschitz constant of the covariance function in continuous domains), and the optimality of the retrieved function value.
In particular, we show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).

Regret Bounds for Gaussian-Proeess Optimization in Large Domains
Manuel Wüthricc' MPI for Intelligent Systems Tübingen, Germany
Bernhard Schölkopf MPI for Intelligent Systems Tübingen, Germany
Andreas Krause ETH Zurich Zurich, Switzerland
Abstract
The goal of this paper is to characterize Caussian-Procees optimization in the setting where the function domain is large relative to the number of admissible function evaluations, i.e., where it is impossible find the global optimum. We provide upper bounds on the suboptimality (Bayesian simple regret) of the so- lution found by optimization strategies that closely related to the widely used expected improvement (EI) and upper confidence bound (UCB) algorithms. These regret bounds illuminate the relationship between the number of evaluations, the domain size (i.e. cardinality of finite domains Lipschitz constant of the covari- ance function in continuous domains), and the optimality of the retrieved function value. In particular, we show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).
Introduction
In practice, nonconvex, gradient-free optimization problems arise frequently, for instance when tuning the parameters of algorithm or optimizing the controller of physical system (see e.g- Shahriari et al. [2016)) for more concrete examples). Different versions of this problem have been addressed e.g. in the multi-armed- and the Bayesian-optimizzaton literature (which review below). However, the situation where the number of admissible function evaluations is too small to identify the global optimum has far received little attention, despite arising frequently in practice. For instance, when optmizing the aaper-parameters of a machine-learning method or the controller- parameters of a physical system, typically impossible to explore the domain exhaustively. We take first steps towards better understanding of this setting through a theoretical analysis based on the adaptive-submodulare the present paper to propose a novel algorithm with better performance (we modify the EI and UCB strategies merely to facilitate the proof), but rather to gain an understanding of how GP-optimization performs in the aforementioned setting, as a function of the number of evaluations and the domain size.
framework by Golovin and Krause [2011]. 1].
not the purpose of
As is done typically, we model the uncertainty about the underlying function as Gaussian Process (GP). The question is how close can get the global optimum with T' function evaluations, where T is small relative to the domain of the function (i.e., it is impossible to identify the global optimum with high confidence with only T evaluations). As performance measure, we use the Bayesian simple regret, i.e., the expected difference between the optimal function value and the value attained by the algorithm. For the discrete case with domain size N, we derive a problem- independent regret bound (i.e., it only depends on T, N and is worst-case in terms of the GP prior) for two optimization algorithms that are closely related the well-known expected improvement (EI, Jones et al. [1998]) and the upper confidence bound (UCB, Auer et al. [2002], Srinivas et al.
manuel. wuttuuelw.thhrrchhp......
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

[2010]) methods. In contrast to related work, our bounds are non-vacuous even when we can only explore small fraction of the function. We extend this result to continuous domains and show that the resulting bound scales better with the size of the function domain (equivalently, the Lipschitz constant of the covariance function) than related work (Grünewälder al. [2010]).
1.1 Related Work
The multi-armed bandit literature is closest to the present paper. In the multi-armed bandit problem, the agent faces a row of N slot machines (also called one-armed bandits, hence the name). The agent can decide at each of 7 rounds which lever (arm) to pull, with the objective of maximizing the payoff. This problem was originally proposed in Robbins [1952] to study the trade-off between exploration and exploitation in a generic and principled way. Since then, this problem has been studied extensively and important theoretical results have been established.
Each of the arms has an associated reward distribution, with a fixed but unknown mean Fx- When pulling
at round we obtain payoff' Y, == F, + E,, where the noise is zero mean E[E,,,] = O, independent across time steps and arms, and identically distributed for a given arm across time steps. Let denote the arm pulled at time t by A,. Performance is typically analyzed in terms of the regret, which is defined as the difference between the mean payoff of the optimal arm and the one pulled at time
R
max F.. EE[N]
FA.-
Here, we are interested in the setting where En, small or even zero and we are allowed to pull only few arms 7' < N. We classify related work according to the information about the mean Fx and the noise F,,t that is available to the agent.
1.1.1 No Prior Information
Traditionally, most authors considered the case where only very basic information about the payoff member of a given family of
Fn + En, is available the agent, e.g. that its distribution distributions or that it takes values in an interval, typically [0, 1].
In seminal paper, Lai and Robbins [1985] showed that the cumulative regret Eierry Rg grows at least logarithmically in T and proposed policy that achieves this rate asymptotically. Later, Auer et al. [2002] proposed an upper confidence bound (UCB) strategy and proved that it achieves loga- rithmic cumulative regret in T uniformly in time, not just asymptotically. Since then, many related results have been obtained for UCB and other strategies, such as Thompson sampling Agrawal and Goyal [201]] IJ, Kaufmann et al. [2012]. A number of similar results have also been obtained for the objective of best arm identification Madani et al. [2004], Bubeck et al. [2009], Audibert and Bubeck [2010], where we do not care about the cumulative regret, but only about the lowest regret attained.
However, all of these bounds are nontrivial only when the number of plays is larger than the number of arms T > N. This is not surprising, since no algorithm can be guaranteed to perform well with low number of plays with such limited information. To see this, consider an example where F; and F,, 0 Vn. + i. Since the agent has prior information about which is the right arm the best can do is to randomly try out one after the other. Hence it clear that to obtain meaningful bounds for T < N need more prior knowledge about the reward distributions of the arms.
1.1.2 Structural Prior Information
In Dani et al. [2008] the authors consider the problem where the mean rewards at each bandit are a linear function of an unknown, K Kddimensional vector. However, similarly to the work above, the difficulty addressed in this paper is mainly the noise, i.e. the fact that the same arm does not always yield the same reward. For En,, 0, the O(K) cumulative regret bounds derived in this paper trivial, since with OK) evaluations we can simply identify the linear function.
1.1.3 Gaussian Prior
More closely related to our work, number of authors have considered Gaussian priors. Bull [2011] for instance provides asymptotic convergence rates for the EI strategy with Gaussian-process priors on the unknown function.

---

Srinivas et al. [2010] propose UCB algorithm for the Gaussian finite-time bounds on the cumulative regret. However, these bounds are intended for different setting than the one we consider here: 1) They allow for noisy observations and 2) they are only meaningful if we are allowed to make a sufficient number of evaluations to attain low uncertainty over the entire GP. Please see Appendix B for more details on the second point.
Gaussian-process process setting. The authors give
Russo and Van Roy [2014] use similar analysis derive bounds for Thompson sampling, which are therefore subject to similar limitations. In contrast, the bounds in Russo and Van Roy [2016] do not depend on the entropy of the entire GP, but rather on the entropy of the optimal action. However, our goal here is to derive bounds that are meaningful even when the optimal action cannot be found, i.e its entropy remains large.
De Freitas et al. [2012] complement the work in [Srinivas et al., 2010] by providing regret bounds for the setting where the function can be observed without noise. However, these are asymptotic and therefore not applicable to the setting we have in mind.
Similarly to the present paper, Grünewälder et al. [2010] analyze the Bayesian simple regret of GP optimization. They provide a lower and an upper bound on the regret of the optimal policy for GPs on continuous domains with covariance functions that satisfy a continuity assumption. Here, we build on this work and derive a bound with an improved dependence on the Lipschitz constant of the covariance function, i.e., our bound scales better with decreasing length-scart scallss (and, equivalently, larger domains). Unlike [Grünewälder et al., 2010], we also consider GPs on finite domains without any restrictions the covariance.
1.1.4 Adaptive Submodularity
The Slaattive-suboodllriig framework of Golovin and Krause [2011] in principle well suited for the kind of analysis are interested in. However, we will show that the problem hand is not adaptively submodular, but our proof is inspired by that framework.
Problem Definition
2.1 The Finite Case
In this section we specify the type of bandit problem we are interested in more formally. The goal is to learn about function with domain A = [N] (we will use [N] to denote the set [1....NN) and co-domain TR. We represent the function as a sequence F (Fa)ne(N) Our prior belief about the function F is assumed to be Gaussian
F PN E).
At each of the I' iterations, we pick an action (arm) A, from [M] at which we evaluate the function. After each action, an observation Y, E TR is returned the agent
Y, := FA
Note that here we restrict ourselves to the case where the function can be evaluated without noise.
For convenience, we introduce some additional random variables, based on which the optimization algorithm will pick where evaluate the function next. We denote the posterior mean and covari- ance at time by
M, = A,, Y.l
(4)
C. COV(F) A,, Y.]-
(5)
In addition, we will need the maximum and minimum observations up to time t
Y : = max Ys kE[e]
Vt [1,..,T}
(6)
Y, min Ys
VE (I.
(7)
kEll
Furthermore, we will make statements about the difference between the smallest and the largest observed value
v. ; -
Y, WE {}.
(8)
3

---

Finally, for notational convenience we define
Y,Y, Yr, Yr. Yr.
(9)
Analogously, let us define the function minimum ;= min Pr, maximum f maxne[N] Fr and difference F =
2.1.1 Problem Instances
A problem instance is defined by the tuple (N, T. 14, E), i.e. the domain size N E Nso, the number of rounds 7 E No and the prior (2) with mean μ IR. and covariance $4, where we use S to denote the set of positive semidefinite matrices of size
2.2 The Continuous Case
The definitions in the continuous (A, T, μ, k). i.e. the function domain A, the number rounds E Nyo. a mean function p A + R and positive semi-definite kernel k A? - R.
analogous. A problem instance here is defined by
3 Results
In this section we provide bounds on the Bayesian simple regret that hold for the two different optimization algorithms describe in the following.
3.1 Optimization Algorithms
Two of the most widely used GP-optimization algorithms are the expected improvement (EI) (Jones et al. [1998]) and the upper confidence bound (UCB) (Auer et al. [2002], Srinivas et al. [2010]) methods. the following, we define two optimization policies that are closely related:
Definition 1. The expected improvement Bull [2011] is defined as
ei(r) = maxf# - -a N
(10)
where N is the standard normal density function and &c the complementary cumulative density function of a standard normal distribution. Furthermore, we use the notation
(T=
ci(Tlu,o) =
max T, (0.
(11)
Definition (E12). An agent follows the E12 strategy when it picks its actions according to
A argmax argmaxmax
CT. ei (-Y,1 M v C
(12)
WE[N]
with the expected improvement ci defined in Definition 1.
Definition 3 (UCB2), An agent follows the UCB2 strategy when picks its actions according
{-Y, + + 2og N. Y, MM + VCnn log N
A argmax nE[N]
(13)
The main difference to the standard versions of these methods (see Definition 6 and Definition 7) is that the algorithms here are symmetrical in the sense that they are invariant to flipping the sign of the GP. They maximize and minimize at same time by picking the point which we expect to either increase the observed maximum or decrease the observed minimum the most. This symmetry important for our proof, whether the same bound also holds for following the standard, one-sided El or UCB strategies is open question, discuss this point in detail in Section 4.

---

3.2 Upper Bound on the Bayesian Simple Regret for the Extremization Problem
Here, we provide a regret bound for function extremization (i.e. the goal is to find both the minimum and the maximum) from which the regret bound for function maximization will follow straightfor- wardly. Note that the bound is problem caablem-indepeneenn in the sense that it does not depend on the prior (1, E).
Theorem 1. For any instance (N, T, μ., E) of the problem defined in Section 2.1 with 2 T 500, we follow either the E12 (Definition 2) the UCB2 (Definition 3) strategy, we have
E 1 -
E
log(T)) log log (
S1 (1- zVa
(14)
log(N)
E
This guarantees that the expected difference between the maximum and minimum retrieved function value achieves a certain ratio with respect to the expected difference between the global maximum and the global minimum.
Proof. The full proof can found the supplementary material in Appendix G, here we only give an outline. The proof is inspired by the adaptive submodularity framework by Golovin and Krause [2011]. The problem at hand can be understood as finding the policy (optimization algorithm) which maximizes expected utility. Finding this optimal policy would require solving partially observable Markov decision process (POMDP), which is intractable in most relevant situations. greedy policy which maximizes the expected single-step
Instead, common approach is to increase in utility at each time step t, which our case
A4+1 argmax E Yit1 Y1+1/ A4t1 A, Y.
E -Y-YAAA
(15)
This corresponds to the E12 (Definition 2) strategy. The task now is show that the greedy policy will not perform much worse than the optimal policy. Golovin and Krause [2011] show that this holds for problems that are adaptively submodular (among some other conditions). In the present problem, we can roughly translate this condition to: The progress we make at a given time step has be proportional how far the current best value is from the global optimum. While our problem is not adaptively submodular (see Appendix A), we show that similar condition holds (which leads to similar guarantees).
3.3 Upper and Lower Bound on the Bayesian Simple Regret for the Maximization Problem
For maximization, the goal is to minimize the Bayesian simple regret, i.c. the expected difference between the globally maximal function value and the best value found by the optimization algorithm
E E[T].
(16)
As is often done in the literature (see e.g. Srinivas et al. [2010]), we restrict ourselves here to centered GPs (i.e. zero prior mean; naturally, the mean will change during the optimization). To be invariant to scaling of the prior distribution, we normalize the regret with the expected global maximum:
E
E
normreg
(17)
E
3.3.1 Upper Regret Bound for the E12 and UCB2 Policies
We obtain the following upper bound on this normalized Bayesian simple regret:
Corollary 1. For any instance (N, T. μ, E) of the problem defined in Section 2.1 with mean Nn = O Yn and N 2 T z 500, if we follow either the E12 (Definition 2) or the UCB2 (Definition 3) strategy, we have
log(T) - log 3 3 (T)
normreg <
(1-T 101-1 IV -V=
(18)
log(NV
5

---

normreg
Figure 1: The upper bound the regret from Corollary as a function of the number of eval- uations T. Each curve corresponds ferent domain size N and is plotted for T E (500, .... N}, hence N can be read from the end point of each curve.
Figure 2: An upper bound on the required num- ber of evaluations as a function of the domain size N (implied by Corollary 1). Each curve corresponds to given regret which we want to achieve.
dif-
This implies a bound on the ratio between the expected maximum found by the algorithm and the expected global maximum.
Proof. The Gaussian prior is symmetric about 0, as the mean everywhere (i.e. the probability density satisfies p(F = f) p(F -f) Vf). Since also both the E12 and the UCB2 policies are symmetric, we have E F
E
[F] and hence
E
E
E
F
2E
(19)
and similarly E [
2E
Y
Substituting this in Theorem 1, Corollary follows.
In Figure we plot this bound, and we observe that we obtain nontrivial regret bounds even when evaluating the function only at small fraction of its domain. For instance, if we pick the curve that corresponds to N 1020 (the rightmost curve), and we choose about 0.6, indicated in the figure. This means that we can expect to find a function value of about 40% of the expected global maximum by evaluating the function at only a fraction 10-14 14 of its domain, and this holds for any prior covariance Σ.
10 we achieve regret of
In Figure we plot the upper bound the required number of evaluations T, implied by Corol- lary 1, as a function of the domain size N. We observe that T seems to scale polynomially with N (i.e. linearly in log space) with order that depends on the regret we want achieve. Indeed, is easy to see from Corollary that Ve > 0 3K VN > T 2 K
normreg < Vlog? T
Vlog N +
(20)
which implies that Ve > 0 K. AA 2 T K
T < (1 mc)
(21)
This means for instance that, if we accept to achieve only 20% of the global maximum, the required number of evaluations grows very slowly with about T' ~ 12122 but still polynomially.
3.3.2 Lower Regret Bound for the Optimal Policy
The upper bound from Corollary I is tight,
by comparing (20) to the following result:
Lemma 1 (Lower Bound). For the instance of the problem defined in Section 2.1 with μ 0 and
I. the following lower bound on the regret holds for the optimal strutegy: Ve > 0 3K VN >
T 2 K
Mlg T
normreg 2
Vlog N C.
(22)

---

Proof. Here, sampling without replacement is an optimal strategy, which yields the bound above, see Appendix for the full proof.
It follows from Lemma I that Ve PEOO AA T K
T 2 N mommrey c)²
(23)
Hence, for a given regret, the required number of evaluations T grows polynomially in the domain size N, even for the optimal policy, albeit with low degree. This means that the domain size grows exponentially in the problem dimension, we will inherit this exponential growth also for the necessary number of evaluations. However, since our bounds are problem independent and hence worst-case in terms of the prior covariance Σ, this result does not exclude the possibility that for certain covariances we might be able obtain polynomial scaling of the required number of evaluations in the dimension of the problem.
3.3.3 Lower Regret Bound for Prior-Independen Policies
It is important to note that a uniform random policy will not achieve the bound from Corollary I in general. In fact, despite the bound from Corollary being independent the prior (n, E), it cannot be achieved by any policy that is independent of the prior:
Lemma 2.
For any optimization policy which does not depend on the prior (H, E), there exists instance of the problem defined in Section 2.1 where
T
normreg
(24)
N
which is clearly worse for T & N than the bound in Corollary 1.
Proof. Suppose we construct a function that zero everywhere except in one location. Since the policy has no knowledge of that location, is possible to place it such that the policy will perform better than random selection, which yields the regret above. See Appendix for the full proof. O
3.4 Extension to Continuous Domains
For finite domains, we looked the setting where the cardinality of the domain N is much larger than the number of admissible evaluations T. The notion of domain size is less obvious in the continuous case, in the following we clarify this point before we discuss the results.
3.4.1 Problem Setting
In the continuous setting, we characterize the GP by L and a, which are properties of the kernel k:
(x(xxx) - ((x,v) < La ||x ylloo k<,,x) < 0² Vr A
V
(25)
(26)
where A is the D-dimensional unit cube (note that to use a domain other than the unit cube we can simply rescale). The setting we are interested in is
Lb 20
T
r<
m(Lk, D).
(27)
As we discuss in more detail in Appendix C, m [nL o, D) corresponds to the number of points we would require to cover domain such that we could acquire nonzero information about any point in the domain. Naturally, to guarantee that we can find the global optimum we would require at least that number evaluations T. Here, in contrast, we consider the setting where is much smaller and only small fraction of the GP can be explored.
7

---

3.4.2 Results
Here, we adapt Corollary to continuous domains. The bound we propose in the following is
based on result from [Grünewälder al., 2010], which states that for a centered Gaussian Process (Ga) aEA with domain A being the D-dimensional unit cube and a Lipschitz-conninuous kernel k
[k(x, k(x, v) - Tu 1x
vlloo
Vx, A,
(28)
the regret of the optimal policy is bounded by
E sup G(a)) - G(a)- - S V
2 [TI/]
(2vlog
(2T) (2T) + 15VD)
(29)
LEEA
Note that Grünewälder et al. [2010] state the bound for the more general case of cölder-s functions, for simplicity of exposition we limit ourselves here to the case of Lipschitz-continuuur kernels. Grünewälder al. [2010] complement this bound with a matching lower bound (up to log factors). However, as we shall see, we can improve substantially on this bound in terms of its dependence on the Lipschitz constant I.g we assume that the variance bounded, i.e., k(x,, xx. S o². This is particularly relevant for GPs with short length scales (or, equivalently, large domains) and hence large Li-
Interestingly, Grünewälder et al. [2010] obtain (29) using policy that selects the actions priori (by placing them on grid), without any feedback from the observations made. Here, we will refine (29) by using this strategy for preselecting a large set of admissible actions offline and then selecting actions from this set using EI2 (Definition 2) or UCB2 (Definition 3) online. reasoning along these lines yields the following bound:
Theorem 2. For any centered Gaussian Process (Ga) aeAA. where A is the D-dimensional unit cube, with kernel Is such that
(x(2,, - k(s, S Lak || ylloo
(30)
Vk(x,x) x) S Yx E we obtain the following bound on the regret, if we follow the E12 (Definition 2) or the UCB2 (Defi- nition 3) strategy:
(31)
E sup G(aa) LoEA
8 S
2 2 Ln)
2 log 2
T1/D 1
Lx
+
15VD
+
T1/D
(lo((L))
V20
D
Lk T1/D (1
log
T
(32)
3 & (T)
This bound also holds when restricting E12 or UCB2 to a uniform grid on the domain A, where each side is divided into
La TL/D] segments. Finally, this bound converges O as T Co.
log(Ln]
Proof. The idea here is to pre-select a set of N points at locations XIAN on a grid and then sub-select points from this set during runtime using E12 (Definition 2) or UCB2 (Definition 3). We bound the regret of this strategy by combining Theorem with the main result from [Grünewälder et al., 2010], the full proof can be found in Appendix K.
The important point to note here is that in Theorem 2 the bound grows logarithmically in Lg, as op- posed to the bound (29) from Grünewälder al. [2010], which grows with VTa.- This means that for Gaussian Processes with high T,, i.e. high variability, (32) is much lower than (29) (note that cuboid domains A can be rescaled the unit cube by adapting the Lipschitz constant Lx accordingly, hence a large domain is equivalent to large Lipschitz constant). This allows for meaningful bounds even when the number of allowed evaluations small relative to the domain-size of the function. We il- lustrate this in Figure 3. Consider for instance the case of L = 10 1, 2, = 105, where the number of evaluations is far too low to explore the GP (T 10 & m mL a. D) = 2.5 x 10"). We see from Figure 3a that our regret bounds -second-darkest cyan) remain low while the ones from Grünewälder et al. [2010] (second-darkest magenta) explode. Theorem 2 also provides an- other insight: To allow for straightforward optimization of the acquisition function (e.g. EI, UCB), the domain is often discretized in practical Bayesian optimization. Theorem 2 tells us how fine this discretization should be to still achieve performance guarantees.
8

---

varying D from (dark) 10 (bright)
varying T from 10' (dark) 10 (bright)
Grünzwalder
Grünewaddor
Ours
Ours
(a) Different shades correspond to different di- mensions (1,... 10) from dark to bright, the other parameters are:
(b) Different shades correspond to different
evaluations 7 E {10', 10" ,..,, 10 from dark to bright, the other parameters are:
T, = 10",
1, D 5, = 1.
Figure 3: The regret as a function of the Lipschitz constant Lg. Comparison the bound from Grünewälder et al. [2010] (magenta) and ours (32) (cyan).
4 Relation to Standard EI and UCB
An empirical comparison (Appendix F) indicates EI2/UCB2 require more evaluations than EI/UCB to attain a given regret, but not more than twice as many. This matches our intuition: We would expect standard EI/UCB to perform better because i) any given step, evaluating mizer instead of minimizer will clearly lead to larger immediate reduction in expected regret and ii) we would not expect an evaluation at a potential minimizer to provide any more useful informa- tion than an evaluation at potential maximizer. Further, we would not expect EI2/UCB2 to perform much worse because substantial fraction of evaluations (in expectation half, for a centered GP) will be maximizations.
potential maxi-
If could prove that EI/UCB performs better than EI2/UCB2 for maximization, this would imply that the regret bounds presented above apply to EI/UCB. Unfortunately, proving this formally ap- pears to be nontrivial. Nevertheless, we are able give weaker regret bounds for standard EI/UCB which we discuss in the following.
4.1 Upper Bound on the Bayesian Simple Regret for Standard El and UCB
Let now consider the standard, one-sided versions of EI (Definition 6) and UCB (Definition 7), which are identical to E12 (Definition 2) and UCB2 (Definition 3) except that we drop the second term in the max. We obtain the following version of Theorem 1:
Theorem 3. For any instance (N, T, , μ. E) of the problem defined in Section 2.1 with N 2 T 2 500, we follow either the EI (Definition 6) the UCB strategy (Definition 7) we have
E
E
Y
F
log(T) log 3 3ll (T)
S (1 (1-T z
11-11-11
(33)
log(N)
E
Proof. The proof is very similar to the one of Theorem and can be found in Appendix H.
Note that marked the changes in bold. Now, instead of a guarantee on Y, provide guarantee on Y - F, i.e. the difference between the best obtained value and the function minimum. We can then derive from that a version of Corollary 1:
Corollary 2. For any instance (N, μu, Σ) of the problem defined in Section 2.1 with mean Hh, = vn and N 2 T 2 500, if we follow either standard EI (Definition 6) or UCB strategy (Defiittion 7), have
log(T) log (3lgg (1)) log(N)
- +
normreg 2 1-
(34)

---

Proof. The proof is analogous to the one of Corollary 1.
The important thing to note here is the appearance of the factor in the bound. This means that asymptotically we have
Vlog 7
normreg 2
+
(35)
Vlog N
and
T
(1-ummnryy noinmmmmr/////t
(36)
which is weaker compared to (20) and (21). We believe that this gap is not due EI/UCB actually performing worse than EI2/UCB2, but rather an artifact of the proof.
Limitations
While we believe that the results above are insightful, there are a number limitations one should be aware of:
As discussed in Section 4, the regret bounds we derive for standard El and UCB are weaker than the ones for E12 and UCB2, despite the intuition and empirical evidence that EI/UCB most likely perform no worse for maximization than E12/UCB2. It would be interesting to close this gap.
Another limitation is that the bounds only hold for the noise-free setting. We believe that this limi- tation is acceptable because the problem of noisy observations is mostly orthogonal to the problem studied herein. Furthermore, the naive solution of reducing the noise by evaluating multiple times at each point leads qualitatively similar regret bounds, see Appendix D for more detailed discus- sion.
Further, the bounds from Corollary 1, Theorem 2, and Corollary 2 only hold for zero prior mean (equivalently, constant prior mean). This assumption is not uncommon in the GP optimization literature (see e.g. Srinivas et al. [2010]) but it may be limiting if one has prior knowledge about where good function values lie. It is likely possible to extend the results in this article to arbitrary prior means.
Finally, there are limitations that hold generally for the GP optimization literature: 1) a naive implementation, the computational cost is cubic in the number of evaluations T and 2) the assump- tion that the true function is drawn from Gaussian Process typically not realistic and only made for analytical convenience. It is hence not clear whether the relations we uncovered herein apply to realistic optimization settings or they are mostly an artifact of the GP assumption.
Summarizing, it is clear that the results in the present paper have little direct practical relevance. Instead, the intention develop theoretical understanding of the problem setting.
Conclusion
We have characterized GP optimization in the setting where finding the global optimum is im- possible because the number of evaluations too small with respect to the domain size. We de- rived regret-bounds for the finite-arm setting which are independent of the prior covariance, and showed that they are tight. Further, we derived mains that depend the Lipschitz constant of the covariance function and the maximum variance. In contrast to previous work, our bounds are non non-vucuous even when the domain size very large relative to the number of evaluations. Therefore, they provide novel insights into the performance of GP optimization in this challenging setting. particular, they show that even when the number of evaluations is far too small find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).
for GP optimization in continuous do-
10

---

References
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit prob- lem. CoRR,
2011. URL http::/ttx//ii...///// www.://///aaaaa.ee.e.. 1111. .197.
Jean-Y Yves Audibert and Sébastien Bubeck. Best Arm Identification in Multi-Armed Bandits. In
COLT 23th Conference on Learning Theory- 2010, page 13 p.. Haifa, Israel, June 2010. URL
atttps:/hhat heaphalc...h.. cimppc.archivve wwwchieeseooorrreiee wwweoooeeeeeeeeeee Swwvertes..f/aa--OO00 froa.f000/1100000000--
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed ban- dit problem. Mach. Learn., 47(--3)235-256, May 2002. ISSN 0885-6125. doi: 10.1023/A:
1013689704352. URL htw.h:tps//// /ttp::://doo.ooo org 1023/ 1013639704322.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits prob- lems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory, 0LT pages 23-37, Berlin, Heidelberg, 2009. Springer- ISBN 3-642-04413-1, 978-3- 642-04413-7. URL http: //dl./dl./// acm otg/citatiio.ccoiooooooooooeee att.ttioonncfmiid---11333333333 ottt://ctaati.o...ooaattttaaaaaa 1813240.
Adam D. Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12:2879-2904, 2011. URL http://bbb/ uni-tiieuiiitiierreeee wttttteeeeeer//eteeeeeeeeeeeeeee joraad//aa//////sssss///// jornalss/
jmlr/jmlr12 htm1#Bul111
Varsha Dani, Thomas Hayes, and Sham M. Kakade, Stochastic linear optimization under bandit feedback. In In submission, 2008
Nando De Freitas, Alex J. Smola, and Masrour Zoghi. Exponential regret bounds for gaussian pro- cess bandits with deterministic observations. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, pages 955-962, USA, 2012. Om- nipress. ISBN 978-1 178-1-450331228-11 URL http: //al. acm ortg/orttttteoooooooooooooootttt httg/eitatiion.. c211 3042697.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research (JAIR), 42:427- 486, 2011.
GPy. GPy: gaussian process framework python. since 2012.
Steffen Grünewääder, Jean-yves Audibert, Manfred Opper, and John Shawe- Regret Bounds for Gaussian Process Bandit Problems. In Yee Whye Tch and Mike Titterington, editors, Proceed- ings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 273-280, Chia Laguna Resort, Sardinia, Italy, 2010. PMLR.
Donald R. Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expen- sive black-box functions. Journal of Global Optimization, 13(4):455 Dec 1998. ISSN 1573- 2916. doi:
147. URL URL.htts: org/10 10. 1023/4:220002 A: 1008306431147.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Proceedings of the 23rd International Conference Algorithmic Learning Theory, ALT' 12, pages 199-213, Berlin, Heidelberg, 2012. Springer-Verte Verlag. ISBN 978- 3-642-34105 doi: 10.1007/978-3-0 178-3-642-34100 34106-9_11.
URL http: //dx doi. ort./0..000/////////1
Andreas Krause and Daniel Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press, February 2014.
T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math., 6(1):4-22, March 1985. ISSN 0196-8858. doi: 10.
URL http:
10. 1016/01966-110 8858 (85) 90002-8.
Omid Madani, Daniel J. Lizotte, and Russell Greiner. Active model selection. Proceedings of the 20th Conference on Uncertainly in Artificial Intelligence, UAI '04, pages 357-365, Arlington, Virginia, United States, 2004. AUAI Press. ISBN 0-9749039-0-6. URL http: h/tp//ll.ac/ acm. org/ citation. wttp:mdddmmdmdmmma333333 01777//-1111888..0666677 1036887.

---

Pascal Massart. Concentration Inequalities and Model Selection. Springer, June 2007. URL https: //market. android. wat.aaaaeseatobbboo--oAAAAAAAAA
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-is Mathematical Programming, 14(1):265-294, 1978.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg. Jake Vanderplas, Alexandre Passos, David Couraapaau, Matthieu Brucher, Matthieu Perrot, and Edouard Duch- esnay. Scikit-lcarn: Machine Learning in Python. Journal of machine learning research: JMLR, 12(null):2825-22)) 2830, November 2011. URL https: //dl://dll.. acm. arg//oi/10/ http:/ooo.....5511188888 Www..5555511100 1953048. 2078195.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952. URL http://www. http://wwwojjcteucllll//oooo///t orgg org/
DPubS /etpa///pppsitr/1...oo htt.:///w.....eeeeeeeeeerrrrrrro 1183517370.
lthandle=euclid, bams/
D Russo and B Van Roy. An information-theorrtiic analysis of thompson sampling. Journal of machine learning research: JMLR, 2016.
Daniel Russo and Benjamin Van Roy. Learning to Optimize via Posterior Sampling. Mathematics of Operations Research, 3214):1221-1243, April 2014.
B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the human of the loop: A review of bayesian optimization, Proceedings of the IEEE, 104(1):148-175, Jan 2016.
ISSN 0018-9219. doi: 10.1 10.100//PROC.225.2244111
Niranjan Srinivas, Andreas Krause. Sham M Kakade, and Matthias Seeger. Gaussian Process
Optimization in the Bandit Setting: No Regret and Experimental Design. In Proceedings of the 27th International Conference on Machine Learning (ICML-I0), 2010. URL https:
//arxiv.
3995.
12


Reviews:
[{"review_id": "v-xkMlg9KoR", "reviewer": "Reviewer_i5A5", "summary": "This paper considers Gaussian process optimization and provides bounds for the (normalized) Bayesian simple regret of two policies. Each of these policies can be seen as a symmetrization of either the classical expected improvement (EI) or upper confidence bound (UCB) policies. The symmetrized version of EI, which is denoted by EI2,  picks the point expected to either increase the current observed maximum or decrease the current observed minimum the most. UCB2 is defined analogously with respect to UCB. The bounds obtained are shown to be tight and suggest that it is possible to find points with high (normalized) objective value even when the number of evaluations is small relative to the number of points in the domain, $N$,  (in the finite case, or relative to the smoothness of the prior covariance function in the continuous case), although it still grows polynomially with respect to $N$. Such guarantee contrasts with previously obtained results, which require the number of evaluations to be large with respect to the number of points in the domain.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: This paper contains several ideas that are, to the best of my knowledge, novel. Perhaps the most striking one is the consideration of the symmetrized versions of the EI and UCB policies. Although these policies are likely to have no practical impact, it is interesting to see that there exist simple myopic policies guaranteed to achieve low (normalized) regret in the low-budget regime. Moreover, this proof technique is likely to inspire similar works in other GP-based active learning settings.\n\nQuality: Most of the claims are well supported, and the main ideas in the proofs of the two main results seem to be right (although did not verify in detail most of the calculations). On the other hand, I would encourage the authors to provide a more formal treatment of the following two claims: (1) \"As long as the GP still has large uncertainty... $\\gamma_T$ will essentially\ngrow linearly in $T$\"; (2) \"the problem at hand is not adaptively submodular\". While I understand that the main results proved in this paper do not rely on these two claims, a more formal treatment would help to clarify the technical contributions made with respect to previous works.\n\nClarity: This paper is very well written and, most of the time, has a nice balance between intuitive explanations and formal statements. The mathematical notation is well chosen. Figures 1 and 2 help understanding the significance of the obtained bounds. On the other hand, I would encourage the authors to discuss how the bounds obtained in the finite setting relate to those in the continuous setting. The relationship between these two results can prove somewhat mysterious for a reader omitting the proof of Theorem 2.\n\nSignificance: This paper provides an interesting approach to understanding the performance of simple myopic Bayesian optimization algorithms in the low-budget regime. Although the policies considered here are likely to have no practical impact, it is interesting to see that there exist simple myopic policies guaranteed to achieve low (normalized) regret in the low-budget regime.  At the same time, it would be nice if the performance of the EI2 and UCB2 policies could be related to that of the classical EI and UCB policies,  even at the expense of proving weaker bounds. Finally, I consider that an empirical assessment of the EI2 and UCB2 policies is desirable even if they underperform their classical counterparts.\n\nOther comments:\n\nThe following paper should be discussed as part of the related work: Ryzhov, I. O. (2016). On the convergence rates of expected improvement methods. Operations Research, 64(6), 1515-1528.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have properly discussed the limitations of their work, particularly with respect to the practical relevance of the EI2 and UCB2 policies. \n\nUnderstanding the performance of myopic Bayesian optimization algorithms in the low-budget regime is of great relevance and has the potential to shape the landscape of future research in Bayesian optimization. As a consequence, works of this nature could have a significant societal impact. I encourage the authors to discuss this in more detail.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "mWXXK4tvFC6", "reviewer": "Reviewer_qn7v", "summary": "The paper studies regret bounds for Bayesian Optimization (with UCB & EI as acquisition functions) in the setting where the function domain is large relative to the number of admissible function evaluations, and the function evaluation is noiseless. The paper proposes two modified version of EI and UCB for this purpose and characterize the Bayesian simple regret of these methods, for both discrete and continuous domains. The work shows that the methods can find nontrivial function values even when the number of evaluations is far too small to find the global optimum.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n1.\tThe setting studied seems novel and interesting.\n2.\tThe paper established both upper bounds and lower bounds of their proposed algorithms.\n\nWeaknesses:\n1.\tIt is unclear what the exact setting the paper considers in the continuous domain and how prior work would fail in that setting (please see the Questions).\n2.\tEven when the paper proposes new algorithms (EI2 and UCB2) for the theoretical analysis, but it still benefits if we can see some experimental results about how BO performs with these two new algorithms. I would suggest including at least some BO experiments with the proposed algorithms EI2 and UCB2.\n\nQuestions:\n1.\tAs mentioned, I feel unclear on the setting of the paper in the continuous domain. For discrete domain, I can understand the setting of the problem is when T (number of iterations) << N (the cardinality of the discrete domain). However, for the continuous domain, I can not find/understand the setting. I guess it has something to do with T and L_k, the Lipschitz constant of the kernel. But what exactly the setting in the continuous domain is?\n2.\tLines 93-97: Why the regret bound of [Srinivas et al, 2010] is vacuous when in your setting? In other words, why $\\gamma_T$ grows linearly with $T$ in your setting? I cannot follow the arguments explaining why the simple regret bound in [Srinivas et al, 2010] does not decrease at all. I think this argument needs to be proved rigorously so that you can demonstrate your proposed algorithms and analysis are necessary. I think some dedicated parts of the main paper are even needed to explain why your setting hinders [Srinivas et al, 2010]. \n3.\tDoes the bound in Theorem 2, Eq. (30) converge to 0 when T goes to infinity?  As the bound in [Grunewalder et al, 2010], Eq. (27) does converge to 0. The first term in Eq. (30) does converge to 0, but it is not trivial to derive that the 2nd term in Eq. (30) also converges to 0. Can the authors prove this?\n\nNote: I'm willing to increase my score if the authors can address my questions properly.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "kcwNaS6Gtxl", "reviewer": "Reviewer_sZcy", "summary": "This paper studies the problem of Gaussian process optimization when the number of arms (the domain) is larger than the horizon of the problem. In the finite arm case, it is assumed that the function is drawn from a zero-mean Gaussian prior and the learner is allowed to make T noiseless queries. Two algorithms based on expected improvement and UCB are proposed to solve this by achieving a simple regret that is some fraction of the optimal value. These are shown to be tight. It is shown that similar results can be extended to the continuous domain, but instead depending on a large Lipschitz constant.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall, I think this is a good paper with a solid and reasonably thorough contribution. The problem setting is very interesting where one must make do with potentially very little data compared to the complexity of the problem. I think this class of problems is of great relevance for the bandit/GP/online learning communities. The related work seems to do a good job of placing the paper in the current literature. The paper itself is well-written and easy to understand.\n\nThe limitations of the paper are already discussed in some detail in the paper’s limitations section. To reiterate a couple that I agree are particularly important: (1) the algorithms seem to be non-standard, aiming to reduce uncertainty in both the best and worst estimates. (2) The observations are noiseless.\n\nRegarding (1), in the more traditional setting when many evaluations are actually allowed, do the proposed algorithms achieve comparable performance with the state-of-the-art? I think this would be useful in understanding what trade-offs (if any) are necessary to achieve good performance in the large domain regime. Similarly, is there simple intuition for what makes the analysis of the standard algorithms fail in the large domain regime? It was mentioned in the paper that this was the case, but it was unclear to me why. It seems like whether there is a separation between these two regimes is an open question.\n\nRegarding (2), this seems like a particularly limiting aspect of the results. It is also difficult for me to tell whether handling noise in the observations would require a non-trivial extension of current analysis. Can you elaborate on this? If the extension would be trivial, I would suggest including it perhaps in the appendix in order to make the work more complete.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and suggestions discussed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "dtJkLgqOLo", "reviewer": "Reviewer_PkGh", "summary": "The paper derives bounds for the Bayesian simple regret of two GP optimization policies that are variants of the popular expected improvement and UCB, specifically under the assumption that the querying budget is very low compared to the size of the search space.\nThe authors first do this in the discrete setting where there are a finite number of actions to be taken and then extend their results to the continuous setting.\nThe bounds are derived using a procedure inspired by the adaptive submodularity framework.\nResults show that these new bounds are lower than those from a previous work.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper in general is clear and does a good job setting up the problem and their own approach.\nThe low-budget assumption is natural in many applications of Bayesian optimization where making a measurement is expensive; this addresses the problem of many of previous work where regret bounds are only meaningful when the budget is large.\nThe high-level idea for the proof makes intuitive sense: if we are far away from the global optimum, we are more likely to be able to make significant progress at the next iteration.\nThe included visualizations clearly show that the bounds are much lower than those from Grunewalder et al. (presumably the state-of-the-art bounds in this setting).\nAlso, the authors are very clear about the limitations of this submission.\n\nMy questions for the authors are as follows.\n\nAs mentioned in the paper, EI2 and UCB2, for which the bounds are derived, are special variants of EI and UCB that aim to find both the global minimum and the maximum of the function simultaneously.\nThis symmetry is necessary as it plays a role in the proof for the bounds.\nSo, these bounds don't apply to EI and UCB, which are commonly used in practice, although the authors think they might, but showing this is not trivial.\nI wonder if there are any intermediate results supporting the claim that EI/UCB tends to perform better than EI2/UCB2, as the former only needs to dedicate its budget to one direction of the optimization.\nSince the regret of EI2/UCB2 is upper-bounded as established by this paper, EI/UCB may then have the same guarantee?\nSomething along these lines would make the results more relevant.\n\nA big question I have is about the optimal policy: it is mentioned several times in the paper that the optimal strategy is random sampling without replacement, but I do not see why this is the case.\nIsn't the optimal strategy the one found by solving the intractable POMDP, of which EI is the one-step approximation, as mentioned in section 3.3?\nIt seems to me random sampling is very far from being optimal.\n\nHow does Lemma 2 fit in with the rest of the results?\nDoes it say that despite the bounds derived, there always exist situations where the regret is greater than $1 - T / N$?\nIf so, could stronger bounds be derived when we place restrinctions on the covariance function like in the continuous case?\n\nA few minor details:\n- There is a typo in the notation for the function minimum on line 134.\n- It seems equations (22) and (24) have the wrong sign for $\\epsilon$.\n- EI in equation (10) seems to be defined as a function of the current incumbent $\\tau$.\nI suggest following the convention and define it as a function of a candidate query/action.\n\nOverall, I think the submission tackles an important problem, but more results may be needed to warrant publication.\n\n**After the authors' response**: Thank you for the detailed comments and answers. I am happy with them and have decided to increase my score to 6. I look forward to seeing the (weaker) bounds for the standard EI/UCB and empirical comparisons between the versions being added to the revision.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript considers the development of insightful regret bounds for Bayesian optimization when the domain is so large that we have effectively no hope of finding the global optimum. The analysis is novel and the results give insight into performance in this realistic setting.

After a long discussion and continued engagement with the authors, there is consensus among the reviewers that the work is of high quality, relevant to the NeurIPS audience, and significant.

There is also consensus that there is room for improvement in the current manuscript before publication, and I strongly recommend that the authors take the reviewers' comments and suggestions into account when preparing their camera-ready version. In particular, the empirical evaluation designed and carried out during the rebuttal phase should not be lost.
Decision: Accept (Poster)