The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification
Nicolás García Trillos, Matt Jacobs, Jakwang Kim; 24(45):1−56, 2023.
Abstract
This paper explores a range of adversarial multiclass classification problems and presents alternative formulations using: 1) a set of generalized barycenter problems introduced within the study, and 2) a series of multimarginal optimal transport problems where the number of marginals matches the number of classes in the original classification problem. These novel theoretical findings uncover a complex geometric structure in adversarial learning problems related to multiclass classification, expanding on recent research limited to binary classification scenarios. A key computational implication of these results is that by solving either the barycenter problem and its dual, or the multimarginal optimal transport problem and its dual, we can determine the optimal robust classification rule and optimal adversarial strategy for the original adversarial problem. Synthetic and real data examples are provided to illustrate our results.
[abs]