Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral

1. Problem Statement

The paper addresses the problem of establishing two-sided bounds (both upper and lower) for Entropic Optimal Transport (EOT) and Information-Constrained Optimal Transport.

Specifically, the author investigates the maximum expected inner product between a standard Gaussian vector $Y \sim \mathcal{N}(0, I_n)$ and a random vector $Z$ distributed according to an arbitrary measure $\mu$ (with finite second moments), subject to a constraint on their mutual information $I(Y; Z) \le R$. This quantity is denoted as:
$$w(\gamma, \mu, R) := \sup_{P_{YZ} \in \Pi(\gamma, \mu): I(Y; Z) \le R} \mathbb{E}[\langle Y, Z \rangle]$$
where $\Pi(\gamma, \mu)$ is the set of couplings between $\gamma$ and $\mu$.

The paper also considers the regularized version (entropic regularization), defined via the Legendre-Fenchel transform:
$$f(\gamma, \mu, \beta) := \sup_{R > 0} \{ w(\gamma, \mu, R) - \beta R \}$$

The Core Challenge:
Previous work (specifically [1]) established a "rate-distortion integral" formula for the unconstrained case ($R = \infty$), showing equivalence to an integral involving the rate-distortion function $R_\mu(\sigma^2)$. However, extending this to the constrained/regularized case was an open problem. The challenge lies in proving that a similar integral representation holds with two-sided bounds (equivalence up to universal constants) when mutual information is limited, rather than just providing an upper bound.

2. Methodology

The proof relies on a sophisticated lifting technique combined with the Method of Types and Majorizing Measure Theory.

A. Lifting to a Random Subset of the Type Class

Instead of working directly with continuous measures, the author lifts the problem to a high-dimensional discrete space using the Method of Types:

1. Discretization: The continuous measures $\gamma$ and $\mu$ are approximated by rational distributions (distributions where probabilities are rational numbers).
2. Type Classes: Sequences of length $N$ are considered. The "type class" $C_\mu$ consists of all sequences with empirical distribution $\mu$.
3. Random Subset Construction: A random subset $A \subset C_\mu$ is constructed by selecting $L = \lfloor \exp(NR) \rfloor$ sequences uniformly at random. This size $L$ corresponds to the mutual information constraint $R$.
4. Lifting Lemma: The paper proves that the constrained transport value $w(\gamma, \mu, R)$ is asymptotically equivalent to the expected maximum inner product between a uniform sequence from the type class of $\gamma$ and the random subset $A$:
   $$w(\gamma, \mu, R) \approx \mathbb{E}\left[ \max_{z^N \in A} \frac{1}{N} \langle Y^N, z^N \rangle \right]$$

B. Controlling Mutual Information via Randomization

A critical refinement over previous lifting arguments (which used the full type class) is the use of a random subset.

• The full type class is permutation-invariant (stationary), which makes applying Talagrand's Majorizing Measure Theorem straightforward but does not naturally enforce a mutual information constraint.
• By selecting a random subset of size $\exp(NR)$, the author effectively imposes the mutual information constraint.
• Although the random subset breaks strict permutation invariance, the paper argues that the resulting process is "close to stationary" due to sharp double-exponential concentration. The number of selected points in any local ball is approximately the same, allowing the application of majorizing measure bounds.

C. Application of Majorizing Measure Theorem

The problem is reduced to bounding the supremum of a Gaussian process indexed by the set $A$.

• The author utilizes Talagrand's Majorizing Measure Theorem, which relates the expected supremum of a Gaussian process to a geometric functional (the $\gamma_2$ or $\delta_2$ functional) involving the metric entropy of the index set.
• The metric on the index set is derived from the rate-distortion function. Specifically, the probability mass of a ball in the type class relates to the rate-distortion function $i_\mu(\sigma)$.
• By analyzing the concentration of the random subset, the author derives that the geometric functional is equivalent to a truncated integral of the rate-distortion function.

D. Regularization via Convex Duality

For the regularized case (Theorem 2), the paper uses a variational argument (Lemma 4) to convert the integral bound on $w(\gamma, \mu, R)$ into a bound on $f(\gamma, \mu, \beta)$. This involves optimizing over $R$ and utilizing the convex conjugate relationship between the constraint $R$ and the regularization parameter $\beta$.

3. Key Contributions

1. Two-Sided Bounds for Constrained EOT:
   The paper establishes that the information-constrained optimal transport cost is equivalent (up to universal constants) to a truncated rate-distortion integral:
   $$w(\gamma, \mu, R) \asymp \int_0^\infty \sqrt{R \wedge i_\mu(\sigma)} \, d\sigma$$
   where $i_\mu(\sigma)$ is a variant of the rate-distortion function. This is a significant improvement over previous one-sided bounds.

2. Regularized Bound with Exact Tensorization:
   The paper provides a clean integral bound for the entropic regularized transport:
   $$f(\gamma, \mu, \beta) \asymp \int_\beta^\infty \phi(\mu, \alpha) \, d\alpha$$
   where $\phi(\mu, \alpha) = \inf_{\sigma > 0} \{ i_\mu(\sigma^2) + \sigma^2/\alpha^2 \}$.
   Crucially, this formulation satisfies exact tensorization (additivity under product measures), meaning $f(\gamma_1 \times \gamma_2, \mu_1 \times \mu_2, \beta) = f(\gamma_1, \mu_1, \beta) + f(\gamma_2, \mu_2, \beta)$. This property is essential for high-dimensional applications.

3. Refined Lifting Technique:
   The author introduces a novel refinement to the lifting method by using a randomly selected subset of the type class rather than the full class. This allows the method to handle mutual information constraints directly while maintaining the geometric properties necessary for majorizing measure bounds.

4. Simplification of Majorizing Measure Proofs:
   The results suggest a potential pathway to proving Talagrand's Majorizing Measure Theorem via a purely analytic "incremental form" of the rate-distortion integral, potentially offering a simpler alternative to existing probabilistic proofs.

4. Main Results

• Theorem 1 (Constrained Case): For standard Gaussian $\gamma$ and arbitrary $\mu$, the constrained transport cost $w(\gamma, \mu, R)$ is bounded above and below by constants times the integral of $\sqrt{R \wedge i_\mu(\sigma)}$.
• Theorem 2 (Regularized Case): The regularized transport cost $f(\gamma, \mu, \beta)$ is bounded by constants times the integral of $\phi(\mu, \alpha)$ from $\beta$ to $\infty$.
• Tensorization Property: The regularized bound is additive for product measures, a property not immediately obvious from the constrained formulation but derived naturally here.
• Verification: The bounds are verified for Gaussian $\mu$ (where they converge to known constants or specific orders like $1/\beta$), confirming the tightness of the results.

5. Significance and Implications

• Theoretical Unification: The work unifies Optimal Transport, Information Theory (Rate-Distortion), and Stochastic Processes (Majorizing Measure Theorem). It shows that the "rate-distortion integral" is a fundamental object governing optimal transport under information constraints.
• Algorithmic Implications: Entropic regularization is the backbone of the Sinkhorn algorithm, widely used in machine learning for generative models and distribution matching. Understanding the precise behavior of the regularized cost (via the integral bounds) can lead to better convergence rate analyses and algorithm design.
• Statistical Applications: The paper notes that these sharper bounds have consequences for statistical regression rates and sub-Gaussian comparison theorems, potentially improving the theoretical guarantees of high-dimensional statistical estimators.
• New Proof Paradigm: By deriving the Majorizing Measure Theorem (or equivalent forms) from information-theoretic inequalities via lifting, the paper offers a fresh perspective on a classic result in probability theory, suggesting that information-theoretic tools can simplify complex geometric probability proofs.

In summary, this paper provides a rigorous, two-sided characterization of entropic optimal transport using a novel random-subset lifting technique, bridging the gap between information constraints and geometric bounds on stochastic processes.