# Sinkhorn Algorithm for Sequentially Composed Optimal Transports

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 4 Dec 2024.

## Builds on (most cited first, 17 of 17)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improving and generalizing flow-based generative models with minibatch optimal transport](https://mlsanity.com/paper/2302.00482/) (2023)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018)
- [Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm](https://mlsanity.com/paper/1710.08234/) (2017)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach](https://mlsanity.com/paper/2304.06549/) (2023)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [Error estimate for regularized optimal transport problems via Bregman divergence](https://mlsanity.com/paper/2309.11666/) (2023)
- [An ordinary differential equation for entropic optimal transport and its linearly constrained variants](https://mlsanity.com/paper/2403.20238/) (2024)
- [String Diagram of Optimal Transports](https://mlsanity.com/paper/2408.08550/) (2024)

## Built on by (most cited first, 1 of 1)

- [Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling](https://mlsanity.com/paper/2609.32824/) (2026)

## Abstract (arXiv)

Sinkhorn algorithm is the de-facto standard approximation algorithm for optimal transport, which has been applied to a variety of applications, including image processing and natural language processing. In theory, the proof of its convergence follows from the convergence of the Sinkhorn--Knopp algorithm for the matrix scaling problem, and Altschuler et al. show that its worst-case time complexity is in near-linear time. Very recently, sequentially composed optimal transports were proposed by Watanabe and Isobe as a hierarchical extension of optimal transports. In this paper, we present an efficient approximation algorithm, namely Sinkhorn algorithm for sequentially composed optimal transports, for its entropic regularization. Furthermore, we present a theoretical analysis of the Sinkhorn algorithm, namely (i) its exponential convergence to the optimal solution with respect to the Hilbert pseudometric, and (ii) a worst-case complexity analysis for the case of one sequential composition.