From Soft-Minoration to Information-Constrained Optimal Transport and Spiked Tensor Models

Given $P_{Z}$ on $\mathbb{R}^{n}$, define $\rho(y):=\ln\mathbb{E}[e^{\left<y,Z\right>}],\quad y\in\mathbb{R}^{n}$, where $Z\sim P_{Z}$ and $\left<,\right>$ denotes the inner product. We may interpret $\rho(y)$ as a soft-max of $\left<y,Z\right>$. Indeed, if $P_{Z}$ is the uniform distribution on a compact set $\mathcal{A}$, then $\rho(y)\leq\max_{z\in\mathcal{A}}\left<y,z\right>$. Moreover, the inequality typically becomes tight when $y$ is large. If $P_{Y}$ is the standard Gaussian distribution, Sudakov’s minoration [23][11] gives

where $c>0$ is a universal constant and ${\sf P}_{l}(\mathcal{A})$ denotes the $l$-packing number of $\mathcal{A}$ under the Euclidean distance. Generalization of Sudakov’s minoration to other log-concave measures $P_{Y}$ has also been considered [11][10][16]. In this paper we explore inequalities of the following form which may be called “soft minoration”:

where the inf is over coupling $P_{Z\bar{Z}}$ under which $Z-\bar{Z}$ is “small” and both $Z$ and $\bar{Z}$ have the same law $P_{Z}$.

One motivation for (2) is network information theory. Cover’s problem asks the minimum relay rate needed for achieving the maximum capacity of a relay channel [7] (see also [26]). Measure concentration and reverse hypercontractivity techniques yield nontrivial bounds but are not sufficient for solving Cover’s problem [27][14][15]. The solution in the Gaussian setting is infinity, as shown by [26] using a rearrangement inequality for the spheres (see also a solution for binary symmetric channels using a similar idea [2]). Bai, Wu, and Ozgur [1] provided a simplified proof for the Gaussian setting by proving a bound on information constrained optimal transport: if $P_{Y}$ is the standard normal distribution in $\mathbb{R}^{n}$, $P_{Z}$ has well-defined differential entropy, and $R>0$, then

where ${\sf h}_{1}:=\frac{n}{2}\ln(2\pi e)$ (all information in nats throughout the paper), the function $\tau_{0}(\theta):=\frac{1}{\sqrt{1-e^{-2\theta}}}$, and $\Pi(P_{Y},P_{Z})$ denotes the set of couplings between two distribution. (3) generalizes Talagrand’s $T_{2}$ inequality by replacing optimal transport with entropy-regularized optimal transport [1]. Previous proofs of (3) relied on Gaussian specific arguments. In contrast, [9] used the traditional auxiliary random variable approach, yielding the same capacity region outer bound for the Gaussian setting as [26][1], and also showed that compress-and-forward solves Cover’s problem for discrete memoryless channels under a full-rankness condition. Concurrently, [12][13] used convex geometry to lower bound $\mathbb{E}[\rho(Y)]$ with packing numbers of $\mathcal{A}$ (for $P_{Z}$ uniform on $\mathcal{A}$), showing the optimality of compress-and-forward for all discrete memoryless channels under conditions originally stated in [7] (without full-rankness assumption).

In [13] the argument was restricted to $P_{Z}$ of the form of a uniform distribution on a set, which is sufficient for the solution of Cover’s problem because when applied to the relay channel, $P_{Z}$ is the restriction of the channel output distribution on the intersection of a type class and a relay decoding set. In this paper, we consider general $P_{Z}$, and the packing number of a set is replaced by the mutual information in (2), which is accomplished by combining the approach of [13] with a tensorization argument. Another difference from [13] is that [13] used the reduction of general $P_{Y}$ to the case of Rademacher distribution; in contrast, this paper uses Barvinok’s thrifty approximation of convex bodies [3] which entails explicit information theoretic bounds for general $P_{Y}$.

We show as a consequence of (2) that for any $l>0$,

which implies (3) as $l\to 0$. As noted in [8][1], information constrained optimal transport is useful in machine learning due to the availability of fast algorithms. In many such applications $P_{Z}$ is the empirical distribution of samples, in which case $h(Z)=-\infty$ and (3) is useless. In contrast, a bound with $I(Z;\bar{Z})$ may still be nontrivial. Moreover, our approach easily extends to general symmetric distribution $P_{Y}$, where $\tau_{0}(\cdot)$ is replaced by another universal function $\tau(\cdot)$ and ${\sf h}_{1}$ or the infimum in (4) is given a general definition.

In statistical physics, a central quantity is the (expected) free energy $\mathbb{E}[\ln\int e^{H(\sigma)}d\mu(\sigma)]$, where $\sigma$ is called the spin or configuration, and the expectation is with respect to the randomness (also known as the disorder) of the Hamiltonian $H(\cdot)$ [25][17]. Clearly (2) provides a lower bound on the free energy, once we embed $H$ and $\sigma$ in a suitable Euclidean space so that $H(\sigma)$ is an inner product. The free energy in the Sherrington-Kirkpatrick model (SK) characterizes the information-theoretic threshold for spiked tensor detection [6]. Statistical physics literature has been focusing on the cases of Rademacher and spherical spins, and existing exact formulae for the free energy generally rely on these structures and are usually hard to evaluate [24][22][6][18]. We prove a simple dimension-free bound in the format of (2) and show its tightness when the tensor order is large and the prior is uniform on a type class, which in turn provides asymptotically tight type II error exponent bounds in spiked tensor detection.

The simplest proof of Sudakov’s minoration (1) in the case of Gaussian $P_{Y}$ is through Gaussian comparison (see e.g. [5][11]). However, this approach is Gaussian specific, and a longstanding goal in this research area is to extend the results to general log-concave measures (see [16]). For our proofs in Section III-IV, it suffices to use the following result of Pajor [19], which can be viewed as a generalization of (1) to the case of general $P_{Y}$ and packing number under the Minkowski functional distance. The proof is a simple application of the Alexandrov-Fenchel inequality, and a review of related convex geometry concepts can be found in [13].

Another key ingredient for the proofs in Section III is to relate $\mathbb{E}[\rho(Y)]$ in (2) to $\mathbb{E}[\max_{z\in\mathcal{A}}\left<Y,z\right>]$, which is achieved by approximating the support of $P_{Y}$ in (1) by a sparser set and then apply Markov’s inequality and the union bound. More specifically, we use the following “thrifty approximation of convex body” by Barvinok [3]. We state here a simplified asymptotic version.

In this section we derive a bound in the form of (2) which, among other things, generalizes (3) to arbitrary $P_{Y}$ satisfying $P_{Y}=P_{-Y}$ (see Corollary 4). To be precise, $\tau_{0}(R/n)$ in (3) will be replaced by a worse constant for general $P_{Y}$; we will explain in the next section how the constant is improved to $\tau_{0}(R/n)$ for Gaussian $P_{Y}$.

Let $\theta(\tau)$ be the function defined implicitly in (6)-(7).

Next, we consider a limiting case of Theorem 1 as $l\to 0$.

An equivalent form of (3) is the following:

For Gaussian $P_{Y}$, we can improve the estimates in Section III by replacing Lemma 2 with the following sharp estimate, which follows from sphere covering (e.g. [4]).

Now define the functions $\theta_{0}(\tau)$ and $\tau_{0}(\theta)$ by the equations $\tau=\frac{1}{\cos\phi}$ and $\theta=\ln\frac{1}{\sin\phi}$; explicitly,

In this section we explore bounds in the form (2) when $Z=X^{\otimes d}$ has a special rank-1 tensor structure, and the implications for the spiked tensor detection problem in statistics [20][6]. The order $d$ tensors associated with $R^{n}$ is again a vector space, and can be given an inner product compatible with the Frobenius norm. The dimension of order $d$ tensors is $n^{d}$ and order $d$ symmetric tensors is ${n+d-1}\choose{d}$, both too large for directly applying a dimension depending minoration such as Lemma 1 for tight bounds. As mentioned in Remark 1, a dimension reduction argument may be applied. In this section, we shall just focus on the case of Gaussian $P_{Y}$ where we can apply a Gaussian comparison argument, which reduces to the random energy model (REM). The result we will use is (see [17, p150])

where $E_{j}\sim\mathcal{N}(0,M/2)$, $j=1,\dots,2^{M}$ are independent.

We will lower bound the soft-max (free energy) when $X\in\mathbb{R}^{n}$ follows the equiprobable distribution on a type class; once this setting is understood, the free energy for other permutation invariant $P_{X}$ (such as i.i.d. coordinates) can be estimated using standard method of types and large deviation analysis.

While the statistical physics literature mostly focuses on $X$ equiprobable on a Boolean cube, a general $X$ is relevant for statistical applications such as spiked tensor detection [20][6]. Let the noise $W\in\mathbb{R}^{n^{d}}$ be a tensor with i.i.d. $\mathcal{N}(0,\frac{2}{n})$ entries. Consider a hypothesis testing problem with observation

• •

  $H_{0}$: $T=W$;

• •

  $H_{1}$: $T=\lambda X^{\otimes d}+W$,

where $\lambda>0$ is the signal to noise ratio. Denote by $P_{H_{0}}$ and $P_{H_{1}}$ the distributions of $T$ under $H_{0}$ and $H_{1}$, respectively. From the Gaussian density formula it is easy to see that

Using concentration, it can be shown that the critical $\lambda$ for detecting a rank-1 spike with nontrivial probability coincides with the largest $\lambda$ for $D(P_{H_{0}}\|P_{H_{1}})=o(n)$. Previously [20] computed such critical $\lambda$ by bounding $D(P_{H_{0}}\|P_{H_{1}})$ with the Rényi divergence $D_{2}(P_{H_{1}}\|P_{H_{0}})$. However when $\lambda$ is above the critical value, $D_{2}(P_{H_{1}}\|P_{H_{0}})$ grows super-linearly in $n$ (see [20, Section 2.4]) and hence does not give a useful bound for $D(P_{H_{0}}\|P_{H_{1}})$ and hence for the free energy. In contrast, we show that Theorem 3 is asymptotically tight for large $d$:

The author would like to thank Qiang Wu for discussions on the SK model and tensor detection.