# Rethinking Initialization of the Sinkhorn Algorithm

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 63 references that are in the map.
- First posted on arXiv 15 Jun 2022.

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

- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Semi-Supervised Learning with Deep Generative Models](https://mlsanity.com/paper/1406.5298/) (2014)
- [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)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Improving GANs Using Optimal Transport](https://mlsanity.com/paper/1803.05573/) (2018)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [A Wasserstein-type distance in the space of Gaussian Mixture Models](https://mlsanity.com/paper/1907.05254/) (2019)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Differentiable Particle Filtering via Entropy-Regularized Optimal Transport](https://mlsanity.com/paper/2102.07850/) (2021)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Optimal transport for Gaussian mixture models](https://mlsanity.com/paper/1710.07876/) (2017)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Wasserstein Dictionary Learning: Optimal Transport-based unsupervised non-linear dictionary learning](https://mlsanity.com/paper/1708.01955/) (2017)
- [A Smoothed Dual Approach for Variational Wasserstein Problems](https://mlsanity.com/paper/1503.02533/) (2015)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1711.01851/) (2017)
- [Linear Time Sinkhorn Divergences using Positive Features](https://mlsanity.com/paper/2006.07057/) (2020)
- [Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure](https://mlsanity.com/paper/2108.08129/) (2021)
- [Multi-subject MEG/EEG source imaging with sparse multi-task regression](https://mlsanity.com/paper/1910.01914/) (2019)
- [A note on overrelaxation in the Sinkhorn algorithm](https://mlsanity.com/paper/2012.12562/) (2020)

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Progressive Entropic Optimal Transport Solvers](https://mlsanity.com/paper/2406.05061/) (2024)
- [The derivatives of Sinkhorn-Knopp converge](https://mlsanity.com/paper/2207.12717/) (2022)
- [Wasserstein Gradient Flows for Optimizing Gaussian Mixture Policies](https://mlsanity.com/paper/2305.10411/) (2023)
- [Universal Neural Optimal Transport](https://mlsanity.com/paper/2212.00133/) (2022)
- [Quantum Doubly Stochastic Transformers](https://mlsanity.com/paper/2504.16275/) (2025)
- [DDEQs: Distributional Deep Equilibrium Models through Wasserstein Gradient Flows](https://mlsanity.com/paper/2503.01140/) (2025)
- [Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs](https://mlsanity.com/paper/2305.18483/) (2023)
- [Sinkhorn doubly stochastic attention rank decay analysis](https://mlsanity.com/paper/2604.07925/) (2026)
- [Sliced-Regularized Optimal Transport](https://mlsanity.com/paper/2604.23944/) (2026)
- [Enhancing Hypergradients Estimation: A Study of Preconditioning and Reparameterization](https://mlsanity.com/paper/2402.16748/) (2024)
- [Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes](https://mlsanity.com/paper/2506.14780/) (2025)
- [ASAP: Amortized Doubly-Stochastic Attention via Sliced Dual Projection](https://mlsanity.com/paper/2605.12879/) (2026)
- [DrainSinkhorn: Safe Elimination for Batched Entropic Optimal Transport](https://mlsanity.com/paper/2607.24741/) (2026)

## Abstract (arXiv)

While the optimal transport (OT) problem was originally formulated as a linear program, the addition of entropic regularization has proven beneficial both computationally and statistically, for many applications. The Sinkhorn fixed-point algorithm is the most popular approach to solve this regularized problem, and, as a result, multiple attempts have been made to reduce its runtime using, e.g., annealing in the regularization parameter, momentum or acceleration. The premise of this work is that initialization of the Sinkhorn algorithm has received comparatively little attention, possibly due to two preconceptions: since the regularized OT problem is convex, it may not be worth crafting a good initialization, since any is guaranteed to work; secondly, because the outputs of the Sinkhorn algorithm are often unrolled in end-to-end pipelines, a data-dependent initialization would bias Jacobian computations. We challenge this conventional wisdom, and show that data-dependent initializers result in dramatic speed-ups, with no effect on differentiability as long as implicit differentiation is used. Our initializations rely on closed-forms for exact or approximate OT solutions that are known in the 1D, Gaussian or GMM settings. They can be used with minimal tuning, and result in consistent speed-ups for a wide variety of OT problems.