Continuous Function

Foundation reference

Optimal Transport & Wasserstein Distance

Wasserstein distances measure how far probability mass must move to turn one distribution into another, so they respect the geometry of the space the data live in.

Concept 38 of 100TheoryStudy phase 8
Go to the mathAll concepts
Key equation
Wp(μ,ν)=(inf⁡γ∈Γ(μ,ν)∫∥x−y∥p dγ(x,y))1/pW_p(\mu, \nu) = \left( \inf_{\gamma \in \Gamma(\mu, \nu)} \int \|x - y\|^p \, d\gamma(x, y) \right)^{1/p}
Reading map and next steps

Study guide

Where to start

Concept 38 of 100Optimal TransportTheory · Study phase 8: Scaling, theory & multimodal
Question

Why is the KL divergence infinite when two distributions have disjoint supports, while the Wasserstein distance stays finite and measures how far the mass must move?

Go to the mathAll conceptsNext concept
How to study this pagePredict · Check · Generalize · Continue
PredictSay what you expect.

Pick a concrete input and say what the equation should give before you read the math.

CheckCheck against the math and the papers.

Work through the math, then read the cited papers for the original argument.

GeneralizeName what stays the same.

Identify the part of the idea that survives a change of notation or model, so you can recognize it in another paper or system.

ContinueFollow the connections.

Use the prerequisites and related concepts at the end of the page to fill the next gap.

Why It Matters for Modern Models

  • Wasserstein distances measure how far probability mass must move to turn one distribution into another, so they respect the geometry of the space the data live in.
  • Arjovsky et al. (2017) argue that the Wasserstein-1 distance gives useful gradients even when the generated and real distributions do not overlap, which motivated the Wasserstein GAN.
  • Flow matching with straight-line paths between independently paired noise and data samples does not learn the optimal transport map; pairing the samples with a minibatch optimal transport plan gives simpler flows that are faster to sample (Tong et al., 2024).

Questions to Think About

  • How does the "earth mover" picture, with distributions as piles of earth, map onto couplings and costs, and where does the picture break down?
  • Why does entropic regularization make optimal transport fast and differentiable, and what happens to the transport plan as ε grows?

Core Math

Key Equation
Wp(μ,ν)=(inf⁡γ∈Γ(μ,ν)∫∥x−y∥p dγ(x,y))1/pW_p(\mu, \nu) = \left( \inf_{\gamma \in \Gamma(\mu, \nu)} \int \|x - y\|^p \, d\gamma(x, y) \right)^{1/p}

Optimal transport finds the cheapest way to move probability mass from a distribution μ\mu to a distribution ν\nu:

Wp(μ,ν)=(inf⁡γ∈Γ(μ,ν)∫∥x−y∥p dγ(x,y))1/pW_p(\mu, \nu) = \left( \inf_{\gamma \in \Gamma(\mu, \nu)} \int \|x - y\|^p \, d\gamma(x, y) \right)^{1/p}

where Γ(μ,ν)\Gamma(\mu, \nu) is the set of joint distributions (couplings) with marginals μ\mu and ν\nu. A coupling γ(x,y)\gamma(x, y) says how much mass goes from xx to yy.

Kantorovich–Rubinstein duality (for W1W_1) turns the problem into a maximization over 1-Lipschitz functions ff:

W1(μ,ν)=sup⁡∥f∥L≤1Ex∼μ[f(x)]−Ey∼ν[f(y)]W_1(\mu, \nu) = \sup_{\|f\|_L \leq 1} \mathbb{E}_{x \sim \mu}[f(x)] - \mathbb{E}_{y \sim \nu}[f(y)]

This is the form the Wasserstein GAN critic approximates (Arjovsky et al., 2017).

Brenier's theorem. For the squared Euclidean cost (p=2p = 2) and an absolutely continuous μ\mu, the optimal coupling is given by a map T=∇ϕT = \nabla \phi for some convex function ϕ\phi.

Entropic regularization. Adding −εH(γ)-\varepsilon H(\gamma) to the transport cost gives a strictly convex problem that the Sinkhorn algorithm solves by alternately rescaling rows and columns, which is fast on GPUs and differentiable (Cuturi, 2013).

Key Papers

Computational Optimal Transport

Peyré & Cuturi2019Foundations and Trends in Machine Learning
Read paper →

Sinkhorn Distances: Lightspeed Computation of Optimal Transport

Cuturi2013NeurIPS
Read paper →

Wasserstein GAN

Arjovsky, Chintala & Bottou2017ICML
Read paper →

Improving and generalizing flow-based generative models with minibatch optimal transport

Tong et al.2024TMLR
Read paper →

Connections

Prerequisites

Learning TheoryDiffusionGANs