This paper presents a novel two-step approach for the fundamental problem of learning an optimal map from one distribution to another. First, we learn an optimal transport (OT) plan, which can be thought as a one-to-many map between the two distributions. To that end, we propose a stochastic dual approach of regularized OT, and show empirically that it scales better than a recent related approach when the amount of samples is very large. Second, we estimate a Monge map as a deep neural network learned by approximating the barycentric projection of the previously-obtained OT plan. This parameterization allows generalization of the mapping outside the support of the input measure. We prove two theoretical stability results of regularized OT which show that our estimations converge to the OT and Monge map between the underlying continuous measures. We showcase our proposed approach on two applications: domain adaptation and generative modeling. Mapping one distribution to another Given two random variables X and Y taking values in X and Y respectively, the problem of finding a map f such that f (X) and Y have the same distribution, denoted f (X) ∼ Y henceforth, finds applications in many areas. For instance, in domain adaptation, given a source dataset and a target dataset with different distributions, the use of a mapping to align the source and target distributions is a natural formulation BID22 since theory has shown that generalization depends on the similarity between the two distributions BID2 . Current state-of-the-art methods for computing generative models such as generative adversarial networks BID21 , generative moments matching networks BID26 or variational auto encoders BID24 ) also rely on finding f such that f (X) ∼ Y . In this setting, the latent variable X is often chosen as a continuous random variable, such as a Gaussian distribution, and Y is a discrete distribution of real data, e.g. the ImageNet dataset. By learning a map f , sampling from the generative model boils down to simply drawing a sample from X and then applying f to that sample.Mapping with optimality Among the potentially many maps f verifying f (X) ∼ Y , it may be of interest to find a map which satisfies some optimality criterion. Given a cost of moving mass from one point to another, one would naturally look for a map which minimizes the total cost of transporting the mass from X to Y . This is the original formulation of Monge (1781) , which initiated the development of the optimal transport (OT) theory. Such optimal maps can be useful in numerous applications such as color transfer BID17 , shape matching BID46 , data assimilation BID37 , or Bayesian inference BID31 . In small dimension and for some specific costs, multi-scale approaches BID28 or dynamic formulations BID16 BID3 BID44 can be used to compute optimal maps, but these approaches become intractable in higher dimension as they are based on space discretization. Furthermore, maps veryfiying f (X) ∼ Y might not exist, for instance when X is a constant but not Y . Still, one would like to find optimal maps between distributions at least approximately. The modern approach to OT relaxes the Monge problem by optimizing over plans, i.e. distributions over the product space X × Y, rather than maps, casting the OT problem as a linear program which is always feasible and easier to solve. However, even with specialized algorithms such as the network simplex, solving that linear program takes O(n 3 log n) time, where n is the size of the discrete distribution (measure) support.Large-scale OT Recently, BID14 showed that introducing entropic regularization into the OT problem turns its dual into an easier optimization problem which can be solved using the Sinkhorn algorithm. However, the Sinkhorn algorithm does not scale well to measures supported on a large number of samples, since each of its iterations has an O(n 2 ) complexity. In addition, the Sinkhorn algorithm cannot handle continuous probability measures. To address these issues, two recent works proposed to optimize variations of the dual OT problem through stochastic gradient methods. BID20 proposed to optimize a "semi-dual" objective function. However, their approach still requires O(n) operations per iteration and hence only scales moderately w.r.t. the size of the input measures. BID1 proposed a formulation that is specific to the so-called 1-Wasserstein distance (unregularized OT using the Euclidean distance as a cost function). This formulation has a simpler dual form with a single variable which can be parameterized as a neural network. This approach scales better to very large datasets and handles continuous measures, enabling the use of OT as a loss for learning a generative model. However, a drawback of that formulation is that the dual variable has to satisfy the non-trivial constraint of being a Lipschitz function. As a workaround, BID1 proposed to use weight clipping between updates of the neural network parameters. However, this makes unclear whether the learned generative model is truly optimized in an OT sense. Besides these limitations, these works only focus on the computation of the OT objective and do not address the problem of finding an optimal map between two distributions. We proposed two original algorithms that allow for i) large-scale computation of regularized optimal transport ii) learning an optimal map that moves one probability distribution onto another (the so-called Monge map). To our knowledge, our approach introduces the first tractable algorithms for computing both the regularized OT objective and optimal maps in large-scale or continuous settings. We believe that these two contributions enable a wider use of optimal transport strategies in machine learning applications. Notably, we have shown how it can be used in an unsupervised domain adaptation setting, or in generative modeling, where a Monge map acts directly as a generator. Our consistency results show that our approach is theoretically well-grounded. An interesting direction for future work is to investigate the corresponding convergence rates of the empirical regularized optimal plans. We believe this is a very complex problem since technical proofs regarding convergence rates of the empirical OT objective used e.g. in BID45 BID6 BID18 do not extend simply to the optimal transport plans.that we have π n = (id, T n )#µ n . This also impliesπ n = T n so that (id,π n )#µ n = (id, T n )#µ n . Hence, the second term in the right-hand side of (18) converges to 0 as a result of the stability of optimal transport BID47 [Theorem 5.20] . Now, we show that the first term also converges to 0 for ε n converging sufficiently fast to 0. By definition of the pushforward operator, DISPLAYFORM0 g(x, T n (x))dµ n (x) (19) and we can bound, DISPLAYFORM1 where Y n = (y 1 , · · · , y n ) t and K g is the Lipschitz constant of g. The first inequality follows from g being Lipschitz. The next equality follows from the discrete close form of the barycentric projection. The last inequality is obtained through Cauchy-Schwartz. We can now use the same arguments as in the previous proof. A convergence result by BID10 shows that there exists positive constants (w.r.t. ε n ) M cn,µn,νn and λ cn,µn,νn such that, where c n = (c(x 1 , y 1 ), · · · , c(x n , y n )). The subscript indices indicate the dependences of each constant. Hence, we see that choosing any (ε n ) such that (21) tends to 0 provides the results. In particular, we can take ε n = λ cn,µn,νn ln(n 2 ||Y n || 1/2 R n×d ,2 M cn,µn,νn )which suffices to have the convergence of (15) to 0 for Lipschitz function g ∈ C l (R d × R d ). This proves the weak convergence of (id,π εn n )#µ n to (id, f )#µ.
Learning optimal mapping with deepNN between distributions along with theoretical guarantees.
{"src": "scitldr-AIC_train", "paper_id": "B1zlp1bRW"}