🤖 machine learning

Disagreement-Regularized Importance Sampling for Adversarial Label Corruption

This paper introduces Disagreement-Regularized Importance Sampling (DR-IS), a robust sub-sampling method that leverages loss rank-disagreement across an ensemble to effectively mitigate adversarial label corruption and outperform magnitude-based approaches like EL2N, backed by rigorous finite-sample concentration bounds that guarantee strict separation between clean and corrupted examples.

Original authors: Csongor Horváth, Ida-Maria Sintorn, Prashant Singh

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Csongor Horváth, Ida-Maria Sintorn, Prashant Singh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a student (an AI model) to recognize different animals using a massive textbook of pictures. Normally, you'd show the student every picture in the book, one by one. But what if someone had secretly swapped the labels on some of the pictures? For example, they took a picture of a cat and labeled it "dog," or a picture of a car and labeled it "airplane."

If you just show the student the "hardest" pictures—the ones where the student keeps getting it wrong—they might actually be the ones with the fake labels. The student gets confused, memorizes the wrong answer, and fails the test. This is the problem the paper addresses: Importance Sampling. This is a technique where you try to speed up learning by focusing only on the "hardest" examples. But under label corruption, focusing on the hardest examples is like focusing on the biggest liars in the room.

The authors propose a new method called DR-IS (Disagreement-Regularized Importance Sampling) to fix this. Here is how it works, using simple analogies:

1. The Problem: The "Loud Liar" Trap

In standard methods, if a picture is very hard to classify (high "loss" or error), the system assumes it's a very important, difficult example that needs more attention.

The Trap: When labels are corrupted (fake), those fake examples often look extremely hard to the AI. They scream, "Look at me! I'm confusing!"
The Result: The AI spends all its time studying these fake examples, memorizing the lies, and forgetting the truth.

2. The Solution: The "Committee of Judges"

Instead of asking, "How hard is this example?" (which the liars fake well), DR-IS asks, "Do the judges agree on how hard this is?"

Imagine you have a panel of three different judges (called "proxies"). They all look at the same set of pictures to grade them.

The Fake Examples (The Liars): Because the labels are wrong, the judges are all confused in the same way. They all agree, "This is a terrible example, it's impossible!" Their scores are consistently high and consistent. They agree on the lie.
The Real Hard Examples (The Truth): These are pictures of animals that are genuinely tricky (like a blurry cat that looks like a dog). One judge might think, "That's a cat." Another might think, "No, that's a dog." A third might be unsure. They disagree. Their scores fluctuate.

The Magic: DR-IS looks for the disagreement.

If the judges all agree an example is "hard," it's likely a fake (corrupted) example. DR-IS ignores it.
If the judges disagree about whether an example is hard, it's likely a real, tricky example. DR-IS picks this one to study.

3. The "Simplicity Bias" (Why it works)

The paper relies on a quirk of how AI learns, called "simplicity bias."

When the AI sees a fake label (e.g., a cat labeled "dog"), it eventually realizes, "Wait, this doesn't make sense," but it keeps getting it wrong because the label is wrong. All the judges eventually settle into a pattern of being consistently confused by this specific lie.
Real, difficult examples don't have a single "wrong" pattern. They are genuinely ambiguous. The judges flip-flop on them.
DR-IS filters out the consistent liars and keeps the ambiguous truth-tellers.

4. The Results: What the Paper Found

The authors tested this on standard image datasets (like CIFAR and Food-101) where they intentionally added fake labels.

Old Methods: When they tried to focus on the "hardest" examples, the AI's performance crashed. It memorized the lies.
DR-IS: By focusing on the examples where the judges disagreed, the AI avoided the lies.
- In tests with 25% of the labels being fake, DR-IS kept the AI's accuracy high, while other methods failed completely.
- It reduced the amount of "fake data" the AI studied by about 5 times compared to other methods.

5. The Trade-off

There is a small cost. Because DR-IS focuses on the "tricky" real examples, it sometimes skips the "easy" real examples (like a clear picture of a cat).

On simple tasks: The AI might learn slightly slower because it ignores the easy stuff.
On complex tasks or when there are lies: This strategy is a lifesaver. It prevents the AI from being tricked.

Summary

Think of DR-IS as a teacher who stops listening to the student who is shouting the loudest (the corrupted data) and instead pays attention to the students who are debating the answer (the clean, hard data). By looking for disagreement among a panel of judges rather than just difficulty, the system can spot the liars and keep the learning process honest.

The paper proves mathematically that this works and shows that with just three simple "judge" models, you can filter out a massive amount of noise without needing extra clean data or expensive computing power.

Technical Summary: Disagreement-Regularized Importance Sampling for Adversarial Label Corruption

Problem Statement

Standard Importance Sampling (IS) in Stochastic Gradient Descent (SGD) aims to reduce estimator variance by prioritizing examples with high gradient norms or high loss values. However, this magnitude-based approach suffers a critical failure mode under $\epsilon$ -contamination (adversarial label corruption). In such scenarios, corrupted examples often exhibit the highest gradient norms or loss values. Consequently, standard IS over-allocates sampling mass to these adversarial outliers, causing over-parameterized networks to memorize noise rather than learn the underlying signal. Existing magnitude-based pruning methods (e.g., EL2N, GraNd) and training-dynamics approaches (e.g., AUM) either collapse under targeted high-norm attacks or lack rigorous finite-sample guarantees regarding noise exclusion.

Methodology: Disagreement-Regularized Importance Sampling (DR-IS)

The authors propose DR-IS, a robust subsampling and reweighting framework that shifts the selection criterion from loss magnitude to loss rank disagreement across an ensemble of independent proxy models.

Core Mechanism

Proxy Ensemble: A set of $K$ lightweight proxy models ( $h_1, \dots, h_K$ ) are trained on the potentially corrupted dataset $D$ for a few epochs. These proxies are trained with different seeds, initializations, or architectures to induce stochasticity.
Rank Disagreement Score: For each example $i$ , the normalized loss rank $\rho_i(h_k)$ is computed for each proxy. The selection score $\hat{\sigma}^2_i$ is the sample variance of these ranks across the ensemble:
$\hat{\sigma}^2_i = \frac{1}{K} \sum_{k=1}^K (\rho_i(h_k) - \bar{\rho}_i)^2$
Selection Logic:
- Corrupted Bulk: Under the "simplicity bias" of SGD, proxies consistently assign high loss ranks to corrupted labels (which contradict the dominant features), resulting in low rank variance (stability).
- Clean Boundary: Clean examples near the decision boundary are sensitive to training stochasticity, causing their loss ranks to fluctuate significantly across the ensemble, resulting in high rank variance (instability).
- Easy Clean: Clean examples far from the boundary have consistently low loss ranks, resulting in low variance.
- DR-IS Strategy: The method selects examples with the highest $\hat{\sigma}^2_i$ , effectively prioritizing the "boundary-clean" data while filtering out the "bulk corrupted" data.

Implementation Variants

Static Pruning: Selects the top $\alpha N$ examples with the highest disagreement scores to form a robust subset $S_{DR-IS}$ . The target model is trained on this subset for $1/\alpha$ times more epochs to maintain total gradient steps.
Online IS: Defines a sampling distribution $q_i \propto \hat{\sigma}^2_i + \xi \bar{\sigma}^2$ (where $\xi$ is a smoothing constant) to reweight gradients during training, preserving unbiased estimation while avoiding high-loss outliers.

Key Contributions

Failure-Mode Characterization (Theorem 2): The authors formalize that any importance sampling score that is non-decreasing with respect to per-sample loss (including gradient norms) inevitably over-allocates mass to corrupted points under $\epsilon$ -contamination. This establishes an impossibility result for magnitude-based IS in the presence of loss-aligned adversarial attacks.
Concentration Theorem (Theorem 1): The paper proves finite-sample concentration bounds for the rank-disagreement score. It demonstrates that with probability $1-\delta$ $1 - δ$ , the empirical rank disagreement of bulk corrupted examples is bounded above, while that of boundary-clean examples is bounded below.
- The separation gap scales as $O(\sqrt{\log(N/\delta)/K})$ .
- When the structural expectation gap $\Delta'$ is positive, the method certifies strict separation between the two groups.
Subset Contamination Certificates: The authors provide the first non-asymptotic control over noise leakage in the selected subset. They derive an explicit upper bound on the contamination rate of the selected subset in terms of the "escaping tail" of corrupted points, the tail rank-variance, and the keep-fraction $\alpha$ .
The DR-IS Framework: A practical method using $K=3$ lightweight proxies that maintains low computational overhead (<10%) while preventing the memorization of outliers.
Complementarity with AUM: The paper contrasts DR-IS with Area Under the Margin (AUM). While AUM exploits temporal fluctuations within a single proxy, DR-IS exploits cross-sectional disagreement across independent proxies. The authors provide a uniform finite-sample identification guarantee for DR-IS that is qualitatively distinct from the pairwise AUROC bounds associated with AUM.

Empirical Results

Experiments were conducted on CIFAR-10, CIFAR-100, and Food-101 under both uniform symmetric noise and targeted high-norm attacks (where labels of the top- $\nu$ gradient norm examples are flipped).

Robustness to Targeted Attacks: Under 25% targeted noise, magnitude-based methods (EL2N, Consensus-loss) collapsed to near-chance accuracy (e.g., 9.39% on CIFAR-10). In contrast, DR-IS maintained high accuracy (81.86% on CIFAR-10, 60.96% on CIFAR-100), outperforming uniform SGD by +9.5 percentage points on CIFAR-10.
Subset Contamination: DR-IS reduced the fraction of corrupted examples in the selected subset to ~5-7%, compared to ~86% for EL2N and ~0.25% (chance) for random sampling.
Clean Data Performance: On clean data, DR-IS showed a minor deficit on simple tasks (CIFAR-10, -0.64 pp) due to its bias toward boundary examples but achieved gains on complex tasks (CIFAR-100, +0.56 pp). The online variant tracked uniform SGD performance within ~1 pp on clean data.
Comparison with AUM: While AUM also performed well, DR-IS offered superior fidelity at moderate corruption levels and lower keep-fractions. AUM demonstrated superior stability under extreme noise ( $\epsilon \ge 0.40$ ) but incurred a higher penalty on clean data in the Food-101 natural noise setting.

Significance and Claims

The paper claims that DR-IS addresses a fundamental vulnerability in importance sampling by leveraging ensemble disagreement rather than loss magnitude.

Theoretical Rigor: It provides the first explicit, non-asymptotic certificates for noise exclusion in importance sampling, bounding the contamination rate of the selected subset.
Mechanistic Insight: It identifies that the "simplicity bias" of SGD proxies causes corrupted labels to be consistently penalized (low variance), while clean boundary examples are sensitive to stochasticity (high variance). This bimodal distribution allows for robust separation.
Practical Utility: The method offers a computationally efficient (<10% overhead) and robust alternative to standard IS and data pruning, particularly effective against targeted high-norm attacks that defeat magnitude-based heuristics.

The authors acknowledge limitations, noting that the method relies on the existence of a sufficiently rich boundary set (Assumption 3) and the "simplicity bias" of proxies (Assumption 2). In synthetic settings with low-complexity proxies or uniform noise where these assumptions fail, the method may not separate corrupted data effectively. However, on standard benchmarks with deep learning proxies, the empirical separation consistently outpaces theoretical worst-case bounds.