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

• URL: http://arxiv.org/abs/2608.20480v1
• Date: Thu, 20 Aug 2026 18:10:54 GMT
• Title: When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
• Abstract summary: We show that monotone adversaries are frighteningly more powerful in multiclass classification and partial binary concept classes.<n>We demonstrate that the classic multiclass error rate of $O(d_mathrmDS / n)$ remains achievable against adaptive adversaries.
• Score: 9.871543582439903
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 < \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$.

Related papers

• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice.<n>Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable.<n>Larsen, Pabbaraju, and Shetty, who introduced this model, show that empirical risk minimization attains expected error $O((d/n)log(n/d))$ for classes of VC dimension $d$.
  arXiv  Detail & Related papers  (2026-08-06T17:45:32Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds [16.636823007179082]
  We study online learning in the adversarial injection model introduced by [Goel et al. 2017].<n>We prove a matching $(sqrtT)$ lower bound for VC dimension $1$, establishing a sharp separation between the two information regimes.<n>We introduce a potential-based framework driven by emphrobust witnesses, small subsets of labeled examples that certify predictions remaining resilient to adversarial contamination.
  arXiv  Detail & Related papers  (2026-02-23T18:30:48Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Self-Directed Linear Classification [50.659479930171585]
  In online classification, a learner aims to predict their labels in an online fashion so as to minimize the total number of mistakes. Here we study the power of choosing the prediction order and establish the first strong separation between worst-order and random-order learning.
  arXiv  Detail & Related papers  (2023-08-06T15:38:44Z)
• Supervised Contrastive Prototype Learning: Augmentation Free Robust Neural Network [17.10753224600936]
  Transformations in the input space of Deep Neural Networks (DNN) lead to unintended changes in the feature space. We propose a training framework, $textbfd Contrastive Prototype Learning$ ( SCPL) We use N-pair contrastive loss with prototypes of the same and opposite classes and replace a categorical classification head with a $textbfPrototype Classification Head$ (PCH) Our approach is $textitsample efficient$, does not require $textitsample mining$, can be implemented on any existing DNN without modification to their
  arXiv  Detail & Related papers  (2022-11-26T01:17:15Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Corruption-Robust Offline Reinforcement Learning [19.300465320692066]
  We study adversarial robustness in offline reinforcement learning. We show that a worst-case $Omega(depsilon) optimality gap is unavoidable. We propose robust variants of the Least-Square Value Iteration (LSVI) algorithm.
  arXiv  Detail & Related papers  (2021-06-11T22:41:53Z)
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
  We analyze the properties of adversarial learning adversarially robust halfspaces in the presence of label noise. To the best of our knowledge, this is the first work to show that adversarial training prov yields classifiers in noise.
  arXiv  Detail & Related papers  (2021-04-19T16:35:38Z)
• Towards Defending Multiple $\ell_p$-norm Bounded Adversarial Perturbations via Gated Batch Normalization [120.99395850108422]
  Existing adversarial defenses typically improve model robustness against individual specific perturbations. Some recent methods improve model robustness against adversarial attacks in multiple $ell_p$ balls, but their performance against each perturbation type is still far from satisfactory. We propose Gated Batch Normalization (GBN) to adversarially train a perturbation-invariant predictor for defending multiple $ell_p bounded adversarial perturbations.
  arXiv  Detail & Related papers  (2020-12-03T02:26:01Z)
• Improving Robustness and Generality of NLP Models Using Disentangled Representations [62.08794500431367]
  Supervised neural networks first map an input $x$ to a single representation $z$, and then map $z$ to the output label $y$. We present methods to improve robustness and generality of NLP models from the standpoint of disentangled representation learning. We show that models trained with the proposed criteria provide better robustness and domain adaptation ability in a wide range of supervised learning tasks.
  arXiv  Detail & Related papers  (2020-09-21T02:48:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.