Optimal Transport (Marco Cuturi)

[YugeTen]

Optimal transport

(see lecture notes and tutorial)

Introduction

Two examples:

• Moving earth & Soldiers Monge problem: what is the most efficient way to bring earth from one place to another

How to move the sand to fill the hole most efficiently? Characterise the work involved here by the product between mass and the moving distance:

Exact solution: linear programming

Sinkhorn Algorithm for Entropy Regularized Optimal Transport

Dealing with curse of high dimensionality

Sliced Wasserstein distance:

PCA projection

k-dim (robust) projection

Applications: Average measures

k-means

You can consider W distance as a k-mean algorithm, if the dimension of X is much higher than the dimension of Y.

Wasserstein Barycenter:

Brain imaging

Mapping visual stimulus to different cortex of the brain using MEG. Different subject will have slightly different response -- to account for this spatial variation one can use Wasserstein average.

KL, MMD vs. Wasserstein

there is no geometry in KL/MMD, they're better for high dimensional data. For KL, when you have two Gaussians very close to each other, if the variance goes to zero, the divergence can go to infinity

Wasserstein vs. L2 averages

Domain adaptation

Learning with Wasserstein loss:

Sorting

On 1D, calculating the Wasserstein plan is equivalent to sorting (because the nth ranking point in X is always going to map to the nth ranking in Y)