On Robust Optimal Transport: Computational Complexity and Barycenter Computation

Abstract

We consider robust variants of the standard optimal transport, named robust optimal transport, where marginal constraints are relaxed via Kullback-Leibler divergence. We show that Sinkhorn-based algorithms can approximate the optimal cost of robust optimal transport in $\tilde{\mathcal{O}}(\frac{n^2}{\epsilon })$ time, in which $n$ is the number of supports of the probability distributions and $\epsilon$ is the desired error. Furthermore, we investigate a fixed-support robust barycenter problem between $m$ discrete probability distributions with at most $n$ number of supports and develop an approximating algorithm based on iterative Bregman projections (IBP). For the specific case $m=2$, we show that this algorithm can approximate the optimal barycenter value in $\tilde{\mathcal{O}}(\frac{m{n}^2}{\epsilon })$ time, thus being better than the previous complexity $\tilde{\mathcal{O}}(\frac{m{n}^2}{{\epsilon }^2})$ of the IBP algorithm for approximating the Wasserstein barycenter.

arXiv commentAdvances in NeurIPS, 2021; 52 pages, 10 figures; Khang Le and Huy Nguyen contributed equally to this week

References in corpus (8)

• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Multilevel Clustering via Wasserstein Means
• Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation
• The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
• On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
• Graph Optimal Transport for Cross-Domain Alignment
• A Graph Theoretic Additive Approximation of Optimal Transport