# Adversarial examples from computational constraints

arXiv: https://arxiv.org/abs/1805.10204 · HTML: https://mlsanity.com/paper/1805.10204/

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2018.

## Built on by (most cited first, 30 of 80)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [Probabilistic Margins for Instance Reweighting in Adversarial Training](https://mlsanity.com/paper/2106.07904/) (2021)
- [Exploring Memorization in Adversarial Training](https://mlsanity.com/paper/2106.01606/) (2021)
- [Do Input Gradients Highlight Discriminative Features?](https://mlsanity.com/paper/2102.12781/) (2021)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [AdvRush: Searching for Adversarially Robust Neural Architectures](https://mlsanity.com/paper/2108.01289/) (2021)
- [Gradient Methods Provably Converge to Non-Robust Networks](https://mlsanity.com/paper/2202.04347/) (2022)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Adversarial Training is Not Ready for Robot Learning](https://mlsanity.com/paper/2103.08187/) (2021)
- [Universal Adversarial Perturbations Through the Lens of Deep Steganography: Towards A Fourier Perspective](https://mlsanity.com/paper/2102.06479/) (2021)
- [REAP: A Large-Scale Realistic Adversarial Patch Benchmark](https://mlsanity.com/paper/2212.05680/) (2022)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [Interpreting Attributions and Interactions of Adversarial Attacks](https://mlsanity.com/paper/2108.06895/) (2021)
- [Adversarial Examples in Random Neural Networks with General Activations](https://mlsanity.com/paper/2203.17209/) (2022)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness](https://mlsanity.com/paper/2309.16096/) (2023)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes](https://mlsanity.com/paper/2106.02630/) (2021)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Building Robust Ensembles via Margin Boosting](https://mlsanity.com/paper/2206.03362/) (2022)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)

## Abstract (arXiv)

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.