Geometric Median (GM) Matching for Robust Data Pruning
This addresses the need for robust data pruning methods in large-scale, noisy data collections, with incremental improvements over prior state-of-the-art.
The paper tackles the problem of robust data pruning in noisy datasets by proposing Geometric Median Matching, a greedy algorithm that selects a subset approximating the geometric median, achieving optimal breakdown point of 1/2 under arbitrary corruption and showing improved scaling over uniform sampling.
Large-scale data collections in the wild, are invariably noisy. Thus developing data pruning strategies that remain robust even in the presence of corruption is critical in practice. In this work, we propose Geometric Median ($\gm$) Matching -- a herding 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 {\bf optimal breakdown point} of {\bf 1/2} even under {\bf arbitrary} corruption. Extensive experiments across several popular deep learning benchmarks indicate that $\gm$ Matching consistently improves over 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.