On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
This work provides improved theoretical guarantees for computational efficiency in optimal transport, which is incremental but relevant for researchers and practitioners in machine learning and optimization dealing with unbalanced data.
The paper analyzes the computational complexity of the Sinkhorn algorithm for solving the entropic regularized Unbalanced Optimal Transport (UOT) problem, showing it achieves a near-linear time complexity of order $\widetilde{\mathcal{O}}(n^2/ \varepsilon)$, which is better than the $\widetilde{\mathcal{O}}(n^2/\varepsilon^2)$ complexity for the balanced Optimal Transport problem.
We provide a computational complexity analysis for the Sinkhorn algorithm that solves the entropic regularized Unbalanced Optimal Transport (UOT) problem between two measures of possibly different masses with at most $n$ components. We show that the complexity of the Sinkhorn algorithm for finding an $\varepsilon$-approximate solution to the UOT problem is of order $\widetilde{\mathcal{O}}(n^2/ \varepsilon)$, which is near-linear time. To the best of our knowledge, this complexity is better than the complexity of the Sinkhorn algorithm for solving the Optimal Transport (OT) problem, which is of order $\widetilde{\mathcal{O}}(n^2/\varepsilon^2)$. Our proof technique is based on the geometric convergence of the Sinkhorn updates to the optimal dual solution of the entropic regularized UOT problem and some properties of the primal solution. It is also different from the proof for the complexity of the Sinkhorn algorithm for approximating the OT problem since the UOT solution does not have to meet the marginal constraints.