- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper considers Bayesian Optimization and proposes the so-called “Probability of Optimality (PO)”, which aims to directly estimate the probability of a candidate being the global optimizer, , under a Gaussian process posterior. Empirically, this probability is estimated by Monte Carlo: draw functions from the GP posterior, take each one's minimizer, and smooth the minimizers into a density (KDE in continuous space). Given that plain PO is too exploitative that can end up cluttering, they propose a Non-Replacement Function Sampling, a rejection sampling that keeps only the sampled functions whose minimum is strictly below the current best (in terms of minimization) observation and use that to form the estimation. The paper also gives an analytical surrogate by using the mean of the truncated normal distribution and shows, asymptotically with noise-free observations, in a compact domain setting, simple regret tends to zero. It also empirically compared with other acquisition functions, and plain PO on synthetic benchmarks and real-world tasks, showing competitive experiments.
Critical strengths
- Clarity: In general the paper is very easy to follow, the idea is simple and seems to be empirically effective.
- The paper provide a thorough literature coverage on similar topic.
Critical weaknesses
Behind the nice (maybe fancy) story, I think the main trick the paper does is essentially a rejection sampling to get rid of the over-exploitation issue of the original PO, which has already be mentioned as a limitation in the Hennig paper and hence, to me, is too straightforward (a.k.a., incremental). Hence, I do not think this work add anything new either in terms of the aforementioned perspective, or any new machinary to BO community (as it is simply sample based KDE estimation). Some other weakness considerations are:
- Inappropriate examples: Although straightforward, I also feel the bucket function example somewhat heuristic, as function space is simply uncountable, which is to me not an appropriate example to mention there.
- The paper does not provide any finite-sample guarantee (which to me seems also non-trivial for the method) for the original .
Questions for authors
I dont have any further questions.
2 comments
Could you please let us know whether our response has fully or partially addressed your concerns? We would greatly appreciate any feedback or clarification you may have. Thank you for your consideration!
We appreciate the reviewer’s comments and acknowledgment of the clarity of our paper and the comprehensive discussion of related studies on acquisition function design. Regarding the remaining concern, we provide the following explanation in the hope that it will clearly address and clarify the reviewer’s concern.
Finite-sample guarantee
By “finite-sample guarantee for the original,” does the reviewer refer to the sampling based NRFS? If so, we agree with the reviewer that establishing a finite-sample guarantee for the sampling based NRFS is indeed non-trivial. This difficulty primarily arises because of the stochasticity in acquisition locations in BO. The number of function samples required is strongly dependent on both the dimensionality of the design space and the landscape of the objective function, with the latter being particularly difficult to characterize in a black-box setting.
Nevertheless, our non-replacement sampling strategy, conditioned on xf∗∗∈/Xn, ensures that previously evaluated locations are excluded from subsequent optimizer sampling. Consequently, in practical applications with a prescribed minimum resolution of the design space, the method has the finite-sample convergence guarantee. However, its convergence speed remains difficult to predict, unlike the analytical NRFS without stochasticity, for which we provide a convergence rate in Appendix A.2.4.
Inappropriate examples
Regarding the concern about the example, the bucket concept is mathematically defined in (1), so we think that the uncountability of the function space has no conflict with this definition, since a bucket serves as a categorical representation and can naturally contain an uncountable number of functions. Nevertheless, we would appreciate it if the reviewer could kindly elaborate on why this example may give readers a heuristic impression, so that we can better understand the concern and revise the presentation accordingly.
Incremental study
The core idea of NRFS is to focus on the uncertainty of the objective function given all the observations, and estimate the corresponding acquisition function under iteratively updated functional uncertainty to guide BO more effectively. An important new contribution of this work is, when estimating functional uncertainty for acquisition function design, we should account for function samples that have the possibility of representing the true objective function. To the best of our knowledge, this perspective has not been explored in previous studies, making our work conceptually distinct.
As a minor clarification, Hennig's original work does not directly use the probability of optimality as an acquisition function. Rather, it first discusses the local trapping issue of EI and PI and proposes Predictive Entropy Search (PES) to improve exploration by estimating and reducing the entropy of the optimizer distribution. Since entropy estimation and direct sampling from the optimizer distribution are fundamentally different approaches, we believe our work is conceptually distinct from Hennig's original method.
Technically, our strategy is not applying rejection sampling for acquisition function estimation. Rather, our strategy focuses on the set (bucket) of candidate objective functions which are possible to be the true objective function given all the observed queries. When estimating the acquisition function, conditional sampling is implemented within the set (bucket), avoiding sampling functions which are not possible to be the true objective, instead of randomly sampling functions from the typical GP surrogate class as done in existing BO methods.