On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm

Khiem Pham, Khang Le, Nhat Ho, Tung Pham, Hung Bui

Optimal Transport (OT) is a powerful mathematical framework for comparing probability distributions. However, it comes with a major restriction: the two distributions must have the exact same total mass. In many real-world scenarios—such as comparing cell populations in biology or tracking objects in video—mass can be created or destroyed.

Unbalanced Optimal Transport (UOT) solves this by relaxing the strict marginal constraints of standard OT. Instead of forcing the transport plan to match the marginals exactly, UOT penalizes deviations using divergences (typically Kullback-Leibler). While the Sinkhorn algorithm is the industry standard for solving entropic-regularized OT, its theoretical performance on the unbalanced version was previously poorly understood. Researchers did not know if the added flexibility of UOT made the problem computationally harder or easier to solve.

This paper provides the first rigorous computational complexity analysis of the Sinkhorn algorithm for UOT, revealing that solving UOT is surprisingly more efficient than standard OT.

The "Freedom" Advantage and Complexity Leap

The most striking insight from the paper is that UOT is computationally "easier" than standard OT. Because the algorithm does not have to fight to satisfy hard marginal constraints, the Sinkhorn updates converge much faster.

The authors prove that the complexity of finding an $\epsilon$-approximate solution for UOT is $\tilde{O}(n^2/\epsilon)$. This is a massive improvement over the best-known $\tilde{O}(n^2/\epsilon^2)$ bounds for standard Sinkhorn-based OT. In the world of optimization, moving from $1/\epsilon^2$ to $1/\epsilon$ is a significant leap, especially when high precision (small $\epsilon$) is required. It even outperforms more complex "accelerated" OT algorithms like Gankhorn and Randkhorn by a factor of $n^{1/3}$.

Methodology: Analyzing the Dual Form

The authors analyze the Sinkhorn algorithm applied to the entropic regularized UOT problem by focusing on the dual form of the UOT objective. Key technical components of their proof include:

  • Geometric Convergence: Proving that the dual variables in the Sinkhorn updates converge at a geometric (linear) rate toward the optimal dual solution.
  • Dual-to-Primal Mapping: Establishing how this dual convergence translates into an $\epsilon$-approximate solution for the primal UOT problem.
  • Scaling Properties: Exploiting the "freedom" of UOT Sinkhorn updates to derive new equations relating the optimal primal value to the masses of the input measures.

Empirical Validation and Bound Tightness

The theoretical bounds were validated using both synthetic data (controlled environments with unequal masses) and real-world MNIST data (using pairs of flattened images). On both datasets, the number of iterations required by the algorithm followed the predicted geometric decay.

Theoretical vs. empirical iterations for UOT Sinkhorn

Crucially, the empirical analysis demonstrates the tightness of the theoretical bound. As shown in the experiments, the ratio between the theoretical stopping rule ($k_f$) and the actual minimum iterations needed ($k_c$) stays relatively small. Furthermore, this ratio actually decreases as the desired accuracy $\epsilon$ gets smaller (i.e., as $\log(1/\epsilon)$ increases). This suggests their theoretical analysis is not just a loose upper bound but closely tracks reality.

Limitations and Future Directions

While this complexity analysis is a breakthrough, the authors note a few areas for future refinement:

  • Logarithmic Slack: Some inequalities in the proof might not be perfectly tight to keep the presentation simple, resulting in extra logarithmic terms ($\log n$ and $\log 1/\epsilon$) that might be removable with a more surgical analysis.
  • High-Dimensional Curse: Like standard OT, the Sinkhorn algorithm for UOT still suffers from the curse of dimensionality when the supports of the measures lie in very high-dimensional spaces.

Future work will likely extend this analysis to multi-marginal UOT and UOT barycenters, which are increasingly popular in data science but currently lack firm complexity guarantees. Developing efficient dimension-reduction schemes specifically tailored for the unbalanced case also remains a promising frontier.

Summary updated

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 ...
BibTeX
@inproceedings{pham2020unbalanced,
  author = {Khiem Pham and Khang Le and Nhat Ho and Tung Pham and Hung Bui},
  title = {{On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=yrvnBrMoDHH},
}
Figure