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

Guillaume Gautier, Rémi Bardenet, Michal Valko

TL;DR

This paper revisits and modernizes a forgotten 1960 Monte Carlo integration technique by Ermakov and Zolotukhin (EZ) that leverages Determinantal Point Processes (DPPs) to enforce "repulsion" between sampling points. By introducing an efficient, vectorized Python implementation for sampling multivariate Jacobi ensembles, the authors show that while a newer alternative (the BH estimator) offers steady convergence for smooth functions, the classic EZ estimator can achieve zero variance if the integrand matches the kernel's eigenfunctions—though it behaves erratically otherwise.

What Problem Does This Paper Address?

Numerical integration is a cornerstone of machine learning, especially in Bayesian inference. Standard Monte Carlo integration samples evaluation points independently, which unfortunately yields a slow variance decay rate of $\mathcal{O}(1/N)$. To accelerate this, researchers use "repulsive" point processes to ensure that sampling nodes are well-spread across the target space, mimicking deterministic quadrature rules but scaling better to multiple dimensions.

Two primary DPP-based estimators exist: the recent Bardenet-Hardy (BH) estimator, which enjoys a fast Central Limit Theorem (CLT) for smooth functions, and the older, obscure Ermakov-Zolotukhin (EZ) estimator, which requires solving a linear system. Until now, the EZ estimator lacked modern analysis and efficient sampling algorithms, leaving its practical behavior in multidimensional settings completely unknown.

Methods

The authors bridge the gap between classic numerical integration and modern point process theory through three main contributions:

  1. Modernized Proofs: Using a generalization of the Cauchy-Binet formula, the authors provide a simplified proof of the EZ estimator's properties, demonstrating that it estimates Fourier-like coefficients with uncorrelated errors.
  2. Geometric Vectorization: Instead of using algebraic Schur complements to sample the DPP, the authors reframe the problem geometrically using a base $\times$ height volume formula. This allows the sampling routine to be written as a sequential Gram-Schmidt orthogonalization of feature vectors, which is highly amenable to vectorization in Python.
  3. The DPPy Toolbox: They implement these fast sampling algorithms for a multidimensional DPP called the multivariate Jacobi ensemble, making exact continuous DPP sampling practical for the first time.

Datasets

Not discussed in the paper. The authors evaluate their methods exclusively on synthetic mathematical test functions (e.g., smooth bump functions, absolute value, Heaviside step functions, and sums of eigenfunctions).

Key Insights and Ideas

  • Perfect Interpolation (Zero Variance): The most striking property of the EZ estimator is that if the integrand is a linear combination of the first $N$ eigenfunctions of the DPP kernel, the estimator achieves exactly zero variance. A single sample configuration is enough to reconstruct the integral perfectly.
  • The Double-Edged Sword of EZ: While EZ excels when the function is sparse or has fast-decaying coefficients in the kernel's eigenbasis, it does not preserve the sign of the integrand and can exhibit erratic behavior (extreme outliers) due to the ill-conditioning of its linear system.
  • Dimensionality Degradation: As the dimension $d$ increases, the performance of the EZ estimator deteriorates on non-smooth functions because cross-terms from Taylor expansions introduce high-coefficient monomials that fall outside the span of the DPP kernel.

Key Results

  • Dramatic Speedups: The new vectorized implementation reduces the time required to sample a 2D Jacobi ensemble with $N = 1000$ points from several hours to less than a minute.
  • Empirical Variance Verification: In the smooth "bump" function experiment, the EZ estimator dramatically outperforms both vanilla Monte Carlo and the BH estimator in lower dimensions ($d \le 2$).
Figure 2: (a)-(d) cf. Section 4.1, the numbers in the legend are the slope and R2 (e)-(h) cf. Section 4.2.

As seen in the figure above, when integrating a finite sum of 70 eigenfunctions (plots e-h), the EZ estimator's variance drops to zero the moment $N \ge 70$, empirically validating the authors' theoretical claims.

Limitations and Future Work

  • No CLT for EZ: Establishing a Central Limit Theorem for the EZ estimator remains an open, technically daunting challenge because each quadrature weight depends globally on all other quadrature nodes.
  • Sensitivity to Non-Smoothness: The EZ estimator is fragile when dealing with discontinuities (like the Heaviside step function). Its variance explodes because approximating such functions requires high-frequency components outside the kernel's span.
  • Outlier Vulnerability: Ill-conditioning of the linear system frequently introduces extreme outliers in higher dimensions ($d \ge 3$). The authors suggest that exploring regularization techniques to stabilize the linear system without introducing severe bias is a promising direction for future research.

Summary updated

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.
BibTeX
@inproceedings{gautier2019two,
  author = {Guillaume Gautier and Rémi Bardenet and Michal Valko},
  title = {{On two ways to use determinantal point processes for Monte Carlo integration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=gC2F_ZHe1cA},
}

Loading related content...

Figure