# On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm

arXiv: https://arxiv.org/abs/2002.03293 · HTML: https://mlsanity.com/paper/2002.03293/

## Key facts

- Cited by 61 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 9 Feb 2020.

## Built on by (most cited first, 30 of 61)

- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [TopV: Compatible Token Pruning with Inference Time Optimization for Fast and Low-Memory Multimodal Vision Language Model](https://mlsanity.com/paper/2503.18278/) (2025)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [Generative Modeling through the Semi-dual Formulation of Unbalanced Optimal Transport](https://mlsanity.com/paper/2305.14777/) (2023)
- [Optimal Transport for Treatment Effect Estimation](https://mlsanity.com/paper/2310.18286/) (2023)
- [Get more for less: Principled Data Selection for Warming Up Fine-Tuning in LLMs](https://mlsanity.com/paper/2405.02774/) (2024)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplings](https://mlsanity.com/paper/2209.15621/) (2022)
- [Entropy Partial Transport with Tree Metrics: Theory and Practice](https://mlsanity.com/paper/2101.09756/) (2021)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [Scalable Unbalanced Sobolev Transport for Measures on a Graph](https://mlsanity.com/paper/2302.12498/) (2023)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Light Unbalanced Optimal Transport](https://mlsanity.com/paper/2303.07988/) (2023)
- [Contrastive Learning for Task-Independent SpeechLLM-Pretraining](https://mlsanity.com/paper/2412.15712/) (2024)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [Unbalanced CO-Optimal Transport](https://mlsanity.com/paper/2205.14923/) (2022)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [A High-Quality Robust Diffusion Framework for Corrupted Dataset](https://mlsanity.com/paper/2311.17101/) (2023)
- [Your contrastive learning problem is secretly a distribution alignment problem](https://mlsanity.com/paper/2502.20141/) (2025)
- [COTReg:Coupled Optimal Transport based Point Cloud Registration](https://mlsanity.com/paper/2112.14381/) (2021)
- [Topological Node2vec: Enhanced Graph Embedding via Persistent Homology](https://mlsanity.com/paper/2309.08241/) (2023)
- [Matching for causal effects via multimarginal unbalanced optimal transport](https://mlsanity.com/paper/2112.04398/) (2021)
- [Hierarchical Policy Blending As Optimal Transport](https://mlsanity.com/paper/2212.01938/) (2022)

## Abstract (arXiv)

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 widetildeO(n2/ 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 widetildeO(n2/varepsilon2). 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.