Nested Expectations with Kernel Quadrature

Thank you for your consideration of the paper. We are very glad to see that you think the idea of using NKQ to estimate these expectations is interesting and the paper is well-written and easy to follow.

1. The pushforward map for change of variable trick

Thank you for your question about this. We agree that we could have fleshed out a bit more the details of this trick (see also our response to reviewer duxH) and now plan on providing an extensive discussion using the additional space available for the camera-ready version.

This approach is actually general and widely available. For example, for one dimensional distributions, a simple pushforward map is the inverse CDF, in which case the base measure is the uniform distribution. This is typically called inverse transform sampling. Such pushforward maps can be obtained through a multitude of simulation tricks which are widely popular in the Monte Carlo literature; see [Chapter 2 of https://www.cs.fsu.edu/~mascagni/Devroye.pdf] for a very detailed discussion. Additionally, the idea of using such pushforward transformations is the foundational idea behind the field of simulation-based inference, in which case the pushforward map is simply called a ‘simulator’ or ‘generator’ [https://arxiv.org/pdf/1911.01429]. In this particular case, we note that the literature considers exactly the setting where the distribution $p$ is intractable, although it might not cover all cases that you mention.

If the distribution $p$ is known up to a normalization constant, instead of using the change of variable trick, we have a nicer alternative than the change of variable trick by using the Stein reproducing kernel which constructs a new kernel with a standard base kernel and the score function of $p$; see the third bullet point of Section B.1 in https://arxiv.org/pdf/2406.16530 of how it can be applied for kernel / Bayesian quadrature.

When the pushforward map does not exist, our method would incur the computational burden of inverting the Gram matrices. Fortunately, a wide range of techniques already exist in the literature that aim to reduce this cost. See the detailed discussion between lines 138–152 in the right column of page 3 of the paper. We will add a clear sentence in the paper emphasizing the necessity of using these approximate methods in this case.

2. Minors: typos and big O notations

Thank you for catching these, we will fix these in the revised version of the paper.

Thank you for your consideration of the paper. We are very glad to see that you think the paper is very clearly written and appreciate our effort to include real-world applications. We have carefully addressed all your comments below, but please do let us know if there is anything we can do to help.

1. The core idea appears incremental

While the core idea may appear simple from an algorithmic standpoint, we view this simplicity as a key strength rather than weakness. In practice, we believe that methods that are conceptually clear and easy to implement are much more likely to be adopted. In this specific instance, we show that our proposed method can significantly outperform existing approaches despite this algorithmic simplicity, and believe there is therefore clear evidence of the value of our proposal.

The other very strong element of novelty is in terms of the theoretical guarantees we are able to obtain (and the associated proof techniques). Although we appreciate this is something that not all users of our method might be interested in, it is still highly relevant to practitioners. Specifically, we prove a significantly faster convergence rate in $T$ than what is suggested by the existing literature (e.g., [Chen et al., 2024b]). Our rate of $T^{-s_\Theta/d_\Theta}$ notably improves upon the previously established rate of $T^{-1/4}$. This means that one does not need to take $T$ as large as existing results might suggest, which is important for practitioners who might otherwise have wasted significant computation on trying to approximate the outer expectation.

2. Application to other acquisition functions in Bayesian optimization

Thank you very much for raising this as we were actually not aware that these other acquisition functions were also nested expectations. The reason we decided to focus on the setting of look-ahead optimisation is that there is an entire paper on this topic (in fact written by some of the authors of the BoTorch package) [Yang et al., 2024]. We therefore assumed that this example would be particularly relevant to the BO community. We will add a broader discussion of the applicability of our method to these additional acquisition functions to the camera-ready version.

3. Change of variable trick

Thank you very much for your thoughts on this. We agree that extending our presentation and discussion of this trick could be very helpful and will do this in the camera-ready version. In the meantime, see below for an answer to each of your sub-comments relating to this.

1. Applicability of the change-of-variable trick

We want to clarify that the change-of-variable trick is in fact applicable to all experiments in our paper. We do however agree with you that it is less helpful when the number of function evaluations is already inherently limited since the cost is relatively low in that case anyway. In this paper, the finance and health economics experiments were selected specifically because they are expensive, and so having a better estimator such as NKQ is particularly important. There are however numerous related settings where this is not the case and the change-of-variable trick could still be useful.

2. Cubic complexity

BO with Gaussian processes indeed requires cubic cost at each iteration, however this cost is cubic in the number of queries of the BO algorithm, not the number of samples $N$ or $T$ for estimating the nested expectation (i.e. the acquisition function). Therefore, precomputation reduces the cost in $N$ and $T$ for optimising the acquisition function at each iteration of the BO algorithm, while the cost of GP posterior update is still cubic and is the same across all methods regardless of how the acquisition function is being approximated. We will make this distinction clear in the revised manuscript.

3. Popular libraries already cache quadrature weights, and I presume the authors intend to leverage such caching to avoid repeated computations

We do indeed use the idea of caching for the weights of NKQ in estimating the acquisition function so that we do not need to re-compute the weights at each iteration. We are not, however, using NKQ when computing the marginal likelihood in GP hyperparameter selection because it is a standard expectation not a nested expectation.

4. Comparison to QMC

We conduct an additional experiment with Quasi Monte Carlo ($N=T=\Delta^{-2}$), as shown here https://github.com/Anonymous65536/nest_kq/blob/master/bo.pdf, demonstrating that while QMC outperforms standard Monte Carlo in estimating the nested expectation within the utility function, it is less efficient than our proposed NKQ method across all three Bayesian optimization datasets.

4. Equating kernel quadrature directly with Bayesian quadrature

Thank you for pointing this out. We of course agree and will further highlight the distinction between frequentist and Bayesian approaches in the camera-ready version of the paper.

Thank you very much for your consideration and strong support of our paper (including the very kind comment about the effort we put in the writing). You mention leaning towards a ‘strong accept (5)’ and we remain at your disposal in case there is anything we can do to help in this respect.

1. Acronyms

Thank you for pointing this out. We will do our best to limit the use of acronyms to concepts which are repeatedly used, and will check that all acronyms have been properly defined.

2. Knowledge of constants

Thank you for this interesting and important question – we will certainly add a discussion of this point in the camera-ready version of the paper. Firstly, most constants in Theorem 1 actually have no impact on algorithm design. The constants named $S$ or $G$ only impact $C_1$ and $C_2$, and $C_1$ and $C_2$ do not impact the use of the algorithm in any way.

The only important constants for the algorithm are the smoothness parameters $s_\mathcal{X}$ and $s_{\Theta}$, which help us identify the appropriate level of smoothness to use for kernels $k_{\mathcal{X}}$ and $k_{\Theta}$. This is very common in this literature [Sommariva and Vianello, 2006a, Briol et al., 2019], and even poor choices of these smoothness parameters does not necessarily mean the rate will be impacted [Kanagawa et al., 2020, Wynne et al., 2021]. Although we initially mentioned this very briefly below Theorem 1, we will now use the extra space available to us in the camera-ready version to discuss this more extensively.

Thank you very much for your careful consideration of our paper and for checking the proof of the main theorem. We are very happy that you agree that our convergence rate results (Theorem 1) are technically sound and that our experiments are well-designed.

Thank you for also bringing up the issue of minimax rates and for highlighting papers we were unaware of —this is indeed a fundamental and important question. To the best of our knowledge, most existing approaches on minimax rates for two-stage algorithms first reduce the problem to a one-stage regression by assuming that the target of the second regression is already known. For instance, in the suggested Zhang et al (2025 ) paper, the minimax lower bound provided requires the assumption that the oracle density ratio between the source and target distributions is known (Theorem 1). Similarly, in the literature on nonparametric instrumental variable regression— see for example Theorem 4 and Appendix F.1 in https://arxiv.org/pdf/2411.19653, and Chapter 3 of https://arxiv.org/pdf/0709.2003 — minimax lower rates are provided under the assumption that the conditional expectation operator is known, even though in practice their proposed algorithms would learn this operator from data.

Translating this approach to our setting of nested expectations, we could assume access to the true value of the inner expectation. This effectively reduces the problem to a standard (single-stage) expectation, for which the minimax optimal rate is well-known: $\mathcal{O}(T^{-s_\Theta/ d_\Theta})$ [Sommariva and Vianello, 2006a, Section 2 of https://arxiv.org/pdf/2307.06787]. We agree with you that this is an interesting point to discuss and will do so in the camera-ready version of our paper.

That said, it clearly remains an open challenge to establish minimax lower bounds for genuinely two-stage problems without reducing them to one-stage settings. Developing such a theory would be highly nontrivial and beyond the scope of our paper, but also a very exciting direction for future research.