On the Complexity of Approximating Multimarginal Optimal Transport
On the Complexity of Approximating Multimarginal Optimal Transport
复制标题
DOI：
--
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Tianyi Lin;Nhat Ho;Marco Cuturi;Michael I. Jordan
中科院分区：
文献类型：
--
作者：
Tianyi Lin;Nhat Ho;Marco Cuturi;Michael I. Jordan
我们研究了多边际最优运输距离(MOT)的近似复杂性，它是经典最优运输距离的推广，这里考虑了在$n$支撑点上每个离散概率分布之间支持的$m$离散概率分布。首先，我们证明了当$m\geq3$时，MOT问题的标准线性规划(LP)表示不是最小费用流问题。这一否定结果表明，某些组合算法，如网络单纯形法，不适合逼近MOT问题，而确定性内点算法的最坏情况下的复杂度界仍然是$tide{O}(n^{3m})$.在此基础上，我们提出了两种简单的逼近MOT问题的算法。第一种算法是Sinkhorn算法的证明有效的多边际推广算法，我们称其为Texttit(多边际Sinkhorn)算法。我们证明了对于(0，1)$中的容差$varepsilon，它的复杂性界为$tide{O}(m^3n^m\varepsilon^{-2})$。这为MOT问题的逼近提供了第一个{近线性时间}复杂性界保证，并且当$m=2$时与经典OT环境下Sinkhorn算法的最好复杂性界相匹配。第二种算法，我们称之为加速多边际Sinkhorn算法，通过结合估计序列来实现加速，其复杂度界是$tilde{O}(m^3n^{m+1/3}\varepsilon^{-4/3})。这个界优于第一个算法的$1/varepsilon$，以及加速交替极小化算法~Citep{Tupitsa-2020-多边际}的$n$。最后，我们将新算法与商业LP求解器\Textsc{Gurobi}进行了比较。在合成数据和真实图像上的初步结果证明了该算法的有效性和高效性。
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 \geq 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 $\tilde{O}(n^{3m})$. We then propose two simple and \textit{deterministic} algorithms for approximating the MOT problem. The first algorithm, which we refer to as \textit{multimarginal Sinkhorn} algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of $\tilde{O}(m^3n^m\varepsilon^{-2})$ for a tolerance $\varepsilon \in (0, 1)$. This provides a first \textit{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 \textit{accelerated multimarginal Sinkhorn} algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is $\tilde{O}(m^3n^{m+1/3}\varepsilon^{-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 \textsc{Gurobi}. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.