# Sampling from a k-DPP without looking at all items

arXiv: https://arxiv.org/abs/2006.16947 · HTML: https://mlsanity.com/paper/2006.16947/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

## Built on by (most cited first, 17 of 17)

- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Improved Financial Forecasting via Quantum Machine Learning](https://mlsanity.com/paper/2306.12965/) (2023)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [RD-DPP: Rate-Distortion Theory Meets Determinantal Point Process to Diversify Learning Data Samples](https://mlsanity.com/paper/2304.04137/) (2023)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Learning on Bandwidth Constrained Multi-Source Data with MIMO-inspired DPP MAP Inference](https://mlsanity.com/paper/2306.02497/) (2023)
- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [Diverse Mini-Batch Selection in Reinforcement Learning for Efficient Chemical Exploration in de novo Drug Design](https://mlsanity.com/paper/2506.21158/) (2025)
- [Diversified recommendations of cultural activities with personalized determinantal point processes](https://mlsanity.com/paper/2509.10392/) (2025)
- [Bandit Guided Submodular Curriculum for Adaptive Subset Selection](https://mlsanity.com/paper/2511.22944/) (2025)
- [Adaptive Quality-Diversity Trade-offs for Large-Scale Batch Recommendation](https://mlsanity.com/paper/2602.02024/) (2026)

## Abstract (arXiv)

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.