$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{4}}.$

Similarly,

$\displaystyle\mathrm{Var}(Z_{4b}^{*})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\bigg{(}\sum_{ijk\ell
st}\big{[}\beta_{j}^{2}\beta_{k}^{2}\theta_{i}^{2}\theta_{j}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{s}\theta_{t}+\beta_{k}^{2}\beta_{\ell}\beta_{j}\theta_{i}^{2}\theta_{j}^{3}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{s}^{2}\theta_{t}+\beta_{j}\beta_{k}^{2}\beta_{\ell}\theta_{i}^{2}\theta_{j}^{3}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{s}^{2}\theta_{t}\bigg{)}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

It follows that

$\displaystyle\mathrm{Var}(Z_{4b})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

We study $Z_{4c}$ using the decomposition

$\displaystyle Z_{4c}$
$\displaystyle=\frac{1}{v}\sum_{i,\ell(dist)}\beta_{i\ell}W^{3}_{\ell
i}+\frac{2}{v}\sum_{\begin{subarray}{c}i,\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\beta_{i\ell}W_{is}W^{2}_{\ell
i}+\frac{1}{v}\sum_{\begin{subarray}{c}i,\ell(dist)\\\
s\notin\\{i,\ell\\},t\notin\\{\ell,i\\}\end{subarray}}\beta_{i\ell}W_{is}W_{\ell
t}W_{\ell i}$
$\displaystyle\equiv\widetilde{Z}_{4c}+Z^{*}_{4c}+Z^{{\dagger}}_{4c}.$

from (Jin et al., 2021c, Supplement, pg.68). Only

$\tilde{Z}_{4c}=\frac{1}{v}\sum_{i,\ell(dist)}\alpha_{i\ell}W^{3}_{\ell i}$

has nonzero mean, where
$\alpha_{i\ell}=\sum_{j,k(dist)\notin\\{i,\ell\\}}\eta_{j}\eta_{k}\widetilde{\Omega}_{jk}$.
By (E.20)

$\displaystyle|\alpha_{i\ell}|\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}.$

Hence

$\displaystyle|\mathbb{E}\tilde{Z}_{4c}|\lesssim\frac{1}{\|\theta\|_{1}^{2}}\sum_{i\ell}\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}\theta_{i}\theta_{\ell}\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}.$

Except for when $(i,\ell)=(\ell,i)$, the summands of $\tilde{Z}_{4c}$ are
uncorrelated. Thus

$\displaystyle\mathrm{Var}(\tilde{Z}_{4c})\lesssim\frac{1}{\|\theta\|_{1}^{4}}\sum_{i\ell}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i}\theta_{\ell}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

Applying the casework from (Jin et al., 2021c, Supplement, pg.68),

$\displaystyle\mathrm{Var}(Z_{4c}^{*})$
$\displaystyle\lesssim\sum_{\begin{subarray}{c}i,\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\sum_{\begin{subarray}{c}i^{\prime},\ell^{\prime}(dist)\\\
s^{\prime}\notin\\{i^{\prime},\ell^{\prime}\\}\end{subarray}}|\alpha_{i\ell}\alpha_{i^{\prime}\ell^{\prime}}|\mathrm{Cov}(W_{is}W_{\ell
i}^{2},W_{i^{\prime}s^{\prime}}W_{\ell^{\prime}i^{\prime}}^{2})|$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\big{(}\sum_{i\ell
s}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i}^{2}\theta_{\ell}\theta_{s}+\sum_{i\ell
s\ell^{\prime}}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i}^{3}\theta_{\ell}\theta_{s}\theta_{\ell^{\prime}}\big{)}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\big{(}\|\theta\|_{2}^{2}\|\theta\|_{1}^{2}+\|\theta\|_{2}^{2}\|\theta\|_{1}^{3}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}}.$

Next, in (Jin et al., 2021c, Supplement, pg.69) it is shown that

$\displaystyle\mathrm{Var}(Z^{{\dagger}}_{4c})$
$\displaystyle\lesssim\frac{1}{v^{2}}\sum_{\begin{subarray}{c}i,\ell(dist)\\\
s\notin\\{i,\ell\\},t\notin\\{\ell,i\\}\end{subarray}}\alpha^{2}_{i\ell}\cdot\mathrm{Var}(W_{is}W_{\ell
t}W_{\ell i})$

Thus

$\displaystyle\mathrm{Var}(Z^{{\dagger}}_{4c})$
$\displaystyle\lesssim\sum_{i\ell
s}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i}^{2}\theta_{\ell}^{2}\theta_{s}\theta_{t}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{2}}.$

Combining the results for $\tilde{Z}_{4c},Z_{4c}^{*},Z_{4c}^{\dagger}$, we
have

$\displaystyle|\mathbb{E}Z_{4c}|\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2},\quad\mathrm{Var}(Z_{4c})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}}.$

Combining the results for $Z_{4a},Z_{4b},$ and $Z_{4c}$, we have

$\displaystyle|\mathbb{E}Z_{4}|\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2},\quad\mathrm{Var}(Z_{4})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}}$

To study $Z_{5}$, we use the decomposition

$\displaystyle Z_{5}$
$\displaystyle=2\sum_{i,j,k,\ell(dist)}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})\eta_{j}(\eta_{k}-\tilde{\eta}_{k})\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}+\sum_{i,j,k,\ell(dist)}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}$ (E.49)
$\displaystyle\qquad+\sum_{i,j,k,\ell(dist)}(\eta_{i}-\tilde{\eta}_{i})\eta^{2}_{j}(\eta_{k}-\tilde{\eta}_{k})\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}$ (E.50) $\displaystyle\equiv Z_{5a}+Z_{5b}+Z_{5c}.$ (E.51)

from (Jin et al., 2021c, Supplement, pg. 70). We further decompose $Z_{5a}$ as
in (Jin et al., 2021c, Supplement, pg.70):

$Z_{5a}=\frac{2}{v}\sum_{j,k(dist)}\alpha_{jk}W_{jk}^{2}+\frac{2}{v}\sum_{\begin{subarray}{c}j,k(dist)\\\
s\neq j,t\neq k,\\\
(s,t)\neq(k,j)\end{subarray}}\alpha_{jk}W_{js}W_{kt}\equiv\widetilde{Z}_{5a}+Z^{*}_{5a}.$

where
$\alpha_{jk}=\sum_{i,\ell(dist)\notin\\{j,k\\}}\eta_{i}\eta_{j}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}$. Note that by (E.20) and (E.24),

$\displaystyle|\alpha_{jk}|\lesssim\sum_{i\ell}(\beta_{k}\theta_{k})(\beta_{\ell}\theta_{\ell})^{2}(\beta_{i}\theta_{i})\lesssim\theta_{j}(\beta_{k}\theta_{k})\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}.$

Only $\tilde{Z}_{5a}$ has nonzero mean. By (E.1) and (E.2),

$\displaystyle|\mathbb{E}Z_{5a}|=|\mathbb{E}\tilde{Z}_{5a}|\lesssim\frac{1}{\|\theta\|_{1}^{2}}\sum_{jk}\theta_{j}(\beta_{k}\theta_{k})\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}\cdot\theta_{j}\theta_{k}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

Now we study the variance of $Z_{5a}$. In (Jin et al., 2021c, Supplement,
pg.70) it is shown that

$\displaystyle\mathrm{Var}(\widetilde{Z}_{5a})$
$\displaystyle\lesssim\frac{1}{v^{2}}\sum_{j,k(dist)}\alpha_{jk}^{2}\,\mathrm{Var}(W^{2}_{jk})$
$\displaystyle\mathrm{Var}(Z^{*}_{5a})$
$\displaystyle\lesssim\frac{1}{v^{2}}\sum_{\begin{subarray}{c}j,k(dist)\\\
s\neq j,t\neq k,\\\
(s,t)\neq(k,j)\end{subarray}}\alpha^{2}_{jk}\,\mathrm{Var}(W_{js}W_{kt}).$

Thus by (E.2) and (E.24),

$\displaystyle\mathrm{Var}(\widetilde{Z}_{5a})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{6}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\big{(}\sum_{jk}\theta_{j}^{3}\beta_{k}^{2}\theta_{k}^{3}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{4}}$
$\displaystyle\mathrm{Var}(Z^{*}_{5a})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{6}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\big{(}\sum_{jk}\theta_{j}^{2}\beta_{k}^{2}\theta_{k}^{2}\cdot\theta_{j}\theta_{s}\theta_{k}\theta_{t}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

We conclude that

$\displaystyle\mathrm{Var}(Z_{5a})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

Next we study $Z_{5b}$ using the decomposition

$Z_{5b}=\frac{1}{v}\sum_{j,s(dist)}\alpha_{j}W^{2}_{js}+\frac{1}{v}\sum_{\begin{subarray}{c}j\\\
s,t(dist)\notin\\{j\\}\end{subarray}}\alpha_{j}W_{js}W_{jt}\equiv\widetilde{Z}_{5b}+Z^{*}_{5b}.$

from (Jin et al., 2021c, Supplement, pg.71), where
$\alpha_{j}=\sum_{i,k,\ell(dist)\notin\\{j\\}}\eta_{i}\eta_{k}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}$. Note that by (E.2) and (E.20),

$\displaystyle|\alpha_{j}|\lesssim\sum_{ik\ell}\theta_{i}\theta_{k}(\beta_{k}\theta_{k})(\beta_{\ell}\theta_{\ell})^{2}(\beta_{i}\theta_{i})\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}.$

Only $\widetilde{Z}_{5b}$ above has nonzero mean, and we have

$\displaystyle|\mathbb{E}Z_{5b}|=|\mathbb{E}Z_{5b}|\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}}{\|\theta\|_{1}^{2}}\sum_{j,s}\theta_{j}\theta_{s}\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}.$

Similarly for the variances,

$\displaystyle\mathrm{Var}(\tilde{Z}_{5b})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\sum_{js}\theta_{j}\theta_{s}\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}$
$\displaystyle\mathrm{Var}(Z_{5b}^{*})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\sum_{jst}\theta_{j}^{2}\theta_{s}\theta_{t}\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}},$

and it follows that

$\displaystyle\mathrm{Var}(Z_{5b})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

Next we study

$\displaystyle Z_{5c}$ $\displaystyle=\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{j}-\tilde{\eta}_{j})\eta^{2}_{i}(\eta_{k}-\tilde{\eta}_{k})\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
j}=\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{i}^{2}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
j})(\eta_{j}-\tilde{\eta}_{j})(\eta_{k}-\tilde{\eta}_{k})$
$\displaystyle=\frac{1}{v}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\ s\neq
j,t\neq
k\end{subarray}}(\eta_{i}^{2}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
j})W_{js}W_{kt}=\frac{1}{v}\sum_{\begin{subarray}{c}j,k(dist)\\\ s\neq j,t\neq
k\end{subarray}}\alpha_{jk}W_{js}W_{kt}$

where $\alpha_{jk}=\sum_{\begin{subarray}{c}i,\ell(dist)\\\
i,\ell\notin\\{j,k\\}\end{subarray}}\eta_{i}^{2}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
j}$. Note that by (E.20) and (E.18) ,

$\displaystyle|\alpha_{jk}|\lesssim\sum_{i\ell}\theta_{i}^{2}(\beta_{k}\theta_{k})(\beta_{\ell}\theta_{\ell})^{2}(\beta_{j}\theta_{j})\lesssim(\beta_{j}\theta_{j})(\beta_{k}\theta_{k})\|\theta\|_{2}^{2}\|\beta\circ\theta\|_{2}^{2}.$
(E.52)

We further decompose

$\displaystyle Z_{5c}$
$\displaystyle=\frac{1}{v}\sum_{\begin{subarray}{c}j,k\\\
(dist)\end{subarray}}\alpha_{jk}W_{jk}^{2}+\frac{1}{v}\sum_{\begin{subarray}{c}j,k(dist)\\\
s,t\notin\\{j,k\\}\end{subarray}}\alpha_{jk}W_{js}W_{kt}\equiv\tilde{Z}_{5c}+Z_{5c}^{*}.$

Only the first term has nonzero mean. It follows that

$\displaystyle|\mathbb{E}Z_{5c}|=|\mathbb{E}\tilde{Z}_{5c}|$
$\displaystyle\lesssim\frac{\|\theta\|_{2}^{2}\|\beta\circ\theta\|_{2}^{2}}{\|\theta\|_{1}^{2}}\sum_{j,k,s,t}(\beta_{j}\theta_{j})(\beta_{k}\theta_{k})\cdot\theta_{j}\theta_{k}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

Note that $Z_{5c}$ and $Z_{5a}$ have the same form, but with a different
setting of the coefficient $\alpha_{jk}$. Mimicking the variance bounds for
$Z_{5a}$ we obtain the bound

$\displaystyle\mathrm{Var}(Z_{5c})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

Combining the previous bounds we obtain

$\displaystyle|\mathbb{E}Z_{5}|\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2},\quad\mathrm{Var}(Z_{5})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

Next we study $Z_{6}=Z_{6a}+Z_{6b}$ as defined in (Jin et al., 2021c,
Supplement, pg.72), where

$\displaystyle Z_{6a}$ $\displaystyle=\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{i}\eta_{\ell}\widetilde{\Omega}_{j\ell}\widetilde{\Omega}_{ki})(\eta_{j}-\tilde{\eta}_{j})(\eta_{k}-\tilde{\eta}_{k})=\frac{1}{v}\sum_{\begin{subarray}{c}j,k(dist)\\\
s\neq j,t\neq k\end{subarray}}\alpha_{jk}^{(6a)}W_{js}W_{kt}$ $\displaystyle
Z_{6b}$ $\displaystyle=2\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{i}\eta_{\ell}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{\ell
i})(\eta_{j}-\tilde{\eta}_{j})(\eta_{k}-\tilde{\eta}_{k})=\frac{1}{v}\sum_{\begin{subarray}{c}j,k(dist)\\\
s\neq j,t\neq k\end{subarray}}\alpha_{jk}^{(6b)}W_{js}W_{kt}$

and

$\displaystyle\alpha_{jk}^{(6a)}$
$\displaystyle=\sum_{\begin{subarray}{c}i,\ell(dist)\\\
i,\ell\notin\\{j,k\\}\end{subarray}}\eta_{i}\eta_{\ell}\tilde{\Omega}_{jk}\tilde{\Omega}_{\ell
i}$ $\displaystyle\alpha_{jk}^{(6b)}$
$\displaystyle=\sum_{\begin{subarray}{c}i,\ell(dist)\\\
i,\ell\notin\\{j,k\\}\end{subarray}}\eta_{i}\eta_{\ell}\tilde{\Omega}_{j\ell}\tilde{\Omega}_{ki}.$

Thus $Z_{6a}$ and $Z_{6b}$ take the same form as $Z_{5c}$, but with a
different setting of $\alpha_{jk}$. Note that by (E.24) and similar arguments
from before,

$\displaystyle\max(|\alpha_{jk}^{(6a)}|,|\alpha_{jk}^{(6b)}|)\lesssim(\beta_{j}\theta_{j})(\beta_{k}\theta_{k})\|\theta\|_{2}^{2}\|\beta\circ\theta\|_{2}^{2},$

which is the same as the upper bound on $|\alpha_{jk}|$ associated to $Z_{5c}$
given in (E.52). It follows that

$\displaystyle|\mathbb{E}Z_{6}|\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}},\quad\mathrm{Var}(Z_{6})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

We have proved all claims in Lemma E.9. ∎

#####  E.4.5 Proof of Lemma E.10

The terms $T_{1}$ and $F$ do not depend on $\tilde{\Omega}$, and thus the
claimed bounds transfer directly from (Jin et al., 2021c, Lemma G.9). Thus we
focus on $T_{2}$. We use the decomposition
$T_{2}=2(T_{2a}+T_{2b}+T_{2c}+T_{2d})$ from (Jin et al., 2021c, Supplement,
pg.73) where

$\displaystyle T_{2a}$
$\displaystyle=\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}\big{[}(\eta_{i_{1}}-\tilde{\eta}_{i_{1}})(\eta_{i_{2}}-\tilde{\eta}_{i_{2}})(\eta_{i_{3}}-\tilde{\eta}_{i_{3}})\big{]}\cdot\widetilde{\Omega}_{i_{4}i_{1}},$
$\displaystyle T_{2b}$
$\displaystyle=\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\eta_{i_{2}}\eta_{i_{3}}^{2}\big{[}(\eta_{i_{1}}-\tilde{\eta}_{i_{1}})(\eta_{i_{2}}-\tilde{\eta}_{i_{2}})(\eta_{i_{4}}-\tilde{\eta}_{i_{4}})\big{]}\cdot\widetilde{\Omega}_{i_{4}i_{1}},$
$\displaystyle T_{2c}$
$\displaystyle=\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}\big{[}(\eta_{i_{2}}-\tilde{\eta}_{i_{2}})^{2}(\eta_{i_{3}}-\tilde{\eta}_{i_{3}})\big{]}\cdot\widetilde{\Omega}_{i_{4}i_{1}},$
$\displaystyle T_{2d}$
$\displaystyle=\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\eta_{i_{1}}\eta_{i_{3}}^{2}\big{[}(\eta_{i_{2}}-\tilde{\eta}_{i_{2}})^{2}(\eta_{i_{4}}-\tilde{\eta}_{i_{4}})\big{]}\cdot\widetilde{\Omega}_{i_{4}i_{1}}.$

We study each term separately.

For $T_{2a}$, in (Jin et al., 2021c, Supplement, pg.89), we have the
decomposition $T_{2a}=X_{a1}+X_{a2}+X_{a3}+X_{b}$ where

$\displaystyle X_{a1}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{j_{3}\neq
i_{3}}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}W^{2}_{i_{1}i_{2}}W_{i_{3}j_{3}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle X_{a2}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{j_{2}\neq
i_{2}}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}W^{2}_{i_{1}i_{3}}W_{i_{2}j_{2}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle X_{a3}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{j_{1}\neq
i_{1}}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}W^{2}_{i_{2}i_{3}}W_{i_{1}j_{1}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle X_{b}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\begin{subarray}{c}j_{1},j_{2},j_{3}\\\
j_{k}\neq
i_{\ell},k,\ell=1,2,3\end{subarray}}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}W_{i_{1}j_{1}}W_{i_{2}j_{2}}W_{i_{3}j_{3}}\widetilde{\Omega}_{i_{1}i_{4}}.$

There it is shown that $\mathbb{E}T_{2a}=0$. Further it is argued that

$\displaystyle\mathrm{Var}(X_{a1})$ $\displaystyle=\mathbb{E}X_{a1}^{2}$
$\displaystyle=\frac{1}{v^{3}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}(dist)\\\
i_{1}^{\prime},i_{2}^{\prime},i_{3}^{\prime},i_{4}^{\prime}(dist)\end{subarray}}\sum_{\begin{subarray}{c}j_{3},j_{3}^{\prime}\\\
j_{3}\neq i_{3},j_{3}^{\prime}\neq
i_{3}^{\prime}\end{subarray}}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}\eta_{i_{2}^{\prime}}\eta_{i_{3}^{\prime}}\eta_{i_{4}^{\prime}}\mathbb{E}[W^{2}_{i_{1}i_{2}}W_{i_{3}j_{3}}W^{2}_{i_{1}^{\prime}i_{2}^{\prime}}W_{i_{3}^{\prime}j_{3}^{\prime}}]\widetilde{\Omega}_{i_{1}i_{4}}\widetilde{\Omega}_{i_{1}^{\prime}i_{4}^{\prime}}$
(E.53) $\displaystyle\equiv V_{A}+V_{B}+V_{C},$

where the terms $V_{A},V_{B},V_{C}$ correspond to the contributions from cases
$A,B,C$, respectively, described in (Jin et al., 2021c, Supplement, pg.89).
Concretely, the nonzero terms of (E.53) fall into three cases:

  * Case A.

$\\{i_{1},i_{2}\\}=\\{i_{3}^{\prime},j_{3}^{\prime}\\}$ and
$\\{i_{3},j_{3}\\}=\\{i_{1}^{\prime},i_{2}^{\prime}\\}$

  * Case B.

$\\{i_{3},j_{3}\\}=\\{i_{3}^{\prime},j_{3}^{\prime}\\}$ and
$\\{i_{1},i_{2}\\}=\\{i_{1}^{\prime},i_{2}^{\prime}\\}$

  * Case C.

$\\{i_{3},j_{3}\\}=\\{i_{3}^{\prime},j_{3}^{\prime}\\}$ and
$\\{i_{1},i_{2}\\}\neq\\{i_{1}^{\prime},i_{2}^{\prime}\\}$.

Here $V_{A},V_{B},$ and $V_{C}$ are defined to be the contributions from each
case.

Applying (E.2), (E.22), and (E.20),

$\displaystyle|\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}\eta_{i_{2}^{\prime}}\eta_{i_{3}^{\prime}}\eta_{i_{4}^{\prime}}\widetilde{\Omega}_{i_{1}i_{4}}\widetilde{\Omega}_{i_{1}^{\prime}i_{4}^{\prime}}|$
$\displaystyle\lesssim\theta_{i_{2}}\theta_{i_{3}}\theta_{i_{4}}\theta_{i_{2}^{\prime}}\theta_{i_{3}^{\prime}}\theta_{i_{4}^{\prime}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})(\beta_{i_{1}^{\prime}}\theta_{i_{1}^{\prime}})(\beta_{i_{4}^{\prime}}\theta_{i_{4}^{\prime}})$
$\displaystyle\lesssim\theta_{i_{2}}\theta_{i_{3}}\theta_{i_{4}}\theta_{i_{2}^{\prime}}\theta_{i_{3}^{\prime}}\theta_{i_{4}^{\prime}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\theta_{i_{1}^{\prime}}(\beta_{i_{4}^{\prime}}\theta_{i_{4}^{\prime}}).$
(E.54)

Note that using the last inequality reduces the required casework while still
yielding a good enough bound. Mimicking the casework in Case A of (Jin et al.,
2021c, Supplement, pg.90) and applying (E.24), we have

$\displaystyle V_{A}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3}\\\
i_{4},i_{4}^{\prime},j_{3}\end{subarray}}\,\sum_{\begin{subarray}{c}b_{1},b_{2}\\\
(b_{1}+b_{2}=1)\end{subarray}}\beta_{i_{1}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{2+b_{1}}\theta_{i_{2}}^{2+b_{2}}\theta_{i_{3}}^{3}\theta_{j_{3}}^{2}\theta_{i_{4}}^{2}\theta_{i_{4}^{\prime}}^{2}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\big{(}\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}^{3}\|\theta\|_{2}^{4}\|\theta\|_{3}^{3}+\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}^{3}\|\theta\|_{2}^{2}\|\theta\|_{3}^{6}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}^{9}}{\|\theta\|_{1}^{6}}.$

Similarly, applying (E.54) along with (E.22), (E.20), and (E.24) yields

$\displaystyle V_{B}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3}\\\
i_{4},i_{4}^{\prime},j_{3}\end{subarray}}\,\sum_{\begin{subarray}{c}c_{1},c_{2}\\\
(c_{1}+c_{2}=1)\end{subarray}}\beta_{i_{1}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{3}\theta_{i_{2}}^{3}\theta_{i_{3}}^{2+c_{1}}\theta_{j_{3}}^{1+c_{2}}\theta_{i_{2}}^{2}\theta_{i_{4}^{\prime}}^{2}\lesssim\frac{\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}^{7}}{\|\theta\|_{1}^{5}}.$

and

$\displaystyle V_{C}$
$\displaystyle\lesssim\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\\\
i_{1}^{\prime},i_{2}^{\prime},i_{4}^{\prime},j_{3}\end{subarray}}\,\sum_{\begin{subarray}{c}c_{1},c_{2}\\\
(c_{1}+c_{2}=1)\end{subarray}}\beta_{i_{1}}\beta_{i_{4}}\beta_{i_{1}^{\prime}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{2}\theta_{i_{2}}^{2}\theta_{i_{3}}^{2+c_{1}}\theta_{j_{3}}^{1+c_{2}}\theta_{i_{4}}^{2}\theta_{i_{1}^{\prime}}^{2}\theta_{i_{2}^{\prime}}^{2}\theta_{i_{4}^{\prime}}^{2}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{10}}{\|\theta\|_{1}^{5}}.$

Thus

$\displaystyle\mathrm{Var}(X_{a1})\lesssim\|\beta\circ\theta\|_{2}^{4}.$

The arguments for $X_{a2}$ and $X_{a3}$ are similar, and the corresponding
$V_{A},V_{B},V_{C}$ satisfy the same inequalities above. We simply state the
bounds:

$\displaystyle\mathbb{E}X_{a_{2}}$
$\displaystyle=\mathbb{E}X_{a3}=0,\quad\mathrm{Var}(X_{a2})\lesssim\|\beta\circ\theta\|_{2}^{4},\quad\mathrm{Var}(X_{a3})\lesssim\|\beta\circ\theta\|_{2}^{4}.$

Next we consider $X_{b}$ as defined in (Jin et al., 2021c, Supplement, pg.89).
We have $\mathbb{E}X_{b}=0$ and focus on the variance. In (Jin et al., 2021c,
Supplement, pg.91) it is shown that

$\displaystyle\mathrm{Var}(X_{b})$ $\displaystyle=\mathbb{E}[X_{b}^{2}]$
$\displaystyle=v^{-3}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}(dist)\\\
i_{1}^{\prime},i_{2}^{\prime},i_{3}^{\prime},i_{4}^{\prime}(dist)\end{subarray}}\sum_{\begin{subarray}{c}j_{3},j_{3}^{\prime}\\\
j_{3}\neq i_{3},j_{3}^{\prime}\neq
i_{3}^{\prime}\end{subarray}}\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}\eta_{i_{2}^{\prime}}\eta_{i_{3}^{\prime}}\eta_{i_{4}^{\prime}}\mathbb{E}[W_{i_{1}j_{1}}W_{i_{2}j_{2}}W_{i_{3}j_{3}}W_{i_{1}^{\prime}j_{1}^{\prime}}W_{i_{2}^{\prime}j_{2}^{\prime}}W_{i_{3}^{\prime}j_{3}^{\prime}}]\widetilde{\Omega}_{i_{1}i_{4}}\widetilde{\Omega}_{i_{1}^{\prime}i_{4}^{\prime}},$

Note that

$\displaystyle\mathbb{E}[W_{i_{1}j_{1}}W_{i_{2}j_{2}}W_{i_{3}j_{3}}W_{i_{1}^{\prime}j_{1}^{\prime}}W_{i_{2}^{\prime}j_{2}^{\prime}}W_{i_{3}^{\prime}j_{3}^{\prime}}]\neq
0$

if and only if the two sets of random variables
$\\{W_{i_{1}j_{1}},W_{i_{2}j_{2}},W_{i_{3}j_{3}}\\}$ and
$\\{W_{i_{1}^{\prime}j_{1}^{\prime}},W_{i_{2}^{\prime}j_{2}^{\prime}},W_{i_{3}^{\prime}j_{3}^{\prime}}\\}$
are identical. Applying (E.22) and (E.20),

$\displaystyle|\eta_{i_{2}}\eta_{i_{3}}\eta_{i_{4}}\eta_{i_{2}^{\prime}}\eta_{i_{3}^{\prime}}\eta_{i_{4}^{\prime}}\widetilde{\Omega}_{i_{1}i_{4}}\widetilde{\Omega}_{i_{1}^{\prime}i_{4}^{\prime}}|$
$\displaystyle\lesssim\theta_{i_{2}}\theta_{i_{3}}\theta_{i_{4}}\theta_{i_{2}^{\prime}}\theta_{i_{3}^{\prime}}\theta_{i_{4}^{\prime}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\theta_{i_{1}^{\prime}}(\beta_{i_{4}^{\prime}}\theta_{i_{4}^{\prime}})$
$\displaystyle\lesssim\beta_{i_{1}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{1+a_{1}}\theta_{j_{1}}^{a_{2}}\theta_{i_{2}}^{1+a_{3}}\theta_{j_{2}}^{a_{4}}\theta_{i_{3}}^{1+a_{5}}\theta_{j_{3}}^{a_{6}}\theta_{i_{4}}^{2}\theta_{i_{4}^{\prime}}^{2}$

if
$\mathbb{E}[W_{i_{1}j_{1}}W_{i_{2}j_{2}}W_{i_{3}j_{3}}W_{i_{1}^{\prime}j_{1}^{\prime}}W_{i_{2}^{\prime}j_{2}^{\prime}}W_{i_{3}^{\prime}j_{3}^{\prime}}]\neq
0$, where $a_{i}\in\\{0,1\\}$ and $\sum_{i=1}^{6}a_{i}=3$. Thus by (E.1),
(E.2), and (E.24),

$\displaystyle\mathrm{Var}(X_{b})$
$\displaystyle\lesssim\max_{a}\frac{1}{\|\theta\|_{1}^{6}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\\\
i_{4}^{\prime},j_{1},j_{2},j_{3}\end{subarray}}\beta_{i_{1}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{2+a_{1}}\theta_{j_{1}}^{1+a_{2}}\theta_{i_{2}}^{2+a_{3}}\theta_{j_{2}}^{1+a_{4}}\theta_{i_{3}}^{2+a_{5}}\theta_{j_{3}}^{1+a_{6}}\theta_{i_{4}}^{2}\theta_{i_{4}^{\prime}}^{2}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\\\
i_{4}^{\prime},j_{1},j_{2},j_{3}\end{subarray}}\beta_{i_{1}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{2}\theta_{j_{1}}^{1}\theta_{i_{2}}^{2}\theta_{j_{2}}^{1}\theta_{i_{3}}^{2}\theta_{j_{3}}^{1}\theta_{i_{4}}^{2}\theta_{i_{4}^{\prime}}^{2}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}^{3}\|\theta\|_{2}^{4}\|\theta\|_{1}^{3}}{\|\theta\|_{1}^{6}}\lesssim\frac{\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}^{7}}{\|\theta\|_{1}^{3}}\lesssim\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}.$

Combining the results for $X_{a1},X_{a2},X_{a3}$ and $X_{b}$, we conclude that

$\displaystyle\mathbb{E}T_{2a}=0,\qquad\mathrm{Var}(T_{2a})\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}.$

The argument for $T_{2b}$ is similar to the one for $T_{2a}$, so we simply
state the results:

$\displaystyle\mathbb{E}T_{2b}=0,\qquad\mathrm{Var}(T_{2b})\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}.$

Next we study $T_{2c}$, providing full details for completeness. Using the
definition of $T_{2c}$ in (Jin et al., 2021c, Supplement, pg.92), we have the
following decomposition by careful casework.

$\displaystyle Y_{a}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}W^{3}_{i_{2}i_{3}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle Y_{b1}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\begin{subarray}{c}(i_{2},j_{2})\neq(j_{3},i_{3})\\\
j_{2}\neq i_{2},j_{3}\neq
i_{3}\end{subarray}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}W^{2}_{i_{2}j_{2}}W_{i_{3}j_{3}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle Y_{b2}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\ell_{2}\notin\\{i_{3},i_{2}\\}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}W^{2}_{i_{2}i_{3}}W_{i_{2}\ell_{2}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle Y_{b3}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{j_{2}\notin\\{i_{3},i_{2}\\}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}W^{2}_{i_{2}i_{3}}W_{i_{2}j_{2}}\widetilde{\Omega}_{i_{1}i_{4}},$
$\displaystyle Y_{c}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\begin{subarray}{c}j_{2},\ell_{2},j_{3}\\\
j_{2}\neq i_{2},\ell_{2}\neq i_{2},j_{3}\neq i_{3}\\\
j_{2}\neq\ell_{2},(i_{2},j_{2})\neq(j_{3},i_{3}),(i_{2},\ell_{2})\neq(j_{3},i_{3})\end{subarray}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}W_{i_{2}j_{2}}W_{i_{2}\ell_{2}}W_{i_{3}j_{3}}\widetilde{\Omega}_{i_{1}i_{4}}.$

Note that, by the change of variables $\ell_{2}\to j_{2}$, it holds that
$Y_{b2}=Y_{b3}$.

The only term with nonzero mean is $Y_{a}$. We have by (E.18), (E.20), (E.22),
and (E.24) that

$\displaystyle|\mathbb{E}Y_{a}|$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{3}}\sum_{i_{1},i_{2},i_{3},i_{4}}\theta_{i_{1}}\theta_{i_{3}}\theta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\cdot|\mathbb{E}W_{i_{2}i_{3}}^{3}|\lesssim\frac{1}{\|\theta\|_{1}^{3}}\sum_{i_{1},i_{2},i_{3},i_{4}}\beta_{i_{1}}\beta_{i_{4}}\theta_{i_{1}}^{2}\theta_{i_{2}}\theta_{i_{3}}^{2}\theta_{i_{4}}^{2}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

For the variance, by independence of $\\{W_{ij}\\}_{i>j}$, (E.2), (E.20), and
(E.24), we have

$\displaystyle\mathrm{Var}(Y_{a})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2},i_{3}}\big{(}\sum_{i_{1},i_{4}}\theta_{i_{1}}\theta_{i_{3}}\theta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\big{)}^{2}\theta_{i_{2}}\theta_{i_{3}}\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2},i_{3}}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i_{2}}\theta_{i_{3}}^{2}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{5}}.$

For $Y_{b1},Y_{b2},Y_{b3}$ we make note of the identity

$\displaystyle W_{ij}^{2}$
$\displaystyle=(1-2\Omega_{ij})W_{ij}+\Omega_{ij}(1-\Omega_{ij})\equiv
A_{ij}W_{ij}+B_{ij}.$ (E.55)

Write

$\displaystyle Y_{b1}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\begin{subarray}{c}(i_{2},j_{2})\neq(j_{3},i_{3})\\\
j_{2}\neq i_{2},j_{3}\neq
i_{3}\end{subarray}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}A_{i_{2}j_{2}}W_{i_{2}j_{2}}W_{i_{3}j_{3}}\widetilde{\Omega}_{i_{1}i_{4}}$
$\displaystyle\quad-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\begin{subarray}{c}(i_{2},j_{2})\neq(j_{3},i_{3})\\\
j_{2}\neq i_{2},j_{3}\neq
i_{3}\end{subarray}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}B_{i_{2}j_{2}}W_{i_{3}j_{3}}\widetilde{\Omega}_{i_{1}i_{4}}\equiv
Y_{b1,A}+Y_{b1,B}.$

By similar arguments from before, and noting that $|A_{i_{2},j_{2}}|\lesssim
1$,

$\displaystyle\mathrm{Var}(Y_{b1,A})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{\begin{subarray}{c}(i_{2},j_{2})\neq(j_{3},i_{3})\\\
j_{2}\neq i_{2},j_{3}\neq
i_{3}\end{subarray}}\bigg{(}\sum_{i_{1},i_{4}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\bigg{)}^{2}|\mathbb{E}W_{i_{2}j_{2}}W_{i_{3}j_{3}}|$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2},j_{2},i_{3},j_{3}}\bigg{(}\sum_{i_{1},i_{4}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\bigg{)}^{2}\cdot\theta_{i_{2}}\theta_{j_{2}}\theta_{i_{3}}\theta_{j_{3}}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2},j_{2},i_{3},j_{3}}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i_{2}}\theta_{j_{2}}\theta_{i_{3}}^{3}\theta_{j_{3}}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{3}}.$

Similarly, using $|B_{ij}|\lesssim\Omega_{ij}\lesssim\theta_{i}\theta_{j}$,

$\displaystyle\mathrm{Var}(Y_{b1,B})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{3},j_{3}(dist)}\bigg{(}\sum_{i_{1},i_{2},i_{4},j_{2}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}\theta_{i_{2}}\theta_{j_{2}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\bigg{)}^{2}\cdot|\mathbb{E}W_{i_{3},j_{3}}|$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{3},j_{3}}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\|\theta\|_{1}^{2}\theta_{i_{3}}^{3}\theta_{j_{3}}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{3}}.$

It follows that

$\displaystyle\mathrm{Var}(Y_{b1})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{3}}$

To control $\mathrm{Var}(Y_{b2})$, again we invoke the identity (E.55) to
write

$\displaystyle Y_{b2}$
$\displaystyle=-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\ell_{2}\notin\\{i_{3},i_{2}\\}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}A_{i_{2}i_{3}}W_{i_{2}i_{3}}W_{i_{2}\ell_{2}}\widetilde{\Omega}_{i_{1}i_{4}}$
$\displaystyle\quad-\frac{1}{v^{3/2}}\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\sum_{\ell_{2}\notin\\{i_{3},i_{2}\\}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}B_{i_{2}i_{3}}W_{i_{2}\ell_{2}}\widetilde{\Omega}_{i_{1}i_{4}}\equiv
Y_{b2,A}+Y_{b2,B}.$

Using similar arguments from before, we have

$\displaystyle\mathrm{Var}(Y_{b2,A})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2}i_{3}\ell_{2}}\bigg{(}\sum_{i_{1}i_{4}}\theta_{i_{1}}\theta_{i_{3}}\theta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\bigg{)}^{2}\theta_{i_{2}}^{2}\theta_{i_{3}}\theta_{\ell_{2}}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2}i_{3}\ell_{2}}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\theta_{i_{2}}^{2}\theta_{i_{3}}^{3}\theta_{\ell_{2}}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{5}}.$

Furthermore,

$\displaystyle\mathrm{Var}(Y_{b2,B})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2},\ell_{2}}\bigg{(}\sum_{i_{1},i_{3},i_{4}}\theta_{i_{1}}\theta_{i_{3}}\theta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\theta_{i_{2}}\theta_{i_{3}}\bigg{)}^{2}\theta_{i_{2}}\theta_{\ell_{2}}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{6}}\sum_{i_{2},\ell_{2}}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}\theta_{i_{2}}^{3}\theta_{\ell_{2}}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{10}}{\|\theta\|_{1}^{5}}.$

Since $Y_{b2}=Y_{b3}$, we have

$\displaystyle\mathrm{Var}(Y_{b2})=\mathrm{Var}(Y_{b3})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{10}}{\|\theta\|_{1}^{5}}.$

Next we study the variance of $Y_{2c}$. For notational brevity, let

$\displaystyle\mathcal{R}_{i_{1},i_{2},i_{3}}=\bigg{\\{}(j_{2},\ell_{2},j_{3})\bigg{|}j_{2}\neq
i_{2},\ell_{2}\neq i_{2},j_{3}\neq
i_{3}j_{2}\neq\ell_{2},(i_{2},j_{2})\neq(j_{3},i_{3}),(i_{2},\ell_{2})\neq(j_{3},i_{3})\bigg{\\}}.$

We have

$\displaystyle\mathrm{Var}(Y_{c})$
$\displaystyle=\frac{1}{v^{3}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}(dist)\\\
i_{1}^{\prime},i_{2}^{\prime},i_{3}^{\prime},i_{4}^{\prime}(dist)\end{subarray}}\,\,\sum_{\begin{subarray}{c}(j_{2},\ell_{2},j_{3})\in\mathcal{R}_{i_{1},i_{2},i_{3}}\\\
(j_{2}^{\prime},\ell_{2}^{\prime},j_{3}^{\prime})\in\mathcal{R}_{i_{1}^{\prime},i_{2}^{\prime},i_{3}^{\prime}}\end{subarray}}\eta_{i_{1}}\eta_{i_{3}}\eta_{i_{4}}\widetilde{\Omega}_{i_{1}i_{4}}\eta_{i_{1}^{\prime}}\eta_{i_{3}^{\prime}}\eta_{i_{4}^{\prime}}\widetilde{\Omega}_{i_{1}^{\prime}i_{4}^{\prime}}\mathbb{E}\big{[}W_{i_{2}j_{2}}W_{i_{2}\ell_{2}}W_{i_{3}j_{3}}W_{i_{2}^{\prime}j_{2}^{\prime}}W_{i_{2}^{\prime}\ell_{2}^{\prime}}W_{i_{3}^{\prime}j_{3}^{\prime}}\big{]}$
(E.56)

Note that $W_{i_{2}j_{2}}W_{i_{2}\ell_{2}}W_{i_{3}j_{3}}$ and
$W_{i_{2}^{\prime}j_{2}^{\prime}}W_{i_{2}^{\prime}\ell_{2}^{\prime}}W_{i_{3}^{\prime}j_{3}^{\prime}}$
above are uncorrelated unless

$\bigg{\\{}\\{i_{2},j_{2}\\},\\{i_{2},\ell_{2}\\},\\{i_{3},j_{3}\\}\bigg{\\}}=\bigg{\\{}\\{i_{2}^{\prime},j_{2}^{\prime}\\},\\{i_{2}^{\prime},\ell_{2}^{\prime}\\},\\{i_{3}^{\prime},j_{3}^{\prime}\\}\bigg{\\}}.$

In particular, $i_{3}^{\prime}\in\\{i_{2},j_{2},\ell_{2},i_{3},j_{3}\\}$ when
the above holds. Hence for some choice of $a_{i}\in\\{0,1\\}$ with
$\sum_{i=1}^{5}a_{i}=1$,

$\displaystyle\mathrm{Var}(Y_{c})$
$\displaystyle\lesssim\frac{1}{v^{3}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\\\
i_{1}^{\prime},i_{4}^{\prime},j_{2},\ell_{2},j_{3}\end{subarray}}\theta_{i_{2}}^{a_{1}}\theta_{j_{2}}^{a_{2}}\theta_{\ell_{2}}^{a_{3}}\theta_{i_{3}}^{a_{4}}\theta_{j_{3}}^{a_{5}}\cdot\theta_{i_{1}}\theta_{i_{3}}\theta_{i_{4}}(\beta_{i_{1}}\theta_{i_{1}})(\beta_{i_{4}}\theta_{i_{4}})\theta_{i_{1}^{\prime}}\theta_{i^{\prime}_{4}}(\beta_{i_{1}^{\prime}}\theta_{i_{1}^{\prime}})(\beta_{i_{4}^{\prime}}\theta_{i_{4}^{\prime}})\cdot\theta_{i_{2}}^{2}\theta_{j_{2}}\theta_{\ell_{2}}\theta_{i_{3}}\theta_{j_{3}}$
$\displaystyle\lesssim\frac{1}{v^{3}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\\\
i_{1}^{\prime},i_{4}^{\prime},j_{2},\ell_{2},j_{3}\end{subarray}}\beta_{i_{1}}\beta_{i_{1}^{\prime}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{2}\theta_{i_{2}}^{2+a_{1}}\theta_{i_{3}}^{2+a_{4}}\theta_{i_{4}}^{2}\theta_{i_{1}^{\prime}}^{2}\theta_{i_{4}^{\prime}}^{2}\theta_{j_{2}}^{1+a_{2}}\theta_{\ell_{2}}^{1+a_{3}}\theta_{j_{3}}^{1+a_{5}}$
$\displaystyle\lesssim\frac{1}{v^{3}}\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}\\\
i_{1}^{\prime},i_{4}^{\prime},j_{2},\ell_{2},j_{3}\end{subarray}}\beta_{i_{1}}\beta_{i_{1}^{\prime}}\beta_{i_{4}}\beta_{i_{4}^{\prime}}\theta_{i_{1}}^{2}\theta_{i_{2}}^{2}\theta_{i_{3}}^{2}\theta_{i_{4}}^{2}\theta_{i_{1}^{\prime}}^{2}\theta_{i_{4}^{\prime}}^{2}\theta_{j_{2}}^{1}\theta_{\ell_{2}}^{1}\theta_{j_{3}}^{1}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{3}},$

where in the last line we apply (E.2) followed by (E.24). Combining our
results above we have

$\displaystyle|\mathbb{E}T_{2c}|\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}},\qquad\mathrm{Var}(T_{2c})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

The argument for $T_{2d}$ is omitted since it is similar to the one for
$T_{2c}$ (note that the two terms have similar structure). The results are
stated below.

$\displaystyle|\mathbb{E}T_{2d}|$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}},\qquad\mathrm{Var}(T_{2d})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{3}}.$

Combining the results for $T_{2a},\ldots,T_{2d}$ yields

$\displaystyle|\mathbb{E}T_{2}|\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}},\qquad\mathrm{Var}(T_{2})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{2}},$

as desired. ∎

#####  E.4.6 Proof of Lemma E.11

As before, we only need to analyze the alternative hypothesis. In (Jin et al.,
2021c, Supplement,pg.103) it is shown that $\tilde{Q}^{*}-Q^{*}$ is a sum of
$O(1)$ terms of the form

$\displaystyle
Y=\Bigl{(}\frac{v}{V}\Bigr{)}^{N_{\tilde{r}}}\sum_{i,j,k,\ell(dist)}a_{ij}b_{jk}c_{k\ell}d_{\ell
i},$ (E.57)

where
$a,b,c,d\in\\{\widetilde{\Omega},W,\delta,-(\tilde{\eta}-\eta)(\tilde{\eta}-\eta)^{\mathsf{T}}\\}$,
and $N_{\tilde{r}}$ denotes the number of $a,b,c,d$ that are equal to
$-(\tilde{\eta}-\eta)(\tilde{\eta}-\eta)^{\mathsf{T}}$.

Similarly, let $N_{W}$ denote the number of $a,b,c,d$ that are equal to $W$,
and $N_{\tilde{\Omega}}$ and $N_{\delta}$ are similarly defined. Write

$Y=\Bigl{(}\frac{v}{V}\Bigr{)}^{m}X,\quad\quad\mbox{where}\quad
X=\sum_{i,j,k,\ell(dist)}a_{ij}b_{jk}c_{k\ell}d_{\ell i}.$ (E.58)

Note that for this proof, we do not need the explicit decomposition: we only
will use the fact that $\tilde{Q}^{*}-Q^{*}$ is a sum of $O(1)$ terms. At
times, we refer to these terms of the form $Y$ composing $\tilde{Q}^{*}-Q^{*}$
as post-expansion sums.

In Jin et al. (2021c) it is shown that $4\geq N_{\tilde{r}}\geq 1$ for every
post-expansion sum (note that the upper bound of $4$ is trivial). It turns out
that this is the only constraint on the post-expansion sums; so we need to
analyze every single possible combination of nonnegative integers
$(N_{\tilde{\Omega}},N_{W},N_{\delta},N_{\tilde{r}})$ where their sum is $4$
and $N_{\tilde{r}}\geq 1$ and then arrange
$a,b,c,d\in\\{\tilde{\Omega},W,\delta,-(\tilde{\eta}-\eta)(\tilde{\eta}-\eta)^{\mathsf{T}}\\}$
in all possible ways according to (E.57). This leads to a total of $34$
possibilities, all of which are shown in Table 1 reproduced from Jin et al.
(2021c).

Table 1: Note: This table and caption reproduced from Table G.4 of Jin et al.
(2021c).The $34$ types of the $175$ post-expansion sums for
$(\widetilde{Q}^{*}_{n}-Q_{n}^{*})$.

Notation | $\\#$ | $N_{\tilde{r}}$ | ($N_{\delta},N_{\widetilde{\Omega}},N_{W})$ | Examples | $N^{*}_{W}$
---|---|---|---|---|---
$R_{1}$ | 4 | 1 | (0, 0, 3) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}W_{jk}W_{k\ell}W_{\ell i}$ | 5
$R_{2}$ | 8 | 1 | (0, 1, 2) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}W_{k\ell}W_{\ell i}$ | 4
$R_{3}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}W_{jk}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | 4
$R_{4}$ | 8 | 1 | (0, 2, 1) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | 3
$R_{5}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}W_{k\ell}\widetilde{\Omega}_{\ell i}$ | 3
$R_{6}$ | 4 | 1 | (0, 3, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | 2
$R_{7}$ | 8 | 1 | (1, 0, 2) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}W_{k\ell}W_{\ell i}$ | 5
$R_{8}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}W_{jk}\delta_{k\ell}W_{\ell i}$ | 5
$R_{9}$ | 8 | 1 | (1, 1, 1) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | 4
$R_{10}$ | 8 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}W_{k\ell}\delta_{\ell i}$ | 4
$R_{11}$ | 8 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}W_{jk}\delta_{k\ell}\widetilde{\Omega}_{\ell i}$ | 4
$R_{12}$ | 8 | 1 | (1, 2, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | 3
$R_{13}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}\delta_{k\ell}\widetilde{\Omega}_{\ell i}$ | 3
$R_{14}$ | 8 | 1 | (2, 0, 1) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\delta_{k\ell}W_{\ell i}$ | 5
$R_{15}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}W_{k\ell}\delta_{\ell i}$ | 5
$R_{16}$ | 8 | 1 | (2, 1, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\delta_{k\ell}\widetilde{\Omega}_{\ell i}$ | 4
$R_{17}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\widetilde{\Omega}_{k\ell}\delta_{\ell i}$ | 4
$R_{18}$ | 4 | 1 | (3, 0, 0) | $\sum_{i,j,k,\ell(dist)}\widetilde{r}_{ij}\delta_{jk}\delta_{k\ell}\delta_{\ell i}$ | 5
$R_{19}$ | 4 | 2 | (0, 0, 2) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}W_{k\ell}W_{\ell i}$ | 6
$R_{20}$ | 2 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}W_{jk}\tilde{r}_{k\ell}W_{\ell i}$ | 6
$R_{21}$ | 4 | 2 | (0, 2, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | 4
$R_{22}$ | 2 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}\tilde{r}_{k\ell}\widetilde{\Omega}_{\ell i}$ | 4
$R_{23}$ | 4 | 2 | (2, 0, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\delta_{k\ell}\delta_{\ell i}$ | 6
$R_{24}$ | 2 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\tilde{r}_{k\ell}\delta_{\ell i}$ | 6
$R_{25}$ | 8 | 2 | (0, 1, 1) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | 5
$R_{26}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\widetilde{\Omega}_{jk}\tilde{r}_{k\ell}W_{\ell i}$ | 5
$R_{27}$ | 8 | 2 | (1, 1, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\delta_{k\ell}\widetilde{\Omega}_{\ell i}$ | 5
$R_{28}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\tilde{r}_{k\ell}\widetilde{\Omega}_{\ell i}$ | 5
$R_{29}$ | 8 | 2 | (1, 0, 1) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\delta_{k\ell}W_{\ell i}$ | 6
$R_{30}$ | 4 |  |  | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\delta_{jk}\tilde{r}_{k\ell}W_{\ell i}$ | 6
$R_{31}$ | 4 | 3 | (0, 0, 1) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\tilde{r}_{k\ell}W_{\ell i}$ | 7
$R_{32}$ | 4 | 3 | (0, 1, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\tilde{r}_{k\ell}\widetilde{\Omega}_{\ell i}$ | 6
$R_{33}$ | 4 | 3 | (1, 0, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\tilde{r}_{k\ell}\delta_{\ell i}$ | 7
$R_{34}$ | $1$ | 4 | (0, 0, 0) | $\sum_{i,j,k,\ell(dist)}\tilde{r}_{ij}\tilde{r}_{jk}\tilde{r}_{k\ell}\tilde{r}_{\ell i}$ | 8

In (Jin et al., 2021c, Supplement,pg.103) it is shown that

$\displaystyle|\mathbb{E}[Y-X]|$ $\displaystyle\leq
o(\|\theta\|_{2}^{-2})\sqrt{\mathbb{E}[X^{2}]}+o(1),\text{ and }$
$\displaystyle\mathrm{Var}(Y)$ $\displaystyle\leq
2\mathrm{Var}(X)+o(\|\theta\|_{2}^{-4})\mathbb{E}[X^{2}]+o(1).$ (E.59)

The proof of (E.59) in Jin et al. (2021c) only requires the heterogeneity
assumptions (E.2)–(E.4) and the following two conditions. First, we must have
the tail inequality

$\mathbb{P}(|V-v|>t)\leq\begin{cases}2\exp\bigl{(}-\frac{C_{1}}{\|\theta\|_{1}^{2}}t^{2}\bigr{)},&\mbox{when
}x_{n}\|\theta\|_{1}\leq t\leq\|\theta\|_{1}^{2},\\\
2\exp\bigl{(}-C_{2}t\bigr{)},&\mbox{when }t>\|\theta\|_{1}^{2}.\end{cases}$
(E.60)

Second, it must hold that $|Y-X|$ is dominated by a polynomial in $V$. See
(Jin et al., 2021c, Lemma G.10 and G.11) for further details. Both conditions
are satisfied in our setting, so indeed (E.59) applies.

Let $N_{W}$ and $N_{\delta}$ denote the number of $a,b,c,d$ that are equal to
$W$ and $\delta$, respectively. As in Jin et al. (2021c), we define

$\displaystyle N_{W}^{*}=N_{W}+N_{\delta}+2N_{\tilde{r}}$ (E.61)

and divide our analysis into parts based on this parameter.

###### Analysis of terms with $N^{*}_{W}\leq 4$

For convenience, we reproduce Table G.5 from Jin et al. (2021c) in Table 2.
The left column of Table 2 lists all of the terms with $N^{*}_{W}\leq 4$ ,
where note that factors of $(\frac{v}{V})^{N_{\tilde{r}}}$ are removed. In the
right column terms are listed that have similar structure to those on the
left. Precisely, a term in the left column has the form

$\displaystyle X$
$\displaystyle=\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}}c_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}},$

and its adjacent term on the right column has the form

$X^{*}=\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}}c^{*}_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}},$

analogous to $T$ and $T^{*}$ from Lemma E.13. By inspection, we see that for
each term in the left column, the canonical upper bounds
$\overline{c_{i_{1},\ldots,i_{m}}}$ and
$\overline{c^{*}_{i_{1},\ldots,i_{m}}}$ on the coefficients
$c_{i_{1},\ldots,i_{m}}$ and $c^{*}_{i_{1},\ldots,i_{m}}$ satisfy

$\overline{c_{i_{1},\ldots,i_{m}}}\lesssim\overline{c^{*}_{i_{1},\ldots,i_{m}}}.$

Recall that these canonical upper bounds were defined in Section E.4.1. Thus
the conclusion of Lemma E.13 applies, and we have for each term $X$ in the
left column of Table 2,

$\displaystyle|\mathbb{E}X|\lesssim\overline{\mathbb{E}X^{*}},\qquad\mathrm{Var}(X)\lesssim\overline{\mathrm{Var}(X^{*})}.$

Table 2:  For clarity, this table and caption are borrowed from Table G.5 of
Jin et al. (2021c).The $14$ types of post-expansion sums with $N^{*}_{W}\leq
4$. The right column displays the post-expansion sums defined before which
have similar forms as the post-expansion sums in the left column. For some
terms in the right column, we permute $(i,j,k,\ell)$ in the original
definition for ease of comparison with the left column. (In all expressions,
the subscript “$i,j,k,\ell(dist)$” is omitted.)

| Expression |  | Expression
---|---|---|---
$R_{2}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}W_{k\ell}W_{\ell i}$ | $Z_{1b}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})\eta_{j}(\tilde{\eta}_{j}-\eta_{j})\eta_{k}W_{k\ell}W_{\ell i}$
$R_{3}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})W_{jk}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | $Z_{2a}$ | $\sum\eta_{\ell}(\tilde{\eta}_{j}-\eta_{j})W_{jk}\eta_{k}(\tilde{\eta}_{i}-\eta_{i})W_{i\ell}$
$R_{4}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | $Z_{3d}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})\eta_{j}(\tilde{\eta}_{j}-\eta_{j})\eta_{k}\widetilde{\Omega}_{k\ell}W_{\ell i}$
$R_{5}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}W_{k\ell}\widetilde{\Omega}_{\ell i}$ | $Z_{4b}$ | $\sum\widetilde{\Omega}_{ij}(\tilde{\eta}_{j}-\eta_{j})\eta_{k}W_{k\ell}\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
$R_{6}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | $Z_{5a}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
$R_{9}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}W_{\ell i}$ | $T_{1d}$ | $\sum\eta_{\ell}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta^{2}_{k}(\tilde{\eta}_{i}-\eta_{i})W_{i\ell}$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\widetilde{\Omega}_{k\ell}W_{\ell i}$ | $T_{1a}$ | $\sum\eta_{\ell}(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\eta_{k}(\tilde{\eta}_{i}-\eta_{i})W_{i\ell}$
$R_{10}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})^{2}(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}W_{k\ell}\eta_{\ell}$ | $T_{1c}$ | $\sum(\tilde{\eta}_{j}-\eta_{j})\eta_{k}W_{k\ell}\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})^{2}\eta_{j}$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}W_{k\ell}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{i}$ | $T_{1a}$ | $\sum(\tilde{\eta}_{j}-\eta_{j})\eta_{k}W_{k\ell}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{i}(\tilde{\eta}_{i}-\eta_{i})\eta_{j}$
$R_{11}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})W_{jk}\eta_{k}(\tilde{\eta}_{\ell}-\eta_{\ell})\widetilde{\Omega}_{\ell i}$ | $T_{1a}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})\eta_{k}W_{kj}(\tilde{\eta}_{j}-\eta_{j})\eta_{\ell}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{i}$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})W_{jk}(\tilde{\eta}_{k}-\eta_{k})\eta_{\ell}\widetilde{\Omega}_{\ell i}$ | $T_{1b}$ | $\sum\eta_{i}(\tilde{\eta}_{k}-\eta_{k})W_{kj}(\tilde{\eta}_{j}-\eta_{j})\eta^{2}_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
$R_{12}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | $T_{2c}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | $T_{2a}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\widetilde{\Omega}_{k\ell}\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
$R_{13}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}(\tilde{\eta}_{k}-\eta_{k})\eta_{\ell}\widetilde{\Omega}_{\ell i}$ | $T_{2b}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}(\tilde{\eta}_{k}-\eta_{k})\eta_{\ell}^{2}(\tilde{\eta}_{i}-\eta_{i})$
$R_{16}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}(\tilde{\eta}_{k}-\eta_{k})\eta_{\ell}\widetilde{\Omega}_{\ell i}$ | $F_{b}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}(\tilde{\eta}_{k}-\eta_{k})\eta_{\ell}^{2}(\tilde{\eta}_{i}-\eta_{i})$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})^{2}\eta^{2}_{k}(\tilde{\eta}_{\ell}-\eta_{\ell})\widetilde{\Omega}_{\ell i}$ | $F_{b}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}^{2}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})^{2}\eta_{\ell}\widetilde{\Omega}_{\ell i}$ | $F_{b}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})^{2}\eta_{\ell}^{2}(\tilde{\eta}_{i}-\eta_{i})$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\eta_{k}(\tilde{\eta}_{\ell}-\eta_{\ell})\widetilde{\Omega}_{\ell i}$ | $F_{a}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\eta_{k}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
$R_{17}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\widetilde{\Omega}_{k\ell}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{i}$ | $F_{a}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\eta_{k}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
| $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{i}$ | $F_{b}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}^{2}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$
| $\sum(\tilde{\eta}_{i}-\eta_{i})^{2}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}\eta_{\ell}$ | $F_{c}$ | $\sum\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})^{2}\eta_{k}^{2}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{\ell}$
$R_{21}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})^{2}(\tilde{\eta}_{k}-\eta_{k})\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell i}$ | $F_{b}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})^{2}\eta_{k}(\tilde{\eta}_{k}-\eta_{k})\eta_{\ell}^{2}(\tilde{\eta}_{i}-\eta_{i})$
$R_{22}$ | $\sum(\tilde{\eta}_{i}-\eta_{i})(\tilde{\eta}_{j}-\eta_{j})\widetilde{\Omega}_{jk}(\tilde{\eta}_{k}-\eta_{k})(\tilde{\eta}_{\ell}-\eta_{\ell})\widetilde{\Omega}_{\ell i}$ | $F_{a}$ | $\sum\eta_{i}(\tilde{\eta}_{j}-\eta_{j})\eta_{j}(\tilde{\eta}_{k}-\eta_{k})\eta_{k}(\tilde{\eta}_{\ell}-\eta_{\ell})\eta_{\ell}(\tilde{\eta}_{i}-\eta_{i})$

As discussed in Section E.4.1, the upper bounds on the means and variances in
Lemmas E.7–E.10 are in fact upper bounds on $\overline{\mathbb{E}X^{*}}$ and
$\overline{\mathrm{Var}(X^{*})}$. By (E.59) and Lemmas E.7–E.10, for every
post-expansion sum $Y$ with $N_{W}^{*}\leq 4$ we have

$\displaystyle|\mathbb{E}Y|$
$\displaystyle\leq|\mathbb{E}X|+o(\|\theta\|_{2}^{-2})\sqrt{\mathbb{E}[X^{2}]}=|\mathbb{E}X|+o(\|\theta\|_{2}^{-2})\sqrt{\mathbb{E}[X]^{2}+\mathrm{Var}(X)}$
$\displaystyle\lesssim\tilde{\lambda}^{2}\lambda_{1}+o(\|\theta\|_{2}^{-2})\cdot\sqrt{\tilde{\lambda}^{4}\lambda_{1}^{2}+\lambda_{1}^{4}+\tilde{\lambda}^{6}+\tilde{\lambda}^{2}\lambda_{1}^{3}}$
$\displaystyle\lesssim\tilde{\lambda}^{2}\lambda_{1}+\lambda_{1}^{2}+\tilde{\lambda}^{3}+|\tilde{\lambda}|\lambda_{1}^{3/2}=o(\tilde{\lambda}^{4})$

by the assumption that $|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$.
Similarly,

$\displaystyle\mathrm{Var}(Y)$
$\displaystyle\lesssim\mathrm{Var}(X)+o(\|\theta\|_{2}^{-4})\mathbb{E}[X^{2}]=\mathrm{Var}(X)+o(\|\theta\|_{2}^{-4})(\mathbb{E}[X]^{2}+\mathrm{Var}(X))$
$\displaystyle\lesssim\lambda_{1}^{4}+\tilde{\lambda}^{6}+\tilde{\lambda}^{2}\lambda_{1}^{3}+o(\|\theta\|_{2}^{-4})\cdot\big{(}\tilde{\lambda}^{4}\lambda_{1}^{2}+\lambda_{1}^{4}+\tilde{\lambda}^{6}+\tilde{\lambda}^{2}\lambda_{1}^{3}\big{)}\lesssim
o(\tilde{\lambda}^{8}).$

###### Analysis of terms with $N^{*}_{W}>4$

Recall that

$\displaystyle\eta=\frac{1}{\sqrt{v}}(\mathbb{E}A){\bf
1}_{n},\;\;\tilde{\eta}=\frac{1}{\sqrt{v}}A{\bf 1}_{n},\;\;v={\bf
1}_{n}^{\prime}(\mathbb{E}A){\bf 1}_{n}$ .

Define

$\displaystyle G_{i}=\tilde{\eta}_{i}-\eta_{i}.$ (E.62)

Among the post-expansion sums in Table (1) satisfying $N^{*}_{W}=5$, only
$R_{7},R_{8},$ and $R_{25}$–$R_{28}$ depend on $\tilde{\Omega}$. Each of these
terms falls into one of the types

$\displaystyle J^{\prime}_{5}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{jk}(G_{i}G_{j}G_{k}G_{\ell}W_{\ell
i}),$ $\displaystyle J^{\prime}_{6}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{k\ell}(G_{i}G^{2}_{j}G_{k}W_{\ell
i})$ $\displaystyle J_{9}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}\eta_{k}\widetilde{\Omega}_{\ell
i}(G_{i}G_{j}^{2}G_{k}G_{\ell})$ $\displaystyle J_{10}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}\eta_{\ell}\widetilde{\Omega}_{\ell
i}(G_{i}G_{j}^{2}G^{2}_{k}).$

See (Jin et al., 2021c, Supplement, Section G.4.10.2) for more details.

To handle $J^{\prime}_{5}$ and $J^{\prime}_{6}$, we compare them to

$\displaystyle J_{5}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}\eta_{j}\eta_{k}(G_{i}G_{j}G_{k}G_{\ell}W_{\ell
i})$ $\displaystyle J_{6}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}\eta_{k}\eta_{\ell}(G_{i}G^{2}_{j}G_{k}W_{\ell
i}),$

both of which are considered in (Jin et al., 2021c, Supplement, Section
G.4.10.2). Note that neither $J_{5}$ nor $J_{5}$ depends on $\tilde{\Omega}$.
Setting $T=J^{\prime}_{5}$ and $T^{*}=J_{5}$ in Lemma E.13 and noting that
$|\tilde{\Omega}_{jk}|\lesssim\theta_{j}\theta_{k}$ by (E.24), we see that the
hypotheses of Lemma E.13 are satisfied. In (Jin et al., 2021c, Supplement,
Section G.4.10.2), it is shown that

$\displaystyle\mathbb{E}[J_{5}^{2}]\leq\overline{\mathbb{E}[J_{5}]}^{2}+\overline{\mathrm{Var}(J_{5})}=o(\|\theta\|_{2}^{8}).$

Applying Lemma E.13, we conclude that

$\mathbb{E}[J_{5}^{{}^{\prime}2}]=o(\|\theta\|_{2}^{8}).$

Similarly, it is shown in (Jin et al., 2021c, Supplement, Section G.4.10.2)
that

$\displaystyle\mathbb{E}[J_{6}^{2}]\leq\overline{\mathbb{E}[J_{6}]}^{2}+\overline{\mathrm{Var}(J_{6})}=o(\|\theta\|_{2}^{8}).$

Setting $T=J^{\prime}_{6}$ and $T^{*}=J_{6}$, the hypotheses of Lemma E.13 are
satisfied because $|\tilde{\Omega}_{k\ell}|\lesssim\theta_{k}\theta_{\ell}$.
We conclude that

$\mathbb{E}[J_{6}^{{}^{\prime}2}]=o(\|\theta\|_{2}^{8}).$

The terms $J_{9}$ and $J_{10}$ can be analyzed explicitly using the strategy
described in Section E.4.1. We omit the full details and instead give a
simplified proof in the case where $\|\theta\|_{2}\gg[\log(n)]^{5/2}$. The
event

$E=\cap_{i=1}^{n}E_{i},\qquad\mbox{where}\quad
E_{i}=\big{\\{}\sqrt{v}|G_{i}|\leq
C_{0}\sqrt{\theta_{i}\|\theta\|_{1}\log(n)}\bigr{\\}}.$ (E.63)

is introduced in (Jin et al., 2021c, Supplement,pg.110). By applying
Bernstein’s inequality and the union bound, it is shown that $E$ holds with
probability at least $1-n^{-C_{0}/2.01}$. Applying the crude bound
$|G_{i}|\leq n$ and triangle inequality, we see that $|J_{9}|\lesssim n^{9}$
with high probability, and thus for $C_{0}$ sufficiently large,

$\displaystyle\mathbb{E}[|J_{9}|^{2}\cdot\mathbf{1}_{E^{c}}]=o(1).$

Under the event $E$, we have by (E.20),

$\displaystyle|J_{9}|$
$\displaystyle\leq\sum_{i,j,k,\ell}|\eta_{k}\widetilde{\Omega}_{\ell
i}||G_{i}G_{j}^{2}G_{k}G_{\ell}|$
$\displaystyle\lesssim\sum_{i,j,k,\ell}(\theta_{i}\theta_{k}\theta_{\ell})\frac{\sqrt{\theta_{i}\theta_{j}^{2}\theta_{k}\theta_{\ell}\|\theta\|_{1}^{5}[\log(n)]^{5}}}{\sqrt{v^{5}}}$
$\displaystyle\lesssim\frac{[\log(n)]^{5/2}}{\sqrt{\|\theta\|_{1}^{5}}}\Bigl{(}\sum_{i}\theta^{3/2}_{i}\Bigr{)}\Bigl{(}\sum_{j}\theta_{j}\Bigr{)}\Bigl{(}\sum_{k}\theta^{3/2}_{k}\Bigr{)}\Bigl{(}\sum_{\ell}\theta^{3/2}_{\ell}\Bigr{)}$
$\displaystyle\lesssim\frac{[\log(n)]^{5/2}}{\sqrt{\|\theta\|_{1}^{3}}}\Bigl{(}\sum_{i}\theta^{3/2}_{i}\Bigr{)}^{3}$
$\displaystyle\lesssim\frac{[\log(n)]^{5/2}}{\sqrt{\|\theta\|_{1}^{3}}}\Bigl{(}\sum_{i}\theta_{i}^{2}\Bigr{)}^{3/2}\Bigl{(}\sum_{i}\theta_{i}\Bigr{)}^{3/2}$
$\displaystyle\lesssim[\log(n)]^{5/2}\|\theta\|^{3}.$

It follows that

$\displaystyle\mathbb{E}[J_{9}^{2}]=\mathrm{Var}(J_{9})+\mathbb{E}[J_{9}]^{2}=o(\|\theta\|_{2}^{8}).$

We give a similar, simplified argument for $J_{10}$ assuming that
$\|\theta\|_{2}\gg[\log(n)]^{5/2}$. Under the event $E$, we have

$\displaystyle|J_{10}|$
$\displaystyle\leq\sum_{i,j,k,\ell}|\eta_{\ell}\widetilde{\Omega}_{\ell
i}||G_{i}G_{j}^{2}G^{2}_{k}|$
$\displaystyle\lesssim\sum_{i,j,k,\ell}(\theta_{i}\theta_{\ell}^{2})\frac{\sqrt{\theta_{i}\theta_{j}^{2}\theta^{2}_{k}\|\theta\|_{1}^{5}[\log(n)]^{5}}}{\sqrt{v^{5}}}$
$\displaystyle\lesssim\frac{[\log(n)]^{5/2}}{\sqrt{\|\theta\|_{1}^{5}}}\Bigl{(}\sum_{i}\theta_{i}^{3/2}\Bigr{)}\Bigl{(}\sum_{j}\theta_{j}\Bigr{)}\Bigl{(}\sum_{k}\theta_{k}\Bigr{)}\Bigl{(}\sum_{\ell}\theta_{\ell}^{2}\Bigr{)}$
$\displaystyle\lesssim\frac{[\log(n)]^{5/2}}{\sqrt{\|\theta\|_{1}^{5}}}\bigl{(}\|\theta\|\sqrt{\|\theta\|_{1}}\bigr{)}\|\theta\|^{2}_{1}\|\theta\|^{2}$
$\displaystyle\lesssim[\log(n)]^{5/2}\|\theta\|^{3};$

Hence

$\displaystyle\mathbb{E}[J_{10}^{2}]=\mathrm{Var}(J_{10})+\mathbb{E}[J_{10}]^{2}=o(\|\theta\|_{2}^{8}).$

Next we consider the terms with $N_{W}^{*}=6$. The only term that depends on
$\tilde{\Omega}$ is $R_{32}$, which has the form

$K_{5}^{\prime}=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{ik}G_{i}G_{j}^{2}G_{k}G_{\ell}^{2}.$

The variance of $K_{5}^{\prime}$ can be analyzed explicitly using the strategy
described in Section E.4.1. To save space, we give a simplified argument when
$\|\theta\|_{2}\gg[\log(n)]^{3/2}$. Again let $E$ denote the event (E.63).
Under this event we have

$\displaystyle|K_{5}^{\prime}|$
$\displaystyle\lesssim\sum_{i,j,k,\ell}(\theta_{i}\theta_{k})\frac{\sqrt{\theta_{i}\theta_{j}^{2}\theta_{k}\theta_{\ell}^{2}}\|\theta\|_{1}^{3}[\log(n)]^{3}}{v^{3}}$
$\displaystyle\lesssim\frac{[\log(n)]^{3}}{\|\theta\|_{1}^{3}}\Bigl{(}\sum_{i}\theta_{i}^{3/2}\Bigr{)}\Bigl{(}\sum_{j}\theta_{j}\Bigr{)}\Bigl{(}\sum_{k}\theta_{k}^{3/2}\Bigr{)}\Bigl{(}\sum_{\ell}\theta_{\ell}\Bigr{)}$
$\displaystyle\lesssim\frac{[\log(n)]^{3}}{\|\theta\|_{1}^{3}}\bigl{(}\|\theta\|\sqrt{\|\theta\|_{1}}\bigr{)}^{2}\|\theta\|_{1}^{2}$
$\displaystyle\lesssim[\log(n)]^{3}\|\theta\|^{2},$

Above we apply (E.20) and (E.24) as well as Cauchy–Schwarz. It follows that

$\displaystyle\mathbb{E}[K_{5}^{{}^{\prime}2}]=\mathrm{Var}(K_{5}^{\prime})+\mathbb{E}[K_{5}^{\prime}]^{2}=o(\|\theta\|_{2}^{8}).$

Finally, all terms with $N^{*}_{W}\geq 7$ have no dependence on
$\tilde{\Omega}$, and thus the bounds carry over immediately (see (Jin et al.,
2021c, Supplement, Section G.4.10.4) for details). This completes the proof of
the lemma. ∎

#####  E.4.7 Proof of Lemma E.12

Define

$\epsilon_{ij}^{(1)}=\eta_{i}^{*}\eta_{j}^{*}-\eta_{i}\eta_{j},\quad\epsilon_{ij}^{(2)}=(1-\frac{v}{V})\eta_{i}\eta_{j},\quad\epsilon^{(3)}_{ij}=-(1-\frac{v}{V})\delta_{ij}.$

Note that $\epsilon_{ij}^{(1)}$ is a nonstochastic term. As shown in (Jin et
al., 2021c, Supplement, pg. 119), we have

$\displaystyle|\epsilon_{ij}^{(1)}|\lesssim\frac{\|\theta\|_{\infty}}{\|\theta\|_{1}}\cdot\theta_{i}\theta_{j},$

which implies that

$\displaystyle|\epsilon_{ij}^{(1)}|\lesssim\frac{1}{\|\theta\|_{2}^{2}}\cdot\theta_{i}\theta_{j}$
(E.64)

by (E.2).

As discussed in (Jin et al., 2021c, Supplement, Section G.3), $Q-Q^{*}$ is a
finite sum of terms of the form

$\sum_{i,j,k,\ell(dist)}a_{ij}b_{jk}c_{k\ell}d_{\ell
i},\qquad\mbox{where}\quad
a,b,c,d\in\\{\widetilde{\Omega},W,\delta,\tilde{r},\epsilon^{(1)},\epsilon^{(2)},\epsilon^{(3)}\\}.$
(E.65)

Let $Y$ denote an arbitrary term of the form above, and given
$X\in\\{\widetilde{\Omega},W,\delta,\tilde{r},\epsilon^{(1)},\epsilon^{(2)},\epsilon^{(3)}\\}$,
let $N_{X}$ denote the total number of $a,b,c,d$ that are equal to $X$. It
holds that

$Y=\big{(}\frac{v}{V}\big{)}^{N_{\tilde{r}}}(-1)^{N_{\epsilon}^{(3)}}\Bigl{(}1-\frac{v}{V}\Bigr{)}^{N^{(2)}_{\epsilon}+N^{(3)}_{\epsilon}}X,\qquad
X\equiv\sum_{i,j,k,\ell(dist)}a_{ij}b_{jk}c_{k\ell}d_{\ell i}.$

where

$\begin{cases}a,b,c,d\in\\{\widetilde{\Omega},W,\delta,(V/v)\tilde{r},\epsilon^{(1)},\eta\eta^{\mathsf{T}}\\},\\\
\mbox{number of $\eta_{i}\eta_{j}$ in the product is $N^{(2)}_{\epsilon}$},\\\
\mbox{number of $\delta_{ij}$ in the product is
$N_{\delta}+N_{\epsilon}^{(3)}$},\\\ \mbox{number of any other term in the
product is same as before}.\end{cases}$ (E.66)

Let $x_{n}$ denote a sequence of real numbers such that
$\sqrt{\log(\|\theta\|_{1})}\ll x_{n}\ll\|\theta\|_{1}$. Mimicking the
argument in (Jin et al., 2021c, Supplement,pg.121), it holds that

$\displaystyle\mathbb{E}[Y^{2}]\lesssim\Bigl{(}\frac{x^{2}_{n}}{\|\theta\|_{1}^{2}}\Bigr{)}^{N^{(2)}_{\epsilon}+N^{(3)}_{\epsilon}}\cdot\mathbb{E}[X^{2}]+o(1),$

By (E.4), there exists a sequence $\log(\|\theta\|_{1})\ll
x_{n}\ll\|\theta\|_{1}/\|\theta\|_{2}^{2}$. Hence,

$\displaystyle\mathbb{E}[Y^{2}]\lesssim\Bigl{(}\frac{1}{\|\theta\|_{2}^{4}}\Bigr{)}^{N^{(2)}_{\epsilon}+N^{(3)}_{\epsilon}}\cdot\mathbb{E}[X^{2}]+o(1),$
(E.67)

Thus we focus on controlling $\mathbb{E}[X^{2}]$.

Consider a new random variable $X^{*}$ defined to be

$\displaystyle
X^{*}\equiv\sum_{i,j,k,\ell(dist)}a_{ij}^{*}b_{jk}^{*}c_{k\ell}^{*}d_{\ell
i}^{*}$

where

$\displaystyle a^{*}$
$\displaystyle=\begin{cases}\frac{1}{\|\theta\|_{2}^{2}}\cdot\theta\theta^{\mathsf{T}}&\quad\text{
if }a=\epsilon^{(1)}\\\ \theta\theta^{\mathsf{T}}&\quad\text{ if
}a\in\\{\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\ a&\quad\text{ otherwise
}\end{cases}$ $\displaystyle b^{*}$
$\displaystyle=\begin{cases}\frac{1}{\|\theta\|_{2}^{2}}\cdot\theta\theta^{\mathsf{T}}&\quad\text{
if }b=\epsilon^{(1)}\\\ \theta\theta^{\mathsf{T}}&\quad\text{ if
}b\in\\{\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\ b&\quad\text{ otherwise
}\end{cases}$ $\displaystyle c^{*}$
$\displaystyle=\begin{cases}\frac{1}{\|\theta\|_{2}^{2}}\cdot\theta\theta^{\mathsf{T}}&\quad\text{
if }c=\epsilon^{(1)}\\\ \theta\theta^{\mathsf{T}}&\quad\text{ if
}c\in\\{\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\ c&\quad\text{ otherwise
}\end{cases}$ $\displaystyle d^{*}$
$\displaystyle=\begin{cases}\frac{1}{\|\theta\|_{2}^{2}}\cdot\theta\theta^{\mathsf{T}}&\quad\text{
if }d=\epsilon^{(1)}\\\ \theta\theta^{\mathsf{T}}&\quad\text{ if
}\in\\{\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\ d&\quad\text{ otherwise
}.\end{cases}$

Also define

$\tilde{X}=\sum_{ijk\ell(dist)}\tilde{a}_{ij}\tilde{b}_{jk}\tilde{c}_{k\ell}\tilde{d}_{\ell
i}$

where

$\displaystyle\tilde{a}$
$\displaystyle=\begin{cases}\theta\theta^{\mathsf{T}}&\quad\text{ if
}a\in\\{\epsilon^{(1)},\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\
a&\quad\text{ otherwise }\end{cases}$ $\displaystyle\tilde{b}$
$\displaystyle=\begin{cases}\theta\theta^{\mathsf{T}}&\quad\text{ if
}b\in\\{\epsilon^{(1)},\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\
b&\quad\text{ otherwise }\end{cases}$ $\displaystyle\tilde{c}$
$\displaystyle=\begin{cases}\theta\theta^{\mathsf{T}}&\quad\text{ if
}c\in\\{\epsilon^{(1)},\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\
c&\quad\text{ otherwise }\end{cases}$ $\displaystyle\tilde{d}$
$\displaystyle=\begin{cases}\theta\theta^{\mathsf{T}}&\quad\text{ if
}d\in\\{\epsilon^{(1)},\tilde{\Omega},\eta\eta^{\mathsf{T}}\\}\\\
d&\quad\text{ otherwise }.\end{cases}$

Note that
$X^{*}=\big{(}\frac{1}{\|\theta\|_{2}^{2}}\big{)}^{N_{\epsilon}^{(1)}}\tilde{X}$
and
$\tilde{a},\tilde{b},\tilde{c},\tilde{d}\in\\{\theta\theta^{\mathsf{T}},W,\delta,(V/v)\tilde{r}\\}$.
Later we show that

$\displaystyle\mathbb{E}[X^{2}]\lesssim\mathbb{E}[X^{*2}]$ (E.68)

First we bound $\mathbb{E}[\tilde{X}^{2}]$ in the case when
$N_{W}+N_{\delta}+N_{\tilde{r}}=0$. Note that for all such terms in $Q-Q^{*}$,
we have
$N_{\epsilon}^{(1)}+N_{\epsilon}^{(2)}+N_{\epsilon}^{(3)}+N_{\tilde{\Omega}}=4$
and $N_{\tilde{\Omega}}<4$. In particular, $\tilde{X}$ and $X^{*}$ are
nonstochastic. If $N_{\tilde{\Omega}}=3$, then by (E.22) and (E.24),

$\displaystyle|\tilde{X}|$
$\displaystyle=\big{|}\sum_{ijk\ell(dist)}\tilde{\Omega}_{ij}\tilde{\Omega}_{jk}\tilde{\Omega}_{k\ell}\theta_{i}\theta_{\ell}\big{|}\lesssim\frac{1}{\|\theta\|_{2}^{2}}\sum_{ijk\ell}\beta_{i}\theta_{i}^{2}\beta_{j}^{2}\theta_{j}^{2}\beta_{k}^{2}\theta_{k}^{2}\beta_{\ell}\theta_{\ell}^{2}\lesssim\|\beta\circ\theta\|_{2}^{6}\|\theta\|_{2}^{2}$

If $N_{\tilde{\Omega}}=2$, there are two cases. First,

$\displaystyle|\tilde{X}|$
$\displaystyle=\big{|}\sum_{ijk\ell(dist)}\tilde{\Omega}_{ij}\tilde{\Omega}_{jk}\theta_{k}\theta_{\ell}\theta_{\ell}\theta_{i}\big{|}\lesssim\sum_{ijk\ell}\beta_{i}\theta_{i}\beta_{j}^{2}\theta_{j}^{2}\beta_{k}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{i}\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4},$

and second

$\displaystyle|\tilde{X}|$
$\displaystyle=\big{|}\sum_{ijk\ell(dist)}\tilde{\Omega}_{ij}\theta_{j}\theta_{k}\tilde{\Omega}_{k\ell}\theta_{\ell}\theta_{i}\big{|}\lesssim\sum_{ijk\ell}\beta_{i}\theta_{i}^{2}\beta_{j}\theta_{j}^{2}\beta_{k}\theta_{k}^{2}\beta_{\ell}\theta_{\ell}^{2}\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}$

Finally if $N_{\tilde{\Omega}}=1$,

$\displaystyle|\tilde{X}|$
$\displaystyle=\big{|}\sum_{ijk\ell(dist)}\tilde{\Omega}_{ij}\theta_{j}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{i}\big{|}\lesssim\sum_{ijk\ell}\tilde{\beta}_{i}\theta_{i}^{2}\beta_{j}\theta_{j}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{6}.$

Note that when $N_{W}+N_{\delta}+N_{\tilde{r}}=0$

$|X|\lesssim|X^{*}|$

by (E.22), (E.20), and (E.64). By the bounds above, we conclude that

$\displaystyle|Y|\lesssim\big{(}\frac{1}{\|\theta\|_{2}^{2}}\big{)}^{N_{\varepsilon}^{(1)}+N_{\varepsilon}^{(2)}+N_{\varepsilon}^{(3)}}|\tilde{X}|\lesssim\max_{1\leq
k\leq
3}\|\beta\circ\theta\|_{2}^{2k}\|\theta\|_{2}^{2(4-k)}\lesssim|\tilde{\lambda}|^{3}.$
(E.69)

Next we bound $\mathbb{E}[\tilde{X}^{2}]$ in the case when
$N_{W}+N_{\delta}+N_{\tilde{r}}>0$. By Lemma E.2 and the definition of
$f\in\mathbb{R}^{2}$ there, we have
$\tilde{\Omega}_{ij}=\alpha_{i}\alpha_{j}\theta_{i}\theta_{j}$ where
$\alpha=\Pi f$. Observe that in Lemmas E.7–E.11, we bound the mean and
variance of all terms of the form

$Z\equiv\sum_{i,j,k,\ell(dist)}a_{ij}b_{jk}c_{k\ell}d_{\ell
i},\qquad\mbox{where}\quad
a,b,c,d\in\\{\widetilde{\Omega},W,\delta,(V/v)\tilde{r}\\}.$

As a result, the proofs of Lemmas E.7–E.11 produce a function $F$ such that

$\displaystyle\mathbb{E}[Z^{2}]\leq
F(\theta,\beta;N_{\tilde{\Omega}},N_{W},N_{\delta},N_{\tilde{r}}),$

where recall that $|\alpha_{i}|\leq\beta_{i}$.

Note that in what follows, we use ′ to denote a new variable rather than the
transpose. As a direct corollary to the proofs of Lemmas E.7–E.11, if we
define a new matrix
$\tilde{\Omega}^{\prime}=\alpha^{\prime}_{i}\alpha^{\prime}_{j}\theta_{i}\theta_{j}$
where $\alpha^{\prime}$ is a vector with a coordinate-wise bound of the form
$|\alpha^{\prime}_{i}|\leq\beta^{\prime}_{i}$, then

$Z^{\prime}\equiv\sum_{i,j,k,\ell(dist)}a_{ij}b_{jk}c_{k\ell}d_{\ell
i},\qquad\mbox{where}\quad
a,b,c,d\in\\{\widetilde{\Omega}^{\prime},W,\delta,(V/v)\tilde{r}\\}$

satisfies

$\displaystyle\mathbb{E}[Z^{{}^{\prime}2}]\leq
F(\theta,\beta^{\prime};N_{\tilde{\Omega}^{\prime}}^{\prime},N_{W}^{\prime},N_{\delta}^{\prime},N_{\tilde{r}}^{\prime}),$

where, for example, $N^{\prime}_{\delta}$ counts the number of appearances of
$\delta$ in $Z^{\prime}$. This can be verified by tracing each calculation in
Lemmas E.7–E.11 line by line, replacing all occurences of $\tilde{\Omega}$
with $\tilde{\Omega}^{\prime}$, and replacing every usage of the bound
$|\alpha_{i}|\leq\beta_{i}$ with $|\alpha_{i}^{\prime}|\leq\beta^{\prime}_{i}$
instead. In other words, our proofs make no use of the specific value of
$\alpha=\Pi f$.

In particular, if $\alpha=\mathbf{1}$, then
$\tilde{\Omega}^{\prime}=\theta\theta^{\mathsf{T}}$. In this case we may set
$\beta=\mathbf{1}$. Observe that $\tilde{X}$ has the form of $Z^{\prime}$ with
this choice of $\tilde{\Omega}^{\prime}$. Hence,

$\displaystyle\mathbb{E}[\tilde{X}^{2}]\leq
F(\theta,\mathbf{1};\tilde{N}_{\tilde{\Omega}^{\prime}},\tilde{N}_{W},\tilde{N}_{\delta},\tilde{N}_{\tilde{r}}).$
(E.70)

By careful inspection of the bounds in Lemmas E.7–E.11, we see that

$\displaystyle
F(\theta,\mathbf{1};N_{\tilde{\Omega}^{\prime}},N_{W},N_{\delta},N_{\tilde{r}})\lesssim\|\theta\|_{2}^{12}.$
(E.71)

In (Jin et al., 2021c, Supplement, Section G.3) it is shown that all terms in
the decomposition of $Q-Q^{*}$ satisfy
$N_{\epsilon}^{(1)}+N_{\epsilon}^{(2)}+N_{\epsilon}^{(3)}>0$. Using this fact
along with (E.67), (E.68), (E.70) and (E.71),

$\displaystyle\mathbb{E}[Y^{2}]$
$\displaystyle\lesssim\Bigl{(}\frac{1}{\|\theta\|_{2}^{4}}\Bigr{)}^{N^{(2)}_{\epsilon}+N^{(3)}_{\epsilon}}\cdot\big{(}\frac{1}{\|\theta\|_{2}^{2}}\big{)}^{2N_{\epsilon}^{(1)}}\cdot\mathbb{E}[\tilde{X}^{2}]+o(1)\lesssim\|\theta\|_{2}^{8}.$
(E.72)

Observe that (E.69) and (E.72) recover the bounds in Lemma E.12 under the
alternative hypothesis, and the bounds under the null hypothesis transfer
directly from (Jin et al., 2021c, Lemma G.12). Thus it only remains to justify
(E.68) when $N_{W}+N_{\delta}+N_{\tilde{r}}>0$. Let us write

$\displaystyle X$
$\displaystyle=\sum_{i_{1},\ldots,i_{m}}c_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}}$
$\displaystyle X^{*}$
$\displaystyle=\sum_{i_{1},\ldots,i_{m}}c^{*}_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}}$

in the form described in Section E.4.1, where now

  * •

$c_{i_{1},\ldots,i_{m}}=\prod_{(s,s^{\prime})\in
A}\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}$ is a nonstochastic term
where $A\subset[m]\times[m]$ and

$\Gamma^{(s,s^{\prime})}\in\\{\tilde{\Omega},\eta^{*}\mathbf{1}^{\mathsf{T}},\eta\mathbf{1}^{\mathsf{T}},\mathbf{1}\mathbf{1}^{\mathsf{T}},\epsilon^{(1)},\eta\eta^{\mathsf{T}}\\}$

  * •

$c^{*}_{i_{1},\ldots,i_{m}}=\prod_{(s,s^{\prime})\in
A}\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}$ is a nonstochastic term
where $A\subset[m]\times[m]$ and

$\Gamma^{(s,s^{\prime})}\in\\{\eta^{*}\mathbf{1}^{\mathsf{T}},\eta\mathbf{1}^{\mathsf{T}},\mathbf{1}\mathbf{1}^{\mathsf{T}},\theta\theta^{\mathsf{T}}/\|\theta\|_{2}^{2},\theta\theta^{\mathsf{T}}\\}$

  * •

$G_{i_{1},\ldots,i_{m}}=\prod_{(s,s^{\prime})\in B}W_{i_{s},i_{s^{\prime}}}$
where $B\subset[m]\times[m]$.

If
$\Gamma^{(s,s^{\prime})}\in\\{\theta\theta^{\mathsf{T}},\theta\theta^{\mathsf{T}}/\|\theta\|_{2}^{2}\\}$,
we simply let $\overline{\Gamma^{(s,s^{\prime})}}=\Gamma^{(s,s^{\prime})}$ and
define

$\overline{c^{*}_{i_{1},\ldots,i_{m}}}=\prod_{(s,s^{\prime})\in
A}\overline{\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}}$

as in Section E.4.1. We also define the canonical upper bound
$\overline{\mathbb{E}X^{*}}$ on $|\mathbb{E}X^{*}|$ and the canonical upper
bound $\overline{\mathrm{Var}(X^{*})}$ on $\mathrm{Var}(X^{*})$ similarly to
Section E.4.1. By the discussion above and (E.70),

$\displaystyle\overline{\mathbb{E}[X^{*}]}\equiv\big{(}\frac{1}{\|\theta\|_{2}^{2}}\big{)}^{N_{\epsilon}^{(1)}}\sqrt{F(\theta,\mathbf{1};\tilde{N}_{\tilde{\Omega}^{\prime}},\tilde{N}_{W},\tilde{N}_{\delta},\tilde{N}_{\tilde{r}})},$

and

$\displaystyle\overline{\mathrm{Var}(X^{*})}\equiv\big{(}\frac{1}{\|\theta\|_{2}^{2}}\big{)}^{2N_{\epsilon}^{(1)}}F(\theta,\mathbf{1};\tilde{N}_{\tilde{\Omega}^{\prime}},\tilde{N}_{W},\tilde{N}_{\delta},\tilde{N}_{\tilde{r}}).$

Next observe that

$\displaystyle|c_{i_{1},\ldots,i_{m}}|\lesssim|c^{*}_{i_{1},\ldots,i_{m}}|\lesssim|\overline{c^{*}_{i_{1},\ldots,i_{m}}}|.$

By a mild extension of Lemma E.13 it follows that

$\displaystyle|\mathbb{E}X|$ $\displaystyle\lesssim\overline{\mathbb{E}X^{*}}$
$\displaystyle\mathrm{Var}(X)$
$\displaystyle\lesssim\overline{\mathrm{Var}(X^{*})},$

which verifies (E.68) and completes the proof. ∎

####  E.5 Calculations in the SBM setting

We compute the order of $\lambda_{1}$ and $\tilde{\lambda}_{1}=\lambda_{2}$ in
the SBM setting (which are the two nonzero eigenvalues of $\Omega$). By basic
algebra, $\lambda_{1},\lambda_{2}$ are also the two nonzero eigenvalues of the
following matrix

$\left[\begin{array}[]{cc}N&0\\\
0&n-N\end{array}\right]^{1/2}\times\left[\begin{array}[]{cc}a&b\\\
b&c\end{array}\right]\times\left[\begin{array}[]{cc}N&0\\\
0&n-N\end{array}\right]^{1/2}=\left[\begin{array}[]{cc}aN&\sqrt{N(n-N)}b\\\
\sqrt{N(n-N)}b&(n-N)c\end{array}\right],$

where $b$ is given by (H.1). By direct calculations and pluging the
definitions of $b$,

$\displaystyle\lambda_{1}=$
$\displaystyle\frac{aN+(n-N)c+\sqrt{(aN-(n-N)c)^{2}+4N(n-N)b^{2}}}{2}$
$\displaystyle=$ $\displaystyle\frac{aN+(n-N)c+|(n-N)c-aN|\frac{n}{n-2N}}{2}.$

Recall that

$b=\frac{nc-N(a+c)}{n-2N}.$

It is required that $b\geq 0$. Therefore,

$nc-(a+c)N\geq 0,\qquad\text{and so}\qquad(n-N)c\geq aN.$ (E.73)

By direct calculations, it follows that

$\lambda_{1}=\frac{(n-N)^{2}c-aN^{2}}{n-2N}=\frac{(n-N)c((n-N)-\frac{aN}{(n-N)c}N)}{n-2N}\sim\frac{(n-N)c(n-N)}{n-2N}\sim
nc$

where in the last two $\asymp$, we have used $(n-N)c\geq aN$ and $N=o(n)$.
Similarly,

$\lambda_{2}=\frac{aN+(n-N)c-\sqrt{(aN-(n-N)c)^{2}+4N(n-N)b^{2}}}{2}=\frac{(a-c)N(n-N)}{n-2N}\sim
N(a-c).$

###  Appendix F Proof of Theorem 2.3 (Powerlessness of $\chi^{2}$ test)

We compare the SgnQ test with the $\chi^{2}$ test. Recall we assume
$\theta_{i}=\mathbf{1}_{n}$. The $\chi^{2}$ test statistic is defined to be

$X_{n}=\frac{1}{\hat{\alpha}(1-\hat{\alpha})(n-1)}\sum_{i=1}^{n}\big{(}(A\mathbf{1}_{n})_{i}-\hat{\alpha}n\big{)}^{2},\qquad\text{
where }\hat{\alpha}=\frac{1}{n(n-1)}\sum_{i\neq j}A_{ij}.$

We also define an idealized $\chi^{2}$ test statistic by

$\tilde{X}_{n}=\frac{1}{\alpha(1-\alpha)(n-1)}\sum_{i=1}^{n}\big{(}(A\mathbf{1}_{n})_{i}-\alpha
n\big{)}^{2},\qquad\text{ where }\alpha=\frac{1}{n(n-1)}\sum_{i\neq
j}\Omega_{ij}.$

The $\chi^{2}$ test is defined to be

$\chi^{2}_{n}=\mathbf{1}\bigg{[}\frac{|X_{n}-n|}{\sqrt{2n}}>z_{\gamma/2}\bigg{]},$

where $z_{\gamma}$ is such that $\mathbb{P}[|N(0,1)|\geq z_{\gamma}]=\gamma$.
Similarly, the idealized $\chi^{2}$ test is defined by

$\tilde{\chi}^{2}_{n}=\mathbf{1}\bigg{[}\frac{|\tilde{X}_{n}-n|}{\sqrt{2n}}>z_{\gamma/2}\bigg{]},$

In certain degree-homogeneous settings, the $\chi^{2}$ test is known to have
full power Arias-Castro & Verzelen (2014); Cammarata & Ke (2022).

We prove the following, which directly implies Theorem 2.3.

######  Theorem F.1.

Suppose that (2.7) holds and that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$, and recall that under these
conditions, the power of the SgnQ test goes to $1$. Next suppose that the
following regularity conditions hold under the null and alternative:

  * (i)

$\theta=\mathbf{1}_{n}$

  * (ii)

$\alpha\to 0$

  * (iii)

$\alpha^{2}n\to\infty$

  * (iv)

$\sum_{ij}(\Omega_{ij}-\alpha)^{2}=o(\alpha n^{3/2})$.

Then the power of both the $\chi^{2}$-test and idealized $\chi^{2}$-test goes
to $\gamma$ (which is the prescribed level of the test).

Note that the previous theorem implies Theorem 2.3. By Theorem 2.2, SgnQ has
full power even without the extra regularity conditions (i)–(iv). On the other
hand, for any fixed alternative DCBM satisfying (i)–(iv), Theorem F.1 implies
that $\chi^{2}$ has power $\kappa$.

###### Proof of Theorem F.1.

Theorem 2.2 confirms that SgnQ has full power provided that (2.7) holds and
that $|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$. It remains to justify
the powerlessness of the $\chi^{2}$ test.

Consider an SBM in the alternative such that $\Omega\mathbf{1}=(\alpha
n)\mathbf{1}$ and $|\tilde{\lambda}|/\sqrt{\lambda_{1}}\asymp
N(a-c)/\sqrt{nc}\to\infty$. To do this we select an integer $N>0$ to be the
size of the smaller community and set $b=\frac{cn-(a+c)N}{n-2N}$. The
remaining regularity conditions are satisfied if $c\to 0$ and $cn\ll
N(a-c)^{2}\ll cn^{3/2}$. We show that both $X_{n}$ and $\tilde{X}_{n}$ are
asymptotically normal under the specified alternative, which is enough to
imply Theorem F.1.

In Cammarata & Ke (2022) it is shown that

$\hat{T}_{n}\equiv[(n-1)\hat{\alpha}(1-\hat{\alpha})](X_{n}-n)=\sum_{i,j,k\text{
(dist.)}}(A_{ik}-\hat{\alpha})(A_{jk}-\hat{\alpha}).$ (F.1)

We introduce an idealized version $T_{n}$ of $\hat{T}_{n}$, which is

$\displaystyle T_{n}=\sum_{i,j,k\text{
(dist.)}}(A_{ik}-{\alpha})(A_{jk}-{\alpha}),$

Following Cammarata & Ke (2022), we have

$\frac{X_{n}-n}{\sqrt{2n}}=\left(\frac{n-2}{n-1}\right)^{1/2}U_{n}V_{n}Z_{n}.$
(F.2)

where

$\displaystyle
U_{n}=\frac{\alpha_{n}(1-\alpha_{n})}{\hat{\alpha}_{n}(1-\hat{\alpha}_{n})}$ ,
$\displaystyle V_{n}=\frac{\hat{T}_{n}}{T_{n}}$ , $\displaystyle
Z_{n}=\frac{\frac{T_{n}}{(n-1)\alpha_{n}(1-\alpha_{n})}}{\sqrt{\frac{2n(n-2)}{(n-1)}}}.$

Since the terms of $\hat{\alpha}$ are bounded, the law of large numbers
implies that $U_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$.
Furthermore, since $\alpha n\to\infty$ by assumption that
$\alpha^{2}n\to\infty$, a straightforward application of the Berry-Esseen
theorem implies that

$\sqrt{\frac{n(n-1)}{2}}\frac{\hat{\alpha}_{n}-\alpha_{n}}{\sqrt{\alpha_{n}(1-\alpha_{n})}}\Rightarrow\mathcal{N}(\mu,1).$

With the previous fact, mimicking the argument in (Cammarata & Ke, 2022,
pg.32), it also follows that

$V_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1,$

provided we can show that $Z_{n}\Rightarrow N(0,1)$. We omit the details since
the argument is very similar.

Thus it suffices to study $Z_{n}$. We first analyze $T_{n}$, which we
decompose as

$\displaystyle T_{n}$ $\displaystyle=\sum_{i,j,k\text{
(dist.)}}(A_{ik}-\Omega_{ik})(A_{jk}-\Omega_{jk})+2\sum_{ijk(dist)}(\Omega_{ik}-\alpha)(A_{jk}-\Omega_{jk})$
$\displaystyle\quad+\sum_{ijk(dist)}(\Omega_{ik}-\alpha)(\Omega_{jk}-\alpha)\equiv
T_{n1}+T_{n2}+T_{n3}.$

Observe that $T_{n3}$ is non-stochastic. The second and third term are
negligible compared to $T_{n1}$. Define
$\overline{\Omega}=\Omega-\alpha\mathbf{1}\mathbf{1}^{\prime}$. By direct
calculations,

$\displaystyle\mathbb{E}T_{n2}=0,\qquad$

and

$\displaystyle\mathrm{Var}(T_{n2})$
$\displaystyle=8\sum_{j<k(dist)}\big{(}\sum_{i\notin\\{j,k\\}}\overline{\Omega}_{ik}\big{)}^{2}\Omega_{jk}(1-\Omega_{jk})=8\sum_{j<k(dist)}\big{(}\overline{\Omega}_{jk}+\overline{\Omega}_{kk}\big{)}^{2}\Omega_{jk}(1-\Omega_{jk})\lesssim\alpha
n^{2}.$

Next,

$\displaystyle|T_{n3}|$
$\displaystyle=\big{|}\sum_{ijk}\overline{\Omega}_{ik}\overline{\Omega}_{jk}-\sum_{ijk(not\,dist.)}\overline{\Omega}_{ik}\overline{\Omega}_{jk}\big{|}=\big{|}\sum_{ijk(not\,dist.)}\overline{\Omega}_{ik}\overline{\Omega}_{jk}\big{|}$
$\displaystyle\lesssim\big{|}\sum_{ij}\overline{\Omega}_{ii}\overline{\Omega}_{ji}\big{|}+\big{|}\sum_{ik}\overline{\Omega}_{ik}^{2}\big{|}+\big{|}\sum_{i}\overline{\Omega}_{ii}^{2}\big{|}=0+o(\alpha
n^{3/2})+n=o(\alpha n^{3/2}),$

where we apply the third regularity condition.

Now we focus on $T_{n1}$. By direct calculations

$\displaystyle\mathbb{E}T_{n1}=0,$

and

$\displaystyle\mathrm{Var}\,T_{n1}$
$\displaystyle=2\sum_{i,j,k(dist)}\Omega_{ik}(1-\Omega_{ik})\Omega_{jk}(1-\Omega_{jk})$
$\displaystyle=2\sum_{i,j,k}\Omega_{ik}(1-\Omega_{ik})\Omega_{jk}(1-\Omega_{jk})-2\sum_{i,j,k(not\,dist.)}\Omega_{ik}(1-\Omega_{ik})\Omega_{jk}(1-\Omega_{jk})$
$\displaystyle=2\mathbf{1}^{\prime}\Omega^{2}\mathbf{1}-2\sum_{i,j,k(not\,dist.)}\Omega_{ik}(1-\Omega_{ik})\Omega_{jk}(1-\Omega_{jk})$

Note that

$\displaystyle 2\mathbf{1}^{\prime}\Omega^{2}\mathbf{1}\sim
2n(n-1)(n-2)\alpha^{2}$

since $\alpha\to 0$. Moreover, with some simple casework we can show

$\displaystyle\sum_{i,j,k(not\,dist.)}\Omega_{ik}(1-\Omega_{ik})\Omega_{jk}(1-\Omega_{jk})\lesssim\alpha
n^{2}=o(\alpha^{2}n^{3}),$

where we use that $\alpha n\rightarrow\infty$ (because
$\alpha^{2}n\rightarrow\infty$). Hence

$\displaystyle\mathrm{Var}\,T_{n1}\sim
2n(n-1)(n-2)\alpha^{2}(1-\alpha)^{2}\sim
2n(n-1)(n-2)\alpha^{2}(1-\alpha)^{2}.$

To study $T_{n1}$ we apply the martingale central limit theorem using a
similar argument to Cammarata & Ke (2022)). Define $W_{ij}=A_{ij}-\Omega_{ij}$
and

$\displaystyle T_{n,m}$ $\displaystyle=\sum_{(i,j,k)\in
I_{m}}W_{ik}W_{jk},\qquad\text{ and }\qquad T_{n,0}=0,$ $\displaystyle
Z_{n,m}$
$\displaystyle=\sqrt{\frac{n-1}{2n(n-2)}}\frac{T_{n,m}}{(n-1)\alpha_{n}(1-\alpha_{n})},\qquad\text{
and }\qquad Z_{n,0}=0.$

where

$I_{m}=\\{(i,j,k)\in[m]^{3}\text{ s.t. $i,j,k$ are distinct}\\},$

and $m\leq n$. Define a filtration $\\{\mathcal{F}_{n,m}\\}$ where
$\mathcal{F}_{n,m}=\sigma\\{W_{ij},(i,j)\in[m]^{2}\\}$ for all $m\in[n]$, and
let $\mathcal{F}_{n,0}$ be the trivial $\sigma$-field. It is straightforward
to verify that $T_{n,m}$ and $Z_{n,m}$ are martingales with respect to this
filtration. We further define a martingale difference sequence

$X_{n,m}=Z_{n,m}-Z_{n,m-1}$

for all $m\in[n]$.

If we can show that the following conditions hold

(a)
$\displaystyle\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{2}|\mathcal{F}_{n,m-1}]\xrightarrow{\mathbb{P}}1,$
(F.3) (b)
$\displaystyle\forall\epsilon>0,\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{2}\mathbf{1}\\{|X_{n,m}>\epsilon|\\}|\mathcal{F}_{n,m-1}]\xrightarrow{\mathbb{P}}0,$
(F.4)

then the Martingale Central Limit Theorem implies that
$Z_{n}\Rightarrow\mathcal{N}(0,1)$.

Our argument follows closely Cammarata & Ke (2022). First consider (F.3). It
suffices to show that

$\mathbb{E}\left[\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{2}|\mathcal{F}_{n,m-1}]\right]\xrightarrow{n\to\infty}1,$
(F.5)

and

$\mathrm{Var}\left(\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{2}|\mathcal{F}_{n,m-1}]\right)\xrightarrow{n\to\infty}0.$
(F.6)

For notational brevity, define

$C_{n}:=(n-1)\alpha_{n}(1-\alpha_{n})\sqrt{\frac{2n(n-2)}{n-1}}.$

Mimicking the argument in (Cammarata & Ke, 2022, pgs.33-34) shows the
following. Note that all sums below are indexed up to $m-1$.

$\displaystyle\mathbb{E}[C_{n}^{2}X_{n,m}^{2}|$
$\displaystyle\mathcal{F}_{n,m-1}]=4\sum_{k\neq j;\;i\neq
l}W_{jk}W_{il}\mathbb{E}\left[W_{mk}W_{mi}\right]+4\sum_{k\neq j;\;i\neq
l}W_{jk}\mathbb{E}\left[W_{im}W_{km}W_{lm}\right]$ $\displaystyle+\sum_{i\neq
j;\;k\neq l}\mathbb{E}\left[W_{im}W_{jm}W_{km}W_{lm}\right].$ (F.7)

Continuing, we have

$\displaystyle\mathbb{E}[C_{n}^{2}X_{n,m}^{2}|\mathcal{F}_{n,m-1}]$
$\displaystyle=4\sum_{i}\sum_{j\neq i,l\neq
i}W_{ij}W_{il}\Omega_{mi}(1-\Omega_{mi})+2\sum_{i,j(dist)}\Omega_{im}(1-\Omega_{im})\Omega_{jm}(1-\Omega_{jm})$
$\displaystyle=4\sum_{ij\ell(dist)}W_{ij}W_{il}\Omega_{mi}(1-\Omega_{mi})+4\sum_{i,j(dist)}W_{ij}^{2}\Omega_{mi}(1-\Omega_{mi})$
$\displaystyle\qquad+2\sum_{i,j(dist)}\Omega_{im}(1-\Omega_{im})\Omega_{jm}(1-\Omega_{jm}).$
(F.8)

Computing expectations,

$\displaystyle\mathbb{E}[\mathbb{E}[C_{n}^{2}X_{n,m}^{2}$
$\displaystyle|\mathcal{F}_{n,m-1}]]$
$\displaystyle=4\sum_{i,j(dist)}\Omega_{ij}(1-\Omega_{ij})\Omega_{mi}(1-\Omega_{mi})+2\sum_{i,j(dist)}\Omega_{im}(1-\Omega_{im})\Omega_{jm}(1-\Omega_{jm})$

Summing over $m$ and a simple combinatorial argument yields

$\displaystyle
C_{n}^{2}\mathbb{E}\big{[}\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{2}|\mathcal{F}_{n,m-1}]\big{]}$
$\displaystyle=2\sum_{i,j,k(dist)}\Omega_{ik}(1-\Omega_{ik})\Omega_{jk}(1-\Omega_{jk})\sim
C_{n}^{2}.$

Using the identity

$W_{ij}^{2}=(1-2\Omega_{ij})W_{ij}+\Omega_{ij}(1-\Omega_{ij}),$

we have

$\displaystyle\mathbb{E}[C_{n}^{2}X_{n,m}^{2}|\mathcal{F}_{n,m-1}]$
$\displaystyle=4\sum_{ij\ell(dist)}W_{ij}W_{il}\Omega_{mi}(1-\Omega_{mi})+4\sum_{i,j(dist)}W_{ij}^{2}\Omega_{mi}(1-\Omega_{mi})$
$\displaystyle=24\sum_{i<j<\ell}W_{ij}W_{il}\Omega_{mi}(1-\Omega_{mi})+8\sum_{i<j}W_{ij}(1-2\Omega_{ij})\Omega_{mi}(1-\Omega_{mi})$
$\displaystyle\quad+4\sum_{i<j}\Omega_{ij}(1-\Omega_{ij})\Omega_{mi}(1-\Omega_{mi}).$

Thus

$\displaystyle\sum_{m=1}^{n}\mathbb{E}[C_{n}^{2}X_{n,m}^{2}|\mathcal{F}_{n,m-1}]$
$\displaystyle=24\sum_{i<j<\ell}\big{(}\sum_{m>\max(i,j,\ell)}\Omega_{mi}(1-\Omega_{mi})\,\,\big{)}W_{ij}W_{i\ell}$
$\displaystyle\quad+8\sum_{i<j}\big{(}\sum_{m>\max(i,j,\ell)}\Omega_{mi}(1-\Omega_{mi})\,\,\big{)}(1-2\Omega_{ij})W_{ij}.$

All terms above are uncorrelated. Hence,

$\displaystyle\mathrm{Var}\left(\sum_{m=1}^{n}\mathbb{E}[C_{n}^{2}X_{n,m}^{2}|\mathcal{F}_{n,m-1}]\right)$
$\displaystyle=24^{2}\sum_{i<j<\ell}\big{(}\sum_{m>\max(i,j,\ell)}\Omega_{mi}(1-\Omega_{mi})\,\,\big{)}^{2}\Omega_{ij}(1-\Omega_{ij})\Omega_{i\ell}(1-\Omega_{i\ell})$
$\displaystyle\quad+64\sum_{i<j}\big{(}\sum_{m>\max(i,j,\ell)}\Omega_{mi}(1-\Omega_{mi})\,\,\big{)}^{2}(1-2\Omega_{ij})^{2}\Omega_{ij}(1-\Omega_{ij})$
$\displaystyle\lesssim n^{2}\cdot C_{n}^{2},$

whence,

$\displaystyle\mathrm{Var}\left(\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{2}|\mathcal{F}_{n,m-1}]\right)$
$\displaystyle\lesssim\frac{n^{2}}{C_{n}^{2}}\asymp\frac{n^{2}}{\alpha^{2}n^{3}}\to
0$

since $\alpha^{2}n\to\infty$. Thus we have shown (F.5) and (F.6), which
together prove (F.3).

Next we prove (F.4), again following the argument in Cammarata & Ke (2022). In
(Cammarata & Ke, 2022, pg.36) it is shown that it suffices to prove

$\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{4}]\xrightarrow{n\to\infty}0.$ (F.9)

Further in (Cammarata & Ke, 2022, pg.37), it is shown that

$\displaystyle\mathbb{E}[C_{n}^{4}X_{n,m}^{4}]=$ $\displaystyle
16\biggl{[}\sum_{i<j}\mathbb{E}[W_{jm}^{4}]\mathbb{E}[(W_{ij}+W_{im})^{4}]$
$\displaystyle+3\sum_{\begin{subarray}{c}i<j,u<v\\\ i\neq u,j\neq
v\end{subarray}}\mathbb{E}[W_{jm}^{2}]\,\mathbb{E}[(W_{ij}+W_{im})^{2}]\,\mathbb{E}[W_{vm}^{2}]\,\mathbb{E}[(W_{uv}+W_{um})^{2}]$
$\displaystyle+3\sum_{\begin{subarray}{c}i<j,v\\\ j\neq
v\end{subarray}}\mathbb{E}[W_{jm}^{2}]\,\mathbb{E}[W_{vm}^{2}]\,\mathbb{E}[(W_{ij}+W_{im})^{2}(W_{iv}+W_{im})^{2}]$
$\displaystyle+3\sum_{\begin{subarray}{c}i,u<j\\\ i\neq
u\end{subarray}}\mathbb{E}[(W_{ij}+W_{im})^{2}]\,\mathbb{E}[(W_{uj}+W_{um})^{2}]\,\mathbb{E}[W_{jm}^{4}]\biggr{]}.$

Going through term by term, we have for $n$ sufficiently large

$\displaystyle\sum_{i<j}\mathbb{E}[W_{jm}^{4}]\mathbb{E}[(W_{ij}+W_{im})^{4}]$
$\displaystyle\lesssim\sum_{i,j}\Omega_{jm}\big{(}\Omega_{ij}+\Omega_{im}\big{)}\lesssim\alpha^{2}n^{2}$

Next

$\displaystyle\sum_{\begin{subarray}{c}i<j,u<v\\\ i\neq u,j\neq
v\end{subarray}}\mathbb{E}[W_{jm}^{2}]\,$
$\displaystyle\mathbb{E}[(W_{ij}+W_{im})^{2}]\,\mathbb{E}[W_{vm}^{2}]\,\mathbb{E}[(W_{ij}+W_{im})^{2}]\lesssim\sum_{ijuv}\Omega_{jm}(\Omega_{ij}+\Omega_{jm})\Omega_{vm}(\Omega_{uv}+\Omega_{um})$
$\displaystyle=\sum_{ijuv}\Omega_{jm}\Omega_{ij}\Omega_{vm}\Omega_{uv}+\sum_{ijuv}\Omega_{jm}\Omega_{ij}\Omega_{vm}\Omega_{um}+\sum_{ijuv}\Omega_{jm}^{2}\Omega_{vm}\Omega_{uv}$
$\displaystyle\quad+\sum_{ijuv}\Omega_{jm}^{2}\Omega_{vm}\Omega_{um}$
$\displaystyle\lesssim\alpha^{4}n^{4}+\alpha^{3}n^{3}$

With a similar argument, we also have, for $n$ sufficiently large,

$\displaystyle\sum_{\begin{subarray}{c}i<j,v\\\ j\neq
v\end{subarray}}\mathbb{E}[W_{jm}^{2}]\,\mathbb{E}[W_{vm}^{2}]\,\mathbb{E}[(W_{ij}+W_{im})^{2}(W_{iv}+W_{im})^{2}]$
$\displaystyle\lesssim\alpha^{2}n^{2}+\alpha^{3}n^{3}$
$\displaystyle\sum_{\begin{subarray}{c}i,u<j\\\ i\neq
u\end{subarray}}\mathbb{E}[(W_{ij}+W_{im})^{2}]\,\mathbb{E}[(W_{uj}+W_{um})^{2}]\,\mathbb{E}[W_{jm}^{4}]\biggr{]}$
$\displaystyle\lesssim\alpha^{3}n^{3}+\alpha^{2}n^{2}.$

Thus

$\displaystyle\sum_{m=1}^{n}\mathbb{E}[X_{n,m}^{4}]\lesssim\frac{\alpha^{4}n^{5}}{C_{n}^{4}}\sim\frac{\alpha^{4}n^{5}}{\alpha^{4}n^{6}}\rightarrow
0,$

which verifies (F.9). Since (F.9) implies (F.4), this completes the proof. ∎

###  Appendix G Proof of Theorem 2.4 (Statistical lower bound)

Let $f_{0}(A)$ be the density under the null hypothesis. Let $\mu(\Pi)$ be the
density of $\Pi$, and let $f_{1}(A|\Pi)$ be the conditional density of $A$
given $\Pi$. The $L_{1}$ distance between two hypotheses is

$\ell^{*}\equiv\frac{1}{2}\mathbb{E}_{A\sim
f_{0}}\bigl{|}\mathbb{E}_{\Pi\sim\mu}L(A,\Pi)-1\bigr{|},\qquad
L(A,\Pi)=f_{1}(A|\Pi)/f_{0}(A).$

Define

${\cal M}=\bigl{\\{}\Pi:\mbox{$\Pi$ is an eligible membership matrix and
$\sum_{i}\pi_{i}(1)\leq 2n\epsilon$}\bigr{\\}}.$ (G.1)

Write $L^{{\cal M}}(A,\Pi)=L(A,\Pi)\cdot 1\\{\Pi\in{\cal M}\\}$ and define
$L^{{\cal M}^{c}}(A,\Pi)$ similarly. By direct calculations, we have

$\displaystyle\ell^{*}$ $\displaystyle=\frac{1}{2}\mathbb{E}_{A\sim
f_{0}}\bigl{|}\mathbb{E}_{\Pi\sim\mu}L^{\cal
M}(A,\Pi)-1+\mathbb{E}_{\Pi\sim\mu}L^{{\cal M}^{c}}(A,\Pi)\bigr{|}$ (G.2)
$\displaystyle\leq\frac{1}{2}\mathbb{E}_{A\sim
f_{0}}\bigl{|}\mathbb{E}_{\Pi\sim\mu}L^{\cal
M}(A,\Pi)-1\bigr{|}+\frac{1}{2}\mathbb{E}_{A\sim
f_{0}}\mathbb{E}_{\Pi\sim\mu}L^{{\cal M}^{c}}(A,\Pi)$ (G.3)
$\displaystyle\equiv\frac{1}{2}\ell_{0}+\frac{1}{2}\ell_{1}.$ (G.4)

Note that $\mathbb{E}_{A\sim f_{0}}\mathbb{E}_{\Pi\sim\mu}L^{{\cal
M}^{c}}(A,\Pi)=\int_{\Pi\in{\cal M}^{c}}f_{1}(A|\Pi)\mu(\Pi)d\Pi
dA=\int_{\Pi\in{\cal M}^{c}}\mu(\Pi)d\Pi=\mu({\cal M}^{c})$. We bound the
probability of $\mu\in{\cal M}^{c}$. Note that $\pi_{i}(1)$ are independent
Bernoulli variables with mean $\epsilon$, where $\epsilon\asymp n^{-1}N$. It
follows by Bernstein inequality that if $t=100\sqrt{N\log N}$, the we have
conservatively,

$\displaystyle\mathbb{P}\Bigl{(}\Bigl{|}\sum_{i}\pi_{i}(1)-N\Bigr{|}>t\Bigr{)}\leq
2\exp\biggl{(}-\frac{t^{2}/2}{n\varepsilon+t/3}\biggr{)}\leq
2\exp\biggl{(}-\frac{100^{2}N(\log N)/2}{200N}\biggr{)}\lesssim N^{-c}=o(1)$
(G.5)

for some $c>0$. It follows that

$\ell_{1}=\mu({\cal M}^{c})=o(1).$ (G.6)

By Cauchy-Schwarz inequality,

$\displaystyle\ell_{0}^{2}$ $\displaystyle\leq\mathbb{E}_{A\sim
f_{0}}\bigl{|}\mathbb{E}_{\Pi\sim\mu}L^{\cal M}(A,\Pi)-1\bigr{|}^{2}$
$\displaystyle=\mathbb{E}_{A\sim f_{0}}\bigl{(}\mathbb{E}_{\Pi\sim\mu}L^{\cal
M}(A,\Pi))^{2}-2\mathbb{E}_{A\sim f_{0}}\mathbb{E}_{\Pi\sim\mu}L^{{\cal
M}}(A,\Pi)+1$ $\displaystyle=\mathbb{E}_{A\sim
f_{0}}\bigl{(}\mathbb{E}_{\Pi\sim\mu}L^{\cal
M}(A,\Pi))^{2}-2\bigl{[}1-\mathbb{E}_{A\sim
f_{0}}\mathbb{E}_{\Pi\sim\mu}L^{{\cal M}^{c}}(A,\Pi)\bigr{]}+1$
$\displaystyle\leq\mathbb{E}_{A\sim
f_{0}}\bigl{(}\mathbb{E}_{\Pi\sim\mu}L^{\cal M}(A,\Pi))^{2}-1+o(1),$

where the third line is from $\mathbb{E}_{A\sim
f_{0}}\mathbb{E}_{\Pi\sim\mu}L(A,\Pi)=1$ and the last line is from (G.6). We
plug it into (G.2) to get

$\ell^{*}\leq\sqrt{\ell_{2}-1}+o(1),\qquad\mbox{where}\quad\ell_{2}\equiv\mathbb{E}_{A\sim
f_{0}}\bigl{(}\mathbb{E}_{\Pi\sim\mu}L^{{\cal M}}(A,\Pi))^{2}.$ (G.7)

It suffices to prove that $\ell_{2}\leq 1+o(1)$.

Below, we study $\ell_{2}$. Let $\widetilde{\Pi}$ be an independent copy of
$\Pi$. Define

$S(A,\Pi,\widetilde{\Pi})=L(A,\Pi)\cdot L(\widetilde{\Pi},A).$

It is easy to see that

$\ell_{2}=\mathbb{E}_{A\sim
f_{0},\Pi,\tilde{\Pi}\sim\mu}\bigl{[}S(A,\Pi,\widetilde{\Pi})\cdot
1\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal M}\\}\bigr{]}.$ (G.8)

Denote by $p_{ij}$ and $q_{ij}(\Pi)$ the values of $\Omega_{ij}$ under the
null and the alternative, respectively. Write
$\delta_{ij}(\Pi)=(q_{ij}(\Pi)-p_{ij})/p_{ij}$. By definition,

$S(A,\Pi,\widetilde{\Pi})=\prod_{i<j}\left[\frac{q_{ij}(\Pi)q_{ij}(\widetilde{\Pi})}{p_{ij}^{2}}\right]^{A_{ij}}\left[\frac{(1-q_{ij}(\Pi))(1-q_{ij}(\widetilde{\Pi}))}{(1-p_{ij})^{2}}\right]^{1-A_{ij}}.$

Write for short $q_{ij}(\Pi)=q_{ij}$,
$q_{ij}(\widetilde{\Pi})=\tilde{q}_{ij}$, $\delta_{ij}(\Pi)=\delta_{ij}$ and
$\delta_{ij}(\widetilde{\Pi})=\tilde{\delta}_{ij}$. By straightforward
calculations, we have the following claims:

$\mathbb{E}_{A\sim
f_{0}}[S(A,\Pi,\widetilde{\Pi})]=\prod_{i<j}\Bigl{(}1+\frac{p_{ij}\delta_{ij}\tilde{\delta}_{ij}}{1-p_{ij}}\Bigr{)},$
(G.9)

and

$\displaystyle\ln S(A,\Pi,\widetilde{\Pi})$
$\displaystyle=\sum_{i<j}A_{ij}\ln\biggl{[}\frac{(1+\delta_{ij})(1+\tilde{\delta}_{ij})}{(1-\frac{p_{ij}}{1-p_{ij}}\delta_{ij})(1-\frac{p_{ij}}{1-p_{ij}}\tilde{\delta}_{ij})}\biggr{]}$
(G.10)
$\displaystyle\qquad+\ln\biggl{[}\Bigl{(}1-\frac{p_{ij}}{1-p_{ij}}\delta_{ij}\Bigr{)}\Bigl{(}1-\frac{p_{ij}}{1-p_{ij}}\tilde{\delta}_{ij}\Bigr{)}\biggr{]}.$
(G.11)

The expression (G.10) may be useful for the case of $Nc\to 0$. In the current
case of $Nc\to\infty$, we use (G.9). It follows from (G.8) that

$\displaystyle\ell_{2}$
$\displaystyle=\mathbb{E}_{\Pi,\tilde{\Pi}\sim\mu}\biggl{[}\prod_{i<j}\Bigl{(}1+\frac{p_{ij}\delta_{ij}\tilde{\delta}_{ij}}{1-p_{ij}}\Bigr{)}\cdot
1\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal M}\\}\biggr{]}$ (G.12)
$\displaystyle=\mathbb{E}_{\Pi,\tilde{\Pi}\sim\mu}\biggl{[}\exp\biggl{(}\sum_{i<j}\ln\Bigl{(}1+\frac{p_{ij}\delta_{ij}\tilde{\delta}_{ij}}{1-p_{ij}}\Bigr{)}\biggr{)}\cdot
1\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal M}\\}\biggr{]}$ (G.13)
$\displaystyle\leq\mathbb{E}_{\Pi,\tilde{\Pi}\sim\mu}\biggl{[}\exp(X)\cdot
1\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal
M}\\}\biggr{]},\quad\mbox{with}\;\;X\equiv\sum_{i<j}\frac{p_{ij}\delta_{ij}\tilde{\delta}_{ij}}{1-p_{ij}}.$
(G.14)

where the last line is from the universal inequality of $\ln(1+t)\leq t$.

We further work out the explicit expressions of $p_{ij}$, $\delta_{ij}$ and
$\tilde{\delta}_{ij}$. Let $h=(\epsilon,1-\epsilon)^{\prime}$, and recall that
$\alpha_{0}=a\epsilon+b(1-\epsilon)$. The condition of $b$ in (H.1) guarantees
that

$Ph=\alpha_{0}{\bf 1}_{2},\qquad\alpha_{0}=a\epsilon+b(1-\epsilon).$

By direct calculations,

$\alpha_{0}=\frac{c(1-\epsilon)^{2}-a\epsilon^{2}}{1-2\epsilon}.$ (G.15)

It follows that

$P=\alpha_{0}{\bf 1}_{2}{\bf 1}_{2}^{\prime}+M,\qquad\mbox{where}\quad
M=\frac{a-c}{1-2\epsilon}\xi\xi^{\prime},\quad\xi=(1-\epsilon,-\epsilon)^{\prime}.$
(G.16)

Write $z_{i}=\pi_{i}-h$. Since $Ph=\alpha_{0}{\bf 1}_{2}$ and
$z_{i}^{\prime}{\bf 1}_{2}=0$, we have

$\displaystyle\Omega_{ij}$
$\displaystyle=\theta_{j}\theta_{j}(h+z_{i})^{\prime}P(h+z_{i})$
$\displaystyle=\theta_{i}\theta_{j}(h^{\prime}Ph+z_{i}^{\prime}Pz_{j})$
$\displaystyle=\theta_{i}\theta_{j}(\alpha_{0}+z_{i}^{\prime}Pz_{j})$
$\displaystyle=\theta_{i}\theta_{j}(\alpha_{0}+z_{i}^{\prime}Mz_{j})$
$\displaystyle=\theta_{i}\theta_{j}\Bigl{[}\alpha_{0}+\frac{a-c}{1-2\epsilon}(\xi^{\prime}z_{i})(\xi^{\prime}z_{j})\Bigr{]}.$

Let $t_{i}$ be the indicator that node $i$ belongs to the first community and
write $u_{i}=t_{i}-\frac{N}{n}$. Then, $\pi_{i}=(t_{i},1-t_{i})$ and
$z_{i}=u_{i}(1,-1)^{\prime}$. It follows that $\xi^{\prime}z_{i}=u_{i}$.
Therefore,

$\Omega_{ij}=\theta_{i}\theta_{j}\Bigl{[}\alpha_{0}+\frac{a-c}{1-2\epsilon}u_{i}u_{j}\Bigr{]},\qquad\mbox{where}\quad
u_{i}\overset{iid}{\sim}\mathrm{Bernoulli}(\epsilon)-\epsilon.$ (G.17)

Consequently,

$p_{ij}=\alpha_{0}\theta_{i}\theta_{j},\qquad\delta_{ij}(\Pi)=\frac{a-c}{(1-2\epsilon)\alpha_{0}}u_{i}u_{j}.$

We plug it into (G.12) to obtain

$X=\sum_{i<j}\frac{\theta_{i}\theta_{j}}{1-\alpha_{0}\theta_{i}\theta_{j}}\frac{(a-c)^{2}}{(1-2\epsilon)^{2}\alpha_{0}}u_{i}u_{j}\tilde{u}_{i}\tilde{u}_{j}.$
(G.18)

Below, we use (G.18) to bound $\ell^{2}$. Since
$\alpha_{0}\theta_{\max}^{2}=O(c\theta_{\max}^{2})=o(1)$, by Taylor expansion
of $(1-\alpha_{0}\theta_{i}\theta_{j})^{-1}$, we have

$X=\frac{(a-c)^{2}}{(1-2\epsilon)^{2}\alpha_{0}}\sum_{i<j}\sum_{s=1}^{\infty}\alpha_{0}^{s-1}\theta_{i}^{s}\theta_{j}^{s}u_{i}u_{j}\tilde{u}_{i}\tilde{u}_{j}.$

Let $b_{i}=\theta_{i}\theta_{\max}^{-1}<1$. We re-write $X$ as

$X=\gamma\sum_{s=1}^{\infty}w_{s}X_{s},$

where

$\displaystyle\gamma=\frac{\theta_{\max}^{2}(a-c)^{2}}{(1-\alpha_{0}\theta_{\max}^{2})(1-2\epsilon)^{2}\alpha_{0}},\;\;w_{s}=(1-\alpha_{0}\theta_{\max}^{2})\alpha_{0}^{s-1}\theta_{\max}^{2s-2},\;\;\text{
and }X_{s}=\sum_{i<j}b_{i}^{s}b_{j}^{s}u_{i}u_{j}\tilde{u}_{i}\tilde{u}_{j}.$
(G.19)

Let $\check{\mathbb{E}}$ be the conditional expectation by conditioning on the
event of $\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal M}\\}$. It follows from
(G.12) that

$\displaystyle\ell_{2}$ $\displaystyle=\mathbb{P}(\Pi\in{\cal
M},\widetilde{\Pi}\in{\cal M})\cdot\check{\mathbb{E}}[\exp(X)]$ (G.20)
$\displaystyle=\mathbb{P}(\Pi\in{\cal M},\widetilde{\Pi}\in{\cal
M})\cdot\check{\mathbb{E}}\Bigl{[}\exp\Bigl{(}\gamma\sum_{s=1}^{\infty}w_{s}X_{s}\Bigr{)}\Bigr{]}$
(G.21) $\displaystyle\leq\mathbb{P}(\Pi\in{\cal M},\widetilde{\Pi}\in{\cal
M})\cdot\sum_{s=1}^{\infty}w_{s}\check{\mathbb{E}}[\exp(\gamma X_{s})]$ (G.22)
$\displaystyle=\sum_{s=1}^{\infty}w_{s}\;\mathbb{E}\bigl{[}\exp(\gamma
X_{s})\cdot 1\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal M}\\}\bigr{]}.$ (G.23)

The third line follows using Jensen’s inequality and that $\sum_{s\geq
1}w_{s}=1$.

It suffices to bound the term in (G.20) for each $s\geq 1$. Note that

$X_{s}\leq Y_{s}^{2},\qquad Y_{s}=\sum_{i}b_{i}^{s}u_{i}\tilde{u}_{i}.$ (G.24)

We recall that $u_{i}=t_{i}-\epsilon$, where $t_{i}=\pi_{i}(1)\in\\{0,1\\}$.
The event $\\{\Pi\in{\cal M},\widetilde{\Pi}\in{\cal M}\\}$ translates to
$\max\\{\sum_{i}t_{i},\;\sum_{i}\tilde{t}_{i}\\}\leq 2n\epsilon$. Note that

$u_{i}\tilde{u}_{i}=\begin{cases}(1-\epsilon)^{2},&\mbox{when
}t_{i}+\tilde{t}_{i}=2,\cr-\epsilon(1-\epsilon),&\mbox{when
}t_{i}+\tilde{t}_{i}=1,\cr\epsilon^{2},&\mbox{where
}t_{i}+\tilde{t}_{i}=0.\end{cases}$

It follows that
$|u_{i}\tilde{u}_{i}|\leq(t_{i}+\tilde{t}_{i})/2+\epsilon^{2}$. Note that
$\epsilon=O(N/n)$. Therefore, on this event,

$|Y_{s}|\leq\sum_{i}[(t_{i}+\tilde{t}_{i})/2+\epsilon^{2}]\leq
2n\epsilon+n\epsilon^{2}\leq 3N.$

We immediately have

$\mathbb{E}\bigl{[}\exp(\gamma X_{s})\cdot 1\\{\Pi\in{\cal
M},\widetilde{\Pi}\in{\cal M}\\}\bigr{]}\leq\mathbb{E}\Biggl{[}\exp(\gamma
Y_{s}^{2})\cdot 1\\{|Y_{s}|\leq 3N\\}\Biggr{]}.$ (G.25)

The following lemma is useful.

######  Lemma G.1.

Let $Z$ be a random variable satisfying that

$\mathbb{P}(|Z|>t)\leq
2\exp\Bigl{(}-\frac{t^{2}/2}{\sigma^{2}+bt}\Bigr{)},\qquad\mbox{for all
$t>0$}.$

Then, for any $\gamma>0$ and $B>0$ such that $\gamma(\sigma^{2}+bB)<1/2$, we
have

$\mathbb{E}\bigl{[}\exp(\gamma Z^{2})1\\{|Z|\leq B\\}\bigr{]}\leq
1+\frac{4\gamma(\sigma^{2}+bB)}{1-2\gamma(\sigma^{2}+bB)}.$

Note that $Y_{s}=\sum_{i}b_{i}^{s}u_{i}\tilde{u}_{i}$ is a sum of independent,
mean-zero variables, where $|b_{i}^{s}u_{i}\tilde{u}_{i}|\leq 2$ and
$\sum_{i}\mathrm{Var}(b_{i}^{s}u_{i}\tilde{u}_{i})\leq\sum_{i}b_{i}^{2s}2\epsilon^{2}\leq
2n\epsilon^{2}$. It follows from Bernstein’s inequality that

$\mathbb{P}(|Y_{s}|>t)\leq\exp\biggl{(}-\frac{t^{2}/2}{2n\epsilon^{2}+2t}\biggr{)},\qquad\mbox{for
all }t>0.$

To apply Lemma G.1, we set

$\displaystyle b$ $\displaystyle=2,\qquad\sigma^{2}=2n\epsilon^{2}\leq
2n^{-1}N^{2},\qquad Z=Y_{s},\qquad B=3N,$

and $\gamma$ as in (G.19). The choice of $B$ is in light of (G.25).
Furthermore, by (G.15), we have $\alpha_{0}\asymp c$. Also we have
$\theta_{\max}^{2}\alpha_{0}\to 0$. Hence,

$\gamma=\frac{\theta_{\max}^{2}(a-c)^{2}}{(1-\alpha_{0}\theta_{\max}^{2})(1-2\epsilon)^{2}\alpha_{0}}\leq
C\cdot\big{(}\frac{\theta_{\max}^{2}(a-c)^{2}}{c}\big{)}.$

Thus by the hypothesis $\frac{\theta_{\max}^{2}N(a-c)^{2}}{c}\to 0$, it holds
that $\gamma(\sigma^{2}+bB)<1/2$ for $n$ sufficiently large. Applying Lemma
G.1, we obtain

$\displaystyle\mathbb{E}\bigl{[}\exp(\gamma X_{s})\cdot 1\\{\Pi\in{\cal
M},\widetilde{\Pi}\in{\cal M}\\}\bigr{]}$ $\displaystyle\leq
1+C(\gamma(\sigma^{2}+bB))$ $\displaystyle\leq
1+C\cdot\big{(}\frac{\theta_{\max}^{2}N(a-c)^{2}}{c}\big{)}$

We further plug it into (G.20) to get

$\displaystyle\ell_{2}$
$\displaystyle\leq\sum_{s=1}^{\infty}w_{s}\Bigl{[}1+C\cdot\big{(}\frac{\theta_{\max}^{2}N(a-c)^{2}}{c}\big{)}\Bigr{]}\leq
1+\big{(}\frac{\theta_{\max}^{2}N(a-c)^{2}}{c}\big{)},$

where we use that $\sum w_{s}=1$.

It follows immediately that

$\ell_{2}\leq
1+o(1),\qquad\mbox{if}\quad\theta_{\max}\frac{\sqrt{N}(a-c)}{\sqrt{c}}\to 0.$

This proves the claim. ∎

####  G.1 Proof of Lemma G.1

Let $X$ denote a nonnegative random variable, and define
$\overline{F}(x)=\mathbb{P}_{X}[X\geq x]$. For any positive number $\beta>0$,
we have

$\displaystyle\mathbb{E}[\exp(\gamma X)1\\{X<\beta\\}]$
$\displaystyle=\int_{0}^{\beta}e^{\gamma x}\,\mathrm{d}\mathbb{P}_{X}(x)$
$\displaystyle=-e^{\gamma
x}\bar{F}(x)\bigg{|}_{0}^{\beta}+\int_{0}^{\beta}\gamma e^{\gamma
x}\bar{F}(x)dx$
$\displaystyle=1-e^{\gamma\beta}\bar{F}(\beta)+\int_{0}^{\beta}\gamma
e^{\gamma x}\bar{F}(x)dx$ $\displaystyle\leq 1+\int_{0}^{\beta}\gamma
e^{\gamma x}\bar{F}(x)dx.$

We apply it to $X=Z^{2}$ and $\beta=B^{2}$ to get

$\displaystyle\mathbb{E}\bigl{[}\exp(\gamma Z^{2})1\\{|Z|\leq B\\}\bigr{]}$
$\displaystyle\leq 1+\int_{0}^{B^{2}}\gamma\exp(\gamma
x)\mathbb{P}(|Z|>\sqrt{x})dx$ $\displaystyle\leq
1+2\gamma\int_{0}^{B^{2}}\exp(\gamma
x)\exp\biggl{\\{}-\frac{x}{2(\sigma^{2}+b\sqrt{x})}\biggr{\\}}dx$
$\displaystyle\leq 1+2\gamma\int_{0}^{B^{2}}\exp(\gamma
x)\exp\biggl{\\{}-\frac{x}{2(\sigma^{2}+bB)}\biggr{\\}}dx$ $\displaystyle\leq
1+2\gamma\int_{0}^{\infty}\exp\biggl{\\{}-\frac{1-2\gamma(\sigma^{2}+bB)}{2(\sigma^{2}+bB)}x\biggr{\\}}dx$
$\displaystyle\leq 1+\frac{4\gamma(\sigma^{2}+bB)}{1-2\gamma(\sigma^{2}+bB)}.$

This proves the claim. ∎

###  Appendix H Proof of Theorem 2.5 (Tightness of the statistical lower
bound)

Let $\rho\in\mathbb{R}^{n}$. We consider the global testing problem in the
DCBM model where

  1. _A_)

$P=\begin{pmatrix}1&b\\\ b&1\end{pmatrix}$

  2. _B_)

$b=\tilde{b}/\sqrt{ac}$,

  3. _C_)

$\theta_{i}=\rho_{i}\sqrt{a}$ for $i\in S$,

  4. _D_)

$\theta_{i}=\rho_{i}\sqrt{c}$ for $i\notin S$, and

  5. _E_)

$aN_{0}+\tilde{b}(n-N_{0})=\tilde{b}N_{0}+c(n-N_{0})$,

Recall that $h=(N_{0}/n,1-N_{0}/n)^{\mathsf{T}}$, and $N_{0}$ is the size of
the smaller community in the alternative. Observe that the null model $K=1$ is
parameterized by setting $a=c=\tilde{b}=1$.

Recall that $\varepsilon=N/n$. We define

$\displaystyle\alpha_{0}\equiv\frac{aN_{0}+\tilde{b}(n-N_{0})}{n}.$

Note that by Assumption (_E_),

$\displaystyle\tilde{b}$ $\displaystyle=\frac{nc-(a+c)N_{0}}{n-2N_{0}}$ (H.1)
$\displaystyle a\epsilon$ $\displaystyle=O(c),\text{ and }$ (H.2)
$\displaystyle c$ $\displaystyle\sim\tilde{b}\sim\alpha_{0}.$ (H.3)

Our assumptions in this section are the following:

  1. _a_)

There exists an absolute constant $C_{\rho}>0$ such that $\rho_{\max}\leq
C_{\rho}\,\rho_{\min}$

  2. _b_)

$\frac{\rho_{\max}^{2}\alpha_{0}n}{\sqrt{\log n}}\to\infty$

  3. _c_)

An integer $N$ is known such that $N_{0}=N[1+o(1)]$.

Note that since we tolerate a small error in the clique size by Assumption
(_c_), our setting indeed matches that of the statistical lower bound, by
(G.5).

Define the signed scan statistic

$\displaystyle\phi_{sc}=\max_{D\subset[n]:|D|=N}\mathbf{1}^{\prime}_{D}\big{(}A-\hat{\eta}\hat{\eta}^{\mathsf{T}}\big{)}\mathbf{1}_{D}.$
(H.4)

For notational brevity, define $n^{(2)}=\binom{n}{2}$. Let

$\hat{\gamma}=\frac{1}{n^{(2)}}\sum_{i,j}A_{ij}.$

The estimator $\hat{\gamma}$ provides a constant factor approximation of the
edge density of the least-favorable null model. See Lemma H.1 for further
details.

Next let

$\displaystyle h(u)=(1+u)\log(1+u)-u,$ (H.5)

and note that this function is strictly increasing on $\mathbb{R}_{\geq 0}$.
Define a random threshold $\hat{\tau}$ to be

$\displaystyle\hat{\tau}=C^{*}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{C^{*}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}$
(H.6)

Let $C^{*}>0$ denote a sufficiently large constant, to be determined, that
depends only on $C_{\rho}$ from Assumption (_a_). Finally define the scan test
to be

$\displaystyle\varphi_{sc}=\mathbf{1}\big{[}|\phi_{sc}|>\hat{\tau}\big{]}$

Note that, if we assume $a\geq c$, as in the main text, then $b<1$. In this
case, we can simply take

$\displaystyle\varphi_{sc}=\mathbf{1}\big{[}\phi_{sc}>\hat{\tau}\big{]},$

and the same guarantees hold. On the other hand, if $b>1$, then the scan test
skews negative, as our proof shows.

######  Theorem H.1.

If

$\displaystyle
h\bigg{(}\frac{\|\theta_{S}\|_{1}^{2}|1-b^{2}|}{\rho_{\max}^{2}\alpha_{0}N_{0}^{2}}\bigg{)}\gg\frac{\log\frac{ne}{N_{0}}}{\rho_{\max}^{2}\alpha_{0}N_{0}},$
(H.7)

then the type 1 and 2 error of $\varphi_{sc}$ tend to $0$ as $n\to\infty$.

We interpret the previous result in the following concrete settings.

######  Corollary H.1.

If

$\frac{\rho_{\max}^{2}\alpha_{0}N_{0}}{\log\frac{ne}{N_{0}}}\to 0,$

then $\varphi_{sc}$ has type 1 and 2 errors tending to $0$ as $n\to\infty$,
provided that

$\frac{\rho_{\max}^{2}N_{0}(a-c)}{\log\frac{ne}{N_{0}}}\gg 1.$

If

$\frac{\rho_{\max}^{2}\alpha_{0}N_{0}}{\log\frac{ne}{N_{0}}}\to\infty,$

then $\varphi_{sc}$ has type 1 and 2 errors tending to $0$ as $n\to\infty$,
provided that

$\frac{\rho_{\max}^{2}N_{0}(a-c)}{\sqrt{\rho_{\max}^{2}N_{0}\alpha_{0}\log\frac{ne}{N_{0}}}}\gg
1.$

###### Proof.

Note that

$\|\theta_{S}\|_{1}^{2}|1-b^{2}|=\rho_{\max}^{2}N_{0}^{2}(a-\tilde{b}^{2}/\sqrt{c})\sim\rho_{\max}^{2}N_{0}^{2}(a-c).$

In the first case,

$h\bigg{(}\frac{\|\theta_{S}\|_{1}^{2}|1-b^{2}|}{\rho_{\max}^{2}\alpha_{0}N_{0}^{2}}\bigg{)}\gg
h\bigg{(}\frac{\log\frac{ne}{N_{0}}}{\rho_{\max}^{2}\alpha_{0}N_{0}}\bigg{)}\gtrsim\frac{\log\frac{ne}{N_{0}}}{\rho_{\max}^{2}\alpha_{0}N_{0}}.$

We use the fact that $h(u)\gtrsim u$ for $u\geq 1$.

In the second case,

$\displaystyle
h\bigg{(}\frac{\|\theta_{S}\|_{1}^{2}|1-b^{2}|}{\rho_{\max}^{2}\alpha_{0}N_{0}^{2}}\bigg{)}$
$\displaystyle\gg
h\bigg{(}\frac{N_{0}\cdot\sqrt{\rho_{\max}^{2}N_{0}\alpha_{0}\log\frac{ne}{N_{0}}}}{\rho_{\max}^{2}\alpha_{0}N_{0}^{2}}\bigg{)}=h\bigg{(}\sqrt{\frac{\log\frac{ne}{N_{0}}}{\rho_{\max}^{2}\alpha_{0}N_{0}}}\bigg{)}\gtrsim\frac{\log\frac{ne}{N_{0}}}{\rho_{\max}^{2}\alpha_{0}N_{0}}.$

∎

The upper bounds in the second part of Corollary H.1 is the best possible up
to logarithmic factors. For example, suppose that
$\theta_{\max}\lesssim\theta_{\min}$ in Theorem 2.4. Then the upper bound for
the second case of Corollary H.1 matches the lower bound of Theorem 2.4 up to
logarithmic factors.

To prove Theorem 2.5, first we establish concentration of $\hat{\gamma}$.

######  Lemma H.1.

Recall

$\displaystyle\hat{\gamma}=\frac{1}{n^{(2)}}\sum_{i,j(dist)}A_{ij}.$

There exists an absolute constant $C>0$ such that for all $\delta>0$, it holds
that

$\displaystyle|\hat{\gamma}-\mathbb{E}\hat{\gamma}|\leq\frac{C\sqrt{\rho_{\max}^{2}\alpha_{0}\log(1/\delta)}}{n}$

with probability at least $1-\delta$.

###### Proof.

As a preliminary, we claim that

$\displaystyle(\Omega\mathbf{1})_{i}\asymp\rho_{\max}^{2}\alpha_{0}n.$ (H.8)

To see this, note that if $i\in S$, then by (_E_)

$\displaystyle(\Omega\mathbf{1})_{i}$
$\displaystyle=\sum_{j}\Omega_{ij}=\theta_{i}(\|\theta_{S}\|_{1}+b\|\theta_{S^{c}}\|_{1})$
$\displaystyle\asymp\rho_{\max}\sqrt{a}\cdot\big{(}\sqrt{a}N\rho_{\max}+\frac{\tilde{b}}{\sqrt{ac}}\cdot\sqrt{c}\rho_{\max}\big{)}=\rho_{\max}^{2}\alpha_{0}n.$

The claim for $i\notin S$ follows by a similar argument applying (_E_). It
follows that

$\displaystyle
v_{0}=\mathbf{1}^{\mathsf{T}}\Omega\mathbf{1}\asymp\rho_{\max}^{2}\alpha_{0}n^{2}$

The expectation is

$\displaystyle\mathbb{E}\hat{\gamma}=\frac{1}{n^{(2)}}\sum_{i,j(dist)}\Omega_{ij},$

and the variance is

$\displaystyle\mathrm{Var}(\hat{\gamma})=\frac{1}{(n^{(2)})^{2}}\sum_{i,j(dist)}\Omega_{ij}(1-\Omega_{ij}).$

By Bernstein’s inequality,

$\displaystyle\mathbb{P}\big{[}n^{(2)}\big{|}\hat{\gamma}-\mathbb{E}\hat{\gamma}\big{|}>t\big{]}\leq
2\exp\bigg{(}-\frac{ct^{2}}{\sum_{i,j(dist)}\Omega_{ij}+t}\bigg{)}.$ (H.9)

By Assumptions (_a_) and (_b_),

$\displaystyle\sum_{i,j(dist)}\Omega_{ij}\asymp\rho_{\max}^{2}\alpha_{0}n^{2}\gg
n.$

Setting

$t=\tau\equiv C\sqrt{\rho_{\max}^{2}\alpha_{0}n^{2}\log(1/\delta)}$

for a large enough absolute constant $C>0$, (H.9) implies that

$|\hat{\gamma}-\mathbb{E}\hat{\gamma}|\leq\frac{\tau}{n^{2}}\asymp\frac{\sqrt{\rho_{\max}^{2}\alpha_{0}\log(1/\delta})}{n}$

with probability at least $1-\delta$. ∎

Next we control the error arising from the plug-in effect of approximating
$\eta^{*}$ by $\hat{\eta}$.

######  Lemma H.2.

Given $D\subset[n]$, define

$L_{D}\equiv\mathbf{1}^{\mathsf{T}}_{D}(\eta^{*}\eta^{*\mathsf{T}}-\hat{\eta}\hat{\eta}^{\mathsf{T}})\mathbf{1}_{D}.$

Then under the null and alternative hypothesis,

$\displaystyle\max_{|D|=N}|L_{D}|\lesssim\sqrt{N_{0}^{3}\rho_{\max}^{2}\alpha_{0}\log(\frac{ne}{N_{0}})}$

with probability at least $1-\binom{n}{N}^{-1}-2v_{0}^{-c_{1}}$, for an
absolute constant $c_{1}>0$.

###### Proof.

In this proof, $c>0$ is an absolute constant that may vary from line to line.

Given $D\subset[n]$, let

$\displaystyle
L_{D}\equiv\mathbf{1}^{\mathsf{T}}_{D}(\eta^{*}\eta^{*\mathsf{T}}-\hat{\eta}\hat{\eta}^{\mathsf{T}})\mathbf{1}_{D}=\mathbf{1}^{\mathsf{T}}_{D}\eta^{*}(\eta^{*}-\hat{\eta})^{\mathsf{T}}\mathbf{1}_{D}+\mathbf{1}^{\mathsf{T}}_{D}(\eta^{*}-\hat{\eta})\hat{\eta}^{\mathsf{T}}\mathbf{1}_{D}$
(H.10)

Our first goal is to control

$\displaystyle\big{|}\mathbf{1}_{D}^{\mathsf{T}}(\hat{\eta}-\eta^{*})\big{|}.$

Define $\overline{\Omega}=\Omega-\mathrm{diag}(\Omega)$. Note that

$\displaystyle\hat{\eta}-\eta^{*}$
$\displaystyle=\frac{A\mathbf{1}}{\sqrt{V}}-\frac{\Omega\mathbf{1}}{\sqrt{v_{0}}}=\big{(}\frac{A\mathbf{1}}{\sqrt{V}}-\frac{A\mathbf{1}}{\sqrt{v_{0}}}\big{)}+\big{(}\frac{A\mathbf{1}}{\sqrt{v_{0}}}-\frac{\overline{\Omega}\mathbf{1}}{\sqrt{v_{0}}}\big{)}+\big{(}\frac{\overline{\Omega}\mathbf{1}}{\sqrt{v_{0}}}-\frac{\Omega\mathbf{1}}{\sqrt{v_{0}}}\big{)}$
(H.11)

We study each term of (H.11). First note that

$\displaystyle(\overline{\Omega}\mathbf{1})_{i}=(\Omega\mathbf{1})_{i}-\Omega_{ii}=\rho_{\max}^{2}\alpha_{0}n+O(1),$

and thus

$\displaystyle v_{0}=\sum_{i}(\Omega\mathbf{1})_{i}$
$\displaystyle\sim\sum_{i}(\overline{\Omega}\mathbf{1})_{i}=v,\text{ and}$
$\displaystyle|v_{0}-v|$ $\displaystyle\lesssim 1$ (H.12)

Next note that

$\displaystyle\mathrm{Var}\big{(}\mathbf{1}_{D}^{\mathsf{T}}\big{(}A\mathbf{1}-\overline{\Omega}\mathbf{1}\big{)}\big{)}$
$\displaystyle\lesssim\sum_{\begin{subarray}{c}i\in[n],j\in D\\\ i\neq
j\end{subarray}}\Omega_{ij}\lesssim|D|\rho_{\max}^{2}\alpha_{0}n.$

By Bernstein’s inequality,

$\displaystyle\mathbb{P}\big{[}\big{|}\mathbf{1}_{D}^{\mathsf{T}}\big{(}A\mathbf{1}-\overline{\Omega}\mathbf{1}\big{)}\big{|}\geq
t\big{]}\leq
2\exp\bigg{(}-\frac{ct^{2}}{|D|\rho_{\max}^{2}\alpha_{0}n+t}\bigg{)}$ (H.13)

for all $t>0$. Setting

$t=\tau\equiv\sqrt{4/c}\cdot\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)},$

we have

$\displaystyle\frac{1}{\sqrt{v_{0}}}\big{|}\mathbf{1}_{D}^{\mathsf{T}}\big{(}A\mathbf{1}-\overline{\Omega}\mathbf{1}\big{)}\big{|}\lesssim\frac{\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}}{\sqrt{\rho_{\max}^{2}\alpha_{0}n^{2}}}=\sqrt{(|D|/n)\cdot\log(1/\delta)}$
(H.14)

with probability at least $1-\delta$.

Next, it is shown in (Jin et al., 2021c, Supplement, pg.100) that for
$\sqrt{\log\|\theta\|_{1}}\ll x_{n}\ll\|\theta\|_{1}$,

$\displaystyle\mathbb{P}\big{[}|V-v|>x_{n}\|\theta\|_{1}\big{]}=\mathbb{P}\bigg{[}|\sqrt{V}-\sqrt{v}|>\frac{x_{n}\|\theta\|_{1}}{\sqrt{V}+\sqrt{v}}\bigg{]}\leq
2\exp(-cx_{n}^{2}).$

Hence

$\displaystyle\mathbb{P}\bigg{[}|\sqrt{V}-\sqrt{v}|>\frac{x_{n}\|\theta\|_{1}}{\sqrt{v}}\bigg{]}\leq
2\exp(-cx_{n}^{2}),$

Note that by (H.2) and (H.3),

$\displaystyle\frac{\|\theta\|_{1}}{\sqrt{v}}\asymp\frac{N_{0}\rho_{\max}\sqrt{a}+(n-N_{0})\rho_{\max}\sqrt{c}}{\rho_{\max}\sqrt{\alpha_{0}}n}\asymp
1.$

By (H.12), we have

$\displaystyle\mathbb{P}\bigg{[}|\sqrt{V}-\sqrt{v_{0}}|>\frac{x_{n}\|\theta\|_{1}}{\sqrt{v}}\bigg{]}\leq
2\exp(-cx_{n}^{2}).$ (H.15)

Hence with probability at least $1-2\exp(-cx_{n}^{2})$,

$V\gtrsim v_{0}.$

It follows that

$\displaystyle\mathbb{P}\bigg{[}\big{|}\frac{1}{\sqrt{V}}-\frac{1}{\sqrt{v_{0}}}\big{|}\geq\frac{x_{n}\|\theta\|_{1}}{v_{0}\sqrt{v}}\bigg{]}$
$\displaystyle=\mathbb{P}\bigg{[}\frac{|\sqrt{V}-\sqrt{v_{0}}|}{\sqrt{V\cdot
v_{0}}}\geq\frac{x_{n}\|\theta\|_{1}}{v_{0}\sqrt{v}}\bigg{]}\leq
2\exp(-cx_{n}^{2}).$

Hence with probability at least $1-\delta-2\exp(-cx_{n}^{2})$,

$\displaystyle\bigg{|}\mathbf{1}_{D}^{\mathsf{T}}(\frac{A\mathbf{1}}{\sqrt{V}}-\frac{A\mathbf{1}}{\sqrt{v_{0}}})\bigg{|}$
$\displaystyle\leq\frac{x_{n}\cdot\big{(}|D|\rho_{\max}^{2}\alpha_{0}n+\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}\big{)}}{v_{0}}$
$\displaystyle\asymp\frac{x_{n}\cdot\big{(}|D|\rho_{\max}^{2}\alpha_{0}n+\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}\big{)}}{\rho_{\max}^{2}\alpha_{0}n^{2}}.$
(H.16)

For the last term of (H.11),

$\displaystyle\mathbf{1}_{D}^{\mathsf{T}}\big{(}\frac{\overline{\Omega}\mathbf{1}}{\sqrt{v_{0}}}-\frac{\Omega\mathbf{1}}{\sqrt{v_{0}}}\big{)}$
$\displaystyle=\frac{\sum_{i\in
D}\Omega_{ii}}{\sqrt{v_{0}}}\asymp\frac{\rho_{\max}^{2}a|D\cap
S|+\rho_{\max}^{2}c|D\cap S^{c}|}{\sqrt{\rho_{\max}^{2}\alpha_{0}n^{2}}}$
$\displaystyle\lesssim\rho_{\max}a\epsilon/\sqrt{\alpha_{0}}\lesssim\rho_{\max}\sqrt{c}\lesssim
1.$ (H.17)

Next we control $\mathbf{1}_{D}^{\mathsf{T}}\hat{\eta}$. By (H.13) and (H.15),

$\displaystyle|\mathbf{1}_{D}^{\mathsf{T}}\hat{\eta}|=\frac{|\mathbf{1}_{D}^{\mathsf{T}}A\mathbf{1}|}{\sqrt{V}}\lesssim\frac{|D|\rho_{\max}^{2}\alpha_{0}n+\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}}{\sqrt{v_{0}}-cx_{n}}$
(H.18)

with probability at least $1-\delta-2\exp(-cx_{n}^{2})$. It also holds that

$\displaystyle|\mathbf{1}_{D}^{\mathsf{T}}\eta^{*}|=\frac{|\mathbf{1}_{D}^{\mathsf{T}}\Omega\mathbf{1}|}{\sqrt{v_{0}}}=\frac{|D|\rho_{\max}^{2}\alpha_{0}n}{\rho_{\max}\sqrt{\alpha_{0}}n}=|D|\rho_{\max}\sqrt{\alpha_{0}}.$
(H.19)

Next we set $x_{n}=\sqrt{\log\|\theta\|_{1}}\asymp\sqrt{\log v_{0}}$. Then
from (H.16) and (H.18),

$\displaystyle\bigg{|}\mathbf{1}_{D}^{\mathsf{T}}(\frac{A\mathbf{1}}{\sqrt{V}}-\frac{A\mathbf{1}}{\sqrt{v_{0}}})\bigg{|}$
$\displaystyle\asymp\frac{\sqrt{\log
v_{0}}\cdot\big{(}|D|\rho_{\max}^{2}\alpha_{0}n+\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}\big{)}}{\rho_{\max}^{2}\alpha_{0}n^{2}}$
$\displaystyle\asymp\sqrt{\log
v_{0}}\cdot\big{(}(|D|/n)+\frac{\sqrt{(|D|/n)\log(1/\delta)}}{\rho_{\max}\sqrt{\alpha_{0}}n}\big{)},$
(H.20)

and

$\displaystyle|\mathbf{1}_{D}^{\mathsf{T}}\hat{\eta}|$
$\displaystyle\lesssim\frac{|D|\rho_{\max}^{2}\alpha_{0}n+\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}}{\sqrt{v_{0}}}$
$\displaystyle\asymp\frac{|D|\rho_{\max}^{2}\alpha_{0}n+\sqrt{|D|\rho_{\max}^{2}\alpha_{0}n\log(1/\delta)}}{\rho_{\max}\sqrt{\alpha_{0}}n}$
$\displaystyle\asymp|D|\rho_{\max}\sqrt{\alpha_{0}}+\sqrt{(|D|/n)\cdot\log(1/\delta)}$
(H.21)

with probability at least $1-\delta-2v_{0}^{-c_{1}}$.

By (H.14),(H.17), (H.19), (H.20), and (H.21)

$\displaystyle|L_{D}|$
$\displaystyle\leq\big{|}\mathbf{1}^{\mathsf{T}}_{D}\eta^{*}(\eta^{*}-\hat{\eta})^{\mathsf{T}}\mathbf{1}_{D}\big{|}+\big{|}\mathbf{1}^{\mathsf{T}}_{D}(\eta^{*}-\hat{\eta})\hat{\eta}^{\mathsf{T}}\mathbf{1}_{D}\big{|}$
$\displaystyle\lesssim\big{(}|D|\rho_{\max}\sqrt{\alpha_{0}}+\sqrt{(|D|/n)\cdot\log(1/\delta)}\big{)}\cdot\big{(}\sqrt{\log
v_{0}}(|D|/n)+\sqrt{(|D|/n)\log(1/\delta)}+1\big{)}.$

with probability at least $1-\delta-2v_{0}^{-c_{1}}$.

It follows that, setting $\delta=1/\binom{n}{N}^{2}$ above and applying the
union bound,

$\displaystyle\max_{|D|=N}|L_{D}|$
$\displaystyle\lesssim\big{(}N\rho_{\max}\sqrt{\alpha_{0}}+\sqrt{N\epsilon\cdot\log(\frac{ne}{N})}\,\big{)}\cdot\big{(}\epsilon\sqrt{\log
v_{0}}+\sqrt{N\epsilon\cdot\log(\frac{ne}{N})}+1\big{)}$

with probability at least $1-\binom{n}{N}^{-1}-2v_{0}^{-c_{1}}\to 1$. Note
that

$\displaystyle\frac{n\log\frac{ne}{N}}{\log v_{0}}$
$\displaystyle\asymp\frac{n\log\frac{ne}{N}}{\log(\rho_{\max}^{2}\alpha_{0}n^{2})}\gtrsim
1\Rightarrow$ $\displaystyle\frac{N^{2}}{n}\log\frac{ne}{N}$
$\displaystyle\gtrsim\frac{N^{2}}{n^{2}}\log(\rho_{\max}^{2}\alpha_{0}n^{2})\Rightarrow$
$\displaystyle\sqrt{N\epsilon\cdot\log(\frac{ne}{N})}$
$\displaystyle\gtrsim\epsilon\sqrt{\log v_{0}}.$

Further, since $(N/n)\log\frac{ne}{N}\ll 1$ and
$\rho_{\max}^{2}\alpha_{0}n\to\infty$ by Assumption (_b_),

$\displaystyle N\log\frac{ne}{N}$
$\displaystyle\lesssim\rho_{\max}^{2}\alpha_{0}n^{2}\Rightarrow$
$\displaystyle\frac{N}{n}\sqrt{\log\frac{ne}{N}}$
$\displaystyle\lesssim\sqrt{N\rho_{\max}^{2}\alpha_{0}}\Rightarrow$
$\displaystyle N\epsilon\log\frac{ne}{N}$
$\displaystyle\lesssim\sqrt{N^{3}\rho_{\max}^{2}\alpha_{0}\log\frac{ne}{N}}.$

Hence

$\displaystyle\max_{|D|=N}|L_{D}|\lesssim\sqrt{N^{3}\rho_{\max}^{2}\alpha_{0}\log(\frac{ne}{N})}+N\epsilon\log(\frac{ne}{N})\lesssim\sqrt{N^{3}\rho_{\max}^{2}\alpha_{0}\log(\frac{ne}{N})}$

with probability at least $1-\binom{n}{N}^{-1}-2v_{0}^{-c_{1}}$. Recalling
that $N=N_{0}[1+o(1)]$ yields the statement of the lemma.

∎

Next we study an ideal version of $\phi_{sc}$.

######  Lemma H.3.

Define the ideal scan statistic

$\tilde{\phi}_{sc}=\max_{|D|=N}\mathbf{1}_{D}^{\mathsf{T}}(A-\eta^{*}\eta^{*\mathsf{T}})\mathbf{1}_{D},$

and corresponding test

$\tilde{\varphi}_{sc}=\mathbf{1}\bigg{[}\tilde{\phi}_{sc}>\tilde{\tau}\bigg{]},$

where

$\tilde{\tau}\equiv\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)},$

and $\tilde{C}>0$ is a sufficiently large absolute constant that depends only
on $C_{\rho}$ from Assumption (_a_). Then under the null hypothesis,

$\displaystyle\mathbb{P}\big{[}|\tilde{\phi}_{sc}|>\tilde{\tau}\big{]}\leq
n^{-c_{0}}+\exp\big{(}-N\log\frac{ne}{N}\big{)}$

and under the alternative hypothesis,

$\displaystyle\mathbb{P}\big{[}|\tilde{\phi}_{sc}|\leq\tilde{\tau}\big{]}\leq
n^{-c_{0}}+\big{(}\frac{N}{ne}\big{)}^{10}$

for $n$ sufficiently large, where $c_{0}$ is an absolute constant.

###### Proof.

In this proof, $c>0$ is an absolute constant that may vary form line to line.

Define the ideal scan statistic

$\tilde{\phi}_{sc}=\max_{|D|=N}\mathbf{1}_{D}^{\mathsf{T}}(A-\eta^{*}\eta^{*\mathsf{T}})\mathbf{1}_{D}.$

Also define

$Z_{D}\equiv\sum_{i,j\in D(dist)}(A_{ij}-\Omega_{ij})$

First consider the type 1 error. Under the null hypothesis, we have
$\eta^{*}=\theta=\rho$ and $\alpha_{0}=1$. Observe that

$\sigma^{2}_{D}\equiv\mathrm{Var}(Z_{D})=\mathrm{Var}\big{(}\sum_{i,j\in
D(dist)}(A_{ij}-\theta_{i}\theta_{j})\big{)}\lesssim\|\theta_{D}\|_{1}^{2}\asymp\rho_{\max}^{2}N^{2}\sim\rho_{\max}^{2}N_{0}^{2}$

By the Bennett inequality, (Vershynin, 2018, Theorem 2.9.2),

$\displaystyle\mathbb{P}\big{[}\sum_{i,j\in
D}(A_{ij}-\theta_{i}\theta_{j})>t\big{]}\leq\exp\bigg{(}-\sigma_{D}^{2}\,h\bigg{(}\frac{t}{\sigma_{D}^{2}}\bigg{)}\bigg{)},$
(H.22)

where $h(u)=(1+u)\log(1+u)-u$.

Next, by Lemma H.1,

$|\hat{\gamma}-\mathbb{E}\hat{\gamma}|\lesssim\frac{\sqrt{\log n}}{n}$

with probability $n^{-c_{0}}$. Also recall that

$\mathbb{E}\,\hat{\gamma}=\frac{1}{n^{(2)}}\sum_{i,j(dist)}\Omega_{ij}\asymp\rho_{\max}^{2}\alpha_{0}=\rho_{\max}^{2}\gg\frac{\sqrt{\log
n}}{n}$

by Assumptions (_a_) and (_b_). It follows that there exist absolute constants
$c_{0},c_{\gamma},C_{\gamma}>0$ such that

$\displaystyle
c_{\gamma}\rho_{\max}^{2}<\hat{\gamma}<C_{\gamma}\rho_{\max}^{2}$ (H.23)

with probability $n^{-c_{0}}$. Let $\mathcal{E}$ denote this event. Under
$\mathcal{E}$, we have that for $\tilde{C}$ sufficiently large,

$\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}\geq\sigma_{D}^{2}h^{-1}\bigg{(}\frac{2N\log\frac{ne}{N}}{\sigma^{2}_{D}}\bigg{)}$

It follows from this, the union bound, and the Bennett inequality,

$\displaystyle\mathbb{P}\bigg{[}|\tilde{\phi}_{sc}|>\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}\bigg{]}$
$\displaystyle\leq\mathbb{P}[\mathcal{E}^{c}]+\mathbb{P}\bigg{[}|\tilde{\phi}_{sc}|>\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)},\,\,\mathcal{E}\bigg{]}$
$\displaystyle\leq
n^{-c_{0}}+\sum_{|D|=N}\mathbb{P}\bigg{[}|Z_{D}|>\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}\bigg{]}$
$\displaystyle\leq
n^{-c_{0}}+\sum_{|D|=N}\mathbb{P}\bigg{[}|Z_{D}|>\sigma_{D}^{2}h^{-1}\bigg{(}\frac{2N\log\frac{ne}{N}}{\sigma^{2}_{D}}\bigg{)}\bigg{]}$
$\displaystyle\leq
n^{-c_{0}}+\big{(}\frac{ne}{N}\big{)}^{N}\exp\big{(}-2N\log\frac{ne}{N}\big{)}.$

This shows that the type 1 error for the ideal scan statistic is $o(1)$.

Next consider the type 2 error. We have by Lemma (E.2),

$\displaystyle\mathbf{1}_{S}^{\mathsf{T}}(A-\eta^{*}\eta^{*\mathsf{T}})\mathbf{1}_{S}$
$\displaystyle=\sum_{i,j\in
S(dist)}(A_{ij}-\Omega_{ij})+\mathbf{1}_{S}^{\mathsf{T}}\tilde{\Omega}\mathbf{1}_{S}=Z_{S}+\|\theta_{S}\|_{1}^{2}(1-b^{2})\cdot\frac{\|\theta_{S^{c}}\|_{1}^{2}}{v_{0}}.$

Note that by (H.12)

$\displaystyle\|\theta_{S}\|_{1}^{2}(1-b^{2})\cdot\frac{\|\theta_{S^{c}}\|^{2}_{1}}{v_{0}}\sim\|\theta_{S}\|_{1}^{2}(1-b^{2}).$

Next,

$\displaystyle\mathrm{Var}(Z_{S})=\sum_{i,j\in
S(dist)}\Omega_{ij}(1-\Omega_{ij})\lesssim\|\theta_{S}\|_{1}^{2}\asymp\rho_{\max}^{2}Na\sim\rho_{\max}^{2}N_{0}a$

By Bernstein’s inequality,

$\displaystyle|Z_{S}|\lesssim\sqrt{\|\theta_{S}\|_{1}^{2}\log(1/\delta)}\vee\log(1/\delta)\leq\|\theta_{S}\|_{1}\log(1/\delta)$

with probability at least $1-\delta$. Setting $\delta=(\frac{N}{ne})^{10}$, we
have

$|Z_{S}|\lesssim\|\theta_{S}\|_{1}\log\big{(}\frac{ne}{N}\big{)}$

with probability at least $1-(\frac{N}{ne})^{10}$.

Next we show that

$\displaystyle\|\theta_{S}\|_{1}|1-b^{2}|\gtrsim\log\frac{ne}{N}$ (H.24)

using (H.7), which we rewrite as

$\displaystyle\|\theta_{S}\|_{1}^{2}|1-b^{2}|\gg\gamma
N_{0}^{2}h^{-1}\bigg{(}\frac{\log\frac{ne}{N_{0}}}{\gamma
N_{0}}\bigg{)}\sim\gamma N^{2}h^{-1}\bigg{(}\frac{\log\frac{ne}{N}}{\gamma
N}\bigg{)}$ (H.25)

where $\gamma=\rho_{\max}^{2}\alpha_{0}$. Recall that $\alpha_{0}=1$ under the
null, and $\alpha_{0}\sim c$ under the alternative. Let

$u=\frac{\log\frac{ne}{N}}{\gamma N}.$

Consider two cases: (i) $u\leq 0.01$, and (ii) $u\geq 0.01$. For
$u^{\prime}\leq h^{-1}(0.01)$, we have $h(u^{\prime})\asymp(u^{\prime})^{2}$,
and therefore $h^{-1}(u)\asymp u^{2}$ for $u\leq 0.01$. In this case (H.25)
implies

$\displaystyle\|\theta_{S}\|_{1}^{2}|1-b^{2}|\gg\gamma
N^{2}\sqrt{\frac{\log\frac{ne}{N}}{\gamma N}}=\sqrt{\gamma
N^{3}\log\frac{ne}{N}}.$

In addition,

$\|\theta_{S}\|_{1}=N\sqrt{a}\rho_{\max},$

so that

$\displaystyle\|\theta_{S}\|_{1}(1-b^{2})\gg\sqrt{\frac{\gamma
N\log\frac{ne}{N}}{a\rho_{\max}^{2}}}\gtrsim\log\frac{ne}{N}$

since $u\leq 0.01$ and $a\rho_{\max}^{2}\lesssim 1$. Thus in case (i), (H.24)
is satisfied for $n$ sufficiently large.

Now consider case (ii) where $u\geq 0.01$. Note that $h(u)\leq(u+1)\log(u+1)$,
and thus

$\frac{1}{2}(u+1)\leq u\leq h^{-1}((u+1)\log(u+1)).$

Let $\varphi\equiv(u+1)\log(u+1)\geq u$ and observe that

$u+1=\frac{\varphi}{\log(u+1)}\geq\frac{\varphi}{\log\varphi}.$

Hence

$h^{-1}((u+1)\log(u+1))\geq\frac{1}{2}\cdot\frac{(u+1)\log(u+1)}{\log\big{[}(u+1)\log(u+1)\big{]}}.$

Applying (H.25),

$\displaystyle\|\theta_{S}\|_{1}^{2}|1-b^{2}|$ $\displaystyle\gg\gamma
N^{2}\cdot\frac{(\frac{\log\frac{ne}{N}}{\gamma
N}+1)\log(\frac{\log\frac{ne}{N}}{\gamma
N}+1)}{\log\big{[}(\frac{\log\frac{ne}{N}}{\gamma
N}+1)\log(\frac{\log\frac{ne}{N}}{\gamma N}+1)\big{]}}\gtrsim
N\log\frac{ne}{N}.$

Hence

$\displaystyle\|\theta_{S}\|_{1}|1-b^{2}|\gg\frac{\log\frac{ne}{N}}{\sqrt{a}\rho_{\max}}\gtrsim\log\frac{ne}{N}.$

Thus in case (ii), (H.24) is also satisfied.

Next we have,

$\displaystyle\mathbb{P}\bigg{[}|\tilde{\phi}_{sc}|\leq\tilde{C}\hat{\gamma}N^{2}$
$\displaystyle
h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}\bigg{]}$
$\displaystyle\leq
n^{-c_{0}}+\mathbb{P}\bigg{[}|\tilde{\phi}_{sc}|\leq\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)},\,\mathcal{E}\bigg{]}$
$\displaystyle\leq
n^{-c_{0}}+\mathbb{P}\bigg{[}\,\,\bigg{|}\|\theta_{S}\|_{1}^{2}(1-b^{2})+Z_{S}\bigg{|}\leq
C\gamma N^{2}h^{-1}\bigg{(}\frac{CN\log(\frac{ne}{N})}{\gamma
N^{2}}\bigg{)}\,\bigg{]}$ $\displaystyle\leq
n^{-c_{0}}+\mathbb{P}\bigg{[}|Z_{S}|\geq\big{|}\|\theta_{S}\|_{1}^{2}(1-b^{2})\big{|}-C\gamma
N^{2}h^{-1}\bigg{(}\frac{CN\log(\frac{ne}{N})}{\gamma N^{2}}\bigg{)}\bigg{]},$

where $C>0$ is a sufficiently large absolute constant. In the second line and
third lines we use the event $\mathcal{E}$ from (H.23), and in the last line
we use the triangle inequality. By (H.7), we have conservatively that

$\big{|}\,\|\theta_{S}\|_{1}^{2}(1-b^{2})\big{|}-C\gamma
N^{2}h^{-1}\bigg{(}\frac{CN\log(\frac{ne}{N})}{\gamma
N^{2}}\bigg{)}\geq\frac{1}{2}\big{|}\|\theta_{S}\|_{1}^{2}(1-b^{2})\big{|}\gg\|\theta_{S}\|_{1}\log\frac{ne}{N}$

for $n$ sufficiently large. Thus for $n$ sufficiently large,

$\displaystyle\mathbb{P}\bigg{[}|\tilde{\phi}_{sc}|\leq\tilde{C}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{\tilde{C}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}\bigg{]}$
$\displaystyle\leq
n^{-c_{0}}+\mathbb{P}\bigg{[}|Z_{S}|\geq\frac{1}{2}\big{|}\,\|\theta_{S}\|_{1}^{2}(1-b^{2})\big{|}\,\bigg{]}$
$\displaystyle\leq n^{-c_{0}}+\big{(}\frac{N}{ne}\big{)}^{10}.$

Therefore the type 2 error for the ideal scan statistic is also $o(1)$. ∎

######  Lemma H.4.

Let $\phi_{sc}$ denote the scan statistic defined in (H.4), and let
$\hat{\tau}$ denote the random threshold defined in (H.6). Then under the null
hypothesis,

$\mathbb{P}\big{[}|\phi_{sc}|>\hat{\tau}\big{]}\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+n^{-c_{0}}+\exp\big{(}-N\log\frac{ne}{N}\big{)},$

and under the alternative hypothesis,for $n$ sufficiently large we have

$\mathbb{P}\big{[}|\phi_{sc}|<\hat{\tau}\big{]}\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+n^{-c_{0}}+\big{(}\frac{N}{ne}\big{)}^{10}.$

###### Proof.

We show that the plug-in effect is negligible compared to the threshold and
signal-strength.

By Lemma H.2,

$\max_{|D|=N}|L_{D}|\lesssim\sqrt{N_{0}^{3}\gamma\log(\frac{ne}{N_{0}})}$

with high probability. Since $h(u)\leq u^{2}$ for $u\geq 0$, it follows that

$\displaystyle
h\bigg{(}\frac{\sqrt{N_{0}^{3}\gamma\log(\frac{ne}{N_{0}})}}{\gamma
N_{0}^{2}}\bigg{)}$
$\displaystyle\leq\frac{N_{0}^{3}\gamma\log(\frac{ne}{N_{0}})}{\gamma^{2}N_{0}^{4}}=\frac{\log\frac{ne}{N_{0}}}{\gamma
N_{0}}\Rightarrow$ $\displaystyle\sqrt{N_{0}^{3}\gamma\log(\frac{ne}{N_{0}})}$
$\displaystyle\leq\gamma
N_{0}^{2}h^{-1}\bigg{(}\frac{\log\frac{ne}{N_{0}}}{\gamma
N_{0}}\bigg{)}\Rightarrow$ $\displaystyle\sqrt{N^{3}\gamma\log(\frac{ne}{N})}$
$\displaystyle\leq[1+o(1)]\gamma
N^{2}h^{-1}\bigg{(}\frac{\log\frac{ne}{N}}{\gamma N}\bigg{)}.$

Under the null, we have by Lemma H.3 that

$\displaystyle\mathbb{P}\big{[}|\phi_{sc}|\geq\hat{\tau}\big{]}$
$\displaystyle\leq\mathbb{P}\big{[}\,|\tilde{\phi}_{sc}|\geq\hat{\tau}-\max_{|D|=N}|L_{D}|\,\big{]}$
$\displaystyle\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+\mathbb{P}\bigg{[}|\tilde{\phi}_{sc}|\geq
C^{*}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{C^{*}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}-\gamma
N^{2}h^{-1}\bigg{(}\frac{\log\frac{ne}{N}}{\gamma N}\bigg{)}\bigg{]}$
$\displaystyle\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+n^{-c_{0}}+\exp\big{(}-N\log\frac{ne}{N}\big{)}$

for $C^{*}>0$ a sufficiently large absolute constant. It suffices to take
$C^{*}\geq 2\tilde{C}$.

Under the alternative hypothesis, we have by Lemma H.3 that

$\displaystyle\mathbb{P}\big{[}|\phi_{sc}|\leq\hat{\tau}\big{]}$
$\displaystyle\leq\mathbb{P}\big{[}\,|\tilde{\phi}_{sc}|\leq\hat{\tau}+\max_{|D|=N}|L_{D}|\,\big{]}$
$\displaystyle\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+\mathbb{P}\bigg{[}\,|\tilde{\phi}_{sc}|\leq
C^{*}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{C^{*}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}+\gamma
N^{2}h^{-1}\bigg{(}\frac{\log\frac{ne}{N}}{\gamma N}\bigg{)}\bigg{]}$
$\displaystyle\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+\mathbb{P}\bigg{[}\,|\tilde{\phi}_{sc}|\leq
2C^{*}\hat{\gamma}N^{2}h^{-1}\bigg{(}\frac{C^{*}N\log(\frac{ne}{N})}{\hat{\gamma}N^{2}}\bigg{)}\bigg{]}$
$\displaystyle\leq\binom{n}{N}^{-1}+v_{0}^{-c_{1}}+n^{-c_{0}}+\big{(}\frac{N}{ne}\big{)}^{10}$

for $n$ sufficiently large.

∎