# New Algorithmic Directions in Optimal Transport and Applications for Product Spaces

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 48 references that are in the map.
- First posted on arXiv 25 Sep 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Statistical optimal transport](https://mlsanity.com/paper/2407.18163/) (2024)
- [Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes](https://mlsanity.com/paper/1810.02403/) (2018)
- [Causal transport in discrete time and applications](https://mlsanity.com/paper/1606.04062/) (2016)
- [On Approximating Total Variation Distance](https://mlsanity.com/paper/2206.07209/) (2022)
- [Optimal Transport of Classifiers to Fairness](https://mlsanity.com/paper/2202.03814/) (2022)
- [Can Adversarially Robust Learning Leverage Computational Hardness?](https://mlsanity.com/paper/1810.01407/) (2018)
- [The Importance of Generation Order in Language Modeling](https://mlsanity.com/paper/1808.07910/) (2018)
- [A simple polynomial-time approximation algorithm for the total variation distance between two product distributions](https://mlsanity.com/paper/2208.00740/) (2022)
- [Computational Concentration of Measure: Optimal Bounds, Reductions, and More](https://mlsanity.com/paper/1907.05401/) (2019)
- [Improving Diffusion-Based Generative Models via Approximated Optimal Transport](https://mlsanity.com/paper/2403.05069/) (2024)
- [Clustering, factor discovery and optimal transport](https://mlsanity.com/paper/1902.10288/) (2019)

## Abstract (arXiv)

We study optimal transport between two high-dimensional distributions μ,nu in Rn from an algorithmic perspective: given x ~ μ, find a close y ~ nu in poly(n) time, where n is the dimension of x,y. Thus, running time depends on the dimension rather than the full representation size of μ,nu. Our main result is a general algorithm for transporting any product distribution μ to any nu with cost Delta + δ under ℓpp, where Delta is the Knothe-Rosenblatt transport cost and δ is a computational error decreasing with runtime. This requires nu to be "sequentially samplable" with bounded average sampling cost, a new but natural notion. We further prove: An algorithmic version of Talagrand's inequality for transporting the standard Gaussian Phin to arbitrary nu under squared Euclidean cost. For nu = Phin conditioned on a set S of measure varepsilon, we construct the sequential sampler in expected time poly(n/varepsilon) using membership oracle access to S. This yields an algorithmic transport from Phin to Phin|S in poly(n/varepsilon) time and expected squared distance O(log 1/varepsilon), optimal for general S of measure varepsilon. As corollary, we obtain the first computational concentration result (Etesami et al. SODA 2020) for Gaussian measure under Euclidean distance with dimension-independent transportation cost, resolving an open question of Etesami et al. Specifically, for any S of Gaussian measure varepsilon, most Phin samples can be mapped to S within distance O(√log 1/varepsilon) in poly(n/varepsilon) time.