On the Complexity of Approximating Multimarginal Optimal Transport

Tianyi LinNhat HoMarco CuturiMichael I. Jordan

article2022JMLR73 citations

Establishes the computational limits of discrete multimarginal optimal transport and introduces near-linear time Sinkhorn-based algorithms with rigorous complexity bounds that scale efficiently to multiple probability distributions.

Listen

Multimarginal optimal transport provides a mathematical foundation for simultaneously aligning or matching multiple probability distributions. This framework has become increasingly critical across diverse fields, including economics, fluid dynamics, physics, and modern machine learning applications such as generative adversarial networks, domain adaptation, and computing free-support Wasserstein barycenters. However, scaling these methods presents severe computational challenges because discrete representations across several distributions involve an exponential number of decision variables, causing standard optimization techniques to become computationally impractical.

The article aims to evaluate the fundamental computational complexity of the multimarginal optimal transport problem and demonstrate provably efficient deterministic approximation algorithms. Specifically, the authors analyze the underlying network structure of the standard linear programming formulation and establish rigorous computational complexity bounds for two newly designed approximation algorithms.

To establish these properties, the authors conduct a theoretical structural reduction by linking the linear programming form of multimarginal transport to multidimensional matching problems. They then develop two deterministic algorithms utilizing entropy regularization, which smooths the dual optimization problem: the multimarginal Sinkhorn algorithm, incorporating a greedy coordinate selection rule, and an accelerated variant using Nesterov estimate sequences and monotone search steps. Both algorithms are paired with a specialized rank-one tensor rounding scheme to map regularized outputs back to exact feasibility. The authors validate their theoretical findings through numerical experiments on both synthetic image data and real handwritten digit datasets, benchmarking performance against the standard commercial linear programming solver Gurobi.

The article establishes several key findings regarding structure, efficiency, and practical execution. First, the standard linear programming representation of multimarginal optimal transport is not a minimum-cost flow problem when matching three or more distributions, demonstrating that fast combinatorial network simplex methods cannot be applied and leaving standard interior-point solvers with poor worst-case complexity scaling. Second, the proposed multimarginal Sinkhorn algorithm achieves the first near-linear time computational complexity bound with respect to the total number of variable combinations, making its dependence on support size mathematically unimprovable in general settings. Third, the accelerated multimarginal Sinkhorn algorithm improves runtime dependence on target approximation precision at the expense of a slightly higher dependence on support size. Finally, empirical evaluations show that both proposed methods significantly outperform commercial solvers, with standard solvers running out of memory on high-resolution image benchmarks while the new algorithms successfully compute high-quality approximations.

These findings provide clear guidelines for managing computational cost and performance across large-scale optimization tasks. Decision-makers should recognize that classical commercial linear programming solvers are fundamentally ill-suited for multi-distribution transport problems involving three or more marginals. Instead, selecting the appropriate approximation algorithm depends on the operational accuracy requirements: the standard multimarginal Sinkhorn algorithm is ideal for applications tolerating moderate precision on large support grids, such as computer vision and image processing, whereas the accelerated variant is superior for high-precision scientific or economic applications.

Organizations implementing multi-distribution alignment should transition away from general-purpose linear programming software toward entropy-regularized Sinkhorn frameworks. Before broad deployment, development teams should pilot these methods and explore parallelized or distributed computing implementations, which are particularly valuable for mitigating the gradient computation overhead in the accelerated algorithm. Further technical exploration should focus on integrating low-rank tensor decompositions and explicit sparsity penalties to reduce memory demands and recover sparse transport plans.

Confidence in the mathematical complexity bounds and convergence guarantees is high, as the theoretical analysis rests on rigorous optimization proofs. Readers should note, however, that the general multimarginal transport problem remains inherently subject to the curse of dimensionality as the number of distributions grows, and the present algorithms assume discrete, balanced probability measures with dense support. Caution is warranted when applying these baseline algorithms to unbalanced or continuous mass distributions without further dimension-reduction or problem-specific structural simplifications.

ENSAE Paris Google University of California University of Texas at Austin multimarginal optimal transport computational complexity approximation algorithms

arXiv: 1910.00152

Paper: On the Efficiency of Entropic Regularized Algorithms for Optimal Transport, Tianyi Lin et al. (2022). It analyzes the computational complexity and accelerated first-order optimization schemes for entropic regularized Sinkhorn algorithms in classical optimal transport, establishing the foundational theoretical bounds and accelerated techniques generalized by this work.
Paper: Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances, Marco Cuturi (2013). It introduces the entropic regularization formulation and matrix-scaling Sinkhorn algorithm that serve as the core basis for multimarginal Sinkhorn approximations.
Paper: Computational Optimal Transport, Gabriel Peyré et al. (2018). It provides a comprehensive overview of computational optimal transport, including Kantorovich linear programs, entropic regularization, and foundational multimarginal formulations.

No sufficiently relevant recommendations were found.

Cover for 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 ≥ 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 Õ(n^{3m}). We then propose two simple and deterministic algorithms for approximating the MOT problem. The first algorithm, which we refer to as multimarginal Sinkhorn algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of Õ(m^{3}n^{m}ε^{−2}) for a tolerance ε ∈ (0, 1). This provides a first 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 accelerated multimarginal Sinkhorn algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is Õ(m^{3}n^{m+1/3}ε^{−4/3}). This bound is better than that of the first algorithm in terms of 1/ε, and accelerated alternating minimization algorithm (Tupitsa et al., 2020) in terms of n. Finally, we compare our new algorithms with the commercial LP solver GUROBI. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.

Keywords

multimarginal optimal transport computational complexity approximation algorithms multimarginal Sinkhorn algorithms transportation polytope minimum-cost flow problems interior-point algorithms cost tensor

1. Introduction
2. Preliminaries
2.1 Linear programming representation
2.2 Entropic regularized MOT and its dual form
2.3 Properties of dual entropic regularized multimarginal OT
3. Computational Hardness
3.1 Unimodularity, minimum-cost flow and matching
3.2 Main result
3.3 Discussion
4. Multimarginal Sinkhorn Algorithm
4.1 Algorithmic procedure
4.2 Technical lemmas
4.3 Main results
5. Accelerating Multimarginal Sinkhorn Algorithm
5.1 Algorithmic procedure
5.2 Technical lemmas
5.3 Main results
6. Experiments
6.1 Experiments on synthetic data
6.2 Experiments on real images
7. Conclusion
8. Acknowledgements
References

Knowls

Knowl 1 — Discrete multimarginal optimal transport and approximation target
definition
For $m\ge 2$ probability vectors $r_1,\ldots,r_m\in\Delta^n$ and a nonnegative cost tensor $C\in\mathbb{R}_+^{n\times\cdots\times n}$ , the discrete multimarginal optimal transport problem is
$\min_{X\in\mathbb{R}_+^{n\times\cdots\times n}}\ \langle C,X\rangle \quad\text{subject to}\quad r_k(X)=r_k\ \text{for every }k\in[m].$
Here $X_{i_1,\ldots,i_m}$ is a nonnegative transportation plan, $\langle C,X\rangle=\sum_{i_1,\ldots,i_m}C_{i_1,\ldots,i_m}X_{i_1,\ldots,i_m}$ , and the $k$ -th marginal is the vector whose $j$ -th entry is
$[r_k(X)]_j=\sum_{i_\ell,\,\ell\ne k}X_{i_1,\ldots,i_{k-1},j,i_{k+1},\ldots,i_m}.$
The linear program has $n^m$ unknown tensor entries and $mn$ marginal equalities, although some equalities are redundant. If $X^*$ is an optimal plan, an $\varepsilon$ -approximate multimarginal transportation plan is a nonnegative tensor $\widehat X$ satisfying all original marginals exactly and
$\langle C,\widehat X\rangle\le \langle C,X^*\rangle+\varepsilon,$
where $\varepsilon>0$ is the desired additive accuracy.
Knowl 2 — Dual formulation of entropically regularized MOT
model/method
The paper solves a regularized version of the discrete MOT problem before rounding its output to a feasible plan for the unregularized problem. For a regularization parameter $\eta>0$ , the regularized primal problem is
$\min_{X\ge 0}\ \langle C,X\rangle-\eta H(X) \quad\text{subject to}\quad r_k(X)=r_k\ \text{for every }k\in[m],$
where $H(X)=-\langle X,\log X-\mathbf{1}\rangle$ is the entropy, with logarithms and the all-ones tensor applied entrywise.

After rescaling the dual variables, let $\beta=(\beta_1,\ldots,\beta_m)$ with each $\beta_k\in\mathbb{R}^n$ , and define
$B_{i_1,\ldots,i_m}(\beta)=\exp\!\left(\sum_{k=1}^m\beta_{k,i_k}-\frac{C_{i_1,\ldots,i_m}}{\eta}\right),$
where $\|B(\beta)\|_1$ is the sum of all tensor entries. The unconstrained smooth dual objective is
$\phi(\beta)=\log\bigl(\|B(\beta)\|_1\bigr)-\sum_{k=1}^m\beta_k^\top r_k, \qquad \min_{\beta\in\mathbb{R}^{mn}}\phi(\beta).$
Its gradient with respect to block $\beta_k$ is
$\nabla_{\beta_k}\phi(\beta)=\frac{r_k(B(\beta))}{\|B(\beta)\|_1}-r_k.$
Thus, dual optimization seeks a tensor whose normalized marginals match the prescribed distributions. The paper establishes that the dual objective is $m$ -smooth with respect to the Euclidean norm and that an optimal solution can be chosen with bounded norm, which enables the subsequent complexity guarantees.
Knowl 3 — The standard MOT linear program is not a minimum-cost flow problem for three or more marginals
theoretical result
For the general discrete MOT linear program with $m\ge 3$ , the marginal constraint matrix is not a minimum-cost-flow constraint matrix. In particular, it is not totally unimodular in general, so the network-flow structure available for classical two-marginal optimal transport does not extend to multimarginal transport.

A concrete instance with $m=3$ and $n=2$ has a $4\times 8$ effective constraint matrix containing a $4\times4$ submatrix with determinant $2$ , which directly violates total unimodularity. More generally, the paper proves the result by reducing $m$ -dimensional matching to the integer counterpart of MOT with uniform marginals $r_k=\mathbf{1}_n/n$ . A binary feasible tensor corresponds one-to-one with an $m$ -dimensional matching, an NP-complete problem already for $m=3$ .

Consequently, network simplex and specialized minimum-cost-flow interior-point bounds cannot be applied to the general MOT formulation. The standard deterministic interior-point approach instead has worst-case complexity $\widetilde O(n^{3m})$ . The theorem concerns the general MOT formulation; specially structured individual instances may still admit additional algorithms.
Knowl 4 — Greedy multimarginal Sinkhorn algorithm
algorithm
The multimarginal Sinkhorn method is a deterministic greedy block-coordinate algorithm for the dual objective $\phi$ . Given a nonnegative cost tensor $C$ , regularization parameter $\eta>0$ , dense target marginals $r_1,\ldots,r_m\in\Delta^n$ , and stopping tolerance $\varepsilon_0>0$ , define
$\rho(a,b)=\mathbf{1}_n^\top(b-a)+\sum_{j=1}^n a_j\log\frac{a_j}{b_j},$
for positive vectors $a,b\in\mathbb{R}^n$ , and define the residual $E_t=\sum_{k=1}^m\|r_k(B(\beta^t))-r_k\|_1$ . The algorithm is:
Input: cost tensor $C$ , regularization $\eta$ , target marginals $r_1,\ldots,r_m$ , tolerance $\varepsilon_0$
Initialize $t=0$ and $\beta^0=0\in\mathbb{R}^{mn}$
while $E_t>\varepsilon_0$ do
    Choose $K=\arg\max_{1\le k\le m}\rho(r_k,r_k(B(\beta^t)))$
    Set $\beta_k^{t+1}=\beta_k^t$ for every $k\ne K$
    Set $\beta_K^{t+1}=\beta_K^t+\log(r_K)-\log(r_K(B(\beta^t)))$
    Set $t=t+1$
end while
return $B(\beta^t)$
The logarithms and divisions in the coordinate update are entrywise. The selected block is updated exactly so that the corresponding normalized marginal equals its target marginal. After the first update, the tensor has unit total mass, and each iteration requires $O(n^m)$ arithmetic operations in the direct implementation.
Knowl 5 — Multimarginal rounding scheme with exact marginal repair
algorithm
The Sinkhorn output need not have the original marginals exactly, so the paper introduces a deterministic rounding procedure. Given a nonnegative tensor $X\in\mathbb{R}_+^{n\times\cdots\times n}$ and target probability vectors $r_1,\ldots,r_m\in\Delta^n$ , initialize $X^{(0)}=X$ . For $k=1,\ldots,m$ , compute
$[z_k]_j=\min\left\{1,\frac{[r_k]_j}{[r_k(X^{(k-1)})]_j}\right\},$
and multiply every slice of $X^{(k-1)}$ with index $i_k=j$ by $[z_k]_j$ , producing $X^{(k)}$ . After all $m$ passes, define the nonnegative residual vectors
$e_k=r_k-r_k(X^{(m)}).$
If the residuals are nonzero, return
$Y=X^{(m)}+\frac{e_1\otimes e_2\otimes\cdots\otimes e_m}{\|e_1\|_1^{m-1}};$
if all residuals vanish, return $Y=X^{(m)}$ . The residuals have equal total mass, so the rank-one correction has $k$ -th marginal $e_k$ . Therefore $Y\ge0$ and $r_k(Y)=r_k$ for every $k$ . The procedure also satisfies
$\|Y-X\|_1\le 2\sum_{k=1}^m\|r_k(X)-r_k\|_1,$
and its direct implementation costs $O(mn^m)$ arithmetic operations.
Knowl 6 — Convergence certificate for greedy multimarginal Sinkhorn
theoretical result
Assume every target marginal entry is positive and define
$R=\frac{\|C\|_\infty}{\eta}-\log\left(\min_{1\le k\le m,\,1\le j\le n}[r_k]_j\right),$
where $\|C\|_\infty$ is the largest cost-tensor entry. For the iterates generated by the greedy multimarginal Sinkhorn method, let $\beta^*$ be a suitably shifted optimal dual solution and let $E_t=\sum_{k=1}^m\|r_k(B(\beta^t))-r_k\|_1$ . The paper proves
$\phi(\beta^t)-\phi(\beta^*)\le R E_t,$
and the per-iteration decrease satisfies
$\phi(\beta^t)-\phi(\beta^{t+1})\ge \frac12\left(\frac{E_t}{m}\right)^2.$
The first inequality follows from a uniform bound on the within-block ranges of the dual variables, while the second uses the KL progress of the selected coordinate and Pinsker's inequality. Consequently, the number of iterations needed to reach $E_t\le\varepsilon_0$ is at most
$2+\frac{2m^2R}{\varepsilon_0}.$
These bounds are the key reason the greedy choice of the next marginal yields a finite, explicit complexity guarantee rather than only an asymptotic convergence statement.
Knowl 7 — Near-linear-in-variables approximation via multimarginal Sinkhorn
theoretical result
For a desired additive MOT accuracy $\varepsilon>0$ , let
$\eta=\frac{\varepsilon}{2m\log n}, \qquad \varepsilon_0=\frac{\varepsilon}{8\|C\|_\infty},$
and smooth each possibly sparse marginal by
$\widetilde r_k=\left(1-\frac{\varepsilon_0}{4m}\right)r_k+\frac{\varepsilon_0}{4mn}\mathbf{1}_n.$
The end-to-end method runs greedy multimarginal Sinkhorn on the smoothed marginals until its residual is at most $\varepsilon_0/2$ , then applies the exact marginal-repair rounding scheme to the resulting tensor. The output $\widehat X$ has the original marginals and satisfies
$\langle C,\widehat X\rangle\le \langle C,X^*\rangle+\varepsilon.$
Its arithmetic complexity is
$O\left(\frac{m^3 n^m\|C\|_\infty^2\log n}{\varepsilon^2}\right).$
Because $n^m$ is the number of unknown entries in the MOT tensor, this is near-linear in the input variable count, up to logarithmic and polynomial factors in $m$ , $\|C\|_\infty$ , and $1/\varepsilon$ . The dependence on $n^m$ is therefore optimal up to logarithmic factors for a general dense MOT instance.
Knowl 8 — Accelerated multimarginal Sinkhorn algorithm
algorithm
The accelerated method combines Nesterov estimate-sequence updates, a monotone selection step, and greedy exact marginal updates. Let $B(\beta)$ and $\phi(\beta)$ be defined from the entropic dual problem, let $\rho(a,b)=\mathbf{1}_n^\top(b-a)+\sum_j a_j\log(a_j/b_j)$ , and let $E_t=\sum_{k=1}^m\|r_k(B(\beta^t))-r_k\|_1$ . For dense target marginals $r_k$ , the procedure is:
Input: cost tensor $C$ , regularization $\eta$ , target marginals $r_1,\ldots,r_m$ , tolerance $\varepsilon_0$
Initialize $t=0$ , $\theta_0=1$ , $K=1$ , and $\check\beta^0=\widetilde\beta^0=0\in\mathbb{R}^{mn}$
while $E_t>\varepsilon_0$ do
    Set $\overline\beta^t=(1-\theta_t)\check\beta^t+\theta_t\widetilde\beta^t$
    For every $k$ , set $\widetilde\beta_k^{t+1}=\widetilde\beta_k^t-\frac{1}{m\theta_t}\left(\frac{r_k(B(\overline\beta^t))}{\|B(\overline\beta^t)\|_1}-r_k\right)$
    Set $\beta'^t=\overline\beta^t+\theta_t(\widetilde\beta^{t+1}-\widetilde\beta^t)$
    Set $\widehat\beta_k^t=\beta_k'^t$ for $k\ne K$
    Set $\widehat\beta_K^t=\beta_K'^t+\log(r_K)-\log(r_K(B(\beta'^t)))$
    Choose $\beta^t$ as the lower- $\phi$ point among $\check\beta^t$ and $\widehat\beta^t$
    Choose $K=\arg\max_{1\le k\le m}\rho(r_k,r_k(B(\beta^t)))$
    Set $\check\beta_k^{t+1}=\beta_k^t$ for $k\ne K$
    Set $\check\beta_K^{t+1}=\beta_K^t+\log(r_K)-\log(r_K(B(\beta^t)))$
    Set $\theta_{t+1}=\theta_t(\sqrt{\theta_t^2+4}-\theta_t)/2$
    Set $t=t+1$
end while
return $B(\beta^t)$
The first three steps accelerate optimization of the smooth dual objective, the monotone choice preserves the better dual objective value, and the two exact coordinate updates maintain unit tensor mass and provide the residual decrease needed for the complexity proof. A direct iteration costs $O(mn^m)$ arithmetic operations.
Knowl 9 — Accelerated approximation bound for MOT
theoretical result
Using the same marginal smoothing and rounding procedure as the nonaccelerated method, set $\eta=\varepsilon/(2m\log n)$ and $\varepsilon_0=\varepsilon/(8\|C\|_\infty)$ . Run the accelerated multimarginal Sinkhorn algorithm until its marginal residual is at most $\varepsilon_0/2$ , and then round its tensor to the original marginals.

The resulting plan $\widehat X$ is an $\varepsilon$ -approximate multimarginal transportation plan. The accelerated dual iterates satisfy an inverse-square objective-gap estimate of the form
$\phi(\check\beta^t)-\phi(\beta^*)\le \frac{2m^2nR^2}{(t+1)^2},$
where $R$ bounds an optimal dual solution and depends on $\|C\|_\infty$ , $\eta$ , and the smallest smoothed marginal entry. Combining this estimate with the greedy marginal-repair progress gives the arithmetic complexity
$O\left(\frac{m^3 n^{m+1/3}\|C\|_\infty^{4/3}(\log n)^{1/3}}{\varepsilon^{4/3}}\right).$
This improves the dependence on $1/\varepsilon$ from $\varepsilon^{-2}$ to $\varepsilon^{-4/3}$ , but is not near-linear in the $n^m$ tensor dimension because of the additional factor $n^{1/3}$ .
Knowl 10 — Empirical comparison on synthetic and real image barycenters
empirical result
The authors evaluated the two deterministic methods against the commercial LP solver Gurobi while computing free-support Wasserstein barycenters with quadratic Euclidean costs. Experiments used MATLAB R2020a on a six-core Intel Core i5-9400F workstation with 32 GB memory.

For synthetic data, each trial used three normalized random grayscale images containing a randomly positioned foreground square. Background intensities were sampled uniformly from $[0,1]$ , foreground intensities from $[0,50]$ , and the square occupied 10% of the image. The three marginals used equal barycentric weights, and experiments used $n\in\{25,100\}$ pixel locations. Over ten random triples and at most ten iterations, the accelerated method reduced the distance to the transportation polytope faster and required fewer iterations than the ordinary multimarginal Sinkhorn method for $\eta\in\{1,0.2,0.1\}$ . When runtime was measured for $n\in\{25,100,144\}$ , ordinary multimarginal Sinkhorn was fastest, accelerated Sinkhorn was second, and both outperformed Gurobi; the direct accelerated implementation was slower despite fewer iterations because of its heavier gradient computations.

On MNIST, the experiments used three $28\times28$ images, added noise $10^{-6}$ to zero entries, normalized each image, and used $\eta\in\{1,0.05,0.02\}$ , giving $n=576$ . Gurobi could not run because the three-image MOT linear program exceeded available memory. The accelerated method again improved iteration behavior relative to ordinary Sinkhorn. With $\eta=0.05$ , both methods produced visually plausible high-quality free-support barycenters for two triples of MNIST images with different barycentric weight vectors.

Coverage note — Proof derivations, auxiliary total-unimodularity criteria, and routine implementation discussions were omitted; the stated hardness result, convergence certificates, algorithms, complexity bounds, rounding guarantee, experiments, and principal empirical limitations are retained.

References

1.M. Agueh and G. Carlier. Barycenters in the Wasserstein space. SIAM Journal on Mathematical Analysis, 43(2):904–924, 2011.
2.Z. Allen-Zhu, Z. Qu, P. Richtárik, and Y. Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In ICML, pages 1110–1119, 2016.
3.J. Altschuler, J. Weed, and P. Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In NeurIPS, pages 1964–1974, 2017.
4.J. M. Altschuler and E. Boix-Adsera. Hardness results for multimarginal optimal transport problems. Discrete Optimization, 42:100669, 2021a.
5.J. M. Altschuler and E. Boix-Adsera. Wasserstein barycenters can be computed in polynomial time in fixed dimension. Journal of Machine Learning Research, 22:1–19, 2021b.
6.J. M. Altschuler and E. Boix-Adser`a. Wasserstein barycenters are NP-hard to compute. SIAM Journal on Mathematics of Data Science, 4(1):179–203, 2022.
7.E. Anderes, S. Borgwardt, and J. Miller. Discrete Wasserstein barycenters: Optimal transport for discrete data. Mathematical Methods of Operations Research, 84(2):389–409, 2016.
8.J-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré. Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2):A1111–A1138, 2015.
9.J-D. Benamou, G. Carlier, and L. Nenna. Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm. Numerische Mathematik, 142(1):33–54, 2019.
10.C. Berge. The Theory of Graphs. Courier Corporation, 2001.
11.J. Blanchet, A. Jambulapati, C. Kent, and A. Sidford. Towards optimal running times for optimal transport. ArXiv Preprint: 1810.07717, 2018.
12.Y. Brenier. The least action principle and the related concept of generalized flows for incompressible perfect fluids. Journal of the American Mathematical Society, 2(2):225–255, 1989.
13.Y. Brenier. Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 52(4):411–452, 1999.
14.Y. Brenier. Generalized solutions and hydrostatic approximation of the Euler equations. Physica D: Nonlinear Phenomena, 237(14-17):1982–1988, 2008.
15.G. Buttazzo, L. D. Pascale, and P. Gori-Giorgi. Optimal-transport formulation of electronic density-functional theory. Physical Review A, 85(6), 2012.
16.J. Cao, L. Mo, Y. Zhang, K. Jia, C. Shen, and M. Tan. Multi-marginal Wasserstein GAN. In NeurIPS, pages 1776–1786, 2019.
17.G. Carlier and I. Ekeland. Matching for teams. Economic Theory, 42(2):397–418, 2010a.
18.G. Carlier and I. Ekeland. Hedonic price equilibria, stable matching and optimal transport: Equivalence, topology and uniqueness. Economic Theory, 42(2):317–354, 2010b.
19.G. Carlier, A. Oberman, and E. Oudet. Numerical methods for matching for teams and Wasserstein barycenters. ESAIM: Mathematical Modelling and Numerical Analysis, 49(6):1621–1642, 2015.
20.Y. Choi, M. Choi, M. Kim, J-W. Ha, S. Kim, and J. Choo. Stargan: Unified generative adversarial networks for multi-domain image-to-image translation. In CVPR, pages 8789–8797, 2018.
21.S. Claici, E. Chien, and J. Solomon. Stochastic Wasserstein barycenters. In ICML, pages 999–1008. PMLR, 2018.
22.M. B. Cohen, Y. T. Lee, and Z. Song. Solving linear programs in the current matrix multiplication time. In STOC, pages 938–942, 2019.
23.C. Cotar, G. Friesecke, and C. Klüppelberg. Density functional theory and optimal transportation with Coulomb cost. Communications on Pure and Applied Mathematics, 66(4):548–599, 2013.
24.T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 2012.
25.M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurIPS, pages 2292–2300, 2013.
26.M. Cuturi and A. Doucet. Fast computation of Wasserstein barycenters. In ICML, pages 685–693, 2014.
27.M. Cuturi and G. Peyré. Semidual regularized optimal transport. SIAM Review, 60(4):941–965, 2018.
28.S. I. Daitch and D. A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Foundations of Computer Science, pages 451–460. ACM, 2008.
29.I. S. Dhillon, P. K. Ravikumar, and A. Tewari. Nearest neighbor based greedy coordinate descent. In NeurIPS, pages 2160–2168, 2011.
30.J. Diakonikolas and L. Orecchia. Alternating randomized block coordinate descent. In ICML, pages 1224–1232. PMLR, 2018.
31.Y. Dolinsky and M. H. Soner. Robust hedging and martingale optimal transport in continuous time. Probability Theory and Related Fields, 160:391–427, 2014.
32.R. M. Dudley. The speed of mean Glivenko-Cantelli convergence. The Annals of Mathematical Statistics, 40(1):40–50, 1969.
33.P. Dvurechensky, D. Dvinskikh, A. Gasnikov, C. A. Uribe, and A. Nedić. Decentralize and randomize: Faster algorithm for Wasserstein barycenters. In NeurIPS, pages 10760–10770, 2018a.
34.P. Dvurechensky, A. Gasnikov, and A. Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm. In ICML, pages 1367–1376, 2018b.
35.J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248–264, 1972.
36.I. Ekeland. An optimal matching problem. ESAIM: Control, Optimisation and Calculus of Variations, 11(1):57–71, 2005.
37.T. R. Ervolina and S. T. McCormick. Canceling most helpful total cuts for minimum cost network flow. Networks, 23(1):41–52, 1993a.
38.T. R. Ervolina and S. T. McCormick. Two strongly polynomial cut cancelling algorithms for minimum cost network flow. Discrete Applied Mathematics, 46(2):133–165, 1993b.
39.O. Fercoq and P. Richtárik. Accelerated, parallel, and proximal coordinate descent. SIAM Journal on Optimization, 25(4):1997–2023, 2015.
40.R. Flamary and N. Courty. POT: Python optimal transport library, 2017. URL https://pythonot.github.io/.
41.N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707–738, 2015.
42.A. Galichon, P. Henry-Labordere, and N. Touz. A stochastic control approach to non-arbitrage bounds given marginals, with an application to Lookback options. The Annals of Applied Probability, 24:312–336, 2014.
43.Z. Galil and E. Tardos. An o(n2(m+nlogn)logn) min-cost flow algorithm. Journal of the ACM (JACM), 35(2):374–386, 1988.
44.W. Gangbo and A. Swiech. Optimal maps for the multidimensional Monge-Kantorovich problem. Communications on Pure and Applied Mathematics, 51(1):23–45, 1998.
45.M. R. Garey and D. S. Johnson. Computers and Intractability, volume 29. WH Freeman New York, 2002.
46.D. Ge, H. Wang, Z. Xiong, and Y. Ye. Interior-point methods strike back: Solving the Wasserstein barycenter problem. In NeurIPS, pages 6894–6905, 2019.
47.A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyré. Sample complexity of Sinkhorn divergences. In AISTATS, 2019.
48.A. Ghouila-Houri. Caractérisation des matrices totalement unimodulaires. Comptes Redus Hebdomadaires des Séances de l’Académie des Sciences (Paris), 254:1192–1194, 1962.
49.A. V. Goldberg and S. Rao. Beyond the flow decomposition barrier. Journal of the ACM (JACM), 45(5):783–797, 1998.
50.A. V. Goldberg and R. E. Tarjan. Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research, 15(3):430–466, 1990.
51.S. Guminov, P. Dvurechensky, N. Tupitsa, and A. Gasnikov. Accelerated alternating minimization, accelerated Sinkhorn’s algorithm and accelerated iterative Bregman projections. ArXiv Preprint: 1906.03622, 2019.
52.R. Hassin. The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm. Mathematical Programming, 25(2):228–239, 1983.
53.R. Hassin. Algorithms for the minimum cost circulation problem based on maximizing the mean improvement. Operations Research Letters, 12(4):227–233, 1992.
54.Z. He, W. Zuo, M. Kan, S. Shan, and X. Chen. Attgan: Facial attribute editing by only changing what you want. IEEE Transactions on Image Processing, 28(11):5464–5478, 2019.
55.L. Hui, X. Li, J. Chen, H. He, and J. Yang. Unsupervised multi-domain image translation with domain-specific encoders/decoders. In ICPR, pages 2044–2049. IEEE, 2018.
56.A. Jambulapati, A. Sidford, and K. Tian. A direct tilde {O}(1/epsilon) iteration parallel algorithm for optimal transport. In NeurIPS, pages 11355–11366, 2019.
57.L. V. Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), volume 37, pages 199–201, 1942.
58.R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer, 1972.
59.M. Klein. A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science, 14(3):205–220, 1967.
60.A. Kroshnin, N. Tupitsa, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, and C. Uribe. On the complexity of approximating Wasserstein barycenters. In ICML, pages 3530–3540, 2019.
61.T. Lacombe, M. Cuturi, and S. Oudot. Large scale computation of means and clusters for persistence diagrams using optimal transport. In NeurIPS, 2018.
62.N. Lahn, D. Mulchandani, and S. Raghvendra. A graph theoretic additive approximation of optimal transport. In NeurIPS, pages 13836–13846, 2019.
63.K. Le, H. Nguyen, K. Nguyen, T. Pham, and N. Ho. On multimarginal partial optimal transport: Equivalent forms and computational complexity. In AISTATS, 2022.
64.Y. T. Lee and A. Sidford. Path finding methods for linear programming: Solving linear programs in Oe(sqrt(rank)) iterations and faster algorithms for maximum flow. In Foundations of Computer Science, pages 424–433. IEEE, 2014.
65.J. Lei. Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767–798, 2020.
66.Q. Lin, Z. Lu, and L. Xiao. An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization. SIAM Journal on Optimization, 25(4):2244–2273, 2015.
67.T. Lin, N. Ho, and M. Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In ICML, pages 3982–3991, 2019a.
68.T. Lin, N. Ho, and M. I. Jordan. On the efficiency of the Sinkhorn and Greenkhorn algorithms and their acceleration for optimal transport. ArXiv Preprint: 1906.01437, 2019b.
69.T. Lin, N. Ho, X. Chen, M. Cuturi, and M. I. Jordan. Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm. In NeurIPS, pages 5368–5380, 2020.
70.H. Lu, R. Freund, and V. Mirrokni. Accelerating greedy coordinate descent methods. In ICML, pages 3257–3266, 2018.
71.G. Mena and J. Niles-Weed. Statistical bounds for entropic optimal transport: Sample complexity and the central limit theorem. In NeurIPS, pages 4541–4551, 2019.
72.C. B. Mendl and L. Lin. Kantorovich dual solution for strictly correlated electrons in atoms and molecules. Physical Review B, 87:125106, 2013.
73.O. Meshi, A. Globerson, and T. S. Jaakkola. Convergence rate analysis of MAP coordinate minimization algorithms. In NeurIPS, pages 3014–3022, 2012.
74.L. Mi and J. Bento. Multi-marginal optimal transport defines a generalized metric. ArXiv Preprint: 2001.11114, 2020.
75.Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005.
76.Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341–362, 2012.
77.Y. Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
78.J. Nutini, M. Schmidt, I. Laradji, M. Friedlander, and H. Koepke. Coordinate descent converges faster with the Gauss-Southwell rule than random selection. In ICML, pages 1632–1641, 2015.
79.J. B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41(2):338–350, 1993.
80.J. B. Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(2):109–129, 1997.
81.B. Pass. Multi-marginal optimal transport: Theory and applications. ESAIM: Mathematical Modelling and Numerical Analysis, 49(6):1771–1790, 2015.
82.G. Peyré and M. Cuturi. Computational Optimal Transport: With Applications to Data Science. Foundations and Trends(r) in Machine Learning, 2019.
83.K. Pham, K. Le, N. Ho, T. Pham, and H. Bui. On unbalanced optimal transport: An analysis of Sinkhorn algorithm. In ICML, pages 7673–7682. PMLR, 2020.
84.A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24. Springer Science & Business Media, 2003.
85.M. Seidl, P. Gori-Giorgi, and A. Savi. Strictly correlated electrons in density-functional theory: A general formulation with applications to spherical densities. Physical Review A, 75:75:042511, 2007.
86.S. Srivastava, C. Li, and D. Dunson. Scalable Bayes via barycenter in Wasserstein space. Journal of Machine Learning Research, 19(8):1–35, 2018.
87.M. Staib, S. Claici, J. M. Solomon, and S. Jegelka. Parallel streaming Wasserstein barycenters. In NeurIPS, pages 2647–2658, 2017.
88.E. Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247–255, 1985.
89.R. E. Tarjan. Dynamic trees as search trees via euler tours, applied to the network simplex algorithm. Mathematical Programming, 78(2):169–177, 1997.
90.P. Tseng. On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal on Optimization, 2(3), 2008.
91.N. Tupitsa, P. Dvurechensky, A. Gasnikov, and C. A. Uribe. Multimarginal optimal transport by accelerated alternating minimization. In CDC, pages 6132–6137. IEEE, 2020.
92.C. Villani. Topics in Optimal Transportation. American Mathematical Society, Providence, RI, 2003.
93.J. Weed and F. Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli, 25(4A):2620–2648, 2019.
94.S. J. Wright. Primal-Dual Interior-Point Methods, volume 54. SIAM, 1997.
95.Y. Xie, X. Wang, R. Wang, and H. Zha. A fast proximal point method for computing exact Wasserstein distance. In UAI, pages 433–453. PMLR, 2020.

Citation

MLA

Lin, T., et al. “On the Complexity of Approximating Multimarginal Optimal Transport”. Journal of Machine Learning Research, vol. 23, no. 65, 2022, pp. 1–3, https://www.jmlr.org/papers/v23/19-843.html.

APA

Lin, T., Ho, N., Cuturi, M., & Jordan, M. I. (2022). On the Complexity of Approximating Multimarginal Optimal Transport. Journal of Machine Learning Research, 23(65), 1–43. https://www.jmlr.org/papers/v23/19-843.html

Chicago

Lin, T., N. Ho, M. Cuturi, and M. I. Jordan. 2022. “On the Complexity of Approximating Multimarginal Optimal Transport”. Journal of Machine Learning Research 23 (65): 1–43. https://www.jmlr.org/papers/v23/19-843.html.

Harvard

Lin, T. et al. (2022) “On the Complexity of Approximating Multimarginal Optimal Transport”, Journal of Machine Learning Research, 23(65), pp. 1–43. Available at: https://www.jmlr.org/papers/v23/19-843.html.

Vancouver

1. Lin T, Ho N, Cuturi M, Jordan MI (2022) On the Complexity of Approximating Multimarginal Optimal Transport. Journal of Machine Learning Research 23:1–43

BibTeX

@article{JMLR:v23:19-843,
  author  = {Tianyi Lin and Nhat Ho and Marco Cuturi and Michael I. Jordan},
  title   = {On the Complexity of Approximating Multimarginal Optimal Transport},
  journal = {Journal of Machine Learning Research},
  year    = {2022},
  volume  = {23},
  number  = {65},
  pages   = {1--43},
  url     = {http://jmlr.org/papers/v23/19-843.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

On the Complexity of Approximating Multimarginal Optimal Transport

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — Discrete multimarginal optimal transport and approximation target

Knowl 2 — Dual formulation of entropically regularized MOT

Knowl 3 — The standard MOT linear program is not a minimum-cost flow problem for three or more marginals

Knowl 4 — Greedy multimarginal Sinkhorn algorithm

Knowl 5 — Multimarginal rounding scheme with exact marginal repair

Knowl 6 — Convergence certificate for greedy multimarginal Sinkhorn

Knowl 7 — Near-linear-in-variables approximation via multimarginal Sinkhorn

Knowl 8 — Accelerated multimarginal Sinkhorn algorithm

Knowl 9 — Accelerated approximation bound for MOT

Knowl 10 — Empirical comparison on synthetic and real image barycenters

References

Citation

BibTeX

Access the Paper