Entropic estimation of optimal transport maps
arXiv:2109.12004
Abstract
We develop a computationally tractable method for estimating the optimal map between two distributions over with rigorous finite-sample guarantees. Leveraging an entropic version of Brenier's theorem, we show that our estimator -- the \emph{barycentric projection} of the optimal entropic plan -- is easy to compute using Sinkhorn's algorithm. As a result, unlike current approaches for map estimation, which are slow to evaluate when the dimension or number of samples is large, our approach is parallelizable and extremely efficient even for massive data sets. Under smoothness assumptions on the optimal map, we show that our estimator enjoys comparable statistical performance to other estimators in the literature, but with much lower computational cost. We showcase the efficacy of our proposed estimator through numerical examples, even ones not explicitly covered by our assumptions. By virtue of Lepski's method, we propose a modified version of our estimator that is adaptive to the smoothness of the underlying optimal transport map. Our proofs are based on a modified duality principle for entropic optimal transport and on a method for approximating optimal entropic plans due to Pal (2019).
38 pages, 8 figures
References in corpus (8)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Sample Complexity of Sinkhorn divergences
- Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
- Faster Wasserstein Distance Estimation with the Sinkhorn Divergence
- Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections
- Asymptotics for semi-discrete entropic optimal transport
- On the difference between entropic cost and the optimal transport cost
- Learning normalizing flows from Entropy-Kantorovich potentials