Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

multimarginal optimal transport

Multimarginal optimal transport is an extension of classical optimal transport that seeks the most cost-effective coupling among three or more probability distributions. While standard optimal transport finds a plan to transfer mass between two distributions to minimize a pairwise cost, the multimarginal formulation determines a joint probability distribution over multiple spaces that minimizes the expectation of a multi-variable cost function while ensuring that its projected marginals match the prescribed distributions. This framework arises in various fields including quantum chemistry, economics, statistics, and machine learning, particularly for computing Wasserstein barycenters and modeling multi-agent matching problems. Because the size of the joint distribution tensor grows exponentially with the number of marginals, practical solutions often rely on structured costs or regularized numerical techniques, such as generalized Sinkhorn algorithms, to mitigate computational complexity.

1 item

On the Complexity of Approximating Multimarginal Optimal Transport

On the Complexity of Approximating Multimarginal Optimal Transport

Tianyi Lin, Nhat Ho, Marco Cuturi, Michael I. Jordan

OrganizationsENSAE ParisGoogleUniversity of CaliforniaUniversity of Texas at Austin

Why you should read this

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.

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.

Added

2026-09-26