Research map / Learning theory and algorithms / Prediction and decision losses
Geometric Median (GM) Matching for Robust k-Subset Selection from Noisy Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Geometric Median (GM) Matching, a herding-style k-subset selection method that matches the subset mean to the geometric median of CLIP-embedded (possibly corrupted) data, evaluated for robust data pruning in classification and generation.
Problem
Data pruning / k-subset selection degrades under gross corruption (noisy labels, corrupted features, adversarial points) because existing scoring and moment-matching methods rely on the empirical mean, which has a breakdown point of zero.
Approach
Replace the empirical mean target in kernel-herding-style moment matching with the geometric median of the embedded dataset (breakdown point 1/2), computed via Weiszfeld iterations, and select samples greedily so the subset mean matches it.
Key results
- On CIFAR-100 with 20% selection and clean data, GM Matching reaches 55.93% vs 51.83% for Moderate-DS and 50.26% for Random.
- Under 20% feature corruption on CIFAR-100 at 20% selection, GM Matching achieves 47.12% vs 42.98% for Moderate-DS.
- On ImageNet-1k at 60% selection, GM Matching gets 90.28% top-5 vs 89.23% for Moderate-DS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · CIFAR-100, clean | Mean Top-1 accuracy (%): 66.01 vs 64.37 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · Tiny ImageNet, clean | Mean Top-1 accuracy (%): 37.44 vs 35.64 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · ImageNet-1k, clean | Mean Top-5 accuracy (%): 90.65 vs 90.29 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · CIFAR-100, 5% feature corruption | Mean test accuracy (%): 64.80 vs 63.33 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · CIFAR-100, 10% feature corruption | Mean test accuracy (%): 64.33 vs 62.46 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · CIFAR-100, 20% feature corruption | Mean test accuracy (%): 63.21 vs 60.87 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · Tiny ImageNet, 5% feature corruption | Mean test accuracy (%): 36.96 vs 35.24 | Helped |
| Use GM Matching instead of Moderate-DS | ResNet-50 data pruning · Tiny ImageNet, 10% feature corruption | Mean test accuracy (%): 36.94 vs 34.68 | Helped |
Surprising findings
- Kernel Herding marginally outperforms GM Matching in the clean setting in the moment-discrepancy analysis, per the authors.
- Even the 'Optimization-based' and 'EL2N-score' baselines degrade strongly under corruption, sometimes below random sampling.
Limitations
- Theoretical O(1/k) rate depends on assumptions such as bounded features and the target lying in the relative interior of the convex hull, and the bound on the GM error is stated loosely.
- Sub-sampling for GM and batching introduce extra variance and bias, with a trade-off against speed.
- Robustness is shown mainly on synthetic 2D GMM and image corruptions with a fixed CLIP proxy encoder; the proxy encoder choice matters.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 Tiny-ImageNet ImageNet-1k MNIST GMM synthetic
Benchmarks: CIFAR-100 Tiny-ImageNet ImageNet-1k
Metrics: top-1 accuracy top-5 accuracy squared moment discrepancy
Baselines: Random Herding Forgetting GraNd-score EL2N-score Optimization-based Self-sup.-selection Moderate-DS
Builds on: Kernel Herding Weiszfeld algorithm Gross Corruption model Frank-Wolfe
Closest papers by meaning
- DRoP: Distributionally Robust Data Pruning (ICLR 2025 · similarity 0.86)
- $\mathbb{D}^2$ Pruning: Message Passing for Balancing Diversity & Difficulty in Data Pruning (ICLR 2024 · similarity 0.84)
- GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning (NeurIPS 2024 · similarity 0.84)
- Data Pruning by Information Maximization (ICLR 2025 · similarity 0.84)
- Exploring Learning Complexity for Efficient Downstream Dataset Pruning (ICLR 2025 · similarity 0.84)
- Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.