mlsanityData to 14 Oct 2026

Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker

arXiv 2302.10722 ↗First posted 21 Feb 2023cs.LG cs.CRcited by 6

Not on the map. Why?

Abstract (arXiv)

Finding classifiers robust to adversarial examples is critical for their safe deployment. Determining the robustness of the best possible classifier under a given threat model for a given data distribution and comparing it to that achieved by state-of-the-art training methods is thus an important diagnostic tool. In this paper, we find achievable information-theoretic lower bounds on loss in the presence of a test-time attacker for multi-class classifiers on any discrete dataset. We provide a general framework for finding the optimal 0-1 loss that revolves around the construction of a conflict hypergraph from the data and adversarial constraints. We further define other variants of the attacker-classifier game that determine the range of the optimal loss more efficiently than the full-fledged hypergraph construction. Our evaluation shows, for the first time, an analysis of the gap to optimal robustness for classifiers in the multi-class setting on benchmark datasets.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 20 of its 34 references that are in the map. First posted on arXiv 21 Feb 2023.

Builds on

20 of 34 references.

References · 20

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2013Intriguing properties of neural networkscited by 5,155
  4. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,998
  5. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,517
  6. 2020Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attackscited by 1,451
  7. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 328
  8. 2018Adversarially Robust Generalization Requires More Datacited by 318
  9. 2020Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examplescited by 278
  10. 2021Improving Robustness using Generated Datacited by 234
  11. 2021Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?cited by 113
  12. 2020SoK: Certified Robustness for Deep Neural Networkscited by 105
8 more
  1. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  2. 2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 53
  3. 2018The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measurecited by 46
  4. 2019Adversarial Risk via Optimal Transport and Optimal Couplingscited by 36
  5. 2022The Many Faces of Adversarial Riskcited by 28
  6. 2022The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classificationcited by 21
  7. 2019Robustness for Non-Parametric Classification: A Generic Attack and Defensecited by 12
  8. 2021Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversariescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 1.

6 papers.

  1. 2024An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classificationcited by 5
  2. 2025Adapting to Evolving Adversaries with Regularized Continual Robust Trainingcited by 2
  3. 2025Adversarial Surrogate Risk Bounds for Binary Classificationcited by 1
  4. 2025Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functionscited by 1
  5. 2025Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theorycited by 0
  6. 2026Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transportcited by 0