Optimizing Posterior Samples for Bayesian Optimization via Rootfinding
Bayesian optimization;global optimization;acquisition function;Thompson sampling
Yes
No ethics review needed.
-	There are also other works addressing the issue on mostly-flat acquisition functions (stated by authors in line 49). One of the notable approaches is to compute log of acquisition values, which has been shown to mitigate the flatness problem. One example is a recent work [1], which combines previous similar attempts into a systematic solution, the logEI acquisition function. Can the authors comment on this log approach? For example, how about computing log acquisition values + random multi-start for gradient solver?

[1] Ament, Sebastian, et al. "Unexpected improvements to expected improvement for bayesian optimization." Advances in Neural Information Processing Systems 36 (2023): 20577-20612.
-	The paper addresses the problems of finding the global optimum of GP posterior samples efficiently, which is an important topic for many BO acquisition functions.
-	There are many empirical analyses for the proposed methods.
-	The method significantly reduces the CPU times to optimize GP-TS compared against genetic algorithm and random multi-start.
-	The method can be a robust choice for general problem – TS-root performance is the most robust among other baselines, despite only being on par with the best baselines in each problem.
The paper proposes a method for optimizing the sample paths generated by GP posterior. The method, TS-root, globally optimizes the posterior samples via gradient-based multi-start optimization. 
Specifically, TS-root can provide the gradient-based solver with a set of starting points accounting for exploration and exploitation, thereby finding the global optimum of posterior sample more efficiently. This starting point set S is discussed in section 3.1. Basically, S consists of exploration set S_e and exploitation set S_x. As S_x is a subset of observed data points satisfying eq (4), the number of points n_x can be small (hence easy to find, I think?). However, the set S_e is a n_e subset from the set S_0 of n_0 prior sample local optimum, and because n_0 can be larger, especially in high dimensions, finding S_e is non-trivial, which is discussed in Section 3.4 and 3.5. The main focus of the paper is to compute set S_e.

Another important component of TS-root is that it does not follow the conventional representation for GP posterior, and instead adopt the Decoupled form of GP posterior. This technique was presented in Wilson et al., 2020. The main idea of this decoupled form is to reduce to computational cost of conventional GP posterior, while maintaining similar predictive performance.
-	The contribution is fair, as the main contribution seems to be computing the starting points for gradient-based optimization process. The decoupled representation for GP posterior was proposed by previous works.
-	The idea seems to not very effective in improving MES acquisition function. Fig. 5 shows that TS-Random Fourier and TS-root are statistically similar.
-	No real-world benchmark problems.
Yes
No ethics review needed.
1. The author describes the computational complexity of the algorithm in the appendix. It seems that finding local optimizers of the prior sample path is of O(m^2). It seems that this additional computational cost may be a bit of problematic in high(or even moderate) dimension, where you need more initial locations to optimize the inner acquisition function. Can you provide some computational efficiency comparison with other existing methods (based on LHS or uniform grid) to perform posterior sample path based acquisition function optimization?

2. Rather subtle question I have is, the robustness of the separability assumption on Kernel. It seems that if one is only interested in characterizing the optimum, utilizing the separable kernel instead of standard ones (like standard Matern Kernel) is sufficient for describing the geometry near the optima. Can you comment a bit on the necessity of the separability assumption for Kernel, besides the implementation or computaion aspect?
The paper delves into a problem that's important in Bayesian optimization but less understood, namely the effect or efficient strategy of optimizing the acquisition function. As the paper said, many (almost all) Bayesian optimization methods assume the exact inner optimization solution, which can be very difficult in practice. The authors provide a systematic way to come up with a starting point to facilitate existing multi-start gradient-based optimization strategies in acquisition functions. The effectiveness of this strategy and improving the existing sample path based acquisition function strategy looks impressive.
The paper proposes a new methodology to optimize acquisition functions based on posterior sample paths. By judiciously selecting initial starting points, the proposed method makes a gradient-based multi-start strategy an appealing technique for optimizing the acquisition function. The effectiveness of the proposed methods has been demonstrated in multiple examples and comparisons with other existing methods are provided.
No major weakness. The paper is clearly written, except for the part where it describes the starting point for the inner acquisition optimization task. It seems that there are some inconsistencies between descriptions and notations between lines 142-161 on page 3. 1) I suggest authors revise this part to enhance the clarity of the method. 2) Furthermore, having an algorithmic box description would help readers gain the gist of the proposed method.
Yes
No ethics review needed.
1. There are some hyperparameters, e.g., n_o, n_e, n_x, that control the balance between exploration and exploitation. Given a specific optimization problem to be resolved, how to specify appropriate values for these hyperparameters? Is there any thoretical or empirical guidance?

2. The proposed method is claimed to be able to find the global optimum of the aquisition functions in a scalable way. Is there a theoretical guarantee?  It seems that the performance of the posterior sampling procedure plays a key role for the follow-up root finding based global optimum searching procedure. Is the posterior sampling procedure scalable to higher dimensions? As far as we know, posterior sampling of a high dimensional parameter space is much more challenging issue to be resolved. If this procedure only yields low quality samples, how to guarantee that the proposed method here can work well?
1. This paper selects an uncommon topic of BO, namely global optimization of acquisition functions, and conduct a systematic research on it.
2. The paper proposes a novel strategy that uses root finding to search the global optimum of the acquisition functions, and evaluates it by numerical experiments.
This paper focuses on global optimization of acquisition functions in the framework of Bayesian optimization (BO). The common practice of BO is to utilize routine algorithms, such as dividing rectangles (DIRECT),  covariance matrix adaptation evolution strategy (CMA-ES), and Thompson sampling (TS), to solve the acquisition function optimization problem. The authors here propose to leverage root finding procedures to improve/accelerate optimization of posterior sample-based acquisition functions. The basic idea is to select a subset of posterior samples as the starting points to conduct gradient-based root finding for searching local minima of the acquisition function. The global optimum is obtained by ranking the local optima. The performance of the proposed methods is evaluated by comparison with some standard BO algorithms on several benchmark testing functions.
1. The premise for that this paper is an important contribution to the community is that global optimization of acquisition functions is really necessary for guaranteeing BO's performance. Unfortunately this is not proved or even discussed in the paper. Is it worth to develop more complex algorithms which consume more computations to optimize the acquisition function? Is this better than we using the same resource to build a better surrogate model to approximate the objective function? Why the community paid more attention to the latter issue? It's likely because it plays a more important role for BO's performance.   

2. As shown in Figure 2, for some cases, the proposed method, TS-roots, performs better than othe competitors; while for the other cases, it just performs on par with or even worse than the standard commonly used baseline BO methods. In addition, only several simple benchmark test objective functions are involved in the experiments. Combining the above two points, the experiment results don't provide enough evidence for that the proposed solution can bring remarkable benefits for solving challenging real-life problems.
Yes
-
No ethics review needed.
* Is the method also applicable to Entropy Search [1]? The paragraph (l. 54-63) in the introduction mentions many information-theoretic acquisition functions besides this one and Entropy Search is arguably one of the main/first such acquisition functions. 

[1] Entropy Search for Information-Efficient Global Optimization (Hennig and Schuler, 2012)
* The method is motivated well (Section 3.2)
* The method performs better than (or at least on-par with ) the baselines empirically. 
* I think it is good that also the outer-loop performance is tested.  At the first sight, I was wondering whether a potentially slight improvement in the inner loop would really matter for the final performance, but now I am more convinced that it does.
* Figure 1 is very useful
The paper is about improving the inner-loop in Bayesian Optimization methods that rely on optimization of posterior samples. This is done by selecting better starting points for the gradient based optimization of the posterior samples. The set of starting points is made up from a subset of the local minima of the prior and the local minimal of the posterior mean function (the subset where the posterior values are highest, respectively). The empirical performance of the method is assessed on common benchmark functions.
* For me, a bit more explanation on the decouple representation of GP Posteriors would have been useful. There is a reference to Wilson et al. 2020, but if one is not familiar with that particular piece of work, a bit more explanation on the decouple representation of GP Posteriors would have been useful. In particular, because this representation later on is key in the construction of the method. 
* I think it would be nicer to either have Figure 8/Figure 9 from the Appendix near the "Sample-Average Posterior Function" Section. Or maybe even have the "Sample-Average Posterior Function" Section in the methods part instead of the results part? Otherwise, I reads more like an afterthought.
@inproceedings{
anonymous2024optimizing,
title={Optimizing Posterior Samples for Bayesian Optimization via Rootfinding},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=I6UbnkUveF},
note={under review}
}
Bayesian optimization devolves the global optimization of a costly objective function to the global optimization of a sequence of acquisition functions. This inner-loop optimization can be catastrophically difficult if it involves posterior samples, especially in higher dimensions. We introduce an efficient global optimization strategy for posterior samples based on global rootfinding. It provides gradient-based optimizers with judiciously selected starting points, designed to combine exploitation and exploration. The algorithm scales practically linearly to high dimensions. For posterior sample-based acquisition functions such as Gaussian process Thompson sampling (GP-TS) and variants of entropy search, we demonstrate remarkable improvement in both inner- and outer-loop optimization, surprisingly outperforming alternatives like EI and GP-UCB in most cases. We also propose a sample average formulation of GP-TS, which has a parameter to explicitly control exploitation and can be computed at the cost of one posterior sample.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Bayesian optimization global optimization acquisition function Thompson sampling
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/8f152a8675fdd6725e9d58180e58d72e01eacefd.pdf
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Optimizing Posterior Samples for Bayesian Optimization via Rootfinding
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission