# Origins of Low-dimensional Adversarial Perturbations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 43 references that are in the map.
- First posted on arXiv 25 Mar 2022.

## Builds on (most cited first, 30 of 30)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models](https://mlsanity.com/paper/1712.04248/) (2017)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [A Fourier Perspective on Model Robustness in Computer Vision](https://mlsanity.com/paper/1906.08988/) (2019)
- [Simple Black-box Adversarial Attacks](https://mlsanity.com/paper/1905.07121/) (2019)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Predicting the Generalization Gap in Deep Networks with Margin Distributions](https://mlsanity.com/paper/1810.00113/) (2018)
- [Low Frequency Adversarial Perturbation](https://mlsanity.com/paper/1809.08758/) (2018)
- [Adversarial vulnerability for any classifier](https://mlsanity.com/paper/1802.08686/) (2018)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [Black-Box Adversarial Attack with Transferable Model-based Embedding](https://mlsanity.com/paper/1911.07140/) (2019)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Art of singular vectors and universal adversarial perturbations](https://mlsanity.com/paper/1709.03582/) (2017)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [Subspace Attack: Exploiting Promising Subspaces for Query-Efficient Black-box Attacks](https://mlsanity.com/paper/1906.04392/) (2019)
- [A single gradient step finds adversarial examples on random two-layers neural networks](https://mlsanity.com/paper/2104.03863/) (2021)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [Robustness of classifiers to universal perturbations: a geometric perspective](https://mlsanity.com/paper/1705.09554/) (2017)
- [Most ReLU Networks Suffer from ℓ2 Adversarial Perturbations](https://mlsanity.com/paper/2010.14927/) (2020)

## Built on by (most cited first, 4 of 4)

- [How many dimensions are required to find an adversarial example?](https://mlsanity.com/paper/2303.14173/) (2023)
- [Eigenpatches -- Adversarial Patches from Principal Components](https://mlsanity.com/paper/2306.10963/) (2023)
- [Traversing the Subspace of Adversarial Patches](https://mlsanity.com/paper/2412.01527/) (2024)
- [Probing the Geometry of Color Representations in Multilingual Language Models](https://mlsanity.com/paper/2610.18331/) (2026)

## Abstract (arXiv)

In this paper, we initiate a rigorous study of the phenomenon of low-dimensional adversarial perturbations (LDAPs) in classification. Unlike the classical setting, these perturbations are limited to a subspace of dimension k which is much smaller than the dimension d of the feature space. The case k=1 corresponds to so-called universal adversarial perturbations (UAPs; Moosavi-Dezfooli et al., 2017). First, we consider binary classifiers under generic regularity conditions (including ReLU networks) and compute analytical lower-bounds for the fooling rate of any subspace. These bounds explicitly highlight the dependence of the fooling rate on the pointwise margin of the model (i.e., the ratio of the output to its L2 norm of its gradient at a test point), and on the alignment of the given subspace with the gradients of the model w.r.t. inputs. Our results provide a rigorous explanation for the recent success of heuristic methods for efficiently generating low-dimensional adversarial perturbations. Finally, we show that if a decision-region is compact, then it admits a universal adversarial perturbation with L2 norm which is √d times smaller than the typical L2 norm of a data point. Our theoretical results are confirmed by experiments on both synthetic and real data.