New Algorithmic Directions in Optimal Transport and Applications for Product Spaces

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.