Integration in reproducing kernel Hilbert spaces of Gaussian kernels

Toni Karvonen, Chris J. Oates, Mark Girolami

Abstract

The Gaussian kernel is a fundamental tool in machine learning, uncertainty quantification, and scattered data approximation. Despite its ubiquity, the numerical integration of functions within the Reproducing Kernel Hilbert Space (RKHS) generated by Gaussian kernels has remained an under-explored problem in numerical analysis. Specifically, existing algorithms often require restrictive constraints on the kernel's length-scale parameter. This paper introduces two classes of integration algorithms designed for $d$-variate functions in Gaussian RKHSs that achieve exponential or super-algebraic error decay without constraints on the length-scale. The first class utilizes scaled Gauss-Hermite rules, while the second employs worst-case optimal weights for flexible, potentially nested, point sequences. We provide rigorous upper and lower bounds on the worst-case error for both approaches, filling a significant gap in the theoretical understanding of Gaussian process integration.

Introduction

In applications ranging from Gaussian Process (GP) regression to Bayesian Quadrature, we frequently encounter the need to integrate functions that belong to an RKHS. The Gaussian kernel, defined by its variance and length-scale parameters, is the most common choice for these models. However, standard numerical integration rules like Gauss-Hermite quadrature are designed for polynomials and do not inherently account for the specific Hilbert space structure of the Gaussian kernel.

A primary challenge in this field has been the "parameter-universality" of integration rules. Previous research often assumed specific relationships between the kernel's length-scale and the integration measure. When these assumptions are violated—for instance, when the length-scale is very small—standard rules can fail to converge efficiently. This research addresses this gap by constructing algorithms that provide explicit, tight bounds on the worst-case error (WCE) across all positive length-scales.

Proposed Integration Algorithms

The authors propose two distinct methodologies to achieve robust numerical integration in $\mathbb{R}^d$.

1. Scaled Gauss–Hermite Rules

The first approach adapts classical Gauss–Hermite (GH) quadrature. While standard GH rules are exact for polynomials, they are not optimized for the orthonormal basis functions of a Gaussian RKHS. The authors introduce a scaling factor, $\beta$, which is a function of the kernel's variance and length-scale. By scaling the quadrature points and weights, the rule becomes exact for the RKHS basis functions.

For these scaled rules, the paper derives both lower and upper bounds for the worst-case error $e$. The error is shown to decay at a rate of approximately: $$e \approx \exp(-c N^{1/d})$$ where $N$ is the number of evaluation points and $d$ is the dimension. This confirms that the scaled GH rules achieve exponential convergence, with the scaling factor ensuring the rule remains effective regardless of how "wiggly" the underlying function is.

2. Worst-case Optimal Weights (Bayesian Quadrature)

The second approach offers greater flexibility by allowing for arbitrary point sets, such as van der Corput sequences or other quasi-Monte Carlo designs. Given a set of points, the algorithm calculates weights that are "worst-case optimal"—meaning they minimize the maximum possible error for any function in the unit ball of the RKHS.

To prove the convergence of this method in an unbounded domain, the authors employ a domain decomposition technique. They partition $\mathbb{R}^d$ into bounded cubes and a "tail domain." By applying scattered data approximation theory to the interior cubes and bounding the integration error in the tail, they prove an upper bound of $\exp(-c N^{1/(2d)})$. While this rate is theoretically slower than the GH rules, the method supports nested sequences. This is a significant practical advantage, as it allows users to incrementally add points to an integration estimate without discarding previous computations.

Numerical Verification

As this is a theoretical numerical analysis study, the authors verified their findings through high-precision simulations rather than empirical datasets. Using Python with 100-digit and 400-digit precision, they tested the algorithms on synthetic $d$-dimensional Gaussian integrals. These experiments confirmed the predicted exponential decay rates and demonstrated that the scaled GH rules maintain their accuracy even as the length-scale parameter varies across several orders of magnitude.

Key Insights and Conclusion

This work provides several critical insights for the fields of numerical analysis and machine learning:

  • Scaling as a Bridge: The introduction of the scaling factor $\beta$ demonstrates how classical polynomial quadrature can be rigorously adapted to modern kernel-based spaces.
  • Parameter Universality: By removing constraints on the length-scale, these algorithms become applicable to real-world ML scenarios where kernel parameters are often learned from data and can take extreme values.
  • Approximation vs. Integration: The research highlights the deep link between how well a function can be reconstructed (interpolation) and how well it can be integrated (quadrature).

While the "curse of dimensionality" remains—evidenced by the $1/d$ term in the error exponents—this paper establishes a solid theoretical foundation for Gaussian RKHS integration. Future work may focus on optimizing point placement to improve convergence constants or extending these scaling techniques to non-Gaussian weight functions.

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},
}
Figure