mlsanityData to 7 Oct 2026

On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm

arXiv 2002.03293 ↗First posted 9 Feb 2020cs.CC cs.DS math.OCcited by 61

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 12; 2023: 16; 2024: 8; 2025: 6; 2026: 12.

61 papers.

Sort:

By area:

  1. 2021Unbalanced minibatch Optimal Transport; applications to Domain Adaptationcited by 123
  2. 2025TopV: Compatible Token Pruning with Inference Time Optimization for Fast and Low-Memory Multimodal Vision Language Modelcited by 57
  3. 2021Improving Mini-batch Optimal Transport via Partial Transportationcited by 40
  4. 2023Generative Modeling through the Semi-dual Formulation of Unbalanced Optimal Transportcited by 39
  5. 2023Optimal Transport for Treatment Effect Estimationcited by 32
  6. 2024Get more for less: Principled Data Selection for Warming Up Fine-Tuning in LLMscited by 32
  7. 2021On Robust Optimal Transport: Computational Complexity and Barycenter Computationcited by 27
  8. 2023Scalable Optimal Transport Methods in Machine Learning: A Contemporary Surveycited by 27
  9. 2022Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfecited by 22
  10. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
  11. 2022Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplingscited by 16
  12. 2021Entropy Partial Transport with Tree Metrics: Theory and Practicecited by 13
38 more
  1. 2022Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsificationcited by 11
  2. 2023Scalable Unbalanced Sobolev Transport for Measures on a Graphcited by 10
  3. 2022Hilbert Curve Projection Distance for Distribution Comparisoncited by 9
  4. 2021On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexitycited by 8
  5. 2023Light Unbalanced Optimal Transportcited by 8
  6. 2024Contrastive Learning for Task-Independent SpeechLLM-Pretrainingcited by 8
  7. 2023Improved Rate of First Order Algorithms for Entropic Optimal Transportcited by 7
  8. 2023Unbalanced Low-rank Optimal Transport Solverscited by 7
  9. 2023On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methodscited by 7
  10. 2022Unbalanced CO-Optimal Transportcited by 6
  11. 2023Outlier-Robust Gromov-Wasserstein for Graph Datacited by 6
  12. 2023Importance Sparsification for Sinkhorn Algorithmcited by 6
  13. 2023A High-Quality Robust Diffusion Framework for Corrupted Datasetcited by 6
  14. 2025Your contrastive learning problem is secretly a distribution alignment problemcited by 6
  15. 2021COTReg:Coupled Optimal Transport based Point Cloud Registrationcited by 5
  16. 2023Topological Node2vec: Enhanced Graph Embedding via Persistent Homologycited by 5
  17. 2021Matching for causal effects via multimarginal unbalanced optimal transportcited by 4
  18. 2022Hierarchical Policy Blending As Optimal Transportcited by 4
  19. 2023Group-blind optimal transport to group parity and its constrained variantscited by 4
  20. 2024Dude: Dual Distribution-Aware Context Prompt Learning For Large Vision-Language Modelcited by 4
  21. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  22. 2025MGPATH: Vision-Language Model with Multi-Granular Prompt Learning for Few-Shot WSI Classificationcited by 3
  23. 2022Regularized Optimal Transport Layers for Generalized Global Pooling Operationscited by 2
  24. 2026Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methodscited by 2
  25. 2022On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gapscited by 1
  26. 2023Optimal Transport for Change Detection on LiDAR Point Cloudscited by 1
  27. 2024Collective Counterfactual Explanations: Balancing Individual Goals and Collective Dynamicscited by 1
  28. 2024GeOT: A spatially explicit framework for evaluating spatio-temporal predictionscited by 1
  29. 2025Experts-Guided Unbalanced Optimal Transport for ISP Learning from Unpaired and/or Paired Datacited by 1
  30. 2026Distributional Open-Ended Evaluation of LLM Cultural Value Alignment Based on Value Codebookcited by 1
  31. 2026Globally Solving Unbalanced Optimal Transport and Density Control for Gaussian Distributionscited by 1
  32. 2026Small Cues, Big Consequences: Learning Pivotal Cues for Multimodal Meme Classificationcited by 1
  33. 2022Revisiting Global Pooling through the Lens of Optimal Transportcited by 0
  34. 2022On making optimal transport robust to all outlierscited by 0
  35. 2022Convolutional Persistence Transformscited by 0
  36. 2023Safe Screening for Unbalanced Optimal Transportcited by 0
  37. 2023Optimal Transport with Cyclic Symmetrycited by 0
  38. 2024An inexact Bregman proximal point method and its acceleration version for unbalanced optimal transportcited by 0

50 most cited of 61 All 61 (JSON)