Learning in the presence of malicious errors

By Michael Kearns, Ming Li. 1988

In this paper an extension of the distribution-free model of learning introduced by Valiant [Comm. ACM, 27(1984), pp. 1134–1142] that allows the presence of malicious errors in the examples given to a learning algorithm is studied. Such errors are generated by an adversary with unbounded computational power and access to the entire history of the learning algorithm’s computation. Thus, a worst-case model of errors is studied.The results of this research include general methods for bounding the rate of error tolerable by any learning algorithm, efficient algorithms tolerating nontrivial rates of malicious errors, and equivalences between problems of learning with errors and standard combinatorial optimization problems.

Subfields: Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Safety, Robustness & Interpretability

Citations in the corpus

Towards the Science of Security and Privacy in Machine Learning (2016, background): “Kearns et al. formally analyzed PAC-learnability when the adversary is allowed to modify training samples with probability β [39].”
Stronger data poisoning attacks break data sanitization defenses (2018, methodology): “The theoretical computer science community has studied robust estimators in high dimensions, which seek to work well even in the presence of outliers (Kearns and Li, 1993).”
Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning (2018, methodology): “treatments consider the robustness of learning to noise, including the extension of the PAC model by Kearns and Li [31], as well as work on robust statistics [8], [28], [52], [56].”
Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization (2017, background): “5 RELATEDWORK Seminal work on the analysis of supervised learning in the presence of omniscient attackers that can compromise the training data has been presented in [12, 18].”
Practical Evasion of a Learning-Based Classifier: A Case Study (2014, methodology): “In this paper, we experimentally investigate the effectiveness of classifier evasion using a real, deployed system, PDFRATE, as a test case.”
Security Evaluation of Pattern Classifiers under Attack (2014, background): “application-independent criteria to model the adversary’s behavior (including PAC learning and game theory) [10], [12], [14], [16], [17], [37], [38], [39], [40].”
Efficient Defenses Against Adversarial Attacks (2017, background): “They are thus unable to tamper with the training sample, unlike in other contexts, such as learning with malicious error [16].”
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…”
Support vector machines under adversarial label contamination (2015, methodology): “While stochastic label noise has been widely studied in the machine learning literature, to account for different kinds of potential labeling errors in the training data [31, 32], only a few works have considered adversarial, worst-case label noise, either from a more theoretical [33] or practical p”
Adversarially Robust Generalization Requires More Data (2018, background): “, see [7, 27, 28]), we are not aware of similar work on test time robustness.”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “Keywords-unsupervised learning, statistical learning, density estimation robust algorithm I. INTRODUCTION”
Learning from untrusted data (2016, methodology): “In this case, we can identify outliers i Ig by considering the value of fi (w̃i ) − fi (ŵi ), and Lemma 4.5 verifies that we can use this to perform outlier removal.”
SoK: Security and Privacy in Machine Learning (2018, background): “theoretically analyzed the accuracy of learning classifiers when the adversary is allowed to modify training samples with probability β [32].”
Towards Making Systems Forget with Machine Unlearning (2015, background): “, by injecting benign features into malicious samples [30, 49, 76, 77].”
Adversarial Attacks and Defences: A Survey (2018, neutral): “[40], thus challenging the learning system’s integrity.”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “In the context of poisoning attacks, some classical results about malicious noise (Valiant 1985; Kearns and Li 1993; Bshouty, Eiron, and Kushilevitz 2002) could be interpreted as limitations of learning under poisoning attacks.”
An experimental evaluation of simplicity in rule learning (2008, background): “It uses a stochastic combinatorial optimization technique to overcome the computational complexity of determining the smallest rule set with the lowest empirical error, which is an NP-hard problem.”