The classic PAC model assumes training data is i.i.d., but what if an adversary inserts correctly labeled examples from an unrelated source? Prior work by Larsen et al. and Mehrotra showed that such "monotone corruptions" hurt binary classifiers, forcing an extra logarithmic factor in error. This paper extends the question to multiclass classification and partial binary concept classes, where the authors find the adversary is far more powerful.

Their main result is a learnable multiclass problem with DS dimension only 2 that becomes completely unlearnable under a monotone adversary. The adversary is adaptive, sees the original training set S, and needs to insert only n corrupted points—a linear number. An analogous result holds for partial binary concept classes, showing the phenomenon is not an artifact of multiclass labels.

On the positive side, the authors prove that every class remains learnable when the number of adaptive additions is o(n), and this bound is tight. They also show the classic O(d_DS/n) multiclass error rate survives against adversaries with a constant budget, semi-adaptive adversaries that see only a fraction of S, and oblivious adversaries that see no data. The paper thus maps exactly where monotone corruption breaks learning beyond binary classification.