Martin Rouault

Martin Rouault, Rémi Bardenet, Mylène Maïda

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.

Rémi Bardenet, Mylène Maïda, Martin Rouault

Gibbs measures, such as Coulomb gases, are popular in modelling systems of interacting particles. Recently, we proposed to use Gibbs measures as randomized numerical integration algorithms with respect to a target measure $π$ on $\mathbb R^d$, following the heuristics that repulsiveness between particles should help reduce integration errors. A major issue in this approach is to tune the interaction kernel and confining potential of the Gibbs measure, so that the equilibrium measure of the system is the target distribution $π$. Doing so usually requires another Monte Carlo approximation of the \emph{potential}, i.e. the integral of the interaction kernel with respect to $π$. Using the methodology of large deviations from Garcia--Zelada (2019), we show that a random approximation of the potential preserves the fast large deviation principle that guarantees the proposed integration algorithm to outperform independent or Markov quadratures. For non-singular interaction kernels, we make minimal assumptions on this random approximation, which can be the result of a computationally cheap Monte Carlo preprocessing. For the Coulomb interaction kernel, we need the approximation to be based on another Gibbs measure, and we prove in passing a control on the uniform convergence of the approximation of the potential.