Discovering Potential Correlations via Hypercontractivity ^†

Abstract

Discovering a correlation from one variable to another variable is of fundamental scientific and practical interest. While existing correlation measures are suitable for discovering average correlation, they fail to discover hidden or potential correlations. To bridge this gap, (i) we postulate a set of natural axioms that we expect a measure of potential correlation to satisfy; (ii) we show that the rate of information bottleneck, i.e., the hypercontractivity coefficient, satisfies all the proposed axioms; (iii) we provide a novel estimator to estimate the hypercontractivity coefficient from samples; and (iv) we provide numerical experiments demonstrating that this proposed estimator discovers potential correlations among various indicators of WHO datasets, is robust in discovering gene interactions from gene expression time series data, and is statistically more powerful than the estimators for other correlation measures in binary hypothesis testing of canonical examples of potential correlations.

1. Introduction

Measuring the strength of an association between two random variables is a fundamental topic of broad scientific interest. Pearson’s correlation coefficient [1] dates from over a century ago and has been generalized seven decades ago as maximal correlation (mCor) to handle nonlinear dependencies [2,3,4]. Novel correlation measures to identify different kinds of associations continue to be proposed in the literature; these include maximal information coefficient (MIC) [5] and distance correlation (dCor) [6]. Despite the differences, a common theme of measurement of the empirical average dependence unites the different dependence measures. Alternatively, these are factual measures of dependence and their relevance is restricted when we seek a potential dependence of one random variable on another. For instance, consider a hypothetical city with very few smokers. A standard measure of correlation on the historical data in this town on smoking and lung cancer will fail to discover the fact that smoking causes cancer, since the average correlation is very small. On the other hand, clearly, there is a potential correlation between smoking and lung cancer; indeed applications of this nature abound in several scenarios in modern data science, including a recent one on genetic pathway discovery [7].

Discovery of a potential correlation naturally leads one to ask for a measure of potential correlation that is statistically well-founded and addresses practical needs. Such is the focus of this work, where our proposed measure of potential correlation is based on a novel interpretation of the Information Bottleneck (IB) principle [8]. The IB principle has been used to address one of the fundamental tasks in supervised learning: given samples ${\{X_i,Y_i\}}_{i=1}^n$, how do we find a compact summary of a variable X that is most informative in explaining another variable Y. The output of the IB principle is a compact summary of X that is most relevant to Y and has a wide range of applications [9,10].

We use this IB principle to create a measure of correlation based on the following intuition: if X is (potentially) correlated with Y, then a relatively compact summary of X can still be very informative about Y. In other words, the maximal ratio of how informative a summary can be in explaining Y to how compact a summary is with respect to X is, conceptually speaking, an indicator of potential correlation from X to Y. Quantifying the compactness by $I(U;X)$ and the information by $I(U;Y)$ we consider the rate of information bottleneck as a measure of potential correlation:

$$\begin{array}{c}\hfill s(X;Y)\equiv \underset{U-X-Y}{sup}\frac{I(U;Y)}{I(U;X)},\end{array}$$

(1)

where $U-X-Y$ forms a Markov chain and the supremum is over all summaries U of X. This intuition is made precise in Section 2, where we formally define a natural notion of potential correlation (Axiom 6), and show that the rate of information bottleneck $s(X;Y)$ captures this potential correlation (Theorem 1) while other standard measures of correlation fail (Theorem 2).

This ratio has only recently been identified as the hypercontractivity coefficient [11]. Hypercontractivity has a distinguished and central role in a large number of technical arenas including quantum physics [12,13], theoretical computer science [14,15], mathematics [16,17,18] and probability theory [19,20]. In this paper, we provide a novel interpretation to the hypercontractivity coefficient as a measure of potential correlation by demonstrating that it satisfies a natural set of axioms such a measure is expected to obey.

For practical use in discovering correlations, the standard correlation coefficients are equipped with corresponding natural sample-based estimators. However, for hypercontractivity coefficient, estimating it from samples is widely acknowledged to be challenging, especially for continuous random variables [21,22,23]. There is no existing algorithm to estimate the hypercontractivity coefficient in general [21], and there is no existing algorithm for solving IB from samples either [22,23]. We provide a novel estimator of the hypercontractivity coefficient—the first of its kind—by bringing together the recent theoretical discoveries in [11,24] of an alternate definition of hypercontractivity coefficient as ratio of Kullback–Leibler divergences defined in (10), and recent advances in joint optimization (the max step in Equation (1)) and estimating information measures from samples using importance sampling [25].

Our main contributions are the following:

• We postulate a set of natural axioms that a measure of potential correlation from X to Y should satisfy (Section 2.1).
• We show that $\sqrt{s(X;Y)}$, our proposed measure of potential correlation, satisfies all the axioms we postulate (Section 2.2). In comparison, we prove that existing standard measures of correlation not only fail to satisfy the proposed axioms, but also fail to capture canonical examples of potential correlations captured by $\sqrt{s(X;Y)}$ (Section 2.3). Another natural candidate is mutual information, but it is not clear how to interpret the value of mutual information as it is unnormalized, unlike all other measures of correlation which are between zero and one.
• Computation of the hypercontractivity coefficient from samples is known to be a challenging open problem. We in troduce a novel estimator to compute hypercontractivity coefficient from i.i.d. samples in a statistically consistent manner for continuous random variables, using ideas from importance sampling and kernel density estimation (Section 3).
• In a series of synthetic experiments, we show empirically that our estimator for the hypercontractivity coefficient is statistically more powerful in discovering a potential correlation than existing correlation estimators; a larger power means a larger successful detection rate for a fixed false alarm rate (Section 4.1).
• We show applications of our estimator of hypercontractivity coefficient in two important datasets: In Section 4.2, we demonstrate that it discovers hidden potential correlations among various national indicators in WHO datasets, including how aid is potentially correlated with the income growth. In Section 4.3, we consider the following gene pathway recovery problem: we are given samples of four gene expressions time series. Assuming we know that gene A causes B, that B causes C, and that C causes D, the problem is to discover that these causations occur in the sequential order: A to B, and then B to C, and then C to D. We show empirically that the estimator of the hypercontractivity coefficient recovers this order accurately from a vastly smaller number of samples compared to other state-of-the art causal influence estimators.

2. Axiomatic Approach to Measure Potential Correlations

We propose a set of axioms that we expect a measure of potential correlation to satisfy. We then show that hypercontractivity coefficient, first introduced in [19], satisfies all the proposed axioms, hence propose hypercontractivity coefficient as a measure of potential correlation. We also show that other standard correlation coefficients and mutual information, on the other hand, violate the proposed axioms.

2.1. Axioms for Potential Correlation

We postulate that a measure of potential correlation ${\rho }^{\ast }:\mathcal{X}\times \mathcal{Y}\to [0,1]$ between two random variables $X\in \mathcal{X}$ and $Y\in \mathcal{Y}$ should satisfy:

• ${\rho }^{\ast }(X,Y)$ is defined for any pair of non-constant random variables X and Y.
• $0\le {\rho }^{\ast }(X,Y)\le 1$.
• ${\rho }^{\ast }(X,Y)=0$ iff X and Y are statistically independent.
• For bijective Borel-measurable functions $f,g:\mathbb{R}\to \mathbb{R}$, ${\rho }^{\ast }(X,Y)={\rho }^{\ast }(f\left(X\right),g\left(Y\right))$.
• If $(X,Y)\sim \mathcal{N}(\mu ,\Sigma )$, then ${\rho }^{\ast }(X,Y)=\left|\rho \right|$, where $\rho$ is the Pearson correlation coefficient.
• ${\rho }^{\ast }(X,Y)=1$ if there exists a subset ${\mathcal{X}}_r\subseteq \mathcal{X}$ such that for a pair of continuous random variables $(X,Y)\in {\mathcal{X}}_r\times \mathcal{Y}$, $Y=f\left(X\right)$ for a Borel-measurable and non-constant continuous function f.

Axioms 1–5 are identical to a subset of the celebrated axioms of Rényi in [4], which ensure that the measure is properly normalized and invariant under bijective transformations, and recovers the Pearson correlation for jointly Gaussian random variables. Rényi’s original axioms for a measure of correlation in [4] included Axioms 1–5 and also that the measure ${\rho }^{\ast }$ of correlation should satisfy

6’.

${\rho }^{\ast }(X,Y)=1$ if for Borel-measurable functions f or g, $Y=f\left(X\right)$ or $X=g\left(Y\right)$.

7’.

${\rho }^{\ast }(X;Y)={\rho }^{\ast }(Y;X)$.

The Pearson correlation violates a subset (3, 4, and 6’) of Rényi’s axioms. Together with recent empirical successes in multimodal deep learning (e.g., [26,27,28]), Rényi’s axiomatic approach has been a major justification of Hirschfeld–Gebelein–Rényi (HGR) maximal correlation coefficient defined as $\mathrm{mCor}(X,Y):={sup}_{f,g}\mathsf{E}\left[f\left(X\right)g\left(Y\right)\right]$, which satisfies all Rényi’s axioms [2]. Here, the supremum is over all measurable functions with $\mathsf{E}\left[f\right(X\left)\right]=\mathsf{E}\left[g\right(Y\left)\right]=0$ and $\mathsf{E}\left[f^2\left(X\right)\right]=\mathsf{E}\left[g^2\left(Y\right)\right]=1$. However, maximal correlation is not the only measure satisfying all of Rényi’s axioms, as we show in the following.

Proposition 1.

For any function $F:[0,1]\times [0,1]\to [0,1]$ satisfying $F(x,y)=F(y,x)$, $F(x,x)=x$, and $F(x,y)=0$ only if $xy=0$, the symmetrized $F(\sqrt{s(X;Y)},\sqrt{s(Y;X)})$ satisfies all Rényi’s axioms.

This follows from the fact that the hypercontractivity coefficient $\sqrt{s(X;Y)}$ satisfies all but the symmetry in Axiom 7’ (Theorem 1), and it follows that a symmetrized version satisfies all axioms, e.g., $(1/2)(\sqrt{s(X;Y)}+\sqrt{s(Y;X)})$ and ${\left(s(X;Y)s(Y;X)\right)}^{1/4}$. A formal proof is provided in Section 5.1.

From the original Rényi’s axioms, for a potential correlation measure, we remove Axiom 7’ that ensures symmetry, as directionality is fundamental in measuring the potential correlation from X to Y. We further replace Axiom 6’ by Axiom 6, as a variable X has a full potential to be correlated with Y if there exists a domain ${\mathcal{X}}_r$ such that X and Y are deterministically dependent and non-degenerate (i.e., not a constant function), as illustrated in Figure 1 for a linear function and a quadratic function.

2.2. The Hypercontractivity Coefficient Satisfies All Axioms

We show that the hypercontractivity coefficient defined in Equation (1) satisfies all Axioms 1–6. Intuitively, $s(X;Y)$ measures how much potential correlation X has with Y. For example, if X and Y are independent, then $s(X;Y)=0$ as X has no correlation with Y (Axiom 3). By data processing inequality, it follows that it is a measure between zero and one (Axiom 2) and also invariant under bijective transformations (Axiom 4). For jointly Gaussian variables X and Y with the Pearson correlation $\rho$, we can show that $s(X;Y)=s(Y;X)={\rho }^2$. Hence, the squared-root of $s(X;Y)$ satisfies Axiom 5. In fact, $\sqrt{s(X;Y)}$ satisfies all desired axioms for potential correlation, and we make this precise in the following theorem whose proof is provided in Section 5.2.

Theorem 1.

Hypercontractivity coefficient $\sqrt{s(X;Y)}$ satisfies Axioms 1–6.

In particular, the hypercontractivity coefficient satisfies Axiom 6 for potential correlation, unlike other measures of correlation (see Theorem 2 for examples). If there is a potential for X in a possibly rare regime in $\mathcal{X}$ to be fully correlated with Y such that $Y=f\left(X\right)$, then the hypercontractivity coefficient is maximum: $s(X;Y)=1$. In the following section, we show that existing correlation measures, on the other hand, violate the proposed axioms.

2.3. Standard Correlation Coefficients Violate the Axioms

We analyze existing measures of correlations under the scenario with potential correlation (Axiom 6), where we find that none of the existing correlation measures satisfy Axiom 6. Suppose X and Y are independent (i.e., no correlation) in a subset ${\mathcal{X}}_d$ of the domain $\mathcal{X}$, and allow X and Y to be arbitrarily correlated in the rest ${\mathcal{X}}_r$ of the domain, such that $\mathcal{X}={\mathcal{X}}_d\cup {\mathcal{X}}_r$. We further assume that the independent part is dominant and the correlated part is rare; let $\alpha :=\mathsf{P}(X\in {\mathcal{X}}_r)$ and we consider the scenario when $\alpha$ is small. A good measure of potential correlation is expected to capture the correlation in ${\mathcal{X}}_r$ even if it is rare (i.e., $\alpha$ is small). To make this task more challenging, we assume that the conditional distribution of $Y\left|\right\{X\in {\mathcal{X}}_r\}$ is the same as $Y\left|\right\{X\notin {\mathcal{X}}_r\}$. Figure 1 illustrates sampled points for two examples from such a scenario and more examples are in Figure 3. Our main result is the analysis of HGR maximal correlation (mCor) [2], distance correlation (dCor) [6], maximal information coefficients (MIC) [5], which shows that these measures are vanishing with $\alpha$ even if the dependence in the rare regime is very high. Suppose $Y|(X\in {\mathcal{X}}_r)=f\left(X\right)$, then all three correlation coefficients are vanishing as $\alpha$ gets small. This in particular violates Axiom 6. The reason is that standard correlation coefficients measure the average correlation whereas the hypercontractivity coefficient measures the potential correlation. The experimental comparisons on the power of these measures confirm our analytical predictions in Figure 4 in Section 4. The formal statement is below and the proof is provided in Section 5.3.

Theorem 2.

Consider a pair of continuous random variables $(X,Y)\in \mathcal{X}\times \mathcal{Y}$. Suppose $\mathcal{X}$ is partitioned as ${\mathcal{X}}_r\cup {\mathcal{X}}_d=\mathcal{X}$ such that $P_{Y|X}\left(S\right|X\in {\mathcal{X}}_r)=P_{Y|X}\left(S\right|X\in {\mathcal{X}}_d)$ for all $S\subseteq \mathcal{Y}$, and Y is independent of X for $X\in {\mathcal{X}}_d$. Let $\alpha =\mathsf{P}\{X\in {\mathcal{X}}_r\}$. The HGR maximal correlation coefficient is

$$\begin{array}{c}\hfill \mathrm{mCor}(X,Y)=\sqrt{\alpha }\mathrm{mCor}(X_r,Y),\end{array}$$

(2)

the distance correlation coefficient is

$$\begin{array}{c}\hfill \mathrm{dCor}(X,Y)=\alpha \mathrm{dCor}(X_r,Y),\end{array}$$

(3)

the maximal information coefficient is upper bounded by

$$\begin{array}{c}\hfill \mathrm{MIC}(X,Y)\le \alpha \mathrm{MIC}(X_r,Y),\end{array}$$

(4)

where $X_r$ is the random variable X conditioned on the rare domain $X\in {\mathcal{X}}_r$.

Under the rare/dominant scenario considered in Theorem 2, $s(X;Y)\ge {\mathrm{mCor}}^2(X;Y)$. It is well known that this inequality holds for any X and Y [19]. In particular, Theorem 3 in [29] shows that hypercontractivity coefficient is a natural extension of the popular HGR maximal correlation coefficient as follows.

Remark 1

(Connection between $s(X;Y)$ and mCor$(X,Y)$ [29]). The squared HGR maximal correlation is a special case of the hypercontractivity optimization in Equation (10) restricted to searching over a distribution $r\left(x\right)$ in a close neighborhood of $p\left(x\right)$.

As $s(X;Y)$ searches over a larger space, it is always larger than or equal to mCor${}^2(X;Y)$. This gives an intuitive justification for using $s(X;Y)$ as a measure of potential influence; we allow search over larger space, but properly normalized by the KL divergence, in a hope to find a potential distribution $r\left(x\right)$ that can influence Y significantly. While hypercontractivity coefficient is a natural extension of HGR maximal correlation coefficient, there is an important difference between hypercontractivity coefficient and HGR maximal correlation coefficient (and other correlation measures); hypercontractivity is directional.

Remark 2

(Asymmetry of $s(X;Y)$). Hypercontractivity coefficient is asymmetric in X and Y while HGR maximal correlation, distance correlation, and MIC are symmetric.

Under the rare/dominant scenario considered in Theorem 2, the hypercontracitivy coefficient $s(X;Y)$ is large because it measures the potential correlation from X to Y. On the other hand, inverse hypercontractivity coefficient $s(Y;X)$, which measures the potential correlation from Y to X, is small as there is no apparent potential correlation from Y to X. This is made precise in the following proposition, with its proof in Section 5.4.

Proposition 2.

Under the hypotheses of Theorem 2, the hypercontractivity coefficient from Y to X is

$$s(Y;X)=\alpha s(Y;X_r),$$

where $X_r$ is the random variable X conditioned on the rare domain $X\in {\mathcal{X}}_r$.

2.4. Mutual Information Violates the Axioms

Beside standard correlation measures, another measure widely used to quantify the strength of dependence is mutual information. We can show that mutual information satisfies Axiom 6 if we replace 1 by ∞. However there are two key problems:

• Practically, mutual information is unnormalized, i.e., $I(X;Y)\in [0,\infty )$. Hence, it provides no absolute indication of the strength of the dependence.
• Mathematically, we are looking for a quantity that tensorizes, i.e., does not change when there are many i.i.d. copies of the same pair of random variables.

Remark 3

(Tensorization property of $s(X;Y)$ [30]). Hypercontractivity coefficient tensorizes, i.e.,

$$s(X_1,\dots ,X_n;Y_1,\dots ,Y_n)=s(X_1,Y_1),\mathit{for}i.i.d.(X_i,Y_i),i=1,\cdots ,n.$$

On the other hand, mutual information is additive, i.e.,

$$I(X_1,\cdots ,X_n;Y_1,\cdots ,Y_n)=nI(X_1;Y_1),\mathrm{for}\mathrm{i}.\mathrm{i}.\mathrm{d}.(X_i,Y_i),i=1,\cdots ,n.$$

Tensorizing quantities capture the strongest relationship among independent copies while additive quantities capture the sum. For instance, mutual information could be large because a small amount of information accumulates over many of the independent components of X and Y (when X and Y are high dimensional) while tensorizing quantities would rule out this scenario, where there is no strong dependence. When the components are not independent, hypercontractivity indeed pools information from different components to find the strongest direction of dependence, which is a desirable property.

One natural way to normalize mutual information is by the log of the cardinality of the input/output alphabets [31]. One can interpret a popular correlation measure MIC as a similar effort for normalizing mutual information and is one of our baselines.

Given that other correlation measures and mutual information do not satisfy our axioms, a natural question to ask is whether hypercontractivity is a unique solution that satisfies all the proposed axioms. In the following, we show that the hypercontractivity coefficient is not the only one satisfying all the proposed axioms—just as HGR correlation is not the only measure satisfying Rényi’s original axioms.

2.5. Hypercontractivity Ribbon

We show that a family of measures known as hypercontractivity ribbon, which includes hypercontractivity coefficient as a special case, satisfy all the axioms. The hypercontractivity ribbon [19,32] is a class of measures parametrized by $\alpha >0$ as

$$\begin{array}{c}\hfill r_{\alpha }(X;Y)=\underset{r(x,y)\ne p(x,y)}{sup}\frac{D\left(r\right(y)\parallel p(y\left)\right)}{D\left(r\right(x)\parallel p(x\left)\right)+\alpha D\left(r\right(y\left|x\right)\parallel p\left(y\right|x\left)\right)},\end{array}$$

(5)

where $D\left(r\right(x\left)\right|\left|p\right(x\left)\right)$ denotes the KL divergence of $r\left(x\right)$ and $p\left(x\right)$. An alternative characterization of hypercontractivity ribbon in terms of mutual information is provided in [24,32];

$$\begin{array}{c}\hfill r_{\alpha }(X;Y)=\underset{p\left(u\right|x,y)}{sup}\frac{I(U;Y)}{I(U;X)+\alpha I(U;Y|X)}.\end{array}$$

(6)

from which we can see that hypercontractivity coefficient is a special case of hypercontractivity ribbon [11]:

$$\begin{array}{cc}\hfill s(X;Y)& =\underset{\alpha \to \infty }{lim}{r}_{\alpha }(X;Y)=\underset{\alpha \to \infty }{lim}{s}_{\alpha }(X;Y).\hfill \end{array}$$

Proposition 3.

The (re-parameterized) hypercontractivity ribbon $s_{\alpha }(X;Y):=(\alpha r_{\alpha }(X;Y)-1)/(\alpha -1)$, for $\alpha >1$, satisfies Axioms 1–6.

Proof. 

By definition, $s_{\alpha }(X;Y)$ is defined for any pair of non-constant random variables (Axiom 1) and is between 0 and 1 by data processing inequality (Axiom 2). We can show that $s_{\alpha }(X;Y)$ satisfies Axioms 3 and 4, in a similar way to show $s(X;Y)$ satisfies Axioms 3 and 4. Also, $s_{\alpha }(X;Y)={\rho }^2$ for a jointly Gaussian X, Y with Pearson correlation $\rho$ [24] (Axiom 5). Finally, $s_{\alpha }(X;Y)$ satisfies Axiom 6 because $r_{\alpha }(X;Y)$ is non-increasing in $\alpha$, which implies that $s_{\alpha }(X;Y)=r_{\alpha }(X;Y)=1$ if $s(X;Y)=1$. ☐

Although hypercontracitivy ribbon satisfies all axioms, a few properties of the hypercontractivity coefficient make it more attractive than hypercontractivity ribbon for practical use; hypercontractivity coefficient can be efficiently estimated from samples (see Section 3). Hypercontractivity coefficient is a natural extension of the popular HGR maximal correlation coefficient (Remark 1).

2.6. Multidimensional X and Y

In this section, we discuss potential correlation of multidimensional X and Y. While most of the correlation coefficients, including the hypercontractivity coefficient, are well-defined for multi-dimensional X and Y, the axioms are specific to univariate X and Y. To bridge this gap, we propose replacing Axiom 5, as this is the only axiom specific to univariate random variables.

Axiom 5’.

If $(X,Y)\sim \mathcal{N}\left(\mu ,\Sigma =\left[\begin{array}{cc}{\Sigma }_X& {\Sigma }_{XY}\\ {\Sigma }_{YX}& {\Sigma }_Y\end{array}\right]\right)$, then ${\rho }^{\ast }(X,Y)=\parallel {\Sigma }_X^{-1/2}{\Sigma }_{XY}{\Sigma }_Y^{-1/2}\parallel$, where $\parallel ·\parallel$ is the spectral norm of a matrix.

This recovers the original Axiom 5 when restricted to univariate X and Y. This naturally generalizes both Rényi’s axioms and the proposed potential correlation axioms to multidimensional X and Y.

Proposition 4.

Axiom 5’, together with original Rényi’s Axioms 1–4, 6’, and 7’, recovers maximal correlation (mCor) as a measure satisfying all Axioms even in this multi-dimensional case. Axiom 5’, together with our proposed Axioms 1–4, and 6, recovers the hypercontractivity coefficient $\sqrt{s(X;Y)}$ as a measure satisfying all axioms.

The second statement in the proposition follows from the analyses of the hypercontractivity coefficient of Gaussian distributions in [33]. A formal proof is provided in Section 5.7.

2.7. Noisy, Discrete, Noisy and Discrete Potential Correlation

In this section, we consider more general scenarios of potential correlation than the one in Axiom 6. We consider (i) noisy potential correlation where $Y=f\left(X\right)+Z$ for a Gaussian noise Z for $(X,Y)\in {\mathcal{X}}_r\times \mathcal{Y}$, (ii) discrete potential correlation, where ${\mathcal{X}}_r=\{1,\cdots ,k\}$, and (iii) noisy discrete potential correlation—a random corruption model. For these three examples, we obtain a lower bound on $s(X;Y)$.

Example 1.

Suppose for $(X,Y)\in {\mathcal{X}}_r\times \mathcal{Y}$, $(X,Y)\sim \mathcal{N}(\mathbf{0},\Sigma )$ for

$$\Sigma =\left[\begin{array}{cc}1& \rho \\ \rho & 1\end{array}\right].$$

Then

$$\begin{array}{c}\hfill s(X;Y)\ge \frac{\log \frac{1}{1-{\rho }^2}+log\frac{1}{1+{\rho }^2}}{log\frac{1}{1-{\rho }^2}+\frac{H\left(\alpha \right)}{\alpha }}\end{array}$$

(7)

Proof is in Section 5.5.

We now consider for discrete $(X,Y)$. We start with the case for which X and Y are perfectly correlated for $(X,Y)\in {\mathcal{X}}_r\times \mathcal{Y}$.

Example 2.

Suppose that for a pair of discrete random variables $(X,Y)\in \mathcal{X}\times \mathcal{Y}$, there exists a subset ${\mathcal{X}}_r=\{1,2,\cdots ,k\}\subseteq \mathcal{X}$ for which $\mathsf{P}\{X\in {\mathcal{X}}_r\}=\alpha$ and $X|\{X\in {\mathcal{X}}_r\}\sim \mathrm{Unif}[1:k]$ and $Y=X$ for $X\in {\mathcal{X}}_r$. Then,

$$s(X;Y)\ge \frac{logk}{logk+log(1/\alpha )}.$$

The inequality holds by considering $r\left(x\right)={\mathbb{I}}_{\{X=1\}}$ in (10).

We conjecture this lower bound is indeed tight for $\alpha \le 0.5$ based on numerical simulations. From this lower-bound, we can see the trade-off between k and $\alpha$. As $k\to \infty$, the lower bounds approaches to 1. As $\alpha \to 1$, the lower bound approaches to 1. As $\alpha \to 0$, the lower bound approaches to 0. In the following, we consider the case where X and Y are not perfectly correlated in $({\mathcal{X}}_r\times \mathcal{Y})$ for discrete $(X,Y)$. In particular, we consider a random corruption model for $({\mathcal{X}}_r\times \mathcal{Y})$ and obtain a lower bound on $s(X;Y)$.

Example 3.

Consider a random corruption noise model for $(X,Y)\in {\mathcal{X}}_r\times \mathcal{Y}$, i.e.,

$$Y=\left\{\begin{array}{cc}{X}_r\hfill & w.p.1-\frac{k}{k-1}ϵ,\hfill \\ \mathit{Unif}[1:k]\hfill & w.p.\frac{1}{k-1}ϵ\hfill \end{array}\right..$$

Then

$$\begin{array}{c}\hfill s(X;Y)\ge \frac{(1-ϵ)logk(1-ϵ)+ϵlogkϵ/(k-1)}{log(k/\alpha )}=\frac{logk-H_2\left(ϵ\right)-ϵlog(k-1)}{log(k/\alpha )}.\end{array}$$

(8)

On the other hand,

$$\begin{array}{c}\hfill {\mathrm{mCor}}^2(X;Y)=\alpha {\left(1-\frac{k}{k-1}ϵ\right)}^2,0\le ϵ\le \frac{k-1}{k}.\end{array}$$

(9)

Proof is in Section 5.6.

In Figure 2, we show plots of lower bounds on $s(X;Y)$ and mCor$(X;Y)$ in Examples 1–3; from these figures, we can see that $s(X;Y)$ increases as $\rho \to 1$ and $k\to \infty$, and $s(X;Y)$ is larger than mCor$(X;Y)$ for $\rho \approx 1$ and large k.

3. Estimator of the Hypercontractivity Coefficient from Samples

In this section, we present an algorithm to compute the hypercontractivity coefficient $s(X;Y)$ from i.i.d. samples ${\{X_i,Y_i\}}_{i=1}^n$. The computation of the hypercontractivity coefficient from samples is known to be challenging for continuous random variables [22,23], and to the best of our knowledge, there is no known efficient algorithm to compute the hypercontractivity coefficient from samples. Our estimator is the first efficient algorithm to compute the hypercontractivity coefficient, based on the following equivalent definition of the hypercontractivity coefficient, shown recently in [11]:

$$\begin{array}{ccc}\hfill s(X;Y)& \equiv & \underset{r_x\ne p_x}{sup}\frac{D\left(r_y\right|\left|p_y\right)}{D\left(r_x\right|\left|p_x\right)}.\hfill \end{array}$$

(10)

There are two main challenges for computing $s(X;Y)$. The first challenge is – given a marginal distribution $r_x$ and samples from $p_{xy}$, how do we estimate the KL divergences $D\left(r_y\right|\left|p_y\right)$ and $D\left(r_x\right|\left|p_x\right)$. The second challenge is the optimization over the infinite dimensional simplex. We need to combine estimation and optimization together in order to compute $s(X;Y)$. Our approach is to combine ideas from traditional kernel density estimates and from importance sampling. Let $w_i=r_x\left(X_i\right)/p_x\left(X_i\right)$ be the likelihood ratio evaluated at sample i. We propose the estimation and optimization be solved jointly as follows:

Estimation: To estimate KL divergence $D\left(r_x\right|\left|p_x\right)$, notice that

$$\begin{array}{ccc}\hfill D\left(r_x\right|\left|p_x\right)& =& {\mathbb{E}}_{X\sim p_x}\left[\frac{r_x\left(X\right)}{p_x\left(X\right)}log\frac{r_x\left(X\right)}{p_x\left(X\right)}\right].\hfill \end{array}$$

Using empirical average to replace the expectation over $p_x$, we propose

$$\begin{array}{c}\hfill \widehat{D}(r_x\left|\right|p_x)=\frac{1}{n}\sum _{i=1}^n\frac{r_x\left(X_i\right)}{p_x\left(X_i\right)}log\frac{r_x\left(X_i\right)}{p_x\left(X_i\right)}=\frac{1}{n}\sum _{i=1}^n{w}_{i}log{w}_i.\end{array}$$

For $D\left(r_y\right|\left|p_y\right)$, we follow the similar idea, but the challenge is in computing $v_j=r_y\left(Y_j\right)/p_y\left(Y_j\right)$. To do this, notice that $r_{xy}=r_x{p}_{y|x}$, so

$$\begin{array}{ccc}\hfill r_y\left(Y_j\right)& =& {\mathbb{E}}_{X\sim r_x}\left[p_{y|x}\left(Y_j\right|X)\right]={\mathbb{E}}_{X\sim p_x}\left[p_{y|x}\left(Y_j\right|X)\frac{r_x\left(X\right)}{p_x\left(X\right)}\right].\hfill \end{array}$$

Replacing the expectation by empirical average again, we get the following estimator of $v_j$:

$$\begin{array}{ccc}\hfill {\widehat{v}}_j& =& \frac{1}{n}\sum _{i=1}^n\frac{p_{y|x}\left(Y_j\right|X_i)}{p_y\left(Y_j\right)}\frac{r_x\left(X_i\right)}{p_x\left(X_i\right)}=\frac{1}{n}\sum _{i=1}^n\underset{A_{ji}}{\underbrace{\frac{p_{xy}(X_i,Y_j)}{p_x\left(X_i\right)p_y\left(Y_j\right)}}}{w}_i.\hfill \end{array}$$

We can write this expression in matrix form as $\widehat{\mathbf{v}}={\mathbf{A}}^T\mathbf{w}$. We use a kernel density estimator from [34] to estimate the matrix $\mathbf{A}$, but our approach is compatible with any density estimator of choice.

Optimization: Given the estimators of the KL divergences, we are able to convert the problem of computing $s(X;Y)$ into an optimization problem over the vector $\mathbf{w}$. Here a constraint of $(1/n){\sum }_{i=1}^n{w}_i=1$ is needed to satisfy ${\mathbb{E}}_{p_x}[r_x/p_x]=1$. To improve numerical stability, we use $logs(X;Y)$ as the objective function. Then the optimization problem has the following form:

$$\begin{array}{ccc}\hfill {\max }_{\mathbf{w}}& & log\left(({\mathbf{w}}^T\mathbf{A}log\left({\mathbf{A}}^T\mathbf{w}\right)\right)-log\left({\mathbf{w}}^{T}log\mathbf{w}\right)\hfill \\ \hfill \mathrm{subject}\mathrm{to}& & \frac{1}{n}\sum _{i=1}^n{w}_i=1\hfill \\ & & w_i\ge 0,\forall i\hfill \end{array}$$

where ${\mathbf{w}}^{T}log\mathbf{w}={\sum }_{i=1}^n{w}_{i}log{w}_i$ for short. Although this problem is not convex, we apply gradient descent to maximize the objective. In practice, we initialize $w_i=1+\mathcal{N}(0,{\sigma }^2)$ for ${\sigma }^2=0.01$. Hence, the initial $r_x$ is perturbed mildly from $p_x$. Although we are not guaranteed to achieve the global maximum, we consistently observe in extensive numerical experiments that we have 50–60% probability of achieving the same maximum value, which we believed to be the global maximum. A theoretical analysis of the landscape of local and global optima and their regions of attraction with respect to gradient descent is an interesting and challenging open question, outside the scope of this paper.

Consistency of Estimation

While a theoretical understanding of the performance of gradient descent on the optimization step (where the number of samples is fixed) above is technically very challenging, we can study the performance of the solution as the number of samples increases. In particular we show below (under suitable simplifying assumptions to get to the essence of the proof) that the optimal solution to the finite sample optimization problem is consistent. Suppose that $\mathcal{X}$ is discrete. Further we restrict the optimization over a quantized and bounded set $T_{\Delta }$, where $\mathbf{w}\in T_{\Delta }$ is quantized by a gap $\Delta$ and satisfies: (1) $C_1\le w_i\le C_2$ for all i; (2) $(1/n){\sum }_{i=1}^n{w}_{i}log{w}_i>C_0$. We further assume that we have access of $\mathbf{A}=P_{xy}(X_i,Y_j)/P_x\left(X_i\right)P_y\left(Y_j\right)$. Define ${\widehat{s}}_{\Delta }(X;Y)={max}_{\mathbf{w}\in T_{\Delta }}{\mathbf{w}}^T\mathbf{A}log\left({\mathbf{A}}^T\mathbf{w}\right)/{\mathbf{w}}^{T}log\mathbf{w}$, then with two further simplifying conditions on the joint distribution (formally stated in Section 5.8), we can prove consistency of our estimation procedure:

Theorem 3.

As n goes to infinity, ${\widehat{s}}_{\Delta }(X;Y)$ converges to $s(X;Y)$ up to a resolution of quantization in probability, i.e., for any $\epsilon >0$, $\Delta >0$ and $s(\Delta )=O(\Delta )$, we have

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\mathcal{P}\left(|{\widehat{s}}_{\Delta }(X;Y)-s(X;Y)|>\epsilon +s(\Delta )\right)=0.\end{array}$$

(11)

4. Experimental Results

We present experimental results on synthetic and real datasets showing that the hypercontractivity coefficient $\left(a\right)$ is more powerful in detecting potential correlation compared to existing measures; $\left(b\right)$ discovers hidden potential correlations among various national indicators in WHO datasets; and $\left(c\right)$ is more robust in discovering pathways of gene interactions from gene expression time series data.

4.1. Synthetic Data: Power Test on Potential Correlation

As our estimator (and the measure itself) involves a maximization, it is possible that we are sensitive to outliers and may capture spurious noise. Via a series of experiments we show that the hypercontractivity coefficient and our estimator are capturing the true potential correlation. As shown in Figure 3, we generate pairs of datasets—one where X and Y are independent and one where there is a potential correlation as per our scenario. We run experiment with eight types of functional associations, following the examples from [5,35,36]. For the correlated datasets, out of n samples ${\left\{(x_i,y_i)\right\}}_{i=1}^n$, $\alpha n$ rare but correlated samples are in $\mathcal{X}=[0,1]$ and $(1-\alpha )n$ dominant but independent samples are in $\mathcal{X}\in [1,1.1]$. The rare but correlated samples are generated as $x_i\sim \mathrm{Unif}[0,1],y_i\sim f\left(x_i\right)+\mathcal{N}(0,{\sigma }^2)$ for $i\in [1:\alpha n]$. The dominant samples are generated as $x_i\sim \mathrm{Unif}[1,1.1],y_i\sim f\left(\mathrm{Unif}[0,1]\right)+\mathcal{N}(0,{\sigma }^2)$ for $i\in [\alpha n+1,n]$.

Table 1. Correlation estimates for independent and correlated samples from Figure 3.

				Cor		dCor		mCor		MIC		HC
#	Function	$\mathit{\alpha }$	${\mathit{\sigma }}^{\mathbf{2}}$	Dep	Indep	Dep	Indep	Dep	Indep	Dep	Indep	Dep	Indep
1	Linear	0.05	0.03	0.03	0.00	0.19	0.11	0.06	0.04	0.21	0.17	0.18	0.08
2	Quadratic	0.10	0.10	0.00	0.01	0.09	0.10	0.07	0.02	0.21	0.18	0.08	0.04
3	Cubic	0.10	0.00	0.02	0.00	0.16	0.08	0.09	0.03	0.26	0.17	0.11	0.04
4	sin($4\pi X$)	0.05	0.03	0.00	0.00	0.10	0.06	0.03	0.01	0.20	0.18	0.10	0.04
5	sin($16\pi X$)	0.10	0.00	0.00	0.00	0.07	0.08	0.03	0.03	0.18	0.22	0.03	0.03
6	$X^{1/4}$	0.05	0.01	0.01	0.00	0.12	0.07	0.02	0.01	0.20	0.20	0.12	0.04
7	Circle	0.10	0.00	0.00	0.00	0.09	0.05	0.01	0.03	0.16	0.17	0.06	0.01
8	Step func.	0.10	0.03	0.00	0.00	0.13	0.07	0.04	0.02	0.20	0.17	0.11	0.04

shows the hypercontractivity coefficient and the other correlation coefficients for correlated and independent datasets shown in Figure 3, along with the chosen value of $\alpha$ and ${\sigma }^2$. Correlation estimates with the largest separation for each row is shown in bold. The hypercontractivity coefficient gives the largest separation between the correlated and the independent dataset for most functional types.

A formal statistical approach to test the robustness as well as accuracy is to run power tests: testing for the power of the estimator in binary hypothesis tests. To compute the power of each estimator, we compare the false negative rate at a fixed false positive rate of, say, 5%. We generate 500 independent datasets and 500 correlated datasets. We compute the correlation estimates on 500 independent samples, and take the top 5% as a threshold. We compute the correlation estimates on 500 correlated samples. Power is defined as the fraction of correlated datasets for which the correlation estimate is larger than the threshold.

We show empirically that for linear, quadratic, sine with period 1/2, and the step function, the hypercontractivity coefficient is more powerful as compared to other measures. For a given setting, a larger power means a larger successful detection rate for a fixed false alarm rate. Figure 4 shows the power of correlation estimators as a function of the additive noise level, ${\sigma }^2$, for $\alpha =0.05$ and $n=320$. The hypercontractivity coefficient is more powerful than other correlation estimators for most functions. The power of all the estimators are very small for sine (period 1/8) and circle functions. This is not surprising given that it is very hard to discern the correlated and independent cases even visually, as shown in Figure 3.

Figure 5 plots the power of correlation estimators as a function of noise level for $\alpha =0.1$ and $n=320$. As we can see from these figures, hypercontractivity estimator is more powerful than other correlation estimators for most functions. For circle function, the gap between the power of hypercontractivity estimator and the powers of other estimators is significantly large.

On the other hand, hypercontractivity estimator is power deficient for the cubic function. This is because in estimating hypercontractivity coefficient, we estimate $p\left(y_j\right|x_i)/p\left(y_j\right)$ using the kernel density estimator (KDE), which gives a smooth estimate of $p\left(y_j\right|x_i)/p\left(y_j\right)$, i.e., for $x_i$ and $x_j$ close to each other, estimated $p\left(y\right|x_i)$ and $p\left(y\right|x_j)$ are close to each other. Hence, for a correlated dataset for a cubic function, shown in Figure 6C, the estimated $p\left(y\right|x)$ does not vary much for x. (Estimated $p\left(y\right|x)$ for $x\in [0.8:1]$ and $p\left(y\right|x)$ for $x\in [1:1.1]$ are close to each other). This results in a small hypercontracitivy, which in turn results in a low power in the hypothesis testing. To further analyze this effect, we considered the same dataset but with dominant independent samples appear on the left, as shown in Figure 6E,F, and computed the power of hypercontractivity estimator, shown in Figure 6D. Hypercontractivity estimator is much more powerful than the one for the original dataset. This is because the estimated $p\left(y\right|x)$ for $x\in [0.8,1]$ is very different from the estimated $p\left(y\right|x)$ for $x\in [-0.1,0]$, which results in a large estimate of hypercontractivity coefficient for the correlated dataset.

To investigate the dependency of power on $\alpha$ more closely, in Figure 7, we plot the power vs. $\alpha$ or $n=320$ and ${\sigma }^2=0.1$. Hypercontractivity estimator is more powerful than other estimators for most $\alpha$, for all functions except for cubic function. For a sine with period 1/8, due to its high frequency, the powers of all the correlation estimators do not increase as $\alpha$ increases. Figure 8 plots the power vs. sample size n for $\alpha =0.05$ and ${\sigma }^2=0.1$. For sine with period 1/2, hypercontractivity estimator is much more powerful than the other estimators for all sample sizes. We can also see that for sine with period 1/8, powers of all correlation estimators do not increase as sample size increases.

4.2. Real Data: Correlation between Indicators of WHO Datasets

We computed the hypercontractivity coefficient, MIC, and Pearson correlation of 1600 pairs of indicators from 202 samples (countries, non i.i.d.) in the World Health Organization (WHO) dataset [5]. Figure 9 illustrates that the hypercontractivity coefficient discovers hidden potential correlation (e.g., in Figure 9E–H, whereas other measures fail. Scatter plots of Pearson correlation vs. the hypercontractivity coefficient and MIC vs. the hypercontractivity coefficient for all pairs are presented in Figure 9A,D. The samples for pairs of indicators corresponding to B,C,E–J in Figure 9A,D are shown in Figure 9B,C,E–J, respectively. In Figure 9B, it is reasonable to assume that the number of bad teeth per child is uncorrelated with the democracy score. The hypercontractivity coefficient, MIC, and Pearson correlation are all small, as expected. In Figure 9C, the correlation between CO${}_2$ emissions and energy use is clearly visible, and all three correlation estimates are close to one.

However, only the hypercontractivity coefficient discovers the hidden potential correlation in Figure 9E–H. In Figure 9E, the data is a mixture of two types of countries—one with small amount of aid received (less than $$5\times {10}^8$), and the other with large amount of aid received (larger than $$5\times {10}^8$). Dominantly many countries (104 out of 146) belong to the first type (small aid), and for those countries, the amount of aid received and the income growth are independent. For the remaining countries with larger aid received, although those are rare, there is a clear correlation between the amount of aid received and the income growth.

Similarly in Figure 9F, there are two types of countries—one with small arms exports (less than $$2\times {10}^8$) and the other with large arms exports (larger than $$2\times {10}^8$). Dominantly many countries (71 out of 82) belong to the first type, for which the amount of arms exports and the health expenditure are independent. For the remaining countries that belong to the second type, on the other hand, there is a visible correlation between the arms exports and the health expenditure. This is expected as for those countries that export arms the GDP is positively correlated with both arms exports and health expenditure, whereas for those do not have arms industry, these two will be independent.

In Figure 9G, for dominant number of countries, the number of male deaths from the colon and rectum cancer is small (for 145 out of 169 countries, it is smaller than 2000, while for the remaining countries, it is between 2000 and 50,000), and it is independent of the amount of health expenditure. On the other hand, for the remaining countries with larger number of male deaths from colon and rectum cancer, the two indicators are positively associated. This is expected as both indicators are positively correlated with the population. Only hypercontractivity discovers this hidden potential correlation. MIC and Pearson correlation are small.

In Figure 9H, for dominant number of countries, the number of broadband subscribers is very small and is independent of the private health expenditure; 155 out of 180 countries have broadband subscribers less than ${10}^6$. On the other hand, for the remaining countries, the number of broadband subscribers is positively correlated with the private health expenditure. This is as expected because both indicators are positively correlated with the population. Hypercontractivity is large for this dataset, discovering the hidden correlation, whereas all other correlations all small.

In Figure 9I, most countries do not have large hydroelectricity facilities, and for those countries, energy use and hydroelectricity consumption are independent (41 out of 53 countries have hydroelectricity ≤0.25). On the other hand, for the countries which have hydroelectrocity facilities, the amount of total energy use and the amount of hydroelectricity consumption are positively correlated. Hypercontractivity discovers this hidden potential correlation. Unlike in Figure 9G,H for which the fraction of correlated samples was only about $14\%$, in Figure 9I, the fraction of correlated samples is about $23\%$. Hence, Pearson correlation is larger compared to Pearson correlation values for Figure 9G,H.

In Figure 9J, there is one country (Luxembourg) with very large amounts of foreign direct investment net inflow and outflow. Due to this outlier, Pearson correlation is close to 1. Hypercontractivity is also close to 1, whereas MIC is small. To analyze the effect of the outlier in correlation measures, in the following, we compute the correlation measures for samples without an outlier.

4.2.1. How Hypercontractivity Changes as We Remove Outliers

Figure 10, Figure 11, Figure 12, Figure 13, Figure 14 and Figure 15, on the left, are shown samples from Figure 9E–J respectively. On the middle and on the right are shown all samples but one outlier and all samples but two outliers, respectively. By comparing the hypercontractivity coefficients for the three datasets for each pair of indicators, we can analyze the effect of outliers on hypercontractivity. For a comparison, on the top of each figure, we show the estimated hypercontractivity (HC), MIC, Pearson correlation (Cor), distance correlation (dCor), maximal correlation (mCor), and the hypercontractivity for reversed direction (HCR). In Figure 10 and Figure 11, we can see that hypercontractivity is more sensitive to an outlier than other correlation measures.

In Figure 12 (left), the two countries with the largest number of male deaths from the colon and rectum cancer are China and United States. As China is removed from the dataset, in (middle), hypercontractivity remains unchanged. As we also remove United States, in (right), hypercontractivity becomes small, 0.17. This value is still larger than the typical coefficient for two independent indicators (≈0.05), we can see that hypercontractivity is more sensitive to the outlier than other correlation measures.

In Figure 13, the two countries with the largest number of broadband subscribers are United States and China. When we remove United States from the samples, hypercontractivity becomes close to zero, which also shows hypercontractivity is sensitive to the outliers.

In Figure 14, hypercontractivity remains large even after we remove outliers. The two countries with the largest amount of hydroelectricity consumption are Norway and Iceland. Even after we remove Norway from the samples, as shown in (middle), hypercontractivity remains large. As we further remove one outlier (Iceland) from the samples, as shown in (right), hypercontractivity becomes 0.49.

In Figure 15 (middle), all samples but Luxembourg is shown. We can see that most countries have a very small absolute amount of foreign direct investment net outflows (For 126 out of 157 countries, it is between $[-2,2]$), and for those countries, the foreign direct investment net outflow is independent of foreign direct investment net inflows. For the remaining countries, there is a positive association between the outflow and the inflow. Hypercontractivity captures this hidden correlation better than other correlations; hypercontractivity is 0.47, whereas MIC and Pearson correlation are small. If we further remove the rightmost sample, as shown in (right), hypercontractivity becomes small.

Whether we should consider a sample in a rare type as a meaningful sample or as an outlier depends on the application. If we use hypercontractivity to discover a pair of measures for which one variable can be potentially correlated with the other, then we would expect to discover that an aid for a country has potential correlation in the income growth. Other measures will fail. It is possible that hypercontractivity might have larger false positive rate, and depending on the application, one might prefer to error on the side of having more positive cases to be screened by further experiments, surveys, or human judgements.

4.2.2. Hypercontractivity Detecting an Outlier

In Figure 16A and B, we show examples of pairs of indicators for which there is one outlier and the remaining samples are independent. In Figure 16C,D, we show the scatterplot of the same pairs of indicators as in Figure 16A,B, respectively, with one outlier removed. As shown in Figure 16A,B, hypercontractivity is close to 1, when there is an outlier. As shown in Figure 16B,D, hypercontractivity is close to 0, when the outlier is removed. This implies that one single outlier can make the hypercontractivity large. We can see similar patterns for other correlation measures, such as Pearson correlation, distance correlation, and maximal correlation from Figure 16, and MIC from Figure 16C,D. Nonetheless, these other correlation measures are not as sensitive to an outlier as hypercontractivity coefficient.

To further study how hypercontractivity estimator is affected by outliers, we ran simulations on synthetic data. We generated three sets of synthetic data shown in Figure 17 and computed hypercontractivity coefficients. In Figure 17 (left), an outlier is located far from the rest of samples, and the estimated hypercontractivity coefficient is 0.99. In Figure 17 (middle), an outlier is located close to the rest of samples, and the estimated hypercontractivity coefficient is 0.04. In Figure 17 (right), X and Y are potentially correlated, and the hypercontractivity estimate is 0.17. As can bee seen from this simulation and experimental results on WHO dataset, our hypercontractivity estimator is sensitive to outliers. If one wants to filter out the effect of outliers, one can combine methods for robust estimation, such as trimming and winsorizing [37,38,39], along with the hypercontractivity estimator. This is an interesting future research direction.

4.3. Gene Pathway Recovery From Single Cell Data

We replicate the genetic pathway detection experiment from [7], and show that hypercontractivity correctly discovers the genetic pathways from smaller number of samples. A genetic pathway is a series of genes interacting with each other as a chain. Consider the following setup where four genes whose expression values in a single cell are modeled by random processes $X_t$, $Y_t$, $Z_t$ and $W_t$ respectively. These 4 genes interact with each other following a pathway $X_t\to Y_t\to Z_t\to W_t$; it is biologically known that $X_t$ causes $Y_t$ with a negligible delay, and later at time $t^{\prime }$, $Y_{t^{\prime }}$ causes $Z_{t^{\prime }}$, and so on. Our goal is to recover this known gene pathway from sampled datapoints. For a sequence of time points ${\left\{t_i\right\}}_{i=0}^m$, we observe $n_i$ i.i.d. samples ${\{X_{t_i}^{\left(j\right)},Y_{t_i}^{\left(j\right)},Z_{t_i}^{\left(j\right)},W_{t_i}^{\left(j\right)}\}}_{j=1}^{n_i}$ generated from the random process $P(X_{t_i},Y_{t_i},Z_{t_i},W_{t_i})$. We use the real data obtained by the single-cell mass flow cytometry technique [7].

Given these samples from time series, the goal of [7] is to recover the direction of the interaction along the known pathway using correlation measures as follows, where they proposed a new measure called DREMI. The DREMI correlation measure is evaluated on each pairs on the pathway, $\tau (X_{t_i},Y_{t_i})$, $\tau (Y_{t_i},Z_{t_i})$ and $\tau (Z_{t_i},W_{t_i})$, at each time points $t_i$. It is declared that a genetic pathway is correctly recovered if the peak of correlation follows the expected trend: $arg{max}_{t_i}\tau (X_{t_i},Y_{t_i})\le arg{max}_{t_i}\tau (Y_{t_i},Z_{t_i})\le arg{max}_{t_i}\tau (Z_{t_i},W_{t_i})$. In [25], the same experiment has been done with $\tau$ evaluated by UMI and CMI estimators. In this paper, we evaluate $\tau$ using our proposed estimator of hypercontractivity.

The Figure 18 shows the scatter plots pCD3$\zeta$-pSLP76-pERK-pS6 chain at different time points after TCR activation. The data comes from CD4+ naïve T lymphocytes from B6 mice with CD3, CD28, and CD4 cross-linking. Each row represents a pair of data in the chain, and each column stands for a time point after TCR activation. Estimate of hypercontractivity is shown below the scatter plot for each pair of data and each time point and we highlight the time point where each pair of data is maximally correlated. We can see that the peak of the correlation of pCD3$\zeta$-pSLP76, pSLP76-pERK and pERK-pS6 appears at 0.5 min, 1 min and 2 min respectively, hence the pathway is correctly identified.

In Figure 19, the similar plots was shown for T-cells exposed with an antigen. Similarly, hypercontractivity is able to capture the trend.

We subsample the raw data from [7] to evaluate the ability to find the trend from smaller samples. Precisely, given a resampling rate $\gamma \in (0,1]$, we randomly select a subset of indices $S_i\subseteq \left[n_i\right]$ with $\mathrm{card}\left(S_i\right)=\lceil \gamma n_i\rceil$, compute $\tau (X_{t_i},Y_{t_i})$, $\tau (Y_{t_i},Z_{t_i})$ and $\tau (Z_{t_i},W_{t_i})$ from subsamples ${\{X_{t_i}^{\left(j\right)},Y_{t_i}^{\left(j\right)},Z_{t_i}^{\left(j\right)},W_{t_i}^{\left(j\right)}\}}_{j\in S_i}$, and determine whether we can recover the trend successfully, i.e., whether $arg{max}_{t_i}\tau (X_{t_i},Y_{t_i})\le arg{max}_{t_i}\tau (Y_{t_i},Z_{t_i})\le arg{max}_{t_i}\tau (Z_{t_i},W_{t_i})$. We repeat the experiment several times with independent subsamples and compute the probability of successfully recovering the trend. Figure 20 illustrates that when the entire dataset is available, all methods are able to recover the trend correctly. When only fewer samples are available, hypercontractivity improves upon other competing measures in recovering the hidden chronological order of interactions of the pathway. For completeness, we run datasets for both regular T-cells (shown in left figure) and T-cells exposed with an antigen (shown right figure), for which we expect distinct biological trends. Hypercontractivity method can capture the trend for both datasets correctly and sample-efficiently.

5. Proofs

In this section, we provide proofs for our main results and technical lemmas.

5.1. Proof of Proposition 1

Let $S_F(X,Y)=F(\sqrt{s(X;Y)},\sqrt{s(Y;X)})$ for F satisfying conditions in Proposition 1. We show that $S_F(X,Y)$ satisfies all Rényi’s axioms, i.e., Axioms 1–5 and 6’ and 7’.

1.

$S_F(X,Y)$ is defined for any pair of non-constant random variables $X,Y$ because $s(X;Y)\in [0,1]$ and $s(Y;X)\in [0,1]$ are defined for any random variables X, Y by Theorem 1.

2.

$S_F(X,Y)\in [0,1]$ because the output of a function F is in $[0,1]$ by the condition on F.

3.

If X and Y are statistically independent, $s(X;Y)=s(Y;X)=0$. By the condition on F, it follows that $S_F(X,Y)=0$. If $S_F(X,Y)=0$, by the condition on F, $s(X;Y)s(Y;X)=0$, which implies that X and Y are statistically independent.

4.

$S_F(f\left(X\right),g\left(Y\right))=S_F(X,Y)$ for any bijective Borel-measurable functions $f,g$ because $\sqrt{s\left(f\right(X);g(Y\left)\right)}$ = $\sqrt{s(X;Y)}$ and $\sqrt{s\left(g\right(Y);f(X\left)\right)}=\sqrt{s(Y;X)}$ by Theorem 1.

5.

For $(X,Y)\sim \mathcal{N}(\mu ,\Sigma )$ with Pearson correlation $\rho$, $s(X;Y)=s(Y;X)={\rho }^2$. Hence, $S_F(X,Y)=F\left(\right|\rho |,|\rho \left|\right)=\left|\rho \right|$.

6’

If $Y=f\left(X\right)$ for a non-constant function f, it follows that $I\left(f\right(X);f(X\left)\right)=I\left(f\right(X);X)$ because if $f\left(X\right)$ is discrete, $I\left(f\right(X);f(X\left)\right)=I\left(f\right(X);X)=H\left(f\right(X\left)\right)$ and otherwise, $I\left(f\right(X);f(X\left)\right)=I\left(f\right(X);X)=\infty$. Hence

$$s(X;f\left(X\right))=\underset{U-X-f\left(X\right)}{sup}I(U;f\left(X\right))/I(U;X)=I(f\left(X\right);f\left(X\right))/I(f\left(X\right);X)=1.$$

Similarly, $s(f\left(X\right);X)={sup}_{U-f\left(X\right)-X}I(U;X)/I(U;f\left(X\right))=1$. Hence, $S_F(X;f\left(X\right))=F(1,1)=1$. Likewise, we can show that $S_F(X;Y)=1$ if $X=g\left(Y\right)$.

7’

$S_F(X,Y)=S_F(Y,X)$ because $F(x,y)=F(y,x)$.

5.2. Proof of Theorem 1

We show that $s(X;Y)$ satisfies Axioms 1–6 in Section 2.

• For any non-constant random variable X, $\exists U$ s.t. $I(U;X)>0$. Hence, $s(X;Y)$ is defined for any pair of non-constant random variables X and Y.
• Since mutual information is non-negative, $s(X;Y)\ge 0$. By data processing inequality, for any $U-X-Y$, $I(U;X)\le I(U;Y)$. Hence, $s(X;Y)\le 1$.
• If X and Y are independent, for any U, $I(U;Y)\le I(X;Y)=0$. Hence, $s(X;Y)=0$. If X and Y are dependent, $I(X;Y)>0$, which implies that $s(X;Y)\ge I(X;Y)/H\left(X\right)>0$.
• For any bijective functions $f,g$,

  $$I(U;g(Y\left)\right)=I(U;g(Y),Y)=I(U;Y)+I(U;g(Y\left)\right|Y)=I(U;Y).$$
  Similarly, $I(U;f(X\left)\right)=I(U;X)$. Hence,

  $$\begin{array}{cc}\hfill s\left(f\right(X);g(Y\left)\right)& =\underset{U:U-f\left(X\right)-g\left(Y\right),I(U;f(X\left)\right)>0}{sup}\frac{I(U;g(Y\left)\right)}{I(U;f(X\left)\right)}\hfill \\ & =\underset{U:U-X-f\left(X\right)-g\left(Y\right)-Y,I(U;X)>0}{sup}\frac{I(U;Y)}{I(U;X)}\hfill \\ & =s(X;Y).\hfill \end{array}$$
• By Theorem 3.1 in [33], for $(X,Y)$ jointly Gaussian with correlation coefficient $\rho$,

  $$\underset{U:U-X-Y}{min}\left(I(U;X)-\beta I(U;Y)\right)=0$$

  for $\beta \le 1/{\rho }^2$. Equivalently,

  $$\underset{U:U-X-Y}{max}\left(I(U;Y)-{\rho }^{2}I(U;X)\right)=0,$$

  which implies that $s(X;Y)\le {\rho }^2$. To show that $s(X;Y)\ge {\rho }^2$, let $U_Z=X+Z$ for $Z\sim (0,{\sigma }_1^2)$. Consider

  $$\begin{array}{cc}\hfill s(X;Y)& \ge \underset{{\sigma }_1^2\to \infty }{lim}\frac{I(U_Z;Y)}{I(U_Z;X)}\hfill \\ & =\underset{{\sigma }_1^2\to \infty }{lim}\frac{log\left(\frac{({\sigma }_X^2+{\sigma }_1^2){\sigma }_Y^2}{({\sigma }_X^2+{\sigma }_1^2){\sigma }_Y^2-{\rho }^2{\sigma }_X^2{\sigma }_Y^2}\right)}{log\left(1+\frac{{\sigma }_X^2}{{\sigma }_1^2}\right)}\hfill \\ & =\underset{{\sigma }_1^2\to \infty }{lim}\frac{{\rho }^2{\sigma }_X^2{\sigma }_Y^2/\left(({\sigma }_X^2+{\sigma }_1^2){\sigma }_Y^2-{\rho }^2{\sigma }_X^2{\sigma }_Y^2\right)}{{\sigma }_X^2/{\sigma }_1^2}\hfill \\ & ={\rho }^2.\hfill \end{array}$$
  Hence, $s(X;Y)={\rho }^2$. An alternative proof is provided in [24].
• To prove that $s(X;Y)$ satisfies Axiom 6, we first show the following lemma.

Lemma 1.

Consider a pair of random variables $(X,Y)\in \mathcal{X}\times \mathcal{Y}$. The hypercontractivity $s(X;Y)$ is lower bounded by

$$\begin{array}{c}\hfill s(X;Y)\ge \frac{I(U;Y|X\in {\mathcal{X}}_r)}{H\left(\alpha \right)/\alpha +I(U;X|X\in {\mathcal{X}}_r)}\end{array}$$

(12)

for any ${\mathcal{X}}_r$ such that ${\mathcal{X}}_r\subseteq \mathcal{X}$ for $\mathsf{P}\{X\in {\mathcal{X}}_r\}=:\alpha >0$.

Proof. 

Let

$$\begin{array}{c}\hfill U_s=\left\{\begin{array}{cc}U\sim p\left(u\right|x)\hfill & \mathrm{if}X\in {\mathcal{X}}_r,\hfill \\ \varnothing \hfill & \mathrm{otherwise}.\hfill \end{array}\right.\end{array}$$

(13)

Let $S={\mathbb{I}}_{\{U_s=\varnothing \}}={\mathbb{I}}_{\{X\in {\mathcal{X}}_r\}}$. Note that $S-U_s-X-Y$ holds, and that S is a deterministic function of X. Hence,

$$\begin{array}{cc}\hfill I(U_s;X)& =I(U_s,S;X)\hfill \\ & =I(S;X)+I(U_s;X|S)\hfill \\ & =H\left(\alpha \right)+\alpha I(U;X|X\in {\mathcal{X}}_r).\hfill \end{array}$$

(14)

Consider

$$\begin{array}{cc}\hfill I(U_s;Y)& =I(U_s,S;Y)\hfill \\ & =I(S;Y)+I(U_s;Y|S)\hfill \\ & \ge \alpha I(U;Y|X\in {\mathcal{X}}_r).\hfill \end{array}$$

(15)

The proof is completed by combining (14) and (15). ☐

Assume that $Y=f\left(X\right)$ for $X\in {\mathcal{X}}_r$. Considering $U=f\left(X\right)$ in (13) in Lemma 1, we obtain the following lower bound:

$$s(X;Y)\ge \frac{I(f\left(X\right);f\left(X\right)|X\in {\mathcal{X}}_r)}{H\left(\alpha \right)/\alpha +I(f\left(X\right);X|X\in {\mathcal{X}}_r)}.$$

For any continuous random variable X and a non-constant continuous function f, $I(f\left(X\right);f\left(X\right)|X\in {\mathcal{X}}_r)=I(f\left(X\right);X|X\in {\mathcal{X}}_r)=\infty$, which implies that $s(X;Y)=1$.

5.3. Proof of Theorem 2

We first prove that $\mathrm{mCor}(X,Y)=\sqrt{\alpha }\mathrm{mCor}(X_r,Y)$ in (2). Let $S={\mathbb{I}}_{\{X\in {\mathcal{X}}_r\}}$ be the indicator for whether $X\in {\mathcal{X}}_r$ or not. Consider

$$\begin{array}{cc}\hfill \mathrm{mCor}(X;Y)& =\underset{\begin{array}{c}f,g\\ :\mathsf{E}[f(X)]=\mathsf{E}[g(Y)]=0,\\ \mathsf{E}[f^2\left(X\right)]\le 1,\mathsf{E}[g^2\left(Y\right)]\le 1\end{array}}{max}\mathsf{E}[f\left(X\right)g\left(Y\right)]\hfill \\ & =\underset{\begin{array}{c}f,g\\ :\mathsf{E}[f(X)]=\mathsf{E}[g(Y)]=0,\\ \mathsf{E}[f^2\left(X\right)]\le 1,\mathsf{E}[g^2\left(Y\right)]\le 1\end{array}}{max}{\mathsf{E}}_S[\mathsf{E}[f\left(X\right)g\left(Y\right)|S]]\hfill \\ & =\underset{\begin{array}{c}f,g\\ :\mathsf{E}[f(X)]=\mathsf{E}[g(Y)]=0,\\ \mathsf{E}[f^2\left(X\right)]\le 1,\mathsf{E}[g^2\left(Y\right)]\le 1\end{array}}{max}\left(\alpha \mathsf{E}[f\left(X\right)g\left(Y\right)|X\in {\mathcal{X}}_r]+\overline{\alpha }\mathsf{E}[f\left(X\right)g\left(Y\right)|X\in {\mathcal{X}}_d]\right)\hfill \\ & =\underset{\begin{array}{c}f,g\\ :\mathsf{E}[f(X)]=\mathsf{E}[g(Y)]=0,\\ \mathsf{E}[f^2\left(X\right)]\le 1,\mathsf{E}[g^2\left(Y\right)]\le 1\end{array}}{max}\left(\alpha \mathsf{E}[f\left(X\right)g\left(Y\right)|X\in {\mathcal{X}}_r]+\overline{\alpha }\mathsf{E}[f\left(X\right)|X\in {\mathcal{X}}_d]\mathsf{E}[g\left(Y\right)|X\in {\mathcal{X}}_d]\right)\hfill \\ & \stackrel{\left(a\right)}{=}\alpha \underset{\begin{array}{c}f,g\\ :\mathsf{E}[f(X)]=\mathsf{E}[g(Y)]=0,\\ \mathsf{E}[f^2\left(X\right)]\le 1,\mathsf{E}[g^2\left(Y\right)]\le 1\end{array}}{max}\mathsf{E}[f\left(X\right)g\left(Y\right)|X\in {\mathcal{X}}_r]\hfill \\ & \stackrel{\left(b\right)}{=}\sqrt{\alpha }\mathrm{mCor}(X_r,Y).\hfill \end{array}$$

Step $\left(a\right)$ holds since $\mathsf{E}\left[g\left(Y\right)\right|X\in {\mathcal{X}}_r]=\mathsf{E}\left[g\left(Y\right)\right|X\in {\mathcal{X}}_d]$ from the assumption that marginal distributions are equal, and that $\mathsf{E}\left[g\left(Y\right)\right]=\alpha \mathsf{E}\left[g\left(Y\right)\right|X\in {\mathcal{X}}_r]+\overline{\alpha }\mathsf{E}\left[g\left(Y\right)\right|X\in {\mathcal{X}}_d]$. To show step $\left(b\right)$, let $c=\mathsf{E}\left[f\left(X\right)\right|X\in {\mathcal{X}}_d]$ and note that

$$\begin{array}{cc}\hfill \alpha \mathsf{E}\left[f\left(X\right)\right|X\in {\mathcal{X}}_r]& =-\overline{\alpha }c,\hfill \\ \hfill \alpha \mathsf{E}\left[f^2\left(X\right)\right|X\in {\mathcal{X}}_r]& =\mathsf{E}\left[f^2\left(X\right)\right]-\overline{\alpha }\mathsf{E}\left[f^2\left(X\right)\right|X\in {\mathcal{X}}_d]\hfill \\ & \le 1-\overline{\alpha }{c}^2,\hfill \\ \hfill \mathsf{E}\left[g\left(Y\right)\right|X\in {\mathcal{X}}_r]& =0.\hfill \end{array}$$

Hence,

$$\begin{array}{cc}\hfill \underset{\begin{array}{c}f,g\\ :\mathsf{E}\left[f\right(X\left)\right]=\mathsf{E}\left[g\right(Y\left)\right]=0,\\ \mathsf{E}\left[f^2\left(X\right)\right]\le 1,\mathsf{E}\left[g^2\left(Y\right)\right]\le 1\end{array}}{max}\mathsf{E}\left[f\left(X\right)g\left(Y\right)\right|X\in {\mathcal{X}}_r]& =\underset{\begin{array}{c}{f}_r,g\\ :\mathsf{E}\left[f_r\left(X\right)\right]=-\overline{\alpha }c/\alpha ,\mathsf{E}\left[g\left(Y\right)\right]=0,\\ \mathsf{E}\left[f_r^2\left(X\right)\right]\le (1-\overline{\alpha }{c}^2)/\alpha ,\mathsf{E}\left[g^2\left(Y\right)\right]\le 1\end{array}}{max}\mathsf{E}\left[f_r\left(X\right)g\left(Y\right)\right]\hfill \\ & =\underset{\begin{array}{c}{f}_{rc},g\\ :\mathsf{E}\left[f_{rc}\left(X\right)\right]=0,\mathsf{E}\left[g\left(Y\right)\right]=0,\\ \mathsf{E}\left[f_{rc}^2\left(X\right)\right]\le (\alpha -\overline{\alpha }{c}^2)/{\alpha }^2,\mathsf{E}\left[g^2\left(Y\right)\right]\le 1\end{array}}{max}\mathsf{E}[\left(f_{rc}\left(X\right)g\left(Y\right)\right]\hfill \\ & =\underset{\begin{array}{c}{f}_{rc},g\\ :\mathsf{E}\left[f_{rc}\left(X\right)\right]=0,\mathsf{E}\left[g\left(Y\right)\right]=0,\\ \mathsf{E}\left[f_{rc}^2\left(X\right)\right]\le 1/\alpha ,\mathsf{E}\left[g^2\left(Y\right)\right]\le 1\end{array}}{max}\mathsf{E}\left[f_{rc}\left(X\right)g\left(Y\right)\right]\hfill \\ & =\underset{\begin{array}{c}{f}_{rca},g\\ :\mathsf{E}\left[f_{rca}\left(X\right)\right]=0,\mathsf{E}\left[g\left(Y\right)\right]=0,\\ \mathsf{E}\left[f_{rca}^2\left(X\right)\right]\le 1,\mathsf{E}\left[g^2\left(Y\right)\right]\le 1\end{array}}{max}\frac{1}{\sqrt{\alpha }}\mathsf{E}\left[f_{rca}\left(X\right)g\left(Y\right)\right]\hfill \\ & =\frac{\mathrm{mCor}(X_r,Y)}{\sqrt{\alpha }},\hfill \end{array}$$

where $f_r\left(X\right)$, $f_{rc}\left(X\right)=f_r\left(X\right)+\overline{\alpha }c/\alpha$, and $f_{rca}\left(X\right)=\sqrt{\alpha }{f}_{rc}\left(X\right)$ are functions defined only for $X\in {\mathcal{X}}_r$.

We next show $\mathrm{dCor}(X,Y)=\alpha \mathrm{dCor}(X_r,Y)$ in (3). Let

$$h_X\left(s\right)=\mathsf{E}[e^{isX}],h_Y\left(t\right)=\mathsf{E}[e^{itY}],h_{XY}(s,t)=\mathsf{E}[e^{i(sX+tY)}].$$

Note that

$$\begin{array}{cc}\hfill h_{XY}(s,t)& =\mathsf{E}[e^{i(sX+tY)}]\hfill \\ & =\alpha \mathsf{E}[e^{i(sX+tY)}|X\in {\mathcal{X}}_r]+\overline{\alpha }\mathsf{E}[e^{isX}|X\in {\mathcal{X}}_d]\mathsf{E}[e^{itY}|X\in {\mathcal{X}}_d]\hfill \\ & =\alpha \mathsf{E}[e^{i(sX+tY)}|X\in {\mathcal{X}}_r]+\overline{\alpha }\mathsf{E}[e^{isX}|X\in {\mathcal{X}}_d]\mathsf{E}[e^{itY}],\hfill \end{array}$$

(16)

and

$$\begin{array}{c}\hfill h_X\left(s\right)=\mathsf{E}[e^{isX}]=\alpha \mathsf{E}[e^{isX}|X\in {\mathcal{X}}_r]+\overline{\alpha }\mathsf{E}[e^{isX}|X\in {\mathcal{X}}_d].\end{array}$$

(17)

By combining (16) and (17),

$$\begin{array}{cc}\hfill h_{XY}(s,t)-h_X\left(s\right)h_Y\left(t\right)& =\alpha \mathsf{E}[e^{i(sX+tY)}|X\in {\mathcal{X}}_r]-\alpha \mathsf{E}[e^{isX}|X\in {\mathcal{X}}_r]\mathsf{E}[e^{itY}]\hfill \\ & =\alpha \mathsf{E}[e^{i(sX+tY)}|X\in {\mathcal{X}}_r]-\alpha \mathsf{E}[e^{isX}|X\in {\mathcal{X}}_r]\mathsf{E}[e^{itY}|X\in {\mathcal{X}}_r]\hfill \\ & =\alpha \mathrm{dCor}(X_r,Y).\hfill \end{array}$$

Finally, we show that $\mathrm{MIC}(X,Y)\le \alpha \mathrm{MIC}(X_r,Y)$ in (4).

Let $X_Q\left(X\right)\in {\mathcal{X}}_Q\left(X\right)$ and $Y_Q\left(Y\right)\in {\mathcal{Y}}_Q\left(Y\right)$ denote a quantization of X and Y, respectively. Consider

$$\begin{array}{cc}\hfill \mathrm{MIC}(X,Y)& =\underset{X_Q\left(X\right),Y_Q\left(Y\right)}{max}\frac{I(X_Q;Y_Q)}{logmin\left\{\right|{\mathcal{X}}_Q|,|{\mathcal{Y}}_Q\left|\right\}}\hfill \\ & \le \underset{X_Q\left(X\right),Y_Q\left(Y\right)}{max}\frac{I({\mathbb{I}}_{X\in {\mathcal{X}}_r},X_Q;Y_Q)}{logmin\left\{\right|{\mathcal{X}}_Q|,|{\mathcal{Y}}_Q\left|\right\}}\hfill \\ & \stackrel{\left(a\right)}{=}\alpha \underset{X_Q\left(X\right),Y_Q\left(Y\right)}{max}\frac{I(X_Q;Y_Q|X\in {\mathcal{X}}_r)}{logmin\left\{\right|{\mathcal{X}}_Q|,|{\mathcal{Y}}_Q\left|\right\}}\hfill \\ & \le \alpha \underset{X_Q\left(X_r\right),Y_Q\left(Y\right)}{max}\frac{I(X_Q;Y_Q|X\in {\mathcal{X}}_r)}{logmin\left\{\right|{\mathcal{X}}_Q\left(X_r\right)|,|{\mathcal{Y}}_Q\left|\right\}}\hfill \\ & =\alpha \mathrm{MIC}(X_r,Y),\hfill \end{array}$$

where step $\left(a\right)$ holds because ${\mathbb{I}}_{X\in {\mathcal{X}}_r}⫫Y$ implies ${\mathbb{I}}_{X\in {\mathcal{X}}_r}⫫Y_Q$ and $X⫫Y$ in $X\in {\mathcal{X}}_d$ implies $X_Q⫫Y_Q$ in $X\in {\mathcal{X}}_d$.

5.4. Proof of Proposition 2

The inverse hypercontractivity $s(Y;X)$ is defined as

$$s(Y;X)=\underset{U-Y-X}{sup}\frac{I(U;X)}{I(U;Y)}.$$

Let ${\mathbb{I}}_r={\mathbb{I}}_{\{X\in {\mathcal{X}}_r\}}$. Since the marginal distribution of Y given $\{X\in {\mathcal{X}}_r\}$ and the one given $\{X\notin {\mathcal{X}}_r\}$ are equivalent, Y and ${\mathbb{I}}_r$ are independent, i.e., $I(Y;{\mathbb{I}}_r)=0$. For any U such that Markov chain $U-Y-X$ holds, the Markov chain $U-Y-X-{\mathbb{I}}_r$ holds. Hence, $I(U;{\mathbb{I}}_r)=0$. Hence, for any $U-Y-X$, consider

$$\begin{array}{cc}\hfill I(U;X)& =I(U;X,{\mathbb{I}}_r)\hfill \\ & =I(U;X|{\mathbb{I}}_r)\hfill \\ & =(1-\alpha )I(U;X|{\mathbb{I}}_r=0)+\alpha I(U;X|{\mathbb{I}}_r=1)\hfill \\ & \stackrel{\left(a\right)}{=}\alpha I(U;X|{\mathbb{I}}_r=1)\hfill \end{array}$$

Step $\left(a\right)$ holds because $Y⫫X$ given ${\mathbb{I}}_r=0$. Consider

$$\begin{array}{cc}\hfill I(U;Y)& \stackrel{\left(a\right)}{=}I(U;Y,{\mathbb{I}}_r)\hfill \\ & =I(U;Y|{\mathbb{I}}_r)+I(U;{\mathbb{I}}_r)\hfill \\ & \stackrel{\left(b\right)}{=}I(U;Y|{\mathbb{I}}_r)\hfill \\ & =\alpha I(U;Y|{\mathbb{I}}_r=1)+(1-\alpha )I(U;Y|{\mathbb{I}}_r=0)\hfill \\ & \stackrel{\left(c\right)}{=}I(U;Y|{\mathbb{I}}_r=1),\hfill \end{array}$$

where step $\left(a\right)$ folllows since $U-Y-{\mathbb{I}}_r$. Step $\left(b\right)$ follows from $I(U;{\mathbb{I}}_r)=0$. Step $\left(c\right)$ holds since $H\left(U\right|{\mathbb{I}}_r=1)=H\left(U\right|{\mathbb{I}}_r=0)$ and $U-Y-{\mathbb{I}}_r$. Therefore, for any $U-Y-X$, it follows that

$$s(Y;X)=\underset{U-Y-X}{sup}\frac{\alpha I(U;X|I_r=1)}{I(U;Y|I_r=1)}=\alpha s(Y;X_r).$$

5.5. Noisy Rare Correlation in Example 1

Let

$$U=X+Z,Z\sim \mathcal{N}(0,{\sigma }_1^2).$$

Consider

$$\underset{U:U-X-Y,I(U;X)>0}{sup}\frac{I(U;Y)}{I(U;X)}\ge \underset{{\sigma }_1^2\ge 0}{sup}\frac{log\frac{(1+{\sigma }_1^2)}{(1+{\sigma }_1^2)-{\rho }^2}}{H\left(\alpha \right)/\alpha +log(1+1/{\sigma }_1^2)}.$$

The inequality (7) follows by choosing ${\sigma }_1^2=(1-{\rho }^2)/{\rho }^2$.

5.6. Noisy Discrete Rare Correlation in Example 3

The inequality (8) follows by choosing $r\left(x\right)={\mathbb{I}}_{\{X=1\}}$ in (10). To show (9), we show that

$$\begin{array}{c}\hfill \mathrm{mCor}(X_r,Y)=1-\frac{k}{k-1}ϵ.\end{array}$$

(18)

The rest follows because $\mathrm{mCor}(X;Y)=\sqrt{\alpha }\mathrm{mCor}(X_r,Y)$ by Proposition 2. To show (18), we use the fact that maximal correlation is the second eigenvalue of $Q=P_X^{-1/2}{P}_{XY}{P}_Y^{-1/2}$ (see [40] for a detailed proof). We can easily show that

$$Q=\left(1-\frac{k}{k-1}ϵ\right)I+\frac{ϵ}{k-1}{11}^T.$$

First singular vector of Q is $P_X^{1/2}=1/\sqrt{k}$. Second singular vector $u_2$ is orthogonal to $1/\sqrt{k}$. The Equation (18) follows because $\mathrm{mCor}(X_r;Y)=u_2^{T}Q{u}_2=u_2^T(1-kϵ/(k-1))u_2$.

5.7. Proof of Proposition 4

We first prove the second part of proposition: the hypercontractivity coefficient $\sqrt{s(X;Y)}$ satisfies Axioms 1–4, 5’, and 6. It follows immediately from Theorem 1 that $\sqrt{s(X;Y)}$ satisfies Axioms 1–4 and 6 because in the proof of Theorem 1—1–4 and 6, the same argument holds for random vectors X and Y. We can show that that $\sqrt{s(X;Y)}$ satisfies Axiom 5’ using results from [33]. In [33], it is shown that that as we increase $\beta$ starting from zero, $min\left\{I\right(U;X)-\beta I(U;Y\left)\right\}$ departs form zero at $\beta =1/\parallel {\Sigma }_X^{-1/2}{\Sigma }_{XY}{\Sigma }_Y^{-1/2}{\parallel }^2$ for jointly Gaussian random vectors X and Y. This result implies that $\sqrt{s(X;Y)}=\parallel {\Sigma }_X^{-1/2}{\Sigma }_{XY}{\Sigma }_Y^{-1/2}\parallel$.

To show that maximal correlation of two random vectors satisfies Axioms 1–4, 6’, and 7’, we can follow the same arguments for showing that maximal correlation for two random variables satisfies Axioms 1–4, 6’, and 7’ by [4]. To show that maximal correlation satisfies Axiom 5’, note that maximal correlation is upper bounded by hypercontractivity as shown in Remark 1 in Section 2.3: hence mCor$(X;Y)\le \parallel {\Sigma }_X^{-1/2}{\Sigma }_{XY}{\Sigma }_Y^{-1/2}\parallel$ for a jointly Gaussian $X,Y$. Equality holds because mCor$(X,Y)$ is lower bounded by its canonical correlation, which is $\parallel {\Sigma }_X^{-1/2}{\Sigma }_{XY}{\Sigma }_Y^{-1/2}\parallel$ for jointly Gaussian random vectors $(X,Y)$ [33].

5.8. Proof of Theorem 3

We begin with the following assumptions:

(a)

There exist finite constants $C_1<C_1^{\prime }<C_2^{\prime }<C_2$ such that the ratio of the optimal $r_x^{\ast }$ and the true $p_x$ satisfies $r_x^{\ast }\left(x\right)/p_x\left(x\right)\in [C_1^{\prime },C_2^{\prime }]$ for every $x\in \mathcal{X}$.

(b)

There exist finite constants $C_0^{\prime }>C_0>0$ such that the KL divergence $D(r_x^{\ast }\left|\right|p_x)>C_0^{\prime }$.

With a little abuse of notations, we define $s\left(r_x\right)=D(r_y\left|\right|p_y)/D(r_x\left|\right|p_x)$ and $\widehat{s}\left(\mathbf{w}\right)={\mathbf{w}}^T\mathbf{A}log\left({\mathbf{A}}^T\mathbf{w}\right)/{\mathbf{w}}^{T}log\mathbf{w}$. Therefore, $s(X;Y)={max}_{r_x\in R}s\left(r_x\right)$ and ${\widehat{s}}_{\Delta }(X;Y)={max}_{\mathbf{w}\in T_{\Delta }}\widehat{s}\left(\mathbf{w}\right)$. Here R is the probability simplex over all $r_x$. We want to bound the error $|{\widehat{s}}_{\Delta }(X;Y)-s(X;Y)|$. First, consider the quantity:

$$\begin{array}{ccc}\hfill s_{\Delta }(X;Y)& \equiv & \underset{r_x\in T_{\Delta }\left(R\right)}{max}s\left(r_x\right),\hfill \end{array}$$

(19)

where the constraint set $T_{\Delta }\left(R\right)$ is defined as:

$$\begin{array}{c}\hfill T_{\Delta }\left(R\right)=\{r_x\in {\mathbb{R}}^{\left|\mathcal{X}\right|}:[(r_x\left(x\right)/p_x\left(x\right))]\in T_{\Delta }\mathrm{and}\sum _{x\in \mathcal{X}}{r}_x\left(x\right)\in [1-\left|\mathcal{X}\right|\Delta ,1+\left|\mathcal{X}\right|\Delta ]\}\end{array}$$

(20)

Now we rewrite the error term as

$$\begin{array}{ccc}\hfill |{\widehat{s}}_{\Delta }(X;Y)-s(X;Y)|& \le & |s_{\Delta }(X;Y)-s(X;Y)|+|{\widehat{s}}_{\Delta }(X;Y)-s_{\Delta }(X;Y)|.\hfill \end{array}$$

(21)

The first error comes from quantization. Let $r^{\ast }$ be the maximizer of $s(X;Y)$. By assumption, $r^{\ast }\left(x\right)/p_x\left(x\right)\in [C_1,C_2]$, for all x. Since $T_{\Delta }\left(R\right)$ is a quantization of the simplex R, so there exists an $r_0\in T_{\Delta }\left(R\right)$ such that $|r_0\left(x\right)-r^{\ast }\left(x\right)|<\Delta$ for all $x\in \mathcal{X}$. Now we will bound the difference between $s\left(r_0\right)$ and $s\left(r^{\ast }\right)$ by the following lemma:

Lemma 2.

If $r\left(x\right)/p\left(x\right)\in [C_1,C_2]$ and $r^{\prime }\left(x\right)/p\left(x\right)\in [C_1,C_2]$ for all $x\in \mathcal{X}$, and $D(r_x\left|\right|p_x)>C_0$ and $D(r_x^{\prime }\left|\right|p_x)>C_0$, then

$$\begin{array}{c}\hfill |s\left(r\right)-s\left(r^{\prime }\right)|\le L\underset{x\in \mathcal{X}}{max}|r\left(x\right)-r^{\prime }\left(x\right)|,\end{array}$$

(22)

for some positive constant L.

Next we have:

$$\begin{array}{cc}s(X;Y)\hfill & =s\left(r^{\ast }\right)\le s\left(r_0\right)+L\underset{x\in \mathcal{X}}{max}|r_0\left(x\right)-r^{\ast }\left(x\right)|\hfill \\ & \le \underset{r\in T_{\Delta }\left(R\right)}{max}s\left(r\right)+L\Delta =s_{\Delta }(X;Y)+L\Delta .\hfill \end{array}$$

(23)

Similarly, let $r^{\ast \ast }$ be the maximizer of $s_{\Delta }(X;Y)$, we can also find a $r_1\in R$ such that $|r_1\left(x\right)-r^{\ast \ast }\left(x\right)|<\Delta$ for all $x\in \mathcal{X}$. Using Lemma 2 again, we will obtain $s_{\Delta }(X;Y)\le s(X;Y)+L\Delta$. Therefore, the quantization error is bounded by $O(\Delta )$ with probability 1.

Now consider the second term. Upper bound on the second term relies on the convergence of estimation of s. We claim that for given $r_x$, the estimator is convergent in probability, i.e.,

Lemma 3.

$$\begin{array}{c}\hfill \underset{N\to \infty }{lim}\mathcal{P}\left(|\widehat{s}\left({\mathbf{w}}_r\right)-s\left(r_x\right)|>\epsilon \right)=0.\end{array}$$

(24)

Here ${\mathbf{w}}_r\left(x\right)=r_x\left(x\right)/p_x\left(x\right)$. Since the set $T_{\Delta }\left(R\right)$ is finite, by union bound, we have:

$$\begin{array}{c}\underset{N\to \infty }{lim}\mathcal{P}\left(\forall r\in T_{\Delta }\left(R\right),|\widehat{s}\left({\mathbf{w}}_r\right)-s\left(r_x\right)|\le \epsilon \right)\hfill \\ \ge 1-|T_{\Delta }\left(R\right)|\underset{N\to \infty }{lim}\mathcal{P}\left(|\widehat{s}\left({\mathbf{w}}_r\right)-s\left(r_x\right)|\le \epsilon \right)=1.\hfill \end{array}$$

(25)

Also, by the strong law of large numbers, we have that

$$\begin{array}{c}\hfill \underset{N\to \infty }{lim}\mathcal{P}\left(\forall x\in \mathcal{X},|p_x\left(x\right)-\frac{n_x}{n}|<\frac{\Delta }{C_2\left|\mathcal{X}\right|}\right)=1.\end{array}$$

(26)

where $n_x=\mathrm{card}\{i\in [n]:x_i=x\}$. We claim that if the events inside the probability in (25) and (26) happen simultaneously, then $|{\widehat{s}}_{\Delta }(X;Y)-s_{\Delta }(X;Y)|<\epsilon +O(\Delta )$, which implies the desired claim.

Let ${\mathbf{w}}^{\ast }=arg{max}_{\mathbf{w}\in T_{\Delta }}\widehat{s}\left(\mathbf{w}\right)$. Define $r_2\left(x\right)={\mathbf{w}}^{\ast }\left(x\right)p_x\left(x\right)$. Since $[r_2\left(x\right)/p_x\left(x\right)]\in T_{\Delta }$ for all x and

$$\begin{array}{ccc}\hfill |\sum _{x\in \mathcal{X}}{r}_2\left(x\right)-1|& =& \left|\sum _{x\in \mathcal{X}}{\mathbf{w}}_x^{\ast }(p_x\left(x\right)-\frac{n_x}{n})\right|+\frac{\Delta \left|\mathcal{X}\right|}{2}\hfill \\ & \le & \left|\mathcal{X}\right|\left(\frac{\Delta }{2}+C_2\underset{x\in \mathcal{X}}{max}|p_x\left(x\right)-\frac{n_x}{n}|\right)\hfill \\ & \le & (\left|\mathcal{X}\right|/2+1)\Delta .\hfill \end{array}$$

(27)

Therefore, $r_2\in T_{\Delta }\left(R\right)$, so

$$\begin{array}{ccc}\hfill {\widehat{s}}_{\Delta }(X;Y)& =& \widehat{s}\left({\mathbf{w}}^{\ast }\right)\le s\left(r_2\right)+\epsilon \le s_{\Delta }(X;Y)+\epsilon .\hfill \end{array}$$

(28)

On the other hand, consider $r^{\ast \ast }=arg{max}_{r_x\in T_{\Delta }\left(R\right)}s\left(r_x\right)$ again, and define ${\mathbf{w}}_0\left(x\right)=r^{\ast \ast }\left(x\right)/p_x\left(x\right)$. We know that ${\mathbf{w}}_0\in T_{\Delta }^{\left|\mathcal{X}\right|}$ but not necessarily ${\sum }_{i=1}^n{\mathbf{w}}_0\left(x_i\right)=n$. However, we claim that the sum is closed to n as follows:

$$\begin{array}{cc}\hfill |\sum _{i=1}^n{\mathbf{w}}_0\left(x_i\right)-n|& =|\sum _{x\in \mathcal{X}}\frac{n_x{r}^{\ast \ast }\left(x\right)}{p_x\left(x\right)}-n|\hfill \\ & \le n\underset{x\in \mathcal{X}}{max}\left\{\frac{r^{\ast \ast }\left(x\right)}{p_x\left(x\right)}|\frac{n_x}{n}-p_x\left(x\right)|\right\}\hfill \\ & \le n{C}_2\frac{\Delta }{C_2\left|\mathcal{X}\right|}<n\Delta \hfill \end{array}$$

(29)

so we can find a ${\mathbf{w}}_1\in T_{\Delta }\left(R\right)$ such that $|{\mathbf{w}}_1\left(x\right)-{\mathbf{w}}_0\left(x\right)|\le \Delta$ for all x. Let $r_4\left(x\right)={\mathbf{w}}_1\left(x\right)p_x\left(x\right)$, similar as (27), we know that $r_4\in T_{\Delta }\left(R\right)$. Moreover, $|r_4\left(x\right)-r^{\ast \ast }\left(x\right)|\le p_x\left(x\right)|{\mathbf{w}}_1\left(x\right)-{\mathbf{w}}_0\left(x\right)|\le \Delta$ for all x. Then we have

$$\begin{array}{cc}\hfill s_{\Delta }(X;Y)& =s\left(r^{\ast \ast }\right)\le s\left(r_4\right)+L\underset{x\in \mathcal{X}}{max}|r^{\ast \ast }\left(x\right)-r_4\left(x\right)|\hfill \\ & \le \widehat{s}\left({\mathbf{w}}_1\right)+\epsilon +L\Delta ={\widehat{s}}_{\Delta }(X;Y)+\epsilon +L\Delta .\hfill \end{array}$$

(30)

We conclude that $|{\widehat{s}}_{\Delta }(X;Y)-s_{\Delta }(X;Y)|<\epsilon +O(\Delta )$; thus our proof is complete.

5.9. Proof of Lemma 2

We will show that for any $x\in \mathcal{X}$, we have $|\partial s\left(r_x\right)/\partial r_x\left(x\right)|\le L/|\mathcal{X}|$ for some L. Therefore,

$$\begin{array}{cc}\hfill |s\left(r\right)-s\left(r^{\prime }\right)|& \le \sum _{x\in \mathcal{X}}|\frac{\partial s\left(r\right)}{\partial r_x\left(x\right)}\left|\right|r_x\left(x\right)-r_x^{\prime }\left(x\right)|\hfill \\ & \le L\underset{x\in \mathcal{X}}{max}|r_x\left(x\right)-r_x^{\prime }\left(x\right)|.\hfill \end{array}$$

(31)

The gradient can be written as

$$\begin{array}{cc}\hfill \frac{\partial s\left(r\right)}{\partial r_x\left(x\right)}& =\frac{\partial }{\partial r_x\left(x\right)}\frac{D\left(r_y\right|\left|p_y\right)}{D\left(r_x\right|\left|p_x\right)}\hfill \\ & =\frac{1}{D^2(r_x\left|\right|p_x)}\left(\frac{\partial D\left(r_y\right|\left|p_y\right)}{\partial r_x\left(x\right)}D(r_x\left|\right|p_x)-\frac{\partial D\left(r_x\right|\left|p_x\right)}{\partial r_x\left(x\right)}D(r_y\left|\right|p_y)\right).\hfill \end{array}$$

(32)

Since

$$\begin{array}{ccc}\hfill \frac{\partial D\left(r_x\right|\left|p_x\right)}{\partial r_x\left(x\right)}& =\hfill & log\frac{r_x\left(x\right)}{p_x\left(x\right)}+1\le max\left\{\right|log{C}_1|,|log{C}_2\left|\right\}+1\hfill \\ \hfill \frac{\partial D\left(r_y\right|\left|p_y\right)}{\partial r_x\left(x\right)}& =\hfill & \int \frac{\partial r_y\left(y\right)}{\partial r_x\left(x\right)}\frac{\partial D\left(r_y\right|\left|p_y\right)}{\partial r_y\left(y\right)}dy\hfill \\ & =\hfill & \int p_{y|x}\left(y\right|x)(log\frac{r_y\left(y\right)}{p_y\left(y\right)}+1)dy\le max\left\{\right|log{C}_1|,|log{C}_2\left|\right\}+1\hfill \end{array}$$

(33)

Therefore, we have

$$\begin{array}{ccc}\hfill |\frac{\partial s\left(r\right)}{\partial r_x\left(x\right)}|& \le \hfill & \left(\max \right\{|log{C}_1|,|log{C}_2\left|\right\}+1)\frac{D(p_x\left|\right|r_x)+D(r_y\left|\right|p_y)}{D^2(r_x\left|\right|p_x)}\hfill \\ & \le \hfill & \frac{2(max\{|log{C}_1|,|log{C}_2\left|\right\}+1)}{D\left(r_x\right|\left|p_x\right)}\hfill \\ & \le \hfill & \frac{2(max\{|log{C}_1|,|log{C}_2\left|\right\}+1)}{C_0}\hfill \end{array}$$

(34)

Since $C_0,C_1,C_2$ are constants and $\left|\mathcal{X}\right|$ is finite, our proof is complete by letting $L=2\left|\mathcal{X}\right|(max\{|log{C}_1|,|log{C}_2\left|\right\}+1)/C_0$.

5.10. Proof of Lemma 3

Note that $\widehat{s}\left({\mathbf{w}}_r\right)={\mathbf{w}}^T\mathbf{A}log\left({\mathbf{A}}^T\mathbf{w}\right)/{\mathbf{w}}^{T}log\mathbf{w}$. Define $\widehat{D}(r_y\left|\right|p_y)={\mathbf{w}}^T\mathbf{A}log\left({\mathbf{A}}^T\mathbf{w}\right)$ and $\widehat{D}(r_x\left|\right|p_x)={\mathbf{w}}^{T}log\mathbf{w}$. We will prove that both $\widehat{D}(r_y\left|\right|p_y)$ converges to $D\left(r_y\right|\left|p_y\right)$ and $\widehat{D}(r_x\left|\right|p_x)$ converges to $D\left(r_x\right|\left|p_x\right)$ in probability. Since $D\left(r_x\right|\left|p_x\right)>0$ and $\widehat{D}(r_x\left|\right|p_x)>0$ with probability 1, we obtain that $\widehat{s}\left({\mathbf{w}}_r\right)$ converges to $D(r_y\left|\right|p_y)/D(r_x\left|\right|p_x)=s\left(r_x\right)$ in probability.

The convergence $\widehat{D}(r_x\left|\right|p_x)$ comes from law of large number. Since $\widehat{D}(r_x\left|\right|p_x)=\frac{1}{n}{\sum }_{i=1}^n\frac{r_x\left(X_i\right)}{p_x\left(X_i\right)}log\frac{r_x\left(X_i\right)}{p_x\left(X_i\right)}$ and $D(r_x\left|\right|p_x)={\mathbb{E}}_{X\sim p_x}\left[\frac{r_x\left(X\right)}{p_x\left(X\right)}log\frac{r_x\left(X\right)}{p_x\left(X\right)}\right]$, the weak law of large number shows the convergence in probability.

For the convergence of $\widehat{D}(r_y\left|\right|p_y)$. Consider the vector $\mathbf{v}={\mathbf{A}}^T\mathbf{w}$, we have

$$\begin{array}{ccc}\hfill v_j& =& \frac{1}{n}\sum _{i=1}^n\frac{p_{xy}(X_i,Y_j)}{p_x\left(X_i\right)p_y\left(Y_j\right)}{w}_i=\frac{1}{n}\sum _{i=1}^n\frac{p_{y|x}\left(Y_j\right|X_i)}{p_y\left(Y_j\right)}\frac{r_x\left(X_i\right)}{p_x\left(X_i\right)}.\hfill \end{array}$$

On the other hand, for fixed $Y_j=y$, we have

$$\begin{array}{c}\hfill \frac{r_y\left(y\right)}{p_y\left(y\right)}=\frac{{\mathbb{E}}_{X\sim p_x}\left[p_{y|x}\left(y\right|X)\frac{r_x\left(X\right)}{p_x\left(X\right)}\right]}{p_y\left(y\right)}={\mathbb{E}}_{X\sim p_x}\left[\frac{p_{y|x}\left(y\right|X)}{p_y\left(y\right)}\frac{r_x\left(X\right)}{p_x\left(X\right)}\right].\end{array}$$

Therefore, by law of large number, we conclude that $v_j$ converges to $\frac{r_y\left(Y_j\right)}{p_y\left(Y_j\right)}$ in probability. Hence, $\widehat{D}(r_y\left|\right|p_y)=\frac{1}{n}{\sum }_{j=1}^n{v}_{j}log{v}_j$ converges to $\frac{1}{n}{\sum }_{j=1}^n\frac{r_y\left(Y_j\right)}{p_y\left(Y_j\right)}log\frac{r_y\left(Y_j\right)}{p_y\left(Y_j\right)}$ in probability. Furthermore, $\frac{1}{n}{\sum }_{j=1}^n\frac{r_y\left(Y_j\right)}{p_y\left(Y_j\right)}log\frac{r_y\left(Y_j\right)}{p_y\left(Y_j\right)}$ converges to $D(r_y\left|\right|p_y)={\mathbb{E}}_{Y\sim p_y}\left[\frac{r_y\left(Y\right)}{p_y\left(Y\right)}log\frac{r_y\left(Y\right)}{p_y\left(Y\right)}\right]$ in probability, by law of large number again. Therefore, we conclude that $\widehat{D}(r_y\left|\right|p_y)$ converges to $D\left(r_y\right|\left|p_y\right)$ in probability.