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

arXiv: https://arxiv.org/abs/2608.20480 · HTML: https://mlsanity.com/paper/2608.20480/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 24 references that are in the map.
- First posted on arXiv 20 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Scaling Data-Constrained Language Models](https://mlsanity.com/paper/2305.16264/) (2023)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Majority-of-Three is Optimal](https://mlsanity.com/paper/2606.13614/) (2026)
- [Optimal Rates for Learning with Monotone Adversaries](https://mlsanity.com/paper/2608.06337/) (2026)

## Abstract (arXiv)

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 Omega (d log(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 < ∞ 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(dDS / 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 ∈ (0, 1), and against oblivious adversaries that cannot view S.