Scalable Bayesian Optimization via Focalized Sparse Gaussian Processes

Thanks for your appreciations of our problem setting and algorithm design. We address your concerns below. Please find the rebuttal Figures by opening the rebuttal PDF file.

Baselines comparison

In Figure R4, We run the "keep closest N TuRBO" baseline (denoted as NN GP TuRBO) on both robot morphology design and human musculoskeletal system control task, and find that FocalBO consistently outperforms this simple baseline. Thanks to reviewer SUei, we find that FocalBO also outperforms original TuRBO implementation on both high-dimensional benchmarks. The reason of TuRBO's poor performance may be that it cannot quickly adapt over the search space when the online evaluation budget is small.

In terms of the statement in section 5.2, we find that there is no statistically significant difference between FocalBO and the best performing algorithm reported in Design Bench baselines (p value=0.1168). We will extensively compare the optimization performances against MBO baselines in the new version.

The design of $\mathcal{L}_{\text{reg}}$

Indeed, the -1 does not affect the loss, and is primarily for illustrative purposes. Specifically, we can write

$L_{\text{reg}} = \frac{ \sum_{i=1}^t w_i - |X \in S_{c,l}| }{ |X \in S_{c,l}| }$ $= \frac{ \sum_{i=1}^t w_i -\sum_{i=1}^t 1_{x\in S_{c,l}} w_i }{ \sum_{i=1}^t 1_{x\in S_{c,l}} w_i } = \frac{ \sum_{i=1}^t 1_{x\notin S_{c,l}} w_i }{ \sum_{i=1}^t 1_{x\in S_{c,l}} w_i }$

which motivates the regularization term as minimizing the weights of points outside of the search region, while normalizing by the size of the search region (to account for decreasing search region sizes in FocalBO).

ELBO statements

Thanks to pointing out the confusing loss description - it's a typo on our end. We actually maximize the weighted data likelihood term and minimize the regularization term, therefore $\mathcal{L}_{\text{reg}}$ should be multiplied by $-1$. We will unify the definitions to the ELBO description to reduce confusion.

Limitations of our work

While FocalBO demonstrate superior performances against existing scalable BO algorithms, theoretical can be further improved to make it more rigorous. For instance, an analysis of the convergence of FocalBO would enhance our understanding of the algorithm’s mechanism. The currently-used hypercube search region may not align well with the underlying function landscape, potentially wasting computational resources on low-performing regions. A more sophisticated search region design such as [1] may help FocalBO to further improve the optimization performance.

[1] Wang, Linnan, Rodrigo Fonseca, and Yuandong Tian. "Learning search space partition for black-box optimization using monte carlo tree search." Advances in Neural Information Processing Systems 33 (2020): 19511-19522.

Thank you for your appreciation of this work! We address your question below. The rebuttal figures can be found by opening the rebuttal PDF file.

Better way to center the search region

A plausible alternative would be to instead center the search region at the maximum of the chosen acquisition function. We empirically investigate this in Figure R1 (a), which compares different ways of selecting the search region center by measuring the distance from the search region center to the global optima. We observe that current best point consistently is the closest to the global optimum, which validates this design choice.

For the experiment above, we sampled 2d functions from GPs with Matern $\frac{5}{2}$ kernel and lengthscale of 0.05 (representing rigid functions), and selected the best point over unifromly sampled 10,000 points as the global optima.

A sparse GP is already more explorative than using the full GP, since the smaller representational capacity leads to smoother posteriors. We demonstrate this empirically in Figure R1 (b), where we measure the pair-wise distance of 100 Thompson sampling points under exact and SVGP (with 50 inducing points). We observe that sparse GP actually samples more diverse sets compared to exact GPs, i.e. exhibiting more exploration. Therefore, using focalized GPs does not sacrifice exploration, and significantly helps exploitation by performing acquisition function optimization over smaller search regions.

Regarding Figure 3, we believe that the better performance of "FocalBO TuRBO" may be because utilizing trust regions helps FocalBO to better exploit at early optimization depths, leading to faster convergence with limited evaluation budgets.

Limitations of our work

While FocalBO demonstrate superior performances against existing scalable BO algorithms, theoretical can be further improved to make it more rigorous. For instance, an analysis of the convergence of FocalBO would enhance our understanding of the algorithm’s mechanism. The currently-used hypercube search region may not align well with the underlying function landscape, potentially wasting computational resources on low-performing regions. A more sophisticated search region design such as [1] may help FocalBO to further improve the optimization performance.

[1] Wang, Linnan, Rodrigo Fonseca, and Yuandong Tian. "Learning search space partition for black-box optimization using monte carlo tree search." Advances in Neural Information Processing Systems 33 (2020): 19511-19522.

The rationality of FocalBO design

FocalBO has two main components: the focalized GP and the hierarchical acquisition optimization. In the clarification of the regularization term, we have explained that the scaling is used for maintaining similar scale for similar size of search regions, and our emprical evaluation demonstrate the rationality of our loss function design. Below we give some empirical results and the intuition in the design of hierarchical acquisition optimization.

After each BO iteration, we use a simple yet effective heuristic to adjust the optimization depth for the next round, without introducing additional hyperparameters. We encourage more exploitation (increase the depth) when finding good points in the smallest search region, and encourage more exploration (decrease the depth) when good points are found in boarder search regions. On our set of diverse benchmarks - including synthetic and commonly-used test functions, as well as two challenging high-dimensional problems - this simple heuristic worked without any tuning required.

Comparison with original TuRBO

Our current experiments with TuRBO are all re-implementations to make sure baselines have the same computational cost. We run the original TuRBO implementation (with exact GP and Thompson sampling) on both robot morphology design and human musculoskeletal system control task (Figure R4). We observed that FocalBO outperforms TuRBO on both tasks with smaller computational cost. The reason of TuRBO's poor performance may be that it cannot quickly adapt over the search space when the online evaluation budget is small.

Typos and unclear statements

Thanks for pointing out the typos. We will correct them and improve our paper in the new version.

The novelty of our work

Here we highlight the novelty of FocalBO in both GP and BO aspects.

We design the first sparse GP model that improves acquisition function optimization. Our design of focalized GP enables better local estimation, aiming at improving acquisition function optimization during Bayesian optimization. We adopt variational inference to derive focalized GP, which is capable of performing joint posterior inference and sampling given a set of test points just like exact GP. Therefore our proposed GP model is automatically compatible with any acquisition function that is used for exact GPs. (Figure 2).

The locally induced GP (LIGP) in the cited work [2] is designed for regression tasks, which assigns different inducing points to every test point, aiming at improving the point estimation measured by MSE. The inability of joint posterior computation and discontinuous prediction prevents LIGP from easily being incorporated into the BO framework.

We propose the first scalable BO algorithm that is capable of utilizing large offline dataset for optimization. Our design of hierarchical acquisition function optimization with focalized GP searches promising positions over different scale of search region during one BO iteration, enabling making decision based on both global and local information under restricted computational budget.

The overall idea of TuRBO [3] is to restrict the search space to a fixed size during one BO iteration, and adjust the search region size based on the optimization results. It achieves scalability by discarding previous samples and restarting when the search region reduce to certain threshold. Their use of exact GP still faces the scalability issue and would be computationally intensive when handling large offline datasets. As mentioned in the last paragraph of section 4.2, our proposed framework is orthogonal to TuRBO, and find that FocalBO and TuRBO can have a complementary effect in sections 5.2 and 5.3.

[2] Cole, D. Austin, Ryan B. Christianson, and Robert B. Gramacy. "Locally induced Gaussian processes for large-scale simulation experiments." Statistics and Computing 31.3 (2021): 33.

[3] Eriksson, David, et al. "Scalable global optimization via local Bayesian optimization." Advances in neural information processing systems 32 (2019).

Theoretical implications of sparse GP approximation

We agree that the theory section can be fleshed out more, and will do so by (1) providing more precise formulae for the additional regret incurred due to too-sparse approximations, and (2) experimental and numerical evidence for the increased approximation fidelity of Focalized GP.

For the former, we do not aim to propose any new theorems due to the restrictive nature of common assumptions, lack of guarantees for ELBO-based methods, and difficulty for controlling the effective number of inducing points within the local region. However, we will better motivate our method by providing examples of high KL error under reasonable assumptions, e.g. those used in SVGP-TS[1].

In Figure R2, we also empirically measure our claim that Focalized GP can significantly reduce approximation error on the search region. We sampled 8000 training points from 2d GP functions to train focalized GP and SVGP. Over different size of the search region, we compare the KL divergence of the GP posterior prediction over search region between sparse GPs and the exact GP. We observe that the KL divergence between focalized GP and exact GP is consistently smaller than that between SVGP and exact GP, implying tighter approximation to the exact GP over local region.

While a rigorous regret bound is hard to derive, we conduct an empirical study where we directly compare the optimization performance between focalized GP and SVGP when combining with TuRBO. In this way we can eliminate the influence of hierarchical acquisition optimization. The optimization performances are shown in Figure R3. We observe that focalized GP outperforms SVGP on both high-dimensional problems, which empirically demonstrates our theoretical implications that Focalized GP contributes to reducing regret.

[1] Vakili, Sattar, et al. "Scalable Thompson sampling using sparse Gaussian process models." Advances in neural information processing systems 34 (2021): 5631-5643.

Thank you for your detailed review. We are improving the paper based on your suggestions. We'd also like to clarify your concerns in the following paragraphs. Please find the rebuttal Figures by opening the rebuttal PDF file.

GP comparison in Figure 1

We would like to highlight that our goal of designing focalized GP is to to allocate a fixed set of limited computational resources to obtain better prediction over specific search regions instead of the entire input domain. This would contribute to better acquisition function optimization in BO as local optimization are usually employed (line 147-165 in the paper).

For any function, there is some number of inducing points for which the sparse GP posterior converges to that of the full GP. In practice, however, this threshold is unknown, and may be prohibitively high for complex functions. Hence, Figure 1 attempts to illustrate that for a fixed number of inducing points, there is a failure mode in which attempting to model the full input space results in an overly-smooth posterior, and that one possible remedy (ours) is to allocate this representational budget towards a subregion of the input space.

The design of $\mathcal{L}_{\text{reg}}.$

Without this regularization term, we observed that the ELBO loss can lead to arbitrarily high weights, leading to large lengthscales and poor fidelity within the search region. Hence, we designed $\mathcal{L_{\text{reg}}}$ to emphasize prediction within the search region, since we are only optimizing within those subregions in FocalBO. To better illustrate the formulation of $\mathcal{L}_{\text{reg}}$, we can rewrite it as

$L_{\text{reg}} = \frac{ \sum_{i=1}^t w_i - |X \in S_{c,l}| }{ |X \in S_{c,l}| }$ $= \frac{ \sum_{i=1}^t w_i -\sum_{i=1}^t 1_{x\in S_{c,l}} w_i }{ \sum_{i=1}^t 1_{x\in S_{c,l}} w_i } = \frac{ \sum_{i=1}^t 1_{x\notin S_{c,l}} w_i }{ \sum_{i=1}^t 1_{x\in S_{c,l}} w_i }$

in which the numerator encourages reducing the weights of points outside search region (leading to better estimation within the search region), and the denominator scales the value of $\mathcal{L}_{\text{reg}}$ according to the amount of data points inside the search region. Using this relative quantity allows us to perform hyperparameter-free regularization over different search region sizes.

In our experiments, we observed that adding $\mathcal{L}_{\text{reg}}$ did help avoid overfitting to large lengthscales and enabled better local estimation compared to SVGP (Figure 7 and 8 in appendix).