On the Complexity of Approximating Multimarginal Optimal Transport

arXiv1910.00152MaRDI QIDQ6326296

Author name not available (Why is that?)

Publication date: 30 September 2019

Abstract: 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 $mgeq3$. 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 $ildeO(n^{3m})$. We then propose two simple and extit{deterministic} algorithms for approximating the MOT problem. The first algorithm, which we refer to as extit{multimarginal Sinkhorn} algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of $ildeO(m^3{n}^{m}varepsilo{n}^{-2})$ for a tolerance $varepsilonin(0,1)$. This provides a first extit{near-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 extit{accelerated multimarginal Sinkhorn} algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is $ildeO(m^3{n}^{m+1/3}varepsilo{n}^{-4/3})$. This bound is better than that of the first algorithm in terms of $1/varepsilon$, and accelerated alternating minimization algorithm~citep{Tupitsa-2020-Multimarginal} in terms of $n$. Finally, we compare our new algorithms with the commercial LP solver extsc{Gurobi}. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.

Has companion code repository: https://github.com/shuge-mit/mot_project

This page was built for publication: On the Complexity of Approximating Multimarginal Optimal Transport

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326296)