Scaling Multimarginal Optimal Transport

39 concepts37 papers

Standard Optimal Transport (OT) answers a clean geometric question: what is the most efficient way to transform one probability distribution into another? When we discretize two distributions into $n$ distinct bins, the solution is a coupling matrix of size $n \times n$. This matrix tracks how mass moves from every source bin to every destination bin, and it can be computed efficiently using linear programming or iterative scaling methods.

But many real-world problems require aligning multiple distributions simultaneously. For example, we might want to track a population of cells moving through $m$ discrete time steps, or find a single consensus "average" shape (a barycenter) among $m$ different objects. This generalization is known as Multimarginal Optimal Transport (MOT).

As soon as we move from two distributions to $m$ distributions, the mathematical landscape changes dramatically. Instead of a 2D coupling matrix, the joint transport plan becomes an $m$-dimensional tensor containing $n^m$ entries. This exponential growth is the core computational bottleneck of MOT. For even a handful of distributions, storing or optimizing over this tensor directly becomes completely impossible.

Why Standard Optimization Fails

In standard bi-marginal OT, the optimization problem can be framed as a minimum-cost flow on a graph, which allows for highly efficient combinatorial algorithms. However, Michael I. Jordan et al. demonstrated that MOT loses this minimum-cost flow structure as soon as $m > 2$, meaning classical network flow shortcuts no longer apply.

Worse yet, the problem is fundamentally hard. Saverio Salzo et al. note that finding exact solutions for MOT is NP-hard in general settings. Even when we introduce structural assumptions that seem simplifying—such as assuming one of the target distributions has entirely independent marginals—Bahar Taskesen et al. proved that the problem remains #P-hard. The hardness stems from the combinatorial explosion of the joint distribution's potential size, creating a severe bottleneck when scaling to large-scale experiments or many treatment margins, as highlighted by Khang Le and Zijun Gao et al..

To bypass this $n^m$ tensor explosion, researchers have developed three primary strategies: exploiting cost structures, smoothing the optimization landscape, and utilizing continuous generative approximations.

Exploiting Cost Structure

We rarely need to compute arbitrary couplings between distributions; in practice, the cost function often reflects an underlying geometric or relational network. If the cost of transporting mass across multiple margins decomposes along a graph (such as a tree or a temporal chain), we can avoid computing the full joint tensor.

Jiaojiao Fan et al. demonstrated that graph-structured costs allow the transport plan to be factored into smaller, localized components. Building on this insight, Rahul Singh et al. introduced Sinkhorn Belief Propagation. By mapping the multi-marginal problem onto a probabilistic graphical model, they showed that global convergence can be achieved on tree graphs with a computational complexity that scales with the structure of the graph rather than exponentially with the number of nodes.

Similarly, if the cost function satisfies specific one-dimensional "Monge costs," Ronak Mehta et al. showed that a greedy solver can reduce the complexity to scale linearly with both the number of distributions and bins, though extending this efficiency to inherently high-dimensional spaces remains an active area of research.

Entropic Regularization and Alternating Minimization

When the cost function does not possess a convenient graph structure, we can instead smooth the optimization landscape. By adding an entropic regularization term to the objective, the sharp, linear programming problem transforms into a strictly convex Kullback-Leibler (KL) projection problem.

As shown by Jean-David Benamou et al., this regularized formulation allows researchers to solve complex transport problems using simple, iterative closed-form updates. Instead of optimizing the entire tensor at once, algorithms can alternate between scaling each marginal constraint sequentially. To accelerate these iterations, Nazarii Tupitsa et al. and Sergey Guminov et al. developed primal-dual frameworks that combine block-wise minimization with Nesterov's momentum. This approach provides provable deterministic complexity bounds that scale significantly better than standard multi-marginal Sinkhorn algorithms, making tasks like computing high-dimensional Wasserstein barycenters numerically viable.

Continuous and Generative Approximations

For high-dimensional continuous datasets—such as single-cell RNA sequences collected over time or multi-domain image translation—discrete grids and tensors fail entirely. Instead of parameterizing the coupling matrix explicitly, modern approaches parameterize the underlying transport maps or flow fields using deep neural networks.

For instance, Yujia Xie et al. proposed a generative learning framework (SPOT) that treats the transport plan as a push-forward of a latent distribution, solving it via minimax optimization to bypass grid-based bottlenecks. In a similar vein, Jiezhang Cao et al. developed the Multi-marginal Wasserstein GAN (MWGAN) to jointly optimize distances across multiple target domains simultaneously, capturing complex cross-domain correlations that pairwise models fail to resolve.

When modeling continuous trajectories over time, the problem can be framed as a Schrödinger Bridge (SB). George Rapakoulias et al. demonstrated that modeling distributions as Gaussian Mixture Models allows for training-free, highly accelerated solutions to multi-marginal SB problems. To capture long-range temporal dependencies without relying on expensive stochastic differential equation simulations during training, Panagiotis Theodoropoulos et al. lifted the system dynamics into phase space, deriving closed-form multi-marginal bridges that enable fast, simulation-free trajectory inference from sparse data snapshots.

Key Foundational Work

Iterative Bregman Projections for Regularized Transportation Problems (2015) — contributed 1 concept elements to this direction.
A convex representation for the vectorial Mumford-Shah functional (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_in_optimal_trans_d6673acb,
  title = {curse of dimensionality in optimal transport (high-dimensional coupling complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-in-optimal-transport-high-dimensional-coupling/rdr_d6673acb66de442a88f50c0d7fa47ac5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_curse_of_dimensionality_in_optimal_trans_d6673acb_v1,
  title = {curse of dimensionality in optimal transport (high-dimensional coupling complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-in-optimal-transport-high-dimensional-coupling/rdr_d6673acb66de442a88f50c0d7fa47ac5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake