Multi-Marginal Optimal Transport Defines a Generalized Metric

Abstract--We prove that the multi-marginal optimal transport (MMOT) problem defines a generalized metric. In addition, we prove that the distance induced by MMOT satisfies a generaliz ed triangle inequality that, to leading order, cannot be impro ved. The Optimal Transport (OT) problem dates back to 1781, when Monge [1] raised the problem of finding a way to transport one distribution of points (formally a probabili ty distribution) into another one at minimal cost. OT theory wa s greatly developed in the past century, especially assisted by Kantorovich [2] in 1941 and Brenier [3] in 1991, and, in part thanks to contemporary fast OT solvers, e.g. In this case, the minimum cost induced by (1) is called the W asserstein distance (WD), and it is a metric on the space of probability measures. The WD has gained increasing popularity in the past two decades thanks to its superiority over other metrics, and divergences, in many applications, e.g.