🤖 machine learning

When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory

This paper demonstrates that while adding correctly labeled data can paradoxically increase a learner's error due to adversarial insertions, this vulnerability is not inherent to the data class's dimensionality but rather depends on whether the specific learner is "insertion-stable," a property that allows certain algorithms to maintain optimal error rates regardless of such additions.

Original authors: Joseph Sankoorikal Johny

Published 2026-08-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Joseph Sankoorikal Johny

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

The Paradox of Perfect Data

Imagine you are trying to teach a robot to recognize cats. You show it a thousand photos of fluffy tabbies and sleek siameses, all correctly labeled. The robot learns the rules and gets pretty good at spotting cats. Now, imagine you decide to help it out even more. You take those same photos, rotate them, zoom in, or even copy-paste them a hundred times, making sure every single new image is still correctly labeled as "cat." Common sense tells you this should only make the robot smarter, right? More data, even if it's just more of the same, should mean fewer mistakes.

But in the world of machine learning, specifically a field called statistical learning theory, things aren't always so simple. This field studies how computers learn from examples and how we can mathematically guarantee they won't get confused. The big question researchers ask is: "How many examples do we need to learn a concept perfectly?" Usually, the answer is "the more, the better." However, a new paper explores a weird twist: what if the person giving you the extra data is a sneaky trickster? Not a liar who gives you wrong labels, but a "monotone adversary." This trickster watches your original data, then adds as many correctly labeled examples as they want, but they choose them specifically to confuse the robot's learning process. The paper asks a startling question: Can adding perfect, correct information actually make a learning algorithm perform worse?

When More "Help" Becomes a Trap

This paper, written by independent researcher Joseph Sankoorikal Johny, dives deep into that paradox. The author investigates a scenario where a learning algorithm is fed a clean set of training data, followed by a flood of extra, perfectly correct examples chosen by an adversary who knows exactly what the original data looked like. The goal is to see if the algorithm can still learn the truth, or if this "helpful" noise breaks it.

The paper's main discovery is that the answer depends entirely on how the algorithm learns, not just on the type of data it's trying to learn. The author introduces a concept called insertion-stability. Think of a learning algorithm as a detective trying to solve a mystery. An "insertion-stable" detective is one who, when handed more clues (even if those clues were chosen by a villain), can only get better at narrowing down the list of suspects. Their "error zone"—the area where they might guess wrong—shrinks or stays the same, but it never grows. If a detective is insertion-stable, the villain's tricks don't matter; the detective will perform just as well as if they had only seen the original clues.

However, the paper proves that not all detectives are this stable. For certain types of learning problems, adding more correct data does hurt. The author shows that for some classes of problems, the best possible error rate gets worse by a factor of $\log(n)$ (a logarithmic factor) when this kind of adversarial data is added. This means that even with infinite correct data, the algorithm might be stuck with a higher error rate than it would have had with just a few clean examples.

The Great Dimension Mismatch

One of the most playful and surprising parts of the paper is how it debunks a long-held belief in the field. For decades, researchers have used mathematical "dimensions" (like VC dimension and Littlestone dimension) to predict how hard a learning problem is. It was generally thought that if two problems had the same dimension, they would behave the same way.

The author proves this is wrong. They construct two specific "worlds" of data (mathematical classes) that have the exact same dimensions (both equal to 2). In one world, the learning algorithm is insertion-stable; it shrugs off the adversary's tricks and learns perfectly fast. In the other world, the algorithm is not stable, and the adversary can force the error rate to be much worse, specifically $\Theta(\log(en)/n)$ instead of the clean rate of $\Theta(1/n)$ .

To make this concrete, the paper compares two scenarios:

The "Safe" World (Intersection-Closed Classes): Imagine a class of rules where combining two valid rules always creates another valid rule (like "is a red square" and "is a blue square" combining to "is a red square AND a blue square"). For these, the author proves that the "Closure" algorithm is insertion-stable. No matter how many extra correct examples the adversary adds, the error rate stays low and clean. The extra data is harmless.
The "Tricky" World (Mehrotra's Class): The author analyzes a specific, complex class of problems (built from projective planes) where the dimensions are also small, but the structure is different. Here, no matter what algorithm you use, the adversary can force the error rate to be higher. The paper proves that no "compression scheme" (a way of summarizing data) of any finite size can fix this. The penalty is baked into the problem itself.

What the Paper Rules Out

The paper is very careful about what it doesn't say. It does not claim that all learning is broken by extra data. It explicitly rules out the idea that classical dimensions (like VC dimension) can predict whether a problem will suffer from this penalty. Two problems can look identical on paper (same dimensions) but behave totally differently when an adversary is involved.

Furthermore, the paper argues against the idea that simply changing the learning algorithm can always save you. If a problem class is inherently "unstable" (like the tricky world mentioned above), no algorithm can avoid the penalty. The cost belongs to the class of problems, not the learner. Conversely, if a problem class is "stable" (like the safe world), the right algorithm (Closure) can make the extra data completely free.

The Bottom Line

The paper concludes that the question isn't just "Is the data hard?" or "Is the learner smart?" It's about the pairing of the two. If you have a learner that is insertion-stable, adding more correct data is free and safe. If you don't have one, the cost is unavoidable.

The author also points out that while they have found a way to identify "safe" learners (those that are insertion-stable), they haven't yet found a perfect mathematical "ruler" to measure why some problems are unsafe. They propose a new measure called isdim (insertion-stability dimension), but admit it's hard to calculate and currently relies on knowing the answer beforehand. The paper leaves us with a clear warning: in the age of big data, blindly adding more "correct" examples isn't always a win. Sometimes, the way you add them matters just as much as the data itself.

Technical Summary: Insertion-Stability and the Limits of Dimension-Based Theory

Problem Statement
The paper addresses a counterintuitive phenomenon in statistical learning theory: adding data known to be correctly labeled can increase the expected error of a learning algorithm. This occurs under the "monotone adversary" model introduced by Larsen, Pabbaraju, and Shetty, and analyzed by Mehrotra. In this model, an adversary observes a clean, i.i.d. training sample and appends additional examples. The only restriction is that the appended examples must be correctly labeled by the target hypothesis $h^*$ . While the labels are valid, the adversary chooses these points adaptively based on the clean sample, destroying the independence and exchangeability assumptions required for standard generalization bounds.

Mehrotra established that for concept classes with VC dimension $d \ge 2$ , the optimal expected error rate under such insertions is $\Theta((d/n) \log(en/d))$ , which is a logarithmic factor worse than the clean PAC rate of $\Theta(d/n)$ . The central question this paper investigates is: Which structural properties of a concept class determine whether it suffers this logarithmic penalty, and which allow it to retain the clean rate? The paper argues that classical dimensions (VC dimension and Littlestone dimension) are insufficient predictors of this behavior.

Methodology
The author introduces a new property of learning algorithms called insertion-stability. A learner is defined as insertion-stable if:

It is permutation-invariant (its output depends only on the multiset of labeled examples, not their order).
It is superset-monotone regarding its error region: for any two correctly labeled multisets $S \subseteq T$ , the error region of the learner on $T$ is a subset of the error region on $S$ .

The core methodological contribution is a reduction lemma (Theorem 3). The author proves that if a learner is insertion-stable, its risk under an adaptive monotone adversary is almost surely dominated by its risk on the clean sample alone. Crucially, this proof does not rely on the independence of the inserted points; it relies solely on the fact that the inserted points form a correctly labeled superset of the clean sample. This allows the transfer of any high-probability or expectation bounds from the clean i.i.d. setting to the adversarial setting without modification.

The paper then analyzes specific concept classes and learners:

Closure Algorithm: The author shows that the Closure algorithm (which outputs the intersection of all hypotheses in the version space) is insertion-stable for any class.
Compression Schemes: They extend the analysis to consistent, permutation-invariant, superset-monotone sample compression schemes.
Counterexamples: They examine specific classes, including $H_{\le d}$ (concepts with at most $d$ positive points) and $H_{prime}$ (a construction by Mehrotra based on projective planes), to test the limits of dimension-based theories.

Key Contributions and Results

The Insertion-Stability Lemma: The paper establishes that insertion-stability is a sufficient condition for immunity to monotone insertions. If a learner is insertion-stable, adding correctly labeled data can never increase the error region. Consequently, any learner that is insertion-stable retains the clean-sample error rate (including high-probability bounds) regardless of the number of insertions or the adversary's adaptivity.
Closure is Insertion-Stable: The author proves that the Closure algorithm is insertion-stable. For intersection-closed classes (where the intersection of any two concepts in the class is also in the class), Closure is a valid learner. This implies that for all intersection-closed classes, the clean rate of $E[\text{Err}] \le (21d + 34)/n$ holds even under arbitrarily many adaptive monotone insertions. This result is explicit and free of logarithmic factors.
Failure of Dimension-Based Theory: The paper demonstrates that neither VC dimension nor Littlestone dimension predicts the rate under monotone insertions.
- Case 1: $H_{\le 2}$ and $H_{prime}$ both have VC dimension 2 and Littlestone dimension 2. However, $H_{\le 2}$ (which is intersection-closed) retains the clean rate $\Theta(1/n)$ , while $H_{prime}$ suffers the logarithmic penalty $\Theta(\log(en)/n)$ .
- Case 2: Intervals on $\mathbb{R}$ have VC dimension 2 but unbounded Littlestone dimension. Despite the unbounded Littlestone dimension, they retain the clean rate because they are intersection-closed.
- Conclusion: No function of VC and Littlestone dimensions can determine the monotone-insertion rate.
Impossibility for Compression Schemes on Hard Classes: For the class $H_{prime}$ , the author proves a stronger negative result: no consistent, permutation-invariant, superset-monotone sample compression scheme of any finite size can achieve the clean rate. This rules out a broad family of potential algorithms, not just a specific one. The proof relies on the fact that if such a scheme existed with size $k$ , it would achieve a rate of $O(k/n)$ , which contradicts the known lower bound of $\Omega(\log(en)/n)$ for $H_{prime}$ for sufficiently large $n$ .

Significance and Claims
The paper claims that the difficulty of learning under monotone insertions is not an intrinsic property of the concept class alone, nor solely a property of the learner, but rather a property of the pairing between the class and the learner.

Sufficiency vs. Characterization: The author explicitly states they provide a sufficient condition (insertion-stability) for immunity, not a full characterization. They do not claim to have identified a combinatorial quantity that is both necessary and sufficient for the clean rate.
The Role of the Learner: The paper emphasizes that for classes where an insertion-stable learner exists (like intersection-closed classes), correct additions are "free." For classes where no such learner exists (like $H_{prime}$ ), the logarithmic penalty is unavoidable for any learner that satisfies the standard consistency and monotonicity properties.
Limitations: The paper acknowledges that its proposed measure, isdim (the size of the smallest insertion-stable compression scheme), is currently a bookkeeping device. It is defined by the existence of a scheme rather than an intrinsic structural property of the class, and it cannot be computed for a class without already knowing the class's rate or exhibiting a specific scheme.
Open Problems: The author identifies the search for a combinatorial quantity (analogous to VC or Littlestone dimension) that characterizes the rate under monotone insertions as a major open problem. They note that current lower-bound techniques (shattering) have not yet been adapted to this specific "helpful" adversary model.

In summary, the paper shifts the focus from "which classes are hard" to "which learner-class pairs are robust," demonstrating that classical dimensions fail to predict robustness against correctly labeled, adaptive data insertions, and that intersection-closedness (via the Closure algorithm) is a sufficient structural property for immunity.