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:
- 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.
- 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.
- 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.
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$.
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