Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling
Abstract
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 \textit{determinantal sampling}, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible ε-coreset for (k,z)-clustering in ℝd whose dependence on 1/ε has exponent strictly smaller than $2$ when d is fixed. This improves over the worst-case ε−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.
Related
- Determinantal sampling on general spaces: fast approximation via diffusion geometry
- Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
- L2-error bounds for covariation estimation under asynchronous mixed time-space sampling
- Low-degree polynomials lower bounds for clustering in small dimension
- Wasserstein Bounds for Euler and Randomized Midpoint Langevin Sampling with Noisy Gradients
BibTeX
@misc{chakraborty2026beyond,
title = {{Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling}},
author = {Diptarka Chakraborty and Satyaki Mukherjee and Gaurav Vallabhdas Revankar and Hoang-Son Tran},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06394},
eprint = {2609.06394},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06394},
}
RIS
TY - UNPB
TI - Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling
AU - Diptarka Chakraborty
AU - Satyaki Mukherjee
AU - Gaurav Vallabhdas Revankar
AU - Hoang-Son Tran
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06394
UR - https://arxiv.org/abs/2609.06394
AB - 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 \textit{determinantal sampling}, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible ε-coreset for (k,z)-clustering in ℝ^d whose dependence on 1/ε has exponent strictly smaller than $2$ when d is fixed. This improves over the worst-case ε^−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.
ER -