Optimizing Posterior Samples for Bayesian Optimization via Rootfinding

Authors: Taiwo Adebiyi, Bach Do, Ruda Zhang
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: Bayesian optimization, global optimization, acquisition function, Thompson sampling

Abstract:
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 sample paths, especially in higher dimensions. We introduce an efficient global optimization strategy for posterior samples based on global rootfinding. It provides gradient-based optimizers with two sets of judiciously selected starting points, designed to combine exploration and exploitation. The number of starting points can be kept small without sacrificing optimization quality. Remarkably, even with just one point from each set, the global optimum is discovered most of the time. The algorithm scales practically linearly to high dimensions, breaking the curse of dimensionality. For Gaussian process Thompson sampling (GP-TS), we demonstrate remarkable improvement in both inner- and outer-loop optimization, surprisingly outperforming alternatives like EI and GP-UCB in most cases. Our approach also improves the performance of other posterior sample-based acquisition functions, such as variants of entropy search. Furthermore, we 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.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1729330434799

thread_type:
official_review

<thread_object>
creator: reviewer_akky

<content>
summary:
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.

strengths:
* 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

weaknesses:
* 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.

questions:
* 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)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730099075024

thread_type:
official_review

<thread_object>
creator: reviewer_kcrq

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730513783041

thread_type:
official_review

<thread_object>
creator: reviewer_d2as

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730790457798

thread_type:
official_review

<thread_object>
creator: reviewer_mhus

<content>
summary:
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.

strengths:
-	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.

weaknesses:
-	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.

questions:
-	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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732502584182

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Changes to the paper

comment:
After considering the initial reviewer comments,
we have carefully made the following changes to the paper:

- New algorithmic box for the proposed `TS-roots` method (Algorithm 1).
- Revised `minsort` algorithm allowing _exact_ subsetting of prior local minima (Algorithm 4).
- New analysis on the computational complexity of `TS-roots` (Appendix C.5).
- New analytical result on the number of local minima of a separable function (Appendix A.2)
- New empirical results on the effect of set sizes $n_o, n_e, n_x$ on optimization accuracy
  (Appendix D).
- New empirical result on the out-loop performance of TS-roots in real-world problem
  (Section 6 paragraph "Optimizing Real-world Problem"; and Appendix G)
- New empirical result on gradient-based multistart optimization using
  two other initialization schemes: uniform grid and Latin hypercube sampling.
  (Appendix I paragraph "Comparison of Inner-loop Optimization Results")
- Further explanation of the pathwise conditioning representation of GP posterior (Wilson et al., 2020; 2021), which is an important building block of our proposed TS-roots method.
- New discussion on the log transform of acquisition function
  (Section 5 paragraph "Optimization of Acquisition Functions")
- Clarifications on: contributions of the paper; the `TS-roots` algorithm;
  improvement in the performance of MES; spectral representation of a separable GP prior;
  computational complexity of the `roots` algorithm;
- Move the description of Sample-Average Posterior Function to a new section (Section 4).

Changed text are highlighted in blue in the revised manuscript PDF.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This study proposes a novel method for the global optimization of acquisition functions by optimizing sample paths generated from the posterior distribution of Gaussian processes (GPs). The key feature of this method is its utilization of the decoupled representation of the GP posterior. By leveraging this decoupled framework, the proposed method provides a systematic algorithm based on gradient optimization that promotes the use of multiple initial points.　A potential weakness is the assumption of separability. However, as the authors point out, this assumption is satisfied by the squared exponential kernel and can be met for the Matérn kernel with appropriate adjustments, making it unlikely to pose a significant practical limitation.
All reviewers have acknowledged the significant contributions of this paper, and numerical experiments further demonstrate its utility. Therefore, I believe this work is valuable to the community and recommend acceptance.