Learning with Monotone Adversarial Corruptions
This work exposes vulnerabilities in optimal learning algorithms to monotone corruptions, highlighting overreliance on exchangeability, which is an incremental contribution to robustness in machine learning.
The paper investigates how standard machine learning algorithms rely on data exchangeability and independence by introducing a monotone adversarial corruption model, where an adversary adds corrupted points labeled by the ground-truth function, and shows that optimal binary classification algorithms achieve suboptimal expected error while uniform convergence-based algorithms maintain their guarantees.
We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon looking at a "clean" i.i.d. dataset, inserts additional "corrupted" points of their choice into the dataset. These added points are constrained to be monotone corruptions, in that they get labeled according to the ground-truth target function. Perhaps surprisingly, we demonstrate that in this setting, all known optimal learning algorithms for binary classification can be made to achieve suboptimal expected error on a new independent test point drawn from the same distribution as the clean dataset. On the other hand, we show that uniform convergence-based algorithms do not degrade in their guarantees. Our results showcase how optimal learning algorithms break down in the face of seemingly helpful monotone corruptions, exposing their overreliance on exchangeability.