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