# Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 35 references that are in the map.
- First posted on arXiv 5 Apr 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Is Robustness the Cost of Accuracy? -- A Comprehensive Study on the Robustness of 18 Deep Image Classification Models](https://mlsanity.com/paper/1808.01688/) (2018)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Towards the first adversarially robust neural network model on MNIST](https://mlsanity.com/paper/1805.09190/) (2018)
- [SparseFool: a few pixels make a big difference](https://mlsanity.com/paper/1811.02248/) (2018)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Adversarial camera stickers: A physical camera-based attack on deep learning systems](https://mlsanity.com/paper/1904.00759/) (2019)
- [Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks](https://mlsanity.com/paper/2006.12834/) (2020)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Adversarial Perturbations Against Deep Neural Networks for Malware Classification](https://mlsanity.com/paper/1606.04435/) (2016)
- [Provable tradeoffs in adversarially robust classification](https://mlsanity.com/paper/2006.05161/) (2020)
- [The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization](https://mlsanity.com/paper/2002.11080/) (2020)
- [Adversarial Risk via Optimal Transport and Optimal Couplings](https://mlsanity.com/paper/1912.02794/) (2019)
- [A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance](https://mlsanity.com/paper/1901.10861/) (2019)
- [Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification](https://mlsanity.com/paper/2006.16384/) (2020)
- [More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models](https://mlsanity.com/paper/2002.04725/) (2020)
- [Sparsity-based Defense against Adversarial Attacks on Linear Classifiers](https://mlsanity.com/paper/1801.04695/) (2018)

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

- [Efficient and Robust Classification for Sparse Attacks](https://mlsanity.com/paper/2201.09369/) (2022)
- [Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpoint](https://mlsanity.com/paper/2401.13624/) (2024)
- [Generalized Likelihood Ratio Test for Adversarially Robust Hypothesis Testing](https://mlsanity.com/paper/2112.02209/) (2021)
- [Binary Classification Under ℓ0 Attacks for General Noise Distribution](https://mlsanity.com/paper/2203.04855/) (2022)
- [Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attacks](https://mlsanity.com/paper/2402.03576/) (2024)

## Abstract (arXiv)

It is well-known that machine learning models are vulnerable to small but cleverly-designed adversarial perturbations that can cause misclassification. While there has been major progress in designing attacks and defenses for various adversarial settings, many fundamental and theoretical problems are yet to be resolved. In this paper, we consider classification in the presence of ℓ0-bounded adversarial perturbations, a.k.a. sparse attacks. This setting is significantly different from other ℓp-adversarial settings, with p≥ 1, as the ℓ0-ball is non-convex and highly non-smooth. Under the assumption that data is distributed according to the Gaussian mixture model, our goal is to characterize the optimal robust classifier and the corresponding robust classification error as well as a variety of trade-offs between robustness, accuracy, and the adversary's budget. To this end, we develop a novel classification algorithm called FilTrun that has two main modules: Filtration and Truncation. The key idea of our method is to first filter out the non-robust coordinates of the input and then apply a carefully-designed truncated inner product for classification. By analyzing the performance of FilTrun, we derive an upper bound on the optimal robust classification error. We also find a lower bound by designing a specific adversarial strategy that enables us to derive the corresponding robust classifier and its achieved error. For the case that the covariance matrix of the Gaussian mixtures is diagonal, we show that as the input's dimension gets large, the upper and lower bounds converge; i.e. we characterize the asymptotically-optimal robust classifier. Throughout, we discuss several examples that illustrate interesting behaviors such as the existence of a phase transition for adversary's budget determining whether the effect of adversarial perturbation can be fully neutralized.