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

• URL: http://arxiv.org/abs/2609.06394v1
• Date: Sun, 06 Sep 2026 05:08:57 GMT
• Title: Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling
• Abstract summary: We introduce a new correlated sampling framework, called textitdeterminantal sampling, based on a novel application of exponental point processes.<n>We obtain an efficiently constructible $varepsilon$-coreset for $(k,z)$-clustering in $mathbb Rd$ whose dependence on $1/varepsilon$ has strictly smaller than $2$ when $d$ is fixed.<n>This is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions.
• Score: 2.0357579455195007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\varepsilon$-coreset for $(k,z)$-clustering in $\mathbb R^d$ 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.

Related papers

• Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
  We introduce a new data selection framework based on low-rank approximation and residual-based sampling.<n>We show that it is possible to select a weighted subset of $tildeOleft(k + frac1varepsilon2right)$ data points whose average loss approximates the average loss over the full dataset.
  arXiv  Detail & Related papers  (2026-06-14T22:29:59Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Simple KNN-Based Outlier Detection Achieves Robust Clustering [0.8250700096210891]
  Being robust to the presence of outliers is crucial for applying clustering algorithms in practice.<n>We show that removing points with large $K$-Nearest-Neighbor distances achieves performance comparable to prior work in terms of approximation guarantees.
  arXiv  Detail & Related papers  (2026-05-08T02:08:50Z)
• Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers [9.19267739465056]
  We construct a coreset of size $tildeO(varepsilon-2 cdot minvarepsilon-2, d)$ when $n geq 4m$.<n>For the special case of $d = 1$, we achieve an optimal coreset size of $tildeTheta(varepsilon-1/2 + fracmn varepsilon-1)$.<n>Our results extend to robust $(k,z)$-clustering
  arXiv  Detail & Related papers  (2025-10-28T16:49:03Z)
• Coresets for Clustering Under Stochastic Noise [33.12252505929148]
  We study the problem of constructing coresets for $(k, z)$-clustering when the input dataset is corrupted by noise.<n>We use surrogate error metrics that are tractable and provably related to the true clustering cost.<n>We show that the coreset size can improve by a factor of up to $mathrmpoly(k)$, where $n$ is the dataset size.
  arXiv  Detail & Related papers  (2025-10-27T15:41:27Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Universal Weak Coreset [3.1509756165776635]
  A weak coreset is a pair $(J,S)$ of subsets of points, where $S$ acts as a summary of the point set and $J$ as a set of potential centers. We develop this framework, which we call universal weak coresets, for constrained clustering settings.
  arXiv  Detail & Related papers  (2023-05-26T12:51:16Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  We propose an efficient approximation procedure based on the Nystr"om method. It yields sufficient conditions on the subsample size to obtain the standard $n-1/2$ rate. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules.
  arXiv  Detail & Related papers  (2022-01-31T08:26:06Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.