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

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.

• Publication year

  2023

• Venue

  Neural Information Processing Systems

• Publication date

  2023-09-28

• Fields of study

  Computer Science

• Identifiers
  DOI 10.48550/arXiv.2309.16096arXiv 2309.16096
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Projected Randomized Smoothing for Certified Adversarial Robustness

  2023cited by this paper
• Understanding Noise-Augmented Training for Randomized Smoothing

  2023cited by this paper
• Rethinking Lipschitz Neural Networks for Certified L-infinity Robustness

  2022cited by this paper
• Provably Adversarially Robust Nearest Prototype Classifiers

  2022cited by this paper
• Learning a Self-Expressive Network for Subspace Clustering

  2021cited by this paper
• Manifold adversarial training for supervised and semi-supervised learning

  2021cited by this paper
• A Nullspace Property for Subspace-Preserving Recovery

  2021cited by this paper
• ANCER: Anisotropic Certification via Sample-wise Volume Maximization

  2021cited by this paper
• Understanding Intrinsic Robustness Using Label Uncertainty

  2021influential reference
• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks

  2020cited by this paper
• On the Limitations of Denoising Strategies as Adversarial Defenses

  2020cited by this paper
• Randomized Smoothing of All Shapes and Sizes

  2020cited by this paper
• Fast is better than free: Revisiting adversarial training

  2020cited by this paper
• Certified Defense to Image Transformations via Randomized Smoothing

  2020cited by this paper
• Adversarial Robustness of Supervised Sparse Coding

  2020cited by this paper
• Manifold Regularization for Locally Stable Deep Neural Networks

  2020cited by this paper
• Dual Manifold Adversarial Robustness: Defense against Lp and non-Lp Adversarial Attacks

  2020cited by this paper
• Adversarial robustness via robust low rank representations

  2020cited by this paper
• Certified Defenses for Adversarial Patches

  2020cited by this paper
• Adversarial Risk via Optimal Transport and Optimal Couplings

  2019influential reference
• On Evaluating Adversarial Robustness

  2019cited by this paper
• Certified Adversarial Robustness via Randomized Smoothing

  2019influential reference
• Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness

  2019influential reference
• HopSkipJumpAttack: A Query-Efficient Decision-Based Attack

  2019cited by this paper
• Adversarial Training for Free!

  2019cited by this paper
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers

  2019cited by this paper
• Lower Bounds on Adversarial Robustness from Optimal Transport

  2019influential reference
• Adversarially Robust Low Dimensional Representations

  2019cited by this paper
• On Geometric Analysis of Affine Sparse Subspace Clustering

  2018cited by this paper
• Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality

  2018cited by this paper
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples

  2018cited by this paper
• Divide, Denoise, and Defend against Adversarial Attacks

  2018cited by this paper
• Defense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Models

  2018cited by this paper
• Adversarial vulnerability for any classifier

  2018cited by this paper
• The Unreasonable Effectiveness of Deep Features as a Perceptual Metric

  2018cited by this paper
• Countering Adversarial Images using Input Transformations

  2018cited by this paper
• Adversarially Robust Generalization Requires More Data

  2018cited by this paper
• Adversarial examples from computational constraints

  2018cited by this paper
• Adversarial Examples that Fool both Computer Vision and Time-Limited Humans

  2018cited by this paper
• Are adversarial examples inevitable?

  2018influential reference
• The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure

  2018influential reference
• Robustness May Be at Odds with Accuracy

  2018cited by this paper
• On the Geometry of Adversarial Examples

  2018cited by this paper
• Robustness via Curvature Regularization, and Vice Versa

  2018cited by this paper
• Disentangling Adversarial Robustness and Generalization

  2018cited by this paper
• Generalized No Free Lunch Theorem for Adversarial Robustness

  2018cited by this paper
• Low rank representation with adaptive distance penalty for semi-supervised subspace classification

  2017cited by this paper
• Generalized Principal Component Analysis

  2017cited by this paper
• Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks

  2015cited by this paper
• Geometric Conditions for Subspace-Sparse Recovery

  2015cited by this paper
• Nearest Regularized Subspace for Hyperspectral Classification

  2014cited by this paper
• Semi-supervised classification based on subspace sparse representation

  2013cited by this paper
• Intriguing properties of neural networks

  2013cited by this paper
• Noisy Sparse Subspace Clustering

  2013cited by this paper
• Robust Subspace Clustering

  2013cited by this paper
• An Invitation to Compressive Sensing

  2013cited by this paper
• Sparse neighbor representation for classification

  2012cited by this paper
• Robust classification using structured sparse representation

  2011cited by this paper
• Concise Formulas for the Area and Volume of a Hyperspherical Cap

  2011cited by this paper
• Learning the sparse representation for classification

  2011cited by this paper
• A Geometric Analysis of Subspace Clustering with Outliers

  2011cited by this paper
• Block-Sparse Recovery via Convex Optimization

  2011cited by this paper
• Linear Regression for Face Recognition

  2010cited by this paper
• Sparse Representation for Computer Vision and Pattern Recognition

  2010cited by this paper
• Robust Face Recognition via Sparse Representation

  2009cited by this paper
• The mnist database of handwritten digits

  2005influential reference
• Optimally sparse representation in general (nonorthogonal) dictionaries via l minimization.

  2003cited by this paper
• Subspace Classification for Face Recognition

  2002cited by this paper
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

  2001cited by this paper
• Subspace classifiers in recognition of handwritten digits

  1997cited by this paper

• Adversarial Subspace Generation for Outlier Detection in High-Dimensional Data

  2025cites this paper
• A Curious Case of Searching for the Correlation between Training Data and Adversarial Robustness of Transformer Textual Models

  2024cites this paper
• Optimal Zero-Shot Detector for Multi-Armed Attacks

  2024cites this paper
• Local-contrastive-learning machine with both generalization and adversarial robustness: A statistical physics analysis

  2024cites this paper
• Can Implicit Bias Imply Adversarial Robustness?

  2024cites this paper
• GBKPA and AuxShield: Addressing adversarial robustness and transferability in android malware detection

  2024cites this paper
• Certified Robustness against Sparse Adversarial Perturbations via Data Localization

  2024cites this paper
• On robust overfitting: adversarial training induced distribution matters

  2023cites this paper
• Certified Robustness against Sparse Adversarial Perturbations via Data Localization

  year unknowncites this paper