Sampling from a k-DPP without looking at all items

Daniele Calandriello, Michal Derezinski, Michal Valko

Introduction

Determinantal Point Processes (DPPs) are widely considered the "gold standard" for selecting a subset of items that are both high-quality and diverse. They have broad applications in machine learning, from picking diverse news articles out of millions to summarizing large video datasets. However, $k$-DPPs—which constrain the selection to a fixed number of items $k$—suffer from a massive scalability wall.

This paper presents $\alpha$-DPP, the first algorithm capable of sampling exactly from a $k$-DPP without needing to process, or even look at, the entire dataset. By combining uniform intermediate sampling with a novel binary search reduction, the algorithm achieves orders-of-magnitude speedups on large datasets. In many cases, it observes as little as 1% of the total items while maintaining perfect sampling accuracy.

The Scalability Bottleneck

Standard exact algorithms for $k$-DPPs require at least one full pass over all $n$ items to compute "marginals" (the probability of each item being included). When $n$ is in the millions, this $O(n)$ bottleneck makes real-time recommendation or large-scale summarization practically impossible.

Theoretical complexity comparison of k-DPP sampling algorithms.

Previous "fast" methods either relied on approximations (like MCMC), which are hard to verify, or still required looking at every single item at least once. The core challenge is breaking this $O(n)$ barrier without sacrificing the exactness of the target distribution.

Methods: Breaking the $O(n)$ Barrier

The authors introduce two major algorithmic innovations to bypass the need to evaluate every item:

  1. Uniform Intermediate Sampling ($\alpha$-DPP): Instead of computing exact marginals for all $n$ items, the algorithm starts by taking a "blind" uniform sample of the data. It then uses a small "dictionary" (a subset of the data) to approximate the marginals only for those uniformly selected items. Through a clever rejection sampling scheme, the authors prove that this process results in a sample drawn exactly from the target distribution, provided the kernel's maximum similarity is bounded.
  2. Binary Search for Rescaling: A $k$-DPP is often sampled by "rescaling" a standard DPP until its expected size is $k$. Previous methods used expensive optimization to find this scale factor $\alpha$. This paper proves that a simple binary search, requiring only $O(\sqrt{k})$ calls to the sampler, is sufficient to find a valid $\alpha$ that ensures high acceptance rates.

The underlying "magic" here relies on a computational free lunch: if the dataset is naturally very diverse (i.e., it has a high effective dimension), the algorithm can ignore the vast majority of items. Any sufficiently large random subset will contain enough diverse candidates to satisfy the $k$-DPP requirements.

Key Results and Insights

The authors evaluated their approach using the Infinite MNIST dataset (a synthetic expansion of the classic handwritten digit dataset) and RBF Kernels to define image similarity. They tested subsets ranging from small scales up to $n = 10^6$ items.

Runtime comparison on the Infinite MNIST dataset up to 1 million items. Notice the near-constant scaling of alpha-DPP.
  • Constant Scaling: On the large-scale MNIST experiment ($n=10^6$), the runtime of $\alpha$-DPP remained almost flat as $n$ increased. In contrast, the previous state-of-the-art (DPP-VFX) grew linearly.
  • Data Efficiency: For $n=10^6$, the algorithm only had to "look" at roughly 1% of the data to produce an exact $k$-DPP sample. This proves that sub-linear sampling is possible: you don't need to know the "importance" of every item to pick a diverse set.
  • Exactness via Rejection: Unlike MCMC methods that only approach the right distribution, $\alpha$-DPP uses rejection sampling to ensure the final output is mathematically perfect, even though the intermediate steps use approximations.

Limitations and Future Work

While highly efficient, the current proof relies on the similarity kernel having a bounded maximum entry ($\kappa^2$). While this holds true for Gaussian/RBF kernels, it might be a loose bound for linear kernels, potentially reducing the speedup. Additionally, because it relies on rejection sampling, the runtime can be "jittery." The authors noted that $\alpha$-DPP requires 2-5x more trials in the rejection step than some competitors, leading to higher variance in execution time.

Future work could replace the initial "uniform" sampling with more sophisticated, multi-level filtering (e.g., using random projections) to further prune the search space and stabilize runtime variance.

Implementation available at: https://github.com/guilgautier/DPPy/

Summary updated

Abstract

Determinantal point processes (DPPs) are a useful probabilistic model for selecting a small diverse subset out of a large collection of items, with applications in summarization, recommendation, stochastic optimization, experimental design and more. Given a kernel function and a subset size k, our goal is to sample k out of n items with probability proportional to the determinant of the kernel matrix induced by the subset (a.k.a. k-DPP). Existing k-DPP sampling algorithms require an expensive preprocessing step which involves multiple passes over all n items, making it infeasible for large datasets. A naïve heuristic addressing this problem is to uniformly subsample a fraction of the data and perform k-DPP sampling only on those items, however this method offers no guarantee that the produced sample will even approximately resemble the target distribution over the original dataset. In this paper, we develop alpha-DPP, an algorithm which adaptively builds a sufficiently large uniform sample of data that is then used to efficiently generate a smaller set of k items, while ensuring that this set is drawn exactly from the target distribution defined on all n items. We show empirically that our algorithm produces a k-DPP sample after observing only a small fraction of all elements, leading to several orders of magnitude faster performance compared to the state-of-the-art. Our implementation of alpha-DPP is provided at https://github.com/guilgautier/DPPy/.
BibTeX
@inproceedings{calandriello2020sampling,
  author = {Daniele Calandriello and Michal Derezinski and Michal Valko},
  title = {{Sampling from a k-DPP without looking at all items}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=o7HL79fZ94},
}
Figure