Geometric Median (GM) Matching for Robust k-Subset Selection from Noisy Data
Authors: Anish Acharya
Sujay Sanghavi
Alex Dimakis
Inderjit S Dhillon
Venue: ICML 2025 poster (2025)
Keywords: robust
subset
sampling
efficiency
coreset
combinatorial
noise
real world
corruption
Primary area: deep_learning->robustness
TL;DR: This paper proposes Geometric Median Matching -- a robust data pruning method that selects representative subsets by matching their mean to the geometric median, ensuring resilience to extreme noise and corruption.

Abstract: Data pruning -- the combinatorial task of selecting a small and representative 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. Existing data pruning methods often fail under high corruption rates due to their reliance on empirical mean estimation, which is highly sensitive to outliers. In response, this work proposes Geometric Median (GM) Matching, a novel k-subset selection strategy that leverages the Geometric Median (GM) , a robust estimator with an optimal breakdown point of 1/2; to enhance resilience against noisy data. Our method iteratively selects a $k$-subset such that the mean of the subset approximates the GM of the (potentially) noisy dataset, ensuring robustness even under arbitrary corruption. We provide theoretical guarantees, showing that GM Matching enjoys an improved $\mathcal{O}(1/k)$ convergence rate, outperforming $\mathcal{O}(1/\sqrt{k})$ scaling of uniform sampling, even under arbitrary corruption. Extensive experiments across image classification and image generation tasks demonstrate that GM Matching consistently outperforms existing pruning approaches, particularly in high-corruption settings; making it a strong baseline for robust data pruning.

Geometric Median (GM) Matching for Robust k-Subset Selection from Noisy Data
Anish Acharya 12
Sujay Sanghavi 12 Alexandros G. Dimakis 34 Inderjit S. Dhillon 15
Abstract
ing data (Radford et al.
2018 202
Brown et al. 2020
Touvron et al. 2023 Kaplan et al. 2020 Hestness et al. 2017). However, such large-scale training is usually associ- ated with enormous computational costs, hindering the path to democratizing Al (Paul et al. 2021).
Data pruning - the combinatorial task of select- ing small and representative subset from a large dataset, is crucial for mitigating the enormous computational costs associated with training data- hungry modern deep learning models scale. Since large-scale data collections are invariably noisy, developing data pruning strategies that re- main robust even in the presence of corruption is critical in practice. Existing data pruning methods often fail under high corruption rates due to their reliance on empirical mean estimation, which highly sensitive outliers. In response, this work proposes Geometric Median (GM) Matching, a novel k-subset selection strategy that leverages the GM, a robust estimator with an optimal break- down point of 1/2; to enhance resilience against noisy data. Our method iteratively selects k- subset such that the mean of the subset approxi- mates the GM of the (potentially) noisy dataset, ensuring robustness even under arbitrary corrup- tion. We provide theoretical guarantecs, showing that Gm MATCHING enjoys an improved O(1 /k) convergence rate, outperforming (11/V)) scal- ing of uniform sampling, even under arbitrary corruption. Extensive experiments across image classification and image generation tasks demon- strate that Gm MATCHING consistently outper- forms existing pruning approaches, particularly in high-corruption settings; making it strong baseline for robust data pruning.
Data pruning the combinatorial task of reducing large training set into small informative subset (Feldman 2020
Agarwal al. 2005 Muthukrishnan et al. 2005 Hel-Peled] 2011 Feldman & Langberg 2011). is a promising approach
to reduce the enormous computational and storage costs of modern deep learning.
1.1. Robustness vs Diversity
Consequently, a large body of recent work has been pro- posed to solve the combinatorial subset selection problem. At high level, these approaches rely on some carefully de- signed importance scoring criterion rank the training sam- ples, retaining fraction of them as representative samples (super samples) used for training the downstream model. For example, spatial sampling approaches (Xia et al. 2022
Joshi & Mirzasoleiman, 2023) Sorscher et al. 2022 Needell
et al. 2014) 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 consid- ered the most prototypical (easy) and those far from the centroid treated as least prototypical (hard). Canonical scoring criteria have also been developed in terms of gra- dients (Paul et al. (022).. uncertainty (Pleiss et al. 2020). and forgetfulness (Toneva et al.. 2018). Notably, the spa- tial distance-based score is closely related to the gradient uncertainty / forgetting-
score. Samples close (far away) the class centroid are often associated with smaller (larger) gradient norm lower (higher) uncertainty / harder (easier) to forget (Paul et al.) 2021: Sorscher et al.) 2022 Xia et al. 2022).
1. Introduction
The recent success of deep learning has been largely fueled by the training of gigantic models on vast amounts of train-
In the ideal scenario i.c. in the absence of any corruption, hard examples are known to contribute the most towards downstream generalization performance (Katharopoulos Fleuret 2018 Joshi et al.) 2009. Huang et al.) 22100] Balcan et al. 2007) as they often encode the most discriminative and task-relevant information in the dataset (Xu et al. 2020).
Uniierssity of Texas Austin 2 AAmazon 'University of Califor- nia, Berkeley BBespoke Labs * Google. Correspondence to: Anish Acharya canishacharya edux.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Geometric Median (GM) Matching
However, in the realistic noisy scenarios involving outliers, this strategy often fails since the noisy examples are wrongly deemed informative for training (hang & Sabuncu 2018 Park et al. 2024). To mitigate this issue, existing pruning methods, tailored for such noisy scenarios, aim to retain the most prototypical / easy samples (Pleiss et al.
Algorithm 1 GEOMETRIC MEDIAN MATCHING
(initialization)
A finite collection of grossly corrupted (Definition D ob- servations DD {x; [ pretrained encoder ((+) Fd + _ e.g. CLIP (Radford et al. 2021b); initial weight vector Og E R"; number of sampling batches B, population fraction for GM computation 0 < YGM S 1.
2020 Jiang jet al. 2018, Har-Peled et al. 2007 Shah et al. 2020 Shen
& Sanghavi 2019). Yet, by prioritizing samples far from the decision boundary, these methods overlook less proto- typical but uncorrupted and highly informative examples. This bias introduces a fundamental robustness vs. diversity trade-off (Xia et al.) (2022), where emphasizing robustness can lead to a lack of diversity in the pruned subset. This limitation not only results suboptimal generalization per- formance but, in extreme cases, can also lead to degenerate solutions (Sugiyama & Kawanabe 2012).
(compute embeddings)
T = {w; = x(x,) E R : Vx; E D (pick random neww-subset for GM computation)
PG ~ Φ, where, - 7GM Φ S n
i.i.d
(compute e-approximate geometric median)
GM ( (MG)) arg min Ewietau ||z will
(partition data into batches)
D= B D, (initialize subset)
Moreover, real-world scenarios frequently deviate from ide- alized assumptions, making it challenging or infeasible to adapt selection criteria and methodologies to diverse and un- predictable conditions. Consequently, despite its drawbacks in prioritizing informative examples, random sampling re- mains the industry standard due to its simplicity, efficiency, and ease of implementation. Due to space constraints, more detailed related work is deferred to Appendix C
Ds 5- 0
for batch index b = 1,... . do
(load batch embeddings)
Tb = =w: E X; E )D,
for iterations = 0, 1, 1.......k k/B do (find embedding closest to 0,) w := arg m. (0), wi)
(update direction parameter)
0.+1 : 0 +
p. (+,)) w
1.2. Overview of Our Approach
(update selected subset)
To go beyond these limitations, we investigate the k-subset selection problem under the Gross Corruption Framework (Definition] where 0 < & < 2 fraction of the samples are allowed to be arbitrarily perturbed. This allowance for arbitrary corruption enables us to capture many practical robustness scenarios- including corrupt features / labels and adversarial attacks.
Ds := Ds Ux where, = (xx) (update the batch embedding set)
D == D \
end
end return: Ds
We make a key observation that: existing pruning methods typically use the empirical mean to calculate the centroid of the samples, which then guides the selection process based on how representative those samples are. However, the empirical mean is highly susceptible to outliers- - in fact, is possible to construct a single adversarial example to arbitrarily perturb the empirical mean (Figure ...
true (uncorrupted) distribution. Our key idea is to replace the empirical mean with a robust surrogate - Geometric Median (Gx))Definition 3 (Weber et al. 1929; Weiszfeld 1937) - a classical estimator of the central tendency, inher- ently robust to outliers.
In particular, we optimize over finding k-subset that mini- mizes the distance between the subset's 's empirical mean and the Gm of the (potentially noisy) dataset over some appro- priate embedding space, using herding (Welling) 2009) style greedy iterative updates. We call our algorithm Geometric Median (GM) Matching as described in Algorithm []
As consequence, in the presence of arbitrary corruption, the conventional distinction between easy (robust) and hard samples breaks down, leading to the selection of subsets that are significantly compromised by corruptions (
In response, we propose a novel subset selection strategy that fosters balanced diversity, effectively navigating vari- ous regions of the distribution while avoiding distant, noisy points. Specifically, we formulate the subset selection prob- lem as one of minimizing the Maximum Mean Discrep- ancy (Gretton et al. 2012) between the empirical distribu- tion induced by the selected subset and that of the underlying
Intuitively, Gm MATCHING can be viewed as a robust gen- eralization of Kernel Herding (Chen al. 2010). By re- placing its vulnerable empirical mean with the Gm, we inherit the favorable (11/)) convergence of Kernel Herd- ing while adding robustness to adversarial and heavy-tailed noise, bridging moment moment-matching and robust estimation in unified framework.
2

---

Geometric Median (GM) Matching
Bosi Juandrr
(a) No Corruption (v
(b) 20% % Corruption (v 0.2) (c) 40% Corruption (2) 0.4)
Figure 1: ROBUST MEAN ESTIMATION: As the corruption rate 0 S v < increases ( representing the fraction of samples drawn from an adversary-choser distribution), the empirical mean increasingly deviates from the true uncorrupted mean. In contrast, the geometric median (GM) remains robust and stays closer to uncorrupted (oracle) mean, demonstrating its resilience to outliers.
RANDOM
(b) EASY
(c)
HARD
(d) MODERATE
(c) HERDING
( Gm MATCHING
Figure 2: DATA PRUNING IN THE WILD: subset 10% of the examples from anisotropic Gaussian (blue) where 40% replaced by an adversarial distribution (red). We compare GM MATCHING with (RANDOM), (EASY) samples closest to the centroid, (HARD) samples farthest from the centroid, (MODERATE) samples closest to the median distance from the centroid, and (KERNEL HERDING) 6 GM MATCHING yields significantly more robust subset than the other approaches.
1.3. Contributions
mean, which has an asymptotic breakdown point of zero. Through both formal analysis (Lemma[) and illustrative examples (Figure T Figure 88, we show how even a sin- gle adversarial point can arbitrarily skew moment-based selection methods.
Overall, our contributions can be summarized as follows:
We introduce principled formulation of the k-subset se- lection problem under the Gross Corruption model (Defi- nition]] D allowing up to 50% of the data to be arbitrarily corrupted. This generalizes prior noise models such as Huber contamination and Byzantine failure, and captures a wide range of real-world noise scenarios such as label noise, outliers, and adversarial attacks. To the best of our knowledge, this is the first theoretical and algorithmic treatment of robust data pruning under such general corruption model.
Motivated by this key observation, we propose robust al- ternative: Geometric Median (G)) Matching, Our method selects subset whose empirical mean approximates the Geometric Median (GM) of the full (potentially corrupted) dataset. We formalize this as a robust moment matching objective (6), and solve it via a greedy, herding (Chen) ct al. 2010) style iterative selection procedure (Algo- rithm D.. Unlike prior approaches, Gm MATCHING lever- ages the optimal 1/2 breakdown point of GM, ensuring robustness even under adversarial perturbations.
We demonstrate that state-of-the-an art pruning strategies including those designed for robustness - fail under gross corruption due to their reliance on the empirical
We provide rigorous theoretical analysis showing that
3

---

Geometric Median (GM) Matching
GM MATCHING converges bounded neighborhood of the true (uncorrupted) underfying mean at an (11/k) rate (Theorem D.. This matches the best-known rates from Kernel Herding in clean settings, and crucially, contin- ues to hold under arbitrary corruption. As a corollary. we derive bounds on the Maximum Mean Discrepancy (MMD) between the selected subset and the clean dis- tribution (Lemma Dp. establishing formal generalization guarantees.
{x, E Rd God p(z)}==> an adversary inspects all the samples and arbitrarily perturbs ab E [0. fraction of them. We will refer to such a set of samples = Ds U Di as u-corrupted, where DB, Dg denote the sets of corrupt and clean samples respectively.
The goal of Robust Data Pruning thus select a k-subset Ds C 'D where [Ds] = k that encapsulates the underlying uncorrupted distribution p(z) induced by subset Dg without any a-priori knowledge about the corrupted samples.
We also propose a practical, batched version of the al- gorithm, that enables efficient computation at scale as outlined in Algorithm [ Our method incorporates two key engineering strategies: (i) sub-sampling for GM esti- mation, and (ii) batched greedy selection. We analyze the computational complexity and demonstrate that batching yields near-linear speedups without significantly compro- mising performance.
Let, ps denote the empirical measure induced by Ds. Then, we aim to solve:
min A (DS(C)) p(x)
(I)
DoC
for some appropriate divergence measure A. As discussed in Section [] the proposed Gm MATCHING (Algorithm [ finds the subset by minimizing the Maximum Mean Dis- crepancy (MMD) (Gretton al. 2012) between Ps and the true underlying uncorrupted distribution p.
We conduct comprehensive experiments across a range of tasks - including image classification, unsupervised distribution matching, and image generation. Our bench- marks cover diverse noise types: feature corruptions, label noise, and adversarial attacks. In all settings, the proposed approach consistently outperforms existing methods, es- pecially under high coruptiion and aggressive pruning (often by > 100) establishing it as a state-of-the--at ro- bust coreset selection strategy.
We measure the robustness of subset selection algorithms via breakdown point (Donoho & Huber 1983 Lopuhaa et al., 1991, Davies & Gather] 2007) - a classic tool in robust optimization to assess the resilience of an estimator.
Definition 2 (Breakdown Point). The breakdown point ĒT of an estimator T()) is the smallest fraction of corrupted samples that can cause it to diverge arbitrarily:
Our analysis and visualizations (Figure 2 highlight how Gm MATCHING balances robustness and diversity avoiding the degeneracies of "eeasy-oll"" pruning while excluding adversarial outliers. This addresses a key open problem in the pruning literature: how to retain task- relevant examples near the decision boundary without being misled by corrupted points.
ST CT= inf { 222 sup ((D))T((D)) =00 (2) De
T(-) achieves the optimal breakdown point Gj = 1/2 it remains bounded V 0 S v0 < 1/2.
2. Problem Setup: Robust Data Pruning
Identifying sample importance is an ill-posed problem without some notion of similarity among the samples. Hence, we assume access to a proxy encoder Φ : RR + H that maps raw inputs into a separable embed- ding space (potentially infinite- dinntt--dimessoonaa) i.e., a Repro- ducing Kernel Hilbert Space (RKHS) H with inner prod- uet determined by a positive-defiitt kernel w(x,x') (ø(x), o(x')) The RKHS structure ensures that inner products in H. define a well-behaved notion of similar- ity i.e. semantically similar samples remain close while dissimilar ones are well separated. We further assume that <(-) is a characteristic feature map i.e. the mapping p + Mp = Ex-p [o(x)] is injective. Simply put, for any two distributions p and q: 14g = 1ig
PROXY ENCODER:
Given set of n samples, data pruning (or coreset selection) aims to find a k-subset that is representative of the under- lying distribution. If such subset can be found compute- efficiently, then training parametric model on the sub- set typically yields similar generalization performance as training on the entire dataset, while resulting in significant speedup when & n.
CORRUPTION MODEL: However, real-world data is of- ten noisy and imperfect due to the difficulty and expense of obtaining perfect semantic annotations, adversarial at- tacks, or simply measurement noise. To account for such realistic scenarios, we study the combinatorial k-subset selection problem under Gross Corruption Framework (Def- inition [ (Diakonikolas et al. 2019) that generalizes both the Huber Contamination (Huber 1992). and the Byzantine
p q. In practice, we instantiate such embeddings with pretrained foundation models, e.g., CLIP encoders (Radford et al. (221a) - -xplic- itly trained via a contrastive objective (Chen et al.) 2020) to map semantically similar examples closer together while pushing dissimilar ones apart.
Failure model (Lamport et al. 1982).
Definition (Gross Corruption). Given observations D
4

---

Geometric Median (GM) Matching
CIFAR-100
Method Ratio
20%
30%
40%
60%
80%
100%
Mean f
Random
3..26:3322
53.61
64.32:1.77
71.03=00775
14.12:40.56
78.14::0.55
62.67
Herding
48.39=1142
50,89=00.7
62.99=0.61
70.61=0.44
74.21
18.14:4.555
61.42
Forgetting
35.57+1.40
49.83=40.91
59.65=2.50
73.34=0..9
77,50=0.53
78.14
59.18
GraNd--ccom -core
42.65++1.39
53.14=11228
60.52:0079
69.70=0.68
74.67=40.79
08.14:0.55
60.14
EL2N-score
17.32=1116
41,98=0.54
50.47=1.20
69.23=1100
75.96=10.88
78.14:0.55
$2.99
Optimization- based
42.16:13.30
53.19 14
58.93=0.98
68.93=0.700
75.62-40.33
78.
59.77
Self-sup--scleee -eelection
44.45=22.51
54.63-22.10
62.91=1220
0..
75.29=40.45
14:40.55
61.60
Moderate-DS
51.83=00.52
1.679:1166
0.99
0.9
75.44=0.40
14.14
64.37
GM Matching
55,93: 0.48
63.08 0.57
66.59 + 1.18
70.82 0.59
74.63 0.86
78.14 0.55
66.01
Tiny ImageNet
Random
24.02=00.41
29.79+0..27
34.41
40.96=00477
45.74++0.61
49.36-+0.25
34.98
Herding
24.09=00.45
29.39=0053
34.13=0.37
40.86=0061
45.45:10.33
49,36=0.25
34.78
Forgetting
22.37=0.71
28.67=0.54
33.64=0.32
41.14=0.43
46.77=10.11
49,36=:0225
34,52
GraNdd-szore
23.56+00.2
29.66-00.37
34.33-0.50
40.77=00.2
45.96+40.56
49,36++0.25
34.86
EL22-sccre
19.74=0.26
26.58=00400
31.93=:0228
39.12=0046
45.32:4.27
49.36=:0.25
32.54
Optimization-bseed
13.88=22.17
2..75=1.62
29.77=0.94
37.05=2.81
43.76::1.50
49.36::0.25
29.64
Self-sup.-selcctee
20.89=0042
27.66=0.550
32.50=0.30
39.64=0.39
44.94:10344
49.36::0.25
33.13
Moderate-DS
25.29=#0.38
30,57=0.20
34.81=0.51
41.45=0.44
46.06:20.33
49, 49,36=+0225
35.64
GM Matching
27.88=0019
33.15-:0.26
36,92 0.40
0.14
46.75:40.51
49.36++0:25
37.44
Table 1: (Clean) IMAGE CLASSIFICATION: Comparing (Test Accuracy) pruning algorithms on CIFAR-100 and Tmny-Im the uncorrupted setting. ResNet-50 is used both as proxy and for downstream classification.
3. Geometric Median Matching
ROBUST MOMENT MATCHING : Building on this key observation, propose to solve robust variant ( of the moment matching objective (3) instead. The key idea is to replace the empirical mean with a robust surrogate estimator of the targel moment, mitigating its susceptibility to corrupted samples.
In the uncorrupted setting i.e. when & = 0, a natural and theoretically grounded approach for data pruning for- mulate it combinatorial MOMENT MATCHING objective:
|1
arg min
A =
Σ ((x)) X.ED
Σ (xx)) x,
A well-designed robust estimator jt should guarantee that the estimation error, A even under cccorruppion (Definition) D In this context, Geo- metric Median (GM) Definition 3 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., 2015 Kemper man 1987) Figure [78). Moreover, GM guaranteed lie in the relative interior of the convex hull of the majority (good) points i.e. μa C Cg,, making it an attractive choice to estimate the target moment.
DD [Ds
D
و < 5 remains bounded,
where the goal is to find k-subset such that the empir- ical mean of the subset closely approximates that of the full dataset. Note that, 33) is an instance of the famous set function maximization problem known to be NP-hard via a reduction from k-set cover (Feige 1998). Remarkably, (Mirzasoleiman al.! 2020) demonstrated transforma- tion into submodular set cover problem, allowing efficient solutions via greedy algorithms (Nemhauser et al.) 1978) Despite strong theoretical guarantees in the uncorrupted setting, the moment matching objective can result in arbi- trarily poor solutions under gross corruption (Definition Vy 0. The vulnerability can be attributed to the estima- tion of target moment via empirical mean notorious for its sensitivity outliers. To illustrate, consider single adver-
Definition 3 (Geometric Median). Given a finite collec- tion of observations {σ(x1), ((x)).... .(x,)) defined over Hilbert space H E Rd, equipped with norm || and in- ner (-) operators, the geometric median (Fermat- Weber point) /Weber al. 1929) μ g defined as:
sarial sample x (DD -ExpeeEx d(x) forcing
12
the empirical mean an adversary chosen arbitrary target 5 This implies that the empirical mean can't tolerate single grossly corrupted sample i.e. yields lowest possible asymptotic breakdown point of O. Consequently, optimizing over (3) no longer guarantees convergence to the true underlying (uncorrupted) moment Ss = ExED, (xx). Instead, the subset selection can be hijacked by a single bad sample, warping the solution towards an adversarial target.
f1 GM arg min *EH
p(z) = Σ 1=1
((x:)
(4)
Computing the Gm exactly, is known to be algebraically intractable (Bajaj 1988), making it necessary to rely on ap-
proximation methods to estimate the Gm (Weiszfeld) 1937]
Vardi & Zhang 2000 Cohen et al. 2016). We call point
5

---

Geometric Median (GM) Matching
Method / Selection ratio
20%
30%
40%
60%
80%
100%
Mean 1
CIFAR-100 with 20% corrupted images
Random
40.99=1.44
50,38=1.399
57.24:0.65
63.21=1.31
71.74=0.28
74.92=
57.11
Herding
44.42-40.46
53.57+00.31
60.72-+1.78
1.703
73.08+00.98
74.92-+0.88
60.18
Forgetting
26.39=0.117
40.78:2..2
49.95:2231
6..71=1.12
73.67=1.12
74.92+0.88
51.30
GraNd-sscom
36.33+22.66
46,21++1.48
55.51+10.76
64.5942.40
7..14+1.36
74.92++0.88
54.56
EL.2--score
21.6442.03
23.78::1.66
35.71=:1.17
86.3240.86
69.66=0043
74.92-40.88
Optimization hused
3..4241.66
4..37
1..0
1..19:11.27
70.06:1-..3
74.92:10.88
54.42
Self-sup-sslection
42.61=2.44
54.04+1.90
59,51:1.22
68.97:40.96
72.33-+0.20
74.92-40.88
60.01
Moderate
42.98:10.87
11.84411.96
70.05:1:.29
73.67:0.30
74.92-10.88
GM Matching
47.12=0.64
59.17=00.92
63.45-+0.3
71.70=10.60
74.60 1.03
74.92++0.88
63.21
Tiny ImageNet with 20 % corrupted images
Random
19.9911.42
25.93:10.53
30.83:1:044
37.98:10311
42.9610.62
46.68:1043
31.54
Herding
19.46=0.114
24.47=0.33
29.72:10.39
37.50==0.59
42.28=0.30
46.68-1043
30.86
Forgetting
18.47=0.46
25.53:0.23
31.17:0:244
39.35:0.44
44.55=0.67
46.6810.43
31.81
GraNd-score
20.07=20.49
26.68=0.40
31.25:10.40
38.21=0.49
42.84=0.72
46.681043
30.53
EL2N-score
18.57=0.30
24.42:0.44
30.04:10.15
37.6222044
42.4320.61
46.6810433
30,53
Optimization-based
13.71=0.26
13.33++1.44
29.15+2..4
1.86
42.94=0.52
46.88+043
29.06
Self-sup--eleccioon
20.22-20.23
26.90=0.500
31.9310499
39.74:1.522
44.27+0.10
46.6810443
32.61
Moderate-DS
23.27=0.33
29.06-0.336
33.48-0.111
40.07=0.36
44.73+0.39
46.68:0443
34.12
GM Matching
27.19=1.922
31.70:10.8
35.14:10119
42.04:10.31
45.12:10.28
46.68:10.3
36.24
Table 2: (FEATURE CORRUPTION) IMAGE CLASSIFICATION: Experiments comparing pruning methods when 20% of the images comuppedd ResNet-50 is used for both proxy (data pruning) and downstream training.
Tardor
Sandiee Herding
Random Heeding
(a) No Corruption
(b) 20% Corruption
(c) 40% Corruption
Figure 3: SAMPLING CONVERGENCE (RECOVERING A ANSOORROIIC GAUSSIAN): Comparison of convergence rates for Mcan Discrepancy, defined as A = 1| mell? as function of sample size A under varying corruption rates. Without corruption, both Herding and GM Matching achieve quadratic improvement (1/k) over random sampling (1/vk). In the presence of corruption, GM Matching demonstrates superior robustness, maintaining convergence while Herding is significantly impacted.
c
GM E H an e accurate Gm if:
Consequently, we perform herding style greedy minimiza- tion (Chen al. 2010) of the error (6) Starting with a suitably chosen On H; we repeatedly perform the follow- ing updates, adding one sample at time, k times:
Σ
Me GM
((x)) (1++)) Σ
UM o(xi)
(5)
We adopt the popular Weiszfeld Algorithm ( (Algorithm] for approximating the Gm due of its efficiency, numerical stability and simplicity. We refer the reader to Appendix for more details and results computing Gm.
Xt+1 = arg max (0,, ((x))
XED
0 = 0, +
He x(xx+1)
(8)
Leveraging the breakdown and translation invariance prop- erties of GM we solve for the following objective:
arg min
A
14,
GM
Σ X.EDs
d(xx))
(6)
We refer to the resulting robust data pruning approach as Gm MATCHING (Algorithm
DD
Pai==
3.1. Theoretical Analysis
In other words, we aim to find a k-subset Ds such that the empirical mean the subset μı = Ex o(x,) approximately matches the GM of the input dataset D.
Notably, Gm MATCHING is an infinite memory, determin-
istie process as at any iteration T, Or encapsulates the
6

---

Geometric Median (GM) Matching
entire sampling history:
n -EXEDD (o(x)) the rate (11/k) such that:
T
8 D
2²a
0r = 0o + THe GM Σ o(x))
8² - ( DDB
0 + (1D5l - (DB) )²
(9)
1=1
where, 0g [Dg] EXEDg Bl(((x) μ 1012 denotes the
Conceptually, Or represents the vector pointing towards under-sampled regions of the target distribution induced by D iteration T. Greedy updates in the direction that reduces the accumulated error encourage the algorithm to explore underrepresented regions of the feature space, pro- moting diversity. By matching the GM rather than the empirical mean, the algorithm imposes larger penalties on outliers, which lie farther from the core distribution, pri- oritizing samples near the convex hull of uncorrupted points Cg = conv ( (x) x E Dg). As result, the algo- rithm promotes diversity in balanced manner, effectively exploring different regions of the distribution while avoid- ing distant, noisy points, thus mitigating the robustness vs. diversity trade-off discussed Section]
variance of the uncorrupted samples.
This result suggests that, even under gross comupption, Gm MATCHING converges to neighborhood of the true mean, where the neighborhood radius depends on two terms - the first term depends on the variance of the un- corrupted samples and the second term depends on how accurately the GM is calculated. Furthermore, the bound holds Ya - Dz/ D robust even when 1/2 of the samples are arbitrarily cor- rupted, i.e. it achieves the optimal breakdown point of 1/2. Furthermore, Gm MATCHING achieves a convergence rate of (11kk) - quadratic improvement over random sampling ( //). As a straightforward consequence of Theorem I we have:
implying Gm Matching remains
Lemma 1.
10
A (DDs))u(t)) (((s))
0
1
comuption rate(())
10
16
4e2
+ (1 (1-a)2 0
+
(10)
0.1
Dg (2 a)
10
0,2
10
16'
10'
10'
By matching (DDs) to (((g)), we ensure that Ds cap- tures the uncorrupted distribution's first moment in the RKHS. Specifically, because ((-) is a characteristic feature map, bounding (Ds) - (=(z))] immediately bounds AMMD (ps, p). In turn, If the subset satisfies A S 6, then the expected risk difference between models trained on Ds and can be bounded as O(8)), assuming the model class exhibits Lipschitz continuity in expectation (Shalev-Shwartz & Ben-David 2014). Detailed proofs in Appendix
number of samples
Figure 4: GM SCALING (CONVERGENCE)) Comparison of Mean Estimation Error ie. deviation of GM from the oracle mean eM noll w.rl sample size [D] and corruption rate tb.
CONVERGENCE GUARANTEE: Our convergence analysis leverages two key properties of GM its robustness under gross corruption and the fact that it guaranteed to lie in the interior of the convex hull of the majority (good) sam- ples (Boyd & Vandenberghe| 2004).. First, we exploit the robustness property of GM to get an upper bound on the estimation error w.r.t the underlying oracle mean (Acharya ct al. 2022; Chen et al., 2017). Next, we use the property that GM guaranteed to lie in the interior of the convex hull of the majority of the samples (Boyd & Vandenberghe Bo0dd..Cmmiiingg these two results, we establish the follow- ing convergence guarantee:
3.2. Computational Complexity Analysis
Ensuring computational efficiency is paramount in large- scale, real-world applications. Below, we outline the three major cost components in Gm MATCHING:
(A. Compute Embeddings) For inputs divided into L n (d) patches / tokens, the computational cost com- puting CLIP ViT (Radford et al., 2021a) o(-) Rd + Rs embedding is Oldh" + dPh) where h is the hid- den size of the encoder. (B. Compute Gm) Weiszfeld's algorithm(Algorihhm 2 converges in the worst case as Oss/e) i.e. to compute سL over the embeddings incurs Po O(ns/e) (C. Sampling Iterations) Each iteration of Gm MATCHING computes inner products between all points in D and a direction vector 0 E R incurring x (nks)) compute. Additionally, storing the embeddings gives rise to
Theorem Suppose that we are given a set of grossly corrupted samples D 'Dg U 'D (Definition [T. an approx. GM(-) orucle (4) and characteristic feature map o(.): : Rd -7 H. Further assume that [[x(x]] S R Vx E D for some constant R. Then, GM MATCHING guarantees that the mean of the selected k-subset Ds C D con- verges to 5-neighborhood of the uncorrupted (true) mean

---

Geometric Median (GM) Matching
(ns) space complexity. Thus, the overall time complexity can be expressed as:
following baselines: (1) Random; (2) Herding (Welling
2009; (3) Forgetting Toneva et al. 2018); (4) GraNd-
score (Paul et al. 2021): (5) EL2N-score (Paul et al. 202 )
Toмm = O(((dh² + d h + s/c + ks))
(6) Optimization based Yang et al., 2022); (7) Self-sup.-
To improve efficiency, we propose a two-fold batching strat-
selection (Sorscher et al.
2022 and (8) Moderate (Xia et al.)
egy as outlined in Algorithm[ | (1. Subsampling for GM);
2022) across three popular Image Classification datasets- Tiny-ImageNet, CIFAR 10/100. Our experiments span popu- lar deep nets including ResNet-18/50, VGG-16, ShuffleNet, SENet, EfficientNet-B0)
Instead of computing GM over the entire dataset, we com- pute it over a randomly chosen You ffacctin (0 < YOM < 1),
reducing complexity to (nT)Gxs/e)) The deviation of GM from the true mean depends on the variance of the clean population (Theorem D. In practice, for sufficiently large YGM. the variance increase is negligible compared to the sav- ings (Figure I. (2. Batched GM MATCHING Iterations): Instead of selecting all & samples once, we divide the itera- tions into B batches, selecting k/ B samples per batch. This results in a linear reduction of inner product computations per iteration, lowering the complexity to (nskk/ B).
IDEAL (No CORRUPTION) SCENARIO: Our first sets of experiments involve performing data pruning across se- lection ratio ranging from 20% 80% in the uncorrupted setting. The corresponding results, presented in Table [] indicate that while Gm Matching developed with robust- ness scenarios in mind, 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 average. In particular, we note that Gm Matching enjoys larger gains in the low data selection regime, while staying competitive at low pruning rates.
320
512
2004
CORRUPTION SCENARIOS:
To understand the perfor- mance of data pruning strategies in presence of corruption, we experiment with three different sources of corruption image corruption, label noise and adversarial attacks.
10
ROBUSTNESS TO IMAGE CORRUPTION: In these ex- periments, the input images are corrupted - a popular ro- bustness setting, often encountered when training models on real-world data (Hendrycks & Dietterich 2019 Szegedy et al. 2013). To corrupt images, we apply: 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 We ob- serve that Gm Matching outperforms all the baselines across all pruning rates improving =3% across both datasets on average. We note that, the gains are more consistent and profound in this setting than the clean setting.
Cormsott Size (A)
Figure 5: GMM SCALING (CONVERGENCE): Comparing mo- ment matching error || [pg - u=sl of GM MATCHING across dif- ferent batch size (b).
However, choosing too small of a batch size can increase variance and slow down convergence (Figure 5). In practice, with a moderate batch size, this additional error is often negligible, while the speedup is substantial. Incorporating these two ideas results in overall complexity:
Tosm (n(chh + dh + ks/B + /tm)s/e))
We provide additional discussion and wall clock experi- ments in Appendix G.I
ROBUSTNESS TO LABEL CORRUPTION: Next, we con- sider another important corruption scenario where a fraction of the training examples are mislabeled. We conduct experi- ments with synthetically injected symmetric label noise (Li et al. 2022 Patrini et al., 2017 Xia al.) 2020). The re- 3 Left). Encouragingly. Gm Matching outperforms the baselines by ~ 12% Since, mislabeled samples come from different class - they tend to be spatially quite dissimilar, being less likely to be picked by Gm matching, explaining the superior performance.
4. Experiments
In this section, we outline our experimental setup, present our key empirical findings, and discuss deeper insights into the performance of GM MATCHING.
sults summarized in Table
Due to space constraint, we only present a small subset of results in the main paper; a larger set of experiments and implementation details can be found in Appendix[] []]
ROBUSTNESS TO ADVERSARIAL ATTACKS: Finally, we experiment with adversarial attacks that add impercepti- ble but adversarial noise natural examples (Szegedy et al.
4.1. Image Classification
To ensure reproducibility, our experimental setup is identical to Xia et al. 2022). We compare GM MATCHING with the
8

---

Geometric Median (GM) Matching
CIEAR- 100 (PGD Attuck)
CIFAR-100 100 (GS Attuck)
CIEAR-I0M 100 (Label noise)
Tiny ImageNet (Label moise)
Method/ / Ratio
20%
30%
20%
30%
Method/ Ratio
20%
30%
20%
30%
Random
43.23++0.31
52.86+0.35
44 41
53.44=00.4
Random
34.47=0064
13.26+1.21
17.78-0.44
23.88=0042
Hending
40.21:10.72
49.62.10.65
39.92-11.03
50.14:0..15
Hending
42.29::1.75
50.52.1.338
18.98:0.44
24.23::0.29
Forgetiing
35.90:11_30
47.57.10.9
37.55:0.553
46.8811191
Forgetting
36.5341.11
45.7811.04
13.20:0.38
21.79:00433
GraNd-score
40.87=#0.84
50.13:20.30
40.77=11.11
49.88=0.85
GraNd-score
31.72:00.67
42,80+0.30
18.28=0.52
23.72=0018
26.61.10.58
34.50.11.02
26.72.10.66
35.55
EL scure
29.82.11.19
33.62.1..35
13.93_0069
18.57_00.31
Optimization-
38.29=1.77
46,2511882
41.36:10922
49.1010881
Optimization based
32.79=0062
41.8011.14
14.77=0.95
22.52=0.77
Self-sup-selectioon
40.53+1115 15
49.95=0.500
40.74 .66
$1.23=0.255
Self-sap--sleccioon sellccionn
31.08:0.788
41887=0.63
15.10:0..3
21.01=0.36
Moderate-DS
43.60-+0.77
51.66-4..8 39
44 68.69-00.68
53.71+0.37
Moderate-DS GMt Matching
40.25-00.12
18.53++1.60
19.64-0.40
24.96-0.30
GM Matching
45.41.10.88
51.80.1.01
49.78.10.27
55.50.10.31
52.64.10.72
61.0110.47
25.80
31.71
Table 3: (Left) (LABEL NOISE) IMAGE CLASSIFICATION: Comparing (Test Accuracy) pruning methods on CIFAR-100 and TinyImageNet datasets, under 20% Symmetric Label Corruption, at 20% and 30% selection ratio. ResNet-50 is used both as proxy and for downstream classification. Side-by-side comparison of (Test Accuracy) pruning methods under adversarial attacks (left) and label noise (right) across CIFAR- 100 and Tiny ImageNet datasets. ResNet-50 is used both as proxy and for downstream classification. (Right) (ADVERSARIAL ATTACK) IMAGE CLASSIFICATION: Comparing (Test Accuracy) pruning methods under PGD and GS attacks. ResNet-50 is used both as proxy and for downstream classification.
1.0
Casy
120
Casy
120
Dasy
125
Roderrs
Modenss
100
Mobertss
100
ONL Medrie
80
ONL Nacking
GM, Muscling
2 75
60
40
26
20
20
20
40
60
80
100
20
40
60
80
100
20
40
50
80
100
Sathett Ston
Subsert Siaw (S))
Saboot Stoee
(a) No Corruption
(b) 20% Corruption
(c) 30% Corruption
Figure 6: DIFFUSION (FID): We train DDPM MNIST across different sampling fraction and corruption rates using different sampling strategies. Gm MATCHING consistently outperformed other approaches especially under corruption.
2013 Huang et al. 2010). Specifically, we employ two pop- ular adversarial attack algorithms- PGD attack (Madry et al. 2017) and GS Attacks (Goodfellow et al. 2014) on models trained with CIFAR-I00 and Tiny-ImageNet to gen- erate adversarial examples. Following this, various pruning methods are applied these adversarial examples, and the models are retrained on the curated subset of data. The results are summarized in Table 3 Right). Similar to other corruption scenarios, even in this setting, Gm MATCHING outperforms the baselines yielding R 3% average gain over the best performing baseline.
selection methods, we introduce a range of structured per- turbations in the training data, including Gaussian noise, uniform noise, random patches, Cutout augmentations, and entirely random images (Figure [8). We perform sample selection over CLIP ViT-B/32 (Radford et al.. 2021a) em- beddings (Figure 19). The performance of each sampling method is summarized (FID Score) in Figure 6 where Gm MATCHING consistently outperforms other approaches by a significant margin. These findings underscore the ef- fectiveness of geometric median-based selection in robustly curating training subsets for generative modeling.
Code is available publicly at Github
4.2. Unconditional Image Generation
To further validate our approach, we conduct experiments on an unconditional image generation task using a diffu- sion model. Specifically, we train U-Net with Denoising Diffusion Probabilistic Models (DDPM) (Ho et al. 2020) on the MNIST dataset. Given the importance of selecting informative training samples, we compare our proposed ge- ometric median- based sampling method (GM MATCHING) against multiple baseline selection strategies: (RANDOM) selection, (EASY) samples closest to the centroid, (HARD) samples farthest from the centroid, (MODERATE) samples with distances closest the median, and (KERNEL HERD- ING) (Welling 2009). To assess the resilience of different
5. Conclusion and Limitations
We introduced Gm MATCHING, a novel data pruning strat- egy that ensures resilience under corruption, with theoretical and empirical validation. However, it relies on approximate GM computation, which can face challenges in degener- ate cases. Additionally, its performance depends on the quality of the embedding space, which may be suboptimal in biased or poorly calibrated encoders. Addressing these challenges with efficient approximations and adaptive em- bedding strategies is a promising avenue for future work.
9

---

Geometric Median (GM) Matching
Impact Statement
active learning. In International Conference on Compu- tational Learning Theory, pp. 35-50. Springer, 2007.
This work presents a method for robust data pruning, aimed improving the efficiency and reliability of machine learn- ing systems trained on large, potentially noisy datasets. By enabling models to learn from smaller, cleaner subsets, our approach reduces the computational burden and improves robustness - making it easier to train models in a data ef- ficient manner, even in imperfect real world settings. The proposed method is task- aagkston and broadly applicable, with potential benefits across a wide array of domains particularly where resilience to corrupted or adversarial data is critical. While the algorithm itself is neutral, any data pruming approach may risk amplifying biases if the embed- ding space or selection criteria reflect underlying societal or structural imbalances. We therefore encourage users to pair this method with fair, well-audited encoders and to critically evaluate the representativeness of selected subsets, especially in high-stakes applications.
Boyd, and Vandenberghe, L. Convex optimization. Cam- bridge university press, 2004.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
Campbell, T. and Broderick, T. Bayesian coreset construc- tion via greedy iterative geodesic ascent. In International Conference on Machine Learning, pp. 698-706 PMLR, 2018.
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual rep- resentations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Overall, this work contributes to central goal in machine learning: learning effectively from imperfect data. We be- lieve the potential benefits are significant, but we also em- phasize the importance of careful, responsible deployment and continued ethical scrutiny.
Chen, Y. and Welling, M. Parametric herding. In Pro- ceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 97-104. JMLR Workshop and Conference Proceedings, 2010.
Chen, Y., Welling, M., and Smola, A. Super-samples from kernel herding. In Proceedings of the Twenty-Sixth Con- ference on Uncertainty in Artificial Intelligence, pp. 109- 116, 2010.
Acknowledgments
This work was supported by NSF Encore Tripods (2217069), NSF's AI Institute IFML (2019844) and grant from Meta.
Chen, Y., Su, L.,, and Xu, J. Distributed statistical machine learning in adversarial settings: Byzantine gradient de- scent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-25,200
References
Acharya, A., Hashemi, A., Jain, P., Sanghavi, S., Dhillon, I. S., and Topcu, U. Robust training in high di- mensions via block coordinate geometric median de- scent. In Camps-Vale Valls, G., Ruiz, F. J. R., and Valera, I. (eds.), Proceedings of The 25th Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 151 of Proceedings of Machine Learn- ing Research, pp. 11145-11168. PMIR, 28-30 Mar 2022.
Cohen, M. B., Lee, Y. T., Miller, G., pachocki, J., and Sidford, A. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 9-21, 2016.
Davies, P. and Gather, U. The breakdown point- examples and counterexamples. REVSTAT Statistical Journal, 5(1): 1-17, 2007.
mlr .resss/
v151/acharya22a.1r
Deng, J., Dong, W., Socher, R., L.-J,, Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and patlern recognition, pp. 248-248222 255. leee, 2009.
Agarwal, P. K., Har-Peled, S., Varadarajan, K. R., et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52(1), 2005.
Bach, F,, Lacoste-Julien, S., and Obozinski, G. On the equivalence between herding and conditional gradient algorithms. arXiv preprint arXiv: 220 4523, 2012.
Diakonikolas, I. and Kane, D. M. Recent advances in algo- rithmic high-dimensions robust statistics. arXiv preprint arXiv: /9/ (tt.:/91110000 1.0511,11110 2019.
Bajaj. C. The algebraic degree of geometric optimization problems. Discrete & Computational Geometry, 3:177- 191, 1988.
Diakonikolas, I., Kamath, G., Kane, D.,, Li, J., Moitra, A., and Stewart, A. Robust estimators in high- high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742 864, 2019.
Balcan, M.-F., Broder, A., and Zhang, Margin based
10

---

Geometric Median (GM) Matching
Donoho, D. L. and Huber, P. J. The notion of breakdown point. A festschrift for Erich L. Lehmann, 157184, 1983.
Hestness, J., Narang, S., Ardalani, N., Diamos, G., Jun, H., Kianinejad, H., Patwary, M., Ali, M., Yang, Y., and Zhou, Y. Deep learning scaling is predictable, empirically, arXiv preprint 1.XXvv1112.000099 2017.
Dosovitskiy, A., Beyer, L.. Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M.,, Heigold, G., Gelly, S., al. An image is worth 16x words: Transformers for image recognition scale. arXiv preprint arXiv:2010.11929 2020.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 1168840-6811, 2020.
Dwivedi, R. and Mackey, L. Generalized kernel thinning. arXiv preprini arXiv:2110.01593, 2021.
Hu, J., Shen, L., and Sun, G. Sgueeze-and-excitatie networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018.
Feige, U. A threshold of In n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998.
Huang, S.-J,, Jin, R., and Zhou, Z.-H. Active learning by querying informative and representative examples. Advances in neural information processing systems, 23, 2010.
Feldman, D. Core-sets: Updated survey, In Sampling techniques for supervised or unsupervised tasks, pp. 23- 44. Springer, 2020.
Feldman, D. and Langberg, M. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of comput- 2011.
Huber, P.J. Robust estimation of a location parameter. In Breakthroughs in statistics, pp. 492-518, Springer, 1992.
Jiang, L., Zhou, Z., Leung, T., Li, L.-J,, and Fei-Fei, L. Men- tornet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In International conference on machine learning, pp. 2304-2315 PMLR, 2018.
ing. pp.
Feldman, V. and Zhang, C. What neural networks mem- orize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing 2020.
Systems,
Joshi, A. J., Porikli, F., and Papanikolopoulos, N. Multi- class active learning for image classification. In 2009 ieee conference on computer vision and pattern recognition, pp. 2372-2379 IEEE, 2009.
Garg, I. and Roy, K. Samples with low loss curvature improve data efficiency. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 20290-20300, June 2023.
Joshi, and Mirzasoleiman, B. Data-efficient contrastive self-supervised learning: Most beneficial examples for supervised learning contribute the least. In Interna- tional conference on machine learning, pp. 15356-15370. PMLR, 2023.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explain- ing and harnessing adversarial examples. arXiv preprint 1rXiv::412.6573 2014.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf. B., and Smola, A. A kemel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint Siti::2001.0836// 2020.
Har-Peled, S. Geometric approximation algorithms.. Num- ber 173. American Mathematical Soc., 2011.
Katharopoulos, A. and Fleuret, F. Not all samples are cre- ated equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525- 2534. PMLR, 2018.
Har-Peled, S., Roth, D., and Zimak, D. Maximum margin coresets for active and noise tolerant learning. In Pro- ceedings of the 20th international joint conference on Artifical intelligence, pp. 836-841, 2007.
Kemperman, J. The median of a finite measure on a banach space. Statistical data analysis based on the LI -oorm and related methods (Neuchâtel, 1987), pp. 217-230, 1987.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Koh, P. W. and Liang, P. Understanding black-box predic- tions via influence functions. In International conference on machine learning, pp. 1885-1894. PMLR. 2017.
Hendrycks, D. and Dietterich, Benchmarking neural network robustness to common corruptions and perturba- tions. arXiv preprint arXiv: /903. 0003./2611. 2019.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical Report, 2009.

---

Geometric Median (GM) Matching
Lamport, L., SHOSTAK, R., and PEASE, M. The byzantine generals problem. ACM Transactions Programming Languages and Systems, 4(3):3824401, 1982.
Park, D., Choi, S., Kim, D., Song, H., and Lee, J.-G. Robust data pruning under label noise via maximizing re-labeling accuracy. Advances in Neural Information Processing Systems, 36, 2024.
Le, Y. and Yang, X. Tiny imagenet visual recognition chal- lenge. In CS 231N, 2015.
Patrini, G., Rozza, A., Krishna Menon, A., Nock, R., and Qu, I.. Making deep neural networks robust label noise: A loss correction approach. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1944-1952, 2017.
Lee, S. H., Lee, S., and Song, B. C. Vision transformer for small-size datasets. arXiv preprint arXiv:2112.1399,, 2021.
Li L., Xu, W., Chen, T., Giannakis, G. B., and Ling, Q. Rsa: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 33, pp. 1544-1551, 1551, 2019.
Paul, M., Ganguli, S., and Dziugaite, G. K. Deep learning on data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34: 20596-20607, 2021.
Pleiss, G., Zhang, T., Elenberg, E., and Weinberger, K. Q. Identifying mislabeled data using the area under the mar- gin ranking. Advances in Neural Information Processing Systems, 13:17044-17056, 2020.
Li, S., Xia, X., Ge, S., and Liu, T. selective-superviser contrastive learning with noisy labels. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 316-325, 2022.
Qian, C., Shi, J.-C., Yu, Y., Tang, K., and Zhou, Z.-H. Subset selection under noise. Advances in neural information processing systems, 30, 2017.
Lopuhaa, H. P., Rousseeuw, P. J., et Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. The Annals of Statistics, 19(1): 229-248. 248, 1991.
Radford, A., Narasimhan, K., Salimans, T., Sutskever, I., al. Improving language understanding by generative pre-training. 2018.
Ma, N., Zhang, X., Zheng, H.-T., and Sun, J. Shufflenet v2: Practical guidelines for efficient enn architecture design. In Proceedings of the European conference on computer vision (ECCV), pp. 116-131, 2018
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., and Sutskever, I. Learning transferable visual models from natural language supervision. In ICML, 2021a.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: (xiv:/70660608. 06083, 2017.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., al. Learning transferable visual models from natural language supervision. In International conference machine learning, pp. 8748-8763. PMLR, 2021b.
Minsker, S. et al. Geometric median and robust estimation in banach spaces. Bernoulli, 21(4): 2335,, 2015.
Mirzasoleiman, B., Bilmes, J., and Leskovec, J. Coresets for data-efficient training of machine learning models. In International Conference Machine Learning, pp. 6950-6960. PMLR, 2020.
Shah, V., Wu, X., and Sanghavi, S. Choosing the sam- ple with lowest loss makes sgd robust. In International Conference Artificial Intelligence and Statistics, pp. 2120-2130. PMLR, 2020.
Muthukrishnan, S. al. Data streams: Algorithms and applications. Foundations and Trends@ in Theoretical Computer Science, 1(2):117-25) 236, 2005.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory algorithms. Cambridge university press, 2014.
Needell, D., Ward, R., and Srebro, N. Stochastic gradient de- scent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems, 27, 2014.
Shen, Y. and Sanghavi, S. Learning with bad training data via iterative trimmed loss minimization. In Interna- tional Conference on Machine Learning, pp. 5739-5748. PMLR, 2019.
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions- i. Mathematical programming. 14:265- 294, 1978.
Simonyan, K. and Zisserman, A. Very deep convolu- tional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
12

---

Geometric Median (GM) Matching
Sorscher, B., Geirhos, R., Shekhar, S., Ganguli, S., and Mor- cos, A. Beyond neural scaling laws: beating power law scaling via data pruning, Advances in Neural Information Processing Systems, 11119523-19338 2022.
Xia, X., Liu, J., Yu, J., Shen, X., Han, B., and Liu, T. Mod- erate coreset: A universal method of data selection for real-world data-efficient deep learning. In The Eleventh International Conference on Learning Representations, 2022.
Sugiyama, M. and Kawanabe, M. Machine learning in non- stationary environments: Introduction to covariate shift adaptation. MIT press, 2012.
Xu, Y. Zhao, S., Song, J., Stewart, R., and Ermon, S. A theory of usable information under computational con- straints. arXiv preprint 20th:2002.10889, 2020.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Xu, Y.H., Qian, C., and Tang, K. Pareto optimization with robust evaluation for noisy subset selection. arXiv preprint arXiv:2501.068/1 2025.
Tan, M. and Le, Q. Efficientnet: Rethinking model scal- ing for convolutional neural networks. In International conference on machine learning, pp. 6105-6114. PMLR, 2019.
Yang, S., Xie, Z.., Peng, H., Xu, M., Sun, M., and Li, Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint arXiv:2205.93322 2022.
Thompson, R. Robust subset selection. arXiv preprint arXiv:2005.08217, 2022.
Zhang, Z. and Sabuneu, M. Generalized cross entropy loss for training deep neural networks with noisy labels. Advances neural information processing systems, 31, 2018.
Toneva, M., Sordoni, A., Combes, R. T. d., Trischler, A., Bengio, Y., and Gordon, G. J. An empirical study of example forgetting during deep neural network learning. arXiv preprint 181.::11100015555 2018.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F, al. Llama: Open and efficient foundation lan- guage models. arXiv preprint arXiv:2302.13971, 2023.
Vardi, Y. and Zhang, C.-H. The multivariate 11-median and associated data depth. Proceedings of the National Academy Sciences. 97(4):1423-144 2000.
Weber, A., Friedrich, J., al. Alfred Weber's theory of the location of industries. The University of Chicago Press, 1929.
Weiszfeld, F. Sur le point pour lequel la somme des dis- tances de points donnés est minimum. Tohoku Mathe- matical Journal, First Series, 43:355-388 1937.
Welling, M. Herding dynamical weights to learn. In Pro- ceedings of the 26th Annual International Conference Machine Learning, pp. 1 1121-1128, 2009.
Wu, Z., Ling, Q., Chen, T.. and Giannakis, G. B. Federated variance-reduced stochastic gradient descent with robust- ness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583 4596, 2020.
Xia, X., Liu, T., Han, B., Gong, C., Wang, N., Ge, Z., and Chang, Y. Robust early-learning: Hindering the memorization of noisy labels. In International conference on learning representations, 2020.
13

---

Geometric Median (GM) Matching
Supplementary Material for GM MATCHING
Contents
Introduction
Robustness Diversity
1.2
Overview of Our Approach
1.3
Contributions
Problem Setup: Robust Data Pruning
3
Geometric Median Matching
Theoretical Analysis
Computational Complexity Analysis
Experiments
8
Image Classification
4.2
Unconditional Image Generation
S
Conclusion and Limitations
9
Notations and Abbreviations
16
Additional Definitions
16
Related Work
17
Lemma 2:
Vulnerability Importance Score based Pruning
19
D.I Proof of Lemma
19
Proof of Theorem
19
E.1 Bounding Estimation Error from Approximate Geometric Median
19
E.2 Convergence the Greedy Updates
21
Proof of Lemma 1
22
Computing Geometrie Median
23
G.1
Approximate :Te Weiszfeld Algorithm
24
Additional Details on Computational Complexity Analysis
27
GM Scaling Law
27
14

---

Geometric Median (GM) Matching
H.2
GM MATCHING Scaling Law
28
H.3
Variance Considerations
28
Additional Experimental Details
29
Baselines
29
1.2
Approximating from Noisy Distributions
30
I.2.1
Robustness Corruption
1.2.2
Ablations with Proxy Encoder
31
1.3
Image Classification
32
I.3.1
Experimental Setup
32
I.3.2
Ideal (No Corruption) Scenario
33
I.3.3
Robustness Image Corruption
34
1.3.4
Robustness Label Corruption
38
3,5
Robustness to Adversarial Attacks
38
1.3.6
Ablations with Proxy Encoder
39
1.4
Unconditional Image Generation
44
Experimental Setup
45
1.22
Discussion
46
15

---

Geometric Median (GM) Matching
A. Notations and Abbreviations
A scalar (integer real)
A vector
A
matrix
a
scalar random variable vector-valued random variable
A,A
A set
la, b]
The real interval including and b
A\
Set subtraction, i.e., the set containing the elements of A. that are not in I
as
Element of the random vector
P(a)
A probability distribution over discrete variable
p(a)
A probability distribution over continuous variable, or over variable whose type has not been specified
A:A +B
The function f with domain A and range
fog
Composition of the functions f and g
(x
A function of x parametrized by 0. (Sometimes write f(x) and omit the argument 0 to lighten notation)
||x||p
L norm of x
(ccondition)
if the condition is true, otherwise
GM MATCHING
Geometric Median Matching
B. Additional Definitions
Definition 4 (Multivariate Gaussian). A Multivariate Gaussian (or normal) distribution for random vector Rd with mean and covariance mairix Σ has the probability density function:
(x)- (1)
p(x) (2T)d//2 Σ
exp
(11)
1/2
Definition 5 (Isotropic Gaussian). A Gaussian distribution is said to be isotropic if its covariance matrix is scalar multiple of the identity matrix:
(12)
where, o² > 0 is the variance (common all dimensions) and I is the d d identity matrix.
In this case, the density function simplifies to:
p(x) (2mo2)a/2 exp (- 1
(To02
202 ||x 1e112)
(13)
Key characteristics:
Equal variance in all directions: Every component x has the same variance o²
No correlations: The off-diagonal elements of the covariance matrix are zero.
Circular (or spherical higher dimensions): Level sets of the density (contours) are circles (or spheres) centered at p.
16

---

Geometric Median (GM) Matching
Definition (Anisotropic Gaussian). A Gaussian distribution is anisotropic if its covariance matrix is general symmetric
positive definite matrix that is not scalar multiple of the identity:
Σ
(14)
In this case, the full density function remains:
p(x) (2 exp (-1
- (2(x-1) 1 (mm) 1 (x-(xxx))))
(15)
Key characteristies:
Different variances along different axes: The eigenvalues of determine the variance along the corresponding eigen- directions.
Possible correlations: Off-diagonal entries may be nonzero, indicating correlations between components.
Ellipptiaal contours: The level sets of the density are ellipsoids, which can be elongated in some directions and compressed in others.
Definition 7 (Diserete Derivative). For a set function f 2 RR marginal gain of f at S with respect to is defined as:
E the discrete derivative or the
Ay(e(S) f(Su(e) f(S)
(16)
Definition (Submodularity). set set function f: 12 + submodular if VA BACE and the following holds:
(e(e| 2 Ay(eBB)
(17)
It can be shown that it is equivalent to the following condition:
f(A) -
f(AUB)
(18)
Definition 9 (Convex Hull), Given set S C R.d, the convex hull S defined as the set of all convex combinations of points in S, i.e.
conv(8) Ax x E S, 220, Σ A 1, MEN
C. Related Work
large body of recent works have been proposed solve the data selection problem detailed below:
IMPORTANCE SAMPLING
One set of data pruning approaches rely on some carefully designed pruning metrics to rank the training samples based on the scores and retain fraction of them as representative samples, used for training the downstream model. For example, (Xia ett al. 2022 Joshi Mirzasoleiman 2023 Sorscher et al. 2022) calculate the importance score sample 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 least prototypical (hard). While this work primarily focuses spatial approaches, it is worth mentioning that the canonical importance scoring criterion have been proposed in terms gradient norm (Paul et al. 2021 Needell et al.] (014), uncertainty (Pleiss et al.) 2020 Garg & Roy 2023) and forgetfulness (Toneva et al. 2018 Feldman & Zhang 2020)). Typically, samples closer to the class centroid in feature space tend to have lower gradient norms, exhibit lower uncertainty, and are harder to forget during training. In contrast, samples farther from the centroid generally have higher gradient norms, greater uncertainty, and are casier to forget (Paul et al. 2021 Xia al. 2022). However, such scoring-based selection methods typically rely on the empirical mean
Sorscher al. 2022
17

---

Geometric Median (GM) Matching
to define centroids, making them brittle under data corruption-a vulnerability that becomes critical in noisy or adversarial
settings.
MOMENT MATCHING METHODS:
A second family of methods tackles data selection as an optimization problem, aiming to match certain statistical mo- ments-such as means, losses, or gradients-
the subset and the full dataset. These techniques, often rooted in coreset construction, select a subset whose empirical properties approximate those of the entire dataset (Chen et al. 2010)
Campbell & Broderick 2018 Dwivedi & Mackey 202I). A notable extension is gradient- based moment matching (Mirza soleiman al. 2020), which seeks to preserve the full dataset's gradient dynamies within the selected subset, enabling efficient yet faithful training.
SUBSET SELECTION FROM NOISY DATA:
Despite substantial advances in subset selection algorithms for large-scale datasets, most existing methods are designed for idealized, clean training data. In practical scenarios, however, real-world datasets are often noisy- by mislabeled examples, corrupted features, or adversarial attacks. Unfortunately, extending traditional subset selection methods such noisy settings remains an under-explored challenge. A key limitation of many classical approaches lies in their dependence on the empirical mean- statistic known to be highly sensitive to outliers and heavy-tailed distributions. As we formally demonstrate in Lemma 2 this renders them brittle under arbitrary corruption, where even a small fraction of adversarial points can severely skew the selection process. Consequently, any method that uses the empirical mean as a reference-eithe the same
directly (e.g.. centroid-based selection) or indirectly (e.g., gradient- or uncertainty- based fundamental vulnerability.
Several recent works have attempted address robustness, but often in narrowly scoped settings. For instance, methods tailored to label noise (Pleiss al., 2020 Park al., (224) typically rely on techniques such as relabeling or sample reweighting, assuming access to a relatively clean subset or side information. These strategies can be effective in controlled scenarios but do not generalize well to broader corruption types such as input perturbations, distribution shift, or structural
outliers.
Another class of methods mitigate noise by aggressively pruning away uncertain or atypical examples- often selecting only the most prototypical or easy-to-learn samples (Shah et al., [020)] Toneva et al.) 2018 Jiang et al.) [0188] Har Peled et al., 2007). While such selection improves robustness by avoiding noisy outliers, inadvertently sacrifices diversity, discarding informative hard examples that are essential for learning decision boundaries. This introduces well- known robustness-diveriic tradeoff (Xia et al. 2022: Feldman & Zhang 2020), where safe selection leads to suboptimal generalization. To balance this trade-off, Xia et al. (2022) proposed a moderation strategy that retains samples closest to the median distance from the class inntroid-aiming to avoid both overly hard and overly easy examples. However, this approach still fundamentally relies on spatial distances measured from the empirical mean, making it vulnerable to corruption that distorts this reference point. Furthermore, while few recent works have studied robust subset selection in a theoretical manner, they are either limited linear models(Xu et al. 2025) or assume simplified theoretical frameworks Saameworss/hhompsonn 2022 Park et al.] 2024), strong assumptions (Qian et al.) 2017). These works stop short of providing practical algorithms or generalization guarantees applicable to modern, highly nonlinear deep learning systems.
In contrast, our work introduces a simple, theoretically grounded algorithm for subset selection under arbitrary data corruption, bridging the gap between robustmess and diversity. Gm MATCHING generalizes to deep models and real-world noisy data, offering provable guarantees under the Gross Corruption.
CONNECTION TO KERNEL HERDING
Gm MATCHING builds upon the classical Kernel Herding framework (Welling, 2009 Chen & Welling 2010; Bach et al., 2012), which selects representative subsets that match the mean embedding of the data distribution in a reproducing kernel Hilbert space (RKHS). While Kernel Herding offers favorable convergence guarantees (1/kk) vs. ((1/Vk) for random sampling; it relies on the empirical mean, making it vulnerable to outliers and adversarial corruption. Gm MATCHINNG preserves the moment-matching spirit of Kernel Herding but replaces the empirical mean with the geometric median (GM), a robust estimator with a breakdown point of 1/2. This simple substitution significantly improves robustness without compromising convergence. To our knowledge, Gm MATCHING is the first method combine robust estimation with herding-style greedy selection, enabling provably fast and stable subset selection even under high rates of data corruption.
18

---

Geometric Median (GM) Matching
D. Lemma Vulnerability of Importance Score based Pruning
In the ideal setting, given a batch i.i.d samples My - u Ex=DD However, the presence even a single grossly corrupted sample can cause the centroid estimate deviate arbitrarily from the true mean. Consider single grossly corrupt sample (x.* 31) such that:
x
Σ
1(y, y)
E
1(ys y)x,
(19)
(x, (X. (xf ..))
resulting in shifting the estimated centroid Apy
Lemma 2. A single gross corrupted sample 19 causes the importance scores to deviate arbitrarily:
Ad(x;, ve) | - 2 =2xx- u Ap
T
(20)
Implying, these methods yield the lowest possible asymptotic breakdown of 0.
D.1. Proof of Lemma 2
Proof. The original importance score without the corrupted sample is:
d(x,, yi) = ||x; - 1
(21)
The importance score with the corrupted sample affecting the centroid is:
(x(x Us) -||x: - 11
(22)
We can calculate the deviation as:
Ad(x;, yi) d(xi, vi) d' (xx;)))))
(ry ( xi - 11 - (xi (xi- ((xx))(xx=)) (xi- 19
T
Xi
The result follows by expanding and defining Apyy = 11 16
E. Proof of Theorem 1
We restate the theorem for convenience:
Theorem Given a set of Grossll-corrupted samples = Dg U DD (Definition 1 and an approx. GM(-) oracle 44) Further assume that ||x|| < R Vx D for some constant Rt. Then, Gm MATCHING guarantees that the mean the selected 6-neighborhood of the uncorrupted (true) mean (Dg)) EXED, (x) the rate (1)
k-subset Ds C D converges such that:
== E (D)
MM(D)) (D))-((Do))
<
8 Dg
L U(Do>) x
Σ
2
(23)
(D DB
( DB))²
Proof. For notational simplicity, WLOG we will assume that the samples are already in RKHS i.e. we drop the notation d(-) for the proof i.e. we assume that x; is already projected on the positive definite kernel space using a characteristic mapping 6(.). We prove Theorem in two main steps:
F. Bounding Estimation Error from Approximate Geometric Median
We will first establish the following result which follows from the definition of GM; see also (Lopuhaa et al. 1991
Minsker et al. 2015) Cohen et al. 2016 Chen et al. 2017 et al. 2019 Wu et al. 2020 Acharya et al. 2022) for similar adaptations.
19

---

Geometric Median (GM) Matching
Lemma 3. Given a set of a-corrupted samples D -Dg U Dg (Defiitionn
and an e-approx. GM(-) oracle then we
have:
(D) - H(DD)) 1 (DDg] DBl)2
8| Σ
u(De))
2 + (DDgl |Dal)²
2Ea
E
E x
(24)
xEDg
where, uhe (D) is the e-approximate GM over the entire (a-corrupted) dataset; and (( = |Pol EXEED x, denotes the mean of the (underlying) uncorrupted set.
-
Now we prove this bound:
Note that, by using the triangle inequality, we can write:
Σ
Me
GM (D)
2
Σ
X;
Me
(D)) ))
Σ
(1
(w (M (D)
x:
(25)
X
x
XIED2
Σ
Σ
Me.
+
Σ
x;
Σ
xi
(26)
X: x:EDg
XiEDE
XiED8
Xi XiEDg
[ool - -PDsl
Me
(D))
Σ
X
2
Σ
(27)
X
x; DD
Now, by definition 5): we have that:
GM (D) - -x:
S inf
2 X
+ Σ
x3 +
(28)
ZEH
X;ED
X
X,ED
Combining these two inequalities, we get:
( DDsl -Dssl
(Dsl
1 CM
[D)
Σ
x:
Σ
xi
+2 E
xi
+
(29)
X.ED
X.ED
X.ED2
This implies:
Me ( s
2
x5
+
(30)
(Peol - -1Disl
X.EDs
(
Dool - [Dss
Squaring both sides,
[ec (D)
GM
5
2
Σ
x:
+
6
(31)
|Dol -1Dss
x.EDg
|Dol
[Ds)]
2
2
e
2
x;
+
(32)
(Del (Dal
x:
(Dgl |Dol
Where the last step is well-known consequence of the triangle inequality and AM-GM inequality. Taking expectation on both sides, we have:
8/Dsf
2 + x
2e2
E
GM
(D)
E x, X,E
Σ
(33)
2
(Dol - (Dsl)
(Pol
-1Dss)
20

---

Geometric Median (GM) Matching
Since, GM is translation equivariant, we can write:
((x: x ((Do))x
D))] -BIGo
(xXIxEE eD))
- -
E Gm
B GM
(34)
Consequently, we have that :
GM (D) (D) - m(Ds) (D)- B ue
||
8/Dgl
Σ
Bxx WDD3)
2ca
D - (Ds)
DDol
x, ED
(Dol (DB)
This concludes the proof of Lemma
3
E.2. Convergence of the Greedy Updates
We will now show that Gm MATCHING converges to μ. (D) O()).
It suffices to show that the error 8 (D) - Ex x;
0 asymptotically. We will follow the proof technique
in (Chen et al. 2010) mutatis-mutandis to prove this result. We also assume that D contains the support of the resulting noisy distribution.
We start by defining a GM-centered marginal polytope the convex hull
Mr conv
1te (D) |x E D
(35)
Then, we can rewrite the update equation g
as:
0.t1 = 0 + 14,
GM (D) X1+1
(36)
0 [x++1 f1c JOM (D)
(37)
0,
arr max x) 14e (D)
(38)
XED
0: arg (ax m) m..,
(39)
0: m.
(40)
Now, squaring both sides we get:
110++112 = =110,12 ||mmm]1 2(0,, m.)
(41)
Rearranging the terms we get:
10++112
-100111 = |m/ || -((0,, m+)
(42)
0.
mm || 2 mm
0|1
(43)
|
m/
0. m
m
||
110.1(
(44)
0,
||
Assume that ||x:| S vx, E D. Then note that,
xx
4
(M(
GM
<
|x|||
+ || GM (D))
s
2r
21

---

Geometric Median (GM) Matching
Plugging this in, get:
|0++1 110.112 S 2|| (r-
||0,|K
Oc
m;
(45)
|m,
Recall that, f2 (D) is guaranteed to be in the relative interior of (x |x E D) (Lopuhaa et al. 2015). Consequently, 3x-ball around (x((D) contained inside M and we have V4 > 0
1991
Minsker et al.
0.
m
B>6 0
(46)
0
m
This implies, 74 > 0
|0:11 -
(47)
Expanding the value of O,, have:
k
Oul| =
Oo + kppe GM (D)
-
_ X
5
r
(48)
Apply Sauchy-Schward inequality:
Xk
I 1100ll
r
(49)
Normalizing both sides by the number of iterations k
GM (D)
Xk
1 S ke
(100||
=
(50)
Thus, we have that Gm MATCHING converges to ftc at the rate (+))
GM
Combining this with Lemma 3 completes the proof Theorem
F. Proof of Lemma 1
We restate the lemma for convenience:
Lemma [ Suppose that we are given a set of grossly corrupted samples D = Dg Ds (Definition D an approx. GM(.) oracle (4) and bounded, characteristic feature map o(-) Rd + H. Then, Gm MATCHING guarantees that:
2 = (u(Ds) - (u(Ds)-u(Po)
16
o0 +
4e2
(51)
(1 - (1-a)²
(Do a0)²
where, a = DDBl/[Dgl < 1 is the ratio of corrupted and clean samples. (DDs) and μe (((g)) denote the mean of the selected subset and the true uncorrupted mean respectively.
Proof. We begin by decomposing the overall error using the triangle inequality:
((Ds)-H(Do) - ((Do)
A
(52)
((DD)) (On(Din
m (D(( -m(D))
(53)
2
(SD1 4 (D)
+2 (o (aa - M(DG)
(54)
22

---

Geometric Median (GM) Matching
Bounding the first term. The herding-style greedy procedure is designed iteratively reduce the discrepancy between the empirical mean of the selected subset and the robust target moment (D)). Standard results from the analysis of kernel herding imply that
(((Ds) (/( (+)
(55)
Thus, there exists constant C1 such that
((Ds) te (D) |'
C1
- k2a
(56)
Bounding the second term.
By Theorem
the robust estimator (D) satisfies
8|
26
pe (D) ((Ds))
o + (1Pgl-
(57)
D DBl)²
- 1 )²
Since [Dgl - [Dg) [Pol(1 a) with a
|Dal/ Dgl
< 1, we can rewrite the bound as
8
2ca
Me
o² (Do)
(58)
(1 - a)
|Dol2(1 a)²
Multiplying both sides by 2 yields:
2
(M)( (D((D)))DD)))
GM
16
(Dg) + Dggl a)²²
4e2
(59)
(1 - a)²
Combining the bounds.
Substituting the bounds from 566 and 59
into 54
obtain
2C1
16
4ea
A
+
(1 a) o 2 (Dg) + iDg
1
(1
a)
Since the constant 20₁ can be absorbed into the 0(1 ((1/k²) term, we conclude that
16
4e
A
o² (Dg) + [1 - a)²
(1 a)²
This completes the proof.
G. Computing Geometric Median
As discussed in Section 3 the Geometric Median (GM) also known as the Fermat- point (Weber et al. 1929). is
robust measure central tendency for a set of observations. Given a finite collection of observations (X1, X2,.. x, defined over Hilbert space E Rd, equipped with norm || || and inner (+) operators, the geometric median(Definition Weber al. 1929 Gm (x), X2. ...... x,)) )) is defined as the solution the optimization problem:
.x,))
GM arg min p(z), where p(z) =
Σ 1=1
xx
z
(60)
ZERd
where p(z) is the sum of Euclidean distances from z to the data points, illustrated in Figure 7
Note that, in contrast, the empirical mean is defined as the minimizer of the squared Euclidean distances:
A arg min p(z), where p(z) Σ |x; - z||²
(61)
im
23

---

Geometric Median (GM) Matching
OM
Sum of Detarces
(a) Triangle
(b) Pentagon
(c) Random
Figure 7: GEOMETRIC MEDIAN VISUALIZATION: The plots illustrate the computation of the geometric median (denoted by the pink circle) for three different spatial point configurations: (a) Triangle, (b) Pentagon, and (c) Random. The color gradient represents the sum of distances p(z) from candidate point all data points, with darker regions indicating smaller values of p(z). The white dashed lines show the connections between the geometric median and the data points, emphasizing how the geometric median minimizes the total Fuclidean distance all points. Additionally, the Voronai regions formed around the data points visually partition space based on proximity, offering insight into how the geometric median balances contributions from each point. In symmetric configurations such as (a) and (b), the Voronoi structure highlights the symmetry in influence regions, leading to geometric median located at the center. For the random configuration (c), the imregular Voronoi regions illustrate the varying influence of data points, with the geometric median robustly adapting to minimize total distance while down-weighting the effect of outlier-like points.
Minimizing the squared Euclidean distances ensures computational simplicity, closed-form solution exists:
(62)
which follows from the first-order optimality conditions of convex quadratic minimization. However, this also makes the empirical mean sensitive to outliers, as extreme values have a disproportionately large effect on the sum of squared distances. the other hand, the linear penalty in the GM computation ensures that the objective less influenced by outliers, as deviations are amplified guadratically.
(Drecte)
Cenmebro Median (DM)
Coometro Median (CM)
Goonetre Median
(a) No Corruption (2) 0)
(b) 20% Corruption (17 0.2)
(c) 40% Corruption (1) = 0.4)
This figure illustrates the deviation of the Empirical Mean (red) and Geometric Median (purple) from the Oracle Mean (green) as the fraction of corrupted samples 0 3 < 1/2 is varied. The uncorrupted distribution is shown in Blue, while the adversarial distribution is shown in red. At 0, all estimators align closely with the oracle mean. As increases, significantly influenced by the corrupted samples, drifting toward the corrupted distribution. In contrast, the GM remains robust, staying closer to oracle mean demonstrating the resilience the GM in the presence of corruptions.
Figure 8: ROBUST MEAN ESTIMATION:
the empirical
G.1. Approximate GM The Weiszfeld Algorithm
Note that the GM optimization problem is inherently non-smooth due to the presence of the Euclidean norm ||x; - z|| which leads to differentiabilityy at points where multiple distances are equal, making gradient-basee optimization difficult. Furthermore, computing the exact geometric median NP-hard in dimensions 2 (Bajaj 1988), as it involves solving a
24

---

Geometric Median (GM) Matching
high-degree polynomial system without closed-form solution.
As result, long line of research has focused on developing efficient approximation methods, and several algorithms have
been proposed (Weiszfeld] 1937 Vardi & Zhang 2000 Cohen et al. 2016) to compute e-approx GM instead.
Recall that, an 6-approximate geometric median denoted by 14cm, satisfies:
GM
X;
S (1
Σ
p GM
X;
where GM is the exact geometric median.
In this work, adopt the celebrated Weiszfeld algorithm (Algorithm) geometric median by leveraging re-weighted averaging scheme.
2
an iterative procedure for approximating the
Algorithm 2 (WEISZFELD) 1937) COMPUTING E-APPROX. Gm
Input:
Observations (x; E TR J==1- initial guess z (0) Rd convergence threshold é > 0, and regularization parameter 6 > 0.
Initialization:
Initialize ( (e.g., as the arithmetic mean of {x, )) set iteration counter 4-
while not converged (i.e.. [|z(k+1] [1 || 2 e) do
(compute update step)
Σ
x, x -2
(k+1)
i=1
x 11:
(update iteration counter)
1
1:
+
end
Return:
z² (k)
Note that the subgradient of p(z) at any point is given by:
12
X;
0p(z)
(63)
X z
Let f(z) = ||z xiIl. where:
f(z) = (z - Tx,) x,).
The Euclidean norm can be expressed as:
d
1z - xi| =
Σ
(2j 2.
1=1
Define g(2) (z xx) (z x;), so:
f(z) = Vglz).
Using the chain rule, the gradient of fzz) with respect to z is:
Vzf(z) = 2/)(2)
Veg(z).
The function g(z) is given by:
g(2) (z x;) (z x:),
25

---

Geometric Median (GM) Matching
and its gradient is:
Vzg(z) 2(z xx).
Substituting Vzg(z) into the chain rule:
1 Vaf(z)= 2/ 2/ g(z)
2(z x;).
Since vg(z)= ||z - -x:/l. we have:
X;
V x;|l
2 X
thus we have that the subgradient of the Euclidean norm
l|z X; with respect to z is:
Z X; x;|
V 2
z
To find the optimal solution z", we can solve the condition:
0p(z')
Substituting z² and re-arranging the terms, we get:
z' 1= X
Since this equation is non-linear in z", solving it directly is infeasible. Instead, the Weiszfeld algorithm approximates zz iteratively using the update:
Ei=1 ||x: 12-220 2
2 (k+1)
Di=1 x x
where (k) is the estimate at the k-th iteration.
This update step can be interpreted as a re-weighted average, where the weights are inversely proportional to the distance of each point x; from the current estimate (*)), Points closer (k) contribute most the next estimate.
Handling Non Non-Differentiabbiity At points where (*) x; i.e. the current estimate coincides with one of the observations, the term ||x; [ 0 results in division by zero. To address this, the algorithm excludes the term corresponding to x; from the summation. Alternatively, the subgradient of ||x; z|| at z x; can be defined as:
2 X;
if + Xis
0||:; z||
{g
g
<1}
if = X
Convergence and Regularizatio: Notably, the Weiszfeld algorithm converges under mild conditions if the initial point (0)) is not chosen at one of the data points. Convergence can be shown using fixed-point theory or by analyzing the decrease in the objective function p(z) at each iteration. However, convergence is only guaranteed to a local minimum if the data
points x; are not in general position (e.g., collinear points in R.2). To handle singularities, we modify the denominator to avoid division by zero:
(k+1)
2
x -x)
where 5 is a small regularization term.
26

---

Geometric Median (GM) Matching
10"
10º
GM 912
10"
10
corruption (a)
10
corruption rate(w)
10
0.05
52
10"
0.05
52
0.1
0.15
10"
0.15
0,2
0.2
10'
10'
10'
10'
number of samples
number samples
(a) Geometric Median (1i OM)
(b) Empirical Mean (fi)
Figure 9: MEAN ESTIMATION ERROR SCALING FOR RECOVERING ANISOTROPIC GAUSSIAN Comparison of Mean Estimation Error i.c. deviation from the oracle mean using Geometric Median (GM) TM and Empirical Mean (EM) a function of sample size and amount of corruption. GM is computed using Weiszfeld Algorithm Algorithm _ The axis represents the sample size i.e. the number of samples drawn i.i.d. distribution. The plots depict the convergence behavior of both methods across varying corruption rates, highlighting the robustness of GM in the presence of outliers. The plots further emphasize the effect of sample size on estimation error for both the estimators.
an anisotropic Gaussian, with fraction 0 S & 1/2 of them corrupted by an adversarially chosen
H. Additional Details on Computational Complexity Analysis
H.1. Gm Scaling Law
We now discuss the computational complexity of GM computation over points in Rd:
Weiszfeld's ss algorithm proceeds by iteratively updating the current estimate (k) via re-weighted average of the data points. Each iteration requires:
1. Distance evaluations: Computing |x, (x1 for all 1,2, ..... n. Each distance in Rd is evaluated in O(d) time, this step costs (nd)) per iteration.
2. Update step: Forming the weighted average (x++1)
(Es X 1//pp//2 (20)))))))) also takes ( time.
Hence, each iteration costs (nd)).
Although Weiszfeld's algorithm is guaranteed to converge under mild conditions, the rate of convergence depends on the geometric configuration of the data points:
Non-degenerate (typical) case: the geometric median GM lies strictly in the interior (i.e., does not coincide with any x; and is at positive distance from each data point), then Weiszfeld's iteration converges linearly near the optimum. The number of iterations to achieve an e-accurate solution typically scales (log(1//)).
If the geometric median coincides with (or lies extremely close to) some data point(s), the objective can lose strict convexity and the Weiszfeld update may progress more slowly. In the worst theoretical analyses, the iteration count grow O11/e)
Degenerate (worst) case:
Putting it together, let K denote the iteration count required for an e-accurate estimate, We have:
Time per iteration O d),
K (log((1/))) 0(1/c)
(typical, non-degenerate),
(worst-case, degenerate).
27

---

Geometric Median (GM) Matching
embed dim (s)
average wall clock time (TGN)
10"
128
256
1024
2048
10'
number of samples
Figure 10: SCALING LAWS (WALL CLOCK) FOR GM COMPUTATION: This figure shows the scaling behavior for computing the geometric median using Weiszfeld algorithm Algorithm in terms of the wall clock time (TGM) as function of population size. The x-axis represents the number samples (n) logaritmmic scale, and the y-axis shows the average wall clock time (Toas) on logarithmic seale. Each curve corresponds to a different embedding dimension (d), ranging from 32 to 4096. The results were generated using synthetic data drawn from a standard normal distribution, with the geometric median computed iteratively until convergence (tolerance 10-5, maximum iterations 100). For each combination of and wall clock time averaged across 10 random seed. The computational cost increases with both and for fixed n, the scaling with is approximately linear, while for fixed s, scaling with n exhibits sub-linear to near-linear growth. These results emphasize the trade-offs in selecting n and for practical applications. Experiments were run on a single-threaded CPU setup. These results confirm that the practical runtime aligns with the expected time complexity of Onns log(1/c)) in typical scenarios, showcasing the efficiency of Weiszfeld algorithm for tigh-dimensional data.
Thus, the overall time complexity is either On d log(1/e)) in the typical scenario or On d (1/e)) in the worst case. In practice, degeneracies are rare for generic data, and Weiszfeld's 's algorithm often converges quite rapidly to a high-accurage solution. In Figure [0] we empirically validate the theoretical scaling behavior of the geometric median computation, demonstrating how the wall clock time 7GM scales with the number of samples n and embedding dimension s.
H.2. Gm MATCHING Scaling Law
We show how the batching scheme scales w.r.t wall-clock time in Figure 11 almost linear scaling can be observed.
H.3. Variance Considerations
In reducing computational costs, the use of sub-sampling for the robust GM, and batching in the Gm MATCHING selection process inevitably introduces additional variance into the estimation and selection outcomes. In this section, we dissect the variance implications of these strategies, stressing that any gain efficiency incurs trade-off with statistical precision- quintessential free lunch scenario: faster computation comes with the cost of reduced statistical precision.
Note that the deviation of GM from the true mean depends on the variance of the clean population (Theorem I]. This implies that, when estimating Gm over a subset of the data, as the variance of the population increases:
A(O²) (1- AGM
(D
(64)
AGMa
n
Thus, while sub-sampling offers significant computational speedup by reducing the number of points used, also amplifies the estimation variance-4 trade-off that must be carefully balanced by choosing appropriate sub-sampling fraction relative to the intrinsic noise level of the data. In practice, however, notice that for sufficiently large 7GM,, the variance increase is negligible compared to the savings as evidenced in Figure 9
Similarly, batching in the Gm MATCHING selection process, where the selection of the k-subset is partitioned into B smaller batches, inherently introduces additional error terms in the convergence. Firstly, for each batch, the herding convergence suffers constant bias penalty because each batch only selects k/ samples instead of samples, thereby incurring an error
28

---

Geometric Median (GM) Matching
10
Batch
Sizuib
128
256
512
(saconda)
20-1
10
10
10a
10
10
10
Coreset Size (k)
Figure 11: SCALING LAWS (WALL CLOCKK FOR BATCH Gm MATCHING function of coreset size (k) across varying batch sizes (h). Log-log scale highlights the computational cost trends for batch sizes ranging from to 1024.
term the order of O(B/k). Moreover, the overall estimate is formed as the mean of the batch estimates, which introduces an additional variance component arising from the averaging of independent errors across batches. This variance term scales as OI//BB) i.e.
(u(Ds) te ( s
B ( k
+
(65)
VB
This implies that, while batching can result in significant speedups small batch size can also slow down convergence. In practice, find that, with moderate batch size, this additional error is often negligible, while the speedup is substantial as demonstrated in Figure 5
I. Additional Experimental Details
In this section, we will provide more detail on our experiments from Section share additional results and provide more detailed discussion.
Our experiments are divided into three fundamental learning paradigms:
Approximating from Noisy Distributions
Image Classification
Image Generation
By dividing the experiments into these categories, ensure that Gm MATCHING is tested across wide spectrum of tasks, covering unsupervised, supervised, and generative learning scenarios. Detailed analyses in each paradigm help uncover not just the strengths of Gm MATCHING but also potential limitations or areas where further improvements can be made. In each experiment, the performance of Gm MATCHING is rigorously compared to established baselines, offering clear evidence of its competitive edge handling noisy data, enhancing classification, and generating realistic outputs demonstrating the practical applicability and versatility of Gm MATCHING across wide array of machine learning challenges.
I.1. Baselines
We compare Gm MATCHING (see Algorithm I against several baseline subset selection methods.
These baselines include:
Samples are selected uniformly at random. This approach serves as a strong baseline that does not incorporate any structure from the data widely adopted in practical applications due to its simplicity and strong performance under idealized conditions.
Random:
29

---

Geometric Median (GM) Matching
Easy: (Shah al. 2020) This strategy selects samples that closest to the centroid of the dataset. These "easy" samples presumed be representative of the core data distribution, but may under-represent the data's diversity, especially in the presence of noise.
(Joshi et al. p This approach selects samples that are farthest from the centroid. While these "hard" samples may capture edge cases or outliers, they can also be overly sensitive noise and may not adequately reflect the central structure of the clean distribution.
Hard:
Moderate: (Xia et al. 2022): : This strategy selects samples that are closest to the median distance from the centroid. This approach aims to balance the representation of the data by avoiding the extremes of the distribution, thereby providing a more stable and robust subset.
(Chen al. 2010) kernel herding employs a greedy algorithm select samples that minimize the discrepancy between the empirical distribution and the target distribution in reproducing kernel Hilbert space which forms the basis of this work.
Kernel Herding:
Forgetting Toneva et al.
2018): Data points that are easily forgotten during optimization are chosen.
GraNd-score (Paul al.
2021 Data points with larger loss gradient norms are included.
EL2N-score PPal et al.
2021 This focuses on data points with larger norms of the error vector, which is the difference
between the predicted class probabilities and the one-hot label encoding.
Optimization- YYngg al.) 2022): This method uses the influence function (Koh & Liang 2017) select data points that minimize the generalization gap under strict constraints.
Self-sup.-selection (Sorscher et al. 2022): After self-supervised pre-training and clustering, data points are selected based on their distance to the nearest cluster centroid, with the number clusters set to the number of classes to avoid tuning. Points with larger distances are chosen.
For Gm MATCHING, the Gm approximated via Algorithm Weiszfeld 1937). The optimization routine terminates, either when the GM approximation error is small en or after maximum number of iterations Tmax is reached. en 10-8 and Tmax 1000 are used for all the experiments.
1.2. Approximating from Noisy Distributions
We simulate Gaussian Mixture Model (GMM) comprising both clean and adversarial components evaluate robust moment estimation in noisy datasets. The clean and corrupt samples are drawn from two anisotropic Gaussian distributions:
Pelean (x) = NNx;; pt M) Padv (I) Nrr;; p/, 2').
(66)
In our experiments, the two Gaussians are well-separated in the 2D plane, ensuring a clear notion of "clean" vs. "adversarial" clusters with means and covariances:
-0.5
10
1
0.5
Σ
M'
(67)
-0.5 0.5
0.5
0.5
Assuming that fraction vi of the data corrupted, the input data modeled as mixture:
Poomupe (x) (1 - 2b) Peteau (x) + 1/ Padv (z))
(68)
The objective is to select a subset Ds of samples such that the subset induced distribution Ps(x) is as close to the clean distribution (z). We generate total of n = 10 samples, where yin samples are generated from Paav(z) and the rest of the - ) samples are generated from Peteun (I)) and the sampling algorithms subset 10% of the samples.
30

---

Geometric Median (GM) Matching
Leffer
Eagy
Hard
30
XG
X0
(a) UNIFORM
(b) EASY
(c) HARD
Modende
Hesting
A PREEEEI At
2
XB
(d) MODERATE
(e) HERDING
(1 Gm MATCHING
Figure 12: No Corruption: : We select 10% of the samples using: (UNIFORM) Random Sampling, (BASy) Selection of samples closest the centroid. (HARD) Selection of samples farthest from the centroid. (MODERATE) Selection of samples closest the median distance from the centroid. (HERDING) Moment Matching, (GM MATCHING) Robust Moment (GM) Matching 66)
1.2.1. ROBUSTNESS TO CORRUPTION
Firstly, in Figure g we observe that as the fraction of adversarial samples t increases, the empirical mean of the noisy data set drifts noticeably towards the adversarial group. In contrast, GM remains anchored near the true uncorrupted mean μ. This divergence underscores the vulnerability of classical moment estimators to even modest levels of noise a phenomenon well documented in robust statisties (Huber 1992 Diakonikolas & Kane, 2019).
In our robust sampling experiments, observe that when r 0 i.e. the no-corruption scenario, all methods trivially capture the clean distribution, but as soon as a fraction of the data is adversarial, many standard strategies fail to consistently filter out the adversarial cluster. However, as t increases as demonstrated in Figure 12 sampling or even heuristic approaches (Easy, Hard, and Moderate), as well as standard Kernel Herding, begin to pick up an increasing number of adversarial points. Their selected subsets start to show a clear dual-group pattern, which results in a mixed empirical distribution that deviates from Petcan (1:).
13 2 14 methods like uniform
In contrast, GM MATCHING yields a significantly more robust subset than these baseline methods, effectively filtering adversarial noise while preserving the intrinsic structure of the clean data. The robustness of Gm MATCHING becomes particularly prominent at high corruption levels (v- = 0.4, vi 0.45) where most other methods fail. This demonstrates the potential of the proposed strategy to serve as powerful tool for robust moment estimation in noisy and adversarial settings.
1.2.2. ABLATIONS WITH PROXY ENCODER
Next, we examine the impact of various kernel maps on the performance of Gm MATCHING, particularly in the presence of data corruption. Using a Gaussian mixture model as our testbed, we empirically evaluated different kernels to understand their ability capture the underlying data structure and robustness under noise.
In Figure 15 we experiment with polynomial kernels:
w(x, = ((x, x') + c)d
(69)
where, e is a constant (typically set 1) and is the degree of the polynomial. We tried varying degrees (1,3,,510)
10))
31

---

Geometric Median (GM) Matching
Leffem
Easy
Hard
X
30
20
(a) UNIFORM
(b) EASY
(c) HARD
Moderde
Herting
2
X8
(d) MODERATE
HERDING
(1) GM MATCHING
Figure 13: 20% Corruption: In this experiment, 20% of the samples corrupted drawn from adversary chosen distribution (red). We select 10% samples using: (UNIFORM) Random Sampling, (EASY) Selection of samples closest the centroid. (HARD) Selection of samples farthest from the centroid. (MODERATE) Selection of samples closest to the median distance from centroid. (HERDING) Moment Matching, (GM MATCHING) Robust Moment (GM) Matching (6). We see that while EASY remains robust, it clearly sampling from low-density areas failing to capture the prototypical samples.
highlighting how increased degree improves representational capacity while potentially amplifying noise when data are corrupted 20% corruption.
I.3. Image Classification
This set of experiments evaluates the performance of Gm MATCHING when applied to Image Classification tasks. To ensure reproducibility, our experimental setup including baselines, neural architectures, and choice of hyper-parameters is identical to (Xia et al. 2022
1.3.1. EXPERIMENTAL SETUP
We evaluate the performance of Gm MATCHING against multiple popular data pruning baselines, namely Random selection, Moderate (Xia al. 2022), Forgetting (Toneva al. 2018). Kernel Herding (Chen et al. 2010). GraNd-score (Paul et al.
2021), EL2N-score (Paul et al. 202I) and Self-supervised Selection (Sorscher et al. 2022 These baselines are evaluated
across both standard (uncorrupted) and touustness-focusee experimental settings.
Our robust sampling experiments assess the resilience of each algorithm to variety of data corruptions, measuring their generalization capabilities beyond conventional training conditions. Specifically, we investigate three key robustness scenarios: (1) direct corruptions applied images (Appendix I.3.3), (2) label noise (Appendix I.3.4). and (3) adversarial attacks (Appendix L..55 across different corruption intensities.
Additionally, we conduct series of ablation studies to analyze the impact of incorporating a Proxy Encoder within the GM MATCHING pipeline. These studies examine how changes in network architecture and distribution shifts between the pretraining distribution (proxy) and downstream tasks affect pruning efficacy. These experiments provide deeper insights into the role of the Proxy Encoder and its influence on the overall performance of Gm MATCHING.
We conduct experiments on widely used image classification benchmarks, including CIFAR-10/100 (Krizhessky 2009
32

---

Geometric Median (GM) Matching
Leffem
Easy
Herd
X
X0
20
(a) UNIFORM
(b) EASY
(c) HARD
Moderde
Perting
DM Hutrons
28
(d) MODERATE
(e) HERDING
(1 GM MATCHING
Figure 14: Toy Example: 45% % of the samples are corrupted i.c. drawn from adversary chosen distribution (red). We compare several basclines for choosing 10% samples: (UNIFORM) random sampling, (EASY) selects of samples closest to centroid. (HARd) Selection of samples farthest from centroid. (MODERATe) selects samples closest the median distance from the centroid. (HERDING) moment matching, (GM MATCHING) robust moment (GM) matching (6). Clearly Gm Matching is significantly more robust and diverse than the other approaches even at such high corruption rates.
Tmag-em [Le & Yang 2015), and ImageNet-1K (Deng al. 2009). Our study spans multiple popular neural network architectures, such as Res.ett- 18/50 (He et 2016. V6G-16 (Simonyan & Zisserman 2014). ShuffleNet (Ma 2018).
SENet (Hu al. 2018), EfficientNet-B0 Tan & Le 2019). and VITS (Dosovitskiy
2020
Lee et al. 2021).
For CIFAR- 10/100 datasets, the training configuration consists of batch size of 128, SGD optimizer with momentum (0.9). weight decay of 5 x 10 10-4, and an initial learning rate of 0.1. The learning rate undergoes step-wise decay by factor of
at epochs 60, 120, and 160, totaling 200 epochs. Data augmentation strategies incorporate random cropping and random horizontal flipping.
For Tiny-ImageNer and ImageNet- 1k experiments, we use batch size of 256, SGD optimizer with momentum (0.9), weight decay of 10-4, and initial learning of 0.1. The learning decreases by a factor of 10 at epochs 30 and 60, across 90 total epochs, employing random horizontal flipping for data augmentation.
For computational practicality, particularly due to the scale of datasets and the complexity of geometric median computation, we employ the approximate Weiszfeld solver (Algorithm 2 for estimating the GM. Specifically, to further enhance computational efficiency without significant performance compromise, the solver computes the median over randomly selected subset consisting of 50% of the training data points.
To account for variability and ensure statistical robustness, each experimental configuration is independently replicated across five distinct random seeds. Performance metrics reported with variance to transparently capture and reflect the consistency of each method.
1.3.2. IDEAL (No CORRUPTION) SCENARIO
Our initial set of experiments evaluates the effectiveness of different data pruning strategies under an ideal, uncorrupted set- ting. We systematically prune datasets at selection ratios ranging from 20% to 80%, assessing the downstream classification performance across two widely used benchmarks: CIFAR- 100 and Tiny ImageNet. The corresponding results, presented
33

---

Geometric Median (GM) Matching
Naneaaiigg lavel
Paymea geil sanes
(a) =1
(b)
(c) =5
(d)
Figure 15: POLYNOMIAL KERNEL: GM MATCHING experiments under 20% corruption using a polynomial kernel. Sub-figures (a)-(d) illustrate the effect of varying the polynomial degree (1, 3, 5, and 10, respectively) on the kernel mapping performance. The comparison highlights how increasing the degree can influence robustness and representational capacity in corrupted settings.
ImageNett Net-
Method / Ratio
60%
70%
80%
90%
100 %
Mean
Random
87.91 + 0.37
88.63 + 0.95
89.52 = 0.73
89.57 = 0.60
90.86 = 0.71
89.30
Herding
88.25 2.16
88.81 1.06
89.60 + 0.58
90.41 + 0.33
90.86 + 0.71
89.59
Forgetting
88.83 0.92
89.81 0.97
89.94 0.26
90.41 0.58
90.86 + 0.71
89.97
GraNd-score
88.48 1.73
89.82 2.07
89.94 0.81
90.41 0.62
90.86 = 0.71
89.90
EL.2N-score
88.48 + 2.81
89.82 + 1.14
90.34 0.87
90.57 0.46
90.86 + 0.71
90.01
Self-sup--selection
87.59 + 2.61
89.56 1.97
90.74 0.27
90.49 = 0.98
90.86 = 0.71
89.49
Moderate-DS
89.23 + 0.96
89.94 0.74
90.65 + 0.51
90.75 = 0.35
90.86 + 0.71
90.29
GM Matching
90.28 + 0.38
90.54 + 0.19
90.72 = 0.26
90.84 = 0.32
90.86 = 0.71
90.65
Table 4: (Clean) IMAGE CLASSIFICATION; Downstream Test Accuracy (Top-5) (%) of a ResNct-50 trained on 60%, 70%, 80%, and 90% subset of ImageNet-Ik, Ik, where the subset is selected via several benchmark data pruning algorithms(Appende The best result in each case is in bold.
I
in T demonstrate that despite heing designed with robustness-orientedd applications in mind, GM MATCHING surpasses existing strong baselines even in the standard, clean setting. Across both datasets, Gm MATCHING achieves an average improvement of over 2% compared to prior methods. Notably, its performance gains are particularly pronounced in the low-data selection regime (20%-40%) where it significantly outperforms competing pruning techniques. In Table 4 observe similar improvements with Gm MATCHING on ImageNet-IK, lk. This suggests that Gm MATCHING is especially effective in scenarios where data efficiency is critical, making promising approach for resource-constraine settings.
1.3.3. ROBUSTNESS TO IMAGE CORRUPTION
In real-world applications, machine learning models are often deployed in environments where the input data is imperfect, degraded, or subject to various forms of corruption. This degradation can stem from sensor noise, environmental conditions, transmission artifacts, or adversarial perturbations.
To systematically evaluate the robustness of data pruning strategies under such conditions, introduce structured image corruptions into the dataset and assess the downstream test accuracy across varying levels of pruning.
Specifically, we adopt the following practical perturbation types, drawing from established robustness bench- marks (Hendrycks & Dietterich 2019 Szegedy et al. 2013) as
Gaussian Noise: Models real-world sensor noise by adding random perturbations sampled from a standard normal distribution.
Random Occlusion: Mimics missing occluded regions in images by replacing random patches with black noisy pixels.
Resolution Reduction: Simulates low-quality images by applying aggressive down-sampling up-sampling. introducing
34

---

Geometric Median (GM) Matching
CIFAR-100
Method Seleccion ratio
20%
30% %
40 %
60 %
80 %
100 %
Mean 1
No Corruption
Random
50.26:43.24
53.61++2.73
1..7
71.03++0.75
74.12:40.56
78.1440..55
62.67
Herding
48.39:11.42
50.89:0.97
62.99:10.61
70.6110.44
04.2110049
18.14
61.42
Forgetting
3..57
49.83
59.65:2.50
73.34:10.39
77.50+0.53
78.14:10.55
59.18
Graod-score
1.365+
53.14+1.28
60.52+0.79
69.70+0066
74.67+00.9
78.14+0.55
60.14
EL2N-score
27.32.11.16
41.9810.54
50.47111.20
69.23.11000
75.96.10.88
78.14:10.55
52.99
Optimization-based
42.16:13.30
53.1942.14
58.93:10988
68.9310.770
75.62-10.33
18.14:10.55
59.77
Self-sup--
44.45+2.51
54.63+2.10
1.291
70.70+0.82
75.29=:0.45
14.1555.555
61.60
Moderate-DS
51.83:10.52
57.7941.61
64.92110.93
71.8710911
75.44
78. 14.0.55
64.37
GM Matching
55,93 0.48
63.08 0.57
66.59 1.18
70.82 0.59
74.63 0.86
78.14 0.55
66.01
5% Feature Corruption
Random
33.1443.04
54.1942.92
64.211:2.39
69.5011.006
72.90:0.52
77.26:10.39
60.79
Herding
4..50+1.27
53.88+3.007
60.54+00.4
69.15
73.47+0.89
77.26++0.39
59.81
Forgetting
32.42:10.74
19.72
54.8412.20
70.22:2.00
75.1910.40
77.26:10.39
56.48
GraNd-score
42.24:10.57
53.48110.76
1.617:11.66
69.16110.81
73.35-10.81
77.26:10.39
59.68
EL.2N-score
16.5
19.01+1.42
1..8
68.36:1.41
73.10+0.36
77.26+10.39
$1.30
Optimization--ased
38.2543.04
50.88-16.07
57.26:10.93
68.02-10.39
73.77:10.56
77.26-10.39
57.64
self-sup--selection
44.24:10.48
15.9
61.03++0.59
69.96+11077
74.56+1.17
77.26+00.99
61.16
Moderate-DS D
1.97
57.36+1.22
1..40=11.19
71.46#0.19
75.64+0.61
77.26+00.99
63.33
Gm Matching
0.750
60.23
66.25
72.91
75.10:10.29
77.26:10.39
64.80
10% % Feature Corruption
Random
43.27443.01
53.9442.78
62.17:::11 .229
68.41+1.21
73.5010.73
76.50110.33
60.26
Herding
1.07
13.31
60.13:10.38
68.2010.77
1..34+1.07
76.50110.63
60.06
Forgetting
30.43+00.70
4..50++.443
53.16++0.44
70.36++0.82
75.11+0.71
76.50++0.63
55.31
GraNd-score
36.36.11.06
52.26110.66
60.22:11.39
68.96110.22
72.78-0.51
76.50110.3
58.12
EL2N-score
1.57
30.80+2.223
11.06:11.23
64.82.1148
1..4
76.50-10.63
46.38
Optimization-based
37.22-10.39
48.92+1..8
56.88+1.48
67.33+2.115
7..94+1.90
76.50+00.3
56.68
Self-sup--sllcttinn
42.01111.31
54.47-11.19
61.37-10.68
68.52-11.24
74.73.10.36
76.50-10.63
60.22
Moderate-Ds DS
47.02+0066
11.60
62.18 1.86
71.83=0.78
7..66+0066
76.50+10.3
62.46
GM Matching
1.08
60.15:10.43
6.292-10.28
72.03+10.38
73.71+:0199
76.50+1063
64.33
20 %
Feature Corruption
Random
1..99
50.38++1.39
57.24-1:0.65
65.21++1.31
71.744-0.8
74.92+-0.88
57.11
Herding
44.42:10.46
53.5740.31
60.72 1.78
69.09
73.0810.98
74.9241088
60.18
Forgetting
26.39110117
40.78+1202
49.95.12.31
65.71111.1
73.67+1.12
74.92-10.88
51.30
GraNd-score
36.33+2.66
16.21+11448
55.51=10.76
64.59+2.400
70.14+1.36
74.92+10.88
54.56
EL2N-score
21.6412.03
23.78.11.66
35.71111.17
56.32-10.86
69.66.10.33
74.92-10.88
41.42
Optimization-bused
1..42-11.60
45.37-1281
54.06.11.74
65.19:11.27
70.06.10.83
74.92-10.88
$4.42
42.61+2..44
54.04++1.90
59.51
68.97+0.96
72.33++0.0
74.92+00.8
60.01
Moderate-DS
42.98-10.87
55.80-10.95
61.84
70.05
73.6740.30
74.92-10.88
60.87
GM Matching
47.124:0.64
59.17-10.22
63.45:10.4
71.7011..0
1.06
74.92-10.88
63.21
Table 5: Image Corruption ( CIFAR 100 ): Comparing (Test Accuracy) pruning methods when 20% of the images are corrupted. 5e is used both proxy and for downstream classification.
35

---

Geometric Median (GM) Matching
Tiny ImageNet
Method Ratio
20%
30%
40%
60% %
80 %
100%
Mean 1
No Corruption
Random
24.02++0.41
29.79+0.22
34.41=0.46
40.96-+0.47
45.74+0061
49.36+0.25
34.98
Herding
24.09::0.45
29.39110.53
34.13=20.7
40.86:10.61
45.45=10.3
49.36=:0.25
34.78
Forgetting
22.37:10771
28.67:20.54
33.64:1.322
41.14410.3
46.77:10.11
49.36=:0.25
34.52
GraNd-score
23.56::0.52
29.66:10.37
34.33=0.50
40.77=1042
45.96=10.56
49.36:0:25
34.86
EL2N-score
19.74
26.58=10.40
31.93=0.28
39.12:10.46
45.32+:.27
49.36=:025
32.54
Optimization-basee
13.88+22.17
1..75+1.62
29.77=00.4
37.05+22.81
43.76++1.50
49.36=t0.25
29.64
Self-sup--ellctioon
20.89:10.42
27.66+0.50
32.50=0.30
39.6411.39
44.94+0.34
49.36:0.25
33.13
Moderate-DS
25.29:40.38
30.57++.220
34.81
41.45-+0.44
46.06++0.33
49.36
35.64
GM Matching
27.88
0.225
36.92 0.40
42.48
46.75+00551
49.36+0.25
37.44
5% Feature Corruption
Random
23.51
28.82:10.72
32.61=0.68
39.77=1035
44.37+0.34
49.02::0.35
33.82
Herding
23.09:1.533
28.67=0.37
33.09=0.32
39.71+0.31
45.04
49.02:0.355
33.92
Forgetting
2..26
27.72+00.3
33.45+0.21
40.92++0.55
45.99+0.51
49.02+0.35
33.89
GraNd-score
22.47:10.23
28.85+10.83
33.81=0.244
40.40+10.15
44.86+10.49
49.02+0035
34.08
EL2N-score
18.98
2..96
31.07=0.63
38.6540.36
44.21
49.02+0.35
31.77
Optimization-basee
13.65++1226
1..02++1.35
19.65+1.86
36.55+1.84
43.6440.71
49.02+0.35
29.50
19.35:0.57
26.11
31.9011.37
38.9140.29
44.43-:0.42
49.02
32.14
Moderate-DS
24.6311077
30.27:0.16
34.84.10224
40.86:10.22
45.60+0031
49.02
35.24
Gm Matching
27.46:1.22
33.1410..1
35.76=1.114
41.62
46.83+0.56
49.02
36.96
10 % Feature Corruption
Random
22.67+0..7
28.67+00.52
0..3
38.63++0.36
43.46++0.20
48.40+00.32
33.06
Herding
20.01
27.82+0.11
31.82:10.26
39.37=0.188
44.18:10.7
48.40:10.2
33.04
Forgetting
20.06:10.48
27.1740..6
32.21-10.22
40.19-1.29
45.51
48.40-10.2
33.05
GraNd-score
2..52++0.48
26.98-40.43
32.70+0.19
40.03-+0.26
44.87+0.35
48.40-40.22
33.22
EL2N-score
18.5910.13
25.2340.18
30.37=0.22
38.4410.32
44.32+11.07
48.40:0.32
31.39
Optimization-baser
14.05=:1.74
19.18
29.1220.61
36.28+1.88
43.52+0.31
48.40=10.2
29.03
Self-sup--selctioon
19.47:0.26
26.51
31.7810.14
38.8710.54
44.69:10.99
48.40:0.32
32.26
Moderate-DS
23.79:10.16
29.56110116
34.60-0.12
40.3611.27
45.10
48.40:1.32
34.68
GM Matching
27.4140.23
32.84
36.27=0.68
41.85++0.29
46.35-10.44
48.40+00.22
36.94
20% % Feature Corruption
Random
19.9910.42
25.93
30.83=1.44
37.98-10.31
42.96-L0.62
46.68+0.43
31.54
Herding
19.46:10.14
24.3
29.72-0.39
37.50+0.59
42.28+00.00
46.68=0.43
30.86
Forgetting
18.4710.46
25.5310.23
31.17-0.24
39.35110.4
44.55-10.67
46.6810.43
31.81
GraNd-score
20.07:10.49
26.68:10.40
31.25=:0.00
38.2110.49
42.8440.72
46.6810043
30.53
EL22-score
18.5740.30
24.42:10.44
30.04:0.115
37.62-10.44
42.43::0.61
46.68=10.3
30.53
Optimization-basee
13.7140.26
23.33++1.84
29.15+2.84
36.12+1.86
42.94+-0.52
46.88+0043
29.06
Self-sup--selection
20.22+10.3
26.90+1..50
31.93:10:49
39.74+1.552
44.27+10.10
46.68+0043
32.61
Moderate-DS
23.27-10.3
29.06
33.48-0.11
40.07+0.36
44.73+0.39
46.68:1043
34.12
GM Matching
27.19-10.92
31.70.L0.78
35.14
42.0440.311
45.12-10.28
46.68+1043
36.24
Table 6: Image Corruption Tiny ImageNet ): Comparing (Test Accuracy) pruning methods under feature (image) corruption. ResNet-50 is used both as proxy and for downstream classification.
36

---

Geometric Median (GM) Matching
CIFAR-100 (Label noise)
Tiny ImageNet (Label noise)
Method Ratio
20%
30%
20%
30%
Mean
20% Label Noise
Random
34.47.10.64
43.26.11.21
17.78.10.44
23.88.10.42
29.85
Herding
42.2911..75
50.52.13.38
18.9811.44
24.23.10.29
34.01
Forgetting
36.53.11.11
45.78.11.04
13.20.10.38
21.79:10.43
29.33
GraNd-score
31.72:+0.67
42.80=0.30
18.28+0.32
23.72=+0.18
28.05
EL2N-score
29.82+1.119
33.62::2.35
13.9310.69
18.57=0031
23,99
Optimization- based
32.79-10662
1..80:1.144
14.7740.95
22.52:+0.77
27.57
Self-sup--slecctoon
31.08:1-0.78
41.87+10.6
15.10:10.73
21.01+0.366
27.27
Moderate-DS
40.25:+0.12
1.65
19.64+0..0
24.96++0.30
31.33
GM Matching
52.64410.72
61.01+0.447
25.80++0.37
31.71++0224
42,79
35% Label Noise
Random
24.51+1.34
32.26++0.8
14.64+00.29
19.41+0.45
22.71
Herding
29.42+1.554
37.50+2.12
15.14+0..45
20.19+00.45
25.56
Forgetting
29.48.11.98
38.0112.211
11.25.10.00
17.07-10.66
23.14
GraNd-score
23.03.11.05
34.83:12.01
13.68110.46
19.51
22.76
EL2N-score
21.95.11.08
31.63.12.84
10.11:10.25
13.69.10.32
19.39
Optimization-baser
26.77=t0.15
35.63+0.92
12.37+0.68
18.52+00.0
23,32
Self-sup.-sche seleccion
23.12+11447
34.85+00.68
11.231+.32
17.76=00669
22.64
Moderate-DS
28.45:+0.53
36.55+1.226
15.27+0.31
20.33::0.28
25.15
Matching
43.33:1 1.02
58.41 0.68
23.14 0.92
27.76 0.40
38.16
Table 7: Robustness Label Noise: Comparing (Test Accuracy) pruning methods CIFAR-100 and TinyImageNet datasets, under 20% and 35% Symmetric Label Corruption, 20% and 30% selection ratio. ResNet-50 used both as proxy and downstream classification.
pixelation artifacts.
Fog: Emulates atmospheric distortions by overlaying simulated fog effect resulting in reduced contrast and visibility,
Motion Blur: Models dynamic distortions caused by camera motion moving objects during exposure.
To introduce diverse corruption across the dataset while ensuring balanced distribution, apply each corruption type uniformly at random to the corrupted samples. Instead of assigning fixed partitions, this approach ensures that each sample has an equal probability of being affected by any of the five corruption types. This stochastic allocation results in heterogeneous mix of corruptions, compelling models to generalize across multiple degradation patterns rather than overfitting to specific type distortion.
The results of our experiments, presented in Tables and 6 evaluate the impact increasing corruption levels (5%, 10%, and 20%) various pruning methods. Across both CIFAR-T00 and Tiny ImageNet, Gm MATCHING consistently outperforms all baselines, achieving average accuracy improvement of ~ 3% over the next-best approach.
This performance gap is amplified at higher corruption levels, where Gm MATCHING maintains superior test accuracy. Moreover, the gains are also significant at aggressive pruning ratios (20%-40%) where GM MATCHING improves test accuracy by 2-4% over baselines. This trend aligns with its strong performance in data-scarce settings, reinforcing its ability to preserve robustness even when training data significantly reduced.
Among baselines, Random Selection exhibits steady performance drop with increasing corruption, confirming its inability to retain robustness. Herding and Moderate-DS. while effective in standard settings, struggle under high corruption levels. Forgetting and appimizatiionbassel methods show inconsistent results, likely due to their reliance on training dynamics that become unstable when corrupted samples are introduced. GraNd-score and EL2N-score, which prioritize loss-based selection, perform well in clean settings but degrade significantly under corruption, suggesting vulnerability to adversarial perturbations. Self-supervised Selection remains competitive but fails to match Gm MATCHING, particularly at higher corruption intensities.
37

---

Geometric Median (GM) Matching
Tiny ImageNet (Label Noise)
Method Ratio
20%
30%
40 %
60% %
80 %
100%
Mean t
Random
17.78:1044
23.88:1:0:2
27.97=1.339
34.88:10.51
38.47:0.400
44.42:10.47
28.60
Herding
18.98=0.44
24.23:1.229
27.28=0.31
34.36::0.29
39.00=10.49
44.42:10.47
28.87
Forgetting
13.20=0.38
21.79-+:0:3
27.89=#022
36.03+40.24
40.60=10.11
44.42:10.47
27.50
GraNd-score
18.28=0.32
23.72+10.18
27.34=0.33
34.91=0.119
39.45=0.45
44.42:10.47
28.34
EL2N-score score
13.93:10.69
18.57:0.31
24.56-0.34
32.14:10.49
37.6410.41
44.42:10.47
25.37
Oplimization-aane -ased
14.77++0.95
22.52++0.77
25.62
34.18:40.79
38.49-0.69
44.42+40.47
27.12
Self-sup.-selectee -election
15.10=10.73
21.01=10.36
26.62=0.22
33,93:10.66
39.22=0012
44.42::0.47
27.18
Moderate-DS
19.64=1.40
24.96:10.30
29.56=0.21
35.79:10.36
39.93=0.23
44,42:10.47
30.18
GM Matching
25.80++0.37
31.71+-0.24
34.87+0.21
39.76++0.71
41.944...3
44.42+40.47
34,82
Table 8: Pruning with Label Noise (TinylmageNet): Comparing (Test Accuracy) pruning methods under 20% Symmetric Label Corruption across wide array of selection ratio. ResNct-50 is used both as proxy and for downstream classification.
1.3.4. ROBUSTNESS TO LABEL CORRUPTION
Next, we consider label noise- prevalent issue in real-world datasets, where obtaining perfectly annotated data impractical due to human labeling errors, dataset aggregation inconsistencies, or adversarial data manipulations, Consequently. it is crucial to assess the ability of data pruning methods to select informative samples while filtering out mislabeled examples, ensuring robustness to noisy annotations.
To systematically evaluate pruming methods under label noise, we introduce synthetically injected symmetric label noise, a widely used corruption paradigm in robust learning (Li ct al. 2022 Patrini et al. 2017 Xia et al. (2020). In this setting, a fraction of training labels is randomly flipped different class, simulating annotation errors encountered in large-scale weakly labeled datasets. We experiment with two corruption levels (20% and 35% label noise) and report test accuracy across different pruning ratios.
Interestingly, in both CIFAR-100 and Tiny ImageNet, training ResNet50 in subset selected by Gm MATCHING outperforms all competing methods by large margin Table 78 For instance, at 20% label noise, when selecting 30% of samples from CIFAR-100, Gm MATCHING achieves 61.01% % accuracy, compared to 48.53% (Moderate-DS) and 45.78% (Forgetting). At 35% label noise, the performance gap widens, with Gm MATCHING achieving 58.41 %, while the closest baseline (Moderate-)e -DetatteeDDDaeee lags behind at 36.55%. Similar trends hold for Tiny ImageNet, where GM MATCHING outperforms the best baseline by 4-6% across different noise levels. Overall, on average Gm MATCHING outperforms the baselines by 12% % when selecting small 20- 30%. Moreover, when Vision Transformers trained on 20% subset of CIFAR-10 data chosen by GM MATCHING, they achieve = 10% improvement over previous robust data selection algorithms (Table
Since mislabeled examples originate from random class assignments, they tend to be spatially dissimilar from their intended class distributions. As result, Gm MATCHING is less likely to select such noisy examples, leading to improved generalization despite high noise levels.
1.3.5. ROBUSTNESS TO ADVERSARIAL ATTACKS
Adversarial attacks pose fundamental challenge the reliability of deep learning models, as they introduce imperceptible but highly effective perturbations to input samples, forcing misaligned predictions (Szegedy al. 2013 Huang et al. 2010).
To assess the robustness of data pruning methods in adversarial settings, we experiment with two widely used attack techniques:
Projected Gradient Descent (PGD) (Madry et al., (017):: A strong iterative attack that optimizes perturbations by taking multiple gradient ascent steps, maximizing the model's loss function.
Gradient Sign Attack (GS) Goodfellow et al. gradient of the loss function, often serving as a computationally efficient alternative to PGD.
2014): A single-step adversarial attack that perturbs the input along the
Using these attack methods, we generate adversarial examples from models trained on CIFAR- and Tiny ImageNet. We then apply different data pruning strategies to these adversarial datasets and retrain models on the curated subsets to analyze
38

---

Geometric Median (GM) Matching
CIFAR-100 (PGD Attack)
CIFAR-100 (GS Attack)
Method Ratio
20%
30%
20%
30%
Mean f
Random
13.23++0.11
02.86=0.34
44.2340041
03.4440.44
48.44
Herding
40.21=+0.72
09.62=#0.65
39.92++.003
50.14+0.15
44.97
Forgetting
35.90 1.30
47.37=0.99
37.55+0.53
46.88+1911
41.93
GraNd-score
40.87110.84
50.1310.30
40.7711.111
49.8810.83
45.41
EL2N-score
26.61-10.58
34.50.11.02
26.72.10.66
35.55
30.85
Optimization-based
38.29411.77
1.825:11.82
41.36.10.92
49.10:10.81
43.75
self-sup.-see -ss-eectnntn
1.15
09.95==0.50
10.74+1166
01.23:
45.61
Moderate-DS DS
43.60=10.97
51.66=0.339
44.69-1.66
53.71
48.42
Gm Matching
45.41 +0.86
51.80 1101
49.78 10.27
55.50 10.31
50.62
Tiny ImageNet (PGD Attack)
Tiny ImageNet (GS Attack)
Method Ratio
20%
30%
20%
30%
Mean
Random
20.93.10.30
26.60.10.98
22.43.10.31
26.89110.31
24.21
Herding
21.61
25.95:10.19
23.04.10.28
27.39110.14
24.50
Forgetting
20.38:10.47
26.12.10.19
22.06.10.31
27.21
23.94
GraNd-score
20.76++0.21
26.3410.32
22.56=t0.30
27.52=00440
24.30
EL2N-score
16.67=00.2
22.36=0.42
19.93=#0.57
24.65=+0.32
20.93
Optimization-basee based
19.26=:0.77
24.55=0..2
21.26::0.24
25.88
22.74
Self-sup--slecctong
19.23-400.46
23.92+0.51
19.70-H0.20
24.73++0.39
21.90
Moderate-DS
21.81+00.37
27.11+0.220
23.20++0.13
28.89+0.27
25.25
GM Matching
25.98 +1.12
30.77 +0.25
29.71 +0.45
32.88 +.7.3
29.84
Table Robustness to Adversarial Attacks. Comparing (Test Accuracy) pruning methods under PGD and GS attacks. ResNet-50 used both proxy and for downstream classification.
their effectiveness in retaining robustness. The results with ResNet-50 are summarized in Table 9 and the experiments with ViT are presented in Table I0
Similar to other corruption scenarios, across both datasets and attack types, Gm MATCHING consistently outperforms all baseline pruning methods, yielding an average accuracy improvement of 3% over the next-best approach. Specifically, under PGD attacks on CIFAR- 100, Gm MATCHING achieves 45.4 % accuracy 20% selection, compared to 43.60% (Moderate-DS) and 40.87% (GraNd-score). Similarly, in Tiny ImageNet under GS attacks, Gm MATCHING maintains the highest mean accuracy of 29. 84%, outperforming Moderate-DS (25.23 (25.25%) and Self-supervised Selection (21.90%).
1.3.6. ABLATIONS WITH PROXY ENCODER
Since the input features (e.g, images) often reside on non-separable manifold, data pruning strategies rely on proxy models to map raw input samples into a separable embedding space, where importance scores can be assigned more effectively.
A. IDEALIZED SETTING In the standard setting, the proxy model used for sample selection identical to the model used for downstream training both in terms of architecture and dataset. This represents an idealized scenario, where the feature representations used evaluate sample importance remain consistent throughout training. Since the proxy and final models are identical, performance differences between pruning methods directly reflect the effectiveness of sample selection, rather than being confounded by architectural mismatches. Since no external factors (such as domain shifts) interfere, the results from this setup serve as benchmark for understanding the best-case scenario for sample selection.
All the experiments reported in Tables 5 9 ImageNet, using ResNet-50 as both the proxy model (for selecting samples) and the downstream classifier (for final training). The proxy model assigns importance scores to training samples, and a subset selected accordingly. new ResNet-50 then trained from scratch on the pruned dataset, ensuring that information leakage occurs between sample selection and final training. This methodology remains consistent across clean data, label noise, feature corruption, and adversarial attack settings, providing a direct comparison of how pruning strategies perform across diverse learning conditions.
follow this framework: We perform data pruning on CIFAR-100 and Tiny
By maintaining this controlled setup, we isolate the true impact different pruning strategies, ensuring that their ability to retain the most valuable and generalizable training samples is the sole factor influencing performance. This establishes a strong foundation before extending the analysis to more complex settings involving distribution shifts and network
39

---

Geometric Median (GM) Matching
CIFAR-100 (ViT-S)
Method
No Corruption
Noisy Feature
Label Noise
Ady. Attack
Mean 1
Random
33.80++0.54
31.29=#0.61
26.67+0.54
31.01+0445
30.19
Herding
32.1610.37
31.75=0.22
32.27=0.53
31.28=0.66
31.37
Forgetting
33.52.10.73
24.45=0.229
26.24:11007
28.26=11995
28.12
GraNd-score
22.49+00.47
18.40+0.111
22.13+0.90
19.27++1.27
20.07
EI EI.2N-ccoee
26.15+0.21
23.27+0068
24.80++0.72
20.26++1668
23.12
Optimization- based
31.8410.63
30.1211..33
30.12::0.70
29.3610.75
30.36
Self-sup.-sedee -
33.35+0031
30.72+1090
29.16::0.27
28.49
30.93
Moderate-DS
34,43+0.32
02.33+00335
31.86+00499
32.61+0.40
32.91
GM MATCHING
40.81
38.26-0068
42.11++0.66
39.45+0.82
40.66
Table 10: IMAGE CLASSIFICATION (VIT-S): We compare the downstream test accuracy of various data selection methods simulated CIFAR- 100 (using ViT-S) under different corruption types: No Corruption, Noisy Feature, Label Noise, and Adversarial Attack. experiments are performed with a fixed selection ratio of 20%, using ResNet-50 as both the proxy and downstream classifier. Our method, GM MATCHING, consistently outperforms all seeelies--dmmonstee gains at higher corruption levels. Mean and standard deviation (%) are reported over multiple runs. The best result in each case is highlighted hold.
superior robustness to corrupted data, with larger performance
ResNet-50-SSEN
Method Ratio
20%
30%
20%
30%
Mean f
Random
34.13
39.5
32.88+1.552
39.11
36.42
Herding
34.86+0.55
38.60
32.21+1.54
37.53+0.22
35.80
Forgetting
33.40:10.64
39.79-10.78
31.12::.21
38.38:00.65
35.67
GraNd-score
35.12::0.54
41.14::0.2
33.2010.67
40.02:10.35
37.37
EL2N-score
31.08:t1.11
38.26110.45
31.34110.49
36.88=0.32
34.39
Optimization- based
33.18::0.52
39.42:1.777
32.1610.90
38.52:1..00
35.82
Self-sup--selcction
31.74=10771
38.4510.39
30,9
37.96:10.77
34.79
Moderate-DS
36.04=1.115
41.40:1..0
34.26110.48
39.57=:0.29
37.82
GM Matching
37.93110.23
42.59
36.3110.67
41.03:10.41
39.47
Table 11: NETWORK TRANSFER (No CORRUPTION) PROXY ENCODER: (Tiny-ImageNet) Model Transfer Results. A ResNet-50 proxy is used to find important samples which are then used to train SENet and EfficientNet.
mismatches.
However, critical question remains:
How well do samples selected by proxy model generalize when trained on a different architecture or dataset
In real-world applications, the model used for data selection (proxy model) is often different from the final model used for training due to hardware constraints, deployment considerations, domain shifts. An ideal pruning strategy should ensure that the selected subset remains highly effective, when the final model differs from the used during selection.
To investigate this, we perform comprehensive ablation studies across multiple proxy selection scenarios, evaluating the robustness to distribution shifts and network mismatches i.c. to say that samples selected via proxy network should generalize well when trained on unseen (during sample selection) networks domains.
B. GENERALIZATION TO UNSEEN NETWORK: this setting, the proxy model and downstream classifier are trained on the same dataset, meaning there is no distribution shift. However, the proxy model's architecture differs from the final training model, testing whether pruned subset remains useful across different network designs. This scenario simulates practical constraints where proxy model is used for data selection, but the final model needs to be optimized for different architectural properties (e.g., mobile-friendll architectures).
In Table II we use a ResNet-50 proxy trained on TinyImageNet (no corruption) to select samples from the same dataset for downstream training. Instead of using ResNet-50 for final training, we train with different architectures on the pruned subset:
40

---

Geometric Median (GM) Matching
ResNet-50-> VGG-16
ResNet-50-1 ShuffleNet
Method Ratio
20%
30%
20%
30%
Mean
No Corruption
Random
29.63-+0443
35.38+00.83
32.40+1.00
39.13+0.81
34.96
Herding
31.05=+0.22
36.27+0.57
33. 10:30.9
38.65+0.22
35.06
Forgetting
27.53+0.36
35.61
27.82++0.56
36.26+t.51
32.35
GraNd-score
29.93:10.95
35.61
29.56.10:46
37.40-10.38
33.34
EL2N-score
26.47:10.31
33.1910.51
28.18:10.27
35.8111.229
31.13
Optimization-based
25.92.10.64
34.82.1..29
31.37-11.14
38.22.10.78
32.55
Self-sup.-seele selecciio
25.16=t1.10
33.30
29.47=00.56
36.6810..6
31.45
Moderate- DS
31.45=:0.32
37.89-0.33
33.32++0.41
39.68:10.34
35.62
Gm Matching
35.86:10.41
40.56:10.22
35.51+0.32
40.30+0..8
38.47
20 % Label Corruption
Random
23.29:11.12
28. 18:
25.08 1.32
31.4411.21
27.00
Herding
23.99:10.36
28.57=0.40
26.25=10447
30.7310.28
27.39
Forgetting
14.52+00.66
21.75++0.23
15.70+0..29
22.31+:0.55
18.57
GraNd-score
22.44+00446
27.95+0.29
23.64+:0.10
30.85+0.21
26.22
EL2N-score
15.15=11.25
23.36++0.30
18.0140.444
24.68+10.44
20.30
Optimization-based
22.93.10.58
24.92.12.50
25.82.11.70
30.19.10.48
25.97
Self-sup--selection
18.39111.30
25.77
22.87.10.54
29.80-10.36
24.21
Moderate-DS
23.68.1..19
18.93.1..19
28.82-10.33
32.3911.211
28.46
GM Matching
28.77:0.77
34.87=0.223
32.05++0.93
37.43+0.22
33.28
20% Feature Corruption
Random
26.33.10.88
31.57:11.31
29.15-10.83
34.72.1..00
30.44
Herding
18.03310.33
25.77
23.33+:0:43
31.73110.88
24.72
Forgetting
19.41=0.57
28.3540.16
18.4440.57
31.0910.61
24.32
GraNd-score
23.59:10.19
30.6910.13
23.15:00.56
31.5810.95
27.25
FI NN-oore
24.60+40.81
31.49+00.3
26.62++0.34
33.91+0.56
29.16
Optimization-based
25.12+0..4
30.52+0.89
28.87++1.25
34.08+1.92
29.65
Self-sup--selection
26.33++0.21
33.23++0.26
26.48++0.37
33.54+10.46
29.90
Moderate-DS
29.65.10.68
35.89.10.53
32.30110.38
38.66.10.29
34.13
GM Matching
33.45.1.022
39.46.10.44
35.14
39.89-10.98
36.99
PGD Attack
Random
26.12.11.00
31.98
20.98
34.59.1.118
30.24
Herding
26.76.10.59
32.56.10.35
28.87-10.48
35.43.10.22
30.91
Forgetting
24.55
31.83.10.36
23.32-10.37
31.82.10.15
27.88
GraNd-scom score
25.19:10.33
31.46+0.554
26.03-10.66
33.22+0.24
28.98
EL22-score
21.73:10.47
27.66+10.32
22.66+10.35
29.8911064
25.49
Optimization based
26.02=10.36
11.64
27.93+0047
34.82+0.96
30.10
Self-sup--selecteee selecctinn
22.36-+0.30
28.56++0.50
25.35++0.27
32.57+0..1
27.21
Moderate-DS
27.24+00.66
32.90+00.11
29.06--0.28
35.89+0.53
31.27
Gm Matching
27.96+11660
35.76+10.82
34.11+0.65
40.91+10.84
34.69
Table 12: NETWORK TRANSFER (CORRUPTED) PROXY ENCODER: A ResNet-50 proxy (pretrained TinyImageNet) used
find important samples from TmageenageNet; which is then used 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.

---

Geometric Median (GM) Matching
90
80-
70-
60-
Accurasy
Accuracy
Accuracy
40
40-
60
40-
Ratile
20-
30-
500
5050
50 1000
Samples Category
Samples Category
Samples/ Category
(a) No Corruption
(b) 20% Label Noise
(c) 40% Label Noise
Figure 16: DOMAIN TRANSFER ( IMAGENET-IK - CIEAR-10 ) PROXY ENCODER: CIFARIO, corrupted with label noise pruned using (proxy) ResNet-18 18 pretrained on ImageNet-Ik. A ResNet-18 18 is trained from scratch on the subset. We compare our method GM MATCHING with geometric pruning baselines: UNIFORM. EASY,HARD, MODERATE, HERDING.
SENet model optimized for channel-wise attention mechanisms, which enhances feature selection by adaptively recalibrating channel-wise responses.
EfficientNet-BO - A lightweight model designed for mobile and resource-efficient inference, using combination of depthwise convolutions and width scaling to optimize performance while maintaining parameter efficiency.
VGG-16 A deep convolutional network with uniform architecture, known for its simple yet effective design, using fixed-size convolution filters and max pooling layers.
ShuffleNet A model specifically designed for speed and efficiency, utilizing group convolutions and channel shuffling to maximize accuracy while maintaining low computational overhead.
In Table 12 we also experiment with similar network mismatch scenarios, in the presence of various types and levels of corruption.
Both sets of experiments demonstrate that Gm MATCHING consistently outperforms all pruning baselines, ensuring that selected samples remain informative and transferable across different network architectures. SENet and EfficientNet-Bl benefit the most from pruning, likely due to their adaptive feature recalibration and efficiency optimizations, while VGG- 16 and ShuffleNet show greater sensitivity to pruning and corruption, struggling more under distribution shifts. Under corruption, loss- based selection methods (GraNd, EL2N) degrade significantly, whereas representative selection methods (Moderate-De DS, Herding) hold up better under mild corruption but fail under severe noise.
These results highlight the importance of selecting subsets that generalize well, not only across different architectures but also under varying levels of corruption, reinforcing Gm MATCHING as a highly robust and adaptable pruning strategy suitable for diverse deployment scenarios.
C. GENERALIZATION TO UNSEEN DOMAIN.
In many real- woal-world applications, deep learning models are pretrained on large-scale datasets (e.g., ImageNet) before being adapted to a different, often smaller, target dataset (c.g., 1IFAR-10). This introduces distribution shift between the dataset used for proxy-based based sample selection and the dataset used for final training. a pruning method truly effective, should be able to identify samples that generalize well across different data distributions, ensuring that the selected subset remains informative even if the proxy model was never explicitly trained on the target dataset.
To investigate this, conduct experiments where the proxy model and downstream classifier share the same architecture, but the proxy model is pretrained on different dataset, introducing a distribution shift. By keeping the architecture constant, we isolate the impact of dataset shift while avoiding confounding factors related to network differences.
In Figure 16 a ResNet-13 18 pretrained on ImageNet is used to select samples from CIFAR-10, which are then used to train a new ResNet-15 18 from scratch. This setup closely mirrors real-world transfer learning scenarios, where targe-scale pretraining leveraged to prune or curate training data for a smaller, domain- -specffcc dataset before training a new model. The key
42

---

Geometric Median (GM) Matching
85.0
$2.5
Accuracy (50)
60-
Accuracy (%0
-0-
Accuracy
77.5-
13-
75.0-
72.6
70.0
Emg
Eag
67.5
Day
65
65
00 000
2000
65.0
00
000
1000
2000
Samples/ Cattggry
Samples/ Category
Samples: Category
(a) No Corruption
(b) 20% Label Noise
(c) 40% Label Noise
Figure 17: DOMAIN TRANSFER (IMAGENET-IK -> R-FAR-10 PROXY ENCODER: We train Linear Classifier on CIFARIO. over embeddings obtained from a frozen ResNet-18 18 pretrained on ImageNet- Ik. The dataset was pruned using the same encoder. We compare Gm MATCHING with several geometrie pruning baselines (Appendix III: Uniform, Easy, Hard, Moderate, Herding across no corruption, 20% and 30% label noise settings.
objective is to determine whether the subset selected by a proxy trained on different dataset remains informative and structurally representative of the target dataset when used for full downstream training.
Furthermore, in Figure 17 we introduce an even more challenging setting by freezing the pretrained (on ImageNet) ResNet- 18 and training only a linear classifier on top of the extracted CIFAR-10 features. Unlike the full fine-tuning approach, this method eliminates any feature adaptation between datasets, forcing the classifier to rely entirely on the quality of the selected samples. This makes it a more rigorous test of how well the pruned subsets inherently align with robust, transferable representations, ensuring that the selected data itself is informative, rather than merely benefiting from feature adaptation during training.
The results from Figure 17 demonstrate that Gm MATCHING consistently outperforms all baselines, ensuring that selected samples remain highly informative and transferable despite the distribution shift. When fully fine-tuned, models trained on GM MATCHING pruned subsets achieve higher accuracy than those trained on subsets selected by other methods, indicating that it effectively identifies structurally important and generalizable samples. In the frozen feature setting, performance gaps between pruning strategies become even more pronounced, with Hard and Easy pruning strategies performing significantly worse, highlighting their reliance on feature adaptation rather than inherently meaningful sample selection. Loss- based methods (GraNd-score, EL22-score) degrade under dataset shifts, suggesting that they may over-prioritize easy-to-learn samples that do not generalize well across domains. These findings emphasize that effective pruning strategies must go beyond dataset setaset-specific heuristics and instead focus on selecting robust, transferable samples that remain useful even under feature extraction constraints, reinforcing the advantage of Gm MATCHING in real-world transfer learning applications.
DENERALIZATION TO BOTH UNSEEN DOMAIN AND NETWORK.
D. GENERALIZATION
In many real-world scenarios, both domain and architecture mismatches occur simultaneously - a setting where the data selection model differs from the downstream training model both in terms of dataset and architecture. For instance, models like CLIP (Radford al., 2021a) are often used frozen, large-scale pretrained encoders on generic web-scale data (e.g.. YFCC), whereas final deployment models may be lightweight CNNs (e.g., ResNet-18) trained from scratch on task-specific datasets like CIFAR.
To assess the robustness of pruning strategies in this challenging setting, we construct an experiment where a frozen CLIP ViT-B/32 encoder - pretrained on a generic dataset - is used as proxy to embed CIFAR-10 10 samples and perform subset selection via Gm MATCHING. A ResNet-18 model is then trained from scratch on the selected subset using only CIFAR-10 labels. This setup introduces both domain shift (CLIP never trained on CIFAR- 10) and a network shift (ViT to ResNet).
We evaluate performance across multiple corruption regimes: a clean dataset, well as with 20% and 40% label noise. Table 13 presents the results across three subset sizes (10, 100, 1000 samples per class), showing the classification accuracy of -8 trained on these subsets.
Across all corruption levels and subset sizes, Gm MATCHING consistently outperforms all baselines. For instance, in the 40% label noise setting, GM MATCHING achieves 43.7% % mean accuracy - a full 3% higher than the next best method
43

---

Geometric Median (GM) Matching
CIEAR-10 (VIT-B/32 - ResNet--18
Method Size
10
100
1000
Mean 1
No Corruption
Random
23.2 - 3.9
42.4 + 2.3
86.8 + 0.7
50.8
Easy
27.4 + 0.4
42.5
0.5
84.2 0.3
51.4
Hard
19.8 + 1.7
39.7
+ 1.0
86.1 0.2
48.5
Herding
24.9 + 1.6
45.7
+ 0.6
86.8 0.4
52.5
Moderate
24.0 - 1.8
44.5
2.7
86.1 - 1.3
51.5
GM Matching
25.6 + 0.2
47.6
+ 1.9
86.9 + 0.3
53.4
20%
Label Noise
Random
18.0 2.4
36.4 + 0.9
75.5 0.7
43.3
Easy
24.2 0.6
40.7 1.1
76.5
47.1
Hard
13.1 1.9
22.7 + 0.7
67.2
34.3
Herding
22.7 0.3
38.5 1.5
76.6 1.3
45,9
Moderate
23.0 1.3
39.8
+ 1.3
75.9 + 1.3
46.2
GM Matching
26.0 - 0.9
41.1 + 1.8
77.8 0.4
48.3
40% Label Noise
Random
16.8
28.3
66.2 0.8
37.1
Easy
22.5 + 1.5
34.1 1.5
1.1
42.4
Hard
12.8 1.3
16.5 1.6
1.94
26.9
Herding
18.0 + 1.4
30.1
1.4
37.7
Moderate
20.2 + 1.3
34.0 1.7
67.8 1 1.5
40.7
GM Matching
23.3 + 1.8
36.8
1 1.4
71.0
1.3
43.7
Table 13: NETWORK DOMAIN TRANSFER PROXY ENCODER: A pretrained CLIP ViT-B/32 proxy encoder used find (10, 100, 1000) samples per class from CIFAR-IO. Consequently. ResNet-18 is trained on the selected subset. perform the experiment across clean; 20% and 40% Label Noise.
(Moderate, 40.7%). Notably, the advantage of GM MATCHING particularly prominent at smaller subset sizes (e.g., 10 samples/class), suggesting that it is more effective at isolating informative, transferable samples even when the proxy encoder and downstream model differ significantly.
These findings highlight key strength of Gm MATCHING: its ability to select subsets that retain semantic structure and predictive utility, even when selected in a drastically different representation space than where the model is ultimately trained. By anchoring the selection process on the geometric median - a robust estimator that captures the core of the data distribution - Gm MATCHING exhibits strong generalization under simultancous domain and architecture shifts, making a practical and principled choice for real-world deployment settings involving large-scale, black-box, or frozen proxy encoders.
I.4. Unconditional Image Generation
To further validate our approach, we conduct experiments on an unconditional image generation task using a diffusion model. Specifically, we train U-Net on the MNIST dataset, with Denoising Diffusion Probabilistic Models (DDPM) (Ho al. 2020), which learns generate images through a gradual denoising process. We perform sample selection with CLIP
ViT-B/32 (Radford et al. 202 embeddings demonstrated in Figure 19
The fundamental idea behind diffusion models is to learn the reverse of gradual noise corruption process applied to training images. This forward diffusion process progressively adds Gaussian noise to an image across a sequence of time-steps t I,...,T T, following the Markovian formulation:
N(zi / 1 1,T
(70)
where, x, represents the image timestep and 3r 10 denotes the noise variance timestep f, following predefined
44

---

Geometric Median (GM) Matching
504 / 2
3
5 6
7
2
8
6
7
6
9
140
4
/
1
2 9
4 6 8 8 4
5
3
3
3
8
6
3
3
0
7
8
1
9
3
9
8
6
9
7
5
9
3
3
0
7
4
7
6
8
0
9
4
/
4
4
5
6
0
7
6
0
(a) Clean Samples
(b) (Additive) Gaussian Noise
(c) (Additive) Uniform Noise
2
4 3 0
5
4 4
1
8 6 3 5 2 4
4
9 1 7v
8 9 9. & 6 6 9
3 9 S
5 8 2 8
1
&
4
0
044224
2
0
(d) Random Patches
(c) Cutout Noise
(f) Random Noise
Figure 18: Image Corruption: Visualization various noise types and sample categories. Each sub-figure demonstrates a distinct type data corruption or clean sample used in the experiments.
schedule. The generative process aims learn function po (2 (2xa) that can reverse this diffusion, thereby reconstructing clean images from noise. The learned denoising function is parameterized using deep neural network that predicts the noise component in given sample, enabling the recovery of realistic image distributions.
To evaluate the quality of the generated samples, we use the Fréchet Inception Distance (FID), which measures the Wasserstein-2 distance between the feature distributions of real and generated images:
FID
μr,
Ugg
+ Tr E, +E, 2(E,
(71)
where (pr; Ex) and (Mg, Eg) are the mean and covariance the real and generated feature distributions respectively, and Tr(-) denotes the trace operator. Lower FID values indicate that the generated images more closely resemble the real data distribution.
1.4.1. EXPERIMENTAL SETUP
For training stability and optimal convergence, adopt specific hyperparameter settings. The batch size is set to 128 to ensure efficient mini-batch updates. The learning rate is fixed at 1 x 10-1, tuned for stable convergence. We use the AdamW optimizer due to its adaptive learning rate properties and weight decay regularization. The number of diffusion time-steps set to 1000, providing sufficient granularity for high-resolution generative refinement. A linear noise schedule applied where 3, increases lincarly over time-steps, preventing abrupt changes noise levels. To ensure robustness in our conclusions, we conduct multiple training runs with different random seeds, mitigating the impact of initialization biases
45

---

Geometric Median (GM) Matching
-3
-1
3
-3
(a) Clean Samples
(b) (Additive) Gaussian Noise
(c) (Additive) Uniform Noisc
Baen
-3
-2
-3
(d) Random Patches
(e) Cutout Noise
(I) Random Noise
Figure 19: (PROXY EMBEDDING SPACE) t-SNE Visualization of CLIP ViT-B/32 Embeddings of a subset of MNIST images from Figure 18 (a) Clean (baseline), and where 45% samples corrupted with (b) Gaussian noise, (c) Uniform noise,
(d) Random patches, (e) Cutout noise.
and training variability.
Our experiments involve rumning the model across multiple random seeds ensure statistical robustness. Results compared using FID scores to determine the effectiveness of different data selection strategies in training the diffusion model. We compare GM MATCHING against multiple baseline geometric subset selection gtratgies(Appendin I.T): Random, Easy, Hard, Moderate, and Kernel Herding.
To further stress-test these selection methods, we introduce structured perturbations into the training data, simulating realistic noise and adversarial conditions. These perturbations include Gaussian noise, which applies additive white noise pixel-wise; uniform noise, which perturbs pixel intensities randomly; random patches, which corrupt localized regions with random pixel values; cutout augmentations, which mask rectangular sections of images; and completely random images, which introduce purely random noise samples into training batches. Visual examples of these corrupted data samples presented in Figure T8
1.4.2. DISCUSSION
Figure 6 depicts the generative performance of the diffusion model when trained on the selected subset. Evidently, GM MATCHING consistently achieves FID scores across all subset sizes and corruption scenarios, clearly demonstrating its superior performance terms of generating high-quality samples. the clean (no corruption) setting, at smaller subset sizes (10%-20%), Gm MATCHING substantially outperforms the baseline methods. While all methods eventually converge to similar performance levels full dataset size (100%), the early advantage of Gm MATCHING highlights its efficiency in selecting representative subsets. Under moderate (20% )corruption, Gm MATCHING maintains significant performance advantage, especially at smaller subset sizes (10%-40%) This result suggests that Gm MATCHING effectively identifies high-quality training subsets even in the presence of moderately corrupted data, thereby preserving generative quality. At higher (30%)corrmg)l corruption rates, Gm MATCHING demonstrates remarkable robustness against higher corruption levels. In contrast, methods such "Hard" sampling significantly degrade in performance due to sensitivity to corrupted data.
46

---

Geometric Median (GM) Matching
3
O
7
8
7
8
3
5
7
0
7
8
6
9
3
O
7
8
7
8
4
/
7
.3
2
/
4
O
8
7
6
2
2
6
9
0
1
6
2
2
/
1
0
0
/
5
5
1
3
6
0
E
5
0
8
6
0
0
1
5
5
1
3
6
9
3
5
2
8
3
5
1
2
8
9
6
6
1
5 4 6 9 6
2
8
O 1
5
/ 7
8
3
5
6
7
7
9
4
9
0
4
2
7
9
4
9
2
4
7 1
4
9
0
9
3
6
6
?
3
6
3
9
3
0
6
7
3
3
3
0
?
3
d
0
2
0
0
7
1
6
9
7
2
0
8
7
8
6
7
2 0
0
7
6
2
9
5
5
9
0
6
4
9 4
5
9
7
6
4
3 5
U
4
O
(
6
4
(a) Random
(b) Easy
(c) Hard
3
O
7
6
9
8
6 9
3
5
7
0
7
8
9
3 0
7
0
7
8
3
8
8
7 /
6
2
2
6
8
0
8
7
6
2
2
/
3
0
8 7
6
7
2
6
3
0 8 2
0
5
5
7
3
6
8
0
1
5
7
3
6
8
0
5
O
7
6
6
2
8
9
1
8
4
5
2
2
8
8
2
8
1
5
2
2
5
8
6
8
1
5
6
7
7
9
4
9
0
4
7
7
9
4
9
4
4
7
7
9
4
9
4
9
3
0
6
7
3
6
3
9
3
0
6
7
4
6
3
9
3
0
6
7
5
6
3 7 4
2
0
8
7
6
9 6 4
7
2
0
8
7
1
6
7
2
0
8
7
8
6
7
9
5
5
4
0
6
1 5
5
9
0
7
6 4
3 5
5
9
0
6
(d) Moderate
(c) Herding
(f) Gm MATCHING
Figure 20: (No Corruption) Visualization Generated Samples 40% sampling
GM MATCHING, however, remains stable and consistently achieves superior FID scores, emphasizing its robustness in more challenging scenarios.
Visual analyses provide additional insights into the effectiveness of GM Matching, particularly when comparing subsets of clean versus noisy training data. In Figure 20 present visualizations of generated samples obtained from the UNet trained via DDPM on a 40% subset of MNIST. All subset selection methods produce visually comparable and clear digit images under these clean conditions, demonstrating that, in an ideal scenario without data corruption, the impact of different subset selection methods on visual quality is minimal. However, Figure 2T highlights significant differences generated samples when the same model is trained on 40% subset derived from data subjected to severe corruption (30%). Baseline methods, such as Random, Easy, and Hard selection, result samples with substantial visual distortion and ambiguity. In contrast, Gm MATCHING notably produces clear and well-defined digit representations, emphasizing its superior robustness and capability effectively mitigate the adverse effects of corrupted data during training. Collectively, these visual results reinforce our quantitative findings (Figure 6), clearly underscoring the suitability and robustness of Gm MATCHING in challenging data corruption scenarios for training diffusion models.
47

---

Geometric Median (GM) Matching
9
7
0
7
8
7
3
7
3
8
7
B
7
3
2
4
8
7
6
7
6
8
/
\
E
5
5
7
4
3
6
6
6
%
4
/
R
7
3
2
6
6
3
4
/
Z
3
A
4
1
9
7
6
/
f
8
0
6
6
i
0
4
8
1
V
7
4
3
6
7
2
9
(a) Random
(b) Easy
(c) Hard
3
0
7
8
9
0
6 4
9
7
3
C
7
6
7
8
3
9
6
7
6
/
2
6
4
6
7
4
7
6
7
6
3
2
6
4
0
0
5
6
O
7
8
6
5 & 6
E
9
7
4
3
8
6
6
5
7
9
6
5 6 1 3
4 4
8
8
6
8
5 A 6 9
9
2
9
2
5
5
6
6
1
5
2 8
7
9
4
9 1 6
2
7
0
1
4
7
77
9
6
9
9
9
0
6
9
6
#
8
G
6
3
6
6
7
6
2
0
8
7
9
t
U
9
4
2
0
8
7
9
6
9
7
>
9
S
4
0
4
9
0
4
5
4
2
6
4
(d) Moderate
(c) Herding
(f) Gm MATCHING
Figure 21: (30% Corruption) Visualization of Generated Samples 40% sampling
48


Reviews:
[{"review_id": "JkZDAElFru", "reviewer": "Reviewer_1B9r", "summary": "This paper proposes a dataset pruning method with subset selection. The proposed method utilizes the geometric median moment matching allowing a small amount of an approximation error. Also, the authors provide the theoretical guarantee that the proposed geometric median moment matching leads to a good approximation of the mean. Finally, several experiments on the benchmark datasets are conducted to demonstrate the efficacy of the proposed method on the clean dataset as well as noisy data.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The terminology k-subset selection.**\n\nWe appreciate the reviewer’s observation regarding potential ambiguity in the term k-subset selection. Our usage follows common conventions in the subset selection and coreset literature, where k typically denotes the size of the selected subset—either as an absolute number or as a fraction of the dataset i.e., $k = \\rho n $ for some  $\\rho \\in (0,1)$ interchangeably. \nImportantly, this terminology is not only standard but also theoretically grounded in our work. Our results are stated in terms of selecting k samples from a dataset of size n, and the error bounds naturally depend on k (e.g. Theorem 1). \nThus, we feel our formulation justifies the use of k-subset selection both terminologically and theoretically.\n\nHowever, based on your suggestion, we will clarify this distinction explicitly in the revised manuscript to avoid any confusion.\n\n**Q2. Performance for small fixed subset sizes (k=10,100,1000)**\n\nWe thank the reviewer for this valuable suggestion. \n\nWe conduct additional experiments on CIFAR-10 using fixed subset sizes 10, 100, 1000 samples per class  under three settings: clean, 20% label noise, and 40% label noise. A CLIP ViT-B/32 proxy encoder is used to select subsets, and a ResNet-18 is trained from scratch on the pruned data.\n\n| **Method / Subset** | **10** | **100** | **1000** | **Mean ↑** |\n|---------------------|--------|---------|----------|------------|\n| **No Corruption** |||||\n| Random              | 23.2 ± 3.9 | 42.4 ± 2.3 | 86.8 ± 0.7 | 50.8 |\n| Easy                | 27.4 ± 0.4 | 42.5 ± 0.5 | 84.2 ± 0.3 | 51.4 |\n| Hard                | 19.8 ± 1.7 | 39.7 ± 1.0 | 86.1 ± 0.2 | 48.5 |\n| Herding             | 24.9 ± 1.6 | 45.7 ± 0.6 | 86.8 ± 0.4 | 52.5 |\n| Moderate            | 24.0 ± 1.8 | 44.5 ± 2.7 | 86.1 ± 1.3 | 51.5 |\n| **GM Matching**     | **25.6 ± 0.2** | **47.6 ± 1.9** | **86.9 ± 0.3** | **53.4** |\n| **20% Label Noise** |||||\n| Random              | 18.0 ± 2.4 | 36.4 ± 0.9 | 75.5 ± 0.7 | 43.3 |\n| Easy                | 24.2 ± 0.6 | 40.7 ± 1.1 | 76.5 ± 1.9 | 47.1 |\n| Hard                | 13.1 ± 1.9 | 22.7 ± 0.7 | 67.2 ± 0.5 | 34.3 |\n| Herding             | 22.7 ± 0.3 | 38.5 ± 1.5 | 76.6 ± 1.3 | 45.9 |\n| Moderate            | 23.0 ± 1.3 | 39.8 ± 1.3 | 75.9 ± 1.3 | 46.2 |\n| **GM Matching**     | **26.0 ± 0.9** | **41.1 ± 1.8** | **77.8 ± 0.4** | **48.3** |\n| **40% Label Noise** |||||\n| Random              | 16.8 ± 2.0 | 28.3 ± 2.2 | 66.2 ± 0.8 | 37.1 |\n| Easy                | 22.5 ± 1.5 | 34.1 ± 1.5 | 70.5 ± 1.1 | 42.4 |\n| Hard                | 12.8 ± 1.3 | 16.5 ± 1.6 | 51.4 ± 1.9 | 26.9 |\n| Herding             | 18.0 ± 1.4 | 30.1 ± 0.9 | 65.1 ± 1.4 | 37.7 |\n| Moderate            | 20.2 ± 1.3 | 34.0 ± 1.7 | 67.8 ± 1.5 | 40.7 |\n| **GM Matching**     | **23.3 ± 1.8** | **36.8 ± 1.4** | **71.0 ± 1.3** | **43.7** |\n\nAs evident, GM Matching remains consistently strong even under extreme data reduction, particularly in noisy settings. This further supports the versatility of the method across the spectrum of subset sizes.\n\n**Q3. Simplicity of DDPM exp**\n\t\nWe agree that MNIST is a relatively simple dataset. Our goal with this experiment was to provide a proof of concept (PoC) demonstrating the applicability of GM Matching to generative modeling — specifically, to show that high-quality subsets selected via our method improve generation quality, even under severe corruption. This controlled setup was intentionally chosen to isolate the effect of subset selection, avoiding confounding factors from architectural or optimization complexity.  We believe this early result is a meaningful step in connecting robust selection to generative tasks. A thorough investigation of GM Matching in diffusion models on more complex datasets (e.g., CIFAR-10, CelebA) and with modern backbones (e.g., ADM) is an exciting direction for future work, as is exploring its applicability to LLMs.\n\n**Q4. Intuition behind GM**\n\nGreat question — thank you for the opportunity to clarify.\nAt the core of our approach is the observation that the empirical mean is highly sensitive to outliers and corrupted data, which can significantly distort subset selection. In contrast, the geometric median has a breakdown point of 50%, making it a far more robust estimate of central tendency in noisy settings. This intuition leads naturally to our Robust Moment Matching formulation: instead of chasing the (fragile) dataset mean, we align with a robust estimator that resists the influence of corrupted or adversarial data points. This makes the selection process resilient across a variety of noise settings — as our theory and experiments confirm.\n\nWe thank the reviewer once again and look forward to engaging further in discussion in strengthening the paper.", "claims_and_evidence": "The author's claims are clear.", "methods_and_evaluation_criteria": "The proposed methods seem to make sense.", "theoretical_claims": "I haven't read the proof of the proposed theorem, but it seems to be straightforward maths.", "experimental_designs_or_analyses": "The experiments are conducted based on the previous literature.", "relation_to_broader_scientific_literature": "-", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "- The paper is clearly written, and easy to follow.\n- Extensive experiments are conducted to demonstrate the superiority of the proposed method.\n- The DDPM data generation experiment on the MNIST dataset is too simple. I am aware that training the diffusion model requires a long training time, but it would be more persuasive if the authors utilized complex datasets for training the generative model.", "other_comments_or_suggestions": "- The terminology $k$-subset selection might be misunderstood as choosing a few handful number of data instances, while the authors are selecting a portion of the dataset.\n- Regarding that, what happens to the experimental result if the authors set $k=10, 100, 1000$, for example in the CIFAR case?", "questions_for_authors": "- What was the intuition behind utilizing the geometric median moment matching?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RvfaHiolJo", "reviewer": "Reviewer_7RaC", "summary": "The paper introduces Geometric Median (GM) Matching, a novel approach for robust k-subset selection from noisy datasets. The key contribution is replacing the empirical mean, which is sensitive to outliers, with the Geometric Median (GM), a robust estimator with an optimal breakdown point of 1/2. The GM Matching algorithm iteratively selects a subset whose mean approximates the GM of the potentially noisy dataset. Theoretical guarantees demonstrate that GM Matching achieves $O(1/k)$ scaling, outperforming traditional $O(1/\\sqrt{k})$ scaling of uniform sampling, even under high corruption. Extensive experiments on image classification and generation tasks show that GM Matching significantly outperforms existing pruning methods, particularly in high-corruption settings, making it a strong baseline for robust data pruning.\n\n--------------- Updated ------------\nThank you for your response, based on other reviews and response, I feel confident in my rating of accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed, thoughtful, and encouraging feedback. We are pleased that you found our theoretical results, empirical validation, and overall framing of GM Matching to be strong contributions. We respond to your key points below: \n\n**Q1. Missing Related Work**\n\nThank you for pointing this out. Garg et al. (2023) presents an interesting and well-motivated approach based on low-loss curvature, which offers valuable insights into data efficiency and sample selection. While it is not explicitly designed for noisy settings, we agree that it is a promising direction for future work, particularly in exploring whether curvature-based selection methods can be made robust to corruption. We will cite and briefly discuss this work in the revised Related Work section. \n\n**Q2. Evaluation Metrics for Diffusion**\n\nWe agree that FID has known limitations, especially when evaluating modern diffusion models. In our case, we used FID following standard practice for proof-of-concept (PoC) experiments on simple generative setups, and we appreciate that the reviewer finds this acceptable. That said, we thank the reviewer for pointing us to Stein et al. (2023) and Jayasumana et al. (2024), and we will reference both in the revised manuscript.\n\n**Q3. Adversarial attack parameters:**\n\nWe appreciate the reviewer’s careful attention to reproducibility and thank you for this valuable feedback. Clarifying attack settings is indeed essential for replicating adversarial corruption experiments.\n\nAs mentioned in the Experiments Section, our setup is identical to Moderate Coreset [ICLR 23]. The code is available at: https://github.com/tmllab/2023_ICLR_Moderate-DS . \n\nSpecifically,  In the adversarial corruption experiments, we used Projected Gradient Descent (PGD) as implemented in torchattacks, with the following parameters: $\\epsilon$ = 8/255, step size  = 2/255, number of iterations = 10, and random start = True. These are standard settings in the robust training literature (e.g., Madry et al., 2018). Additionally, we used Gradient Sign Attack (GSA)  (Goodfellow et al., 2014) via advertorch, with the same $\\epsilon$ = 8/255. Adversarial examples were generated using a pretrained ResNet-50 on CIFAR-100 with standard normalization. \n\nWe will ensure these details are clearly stated in the revised manuscript - Appendix.\n\nFurthermore, we will release the code of GM Matching for reproducibility. \n\n**Q4.. Discussion on forgetting**\n\nWe appreciate the reviewer highlighting this nuanced behavior. \n\nForgetting-based methods, which leverage early training dynamics, can perform well in clean or mildly corrupted settings at high retain ratios (e.g., 80–90%), where noise has limited impact. In such regimes, GM Matching may be modestly disadvantaged due to the bias introduced by the geometric median, while Forgetting can surface informative, hard-to-learn examples.\nHowever, Forgetting is known to be sensitive to corruption, unstable across architectures, and often requires careful tuning and access to full training traces. In contrast, GM Matching is simple, tuning-free, and inherently robust—making it particularly effective in severe or mixed corruption scenarios.\n\nWe will expand on this comparison in the revised manuscript and include a discussion highlighting when each method is most appropriate.\n\n**Q5. Settings where GM Matching is preferable.**\n \nWe thank the reviewer for this thoughtful question.\nTheoretically, in clean settings, at low pruning rates: the GM is a biased estimator of the uncorrupted mean, and as such, GM Matching may perform similar to or slightly worse than algorithms that leverage informative or hard examples—e.g., those with high loss, large gradient norms, or that are frequently forgotten—can be more valuable, making dynamic or score-based methods (e.g., Forgetting, EL2N) highly competitive.\n\nHowever, GM Matching has strong advantage in two key regimes:\n\n (1) Clean settings with high pruning rates, where its $\\mathcal{O}(1/k)$ convergence offers a sharp advantage over random sampling (a very strong baseline); and\n\n (2) Noisy settings, where its robustness to outliers leads to consistent improvements over dynamic or score-based methods, which often degrade under corruption.\n\nEven on real-world datasets without synthetic noise (e.g., CIFAR-100, TinyImageNet, ImageNet-1k), we observe consistent gains, underscoring its practical relevance—making it a robust, tuning-free default across varied conditions.\n\nWe will include this discussion in our revised manuscript. \n\nWe appreciate the thoughtful comments and suggestions, and we look forward to continued dialogue to further strengthen the work.", "claims_and_evidence": "The paper makes several claims, which are mostly well-supported by theoretical analysis and empirical validation:\n\n* GM Matching is robust under high corruption rates: Theoretical guarantees (Theorem 1) prove that GM Matching remains stable even when up to 50% of data is arbitrarily corrupted. The experiments on CIFAR-100 and Tiny ImageNet confirm that GM Matching consistently outperforms other selection methods in corrupted environments.\n* O(1/k) convergence rate: The authors provide a mathematical proof that GM Matching converges at a quadratic improvement over uniform sampling. Empirical results (Fig. 3) support this claim, showing GM Matching achieving better moment matching error than herding and random sampling.\n* Superior performance in real-world scenarios: The experiments across multiple datasets (Tables 1, 2, 3) demonstrate that GM Matching consistently outperforms alternatives in both clean and noisy settings.", "methods_and_evaluation_criteria": "The proposed method makes sense given the problem at hand, as it directly addresses the weaknesses of empirical mean-based selection methods in noisy datasets. The evaluation is mostly robust, with well-chosen benchmarks (CIFAR-100, Tiny ImageNet, MNIST), pruning ratios (20%-100%), and corruption scenarios (label noise, feature corruption, adversarial attacks).\n\nOne minor issue: The baseline comparison might be missing Garg et al. (2023) for core set selection [1]. While Garg et al. is not explicitly designed for noisy datasets, this work could be relevant and should be included in Related Work.\n\n\n[1] Garg, Isha, and Kaushik Roy. \"Samples with low loss curvature improve data efficiency.\" In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 20290-20300. 2023.", "theoretical_claims": "I checked the correctness of the theoretical proofs, and they seem sound. The key theoretical claim (GM Matching achieves O(1/k) convergence under gross corruption) is well-supported by rigorous mathematical derivations and empirical validation. While low-level details may have been missed, the results seem correct at the high level.", "experimental_designs_or_analyses": "The experimental design is solid, with extensive comparisons across different datasets, architectures, and corruption settings. The main concern is the use of FID for diffusion model evaluation. While acceptable in this case, the authors should consider moving to more robust generative evaluation metrics such as those proposed by Stein et al. (2023) and Jayasumana et al. (2024).\n\n[2] Stein, George, Jesse Cresswell, Rasa Hosseinzadeh, Yi Sui, Brendan Ross, Valentin Villecroze, Zhaoyan Liu, Anthony L. Caterini, Eric Taylor, and Gabriel Loaiza-Ganem. \"Exposing flaws of generative model evaluation metrics and their unfair treatment of diffusion models.\" Advances in Neural Information Processing Systems 36 (2023): 3732-3784.\n\t\n[3] Jayasumana, Sadeep, Srikumar Ramalingam, Andreas Veit, Daniel Glasner, Ayan Chakrabarti, and Sanjiv Kumar. \"Rethinking fid: Towards a better evaluation metric for image generation.\" In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9307-9315. 2024.", "relation_to_broader_scientific_literature": "The work builds upon robust statistics and subset selection techniques, integrating Geometric Median estimation into a scalable data pruning method. The key contribution is applying GM to data selection for deep learning robustness, which is novel and well-grounded in theoretical and empirical research. GM Matching provides a formal and solid approach to robustness against label noise and feature corruption.", "essential_references_not_discussed": "Garg et al. (2023): This work discusses low-loss curvature and its impact on data efficiency, which could strengthen the theoretical backing of GM Matching. While not directly related to robustness, it is worth including in Related Work.\n\n[1] Garg, Isha, and Kaushik Roy. \"Samples with low loss curvature improve data efficiency.\" In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 20290-20300. 2023.", "other_strengths_and_weaknesses": "Strengths:\n\n* Strong theoretical guarantees: The breakdown point of 1/2 makes GM Matching highly robust compared to mean-based approaches.\n* Extensive experiments: The authors test multiple datasets, architectures, and corruption types, making the results more generalizable.\n* Practical relevance: Given the increasing interest in data pruning and robust training, GM Matching is a strong baseline for future research.\n\nWeaknesses:\n\n*  Forgetting method performance needs more discussion: The results indicate that Forgetting performs better at higher corruption rates, but the paper does not fully explain why. A more detailed discussion of when to use GM Matching vs. other approaches would be useful.\n* Under feature corruption, when should GM Matching be used versus other methods? This should be more explicitly stated.\n* Adversarial attack settings are unclear: The paper does not provide details on PGD attack parameters—e.g., what was the epsilon bound? How many iterations were used? This should be stated in the main paper or appendix.", "other_comments_or_suggestions": "* Add adversarial attack parameters: Without this information, it is hard to replicate the results.\n* Clarify when to use GM Matching: The paper should discuss specific conditions under which GM Matching is preferable over other methods (e.g., what levels of corruption?).", "questions_for_authors": "1. What were the specific attack parameters? Please provide details on the epsilon bound and number of iterations.\n\n2. Why does Forgetting perform better at higher corruption rates? The paper suggests GM Matching is robust, yet Forgetting seems to outperform it at low pruning rates. Why is this the case? Some discussion would be helpful.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e0bg07oKcc", "reviewer": "Reviewer_C6QM", "summary": "The paper proposes the use of the Geometric Median to robustly identify subsets of a dataset that best represents the full dataset. The main goal is to reduce sensitivity of the selection algorithm to outliers in the corrupted data, a problem that traditional subset selectors that rely on the empirical mean suffer from. In this regard, the geometric mean is proposed as more robust surrogate. An iterative selection algorithm is proposed that selects subsets that minimizes the discrepancy between the subset and the geometric mean. Theoretical guarantees are given on the convergence properties of the proposed algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and detailed feedback. We are encouraged that the reviewer finds the theoretical claims well supported, the empirical design appropriate, and the core contribution valuable.\nBelow, we address the specific points raised: \n\n**Q1: Performance at Higher Corruption Rates (>20%) in Table 2**\n\nThank you for raising this. We now include experiments with 30% image corruption across two datasets (CIFAR-100 and TinyImageNet), at 20% and 30% selection rate: \n\n| Method / Ratio       | C(20%)     | C(30%)     | T(20%)  | T(30%)  | \n|----------------------|-------------------|--------------------|--------------------|--------------------|\n| Random               | 24.51 ± 1.34       | 32.26 ± 0.81       | 14.64 ± 0.29       | 19.41 ± 0.45       | \n| Herding              | 29.42 ± 1.54       | 37.50 ± 2.12       | 15.14 ± 0.45       | 20.19 ± 0.45       | \n| Forgetting           | 29.48 ± 1.98   | 38.01 ± 2.11       | 11.25 ± 0.90       | 17.07 ± 0.66       | \n| GraNd-score          | 23.03 ± 1.15       | 34.83 ± 1.22       | 13.68 ± 0.42       | 15.40 ± 0.52       | \n| EL2N-score           | 21.95 ± 1.08       | 31.63 ± 2.84       | 10.11 ± 0.25       | 13.52 ± 0.32       | \n| Optimization-based   | 26.77 ± 1.05       | 35.63 ± 0.63       | 13.20 ± 0.56       | 18.52 ± 0.33       | \n| Self-sup.-selection  | 23.12 ± 1.47       | 34.85 ± 0.68       | 11.23 ± 0.32       | 17.76 ± 0.69       | \n| Moderate-DS          | 28.45 ± 0.53       | 36.55 ± 1.26       | 15.27 ± 0.38   | 20.33 ± 0.28       |\n| **GM Matching**      | **40.28 ± 1.02**   | **50.71 ± 0.86**   | **20.38 ± 1.09**   | **25.93 ± 0.98**   |\n\nGM Matching, significantly outperforms all baselines — the gains are even more pronounced compared to milder corruption (Tables 2, 4, 5), further validating the robustness of our approach.\n\n**Q2. Scaling on larger datasets?**\n\nWe now include results ( Test Accuracy @ Top-5) on ImageNet-1k (1.2M training samples), using ResNet-50 and selection ratios from 60% to 90%: \n\n| Method / Ratio       | 60%             | 70%             | 80%             | 90%             | \n|----------------------|-----------------|------------------|------------------|------------------|\n| Random               | 87.91 ± 0.37     | 88.63 ± 0.95     | 89.52 ± 0.73     | 89.57 ± 0.60     | \n| Herding              | 88.25 ± 2.16     | 88.81 ± 1.06     | 89.60 ± 0.58     | 90.41 ± 0.33     |\n| Forgetting           | 88.83 ± 0.92     | 89.81 ± 0.97     | 89.94 ± 0.26     | 90.41 ± 0.58     | \n| GraNd-score          | 88.48 ± 1.73     | 89.82 ± 2.07     | 90.24 ± 0.81     | 90.41 ± 0.62     | \n| EL2N-score           | 88.48 ± 2.81     | 89.82 ± 1.14     | 90.34 ± 0.87     | 90.46 ± 0.96     | \n| Self-sup.-selection  | 87.59 ± 2.61     | 89.56 ± 1.97     | 90.74 ± 0.27     | 90.49 ± 0.98     | \n| Moderate-DS          | 89.23 ± 0.96     | 89.94 ± 0.74     | 90.65 ± 0.51     | 90.75 ± 0.35     | \n| **GM Matching**      | **90.28 ± 0.38** | **90.54 ± 0.19** | **90.72 ± 0.26** | **90.84 ± 0.32** | \n\nGM Matching achieves the best performance across all pruning levels — outperforming all baselines. Beyond empirical scalability, kindly also refer to Section 5.4 and Appendix F, where we break down the time complexity of both GM estimation and greedy selection and motivating the batched variant (Algorithm 1). Figure 9-11 show wall-clock time scaling vs. dataset size, embedding dim, and batch size. \n\n**Note:** For the new experiments in Q1 and Q2, we follow the setup and reuse baselines from Moderate Coreset (ICLR 2023). Code: https://github.com/tmllab/2023_ICLR_Moderate-DS\n\n**Q3. Contribution**\n\nWe thank the reviewer for acknowledging the strength of our theoretical grounding and robustness to outliers. We respectfully clarify that our contribution goes well beyond a simple substitution: Fundamentally, we propose a new combinatorial formulation for Robust Moment Matching, enabling systematic study of subset selection in noisy settings. While we instantiate our method with the GM, the framework supports a wide class of robust estimators (e.g., trimmed means, M-estimators), opening a principled direction in robust subset selection under noise. This formulation is fundamental, as it decouples selection from fragile mean estimation and instead aligns with a robust signal. Moreover, since the framework applies to general Hilbert spaces, it can extend to gradient space, enabling integration with methods like CRAIG that perform gradient matching for coreset selection. In summary, we present a general, theoretically grounded framework for robust coreset selection — not limited to a single estimator or modality — paving the way for future advances in robust data summarization.\n\n**Q4. Figure 6 formatting**\n\nThank you for pointing this out. We will correct the spacing issue in the camera-ready version.\n\nWe are grateful for the reviewer’s insights and look forward to constructive discussion and refining the paper accordingly.", "claims_and_evidence": "The claims made in the paper are well supported in theoretical and empirical analysis.", "methods_and_evaluation_criteria": "The evaluation criteria is standard for the subset selection problem.", "theoretical_claims": "I do not find any issues with the proofs of the theoretical claims in the paper, although i should stress that i only did a cursory pass over the proofs.", "experimental_designs_or_analyses": "The experimental setup appears standard for the problem domain.", "relation_to_broader_scientific_literature": "The paper builds on classical results in robust estimation and by utilizing the Geometric Mean, extend these workds into the current subset selection domain.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The main strength of the proposed method is its extension of subset selection methods using the GM, which is well grounded in theory and in so doing , answers the question of how to obtain subset selector that are robust to outliers. On the other side, one may point out that the main contribution is the substitution of the empirical mean with the geometric mean in an already existing subset selection method.", "other_comments_or_suggestions": "The captions of Figure 6 are obscured by vspacing.", "questions_for_authors": "- How well does the proposed method perform when the corruption rate is larger than 20% in table 2?\n\n- The current experiments are performed on small scale datasets. How does the proposed method scale when applied on larger datasets?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes Geometric Median (GM) Matching, a robust method for k-subset selection from noisy data. By replacing the outlier-sensitive empirical mean with the GM, which has an optimal breakdown point of 1/2, the algorithm selects subsets whose means approximate the GM. It achieves an improved theoretical error scaling of $O(1/k)$, surpassing the $O(1/\sqrt{k})$ of uniform sampling, even under heavy corruption. Experiments on image classification and generation confirm its superior performance over existing pruning methods, establishing it as a strong baseline for robust data selection. The majority of reviewers appreciates its novelty and soundness of the paper, especially its theoretical contribution. Although one reviewer raised concerns about the parameters used in the CIFAR-10 experiment, I find the rebuttal sufficiently convincing. As a side note, while the reviewer found the term ``k-subset'' potentially misleading, I consider it standard terminology in the community. Therefore, I recommend accepting the paper.
Decision: Accept (poster)