# Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 28 references that are in the map.
- First posted on arXiv 2 Oct 2025.

## Builds on (most cited first, 20 of 20)

- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Fast Optimal Transport Averaging of Neuroimaging Data](https://mlsanity.com/paper/1503.08596/) (2015)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [The Geometry of Adversarial Training in Binary Classification](https://mlsanity.com/paper/2111.13613/) (2021)
- [Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification](https://mlsanity.com/paper/2206.09098/) (2022)
- [Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning](https://mlsanity.com/paper/2211.15223/) (2022)
- [On the existence of solutions to adversarial training in multiclass classification](https://mlsanity.com/paper/2305.00075/) (2023)
- [Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker](https://mlsanity.com/paper/2302.10722/) (2023)
- [The Adversarial Consistency of Surrogate Risks for Binary Classification](https://mlsanity.com/paper/2305.09956/) (2023)
- [An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification](https://mlsanity.com/paper/2401.09191/) (2024)
- [Barycenters for the Hellinger--Kantorovich distance over ℝd](https://mlsanity.com/paper/1910.14572/) (2019)
- [Kantorovich-Rubinstein distance and barycenter for finitely supported measures: Foundations and Algorithms](https://mlsanity.com/paper/2112.03581/) (2021)
- [A mean curvature flow arising in adversarial training](https://mlsanity.com/paper/2404.14402/) (2024)
- [Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifier](https://mlsanity.com/paper/2404.17358/) (2024)
- [Unbalanced Kantorovich-Rubinstein distance, plan, and barycenter on finite spaces: A statistical perspective](https://mlsanity.com/paper/2211.08858/) (2022)
- [Genetic Column Generation for Computing Lower Bounds for Adversarial Classification](https://mlsanity.com/paper/2406.08331/) (2024)
- [Uniform Convergence of Adversarially Robust Classifiers](https://mlsanity.com/paper/2406.14682/) (2024)
- [On a class of adversarial classification problems which admit a continuous solution](https://mlsanity.com/paper/2502.21170/) (2025)

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

- [Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transport](https://mlsanity.com/paper/2609.22240/) (2026)

## Abstract (arXiv)

We consider adversarially robust classification in a multiclass setting under arbitrary loss functions and derive dual and barycentric reformulations of the corresponding learner-agnostic robust risk minimization problem. We provide explicit characterizations for important cases such as the cross-entropy loss, loss functions with a power form, and the quadratic loss, extending in this way available results for the 0-1 loss. These reformulations enable efficient computation of sharp lower bounds for adversarial risks and facilitate the design of robust classifiers beyond the 0-1 loss setting. Our paper uncovers interesting connections between adversarial robustness, α-fair packing problems, and generalized barycenter problems for arbitrary positive measures where Kullback-Leibler and Tsallis entropies are used as penalties. Our theoretical results are accompanied with illustrative numerical experiments where we obtain tighter lower bounds for adversarial risks with the cross-entropy loss function.