Metraipolis › archive › dc_1f22bb598bc5
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification — arXiv:2608.20480
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.20480
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T10:31:01.221Z
- SHA-256 of the archived text
3098f3e8be3fae81c5e8a3570ce4d05c60f063cd69baceac7d586e47dc928c82- Stable URL of this page
https://metraipolis.com/documento/dc_1f22bb598bc5
How to cite
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification — arXiv:2608.20480 — arXiv (en), https://arxiv.org/abs/2608.20480 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1f22bb598bc5 (Metraipolis archive dc_1f22bb598bc5, sha256 3098f3e8be3fae81c5e8a3570ce4d05c60f063cd69baceac7d586e47dc928c82)
BibTeX
@misc{dc1f22bb598bc5,
title = {When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification — arXiv:2608.20480},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.20480},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1f22bb598bc5; sha256 3098f3e8be3fae81c5e8a3570ce4d05c60f063cd69baceac7d586e47dc928c82},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.20480. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 < \infty$ 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_{\mathrm{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$.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-24 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2608.20480 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T10:27:55.925Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).