# Small coresets via negative dependence: DPPs, linear statistics, and concentration

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 1 Nov 2024.

## Builds on (most cited first, 13 of 13)

- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Monte Carlo with Determinantal Point Processes](https://mlsanity.com/paper/1605.00361/) (2016)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Bayesian experimental design using regularized determinantal point processes](https://mlsanity.com/paper/1906.04133/) (2019)
- [Distributed estimation of the inverse Hessian by determinantal averaging](https://mlsanity.com/paper/1905.11546/) (2019)
- [Learning Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/1905.12962/) (2019)
- [Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2006.09862/) (2020)
- [Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD](https://mlsanity.com/paper/2112.06007/) (2021)
- [A determinantal point process for column subset selection](https://mlsanity.com/paper/1812.09771/) (2018)
- [On Optimal Coreset Construction for Euclidean (k,z)-Clustering](https://mlsanity.com/paper/2211.11923/) (2022)
- [Gaussian Determinantal Processes: a new model for directionality in data](https://mlsanity.com/paper/2111.09990/) (2021)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)

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

- [How Reliable is Language Model Micro-Benchmarking?](https://mlsanity.com/paper/2510.08730/) (2025)
- [Group-invariant Coresets for Data-efficient Active Learning](https://mlsanity.com/paper/2607.01089/) (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)

## Abstract (arXiv)

Determinantal point processes (DPPs) are random configurations of points with tunable negative dependence. Because sampling is tractable, DPPs are natural candidates for subsampling tasks, such as minibatch selection or coreset construction. A coreset is a subset of a (large) training set, such that minimizing an empirical loss averaged over the coreset is a controlled replacement for the intractable minimization of the original empirical loss. Typically, the control takes the form of a guarantee that the average loss over the coreset approximates the total loss uniformly across the parameter space. Recent work has provided significant empirical support in favor of using DPPs to build randomized coresets, coupled with interesting theoretical results that are suggestive but leave some key questions unanswered. In particular, the central question of whether the cardinality of a DPP-based coreset is fundamentally smaller than one based on independent sampling remained open. In this paper, we answer this question in the affirmative, demonstrating that DPPs can provably outperform independently drawn coresets. In this vein, we contribute a conceptual understanding of coreset loss as a linear statistic of the (random) coreset. We leverage this structural observation to connect the coresets problem to a more general problem of concentration phenomena for linear statistics of DPPs, wherein we obtain effective concentration inequalities that extend well-beyond the state-of-the-art, encompassing general non-projection, even non-symmetric kernels. The latter have been recently shown to be of interest in machine learning beyond coresets, but come with a limited theoretical toolbox, to the extension of which our result contributes. Finally, we are also able to address the coresets problem for vector-valued objective functions, a novelty in the coresets literature.