Stability of Schrödinger Potentials and Convergence of Sinkhorn's Algorithm

Introduction

where $H(\,\cdot\,|\mu\otimes\nu)$ denotes relative entropy with respect to the product of the marginals,

where $\Pi(\ast,\nu)$ is the set of measures on $\mathcal{X}\times\mathcal{Y}$ with second marginal $\nu$ (and arbitrary first marginal), and $\Pi(\mu,\ast)$ is defined analogously. The algorithm alternatingly “fits” the marginals $\mu$ and $\nu$, hence is also called iterative proportional fitting procedure (IPFP). The argmin in (1.2) can be solved explicitly, and then each step of the algorithm only requires an explicit integration against $e^{-c/\varepsilon}$, cf. Section 3. The algorithm dates back as far as and its convergence properties are well studied when the cost $c$ is bounded: the convergence of $\pi_{n}$ to the solution $\pi_{*}$ of (1.1) holds in total variation (and in relative entropy), see , among others. More precisely, relaxed the boundedness condition, but introduced several other conditions, including one (see (B1) in ) that essentially forces $c$ to be bounded from above in one variable and thus excludes quadratic cost with unbounded marginal supports.

One main result of this paper is the convergence $\|\pi_{n}-\pi_{*}\|_{TV}\to 0$ of Sinkhorn’s algorithm (1.2) for quadratic cost and arbitrary subgaussian marginals. More generally, our result (see Corollary 3.2) holds for the continuous cost $c$ and marginals $(\mu,\nu)$ as soon as

A fairly elementary proof of the convergence $\|\pi_{n}-\pi_{*}\|_{TV}\to 0$, following the same idea of weak-star compactness as , was recently given in under the condition that (1.3) holds for some $\beta>\varepsilon^{-1}$. We emphasize that this condition does not capture the regime of principal interest: when approximating the 2-Wasserstein distance and marginals are standard Gaussians, say, this condition forces $\varepsilon>1/2$, but the approximation often requires $\varepsilon$ to be several orders of magnitude smaller (e.g., ). While the case $\beta>\varepsilon^{-1}$ is broadly similar to the case of bounded cost, it seems that the regime $\beta<\varepsilon^{-1}$ requires a fundamentally different line of attack—which brings us to the main theorem of this paper.

In all that follows, we focus on $\varepsilon=1$ in (1.1) for notational simplicity; the general case is easily retrieved by replacing $c$ with $c/\varepsilon$. Assuming that

is finite, there is a unique solution $\pi_{*}\in\Pi(\mu,\nu)$, and $\pi_{*}$ is uniquely characterized within $\Pi(\mu,\nu)$ by having a density of the form

Our aim is to establish stability of the potentials with respect to the marginals. Consider sequences $\mu_{n}\to\mu$ and $\nu_{n}\to\nu$ of marginals converging weakly (i.e., in the topology induced by bounded continuous functions). Denoting by $(f_{n},g_{n})$ associated potentials, we want to state that $(f_{n},g_{n})\to(f,g)$ in a suitable sense. In view of the above characterization, a key step in this endeavor is to establish a form of compactness. In general, it is not straightforward how to formalize the convergence of potentials. E.g., in a computational context, we may be interested in discrete measures $(\mu_{n},\nu_{n})$ approximating a continuous pair $(\mu,\nu)$. Then, these measures are mutually singular and the spaces $L^{p}(\mu_{n})$ and $L^{p}(\mu)$ are not immediately comparable. If $\mu\ll\mu_{n}$ (and similarly for $\nu_{n}$), this issue is milder as convergence in $\mu$-probability yields a natural topology. However, compactness still turns out to be an issue in the regime of interest. If $c$ has high integrability, the weak-star topology in $L^{1}$ can be used, similarly to the arguments for Sinkhorn convergence in . In some cases one can even use the Arzelà–Ascoli theorem (see Appendix B). But in the regime of interest here, where we want to cover quadratic cost and subgaussian marginals, we have not succeeded with off-the-shelf compactness concepts.

Instead, we shall build compactness through an approximation scheme and properties specific to the problem at hand, eventually using compactness of bounded sets in Euclidean space. This construction is the main technical contribution of the paper. It will also allow us to cover the case of mutually singular measures (in fact, focusing on equivalent measures would not result in a substantial simplification). The approximation scheme has the form

The scheme in the diagram also acts as a way to formalize a strong convergence $f_{n}\to f$. It implies convergence in distribution; that is, $(f_{n})_{\#}\mu_{n}\to f_{\#}\mu$ weakly, where $f_{\#}$ denotes the pushforward under $f$. Convergence in distribution is a natural notion given the weak convergence setting, but it is far from strong enough to imply the desired conclusions. If $\mu\ll\mu_{n}$, we show that our scheme implies the convergence in $\mu$-probability (and similarly for $\nu$) under a fairly general condition on the Radon–Nikodym derivatives; cf. Corollary 2.4. This condition is satisfied in particular whenever the marginals convergence in total variation, allowing us to deduce via Scheffé’s lemma a result of its own interest (Corollary 2.6): the optimal couplings are stable in total variation; i.e., for marginals with $\|\mu_{n}-\mu\|_{TV}\to 0$ and $\|\nu_{n}-\nu\|_{TV}\to 0$, the corresponding optimizers satisfy $\|\pi_{n}-\pi_{*}\|_{TV}\to 0$. Returning to the convergence of Sinkhorn’s algorithm, we interpret each iteration of the algorithm as solving an entropic optimal transport problem with changing marginals $(\mu_{n},\nu_{n})$. These marginals converge in total variation to $(\mu,\nu)$, and we infer the convergence of the algorithm to the desired limit $\pi_{*}$.

Several recent works have addressed the stability of entropic optimal transport from different angles. The first result is in , for a setting with bounded cost and marginals equivalent to a common reference measure with densities uniformly bounded above and below. The authors show by a differential approach that the potentials are continuous in $L^{p}$ relative to the marginal densities. Still with bounded cost (and some other conditions), establishes uniform continuity of the potentials relative to the marginals in Wasserstein distance $W_{1}$; this result is based on the Hilbert–Birkhoff projective metric. Closer to the present unbounded setting, obtains stability of the optimal couplings in weak convergence for general continuous costs. Based on the geometric approach first proposed in , the main restriction of the technique is that the underlying spaces need to satisfy Lebesgue’s theorem on differentiation of measures which generally holds only in finite-dimensional spaces. As a by-product, the main result of the present paper yields a similar stability result for weak convergence; cf. Theorem 2.1 (i). The present result also applies in an infinite-dimensional context; the more important difference, however, is that we achieve a strong form of convergence, whereas is silent about any convergence of the densities or potentials. In particular, we can infer stability in the sense of total variation convergence (Corollary 2.6) and the corresponding convergence of Sinkhorn’s algorithm (Corollary 3.2). It is worth noting that these two stabilities are at opposites ends of the spectrum: in the weak topology, compactness for sets of couplings is immediate; the difficulty is to ensure that a limit is the optimal coupling for its marginals. For a limit in total variation, the latter is easy, but obtaining compactness is difficult due to the strength of the topology. In the present work, we effectively reduce the dimension by focusing on densities with a decomposition given by potentials and then obtain compactness through the potentials. A last related work is , which was conducted concurrently. Here stability of the coupling in Wasserstein distance $W_{p}$ is shown under certain growth and integrability conditions. Obtained by control-theoretic arguments through a transport inequality, the main strength of this result lies in being quantitative (which the present one is not). On the other hand, is once again silent about the densities or potentials, and does not yield a convergence in total variation. Indeed, we are not aware of previous stability results in total variation beyond bounded settings. Finally, we would like to mention the ongoing research kindly pointed out to us by Giovanni Conforti. In the setting of dynamic Schrödinger bridges satisfying a logarithmic Sobolev inequality for the underlying dynamics and marginal distributions with finite Fisher information, the authors study quantitative bounds for the relative entropy of Schrödinger bridges with different marginals and the convergence of the gradients of the potentials towards the Brenier map as $\varepsilon\to 0$.

The remainder of this paper is organized as follows. Section 2 contains the main results on stability. Section 3 details the application to Sinkhorn’s algorithm. The proof of the main result, Theorem 2.1, is split into ten steps which are reported in Section 4. For convenience, Appendix A summarizes background on entropic optimal transport. Appendix B details how stability, even uniformly on compacts, can be obtained rather directly under strong integrability conditions. Lastly, Appendix C contains some proofs that we defer in the body of the text.

Stability

Let $\mathcal{X},\mathcal{Y}$ be Polish spaces endowed with their Borel $\sigma$-fields and $\mathcal{P}(\mathcal{X}),\mathcal{P}(\mathcal{Y})$ their sets of Borel probability measures. We recall that $c:\mathcal{X}\times\mathcal{Y}\to[0,\infty)$ is continuous. In Theorem 2.1 below, we consider the entropic optimal transport problem (1.4) for marginals $(\mu_{n},\nu_{n})\in\mathcal{P}(\mathcal{X})\times\mathcal{P}(\mathcal{Y})$ converging to marginals $(\mu,\nu)$. The condition (2.1) of the theorem implies that $\mathcal{C}(\mu_{n},\nu_{n})<\infty$ and that there exist optimal couplings $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$ with associated potentials $(f_{n},g_{n})$; see Section A for these facts and further background.

Before stating the theorem, let us comment on the normalization chosen therein. As mentioned in the Introduction, $f_{n}$ and $g_{n}$ are only unique up to an additive constant. This does not affect the sum $f_{n}\oplus g_{n}$ determining the density of $\pi_{n}$, but in order to obtain a separate convergence for $f_{n}$ and $g_{n}$, it is clearly necessarily to impose an additional condition to pin down this constant. There are many possible choices; in Theorem 2.1, we work with $\alpha_{n}:=\int\arctan(f_{n})\,d\mu_{n}$. As $\arctan$ is strictly increasing, fixing the value of the integral is equivalent to determining the additive constant (and conversely, there is a version of the potentials such that, e.g., $\alpha_{n}=0$). Since $\arctan$ is bounded, it is clear that $(\alpha_{n})$ always converges after passing to subsequence. Furthermore, this type of normalization is compatible with convergence in distribution.

and that $\mu_{n},\nu_{n}$ converge weakly to $\mu,\nu$. Then

$\mathcal{C}(\mu,\nu)<\infty$ and the optimal couplings converge weakly: $\pi_{n}\to\pi_{*}$.

and analogous properties hold for $G_{n}^{k},G^{k},g$.

Then the optimal values converge: $\mathcal{C}(\mu_{n},\nu_{n})\to\mathcal{C}(\mu,\nu)$. If $\alpha_{n},\alpha,f,g$ are as in (ii), then

The next two results discuss the main condition (2.1) of the theorem.

and thus (2.1) is equivalent to boundedness in $L^{1}$:

Remark 2.2 follows from the duality $\int f_{n}\,d\mu_{n}+\int g_{n}\,d\nu_{n}=\mathcal{C}(\mu_{n},\nu_{n})\geq 0$; cf. Proposition A.2. We can provide a sufficient condition for (2.1) in terms of the given data as follows.

Let $(f_{n},g_{n})$ satisfy (2.9). The following condition is sufficient for (2.1) and (2.10):

The following condition is sufficient for (2.11):

The proof is deferred to Appendix C. We remark that the assumption (2.9) is mostly a matter of normalization. Indeed, suppose that $f_{n}^{+}\in L^{1}(\mu_{n})$ and $g_{n}^{+}\in L^{1}(\nu_{n})$—which necessarily holds under (2.11), cf. Proposition A.1. Then $\int f_{n}\,d\mu_{n}+\int g_{n}\,d\nu_{n}=\mathcal{C}(\mu_{n},\nu_{n})\geq 0$ by duality (cf. Proposition A.2). Therefore, (2.9) always holds after choosing a suitable normalization for $(f_{n},g_{n})$, for instance the centering $\int f_{n}\,d\mu_{n}=0$.

Let (2.1) hold and let $\mu_{n},\nu_{n}$ converge weakly to $\mu,\nu$. Suppose that $\mu\ll\mu_{n}$, $\nu\ll\nu_{n}$ and

Then $f_{n}\oplus g_{n}\to f\oplus g$ in $\mu\otimes\nu$-probability, where $(f,g)$ are arbitrary potentials for $(\mu,\nu)$. If $\alpha_{n},\alpha,f,g$ are as in Theorem 2.1 (ii), then $f_{n}\to f$ in $\mu$-probability and $g_{n}\to g$ in $\nu$-probability.

As $f\oplus g$ is uniquely determined and convergence in probability is metrizable, it suffices to show that any subsequence of $f_{n}\oplus g_{n}$ has a subsequence converging to $f\oplus g$. Thus we may further assume that $\alpha_{n},\alpha,f,g$ are as in Theorem 2.1 (ii) and show the convergence of $(f_{n})$ and $(g_{n})$. Fix $\varepsilon>0$ and a subsequence of $(f_{n})$. By (2.6) and (2.5) in Theorem 2.1, there exist a further subsequence (not relabeled) and functions $F_{n}^{k},F^{k}$ such that along this subsequence,

for some $\delta_{k}\geq 0$ with $\lim_{k}\delta_{k}=0$, by (2.4). Taking $n\to\infty$, then $k\to\infty$ and finally $C\to\infty$, we obtain

Condition (2.13) holds in particular for sequences converging in total variation.

Suppose that $\mu\ll\mu_{n}$ and $\mu_{n}\to\mu$ in total variation. Then

The proof is deferred to Appendix C. Our final result is the stability of the optimal couplings in the topology of total variation, complementing the weak stability shown in Theorem 2.1 (i).

Let (2.1) hold and let $\mu_{n},\nu_{n}$ converge in total variation to $\mu,\nu$ where $\mu\ll\mu_{n}$ and $\nu\ll\nu_{n}$. Then $\pi_{n}\to\pi_{*}$ in total variation.

For the sake of readability, we state here the proof under the additional assumption that $\mu_{n}\sim\mu$ and $\nu_{n}\sim\nu$; the general case is deferred to Appendix C. By Corollary 2.4 and Lemma 2.5, we have $f_{n}\to f$ in $\mu$-probability and $g_{n}\to g$ in $\nu$-probability after passing to a subsequence. Under the additional assumption, $\frac{d\mu_{n}}{d\mu}\to 1$ in $L^{1}(\mu)$ and $\frac{d\nu_{n}}{d\nu}\to 1$ in $L^{1}(\nu)$. We see that

in $\mu\otimes\nu$-probability. But then the convergence also holds in $L^{1}(\mu\otimes\nu)$, by Scheffé’s lemma, and we conclude that $\pi_{n}\to\pi_{*}$ in total variation. The convergence of the original sequence follows. ∎

Convergence of Sinkhorn’s Algorithm

Fix marginals $(\mu,\nu)\in\mathcal{P}(\mathcal{X})\times\mathcal{P}(\mathcal{Y})$ and a continuous cost $c:\mathcal{X}\times\mathcal{Y}\to[0,\infty)$. Sinkhorn’s algorithm (1.2) can be written in terms of potentials. Set $\varphi_{0}:=0$ and

where $\psi_{-1}:=0$. One can check by direct calculation that $\pi_{n}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})$ are the same measures as in (1.2). Denoting by $(\mu_{n},\nu_{n})$ the marginal distributions of $\pi_{n}$, the following summarizes well known properties of Sinkhorn’s algorithm (e.g., [28, Section 6]).

Let $\mathcal{C}(\mu,\nu)<\infty$. We have $\mu_{n}\sim\mu$ and $\nu_{n}\sim\nu$ for all $n\geq 0$. Moreover, $H(\mu_{n}|\mu)+H(\nu_{n}|\nu)\to 0$; in particular, $\mu_{n}\to\mu$ and $\nu_{n}\to\nu$ in total variation. For $t\geq 0$, the marginals satisfy

In brief, $(f_{n},g_{n})$ are potentials for the marginals $(\mu_{n},\nu_{n})$ which in turn converge to $(\mu,\nu)$ in total variation. The stability result of Corollary 2.6 then yields the following convergence result. As emphasized in the Introduction, it covers quadratic costs with arbitrary subgaussian marginals and the problem (1.1) with arbitrary regularization parameter $\varepsilon>0$.

Then $\mathcal{C}(\mu,\nu)<\infty$ and the Sinkhorn iterates $(\pi_{n})$ converge to $\pi_{*}$ in total variation.

As $H(\mu_{n}|\mu)+H(\nu_{n}|\nu)\to 0$ by Lemma 3.1, Lemma 2.3 yields that

In particular, $\mathcal{C}(\mu_{n},\nu_{n})<\infty$ and $(f_{n},g_{n})$ as defined in Lemma 3.1 are potentials for the marginals $(\mu_{n},\nu_{n})$; cf. Propositions A.1 and A.2. Next, we show that $(f_{n},g_{n})$ satisfy (2.1). In general, the Sinkhorn iterates satisfy $(\varphi_{t},\psi_{t})\in L^{1}(\mu)\times L^{1}(\nu)$ as well as $\int\varphi_{t}\,d\mu\geq 0$ and $\int\psi_{t}\,d\nu\geq-\log\int e^{-c}\,d(\mu\otimes\nu)$; see [28, Lemma 6.4 and its footnote]. Here, as $c\geq 0$, we have $\int\varphi_{t}\,d\mu\geq 0$ and $\int\psi_{t}\,d\nu\geq 0$.

Consider $n=2t$, then $\nu_{n}=\nu$. Using (3.1), Jensen’s inequality and $\int\psi_{t}\,d\nu\geq 0$,

and hence $\int f_{n}^{+}\,d\mu_{n}\leq\int c\,d(\mu_{n}\otimes\nu_{n})$ which is bounded by (3.4). Similarly, (3.1) implies $g_{n}(y)=\psi_{t}(y)\leq\int c(x,y)\,\mu(dx)$ and hence

The argument for $n=2t-1$ is symmetric, so that (2.1) holds. As the marginals are equivalent and converge in total variation by Lemma 3.1, the claim follows by Corollary 2.6. ∎

Proof of Theorem 2.1

The proof is structured into several steps.

Further properties related to $F_{n}^{k}$ and $F^{k}$.

Proof that $(f_{n})_{\#}\mu_{n}\to f_{\#}\mu$.

Proof that $f,g$ induce a coupling $\pi$ and $\pi_{n}\to\pi$.

Identification of the limit, end of proof of Theorem 2.1 (i),(ii).

Step 1 is based on the following generalization of [29, Lemma 2.3] extending that result from a single measure to a tight set of measures.

The proof of Lemma 4.1 is an adaptation of the arguments in ; for completeness, the details are reported in Appendix C.

As a preparation for Step 4, we record the following covering lemma.

$D_{j}$ has diameter at most $r$ and boundary $\mu(\partial D_{j})=0$,

The general relation $\partial(A\cap B)\subseteq\partial A\cup\partial B$ implies that $\mu(\partial D_{j})=0$, and the other requirements are satisfied by construction. ∎

We record two more facts about the construction in Step 4 for later use. For $x\in D_{j}^{k}\cap A_{n}^{k}$, (4.2) and (4.5) yield

As $\cup_{j}D_{j}^{k}=\mathcal{X}$ and $f_{n}^{k}=f_{n}$ on $A_{n}^{k}$, it follows that

In view of $\mu_{n}(A_{n}^{k})\geq 1-\delta_{k}$, this yields in particular

Second, we define similarly as in (4.6) the function

for $x\in A_{n}^{k}\cap A_{n}^{k^{\prime}}$. In view of $\mu_{n}(A_{n}^{k}\cap A_{n}^{k^{\prime}})\geq 1-2\varepsilon$, it follows that

As $F_{n}^{k}\to F^{k}$ and $F_{n}^{k^{\prime}}\to F^{k^{\prime}}$ uniformly (cf. Step 4), we conclude

On the other hand, using the mapping theorem and (4.9) for both $\mu\equiv\mu_{0}$ and $\mu_{n}$,

Fix $k\geq k_{0}$ such that $\delta_{k}\leq\varepsilon$. Then by (4.9),

Above, we have introduced the functions $f_{n}^{k},F_{n}^{k},F^{k},f$ on $\mathcal{X}$. Analogously, one constructs $g_{n}^{k},G_{n}^{k},G^{k},g$ on $\mathcal{Y}$. We can now detail the main step of the proof, showing that $f,g$ are indeed potentials for a coupling $\pi\in\Pi(\mu,\nu)$. To keep track of the argument more easily, we state the technical parts as lemmas and prove them at the end.

and let $S\subset\mathcal{X}\times\mathcal{Y}$ be measurable with $\pi(\partial S)=0$; we show $\pi(S)=\lim_{n\to\infty}\pi_{n}(S)$. Define the auxiliary measures

Fix $\varepsilon\in(0,1/9)$ and consider the decomposition

We estimate separately the four terms on the right-hand side.

The lemma is proved at the end of Step 8. For the first term in (8), Lemma 4.3 shows that there exists $C>0$ such that

We continue with the last term of (8). Since $x\mapsto e^{x}$ is increasing and nonnegative, an application of the monotone convergence theorem for $C\to\infty$ shows that after increasing $C$ as necessary, we have

(The second case will be eliminated by contradiction later on.) The value of $C$ is now fixed for the remainder of the proof.

Turning to the third term in (8), note that since $F^{k}\stackrel{{\scriptstyle\mu}}{{\to}}f$ and $G^{k}\stackrel{{\scriptstyle\nu}}{{\to}}g$,

For the remainder of the proof, $k\geq\max(k_{0},k_{1},k_{2})$ is fixed.

The lemmas are proved at the end of Step 8. Together, they show

Combining this with (4.12) and (4.15) yields

This shows $\lim_{n\to\infty}\pi_{n}(S)=\pi(S)$. Thus we have proved that $\pi\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})$ and $\pi_{n}\to\pi$ weakly [5, Theorem 2.1]. As the marginals then also converge weakly and $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$, this implies $\pi\in\Pi(\mu,\nu)$.

where $\mathcal{J}^{k}$ and $\mathcal{L}^{k}$ are finite sets. Thus

and similarly for $F^{k},G^{k}$ instead of $F_{n}^{k},G_{n}^{k}$. By the construction in Step 4,

As $S$ and $(D_{j}^{k}\times E_{l}^{k})$ are $\mu\otimes\nu$-continuity sets, we also have

We can now expand the difference to be estimated as

In view of (4.19) and (4.20), taking $n\to\infty$ yields

defines a coupling of $\mu,\nu$. Moreover, Step 7 and (2.1) imply that $f^{+}\in L^{1}(\mu)$ and $g^{+}\in L^{1}(\nu)$. By the general verification result in Proposition A.2, the form of $\pi$ with $(f\oplus g)^{+}\in L^{1}(\mu\otimes\nu)$ implies that $(f,g)\in L^{1}(\mu)\times L^{1}(\nu)$, that $\mathcal{C}(\mu,\nu)<\infty$ and that $\pi=\pi_{*}$ is the unique minimizer for the entropic optimal transport problem (1.4). It follows that $\pi_{n}\to\pi_{*}$ also holds along the original sequence, completing the proof of Theorem 2.1 (i).

It remains to prove Theorem 2.1 (iii). Let (2.7) hold. Passing to a subsequence, we may assume that $\alpha_{n}\to\alpha$ and $f,g$ are as in Theorem 2.1 (ii). We first show the upper semicontinuity

Indeed, the weak convergence (2.3) and the uniform integrability (2.7) imply that $\lim_{n\to\infty}\int f^{+}_{n}\,d\mu_{n}=\int f^{+}\,d\mu$. Together with Portmanteau’s theorem for $(f^{-}_{n})$, the first part of (4.22) follows, and similarly for the second.

Next, we argue the lower semicontinuity of the sum,

By (2.1) and Proposition A.2, we have the duality

Together, the lower semicontinuity (4.23) of the sum and the separate upper semicontinuity (4.22) imply (2.8). This completes the proof of Theorem 2.1. ∎

Appendix A Background on Entropic Optimal Transport

Let $(\mu,\nu)\in\mathcal{P}(\mathcal{X})\times\mathcal{P}(\mathcal{Y})$ and let $c:\mathcal{X}\times\mathcal{Y}\to[0,\infty)$ be measurable. We have the following result on existence and uniqueness for the entropic optimal transport problem (1.4).

If $c\in L^{1}(\mu\otimes\nu)$, then $\mathcal{C}(\mu,\nu)<\infty$ and $(f,g)\in L^{1}(\mu)\times L^{1}(\nu)$.

See [28, Theorem 4.2] for a proof. Conversely, the next result shows that the form of the density characterizes the minimizer. We also include the duality relation.

Let $\pi_{0}\in\Pi(\mu,\nu)$ admit a density of the form

If $\mathcal{C}(\mu,\nu)<\infty$, then $\pi_{0}$ is the minimizer $\pi_{*}$ and $f_{0},g_{0}$ are its potentials.

If $(f_{0}\oplus g_{0})^{+}\in L^{1}(\mu\otimes\nu)$, then necessarily $(f_{0},g_{0})\in L^{1}(\mu)\times L^{1}(\nu)$ and

In particular, $\mathcal{C}(\mu,\nu)<\infty$ and (a) applies.

See [28, Theorem 4.2, Theorem 4.7, Remark 4.8]. When $f,g$ are potentials as in Proposition A.1, the fact that $\pi_{*}\in\Pi(\mu,\nu)$ implies the so-called Schrödinger equations

We may choose versions of the potentials such that these relations hold without exceptional sets.

Appendix B Uniform Stability under Strong Integrability

The following result shows that stability of the potentials, even uniformly on compacts, can be obtained quite easily when the cost is sufficiently integrable. As discussed in the Introduction, the integrability condition is not satisfied in the regime of principal interest. For the statement, we choose versions of the potentials such that (A.2) holds without exceptional sets.

Then $f_{n}\oplus g_{n}\to f\oplus g$ uniformly on compacts, where $(f,g)$ are arbitrary potentials for $(\mu,\nu)$, and the corresponding optimal couplings converge weakly. If $\alpha_{n},\alpha,f,g$ are as in Theorem 2.1 (ii), then also $f_{n}\to f$ and $g_{n}\to g$, uniformly on compacts.

Similarly as in Lemma 2.3, a sufficient condition for (B.1) is that

and $(f_{n},g_{n})$ are normalized such that (2.9) holds, for instance $\int f_{n}\,d\mu_{n}=0$.

This yields the uniform lower bound $f_{n}\geq-\log C$, and similarly $g_{n}\geq-\log C$. Fix $x\in\mathcal{X}$. Using (A.2) and the lower bound,

Next, we show that $(f_{n})$ is equicontinuous. On the strength of the pointwise boundedness, it suffices to show that $e^{-f_{n}}$ is equicontinuous. Fix a compatible metric on $\mathcal{X}$, let $x_{0}\in\mathcal{X}$ and $\varepsilon>0$. Using tightness, choose a compact $K\subset\mathcal{Y}$ with $\nu_{n}(K^{c})<\varepsilon$ for all $n$. Let $q\in(1,\infty)$ satisfy $1/\beta+1/q=1$. By Hölder’s inequality,

Recalling that $e^{-c}\leq 1$, the integral can be estimated by

As $c$ is continuous and $K$ is compact, $\sup_{y\in K}\left|e^{-c(x_{0},y)}-e^{-c(\cdot,y)}\right|$ is continuous. Therefore, $\int_{K}|e^{-c(x_{0},y)}-e^{-c(x,y)}|^{q}\,\nu_{n}(dy)<\varepsilon$ for $x\in B_{\delta}(x_{0})$, for $\delta>0$ sufficiently small, and we obtain the desired equicontinuity,

We have shown that $(f_{n})$ is equicontinuous and pointwise bounded, and the same arguments hold for $(g_{n})$. Passing to a subsequence, the Arzelà–Ascoli theorem shows that $f_{n}\to f$ and $g_{n}\to g$ uniformly on compacts. Note that $(e^{f_{n}\oplus g_{n}-c})_{n}$ is $(\mu_{n}\otimes\nu_{n})_{n}$-uniformly integrable by (B.1). As $e^{f_{n}\oplus g_{n}-c}\to e^{f\oplus g-c}$ uniformly on compacts and $\mu_{n}\otimes\nu_{n}\to\mu\otimes\nu$ weakly, it follows for the optimal couplings $\pi_{n}$ that

In particular, $\pi_{0}\in\Pi(\mu,\nu)$. Proposition A.2 now shows that $\pi_{0}$ is the optimal coupling for $(\mu,\nu)$ and $(f,g)$ are corresponding potentials. As $f\oplus g$ is unique (Proposition A.1), the claim for the original sequence follows. ∎

Following the above proof, the argument for pointwise boundedness still applies, and the argument for equicontinuity is even simpler under the additional hypothesis. The argument using uniform integrability may no longer be clear, but we can instead use Theorem 2.1 to conclude that $(f,g)$ must be potentials for $(\mu,\nu)$.

Appendix C Omitted Proofs

and now Tonelli’s theorem yields $\int f_{n}^{+}\,\mu_{n}\leq C+\int c\,d(\mu_{n}\otimes\nu_{n}).$ The analogue holds for $g_{n}$. Thus (2.11) implies (2.1), and via (2.9) also (2.10).

More generally, given a measurable set $A\subset\mathcal{X}$, (C.1) also implies

If $\mu_{n}(A)\leq\delta$, then $(\mu_{n}\otimes\nu_{n})(A\times\mathcal{Y})\leq\delta$, so that the $\varepsilon$–$\delta$ characterization of uniform integrability yields the claim.

(ii) The variational representation of relative entropy [28, Lemma 1.3] shows that

for any measurable function $\psi$ bounded from below. Choosing $\psi=\beta c$, we deduce

Noting that $H(\mu_{n}\otimes\nu_{n}|\mu\otimes\nu)=H(\mu_{n}|\mu)+H(\nu_{n}|\nu)$, the right-hand side is bounded under (2.12), so that (2.11) applies. To obtain the last claim, we replace $c$ with $\phi(c)$ in the preceding argument and apply the la Vallée–Poussin theorem. ∎

then shows that $\limsup_{n}\mu(A_{n})\leq C^{-1}$. The claim follows. ∎

By Corollary 2.4 and Lemma 2.5, we have $f_{n}\to f$ in $\mu$-probability and $g_{n}\to g$ in $\nu$-probability after passing to a subsequence. Consider the Lebesgue decomposition $\mu_{n}=\mu_{n}^{\prime}+\mu_{n}^{\prime\prime}$ into $\mu_{n}^{\prime}\ll\mu$ and $\mu_{n}^{\prime\prime}\bot\mu$. Then $\mu_{n}^{\prime}\to\mu$ in total variation and hence $\frac{d\mu_{n}^{\prime}}{d\mu}\to 1$ in $L^{1}(\mu)$. This implies the convergence in $\mu$-probability of the reciprocal, and as $\frac{d\mu}{d\mu_{n}^{\prime}}=\frac{d\mu}{d\mu_{n}}$ $\mu$-a.s., that $\frac{d\mu}{d\mu_{n}}\to 1$ in $\mu$-probability. Similarly, $\frac{d\nu}{d\nu_{n}}\to 1$ in $\nu$-probability. Following the proof of the particular case in Section 2 but writing the reciprocals,

in $\mu\otimes\nu$-probability. Consider the Lebesgue decomposition $\pi_{n}=\pi_{n}^{\prime}+\pi_{n}^{\prime\prime}$ into $\pi_{n}^{\prime}\ll\mu\otimes\nu$ and $\pi_{n}^{\prime\prime}\bot\mu\otimes\nu$. Then it follows that

in $\mu\otimes\nu$-probability, which by Scheffé’s lemma implies $\pi_{n}^{\prime}\to\pi_{*}$ in total variation. As $\pi_{n},\pi_{*}$ are probability measures, it follows that $\pi_{n}^{\prime\prime}(\mathcal{X}\times\mathcal{Y})\to 0$ and finally $\pi_{n}\to\pi_{*}$ in total variation. The convergence of the original sequence follows. ∎

which implies (C.3). Next, we observe from the definition of $A_{n}$ and (C.4) that for $x\in A_{n}$,

Let $x_{1},x_{2}\in A_{n}$ and assume without loss of generality that $f_{n}(x_{1})\geq f_{n}(x_{2})$. Then

This concludes the proof of the first estimate in the lemma. Turning to the second, note that by (C.2), (C.3) and the definition of $A_{n}$,

where we chose $\varepsilon:=\delta^{2}$ (ensuring $\varepsilon\in(0,\delta)$, in particular). Define

Arguing as for (C.3) and (C), now using (C.7) instead of (C.2), we see that $\nu_{n}(B_{n}^{c})\leq\delta$ and that for $y\in B_{n}$,

We conclude the proof by arguing as in (C.6) but with $f_{n},\varepsilon$ replaced by $g_{n},\delta$. ∎

References