Adversarial Robustness May Be at Odds With Simplicity

Abstract

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 $\text{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, $\text{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.

welcome

References in corpus (6)

• Intriguing properties of neural networks
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Robustness May Be at Odds with Accuracy
• Adversarial examples from computational constraints
• Adversarial Examples from Cryptographic Pseudo-Random Generators

Cited by in corpus (43)

• Interpolation Consistency Training for Semi-Supervised Learning
• Adversarial Examples Are Not Bugs, They Are Features
• Adversarial Weight Perturbation Helps Robust Generalization
• Adversarial Training Can Hurt Generalization
• Smooth Adversarial Training
• Attacks Which Do Not Kill Training Make Adversarial Learning Stronger
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy
• Adversarial Examples Improve Image Recognition
• Do Wider Neural Networks Really Help Adversarial Robustness?
• Triple Wins: Boosting Accuracy, Robustness and Efficiency Together by Enabling Input-Adaptive Inference
• Exploring Architectural Ingredients of Adversarially Robust Deep Neural Networks
• Once-for-All Adversarial Training: In-Situ Tradeoff between Robustness and Accuracy for Free
• Boundary thickness and robustness in learning models
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• Intriguing properties of adversarial training at scale
• Precise Tradeoffs in Adversarial Training for Linear Regression
• How benign is benign overfitting?
• Label Smoothing and Adversarial Robustness
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Adversarial Feature Augmentation and Normalization for Visual Recognition
• Data-Efficient GAN Training Beyond (Just) Augmentations: A Lottery Ticket Perspective
• Computational Limitations in Robust Classification and Win-Win Results
• Improving Adversarial Robustness via Guided Complement Entropy
• Shift Invariance Can Reduce Adversarial Robustness
• Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks
• Adversarially Robust Low Dimensional Representations
• Data Quality Matters For Adversarial Training: An Empirical Study
• Removing Spurious Features can Hurt Accuracy and Affect Groups Disproportionately
• A Survey on Trust Metrics for Autonomous Robotic Systems
• Robustness, Privacy, and Generalization of Adversarial Training
• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• An Empirical Study on the Relation between Network Interpretability and Adversarial Robustness
• A Useful Taxonomy for Adversarial Robustness of Neural Networks
• CycleCluster: Modernising Clustering Regularisation for Deep Semi-Supervised Classification
• Achieving Adversarial Robustness Requires An Active Teacher
• Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective
• Estimating Principal Components under Adversarial Perturbations
• Unique properties of adversarially trained linear classifiers on Gaussian data
• Gödel's Sentence Is An Adversarial Example But Unsolvable
• Understanding Adversarial Behavior of DNNs by Disentangling Non-Robust and Robust Components in Performance Metric