betaFeedback

WorksComputer Science

When is Uniform Sampling Optimal? Coresets for Distributional Clustering

Abstract

Recent work [1] settled the optimal worst-case strong ε\varepsilon-coreset size for Euclidean kk-means in unrestricted dimension at Θ~(min⁡{k3/2ε−2,kε−4})\tildeΘ(\min\{k^{3/2}\varepsilon^{-2}, k\varepsilon^{-4}\}), showing that the natural target O~(kε−2)\tilde{O}(k\varepsilon^{-2}) is unattainable in general. For mixtures of kk isotropic Gaussian components with balanced weights and bounded scale imbalance in dimension d≥log⁡kd\ge\log k, we show that uniform sampling yields strong ε\varepsilon-coresets of size O~(kε−2)\tilde{O}(k\varepsilon^{-2}), without cluster separation. This saves a factor of min⁡{k,ε−2}\min\{\sqrt{k},\varepsilon^{-2}\} over the worst-case bound, up to logarithms. For population approximation by independent, equally weighted samples, the near-linear rate is optimal up to logarithmic factors over this class. More generally, for datasets generated from an isotropic Gaussian mixture μμ satisfying a mild cost-comparison assumption, uniform sampling yields strong ε\varepsilon-coresets of size O~((kζμ+πmin⁡−1)ε−2)\tilde{O}((kζ_μ+π_{\min}^{-1})\varepsilon^{-2}), where πmin⁡π_{\min} is the minimum component weight and ζμζ_μ measures scale imbalance. Our proof uses a base-shift cost decomposition: one query center per component describes the base costs, and graph spanners control the sparse corrections from points switching centers. For general mixtures under cost and tail assumptions, we obtain O~((kζμ+πmin⁡−1)ε−2min⁡{k,ε−2})\tilde{O}((kζ_μ+π_{\min}^{-1})\varepsilon^{-2}\min\{\sqrt{k},\varepsilon^{-2}\}) samples. We also prove a matching Ω~(min⁡{k3/2ε−2,kε−4})\tildeΩ(\min\{k^{3/2}\varepsilon^{-2},k\varepsilon^{-4}\}) lower bound for population approximation by uniform sampling from anisotropic Gaussian mixtures, even with equal weights and a shared covariance matrix. [1] Junqiu Hu, Lingxiao Huang, Jian Li, and Baoduo Xu. Tight coreset bounds for (k,z)(k, z)-clustering in Euclidean and doubling metrics, 2026. arXiv:2610.34373.

Introduction

Clustering is a fundamental task in data analysis, machine learning, and theoretical computer science [23]. Among clustering objectives, Euclidean kk-means is one of the most extensively studied and widely used [7]. Given a finite dataset X⊆RdX \subseteq\mathbb{R}^{d} and an integer k≥1k \ge1, the goal is to find a set C⊆RdC \subseteq\mathbb{R}^{d} of kk centers minimizing the average squared distance to the nearest center. We write

cost⁡(p,C):=d2(p,C)=min⁡c∈C∥p−c∥2,cost⁡(X,C):=1∣X∣∑p∈Xcost⁡(p,C).\operatorname{cost}(p,C) := d^{2}(p,C) = \min_{c \in C} \lVert p-c\rVert^{2}, \qquad\operatorname{cost}(X,C) := \frac{1}{|X|}\sum_{p \in X}\operatorname{cost}(p,C).

When XX is large, storing, communicating, or repeatedly processing the entire dataset can be prohibitively expensive. This motivates coresets: small weighted summaries that approximately preserve the objective values of the original dataset [22, 15]. A weighted subset S⊆XS \subseteq X, with nonnegative weights ww, is a strong ε\varepsilon-coreset for XX if

cost⁡(S,C):=∑p∈Sw(p)cost⁡(p,C)∈(1±ε)cost⁡(X,C)for every C⊆Rd with ∣C∣=k.\operatorname{cost}(S,C) := \sum_{p \in S} w(p)\operatorname{cost}(p,C) \in(1 \pm\varepsilon)\operatorname{cost}(X,C) \qquad\text{for every } C \subseteq\mathbb{R}^{d} \text{ with } |C|=k.

Because the guarantee holds uniformly over all candidate center sets, a strong coreset can replace the full dataset for kk-means optimization, reducing storage and computation; its composability also enables standard streaming and distributed implementations [17].

A central question in coreset theory is to determine the smallest possible strong coreset size for Euclidean kk-means. A natural target was a size nearly linear in kk and quadratic in ε−1\varepsilon^{-1}, namely O~(kε−2)\widetilde{O}(k\varepsilon^{-2}).1 Cohen-Addad et al. [11] established an Ω(kε−2)\Omega(k\varepsilon^{-2}) lower bound together with an upper bound of O~(kε−2min⁡{k,ε−2})\widetilde{O}(k\varepsilon^{-2}\min\{k,\varepsilon^{-2}\}), which was subsequently improved to O~(kε−2min⁡{k,ε−2})\widetilde{O}(k\varepsilon^{-2}\min\{\sqrt{k},\varepsilon^{-2}\}) [9]. Huang, Li, and Wu [21] showed that the target O~(kε−2)\widetilde{O}(k\varepsilon^{-2}) is unattainable in general by proving an Ω(kε−4)\Omega(k\varepsilon^{-4}) lower bound when ε=Ω(k−1/4)\varepsilon=\Omega(k^{-1/4}), matching the corresponding upper-bound regime. More recently, Hu, Huang, Li, and Xu [18] proved a matching Ω~(k3/2ε−2)\widetilde{\Omega}(k^{3/2}\varepsilon^{-2}) lower bound for all 0<ε<k−1/40<\varepsilon<k^{-1/4}. Together, these results determine the optimal worst-case coreset size, over datasets of unrestricted dimension, as

Θ~(min⁡{k3/2ε−2,kε−4}).\widetilde{\Theta}\left(\min\{k^{3/2}\varepsilon^{-2}, k\varepsilon^{-4}\}\right).

These lower bounds rely on delicate worst-case constructions [21, 18] that plant aligned offset vectors across clusters. In practice, simple sampling on real-world datasets performs much better than the worst-case bounds predict [SSO22], motivating structured input models that admit O~(kε−2)\widetilde{O}(k\varepsilon^{-2}) coresets. One approach is to assume cost stability: Bansal et al. [4] showed that sensitivity sampling yields O~(kε−2)\widetilde{O}(k\varepsilon^{-2}) coresets under constant cost stability, OPT⁡k−1(X)≥(1+β)OPT⁡k(X)\operatorname{OPT}_{k-1}(X) \ge(1+\beta)\operatorname{OPT}_{k}(X) for a constant β>0\beta>0, where OPT⁡m(X)\operatorname{OPT}_{m}(X) is the minimum mm-means cost. However, requiring a constant relative cost jump when a single center is removed is restrictive—it can fail for overlapping mixtures, or even for well-separated balanced clusters once kk is large enough that removing one center increases the total cost by only O(1/k)O(1/k).

We instead study a distributional source of structure, modeling the input XX as an i.i.d. sample from an underlying kk-component mixture distribution—starting with isotropic Gaussian mixtures [MB88, BR93, FR02] and extending to general mixtures under a tail condition. For isotropic Gaussians, the offset directions are independent and uniform on the sphere, conditional on the component labels and radii. This contrasts with the aligned patterns of the worst-case constructions and leads us to ask:

Question. If a finite dataset XX is generated from an underlying mixture distribution, does uniform sampling give a strong ϵ\epsilon-coreset of size O~(kϵ−2)\widetilde{O}(k\epsilon^{-2}) for XX, bypassing the worst-case barrier Θ~(min⁡{k3/2ϵ−2,kϵ−4})\widetilde{\Theta}(\min\{k^{3/2}\epsilon^{-2}, k\epsilon^{-4}\})?

Our contributions

Isotropic mixtures: near-linear size. We answer this question affirmatively for isotropic Gaussian mixtures with balanced weights and bounded scale imbalance in dimension d≥log⁡kd \ge\log k, without cluster separation. More generally, the bound holds under the comparison condition (CC). The parameters ζμ\zeta_\mu and πmin⁡\pi_{\min} capture scale and weight imbalance: πmin⁡\pi_{\min} is the minimum component weight, and ζμ\zeta_\mu is the largest component mean-squared radius divided by their mixture-weighted average (§ 2).

For datasets generated from balanced mixtures with πmin⁡=Ω(1/k)\pi_{\min} = \Omega(1/k) and ζμ=O(1)\zeta_\mu= O(1), uniform sampling yields strong ϵ\epsilon-coresets of size O~(kϵ−2)\widetilde{O}(k\epsilon^{-2}) under the same comparison condition. Equal-weight components with a common variance are a special case, with πmin⁡=1/k\pi_{\min} = 1/k and ζμ=1\zeta_\mu= 1. This removes a factor k\sqrt{k} for ϵ≤k−1/4\epsilon\le k^{-1/4} and ϵ−2\epsilon^{-2} for ϵ≥k−1/4\epsilon\ge k^{-1/4} from the worst-case size, up to logarithms. The sampling rule needs no recovery of component labels, means, or covariances.2 We prove the result by first establishing a sampling guarantee for the population cost cost⁡(μ,C):=Ep∼μcost⁡(p,C)\operatorname{cost}(\mu,C) := \mathbb{E}_{p\sim\mu}\operatorname{cost}(p,C) and then transferring it to the generated dataset.

Theorem 1.1 (Coreset size for isotropic Gaussian mixtures). Let μ\mu be an isotropic Gaussian mixture satisfying the comparison condition (CC). For every ϵ∈(0,1)\epsilon\in(0,1), an i.i.d. sample X∼μNX \sim\mu^N of size

N=O~((kζμ+πmin⁡−1)ϵ−2)N = \widetilde{O}\left((k\zeta_\mu+\pi_{\min}^{-1})\epsilon^{-2}\right)

forms a strong ϵ\epsilon-coreset for μ\mu with probability at least 0.9.

Corollary 1.2 (Uniform sampling). Under the assumptions of Theorem 1.1, for every ϵ∈(0,1)\epsilon\in(0,1), let SS consist of

m=O~((kζμ+πmin⁡−1)ϵ−2)m = \widetilde{O}\left((k\zeta_\mu+\pi_{\min}^{-1})\epsilon^{-2}\right)

observations sampled uniformly without replacement from the indices of X∼μNX \sim\mu^N, where N≥mN \ge m. With weight 1/m1/m per observation, SS is a strong ϵ\epsilon-coreset of XX with probability at least 0.9.

The probability is over dataset generation and sampling. This finite-data reduction is proved in Appendix § 9.§ 1.

Appendices D.3 and D.4 establish the necessity of the dependence on πmin⁡\pi_{\min} and ζμ\zeta_\mu for population approximation by independent, equally weighted samples. In particular, the balanced near-linear rate is optimal up to logarithmic factors over the isotropic mixture class.

General mixtures: worst-case size by uniform sampling. We extend this guarantee to general mixtures under the cost and tail assumptions in § 2.3. In the balanced regime, the bound matches the worst-case size; the gain here is the uniform sampling rule rather than a smaller bound:

Theorem 1.3 (Coreset size for general mixtures). Let μ\mu be a mixture with Vμ>0V_\mu> 0, satisfying the comparison condition (CC) and a tail condition (Assumption 2.2). For every ϵ∈(0,1)\epsilon\in(0,1), an i.i.d. sample X∼μNX \sim\mu^N of size

N=O~((kζμ+πmin⁡−1)ϵ−2min⁡{k,ϵ−2})N = \widetilde{O}\left((k\zeta_\mu+\pi_{\min}^{-1})\epsilon^{-2}\min\{\sqrt{k},\epsilon^{-2}\}\right)

forms an ϵ\epsilon-coreset for μ\mu with probability at least 0.9.

The same reduction gives finite-data coresets of this size. Appendices § 10.§ 1 and § 10.§ 2 justify the cost-comparison and tail assumptions.

Anisotropic mixtures: worst-case lower bound. In contrast, for anisotropic Gaussian mixtures, the required sample size can rise to the worst-case scale, even with equal component weights and a shared covariance matrix. The following lower bound for uniform sampling is proved in § 6.

Theorem 1.4 (Lower bound for uniform sampling). For every sufficiently large kk and every ε∈(0,1)\varepsilon\in(0,1), there is an equal-weight Gaussian mixture μ=k−1∑j=1kN(aj,Σ)\mu= k^{-1}\sum_{j=1}^{k}\mathcal{N}(a_j,\Sigma) in some dimension, with Σ⪰0\Sigma\succeq0 and

tr⁡Σ=Vμ=1=O(cost⁡(μ,C))for every set C of at most k centers,\operatorname{tr}\Sigma= V_\mu= 1 = O(\operatorname{cost}(\mu,C)) \quad\text{for every set } C \text{ of at most } k \text{ centers,}

such that, for every

1≤N≤cmin⁡{k3/2ε−2,kε−4}log⁡8(k/ε),(1)1 \leq N \leq c\frac{\min\{k^{3/2}\varepsilon^{-2},k\varepsilon^{-4}\}}{\log^{8}(k/\varepsilon)}, \tag*{(1)}

an independent sample X∼μNX \sim\mu^{N} satisfies, with probability at least 0.90.9,

∣cost⁡(X,C)−cost⁡(μ,C)∣>εcost⁡(μ,C)for some set C of at most k centers.\left|\operatorname{cost}(X,C)-\operatorname{cost}(\mu,C)\right| > \varepsilon\operatorname{cost}(\mu,C) \quad\text{for some set } C \text{ of at most } k \text{ centers.}

Here c>0c > 0 is universal, and μ\mu depends only on k,εk,\varepsilon.

Related work

Coresets for structured instances. Bansal et al. [4] show that sensitivity sampling yields strong ε\varepsilon-coresets of size O~(kε−2)\widetilde{O}(k\varepsilon^{-2}) for datasets satisfying constant cost stability. Their result exploits a cost-stability gap in the finite dataset, whereas ours uses distributional assumptions on the generating components and uniform sampling, without requiring such a gap.

Uniform sampling for clustering coresets. Braverman et al. [5] reduce coreset construction to ring instances and apply uniform sampling within these instances; our construction samples uniformly from the entire dataset without computing such a partition. Huang, Jiang, and Lou [19] obtain (1+ε)(1+\varepsilon)-approximation guarantees for kk-median via uniform sampling under balancedness. Carmel and Krauthgamer [13] introduce stable coresets, which approximately preserve the relative ordering of candidate costs rather than every cost individually, and construct them by uniform sampling for 1-median in ℓ1\ell_1 and related metrics.

Bachem et al. [6] obtain kurtosis-dependent uniform deviation bounds for kk-means over all center sets, with dimension-dependent sample complexity and an additive error term proportional to the global variance. In concurrent and independent work, Carmel and Krauthgamer [12] obtain dimension-free relative-error guarantees over O(1)O(1)-approximate candidate solutions under cluster balancedness, sufficiently strong ρ\rho-separation, and bounded kurtosis within each optimal cluster. In contrast, for datasets generated by isotropic Gaussian mixtures in dimension d≥log⁡kd \geq\log k, we obtain a strong coreset guarantee across all candidate center sets C∈(Rd)kC \in(\mathbb{R}^{d})^{k} without requiring cluster separation.

Statistical learning and distributional coresets. Related work studies Gaussian-mixture density estimation in total variation [1], coresets for likelihood-based Gaussian-mixture fitting [LFKF18, FKW19], and excess-risk bounds for PAC kk-means learning [10]. Our task instead uses mixture assumptions on the input distribution to justify uniform sampling that preserves ordinary kk-means costs within relative error for every candidate center set, first for the population and then for the generated finite dataset, without learning the mixture. Alishahi and Phillips [3] also study dimension-free sampling coresets for distributional inputs, but for regularized classification losses. Work on stochastic noise [20] targets unobserved clean data rather than the observed dataset itself.

Preliminaries

Mixture model and parameters

References

  1. [1][ABDH+20] Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via compression schemes. Journal of the ACM, 67(6):32:1–32:42, 2020. doi:10.1145/3417994.DOI
  2. [2]Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81–100, 1993.DOI
  3. [3]Meysam Alishahi and Jeff M. Phillips. No dimensional sampling coresets for classification. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 1008–1049. PMLR, 2024. URL: https://proceedings.mlr.press/v235/alishahi24a.html.arxiv.org/abs/2402.05280
  4. [4]Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. In Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1707–1723. IEEE, 2024. doi:10.1109/FOCS61266.2024.00106.DOI
  5. [5]Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 462–473. IEEE, 2022. doi:10.1109/FOCS54457.2022.00051.DOI
  6. [6]Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Uniform deviation bounds for k-means clustering. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 283–291. PMLR, 2017. URL: https://proceedings.mlr.press/v70/bachem17a.html.
  7. [7]Johannes Blömer, Christiane Lammersen, Melanie Schmidt, and Christian Sohler. Theoretical analysis of the k-means algorithm—a survey. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 81–116. Springer, Cham, 2016. arXiv:1602.08254, doi:10.1007/978–3–319–49487–6_3.arxiv.org/abs/1602.08254
  8. [9]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for Euclidean k-means. In Advances in Neural Information Processing Systems, volume 35, pages 2679–2694. Curran Associates, Inc., 2022. doi:10.52202/068431-0194.
  9. [10]Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn. Almost optimal PAC learning for k-means. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2019–2030. Association for Computing Machinery, 2025. doi:10.1145/3717823.3718180.
  10. [11]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing, pages 1038–1051. ACM, 2022. doi:10.1145/3519935.3519946.
  11. [12]Amir Carmel and Robert Krauthgamer. Coresets for k-means: When does uniform sampling suffice?, 2026. arXiv:2610.31491.arxiv.org/abs/2610.31491
  12. [13]Amir Carmel and Robert Krauthgamer. Stable coresets: Unleashing the power of uniform sampling. In 14th International Conference on Learning Representations (ICLR), 2026. URL: https://openreview.net/forum?id=sOpAa8iR0A, arXiv:2509.22189.arxiv.org/abs/2509.22189
  13. [15]Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 569–578. ACM, 2011.
  14. [17]Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, PCA, and projective clustering. SIAM Journal on Computing, 49(3):601–657, 2020. arXiv:1807.04518, doi:10.1137/18M1209854.
  15. [18]Junqiu Hu, Lingxiao Huang, Jian Li, and Baoduo Xu. Tight coreset bounds for (k, z)-clustering in Euclidean and doubling metrics, 2026. arXiv:2610.34373.arxiv.org/abs/2610.34373
  16. [19]Lingxiao Huang, Shaofeng H.-C. Jiang, and Jianing Lou. The power of uniform sampling for k-median. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 13933–13956. PMLR, 23–29 Jul 2023. URL: https://proceedings.mlr.press/v202/huang23j.html.arxiv.org/abs/2302.11339
  17. [20]Lingxiao Huang, Zhize Li, Nisheeth K. Vishnoi, Runkai Yang, and Haoyu Zhao. Coresets for clustering under stochastic noise. In Advances in Neural Information Processing Systems, volume 38, pages 84034–84083. Curran Associates, Inc., 2025. arXiv:2510.23438, doi:10.52202/085713–2816.arxiv.org/abs/2510.23438
  18. [21]Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for Euclidean (k, z)-clustering. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1594–1604. ACM, 2024. doi:10.1145/3618260.3649707.DOI
  19. [22]Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 291–300. ACM, 2004.
  20. [23]Anil K. Jain. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8):651–666, 2010. doi:10.1016/j.patrec.2009.09.011.DOI
  21. [24]Michel Ledoux. Concentration of measure and logarithmic Sobolev inequalities. Séminaire de probabilités, 33:120–216, 1999. URL: https://www.numdam.org/item/SPS_1999__33__120_0/.DOI

Paper details

vlnc:W_7vq2wj4s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents