Rank-Variance Scores for Importance Sampling and Data Pruning under Label Contamination

arXiv:2605.07551v2 Announce Type: replace Abstract: Variance-optimal importance sampling and magnitude-based pruning prioritize high-loss or large-gradient examples, which under label contamination are often the corrupted ones. Under Huber's $\varepsilon$-contamination model, we characterize this failure exactly: a score sampler's share of visits to corrupted examples is set by their mean score relative to the dataset mean, and a pruned subset's contamination is tightly bounded by the score's corruption-detection AUROC; at every loss-based score we measure, pruning is provably no cleaner than random selection. A useful score must therefore be non-monotone in the loss. We build such a score from the loss ranks of $K$ independently trained proxies: a mislabelled example ranks consistently hardest, a near-boundary example unstably. Its total rank variance (TRV) splits into a between-proxy part, Disagreement-Regularized Importance Sampling (DR-IS), and a within-proxy part; the split predicts that DR-IS is the better sampler and TRV the better pruning rule, both checkable without labels before training. Experiments on CIFAR-10/100 under label noise confirm both roles: the rules substantially outperform random selection where magnitude-based rules collapse, at a proxy cost of 2-4% of training.