提出新方法消除异常值对数据摘要大小的影响，提升鲁棒几何中位数计算效率。
Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
- 采用非分量误差分析技术，有效降低异常值影响。
- 在 n≥4m 条件下，核心集大小仅依赖 ε 与 d，不再随异常值数 m 增长。
- 适用于一维及多种度量空间的鲁棒聚类，适合高噪声数据场景。
我们研究欧氏空间 $\mathbb{R}^d$ 中的鲁棒几何中位数问题，重点在于构建核心集（coreset）。核心集是大小为 $n$ 的数据集 $P$ 的紧凑表示，对所有中心 $c$ 的鲁棒代价提供乘法误差 $\varepsilon$ 内的近似。给定异常值数量 $m$，当 $n \geq 4m$ 时，我们构造出大小为 $\tilde{O}(\varepsilon^{-2} \cdot \min\{\varepsilon^{-2}, d\})$ 的核心集，消除了先前工作 [Huang et al., 2022 & 2023] 中存在的 $O(m)$ 依赖性。在一维情形下，我们实现了最优核心集大小 $\tilde{\Theta}(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$，揭示了与 [Huang et al., 2023; Afshani and Chris, 2024] 所研究的经典情形的明显差异。我们的结果进一步扩展到多种度量空间下的鲁棒 $(k,z)$-聚类，在弱数据假设下也消除了 $m$ 的依赖。关键技术贡献是一种新型的非分量式误差分析，显著抑制异常值影响，不同于以往保留其影响的方法。实验表明，即使在数据假设被违反的情况下，我们的算法在核心集大小-精度权衡和运行时间上均持续优于现有基线，在广泛数据集上表现稳健。
原文摘要 · Abstract (English)
We study the robust geometric median problem in Euclidean space $\mathbb{R}^d$, with a focus on coreset construction.A coreset is a compact summary of a dataset $P$ of size $n$ that approximates the robust cost for all centers $c$ within a multiplicative error $\varepsilon$. Given an outlier count $m$, we construct a coreset of size $\tilde{O}(\varepsilon^{-2} \cdot \min\{\varepsilon^{-2}, d\})$ when $n \geq 4m$, eliminating the $O(m)$ dependency present in prior work [Huang et al., 2022 & 2023]. For the special case of $d = 1$, we achieve an optimal coreset size of $\tildeΘ(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$, revealing a clear separation from the vanilla case studied in [Huang et al., 2023; Afshani and Chris, 2024]. Our results further extend to robust $(k,z)$-clustering in various metric spaces, eliminating the $m$-dependence under mild data assumptions. The key technical contribution is a novel non-component-wise error analysis, enabling substantial reduction of outlier influence, unlike prior methods that retain them.Empirically, our algorithms consistently outperform existing baselines in terms of size-accuracy tradeoffs and runtime, even when data assumptions are violated across a wide range of datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。