Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers

Thank you for your positive assessment of our work’s quality, clarity, significance, and originality. In response to your feedback, we will improve the paper’s organization for better readability and move key experimental results from the appendix into the main text to enhance accessibility.

Presentation Alignment: Several figures, tables, and algorithm blocks are not placed near the corresponding explanatory text. Reorganizing the layout so that each element appears closer to the relevant discussion would significantly improve readability and reader comprehension.

Thanks for your comment. We will do this to improve readability in the final version.

Structure of Experimental Results: Key experimental results are currently not sufficiently highlighted in the main text. Could the authors restructure the paper to better emphasize these results in the main body, rather than relegating them to the appendix or supplementary material?

Thank you for your question. Yes, we will move the experimental results on the robust geometric median to the main text, including:

• Statistical test (Table 4): Results show that our coreset consistently achieves lower empirical error than the baselines across six datasets, demonstrating the consistency of our method’s outperformance.
• Analysis for $n < 4m$ (Figure 5): Results indicate that our coreset remains effective even when the assumption $n \geq 4m$ is not satisfied, highlighting the robustness of our method.
• Size-error tradeoff for 1D case (Figure 6): Results show that our 1D method consistently outperforms the baselines for the robust 1D geometric median.

Incorporating these results into the main text will enhance the integrity of the experiments presented in the main text.

Thank you again for your comments. To further improve the paper’s presentation, we will also move Assumption F.6 to the main text and add figures to illustrate the pseudo-code.

Thank you for your positive feedback and for recognizing both the significance of our contributions and the strength of our experimental results. We also appreciate your comment regarding Figure 1's labeling; in the final version we will enhance the axis titles, legend descriptions, and in-figure annotations to ensure it is fully self-explanatory.

Thank you for your feedbacks and detailed suggestions. We appreciate your recognition of the soundness, presentation, and contribution of our work.

Q1: Does the proposed non-component-wise error analysis can be generalized to other robust learning tasks, such as robust regression or PCA, or is it fundamentally specific to clustering-like cost functions?

Thank you for the insightful question. To the best of our knowledge, existing coreset methods for robust PCA and robust regression do not partition the dataset into components but take samples from the entity (e.g., [26]). This makes it challenging to directly apply our non-component-wise error analysis to robust regression or PCA.

Q2: How does the proposed method perform when the assumption $n\ge 4m$ is violated in a controlled way?

Thank you for this valuable question. Suppose $n< 4m$.

• Theoretically, the proposed method does not guarantee to produce a coreset. This is because when $n - m = o(n)$, the coreset size for the robust geometric median is $\Omega(m)$ (Theorem 1.1). Thus, the assumption $n\ge 4m$ is necessary (up to a constant factor) for our coreset construction.
• In practice, our method continues to outperform the baselines when $n =2m$ (Figure 5, Section G.1), demonstrating the robustness of our method.

Q3: How does the coreset behave under adversarial or heavy-tailed conditions?

Thank you for raising this question. We do the following experiment accordingly:

On the Census1990 dataset, we fix outlier number $m = 2000$ and randomly perturb 10% of the points by adding i.i.d. Cauchy(0,1) noise, simulating heavy-tailed contamination. Our method outperforms baselines on this perturbed dataset, demonstrating the robustness of our method’s outperformance. For example, our coreset of size 900 achieves an empirical error of 0.018, while the best baseline error is 0.020 when the size is 2200.

We will include this experiment in the final version.

Q4: Is it possible to construct an $\varepsilon$-coreset for the robust geometric median (or more generally, robust (k,z)-clustering) in high-dimensional Euclidean space $\mathbb{R}^d$ with optimal or near-optimal size, without relying on uniform sampling of outliers or the ball range space framework—perhaps via alternative geometric or combinatorial constructions?

Thank you for raising this point. Achieving near-optimal robust coreset sizes in high-dimensional Euclidean spaces via geometric or combinatorial constructions is indeed challenging. This difficulty arises primarily due to the increased complexity in the distribution of candidate centers, which complicates geometric partitioning strategies. For example, [15] employs an $\varepsilon$-net to partition the space, but this approach incurs an exponential factor of $O(\varepsilon^{-d})$ in the coreset size (see Lines 212–215). To the best of our knowledge, the current state-of-the-art coresets for both vanilla and robust geometric median problems are derived through sampling-based methods.

concrete examples or illustrations ... new error analysis approach.

Thank you for this insightful comment. We agree that a concrete example can largely improve the clarity of our new error analysis approach. Below we specify one: Let $P=P_1\cup P_2$ where $P_1=\\{p_1,\ldots,p_{n-m}\\}$ with $p_i = \frac{i}{n}$ and $P_2=\\{p_{n-m+1},\ldots,p_n\\}$ with $p_i = n^{3(i-n+m)}$ (see also Appendix A.3).

• Algorithm 1 decomposes $P_2$ into at most $O(\varepsilon^{-1})$ buckets $B_i$, where each bucket contains $\varepsilon n/16$ points, and collects their mean points $\mu(B_i)$ in the coreset $S$.

• Let $B=\\{p_l,\ldots,p_r\\}$ be a bucket within $P_2$. Let center $c=p_l=n^{3j}$. Since $p_l$ is an inlier point of $P$ w.r.t. $c$, the outlier number of $B$ w.r.t. $c$ must be $|B|-1$.

• In the component-wise analysis, the induced error of bucket $B$ is $\left|\text{cost}^{(|B| - 1)}(B, c) - |\mu(B) - c|\right|$, which is at least $\text{dist}(\mu(B), c) = \Omega(n^{3(j+1)})$. However, $\text{cost}^{(m)}(P,c)$ is approximately $(n-m)\cdot 3^j \ll \text{dist}(\mu(B), c)$, which implies that the induced error substantially exceed the coreset error bound.

• In contrast, in our non-component-wise analysis, the induced error of bucket $B$ is 0. This is because we allow the misaligned outlier numbers in each bucket. Since $\text{dist}(\mu(B),c) \gg \text{dist}(p,c)$ for any point $p \in P_1$, $\mu(B)$ will be totally regarded as an outlier w.r.t. $c$. As a result, $B$ contributes zero error.

• Thus, non-component-wise analysis significantly reduces bucket-wise errors in this example, which is crucial for proving $S$ is a coreset.

We will add this example to the appendix in the final version.

modest empirical gains over strong baselines.

Thank you for raising this point. Below we summarize the empirical gains of our method over baselines:

• Smaller coreset size at same error: Our method reduces the coreset size by 25%–45% compared to baselines when achieving the same empirical error. For instance, on the Census1990 dataset, our method achieves an empirical error of 0.012 while saving 28.6% of the data relative to the baselines (see Lines 324–329).

• Consistent improvement across datasets: This size improvement consistently holds across diverse datasets across different data scales ($10^4$–$10^5$), dimensions ($2$–$64$), and diverse domains (including social network, demographic, and disease data)

• Smaller than $m$ coreset size: Unlike baselines, which require a coreset of size at least $m$, our method can achieve the same level of error with a coreset size smaller than $m$. For example, on the Census1990 dataset with $m = 2000$:

  • Our method yields a coreset of size 600 with an empirical error of 0.021
  • The best baseline needs size 2300 to achieve a worse error of 0.022

  This highlights the strength of our method, especially in settings with many outliers.

We will include this new empirical result in the final version.

lacks a comparison with recent state-of-the-art literature ...

Thank you for suggesting these references.

• [Ding and Wang (2020)] propose a layered sampling framework that constructs a weak coreset of size $\tilde{O}(kd\varepsilon^{-2}) + (1+\varepsilon^{-1})m$ in $O(nkd)$ time.
• [Paul et al. (2021)] propose an iterative algorithm for robust clustering.
• [Cohen-Addad et al. (2022)] has been discussed in Lines 46–47.

In comparison, our paper focuses on (strong) coreset construction for robust clustering, which differs in objective from their works. We will cite these references in the Section 1 of the final version.

The paper makes some strong assumptions (e.g., , existence of VC-dimension bounds) but does not clearly discuss their practical validity or limitations.

We apologize for any confusion.

• Theorems E.11, E.12 work for any VC-dimension, just the coreset size is proportional to the VC dimension. We will remove the sentence "if the VC dimension $d_{VC}(\mathcal{X})$ is bounded" in Theorem E.11.

• VC-dimension bounds are often known [9, 18, 40]:

  • For general metric space $\mathcal{X}$, its VC-dimension is $O(\log|\mathcal{X}|)$.
  • For shortest-path metric of a graph with bounded treewidth $t$, its VC-dimension is $O(t)$.
  • For shortest-path metric of a graph that excludes a fixed minor $H$, its VC-dimension is $O(H)$.

We will clarify this in the final version.

Computational aspects, including the overhead of constructing the coreset and its scalability to large-scale or streaming settings, are not addressed.

Thank you for raising these important points.

Computational overhead. The overhead for constructing our robust coresets is efficient.

• Robust 1D geometric median (Algorithm 1): The construction takes $O(n)$ time, as detailed in Section D (Lines 1020–1026).
• Robust geometric median (Algorithm 2): The overall complexity is dominated by one step that takes $O(nd)$ time, making the total overhead $O(nd)$.
• Robust $(k,z)$-clustering (Algorithm 3): The total complexity is $O(nkd)$, with the dominant step detailed in Theorem F.7.

Scalability to large-scale data. We measure scalability by the practical speed-up achieved when running downstream algorithms on the coreset versus the full dataset. Our empirical results in Table 1 show that using our robust coresets provides a 7x-10x speed-up in computation time while maintaining high accuracy, demonstrating its practical scalability.

Streaming Settings Extending robust coresets to a streaming model is a valuable but challenging future direction. The primary difficulty is that our robust coreset may not satisfy the mergeability property—a key requirement for most streaming algorithms—due to the complex ways noise and outliers can interact across different data chunks.

We will add this discussion on computational overhead and scalability to the main paper and explicitly list the streaming setting as an important direction for future work.

The generalization to robust (k,z)-clustering is stated but not formally supported.

The formal definition and supporting proofs for robust $(k,z)$-clustering can be found in Appendix F.

Thank you for your thoughtful comments, which have helped us improve the clarity and empirical reach of our work.

Thank you for your positive feedback and for acknowledging the significance, correctness, and contributions of our work. We truly appreciate your detailed suggestions.

In response to your concerns regarding paper presentation and code availability, we will (i) move Assumption F.6 to the main body and include the definition of $(i,r,P_i)$, (ii) add illustrative figures to accompany the pseudo-code, (iii) include markers on the curves for clarity, and (iv) release the code publicly upon acceptance.

Below we address your specific questions.

What is the definition of $\tilde{O}$?

Thank you for your question. The notation $\tilde{O}(n)$ denotes $O(n \cdot \text{polylog}(n))$. For example, our coreset size upper bound $\tilde{O}(\varepsilon^{-2}\cdot \min \\{\varepsilon^{-2}, d \\})$ in Theorem 1.3 (Line 105) hides a polylog$(\frac{1}{\varepsilon},d)$ factor.

We will add a footnote in the final version to clarify this notation.

Paper [1] is not cited, although it is one of the few papers that handle this problem.

Thank you for pointing this out. We apologize for missing this citation.

• [1] provides an $O(\log (k+m))$-approximation for robust $k$-median or $k$-means in $O(n)$ time by constructing a weak coreset of size $O(k+m)$. This is a time-efficient algorithm for robust clustering, while its approximation ratio is not constant.

• [1] also proposes an $\varepsilon$-coreset for robust $k$-median or $k$-means of size $O((1/\varepsilon)^d (k+m)\log n)$. This size contains exponential dependence on $d$, much larger than our size $\tilde{O}(k^2 \varepsilon^{-2} \cdot \min\\{\varepsilon^{-2}, d\\})$.

We will cite this paper in Section 1 in the final version.

Datasets: Does it make sense to run your algorithm on these datasets? For what purposes?

Thank you for raising this question. The choice of these datasets aim to show our proposed methods consistently outperform the baselines [39, 40], across a range of scales ($10^4$–$10^5$), dimensions (2–68), and diverse domains (such as social network data, demographic data, and disease data). Moreover, these datasets cover those used in baseline [39], increasing the fairness in the comparison. Empirical results demonstrate the robustness of our methods' outperformance relative to the baselines.

We will clarify the criterion for selecting these datasets in the final version.

Thank you again for your comments, which have helped us enhance the clarity of our results and the quality of our references.