Kantorovich-Rubinstein Duality

The 1-Wasserstein distance equals the largest mean gap a 1-Lipschitz critic can find, turning transport into a neural discriminator objective.

The best 1-Lipschitz critic prices the gap between two distributions

Why Does This Exist?

Primal OT optimizes over couplings, which are quadratic in size and awkward for gradient training. The dual rewrites the same value as one maximization over pricing functions: assign each location a price with slope capped at 1, then the transport cost equals the biggest price gap between target and source. That max-over-critics shape plugs directly into neural training as the WGAN objective.

Primal background: Monge and Kantorovich. GAN usage: OT in generative modeling.

The one idea you need first

A function is 1-Lipschitz when $|f(x) - f(y)| \leq \|x - y\|$ : slope never exceeds 1. Clipping, spectral normalization, and gradient penalties all enforce versions of this cap.

Think of It Like This

A moving company bidding with a rate cap

Two warehouses hold furniture and a mover quotes transfer prices per location with one rule: quotes at nearby addresses differ by at most the mileage between them. The mover then collects the quote gap between the full and empty warehouse.

The sharpest legal quotebook prices the true moving cost exactly. Let quotes slope steeper and the bid overshoots; that overshoot is the WGAN critic cheating without a Lipschitz cap.

Where the analogy stops: real critics are neural nets whose Lipschitz constant is estimated, not a legal cap on paper.

How It Actually Works

$W_1(\mu,\nu) = \sup_{\|f\|_L \leq 1} \mathbb{E}_\nu[f] - \mathbb{E}_\mu[f]$ . The optimal $f$ (Kantorovich potential) has gradient norm 1 along transport rays. WGAN trains $\max_\phi \mathbb{E}[f_\phi(\text{real})] - \mathbb{E}[f_\phi(\text{fake})]$ with penalty $\lambda(\|\nabla f\| - 1)^2$ keeping the critic near the feasible set.

Worked example

$\mu = \delta_0$ , $\nu = \delta_3$ on the line:

Primal: move mass $3$ units, $W_1 = 3$ .
Dual: 1-Lipschitz $f$ gives $f(3) - f(0) \leq 3$ , max $3$ attained by $f(x) = x$ . Gap $3 - 0 = 3$ . Match.
Cheat check: $g(x) = 2x$ (2-Lipschitz) claims gap $6$ , double the truth. Gradient penalty would add $\lambda(2-1)^2 = \lambda$ per point, pulling slope back toward 1. At $\lambda = 10$ the penalty $10$ exceeds the $3$ gain, so cheating loses.

Watch Out For

Weight clipping as the Lipschitz fix

Hard clipping to $[-c, c]$ caps capacity and biases critics toward trivial functions. Gradients vanish or explode and samples degrade.

Prefer gradient penalty or spectral normalization, which constrain slope without flattening the function class.

Reading critic loss as sample quality

The dual value tracks an estimate of $W_1$ under the current critic, not FID or visual fidelity. A rising gap can mean a stronger critic rather than worse samples.

Pair critic curves with independent sample metrics before judging generators.

The Quick Version

KR duality turns 1-Wasserstein distance into a max over 1-Lipschitz critics.
The critic gap is the WGAN objective with a slope cap.
Optimal potentials have unit gradient along transport paths.
Penalties beat clipping for enforcing the Lipschitz constraint.
Critic values estimate distance under the current net, not absolute quality.