Despite the success of deep learning-based algorithms, it is widely known that neural networks may fail to be robust to adversarial perturbations of data. In response to this, a popular paradigm that has been developed to enforce robustness of learning models is adversarial training (AT), but this paradigm 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 talk, I will leverage the MOT connection to discuss new computationally tractable numerical algorithms for computing universal lower bounds on the optimal adversarial risk. The key insight in the AT setting is that one can harmlessly truncate high order interactions between classes, preventing the combinatorial run times typically encountered in MOT problems. I’ll present a rigorous complexity analysis of the proposed algorithm and validate our theoretical results experimentally on the MNIST and CIFAR-10 datasets, demonstrating the tractability of our approach. This is joint work with Matt Jacobs (UCSB), Jakwang Kim (UBC), and Matt Werenski (Tufts).