Abstract: Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. With $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal{ ilde O}(d(G)m n^2\epsilon^{-2})$ bound for a $\epsilon$-accuracy when the problem is associated with a tree with diameter $d(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.
Introduction
Optimal Transport (OT) is the mathematical science of moving "mass" from one distribution to another as efficiently as possible. While standard OT handles two distributions, Multi-marginal Optimal Transport (MOT) handles $m$ distributions. This is essential for calculating things like "barycenters" (the average of multiple shapes or datasets) or tracking objects over time.
The primary challenge in MOT is the "exponential curse": the computational cost of standard MOT scales as $O(n^m)$, where $n$ is the number of points and $m$ is the number of distributions. For instance, with 10 distributions each containing 100 points, the operations required ($100^{10}$) exceed the number of atoms in the universe. This work addresses this bottleneck by exploiting the underlying graph structure of the cost function to provide tighter, explicit complexity bounds.
Methodology: Sinkhorn Belief Propagation
The authors focus on the Sinkhorn Belief Propagation algorithm, which leverages the structure of the cost function to bypass exponential complexity. The approach is built on four pillars:
- Graph-Structured Costs: The cost function is decomposed into pairwise interactions forming a graph. A common example is the "star" graph used in barycenter problems, where each distribution interacts solely with a central "average" distribution.
- Message Passing: Instead of computing a massive $m$-dimensional tensor, the algorithm uses belief propagation. This allows updates to be performed via simple matrix-vector multiplications.
- Randomized Updates: Unlike traditional cyclic Sinkhorn updates, the authors analyze a random update rule. This choice facilitates the use of probabilistic tools to bound the iterations required for a desired accuracy ($\epsilon$).
- Junction Trees: For graphs with cycles, junction tree decomposition clusters nodes into tree-like structures, maintaining efficiency even in non-simple topologies.
Key Insights and Theoretical Contributions
The core finding is that MOT complexity does not inherently depend on $m$ in the exponent. Instead, it depends on the tree-width of the graph. For tree-like structures, the problem becomes computationally manageable.
The authors improved the complexity bound for tree-structured MOT from $O(m^4n^2\epsilon^{-2})$ to $\tilde{O}(\bar{d}(G)mn^2\epsilon^{-2})$. This linear scaling with $m$ is a significant advancement. Furthermore, they introduce the concept of "balanced" MOT problems, where cost magnitudes on edges are comparable, leading to even more favorable complexity. Their general framework also unifies existing knowledge, simplifying to match best-known bounds for specific cases like the Wasserstein barycenter.
Empirical Results
Theoretical bounds were validated using synthetic experiments across three scenarios: Wasserstein Barycenters (star graph), Hidden Markov Models (chain graph), and Wasserstein Least Squares (tree-width two).
Experimental results confirm that for tree-structured costs, computation time grows linearly with the number of marginals. In head-to-head tests against brute-force Sinkhorn, the belief propagation approach was orders of magnitude faster. For example, in HMM experiments, as $m$ increased from 4 to 12, the brute-force method's runtime exploded and eventually became infeasible, while the proposed method's runtime scaled gracefully.
Conclusion and Future Work
This work effectively "breaks the curse" of dimensionality for graph-structured MOT, providing a polynomial scaling of $n^{w(G)+1}$ where $w(G)$ is the tree-width. For trees ($w(G)=1$), this results in $n^2$ scaling, identical to standard two-marginal OT.
Future research directions include analyzing the cyclic update rule, which is common in practice but mathematically more complex to bound than the randomized rule. Additionally, incorporating Nesterov-style acceleration could potentially improve the accuracy dependence from $\epsilon^{-2}$ to $\epsilon^{-1}$, further enhancing the algorithm's utility for high-precision applications.
Summary updated