Venue: NeurIPS 2022 Conference

Reviews:

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 targets multiple problems. First, it develops the theoretical analysis (in particular the regret analysis) for the existing BORE framework by Tiao et al [9], helping to understand BORE's convergence property. Second, it addresses the non-convergence issue of BORE by proposing the method BORE++ which improves the uncertainty estimates combining with using an upper confidence bound (UCB) on the predicted class probabilities as the acquisition function to improve the convergence property. Finally, the paper proposes the batch BORE method along with its theoretical convergence analysis. Some numerical experiments are conducted to assess the theory developed and to compare the performance of the proposed batch BORE method with existing baselines.
strengths_and_weaknesses: Strengths:

•	The paper is very well-written and clear. The proposed methods, the theoretical analysis and the discussion regarding the theoretical analysis are very well presented.

•	The theoretical analysis for the BORE framework, the BORE++ method and the batch BORE method is very interesting. To the best of my knowledge, the analysis seems to be correct. The techniques used are new and can inspire future research works. I know these are difficult problems to perform theoretical analysis. I also like the fact that the paper tries to explain the impact of the theoretical analysis and discuss some assumptions used in the theoretical analysis.

•	Although limited, I also like that the paper tries to perform an experiment to assess the theoretical analysis.


Weaknesses: In general, to me, the experiments are a bit weak/limited. Please find the detailed comments as follows.

•	Experiments are only conducted to compare the proposed Batch BORE method with existing baselines, and very limited experiments are conducted to compare the performance of BORE++ over baselines (e.g., BORE or GP-UCB).

•	For the experiments that compare the proposed Batch BORE method with existing baselines, only synthetic objective functions are used, there are no real-world problems.

questions: Apart from some comments mentioned in the Weaknesses section which the authors can response, I also have the additional following questions:

•	In Section 7.1, Theory Assessment, when assessing the theoretical results of the proposed method BORE, BORE++ and GP-UCB, I'm just wondering what are the values of some parameters in these algorithms such as beta_t, L_{epsilon}, etc.? I saw that in the appendix, the experiment setup is described in detail, however, I couldn't find the information regarding some parameters listed in the previous sentence.

•	I would love to understand more about the performance of BORE++ versus BORE, in particularly for more objective functions.

limitations: Yes, the limitations are described.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes an extension of BORE, BO based on the direct density-ratio estimation, and its regret analysis is also provided. The authors first derived a regret bound for the original BORE and mentioned a problematic term remains. Based on this observation, a UCB based extension, called BORE++, is proposed, and the authors revealed BORE++ has the same good regret convergence as the original GP-UCB.
strengths_and_weaknesses: The paper is well-organized and easy to follow regardless of its technical complexity.

Overall, I think that the regret analysis of this paper is informative for the community. The consequence is interesting (BORE has a problematic term and BORE++ can avoid it).

Empirical evaluation is a bit weak. It only shows the batch setting, though BORE++ would be a novel acquisition function even for the non-batch setting. More comprehensive evaluation with a standard acquisition functions would have been convincing.
questions: [1] In BORE++, how is \sigma_t(x) in (23) estimated? It is seems described in 5.1 (empirical quantile), but I missed, in the end, which uncertainty estimation is employed, and how it affects the theoretical guarantee?

[2]
> Therefore, batch BORE++ should be able to achieve better performance than BORE++ while running the same number of function evaluations.

This is a bit counter-intuitive for me. In general, for each one of decision makings, the non-batch model can use a larger number of observations (The batch model can only use t observations during determining next M observations, while the non-batch model can gradually increase observations (e.g., to observe M-th observation, it can use t+(M-1) observations)). Therefore, the claim that the batch model achieve better performance than the non-batch model by the same number of observations is a bit surprising for me. Could you explain its rationale in more detail?
limitations: I could not find clear descriptions about current limitation.
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 paper provides a regret analysis of previous work which re-formulated Bayesian optimization with expected improvement as optimization over the input space of a discriminative classifier (BORE). Assuming the discriminator $p(y \le \tau | x)$ is a member of a reproducing kernel Hilbert space (RKHS) allows modeling the discriminator using kernel least squares which in turn yields a high probability bound on the discriminator error. From this, bounds on instantaneous and cumulative regret follow. The paper then addresses BORE's potential for a non-vanishing cumulative regret by proposing a UCB-like variant BORE++ which achieves vanishing regret. Then, a batch variant of BORE++ utilizing Stein variational gradient descent is introduced, along with regret analysis, and synthetic and real-data experiments are conducted.
strengths_and_weaknesses: Originality

* The paper mostly appears to utilize previous results in Gaussian process-based Bayesian optimization, online learning, and an approximate inference guarantee in its development. In this sense, the technical contributions seem somewhat incremental.

Quality

* The experimental setup oddly doesn't include non-batch BORE++ which is a primary contribution of the paper. 

* For a batch method, I was a little underwhelmed by the experimental results. However, I do want to commend the authors for including two cases where the proposed method isn't the clear winner. 

Clarity

* The paper was generally very clear and easy to follow. 

* The authors might consider moving the SVGD description (sec 3.4) to the description of the batch alg (sec. 6) since it is not relevant prior to this point.

Significance

* Had the experimental results been more thorough and clearer, the paper's impact might have been higher. Given that BORE is fairly recent and not very prevalent as a standard tool in BO, the significance of guarantees is maybe a question.
questions: * Does the result of theorem 3 only apply when the true $\pi(x)$ is in the RKHS associated with the least-squares kernel?

* How does the performance of BORE++ compare on standard benchmarks to other non-batch BO methods? Particularly, how does it compare to BORE wrt/ the experiments included in the original BORE paper?

* The batch BORE++ guarantee relies on the Lipschitz constant $L_\pi$ being bounded away from zero. However, this appears at odds with a decreasing $\tau$ value to better identify the global minimum. Is there an adaptive schedule for $\tau$ that can retain vanishing regret while locating the optimum?
limitations: There wasn't any discussion that I saw on the limitations of the BORE++ variants or potential negative societal impacts. For the former, some qualitative discussion of which black-box optimization settings BORE++ is preferable / not preferable to standard BO with EI would help.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper presents BORE++ which improve uncertainty quantification over BORE. They present theoretical guarantees for the regret under certain conditions.
strengths_and_weaknesses: The related work section is short and should be more elaborate. The authors could consider placing it after the background section, where it should be easier to elaborate pointing to that section.

Theorem 1 is for pi which is not a valid classifier. Can we say anything about the case where pi optimal with the cross-entropy loss?

How should I relate the bounds in Theorem 2 to GP-UCB with some kernels, when BORE does not have any kernel choice? Are these new bounds for BORE (with no kernel), or just the "usual" GP-UCB bounds in a new language?

Can the authors explain that GP-UCB and BORE++ are fundamentally different? Phrased another way: if we use PLS classifer (as in 5.2), are they two parameterizations of the same mechanism?

The authors explain that BORE can be more flexible because no kernel or GP is needed. From my reading all theoretical guarantees assume a kernel on pi. 

Figure 1 needs more ticks on y-axis. 

In general, the experimental section of this paper does not allow any conclusion to be drawn from it. It lacks in both width and depth.

This is a theoretical paper, but I am to be convinced by the authors that the contribution is substantial to the literature. Specifically, the authors should clearly state that the conditions they prove under are different from GP-UCB.

questions: Is BORE Bayesian? I understand that BORE follows the same sequential updating scheme as Bayesian optimisation. I struggle to see there is any prior in algorithm 1. So is BORE actually Bayesian or is it just probabilistic? 

Following up on this question, if there is no reversion to the prior: how does BORE ensure a trade-off between exploitation and exploration? Question out of curiosity. (I see you discuss this in lines 121-123 too)

"Bayesian neural networks [42], random forests [43], dropout methods, etc. [44], also constitute valid approaches for predictive uncertainty estimation." Can you elaborate what valid means here?

limitations: There are no immediate societal impacts to be discussed in this paper.
review_title: null

Meta-review: metareview: This paper provides a theoretical analysis of the regret for the BORE framework and addresses existing issues with a BORE++ method that provides uncertainty quantification in the estimation of the classifier. An analysis of BORE++ is also presented alongside an exploration of the batch Bayesian optimization setting.

Reviewers appreciated the theoretical analysis provided in the paper as well as the explanation of the theoretical results and the assumptions needed for those results to hold. Several reviewers expressed the main weaknesses were the empirical analyses in the paper, including the results focusing on the batch case. However, after the rebuttal and revision, several reviewers felt like the additional results were convincing enough to recommend acceptance for this work. 

Please use the extra page to finish addressing the remaining comments of the reviewers. Some additional points to keep in mind include: 1) the related work section could be expanded to include more literature as well as the context in which the current work relates to the work cited; 2) the figures could be improved to be easier to read, e.g., by increasing font sizes. 
confidence: Less certain
Decision: Accept