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

Guillaume Gautier; Rémi Bardenet; Michal Valko

cs.LGApr 21, 2026

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

Authors: Guillaume Gautier, Rémi Bardenet, Michal Valko

Organizations: †Univ. Lille, CNRS, Centrale Lille, UMR 9189 – CRIStAL, 59651 Villeneuve d’Ascq, France · *Inria Lille-Nord Europe, 40 avenue Halley 59650 Villeneuve d’Ascq, France · ‡DeepMind Paris, 14 Rue de Londres, 75009 Paris, France · ∗Inria Lille-Nord Europe, 40 avenue Halley 59650 Villeneuve d’Ascq, France

Abstract

The standard Monte Carlo estimator $\widehat{I}_N^{\mathrm{MC}}$ of $\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.

Explore similar work

Fast determinantal sampling on general spaces and diffusion geometry
Jul 7, 2026Hoang-Son Tran, Pranav Gupta, Subhroshekhar GhoshDeterminantal Point Process Optimal Sample Complexity
State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives
May 13, 2026Hoang-Son Tran, Pranav Gupta, Rémi Bardenet +1Mini-Batch Stochastic Gradient Descent Subsampling
Variance Reduction for Independent Metropolis
Jun 25, 2024Siran Liu, Petros Dellaportas, Michalis K. TitsiasVariance Reduction

Jul 7, 2026 · stat.MLJ/K move · Enter open · S save

Fast determinantal sampling on general spaces and diffusion geometry

Hoang-Son Tran, Pranav Gupta, Subhroshekhar Ghosh

Department of Mathematics National University of Singapore

Determinantal point processes have recently emerged as a kernel-based alternative to standard independent sampling for constructing efficient minibatches, coresets, and other compact representations of large-scale datasets. In particular, sampling mechanisms based on DPPs are believed to demonstrate better approximation properties compared to classical i.i.d. samplers, even at the scale of the exponent. One of the key strengths of DPP based samplers is that they can be deployed over very general spaces, in contrast to more classical sampling methods beyond i.i.d. which tend to work in very well-structured settings, principally Euclidean spaces. In this work, we establish explicit rate guarantees for determinantal sampling in spaces that extend far beyond known Euclidean setups, focusing on spectral kernels obtained from eigenspaces of naturally associated Laplacian and other Markov diffusion operators. This includes, in particular, Riemannian manifolds and weighted networks. In determinantal sampling from compact Riemannian manifolds, we establish sampling rates that automatically pick up the intrinsic dimensionality

d_{\text{int}}

of the underlying manifold. In the setting of networks, we investigate DPP-based samplers on the celebrated k-nearest neighbour graphs, as well as weighted random geometric graphs, and demonstrate a similar improved dependence on the intrinsic dimensionality of the data. Overall, our approach achieves guarantees of

\big(\text{sample size}\big)^{-\frac{1}{2}-\frac{1}{2d_{\text{int}}}}

that match known rates on Euclidean spaces of comparable dimension. In terms of techniques, we connect to the celebrated Weyl's Law for manifold spectra, and leverage tools from the theory of Markov diffusions and Dirichlet forms as well as certain ingredients from the theory of pseudodifferential operators, which could be of independent interest in this area.

Determinantal Point Process Optimal Sample Complexity Exponential Random Graph Models Gibbs Measures

Open paper Ask about it PDF

Abstract

Explore similar work

Fast determinantal sampling on general spaces and diffusion geometry

State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives

Variance Reduction for Independent Metropolis