Entropic Optimal Transport: Geometry and Large Deviations

Introduction

Over the last three decades, optimal transport theory has flourished due to its connections with geometry, analysis, probability theory, and other fields in mathematics; see for instance . Following computational advances which have enabled high-dimensional applications, a renewed interest comes from applied fields such as machine learning, image processing and statistics. Popularized in this area by Cuturi , entropic regularization is a key computational approach for high-dimensional problems. The resulting entropic optimal transport problem provides an approximate optimal transport when solved for small regularization parameter $\varepsilon>0$ while admitting much more efficient algorithms than the unregularized problem, in addition to having other desirable properties. We defer the discussion of related literature to Section 1.1 below and proceed with a synopsis of the present study.

where $\Pi(\mu,\nu)$ is the set of couplings and $H(\cdot|\mu\otimes\nu)$ denotes relative entropy (or Kullback–Leibler divergence) with respect to the product of the marginals; see Section 2 for the formal definitions. The constant $\varepsilon>0$ acts as a regularization parameter; $\varepsilon=0$ recovers the (unregularized) optimal transport problem. Under mild conditions detailed in Sections 2 and 3, respectively, the entropic optimal transport problem admits a unique solution $\pi_{\varepsilon}\in\Pi(\mu,\nu)$ and $\pi_{\varepsilon}$ converges weakly to a solution $\pi_{*}$ of the unregularized problem. Our main interest is to quantify the speed of this convergence $\pi_{\varepsilon}\to\pi_{*}$.

In the present study, we adopt a different, more local perspective, from which the Gaussian example is actually encouraging: the density of $\pi_{\varepsilon}$ decays exponentially away from $\Gamma$. Indeed, it is proportional to $e^{-\alpha|y-T(x)|^{2}/\varepsilon}$, where $\alpha>0$ is the quotient of the marginal variances.

The main result of this paper is a comparable statement in a remarkably general setting; it takes the form of a large deviations principle. We define a function $I(x,y)$ through the following optimization. In addition to the given point $(x,y)=:(x_{1},y_{1})$, choose finitely many points $(x_{2},y_{2}),\dots,(x_{k},y_{k})$ from the support $\Gamma$ of the limiting optimal transport $\pi_{*}$, as well as a permutation $\sigma\in\Sigma(k)$. Then, consider the difference

between the pointwise transport costs from $x_{i}$ to $y_{i}$ with the costs for the permuted destinations $y_{\sigma(i)}$. The optimization is to maximize this difference, and we define $I(x,y)$ as the supremum value of (1.2) over all choices of points and permutations. For $(x,y)\in\Gamma$, the optimality of $\pi_{*}$ implies that $I(x,y)=0$, because $\Gamma$ is $c$-cyclically monotone. But outside $\Gamma$, we may typically expect that $I(x,y)>0$. Part (a) of our theorem below, the large deviations upper bound, shows that $I$ is a lower bound for the rate function in the general Polish setting. The matching bound (b) necessitates a condition on the optimal transport problem that is being approximated—but still holds for the majority of continuous or semi-discrete transport problems of interest. We mainly discuss the uniqueness of Kantorovich potentials (Assumption 4.4) as a sufficient condition; it also gives rise to an insightful representation of $I$ as $I(x,y)=c(x,y)-\psi^{c}(y)+\psi(x)$, the difference between the cost $c(x,y)$ and the solution of the dual optimal transport problem (see Proposition 4.5). An alternative condition imposing regularity of the optimal transport (Assumption 4.9) is also considered. Tacitly assuming the existence of $\pi_{\varepsilon}$ and its weak limit (cf. Sections 2 and 3), the main result reads as follows.

Let $\Gamma=\operatorname{spt}\pi_{*}$ where $\pi_{*}=\lim_{\varepsilon\to 0}\pi_{\varepsilon}$ is the limiting optimal transport and define $I:\mathsf{X}\times\mathsf{Y}\to[0,\infty]$ by (4.3).

For any compact set $C\subset\mathsf{X}\times\mathsf{Y}$,

Let Assumption 4.4 or Assumption 4.9 hold, and consider the sets $\mathsf{X}_{0}=\operatorname{proj}_{\mathsf{X}}\Gamma$ and $\mathsf{Y}_{0}=\operatorname{proj}_{\mathsf{Y}}\Gamma$ of full marginal measure. For any open set $U\subset\mathsf{X}_{0}\times\mathsf{Y}_{0}$,

The theorem shows in particular that the rate depends (only) on the geometry of $\pi_{*}$, which does not seem to be clear a priori. We mention that our result can also be stated in terms of (static) Schrödinger bridges. In this context, it is a large deviations principle for the small-noise (or small-time) limit; cf. Section 1.1.

For finitely supported marginals, the density of $\pi_{\varepsilon}$ converges exponentially for any cost function; that is, the rate function is strictly positive outside $\Gamma$. We shall see that the analogue may fail in the continuous case. Rather, positivity depends on the geometry of the cost. The twist condition (injectivity of $\nabla_{x}c(x,\cdot)$) plays an important role, like in many results on optimal transport. We include affirmative positivity results in particular for quadratic costs, which is the most important case for applications. While not pursued in the present paper, our results should also be useful to derive detailed quantitative bounds on the rate in more specific settings. We may also hope to gain insights into how the rate depends on the dimension.

Geometry is a cornerstone in the now-classical theory of optimal transport, where optimality is captured geometrically by the $c$-cyclical monotonicity of a transport’s support. Defined by comparing costs at finitely many points, it yields a powerful tool to derive fundamental results such as stability of optimal transports under weak limits or existence of dual potentials. We are not aware of a comparable technique in the literature on entropic optimal transport (or on Schrödinger bridges). In this paper, we exploit a cyclical invariance property satisfied by the density of $\pi_{\varepsilon}$. The invariance itself can be understood as a reformulation of a classical characterization for $\pi_{\varepsilon}$ through the solution of the dual problem, the Schrödinger potentials. The novelty here lies in exploiting the geometric aspect and working on the primal side, following the spirit of $c$-cyclical monotonicity. Like in classical optimal transport, the arguments are remarkably simple and general once the correct notions are in place. Our technique is a departure from the control-theoretic methods in the related literature. Case in point, the geometric proof that a weak limit $\pi=\lim_{\varepsilon\to 0}\pi_{\varepsilon}$ is an optimal transport (cf. Proposition 3.2), is nearly trivial compared to the Gamma-convergence technique, even in the general Polish context. (Of course, Gamma-convergence is applicable to many other problems where our technique has no analogue.)

We also emphasize another benefit which may illustrate that cyclical invariance is in fact more than just a reformulation of control theory or convex analysis: the geometry singles out a unique coupling $\pi_{\varepsilon}$ even if the value function (1.1) is infinite and hence the usual notion of solution as a minimizer is not meaningful. This is crucial for instance if costs are quadratic but one of the marginal distributions does not have a finite second moment. Our arguments for the large deviations result apply in that setting without any added difficulty, paralleling the geometric insights in classical optimal transport. (On the other hand, the existence of $\pi_{\varepsilon}$ in the case of infinite value functions is not immediate. We establish it in , together with a stability theorem for $\pi_{\varepsilon}$, using the same geometric standpoint.) Indeed, we expect the technique to be useful in several other aspects of entropic optimal transport and Schrödinger bridges, and thus the technique may be as important a contribution as the main theorem.

The present paper is organized as follows. After reviewing motivations for our research and related literature in the remainder of this Introduction, Section 2 details the basic definitions and introduces cyclical invariance. In Section 3, this notion is used to prove that cluster points of $\pi_{\varepsilon}$ as $\varepsilon\to 0$ have $c$-cyclically monotone support, hence are optimal transports. The main result on large deviations is obtained in Section 4: part (a) of Theorem 1.1 is stated as Corollary 4.3 whereas (b) is split into Corollaries 4.7 and 4.12, each covering one of the two alternative assumptions. Section 5 gives examples of settings where the rate function $I$ is strictly positive outside the support $\Gamma$, with a focus on quadratic costs. Appendix A contains facts about Schrödinger bridges and a derivation of the cyclical invariance property. In Appendix B, we detail two general settings where Assumption 4.4 on the uniqueness of Kantorovich potentials is satisfied. Finally, Appendix C shows how to translate the results on the positivity of $I$ in Section 5 from quadratic costs to more general cost functions by means of $c$-convex analysis.

In the literature on finite-dimensional linear programs and their entropic regularization, the early work contains a very detailed study of primal and dual convergence, expansion of the value function, and characterizations of the rates. Their setting includes discrete optimal transport problems with marginals supported by finitely many points, and in that case the pointwise results in certainly include the large deviations result for $\varepsilon\to 0$. On the other hand, our main theorem is most relevant when at least one marginal support is connected, hence is complementary to the discrete case. More recently, proved an exponential convergence bound for finite-dimensional linear programs. While the bound is not sharp in a pointwise sense, the result is non-asymptotic; i.e., holds for all $\varepsilon$ below a known threshold. Moreover, the constants are known in terms of the data, which provided valuable intuition for our construction of the rate function $I$. One may also observe how the constants in blow up as the cardinality of the support increases.

Continuing with a different branch of related literature, recall that entropic optimal transport can also be phrased as the (static) Schrödinger bridge problem. Informally stated, consider a system of diffusing particles from time $t_{0}$ to $t_{1}$ in thermal equilibrium, and a given joint “reference” law $R$ for its configuration at those times. If marginals $(\mu,\nu)$ differing from the ones of $R$ are observed, what is the most likely evolution (joint law of $\mu,\nu$) of the system conditional on $R$? Schrödinger’s answer amounts to $\pi^{*}=\operatorname*{arg\,min}_{\Pi(\mu,\nu)}H(\cdot|R)$; see for extensive surveys including historical accounts. (This is the static formulation. Given the origins in physics, it is natural that much of the literature focuses on the dynamic Schrödinger bridge problem, which asks for the dynamic evolution of the particle system over time $t\in[t_{0},t_{1}]$. The static problem is recovered by projecting to the marginals.)

The minimization of $H(\cdot|R)$ over $\Pi(\mu,\nu)$ coincides with the entropic optimal transport problem (1.1) if we introduce the cost function $c:=-\varepsilon\log(\alpha^{-1}dR/d(\mu\otimes\nu))$, where the parameter $\varepsilon>0$ is arbitrary and $\alpha$ is a normalizing constant (we tacitly assume that $R\sim\mu\otimes\nu$). Conversely, taking (1.1) as the starting point, defining $R(\varepsilon)$ by $dR(\varepsilon)/d(\mu\otimes\nu)=\alpha e^{-c/\varepsilon}$ yields the associated Schrödinger bridge problem. Assuming for simplicity that $\{c=0\}$ is the graph of a function $f:\mathsf{X}\to\mathsf{Y}$, Theorem 1.1 is then a large deviations principle as the reference measure $R(\varepsilon)$ degenerates to a deterministic coupling (meaning that a particle with given origin $x$ travels to the predetermined destination $f(x)$).Schrödinger’s ideas about the “most likely evolution” are usually presented as a large deviations result in the modern literature. That result is very different from the one just discussed. This is also called the small-noise or small-time limit. While not pursued here, it seems plausible that a similar principle could be established for more general sequences $R(\varepsilon)$. From the point of view of Schrödinger bridges, another interesting follow-up question is whether a comparable large deviations result can be stated for the dynamic problem on path space.

Mikami first highlighted the connection between Schrödinger equations and optimal transport in the small-noise limit; see also for a connection through a fluid dynamic formulation. Léonard studied Schrödinger bridges in a series of works starting with ; see for further references. In , he established convergence of the value function to an optimal transport problem in the sense of Gamma-convergence for a general formulation of the problem. See also where a very accessible proof of the Gamma-convergence is presented for quadratic costs. More recently, study the limit in specific settings and determine higher-order terms in the expansion of the Schrödinger (or entropic) value function around the optimal transport cost. These works complement earlier results of showing that the large deviation rate function for the empirical distribution of independent Brownian particles with drift is asymptotically equivalent to the Jordan–Kinderlehrer–Otto functional arising in the Wasserstein gradient flow. We mention that also considers the large-time limit (corresponding to $\varepsilon\to\infty$); cf. for recent developments. The setup in is closest to ours in that the entropic penalty and the limit $\varepsilon\to 0$ are formulated in the same way, whereas the literature on Schrödinger bridges often formulates the zero-noise limit through a vanishing Laplacian. We also mention , establishing convergence of the dual potentials for compact marginals (see for a follow-up and more on the relation to the present work).

While the focus of the aforementioned works is on value functions and global quantities, the present study focuses on the local geometry and convergence. The value functions are not used at all, and so it is quite natural that the results hold even when costs are infinite. We are not aware of a large deviations principle similar to ours in the extant literature. One concrete example where these aspects are of interest, are the multidimensional ranks and quantiles that have been introduced in statistics to extend the usual scalar notions and familiar nonparametric tests; see . Here Brenier’s map is fundamental, but like in the scalar case, moment conditions are not natural. McCann’s geometric extension of Brenier’s map (see also [58, pp. 249–258]) can be used to provide a definition irrespectively of the finiteness of the value function. Unlike their scalar counterparts, the ranks defined through optimal transport are computationally expensive. Entropic optimal transport resolves that issue and provides an approximate Brenier’s map. Leveraging this idea, a notion of “differentiable ranks” based on entropic optimal transport was recently proposed in . We expect that our results can be used to study the local deviations of these differentiable ranks from the unregularized ones.

Related to our technique in a broader sense, there have been recent works successfully using ideas of $c$-cyclical monotonicity outside the setting of classical optimal transport. Examples include martingale optimal transport and optimal Skorokhod embeddings . Finally, we mention the intriguing “optimal entropy-transport problem” studied in . Here, the usual optimal transport problem is relaxed in that the marginal constraints are replaced by an entropic penalty relative to a given pair of measures. While similar in name, this problem is quite different from ours, where the marginal constraints are strictly enforced and the entropy of the joint distribution is used as penalty.

Cyclical Invariance

where $\Pi(\mu,\nu)$ is the set of all couplings; that is, probability measures $\pi$ on $\mathsf{X}\times\mathsf{Y}$ with marginals $\mu=(\operatorname{proj}_{\mathsf{X}})_{\#}\pi$ and $\nu=(\operatorname{proj}_{\mathsf{Y}})_{\#}\pi$. Given a constant $\varepsilon>0$, the entropic optimal transport problem is

where $H$ denotes the relative entropy or Kullback–Leibler divergence,

As detailed in Proposition A.1 of Appendix A, this problem admits a unique minimizer $\pi_{\varepsilon}$ whenever the value (2.2) is finite; i.e., whenever

Moreover, we then have $\pi_{\varepsilon}\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 $\frac{d\pi}{dP}:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$ such that

We omit the qualifier $(c,\varepsilon)$ when there is no ambiguity. One elementary way to motivate Definition 2.1 is to derive a first-order condition of optimality for (2.2) through variational arguments in the case of discrete marginals, which indeed yields (2.4). Cyclical invariance can be phrased more succinctly using the auxiliary reference measure $R=R(\varepsilon)$ defined by the Gibbs kernel

where $\alpha=(\int e^{-c/\varepsilon}\,dP)^{-1}$ is the normalizing constant. As $R\sim P$, we can state (2.4) as

This condition, in turn, is related to a multiplicative decomposition of the density $d\pi/dR$; cf. Appendix A. For our analysis of the limit $\varepsilon\to 0$, the less elegant definition (2.4) will be the more useful one, as it makes explicit the role of $\varepsilon$ and links directly to the $c$-cyclical monotonicity condition of optimal transport.

(a) There is at most one $(c,\varepsilon)$-cyclically invariant coupling $\pi\in\Pi(\mu,\nu)$.

(b) Let (2.3) hold. Then $\pi\in\Pi(\mu,\nu)$ is $(c,\varepsilon)$-cyclically invariant if and only if it minimizes (2.2). Moreover, there exists a unique such coupling.

The proof is detailed in Appendix A. Under Condition (2.3), Proposition 2.2 shows the equivalence between minimality and cyclical invariance. The notion of minimality is meaningful only under (2.3), otherwise all couplings have infinite cost. By contrast, we show in that the notion of cyclical invariance remains meaningful in this context of infinite costs: existence and uniqueness hold under mild regularity conditions; e.g., when $\mathsf{X},\mathsf{Y}$ are Euclidean spaces and $c$ is continuous.

In the remainder of this paper, we simply assume that a $(c,\varepsilon)$-cyclically invariant coupling $\pi_{\varepsilon}\in\Pi(\mu,\nu)$ exists for every $\varepsilon>0$, rather than imposing Condition (2.3) as in much of the literature. One reason is that this condition precludes some applications of interest to us. In any event, the arguments in this paper do not simplify if (2.3) is assumed.

Cluster Points as ε→0→𝜀0\varepsilon\to 0

Denote by $\pi_{\varepsilon}$ the unique $(c,\varepsilon)$-cyclically invariant coupling. In this section we show that cluster points of $\pi_{\varepsilon}$ as $\varepsilon\to 0$ are $c$-cyclically monotone. The estimates leading to that conclusion are obtained by simply integrating the cyclical invariance condition.

Let $k\geq 2$ and $0\leq\delta\leq\delta^{\prime}\leq\infty$. Define

and let $A\subset A_{k}(\delta,\delta^{\prime})$ be Borel. Then $\pi_{\varepsilon}^{k}:=\prod_{i=1}^{k}\pi_{\varepsilon}(dx_{i},dy_{i})$ satisfies

Suppose in addition that \bar{A}:=\big{\{}(x_{i},y_{i+1})_{i=1}^{k}:(x_{i},y_{i})_{i=1}^{k}\in A\big{\}} satisfies $\liminf_{\varepsilon\to 0}\varepsilon\log\pi_{\varepsilon}^{k}(\bar{A})=0$. Then

Set $Z=d\pi_{\varepsilon}/dP$. Using (2.4), we have for $P^{k}$-a.e. $(x_{i},y_{i})_{i=1}^{k}\in A$ that

Integrating over $A$ with respect to $P^{k}=\prod P(dx_{i},dy_{i})=\prod P(dx_{i},dy_{i+1})$ yields

which is (3.1). Analogously, $\pi_{\varepsilon}^{k}(A)\geq e^{-\delta^{\prime}/\varepsilon}\pi_{\varepsilon}^{k}(\bar{A})$ and hence

so that (3.2) follows under the stated condition on $\bar{A}$. ∎

In all that follows, probability measures are considered with weak convergence; i.e., the topology induced by bounded continuous functions. We recall that $\Pi(\mu,\nu)$ is weakly compact; cf. [58, p. 45]. As a consequence, any sequence of couplings admits at least one cluster point, and any cluster point is a coupling. A set $\Gamma\subset\mathsf{X}\times\mathsf{Y}$ is called $c$-cyclically monotone if $\sum_{i=1}^{k}c(x_{i},y_{i})\leq\sum_{i=1}^{k}c(x_{i},y_{i+1})$ for all $k\geq 1$ and $(x_{i},y_{i})\in\Gamma$, $1\leq i\leq k$.

Let $c$ be continuous and let $\pi$ be a cluster point of $(\pi_{\varepsilon})$ as $\varepsilon\to 0$. Then $\operatorname{spt}\pi$ is $c$-cyclically monotone, hence $\pi$ is an optimal transport as soon as the optimal transport problem (2.1) is finite. If (2.1) admits a unique $c$-cyclically monotone coupling $\pi_{*}\in\Pi(\mu,\nu)$, then $\pi_{\varepsilon}\to\pi_{*}$ as $\varepsilon\to 0$.

Rate Function

Throughout this section, the cost function $c$ is assumed to be continuous. For simplicity of exposition, we shall also assume that

for some (necessarily $c$-cyclically monotone) transport $\pi_{*}\in\Pi(\mu,\nu)$. However, if it is merely known that $\pi_{\varepsilon_{n}}\to\pi_{*}$ along a specific sequence $\varepsilon_{n}\to 0$, then all of our results hold along that sequence, regardless of whether $(\pi_{\varepsilon})$ has other cluster points. In fact, the arguments in this paper are complementary to the question of convergence discussed in the preceding paragraph: given the convergence of a sequence, we describe the large deviations.

In this subsection we introduce the function $I$ and show the large deviations upper bound; i.e., that $I$ provides a lower bound for the large deviations rate. With the definitions in place, the arguments are straightforward and apply in great generality. We write $B_{r}(z)$ for the open ball of radius $r$ around $z$, in any metric space. The first lemma is a way to bound the decay of a ball in $\mathsf{X}\times\mathsf{Y}$ based on the estimate for subsets of $(\mathsf{X}\times\mathsf{Y})^{k}$ in Lemma 3.1.

Let $(x,y)\in\mathsf{X}\times\mathsf{Y}$. Suppose there exist $(x_{i},y_{i})_{2\leq i\leq k}\subset\operatorname{spt}\pi_{*}$ with $k\geq 2$ such that

Given $\delta<\delta_{0}$, there exist $\alpha,r,\varepsilon_{0}>0$ such that

For $i\geq 2$ we have $\liminf\pi_{\varepsilon}(B_{i})\geq\pi_{*}(B_{i})$ due to the weak convergence $\pi_{\varepsilon}\to\pi_{*}$, and $\beta_{i}:=\pi_{*}(B_{i})>0$ as $(x_{i},y_{i})\in\operatorname{spt}\pi_{*}$. Let $\beta=\min_{i\geq 2}\beta_{i}$. Then $\pi_{\varepsilon}(B_{i})\geq\beta/2$ for $i\geq 2$ and $\varepsilon$ small, and thus (4.2) yields $\pi_{\varepsilon}(B_{1})\leq(\beta/2)^{1-k}e^{-\delta/\varepsilon}$. ∎

Denote by $\Sigma(k)$ the set of permutations of $\{1,\dots,k\}$. Next, we state the definition of $I(x,y)$; it is designed to capture the rate $\delta$ in Lemma 4.1 and optimize it over the choice of $(x_{i},y_{i})_{2\leq i\leq k}$.

Given a $c$-cyclically monotone set $\emptyset\neq\Gamma\subseteq\mathsf{X}\times\mathsf{Y}$, define

where $(x_{1},y_{1}):=(x,y)$. Then $I:\mathsf{X}\times\mathsf{Y}\to[0,\infty]$ is lower semicontinuous and $I=0$ on $\Gamma$. We have

and equality holds as soon as $x\in\mathsf{X}_{0}:=\operatorname{proj}_{\mathsf{X}}\Gamma$ or $y\in\mathsf{Y}_{0}:=\operatorname{proj}_{\mathsf{Y}}\Gamma$.

We have $I\geq 0$ as $\sigma=\operatorname{Id}$ is a possible choice in (4.3). For $(x,y)\in\Gamma$, the difference of sums in (4.3) is nonpositive by cyclical monotonicity. The semicontinuity follows from the continuity of $c$.

Let $I^{\prime}(x,y)$ be the right-hand side of (4.4). As the pairs $(x_{i},y_{i})_{i=2}^{k}$ can be relabeled arbitrarily, this is the same as (4.3) except that the last supremum in (4.4) is taken over $\sigma\in\Sigma(k)\setminus\{\operatorname{Id}\}$. If $I(x,y)>0$, the identity permutation is not optimal for the relevant pairs $(x_{i},y_{i})_{i=2}^{k}$ and equality must hold in (4.4). Thus, if equality fails, then $I(x,y)=0$ whereas $I^{\prime}(x,y)<0$. Let $x\in\mathsf{X}_{0}$, then we can choose $k=2$ and $(x_{2},y_{2})\in\Gamma$ with $x_{2}=x$, which yields $\sum_{i=1}^{2}c(x_{i},y_{i})-\sum_{i=1}^{2}c(x_{i},y_{i+1})=0$ and hence $I^{\prime}(x,y)\geq 0$. The argument for $y\in\mathsf{Y}_{0}$ is symmetric. ∎

The reader may ignore the difference between (4.3) and (4.4); it is merely a notational nuisance. We have the following result for the $c$-cyclically monotone set $\Gamma:=\operatorname{spt}\pi_{*}$, also stated as Theorem 1.1 (a) in the Introduction.

For any compact set $C\subset\mathsf{X}\times\mathsf{Y}$,

Fix $\eta>0$ and $(x,y)\in C$. By the definition of $I(x,y)$ there are $k\geq 1$ and $(x_{i},y_{i})_{i=2}^{k}\subset\Gamma$ such that

where $(x_{1},y_{1}):=(x,y)$ and $I_{\eta}(x,y):=I(x,y)\wedge\eta^{-1}$. (The truncation is needed only if $I(x,y)=\infty$.) Lemma 4.1 thus yields a ball $B_{r}(x,y)$ with

This holds for every $(x,y)\in C$, and as $C$ is covered by finitely many such balls, we deduce that

Recalling that $\eta>0$ was arbitrary, the claim follows. ∎

We note that the measure $\pi_{*}=\lim_{\varepsilon}\pi_{\varepsilon}$ is not compactly supported in general. It is then an open problem how to relax the compactness condition in Corollary 4.3 and hence obtain a “stronger” version of the large deviations principle.

2 Large Deviations Lower Bound

Our next aim is to show that $I$ is also an upper bound for the large deviations rate, thus matching the bound in Corollary 4.3. This will be accomplished in two slightly different settings and approaches. The dual approach expresses $I$ as the gap (4.6) between the cost $c$ and the solution of the dual optimal transport problem, whereas the primal directly uses the definition (4.3) of $I$ and imposes regularity conditions. The results correspond to Theorem 1.1 (b) in the Introduction.

We start with the dual approach, first recalling some standard notions of optimal transport—we have tried to consistently use the notation of . A proper function $\psi:\mathsf{X}\to(-\infty,\infty]$ is called $c$-convex if there exists some $\zeta:\mathsf{Y}\to[-\infty,\infty]$ such that $\psi(x)=\sup_{y\in\mathsf{Y}}[\zeta(y)-c(x,y)]$ for all $x\in\mathsf{X}$. Its $c$-conjugate is defined by $\psi^{c}(y):=\inf_{x\in\mathsf{X}}[\psi(x)+c(x,y)]$ for $y\in\mathsf{Y}$, and its $c$-subdifferential is

Given a $c$-cyclically monotone set $\Gamma$, a $c$-convex function $\psi$ is called a Kantorovich potential if $\Gamma\subset\partial_{c}\psi$; that is, if $\psi^{c}(y)-\psi(x)=c(x,y)$ on $\Gamma$. This implies in particular that $\psi,\psi^{c}$ are finite on

In the context of optimal transport, $\operatorname{spt}\pi\subset\partial_{c}\psi$ for some optimal $\pi\in\Pi(\mu,\nu)$ implies that $\partial_{c}\psi$ contains the support of any optimal transport. Indeed, $\partial_{c}\psi$ is a maximal $c$-monotone set for inclusion. In what follows, the cyclically monotone set of interest is $\Gamma=\operatorname{spt}\pi_{*}$, where $\pi_{*}$ is the limiting optimal transport (4.1).

Uniqueness of Kantorovich potentials holds on $\mathsf{X}_{0}$; that is, for any $c$-convex functions $\psi_{1},\psi_{2}$ on $\mathsf{X}$ with $\Gamma\subset\partial_{c}\psi_{i}$, it holds that $\psi_{1}-\psi_{2}$ is constant on $\mathsf{X}_{0}$.

This is often considered a fairly weak assumption, at least for differentiable cost functions, and we detail sufficient conditions in Proposition B.2 of Appendix B. However, we emphasize that connectedness of at least one marginal support is crucial (cf. Example 4.8 below).

As announced, Assumption 4.4 allows us to express $I$ through the Kantorovich potential; see (4.6). For our present purpose, the key consequence is (4.7). It is worth noting that (4.6) also allows us to translate a large body of known results about $c$-convex functions, such as regularity results, into statements about $I$. Finally, the gap (4.6) also plays a role in the regularity theory of optimal transport maps (especially in ), thus relating to the second approach in Section 4.2.2 below.

for any Kantorovich potential $\psi$. In particular, $I<\infty$ on $\mathsf{X}_{0}\times\mathsf{Y}_{0}$. If $(x,y),(x^{\prime},y^{\prime})\in\mathsf{X}_{0}\times\mathsf{Y}_{0}$ are such that $(x^{\prime},y),(x,y^{\prime})\in\Gamma$, then

We first elaborate on Assumption 4.4. A particular family of Kantorovich potentials, sometimes called Rockafellar antiderivatives of $\Gamma$, is defined as follows (cf. [58, Equation (5.17), p. 65]): fix $(x_{0},y_{0})\in\Gamma$ and set

It then holds that $\psi_{(x_{0},y_{0})}(x)=0$ for $x=x_{0}$. Clearly Assumption 4.4 implies that changing the reference point $(x_{0},y_{0})$ only changes this potential by a constant. In particular,

does not depend on $(x_{0},y_{0})\in\Gamma$, and we may simply write $\Psi:=\Psi_{(x_{0},y_{0})}$. Indeed, under Assumption 4.4, $\Psi$ is even the same for any potential $\psi$.

We now use this independence to prove the lemma. To avoid notational conflict, we first rewrite the definition (4.8) as

where we have used the last part of Lemma 4.2. In view of $\psi_{(\bar{x},y)}(\bar{x})=0$, the fact that $\Psi_{(\bar{x},y)}=c$ on $\Gamma$ shows in particular that $c(\bar{x},y)=\psi^{c}_{(\bar{x},y)}(y)$, and hence the preceding display yields

By the first part of the proof, $\Psi_{(\bar{x},y)}(\cdot)=\Psi(\cdot)$ does not depend on $(\bar{x},y)$ and the above is precisely (4.6).

To see (4.7), let $(x^{\prime},y),(x,y^{\prime})\in\Gamma$. Using that $I=0$ on $\Gamma$ by Lemma 4.2 and then (4.6),

where the last line vanishes as $\Psi$ is a sum of marginal functions (4.9). ∎

The proof of Proposition 4.5 is based on the condition that

which may seem weaker than Assumption 4.4. However, Assumption 4.4 is in fact equivalent to (4.11); the proof is stated below. As a direct consequence, another equivalent condition is that the Rockafellar antiderivative (4.8) be independent of $(x_{0},y_{0})$. The symmetry of (4.11) shows that it is further equivalent to impose the analogue of Assumption 4.4 on $\mathsf{Y}$ instead of $\mathsf{X}$.

By construction, the Rockafellar antiderivative $\psi_{0}:=\psi_{(x_{0},y_{0})}$ of (4.8) has the minimality property $\psi_{0}\leq\xi$ on $\mathsf{X}_{0}$ whenever $\xi$ is a potential with $\xi(x_{0})=0=\psi_{0}(x_{0})$. (See [58, p. 62], or for a more general result and further context.) Consider another point $(x_{1},y_{1})\in\Gamma$, let $\psi_{1}:=\psi_{(x_{1},y_{1})}$ and let $\xi$ be any potential. Using the minimality twice,

Given (4.11), the right-hand side can be expressed as

which is the left-hand side. It follows that $\psi_{0}(x_{1})-\psi_{0}(x_{0})=\xi(x_{1})-\xi(x_{0})$ for any potential $\xi$, and as $x_{0},x_{1}\in\mathsf{X}_{0}$ were arbitrary, Assumption 4.4 holds. ∎

We can now show the large deviations lower bound.

Let Assumption 4.4 hold. For any open set $U\subset\mathsf{X}_{0}\times\mathsf{Y}_{0}$,

It suffices to show that given $(x,y)\in U$ and $\eta>0$, there exists $r_{0}>0$ such that for all $r<r_{0}$,

Let $\eta>0$, pick any $(x^{\prime},y^{\prime})\in\mathsf{X}_{0}\times\mathsf{Y}_{0}$ such that $(x^{\prime},y),(x,y^{\prime})\in\Gamma$, and set

We have $I(x,y)<\infty$ and $I(x^{\prime},y^{\prime})<\infty$ by Proposition 4.5. For $r>0$ small enough we may use Lemma 3.1 with $\delta^{\prime}:=\alpha+\eta/2$ and $B_{r}(x,y)\times B_{r}(x^{\prime},y^{\prime})\subset A_{2}(0,\delta^{\prime})$ to obtain

On the other hand, for $r$ small enough, Lemma 4.1 yields as in (4.5) that

Using (4.12), then (4.7) and finally (4.13),

The following simple example shows that if both marginals supports are disconnected (and Assumption 4.4 is violated), $I$ may fail to be an upper bound for the rate function.

Consider the normalized $2\times 2$ assignment problem: $\mathsf{X}=\mathsf{Y}=\{1,2\}$ and $\mu=\nu=(\delta_{\{1\}}+\delta_{\{2\}})/2$. Here $\Pi(\mu,\nu)$ is the convex hull of the two couplings

In particular, every $\pi\in\Pi(\mu,\nu)$ is symmetric: $\pi\{(1,2)\}=\pi\{(2,1)\}$. Consider a cost function $c$ with $c(1,1)=c(2,2)=0$ and $c(1,2)+c(2,1)>0$. Then $\pi_{*}$ is the unique optimal transport and we know that $\pi_{\varepsilon}\to\pi_{*}$. Let

be the exponential rate of convergence. Using Lemma 3.1 with

for $\delta:=c(1,2)+c(2,1)>0$ shows $r(1,2)+r(2,1)=\delta$. As $\pi_{\varepsilon}$ must be symmetric, we conclude that the true exponential rate is

(A priori, it may not be obvious that the limit (4.14) exists, but a posteriori, this is justified as every subsequential limit leads to the same value.) On the other hand, the definition (4.3) of $I$ readily yields that $I\equiv 0$.

2.2 Bound via Regularity

In the remainder of the section we present an alternative approach to the large deviations lower bound which does not (directly) refer to potentials but instead employs a continuity condition for the limiting optimal transport $\pi_{*}$. We call a subset of a metric space arcwise connected if any two points are connected by a continuous curve of finite length.

(a) $\Gamma=\operatorname{graph}T$ for a map $T:\mathsf{X}_{0}\to\mathsf{Y}$.

(b) $\mathsf{X}_{0}$ is arcwise connected.

(c) The function $c(\cdot,T(\cdot))$ has the following continuity property: given a compact $K\subset\mathsf{X}_{0}$, we have uniformly over $x_{1},x_{2}\in K$ that

and $T$ is uniformly continuous on compact sets. General sufficient conditions for the continuity of $T$ can be found in [19, Theorem 1].

Next, we show how to establish the key half of (4.7) under Assumption 4.9.

Let Assumption 4.9 hold. If $(x,y),(x^{\prime},y^{\prime})\in\mathsf{X}_{0}\times\mathsf{Y}_{0}$ are such that $(x^{\prime},y),(x,y^{\prime})\in\Gamma$, then

Set $(x_{1},y_{1}):=(x,y)$ and $(x^{\prime}_{1},y^{\prime}_{1}):=(x^{\prime},y^{\prime})$. Let $k\geq 2$ and consider arbitrary $(x_{i},y_{i}),(x^{\prime}_{i},y^{\prime}_{i})\in\Gamma$ for $2\leq i\leq k$. The definition of $I$ yields that

This holds in particular for the choices $x_{k}:=x^{\prime}$ and $x^{\prime}_{k}:=x$, which entail that $y_{k}=T(x^{\prime})=y$ and $y^{\prime}_{k}=T(x)=y^{\prime}$. Moreover, we have $y_{i}=T(x_{i})$ and $y^{\prime}_{i}=T(x^{\prime}_{i})$ for $i\geq 2$. Separating the first term of the first sum and the last term of the second sum, we obtain that

We further choose $x^{\prime}_{i}:=x_{k-i+1}$ for $i=2,\dots,k-1$, which implies $y^{\prime}_{i}=y_{k-i+1}$ for $i=2,\dots,k-1$. Then the first sum can be rearranged as

(These rearrangements are elementary if tedious; Figure 1 may be helpful to complete them.)

where, always with the conventions $x_{1}=x$ and $x_{k}=x^{\prime}$,

It remains to show that given $\eta>0$, we can achieve $\Xi_{k}\geq-\eta$ by a suitable choice of $k$ and $x_{2},\dots,x_{k-1}$. Fix a continuous, rectifiable curve $\varphi:\to\mathsf{X}_{0}$ with $\varphi(0)=x$ and $\varphi(1)=x^{\prime}$, and denote its length by $C$. For each $k\geq 2$ there exist $0=t_{1}<t_{2}<\dots<t_{k-1}<t_{k}=1$ such that $x_{i}:=\varphi(t_{i})$ satisfy $d(x_{i},x_{i+1})\leq C/(k-1)$ for all $1\leq i\leq k-1$. Applying Assumption 4.9 on the compact set $\varphi()$, we have that

The preceding arguments can be generalized to handle certain discontinuities in $T$, even though at a discontinuity, (4.15) can only be expected with $o(1)$ rather than $o(d(x_{1},x_{2}))$. Indeed, the conclusion of (4.2.2) still holds if for a bounded number of $i$’s, the term under the sum is only $o(1)$. For instance, this can be used to handle the case of semi-discrete transport with quadratic cost, where $\nu$ has finite support and hence the transport map is necessarily discontinuous.

Let Assumption 4.9 hold. For any open set $U\subset\mathsf{X}_{0}\times\mathsf{Y}_{0}$,

The argument is similar to the proof of Corollary 4.7, using the inequality (4.16) instead of the equality (4.7). In the course of the argument one also obtains that (4.16) already implies (4.7). We omit the details. ∎

Positivity of the Rate Function

The aim of this section is to establish that, under certain conditions, $I(x,y)$ of (4.3) is strictly positive for $(x,y)\in\mathsf{X}_{0}\times\mathsf{Y}_{0}$ outside the support $\Gamma$ of the limiting optimal transport $\pi_{*}$. In view of Corollary 4.7, this implies that that the mass of $\pi_{\varepsilon}$ around $(x,y)$ converges exponentially fast.

Fix $(x,y^{\prime})\in\Gamma$ and $y\in\mathsf{Y}$. Suppose that

and that there exist $(x_{n},y_{n})\in\Gamma$ such that $(x_{n},y_{n})\to(x,y^{\prime})$ and

Set $\Delta(x,y^{\prime},y_{n}):=\nabla_{x}c(x,y^{\prime})-\nabla_{x}c(x,y_{n})$; then $\Delta(x,y^{\prime},y_{n})\to 0$ as $d(y^{\prime},y_{n})\to 0$ and we have

As $v\neq 0$ and $\liminf_{n}\cos\alpha_{n}>0$, it follows that $\delta_{n}>0$ for $n$ large enough. Fix such an $n$, then choosing $k=2$ and $(x_{2},y_{2}):=(x_{n},y_{n})$ in (4.3) shows that $I(x,y)\geq\delta_{n}>0$. ∎

Recall the notation $\mathsf{X}_{0}=\operatorname{proj}_{\mathsf{X}}\Gamma$ and $\Gamma=\operatorname{spt}\pi_{*}$. If $x$ is interior in $\mathsf{X}_{0}$, we can choose auxiliary points in any direction from $x$ and Lemma 5.1 yields a positivity result for $I(x,y)$ as follows.

Let $x\in\operatorname{int}\mathsf{X}_{0}$ and $y\in\mathsf{Y}$. Let $\pi_{*}$ be given by a transport map $T$ which is continuous at $x$. If $\nabla_{x}c(x,y)-\nabla_{x}c(x,T(x))\neq 0,$ then $I(x,y)>0$.

For $n$ large we can uniquely define a point $x_{n}\in\partial B_{1/n}(x)\subset\mathsf{X}_{0}$ by the requirement that $x-x_{n}$ be parallel to $v:=\nabla_{x}c(x,y)-\nabla_{x}c(x,T(x))$ (here $\partial B$ denotes the boundary). Then $\cos\alpha_{n}=1$ in the notation of (5.2) and we conclude using Lemma 5.1 with $(x,y^{\prime})=(x,T(x))$ and $(x_{n},y_{n})=(x_{n},T(x_{n}))$. ∎

Sufficient conditions for the continuity (and higher regularity) of the transport map have been studied extensively; see [58, Section 12] for an overview of now-classical results and, among others, for recent results including unbounded domains.

Let $c(x,y)=\|x-y\|^{2}$, let $\mathsf{X}_{0}$ be strictly convexIn the sense that the open segment $(x,x^{\prime})$ is contained in $\operatorname{int}\mathsf{X}_{0}$ for distinct $x,x^{\prime}\in\mathsf{X}_{0}$. and consider $(x,y)\in(\mathsf{X}_{0}\times\mathsf{Y}_{0})\setminus\Gamma$ with $x\in\partial\mathsf{X}_{0}$. Suppose that $\pi_{*}$ is given by a transport map $T$ which is continuous on a neighborhood $B_{r}(x)\cap\mathsf{X}_{0}$ for some $r>0$. Then $I(x,y)>0$.

The main step is to find a point $x^{\prime\prime}\in\mathsf{X}_{0}$ such that

Once that is achieved, we may choose a sequence $x_{n}\to x$ in the open segment $(x^{\prime\prime},x)$ which is contained in $\operatorname{int}\mathsf{X}_{0}$ due to strict convexity. As $(x_{n},T(x_{n}))\to(x,T(x))$ by continuity and $\alpha_{n}=\angle(v,x-x^{\prime\prime})$ for all $n$, we conclude by Lemma 5.1 with $(x,y^{\prime}):=(x,T(x))$.

To find $x^{\prime\prime}$ satisfying (5.3), we first fix $x^{\prime}\in\mathsf{X}_{0}$ such that $(x^{\prime},y)\in\Gamma$. As $c$ is quadratic, we have $v=y^{\prime}-y$ in (5.1) and the cyclical monotonicity of $\Gamma$ yields

If this inequality is strict, we choose $x^{\prime\prime}:=x^{\prime}$. Whereas if $\langle v,x-x^{\prime}\rangle=0$, we consider the mid-point $\bar{x}=(x^{\prime}-x)/2$ which satisfies $\bar{x}\in\operatorname{int}\mathsf{X}_{0}$ by strict convexity as well as $\langle v,x-\bar{x}\rangle=0$. After choosing $\rho>0$ small enough such that $\partial B_{\rho}(\bar{x})\subset\mathsf{X}_{0}$, we can find a point $x^{\prime\prime}\in\partial B_{\rho}(\bar{x})\subset\mathsf{X}_{0}$ such that $\langle v,x-x^{\prime\prime}\rangle>0$, completing the proof. ∎

Next, we illustrate the dual approach in a problem with discontinuous optimal transport map. For the remainder of the section, we assume that there exists a Kantorovich potential $\psi$ such that

As seen in Proposition 4.5, a sufficient condition is Assumption 4.4 (uniqueness of potentials). If we assume that $\mu\sim\mathcal{L}^{d}$ on its support, the quadratic cost and the convexity condition in the below results already guarantee that Assumption 4.4 holds; cf. Proposition B.2. The relevance of (5.4) is that it yields the representation

so that our question regarding exponential convergence can be phrased as:

does $\Gamma$ fill the entire set $\partial_{c}\psi\cap(\mathsf{X}_{0}\times\mathsf{Y}_{0})$?

The intersection with $\mathsf{X}_{0}\times\mathsf{Y}_{0}$ is crucial to avoid a negative answer in many cases with discontinuous transport (see also the proof of Proposition 5.5 below). On the other hand, the intersection is justified because the interpretation of $I$ as rate of convergence is meaningless outside $\operatorname{spt}\pi_{\varepsilon}$.

We first state the following continuation argument similar to Lemma 5.3.

We may state the proof with the equivalent cost $c(x,y)=-\langle x,y\rangle/2$, so that the notions of $c$-convex analysis and convex analysis coincide. Suppose for contradiction that $I(x,y)=0$. Fix $x^{\prime}\in\mathsf{X}_{0}$ such that $(x^{\prime},y)\in\Gamma$ and denote $\phi:=-\psi^{c}$ for $\psi$ as in (5.4), then both $x$ and $x^{\prime}$ are in the set

Again, we may state the proof with the equivalent cost $c(x,y)=-\langle x,y\rangle/2$. Let $(x,y)\in\mathsf{X}_{0}\times\mathsf{Y}_{0}$. In view of Lemma 5.4, it suffices to treat the case $x\in\operatorname{int}\mathsf{X}_{0}$. Denote by $\operatorname{dom}\nabla\psi$ the set of points where $\psi$ is differentiable and assume that $I(x,y)=0$; that is, $y\in\partial_{c}\psi(x)=\partial\psi(x)$. The (ordinary) subdifferential $\partial\psi(x)$ equals $\{\nabla\psi(x)\}$ if $x\in\operatorname{dom}\nabla\psi$, whereas in general, it can be described (cf. [55, Theorem 25.6, p. 246]) as the closed convex hull of

Case 1: $x\in\operatorname{dom}\nabla\psi$. As $\Gamma\subset\partial\psi$ and $\partial\psi(x)$ is a singleton, it follows that $(x,y)=(x,\nabla\psi(x))\in\Gamma$.

Case 2: $y\in S(x)$. Let $x_{n}\to x$ be as in (5.6). Recalling that $x\in\operatorname{int}\mathsf{X}_{0}$, we have $x_{n}\in\mathsf{X}_{0}$ for $n$ large. Thus $(x_{n},\nabla\psi(x_{n}))\in\Gamma$ by Case 1 and closedness entails that the limit $(x,y)$ pertains to $\Gamma$ as well.

Case 3: $y\in\partial\psi(x)\setminus S(x)$. We shall show that this case does not occur. As a first step, we argue that

in the present context (without taking closure). As $x\in\operatorname{int}\mathsf{X}_{0}\subset\operatorname{int}\{\psi<\infty\}$, the subdifferential $\partial\psi(x)$ is bounded [55, Theorem 23.4, p. 217]. Let $U$ be a bounded neighborhood of $\partial\psi(x)$. The discreteness assumption on $\operatorname{spt}\nu$ entails that $U\cap\mathsf{Y}_{0}$ is a finite set (and that $\mathsf{Y}_{0}=\operatorname{spt}\nu$). Let $x_{n}\to x$ be as in (5.6). For $x_{n}$ close to $x$ we have $\nabla\psi(x_{n})\in U$, but also $\nabla\psi(x_{n})\in\mathsf{Y}_{0}$ by Case 1. As a result, the set $S(x)$ of limits is finite. In particular, its convex hull is already closed, and (5.7) follows.

Now let $y\in\partial\psi(x)\setminus S(x)$. By (5.7), $y$ is a nontrivial convex combination $y=\sum_{i=1}^{k}\theta_{i}y_{i}$ for some distinct $y_{i}\in S(x)$ and $\theta_{i}\in(0,1)$ with $\sum\theta_{i}=1$. Let $\phi:=-\psi^{c}$ (which is the Legendre–Fenchel transform of $\psi$ in this context) and $x^{\prime}\in\partial\phi(y)$. Then cyclical monotonicity of $\partial\phi$ implies $\langle x^{\prime}-x,y-y_{i}\rangle\geq 0$ for all $i$ and as

it follows that $\langle x^{\prime}-x,y-y_{i}\rangle=0$ for all $i$. That is, we have

which implies in particular $\dim\partial\phi(y)<d$. On the other hand, $\nu(\{y\})>0$ by the discreteness of $\mathsf{Y}_{0}$. Thus $\mu(\partial\phi(y))=\nu(\{y\})>0$, contradicting that $\mu\ll\mathcal{L}^{d}$ does not charge lower dimensional sets. This shows that Case 3 does not occur and completes the proof. ∎

The preceding arguments can be extended to a class of cost functions satisfying a Ma-Trudinger-Wang condition. This is detailed in Appendix C.

After replacing convexity by $c$-convexity, Lemma 5.4 and Proposition 5.5 extend to cost functions $c$ satisfying Assumption C.1.

We conclude with a simple example illustrating the relevance of the twist condition. Here, $\nabla_{x}c(x,y)$ vanishes below the diagonal, so that the condition fails, and indeed the convergence $\pi_{\varepsilon}\to\pi_{*}$ is sub-exponential in that region.

As $\nabla_{x}c(x,y)=0$ for all $y<x$, this cost does not satisfy the twist condition. Clearly there is a unique optimal transport $\pi_{*}\in\Pi(\mu,\nu)$, given by the Monge map $T(x)=x$. Its support is $\Gamma=\{(x,x):0\leq x\leq 1\}$ and one can check by direct calculation based on (4.3) that $I=c$ on $\mathsf{X}_{0}\times\mathsf{Y}_{0}=^{2}$. Assumption 4.9 is readily verified, hence Corollary 4.12 shows that $I$ is indeed the rate function in this context. We can obtain the same conclusion from Corollary 4.7, at least if we also suppose that $\mu$ is equivalent to the Lebesgue measure on $$: then, Proposition B.2 shows that Assumption 4.4 holds. Or as a third option, we may verify directly that$I$satisfies (4.7), and then conclude as in the proof of Corollary 4.7. In any event, we see that$I=0$on$\{y$, indicating sub-exponential decay of the weight of$\pi_{\varepsilon}$.

Appendix A Cyclical Invariance and Factorization

In this section we detail some classical facts about static Schrödinger bridges as well as the proof of Proposition 2.2. Let $(\mathsf{X},\mu)$ and $(\mathsf{Y},\nu)$ be Polish probability spaces; as before, we denote by $\Pi(\mu,\nu)$ the set of couplings.

Let $R$ be a probability measure on $\mathsf{X}\times\mathsf{Y}$ and suppose that

Then there is a unique minimizer $\pi^{*}\in\Pi(\mu,\nu)$ for $\inf_{\pi\in\Pi(\mu,\nu)}H(\pi|R).$ Assume in addition that $R\sim\mu\otimes\nu$. Then $\pi_{*}\sim\mu\otimes\nu$ and there exist measurable functions $Z:\mathsf{X}\times\mathsf{Y}\to(0,\infty)$, $f:\mathsf{X}\to(0,\infty)$, $g:\mathsf{Y}\to(0,\infty)$ such that

and $Z$ is a version of the Radon–Nikodym density $d\pi^{*}/dR$. Conversely, if $\pi\in\Pi(\mu,\nu)$ and a version of its density has the form (A.2) on a set of full $\mu\otimes\nu$-measure, where $f$ and $g$ are arbitrary $[-\infty,\infty]$-valued functions, then $\pi=\pi^{*}$.

The uniqueness result also holds without Assumption (A.1), if stated as follows. Let $\pi,\pi^{\prime}\in\Pi(\mu,\nu)$ and $\pi,\pi^{\prime},R\sim\mu\otimes\nu$. If versions of $d\pi/dR$ and $d\pi^{\prime}/dR$ both admit factorizations as above, then $\pi=\pi^{\prime}$.