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

arXiv:2608.20480 · cs.LG, stat.ML · Submitted 2026-08-20 · Read on arXiv

Listen

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

Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju

University of Southern California · Stanford University

cs.LG, stat.ML

Submitted: 2026-08-20

Updated: 2026-10-16

Comments: 52 pages

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

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

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.

Summary

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 learners

Destroying Learnability with Adaptive Adversaries

The paper demonstrates that adaptive monotone adversaries are frighteningly more powerful in multiclass and partial binary settings than previously understood The primary result shows that a learnable multiclass problem of DS dimension only 2 becomes altogether unlearnable under a monotone adversary by inserting exactly n datapoints into the original dataset of n i.i.d. points Similarly, a class of partial VC dimension at most 18 in binary partial concept learning becomes nonlearnable under an adaptive adversary making a finite number of insertions. This resolves Open Problem 1 from Larsen et al. (2026) negatively.

Harmless Regimes for Additions

The paper characterizes settings where monotone data is harmless, showing that every ordinarily learnable class remains learnable when the number of adaptive additions is o(n). Specifically, a learner permitted r many private i.i.d. points can achieve expected error at most dDS/ (r + 1). Furthermore, the classic multiclass error rate of O(dDS/n) remains achievable against semi-adaptive adversaries restricted to a known constant budget b = O(1), against semi-adaptive adversaries viewing only a p-fraction of S for p ∈ (0, 1), and against oblivious adversaries that cannot view S.

Proper Learning and ERM Fragility

The results show that proper learning and Empirical Risk Minimization (ERM) are especially fragile under monotone additions. Even with only a linear number of oblivious additions, the PAC sample complexity of proper learning can increase by arbitrarily large amounts, achieving a monotone sample complexity lower bound of F(1/δ) for any growth function F. Moreover, even oblivious adversaries can make proper learning arbitrarily expensive and destroy every ERM. There is a fixed countable class of DS dimension 1 where the PAC sample complexity of proper learning can increase by an arbitrary amount under oblivious additions.

Quantitative Lower Bounds and Robustification

The paper provides sharp quantitative bounds on the price of adaptivity, showing that for every d ≥ 1, a d-fold product gives a class of DS dimension d with clean risk O(d/n) and adaptive risk omega(d log(1 + n/d)/n). For arbitrary budgets b, there is a fixed countable multiclass class H of DS dimension d such that the adaptive risk is at least c min 1, d log(2 + s/d) / n. The paper also shows that ordinary learnability is always preserved under bn = o(n) additions.

Conclusion on Learnability

In summary, the paper constructs learnable problems in multiclass classification and partial binary concepts that become altogether unlearnable under adaptive monotone additions Oblivious additions, in contrast, remain benign for general learners. The results establish a sharp threshold between o(n) and Θ(n) additions for ordinary PAC learnability.

Open Questions

Several questions remain open, including the precise dependence of monotone error rates on the budget b in multiclass and partial binary settings and finding robust replacements to DS and partial VC dimensions that successfully characterize learnability in the monotone model. The paper also leaves open whether proper multiclass learnability can be destroyed altogether by an oblivious adversary.

Acknowledgments

Julian Asilis was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1842487, Shaddin Dughmi was supported by NSF Grant CCF2432219, and completed part of this work while on sabbatical as the Carter and Tania Neild visiting professor at Northwestern University, as well as a visiting professor in the Data Science Institute at the University of Chicago. Chirag Pabbaraju was supported by a Google PhD Fellowship, and Moses Charikar’s and Gregory Valiant’s Simons Investigator Awards. AI disclosure ChatGPT 5.6 Pro and Sol Max played a significant role in the development of several results.

References

Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In IEEE Symposium on Foundations of Computer Science, pages 1203–1223, 2023. Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majorityof-three: The simplest optimal learner? In Conference on Learning Theory, pages 22–45, 2024. Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of PAC learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671, IEEE, 2022. Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. Robust learning under clean-label attack. In Conference on Learning Theory, pages 591–634, 2021. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapnik–chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989. Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In IEEE Symposium on Foundations of Computer Science, pages 943–955, 2022. Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287–316, 2014. Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16:2377–2404, 2015. Uriel Feige. Introduction to semirandom models. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 189–211, Cambridge University Press, 2021. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. Steve Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1–15, 2016. Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran. On optimal learning under targeted data poisoning. In Advances in Neural Information Processing Systems, volume 35, pages 30770–30782, 2022.

Improvements for AI systems

The AI system can be robust against monotone adversarial corruptions in multiclass classification by utilizing learnable problems with DS dimension two that are altogether unlearnable under a monotone adversary. This capability is achieved by constructing a class of hypotheses where, adaptive monotone additions can destroy learnability altogether in both the multiclass and partial binary settings.
The system can maintain optimal expected error rates against restricted adversarial access by exploiting the property that every o(n) adaptive budget is universally harmless, as shown by Theorem 4.6: Every sequence bn = o(n) of adaptive monotone additions preserves ordinary PAC learnability.
The AI system can achieve robust performance in scenarios where only a fraction of the training data is visible to the adversary by leveraging exchangeability, ensuring that hidden clean examples retain all of the symmetry of ordinary i.i.d. data, which leads to an expected error bound of ELD(bh, h⋆) ≤ d(r+1).
The system can be designed to handle scenarios with known budget constraints by employing aggregation techniques, as shown in Theorem 4.7: If the adversary adds at most b examples, the robust risk is reduced to a term that scales as O(d(b + 1)/(n + b)).
For proper learning tasks, the system can be made arbitrarily expensive by using monotone additions, as demonstrated by Theorem 5.1: an oblivious additions can make proper learning arbitrarily expensive and can destroy every ERM, resulting in a sample complexity lower bound of F(1/δ) for all sufficiently small δ.
The system's performance under the Empirical Risk Minimization (ERM) principle is protected against adaptive monotone additions by Theorem 5.3: If every ERM rule PAC learns H in the ordinary realizable model, then every ERM rule PAC learns H under arbitrary adaptive monotone additions.

Abstract

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.