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.

本文提出了一种基于状态较好的拒绝抽样算法的可扩展 MCMC 采样算法，用于 kdeterminantal point process，使其在低秩核下的运行时间为 n 的次幂；进一步将其扩展到没有大小限制的 NDPP。实验结果表明，我们的方法比现有的采样方法快得多。