Geometric Median (GM) Matching for Robust Data Pruning

Correction:

• Eq 6 is a typo it should be $D_S$ instead of $S$ where $D_S$ denotes the selected k-subset.

Clarifications:

• we are happy to incorporate $x_i$ and $x_j$ to better distinguish if this was not obvious.
• $x_i \in R^d$ denotes sample vectors ~ analogous to how any ML algorithm is defined. In practice, this can be original feature space or embeddings --- we dont understand the concern -- we feel this is obvious.
• < , > is standard notation for inner product -- but we agree that we should explicitly mention this.
• while the notation is not incorrect -- we take your feedback and change it to $x_i$ for consistency and readability.
• $\theta_t$ denotes the weight vector at iteration t and $\theta_T$ is weight vector after T iterations i.e. $t=T$ again we feel that this is quite standard notation in any optimization literature.
• z denotes any point in Hilbert space as defined in Definition 3 (Eq 4)
• $\mu_\epsilon^{GM}$ denotes epsilon accurate GM as mentioned right before the Eq (5) in L 251 as defined in Eq (6)

We appreciate the reviewer highlighting relevant prior works.

Specifically:

[1] focuses on robustness under label noise, which is a special case of noise. In contrast, our work addresses arbitrary noise in the data distribution, which presents a broader and more challenging problem.

[2] employs feature distribution matching using Optimal Transport, representing a different methodological approach compared to the herding-based framework that our work builds upon. While [2] does not directly address robustness to arbitrary corruption, our GM-based robustness concept could potentially be extended to this context and analyzed theoretically in future work.

Although these works share similar goals, they tackle distinct problems or adopt different methodologies. In the revised manuscript, we will explicitly compare our approach to [1] and [2], clarifying their contributions and how our method differs in terms of scope, assumptions, and robustness guarantees.

Thanks for your response.

1.I hope the author could explain further, such as in what scenarios the mean is valid and in what scenarios the geometric median is valid.

2.Is the median really stable in most scenarios?

Thanks for engaging in the rebuttal discussions. Below we try to answer these questions:

Mean Estimation

Suppose we are given a set $D$ of N samples $\mathbf{x}_i \in R^d : i=0, 1, \dots, N$ sampled from some distribution $p(x)$ of interest with finite mean and variance. Then, as we know empirical mean $\mu = \frac{1}{N}\sum_i \mathbf{x}_i$ serves as the unbiased estimator of the population mean.

Robust Mean Estimation

However, in real-world scenarios, distributions are often non-Gaussian, and the presence of outliers, skewness, or heavy tails can severely impact the performance of the mean as an estimator.

In this paper we consider the noisy, real-world scenario -- in particular, we study the arbitrary corruption setting where: Given a set of observations from the original distribution of interest, an adversary is allowed to inspect all the samples and arbitrarily perturb up to 1/2 fraction of the samples ( Definition 1 ).

Consider the following simple example:

Let the dataset $D = \{\mathbf{x}_i \in \mathbb{R}^d : i = 1, \dots, N \}$, and suppose an adversary modifies one sample $\mathbf{x}_j$ such that:

$\mathbf{x}_j = - \sum {\mathbf{x}_i \in D \setminus \mathbf{x}_j}$ i.e. it is the negative of the sum of all the other samples in the dataset. This replacement ensures the sum of all samples becomes zero, i.e., the empirical mean is zero regardless of the original data distribution.

This simply implies that a single arbitrarily corrupted sample can break the empirical mean estimation i.e. the empirical mean has the lowest asymptotic breakdown point (Definition 2) of 0.

On the other hand, Geometric Median (Definition 3) has optimal breakdown point of 1/2. This means that up to half of the samples can be arbitrarily corrupted without invalidating the estimate. The geometric median is particularly effective in the following scenarios:

• Heavy-tailed distributions: The geometric median minimizes the $\ell_1$-norm, making it less sensitive to outliers.
• Adversarial settings: Unlike the mean, the geometric median is not unduly influenced by a small subset of corrupted points.

Thus, In summary, the geometric median serves as a robust alternative to the mean in environments where data is corrupted, noisy, or non-Gaussian. While the mean remains a useful and efficient estimator in clean settings, its susceptibility to outliers and low breakdown point limit its applicability in practical scenarios.

By contrast, the geometric median offers resilience and reliability, ensuring stable estimation even under significant corruption or adversarial perturbation.

These robustness properties are well studied in the classical robust statistics literature.

• https://projecteuclid.org/journals/bernoulli/volume-21/issue-4/Geometric-median-and-robust-estimation-in-Banach-spaces/10.3150/14-BEJ645.full
• https://dl.acm.org/doi/10.1145/2897518.2897647
• http://www.iliasdiakonikolas.org/ars-book.pdf

The breakdown point, as defined in Definition 2 (L179-180), is the smallest fraction of contaminated data that can cause an estimator to yield arbitrarily large errors.

The Geometric Median achieves a breakdown point of $\epsilon^* = 1/2$, which is optimal for any estimator. This means the GM can tolerate up to 50% of the dataset being arbitrarily corrupted while still providing meaningful results. This property is derived from the GM’s reliance on the L1​-norm, which limits the influence of individual data points.

Specifically: For any n-point dataset, the GM is determined by minimizing the sum of distances. When fewer than n/2 points are corrupted, the remaining majority of clean points dominate the optimization, ensuring stability.

If the corruption exceeds 50%, the clean data no longer forms a majority, and the GM can shift arbitrarily.

This property is fundamental to our Robust Moment Matching framework, as it ensures that the selected subset remains representative of the uncorrupted data distribution under extreme noise conditions.

Please refer to the classic paper for more detail on breakdown points, robust estimation.

• Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices Hendrik P. Lopuhaä, Peter J. Rousseeuw The Annals of Statistics, Vol. 19, No. 1 (Mar., 1991), pp. 229-248 (20 pages)

We appreciate the reviewer’s attention to detail regarding the expressions and notation. Below, we provide clarifications and corrections where necessary:

Q-1

• $\mathbf{x} \in R^d$ denotes the samples in the noisy dataset D – that needs to be pruned into a smaller subset $D_S$.

• $\theta_t \in R^d$ denotes the weight vector guiding the iterative sampling at time step t initialized randomly ( Line 196 ).

• $\mathbf{x}_t$ denotes the sample chosen at iteration t of the algorithm.

Thus, the dimensions of $\mathbf{x}$ and $\theta_t$ are consistent, as both exist in $R^d$.

Q-2

• This is a typo – it should be $D_S$ i.e. the selected k-subset.

We appreciate the reviewer highlighting relevant prior works.

Specifically:

[1] focuses on robustness under label noise, which is a special case of noise. In contrast, our work addresses arbitrary noise in the data distribution, which presents a broader and more challenging problem.

[2] employs feature distribution matching using Optimal Transport, representing a different methodological approach compared to the herding-based framework that our work builds upon. While [2] does not directly address robustness to arbitrary corruption, our GM-based robustness concept could potentially be extended to this context and analyzed theoretically in future work.

Although these works share similar goals, they tackle distinct problems or adopt different methodologies. In the revised manuscript, we will explicitly compare our approach to [1] and [2], clarifying their contributions and how our method differs in terms of scope, assumptions, and robustness guarantees.

Thanks for your response.

1. I think the author's claim that any noise can be handled is too broad. So far, only label noise and adversarial examples have been seen in papers, which can be attributed to label noise.
2. The formula proofs and notation definitions are too coarse to understand in this version. I will keep the previous score.

1. Indeed, there has been very limited work on data sampling under noisy real world constraints; the handful of works on this topic has been only limited to "label noise" scenarios. for example the Prune4REL work you cited. To the best of our knowledge, This is the first data sampling work that is provably robust to arbitrary noise scenarios i.e. the algorithm works without any assumption on the data distribution or type of noise.

We appreciate your feedback and understand the importance of clarity. However, the phrase "too coarse to understand" is somewhat ambiguous.

The notations and formulas presented in our work adhere to standard conventions widely used in classic optimization and robust mean estimation literature. If certain aspects were unclear or specific steps in the proof were challenging to follow, we would be more than happy to address those directly. Pointing out the exact areas where further elaboration would help will allow us to refine our explanations and make them more accessible.

See for example prior work that used robust mean estimation adaptations -

• https://proceedings.mlr.press/v151/acharya22a/acharya22a.pdf
• http://www.iliasdiakonikolas.org/ars-book.pdf

We appreciate the reviewer’s observation regarding the comparison with existing methods. Below, we clarify the differences between the proposed approach and [1] and [2], which form our main baselines and have been extensively compared in the paper.

[1] Moderate Coreset : ICLR 2023

• First, they compute the centers (mean) of each class - ( Section 3.2. Eq 1 in [1] )
• Then, for each sample they compute euclidean distance from the corresponding class center d(s_i)
• Afterwards, the data points with distances close to the distance median [ median of the scalar distances ] are selected as coreset. (Section 3.2. Eq 2 in [1] ) As we argued that in presence of arbitrary noise, the class center can be arbitrarily shifted meaning the distances d(s_i) is no longer a true representation of distance from the true (uncorrupted) class center, resulting in the method having zero breakdown point as we show in Lemma 1 (Appendix Section 8.5)

[2] Kernel Herding : UAI 2009

• The celebrated kernel herding series of works from Prof Max Welling forms the basis of this paper. In order to solve the moment matching objective i.e. find a subset such that the mean of the subset is close to the mean of the entire dataset, they propose an iterative greedy approach.

However, as we argued that in the noisy real world setting, mean is not a robust estimate of the center. Instead we propose a “Robust Moment Matching objective” where the goal is to find a k-subset such that the mean of the subset is close to the Geometric Median of the original dataset using herding-style iterative algorithm. Note that, Geometric Median is a spatial estimator (defined over vector spaces) unlike median – which is defined over scalars.

So, in summary, we can say the proposed method is Robust variant of Kernel Herding – we also provide theoretical guarantees (Theorem 1) of solving the robust moment matching objective and show how existing methods are not robust (Lemma 1). We also compare with both these methods in every experiment in the paper – we refer to [1] as Moderate DS and [2] as Herding in the tables and plots.

We are happy to highlight these differences with [1,2] more if it was not clear.

We appreciate your continued engagement.

1. We acknowledge your suggestion to include advanced baselines such as Coverage-centric Coreset Selection (CCS) [1] and D2 Pruning [2]. While these methods represent significant advancements in data pruning, they primarily focus on selecting representative subsets without explicitly addressing robustness in noisy settings. Our proposed GM Matching algorithm is specifically designed to handle datasets with potential corruption, aiming to approximate the geometric median to ensure robustness against noise. The generality of our approach allows for extensions to other methods, potentially enhancing their robustness in noisy environments. We will consider incorporating comparisons to these advanced baselines in future work to provide a more comprehensive evaluation.

We respectfully disagree with the assertion that our theoretical analysis is meaningless. Our results are akin to classical moment-matching approaches, demonstrating that our algorithm converges to an ε-neighborhood of the true underlying moment. This convergence guarantees that the selected subset faithfully represents the central tendency of the data, even in the presence of noise, thereby supporting the generalization capabilities of models trained on this subset. While our current analysis does not directly address hyperparameter selection, it provides a solid foundation for understanding the behavior of GM Matching, which can inform future strategies for hyperparameter tuning.

-- the main takeaway from the theory is that even in presence of arbitrary corruption our approach guarantees discovery of a subset such that the mean of the subset is guaranteed to be within a small neighborhood of the true (uncorrupted) mean -- the algorithm is further able to maintain the quadratic improvement in convergence rate compared to random sampling.