Kernel Quadrature and Kernel Means

Summary

The three integrals that make Bayesian quadrature tractable have a reproducing-kernel-Hilbert-space (RKHS) reading: the kernel mean ${\mu }_{\nu }=\int k(x,\cdot )\nu (\mathrm{d}x)$ is the embedding of the base measure $\nu$ into the RKHS $\mathcal{H}$ of $k$, and the BQ posterior variance $\mathfrak{v}$ equals the squared worst-case (RKHS) error of the quadrature rule. This dual view links Bayesian quadrature to kernel means, kernel herding, and the maximum-mean-discrepancy (MMD); it also clarifies the one subtle difference from kernel quadrature, where the kernel is allowed to shrink with the number of nodes.

Overview

Bayesian Quadrature showed the posterior mean and variance are assembled from ${\mathfrak{m}}_0$, the kernel mean $\ell (x_i)=\int k(x,x_i)\nu (\mathrm{d}x)$, and the initial error $\mathfrak{K}=\iint k\nu \nu$. This note gives those quantities their functional-analytic meaning. Every positive-definite kernel $k$ defines an RKHS $\mathcal{H}$ with reproducing property $⟨f,k(\cdot ,x){⟩}_{\mathcal{H}}=f(x)$ (see Gaussian Process Regression). In this language, integration against $\nu$ is a bounded linear functional whose Riesz representer is precisely the kernel mean. This is the bridge between the probabilistic (Bayesian) and the deterministic worst-case views of quadrature, and it is why the BQ error bar $\mathfrak{v}$ is simultaneously a Bayesian posterior variance and a tight worst-case bound over an RKHS ball.

Main Content

Kernel mean (kernel embedding of a measure)

For a kernel $k$ with RKHS $\mathcal{H}$ and a measure $\nu$ on $\mathcal{X}$, the kernel mean (or kernel embedding) of $\nu$ is the element

$${\mu }_{\nu }(\cdot ):={\int }_{\mathcal{X}}k(x,\cdot )\nu (\mathrm{d}x)\in \mathcal{H}.$$

Evaluated at a node, ${\mu }_{\nu }(x_i)=\ell (x_i)=\int k(x,x_i)\nu (\mathrm{d}x)$, recovering the BQ vector ${\ell }_X$. By the reproducing property, for any $f\in \mathcal{H}$,

$${\int }_{\mathcal{X}}f(x)\nu (\mathrm{d}x)=⟨f,{\mu }_{\nu }{⟩}_{\mathcal{H}},$$

i.e. ${\mu }_{\nu }$ is the Riesz representer of the integration functional $f\mapsto \int f\mathrm{d}\nu$.

Symbols. $\mathcal{H}$ = RKHS of $k$; $⟨\cdot ,\cdot {⟩}_{\mathcal{H}}$ = its inner product; $\Vert \cdot {\Vert }_{\mathcal{H}}$ = its norm; ${\mu }_{\nu }\in \mathcal{H}$ = kernel mean of $\nu$; ${\ell }_X=[{\mu }_{\nu }(x_1),\dots ,{\mu }_{\nu }(x_N)]$; $\mathfrak{K}=⟨{\mu }_{\nu },{\mu }_{\nu }{⟩}_{\mathcal{H}}=\iint k\nu \nu$ = squared RKHS-norm of the kernel mean = initial variance.

The posterior variance is the squared worst-case error

A quadrature rule $Q(f)={\sum }_i{w}_{i}f(x_i)$ with weights $w=k_{XX}^{-1}{\ell }_X$ (the BQ weights of ^thm-bq-weights in Bayesian Quadrature) has a worst-case error over the unit ball of $\mathcal{H}$. The following identity — the same computation as Exercise 4.7 in the text (the RKHS worst-case error of GP regression) — is the key result.

Worst-case error = BQ posterior standard deviation

Define the worst-case integration error of the rule with weights $w$ over the RKHS unit ball,

$$e(X,w):=\underset{\Vert f{\Vert }_{\mathcal{H}}\le 1}{\sup }|{\int }_{\mathcal{X}}f\mathrm{d}\nu -\sum _{i=1}^N{w}_{i}f(x_i)|.$$

With the BQ weights $w=k_{XX}^{-1}{\ell }_X$ this worst-case error equals the BQ posterior standard deviation:

$$e(X,w{)}^2=\mathfrak{K}-{\ell }_X^{\top }{k}_{XX}^{-1}{\ell }_X=\mathfrak{v}.$$

Proof sketch. Write the error functional as an inner product with $g:={\mu }_{\nu }-{\sum }_i{w}_{i}k(\cdot ,x_i)\in \mathcal{H}$ using the reproducing property: $\int f\mathrm{d}\nu -{\sum }_i{w}_{i}f(x_i)=⟨f,g{⟩}_{\mathcal{H}}$. By Cauchy–Schwarz the supremum over $\Vert f{\Vert }_{\mathcal{H}}\le 1$ is attained at $f=g/\Vert g\Vert$ and equals $\Vert g{\Vert }_{\mathcal{H}}$. Expanding

$$\Vert g{\Vert }_{\mathcal{H}}^2=⟨{\mu }_{\nu },{\mu }_{\nu }⟩-2\sum _i{w}_i{\mu }_{\nu }(x_i)+\sum _{ij}{w}_i{w}_{j}k(x_i,x_j)=\mathfrak{K}-2w^{\top }{\ell }_X+w^{\top }{k}_{XX}w.$$

Minimising over $w$ gives $w^{\star }=k_{XX}^{-1}{\ell }_X$ and the minimal value $\mathfrak{K}-{\ell }_X^{\top }{k}_{XX}^{-1}{\ell }_X=\mathfrak{v}$. So the BQ weights are simultaneously the minimum-worst-case-error weights, and $\sqrt{\mathfrak{v}}$ is that minimal worst-case error. $\square$

This is a foundational fact: the Bayesian posterior variance $\mathfrak{v}$ (a subjective, prior-dependent quantity) coincides with a hard, frequentist worst-case error bound over the RKHS ball. The BQ error bar is therefore an honest upper bound on the actual error for any integrand living in the unit ball of $\mathcal{H}$.

Maximum mean discrepancy view

If nodes carry uniform weights $w_i=1/N$ (as in Monte Carlo / quasi-Monte Carlo), the worst-case error becomes the maximum mean discrepancy (MMD) between the target measure $\nu$ and the empirical measure ${\hat{\nu }}_N=\frac{1}{N}{\sum }_i{\delta }_{x_i}$:

$$\mathrm{MMD}(\nu ,{\hat{\nu }}_N)=\Vert {\mu }_{\nu }-{\mu }_{{\hat{\nu }}_N}{\Vert }_{\mathcal{H}}=\underset{\Vert f{\Vert }_{\mathcal{H}}\le 1}{\sup }|\int f\mathrm{d}\nu -\frac{1}{N}\sum _{i}f(x_i)|.$$

Minimising MMD by choosing nodes greedily is kernel herding; choosing both nodes and weights to minimise $e(X,w)$ is kernel quadrature. Bayesian quadrature is thus the probabilistic member of a family that also contains kernel herding, kernel quadrature, and (via low-discrepancy sequences) quasi-Monte Carlo.

Initial error and node contraction

Before any evaluation ($N=0$), the rule integrates to the prior mean and the worst-case error is the initial error $\sqrt{\mathfrak{K}}=\Vert {\mu }_{\nu }{\Vert }_{\mathcal{H}}$. Each added node can only reduce the worst-case error, because adding a row/column to $k_{XX}$ and an entry to ${\ell }_X$ can only increase the subtracted term ${\ell }_X^{\top }{k}_{XX}^{-1}{\ell }_X$. The rate at which $\mathfrak{v}\to 0$ is governed by the smoothness of the kernel and the placement of nodes (see Convergence and Priors in Bayesian Quadrature).

Kernel quadrature vs Bayesian quadrature — the subtle difference

Bayesian quadrature keeps the kernel $k$ fixed (a genuine prior). Kernel quadrature (Bach; Bach, Lacoste-Julien, and Oborozinski) often lets the kernel shrink as the number of nodes grows. This can improve worst-case rates but is not compatible with the Bayesian notion of a prior (a prior must not depend on the amount of data). More practically, an $N$-dependent kernel amounts to a continuous relaxation of the associated error estimate — which plays a less central role in the deterministic kernel view than in the Bayesian one. This same tension reappears for degenerate (finite-rank) polynomial kernels that reproduce Gaussian quadrature (see Classical Quadrature as Inference), where the “prior” grows more flexible with $N$ and is “not a real prior at all.”

Examples

Kernel mean for the Gaussian pairing

With $k(x,x^{\prime })={\theta }^2\mathcal{N}(x;x^{\prime },{\lambda }^2)$ and $\nu (x)=\mathcal{N}(x;\mu ,{\sigma }^2)$ (see Bayesian Quadrature), the kernel mean is available in closed form by Gaussian convolution:

$${\mu }_{\nu }(x_i)=\int {\theta }^2\mathcal{N}(x;x_i,{\lambda }^2)\mathcal{N}(x;\mu ,{\sigma }^2)\mathrm{d}x={\theta }^2\mathcal{N}(x_i;\mu ,{\lambda }^2+{\sigma }^2),$$

and its squared RKHS norm is $\mathfrak{K}={\theta }^2/\sqrt{2\pi (2{\sigma }^2+{\lambda }^2)}$. Every quantity needed for the worst-case error / posterior variance is thus a Gaussian evaluation.

Worst-case interpretation of an error bar

Suppose $\mathfrak{K}=1$ (unit initial error) and after $N$ nodes ${\ell }_X^{\top }{k}_{XX}^{-1}{\ell }_X=0.9999$, so $\mathfrak{v}=10^{-4}$ and $\sqrt{\mathfrak{v}}=10^{-2}$. Then for any integrand $f$ in the unit ball $\Vert f{\Vert }_{\mathcal{H}}\le 1$, the rule’s error is guaranteed $\le 10^{-2}$; more generally the guaranteed error scales with $\Vert f{\Vert }_{\mathcal{H}}$. The Bayesian and worst-case readings agree exactly.

Connections

• Explains the ingredients ${\ell }_X,\mathfrak{K},\mathfrak{v}$ of Bayesian Quadrature in RKHS terms.
• Specialises to MMD / kernel herding (uniform weights) and quasi-Monte Carlo (low-discrepancy nodes); see Lessons from Integration.
• Underlies the degenerate-kernel reproduction of Gaussian quadrature in Classical Quadrature as Inference.
• Sets up convergence analysis: worst-case error rates in Convergence and Priors in Bayesian Quadrature.

See Also

• Bayesian Quadrature — the probabilistic side of this duality.
• Gaussian Process Regression — reproducing property and the Exercise 4.7 worst-case-error identity.
• Convergence and Priors in Bayesian Quadrature — how kernel smoothness sets the rate at which $\sqrt{\mathfrak{v}}\to 0$.
• Lessons from Integration — quasi-Monte Carlo, kernel herding, and the RKHS view of “why be probabilistic.”