Fast automatic Bayesian cubature using lattice sampling

Abstract

Automatic cubatures approximate integrals to user-specified error tolerances. For high-dimensional problems, it is difficult to adaptively change the sampling pattern, but one can automatically determine the sample size, n, given a reasonable, fixed sampling pattern. We take this approach here using a Bayesian perspective. We postulate that the integrand is an instance of a Gaussian stochastic process parameterized by a constant mean and a covariance kernel defined by a scale parameter times a parameterized function specifying how the integrand values at two different points in the domain are related. These hyperparameters are inferred or integrated out using integrand values via one of three techniques: empirical Bayes, full Bayes, or generalized cross-validation. The sample size, n, is increased until the half-width of the credible interval for the Bayesian posterior mean is no greater than the error tolerance. The process outlined above typically requires a computational cost of $O(N_{\text {opt}}n^3)$, where $N_{\text {opt}}$ is the number of optimization steps required to identify the hyperparameters. Our innovation is to pair low discrepancy nodes with matching covariance kernels to lower the computational cost to $O(N_{\text {opt}} n \log n)$. This approach is demonstrated explicitly with rank-1 lattice sequences and shift-invariant kernels. Our algorithm is implemented in the Guaranteed Automatic Integration Library (GAIL).

Appendix: Details of the full Bayes posterior density for \(\mu \)

To simplify, we drop the dependence of $c_{0{\varvec{\theta }}}$, $\varvec{c}_{\varvec{\theta }}$, and ${\mathsf {C}}_{\varvec{\theta }}$ on ${\varvec{\theta }}$ in the notation below. Starting from the Bayesian formula for the posterior density for $\mu$ at the beginning of Sect. 2.2.2 with the non-informative prior, it follows that

$$\begin{aligned}&\rho _{\mu |\varvec{f}}(z | \varvec{y}) \propto \int _{0}^\infty \int _{-\infty }^\infty \rho _{\mu | m, s^2, \varvec{f}}(z | \xi , \lambda , \varvec{y})\\&\quad \rho _{\varvec{f}| m, s^2} (\varvec{y}| \xi , \lambda ) \, \varvec{\rho }_{m,s^2}(\xi ,\lambda ) \, \text {d}{\xi }\text {d}{\lambda }\\&\quad \propto \displaystyle \int _{0}^\infty \frac{1}{\lambda ^{(n+3)/2}} \int _{-\infty }^\infty \exp \\&\quad \biggl ( -\frac{1}{2\lambda }\biggl \{ \frac{ [z - \xi (1 - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{1}) - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{y}]^2}{c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c}} \\&\quad + (\varvec{y}- \xi \varvec{1})^T {\mathsf {C}}^{-1}(\varvec{y}- \xi \varvec{1}) \biggr \} \biggr ) \, \text {d}{\xi }\text {d}{\lambda }\\&\quad \text {by } (7), (8) \; \text {and} \; \rho _{m,s^2}(\xi ,\lambda ) \propto 1/\lambda \\&\propto \displaystyle \int _{0}^\infty \frac{1}{\lambda ^{(n+3)/2}} \int _{-\infty }^\infty \exp \left( -\frac{\alpha \xi ^2 -2 \beta \xi + \gamma }{2\lambda (c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c})} \right) \, \text {d}{\xi }\text {d}{\lambda }, \end{aligned}$$

where

$$\begin{aligned} \alpha&= (1 - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{1})^2 + \varvec{1}^T {\mathsf {C}}^{-1} \varvec{1}(c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c}),\\ \beta&=(1 - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{1})(z - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{y})\\&\quad +\, \varvec{1}^T {\mathsf {C}}^{-1} \varvec{y}(c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c}),\\ \gamma&= (z - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{y})^2 + \varvec{y}^T {\mathsf {C}}^{-1} \varvec{y}(c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c}). \end{aligned}$$

In the derivation above and below, factors that are independent of $\xi$, $\lambda$, or z can be discarded since we only need to preserve the proportion. But, factors that depend on $\xi$, $\lambda$, or z must be kept. Completing the square, $\alpha \xi ^2 -2 \beta \xi + \gamma = \alpha (\xi -\beta /\alpha )^2 - (\beta ^2/\alpha ) + \gamma ,$ allows us to evaluate the integrals with respect to $\xi$ and $\lambda$:

$$\begin{aligned} \rho _{\mu |\varvec{f}}(z | \varvec{y})&\propto \displaystyle \int _{0}^\infty \frac{1}{\lambda ^{(n+3)/2}} \exp \left( -\frac{ \gamma - \beta ^2/\alpha }{2\lambda (c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c})} \right) \\&\quad \times \int _{-\infty }^\infty \exp \left( -\frac{\alpha (\xi -\beta /\alpha )^2}{2\lambda (c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c})} \right) \, \text {d}{\xi }\text {d}{\lambda }\\&\propto \displaystyle \int _{0}^\infty \frac{1}{\lambda ^{(n+2)/2}} \exp \left( -\frac{ \gamma - \beta ^2/\alpha }{2\lambda (c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c})} \right) \text {d}{\lambda }\\&\propto \left( \gamma - \frac{\beta ^2}{\alpha }\right) ^{-n/2} \\&\propto \left( \alpha \gamma - \beta ^2\right) ^{-n/2}. \end{aligned}$$

Finally, we simplify the key term via straightforward calculations to the following:

$$\begin{aligned} \alpha \gamma - \beta ^2 \propto 1 + \frac{(z - {\widehat{\mu }}_{\mathrm{EB}})^2}{(n-1)s_{\text {full}}^2}, \end{aligned}$$

where

$$\begin{aligned}&{\widehat{\sigma }}_{\text {full}}^2 := \frac{1}{n-1} \varvec{y}^T\left[ {\mathsf {C}}^{-1} - \frac{ {\mathsf {C}}^{-1} \varvec{1}\varvec{1}^T {\mathsf {C}}^{-1}}{\varvec{1}^T {\mathsf {C}}^{-1} \varvec{1}} \right] \varvec{y}\\&\quad \left[ \frac{(1 - \varvec{c}^T {\mathsf {C}}^{-1} \varvec{1})^2}{\varvec{1}^T {\mathsf {C}}^{-1} \varvec{1}} + (c_0 -\varvec{c}^T {\mathsf {C}}^{-1} \varvec{c}) \right] . \end{aligned}$$

This completes the derivation of (13).