2025/10/28 by Fang, Ziyi, Huang, Lingxiao, Yang, Runkai
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2510.24621
We study the robust geometric median problem in Euclidean space ℝ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 ε. Given an outlier count m, we construct a coreset of size O(ε-2 ⋅ min\ε-2, d\) when n ≥ 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 Θ(ε-1/2 + (m)/(n) ε-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.