On the Complexity of Approximating Multimarginal Optimal Transport

We study the complexity of approximating the multimarginal optimal transport (MOT) distance, a generalization of the classical optimal transport distance, considered here between m discrete probability distributions supported each on n support points. First, we show that the standard linear programming (LP) representation of the MOT problem is not a minimum-cost flow problem when m ≥ 3. This negative result implies that some combinatorial algorithms, e.g., network simplex method, are not suitable for approximating the MOT problem, while the worst-case complexity bound for the deterministic interior-point algorithm remains a quantity of tildeO(n3m). We then propose two simple and textitdeterministic algorithms for approximating the MOT problem. The first algorithm, which we refer to as textitmultimarginal Sinkhorn algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of tildeO(m3nmvarepsilon-2) for a tolerance varepsilon ∈ (0, 1). This provides a first textitnear-linear time complexity bound guarantee for approximating the MOT problem and matches the best known complexity bound for the Sinkhorn algorithm in the classical OT setting when m = 2. The second algorithm, which we refer to as textitaccelerated multimarginal Sinkhorn algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is tildeO(m3nm+1/3varepsilon-4/3). This bound is better than that of the first algorithm in terms of 1/varepsilon, and accelerated alternating minimization algorithm~citepTupitsa-2020-Multimarginal in terms of n. Finally, we compare our new algorithms with the commercial LP solver textscGurobi. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.