When is Uniform Sampling Optimal? Coresets for Distributional Clustering
Junqiu Hu, Lingxiao Huang, Baoduo Xu
原文摘要
Recent work [1] settled the optimal worst-case strong $\varepsilon$-coreset size for Euclidean $k$-means in unrestricted dimension at $\tildeΘ(\min\{k^{3/2}\varepsilon^{-2}, k\varepsilon^{-4}\})$, showing that the natural target $\tilde{O}(k\varepsilon^{-2})$ is unattainable in general. For mixtures of $k$ isotropic Gaussian components with balanced weights and bounded scale imbalance in dimension $d\ge\log k$, we show that uniform sampling yields strong $\varepsilon$-coresets of size $\tilde{O}(k\varepsilon^{-2})$, without cluster separation. This saves a factor of $\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 $\tilde{O}((kζ_μ+π_{\min}^{-1})\varepsilon^{-2})$, where $π_{\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 $\tilde{O}((kζ_μ+π_{\min}^{-1})\varepsilon^{-2}\min\{\sqrt{k},\varepsilon^{-2}\})$ samples. We also prove a matching $\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)$-clustering in Euclidean and doubling metrics, 2026. arXiv:2610.34373.
cs.DS · cs.CG