Determinantal sampling on general spaces: fast approximation via diffusion geometry

Abstract

Determinantal point processes (DPPs) 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. 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 be tailored to particular 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, focussing on spectral kernels obtained from eigenspaces of naturally associated Markov diffusion operators, including in particular the Laplacian on manifolds and nearest-neighbour type graphs on data point clouds and the discrete Schrodinger operator on large scale networks. This covers, in particular, the settings of Riemannian manifolds and discrete networks, as well as the problem of batch sampling from discrete datasets. Overall, our approach achieves guarantees comparable to $(\text{sample size}{)}^{-\frac{1}{2}-\frac{1}{2d_{\text{int}}}}$ , which match with the rates for well-known determinantal samplers on Euclidean spaces of comparable dimension. In terms of techniques, we connect to the celebrated Weyl's Law for spectra on general spaces, and leverage tools from the theory of Markov diffusion operators and Dirichlet forms, which could be of independent interest in this area. Our approach is applicable to a very wide plethora of ambient spaces beyond Euclidean as soon as these ingredients are available, including e.g. fractals, leading to guarantees that will be governed by the intrinsic structural constants of such spaces.

arXiv commentAbstract shortened to meet arXiv requirements