📊 statistics

Learning with Monotone Adversarial Corruptions

This paper demonstrates that standard optimal learning algorithms for binary classification can be made to fail under a monotone adversarial corruption model—where an adversary inserts correctly labeled points—by exposing their overreliance on data exchangeability, whereas uniform convergence-based algorithms remain robust.

Original authors: Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty

Published 2026-06-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty

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 how to recognize different types of fruit. You give them a basket of apples and oranges (the "clean" data) and ask them to learn the rules. In a perfect world, the student studies the basket, and when you show them a new fruit from the same orchard later, they get it right. This works because we assume the fruits in the basket were picked randomly and independently.

This paper explores what happens when a "helpful" but tricky teacher interferes with this process.

The "Helpful" Saboteur: The Monotone Adversary

The authors introduce a character called the Monotone Adversary. Think of this adversary as a teacher who is too eager to help.

The Setup: The teacher looks at your basket of $n$ random apples and oranges.
The Twist: The teacher then adds $m$ extra fruits to the basket.
The Catch: These extra fruits are not fake. They are real apples and oranges, and the teacher labels them 100% correctly according to the true rules of the orchard.
The Deception: The teacher chooses which extra fruits to add based on exactly what was already in your basket. They might add a thousand extra apples if they see you only have oranges, or they might add specific rare fruits to confuse the pattern.

The scary part? The labels are all correct. The data is "clean" in terms of truth, but the mix of data is no longer random. It's been manipulated to break the assumption that "all data points are independent."

The Big Surprise: "More Data" Can Be Worse

In machine learning, we usually believe that "more data is better." The paper shows that in this specific scenario, adding these "perfectly labeled" extra fruits can actually break the smartest learning algorithms.

The authors tested two famous types of learning strategies:

1. The "Leave-One-Out" Strategy (The One-in-Graph Algorithm)

How it works: Imagine a student who learns by thinking, "If I remove one fruit from my basket, can I still guess the rest correctly?" They use this logic to make their final guess. This is considered one of the most optimal ways to learn.
The Failure: The adversary can add just enough extra fruits to trick this student. Even though the student is using the best possible logic, the adversary can force them to guess wrong 25% of the time (a constant error), even if the student is learning a very simple rule (like distinguishing just two types of fruit).
The Lesson: This strategy relies entirely on the idea that the data is a random shuffle. Once the adversary manipulates the shuffle, the strategy collapses.

2. The "Majority Vote" Strategy (The Ensemble)

How it works: Imagine a committee of students. Each student looks at a small, random subset of the basket, makes a guess, and then the committee takes a vote. If most students say "Apple," the final answer is "Apple." This is how many modern AI systems work (like "Bagging").
The Failure: The adversary can add extra fruits in a way that correlates the mistakes of the different students. Instead of their mistakes canceling each other out, the adversary forces a majority of the committee to vote for the wrong answer.
The Lesson: Even if you have thousands of students voting, if the data they are looking at is secretly correlated by the adversary, the "wisdom of the crowd" fails.

The Hero: The "Simple" Learner (ERM)

If the fancy, optimal strategies fail, is there anyone who can survive?

Yes. The paper points to the Empirical Risk Minimizer (ERM).

How it works: This is the "brute force" student. They simply look at the entire basket and say, "I will find a rule that fits every single fruit in this basket perfectly."
The Success: Because the adversary cannot lie about the labels (they must be correct), the true rule (the ground truth) is always a valid rule that fits the data. The "brute force" student will find a rule that fits the data well enough to generalize, even with the extra fruits.
The Result: While this student might not be the absolute fastest or most efficient learner (they might be slightly slower to learn than the theoretical best), they are robust. They don't get tricked by the manipulation. Their error rate stays low and predictable.

The "Oblivious" Exception

The paper also notes one scenario where the fancy "Leave-One-Out" strategy works again: if the adversary is Oblivious.

The Difference: An oblivious adversary adds their extra fruits without looking at your basket first. They just pick fruits randomly and add them.
The Result: Because they didn't look at your specific data to manipulate it, the randomness is preserved. The fancy algorithms work perfectly fine here.

Summary

The paper's main message is a warning to the machine learning world:
We often assume that if data is labeled correctly, we are safe. But if the selection of that data is manipulated (even if the labels are perfect), our most sophisticated and "optimal" algorithms can fail spectacularly.

Sophisticated algorithms (Leave-One-Out, Majority Voting) are fragile; they break when data independence is violated.
Simple algorithms (ERM/Loss Minimization) are robust; they keep working because they just try to fit the truth, regardless of how the data was shuffled.

This suggests that in the real world, where data is often curated or selected adaptively, the "simple" approach of minimizing error on the whole dataset might be more reliable than we thought, while our fancy theoretical guarantees might be too fragile to hold up.

Technical Summary: Learning with Monotone Adversarial Corruptions

Problem Statement
This paper investigates the extent to which standard machine learning algorithms rely on the assumptions of data independence and exchangeability. The authors introduce a monotone adversarial corruption model to isolate the role of these assumptions in generalization. In this model, an adversary observes a set of $n$ clean, i.i.d. samples drawn from a distribution $D$ and a target hypothesis $h^\star$ . The adversary then inserts $m$ additional "corrupted" points into the dataset. Crucially, these corrupted points are monotone: they are labeled according to the ground-truth function $h^\star$ . While the labels are honest, the adversary has full knowledge of $D$ , the hypothesis class $\mathcal{H}$ , and $h^\star$ , and can choose the corrupted points adaptively based on the clean samples. The learning algorithm receives the combined dataset of $n+m$ points (shuffled randomly) and must output a hypothesis with low error on a new test point drawn from $D$ .

The core tension is that while the added data is "clean" (correctly labeled), the adaptive selection of these points violates the exchangeability of the dataset. The paper asks whether standard optimal learning algorithms, which typically assume i.i.d. data, can maintain their guarantees in this setting.

Methodology and Framework
The authors formalize the Monotone Adversary (Definition 2.1), where the adversary generates corrupted points $A(x_1, \dots, x_n)$ as a function of the clean points. They also define an Oblivious Monotone Adversary (Definition 2.2), where the adversary generates corrupted points independently of the clean samples, though still with knowledge of $D$ and $h^\star$ .

The study focuses on binary classification with a hypothesis class $\mathcal{H}$ of VC dimension $d$ . The paper analyzes three primary classes of learning algorithms:

Empirical Risk Minimizers (ERM): Algorithms that output a hypothesis consistent with the training data.
Majority Voting Algorithms: Algorithms that train ERMs on subsets of the data and aggregate predictions via majority vote (e.g., Bagging, Majority-of-Three, Hanneke's algorithm).
One-Inclusion Graph (OIG) Algorithms: Algorithms based on the structural properties of the hypothesis class, specifically minimizing the maximum out-degree in a one-inclusion graph to achieve optimal error rates in the standard i.i.d. setting.

Key Contributions and Results

1. Fragility of Optimal i.i.d. Algorithms
The paper demonstrates that algorithms achieving optimal error rates ( $\Theta(d/n)$ ) in the standard i.i.d. setting can be forced into suboptimal performance by a monotone adversary.

OIG Failure: The One-inclusion Graph algorithm, which is optimal for VC classes in the i.i.d. setting, is shown to suffer a constant expected error (specifically $1/4$ ) even for VC dimension $d=1$ when faced with $n$ clean and $n$ corrupted points (Theorem 1.1, Theorem 4.4). This holds even for the "natural" orientation strategy that minimizes the maximum out-degree.
Majority Voting Failure: Any majority voting algorithm that uses subsets of size at least $t$ can be forced to suffer an expected error of $\Omega(d \log(n/d)/n)$ using only $2n/t$ corrupted points (Theorem 1.2, Theorem 4.2, Theorem 4.3). This applies to state-of-the-art optimal learners like Bagging and Majority-of-Three, which typically use subsets of size $\Omega(n)$ . The adversary exploits the adaptive nature of the corruption to correlate the subsets used by the voting algorithm, causing them to simultaneously fail.

2. Robustness of Uniform Convergence (ERM)
In contrast to the failure of OIG and majority voting, the paper shows that Empirical Risk Minimization (ERM) is robust to monotone corruptions.

Upper Bound: The authors prove that any ERM on the combined dataset (clean + corrupted) achieves an expected error of $O(d \log(n/d)/n)$ , regardless of the number of corrupted points (Theorem 1.3, Theorem 3.1).
Mechanism: The proof relies on the observation that because the adversary cannot corrupt labels, any ERM consistent with the full dataset is also consistent with the clean subset. By conditioning on the random permutation of the data, the clean points remain i.i.d. from $D$ . Thus, standard uniform convergence arguments apply to the clean subset, ensuring the ERM does not overfit the corrupted points to the detriment of the clean distribution.
Significance: This suggests that the suboptimality of ERM in the i.i.d. setting (a $\log(n/d)$ factor compared to the optimal $d/n$ ) is the "price" paid for robustness against this specific type of dependence.

3. The Role of Exchangeability
The paper highlights that the failure of OIG and majority voting is directly attributable to the lack of exchangeability.

Oblivious Adversary: If the adversary is constrained to be oblivious (corrupted points independent of clean points), the OIG algorithm recovers its optimal expected error of $O(d/n)$ (Theorem 1.4, Theorem 3.2). This confirms that the adaptive dependence introduced by the monotone adversary is the specific mechanism breaking these algorithms.

Significance and Claims
The authors claim that their results expose a fundamental overreliance on exchangeability in optimal learning algorithms.

Theoretical Insight: The work challenges the intuition that "more data is better," even when the additional data is correctly labeled. It demonstrates that seemingly helpful monotone corruptions can provably break sophisticated learning techniques (like leave-one-out and ensemble methods) that are optimal in the standard setting.
Practical Implication: The results suggest that the success of loss minimization (ERM) in modern machine learning practice may stem from its inherent robustness to certain forms of data misspecification and dependence, whereas more sophisticated techniques designed for optimal rates in i.i.d. settings may be fragile.
Open Questions: The paper identifies the optimal expected error for learning under monotone adversaries as an open problem. While ERM provides an $O(d \log(n/d)/n)$ upper bound, it remains unknown if an algorithm can achieve the optimal $O(d/n)$ rate. Furthermore, the learnability of Littlestone classes and partial/multiclass classes under this model remains an open challenge, as uniform convergence principles do not hold in those settings.

In summary, the paper establishes that while ERM offers a robust, albeit slightly suboptimal, guarantee in the presence of monotone corruptions, the currently known optimal algorithms for i.i.d. data are highly fragile to adaptive, label-correct corruptions that violate exchangeability.