Adversarial examples from computational constraints

Abstract

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.

19 pages, 1 figure

References in corpus (7)

• 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
• Adversarially Robust Generalization Requires More Data
• Adversarial vulnerability for any classifier
• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Adversarial Spheres

Cited by in corpus (67)

• Theoretically Principled Trade-off between Robustness and Accuracy
• Adversarial Examples Are Not Bugs, They Are Features
• Robustness May Be at Odds with Accuracy
• Rademacher Complexity for Adversarially Robust Generalization
• Do Adversarially Robust ImageNet Models Transfer Better?
• The Pitfalls of Simplicity Bias in Neural Networks
• A Closer Look at Accuracy vs. Robustness
• Adversarial Robustness May Be at Odds With Simplicity
• A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance
• Unlabeled Data Improves Adversarial Robustness
• The Limitations of Adversarial Training and the Blind-Spot Attack
• Excessive Invariance Causes Adversarial Vulnerability
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Robust in Practice: Adversarial Attacks on Quantum Machine Learning
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• High Frequency Component Helps Explain the Generalization of Convolutional Neural Networks
• Theoretical evidence for adversarial robustness through randomization
• Do Wider Neural Networks Really Help Adversarial Robustness?
• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• Adversarial Risk Bounds via Function Transformation
• Probabilistic Margins for Instance Reweighting in Adversarial Training
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• Randomization matters. How to defend against strong adversarial attacks
• Adversarial Examples from Cryptographic Pseudo-Random Generators
• Exploring Memorization in Adversarial Training
• A Spectral View of Adversarially Robust Features
• Adversarial Examples on Object Recognition: A Comprehensive Survey
• Towards Security Threats of Deep Learning Systems: A Survey
• Lower Bounds for Adversarially Robust PAC Learning
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Convergence and Margin of Adversarial Training on Separable Data
• Calibrated Surrogate Losses for Adversarially Robust Classification
• A law of robustness for two-layers neural networks
• Learning Adversarially Robust Representations via Worst-Case Mutual Information Maximization
• Is Robustness the Cost of Accuracy? -- A Comprehensive Study on the Robustness of 18 Deep Image Classification Models
• Computational Limitations in Robust Classification and Win-Win Results
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• ColdGANs: Taming Language GANs with Cautious Sampling Strategies
• Robust Attacks against Multiple Classifiers
• Adversarial Robustness of Supervised Sparse Coding
• Calibration and Consistency of Adversarial Surrogate Losses
• Rearchitecting Classification Frameworks For Increased Robustness
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks
• Adversarial Classification: Necessary conditions and geometric flows
• On Isometry Robustness of Deep 3D Point Cloud Models under Adversarial Attacks
• Adversarially Robust Low Dimensional Representations
• Random Directional Attack for Fooling Deep Neural Networks
• Improving Adversarial Robustness via Unlabeled Out-of-Domain Data
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning
• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• Feature-Filter: Detecting Adversarial Examples through Filtering off Recessive Features
• Towards Deep Learning Models Resistant to Large Perturbations
• An Empirical Study on the Relation between Network Interpretability and Adversarial Robustness
• On Mean Estimation for General Norms with Statistical Queries
• Robust learning under clean-label attack
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• Do Input Gradients Highlight Discriminative Features?
• Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
• Query complexity of adversarial attacks
• Gödel's Sentence Is An Adversarial Example But Unsolvable
• Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes
• Interpreting Attributions and Interactions of Adversarial Attacks
• Unique properties of adversarially trained linear classifiers on Gaussian data
• Derivation of Information-Theoretically Optimal Adversarial Attacks with Applications to Robust Machine Learning
• Robust Deep Neural Networks Inspired by Fuzzy Logic
• A Separation Result Between Data-oblivious and Data-aware Poisoning Attacks
• Adversarial Data Encryption