← 研踪 PaperTrailarXiv: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
摘要
Recent work [1] settled the optimal worst-case strong -coreset size for Euclidean -means in unrestricted dimension at , showing that the natural target is unattainable in general. For mixtures of isotropic Gaussian components with balanced weights and bounded scale imbalance in dimension , we show that uniform sampling yields strong -coresets of size , without cluster separation. This saves a factor of 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 -coresets of size , where 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 samples. We also prove a matching 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 -clustering in Euclidean and doubling metrics, 2026. arXiv:2610.34373.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 -coreset size for Euclidean -means in unrestricted dimension at , showing that the natural target is unattainable in general. For mixtures of isotropic Gaussian components with balanced weights and bounded scale imbalance in dimension , we show that uniform sampling yields strong -coresets of size , without cluster separation. This saves a factor of 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 -coresets of size , where 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 samples. We also prove a matching 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 -clustering in Euclidean and doubling metrics, 2026. arXiv:2610.34373.
查看此版本解读 →查看此版本原文 ↗