On the Complexity of Approximating Multimarginal Optimal Transport

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 $m\ge 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^3{n}^m{\epsilon }^{-2})$ for a tolerance $\epsilon \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^3{n}^{m+1/3}{\epsilon }^{-4/3})$. This bound is better than that of the first algorithm in terms of $1/\epsilon$, 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.

arXiv commentAccepted by Journal of Machine Learning Research; Add the references and the funding information; 40 pages, 14 figures

References in corpus (12)

• Fast Computation of Wasserstein Barycenters
• Optimal-transport formulation of electronic density-functional theory
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Towards the Kantorovich dual solution for strictly correlated electrons in atoms and molecules
• Semi-dual Regularized Optimal Transport
• Multi-marginal Wasserstein GAN
• Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport
• A Graph Theoretic Additive Approximation of Optimal Transport
• Accelerating Greedy Coordinate Descent Methods

Cited by in corpus (13)

• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
• Accelerating the Sinkhorn algorithm for sparse multi-marginal optimal transport by fast Fourier transforms
• Multi-marginal optimal transport and probabilistic graphical models
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent
• Kinetic correlation functionals from the entropic regularisation of the strictly-correlated electrons problem
• On the complexity of the optimal transport problem with graph-structured cost
• Barriers for recent methods in geodesic optimization
• Sliced Multi-Marginal Optimal Transport
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity
• Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport
• A Family of Pairwise Multi-Marginal Optimal Transports that Define a Generalized Metric