Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a Guassian process-based Bayesian optimization algorithm for solving the black-box optimization problems with order-optimal regret guarantee. The main contribution of the paper is in domain-shrinking strategy implemented through tree-based region pruning and focusing on high-performing regions to offer high learning and computational efficiency. 

The paper presents solid theoretical proofs of performance analysis, as well as empirical results on benchmark problems.

main_review: The paper is well-written, clear, and easy to follow. It solves an interesting problem with many potential applications. It is both theoretically sound and includes good empirical studies.

A few comments and questions for potential improvement/clarification of the method:

Section 1.2: an illustration of the general idea (domain shrinking concept) would help in understanding the method. Potentially simply refer to Figure 1.

Figure 1: Extend the caption to explain what is presented in the figure and what each symbol stands for.

Could the algorithm be parallelized to improve the time efficiency?

Only 2 benchmark functions are shown in the results of the paper. More test problems would be appreciated.

limitations_and_societal_impact: Some limitations are already presented in Section 4. However, more discussion on when the method fails or performs worse than other algorithms shown in Figure 4 would improve the understanding of the method.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a GP optimization algorithm under the RKHS setting. The algorithm uses a tree-based domain shrinking approach where elimination, region splitting, and threshold updating are conducted in each epoch. This algorithm achieves a regret guarantee of $O(\sqrt{T\gamma_T})$ and has a low computational complexity of $O(T^4)$.
main_review: This paper is well-written overall and easy to understand. The tree-based domain shrinking strategy presents its novelty over prior works. The nearly optimal regret guarantee is also a highlight. Most of the proofs seem correct and easy to follow. A comprehensive set of experiments shows that the proposed algorithm also performs well empirically. Some suggestions are given in the Limitations section below.
limitations_and_societal_impact: Main comments:
- Related Work: More should be said about other domain-shrinking algorithms that work under general smoothness assumptions, such as SOO — could these potentially also give optimal bounds? Some ideas might even be related to those in algorithms like DIRECT (e.g., splitting the longest edge).
- More importantly, the idea of using a local GP in a small region was already used in [5], and so [5] seems potentially very closely related, but is only mentioned in passing. Please provide a clear comparison in the responses and also in the final paper, both in Section 1.3 and in any relevant technical sections.
- Related Work: The paper "High-Dimensional Experimental Design and Kernel Bandits” (ICML 2021) should also be mentioned, since it gets the same bound as SupKernelUCB but could be more practical (this hasn’t been verified yet)
- It would be better to mention how to construct a discretization in the main paper.
- Around Figure 3 I don’t see an explicit mention of whether $\mu_{s-1}$ and $\sigma_{s-1}$ are computed using all samples so far, or only the ones at the current node — this should be highlighted more clearly, as it seems to be fundamental.
- The proof of Lemma 3 is a bit hard to follow, especially regarding the definition of $\tau_d$, which could be reworded.
- If the authors are claiming optimality, they should make sure that any extra assumptions are consistent with the proofs of the lower bounds.  This should be commented on for Holder continuity and f in [a,b]. Both are consistent based on my understanding.
- The authors mention order-optimality in many parts, including the title. This ignores log factors, but that should be OK because it’s clarified early in the abstract. But another issue is that matching lower bounds are only known for a few kernels, not general kernels. Hence, the phrasing should be more modest to reflect this.
- Figure 4: Can error bars be added?
- Supplementary: Some notation, e.g., $\bar{S}(p)$, can be hard to locate. I suggest giving more reminders throughout, or even a table of notation.

Minor comments:
- Line 41: The phrasing “state-of-the-art regret bound of GP-UCB” is ambiguous, and makes it sounds (incorrectly) like that bound is the best known for any algorithm
- Line 49: Only use phrasing “needs to” for necessary conditions, not sufficient conditions
- Line 100-101: Phrasing “for the general case” isn’t so clear.  You could say “in other cases”, or more specifically mention the Matern kernel.
- In the main text, mention where the proofs can be found
- Line 328: Avoid the unusual phrasing “would have”
- The coefficients in some equations don't seem correct to me, but they don't affect the main result: appendix p9 -- the final step of $R^{(1)}$; appendix p10 -- the final step of $r_t$.
- Typos: appendix p9 -- $gamma_N$; appendix p16 -- additional minus sign in the first line of the second case.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a GP based Bayesian optimization algorithm for regret minimization. This paper uses a domain-shrinking approach where the domain is explored as a tree. Using smoothness assumptions on the true function, it is possible to get upper and lower bounds on the function value in an entire region and this allows the algorithm to decide whether to subdivide a region to explore further or remove it entirely. A key idea and contribution of this work is that the number of leaves in the tree at any one time is a constant. Hence, the total computational complexity of this algorithm is reduced greatly compared to the standard complexity incurred by the famed GP-UCB algorithm. Additionally, the algorithm achieves order optimal performance, closing a gap of \sqrt(\gamma_t) observed in previous work. The paper closes with simple numerical experiments. 
main_review: Strengths: The paper is very well written. The algorithm, which complicated, is clearly stated and easily understood. The theoretical performance is strong as well and the paper closes a known gap. Furthermore, the computational gain is large. 

Weaknesses: Error bars are omitted from the experiments in the main paper and moved to the appendix where they are somewhat large. Presumably this can be fixed by running more repetitions for a final draft. Axis and legend labels on the figures should also be larger to be more legible. Additionally, it is somewhat hard to interpret the experimental results. The results are stated in terms of wall clock time, but no significant discussion of the implementations is given, though this can have a large impact on wall clock performance. Additionally, the theoretical results of this paper state a gain in terms of the regret bound. However, as the results are given for wall-clock time, it is not possible to evaluate this empirically- though this seems like a significant contribution of this paper. 

Other comments and questions: 
-	Saying that the prior is fictitious is somewhat misleading. In terms of implementing the algorithm that is true, but all of the analysis assumes that the prior is real and so does this work.  
-	For the statement of Thm 1, \delta_0 is presumably user provided? Please clarify. 

limitations_and_societal_impact: Not discussed in this paper. Note that the submission guidelines state that a paper being theoretical is not sufficient grounds to claim that there are no societal impacts: https://neurips.cc/Conferences/2021/PaperInformation/PaperChecklist. A proper discussion should be added, though I don’t think anything extensive is needed.
review_title: null

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