Proof of Existence, Penalty Bounds and the Least Penalty at a Maximiser of the Wasserstein-Doubled Difference

Each result cited is universally quantified over the data in its own statement and is applied here to the data named in the statement of the lemma. The real line carries the metric $d_{\mathbb{R}}$ with $d_{\mathbb{R}}(s,t)=|s-t|$ of The Absolute Value Metric on the Real Line. Throughout, by Basic Properties of a Wasserstein-Coercive Penalty Pair §envelopes,

The compatibility of the order with addition and its transitivity, antisymmetry and totality are axioms of Ordered Field; mixed transitivity is claim 2 of Elementary Order Arithmetic in an Ordered Field. The claims are proved in the order 2, 1, 3, 4; claim 1 uses claim 2.

Monotonicity of $\iota$. For $m,n\in\mathbb{N}$ with $m\le n$ one has $\iota(m)\le\iota(n)$. Indeed, by the trichotomy of the order of $\mathbb{N}$ (claim 3 of Properties of the Order on the Natural Numbers) either $m=n$, and then $\iota(m)=\iota(n)$, or $m<n$, and then $\iota(m)<\iota(n)$ by claim 6 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field; in both cases $\iota(m)\le\iota(n)$.

A bound valid on all of $\mathcal{D}\times\mathcal{D}$. Let $\alpha$ be positive and $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$. The square $W_{2}(\mu,\nu)^{2}$ is nonnegative by Nonnegativity of Squares in an Ordered Field, so $0\le\tfrac{\alpha}{2}W_{2}(\mu,\nu)^{2}$ by claim 5 of Elementary Arithmetic in an Ordered Field applied with the nonnegative multiplier $\tfrac{\alpha}{2}$ and $x\cdot0=0$ (claim 1 of Zero Products and Elementary Identities in a Field). From $u(\mu)\le b$ and $b'\le v(\nu)$, the latter equivalent to $-v(\nu)\le-b'$ by claim 3 of Elementary Arithmetic in an Ordered Field used in both directions, we obtain

Also $W_{2}(\mu_{0},\mu_{0})=0$ by the metric axioms of Metric Space, so $\tfrac{\alpha}{2}W_{2}(\mu_{0},\mu_{0})^{2}=0$ and

the collection of the two equal penalty terms using the distributivity of Field.

Claim 2. Let $\alpha$ be positive, let $\eta$ be nonnegative and let $(\hat{\mu},\hat{\nu})\in\mathcal{D}\times\mathcal{D}$ satisfy $\Psi_{\alpha}(\mu_{0},\mu_{0})-\eta\le\Psi_{\alpha}(\hat{\mu},\hat{\nu})$. Combining this with $(\dagger)$ at $(\hat{\mu},\hat{\nu})$ and with $(\ddagger)$ gives

and adding $\delta\mathcal{E}(\hat{\mu})+\delta\mathcal{E}(\hat{\nu})-u(\mu_{0})+v(\mu_{0})+2\delta\mathcal{E}(\mu_{0})+\eta$ to both sides yields the displayed inequality of claim 2,

Since $e_{0}\le\mathcal{E}(\hat{\nu})$, multiplying by the nonnegative $\delta$ (claim 5 of Elementary Arithmetic in an Ordered Field) gives $\delta e_{0}\le\delta\mathcal{E}(\hat{\nu})$, whence $\delta\mathcal{E}(\hat{\mu})\le K_{\eta}-\delta e_{0}$. Multiplying by the positive $\delta^{-1}$ (claim 7 of Elementary Order Arithmetic in an Ordered Field and claim 5 of Elementary Arithmetic in an Ordered Field) and using $\delta^{-1}\delta=1$ gives

the middle identity by the distributivity and commutativity of Field. Interchanging the roles of $\hat{\mu}$ and $\hat{\nu}$ and using $e_{0}\le\mathcal{E}(\hat{\mu})$ gives $\mathcal{E}(\hat{\nu})\le c_{0}+\delta^{-1}\eta$ in the same way.

Finally, both $\hat{\mu}$ and $\hat{\nu}$ lie in $\mathcal{D}$ and have just been shown to satisfy $\mathcal{E}\le c_{0}+\delta^{-1}\eta$, so Basic Properties of a Wasserstein-Coercive Penalty Pair §moment, read at the level $c=c_{0}+\delta^{-1}\eta$, gives $M_{2}(\hat{\mu})\le R$ and $M_{2}(\hat{\nu})\le R$ for the $R$ it provides at that level. The level is determined by $b,b',u(\mu_{0}),v(\mu_{0}),\mathcal{E}(\mu_{0}),\delta,e_{0}$ and $\eta$ alone, so neither it nor $R$ depends on $\alpha$. This completes claim 2.

Claim 1. Let $\alpha\in\mathbb{R}$ be positive. By $(\dagger)$ and $e_{0}\le\mathcal{E}$ on $\mathcal{D}$, every value of $\Psi_{\alpha}$ satisfies $\Psi_{\alpha}(\mu,\nu)\le b-b'-2\delta e_{0}$, so the set $\{\Psi_{\alpha}(\mu,\nu):(\mu,\nu)\in\mathcal{D}\times\mathcal{D}\}$, which is nonempty because $\mathcal{D}$ is, is bounded above and has a supremum $M\in\mathbb{R}$ by that clause.

For $n\in\mathbb{N}$ the inverse $\iota(n)^{-1}$ exists and is positive by claim 3 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field. Moreover $1\le n$ by claim 4 of Properties of the Order on the Natural Numbers, so $\iota(1)\le\iota(n)$ by the monotonicity of $\iota$ established above, and $\iota(1)=1$ by claim 1 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field; multiplying $1\le\iota(n)$ by the nonnegative $\iota(n)^{-1}$ (claim 5 of Elementary Arithmetic in an Ordered Field) gives

By claim 3 of Approximation Property of the Supremum and the Infimum in $\mathbb{R}$, applied with the positive $\iota(n)^{-1}$, the set of pairs $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$ with $M-\iota(n)^{-1}<\Psi_{\alpha}(\mu,\nu)$ is nonempty for every $n\in\mathbb{N}$, so Axiom of Countable Choice provides a sequence of pairs $(\mu_{n},\nu_{n})\in\mathcal{D}\times\mathcal{D}$ with

the second inequality because $M$ is an upper bound of the set of values. As $\Psi_{\alpha}(\mu_{0},\mu_{0})\le M$ and $\iota(n)^{-1}\le1$, we get $\Psi_{\alpha}(\mu_{0},\mu_{0})-1\le M-\iota(n)^{-1}\le\Psi_{\alpha}(\mu_{n},\nu_{n})$, so claim 2 with $\eta=1$ gives $\mathcal{E}(\mu_{n})\le c_{1}$ and $\mathcal{E}(\nu_{n})\le c_{1}$, where $c_{1}=c_{0}+\delta^{-1}$. Thus both sequences lie in

which is sequentially compact in $(\mathcal{P}_{2}(\mathbb{R}^{d}),W_{2})$ by Wasserstein-Coercive Penalty Pairs §coercive read at the level $c_{1}$.

Hence there are $\hat{\mu}\in K$ and a strictly increasing sequence $(n_{k})_{k\in\mathbb{N}}$ in $\mathbb{N}$ such that $(\mu_{n_{k}})_{k\in\mathbb{N}}$ converges to $\hat{\mu}$ in $(\mathcal{P}_{2}(\mathbb{R}^{d}),W_{2})$; applying sequential compactness once more to the sequence $(\nu_{n_{k}})_{k\in\mathbb{N}}$ in $K$ gives $\hat{\nu}\in K$ and a strictly increasing $(k_{j})_{j\in\mathbb{N}}$ such that $(\nu_{n_{k_{j}}})_{j\in\mathbb{N}}$ converges to $\hat{\nu}$. By A Subsequence of a Convergent Sequence Has the Same Limit, applied to the convergent sequence $(\mu_{n_{k}})_{k\in\mathbb{N}}$ and the indices $(k_{j})_{j\in\mathbb{N}}$, the sequence $(\mu_{n_{k_{j}}})_{j\in\mathbb{N}}$ converges to $\hat{\mu}$. Write $m_{j}=n_{k_{j}}$.

The real sequence $(\Psi_{\alpha}(\mu_{n},\nu_{n}))_{n\in\mathbb{N}}$ converges to $M$ in $(\mathbb{R},d_{\mathbb{R}})$: from the displayed near-maximising inequality, $0\le M-\Psi_{\alpha}(\mu_{n},\nu_{n})\le\iota(n)^{-1}$, so $d_{\mathbb{R}}(\Psi_{\alpha}(\mu_{n},\nu_{n}),M)\le\iota(n)^{-1}$ by claim 6 of Properties of the Absolute Value in an Ordered Field, applied to $x=\Psi_{\alpha}(\mu_{n},\nu_{n})-M$ and $c=\iota(n)^{-1}$, the required bounds $-\iota(n)^{-1}\le x$ and $x\le0\le\iota(n)^{-1}$ being claim 3 of Elementary Arithmetic in an Ordered Field applied to the displayed inequalities. Given a positive $\varepsilon'$, claim 2 of The Archimedean Property of the Real Numbers provides $N\in\mathbb{N}$ with $1<\iota(N)\varepsilon'$, whence for $N\le n$ one has $\iota(N)\le\iota(n)$ by the monotonicity of $\iota$ established above, then $1<\iota(n)\varepsilon'$ and, multiplying by the positive $\iota(n)^{-1}$ (claim 10 of Elementary Order Arithmetic in an Ordered Field), $\iota(n)^{-1}<\varepsilon'$. Applying A Subsequence of a Convergent Sequence Has the Same Limit twice, the sequence $(\Psi_{\alpha}(\mu_{m_{j}},\nu_{m_{j}}))_{j\in\mathbb{N}}$ converges to $M$ as well.

The five estimates. Let $\varepsilon\in\mathbb{R}$ be positive.

Since $u$ is upper semicontinuous at $\hat{\mu}$ relative to $\mathcal{P}_{2}(\mathbb{R}^{d})$, that definition applied with the positive $\varepsilon$ provides a positive $r_{1}$ such that $u(\sigma)<u(\hat{\mu})+\varepsilon$ for every $\sigma\in\mathcal{P}_{2}(\mathbb{R}^{d})$ with $W_{2}(\hat{\mu},\sigma)<r_{1}$. Since $v$ is lower semicontinuous at $\hat{\nu}$ relative to $\mathcal{P}_{2}(\mathbb{R}^{d})$, that definition applied with the positive $\varepsilon$ provides a positive $r_{2}$ such that $v(\hat{\nu})-\varepsilon<v(\sigma)$, equivalently $-v(\sigma)<-v(\hat{\nu})+\varepsilon$ by claim 3 of Elementary Arithmetic in an Ordered Field used in both directions, for every $\sigma\in\mathcal{P}_{2}(\mathbb{R}^{d})$ with $W_{2}(\hat{\nu},\sigma)<r_{2}$. No continuity of $u$ or of $v$ is used.

By Basic Properties of a Wasserstein-Coercive Penalty Pair §lsc and Lower Semicontinuous Function on a Subset of a Metric Space, applied at $\hat{\mu}$ with the positive $\delta^{-1}\varepsilon$, there is a positive $r_{3}$ such that $\mathcal{E}(\hat{\mu})-\delta^{-1}\varepsilon<\mathcal{E}(\sigma)$ for every $\sigma\in\mathcal{D}$ with $W_{2}(\hat{\mu},\sigma)<r_{3}$; multiplying by the positive $\delta$ (claim 10 of Elementary Order Arithmetic in an Ordered Field) and using $\delta\delta^{-1}=1$ gives $\delta\mathcal{E}(\hat{\mu})-\varepsilon<\delta\mathcal{E}(\sigma)$, that is, $-\delta\mathcal{E}(\sigma)<-\delta\mathcal{E}(\hat{\mu})+\varepsilon$. In the same way there is a positive $r_{4}$ with $-\delta\mathcal{E}(\sigma)<-\delta\mathcal{E}(\hat{\nu})+\varepsilon$ for every $\sigma\in\mathcal{D}$ with $W_{2}(\hat{\nu},\sigma)<r_{4}$.

For the last estimate write $s=W_{2}(\hat{\mu},\hat{\nu})$, a nonnegative real number, and put

which is positive because $\alpha$ and $1+s$ are positive (for the latter, $0<1\le1+s$) and by claims 5 and 7 of Elementary Order Arithmetic in an Ordered Field. Let $\sigma,\tau\in\mathcal{P}_{2}(\mathbb{R}^{d})$ satisfy $W_{2}(\hat{\mu},\sigma)<\varepsilon_{0}$ and $W_{2}(\hat{\nu},\tau)<\varepsilon_{0}$. The triangle inequality and the symmetry of $W_{2}$ (metric axioms of Metric Space), used twice, give $s\le W_{2}(\hat{\mu},\sigma)+W_{2}(\sigma,\tau)+W_{2}(\tau,\hat{\nu})$ and hence $s-2\varepsilon_{0}<W_{2}(\sigma,\tau)$. We claim that

If $2\varepsilon_{0}\le s$, then $0\le s-2\varepsilon_{0}<W_{2}(\sigma,\tau)$, so $(s-2\varepsilon_{0})^{2}<W_{2}(\sigma,\tau)^{2}$ by claim 1 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, and $(s-2\varepsilon_{0})^{2}=s^{2}-4\varepsilon_{0}s+4\varepsilon_{0}^{2}$ by claim 5 of Zero Products and Elementary Identities in a Field, the last summand being nonnegative by Nonnegativity of Squares in an Ordered Field, so $s^{2}-4\varepsilon_{0}s\le(s-2\varepsilon_{0})^{2}$. If instead $s<2\varepsilon_{0}$, then multiplying by the nonnegative $s$ gives $s^{2}\le2\varepsilon_{0}s$, so $s^{2}-4\varepsilon_{0}s\le-2\varepsilon_{0}s\le0\le W_{2}(\sigma,\tau)^{2}$, the middle step because $2\varepsilon_{0}s$ is nonnegative. Multiplying the claimed inequality by the nonnegative $\tfrac{\alpha}{2}$ and using claim 3 of Elementary Arithmetic in an Ordered Field in both directions gives

Finally $2\alpha\varepsilon_{0}s=\varepsilon\,s\,(1+s)^{-1}\le\varepsilon$, since $s\le1+s$ gives $s(1+s)^{-1}\le1$ on multiplying by the positive $(1+s)^{-1}$, and multiplying that by the nonnegative $\varepsilon$ preserves the inequality; so

Conclusion of claim 1. Let $r$ be the least of $r_{1},r_{2},r_{3},r_{4},\varepsilon_{0}$, obtained by repeated use of claim 9 of Elementary Order Arithmetic in an Ordered Field; it is positive. Since $(\mu_{m_{j}})_{j}$ converges to $\hat{\mu}$ and $(\nu_{m_{j}})_{j}$ converges to $\hat{\nu}$, and since $(\Psi_{\alpha}(\mu_{m_{j}},\nu_{m_{j}}))_{j}$ converges to $M$, given a positive $\varepsilon''$ there are three thresholds in $\mathbb{N}$ beyond which the corresponding distances are smaller than $r$, $r$ and $\varepsilon''$; let $J$ be the largest of the three, which exists by the trichotomy of the order of $\mathbb{N}$ (claim 3 of Properties of the Order on the Natural Numbers), and let $j\in\mathbb{N}$ satisfy $J\le j$. Then $W_{2}(\hat{\mu},\mu_{m_{j}})<r$ and $W_{2}(\hat{\nu},\nu_{m_{j}})<r$, so all five estimates apply with $\sigma=\mu_{m_{j}}$ and $\tau=\nu_{m_{j}}$, and adding them gives

Also $d_{\mathbb{R}}(\Psi_{\alpha}(\mu_{m_{j}},\nu_{m_{j}}),M)<\varepsilon''$, so $M<\Psi_{\alpha}(\mu_{m_{j}},\nu_{m_{j}})+\varepsilon''$ by claim 3 of Properties of the Absolute Value in an Ordered Field, and therefore $M\le\Psi_{\alpha}(\hat{\mu},\hat{\nu})+5\varepsilon+\varepsilon''$. As $\varepsilon''$ was an arbitrary positive number, Comparison of Real Numbers with Arbitrary Positive Slack §slack-above gives $M\le\Psi_{\alpha}(\hat{\mu},\hat{\nu})+5\varepsilon$. Given now an arbitrary positive $\varepsilon'''$, taking $\varepsilon=\varepsilon'''\iota(5)^{-1}$, positive by claims 3 and 7 quoted above, gives $5\varepsilon=\varepsilon'''$ and hence $M\le\Psi_{\alpha}(\hat{\mu},\hat{\nu})+\varepsilon'''$; so $M\le\Psi_{\alpha}(\hat{\mu},\hat{\nu})$ by Comparison of Real Numbers with Arbitrary Positive Slack §slack-above once more.

Since $K\subseteq\mathcal{D}$, the pair $(\hat{\mu},\hat{\nu})$ lies in $\mathcal{D}\times\mathcal{D}$, so $\Psi_{\alpha}(\hat{\mu},\hat{\nu})\le M$ as well. Hence $\Psi_{\alpha}(\mu,\nu)\le M=\Psi_{\alpha}(\hat{\mu},\hat{\nu})$ for every $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$, which is claim 1.

Claim 3. Apply Penalised Suprema: Monotonicity, Near-Maximisers, and Vanishing Penalty along a Doubling Sequence with the nonempty set $Z=\mathcal{D}\times\mathcal{D}$, with $\psi(\mu,\nu)=u^{-}_{\delta}(\mu)-v^{+}_{\delta}(\nu)$ and with $D(\mu,\nu)=\tfrac{1}{2}W_{2}(\mu,\nu)^{2}$. Its hypotheses hold: $\psi$ is bounded above by $b-b'-2\delta e_{0}$, by $(\dagger)$ and $e_{0}\le\mathcal{E}$ on $\mathcal{D}$; $D$ is nonnegative, being a nonnegative multiple of a square (Nonnegativity of Squares in an Ordered Field and claim 5 of Elementary Arithmetic in an Ordered Field); and $D(\mu_{0},\mu_{0})=0$ because $W_{2}(\mu_{0},\mu_{0})=0$ by the metric axioms of Metric Space. For a positive $\beta$ the function $\Psi_{\beta}$ of that lemma has value $\psi(\mu,\nu)-\beta D(\mu,\nu)=\Psi_{\beta}(\mu,\nu)$ here, so the two suprema written $M(\beta)$ agree and the lemma may be quoted with the present notation.

Let $\gamma_{k}=2^{k}\alpha_{0}$ for $k\in\mathbb{N}$, so that $\gamma_{n}=\alpha_{n}$ for every $n\in\mathbb{N}$. Let $\varepsilon\in\mathbb{R}$ be positive. By Penalised Suprema: Monotonicity, Near-Maximisers, and Vanishing Penalty along a Doubling Sequence §vanishing, applied with $\beta_{0}=\alpha_{0}$, the sequence whose $k$-th term is $M(\gamma_{k})-M(\gamma_{k+1})$ converges to $0$, so there is $N\in\mathbb{N}$ such that

using claim 3 of Properties of the Absolute Value in an Ordered Field to pass from the distance to the value. Let $n\in\mathbb{N}$ satisfy $N+1\le n$ and write $k=n-1$, a natural number with $N\le k$ by claim 7 of Properties of the Order on the Natural Numbers; then $\gamma_{k+1}=\gamma_{n}=\alpha_{n}$ and $\gamma_{k}=2^{n-1}\alpha_{0}$, which is $\tfrac{\alpha_{n}}{2}$ because $2^{n}=2\cdot2^{n-1}$.

Since $(\hat{\mu}_{n},\hat{\nu}_{n})$ maximises $\Psi_{\alpha_{n}}$, it satisfies $M(\alpha_{n})-\eta\le\Psi_{\alpha_{n}}(\hat{\mu}_{n},\hat{\nu}_{n})$ for every positive $\eta$, so Penalised Suprema: Monotonicity, Near-Maximisers, and Vanishing Penalty along a Doubling Sequence §near-maximiser, applied at $\beta=\alpha_{n}$, gives

for every positive $\eta$, whence $\tfrac{\alpha_{n}}{4}W_{2}(\hat{\mu}_{n},\hat{\nu}_{n})^{2}\le M(\gamma_{k})-M(\gamma_{k+1})$ by Comparison of Real Numbers with Arbitrary Positive Slack §slack-above. Combining with the displayed bound and multiplying by the positive $4$ gives

The left-hand side is nonnegative, so its distance to $0$ is itself by Absolute Value in an Ordered Field; hence the sequence converges to $0$.

For the last assertion, $2\alpha_{0}\le\alpha_{n}$ for every $n\in\mathbb{N}$, since $2\le2^{n}$ by claim 4 of Properties of the Order on the Natural Numbers and the monotonicity of natural powers of $2$; so multiplying $W_{2}(\hat{\mu}_{n},\hat{\nu}_{n})^{2}\le(2\alpha_{0})^{-1}\alpha_{n}W_{2}(\hat{\mu}_{n},\hat{\nu}_{n})^{2}$ shows that the squares converge to $0$. Given a positive $\varepsilon'$, take $n$ beyond the threshold for the positive $\varepsilon'^{2}$; then $W_{2}(\hat{\mu}_{n},\hat{\nu}_{n})^{2}<\varepsilon'^{2}$, and both $W_{2}(\hat{\mu}_{n},\hat{\nu}_{n})$ and $\varepsilon'$ are nonnegative, so $W_{2}(\hat{\mu}_{n},\hat{\nu}_{n})<\varepsilon'$ by claim 1 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field.

Claim 4. Put $c=\mathcal{E}(\mu_{0})$ and $K=\{\sigma\in\mathcal{D}:\mathcal{E}(\sigma)\le c\}$. Then $\mu_{0}\in K$, and $K$ is sequentially compact in $(\mathcal{P}_{2}(\mathbb{R}^{d}),W_{2})$ by Wasserstein-Coercive Penalty Pairs §coercive, hence compact by A Sequentially Compact Subset of a Metric Space is Compact. The penalty $\mathcal{E}$ is lower semicontinuous on $\mathcal{D}$ relative to $\mathcal{D}$ by Basic Properties of a Wasserstein-Coercive Penalty Pair §lsc, so its restriction to $K\subseteq\mathcal{D}$ is lower semicontinuous relative to $K$ by claim 4 of Semicontinuity and Continuity Under Composition with a Continuous Map. By Semicontinuous Functions Attain Their Extrema on a Compact Set this restriction attains a least value on the nonempty compact set $K$, at some $\mu_{\min}\in K\subseteq\mathcal{D}$; thus $\mathcal{E}(\mu_{\min})\le\mathcal{E}(\sigma)$ for every $\sigma\in K$, and in particular $\mathcal{E}(\mu_{\min})\le\mathcal{E}(\mu_{0})=c$. Let $\sigma\in\mathcal{D}\setminus K$. By the totality of the order (Ordered Field), $\mathcal{E}(\sigma)\le c$ or $c\le\mathcal{E}(\sigma)$; the first is excluded because $\sigma\notin K$, so $c\le\mathcal{E}(\sigma)$, and $c\neq\mathcal{E}(\sigma)$ because equality would give $\mathcal{E}(\sigma)\le c$ by reflexivity, again contradicting $\sigma\notin K$; hence $c<\mathcal{E}(\sigma)$, and $\mathcal{E}(\mu_{\min})\le c<\mathcal{E}(\sigma)$ gives $\mathcal{E}(\mu_{\min})\le\mathcal{E}(\sigma)$ by mixed transitivity. Hence $\mathcal{E}(\mu_{\min})\le\mathcal{E}(\sigma)$ for every $\sigma\in\mathcal{D}$. $\blacksquare$