Stability of Entropic Optimal Transport and Schrödinger Bridges

Introduction

Computational progress has lead to manifold applications of optimal transport in high-dimensional problems ranging from machine learning and statistics to image and language processing (e.g., ). In this context, entropic regularization is crucial to enable efficient large-scale computation via Sinkhorn’s algorithm, hence has become the focus of dozens of recent studies. We refer to for a survey with numerous references.

Our main contribution is the stability of solutions to the entropically regularized optimal transport problem with respect to the marginals and the cost function. Parallel to the fundamental stability theorem in classical optimal transport, it justifies, for example, that approximations found by solving discretized problems indeed converge to the true solution when the cost function is continuous. Our results are stated in terms of cyclical invariance, a geometric notion inspired by the $c$-cyclical monotonicity property in classical optimal transport. When the entropic transport problem has finite value, a coupling is cyclically invariant if and only if it is an optimal transport. Our stability theorem entails a general wellposedness result beyond the realm of optimization: cyclical invariance singles out a unique coupling even if the transport problem has infinite value—i.e., all couplings have infinite cost—and therefore the paradigm of cost minimization does not differentiate couplings from one another.

where $\Pi(\mu,\nu)$ is the set of couplings and $H(\cdot|P)$ denotes relative entropy (or Kullback–Leibler divergence) with respect to the product $P$ of the marginals, defined as $H(\pi|P):=\int\log(\frac{d\pi}{dP})\,d\pi$ for $\pi\ll P$ and $H(\pi|P):=\infty$ otherwise. If the minimization (1.1) is finite; i.e., if

then it admits a unique minimizer $\pi\in\Pi(\mu,\nu)$ and moreover $\pi\sim P$.

A coupling $\pi\in\Pi(\mu,\nu)$ is called $(c,\varepsilon)$-cyclically invariant if $\pi\sim P$ and its density admits a version $d\pi/dP:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$ such that

By way of a factorization property that is equivalent to cyclical invariance, known results imply the following relation to the optimization (1.1).

Let (1.1) be finite. Then $\pi\in\Pi(\mu,\nu)$ is the minimizer of (1.1) if and only if $\pi$ is $(c,\varepsilon)$-cyclically invariant.

See Section 5 for details and references. We are mainly interested in optimal transport problems on Euclidean spaces $\mathsf{X},\mathsf{Y}$. However, the only particular property of such spaces that plays a role for our analysis is that Lebesgue’s theorem on the differentiation of measures holds. Thus, we postulate that property (see Assumption 2.3) and otherwise allow for a general Polish setting. We can now state the aforementioned wellposedness result.

Let $c:\mathsf{X}\times\mathsf{Y}\to[0,\infty)$ be continuous, $\varepsilon>0$ and $(\mu,\nu)\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$. There exists a unique $(c,\varepsilon)$-cyclically invariant coupling $\pi\in\Pi(\mu,\nu)$. If (1.1) is finite, $\pi$ is its unique minimizer.

Uniqueness follows from known facts and does not require the continuity of $c$. On the other hand, existence beyond the framework of finite cost is a completely novel result. Rather than using convex analysis or variational arguments, it is based on the subsequent stability theorem for cyclical invariance. One example where wellposedness with infinite cost is of interest, is the statistical notion of rank recently proposed in . Multivariate ranks have been defined in nonparametric statistics through Brenier’s optimal transport map to extend the usual scalar notions and tests; see . Leveraging the same idea but computationally less expensive, entropic optimal transport is used in to define “differentiable ranks.” Theorem 1.3 allows one to naturally define such ranks for arbitrary distributions—like in the scalar case—without imposing a second moment condition.

For $n\geq 1$, let $(\mu_{n},\nu_{n})\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$, let $\varepsilon_{n}>0$ and let $c_{n}:\mathsf{X}\times\mathsf{Y}\to[0,\infty)$ be measurable. Let $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$ be $(c_{n},\varepsilon_{n})$-cyclically invariant. Suppose that $\mu_{n},\nu_{n}$ converge weakly to some limits $\mu,\nu$, that $\varepsilon_{n}\to\varepsilon>0$ and that $c_{n}$ converges uniformly on bounded sets to a continuous function $c$. Then $\pi_{n}$ converges weakly to a limit $\pi\in\Pi(\mu,\nu)$ and $\pi$ is $(c,\varepsilon)$-cyclically invariant.

If the involved optimization problems are finite, the theorem states the stability of the (entropic) optimal transport couplings. A simple yet important application is when the marginals $\mu,\nu$ are approximated by discrete measures, as it would be in a computational implementation. Even for this particular case, we are not aware of similar results in the literature. We mention that continuity for the limiting cost $c$ in Theorem 1.4 is a sharp condition: Proposition 5.3 will demonstrate that any nontrivial discontinuity in $c$ leads to a failure of Theorem 1.4, for suitable marginals.

A noteworthy application of the stability theorem was presented in the follow-up work where it was observed that convergence of Sinkhorn’s algorithm can be seen as a stability problem. In that context, the marginals $\mu_{n},\nu_{n}$ are produced by the algorithm and known to converge to $\mu,\nu$ in great generality, while the iterates of the algorithm correspond to $\pi_{n}$. Theorem 1.4 then implies the weak convergence to the correct optimizer $\pi$. Its geometric approach completely avoids the difficulty of establishing the integrability properties of $\mu_{n},\nu_{n}$ or even the finiteness of the associated entropic optimal transport problems.

The general existence result of Theorem 1.3 is a consequence of Theorem 1.4 applied with $c_{n}=c$, $\varepsilon_{n}=\varepsilon$ and approximations $(\mu_{n},\nu_{n})\to(\mu,\nu)$ where $\mu_{n},\nu_{n}$ are discrete measures with finite support. To solve the problem with marginals $(\mu_{n},\nu_{n})$, one could use Proposition 1.2, but this particular case is a finite-dimensional minimization problem that can also be solved by standard calculus arguments. In particular, Theorem 1.4 yields an approach to construct cyclically invariant couplings which is novel even when the optimization problem is finite. This approach does not use the (classical but non-trivial) arguments of convex analysis and density factorization behind Proposition 1.2 (see , among others). It is also quite different from the iterative method of which uses another finiteness condition; see for a modern presentation, analysis and extension of that method. Instead, our approach is close in spirit to the construction of $c$-cyclically monotone couplings that is standard in classical optimal transport; cf. [52, pp. 64–65].

The companion paper illustrates the use of cyclical invariance for the limit $\varepsilon\to 0$. In this degenerate asymptotic, the limiting object is classical optimal transport as characterized by $c$-cyclical monotonicity. The latter property describes the shape of the support of the coupling and, therefore, is readily amenable to weak convergence arguments via Portmanteau’s theorem. The same fact is often exploited in classical optimal transport theory, for instance in the standard proof of its stability theorem [52, p. 77]. In the present study, the limit is entropic optimal transport. Being a property of the density, the relation of cyclical invariance with weak convergence is less direct (especially as the measures in Theorem 1.4 may well be mutually singular). Our general principle is to blow the points $(x_{i},y_{i})$ in Definition 1.1 up to small balls, pass to the weak limit, and then recover information about the limiting density by shrinking the balls, via differentiation of measures. This technique appears to be novel in this area.

Starting with , a number of works examine the degenerate asymptotic $\varepsilon\to 0$ where the limiting problem is classical optimal transport. The fact that weak limits of entropic optimizers are optimal transports was established by using Gamma-convergence arguments in a more general context of Schrödinger bridges; see also for the case of optimal transport with quadratic cost. As mentioned above, extends this result to transport problems with infinite value by way of cyclical invariance and $c$-cyclical monotonicity; moreover, a large deviations principle quantifies the local rate of convergence. Related results can be found in where the expansion of the optimal cost as a function of $\varepsilon$ is studied. We remark that Gamma convergence seems difficult to use in the context of Theorem 1.4 due to the reference measures changing along the sequence. The limit $\varepsilon\to 0$ can also be analyzed in the associated dual problem, here the solutions are called potentials. Convergence of potentials was shown in for quadratic costs and compactly supported marginals, and recently in for a general Polish setting. Closer to the problem occurring in computational practice as well as the present question of stability, studies the convergence of the discrete Sinkhorn algorithm to an optimal transport in the joint limit when $\varepsilon_{n}\to 0$ and the marginals $\mu,\nu$ are approximated by discretizations $\mu_{n},\nu_{n}$ satisfying a certain density property. Explicit error bounds are derived, for instance for quadratic cost on the torus, to establish near-linear complexity of the resulting algorithm. For more on the computational challenges and remedies in this regime, see for instance and the references therein.

While we are not aware of general stability results for the nondegenerate limit $\varepsilon_{n}\to\varepsilon>0$ in the literature, the sampling complexity of entropic optimal transport (with fixed $\varepsilon$) can be seen as a particular form of stability with respect to the marginals. Indeed, study how the the empirical entropic Wasserstein distance, obtained by optimally coupling i.i.d. samples from the marginals, converges to the population version. The results are based on global arguments exploiting the regularity of the Schrödinger potentials, which, in turn, is achieved by imposing compactness and decay conditions on the marginals. See also which studies a related asymptotic regime for a different regularization of optimal transport. Related to the present work at least in spirit, there are several areas where analogues of $c$-cyclical monotonicity have recently lead to breakthroughs, including martingale optimal transport , optimal Skorokhod embeddings and weak transport .

The remainder of this paper is organized as follows. Section 2 details the setting and main results in the language of Schrödinger bridges. The first step towards the stability theorem is reported Section 3 where we establish that weak limits of cyclically invariant couplings remain absolutely continuous. This is based on comparing measures of rectangles, an analysis that may be of independent interest. Section 4 continuous the main proof by showing that limits of cyclically invariant couplings are again cyclically invariant. It comprises of two steps; the aforementioned principle of blowing up points and passing to the limit first yields a weakened version of the invariance property, and then measure-theoretic arguments can be used to show that the (proper) invariance property already follows. The concluding Section 5 collects the arguments to prove the main results and their ramifications, including that continuity of the cost function is necessary for stability.

Main Results

Let $(\mathsf{X},d)$ be a complete, separable metric space; we write $\mathcal{P}(\mathsf{X})$ for the space of probability measures on the Borel $\sigma$-field $\mathcal{B}(\mathsf{X})$ endowed with weak convergence (induced by bounded continuous functions). The same is assumed for the second marginal space $(\mathsf{Y},d)$, and we equip $\mathsf{X}\times\mathsf{Y}$ with the metric $d((x,y),(x^{\prime},y^{\prime}))=\max\{d(x,x^{\prime}),d(y,y^{\prime})\}$. Throughout this section, two measures $(\mu,\nu)\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$ play the role of given marginals for the static Schrödinger bridge problem

where $R\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$ is a given reference measure. We refer to for extensive surveys on Schrödinger bridges. The entropic optimal transport problem (1.1) can be recovered (up to constants) as a special case for $R$ defined by

where $a=(\int e^{-c/\varepsilon}\,dP)^{-1}$ is the normalizing constant. In particular, $R\sim P$, which will also be an important condition in many of our results for (2.1). By way of (2.2), the following generalizes Definition 1.1.

Let $\pi\in\Pi(\mu,\nu)$ and $R\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$. We call $(\pi,R)$ cyclically invariant if $\pi\sim R\sim P$ and there exists a version $d\pi/dR:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$ of the relative density satisfying

The analogue of the finiteness condition (1.2) is that

We summarize the pertinent facts; see Lemma 5.1 for detailed references.

Let $R\sim P$ and let (2.1) be finite. There exists a unique minimizer $\pi\in\Pi(\mu,\nu)$ for (2.1), it satisfies $\pi\sim R$, and it is the unique coupling $\pi$ such that $(\pi,R)$ is cyclically invariant.

In the remainder of the paper we assume that the underlying spaces allow for differentiation of measures in the following sense.

Given $\rho,\lambda\in\mathcal{P}(\mathsf{X})$ satisfying $\rho\ll\lambda$, there exists $\mathsf{X}^{\prime}\subset\mathsf{X}$ of full $\lambda$-measure such that

defines a version of the Radon–Nikodym density $d\rho/d\lambda$. The analogous property is assumed on the space $\mathsf{X}\times\mathsf{Y}$.

For Euclidean spaces $\mathsf{X},\mathsf{Y}$, the assumption holds by the standard differentiation theorem [21, Theorem 1.32, p. 53]. More generally, it holds in the context of so-called Vitali covering relations; the classical reference is [23, Theorem 2.9.8, p. 156]. For example, Assumption 2.3 holds when $\mathsf{X}$ and $\mathsf{X}\times\mathsf{Y}$ are compact subsets of Riemannian manifolds (due to the “directionally limited” property established in [23, Section 2.8.9, pp. 145-146]), or more generally, countable unions of such sets. See also [31, pp. 4-8, esp. Example 1.15] for an accessible introduction. For our purposes, the main restriction is that differentiation of measures generally fails on infinite-dimensional spaces; see for a counterexample and for a related result on coverings. An alternative to Assumption 2.3, making our results slightly more general, is to impose a doubling condition on the specific marginal measures $(\mu,\nu)$; cf. Remark 5.2.

We have seen in the Introduction that continuity of $c$ is essential for the stability of entropic optimal transport. In view of (2.2), it is then clear that the regularity of $dR/dP$ is pivotal. The following generalizations of Theorems 1.3 and 1.4 are our main results.

Suppose that $R\sim P:=\mu\otimes\nu$ and that the density $dR/dP$ admits a continuous version. Then there exists a unique coupling $\pi\in\Pi(\mu,\nu)$ such that $(\pi,R)$ is cyclically invariant. If (2.1) is finite, $\pi$ is its minimizer.

For $n\geq 1$, consider $(\mu_{n},\nu_{n})\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$, $R_{n}\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$ and $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$. Let $(\pi_{n},R_{n})$ be cyclically invariant and suppose that $\mu_{n},\nu_{n},R_{n}$ converge weakly to some limits $\mu,\nu,R$, where $R\sim P:=\mu\otimes\nu$. Writing $P_{n}:=\mu_{n}\otimes\nu_{n}$, suppose also that for some versions $\frac{dR_{n}}{dP_{n}},\frac{dR}{dP}:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$ of the respective densities and some constants $\alpha_{n}>0$, it holds that for any fixed $z\in\operatorname{spt}R$,

where $o(1)$ stands for a function $\phi_{z}(z^{\prime},n)\to 0$ as $d(z^{\prime},z)+1/n\to 0$. Then $\pi_{n}$ converges weakly to a limit $\pi\sim R$ and $(\pi,R)$ is cyclically invariant.

Schrödinger bridges are closely related to so-called Schrödinger systems (also called Schrödinger equations). For instance, Theorem 2.4 entails the following wellposedness result.

Let $(\mu,\nu)\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$ and let $f:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$ be continuous with $\int_{\mathsf{X}\times\mathsf{Y}}f\,dP=1$. There exist Borel functions $\varphi:\mathsf{X}\to(0,\infty)$ and $\psi:\mathsf{Y}\to(0,\infty)$ such that

for $\mu$-a.e. $x\in\mathsf{X}$ and $\nu$-a.e. $y\in\mathsf{Y}$. The pair $(\varphi,\psi)$ is a.s. unique up to a multiplicative constant.I.e., any solution $(\varphi^{\prime},\psi^{\prime})$ satisfies $\varphi^{\prime}=a\varphi$ $\mu$-a.s., $\psi^{\prime}=a^{-1}\psi$ $\nu$-a.s., for some $a>0$.

As above, the uniqueness follows from known results. Existence for continuous functions $f$ such that $f,f^{-1}$ are uniformly bounded was first shown in . Under the boundedness condition alone, existence is due to . Using the connection with Schrödinger bridges, relaxed the boundedness to a condition of finite entropy, corresponding to the finiteness of (2.1) in our setting. We refer to for a more complete review of the literature which dates back to Schrödinger. In Corollary 2.6, we reintroduce the continuity condition of but avoid any condition of finite entropy or boundedness. Of course, the stability result of Theorem 2.5 also has an analogous corollary for Schrödinger systems.

Absolute Continuity of Limits

In this section we show that if $(\pi_{n},R_{n})$ is cyclically invariant and $R_{n}\sim\mu_{n}\otimes\nu_{n}$ holds in a locally uniform sense (to be made precise), then any weak limit pair $(\pi,R)=(\lim_{n}\pi_{n},\lim_{n}R_{n})$ must satisfy $\pi\ll R$.

As the method of proof is novel, we first sketch the line of argument. We shall be comparing the measures of rectangles $F_{i}\times G_{i}\subset\mathsf{X}\times\mathsf{Y}$ for $i=1,2$ with their permutations $F_{i}\times G_{i+1}$.We use the cyclical convention for $i\in\{1,2\}$; that is, $i+1:=1$ for $i=2$. Consider first the trivial case $R_{n}=P_{n}:=\mu_{n}\otimes\nu_{n}$, then cyclical invariance of $(\pi_{n},R_{n})$ implies

This will of course no longer hold if $R_{n}\neq P_{n}$, but the equivalence $R_{n}\sim P_{n}$ suggests that the two sides of (3.1) should still be comparable. We will quantify the equivalence $R_{n}\sim P_{n}$ and assume it to hold uniformly in $n$. Then, we prove that the two sides of (3.1) are comparable in the sense that their quotient remains bounded uniformly in $n$. For suitable rectangles, the bound propagates to the weak limit $(\pi,R)$, accomplishing the first step of the proof. The second step is to argue by contraposition that this bound implies $\pi\ll R$. Indeed, we establish that if $\pi\in\Pi(\mu,\nu)$ is singular wrt. $\mu\otimes\nu$, then there exist $F_{i},G_{i}$ such that $\pi(F_{1}\times G_{1})\pi(F_{2}\times G_{2})$ is above a threshold whereas $\pi(F_{1}\times G_{2})\pi(F_{2}\times G_{1})$ is arbitrarily small.

For ease of reference, we first record two measure-theoretic facts.

Let $\rho$ be a $\sigma$-finite measure on a Polish space $(\Omega,d)$. We say that $C\subset\Omega$ is $\rho$-continuous if its boundary $\partial C$ is a $\rho$-nullset.

(i) $\rho$-continuous sets form a field; i.e., unions, intersections, complements, differences of $\rho$-continuous sets are again $\rho$-continuous.

(ii) For fixed $z\in\Omega$, the open ball $B_{r}(z)=\{z^{\prime}:d(z,z^{\prime})<r\}$ is $\rho$-continuous for all but countably many values of $r>0$. In particular, given $r>0$, there exists $0<r^{\prime}\leq r$ such that $B_{r^{\prime}}(z)$ is $\rho$-continuous.

(iii) If $F\subset\mathsf{X}$ is $\mu$-continuous and $G\subset\mathsf{Y}$ is $\nu$-continuous, then $F\times G$ is $\pi$-continuous for any $\pi\in\Pi(\mu,\nu)$.

(iv) Given $A\in\mathcal{B}(\Omega)$ and $\varepsilon>0$, there exists an open set $B\subset A_{\varepsilon}:=\{d(\cdot,A)<\varepsilon\}$ with $\rho(\partial B)=0$ and $\rho(A\Delta B)<\varepsilon$.

Statement (i) is verified directly; (ii) holds because a $\sigma$-finite measure admits at most countably many disjoint sets of positive measure; (iii) follows from $\partial(F\times G)=(\overline{F}\times\partial G)\cup(\partial F\times\overline{G})$. Let $A,\varepsilon$ be as in (iv). By interior and exterior regularity of $\rho$, there is a compact set $K\subset A$ with $\rho(A\setminus K)<\varepsilon$ and an open set $A\subset O\subset A_{\varepsilon}$ with $\rho(O\setminus A)<\varepsilon$. We have $r(z):=d(z,O^{c})>0$ for all $z\in K$ by the closedness of $O^{c}$, and $K$ is covered by the open balls $B_{r(z)}(z)$ with $z\in K$. After making $r(z)$ smaller if necessary, each of these balls is $\rho$-continuous. Choosing a finite cover $\{B_{r(z_{i})}(z_{i})\}_{i\leq N}$, the set $B:=\cup_{i}B_{r(z_{i})}(z_{i})$ has the required properties. ∎

The second fact is a conditional version of the differentiation of measures, based on Assumption 2.3 for the marginal space $\mathsf{X}$. While not widely known, this concept was already established in , although the author defined differentiation of measures in a slightly different way. For the convenience of the reader, we detail the adaptation to our setting.

Let $\pi\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$ and let $\mu$ be its first marginal. Consider for $x\in\operatorname{spt}\mu$ and $r>0$ the probability measure $\pi^{(r)}_{x}\in\mathcal{P}(\mathsf{Y})$ defined by

Under Assumption 2.3 on $\mathsf{X}$, there exists $\mathsf{X}_{0}\subset\operatorname{spt}\mu$ with $\mu(\mathsf{X}_{0})=1$ such that for all $x\in\mathsf{X}_{0}$, the weak limit

exists. Moreover, $\pi_{x}$ defines a regular conditional probability of $\pi$ given $x$.

As $\hat{\pi}_{x}$ is a regular conditional probability, it holds for $\mu$-a.e. $x\in\mathsf{X}$ that

We now apply Assumption 2.3 to the pair $f\,d\mu\ll d\mu$ and deduce that the right-hand side converges to $f(x)$ for $\mu$-a.e. $x\in\mathsf{X}$, which is (3.2). ∎

The next result is the main ingredient for the second step as sketched above: the sets $\{x_{i}\}\times U_{i}$ constructed in Lemma 3.3 will be “blown up” to rectangles in the proof of Proposition 3.5 and used to show by contraposition that $\pi\ll R$.

Let $\pi\in\Pi(\mu,\nu)$ and let $\pi=\mu(dx)\otimes\pi_{x}(dy)$ be a disintegration. If $\pi\not\ll\mu\otimes\nu$, then

In addition, the sets $U_{i}$ can be chosen to be disjoint, of arbitrarily small diameter, and such that $\pi_{x_{i}}(\partial U_{j})=\nu(\partial U_{j})=0$ for $i,j\in\{1,2\}$.

Let $\pi\not\ll\mu\otimes\nu$; that is, there exists a set $A\in\mathcal{B}(\mathsf{X}\times\mathsf{Y})$ with $\pi(A)>0$ and $(\mu\otimes\nu)(A)=0$. Let $A_{x}=\{y:\,(x,y)\in A\}$ denote the $x$-section, then $\nu(A_{x})=0$ for $\mu$-a.e. $x\in\mathsf{X}$. On the other hand, any $B\in\mathcal{B}(\mathsf{Y})$ satisfies $\nu(B)=\int_{\mathsf{X}}\pi_{x^{\prime}}(B)\,\mu(dx^{\prime})$. In particular, $\nu(A_{x})=0$ implies that $\pi_{x^{\prime}}(A_{x})=0$ for $\mu$-a.e. $x^{\prime}\in\mathsf{X}$. Therefore,

As $\pi(A)>0$, the set $W=\{x:\,\pi_{x}(A_{x})>0\}$ satisfies $\mu(W)>0$ and hence $\mu^{2}((W\times W)\cap F)>0$. For $(x_{1},x_{2})\in(W\times W)\cap F$ we have $\pi_{x_{i}}(A_{x_{i}})>0$ and $\pi_{x_{i}}(A_{x_{i+1}})=0$. In particular, the disjoint sets $U^{\prime}_{i}:=A_{x_{i}}\setminus A_{x_{i+1}}$ satisfy $\pi_{x_{i}}(U^{\prime}_{i})>0$ and $\pi_{x_{i}}(U^{\prime}_{i+1})=0$. By intersecting with a suitable ball, the diameter of $U^{\prime}_{i}$ can be assumed to be arbitrarily small. Finally, let $\rho=\pi_{x_{1}}+\pi_{x_{2}}+\nu$ and choose $\rho$-continuous sets $U^{\prime\prime}_{i}$ for $U^{\prime}_{i}$ as in Lemma 3.1 (iv), with $\varepsilon>0$ small enough such that the sets $U_{i}:=U^{\prime\prime}_{i}\setminus U^{\prime\prime}_{i+1}$ have the required properties; cf. Lemma 3.1 (i). ∎

The next lemma establishes that the two sides of (3.1) are comparable with a bound related to the equivalence $R_{n}\sim P_{n}$. The following notation is useful: when $k\geq 1$ and a $k$-tuple $(z_{1},\dots,z_{k})\in(\mathsf{X}\times\mathsf{Y})^{k}$ are given, and

with the cyclical convention $y_{k+1}:=y_{1}$.

Let $\pi\in\Pi(\mu,\nu)$ and $\pi\ll R\sim P:=\mu\otimes\nu$. Consider rectangles $A_{i}\in\mathcal{B}(\mathsf{X})\times\mathcal{B}(\mathsf{Y})$ for $1\leq i\leq k$ and denote $\bar{A}_{1}\times\dots\times\bar{A}_{k}:=\{(\bar{z}_{1},\dots,\bar{z}_{k}):z_{i}\in A_{i}\}$. For some $\alpha,\bar{\alpha}>0$, suppose that $dR/dP\leq\alpha$ on $A_{i}$ and $(dR/dP)^{-1}\leq\bar{\alpha}$ on $\bar{A}_{i}$, for all $i$. Then

Using the cyclical invariance of $(\pi,R)$ and the rectangular form of $A_{i}$,

We can now prove the main result of this section.

Let $(\mu_{n},\nu_{n})\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$, let $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$ and $R_{n}\sim P_{n}:=\mu_{n}\otimes\nu_{n}$. Suppose that $(\pi_{n},R_{n})$ is cyclically invariant for each $n$ and that $\pi_{n}$ converges weakly to some limit $\pi$. In particular, $\mu_{n},\nu_{n}$ converge to some limits $\mu,\nu$, and $\pi\in\Pi(\mu,\nu)$. Set $P=\mu\otimes\nu$ and suppose that $(R_{n},P_{n})$ are uniformly locally equivalent in the following sense: there are versions $\frac{dR_{n}}{dP_{n}}:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$ of the relative densities and constants $\alpha_{n}>0$ such that given $z\in\operatorname{spt}P$, there exist $r=r(z)>0$ and $n_{0}=n_{0}(z,r)$ with

Note that the weak convergence of $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$ implies the weak convergence of its marginals to some limits $\mu$ and $\nu$, and then $\pi\in\Pi(\mu,\nu)$. By Lemma 3.2, there is a set $\mathsf{X}_{0}\subset\operatorname{spt}\mu$ of full $\mu$-measure such that for $x\in\mathsf{X}_{0}$, the weak limit

exists, and $\pi=\mu\otimes_{x}\pi_{x}$ is a disintegration of $\pi$. In particular, for any $x\in\mathsf{X}_{0}$ and any $\pi_{x}$-continuity set $U$,

Suppose for contradiction that $\pi\not\ll\mu\otimes\nu$. Then Lemma 3.3 yields $x_{i}\in\mathsf{X}_{0}$ ($i=1,2$) and disjoint sets $U_{i}$ such that

Moreover, given $r_{0}>0$, the sets $U_{i}$ can be chosen to be $(\pi_{1}+\pi_{2}+\nu)$-continuous and contained in a ball $B_{r_{0}}(y_{i})$ around some $y_{i}\in\operatorname{spt}\nu$. Using also (3.5), we can choose $r_{0},n_{0}$ such that for some $\alpha_{*}>0$,

for all $1\leq i\leq k$ and $n\geq n_{0}$. Writing $B_{i,r}:=B_{r}(x_{i})$ for brevity, (3.6) implies in particular that

That is, given $\varepsilon>0$, choosing $r\leq r_{0}$ small enough results in

and we may further choose $r$ such that $\mu(\partial B_{i,r})=0$. Specifically, we choose $\varepsilon>0$ such that $\varepsilon/(q-\varepsilon)<\alpha_{*}^{-2}$, then (3.8) implies

Note that $B_{i,r}\times U_{j}$ is a $\pi$-continuity set for $i,j\in\{1,2\}$; cf. Lemma 3.1 (iii). In view of $\pi_{n}\to\pi$, it then follows that

for $n$ sufficiently large. On the other hand, we apply Lemma 3.4 with $k=2$ and $A_{i}=B_{i,r}\times U_{i}$. In view of (3.7), the condition of the lemma holds with $\alpha:=\alpha_{n}^{-1}\alpha_{*}$ and $\bar{\alpha}:=\alpha_{n}\alpha_{*}$. Noting that the $\alpha_{n}$ cancel to yield $(\alpha\bar{\alpha})^{k}=\alpha_{*}^{4}$, the lemma yields the inequality opposite to (3.9), a contradiction. ∎

Cyclical Invariance of Limits

In this section we aim to show that limits of cyclically invariant couplings are again cyclically invariant, under suitable conditions. We proceed in two steps. First, we establish that limits are weakly cyclically invariant as defined below. Second, we show that weak cyclical invariance already implies cyclical invariance. This second step has little to do with the passage to the limit; rather, it settles some measure-theoretic aspects to get rid of pesky nullsets.

The “weak” notion is introduced mainly to disentangle the proof of the main result. It weakens in two ways the cyclical invariance of $(\pi,R)$ as stated in Definition 2.1: the equivalence of $\pi$ and $R$ is reduced to absolute continuity and the cyclical relation only holds for points from specific sets. We recall the notation $\bar{z}_{i}$ from (3.3).

Let $\pi\in\Pi(\mu,\nu)$ and $R\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$. We call $(\pi,R)$ weakly cyclically invariant if $\pi\ll R\sim P:=\mu\otimes\nu$ and there exist

a version $Z:\mathsf{X}\times\mathsf{Y}\to[0,\infty]$ of the density $d\pi/dR$,

$\Omega_{1},\Omega_{0}\in\mathcal{B}(\mathsf{X}\times\mathsf{Y})$ with $\pi(\Omega_{1})=R(\Omega_{0})=1$ and $0<Z<\infty$ on $\Omega_{1}$

Let $(\mu_{n},\nu_{n})\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$, let $\pi_{n}\in\Pi(\mu_{n},\nu_{n})$ and $R_{n}\sim P_{n}:=\mu_{n}\otimes\nu_{n}$. Suppose that $(\pi_{n},R_{n})$ is cyclically invariant for each $n$ and that $\pi_{n},R_{n}$ converge weakly to some limits $\pi,R$. In particular, $\mu_{n},\nu_{n}$ converge to some limits $\mu,\nu$, and $\pi\in\Pi(\mu,\nu)$. Suppose that $R\sim P:=\mu\otimes\nu$ and that there are versions $f_{n},f:\Omega\to(0,\infty)$ of the densities $\frac{dR_{n}}{dP_{n}},\frac{dR}{dP}$ and constants $\alpha_{n}>0$ such that for any fixed $z\in\operatorname{spt}R$,

where $o(1)$ stands for a function $\phi_{z}(z^{\prime},n)\to 0$ as $d(z^{\prime},z)+1/n\to 0$. Then $(\pi,R)$ is weakly cyclically invariant. Specifically, the quantities $\Omega_{1},\Omega_{0},Z$ of Definition 4.1 can be chosen as

Assumption 2.3 for the space $\mathsf{X}\times\mathsf{Y}$ shows that $Z$ is a version of $d\pi/dR$ and $R(\Omega_{0})=1$. As (4.1) implies (3.5), Proposition 3.5 yields that $\pi\ll P$, hence $\pi\ll R$ and the definition of $\Omega_{1}$ implies $\pi(\Omega_{1})=1$.

Let $z_{1},\dots,z_{k}\in\Omega_{1}$ be such that $\bar{z}_{i}\in\Omega_{0}$ and consider for $r>0$ the balls $A_{i}=A_{i}^{(r)}:=B_{r}(z_{i})=B_{r}(x_{i})\times B_{r}(y_{i})$. To avoid unwieldy formulas, we use the vector notation

together with the convention that functions and measures are evaluated by multiplication over the components, for instance

As $d\pi_{n}/dP_{n}=(d\pi_{n}/dR_{n})(dR_{n}/dP_{n})$, we then have

We also have $\pi_{n}(A_{i})>0$ for $n$ large as $Z(z_{i})>0$ and $\pi_{n}\to\pi$. On the other hand, $Z_{n}(\bm{z}^{\prime})$ and $P_{n}(d\bm{z}^{\prime})$ are invariant under $\bm{z}^{\prime}\mapsto\bm{\bar{z}}^{\prime}$ due to the assumption on $\pi_{n}$ and the form of $P_{n}$; cf. (3.4). Thus

Applying the assumption on $f_{n}$ to each of the points $z_{i},\bar{z}_{i}$ then yields

where $o(1)$ stands for a function of $(\bm{z},\bm{\bar{z}})$ converging to zero as $r+1/n\to 0$. For values of $r>0$ such that $A_{i},\bar{A}_{i}$ are continuity sets of $P$ (and hence also of $\pi$ and $R$), taking $n\to\infty$ yields

On the other hand, $z_{i},\bar{z}_{i}\in\Omega_{0}$ also guarantees that $\frac{R(A_{i})}{P(A_{i})}=[1+o(1)]f({z}_{i})$ and similarly for $\bar{z}_{i}$. Recalling $P(\bm{\bar{A}})=P(\bm{A})$, we deduce

and then letting $r\to 0$ (along a sequence of $r$ such that $A_{i},\bar{A}_{i}$ are continuity sets of $P$) shows $Z(\bm{z})=Z(\bm{\bar{z}})$, as desired. ∎

Assumption (4.1) on $f_{n},f$ in Proposition 4.2 is a sufficient condition for

it can be replaced by any other condition implying (4.4). We note that (4.4) can be seen as a differentiation of measures intertwined with a weak limit.

As mentioned above, the second step is to upgrade the weak cyclical invariance. Some of these considerations are similar to arguments in the proofs of , where it is shown by variational arguments that minimizers of certain static Schrödinger bridge problems admit a factorization.

Let $\pi\in\Pi(\mu,\nu)$ and let $R\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$ satisfy $R\sim P:=\mu\otimes\nu$. The following are equivalent:

$(\pi,R)$ is weakly cyclically invariant,

there exist Borel functions $\varphi:\mathsf{X}\to(0,\infty)$ and $\psi:\mathsf{Y}\to(0,\infty)$ such that $(x,y)\mapsto\varphi(x)\psi(y)$ is a version of the density $d\pi/dR$.

The implications $(i)\Rightarrow(ii)$ and $(iii)\Rightarrow(i)$ are immediate. The fact that $(i)\Rightarrow(iii)$ is also well known, cf. , but will not be used directly. For the proof of $(ii)\Rightarrow(iii)$, a measure-theoretic fact will be useful. Given a set $A\subset\mathsf{X}\times\mathsf{Y}$ with $P(A)=1$, Lemma 4.5 below states that within any set $B$ of positive measure we can find a point $(x_{*},y_{*})$ which acts like an airline hub for $A$: any two points of $A$ are connected through $(x_{*},y_{*})$, modulo marginal nullsets. In particular, any trip can be achieved with at most one stopover, and we may stop within $B$. (The bound of one is optimal as the set $A$ need not be a rectangle; in fact, $A$ may fail to contain any measurable rectangle of positive measure [22, Exercise 5.4, p. 74].) Lemma 4.5 is refinement of [6, Lemma 4.3] which asserts the connectedness of $A$ in the sense of —in our analogy, connectedness means that any trip between two points of $A$ can be achieved with finitely many stopovers at some points in $A$.

Let $P=\mu\otimes\nu$ and let $A,B\subset\mathsf{X}\times\mathsf{Y}$ be Borel sets with $P(B)>0$ and $P(A)=1$. There are Borel sets $\mathsf{X}_{0}\subset\mathsf{X}$ and $\mathsf{Y}_{0}\subset\mathsf{Y}$ with $\mu(\mathsf{X}_{0})=\nu(\mathsf{Y}_{0})=1$ such that setting $A_{0}:=A\cap(\mathsf{X}_{0}\times\mathsf{Y}_{0})$ and $B_{0}:=B\cap(\mathsf{X}_{0}\times\mathsf{Y}_{0})$, there exists a point

$(x_{*},y_{*})\in B_{0}$ such that $(x,y_{*}),(x_{*},y)\in A_{0}$ for any $(x,y)\in\mathsf{X}_{0}\times\mathsf{Y}_{0}$.

Let $C_{x}=\{y:(x,y)\in C\}$ denote the section of a set $C\subset\mathsf{X}\times\mathsf{Y}$ at $x\in\mathsf{X}$, and analogously for $y\in\mathsf{Y}$. Let $\mathsf{X}_{1}=\{x\in\mathsf{X}:\nu(A_{x})=1\}$. In view of Fubini’s theorem, $P(A)=1$ implies $\mu(\mathsf{X}_{1})=1$. Similarly, $P(B)>0$ implies that $\{x\in\mathsf{X}:\nu(B_{x})>0\}$ has positive $\mu$-measure. In particular, there exists a point $x_{*}\in\mathsf{X}_{1}$ with $\nu(B_{x_{*}})>0$.

Next, let $\mathsf{Y}_{0}=\{y\in\mathsf{Y}:\mu(A_{y})=1\}\cap A_{x_{*}}$. Then again $\nu(\mathsf{Y}_{0})=1$, and in particular there exists a point $y_{*}\in\mathsf{Y}_{0}\cap B_{x_{*}}$. Moreover, the set $\mathsf{X}_{0}:=\mathsf{X}_{1}\cap A_{y_{*}}$ satisfies $\mu(\mathsf{X}_{0})=1$. By passing to Borel subsets of full measure, we may assume that $\mathsf{X}_{0},\mathsf{Y}_{0}$ are themselves Borel.

Writing $A_{0}=A\cap(\mathsf{X}_{0}\times\mathsf{Y}_{0})$ and $B_{0}=B\cap(\mathsf{X}_{0}\times\mathsf{Y}_{0})$, we have by construction that $(x_{*},y_{*})\in B_{0}$ satisfies $(x_{*},y)\in A_{0}$ for all $y\in\mathsf{Y}_{0}$ and $(x,y_{*})\in A_{0}$ for all $x\in\mathsf{X}_{0}$. ∎

Let $Z,\Omega_{1},\Omega_{0}$ be as in Definition 4.1. Our aim is to find Borel functions $\varphi:\mathsf{X}\to(0,\infty)$ and $\psi:\mathsf{Y}\to(0,\infty)$ such that $Z^{\prime}(x,y):=\varphi(x)\psi(y)$ defines a version of the density $d\pi/dR$. It is sufficient to construct $\varphi$ on a Borel set $\mathsf{X}_{0}\subset\mathsf{X}$ of full marginal measure, as we may then extend $\varphi$ by setting $\varphi=1$ on $\mathsf{X}\setminus\mathsf{X}_{0}$, and similarly for $\psi$. In particular, we may assume that $\operatorname{proj}_{\mathsf{X}}\Omega_{1}=\mathsf{X}$ and $\operatorname{proj}_{\mathsf{Y}}\Omega_{1}=\mathsf{Y}$.

Noting that $P(\Omega_{1})>0$ due to $\pi\ll P$, we can apply Lemma 4.5 to $\Omega_{1}$ and $\Omega_{0}$, and in view of the above observation, we may assume that $\mathsf{X}_{0}=\mathsf{X}$ and $\mathsf{Y}_{0}=\mathsf{Y}$ in its assertion. We then obtain a point

$(x_{*},y_{*})\in\Omega_{1}$ such that $(x,y_{*}),(x_{*},y)\in\Omega_{0}$ for any $(x,y)\in\mathsf{X}\times\mathsf{Y}$.

Define $\varphi(x_{*}):=a>0$ as an arbitrary number and $\psi(y_{*}):=Z(x_{*},y_{*})/\varphi(x_{*})$. Given $(x,y)\in\mathsf{X}\times\mathsf{Y}$, we have $(x_{*},y)\in\Omega_{0}$ and $(x,y_{*})\in\Omega_{0}$, allowing us to define

The fact that $Z$ is Borel readily implies that $\varphi,\psi$ are Borel. Define $Z^{\prime}(x,y):=\varphi(x)\psi(x)$ for $(x,y)\in\mathsf{X}\times\mathsf{Y}$. Clearly $Z^{\prime}$ is Borel and takes values in $(0,\infty)$. Let $(x,y)\in\Omega_{1}$. Then $(x,y_{*}),(x_{*},y)\in\Omega_{0}$ and weak cyclical invariance yields

That is, $Z^{\prime}=Z$ on $\Omega_{1}$. To prove the same relation on $\Omega_{0}$, consider $(x,y)\in\Omega_{0}$. There are $x^{\prime}\in\mathsf{X}$ and $y^{\prime}\in\mathsf{Y}$ such that $z_{1}:=(x,y^{\prime})$ and $z_{2}:=(x^{\prime},y)$ are in $\Omega_{1}$, and of course we also have $z_{3}:=(x_{*},y_{*})\in\Omega_{1}$. Thus the already established fact that $Z^{\prime}=Z$ on $\Omega_{1}$ implies

On the other hand, $\bar{z}_{1}=(x,y)$ and $\bar{z}_{2}=(x^{\prime},y_{*})$ and $\bar{z}_{3}=(x_{*},y^{\prime})$ are all in $\Omega_{0}$, so that the invariance yields

As a result, $Z^{\prime}(x,y)=\varphi(x)\psi(y)=Z(x,y)$, showing $Z^{\prime}=Z$ on $\Omega_{0}$. Recalling $R(\Omega_{0})$=1, it follows that $Z^{\prime}$ is again a version of $d\pi/dR$. ∎

Proof of Main Results and Ramifications

For ease of reference, we first summarize some known results.

Let $(\mu,\nu)\in\mathcal{P}(\mathsf{X})\times\mathcal{P}(\mathsf{Y})$, $R\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$ and $R\sim P:=\mu\otimes\nu$.

If the static Schrödinger bridge problem (2.1) is finite, it admits a unique minimizer $\pi\in\Pi(\mu,\nu)$. Moreover, $(\pi,R)$ is cyclically invariant.

Let $\pi\in\Pi(\mu,\nu)$. If $(\pi,R)$ is cyclically invariant and (2.1) is finite, then $\pi$ is its minimizer.

There exists at most one $\pi\in\Pi(\mu,\nu)$ such that $(\pi,R)$ is cyclically invariant.

Recall that cyclical invariance of $(\pi,R)$ is equivalent a factorization of the density $d\pi/dR$ into strictly positive functions; cf. Proposition 4.4 or . Taking that into account, (i) and (ii) can be found in [40, Theorem 2.1] in the stated generality. (The original results are due to , among others.) Finally, (iii) follows from (ii), as was also noted in [40, Corollary 2.9]: if $\pi,\pi^{\prime}\in\Pi(\mu,\nu)$ have positive densities $d\pi/dR$, $d\pi^{\prime}/dR$ admitting factorizations, then $d\pi/d\pi^{\prime}$ also admits a factorization and now (ii), applied with $\pi^{\prime}$ as reference measure, implies that $\pi$ is the unique minimizer of $H(\cdot|\pi^{\prime})$. As $\pi^{\prime}\in\Pi(\mu,\nu)$ is itself a coupling, this minimizer is $\pi^{\prime}$. ∎

Given data as in Theorem 2.5, the sequences $(\mu_{n})$ and $(\nu_{n})$ are tight, which readily implies the tightness of $(\pi_{n})$; cf. [52, Lemma 4.4, p. 44]. In view of Propositions 4.2 and 4.4, any cluster point $\pi$ is such that $(\pi,R)$ is cyclically invariant. The uniqueness of cyclically invariant couplings, see Lemma 5.1 (iii), shows that all cluster points coincide and hence that the original sequence $(\pi_{n})$ converges. This proves Theorem 2.5.

To deduce Theorem 1.4 from Theorem 2.5, we choose the reference measure as in (2.2); i.e.,

where $a_{n},a$ are the normalizing constants. Combining the uniform convergence $c_{n}/\varepsilon_{n}\to c/\varepsilon$ on bounded sets with the continuity of $c$, we see that (2.4) holds, for instance with $\alpha_{n}=a_{n}/a$.

The uniqueness part of Theorem 2.4, as well as its last assertion, are stated in Lemma 5.1. To deduce existence from Theorem 2.5, we consider the constant marginals $(\mu_{n},\nu_{n}):=(\mu,\nu)$ and define approximating reference measures $R_{n}$ via

where $a_{n}$ is the (finite) normalizing constant. As $\frac{dR}{dP}$ is continuous and positive, hence bounded away from zero on small balls, the condition (2.4) is satisfied with $P_{n}=P$ and a function $o(1)$ independent of $n$. The static Schrödinger bridge problem (2.1) for $R_{n}$ falls into the classical setting of Lemma 5.1 (i) because the product coupling $\pi_{0}:=\mu\otimes\nu$ satisfies $H(\pi_{0}|R_{n})<\infty$. In particular, the associated cyclically invariant couplings $\pi_{n}\in\Pi(\mu,\nu)$ exist, and now Theorem 2.5 implies the existence of $\pi\in\Pi(\mu,\nu)$ such that $(\pi,R)$ is cyclically invariant. Finally, Theorem 1.3 is a direct consequence of Theorem 2.4 via (2.2). ∎

Define $R\in\mathcal{P}(\mathsf{X}\times\mathsf{Y})$ by $dR/dP:=f$ and let $\pi$ be as in Theorem 2.4. As $(\pi,R)$ is cyclically invariant, a version of the relative density admits a factorization $d\pi/dR(x,y)=\varphi(x)\psi(y)$ into positive Borel functions; cf. Proposition 4.4. The fact that $\pi$ has marginals $(\mu,\nu)$ then translates to the fact that $(\varphi,\psi)$ solve the Schrödinger system. Uniqueness of $\varphi,\psi$ up to a constant follows from the uniqueness of $\pi$ (here the fact that $R\sim P$ is particularly important). ∎