optimal transport costs

Let $\Gamma (\rho ,\nu )$ be the set of joint probability distributions over a space $\mathcal{X}\times \mathcal{X}$ whose martingales are $\rho$ and $\nu$. Given a (nonnegative) cost function $c:\mathcal{X}\times \mathcal{X}\to {\mathbb{R}}_{\ge 0}$, the optimal transport cost between $\rho$ and $\nu$ is

$$L_c(\rho ,\nu )=\underset{\pi \in \Gamma (\rho ,\nu )}{\inf }{\mathbb{E}}_{(X,Y)\sim \pi )c(X,Y)}=\underset{\pi \in \Gamma (\rho ,\nu )}{\inf }\int c(x,y)\text{d}\pi (x,y).$$

If we take $c=d^p$ where $d$ is a metric, we recover the Wasserstein distance. We call this an optimal transport cost because it’s a formulation of the optimal transport problem. The optimization problem can be seen as a relaxation of Monge formulation, often called the Kantorovich formulation (see below).

Optimal transport costs are convex divergences. We can thus build confidence sequences for them using confidence sequences for convex functionals.

The Kantorovich Dual

$L_c$ admits the following dual representation, known as the Kantorovich dual:

$$L_c(\rho ,\nu )\le \underset{(f,g)\in {\mathcal{M}}_c}{\sup }\{{\mathbb{E}}_P[f]+{\mathbb{E}}_Q[g]\},$$

where ${\mathcal{M}}_c$ is the set of pairs of functions $f,g$ such that $f(x)+g(y)\le c(x,y)$ for all $x,y\in \mathcal{X}$ (almost surely). If $c$ is lower semi-continuous then we have equality above. This might be considered the equivalent of the variational representation of e.g., f-divergences.

Motivation: The Kantorovich Relaxation

We can recover optimal transport costs by relaxing the Monge formulation, which does not always admit a solution. To remedy this, we might allow ourselves to transport dirt from one pile to multiples holes. Let $\pi (i,j)$ denote the amount of dirt transported from pile $i$ to hole $j$. Then we are looking to minimize the total transportation cost ${\sum }_{i,j}\pi (i,j)c(i,j)$ such that the total amount of dirt transported from pile $i$ is ${\alpha }_i$, and the total amount of dirt transported to hole $j$ is ${\beta }_j$. That is, we are looking to solve

$$\underset{\pi }{\min }\sum _{i,j}\pi (i,j)c(i,j)\text{s.t.}\sum _j\pi (i,j)=\alpha (i),\sum _i\pi (i,j)=\beta (j).$$

Again, looking at $\alpha$ and $\beta$ as discrete probability distribution, we are searching for a map between $\alpha$ and $\beta$ which minimizes total transportation cost who marginal distributions are $\alpha$ and $\beta$. This suggests the continuous version of the above optimization problem:

$$L_c(\alpha ,\beta )=\underset{\pi \in \Gamma (\alpha ,\beta )}{\inf }\{{\mathbb{E}}_{(X,Y)\sim \pi }[c(X,Y)]\},$$

where

$$\Gamma (\alpha ,\beta )=\{\pi \in \mathcal{P}(\mathcal{X}\times \mathcal{X}):\int \pi (x,y)dy=\alpha (x),\int \pi (x,y)dx=\beta (y).\},$$

is the set of joint distributions on $\mathcal{X}\times \mathcal{X}$ whose marginals are $\alpha$ and $\beta$. This is known as the Kantorovich relaxation.