# Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2018.

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

- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [Universal Approximation Under Constraints is Possible with Transformers](https://mlsanity.com/paper/2110.03303/) (2021)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Amortized Projection Optimization for Sliced Wasserstein Generative Models](https://mlsanity.com/paper/2203.13417/) (2022)
- [On Transportation of Mini-batches: A Hierarchical Approach](https://mlsanity.com/paper/2102.05912/) (2021)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Faster Inference of Flow-Based Generative Models via Improved Data-Noise Coupling](https://mlsanity.com/paper/2603.15279/) (2026)
- [KOI: Accelerating Online Imitation Learning via Hybrid Key-state Guidance](https://mlsanity.com/paper/2408.02912/) (2024)
- [WFR-FM: Simulation-Free Dynamic Unbalanced Optimal Transport](https://mlsanity.com/paper/2601.06810/) (2026)
- [Improving Approximate Optimal Transport Distances using Quantization](https://mlsanity.com/paper/2102.12731/) (2021)
- [Group-blind optimal transport to group parity and its constrained variants](https://mlsanity.com/paper/2310.11407/) (2023)
- [Improving Consistency Models with Generator-Augmented Flows](https://mlsanity.com/paper/2406.09570/) (2024)
- [Estimating Long-term Heterogeneous Dose-response Curve: Generalization Bound Leveraging Optimal Transport Weights](https://mlsanity.com/paper/2406.19195/) (2024)
- [Optimal transport meets noisy label robust loss and MixUp regularization for domain adaptation](https://mlsanity.com/paper/2206.11180/) (2022)
- [Optimal Transport-inspired Deep Learning Framework for Slow-Decaying Kolmogorov n-width Problems: Exploiting Sinkhorn Loss and Wasserstein Kernel](https://mlsanity.com/paper/2308.13840/) (2023)
- [Schr"odinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres](https://mlsanity.com/paper/2506.17197/) (2025)
- [Amortized Optimal Transport from Sliced Potentials](https://mlsanity.com/paper/2604.15114/) (2026)
- [Feature Selection via Maximizing Distances between Class Conditional Distributions](https://mlsanity.com/paper/2401.07488/) (2024)
- [How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectories](https://mlsanity.com/paper/2402.09113/) (2024)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Document-Level Text Generation with Minimum Bayes Risk Decoding using Optimal Transport](https://mlsanity.com/paper/2505.23078/) (2025)
- [On the Information Processing of One-Dimensional Wasserstein Distances with Finite Samples](https://mlsanity.com/paper/2511.12881/) (2025)
- [Multiscale Supervised Unbalanced Optimal Transport Flow Matching](https://mlsanity.com/paper/2605.16529/) (2026)

## Abstract (arXiv)

We propose a simple subsampling scheme for fast randomized approximate computation of optimal transport distances. This scheme operates on a random subset of the full data and can use any exact algorithm as a black-box back-end, including state-of-the-art solvers and entropically penalized versions. It is based on averaging the exact distances between empirical measures generated from independent samples from the original measures and can easily be tuned towards higher accuracy or shorter computation times. To this end, we give non-asymptotic deviation bounds for its accuracy in the case of discrete optimal transport problems. In particular, we show that in many important instances, including images (2D-histograms), the approximation error is independent of the size of the full problem. We present numerical experiments that demonstrate that a very good approximation in typical applications can be obtained in a computation time that is several orders of magnitude smaller than what is required for exact computation of the full problem.