# Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 69 references that are in the map.
- First posted on arXiv 18 Nov 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Wasserstein Auto-Encoders](https://mlsanity.com/paper/1711.01558/) (2017)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Soft-DTW: a Differentiable Loss Function for Time-Series](https://mlsanity.com/paper/1703.01541/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Differentiable Patch Selection for Image Recognition](https://mlsanity.com/paper/2104.03059/) (2021)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection](https://mlsanity.com/paper/2103.17202/) (2021)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections](https://mlsanity.com/paper/2106.15427/) (2021)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [A gradient descent perspective on Sinkhorn](https://mlsanity.com/paper/2002.03758/) (2020)
- [Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters](https://mlsanity.com/paper/1806.03915/) (2018)
- [On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1806.04781/) (2018)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)

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

- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [A Truncated Newton Method for Optimal Transport](https://mlsanity.com/paper/2504.02067/) (2025)
- [Optimal Transport with Tempered Exponential Measures](https://mlsanity.com/paper/2309.04015/) (2023)
- [Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm](https://mlsanity.com/paper/2311.16706/) (2023)
- [Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning](https://mlsanity.com/paper/2610.04264/) (2026)

## Abstract (arXiv)

Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a single-loop optimization algorithm for minimizing general convex objectives on these domains, utilizing the principles of Sinkhorn matrix scaling and mirror descent. The proposed algorithm is robust to noise, and can be used in an online setting. We provide theoretical guarantees for convex objectives and experimental results showcasing it effectiveness on both synthetic and real-world data.