Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness

arXiv 2309.16096 ↗First posted 28 Sep 2023cs.LG cs.AIcited by 11

Not on the map. Why?

Abstract (arXiv)

The susceptibility of modern machine learning classifiers to adversarial examples has motivated theoretical results suggesting that these might be unavoidable. However, these results can be too general to be applicable to natural data distributions. Indeed, humans are quite robust for tasks involving vision. This apparent conflict motivates a deeper dive into the question: Are adversarial examples truly unavoidable? In this work, we theoretically demonstrate that a key property of the data distribution -- concentration on small-volume subsets of the input space -- determines whether a robust classifier exists. We further demonstrate that, for a data distribution concentrated on a union of low-dimensional linear subspaces, utilizing structure in data naturally leads to classifiers that enjoy data-dependent polyhedral robustness guarantees, improving upon methods for provable certification in certain regimes.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 45 of its 79 references that are in the map. First posted on arXiv 28 Sep 2023.

Builds on

45 of 79 references.

References · 45

2018The Unreasonable Effectiveness of Deep Features as a Perceptual Metriccited by 11,177
2013Intriguing properties of neural networkscited by 5,155
2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,268
2018Robustness May Be at Odds with Accuracycited by 880
2020Fast is better than free: Revisiting adversarial trainingcited by 727
2015Distillation as a Defense to Adversarial Perturbations against Deep Neural Networkscited by 678
2019Adversarial Training for Free!cited by 643
2017Countering Adversarial Images using Input Transformationscited by 520
2019On Evaluating Adversarial Robustnesscited by 447
2018Defense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Modelscited by 362
2019HopSkipJumpAttack: A Query-Efficient Decision-Based Attackcited by 333

33 more

2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 330
2018Adversarially Robust Generalization Requires More Datacited by 318
2018Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionalitycited by 282
2018Robustness via curvature regularization, and vice versacited by 175
2018Disentangling Adversarial Robustness and Generalizationcited by 172
2020Randomized Smoothing of All Shapes and Sizescited by 147
2018Are adversarial examples inevitable?cited by 113
2020Certified Defenses for Adversarial Patchescited by 101
2020(De)Randomized Smoothing for Certifiable Defense against Patch Attackscited by 98
2018Adversarial examples from computational constraintscited by 80
2018Adversarial vulnerability for any classifiercited by 78
2018Adversarial Examples that Fool both Computer Vision and Time-Limited Humanscited by 73
2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 53
2020Certified Defense to Image Transformations via Randomized Smoothingcited by 51
2018The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measurecited by 46
2020Dual Manifold Adversarial Robustness: Defense against Lp and non-Lp Adversarial Attackscited by 45
2018On the Geometry of Adversarial Examplescited by 43
2019Adversarial Risk via Optimal Transport and Optimal Couplingscited by 36
2013Robust subspace clusteringcited by 24
2021Learning a Self-Expressive Network for Subspace Clusteringcited by 24
2021ANCER: Anisotropic Certification via Sample-wise Volume Maximizationcited by 23
2020Adversarial Robustness of Supervised Sparse Codingcited by 22
2013Noisy Sparse Subspace Clusteringcited by 18
2020Adversarial robustness via robust low rank representationscited by 14
2018Divide, Denoise, and Defend against Adversarial Attackscited by 12
2018On Geometric Analysis of Affine Sparse Subspace Clusteringcited by 12
2019Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustnesscited by 12
2023Projected Randomized Smoothing for Certified Adversarial Robustnesscited by 11
2020On the Limitations of Denoising Strategies as Adversarial Defensescited by 9
2019Adversarially Robust Low Dimensional Representationscited by 7
2023Understanding Noise-Augmented Training for Randomized Smoothingcited by 7
2021Understanding Intrinsic Robustness Using Label Uncertaintycited by 3
2022Provably Adversarially Robust Nearest Prototype Classifierscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 2; 2026: 3.

11 papers.

2024A Curious Case of Searching for the Correlation between Training Data and Adversarial Robustness of Transformer Textual Modelscited by 5
2024Can Implicit Bias Imply Adversarial Robustness?cited by 5
2024Fermi-Bose Machine achieves both generalization and adversarial robustnesscited by 2
2025Adversarial Subspace Generation for Outlier Detection in High-Dimensional Datacited by 2
2024Certified Robustness against Sparse Adversarial Perturbations via Data Localizationcited by 1
2023On robust overfitting: adversarial training induced distribution matterscited by 0
2024Optimal Zero-Shot Detector for Multi-Armed Attackscited by 0
2025Geometric origin of adversarial vulnerability in deep learningcited by 0
2026Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysiscited by 0
2026Certified Robustness from Approximate Gaussian Mixture Structures in Pretrained Latent Spacescited by 0
2026The Role of Input Dimensionality in the Emergence and Targeted Control of Adversarial Examplescited by 0