![[2511.09763] Is nasty noise actually harder than malicious noise?](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2511.09763] Is nasty noise actually harder than malicious noise?
Summary
This paper explores the complexities of learning Boolean functions in the presence of two noise models: malicious and nasty noise, highlighting their differences in learnability under various conditions.
Why It Matters
Understanding the distinctions between malicious and nasty noise is crucial for developing robust machine learning algorithms. This research provides insights into how different noise models affect learning efficiency, which is vital for applications in AI safety and algorithm design.
Key Takeaways
- Malicious and nasty noise exhibit strong equivalence in distribution-independent learning.
- A significant separation exists in the fixed-distribution setting, affecting learnability rates.
- ICE algorithms can mitigate the challenges posed by nasty noise, maintaining efficiency.
- The findings have implications for cryptographic assumptions in machine learning.
- Understanding these noise models aids in designing more resilient AI systems.
Computer Science > Machine Learning arXiv:2511.09763 (cs) [Submitted on 12 Nov 2025 (v1), last revised 16 Feb 2026 (this version, v2)] Title:Is nasty noise actually harder than malicious noise? Authors:Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio View a PDF of the paper titled Is nasty noise actually harder than malicious noise?, by Guy Blanc and 3 other authors View PDF Abstract: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 $\eta$-rate malicious noise, then it is also efficiently learnable in the presence of $\eta$-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 conc...
