On the complexity of the optimal transport problem with graph-structured cost
This work addresses computational bottlenecks in MOT for machine learning applications, providing theoretical complexity bounds that are incremental but specific to structured cost scenarios.
The paper tackles the computational complexity of multi-marginal optimal transport (MOT) with graph-structured costs, deriving a bound of $\mathcal{ ilde O}(d(G)m n^2ε^{-2})$ for achieving ε-accuracy when the cost is associated with a tree of diameter d(G), aligning with existing bounds for the Wasserstein barycenter problem.
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{\tilde O}(d(G)m n^2ε^{-2})$ bound for a $ε$-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.