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

arXiv:2605.07551 · cs.LG · Submitted 2026-05-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Hi, I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Rank-Variance Scores for Importance Sampling and Data Pruning under Label Contamination".

Jane: Here's the gist of the paper. The gist The authors propose Disagreement-Regularized Importance Sampling (DR-IS), a sub-sampling method based on loss rank-disagreement across an independent proxy ensemble, to prevent standard Importance Sampling from collapsing under adversarial label corruption by redirecting sampling mass to high-disagreement boundary examples.

Tom: Failure Mode Characterization The paper formalizes the vulnerability of standard Importance Sampling (IS) under ε-contamination, proving that any score non-decreasing in per-sample loss over-allocates to corrupted points.

Jane: This occurs because corrupted examples often yield the highest norms, causing IS to over-allocate mass to noise which over-parametrized networks then memorize.

Tom: This failure mode is verified in Section 6.2.

Paper summary: Tom: So we're looking at this paper called "Rank-Variance Scores for Importance Sampling and Data Pruning under Label Contamination." Basically, standard importance sampling methods fail when you have label noise because they tend to pick those high-loss or large-gradient examples, which are often the ones that are actually corrupted by bad labels.

Jane: That sounds really practical. So what's the main idea of this paper? What are they trying to fix with this new approach?

Tom: They propose something called Disagreement-Regularized Importance Sampling, or DR-IS. It uses loss rank disagreement across a set of independent proxy models to redirect the sampling mass towards examples that have high disagreement, specifically boundary examples.

Lu: The core idea is that instead of just looking at one loss score, they use the variance of loss ranks from several different proxies to separate clean data from corrupted data. They assume that mislabeled examples will consistently rank hardest across these proxies because they are outliers in a structural sense.

Meng: But this sounds complicated. What’s the actual problem they’re solving? Is it just about getting better accuracy, or is it about making the whole process more stable when you have noisy labels?

Jane: It's really about stability under contamination. The paper shows that a score that only goes up as the loss increases will always over-allocate to those corrupted points, which is why standard importance sampling collapses in this scenario.

Tom: Exactly. They formalize this failure using an epsilon contamination model and then they prove some concentration bounds showing that the empirical rank disagreement of bulk corrupted examples is bounded above by O(p log(N/delta)/K) with probability one minus delta, which is a big deal for control.

Lu: And they also get a lower bound on the boundary-clean examples, which when combined with a positive structural expectation gap between the two groups, certifies a strict separation between bulk corrupted and boundary-clean data.

Jane: So if you're just listening, what does this mean for your model training? Does it make the whole process safer?

Tom: It means that when you use DR-IS as a static pruning rule—selecting the top alpha N examples based on their variance—it can control the contamination rate of the selected subset. They show that empirically, DR-IS reduces subset contamination five times over magnitude scores on CIFAR and Food-one hundred one which is a significant jump from just using uniform SGD <ref:2605.07551#pg2,DR-IS reduces subset contamination>.

Paper summary: Meng: Five times? That’s a big number when you're talking about deployment where you can't afford massive amounts of extra data or computation. How much extra cost are we looking at for this DR-IS method itself compared to the baseline?

Tom: The computational overhead is low, less than ten percent of the total compute budget, and they say it’s amortized and readily parallelized across different hardware setups like A100 forty GB and A100 eighty GB nodes.

Jane: It seems they’ve managed to make a method that's computationally efficient while providing a statistical guarantee against label noise leakage in the selected data. What about why this works when other methods don't?

Lu: The key difference is that DR-IS uses cross-sectional disagreement across independent proxies, whereas magnitude-based methods, like those using the Error L2-norm, are relying on a single measure within one proxy. That’s what makes them collapse under targeted high-norm attacks.

Tom: They contrast it with Area Under the Margin ranking, which uses training dynamics statistics from just one proxy to rank things. DR-IS uses that ensemble disagreement to get a uniform finite-sample identification guarantee that is qualitatively different from the pairwise AUROC bound you might get from AUM.

Jane: So, for someone who isn't reading papers and just wants to know what this means for their next training run, what's the simple version of what they found?

Tom: The simple version is that if you have noisy labels, don't just pick the examples that look like they have the biggest errors; use a score based on how much different models disagree on those examples. This points you toward clean examples near the decision boundary instead of just high-loss outliers.

Lu: It’s about exploiting that structural assumption—the idea that corrupted ranks will be consistently high across proxies—to certify separation between the two groups of data, which is what Theorem one is all about <ref:2605.07551#pg1>.

Meng: If I'm thinking about deploying this to a real production system, I have to wonder how stable those K independent proxies are when the underlying model architecture changes. Does it require me to retrain every single proxy ensemble?

Paper summary: Tom: The paper suggests that even a homogeneous ensemble of three lightweight proxies is sufficient for neural network models, because the empirical separation gap remains positive regardless of the architectural diversity you introduce.

Jane: So, what’s the final word on this paper? What is its main contribution to people who aren't deep into the math?

Tom: The main contribution is providing explicit finite-sample concentration certificates and a contamination bound that limits how much noise can leak from the statistical tail of corrupted points when you use DR-IS. It moves beyond just showing better performance to giving you a verifiable guarantee about the noise level in your final selected subset.

Lu: This work extends ideas from ensemble disagreement in active learning and Bayesian active learning to this specific setting, adapting it to the SGD importance sampling setting by connecting disagreement directly to noise filtration formalized through that high-quantile separation.

Meng: From an engineering standpoint, DR-IS gives us a concrete rule—a static pruning rule based on rank variance—and an online distribution that preserves unbiased gradient estimation without needing extra clean data during the training phase. That’s something I can actually think about implementing.

Jane: It sounds like it offers a robust way to handle label noise without requiring you to spend massive amounts of time or compute trying to perfectly filter out every single noisy point individually.

Tom: Right, so we've covered the core idea of DR-IS, how it beats magnitude-based methods with five times better contamination reduction on CIFAR and Food-one hundred one and the theoretical backing from concentration bounds and structural assumptions <ref:2605.07551#pg2,on CIFAR and Food-101>.

Lu: The paper establishes that this rank-variance score is non-monotone in terms of loss, which is what they say is a necessary condition for a useful score to prevent over-allocating mass to corrupted points.

Jane: So, looking at the authors, Csongor Horváth and Ida-Maria Sintorn and Prashant Singh are the people who put together this framework based on these rank disagreements. They’ve built a method that is very specific about how it handles label contamination through this variance measure.

Tom: Exactly. The paper "Rank-Variance Scores for Importance Sampling and Data Pruning under Label Contamination" gives us a concrete statistical tool to manage the trade-off between sampling efficiency and robustness against label noise in deep learning models.

Conclusion: Tom: So we’ve been talking about this paper called "Rank-Variance Scores for Importance Sampling and Data Pruning under Label Contamination."

Jane: Right, so basically, this paper is looking at how to make importance sampling methods work when you have bad labels mixed in the data.

Tom: Yeah, it focuses on using loss rank disagreement across multiple proxy models to find a better way to sample.

Lu: The authors are Csongor Horváth and Ida-Maria Sintorn and Prashant Singh. They’re building this framework around how loss ranks behave under contamination.

Meng: I see they're looking at structural assumptions about the data—like how corrupted ranks stay high across different models—to separate the clean points from the noisy ones.

Jane: So, what does this actually mean for someone who just runs a model and gets some noise back?

Tom: It means that instead of just picking examples with high loss, you use this rank variance score to pick examples that are on the edge but where different models disagree a lot.

Lu: The authors show that this approach provides explicit concentration certificates and a contamination bound limiting how much noise can leak from the statistical tail of corrupted points.

Jane: A contamination bound? Can you explain what that means for deployment?

Tom: It means you get a mathematical guarantee about how much label noise will affect your final selected subset, not just an empirical observation.

Meng: If this method works, it suggests we can build more stable sampling and pruning pipelines without needing to manually clean up every single noisy data point beforehand.

Jane: And the results show that this approach substantially outperforms magnitude-based rules when the labels are corrupted.

Tom: That’s because those magnitude rules just collapse under label noise, but DR-IS redirects the sampling mass effectively toward clean boundary examples.

Lu: The method’s strength is that it works even if you introduce architectural diversity in your models, because the empirical separation gap stays positive regardless of that diversity.

Jane: So, what’s next for this research? Where do they go from here?

Csongor Horváth, Ida-Maria Sintorn, Prashant Singh

Uppsala University

cs.LG

Submitted: 2026-05-08

Updated: 2026-10-16

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: The gist The authors propose Disagreement-Regularized Importance Sampling (DR-IS), a sub-sampling method based on loss rank-disagreement across an independent proxy ensemble, to prevent standard

Key concepts

$\epsilon$-contamination model: This model assumes the training data is mixed with a small fraction ($\epsilon$) of corrupted labels. The paper formalizes how standard importance sampling fails under this condition, showing that scores non-decreasing in loss will over-allocate to these noisy points.
Empirical Rank Disagreement: This is calculated as the sample variance of normalized loss ranks obtained from $K$ independent proxies trained on the data. High disagreement between proxy rankings indicates an example's rank is unstable, often marking it as a boundary example or a corrupted point.
Disagreement-Regularized Importance Sampling (DR-IS): This is a static pruning rule that selects examples based on their rank variance ($\sigma b^2_i$). It prioritizes clean boundary data over bulk corrupted data when the separation between these two groups is positive, effectively mitigating contamination leakage.
Structural Assumptions (Assumption 2 & 3): These assumptions leverage 'simplicity bias' to keep corrupted loss ranks consistently high and target clean points near decision boundaries whose marginal status makes them sensitive to training noise. These structural properties allow the theoretical guarantees for DR-IS to hold in finite samples.

Terminology

Benchmark — 1× in this paper · explained in 2 episodes
Data Pruning — 1× in this paper · explained in 2 episodes
Pruning — 1× in this paper · explained in 4 episodes
Robustness — 1× in this paper · explained in 6 episodes
Standard Importance Sampling — 1× in this paper

Summary

The gist The authors propose Disagreement-Regularized Importance Sampling (DR-IS), a sub-sampling method based on loss rank-disagreement across an independent proxy ensemble, to prevent standard Importance Sampling from collapsing under adversarial label corruption by redirecting sampling mass to high-disagreement boundary examples.

Failure Mode Characterization

The paper formalizes the vulnerability of standard Importance Sampling (IS) under ε-contamination, proving that any score non-decreasing in per-sample loss over-allocates to corrupted points. This occurs because corrupted examples often yield the highest norms, causing IS to over-allocate mass to noise which over-parametrized networks then memorize. This failure mode is verified in Section 6.2.

Theoretical Framework

The framework relies on an ε-contamination model where the training set is partitioned into clean and corrupted data, and it defines the empirical rank disagreement as the sample variance of normalized loss ranks across K independent proxies. Structural assumptions are crucial, including Assumption 2 (Quantile concentration of corrupted ranks), which leverages simplicity bias to keep corrupted loss ranks consistently high across P [like AUM, 34]. Assumption 3 targets clean points near the decision boundary whose marginal status makes them highly sensitive to stochasticity in the training pipeline.

Concentration and Separation Theorems

Theorem 1 establishes finite-sample concentration bounds showing that the empirical rank disagreement of bulk corrupted examples is bounded above by O(p log(N/δ)/K) with probability 1 − δ. When the structural expectation gap ∆′ between the two groups is positive, these bounds certify strict separation between bulk corrupted and boundary-clean data. Theorem 2 provides an impossibility result for magnitude-based IS as a class, showing that no choice of non-decreasing score within this family can avoid an Ω(ε) allocation to Dcorr.

DR-IS Framework and Empirical Validation

DR-IS proposes a static pruning rule selecting the top αN examples with the highest σb 2 i, which prioritizes clean boundary data over bulk corrupted data when the separation gap ∆' is positive. The online extension uses a smoothed IS distribution defined by q DR i ∝ σb 2 i + ξ σb squared, which prevents importance sampling from over-allocating mass to high-loss outliers. Empirically, DR-IS reduces subset contamination 5× over magnitude scores on CIFAR and Food-101.

Comparison to Other Methods

DR-IS is contrasted with Area Under the Margin ranking (AUM), which uses training-dynamics statistics like margin trajectories within a single proxy, while DR-IS exploits cross-sectional disagreement across independent proxies. While AUM achieves near-perfect noise rejection under extreme noise, DR-IS provides a uniform finite-sample identification guarantee that is qualitatively distinct from the pairwise AUROC bound derivable for AUM. The study also investigates the failure mode of hybrid scores, showing that combining gradient norms with rank-variance does not yield a robust mechanism under contamination.

Proxy Diversity and Practical Scope

The analysis shows that the empirical resolution is not contradictory to the mechanics of Theorem 1, as the validity of the theorem relies on a simplicity bias (Assumption 2) and boundary stochasticity (Assumption 3), rather than deep-learning-specific artifacts. The study demonstrates that a homogeneous ensemble suffices for neural network models, as the empirical separation gap remains positive regardless of architectural diversity. The computational overhead is amortized and remains below 10% of total compute budget.

Conclusion

Disagreement-Regularized Importance Sampling improves the efficiency of importance sampling mitigating the vulnerability to adversarial label corruption by redirecting sampling mass to high-disagreement boundary examples. The method provides explicit finite-sample concentration certificates and a contamination bound limiting noise leakage from the statistical tail of corrupted points. This approach offers improved robustness in the loss-aligned regime alongside explicit finite-sample concentration certificates and a contamination bound limiting noise leakage from the statistical tail of corrupted points. The original motivation for the hybrid score is to mitigate DR-IS’s clean-data cost — the tendency to aggressively filter out easy clean samples in favor of the clean boundary. This mix would successfully reintroduce easy clean samples into the training batches under limited contamination, without actively rewarding high-loss outliers. The rigorous contamination bound derived in Theorem 1(iii) would degrade gracefully toward the base dataset corruption rate ε, rather than collapsing entirely as it does when mixed with gradient norms. This blending rank-variance with uniform probability provides a safe mechanism to tune the boundary-heavy bias of DR-IS. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. The wall-clock measurements reported in Table 9 demonstrate that the target training duration is essentially uniform across all evaluated data pruning and importance sampling methodologies. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required. The observed within-cell variance is largely attributable to the dispatch of runs to a heterogeneous mix of A100 40 GB and A100 80 GB nodes. This cost is amortized and readily parallelized, achieving a total overhead below 10% with no auxiliary clean data required<ref:2605.

Improvements for AI systems

Robust Importance Sampling for Training: The DR-IS framework can be used to select a subset of training examples by prioritizing those with high rank disagreement across an ensemble of lightweight proxies, effectively avoiding high-norm outliers that cause standard importance sampling to over-allocate mass to noise.
Contamination Control in Subset Selection: By leveraging the concentration theorem, DR-IS provides non-asymptotic control over noise leakage in a selected subset, bounding the contamination rate from the escaping tail of corrupted points using Theorem 1(iii).
Noise Robustness via Disagreement Scoring: The system can be implemented to remain stable under targeted high-norm attacks that break magnitude-based methods like Error L2-norm (EL2N) by utilizing cross-sectional disagreement instead of relying on a score non-decreasing in per-sample loss over time, as proven by Theorem 2.
Dynamic Importance Sampling: The online version of DR-IS can be used to define an unbiased gradient estimation distribution qDR i proportional to the rank disagreement plus a smoothing constant ξ sigma b 2, which preserves unbiased gradient estimation while preventing importance sampling from over-allocating mass to high-loss outliers.
Architecture-Agnostic Scoring: The use of normalized loss ranks (rho i in (0, 1]) establishes an inherently proxy independent and scale free metric, allowing the system to utilize any proxy ensemble size K without being constrained by architecture-specific scaling issues seen in margin-based methods like Area Under the Margin ranking.

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