Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding

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

cs.LGFeb 18, 2024

Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding

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

Organizations: 1Univ. Lille, CNRS, Centrale Lille, UMR 9189 – CRIStAL, 59651 Villeneuve d’Ascq, France · 2Univ. Lille, CNRS, UMR 8524 – Laboratoire Paul Painlev´e, F-59000 Lille, France

Abstract

Kernel herding belongs to a family of deterministic quadratures that seek to minimize the maximum mean discrepancy (MMD), that is, the worst-case integration error over a reproducing kernel Hilbert space (RKHS). These MMD minimization procedures come with strong experimental support, but comparatively less theoretical footing. In particular, apart from recent progress in distribution compression, little has been proved in favor of an improvement of MMD minimization over classical Monte Carlo quadrature when the RKHS is infinite-dimensional. In this paper, we study a joint probability distribution over quadrature nodes, a tailored Gibbs distribution, whose support intuitively tends to concentrate around MMD minimizers as a temperature parameter is decreased. Our main contribution is to prove that drawing integration nodes from our distribution does outperform i.i.d Monte Carlo. While our bounds on the worst-case integration error feature the same rate as i.i.d. Monte Carlo, we do obtain a tighter concentration inequality as the temperature parameter decreases. This means smaller confidence intervals as the number of quadrature nodes increases. While arguably a first step, our results demonstrate that the mathematical toolbox developed around Gibbs measures can help understand to what extent kernel herding and its variants improve on computationally cheaper methods. There remains the issue of sampling from our Gibbs distribution. In our numerical experiments, we demonstrate that a simple MCMC chain already yields approximate samples that lead to improved confidence intervals around the target integrals, as supported by our theoretical results.

Explore similar work

Aug 2, 2025cs.LG

Quenched large deviations for Monte Carlo integration with Coulomb gases

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

π

\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.

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

Gibbs Measures Monte Carlo Iterative

Ask PDF

Apr 21, 2026cs.LG

On two ways to use determinantal point processes for Monte Carlo integration

The standard Monte Carlo estimator

\widehat{I}_N^{\mathrm{MC}}

\int fdω

relies on independent samples from

ω

and has variance of order

1/N

. Replacing the samples with a determinantal point process (DPP), a repulsive distribution, makes the estimator consistent, with variance rates that depend on how the DPP is adapted to

f

and

ω

. We examine two existing DPP-based estimators: one by Bardenet & Hardy (2020) with a rate of

\mathcal{O}(N^{-(1+1/d)})

for smooth

f

, but relying on a fixed DPP. The other, by Ermakov & Zolotukhin (1960), is unbiased with rate of order

1/N

, like Monte Carlo, but its DPP is tailored to

f

. We revisit these estimators, generalize them to continuous settings, and provide sampling algorithms.

Guillaume Gautier, Rémi Bardenet, Michal Valko

Determinantal Point Process Monte Carlo Estimators Rotational Repulsion Mechanism

Ask PDF

May 7, 2026math.NA

Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature

Kernel quadrature can exploit RKHS spectral structure and outperform Monte Carlo on smooth integrands, but optimized quadrature weights are generally signed and may be numerically unstable. We study whether spectral acceleration remains possible when the weights are constrained to be positive, i.e., simplex weights. In the exact-target fixed-pool setting, an evaluated i.i.d. candidate pool of size

N

is already available and the task is to reweight it so as to approximate the kernel mean embedding. We show that this positive reweighting problem is governed not by the equal-weight empirical average, but by the random convex hull generated by the pool. Our main geometric result shows that the mean of a bounded

d

-dimensional random vector can be approximated by a convex combination of

N

i.i.d. samples at accuracy

O(d/N)

with high probability, sharper than equal-weight averaging in the fixed-dimensional regime. We transfer this

d

-dimensional convex-hull approximation to full RKHS worst-case error through an augmented Mercer-truncation argument. The resulting positive-weight KQ bounds consist of a spectral tail term and a finite-sample convex-hull term, yielding Monte-Carlo-beating rates in favorable spectral regimes, including near-

O(1/N)

rates up to logarithmic factors under exponential spectral decay. We also provide a constructive Frank--Wolfe algorithm that operates directly on the pool atoms, maintains simplex weights, and admits an explicit optimization-error bound.

Satoshi Hayakawa

Kernel Hilbert Spaces Convex Sets Concentration Inequalities Bayesian Quadrature Spectral Norm Upper Bounds+1

Ask PDF