New DPP Sampling Method Matches Euclidean Rates on Manifolds and Networks

Determinantal point processes (DPPs) have emerged as a powerful alternative to independent sampling for constructing efficient minibatches and coresets, offering better approximation properties even at the exponent scale. However, existing DPP theory and guarantees were largely limited to Euclidean spaces. Now, Hoang-Son Tran, Pranav Gupta, and Subhroshekhar Ghosh have extended DPP sampling to much more general spaces, including compact Riemannian manifolds and weighted networks (e.g., k-nearest neighbor graphs). Their approach uses spectral kernels derived from eigenspaces of Laplacian and Markov diffusion operators.

On compact Riemannian manifolds, the sampler automatically captures the intrinsic dimensionality d_int, achieving a rate of (sample size)^{-1/2 - 1/(2d_int)} — matching the known optimal rate in Euclidean spaces of comparable dimension. For networks, the authors demonstrate similar improvements on k-nearest neighbor graphs and weighted random geometric graphs. The technical machinery connects to Weyl's law for manifold spectra, Markov diffusion theory, and pseudodifferential operators, providing a theoretical foundation that could unlock DPP-based sampling for non-Euclidean datasets common in machine learning, such as graph-structured data and manifold-embedded features.