This paper investigates the extent to which standard machine learning algorithms depend on the exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon examining a 'clean' i.i.d. dataset, inserts additional 'corrupted' points of their choice. These added points are constrained to be monotone corruptions, meaning they are labeled according to the ground-truth target function.
Surprisingly, we demonstrate that in this setting, all known optimal learning algorithms for binary classification can achieve suboptimal expected error on a new independent test point drawn from the same distribution as the clean dataset. In contrast, we show that uniform convergence-based algorithms do not degrade in their guarantees. Our results highlight how optimal learning algorithms can fail in the presence of seemingly helpful monotone corruptions, exposing their overreliance on exchangeability.
Blogger's Review: This paper reveals the vulnerability of machine learning models when faced with adversarial data corruption, emphasizing the risks associated with the assumption of exchangeability. This finding presents new challenges for future algorithm design and data handling strategies, prompting a reevaluation of model robustness and adaptability. The use of monotone corruption strategies offers profound insights into understanding algorithm limitations.