# A Sinkhorn-type Algorithm for Constrained Optimal Transport

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 73 references that are in the map.
- First posted on arXiv 8 Mar 2024.

## Builds on (most cited first, 30 of 39)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [OT-Flow: Fast and Accurate Continuous Normalizing Flows via Optimal Transport](https://mlsanity.com/paper/2006.00104/) (2020)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Improving GANs Using Optimal Transport](https://mlsanity.com/paper/1803.05573/) (2018)
- [Max-Sliced Wasserstein Distance and its use for GANs](https://mlsanity.com/paper/1904.05877/) (2019)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Theoretical Analysis of Domain Adaptation with Optimal Transport](https://mlsanity.com/paper/1610.04420/) (2016)
- [Graph Optimal Transport for Cross-Domain Alignment](https://mlsanity.com/paper/2006.14744/) (2020)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [From optimal transport to generative modeling: the VEGAN cookbook](https://mlsanity.com/paper/1705.07642/) (2017)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [A Geometric View of Optimal Transportation and Generative Model](https://mlsanity.com/paper/1710.05488/) (2017)
- [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017)
- [Multi-source Domain Adaptation via Weighted Joint Distributions Optimal Transport](https://mlsanity.com/paper/2006.12938/) (2020)
- [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018)
- [GAN and VAE from an Optimal Transport Point of View](https://mlsanity.com/paper/1706.01807/) (2017)
- [Linear Time Sinkhorn Divergences using Positive Features](https://mlsanity.com/paper/2006.07057/) (2020)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)

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

- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [Sinkhorn Algorithm for Sequentially Composed Optimal Transports](https://mlsanity.com/paper/2412.03120/) (2024)
- [Accelerated Algorithm for Sparse Regularized Partial Optimal Transport](https://mlsanity.com/paper/2609.40075/) (2026)

## Abstract (arXiv)

Entropic optimal transport (OT) and the Sinkhorn algorithm have made it practical for machine learning practitioners to perform the fundamental task of calculating transport distance between statistical distributions. In this work, we focus on a general class of OT problems under a combination of equality and inequality constraints. We derive the corresponding entropy regularization formulation and introduce a Sinkhorn-type algorithm for such constrained OT problems supported by theoretical guarantees. We first bound the approximation error when solving the problem through entropic regularization, which reduces exponentially with the increase of the regularization parameter. Furthermore, we prove a sublinear first-order convergence rate of the proposed Sinkhorn-type algorithm in the dual space by characterizing the optimization procedure with a Lyapunov function. To achieve fast and higher-order convergence under weak entropy regularization, we augment the Sinkhorn-type algorithm with dynamic regularization scheduling and second-order acceleration. Overall, this work systematically combines recent theoretical and numerical advances in entropic optimal transport with the constrained case, allowing practitioners to derive approximate transport plans in complex scenarios.