{"ID":2822610,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.02193","arxiv_id":"2601.02193","title":"Learning with Monotone Adversarial Corruptions","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2601.02193","url_pdf":"https://arxiv.org/pdf/2601.02193v1","authors":"[\"Kasper Green Larsen\",\"Chirag Pabbaraju\",\"Abhishek Shetty\"]","published":"2026-01-05T15:16:26Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.DS\",\"stat.ML\"]","methods":"[]","has_code":false}