Adversarial Robustness May Be at Odds With Simplicity

By Preetum Nakkiran. 2019

116 citations recorded by the source corpus.

Current techniques in machine learning are so far are unable to learn classifiers that are robust to adversarial perturbations. However, they are able to learn non-robust classifiers with very high accuracy, even in the presence of random perturbations. Towards explaining this gap, we highlight the hypothesis that $\textit{robust classification may require more complex classifiers (i.e. more capacity) than standard classification.}$ In this note, we show that this hypothesis is indeed possible, by giving several theoretical examples of classification tasks and sets of "simple" classifiers for which: (1) There exists a simple classifier with high standard accuracy, and also high accuracy under random $\ell_\infty$ noise. (2) Any simple classifier is not robust: it must have high adversarial loss with $\ell_\infty$ perturbations. (3) Robust classification is possible, but only with more complex classifiers (exponentially more complex, in some examples). Moreover, $\textit{there is a quantitative trade-off between robustness and standard accuracy among simple classifiers.}$ This suggests an alternate explanation of this phenomenon, which appears in practice: the tradeoff may occur not because the classification task inherently requires such a tradeoff (as in [Tsipras-Santurkar-Engstrom-Turner-Madry `18]), but because the structure of our current classifiers imposes such a tradeoff.

Subfields: Artificial Intelligence, 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 Safety, Robustness & Interpretability

Citations in the corpus

Adversarial Examples Are Not Bugs, They Are Features (2019, background): “In a similar vein, Nakkiran [Nak19a] constructs a set of adversarial perturbations that is explicitly non-transferable and ﬁnds that these perturbations cannot be used to learn a good classiﬁer.”
Adversarial Examples Improve Image Recognition (2019, background): “Other works try to explain this tradeoff phenomenon from the perspective of the increased sample complexity of adversary [37, 25, 28], the limited amount of training data [1, 27, 34, 44, 48], or network overparameterization [31].”
Precise Tradeoffs in Adversarial Training for Linear Regression (2020, background): “In particular, [Nak19] provides classiﬁcation problems where simple classiﬁers with high standard accuracy exist; but having high robust accuracy is possible through more complex classiﬁers.”
Computational Limitations in Robust Classification and Win-Win Results (2019, methodology): “We can replace them by any constants α, β where α > β and the result holds (see Naor and Rothblum (2006); Berman et al.”
Triple Wins: Boosting Accuracy, Robustness and Efficiency Together by Enabling Input-Adaptive Inference (2020, background): “Nakkiran (2019) argued from a different perspective, that the complexity (e.g. capacity) of a robust classiﬁer must be higher than that of a standard classiﬁer.”
Intriguing properties of adversarial training (2019, result): “This finding also coincides with the recent theoretical study [15] which argues that robust adversarial learning needs more complex classifiers.”
Understanding and Mitigating the Tradeoff Between Robustness and Accuracy (2020, background): “, 2018), and when the hypothesis class is not expressive enough to contain the true classifier (Nakkiran, 2019).”
Improving Adversarial Robustness Requires Revisiting Misclassified Examples (2020, background): “Nakkiran (2019) showed that a model requires more capacity to be robust ( i.e. , simple models can have high natural accuracy but are less likely to be robust).”
Smooth Adversarial Training (2020, background): “This phenomenon is referred to as no free lunch in adversarial robustness [65, 42, 62].”
Attacks Which Do Not Kill Training Make Adversarial Learning Stronger (2020, background): “Moreover, [38] states that robust classiﬁcation needs more complex classiﬁers (exponentially more complex).”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, background): “Apart from this paper, there are other works supporting the need for capacity including the perspective of network width [31], depth [49] and computational complexity [35].”
Adversarial Training Can Hurt Generalization (2019, background): “Another explanation could be that the hypothesis class is not rich enough to contain predictors that have optimal standard and high robust accuracy, even if they exist [9].”
Do Adversarially Robust ImageNet Models Transfer Better? (2020, background): “In fact, adversarially robust models are known to be significantly less accurate than their standard counterparts [Tsi+19; Su+18; Rag+19; Nak19], suggesting that using adversarially robust feature representations should hurt transfer performance.”
Adversarial Weight Perturbation Helps Robust Generalization (2020, background): “Nakkiran [31] showed that a model requires more capacity to be robust.”
Do Wider Neural Networks Really Help Adversarial Robustness? (2020, background): “(2020) and Nakkiran (2019) also challenged this robust-natural trade-off Tsipras et al.”