Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers

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 $\epsilon$.

Given an outlier count $m$, we construct a coreset of size $$\begin{gathered} \tilde{O}({\epsilon }^{-2}\cdot \min \\ {\epsilon }^{-2},d \\ ) \end{gathered}$$ when $n\ge 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{\Theta }({\epsilon }^{-1/2}+\frac{m}{n}{\epsilon }^{-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.