# Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 57 references that are in the map.
- First posted on arXiv 6 Sep 2026.

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

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Distributed k-Means and k-Median Clustering on General Topologies](https://mlsanity.com/paper/1306.0604/) (2013)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Monte Carlo with Determinantal Point Processes](https://mlsanity.com/paper/1605.00361/) (2016)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD](https://mlsanity.com/paper/2112.06007/) (2021)
- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [On Optimal Coreset Construction for Euclidean (k,z)-Clustering](https://mlsanity.com/paper/2211.11923/) (2022)
- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds](https://mlsanity.com/paper/2405.01339/) (2024)
- [Small coresets via negative dependence: DPPs, linear statistics, and concentration](https://mlsanity.com/paper/2411.00611/) (2024)
- [On Coresets for Clustering in Small Dimensional Euclidean Spaces](https://mlsanity.com/paper/2302.13737/) (2023)
- [Negative Dependence as a toolbox for machine learning : review and new developments](https://mlsanity.com/paper/2502.07285/) (2025)
- [Generalization Performance of Ensemble Clustering: From Theory to Algorithm](https://mlsanity.com/paper/2506.02053/) (2025)

## Abstract (arXiv)

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an textitε-coreset: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the textit(k,z)-clustering problem, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called textitdeterminantal sampling, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible varepsilon-coreset for (k,z)-clustering in mathbb Rd whose dependence on 1/varepsilon has exponent strictly smaller than 2 when d is fixed. This improves over the worst-case varepsilon-2 barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.