In this paper, we present a novel and principled approach to learn the optimal transport between two distributions, from samples. Guided by the optimal transport theory, we learn the optimal Kantorovich potential which induces the optimal transport map. This involves learning two convex functions, by solving a novel minimax optimization. Building upon recent advances in the field of input convex neural networks, we propose a new framework where the gradient of one convex function represents the optimal transport mapping. Numerical experiments confirm that we learn the optimal transport mapping. This approach ensures that the transport mapping we find is optimal independent of how we initialize the neural networks. Further, target distributions from a discontinuous support can be easily captured, as gradient of a convex function naturally models a discontinuous transport mapping.
Statistical analysis of learning the optimal transport map through the semi-dual optimization problem is studied in @cite_17 @cite_23 , where the authors establish a minimax convergence rate with respect to number of samples for certain classes of regular probability distributions. They also propose a procedure that achieves the optimal convergence rate, that involves representing the function @math with span of wavelet basis functions up to a certain order, and also requiring the function @math to be convex. However, they do not provide a computational algorithm to implement the procedure.
@cite_23 @cite_17
2810943841 2946680009
Isotonic regression is a standard problem in shape-constrained estimation where the goal is to estimate an unknown nondecreasing regression function @math from independent pairs @math where @math . While this problem is well understood both statistically and computationally, much less is known about its uncoupled counterpart where one is given only the unordered sets @math and @math . In this work, we leverage tools from optimal transport theory to derive minimax rates under weak moments conditions on @math and to give an efficient algorithm achieving optimal rates. Both upper and lower bounds employ moment-matching arguments that are also pertinent to learning mixtures of distributions and deconvolution. Brenier's theorem is a cornerstone of optimal transport that guarantees the existence of an optimal transport map @math between two probability distributions @math and @math over @math under certain regularity conditions. The main goal of this work is to establish the minimax rates estimation rates for such a transport map from data sampled from @math and @math under additional smoothness assumptions on @math . To achieve this goal, we develop an estimator based on the minimization of an empirical version of the semi-dual optimal transport problem, restricted to truncated wavelet expansions. This estimator is shown to achieve near minimax optimality using new stability arguments for the semi-dual and a complementary minimax lower bound. These are the first minimax estimation rates for transport maps in general dimension.