# Structural Extensions of Basis Pursuit: Guarantees on Adversarial Robustness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 5 May 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Are Transformers More Robust Than CNNs?](https://mlsanity.com/paper/2111.05464/) (2021)
- [A Unified Survey on Anomaly, Novelty, Open-Set, and Out-of-Distribution Detection: Solutions and Future Challenges](https://mlsanity.com/paper/2110.14051/) (2021)
- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Dense Extreme Inception Network: Towards a Robust CNN Model for Edge Detection](https://mlsanity.com/paper/1909.01955/) (2019)
- [Convolutional Neural Networks Analyzed via Convolutional Sparse Coding](https://mlsanity.com/paper/1607.08194/) (2016)
- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [Adversarial Robustness of Supervised Sparse Coding](https://mlsanity.com/paper/2010.12088/) (2020)
- [Architectural Adversarial Robustness: The Case for Deep Pursuit](https://mlsanity.com/paper/2011.14427/) (2020)
- [Adversarial Noise Attacks of Deep Learning Architectures -- Stability Analysis via Sparse Modeled Signals](https://mlsanity.com/paper/1805.11596/) (2018)
- [Dataless Model Selection with the Deep Frame Potential](https://mlsanity.com/paper/2003.13866/) (2020)
- [Reframing Neural Networks: Deep Structure in Overcomplete Representations](https://mlsanity.com/paper/2103.05804/) (2021)

## Abstract (arXiv)

While deep neural networks are sensitive to adversarial noise, sparse coding using the Basis Pursuit (BP) method is robust against such attacks, including its multi-layer extensions. We prove that the stability theorem of BP holds upon the following generalizations: (i) the regularization procedure can be separated into disjoint groups with different weights, (ii) neurons or full layers may form groups, and (iii) the regularizer takes various generalized forms of the ℓ1 norm. This result provides the proof for the architectural generalizations of Cazenavette et al. (2021), including (iv) an approximation of the complete architecture as a shallow sparse coding network. Due to this approximation, we settled to experimenting with shallow networks and studied their robustness against the Iterative Fast Gradient Sign Method on a synthetic dataset and MNIST. We introduce classification based on the ℓ2 norms of the groups and show numerically that it can be accurate and offers considerable speedups. In this family, linear transformer shows the best performance. Based on the theoretical results and the numerical simulations, we highlight numerical matters that may improve performance further.