New Algorithmic Directions in Optimal Transport and Applications for Product Spaces

We consider the problem of optimal transport between two high-dimensional distributions µ, ν in R n from a new algorithmic perspective, in which we are given a sample x ∼ µ and we have to find a close y ∼ ν while running in poly(n) time, where n is the size/dimension of x, y. In other words, we are interested in making the running time bounded in dimension of the spaces rather than bounded in the total size of the representations of the two distributions. Our main result is a general algorithmic transport result between any product distribution µ and an arbitrary distribution ν of total cost ∆ + δ under ℓ p p cost; here ∆ is the cost of the so-called Knothe-Rosenblatt transport from µ to ν, while δ is a computational error that goes to zero for larger running time in the transport algorithm. For this result, we need ν to be "sequentially samplable" with a "bounded average sampling cost" which is a novel but natural notion of independent interest. In addition, we prove the following. We prove an algorithmic version of the celebrated Talagrand's inequality for transporting the standard Gaussian distribution Φ n to an arbitrary ν under the Euclidean-squared cost. When ν is Φ n conditioned on a set S of measure ε, we show how to implement the needed sequential sampler for ν in expected time poly(n/ε), using membership oracle access to S. Hence, we obtain an algorithmic transport that maps Φ n to Φ n |S in time poly(n/ε) and expected Euclidean-squared distance O(log 1/ε), which is optimal for a general set S of measure ε. As corollary, we find the first computational concentration (Etesami et al. SODA 2020) result for the Gaussian measure under the Euclidean distance with a dimension-independent transportation cost, resolving a question of Etesami et al. More precisely, for any set S of Gaussian measure ε, we map most of Φ n samples to S with Euclidean distance O log 1/ε in time poly(n/ε).