
We first consider for fixed unit vectors \({\mathbf {a}}, {\mathbf {b}}\in \mathbb {R}^p\)  with \({\rm supp}({\mathbf {a}})\subseteq A, {\rm supp}({\mathbf {b}})\subseteq B\) , the tail bound of \({\mathbf {a}}^{\top }(\hat{{\mathbf {\Sigma }}}^* - {\mathbf {\Sigma }}){\mathbf {b}}\) . We would like to show that there exist uniform constants \(C_1, c>0\)  such that for all \(x>0\) ,
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^{\top }\left(\hat{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}\right){\mathbf {b}}\right|\ge x\right\rbrace \\\le & C_1\exp \left\lbrace -cn_{\min }^\ast \min \left(\frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right)\right\rbrace .\end{split}\) 
Specifically, we will bound \({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}){\mathbf {b}}\)  and \({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}){\mathbf {b}}\)  separately in the next two steps.

We consider \({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}){\mathbf {b}}\)  first. Since
\(\breve{\sigma }^\ast _{ij} - \hat{\sigma }^\ast _{ij} = \frac{1}{n_{ij}^\ast }\sum _{k=1}^n (X_{jk}\bar{X}_i^\ast + X_{ik}\bar{X}_j^\ast )S_{ik}S_{jk} - \bar{X}_i^\ast \bar{X}_j^\ast ,\) 
\({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ){\mathbf {b}}\)  can be written as
\(\begin{split}& {\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ){\mathbf {b}}= \sum _{i, j=1}^p a_ib_j (\breve{\sigma }_{ij}^\ast - \hat{\sigma }_{ij}^\ast )\\= & \sum _{i, j = 1}^p a_i b_j \Bigg (\frac{\sum _{k=1}^n X_{ik}S_{ik}}{n_i^\ast }\cdot \frac{\sum _{l=1}^n X_{jl}S_{il}S_{jl}}{n_{ij}^\ast }\\& + \frac{\sum _{k=1}^n X_{ik}S_{ik}S_{jk}}{n_{ij}^\ast }\cdot \frac{\sum _{l=1}^n X_{jl}S_{jl}}{n_j^\ast } - \frac{\sum _{k=1}^n X_{ik}S_{ik}}{n_i^\ast }\cdot \frac{\sum _{l=1}^n X_{jl}S_{jl}}{n_j^\ast }\Bigg )\\= & \sum _{i,j = 1}^p\sum _{k, l = 1}^n X_{ik}X_{jl}a_ib_j \left(\frac{S_{ik}S_{il}S_{jl}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jl}}{n_i^\ast n_j^\ast }\right).\end{split}\) 
We can calculate from (REF ) that
\(\begin{split}& \left|{\rm E}{\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ){\mathbf {b}}\right|\\= & \left|\sum _{i,j = 1}^p\sum _{k = 1}^n \sigma _{ij}a_ib_j \left(\frac{S_{ik}S_{ik}S_{jk}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jk}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jk}}{n_i^\ast n_j^\ast }\right)\right|\\= & \left|\sum _{i, j=1}^p \sigma _{ij}\frac{a_i}{n_i^\ast }b_j + \sum _{i, j = 1}^p a_i\frac{b_j}{n_j^\ast } \sigma _{ij} - \sum _{k=1}^n\sum _{i, j=1}^p\frac{S_{ik}a_i}{n_i^\ast }\frac{S_{jk}b_j}{n_j^\ast }\sigma _{ij}\right|\\\le & \left|\left(\frac{a_1}{n_1^\ast }, \ldots , \frac{a_p}{n_p^\ast }\right){\mathbf {\Sigma }}{\mathbf {b}}\right| + \left|{\mathbf {a}}^{\top }{\mathbf {\Sigma }}\left(\frac{b_1}{n_1^\ast }, \ldots , \frac{b_p}{n_p^\ast }\right)^\top \right|\\& + \sum _{k=1}^n \left|\left(\frac{S_{1k}a_1}{n_1^\ast }, \ldots , \frac{S_{pk}a_p}{n_p^\ast }\right){\mathbf {\Sigma }}\left(\frac{S_{1k}b_1}{n_1^\ast }, \ldots , \frac{S_{pk}b_p}{n_p^\ast }\right)^{\top }\right| \\\le & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert \frac{\Vert {\mathbf {a}}\Vert _2\Vert {\mathbf {b}}\Vert _2}{n_{\min }^\ast } + \Vert {\mathbf {\Sigma }}_{A\times B}\Vert \frac{\Vert {\mathbf {a}}\Vert _2\Vert {\mathbf {b}}\Vert _2}{n_{\min }^\ast }\\& + \sum _{k=1}^n\Vert {\mathbf {\Sigma }}_{A\times B}\Vert \cdot \frac{1}{2}\left\lbrace \left\Vert \left(\frac{S_{1k}a_1}{n_1^\ast }, \ldots , \frac{S_{pk}a_p}{n_p^\ast }\right)\right\Vert _2^2 + \left\Vert \left(\frac{S_{1k}b_1}{n_1^\ast }, \ldots , \frac{S_{pk}b_p}{n_p^\ast }\right) \right\Vert _2^2\right\rbrace .\end{split}\) 
For the last term in (REF ), we have the following bound,
\(\begin{split}& \sum _{k=1}^n\Vert {\mathbf {\Sigma }}_{A\times B}\Vert \cdot \frac{1}{2}\left\lbrace \left\Vert \left(\frac{S_{1k}a_1}{n_1^\ast }, \ldots , \frac{S_{pk}a_p}{n_p^\ast }\right)\right\Vert _2^2 + \left\Vert \left(\frac{S_{1k}b_1}{n_1^\ast }, \ldots , \frac{S_{pk}b_p}{n_p^\ast }\right) \right\Vert _2^2\right\rbrace \\= & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \sum _{k=1}^n\sum _{i=1}^p \frac{1}{2} \left(\frac{S_{ik}a_i^2}{n_i^{\ast 2}} + \frac{S_{ik}b_i^2}{n_i^{\ast 2}}\right)\\= & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \sum _{i=1}^p \frac{1}{2}\left(\frac{a_i^2 + b_i^2}{n_i^\ast }\right)\\\le & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \sum _{i=1}^p \frac{a_i^2+b_i^2}{2n_{\min }^\ast } \le \frac{(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}{n_{\min }^\ast }.\end{split}\) 
Thus, by (REF ) and the inequality above, we have
\(\left|{\rm E}a^\top (\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ) b \right| \le \frac{3(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}{n_{\min }^\ast }.\) 
The last term of (REF ) can be treated as a quadratic form of the vectorization of \({\mathbf {X}}: \text{vec}({\mathbf {X}})\in \mathbb {R}^{pn}\) . We note the last term as \(\text{vec}({\mathbf {X}})^{\top }{\mathbf {Q}}\text{vec}({\mathbf {X}})\) , where \({\mathbf {Q}}\in \mathbb {R}^{pn\times pn}\)  and
\({\mathbf {Q}}_{(i, k), (j, l)} = a_ib_j \left(\frac{S_{ik}S_{il}S_{jl}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jl}}{n_i^\ast n_j^\ast }\right),\quad 1\le i, j\le p, 1\le k, l\le n. \) 
\({\mathbf {Q}}\)  has the following properties,
\(\begin{split}\Vert {\mathbf {Q}}\Vert _F^2 = & \sum _{i,j = 1}^p\sum _{k,l=1}^n a_i^2b_j^2 \left(\frac{S_{ik}S_{il}S_{jl}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jl}}{n_i^\ast n_j^\ast }\right)^2\\\le & \sum _{i, j=1}^p a_i^2b_j^2\sum _{k, l =1}^n \left(2\frac{S_{ik}S_{il}S_{jl}}{n_i^{\ast 2}n_{ij}^{\ast 2}} + 2\frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^{\ast 2}n_j^{\ast 2}} + \frac{S_{ik}S_{jl}}{n_i^{\ast 2}n_j^{\ast 2}}\right),\quad \text{since } S_{ik} \in \lbrace 0, 1\rbrace ;\\\le & \sum _{i,j=1}^p a_i^2b_j^2 \frac{5}{n_{\min }^{\ast 2}} = \frac{5\Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2}{n_{\min }^{\ast 2}} = \frac{5}{n_{\min }^{\ast 2}};\end{split}\) 
\(\Vert {\mathbf {Q}}\Vert  \le \Vert {\mathbf {Q}}\Vert _F \le \frac{\sqrt{5}\Vert {\mathbf {a}}\Vert _2\Vert {\mathbf {b}}\Vert _2}{n_{\min }^\ast } \le \frac{\sqrt{5}}{n_{\min }^{\ast }}.\) 
For \({\rm vec}({\mathbf {X}}) \in \mathbb {R}^{pn}\) , since its segments \(\lbrace {\mathbf {X}}_{k}, k=1,\ldots , p\rbrace \)  are independent and \({\mathbf {X}}_k = \Gamma {\mathbf {Z}}_k\) , we can further write \(\text{vec}({\mathbf {X}}) = {\Gamma } \text{vec}({\mathbf {Z}})\) , where \({\Gamma }\in \mathbb {R}^{pn\times qn}\)  is with \(n\)  diagonal blocks of \(\Gamma \) , \(\text{vec}({\mathbf {Z}})\)  is a \((qn)\) -dimensional i.i.d. sub-Gaussian random vector. Based on Hanson-Wright's inequality (Theorem 1.1 in Rudelson and Vershynin [1]}),
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}- {\rm E}{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}\right|\ge x\right\rbrace \\= & \Pr \left\lbrace \left|\text{vec}({\mathbf {X}})^{\top }{\mathbf {Q}}\text{vec}({\mathbf {X}}) - {\rm E}\text{vec}({\mathbf {X}})^{\top }{\mathbf {Q}}\text{vec}({\mathbf {X}})\right|\ge x\right\rbrace \\= & \Pr \left[\left|\text{vec}({\mathbf {Z}})^{\top }{\Gamma }^{\top }{\mathbf {Q}}{\Gamma } \text{vec}({\mathbf {Z}}) - {\rm E}\left\lbrace \text{vec}({\mathbf {Z}})^{\top }{\Gamma }^{\top }{\mathbf {Q}}{\Gamma } \text{vec}({\mathbf {Z}})\right\rbrace \right|\ge x\right]\\\le & 2\exp \left\lbrace -c\min \left(\frac{x^2}{\tau ^4\Vert {\Gamma }^{\top }{\mathbf {Q}}{\Gamma }\Vert _F^2}, \frac{x}{\tau ^2\Vert {\Gamma }{\mathbf {Q}}{\Gamma }\Vert } \right)\right\rbrace .\end{split}\) 
Here \(c>0\)  is a uniform constant. Since \({\mathbf {Q}}\)  is supported on \(\lbrace (i, k), (j, l): i\in A, j\in B\rbrace \) , we have \({\Gamma }^{\top }{\mathbf {Q}}{\Gamma } = {\Gamma _A}^{\top }{\mathbf {Q}}_{A\times B}{\Gamma _B}\) . Here \({\Gamma _A} \in \mathbb {R}^{|A|n\times qn}, {\Gamma _B}\in \mathbb {R}^{|B|n\times qn}\)  are with \(n\)  diagonal block \(\Gamma _{A\times [q]}\)  and \(\Gamma _{B \times [q]}\) , respectively, where \([q] = \lbrace 1, \ldots , q\rbrace \) . Since \(\Gamma _{A\times [q]} \Gamma _{A\times [q]}^{\top }= {\mathbf {\Sigma }}_{A}\) , \(\Gamma _{B\times [q]} \Gamma _{B\times [q]}^{\top }= {\mathbf {\Sigma }}_{B}\) , we know
\(\Vert {\Gamma _A}\Vert  = \Vert \Gamma _{A\times [q]}\Vert  \le \Vert {\mathbf {\Sigma }}_A\Vert ^{1/2}, \quad \Vert \Gamma _{B\times [q]}\Vert  \le \Vert {\Gamma _B}\Vert  \le \Vert {\mathbf {\Sigma }}_B\Vert ^{1/2}. \) 
Then we further have
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}- {\rm E}{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}\right|\ge x\right\rbrace \\\le & 2\exp \left\lbrace -c\min \left(\frac{x^2}{\tau ^4\Vert {\Gamma _A}^{\top }{\mathbf {Q}}_{A\times B}{\Gamma _B}\Vert _F^2}, \frac{x}{\tau ^2\Vert {\Gamma _A}^{\top }{\mathbf {Q}}_{A\times B}{\Gamma _B}\Vert } \right)\right\rbrace \\\le & 2\exp \left\lbrace -c\min \left(\frac{x^2}{\tau ^4\Vert {\Gamma _B}\Vert ^2\Vert {\Gamma _A}^{\top }\Vert ^2\Vert {\mathbf {Q}}\Vert _F^2}, \frac{x}{\tau ^2\Vert {\Gamma _B}\Vert \Vert {\Gamma _A}^{\top }\Vert \Vert {\mathbf {Q}}\Vert } \right)\right\rbrace \\\le & 2\exp \left[-c\min \left\lbrace \frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert \Vert {\mathbf {Q}}\Vert _F^2}, \frac{x}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}\Vert {\mathbf {Q}}\Vert } \right\rbrace \right]\\\le & 2\exp \left[-c \min \left\lbrace \frac{x^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{xn_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace \right].\end{split}\) 
We define \(x^{\prime } = \max \left\lbrace x -3(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}/n_{\min }^\ast , 0\right\rbrace \) , combining the inequality above and (REF ), we have
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^\top \left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}\right| \ge x\right\rbrace  \le \Pr \left\lbrace \left|{\mathbf {a}}^\top \left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}- {\rm E}{\mathbf {a}}^\top \hat{{\mathbf {\Sigma }}}^\ast {\mathbf {b}}\right| \ge x^{\prime }\right\rbrace \\\le & 2\exp \left[-c \min \left\lbrace \frac{(x^{\prime })^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{x^{\prime }n_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace \right]\\\le & 2\exp \left[-c^{\prime } \min \left\lbrace \frac{x^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{xn_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace  +C\max \left(\frac{1}{\tau ^4}, \frac{1}{\tau ^2}\right)\right]\\\le & C\exp \left[-c^{\prime } \min \left\lbrace \frac{x^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{xn_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace  \right].\end{split}\) 
In the last inequality above, we used a fact that \(\tau \)  is lower bounded by a uniform constant. This is due to Assumption REF  that \({\rm E}(Z) = 0\) , \({\rm var}(Z) = 1\) , \({\rm E}\exp (tZ)\le \exp (t^2\tau ^2/2)\) . Then,
\(\exp (4\tau ^2/2) \ge \frac{1}{2}\left\lbrace {\rm E}\exp (2Z) + {\rm E}\exp (-2Z)\right\rbrace  =\sum _{k=0}^\infty \frac{2^{2k}{\rm E}Z^{2k}}{(2k)!} \ge 2{\rm E}Z^2 = 2, \) 
which implies \(\tau ^2\ge \frac{1}{2}\ln (2)\) .

It is easy to see that \({\rm E}\breve{{\mathbf {\Sigma }}}^\ast = {\mathbf {\Sigma }}\) , so \({\rm E}{\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}){\mathbf {b}}= 0\) . Then
\(\begin{split}& a^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }})b\\= & \sum _{i,j= 1}^p a_i b_j \left(\frac{1}{n_{ij}^\ast }\sum _{k=1}^n X_{ik}X_{jk}S_{ik}S_{jk}\right) - {\rm E}\sum _{i,j= 1}^p a_i b_j \left(\frac{1}{n_{ij}^\ast }\sum _{k=1}^n X_{ik}X_{jk}S_{ik}S_{jk}\right)\\= & \sum _{k=1}^n \sum _{i, j=1}^p \left(\frac{a_ib_jS_{ik}S_{jk}}{n_{ij}^\ast } X_{ik}X_{jk} - {\rm E}\frac{a_ib_jS_{ik}S_{jk}}{n_{ij}^\ast } X_{ik}X_{jk} \right)\\\triangleq & \sum _{k=1}^n \left({\mathbf {X}}_k^{\top }k {\mathbf {X}}_k - {\rm E}{\mathbf {X}}_k ^{\top }k {\mathbf {X}}_k\right)\\= & \sum _{k=1}^n \left({\mathbf {Z}}_k^{\top }\Gamma ^{\top }k\Gamma {\mathbf {Z}}_k - {\rm E}{\mathbf {Z}}_k^{\top }\Gamma ^{\top }k\Gamma {\mathbf {Z}}_k\right).\end{split}\) 
Here \(k\in \mathbb {R}^{p\times p}\)  is a matrix such that \(C^k_{ij} = a_ib_jS_{ik}S_{jk}/n_{ij}^\ast \) . Note that \(k\)  is supported on \(A\times B\) , we can prove the following properties of \(k\) .
\(\begin{split}\Vert \Gamma ^{\top }k\Gamma \Vert _F = & \sqrt{{\rm tr}\left(k\Gamma \Gamma ^{\top }{k\top }\Gamma \Gamma ^{\top }\right)}\\= & \sqrt{{\rm tr}\left(k_{A\times B} \Gamma _{B\times [q]}\Gamma _{B\times [q]}^{\top }{k\top }_{A\times B}\Gamma _{A\times [q]}\Gamma _{A\times [q]}^{\top }\right)} \\\le & \Vert \Gamma _{B\times [q]}\Vert  \Vert \Gamma _{A\times [q]}\Vert  \sqrt{{\rm tr}(k{k\top })}\\\le & (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2} \sqrt{{\rm tr}(k{k\top })};\end{split}\) 
\(\begin{split}& \sum _{k=1}^n \Vert \Gamma ^\top k \Gamma \Vert _F^2 \le \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \Vert k\Vert _F^2 = \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \sum _{k=1}^n \sum _{i,j=1}^p \left(\frac{a_ib_jS_{ik}S_{jk}}{n_{ij}^\ast }\right)^2\\= & \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \sum _{k=1}^n \sum _{i, j=1}^p \frac{S_{ik}S_{jk}a_i^2b_j^2}{n_{ij}^{\ast 2}} = \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \sum _{i,j=1}^p \frac{a_i^2b_j^2}{n_{ij}^\ast } \\\le & \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \frac{\Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2}{n_{\min }^\ast } = \frac{\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }{n_{\min }^\ast };\end{split}\) 
\(\begin{split}\Vert \Gamma ^\top k\Gamma \Vert  \le & \Vert \Gamma ^\top k\Gamma \Vert _F \le (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2} \sqrt{{\rm tr}(k{k\top })}\\\le & (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2} \sqrt{\sum _{i, j=1}^p \left(\frac{a_ib_j S_{ik}S_{jk}}{n_{ij}^\ast }\right)^2}\\\le & (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}\sqrt{\sum _{i,j=1}^p \frac{a_i^2b_j^2}{n_{\min }^{\ast 2}}}\le \frac{\sqrt{\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }}{n_{\min }^\ast }.\end{split}\) 
Now, note that the last line of (REF ) can be also equivalently written as
\(\text{vec}({\mathbf {Z}})^\top {con}\text{vec}({\mathbf {Z}})^\top - {\rm E}\text{vec}({\mathbf {Z}})^\top {con}\text{vec}({\mathbf {Z}})^\top , \) 
\({con} = \begin{bmatrix}\Gamma ^\top 1 \Gamma & & \\& \ddots & \\& & \Gamma ^\top n \Gamma \end{bmatrix} \in \mathbb {R}^{(qn)\times (qn)}, \) 
where \(\text{vec}({\mathbf {Z}})\)  is the vectorization of \({\mathbf {Z}}\) , which is an \(qn\) -dimensional i.i.d. sub-Gaussian vector. Based on the properties of \(k\)  above, we have
\(\Vert {con} \Vert _F^2 = \sum _{k=1}^n \Vert \Gamma ^\top k \Gamma \Vert _F^2 \overset{(\ref {ineq:GammaCGamma_fro_sum})}{\le } \frac{\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }{n_{\min }^\ast },\) 
\(\Vert {con}\Vert  \le \max _{1\le k\le n} \Vert \Gamma ^\top k \Gamma \Vert  \overset{(\ref {ineq:GammaCGamma_spe})}{\le } \frac{(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}{n_{\min }^\ast }. \) 
Now applying Hanson-Wright's inequality (Theorem 1.1 in Rudelson and Vershynin [1]}), we have
\(\begin{split}& \Pr \left\lbrace \left|\text{vec}({\mathbf {Z}}_k)^{\top }{con}\text{vec}({\mathbf {Z}}_k) - {\rm E}\text{vec}({\mathbf {Z}}_k)^{\top }{con}\text{vec}({\mathbf {Z}}_k)\right|\ge x\right\rbrace \\\le & 2\exp \left\lbrace -c \min \left(\frac{x^2}{\tau ^4\Vert {con}\Vert _F^2}, \frac{x}{\tau ^2\Vert {con}\Vert }\right)\right\rbrace  \\\le & 2\exp \left\lbrace -cn_{\min }^\ast \min \left(\frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2 (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right)\right\rbrace .\end{split}\) 
Thus,
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^\top (\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}){\mathbf {b}}\right|\ge x\right\rbrace \\\le & 2\exp \left\lbrace -cn_{\min }^\ast \min \left(\frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2 (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right)\right\rbrace .\end{split}\) 
Here \(c\)  is a uniform constant. Combining (REF ) and (REF ), we have (REF ).

Next, we use the \(\varepsilon \) -net technique to give the bound on \(\Vert \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\Vert \) . Denote \(\ast = \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\) . Suppose \(S_{1/3}^{A}\)  is the \((1/3)\) -net for all unit vectors in \(\mathbb {R}^{|A|}\) ; similarly \(S_{1/3}^B\)  is the \((1/3)\) -net for all unit vectors in \(\mathbb {R}^{|B|}\) . Based on the proof of Lemma 3 in Cai et al. [3]}, we can let \(\text{Card}(S_{1/3}^A) \le 7^k\) , \(\text{Card}(S_{1/3}^B) \le 7^k\) . Since for all \({\mathbf {a}}, {\mathbf {a}}_0\in \mathbb {R}^{|A|}, {\mathbf {b}}, {\mathbf {b}}_0\in \mathbb {R}^{|B|}\) ,
\(\begin{split}\left|{\mathbf {a}}^{\top }\ast {\mathbf {b}}\right| - \left|{\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0\right| \le & \left|{\mathbf {a}}^{\top }\ast {\mathbf {b}}- {\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0\right| \le \left|({\mathbf {a}}- {\mathbf {a}}_0)^{\top }\ast {\mathbf {b}}\right| + \left|{\mathbf {a}}_0^{\top }\ast ({\mathbf {b}}- {\mathbf {b}}_0) \right|\\\le & \left(\Vert {\mathbf {a}}- {\mathbf {a}}_0\Vert _2 + \Vert {\mathbf {b}}- {\mathbf {b}}_0\Vert _2\right)\Vert \ast \Vert ,\end{split}\) 
we have for all \({\mathbf {a}}\in \mathbb {R}^{|A|}, {\mathbf {b}}\in \mathbb {R}^{|B|}, \Vert {\mathbf {a}}\Vert _2 = \Vert {\mathbf {b}}\Vert _2 = 1\) , we can find \({\mathbf {a}}_0 \in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B\)  such that \(\Vert {\mathbf {a}}_0 - {\mathbf {a}}\Vert _2\le 1/3, \Vert {\mathbf {b}}_0 - {\mathbf {b}}\Vert _2\le 1/3\) , then
\(|{\mathbf {a}}^\top \ast {\mathbf {b}}| \le |{\mathbf {a}}_0^\top \ast {\mathbf {b}}_0| + \frac{2}{3}\Vert \ast \Vert  \le \sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B}|{\mathbf {a}}_0^\top \ast {\mathbf {b}}_0| + \frac{2}{3}\Vert \ast \Vert , \) 
\(\Vert \ast \Vert  = \sup _{\begin{array}{c}{\mathbf {a}}\in \mathbb {R}^{|A|}, {\mathbf {b}}\in \mathbb {R}^{|B|},\\ \Vert {\mathbf {a}}\Vert _2 = \Vert {\mathbf {b}}\Vert _2 = 1\end{array}} |{\mathbf {a}}^\top \ast {\mathbf {b}}| \le \sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B}|{\mathbf {a}}_0^\top \ast {\mathbf {b}}_0| + \frac{2}{3}\Vert \ast \Vert , \) 
which yields
\(\Vert \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\Vert  = \Vert \ast \Vert  \le 3\sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B}|{\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0|.\) 
Finally, by combining (REF ) and the inequality above, we know there exist uniform constants \(C_1, c>0\)  such that for all \(t>0\) ,
\(\begin{split}& \Pr \left(\Vert \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\Vert  \ge x\right) \le \Pr \left(\sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0 \in S_{1/3}^B}|{\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0| \ge \frac{x}{3} \right)\\\le & C_1(7)^{|A| + |B|}\exp \left[-cn_{\min }^\ast \min \left\lbrace \frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace \right].\end{split}\) 
Since \(|A|+|B|\le 2|A\cup B|\) , we have finished the proof of Lemma REF .    \(\square \)

