Goal: Given a set of data in high dimension (e.g., images, speeches, words, etc.), we would like to learn the underlying data distribution
OT is used as a loss between push-forward distribution from low-dimensional space and the empirical distribution from data
Popular examples: Wasserstein GAN [1, 2], Wasserstein Autoencoder [3]

Domain Adaptation: An important problem in designing autonomous vehicles is to make sure that the model we train in some particular weather/ environment/ time (source domains) will still perform well under other weathers/ environments/ time (target domains)
Optimal transport is an efficient loss function that captures the difference between these domains (e.g., [4] and [5])

Domain Generalization: An important example is that we would like to develop a face recognition system in new generation of Iphone (target domain) based on the previous Iphones (source domains) without the expensive cost of collecting new data for the new Iphone
Optimal Transport also offers a great solution for this application

Above: Input 3D images
Below: Reconstruction of 3D images based on optimal transport [6]

Each image contains several annotated regions, such as, those of animals, buildings, trees, etc.
Goal: Based on the clustering behaviors of annotated regions from the images, we would like to learn the themes/ clusters of images

Optimal Transport is also a powerful tool for other important applications:

• Forecasting Time Series (e.g., forecasting sales (Walmart), forecasting expenses (Amazon), etc.) [9]
• Machine Translation [10]
• Robust/ Reliable Machine Learning [11]
• airness/ Responsible AI
• Optimal transport can be used to understand the behaviors of latent variables associated with Relu, Maxpooling from Convolutional Neural Networks (CNNs) (cf. [12])
• Mixture models and hierarchical models: Characterizing the convergence rates of estimating parameters, performing model selection, etc. (cf. [13], [14], [15])
• Distributional robust optimization: Optimal Transport can be used to define a perturbed neighborhood of the true distribution (cf. [16], [17])

Optimal Transport was created by mathematician Gaspard Monge to find optimal ways to transport commodities and products under certain constraints

We start with a simple practical example of moving products from Bakeries (denoted by B) to Restaurants (denoted by R)
Two bakeries will not transport the products to the same restaurant
We denote by Cij the distance between bakery Bi to restaurant Rj
Goal: Find the shortest distance to move products from the bakeries to restaurants

• If we search for all the possible permutations in the optimization problem, the complexity of solving Monge’s Optimal Transport is (n ) (The total number of permutations of 1,2, ,n is )
• By using Hungarian’s algorithm for graph matching, we can obtain an improved complexity of (n3)
• When we have Cij = | Bi jR| 2 , i.e., one dimensional setting, we can use quick sort algorithm to compute Monge’s Optimal Transport in equation (1) with a complexity of (n log n)

Push-forward measure

• The non-existence of transport map T under pathological settings makes it challenging to use Monge’s OT formulation when the probability distributions P and Q are discrete
• Furthermore, due to the non-linearity of the constraint T P= Q, it is non- trivial to solve for or approximate the optimal mapping T in equation (2)
• A relaxation and optimization friendly form of Monge’s OT formulation is needed