Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

•	The 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.

•	The 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)

•	The experiments conducted are quite comprehensive. They include many real-world benchmark problems. 

•	The proposed algorithms perform quite well in the benchmark tasks presented in the paper. They are superior to existing baselines.

Weaknesses:

•	The 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.

•	Using 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.

•	I 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.

questions: •	How 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?

•	How is the time cost of the proposed algorithms? And how are they compared to existing baselines like GP-TS and Neural-TS?

limitations: The paper describes some societal impact of the work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The proposed algorithms are experimentally evaluated, and shown to work better compared to other baselines including other neural bandit approaches and GP based approaches.
strengths_and_weaknesses: **Strengths**:
- The proposed approach is a much simpler approach compared to past neural bandit approaches, which can be complicated and computationally expensive.
- 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.
- Extensive experimental results show that neural network based approaches perform at par or better than GP based approaches for low-dimensional problems.
- In high-dimensional problems such as with images, neural network based approaches are able to scale where as GP based approaches are not.

**Weaknesses**:
- 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.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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].
Two variants of the algorithms are presented, and regret bounds are presented (and proved in the appendix) for both variants.
An 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.


strengths_and_weaknesses: 
 
- The paper addresses a timely problem and is mostly clear except for a few key sections and the use of legends (see question below). 
- 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)
- 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...).
questions: 
Comments/suggestions/comments:

- 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.  
-  l111: What does it entail to "....construct an NN f(x;\theta)..." ? I'd suggest adding this step to Algorithm 1 on page 4.  
- 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.
- 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.
- Experiments: I would suggest some discussion/justification on the choice and sensitivity of m and L.
 
Very minor:
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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. 

I have a couple of questions (including some weaknesses from my perspective) based on the manuscript, and they are listed in the Questions section. 
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. 

Theorem 1

(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?

(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. 

(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? 

(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). 

(e) Proof of lemma 7, is $Y_t$ always integrable? 

(f) Minor point: math form (13), (14), some “)” are redundant.  

Theorem 2

(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. 

(b) Math form (26), should the first $=$ be $\leq$? (the operator norm is a sub-multiplicative matrix norm)

(c) Math form (27), the third $\leq$ from last is $=$. 

(d) Math form (28), the first $\leq$ is $=$. 

(e) Math form (41), the $\leq$ between $(a)\leq$ and $(b)\leq$ is $=$. 

Experiments

(a) How to set the value of $\sigma$ in the loss function?

(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?
 
(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?

(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. 

(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). 



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.
review_title: null

Meta-review: metareview: The authors introduced two asymptotically no-regret neural Thompson sampling algorithms. They derived regret upper bounds and showed that they are asymptotically no-regret under certain conditions. They verified their empirical effectiveness with AutoML and reinforcement learning experiments.
All reviewers liked this paper. Please note however, that it is somewhat surprising that in some cases that standard GP-UCB and GP-TS competitors performed very badly. One of the reviewers reproduced the Lunar-Lander experiments in BoTorch and achieved much better performance for these competitor methods.

confidence: Less certain
Decision: Accept