Integration in reproducing kernel Hilbert spaces of Gaussian kernels

Toni Karvonen, Chris J. Oates, Mark Girolami

TL;DR

This paper provides a rigorous numerical analysis of integrating functions within the Reproducing Kernel Hilbert Space (RKHS) of Gaussian kernels. The authors introduce two classes of integration algorithms—scaled Gauss–Hermite rules and worst-case optimal rules—and prove that they achieve exponential or super-algebraic error decay regardless of the kernel's length-scale, filling a significant gap in the theoretical understanding of Gaussian process integration.

What Problem Does This Paper Address?

The Gaussian kernel is a cornerstone of machine learning (e.g., Gaussian Processes), uncertainty quantification, and scattered data approximation. However, from a numerical analysis perspective, the problem of efficiently integrating functions "reproduced" by these kernels hasn't been fully solved.

Specifically, previous research often placed restrictive constraints on the kernel's length-scale parameter (how "wiggly" the function is) relative to the integration measure. If the length-scale was too small, standard rules like Gauss-Hermite could fail to converge. This paper seeks "parameter-universal" algorithms that work for any positive length-scale and provide explicit, tight bounds on the "worst-case error"—the maximum possible integration error for any function in the unit ball of the RKHS.

Methods

The authors propose and analyze two distinct approaches:

  1. Scaled Gauss–Hermite Rules: The authors take the classical Gauss–Hermite quadrature (designed for polynomials) and apply a specific scaling factor derived from the RKHS parameters. By adapting the points and weights to the specific length-scale of the Gaussian kernel, they ensure the rule is exact for the orthonormal basis functions of the RKHS.
  2. Worst-case Optimal Weights (Bayesian Quadrature): This approach is more flexible. Given a set of points (which can be nested or scattered, like a van der Corput sequence), the algorithm calculates weights that minimize the worst-case error. To analyze this in an unbounded domain ($\mathbb{R}^d$), the authors use a domain decomposition technique: they break the space into bounded cubes and a "tail domain," applying scattered data approximation theory to the cubes and bounding the tail separately.

Datasets

As a theoretical numerical analysis paper, no external real-world datasets were used. Instead, the authors performed numerical simulations using Python with 100-digit and 400-digit precision to verify their theoretical error bounds. They tested their algorithms on synthetic d-dimensional Gaussian integrals to demonstrate the predicted exponential decay rates.

Key Insights and Ideas

  • Scaling is the Secret Sauce: Standard Gauss-Hermite rules are not "aware" of the RKHS structure. By introducing a scaling factor $\beta$ (a function of the variance $\alpha$ and length-scale $\ell$), the authors transform the problem into one where classical polynomial exactness translates into RKHS basis exactness.
  • Parameter Universality: Unlike prior work, these bounds hold for any positive length-scale. This is crucial for ML applications where length-scales are often learned from data and can be quite small.
  • Bridging Approximation and Integration: The second method leverages the link between kernel interpolation (how well we can reconstruct a function from points) and quadrature (how well we can integrate it). By bounding the "power function" (pointwise worst-case error), they derive integration bounds for flexible point sets.

Key Results

  • Exponential Convergence: For the scaled Gauss–Hermite rules, the worst-case error $e$ decays at a rate of approximately $\exp(-c N^{1/d})$, where $N$ is the number of points and $d$ is the dimension.
  • Tight Bounds: The authors derived both lower and upper bounds for the scaled GH rules, showing that their error estimates are nearly optimal.
  • Flexible Point Sets: For the second class of algorithms, they proved an upper bound of $\exp(-c N^{1/(2d)})$. While theoretically slower than the GH rules, this method allows for nested sequences, meaning you can add points one by one without throwing away previous computations—a major practical advantage for expensive integrands.

Limitations and Future Work

  • The Curse of Dimensionality: Both methods suffer from the $1/d$ term in the exponent. As the dimension $d$ increases, the number of points required for a specific accuracy grows exponentially.
  • Sub-optimal Point Placement: The authors acknowledge that the point sets used for the flexible method (locally quasi-uniform) are likely sub-optimal. They suggest that concentrating points more heavily near the origin (where the Gaussian weight is highest) could lead to even faster exponential convergence.
  • General Weight Functions: While this paper focuses on Gaussian measures, the authors note that extending these scaling techniques to other weight functions remains an open and interesting challenge.

Summary updated

Abstract

The Gaussian kernel plays a central role in machine learning, uncertainty quantification and scattered data approximation, but has received relatively little attention from a numerical analysis standpoint. The basic problem of finding an algorithm for efficient numerical integration of functions reproduced by Gaussian kernels has not been fully solved. In this article we construct two classes of algorithms that use $N$ evaluations to integrate $d$-variate functions reproduced by Gaussian kernels and prove the exponential or super-algebraic decay of their worst-case errors. In contrast to earlier work, no constraints are placed on the length-scale parameter of the Gaussian kernel. The first class of algorithms is obtained via an appropriate scaling of the classical Gauss-Hermite rules. For these algorithms we derive lower and upper bounds on the worst-case error of the forms $\exp(-c_1 N^{1/d}) N^{1/(4d)}$ and $\exp(-c_2 N^{1/d}) N^{-1/(4d)}$, respectively, for positive constants $c_1 > c_2$. The second class of algorithms we construct is more flexible and uses worst-case optimal weights for points that may be taken as a nested sequence. For these algorithms we derive upper bounds of the form $\exp(-c_3 N^{1/(2d)})$ for a positive constant $c_3$.
BibTeX
@article{karvonen2021integration,
  author = {Toni Karvonen and Chris J. Oates and Mark Girolami},
  title = {{Integration in reproducing kernel Hilbert spaces of Gaussian kernels}},
  journal = {Math. Comput.},
  year = {2021},
  doi = {10.1090/mcom/3659},
}

Loading related content...

Figure