Geometric Median (GM) Matching for Robust Data Pruning

## Abstract

Abstract Data pruning, the combinatorial task of selecting a small and informative subset from a large dataset, is crucial for mitigating the enormous computational costs associated with training data-hungry modern deep learning models at scale. Since large-scale data collections are invariably noisy, developing data pruning strategies that remain robust even in the presence of corruption is critical in practice. Unfortunately, the existing heuristics for (robust) data pruning lack theoretical coherence and rely on heroic assumptions, that are, often unattainable, by the very nature of the problem setting. Moreover, these strategies often yield sub-optimal neural scaling laws even compared to random sampling, especially in scenarios involving strong corruption and aggressive pruning rates – making provably robust data pruning an open challenge. In response, in this work, we propose Geometric Median ( Gm ) Matching – a herding (Welling,, 2009 ) style greedy algorithm – that yields a k 𝑘 k italic_k -subset such that the mean of the subset approximates the geometric median of the (potentially) noisy dataset. Theoretically, we show that Gm Matching enjoys an improved 𝒪 ⁢ ( 1 / k ) 𝒪 1 𝑘 {\mathcal{O}}(1/k) caligraphic_O ( 1 / italic_k ) scaling over 𝒪 ⁢ ( 1 / k ) 𝒪 1 𝑘 {\mathcal{O}}(1/\sqrt{k}) caligraphic_O ( 1 / square-root start_ARG italic_k end_ARG ) scaling of uniform sampling; while achieving the optimal breakdown point of 1/2 even under arbitrary corruption. Extensive experiments across popular deep learning benchmarks indicate that Gm Matching consistently outperforms prior state-of-the-art; the gains become more profound at high rates of corruption and aggressive pruning rates; making Gm Matching a strong baseline for future research in robust data pruning.

## 1 Introduction

Recent success of deep learning has been largely fueled by training gigantic models over vast amounts of training data (Radford et al.,, , ; Brown et al.,, ; Kaplan et al.,, ; Hestness et al.,, ). Such large scale training, however is associated with enormous computational costs hindering the path to democratizing AI (Paul et al.,, ).

Data pruning, the combinatorial task of downsizing a large training set into a small informative subset (Feldman,, ; Agarwal et al.,, ; Muthukrishnan et al.,, ; Har-Peled,, ; Feldman and Langberg,, ), is a promising approach for reducing the enormous computational and storage costs of modern deep learning.
Consequently, a large body of recent works have been proposed to solve the data selection problem. At a high level, data pruning approaches rely on some carefully designed pruning metrics and rank the training samples based on the scores and retain a fraction of them as representative samples (super samples), used for training the downstream model. For example, (Xia et al.,, ; Joshi and Mirzasoleiman,, ; Sorscher et al.,, ) calculate the importance score of a sample in terms of the distance from the centroid of its corresponding class marginal.
Samples closer to the centroid are considered most prototypical (easy) and those far from the centroid are treated as least prototypical (hard). Canonically, similar scoring criterion have been developed in terms of gradients (Paul et al.,, ), uncertainty (Pleiss et al.,, ), forgetfulness (Toneva et al.,, ). It is worth noting that the distance-based score is closely related to the uncertainty / gradient forgetting based score. Samples close (far away) to the class centroid are often associated with smaller (larger) gradient norm ; lower (higher) uncertainty; harder (easier) to forget (Paul et al.,, ; Sorscher et al.,, ; Xia et al.,, ).

Robustness vs Diversity : In the ideal scenario (i.e. in absence of any corruption), hard examples are known to contribute the most in downstream generalization performance (Katharopoulos and Fleuret,, ; Joshi et al.,, ; Huang et al.,, ; Balcan et al.,, ) as they often capture most of the usable information in the dataset (Xu et al.,, ). On the other hand, in realistic noisy scenarios involving outliers, this strategy often fails since the noisy examples are wrongly deemed informative
for training (Zhang and Sabuncu,, ; Park et al.,, ). Pruning methods specifically designed for such noisy scenarios thus propose to retain the most representative (easy) samples (Pleiss et al.,, ; Jiang et al.,, ; Har-Peled et al.,, ; Shah et al.,, ; Shen and Sanghavi,, ). However, by only choosing samples far from the decision boundary, these methods ignore the more informative uncorrupted less prototypical samples. This can often result in sub-optimal downstream performance and in fact can also lead to degenerate solutions due to a covariance-shift problem (Sugiyama and Kawanabe,, ); giving rise to a robustness vs diversity trade off (Xia et al.,, ).
This issue restricts the applicability of these methods, as realistic scenarios often deviate from expected conditions, making it challenging or impractical to adjust the criteria and methods accordingly.

To go beyond these limitations,
in this work, we consider the setting where a fraction of the samples can be arbitrarily corrupted( Definition 1). We make a key observation that in presence of arbitrary corruption, the class center itself can be arbitrarily shifted and in fact need not even lie in the convex hull of the underlying clean samples. That is to say, in the arbitrary corruption scenario, the entire notion of easy (robust) / hard based on heuristic falls apart. We provide a more formal argument in Section 3. Figure 4 elaborates this over a toy example.

Figure: Algorithm 1 Gm Matching

In response, we develop a selection strategy that aims to find subset such that the discrepancy between the mean of subset and the geometric median (Gm)(Definition 3) of the (potentially noisy) dataset is minimized. We call this algorithm Geometric Median Matching and describe it in Section 4. We show that Gm Matching is guaranteed to converge to a neighborhood of the underlying true (uncorrupted) mean of the (corrupted) dataset even when $1/2$ fraction of the samples are arbitrarily corrupted.

Contributions

Overall, our contributions can be summarized as follows:

- •
We systematically investigate and extend data pruning in presence of corruption. In particular, we study data pruning under the gross corruption framework ( Definition 1), where up to 1/2 fraction of the training examples are allowed to be arbitrarily corrupted.
- •
We show that, existing pruning heuristics (including the ones proposed for robust scenarios) break down under this strong corruption.
In response; exploiting robustness property of Geometric Median; we propose a robust data pruning strategy that we call Gm Matching that remains robust even when up to 1/2 fraction of the samples are arbitrarily corrupted.
- •
Theoretically, we show that, Gm Matching converges to a neighborhood of original underlying mean, at an impressive ${\mathcal{O}}(1/k)$ rate while being robust.
- •
Extensive experiments over CIFAR 10/100, Tiny ImageNet, across feature corruption, label noise and adversarial attacks indicate the superiority of Gm Matching over existing methods. We improve over prior work almost in all settings, the gains are especially more profound in presence of corruption and at aggressive pruning rates. Thus, making GM Matching a strong baseline for future research in robust data pruning.

## 2 Problem Setup

Given a set of observations,
data pruning strategies aim to select a subset; such that training a parametric model
on the subset, yields (approximately) similar generalization performance as training on the entire dataset.
However, this paper considers the setting where the training data
is generated via an $\alpha$-corrupted generation process (Definition 1).

Definition 1 ($\alpha$-corrupted generation process).
Given $\psi\in[0,\frac{1}{2})$ and a set of observations from the original distribution of interest, an adversary is allowed to inspect all the samples and arbitrarily perturb up to $\psi$ fraction of them. We refer to a set of samples ${\mathcal{D}}={\mathcal{D}}_{{\mathcal{G}}}\cup{\mathcal{D}}_{{\mathcal{B}}}$ generated through this process as $\alpha$-corrupted where, $\alpha:=|{\mathcal{D}}_{{\mathcal{B}}}|/|{\mathcal{D}}_{{\mathcal{G}}}|=\frac{
\psi}{1-\psi}<1$. ${\mathcal{D}}_{{\mathcal{B}}}$ and ${\mathcal{D}}_{{\mathcal{G}}}$ denote the sets of corrupt and clean samples.

Given such an $\alpha$-corrupted (^1^11 This strong corruption model is often referred to as the Gross Contamination Framework (Diakonikolas and Kane,, ). It also generalizes the popular Huber Contamination Model (Huber,, ) as well as the notorious Byzantine Corruption Framework (Lamport et al.,, ).) set of observations ${\mathcal{D}}={\mathcal{D}}_{{\mathcal{G}}}\cup{\mathcal{D}}_{{\mathcal{B}}}=
\{({\mathbf{x}}_{i},y_{i})\in{\mathbb{R}}^{d}\times{\mathcal{Y}}\}_{i=1}^{N}$, the goal of robust data pruning is thus to judiciously select a subset ${\mathcal{D}}_{\mathcal{S}}\subseteq{\mathcal{D}}$
; that encapsulates the comprehensive statistical characteristics of the underlying clean (uncorrupted) distribution induced by subset ${\mathcal{D}}_{{\mathcal{G}}}$ without any a-priori knowledge about the corrupted samples.

Note that, allowing the noisy samples to be arbitrarily corrupted enables us to generalize many important robustness scenarios; including corrupt features, label noise and adversarial attacks.

###### Definition 1 ( α 𝛼 \alpha italic_α -corrupted generation process).

## 3 Breakdown Point Analysis of Pruning Methods

Figure: (a) Uniform
Refer to caption: extracted/5689101/plots/toy/corr=0/uniform.png

Figure: (a) Uniform
Refer to caption: extracted/5689101/plots/toy/corr=20/uniform.png

Figure: (a) Uniform
Refer to caption: extracted/5689101/plots/toy/corr=40/uniform.png

Figure: (a) Uniform
Refer to caption: extracted/5689101/plots/toy/corr=45/uniform.png

We begin by analyzing the robustness of existing data pruning algorithms under the strong gross contamination framework via breakdown point analysis (Donoho and Huber,, ) – a common method to assess the resilience of an estimator.

Definition 2 (Breakdown Point).
The breakdown point of an estimator is defined as the smallest fraction of contaminated data that can cause the estimator to result in arbitrarily large errors. An estimator with a high breakdown point is considered robust because it can handle a larger amount of contamination before failing. In the context of Definition 1 we say an estimator has optimal breakdown point 1/2 if it is robust in presence of $\alpha$-corruption
$\forall\;\alpha<1$.

Score based pruning algorithms determine importance using similarity measures relative to the corresponding class centroid. For instance, consider the popular importance score:

$$ $\displaystyle d({\mathbf{x}}_{i},y_{i})=\|{\mathbf{x}}_{i}-\bm{\mu}_{y}\|_{2}^ {2}:\forall({\mathbf{x}}_{i},y_{i})\in{\mathcal{D}}$ (1) $$

where, $\bm{\mu}_{y}$ denotes the class centroid , defined as:

$$ $\displaystyle\bm{\mu}_{y}=\frac{\sum_{({\mathbf{x}}_{i},y_{i})\in{\mathcal{D}} }\mathbf{1}(y_{i}=y){\mathbf{x}}_{i}}{\sum_{({\mathbf{x}}_{i},y_{i})\in{ \mathcal{D}}}\mathbf{1}(y_{i}=y)}:\forall y\in{\mathcal{Y}}$ (2) $$

In the ideal setting, given a batch of i.i.d samples $\bm{\mu}_{y}=\bm{\mu}_{y}^{\mathcal{G}}=\mathbb{E}_{{\mathbf{x}}\sim{\mathcal{
D}}_{\mathcal{G}}}({\mathbf{x}})$. However, the presence of even a single grossly corrupted sample can cause the centroid estimate to deviate arbitrarily from the true mean. Consider a single grossly corrupt sample $({\mathbf{x}}_{i}^{\mathcal{B}},y_{i})$ such that :

$$ $\displaystyle{\mathbf{x}}_{i}^{\mathcal{B}}={\sum_{({\mathbf{x}}_{i},y_{i})\in {\mathcal{D}}}\mathbf{1}(y_{i}=y)}\bm{\mu}_{y}^{\mathcal{B}}-\sum_{({\mathbf{x }}_{i},y_{i})\in{\mathcal{D}}\setminus({\mathbf{x}}_{i}^{\mathcal{B}},y_{i})} \mathbf{1}(y_{i}=y){\mathbf{x}}_{i}$ (3) $$

resulting in shifting the estimated centroid $\Delta\bm{\mu}_{y}=\bm{\mu}_{y}^{\mathcal{B}}-\bm{\mu}_{y}^{\mathcal{G}}$

###### Lemma 1 .

A single gross corrupted sample (3) causes the importance scores to deviate arbitrarily:

$$ $\displaystyle\Delta d({\mathbf{x}}_{i},y_{i})=\|\Delta\bm{\mu}_{y}\|^{2}-2 \bigg{(}{\mathbf{x}}_{i}-\bm{\mu}_{y}^{\mathcal{G}}\bigg{)}^{T}\Delta\bm{\mu}_ {y}$ (4) $$

Implying, these methods yield the lowest possible asymptotic breakdown of 0.

Similarly, under the same corruption, moment matching based methods, would to find subsets such that centroid of the subset is closely aligned to the perturbed centroid implying a bias ${\mathcal{O}}(\Delta\bm{\mu}_{y})$. Thus, moment matching based methods also has the asymptotic breakdown of 0.
Figure 4,5 validates these theoretical implications.

###### Definition 2 ( Breakdown Point ) .

###### Lemma 1 .

## 4 Geometric Median ( GM ) Matching

Under the gross contamination framework (Definition 1), the vulnerability of pruning algorithms can be attributed to the centroid estimation. Motivated by this key observation in this paper we propose Gm Matching – a data pruning strategy that remains provably effective even when up to $1/2$ fraction of the samples are arbitrary corrupted without any distributional assumption on the data.

Gm Matching involves two key steps:
•
Find an estimate of the centroid $\bm{\mu}$ of training observations such that $\Delta=\|\bm{\mu}-\bm{\mu}^{\mathcal{G}}\|$ remains bounded even when the observations are $\alpha$-corrupted (Definition 1).
•
Find a subset ${\mathcal{S}}\subseteq{\mathcal{D}}$ such that the empirical mean of the subset $\approx\bm{\mu}$.

In the rest of this section, we discuss these two key ideas in detail.

### 4.1 Robust Centroid Estimation

In the univariate setting, various robust mean estimators, such as the median and the trimmed mean, are known to achieve the optimal breakdown point 1/2. To extend these estimators to the multivariate setting, a common approach can be applying the univariate estimators to each dimension independently. However, in high dimensions this can become problematic e.g. when $d>2$ these estimates need not lie in the convex hull of the samples and are not orthogonal equivariant i.e. do not commute with co-ordinate transform and can become degenerate in overparameterized settings ($n\ll d$) (Lopuhaa et al.,, ; Rousseeuw and Leroy,, ). On the other hand, M-estimators are affine equivariant but have breakdown point at most $1/(d+1)$ (Donoho and Huber,, ).

Figure: (a) $\psi=0$
Refer to caption: extracted/5689101/plots/toy/corr=0/dist.png

In this context, Geometric Median (Gm) ( Definition 3) is a well studied spatial estimator, known for several nice properties like rotation and translation invariance and optimal breakdown point of 1/2 under gross corruption (Minsker et al.,, ; Kemperman,, ).

Definition 3 (Geometric Median).
Given a finite collection of observations $\{{\mathbf{x}}_{1},{\mathbf{x}}_{2},\dots\mathbf{x}_{n}\}$ defined over Hilbert space ${\mathcal{H}}\in{\mathbb{R}}^{d}$, equipped with norm $\|\cdot\|$ and inner $\langle\cdot\rangle$ operators,
the geometric median(or Fermat-Weber point) (Weber et al.,, ) is defined as:
${\mathbf{x}}_{*}=\textsc{Gm}(\{{\mathbf{x}}_{1},{\mathbf{x}}_{2},\dots\mathbf{
x}_{n}\})=\operatorname*{arg\,min}_{{\mathbf{z}}\in{\mathcal{H}}}\bigg{[}\rho(
{\mathbf{z}}):=\sum_{i=1}^{n}\bigg{\|}{\mathbf{z}}-{\mathbf{x}}_{i}\bigg{\|}
\bigg{]}$
(5)
Computing the Gm exactly is known to be hard and no linear time algorithm exists (Bajaj,, ). Consequently, it is necessary to rely on approximation methods to estimate the geometric median (Weiszfeld,, ; Vardi and Zhang,, ; Cohen et al.,, ). We call a point ${\mathbf{x}}_{\epsilon}\in{\mathcal{H}}$ an $\epsilon$-accurate geometric median if it holds that: $\rho({\mathbf{x}}_{\epsilon})\leq(1+\epsilon)\rho({\mathbf{x}}_{\ast})$ i.e.
$\sum_{i=1}^{n}\bigg{\|}{\mathbf{x}}_{\epsilon}-{\mathbf{x}}_{i}\bigg{\|}\leq(1
+\epsilon)\sum_{i=1}^{n}\bigg{\|}{\mathbf{x}}_{\ast}-{\mathbf{x}}_{i}\bigg{\|}$
(6)

###### Definition 3 ( Geometric Median ) .

### 4.2 Sampling via Robust Moment Matching

We exploit the breakdown and translation invariance property of Gm to perform subset selection while being resilient to arbitrary corruption. In particular,

Given a random batch of samples ${\mathcal{D}}$ from an $\alpha$ corrupted dataset ( Definition 1), access to an $\epsilon$ accurate $\textsc{Gm}(\cdot)$ oracle; we aim to find a $k$-subset of samples such that the mean of the selected subset approximately matches the geometric median of the training dataset, i.e. we aim solve:
$\operatorname*{arg\,min}_{{\mathcal{D}}_{\mathcal{S}}\subseteq{\mathcal{D}},|{
\mathcal{D}}_{\mathcal{S}}|=k}\bigg{\|}\bm{\mu}^{\textsc{Gm}}_{\epsilon}-\frac
{1}{k}\sum_{{\mathbf{x}}_{i}\in{\mathcal{S}}}{\mathbf{x}}_{i}\bigg{\|}^{2}$
(7)
where, $\bm{\mu}^{\textsc{Gm}}_{\epsilon}$ denotes the $\epsilon$-approximate Gm (6) of training dataset ${\mathcal{D}}$.

Intuitively, if such a subset can be found, the expected cost (e.g. loss / average gradient) over ${\mathcal{S}}$ is guaranteed to be close (as characterized in Equation 11) to the expected cost over the uncorrupted examples ${\mathcal{D}}_{\mathcal{G}}$; enabling robust data pruning. This is because, even in presence of grossly corrupted samples (unbounded), Gm remains bounded w.r.t the underlying true mean (Acharya et al.,, ; Minsker et al.,, ; Cohen et al.,, ; Wu et al.,, ; Chen et al.,, ).

Note that the proposed robust moment matching objective (7) is an instance of the famous set function maximization problem – known to be NP hard via a reduction from $k$-set cover (Feige,, ; Nemhauser et al.,, ). In this work, we adopt the iterative, herding (Welling,, ; Chen et al.,, ) style greedy approach to approximately solve (7). The idea is simple –

We start with a suitably chosen ${\mathbf{\theta}}_{0}\in{\mathbb{R}}^{d}$; and repeatedly perform the following updates, adding one sample at a time, $k$ times:
$\displaystyle{\mathbf{x}}_{t+1}$
$\displaystyle:=\operatorname*{arg\,max}_{{\mathbf{x}}\in{\mathcal{D}}}\;
\langle{\mathbf{\theta}}_{t},{\mathbf{x}}\rangle$
(8)
$\displaystyle{\mathbf{\theta}}_{t+1}$
$\displaystyle:={\mathbf{\theta}}_{t}+\bigg{(}\bm{\mu}^{\textsc{Gm}}_{\epsilon}
-{\mathbf{x}}_{t+1}\bigg{)}$
(9)

For ease of exposition, let ${\mathbf{\theta}}_{0}=\bm{\mu}^{\textsc{Gm}}_{\epsilon}$. Then, at iteration $t=T$, Gm Matching is performing:

$$ $\displaystyle{\mathbf{x}}_{T+1}=\operatorname*{arg\,max}_{{\mathbf{x}}\in{ \mathcal{D}}}\bigg{[}\langle\bm{\mu}^{\textsc{Gm}}_{\epsilon},{\mathbf{x}} \rangle-\frac{1}{T+1}\sum_{t=1}^{T}\langle{\mathbf{x}},{\mathbf{x}}_{t}\rangle \bigg{]}$ (10) $$

Thus, evidently, Gm Matching is performing greedy minimization of the error (7).

Intuitively, at each iteration, Gm Matching accumulates the discrepancies between the Gm of dataset and empirical mean of the chosen samples. By pointing towards the direction that reduces the accumulated error, $\mathbf{\theta}_{t}$ guides the algorithm to explore underrepresented regions of the feature space, thus promoting diversity. Moreover, by matching Gm (robust moment), the algorithm ensures that far-away points (outliers) suffer larger penalty – consequently, encouraging Gm Matching to choose more samples near the convex hull of uncorrupted points $\text{conv}\{\phi_{\mathcal{B}}({\mathbf{x}})|{\mathbf{x}}\in{\mathcal{D}}_{
\mathcal{G}}\}$.

Theoretically, we can establish the following convergence guarantee for Gm Matching :

Theorem 1.
Suppose that, we are given, a set of $\alpha$-corrupted samples ${\mathcal{D}}$ (Definition 1), pretrained proxy model $\phi_{\mathbf{B}}$, and an $\epsilon$ approx. $\textsc{Gm}(\cdot)$ oracle (5). Then, Gm Matching guarantees that the mean of the selected $k$-subset $\bm{\mu}^{\mathcal{S}}=\frac{1}{k}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{
\mathcal{S}}}{\mathbf{x}}_{i}$ converges to the neighborhood of $\bm{\mu}^{\mathcal{G}}=\mathbb{E}_{{\mathbf{x}}\in{\mathcal{D}}_{\mathcal{G}}}
({\mathbf{x}})$ at the rate ${\mathcal{O}}(\frac{1}{k})$ such that:
$\mathbb{E}\bigg{\|}\bm{\mu}^{\mathcal{S}}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2}
\leq\frac{8|{\mathcal{D}}_{\mathcal{G}}|}{(|{\mathcal{D}}_{\mathcal{G}}|-|{
\mathcal{D}}_{\mathcal{B}}|)^{2}}\sum_{{\mathbf{x}}\in{\mathcal{D}}_{\mathcal{
G}}}\mathbb{E}\bigg{\|}{\mathbf{x}}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2}+\frac{
2\epsilon^{2}}{(|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}|)^{
2}}$
(11)

This result suggest that, even in presence of $\alpha$ corruption, the proposed algorithm Gm Matching converges to a neighborhood of the true mean, where the neighborhood radius depends on two terms – the first term depend on the variance of the uncorrupted samples and the second term depends on how accurately the Gm is calculated. Consequently, we say that Gm Matching achieves the optimal breakdown point 1/2. The detailed proofs are provided in Section 7.

###### Theorem 1 .

## 5 Experiments

In this section, we outline our experimental setup, present our key empirical findings, and discuss deeper insights into the performance of Gm Matching.

### 5.1 Experimental Setup

A. Baselines:

To ensure reproducibility, our experimental setup is identical to (Xia et al.,, ). We compare the proposed Gm Matching selection strategy against the following popular data pruning strategies as baselines for comparison: (1) Random; (2) Herding Welling, (); (3) Forgetting Toneva et al., (); (4) GraNd-score Paul et al., (); (5) EL2N-score Paul et al., (); (6) Optimization-based Yang et al., (); (7) Self-sup.-selection Sorscher et al., () and (8) Moderate (Xia et al.,, ). We do not run these baselines for be these baselines are borrowed from (Xia et al.,, ).

Additionally, for further ablations we compare Gm Matching with many (natural) distance based geometric pruning strategies: (Uniform) Random Sampling, (Easy) Selection of samples closest to the centroid; (Hard) Selection of samples farthest from the centroid; (Moderate) (Xia et al.,, ) Selection of samples closest to the median distance from the centroid; (Herding) Moment Matching (Chen et al.,, ), (GM Matching) Robust Moment (GM) Matching (7).

B. Datasets and Networks :

We perform extensive experiments across three popular image classification datasets - CIFAR10, CIFAR100 and Tiny-ImageNet. Our experiments span popular deep nets including ResNet-18/50 (He et al.,, ), VGG-16 (Simonyan and Zisserman,, ), ShuffleNet (), SENet (Hu et al.,, ), EfficientNet-B0(Tan and Le,, ).

C. Implementation Details :

For the CIFAR-10/100 experiments, we utilize a batch size of 128 and employ SGD optimizer with a momentum of 0.9, weight decay of 5e-4, and an initial learning rate of 0.1. The learning rate is reduced by a factor of 5 after the 60th, 120th, and 160th epochs, with a total of 200 epochs. Data augmentation techniques include random cropping and random horizontal flipping. In the Tiny-ImageNet experiments, a batch size of 256 is used with an SGD optimizer, momentum of 0.9, weight decay of 1e-4, and an initial learning rate of 0.1. The learning rate is decreased by a factor of 10 after the 30th and 60th epochs, with a total of 90 epochs. Random horizontal flips are applied for data augmentation. Each experiment is repeated over 5 random seeds and the variances are noted.

For all the experiments in this paper we use Weiszfield Solver (Weiszfeld,, ) to compute Gm approximately.

D. Proxy Model :

Needless to say, identifying sample importance is an ill-posed problem without some notion of similarity among the samples. Thus, it is common to assume access to a proxy encoder $\phi_{\mathbf{B}}(\cdot):{\mathbb{R}}^{d}\to{\mathcal{H}}\in{\mathbb{R}}^{p}$ that maps the features to a separable Hilbert space equiped with inner product. Intuitively, this simply means that the embedding space of the encoder fosters proximity of semantically similar examples, while enforcing the separation of dissimilar ones – a property often satisfied by even off-the-shelf pretrained foundation models (Hessel et al.,, ; Sorscher et al.,, ). We perform experiments across multiple choices of such proxy encoder scenarios: A. Standard Setting: In Table 1- 6, we show results for the case when the proxy model shares the same architecture as the model e.g. ResNet-50 to be trained downstream, and is pretrained (supervised) on the clean target dataset e.g. TinyImageNet. Additionally, we also experiment with B. Distribution Shift: proxy model pretrained on a different (distribution shifted) dataset e.g. ImageNet and used to sample from Mini ImageNet. C. Network Transfer: Where, the proxy has a different network compared to the classifier. We describe these setups in more detail in Section 5.4.

**Table 1: No Corruption : Comparing (Test Accuracy) pruning algorithms on CIFAR-100 and Tiny-ImageNet in the uncorrupted setting. ResNet-50 is used both as proxy and for downstream classification.**
| CIFAR-100 |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 40% | 60% | 80% | 100% | Mean $\uparrow$ |
| Random | 50.26$\pm$3.24 | 53.61$\pm$2.73 | 64.32$\pm$1.77 | 71.03$\pm$0.75 | 74.12$\pm$0.56 | 78.14$\pm$0.55 | 62.67 |
| Herding | 48.39$\pm$1.42 | 50.89$\pm$0.97 | 62.99$\pm$0.61 | 70.61$\pm$0.44 | 74.21$\pm$0.49 | 78.14$\pm$0.55 | 61.42 |
| Forgetting | 35.57$\pm$1.40 | 49.83$\pm$0.91 | 59.65$\pm$2.50 | 73.34$\pm$0.39 | 77.50$\pm$0.53 | 78.14$\pm$0.55 | 59.18 |
| GraNd-score | 42.65$\pm$1.39 | 53.14$\pm$1.28 | 60.52$\pm$0.79 | 69.70$\pm$0.68 | 74.67$\pm$0.79 | 78.14$\pm$0.55 | 60.14 |
| EL2N-score | 27.32$\pm$1.16 | 41.98$\pm$0.54 | 50.47$\pm$1.20 | 69.23$\pm$1.00 | 75.96$\pm$0.88 | 78.14$\pm$0.55 | 52.99 |
| Optimization-based | 42.16$\pm$3.30 | 53.19$\pm$2.14 | 58.93$\pm$0.98 | 68.93$\pm$0.70 | 75.62$\pm$0.33 | 78.14$\pm$0.55 | 59.77 |
| Self-sup.-selection | 44.45$\pm$2.51 | 54.63$\pm$2.10 | 62.91$\pm$1.20 | 70.70$\pm$0.82 | 75.29$\pm$0.45 | 78.14$\pm$0.55 | 61.60 |
| Moderate-DS | 51.83$\pm$0.52 | 57.79$\pm$1.61 | 64.92$\pm$0.93 | 71.87$\pm$0.91 | 75.44$\pm$0.40 | 78.14$\pm$0.55 | 64.37 |
| Gm Matching | 55.93$\pm$ 0.48 | 63.08$\pm$ 0.57 | 66.59$\pm$ 1.18 | 70.82$\pm$ 0.59 | 74.63$\pm$ 0.86 | 78.14$\pm$ 0.55 | 66.01 |
| Tiny ImageNet |  |  |  |  |  |  |  |
| Random | 24.02$\pm$0.41 | 29.79$\pm$0.27 | 34.41$\pm$0.46 | 40.96$\pm$0.47 | 45.74$\pm$0.61 | 49.36$\pm$0.25 | 34.98 |
| Herding | 24.09$\pm$0.45 | 29.39$\pm$0.53 | 34.13$\pm$0.37 | 40.86$\pm$0.61 | 45.45$\pm$0.33 | 49.36$\pm$0.25 | 34.78 |
| Forgetting | 22.37$\pm$0.71 | 28.67$\pm$0.54 | 33.64$\pm$0.32 | 41.14$\pm$0.43 | 46.77$\pm$0.31 | 49.36$\pm$0.25 | 34.52 |
| GraNd-score | 23.56$\pm$0.52 | 29.66$\pm$0.37 | 34.33$\pm$0.50 | 40.77$\pm$0.42 | 45.96$\pm$0.56 | 49.36$\pm$0.25 | 34.86 |
| EL2N-score | 19.74$\pm$0.26 | 26.58$\pm$0.40 | 31.93$\pm$0.28 | 39.12$\pm$0.46 | 45.32$\pm$0.27 | 49.36$\pm$0.25 | 32.54 |
| Optimization-based | 13.88$\pm$2.17 | 23.75$\pm$1.62 | 29.77$\pm$0.94 | 37.05$\pm$2.81 | 43.76$\pm$1.50 | 49.36$\pm$0.25 | 29.64 |
| Self-sup.-selection | 20.89$\pm$0.42 | 27.66$\pm$0.50 | 32.50$\pm$0.30 | 39.64$\pm$0.39 | 44.94$\pm$0.34 | 49.36$\pm$0.25 | 33.13 |
| Moderate-DS | 25.29$\pm$0.38 | 30.57$\pm$0.20 | 34.81$\pm$0.51 | 41.45$\pm$0.44 | 46.06$\pm$0.33 | 49.36$\pm$0.25 | 35.64 |
| Gm Matching | 27.88$\pm$0.19 | 33.15$\pm$0.26 | 36.92$\pm$0.40 | 42.48$\pm$0.12 | 46.75$\pm$0.51 | 49.36$\pm$0.25 | 37.44 |

### 5.2 Ideal (No Corruption) Scenario

Our first sets of experiments involve performing data pruning across selection ratio ranging from 20% - 80% in the uncorrupted setting. The corresponding results, presented in Table 1, indicate that while Gm Matching is developed with robustness scenarios in mind, it outperforms the existing strong baselines even in the clean setting. Overall, on both CIFAR-100 and Tiny ImageNet Gm Matching improves over the prior methods > 2% on an average. In particular, we note that Gm Matching enjoys larger gains in the low data selection regime, while staying competitive at low pruning rates.

**Table 2: Image Corruption ( CIFAR 100 ): Comparing (Test Accuracy) pruning methods when 20% of the images are corrupted. ResNet-50 is used both as proxy and for downstream classification.**
| CIFAR-100 |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Method / Selection ratio | 20% | 30% | 40% | 60% | 80% | 100% | Mean $\uparrow$ |
| No Corruption |  |  |  |  |  |  |  |
| Random | 50.26$\pm$3.24 | 53.61$\pm$2.73 | 64.32$\pm$1.77 | 71.03$\pm$0.75 | 74.12$\pm$0.56 | 78.14$\pm$0.55 | 62.67 |
| Herding | 48.39$\pm$1.42 | 50.89$\pm$0.97 | 62.99$\pm$0.61 | 70.61$\pm$0.44 | 74.21$\pm$0.49 | 78.14$\pm$0.55 | 61.42 |
| Forgetting | 35.57$\pm$1.40 | 49.83$\pm$0.91 | 59.65$\pm$2.50 | 73.34$\pm$0.39 | 77.50$\pm$0.53 | 78.14$\pm$0.55 | 59.18 |
| GraNd-score | 42.65$\pm$1.39 | 53.14$\pm$1.28 | 60.52$\pm$0.79 | 69.70$\pm$0.68 | 74.67$\pm$0.79 | 78.14$\pm$0.55 | 60.14 |
| EL2N-score | 27.32$\pm$1.16 | 41.98$\pm$0.54 | 50.47$\pm$1.20 | 69.23$\pm$1.00 | 75.96$\pm$0.88 | 78.14$\pm$0.55 | 52.99 |
| Optimization-based | 42.16$\pm$3.30 | 53.19$\pm$2.14 | 58.93$\pm$0.98 | 68.93$\pm$0.70 | 75.62$\pm$0.33 | 78.14$\pm$0.55 | 59.77 |
| Self-sup.-selection | 44.45$\pm$2.51 | 54.63$\pm$2.10 | 62.91$\pm$1.20 | 70.70$\pm$0.82 | 75.29$\pm$0.45 | 78.14$\pm$0.55 | 61.60 |
| Moderate-DS | 51.83$\pm$0.52 | 57.79$\pm$1.61 | 64.92$\pm$0.93 | 71.87$\pm$0.91 | 75.44$\pm$0.40 | 78.14$\pm$0.55 | 64.37 |
| Gm Matching | 55.93$\pm$ 0.48 | 63.08$\pm$ 0.57 | 66.59$\pm$ 1.18 | 70.82$\pm$ 0.59 | 74.63$\pm$ 0.86 | 78.14$\pm$ 0.55 | 66.01 |
| 5% Feature Corruption |  |  |  |  |  |  |  |
| Random | 43.14$\pm$3.04 | 54.19$\pm$2.92 | 64.21$\pm$2.39 | 69.50$\pm$1.06 | 72.90$\pm$0.52 | 77.26$\pm$0.39 | 60.79 |
| Herding | 42.50$\pm$1.27 | 53.88$\pm$3.07 | 60.54$\pm$0.94 | 69.15$\pm$0.55 | 73.47$\pm$0.89 | 77.26$\pm$0.39 | 59.81 |
| Forgetting | 32.42$\pm$0.74 | 49.72$\pm$1.64 | 54.84$\pm$2.20 | 70.22$\pm$2.00 | 75.19$\pm$0.40 | 77.26$\pm$0.39 | 56.48 |
| GraNd-score | 42.24$\pm$0.57 | 53.48$\pm$0.76 | 60.17$\pm$1.66 | 69.16$\pm$0.81 | 73.35$\pm$0.81 | 77.26$\pm$0.39 | 59.68 |
| EL2N-score | 26.13$\pm$1.75 | 39.01$\pm$1.42 | 49.89$\pm$1.87 | 68.36$\pm$1.41 | 73.10$\pm$0.36 | 77.26$\pm$0.39 | 51.30 |
| Optimization-based | 38.25$\pm$3.04 | 50.88$\pm$6.07 | 57.26$\pm$0.93 | 68.02$\pm$0.39 | 73.77$\pm$0.56 | 77.26$\pm$0.39 | 57.64 |
| Self-sup.-selection | 44.24$\pm$0.48 | 55.99$\pm$1.21 | 61.03$\pm$0.59 | 69.96$\pm$1.07 | 74.56$\pm$1.17 | 77.26$\pm$0.39 | 61.16 |
| Moderate-DS | 46.78$\pm$1.90 | 57.36$\pm$1.22 | 65.40$\pm$1.19 | 71.46$\pm$0.19 | 75.64$\pm$0.61 | 77.26$\pm$0.39 | 63.33 |
| Gm Matching | 49.50$\pm$0.72 | 60.23$\pm$0.88 | 66.25$\pm$0.51 | 72.91$\pm$0.26 | 75.10$\pm$0.29 | 77.26$\pm$0.39 | 64.80 |
| 10% Feature Corruption |  |  |  |  |  |  |  |
| Random | 43.27$\pm$3.01 | 53.94$\pm$2.78 | 62.17$\pm$1.29 | 68.41$\pm$1.21 | 73.50$\pm$0.73 | 76.50$\pm$0.63 | 60.26 |
| Herding | 44.34$\pm$1.07 | 53.31$\pm$1.49 | 60.13$\pm$0.38 | 68.20$\pm$0.74 | 74.34$\pm$1.07 | 76.50$\pm$0.63 | 60.06 |
| Forgetting | 30.43$\pm$0.70 | 47.50$\pm$1.43 | 53.16$\pm$0.44 | 70.36$\pm$0.82 | 75.11$\pm$0.71 | 76.50$\pm$0.63 | 55.31 |
| GraNd-score | 36.36$\pm$1.06 | 52.26$\pm$0.66 | 60.22$\pm$1.39 | 68.96$\pm$0.62 | 72.78$\pm$0.51 | 76.50$\pm$0.63 | 58.12 |
| EL2N-score | 21.75$\pm$1.56 | 30.80$\pm$2.23 | 41.06$\pm$1.23 | 64.82$\pm$1.48 | 73.47$\pm$1.30 | 76.50$\pm$0.63 | 46.38 |
| Optimization-based | 37.22$\pm$0.39 | 48.92$\pm$1.38 | 56.88$\pm$1.48 | 67.33$\pm$2.15 | 72.94$\pm$1.90 | 76.50$\pm$0.63 | 56.68 |
| Self-sup.-selection | 42.01$\pm$1.31 | 54.47$\pm$1.19 | 61.37$\pm$0.68 | 68.52$\pm$1.24 | 74.73$\pm$0.36 | 76.50$\pm$0.63 | 60.22 |
| Moderate-DS | 47.02$\pm$0.66 | 55.60$\pm$1.67 | 62.18$\pm$1.86 | 71.83$\pm$0.78 | 75.66$\pm$0.66 | 76.50$\pm$0.63 | 62.46 |
| Gm Matching | 48.86$\pm$1.02 | 60.15$\pm$0.43 | 66.92$\pm$0.28 | 72.03$\pm$0.38 | 73.71$\pm$0.19 | 76.50$\pm$0.63 | 64.33 |
| 20% Feature Corruption |  |  |  |  |  |  |  |
| Random | 40.99$\pm$1.46 | 50.38$\pm$1.39 | 57.24$\pm$0.65 | 65.21$\pm$1.31 | 71.74$\pm$0.28 | 74.92$\pm$0.88 | 57.11 |
| Herding | 44.42$\pm$0.46 | 53.57$\pm$0.31 | 60.72$\pm$1.78 | 69.09$\pm$1.73 | 73.08$\pm$0.98 | 74.92$\pm$0.88 | 60.18 |
| Forgetting | 26.39$\pm$0.17 | 40.78$\pm$2.02 | 49.95$\pm$2.31 | 65.71$\pm$1.12 | 73.67$\pm$1.12 | 74.92$\pm$0.88 | 51.30 |
| GraNd-score | 36.33$\pm$2.66 | 46.21$\pm$1.48 | 55.51$\pm$0.76 | 64.59$\pm$2.40 | 70.14$\pm$1.36 | 74.92$\pm$0.88 | 54.56 |
| EL2N-score | 21.64$\pm$2.03 | 23.78$\pm$1.66 | 35.71$\pm$1.17 | 56.32$\pm$0.86 | 69.66$\pm$0.43 | 74.92$\pm$0.88 | 41.42 |
| Optimization-based | 33.42$\pm$1.60 | 45.37$\pm$2.81 | 54.06$\pm$1.74 | 65.19$\pm$1.27 | 70.06$\pm$0.83 | 74.92$\pm$0.88 | 54.42 |
| Self-sup.-selection | 42.61$\pm$2.44 | 54.04$\pm$1.90 | 59.51$\pm$1.22 | 68.97$\pm$0.96 | 72.33$\pm$0.20 | 74.92$\pm$0.88 | 60.01 |
| Moderate-DS | 42.98$\pm$0.87 | 55.80$\pm$0.95 | 61.84$\pm$1.96 | 70.05$\pm$1.29 | 73.67$\pm$0.30 | 74.92$\pm$0.88 | 60.87 |
| Gm Matching | 47.12$\pm$0.64 | 59.17$\pm$0.92 | 63.45$\pm$0.34 | 71.70$\pm$0.60 | 74.60$\pm$1.03 | 74.92$\pm$0.88 | 63.21 |

**Table 3: Image Corruption ( Tiny ImageNet ): Comparing (Test Accuracy) pruning methods under feature (image) corruption. ResNet-50 is used both as proxy and for downstream classification.**
| Tiny ImageNet |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 40% | 60% | 80% | 100% | Mean $\uparrow$ |
| No Corruption |  |  |  |  |  |  |  |
| Random | 24.02$\pm$0.41 | 29.79$\pm$0.27 | 34.41$\pm$0.46 | 40.96$\pm$0.47 | 45.74$\pm$0.61 | 49.36$\pm$0.25 | 34.98 |
| Herding | 24.09$\pm$0.45 | 29.39$\pm$0.53 | 34.13$\pm$0.37 | 40.86$\pm$0.61 | 45.45$\pm$0.33 | 49.36$\pm$0.25 | 34.78 |
| Forgetting | 22.37$\pm$0.71 | 28.67$\pm$0.54 | 33.64$\pm$0.32 | 41.14$\pm$0.43 | 46.77$\pm$0.31 | 49.36$\pm$0.25 | 34.52 |
| GraNd-score | 23.56$\pm$0.52 | 29.66$\pm$0.37 | 34.33$\pm$0.50 | 40.77$\pm$0.42 | 45.96$\pm$0.56 | 49.36$\pm$0.25 | 34.86 |
| EL2N-score | 19.74$\pm$0.26 | 26.58$\pm$0.40 | 31.93$\pm$0.28 | 39.12$\pm$0.46 | 45.32$\pm$0.27 | 49.36$\pm$0.25 | 32.54 |
| Optimization-based | 13.88$\pm$2.17 | 23.75$\pm$1.62 | 29.77$\pm$0.94 | 37.05$\pm$2.81 | 43.76$\pm$1.50 | 49.36$\pm$0.25 | 29.64 |
| Self-sup.-selection | 20.89$\pm$0.42 | 27.66$\pm$0.50 | 32.50$\pm$0.30 | 39.64$\pm$0.39 | 44.94$\pm$0.34 | 49.36$\pm$0.25 | 33.13 |
| Moderate-DS | 25.29$\pm$0.38 | 30.57$\pm$0.20 | 34.81$\pm$0.51 | 41.45$\pm$0.44 | 46.06$\pm$0.33 | 49.36$\pm$0.25 | 35.64 |
| Gm Matching | 27.88$\pm$0.19 | 33.15$\pm$0.26 | 36.92$\pm$0.40 | 42.48$\pm$0.12 | 46.75$\pm$0.51 | 49.36$\pm$0.25 | 37.44 |
| 5% Feature Corruption |  |  |  |  |  |  |  |
| Random | 23.51$\pm$0.22 | 28.82$\pm$0.72 | 32.61$\pm$0.68 | 39.77$\pm$0.35 | 44.37$\pm$0.34 | 49.02$\pm$0.35 | 33.82 |
| Herding | 23.09$\pm$0.53 | 28.67$\pm$0.37 | 33.09$\pm$0.32 | 39.71$\pm$0.31 | 45.04$\pm$0.15 | 49.02$\pm$0.35 | 33.92 |
| Forgetting | 21.36$\pm$0.28 | 27.72$\pm$0.43 | 33.45$\pm$0.21 | 40.92$\pm$0.45 | 45.99$\pm$0.51 | 49.02$\pm$0.35 | 33.89 |
| GraNd-score | 22.47$\pm$0.23 | 28.85$\pm$0.83 | 33.81$\pm$0.24 | 40.40$\pm$0.15 | 44.86$\pm$0.49 | 49.02$\pm$0.35 | 34.08 |
| EL2N-score | 18.98$\pm$0.72 | 25.96$\pm$0.28 | 31.07$\pm$0.63 | 38.65$\pm$0.36 | 44.21$\pm$0.68 | 49.02$\pm$0.35 | 31.77 |
| Optimization-based | 13.65$\pm$1.26 | 24.02$\pm$1.35 | 29.65$\pm$1.86 | 36.55$\pm$1.84 | 43.64$\pm$0.71 | 49.02$\pm$0.35 | 29.50 |
| Self-sup.-selection | 19.35$\pm$0.57 | 26.11$\pm$0.31 | 31.90$\pm$0.37 | 38.91$\pm$0.29 | 44.43$\pm$0.42 | 49.02$\pm$0.35 | 32.14 |
| Moderate-DS | 24.63$\pm$0.78 | 30.27$\pm$0.16 | 34.84$\pm$0.24 | 40.86$\pm$0.42 | 45.60$\pm$0.31 | 49.02$\pm$0.35 | 35.24 |
| Gm Matching | 27.46$\pm$1.22 | 33.14$\pm$0.61 | 35.76$\pm$1.14 | 41.62$\pm$0.71 | 46.83$\pm$0.56 | 49.02$\pm$0.35 | 36.96 |
| 10% Feature Corruption |  |  |  |  |  |  |  |
| Random | 22.67$\pm$0.27 | 28.67$\pm$0.52 | 31.88$\pm$0.30 | 38.63$\pm$0.36 | 43.46$\pm$0.20 | 48.40$\pm$0.32 | 33.06 |
| Herding | 22.01$\pm$0.18 | 27.82$\pm$0.11 | 31.82$\pm$0.26 | 39.37$\pm$0.18 | 44.18$\pm$0.27 | 48.40$\pm$0.32 | 33.04 |
| Forgetting | 20.06$\pm$0.48 | 27.17$\pm$0.36 | 32.31$\pm$0.22 | 40.19$\pm$0.29 | 45.51$\pm$0.48 | 48.40$\pm$0.32 | 33.05 |
| GraNd-score | 21.52$\pm$0.48 | 26.98$\pm$0.43 | 32.70$\pm$0.19 | 40.03$\pm$0.26 | 44.87$\pm$0.35 | 48.40$\pm$0.32 | 33.22 |
| EL2N-score | 18.59$\pm$0.13 | 25.23$\pm$0.18 | 30.37$\pm$0.22 | 38.44$\pm$0.32 | 44.32$\pm$1.07 | 48.40$\pm$0.32 | 31.39 |
| Optimization-based | 14.05$\pm$1.74 | 29.18$\pm$1.77 | 29.12$\pm$0.61 | 36.28$\pm$1.88 | 43.52$\pm$0.31 | 48.40$\pm$0.32 | 29.03 |
| Self-sup.-selection | 19.47$\pm$0.26 | 26.51$\pm$0.55 | 31.78$\pm$0.14 | 38.87$\pm$0.54 | 44.69$\pm$0.29 | 48.40$\pm$0.32 | 32.26 |
| Moderate-DS | 23.79$\pm$0.16 | 29.56$\pm$0.16 | 34.60$\pm$0.12 | 40.36$\pm$0.27 | 45.10$\pm$0.23 | 48.40$\pm$0.32 | 34.68 |
| Gm Matching | 27.41$\pm$0.23 | 32.84$\pm$0.98 | 36.27$\pm$0.68 | 41.85$\pm$0.29 | 46.35$\pm$0.44 | 48.40$\pm$0.32 | 36.94 |
| 20% Feature Corruption |  |  |  |  |  |  |  |
| Random | 19.99$\pm$0.42 | 25.93$\pm$0.53 | 30.83$\pm$0.44 | 37.98$\pm$0.31 | 42.96$\pm$0.62 | 46.68$\pm$0.43 | 31.54 |
| Herding | 19.46$\pm$0.14 | 24.47$\pm$0.33 | 29.72$\pm$0.39 | 37.50$\pm$0.59 | 42.28$\pm$0.30 | 46.68$\pm$0.43 | 30.86 |
| Forgetting | 18.47$\pm$0.46 | 25.53$\pm$0.23 | 31.17$\pm$0.24 | 39.35$\pm$0.44 | 44.55$\pm$0.67 | 46.68$\pm$0.43 | 31.81 |
| GraNd-score | 20.07$\pm$0.49 | 26.68$\pm$0.40 | 31.25$\pm$0.40 | 38.21$\pm$0.49 | 42.84$\pm$0.72 | 46.68$\pm$0.43 | 30.53 |
| EL2N-score | 18.57$\pm$0.30 | 24.42$\pm$0.44 | 30.04$\pm$0.15 | 37.62$\pm$0.44 | 42.43$\pm$0.61 | 46.68$\pm$0.43 | 30.53 |
| Optimization-based | 13.71$\pm$0.26 | 23.33$\pm$1.84 | 29.15$\pm$2.84 | 36.12$\pm$1.86 | 42.94$\pm$0.52 | 46.88$\pm$0.43 | 29.06 |
| Self-sup.-selection | 20.22$\pm$0.23 | 26.90$\pm$0.50 | 31.93$\pm$0.49 | 39.74$\pm$0.52 | 44.27$\pm$0.10 | 46.68$\pm$0.43 | 32.61 |
| Moderate-DS | 23.27$\pm$0.33 | 29.06$\pm$0.36 | 33.48$\pm$0.11 | 40.07$\pm$0.36 | 44.73$\pm$0.39 | 46.68$\pm$0.43 | 34.12 |
| Gm Matching | 27.19$\pm$0.92 | 31.70$\pm$0.78 | 35.14$\pm$0.19 | 42.04$\pm$0.31 | 45.12$\pm$0.28 | 46.68$\pm$0.43 | 36.24 |

### 5.3 Corruption Scenarios

To understand the performance of data pruning strategies in presence of corruption, we experiment with three different sources of corruption – image corruption, label noise and adversarial attacks.

#### 5.3.1 Robustness to Image Corruption

In this set of experiments, we investigate the robustness of data pruning strategies when the input images are corrupted – a popular robustness setting, often encountered when training models on real-world data (Hendrycks and Dietterich,, ; Szegedy et al.,, ).
To corrupt images, we apply five types of realistic noise: Gaussian noise, random occlusion, resolution reduction, fog, and motion blur to parts of the corrupt samples i.e. to say if $m$ samples are corrupted, each type of noise is added to one a random $m/5$ of them, while the other partitions are corrupted with a different noise. The results are presented in Table 2, 3. We observe that Gm Matching outperforms all the baselines across all pruning rates improving $\approx$3% across both datasets on an average. We note that, the gains are more consistent and profound in this setting over the clean setting. Additionally, similar to our prior observations in the clean setting, the gains of Gm Matching are more significant at high pruning rates (i.e. low selection ratio).

**Table 4: Robustness to Label Noise: Comparing (Test Accuracy) pruning methods on CIFAR-100 and TinyImageNet datasets, under 20% and 35% Symmetric Label Corruption, at 20% and 30% selection ratio. ResNet-50 is used both as proxy and for downstream classification.**
|  | CIFAR-100 (Label noise) | Tiny ImageNet (Label noise) |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 20% | 30% | Mean $\uparrow$ |
| 20% Label Noise |  |  |  |  |  |
| Random | 34.47$\pm$0.64 | 43.26$\pm$1.21 | 17.78$\pm$0.44 | 23.88$\pm$0.42 | 29.85 |
| Herding | 42.29$\pm$1.75 | 50.52$\pm$3.38 | 18.98$\pm$0.44 | 24.23$\pm$0.29 | 34.01 |
| Forgetting | 36.53$\pm$1.11 | 45.78$\pm$1.04 | 13.20$\pm$0.38 | 21.79$\pm$0.43 | 29.33 |
| GraNd-score | 31.72$\pm$0.67 | 42.80$\pm$0.30 | 18.28$\pm$0.32 | 23.72$\pm$0.18 | 28.05 |
| EL2N-score | 29.82$\pm$1.19 | 33.62$\pm$2.35 | 13.93$\pm$0.69 | 18.57$\pm$0.31 | 23.99 |
| Optimization-based | 32.79$\pm$0.62 | 41.80$\pm$1.14 | 14.77$\pm$0.95 | 22.52$\pm$0.77 | 27.57 |
| Self-sup.-selection | 31.08$\pm$0.78 | 41.87$\pm$0.63 | 15.10$\pm$0.73 | 21.01$\pm$0.36 | 27.27 |
| Moderate-DS | 40.25$\pm$0.12 | 48.53$\pm$1.60 | 19.64$\pm$0.40 | 24.96$\pm$0.30 | 31.33 |
| Gm Matching | 52.64$\pm$0.72 | 61.01$\pm$0.47 | 25.80$\pm$0.37 | 31.71$\pm$0.24 | 42.79 |
| 35% Label Noise |  |  |  |  |  |
| Random | 24.51$\pm$1.34 | 32.26$\pm$0.81 | 14.64$\pm$0.29 | 19.41$\pm$0.45 | 22.71 |
| Herding | 29.42$\pm$1.54 | 37.50$\pm$2.12 | 15.14$\pm$0.45 | 20.19$\pm$0.45 | 25.56 |
| Forgetting | 29.48$\pm$1.98 | 38.01$\pm$2.21 | 11.25$\pm$0.90 | 17.07$\pm$0.66 | 23.14 |
| GraNd-score | 23.03$\pm$1.05 | 34.83$\pm$2.01 | 13.68$\pm$0.46 | 19.51$\pm$0.45 | 22.76 |
| EL2N-score | 21.95$\pm$1.08 | 31.63$\pm$2.84 | 10.11$\pm$0.25 | 13.69$\pm$0.32 | 19.39 |
| Optimization-based | 26.77$\pm$0.15 | 35.63$\pm$0.92 | 12.37$\pm$0.68 | 18.52$\pm$0.90 | 23.32 |
| Self-sup.-selection | 23.12$\pm$1.47 | 34.85$\pm$0.68 | 11.23$\pm$0.32 | 17.76$\pm$0.69 | 22.64 |
| Moderate-DS | 28.45$\pm$0.53 | 36.55$\pm$1.26 | 15.27$\pm$0.31 | 20.33$\pm$0.28 | 25.15 |
| Gm Matching | 43.33$\pm$ 1.02 | 58.41$\pm$ 0.68 | 23.14$\pm$ 0.92 | 27.76$\pm$ 0.40 | 38.16 |

**Table 5: Pruning with Label Noise (TinyImageNet): Comparing (Test Accuracy) pruning methods under 20% Symmetric Label Corruption across wide array of selection ratio. ResNet-50 is used both as proxy and for downstream classification.**
| Tiny ImageNet (Label Noise) |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 40% | 60% | 80% | 100% | Mean $\uparrow$ |
| Random | 17.78$\pm$0.44 | 23.88$\pm$0.42 | 27.97$\pm$0.39 | 34.88$\pm$0.51 | 38.47$\pm$0.40 | 44.42$\pm$0.47 | 28.60 |
| Herding | 18.98$\pm$0.44 | 24.23$\pm$0.29 | 27.28$\pm$0.31 | 34.36$\pm$0.29 | 39.00$\pm$0.49 | 44.42$\pm$0.47 | 28.87 |
| Forgetting | 13.20$\pm$0.38 | 21.79$\pm$0.43 | 27.89$\pm$0.22 | 36.03$\pm$0.24 | 40.60$\pm$0.31 | 44.42$\pm$0.47 | 27.50 |
| GraNd-score | 18.28$\pm$0.32 | 23.72$\pm$0.18 | 27.34$\pm$0.33 | 34.91$\pm$0.19 | 39.45$\pm$0.45 | 44.42$\pm$0.47 | 28.34 |
| EL2N-score | 13.93$\pm$0.69 | 18.57$\pm$0.31 | 24.56$\pm$0.34 | 32.14$\pm$0.49 | 37.64$\pm$0.41 | 44.42$\pm$0.47 | 25.37 |
| Optimization-based | 14.77$\pm$0.95 | 22.52$\pm$0.77 | 25.62$\pm$0.90 | 34.18$\pm$0.79 | 38.49$\pm$0.69 | 44.42$\pm$0.47 | 27.12 |
| Self-sup.-selection | 15.10$\pm$0.73 | 21.01$\pm$0.36 | 26.62$\pm$0.22 | 33.93$\pm$0.36 | 39.22$\pm$0.12 | 44.42$\pm$0.47 | 27.18 |
| Moderate-DS | 19.64$\pm$0.40 | 24.96$\pm$0.30 | 29.56$\pm$0.21 | 35.79$\pm$0.36 | 39.93$\pm$0.23 | 44.42$\pm$0.47 | 30.18 |
| Gm Matching | 25.80$\pm$0.37 | 31.71$\pm$0.24 | 34.87$\pm$0.21 | 39.76$\pm$0.71 | 41.94$\pm$0.23 | 44.42$\pm$0.47 | 34.82 |

#### 5.3.2 Robustness to Label Corruption

Next, we consider another important corruption scenario where a fraction of the training examples are mislabeled. Since acquiring manually labeled data is often impractical and data in the wild always contains noisy annotations – it is important to ensure the pruning method is robust to label noise. We conduct experiments with synthetically injected symmetric label noise (Li et al.,, ; Patrini et al.,, ; Xia et al.,, ). The results are summarized in Table 4,5. Encouragingly, Gm Matching outperforms the baselines by $\approx$ 12%. Since, mislabeled samples come from different class - they are spatially quite dissimilar than the correctly labeled ones thus, less likely to be picked by Gm matching, explaining the superior performance.

**Table 6: Robustness to Adversarial Attacks. Comparing (Test Accuracy) pruning methods under PGD and GS attacks. ResNet-50 is used both as proxy and for downstream classification.**
|  | CIFAR-100 (PGD Attack) | CIFAR-100 (GS Attack) |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 20% | 30% | Mean $\uparrow$ |
| Random | 43.23$\pm$0.31 | 52.86$\pm$0.34 | 44.23$\pm$0.41 | 53.44$\pm$0.44 | 48.44 |
| Herding | 40.21$\pm$0.72 | 49.62$\pm$0.65 | 39.92$\pm$1.03 | 50.14$\pm$0.15 | 44.97 |
| Forgetting | 35.90$\pm$1.30 | 47.37$\pm$0.99 | 37.55$\pm$0.53 | 46.88$\pm$1.91 | 41.93 |
| GraNd-score | 40.87$\pm$0.84 | 50.13$\pm$0.30 | 40.77$\pm$1.11 | 49.88$\pm$0.83 | 45.41 |
| EL2N-score | 26.61$\pm$0.58 | 34.50$\pm$1.02 | 26.72$\pm$0.66 | 35.55$\pm$1.30 | 30.85 |
| Optimization-based | 38.29$\pm$1.77 | 46.25$\pm$1.82 | 41.36$\pm$0.92 | 49.10$\pm$0.81 | 43.75 |
| Self-sup.-selection | 40.53$\pm$1.15 | 49.95$\pm$0.50 | 40.74$\pm$1.66 | 51.23$\pm$0.25 | 45.61 |
| Moderate-DS | 43.60$\pm$0.97 | 51.66$\pm$0.39 | 44.69$\pm$0.68 | 53.71$\pm$0.37 | 48.42 |
| Gm Matching | 45.41 $\pm$0.86 | 51.80 $\pm$1.01 | 49.78 $\pm$0.27 | 55.50 $\pm$0.31 | 50.62 |
|  | Tiny ImageNet (PGD Attack) | Tiny ImageNet (GS Attack) |  |  |  |
| Method / Ratio | 20% | 30% | 20% | 30% | Mean $\uparrow$ |
| Random | 20.93$\pm$0.30 | 26.60$\pm$0.98 | 22.43$\pm$0.31 | 26.89$\pm$0.31 | 24.21 |
| Herding | 21.61$\pm$0.36 | 25.95$\pm$0.19 | 23.04$\pm$0.28 | 27.39$\pm$0.14 | 24.50 |
| Forgetting | 20.38$\pm$0.47 | 26.12$\pm$0.19 | 22.06$\pm$0.31 | 27.21$\pm$0.21 | 23.94 |
| GraNd-score | 20.76$\pm$0.21 | 26.34$\pm$0.32 | 22.56$\pm$0.30 | 27.52$\pm$0.40 | 24.30 |
| EL2N-score | 16.67$\pm$0.62 | 22.36$\pm$0.42 | 19.93$\pm$0.57 | 24.65$\pm$0.32 | 20.93 |
| Optimization-based | 19.26$\pm$0.77 | 24.55$\pm$0.92 | 21.26$\pm$0.24 | 25.88$\pm$0.37 | 22.74 |
| Self-sup.-selection | 19.23$\pm$0.46 | 23.92$\pm$0.51 | 19.70$\pm$0.20 | 24.73$\pm$0.39 | 21.90 |
| Moderate-DS | 21.81$\pm$0.37 | 27.11$\pm$0.20 | 23.20$\pm$0.13 | 28.89$\pm$0.27 | 25.25 |
| Gm Matching | 25.98 $\pm$1.12 | 30.77 $\pm$0.25 | 29.71 $\pm$0.45 | 32.88 $\pm$0.73 | 29.84 |

Figure: (a) No Corruption
Refer to caption: x1.png

Figure: (a) No Corruption
Refer to caption: extracted/5689101/plots/CIFAR10-LP-Label-Noise/psi=0.png

#### 5.3.3 Robustness to Adversarial Attacks

Finally, we investigate the robustness properties of data pruning strategies in presence of adversarial attacks that add imperceptible but adversarial noise on natural examples (Szegedy et al.,, ; ; Huang et al.,, ). Specifically, we experiment with two popular adversarial attack algorithms – PGD attack (Madry et al.,, ) and GS Attacks (Goodfellow et al.,, ). We employ adversarial attacks on models trained with CIFAR-100 and Tiny-ImageNet to generate adversarial examples. Following this, various methods are applied to these adversarial examples, and the models are retrained on the curated subset of data. The results are summarized in Table 6. Similar to other corruption scenarios, even in this setting, Gm Matching outperforms the baselines $\approx$ and remains effective across different pruning rates yielding $\approx$ 3% average gain over the best performing baseline.

**Table 7: Network Transfer (Clean) : Tiny-ImageNet Model Transfer Results. A ResNet-50 proxy is used to find important samples which are then used to train SENet and EfficientNet.**
|  | ResNet-50→SENet | ResNet-50→EfficientNet-B0 |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 20% | 30% | Mean $\uparrow$ |
| Random | 34.13$\pm$0.71 | 39.57$\pm$0.53 | 32.88$\pm$1.52 | 39.11$\pm$0.94 | 36.42 |
| Herding | 34.86$\pm$0.55 | 38.60$\pm$0.68 | 32.21$\pm$1.54 | 37.53$\pm$0.22 | 35.80 |
| Forgetting | 33.40$\pm$0.64 | 39.79$\pm$0.78 | 31.12$\pm$0.21 | 38.38$\pm$0.65 | 35.67 |
| GraNd-score | 35.12$\pm$0.54 | 41.14$\pm$0.42 | 33.20$\pm$0.67 | 40.02$\pm$0.35 | 37.37 |
| EL2N-score | 31.08$\pm$1.11 | 38.26$\pm$0.45 | 31.34$\pm$0.49 | 36.88$\pm$0.32 | 34.39 |
| Optimization-based | 33.18$\pm$0.52 | 39.42$\pm$0.77 | 32.16$\pm$0.90 | 38.52$\pm$0.50 | 35.82 |
| Self-sup.-selection | 31.74$\pm$0.71 | 38.45$\pm$0.39 | 30.99$\pm$1.03 | 37.96$\pm$0.77 | 34.79 |
| Moderate-DS | 36.04$\pm$0.15 | 41.40$\pm$0.20 | 34.26$\pm$0.48 | 39.57$\pm$0.29 | 37.82 |
| Gm Matching | 37.93$\pm$0.23 | 42.59$\pm$0.29 | 36.31$\pm$0.67 | 41.03$\pm$0.41 | 39.47 |

**Table 8: Network Transfer : A ResNet-50 proxy (pretrained on TinyImageNet) is used to find important samples from Tiny-ImageNet; which is then used to train a VGGNet-16 and ShuffleNet. We repeat the experiment across multiple corruption settings - clean; 20% Feature / Label Corruption and PGD attack when 20% and 30% samples are selected.**
|  | ResNet-50→ VGG-16 | ResNet-50→ ShuffleNet |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Method / Ratio | 20% | 30% | 20% | 30% | Mean $\uparrow$ |
| No Corruption |  |  |  |  |  |
| Random | 29.63$\pm$0.43 | 35.38$\pm$0.83 | 32.40$\pm$1.06 | 39.13$\pm$0.81 | 34.96 |
| Herding | 31.05$\pm$0.22 | 36.27$\pm$0.57 | 33.10$\pm$0.39 | 38.65$\pm$0.22 | 35.06 |
| Forgetting | 27.53$\pm$0.36 | 35.61$\pm$0.39 | 27.82$\pm$0.56 | 36.26$\pm$0.51 | 32.35 |
| GraNd-score | 29.93$\pm$0.95 | 35.61$\pm$0.39 | 29.56$\pm$0.46 | 37.40$\pm$0.38 | 33.34 |
| EL2N-score | 26.47$\pm$0.31 | 33.19$\pm$0.51 | 28.18$\pm$0.27 | 35.81$\pm$0.29 | 31.13 |
| Optimization-based | 25.92$\pm$0.64 | 34.82$\pm$1.29 | 31.37$\pm$1.14 | 38.22$\pm$0.78 | 32.55 |
| Self-sup.-selection | 25.16$\pm$1.10 | 33.30$\pm$0.94 | 29.47$\pm$0.56 | 36.68$\pm$0.36 | 31.45 |
| Moderate-DS | 31.45$\pm$0.32 | 37.89$\pm$0.36 | 33.32$\pm$0.41 | 39.68$\pm$0.34 | 35.62 |
| Gm Matching | 35.86$\pm$0.41 | 40.56$\pm$0.22 | 35.51$\pm$0.32 | 40.30$\pm$0.58 | 38.47 |
| 20% Label Corruption |  |  |  |  |  |
| Random | 23.29$\pm$1.12 | 28.18$\pm$1.84 | 25.08$\pm$1.32 | 31.44$\pm$1.21 | 27.00 |
| Herding | 23.99$\pm$0.36 | 28.57$\pm$0.40 | 26.25$\pm$0.47 | 30.73$\pm$0.28 | 27.39 |
| Forgetting | 14.52$\pm$0.66 | 21.75$\pm$0.23 | 15.70$\pm$0.29 | 22.31$\pm$0.35 | 18.57 |
| GraNd-score | 22.44$\pm$0.46 | 27.95$\pm$0.29 | 23.64$\pm$0.10 | 30.85$\pm$0.21 | 26.22 |
| EL2N-score | 15.15$\pm$1.25 | 23.36$\pm$0.30 | 18.01$\pm$0.44 | 24.68$\pm$0.34 | 20.30 |
| Optimization-based | 22.93$\pm$0.58 | 24.92$\pm$2.50 | 25.82$\pm$1.70 | 30.19$\pm$0.48 | 25.97 |
| Self-sup.-selection | 18.39$\pm$1.30 | 25.77$\pm$0.87 | 22.87$\pm$0.54 | 29.80$\pm$0.36 | 24.21 |
| Moderate-DS | 23.68$\pm$0.19 | 28.93$\pm$0.19 | 28.82$\pm$0.33 | 32.39$\pm$0.21 | 28.46 |
| Gm Matching | 28.77$\pm$0.77 | 34.87$\pm$0.23 | 32.05$\pm$0.93 | 37.43$\pm$0.25 | 33.28 |
| 20% Feature Corruption |  |  |  |  |  |
| Random | 26.33$\pm$0.88 | 31.57$\pm$1.31 | 29.15$\pm$0.83 | 34.72$\pm$1.00 | 30.44 |
| Herding | 18.03$\pm$0.33 | 25.77$\pm$0.34 | 23.33$\pm$0.43 | 31.73$\pm$0.38 | 24.72 |
| Forgetting | 19.41$\pm$0.57 | 28.35$\pm$0.16 | 18.44$\pm$0.57 | 31.09$\pm$0.61 | 24.32 |
| GraNd-score | 23.59$\pm$0.19 | 30.69$\pm$0.13 | 23.15$\pm$0.56 | 31.58$\pm$0.95 | 27.25 |
| EL2N-score | 24.60$\pm$0.81 | 31.49$\pm$0.33 | 26.62$\pm$0.34 | 33.91$\pm$0.56 | 29.16 |
| Optimization-based | 25.12$\pm$0.34 | 30.52$\pm$0.89 | 28.87$\pm$1.25 | 34.08$\pm$1.92 | 29.65 |
| Self-sup.-selection | 26.33$\pm$0.21 | 33.23$\pm$0.26 | 26.48$\pm$0.37 | 33.54$\pm$0.46 | 29.90 |
| Moderate-DS | 29.65$\pm$0.68 | 35.89$\pm$0.53 | 32.30$\pm$0.38 | 38.66$\pm$0.29 | 34.13 |
| Gm Matching | 33.45$\pm$1.02 | 39.46$\pm$0.44 | 35.14$\pm$0.21 | 39.89$\pm$0.98 | 36.99 |
| PGD Attack |  |  |  |  |  |
| Random | 26.12$\pm$1.09 | 31.98$\pm$0.78 | 28.28$\pm$0.90 | 34.59$\pm$1.18 | 30.24 |
| Herding | 26.76$\pm$0.59 | 32.56$\pm$0.35 | 28.87$\pm$0.48 | 35.43$\pm$0.22 | 30.91 |
| Forgetting | 24.55$\pm$0.57 | 31.83$\pm$0.36 | 23.32$\pm$0.37 | 31.82$\pm$0.15 | 27.88 |
| GraNd-score | 25.19$\pm$0.33 | 31.46$\pm$0.54 | 26.03$\pm$0.66 | 33.22$\pm$0.24 | 28.98 |
| EL2N-score | 21.73$\pm$0.47 | 27.66$\pm$0.32 | 22.66$\pm$0.35 | 29.89$\pm$0.64 | 25.49 |
| Optimization-based | 26.02$\pm$0.36 | 31.64$\pm$1.75 | 27.93$\pm$0.47 | 34.82$\pm$0.96 | 30.10 |
| Self-sup.-selection | 22.36$\pm$0.30 | 28.56$\pm$0.50 | 25.35$\pm$0.27 | 32.57$\pm$0.13 | 27.21 |
| Moderate-DS | 27.24$\pm$0.36 | 32.90$\pm$0.31 | 29.06$\pm$0.28 | 35.89$\pm$0.53 | 31.27 |
| Gm Matching | 27.96$\pm$1.60 | 35.76$\pm$0.82 | 34.11$\pm$0.65 | 40.91$\pm$0.84 | 34.69 |

### 5.4 Generalization to Unseen Network / Domain

One crucial component of data pruning is the proxy network. Since, the input features (e.g. images) often reside on a non-separable manifold, data pruning strategies rely on a proxy model to map the samples into a separable manifold (embedding space), wherein the data pruning strategies can now assign importance scores. However, it is important for the data pruning strategies to be robust to architecture changes i.e. to say that samples selected via a proxy network should generalize well when trained on unseen (during sample selection) networks / domains. We perform experiments on two such scenarios:

A. Network Transfer: In this setting, the proxy model is trained on the target dataset (no distribution shift). However, the proxy architecture is different than the downstream network. In Table 7, we use a ResNet-50 proxy trained on MiniImageNet to sample the data. However, then we train a downstram SENet and EfficientNet-B0 on the sampled data. In Table 8, we use a ResNet-50 pretrained on Mini ImageNet as proxy, whereas we train a VGG-16 and ShuffleNet over the selected samples.

B. Domain Transfer: Next, we consider the setting where the proxy shares the same architecture with the downstream model. However, the proxy used to select the samples is pretrained on a different dataset (distribution shift) than target dataset. In Figure 6 we use a proxy ResNet-18 pretrained on ImageNet to select samples from CIFAT-10. The selected samples are used to train a subsequent ResNet-18. In Figure 7, we additionally freeze the pretrained encoder i.e. we use ResNet-18 encoder pretrained on ImageNet as proxy. Further, we freeze the encoder and train a downstream linear classifier on top over CIFAR-10 (linear probe).

## 6 Conclusion

In this work, we formalized and studied the problem of robust data pruning. We show that existing data pruning strategies suffer significant degradation in performance in presence of corruption. Orthogonal to existing works, we propose Gm Matching where our goal is to find a $k$-subset from the noisy data such that the mean of the subset approximates the Gm of the noisy dataset. We solve this meta problem using a herding style greedy approach. We theoretically justify our approach and empirically show its efficacy by comparing Gm Matching against several popular benchmarks across multiple datasets. Our results indicate that Gm Matching consistently outperforms existing pruning strategies in both clean and noisy settings. While in this work we have only explored greedy herding style approach, it is possible to investigate other combinatorial approaches to solve the meta problem. Further, while we only studied the problem under gross corruption framework, it remains open to improve the results by incorporating certain structural assumptions.

## 7 Appendix

### 7.1 Notations and Abbreviations

| $\displaystyle a$ | A scalar (integer or real) |
| --- | --- |
| $\displaystyle{\mathbf{a}}$ | A vector |
| $\displaystyle{\mathbf{A}}$ | A matrix |
| a | A scalar random variable |
| $\displaystyle{\mathbf{a}}$ | A vector-valued random variable |
| $\displaystyle{\mathbb{A}},{\mathcal{A}}$ | A set |
| $\displaystyle[a,b]$ | The real interval including $a$ and $b$ |
| $\displaystyle{\mathbb{A}}\backslash{\mathbb{B}}$ | Set subtraction, i.e., the set containing the elements of ${\mathbb{A}}$ that are not in ${\mathbb{B}}$ |
| $\displaystyle{\textnormal{a}}_{i}$ | Element $i$ of the random vector ${\mathbf{a}}$ |
| $\displaystyle P({\textnormal{a}})$ | A probability distribution over a discrete variable |
| $\displaystyle p({\textnormal{a}})$ | A probability distribution over a continuous variable, or over<br>a variable whose type has not been specified |
| $\displaystyle f:{\mathbb{A}}\rightarrow{\mathbb{B}}$ | The function $f$ with domain ${\mathbb{A}}$ and range ${\mathbb{B}}$ |
| $\displaystyle f\circ g$ | Composition of the functions $f$ and $g$ |
| $\displaystyle f({\mathbf{x}};{\mathbf{\theta}})$ | A function of ${\mathbf{x}}$ parametrized by ${\mathbf{\theta}}$.<br>(Sometimes we write $f({\mathbf{x}})$ and omit the argument ${\mathbf{\theta}}$ to lighten notation) |
| $\displaystyle||{\mathbf{x}}||_{p}$ | $L^{p}$ norm of ${\mathbf{x}}$ |
| $\displaystyle\mathbf{1}(condition)$ | is 1 if the condition is true, 0 otherwise |
| Gm Matching | Geometric Median Matching |

### 7.2 Proof of Lemma 1

###### Proof.

The original importance score without the corrupted sample is:

$$ $\displaystyle d({\mathbf{x}}_{i},y_{i})=\|{\mathbf{x}}_{i}-\mu_{y}^{\mathcal{G }}\|^{2}_{2}$ (12) $$

The importance score with the corrupted sample affecting the centroid is:

$$ $\displaystyle d^{\prime}({\mathbf{x}}_{i},y_{i})=\|{\mathbf{x}}_{i}-\mu_{y}^{ \mathcal{B}}\|^{2}_{2}$ (13) $$

We can calculate the deviation as:

$$ $\displaystyle\Delta d({\mathbf{x}}_{i},y_{i})$ $\displaystyle=d({\mathbf{x}}_{i},y_{i})-d^{\prime}({\mathbf{x}}_{i},y_{i})$ $\displaystyle=\bigg{(}{\mathbf{x}}_{i}-\mu_{y}^{\mathcal{B}}\bigg{)}^{T}\bigg{ (}{\mathbf{x}}_{i}-\mu_{y}^{\mathcal{B}}\bigg{)}-\bigg{(}{\mathbf{x}}_{i}-\mu_ {y}^{\mathcal{G}}\bigg{)}^{T}\bigg{(}{\mathbf{x}}_{i}-\mu_{y}^{\mathcal{G}} \bigg{)}$ $$

The result follows by expanding and defining $\Delta\mu_{y}=\mu_{y}^{\mathcal{B}}-\mu_{y}^{\mathcal{G}}$
∎

###### Proof.

### 7.3 Intermediate Lemmas

In order to prove Equation 11, we will first establish the following result which follows from the definition of Gm; see also (Lopuhaa et al.,, ; Minsker et al.,, ; Cohen et al.,, ; Chen et al.,, ; Li et al.,, ; Wu et al.,, ; Acharya et al.,, ) for similar adaptations.

###### Lemma 2 .

Given a set of $\alpha$-corrupted samples ${\mathcal{D}}={\mathcal{D}}_{\mathcal{G}}\cup{\mathcal{D}}_{\mathcal{B}}$ ( Definition 1), and an $\epsilon$-approx. $\textsc{Gm}(\cdot)$ oracle (5), then we have:

$$ $\mathbb{E}\bigg{\|}\bm{\mu}^{\textsc{Gm}}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2} \leq\frac{8|{\mathcal{D}}_{\mathcal{G}}|}{(|{\mathcal{D}}_{\mathcal{G}}|-|{ \mathcal{D}}_{\mathcal{B}}|)^{2}}\sum_{{\mathbf{x}}\in{\mathcal{D}}_{\mathcal{ G}}}\mathbb{E}\bigg{\|}{\mathbf{x}}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2}+\frac{ 2\epsilon^{2}}{(|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}|)^{ 2}}$ (14) $$

where, $\bm{\mu}^{\textsc{Gm}}=\textsc{Gm}(\{{\mathbf{x}}_{i}\in{\mathcal{D}}\})$ is the $\epsilon$-approximate Gm over the entire ($\alpha$-corrupted) dataset; and $\bm{\mu}^{\mathcal{G}}=\frac{1}{|{\mathcal{D}}_{\mathcal{G}}|}\sum_{{\mathbf{x
}}_{i}\in{\mathcal{D}}_{\mathcal{G}}}{\mathbf{x}}_{i}$ denotes the mean of the (underlying) uncorrupted set.

###### Proof.

Note that, by using triangle inequality, we can write:

$$ $\displaystyle\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}}\bigg{\|}\bm{\mu}^{\textsc {Gm}}-{\mathbf{x}}_{i}\bigg{\|}$ $\displaystyle\geq\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{B}}}\bigg{(} \bigg{\|}{\mathbf{x}}_{i}\bigg{\|}-\bigg{\|}\bm{\mu}^{\textsc{Gm}}\bigg{\|} \bigg{)}+\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{G}}}\bigg{(}\bigg{\| }\bm{\mu}^{\textsc{Gm}}\bigg{\|}-\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}\bigg{)}$ $\displaystyle=\bigg{(}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{G}}}- \sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{B}}}\bigg{)}\bigg{\|}\bm{\mu} ^{\textsc{Gm}}\bigg{\|}+\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{B}}} \bigg{\|}{\mathbf{x}}_{i}\bigg{\|}-\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{ \mathcal{G}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}$ $\displaystyle=\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B }}|\bigg{)}\bigg{\|}\bm{\mu}^{\textsc{Gm}}\bigg{\|}+\sum_{{\mathbf{x}}_{i}\in{ \mathcal{D}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}-2\sum_{{\mathbf{x}}_{i}\in{ \mathcal{D}}_{\mathcal{G}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}.$ (15) $$

Now, by definition (6); we have that:

$$ $\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}}\bigg{\|}\bm{\mu}^{\textsc{Gm}}-{ \mathbf{x}}_{i}\bigg{\|}\leq\inf_{{\mathbf{z}}\in{\mathcal{H}}}\sum_{{\mathbf{ x}}_{i}\in{\mathcal{D}}}\bigg{\|}{\mathbf{z}}-{\mathbf{x}}_{i}\bigg{\|}+ \epsilon\leq\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}}\bigg{\|}{\mathbf{x}}_{i} \bigg{\|}+\epsilon$ (16) $$

Combining these two inequalities, we get:

$$ $\displaystyle\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B} }|\bigg{)}\bigg{\|}\bm{\mu}^{\textsc{Gm}}\bigg{\|}\leq\sum_{{\mathbf{x}}_{i} \in{\mathcal{D}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}-\sum_{{\mathbf{x}}_{i}\in{ \mathcal{D}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}+2\sum_{{\mathbf{x}}_{i}\in{ \mathcal{D}}_{\mathcal{G}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}+\epsilon$ (17) $$

This implies:

$$ $\displaystyle\bigg{\|}\bm{\mu}^{\textsc{Gm}}\bigg{\|}\leq\frac{2}{\bigg{(}|{ \mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}|\bigg{)}}\sum_{{ \mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{G}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{ \|}+\frac{\epsilon}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{ \mathcal{B}}|\bigg{)}}$ (18) $$

Squaring both sides,

$$ $\displaystyle\bigg{\|}\bm{\mu}^{\textsc{Gm}}\bigg{\|}^{2}$ $\displaystyle\leq\Bigg{[}\frac{2}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{ \mathcal{D}}_{\mathcal{B}}|\bigg{)}}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{ \mathcal{G}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}+\frac{\epsilon}{\bigg{(}|{ \mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}|\bigg{)}}\Bigg{]}^{2}$ (19) $\displaystyle\leq 2\Bigg{[}\frac{2}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{ \mathcal{D}}_{\mathcal{B}}|\bigg{)}}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{ \mathcal{G}}}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}\Bigg{]}^{2}+2\Bigg{[}\frac{ \epsilon}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}| \bigg{)}}\Bigg{]}^{2}$ (20) $$

Where, the last step is a well-known consequence of triangle inequality and AM-GM inequality.
Taking expectation on both sides, we have:

$$ $\displaystyle\mathbb{E}\bigg{\|}\bm{\mu}^{\textsc{Gm}}\bigg{\|}^{2}$ $\displaystyle\leq\frac{8}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}} _{\mathcal{B}}|\bigg{)}^{2}}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{G }}}\mathbb{E}\bigg{\|}{\mathbf{x}}_{i}\bigg{\|}^{2}+\frac{2\epsilon^{2}}{\bigg {(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}|\bigg{)}^{2}}$ (21) $$

Since, Gm is translation equivariant, we can write:

$$ $\displaystyle\mathbb{E}\bigg{[}\textsc{Gm}\bigg{(}\bigg{\{}{\mathbf{x}}_{i}- \bm{\mu}^{\mathcal{G}}|{\mathbf{x}}_{i}\in{\mathcal{D}}\bigg{\}}\bigg{)}\bigg{ ]}=\mathbb{E}\bigg{[}\textsc{Gm}\bigg{(}\bigg{\{}{\mathbf{x}}_{i}|{\mathbf{x}} _{i}\in{\mathcal{D}}\bigg{\}}\bigg{)}-\bm{\mu}^{\mathcal{G}}\bigg{]}$ (22) $$

Consequently we have that :

$$ $\displaystyle\mathbb{E}\bigg{\|}\bm{\mu}^{\textsc{Gm}}-\bm{\mu}^{\mathcal{G}} \bigg{\|}^{2}$ $\displaystyle\leq\frac{8}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}} _{\mathcal{B}}|\bigg{)}^{2}}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{\mathcal{G }}}\mathbb{E}\bigg{\|}{\mathbf{x}}_{i}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2}+ \frac{2\epsilon^{2}}{\bigg{(}|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{ \mathcal{B}}|\bigg{)}^{2}}$ $$

This concludes the proof.
∎

###### Lemma 2 .

###### Proof.

### 7.4 Proof of Theorem 11

We restate the theorem for convenience:

Theorem 11
Suppose that, we are given, a set of $\alpha$-corrupted samples ${\mathcal{D}}$ (Definition 1), and an $\epsilon$ approx. $\textsc{Gm}(\cdot)$ oracle (5). Then, Gm Matching guarantees that the mean of the selected $k$-subset $\bm{\mu}^{\mathcal{S}}=\frac{1}{k}\sum_{{\mathbf{x}}_{i}\in{\mathcal{D}}_{
\mathcal{S}}}{\mathbf{x}}_{i}$ converges to the neighborhood of $\bm{\mu}^{\mathcal{G}}=\mathbb{E}_{{\mathbf{x}}\in{\mathcal{D}}_{\mathcal{G}}}
({\mathbf{x}})$ at the rate ${\mathcal{O}}(\frac{1}{k})$ such that:

$$ $\mathbb{E}\bigg{\|}\bm{\mu}^{\mathcal{S}}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2} \leq\frac{8|{\mathcal{D}}_{\mathcal{G}}|}{(|{\mathcal{D}}_{\mathcal{G}}|-|{ \mathcal{D}}_{\mathcal{B}}|)^{2}}\sum_{{\mathbf{x}}\in{\mathcal{D}}_{\mathcal{ G}}}\mathbb{E}\bigg{\|}{\mathbf{x}}-\bm{\mu}^{\mathcal{G}}\bigg{\|}^{2}+\frac{ 2\epsilon^{2}}{(|{\mathcal{D}}_{\mathcal{G}}|-|{\mathcal{D}}_{\mathcal{B}}|)^{ 2}}$ (23) $$

###### Proof.

To prove this result, we first show that Gm Matching converges to $\bm{\mu}_{\epsilon}^{\textsc{Gm}}$ at ${\mathcal{O}}(\frac{1}{k})$. It suffices to show that the error $\delta=\bigg{\|}\bm{\mu}^{\textsc{Gm}}_{\epsilon}-\frac{1}{k}\sum_{{\mathbf{x}
}_{i}\in{\mathcal{S}}}{\mathbf{x}}_{i}\bigg{\|}\rightarrow 0$ asymptotically. We will follow the proof technique in (Chen et al.,, ) mutatis mutandis to prove this result.
We also assume that ${\mathcal{D}}$ contains the support of the resulting noisy distribution.

We start by defining a Gm-centered marginal polytope as the convex hull –

$$ $\displaystyle{\mathcal{M}}_{\epsilon}:=\text{conv}\bigg{\{}{\mathbf{x}}-\bm{ \mu}^{\textsc{Gm}}_{\epsilon}\;|{\mathbf{x}}\in{\mathcal{D}}\bigg{\}}$ (24) $$

Then, we can rewrite the update equation (9) as:

$$ $\displaystyle{\mathbf{\theta}}_{t+1}$ $\displaystyle={\mathbf{\theta}}_{t}+\bm{\mu}_{\epsilon}^{\textsc{Gm}}-{\mathbf {x}}_{t+1}$ (25) $\displaystyle={\mathbf{\theta}}_{t}-({\mathbf{x}}_{t+1}-\bm{\mu}_{\epsilon}^{ \textsc{Gm}})$ (26) $\displaystyle={\mathbf{\theta}}_{t}-\bigg{(}\operatorname*{arg\,max}_{{\mathbf {x}}\in{\mathcal{D}}}\langle{\mathbf{\theta}}_{t},{\mathbf{x}}\rangle-\bm{\mu} _{\epsilon}^{\textsc{Gm}}\bigg{)}$ (27) $\displaystyle={\mathbf{\theta}}_{t}-\operatorname*{arg\,max}_{{\mathbf{m}}\in{ \mathcal{M}}_{\epsilon}}\langle{\mathbf{\theta}}_{t},{\mathbf{m}}\rangle$ (28) $\displaystyle={\mathbf{\theta}}_{t}-{\mathbf{m}}_{t}$ (29) $$

Now, squaring both sides we get :

$$ $\displaystyle\|{\mathbf{\theta}}_{t+1}\|^{2}=\|\theta_{t}\|^{2}+\|{\mathbf{m}} _{t}\|^{2}-2\langle{\mathbf{\theta}}_{t},{\mathbf{m}}_{t}\rangle$ (30) $$

rearranging the terms we get:

$$ $\displaystyle\|{\mathbf{\theta}}_{t+1}\|^{2}-\|\theta_{t}\|^{2}$ $\displaystyle=\|{\mathbf{m}}_{t}\|^{2}-2\langle{\mathbf{\theta}}_{t},{\mathbf{ m}}_{t}\rangle$ (31) $\displaystyle=\|{\mathbf{m}}_{t}\|^{2}-2\|{\mathbf{m}}_{t}\|\|{\mathbf{\theta} }_{t}\|\langle\frac{{\mathbf{\theta}}_{t}}{\|{\mathbf{\theta}}_{t}\|},\frac{{ \mathbf{m}}_{t}}{\|{\mathbf{m}}_{t}\|}\rangle$ (32) $\displaystyle=2\|{\mathbf{m}}_{t}\|\bigg{(}\frac{1}{2}\|{\mathbf{m}}_{t}\|-\|{ \mathbf{\theta}}_{t}\|\langle\frac{{\mathbf{\theta}}_{t}}{\|{\mathbf{\theta}}_ {t}\|},\frac{{\mathbf{m}}_{t}}{\|{\mathbf{m}}_{t}\|}\rangle\bigg{)}$ (33) $$

Assume that $\|{\mathbf{x}}_{i}\|\leq r\;\forall{\mathbf{x}}_{i}\in{\mathcal{D}}$. , Then we note that,

$$ $\displaystyle\|{\mathbf{x}}_{i}-\bm{\mu}_{\epsilon}^{\textsc{Gm}}\|$ $\displaystyle\leq\|{\mathbf{x}}_{i}\|+\|\bm{\mu}_{\epsilon}^{\textsc{Gm}}\| \leq 2r$ $$

Plugging this in, we get:

$$ $\displaystyle\|{\mathbf{\theta}}_{t+1}\|^{2}-\|\theta_{t}\|^{2}$ $\displaystyle\leq 2\|{\mathbf{m}}_{t}\|\bigg{(}r-\|{\mathbf{\theta}}_{t}\| \langle\frac{{\mathbf{\theta}}_{t}}{\|{\mathbf{\theta}}_{t}\|},\frac{{\mathbf{ m}}_{t}}{\|{\mathbf{m}}_{t}\|}\rangle\bigg{)}$ (34) $$

Recall that, $\bm{\mu}_{\epsilon}^{\textsc{Gm}}$ is guaranteed to be in the relative interior of
$\text{conv}\{{\mathbf{x}}\;|{\mathbf{x}}\in{\mathcal{D}}\}$ (Lopuhaa et al.,, ; Minsker et al.,, ). Consequently, $\exists\kappa$-ball around $\bm{\mu}_{\epsilon}^{\textsc{Gm}}$ contained inside ${\mathcal{M}}$ and we have $\forall t>0$

$$ $\displaystyle\langle\frac{{\mathbf{\theta}}_{t}}{\|{\mathbf{\theta}}_{t}\|}, \frac{{\mathbf{m}}_{t}}{\|{\mathbf{m}}_{t}\|}\rangle$ $\displaystyle\geq\kappa>0$ (35) $$

This implies, $\forall t>0$

$$ $\displaystyle\|{\mathbf{\theta}}_{t}\|\leq\frac{r}{\kappa}$ (36) $$

Expanding the value of ${\mathbf{\theta}}_{t}$ we have:

$$ $\displaystyle\bigg{\|}{\mathbf{\theta}}_{k}\bigg{\|}=\bigg{\|}{\mathbf{\theta} }_{0}+k\bm{\mu}^{\textsc{Gm}}_{\epsilon}-\sum_{i=1}^{k}{\mathbf{x}}_{k}\bigg{ \|}\leq\frac{r}{\kappa}$ (37) $$

Apply Cauchy Schwartz inequality:

$$ $\displaystyle\bigg{\|}k\bm{\mu}^{\textsc{Gm}}_{\epsilon}-\sum_{i=1}^{k}{ \mathbf{x}}_{k}\bigg{\|}$ $\displaystyle\leq\bigg{\|}{\mathbf{\theta}}_{0}\bigg{\|}+\frac{r}{\kappa}$ (38) $$

normalizing both sides by number of iterations $k$

$$ $\displaystyle\bigg{\|}\bm{\mu}^{\textsc{Gm}}_{\epsilon}-\frac{1}{k}\sum_{i=1}^ {k}{\mathbf{x}}_{k}\bigg{\|}$ $\displaystyle\leq\frac{1}{k}\bigg{(}\bigg{\|}{\mathbf{\theta}}_{0}\bigg{\|}+ \frac{r}{\kappa}\bigg{)}$ (39) $$

Thus, we have that Gm Matching converges to $\bm{\mu}^{\textsc{Gm}}_{\epsilon}$ at the rate ${\mathcal{O}}(\frac{1}{k})$.

Combining this with Lemma 2, completes the proof.
∎

###### Proof.

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: See the weakness part.
soundness: 3
strengths: See the summarization part.
summary: This paper proposed a data pruning method based on geometric median-guided sampling. Moreover, the author presents a solver with a relatively fast convergence rate. The experimental results, to some extent, demonstrate the effectiveness of this method.
weaknesses: 1. It is rather difficult for me to identify the innovative points of the proposed scheme in this paper compared to previous methods. For instance, the Moderate based on Geometric Median is also available in other approaches [1,2]. In the context of research progress, innovation is the key driving force. Without clear differentiating factors, it becomes challenging to justify the novelty and significance of this new scheme within the existing body of knowledge. There should be a distinct advantage or a novel application aspect that sets it apart from what has been done before.

2. The experiments in this paper are highly insufficient. They are still centered around CIFAR and Tiny-ImageNet. I don't believe these experimental scenarios are adequate to prove the effectiveness of the Pruning algorithm, nor can they easily reflect the application value of the algorithm. The real scenarios where data pruning plays a significant role should be in the learning process of VLM and LLM. In the field of data-driven research, the choice of experimental datasets directly impacts the reliability and generalizability of the results. Restricting these relatively small-scale and specific datasets fails to capture the complexity and diversity of real-world applications. To truly evaluate the potential of a Pruning algorithm, it is essential to test it in more relevant and challenging environments such as those encountered in the training of large-scale language and vision models.

3. I have some doubts regarding the theoretical analysis in this paper. Firstly, there is a lack of theoretical analysis of the generalization performance of the Coreset results. Moreover, as far as I know, there isn't necessarily a connection between the so-called **neighborhood of the true mean** targeted by Theorem 1 and the actual final performance. Theorem 1 also lacks some intuitive explanations and valuable inferences. Theoretical analysis provides the foundation for understanding the behavior and potential of an algorithm. The absence of these key elements in the theoretical part raises concerns about the overall validity of the proposed approach. 

[1]. Moderate Coreset: A Universal Method of Data Selection for Real-world Data-efficient Deep Learning. ICLR-2023. 

[2]. Herding Dynamic Weights for Partially Observed Random Field Models. UAI-2029.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. How does the proposed method distinguish between hard samples and noise samples? For instance, in Figure 1, if there are currently no perturbed data points (i.e., the data forms a bimodal distribution with both the red and blue regions representing clean data), GM Matching might only cover the blue region and fail to encompass the red region. The authors claim that existing methods tend to select simpler samples, which can make them susceptible to outliers. However, it seems that GM Matching may not guarantee that the selected data points cover the entire data distribution and could misclassify clean samples (or hard samples) as noise samples, potentially resulting in a biased subset. It might be beneficial for the authors to consider how the method could better address the practical performance of data pruning alongside robustness guarantees.
2. What does "breakdown point" refer to? Is there a formal definition? Additionally, how is the optimal breakdown point of 1/2 achieved? It's better to provide further explanation or mathematical proof .
3. How are the convergence rates $ O(1/k) $ and $ O(1/\sqrt{k}) $ defined and estimated in the paper? I am unsure if these refer to convergence rates, scaling, or some other asymptotic metric. Furthermore, the proposed method is said to have better convergence rates compared to random sampling. Given that $ \mu_\epsilon^{GM} $ needs to be approximated rather than computed directly, shouldn't of the calculation of convergence rates consider the computational process involved in estimating $ \mu_\epsilon^{GM} $?
soundness: 3
strengths: The paper is well written and easy to follow.
summary: This paper presents an efficient and simple algorithm for data pruning in the presence of noise, along with a theoretical guarantee on the estimation error.
weaknesses: 1. Some important references and comparisons are missing, e.g. [1] Robust Data Pruning under Label Noise via Maximizing Re-labeling Accuracy.(NeurIPs 2023), [2] Feature Distribution Matching by Optimal Transport for Effective and Robust Coreset Selection.(AAAI 2024). The reported performance is not SOTA. 
2. The main idea of the paper is to utilize the Geometric Median instead of the empirical mean objective in moment matching. However, as mentioned, both Geometric Median and Moment Matching have been extensively studied in the literature. The novelty is quite limited.
3. Some expressions and notation could be more precise.
   - In Eq. 2 and Eq. 3, are the dimensions of $ x $ and $ \theta_t $ consistent? Is $ x \in \mathbb{R}^d $? Additionally, what does $ x_t $ represent, and is $ x_t \in D_S $?
   - In Eq. 6, what is $ S $? Is it equivalent to $ D_S $?

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 1
questions: 1. The description of the paper is so poor that it seriously affects understanding.
2. The performance presented in the paper is not state-of-the-art, and there is a lack of comparison with the latest methods (e.g. [1-3]).
soundness: 1
strengths: 1. It is very meaningful to solve the problem of data pruning in the noisy label scene.
summary: This paper proposes a data pruning method for noisy labeled datasets, which uses geimetric median matching to find the coreset. This paper first describes the moment matching and then describes the geometric median matching. Experiments are conducted on three datasets CIFAR10, CIFAR100 and Tiny-ImageNet.
weaknesses: 1. The coverage of related work is not enough, which is not consistent with contribution point one.  Many existing works study the robust data pruning in noisy scenarios (e.g. [1]Prune4R4L, [2]FDMat). The performance of these methods is much higher than that of the proposed GM matching.
2. The motivation of the paper is unclear and the difference from baseline (Moderate) is not described. The contribution of the paper is unclear.
3. The paper is poorly written. The description of the formulas lacks rigor, with **nearly all formulas** containing undefined symbols and incorrect descriptions. These issues hinder the overall understanding of the paper. 

    For example, 
    in Eq. 1, (1) ${x_{i}}$  is not distinguished (${x_{i}\in D}$ and ${x_{i}\in D_{S}}$); (2)What does ${X_{i}}$ mean ? Is ${X_{i}}$ a feature or a sample ?

    in Eq.2, what does $<,>$ mean? Why does ${x_{i}\in D}$ become ${x \in D}$ ?
    
    in Eq.3, what does $\theta_{t}$ mean? and what does $\theta_{T}$ mean ? 

    in Eq.4, what does $z$ mean ?

    in Eq.5, what does $\mu^{GM}_{\epsilon}$ mean ?
    
    in Eq.6,  Why does ${x_{i}\in D}$ become ${x_{i} \in S}$ ? What is ${S}$ ?

     **There are various errors in all the following formulas.**




[1] Robust Data Pruning under Label Noise via Maximizing Re-labeling Accuracy.(NeurIPS 2023)

[2] Feature Distribution Matching by Optimal Transport for Effective and Robust Coreset Selection.(AAAI 2024)

[3] Loss-Curvature Matching for Dataset Selection and Condensation.(AISTATS 2023 )

Meta-review: The submitted paper presents a novel method for robust data selection in deep learning, aimed at addressing issues related to arbitrary noise within datasets. The authors propose a framework that relies on the Geometric Median for improving robustness over existing methods that typically use the mean. The importance of topic is significant as it seeks to enhance the reliability of training models in real-world scenarios, where data corruption is often prevalent.

Reviewers unanimously expressed strong reservations about the paper's contributions, specifically criticizing the novelty and clarity of the proposed method. While some reviewers acknowledged the potential relevance of the authors' approach, they highlighted that the paper failed to sufficiently differentiate itself from prior works and lacked thorough experimental validation on larger-scale datasets. The feedback indicates a consistent sentiment that the paper does not meet the expected standards for publication.

Despite the authors' rebuttal which aimed to address these concerns by clarifying their methodology and proposing future extensions, critical reservations remained unaddressed. Reviewers remained unconvinced regarding the practical implications of the proposed method and its robustness claims, especially in larger-scale applications. As a result, after weighing the reviews and the rebuttal, it is clear that the overall consensus leans towards rejection due to insufficient evidence of novelty and effectiveness. Ultimately, the decision is to reject the paper.

Decision: Reject