Learning Nested Differences in the Presence of Malicious Noise
By Peter Auer. 1995
We investigate the learnability of nested differences of intersection-closed classes in the presence of malicious noise. Examples of intersection-closed classes include axis-parallel rectangles, monomials, linear sub-spaces, and so forth. We present an on-line algorithm whose mistake bound is optimal in the sense that there are concept classes for which each learning algorithm (using nested differences as hypotheses) can be forced to make at least that many mistakes. We also present an algorithm for learning in the PAC model with malicious noise. Surprisingly enough, the noise rate tolerable by these algorithms does not depend on the complexity of the target class but depends only on the complexity of the underlying intersection-closed class.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Battista Biggio
- Blaine Nelson
- Nicolas Papernot
- Pavel Laskov
- Nicholas Carlini
- Fabio Roli
- Marius Kloft
- Davide Maiorca
Citations in the corpus
- Security analysis of online centroid anomaly detection (2010, background): “On the other hand, several examples of effective attacks have been demonstrated in the context of specific security and spam detection applications (Lowd and Meek, 2005a; Fogla et al., 2006; Fogla and Lee, 2006; Perdisci et al., 2006; Newsome et al., 2006; Nelson et al., 2008), which has motivated…”
- Can machine learning be secure? (2006, background): “Specifically, they proved that if the learner is to perform correctly, in general the fraction of training points controlled by the adversary must be less than ✏/(1+ ✏), where ✏ is the desired bound on classification errors by the learner [4, 6, 30].”
- Limits of Learning-based Signature Generation with Adversaries (2008, background): “[2, 5, 16] In this regard, the most related work is mentioned in Sec.”