S. Dughmi

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

This work exhibits a learnable multiclass problem that becomes altogether unlearnable under a monotone adversary, and shows an analogous result for partial binary concept classes, and demonstrates that monotone adversaries are frighteningly more powerful in each of these settings.