# Is nasty noise actually harder than malicious noise?

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2025.

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

- [Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing](https://mlsanity.com/paper/2606.31230/) (2026)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Robust Statistical Estimators with Bounded Empirical Sensitivity](https://mlsanity.com/paper/2605.21860/) (2026)
- [Efficient Robust Learning at the Information-Theoretic Limit](https://mlsanity.com/paper/2609.17655/) (2026)

## Abstract (arXiv)

We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial noise models for learning Boolean functions: malicious noise, in which an adversary can arbitrarily corrupt a random subset of examples given to the learner; and nasty noise, in which an adversary can arbitrarily corrupt an adversarially chosen subset of examples given to the learner. We consider both the distribution-independent and fixed-distribution settings. Our main results highlight a dramatic difference between these two settings: For distribution-independent learning, we prove a strong equivalence between the two noise models: If a class cal C of functions is efficiently learnable in the presence of η-rate malicious noise, then it is also efficiently learnable in the presence of η-rate nasty noise. In sharp contrast, for the fixed-distribution setting we show an arbitrarily large separation: Under a standard cryptographic assumption, for any arbitrarily large value r there exists a concept class for which there is a ratio of r between the rate ηmalicious of malicious noise that polynomial-time learning algorithms can tolerate, versus the rate ηnasty of nasty noise that such learning algorithms can tolerate. To offset the negative result for the fixed-distribution setting, we define a broad and natural class of algorithms, namely those that ignore contradictory examples (ICE). We show that for these algorithms, malicious noise and nasty noise are equivalent up to a factor of two in the noise rate: Any efficient ICE learner that succeeds with η-rate malicious noise can be converted to an efficient learner that succeeds with η/2-rate nasty noise. We further show that the above factor of two is necessary, again under a standard cryptographic assumption.