When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification

summary

The gist

The gist: Adaptive monotone additions can destroy learnability altogether in both multiclass classification and partial binary concept learning, while oblivious additions remain harmless for general

In short

Adaptive monotone additions can completely destroy learnability in multiclass and partial binary settings, a result previously unexpected. While oblivious additions are harmless for general learners, adaptive adversaries can make proper learning arbitrarily expensive and destroy Empirical Risk Minimization (ERM) under certain conditions. This establishes a sharp threshold between $o(n)$ and $\Theta(n)$ additions for ordinary PAC learnability.

Key concepts

Adaptive Monotone Adversaries: These are adversaries that can strategically add data points to the training set in an adaptive manner, observing the learner's progress. They are particularly powerful in multiclass and partial binary settings, capable of rendering previously learnable problems unlearnable if they insert exactly $n$ points.
Oblivious Additions: These are additions where the adversary cannot see the specific data points being added to the training set. The paper shows that oblivious additions remain benign for general learners, meaning ordinary PAC learnability is preserved when the number of such additions is $o(n).
Proper Learning and ERM Fragility: Proper learning and Empirical Risk Minimization (ERM) are especially vulnerable to monotone corruptions. Even a linear number of oblivious additions can increase the sample complexity for proper learning arbitrarily, potentially destroying every ERM rule.
DS Dimension: This is a measure used to characterize the complexity of a hypothesis class, similar to VC dimension. The paper uses DS dimension to show that certain classes with low DS dimension (like 2 in multiclass) become unlearnable under adaptive monotone adversaries.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 25 episodes
Sample Complexity — explained in 20 episodes
Retrieval-Augmented Generation (RAG) — explained in 19 episodes
Federated Learning — explained in 17 episodes
Flow Matching — explained in 17 episodes
Quantum Fisher Information (QFI) — explained in 17 episodes

This episode discusses

The paper

When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification · Read on arXiv

Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju

University of Southern California · Stanford University

Optimal learners are tailored to exploit the i.i.d. data assumption underlying the classic PAC model. What if an i.i.d. training sample were corrupted with correctly labeled examples drawn from an otherwise unrelated, even adversarial source? This model of learning with monotone adversarial corruptions was recently introduced by Larsen et al. (2026), who demonstrated that all known optimal binary learners suffer increased error rates in this setting, from O(d / n) in the PAC model to Ω(d (n / d) / n) under monotone corruption. Mehrotra (2026) proved this logarithmic factor to be necessary for binary classification, but left open the consequences of corruption for more general learning settings, such as multiclass classification and partial binary concept classes. As our primary result, we demonstrate that monotone adversaries are frighteningly more powerful in each of these settings. We exhibit a learnable multiclass problem, of DS dimension only 2, that becomes altogether unlearnable under a monotone adversary, and show an analogous result for partial binary concept classes. These results are achieved by an adaptive adversary permitted to view the original i.i.d. training set S and to insert b < infinity corrupted datapoints into S. In the multiclass example, the adversary need only insert a linear number b = S = n of datapoints. We complement these impossibility results by proving that every class remains learnable when the number of adaptive additions is o(n), which our previous multiclass lower bound proves to be tight. We further observe that the classic multiclass error rate of O(d DS / n) remains achievable against adaptive adversaries restricted to a known constant budget b = O(1), against semi-adaptive adversaries viewing only a p-fraction of S for p in (0, 1), and against oblivious adversaries that cannot view S.

Transcript

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

Tom: 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: "When Clean Data Hurts".

Jane: The gist: Adaptive monotone additions can destroy learnability altogether in both multiclass classification and partial binary concept learning,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're talking about this paper, "When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification." Jane, what's the big picture takeaway from that title?

Jane: It sounds like it’s about how adding data that is perfectly labeled—monotone corruption—can actually hurt a learning system. It suggests we can't just assume the training data is coming from some simple independent and identically distributed process anymore.

Lu: Exactly, Jane, because the authors show that this specific type of corruption makes things much worse than we thought for more complex problems like multiclass classification or partial binary concept learning <ref:2608.20480#pg1>.

Meng: I’m wondering if this means that when we build models, we can't just rely on the assumption that our training data is clean and i.i.d., because someone could be injecting perfectly labeled examples to trick us <ref:2608.20480#pg3>.

Lalam: The paper shows that optimal learners for binary classification suffer increased error rates, going from O(d/n) in the standard PAC model up to Omega of d log(n/d)/n under this monotone corruption <ref:2608.20480#pg1>.

Tom: That logarithmic factor, that log term, is what really gets my attention because it suggests a significant penalty for this type of data injection compared to the standard scaling laws we usually see <ref:2608.20480#pg1>.

The paper's summary: Jane: Okay, so to summarize what the authors are showing in "When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification," they demonstrate that adaptive monotone adversaries are much more powerful than previously understood, especially in multiclass and partial binary settings <ref:2608.20480#pg1>.

Tom: They specifically show that a learnable multiclass problem with dimension only two becomes completely unlearnable under a monotone adversary if they insert exactly n data points into the original set of n i.i.d. points <ref:2608.20480#pg1>. That's a pretty strong result about destroying learnability entirely <ref:2608.20480#pg1>.

Lu: And it extends that idea to partial binary concept learning, where they show a class with at most eighteen of the VC dimension becomes nonlearnable under an adaptive adversary after inserting a finite number of points <ref:2608.20480#pg2>. This resolves a question raised by Larsen et al. in two thousand twenty-six about what happens when corruption goes beyond binary settings <ref:2608.20480#pg1>.

Meng: So, it means that for certain problem sizes or class complexities, the introduction of perfectly labeled but adversarial examples can completely break the learning process <ref:2608.20480#pg1>. That’s a serious deployment risk if we aren't careful about data provenance.

Lalam: The core idea is that optimal learners are tailored for i.i.d. data, but when you introduce these monotone adversarial corruptions, they suffer these increased error rates <ref:2608.20480#pg1>.

Tom: I’m focused on the "frighteningly more powerful" part; it's not just a small error increase anymore; it's a fundamental change in what is learnable <ref:2608.20480#pg1>.

The paper's improvements: Jane: Now, the paper doesn't just stop at showing things get unlearnable; they also characterize when this corruption isn't so bad. They show settings where monotone data is harmless, meaning every ordinarily learnable class stays learnable if the number of adaptive additions is sublinear with respect to n <ref:2608.20480#pg4>.

Tom: That's a relief, because it tells us there are still regimes where we can trust our learning process even when some data is corrupted <ref:2608.20480#pg4>. They show that if the learner is permitted r many private i.i.d. points, the expected error rate stays at most dDS over r plus one, which looks like a manageable bound <ref:2608.20480#pg4>.

Lu: They also characterize robustness against semi-adaptive adversaries and oblivious ones, showing that the classic multiclass error rate of O(dDS over n) remains achievable even when the adversary is restricted in specific ways <ref:2608.20480#pg4>. This gives us some concrete bounds on how much noise we can tolerate <ref:2608.20480#pg4>.

Meng: That sublinear adaptive addition part, where every sequence b n equals o(n) of additions preserves ordinary PAC learnability, that’s what matters for real-world deployment because we can’t always guarantee zero corruption <ref:2608.20480#pg4>.

Lalam: They also look at proper learning and Empirical Risk Minimization, showing they are especially fragile under monotone additions; even a linear number of oblivious additions can make the sample complexity increase arbitrarily large, hitting a bound of F(one/delta) <ref:2608.20480#pg5>.

Tom: So the implication here is that proper learning and ERM might be more sensitive to these kinds of monotone additions than we initially thought, even when the number of additions is small <ref:2608.20480#pg5>.

Conclusion: Jane: We've covered how adaptive monotone adversaries can destroy learnability in multiclass and partial binary settings, but also where they are harmless, like when the corruption budget is sublinear with respect to n <ref:2608.20480#pg4>.

Tom: And we saw that proper learning and ERM principles become very fragile, with oblivious additions making them arbitrarily expensive in terms of sample complexity <ref:2608.20480#pg5>. The key distinction here seems to be the budget: sublinear versus linear or full n additions <ref:2608.20480#pg5>.

Lu: The quantitative bounds they provide are interesting, showing that for a d-fold product, the adaptive risk scales as Omega of d log(one + n/d)/n <ref:2608.20480#pg1>. This helps us understand the actual price we pay when adaptivity is involved <ref:2608.20480#pg1>.

Meng: From an operational standpoint, knowing that sublinear additions preserve learnability gives us a boundary for how much noise we can expect without completely breaking our model training pipeline <ref:2608.20480#pg4>.

Lalam: The paper establishes a sharp threshold between sublinear and linear additions for ordinary PAC learnability <ref:2608.20480#pg1>. This means the results are concrete enough to guide future research on robustness in learning theory <ref:2608.20480#pg1>.

Tom: So, we've seen how adaptive monotone additions can be devastating to certain learning tasks while sublinear corruption is manageable, and this whole study on "When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification" sets a clear boundary for what we need to watch out for in data handling <ref:2608.20480#pg1>.

More episodes

← Home