Kernel interpolation with continuous volume sampling
This work provides a theoretical foundation for kernel methods in machine learning, offering a generalizable solution for function approximation tasks like density estimation and quadrature, though it is incremental as it builds on existing discrete sampling concepts.
The paper tackles the problem of selecting nodes and weights for kernel interpolation and quadrature by introducing continuous volume sampling, a method applicable to any Mercer kernel. The authors prove almost optimal theoretical bounds for interpolation and quadrature under this approach, with bounds depending on the spectrum of the associated integration operator.
A fundamental task in kernel methods is to pick nodes and weights, so as to approximate a given function from an RKHS by the weighted sum of kernel translates located at the nodes. This is the crux of kernel density estimation, kernel quadrature, or interpolation from discrete samples. Furthermore, RKHSs offer a convenient mathematical and computational framework. We introduce and analyse continuous volume sampling (VS), the continuous counterpart -- for choosing node locations -- of a discrete distribution introduced in (Deshpande & Vempala, 2006). Our contribution is theoretical: we prove almost optimal bounds for interpolation and quadrature under VS. While similar bounds already exist for some specific RKHSs using ad-hoc node constructions, VS offers bounds that apply to any Mercer kernel and depend on the spectrum of the associated integration operator. We emphasize that, unlike previous randomized approaches that rely on regularized leverage scores or determinantal point processes, evaluating the pdf of VS only requires pointwise evaluations of the kernel. VS is thus naturally amenable to MCMC samplers.