When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
Adaptive monotone additions can completely destroy learnability in multiclass and partial binary settings, a result previously unexpected. While oblivious additions are harmless for general learners, adaptive adversaries can make proper learning arbitrarily expensive and destroy Empirical Risk Minimization (ERM) under certain conditions. This establishes a sharp threshold between $o(n)$ and $\Theta(n)$ additions for ordinary PAC learnability.