Near-optimal estimation of smooth transport maps with kernel sums-of-squares
This provides the first tractable algorithm with near-optimal statistical guarantees for estimating transport maps, addressing a key bottleneck in applications such as generative modeling.
The paper tackles the problem of estimating optimal transport maps (rather than just distances) for applications like generative modeling, and achieves statistical error rates that nearly match existing minimax lower-bounds for smooth map estimation.
It was recently shown that under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. However, rather than the distance itself, the object of interest for applications such as generative modeling is the underlying optimal transport map. Hence, computational and statistical guarantees need to be obtained for the estimated maps themselves. In this paper, we propose the first tractable algorithm for which the statistical $L^2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation. Our method is based on solving the semi-dual formulation of optimal transport with an infinite-dimensional sum-of-squares reformulation, and leads to an algorithm which has dimension-free polynomial rates in the number of samples, with potentially exponentially dimension-dependent constants.