When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
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 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.
Related
- RobustLDS: Learning linear dynamical systems under adversarial corruptions
- Benchmarking Classical Machine Learning and Deep Learning Models on the Cleveland Heart Disease Binary Classification Dataset
- Byzantine-tolerant distributed learning of finite mixture models under partial corruptions
- When are time-to-event models a waste of time? Bridging mixture cure models and positive-unlabeled learning for binary classification under right-censoring
- Critical p-Laplace equations with monotone coefficients: Liouville classification and a Schoen-type Harnack inequality
BibTeX
@misc{asilis2026when,
title = {{When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification}},
author = {Julian Asilis and Shaddin Dughmi and Chirag Pabbaraju},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.20480},
eprint = {2608.20480},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.20480},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
AU - Julian Asilis
AU - Shaddin Dughmi
AU - Chirag Pabbaraju
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2608.20480
UR - https://arxiv.org/abs/2608.20480
AB - 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 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(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 ∈ (0, 1), and against oblivious adversaries that cannot view S.
ER -