# An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 17 Jan 2024.

## 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)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Imperceptible, Robust, and Targeted Adversarial Examples for Automatic Speech Recognition](https://mlsanity.com/paper/1903.10346/) (2019)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Adversarial Classification: Necessary conditions and geometric flows](https://mlsanity.com/paper/2011.10797/) (2020)
- [Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning](https://mlsanity.com/paper/2211.15223/) (2022)
- [Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker](https://mlsanity.com/paper/2302.10722/) (2023)

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

- [Consensus-based optimization for closed-box adversarial attacks and a connection to evolution strategies](https://mlsanity.com/paper/2506.24048/) (2025)
- [Genetic Column Generation for Computing Lower Bounds for Adversarial Classification](https://mlsanity.com/paper/2406.08331/) (2024)
- [Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functions](https://mlsanity.com/paper/2510.01969/) (2025)
- [Duality for the Adversarial Total Variation](https://mlsanity.com/paper/2604.18540/) (2026)
- [Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transport](https://mlsanity.com/paper/2609.22240/) (2026)

## Abstract (arXiv)

Despite the success of deep learning-based algorithms, it is widely known that neural networks may fail to be robust. A popular paradigm to enforce robustness is adversarial training (AT), however, this introduces many computational and theoretical difficulties. Recent works have developed a connection between AT in the multiclass classification setting and multimarginal optimal transport (MOT), unlocking a new set of tools to study this problem. In this paper, we leverage the MOT connection to propose computationally tractable numerical algorithms for computing universal lower bounds on the optimal adversarial risk and identifying optimal classifiers. We propose two main algorithms based on linear programming (LP) and entropic regularization (Sinkhorn). Our key insight is that one can harmlessly truncate the higher order interactions between classes, preventing the combinatorial run times typically encountered in MOT problems. We validate these results with experiments on MNIST and CIFAR-10, which demonstrate the tractability of our approach.