# Compressed online Sinkhorn

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 8 Oct 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [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)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [Vocabulary Learning via Optimal Transport for Neural Machine Translation](https://mlsanity.com/paper/2012.15671/) (2020)
- [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombination](https://mlsanity.com/paper/2206.04734/) (2022)
- [A Randomized Algorithm to Reduce the Support of Discrete Measures](https://mlsanity.com/paper/2006.01757/) (2020)

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

- [Streaming Sliced Optimal Transport](https://mlsanity.com/paper/2505.06835/) (2025)

## Abstract (arXiv)

The use of optimal transport (OT) distances, and in particular entropic-regularised OT distances, is an increasingly popular evaluation metric in many areas of machine learning and data science. Their use has largely been driven by the availability of efficient algorithms such as the Sinkhorn algorithm. One of the drawbacks of the Sinkhorn algorithm for large-scale data processing is that it is a two-phase method, where one first draws a large stream of data from the probability distributions, before applying the Sinkhorn algorithm to the discrete probability measures. More recently, there have been several works developing stochastic versions of Sinkhorn that directly handle continuous streams of data. In this work, we revisit the recently introduced online Sinkhorn algorithm of [Mensch and Peyr'e, 2020]. Our contributions are twofold: We improve the convergence analysis for the online Sinkhorn algorithm, the new rate that we obtain is faster than the previous rate under certain parameter choices. We also present numerical results to verify the sharpness of our result. Secondly, we propose the compressed online Sinkhorn algorithm which combines measure compression techniques with the online Sinkhorn algorithm. We provide numerical experiments to show practical numerical gains, as well as theoretical guarantees on the efficiency of our approach.