Optimal transport metrics

danger: I am halfway through editing this! Notation inconsistencies and indeed plain falsehoods abound.

I presume there are other uses for optimal transport distances apart from as probability metrics, but so far I only care about them in that context, so this will be skewed that way.

Encyclopedia of Math says:

Let $(M,d)$ be a metric space for which every probability measure on $M$ is a Radon measure. For $p\ge 1$, let ${\mathcal{P}}_p(M)$ denote the collection of all probability measures $P$ on $M$ with finite $p^{\text{th}}$ moment for some $x_0$ in $M$,

$${\int }_{M}d(x,x_0{)}^p\mathrm{d}P(x)<+\mathrm{\infty }.$$

Then the $p^{\text{th}}$ Wasserstein distance between two probability measures $P$ and $Q$ in ${\mathcal{P}}_p(M)$ is defined as

$$W_p(P,Q):={(\underset{\gamma \in \mathrm{\Pi }(P,Q)}{inf}{\int }_{M\times M}d(x,y{)}^p\mathrm{d}\gamma (x,y))}^{1/p},$$ where $\mathrm{\Pi }(P,Q)$ denotes the collection of all measures on $M\times M$ with marginal distributions $P$ and $Q$ respectively.

We can work equivalently with RVs distributed according to these measures, respectively $X\sim P,Y\sim Q,$ and then we consider $\gamma$ to range over joint distributions for these RVs, so that $$W_p(X,Y):=W_p(P;Q):=\underset{\gamma }{inf}\mathbb{E}[d(X,Y{)}^p{]}^{1/p}$$

Also, the cost is usually just the Euclidean/$L_2$ distance, so that $$\begin{array}{rl}{W}_p(X,Y):=W_p(P;Q)& :=\underset{\gamma }{inf}\mathbb{E}[\Vert X-Y{\Vert }_2^p{]}^{1/p}.\end{array}$$

Practically, one usually sees $p\in \{1,2\}$. Maybe $p=\mathrm{\infty }$ is interesting also (Champion, De Pascale, and Juutinen 2008). For $p=1$ we have an extremely useful representation in terms of optimisation over functions, the Kantorovich-Rubinstein duality. $$W_1(P,Q)=\underset{f,g:f(x)+g(y)\le d(x,y)}{sup}{\mathbb{E}}_{x\sim P}[f(x)]-{\mathbb{E}}_{x\sim Q}[g(x)].$$ For Euclidean distance this optimisation ranges over 1-Lipschitz functions, $$W_1(P,Q)=\underset{\parallel f{\parallel }_L\le 1}{sup}{\mathbb{E}}_{x\sim P}[f(x)]-{\mathbb{E}}_{x\sim Q}[f(x)].$$ TODO: check that.

The Wasserstein distance between two objects is frequently intractable, or at least has no closed form, but you can find it for some useful special cases, or bound/approximate it in others.

🏗 discuss favourable properties of this metric (triangle inequality, bounds on moments etc).

But why do we care about such an intractable distance? Because it gives good error bounds for sufficiently nice expectations. We know that if $W_p(X,Y)\le ϵ$, then for any L-Lipschitz function $f$, $|f(X)-f(Y)|\le Lϵ.$