Approximation-Aware Bayesian Optimization

Figure 1: which points were used as inducing points?

The inducing points are initialized to a set of points selected uniformly at random in the search space and then they are learned via gradient descent by minimizing the loss (ELBO or EULBO) when the GP model is trained on the data.

Figure 1: why is the uncertainty relatively constant at the right side of the plot (left plot)? Depending on the choice of the inducing points, I'd expect the predicted variance (and thus the EI) to increase towards the right edge of the plot

In the large interval between the rightmost inducing points, the variance remains fairly constant at the prior variance. At the rightmost inducing point, the variance dips, and then to the right of this rightmost inducing point, the variance increases back up to the prior variance. We think this is fairly expected behavior, and perhaps the dip in variance at the rightmost inducing point was missed due to the relatively large observation noise in this data? We are happy to discuss this with you in more detail.

Figure 1: what was the exact problem definition leading to Fig. 1? It would be good to see the exact parameterizations for reproducibility as it would help to gauge whether the motivational example is rather cherry-picked or whether the shown issue manifests across different parameterizations

We agree that reproducibility is important for this example problem as well as for other experiments. We plan to include a simple notebook with code to quickly reproduce Figure 1 in our code release which will be available on github once the paper is accepted. We specifically designed the toy dataset to illustrate the point of the paper (large amount of data on the left, very little on the right so that an SVGP with only 4 inducing points would underfit on the right so that the large objective value out right would be missed). Our hope is that this figure is illustrative and aids reader understanding, which we will make more clear in the next version. Of course, the actual experimental results in the paper are actual challenging benchmark problems and not designed for our method. Thank you for the suggestion!

missing 𝑡 in Eq. 2? shouldn't it be 𝜋(𝑓|𝐷𝑡)?

Thanks for catching this. We will fix this in the next version.

in the equation after line 221 it seems that the sum does not depend on 𝑗. shouldn't it be 𝑥𝑗?

The maximum (denoted by “max”; not “maximize”!) operation in Line 221 is taken over j.

why were the baselines only applied in conjunction with EI? (see line 259)

EI is the most commonly used acquisition function used in the BO literature, often because it is cheap to compute and performs comparably with other KG and other acquisition functions. A common motivation in the literature for choosing EI over KG is because KG is significantly more expensive to compute. Running EULBO provides a unique opportunity to make computing KG much more efficient such that it becomes approximately as cheap as EULBO with EI (see last paragraph of section 3.3). This is not the case for other baselines so running them with KG wouldn’ve been much more expensive. Beyond KG and EI, we note that the EULBO is limited by construction to acquisition functions that admit decision theoretic formulations, i.e. they must be phrasable as posterior expected utilities. This appears to exclude some popular acquisition functions like UCB.

it seems that, depending on the choice of the objective and method, there are quite significant differences in the variance of EULBO. For example, in Fig. 2 "Media Molecules 1", TuRBO + ELBO EI has much higher variance than TuRBO + EULBO EI. Do you account this observation to EULBO?

This is not something that we have explored specifically, but one plausible explanation is that EULBO consistently converges to a high-performing region of the search space with similar high-scoring molecules, while ELBO converges to a wider variety of lower-scoring regions of the search space, thus resulting in higher variance and lower final objective values. In other words, EULBO may just have lower variance because it consistently performs better on this problem.

(line 110): Could you define \lambda, m and S?

$m$ and $S$ are defined as the (learned) mean and covariance of the variational distribution $q(u)$ in our SVGP model. $\lambda$ should have been defined as $\lambda = (m, S)$, a shorthand for “all of the variational parameters,” which we omitted. We will fix this in the next version, and clarify the definition of $m, S$.

(Eq. between 114-115): q_\lambda is initially presented with one argument, then two. If the intention is for q_\lambda to represent all approximate distributions (in this case, p(f, u) ), please state this explicitly. It is natural to assume that q_\lambda(.) is just the Gaussian pdf.

In Bayesian methods, it is fairly typical to overload the notation of a pdf/measure with its argument. Therefore, $q(u)$ and $q(f, u)$, should be without ambiguity as per common practice. The subscript \lambda is to denote that the distribution denoted as q contains trainable parameters in $\lambda$. We will clarify this.

(line 116): k(.,.) as a function also needs to be explicitly defined.

Thank you for pointing this out. We will define the kernel function properly in the next version.

(line 165): Please clarify where exactly the requirement for the utility to be strictly positive plays a role or comes from.

This is due to the log in Eq 6. Thank you for pointing this out, this is pretty subtle and we don’t draw much attention to it. We will clarify this requirement in the next version.

(lines 173-175): Would using Gauss-Hermite quadrature for EI make EULBO significantly slower than ELBO?

This is a great question that we missed addressing in the original text. Very crucially, the expensive $K_{zz}^{-1}m$ and $K_{zz}^{-1}SK_{zz}^{-1}$ (or $K_{zz}^{-1/2}$ with whitening) solves that dominate both the asymptotic and practical running time of both the ELBO and the EULBO are fixed across the log utility evaluations needed by quadrature (and Monte Carlo in the q-EULBO case). As a result, the additional work of quadrature is pretty negligible. Because Gauss-Hermite quadrature converges extremely quickly in the number of quadrature sites, it only requires on the order of 10 or so of these post-solve evaluations to achieve near machine precision. We will add an explanation of this.

(Eq 6): Please use double integrals to indicate nested integration. Additionally, I don't understand the emergence of l(D_t |f) and the normalizing constant Z. I was under the impression that l(.|.) is the Gaussian likelihood as defined in line 113. Notice that D_t, as defined in line 92, contains both x and y.

Yes, that is correct. $\pi(f,u|D)$ denotes the “normalized” posterior, which is essentially $\ell(D|f,u) p(f,u) / Z$. Plugging these into the derivation of Eq 6 should clarify things.

(line 189): What is y^{+}_t and what its relation to y_t?

Thank you for catching this! We forgot to define $y^{+}_t$, which is the highest value of $y_t$ observed so far. We will properly define this in the next version.

Because you formulate the BO queries and GP approximation as a joint optimization problem without necessarily reducing the dimensionality of the problem, how much slower is this method compared to ‘approximation-ignorant’ BO?

In general, you’re right that the added cost of EULBO is largely due to optimization challenges, rather than concerns like quadrature etc. A single EULBO forward and backward calculation has essentially the same cost as an ELBO calculation; however, as we describe in Section 3.5 and our limitations section, we currently “warm start” EULBO optimization by first optimizing the ELBO, leading to increased computational cost. Here are the wall-clock run times for running TuRBO on the Lasso DNA task using the standard ELBO compared to EULBO with EI and EULBO with KG:

For the camera ready version of the paper, we plan to add a table of wall-clock runtimes comparing EULBO to all baselines.

The paper focuses specifically on SVGPs, but it would be interesting to explore whether the proposed approach can be extended to other sparse GP approximations, even those without a tractable ELBO. This would broaden the applicability of the method and strengthen the contribution.

Can the proposed EULBO approach be extended to other sparse GP approximations beyond SVGPs, even if they do not have a tractable ELBO? If so, what challenges would need to be addressed, and how might the optimization problem be formulated?

Our focus on SVGP was motivated by the fact that SVGPs are the most widely used sparse GP approximation in the high-throughput BO literature, but your question is a good one. SVGPs have been extended and improved several times, and it’s a natural question whether the EULBO can be adapted to all of these settings. Our method should be readily applicable when an ELBO exists mathematically but can only be approximated through Monte Carlo or quadrature. For sparse approximations where the objective is not a canonical ELBO, it is possible that a similar variational utility lower-bound could be derived, but it may look very different from this paper. We conjecture that some recent SVGP-like models like ODSVGP admit relatively straightforward EULBO adaptations. Other examples, like Vecchia approximations, would require pretty orthogonal machinery to what we introduce and would probably be interesting in their own right. We are happy to provide more detailed comments on specific sparse GP approximations if the reviewer has one in mind, and will add a discussion to the camera ready version.

In Figure 2, the exact GP performs worse than the proposed method and some other baselines in the BO setting. This is counterintuitive, as one would expect the exact GP to be the gold standard when computationally feasible. The authors should provide more discussion and insights into this unexpected result. Why does the exact GP perform worse than the proposed method and some other baselines in the BO experiments (Figure 2)? Is this due to the limitations of the exact GP in high dimensions, or are there other factors at play?

While we agree that this is counter-intuitive, we point to the fact that the true posterior of an SVGP is not an exact GP. Strictly speaking, SVGPs not only provide a variational approximation, but also modify the GP model to have an additional layer of latent variables. Therefore, there is no reason to expect that the performance of SVGPs would be the same as exact GPs, even if one has access to their true posterior. Additionally, and perhaps most interestingly, Exact GPs arguably have their own “mismatches” between learning and acquisition like the ones pointed out in and addressed by this paper: hyperparameter learning in exact GPs is not done in a utility aware fashion, for example. It seems plausible that, for some problems, utility aware hyperparameter learning might outweigh the loss incurred by using a sparse model. We do note that whether our method is better or worse than exact GPs is unlikely to be consistent across different tasks, and we suspect exact GPs are still quite competitive in settings where they can be used. (Also note the response to Reviewer veTg on a similar question.)

The paper presents several variations of the proposed method (e.g., EI-EULBO, KG-EULBO, batch versions), but it lacks a clear recommendation on which variant to use in practice. A more in-depth discussion of the trade-offs between these variants and guidance on when to use each one would enhance the practical value of the work. What are the key factors to consider when choosing between the different variants of the proposed method (e.g., EI-EULBO, KG-EULBO, batch versions)? In what scenarios would one variant be preferred over another?

The best choice for which acquisition function to use, whether or not to use batch BO, what batch size to use, etc., often vary widely across problems and it’s hard for us to give guidance beyond what exists in the literature: KG is often less myopic than EI, which can be better on some problems and worse on others. Definitively comparing acquisition strategies probably deserves its own investigation. One thing we do note, however, is that the use of the EULBO switches the balance in the computational-performance trade-off of acquisition functions. For instance, the cost of computing the EULBO amortizes the cost of computing KG, making it a more sensible choice in some settings than it was before (see section 3.3 last paragraph). But again, whether one should use EI or KG given this tipping of the scale will highly depend on the problem and this paper probably doesn’t help definitively answer that question.

While authors cite previous work, which proved that the selected action satisfies convergence guarantee, it does not directly prove anything about the performance of optimisation process choosing action in such a way (e.g. regret bound or convergence to optimum). The paper could be made much stronger if authors managed to connect those notions in some way. However, I also do not think it is critical, as the main contribution of the paper is empirical (although it would be greatly appreciated).

From the best of our knowledge, non-asymptotic convergence proofs under approximate inference, both in Bayesian optimization and bandits are rare. Furthermore, most existing works assume that one can explicitly control the fidelity of the approximation or that the true posterior is within the variational family. The benefits of utility-calibrated variational inference, on the other hand, only exists when the approximation is imperfect. Therefore, we are currently unsure how to analyze the theoretical properties of utility-calibrated Bayesian inference. However, we believe this would be a very interesting avenue for future research and will definitely explore this direction. We also point out that some asymptotic analyses of consistency exist as mentioned in Line 151-152.

Can the authors provide the running time of the proposed method (and baselines) ? It is ok if the proposed method is slower, but it would be good to quantify exactly how much slower it is.

Here are the wall-clock run times for running TuRBO on the Lasso DNA task from the paper using the standard ELBO compared to using EULBO with EI and using EULBO with KG:

We agree that providing a full table of average wall-clock runtimes for EULBO and all baselines would be useful, we will plan to add this table to the appendix for the camera ready version. Thank you for the suggestion!

Do authors have any expectations on how would the method perform in comparison to an exact GP on a smaller dataset? While I understand that the method is particularly designed for large datasets, it would be interesting to see how the utility VI-based acquisition strategy compares to standard acquisition functions like EI. It would be nice to have at least such experiment in the camera-ready version to judge whether the improvement delivered by the method comes from better acquisition strategy or better modelling

We point out to the top left pane in Figure 2, where we present results on the classic Hartmann 6 function. Somewhat surprisingly, our proposed approach does better than exact GPs in this one instance. Because SVGPs are not only a variational approximation, but a distinct model from exact GPs due to the use of inducing points, there is no reason to expect that exact GPs are a limiting case for the BO performance of SVGPs. Indeed, Exact GPs arguably have their own “mismatches” between learning and acquisition like the ones pointed out in this paper: hyperparameter learning in exact GPs is not done in a utility aware fashion, for example, while it is with EULBO. In general, we still expect exact GPs to be quite performant in settings where it can be applied. (Also note the response to Reviewer TCW1 on a similar question.)