Abstract
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.
Introduction
Optimal Transport (OT) has become a cornerstone of modern machine learning, powering everything from generative modeling to domain adaptation. However, standard OT comes with a rigid constraint: the total "mass" of the two distributions being compared must be identical. In real-world scenarios—such as comparing single-cell RNA sequences or images with different intensities—this requirement is rarely met.
Unbalanced Optimal Transport (UOT) addresses this by relaxing hard marginal constraints, replacing them with soft penalties (typically Kullback-Leibler divergence). While the Sinkhorn algorithm has been widely adopted to solve UOT due to its scalability and GPU-friendliness, its precise computational complexity remained uncharacterized. This paper, presented at ICML 2020, provides the first rigorous analysis, revealing that UOT is not only more flexible but also computationally more efficient than standard OT.
Theoretical Framework
The authors analyze the Entropic Regularized UOT problem. By adding an entropy term, the objective function becomes strongly convex, enabling the use of the Sinkhorn algorithm—an iterative scaling approach.
The core contribution is a novel proof technique for convergence:
- Dual Geometric Convergence: The authors demonstrate that the dual variables in the UOT formulation converge at a geometric (linear) rate in the $\ell_\infty$ norm.
- Primal-Dual Mapping: They establish a rigorous relationship between the convergence of these dual variables and the accuracy of the resulting primal transportation plan.
- Algorithmic Freedom: Unlike standard OT, where the algorithm is constrained by exact marginal matching, the UOT formulation allows more "freedom" in its updates. This flexibility leads to a significantly improved dependency on the accuracy parameter $\epsilon$.
Complexity Comparison
The headline result is a complexity of $\tilde{O}(n^2/\epsilon)$ for UOT. This is a substantial improvement over the best-known complexity for standard OT, which is $\tilde{O}(n^2/\epsilon^2)$. Furthermore, this bound outperforms more complex "accelerated" OT algorithms (like Randkhorn) by a factor of $n^{1/3}$.
Key Results and Empirical Validation
The theoretical bounds were validated using both synthetic data (random cost matrices of size $n=100$) and real-world data (MNIST images treated as measures).
As shown in the empirical results, the data strongly supports the theoretical analysis:
- Linear Scaling: The number of iterations $k$ scales linearly with $1/\epsilon$, confirming the $\tilde{O}(1/\epsilon)$ dependency.
- Tightness of Bounds: The ratio of the theoretical bound to the actual iterations remains stable (between 8x and 18x), suggesting that the derived bound is a tight representation of the algorithm's actual performance rather than a loose upper limit.
Conclusion and Future Directions
This work establishes that by relaxing marginal constraints, the Optimal Transport problem becomes fundamentally "easier" to solve. The $\tilde{O}(n^2/\epsilon)$ complexity makes UOT a highly attractive choice for large-scale applications.
Future research directions include refining logarithmic factors of $n$ and $1/\epsilon$, extending these results to multi-marginal cases for barycenters, and investigating dimension-reduction schemes to mitigate the "curse of dimensionality" in high-dimensional spaces.
Reference: Pham, K., Le, K., Ho, N., Pham, T., & Bui, H. (2020). On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm. Proceedings of the 37th International Conference on Machine Learning (ICML).
Summary updated