# Adversarial Robustness May Be at Odds With Simplicity

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jan 2019.

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

- [Robustness and Accuracy Could Be Reconcilable by (Proper) Definition](https://mlsanity.com/paper/2202.10103/) (2022)
- [Exploring Architectural Ingredients of Adversarially Robust Deep Neural Networks](https://mlsanity.com/paper/2110.03825/) (2021)
- [Aug-NeRF: Training Stronger Neural Radiance Fields with Triple-Level Physically-Grounded Augmentations](https://mlsanity.com/paper/2207.01164/) (2022)
- [Sparsity Winning Twice: Better Robust Generalization from More Efficient Training](https://mlsanity.com/paper/2202.09844/) (2022)
- [Data-Efficient GAN Training Beyond (Just) Augmentations: A Lottery Ticket Perspective](https://mlsanity.com/paper/2103.00397/) (2021)
- [Taxonomy of Machine Learning Safety: A Survey and Primer](https://mlsanity.com/paper/2106.04823/) (2021)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [A Theory of PAC Learnability under Transformation Invariances](https://mlsanity.com/paper/2202.07552/) (2022)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [What Can the Neural Tangent Kernel Tell Us About Adversarial Robustness?](https://mlsanity.com/paper/2210.05577/) (2022)
- [Analyzing Modality Robustness in Multimodal Sentiment Analysis](https://mlsanity.com/paper/2205.15465/) (2022)
- [Shift Invariance Can Reduce Adversarial Robustness](https://mlsanity.com/paper/2103.02695/) (2021)
- [Adversarial Imaging Pipelines](https://mlsanity.com/paper/2102.03728/) (2021)
- [Understanding Robust Learning through the Lens of Representation Similarities](https://mlsanity.com/paper/2206.09868/) (2022)
- [Adversarial Feature Augmentation and Normalization for Visual Recognition](https://mlsanity.com/paper/2103.12171/) (2021)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [MixACM: Mixup-Based Robustness Transfer via Distillation of Activated Channel Maps](https://mlsanity.com/paper/2111.05073/) (2021)
- [Adversarial Perturbations Are Not So Weird: Entanglement of Robust and Non-Robust Features in Neural Network Classifiers](https://mlsanity.com/paper/2102.05110/) (2021)
- [Boosting Adversarial Training via Fisher-Rao Norm-based Regularization](https://mlsanity.com/paper/2403.17520/) (2024)
- [Conserve-Update-Revise to Cure Generalization and Robustness Trade-off in Adversarial Training](https://mlsanity.com/paper/2401.14948/) (2024)
- [Adversarially Robust Out-of-Distribution Detection Using Lyapunov-Stabilized Embeddings](https://mlsanity.com/paper/2410.10744/) (2024)
- [All You Need is RAW: Defending Against Adversarial Attacks with Camera Image Pipelines](https://mlsanity.com/paper/2112.09219/) (2021)
- [The Price of Implicit Bias in Adversarially Robust Generalization](https://mlsanity.com/paper/2406.04981/) (2024)
- [Empirical Advocacy of Bio-inspired Models for Robust Image Recognition](https://mlsanity.com/paper/2205.09037/) (2022)
- [The Consistency of Adversarial Training for Binary Classification](https://mlsanity.com/paper/2206.09099/) (2022)
- [Strength-Adaptive Adversarial Training](https://mlsanity.com/paper/2210.01288/) (2022)
- [Intriguing Properties of Robust Classification](https://mlsanity.com/paper/2412.04245/) (2024)
- [When Flatness Does (Not) Guarantee Adversarial Robustness](https://mlsanity.com/paper/2510.14231/) (2025)
- [Mitigating Adversarial Attacks in Federated Learning with Trusted Execution Environments](https://mlsanity.com/paper/2309.07197/) (2023)

## Abstract (arXiv)

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 textitrobust 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 ℓ_∞ noise. (2) Any simple classifier is not robust: it must have high adversarial loss with ℓ_∞ perturbations. (3) Robust classification is possible, but only with more complex classifiers (exponentially more complex, in some examples). Moreover, textitthere 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.