Exact sampling of determinantal point processes with sublinear time preprocessing

Michal Derezinski, Daniele Calandriello, Michal Valko

Abstract

Determinantal Point Processes (DPPs) are powerful probabilistic models for subset selection that favor diversity. However, their adoption has been limited by the high computational cost of exact sampling, typically requiring $O(n^3)$ preprocessing for $n$ items. We present DPP-VFX, an algorithm that achieves exact sampling with $n \cdot \text{poly}(k)$ preprocessing time and $\text{poly}(k)$ sampling time, where $k$ is the expected subset size. By leveraging Nyström approximations and a rejection sampling framework, DPP-VFX breaks the cubic bottleneck, enabling exact diversity-aware sampling for datasets with millions of points.

Introduction

In many machine learning applications, such as search result summarization or active learning, we seek to select a subset of items that is both high-quality and diverse. Determinantal Point Processes (DPPs) provide a mathematically elegant framework for this task. A DPP defines a distribution over subsets $S \subseteq \{1, \dots, n\}$ where the probability of selecting $S$ is proportional to $\det(\mathbf{L}_S)$, for some positive semi-definite kernel matrix $\mathbf{L}$.

Despite their elegance, the computational "tax" for exact DPP sampling is steep. Traditional methods require an eigendecomposition of $\mathbf{L}$, costing $O(n^3)$, followed by sampling procedures that often scale linearly with $n$. For large-scale datasets where $n$ reaches $10^6$, these costs are prohibitive. Previous research has often resorted to approximate methods (like MCMC) or low-rank heuristics, sacrificing the exactness of the distribution.

The DPP-VFX Algorithm

The proposed DPP-VFX (Very Fast and eXact) algorithm overcomes these limitations through a "downsample-then-correct" strategy. The core idea is to use a coarse approximation of the dataset to select a manageable intermediate subset, which is then refined to produce an exact sample from the target DPP.

The algorithm proceeds in several key stages:

  1. Nyström Approximation: Instead of the full matrix $\mathbf{L}$, the algorithm uses a Nyström approximation $\widehat{\mathbf{L}}$ to estimate Ridge Leverage Scores (RLS). These scores identify the most "informative" items in the dataset.
  2. Intermediate Sampling: Using the RLS, an intermediate set $\sigma$ is sampled. The size of this set is $O(k^2)$, which is significantly smaller than $n$ but large enough to capture the necessary diversity.
  3. Rejection Sampling: To ensure the final output follows the exact DPP distribution, a rejection sampling step is applied. The acceptance probability is calculated using the Nyström-based approximation.
Algorithm 1: The DPP-VFX sampling procedure.

Crucially, the authors prove that even with a cheap Nyström approximation, the rejection sampling loop remains highly efficient, typically requiring only a few iterations to accept a candidate.

Complexity and Theoretical Comparison

The primary contribution of DPP-VFX is its sublinear preprocessing complexity. As shown in the comparison table below, DPP-VFX is the first algorithm to achieve both exactness and a preprocessing cost that scales as $n \cdot \text{poly}(k)$ rather than $n^3$.

Comparison of complexity and exactness across different DPP sampling algorithms.

Once the initial preprocessing is complete, the cost of generating subsequent samples is $\text{poly}(k)$, making it independent of the total number of items $n$. This is a significant improvement over prior state-of-the-art samplers that required $O(n^3)$ preprocessing or had sampling times dependent on $n$ or the spectral properties of $\mathbf{L}$.

Empirical Evaluation

The authors evaluated DPP-VFX on large-scale datasets, including an "infinite" version of MNIST scaled to $n = 10^6$ points using RBF kernels.

  • Scalability: On the million-point dataset, DPP-VFX generated its first sample in approximately 68 seconds. Traditional exact samplers failed to run on much smaller subsets (e.g., $n=1.5 \cdot 10^4$) due to memory constraints.
  • Efficiency: The rejection sampling mechanism proved robust in practice. Despite the theoretical worst-case bounds for $\text{poly}(k)$, the algorithm accepted candidates quickly, often within 1-2 iterations.

Conclusion

DPP-VFX represents a significant step forward in making diverse subset selection practical for massive datasets. By combining Nyström sketching with rejection sampling, it provides the first exact sampler with sublinear preprocessing and constant-time resampling (relative to $n$). This allows researchers to apply the rigorous diversity guarantees of DPPs to problems that were previously computationally out of reach.

Summary updated

Abstract

We study the complexity of sampling from a distribution over all index subsets of the set $\{1,...,n\}$ with the probability of a subset $S$ proportional to the determinant of the submatrix $\mathbf{L}_S$ of some $n\times n$ p.s.d. matrix $\mathbf{L}$, where $\mathbf{L}_S$ corresponds to the entries of $\mathbf{L}$ indexed by $S$. Known as a determinantal point process, this distribution is used in machine learning to induce diversity in subset selection. In practice, we often wish to sample multiple subsets $S$ with small expected size $k = E[|S|] \ll n$ from a very large matrix $\mathbf{L}$, so it is important to minimize the preprocessing cost of the procedure (performed once) as well as the sampling cost (performed repeatedly). For this purpose, we propose a new algorithm which, given access to $\mathbf{L}$, samples exactly from a determinantal point process while satisfying the following two properties: (1) its preprocessing cost is $n \cdot \text{poly}(k)$, i.e., sublinear in the size of $\mathbf{L}$, and (2) its sampling cost is $\text{poly}(k)$, i.e., independent of the size of $\mathbf{L}$. Prior to our results, state-of-the-art exact samplers required $O(n^3)$ preprocessing time and sampling time linear in $n$ or dependent on the spectral properties of $\mathbf{L}$. We also give a reduction which allows using our algorithm for exact sampling from cardinality constrained determinantal point processes with $n\cdot\text{poly}(k)$ time preprocessing.
BibTeX
@inproceedings{derezinski2019exact,
  author = {Michal Derezinski and Daniele Calandriello and Michal Valko},
  title = {{Exact sampling of determinantal point processes with sublinear time preprocessing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=mmKR7YKGNZ4},
}
Figure