The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure

By Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad Mahmoody. 2018

161 citations recorded by the source corpus.

Many modern machine learning classifiers are shown to be vulnerable to adversarial perturbations of the instances. Despite a massive amount of work focusing on making classifiers robust, the task seems quite challenging. In this work, through a theoretical study, we investigate the adversarial risk and robustness of classifiers and draw a connection to the well-known phenomenon of “concentration of measure” in metric measure spaces. We show that if the metric probability space of the test instance is concentrated, any classifier with some initial constant error is inherently vulnerable to adversarial perturbations.One class of concentrated metric probability spaces are the so-called Lévy families that include many natural distributions. In this special case, our attacks only need to perturb the test instance by at most O(√n) to make it misclassified, where n is the data dimension. Using our general result about Lévy instance spaces, we first recover as special case some of the previously proved results about the existence of adversarial examples. However, many more Lévy families are known (e.g., product distribution under the Hamming distance) for which we immediately obtain new attacks that find adversarial examples of distance O(√n).Finally, we show that concentration of measure for product spaces implies the existence of forms of “poisoning” attacks in which the adversary tampers with the training data with the goal of degrading the classifier. In particular, we show that for any learning algorithm that uses m training examples, there is an adversary who can increase the probability of any “bad property” (e.g., failing on a particular test instance) that initially happens with non-negligible probability to ≈ 1 by substituting only Õe(√m) of the examples with other (still correctly labeled) examples.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, Statistical Learning Theory

How researchers see this paper

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

In Artificial Intelligence

In Safety, Robustness & Interpretability

In Statistical Learning Theory

Citations in the corpus

Adversarial Examples Are Not Bugs, They Are Features (2019, methodology): “Previous work has proposed a variety of explanations for this phenomenon, ranging from theoretical models [Sch+18; BPR18] to arguments based on concentration of measure in high-dimensions [Gil+18; MDM18; Sha+19a].”
Adversarial Training and Robustness for Multiple Perturbations (2019, background): “We follow a line of works that study distributions for which adversarial examples exist unconditionally [41, 21, 33, 12, 14, 26].”
Certified Adversarial Robustness via Randomized Smoothing (2019, background): “t conditions is it possible to learn a high-accuracy classiﬁer that is invariant to imperceptible perturbations of its input? Recent theoretical work has taken steps towards addressing this question (Mahloujifar et al., 2019;Gilmer et al.,2018b;Fawzi et al.,2018;Tsipras et al., 2019;Schmidt et al.,2”
Are adversarial examples inevitable? (2018, background): “Shortly after the original appearance of our work, Mahloujifar et al. (2018) presented a study of adversarial susceptibility that included both evasion and poisoning attacks.”
Adversarial Examples Are a Natural Consequence of Test Error in Noise (2019, background): “Several recent papers (Gilmer et al., 2018b; Mahloujifar et al., 2018; Dohmatob, 2018; Fawzi et al., 2018a) use concentation of measure to prove rigorous upper bounds on adversarial robustness for certain distributions in terms of test error, suggesting non-zero test error may imply the existence of”
Label-Consistent Backdoor Attacks (2019, unknown): “, 2017), “plausible” (Mahloujifar et al., 2018; Mahloujifar & Mahmoody, 2018), “visually indistinguishable” (Koh & Liang, 2017), and “clean-label” (Shafahi et al.”
Learning From Noisy Labels With Deep Neural Networks: A Survey (2020, background): “There has been a lot of research on the robustness of deep learning under input perturbation, mainly in the ﬁeld of adversarial training where the input feature is maliciously perturbed to distort the output of the DNN [34], [36].”
High-Frequency Component Helps Explain the Generalization of Convolutional Neural Networks (2019, background): “, 2018), and many more from different model or algorithm perspectives (Kawaguchi et al., 2017; Mahloujifar et al., 2018; Bubeck et al., 2018; Shamir et al., 2019).”
Rademacher Complexity for Adversarially Robust Generalization (2018, background): “A few other lines of work have conducted theoretical analysis of adversarial examples (Wang et al., 2017; Bubeck et al., 2018; Gilmer et al., 2018b; Dohmatob, 2018; Mahloujifar et al., 2018).”
Limitations of adversarial robustness: strong No Free Lunch Theorem (2018, background): “Just to name a few, let us mention (Tsipras et al., 2018; Schmidt et al., 2018; Bubeck et al., 2018; Gilmer et al., 2018b; Fawzi et al., 2018a; Mahloujifar et al., 2018; Sinha et al., 2017; Blanchet & Murthy, 2016; Mohajerin Esfahani & Kuhn, 2017).”
Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses (2020, background): “Further theoretical work relates p-tampering attacks to concentration of measure, wherein the existence of training-only attacks against learners over metric spaces is proven [68].”
Analyzing and Improving Representations with the Soft Nearest Neighbor Loss (2019, background): “Furthermore, recent work has found that when models concentrate data, they are more vulnerable to adversarial examples (Mahloujifar et al., 2018), whereas entangled models encourage intraclass clusters to spread out.”