# Stochastic Optimization for Large-scale Optimal Transport

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

## Key facts

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

## Built on by (most cited first, 30 of 189)

- [Neural Optimal Transport](https://mlsanity.com/paper/2201.12220/) (2022)
- [Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark](https://mlsanity.com/paper/2106.01954/) (2021)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Simulation-free Schr"odinger bridges via score and flow matching](https://mlsanity.com/paper/2307.03672/) (2023)
- [Optimal Flow Matching: Learning Straight Trajectories in Just One Step](https://mlsanity.com/paper/2403.13117/) (2024)
- [Large-Scale Wasserstein Gradient Flows](https://mlsanity.com/paper/2106.00736/) (2021)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [Wasserstein Adversarial Imitation Learning](https://mlsanity.com/paper/1906.08113/) (2019)
- [TopV: Compatible Token Pruning with Inference Time Optimization for Fast and Low-Memory Multimodal Vision Language Model](https://mlsanity.com/paper/2503.18278/) (2025)
- [Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization](https://mlsanity.com/paper/2102.01752/) (2021)
- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control](https://mlsanity.com/paper/2302.03791/) (2023)
- [Light and Optimal Schr"odinger Bridge Matching](https://mlsanity.com/paper/2402.03207/) (2024)
- [Neural Monge Map estimation and its applications](https://mlsanity.com/paper/2106.03812/) (2021)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Neural Optimal Transport with General Cost Functionals](https://mlsanity.com/paper/2205.15403/) (2022)
- [A Survey on Optimal Transport for Machine Learning: Theory and Applications](https://mlsanity.com/paper/2106.01963/) (2021)
- [Kernel Neural Optimal Transport](https://mlsanity.com/paper/2205.15269/) (2022)
- [On amortizing convex conjugates for optimal transport](https://mlsanity.com/paper/2210.12153/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Energy-guided Entropic Neural Optimal Transport](https://mlsanity.com/paper/2304.06094/) (2023)
- [Conditional Optimal Transport on Function Spaces](https://mlsanity.com/paper/2311.05672/) (2023)
- [Wasserstein Iterative Networks for Barycenter Estimation](https://mlsanity.com/paper/2201.12245/) (2022)
- [Wasserstein Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2110.07940/) (2021)
- [Vector Quantized Wasserstein Auto-Encoder](https://mlsanity.com/paper/2302.05917/) (2023)
- [Calibration tests beyond classification](https://mlsanity.com/paper/2210.13355/) (2022)
- [Sliced Optimal Partial Transport](https://mlsanity.com/paper/2212.08049/) (2022)
- [Kantorovich Strikes Back! Wasserstein GANs are not Optimal Transport?](https://mlsanity.com/paper/2206.07767/) (2022)
- [Building the Bridge of Schr"odinger: A Continuous Entropic Optimal Transport Benchmark](https://mlsanity.com/paper/2306.10161/) (2023)

## Abstract (arXiv)

Optimal transport (OT) defines a powerful framework to compare probability distributions in a geometrically faithful way. However, the practical impact of OT is still limited because of its computational burden. We propose a new class of stochastic optimization algorithms to cope with large-scale problems routinely encountered in machine learning applications. These methods are able to manipulate arbitrary distributions (either discrete or continuous) by simply requiring to be able to draw samples from them, which is the typical setup in high-dimensional learning problems. This alleviates the need to discretize these densities, while giving access to provably convergent methods that output the correct distance without discretization error. These algorithms rely on two main ideas: (a) the dual OT problem can be re-cast as the maximization of an expectation ; (b) entropic regularization of the primal OT problem results in a smooth dual optimization optimization which can be addressed with algorithms that have a provably faster convergence. We instantiate these ideas in three different setups: (i) when comparing a discrete distribution to another, we show that incremental stochastic optimization schemes can beat Sinkhorn's algorithm, the current state-of-the-art finite dimensional OT solver; (ii) when comparing a discrete distribution to a continuous density, a semi-discrete reformulation of the dual program is amenable to averaged stochastic gradient descent, leading to better performance than approximately solving the problem by discretization ; (iii) when dealing with two continuous densities, we propose a stochastic gradient descent over a reproducing kernel Hilbert space (RKHS). This is currently the only known method to solve this problem, apart from computing OT on finite samples. We backup these claims on a set of discrete, semi-discrete and continuous benchmark problems.