1
$\begingroup$

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.$

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.