# Optimal Transport: how is this transport map Borel measurable?

I'm reading Theorem 1.17. and its proof at page 14 of Santambrogio's Optimal transport for applied mathematicians. The content is not hard but a little bit long (because of related detail). Please save your time by scrolling down to Theorem 1.17. if you are familiar with optimal transport.

Let $$X=Y=\Omega$$ be a compact subset of $$\mathbb{R}^d$$. Let the cost function $$c:X \times Y \to [0, \infty)$$ be of the form $$c(x, y)=h(x-y)$$ for a strictly convex function $$h: \mathbb R^d \to [0, \infty)$$. By Kantorovich duality, there exist an optimal transport plan $$\gamma$$ and a Kantorovich potential $$\varphi:X \to \mathbb R \cup \{-\infty\}$$ such that $$\varphi(x)+\varphi^c(y) \leq c(x, y) \text { on } \Omega \times \Omega \text { and } \varphi(x)+\varphi^c(y)=c(x, y) \text { on } \operatorname{spt}(\gamma) .$$

Here $$\varphi^c:Y \to \mathbb R \cup \{-\infty\}$$ is the $$c$$-conjugate of $$\varphi$$ and $$\operatorname{spt}(\gamma)$$ the support of $$\gamma$$. Because $$c$$ is Lipschitz, $$\varphi, \varphi^c$$ are real-valued and Lipschitz. Let us fix a point $$\left(x_0, y_0\right) \in \operatorname{spt}(\gamma)$$. One may deduce from the previous computations that $$x \mapsto \varphi(x)-c\left(x, y_0\right) \quad \text { is minimal at } x=x_0.$$

If $$\varphi$$ and $$h$$ are differentiable at $$x_0$$ and $$x_0-y_0$$, respectively, and $$x_0 \notin \partial \Omega$$, one gets $$\nabla \varphi\left(x_0\right)=\nabla h\left(x_0-y_0\right)$$. This works if the function $$h$$ is differentiable, if it is not we shall write $$\nabla \varphi\left(x_0\right) \in \partial h\left(x_0-y_0\right)$$ (using the subdifferential of $$h$$, see Box 1.12). For a strictly convex function $$h$$ one may inverse the relation passing to $$(\nabla h)^{-1}$$ thus getting $$x_0-y_0=(\nabla h)^{-1}\left(\nabla \varphi\left(x_0\right)\right) .$$

Notice that the expression $$(\nabla h)^{-1}$$ makes sense for strictly convex functions $$h$$, thanks to the considerations on the invertibility of $$\partial h$$ in Box 1.12.

This formula gives the solution to the transport problem with this cost, provided $$\varphi$$ is differentiable a.e. with respect to $$\mu$$. This is usually guaranteed by requiring $$\mu$$ to be absolutely continuous with respect to the Lebesgue measure, and using the fact that $$\varphi$$ may be proven to be Lipschitz. Then, one may use the previous computation to deduce that, for every $$x_0$$, the point $$y_0$$ (whenever it exists) such that $$\left(x_0, y_0\right) \in \operatorname{spt}(\gamma)$$ is unique (i.e. $$\gamma$$ is of the form $$\gamma_{\mathrm{T}}:=(\mathrm{id}, \mathrm{T})_{\#} \mu$$ where $$\mathrm{T}\left(x_0\right)=y_0$$). Moreover, this also gives uniqueness of the optimal transport plan and of the gradient of the Kantorovich potential.

Box 1.12.

• For every convex function $$f: \mathbb{R}^d \rightarrow \mathbb{R} \cup\{+\infty\}$$ we define its subdifferential at $$x$$ as the set $$\partial f(x)=\left\{p \in \mathbb{R}^d: f(y) \geq f(x)+p \cdot(y-x) \forall y \in \mathbb{R}^d\right\}.$$ It is possible to prove that $$\partial f(x)$$ is never empty if $$x$$ lies in the interior of the set $$\{f<+\infty\}$$. At every point where the function $$f$$ is differentiable, then $$\partial f$$ reduces to the singleton $$\{\nabla f\}$$.
• If $$h$$ is strictly convex then $$\partial h$$, which is a multi-valued map, can be inverted and is uni-valued, thus getting a map $$(\partial h)^{-1}$$, that should use in the statement of Theorem $$1.17$$ instead of $$(\nabla h)^{-1}$$.

We may summarize everything in the following theorem:

Theorem 1.17. Given $$\mu$$ and $$v$$ probability measures on a compact domain $$\Omega \subset \mathbb{R}^d$$ there exists an optimal transport plan $$\gamma$$ for the cost $$c(x, y)=h(x-y)$$ with h strictly convex. It is unique and of the form (id, $$T)_{\#} \mu$$, provided $$\mu$$ is absolutely continuous and $$\partial \Omega$$ is negligible. Moreover, there exists a Kantorovich potential $$\varphi$$, and $$\mathrm{T}$$ and the potentials $$\varphi$$ are linked by $$\mathrm{T}(x) = x-(\nabla h)^{-1}(\nabla \varphi(x)) .$$

Proof.

• The previous theorems give the existence of an optimal $$\gamma$$ and an optimal $$\varphi$$. The previous considerations show that if we take a point $$\left(x_0, y_0\right) \in \operatorname{spt}(\gamma)$$ where $$x_0 \notin \partial \Omega$$ and $$\nabla \varphi\left(x_0\right)$$ exists, then necessarily we have $$y_0=x_0-(\nabla h)^{-1}\left(\nabla \varphi\left(x_0\right)\right)$$.

• The points $$x_0$$ on the boundary are negligible by assumption. The points where the differentiability fails are Lebesgue-negligible by Rademacher's theorem. Indeed, $$\varphi$$ shares the same modulus of continuity of $$c$$, which is a Lipschitz function on $$\Omega \times \Omega$$ since $$h$$ is locally Lipschitz continuous and $$\Omega$$ is bounded. Hence, $$\varphi$$ is also Lipschitz.

• From the absolute continuity assumption on $$\mu$$, these two sets of "bad" points (the boundary and the nondifferentiability points of $$\varphi$$ ) are $$\mu$$-negligible as well. This shows at the same time that every optimal transport plan is induced by a transport map and that this transport map is $$x \mapsto x-(\nabla h)^{-1}(\nabla \varphi(x))$$. Hence, it is uniquely determined (since the potential $$\varphi$$ does not depend on $$\gamma$$ ). As a consequence, we also have uniqueness of the optimal $$\gamma$$.

My question I'm fine with the fact that there is a $$\mu$$-null Borel subset $$N$$ of $$\Omega$$ such that the gradient $$\nabla \varphi: N^c \to \mathbb R^d$$ is Borel measurable. Of course, the transport map $$T$$ must be Borel measurable. However, it's possible that a non-measurable map has a measurable graph.

Could you elaborate on how the inverse $$(\nabla h)^{-1}$$ is Borel measurable?

• (i) What do you mean by "$\partial \Omega$ is negligible"? (ii) On what set is $h$ defined so that it be "strictly convex"? (iii) How, in detail, is $(\nabla h)^{-1}$ defined? (I don't have access to the book you are reading.) Dec 20, 2022 at 18:51
• @IosifPinelis You can download the PDF of the book from here. (i) $\partial \Omega$ is negligible means that $\mu (\partial \Omega) = 0$. (ii) $h:\mathbb R^d\to [0, \infty)$. (iii) This is the essential part of my confusion... Dec 20, 2022 at 19:53
• @IosifPinelis Please see my update. Dec 20, 2022 at 20:12
• Can you please summarize in one place all the conditions on $h$, and the exact definition of $\nabla h$ which has been omitted? Also, what was in Box 1.12? Dec 20, 2022 at 23:25
• @NateEldredge Please see my update. Dec 21, 2022 at 0:54


Consider the set $$S:=2^{\R^d}$$ of all subsets of $$\R^d$$ endowed with the Hausdorff distance $$d_H$$. As usual, let $$\p h(x)$$ denote the subdifferential of the function $$h$$ at a point $$x\in\R^d$$; we will identify $$(\R^d)^*$$ with $$\R^d$$. Thus, we have the map $$\begin{equation*} \R^d\ni x\mapsto\p h(x)\in R, \tag{1}\label{1} \end{equation*}$$ where $$R:=\{\p h(x)\colon x\in\R^d\}\subseteq S$$.

It suffices to prove

Proposition 1: The map $$\p h$$ in \eqref{1} is invertible and its inverse is continuous.

Proof: Using horizontal shifts, without loss of generality (wlog) it is enough to show that, for any sequence $$(x_k)$$ in $$\R^k$$,
$$\begin{equation*} \text{if d_H(\p h(x_k),\p h(0))\to0 then x_k\to0.} \tag{2}\label{2} \end{equation*}$$

By subtracting an appropriate affine function from $$h$$, wlog we may and will assume that $$\begin{equation*} h(0)=0\quad\text{and}\quad 0\in\p h(0),\quad\text{so that}\quad h\ge0. \end{equation*}$$

To obtain a contradiction, suppose that \eqref{2} is false. Then there exist a real $$\ep>0$$, a sequence $$(x_k)$$ in $$\R^d$$, and a sequence $$(a_k)$$ in $$\R^d$$ such that for all $$k$$ $$\begin{equation*} a_k\in\p h(x_k)\quad\text{and}\quad |x_k|\ge\ep, \quad\text{whereas}\quad a_k\to0. \end{equation*}$$

Since $$h$$ is convex and $$a_k\in\p h(x_k)$$, for all $$k$$ we have $$0=h(0)\ge h(x_k)+a_k\cdot(0-x_k)$$ and hence $$\begin{equation*} 0\le h(x_k)\le a_k\cdot x_k, \tag{3}\label{3} \end{equation*}$$ with $$\cdot$$ standing for the dot product. Let also $$|\cdot|$$ denote the Euclidean norm. Letting now $$\begin{equation*} y_k:=\frac\ep{|x_k|}\,x_k=\frac\ep{|x_k|}\,x_k+\Big(1-\frac\ep{|x_k|}\Big)0 \end{equation*}$$ we have $$|y_k|=\ep$$ and, using the convexity of $$h$$ again and looking back at \eqref{3}, we get $$\begin{equation*} 0\le h(y_k)\le\frac\ep{|x_k|}\,h(x_k) \le\frac\ep{|x_k|}\,a_k\cdot x_k =a_k\cdot y_k\to0, \end{equation*}$$ so that $$h(y_k)\to0$$. Passing to subsequences, wlog we have $$y_k\to y$$ for some $$y\in\R^d$$ with $$|y|=\ep$$, so that $$y\ne0$$.

On the other hand, the convex function $$h\colon\R^d\to\R$$ is necessarily continuous. So, $$h(y)=\lim_k h(y_k)=0$$. So, for all $$t\in[0,1]$$, once again by the convexity of $$h$$, we have $$0\le h(ty)\le(1-t)h(0)+th(y)=0$$, so that $$h(ty)=0$$ for all $$t\in[0,1]$$, which contradicts the strict convexity of $$h$$. $$\quad\Box$$

• Thank you so much for your detailed answer. It seems we have $|y_k| =|\frac\varepsilon {|x_k|}\,x_k| = \varepsilon$ without using the convexity of $h$. I'm surprised that you only use the strict convexity of $h$ at the last line of the proof. Dec 21, 2022 at 11:09
• @Akira : Even though that sentence is formally OK, it may be indeed be somewhat misleading; so, I have now rephrased it. As for using the strict convexity only in the last sentence, indeed everything else can be considered preparatory to that. Dec 21, 2022 at 13:51
• I have just realized that your Proposition 1 also implies that $\partial h (x) \cap \partial h (y) \neq \emptyset \iff x = y$. So great! Dec 21, 2022 at 18:46
• @Analyst : This is not true in general. For a counterexample, take $d=1$, $x=0$, $f(t):=|t|+t^2$. Dec 23, 2022 at 18:41
• @Analyst : Thank you, and best wishes to you too! Dec 23, 2022 at 18:55