# Determinantal Point Processes for Coresets

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2018.

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

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [DGR-MIL: Exploring Diverse Global Representation in Multiple Instance Learning for Whole Slide Image Classification](https://mlsanity.com/paper/2407.03575/) (2024)
- [Diversified Batch Selection for Training Acceleration](https://mlsanity.com/paper/2406.04872/) (2024)
- [Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD](https://mlsanity.com/paper/2112.06007/) (2021)
- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)
- [RD-DPP: Rate-Distortion Theory Meets Determinantal Point Process to Diversify Learning Data Samples](https://mlsanity.com/paper/2304.04137/) (2023)
- [Small coresets via negative dependence: DPPs, linear statistics, and concentration](https://mlsanity.com/paper/2411.00611/) (2024)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [DPPMask: Masked Image Modeling with Determinantal Point Processes](https://mlsanity.com/paper/2303.12736/) (2023)
- [On sampling determinantal and Pfaffian point processes on a quantum computer](https://mlsanity.com/paper/2305.15851/) (2023)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Coreset selection based on Intra-class diversity](https://mlsanity.com/paper/2509.21380/) (2025)
- [Adaptive Quality-Diversity Trade-offs for Large-Scale Batch Recommendation](https://mlsanity.com/paper/2602.02024/) (2026)
- [Fast determinantal sampling on general spaces and diffusion geometry](https://mlsanity.com/paper/2607.06644/) (2026)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)
- [When Less Data Favors Smaller Teachers: Rethinking Teacher Capacity and Data Selection for Knowledge Distillation](https://mlsanity.com/paper/2609.34489/) (2026)

## Abstract (arXiv)

When faced with a data set too large to be processed all at once, an obvious solution is to retain only part of it. In practice this takes a wide variety of different forms, and among them "coresets" are especially appealing. A coreset is a (small) weighted sample of the original data that comes with the following guarantee: a cost function can be evaluated on the smaller set instead of the larger one, with low relative error. For some classes of problems, and via a careful choice of sampling distribution (based on the so-called "sensitivity" metric), iid random sampling has turned to be one of the most successful methods for building coresets efficiently. However, independent samples are sometimes overly redundant, and one could hope that enforcing diversity would lead to better performance. The difficulty lies in proving coreset properties in non-iid samples. We show that the coreset property holds for samples formed with determinantal point processes (DPP). DPPs are interesting because they are a rare example of repulsive point processes with tractable theoretical properties, enabling us to prove general coreset theorems. We apply our results to both the k-means and the linear regression problems, and give extensive empirical evidence that the small additional computational cost of DPP sampling comes with superior performance over its iid counterpart. Of independent interest, we also provide analytical formulas for the sensitivity in the linear regression and 1-means cases.