mlsanityData to 7 Oct 2026

Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory

arXiv 2503.14299 ↗First posted 18 Mar 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Randomization as a mean to improve the adversarial robustness of machine learning models has recently attracted significant attention. Unfortunately, much of the theoretical analysis so far has focused on binary classification, providing only limited insights into the more complex multiclass setting. In this paper, we take a step toward closing this gap by drawing inspiration from the field of graph theory. Our analysis focuses on discrete data distributions, allowing us to cast the adversarial risk minimization problems within the well-established framework of set packing problems. By doing so, we are able to identify three structural conditions on the support of the data distribution that are necessary for randomization to improve robustness. Furthermore, we are able to construct several data distributions where (contrarily to binary classification) switching from a deterministic to a randomized solution significantly reduces the optimal adversarial risk. These findings highlight the crucial role randomization can play in enhancing robustness to adversarial attacks in multiclass classification.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 27 of its 45 references that are in the map. First posted on arXiv 18 Mar 2025.

Builds on

27 of 45 references.

References · 27

  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. 2020Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attackscited by 1,442
  5. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  6. 2016Adversarial Machine Learning at Scalecited by 934
  7. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  8. 2017Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methodscited by 542
  9. 2017Mitigating Adversarial Effects Through Randomizationcited by 382
  10. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  11. 2018Robustness via curvature regularization, and vice versacited by 174
  12. 2018Stochastic Activation Pruning for Robust Adversarial Defensecited by 171
15 more
  1. 2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 52
  2. 2020Randomization matters. How to defend against strong adversarial attackscited by 37
  3. 2019Theoretical evidence for adversarial robustness through randomizationcited by 33
  4. 2022The Many Faces of Adversarial Riskcited by 28
  5. 2020Adversarial Robustness of Stabilized NeuralODEs Might be from Obfuscated Gradientscited by 22
  6. 2021Mixed Nash Equilibria in the Adversarial Examples Gamecited by 22
  7. 2022The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classificationcited by 21
  8. 2022Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classificationcited by 15
  9. 2021Local Competition and Stochasticity for Adversarial Robustness in Deep Learningcited by 12
  10. 2022Towards Consistency in Adversarial Classificationcited by 12
  11. 2021On the robustness of randomized classifiers to adversarial examplescited by 9
  12. 2023On the existence of solutions to adversarial training in multiclass classificationcited by 9
  13. 2023Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attackercited by 6
  14. 2023On the Role of Randomization in Adversarially Robust Classificationcited by 4
  15. 2022Rethinking Feature Uncertainty in Stochastic Neural Networks for Adversarial Robustnesscited by 2

Built on by

Not cited yet.