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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_{k,x} : y \mapsto g(y) + k|x - y|} is continuous everywhere and differentiable everywhere except for when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_k(x)} : find the critical points of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_{k,x}} and take the infimum of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_{k,x}} evaluated at the critical points. One of these values will always be the original function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} evaluated at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , since this corresponds to the critical point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = x} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_{k,x}} .

• Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) := x^2} . Then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_k(x) = \min \left\{ x^2 , \frac{k^2}{2} + k \left| x \pm \frac{k}{2} \right| \right\}.}

Plot of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) = x^2} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_k(x)} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 0, 1, 2, 3} .

Approximating Lower Semicontinuous Functions by Lipschitz Functions

Proposition. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (X,d)} be a Polish space and let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g : X \to (-\infty,+\infty]} .

• If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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})$ is finite in the limit is for $d(x,y_{k})$ to go to zero. 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.