Introduction
Selecting a probability distribution from incomplete information is a fundamental problem in statistical inference and statistical physics. When the available information does not uniquely determine a distribution, the maximum entropy principle (MEP) provides a systematic criterion for selecting the least informative distribution consistent with that information [2 , 3 , 12 , 13 , 23 , 24 ] . Traditionally, the available information is expressed through moment or expectation constraints, leading to Gibbs-type distributions. In many settings, however, uncertainty is naturally described relative to a prescribed nominal distribution, with admissible distributions restricted to a neighborhood of that nominal law. Optimal transport provides a geometric framework for describing such neighborhoods through the Wasserstein distance, which quantifies the minimum cost required to transport one probability distribution into another [22 , 27 ] .
This motivates the study of maximum-entropy inference under Wasserstein constraints. Given a nominal distribution P X \mathbb{P}_{X} P X , the objective is to identify a maximally uncertain distribution P V \mathbb{P}_{V} P V whose Wasserstein distance from P X \mathbb{P}_{X} P X does not exceed a prescribed radius. Such a formulation combines the maximum entropy principle with a geometric description of distributional uncertainty. However, directly solving the resulting optimization problem can be challenging. The Wasserstein constraint is defined through an optimization over transport couplings, and characterizing the entropy-maximizing distribution generally requires solving a variational problem involving the induced marginal distribution and the associated transport geometry. This raises a natural question: can Wasserstein-constrained maximum-entropy inference be approximated through a computationally simpler formulation, while retaining quantitative guarantees on the loss of optimality?
One alternative is to impose the transport budget directly on the stochastic transition generating the perturbed variable. Given a nominal random variable X X X , one seeks a conditional distribution P V ∣ X \mathbb{P}_{V\mid X} P V ∣ X maximizing the conditional entropy of V V V given X X X , subject to a bound on the expected transport cost between X X X and V V V . This formulation is closely related to the maximum-caliber principle, originally proposed by Jaynes [14 ] , which extends maximum-entropy reasoning to stochastic trajectories and dynamical laws subject to constraints on transition or path observables [10 , 21 , 25 ] . We refer to this formulation as the average-transport maximum entropy principle (A-MEP). Unlike the Wasserstein constraint, which involves minimizing the transport cost over all couplings between two distributions, the average-transport constraint is evaluated directly under the joint law induced by the perturbation kernel. This distinction leads to a particularly tractable optimization problem, on Euclidean spaces, A-MEP admits an explicit generalized-Gaussian additive-noise solution, including Gaussian and Laplace perturbations as special cases.
In contrast, Wasserstein-constrained maximum-entropy inference imposes the transport budget only on the marginal distribution induced by the perturbation. This distribution-level perspective is related to Wasserstein variational principles, including the Jordan–Kinderlehrer–Otto scheme [15 ] , in which probability distributions are selected through variational problems involving Wasserstein geometry. We refer to the corresponding formulation as the Wasserstein maximum entropy principle (W-MEP). Importantly, the coupling certifying Wasserstein proximity need not coincide with the joint law generated by the entropy-bearing transition kernel. Consequently, although A-MEP and W-MEP maximize the same conditional-entropy objective, they impose different restrictions on the stochastic relationship between the nominal and perturbed variables.
The computational simplicity of A-MEP makes it an attractive surrogate for W-MEP. Indeed, every perturbation kernel satisfying the average-transport constraint induces a marginal distribution lying within the corresponding Wasserstein neighborhood of the nominal law. Thus, the explicit A-MEP solution provides a feasible construction for W-MEP without requiring the computation of an optimal transport coupling or the solution of the Wasserstein-constrained variational problem. Nevertheless, the two formulations need not yield the same optimal value or the same entropy-maximizing marginal distribution. Feasibility alone is therefore insufficient to establish the quality of the approximation. The central question addressed in this paper is: how accurately can the tractable A-MEP formulation approximate W-MEP, and how can the resulting loss of optimality be quantified?
We address this question through three main contributions:
First, we characterize the optimal solutions of both formulations. On Euclidean spaces, A-MEP admits an explicit generalized-Gaussian additive-noise solution, providing a computationally tractable construction of a feasible distribution for W-MEP. For W-MEP, we derive a dual characterization in terms of a Kantorovich potential and show that the entropy-maximizing conditional kernel can be chosen independently of the nominal realization.
Second, we establish that both formulations generate the same set of attainable marginal distributions and admit representations over a common feasible set. This reveals that their discrepancy is governed by the mutual information retained between the nominal and perturbed variables. We use this characterization to derive bounds on the entropy gap, including an explicit upper bound that provides a quantitative optimality guarantee for the A-MEP surrogate.
Third, for finitely supported nominal distributions, we obtain finite-mixture representations and an exact decomposition of the entropy gap into a marginal-entropy gain and a weighted Jensen–Shannon divergence. A symmetric two-point example illustrates that the gap can be strict and that the formulations can yield different entropy-maximizing distributions.
.
Related connections between entropy and optimal transport arise in regularized optimal transport and the Schrödinger problem [4 , 17 , 20 ] , while entropy-based selection over Wasserstein balls has also been studied through minimum-cross-entropy formulations [26 ] . These works differ from the question considered here. Rather than introducing an entropy regularization of the transport problem or studying relative-entropy projections onto Wasserstein neighborhoods, we investigate whether a maximum-entropy problem under an average transport constraint can serve as a tractable approximation to its Wasserstein-constrained counterpart. Our results establish that this approximation can be characterized and bounded through information-theoretic quantities, providing a connection between computational tractability, transport geometry, and the dependence retained by stochastic perturbations.
Problem setting
Throughout the paper, all random objects are defined on a common probability space ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) . Let ( X , ∥ ⋅ ∥ ) (\mathcal{X},\lVert\cdot\rVert) ( X , ∥ ⋅ ∥) be a Polish space with Borel σ \sigma σ -algebra B ( X ) \mathcal{B}(\mathcal{X}) B ( X ) , and let X , V : ( Ω , F ) → ( X , B ( X ) ) X,V:(\Omega,\mathcal{F})\to(\mathcal{X},\mathcal{B}(\mathcal{X})) X , V : ( Ω , F ) → ( X , B ( X )) be random variables. Denote by P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) the set of all Borel probability measures on ( X , B ( X ) ) (\mathcal{X},\mathcal{B}(\mathcal{X})) ( X , B ( X )) , and by P p ( X ) \mathcal{P}_p(\mathcal{X}) P p ( X ) the set of probability measures on X \mathcal{X} X with finite p p p -th moment,
P p ( X ) = { P ∈ P ( X ) : ∫ X ∥ x ∥ p d P ( x ) < ∞ } . \mathcal{P}_p(\mathcal{X}) = \left\{ \mathbb{P} \in\mathcal{P}(\mathcal{X}) : \int_{\mathcal{X}} \lVert x \rVert^p \, \mathrm{d}\mathbb{P}(x) < \infty\right\}. P p ( X ) = { P ∈ P ( X ) : ∫ X ∥ x ∥ p d P ( x ) < ∞ } .
For a given a nominal distribution P X ∈ P p ( X ) \mathbb{P}_X \in\mathcal{P}_p(\mathcal{X}) P X ∈ P p ( X ) , a perturbation is described by a stochastic kernel P V ∣ X \mathbb{P}_{V\mid X} P V ∣ X from X \mathcal{X} X to X \mathcal{X} X . Together, P X \mathbb{P}_X P X and P V ∣ X \mathbb{P}_{V\mid X} P V ∣ X induce the joint law
P X , V : = P X ⊗ P V ∣ X , \mathbb{P}_{X,V} := \mathbb{P}_X \otimes\mathbb{P}_{V\mid X}, P X , V := P X ⊗ P V ∣ X ,
defined by
P X , V ( B × C ) = ∫ B P V ∣ X = x ( C ) d P X ( x ) , B , C ∈ B ( X ) , \mathbb{P}_{X,V}(B \times C) = \int_B \mathbb{P}_{V\mid X=x}(C) \, \mathrm{d}\mathbb{P}_X(x), \qquad B,C \in\mathcal{B}(\mathcal{X}), P X , V ( B × C ) = ∫ B P V ∣ X = x ( C ) d P X ( x ) , B , C ∈ B ( X ) ,
and its marginal with respect to V V V , denoted by P V \mathbb{P}_V P V , satisfies
P V ( C ) = ∫ X P V ∣ X = x ( C ) d P X ( x ) , C ∈ B ( X ) . \mathbb{P}_V(C) = \int_{\mathcal{X}} \mathbb{P}_{V\mid X=x}(C) \, \mathrm{d}\mathbb{P}_X(x), \qquad C \in\mathcal{B}(\mathcal{X}). P V ( C ) = ∫ X P V ∣ X = x ( C ) d P X ( x ) , C ∈ B ( X ) .
We write
K p ( X ) = { P V ∣ X stochastic kernels on X : ∫ X ∫ X ∥ v ∥ p d P V ∣ X ( v ) d P X ( x ) < ∞ } , \mathcal{K}_p(\mathcal{X}) = \left\{ \mathbb{P}_{V\mid X}\ \text{stochastic kernels on }\mathcal{X} : \int_{\mathcal{X}}\int_{\mathcal{X}} \lVert v \rVert^p \, \mathrm{d}\mathbb{P}_{V\mid X}(v) \, \mathrm{d}\mathbb{P}_X(x) < \infty\right\}, K p ( X ) = { P V ∣ X stochastic kernels on X : ∫ X ∫ X ∥ v ∥ p d P V ∣ X ( v ) d P X ( x ) < ∞ } ,
for the set of perturbation kernels whose induced marginal belongs to P p ( X ) \mathcal{P}_p(\mathcal{X}) P p ( X ) . The p p p -Wasserstein distance between probability measures P X , P V ∈ P p ( X ) \mathbb{P}_X,\mathbb{P}_V \in\mathcal{P}_p(\mathcal{X}) P X , P V ∈ P p ( X ) is defined by
W p ( P X , P V ) = ( inf π ∈ Π ( P X , P V ) ∫ X × X ∥ x − v ∥ p d π ( x , v ) ) 1 / p . W_p(\mathbb{P}_X,\mathbb{P}_V) = \left( \inf_{\pi\in\Pi(\mathbb{P}_X,\mathbb{P}_V)} \int_{\mathcal{X}\times\mathcal{X}} \lVert x-v \rVert^p \, \mathrm{d}\pi(x,v) \right)^{1/p}. W p ( P X , P V ) = ( π ∈ Π ( P X , P V ) inf ∫ X × X ∥ x − v ∥ p d π ( x , v ) ) 1/ p .
where Π ( P X , P V ) \Pi(\mathbb{P}_X,\mathbb{P}_V) Π ( P X , P V ) denotes the set of all couplings of P X \mathbb{P}_X P X and P V \mathbb{P}_V P V . A distinction used throughout the paper is that between the perturbation-induced joint law P X , V = P X ⊗ P V ∣ X \mathbb{P}_{X,V} = \mathbb{P}_X \otimes\mathbb{P}_{V\mid X} P X , V = P X ⊗ P V ∣ X and a generic transport coupling of the same marginals π ∈ Π ( P X , P V ) \pi\in\Pi(\mathbb{P}_X,\mathbb{P}_V) π ∈ Π ( P X , P V ) . Since X \mathcal{X} X is a standard Borel space, such a coupling admits a disintegration [16 Thm. 8.5] of the form
d π ( x , v ) = d P X ( x ) d Q V ∣ X = x ( v ) , \mathrm{d}\pi(x,v) = \mathrm{d}\mathbb{P}_X(x) \, \mathrm{d}\mathbb{Q}_{V\mid X=x}(v), d π ( x , v ) = d P X ( x ) d Q V ∣ X = x ( v ) ,
for some stochastic kernel Q V ∣ X \mathbb{Q}_{V\mid X} Q V ∣ X . In general, this Q V ∣ X \mathbb{Q}_{V\mid X} Q V ∣ X need not coincide with the perturbation kernel P V ∣ X \mathbb{P}_{V\mid X} P V ∣ X even though both kernels induce the same marginal P V \mathbb{P}_V P V . Thus, P X , V \mathbb{P}_{X,V} P X , V is the coupling generated by the perturbation, whereas π \pi π is a generic coupling used in the transport problem.
Entropy and mutual information. Entropy is not defined on an arbitrary Polish space without specifying additional structure. We therefore follow the standard information-theoretic convention of using H P X , V ( V ) H_{\mathbb{P}_{X,V}}(V) H P X , V ( V ) for Shannon entropy on finite or countable spaces and h P X , V ( V ) h_{\mathbb{P}_{X,V}}(V) h P X , V ( V ) for differential entropy on Euclidean spaces [2 ] . Mutual information is denoted by I P X , V ( X ; V ) I_{\mathbb{P}_{X,V}}(X;V) I P X , V ( X ; V ) in both settings. Throughout, the subscript identifies the joint probability law under which the corresponding information-theoretic quantity is evaluated; marginal and conditional laws are understood to be induced by this joint law. Thus, for example, h P X , V ( V ) h_{\mathbb{P}_{X,V}}(V) h P X , V ( V ) denotes the differential entropy of the V V V -marginal of P X , V \mathbb{P}_{X,V} P X , V , while h P X , V ( V ∣ X ) h_{\mathbb{P}_{X,V}}(V\mid X) h P X , V ( V ∣ X ) denotes the corresponding conditional differential entropy. For instance, if X \mathcal{X} X is finite or countable, the Shannon entropy of V ∼ P V V \sim\mathbb{P}_V V ∼ P V is
H P X , V ( V ) : = − ∑ v ∈ X P V ( v ) log P V ( v ) . H_{\mathbb{P}_{X,V}}(V) := -\sum_{v \in\mathcal{X}} \mathbb{P}_V(v) \log\mathbb{P}_V(v). H P X , V ( V ) := − v ∈ X ∑ P V ( v ) log P V ( v ) .
If instead X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^d X ⊆ R d and P V \mathbb{P}_V P V admits a density p V p_V p V , its differential entropy is
h P X , V ( V ) : = − ∫ X p V ( v ) log p V ( v ) d v , h_{\mathbb{P}_{X,V}}(V) := -\int_{\mathcal{X}} p_V(v) \log p_V(v) \, \mathrm{d}v, h P X , V ( V ) := − ∫ X p V ( v ) log p V ( v ) d v ,
whenever the integral is well defined. Analogously, we also define the conditional entropy, in the discrete setting,
H P X , V ( V ∣ X ) = − ∑ x , v P X , V ( x , v ) log P V ∣ X = x ( v ) , H_{\mathbb{P}_{X,V}}(V\mid X) = -\sum_{x,v} \mathbb{P}_{X,V}(x,v) \log\mathbb{P}_{V\mid X=x}(v), H P X , V ( V ∣ X ) = − x , v ∑ P X , V ( x , v ) log P V ∣ X = x ( v ) ,
as well as in the Euclidean setting, if P V ∣ X = x P_{V\mid X=x} P V ∣ X = x admits a density p V ∣ X = x ( v ) p_{V\mid X=x}(v) p V ∣ X = x ( v ) for P X P_X P X -almost every x x x ,
h P X , V ( V ∣ X ) = − ∫ X × X log p V ∣ X = x ( v ) d P X , V ( x , v ) . h_{P_X,V}(V\mid X)=-\int_{\mathcal{X}\times\mathcal{X}}\log p_{V\mid X=x}(v)\,\mathrm{d}P_{X,V}(x,v). h P X , V ( V ∣ X ) = − ∫ X × X log p V ∣ X = x ( v ) d P X , V ( x , v ) .
Furthermore, the mutual information is
I P X , V ( X ; V ) : = KL ( P X , V ∥ P X ⊗ P V ) . I_{P_X,V}(X;V):=\operatorname{KL}(P_{X,V}\mathbin{\|}P_X\otimes P_V). I P X , V ( X ; V ) := KL ( P X , V ∥ P X ⊗ P V ) .
with the Kullback–Leibler divergence,
KL ( P ∥ Q ) = { ∫ Ω log ( d P d Q ) d P , if P ≪ Q and log ( d P d Q ) ∈ L 1 ( P ) , ∞ , otherwise. \operatorname{KL}(P\mathbin{\|}Q)=
\begin{cases}
\int_{\Omega}\log\left(\frac{\mathrm{d}P}{\mathrm{d}Q}\right)\,\mathrm{d}P, & \text{if }P\ll Q\text{ and }\log\left(\frac{\mathrm{d}P}{\mathrm{d}Q}\right)\in L^1(P),\\
\infty, & \text{otherwise.}
\end{cases} KL ( P ∥ Q ) = { ∫ Ω log ( d Q d P ) d P , ∞ , if P ≪ Q and log ( d Q d P ) ∈ L 1 ( P ) , otherwise.
Whenever the relevant quantities are well defined, the entropy decomposition
h P X , V ( V ∣ X ) = h P X , V ( V ) − I P X , V ( X ; V ) , h_{P_X,V}(V\mid X)=h_{P_X,V}(V)-I_{P_X,V}(X;V), h P X , V ( V ∣ X ) = h P X , V ( V ) − I P X , V ( X ; V ) ,
holds in the discrete and continuous Euclidean setting, respectively.
Problem setup
We now introduce the two maximum-entropy problems studied in this paper.
Maximum entropy under average transport constraint (A-MEP). Under the average-transport formulation, both entropy and transport cost are evaluated under the joint law generated by the perturbation kernel,
A ζ : = sup P V ∣ X ∈ K p ( X ) h P X , V ( V ∣ X ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p . (1) A_{\zeta}:=\sup_{P_{V\mid X}\in\mathcal{K}_p(\mathcal{X})}h_{P_X,V}(V\mid X)
\quad\text{s.t.}\quad
\mathbb{E}_{X,V}\left[\|x-v\|_p^p\right]\leq\zeta^p. \tag*{(1)} A ζ := P V ∣ X ∈ K p ( X ) sup h P X , V ( V ∣ X ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p . (1)
Maximum entropy under Wasserstein constraint (W-MEP). Under the Wasserstein formulation, the problem maximizes the same conditional entropy, but constrains only the marginal distribution induced by the perturbation kernel,
W ζ : = sup P V ∣ X ∈ K p ( X ) h P X , V ( V ∣ X ) s.t. W p ( P X , P V ) ≤ ζ . (2) W_{\zeta}:=\sup_{P_{V\mid X}\in\mathcal{K}_p(\mathcal{X})}h_{P_X,V}(V\mid X)
\quad\text{s.t.}\quad
W_p(P_X,P_V)\leq\zeta. \tag*{(2)} W ζ := P V ∣ X ∈ K p ( X ) sup h P X , V ( V ∣ X ) s.t. W p ( P X , P V ) ≤ ζ . (2)
Note that, every kernel feasible for A-MEP induces a marginal feasible for W-MEP, since the joint law P X ⊗ P V ∣ X P_X\otimes P_{V\mid X} P X ⊗ P V ∣ X is an admissible coupling between P X P_X P X and P V P_V P V . Consequently,
W p p ( P X , P V ) ≤ E X , V [ ∥ x − v ∥ p p ] ≤ ζ p . W_p^p(P_X,P_V)\leq\mathbb{E}_{X,V}\left[\|x-v\|_p^p\right]\leq\zeta^p. W p p ( P X , P V ) ≤ E X , V [ ∥ x − v ∥ p p ] ≤ ζ p .
Thus, the feasible set of A-MEP is contained in that of W-MEP. The inclusion can be strict because the joint law induced by P V ∣ X P_{V\mid X} P V ∣ X need not be an optimal coupling between its marginals.
Maximum entropy principle under transport constraints
Average transport constrained MEP
In the continuous setting, the A-MEP problem admits a closed-form solution. The dual variational formulation provides the structure needed to identify the optimizer, and the next theorem shows that the entropy-maximizing kernel on R d \mathbb{R}^d R d is of Gibbs type.
Proposition 3.1 (A-MEP). Consider X = R d \mathcal{X} = \mathbb{R}^{d} X = R d , then, given P X ∈ P p ( X ) \mathbb{P}_{X} \in\mathcal{P}_{p}(\mathcal{X}) P X ∈ P p ( X ) , the optimization problem in (1) admits an optimal value equal to,
A ζ = d p + log ( d p vol ( B p d ) Γ ( d p ) ( p d ) d / p ζ d ) . A_{\zeta} = \frac{d}{p} + \log\left(\frac{d}{p}\operatorname{vol}(B_{p}^{d})\Gamma\left(\frac{d}{p}\right)\left(\frac{p}{d}\right)^{d/p}\zeta^{d}\right). A ζ = p d + log ( p d vol ( B p d ) Γ ( p d ) ( d p ) d / p ζ d ) . with optimal solution given by a generalized gaussian distribution,
P V ∣ X A ( C ) = p d vol ( B p d ) Γ ( d / p ) ( d p ) d / p ζ − d ∫ C exp ( − d p ζ p ∥ x − v ∥ p p ) d v . \mathbb{P}^{\mathrm{A}}_{V|X}(C) = \frac{p}{d\operatorname{vol}(B_{p}^{d})\Gamma(d/p)}\left(\frac{d}{p}\right)^{d/p}\zeta^{-d}\int_{C}\exp\left(-\frac{d}{p\zeta^{p}}\lVert x-v\rVert_{p}^{p}\right)\,dv. P V ∣ X A ( C ) = d vol ( B p d ) Γ ( d / p ) p ( p d ) d / p ζ − d ∫ C exp ( − p ζ p d ∥ x − v ∥ p p ) d v . where Γ ( d ) = ∫ 0 ∞ x d − 1 e − x d x \Gamma(d) = \int_{0}^{\infty}x^{d-1}e^{-x}\,dx Γ ( d ) = ∫ 0 ∞ x d − 1 e − x d x is the gamma function and vol ( B p d ) = ( 2 Γ ( 1 + 1 p ) ) d Γ ( 1 + d p ) \operatorname{vol}(B_{p}^{d}) = \frac{\left(2\Gamma\left(1+\frac{1}{p}\right)\right)^{d}}{\Gamma\left(1+\frac{d}{p}\right)} vol ( B p d ) = Γ ( 1 + p d ) ( 2Γ ( 1 + p 1 ) ) d is the volume of the ℓ p \ell_{p} ℓ p -unit-ball.
The proof is provided in Section A.1.1.
The next corollaries show special cases of Proposition 3.1 corresponding to p = 2 p=2 p = 2 , p = 1 p=1 p = 1 and p → ∞ p\to\infty p → ∞ .
Corollary 3.1 (ℓ 2 \ell_{2} ℓ 2 A-MEP). Consider X = R d \mathcal{X}=\mathbb{R}^{d} X = R d , then, given P X ∈ P 2 ( X ) \mathbb{P}_{X}\in\mathcal{P}_{2}(\mathcal{X}) P X ∈ P 2 ( X ) , the optimization problem in (1), with p = 2 p=2 p = 2 , admits an optimal value d 2 + d log ( 2 π d ζ ) \frac{d}{2}+d\log\left(\sqrt{\frac{2\pi}{d}}\zeta\right) 2 d + d log ( d 2 π ζ ) , and optimal solution given by P V ∣ X A ∼ N ( x , ζ 2 d I d ) \mathbb{P}^{\mathrm{A}}_{V|X}\sim\mathcal{N}\left(x,\frac{\zeta^{2}}{d}\mathbb{I}_{d}\right) P V ∣ X A ∼ N ( x , d ζ 2 I d ) .
Corollary 3.2 (ℓ 1 \ell_{1} ℓ 1 A-MEP). Consider X = R d \mathcal{X}=\mathbb{R}^{d} X = R d , then, given P X ∈ P 1 ( X ) \mathbb{P}_{X}\in\mathcal{P}_{1}(\mathcal{X}) P X ∈ P 1 ( X ) , the optimization problem in (1), with p = 1 p=1 p = 1 , admits an optimal value d + d log ζ d d+d\log\frac{\zeta}{d} d + d log d ζ , an optimal optimal solution given by P V ∣ X A ∼ Laplace d ( x , ζ d ) \mathbb{P}^{\mathrm{A}}_{V|X}\sim\operatorname{Laplace}_{d}\left(x,\frac{\zeta}{d}\right) P V ∣ X A ∼ Laplace d ( x , d ζ ) , equivalently, P v i ∣ x i A ∼ i . i . d . Laplace ( x i , ζ d ) \mathbb{P}^{\mathrm{A}}_{v_{i}|x_{i}}\overset{\mathrm{i.i.d.}}{\sim}\operatorname{Laplace}\left(x_{i},\frac{\zeta}{d}\right) P v i ∣ x i A ∼ i.i.d. Laplace ( x i , d ζ ) .
Corollary 3.3 (Hard ℓ ∞ \ell_{\infty} ℓ ∞ MEP). Let ζ > 0 \zeta>0 ζ > 0 and let P X \mathbb{P}_{X} P X be a Borel probability measure on R d \mathbb{R}^{d} R d . The hard-constrained maximum conditional entropy problem
sup P V ∣ X ∈ K p ( X ) h P X , V ( V ∣ X ) \sup_{\mathbb{P}_{V|X}\in\mathcal{K}_{p}(\mathcal{X})} h_{\mathbb{P}_{X,V}}(V|X) P V ∣ X ∈ K p ( X ) sup h P X , V ( V ∣ X ) s.t. ∥ X − V ∥ ∞ ≤ ζ P X , V -a.s. , \text{s.t.}\qquad\lVert X-V\rVert_{\infty}\leq\zeta\qquad\mathbb{P}_{X,V}\text{-a.s.}, s.t. ∥ X − V ∥ ∞ ≤ ζ P X , V -a.s. , admits the unique optimal conditional density, V ∣ X = x ∼ Unif ( x + [ − ζ , ζ ] d ) V|X=x\sim\operatorname{Unif}(x+[-\zeta,\zeta]^{d}) V ∣ X = x ∼ Unif ( x + [ − ζ , ζ ] d ) , and the corresponding optimal value is d log ( 2 ζ ) d\log(2\zeta) d log ( 2 ζ ) .
These results show that the entropy-maximizing conditional distribution under an average transport constraint admits a simple additive-noise interpretation. For the squared average transport cost, the maximizer is a multivariate Gaussian distribution with diagonal covariance, assigning variance ζ 2 / d \zeta^{2}/d ζ 2 / d to each coordinate. For the absolute average transport cost, the optimal conditional law is an independent Laplace distribution with scale parameter ζ / d \zeta/d ζ / d in each coordinate. The proofs are in Sections A.1.2 to A.1.4, respectively.
Wasserstein constrained MEP
The marginal Wasserstein problem no longer admits a purely local Gibbs kernel depending only on the displacement x − v x-v x − v . This is natural because, unlike the average-transport constraint, the Wasserstein constraint is imposed at the level of the induced marginal rather than on each transition from x x x to v v v . Consequently, the conditional laws associated with different realizations of X X X are coupled through the common marginal they induce, so the entropy–transport trade-off can no longer be resolved pointwise in x x x . Instead, the optimizer is characterized through a Kantorovich-type dual potential. The next result makes this distinction explicit by deriving a dual formulation in which the entropy contribution appears through a log-partition function, while the transport contribution appears through a c c c -transform.
In this sense, the average transport formulation identifies the entropy kernel with the transport kernel, whereas the marginal Wasserstein formulation only requires their induced marginals to agree. The latter is particularly natural when individual transitions cannot be observed or matched, or when the available information concerns only population-level distributions rather than individual perturbations.
Proposition 3.2 (W-MEP dual characterization) Consider X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^{d} X ⊆ R d and let P X ∈ P p ( X ) \mathbb{P}_{X} \in\mathcal{P}_{p}(\mathcal{X}) P X ∈ P p ( X ) . Then the optimization problem in (2) admits the dual formulation
inf α ≥ 0 , φ log ∫ X exp ( − φ ( v ) ) d v − E X [ φ c α ( x ) ] + α ζ p . \inf_{\alpha\ge0,\ \varphi} \log\int_{\mathcal{X}} \exp(-\varphi(v))\,\mathrm{d}v - \mathbb{E}_{X}\left[\varphi^{c_{\alpha}}(x)\right] + \alpha\zeta^{p}. α ≥ 0 , φ inf log ∫ X exp ( − φ ( v )) d v − E X [ φ c α ( x ) ] + α ζ p . The infimum is taken over α ≥ 0 \alpha\ge0 α ≥ 0 and over admissible measurable dual potentials φ : X → R \varphi:\mathcal{X} \to\mathbb{R} φ : X → R such that exp ( − φ ) \exp(-\varphi) exp ( − φ ) is integrable and the terms in the dual objective are finite. The potential φ \varphi φ is the Lagrange multiplier associated with the marginal consistency constraint between the entropy kernel and the transport kernel. Furthermore,
c α ( x , v ) : = α ∥ x − v ∥ p p , φ c α ( x ) : = inf v ∈ X c α ( x , v ) − φ ( v ) c_{\alpha}(x,v) := \alpha\lVert x-v\rVert_{p}^{p}, \qquad\varphi^{c_{\alpha}}(x) := \inf_{v \in\mathcal{X}} c_{\alpha}(x,v)-\varphi(v) c α ( x , v ) := α ∥ x − v ∥ p p , φ c α ( x ) := v ∈ X inf c α ( x , v ) − φ ( v ) denotes the c α c_{\alpha} c α -transform of φ \varphi φ .
Moreover, suppose that strong duality holds and that an optimal dual pair ( α W , φ W ) (\alpha^{W},\varphi^{W}) ( α W , φ W ) exists. Then the optimal induced marginal has density
p V W ( v ) = exp ( − φ W ( v ) ) ∫ X exp ( − φ W ( u ) ) d u . p_{V}^{W}(v) = \frac{\exp(-\varphi^{W}(v))}{\int_{\mathcal{X}}\exp(-\varphi^{W}(u))\,\mathrm{d}u}. p V W ( v ) = ∫ X exp ( − φ W ( u )) d u exp ( − φ W ( v )) . The corresponding entropy-maximizing conditional kernel is independent of X X X .
d P V ∣ X W d P V W = 1 , P X -a.s. \frac{\mathrm{d}\mathbb{P}_{V\mid X}^{W}}{\mathrm{d}\mathbb{P}_{V}^{W}} = 1,\qquad\mathbb{P}_{X}\text{-a.s.} d P V W d P V ∣ X W = 1 , P X -a.s. The proof, including the derivation of the dual formulation and sufficient conditions for strong duality, is given in Section A.2.1.
Corollary 3.4 (W1-MEP) Consider X = R d \mathcal{X} = \mathbb{R}^{d} X = R d , then, given P X ∈ P 1 ( X ) \mathbb{P}_{X} \in\mathcal{P}_{1}(\mathcal{X}) P X ∈ P 1 ( X ) , the optimization problem in (2) , with p = 1 p=1 p = 1 , admits the dual formulation
inf φ log ∫ R d exp ( − φ ( v ) ) d v + E X [ φ ( x ) ] + Lip ( φ ) ζ , \inf_{\varphi} \log\int_{\mathbb{R}^{d}} \exp(-\varphi(v))\,\mathrm{d}v + \mathbb{E}_{X}[\varphi(x)] + \operatorname{Lip}(\varphi)\zeta, φ inf log ∫ R d exp ( − φ ( v )) d v + E X [ φ ( x )] + Lip ( φ ) ζ , where the infimum is restricted to pairs ( α , φ ) (\alpha,\varphi) ( α , φ ) for which the log-partition term is finite, and Lip α ( X ) \operatorname{Lip}_{\alpha}(\mathcal{X}) Lip α ( X ) denotes the set of measurable α \alpha α -Lipschitz functions with respect to the ℓ 1 \ell_{1} ℓ 1 norm,
Lip α ( X ) : = { φ : X → R : ∣ φ ( v ) − φ ( x ) ∣ ≤ α ∥ v − x ∥ 1 , ∀ x , v ∈ X } . \operatorname{Lip}_{\alpha}(\mathcal{X}) := \{\varphi:\mathcal{X}\to\mathbb{R}:|\varphi(v)-\varphi(x)| \le\alpha\lVert v-x\rVert_{1},\ \forall x,v \in\mathcal{X}\}. Lip α ( X ) := { φ : X → R : ∣ φ ( v ) − φ ( x ) ∣ ≤ α ∥ v − x ∥ 1 , ∀ x , v ∈ X } . Moreover, if an optimal pair ( α W , φ W ) (\alpha^{W},\varphi^{W}) ( α W , φ W ) exists, then the optimal induced marginal has density
p V W ( v ) = exp ( − φ W ( v ) ) ∫ X exp ( − φ W ( u ) ) d u , p_{V}^{W}(v) = \frac{\exp(-\varphi^{W}(v))}{\int_{\mathcal{X}}\exp(-\varphi^{W}(u))\,\mathrm{d}u}, p V W ( v ) = ∫ X exp ( − φ W ( u )) d u exp ( − φ W ( v )) , and the entropy-maximizing conditional kernel is independent of X X X , P V ∣ X W = P V W \mathbb{P}_{V\mid X}^{W} = \mathbb{P}_{V}^{W} P V ∣ X W = P V W , P X \mathbb{P}_{X} P X -a.s.
Proof provided in Section A.2.2.
Moreover, suppose that strong duality holds and that an optimal dual pair ( α W , φ W ) (\alpha^{W},\varphi^{W}) ( α W , φ W ) exists. Then the corresponding entropy-maximizing conditional kernel is independent of X X X , and the optimal induced marginal has density as given in Proposition 3.2.
This is the quadratic Wasserstein analogue of the Lipschitz-potential formulation in Corollary 3.4 and is consistent with the JKO scheme [15 ] , a variational Wasserstein formulation for the Fokker–Planck equation with decay. Furthermore, the W-MEP dual involves the quadratic c α c_{\alpha} c α -transform rather than a Lipschitz constraint. Under suitable regularity assumptions, the associated optimality conditions take the form of a Monge–Ampère equation [22 , 27 ] . This contrasts with the p = 1 p=1 p = 1 case, where the dual reduces to a Lipschitz-potential formulation.
Cost of Dependence
The previous section characterized the optimal solutions of A-MEP and W-MEP, highlighting the different roles played by the perturbation kernel and the induced marginal distribution. We now investigate how these differences affect their optimal values. In particular, we seek to quantify the loss of optimality incurred when using the tractable A-MEP formulation as a surrogate for W-MEP. To this end, we first establish that the average-transport and Wasserstein constraints generate the same set of attainable marginal distributions. This allows us to express both problems over a common feasible set and identify the dependence between the nominal and perturbed variables, measured through mutual information, as the source of their discrepancy. We then use this characterization to derive bounds on the resulting entropy gap.
Proposition 4.1 (Marginal equivalence) Let P X ∈ P p ( X ) \mathbb{P}_{X} \in\mathcal{P}_{p}(\mathcal{X}) P X ∈ P p ( X ) be given, ζ ≥ 0 \zeta\ge0 ζ ≥ 0 , and let F : P p ( X ) → R F:\mathcal{P}_{p}(\mathcal{X}) \to\mathbb{R} F : P p ( X ) → R be any functional of the perturbed marginal distribution. Then,
sup P V ∣ X ∈ K p ( X ) F ( P V ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p = sup P V ∈ P p ( X ) F ( P V ) , s.t. W p ( P X , P V ) ≤ ζ . \sup_{\mathbb{P}_{V|X} \in\mathcal{K}_{p}(\mathcal{X})} F(\mathbb{P}_{V})
\quad\text{s.t.}\quad\mathbb{E}_{X,V}\left[\lVert x-v\rVert_{p}^{p}\right] \le\zeta^{p}
=
\sup_{\mathbb{P}_{V} \in\mathcal{P}_{p}(\mathcal{X})} F(\mathbb{P}_{V}),
\quad\text{s.t.}\quad W_{p}(\mathbb{P}_{X},\mathbb{P}_{V}) \le\zeta. P V ∣ X ∈ K p ( X ) sup F ( P V ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p = P V ∈ P p ( X ) sup F ( P V ) , s.t. W p ( P X , P V ) ≤ ζ . Proof. “≤ \le ≤ ”: Let P V ∣ X \mathbb{P}_{V|X} P V ∣ X be a feasible argument for the problem on the left, with induced marginal P V \mathbb{P}_{V} P V and joint law P X , V \mathbb{P}_{X,V} P X , V . Since P X , V ∈ Π ( P X , P V ) \mathbb{P}_{X,V} \in\Pi(\mathbb{P}_{X},\mathbb{P}_{V}) P X , V ∈ Π ( P X , P V )
W p p ( P X , P V ) ≤ ∫ X × X ∥ x − v ∥ p p d P X , V ( x , v ) ≤ ζ p . W_{p}^{p}(\mathbb{P}_{X},\mathbb{P}_{V}) \le\int_{\mathcal{X}\times\mathcal{X}} \lVert x-v\rVert_{p}^{p}\,\mathrm{d}\mathbb{P}_{X,V}(x,v) \le\zeta^{p}. W p p ( P X , P V ) ≤ ∫ X × X ∥ x − v ∥ p p d P X , V ( x , v ) ≤ ζ p . Hence, P V \mathbb{P}_{V} P V is feasible for the problem on the right and attains there the same objective value F ( P V ) F(\mathbb{P}_{V}) F ( P V ) . Since this holds for every feasible kernel on the left,
sup P V ∣ X ∈ K p ( X ) F ( P V ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p ≤ sup P V ∈ P p ( X ) F ( P V ) , s.t. W p ( P X , P V ) ≤ ζ . \sup_{\mathbb{P}_{V|X} \in\mathcal{K}_{p}(\mathcal{X})} F(\mathbb{P}_{V})
\quad\text{s.t.}\quad\mathbb{E}_{X,V}\left[\lVert x-v\rVert_{p}^{p}\right] \le\zeta^{p}
\le
\sup_{\mathbb{P}_{V} \in\mathcal{P}_{p}(\mathcal{X})} F(\mathbb{P}_{V}),
\quad\text{s.t.}\quad W_{p}(\mathbb{P}_{X},\mathbb{P}_{V}) \le\zeta. P V ∣ X ∈ K p ( X ) sup F ( P V ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p ≤ P V ∈ P p ( X ) sup F ( P V ) , s.t. W p ( P X , P V ) ≤ ζ . “≥ \ge ≥ ”: Conversely, let P V \mathbb{P}_{V} P V be a feasible solution for the problem on the right, and let π ⋆ ∈ Π ( P X , P V ) \pi^{\star} \in\Pi(\mathbb{P}_{X},\mathbb{P}_{V}) π ⋆ ∈ Π ( P X , P V ) be an optimal coupling. Since X \mathcal{X} X is Polish, π ⋆ \pi^{\star} π ⋆ admits a disintegration
d π ⋆ ( x , v ) = d P X ( x ) d Q V ∣ X = x ( v ) . \mathrm{d}\pi^{\star}(x,v) = \mathrm{d}\mathbb{P}_{X}(x)\,\mathrm{d}\mathbb{Q}_{V|X=x}(v). d π ⋆ ( x , v ) = d P X ( x ) d Q V ∣ X = x ( v ) . Taking P V ∣ X : = Q V ∣ X \mathbb{P}_{V|X} := \mathbb{Q}_{V|X} P V ∣ X := Q V ∣ X , the resulting kernel induces the same marginal P V \mathbb{P}_{V} P V and satisfies
∫ X × X ∥ x − v ∥ p p d ( P X ⊗ P V ∣ X ) ( x , v ) = W p p ( P X , P V ) ≤ ζ p . \int_{\mathcal{X}\times\mathcal{X}} \lVert x-v\rVert_{p}^{p}\,\mathrm{d}(\mathbb{P}_{X}\otimes\mathbb{P}_{V|X})(x,v) = W_{p}^{p}(\mathbb{P}_{X},\mathbb{P}_{V}) \le\zeta^{p}. ∫ X × X ∥ x − v ∥ p p d ( P X ⊗ P V ∣ X ) ( x , v ) = W p p ( P X , P V ) ≤ ζ p . Hence, P V ∣ X \mathbb{P}_{V|X} P V ∣ X is feasible for the problem on the left and attains there the same objective value F ( P V ) F(\mathbb{P}_{V}) F ( P V ) ,
sup P V ∣ X ∈ K p ( X ) F ( P V ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p ≥ sup P V ∈ P p ( X ) F ( P V ) , s.t. W p ( P X , P V ) ≤ ζ . \sup_{\mathbb{P}_{V|X} \in\mathcal{K}_{p}(\mathcal{X})} F(\mathbb{P}_{V})
\quad\text{s.t.}\quad\mathbb{E}_{X,V}\left[\lVert x-v\rVert_{p}^{p}\right] \le\zeta^{p}
\ge
\sup_{\mathbb{P}_{V} \in\mathcal{P}_{p}(\mathcal{X})} F(\mathbb{P}_{V}),
\quad\text{s.t.}\quad W_{p}(\mathbb{P}_{X},\mathbb{P}_{V}) \le\zeta. P V ∣ X ∈ K p ( X ) sup F ( P V ) s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p ≥ P V ∈ P p ( X ) sup F ( P V ) , s.t. W p ( P X , P V ) ≤ ζ .
Proposition 4.1 applies to objectives that depend on the perturbation only through its induced marginal distribution. In particular, the two transport constraints are indistinguishable for any objective of the form F ( P V ) F(\mathbb{P}_V) F ( P V ) . When applying this result to entropy, we write H ( P V ) H(\mathbb{P}_V) H ( P V ) and h ( P V ) h(\mathbb{P}_V) h ( P V ) for the Shannon and differential entropy functionals of the marginal measure, respectively. In particular,
H ( P V ) = H P X , V ( V ) , h ( P V ) = h P X , V ( V ) . H(\mathbb{P}_V)=H_{\mathbb{P}_{X,V}}(V), \qquad h(\mathbb{P}_V)=h_{\mathbb{P}_{X,V}}(V). H ( P V ) = H P X , V ( V ) , h ( P V ) = h P X , V ( V ) .
Corollary 4.1 (Common average-transport representation) Let A ζ A_\zeta A ζ and W ζ W_\zeta W ζ denote the optimal values of A-MEP 1, and W-MEP 2, respectively. Then
W ζ = sup P V ∣ X ∈ K p ( X ) h P X , V ( V ) W_\zeta=\sup_{\mathbb{P}_{V|X}\in\mathcal{K}_p(\mathcal{X})} h_{\mathbb{P}_{X,V}}(V) W ζ = P V ∣ X ∈ K p ( X ) sup h P X , V ( V ) s . t . E X , V [ ∥ x − v ∥ p p ] ≤ ζ p \mathrm{s.t.}\qquad\mathbb{E}_{X,V}\left[\lVert x-v\rVert_p^p\right]\leq\zeta^p s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p whereas
A ζ = sup P V ∣ X ∈ K p ( X ) h P X , V ( V ) − I P X , V ( X ; V ) A_\zeta=\sup_{\mathbb{P}_{V|X}\in\mathcal{K}_p(\mathcal{X})} h_{\mathbb{P}_{X,V}}(V)-I_{\mathbb{P}_{X,V}}(X;V) A ζ = P V ∣ X ∈ K p ( X ) sup h P X , V ( V ) − I P X , V ( X ; V ) s . t . E X , V [ ∥ x − v ∥ p p ] ≤ ζ p , \mathrm{s.t.}\qquad\mathbb{E}_{X,V}\left[\lVert x-v\rVert_p^p\right]\leq\zeta^p, s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p , and A ζ ≤ W ζ A_\zeta\leq W_\zeta A ζ ≤ W ζ .
Proof. The characterization of W-MEP established above can be equivalently written as
W ζ = sup P V ∈ P p ( X ) h P X , V ( V ) W_\zeta=\sup_{\mathbb{P}_V\in\mathcal{P}_p(\mathcal{X})} h_{\mathbb{P}_{X,V}}(V) W ζ = P V ∈ P p ( X ) sup h P X , V ( V )
s . t . W p ( P X , P V ) ≤ ζ . \mathrm{s.t.}\qquad W_p(\mathbb{P}_X,\mathbb{P}_V)\leq\zeta. s.t. W p ( P X , P V ) ≤ ζ .
This is due to Proposition 3.2 and Remark 3.1 which show that the optimal argument for the W-MEP problem is an argument independent of X X X . Additionally, by Proposition 4.1 with F ( P V ) = h ( P V ) F(\mathbb{P}_V)=h(\mathbb{P}_V) F ( P V ) = h ( P V ) , and using h ( P V ) = h P X , V ( V ) h(\mathbb{P}_V)=h_{\mathbb{P}_{X,V}}(V) h ( P V ) = h P X , V ( V ) results in,
W ζ = sup P V ∣ X ∈ K p ( X ) h P X , V ( V ) W_\zeta=\sup_{\mathbb{P}_{V|X}\in\mathcal{K}_p(\mathcal{X})} h_{\mathbb{P}_{X,V}}(V) W ζ = P V ∣ X ∈ K p ( X ) sup h P X , V ( V )
s . t . E X , V [ ∥ x − v ∥ p p ] ≤ ζ p . \mathrm{s.t.}\qquad\mathbb{E}_{X,V}\left[\lVert x-v\rVert_p^p\right]\leq\zeta^p. s.t. E X , V [ ∥ x − v ∥ p p ] ≤ ζ p .
The expression for A ζ A_\zeta A ζ follows from the identity
h P X , V ( V ∣ X ) = h P X , V ( V ) − I P X , V ( X ; V ) . h_{\mathbb{P}_{X,V}}(V|X)=h_{\mathbb{P}_{X,V}}(V)-I_{\mathbb{P}_{X,V}}(X;V). h P X , V ( V ∣ X ) = h P X , V ( V ) − I P X , V ( X ; V ) .
Finally, for every feasible kernel P V ∣ X \mathbb{P}_{V|X} P V ∣ X ,
h P X , V ( V ) − I P X , V ( X ; V ) ≤ h P X , V ( V ) , h_{\mathbb{P}_{X,V}}(V)-I_{\mathbb{P}_{X,V}}(X;V)\leq h_{\mathbb{P}_{X,V}}(V), h P X , V ( V ) − I P X , V ( X ; V ) ≤ h P X , V ( V ) ,
by nonnegativity of mutual information. Suppose, by contradiction, that A ζ > W ζ A_\zeta>W_\zeta A ζ > W ζ . By the definition of supremum, there then exists a feasible kernel for which
h P X , V ( V ) − I P X , V ( X ; V ) > W ζ . h_{\mathbb{P}_{X,V}}(V)-I_{\mathbb{P}_{X,V}}(X;V)>W_\zeta. h P X , V ( V ) − I P X , V ( X ; V ) > W ζ .
For the same kernel, nonnegativity of mutual information implies
h P X , V ( V ) > W ζ , h_{\mathbb{P}_{X,V}}(V)>W_\zeta, h P X , V ( V ) > W ζ ,
contradicting the definition of W ζ W_\zeta W ζ as the supremum of h P X , V ( V ) h_{\mathbb{P}_{X,V}}(V) h P X , V ( V ) over the common feasible set. Hence A ζ ≤ W ζ A_\zeta\leq W_\zeta A ζ ≤ W ζ .
After expressing both problems over the same average-transport feasible set, their difference lies entirely in the objective. W-MEP maximizes the entropy of the induced marginal, whereas A-MEP maximizes the same marginal entropy net of the dependence I P X , V ( X ; V ) I_{\mathbb{P}_{X,V}}(X;V) I P X , V ( X ; V ) required by the perturbation. We can now isolate the effect of the mutual-information term and characterize the resulting optimal-value gap, Δ : = W ζ − A ζ ≥ 0 \Delta:=W_\zeta-A_\zeta\geq0 Δ := W ζ − A ζ ≥ 0 .
Theorem 4.1 (Information-gap representation and bounds). Suppose that A-MEP and W-MEP attain their optimal values. Let P V ∣ X A \mathbb{P}^{\mathrm{A}}_{V \mid X} P V ∣ X A be an optimal kernel for A-MEP, with induced marginal P V A \mathbb{P}^{\mathrm{A}}_{V} P V A and joint law P X , V A = P X ⊗ P V ∣ X A \mathbb{P}^{\mathrm{A}}_{X,V} = \mathbb{P}_{X} \otimes\mathbb{P}^{\mathrm{A}}_{V \mid X} P X , V A = P X ⊗ P V ∣ X A , and let P V W \mathbb{P}^{\mathrm{W}}_{V} P V W denote an optimal marginal associated with W-MEP. Define I A : = I P X , V A ( X ; V ) I_{\mathrm{A}} := I_{\mathbb{P}^{\mathrm{A}}_{X,V}}(X;V) I A := I P X , V A ( X ; V ) , and
I W : = inf P V ∣ X ∈ K p ( X ) I P X , V ( X ; V ) I_{\mathrm{W}} := \inf_{\mathbb{P}_{V \mid X} \in\mathcal{K}_{p}(\mathcal{X})} I_{\mathbb{P}_{X,V}}(X;V) I W := P V ∣ X ∈ K p ( X ) inf I P X , V ( X ; V ) subject to
E X E V ∣ X [ ∥ x − v ∥ p ] ≤ ζ p , \mathbb{E}_{X}\mathbb{E}_{V \mid X}\left[\lVert x-v\rVert^{p}\right] \le\zeta^{p}, E X E V ∣ X [ ∥ x − v ∥ p ] ≤ ζ p , h P X , V ( V ) = W ζ . h_{\mathbb{P}_{X,V}}(V) = W_{\zeta}. h P X , V ( V ) = W ζ . Then, the entropy gap Δ = [ h P X , V W ( V ) − h P X , V A ( V ) ] + I A \Delta= \left[h_{\mathbb{P}^{\mathrm{W}}_{X,V}}(V) - h_{\mathbb{P}^{\mathrm{A}}_{X,V}}(V)\right] + I_{\mathrm{A}} Δ = [ h P X , V W ( V ) − h P X , V A ( V ) ] + I A , is bounded by,
I A ≤ Δ ≤ I W . I_{\mathrm{A}} \le\Delta\le I_{\mathrm{W}}. I A ≤ Δ ≤ I W . Proof. Since P V ∣ X A \mathbb{P}^{\mathrm{A}}_{V \mid X} P V ∣ X A is optimal for A-MEP, A ζ = h P X , V A ( V ) − I A A_{\zeta} = h_{\mathbb{P}^{\mathrm{A}}_{X,V}}(V) - I_{\mathrm{A}} A ζ = h P X , V A ( V ) − I A , while optimality of P V W \mathbb{P}^{\mathrm{W}}_{V} P V W for W-MEP gives W ζ = h P X , V W ( V ) W_{\zeta} = h_{\mathbb{P}^{\mathrm{W}}_{X,V}(V)} W ζ = h P X , V W ( V ) . Hence
Δ = h P X , V W ( V ) − h P X , V A ( V ) + I A . \Delta= h_{\mathbb{P}^{\mathrm{W}}_{X,V}}(V) - h_{\mathbb{P}^{\mathrm{A}}_{X,V}}(V) + I_{\mathrm{A}}. Δ = h P X , V W ( V ) − h P X , V A ( V ) + I A . Since P V A \mathbb{P}^{\mathrm{A}}_{V} P V A is attainable under the common average-transport constraint and P V W \mathbb{P}^{\mathrm{W}}_{V} P V W maximizes marginal entropy over all attainable marginals,
h P X , V W ( V ) ≥ h P X , V A ( V ) , h_{\mathbb{P}^{\mathrm{W}}_{X,V}}(V) \ge h_{\mathbb{P}^{\mathrm{A}}_{X,V}}(V), h P X , V W ( V ) ≥ h P X , V A ( V ) , which proves Δ ≥ I A \Delta\ge I_{\mathrm{A}} Δ ≥ I A }.
For the upper bound, let P V ∣ X ∈ K p \mathbb{P}_{V \mid X} \in\mathcal{K}_{p} P V ∣ X ∈ K p , with E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p \mathbb{E}_{X}\mathbb{E}_{V \mid X}[\lVert x-v\rVert_{p}^{p}] \le\zeta^{p} E X E V ∣ X [∥ x − v ∥ p p ] ≤ ζ p , be any feasible kernel inducing the W-MEP marginal P V W \mathbb{P}^{\mathrm{W}}_{V} P V W . Since A-MEP maximizes h P X , V ( V ) − I P X , V ( X ; V ) h_{\mathbb{P}_{X,V}}(V) - I_{\mathbb{P}_{X,V}}(X;V) h P X , V ( V ) − I P X , V ( X ; V ) ,
A ζ ≥ h P X , V ( P V W ) − I P X , V ( X ; V ) = W ζ − I P X , V ( X ; V ) . A_{\zeta} \ge h_{\mathbb{P}_{X,V}}(\mathbb{P}^{\mathrm{W}}_{V}) - I_{\mathbb{P}_{X,V}}(X;V) = W_{\zeta} - I_{\mathbb{P}_{X,V}}(X;V). A ζ ≥ h P X , V ( P V W ) − I P X , V ( X ; V ) = W ζ − I P X , V ( X ; V ) . Therefore,
h P X , V A ( V ) − h P X , V W ( V ) ≥ I A − I P X , V ( X ; V ) , h_{\mathbb{P}^{\mathrm{A}}_{X,V}}(V) - h_{\mathbb{P}^{\mathrm{W}}_{X,V}}(V) \ge I_{\mathrm{A}} - I_{\mathbb{P}_{X,V}}(X;V), h P X , V A ( V ) − h P X , V W ( V ) ≥ I A − I P X , V ( X ; V ) , and hence,
Δ ≤ I P X , V ( X ; V ) . \Delta\le I_{\mathbb{P}_{X,V}}(X;V). Δ ≤ I P X , V ( X ; V ) . Taking the infimum over all P V ∣ X \mathbb{P}_{V \mid X} P V ∣ X with E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p \mathbb{E}_{X}\mathbb{E}_{V \mid X}[\lVert x-v\rVert_{p}^{p}] \le\zeta^{p} E X E V ∣ X [∥ x − v ∥ p p ] ≤ ζ p inducing P V W \mathbb{P}^{\mathrm{W}}_{V} P V W yields Δ ≤ I W \Delta\le I_{\mathrm{W}} Δ ≤ I W .
Corollary 4.2 (Explicit entropy-gap bounds on R d \mathbb{R}^{d} R d ). Let X = R d \mathcal{X} = \mathbb{R}^{d} X = R d , and suppose that the assumptions of Theorem 4.1 hold. Let Z Z Z be independent of X X X and distributed according to the generalized Gaussian identified in Proposition 3.1, so that V = X + Z V = X + Z V = X + Z is an optimal A-MEP kernel. Define
m p ( X ) : = ( E [ ∥ X − E [ X ] ∥ p p ] ) 1 / p , B ζ ( X ) : = d log ( 1 + m p ( X ) ζ ) . m_{p}(X) := \left(\mathbb{E}\left[\lVert X-\mathbb{E}[X]\rVert_{p}^{p}\right]\right)^{1/p}, \qquad B_{\zeta}(X) := d\log\left(1+\frac{m_{p}(X)}{\zeta}\right). m p ( X ) := ( E [ ∥ X − E [ X ] ∥ p p ] ) 1/ p , B ζ ( X ) := d log ( 1 + ζ m p ( X ) ) . Then
I P X , V ( X ; X + Z ) ≤ Δ ≤ min { I W , B ζ ( X ) } ≤ B ζ ( X ) . I_{\mathbb{P}_{X,V}}(X;X+Z) \le\Delta\le\min\{I_{\mathrm{W}},B_{\zeta}(X)\} \le B_{\zeta}(X). I P X , V ( X ; X + Z ) ≤ Δ ≤ min { I W , B ζ ( X )} ≤ B ζ ( X ) . Proof. By Proposition 3.1, the A-MEP optimum is attained by a generalized-Gaussian kernel centered at X X X , whose displacement distribution is independent of the nominal realization. The mutual information associated with this A-MEP optimizer is I A = I P X , V ( X ; X + Z ) I_{\mathrm{A}} = I_{\mathbb{P}_{X,V}}(X;X+Z) I A = I P X , V ( X ; X + Z ) . Applying Theorem 4.1 gives
I P X , V ( X ; X + Z ) ≤ Δ ≤ I W . I_{\mathbb{P}_{X,V}}(X;X+Z) \le\Delta\le I_{\mathrm{W}}. I P X , V ( X ; X + Z ) ≤ Δ ≤ I W . It remains to establish the explicit upper bound. For any kernel P V ∣ X \mathbb{P}_{V \mid X} P V ∣ X feasible for W-MEP, by Minkowski’s inequality we have, E [ ∥ V − E [ X ] ∥ p p ] 1 / p ≤ ( ζ + m p ) \mathbb{E}[\lVert V-\mathbb{E}[X]\rVert_{p}^{p}]^{1/p} \le(\zeta+m_{p}) E [∥ V − E [ X ] ∥ p p ] 1/ p ≤ ( ζ + m p ) , since
( E [ ∥ V − E [ X ] ∥ p p ] ) 1 / p = ( E [ ∥ ( V − X ) + ( X − E [ X ] ) ∥ p p ] ) 1 / p \left(\mathbb{E}\left[\lVert V-\mathbb{E}[X]\rVert_{p}^{p}\right]\right)^{1/p}
= \left(\mathbb{E}\left[\lVert(V-X)+(X-\mathbb{E}[X])\rVert_{p}^{p}\right]\right)^{1/p} ( E [ ∥ V − E [ X ] ∥ p p ] ) 1/ p = ( E [ ∥( V − X ) + ( X − E [ X ]) ∥ p p ] ) 1/ p ≤ ( E [ ∥ V − X ∥ p p ] ) 1 / p + ( E [ ∥ X − E [ X ] ∥ p p ] ) 1 / p \le\left(\mathbb{E}\left[\lVert V-X\rVert_{p}^{p}\right]\right)^{1/p}
+ \left(\mathbb{E}\left[\lVert X-\mathbb{E}[X]\rVert_{p}^{p}\right]\right)^{1/p} ≤ ( E [ ∥ V − X ∥ p p ] ) 1/ p + ( E [ ∥ X − E [ X ] ∥ p p ] ) 1/ p ≤ ζ + m p . \le\zeta+ m_{p}. ≤ ζ + m p .
By the maximum-entropy characterization in Proposition 3.1, and by translation invariance of differential entropy,
h P V ( V ) = h P V ( V − E [ X ] ) ≤ A ζ + m p . h_{\mathrm{P}_{V}}(V)=h_{\mathrm{P}_{V}}(V-\mathbb{E}[X])\le A_{\zeta+m_p}. h P V ( V ) = h P V ( V − E [ X ]) ≤ A ζ + m p .
Since this holds for every feasible W-MEP kernel, then, W ζ ≤ A ζ + m p W_{\zeta}\le A_{\zeta+m_p} W ζ ≤ A ζ + m p , and consequently,
Δ = W ζ − A ζ ≤ A ζ + m p − A ζ . \Delta=W_{\zeta}-A_{\zeta}\le A_{\zeta+m_p}-A_{\zeta}. Δ = W ζ − A ζ ≤ A ζ + m p − A ζ .
Furthermore, from Proposition 3.1, the A-MEP value scales with the distortion radius as
A r = C p , d + d log r , A_r=C_{p,d}+d\log r, A r = C p , d + d log r ,
where C p , d C_{p,d} C p , d does not depend on r r r . Hence
Δ ≤ d log ( ζ + m p ζ ) = d log ( 1 + m p ζ ) = B ζ ( X ) . \Delta\le d\log\left(\frac{\zeta+m_p}{\zeta}\right)=d\log\left(1+\frac{m_p}{\zeta}\right)=B_{\zeta}(X). Δ ≤ d log ( ζ ζ + m p ) = d log ( 1 + ζ m p ) = B ζ ( X ) .
Combining this bound with the result from Theorem 4.1, Δ ≤ I W \Delta\le I_W Δ ≤ I W , gives
Δ ≤ min { I W , B ζ ( X ) } ≤ B ζ ( X ) , \Delta\le\min\{I_W,B_{\zeta}(X)\}\le B_{\zeta}(X), Δ ≤ min { I W , B ζ ( X )} ≤ B ζ ( X ) ,
which completes the proof.
Remark 4.1 (Dependence of the gap bound on the transport radius) The explicit upper bound B ζ ( X ) = d log ( 1 + m p ( X ) ζ ) B_{\zeta}(X)=d\log\left(1+\frac{m_p(X)}{\zeta}\right) B ζ ( X ) = d log ( 1 + ζ m p ( X ) ) is decreasing in the transport radius ζ \zeta ζ . In particular, B ζ ( X ) → 0 B_{\zeta}(X)\to0 B ζ ( X ) → 0 as ζ → ∞ \zeta\to\infty ζ → ∞ , whereas B ζ ( X ) → ∞ B_{\zeta}(X)\to\infty B ζ ( X ) → ∞ as ζ ↓ 0 \zeta\downarrow0 ζ ↓ 0 whenever m p ( X ) > 0 m_p(X)>0 m p ( X ) > 0 . The monotonicity of B ζ ( X ) B_{\zeta}(X) B ζ ( X ) does not imply that the entropy gap Δ ζ \Delta_{\zeta} Δ ζ is itself monotone in ζ \zeta ζ , since an ordering of the upper bounds does not induce an ordering of the corresponding gaps.
This tells that for small transport budgets, A-MEP requires the entropy-bearing perturbation to remain close to each realization of X X X , thereby retaining dependence between X X X and V V V . In contrast, W-MEP constrains only the induced marginal distribution and allows the entropy-bearing kernel to be independent of X X X . As the transport budget increases, this distinction becomes less restrictive. In particular, Corollary 4.2 implies that Δ ζ → 0 \Delta_{\zeta}\to0 Δ ζ → 0 as ζ → ∞ \zeta\to\infty ζ → ∞ , provided that m p ( X ) < ∞ m_p(X)<\infty m p ( X ) < ∞ .
Discretely Supported Nominal Distribution
A case of particular interest is that of a discretely supported nominal distribution. Such distributions arise naturally in data-driven settings, where the underlying distribution is unknown and is represented by an empirical distribution constructed from a finite collection of observations. In this case, the nominal law takes the form
P X = ∑ i = 1 n a i δ x i , a i > 0 , ∑ i = 1 n a i = 1 , (3) \mathbb{P}_X=\sum_{i=1}^{n}a_i\delta_{x_i},\qquad a_i>0,\qquad\sum_{i=1}^{n}a_i=1, \tag*{(3)} P X = i = 1 ∑ n a i δ x i , a i > 0 , i = 1 ∑ n a i = 1 , (3)
with the empirical distribution corresponding to the particular choice a i = 1 / n a_i=1/n a i = 1/ n . Although the nominal distribution is discretely supported, the perturbed variable V V V is allowed to take values in the ambient space R d \mathbb{R}^d R d . The resulting formulation is more general than a pointwise perturbation of the nominal support since the probability mass associated with each x i x_i x i may be split and transported according to an arbitrary distribution on R d \mathbb{R}^d R d . In particular, translations of the nominal support points are recovered as the special case in which the corresponding conditional distributions are Dirac measures. In this setting, the A-MEP and W-MEP problems admit particularly transparent representations, highlighting the distinction between the entropy of the conditional perturbations and the entropy of their induced mixture.
Proposition 5.1 (Semi-discrete representation) Let X = R d \mathcal{X}=\mathbb{R}^d X = R d and consider an empirical, finitely supported nominal distribution as in (3). Then the A-MEP problem 1 is equivalent to
A = sup { P i ∈ P p ( R d ) } i = 1 n ∑ i = 1 n a i h P i ( V ) A=\sup_{\{\mathbb{P}_i\in\mathcal{P}_p(\mathbb{R}^d)\}_{i=1}^{n}}\sum_{i=1}^{n}a_i h_{\mathbb{P}_i}(V) A = { P i ∈ P p ( R d ) } i = 1 n sup i = 1 ∑ n a i h P i ( V )
s . t . ∑ i = 1 n a i ∫ R d ∥ x i − v ∥ p d P i ( v ) ≤ ζ p , \mathrm{s.t.}\qquad\sum_{i=1}^{n}a_i\int_{\mathbb{R}^d}\lVert x_i-v\rVert^p\,\mathrm{d}\mathbb{P}_i(v)\le\zeta^p, s.t. i = 1 ∑ n a i ∫ R d ∥ x i − v ∥ p d P i ( v ) ≤ ζ p ,
and the W-MEP problem 2 admits the equivalent average-transport representation
W = sup { P i ∈ P p ( R d ) } i = 1 n h P ‾ ( V ) s.t. ∑ i = 1 n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) ≤ ζ p . W=\sup_{\{\mathbb{P}_i\in\mathcal{P}_p(\mathbb{R}^d)\}_{i=1}^n} h_{\overline{\mathbb{P}}}(V)
\quad\text{s.t.}\quad
\sum_{i=1}^n a_i\int_{\mathbb{R}^d}\lVert x_i-v\rVert_p^p\,\mathrm{d}\mathbb{P}_i(v)\leq\zeta^p. W = { P i ∈ P p ( R d ) } i = 1 n sup h P ( V ) s.t. i = 1 ∑ n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) ≤ ζ p .
where P i = P V ∣ X = x i \mathbb{P}_i=\mathbb{P}_{V\mid X=x_i} P i = P V ∣ X = x i , i = 1 , … , n i=1,\ldots,n i = 1 , … , n and, P ‾ : = ∑ i = 1 n a i P i \overline{\mathbb{P}}:=\sum_{i=1}^n a_i\mathbb{P}_i P := ∑ i = 1 n a i P i denotes the induced V V V -marginal. Moreover, the quantities h P i ( V ) h_{\mathbb{P}_i}(V) h P i ( V ) and h P ‾ ( V ) h_{\overline{\mathbb{P}}}(V) h P ( V ) denote the differential entropy of V V V under P i \mathbb{P}_i P i and P ‾ \overline{\mathbb{P}} P , respectively, whenever well defined.
Proof. Let the nominal distribution be discretely supported on as given by (3). Although P X \mathbb{P}_X P X is discretely supported, the perturbed variable V V V is allowed to take values in the ambient space R d \mathbb{R}^d R d . Therefore, for each x i x_i x i , define
P i : = P V ∣ X = x i ∈ P p ( R d ) , i = 1 , … , n . \mathbb{P}_i:=\mathbb{P}_{V\mid X=x_i}\in\mathcal{P}_p(\mathbb{R}^d),\qquad i=1,\ldots,n. P i := P V ∣ X = x i ∈ P p ( R d ) , i = 1 , … , n .
The collection { P i } i = 1 n \{\mathbb{P}_i\}_{i=1}^n { P i } i = 1 n completely determines the perturbation kernel on the support of P X \mathbb{P}_X P X . The joint distribution induced by this kernel is
P X , V ( x , v ) = ∑ i = 1 n a i δ x i ( x ) d P i ( v ) , \mathbb{P}_{X,V}(x,v)=\sum_{i=1}^n a_i\delta_{x_i}(x)\,\mathrm{d}\mathbb{P}_i(v), P X , V ( x , v ) = i = 1 ∑ n a i δ x i ( x ) d P i ( v ) ,
and its V V V -marginal is therefore the mixture P ‾ = ∑ i = 1 n a i P i \overline{\mathbb{P}}=\sum_{i=1}^n a_i\mathbb{P}_i P = ∑ i = 1 n a i P i . Since X X X is discrete and V V V is continuous, the conditional differential entropy is obtained by averaging the differential entropies of the conditional laws,
h P X , V ( V ∣ X ) = ∑ i = 1 n P X ( x i ) h P i ( v ) = ∑ i = 1 n a i h P i ( V ) . h_{\mathbb{P}_{X,V}}(V\mid X)=\sum_{i=1}^n\mathbb{P}_X(x_i)h_{\mathbb{P}_i}(v)=\sum_{i=1}^n a_i h_{\mathbb{P}_i}(V). h P X , V ( V ∣ X ) = i = 1 ∑ n P X ( x i ) h P i ( v ) = i = 1 ∑ n a i h P i ( V ) .
If P i \mathbb{P}_i P i admits a density b i b_i b i with respect to Lebesgue measure, this can equivalently be written as
h P X , V ( V ∣ X ) = − ∑ i = 1 n a i ∫ R d b i ( v ) log b i ( v ) d v . h_{\mathbb{P}_{X,V}}(V\mid X)=-\sum_{i=1}^n a_i\int_{\mathbb{R}^d}b_i(v)\log b_i(v)\,\mathrm{d}v. h P X , V ( V ∣ X ) = − i = 1 ∑ n a i ∫ R d b i ( v ) log b i ( v ) d v .
Furthermore, the average transport cost under the perturbation-induced joint law is
E X E V ∣ X [ ∥ X − V ∥ p p ] = ∑ i = 1 n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) . \mathbb{E}_{X}\mathbb{E}_{V\mid X}\left[\lVert X-V\rVert_p^p\right]=\sum_{i=1}^n a_i\int_{\mathbb{R}^d}\lVert x_i-v\rVert_p^p\,\mathrm{d}\mathbb{P}_i(v). E X E V ∣ X [ ∥ X − V ∥ p p ] = i = 1 ∑ n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) .
As a result, the A-MEP problem is equivalent to
sup { P i ∈ P p ( R d ) } i = 1 n ∑ i = 1 n a i h P i ( V ) s.t. ∑ i = 1 n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) ≤ ζ p . \sup_{\{\mathbb{P}_i\in\mathcal{P}_p(\mathbb{R}^d)\}_{i=1}^n}\sum_{i=1}^n a_i h_{\mathbb{P}_i}(V)
\quad\text{s.t.}\quad
\sum_{i=1}^n a_i\int_{\mathbb{R}^d}\lVert x_i-v\rVert_p^p\,\mathrm{d}\mathbb{P}_i(v)\leq\zeta^p. { P i ∈ P p ( R d ) } i = 1 n sup i = 1 ∑ n a i h P i ( V ) s.t. i = 1 ∑ n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) ≤ ζ p .
For W-MEP, let us recall the equivalent average-transport representation of Corollary 4.1,
sup P V ∣ X ∈ K p ( X ) h P X , V ( V ) s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p . \sup_{\mathbb{P}_{V\mid X}\in\mathcal{K}_p(\mathcal{X})}h_{\mathbb{P}_{X,V}}(V)
\quad\text{s.t.}\quad
\mathbb{E}_{X}\mathbb{E}_{V\mid X}\left[\lVert x-v\rVert_p^p\right]\leq\zeta^p. P V ∣ X ∈ K p ( X ) sup h P X , V ( V ) s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p .
Since V V V -marginal is the mixture P ‾ = ∑ i = 1 n a i P i \overline{\mathbb{P}}=\sum_{i=1}^n a_i\mathbb{P}_i P = ∑ i = 1 n a i P i , the W-MEP result follows directly,
sup { P i ∈ P p ( R d ) } i = 1 n h P ‾ ( V ) s.t. ∑ i = 1 n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) ≤ ζ p . \sup_{\{\mathbb{P}_i\in\mathcal{P}_p(\mathbb{R}^d)\}_{i=1}^n}h_{\overline{\mathbb{P}}}(V)
\quad\text{s.t.}\quad
\sum_{i=1}^n a_i\int_{\mathbb{R}^d}\lVert x_i-v\rVert_p^p\,\mathrm{d}\mathbb{P}_i(v)\leq\zeta^p. { P i ∈ P p ( R d ) } i = 1 n sup h P ( V ) s.t. i = 1 ∑ n a i ∫ R d ∥ x i − v ∥ p p d P i ( v ) ≤ ζ p .
Under a discretely supported nominal distribution, W-MEP maximizes the differential entropy of the mixture induced by the conditional transport distributions { P i } i = 1 n \{\mathbb{P}_i\}_{i=1}^{n} { P i } i = 1 n , subject to the same average transport constraint as A-MEP. In contrast, A-MEP maximizes the average of their individual differential entropies, whereas W-MEP maximizes the entropy of the average marginals.
Corollary 5.1 (Fully discrete representation). Suppose that the perturbed variable is restricted to the finite set { v 1 , … , v m } \{v_1,\ldots,v_m\} { v 1 , … , v m } and consider an empirical, finitely supported nominal distribution as in (3) . Define, for each i = 1 , … , n i=1,\ldots,n i = 1 , … , n ,
b i j : = P V ∣ X = x i ( v j ) , j = 1 , … , m , b_{ij} := \mathbb{P}_{V\mid X=x_i}(v_j), \qquad j=1,\ldots,m, b ij := P V ∣ X = x i ( v j ) , j = 1 , … , m , and let b i = ( b i 1 , … , b i m ) ∈ Δ m b_i=(b_{i1},\ldots,b_{im})\in\Delta_m b i = ( b i 1 , … , b im ) ∈ Δ m where Δ m = { b ∈ R + m : ∑ j = 1 m b j = 1 } \Delta_m=\left\{b\in\mathbb{R}_+^m:\sum_{j=1}^{m}b_j=1\right\} Δ m = { b ∈ R + m : ∑ j = 1 m b j = 1 } . Then the A-MEP problem admits the finite-dimensional representation
sup { b i ∈ Δ m } i = 1 n ∑ i = 1 n a i H ( b i ) \sup_{\{b_i\in\Delta_m\}_{i=1}^{n}} \quad\sum_{i=1}^{n}a_i\mathrm{H}(b_i) { b i ∈ Δ m } i = 1 n sup i = 1 ∑ n a i H ( b i ) s . t . ∑ i = 1 n ∑ j = 1 m a i b i j ∥ x i − v j ∥ p p ≤ ζ p , \mathrm{s.t.}\quad\sum_{i=1}^{n}\sum_{j=1}^{m}a_i b_{ij}\lVert x_i-v_j\rVert_p^p\leq\zeta^p, s.t. i = 1 ∑ n j = 1 ∑ m a i b ij ∥ x i − v j ∥ p p ≤ ζ p , with H ( b i ) = − ∑ j = 1 m b i j log b i j \mathrm{H}(b_i)=-\sum_{j=1}^{m}b_{ij}\log b_{ij} H ( b i ) = − ∑ j = 1 m b ij log b ij . Moreover, the W-MEP problem admits the equivalent representation
sup { b i ∈ Δ m } i = 1 n H ( ∑ i = 1 n a i b i ) \sup_{\{b_i\in\Delta_m\}_{i=1}^{n}} \quad\mathrm{H}\left(\sum_{i=1}^{n}a_i b_i\right) { b i ∈ Δ m } i = 1 n sup H ( i = 1 ∑ n a i b i ) s . t . ∑ i = 1 n ∑ j = 1 m a i b i j ∥ x i − v j ∥ p p ≤ ζ p . \mathrm{s.t.}\quad\sum_{i=1}^{n}\sum_{j=1}^{m}a_i b_{ij}\lVert x_i-v_j\rVert_p^p\leq\zeta^p. s.t. i = 1 ∑ n j = 1 ∑ m a i b ij ∥ x i − v j ∥ p p ≤ ζ p .
Proof. This is the fully discrete specialization of Proposition 5.1. Indeed, since V ∈ V V\in\mathcal{V} V ∈ V , each conditional law b i = P V ∣ X = x i b_i=\mathbb{P}_{V\mid X=x_i} b i = P V ∣ X = x i is identified with a probability vector b i ∈ Δ m b_i\in\Delta_m b i ∈ Δ m , and its entropy is H ( b i ) = − ∑ j = 1 m b i j log b i j \mathrm{H}(b_i)=-\sum_{j=1}^{m}b_{ij}\log b_{ij} H ( b i ) = − ∑ j = 1 m b ij log b ij . The induced marginal satisfies P V ( v j ) = ∑ i = 1 n a i b i j \mathbb{P}_V(v_j)=\sum_{i=1}^{n}a_i b_{ij} P V ( v j ) = ∑ i = 1 n a i b ij , and the average transport cost becomes ∑ i = 1 n a i ∑ j = 1 m b i j ∥ x i − v j ∥ p p \sum_{i=1}^{n}a_i\sum_{j=1}^{m}b_{ij}\lVert x_i-v_j\rVert_p^p ∑ i = 1 n a i ∑ j = 1 m b ij ∥ x i − v j ∥ p p . Substituting these expressions into the A-MEP and W-MEP representations of Proposition 5.1 gives the fully discrete representations of A-MEP and W-MEP.
Entropy gap
Consider the empirical, finitely supported nominal distribution, in (3) , and let { P i A } i = 1 n \{\mathbb{P}^{A}_i\}_{i=1}^{n} { P i A } i = 1 n and { P i W } i = 1 n \{\mathbb{P}^{W}_i\}_{i=1}^{n} { P i W } i = 1 n denote optimal conditional perturbation laws for A-MEP and W-MEP, respectively. Define the corresponding induced marginals,
P ‾ A : = ∑ i = 1 n a i P i A , P ‾ W : = ∑ i = 1 n a i P i W , \overline{\mathbb{P}}^{A}:=\sum_{i=1}^{n}a_i\mathbb{P}^{A}_i,\qquad\overline{\mathbb{P}}^{W}:=\sum_{i=1}^{n}a_i\mathbb{P}^{W}_i, P A := i = 1 ∑ n a i P i A , P W := i = 1 ∑ n a i P i W ,
and suppose that the relevant differential entropies are finite. The following proposition characterizes the gap between the results in Proposition 5.1,
Δ = h P ‾ W ( V ) − ∑ i = 1 n a i h P i A ( V ) . \Delta=h_{\overline{\mathbb{P}}^{W}}(V)-\sum_{i=1}^{n}a_i h_{\mathbb{P}^{A}_i}(V). Δ = h P W ( V ) − i = 1 ∑ n a i h P i A ( V ) .
Proposition 5.2 (Decomposition of the entropy gap). The entropy gap Δ \Delta Δ admits an exact decomposition,
Δ = h P ‾ W ( V ) − h P ‾ A ( V ) + ∑ i = 1 n a i KL ( P i A ∥ P i A | P ‾ A ) , \Delta=h_{\overline{\mathbb{P}}^{W}}(V)-h_{\overline{\mathbb{P}}^{A}}(V)+\sum_{i=1}^{n}a_i\operatorname{KL}\left(\mathbb{P}^{A}_i\middle\|\mathbb{P}^{A}_i\middle|\overline{\mathbb{P}}^{A}\right), Δ = h P W ( V ) − h P A ( V ) + i = 1 ∑ n a i KL ( P i A P i A P A ) , equivalently given by,
Δ = h P ‾ W ( V ) − h P ‾ A ( V ) + I P X , V A ( X ; V ) . \Delta=h_{\overline{\mathbb{P}}^{W}}(V)-h_{\overline{\mathbb{P}}^{A}}(V)+I_{\mathbb{P}^{A}_{X,V}}(X;V). Δ = h P W ( V ) − h P A ( V ) + I P X , V A ( X ; V ) .
Proof. From the finite-support representations of A-MEP, A = ∑ i = 1 n a i h P i A ( V ) A = \sum_{i=1}^{n} a_i h_{\mathbb P_i^A}(V) A = ∑ i = 1 n a i h P i A ( V ) , and W-MEP, W = h P W ( V ) W = h_{\mathbb P^W}(V) W = h P W ( V ) . Hence Δ = W − A = h P W ( V ) − ∑ i = 1 n a i h P i A ( V ) \Delta= W-A = h_{\mathbb P^W}(V) - \sum_{i=1}^{n} a_i h_{\mathbb P_i^A}(V) Δ = W − A = h P W ( V ) − ∑ i = 1 n a i h P i A ( V ) . Adding and subtracting h P A ( V ) h_{\mathbb P^A}(V) h P A ( V ) gives
Δ = h P W ( V ) − h P A ( V ) + h P A ( V ) − ∑ i = 1 n a i h P i A ( V ) . \Delta= h_{\mathbb P^W}(V) - h_{\mathbb P^A}(V) + h_{\mathbb P^A}(V) - \sum_{i=1}^{n} a_i h_{\mathbb P_i^A}(V). Δ = h P W ( V ) − h P A ( V ) + h P A ( V ) − i = 1 ∑ n a i h P i A ( V ) .
It remains to identify the second term. Let p i A p_i^A p i A denote the density of P i A \mathbb P_i^A P i A with respect to Lebesgue measure and define p ‾ A ( v ) : = ∑ i = 1 n a i p i A ( v ) \overline{p}^A(v) := \sum_{i=1}^{n} a_i p_i^A(v) p A ( v ) := ∑ i = 1 n a i p i A ( v ) , which is the density of P ‾ A \overline{\mathbb P}^A P A . Then
∑ i = 1 n a i KL ( P i A ∥ P ‾ A ) = ∑ i = 1 n a i ∫ R d p i A ( v ) log p i A ( v ) p ‾ A ( v ) d l = ∑ i = 1 n a i ∫ R d p i A ( v ) log p i A ( v ) d v − ∑ i = 1 n a i ∫ R d p i A ( v ) log p ‾ A ( v ) d v . \begin{aligned}
\sum_{i=1}^{n} a_i \operatorname{KL}\left(\mathbb P_i^A \middle\| \overline{\mathbb P}^A\right)
=
\sum_{i=1}^{n} a_i \int_{\mathbb R^d} p_i^A(v)\log\frac{p_i^A(v)}{\overline{p}^A(v)}\,\mathrm{d}l \\
&=
\sum_{i=1}^{n} a_i \int_{\mathbb R^d} p_i^A(v)\log p_i^A(v)\,\mathrm{d}v
-
\sum_{i=1}^{n} a_i \int_{\mathbb R^d} p_i^A(v)\log\overline{p}^A(v)\,\mathrm{d}v.
\end{aligned} i = 1 ∑ n a i KL ( P i A P A ) = i = 1 ∑ n a i ∫ R d p i A ( v ) log p A ( v ) p i A ( v ) d l = i = 1 ∑ n a i ∫ R d p i A ( v ) log p i A ( v ) d v − i = 1 ∑ n a i ∫ R d p i A ( v ) log p A ( v ) d v .
Using ∑ i = 1 n a i p i A ( v ) = p ‾ A ( v ) \sum_{i=1}^{n} a_i p_i^A(v) = \overline{p}^A(v) ∑ i = 1 n a i p i A ( v ) = p A ( v ) , the second term becomes
∑ i = 1 n a i ∫ R d p i A ( v ) log p ‾ A ( v ) d v = ∫ R d p ‾ A ( v ) log p ‾ A ( v ) d v . \sum_{i=1}^{n} a_i \int_{\mathbb R^d} p_i^A(v)\log\overline{p}^A(v)\,\mathrm{d}v
=
\int_{\mathbb R^d} \overline{p}^A(v)\log\overline{p}^A(v)\,\mathrm{d}v. i = 1 ∑ n a i ∫ R d p i A ( v ) log p A ( v ) d v = ∫ R d p A ( v ) log p A ( v ) d v .
Therefore,
∑ i = 1 n a i KL ( P i A ∥ P ‾ A ) = ∑ i = 1 n a i ∫ R d p i A ( v ) log p i A ( v ) d v − ∫ R d p ‾ A ( v ) log p ‾ A ( v ) d v = h P ‾ A ( V ) − ∑ i = 1 n a i h P i A ( V ) . \begin{aligned}
\sum_{i=1}^{n} a_i \operatorname{KL}\left(\mathbb P_i^A \middle\| \overline{\mathbb P}^A\right)
=
\sum_{i=1}^{n} a_i \int_{\mathbb R^d} p_i^A(v)\log p_i^A(v)\,\mathrm{d}v
-
\int_{\mathbb R^d} \overline{p}^A(v)\log\overline{p}^A(v)\,\mathrm{d}v \\
&= h_{\overline{\mathbb P}^A}(V) - \sum_{i=1}^{n} a_i h_{\mathbb P_i^A}(V).
\end{aligned} i = 1 ∑ n a i KL ( P i A P A ) = i = 1 ∑ n a i ∫ R d p i A ( v ) log p i A ( v ) d v − ∫ R d p A ( v ) log p A ( v ) d v = h P A ( V ) − i = 1 ∑ n a i h P i A ( V ) .
Substituting this identity into the expression for Δ \Delta Δ yields
Δ = h P W ( V ) − h P ‾ A ( V ) + ∑ i = 1 n a i KL ( P i A ∥ P ‾ A ) . \Delta= h_{\mathbb P^W}(V) - h_{\overline{\mathbb P}^A}(V) + \sum_{i=1}^{n} a_i \operatorname{KL}\left(\mathbb P_i^A \middle\| \overline{\mathbb P}^A\right). Δ = h P W ( V ) − h P A ( V ) + i = 1 ∑ n a i KL ( P i A P A ) .
Finally, under the A-MEP joint law,
P X , V A ( x , v ) = ∑ i = 1 n a i δ x i ( x ) d P i A ( v ) , \mathbb P_{X,V}^A(x,v) = \sum_{i=1}^{n} a_i \delta_{x_i}(x)\,\mathrm{d}\mathbb P_i^A(v), P X , V A ( x , v ) = i = 1 ∑ n a i δ x i ( x ) d P i A ( v ) ,
the conditional law of V V V given X = x i X=x_i X = x i is P i A \mathbb P_i^A P i A , while the V V V -marginal is P ‾ A \overline{\mathbb P}^A P A . Hence
I P X , V A ( X ; V ) = ∑ i = 1 n a i KL ( P i A ∥ P ‾ A ) , I_{\mathbb P_{X,V}^A}(X;V) = \sum_{i=1}^{n} a_i \operatorname{KL}\left(\mathbb P_i^A \middle\| \overline{\mathbb P}^A\right), I P X , V A ( X ; V ) = i = 1 ∑ n a i KL ( P i A P A ) ,
which proves the equivalent mutual-information representation. □
Remark 5.1 (Jensen–Shannon divergence) The last term is the equal-weight Jensen–Shannon divergence [18 ] ,
JS ( P 1 A , … , P n A ) : = ∑ i = 1 n a i KL ( P i A ∥ a i ∑ j = 1 n P j A ) \operatorname{JS}(\mathbb P_1^A,\ldots,\mathbb P_n^A) := \sum_{i=1}^{n} a_i \operatorname{KL}\left(\mathbb P_i^A \middle\| a_i\sum_{j=1}^{n}\mathbb P_j^A\right) JS ( P 1 A , … , P n A ) := i = 1 ∑ n a i KL ( P i A a i j = 1 ∑ n P j A )
and therefore
Δ = h P W ( V ) − h P ‾ A ( V ) + JS ( P 1 A , … , P n A ) . \Delta= h_{\mathbb P^W}(V) - h_{\overline{\mathbb P}^A}(V) + \operatorname{JS}(\mathbb P_1^A,\ldots,\mathbb P_n^A). Δ = h P W ( V ) − h P A ( V ) + JS ( P 1 A , … , P n A ) .
The decomposition separates two sources of discrepancy between A-MEP and W-MEP. The first term, h P W ( V ) − h P ‾ A ( V ) h_{\mathbb P^W}(V) - h_{\overline{\mathbb P}^A}(V) h P W ( V ) − h P A ( V ) , measures the gain in marginal entropy obtained by optimizing directly over the perturbed marginal. The second term is the mutual information retained by the A-MEP perturbation mechanism, or equivalently the weighted Jensen–Shannon divergence among its conditional perturbation laws.
A symmetric two-point example
We conclude this section with a simple one-dimensional example illustrating the entropy-gap decomposition in Proposition 5.2. Let p = 2 p=2 p = 2 , and consider, on R \mathbb{R} R , the symmetric nominal distribution
P X = 1 2 δ − a + 1 2 δ a . \mathbb{P}_{X}=\frac{1}{2}\delta_{-a}+\frac{1}{2}\delta_{a}. P X = 2 1 δ − a + 2 1 δ a .
For A-MEP, Corollary 3.1 gives the optimal additive Gaussian perturbation V = X + Z V=X+Z V = X + Z , Z ∼ N ( 0 , ζ 2 ) Z\sim\mathcal{N}(0,\zeta^{2}) Z ∼ N ( 0 , ζ 2 ) and Z ⊥ X Z\perp X Z ⊥ X . Hence, the two optimal conditional laws are
P − A = N ( − a , ζ 2 ) , P + A = N ( a , ζ 2 ) , \mathbb{P}^{A}_{-}=\mathcal{N}(-a,\zeta^{2}),\qquad\mathbb{P}^{A}_{+}=\mathcal{N}(a,\zeta^{2}), P − A = N ( − a , ζ 2 ) , P + A = N ( a , ζ 2 ) ,
and the corresponding induced marginal is the Gaussian mixture
P V A = 1 2 P − A + 1 2 P + A = 1 2 N ( − a , ζ 2 ) + 1 2 N ( a , ζ 2 ) . \mathbb{P}^{A}_{V}=\frac{1}{2}\mathbb{P}^{A}_{-}+\frac{1}{2}\mathbb{P}^{A}_{+}=\frac{1}{2}\mathcal{N}(-a,\zeta^{2})+\frac{1}{2}\mathcal{N}(a,\zeta^{2}). P V A = 2 1 P − A + 2 1 P + A = 2 1 N ( − a , ζ 2 ) + 2 1 N ( a , ζ 2 ) .
The A-MEP optimal value follows directly from Corollary 3.1,
A ζ = h P X , V ( V ∣ X ) = 1 2 log ( 2 π e ζ 2 ) . A_{\zeta}=h_{\mathbb{P}_{X,V}}(V\mid X)=\frac{1}{2}\log(2\pi e\zeta^{2}). A ζ = h P X , V ( V ∣ X ) = 2 1 log ( 2 π e ζ 2 ) .
In contrast, W-MEP maximizes the entropy of the induced marginal over the Wasserstein ball. Since P X \mathbb{P}_{X} P X is symmetric around the origin, an optimal W-MEP marginal may be chosen symmetric. Indeed, for any feasible marginal P V \mathbb{P}_{V} P V , let P V − \mathbb{P}_{V_-} P V − denote the distribution of − V -V − V and let
Q = 1 2 P V + 1 2 P V − . \mathbb{Q}=\frac{1}{2}\mathbb{P}_{V}+\frac{1}{2}\mathbb{P}_{V_-}. Q = 2 1 P V + 2 1 P V − .
Since X X X and − X -X − X have the same distribution and the quadratic transport cost is invariant under reflection,
W 2 ( P X , P V − ) = W 2 ( P X , P V ) . W_{2}(\mathbb{P}_{X},\mathbb{P}_{V_-})=W_{2}(\mathbb{P}_{X},\mathbb{P}_{V}). W 2 ( P X , P V − ) = W 2 ( P X , P V ) .
Moreover, W 2 2 ( P X , ⋅ ) W_{2}^{2}(\mathbb{P}_{X},\cdot) W 2 2 ( P X , ⋅ ) is convex with respect to mixtures, so
W 2 2 ( P X , Q ) ≤ 1 2 W 2 2 ( P X , P V ) + 1 2 W 2 2 ( P X , P V − ) = W 2 2 ( P X , P V ) . W_{2}^{2}(\mathbb{P}_{X},\mathbb{Q})\leq\frac{1}{2}W_{2}^{2}(\mathbb{P}_{X},\mathbb{P}_{V})+\frac{1}{2}W_{2}^{2}(\mathbb{P}_{X},\mathbb{P}_{V_-})=W_{2}^{2}(\mathbb{P}_{X},\mathbb{P}_{V}). W 2 2 ( P X , Q ) ≤ 2 1 W 2 2 ( P X , P V ) + 2 1 W 2 2 ( P X , P V − ) = W 2 2 ( P X , P V ) .
Hence, if P V \mathbb{P}_{V} P V is feasible, then Q \mathbb{Q} Q is also feasible. On the other hand, differential entropy is concave and invariant under reflection, and therefore
h ( Q ) ≥ 1 2 h ( P V ) + 1 2 h ( P V − ) = h ( P V ) . h(\mathbb{Q})\geq\frac{1}{2}h(\mathbb{P}_{V})+\frac{1}{2}h(\mathbb{P}_{V_-})=h(\mathbb{P}_{V}). h ( Q ) ≥ 2 1 h ( P V ) + 2 1 h ( P V − ) = h ( P V ) .
Thus, symmetrization does not increase the Wasserstein cost and does not decrease the entropy. Consequently, an optimal marginal may be taken symmetric about the origin. Furthermore, the Wasserstein distance can be characterized explicitly using the cumulative distribution function [22 Proposition 2.17] ,
W 2 2 ( P X , P V ) = ∫ 0 1 ∣ F X − 1 ( t ) − F V − 1 ( t ) ∣ 2 d t , W_{2}^{2}(\mathbb{P}_{X},\mathbb{P}_{V})=\int_{0}^{1}\left|F_{X}^{-1}(t)-F_{V}^{-1}(t)\right|^{2}\,\mathrm{d}t, W 2 2 ( P X , P V ) = ∫ 0 1 F X − 1 ( t ) − F V − 1 ( t ) 2 d t ,
where F − 1 F^{-1} F − 1 denotes the generalized inverse of the corresponding cumulative distribution function. In the particular case in this section, the generalized inverse is
F X − 1 ( t ) = { − a , 0 < t < 1 2 , a , 1 2 < t < 1. F_{X}^{-1}(t)=
\begin{cases}
-a, & 0<t<\frac{1}{2},\\
a, & \frac{1}{2}<t<1.
\end{cases} F X − 1 ( t ) = { − a , a , 0 < t < 2 1 , 2 1 < t < 1.
Therefore,
W 2 2 ( P X , P V ) = ∫ 0 1 / 2 ( F V − 1 ( t ) + a ) 2 d t + ∫ 1 / 2 1 ( F V − 1 ( t ) − a ) 2 d t . W_{2}^{2}(\mathbb{P}_{X},\mathbb{P}_{V})=\int_{0}^{1/2}\left(F_{V}^{-1}(t)+a\right)^{2}\,\mathrm{d}t+\int_{1/2}^{1}\left(F_{V}^{-1}(t)-a\right)^{2}\,\mathrm{d}t. W 2 2 ( P X , P V ) = ∫ 0 1/2 ( F V − 1 ( t ) + a ) 2 d t + ∫ 1/2 1 ( F V − 1 ( t ) − a ) 2 d t .
Since P V \mathbb{P}_{V} P V may be taken symmetric around the origin, F V − 1 ( 1 − t ) = − F V − 1 ( t ) F_{V}^{-1}(1-t)=-F_{V}^{-1}(t) F V − 1 ( 1 − t ) = − F V − 1 ( t ) for t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) . Changing variables t ↦ 1 − t t\mapsto1-t t ↦ 1 − t in the first integral,
W 2 2 ( P X , P V ) = 2 ∫ 1 / 2 1 ( F V − 1 ( t ) − a ) 2 d t = ∫ 0 1 ( ∣ F V − 1 ( t ) ∣ − a ) 2 d t , W_{2}^{2}(\mathbb{P}_{X},\mathbb{P}_{V})=2\int_{1/2}^{1}\left(F_{V}^{-1}(t)-a\right)^{2}\,\mathrm{d}t=\int_{0}^{1}\left(\left|F_{V}^{-1}(t)\right|-a\right)^{2}\,\mathrm{d}t, W 2 2 ( P X , P V ) = 2 ∫ 1/2 1 ( F V − 1 ( t ) − a ) 2 d t = ∫ 0 1 ( F V − 1 ( t ) − a ) 2 d t ,
where the equality holds by the symmetry argument. Alternatively, in the usual measure notation,
W 2 2 ( P X , P V ) = ∫ R ( ∣ v ∣ − a ) 2 d P V ( v ) . W_2^2(\mathbb{P}_X,\mathbb{P}_V) = \int_{\mathbb{R}} (|v| - a)^2 \,\mathrm{d}\mathbb{P}_V(v). W 2 2 ( P X , P V ) = ∫ R ( ∣ v ∣ − a ) 2 d P V ( v ) .
As a result, the W-MEP simplifies to,
sup P V ∈ P 2 ( X ) h ( V ) s.t. E V [ ( ∣ v ∣ − a ) 2 ] ≤ ζ 2 . \begin{aligned}
\sup_{\mathbb{P}_V \in\mathcal{P}_2(\mathcal{X})} \quad& h(V) \\
\text{s.t.} \quad& \mathbb{E}_V\left[(|v| - a)^2\right] \le\zeta^2.
\end{aligned} P V ∈ P 2 ( X ) sup s.t. h ( V ) E V [ ( ∣ v ∣ − a ) 2 ] ≤ ζ 2 .
The problem is now a standard maximum-entropy problem under an expectation constraint. By the same Gibbs variational argument used in Proposition 3.1, its optimal density is therefore of the form
p V W ( v ) = 1 Z ( α ) exp ( − α ( ∣ v ∣ − a ) 2 ) , α > 0 , p_V^W(v) = \frac{1}{Z(\alpha)}\exp\left(-\alpha(|v| - a)^2\right), \qquad\alpha> 0, p V W ( v ) = Z ( α ) 1 exp ( − α ( ∣ v ∣ − a ) 2 ) , α > 0 ,
with,
Z ( α ) = ∫ R exp ( − α ( ∣ v ∣ − a ) 2 ) d v = π α ( 1 + erf ( a α ) ) . Z(\alpha) = \int_{\mathbb{R}} \exp\left(-\alpha(|v| - a)^2\right)\,\mathrm{d}v = \sqrt{\frac{\pi}{\alpha}}\left(1+\operatorname{erf}(a\sqrt{\alpha})\right). Z ( α ) = ∫ R exp ( − α ( ∣ v ∣ − a ) 2 ) d v = α π ( 1 + erf ( a α ) ) .
Furthermore, the optimal multiplier α ⋆ \alpha^\star α ⋆ is chosen so that the transport constraint is active,
E V [ ( ∣ v ∣ − a ) 2 ] = ζ 2 . \mathbb{E}_V\left[(|v| - a)^2\right] = \zeta^2. E V [ ( ∣ v ∣ − a ) 2 ] = ζ 2 .
Figure 1 illustrates the resulting difference between the A-MEP and W-MEP optimal marginals for a representative choice of a a a and ζ \zeta ζ .
Figure 1. Optimal induced marginals under A-MEP and W-MEP for P X = 1 2 δ − a + 1 2 δ a \mathbb{P}_X = \frac{1}{2}\delta_{-a} + \frac{1}{2}\delta_a P X = 2 1 δ − a + 2 1 δ a , with a = 1 a = 1 a = 1 and ζ = 0.6 \zeta= 0.6 ζ = 0.6 . The A-MEP marginal is the Gaussian mixture P V A = 1 2 N ( − a , ζ 2 ) + 1 2 N ( a , ζ 2 ) P_V^{A} = \frac{1}{2}\mathcal{N}(-a,\zeta^2) + \frac{1}{2}\mathcal{N}(a,\zeta^2) P V A = 2 1 N ( − a , ζ 2 ) + 2 1 N ( a , ζ 2 ) , whereas the W-MEP marginal has density p V W ( v ) ∝ exp [ − α ⋆ ( ∣ v ∣ − a ) 2 ] p_V^{W}(v) \propto\exp[-\alpha^\star(|v| - a)^2] p V W ( v ) ∝ exp [ − α ⋆ ( ∣ v ∣ − a ) 2 ] , with α ⋆ ≈ 1.094 \alpha^\star\approx1.094 α ⋆ ≈ 1.094 determined by the active transport constraint. Dashed lines indicate the nominal support points { − a , a } \{-a,a\} { − a , a } .
The corresponding W-MEP optimal value is
W ζ = log Z ( α ⋆ ) + α ⋆ ζ 2 , W_\zeta= \log Z(\alpha^\star) + \alpha^\star\zeta^2, W ζ = log Z ( α ⋆ ) + α ⋆ ζ 2 ,
and hence the entropy gap is
Δ ζ = log Z ( α ⋆ ) + α ⋆ ζ 2 − 1 2 log ( 2 π e ζ 2 ) . \Delta_\zeta= \log Z(\alpha^\star) + \alpha^\star\zeta^2 - \frac{1}{2}\log(2\pi e\zeta^2). Δ ζ = log Z ( α ⋆ ) + α ⋆ ζ 2 − 2 1 log ( 2 π e ζ 2 ) .
This strict gap provides a concrete illustration of the distinction motivating the two formulations. A-MEP constrains the transition from each nominal realization X X X to its perturbation V V V , and the resulting optimal kernel therefore retains information about the nominal support point from which V V V originates. W-MEP, in contrast, constrains only the perturbed marginal and does not require the entropy-bearing mechanism to preserve this individual correspondence. The additional freedom at the distributional level allows W-MEP to attain a strictly larger entropy, as quantified here by Δ ζ > 0 \Delta_\zeta> 0 Δ ζ > 0 .
Conclusion
This paper investigated a tractable approximation to Wasserstein-constrained maximum-entropy inference through an average-transport formulation. We showed that A-MEP admits an explicit generalized-Gaussian additive-noise solution on R d \mathbb{R}^d R d , providing a computationally simple construction of a feasible distribution for W-MEP. We established quantitative bounds on the difference between their optimal values, including an explicit upper bound depending on the transport radius, dimension, and dispersion of the nominal distribution. This bound vanishes as the transport radius increases, providing a regime in which A-MEP approximates the optimal value of W-MEP arbitrarily closely.
The approximation guarantees follow from an information-theoretic characterization of the two formulations. We showed that A-MEP and W-MEP admit a common feasible-marginal representation, under which W-MEP maximizes marginal entropy, whereas A-MEP additionally penalizes the mutual information between the nominal and perturbed variables. We also derived a dual characterization of W-MEP in terms of Kantorovich potentials and, for finitely supported nominal distributions, an exact decomposition of the entropy gap into a marginal-entropy gain and a weighted Jensen–Shannon divergence. A symmetric two-point example illustrated that the gap can be strict. Overall, these results establish A-MEP as a tractable surrogate for W-MEP with quantitative optimality guarantees, while identifying the retained dependence between nominal and perturbed variables as the source of their discrepancy.
Proofs
Proof of AMEP results
To prepare for the main result, we rewrite the conditional entropy in a form that separates its dependence on the marginal and conditional laws. This representation will serve as a convenient starting point for the analysis that follows.
Lemma A.1 (Equivalent representation of conditional entropy) For any joint distribution P X , V \mathbb{P}_{X,V} P X , V such that P V \mathbb{P}_V P V admits a density p ( v ) p(v) p ( v ) , the conditional entropy h P X , V ( V ∣ X ) h_{\mathbb{P}_{X,V}}(V|X) h P X , V ( V ∣ X ) admits the representation,
E X [ E V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] . \mathbb{E}_{X}\left[\mathbb{E}_{V|X}[-\log p(v)]-\operatorname{KL}(\mathbb{P}_{V|X}\|\mathbb{P}_V)\right]. E X [ E V ∣ X [ − log p ( v )] − KL ( P V ∣ X ∥ P V ) ] . Proof.
h P X , V ( V ∣ X ) = ∫ − log p ( v ∣ x ) p ( v , x ) d v d x h_{\mathbb{P}_{X,V}}(V|X)=\int-\log p(v|x)p(v,x)\,\mathrm{d}v\,\mathrm{d}x h P X , V ( V ∣ X ) = ∫ − log p ( v ∣ x ) p ( v , x ) d v d x = ∫ − log p ( v , x ) p ( x ) p ( v , x ) d v d x =\int-\log\frac{p(v,x)}{p(x)}p(v,x)\,\mathrm{d}v\,\mathrm{d}x = ∫ − log p ( x ) p ( v , x ) p ( v , x ) d v d x = ∬ ( − log p ( v ) p ( v ∣ x ) − log p ( v ∣ x ) p ( v ) p ( v ∣ x ) ) d v p ( x ) d x , =\iint\left(-\log p(v)p(v|x)-\log\frac{p(v|x)}{p(v)}p(v|x)\right)\,\mathrm{d}v\,p(x)\,\mathrm{d}x, = ∬ ( − log p ( v ) p ( v ∣ x ) − log p ( v ) p ( v ∣ x ) p ( v ∣ x ) ) d v p ( x ) d x , and we have the result,
E X [ E V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] . \mathbb{E}_{X}\left[\mathbb{E}_{V|X}[-\log p(v)]-\operatorname{KL}(\mathbb{P}_{V|X}\|\mathbb{P}_V)\right]. E X [ E V ∣ X [ − log p ( v )] − KL ( P V ∣ X ∥ P V ) ] . Note that these also hold in a discrete case, since h P X , V ( V ∣ X ) = ∑ x , v − log p ( v ∣ x ) p ( v , x ) h_{\mathbb{P}_{X,V}}(V|X)=\sum_{x,v}-\log p(v|x)p(v,x) h P X , V ( V ∣ X ) = ∑ x , v − log p ( v ∣ x ) p ( v , x ) and all log manipulations would equally hold.
This representation prepares the ground for a variational argument based on the Donsker–Varadhan variational formula (also known as the Gibbs variational principle) [5 , 6 , 7 , 8 , 11 , 28 ] .
Lemma A.2 (Donsker–Varadhan/Gibbs variational formula) Let ( Θ , F ) (\Theta,\mathcal{F}) ( Θ , F ) be a measurable space and let P \mathbb{P} P be a probability measure on it. For any measurable function f : Θ → R f:\Theta\to\mathbb{R} f : Θ → R such that E P [ e f ] < ∞ \mathbb{E}_{\mathbb{P}}[e^f]<\infty E P [ e f ] < ∞ and any probability measure Q \mathbb{Q} Q with Q ≪ P \mathbb{Q}\ll\mathbb{P} Q ≪ P , the following dual variational representations hold:
log E P [ e f ] = sup Q E Q [ f − KL ( Q ∥ P ) ] and KL ( Q ∥ P ) = sup f E Q [ f ] − log E P [ e f ] . \log\mathbb{E}_{\mathbb{P}}\left[e^f\right]=\sup_{\mathbb{Q}}\mathbb{E}_{\mathbb{Q}}[f-\operatorname{KL}(\mathbb{Q}\|\mathbb{P})]\qquad\text{and}\qquad\operatorname{KL}(\mathbb{Q}\|\mathbb{P})=\sup_f\mathbb{E}_{\mathbb{Q}}[f]-\log\mathbb{E}_{\mathbb{P}}\left[e^f\right]. log E P [ e f ] = Q sup E Q [ f − KL ( Q ∥ P )] and KL ( Q ∥ P ) = f sup E Q [ f ] − log E P [ e f ] . Moreover, the supremum in the first identity is attained at the Gibbs measure Q ⋆ \mathbb{Q}^{\star} Q ⋆ defined by
d Q ⋆ d P ( θ ) = e f ( θ ) E ϑ ∼ P [ e f ( ϑ ) ] . \frac{\mathrm{d}\mathbb{Q}^{\star}}{\mathrm{d}\mathbb{P}}(\theta)=\frac{e^{f(\theta)}}{\mathbb{E}_{\vartheta\sim\mathbb{P}}\left[e^{f(\vartheta)}\right]}. d P d Q ⋆ ( θ ) = E ϑ ∼ P [ e f ( ϑ ) ] e f ( θ ) . and the supremum in the second identity is attained (up to an additive constant) at
f ⋆ ( θ ) = log d Q d P ( θ ) . f^{\star}(\theta)=\log\frac{\mathrm{d}\mathbb{Q}}{\mathrm{d}\mathbb{P}}(\theta). f ⋆ ( θ ) = log d P d Q ( θ ) . The two identities are convex conjugates of each other in the sense of Fenchel–Legendre duality.
This identity provides a variational representation of log-partition functions in terms of KL divergence. It also yields exponentially tilted optimizers, which we exploit to derive the Gibbs structure under Wasserstein constraints.
The following proposition provides an exact formula for the integral ∫ R d exp ( − α ∥ x − v ∥ p p ) d v \int_{\mathbb{R}^d}\exp\left(-\alpha\|x-v\|_p^p\right)\,\mathrm{d}v ∫ R d exp ( − α ∥ x − v ∥ p p ) d v in terms of the unit ℓ p \ell_p ℓ p -ball volume and the Gamma function. This identity will be used in the proof of the main theorem to verify integrability and to simplify the resulting expressions.
Proposition A.1 (Integral for the q q q -radial kernel) Let d ∈ N d\in\mathbb{N} d ∈ N , p ≥ 1 p\ge1 p ≥ 1 , and α > 0 \alpha>0 α > 0 . For any x ∈ R d x\in\mathbb{R}^d x ∈ R d the following integral is finite, independent of x x x , and admits the closed form
∫ R d exp ( − α ∥ x − v ∥ p p ) d v = vol ( B p d ) Γ ( d / p ) p α d / p \int_{\mathbb{R}^d}\exp\left(-\alpha\|x-v\|_p^p\right)\,\mathrm{d}v=\operatorname{vol}(B_p^d)\frac{\Gamma(d/p)}{p\alpha^{d/p}} ∫ R d exp ( − α ∥ x − v ∥ p p ) d v = vol ( B p d ) p α d / p Γ ( d / p ) where ∥ ⋅ ∥ p \|\cdot\|_p ∥ ⋅ ∥ p denotes the ℓ p \ell_p ℓ p norm and the integral is with respect to Lebesgue measure on R d \mathbb{R}^d R d , Γ ( ⋅ ) \Gamma(\cdot) Γ ( ⋅ ) is the Gamma function,
Γ ( t ) = ∫ 0 ∞ s t − 1 e − s d s , t > 0 , \Gamma(t)=\int_0^\infty s^{t-1}e^{-s}\,\mathrm{d}s,\quad t>0, Γ ( t ) = ∫ 0 ∞ s t − 1 e − s d s , t > 0 , and B p d = { u ∈ R d : ∥ u ∥ p ≤ 1 } B_p^d=\{u\in\mathbb{R}^d:\|u\|_p\le1\} B p d = { u ∈ R d : ∥ u ∥ p ≤ 1 } is the ℓ p \ell_p ℓ p unit ball with
vol ( B p d ) = ( 2 Γ ( 1 + 1 / p ) ) d Γ ( 1 + d / p ) . \operatorname{vol}(B_p^d)=\frac{(2\Gamma(1+1/p))^d}{\Gamma(1+d/p)}. vol ( B p d ) = Γ ( 1 + d / p ) ( 2Γ ( 1 + 1/ p ) ) d .
Proof. Note that the integral,
∫ R d exp ( − α ∥ x − v ∥ p p ) d v , \int_{\mathbb{R}^{d}} \exp\left(-\alpha\lVert x-v\rVert_{p}^{p}\right)\,dv, ∫ R d exp ( − α ∥ x − v ∥ p p ) d v ,
takes the form
∫ R d exp ( − α ∥ u ∥ p p ) d u . \int_{\mathbb{R}^{d}} \exp\left(-\alpha\lVert u\rVert_{p}^{p}\right)\,du. ∫ R d exp ( − α ∥ u ∥ p p ) d u .
In the particular case of p = 2 p=2 p = 2 , we can use [9 Prop 2.51] , to write the above as,
σ ( S d − 1 ) ∫ 0 ∞ exp ( − α r p ) r d − 1 d r . \sigma\left(\mathbb{S}^{d-1}\right)\int_{0}^{\infty}\exp\left(-\alpha r^{p}\right)r^{d-1}\,dr. σ ( S d − 1 ) ∫ 0 ∞ exp ( − α r p ) r d − 1 d r .
That being said, this decomposition does not hold for a general ℓ p \ell_{p} ℓ p -ball. In this case we use [19 Prop. 1] , which tells us that, if p ≥ 1 p\ge1 p ≥ 1 , for B p d : = { u ∈ R d : ∥ u ∥ p ≤ 1 } B_{p}^{d}:=\{u\in\mathbb{R}^{d}:\lVert u\rVert_{p}\le1\} B p d := { u ∈ R d : ∥ u ∥ p ≤ 1 } and ∂ B p d = { u : ∥ u ∥ p = 1 } \partial B_{p}^{d}=\{u:\lVert u\rVert_{p}=1\} ∂ B p d = { u : ∥ u ∥ p = 1 } , with μ p \mu_{p} μ p as the cone probability measure on ∂ B p d \partial B_{p}^{d} ∂ B p d , i.e.
μ p ( A ) = vol ( { r z : 0 ≤ r ≤ 1 , z ∈ A } ) vol ( B p d ) \mu_{p}(A)=\frac{\operatorname{vol}\left(\{rz:0\le r\le1,\ z\in A\}\right)}{\operatorname{vol}\left(B_{p}^{d}\right)} μ p ( A ) = vol ( B p d ) vol ( { r z : 0 ≤ r ≤ 1 , z ∈ A } )
for Borel sets A ⊆ ∂ B p d A\subseteq\partial B_{p}^{d} A ⊆ ∂ B p d , then, for every integrable function f : R d → R f:\mathbb{R}^{d}\to\mathbb{R} f : R d → R ,
∫ R d f ( u ) d u = d vol ( B p d ) ∫ 0 ∞ r d − 1 ( ∫ ∂ B p d f ( r z ) d μ p ( z ) ) d r . (4) \int_{\mathbb{R}^{d}}f(u)\,du=d\operatorname{vol}\left(B_{p}^{d}\right)\int_{0}^{\infty}r^{d-1}\left(\int_{\partial B_{p}^{d}}f(rz)\,d\mu_{p}(z)\right)\,dr. \tag*{(4)} ∫ R d f ( u ) d u = d vol ( B p d ) ∫ 0 ∞ r d − 1 ( ∫ ∂ B p d f ( r z ) d μ p ( z ) ) d r . (4)
with the volume of the unit ℓ p \ell_{p} ℓ p -ball, for q > 0 q>0 q > 0 , given by [29 ] ,
vol ( B p d ) = ( 2 Γ ( 1 + 1 p ) ) d Γ ( 1 + d p ) . \operatorname{vol}\left(B_{p}^{d}\right)=\frac{\left(2\Gamma\left(1+\frac{1}{p}\right)\right)^{d}}{\Gamma\left(1+\frac{d}{p}\right)}. vol ( B p d ) = Γ ( 1 + p d ) ( 2Γ ( 1 + p 1 ) ) d .
Now, taking f ( u ) = exp ( − α ∥ u ∥ p p ) f(u)=\exp\left(-\alpha\lVert u\rVert_{p}^{p}\right) f ( u ) = exp ( − α ∥ u ∥ p p ) and using the fact that f ( r z ) = exp ( − α r p ) f(rz)=\exp\left(-\alpha r^{p}\right) f ( r z ) = exp ( − α r p ) for z ∈ ∂ B p d z\in\partial B_{p}^{d} z ∈ ∂ B p d (by definition of the ball), and knowing that μ p \mu_{p} μ p is a probability measure on ∂ B p d \partial B_{p}^{d} ∂ B p d , results in,
∫ R d exp ( − α ∥ u ∥ p p ) d u = d vol ( B p d ) ∫ 0 ∞ r d − 1 exp ( − α r p ) ( ∫ ∂ B p d d μ p ( z ) ) d r = d vol ( B p d ) ∫ 0 ∞ e − t ( t α ) d − 1 p 1 p α 1 / p t 1 p − 1 d t = d vol ( B p d ) ∫ 0 ∞ e − t ( 1 α ) d p 1 p t d p − 1 d t = d vol ( B p d ) Γ ( d / p ) p α d / p . \begin{aligned}
\int_{\mathbb{R}^{d}}\exp\left(-\alpha\lVert u\rVert_{p}^{p}\right)\,du
&=d\operatorname{vol}\left(B_{p}^{d}\right)\int_{0}^{\infty}r^{d-1}\exp\left(-\alpha r^{p}\right)\left(\int_{\partial B_{p}^{d}}d\mu_{p}(z)\right)\,dr\\
&=d\operatorname{vol}\left(B_{p}^{d}\right)\int_{0}^{\infty}e^{-t}\left(\frac{t}{\alpha}\right)^{\frac{d-1}{p}}\frac{1}{p\alpha^{1/p}}t^{\frac{1}{p}-1}\,dt\\
&=d\operatorname{vol}\left(B_{p}^{d}\right)\int_{0}^{\infty}e^{-t}\left(\frac{1}{\alpha}\right)^{\frac{d}{p}}\frac{1}{p}t^{\frac{d}{p}-1}\,dt\\
&=d\operatorname{vol}\left(B_{p}^{d}\right)\frac{\Gamma(d/p)}{p\alpha^{d/p}}.
\end{aligned} ∫ R d exp ( − α ∥ u ∥ p p ) d u = d vol ( B p d ) ∫ 0 ∞ r d − 1 exp ( − α r p ) ( ∫ ∂ B p d d μ p ( z ) ) d r = d vol ( B p d ) ∫ 0 ∞ e − t ( α t ) p d − 1 p α 1/ p 1 t p 1 − 1 d t = d vol ( B p d ) ∫ 0 ∞ e − t ( α 1 ) p d p 1 t p d − 1 d t = d vol ( B p d ) p α d / p Γ ( d / p ) .
where in the second equality we used the change of variable t = α r p t=\alpha r^{p} t = α r p and in the last equality we used the definition of the gamma function, Γ ( d ) = ∫ 0 ∞ x d − 1 e − x d x \Gamma(d)=\int_{0}^{\infty}x^{d-1}e^{-x}\,dx Γ ( d ) = ∫ 0 ∞ x d − 1 e − x d x .
This result together with the following dual formulation of the A-MEP problem, plays a central role in characterizing the Wasserstein-constrained solution.
Proposition A.2 (Dual formulation) Consider X ⊆ R d \mathcal{X}\subseteq\mathbb{R}^{d} X ⊆ R d , then, given P X ∈ P p ( X ) P_{\mathcal{X}}\in\mathcal{P}_{p}(\mathcal{X}) P X ∈ P p ( X ) , the optimization problem in (1) has the following dual formulation,
min α ≥ 0 α ζ p + E X [ log ∫ X exp ( − α ∥ x − v ∥ p p ) d v ] , \min_{\alpha\ge0}\ \alpha\zeta^{p}+\mathbb{E}_{X}\left[\log\int_{\mathcal{X}}\exp\left(-\alpha\lVert x-v\rVert_{p}^{p}\right)\,dv\right], α ≥ 0 min α ζ p + E X [ log ∫ X exp ( − α ∥ x − v ∥ p p ) d v ] , and Radon-Nikodym derivative,
d P V ∣ X d P V = exp ( − α ∥ x − v ∥ p p ) / p ( v ) E V [ exp ( − α ∥ x − v ∥ p p ) / p ( v ) ] . \frac{dP_{V\mid X}}{dP_{V}}=\frac{\exp\left(-\alpha\lVert x-v\rVert_{p}^{p}\right)/p(v)}{\mathbb{E}_{V}\left[\exp\left(-\alpha\lVert x-v\rVert_{p}^{p}\right)/p(v)\right]}. d P V d P V ∣ X = E V [ exp ( − α ∥ x − v ∥ p p ) / p ( v ) ] exp ( − α ∥ x − v ∥ p p ) / p ( v ) . Furthermore, if Slater’s condition holds, then strong duality holds and the KKT conditions are necessary and sufficient for optimality. In particular,
α ⋆ ≥ 0 , E X E V ∣ X ⋆ ∥ x − v ∥ p p ≤ ζ p , α ⋆ ( E X E V ∣ X ⋆ [ ∥ x − v ∥ p p ] − ζ p ) = 0. \alpha^{\star}\ge0,\qquad\mathbb{E}_{X}\mathbb{E}_{V\mid X}^{\star}\lVert x-v\rVert_{p}^{p}\le\zeta^{p},\qquad\alpha^{\star}\left(\mathbb{E}_{X}\mathbb{E}_{V\mid X}^{\star}\left[\lVert x-v\rVert_{p}^{p}\right]-\zeta^{p}\right)=0. α ⋆ ≥ 0 , E X E V ∣ X ⋆ ∥ x − v ∥ p p ≤ ζ p , α ⋆ ( E X E V ∣ X ⋆ [ ∥ x − v ∥ p p ] − ζ p ) = 0.
Proof. From lemma A.1 solving (1) is equivalent to solving,
sup P V ∣ X ∈ K p ( X ) E X [ E V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p . (5) \begin{aligned}
\sup_{P_{V\mid X}\in\mathcal{K}_{p}(\mathcal{X})}\quad
&\mathbb{E}_{X}\left[\mathbb{E}_{V\mid X}[-\log p(v)]-\operatorname{KL}\left(P_{V\mid X}\Vert P_{V}\right)\right]\\
\text{s.t.}\quad
&\mathbb{E}_{X}\mathbb{E}_{V\mid X}\left[\lVert x-v\rVert_{p}^{p}\right]\le\zeta^{p}. \tag*{(5)}
\end{aligned} P V ∣ X ∈ K p ( X ) sup s.t. E X [ E V ∣ X [ − log p ( v )] − KL ( P V ∣ X ∥ P V ) ] E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p . (5)
Now, taking the Lagrangian dual,
sup P V ∣ X ∈ K p ( X ) min α ≥ 0 E X [ E V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] − α ( E X [ E V ∣ X [ ∥ x − v ∥ p p ] − ζ p ] ) . \sup_{P_{V\mid X}\in\mathcal{K}_{p}(\mathcal{X})}\ \min_{\alpha\ge0}\ \mathbb{E}_{X}\left[\mathbb{E}_{V\mid X}[-\log p(v)]-\operatorname{KL}\left(P_{V\mid X}\Vert P_{V}\right)\right]-\alpha\left(\mathbb{E}_{X}\left[\mathbb{E}_{V\mid X}\left[\lVert x-v\rVert_{p}^{p}\right]-\zeta^{p}\right]\right). P V ∣ X ∈ K p ( X ) sup α ≥ 0 min E X [ E V ∣ X [ − log p ( v )] − KL ( P V ∣ X ∥ P V ) ] − α ( E X [ E V ∣ X [ ∥ x − v ∥ p p ] − ζ p ] ) .
and grouping the terms,
sup P V ∣ X ∈ K p ( X ) min α ≥ 0 E X [ E V ∣ X [ − log p ( v ) − α ∥ x − v ∥ p p ] − KL ( P V ∣ X ∥ P V ) − α ζ p ] . (6) \sup_{P_{V|X}\in\mathcal{K}_p(\mathcal{X})}\min_{\alpha\geq0}\mathbb{E}_{X}\left[\mathbb{E}_{V|X}\left[-\log p(v)-\alpha\lVert x-v\rVert_p^p\right]-\operatorname{KL}\left(P_{V|X}\middle\|P_V\right)-\alpha\zeta^p\right]. \tag*{(6)} P V ∣ X ∈ K p ( X ) sup α ≥ 0 min E X [ E V ∣ X [ − log p ( v ) − α ∥ x − v ∥ p p ] − KL ( P V ∣ X P V ) − α ζ p ] . (6)
At this point, all we can say is that weak duality holds, that is, (6) ≤ \leq ≤ (7) ,
min α ≥ 0 sup P V ∣ X ∈ K p ( X ) E X [ E V ∣ X [ − log p ( v ) − α ∥ x − v ∥ p p ] − KL ( P V ∣ X ∥ P V ) + α ζ p ] . (7) \min_{\alpha\geq0}\sup_{P_{V|X}\in\mathcal{K}_p(\mathcal{X})}\mathbb{E}_{X}\left[\mathbb{E}_{V|X}\left[-\log p(v)-\alpha\lVert x-v\rVert_p^p\right]-\operatorname{KL}\left(P_{V|X}\middle\|P_V\right)+\alpha\zeta^p\right]. \tag*{(7)} α ≥ 0 min P V ∣ X ∈ K p ( X ) sup E X [ E V ∣ X [ − log p ( v ) − α ∥ x − v ∥ p p ] − KL ( P V ∣ X P V ) + α ζ p ] . (7)
In the following steps we will show that (7) actually has an analytical solution. First, note that, as P X P_X P X is independent of P V ∣ X P_{V|X} P V ∣ X , we can look at the expected value of the sup,
min α ≥ 0 E X [ sup P V ∣ X ∈ K p ( X ) E V ∣ X [ − log p ( v ) − α ∥ x − v ∥ p p ] − KL ( P V ∣ X ∥ P V ) + α ζ p ] . \min_{\alpha\geq0}\mathbb{E}_X\left[\sup_{P_{V|X}\in\mathcal{K}_p(\mathcal{X})}\mathbb{E}_{V|X}\left[-\log p(v)-\alpha\lVert x-v\rVert_p^p\right]-\operatorname{KL}\left(P_{V|X}\middle\|P_V\right)+\alpha\zeta^p\right]. α ≥ 0 min E X [ P V ∣ X ∈ K p ( X ) sup E V ∣ X [ − log p ( v ) − α ∥ x − v ∥ p p ] − KL ( P V ∣ X P V ) + α ζ p ] .
Now take X = R d \mathcal{X}=\mathbb{R}^d X = R d and consider,
E V [ exp ( − log p ( v ) − α ∥ x − v ∥ p p ) ] = E V [ exp ( − α ∥ x − v ∥ p p ) p ( v ) ] = ∫ X exp ( − α ∥ x − v ∥ p p ) p ( v ) d P V = ∫ X exp ( − α ∥ x − v ∥ p p ) p ( v ) p ( v ) d v = ∫ X exp ( − α ∥ x − v ∥ p p ) d v . \begin{aligned}
\mathbb{E}_V\left[\exp\left(-\log p(v)-\alpha\lVert x-v\rVert_p^p\right)\right]
=
\mathbb{E}_V\left[\frac{\exp\left(-\alpha\lVert x-v\rVert_p^p\right)}{p(v)}\right] \\
&=
\int_{\mathcal{X}}\frac{\exp\left(-\alpha\lVert x-v\rVert_p^p\right)}{p(v)}\,\mathrm{d}P_V \\
&=
\int_{\mathcal{X}}\frac{\exp\left(-\alpha\lVert x-v\rVert_p^p\right)}{p(v)}p(v)\,\mathrm{d}v \\
&=
\int_{\mathcal{X}}\exp\left(-\alpha\lVert x-v\rVert_p^p\right)\,\mathrm{d}v.
\end{aligned} E V [ exp ( − log p ( v ) − α ∥ x − v ∥ p p ) ] = E V [ p ( v ) exp ( − α ∥ x − v ∥ p p ) ] = ∫ X p ( v ) exp ( − α ∥ x − v ∥ p p ) d P V = ∫ X p ( v ) exp ( − α ∥ x − v ∥ p p ) p ( v ) d v = ∫ X exp ( − α ∥ x − v ∥ p p ) d v .
By Proposition A.1, we know that the above is < ∞ <\infty < ∞ if α > 0 \alpha>0 α > 0 . Hence, we can apply Donsker-Varadhan/Gibbs variational principle (lemma A.2), and rewrite the inner sup,
min α > 0 α ζ p + E X [ log ∫ X exp ( − α ∥ x − v ∥ p p ) d v ] . \min_{\alpha>0}\alpha\zeta^p+\mathbb{E}_X\left[\log\int_{\mathcal{X}}\exp\left(-\alpha\lVert x-v\rVert_p^p\right)\,\mathrm{d}v\right]. α > 0 min α ζ p + E X [ log ∫ X exp ( − α ∥ x − v ∥ p p ) d v ] .
For the Radon-Nikodym derivative, we can use once more Donsker-Varadhan/Gibbs (lemma A.2),
d P V ∣ X ⋆ d P V = exp ( − α ∥ x − v ∥ p p ) p ( v ) 1 E V [ exp ( − α ∥ x − v ∥ p p ) p ( v ) ] . \frac{\mathrm{d}P^\star_{V|X}}{\mathrm{d}P_V}
=
\frac{\exp\left(-\alpha\lVert x-v\rVert_p^p\right)}{p(v)}
\frac{1}{\mathbb{E}_V\left[\dfrac{\exp\left(-\alpha\lVert x-v\rVert_p^p\right)}{p(v)}\right]}. d P V d P V ∣ X ⋆ = p ( v ) exp ( − α ∥ x − v ∥ p p ) E V [ p ( v ) exp ( − α ∥ x − v ∥ p p ) ] 1 .
Since the problem is convex, to guarantee strong duality it suffices to verify Slater’s condition, i.e., the existence of a strictly feasible point (an interior point in the relative sense) satisfying the inequality constraints with strict inequality. Under Slater’s condition, the KKT conditions are necessary and sufficient for optimality [1 ] , strong duality holds and optimal Lagrange multipliers exist. Consequently, the KKT conditions are necessary and sufficient for optimality and verifying KKT for the primal-dual optimal, ( α ⋆ , P V ∣ X ⋆ ) (\alpha^\star,P^\star_{V|X}) ( α ⋆ , P V ∣ X ⋆ ) , certifies primal optimality and a zero duality gap [1 ] .
Proof of Proposition 3.1
We finally have all the necessary tools for the proof of Proposition 3.1,
Proof. From Proposition A.2, we know that (1) has a dual representation,
min α > 0 α ζ p + E X [ log ∫ R d exp ( − α ∥ x − v ∥ p p ) d v ] . (8) \min_{\alpha>0}\alpha\zeta^p+\mathbb{E}_X\left[\log\int_{\mathbb{R}^d}\exp\left(-\alpha\lVert x-v\rVert_p^p\right)\,\mathrm{d}v\right]. \tag*{(8)} α > 0 min α ζ p + E X [ log ∫ R d exp ( − α ∥ x − v ∥ p p ) d v ] . (8)
Now, using the result of Proposition A.1 for the integral and (8) becomes,
min α > 0 α ζ p + log ( C p , d α d / p ) , \min_{\alpha>0}\alpha\zeta^p+\log\left(\frac{C_{p,d}}{\alpha^{d/p}}\right), α > 0 min α ζ p + log ( α d / p C p , d ) ,
where C p , d = d p vol ( B d p ) Γ ( d / p ) C_{p,d}=\frac{d}{p}\operatorname{vol}(B_d^p)\Gamma(d/p) C p , d = p d vol ( B d p ) Γ ( d / p ) .
At last, this optimization is solvable and has optimal argument α ⋆ = d p ζ p \alpha^\star=\frac{d}{p\zeta^p} α ⋆ = p ζ p d , since, for f ( α ) = α ζ p + log C p , d − log α d / p f(\alpha)=\alpha\zeta^p+\log C_{p,d}-\log\alpha^{d/p} f ( α ) = α ζ p + log C p , d − log α d / p ,
∂ ∂ α f ( α ) = ζ p − α − d / p d p α d / p − 1 = ζ p − d p α − 1 \begin{aligned}
\frac{\partial}{\partial\alpha}f(\alpha)=\zeta^p-\alpha^{-d/p}\frac{d}{p}\alpha^{d/p-1} \\
&=\zeta^p-\frac{d}{p}\alpha^{-1}
\end{aligned} ∂ α ∂ f ( α ) = ζ p − α − d / p p d α d / p − 1 = ζ p − p d α − 1
and optimal value d p + log ( d p vol ( B p d ) Γ ( d p ) ( p d ) d / p ζ d ) \frac{d}{p}+\log\left(\frac{d}{p}\operatorname{vol}(B_p^d)\Gamma\left(\frac{d}{p}\right)\left(\frac{p}{d}\right)^{d/p}\zeta^d\right) p d + log ( p d vol ( B p d ) Γ ( p d ) ( d p ) d / p ζ d ) . Leading to the result, by duality,
d p + log ( d p vol ( B p d ) Γ ( d p ) ( p d ) d / p ζ d ) ≥ sup P V ∣ X ∈ P E V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) \frac{d}{p}+\log\left(\frac{d}{p}\operatorname{vol}(B_p^d)\Gamma\left(\frac{d}{p}\right)\left(\frac{p}{d}\right)^{d/p}\zeta^d\right)\geq\sup_{\mathbb{P}_{V\mid X}\in\mathcal{P}}\mathbb{E}_{V\mid X}[-\log p(v)]-\operatorname{KL}\left(\mathbb{P}_{V\mid X}\,\middle\|\,\mathbb{P}_V\right) p d + log ( p d vol ( B p d ) Γ ( p d ) ( d p ) d / p ζ d ) ≥ P V ∣ X ∈ P sup E V ∣ X [ − log p ( v )] − KL ( P V ∣ X P V )
s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p . \text{s.t.}\qquad\mathbb{E}_X\mathbb{E}_{V\mid X}\left[\|x-v\|_p^p\right]\leq\zeta^p. s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p .
For the optimal measure, we know the Radon-Nikodym derivative from Proposition A.2,
d P V ∣ X ⋆ d P V = exp ( − α ∥ x − v ∥ p p ) p ( v ) E V [ exp ( − α ∥ x − v ∥ p p ) p ( v ) ] . \frac{\mathrm{d}\mathbb{P}^{\star}_{V\mid X}}{\mathrm{d}\mathbb{P}_V}=\frac{\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}}{\mathbb{E}_V\left[\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}\right]}. d P V d P V ∣ X ⋆ = E V [ p ( v ) exp ( − α ∥ x − v ∥ p p ) ] p ( v ) exp ( − α ∥ x − v ∥ p p ) .
This tells us that,
P V ∣ X ⋆ ( C , α ) = ∫ C exp ( − α ∥ x − v ∥ p p ) p ( v ) E V [ exp ( − α ∥ x − v ∥ p p ) p ( v ) ] d P V = ∫ C exp ( − α ∥ x − v ∥ p p ) p ( v ) E V [ exp ( − α ∥ x − v ∥ p p ) p ( v ) ] p ( v ) d v = ∫ C exp ( − α ∥ x − v ∥ p p ) E V [ exp ( − α ∥ x − v ∥ p p ) p ( v ) ] d v = ∫ C exp ( − α ∥ x − v ∥ p p ) ∫ R d exp ( − α ∥ x − v ∥ p p ) d v d v . \begin{aligned}
\mathbb{P}^{\star}_{V\mid X}(C,\alpha)=\int_C\frac{\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}}{\mathbb{E}_V\left[\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}\right]}\,\mathrm{d}\mathbb{P}_V \\
&=\int_C\frac{\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}}{\mathbb{E}_V\left[\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}\right]}p(v)\,\mathrm{d}v \\
&=\int_C\frac{\exp\left(-\alpha\|x-v\|_p^p\right)}{\mathbb{E}_V\left[\dfrac{\exp\left(-\alpha\|x-v\|_p^p\right)}{p(v)}\right]}\,\mathrm{d}v \\
&=\int_C\frac{\exp\left(-\alpha\|x-v\|_p^p\right)}{\int_{\mathbb{R}^d}\exp\left(-\alpha\|x-v\|_p^p\right)\,\mathrm{d}v}\,\mathrm{d}v.
\end{aligned} P V ∣ X ⋆ ( C , α ) = ∫ C E V [ p ( v ) exp ( − α ∥ x − v ∥ p p ) ] p ( v ) exp ( − α ∥ x − v ∥ p p ) d P V = ∫ C E V [ p ( v ) exp ( − α ∥ x − v ∥ p p ) ] p ( v ) exp ( − α ∥ x − v ∥ p p ) p ( v ) d v = ∫ C E V [ p ( v ) exp ( − α ∥ x − v ∥ p p ) ] exp ( − α ∥ x − v ∥ p p ) d v = ∫ C ∫ R d exp ( − α ∥ x − v ∥ p p ) d v exp ( − α ∥ x − v ∥ p p ) d v .
Resulting in an optimal argument,
P V ∣ X ⋆ ( C ) = p d vol ( B p d ) Γ ( d / p ) ( d p ) d / p ζ − d ∫ C exp ( − d p ζ p ∥ x − v ∥ p p ) d v . \mathbb{P}^{\star}_{V\mid X}(C)=\frac{p}{d\operatorname{vol}(B_p^d)\Gamma(d/p)}\left(\frac{d}{p}\right)^{d/p}\zeta^{-d}\int_C\exp\left(-\frac{d}{p\zeta^p}\|x-v\|_p^p\right)\,\mathrm{d}v. P V ∣ X ⋆ ( C ) = d vol ( B p d ) Γ ( d / p ) p ( p d ) d / p ζ − d ∫ C exp ( − p ζ p d ∥ x − v ∥ p p ) d v .
Now, to show strong duality we need to show Slater and KKT conditions as per Equation (5) :
Slater condition We need to check that there exists a strictly feasible point for Equation (5) . Assuming ζ > 0 \zeta>0 ζ > 0 , take U U U to be a uniform distribution on [ − δ , δ ] d [-\delta,\delta]^d [ − δ , δ ] d and independent of X X X . Define V = X + U V=X+U V = X + U , then E X , V [ ∥ x − v ∥ p p ] = E [ ∥ u ∥ p p ] ≤ C ( q ) δ p \mathbb{E}_{X,V}\left[\|x-v\|_p^p\right]=\mathbb{E}[\|u\|_p^p]\leq C(q)\delta^p E X , V [ ∥ x − v ∥ p p ] = E [ ∥ u ∥ p p ] ≤ C ( q ) δ p (with C ( q ) C(q) C ( q ) being a scaling factor to account for the norm used). Choosing δ \delta δ small enough such that C ( q ) δ p < ζ p C(q)\delta^p<\zeta^p C ( q ) δ p < ζ p guarantees that Slater’s condition is satisfied.
KKT conditions
– Dual feasibility: α ⋆ ≥ 0 \alpha^\star\geq0 α ⋆ ≥ 0 .
– Primal feasibility: ∫ X ∫ X ∥ x − v ∥ p p d P V ∣ X ⋆ ( v ) d P X ( x ) ≤ ζ p \int_{\mathcal{X}}\int_{\mathcal{X}}\|x-v\|_p^p\,\mathrm{d}\mathbb{P}^{\star}_{V\mid X}(v)\,\mathrm{d}\mathbb{P}_X(x)\leq\zeta^p ∫ X ∫ X ∥ x − v ∥ p p d P V ∣ X ⋆ ( v ) d P X ( x ) ≤ ζ p .
– Complementary slackness: α ⋆ ( ζ p − ∫ X ∫ X ∥ x − v ∥ p p d P V ∣ X ⋆ ( v ) d P X ( x ) ) = 0 \alpha^\star\left(\zeta^p-\int_{\mathcal{X}}\int_{\mathcal{X}}\|x-v\|_p^p\,\mathrm{d}\mathbb{P}^{\star}_{V\mid X}(v)\,\mathrm{d}\mathbb{P}_X(x)\right)=0 α ⋆ ( ζ p − ∫ X ∫ X ∥ x − v ∥ p p d P V ∣ X ⋆ ( v ) d P X ( x ) ) = 0 .
– Stationarity: P V ∣ X ⋆ \mathbb{P}^{\star}_{V\mid X} P V ∣ X ⋆ maximizes the Lagrangian at α ⋆ \alpha^\star α ⋆ .
Dual feasibility holds immediately by inspecting α ⋆ = d p ζ p \alpha^\star=\frac{d}{p\zeta^p} α ⋆ = p ζ p d . Similarly, stationarity holds by construction, since P V ∣ X ⋆ \mathbb{P}^{\star}_{V\mid X} P V ∣ X ⋆ maximizes the Lagrangian for α ⋆ \alpha^\star α ⋆ via Donsker-Varadhan/Gibbs result. Since α ⋆ > 0 \alpha^\star>0 α ⋆ > 0 , it suffices to show ∫ X ∫ X ∥ x − v ∥ p p d P V ∣ X ⋆ ( v ) d P X ( x ) = ζ p \int_{\mathcal{X}}\int_{\mathcal{X}}\|x-v\|_p^p\,\mathrm{d}\mathbb{P}^{\star}_{V\mid X}(v)\,\mathrm{d}\mathbb{P}_X(x)=\zeta^p ∫ X ∫ X ∥ x − v ∥ p p d P V ∣ X ⋆ ( v ) d P X ( x ) = ζ p for the primal feasibility and complementary slackness,
= ∫ X ∫ X ∥ x − v ∥ p p exp ( − α ⋆ ∥ x − v ∥ p p ) ∫ X exp ( − α ⋆ ∥ x − v ∥ p p ) d v d v d P X ( x ) = ∫ X vol ( B p d ) ∫ 0 ∞ r p r d − 1 exp ( − α ⋆ r p ) d r vol ( B p d ) ∫ 0 ∞ r d − 1 exp ( − α ⋆ r p ) d r d P X ( x ) = ∫ X ∫ 0 ∞ r p + d − 1 exp ( − α ⋆ r p ) d r ∫ 0 ∞ r d − 1 exp ( − α ⋆ r p ) d r d P X ( x ) = ∫ X ∫ 0 ∞ r p + d − 1 exp ( − α ⋆ r p ) d r ∫ 0 ∞ r d − 1 exp ( − α ⋆ r p ) d r d P X ( x ) = ∫ X Γ ( 1 + d / p ) p α ⋆ 1 + d / p Γ ( d / p ) p α ⋆ d / p d P X ( x ) = ∫ X Γ ( 1 + d / p ) Γ ( d / p ) α ⋆ d P X ( x ) = ∫ X d / p Γ ( d / p ) Γ ( d / p ) α ⋆ d P X ( x ) = d p α ⋆ = ζ p \begin{aligned}
=\int_{\mathcal{X}}\int_{\mathcal{X}}\frac{\|x-v\|_p^p\exp\left(-\alpha^\star\|x-v\|_p^p\right)}{\int_{\mathcal{X}}\exp\left(-\alpha^\star\|x-v\|_p^p\right)\,\mathrm{d}v}\,\mathrm{d}v\,\mathrm{d}\mathbb{P}_X(x) \\
&=\int_{\mathcal{X}}\frac{\operatorname{vol}(B_p^d)\int_0^\infty r^p r^{d-1}\exp\left(-\alpha^\star r^p\right)\,\mathrm{d}r}{\operatorname{vol}(B_p^d)\int_0^\infty r^{d-1}\exp\left(-\alpha^\star r^p\right)\,\mathrm{d}r}\,\mathrm{d}\mathbb{P}_X(x) \\
&=\int_{\mathcal{X}}\frac{\int_0^\infty r^{p+d-1}\exp\left(-\alpha^\star r^p\right)\,\mathrm{d}r}{\int_0^\infty r^{d-1}\exp\left(-\alpha^\star r^p\right)\,\mathrm{d}r}\,\mathrm{d}\mathbb{P}_X(x) \\
&=\int_{\mathcal{X}}\frac{\int_0^\infty r^{p+d-1}\exp\left(-\alpha^\star r^p\right)\,\mathrm{d}r}{\int_0^\infty r^{d-1}\exp\left(-\alpha^\star r^p\right)\,\mathrm{d}r}\,\mathrm{d}\mathbb{P}_X(x) \\
&=\int_{\mathcal{X}}\frac{\dfrac{\Gamma(1+d/p)}{p\alpha^{\star\,1+d/p}}}{\dfrac{\Gamma(d/p)}{p\alpha^{\star\,d/p}}}\,\mathrm{d}\mathbb{P}_X(x) \\
&=\int_{\mathcal{X}}\frac{\Gamma(1+d/p)}{\Gamma(d/p)\alpha^\star}\,\mathrm{d}\mathbb{P}_X(x) \\
&=\int_{\mathcal{X}}\frac{d/p\Gamma(d/p)}{\Gamma(d/p)\alpha^\star}\,\mathrm{d}\mathbb{P}_X(x) \\
&=\frac{d}{p\alpha^\star} \\
&=\zeta^p
\end{aligned} = ∫ X ∫ X ∫ X exp ( − α ⋆ ∥ x − v ∥ p p ) d v ∥ x − v ∥ p p exp ( − α ⋆ ∥ x − v ∥ p p ) d v d P X ( x ) = ∫ X vol ( B p d ) ∫ 0 ∞ r d − 1 exp ( − α ⋆ r p ) d r vol ( B p d ) ∫ 0 ∞ r p r d − 1 exp ( − α ⋆ r p ) d r d P X ( x ) = ∫ X ∫ 0 ∞ r d − 1 exp ( − α ⋆ r p ) d r ∫ 0 ∞ r p + d − 1 exp ( − α ⋆ r p ) d r d P X ( x ) = ∫ X ∫ 0 ∞ r d − 1 exp ( − α ⋆ r p ) d r ∫ 0 ∞ r p + d − 1 exp ( − α ⋆ r p ) d r d P X ( x ) = ∫ X p α ⋆ d / p Γ ( d / p ) p α ⋆ 1 + d / p Γ ( 1 + d / p ) d P X ( x ) = ∫ X Γ ( d / p ) α ⋆ Γ ( 1 + d / p ) d P X ( x ) = ∫ X Γ ( d / p ) α ⋆ d / p Γ ( d / p ) d P X ( x ) = p α ⋆ d = ζ p
where we used the property of the Gamma function, Γ ( 1 + z ) = z Γ ( z ) \Gamma(1+z)=z\Gamma(z) Γ ( 1 + z ) = z Γ ( z ) .
Consequently, strong duality holds, leading to,
d p + log ( d p vol ( B p d ) Γ ( d p ) ( p d ) d / p ζ d ) = sup P V ∣ X ∈ P h P X , V ( V ∣ X ) \frac{d}{p}+\log\left(\frac{d}{p}\operatorname{vol}(B_p^d)\Gamma\left(\frac{d}{p}\right)\left(\frac{p}{d}\right)^{d/p}\zeta^d\right)=\sup_{\mathbb{P}_{V\mid X}\in\mathcal{P}} h_{\mathbb{P}_{X,V}}(V\mid X) p d + log ( p d vol ( B p d ) Γ ( p d ) ( d p ) d / p ζ d ) = P V ∣ X ∈ P sup h P X , V ( V ∣ X )
s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p , \text{s.t.}\qquad\mathbb{E}_X\mathbb{E}_{V\mid X}\left[\lVert x-v\rVert_p^p\right]\leq\zeta^p, s.t. E X E V ∣ X [ ∥ x − v ∥ p p ] ≤ ζ p ,
which concludes the proof.
Proof of Corollary 3.1
Proof. Setting p = 2 p=2 p = 2 in Proposition 3.1 gives us,
d 2 + log ( 2 π d ζ ) d , \frac{d}{2}+\log\left(\sqrt{\frac{2\pi}{d}}\zeta\right)^d, 2 d + log ( d 2 π ζ ) d ,
for the optimal solution and
P V ∣ X ⋆ ( C ) = 1 ( 2 π d ζ ) d ∫ C exp ( − d 2 ζ 2 ∥ x − v ∥ 2 2 ) d v , \mathbb{P}^{\star}_{V\mid X}(C)=\frac{1}{\left(\sqrt{\frac{2\pi}{d}}\zeta\right)^d}\int_C\exp\left(-\frac{d}{2\zeta^2}\lVert x-v\rVert_2^2\right)\,dv, P V ∣ X ⋆ ( C ) = ( d 2 π ζ ) d 1 ∫ C exp ( − 2 ζ 2 d ∥ x − v ∥ 2 2 ) d v ,
for the optimal argument. Since x x x is given and both x , v ∈ R d x,v\in\mathbb{R}^d x , v ∈ R d , we can write the above as,
1 ( 2 π ) d det ( ζ 2 d I d ) ∫ C exp ( − 1 2 ( v − x ) T ( ζ 2 d I d ) − 1 ( v − x ) ) d v , \frac{1}{\sqrt{(2\pi)^d\det\left(\frac{\zeta^2}{d}I_d\right)}}\int_C\exp\left(-\frac{1}{2}(v-x)^{\mathsf{T}}\left(\frac{\zeta^2}{d}I_d\right)^{-1}(v-x)\right)\,dv, ( 2 π ) d det ( d ζ 2 I d ) 1 ∫ C exp ( − 2 1 ( v − x ) T ( d ζ 2 I d ) − 1 ( v − x ) ) d v ,
which is a Gaussian kernel, N ( x , ζ 2 d I d ) \mathcal{N}\left(x,\frac{\zeta^2}{d}I_d\right) N ( x , d ζ 2 I d ) .
Proof of Corollary 3.2
Proof. Setting p = 1 p=1 p = 1 in Proposition 3.1 gives us,
d + log ( 2 ζ d ) d , d+\log\left(\frac{2\zeta}{d}\right)^d, d + log ( d 2 ζ ) d ,
for the optimal solution and
P V ∣ X ⋆ ( C ) = ( d 2 ζ ) d ∫ C exp ( − d ζ ∥ x − v ∥ 1 ) d v . \mathbb{P}^{\star}_{V\mid X}(C)=\left(\frac{d}{2\zeta}\right)^d\int_C\exp\left(-\frac{d}{\zeta}\lVert x-v\rVert_1\right)\,dv. P V ∣ X ⋆ ( C ) = ( 2 ζ d ) d ∫ C exp ( − ζ d ∥ x − v ∥ 1 ) d v .
for the optimal argument, which is equivalent to writing,
P V ∣ X ⋆ ( C ) = ( d 2 ζ ) d ∫ C exp ( − d ζ ∑ i = 1 d ∥ x i − v i ∥ 1 ) d v 1 … d v d = ( d 2 ζ ) d ∫ C ∏ i = 1 d exp ( − d ζ ∥ x i − v i ∥ 1 ) d v 1 … d v d , = ∫ C ∏ i = 1 d d 2 ζ exp ( − d ζ ∥ x i − v i ∥ 1 ) d v 1 … d v d . \begin{aligned}
\mathbb{P}^{\star}_{V\mid X}(C)=\left(\frac{d}{2\zeta}\right)^d\int_C\exp\left(-\frac{d}{\zeta}\sum_{i=1}^{d}\lVert x_i-v_i\rVert_1\right)\,dv_1\ldots dv_d \\
&=\left(\frac{d}{2\zeta}\right)^d\int_C\prod_{i=1}^{d}\exp\left(-\frac{d}{\zeta}\lVert x_i-v_i\rVert_1\right)\,dv_1\ldots dv_d, \\
&=\int_C\prod_{i=1}^{d}\frac{d}{2\zeta}\exp\left(-\frac{d}{\zeta}\lVert x_i-v_i\rVert_1\right)\,dv_1\ldots dv_d.
\end{aligned} P V ∣ X ⋆ ( C ) = ( 2 ζ d ) d ∫ C exp ( − ζ d i = 1 ∑ d ∥ x i − v i ∥ 1 ) d v 1 … d v d = ( 2 ζ d ) d ∫ C i = 1 ∏ d exp ( − ζ d ∥ x i − v i ∥ 1 ) d v 1 … d v d , = ∫ C i = 1 ∏ d 2 ζ d exp ( − ζ d ∥ x i − v i ∥ 1 ) d v 1 … d v d .
Since the above holds for every Borel set C ⊆ R d C\subseteq\mathbb{R}^d C ⊆ R d , the optimal conditional law P V ∣ X ⋆ \mathbb{P}^{\star}_{V\mid X} P V ∣ X ⋆ is absolutely continuous w.r.t. Lebesgue measure with density
p ⋆ ( v ∣ x ) = ∏ i = 1 d d 2 ζ exp ( − d ζ ∥ x i − v i ∥ 1 ) . p^{\star}(v\mid x)=\prod_{i=1}^{d}\frac{d}{2\zeta}\exp\left(-\frac{d}{\zeta}\lVert x_i-v_i\rVert_1\right). p ⋆ ( v ∣ x ) = i = 1 ∏ d 2 ζ d exp ( − ζ d ∥ x i − v i ∥ 1 ) .
This is the joint density of independent coordinates v i ∣ x ∼ i . i . d . Laplace ( x i , ζ / d ) v_i\mid x\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\operatorname{Laplace}(x_i,\zeta/d) v i ∣ x ∼ i.i.d. Laplace ( x i , ζ / d ) , i.e. V ∣ x ∼ Laplace d ( x , ζ / d ) V\mid x\sim\operatorname{Laplace}_d(x,\zeta/d) V ∣ x ∼ Laplace d ( x , ζ / d ) .
Proof of Corollary 3.3
Proof. The constraint restricts the support of P V ∣ X = x \mathbb{P}_{V\mid X=x} P V ∣ X = x to
D ζ ( x ) : = x + [ − ζ , ζ ] d , D_\zeta(x):=x+[-\zeta,\zeta]^d, D ζ ( x ) := x + [ − ζ , ζ ] d ,
Among all probability measures supported on a measurable set, the uniform distribution uniquely maximizes differential entropy. Hence
P V ∣ X = x ⋆ = Unif ( D ζ ( x ) ) , \mathbb{P}^{\star}_{V\mid X=x}=\operatorname{Unif}(D_\zeta(x)), P V ∣ X = x ⋆ = Unif ( D ζ ( x )) ,
with optimal value
h X , V ⋆ ( V ∣ X = x ) = log ∣ D ζ ( x ) ∣ . h^{\star}_{X,V}(V\mid X=x)=\log\lvert D_\zeta(x)\rvert. h X , V ⋆ ( V ∣ X = x ) = log ∣ D ζ ( x )∣ .
If x ∈ [ ζ , 1 − ζ ] d x\in[\zeta,1-\zeta]^d x ∈ [ ζ , 1 − ζ ] d , then
D ζ ( x ) = x + [ − ζ , ζ ] d , D_\zeta(x)=x+[-\zeta,\zeta]^d, D ζ ( x ) = x + [ − ζ , ζ ] d ,
whose Lebesgue measure is ( 2 ζ ) d (2\zeta)^d ( 2 ζ ) d . Therefore
h X , V ⋆ ( V ∣ X = x ) = log ( 2 ζ ) d = d log ( 2 ζ ) . h^{\star}_{X,V}(V\mid X=x)=\log(2\zeta)^d=d\log(2\zeta). h X , V ⋆ ( V ∣ X = x ) = log ( 2 ζ ) d = d log ( 2 ζ ) .
Proof of W-MEP results
Prior to the proceeding with the proof we first show a simple statement which will be used in this and subsequent proofs,
Lemma A.3 Let ( X , A ) (\mathcal{X},\mathcal{A}) ( X , A ) be a measurable space and let f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R be measurable. Then
sup P ∈ P ( X ) ∫ X f ( v ) d P ( v ) = sup v ∈ X f ( v ) \sup_{\mathbb{P}\in\mathcal{P}(\mathcal{X})}\int_{\mathcal{X}}f(v)\,\mathrm{d}\mathbb{P}(v)=\sup_{v\in\mathcal{X}}f(v) P ∈ P ( X ) sup ∫ X f ( v ) d P ( v ) = v ∈ X sup f ( v ) provided that the integrals are well defined.
Proof. Let
M : = sup v ∈ X f ( v ) , M:=\sup_{v\in\mathcal{X}}f(v), M := v ∈ X sup f ( v ) , then, for every P ∈ P ( X ) \mathbb{P}\in\mathcal{P}(\mathcal{X}) P ∈ P ( X ) ,
∫ X f ( v ) d P ( v ) ≤ ∫ X M d P ( v ) . \int_{\mathcal{X}}f(v)\,\mathrm{d}\mathbb{P}(v)\leq\int_{\mathcal{X}}M\,\mathrm{d}\mathbb{P}(v). ∫ X f ( v ) d P ( v ) ≤ ∫ X M d P ( v ) . Now, since P \mathbb{P} P is a probability measure, then,
∫ X f ( v ) d P ( v ) ≤ M . \int_{\mathcal{X}}f(v)\,\mathrm{d}\mathbb{P}(v)\leq M. ∫ X f ( v ) d P ( v ) ≤ M . Conversely, for every v ∈ X v\in\mathcal{X} v ∈ X , the Dirac measure δ v \delta_v δ v belongs to P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) , and
∫ X f ( u ) δ v ( d u ) = f ( v ) . \int_{\mathcal{X}}f(u)\,\delta_v(\mathrm{d}u)=f(v). ∫ X f ( u ) δ v ( d u ) = f ( v ) . Therefore,
sup P ∈ P ( X ) ∫ X f ( u ) d P ( u ) ≥ f ( v ) for every v ∈ X . \sup_{\mathbb{P}\in\mathcal{P}(\mathcal{X})}\int_{\mathcal{X}}f(u)\,\mathrm{d}\mathbb{P}(u)\geq f(v)\qquad\text{for every }v\in\mathcal{X}. P ∈ P ( X ) sup ∫ X f ( u ) d P ( u ) ≥ f ( v ) for every v ∈ X . Taking the supremum over v ∈ X v\in\mathcal{X} v ∈ X yields
sup P ∈ P ( X ) ∫ X f ( u ) d P ( u ) ≥ sup v ∈ X f ( v ) . \sup_{\mathbb{P}\in\mathcal{P}(\mathcal{X})}\int_{\mathcal{X}}f(u)\,\mathrm{d}\mathbb{P}(u)\geq\sup_{v\in\mathcal{X}}f(v). P ∈ P ( X ) sup ∫ X f ( u ) d P ( u ) ≥ v ∈ X sup f ( v ) . Combining the two inequalities proves the result.
Proof of Proposition 3.2
Proof. From lemma A.1 solving Equation (2) is equivalent to solving,
sup P V ∣ X ∈ K p ( X ) E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] \sup_{\mathbb{P}_{V|X}\in\mathcal{K}_p(\mathcal{X})}\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}[-\log p(v)]-\operatorname{KL}(\mathbb{P}_{V|X}\Vert\mathbb{P}_{V})\right] P V ∣ X ∈ K p ( X ) sup E X [ E P V ∣ X [ − log p ( v )] − KL ( P V ∣ X ∥ P V ) ]
s.t. W p ( P X , P V ) ≤ ζ . \text{s.t.}\qquad W_p(\mathbb{P}_X,\mathbb{P}_V)\leq\zeta. s.t. W p ( P X , P V ) ≤ ζ .
Note that it is equivalent to (by the definition of the Wasserstein metric),
sup P V ∣ X ∈ K p ( X ) E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] \sup_{\mathbb{P}_{V|X}\in\mathcal{K}_p(\mathcal{X})}\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}[-\log p(v)]-\operatorname{KL}(\mathbb{P}_{V|X}\Vert\mathbb{P}_{V})\right] P V ∣ X ∈ K p ( X ) sup E X [ E P V ∣ X [ − log p ( v )] − KL ( P V ∣ X ∥ P V ) ]
s.t. inf π ∈ Π ( P V , P X ) ∫ X × X ∥ x − v ∥ p p d π ( x , v ) ≤ ζ p , \text{s.t.}\qquad\inf_{\pi\in\Pi(\mathbb{P}_V,\mathbb{P}_X)}\int_{\mathcal{X}\times\mathcal{X}}\|x-v\|_p^p\,\mathrm{d}\pi(x,v)\leq\zeta^p, s.t. π ∈ Π ( P V , P X ) inf ∫ X × X ∥ x − v ∥ p p d π ( x , v ) ≤ ζ p ,
written differently,
sup P V ∣ X ∈ K p ( X ) π ∈ Π ( P X , P V ) h P X , V ( V ∣ X ) \sup_{\substack{\mathbb{P}_{V|X}\in\mathcal{K}_p(\mathcal{X})\\ \pi\in\Pi(\mathbb{P}_X,\mathbb{P}_V)}} h_{\mathbb{P}_X,V}(V|X) P V ∣ X ∈ K p ( X ) π ∈ Π ( P X , P V ) sup h P X , V ( V ∣ X )
s.t. ∫ X × X ∥ x − v ∥ p p d π ( x , v ) ≤ ζ p . \text{s.t.}\qquad\int_{\mathcal{X}\times\mathcal{X}}\|x-v\|_p^p\,\mathrm{d}\pi(x,v)\leq\zeta^p. s.t. ∫ X × X ∥ x − v ∥ p p d π ( x , v ) ≤ ζ p .
Since ( X , B ( X ) ) (\mathcal{X},\mathcal{B}(\mathcal{X})) ( X , B ( X )) is a Borel space, every coupling π ∈ Π ( P X , P V ) \pi\in\Pi(\mathbb{P}_X,\mathbb{P}_V) π ∈ Π ( P X , P V ) admits a disintegration
d π ( x , v ) = d P X ( x ) d Q V ∣ X ( v ) , \mathrm{d}\pi(x,v)=\mathrm{d}\mathbb{P}_X(x)\,\mathrm{d}\mathbb{Q}_{V|X}(v), d π ( x , v ) = d P X ( x ) d Q V ∣ X ( v ) ,
where Q V ∣ X \mathbb{Q}_{V|X} Q V ∣ X is the transport kernel. In contrast to the average transport formulation, this kernel need not coincide with the conditional law P V ∣ X \mathbb{P}_{V|X} P V ∣ X appearing in the entropy objective. Indeed, the Wasserstein constraint depends only on the induced marginal distribution P V \mathbb{P}_V P V , whereas the entropy depends on P V ∣ X \mathbb{P}_{V|X} P V ∣ X . Consequently, the optimization naturally involves two kernels, P V ∣ X \mathbb{P}_{V|X} P V ∣ X and Q V ∣ X \mathbb{Q}_{V|X} Q V ∣ X , which are linked only through the consistency condition
∫ X P V ∣ X ( C ) d P X ( x ) = ∫ X Q V ∣ X ( C ) d P X ( x ) , ∀ C ∈ B ( X ) . \int_{\mathcal{X}}\mathbb{P}_{V|X}(C)\,\mathrm{d}\mathbb{P}_X(x)=\int_{\mathcal{X}}\mathbb{Q}_{V|X}(C)\,\mathrm{d}\mathbb{P}_X(x),\qquad\forall C\in\mathcal{B}(\mathcal{X}). ∫ X P V ∣ X ( C ) d P X ( x ) = ∫ X Q V ∣ X ( C ) d P X ( x ) , ∀ C ∈ B ( X ) .
Therefore, optimizing over couplings π ∈ Π ( P X , P V ) \pi\in\Pi(\mathbb{P}_{X},\mathbb{P}_{V}) π ∈ Π ( P X , P V ) is equivalent to optimizing over transport kernels Q V ∣ X \mathbb{Q}_{V|X} Q V ∣ X satisfying the marginal consistency condition. Hence, the problem can be reformulated over the pair P V ∣ X , Q V ∣ X \mathbb{P}_{V|X},\mathbb{Q}_{V|X} P V ∣ X , Q V ∣ X as,
sup P V ∣ X , Q V ∣ X ∈ K p ( X ) E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] \sup_{\mathbb{P}_{V|X},\mathbb{Q}_{V|X} \in\mathcal{K}_{p}(\mathcal{X})}
\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)\right] P V ∣ X , Q V ∣ X ∈ K p ( X ) sup E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ]
s.t. ∫ X ∫ X ∥ x − v ∥ p p d Q V ∣ X ( v ) d P X ( x ) ≤ ζ p ∫ X P V ∣ X ( C ) d P X ( x ) = ∫ X Q V ∣ X ( C ) d P X ( x ) , ∀ C ∈ B ( X ) . \begin{aligned}
\text{s.t.}\quad&\int_{\mathcal{X}}\int_{\mathcal{X}}\|x-v\|_{p}^{p}\,\mathrm{d}\mathbb{Q}_{V|X}(v)\,\mathrm{d}\mathbb{P}_{X}(x)\leq\zeta^{p}\\
&\int_{\mathcal{X}}\mathbb{P}_{V|X}(C)\,\mathrm{d}\mathbb{P}_{X}(x)=\int_{\mathcal{X}}\mathbb{Q}_{V|X}(C)\,\mathrm{d}\mathbb{P}_{X}(x),\quad\forall C\in\mathcal{B}(\mathcal{X}).
\end{aligned} s.t. ∫ X ∫ X ∥ x − v ∥ p p d Q V ∣ X ( v ) d P X ( x ) ≤ ζ p ∫ X P V ∣ X ( C ) d P X ( x ) = ∫ X Q V ∣ X ( C ) d P X ( x ) , ∀ C ∈ B ( X ) .
which is equivalent to the following (expressing the integrals as expectations),
sup P V ∣ X , Q V ∣ X ∈ K p ( X ) E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] \sup_{\mathbb{P}_{V|X},\mathbb{Q}_{V|X}\in\mathcal{K}_{p}(\mathcal{X})}
\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)\right] P V ∣ X , Q V ∣ X ∈ K p ( X ) sup E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ]
s.t. E X [ E Q V ∣ X [ ∥ x − v ∥ p p ] ] ≤ ζ p ∫ X P V ∣ X ( C ) d P X ( x ) = ∫ X Q V ∣ X ( C ) d P X ( x ) , ∀ C ∈ B ( X ) . (9) \begin{aligned}
\text{s.t.}\quad&\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{Q}_{V|X}}\left[\|x-v\|_{p}^{p}\right]\right]\leq\zeta^{p}\\
&\int_{\mathcal{X}}\mathbb{P}_{V|X}(C)\,\mathrm{d}\mathbb{P}_{X}(x)=\int_{\mathcal{X}}\mathbb{Q}_{V|X}(C)\,\mathrm{d}\mathbb{P}_{X}(x),\\
&\hspace{7em}\forall C\in\mathcal{B}(\mathcal{X}). \tag*{(9)}
\end{aligned} s.t. E X [ E Q V ∣ X [ ∥ x − v ∥ p p ] ] ≤ ζ p ∫ X P V ∣ X ( C ) d P X ( x ) = ∫ X Q V ∣ X ( C ) d P X ( x ) , ∀ C ∈ B ( X ) . (9)
The consistency constraint is an equality between probability measures rather than a scalar constraint. Following the standard convex-analytic duality for optimization over measures (see, e.g., [22 , 27 ] ), its Lagrange multiplier is therefore a measurable potential φ : X → R \varphi:\mathcal{X}\to\mathbb{R} φ : X → R , which acts on measures through the inner product
⟨ φ , μ ⟩ = ∫ X φ ( v ) d μ ( v ) . \langle\varphi,\mu\rangle=\int_{\mathcal{X}}\varphi(v)\,\mathrm{d}\mu(v). ⟨ φ , μ ⟩ = ∫ X φ ( v ) d μ ( v ) .
Introducing the multiplier α ≥ 0 \alpha\geq0 α ≥ 0 for the transport budget and the potential φ \varphi φ for the marginal consistency constraint yields the dual Lagrangian problem,
sup P V ∣ X , Q V ∣ X ∈ K p ( X ) min α ≥ 0 , φ { E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] − α E X [ E Q V ∣ X [ ∥ x − v ∥ p p ] ] + α ζ p − E X [ E P V ∣ X [ φ ( v ) ] ] + E X [ E Q V ∣ X [ φ ( v ) ] ] } . \sup_{\mathbb{P}_{V|X},\mathbb{Q}_{V|X}\in\mathcal{K}_{p}(\mathcal{X})}\ \min_{\alpha\geq0,\varphi}
\left\{
\begin{aligned}
&\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)\right]\\
&\quad-\alpha\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{Q}_{V|X}}\left[\|x-v\|_{p}^{p}\right]\right]+\alpha\zeta^{p}\\
&\quad-\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[\varphi(v)\right]\right]+\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{Q}_{V|X}}\left[\varphi(v)\right]\right]
\end{aligned}
\right\}. P V ∣ X , Q V ∣ X ∈ K p ( X ) sup α ≥ 0 , φ min ⎩ ⎨ ⎧ E X [ E P V ∣ X [ − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] − α E X [ E Q V ∣ X [ ∥ x − v ∥ p p ] ] + α ζ p − E X [ E P V ∣ X [ φ ( v ) ] ] + E X [ E Q V ∣ X [ φ ( v ) ] ] ⎭ ⎬ ⎫ .
and grouping the terms,
sup P V ∣ X , Q V ∣ X ∈ K p ( X ) inf α ≥ 0 , φ { E X [ E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] + E X [ E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] + α ζ p } . (10) \sup_{\substack{\mathbb{P}_{V|X},\mathbb{Q}_{V|X}\\ \in\mathcal{K}_{p}(\mathcal{X})}}
\inf_{\alpha\geq0,\varphi}
\left\{
\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\varphi(v)-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)\right]
+\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{Q}_{V|X}}\left[\varphi(v)-\alpha\|x-v\|_{p}^{p}\right]\right]+\alpha\zeta^{p}
\right\}. \tag*{(10)} P V ∣ X , Q V ∣ X ∈ K p ( X ) sup α ≥ 0 , φ inf { E X [ E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] + E X [ E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] + α ζ p } . (10)
At this point, all we can say is that weak duality holds, that is, (10) is less or equal to (11) ,
inf α ≥ 0 , φ sup P V ∣ X , Q V ∣ X ∈ K p ( X ) { E X [ E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] + E X [ E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] + α ζ p } . (11) \inf_{\alpha\geq0,\varphi}\ \sup_{\substack{\mathbb{P}_{V|X},\mathbb{Q}_{V|X}\\ \in\mathcal{K}_{p}(\mathcal{X})}}
\left\{
\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\varphi(v)-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)\right]
+\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{Q}_{V|X}}\left[\varphi(v)-\alpha\|x-v\|_{p}^{p}\right]\right]+\alpha\zeta^{p}
\right\}. \tag*{(11)} α ≥ 0 , φ inf P V ∣ X , Q V ∣ X ∈ K p ( X ) sup { E X [ E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] + E X [ E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] + α ζ p } . (11)
The objective is separable in P V ∣ X \mathbb{P}_{V|X} P V ∣ X and Q V ∣ X \mathbb{Q}_{V|X} Q V ∣ X , that is, we can optimize over each argument separately.
Entropy Kernel, P V ∣ X \mathbb{P}_{V|X} P V ∣ X
sup P V ∣ X ∈ K p ( X ) E X [ E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] . \sup_{\mathbb{P}_{V|X}\in\mathcal{K}_{p}(\mathcal{X})}
\mathbb{E}_{X}\left[\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\varphi(v)-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)\right]. P V ∣ X ∈ K p ( X ) sup E X [ E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] .
Note that, as P X \mathbb{P}_{X} P X is independent of P V ∣ X \mathbb{P}_{V|X} P V ∣ X , we can look at the expected value of the sup,
E X [ sup P V ∣ X ∈ K p ( X ) E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] . \mathbb{E}_{X}\left[
\sup_{\mathbb{P}_{V|X}\in\mathcal{K}_{p}(\mathcal{X})}
\mathbb{E}_{\mathbb{P}_{V|X}}\left[-\varphi(v)-\log p(v)\right]-\operatorname{KL}\left(\mathbb{P}_{V|X}\|\mathbb{P}_{V}\right)
\right]. E X [ P V ∣ X ∈ K p ( X ) sup E P V ∣ X [ − φ ( v ) − log p ( v ) ] − KL ( P V ∣ X ∥ P V ) ] .
Now take X = R d \mathcal{X}=\mathbb{R}^{d} X = R d and consider,
E V [ exp ( − φ ( v ) − log p ( v ) ) ] = ∫ X exp ( − φ ( v ) ) p ( v ) d P V = ∫ X exp ( − φ ( v ) ) p ( v ) p ( v ) d v = ∫ X exp ( − φ ( v ) ) d v \begin{aligned}
\mathbb{E}_{V}\left[\exp\left(-\varphi(v)-\log p(v)\right)\right]
&=\int_{\mathcal{X}}\frac{\exp\left(-\varphi(v)\right)}{p(v)}\,\mathrm{d}\mathbb{P}_{V}\\
&=\int_{\mathcal{X}}\frac{\exp\left(-\varphi(v)\right)}{p(v)}p(v)\,\mathrm{d}v\\
&=\int_{\mathcal{X}}\exp\left(-\varphi(v)\right)\,\mathrm{d}v
\end{aligned} E V [ exp ( − φ ( v ) − log p ( v ) ) ] = ∫ X p ( v ) exp ( − φ ( v ) ) d P V = ∫ X p ( v ) exp ( − φ ( v ) ) p ( v ) d v = ∫ X exp ( − φ ( v ) ) d v
By the Donsker–Varadhan/Gibbs variational principle, lemma A.2, the supremum over P V ∣ X P_{V\mid X} P V ∣ X is attained at a kernel satisfying, for P X P_X P X -a.e. x x x ,
d P V ∣ X ( ⋅ ∣ x ) d P V ( v ) = exp ( − φ ( v ) − log p ( v ) ) E P V [ exp ( − φ ( V ) − log p ( V ) ) ] . \frac{\mathrm{d}P_{V\mid X}(\cdot\mid x)}{\mathrm{d}P_V}(v)=\frac{\exp\left(-\varphi(v)-\log p(v)\right)}{\mathbb{E}_{P_V}\left[\exp\left(-\varphi(V)-\log p(V)\right)\right]}. d P V d P V ∣ X ( ⋅ ∣ x ) ( v ) = E P V [ exp ( − φ ( V ) − log p ( V ) ) ] exp ( − φ ( v ) − log p ( v ) ) .
Since d P V ( v ) = p ( v ) d v \mathrm{d}P_V(v)=p(v)\,\mathrm{d}v d P V ( v ) = p ( v ) d v , the denominator becomes
E V [ exp ( − φ ( V ) − log p ( V ) ) ] = ∫ X exp ( − φ ( v ) ) d v . \mathbb{E}_V\left[\exp\left(-\varphi(V)-\log p(V)\right)\right]=\int_{\mathcal{X}}\exp\left(-\varphi(v)\right)\,\mathrm{d}v. E V [ exp ( − φ ( V ) − log p ( V ) ) ] = ∫ X exp ( − φ ( v ) ) d v .
Therefore,
d P V ∣ X ( v ) d v = exp ( − φ ( v ) ) ∫ X exp ( − φ ( u ) ) d u , P X -a.s. \frac{\mathrm{d}P_{V\mid X}(v)}{\mathrm{d}v}=\frac{\exp\left(-\varphi(v)\right)}{\int_{\mathcal{X}}\exp\left(-\varphi(u)\right)\,\mathrm{d}u},\qquad P_X\text{-a.s.} d v d P V ∣ X ( v ) = ∫ X exp ( − φ ( u ) ) d u exp ( − φ ( v ) ) , P X -a.s.
In particular, the entropy-maximizing kernel is independent of x x x . Hence the induced marginal satisfies
p V ⋆ ( v ) = exp ( − φ ⋆ ( v ) ) ∫ X exp ( − φ ⋆ ( u ) ) d u . p_V^\star(v)=\frac{\exp\left(-\varphi^\star(v)\right)}{\int_{\mathcal{X}}\exp\left(-\varphi^\star(u)\right)\,\mathrm{d}u}. p V ⋆ ( v ) = ∫ X exp ( − φ ⋆ ( u ) ) d u exp ( − φ ⋆ ( v ) ) .
Consequently,
P V ∣ X ⋆ ( ⋅ ) = P V ⋆ ( ⋅ ) , P X -a.s. , P_{V\mid X}^\star(\cdot)=P_V^\star(\cdot),\qquad P_X\text{-a.s.}, P V ∣ X ⋆ ( ⋅ ) = P V ⋆ ( ⋅ ) , P X -a.s. ,
and the conditional entropy equals the marginal entropy at the optimum.
Transport Kernel, Q V ∣ X Q_{V\mid X} Q V ∣ X
sup Q V ∣ X ∈ K p ( X ) E X [ E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] . \sup_{Q_{V\mid X}\in\mathcal{K}_p(\mathcal{X})}\mathbb{E}_X\left[\mathbb{E}_{Q_{V\mid X}}\left[\varphi(v)-\alpha\lVert x-v\rVert_p^p\right]\right]. Q V ∣ X ∈ K p ( X ) sup E X [ E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] .
Similarly, we can look at,
E X [ sup Q V ∣ X ∈ K p ( X ) E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] , \mathbb{E}_X\left[\sup_{Q_{V\mid X}\in\mathcal{K}_p(\mathcal{X})}\mathbb{E}_{Q_{V\mid X}}\left[\varphi(v)-\alpha\lVert x-v\rVert_p^p\right]\right], E X [ Q V ∣ X ∈ K p ( X ) sup E Q V ∣ X [ φ ( v ) − α ∥ x − v ∥ p p ] ] ,
and from lemma A.3, this is equivalent to,
E X [ sup v ∈ X φ ( v ) − α ∥ x − v ∥ p p ] , \mathbb{E}_X\left[\sup_{v\in\mathcal{X}}\varphi(v)-\alpha\lVert x-v\rVert_p^p\right], E X [ v ∈ X sup φ ( v ) − α ∥ x − v ∥ p p ] ,
which is,
E X [ − φ c α ( x ) ] , \mathbb{E}_X\left[-\varphi^{c_\alpha}(x)\right], E X [ − φ c α ( x ) ] ,
since, the c c c -transform [22 , 27 ] for c α ( x , v ) = α ∥ x − v ∥ p p c_\alpha(x,v)=\alpha\lVert x-v\rVert_p^p c α ( x , v ) = α ∥ x − v ∥ p p is defined as,
φ c α ( x ) = inf v ∈ X α ∥ x − v ∥ p p − φ ( v ) . \varphi^{c_\alpha}(x)=\inf_{v\in\mathcal{X}}\alpha\lVert x-v\rVert_p^p-\varphi(v). φ c α ( x ) = v ∈ X inf α ∥ x − v ∥ p p − φ ( v ) .
Combining these results into Equation (11) , results in,
inf α ≥ 0 , φ log ∫ X exp ( − φ ( v ) ) d v − E X [ φ c α ( x ) ] + α ζ p . \inf_{\alpha\geq0,\ \varphi}\log\int_{\mathcal{X}}\exp\left(-\varphi(v)\right)\,\mathrm{d}v-\mathbb{E}_X\left[\varphi^{c_\alpha}(x)\right]+\alpha\zeta^p. α ≥ 0 , φ inf log ∫ X exp ( − φ ( v ) ) d v − E X [ φ c α ( x ) ] + α ζ p .
Since the problem is convex, to guarantee strong duality it suffices to verify Slater’s condition, i.e., the existence of a strictly feasible point (an interior point in the relative sense) satisfying the inequality constraints with strict inequality. Under Slater’s condition, the KKT conditions are necessary and sufficient for optimality [1 ] , strong duality holds and optimal Lagrange multipliers exist. Consequently, the KKT conditions are necessary and sufficient for optimality and verifying KKT for the primal-dual optimal, ( α ⋆ , φ ⋆ ) (\alpha^\star,\varphi^\star) ( α ⋆ , φ ⋆ ) , certifies primal optimality and a zero duality gap [1 ] .
Proof of Corollary 3.4
Proof. The result follows directly from Proposition 3.2. For p = 1 p=1 p = 1 , let φ \varphi φ be α \alpha α -Lipschitz. Then
φ ( v ) − φ ( x ) ≤ α ∥ v − x ∥ 1 , \varphi(v)-\varphi(x)\leq\alpha\lVert v-x\rVert_1, φ ( v ) − φ ( x ) ≤ α ∥ v − x ∥ 1 ,
and hence
α ∥ x − v ∥ 1 − φ ( v ) ≥ − φ ( x ) . \alpha\lVert x-v\rVert_1-\varphi(v)\geq-\varphi(x). α ∥ x − v ∥ 1 − φ ( v ) ≥ − φ ( x ) .
Since equality is attained at v = x v=x v = x , the c α c_\alpha c α -transform satisfies
φ c α ( x ) = inf v α ∥ x − v ∥ 1 − φ ( v ) = − φ ( x ) . \varphi^{c_\alpha}(x)=\inf_{v}\alpha\lVert x-v\rVert_1-\varphi(v)=-\varphi(x). φ c α ( x ) = v inf α ∥ x − v ∥ 1 − φ ( v ) = − φ ( x ) .
Substituting into the dual formulation of Proposition 3.2 gives
inf α ≥ 0 , φ ∈ Lip α log ∫ R d exp ( − φ ( v ) ) d v + E X [ φ ( X ) ] + α ζ . \inf_{\substack{\alpha\geq0,\\ \varphi\in\operatorname{Lip}_\alpha}}\log\int_{\mathbb{R}^d}\exp\left(-\varphi(v)\right)\,\mathrm{d}v+\mathbb{E}_X[\varphi(X)]+\alpha\zeta. α ≥ 0 , φ ∈ Lip α inf log ∫ R d exp ( − φ ( v ) ) d v + E X [ φ ( X )] + α ζ .
For a fixed Lipschitz potential φ \varphi φ , the smallest admissible α \alpha α is Lip ( φ ) \operatorname{Lip}(\varphi) Lip ( φ ) , which yields the stated formulation. The expression for the optimal marginal and the independence of the optimal conditional kernel from X X X follow directly from Proposition 3.2.