# Improving Approximate Optimal Transport Distances using Quantization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [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)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Improving GANs Using Optimal Transport](https://mlsanity.com/paper/1803.05573/) (2018)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [Optimal Transport: Fast Probabilistic Approximation with Exact Solvers](https://mlsanity.com/paper/1802.05570/) (2018)
- [Multiscale Strategies for Computing Optimal Transport](https://mlsanity.com/paper/1708.02469/) (2017)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Quantized Wasserstein Procrustes Alignment of Word Embedding Spaces](https://mlsanity.com/paper/2212.02468/) (2022)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [Scalable Learning from Probability Measures with Mean Measure Quantization](https://mlsanity.com/paper/2502.04907/) (2025)
- [Quantization-based Bounds on the Wasserstein Metric](https://mlsanity.com/paper/2506.00976/) (2025)

## Abstract (arXiv)

Optimal transport (OT) is a popular tool in machine learning to compare probability measures geometrically, but it comes with substantial computational burden. Linear programming algorithms for computing OT distances scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access. We also provide a variant of our algorithm to improve the performance of approximate solvers, focusing on those for entropy-regularized transport. We give theoretical guarantees on the benefits of this quantization step and display experiments showing that it behaves well in practice, providing a practical approximation algorithm that can be used as a drop-in replacement for existing OT estimators.