Sample-Then-Optimize Batch Neural Thompson Sampling
Authors: Zhongxiang Dai
Yao Shu
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian optimization
Gaussian processes
neural tangent kernel

Abstract: Bayesian optimization (BO), which uses a Gaussian process (GP) as a surrogate to model its objective function, is popular for black-box optimization. However, due to the limitations of GPs, BO underperforms in some problems such as those with categorical, high-dimensional or image inputs. To this end, recent works have used the highly expressive neural networks (NNs) as the surrogate model and derived theoretical guarantees using the theory of neural tangent kernel (NTK). However, these works suffer from the limitations of the requirement to invert an extremely large parameter matrix and the restriction to the sequential (rather than batch) setting. To overcome these limitations, we introduce two algorithms based on the Thompson sampling (TS) policy named Sample-Then-Optimize Batch Neural TS (STO-BNTS) and STO-BNTS-Linear. To choose an input query, we only need to train an NN (resp. a linear model) and then choose the query by maximizing the trained NN (resp. linear model), which is equivalently sampled from the GP posterior with the NTK as the kernel function. As a result, our algorithms sidestep the need to invert the large parameter matrix yet still preserve the validity of the TS policy. Next, we derive regret upper bounds for our algorithms with batch evaluations, and use insights from batch BO and NTK to show that they are asymptotically no-regret under certain conditions. Finally, we verify their empirical effectiveness using practical AutoML and reinforcement learning experiments.

Sample-Then-Optinine Batch Neural Thompson Sampling
Zhongxiang Dai', Yao Shu', ,ryan Kian Hsiang Lowt, Patrick Jaillet
Dept. of Computer Science, National University of Singapore, Republic of Singapore! Dept. of Electrical Engineering and Computer Science, MIT, USA {daizhongxiang, shuyao, 1owkh]0comp nus www.edu.....p....oeo edu.sg", jjaillet@mit ,du.ss',jaillettmnn
edu
Abstract
Bayesian optimization (BO), which uses a Gaussian process (GP) as a surrogate to model its objective function, popular for black-box optimization. However, due to the limitations of GPs, BO underperforms in some problems such as those with categorical, high-dimensional image inputs. To this end, recent works have used the highly expressive neural networks (NNs) as the surrogate model and derived theoretical guarantees using the theory of neural tangent kernel (NTK). However, these works suffer from the limitations of the requirement to invert an extremely large parameter matrix and the restriction setting. To overcome these limitations, we introduce two algorithms based on the Thompson sampling (TS) policy named Sample- Theple--Tee--ee Oiten-Optimize Batch Neural TS To choose an input query, we only need train an NN (resp. a linear model) and then choose the query by maximizing the trained NN (resp. linear model), which is equivalently sampled from the GP posterior with the NTK as the kernel function. As a result, our algorithms sidestep the need to invert the large parameter matrix yet still preserve the validity of the TS policy. Next, we derive regret upper bounds for our algorithms with batch evaluations, and use insights from batch BO and NTK to show that they are asymptotically no-regret under certain conditions. Finally, we verify their empirical effectiveness using practical AutoML and reinforcement learning experiments.
the sequential (rather than batch)
ESTO-BNTS) and
Introduction
Bayesian optimization (BO), also called Gaussian process (GP) bandits, has become celebrated method for optimizing pypensive-to-coppee black-box functions, primarily thanks to its practical sample efficiency and theoretically guaranteed convergence [II [4 21 [5]. However, there
important problem settings where BO either underperforms or is not even applicable without sophisti- cated modifications, such problems with categorical
(18), high-dimensional (30), images inputs.
These issues have arisen mainly because GPs (i.c., the surrogate used by BO to model the objective function) are not able effectively model these types of input space, which therefore calls for the use of alternative surrogate models in BO. To this end, neural networks (NNs) serve as natural candidate owing to their remarkable expressivity 37 NNs have repeatedly proven their ability to model extremely complicated real-world functions such as those involving categorical, high-dimensional or image inputs, whereas the development of GPs effectively model these functions still represents active areas of research. In this regard, 699 have adopted NNs as the surrogate model in contextual bandit problems and employed the theoretical framework of neural tangent kernel (NTK) (7) to construct principled algorithm following the well-known policy of upper confidence bound (UCB), hence introducing the Neural UCB algorithm. More recently, [66] have extended Neural UCB to
Correspondence to: Yao Shu <shuyao@ wwtp:/co.mp...cccoooom
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

follow the Thompson sampling (TS) policy and proposed the Neural TS algorithm. Both Neural UCB and Neural TS are equipped with upper bounds on their cumulative regret and perform competitively in real-world contextual bandit experiments.
However, Neural UCB and Neural TS are still faced with several important limitations that may hinder their practical applications. Firstly, these algorithms suffer from the requirement to invert a p x p matrix in every iteration, in which p the number of parameters of the NN surrogate and is usually extremely large since the theory of NTK requires severe overparameterization In practice, a diagonal upproximation is used to avoid the need to invert such a large p x P matrix [66, [9]] which introduces approximation errors in their practical deployment that are unaccounted for in the theoretical analysis, hence causing a disparity between theory and practice. Secondly, the theoretical analyses of these algorithms are restricted to the sequential setting and are hence not applicable in the batch setting where an entire batch of inputs are selected for querying To overcome these two limitations, we introduce two algorithms based on the TS policy named Sample-Then Setee-Otimmize Batch Neural Thompson Sampling (STO-BNTS) and STO-BNTS-Linees need to invert the p p matrix and hence close the gap between theory and practice, and (2) naturally support batch evaluations while preserving the theoretical guarantees.
both of which (1) sidestep the
To avoid the inversion of the p x matrix while still ensuring the validity of the TS policy, we draw inspirations from efficiently sample functions from the GP posterior (with the NTK as the kernel function) without inverting the p P matrix. Specifically, to choose an input query within a batch, our STO-BNTS (resp. STO--NNTS-LAA (resp. a linear model defined w.r.t. the random features embedding of the NTK associated with an NN surrogate) using randomly initialized parameters, and then choose the input that maximizes the trained NN (resp. trained linear model). As a result, if the NN surrogate has an infinite width, the function of the trained NN (resp. trained linear model) is equivalently sampled from the GP posterior with the NTK as the kernel function. This ensures that our algorithms follow the TS policy and hence lays the foundation for our theoretical analyses. Next, to address the second challenge of deriving theoretical guarantees for our algorithms the batch setting, we generalize the theoretical analysis of sequential TS 7 to account for batch evaluations and derive regret upper bound for both of our algorithms when the NN surrogate is dffiite-widtte Then, we leverage insights from batch BO 117 and NTK [31 to show that the regret upper bound is sub-linear (under some conditions), which implies that our algorithms are asymptotically no-regret. Next, when the NN surrogate is finite-width, we derive a regret upper bound for STO-BNTS-Linear by carefully accounting for the approximation error caused by the use of a finite (instead of infinite) NN, and show that the regret upper bound of STO-BNTS-Linear remains sub-linear long as the NN is wide enough.
optimization 42] and Bayesian deep ensembles [24] to
only needs to use the current observation history to train an NN surrogate
Our contributions are summarized as follows:
Our STO-BNTH and BNTS-Linear algorithms sidestep the inversion of the x p matrix required by Neural UCB and Neural TS, which closes their gap between theory and practice.
Our algorithms naturally support batch evaluations with theoretical guarantees.
Our algorithms are equipped with an upper bound on their cumulative regret when the NN surrogate is infinite-widhh and are asymptotically no-regret (i.e., their regret upper bound is sub-linear) under certain conditions. Moreover, when the NN surrogate is finite-width, our STO-BNTS- Linear still enjoys a regret upper bound, which remains sub-linear as long as the NN is wide enough.
We demonstrate our empirical effectiveness in real- world experiments including automated ma- chine learning (AutoML) and reinforcement learning (RL) tasks, well as a task on optimization over images. To the best of our knowledge, our experiments (Sec.5) are the first empirical study to show the advantage of neural bandit over GP bandit algorithms in practical AutoML and RL tasks.
2 Background
Neural Networks and Neural Tangent Kernel. In this work, we adopt the same construction of neural network (NN) as (2). We use fxx; 8) to denote the scalar output of an (L + layer NN with parameters 0 E Rº and input x, and use Vel (x: 8') to represent the gradient of the NN evaluated at
'The work of (23 focuses on the contextual bandit setting and aims to choose a batch of inputs given a batch of diverse contexts. So, their methods are not applicable in our setting of BO where the contexts are fixed in all iterations, since they do not explicitly encourage input diversity which is crucial problem in batch BO g 17

---

0 = O' For simplicity, we assume every layer of the NN has the same width and represent the width as m. We denote our initializaiton scheme for I as init()) which simply independently samples every NN parameter from the standard Gaussian distribution. The NTK [27 provides an explicit connection between NNs trained via gradient descent and kernel regression using NTK as the kernel function (2]. The NTK matrix, denoted as O has been shown to stay constant during the course of training as the width m of the NN approaches infinity [27]. Moreover, O can be approximated by an empirical NTK θ [2] calculated using a finite-width NN: ( x') (Vof 60). V Vf 60)) xe @(x, x'), where Op init(-) denotes initial parameters and Vo (x; 0o) is referred to as the neural tangent features [66] We refer the readers to the works of [2 27 for a more detailed background on NTK.
Problem Setting, We aim to maximize a black-box function f X + R. i.c. find x* E arg max xx in which the domain X' is a finite subset of the d-dimensional unit ball: X' C [x||x]] < I]. Of note, our theoretical results allow X' to be very large because our re- gret upper bounds only depend on its cardinality | logarithmically. Moreover, all our theoretical results can be easily extended to problems with continuous imput domains with additional assump- tion on the Lipschitz continuity of f (Appendix E. We focus on the noisy setting, i.e., for every queried x, we observe noisy output y(x) f(x) + Ç where Ç (O, o²). For simplicity, focus on the setting of synchromous batch BO with a batch size B where a new batch of B inputs are selected only after all evaluations of the previous batch are completed [17]. However, our theoretical results also hold for asynchronous batch BO where a new input query is selected once any pending query is completed (Appendix (). We denote the 7th selected input in iteration as x,. We analyze the cumulative regret of our algorithms:
Ri = -'' EB ( - f(x))), because if Pr is shown to be sub-linear in T, then the simple regret ST = min,, f(x))) S R /T goes to 0 asymptotically, which implies that our algorithm is asymptotically no-regret.
3
Batch Neural Thompson Sampling
Our STO-BNTS and STO-BNTS--inear algorithms are presented in Algos. and In both algorithms, the NN surrogate f(x; 0) can be either infinite-width or finite-width. Both STO-BNTS
and STO-BNTH B-0--NNT--AN BNTS-Linear follow the TS policy to select an input query x!: They firstly (a) obtain a function f [x: 65) which is equivalently sampled from the GP posterior with the NTK as the kernel:
G 3 f (.))) [24 (see Appendix A for details), and then (b) maximize the function to select the next query: x;- arg maxxex S (x; 0j). Step (a) is achieved via the sample-then-optimizz procedure, i.e., by firstly sampling initial parameters (6, and 6)) to construct a function f (x; f), and
then optimizing the function using gradient descent to obtain the resulting function of f/ (xx 6f).
STO-BNTS (Algo. 1. In every iteration of STO-BNTS, we firstly construct an NN f(x 0) and
multiply its output by 3. = 2 1og(==2=){x]] (3)))) in which ō (0, 1) (Theorem 1 P Next, choose
the شLh query xt. we start by sampling initial parameters 0g ~ init(.) ) and % ~ initi .)) independently,
and then set the parameters of 6, in the last layer to (lines 4-5). Next, we use the resulting 6g and %, as well as the NN fxx, 0). to construct a function fi (x, 0) (line 6). Subsequently, in line 7, using the current history of observations (denoted as D.-1) as the training set, we train fi (x, 0) (setting do as the initial parameters) using gradient descent with the following loss function:
L. (:0.D..1)= = Σ
(ut f((2;;)) + 100210-0000 60112.
(1)
in which 0² is the observation noise variance (Sec. 2h. After the training, we use the resulting function ff ot) as the acquisition function to choose the 7th query: x; = arg maxxex (x; o)) (line 8). This procedure (lines 4-8) is repeated independently for B 2 1 times, after which batch of B queries (x{)==1...,B are selected and then queried to produce the observations I
Next, the newly collected input- pairs {xx, 3t) 1:=1.....B are added to D.-1 1 and the algorithm proceeds to the next iteration. Importantly, if the NN f(x:0) is infinite-width, the function [x of obtained after the training in line 7 is a sample from the GP posterior with the NTK the kernel: GP(()11() (3),33 0f )) (24) (Appendix (A). This ensures the validity of the TS policy and is crucial for deriving the theoretical guarantee of STO-BNTS (Sec. A
STO-BNTS-Linear (Algo.P) D. Similar to STO-BNTS, at the beginning of iteration t, STO-BNTS-
Linear firstly constructs an NN f(x; 8) and multiply its output by 3, To choose the 8th query in
Note that 3 introduced only for the theoretical analysis, and hence set & 1 in our experiments.
3

---

Algorithm STO-BNTS
1: for 1,2,... ..... T/B do
2: Construct NN f(x; 0) and multiply its output by 3r (Theorem)
3:
for .., do
4:
Sample 8n ~ init(.)
5:
Sample 8g ~ init(.) and set the parameters of 8g the last layer to 0
6:
Set (x: 0) = f(x; 0) + of (x: fo), 6%)
7:
Use observation history Dz-1 to train f (x;; 0) with the loss function (0, D,-1)
(setting Ao as the initial parameters) using gradient descent till convergence, to obtain
0; = arg ming C (0, D.-1)
8:
Choose x arg maxxex (x; 0;)
9: Query the batch {x:) )x))inn 1..... to yield the observations {yi lu..,, B, and add them to D.-
Algorithm 2 STO-BNTS-Linear
1:
for = ......... T . do
2:
Construct NN f(x; 0) and multiply its output by 3e (Theorem
3: for = 1, . do
4:
Sample 8 ~ init()), (), and define fi(x: 8) (Vof 6)).
5:
Sample tu init(-)
6:
Use observation history Di-1 to train fi (x: 8) with the loss function C0, D:-1) (setting do as the initial parameters) using gradient descent till convergence, to obtain
= arg ming (0, 1
7:
Choose the query x = arg maxx 0
8: Query the batch [x:):=1..... B to yield the observations { and add them to Dz-1
iteration 1, STO-BNTS- firstly constructs linear model fi (x; 0) using the neural tangent features (i.e., Vef(x: 06) where 8/ ~ init(-) . are initial parameters) as the input features (line 4). Next, sample 0g init(-) (line 5) and use it as the initial parameters to train (x; 0) using gradient descent with the same loss function ( as TTO-BNTS, to produce 0 (line 6). After that, the th query is selected by maximizing the acquisition function fi 0;): x; arg xaxxex (x: 05) (line 7).
Lines 4-6 of STO-BNTS-Linee can be interpreted as a sample-then-opiing neural tangent features as the input features. As a result, same as STO-BNTS, if an infinite-width NN used, the function [x; 0;) obtained after the training in line is a sample from the GP posterior with the NTK as the kernel: GP( (-), 0 Poo-111 (:--)) (Appendix A). However, in contrast to STO- BNTS, if the NN is finite-widdth the function fi; 8)) derived after line 6 of Algo. still corresponds sample from the GP posterior with the empirical NTK θ x') (V (x: 0,), Ve 0))) as the kernel. As result, for infinite-widde NNs, STO-BNTS - and STO-B BNTS enjoy the same sub-linear (under some conditions) upper bound on their cumulative regret (Sec. 4.1); however, for finite-width NNs, unlike STO- -TO-BNTS, STO-BNTS- sub-linear as long as the NN is wide enough (Sec.
method 42) using the
still enjoys regret upper bound which is
Although STO-BNTS--LAE inear (Algo. 2 has the theoretical advantage of a theoretically guaranteed convergence also for finite-width NNs (Sec. 4.2) we expect STO-BNTS (Algo. TT) to perform better in practice. This is because STO-BNTS explicitly trains an NN surrogate model in every iteration and is hence able to directly exploit the strong representation power of NNs model the objective function f. In contrast, STO-BNTS-Linear derives its representation power entirely from the neural tangent features of NTK. However, has been shown [ 69 that neural tangent features of NTK can not completely realize the representation power of NNs. As a result, STO-BNTS is expected to be more competitive practice, especially in problems where the strong representation power of NNs is essential for accurately modeling the complex objective functions. We empirically verify this practical advantage of STO-BNTS in our experiments (Sec. 5.5
4 Theoretical Results
We firstly prove regret upper bound for both STO-BNTS and TTO--BNT--innen using infinite-wide NNs, and show that both algorithms are asymptotically no-regret under certain conditions (Sec. 441). Next, we derive regret upper bound for ETT--BNT--Lineee when the NN is finite-width, and show that the regret upper bound remains sub-linear as long as the NN wide enough 4.2).

---

4.1 Infinite-width NNs
Here we use Y1:e to denote the output observations from iterations 1 to (i.c., è x B observations in total) and use Y denote the vector of observations at set of inputs A C X. Theorem 1 (proof in Appendix C gives a regret upper bound for both STO-BNTS and STO-BNTS-Linest
Theorem 1 (Infinite-width NNs). Assume that is sampled from a GP with the NTK O as the kernel function, that [x)
< B' Vx E X for some B' > O, and that ①(x, x') S Ko vx, x' E X for some Kg > 0. Let ō E (0, 1) and B. 2 2 1 (36)). Then with probability of 1 6,
R7 = +1=0@@VT(V+++1
where Ö ignores all logarithmic factors, "YT is the max information gain about f from any set T observations, and C an absolute constant s.t. B 11::--1-1fffalllal alv1.) S C, Vt 2
The assumption of ((x, x') S Ko is natural and in line with [1,, and [(x) S B' is also mild assumption since most practical objective functions have bounded values. Our primary assumption that is sampled from GP with the NTK as the kernel function is common assumption in the analysis BO algorithms 17 57]. Of note, compared with the assumptions from previous works using other commonly used kernels such the squared exponential (SE) kernel [7 57], our assumption on f holds for more complicated objective functions. Specifically, the class of functions sampled from GP with the NTK the kernel subsumes more non- smooth and sophisticated objective functions compared with the other commonly used kernels. As shown in [7]. C' can be chosen to be an absolute constant that is independent of B and 7 as long as we initialize our algorithm using the uncertainty sampling method, which entails choosing the initial inputs by sequentially maximizing the GP posterior variance (more details in Appendix [B. Specifically, for any chosen constant C' > 0, as long as we run the uncertainty sampling initialization stage for Tinit iterations such that ((B - 1T.,. ) Tiii S C, then
yA S C, Vt 2 1 is guaranteed be satisfied, Since it has been shown by the work of [3 that "r Ö 1) grows sub-linearly for the NTK F therefore, ((B - 1) rrr,, m/Tim is decreasing as iim increases. As result, for any chosen C, we are able to choose a finite Tin such that the condition ((B - 1)Tr, //mm S C is satisfied.
For example, if we choose C 1, then the required number of initial iterations approximately Tinit = @ [ 1)d). As a result, the regret upper bound will be a summation of B (i.e., the regrets incurred during the initializatioin stage, because the regret every step is upper-bounded by 2B') and the regret upper bound from Theorem I with C = 1. Since both B' and Tima are constants independent of T (assuming that B is independent of 7), the asymptotic regret upper bound can be simplified into Rt Ó(VT(1 + VTT)). Plugging in 7T = ((/dd)1)/d) the final regret upper (2) which is sub-linear in T and hence implics that our STO-BNTS and STO-BNTS- Linear are both asymptotically no-regret when the NN surrogate is infinite-width
bound becomes PT O + (
Moreover, when T >> and B is a constant which is independent of T, Theorem gives us insights on the benefit of batch over sequential evaluations. In this case, the regrets incurred during initialization (i.c., ((B )) is negligible. Therefore, our analysis above suggests that our algorithms with batch evaluations (B > 1) enjoys the same asymptotic regret upper bound as its sequential counterpart (B- = 1) since the resulting regret upper bound of Rt = ((VT(1 + vTT)) does not depend on the batch size B. This demonstrates the advantage of batch evaluations because when B > 1, some of our evaluations can be run in parallel, which is not supported by the sequential setting with B- achieve a simple regret of the order Õ(T
As a simple illustration, for a large T, both the sequential and batch settings
after T function evaluations. However, since our batch setting can evaluate every B >>> I selected inputs in parallel in every iteration, our batch setting with B > achieves this simple regret after only T/B iterations, which is only fraction (1/ /) of the T iterations required by the sequential setting. This also shows that we enjoy more benefit with larger batch size B.
Note that in order to quote the results from BII. we need follow their assumption to assume that the domain X is a subset of the d-dimensional unit hyper-sphere: X C [x|]|x||, 1}. which is more strict than our main assumption (Sec.) that X' is subset of the unit hyler- X' C [x||||[2 I 1}.
5

---

4.2 Finite-width NNs
Here we prove regret upper bound for STO-BNTS-Liness with finite-width NN. The main technical challenge in the proof lies in the disparity between the exact and empirical NTKs, i.c., the function f assumed to be sampled from a GP with the exact NTK θ yet our acquisition function [x Bt) (line 7 of Algo. 2 is obtained using the empirical NTK θ when the NN is finite-width. To this end, we make use of the following theoretical guarantee on the approximation enror between Q and θ Proposition 1 (Theorem 3.1 of (2).. Choose e > 0 and ā E (0, 1). If the width of every layer in an log( (T then Vx, x' E X, we have with probability 2 1 - 6/4 that
NN satisfies m Q - gx ( 0o). Vef (x', 00)) xxx,x)) S (L [ 1)e.
Proposition Censures that we can reduce the upper bound (L+1) on the approximation error between @ and θ by increasing the width m of the NN. For example, let m = Catk - log (og(44]/1)) / /5) for some constant Cakk > O, then the approximation quality of Proposition[]] can be expressed as (L 1)= = Catx +
( 1/2 log' /4 [4L|x] /m)m - 1/4 which decreases as the width m increases. In
our theoretical analysis, we assume that (L + 1)E S 1, which can be satisfied as long as m is large enough. The regret upper bound for STO-BNTS-L.Ae Linear is given in Theorem (proof in Appendix D):
Theorem 2 Finite-width NNs). Let 8 E 10, and 3t = 2 log
Then we have
RT = Ö(e VTVTT + 1) - T m 1/8 (L + 1)5/4)
with probability of 2 1-16 5. Here "T and C are the same those defined in Theorem 7
The first term in the regret upper bound in Theorem i is the same as that of Theorem T for infinite- width NNs and can hence be made sub-linear by using uncertainty sampling as the initialization stage: ((r(24-1)/(2)) The second term in the regret upper bound represents the additional regrets incurred by the use of finite-width NNs, which can also be made sub-linear by choosing m- = (2T22)). In other words, if the width m of the NN is chosen to be large enough (i.e., if m (((22)) then the cumulative regret of STO-BNTS-Linear scales sub-linearly in T.
RT = (V(V(L1 +1++gg VTT)
4.3 Discussion
The assumption on the function f for our theoretical analyses in Theorems I and differs from those made by the previous works neural contextual bandits [66 69). Specifically, these previous works have relied on the assumption of positive definite NTK Gram matrix to approximate the value of f (only evaluated at the observed contexts up to iteration T) using a function that is linear in the neural tangent features. When translated into our setting (which is equivalent to the contextual bandit setting where all contexts are fixed for all > 1), the assumption of positive definite NTK Gram matrix can be easily violated as long as any input x queried more than once, thus rendering this assumption unrealistic in our setting. In contrast, we have assumed that is sampled from a GP with the NTK as the kernel, which is a common assumption in the analysis of BO [17, 57 and allows us to derive a regret upper bound. As result of the different assumptions, our regret upper bounds are not directly comparable with those from the previous works on neural contextual bandits [66] 69
Experiments
We compare our STO-BNTS and STO-BNTS-Linear with the baselines of Neural UCB 69 and Neural TS (66) as well GP-UCB and GP-TS which use GPs (with the SE kernel) instead of NNs as their surrogate models. The original implementations of Neural UCB (69 and Neural TS [66] are only applicable to discrete domains. So. for a fair comparison in those tasks with continuous domains, we have modified their implementations to maximize their acquisition functions in the same way as our methods (i.e., through combination of random search and L-BFGS-B, refer Appendix F for more details). We firstly explore some interesting insights about our algorithms using a synthetic experiment in Sec. [5.]] Next, we apply our algorithms to real-world AutoML (Sec. [5.2) and RL (Sec. 5.3) problems, as well as optimization task over images (Sec. Finally, we discuss some interesting insights from our experiments in Sec. 5.5) We plot the simple regret (or the best found observation till an iteration) when presenting the experimental results, which is the common practice in BO X (2). We have deferred some experimental details to Appendix [F due to space limitation.
Our code is available at pittpts//// htt///ggttbbbb com wwtp./////donn...aa...a www.aangggsaaaaaaaaeaaaaeeoo.eoe bnts

---

STO-OMIS
STO-SMI-UreP
0.20
1.5
1.5
1.5
1.0
1.0
1.9
Rorgett
0.35
TTo acts Lines
0.5
0.5
0.5
auth
Ooe Fundion
Obeuciiee Fundoon
Oteective Fandion
-0.5/
Accusition Nuecoan
-0.5
Sosueitonn Neecoa
Accuss Ioe Neecia
0.
Itoration
(a)
(b)
(c)
(d)
Figure I: (a-c) Acquisition functions and (d) performances in the synthetic experiment (Sec. 5.1
5.1 Synthetic Experiment
Here, we sample a smooth function from a GP with an SE kernel (with length scale of 0.1), defined on discrete I-dimensional domain within the range of [0, 1]. For all methods, we use an NN architecture with a depth of L = 8 and a width of m = 64 unless specified otherwise.
Figs. [ (a-c) illustrate the acquisition functions f. x: 8.) (line 8 of Algo. I and line 7 of Algo. 2) of different algorithuss. The Deep Ensemble method [36] in Fig. TT can be regarded as a reduced version of our STO-BNTSS algorithm (Algo. I in which the term VVe((x: Bo), b)) (i.e., the second term in line 6 of Algo. T removed. As result, Deep Ensemble does not enjoy the theoretical guarantees of our algorithms (Sec. 4. In Figs. (a-c), given the same training set (red stars), every method constructs a batch of B 100 acquisition functions. E.g., STO-BNTS repeats lines 4-7 of Algo. [ independently for B 100 times to produce acquisition functions fi 0;) for i = .,.... 100, which are plotted as the blue lines in Fig. [p. Note that every acquisition function (blue line) is maximized to select an input query. The figures show that compared with the naive baseline of Deep Ensemble, our STO-BNTS and STO-BNTS- Linear are able to display more exploratory behaviors in unexplored regions (e.g., the interval of [0.2, 0.4]). This may be explained by theoretical guarantees (Sec.p) 4 which imply that both of our algorithms are able to perform exploration in a principled way and hence naturally handle the the exploration-explont exploitaaionn trade-off. Moreover, it has e also been justified by (24) that the addition of the term (Vo fo), 0%) improves the ability of the NN to characterize the uncertainty of predictions, which corroborates our findings here.
The simple regrets of different algorithms are plotted in Fig. 1 The first interesting observation is that our STO-BNTS (orange) significantly outperforms Deep Ensemble (red), which corroborates the insight discussed above positing that the addition of the term (Voj(x; 9o),0) leads to more principled exploration and hence better performances. Due to its lack of exploration as illustrated in Fig. D.. Deep Ensemble fails to reach zero regret in Fig. Td. Furthermore, the discrepancy between the green and purple curves shows that batch evaluations (B = 4) lead to significant performance improvement. Moreover, compared with the green curve for which m = 64, using a wider NN (gray curve, m = 512) substantially improves the performance of STO-BNTS-Linen yet employing shallower NN (yellow curve, m = 16) significantly degrades the performance. These observations agree with Theorem 2 which states that larger width m reduces the regret of STO--NNTS-Lines Similarly, the NN surrogate model of STO-BNTS should also be wide enough since the use of a narrower NN (light blue curve, m 16) also leads a worse performance for STO-BNTS. Lastly, GP-TS (blue) performs competitively in this experiment with a very smooth objective function. However, we will show in the next two sections, in real-world experiments with more complicated objective functions, based methods are consistently outperformed by our algorithms.
5.2 Real-world Experiments on Automated Machine Learning (AutoML)
Here, we adopt hyperparameter tuning tasks. We use tasks involving categorical hyperparameters to highlight the advantage of our NN-based over GP-based methods. We use a diabetes diagnosis dataset to tune categorical hyperparameters of random forest (RF), and then use the MNIST dataset to tune 9 hyperparameters (4 continuous and 5 categorical) of XGBoost and 9 hyperparameters (2 continuous and 7 categorical) of convolutional neural networks (CNNs). Fig 2 plots the results for the RF (a.b) and XGBoost (c.d) tasks, and the results for CNN are shown in Fig. (Appendix F22
"To show the benefit of batch evaluations, in all experiments (including real-world experiments), we use the iterations i as the horizontal axis and in every iteration f, we report the largest f(x)) (yê in roal-world experiments) within a batch (when B > 1) as the observation in this iteration.
7

---

2/0 293 ROAR
23
D1e bouer 2012
12
319 1-2-9-14 1-1
polideeen Emgr
(1) D4T
5.0
15
20
30
40
50
10
20
30
40
50
20
40
65
80
100
20
40
60
80
1.0
Berations
Iberations
Keradion
Iberatoos
(a)
(b)
(c)
(d)
Figure 2: Validation errors for hyperparameter tuning of RF (a.b), XGBoost (c,d). B by default.
1.0
Comuletoe hww.hao
Rown nd
200
0.6
Comuletiv
100
D
Cum
W0..4
Pandor Seath
150
0
100
200
300
400
500
0
100
200
300
400
500
%
100
200
200
400
500
0.0
0
10
20
30
STO B5T5
40
50
(a)
(b)
(c)
(d)
Figure 3: Results for (a) 12-D Lunar-Lander (b) 14-D robot pushing. (c) 20-D rover trajectory
planning, and (d) optimization over images in Sec. 5.4 B = 1 unless specified otherwise.
For each task, we firstly compare the performances of different variants of our algorithms in Figs. 24. c and Fig. Fa, which demonstrate number of interesting insights. Firstly, our STO-BNTS outperforms Deep Ensemble, which is consistent with the results in Fig. TH and further emphasizes the practical significance of the improved exploration performed by our STO-BNTS (Sec. Secondly, STO- BNTS-Linear is significantly outperformed by STO-BNTS in Figs. - and c, which can likely be attributed to its inability to fully leverage the representation power of NNs as we have discussed in Sec. 3 (see more discussions in Sec. 5.5). Next, Figs. с and Fig. F also show that the performance of PTOOBNNS tends to suffer when the NN surrogate model is either overly shallow (T. = 1,
512, orange curves) or overly deep (L = 8, m = 64, red curves), that is, both the orange and red curves underperform significantly in two of the three experiments. This is likely because an overly shallow NN lacks the representation power to model complicated objective functions, whereas an overly deep NN may be prone to overfitting since the size of the training set here is much smaller than typical deep learning applications. In contrast, the NN architecture of L = 2, m = 256 (blue curves) consistently performs well in all three experiments, therefore, we will use as the default architecture in the experiments in the next section. Moreover, the benefit of batch evaluations can also be further confirmed by comparing the blue (B = 1) and green (B = 4) curves in Figs. Dp. c and Fig. 4a.
Figs. bb, d and Fig. 4p show that for the same NN architecture of L. = 2, m = 256, our STO- BNTS is the best-performing method since it performs better than all basclines in Figs. 2p and and comparably with them in Fig. 4p. The undesirable performances of Neural UCB and Neural TS may be explained by the errors due to their diagonal matrix approximation (Sec. D and the underwhelming performances of GP-UCB and TS may result from the ineffectiveness of GP in modeling categorical inputs (more on this in Sec. (.55)
5.3 Real-world Experiments on Reinforcement Learning (RL)
Here we optimize the control parameters of RL problems: we tune d 12 parameters of a heuristic
controller for the Lunar-Lander task from OpenAl Gym 4 d = 14 parameters of controller for a robot pushing task (62], and d = 20 parameters for a rover trajectory planning problem [2]. We 256 for all methods. The results in these three RL tasks are plotted in Figs. 3h
use L 2, and c. Our STO-ENTS and STO-BNTS--Lnea (purple and yellow curves) consistently perform the best among all methods with sequential evaluations (B 1), and our methods with batch evaluations (B= = 4, gray and light blue curves) achieve further performance improvements over their sequential counterparts. Of note, despite underperforming in Sec. Scc.5.2 STO-BNTS- achieves comparable performances with STO-BNTS in all three experiments here for both the sequential and batch evaluations, outperforming the other baselines. The inefficacy of GP-TS and GP-UCB here may result from the inability of GPs to effectively model high-dimensions input space 30 (Sec. 5.5)
8

---

5,4 Optimization over Images
Some real-world applications require optimizing over an input domain of images. For example, an image recommender system sequentially recommends different images to user in order to select the image with the best rating/score [65). In these applications, GP-based BO methods require sophisticated techniques such as convolutional kernels in order to model the inputs of images [59], in contrast, our methods can be easily applied by simply replacing the NN surrogate model with a CNN. Here, we simulate these applications by maximizing score over the domain of images from the MNIST dataset. For all CNN-based methods, we use a CNN with a convolutional layer followed by a fully connected layer (both with m = 64) as the surrogate model (more details in Appendix F.4). The results (Fig. 311) show that our STO-BNTS performs the best. Moreover, when using the same CNN architecture, STO-BNTS-LE BENSS-Linna fails to achieve comparable performances to the other CNN-based methods since STO-BNTS-LAAE Linear is not able to fully leverage the representation power of CNN (Sec.B) 3) However, again consistent with Theorem 2 increasing the width of the CNN can improve the performance of STO-BNTT-Liness to be comparable with STO-BNTS (Fig. 6 in Appendix F.4).
5.5 Discussion
Secs. 5.2 5.3 and show that our algorithms, although without any special design for specific type of problem (e.g., problems involving categorical, high-dimensional or image inputs), are competitive in all these problems thanks to the ability of NNs to model complicated real-world functions. Compared with GP-based BO methods, our algorithms may incur more computation due to the need to train an NN surrogate model. However, the additional computation can be easily overshadowed by the cost of function evaluations since BO is usually used to optimize expensive-1o-compute functions.
STO-BNTS vs. STO-BNTS-Linear Our experimental results have demonstrated some interesting insights on the comparison between our STO-BNTS (Algo. D and STO-BNNS-Linear (Algo. 2 As we have discussed in Sec. [3] since STO-BNTS-Ling Linear is unable to explicitly take advantage of the representation power of NNN. it is expected to be less competitive than STO-BNTS in practice especially in problems where the strong representation power of NNs is crucial for accurately modeling the objective function. Examples of such problems include those with categorical (Sec. (5.2) or image (Sec. inputs. Interestingly, our results in Secs. 3.4indedd corroborate this insight by showing that STO-BNTS-Linear is consistently outperformed by STO-BNTS these experiments. However, note that in such problems, the performance of STO-BNTS--ing improved by further increasing the width of the NN (CNN) as we have shown in Fig. In addition, the practical efficacy of PIO--NTS-LAAE
can be significantly
can also be seen from the experiments in Sec. [.3] in which STO-BNTS- Linear performs comparably with STO-BNTS and consistently outperforms all other baselines. This demonstrates the empirical competence of STO-BNTS-Linea in some real- world problems such as RL. Moreover, also note that compared with STO-BNTS, STO-BNTS-Lineat enjoys the theoretical advantage of having a guaranteed convergence for finite-width NNs (Sec. 4.2)
Baseline Methods. The underwhelming performances of Neural UCB and Neural TS in our ex- periments are likely caused by the errors introduced by the diagonal matrix approximation that is used to avoid the inversion of the p x p matrix (Sec. [ The inadequate performances of GP-UCB and GP-TS may be explained by the ineffectiveness of GPs to model objective functions involving categorical [15] [8] or high-dimensional inputs 30 43), which correspond to the experiments in Secs. and 5.3] respectively. Nevertheless, we expect GP-based methods to achieve better perfor- mances (than their performances here) in problems with lower-dimensional and purely continuous input space (e.g.. GP-TS performs competitively in the synthetic experiment as shown in Fig. It).
Depth L and Width m of the NN Surrogate Model. Our experimental results have provided some guidelines on the choices of the depth L and width m of the NN surrogate model in our algorithms. Regarding the depth L, our experiments
Sec. 5.2 have shown that an overly shallow NN usually hurts the performance due to its lack of expressive power, whereas an excessively deep NN is also likely to deteriorate the performance due to overfitting. Therefore, we discourage the use of NNs which are either exceedingly shallow or overly deep, and recommend shallower NNs for simpler tasks to prevent overfitting and deeper NNs for more complicated tasks to gain enough representation power. The width m should be chosen to be large enough since our experiments in Sec. (.. ( and Sec. 5.4 (Fig. 6 in Appendix [F4] suggest that a larger width usually improves the performance. 256 consistently leads to competitive
Moreover, we have shown that the choice of L 2, performances in a wide range of experiments (i.e., all experiments in Sec. and and Sec. Therefore, recommend it as the default choice for real-world problems.
9

---

6
Related Works
The NTK provides a theoretical tool to study the training dynamics of NNs by drawing connections with kernel methods 5 13 27 38), and it has been successfully applied to number of practical problems such as neural architecture search [52] active learning [6]. data valuation 63 among others. The pioneering work of [69] exploited the theory of NTK to introduce the Neural UCB algorithm for contextual bandits, which uses an NN to learn the reward (objective) function and leverages neural tangent features for exploration following the UCB principle. Neural UCB has been followed up by other works which mainly aimed to make Neural UCB more practical. [64] proposed to improve the computational efficiency of Neural UCB through the additional assumption that the reward function is linear in the feature mapping of the last layer of the NN, (23] also aimed to
reduce the computational cost of Neural UCB by limiting the numher of updates of the NN surrogate model, and [44] proposed method to reduce the memory requirement of generic neural bandit algorithms. The recent work of [41] performed an empirical study of neural bandit algorithms, and discovered that they tend to perform competitively in problems that require learning complicated representations. Above all, the work that is most closely related to our paper is [66]. which introduced the Neural TS algorithm. Following similar principles as Neural UCB, Neural TS learns the reward function using an NN surrogate model and constructs the exploration term through the neural tangent features, which are used as, respectively, the mean and variance of the Gaussian distribution from which the reward sampled for running the TS routine. GP-based BO methods 3 33 49]
have achieved impressive performances in recent years, and have been extended to various problem
settings such as high-dimensional BO 19 26 (30], multi-fidelity BO [14 28 68], meta-BO 10 50), risk-averse BO
46 47 (58), mulli-agent/collabrraiyy BO [9 56). non-myopic BO [34 40)
among others. More importantly, they have also been extended to the batch setting, based on either
GP-UCB 8 16
60) or GP-TS |25 29 45 60)
7
Conclusion
We propose STO-BNTS and STO-BNTS-Lineat both of which sidestep the requirement to invert large parameter matrix in existing neural bandit algorithms, and naturally support batch evaluations while preserving their theoretical guarantees. Both algorithms are asymptotically no-regret under certain conditions if the NN surrogate is infinite-width, and STO-BNTS-Linea still enjoys sub-linear regret for width NN if it is wide enough. A potential limitation is that theoretical analysis for finite-width NNs (Sec. 4.2) only holds for STO-BNTS-Ling
but not for STO-BNTS, which will explore in future works. Another promising future topic is to leverage our ability exploit the strong representation power of NNs to apply our algorithms to other challenging optimization tasks with sophisticated search spaces, such chemical design 22 35), neural architecture search |53555] (55, etc. Moreover, it is also an interesting future direction to extend our algorithms to handle other problem settings such as those which have been considered by BO (Sec. 6 e.g., multi-fidelity optimization [67 68]. risk aversion/fault tolerance 120, 46 47), etc. A potential negative societal impact is that our work may promote more adoption of deep learning methods and hence cause more electricity consumption.
Acknowledgments and Disclosure of Funding
This research/project is supported by A*SRAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Industry Alignment Fund - Pre Positioning (IAF-PP) (Award A A19E4a0101).
10

---

References
[1] Z. Allen-Zhu and Y. Li. What can ResNet learn efficiently, going beyond kernels? Proc. NeurlPS, 2019.
[2] S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. arXiv: 11955, 2019.
[3] S. Balakrishnan, Q. Nguyen, B. K. H. Low, and H. Soh. Efficient exploration of reward functions in inverse reinforcement learning via Bayesian optimization. In Proc. NeurIPS, pages 4187-4198, 2020.
[4] G. Brockman, V. Cheung, L. Pettersson, Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAl Gym. 1xii::660.0114400 2016.
[5] Y. Cao and Q Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Proc. NeurIPS, volume 32, pages 18836-18846, 2019.
[6] T. Chen and C. Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[7] S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. In Proc. ICMI, pages 844-853, 2017.
[8] E. Contal, D. Buffoni, A. Robicquet, and Vayatis. Parallel Gaussian process optimization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 225-240. Springer, 2013.
[9] Z. Dai, Y. Chen, Bayesian optimization for no-regret learning in games. In Proc. ICML, pages 2291-2301, 2020.
Low, P. Jaillet, and T.-H. Ho. R2-B2: Recursive reasoning-
[10] Z. Dai, Y. Chen, H. Yu, B. K. H. Low, and P. Jaillet. On provably robust meta- meta-Bayesian optimization. In Proc. UAI, 2022.
[11] Z. Dai, B. K. H. Low, and Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurIPS, pages 9687-9699, 2020.
[12] Z. Dai, B. K. H. Low, and P. Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NeurIPS, pages 9125-9139, 2021.
[13] Z. Dai, Y. Shu, A. Verma, F. X. Fan, B. K. H. Low, and P. Jaillet. Federated neural bandit. arXiv:2205. 14309, 2022.
[14] Z. Dai, H. Yu, B. K. H. Low, and P. Jaillet. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML, pages 1496-1506, 2019.
[15] E. Daxberger, A. Makarova, M. Turchetta, and A. Krause. Mixed-variable Bayesian optimization.
In Proc. IJCAI, 2020.
[16] E. A. Daxberger and B. K. H. Low. Distributed batch Gaussian process optimization. In Proc. ICML, pages 951-960, 2017.
[17] T. Desautels, A. Krause, and J. W. Burdick. Parallelizing exploration-exxploiaatonn tradeoffs in Gaussian process bandit optimization. Journal of Machine Learning Research, 15:3873-3923, 2014.
[18] A. Deshwal, S. Belakaria, and J. R. Doppa. Bayesian optimization over hybrid spaces. In Proc. ICML, 2021.
[19] D. Eriksson, M. Pearce, J. Gardner, R. D. Turner, and M. Poloczek. Scalable global optimization
via local Bayesian optimization. volume 32, pages 5496-5507, 2019.
[20] X. Fan, Y. Ma, Z. Dai, W. Jing, C. Tan, and B. K. H. Low. Fault-tolerant federated reinforce- ment learning with theoretical guarantee. In Proc. NeurlPS, 2021.
[21] P. I. Frazier. A tutorial on Bayesian optimization. utXiv:1807. .0771022111111 2018.
[22] R.-R. Griffiths and J. M. Hermández-Lobato, Constrained Bayesian optimization for automatic chemical design using variational autocncoders. Chemical science, 11(2):577-586, 2020.
[23] Q. Gu, A. Karbasi, K. Khosravi, V. Mirrokni, and D. Zhou. LcXiv:2102.13025 2021.
Batched neural bandits.

---

[24] B. He, B. Lakshminarayanan, and Y. W. Teh. Bayesian deep ensembles via the neural tangent kernel. In Proc. NeurIPS, 2020.
[25] J. M. Hemúnndez-Lobato, J. Requeima, E. O. Pyzer-Knapp, and A. Aspuru-Guzik, Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space. In Proc. ICML, pages 1470-1479. PMLR, 2017.
[26] T. N. Hoang, Q. M. Hoang, and B. K. H. Low. Decentralized high-dimensional Bayesian optimization with factor graphs. In Proc. AAAI, pages 3231-3238 2018.
[27] A. Jacot, Gabriel, and Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proc. NeurlPS, 2018.
[28] K. Kandasamy, G. Dasarathy. J. Schneider, and B. Póczos. Multi-fidelity Bayesian optimisation with continuous approximations. In Proc. ICML, pages 1799-1808. PMLR, 2017.
[29] K. Kandasamy, A. Krishnamurthy. J. Schneider, and B. Póczos. Parallelised Bayesian optimisa- tion via Thompson sampling. In Proc. AISTATS, pages 133-142. PMI.,, R, 2018.
[30] K. Kandasamy, Schneider, and B. Póczos. High dimensional Bayesian optimisation and bandits via additive models. In Proc. ICML, pages 295-304. PMLR, 2015.
[31] P. Kassraie and A. Krause. Neural contextual bandits without regret. arXiv:2107.03144 2021.
[32] T. Kathuria, A. Deshpande, and P. Kohli. Batched Gaussian process bandit optimization via determinantal point processes. In Proc. NeurIPS, volume 29, pages 4206-4214, 2016.
[33] D. Kharkovskii, Z. Dai, and B. K. H. Low. Private outsourced Bayesian optimization. In Proc. ICML, pages 5231-5242, 2020.
[34] D. Kharkooskii, C. K. Ling, and B. K. H. Low. Nonmyopic Gaussian process optimization with macro-actions. In Proc. AISTATS, pages 4593-4604, 2020.
[35] K. Korovina, S. Xu, K. Kandasamy, W. Neiswanger, B. Poczos, J. Schneider, and E. Xing. Chembo: Bayesian optimization of small organic molecules with synthesizable recommenda- tions. In Proc. AISTATS, pages 3393-3403. PMLR, 2020.
[36] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Proc. NeurlPS, 2017.
[37] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. nature, 521(5533):336444, 2015.
[38] J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. volume 32, pages 8572-8583, 2019.
[39] Z. Li and J. Scarlett. Gaussian process bandit optimization with few batches. In Proc. AISTATS, pages 92-107, 2022.
[40] C. K. Ling, B. K. H. Low, and P. Jaillet. Gaussian process planning with Lipschitz continuous reward functions: Towards unifying Bayesian optimization, active learning, and beyond. In Proc. AAAI, pages 1860-1866, 2016.
[41] M. Lisicki, A. Afkanpour, and G. W. Taylor. An empirical study of neural kernel bandits. In NeurlPS Workshop on Bayesian Deep Learning, 2021.
[42] A. G. G. Matthews, J. Hron, R. E. Turner, and Z. Ghahramani. Sample-then-opiimize posterior sampling for bayesian linear models. In NeurIPS Workshop on Advances in Approximate Bayesian Inference. 2017.
[43] M. Mutný and A. Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. In Proc. NeurIPS, pages 9005 9005-9016. Curran, 2019.
[44] O. Nabati, T. Zahavy, and S. Mannor. Online limited memory neural-linear bandits with likelihood matching. In Proc. ICMI., 2021.
[45] E. Nava, M. Mutny, and A. Krause. Diversified sampling for batched bayesian optimization with determinantal point processes. In Proc. AISTATS, pages 7031-7054. PMLR, 2022.
[46] Q. P. Nguyen, Z. Dai, B. K. H. Low, and P. Jaillet. Optimizing conditional value-at-rist. of black-box functions. In Proc. NeurlPS, pages 41 4170-4180, 2021.
[47] Q Nguyen, 7. Dai, B. K. H. Low, and Jaillet. Value-at-risk optimization with Gaussian processes. In Proc. ICML, pages 8063-8072 2021.
12

---

[48] Q. P. Nguyen, S. Tay. B. K. H. Low, and P. Jaillet. Top-k ranking Bayesian optimization. In Proc. AAAI. pages 9135-9143, 2021.
[49] Q P. Nguyen, Z. Wu, B. K. H. Low, and P. Jaillet. Trusted-maximizens entropy search for efficient Bayesian optimization. In Proc. UAI, pages 1486-1495, 2021.
[50] D. Salinas, H. Shen, and V. Perrone. quantile-based approach for hyperparameter transfer learning. In Proc. ICML, pages 8438-844 PMLR, 2020.
[51] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148 175, 2016.
[52] Y. Shu, S. Cai, Z. Dai, B. C. Ooi, and B. K. H. Low. NASI: Label- and data-agnostic neural architecture search at initialization. In Proc. ICLR, 2022.
[53] Y. Shu, Y. Chen, Z. Dai, and B. K. H. Low. Neural ensemble search via Bayesian sampling. In Proc. UAI, 2022.
[54] Y. Shu, Z. Dai, Z. Wu, and B. K. H. Low. Unifying and boosting gradient-based training-free neural architecture search. In Proc. NeurlPS, 2022.
[55] Y. Shu, W. Wang. and S. Cai. Understanding architectures learnt by cell-based neural architecture search. In Proc. ICLR, 2020.
[56] R. H. Sim, Y. Zhang. B. K. H. Low, and P. Jaillet. Collaborative Bayesian optimization with fair regret. In Proc. ICML, pages 9691-9701, 2021.
[57] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, pages 1015-1022, 2010.
[58] S. S. Tay, C. S. Foo, D. Urano, R. C. X. Leong, and B. K. H. Low. Efficient distributionally robust Bayesian optimization with worst-case sensitivity. In Proc. JCML, 2022.
[59] M. Van der Wilk, C. Rasmussen, and J. Hensman. Convolutional Gaussian processes. In
Proc. NeurIPS, 2017.
[60] A. Verma, Z. Dai, and B. K. H. Low. Bayesian optimization under stochastic delayed feedback.
In Proc. ICML, pages 22145-22167. PMLR, 2022.
[61] Z. Wang, P. Awasthi, C. Dann, A. Sekhari, and C. Gentile. Neural active learning with performance guarantees. Proc. NeurIPS, 34:7510-7521, 2021.
[62] Z. Wang, C. Gehring, Kohli, and S. Jegelka. Batched large-scale Bayesian optimization in nigh-dimensional spaces. In Proc. AISTATS, pages 745-754. PMLR, 2018.
[63] Z. Wu, Y. Shu, and B. K. H. Low. Davinz: Data valuation using deep neural networks at initialization. In International Conference on Machine Learning, pages 2022.
PMLR,
[64] Xu, Z. Wen, H. Zhao, and Q Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv:2012.01788 2020.
[65] S. Zhang, L. Yao, A. Sun, and Y. Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR), 52(1):1-38, 2019.
[66] W. Zhang, D. Zhou, L. Li, and Q Gu. Neural Thompson sampling. In Proc. ICLR, 2021.
[67] Y. Zhang, Z. Dai, and B. K. H. Low. Bayesian optimization with binary auxiliary information.
In Proc. UAI, pages 1222-1232, 1232, 2019.
[68] Y. Zhang. T. N. Hoang, B. K. H. Low, and M. Kankanhalli. Information- multi multi-fidelity Bayesian optimization. In Proc. NIPS Workshop on Bayesian Optimization, 2017.
[69] D. Zhou, L. Li, and Q Gu. Neural contextual bandits with UCB-based exploration. In Proc. ICML, pages 1142--11502 PMLR, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Refer to Section 7
13

---

(c) Did you discuss any potential negative societal impacts of your work? [Yes] Refer to Section 7
(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] Refer to Sections 4.1 and 4.2
(b) Did you include complete proofs of all theoretical results? [Yes] Refer to Appendices
[ D
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] The code is uploaded as part of the Supplementary Material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they
chosen)? [Yes] Refer Appendix [+]
(c) Did you report error bars (e-g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] Refer to Appendix F
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Refer to Appendix
(b) Did you mention the license of the assets? [Yes] Refer Appendix FF
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's 'r
using/curating? [Yes] Refer to Appendix [F]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [Yes] Refer to Appendix FF
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "ssmne1oT7f", "reviewer": "Reviewer_fxmZ", "summary": "The paper proposes two new algorithms named Sample-Then-Optimize Batch Neural Thompson Sampling (STO-BNTS) and STO-BNTS-Linear by combining the Thompson Sampling strategy and the Neural Network (NN) surrogate model. These methods choose the data to be sampled at each iteration by training an NN surrogate model with randomly initialized parameters and then choose the sampled data as the input data that maximizes the trained NN surrogate model. The proposed methods also support the batch settings. Furthermore, theoretical analysis (in particular the regret analysis) is conducted to understand the convergence property of the proposed methods. Finally, experiments are conducted on multiple real-world experiments including the AutoML and Reinforcement Learning tasks to demonstrate the efficacy of the proposed algorithms.", "questions": "•\tHow are the hyperparameters of the NN surrogate models chosen? Is there any guideline on how to choose these values? Do we need to tune these hyperparameters whenever we train an NN surrogate model?\n\n•\tHow is the time cost of the proposed algorithms? And how are they compared to existing baselines like GP-TS and Neural-TS?\n", "limitations": "The paper describes some societal impact of the work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n•\tThe idea of the paper is interesting. I think exploring the research direction of using neural networks as surrogate models in Bayesian optimization is worth to investigate.\n\n•\tThe theoretical analysis is definitely a strength of this paper. It helps to further understand the behaviours of the proposed algorithms. The theoretical analysis is not just built upon existing analysis in the literature but also introduces new techniques that can be useful for future research in this direction (using neural networks as surrogate models). To the best of my knowledge, the theoretical analysis is sound and reasonable (but note that I could not go deeply into the proof in the appendix, I only judge the theoretical analysis based on my overall knowledge about BO's theoretical analysis)\n\n•\tThe experiments conducted are quite comprehensive. They include many real-world benchmark problems. \n\n•\tThe proposed algorithms perform quite well in the benchmark tasks presented in the paper. They are superior to existing baselines.\n\nWeaknesses:\n\n•\tThe writing could be improved. It took me quite a lot of effort to go back and forth to understand the main idea and the theoretical analysis of the paper.\n\n•\tUsing neural networks as surrogate models will certainly help to improve the model's accuracy, however, I'm wondering how the hyper-parameters of these NN surrogate models (e.g., the number of layers, the width in each layer, the learning rate) could be efficiently set. From the experimental results, it shows that the performance of BO depends on a lot in the hyperparameters of the NN surrogate models. Finding an optimal set of hyperparameters seem to create another AutoML problem to be solved.\n\n•\tI would also like to understand more about the time cost of the proposed algorithms, and how they are compared to the time cost of existing baselines. Training an NN surrogate model for every single input query in the batch probably takes a lot of time.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eVL9jY_T-5D", "reviewer": "Reviewer_8ARv", "summary": "This paper presents a strategy for performing Bayesian optimization using neural network. The core idea behind the approach is the observation that training a wide neural network (with a slight modification) using the squared loss leads to a sample from the posterior GP with the NTK kernel, thus being equivalent to Thompson sampling. Using this observation, the algorithm turns out to be very simple: train a neural network on the data observed so far and use it as the acquisition function, which is maximized to select the next point to be observed.\n\nThe proposed algorithms are experimentally evaluated, and shown to work better compared to other baselines including other neural bandit approaches and GP based approaches.", "questions": "How is the performance of the algorithm affected if the unknown function is not sampled from the GP with the NTK kernel, but some other kernel for example a squared exponential kernel?", "limitations": "The proposed algorithm seems quite reasonable and can work is a large variety of settings. I can't think of any major limitation of this approach. A minor limitation is that the computational complexity of the algorithm is not completely alleviated. The complexity of each iteration is linear in the number of observations which is better than GPs (cubic). However, the number of parameters of the neural can be quite large which may ultimately lead to a higher overhead in low dimensional problems.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n- The proposed approach is a much simpler approach compared to past neural bandit approaches, which can be complicated and computationally expensive.\n- It comes with theoretical guarantees. It is shown that the cumulative regret grows sub-linearly when the true function is sampled from a GP with the NTK kernel.\n- Extensive experimental results show that neural network based approaches perform at par or better than GP based approaches for low-dimensional problems.\n- In high-dimensional problems such as with images, neural network based approaches are able to scale where as GP based approaches are not.\n\n**Weaknesses**:\n- The current algorithm assumes that the unknown function is sampled from the a GP with the NTK kernel. This can be a strong assumption in many cases.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UHql54ykP3E", "reviewer": "Reviewer_cYqf", "summary": "The paper proposes a scheme for Thompson sampling based on the neural tangent kernel (NTK). The novelty comes from sidestepping the inversion of the NTK matrix and directly sampling from the equivalent posterior GP using known techniques presented in [14].\nTwo variants of the algorithms are presented, and regret bounds are presented (and proved in the appendix) for both variants.\nAn empirical evaluation is included, demonstrating that the proposed methods (in particular Algorithm 1) compare very favorably to a set of baselines on a range of problems.\n\n", "questions": "\nComments/suggestions/comments:\n\n- l111-126 and Algorithm 1: I find the presentation very unintuitive and difficult to follow as specific equations and choices pop out of nowhere. I'd suggest rethinking the structure and order of presentation; a genric short intro to NTK based on [14] might assist in communicating the key steps and justifications which are only partially provided in Appendix A.  \n-  l111: What does it entail to \"....construct an NN f(x;\\theta)...\" ? I'd suggest adding this step to Algorithm 1 on page 4.  \n- l 192-202 : I am afraid my intuition/understanding breaks down here.... The claim is that a higher B is better; however, this would imply that with B=T we can achieve the same simple regret in a single iteration? I hope the authors can elaborate and perhaps clarify where the bound is practically useful.\n- Figure 2+3. I found reading the figure somewhat tricky due to the split results (figure 2) and reuse of legends for different methods, but I appreciate the difficulty given the number of methods in the comparison. Regardless, I would reconsider how to make the result more accessible.\n- Experiments: I would suggest some discussion/justification on the choice and sensitivity of m and L.\n \nVery minor:\n- line 317 vs line 314, throughout: I'd suggest being consistent if/when writing out small integer numbers (i.e. 3 vs three).", "limitations": "- l391 (final sentence): Personally, I find the final sentence unnecessary, but I appreciate that the authors are trying to meet the formal requirements from NeurIPS. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n \n- The paper addresses a timely problem and is mostly clear except for a few key sections and the use of legends (see question below). \n- The basic algorithms are somewhat incremental considering prior work (in particular [14]); however, the theoretical bounds in the TS setting appear to be a substantial contribution (assuming I have not overlooked mistakes in the proofs, etc.). I am slightly unsure about the interpretation/explanations relating to the bounds, but hopefully, the authors can educate me in their rebuttal (see below)\n- The empirical results are very encorgining on the included set of relevant problems. Rarely do you see any BO consistenly outperform all other baselines, and I hope the results generalize (I'm keen to try these methods out on my own BO problems...).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EbMREVMMjle", "reviewer": "Reviewer_an5h", "summary": "The authors propose two kinds of new Bayesian Optimization (BO) methods in this work. They use the neural tangent kernel Gaussian Process (NTKGP) as the surrogate model and do the neural Thompson Sampling by sampling the initialization of the neural network and optimizing it to get the next query. The major effort of this work is to prove the sublinear regret of their methods, and the experimental results seem promising. ", "questions": "I have the following questions/comments. I am willing to adjust my score further if the feedbacks from the authors make sense to me. \n\nTheorem 1\n\n(a) The proof is based on finite inputs, which still leaves a gap between theory and practice. What is the major obstacle to generalizing this result to the input of the continuous space?\n\n(b) The authors may consider being more precise when discussing the batch size $B$. It is not completely correct that the regret upper bound does not depend on $B$. The constant $C$ is related to $B$. As the authors say in the manuscript, If we want that maximal conditional mutual information to be no larger than $C$, then we cannot set $B$ to a very high value, otherwise the number of initialized points needs to be extremely high. The authors say that when $C=1$, then $T_{init}=\\Theta ((B-1)^{d})$, meaning that even $B=3$ and $d=10$ will make the number of initialized points unaffordable to almost all the BO cases. The last paragraph of section 4.1 will give people a misconception that it will be totally safe however large $B$ is chosen, but think of an extreme case: when $B=T$, I don't think the sublinear regret bound will still hold. \n\n(c) The authors use a result from previous work to bound $\\gamma_{T}$, but as they point out, the input domain condition of that previous work is different from this work. Why do the authors think it is reasonable to borrow that previous result? \n\n(d) Lemma 4, $p-1/t^2<0$ when $t< 5$, making the statement trivial. Also, when $t<5$, it is not true that $1/(p-1/t^2)\\leq 10/p$ (proof of lemma 6). The authors may consider discussing the value of $t$ seperately when $t<5$ and when $t \\geq 5$ (although I don’t think it will affect the final theoretical result). \n\n(e) Proof of lemma 7, is $Y_t$ always integrable? \n\n(f) Minor point: math form (13), (14), some “)” are redundant.  \n\nTheorem 2\n\n(a) It is not convincing to me to have the claim “STO-BNTS-Linear remains asymptotically no-regret as long as the NN is wide enough” based on the result of Theorem 2. That claim means that $\\exists N>0$, s.t, $\\forall m>N$ ($m$ is the width of NN), $\\lim_{T\\to\\infty}\\frac{R_{T}}{T}= 0$ when $m$ is fixed. $N$ can be very large but $m$ should be considered a constant. The result of Theorem 2 gives us some intuition on how to choose $m$ when we know the value of $T$ (but even so, $\\Omega(T^{24})$ is a very loose bound), but it can not give the asymptotically no-regret conclusion for the finite-width NNs. \n\n(b) Math form (26), should the first $=$ be $\\leq$? (the operator norm is a sub-multiplicative matrix norm)\n\n(c) Math form (27), the third $\\leq$ from last is $=$. \n\n(d) Math form (28), the first $\\leq$ is $=$. \n\n(e) Math form (41), the $\\leq$ between $(a)\\leq$ and $(b)\\leq$ is $=$. \n\nExperiments\n\n(a) How to set the value of $\\sigma$ in the loss function?\n\n(b) The authors say that they use L-BFGS-B to optimize NN and get the new query, how does this work when the input domain is discrete/categorical or mixed?\n \n(c) The authors say that they also use L-BFGS-B to optimize the acquisition function of Neural Thompson Sampling. What kind of acquisition function is used here?\n\n(d) What kind of implementation do the authors use for GP-TS and GP-UCB? From my previous experiences, I find that even for the same algorithm different implementations will make a large difference in the results. It makes sense to me that standard GP-UCB and GP-TS cannot deal with categorical inputs well, but I am a little bit surprised that they perform so badly in cases with continuous spaces (Figure 3(a)-(c)). After all, according to the recent developments of high-dimensional BO $d\\leq 20$ is actually not so high-dimensional. \n\n(e) It might not be so fair to compare sequential baselines with STO-BNTS ($B>1$) under fixed iterations. In that case, STO-BNTS ($B>1$) evaluates the black-box function $B$ times as other methods. It would be more reasonable to compare batched STO-BNTS with other batched baselines such as batched GP-TS (under the same batch size). \n\n\n", "limitations": "The authors mention the limitations and potential negative societal impact of their work in the Conclusion section of their manuscript. The authors may consider discussing the limitations of their work in more detail based on the Questions listed above. I don't think this work will have any severe negative societal impact. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Currently, my overall evaluation of this work is positive. Although NTKGP has already been published before, this is the first work to use it in Bayesian Optimization. I think this work provides a new Bayesian Optimization framework that uses a non-standard Gaussian Process as the surrogate and has a theoretical guarantee. The experimental results shown in the manuscript indicate that this new framework has the potential to outperform standard Bayesian Optimization methods in many black-box optimization cases. The proof of theorems seems non-trivial. \n\nI have a couple of questions (including some weaknesses from my perspective) based on the manuscript, and they are listed in the Questions section. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept