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 $ϵ$-$\text{coreset}$: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the $(k,z)$-$\text{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 $\text{determinantal sampling}$, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible $\epsilon$-coreset for $(k,z)$-clustering in ${\mathbb{R}}^d$ whose dependence on $1/\epsilon$ has exponent strictly smaller than $2$ when $d$ is fixed. This improves over the worst-case ${\epsilon }^{-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.