PAC learning with nasty noise

By Nader H. Bshouty, Nadav Eiron, Eyal Kushilevitz. 1999

How researchers see this paper

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

Citations in the corpus

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].”
Security analysis of online centroid anomaly detection (2010, background): “ther patchy. Earlier work in the PACframework has addressed some scenarios in which training data is deliberately corrupt (Angluin and Laird, 1988; Littlestone, 1988; Kearns and Li, 1993; Auer, 1997; Bschouty et al., 1999). These results, however, are not connected to modern learning algorithms used”
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.”
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.”
Model Inversion Attacks for Prediction Systems: Without Knowledge of Non-Sensitive Attributes (2017, background): “In the early stage, the security of poisoning was theoretically analyzed in terms of probably approximately correct (PAC) learning [12]–[14].”
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].”
Structured labeling for facilitating concept evolution in machine learning (2014, background): “, [10, 30) and techniques for automatically identifying and eliminating or correcting mislabeled data (e.”
On the Sample Complexity of Adversarial Multi-Source PAC Learning (2020, methodology): “This is similar to classic models in the ﬁelds of robust PAC learning, e.g. (Bshouty et al., 2002), and robust mean estimation, e.g. (Diakonikolas et al., 2019), where the adversary itself can inﬂuence which subset of the data to modify once the whole dataset is observed.”
Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners (2017, background): “Comparison with the distribution-independent setting of [10,31].”
Learning geometric concepts with nasty noise (2017, background): “In the nasty noise model [4], an omniscient adversary can arbitrarily corrupt a small constant fraction of both the unlabeled data points and their labels.”
Ieee Transactions on Pattern Analysis and Machine Intelligence Classification with Noisy Labels by Importance Reweighting (unknown): “It has been proven that any nontrivial target function class cannot be PAC learned with accuracy and malicious noise rate η ≥ (1 + ); see, for examples, [18]– [20].”
Limits of Learning-based Signature Generation with Adversaries (2008, background): “[2, 5, 16] In this regard, the most related work is mentioned in Sec.”
Learning under p-Tampering Attacks (2018, background): “[11] studied a closely related model in which the adversary is allowed to make its choices based on the full knowledge of the original training examples.”