Existence of optimal coupling in optimal transport

Question

Let $P,Q$ be any two distributions over a space $\mathcal{X}$ and let $\mathcal{M}(P,Q)$ be the set of all couplings of $P$ and $Q.$ For a given metric $d$ over $\mathcal{X},$ the optimal transport cost is:

$$\min_{(X,Y)\sim M\in \mathcal{M}(P,Q)} \mathbb{E}d(X,Y)~.$$

Is an optimal coupling guaranteed to exist for $P,Q$ being distributions over any general space $\mathcal{X}$?

This quantity frequently appears in the book Concentration Inequalities by Boucheron, Lugosi, Massart (Chapter: The Transportation Method). Yet, no argument is provided as to why we have $\min$ in the optimal transport formula instead of $\inf.$

Answer 1

You can formulate this as the problem of minimizing a continuous function on a compact space, at least when $\mathcal{X}$ is Polish (separable and completely metrizable) and the metric $d$ bounded.

Let $\Delta(\mathcal{X})$ be the set of probability measures on $\mathcal{X}$ endowed with the usual topology of weak convergence of measures, the weakest topology that makes the function $\mu\mapsto\int f~\text{d}\mu$ continuous for each bounded continuous real-valued function $f$ on $\mathcal{X}$. This topology is again Polish. By Prohorov's Theorem, a subset $S$ of $\Delta(\mathcal{X})$ is relatively compact if and only if for every $\epsilon>0$ there is a compact set $K\subseteq\mathcal{X}$ such that $\mu(K)>1-\epsilon$ for each $\mu\in S$. Note that the product of two Polish spaces is again Polish.

Fix $P,Q\in\Delta(\mathcal{X})$. Since $d:\mathcal{X}\times \mathcal{X}\to\mathbb{R}$ is bounded and continuous, it suffices to show that the set $\mathcal{T}$ of probability measures in $\Delta(\mathcal{X}\times\mathcal{X})$ with marginals $P$ and $Q$, respectively, is compact.

Let $\pi_1:\mathcal{X}\times\mathcal{X}\to \mathcal{X}$ and $\pi_2:\mathcal{X}\times\mathcal{X}\to \mathcal{X}$ be the projections onto the first and second factor respectively. For $i=1,2$, let $\hat{\pi_i}:\Delta(\mathcal{X\times\mathcal{X}})\to\Delta(\mathcal{X})$ be given by $\hat{\pi}(\mu)=\mu\circ\pi_i^{-1}$. The resulting functions are easily seen to be continuous by a change of variable argument. Now $$\mathcal{T}=\hat{\pi}_1^{-1}\big(\{P\}\big)\cap\hat{\pi}_2^{-1}\big(\{Q\}\big)$$ is closed, so it remains to show that $\mathcal{T}$ is relatively compact.

Let $\epsilon>0$. Take a compact set $K_P\subseteq\mathcal{X}$ such that $P(K_P)>1-\epsilon/2$ and a compact set $K_Q\subseteq\mathcal{X}$ such that $Q(K_Q)>1-\epsilon/2$. Then for every measure $\mu\in\mathcal{T}$ we must have by the marginal condition that $\mu(K_P\times K_Q)>1-\epsilon$, so $\mathcal{T}$ is relatively compact.

A good source for the mathematical tools used in arguments like this is the book "Convergence of Probability Measures" by Billingsley.