A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
Authors: Sudeep Salgia
Sattar Vakili
Qing Zhao
Venue: NeurIPS 2021 Poster (2021)
Keywords: Gaussian Process Bandit
Bayesian Optimization
Kernelized Model
RKHS
Optimal Regret Bounds

Abstract: We consider sequential optimization of an unknown function in a reproducing kernel Hilbert space. We propose a Gaussian process-based algorithm and establish its order-optimal regret performance (up to a poly-logarithmic factor). This is the first GP-based algorithm with an order-optimal regret guarantee. The proposed algorithm is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries in increasingly smaller high-performing regions of the function domain. The search for high-performing regions is localized and guided by an iterative estimation of the optimal function value to ensure both learning efficiency and computational efficiency. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by a factor of $O(T^{2d-1})$ (where $T$ is the time horizon and $d$ the dimension of the function domain).

A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
Sudeep Salgia", Sattar Vakilit, Qing Zhao" "School of Electrical and Computer Engineering
Cornell University, Ithaca, NY {ss3827, qz16) coonneellllleeu edu Ted Research, UK
sattar, vakili www.lliitttteeearchho com
Abstract
We consider sequential optimization of an unknown function in reproducing kernel Hilbert space. We propose a Gaussian process-based algorithm and establish its order-optime regret performance (up to a poly-logarithmic factor). This is the first GP-based algorithm with an order-optimal regret guarantee. The proposed algorithm is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries increasingly smaller gigh-performing regions of the function domain. The search for high-performing regions localized and guided by an iterative estimation the optimal function value to ensure both learning efficiency and computational efficiency. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by factor of O(T2d-1) (where T is the time horizon and d the dimension of the function domain).
1 Introduction
Consider black-box optimization problem with an unknown objective function f: X + R, where X IRd is convex and compact The learner can access the function only through noisy oracle, which, when queried with a point x E X, returns noisy function value at that point. The learning objective approach the maximizer x² of the function through sequence query points { ) chosen sequentially in time. The learning efficiency is measured by cumulative regret given by
T
R(T) = Σ -(x)))
(1)
This cumulative regret measure dictates the online nature of the problem: every query point during the learning process carries loss, not just the end point Fr after learning concludes. The classical exploration-exploittton tradeoff in online learning hence ensues.
1.1 Gaussian Process Models
The above problem ill-posed unless certain structure of the unknown objective function f is assumed to make learning x: feasible. One such structural assumption is the convexity of f. which leads to the class stochastic convex optimization problems. Another class of black-box optimization problems that is gaining interest in recent years is kernel-based learning where f is assumed to live in a Reproducing Kernel Hilbert Space (RKHS) associated with a positive-definite kernel. An effective approach to kernel-based black-box optimization is Bayesian optimization that adopts fictitious prior on the unknown function f. In other words, while is deterministic, is viewed internally by
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the learning algorithm as a realization of a random process over X. A natural choice is the Gaussian process (GP) with a Gaussian prior due to the conjugate property that significantly simplifies the analytical form of the posterior distribution at each newly obtained observation.
In celebrated work, Srinivas ef al. [1] proposed the GP-UCB algorithm that constructs proxy of using the upper confidence bound (UCB) concept first introduced in the classical multi-armed bandit problem [2, 3]. Specifically, each time instant t, UCB of f is constructed using the closed-fom posterior mean and standard deviation of the GP model of f. The algorithm then sets the next query point to be the maximizer of the UCB. Several variations of GP-UCB, tailored for different settings (see Sec 1.3), have since been developed.
The GP-UCB family of algorithms generally enjoy good empirical performance in terms of regret. The analytical guarantees of their regret performance, however, leave considerable gaps to the existing lower bound [4]. More significantly, the state-of-the-art regret bound of GP-UCB does not guarantee a sublinear order in T for certain kernels, hence a lack of guaranteed convergence to f(x*) [4, 5].
Another difficulty with the GP-UCB family of algorithms is their computational complexity, which can be prohibitive as the dimension d and/or the horizon length T grows. The computational complexity has two main sources: (i) the inversion of the covariance matrix in updating the posterior GP distribution, which has an (tt)) complexity with t samples; (ii) the maximization of the UCB proxy over the entire domain X' at each time instant. In particular, due to the multi-modality of the UCB score, its maximization is often carried out using a grid search with an increasingly finer discretization of the entire domain. Specifically, due analytical requirements, the discretization is typically assumed to grow in the order of ((12d) [1, 6]. resulting in an overall computational complexity of O(T24+3).
Several studies exist that tackle the first source of high complexity of GP-UCB, using sparse matrix approximation techniques to reduce the complexity in the inversion of the covariance matrix (see, e.g., [7, 8D. The second source, which is the dominating factor, has not been effectively addressed.
1.2 Main results
The goal of this work is to develop GP-based Bayesian optimization algorithm with a regret guarantee that closes the gap to the lower bound. Furthermore, we tackle the second source of the complexity to ensure both learning efficiency and computational efficiency.
Referred to as GP-ThreDS (Thresholded Domain Shrinking), the proposed algorithm is rooted in the methodology of domain shrinking: it continuously prunes sub-performing regions of the domain X' and zooms into increasingly smaller high-performing regions of X' as time goes. The purpose of the domain shrinking is twofold. First, it ensures high learning efficiency by focusing queries on regions of X' with function values approaching f(x²). Second, it achieves computational efficiency by avoiding global maximization of the proxy function over the entire domain X.
Our specific approach to domain shrinking is built upon sequence of localized searches on growing binary tree that forms successively refined partitions of X. Starting from the root of the tree that represents the entire domain, the search progresses down the tree by adaptively pruning nodes that do not contain the maximizer with high probability, consequently zooming into increasingly smaller seggoperfoning regions of X as the search deepens. Another progressive thread in this sequence of localized searches is the criterion for pruning the tree. Each localized search aims to identify nodes at a certain depth of the tree that contain points with function values exceeding a given threshold. The threshold is updated iteratively to approach the maximum function value f(="). More succinetly, the proposed algorithm is sequence of localized searches in the domain of the function guided by an iterative search in the range of the function.
The above domain shrinking approach via localized search is the primary contributing factor to improved performance in terms of both regret guarantee and computational complexity. In particular, the rate of domain shrinking is controlled to ensure not only the concentration of query points in high- performing regions, but also a constant-sized discretization at all times when estimating the function values. This constant-sized discretization allows a tighter regret analysis and results in a regret upper bound for GP-ThreDS that matches with the lower bound (up to a poly-logarithmic factor). We show that the regret of GP-ThreDS is O(yTTr the maximum information gain after T steps and is representative of the effective dimension of the
(up to a poly-togarithmic factor), where "r denotes
2

---

problem [9, 10]. In the case of Matérn and Squared Exponential (SE) kernels where the lower bounds on regret are known, on substituting the improved bounds on YT from [11], our results match the lower bounds and close the gap reported in [4, 12]. In comparison, the state-of-the-ar analysis of GP-UCB yields an O regret bound [e.g., see, 6, Theorem 3]. The ((vrr) gap between the regret guarantees of GP-UCB and the proposed GP-ThreDS is significant: it can grow polynomially in T (e.g. in the case of Matérn kernel).
Computation-wiss the constant-sized discretization contrasts sharply with the growing (at rate O with time t) discretization required by the GP-UCB family of algorithms, Another factor contributing to the reduced complexity the relaxed search criterion that aims to determine only the existence of threshold-exceeding points, in contrast to finding a global maximizer as in the GP-UCB family of algorithms. As result, GP-ThreDS reduces the computational complexity from ((T24+3) as required by GP-UCB family of algorithms to O
1.3 Related Work
There is a vast body of literature on numerical and theoretical analysis of Bayesian optimization algorithms. With our focus on a computationally efficient algorithm with a provable regret guarantee, the most relevant results to ours are [1] and [6] discussed above. [6] also proved the same O( VTT regret holds for GP-TS, Bayesian optimization algorithm based on Thompson sampling princi- ple. Augmenting GP models with local polynomial estimators, [13] introduced LP-GP-UCB and established improved regret bounds for it under special cases [see, 13, Sec. 3.2]. However, for other cases, the regret guarantees for LP-GP-UCB remain in the same order as GP-UCB. More recently, [5] introduced G-GP-UCB, specific to Matérn family of kernels, that constructs a cover for the search space, as many hypercubes, and fits an independent GP to each cover element. This algorithm was proven to achieve sublinear regret across all parameters of the Matérn family. Almost all other algorithms in the GP-UCB family have a regret guarantee of O(Tr which is Ol (()rr) greater than the lower bound and can grow polynomially in T. Two exceptions to this are the SupKernelUCB and the RIPS algorithms proposed [10] and [14] which achieve a regret of O(vTTT) for discrete action spaces. While this may be extendable to continuous spaces via discretization argument as recently pointed out in [5, 12), the required discretization needs to grow polynomially in T, making it computationally expensive. Moreover, it has been noted that SupKemelUCB performs poorly in practice [5, 8, 12]. GP-ThreDS, on the other hand, is a computationally efficient algorithm that achieves tight regret bounds with good empirical performance (see Sec. 5). A comparison with other related works including the ones in different settings such as noise-free observations and random f are deferred to the supplementary.
2 Problem Statement
2.1 Problem Formulation
We consider the problem of optimizing fixed and unknown function & IR, where X Rd is a convex and compact domain. A sequential optimization algorithm chooses a point x4 E X at each time instant = 1, 2, . and observes yI = (2.)+ +4, where the noise sequence { 1 is assumed to be i.i.d. over and R-sub-Gaussian for a fixed constant R 2 0, i.e., E [e5es] < exp (22R2/2 for all Ç E IR and t E N.
We assume regularity condition on the objective function f that is commonly adopted under kernelized learning models. Specifically, we assume that f lives in a Reproducing Kernel Hilbert Space (RKHS) associated with a positive definite kernel l X' x X + R. The RKHS norm of f assumed to be bounded by a known constant B, that is, [l.f [| S B. We further assume that f is a-Hölder continuous, that is, [xx) f(z') < L|Iz - I'11" for all x, x, E X' for some (0. 1] and > 0. This is a mild assumption as this is a direct consequence commonly used kernels as shown in [13]. We also assume the knowledge of an interval (u, bj. such
RKHS assumption for
1 'The RKHS, denoted by HA, is Hilbert space associated with positive definite kernel k(.,)) and is fully specified by the kernel and vice versa. is endowed with an inner product (-), that obeys the reproducing property, i.e., g(x) = (g, k(z, }), for all g E Hy. The inner product also induces norm ||g]| = (g. g)a. This norm is a measure of the smoothness of the function f with respect to the kernel & and is finite if and only if f E Ha.
3

---

that f(x") E [a, bl. This is also mild assumption domain-speciin knowledge often provides us with bounds. For example, common application of black-box optimization is hyperparameter tuning in deep learning models. The unknown function represents the accuracy of the model for given set of hyperparameters. Since f represents the accuracy of the model, we have f((=*) E [o, 1/. For
simplicity of notation, we assume X' = [0, I and f(x*)= E [0, 1J. It is straightforward relax these assumptions to general compact domains and arbitrary bounded ranges [a, b].
Our objective is computationally efficient algorithm with a guarantee on regret performance as defined in (1), We provide high probability regret bounds that hold with probability at least 1 60 for any given óg E (0, 1), stronger performance guarantee than bounds on expected regret.
2.2 Preliminaries on Gaussian processes
Under the GP model, the unknown function f is treated hypothetically as a realization Gaus- sian process over X. A Gaussian Process {F( is fully specified by its mean function μ(-) and covariance function k(,,)). All finite samples of the process are jointly Gaussian with mean [[F(x;)] p(x:)) and covariance E((F(xx;: ya(;;) ru(z;)) (F(rr) m(x;))] k(r,,4)) for S S and n E N [15]. The noise is also viewed as Gaussian.
The conjugate property of Gaussian processes with Gaussian noise allows for closed-fome ex- pression of the posterior distribution. Consider a set of observations H4 = {x, where X; 42, ..., 224)² and y: = (11, V2...... "t)""" 1/2.....9))" Here Vs- fxx)) Cg where x, X and G, are the zero-mean noise terms, i.i.d. over s for 8 E N. Conditioned on the history of observations
H2, the posterior for is also Gaussian process with mean and covariance functions given
(x) = E [ 174 = N (Kx,,x, + A yt
kx(xx'') E ((F(x) (F())) (x)x)) k(xx,x') ) K (Kx,x, A1) kx
In the above expressions, a [k( x).... k(x,,))] x)]"" Xx,x, is the x covariance matrix 2))),,,)) 7 is the t x t identity matrix and X is the variance of the Gaussian model assumed for the noise terms.
Gaussian processes powerful non-parametric Bayesian models for functions in RKHSs [16]. In particular, the mean function of the GP regression (eqn. (2)) lies in the RKHS with kernel k(---) with high probability. We emphasize that the GP model of f and the Gaussian noise assumption are internal to the learning algorithm. The underlying objective function f is an arbitrary deterministic function in an RKHS, and the noise obeys an arbitrary
distribution.
3 The GP-ThreDS Algorithm
In Sec. 3.1, we present the basic domain-shrinking structure of GP-ThreDS that continuously prunes pub-performing regions of X' and zooms into increasingly smaller high-performing regions of X. In 3.2, we present the method for identifying high-performing regions of X'
3.1 Thresholded domain shrinking
GP-ThreDS operates in epochs. Each epoch completes one cycle of pruning, refining, and threshold updating detailed below. (i) Pruning: removing sub-performing regions of X' from future consideration; (ii) Refining: splitting high-performing regions of X' into smaller regions for refined search (i.e.. zooming in) in future epochs; (iii) Threshold updating: updating the threshold on function values that defines the criterion for Serhsuuub-eefoomacce to be used in the next epoch. The pruning and refining conform to a binary-tree representation of X' with nodes representing regions of X' and edges the subset relation (i.e., region splitting). Throughout the paper, we use nodes and regions of X' interchangeably.
We explain the details with an example. Consider a one-dimensional function over X' = [0, 1] as shown in Fig. 1. Assume that it is known f(x*) E [0, 1.4). The function threshold defining the pruning criterion in the first epoch set the mid-point: TI = 0.7. epoch 1, the domain X' represented by a tree of height 1 with the root representing the entire domain [0, and the two leaf

---

D=0
D=1
0.5
w-p. > 1/2
D=
0.25
0.5
0.75
f(x)
72 0.95
71 0.7
Figure 2: An illustration of the random-walk based search. (Node 6 is the single high- performing leaf node. If the random walk currently at node the correct direction along the shortest path to node 6: via node 1 and then node 3.)
2
Figure 1: Thresholded domain shrinking
nodes representing the two sub- intervals [0, 0.5] and (0.5, (see Fig. 1). In the pruning stage of this epoch, the algorithm determines, with a required confidence, whether each leaf node contains point with function value exceeding TI. Such threshold-exceedingg leaf nodes are referred as high-performing nodes. Otherwise, they are called sub-performing nodes and are pruned, along with their ancestors, from the tree. Suppose that in this example, both sub-intervals [0, 0.5] and (0.5, 1] are identified as high-performing (see Sec. 3.2 on identifying high- high-perffrmiig nodes). Consequently, no node is pruned, and the algorithm proceeds to the refining stage, where each sub-interval splits, and the tree grows to a height of 2 with four leaf nodes. The threshold is then updated to T2 0.95 (see below on threshold updating). The increased threshold reflects adjustment toward a more aggressive pruning in the next epoch as suggested by the presence of (multiple) nodes in the current epoch.
In the second epoch, the pruning stage aims to identify high-performe (defined by 72) nodes among the four leaf nodes. Supposed that it is determined leaf node (0.25, 0.5) is the only seghrrerrorinngg node. Then the nodes [0, 0.25], (0.5, 0.75) and (0.75, 1] and all their ancestors are pruned. In the refining stage, the high-performing node (0.25, 0.5) splits into two. The threshold is updated 73- The algorithm then progresses into the third epoch, facing the same decision problem on the two leaf' nodes (the two children of (0.25, 0.5) of the pruned tree and following the same pruning-refining threshold updating cycle.
For general d- d-dimensional problem, the basic structure is the same with three simple generalizations. First, the two children of any given node are formed by equally splitting the longest edge of the corresponding d-dimensional cuboid (ties broken arbitrarily). Second, in each epoch, the grows by d levels (d = in the above example) in the refining stage by following successive binary splitting d times. The last detail to specify is that if no leaf node identified high-performing in epoch k then the refining stage is bypassed, and the algorithm repeats the search on the same tree (no pruning or refining) with decreased threshold T the next epoch. The decreased threshold reflects lowered estimate of f(x*) based on the absence of high-performing nodes in the current epoch.
The thresholds {T*}a21 epoch k, the algorithm maintains an interval [ak, by] which is believed to contain f(**). The threshold Tk is set to the mid-point of [ax, bx]. The initial interval [a1, b1] is set to the known range [a, of f(x²). At the end of epoch k, if no leaf node identified as high-performing, we set ak++1 ag (bk /2) and be+1 dy (br- ax)/2, which leads decreased threshold in the next epoch. Otherwise, we 0&+1 Tk c2 opk//411 and b by. where Pk: is the height of the tree before the pruning stage of epoch k. and c E (0, 1/2) a hyperparameter (specified in Sec. 3.2.2).
updated iteratively using binary search approach f==*). For each
We emphasize that while the proposed domain-shrinking shrinking approach conforms to an ever-growing tree, the algorithm can be implemented without storing the entire tree. The only information about the
5

---

tree that needs to be maintained is the set Dj. of high-performing leaf nodes identified in the pruming stage of each epoch k. A pseudo-code of GP-ThreDS is provided in the supplementary material.
3.2 Identifying perf-perg nodes
We now specify the local algorithm for identifying high-performing nodes in a given epoch k. Recall that Dx denotes the set of high-pes performiinn nodes identified in epoch k. Each node in Dj has grown d levels and produced 2d leaf nodes in the refining stage of epoch k. The objective of epoch &o + is to determine which of the 2dd [Dx] newly grown leaves are high- segh-performing nodes defined by Tk+1-
In epoch k + 1, the only portion of the tree that is of interest is the [D&] subtrees, each of height d with root in Dr. Our approach is to treat these subtrees separately, one at time. We can thus focus on one subtree to describe the algorithm for identifying which of the 2d leaves are high- nigh-performing. The terms root, node, and leaf all pertain to this subtree. We also omit the epoch index for simplicity.
3.2.1 A raldom-walk based search for high-performing nodes
A straightforward approach to identifying the perforerfoniing nodes is test each of the 2d leaf nodes directly. This, however, results in large number of samples at suboptimal points when the dimension d is high. Our approach is inspired by the RWT (Random Walk on a Tree) algorithm recently proposed as a robust and adaptive algorithm for stochastic convex optimization [17. 18, 19].
Assume first there is exactly one high-performing node among the 2d leaf nodes. The basic idea is to devise a biased random walk on the tree that initiates at the root and walks towards the high- performing node at the leaf level. As illustrated in Fig. 2 with d = 2, a non-leaf node, the random walk can take one of three directions: towards the parent or one of the two children (the parent of the root is itself). The correct direction is to walk along the shortest path to the high-performing leaf node. With the subset relation encoded by the tree, this implies moving to the child containing a threshold-exceedingg
point or to the parent when neither child contains threshold-exceeding points. Hence, to guide the random walk, a local sequential test is carried out on the two children, one at a time, to determine, at required confidence level, whether it is greshold-exceeding (see Sec. 3.2.2). The walk then moves to the first child identified as wreshold-exceeding (if any) or to the parent otherwise. The confidence level of the local sequential test at each non-leaf node is only required to ensure the walk is correctly biased, i.e., the probability of walking in the correct direction is greater than 1/2.
On reaching a leaf node, the algorithm enters the verification stage to determine whether this node is the high-performing leaf node. If the decision is no, it moves back to the parent of this leaf node, and the random walk resumes. If yes, the algorithm exits (under the assumption of a single high-performing leaf node). This decision can be made by carrying out the same local sequential test that guides the random walk at non-leaf nodes. The only difference is in the required confidence level. Given that a false positive at a leaf cannot be corrected due to exiting while a false negative only resumes the random walk (hence retractable in the future), the confidence level for positive decision needs to be sufficiently high to ensure the overall regret performance, while negative decision only needs to ensure the bias of the walk (as in the lon-leaf nodes).
When the number of high-performing leaf nodes is unknown and arbitrary in {0, 10, 1,....,.... 2d), multiple runs of the random walk are carried out to identify them one by one. In addition, a termination test on the root node is carried out before each run to determine whether there are still unidentified high-performing leaf nodes. See the supplementary for details along with a pseudo code.
We emphasize that the local test is carried out using only observations from the current visit to this node; observations from past visits are forgotten. This is to ensure the random-walk nature of the process for anglt-an A computational benefit is that the matrices being inverted to compute the posterior distribution are always small, improving the run run-time efficiency of the algorithm.
3.2.2
The local sequential test
The last piece of the puzzle in GP-ThreDS is the local sequential test on a given node of a subtree. Given a node/region, D C X. threshold r, and confidence parameter 7) E (0, 1), the local sequential test needs to determine, with a I - 7 confidence level, whether D contains point with function value exceeding T.

---

The test first builds discretization of the region D. denoted by the set D3 (x, The set of points in Dg are chosen to ensure that supzeD inf | yll I A. A simple way to construct such discretization is use uniform grids parallel to the axes with resolution small enough to satisfy the above constraint. The parameter A in epoch & is set to A& (c/L) pt./d and is used to control the approximation of the function values in D. Recall that is the Hölder continuity constant while (0, 1/2) is hyperparameter. The local test sequentially queries points in the set D9 to locally estimate f.
To determine whether there exists a point E D with f(x) 2 T, the test builds pair of Upper and Lower Confidence Bounds using sequentially drawn samples and compares each of them to prescribed values. If the UCB goes below LA indicating that the node is unlikely to contain r-exceeding point, the test terminates and outputs negative outcome. On the other hand, if LCB exceeds then this is a 7-exceeding point with the required confidence level. The test terminates and outputs a positive outcome. both the UCB and LCB are within their prescribed "uncertainty" range, the test draws one more sample and repeats the process. A cap is imposed on the total number of samples. Specifically, the test terminates and outputs positive outcome when the total number of samples exceeds S(p, LA A description of the test for I1 E Dg is given in Fig. 3.W. We would like to emphasize that the posterior mean and variance 1 and o² considered in the description below are constructed only from the samples collected during that particular visit to the current node.
after being initialized with a point
If maxxe2, (z) (s(1))=-1(z) 2 terminate and output +1.
If maX ( (x) + (,(m)o,-1(z) - LA", terminate and output -1. Otherwise, query 2, = arg max U (x) 3. ( )0,)((x)
Observe y/ fxx) + c, and use (2) and (3) to obtain μıs and Øs Increment s by Repeat until 8 < (n, ").
If Sn,, LA terminate and output +1.
Figure 3: The local sequential test for the decision problem of finding a r-exceeding point.
The parameter (v)
+ R / 2 +1 log(1/v)) for E (0,1). " the maximum information gain at time f, defined as "tt == Acx (yA: Here, [va: fA) denotes the mutual information between /A- = [Sxx)]x and УΛ = fA + e.A. Bounds on 7/2 for several common kernels are known [20, 21] and are sublinear functions of
The cap ST7, LAa) on the maximum number of samples is given by
LA²) min { teN: 2(1 + ()) D2 (LAa)Vt
$ $1
(4)
The cap on the total number of samples prevents the algorithm from wasting too many queries on suboptimal nodes. Without such a cap, the expected number of queries issued by the local test inversely proportional to J(=bb,) T|. where =b, = arg maax f=x). Consequently, small values of (f()))) - -rl would lead to a large number of queries at highly suboptimal points when ((*,,) is far from f(**). The cap the number of samples thus helps control the growth of regret at the cost of potential increase in the approximation error. It also reduces the cost in computing the posterior distribution by limiting the number of queries at a node.
Note that when the sequential test reaches the maximum allowable samples and exits with an outcome of +1, it is possible that f=b,,) < (i.e., no r-exceeding points in Dy). Thus, 7 may not be lower bound for the updated belief of f(="). as one would expect in the case of an output of +1 from the sequential test. However, using Lemma 2,
obtain high probability lower bound on - f( ). This additional error term is taken into account while updating the threshold as described in Sec. 3.1. The hyperparameter trades off this error with the size of the discretization.
The sequential test can be easily modified to offer asymmetric confidence levels for declaring positive and negative outcomes (as required for in the verification stage of the RWT search) by changing the confidence parameter in 3,. Details are given in the supplementary material.
7

---

We point out that the construction of the UCB is based on the UCB score employed in IGP-UCB [6]. straightforward to replace with other types of UCB scores. The basic thresholded domain shrinking structure of the proposed algorithm is independent of the specific UCB scores, hence generally applicable as a method for improving the computational efficiency and regret performance of GP-UCB family of algorithms.
4 Performance Analysis
In this section, we analyze the regret and computational complexity of GP-ThreDS. Throughout the section, C X denotes a node visited by GP-ThreDS, D, denotes its associated discretization, constructed described in Sec. 3.2.2, and T' arg maX (zz).
4.1 Regret Analysis
The following theorem establishes the regret order of GP-ThreDS.
Theorem 1. Consider the GP-ThreDS algorithm described in Sec. 3. Then, for any 8u E (0, 1),
with probability at least 5o, the regret incurred by the algorithm is given as
R(T)= Trr log T T(lgg T + vlog T log (og(1/6))))
We provide here sketch of the proof. The regret incurred by GP-ThreDS is analysed by decomposing into two terms: the regret in the first kg epochs referred as R1, and the regret after the completion of the first ko epochs referred as R2, where ko max Os S 2a log T). To bound Ri, first bound the regret incurred at any node visited during the first ko epochs using the following decomposition of the instantaneous regret:
f(x") f(x)) - [f(") Th LAGI + ((b)) - ((x)].
In the above decomposition, denotes the epoch index during which the node visited. Each of these three terms are then bounded separately. The third term the expression is bounded using similar approach to the analysis of IGP-UCB [6] (notice that V, is the maximizer of the UCB score)
that is to bound it by the cumulative standard deviation (Ei=1 0z-1(z,)).
Lemma 1. For any set of sampling points (11, T2, I2,..., .t} chosen from D, (under any choice of algorithm),, the following relation holds: E. o (x,) S / DDIt, where (x(x) is defined in (3).
Since GP-ThreDS ensures constant-sized discretization all times (See Lemma 4), the above lemma implies that the sum of posterior standard deviations is O(vi) resulting in a tight bound corresponding the third term (that is (v)T)) tighter than the bound for IGP-UCB which optimizes the UCB score over the entire domain). The first two terms are bounded using the following lemma with an appropriate choice of A
Lemma 2. If the local test terminated by the termination condition at instant S( Dy) as defined in (4), then with probability at least 1 62. we have T LA A5 I f(zb,)
The final bound on Rí is obtained by a combination of the upper bound on regret on each node and the bound on the total number of nodes visited by GP-ThreDS, captured in the following lemma.
Lemma 3. Consider the random walk based routine described in Section 3.2 with a local confidence parameter p 1/2). Then with probability least 1 5n, one iteration of RWT visits less than log(d/61) 2 1/207 nodes before termination.
To bound Rg, we bound the difference in function values using the Hölder continuity of the function along with the upper bound on the diameter of the nodes after kn epochs. Adding the bounds on R and R2, arrive at the theorem. The detailed proofs are provided in the supplementary material. We would like to point out that the regret analysis depends on the choice of the UCB score. While we have used the UCB score of IGP-UCB, this analysis is straightforward to extend to other UCB scores.

---

Time seconds)
HO19 NOME wall tize
R/F verwaa will caok taee
120
AB
1280
040
700
706
74.12
Shamn
Hownbrock
HGP UCB Adppphe Disceetcation
GP-ThreDD
(a) Branin
(b) Rosenbrock
(c) Time taken by diff. algorithms
Figure 4: (a)-(b) Average cumulative regret against wall clock time for different algorithms on benchmark functions. (d) Computation time (in seconds) for 1000 samples for different algorithms.
Remark 1. We note that our assumptions are consistent with those used in proving the lower bounds. In particular, the lower bounds are proven,for for the Matérn family of kernels including the SE kernel in [4]. [13, Proposition proves the Hölder continuity of this family of kernels. Thus, our assumption on Hölder continuity is consistent with the lower bound. In addition, the proof of lower bound considers class of functions whose RKHS norm is upper bounded by a known constant [4. See 1. This upper bound translates to an upper bound on the absolute value of f. which is consistent with our assumption on having a finite range for f.
4.2 Computational Complexity
The following theorem bounds the worst-case overall computational complexity of GP-ThreDS.
Theorem 2. The worst-case overall computational complexity of GP-ThreDS is O(1*), where I is the time horizon.
The proof of theorem follows from the following lemma.
Lemma 4. The number of points in the discretization, |Dy). Dyyl.for for any node D, is upper bounded by constant, independent of time. i.e.. Dyl I O(1). Vt T.
From the lemma, we can conclude that the number of UCB score evaluations GP-ThreDS is constant all times I, hence matrix inversion becomes the dominant source of computational complexity. Since no more than samples are used to compute the posterior distribution at time f, the worst-case cost associated with matrix inversion step (t+)) and consequently the worst-case computational complexity of Th-ThreDS is O(T*) leading to computational savings of O(T2d-1) over GP-UCB family of algorithms. Lemma 4 is proven by showing that the rate of domain size shrinking matches the rate of granularity of the discretization across epochs. Thus, the size of discretization does need to increase with time. Please refer to the supplementary for a detailed proof.
While the discretization does not grow with I, it is exponential in d. Since non-convex optimization is NP-Hard, such an exponential dependence on is inevitable for maintaining the optimal learning efficiency. In this work, focus reducing the computational complexity with respect to the time horizon T'. The proposed domain shrinking technique can be used conjunction with dimension reduction techniques (e.g.. [22]) to achieve efficiency in both T and d (although the price of invalidating the regret bounds).
Empirical Studies
In this section, compare the performance of GP-ThreDS with several commonly used Bayesian optimization algorithms: IGP-UCB [6], Adaptive Discretization (AD) [23], Expected Improvement (EI) [24] and Probability of Improvement (PI) [25]. For the local test of GP-ThreDS use the exact same UCB score as the one in IGP-UCB.
We compare these algorithms and Rosenbrock (see [26, 27] as well as the supplementary material for their analytical expressions). We use the SE kernel with lengthscale of I = 0.2 on domain [0, 1 We use Gaussian noise with
two standard benchmark functions for Bayesian optimization: Branin

---

variance of 0.01. The parameters À in the GP model and R in St are also set to 0.01. The value of on is set to 10 To limit the computational cost in the standard implementation of IGP-UCB, we consider a maximum of 6400 points in the grid.
Figures 4a, 4b, show the per-sample average regret, in log scale, measured at every 0.1 seconds, wall clock time, Specifically, within a given time (the X-axis of the figures), different algorithms process different number of samples determined by their computational complexity. The average per sample regret is then shown against the time taken. The plots are the average performance over 10 Monte Carlo runs, As expected from theoretical results, GP-ThreDS achieves the best performance especially as time grows. Figure 4c directly compares the computation time of all algorithms for processing 1000 samples, averaged over 10 Monte Carlo runs. GP-ThreDS enjoys a much smaller computation cost in terms of time taken (in seconds).
The details of algorithm parameters, benchmark functions, as well additional experiments hyper- parameter tuning of a convolutional neural network for image classification are in the supplementary.
Conclusion
GP-based algorithm witha regret of Ö(VTT)) for black-box optimization under noisy bandit feedback was proposed. That is order optimal, up to poly-logarithmic factors, for the cases where a lower bound on regret known. The proposed approach is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries in high- perforrffrnnn regions of the function domain. It offers high learning efficiency, allows tight regret analysis, and achieves a computational saving of O(T2d-1) over GP-UCB family of algorithms.
Acknowledgments and Disclosure of Funding
The work of Sudeep Salgia and Qing Zhao was supported by the National Science Foundation under Grants CCF-1815559 and CCF-1934985 The work Sattar Vakili was supported by MediaTek Research, We would also like to thank the anonymous reviewers for their constructive comments.
References
[1] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. In ICML 2010 Proceedings. 27th International Conference on Machine Learning, pages 1015-1022, 2010.
[2] T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[3] Peter Auer, Nicolò Cesa BesanBBancch, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-2566 may 2002.
[4] Jonathan Scarlett, Ilija Bogumovic, and Volkan Cehver. Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization. In Conference on Learning Theory, volume 65, pages 1-20, 2017.
[5] David Janz, David R. Burt, and Javier González. Bandit optimisation of functions in the Matérn kernel RKHS. jan 2020.
[6] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In 34th International Conference on Machine Learning, ICML 2017, volume 2, pages 1397-1422, 2017.
[7] Brian McWilliams, David Balduzzi, and Joachim M. Buhmann. Correlated random features for fast semi-supervised learning. Advances in Neural Information Processing Systems, 2013.
[8] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, Lorenzo Rosasco, Lorenzo Rosasco Gaussian, Michal Valko MICHALVAL Alina Beygelzimer, and Daniel Hsu. Gaussian process optimization with adaptive sketching: Scalable and no regret. Technical report, 2019.
10

---

[9] T. Zhang. Learning bounds for kernel regression using effective data dimensionality. Neural Computation, 1779):2077-2098, 2005.
[10] Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Uncertainty in Artificial Intelligence Proceedings of the 29th Conference, UAI 2013, pages 634-663, 2013.
[11] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. 2020.
[12] Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust gaussian process bandit optimization. arXiv preprint S.Ki:2000.007755 2020.
[13] Shubhanshu Shekhar and Tara Javidi. Multi-Scale Zero-Order Optimization of Smooth Func- tions in an RKHS. 2020.
[14] Romain Camilleri, Julian Katz-Samuela and Kevin Jamieson. High-Dimensional Experimental Design and Kernel Bandits. may 2021.
[15] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[16] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian Processes and Kernel Methods: A Review on Connections and Equivalences. 2018.
[17] S. Vakili and Q. Zhao. A random walk approach first-order stochastic convex optimization. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 395-399, July 2019.
[18] Sattar Vakili, Sudeep Salgia, and Qing Zhao. Stochastic Gradient Descent on a Tree: An Adaptive and Robust Approach to Stochastic Convex Optimization. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019, pages 432- 438, 2019.
[19] Sudeep Salgia, Qing Zhao, and Sattar Vakili. Stochastic Coordinate Minimization with Progres- sive Precision for Stochastic Convex Optimization. mar 2020.
[20] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information- theoretic regret bounds for Gaussian process optimization in the bandit setting. JEEE Transac- tions on Information Theory, 58(5):3250-322 3265, may 2012.
[21] Sattar Vakili, Victor Picheny, and Artem Artemev. Scalable Thompson Sampling using Sparse Gaussian Process Models. 2020.
[22] Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Freitas. Bayesian optimization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361 13331-367,,60 jan 2016
[23] Shubhanshu Shekhar and Tara Javidi. Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics, (2(2)3829-3874 2018.
[24] Ziyu Wang and Nando de Freitas. Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters. arXiv preprint 14X6.7440..7588 2014.
[25] Zi Wang, Beomjoon Kim, and Leslie Pack Kaelbling. Regret bounds for meta bayesian optimization with unknown gaussian process prior. arXiv preprint arXiv: 181100588, 2018.
[26] Javad Azimi, Ali Jalali, and Xiaoli 7 Fern. Hybrid batch bayesian optimization. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, volume 2, pages 1215-1222, 2012.
[27] Victor Picheny, Tobias Wagner, and David Ginsbourger. A benchmark of kriging-based infill criteria for noisy optimization. Structural and Multidisciplinary Optimization, 48(3):607-6266 apr 2013.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] The claims in the abstract and introduction are substantiated in Sec. 4, Theorems and 2, with proofs in the supplementary material. (b) Did you describe the limitations of your work? [Yes] Please see the last paragraph in Sec. 4.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We believe this is not applicable due the theoretical nature of our results
(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 set of assumptions of all theoretical results? [Yes] Our assump- tions on the objective function and noise are fully specified in See 2.1.
(b) Did you include complete proofs of all theoretical results? [Yes] Please see detailed proofs for Theorems and 2 and all the lemmas in the supplementary material (Ap- pendix C).
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes) Source code, detailed algorithm descriptions, instructions and all the parameters provided in the supplementary material (Appendix D).
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] All the parameters of Bayesian optimization algorithms are specified in Sec. 5 and supplementary material (Appendix D).
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The figures in the supplementary material report the error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the supplementary material, Appendix D.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(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 are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "WiWoZULHlk0", "reviewer": "Reviewer_UWNk", "summary": "The paper proposes a Guassian process-based Bayesian optimization algorithm for solving the black-box optimization problems with order-optimal regret guarantee. The main contribution of the paper is in domain-shrinking strategy implemented through tree-based region pruning and focusing on high-performing regions to offer high learning and computational efficiency. \n\nThe paper presents solid theoretical proofs of performance analysis, as well as empirical results on benchmark problems.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 is well-written, clear, and easy to follow. It solves an interesting problem with many potential applications. It is both theoretically sound and includes good empirical studies.\n\nA few comments and questions for potential improvement/clarification of the method:\n\nSection 1.2: an illustration of the general idea (domain shrinking concept) would help in understanding the method. Potentially simply refer to Figure 1.\n\nFigure 1: Extend the caption to explain what is presented in the figure and what each symbol stands for.\n\nCould the algorithm be parallelized to improve the time efficiency?\n\nOnly 2 benchmark functions are shown in the results of the paper. More test problems would be appreciated.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are already presented in Section 4. However, more discussion on when the method fails or performs worse than other algorithms shown in Figure 4 would improve the understanding of the method.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UgqXrAdI2om", "reviewer": "Reviewer_GKzd", "summary": "This paper proposes a GP based Bayesian optimization algorithm for regret minimization. This paper uses a domain-shrinking approach where the domain is explored as a tree. Using smoothness assumptions on the true function, it is possible to get upper and lower bounds on the function value in an entire region and this allows the algorithm to decide whether to subdivide a region to explore further or remove it entirely. A key idea and contribution of this work is that the number of leaves in the tree at any one time is a constant. Hence, the total computational complexity of this algorithm is reduced greatly compared to the standard complexity incurred by the famed GP-UCB algorithm. Additionally, the algorithm achieves order optimal performance, closing a gap of \\sqrt(\\gamma_t) observed in previous work. The paper closes with simple numerical experiments. ", "questions": "", "limitations": "", "rating": 7, "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: The paper is very well written. The algorithm, which complicated, is clearly stated and easily understood. The theoretical performance is strong as well and the paper closes a known gap. Furthermore, the computational gain is large. \n\nWeaknesses: Error bars are omitted from the experiments in the main paper and moved to the appendix where they are somewhat large. Presumably this can be fixed by running more repetitions for a final draft. Axis and legend labels on the figures should also be larger to be more legible. Additionally, it is somewhat hard to interpret the experimental results. The results are stated in terms of wall clock time, but no significant discussion of the implementations is given, though this can have a large impact on wall clock performance. Additionally, the theoretical results of this paper state a gain in terms of the regret bound. However, as the results are given for wall-clock time, it is not possible to evaluate this empirically- though this seems like a significant contribution of this paper. \n\nOther comments and questions: \n-\tSaying that the prior is fictitious is somewhat misleading. In terms of implementing the algorithm that is true, but all of the analysis assumes that the prior is real and so does this work.  \n-\tFor the statement of Thm 1, \\delta_0 is presumably user provided? Please clarify. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not discussed in this paper. Note that the submission guidelines state that a paper being theoretical is not sufficient grounds to claim that there are no societal impacts: https://neurips.cc/Conferences/2021/PaperInformation/PaperChecklist. A proper discussion should be added, though I don’t think anything extensive is needed. \n\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "M2TFclBS3bB", "reviewer": "Reviewer_HjBm", "summary": "This paper introduces a GP optimization algorithm under the RKHS setting. The algorithm uses a tree-based domain shrinking approach where elimination, region splitting, and threshold updating are conducted in each epoch. This algorithm achieves a regret guarantee of $O(\\sqrt{T\\gamma_T})$ and has a low computational complexity of $O(T^4)$.", "questions": "", "limitations": "", "rating": 7, "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": "This paper is well-written overall and easy to understand. The tree-based domain shrinking strategy presents its novelty over prior works. The nearly optimal regret guarantee is also a highlight. Most of the proofs seem correct and easy to follow. A comprehensive set of experiments shows that the proposed algorithm also performs well empirically. Some suggestions are given in the Limitations section below.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Main comments:\n- Related Work: More should be said about other domain-shrinking algorithms that work under general smoothness assumptions, such as SOO — could these potentially also give optimal bounds? Some ideas might even be related to those in algorithms like DIRECT (e.g., splitting the longest edge).\n- More importantly, the idea of using a local GP in a small region was already used in [5], and so [5] seems potentially very closely related, but is only mentioned in passing. Please provide a clear comparison in the responses and also in the final paper, both in Section 1.3 and in any relevant technical sections.\n- Related Work: The paper \"High-Dimensional Experimental Design and Kernel Bandits” (ICML 2021) should also be mentioned, since it gets the same bound as SupKernelUCB but could be more practical (this hasn’t been verified yet)\n- It would be better to mention how to construct a discretization in the main paper.\n- Around Figure 3 I don’t see an explicit mention of whether $\\mu_{s-1}$ and $\\sigma_{s-1}$ are computed using all samples so far, or only the ones at the current node — this should be highlighted more clearly, as it seems to be fundamental.\n- The proof of Lemma 3 is a bit hard to follow, especially regarding the definition of $\\tau_d$, which could be reworded.\n- If the authors are claiming optimality, they should make sure that any extra assumptions are consistent with the proofs of the lower bounds.  This should be commented on for Holder continuity and f in [a,b]. Both are consistent based on my understanding.\n- The authors mention order-optimality in many parts, including the title. This ignores log factors, but that should be OK because it’s clarified early in the abstract. But another issue is that matching lower bounds are only known for a few kernels, not general kernels. Hence, the phrasing should be more modest to reflect this.\n- Figure 4: Can error bars be added?\n- Supplementary: Some notation, e.g., $\\bar{S}(p)$, can be hard to locate. I suggest giving more reminders throughout, or even a table of notation.\n\nMinor comments:\n- Line 41: The phrasing “state-of-the-art regret bound of GP-UCB” is ambiguous, and makes it sounds (incorrectly) like that bound is the best known for any algorithm\n- Line 49: Only use phrasing “needs to” for necessary conditions, not sufficient conditions\n- Line 100-101: Phrasing “for the general case” isn’t so clear.  You could say “in other cases”, or more specifically mention the Matern kernel.\n- In the main text, mention where the proofs can be found\n- Line 328: Avoid the unusual phrasing “would have”\n- The coefficients in some equations don't seem correct to me, but they don't affect the main result: appendix p9 -- the final step of $R^{(1)}$; appendix p10 -- the final step of $r_t$.\n- Typos: appendix p9 -- $gamma_N$; appendix p16 -- additional minus sign in the first line of the second case.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are all in agreement that this work is suitable for publication at NeurIPS, particularly due to being one very few works to attain near-optimal cumulative regret in kernelized bandits.  The reviewers also judged that their concerns were adequately addressed by the authors.  Although the comments/suggestions given are largely minor, I ask the authors to carefully consider them in the camera-ready version.  I particularly highlight the following regarding the related work:
- "[5] seems potentially very closely related, but is only mentioned in passing. Please provide a clear comparison in the responses and also in the final paper, both in Section 1.3 and in any relevant technical sections."
- "[the recent paper] "High-Dimensional Experimental Design and Kernel Bandits” (ICML 2021) should also be mentioned" (it is appreciated that this paper was only made public very close to the NeurIPS deadline)
Decision: Accept (Poster)