Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding
This work addresses a theoretical gap for researchers in probabilistic quadrature and Bayesian inference, offering incremental progress by providing initial guarantees for kernel herding variants.
The paper tackles the lack of theoretical support for the conjectured fast convergence rate of kernel herding quadrature methods in infinite-dimensional RKHS, proving that a joint probability distribution over nodes yields a tighter concentration inequality on worst-case integration error compared to i.i.d. Monte Carlo, with toy examples suggesting a likely faster convergence rate.
Kernel herding belongs to a family of deterministic quadratures that seek to minimize the worst-case integration error over a reproducing kernel Hilbert space (RKHS). These quadrature rules come with strong experimental evidence that this worst-case error decreases at a faster rate than the standard square root of the number of quadrature nodes. This conjectured fast rate is key for integrating expensive-to-evaluate functions, as in Bayesian inference of expensive models, and makes up for the increased computational cost of sampling, compared to i.i.d. or MCMC quadratures. However, there is little theoretical support for this faster-than-square-root rate, at least in the usual case where the RKHS is infinite-dimensional, while recent progress on distribution compression suggests that results on the direct minimization of worst-case integration are possible. In this paper, we study a joint probability distribution over quadrature nodes, whose support tends to minimize the same worst-case error as kernel herding. Our main contribution is to prove that it does outperform i.i.d Monte Carlo, in the sense of coming with a tighter concentration inequality on the worst-case integration error. This first step towards proving a fast error decay demonstrates that the mathematical toolbox developed around Gibbs measures can help understand to what extent kernel herding and its variants improve on computationally cheaper methods. Moreover, we investigate the computational bottlenecks of approximately sampling our quadrature, and we demonstrate on toy examples that a faster rate of convergence, though not worst-case, is likely.