  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.
