The Moreau-Yosida Regularization

The Moreau-Yosida regularization is a technique used to approximate lower semicontinuous functions by Lipschitz functions. The main application of this result is to prove Portmanteau's Theorem, which states that integration against a lower semicontinuous and bounded below function is lower semicontinuous with respect to the narrow topology in the space of probability measures.

Definitions

Let $(X,d)$ be a metric space, and let ${\mathcal {P}}(X)$ denotes the collection of probability measures on $X$. $(X,d)$ is said to be a Polish space if it is complete and separable.

A function $g:X\to (-\infty ,+\infty ]$ is said to be proper if it is not identically equal to $+\infty$, that is, if there exists $x\in X$ such that $g(x)<+\infty$. The domain $D(g)$ of $g$ is the set

$D(g):=\{x\in X|g(x)<+\infty \}$.

For a given function $g:X\to (-\infty ,+\infty ]$ and $k\geq 0$, its Moreau-Yosida regularization $g_{k}:X\to [-\infty ,+\infty ]$ is given by

$g_{k}(x):=\inf \limits _{y\in X}\left[g(y)+kd(x,y)\right].$

The distance term $d(x,y)$ may often be raised to a positive exponent. For example, when $X$ is a Hilbert space , $g_{k}$ is taken to be

$g_{k}(x):=\inf \limits _{y\in X}\left[g(y)+{\frac {k}{2}}\|x-y\|^{2}\right].$

The dependence on the parameter $k$ may also be written instead as

$\inf \limits _{y\in X}\left[g(y)+{\frac {1}{\tau }}d(x,y)\right]$

for $\tau \in (0,+\infty )$.

Note that

$g_{k}(x)=\inf \limits _{y\in X}\left[g(y)+kd(x,y)\right]\leq g(x)+kd(x,x)=g(x)$.

Examples

• If $k=0$, then by definition $g_{0}$ is constant and $g_{0}\equiv \inf \limits _{y\in X}g(y)$.
• If $g$ is not proper, then $g_{k}=+\infty$ for all $k\geq 0$.

Take $(X,d):=(\mathbb {R} ,|\cdot |)$. If $g$ is finite-valued and differentiable, we can explicitly write down $g_{k}$. Then for a fixed $x\in \mathbb {R}$, the map $g_{k,x}:y\mapsto g(y)+k|x-y|$ is continuous everywhere and differentiable everywhere except for when $y=x$, where the derivative does not exist due to the absolute value. Thus we can apply standard optimization techniques from Calculus to solve for $g_{k}(x)$: find the critical points of $g_{k,x}$ and take the infimum of $g_{k,x}$ evaluated at the critical points. One of these values will always be the original function $g$ evaluated at $x$, since this corresponds to the critical point $y=x$ for $g_{k,x}$.

• Let $g(x):=x^{2}$. Then

$g_{k}(x)=\min \left\{x^{2},{\frac {k^{2}}{2}}+k\left|x\pm {\frac {k}{2}}\right|\right\}.$

Plot of $g(x)=x^{2}$ and $g_{k}(x)$ for $k=0,1,2,3$.

Approximating Lower Semicontinuous Functions by Lipschitz Functions

Proposition. Let $(X,d)$ be a Polish space and let $g:X\to (-\infty ,+\infty ]$.

• If $g$ is proper and bounded below, so is $g_{k}$. Furthermore, $g_{k}$ is continuous for all $k\geq 0$.
• If, in addition, $g$ is lower semicontinuous, then $g_{k}(x)\nearrow g(x)$ for all $x\in X$.
• In this case, $g_{k}\wedge k:=\min(g_{k},k)$ is continuous and bounded and $g_{k}(x)\wedge k\nearrow g(x)$ for all $x\in X$.

Plot of $g(x)=x^{2}$ and $g_{k}(x)\wedge k$ for $k=0,3,6,9$.

Proof.

• Since $g$ is proper, there exists $y_{0}\in X$ such that $g(y_{0})<+\infty$. Then for any $x\in X$

$-\infty <\inf \limits _{y\in Y}g(y)\leq g_{k}(x)\leq g(y_{0})+kd(x,y_{0})<+\infty .$

Thus $g_{k}$ is proper and bounded below. Next, for a fixed $y\in X$, let $h_{k,y}(x):=g(y)+d(x,y)$. Then as

$h_{k,y}(x_{1})-h_{k,y}(x_{2})=kd(x_{1},y)-kd(x_{2},y)\leq kd(x_{1},x_{2})$ ,

the family $\{h_{k,y}\}_{y\in X}$ is uniformly Lipschitz and hence equicontinuous. Thus $g_{k}=\inf \limits _{y\in Y}h_{k,y}$ is Lipschitz continuous.

• Suppose that $g$ is also lower semicontinuous. Note that for all $k_{1}\leq k_{2}$, $g_{k_{1}}(x)\leq g_{k_{2}}(x)\leq g(x)$. Thus it suffices to show that $\liminf \limits _{k\to \infty }g_{k}(x)\geq g(x)$. This inequality is automatically satisfied when the left hand side is infinite, so without loss of generality assume that $\liminf \limits _{k\to \infty }g_{k}(x)<+\infty$. By definition of infimum, for each $k\in \mathbb {N}$ there exists $y_{k}\in X$ such that

$g(y_{k})+kd(x,y_{k})\leq g_{k}(x)+{\frac {1}{k}}$.

Then

$+\infty >\liminf \limits _{k\to \infty }g_{k}(x)\geq \liminf \limits _{k\to \infty }\left[g(y_{k})+kd(x,y_{k})\right].$

$g(y_{k})$ is bounded below by assumption, while the only way $kd(x,y_{k})$ to be finite in the limit is for $d(x,y_{k})$ to vanish in the limit. Thus $y_{k}$ converges to $x$ in $X$, and by lower semicontinuity of $g$,

$\liminf \limits _{k\to \infty }g_{k}(x)\geq \liminf \limits _{k\to \infty }\left[g(y_{k})+kd(x,y_{k})\right]\geq g(x)$.

• By definition, $g_{k}\wedge k\in C_{b}(X)$. Since $g_{k}(x)\nearrow g(x)$ for all $x\in X$, $g_{k}(x)\wedge k\nearrow g(x)$ for all $x\in X$.

Portmanteau Theorem

Theorem (Portmanteau). Let $(X,d)$ be a Polish space, and let $g:X\to (-\infty ,+\infty ]$ be lower semicontinuous and bounded below. Then the functional $\mu \mapsto \int _{X}g\,\mathrm {d} \mu$ is lower semicontinuous with respect to narrow convergence in ${\mathcal {P}}(X)$, that is

$\mu _{n}\to \mu {\text{ narrowly}}\Longrightarrow \liminf \limits _{n\to \infty }\int _{X}g_{n}\,\mathrm {d} \mu \geq \int _{X}g\,\mathrm {d} \mu$.

Proof. By the Moreau-Yosida approximation, for all $k\geq 0$,

$\liminf \limits _{n\to \infty }\int _{X}g\,\mathrm {d} \mu _{n}\geq \liminf \limits _{n\to \infty }\int _{X}g_{k}\wedge k\,\mathrm {d} \mu _{n}=\int _{X}g_{k}\wedge k\,\mathrm {d} \mu$.

Taking $k\to \infty$, Fatou's Lemma ensures that

$\liminf \limits _{n\to \infty }\int _{X}g\,\mathrm {d} \mu _{n}\geq \liminf \limits _{k\to \infty }\int _{X}g_{k}\wedge k\,\mathrm {d} \mu \geq \int _{X}g\,\mathrm {d} \mu$.

The Mysterious Etymology of Portmanteau

The curious epithet attached to the above theorem is due to Billingsley , with a citation to a Jean-Pierre Portmanteau's Espoir pour l'ensemble vide? published in Annales de l'Université de Felletin in 1915. This is believed to be a fictional citation made as a play on words .

• The publication date is far too early; Kolmogorov's probability axioms were published in 1933.
• Felletin is a small town in central France with no university, and there is no record of a Jean-Pierre Portmanteau aside from this citation.
• "Espoir pour l'ensemble vide" translates to "hope for the empty set" (translation was by Google, please confirm or amend if you speak French!)

Generalizations

The Moreau-Yosida regularization is a specific case of a type of convolution, and many of the above results follow from this generalization. This material is adapted from Bauschke-Combettes Ch 12 , where the setting is over a Hilbert space instead of a more general Polish space.

Let ${\mathcal {H}}$ be a Hilbert space, and let $f,g:{\mathcal {H}}\to (-\infty ,+\infty ]$. The informal convolution or epi-sum $f\,\square \,g:{\mathcal {H}}\to [-\infty ,+\infty ]$ of $f$ and $g$ is

$(f\,\square \,g)(x):=\inf \limits _{y\in {\mathcal {H}}}\left[f(y)+g(x-y)\right]$.

$f\,\square \,g$ is said to be exact at a point $x\in {\mathcal {H}}$ if this infimum is attained. $f\,\square \,g$ is said to be exact if it is exact at every point of its domain, and in this case it is denoted by $f\,{\dot {\square }}\,g$.

Remark. Bauschke-Combettes uses a box with a dot in the middle for $f\,\square \,g$ to be exact. Due to technical difficulties, we will use $f\,{\dot {\square }}\,g$ instead.

For an example, let $A,B\subseteq {\mathcal {H}}$ be nonempty. Then $\chi _{A}\,\square \,\chi _{B}$ is exact, and $\chi _{A}\,{\dot {\square }}\,\chi _{B}=\chi _{A+B}$.

Proposition. Let $g:{\mathcal {H}}\to (-\infty ,+\infty ]$ be proper, $p\in [1,+\infty )$, and for $k\in (0,+\infty )$, let $g_{k}:{\mathcal {H}}\to (-\infty ,+\infty ]$ be given by

$g_{k}:=g\,\square \,\left({\frac {k}{p}}\|\cdot \|^{p}\right)$.

Then the following hold for all $k\in (0,+\infty )$ and $x\in {\mathcal {H}}$:

• $D(g_{k})={\mathcal {H}}$,
• for $0<k_{1}\leq k_{2}<+\infty$, $\inf \limits _{y\in {\mathcal {H}}}g(y)\leq g_{k_{1}}(x)\leq g_{k_{2}}(x)\leq g(x)$,
• $\inf \limits _{x\in {\mathcal {H}}}g_{k}(x)=\inf \limits _{x\in {\mathcal {H}}}g(x)$,
• $g_{k}(x)\searrow \inf \limits _{y\in {\mathcal {H}}}g(y)$ as $k\downarrow 0$, and
• $g_{k}$ is bounded above on every ball in ${\mathcal {H}}$.

Remark. The convention given above differs slightly from Bauschke-Combettes to fit the convention in this article. The Moreau-Yosida regularization is the special case where $p=1$, and is called the Pasch-Hausdorff Envelope in Bauschke-Combettes.

Proposition. Let $g:{\mathcal {H}}\to (-\infty ,+\infty ]$ be lower semicontinuous and convex, let $k\in (0,+\infty )$, and let $p\in (1,+\infty )$. Then the infimal convolution $g_{k}$ is convex, proper, continuous, and exact. Moreover, for every $x\in {\mathcal {H}}$, the infimum

$g_{k}(x)=\inf \limits _{y\in {\mathcal {H}}}\left[g(y)+{\frac {k}{p}}\|x-y\|^{p}\right]$

is uniquely attained.