Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral
Jingbo Liu · 2026
Read Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral by Jingbo Liu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14061.txt.
Introduction
Liu studies the largest average inner product of a random vector with a standard normal vector. The vectors pair under a mutual-information constraint or penalty. He shows this maximum equals a truncated rate-distortion integral, up to universal constants. The proof lifts the problem to a Gaussian process. That process runs over a random subset of a type class. A form of the majorizing measure theorem then finishes the argument.
Catalog record
| CREATOR | Jingbo Liu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28947 |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14061
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral Thanks: This research was supported in part by NSF Grant DMS-2515510. Jingbo Liu Abstract We show that the maximum expected inner product between a random vector and the standard normal vector over all couplings subject to a mutual information constraint or regularization is equivalent to a truncated integral involving the rate-distortion function, up to universal multiplicative constants. The proof is based on a lifting technique, which constructs a Gaussian process indexed by a random subset of the type class of the probability distribution involved in the information-theoretic inequality, and then applying a form of the majorizing measure theorem. I Introduction Optimal transport has been a pivotal tool in many fields including mathematical analysis, machine learning, and statistics. The case where the probability measure on one side is Gaussian is particularly interesting, with applications in generative models. Recently, [ 1 ] established the following result termed “rate-distortion integral”: Given standard Gaussian measure \gamma and an arbitrary probability measure \mu with finite second moments on \mathbb{R}^{n} , we have \displaystyle\sup_{P_{YZ}\in\Pi(\gamma,\mu)}\mathbb{E}[\left<Y,Z\right>]\asymp\int_{0}^{\infty}\sqrt{R_{\mu}(\sigma^{2})}d\sigma (1) where R_{\mu}(\sigma^{2}):=\inf_{P_{UZ}\colon P_{Z}=\mu,\mathbb{E}[\|Z-U\|_{2}^{2}]\leq\sigma^{2}}I(U;Z) denotes the rate-distortion function, \Pi(\gamma,\mu) denotes the set of couplings of \gamma and \mu , and \asymp denotes equivalence up to universal constants. We note that ( 1 ) resembles the standard Dudley integral [ 2 ] [ 3 ] : \displaystyle\mathbb{E}[\max_{t\in T}\left<Y,t\right>]\lesssim\int_{0}^{\infty}\sqrt{\ln N(T,\lambda)}d\lambda (2) where T is a compact set in \mathbb{R}^{n} and N(T,\lambda) denotes its covering number at scale \lambda . However, ( 1 ) is a two-sided bound , whereas \lesssim indicates that ( 2 ) is only an upper bound up to universal constant. The sharpness of ( 1 ) can be understood via the construction in [ 1 ] , which constructs a Gaussian process indexed by the type class of \mu in a certain high-dimensional space. Due to the permutation invariance of the type class, this process is stationary [ 4 ] , so that Dudley’s integral is well-known to be sharp [ 4 ] . Further, [ 1 ] showed that ( 1 ) implies Talagrand’s celebrated majorizing measure theorem by essentially applying the data processing inequality, which is arguably simpler than existing proofs. Moreover, ( 1 ) has other interesting consequences, including sharper rates in statistical regression [ 1 ] and sub-Gaussian comparison theorems [ 1 ] [ 5 ] . In this paper, we establish two-sided bounds on the entropic constrained/regularized optimal transport, analogous to ( 1 ) but with a constraint/regularization of mutual information. It turns out that a two-sided inequality still holds, provided that the integral on the right side is truncated (see Section III for precise statements of the result). The method is similar to the lifting in [ 1 ] , but with an important refinement that replaces the type class with a randomly selected subset, to avoid “overfitting” and hence control the mutual information. While such a random subset is no longer permutation invariant, the resulting process is still close to stationary, since the numbers of randomly selected points in each ball approximately the same due to a sharp double-exponential concentration (truncation of the integral precisely restricts to the regime where such concentration holds). Regularization plays a prominent role in designing efficient algorithms with provable convergence (see [ 6 ] and many references therein), and entropic regularization is the most popular choice which is used in the Sinkhorn’s algorithm. It is thus interesting to explore potential applications of the new inequalities in machine learning and optimization. Furthermore, since our Theorem 2 offers a clean, “incremental form” of the rate-distortion integral satisfying exact tensorization, a tantalizing question is whether there is purely analytic proof of the majorizing measure theorem even simpler than the lifting approach in [ 1 ] . Related work. The lifting approach in [ 1 ] was inspired by methods used for Cover’s problem [ 7 ] . In [ 8 ] , it was shown that the Gaussian-specific bound in [ 7 ] can be recovered using optimal transport methods without lifting. In [ 9 ] , another method based on convex geometry solved Cover’s problem in its original form concerning general discrete memoryless channels, and [ 10 ] applied the lifting argument to the method of [ 9 ] , extracting general bounds on entropic optimal transport that reduces to the one in [ 8 ] in the Gaussian case. These bounds are dimension-dependent, differing from the present paper. More recently, [ 11 ] obtained upper and lower bounds on the related free-energy functional in the case of a finite index set. Their bounds are one-sided in the general case. II Preliminaries Notation. \wedge and \vee to denote the min and max of two numbers. Given probability measures P and Q on a metric space (T,d) , W_{p}(P,Q):=\inf_{P_{XY}\in\Pi(P,Q)}\mathbb{E}^{\frac{1}{p}}[d(X,Y)^{p}] denotes the Wasserstein distance, where \Pi(P,Q) denotes the set of couplings. Product measures are denoted by P\times Q or P^{\otimes N} . \lesssim means less than or equal to up to a universal constant, and \asymp means both \lesssim and \gtrsim . The empirical distribution of a sequence x=(x(1),x(2),\dots,x(d)) is denoted by \widehat{P}_{x} . The cardinality of a set T is denoted |T| . Information-theoretic notation mostly follows [ 12 ] , and logarithms and exponentials have the natural base by default. II-A Information-Constrained/Regularized Optimal Transport Given probability measures \gamma and \mu on \mathbb{R}^{n} , and R\geq 0 , define \displaystyle{\sf w}(\gamma,\mu,R):=\sup_{P_{YZ}\in\Pi(\gamma,\mu)\colon I(Y;Z)\leq R}\mathbb{E}[\left<Y,Z\right>], (3) which we abbreviate as {\sf w}(R) if no confusion. It is related to the information-constrained optimal transport distance since 2{\sf w}(\gamma,\mu,R)=\mathbb{E}[\|Y\|_{2}^{2}]+\mathbb{E}[\|Z\|_{2}^{2}]-\inf_{P_{YZ}\in\Pi(\gamma,\mu)\colon I(Y;Z)\leq R}\mathbb{E}[\|Y-Z\|_{2}^{2}] . Besides the constrained version, we can also define a regularized version: For any \beta\geq 0 , define \displaystyle{\sf f}(\gamma,\mu,\beta):=\sup_{R>0}\{{\sf w}(\gamma,\mu,R)-\beta R\}. (4) Again we may use the abbreviation {\sf f}(\beta) if no confusion. We note that {\sf f}(\beta)\geq 0 . II-B Upper Bounds on Stochastic Processes Following [ 3 ] , a general stochastic process on a metric space T is denoted by (X_{t})_{t\in T} , and a central object is \mathbb{E}[\sup_{t\in T}X_{t}] . To avoid measurability issues in defining the supremum, [ 3 ] actually defined it through the lattice supremum , i.e., \sup_{T^{\prime}\subseteq T;\,|T^{\prime}|<\infty}\mathbb{E}[\max_{t\in T^{\prime}}X_{t}] , and noted that for the purpose of deriving concrete bounds there is no loss of generality in focusing on finite T . If |T|<\infty , we can always represent (X_{t})_{t\in T} in an inner product form: for example, set T=\{e_{1},\dots,e_{n}\} as the standard basis vectors, so that X_{t}=\left<Y,t\right> , where Y=(X_{e_{1}},\dots,X_{e_{n}}) is a random vector. Upper bounds on \mathbb{E}[\sup_{t\in T}X_{t}] based on chaining-type arguments usually only require controls on the tail probabilities, such as sub-Gaussianity. Lower bounds, such as the one in the majorizing measure theorem, are much more delicate, usually stated for Gaussian processes. Since the current paper focuses on two-sided bounds, we will state the results for Gaussian processes, although the upper bound direction only requires sub-Gaussianity (see [ 1 ] for the treatment in the R=\infty case). For Gaussian processes with |T|=n<\infty , we can use the inner product representation \displaystyle X_{t}=\left<Y,t\right>,\quad Y\sim\mathcal{N}(0,I_{n}). (5) Then the metric on T , defined as d(t_{1},t_{2}):=\mathbb{E}^{1/2}[|X_{t_{1}}-X_{t_{2}}|^{2}] , is equivalent to \|t_{1}-t_{2}\|_{2} on \mathbb{R}^{n} . A Gaussian process is called stationary if the metric on the