Adversarial examples from computational constraints

By Sébastien Bubeck, Eric Price, Ilya P. Razenshteyn. 2018

239 citations recorded by the source corpus.

Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational constraints. First we prove that, for a broad set of classification tasks, the mere existence of a robust classifier implies that it can be found by a possibly exponential-time algorithm with relatively few training examples. Then we give a particular classification task where learning a robust classifier is computationally intractable. More precisely we construct a binary classification task in high dimensional space which is (i) information theoretically easy to learn robustly for large perturbations, (ii) efficiently learnable (non-robustly) by a simple linear separator, (iii) yet is not efficiently robustly learnable, even for small perturbations, by any algorithm in the statistical query (SQ) model. This example gives an exponential separation between classical learning and robust learning in the statistical query model. It suggests that adversarial examples may be an unavoidable byproduct of computational limitations of learning algorithms.

Subfields: Artificial Intelligence, Hardware and Architecture, 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 Artificial Intelligence

In Hardware and Architecture

In Safety, Robustness & Interpretability

Citations in the corpus

ColdGANs: Taming Language GANs with Cautious Sampling Strategies (2020, background): “Conversely, when trained on the different temperatures together ( T ∈ { 0 , 1 , ∞} ), results are more balanced: robust across the various temperatures, but yielding a drop in accuracy, consistently with the well-known accuracy-robustness trade-off [13, 4].”
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].”
Certified Adversarial Robustness via Randomized Smoothing (2019, background): “tob, 2018; Bubeck et al., 2018b). Of particular relevance, Bubeck et al. (2018a); Degwekar & Vaikuntanathan (2019) show that for certain classification problems, there exists a robust classifier that is not efficiently computable (like randomized smoothing) but there does not exist any robust classi”
Theoretical evidence for adversarial robustness through randomization: the case of the Exponential family (2019, background): “Even though several explicit or implicit deﬁnitions can be found in the literature, e.g. (Szegedy et al., 2014; Fawzi et al., 2018a; Bubeck et al., 2018), there is no broadly accepted deﬁnition of robustness to adversarial examples attacks.”
Towards the first adversarially robust neural network model on MNIST (2018, background): “By “solved” we mean a model that reaches at least 99% accuracy (see accuracy-vs-robustness trade-off (Tsipras et al., 2018; Bubeck et al., 2018)) and whose adversarial examples carry semantic meaning to humans (by which we mean that they start looking like samples that could belong to either class).”
Excessive Invariance Causes Adversarial Vulnerability (2018, background): “The reasons for these failures and how they may be avoided or at least mitigated is a prime research area (Schmidt et al., 2018; Gilmer et al., 2018b; Bubeck et al., 2018).”
Robustness May Be at Odds with Accuracy (2018, background): “A recent work (Bubeck et al., 2018) turns out to (implicitly) rely on the distinction between robust and non-robust features in constructing a distribution for which adversarial robustness is hard from a diﬀerent, computational point of view.”
Unlabeled Data Improves Adversarial Robustness (2019, background): “[5] and Degwekar and Vaikuntanathan [12] show possible computational barriers; Gilmer et al.”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, methodology): “However, the work of Bubeck et al. (Bubeck, Price, and Razenshteyn 2018) proved that assuming the existence of classifiers that are robust to evasion attacks, they could be found by “few” training examples in an information theoretic way.”
Towards Deep Learning Models Resistant to Large Perturbations (2020, background): “It is notable that, there is some work in the literature (Bubeck et al., 2018; Garg et al., 2019; Gourdeau et al., 2019; Mahloujifar & Mahmoody, 2018), which discussed the computational hardness of adversarial robust learning.”
There Is No Free Lunch In Adversarial Robustness (But There Are Unexpected Benefits) (2018, background): “A recent work [6] turns out to (implicitly) rely on the distinction between robust and non-robust features in constructing a distribution for which adversarial robustness is hard from a different, computational point of view.”
Advances in adversarial attacks and defenses in computer vision: A survey (2021, background): “[323] argued that adversarial vulnerability of classifiers in high dimension is ‘‘likely not due to information theoretic limitations, but rather it could be due to computational constraints’’.”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, unknown): “This also motivates some recent research on gaining theoretical understanding of robust error [9, 40].”
A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance (2019, background): “…(2018) provides evidence that adversarially robust classiﬁers require more data by examining a distribution of a mixture of two Gaussians, whereas Bubeck et al. (2018) suggests that the bottleneck is the computational intractability of training a robust classiﬁer rather than information…”
Adversarial Examples on Object Recognition (2020, background): “ﬁcantly higher than for training non-robust models. In particular, for achieving robustness forthel∞ normrequiresanincreaseofsamplecomplexitypolynomialintheinputdimension.Ona similarnote,Bubeck et al.[19]suggestthatrobustlearninginthestatisticalquerymodelincreases thenumberofqueriesexponentially.Som”
Is Robustness the Cost of Accuracy? - A Comprehensive Study on the Robustness of 18 Deep Image Classification Models (2018, result): “We also note that our findings are consistent with the very recent paper [54] that proves the difficulty of learning robust models against adversarial examples.”
Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “…et al., 2020; Attias et al., 2022b; Xiao et al., 2022; Viallard et al., 2021; Bubeck & Sellke, 2021; Li & Telgarsky, 2023), adversarial examples (Bubeck et al., 2018; 2019; Bartlett et al., 2021; Bubeck et al., 2021), consistency guarantees and optimal adversarial classifiers (Bao et al., 2020;…”