An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification
This work addresses the computational challenges in adversarial training for neural networks, offering a more efficient method for robustness analysis, though it is incremental as it builds on existing connections to optimal transport.
The paper tackles the computational difficulty of adversarial training in multiclass classification by using multimarginal optimal transport to develop tractable algorithms for computing lower bounds on adversarial risk and identifying optimal classifiers. It demonstrates the approach's feasibility with experiments on MNIST and CIFAR-10 datasets.
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.