# Learning with Monotone Adversarial Corruptions

arXiv: https://arxiv.org/abs/2601.02193 · HTML: https://mlsanity.com/paper/2601.02193/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 5 Jan 2026.

## Builds on (most cited first, 21 of 21)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Adaptive and oblivious statistical adversaries are equivalent](https://mlsanity.com/paper/2410.13548/) (2024)
- [Clustering Semi-Random Mixtures of Gaussians](https://mlsanity.com/paper/1711.08841/) (2017)
- [Boosting, Voting Classifiers and Randomized Sample Compression Schemes](https://mlsanity.com/paper/2402.02976/) (2024)
- [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025)
- [Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness](https://mlsanity.com/paper/2506.03075/) (2025)

## Built on by (most cited first, 4 of 4)

- [Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://mlsanity.com/paper/2602.20111/) (2026)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory](https://mlsanity.com/paper/2608.14020/) (2026)
- [When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification](https://mlsanity.com/paper/2608.20480/) (2026)

## Abstract (arXiv)

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.