跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20641 · v1

When is Uniform Sampling Optimal? Coresets for Distributional Clustering

首次提交 2026-11-16 15:01
版本更新 2026-11-16 15:01
雷达观测 2026-11-17 13:07
arXiv ↗PDF ↗

摘要

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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 15:01 · 最新观测版本

When is Uniform Sampling Optimal? Coresets for Distributional Clustering

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.

查看此版本解读 →查看此版本原文 ↗