Is nasty noise actually harder than malicious noise?
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.
Fields of Study & Subjects
Machine Learning and Algorithms
Adversarial Robustness in Machine Learning
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 6767–6787
- Publication date
- 1 January 2026
- Language
- EN