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

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.