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, stochastic optimization, active learning 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"ive 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 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.
The Challenge of Scalability in DPPs
Determinantal Point Processes (DPPs) are elegant probabilistic models used to select a diverse subset of items from a large pool—such as picking representative frames from a video or diverse products for a recommendation carousel. A $k$-DPP specifically selects a subset of exactly $k$ items.
The primary challenge is scalability. Traditional exact sampling requires an eigendecomposition of an $n \times n$ kernel matrix, costing $O(n^3)$, which is prohibitive for large $n$. Recent state-of-the-art methods like DPP-VFX reduced this to $O(n \cdot \text{poly}(k))$, but they still face a major bottleneck: they must compute marginal probabilities for every single one of the $n$ items. This paper introduces $\alpha$-DPP, the first algorithm capable of exact sampling from a $k$-DPP without needing to observe every item in the dataset.
Methodology: The $\alpha$-DPP Algorithm
The authors propose a two-stage approach centered on the $\alpha$-DPP algorithm:
- Uniform Intermediate Sampling: Instead of computing marginals for all $n$ items, the algorithm first takes a uniform random sample of the data. Theoretical guarantees ensure that if the dataset is naturally diverse (high "effective dimension"), a sufficiently large uniform sample contains enough information to reconstruct the target DPP distribution.
- Binary Search for Rescaling: Sampling a fixed-size $k$-DPP is harder than sampling a random-size DPP. To bridge this gap, the kernel matrix is rescaled by a factor $\alpha$ to shift the expected sample size toward $k$. This paper introduces a robust binary search that finds an optimal $\alpha$ in just $O(\sqrt{k})$ iterations, allowing for efficient rejection sampling to obtain exactly $k$ items.
Crucially, the algorithm uses rejection sampling steps to ensure that even though it uses approximations and subsamples, the final output is exactly distributed according to the target $k$-DPP.
Empirical Performance and Efficiency
The approach was evaluated using Infinite MNIST, a synthetic expansion of the classic handwritten digit dataset, scaling $n$ up to $1,000,000$ items with both RBF and Linear kernels. The results demonstrate a "computational free lunch": if the target size $k$ is much smaller than the dataset's inherent diversity, we can ignore most of the data without losing exactness.
As shown in the runtime analysis, $\alpha$-DPP achieves orders-of-magnitude speedups over the previous state-of-the-art (DPP-VFX). For very large datasets, the runtime of $\alpha$-DPP stays nearly flat as the dataset grows from $200,000$ to $1,000,000$ items, whereas competing methods continue to slow down linearly.
This efficiency is driven by the sublinear nature of the algorithm. For the largest MNIST experiments ($n=10^6, k=10$), the algorithm only needed to observe about 1% of the items ($\beta \approx 0.01$) to produce an exact sample. This significantly reduces memory traffic, which is a common bottleneck in large-scale machine learning.
Conclusion and Future Directions
$\alpha$-DPP provides a distortion-free method for large-scale sampling. Unlike MCMC methods, which only converge over time, this algorithm is guaranteed to return a correct sample if it returns one at all.
Future work may address current limitations, such as the reliance on a bounded similarity assumption ($\kappa^2$). If this bound is loose, the efficiency gains may diminish. The authors suggest that adaptive upper bounds on marginals could further enhance performance for kernels where uniform sampling is less effective.
Summary updated