Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes
A determinantal point process (DPP) is an elegant model that assigns a
probability to every subset of a collection of $n$ items. While conventionally
a DPP is parameterized by a symmetric kernel matrix, removing this symmetry
constraint, resulting in nonsymmetric DPPs (NDPPs), leads to significant
improvements in modeling power and predictive performance. Recent work has
studied an approximate Markov chain Monte Carlo (MCMC) sampling algorithm for
NDPPs restricted to size-$k$ subsets (called $k$-NDPPs). However, the runtime
of this approach is quadratic in $n$, making it infeasible for large-scale
settings. In this work, we develop a scalable MCMC sampling algorithm for
$k$-NDPPs with low-rank kernels, thus enabling runtime that is sublinear in
$n$. Our method is based on a state-of-the-art NDPP rejection sampling
algorithm, which we enhance with a novel approach for efficiently constructing
the proposal distribution. Furthermore, we extend our scalable $k$-NDPP
sampling algorithm to NDPPs without size constraints. Our resulting sampling
method has polynomial time complexity in the rank of the kernel, while the
existing approach has runtime that is exponential in the rank. With both a
theoretical analysis and experiments on real-world datasets, we verify that our
scalable approximate sampling algorithms are orders of magnitude faster than
existing sampling approaches for $k$-NDPPs and NDPPs.