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