On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature
This work addresses error analysis for numerical integration in machine learning and statistics, offering incremental improvements and new bounds for specific kernel-based methods.
The paper tackles the problem of deriving error bounds for Bayesian quadrature in noisy and randomized settings, focusing on Matérn and squared exponential kernels, and presents a meta-algorithm that recovers near-optimal error rates for Matérn kernels and provides new results for other settings, including with noise and misspecification.
In this paper, we study error bounds for {\em Bayesian quadrature} (BQ), with an emphasis on noisy settings, randomized algorithms, and average-case performance measures. We seek to approximate the integral of functions in a {\em Reproducing Kernel Hilbert Space} (RKHS), particularly focusing on the Matérn-$ν$ and squared exponential (SE) kernels, with samples from the function potentially being corrupted by Gaussian noise. We provide a two-step meta-algorithm that serves as a general tool for relating the average-case quadrature error with the $L^2$-function approximation error. When specialized to the Matérn kernel, we recover an existing near-optimal error rate while avoiding the existing method of repeatedly sampling points. When specialized to other settings, we obtain new average-case results for settings including the SE kernel with noise and the Matérn kernel with misspecification. Finally, we present algorithm-independent lower bounds that have greater generality and/or give distinct proofs compared to existing ones.