Geometric Median (GM) Matching for Robust k-Subset Selection from Noisy Data

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. Below, we address the specific points raised:

Q1: Performance at Higher Corruption Rates (>20%) in Table 2

Thank 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:

GM 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.

Q2. Scaling on larger datasets?

We now include results ( Test Accuracy @ Top-5) on ImageNet-1k (1.2M training samples), using ResNet-50 and selection ratios from 60% to 90%:

GM 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.

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

Q3. Contribution

We 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.

Q4. Figure 6 formatting

Thank you for pointing this out. We will correct the spacing issue in the camera-ready version.

We are grateful for the reviewer’s insights and look forward to constructive discussion and refining the paper accordingly.

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:

Q1. Missing Related Work

Thank 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.

Q2. Evaluation Metrics for Diffusion

We 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.

Q3. Adversarial attack parameters:

We 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.

As 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 .

Specifically, 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.

We will ensure these details are clearly stated in the revised manuscript - Appendix.

Furthermore, we will release the code of GM Matching for reproducibility.

Q4.. Discussion on forgetting

We appreciate the reviewer highlighting this nuanced behavior.

Forgetting-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. However, 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.

We will expand on this comparison in the revised manuscript and include a discussion highlighting when each method is most appropriate.

Q5. Settings where GM Matching is preferable.

We thank the reviewer for this thoughtful question. Theoretically, 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.

However, GM Matching has strong advantage in two key regimes:

(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

(2) Noisy settings, where its robustness to outliers leads to consistent improvements over dynamic or score-based methods, which often degrade under corruption.

Even 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.

We will include this discussion in our revised manuscript.

We appreciate the thoughtful comments and suggestions, and we look forward to continued dialogue to further strengthen the work.

Q1. The terminology k-subset selection.

We 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. Importantly, 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). Thus, we feel our formulation justifies the use of k-subset selection both terminologically and theoretically.

However, based on your suggestion, we will clarify this distinction explicitly in the revised manuscript to avoid any confusion.

Q2. Performance for small fixed subset sizes (k=10,100,1000)

We thank the reviewer for this valuable suggestion.

We 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.

As 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.

Q3. Simplicity of DDPM exp

We 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.

Q4. Intuition behind GM

Great question — thank you for the opportunity to clarify. At 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.

We thank the reviewer once again and look forward to engaging further in discussion in strengthening the paper.