# Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2019.

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

- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (2021)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm](https://mlsanity.com/paper/2311.16706/) (2023)
- [Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective](https://mlsanity.com/paper/2507.12246/) (2025)

## Abstract (arXiv)

We present a new perspective on the celebrated Sinkhorn algorithm by showing that is a special case of incremental/stochastic mirror descent. In order to see this, one should simply plug Kullback-Leibler divergence in both mirror map and the objective function. Since the problem has unbounded domain, the objective function is neither smooth nor it has bounded gradients. However, one can still approach the problem using the notion of relative smoothness, obtaining that the stochastic objective is 1-relative smooth. The discovered equivalence allows us to propose 1) new methods for optimal transport, 2) an extension of Sinkhorn algorithm beyond two constraints.