Kantorovich–Rubinstein duality

Remarks

The inequality $\ge$ is easy. For a coupling $\gamma$ and a $1$-Lipschitz $f$, one has $\int f \, d\mu - \int f \, d\nu = \int (f(x) - f(y)) \, d\gamma(x, y) \le \int d(x, y) \, d\gamma(x, y)$. The reverse inequality is a case of Kantorovich duality in optimal transport, for the cost $c(x, y) = d(x, y)$. For this cost the dual potentials can be taken $1$-Lipschitz, with the second potential equal to $-f$.

Example: for Dirac measures $\delta_x$ and $\delta_y$, the function $f = d(\cdot, y)$ is $1$-Lipschitz and gives $f(x) - f(y) = d(x, y)$. This matches $W_1(\delta_x, \delta_y) = d(x, y)$.

The moment condition makes all the integrals finite, since a $1$-Lipschitz $f$ satisfies $\abs{f(x)} \le \abs{f(x_0)} + d(x, x_0)$.

Going deeper

For a student

The duality turns a minimum over couplings into a maximum over Lipschitz functions. It shows that $W_1(\mu, \nu)$ depends only on the signed measure $\mu - \nu$, as a dual norm for the Lipschitz seminorm. This is the form of $W_1$ used in Wasserstein generative adversarial networks, where the Lipschitz function is a trained critic. It is often called the Kantorovich–Rubinstein theorem.