$\cup_{\ell=1}^{\mathfrak{p}}\mathcal{C}_{\ell}=[d]$ such that
$\sigma^{U}_{jk}=\sigma^{V}_{jk}=0$ when $j\in\mathcal{C}_{\ell}$ and
$k\in\mathcal{C}_{\ell^{\prime}}$ for some $\ell\neq\ell^{\prime}$. This is
the connectivity assumption. Theorem 3.2 also assumes that $U$ and $V$ have
unit variances i.e., $\sigma^{U}_{jj}=\sigma^{V}_{jj}=1,j\in[d]$ and there
exists some $\sigma_{0}<1$ such that $|\sigma^{V}_{jk}|\leq\sigma_{0}$ for any
$j\neq k$ and $|\\{(j,k):j\neq k,|\sigma^{U}_{jk}|>\sigma_{0}\\}|\leq b_{0}$
for some constant $b_{0}$. Under its general version (which is actually proved
in Appendix B.2), we only need to assume
$a_{0}\leq\sigma^{U}_{jj}=\sigma^{V}_{jj}\leq a_{1},~{}\forall j\in[d]$, and
given any $j\in\mathcal{C}_{\ell}$ with some $\ell$, there exists at least one
$m\in\mathcal{C}_{\ell^{\prime}}$ such that
$\sigma^{U}_{jj}=\sigma^{V}_{jj}=\sigma^{U}_{mm}=\sigma^{V}_{mm}$ for any
$\ell^{\prime}\neq\ell$. From now, we will call it the general variance
condition. Accordingly, we assume there exists some $\sigma_{0}<1$ such that
$|\sigma^{V}_{jk}/\sqrt{\sigma^{V}_{jj}\sigma^{V}_{kk}}|\leq\sigma_{0}$ for
any $j\neq k$ and $|\\{(j,k):j\neq
k,|\sigma^{U}_{jk}|\sqrt{\sigma^{U}_{jj}\sigma^{U}_{kk}}>\sigma_{0}\\}|\leq
b_{0}$ for some constant $b_{0}$. Such condition is referred as the general
covariance assumption. Below we give the details of applying Theorem 3.2 (with
a general version of the variance assumption) by checking those three
conditions.

We start from the connectivity assumption and the general variance condition.
Notice that in Section 5, $p$ denotes the number of connected components in
the associated graph $\mathcal{G}$ of $\bm{X}$. Then we know there exist
disjoint partitions of nodes $\cup_{\ell=1}^{p}\mathcal{C}^{X}_{\ell}=[d]$
such that $\bm{\Theta}_{jk}=0$ when
$j\in\mathcal{C}^{X}_{\ell},k\in\mathcal{C}^{X}_{\ell^{\prime}}$ for some
$\ell\neq\ell^{\prime}$. We will utilize this fact to examine the covariance
matrices of $U:=(Z_{e})_{e\in N_{0j_{1}}\cup N_{0j_{2}}}$ and
$V:=(Z^{\prime}_{e})_{e\in N_{0j_{1}}\cup N_{0j_{2}}}$ and show the
connectivity assumption holds. Note that for given
$j_{1},j_{2}\in\mathcal{H}_{0},j_{1}\neq j_{2}$, there exist at least $p-2$
components $\cup_{\ell=1}^{p-2}\mathcal{C}^{X}_{\ell}$ such that $j_{1}$ and
$j_{2}$ do not belong to them. Without loss of generality, we write
$j_{1},j_{2}\notin\cup_{\ell=1}^{p-2}\mathcal{C}^{X}_{\ell}$. Thus we have
$\cup_{l=1}^{p-2}\mathcal{C}^{X}_{\ell}\subset N_{0j_{1}}\cap N_{0j_{2}}$ by
definition.

In the following, we will show the number of connected components on the
associated graph of the Gaussian random vector $U:=(Z_{e})_{e\in
N_{0j_{1}}\cup N_{0j_{2}}}$ is at least $2(p-2)$ by examining its covariance
matrix $\bm{\Sigma}_{Z}$. First we focus on the covariance entries in the
block $\bm{\Sigma}_{11}^{Z}$. When $\ell_{1},\ell_{2}\in[p-2]$ and
$\ell_{1}\neq\ell_{2}$, we have for any
$k\in\mathcal{C}^{X}_{\ell_{1}},k^{\prime}\in\mathcal{C}^{X}_{\ell_{2}}$ (thus
$k,k^{\prime}\in N_{0j_{1}}\cap N_{0j_{2}}$), the $(k,k^{\prime})$ covariance
entry (A.26) in the block $\bm{\Sigma}_{11}^{Z}$ equals

$\bm{\Theta}_{j_{1}j_{1}}\bm{\Theta}_{kk^{\prime}}+\bm{\Theta}_{j_{1}k}\bm{\Theta}_{j_{1}k^{\prime}}=\bm{\Theta}_{j_{1}j_{1}}\bm{\Theta}_{kk^{\prime}}=0,$
(A.30)

where the first equality holds since $k,k^{\prime}\in N_{0j_{1}}$, and the
second equality holds since $\ell_{1}\neq\ell_{2}$. Similarly, we have the
$(k,k^{\prime})$ covariance entry in the block $\bm{\Sigma}_{22}^{Z}$ also
equals to zero. Next we compute the covariance entries in the block
$\bm{\Sigma}_{12}^{Z}$. For the same $(k,k^{\prime})$, we know that $k\in
N_{0j_{1}},k^{\prime}\in N_{0j_{2}}$. Thus the corresponding covariance entry
(A.27) equals

$\bm{\Theta}_{j_{1}j_{2}}\bm{\Theta}_{kk^{\prime}}+\bm{\Theta}_{j_{1}k^{\prime}}\bm{\Theta}_{j_{2}k}=0,$
(A.31)

since we also have $k\in N_{0j_{2}},k^{\prime}\in N_{0j_{1}}$ and
$k\in\mathcal{C}^{X}_{\ell_{1}},k^{\prime}\in\mathcal{C}^{X}_{\ell_{2}}$ for
some $\ell_{1}\neq\ell_{2}$. Denote the nodes in the associated graph of
$\bm{\Sigma}^{Z}$ by $\mathcal{V}_{Z}:=\\{(j,k):k\in N_{0j},j=j_{1},j_{2}\\}$.
Remark here we use a pair $(j,k)$ to represent a node since there exists some
$k\in N_{0j_{1}}\cap N_{0j_{2}}$ and we have to distinguish the covariance
entries $(j_{1},k)$ and $(j_{2},k)$. Based on previous calculations, we
immediately find
$\cup_{\ell=1}^{2(p-2)}\mathcal{C}^{Z}_{\ell}\subset\mathcal{V}_{Z}$, where
$\mathcal{C}^{Z}_{\ell}$ is chosen to be

$\mathcal{C}^{Z}_{\ell}=\left\\{\begin{array}[]{ll}\\{(j_{1},k):k\in\mathcal{C}^{X}_{\ell}\\}&~{}\text{when}~{}1\leq\ell\leq
p-2,\\\
\\{(j_{2},k):k\in\mathcal{C}^{X}_{\ell}\\}&~{}\text{when}~{}p-1\leq\ell\leq
2(p-2).\end{array}\right.$ (A.32)

Further, we know they form different components on the associated graph of
$\bm{\Sigma}^{Z}$. This is due to (A.30) and (A.31). The above results also
apply to the Gaussian random vector $V:=(Z^{\prime}_{e})_{e\in N_{0j_{1}}\cup
N_{0j_{2}}}$ by construction of $Z^{\prime}_{e}$, i.e., we have the same
subset of nodes
$\cup_{\ell=1}^{2(p-2)}\mathcal{C}^{Z}_{\ell}\subset\mathcal{V}_{Z}$ from
different components on the associated graph of $\bm{\Sigma}^{Z^{\prime}}$.

When $k\in\mathcal{C}_{\ell}$ for some $\ell\in[p-2]$, the corresponding
diagonal entries of the covariance matrices
$\bm{\Sigma}^{Z},\bm{\Sigma}^{Z^{\prime}}$ equal

$\bm{\Theta}_{j_{1}j_{1}}\bm{\Theta}_{kk}+\bm{\Theta}_{j_{1}k}\bm{\Theta}_{j_{1}k}=\bm{\Theta}_{j_{1}j_{1}}\bm{\Theta}_{kk}=1=\bm{\Theta}_{j_{2}j_{2}}\bm{\Theta}_{kk},$

where the first equality holds since $\bm{\Theta}_{j_{1}k}=0$ when
$k\in\mathcal{C}_{\ell}\subset N_{0j_{1}}$. As for the second equality, we use
the fact that $\bm{\Theta}_{jj}=1,j\in[d]$. This is because $\breve{T}_{E}$ in
(A.5) considers the standardized version
${{\bm{\Theta}}_{jk}}/{\sqrt{{\bm{\Theta}}_{jj}{\bm{\Theta}}_{kk}}}$. Remark
that the rescaling in Lemma A.4 is performed on one of the two random vectors
$(Z^{\prime}_{e})_{e\in N_{0j_{1}}},(Z^{\prime}_{e})_{e\in N_{0j_{2}}}$. Then
we have the variances across the $p-2$ components
$\cup_{\ell=1}^{p-2}\mathcal{C}^{Z}_{\ell}$ are the same. The variances across
the other $p-2$ components $\cup_{\ell=p-1}^{2(p-2)}\mathcal{C}^{Z}_{\ell}$
are also the same. Finally, we show there exist at least $p-2$ components
$\cup_{\ell=1}^{p-2}\mathcal{C}^{Z}_{\ell}$ (or
$\cup_{\ell=p-1}^{2(p-2)}\mathcal{C}^{Z}_{\ell}$) satisfying the requirement
in the connectivity assumption and the general variance condition.

Regarding the general covariance condition, we first note that
$\bm{\Theta}\in\mathcal{U}(M,s,r_{0})$ which says that
$\lambda_{\min}(\bm{\Theta})\geq 1/r_{0},\lambda_{\max}(\bm{\Theta})\leq
r_{0}$. Thus we have $\max_{j,k\in[d],j\neq
k}|\bm{\Theta}_{jk}|\leq\sigma_{0}$ for some $\sigma_{0}<1$. Below we will
examine all the off-diagonal entries of $\bm{\Sigma}^{Z}$ and
$\bm{\Sigma}^{Z^{\prime}}$. Regarding the block $\bm{\Sigma}^{Z}_{11}$, for
any $k,k^{\prime}\in N_{0j_{1}},k\neq k^{\prime}$ where
$N_{0j_{1}}=\\{k:\bm{\Theta}_{j_{1}k}=0\\}$, (A.26) says that the
corresponding $(k,k^{\prime})$ entry in $\bm{\Sigma}^{Z}_{11}$ equals
$\bm{\Theta}_{kk^{\prime}}$ (here we have
$|\bm{\Theta}_{kk^{\prime}}|\leq\sigma_{0}$). Similar results hold for the
block $\bm{\Sigma}^{Z}_{22}$. Regarding the block $\bm{\Sigma}^{Z}_{12}$,
consider $k_{1}\in N_{0j_{1}},k_{2}\in N_{0j_{2}}$, then we have the
corresponding $(k_{1},k_{2})$ entry in the block equals
$\bm{\Theta}_{j_{1}k_{2}}\bm{\Theta}_{j_{2}k_{1}}$. This is due to (A.27) and
the fact that $\bm{\Theta}_{j_{1}j_{2}}=0$ under Case 1. Only when
$k_{2}=j_{1},k_{1}=j_{2}$, we have
$\bm{\Theta}_{j_{1}k_{2}}\bm{\Theta}_{j_{2}k_{1}}=1$. Otherwise,
$|\bm{\Theta}_{j_{1}k_{2}}\bm{\Theta}_{j_{2}k_{1}}|\leq\sigma_{0}^{2}<\sigma_{0}$
always holds. As for the $\bm{\Sigma}^{Z^{\prime}}$, since its block
$\bm{\Sigma}^{Z^{\prime}}_{12}=\bm{O}$, we immediately have the absolute
values of all its off-diagonal entries is bounded by $\sigma_{0}$. In summary,
we verify the covariance condition of Theorem 3.2 (here $U$ and $V$ are chosen
to be $Z_{e})_{e\in N_{0j_{1}}\cup N_{0j_{2}}}$ and $(Z^{\prime}_{e})_{e\in
N_{0j_{1}}\cup N_{0j_{2}}}$ respectively).

Having checked all the three conditions, we now obtain

$\displaystyle\sum_{m=1}^{\lambda_{d}}\sum_{\bm{\Theta}_{j_{1}j_{2}}=0}\frac{\mathrm{IV}_{j_{1}j_{2}}(\alpha_{m})}{\epsilon^{2}d^{2}_{0}}$
(A.33) $\displaystyle\leq$
$\displaystyle\sum_{m=1}^{\lambda_{d}}\bigg{\\{}\frac{1}{\epsilon^{2}d_{0}^{2}}\cdot\frac{\log
d}{\alpha_{m}p}\bigg{(}\sum_{k_{1}\in N_{0j_{1}},k_{2}\in N_{0j_{2}},k_{1}\neq
k_{2}}\mathds{1}{(\bm{\Theta}_{j_{1}k_{2}}\bm{\Theta}_{j_{2}k_{1}}\neq
0)}\bigg{)}\bigg{\\}}$ $\displaystyle\leq$
$\displaystyle\frac{C_{\bm{\Theta}}|S|\log
d}{\epsilon^{2}d_{0}p}\left(\frac{1}{d_{0}}\sum_{m=1}^{\lambda_{d}}\frac{C^{\prime}}{\alpha_{m}}\right),$

where $S$ represents the set

$S=\\{(j_{1},j_{2},k_{1},k_{2}):j_{1},j_{2}\in\mathcal{H}_{0},j_{1}\neq
j_{2},k_{1}\neq
k_{2},\bm{\Theta}_{j_{1}j_{2}}=\bm{\Theta}_{j_{1}k_{1}}=\bm{\Theta}_{j_{2}k_{2}}=0,\bm{\Theta}_{j_{1}k_{2}}\neq
0,\bm{\Theta}_{j_{2}k_{1}}\neq 0\\}$

as defined in Section 5, and $C_{\bm{\Theta}}$ is some universal constant over
$\bm{\Theta}\in\mathcal{U}(M,s,r_{0})$. Finally, combining (A.33) with (A.28),
we obtain the following bound on $\mathrm{III}^{\prime}_{3}$,

$\displaystyle\mathrm{III}^{\prime}_{3}$ $\displaystyle\leq$
$\displaystyle\frac{C_{\bm{\Theta}}|S|\log
d}{\epsilon^{2}d_{0}p}\left(\frac{1}{d_{0}}\sum_{m=1}^{\lambda_{d}}\frac{C^{\prime}}{\alpha_{m}}\right)+\frac{1}{\epsilon^{2}d_{0}}\sum_{m=1}^{\lambda_{d}}\frac{C^{\prime}}{\alpha_{m}}$
$\displaystyle=$ $\displaystyle\left(1+\frac{C_{\bm{\Theta}}|S|\log
d}{d_{0}p}\right)\cdot\frac{1}{\epsilon^{2}d_{0}}\sum_{m=1}^{\lambda_{d}}\frac{C^{\prime}}{\alpha_{m}}$
$\displaystyle\leq$
$\displaystyle\frac{C^{\prime\prime}t_{\lambda_{d}}}{\rho\epsilon^{2}d_{0}h_{d}}\left(1+\frac{C_{\bm{\Theta}}|S|\log
d}{d_{0}p}\right),$

where the last inequality holds due to the same derivations for
$\mathrm{III}_{1}$ in the proof of Lemma A.2. ∎

######  Lemma A.5.

Recall the definitions of $I_{j}(\alpha)$ and $W_{j}(\alpha)$ in (A.19) and
(A.20), for $j_{1},j_{2}\in\mathcal{H}_{0},j_{1}\neq j_{2}$, when
$\alpha\in[\alpha_{L},1]$, we have

${\big{|}\mathbb{E}\left[{I_{j_{1}}(\alpha)I_{j_{2}}(\alpha)}\right]-\mathbb{E}\left[{W_{j_{1}}(\alpha)W_{j_{2}}(\alpha)}\right]\big{|}}\leq{\eta(d,n,\zeta_{1},\zeta_{2},\alpha_{L})}{\alpha}.$
(A.34)

###### Proof of Lemma A.5.

First express
$\big{|}\mathbb{E}\left[{I_{j_{1}}(\alpha)I_{j_{2}}(\alpha)}\right]-\mathbb{E}\left[{W_{j_{1}}(\alpha)W_{j_{2}}(\alpha)}\right]\big{|}$
as

$\displaystyle\big{|}\mathbb{E}\left[{I_{j_{1}}(\alpha)I_{j_{2}}(\alpha)}\right]-\mathbb{E}\left[{W_{j_{1}}(\alpha)W_{j_{2}}(\alpha)}\right]\big{|}$
$\displaystyle=~{}$ $\displaystyle\Big{|}\mathbb{P}\Big{(}\max_{e\in
N_{0j_{1}}}\sqrt{n}|\widetilde{\bm{\Theta}}^{\text{d}}_{e}|\geq\widehat{c}(\alpha,N_{0j_{1}}),\max_{e\in
N_{0j_{2}}}\sqrt{n}|\widetilde{\bm{\Theta}}^{\text{d}}_{e}|\geq\widehat{c}(\alpha,N_{0j_{2}})\Big{)}$
$\displaystyle-\mathbb{P}\Big{(}\max_{e\in N_{0j_{1}}}|Z_{e}|\geq
c(\alpha,N_{0j_{1}}),\max_{e\in N_{0j_{1}}}|Z_{e}|\geq
c(\alpha,N_{0j_{2}})\Big{)}\Big{|}$
$\displaystyle\begin{split}=~{}&\Big{|}\mathbb{P}\Big{(}T_{N_{0j_{1}}}\geq\widehat{c}(\alpha,N_{0j_{1}}),T_{N_{0j_{2}}}\geq\widehat{c}(\alpha,N_{0j_{2}})\Big{)}\\\
~{}~{}&-\mathbb{P}\Big{(}\max_{e\in N_{0j_{1}}}|Z_{e}|\geq
c(\alpha,N_{0j_{1}}),\max_{e\in N_{0j_{1}}}|Z_{e}|\geq
c(\alpha,N_{0j_{2}})\Big{)}\Big{|},\end{split}$ (A.35)

where the second equality holds by the definition of $T_{E}$ in (A.3) and the
definitions of $N_{0j_{1}},N_{0j_{2}}$. Now proving the bound in (A.34) is
reduced to showing

$\displaystyle\begin{split}&\Big{|}\mathbb{P}\Big{(}T_{N_{0j_{1}}}\geq\widehat{c}(\alpha,N_{0j_{1}}),T_{N_{0j_{2}}}\geq\widehat{c}(\alpha,N_{0j_{2}})\Big{)}-\mathbb{P}\Big{(}\max_{e\in
N_{0j_{1}}}|Z_{e}|\geq c(\alpha,N_{0j_{1}}),\max_{e\in N_{0j_{1}}}|Z_{e}|\geq
c(\alpha,N_{0j_{2}})\Big{)}\Big{|}\\\
~{}~{}&\leq{\eta(d,n,\zeta_{1},\zeta_{2},\alpha_{L})}{\alpha}.\end{split}$
(A.36)

We first relate the notations in the above expression to the notations in
Appendix C: $T_{N_{0j_{1}}},T_{N_{0j_{2}}}$ correspond to $T$;
$\widehat{c}(\alpha,N_{0j_{1}}),\widehat{c}(\alpha,N_{0j_{2}})$ correspond to
$q_{\xi}(\alpha,T^{\mathcal{B}})$; $\max_{e\in N_{0j_{1}}}|Z_{e}|,\max_{e\in
N_{0j_{2}}}|Z_{e}|$ correspond to $T_{\bm{Z}}$;
$c(\alpha,N_{0j_{1}}),c(\alpha,N_{0j_{2}})$ correspond to
$q(\alpha;T_{\bm{Z}})$. In Appendix C, we prove Propositions C.1 and C.2. And
the strategy can be used to derive the bound on (A.35). First, we note that
$T_{N_{0j_{1}}},T_{N_{0j_{2}}}$ satisfy the conditions of Proposition C.2,
i.e., (C.4) and (C.5). This is due to the same derivations as the first
parapraph of the proof of Lemmma A.2. Since the proving strategy is quite
similar, we omit the proof of (A.36) for simplicity. Instead, we prove (A.37),
i.e., when $\alpha\in[\alpha_{L},1]$,

$\displaystyle\begin{split}\mathrm{D}:=~{}&\Big{|}\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{1}}),T_{\bm{Y}_{2}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{2}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}}),T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\Big{|}\\\ \leq~{}&C\alpha\left(\frac{(\log
d)^{11/6}}{n^{1/6}\alpha_{L}^{1/3}}+\frac{(\log
d)^{19/6}}{n^{1/6}}\right),\end{split}$ (A.37)

where $T_{\bm{Y}_{1}},T_{\bm{Y}_{2}}$ correspond to $\breve{T}_{E}$ with
$E=N_{0j_{1}},N_{0j_{2}}$ respectively, $T_{\bm{W}_{1}},T_{\bm{W}_{2}}$
correspond to $\breve{T}_{E}^{\mathcal{B}}$ with $E=N_{0j_{1}},N_{0j_{2}}$
respectively, and $T_{\bm{Z}_{1}}=\max_{e\in
N_{0j_{1}}}|Z_{e}|,T_{\bm{Z}_{2}}=\max_{e\in N_{0j_{2}}}|Z_{e}|$. As for the
quantiles, $q_{\xi}(\alpha;T_{\bm{W}_{1}}),q_{\xi}(\alpha;T_{\bm{W}_{2}})$ are
the Gaussian multiplier bootstrap quantiles based on
$T_{\bm{W}_{1}},T_{\bm{W}_{2}}$.
$q(\alpha;T_{\bm{Z}_{1}}),q(\alpha;T_{\bm{Z}_{2}})$ are the quantiles of the
Gaussian maxima $T_{\bm{Z}_{1}},T_{\bm{Z}_{2}}$. Denote
$A_{1}=\\{T_{\bm{Y}_{1}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{1}})\\},A_{2}=\\{T_{\bm{Y}_{2}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{2}})\\}$, $B_{1}=\\{T_{\bm{Y}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})\\}$, $B_{2}=\\{T_{\bm{Y}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})\\}$, we have

$\displaystyle\mathrm{D}_{12}~{}:=~{}$
$\displaystyle\big{|}\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{1}}),T_{\bm{Y}_{2}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{2}})}\right)-\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}}),T_{\bm{Y}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\big{|}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\left({(A_{1}\cap A_{2})\ominus(B_{1}\cap
B_{2})}\right)$ $\displaystyle=~{}$ $\displaystyle\mathbb{P}\left({(A_{1}\cap
A_{2})\cap(B_{1}^{c}\cup B_{2}^{c})}\right)+\mathbb{P}\left({(B_{1}\cap
B_{2})\cap(A_{1}^{c}\cup A_{2}^{c})}\right)$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\left({A_{1}\cap
B_{1}^{c}}\right)+\mathbb{P}\left({A_{2}\cap
B_{2}^{c}}\right)+\mathbb{P}\left({B_{1}\cap
A_{1}^{c}}\right)+\mathbb{P}\left({B_{2}\cap A_{2}^{c}}\right)$
$\displaystyle=~{}$ $\displaystyle\mathbb{P}\left({(A_{1}\cap
B_{1}^{c})\cup(B_{1}\cap A_{1}^{c})}\right)+\mathbb{P}\left({(A_{2}\cap
B_{2}^{c})\cup(B_{2}\cap A_{2}^{c})}\right)$ $\displaystyle=~{}$
$\displaystyle\mathbb{P}\left({A_{1}\ominus
B_{1}}\right)+\mathbb{P}\left({A_{2}\ominus B_{2}}\right).$ (A.38)

By (C.14) and (C.15), we can bound (A.38) as

$\mathrm{D}_{12}\leq\mathbb{P}\left({A_{1}\ominus
B_{1}}\right)+\mathbb{P}\left({A_{2}\ominus
B_{2}}\right)\leq~{}2C^{\prime}\alpha\left(\frac{(\log
d)^{11/6}}{n^{1/6}\alpha_{L}^{1/3}}+\frac{(\log d)^{19/6}}{n^{1/6}}\right).$
(A.39)

By the triangle inequality, we have the following bound on $\mathrm{D}$,

$\displaystyle\mathrm{D}=~{}$
$\displaystyle\Big{|}\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{1}}),T_{\bm{Y}_{2}}\geq
q_{\xi}(\alpha;T_{\bm{W}_{2}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}}),T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\Big{|}$ $\displaystyle\leq~{}$
$\displaystyle\mathrm{D}_{12}+{\Big{|}\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}}),T_{\bm{Y}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}}),T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\Big{|}}.$ $\displaystyle\leq~{}$
$\displaystyle\mathrm{D}_{12}+\Big{|}\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})}\right)\big{|}+\big{|}\mathbb{P}\left({T_{\bm{Y}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\Big{|}$
$\displaystyle~{}+\underbrace{\Big{|}\mathbb{P}\left({\\{T_{\bm{Y}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})\\}\cup\\{T_{\bm{Y}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})\\}}\right)-\mathbb{P}\left({\\{T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})\\}\cup\\{T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})\\}}\right)\Big{|}}_{\mathrm{D}^{\prime}_{12}},$
(A.40)

where the last inequality holds since $\mathbb{P}\left({A\cap
B}\right)=\mathbb{P}\left({A}\right)+\mathbb{P}\left({B}\right)-\mathbb{P}\left({A\cup
B}\right)$. For the second term and the third term in (A.40), we can directly
apply the results (C.10) in Proposition C.1 and bound them as

$\displaystyle\begin{split}~{}~{}&\Big{|}\mathbb{P}\left({T_{\bm{Y}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})}\right)\big{|}+\big{|}\mathbb{P}\left({T_{\bm{Y}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)-\mathbb{P}\left({T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\Big{|}\\\ ~{}~{}&\leq C\alpha\cdot\frac{(\log
d)^{19/6}}{n^{1/6}}\end{split}$ (A.41)

for some constant $C$. Regarding the term $\mathrm{D}^{\prime}_{12}$, we
assume $q(\alpha;T_{\bm{Z}_{2}})=q(\alpha;T_{\bm{Z}_{2}}):=t$ without loss of
generality. This is because
$q(\alpha;T_{\bm{Z}_{1}}),q(\alpha;T_{\bm{Z}_{2}})$ are all deterministic
values and we can rescale the random vector inside one of the maximum
statistics $T_{\bm{Z}_{1}},T_{\bm{Z}_{2}}$. Now we rewrite
$\mathrm{D}^{\prime}_{12}$ based on
$q(\alpha;T_{\bm{Z}_{2}})=q(\alpha;T_{\bm{Z}_{2}})=t$ and derive the following
bound:

$\displaystyle\mathrm{D}^{\prime}_{12}$ $\displaystyle=$
$\displaystyle\Big{|}\mathbb{P}\left({\max\\{T_{\bm{Y}_{1}},T_{\bm{Y}_{2}}\\}\geq
t}\right)-\mathbb{P}\left({\max\\{T_{\bm{Z}_{1}},T_{\bm{Z}_{2}}\\}\geq
t}\right)\Big{|}$ $\displaystyle\leq$
$\displaystyle\frac{C^{\prime\prime}(\log
d)^{19/6}}{n^{1/6}}\cdot\mathbb{P}\left({\max\\{T_{\bm{Z}_{1}},T_{\bm{Z}_{2}}\\}\geq
t}\right)$ $\displaystyle\leq$ $\displaystyle\frac{C^{\prime\prime}(\log
d)^{19/6}}{n^{1/6}}\cdot\big{(}\mathbb{P}\left({T_{\bm{Z}_{1}}\geq
q(\alpha;T_{\bm{Z}_{1}})}\right)+\mathbb{P}\left({T_{\bm{Z}_{2}}\geq
q(\alpha;T_{\bm{Z}_{2}})}\right)\big{)}$ $\displaystyle=$ $\displaystyle
2C^{\prime\prime}\alpha\cdot\frac{(\log d)^{19/6}}{n^{1/6}},$ (A.43)

where the first inequality holds by applying Corollary 5.1 of Kuchibhotla et
al. (2021) similarly as in the derivation of (C.10). Here we briefly explain
why Corollary 5.1 of Kuchibhotla et al. (2021) is applicable to (A.2). Note
that $\max\\{T_{\bm{Y}_{1}},T_{\bm{Y}_{2}}\\}={T_{\bm{Y}_{12}}}$ is the
maximum statistic with respect to the random vectors which concatenate the
random vectors involved in $T_{\bm{Y}_{1}},T_{\bm{Y}_{2}}$. Write
$T_{\bm{Y}_{1}},T_{\bm{Y}_{2}}$ explicitly as

$T_{\bm{Y}_{1}}:=\left\|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bm{Y}^{(1)}_{i}\right\|_{\infty},\quad
T_{\bm{Y}_{2}}:=\left\|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bm{Y}^{(2)}_{i}\right\|_{\infty},$

and denote $\bm{Y}^{(12)}_{i}=(\bm{Y}^{(1)}_{i},\bm{Y}^{(2)}_{i})$, then
$T_{\bm{Y}_{12}}$ is defined as

$T_{\bm{Y}_{12}}:=\left\|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bm{Y}^{(12)}_{i}\right\|_{\infty}.$

By the definition of $\bm{Z}_{1},\bm{Z}_{2}$, we have ${\rm
Cov}((\bm{Z}_{1}^{\top},\bm{Z}_{2}^{\top})^{\top})={\rm
Cov}((\bm{Y}_{1}^{\top},\bm{Y}_{2}^{\top})^{\top})$. Hence we can apply
Corollary 5.1 of Kuchibhotla et al. (2021) to (A.2). Now we combine (A.39),
(A.40), (A.41) with (A.43) and obtain the following bound

$\mathrm{D}\leq C\alpha\left(\frac{(\log
d)^{11/6}}{n^{1/6}\alpha_{L}^{1/3}}+\frac{(\log d)^{19/6}}{n^{1/6}}\right),$

for some constant $C$, thus (A.37) is established. The above strategy of
obtaining (A.37) can be similarly applied to the term in (A.35), then
establishes the bound in (A.34).

∎

###  A.3 Proof of Theorem 4.2

###### Proof of Theorem 4.2.

Throughout the proof, we condition on the design matrix $\bm{X}$, but without
explicitly writing it out in order to simplify the notation. In the context of
selecting hub response variables, we recall
$\mathcal{H}_{0}=\\{j\in[d_{1}]:||\bm{\Theta}_{j}||_{0}\geq k_{\tau}\\}$ and
$d_{0}=|\mathcal{H}_{0}|$. For a non-hub response variable
$j\in\mathcal{H}_{0}$, let $N_{0j}$ be the set of its null covariates, i.e.,
$N_{0j}=\\{(j,k):\bm{\Theta}_{jk}=0\\}$.

To establish FDR control, we follow the same derivations as in the proof of
Theorem 5.2. Specifically, it suffices to bound

$\displaystyle\sum_{m=1}^{\lambda_{d}}\frac{\mathbb{\operatorname{{\rm
Var}}}[\sum_{j\in\mathcal{H}_{0}}I_{j}(\alpha_{m})-d_{0}\alpha_{m}]}{\epsilon^{2}d_{0}^{2}\alpha_{m}^{2}}+\sum_{m=1}^{\lambda_{d}}\frac{(\mathbb{E}[\sum_{j\in\mathcal{H}_{0}}I_{j}(\alpha_{m})-d_{0}\alpha_{m}])^{2}}{\epsilon^{2}d_{0}^{2}\alpha_{m}^{2}}$
(A.44)
$\displaystyle+\sum_{m=1}^{\lambda_{d}}\frac{\sum_{j_{1},j_{2}\in\mathcal{H}_{0},j_{1}\neq
j_{2}}\operatorname{\rm
Cov}(I_{j_{1}}(\alpha_{m}),I_{j_{2}}(\alpha_{m}))}{\epsilon^{2}d_{0}^{2}\alpha_{m}^{2}}:=\mathrm{III}_{1}+\mathrm{III}_{2}+0$

for any $\epsilon>0$. In the above terms, the sequence
$\\{\alpha_{m}\\}_{m=1}^{\lambda_{d}}$ is chosen similarly as in the proof of
Theorem 5.2 and $I_{j}(\alpha)$ is defined as

$I_{j}(\alpha)=\mathds{1}{(\max_{e\in
N_{0j}}\sqrt{n}|\widetilde{\bm{\Theta}}^{\text{d}}_{e}|\geq\widehat{c}(\alpha,N_{0j}))},$

where $\widetilde{\bm{\Theta}}^{\text{d}}_{j}$ is the debiased Lasso estimator
defined in (4.2). Note that the cross term in (A.44) equals zero as
$\operatorname{\rm Cov}(I_{j_{1}}(\alpha_{m}),I_{j_{2}}(\alpha_{m}))=0$. This
is because $\bm{Y}^{(j)},j\in[d_{1}]$ are conditionally independent given
$\mathbf{X}$. Therefore it suffices to bound $\mathrm{III}_{1}$ and
$\mathrm{III}_{2}$. By applying Lemma A.2 with the term
$\eta(d,n,\zeta_{1},\zeta_{2},\alpha_{L})$ replaced by
$\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\alpha_{L})$ in Lemma A.8, (A.44)
can be controlled by

$\mathrm{III}_{2}+\mathrm{III}_{2}\leq\frac{C^{\prime}t_{\lambda_{d_{2}}}}{\epsilon^{2}h_{d_{2}}}\left(\frac{d_{1}}{d_{0}|\mathcal{B}|}+\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\alpha_{L})\right),$

where $\alpha_{L}=q|\mathcal{B}|/d_{1}$ and $t_{\lambda_{d_{2}}},h_{d_{2}}$
are similarly defined as in the proof of Theorem 5.2. According to Lemma A.8,
we have the explicit form of
$\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\delta,\alpha_{L})$:

$\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\delta,\alpha_{L})=\zeta_{1}\log
d_{2}+(\log d_{2})^{5/2}\delta^{1/2}+\frac{\eta+\zeta_{2}}{\alpha_{L}},$

where $\zeta_{1}=O({s\log d_{2}}/{\sqrt{n}})$,
$\zeta_{2}=O(e^{-c_{1}n}+d_{2}^{-\widetilde{c_{0}}\wedge c_{2}})$, $\delta$
satisfies $\frac{1}{\delta}\sqrt{\frac{s\log d_{2}}{n}}=O(1)$ and
$\eta=e^{-c_{1}n}+\frac{1}{d_{2}}+\frac{1}{n\delta^{2}}$. By rearranging, we
obtain the following bound on $\mathrm{III}_{2}+\mathrm{III}_{2}$:

$\frac{\log d_{2}}{\epsilon^{2}}\left(\frac{1}{d_{0}\rho}+\frac{s(\log
d_{2})^{2}}{n^{1/2}}+(\log
d_{2})^{5/2}\delta^{1/2}+\frac{1}{n\delta^{2}\rho}+\frac{1}{\rho}\big{(}\frac{1}{d_{2}}+{e^{-c_{1}n}+d_{2}^{-\widetilde{c_{0}}\wedge
c_{2}}}\big{)}\right).$

where $\rho=\mathcal{B}/d_{1}$. We choose $\delta$ to be
$\frac{1}{(n\rho)^{2/5}\log d_{2}}$ and have $\delta>\frac{1}{n^{2/5}\log
d_{2}}$ (since $\rho<1$). Thus this choice of $\delta$ satisfies the
requirement in Lemma A.8. Finally we have $\eqref{eq:linear_cross_term}$ is
bounded as

$\frac{\log d_{2}}{\epsilon^{2}}\left(\frac{1}{d_{0}\rho}+\frac{s(\log
d_{2})^{2}}{n^{1/2}}+\frac{(\log d_{2})^{2}}{(n\rho)^{1/5}}+\frac{1}{\rho
d_{2}}\right).$

Under the stated assumption in Theorem 4.2, the above term is $o(1)$. Thus the
FDP control result is established. Due to similar derivations as in Theorem
5.2, the FDR control result follows. ∎

###  A.4 Ancillary lemmas for Theorem 4.2

To prove FDR control, we will establish a key result, i.e., Lemma A.8 in this
section. Recall that in Section 4, we utilize the following result

$\sqrt{n}(\widetilde{\bm{\Theta}}^{\text{d}}_{j}-\bm{\Theta}_{j})=Z_{j}+\Xi,\quad
Z_{j}|\bm{X}\sim\mathcal{N}(0,\sigma_{j}^{2}M\widehat{\bm{\Sigma}}M^{\top}).$

and approximate the quantile of the maximum statistics $T_{E}=\max_{(j,k)\in
E}\sqrt{n}|\widetilde{\bm{\Theta}}^{\text{d}}_{jk}|$ by
$T_{E}^{\mathcal{N}}=\max_{(j,k)\in E}|Z_{jk}|$. Lemma A.8 basically
establishes the Cramér deviation bounds for such quantile approximation. Note
that this lemma can be seen as a special case of Proposition C.1 since the
involving random vector
$\sqrt{n}(\widetilde{\bm{\Theta}}^{\text{d}}_{j}-\bm{\Theta}_{j})$ can be
decomposed into a Gaussian random vector plus some error term. Hence we do not
need to use the results in Kuchibhotla et al. (2021) to handle the case of a
general random vector (and quantify Gaussian approximation errors).

In this section, we will define some notations similar to the theoretical
results in Appendix C. First, we will drop the $j$-th subscript for
simplicity. Without loss of generality, we prove relevant results for
$E=\\{(j,k):k\in[d_{2}]\\}$ and drop the subscript $E$. Note the results hold
for any $j\in[d_{1}]$ and any subset of $\\{(j,k):k\in[d_{2}]\\}$. Now we
rewrite (4.4) using new notations, i.e.,

$\sqrt{n}(\widetilde{\bm{\Theta}}^{\text{d}}_{j}-\bm{\Theta}_{j})=\bm{Z}+\Xi,\quad\bm{Z}|\bm{X}\sim\mathcal{N}(0,\sigma_{j}^{2}M\widehat{\bm{\Sigma}}M^{\top}),$
(A.45)

and denote its maximum by $T_{\bm{Z}}=||\bm{Z}||_{\infty}$. Intuitively, we
can use the quantile of $T_{\bm{Z}}$ to approximate the quantile of
$T:=\sqrt{n}||\widetilde{\bm{\Theta}}^{\text{d}}_{j}-\bm{\Theta}_{j}||_{\infty}$.
Since the covariance matrix $\sigma_{j}^{2}M\widehat{\bm{\Sigma}}M^{\top}$ of
the Gaussian random vector $\bm{Z}$ is not completely known, we can not
directly compute its quantile (denoted by $q(\alpha;\bm{Z})$). Instead, we
first estimate the unknown parameter $\sigma_{j}$ by $\widehat{\sigma}_{j}$,
which is constructed according to (4.5). Then we define
$\bm{W}\sim\mathcal{N}(0,\widehat{\sigma}_{j}^{2}M\widehat{\bm{\Sigma}}M^{\top})$
(given the data $\bm{X},\bm{Y}^{(j)}$), and denote its maximum by
$T_{\bm{W}}=||W||_{\infty}$. We will approximate the unknown quantile of $T$
by the conditional quantile $q_{\xi}(\alpha;T_{\bm{W}})$. Here we use the
$\xi$ subscript to emphasize that we are conditioning on the data when
defining such quantiles.

Due to the existence of the term $\Xi$ in (A.45), there also exist additional
estimation errors when we approximate the quantiles of $T$ by the conditional
quantiles $q_{\xi}(\alpha;T_{\bm{W}})$. Lemma A.7 characterizes such
approximation errors. As for the difference between the distributions of the
two Gaussian random vectors $\bm{W}$ and $\bm{Z}$, Lemma A.7 provides a bound
on the maximal difference of their covariance matrices, which is denoted by
$\Delta_{\infty}$. Finally, Lemma A.8 builds on these results and establishes
the Cramér-type deviation bounds for the quantile approximation of $T$.

######  Lemma A.6.

In the context of multiple linear models, we have

$\mathbb{P}(|T-T_{\bm{Z}}|>\zeta_{1})<\zeta_{2},$

where $\zeta_{1}=O({s\log d_{2}}/{\sqrt{n}})$ and
$\zeta_{2}=O(e^{-c_{1}n}+d_{2}^{-\widetilde{c_{0}}\wedge c_{2}})$.

###### Proof of Lemma A.6.

By Theorem 2.5 in Javanmard and Montanari (2014a), we have

$\displaystyle\sqrt{n}(\widetilde{\bm{\Theta}}^{\text{d}}_{j}-\bm{\Theta}_{j})=\bm{Z}+\Xi,\quad\bm{Z}|\bm{X}\sim\mathcal{N}(0,\sigma_{j}^{2}M\widehat{\bm{\Sigma}}M^{\top}),$

and

$\displaystyle\mathbb{P}\left(\|\Xi\|_{\infty}\geq\Big{(}\frac{16ac\,\sigma}{C_{\rm
min}}\Big{)}\frac{s\log d_{2}}{\sqrt{n}}\right)\leq
4\,e^{-c_{1}n}+4\,d_{2}^{-\widetilde{c_{0}}\wedge c_{2}}\,.$

Thus we immediately obtain the following bound on the difference between $T$
and $T_{\bm{Z}}$:

$\mathbb{P}(|T-T_{\bm{Z}}|>\zeta_{1})<\zeta_{2}$

where $\zeta_{1}=O({s\log d_{2}}/{\sqrt{n}})$ and
$\zeta_{2}=O(e^{-c_{1}n}+d_{2}^{-\widetilde{c_{0}}\wedge c_{2}})$. ∎

######  Lemma A.7.

For the the maximal difference term
$\Delta_{\infty}=||\widehat{\sigma}^{2}M\widehat{\bm{\Sigma}}M^{\top}-\sigma^{2}M\widehat{\bm{\Sigma}}M^{\top}||_{\max}$,
we have

$\mathbb{P}\left({\Delta_{\infty}\geq\delta}\right)\leq\eta,$ (A.46)

where $\delta$ satisfies $\frac{1}{\delta}\sqrt{\frac{s\log d_{2}}{n}}=O(1)$
and $\eta=O\left(e^{-c_{1}n}+\frac{1}{d_{2}}+\frac{1}{n\delta^{2}}\right)$.

###### Proof of Lemma A.7.

To bound $\Delta_{\infty}$, we start with the term
$|\widehat{\sigma}/{\sigma}-1|$. First we denote

$\mathcal{E}_{n}=\mathcal{E}_{n}(\phi_{0},s_{0},K):=\Big{\\{}\bm{X}\in\mathbb{R}^{n\times
d_{1}}:\min_{S:|S|\leq
s_{0}}\phi(\widehat{\bm{\Sigma}},S)\geq\phi_{0},\max_{j\in[d_{1}]}\bm{\Sigma}_{jj}\leq
K,\bm{\Sigma}=(\bm{X}^{\top}\bm{X})/n\Big{\\}}$

similarly as in Theorem 7.(a) of Javanmard and Montanari (2014a), where
$\phi(\widehat{\bm{\Sigma}},S)$ is the compatibility constant as defined in
Definition 1 of Javanmard and Montanari (2014a). Following the proof of Lemma
$14$ in Javanmard and Montanari (2014a), we have

$\displaystyle\mathbb{P}\left({\Big{|}\frac{\widehat{\sigma}}{\sigma}-1\Big{|}\geq\epsilon}\right)$
$\displaystyle~{}\leq\mathbb{P}\left({\bm{X}\notin\mathcal{E}_{n}}\right)+\sup_{\bm{X}\in\mathcal{E}_{n}}\mathbb{P}\Big{(}\Big{|}\frac{\widehat{\sigma}}{\sigma}-1\Big{|}\geq\epsilon\,\Big{|}\,\bm{X}\Big{)}$
$\displaystyle~{}\leq
4e^{-c_{1}n}+\sup_{\bm{X}\in\mathcal{E}_{n}}\mathbb{P}\Big{(}\frac{||\bm{X}^{\top}\bm{E}||_{\infty}}{n\sigma^{\star}}\geq{\widetilde{\lambda}}/{4}\,\Big{|}\,\bm{X}\Big{)}+\sup_{\bm{X}\in\mathcal{E}_{n}}\mathbb{P}\Big{(}\Big{|}\frac{{\sigma}^{\star}}{\sigma}-1\Big{|}\geq\frac{\epsilon}{10}\,\Big{|}\,\bm{X}\Big{)}$
(A.47)

where $\widetilde{\lambda}=10\sqrt{(2\log d_{2})/n}$, $\sigma^{\star}$ is the
oracle estimator of $\sigma$ introduced in Sun and Zhang (2012) and $\epsilon$
satisfies
$\frac{2\sqrt{s}\widetilde{\lambda}}{\sigma^{\star}\phi_{0}}\leq\frac{\epsilon}{2}<a_{0}$.

Now we separately bound the last two terms in (A.47). The second term in
(A.47) can be bounded by the derivation in the proof of Theorem 2 (ii) (Sun
and Zhang, 2012), i.e.,

$\displaystyle\sup_{\bm{X}\in\mathcal{E}_{n}}\mathbb{P}\Big{(}\frac{||\bm{X}^{\top}\bm{E}||_{\infty}}{n\sigma^{\star}}\geq{\widetilde{\lambda}}/{4}\,\Big{|}\,\bm{X}\Big{)}$
$\displaystyle\leq$ $\displaystyle
d_{2}\mathbb{P}\Big{(}|L_{k}|\geq\sqrt{{2\log(d_{2}^{25/4})}/{n}}\,\Big{|}\,\bm{X}\Big{)}$
(A.48) $\displaystyle\leq$ $\displaystyle
d_{2}\cdot\frac{C}{d_{2}^{25/4}\sqrt{\log d_{2}}}\leq\frac{C}{d_{2}},$

where $L_{k}$ is the $k$-th element of
$\frac{\bm{X}^{\top}\bm{E}}{n\sigma^{\star}}$ and
$\frac{\sqrt{n-1}L_{k}}{\sqrt{1-L_{k}^{2}}}$ follows the Student’s
t-distribution with $n-1$ degrees of freedom. Then (A.48) holds due to
equation (A7) in Sun and Zhang (2012) together with the union bound. As for
the last term in $\eqref{eq:noise_bound1}$, we note
$n(\sigma^{\star}/\sigma)^{2}$ follows the $\chi^{2}_{n}$ distribution
according to Sun and Zhang (2012). Thus by Markov’s inequality, we have

$\displaystyle\sup_{\bm{X}\in\mathcal{E}_{n}}\mathbb{P}\Big{(}\Big{|}\frac{{\sigma}^{\star}}{\sigma}-1\Big{|}\geq\frac{\epsilon}{10}\,\Big{|}\,\bm{X}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{C^{\prime}\mathbb{E}\left[{(n(\sigma^{\star}/\sigma)^{2}-n)^{2}}\right]}{n^{2}\epsilon^{2}}\leq\frac{2C^{\prime}}{n\epsilon^{2}}.$
(A.49)

Now we arrive at the following bound on $\Delta_{\infty}$:

$\displaystyle\mathbb{P}\Big{(}\Delta_{\infty}\geq(\epsilon^{2}+2\epsilon)\cdot\sigma^{2}||M\widehat{\bm{\Sigma}}M^{\top}||_{\max}\Big{)}$
$\displaystyle=$
$\displaystyle\mathbb{P}\Big{(}||\widehat{\sigma}^{2}M\widehat{\bm{\Sigma}}M^{\top}-\sigma^{2}M\widehat{\bm{\Sigma}}M^{\top}||_{\max}\geq{(\epsilon^{2}+2\epsilon)\cdot\sigma^{2}||M\widehat{\bm{\Sigma}}M^{\top}||_{\max}}\Big{)}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\Big{(}\Big{|}\frac{\widehat{\sigma}}{\sigma}-1\Big{|}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle
4e^{-c_{1}n}+\frac{C}{d_{2}}+\frac{2C^{\prime}}{n\epsilon^{2}},$

where the last inequality comes from combining (A.47), (A.48) with (A.49).
Note that the proof of Theorem 16 in Javanmard and Montanari (2014a) shows
that $||M\widehat{\bm{\Sigma}}M^{\top}||_{\max}=O(1)$. Hence, we finally
establish (A.46) with

$\delta={\sigma^{2}(\epsilon^{2}+2\epsilon)}{||M\widehat{\bm{\Sigma}}M^{\top}||_{\max}}=C_{\sigma}\epsilon,\quad\eta=O\left(e^{-c_{1}n}+\frac{1}{d_{2}}+\frac{1}{n\delta^{2}}\right).$

where $C_{\sigma}$ is some constant and $\delta=C_{\sigma}\epsilon$ satisfies
$\frac{1}{\delta}\sqrt{\frac{s\log d_{2}}{n}}=O(1)$ due to the choice of
$\epsilon$. ∎

######  Lemma A.8.

Based on the result about the approximation error between $T$ and $T_{\bm{Z}}$
(Lemma A.6) and the bound on $||\Delta||_{\infty}$ in Lemma A.7, we have

$\sup_{\alpha\in[\alpha_{L},1]}\left|\frac{\mathbb{P}(T>q(\alpha;T_{\bm{W}}))}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|=O\left(\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\delta,\alpha_{L})\right),$
(A.50)

where
$\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\delta,\alpha_{L}):=\zeta_{1}\log
d_{2}+(\log d_{2})^{5/2}\delta^{1/2}+\frac{\eta+\zeta_{2}}{\alpha_{L}}$ with
$\zeta_{1}=O({s\log d_{2}}/{\sqrt{n}})$,
$\zeta_{2}=O(e^{-c_{1}n}+d_{2}^{-\widetilde{c_{0}}\wedge c_{2}})$. Here
$\delta$ is a term to be determined and we requite
$\frac{1}{\delta}\sqrt{\frac{s\log d_{2}}{n}}=O(1)$. $\eta$ depends on
$\delta$, i.e., $\eta=e^{-c_{1}n}+\frac{1}{d_{2}}+\frac{1}{n\delta^{2}}$.

###### Proof of Lemma A.8.

First we have $\mathbb{P}(|T-T_{\bm{Z}}|>\zeta_{1})<\zeta_{2}$ by Lemma A.6,
thus we obtain

$\left|\frac{\mathbb{P}(T>q(\alpha;T_{\bm{W}}))}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|\leq\max\\{\mathrm{II}_{1},\mathrm{II}_{2}\\}+\frac{2\zeta_{2}}{\alpha}$

for $\alpha\in[\alpha_{L},1]$, where $\mathrm{II}_{1}$ and $\mathrm{II}_{2}$
are defined as:

$\mathrm{II}_{1}:=\left|\frac{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{W}})+\zeta_{1})}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|,\quad\mathrm{II}_{2}:=\left|\frac{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{W}})-\zeta_{1})}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|.$

The above two terms can be bounded similarly. Take $\mathrm{II}_{1}$ as an
example, we use similar strategy as in Proposition C.1. Consider the event
$S:=\\{\Delta_{\infty}\leq\delta\\}$ where $\delta$ satisfies
$\frac{1}{\delta}\sqrt{\frac{s\log d_{2}}{n}}=O(1)$, we apply Lemma C.1 and
bound $\mathrm{II}_{1}$ by

$\frac{1}{1-\pi(\delta)}\cdot\mathrm{II}_{11}+\mathrm{II}_{12}+\frac{\mathbb{P}\left({\Delta_{\infty}>\delta}\right)}{\alpha},$

where $\mathrm{II}_{11}$ and $\mathrm{II}_{11}$ are defined as

$\displaystyle\mathrm{II}_{11}$ $\displaystyle:=$
$\displaystyle\frac{1-\pi(\delta)}{\alpha}\Big{|}\mathbb{P}\Big{(}T_{\bm{Z}}>q(\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}})+\zeta_{1}\Big{)}-\mathbb{P}(T_{\bm{Z}}>q(\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}}))\Big{|},$
$\displaystyle\mathrm{II}_{12}$ $\displaystyle:=$
$\displaystyle\frac{1}{\alpha}\Big{|}\mathbb{P}\Big{(}T_{\bm{Z}}>q(\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}})\Big{)}-\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))\Big{|},$
(A.51)

where $\pi(\Delta_{\infty})=[A(\Delta_{\infty})+1]e^{M_{1}(\log
d)^{3/2}A(\Delta_{\infty})}-1$. By applying the part 3 of Theorem 2.1 in
Kuchibhotla et al. (2021) (with
$r+\epsilon=q(\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}})+\zeta_{1},r-\epsilon=q(\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}})$)
to the Gaussian random vector $\bm{Z}$, we have

$\mathrm{II}_{11}\leq
K_{4}\zeta_{1}\big{(}q(\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}})+{\zeta_{1}}/{2}\big{)}\leq
C\zeta_{1}\log d_{2}.$ (A.52)

where the second inequality holds due to the similar reason stated in the
proof of Proposition C.2. And the term $\mathrm{II}_{11}$ can be simply
derived as

$\mathrm{II}_{12}=\frac{1}{\alpha}\Big{|}\frac{\alpha}{1-\pi(\delta)}-\alpha\Big{|}=\frac{\pi(\delta)}{1-\pi(\delta)}.$
(A.53)

Combing the results above, we have

$\left|\frac{\mathbb{P}(T>q(\alpha;T_{\bm{W}}))}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|\leq
C^{\prime}\zeta_{1}\log
d_{2}+\frac{\pi(\delta)}{1-\pi(\delta)}+\frac{\pi(\delta)}{1+\pi(\delta)}+\frac{2\mathbb{P}\left({\Delta_{\infty}>\delta}\right)}{\alpha}+\frac{2\zeta_{2}}{\alpha}.$

Applying the bound in Lemma A.7, we finally establish (A.50) i.e.,
$\eta_{0}(d_{1},d_{2},n,\zeta_{1},\zeta_{2},\alpha_{L}):=\zeta_{1}\log
d_{2}+(\log d_{2})^{5/2}\delta^{1/2}+\frac{\eta+\zeta_{2}}{\alpha_{L}}$ up to
some constant factor, where
$\eta=e^{-c_{1}n}+\frac{1}{d_{2}}+\frac{1}{n\delta^{2}}$. ∎

##  Appendix B Proofs of Cramér-type comparison bounds

In this section, we will prove two types of Cramér-type comparison bounds:
Theorems 3.1 and 3.2. One of the challenges to derive the comparison bounds
for Gaussian maxima is that the maximum function is non-smooth. In order to
show the Cramér-type comparison bound, we first consider smooth approximation
of the maximum. The following lemma from Bentkus (1990) show the existence of
such smooth approximation.

######  Lemma B.1 (Theorem 1, Bentkus (1990)).

Consider the Euclidean space $\mathbb{R}^{d}$ with $\ell_{\infty}$-norm, for
any $t,\epsilon\geq 0$, there exists a smooth approximating function
$\varphi_{r,\epsilon}$ satisfying the following:

  1. (a)

$\varphi_{r,\epsilon}:\mathbb{R}^{d}\rightarrow[0,1],\varphi_{r,\epsilon}\in\mathbb{C}^{\infty}$,
where $\mathbb{C}^{\infty}$ is the smooth function class with functions
differentiable for all degrees of differentiation.

  2. (b)

$\varphi_{r,\epsilon}(x)=1$ if $||x||_{\infty}\leq r$,
$\varphi_{r,\epsilon}(x)=0$ if $||x||_{\infty}\geq r+\epsilon$,

  3. (c)

$\sup_{x\in\mathbb{R}^{d}}||D^{j}\varphi_{r,\epsilon}(x)||_{1}\leq
c(j)\epsilon^{-j}\log^{j-1}(d+1)$,

where
$||D^{j}\varphi_{r,\epsilon}(x)||_{1}=\sum_{i_{1}=1}^{d}\cdots\sum_{i_{j}=1}^{d}\left|\frac{\partial^{j}\varphi_{r,\epsilon}(x)}{\partial
x_{i_{1}}\cdots\partial x_{i_{j}}}\right|$ and the constants $c(j)$ only
depends on $j$.

######  Remark B.1.

Kuchibhotla et al. (2021) gives a concrete example of
$\varphi_{r,\epsilon}(x)$ satisfying the three properties in Lemma B.1:

$\varphi_{r,\epsilon}(x)=g_{0}\left(\frac{2(F_{\beta}(z_{x}-r\mathbf{1}_{2d})-\epsilon/2)}{\epsilon}\right),$
(B.1)

where $\beta=2\log(2d)/\epsilon$, $g_{0}(t):=30\mathds{1}{(0\leq t\leq
1)}\int_{t}^{1}s^{2}(1-s)^{2}ds+\mathds{1}{(t\leq 0)}$, $F_{\beta}(\cdot)$ is
the “softmax” function

$F_{\beta}(z):=\frac{1}{\beta}\log\Big{(}\sum_{m=1}^{2d}\exp\left(\beta
z_{m}\right)\Big{)}\quad\text{ for }z\in\mathbb{R}^{2d},$

$z_{x}=(x^{\top},-x^{\top})^{\top}$, and $\mathbf{1}_{2d}$ is the vector of
$1$’s of dimension $2d$.

In fact, in the proof of Theorem 3.1, we do not need a specific form of
$\varphi_{r,\epsilon}(x)$ and any function satisfying Lemma B.1 will work.
While in the proof of Theorem 3.2, we need to utilize the specific form in
(B.1).

###  B.1 Proof of Theorem 3.1

As mentioned in Remark 3.1, we can prove the Cramér-type comparison bound with
max norm difference as $M_{3}(\log d)^{3/2}A(\Delta_{\infty})e^{M_{3}(\log
d)^{3/2}A(\Delta_{\infty})},$ without the assumption on $\Delta_{\infty}$.
Therefore we state the more general form of Theorem 3.1 below and give its
proof. Note that under the assumption $(\log d)^{5}\Delta_{\infty}=O(1)$ and
the discussions in Remark 3.1, the bound (3.1) in Theorem 3.1 immediately
follows from Theorem B.2.

######  Theorem B.2 (CCB with max norm difference).

Let $U$ and $V$ be two Gaussian random vectors and we have

$\sup_{0\leq t\leq C_{0}\sqrt{\log
d}}\left|\frac{\mathbb{P}(||U||_{\infty}>t)}{\mathbb{P}(||V||_{\infty}>t)}-1\right|\leq
M_{3}(\log d)^{3/2}A(\Delta_{\infty})e^{M_{1}(\log
d)^{3/2}A(\Delta_{\infty})},$ (B.2)

where $C_{0}>0$ is some constant, $A(\Delta_{\infty})=M_{1}\log
d\Delta_{\infty}^{1/2}\exp{(M_{2}\log^{2}d\Delta_{\infty}^{1/2})}$, the
constants $M_{1},M_{2}$ only depend on $\min_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\},\max_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$, and $M_{3}$ is a universal constant.

###### Proof of Theorem B.2.

Using the smooth approximation in Lemma B.1, we can bound the difference
between the distribution functions of Gaussian maxima as

$\displaystyle\big{|}\mathbb{P}(||U||_{\infty}>t)-\mathbb{P}(||V||_{\infty}>t)\big{|}$
(B.3) $\displaystyle=$
$\displaystyle\big{|}\mathbb{E}[\mathds{1}{(||U||_{\infty}\leq
t)}-\mathds{1}{(||V||_{\infty}\leq t)}]\big{|}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}(t-\epsilon\leq||V||_{\infty}\leq
t+\epsilon)+\max_{j=1,2}\left|\mathbb{E}\varphi_{j}(U)-\mathbb{E}\varphi_{j}(V)\right|,$

where
$\varphi_{1}(x):=\varphi_{t,\epsilon}(x),\varphi_{2}(x):=\varphi_{t-\epsilon,\epsilon}(x)$.
Regarding the inequality in (B.3), we first notice that

$\mathds{1}{(||x||_{\infty}\leq
t)}=\varphi_{t,\epsilon}(x)-\mathds{1}{(t<||x||_{\infty}<t+\epsilon)}\cdot\varphi_{t,\epsilon}(x)=\varphi_{t-\epsilon,\epsilon}(x)-\mathds{1}{(t-\epsilon<||x||_{\infty}<t)}\cdot\varphi_{t-\epsilon,\epsilon}(x),$

where the first equality is due to property (b) in Lemma B.1. Hence we have

$\displaystyle\mathds{1}{(||U||_{\infty}\leq t)}$ $\displaystyle\leq$
$\displaystyle\varphi_{j}(U),\quad j=1,2$
$\displaystyle\mathds{1}{(||V||_{\infty}\leq t)}$ $\displaystyle\geq$
$\displaystyle\varphi_{1}(V)-\mathds{1}{(t<\left\|V\right\|<t+\epsilon)},$
$\displaystyle\mathds{1}{(||V||_{\infty}\leq t)}$ $\displaystyle\geq$
$\displaystyle\varphi_{2}(V)-\mathds{1}{(t-\epsilon<\left\|V\right\|<t)},$

then (B.3) immediately follows by combining the above three inequalities.

The first term in (B.3) is related to the anti-concentration inequalities for
the Gaussian maxima. By applying Theorem 2.1 in Kuchibhotla et al. (2021), we
have

$\mathbb{P}(t-\epsilon\leq||V||_{\infty}\leq t+\epsilon)\leq
K_{1}(t+1)\epsilon\exp(K_{2}(t+1)\epsilon)\mathbb{P}(||V||_{\infty}>t).$ (B.4)

The explicit forms of $K_{1},K_{2}$ can be found in Theorem 2.1 of Kuchibhotla
et al. (2021). They only depend on $\min_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\},\max_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$ and the median of Gaussian maxima.
Remark that the median of $||V||_{\infty}$ is bounded by $O(\sqrt{\log d})$ by
the maximal inequalities for sub-Gaussian random variables (Lemma 5.2 in van
Handel (2014)). Plugging this into the explicit form of $K_{1},K_{2}$ in
Theorem 2.1 of Kuchibhotla et al. (2021), we have $K_{1}=O(\log
d),K_{2}=O({\log^{2}d})$. Then (B.4) can be written as

$\mathbb{P}(t-\epsilon\leq||V||_{\infty}\leq t+\epsilon)\leq M_{1}\log
d(t+1)\epsilon\exp({M_{2}\log^{2}d}~{}(t+1)\epsilon)\mathbb{P}(||V||_{\infty}>t),$

for some constants $M_{1},M_{2}$ only depending on $\min_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\},\max_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$.

Overall the above bound has only a logarithmic dependence on the dimension
$d$, similar to the anti-concentration bounds from Chernozhukov et al. (2014).
But it quantifies the deviation with respect to the tail probability of the
Gaussian maxima, thus offers a more refined characterization, which is crucial
to our proof.

Now we deal with the second term in (B.3). It is not hard to check that the
following proof works for both $\varphi_{1}$ and $\varphi_{2}$. Therefore,
without loss of generality, we use a unified notation $\varphi$ to represent
either functions. We consider the Slepian interpolation between $U$ and $V$:
$W(s):=\sqrt{s}U+\sqrt{1-s}V,~{}~{}s\in[0,1]$. Let
$\Psi_{t}(s)=\mathbb{E}[\varphi(W(s))]$, then we have

$\left|\mathbb{E}\varphi(U)-\mathbb{E}\varphi(V)\right|=|\Psi_{t}(1)-\Psi_{t}(0)|=\left|\int_{0}^{1}\Psi_{t}^{\prime}(s)ds\right|,$
(B.5)

where
$\Psi_{t}^{\prime}(s)=\frac{1}{2}\sum_{j=1}^{d}\mathbb{E}[\partial_{j}\varphi(W(s))(s^{-1/2}U_{j}-(1-s)^{-1/2}V_{j})]$.
Applying Stein’s identity (Lemma 2 of Chernozhukov et al. (2015)) to
$(s^{-1/2}U_{j}-(1-s)^{-1/2}V_{j},W(s)^{\top})^{\top}$ and
$\partial_{j}\varphi(W(s))$, we have

$\displaystyle\Psi_{t}^{\prime}(s)=\frac{1}{2}\sum_{j,k=1}^{d}(\sigma_{jk}^{U}-\sigma_{jk}^{V})\mathbb{E}[\partial_{j}\partial_{k}\varphi(W(s))].$
(B.6)

Hence we obtain the following bound on (B.5),

$\displaystyle\left|\int_{0}^{1}\Psi_{t}^{\prime}(s)ds\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j,k=1}^{d}|\sigma_{jk}^{U}-\sigma_{jk}^{V}|\cdot\left|\int_{0}^{1}\mathbb{E}[\partial_{j}\partial_{k}\varphi(W(s))]ds\right|$
(B.7) $\displaystyle\leq$
$\displaystyle\frac{\Delta_{\infty}}{2}\int_{0}^{1}\sum_{j,k=1}^{d}\mathbb{E}[\left|\partial_{j}\partial_{k}\varphi(W(s))\right|]ds$
$\displaystyle\leq$
$\displaystyle\frac{\Delta_{\infty}}{2}\int_{0}^{1}\sum_{j,k=1}^{d}\mathbb{E}[|\partial_{j}\partial_{k}\varphi(W(s))|\cdot\mathds{1}{(t-\epsilon\leq||W(s)||_{\infty}\leq
t+\epsilon)}]ds$ $\displaystyle\leq$
$\displaystyle\frac{\Delta_{\infty}}{2}\int_{0}^{1}\sup_{x\in\mathbb{R}^{d}}||D^{2}\varphi(x)||_{1}\cdot\mathbb{E}[\mathds{1}{(t-\epsilon\leq||W(s)||_{\infty}\leq
t+\epsilon))}]ds$ $\displaystyle\leq$
$\displaystyle\frac{c(2)\Delta_{\infty}\log(d+1)}{2\epsilon^{2}}\int_{0}^{1}\mathbb{P}(t-\epsilon\leq||W(s)||_{\infty}\leq
t+\epsilon)ds$

where the second inequality is by the definition of $\Delta_{\infty}$ and the
third one comes from the property (b) in Lemma B.1 for $\varphi_{j}(x),j=1,2$
(recalling $\varphi_{1}(x)=\varphi_{t,\epsilon}(x)$ and
$\varphi_{2}(x)=\varphi_{t-\epsilon,\epsilon}(x)$). Note that property (c)
gives a upper bound for the partial derivative terms. Thus the fourth
inequality holds.

By the definition of Slepian interpolation, we have, for any $s\in[0,1]$,
$W(s)$ is a Gaussian random vector and the variances can be controlled between
$\min_{1\leq j\leq d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$ and $\max_{1\leq
j\leq d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$. The median of
$||W(s)||_{\infty}$ can also be similarly bounded by $O(\sqrt{\log d})$ as
$||V||_{\infty}$. Applying the anti-concentration inequalities again to $W(s)$
in (B.7), we thus obtain

$\displaystyle\left|\int_{0}^{1}\Psi_{t}^{\prime}(s)ds\right|\leq\frac{c(2)\Delta_{\infty}\log(d+1)}{2\epsilon^{2}}\cdot
M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)\cdot\int_{0}^{1}\mathbb{P}(||W(s)||_{\infty}>t)ds.$
(B.8)

Let $Q_{t}(u)=\mathbb{P}(||W(u)||_{\infty}>t)$ and
$R_{t}(u)=Q_{t}(u)/Q_{t}(0)-1$. Combining (LABEL:eq:phi_smoothing), (B.4),
(B.5) and (B.8), we have

$\displaystyle|Q_{t}(1)-Q_{t}(0)|$ $\displaystyle=$
$\displaystyle\big{|}\mathbb{P}(||U||_{\infty}>t)-\mathbb{P}(||V||_{\infty}>t)\big{|}$
(B.9) $\displaystyle\leq$ $\displaystyle M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)Q_{t}(0)$
$\displaystyle+~{}\frac{c(2)\Delta_{\infty}\log(d+1)}{2\epsilon^{2}}M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)\int_{0}^{1}Q_{t}(s)ds.$

If starting with the interpolation between $W(s)$ and $V$ instead of that
between $U$ and $V$, we can similarly obtain the bound on
$|Q_{t}(s)-Q_{t}(0)|$. And the integral $\int_{0}^{1}Q_{t}(s)ds$ in (B.9) can
be directly replaced by $\int_{0}^{u}Q_{t}(s)ds$. Namely, we have

$\frac{|Q_{t}(u)-Q_{t}(0)|}{|Q_{t}(0)|}=|R_{t}(u)|\leq
A(t,\epsilon)B(\Delta_{\infty},\epsilon)\int_{0}^{u}|R_{t}(s)|ds+A(t,\epsilon)B(\Delta_{\infty},\epsilon)\cdot
u+A(t,\epsilon),$ (B.10)

where we denote $A(t,\epsilon)=M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)$ and
$B(\Delta_{\infty},\epsilon)=\frac{c(2)\Delta_{\infty}\log(d+1)}{2\epsilon^{2}}$.

Notice that (B.10) is an integral inequality and we can thus bound $R_{t}(s)$
by Grönwall’s inequality (Grönwall, 1919)

$|R_{t}(u)|\leq(A(t,\epsilon)B(\Delta_{\infty},\epsilon)u+A(t,\epsilon))e^{A(t,\epsilon)B(\Delta_{\infty},\epsilon)u}.$

In particular, we have
$|R_{t}(1)|\leq(A(t,\epsilon)B(\Delta_{\infty},\epsilon)+A(t,\epsilon))e^{A(t,\epsilon)B(\Delta_{\infty},\epsilon)}$.
Remember that $\epsilon$ is the smoothing parameter that controls the level of
approximation. Choosing $\epsilon=\Delta_{\infty}^{1/2}/(t+1)$, we then have
$A(\Delta_{\infty}):=A(t,\epsilon)=M_{1}\log
d\Delta_{\infty}^{1/2}\exp{(M_{2}\log^{2}d\Delta_{\infty}^{1/2})}$ for some
constants $M_{1},M_{2}$ only depending on $\min_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\},\max_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$ and
$B(t):=B(\Delta_{\infty},\epsilon)=\frac{c(2)\log(d+1)(t+1)^{2}}{2}$. When
$0\leq t\leq C_{0}\sqrt{\log d}$, we have $B(t)\leq M_{1}(\log d)^{3/2}$ for
some universal constant $M_{3}$. Therefore the bound in (B.2) is established,
i.e.,

$\sup_{0\leq t\leq C_{0}\sqrt{\log d}}|R_{t}(1)|\leq M_{3}(\log
d)^{3/2}A(\Delta_{\infty})e^{M_{3}(\log d)^{3/2}A(\Delta_{\infty})}.$

∎

###  B.2 Proof of Theorem 3.2

Before proving Theorem 3.2, we note its assumption about the connectivity can
be relaxed. Therefore, we first present Theorem B.4 with a weaker connectivity
assumption, which is stated below.

######  Assumption B.3 ($\mathfrak{p}$-connectivity property).

We say two Gaussian random vectors $U$ and $V$ satisfy the
$\mathfrak{p}$-connectivity property if for any $j$ such that
$\sigma^{U}_{jk}\neq\sigma^{V}_{jk}$ for some $k$, there exists a subset
$\mathcal{E}_{0}\subset[d]$ satisfying the following three requirements:

  1. (a)

$j\in\mathcal{E}_{0},|\mathcal{E}_{0}|=\mathfrak{p}+1$;

  2. (b)

When $m,m^{\prime}\in\mathcal{E}_{0}$ and $m\neq m^{\prime}$,
$\sigma^{U}_{mm}=\sigma^{U}_{m^{\prime}m^{\prime}}$ and
$\sigma^{U}_{mm^{\prime}}=\sigma^{V}_{mm^{\prime}}=0$ hold;

  3. (c)

$\forall~{}k\in[d]$,
$|\\{m\in\mathcal{E}_{0}:|\sigma^{U}_{km}|+|\sigma^{V}_{km}|\neq 0\\}|\leq
c_{0}$ for some constant $c_{0}$.

This assumption gives a characterization of the connectivity of the associated
graphs of the Gaussian random vectors $U$ and $V$. Below we give a few
sufficient conditions (SC) for it.

  1. SC1

$U$ and $V$ have unit variances. There exists a disjoint
$(\mathfrak{p}+2)$-partition of nodes
$\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}_{\ell}=[d]$ such that
$\sigma^{U}_{jk}=\sigma^{V}_{jk}=0$ when $j\in\mathcal{C}_{\ell}$ and
$k\in\mathcal{C}_{\ell^{\prime}}$ for some $\ell\neq\ell^{\prime}$.

  2. SC2

$U$ and $V$ have unit variances. There exist disjoint partitions of nodes
$\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}^{U}_{\ell}=\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}^{V}_{\ell}=[d],$
such that $\sigma^{U}_{jk}$ ($\sigma^{V}_{jk}$) equals $0$ when $j,k$ belong
to different elements $\mathcal{C}^{U}_{\ell}$ ($\mathcal{C}^{V}_{\ell}$), and
$\forall\ell\in[\mathfrak{p}+2]$,
$\mathcal{C}^{U}_{\ell}\cap\mathcal{C}^{V}_{\ell}\neq\varnothing$.

  3. SC3

$\forall~{}s\in[0,1]$, the Gaussian random vector
$W(s):=\sqrt{s}U+\sqrt{1-s}V$ always has the same variances $\sigma_{s}^{2}$
across different components. The associated graph of $W(s)$ has at least
$\mathfrak{p}+2$ components, i.e., there exists a disjoint partition of nodes
$\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}^{W}_{\ell}=[d]$, such that each
$\mathcal{C}^{W}_{\ell}$ comes from a different component. And the partition
$\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}^{W}_{\ell}=[d]$ works any
$s\in[0,1]$.

######  Remark B.2.

Note that the above first condition SC1 is the main assumption of Theorem 3.2
(except that $\mathfrak{p}+2$ is replaced by $\mathfrak{p}$). It is immediate
that the condition SC1 implies SC2. We will verify SC2 is indeed a sufficient
condition of Assumption B.3 in the following paragraph. Regarding SC3, its
sufficiency can be verified similarly, thus we omit the details.

Simply, we have $\sigma^{U}_{jj}=\sigma^{V}_{jj}=1,j\in[d]$ by the unit
variance assumption. For any $j$ such that
$\sigma^{U}_{jk}\neq\sigma^{V}_{jk}$ for some $k$, we will construct a subset
$\mathcal{E}_{0}$ and show it satisfies the three requirements (a), (b) and
(c). Note that the condition SC1 assumes the existence of disjoint partitions
of nodes
$\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}^{U}_{\ell}=\cup_{\ell=1}^{\mathfrak{p}+2}\mathcal{C}^{V}_{\ell}=[d]$.
We suppose $j\in\mathcal{C}^{U}_{\ell_{1}}\cap\mathcal{C}^{V}_{\ell_{2}}$ for
some $\ell_{1},\ell_{2}$, then $\mathcal{E}_{0}$ is constructed by including
$j$ and picking one element $m_{\ell}$ from
$\mathcal{C}^{U}_{\ell}\cap\mathcal{C}^{V}_{\ell}$ for each
$\ell\in[\mathfrak{p}+2]\setminus\\{\ell_{1},\ell_{2}\\}$. As
$\mathcal{C}^{U}_{\ell}\cap\mathcal{C}^{V}_{\ell}\neq\varnothing,\forall\ell\in[\mathfrak{p}+2]$,
we have $|\mathcal{E}_{0}|\geq 1+\mathfrak{p}$, hence the requirement (a) is
satisfied. Regarding the requirement (b), when
$m,m^{\prime}\in\mathcal{E}_{0},m\neq m^{\prime}$, we immediately have
$\sigma^{U}_{mm}=\sigma^{V}_{m^{\prime}m^{\prime}}=1$ by the unit variance
assumption. Since every element in $\mathcal{E}_{0}$ comes from a different
component $\mathcal{C}^{U}_{\ell}$ ($\mathcal{C}^{V}_{\ell}$), we also have
$\sigma^{U}_{mm^{\prime}}=\sigma^{V}_{mm^{\prime}}=0$ when
$m,m^{\prime}\in\mathcal{E}_{0},m\neq m^{\prime}$. Lastly, due to the same
reason, we have $\forall k\in[d]$,
$|\\{m\in\mathcal{E}_{0}:|\sigma^{U}_{km}|+|\sigma^{V}_{km}|\neq 0\\}|\leq 2$.
Hence the requirement (c) is also satisfied.

Now we prove Theorem B.4, which is stated below. Note that it requires weaker
connectivity assumption compared with Theorem 3.2 but needs to assume minimal
eigenvalue conditions.

######  Theorem B.4 (CCB with elementwise $\ell_{0}$ norm difference).

Consider the two Gaussian random vectors $U$ and $V$ to have equal variances
$\sigma^{U}_{jj}=\sigma^{V}_{jj}=O(1)$, for $j\in[d]$ and we assume
$\lambda_{\min}(\bm{\Sigma}^{U})\geq
1/b_{0}>0,\lambda_{\min}(\bm{\Sigma}^{V})\geq 1/b_{0}>0$ for some constant
$b_{0}>0$. Suppose $U$ and $V$ also satisfy Assumption B.3, we then have

$\sup_{0\leq t\leq C_{0}\sqrt{\log
d}}\left|\frac{\mathbb{P}(||U||_{\infty}>t)}{\mathbb{P}(||V||_{\infty}>t)}-1\right|=O\left(\frac{\Delta_{0}\log
d}{\mathfrak{p}}\right).$ (B.11)

for some constant $C_{0}>0$.

###### Proof of Theorem B.4.

Following the same derivations as in Theorem B.2, we have

$\displaystyle\left|\mathbb{P}(||U||_{\infty}>t)-\mathbb{P}(||V||_{\infty}>t)\right|$
(B.12) $\displaystyle\leq$ $\displaystyle M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)\mathbb{P}(||V||_{\infty}>t)+\max_{j=1,2}\left|\mathbb{E}[\varphi_{j}(U)]-\mathbb{E}[\varphi_{j}(V)]\right|$
$\displaystyle\leq$ $\displaystyle M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)\mathbb{P}(||V||_{\infty}>t)+\left|\int_{0}^{1}\Psi_{t}^{\prime}(s)ds\right|,$

where $\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log d\\}}$ for some
small enough constant $c>0$, and the constants $M_{1},M_{2}$ only depend on
$\min_{1\leq j\leq d}\\{\sigma^{U}_{jj}\\}$, $\max_{1\leq j\leq
d}\\{\sigma^{U}_{jj}\\}$. The above two inequalities hold by (B.3), (B.4) and
(B.5). We further bound $\left|\int_{0}^{1}\Psi_{t}^{\prime}(s)ds\right|$ as
below,

$\displaystyle\left|\int_{0}^{1}\Psi_{t}^{\prime}(s)ds\right|$ (B.13)
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j,k=1}^{d}|\sigma_{jk}^{U}-\sigma_{jk}^{V}|\left|\int_{0}^{1}\mathbb{E}[\partial_{j}\partial_{k}\varphi(W(s))]ds\right|$
$\displaystyle\leq$ $\displaystyle\frac{M}{2}\sum_{j\neq
k,\sigma^{U}_{jk}\neq\sigma^{V}_{jk}}\int_{0}^{1}\mathbb{E}[|\partial_{j}\partial_{k}\varphi(W(s))|]ds$
$\displaystyle\leq$ $\displaystyle\frac{M}{2}\sum_{j\neq
k,\sigma^{U}_{jk}\neq\sigma^{V}_{jk}}\int_{0}^{1}\mathbb{E}[|\partial_{j}\partial_{k}\varphi(W(s))|\cdot\mathds{1}{(t-\epsilon\leq||W(s)||_{\infty}\leq
t+\epsilon)}]ds$ $\displaystyle\leq$
$\displaystyle\frac{M\Delta_{0}}{2}\max_{j\neq
k,\sigma^{U}_{jk}\neq\sigma^{V}_{jk}}\int_{0}^{1}\mathbb{E}[|\partial_{j}\partial_{k}\varphi(W(s))|\cdot\mathds{1}{(t-\epsilon\leq||W(s)||_{\infty}\leq
t+\epsilon)}]ds,$

where the first inequality holds due to (B.6), the second inequality is
because $\sigma_{jk}^{U}=O(1),\sigma_{jk}^{V}=O(1)$ for all $j,k$ and the
constant $M$ only depends on the maximal variances of the elements of $U,V$,
the third inequality holds by the property (b) in Lemma B.1 for
$\varphi_{j}(x),j=1,2$, and the last inequality holds by the definition of
$\Delta_{0}$. Note that
$\varphi_{1}(x):=\varphi_{t,\epsilon}(x),\varphi_{2}(x):=\varphi_{t-\epsilon,\epsilon}(x)$
as defined in the proof of Theorem B.2. We use the same strategy to deal with
$\varphi_{1}(x)$ and $\varphi_{2}(x)$. Below we give the derivations when
$\varphi=\varphi_{1}(x)$ and it is not hard to check these derivations work
for $\varphi_{2}(x)$ as well. Recall the explicit construction of
$\varphi:\mathbb{R}^{d}\to\mathbb{R}$ introduced in Remark B.1,

$\varphi(x)=\varphi_{r,\epsilon}(x)=g_{0}\left(\frac{2(F_{\beta}(z_{x}-r\mathbf{1}_{2d})-\epsilon/2)}{\epsilon}\right),$

where $\beta=2\log(2d)/\epsilon$, $g_{0}(t):=30\mathds{1}{(0\leq t\leq
1)}\int_{t}^{1}s^{2}(1-s)^{2}ds+\mathds{1}{(t\leq 0)}$, $F_{\beta}$ is the
“softmax” function

$F_{\beta}(z):=\frac{1}{\beta}\log\Big{(}\sum_{m=1}^{2d}\exp\left(\beta
z_{m}\right)\Big{)}\quad\text{ for }z\in\mathbb{R}^{2d},$

$z_{x}=(x^{\top},-x^{\top})^{\top}$ and $\mathbf{1}_{2d}$ is the vector of
$1$’s of dimension $2d$.

To bound (B.13), we consider the case where $j\neq k$ and
$\sigma^{U}_{jk}\neq\sigma^{V}_{jk}$. Note that

$|\partial_{j}\partial_{k}\varphi(W(s))|\leq||g^{\prime\prime}||_{\infty}|\widetilde{\pi}_{j}(Z)\widetilde{\pi}_{k}(Z)|+\beta||g^{\prime}||_{\infty}|\widetilde{\pi}_{j}(Z)\widetilde{\pi}_{k}(Z)|,$
(B.14)

where $g(t):=g_{0}(\frac{2(t-\epsilon/2)}{\epsilon})$, $Z:=W(s)$ and

$\widetilde{\pi}_{j}(z):=\frac{e^{\beta z_{j}}-e^{-\beta
z_{j}}}{\sum_{m=1}^{d}e^{\beta z_{m}}+\sum_{m=1}^{d}e^{-\beta z_{m}}}.$

The above result follows from a direct calculation. Due to the boundedness of
$||g_{0}^{\prime}||_{\infty},||g_{0}^{\prime\prime}||_{\infty}$ and
$\beta={2\log(2d)}/{\epsilon}$, we obtain the following bound on (B.14),

$\displaystyle|\partial_{j}\partial_{k}\varphi(W(s))|$ $\displaystyle\leq$
$\displaystyle(||g^{\prime\prime}||_{\infty}+\beta||g^{\prime}||_{\infty})|\widetilde{\pi}_{j}(Z)\widetilde{\pi}_{k}(Z)|$
$\displaystyle\leq$
$\displaystyle\Big{(}\frac{4}{\epsilon^{2}}||g^{\prime\prime}_{0}||_{\infty}+\frac{2\beta}{\epsilon}||g_{0}^{\prime}||_{\infty}\Big{)}|\widetilde{\pi}_{j}(Z)\widetilde{\pi}_{k}(Z)|$
$\displaystyle\leq$
$\displaystyle\frac{C_{1}\log(2d)}{\epsilon^{2}}|\widetilde{\pi}_{j}(Z)\widetilde{\pi}_{k}(Z)|\leq\frac{C_{1}\log(2d)}{\epsilon^{2}}|{\pi}_{j}(Z){\pi}_{k}(Z)|,$

for some constant $C_{1}$, where
$\pi_{j}(z)={e^{\beta|z_{j}|}}/{\sum_{m=1}^{d}e^{\beta|z_{m}|}}$. Recalling
$Z=W(s)$, we have

$\displaystyle\int_{0}^{1}\mathbb{E}\left[{|\partial_{j}\partial_{k}\varphi(W(s))|\cdot\mathds{1}{(t-\epsilon\leq||W(s)||_{\infty}\leq
t+\epsilon)}}\right]ds$ (B.15) $\displaystyle\leq$
$\displaystyle\frac{C_{1}\log(2d)}{\epsilon^{2}}{\int_{0}^{1}{\mathbb{E}\left[{\pi_{j}(Z)\pi_{k}(Z)\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]}ds}$ $\displaystyle=$
$\displaystyle\frac{C_{1}\log(2d)}{\epsilon^{2}}\mathbb{P}(||V||_{\infty}>t)\int_{0}^{1}\underbrace{\frac{\mathbb{E}\left[{\pi_{j}(Z)\pi_{k}(Z)\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]}{\mathbb{P}(||V||_{\infty}>t)}}_{\rm{II}(s)}ds.$

Below we focus on bounding the term $\rm{II(s)}$ for any $s\in[0,1]$. First we
rewrite $\pi_{j}(Z)\pi_{k}(Z)$ and simply derive the following inequality,

$\displaystyle\pi_{j}(Z)\pi_{k}(Z)$ $\displaystyle=$
$\displaystyle\frac{e^{\beta|Z_{j}|}}{\sum_{m=1}^{d}e^{\beta|Z_{m}|}}\cdot\frac{e^{\beta|Z_{k}|}}{\sum_{m=1}^{d}e^{\beta|Z_{m}|}}$
(B.16) $\displaystyle=$
$\displaystyle\frac{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot
e^{-\beta(||Z||_{\infty}-|Z_{k}|)}}{(1+\sum_{|Z_{m}|\neq||Z||_{\infty}}e^{-\beta(||Z||_{\infty}-|Z_{m}|)})^{2}}$
$\displaystyle\leq$ $\displaystyle e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot
e^{-\beta(||Z||_{\infty}-|Z_{k}|)},$

where the second equality comes from dividing both the numerator and
denominator by $e^{2\beta||Z||_{\infty}}$ in the first line. Note that
$\mathbb{P}(|Z_{j}|=|Z_{k}|)=0$ since the random vector $Z$ follows a non-
degenerate $d$-dimensional multivariate Gaussian distribution. Hence we have

$1=\mathds{1}{(|Z_{j}|=||Z||_{\infty},|Z_{k}|<||Z||_{\infty})}+\mathds{1}{(|Z_{j}|<||Z||_{\infty})},\text{
almost surely}.$ (B.17)

Plugging the equality (B.17) into (B.16), we can further bound
$\pi_{j}(Z)\pi_{k}(Z)$ as

$\pi_{j}(Z)\pi_{k}(Z)\leq
e^{-\beta(||Z||_{\infty}-|Z_{k}|)}\cdot\mathds{1}{(|Z_{k}|<||Z||_{\infty})}+e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(|Z_{j}|<||Z||_{\infty})},\text{
almost surely}.$

Then we can bound $\mathrm{II}(s)$ by

$\displaystyle\mathrm{II}(s)$
$\displaystyle=\frac{\mathbb{E}\left[{\pi_{j}(Z)\pi_{k}(Z)\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]}{\mathbb{P}(||V||_{\infty}>t)}$
$\displaystyle\leq\frac{~{}\mathbb{E}[e^{-\beta(||Z||_{\infty}-|Z_{k}|)}\cdot\mathds{1}{(|Z_{k}|<||Z||_{\infty})}\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}]}{\mathbb{P}(||V||_{\infty}>t)}$ (B.18)
$\displaystyle\quad+\frac{~{}\mathbb{E}[e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(|Z_{j}|<||Z||_{\infty})}\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}]}{\mathbb{P}(||V||_{\infty}>t)}.$ (B.19)

We use the same strategy to bound (B.18) and (B.19). Below we give the
derivations for bounding (B.19) and note these also work for (B.18).

For any $j\neq k$ and $\sigma^{U}_{jk}\neq\sigma^{V}_{jk}$, Assumption B.3
says that there exists a subset $\mathcal{E}_{0}\subset[d]$ satisfying
$j\in\mathcal{E}_{0},|\mathcal{E}_{0}|=\mathfrak{p}+1$, and
$\sigma^{U}_{mm}=\sigma^{U}_{m^{\prime}m^{\prime}}$,
$\sigma^{U}_{mm^{\prime}}=\sigma^{V}_{mm^{\prime}}=0$ when
$m,m^{\prime}\in\mathcal{E}_{0},m\neq m^{\prime}$. This implies the following:
when $s=0$ or $1$ (i.e., $Z=U$ or $V$), we can find a
$\mathfrak{p}-$dimensional random vector $G$ such that $(Z_{j},G)$ are all
independent and $\operatorname{{\rm Var}}(G_{\ell})=\operatorname{{\rm
Var}}(Z_{j})=\sigma_{j}^{2}$ for $\ell\in[\mathfrak{p}]$. Note that $G$ is
constructed as $(Z_{m})_{m\in\mathcal{E}_{0},m\neq j}$ with $\mathcal{E}_{0}$
being the same for $Z=U$ and $V$. Therefore, for any
$s\in(0,1),Z=W(s)=\sqrt{s}U+\sqrt{1-s}V$, we can construct
$G=(Z_{m})_{m\in\mathcal{E}_{0},m\neq j}$ such that $(Z_{j},G)$ are all
independent and $\operatorname{{\rm Var}}(G_{\ell})=\operatorname{{\rm
Var}}(Z_{j})=\sigma_{j}^{2}$ for $\ell\in[\mathfrak{p}]$. Throughout the
following proof and the lemmas in Appendix B.3, we will use the notation $Z,G$
without making the dependence on $s$ explicitly. And we denote the indices of
the random variables in $G$ (among $Z$) by $\mathcal{E}_{G}$, i.e.,
$\mathcal{E}_{G}=\mathcal{E}_{0}\setminus\\{j\\}=\\{m\in[d]:Z_{m}=G_{\ell}\text{
for some }\ell\in[\mathfrak{p}]\\}$.

We will consider two separate cases based on whether
$||G||_{\infty}=||Z||_{\infty}$ holds. Formally, we write
$\mathds{1}{(|Z_{j}|<||Z||_{\infty})}\leq\mathds{1}{(E_{1})}+\mathds{1}{(E_{2})}$
with ${E_{1}}$ and ${E_{2}}$ defined as

$\displaystyle E_{1}$ $\displaystyle:=$
$\displaystyle\\{||Z||_{\infty}>||G||_{\infty},||Z||_{\infty}>|Z_{j}|\\},$
(B.20) $\displaystyle{E_{2}}$ $\displaystyle:=$
$\displaystyle\\{||G||_{\infty}=||Z||_{\infty}>|Z_{j}|\\}.$ (B.21)

Then the numerator of the fraction in (B.19) can be bounded by the summation
of the following two terms:

$\displaystyle\mathrm{II}_{1}$
$\displaystyle:=\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(E_{1})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right],$ (B.22) $\displaystyle\mathrm{II}_{2}$
$\displaystyle:=\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(E_{2})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right].$

Combining (B.19) with (B.22) and applying Lemmas B.5 and B.6, we have

$\mathrm{II}(s)\leq\frac{2(\mathrm{II}_{1}+\mathrm{II}_{2})}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}},\quad\forall s\in[0,1],$ (B.23)

for some constant $C^{\prime}$. By (B.12), (B.13), (B.15) and (B.23), we thus
obtain the following inequality

$\displaystyle\left|\mathbb{P}(||U||_{\infty}>t)-\mathbb{P}(||V||_{\infty}>t)\right|$
(B.24) $\displaystyle\leq$ $\displaystyle
A(t,\epsilon)\mathbb{P}(||V||_{\infty}>t)+\frac{C_{1}M\Delta_{0}\log(2d)}{2\epsilon^{2}}\mathbb{P}(||V||_{\infty}>t)\cdot\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}}$ $\displaystyle=$
$\displaystyle\mathbb{P}(||V||_{\infty}>t)\left(A(t,\epsilon)+B(\Delta_{0},\mathfrak{p})\right),$

where $A(t,\epsilon):=M_{1}\log
d(t+1)\epsilon\exp(M_{2}\log^{2}d(t+1)\epsilon)$,
$B(\Delta_{0},\mathfrak{p}):=C^{\prime\prime}{(\log
d/\mathfrak{p})\Delta_{0}}$ for some constants $M_{1},M_{2},C^{\prime\prime}$.
In the last line, we also subsitute $\beta=\frac{2\log(2d)}{\epsilon}$. By re-
arranging (B.24), we finally have

$\left|\frac{\mathbb{P}(||U||_{\infty}>t)}{\mathbb{P}(||V||_{\infty}>t)}-1\right|\leq
A(t,\epsilon)+B(\Delta_{0},\mathfrak{p}).$

Since $0\leq t\leq C_{0}\sqrt{\log d}$ and $\epsilon={c}/{\max\\{(\log
d)^{3/2},\mathfrak{p}\log d\\}}$ for some small enough constant $c>0$, we have
$A(t,\epsilon)=O(B(\Delta_{0},\mathfrak{p}))$. Then (B.11) can be established,
i.e.,

$\sup_{0\leq t\leq C_{0}\sqrt{\log
d}}\left|\frac{\mathbb{P}(||U||_{\infty}>t)}{\mathbb{P}(||V||_{\infty}>t)}-1\right|\leq
C^{\prime\prime\prime}B(\Delta_{0},\mathfrak{p})=O\left(\frac{\Delta_{0}\log
d}{\mathfrak{p}}\right).$

∎

Now we prove Theorem 3.2 using similar strategies as in Theorem B.4. Recall
that the connectivity assumption in Theorem 3.2 assumes that there exists a
disjoint $\mathfrak{p}$-partition of nodes
$\cup_{\ell=1}^{\mathfrak{p}}\mathcal{C}_{\ell}=[d]$ such that
$\sigma^{U}_{jk}=\sigma^{V}_{jk}=0$ when $j\in\mathcal{C}_{\ell}$ and
$k\in\mathcal{C}_{\ell^{\prime}}$ for some $\ell\neq\ell^{\prime}$. Since this
connectivity assumption is stronger than that in Theorem B.4, we are able to
do slightly more careful analysis in Lemma B.5. As a result, the minimal
eigenvalue condition is no longer needed. Also note that Theorem 3.2 assumes
the unit variance condition and there exists some $\sigma_{0}<1$ such that
$|\sigma^{V}_{jk}|\leq\sigma_{0},|\sigma^{U}_{jk}|\leq\sigma_{0}$ for any
$j\neq k$. Both the variance condition and the covariance condition can be
relaxed. In the following proof, we establish the Cramér-type comparison bound
under a general variance condition. This general version is actually used in
the proof of Theorem 5.2. Specifically, the general variance condition says
that $a_{0}\leq\sigma^{U}_{jj}=\sigma^{V}_{jj}\leq a_{1},~{}\forall j\in[d]$.
After relaxing the unit variance assumption, some balanced variance assumption
on the above components $\mathcal{C}_{\ell}$ is required. It says that given
any $j\in\mathcal{C}_{\ell}$ with some $\ell$, there exists at least one
$m\in\mathcal{C}_{\ell^{\prime}}$ such that
$\sigma^{U}_{jj}=\sigma^{V}_{jj}=\sigma^{U}_{mm}=\sigma^{V}_{mm}$ for any
$\ell^{\prime}\neq\ell$. Remark this condition is mainly needed for Lemma
B.12. We will call all these assumptions about variances as general variance
condition. Denote
$\widetilde{\sigma}^{U}_{jk}={\sigma}^{U}_{jk}/\sqrt{{\sigma}^{U}_{jj}{\sigma}^{U}_{kk}}$.
Accordingly, the covariance condition on $\sigma_{jk}$ in Theorem 3.2 can also
be relaxed into the following: there exists some $\sigma_{0}<1$ such that
$|\widetilde{\sigma}^{V}_{jk}|=|{\sigma}^{V}_{jk}|/\sqrt{{\sigma}^{V}_{jj}{\sigma}^{V}_{kk}}\leq\sigma_{0}$
for any $j\neq k$ and $|\\{(j,k):j\neq
k,|\widetilde{\sigma}^{U}_{jk}|=|{\sigma}^{U}_{jk}|/\sqrt{\sigma^{U}_{jj}\sigma^{U}_{kk}}>\sigma_{0}\\}|\leq
b_{0}$ for some constant $b_{0}$. We will call this condition as general
covariance condition.

###### Proof of Theorem 3.2.

Following exactly the same derivations in Theorem B.4 (up to (B.22)), we
arrive at the following

$\mathrm{II}(s)\leq\frac{2(\mathrm{II}_{1}+\mathrm{II}_{2})}{\mathbb{P}(||V||_{\infty}>t)},$

where $\mathrm{II}(s),\mathrm{II}_{1},\mathrm{II}_{2}$ are defined in (B.15)
and (B.22), except that the random vector $G$ can be constructed to satisfy
more properties. Assuming the connectivity assumption of Theorem 3.2 and the
general variance condition, we construct $G$ by choosing one random variable
$Z_{m}$ from each component (except the one to which $Z_{j}$ belongs)
satisfying
$\mathrm{Var}\left({Z_{m}}\right)=\sigma^{U}_{mm}=\sigma^{V}_{mm}=\sigma^{U}_{jj}=\sigma^{V}_{jj}=\mathrm{Var}\left({Z_{j}}\right)$.
Such construction still satisfies the mentioned properties in Theorem B.4.
Specifically, $(G,Z_{j})$ consists of $(\mathfrak{p}+1)$ i.i.d. Gaussian
random variables. Moreover, for any $k\neq
j,k\notin\mathcal{E}_{G}=\\{m\in[d]:Z_{m}=G_{\ell}\text{ for some
}\ell\in[\mathfrak{p}]\\}$, there exists at most one
$m\in\\{j\\}\cup\mathcal{E}_{G}$, such that $Z_{k}$ and $Z_{m}$ belong to the
same component. Based on this property, we prove Lemma B.12 and Lemma B.13,
which do not require minimal eigenvalue conditions compared with Lemma B.5 and
Lemma B.7. We still apply Lemma B.13 to bound the term $\mathrm{II}_{2}$.
Regarding the term $\mathrm{II}_{1}$, we control it by using Lemma B.6.
Therefore, we obtain the following

$\mathrm{II}(s)\leq\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}}\left(1+\frac{b_{0}}{\sqrt{1-(s+(1-s)\sigma_{0})^{2}}}\right).$
(B.25)

Note a simple calculus result:

$\int_{0}^{1}\frac{b_{0}}{\sqrt{1-(s+(1-s)\sigma_{0})^{2}}}\leq\frac{0.5\pi
b_{0}}{1-\sigma_{0}}<C^{\prime\prime}$

for some constant $C^{\prime\prime}$ when $\sigma_{0}<1$. Combining the above
bound with (B.25), (B.12), (B.13), (B.15) and (B.23), we establish the bound
(3.2) thus prove Theorem 3.2. ∎

###  B.3 Ancillary lemmas for Theorem B.4

Throughout the lemmas in this section, we will use $Z$ and $G$ without making
the dependence on $s$ explicitly, as mentioned in the proof of Theorem B.4.

######  Lemma B.5.

Suppose $\lambda_{\min}(\bm{\Sigma}^{U})\geq
1/b_{0}>0,\lambda_{\min}(\bm{\Sigma}^{V})\geq 1/b_{0}>0$ for some constant
$b_{0}>0$. For the term
$\mathrm{II}_{1}=\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(E_{1})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]$ with ${E_{1}}$ defined in (B.20) and
$\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log d\\}}$ for some small
enough constant $c>0$, whenever $t$ satisfies $0\leq t\leq C_{0}\sqrt{\log d}$
for some constant $C_{0}>0$, we have

$\displaystyle\frac{\mathrm{II}_{1}}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}}.$ (B.26)

###### Proof of Lemma B.5.

We will bound $\mathrm{II}_{1}$ by the law of total expectation. Specifically,
we first calculate the conditional expectation given $(G,Z_{j})$ then take
expectation with respect to $(G,Z_{j})$. Denoting the conditional density
function of $||Z||_{\infty}\mid Z_{j}=z_{j},G=g$ by $f_{g,z_{j}}(u)$, we write
out the integral form of $\mathrm{II}_{1}$ as

$\displaystyle\mathrm{II}_{1}=~{}$
$\displaystyle\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(||Z||_{\infty}>||G||_{\infty},||Z||_{\infty}>Z_{j})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]$ $\displaystyle=~{}$
$\displaystyle\mathbb{E}\left[{e^{\beta|Z_{j}|}\cdot\mathds{1}{(||G||_{\infty}\leq
t+\epsilon,|Z_{j}|\leq
t+\epsilon)}\left(\int_{t-\epsilon}^{t+\epsilon}f_{G,Z_{j}}(u)e^{-\beta
u}\mathds{1}{(u>||G||_{\infty},u>|Z_{j}|)}du\right)}\right]$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{E}\left[{e^{\beta|Z_{j}|}\cdot\mathds{1}{(||G||_{\infty}\leq
t+\epsilon,|Z_{j}|\leq
t+\epsilon)}\left(\int_{t-\epsilon}^{t+\epsilon}C\sqrt{\log d}\cdot e^{-\beta
u}\mathds{1}{(u>|Z_{j}|)}du\right)}\right]$ $\displaystyle\leq~{}$
$\displaystyle C\sqrt{\log d}~{}\mathbb{P}(||G||_{\infty}\leq
t+\epsilon)\mathbb{E}\left[{\int_{|z_{j}|\leq
t+\epsilon}\phi\left(\frac{z_{j}}{\sigma_{j}}\right)e^{\beta|z_{j}|}\left(\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\mathds{1}{(u>|z_{j}|)}du\right)dz_{j}}\right]$ $\displaystyle\leq~{}$
$\displaystyle C\sqrt{\log d}~{}\mathbb{P}(||G||_{\infty}\leq
t+\epsilon)\underbrace{\int_{|z_{j}|\leq
t+\epsilon}\phi\left(\frac{z_{j}}{\sigma_{j}}\right)e^{\beta|z_{j}|}\left(\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\mathds{1}{(u>|z_{j}|)}du\right)dz_{j}}_{\mathrm{III}},$ (B.27)

where the first inequality holds since
$\mathds{1}{(u>||G||_{\infty},|Z_{j}|)}\leq\mathds{1}{(u>|Z_{j}|)}$ and the
conditional density function $f_{g,z_{j}}(u)$ is bounded by $C\sqrt{\log d}$
when $||g||_{\infty},|z_{j}|<u\leq t+\epsilon$ and $0\leq t\leq
C_{0}\sqrt{\log d}$, as a result of Lemma B.7. Recall that $\phi(\cdot)$
denotes the standard Gaussian PDF. We use the fact that
$Z_{j}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}G$, $Z_{j}\sim\mathcal{N}(0,\sigma_{j}^{2})$
and write out the integral form of the expectation with respect to $Z_{j}$,
thus the second inequality follows. Then the integral $\mathrm{III}$ can be
further rewritten as

$\displaystyle\mathrm{III}$ $\displaystyle=$ $\displaystyle
2\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\left(\int_{0}^{u}\phi\left(\frac{x}{\sigma_{j}}\right)e^{\beta
x}dx\right)du$ (B.28) $\displaystyle=$ $\displaystyle
2\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\left(e^{\frac{\beta^{2}\sigma_{j}^{2}}{2}}\int_{0}^{u}\phi\left(\frac{x}{\sigma_{j}}-\beta\sigma_{j}\right)dx\right)du$
$\displaystyle=$ $\displaystyle 2\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\left(e^{\frac{\beta^{2}\sigma_{j}^{2}}{2}}\int_{-\beta\sigma_{j}}^{u/\sigma_{j}-\beta\sigma_{j}}\phi\left(x\right)dx\right)du$
$\displaystyle\leq$ $\displaystyle 2\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\left(e^{\frac{\beta^{2}\sigma_{j}^{2}}{2}}\bar{\Phi}\big{(}\beta\sigma_{j}-{u}/{\sigma_{j}}\big{)}\right)du$
$\displaystyle\leq$ $\displaystyle 2\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\left(e^{\frac{\beta^{2}\sigma_{j}^{2}}{2}}\frac{e^{-\frac{(\beta\sigma_{j}-{u}/{\sigma_{j}})^{2}}{2}}}{\beta\sigma_{j}-{u}/{\sigma_{j}}}\right)du$
$\displaystyle\leq$
$\displaystyle\frac{4}{\beta\sigma_{j}}\int_{t-\epsilon}^{t+\epsilon}e^{-\beta
u}\left(e^{\beta
u}{e^{-\frac{u}{2\sigma_{j}}}}\right)du\leq\frac{8\epsilon}{\beta\sigma_{j}}\exp\left(-\frac{(t-\epsilon)^{2}}{2\sigma^{2}_{j}}\right),$

where the first equality holds by Fubini’s theorem, and the second equality
holds by the definition of $\phi(\cdot)$. Regarding the first inequality, we
use the fact that
$u/\sigma_{j}-\beta\sigma_{j}<2u/\sigma_{j}-\beta\sigma_{j}<0$ for $u\leq
t+\epsilon$ and $t\leq C_{0}\sqrt{\log d}$. This is because
$\beta=\frac{2\log(2d)}{\epsilon}$ and $\epsilon={c}/{\max\\{(\log
d)^{3/2},\mathfrak{p}\log d\\}}$ for some small enough constant $c>0$. Then
$\int_{-\beta\sigma_{j}}^{u/\sigma_{j}-\beta\sigma_{j}}\phi\left(x\right)dx\leq\bar{\Phi}(\beta\sigma_{j}-{u}/{\sigma_{j}})$,
recalling $\bar{\Phi}=1-{\Phi}$, where ${\Phi}$ is the standard Gaussian CDF.
The second inequality holds as a result of Lemma B.8. The third inequality
holds due to $\beta\sigma_{j}>2u/\sigma_{j}$ for $u\leq t+\epsilon$.

By (B.27) and (B.28), we arrive at the following bound

$\displaystyle\frac{\mathrm{II}_{1}}{\mathbb{P}(||V||_{\infty}>t)}$
$\displaystyle\leq$ $\displaystyle C\sqrt{\log
d}\cdot\frac{\mathbb{P}(||G||_{\infty}\leq
t+\epsilon)}{\mathbb{P}(||V||_{\infty}>t)}\cdot\frac{8\epsilon}{\beta\sigma_{j}}\exp\left(-\frac{(t-\epsilon)^{2}}{2\sigma^{2}_{j}}\right)$
$\displaystyle\leq$ $\displaystyle C\sqrt{\log
d}\cdot\frac{C_{1}\epsilon}{\beta}\cdot\frac{\mathbb{P}(||G||_{\infty}\leq
t+\epsilon)}{\mathbb{P}(||G||_{\infty}>t)}\cdot\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}/\sigma_{j}$
$\displaystyle=$ $\displaystyle C\sqrt{\log
d}\cdot\frac{C_{1}\epsilon}{\beta}\cdot\underbrace{\frac{(1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}}}{1-(1-2\bar{\Phi}\big{(}\frac{t}{\sigma_{j}})\big{)}^{\mathfrak{p}}}\cdot\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}/\sigma_{j}}_{\Lambda(t,\epsilon,\mathfrak{p})},$

for some constants $C,C_{1}$, where the second inequality holds due to the
definition of $\phi(z)$ and
$\mathbb{P}(||V||_{\infty}>t)\geq\mathbb{P}(||G||_{\infty}>t)$. This is
because

$\mathbb{P}(||V||_{\infty}>t)\geq\mathbb{P}(\max_{k\in\mathcal{E}_{G}}|V_{k}|>t)=\mathbb{P}(||G_{V}||_{\infty}>t)=\mathbb{P}(||G||_{\infty}>t),$
(B.29)

where $G_{V}=(Z_{m})_{m\in\mathcal{E}_{0},m\neq j}$ with $Z=V$ has the same
distribution as $G$. Regarding the last line, by the construction of
$G=(G_{\ell})_{\ell\in[\mathfrak{p}]}=(Z_{m})_{m\in\mathcal{E}_{0},m\neq j}$
in the proof of Theorem B.4, we have $\\{G_{\ell}\\}_{\ell\in[\mathfrak{p}]}$
are $\mathfrak{p}$ i.i.d. Gaussian random variables with
$\mathrm{Var}\left({G_{\ell}}\right)=\mathrm{Var}\left({Z_{j}}\right)=\sigma_{j}^{2}$.
By applying Lemma B.9 to the term ${\Lambda(t,\epsilon,\mathfrak{p})}$ in the
last line, we further obtain,

$\displaystyle\frac{\mathrm{II}_{1}}{\mathbb{P}(||V||_{\infty}>t)}$
$\displaystyle\leq$ $\displaystyle C^{\prime}\sqrt{\log
d}\cdot\frac{\epsilon}{\beta}\frac{\sqrt{\log
d}}{\mathfrak{p}}=\frac{C^{\prime}\epsilon\log d}{\beta\mathfrak{p}},$

for some constant $C^{\prime}$, therefore (B.26) is established. ∎

######  Lemma B.6.

For the term
$\mathrm{II}_{2}=\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(E_{2})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]$ with ${E_{2}}$ defined in (B.21) and
$\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log d\\}}$ for some small
enough constant $c>0$, whenever $t$ satisfies $0\leq t\leq C_{0}\sqrt{\log d}$
for some constant $C_{0}>0$, we have

$\displaystyle\frac{\mathrm{II}_{2}}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{C^{\prime\prime}\epsilon\sqrt{\log
d}}{\beta\mathfrak{p}}.$ (B.30)

###### Proof of Lemma B.6.

By the definition of $E_{2}$ in (B.21) and the tower property, we have

$\displaystyle\mathrm{II}_{2}$
$\displaystyle~{}=\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(||G||_{\infty}=||Z||_{\infty}>|Z_{j}|)}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]$
$\displaystyle~{}=\mathbb{E}\left[{e^{-\beta(||G||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(||G||_{\infty}=||Z||_{\infty},||G||_{\infty}>|Z_{j}|)}\cdot\mathds{1}{(t-\epsilon\leq||G||_{\infty}\leq
t+\epsilon)}}\right]$
$\displaystyle~{}\leq\mathbb{E}\left[{e^{-\beta(||G||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(||G||_{\infty}>|Z_{j}|)}\cdot\mathds{1}{(t-\epsilon\leq||G||_{\infty}\leq
t+\epsilon)}}\right]$
$\displaystyle~{}=\mathbb{E}\left[{\mathbb{E}\left[{e^{\beta|Z_{j}|}\mathds{1}{(|Z_{j}|<||G||_{\infty})}}\,|\,{G}\right]e^{-\beta||G||_{\infty}}\cdot\mathds{1}{(t-\epsilon\leq||G||_{\infty}\leq
t+\epsilon)}}\right].$ (B.31)

First we bound
$\mathrm{III}(g):=\mathbb{E}\left[{e^{\beta|Z_{j}|}\mathds{1}{(|Z_{j}|<||G||_{\infty})}}\,|\,{G=g}\right]$
when $||g||_{\infty}\in[t-\epsilon,t+\epsilon]$. Specifically,

$\displaystyle\mathrm{III}(g)=\frac{2}{\sigma_{j}}\int_{0}^{||g||_{\infty}}e^{\beta
x}\phi\Big{(}\frac{x}{\sigma_{j}}\Big{)}dx$ $\displaystyle=$
$\displaystyle\frac{2e^{{\beta^{2}\sigma_{j}^{2}}/{2}}}{\sigma_{j}}\int_{0}^{||g||_{\infty}}\phi\Big{(}\frac{x-\beta\sigma_{j}^{2}}{\sigma_{j}}\Big{)}dx$
(B.32) $\displaystyle\leq$
$\displaystyle{2e^{\beta^{2}\sigma_{j}^{2}/2}}\int_{-\infty}^{||g||_{\infty}/\sigma_{j}-\beta\sigma_{j}}\phi(y)dy$
$\displaystyle=$
$\displaystyle{2e^{\beta^{2}\sigma_{j}^{2}/2}}~{}\bar{\Phi}(\beta\sigma_{j}-{||g||_{\infty}}/{\sigma_{j}})$
$\displaystyle\leq$
$\displaystyle{2e^{\beta^{2}\sigma_{j}^{2}/2}}\frac{\phi\left(\beta\sigma_{j}-{||g||_{\infty}}/{\sigma_{j}}\right)}{\beta\sigma_{j}-{||g||_{\infty}}/{\sigma_{j}}}$
$\displaystyle\leq$
$\displaystyle\frac{4}{\beta\sigma_{j}}\phi\left(\frac{||g||_{\infty}}{\sigma_{j}}\right)e^{\beta||g||_{\infty}},$

where the first equality holds due to $Z_{j}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}G$, and the second equality comes from
rearranging. The first inequality holds by the change of variable
$y=(x-\beta\sigma_{j}^{2})/\sigma_{j}$ and setting the lower limit of the
integral as $-\infty$. Because $\beta=\frac{2\log(2d)}{\epsilon}$ and
$\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log d\\}}$ for some small
enough constant $c>0$, we have $||g||_{\infty}/\sigma_{j}<\beta\sigma_{j}$ for
$||g||_{\infty}\leq t+\epsilon$ and $t\leq C_{0}\sqrt{\log d}$. Then the
second inequality holds as a result of Lemma B.8 and the fact that
$\beta\sigma_{j}-||g||_{\infty}/\sigma_{j}>0$. The last inequality comes from
rearranging and the fact that $\beta\sigma_{j}>2||g||_{\infty}/\sigma_{j}$ for
$||g||_{\infty}\leq t+\epsilon$ and $t\leq C_{0}\sqrt{\log d}$. Combining
(B.32) with (B.31), we have

$\displaystyle\mathrm{II}_{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[{\mathrm{III}(G)\cdot
e^{-\beta||G||_{\infty}}\cdot\mathds{1}{(t-\epsilon\leq||G||_{\infty}\leq
t+\epsilon)}}\right]$ (B.33) $\displaystyle\leq$
$\displaystyle\frac{4}{\beta\sigma_{j}}\mathbb{E}\left[{\phi\Big{(}\frac{||G||_{\infty}}{\sigma_{j}}\Big{)}e^{\beta(||G||_{\infty})}\cdot
e^{-\beta||G||_{\infty}}\cdot\mathds{1}{(t-\epsilon\leq||G||_{\infty}\leq
t+\epsilon)}}\right]$ $\displaystyle\leq$
$\displaystyle\frac{4}{\beta\sigma_{j}}\int_{t-\epsilon}^{t+\epsilon}\phi\big{(}\frac{y}{\sigma_{j}}\big{)}f(y)dy,$

where $f(y)$ denotes the PDF of $||G||_{\infty}$. As
$\\{G_{\ell}\\}_{\ell\in[\mathfrak{p}]}$ are i.i.d. Gaussian random variables
satisfying $\forall~{}\ell\in[\mathfrak{p}]$,
$\mathbb{E}\left[{G_{\ell}}\right]=0$ and
$\mathrm{Var}\left({G_{\ell}}\right)=\sigma_{j}^{2}$, we have for $y>0$,

$\mathbb{P}(||G||_{\infty}\leq
y)=\mathbb{P}(\bigcup_{\ell\in[\mathfrak{p}]}|G_{\ell}|\leq
y)=(1-2\mathbb{P}(G_{\ell}/\sigma_{j}>y/\sigma_{j}))^{\mathfrak{p}}=(1-2\bar{\Phi}({y}/{\sigma_{j}}))^{\mathfrak{p}}.$
(B.34)

Thus we have the PDF of $||G||_{\infty}$ equals
$f(y)=\frac{2\mathfrak{p}}{\sigma_{j}}\left(1-2\bar{\Phi}(\frac{y}{\sigma_{j}}))^{\mathfrak{p}}\right)^{\frac{\mathfrak{p}-1}{\mathfrak{p}}}\phi(\frac{y}{\sigma_{j}})$.
Plugging the expression of $f(y)$ into (B.33), we further derive the following
bound

$\displaystyle\frac{\mathrm{II}_{2}}{\mathbb{P}(||V||_{\infty}>t)}$
$\displaystyle\leq$
$\displaystyle\frac{8\mathfrak{p}}{\beta\sigma_{j}^{2}}\int_{t-\epsilon}^{t+\epsilon}\frac{\left(1-2\bar{\Phi}(\frac{y}{\sigma_{j}}))^{\mathfrak{p}}\right)^{\frac{\mathfrak{p}-1}{\mathfrak{p}}}\phi^{2}(\frac{y}{\sigma_{j}})}{\mathbb{P}(||V||_{\infty}>t)}dy$
$\displaystyle\leq$
$\displaystyle\frac{8\mathfrak{p}}{\beta\sigma_{j}^{2}}\int_{t-\epsilon}^{t+\epsilon}\frac{\left(1-2\bar{\Phi}(\frac{y}{\sigma_{j}}))^{\mathfrak{p}}\right)^{\frac{\mathfrak{p}-1}{\mathfrak{p}}}\phi^{2}(\frac{y}{\sigma_{j}})}{1-\mathbb{P}(||G||_{\infty}\leq
t)}dy$ $\displaystyle=$
$\displaystyle\frac{8\mathfrak{p}}{\beta\sigma_{j}^{2}}\int_{t-\epsilon}^{t+\epsilon}\frac{\left((1-2\bar{\Phi}(\frac{y}{\sigma_{j}}))^{\mathfrak{p}}\right)^{\frac{\mathfrak{p}-1}{\mathfrak{p}}}\phi^{2}(\frac{y}{\sigma_{j}})}{1-(1-2\bar{\Phi}(\frac{t}{\sigma_{j}}))^{\mathfrak{p}}}dy$
$\displaystyle\leq$
$\displaystyle\frac{16\epsilon}{\beta\sigma_{j}^{2}\mathfrak{p}}\frac{\left((1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}}\right)^{\frac{\mathfrak{p}-1}{\mathfrak{p}}}(\mathfrak{p}\phi(\frac{t-\epsilon}{\sigma_{j}}))^{2}}{1-(1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}}}\leq\frac{C^{\prime\prime}\epsilon\sqrt{\log
d}}{\beta\mathfrak{p}},$

for some constant $C^{\prime}$, where the second inequality holds due to
(B.29), as mentioned in the proof of Lemma B.5. The equality holds as a result
of substituting the expression of $\mathbb{P}(||G||_{\infty}\leq t)$ by
(B.34). The third inequality holds since $1-2\bar{\Phi}(z)$ is monotonically
increasing and ${\phi}(z)$ is monotonically decreasing when $z\geq 0$. As for
the last line, we apply Lemma B.10. Finally, (B.30) is established. ∎

######  Lemma B.7.

Suppose $\lambda_{\min}(\bm{\Sigma}^{U})\geq
1/b_{0}>0,\lambda_{\min}(\bm{\Sigma}^{V})\geq 1/b_{0}>0$ for some constant
$b_{0}>0$. Recall that the density function of the conditional distribution of
$||Z||_{\infty}\mid\\{Z_{j}=z_{j},G=g\\}$ is denoted by $f_{g,z_{j}}(z)$.
Suppose $\epsilon>0$, when $0\leq t\leq C_{0}\sqrt{\log d}$ for some constant
$C_{0}>0$ and $|z_{j}|,||g||_{\infty}\leq t+\epsilon$, we have

$f_{g,z_{j}}(z)\leq C\sqrt{\log
d},\quad\forall~{}z\in(\max\\{|z_{j}|,||g||_{\infty}\\},t+\epsilon].$

###### Proof of Lemma B.7.

First we introduce some new notations. Let $(\sigma_{jk})_{1\leq j,k\leq
d}\in\mathbb{R}^{d\times d}$ be the covariance matrix of $Z$. For given $j$,
we denote

$\sigma_{kk\cdot
j}:=\sigma_{kk}-\sigma_{kj}^{2}\sigma_{jj}^{-1}-\sum_{m\in\mathcal{E}_{G}}\sigma_{km}^{2}\sigma_{mm}^{-1}.$
(B.35)

As $z\in(\max\\{|z_{j}|,||g||_{\infty}\\},t+\epsilon]$, we can choose $\delta$
such that $0<\delta<z-\max\\{|z_{j}|,||g||_{\infty}\\}$. Throughout the
following proof, we will work with such $\delta$. Since
$\max\\{|z_{j}|,||g||_{\infty}\\}-z<-\delta$, we have

$\mathbb{P}\left({\big{|}||Z||_{\infty}-z\big{|}\leq\delta}\,|\,{Z_{j}=z_{j},G=g}\right)=\mathbb{P}\left({\big{|}||X||_{\infty}-z\big{|}\leq\delta}\,|\,{Z_{j}=z_{j},G=g}\right),$
(B.36)

where $X$ denotes the $(d-\mathfrak{p}-1)$-dimensional random vector by
excluding $Z_{j},G$ from $Z$ and therefore
$||Z||_{\infty}=\max\\{||X||_{\infty},|Z_{j}|,||G||_{\infty}\\}$.

Recalling
$G=(G_{\ell})_{\ell\in[\mathfrak{p}]}=(Z_{m})_{m\in\mathcal{E}_{G}}$, where
$\mathcal{E}_{G}$ denotes the indices of the random variables in $G$ (among
$Z$), i.e., $\mathcal{E}_{G}=\\{m\in[d]:Z_{m}=G_{\ell}\text{ for some
}\ell\in[\mathfrak{p}]\\}$, we have

$||X||_{\infty}=\max_{k\in[d],~{}k\notin\\{j,\mathcal{E}_{G}\\}}\\{\max\\{Z_{k},-Z_{k}\\}\\}.$

Given $j$ and the choice of $G$, we also denote

$\quad\underline{\sigma_{\cdot
j}}:=\min_{k\in[d],k\notin\\{j,\mathcal{E}_{G}\\}}\sqrt{\sigma_{kk\cdot
j}},\quad\bar{\rho}_{j}:=\max_{k\in[d],k\notin\\{j,\mathcal{E}_{G}\\}}\frac{|\sigma_{jk}|}{\sigma_{jj}}.$
(B.37)

For each $k\in[d],k\notin\\{j,\mathcal{E}_{G}\\}$, the conditional expectation
$\mathbb{E}\left[{Z_{k}}\,|\,{Z_{j},G}\right]$ has the following expression,

$\displaystyle\mathbb{E}\left[{Z_{k}}\,|\,{Z_{j},G}\right]=\sigma_{kj}\sigma_{jj}^{-1}Z_{j}+\sum_{m\in\mathcal{E}_{G}}(\sigma_{km}\sigma_{mm}^{-1}Z_{m}),$
(B.38)

since $(Z_{j},G)$ are all independent. Note that the requirement $(c)$ in
Assumption B.3 says $\forall~{}k\in[d]$,
$|\\{m\in\mathcal{E}_{0}:|\sigma^{U}_{km}|+|\sigma^{V}_{km}|\neq 0\\}|\leq
c_{0}$, we thus have

$\displaystyle\sum_{m\in\mathcal{E}_{G}}\mathds{1}{(\sigma_{km}\neq 0)}$
$\displaystyle=$
$\displaystyle\sum_{m\in\mathcal{E}_{G}}\mathds{1}{((s\sigma^{U}_{km}+{(1-s)}\sigma^{V}_{km})\neq
0)}$ (B.39) $\displaystyle\leq$
$\displaystyle\sum_{m\in\mathcal{E}_{G}}\mathds{1}{(\sigma^{U}_{km}\neq
0\text{ or }\sigma^{V}_{km}\neq 0)}\leq c_{0},$

where the first equality holds by the definition of $\sigma_{km}$ and
$Z=W(s)=\sqrt{s}U+\sqrt{1-s}V$. Combining (B.39) with (B.38), it yields the
following bound on $|\mathbb{E}\left[{Z_{k}}\,|\,{Z_{j}=z_{j},G=g}\right]|$,

$\displaystyle|\mathbb{E}\left[{Z_{k}}\,|\,{Z_{j}=z_{j},G=g}\right]|$
$\displaystyle=$
$\displaystyle\big{|}\sigma_{kj}\sigma_{jj}^{-1}z_{j}+\sum_{m\in\mathcal{E}_{G}}(\sigma_{km}\sigma_{mm}^{-1}z_{m})\big{|}$
(B.40) $\displaystyle\leq$
$\displaystyle\bar{\rho}_{j}(|z_{j}|+c_{0}||g||_{\infty}),$

where
$\bar{\rho}_{j}=\max_{k\in\mathcal{E}_{X}}\frac{|\sigma_{jk}|}{\sigma_{jj}}$
as defined. Denoting
$\mathcal{E}_{X}:=\\{k:k\in[d],~{}k\notin\\{j,\mathcal{E}_{G}\\}\\}$, we
define the following random variables,

$\widetilde{W}_{2k-1}=\frac{{Z_{k}}-{z}}{\sqrt{\sigma_{kk\cdot
j}}}+\frac{\widetilde{z}}{\underline{\sigma_{\cdot
j}}},\quad\widetilde{W}_{2k}=\frac{-{Z_{k}}-{z}}{\sqrt{\sigma_{kk\cdot
j}}}+\frac{\widetilde{z}}{\underline{\sigma_{\cdot j}}},\quad
k\in\mathcal{E}_{X},$ (B.41)

where $\widetilde{z}=z+\bar{\rho}_{j}(|z_{j}|+c_{0}||g||_{\infty})$. Then by
the definitions of $\sigma_{kk\cdot j},\underline{\sigma_{\cdot j}}$ and
$\bar{\rho}_{j}$ in (B.35) and (B.37), we have the above random variables
satisfy the following properties,

$\mathbb{E}\left[{\widetilde{W}_{m}}\,|\,{Z_{j}=z_{j},G=g}\right]\geq
0,\quad\mathrm{Var}\left({\widetilde{W}_{m}}\,|\,{Z_{j}=z_{j},G=g}\right)=1,$

where $m=2k-1$ or $2k$ and $k\in\mathcal{E}_{X}$. Denote those random
variables defined in (B.41) by $\\{\widetilde{W}_{m}\\}$ for notation
simplicity. We let $q_{z_{j},g}(w)$ be the PDF of the conditional distribution
of $\max_{m}\\{\widetilde{W}_{m}\\}\mid Z_{j}=z_{j},G=g$. Then we will apply
the derivation of Step $2$ in Theorem $3$ of Chernozhukov et al. (2015) to
bound $q_{z_{j},g}(w)$. Note that for the following derivations, we always
conditional on the event $Z_{j}=z_{j},G=g$. First, we verify the condition on
$\\{\widetilde{W}_{m}\\}$. Since $|\mathrm{Corr}{(U_{j},U_{k})}|\neq 1$,
$|\mathrm{Corr}{(V_{j},V_{k})}|\neq 1$ for distinct $j,k\in[d]$, we then have
the correlation between $\widetilde{W}_{m_{1}}$ and $\widetilde{W}_{m_{2}}$
for $m_{1}\neq m_{2}$ is less than $1$. Therefore, by applying the derivation
of Step $2$ in Theorem $3$ of Chernozhukov et al. (2015) to
$\\{\widetilde{W}_{m}\\}$, we have

$q_{z_{j},g}(w)\leq h(w):=2(w\vee
1)\exp\left\\{-\frac{(w-\bar{w}-a_{d})^{2}_{+}}{2}\right\\},$

where
$\bar{w}=\max_{m}\mathbb{E}\left[{\widetilde{W}_{m}}\,|\,{Z_{j}=z_{j},G=g}\right]$
and

$a_{d}=\max_{m}\mathbb{E}\left[{\Big{(}\widetilde{W}_{m}-\mathbb{E}\left[{\widetilde{W}_{m}}\,|\,{Z_{j}=z_{j},G=g}\right]\Big{)}}\,|\,{Z_{j}=z_{j},G=g}\right].$

When $w\leq\bar{w}+a_{d}$, we have $h(w)\leq 2(\bar{w}+a_{d})$. To deal with
the case where $w>\bar{w}+a_{d}$, we consider

$\displaystyle\log(h(w))$ $\displaystyle=$
$\displaystyle\log(2w)-\frac{(w-\bar{w}-a_{d})^{2}}{2},$
$\displaystyle\frac{d\log(h(w))}{dw}$ $\displaystyle=$
$\displaystyle\frac{1}{w}-(w-\bar{w}-a_{d}),$
$\displaystyle\frac{d^{2}\log(h(w))}{dw^{2}}$ $\displaystyle=$
$\displaystyle-\frac{1}{w^{2}}-1<0.$

Solving $\frac{d}{dw}\log(h(w))=0$ yields
$w^{\star}=\frac{\bar{w}+a_{d}+\sqrt{(\bar{w}+a_{d})^{2}+4}}{2}$. Therefore,
the PDF of the conditional distribution of
$\max_{m}\\{\widetilde{W}_{m}\\}\mid Z_{j}=z_{j},G=g$ can be bounded by

$h(w)\leq h(w^{\star})\leq 3(\bar{w}+a_{d}).$ (B.42)

Now we have

$\displaystyle\mathbb{P}\left({\big{|}||Z||_{\infty}-z\big{|}\leq\delta}\,|\,{Z_{j}=z_{j},G=g}\right)$
(B.43) $\displaystyle=$
$\displaystyle\mathbb{P}\left({\left|||{X}||_{\infty}-{z}\right|\leq\delta}\,|\,{Z_{j}=z_{j},G=g}\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}\left({\left|\max_{k\in\mathcal{E}_{X}}\left\\{{Z}_{k},-{Z}_{k}\right\\}-{z}\right|\leq\delta}\,|\,{Z_{j}=z_{j},G=g}\right)$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left({\left|\max_{k\in\mathcal{E}_{X}}\left\\{\frac{{Z}_{k}-{z}}{\sqrt{\sigma_{kk\cdot
j}}},\frac{-{Z}_{k}-{z}}{\sqrt{\sigma_{kk\cdot
j}}}\right\\}\right|\leq\frac{\delta}{\underline{\sigma_{\cdot
j}}}}\,|\,{Z_{j}=z_{j},G=g}\right)$ $\displaystyle\leq$
$\displaystyle\sup_{y\in\mathbb{R}}\mathbb{P}\left({\left|\max_{k\in\mathcal{E}_{X}}\left\\{\frac{{Z}_{k}-{z}}{\sqrt{\sigma_{kk\cdot
j}}}+\frac{\widetilde{z}}{\underline{\sigma_{\cdot
j}}},\frac{-{Z}_{k}-{z}}{\sqrt{\sigma_{kk\cdot
j}}}+\frac{\widetilde{z}}{\underline{\sigma_{\cdot
j}}}\right\\}-y\right|\leq\frac{\delta}{\underline{\sigma_{\cdot
j}}}}\,|\,{Z_{j}=z_{j},G=g}\right)$ $\displaystyle=$
$\displaystyle\sup_{y\in\mathbb{R}}\mathbb{P}\left({\left|\max_{m}\\{\widetilde{W}_{m}\\}-y\right|\leq\frac{\delta}{\underline{\sigma_{\cdot
j}}}}\,|\,{Z_{j}=z_{j},G=g}\right)\leq\frac{6\delta}{\underline{\sigma_{\cdot
j}}}(\bar{w}+a_{d}),$

where the first equality holds by (B.36), the second equality holds by the
definition of $X$ and $\mathcal{E}_{X}$, the first inequality holds since
$\underline{\sigma_{\cdot j}}=\min_{k\neq j}\sqrt{\sigma_{kk\cdot j}}$, the
third equality holds by the definition of $\\{\widetilde{W}_{m}\\}$ in (B.41),
and the last inequality holds by the bound on $h(w)$ in (B.42). Regarding the
quantity
$\bar{w}=\max_{m}\mathbb{E}\left[{\widetilde{W}_{m}}\,|\,{Z_{j}=z_{j},G=g}\right]$,
we have

$\displaystyle\bar{w}$ $\displaystyle=$
$\displaystyle\max_{k\in\mathcal{E}_{X}}\left\\{\frac{\pm\mathbb{E}\left[{{Z_{k}}}\,|\,{Z_{j}=z_{j},G=g}\right]-{z}}{\sqrt{\sigma_{kk\cdot
j}}}+\frac{\widetilde{z}}{\underline{\sigma_{\cdot j}}}\right\\}$ (B.44)
$\displaystyle\leq$
$\displaystyle\max_{k\in\mathcal{E}_{X}}\left\\{\frac{\pm\mathbb{E}\left[{{Z_{k}}}\,|\,{Z_{j}=z_{j},G=g}\right]}{\sqrt{\sigma_{kk\cdot
j}}}\right\\}+\max_{k\in\mathcal{E}_{X}}\left\\{\frac{1}{\underline{\sigma_{\cdot
j}}}-\frac{1}{\sqrt{\sigma_{kk\cdot
j}}}\right\\}z+\frac{\bar{\rho}_{j}(|z_{j}|+c_{0}||g||_{\infty})}{\underline{\sigma_{\cdot
j}}}$ $\displaystyle\leq$
$\displaystyle\max_{k\in\mathcal{E}_{X}}\left\\{\frac{\pm\big{(}\sigma_{kj}\sigma_{jj}^{-1}z_{j}+\sum_{m\in\mathcal{E}_{G}}(\sigma_{km}\sigma_{mm}^{-1}z_{m})\big{)}}{\sqrt{\sigma_{kk\cdot
j}}}\right\\}+\frac{z}{\underline{\sigma_{\cdot
j}}}+\frac{\bar{\rho}_{j}(|z_{j}|+c_{0}||g||_{\infty})}{\underline{\sigma_{\cdot
j}}}$ $\displaystyle\leq$
$\displaystyle\frac{2\bar{\rho}_{j}(|z_{j}|+c_{0}||g||_{\infty})}{\underline{\sigma_{\cdot
j}}}+\frac{z}{\underline{\sigma_{\cdot
j}}}\leq\frac{2\bar{\rho}_{j}(1+c_{0})+1}{\underline{\sigma_{\cdot
j}}}(t+\epsilon),$

where $\max\\{\pm A\\}:=\max\\{A,-A\\}$, the first inequality holds by the
definition of $\widetilde{z}$, the second inequality holds by (B.38), and the
last inequality holds by the definitions of $\bar{\rho}_{j}$ and
$\underline{\sigma_{\cdot j}}$ and the fact
$\sum_{m\in\mathcal{E}_{G}}\mathds{1}{(\sigma_{km}\neq 0)}\leq c_{0}$.

Let $\delta$ in (B.43) go to $0$, we get the following bound on the density
function of the conditional distribution of
$||Z||_{\infty}\mid\\{Z_{j}=z_{j},G=g\\}$, i.e., when $0\leq t\leq
C_{0}\sqrt{\log d}$ and $|z_{j}|,||g||_{\infty}\leq t+\epsilon$,

$f_{g,z_{j}}(z)\leq\frac{6}{\underline{\sigma_{\cdot
j}}}(\bar{w}+a_{d})\leq\frac{6}{\underline{\sigma_{\cdot
j}}}\left(\frac{2\bar{\rho}_{j}(1+c_{0})+1}{\underline{\sigma_{\cdot
j}}}C_{1}\sqrt{\log d}+C_{2}\sqrt{\log d}\right),$ (B.45)

for any $z\in(\max\\{|z_{j}|,||g||_{\infty}\\},t+\epsilon]$. The first
inequality holds by (B.43). Regarding the second inequality, we apply the
result in $\eqref{eq:wbar_bound}$ and bound $(t+\epsilon)$ and $a_{d}$ by
$C_{1}\sqrt{\log d}$ for some constant $C_{1}$. Note $a_{d}\leq
C_{1}\sqrt{\log d}$ is because of the maximal inequalities for sub-Gaussian
random variables (Lemma 5.2 in van Handel (2014)). As for
$\bar{\rho}_{j}=\max_{k\in\mathcal{E}_{X}}\frac{|\sigma_{jk}|}{\sigma_{jj}}$,
we have

$\bar{\rho}_{j}^{2}\leq\max_{k\neq
j}{\frac{\sigma_{kk}}{\sigma_{jj}}}\leq\frac{\max_{j}\sigma_{jj}^{U}}{\min_{j}\sigma_{jj}^{U}}\leq\frac{\max_{j}\sigma_{jj}^{U}}{\lambda_{\min}(\bm{\Sigma}^{U})}=O(1),$

where the first inequality holds by the Cauchy-Schwarz inequality, the second
inequality holds by the definition of $Z$ and
$\sigma_{jj}^{U}=\sigma_{jj}^{V}$, the third inequality holds by the fact that
$\min_{j}\sigma_{jj}^{U}\geq\lambda_{\min}(\bm{\Sigma}^{U})$, and the last
step holds under the stated assumption of Theorem B.4. As for
$\underline{\sigma_{\cdot j}}=\min_{k\in\mathcal{E}_{X}}\sqrt{\sigma_{kk\cdot
j}}$ where $\sigma_{kk\cdot
j}=\sigma_{kk}-\sigma_{kj}^{2}\sigma_{jj}^{-1}-\sum_{m\in\mathcal{E}_{G}}\sigma_{km}^{2}\sigma_{mm}^{-1}=\mathrm{Var}\left({Z_{k}}\,|\,{Z_{j},G}\right)$,
we have

$\displaystyle\frac{1}{\underline{\sigma^{2}_{\cdot j}}}$ $\displaystyle=$
$\displaystyle\frac{1}{\min_{k\in\mathcal{E}_{X}}\mathrm{Var}\left({Z_{k}}\,|\,{Z_{j},G}\right)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\min_{k}\mathrm{Var}\left({Z_{k}}\,|\,{Z_{\text{-}k}}\right)}$
$\displaystyle=$ $\displaystyle\max_{k}((\bm{\Sigma}^{Z})^{-1})_{kk}$
$\displaystyle\leq$ $\displaystyle\lambda_{\max}((\bm{\Sigma}^{Z})^{-1})$
$\displaystyle=$ $\displaystyle 1/\lambda_{\min}(\bm{\Sigma}^{Z})$
$\displaystyle\leq$
$\displaystyle(\min\\{\lambda_{\min}(\bm{\Sigma}^{U}),\lambda_{\min}(\bm{\Sigma}^{V}\\})^{-1}\leq
b_{0},$

under the stated assumption that $\lambda_{\min}(\bm{\Sigma}^{U})\geq
1/b_{0},\lambda_{\min}(\bm{\Sigma}^{V})\geq 1/b_{0}$, where the first
inequality holds since $(Z_{j},G)$ is a sub-vector of
$Z_{\text{-}k}:=Z_{(1:d)\setminus k}$, the second equality holds by the
relationship between the partial variances and the inverse covariance matrix,
and the last three hold by the definitions of
$\lambda_{\min}(\cdot),\lambda_{\max}(\cdot)$. Thus we have
$f_{g,z_{j}}(z)\leq C\sqrt{\log d}$ for some constant $C$, i.e., Lemma B.7 is
proved.

∎

######  Lemma B.8.

For $z>0$, we have

$\frac{\phi(z)}{2(z\vee
1)}\leq\bar{\Phi}(z)=1-{\Phi}(z)\leq\frac{\phi(z)}{z},$

where $\phi(z),\Phi(z)$ is the PDF and CDF of the standard Gaussian
distribution respectively.

###### Proof of Lemma B.8.

This is a simple fact derived from Mill’s inequality; see the derivations in
the proof of Theorem 3 in Chernozhukov et al. (2015). ∎

######  Lemma B.9.

Whenever $0\leq t\leq C_{0}\sqrt{\log d}$ for some constant $C_{0}>0$, and
$\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log d\\}}$ for some small
enough constant $c>0$, we have

$\Lambda(t,\epsilon,\mathfrak{p}):=\frac{(1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}}}{1-(1-2\bar{\Phi}(\frac{t}{\sigma_{j}}))^{\mathfrak{p}}}\cdot\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}=O\left(\frac{\sqrt{\log
d}}{\mathfrak{p}}\right).$ (B.46)

###### Proof of Lemma B.9.

By Lemma B.8, we can simplify $\Lambda(t,\epsilon,\mathfrak{p})$ into the
following

$\Lambda(t,\epsilon,\mathfrak{p})\leq\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}\vee
1}\right)^{\mathfrak{p}}}{1-\left(1-\frac{\phi(\frac{t}{\sigma_{j}})}{\frac{t}{\sigma}\vee
1}\right)^{\mathfrak{p}}}\cdot\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}.$

When $\frac{t}{\sigma_{j}}\leq 1$, we have $\frac{t+\epsilon}{\sigma_{j}}\leq
2$ due to the choice of $\epsilon$. Because
$\frac{t}{\sigma_{j}}>0,\frac{t+\epsilon}{\sigma_{j}}>0$ and $\phi(z)$ is
monotonically decreasing when $z>0$, we then have the the bound below,

$\Lambda(t,\epsilon,p)\leq\frac{(1-\phi(2)/2)^{\mathfrak{p}}}{1-(1-\phi(1))^{\mathfrak{p}}}=O\left(\frac{\sqrt{\log
d}}{\mathfrak{p}}\right),$

where the second inequality holds due to $0<\phi(2)<\phi(1)<0.5$ and
$\mathfrak{p}>1$. Now it suffices to consider the case where
$\frac{t+\epsilon}{\sigma_{j}}>\frac{t}{\sigma_{j}}>1$ and deal with the
following

$\Lambda(t,\epsilon,\mathfrak{p})\leq\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}{1-\left(1-\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}\cdot\phi\left(\frac{t-\epsilon}{\sigma_{j}}\right).$

We further bound $\Lambda(t,\epsilon,\mathfrak{p})$ as

$\displaystyle\Lambda(t,\epsilon,\mathfrak{p})$ $\displaystyle\leq$
$\displaystyle\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}{1-\left(1-\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}\cdot\phi\Big{(}\frac{t+\epsilon}{\sigma_{j}}\Big{)}\cdot
e^{\frac{t\epsilon}{2\sigma^{2}_{j}}}$ $\displaystyle\leq$ $\displaystyle
2~{}\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}{1-\Bigg{(}1-\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\Bigg{)}^{\mathfrak{p}}}\cdot\phi\Big{(}\frac{t+\epsilon}{\sigma_{j}}\Big{)}$
$\displaystyle:=$ $\displaystyle
2e^{H(\lambda)}\cdot\frac{t+\epsilon}{\mathfrak{p}\sigma_{j}}$

where the first inequality comes from rearranging, the second inequality holds
since $\exp{(\frac{t\epsilon}{2\sigma^{2}_{j}})}<2$ for $t\leq C_{0}\sqrt{\log
d}$. This is because $\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log
d\\}}$ for some small enough constant $c>0$. The last line holds by rewriting
using some new notations:
$\lambda:=\mathfrak{p}~{}\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}$
and

$\displaystyle
H(\lambda):=\log\left(\frac{(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}{1-(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}\cdot\lambda\right)=\mathfrak{p}\log\Big{(}1-\frac{\lambda}{\mathfrak{p}}\Big{)}-\log\Big{(}{1-(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}\Big{)}+\log\lambda.$
(B.47)

Since $\frac{t+\epsilon}{\sigma_{j}}>1$, we have $0<\lambda<\mathfrak{p}$.
Below we will first deal with $H(\lambda)$ then obtain the bound on
$\Lambda(t,\epsilon,\mathfrak{p})$. To bound $H(\lambda)$, consider taking the
derivative of $H(\lambda)$ with respect to $\lambda$, then we have

$\displaystyle H^{\prime}(\lambda)$ $\displaystyle=$
$\displaystyle\frac{\mathfrak{p}}{\lambda-\mathfrak{p}}-\frac{(1-\frac{\lambda}{\mathfrak{p}})^{(\mathfrak{p}-1)}}{1-(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}+\frac{1}{\lambda}$
$\displaystyle=$
$\displaystyle\frac{\mathfrak{p}}{\lambda-\mathfrak{p}}-\frac{1}{1-\frac{\lambda}{\mathfrak{p}}}\cdot\frac{(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}{1-(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}+\frac{1}{\lambda}$
$\displaystyle\leq$
$\displaystyle\frac{\mathfrak{p}}{\lambda-\mathfrak{p}}-\frac{1}{1-\frac{\lambda}{\mathfrak{p}}}\cdot\frac{1-\lambda}{1-(1-\lambda)}+\frac{1}{\lambda}$
$\displaystyle=$
$\displaystyle\frac{\mathfrak{p}}{\lambda-\mathfrak{p}}+\frac{1}{1-\frac{\lambda}{\mathfrak{p}}}-\frac{1}{\lambda}\cdot\frac{1}{1-\frac{\lambda}{\mathfrak{p}}}+\frac{1}{\lambda}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\lambda}\Big{(}1-\frac{\mathfrak{p}}{\mathfrak{p}-\lambda}\Big{)}<0,$

where the first inequality holds by the Bernoulli’s inequality:
${(1+x)^{r}\geq 1+rx}$ when $r\in\mathbb{N},1+x\geq 0$, and the last
inequality holds since $0<\lambda<\mathfrak{p}$. Now we have $H(\lambda)$ is
monotone decreasing. When $0\leq t\leq C_{0}\sqrt{\log d}$, we will first find
the lower bound on
$\lambda=\mathfrak{p}~{}\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}$,
denoted by $\underline{\lambda}$. Then we have $H(\lambda)$ is bounded by
$H(\underline{\lambda})$ due to its monotonicity. Regarding
$\underline{\lambda}$, we denote $\bar{x}:=2C_{0}\sqrt{\log d}/\sigma_{j}$ and
note $\frac{\phi(x)}{x}$ is monotone decreasing when $x\geq 0$. Then we have,
when $0\leq t\leq C_{0}\sqrt{\log d}$,

$\displaystyle\mathfrak{p}~{}\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\geq\mathfrak{p}~{}\frac{\phi(\bar{x})}{\bar{x}}\geq\frac{\mathfrak{p}}{d^{a_{1}}}:=\underline{\lambda},$

where $a_{1}>2$. Therefore we obtain

$\displaystyle H(\lambda)\leq
H({\underline{\lambda}})=\left.\log\left(\frac{(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}{1-(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}}\cdot\lambda\right)\right|_{\lambda=\underline{\lambda}}\leq\left.\log\left(\frac{{\lambda}}{1-(1-\mathfrak{p}\frac{{\lambda}}{\mathfrak{p}}+\frac{(\mathfrak{p}-1)\mathfrak{p}}{2}\frac{\lambda^{2}}{\mathfrak{p}^{2}})}\right)\right|_{\lambda=\underline{\lambda}}\leq
C^{\prime},$ (B.48)

where the second inequality holds due to the fact that
$(1-\frac{\lambda}{\mathfrak{p}})^{\mathfrak{p}}\leq 1$,
$\frac{\lambda}{\mathfrak{p}}\in[0,1]$ and Lemma B.11. The third inequality
holds since
$\underline{\lambda}=\frac{\mathfrak{p}}{d^{a_{1}}}\leq\frac{1}{d^{a_{1}-1}}<\frac{1}{d}$,
then we have

$\left.\left(\frac{{\lambda}}{1-(1-\mathfrak{p}\frac{{\lambda}}{\mathfrak{p}}+\frac{(\mathfrak{p}-1)\mathfrak{p}}{2}\frac{\lambda^{2}}{\mathfrak{p}^{2}})}\right)\right|_{\lambda=\underline{\lambda}}=\frac{\underline{\lambda}}{\underline{\lambda}-\frac{2(\mathfrak{p}-1)}{\mathfrak{p}}\underline{\lambda}^{2}}\leq\frac{\underline{\lambda}}{\underline{\lambda}-2\underline{\lambda}^{2}}=\frac{1}{1-2\underline{\lambda}}\leq
C^{\prime}_{1},$

for some constant $C^{\prime}_{1}$. Now we figure out the bound on
$\Lambda(t,\epsilon,\mathfrak{p})$,

$\displaystyle\Lambda(t,\epsilon,\mathfrak{p})$ $\displaystyle\leq$
$\displaystyle\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}{1-\left(1-\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}\cdot\phi\Big{(}\frac{t-\epsilon}{\sigma_{j}}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}{1-\left(1-\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}\cdot\phi\Big{(}\frac{t+\epsilon}{\sigma_{j}}\Big{)}\cdot
e^{\frac{t\epsilon}{2\sigma^{2}_{j}}}$ $\displaystyle\leq$ $\displaystyle
2~{}\frac{\left(1-\frac{{\phi}(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\right)^{\mathfrak{p}}}{1-\Bigg{(}1-\frac{\phi(\frac{t+\epsilon}{\sigma_{j}})}{\frac{t+\epsilon}{\sigma_{j}}}\Bigg{)}^{\mathfrak{p}}}\cdot\phi\Big{(}\frac{t+\epsilon}{\sigma_{j}}\Big{)}$
$\displaystyle\leq$ $\displaystyle
2e^{H(\lambda)}\cdot\frac{t+\epsilon}{\mathfrak{p}\sigma_{j}}\leq\frac{C\sqrt{\log
d}}{\mathfrak{p}},$

where the second inequality comes from rearranging, the third inequality holds
since $\exp{(\frac{t\epsilon}{2\sigma^{2}_{j}})}<2$ for $t\leq C_{0}\sqrt{\log
d}$. This is because $\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log
d\\}}$ for some small enough constant $c>0$. And the last line holds by (B.47)
and (B.48). Therefore Lemma B.9 is established. ∎

######  Lemma B.10.

Under the same conditions as Lemma B.9, we have

$\frac{(1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}-1}}{1-(1-2\bar{\Phi}(\frac{t}{\sigma_{j}}))^{\mathfrak{p}}}\cdot\Big{(}\mathfrak{p}\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}\Big{)}^{2}=O\left(\sqrt{\log
d}\right).$ (B.49)

###### Proof.

Note that the result (B.46) in Lemma B.9 can be rewritten as

$\mathfrak{p}~{}\Lambda(t,\epsilon,\mathfrak{p})=\frac{(1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}}}{1-(1-2\bar{\Phi}(\frac{t}{\sigma_{j}}))^{\mathfrak{p}}}\cdot\Big{(}\mathfrak{p}\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}\Big{)}=O\left(\sqrt{\log
d}\right).$

By similar derivations as in the proof of Lemma B.9, we can establish

$\frac{(1-2\bar{\Phi}(\frac{t+\epsilon}{\sigma_{j}}))^{\mathfrak{p}-1}}{1-(1-2\bar{\Phi}(\frac{t}{\sigma_{j}}))^{\mathfrak{p}}}\cdot\Big{(}\mathfrak{p}\phi\big{(}\frac{t-\epsilon}{\sigma_{j}}\big{)}\Big{)}^{2}=O\left(\sqrt{\log
d}\right).$

∎

######  Lemma B.11.

For $x\in[0,1]$, we have $(1-x)^{\mathfrak{p}}\leq
1-\mathfrak{p}x+0.5\mathfrak{p}(\mathfrak{p}-1)x^{2}$.

###### Proof.

When $\mathfrak{p}=1$, the above simply holds. Now we consider the case where
$\mathfrak{p}>1$. Let
$Q(x)=(1-x)^{\mathfrak{p}}-(1-\mathfrak{p}x+0.5\mathfrak{p}(\mathfrak{p}-1)x^{2})$,
we have $Q(0)=0$ and

$\displaystyle
Q^{\prime}(x)=-\mathfrak{p}(1-x)^{(\mathfrak{p}-1)}+\mathfrak{p}-\mathfrak{p}(\mathfrak{p}-1)x\leq-\mathfrak{p}(1-(\mathfrak{p}-1)x)+\mathfrak{p}-\mathfrak{p}(\mathfrak{p}-1)x=0,$
(B.50)

where the inequality holds by applying Bernoulli’s inequality to
$(1-x)^{(\mathfrak{p}-1)}$ for $\mathfrak{p}>1,x\in[0,1]$. Therefore, $Q(x)$
is monotonically decreasing, and the statement is proved. ∎

###  B.4 Ancillary lemmas for Theorem 3.2

######  Remark B.3.

Recall that the connectivity assumption of Theorem 3.2 assumes that there
exists a disjoint $\mathfrak{p}$-partition of nodes
$\cup_{\ell=1}^{\mathfrak{p}}\mathcal{C}_{\ell}=[d]$ such that
$\sigma^{U}_{jk}=\sigma^{V}_{jk}=0$ when $j\in\mathcal{C}_{\ell}$ and
$k\in\mathcal{C}_{\ell^{\prime}}$ for some $\ell\neq\ell^{\prime}$. The more
general version of the variance condition assumes:
$a_{0}\leq\sigma^{U}_{jj}=\sigma^{V}_{jj}\leq a_{1},~{}\forall j\in[d]$; given
any $j\in\mathcal{C}^{U}_{\ell}$ with some $\ell$, there exists at least one
$m\in\mathcal{C}^{U}_{\ell^{\prime}}$ such that
$\sigma^{U}_{jj}=\sigma^{U}_{mm}$ for any $\ell^{\prime}\neq\ell$. Denote
$\widetilde{\sigma}^{U}_{jk}={\sigma}^{U}_{jk}/\sqrt{{\sigma}^{U}_{jj}{\sigma}^{U}_{kk}}$.
And the general covariance condition says that there exists some
$\sigma_{0}<1$ such that
$|\widetilde{\sigma}^{V}_{jk}|=|{\sigma}^{V}_{jk}|/\sqrt{{\sigma}^{V}_{jj}{\sigma}^{V}_{kk}}\leq\sigma_{0}$
for any $j\neq k$ and $|\\{(j,k):j\neq
k,|\widetilde{\sigma}^{U}_{jk}|=|{\sigma}^{U}_{jk}|/\sqrt{\sigma^{U}_{jj}\sigma^{U}_{kk}}>\sigma_{0}\\}|\leq
b_{0}$ for some constant $b_{0}$.

######  Lemma B.12.

For the term
$\mathrm{II}_{1}=\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(E_{1})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right]$ with ${E_{1}}$ defined in (B.20) and
$\epsilon={c}/{\max\\{(\log d)^{3/2},\mathfrak{p}\log d\\}}$ for some small
enough constant $c>0$, whenever $t$ satisfies $0\leq t\leq C_{0}\sqrt{\log d}$
for some constant $C_{0}>0$, we have

$\displaystyle\frac{\mathrm{II}_{1}}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}}\left(1+\frac{b_{0}}{\sqrt{1-(s+(1-s)\sigma_{0})^{2}}}\right).$
(B.51)

for any $s\in(0,1)$, where $\sigma_{0}<1$ and $b_{0}$ are the constants in the
assumption of Theorem 3.2.

######  Remark B.4.

Recall the definition of $Z=W(s)$. Hence the term $\mathrm{II}_{1}$ depends on
$s$. In Lemma B.5, we are able to derive a uniform upper bound when assuming
the minimal eigenvalue condition as in Theorem B.4. Since Theorem 3.2 does not
make assumptions about the minimal eigenvalue condition, we will bound the
term $\mathrm{II}_{1}$ differently and the upper bound depend on $s$, as
showed in the following proof.

###### Proof of Lemma B.12.

We basically use the same proof strategy as Lemma but will separately deal
with two cases. First recall that

$\displaystyle\mathrm{II}_{1}=~{}$
$\displaystyle\mathbb{E}\left[{e^{-\beta(||Z||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(||Z||_{\infty}>||G||_{\infty},||Z||_{\infty}>Z_{j})}\cdot\mathds{1}{(t-\epsilon\leq||Z||_{\infty}\leq
t+\epsilon)}}\right].$

We define $Z^{\dagger}=(Z_{k})_{k\in\mathcal{E}^{\dagger}}$ where

$\mathcal{E}^{\dagger}=\\{j\\}\cup\mathcal{E}_{G}\cup\\{k\in[d]:|\widetilde{\sigma}^{U}_{jk}|\leq\sigma_{0},\max_{m\in\mathcal{E}_{G}}\\{|\widetilde{\sigma}^{U}_{mk}|\\}\leq\sigma_{0}\\}.$
(B.52)

Under the condition of Theorem 3.2, we have
$|[d]\setminus\mathcal{E}^{\dagger}|\leq|\\{(j,k):j\neq
k,|\widetilde{\sigma}^{U}_{jk}|\\}>\sigma_{0}\\}|\leq b_{0}$ for some constant
$b_{0}$. Note we can write
$1=\mathds{1}{(||Z^{\dagger}||_{\infty}=||Z||_{\infty})}+\sum_{k\in[d]\setminus\mathcal{E}^{\dagger}}\mathds{1}{(|Z_{k}|=||Z||_{\infty})}$.
Then we have

$\displaystyle\frac{\mathrm{II}_{1}}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{\mathrm{II}^{\dagger}_{1}}{\mathbb{P}(||V||_{\infty}>t)}+b_{0}\cdot\max_{k\in[d]\setminus\mathcal{E}^{\dagger}}\frac{\mathrm{II}^{(k)}_{1}}{\mathbb{P}(||V||_{\infty}>t)},$
(B.53)

where $\mathrm{II}^{\dagger}_{1}$ and $\mathrm{II}^{(k)}_{1}$ are defined as

$\displaystyle\begin{split}\mathrm{II}^{\dagger}_{1}:=&\mathbb{E}\left[{e^{-\beta(||Z^{\dagger}||_{\infty}-|Z_{j}|)}\cdot\mathds{1}{(||Z^{\dagger}||_{\infty}>||G||_{\infty},||Z^{\dagger}||_{\infty}>Z_{j})}\cdot\mathds{1}{(t-\epsilon\leq||Z^{\dagger}||_{\infty}\leq
t+\epsilon)}}\right],\\\
\mathrm{II}^{(k)}_{1}:=&\mathbb{E}\left[{e^{-\beta(|Z_{k}|-|Z_{j}|)}\cdot\mathds{1}{(|Z_{k}|>||G||_{\infty},|Z_{k}|>Z_{j})}\cdot\mathds{1}{(t-\epsilon\leq|Z_{k}|\leq
t+\epsilon)}}\right].\end{split}$ (B.54)

Denote the conditional density function of $||Z^{\dagger}||_{\infty}\mid
Z_{j}=z_{j},G=g$ by $f^{\dagger}_{g,z_{j}}(u)$. Then we apply exactly the same
derivations as in Lemma B.5 (except that $f^{\dagger}_{g,z_{j}}(u)$ is bounded
using Lemma B.13 instead of Lemma B.7) and obtain the following bound

$\frac{\mathrm{II}^{\dagger}_{1}}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}}.$ (B.55)

Regarding the term $\mathrm{II}^{(k)}_{1}$, we follow the same derivations as
in the beginning of the proof of Lemma B.5. Specifically, we have

$\displaystyle\mathrm{II}^{(k)}_{1}=~{}$
$\displaystyle\mathbb{E}\left[{e^{-\beta(|Z_{k}|-|Z_{j}|)}\cdot\mathds{1}{(|Z_{k}|>||G||_{\infty},|Z_{k}|>Z_{j})}\cdot\mathds{1}{(t-\epsilon\leq|Z_{k}|\leq
t+\epsilon)}}\right]$ $\displaystyle=~{}$
$\displaystyle\mathbb{E}\left[{e^{\beta|Z_{j}|}\cdot\mathds{1}{(||G||_{\infty}\leq
t+\epsilon,|Z_{j}|\leq
t+\epsilon)}\left(\int_{t-\epsilon}^{t+\epsilon}f_{Z_{j}}(u)e^{-\beta
u}\mathds{1}{(u>||G||_{\infty},u>|Z_{j}|)}du\right)}\right],$ (B.56)

where $f_{Z_{j},G}(u)$ denotes the conditional density of $Z_{k}$ given
$Z_{j},G$. Recall the construction of $G$ described in the proof of Theorem
3.2, we have for any $k\neq
j,k\notin\mathcal{E}_{G}=\\{m\in[d]:Z_{m}=G_{\ell}\text{ for some
}\ell\in[\mathfrak{p}]\\}$, there exists at most one
$m\in\\{j\\}\cup\mathcal{E}_{G}$, such that $Z_{k}$ and $Z_{m}$ belong to the
same component. Denote that random variable by $Z_{m_{0}}$, then
$f_{Z_{j},G}(u)$ is just the conditional density function of $Z_{k}$ given
$Z_{m_{0}}$. Since $Z$ follows a multivariate Gaussian distribution, we can
immediately figure out the expression of the conditional density
$f_{Z_{m_{0}}}(u)$ and simply derive a bound

$\displaystyle f_{Z_{j},G}(u)=f_{Z_{m_{0}}}(u)$
$\displaystyle\leq\frac{1}{\sqrt{2\pi\mathrm{Var}\left({Z_{k}}\,|\,{Z_{m_{0}}}\right)}}$
$\displaystyle=\frac{1}{\sqrt{2\pi(\sigma_{kk}-\sigma^{2}_{km_{0}}/\sigma_{m_{0}m_{0}}))}}$
$\displaystyle=\frac{1}{\sqrt{2\pi\sigma_{kk}}}\cdot\frac{1}{1-\sigma^{2}_{km_{0}}/(\sigma_{kk}\sigma_{m_{0}m_{0}})}$
$\displaystyle\leq\frac{1}{\sqrt{2\pi
a_{0}}}\cdot\frac{1}{1-\sigma^{2}_{km_{0}}/(\sigma_{kk}\sigma_{m_{0}m_{0}})},$
(B.57)

where
$\sigma_{kk}=\mathrm{Var}\left({Z_{k}}\right),\sigma_{m_{0}m_{0}}=\mathrm{Var}\left({Z_{m_{0}}}\right),\sigma_{km_{0}}=\mathrm{Cov}\left({Z_{k}},{Z_{m_{0}}}\right)$
and we use the fact that
$\sigma_{kk}=\mathrm{Var}\left({Z_{k}}\right)=\sigma^{U}_{kk}\geq a_{0}$
(under the general variance assumption). Note $Z=\sqrt{s}U+\sqrt{1-s}V$, then
we have
$\sigma^{2}_{km_{0}}=(\mathrm{Cov}\left({Z_{k}},{Z_{m_{0}}}\right))^{2}=(s{\sigma}_{km_{0}}^{U}+(1-s){\sigma}_{km_{0}}^{V})^{2}$
where $m_{0}\in\\{j\\}\cup\mathcal{E}_{G}$. Since
$|\widetilde{\sigma}_{km_{0}}^{U}|\leq 1$ by definition and
$|\widetilde{\sigma}_{km_{0}}^{V}|\leq\sigma_{0}$ under the assumption of
Theorem 3.2, we have

$(s{\sigma}_{km_{0}}^{U}+(1-s)\sigma_{km_{0}}^{V})^{2}/(\sigma_{kk}\sigma_{m_{0}m_{0}})=(s\widetilde{\sigma}_{km_{0}}^{U}+(1-s)\widetilde{\sigma}_{km_{0}}^{V})^{2}\leq(s+(1-s)\sigma_{0})^{2}.$
(B.58)

Now we obtain a upper bound on the conditional density function
$f_{Z_{j},G}(u)$ based on (B.57) and (B.58). Combining this bound and
following the same derivations as in Lemma B.5 to deal with the term in
(B.56), we establish the upper bound on the term
$\mathrm{II}^{(k)}_{1}/\mathbb{P}(||V||_{\infty}>t)$ for any
$k\in[d]\setminus\mathcal{E}^{\dagger}$,

$\frac{\mathrm{II}^{(k)}_{1}}{\mathbb{P}(||V||_{\infty}>t)}\leq\frac{C^{\prime}\epsilon\log
d}{\beta\mathfrak{p}}\cdot\frac{1}{\sqrt{1-(s+(1-s)\sigma_{0})^{2}}}.$ (B.59)

Combining (B.53), (B.54),(B.55) with (B.59), we derive the bound in (B.51). ∎

######  Lemma B.13.

Recall that the density function of the conditional distribution of
$||Z^{\dagger}||_{\infty}\mid\\{Z_{j}=z_{j},G=g\\}$ is denoted by
$f^{{\dagger}}_{g,z_{j}}(z)$ where $Z^{\dagger}$ is defined in …. Suppose
$\epsilon>0$, when $0\leq t\leq C_{0}\sqrt{\log d}$ for some constant
$C_{0}>0$ and $|z_{j}|,||g||_{\infty}\leq t+\epsilon$, we have

$f^{{\dagger}}_{g,z_{j}}(z)\leq C\sqrt{\log
d},\quad\forall~{}z\in(\max\\{|z_{j}|,||g||_{\infty}\\},t+\epsilon].$ (B.60)

where the finite constant $C$ depends on $a_{0}$ and $\sigma_{0}<1$.

###### Proof of Lemma B.13.

Following exactly the same derivations as in Lemma B.7 (up to (B.45)), we have

$f^{{\dagger}}_{g,z_{j}}(z)\leq\frac{6}{\underline{\sigma_{\cdot
j}}}\left(\frac{2\bar{\rho}_{j}(1+c_{0})+1}{\underline{\sigma_{\cdot
j}}}C_{1}\sqrt{\log d}+C_{2}\sqrt{\log d}\right),$ (B.61)

for any $z\in(\max\\{|z_{j}|,||g||_{\infty}\\},t+\epsilon]$, where
$C_{1},C_{2}$ are some constants. First, $\bar{\rho}_{j}$ is defined in
(B.37). Simply, we have

$\bar{\rho}_{j}\leq\max_{k\neq
j}\frac{|\sigma_{jk}|}{\sigma_{jj}}\leq\frac{\max_{j}\sigma_{jj}^{U}}{\min_{j}\sigma_{jj}^{U}}\leq\frac{a_{1}}{a_{0}}$

under the general variance assumption. Recall the construction of $G$
described in the proof of Theorem 3.2, we have for any $k\neq
j,k\notin\mathcal{E}_{G}=\\{m\in[d]:Z_{m}=G_{\ell}\text{ for some
}\ell\in[\mathfrak{p}]\\}$, there is at most one $m\in\mathcal{E}_{G}$, such
that $Z_{k}$ and $Z_{m}$ belong to the same component. Then we have

$\sum_{m\in\mathcal{E}_{G}}\mathds{1}{(\sigma_{km}\neq 0)}\leq 1,$

hence $c_{0}=1$ by definition. Also note by the definition of $Z^{\dagger}$
and $\mathcal{E}^{\dagger}$ in (B.52), for any
$k\in\mathcal{E}^{\dagger},k\neq j,k\neq\mathcal{E}_{G}$, we have

$\max\\{|\widetilde{\sigma}^{U}_{jk}|,|\widetilde{\sigma}^{V}_{jk}|\\}\\}\leq\sigma_{0},\quad\max_{m\in\mathcal{E}_{G}}\\{|\widetilde{\sigma}^{U}_{mk}|,|\widetilde{\sigma}^{V}_{mk}|\\}\leq\sigma_{0}$
(B.62)

under the assumption of Theorem 3.2. We will take advantage of this together
with the above property of $G$ to derive a bound on $\underline{\sigma_{\cdot
j}}$. Similarly as in (B.37), we have $\underline{\sigma^{2}_{\cdot
j}}:=\min_{k\in\mathcal{E}_{X}}\mathrm{Var}\left({Z_{k}}\,|\,{Z_{j},G}\right)$
with $\mathcal{E}_{X}:=\\{k\in\mathcal{E}^{\dagger}:k\neq
j,k\notin\mathcal{E}_{G}\\}$. For each $k\in\mathcal{E}_{X}$, we have it can
at most belong to the same component as one of $\\{j\\}\cup\mathcal{E}_{G}$,
due to the property of $G$. Then we have

$\displaystyle\mathrm{Var}\left({Z_{k}}\,|\,{Z_{j},G}\right)$
$\displaystyle\geq$
$\displaystyle\min\\{\mathrm{Var}\left({Z_{k}}\,|\,{Z_{j}}\right),\min_{m\in\mathcal{E}_{G}}\\{\mathrm{Var}\left({Z_{k}}\,|\,{Z_{m}}\right)\\}\\}$
(B.63) $\displaystyle=$
$\displaystyle{\sigma_{kk}}\cdot\min\\{1-\sigma_{jk}^{2}/(\sigma_{jj}\sigma_{kk}),\min_{m\in\mathcal{E}_{G}}\\{1-\sigma^{2}_{mk}/(\sigma_{mm}\sigma_{kk})\\}\\}$
$\displaystyle\geq$ $\displaystyle
a_{0}\cdot\min\\{1-\sigma_{jk}^{2}/(\sigma_{jj}\sigma_{kk}),\min_{m\in\mathcal{E}_{G}}\\{1-\sigma^{2}_{mk}/(\sigma_{mm}\sigma_{kk})\\}\\}.$

since $(Z_{j},G)$ are all independent and
$\sigma_{kk}=\mathrm{Var}\left({Z_{k}}\right)=\sigma^{U}_{kk}\geq a_{0}$
(under the general variance assumption). Recall the definition of
$Z=\sqrt{s}U+\sqrt{1-s}V$, we have

$|\sigma_{mk}|/\sqrt{\sigma_{mm}\sigma_{kk}}=|\mathrm{Cov}\left({Z_{k}},{Z_{m}}\right)|/\sqrt{\sigma_{mm}\sigma_{kk}}=|s\widetilde{\sigma}^{U}_{mk}+(1-s)\widetilde{\sigma}^{V}_{mk}|\leq\sigma_{0},\quad\forall~{}s\in[0,1],$
(B.64)

when $m\in\\{j\\}\cup\mathcal{E}_{G}$. This is due to (B.62). Then we can
derive a bound on ${1}/{\underline{\sigma^{2}_{\cdot j}}}$, i.e.,

$\displaystyle\frac{1}{\underline{\sigma^{2}_{\cdot j}}}$ $\displaystyle=$
$\displaystyle\frac{1}{\min_{k\in\mathcal{E}_{X}}\mathrm{Var}\left({Z_{k}}\,|\,{Z_{j},G}\right)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{a_{0}\min_{k\in\mathcal{E}_{X}}\min\\{1-\sigma_{jk}^{2}/(\sigma_{jj}\sigma_{kk}),\min_{m\in\mathcal{E}_{G}}\\{1-\sigma_{mk}^{2}/(\sigma_{mm}\sigma_{kk})\\}\\}}$
$\displaystyle\leq$ $\displaystyle\frac{1}{a_{0}(1-\sigma^{2}_{0})},$

where the first inequality holds by (B.63) and the second equality holds by
(B.64). Combining the above bound with (B.61), we finally establish (B.60) for
some finite constant $C$. ∎

##  Appendix C Ancillary propositions for FDR control

Throughout this section, we introduce some new notations. For a given mean
zero random vector $\bm{Y}\in\mathbb{R}^{d}$ with positive semi-definite
covariance matrix
$\bm{\Sigma}^{Y}:=\mathbb{E}\left[{\bm{Y}\bm{Y}^{\top}}\right]\in\mathbb{R}^{d\times
d}$, we denote its Gaussian counterpart by $\bm{Z}\in\mathbb{R}^{d}$ (i.e.,
$\mathbb{E}\left[{\bm{Z}}\right]=\mathbf{0}$ and its covariance matrix
$\mathbb{E}\left[{\bm{Z}\bm{Z}^{\top}}\right]:=\bm{\Sigma}^{Z}$ equals
$\bm{\Sigma}^{Y}=(\sigma_{jk}^{Y})_{1\leq j,k\leq d}$ ). Consider $n$ i.i.d.
copies of $\bm{Y}$, denoted by
$\bm{Y}_{1},\cdots,\bm{Y}_{n}\in\mathbb{R}^{d}$. We define the maximum
$T_{\bm{Y}}$ and $T_{\bm{Z}}$ as below,

$T_{\bm{Y}}:=\left\|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bm{Y}_{i}\right\|_{\infty},\quad
T_{\bm{Z}}:=||\bm{Z}||_{\infty},$ (C.1)

where $q(\alpha;T_{\bm{Y}})$ and $q(\alpha;T_{\bm{Z}})$ ($\alpha\in[0,1]$) are
the corresponding upper quantile functions. Define the Gaussian multiplier
bootstrap counterpart as

$T_{\bm{W}}:=\left\|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bm{Y}_{i}\xi_{i}\right\|_{\infty},$
(C.2)

where $\xi_{i}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\mathcal{N}(0,1)$ and
are independent from $\bm{Y}_{1},\cdots,\bm{Y}_{n}$. Let
$q_{\xi}(\alpha;T_{\bm{W}})$ be the conditional quantile of $T_{\bm{W}}$, then
we have $\mathbb{P}_{\xi}\left({T_{\bm{W}}\geq
q_{\xi}(\alpha;T_{\bm{W}})}\right)=\alpha$. Note that we use the $\xi$
subscript to remind ourselves that the probability measure is induced by the
multiplier random variables $\\{\xi_{i}\\}_{i=1}^{n}$ conditional on
$\\{\bm{Y}_{i}\\}_{i=1}^{n}$. And we have the covariance matrix of
$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bm{Y}_{i}\xi_{i}$ (conditional on
$\\{\bm{Y}_{i}\\}_{i=1}^{n}$) equals
$\bm{\Sigma}^{W}:=\frac{1}{n}\sum_{i=1}^{n}\bm{Y}_{i}\bm{Y}_{i}^{\top}$.
Denote $\Delta_{\infty}=||\bm{\Sigma}^{Z}-\bm{\Sigma}^{W}||_{\infty}$, which
measures the maximal differences between the true covariance matrix
$\bm{\Sigma}^{Z}$ and the sample version $\bm{\Sigma}^{W}$.

###  C.1 Cramér-type deviation bounds for the Gaussian multiplier bootstrap

Based on the Cramér-type Gaussian comparison bound in Theorem 3.1, the Cramér-
type approximation bound (Kuchibhotla et al., 2021), the maximal inequalities
and a careful treatment to the comparison of quantiles, we will establish the
Cramér-type deviation bounds for the Gaussian multiplier bootstrap (CGMB) in
this section.

######  Proposition C.1 (CGMB).

Assuming the covariance matrix $\bm{\Sigma}^{Y}$ satisfies
$0<c_{1}\leq\sigma^{Y}_{jj}\leq c_{2}<\infty$, for any $j\in[d]$ and $\bm{Y}$
satisfies the tail condition that $\max_{1\leq i\leq n}\max_{1\leq j\leq
p}||\bm{Y}_{ij}||_{\psi_{1}}\leq K_{3}$ for some constants
$c_{1},c_{2},K_{3}$, under the scaling condition $(\log
ed)^{3}(\log(ed+n))^{56/3}/n=o(1)$, we have the following bound,

$\sup_{\alpha\in[\alpha_{L},1]}\left|\frac{\mathbb{P}(T_{\bm{Y}}>q_{\xi}(\alpha;T_{\bm{W}}))}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|=O\left(\frac{(\log
d)^{11/6}}{n^{1/6}\alpha_{L}^{1/3}}+\frac{(\log d)^{19/6}}{n^{1/6}}\right),$
(C.3)

where $\alpha_{L}$ satisfies $q(\alpha_{L};T_{\bm{Z}})=O\left(\sqrt{\log
d}\right)$ and $\frac{\log^{11}d}{n\alpha_{L}}=O(1)$.

The proof can be found in Appendix C.2. In practice, there are many situations
where the relevant statistics come from the maxima of approximated averages.
In particular, the test statistics in our node selection problem can not be
directly expressed as maxima of scaled averages, but can be approximated by a
$T_{\bm{Y}}$-like term with the approximation error suitably controlled.
Therefore, we also prove an extended version of Proposition C.1. Suppose the
statistics of interest and its Gaussian multiplier bootstrap counterpart,
denoted by $T$ and $T^{\mathcal{B}}$ respectively, can be approximated by
$T_{\bm{Y}}$ (defined in (C.1)) and $T_{\bm{W}}$ (defined in (C.2)). The
quantile functions $q(\alpha;T)$ and $q_{\xi}(\alpha;T^{\mathcal{B}})$ are
defined correspondingly.

######  Proposition C.2 (CGMB with approximation).

Under the same conditions as in Proposition C.1 and the additional assumption
about the differences between the maximum statistics:

$\displaystyle\mathbb{P}(|T-T_{\bm{Y}}|>\zeta_{1})<\zeta_{2},$ (C.4)
$\displaystyle\mathbb{P}(\mathbb{P}_{\xi}(|T^{\mathcal{B}}-T_{\bm{W}}|>\zeta_{1})>\zeta_{2})<\zeta_{2},$
(C.5)

where $\zeta_{1},\zeta_{2}\geq 0$ characterize the approximation error and
satisfy $\zeta_{1}\log d=O(1),\zeta_{2}=O(\alpha_{L})$, we have the following
Cramér-type deviation bound

$\sup_{\alpha\in[\alpha_{L},1]}\left|\frac{\mathbb{P}(T>q_{\xi}(\alpha;T^{\mathcal{B}}))}{\mathbb{P}(T_{\bm{Z}}>q(\alpha;T_{\bm{Z}}))}-1\right|=\eta(d,n,\zeta_{1},\zeta_{2},\alpha_{L}),$
(C.6)

where $\eta(d,n,\zeta_{1},\zeta_{2},\alpha_{L})=O\left(\frac{(\log
d)^{19/6}}{n^{1/6}}+\frac{(\log
d)^{11/6}}{n^{1/6}\alpha_{L}^{1/3}}+\zeta_{1}\log
d+\frac{\zeta_{2}}{\alpha_{L}}\right)$.

###  C.2 Proof of Proposition C.1

Before proving Proposition C.1, we present Lemma C.1. It bounds the
conditional quantile $q_{\xi}(\alpha;T_{\bm{W}})$ in terms of the quantile
$q(\alpha;T_{\bm{Z}})$ of the Gaussian maxima $T_{\bm{Z}}$ when the maximal
covariance matrix differences are controlled. In the proof of Lemma C.1, we
apply the Cramér-type comparison bound (3.1), which is establised in Theorem
3.1. To simplify the notation, we denote the bound $C_{1}(\log
d)^{5/2}\Delta_{\infty}^{1/2}$ in (3.1) by $\pi(\Delta_{\infty})$, where the
constant $C_{1}$ only depends on $\min_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$, $\max_{1\leq j\leq
d}\\{\sigma^{U}_{jj},\sigma^{V}_{jj}\\}$.

######  Lemma C.1.

Suppose $\delta$ satisfies $(\log d)^{5}\delta=O(1)$. On the event
$\\{\Delta_{\infty}\leq\delta\\}$, we have

$\displaystyle{q_{\xi}(\alpha;T_{\bm{W}})\geq
q\Big{(}\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}}\Big{)}},$ (C.7)
$\displaystyle{q_{\xi}(\alpha;T_{\bm{W}})\leq
q\Big{(}\frac{\alpha}{1+\pi(\delta)};T_{\bm{Z}}\Big{)}}.$ (C.8)

###### Proof of Lemma C.1.

On the event $\\{\Delta_{\infty}\leq\delta\\}$, we have $(\log
d)^{5}\Delta_{\infty}\leq(\log d)^{5}\delta=O(1)$, then by applying Theorem
3.1 to $\bm{Z}$ and $\bm{W}$, we obtain the following,

$\sup_{0\leq t\leq C_{0}\sqrt{\log
d}}\left|\frac{\mathbb{P}_{\xi}(T_{\bm{W}}>t)}{\mathbb{P}(T_{\bm{Z}}>t)}-1\right|\leq\pi(\delta).$

Therefore we have

$\mathbb{P}_{\xi}\left({T_{\bm{W}}\geq
q\Big{(}\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}}\Big{)}}\right)\geq\mathbb{P}\left({T_{\bm{Z}}\geq
q\Big{(}\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}}\Big{)}}\right)\cdot(1-\pi(\delta))=\alpha,$

when $t$ satisfies $0\leq t\leq C_{0}\sqrt{\log d}$. Then
$q_{\xi}(\alpha;T_{\bm{W}})\geq
q\Big{(}\frac{\alpha}{1-\pi(\delta)};T_{\bm{Z}}\Big{)}$ immediately follows,
i.e., (C.7) holds. Similarly, on the event $\\{\Delta_{\infty}\leq\delta\\}$,
we have

$\mathbb{P}_{\xi}\left({T_{\bm{W}}\geq
q\Big{(}\frac{\alpha}{1+\pi(\delta)};T_{\bm{Z}}\Big{)}}\right)\leq\mathbb{P}\left({T_{\bm{Z}}\geq
q\Big{(}\frac{\alpha}{1+\pi(\delta)};T_{\bm{Z}}\Big{)}}\right)\cdot(1+\pi(\delta))=\alpha.$

Thus $q_{\xi}(\alpha;T_{\bm{W}})\leq
q\Big{(}\frac{\alpha}{1+\pi(\delta)};T_{\bm{Z}}\Big{)}$, i.e., (C.8) holds. ∎