Selecting a diverse subset of items from a massive dataset is a common but computationally heavy task in machine learning. Whether picking representative images for a summary or diverse products for a recommendation, Determinantal Point Processes (DPPs) are the gold standard. They mathematically favor subsets where items are dissimilar, naturally inducing diversity.
However, DPPs have historically come with a massive "scalability tax." This NeurIPS 2019 paper introduces a breakthrough algorithm called DPP-VFX (Very Fast and eXact), which solves this long-standing efficiency bottleneck, making diverse subset selection practical for million-scale datasets.
The Scalability Tax of Traditional DPPs
To sample exactly from a DPP over $n$ items, standard algorithms require an eigendecomposition of an $n \times n$ matrix. This operation costs $O(n^3)$. If you have a dataset of a million items, $n^3$ is computationally astronomical. Even "fast" approximate methods often have costs that scale linearly with $n$ for every single sample you draw.
The primary goal of the authors was to break this $n$-dependency, shifting the computational bottleneck from the size of the database ($n$) to the size of the subset you actually want to extract ($k$).
The DPP-VFX Algorithm
DPP-VFX achieves exact sampling with sublinear preprocessing time and a sampling cost that is independent of the total dataset size. It relies on a clever "downsample-then-correct" strategy:
- Nyström Approximation: Instead of evaluating the full $n \times n$ matrix $L$, the algorithm uses a small, representative subset of columns to create a computationally "cheap" approximation.
- Intermediate Downsampling: Using this approximation, it computes Ridge Leverage Scores (RLS). These scores indicate which items are most "important" or "unique." The algorithm then draws an intermediate sample $\sigma$ that is much smaller than $n$ but slightly larger than the target subset size $k$.
- Rejection Sampling: Because the intermediate sample is based on an approximation, it carries a slight bias. The algorithm uses a rejection sampling step to correct this. If a sample is rejected, it tries again; if accepted, the result is mathematically guaranteed to be exactly from the true DPP distribution.
- $k$-DPP Reduction: The paper also provides a reduction technique to use this same logic for $k$-DPPs, where the user wants a subset of a specific, fixed size $k$.
Key Results and Performance
The theoretical advancements of DPP-VFX are best understood by comparing its computational complexity to prior state-of-the-art methods.
As shown above, prior exact samplers required $O(n^3)$ preprocessing time. DPP-VFX reduces the first sample cost to $n \cdot \text{poly}(k)$ and makes subsequent samples entirely independent of $n$ (costing only $\text{poly}(k)$).
To test these theoretical bounds in practice, the authors evaluated DPP-VFX using the MNIST8M dataset, varying the ground set size $n$ from $1,000$ up to $1,000,000$.
- Massive Speedups: On a dataset of 70,000 items, a standard MCMC (Markov Chain Monte Carlo) sampler took 160 seconds to produce a sample. DPP-VFX accomplished the same task in just 16 seconds—an order of magnitude faster.
- Constant-Time Resampling: Once the initial preprocessing is complete, generating additional samples takes a constant amount of time dependent only on $k$.
- Unprecedented Scalability: The authors successfully demonstrated exact sampling on $n=1,000,000$ items, a feat previously considered computationally prohibitive for exact DPPs.
Insights and Limitations
One of the core insights of this paper is that exactness is not a luxury. Many researchers default to approximate MCMC methods for speed, but these can take a long time to converge and lack hard mathematical guarantees. DPP-VFX proves that with the right leverage score approximations, you can have both speed and exactness.
Furthermore, previous fast methods required the data matrix to be strictly "low-rank." DPP-VFX only requires the matrix to exhibit "eigenvalue decay" (where a few dimensions capture most of the variation), a property true of almost all real-world datasets.
Limitations to consider: * The $k^3$ Factor: While the algorithm is independent of $n$, it scales cubically (or higher) with $k$, the expected subset size. For extremely large subsets (e.g., $k=10,000$), the $\text{poly}(k)$ terms become the new bottleneck. * Theoretical vs. Practical Bounds: The theoretical proofs suggest a Nyström subset size of $O(k^3 \log n)$ is needed for efficient rejection sampling. However, in practice, the authors found that a size of $10k$ was often sufficient, indicating the theoretical bounds may be overly conservative.
For practitioners looking to leverage these speedups, the authors have integrated DPP-VFX into the open-source DPPy Python library, making it readily accessible for tasks like experimental design and Gaussian Process scaling.
Summary updated