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

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

## 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 (most cited first, 20 of 20)

- [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)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples](https://mlsanity.com/paper/2010.03593/) (2020)
- [Improving Robustness using Generated Data](https://mlsanity.com/paper/2110.09468/) (2021)
- [Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?](https://mlsanity.com/paper/2104.09425/) (2021)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [Adversarial Risk via Optimal Transport and Optimal Couplings](https://mlsanity.com/paper/1912.02794/) (2019)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Robustness for Non-Parametric Classification: A Generic Attack and Defense](https://mlsanity.com/paper/1906.03310/) (2019)
- [Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries](https://mlsanity.com/paper/2104.08382/) (2021)

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

- [An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification](https://mlsanity.com/paper/2401.09191/) (2024)
- [Adapting to Evolving Adversaries with Regularized Continual Robust Training](https://mlsanity.com/paper/2502.04248/) (2025)
- [Adversarial Surrogate Risk Bounds for Binary Classification](https://mlsanity.com/paper/2506.09348/) (2025)
- [Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functions](https://mlsanity.com/paper/2510.01969/) (2025)
- [Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory](https://mlsanity.com/paper/2503.14299/) (2025)
- [Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transport](https://mlsanity.com/paper/2609.22240/) (2026)

## 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.