On Robust Optimal Transport: Computational Complexity and Barycenter Computation
This work addresses computational efficiency challenges in optimal transport for machine learning and data science, offering incremental improvements in algorithm complexity for robust variants.
The paper tackles robust optimal transport by relaxing marginal constraints with Kullback-Leibler divergence, showing that Sinkhorn-based algorithms approximate the optimal cost in O~(n^2/ε) time, and for the robust barycenter problem with m=2, an iterative Bregman projections algorithm achieves O~(mn^2/ε) time, improving over previous O~(mn^2/ε^2) complexity.
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 $\widetilde{\mathcal{O}}(\frac{n^2}{\varepsilon})$ time, in which $n$ is the number of supports of the probability distributions and $\varepsilon$ 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 $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon})$ time, thus being better than the previous complexity $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon^2})$ of the IBP algorithm for approximating the Wasserstein barycenter.