Interaction screening via canonical correlation

A new canonical correlation (CC) based interaction screening procedure called CCIS is suggested for the ultrahigh dimensional interaction model with a multivariate response. The CCIS procedure consists of two steps: First, it selects a set of candidate features which has a large CC with the squared response; Then it recovers the influential main effects and interactions simultaneously from the reduced interaction model built by the features selected in the first step. CCIS has a ranking statistic with a simple structure, thus it can be calculated very quickly. More importantly, CCIS is powerful to detect the features which have a linear relationship with the response. Both theoretical results and numerical studies are provided to illustrate the effectiveness of CCIS.

Authors and Affiliations

1. College of Liberal Arts and Sciences, National University of Defense Technology, Changsha, China

   Jun Lu & Dan Wang

2. School of Mathematics and Statistics, Shandong University, Weihai, China

   Qinqin Hu

Corresponding author

Correspondence to Dan Wang.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Jun Lu was supported by National Natural Science Foundation of China (No.12001486) and China Postdoctoral Foundation (2020M671782).

Appendix

1.1 Appendix A.1: Some lemmas

Before proving the main result, we introduce some lemmas, which will be used several times in our proof.

Lemma A.1

(Hoeffding inequality) Let \(X_{1}, \ldots , X_{n}\) be a series of independent random variables. Assume that \(P\left( X_{i} \in \right. \) \(\left. \left[ a_{i}, b_{i}\right] \right) =1\) for \(1 \le i \le n,\) where \(a_{i}\) and \(b_{i}\) are constants. Let \({\bar{X}}=n^{-1} \sum _{i=1}^{n} X_{i} .\) Then the following inequality holds

Lemma A.2

Suppose a random variable U satisfying the sub-exponential condition that \(E\exp (sU)<\infty \) for some constant \(s>0\), and \(U_1,\ldots ,U_n\) are i.i.d samples from U. Then, for any \(\varepsilon >0,\) there exist some positive constants \(0<\alpha <1 / 2, c_0\) and t such that

Proof

For any \(M>0\),

where the last inequality holds because of the hoeffding inequality and the fact \(P\left( \left| U_i\right| \ge M\right) \le 2E\exp (sU) \exp (-sM),\) which is deduced by the Markov inequality. Setting \(M=n^{\alpha }, 0<\alpha <1/2\) and \(c_0=E\exp (sU)\), (A.1) is proved. \(\square \)

Lemma A.3

By Condition (C1), we have that

and

Proof

If we set \(U=X_j^2Y_k^2\) for \(j\in \{1,\ldots ,p\}\) and \(k\in \{1,\ldots ,q\}\), it has that

By simple algebra, it has that

As a result,

where \(c_1\) and \(c_2\) are constants depending on \(E(X_j^2)\) and \(E(Y_k^2)\), respectively. Consequently, it can be proved that

\(\square \)

Lemma A.4

Let \(\varvec{D}=\widehat{\varvec{\Sigma }}_{\widetilde{y}}-\varvec{\Sigma }_{\widetilde{y}}\), then it has that

The proof can be referred to Lemma 4 in Li et al. (2017). The following lemma is also from Li et al. (2017), which can be easily proved by the Hoeffding inequality and Markov inequality and some matrix theories.

Lemma A.5

For any \(\varepsilon >0\),

In addition, there exist some positive constants \(c_{2}\) and \(c_{3}\) such that

where \(\Vert \varvec{B}\Vert =\lambda _{{\textit{max}}}(\varvec{B}^\top \varvec{B})\) be the maximal eigenvalue operator for matrix \(\varvec{B}^\top \varvec{B}\) for any matrix \(\varvec{B}\).

1.2 Appendix A.2: Proof of Theorem 3.1

To prove the consistency of \(\widehat{\varvec{\Phi }}_j\), we need to make a decomposition on \(\widehat{\varvec{\Phi }}_j\). Note that \(\varvec{\Sigma }_{\widetilde{\varvec{x}}_j}\) is a \(2\times 2\) matrix, denoted as

where \(\sigma ^2_{j,11}=\text{ Cov }(X_j^2,X_j^2)\), \(\sigma ^2_{j,12}=\text{ Cov }(X_j^2,X_j)\) and \(\sigma ^2_{j,22}=\text{ Cov }(X_j,X_j)\). Let \(\varvec{s}_j\) be the j-th column of \(\varvec{\Sigma }_{\widetilde{\varvec{x}}_j\widetilde{\varvec{y}}}\), then

Similarly, we can decompose the sample analogy \(\widehat{\varvec{\Phi }}_j\) of \(\varvec{\Phi }_j\) as

Since

where \(\phi _j^{11}\) is the sample version of \(\phi _j^{11}\), similar definitions go to \(\phi _j^{12}, \phi _j^{21}\) and \(\phi _j^{22}\).

We first prove the consistency for \({\hat{\phi }}_j^{11}={\hat{\gamma }}_{j,11}\hat{\varvec{s}}_1^\top \widehat{\varvec{\Sigma }}_{\widetilde{\varvec{y}}}^{-1}\hat{\varvec{s}}_1+{\hat{\gamma }}_{j,12}\hat{\varvec{s}}_2^\top \widehat{\varvec{\Sigma }}_{\widetilde{\varvec{y}}}^{-1}\hat{\varvec{s}}_1\). It is sufficient to bound the first item in \({\hat{\phi }}_j^{11}\) because the other item shares the same asymptotic behavior. The proof takes a very similar spirit to Li et al. (2017), here we only give the outline of the proof. Denote \(\Vert \varvec{s}\Vert \) as the Euclidean norm of a vector \(\varvec{s}\). For notational simplicity, let \(\varvec{A}=\varvec{\Sigma }_{\widetilde{\varvec{y}}}^{-1}\) and \(\widehat{\varvec{A}}=\widehat{\varvec{\Sigma }}_{\widetilde{\varvec{y}}}^{-1}\). By some simple algebra, it has that

We then bound \(I_{1i}\) for \(i=1,\ldots ,4\) one by one. For the first item \(I_{11}\), note that

By Lemma A.3, it has that

Similarly, the probability bound also holds for item \(\hat{\varvec{s}}_2-\varvec{s}_2\). We next bound the matrix \(\widehat{\varvec{A}}\), for some constant \(c_3\), it has that

where the last second inequality holds because of Lemma A.4.

By condition (C2), it follows that

Consequently,

Or equivalently,

where \(B_1\) and \(B_2\) are two constants depending on \(c_1,c_2,c_3,C_1\) and \(C_2\).

We then prove the convergence rate for the second term \(I_{12}\). It has that

For \(\Vert \widehat{\varvec{A}}\varvec{s}_2\Vert \), by triangle inequality, it follows that

For \(\Vert \widehat{\varvec{A}}-\varvec{A}\Vert \Vert \varvec{s}_2 \Vert \), it has that

where the last inequality holds because \(\Vert \varvec{A}\Vert =\lambda _{\min }^{-1}(\varvec{A}^{-1})\le (C_1/q)^{-1}\) and \(\Vert \varvec{A}^{-1}-\widehat{\varvec{A}}^{-1}\Vert \le q\Vert \varvec{D}\Vert \). As \(\Vert \varvec{D}\Vert _\infty \) converges to zero by the central limit theorem and the boundedness of \(\Vert \widehat{\varvec{A}}\Vert \) proved by (A.3), \(\Vert \widehat{\varvec{A}}-\varvec{A}\Vert \Vert \varvec{s}_2 \Vert \) is negligible as \(n\rightarrow \infty \). Thus \(\Vert \varvec{A}\varvec{s}_2\Vert =\Vert \varvec{A}\Vert \Vert \varvec{s}_2\Vert =\Vert \varvec{s}_2\Vert /\lambda _{\min }(\varvec{A}^{-1})\le \Vert \varvec{s}_2\Vert q/C_1\) controls the convergence rate of \(\Vert \widehat{\varvec{A}}\varvec{s}_2\Vert \). It follows that \(\Vert \varvec{A}\varvec{s}_2\Vert ^2 \le \Vert \varvec{s}_2\Vert ^2q^2/C^2_1\le q^3C_1^2\Vert \varvec{s}_2\Vert ^2_\infty \). Note that \(\Vert \varvec{s}_2\Vert ^2_\infty \) is finite under Condition (C1) in Section 3 as it an expectation. Finally, the above results, together with (A.2), it has that

The item \(I_{13}\) and \(I_{14}\) have the same asymptotic behavior as \(I_{12}\), we thus omit the details here for space saving. Consequently,

Note that when aggregating the boundedness of \(P\left( |I_{11}| \ge \varepsilon \right) \) and \(P\left( |I_{12}| \ge \varepsilon \right) \), we delete the negligible term which does not control the convergence rate of \(\hat{\varvec{s}}_1^\top \widehat{\varvec{A}}\hat{\varvec{s}}_2\) .

Next, we prove the consistency of \({\hat{\gamma }}_{j,12}\). For simplicity, denote \({{\hat{g}}}_j={\hat{\sigma }}^2_{j,11}{\hat{\sigma }}^2_{j,22}-{\hat{\sigma }}_{j,12}^2{\hat{\sigma }}_{j,21}^2\), and \(g_j=\sigma ^2_{j,11}\sigma ^2_{j,22}-\sigma _{j,12}^2\sigma _{j,21}^2\). So, it can be derived that

By similar proving technique to the proof of Lemma A.3, we can get a similar upper bound for the probability \(P(|{\hat{\gamma }}_j-\gamma _j|\ge \varepsilon )\), namely, there exists some constant \(b_0\), \(b_1\) and \(b_2\) such that

For simplicity, let \({\hat{\delta }}=\hat{\varvec{s}}_1^\top \widehat{\varvec{\Sigma }}_{\widetilde{\varvec{y}}}^{-1}\hat{\varvec{s}}_1\) and \(\delta ={\varvec{s}}_1^\top \varvec{\Sigma }_{\widetilde{\varvec{y}}}^{-1}{\varvec{s}}_1\), then

Upper bound of \(J_2\) has the same order as \(|{\hat{\gamma }}_{j,11}-\gamma _{j,11}|\) because \(\delta \) is bounded. The bound of \(J_1\) is also easily obtained because it follows that

where the second term is negligible if we set \(H=n^\xi \). Consequently,

By taking similar argument, the asymptotic behavior of \(\hat{\phi }_j^{22}\) and \(\hat{\phi }_j^{12}\) can also be obtained.

Finally, we prove the consistency of \({\hat{\omega }}_j\). Since

Thus it is sufficient to prove the consistency of the numerator as the denominator is bounded in probability. It is not difficult to show that the numerator shares the same convergence rate as \({\hat{\phi }}_j^{11}\), here we omit the details for space saving. In summary, it can be shown \({\hat{\omega }}_j\) has the same convergence rate as \({\hat{\phi }}_j^{11}\). Consequently, it has that

Let \(\varepsilon =c_\omega n^\tau \) and the condition \(q=O(n^\kappa )\), then it follows that

Now, we prove the second part of the theorem as follows. If \({\mathcal {A}} \subsetneq \widehat{{\mathcal {A}}}\), then there must exist some \(k\in {\mathcal {A}}\) such that \({\hat{\omega }}_k<c_\omega n^{-\eta }\). It follows from Condition (C4) that \(|{\hat{\omega }}_k-\omega _k|>(c_\omega '-c_\omega )n^{-\eta }\) for some \(k\in {\mathcal {A}}\), indicating that the events satisfy \({\mathcal {E}}_n=\left\{ {\mathcal {A}}\subsetneq \widehat{{\mathcal {A}}}\right\} \subset \{|{\hat{\omega }}_k-\omega _k|>(c_\omega '-c_\omega )n^{-\eta }, \text{ for } \text{ some } k\in {\mathcal {A}}\}\). Consequently,

where \(b_\omega =c_\omega '-c_\omega \). \(\square \)

Proof of Corollary 3.1

Define \( \delta =\min _{j \in {\mathcal {A}}} \omega _{j}-\max _{j \in {\mathcal {A}}^{c}} \omega _{j} \), then under condition \((\mathrm {C} 5),\) it has that

The last term goes to 0 as \(n \rightarrow \infty \) when p satisfies some condition. \(\square \)

Proof of Theorem 3.2

We only prove the consistency of \({\hat{\rho }}_j\) as the consistency for \({\hat{\pi }}_{kl}\) is similar to prove.

By setting \(U_i=X_{ij}Y_{ik}\), \(U_i=Y_{ik}Y_{il}\), respectively, it is easily proved by Lemma A.3 that

Similarly, we can bounded \(P\left( \left| \frac{1}{n}\sum _{i=1}^n Y_{ij} -E (Y_j)\right| \ge \varepsilon \right) \) and \(P\left( \left| \frac{1}{n}\sum _{i=1}^n X_{ij}\right. \right. \left. \left. -E (X_j)\right| \ge \varepsilon \right) \). Thus, it can be proved that there exists some constant A and s such that

Note hat

Let \(\hat{\rho }^0_j=\widehat{\varvec{\Sigma }}_{X_j{\varvec{y}}} \left( \widehat{\varvec{\Sigma }}_{\varvec{y}}\right) ^{-1} \widehat{\varvec{\Sigma }}_{\varvec{y}X_j}\) and \(\rho _j^0={\varvec{\Sigma }}_{X_j{\varvec{y}}} \left( {\varvec{\Sigma }}_{\varvec{y}}\right) ^{-1}{\varvec{\Sigma }}_{\varvec{y}X_j}.\) Then by some algebra, we have

where

The next proof is the same as the that in Li et al. (2017), we omit the details. Eventually, we have

where \(C_1\) and \(C_2\) are two constants.

In the following, we prove the consistency of \(\sigma _j^{-2}\). Similarly to Lemma A.5, it has that

It can be proved that

Let \(M=O(n^\xi )\), it has that

We now bound the item \(P(|{\hat{\rho }}_j-\rho _j|\ge \varepsilon )\). It has that

For the first item in A.7, we have

Let \(M_1=O(n^\gamma )\), it has that

Similarly, we can prove

Consequently, it is easily obtained that

By some simple simplication, it has that

By setting \(\varepsilon =cn^{-\eta }\), it is easily obtained that

where \(s_A\) is the size of \(\widehat{{\mathcal {A}}}^\star \). \(\square \)

Proof of Theorem 3.3

By the Bayesian formula. It holds that

On the one hand, \(P\left\{ {\mathcal {A}}\subset \widehat{{\mathcal {A}}}\right\} \) has been bounded in Theorem 3.1, on the other hand, \(P\left\{ {\mathcal {M}}\subset \widehat{{\mathcal {M}}}\mid {\mathcal {A}}\subset \widehat{{\mathcal {A}}}\right\} \) can also be bounded like \(P\left\{ {\mathcal {A}}\subset \widehat{{\mathcal {A}}}\right\} \) by using the same technique, namely, \(P\left\{ {\mathcal {M}}\subset \widehat{{\mathcal {M}}}\mid {\mathcal {A}}\subset \widehat{{\mathcal {A}}}\right\} \ge 1-s_{2n}P\left\{ \left| {\hat{\rho }}_j-\rho _j\right| \ge c_\rho n^{-\gamma } \right\} \). The proof are very similar to the proof of Theorem 3.1, and thus is omitted for simplicity. The sure screening of \(\widehat{{\mathcal {I}}}\) can be proved in a similar spirit. \(\square \)

Reprints and permissions