mlsanityData to 7 Oct 2026

Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model

arXiv 2104.02189 ↗First posted 5 Apr 2021cs.LG stat.MLcited by 5

Not on the map. Why?

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.

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

Builds on

33 of 35 references.

References · 33

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  5. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  6. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  7. 2018Robustness May Be at Odds with Accuracycited by 873
  8. 2015The Limitations of Deep Learning in Adversarial Settingscited by 784
  9. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  10. 2015Distillation as a Defense to Adversarial Perturbations against Deep Neural Networkscited by 675
  11. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  12. 2018Adversarially Robust Generalization Requires More Datacited by 318
21 more
  1. 2018Is Robustness the Cost of Accuracy? -- A Comprehensive Study on the Robustness of 18 Deep Image Classification Modelscited by 135
  2. 2019Adversarial Training Can Hurt Generalizationcited by 131
  3. 2018Are adversarial examples inevitable?cited by 113
  4. 2018Towards the first adversarially robust neural network model on MNISTcited by 104
  5. 2018SparseFool: a few pixels make a big differencecited by 94
  6. 2020Precise Tradeoffs in Adversarial Training for Linear Regressioncited by 76
  7. 2019Adversarial camera stickers: A physical camera-based attack on deep learning systemscited by 69
  8. 2020Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attackscited by 65
  9. 2019Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablationcited by 59
  10. 2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 52
  11. 2016Adversarial Perturbations Against Deep Neural Networks for Malware Classificationcited by 42
  12. 2020The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalizationcited by 39
  13. 2020Provable tradeoffs in adversarially robust classificationcited by 39
  14. 2019Adversarial Risk via Optimal Transport and Optimal Couplingscited by 36
  15. 2019A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distancecited by 32
  16. 2020More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Modelscited by 27
  17. 2020Sharp Statistical Guarantees for Adversarially Robust Gaussian Classificationcited by 27
  18. 2018Sparsity-based Defense against Adversarial Attacks on Linear Classifierscited by 8
  19. 2020A Bayes-Optimal View on Adversarial Examplescited by 8
  20. 2019A Fundamental Performance Limitation for Adversarial Classificationcited by 2
  21. 2020Adversarially Robust Classification based on GLRTcited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 0; 2024: 2.

5 papers.

  1. 2022Efficient and Robust Classification for Sparse Attackscited by 1
  2. 2024Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpointcited by 1
  3. 2021Generalized Likelihood Ratio Test for Adversarially Robust Hypothesis Testingcited by 0
  4. 2022Binary Classification Under ℓ0 Attacks for General Noise Distributioncited by 0
  5. 2024Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attackscited by 0