Optimal Transport (OT) naturally arises in many machine learning applications, where we need to handle cross-modality data from multiple sources. Yet the heavy computational burden limits its wide-spread uses. To address the scalability issue, we propose an implicit generative learning-based framework called SPOT (Scalable Push-forward of Optimal Transport). Specifically, we approximate the optimal transport plan by a pushforward of a reference distribution, and cast the optimal transport problem into a minimax problem. We then can solve OT problems efficiently using primal dual stochastic gradient-type algorithms. We also show that we can recover the density of the optimal transport plan using neural ordinary differential equations. Numerical experiments on both synthetic and real datasets illustrate that SPOT is robust and has favorable convergence behavior. SPOT also allows us to efficiently sample from the optimal transport plan, which benefits downstream applications such as domain adaptation. The Optimal Transport (OT) problem naturally arises in a variety of machine learning applications, where we need to handle cross-modality data from multiple sources. One example is domain adaptation: We collect multiple datasets from different domains, and we need to learn a model from a source dataset, which can be further adapted to target datasets BID18 BID8 . Another example is resource allocation: We want to assign a set of assets (one data source) to a set of receivers (another data source) so that an optimal economic benefit is achieved BID46 BID17 . Recent literature has shown that both aforementioned applications can be formulated as optimal transport problems.The optimal transport problem has a long history, and its earliest literature dates back to Monge (1781). Since then, it has attracted increasing attention and been widely studied in multiple communities such as applied mathematics, probability, economy and geography BID51 Carlier, 2012; BID23 . Specifically, we consider two sets of data, which are generated from two different distributions denoted by X ∼ µ and Y ∼ ν.1 We aim to find an optimal joint distribution γ of X and Y , which minimizes the expectation on some ground cost function c, i.e., γ * = arg min γ∈Π(µ,ν) DISPLAYFORM0 The constraint γ ∈ Π(µ, ν) requires the marginal distribution of X and Y in γ to be identical to µ and ν, respectively. The cost function c measures the discrepancy between input X and Y . For crossmodality structured data, the form of c incorporates prior knowledge into optimal transport problem. Existing literature often refers to the optimal expected cost W * (µ, ν) = E (X,Y )∼γ * [c(X, Y )] as Wasserstein distance when c is a distance, and γ * as the optimal transport plan. For domain adaptation, the function c measures the discrepancy between X and Y , and the optimal transport plan γ * essentially reveals the transfer of the knowledge from source X to target Y . For resource allocation, the function c is the cost of assigning resource X to receiver Y , and the optimal transport plan γ To address the scalability and efficiency issues, we propose a new implicit generative learning-based framework for solving optimal transport problems. Specifically, we approximate γ * by a generative model, which maps from some latent variable Z to (X, Y ). For simplicity, we denote DISPLAYFORM1 where ρ is some simple latent distribution and G is some operator, e.g., deep neural network or neural ordinary differential equation (ODE) . Accordingly, instead of directly estimating the probability density of γ * , we estimate the mapping G between Z and (X, Y ) by solving DISPLAYFORM2 We then cast equation 3 into a minimax optimization problem using the Lagrangian multiplier method. As the constraints in equation 3 are over the space of continuous distributions, the Lagrangian multiplier is actually infinite dimensional. Thus, we propose to approximate the Lagrangian multiplier by deep neural networks, which eventually delivers a finite dimensional generative learning problem.Our proposed framework has three major benefits: (1) Our formulated minimax optimization problem can be efficiently solved by primal dual stochastic gradient-type algorithms. Many empirical studies have corroborated that these algorithms can easily scale to very large minimax problems in machine learning BID2 ; (2) Our framework can take advantage of recent advances in deep learning. Many empirical evidences have suggested that deep neural networks can effectively adapt to data with intrinsic low dimensional structures BID33 . Although they are often overparameterized, due to the inductive biases of the training algorithms, the intrinsic dimensions of deep neural networks are usually controlled very well, which avoids the curse of dimensionality; (3) Our adopted generative models allow us to efficiently sample from the optimal transport plan. This is very convenient for certain downstream applications such as domain adaptation, where we can generate infinitely many data points paired across domains BID35 .Moreover , the proposed framework can also recover the density of entropy regularized optimal transport plan. Specifically , we adopt the neural Ordinary Differential Equation (ODE) approach in to model the dynamics that how Z gradually evolves to G(Z). We then derive the ODE that describes how the density evolves, and solve the density of the transport plan from the ODE. The recovery of density requires no extra parameters, and can be evaluated efficiently.Notations: Given a matrix A ∈ R d×d , det(A) denotes its determinant, tr(A) = i A ii denotes its trace, A F = i,j A 2 ij denotes its Frobenius norm, and |A| denotes a matrix with [|A|] ij = |A ij |. We use dim(v) to denote the dimension of a vector v. Existing literature shows that several stochastic algorithms can efficiently compute the Wasserstein distance between two continuous distributions. These algorithms, however, only apply to the dual of the OT problem equation 1, and cannot provide the optimal transport plan. For example, BID19 suggest to expand the dual variables in two reproducing kernel Hilbert spaces. They then apply the Stochastic Averaged Gradient (SAG) algorithm to compute the optimal objective value of OT with continuous marginal distributions or semi-discrete marginal distributions (i.e., one marginal distribution is continuous and the other is discrete). The follow-up work, BID47 , parameterize the dual variables with neural networks and apply the Stochastic Gradient Descent (SGD) algorithm to eventually achieve a better convergence. These two methods can only provide the optimal transport plan and recover the joint density when the densities of the marginal distributions are known. This is prohibitive in most applications, since we only have access to the empirical data. Our framework actually allows us to efficiently compute the joint density from the transformation of the latent variable Z as in Section 4. TAB1 shows the architecture of two discriminators λ X , λ Y . The two networks have identical architechture and do not share parameters. The CNN architecture for USPS, MNIST and MNISTM. PReLU activation is applied BID24 . TAB2 shows the architecture of two generators G X and G Y . The last column in TAB2 means whether G X and G Y share the same parameter. TAB3 shows the architecture of two discriminators λ X , λ Y , and two classifiers D X , D Y . The last column in TAB2 uses (·, ·) to denote which group of discriminators share the same parameter. TAB4 shows the architecture of two generators G X and G Y . The last column in TAB4 means whether G X and G Y share the same parameter. The Residual block is the same as the one in BID38 . [3 × 3, ch, stride = 1, padding =0] Sigmoid False TAB5 shows the architecture of two discriminators λ X , λ Y , and two classifiers D X , D Y . The last column in TAB5 uses (·, ·) to denote which group of discriminators share the same parameter.
Use GAN-based method to scalably solve optimal transport
{"src": "scitldr-AIC_train", "paper_id": "S1xA7ILFOV"}