Abstract
Unbalanced Optimal Transport (UOT) provides a robust framework for comparing probability distributions where total mass is not conserved, a common scenario in biological modeling and data science. However, standard solvers like the Sinkhorn algorithm often exhibit significantly slower convergence for UOT compared to balanced Optimal Transport (OT). This paper identifies a fundamental symmetry flaw—the lack of translation invariance in dual potentials—as the primary bottleneck. We introduce a "Translation Invariant Sinkhorn" algorithm and a specialized 1-D Frank-Wolfe solver that achieve state-of-the-art performance, reducing the complexity of 1-D UOT problems to linear time ($O(N)$).
Introduction
Optimal Transport (OT) has become a cornerstone in machine learning for measuring distances between distributions. While standard OT requires strict mass conservation, Unbalanced Optimal Transport (UOT) relaxes this constraint, allowing for mass creation or destruction. This flexibility is critical for applications such as single-cell RNA sequencing (e.g., the Waddington-OT dataset), where cell populations grow and differentiate, or in robust statistics where outliers can skew total mass.
Despite its utility, UOT faces a significant "speed problem." The Sinkhorn algorithm, which is highly efficient for standard OT, converges much more slowly when applied to UOT. This paper pinpoints the cause: in standard OT, dual potentials are unique only up to a constant shift, whereas in UOT, this shift is fixed. The standard algorithm spends excessive iterations "drifting" toward a specific global normalization, leading to poor contraction rates.
The Drift Bottleneck and Translation Invariance
The authors demonstrate that the slow convergence of UOT Sinkhorn is an artifact of how the algorithm handles global potential levels. By reformulating the UOT dual problem to explicitly handle a translation parameter, they "factor out" the global shift. This leads to the proposed $\mathcal{G}_\epsilon$ and $\mathcal{H}_\epsilon$-Sinkhorn algorithms. These variants maintain high contraction rates even in regimes where standard Sinkhorn (denoted as $\mathcal{F}_\epsilon$) slows down significantly, particularly as the marginal parameter $\rho$ increases or the regularization $\epsilon$ decreases.
Fast 1-D Solvers and Linear Complexity
For one-dimensional measures, the paper introduces a Frank-Wolfe (conditional gradient) solver applied to the translation-invariant formulation. The key insight is that for 1-D measures, the Linear Minimization Oracle (LMO) required by Frank-Wolfe reduces to a balanced 1-D OT problem. Because 1-D balanced OT can be solved via simple sorting in $O(N \log N)$ or even $O(N)$ time, the entire UOT solver achieves linear time complexity per iteration. This is a major improvement over the $O(N^2)$ cost associated with standard Sinkhorn iterations on discrete measures.
This efficiency extends to computing UOT barycenters—the "average" of multiple distributions. Standard OT barycenters often produce "ghost" modes when mass is mismatched; the UOT approach naturally suppresses these artifacts, providing cleaner and more robust representative distributions.
Experimental Results
The proposed methods were evaluated on synthetic 1-D Gaussian mixtures and the real-world Waddington-OT (WOT) dataset. The results confirm that the $\mathcal{H}_\epsilon$-Sinkhorn algorithm provides a dramatic improvement in contraction rates across different entropy functions, including KL and Berg entropy.
Empirically, the Frank-Wolfe solver reached high-precision solutions for problems with 5,000 samples in a fraction of the time required by standard Sinkhorn. The linear scaling property allows the method to handle large-scale 1-D datasets that were previously computationally prohibitive.
Conclusion
By identifying and fixing the translation invariance issue in UOT dual potentials, this work bridges the performance gap between balanced and unbalanced optimal transport. The resulting algorithms—Translation Invariant Sinkhorn and the 1-D Frank-Wolfe solver—offer a powerful toolkit for robust distribution comparison. Future work includes extending these fast 1-D solvers to higher dimensions via "Sliced UOT" projections, potentially bringing linear-time UOT to a wider range of machine learning applications.
Summary updated