Clean Data Can Harm Learning Under Monotone Corruption.

The classic PAC learning model assumes data is independently and identically distributed (i.i.d.). However, this research explores a scenario where training data is corrupted by adding correctly labeled examples from an otherwise unrelated, potentially adversarial source, a phenomenon termed "monotone adversarial corruptions." Previous work showed that even optimal binary classifiers experience increased error rates in this setting. This paper extends that analysis, revealing even more severe consequences for broader learning problems. The primary finding is that monotone adversaries are far more powerful in multiclass classification and partial binary concept classes. The study demonstrates that a learnable multiclass problem, with a low DS dimension, can become entirely unlearnable when subjected to a monotone adversary. A similar impossibility result is shown for partial binary concept classes. These outcomes are achieved by an adaptive adversary that can view the original i.i.d. training set and insert a linear number of corrupted data points. The research also provides complementary results, proving that classes remain learnable if the number of adaptive additions is sub-linear, establishing a tight bound. It further notes that classic error rates can be maintained against adversaries with a known constant budget, semi-adaptive adversaries, or oblivious adversaries. This work exposes a fundamental vulnerability in standard learning paradigms when faced with subtle, yet powerful, data corruptions.