$\displaystyle\mathbb{P}\left[\left|\sum_{i=1}^{n_{\dagger}}M_{e,u,\bar{u}}^{(i)}-n_{\dagger}\mathbb{E}\left[M_{e,u,\bar{u}}\right]\right|\leq
t\right]$ $\displaystyle\geq
1-2\exp\left(-\frac{t^{2}}{2n_{\dagger}\mathop{\mathrm{Var}}\nolimits\left(M_{e,u,\bar{u}}\right)+\frac{2}{3}Mt}\right).$

Similarly, we find

$\displaystyle t\leq$ $\displaystyle
n_{\dagger}\left(\frac{8}{3n_{\dagger}}\log\frac{4p^{3}}{\delta}+\sqrt{\frac{2}{n_{\dagger}}\mathop{\mathrm{Var}}\nolimits\left(M_{e,u,\bar{u}}\right)\log\frac{4p^{3}}{\delta}}\right)$
(131)

and

$\displaystyle\mathop{\mathrm{Var}}\nolimits\left(M_{e,u,\bar{u}}\right)=$
$\displaystyle
2+\left(1-2q\right)^{4}\left[2\mu_{A}-\mu_{e}^{2}\left(1+\mu_{A}\right)^{2}\right]$
$\displaystyle\leq$ $\displaystyle 2+\left(1-2q\right)^{4}2\mu_{A}$
$\displaystyle=$ $\displaystyle 2\left(1+\mu^{\dagger}_{A}\right).$ (132)

We define
$\epsilon_{\dagger}\triangleq\sqrt{\log\left(2p^{2}/\delta\right)2/n_{\dagger}}$,
then

$\displaystyle t\leq$ $\displaystyle
n_{\dagger}\left(4\epsilon_{\dagger}^{2}+2\epsilon_{\dagger}\sqrt{1+\mu^{\dagger}_{A}}\right)\leq
n_{\dagger}\max\left\\{8\epsilon_{\dagger}^{2},4\epsilon_{\dagger}\sqrt{1+\mu^{\dagger}_{A}}\right\\},$
(133)

which completes the proof.

##  C Recovering strong edges

In Lemma C.1, we define the set of strong edges for the hidden model and show
that the event
$\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)$ defined
in (55) occurs with high probability. That is, only the strong edges are
guaranteed to exist in the estimated structure
$\mathrm{T}^{\text{CL}}_{\dagger}$ We also find a lower bound for the
necessary number of samples for exact structure recovery. In fact we have
$n_{\dagger}\geq n$, as expected. Our bounds coincide with the noiseless case
(Bresler and Karzand, 2018) by setting the noise level $q=0$.

###### Lemma C.1

Fix $\delta\in(0,1)$, and let
$\epsilon_{\dagger}=\sqrt{2\log\left(2p^{2}/\delta\right)/n_{\dagger}}$, for
any $n_{\dagger}>0$. Consider the set of strong edges

$\displaystyle\tau^{\dagger}\triangleq\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-2q\right)^{4}\tanh\beta}}{\left(1-\tanh\beta\right)}\text{
and
}\left\\{\left(i,j\right)\in\mathcal{E}_{\mathrm{T}}:\left|\tanh\theta_{ij}\right|\geq\frac{\tau^{\dagger}}{\left(1-2q\right)^{2}}\right\\}.$
(134)

Then, the Chow-Liu algorithm recovers the strong edges with probability at
least $1-\delta$. In other words, it is true that

$\displaystyle\mathbb{P}\left[\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)\right]\geq
1-2p^{2}\exp\left(-\frac{n_{\dagger}\epsilon_{\dagger}^{2}}{2}\right).$ (135)

Proof  From Lemma B.2, if there is an error then for an edge $f$ not recovered
in the tree $\mathrm{T}^{\text{CL}}_{\dagger}$, we have

$\displaystyle\left(\sum_{i=1}^{n_{\dagger}}Z_{f,u,\bar{u}}^{(i)}\right)\left(\sum_{i=1}^{n_{\dagger}}M_{f,u,\bar{u}}^{(i)}\right)<0$

Therefore one of the sums must be negative. Expanding, one of the two
following inequalities must hold:

$\displaystyle\left|\sum_{i=1}^{n_{\dagger}}Z_{f,u,\bar{u}}^{(i)}-n_{\dagger}\mathbb{E}\left[Z_{f,u,\bar{u}}^{(i)}\right]\right|$
$\displaystyle\geq n_{\dagger}\mathbb{E}\left[Z_{f,u,\bar{u}}^{(i)}\right]$
$\displaystyle\left|\sum_{i=1}^{n_{\dagger}}Y_{f,u,\bar{u}}^{(i)}-n_{\dagger}\mathbb{E}\left[Y_{f,u,\bar{u}}^{(i)}\right]\right|$
$\displaystyle\geq n_{\dagger}\mathbb{E}\left[M_{f,u,\bar{u}}^{(i)}\right].$

In addition, (119), (129), Lemma B.3 and Lemma B.4 give the following pairs of
inequalities:

$\displaystyle\left(1-2q\right)^{2}\mu_{f}\left(1-\mu_{A}\right)$
$\displaystyle\leq\max\left\\{8\epsilon_{\dagger}^{2},4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}\right\\}$
$\displaystyle\left(1-2q\right)^{2}\mu_{f}\left(1+\mu_{A}\right)$
$\displaystyle\leq\max\left\\{8\epsilon_{\dagger}^{2},4\epsilon_{\dagger}\sqrt{1+\mu^{\dagger}_{A}}\right\\}$
$\displaystyle\left|\mu^{\dagger}_{f}\right|$
$\displaystyle\leq\left(1-\mu_{A}\right)^{-1}\max\left\\{8\epsilon_{\dagger}^{2},4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}\right\\}$
$\displaystyle\left|\mu^{\dagger}_{f}\right|$
$\displaystyle\leq\left(1+\mu_{A}\right)^{-1}\max\left\\{8\epsilon_{\dagger}^{2},4\epsilon_{\dagger}\sqrt{1+\mu^{\dagger}_{A}}\right\\}$

Putting these together:

$\displaystyle\left|\mu^{\dagger}_{f}\right|$
$\displaystyle\leq\max\left\\{\frac{8\epsilon_{\dagger}^{2}}{\left(1-\mu_{A}\right)},\frac{8\epsilon_{\dagger}^{2}}{\left(1+\mu_{A}\right)},\frac{4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}}{\left(1-\mu_{A}\right)},\frac{4\epsilon_{\dagger}\sqrt{1+\mu^{\dagger}_{A}}}{\left(1+\mu_{A}\right)}\right\\}$
$\displaystyle\leq\max\left\\{\frac{8\epsilon_{\dagger}^{2}}{\left(1-\mu_{A}\right)},\frac{4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}}{\left(1-\mu_{A}\right)}\right\\}$
$\displaystyle\leq\frac{4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}}{\left(1-\mu_{A}\right)}.$
(136)

We get the last inequality for non trivial values of the bound
$\frac{8\epsilon_{\dagger}^{2}}{\left(1-\mu^{\dagger}_{A}\right)}\leq 1$ and
by using the following bound

$\displaystyle\frac{8\epsilon_{\dagger}^{2}}{\left(1-\mu_{A}\right)}$
$\displaystyle\leq\frac{16\epsilon_{\dagger}^{2}}{\left(1-\mu_{A}\right)}\leq\frac{4\epsilon_{\dagger}}{\sqrt{1-\mu_{A}}}=\frac{4\epsilon_{\dagger}\sqrt{1-\mu_{A}}}{\left(1-\mu_{A}\right)}\leq\frac{4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}}{\left(1-\mu_{A}\right)}.$
(137)

Finally the function
$f(\mu_{A})=\frac{4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}}{\left(1-\mu_{A}\right)}=\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-2q\right)^{4}\mu_{A}^{\text{}}}}{\left(1-\mu_{A}\right)}$
is increasing with respect to $\mu_{A}$ (for all $\mu_{A}\leq 1$) and
$\mu_{A}\leq\tanh\beta<1$, we have

$\displaystyle\left|\mu^{\dagger}_{f}\right|$
$\displaystyle\leq\frac{4\epsilon_{\dagger}\sqrt{1-\mu^{\dagger}_{A}}}{\left(1-\mu_{A}\right)}\leq\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-2q\right)^{4}\tanh\beta}}{\left(1-\tanh\beta\right)}\triangleq\tau^{\dagger}.$
(138)

The weakest edge should satisfy
$\left|\mu^{\dagger}_{f}\right|\geq\tau^{\dagger}$ to guarantee the correct
recovery of the tree under the event
$\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)$. This
yields a condition on the edge strengths:

$\displaystyle\left|\mu^{\dagger}_{f}\right|$
$\displaystyle\geq\tau^{\dagger}\implies$
$\displaystyle\left(1-2q\right)^{2}\tanh\alpha$
$\displaystyle\geq\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-2q\right)^{4}\tanh\beta}}{\left(1-\tanh\beta\right)}$
$\displaystyle\tanh\alpha$
$\displaystyle\geq\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-2q\right)^{4}\tanh\beta}}{\left(1-2q\right)^{2}\left(1-\tanh\beta\right)},\quad
q\in[0,\frac{1}{2}).$ (139)

The last inequality gives the definition of the strong edges in the noisy
scheme.

Based on the definition (138) we derive the following bound on
$\tau^{\dagger}$

$\displaystyle\tau^{\dagger}$
$\displaystyle=\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-2q\right)^{4}\tanh\beta}}{\left(1-\tanh\beta\right)}$
$\displaystyle=\frac{4\epsilon_{\dagger}\sqrt{1-\left(1-8q+24q^{2}-32q^{3}+16q^{4}\right)\tanh\beta}}{\left(1-\tanh\beta\right)}$
$\displaystyle\leq
4\epsilon_{\dagger}\frac{\sqrt{1-\tanh\beta}+\sqrt{\left(1-3q+4q^{2}-2q^{3}\right)8q\tanh\beta}}{\left(1-\tanh\beta\right)}$
$\displaystyle\leq
4\epsilon_{\dagger}e^{\beta}\left(1+e^{\beta}\sqrt{\left(1-q\right)\left(2q^{2}-2q+1\right)8q\tanh\beta}\right)$
(140)
$\displaystyle<4\epsilon_{\dagger}e^{\beta}\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right).$
(141)

(140) holds because $1-\tanh(\beta)\geq e^{-2\beta}$. We will later use (141)
in Lemma D.3.

In comparison to the noiseless setting (see Bresler and Karzand (2018)), we
can guarantee exact recover with high probability under the event
$\mathrm{E}^{\text{strong}}\left(\epsilon\right)$ when the weakest edge
satisfies the inequality

$\displaystyle\tanh\alpha\geq$
$\displaystyle\frac{4\epsilon}{\sqrt{1-\tanh\beta}}.$ (142)

Notice that (142) can be obtained by (139) when $q=0$ and $n=n_{\dagger}$.
When $q>0$ and $n=n_{\dagger}$ it is clear that the set of trees that can be
recovered from noisy observations is a subset of the set of trees that can be
recovered from the original observations. Also, we have

$\displaystyle\epsilon=$
$\displaystyle\sqrt{2\log\left(2p^{2}/\delta\right)/n}\implies
n=\frac{2}{\epsilon^{2}}\log\left(2p^{2}/\delta\right)\quad\text{and}$
$\displaystyle\epsilon_{\dagger}=$
$\displaystyle\sqrt{2\log\left(2p^{2}/\delta\right)/n_{\dagger}}\implies
n_{\dagger}=\frac{2}{\epsilon_{\dagger}^{2}}\log\left(2p^{2}/\delta\right).$
(143)

By combining (139) with (143) we found the number of samples that we need to
recover the tree with probality at $1-\delta$ (Theorem 3.1):

$\displaystyle n_{\dagger}>$
$\displaystyle\frac{32\left[1-\left(1-2q\right)^{4}\tanh\beta\right]}{\left(1-\tanh\beta\right)^{2}\left(1-2q\right)^{4}\tanh^{2}\alpha}\log\frac{2p^{2}}{\delta}.$
(144)

On the other hand when there is no noise (Bresler and Karzand, 2018) we need

$\displaystyle
n>\frac{32}{\tanh^{2}\alpha\left(1-\tanh\beta\right)}\log\frac{2p^{2}}{\delta}.$
(145)

##  D Analysis of the event
$\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)$

###### Lemma D.1

Consider a path of length $d\geq 2$ in the original tree $\mathrm{T}$, and
without loss of generality assume that path is $X_{1}-X_{2}-\cdot\cdot\cdot-
X_{d+1}$. Recall that $Y^{(i)}_{m}$ is the $i^{\text{th}}$ sample of $Y_{m}$
and $m\in[d+1]$ and
$\hat{\mu}^{\dagger}_{k}\triangleq\frac{1}{n}\sum^{n}_{i=1}Y^{(i)}_{k}Y^{(i)}_{k+1}$,
$k\in[d]$. Then

$\displaystyle\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right)$
$\displaystyle=\frac{1\pm(1-2q)^{2}\mu_{k}}{2}\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+\mu^{\dagger}_{k-1}\frac{1\pm\mu_{k}}{2}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}.$
(146)

Proof  Note that

$\displaystyle\hat{\mu}^{\dagger}_{k}=\frac{1}{n}\sum^{n}_{i=1}Y^{(i)}_{k}Y^{(i)}_{k+1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(i)},$
(147)

the latter gives

$\displaystyle\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}\perp\hat{\mu}^{\dagger}_{r}\quad\forall
r\in[1,2,\ldots k-2],\forall\ell\in[1,2,\dots,n]$ (148)

thus

$\displaystyle\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right)$
$\displaystyle=\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)$
$\displaystyle=\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\right)$
$\displaystyle=\frac{\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)}{\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\right)}$
$\displaystyle\qquad\times\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right).$ (149)

First we compute the probability
$\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\right)$.
Define the Bernoulli random variable $Z_{k-1}$ as

$\displaystyle
Z_{k-1}\triangleq\frac{X_{k-1}N_{k-1}X_{k}N_{k}+1}{2}=\begin{cases}0,\quad\text{w.p.
}\frac{1-(1-2q)^{2}\mu_{k-1}}{2}\\\ 1,\quad\text{w.p.
}\frac{1+(1-2q)^{2}\mu_{k-1}}{2}.\end{cases}$ (150)

Then

$\displaystyle\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\right)$
$\displaystyle=\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(2Z_{k-1}-1\right)^{(i)}\right)$
$\displaystyle=\mathbb{P}\left(\sum^{n}_{i=1}Z_{k-1}^{(i)}=n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}\right)$
$\displaystyle={n\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1-(1-2q)^{2}\mu_{k-1}}{2}\right)^{n-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1+(1-2q)^{2}\mu_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}.$
(151)

As a second step we compute the probability

$\displaystyle\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)$ (152)
$\displaystyle=\mathbb{P}\Bigg{(}\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1,i\neq\ell}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}$
$\displaystyle\qquad\qquad+\frac{\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}}{n}\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\Bigg{)}.$

Note that

$\displaystyle\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}\perp\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)},\quad\forall
i\neq\ell,$ (153)

and we would like to find the conditional distribution of
$\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}$ under the event
$\\{\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm 1\\}$.

$\displaystyle\mathbb{P}\left(\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}=c\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell})=\pm
1\right)$
$\displaystyle=\frac{\mathbb{P}\left(\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}=c,\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)}{\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)}$ $\displaystyle=\frac{\frac{1\pm
c\mathbb{E}[X_{k-1}N_{k-1}X_{k+1}N_{k+1}]+c(1-2q)^{2}\mu_{k-1}\pm(1-2q)^{2}\mu_{k}}{4}}{\frac{1\pm(1-2q)^{2}\mu_{k}}{2}}$
$\displaystyle=\frac{1\pm
c(1-2q)^{2}\mu_{k-1}\mu_{k}+c(1-2q)^{2}\mu_{k-1}\pm(1-2q)^{2}\mu_{k}}{2\left(1\pm(1-2q)^{2}\mu_{k}\right)},\quad
c\in\\{-1,+1\\}.$ (154)

Define

$\displaystyle
P_{1}\triangleq\mathbb{P}\left(\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}=+1\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell})=\pm
1\right)$ (155) $\displaystyle
P_{2}\triangleq\mathbb{P}\left(\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}=-1\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell})=\pm
1\right),$ (156)

then

$\displaystyle\mathbb{P}\Bigg{(}\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1,i\neq\ell}\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(i)}$
$\displaystyle\qquad\qquad+\frac{\left(X_{k-1}N_{k-1}X_{k}N_{k}\right)^{(\ell)}}{n}\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\Bigg{)}$
$\displaystyle=\mathbb{P}\left(\hat{\mu}^{\dagger}_{k-1}=\frac{1}{n}\sum^{n}_{i=1,i\neq\ell}\left(2Z_{k-1}-1\right)^{(i)}+\frac{\left(2Z_{k-1}-1\right)^{(\ell)}}{n}\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)$
$\displaystyle=\mathbb{P}\left(\sum^{n}_{i=1,i\neq\ell}\left(Z_{k-1}\right)^{(i)}+\left(Z_{k-1}\right)^{(\ell)}=n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)$
$\displaystyle=\mathbb{P}\left(\left(Z_{k-1}\right)^{(\ell)}=0\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)\mathbb{P}\left(\sum^{n}_{i=1,i\neq\ell}\left(Z_{k-1}\right)^{(i)}=n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}\right)$
$\displaystyle\quad+\mathbb{P}\left(\left(Z_{k-1}\right)^{(\ell)}=1\Big{|}\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)\mathbb{P}\left(\sum^{n}_{i=1,i\neq\ell}\left(Z_{k-1}\right)^{(i)}=n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}-1\right)$
$\displaystyle=P_{2}{n-1\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1-(1-2q)^{2}\mu_{k-1}}{2}\right)^{n-1-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1+(1-2q)^{2}\mu_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}$
$\displaystyle\quad+P_{1}{n-1\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}-1}\left(\frac{1-(1-2q)^{2}\mu_{k-1}}{2}\right)^{n-1-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}+1}\left(\frac{1+(1-2q)^{2}\mu_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}-1}.$
(157)

Finally

$\displaystyle\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)=\frac{1\pm(1-2q)^{2}\mu_{k}}{2},$ (158)

and (149), (151), (152), (157) give

$\displaystyle\frac{\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right)}{\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)}$ $\displaystyle=P_{2}{n-1\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}{n\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}^{-1}\frac{\left(\frac{1-\mu^{\dagger}_{k-1}}{2}\right)^{n-1-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1+\mu^{\dagger}_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}}{\left(\frac{1-\mu^{\dagger}_{k-1}}{2}\right)^{n-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1+\mu^{\dagger}_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}}$
$\displaystyle\quad+P_{1}{n-1\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}-1}{n\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}^{-1}\frac{\left(\frac{1-\mu^{\dagger}_{k-1}}{2}\right)^{n-1-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}+1}\left(\frac{1+\mu^{\dagger}_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}-1}}{\left(\frac{1-\mu^{\dagger}_{k-1}}{2}\right)^{n-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}\left(\frac{1+\mu^{\dagger}_{k-1}}{2}\right)^{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}}$
$\displaystyle=P_{2}{n-1\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}{n\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}^{-1}\left(\frac{1-\mu^{\dagger}_{k-1}}{2}\right)^{-1}$
$\displaystyle\quad+P_{1}{n-1\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}-1}{n\choose
n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}^{-1}\left(\frac{1+\mu^{\dagger}_{k-1}}{2}\right)^{-1}$
$\displaystyle=P_{2}\frac{n-n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}{n}\left(\frac{1-\mu^{\dagger}_{k-1}}{2}\right)^{-1}+P_{1}\frac{n\frac{\hat{\mu}^{\dagger}_{k-1}+1}{2}}{n}\left(\frac{1+\mu^{\dagger}_{k-1}}{2}\right)^{-1}$
$\displaystyle=P_{2}\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}+P_{1}\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}.$
(159)

The latter and the definition of $P_{1},P_{2}$ (see (155), (156)) give

$\displaystyle\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right)$
$\displaystyle=\left[P_{2}\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}+P_{1}\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}\right]\mathbb{P}\left(\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}=\pm
1\right)$
$\displaystyle=\left[P_{2}\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}+P_{1}\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}\right]\frac{1\pm(1-2q)^{2}\mu_{k}}{2}$
$\displaystyle=\Bigg{[}\frac{1\mp(1-2q)^{2}\mu_{k-1}\mu_{k}-(1-2q)^{2}\mu_{k-1}\pm(1-2q)^{2}\mu_{k}}{2\left(1\pm(1-2q)^{2}\mu_{k}\right)}\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}$
$\displaystyle\qquad+\frac{1\pm(1-2q)^{2}\mu_{k-1}\mu_{k}+(1-2q)^{2}\mu_{k-1}\pm(1-2q)^{2}\mu_{k}}{2\left(1\pm(1-2q)^{2}\mu_{k}\right)}\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}\Bigg{]}\frac{1\pm(1-2q)^{2}\mu_{k}}{2}$
$\displaystyle=\frac{1\mp(1-2q)^{2}\mu_{k-1}\mu_{k}-(1-2q)^{2}\mu_{k-1}\pm(1-2q)^{2}\mu_{k}}{4}\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}$
$\displaystyle\qquad+\frac{1\pm(1-2q)^{2}\mu_{k-1}\mu_{k}+(1-2q)^{2}\mu_{k-1}\pm(1-2q)^{2}\mu_{k}}{4}\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}$
$\displaystyle=\frac{1\pm(1-2q)^{2}\mu_{k}}{4}\left(\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}+\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}\right)$
$\displaystyle\qquad+\frac{\pm(1-2q)^{2}\mu_{k-1}\mu_{k}+(1-2q)^{2}\mu_{k-1}}{4}\left(\frac{1+\hat{\mu}^{\dagger}_{k-1}}{1+\mu^{\dagger}_{k-1}}-\frac{1-\hat{\mu}^{\dagger}_{k-1}}{1-\mu^{\dagger}_{k-1}}\right)$
$\displaystyle=\frac{1\pm(1-2q)^{2}\mu_{k}}{2}\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+(1-2q)^{2}\mu_{k-1}\frac{1\pm\mu_{k}}{2}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}.$
(160)

Note that $(1-2q)^{2}\mu_{k-1}=\mu^{\dagger}_{k-1}$, and the proof is
completed.

###### Lemma D.2

Define the function $K(\beta,q)$ as

$\displaystyle
K(\beta,q)\triangleq\frac{10(1-\tanh^{2}(\beta))}{9+(1-2q)^{2}-\tanh^{2}(\beta)(1-2q)^{2}(9(1-2q)^{2}+1)}$
(161)

and the event $\mathrm{E^{edge}_{e,\dagger}}$ as

$\displaystyle\mathrm{E^{edge}_{e,\dagger}}\triangleq\left\\{\left|\hat{\mu}^{\dagger}_{e}-\mu^{\dagger}_{e}\right|\leq\gamma_{e}\right\\},\quad\forall
e\in\mathcal{E}_{\mathrm{T}},$ (162)

and
$\mathrm{E^{edge}_{\dagger}(\mathcal{E}_{\mathrm{T}})}\triangleq\cap_{e\in\mathcal{E}_{T}}\mathrm{E^{edge}_{e,\dagger}}$.
If

$\displaystyle
n\geq\frac{108e^{2\beta}\log(2p/\delta)}{(1-2q)^{4}K(\beta,q)}\text{ and
}\gamma_{e}=\sqrt{3\frac{1-\mu_{e}^{2}}{nK(\beta,q)}\log(2p/\delta)}$ (163)

then
$\mathbb{P}\left[\left(\mathrm{E^{edge}_{\dagger}(\mathcal{E}_{\mathrm{T}})}\right)^{c}\right]\leq\delta$.

Proof  The variance of $\hat{\mu}^{\dagger}_{e}$ is
$(1-(\mu^{\dagger}_{e})^{2})/n$ and by applying Bernstein’s inequality

$\displaystyle\mathbb{P}\left[\left(\mathrm{E^{edge}_{e,\dagger}}\right)^{c}\right]\leq
2\exp\left(-\frac{n\gamma^{2}_{e}}{2\left(1-(\mu^{\dagger}_{e})^{2}\right)+\frac{4}{3}\gamma_{e}}\right),\quad\forall\gamma_{e}>0.$
(164)

We choose
$\gamma_{e}=\sqrt{3\frac{1-\mu_{e}^{2}}{nK(\beta,q)}\log(2p/\delta)}$ (because
the parameter $\gamma_{e}$ is free, that is, Bernstein’s inequality holds for
all $\gamma_{e}>0$). If $n$ satisfies (163) then

$\displaystyle\gamma_{e}\leq\sqrt{3\frac{1-\mu_{e}^{2}}{108e^{2\beta}}(1-2q)^{4}}\leq\frac{(1-2q)^{2}}{6}(1-\mu_{e}^{2}),$
(165)

and the last is true because $e^{-2\beta}\leq 1-\tanh(\beta)\leq
1-|\mu_{e}|\leq 1-\mu^{2}_{e}$. By applying (163) and (165) on (164) we get

$\displaystyle\mathbb{P}\left[\left(\mathrm{E^{edge}_{e,\dagger}}\right)^{c}\right]$
$\displaystyle\leq
2\exp\left(-\frac{n\gamma^{2}_{e}}{2\left(1-(\mu^{\dagger}_{e})^{2}\right)+\frac{4}{3}\gamma_{e}}\right)$
$\displaystyle\leq
2\exp\left(-\frac{3\frac{1-\mu_{e}^{2}}{K(\beta,q)}\log(2p/\delta)}{2\left(1-(1-2q)^{4}\mu_{e}^{2}\right)+\frac{4}{3}\frac{(1-2q)^{2}}{6}(1-\mu^{2}_{e})}\right)$
$\displaystyle=2\exp\left(-\frac{3}{K(\beta,q)}\frac{1-\mu_{e}^{2}}{2+\frac{2}{9}(1-2q)^{2}-\mu_{e}^{2}(1-2q)^{2}(2(1-2q)^{2}+\frac{2}{9})}\log(2p/\delta)\right)$
$\displaystyle=2\exp\left(-\frac{3}{2K(\beta,q)}\frac{1-\mu_{e}^{2}}{1+\frac{1}{9}(1-2q)^{2}-\mu_{e}^{2}(1-2q)^{2}((1-2q)^{2}+\frac{1}{9})}\log(2p/\delta)\right)$
$\displaystyle\leq
2\exp\left(-\frac{10}{9K(\beta,q)}\frac{1-\mu_{e}^{2}}{1+\frac{1}{9}(1-2q)^{2}-\mu_{e}^{2}(1-2q)^{2}((1-2q)^{2}+\frac{1}{9})}\log(2p/\delta)\right)$
(166)

The following function

$\displaystyle
f(x)=\frac{10}{9}\frac{1-x}{1+\frac{1}{9}(1-2q)^{2}-x(1-2q)^{2}((1-2q)^{2}+\frac{1}{9})},\text{
}x\in[\tanh^{2}(\alpha),\tanh^{2}(\beta)]$ (167)

is strictly decreasing, thus we have $f(\tanh^{2}(\beta))\leq f(x)$ for all
$x\in[\tanh^{2}(\alpha),\tanh^{2}(\beta)]$. Also $K(\beta,q)\equiv
f(\tanh^{2}(\beta))$, the latter together with (166) give

$\displaystyle\mathbb{P}\left[\left(\mathrm{E^{edge}_{e,\dagger}}\right)^{c}\right]$
$\displaystyle\leq
2\exp\left(-\frac{1}{K(\beta,q)}f(\mu^{2}_{e})\log(2p/\delta)\right)$
$\displaystyle\leq
2\exp\left(-\frac{1}{K(\beta,q)}f(\tanh^{2}(\beta))\log(2p/\delta)\right)$
$\displaystyle=2\exp\left(-\frac{1}{K(\beta,q)}K(\beta,q)\log(2p/\delta)\right)$
$\displaystyle=\frac{\delta}{p}.$ (168)

Finally, by applying union over the $p-1$ edges of the tree we get
$\mathbb{P}\left[\left(\mathrm{E^{edge}_{\dagger}(\mathcal{E}_{\mathrm{T}})}\right)^{c}\right]\leq\delta$.
The next Lemma is the extension of Lemma 8.7 by Bresler and Karzand (2018).
The sample complexity bound exactly recovers the noiseless case and its
expression is continuous at $q=0$. Further, the bound is independent of the
length of the longest path $d$, similarly to the noiseless setting. Finally,
we provide upper bounds on the functions that appear in the bound. The latter
give a more tractable version of the result and a clear representation of the
required number of samples as a function of the parameters.

######  Lemma D.3 (Concentration bound for the event
$\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)$)

For $\beta>0$ and $q\in[0,1/2)$ we define the functions $S(\cdot)$,
$G(\cdot)$, $K(\cdot)$, $A(\cdot)$, $\Delta(\cdot)$

$\displaystyle S(\beta,q)$ $\displaystyle\triangleq
2+\frac{(1-2q)^{2}}{6}(1-(1-2q)^{2})\tanh^{2}(\beta)\leq
3-(1-2q)^{2}\triangleq S$ (169) $\displaystyle A(\beta,q)$
$\displaystyle\equiv A\triangleq(1-2q)^{2}[1-\tanh(\beta)(1-(1-2q)^{2})]$
(170) $\displaystyle G(\beta,q)$
$\displaystyle\triangleq\frac{3}{4(1-2q)^{2}}\left[d(1-A)\left(\frac{A+2}{3}\right)^{d}+1\right]\leq\frac{3\left(3e^{-1}\mathds{1}_{q\neq
0}+1\right)}{4(1-2q)^{2}}\triangleq G,$ (171)

and the inequality in (171) holds because the function $G(\beta,q)$ is bounded
for all $d\in\mathcal{N}\setminus\\{1\\}$.

$\displaystyle K(\beta,q)$
$\displaystyle\triangleq\frac{10(1-\tanh^{2}(\beta))}{9+(1-2q)^{2}-\tanh^{2}(\beta)(1-2q)^{2}(9(1-2q)^{2}+1)}\geq
e^{-2\beta\mathds{1}_{q=0}}\triangleq K$ (172) $\displaystyle\Delta$
$\displaystyle\triangleq\frac{1-(1-2q)^{2}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sqrt{\frac{3\log(2p^{3}/\delta)}{n}}\tanh^{2}(\beta)e^{2\beta}.$
(173)

If $\Delta<\gamma_{\dagger}\leq S(\beta,q)G(\beta,q)/3+\Delta$ and

$\displaystyle
n\geq\max\left\\{\frac{S^{2}(\beta,q)G^{2}(\beta,q)}{0.3^{2}\left(\gamma_{\dagger}-\Delta\right)^{2}}\log(4p^{2}/\delta),\frac{108e^{2\beta}}{(1-2q)^{4}K(\beta,q)}\log(2p^{3}/\delta)\right\\}$
(174)

then

$\displaystyle\mathbb{P}\left(\left|\prod^{d}_{i=1}\frac{\hat{\mu}^{\dagger}_{i}}{(1-2q)^{2}}-\prod^{d}_{i=1}\frac{\mu^{\dagger}_{i}}{(1-2q)^{2}}\right|\geq\gamma_{\dagger}\right)\leq\frac{2\delta}{p^{2}},\text{
}\forall d\in[p-1].$ (175)

Proof  Define the random variable

$\displaystyle
M^{\dagger}_{i}\triangleq\left(\frac{\hat{\mu}^{\dagger}_{i}}{(1-2q)^{2}}-\frac{\mu^{\dagger}_{i}}{(1-2q)^{2}}\right)\prod^{i-1}_{j=1}\frac{\hat{\mu}^{\dagger}_{j}}{(1-2q)^{2}}\prod^{d}_{j=i+1}\frac{\mu^{\dagger}_{j}}{(1-2q)^{2}}.$
(176)

Then
$\sum^{d}_{i=1}M^{\dagger}_{i}=\prod^{d}_{i=1}\frac{\hat{\mu}^{\dagger}_{i}}{(1-2q)^{2}}-\prod^{d}_{i=1}\frac{\mu^{\dagger}_{i}}{(1-2q)^{2}}$,
$\mathcal{A}_{k}\triangleq\left\\{e_{1},e_{2},\ldots,e_{k}\right\\}$, for
$2\leq k\leq d$. The law of total probability gives

$\displaystyle\\!\\!\\!\mathbb{P}\left[\left|\sum^{d}_{i=1}M^{\dagger}_{i}\right|>\gamma\right]$
$\displaystyle\leq\mathbb{P}\left[\left|\sum^{d}_{i=1}M^{\dagger}_{i}\right|>\gamma\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]+\mathbb{P}\left[\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right)^{c}\right].$
(177)

For second term, Lemma D.2 gives that
$\mathbb{P}\left[\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right)^{c}\right]\leq\delta/p^{2}$
if

$\displaystyle
n\geq\frac{108e^{2\beta}\log(2p^{3}/\delta)}{(1-2q)^{4}K(\beta,q)},$ (178)

we define the function $K(\beta,q)$ in Lemma D.2 (161). Here we will find an
upper bound for the first term of the right hand-side of (177). Note that
$M^{\dagger}_{k}$ is written as

$\displaystyle M^{\dagger}_{k}$
$\displaystyle=\left(\frac{\frac{1}{n}\sum^{n}_{\ell=1}\left(Y_{k}Y_{k+1}\right)^{(\ell)}}{(1-2q)^{2}}-\frac{\mu^{\dagger}_{k}}{(1-2q)^{2}}\right)\prod^{k-1}_{j=1}\frac{\hat{\mu}^{\dagger}_{j}}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{\mu^{\dagger}_{j}}{(1-2q)^{2}}$
$\displaystyle=\frac{1}{n}\sum^{n}_{\ell=1}\left(\frac{\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}}{(1-2q)^{2}}-\frac{\mu^{\dagger}_{k}}{(1-2q)^{2}}\right)\prod^{k-1}_{j=1}\frac{\hat{\mu}^{\dagger}_{j}}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{\mu^{\dagger}_{j}}{(1-2q)^{2}}.$
(179)

and we define

$\displaystyle
Z^{(\ell)}_{k}\triangleq\left(\frac{\left(X_{k}N_{k}X_{k+1}N_{k+1}\right)^{(\ell)}}{(1-2q)^{2}}-\frac{\mu^{\dagger}_{k}}{(1-2q)^{2}}\right)\prod^{k-1}_{j=1}\frac{\hat{\mu}^{\dagger}_{j}}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{\mu^{\dagger}_{j}}{(1-2q)^{2}}.$
(180)

The random variables $Z^{(\ell)}_{k}$ for $\ell\in[n]$ and fixed $k\in[d]$ are
independent conditioned on the event
$\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})$. However the
conditional expectation
$\mathbb{E}[Z^{(i)}_{k}|Z^{(i-1)}_{k},\ldots,Z^{(1)}_{k},\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}]$
is not zero. To apply a concentration of measure result on $Z^{(\ell)}_{k}$ we
use the extended Bennet’s inequality for supermartingales (Fan et al., 2012).

Martingale Differences: Define $\xi_{k}^{(0)}\triangleq 0$,
$\xi_{k}^{(1)}\triangleq
Z^{(1)}_{k}-\mathbb{E}\left[Z^{(1)}_{k}|\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right]$,
$\xi^{(i)}_{k}\triangleq
Z^{(i)}_{k}-\mathbb{E}\left[Z^{(i)}_{k}|Z^{(i-1)}_{k},\ldots,Z^{(1)}_{k},\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right]$.
Also, define as $\mathcal{F}^{k}_{i-1}$ the $\sigma$-algebra generated by
$Z^{(i-1)}_{k},\ldots,Z^{(1)}_{k},\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}$,
then $(\xi^{(i)}_{k},\mathcal{F}^{k}_{i})_{i=1.\ldots,n}$ is a Martingale
Difference Sequence (MDS).

Additionally, conditioned on
$Z^{(i-1)}_{k},\ldots,Z^{(1)}_{k},\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}$
we have

$\displaystyle\\!\\!\\!\\!Z^{(i)}_{k}=\begin{cases}\frac{1}{(1-2q)^{2d}}\left(1-\mu^{\dagger}_{k}\right)\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j},&\text{
w.p.
}\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=+1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)\\\
-\frac{1}{(1-2q)^{2d}}\left(1+\mu^{\dagger}_{k}\right)\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j},&\text{
w.p.
}\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=-1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right),\end{cases}$
(181)

and we have proved (Lemma D.1) that

$\displaystyle\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right)$
$\displaystyle=\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=\pm
1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)$
$\displaystyle=\frac{1\pm\mu^{\dagger}_{k}}{2}\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+\mu^{\dagger}_{k-1}\frac{1\pm\mu_{k}}{2}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}.$
(182)

Thus we have

$\displaystyle\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]=\mathbb{E}\left[Z^{(i)}_{k}|Z^{(i-1)}_{k},\ldots,Z^{(1)}_{k},\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right]$
$\displaystyle=\left[\left(1-\mu^{\dagger}_{k}\right)\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=+1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)-(1+\mu^{\dagger}_{k})\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=-1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)\right]$
$\displaystyle\qquad\times\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}}.$
(183)

Note that (D) gives

$\displaystyle\left[\left(1-\mu^{\dagger}_{k}\right)\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=+1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)-(1+\mu^{\dagger}_{k})\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=-1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)\right]$
$\displaystyle=\left((1-\mu^{\dagger}_{k})\frac{1+\mu^{\dagger}_{k}}{2}-(1+\mu^{\dagger}_{k})\frac{1-\mu^{\dagger}_{k}}{2}\right)\mu^{\dagger}_{k-1}\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle\quad+\left((1-\mu^{\dagger}_{k})\frac{1+\mu_{k}}{2}-(1+\mu^{\dagger}_{k})\frac{1-\mu_{k}}{2}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=\left((1-\mu^{\dagger}_{k})\frac{1+\mu_{k}}{2}-(1+\mu^{\dagger}_{k})\frac{1-\mu_{k}}{2}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=\frac{1}{2}\left(1-\mu^{\dagger}_{k}+\mu_{k}-\mu^{\dagger}_{k}\mu_{k}-1+\mu_{k}-\mu^{\dagger}_{k}+\mu^{\dagger}_{k}\mu_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=(\mu_{k}-\mu^{\dagger}_{k})\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}.$
(184)

Combine the latter with (183) to get

$\displaystyle\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]=\mu^{\dagger}_{k-1}(\mu_{k}-\mu^{\dagger}_{k})\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}},\text{
}i\in[n].$ (185)

If $q=0$ then $\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]=0$.
Also
$\lim_{n\rightarrow\infty}\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\rightarrow
0$ for all $q\in[0,1/2)$ because
$\lim_{n\rightarrow\infty}\hat{\mu}^{\dagger}_{k-1}\rightarrow\mu^{\dagger}_{k-1}$.
Note that

$\displaystyle\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle=\mathbb{E}\left[\left(Z^{(i)}_{k}-\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle=\mathbb{E}\left[\left(Z^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]-\mathbb{E}^{2}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right].$
(186)

We compute
$\mathbb{E}\Big{[}\left(Z^{(i)}_{k}\right)^{2}\Big{|}\mathcal{F}^{k}_{i-1}\Big{]}$,

$\displaystyle\mathbb{E}\left[\left(Z^{(i)}_{k}\right)^{2}|\mathcal{F}^{k}_{i-1}\right]=\mathbb{E}\left[\left(Z^{(i)}_{k}\right)^{2}|Z^{(i-1)}_{k},\ldots,Z^{(1)}_{k},\hat{\mu}^{\dagger}_{k-1},\ldots,\hat{\mu}^{\dagger}_{1}\right]$
$\displaystyle=\left[\left(1-\mu^{\dagger}_{k}\right)^{2}\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=+1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)+(1+\mu^{\dagger}_{k})^{2}\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=-1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)\right]$
$\displaystyle\qquad\times\left(\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}}\right)^{2}.$
(187)

We use (D) to find

$\displaystyle\left[\left(1-\mu^{\dagger}_{k}\right)^{2}\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=+1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)+(1+\mu^{\dagger}_{k})^{2}\mathbb{P}\left(Y^{(\ell)}_{k}Y^{(\ell)}_{k+1}=-1\Big{|}\hat{\mu}^{\dagger}_{k-1}\right)\right]$
$\displaystyle=\left(\left(1-\mu^{\dagger}_{k}\right)^{2}\frac{1+\mu^{\dagger}_{k}}{2}+\left(1+\mu^{\dagger}_{k}\right)^{2}\frac{1-\mu^{\dagger}_{k}}{2}\right)\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle\qquad+\left(\left(1-\mu^{\dagger}_{k}\right)^{2}\frac{1+\mu_{k}}{2}+\left(1+\mu^{\dagger}_{k}\right)^{2}\frac{1-\mu_{k}}{2}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=(1-(\mu^{\dagger}_{k})^{2})\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+\left(1+(\mu^{\dagger}_{k})^{2}-2\mu_{k}\mu^{\dagger}_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=(1-(\mu^{\dagger}_{k})^{2})\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+\left(1+(\mu^{\dagger}_{k})^{2}-2(\mu^{\dagger}_{k})^{2}+2(\mu^{\dagger}_{k})^{2}-2\mu_{k}\mu^{\dagger}_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=(1-(\mu^{\dagger}_{k})^{2})\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+\left(1-(\mu^{\dagger}_{k})^{2}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle\qquad+2\mu^{\dagger}_{k}\left(\mu^{\dagger}_{k}-\mu_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=\left(1-(\mu^{\dagger}_{k})^{2}\right)\left[\frac{1-\mu^{\dagger}_{k-1}\hat{\mu}^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}+\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}\right]+2\mu^{\dagger}_{k}\left(\mu^{\dagger}_{k}-\mu_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=\left(1-(\mu^{\dagger}_{k})^{2}\right)+2\mu^{\dagger}_{k}\left(\mu^{\dagger}_{k}-\mu_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}.$
(188)

Now we combine (185), (186), (187) and (188) to get

$\displaystyle\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle=\mathbb{E}\left[\left(Z^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]-\mathbb{E}^{2}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle=\Bigg{[}\left(1-(\mu^{\dagger}_{k})^{2}\right)+2\mu^{\dagger}_{k}\left(\mu^{\dagger}_{k}-\mu_{k}\right)\mu^{\dagger}_{k-1}\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}-\left(\mu^{\dagger}_{k-1}(\mu_{k}-\mu^{\dagger}_{k})\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}\right)^{2}\Bigg{]}$
$\displaystyle\qquad\times\left(\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}}\right)^{2}$
$\displaystyle=\left[1-\left(\mu^{\dagger}_{k}+\mu^{\dagger}_{k-1}(\mu_{k}-\mu^{\dagger}_{k})\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}\right)^{2}\right]\left(\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}}\right)^{2}$
(189)

For sake of space we define the function

$\displaystyle\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)\equiv
f(\mu^{\dagger}_{k},\mu^{\dagger}_{k-1},\hat{\mu}^{\dagger}_{k-1},q)\triangleq\mu^{\dagger}_{k-1}(\mu_{k}-\mu^{\dagger}_{k})\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}},$
(190)

and then (185) and (189) can be written as

$\displaystyle\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle=\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}},\text{
}i\in[n],$ (191)
$\displaystyle\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle=\left[1-\left(\mu^{\dagger}_{k}+\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)\right)^{2}\right]\left(\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}}\right)^{2},\text{
}i\in[n].$ (192)

We would like to find an upper bound on the summation
$\sum^{d}_{k=1}\mathbb{E}\Big{[}\Big{(}\xi^{(i)}_{k}\Big{)}^{2}\Big{|}\mathcal{F}^{k}_{i-1}\Big{]}$.
Define $A\equiv A(\beta,q)\triangleq(1-2q)^{2}[1-\tanh(\beta)(1-(1-2q)^{2})]$,
for all $\beta>0$ and $q\in[0,1)$ then

$\displaystyle\left[1-\left(\mu^{\dagger}_{k}+\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)\right)^{2}\right]$
$\displaystyle=\left[1-\left(\mu^{\dagger}_{k}+\mu^{\dagger}_{k-1}(\mu_{k}-\mu^{\dagger}_{k})\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}\right)^{2}\right]$
$\displaystyle=\left[1-\mu^{2}_{k}\left((1-2q)^{2}+\mu^{\dagger}_{k-1}(1-(1-2q)^{2})\frac{\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}\right)^{2}\right]$
$\displaystyle\leq\left[1-\mu^{2}_{k}\left((1-2q)^{2}-|\mu^{\dagger}_{k-1}|(1-(1-2q)^{2})\frac{|\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}|}{1-(\mu^{\dagger}_{k-1})^{2}}\right)^{2}\right]$
$\displaystyle\leq\left[1-\mu^{2}_{k}\left((1-2q)^{2}-(1-2q)^{2}\tanh(\beta)(1-(1-2q)^{2})\right)^{2}\right]$
(193) $\displaystyle\leq[1-\mu^{2}_{k}A(\beta,q)],$ (194)

and (193) holds because
$|\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}|\leq\gamma^{\dagger}_{j}\leq(1-2q)^{2}(1-\mu^{2}_{j})/6\leq(1-2q)^{2}(1-(\mu^{\dagger}_{j})^{2})/6$.
Then (192) and (194) give

$\displaystyle\sum^{d}_{k=1}\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle\leq\sum^{d}_{k=1}[1-\mu^{2}_{k}A(\beta,q)]\left(\frac{\prod^{k-1}_{j=1}\hat{\mu}^{\dagger}_{j}\prod^{d}_{j=k+1}\mu^{\dagger}_{j}}{(1-2q)^{2d}}\right)^{2}$
$\displaystyle\leq\frac{1}{(1-2q)^{2}}\sum^{d}_{k=1}[1-\mu^{2}_{k}A(\beta,q)]\prod^{d}_{j=1,j\neq
k}\left[\mu_{j}^{2}+2\frac{\gamma^{\dagger}_{j}}{(1-2q)^{2}}\right].$ (195)

(195) holds under the event
$\mathrm{E^{edge}_{\dagger}(\mathcal{E}_{\mathrm{T}})}$ defined in (162) (see
Lemma D.2) because

$\displaystyle\left(\frac{\hat{\mu}^{\dagger}_{j}}{(1-2q)^{2}}\right)^{2}\leq\left(\frac{\mu^{\dagger}_{j}}{(1-2q)^{2}}\right)^{2}+2\frac{\gamma^{\dagger}_{j}}{(1-2q)^{2}},$
(196)

since $|\mu^{\dagger}_{j}|\leq(1-2q)^{2}$,
$|\hat{\mu}^{\dagger}_{j}|\leq(1-2q)^{2}$ under the assumption of known $q$.
Next we define
$x_{j}\triangleq\mu_{j}^{2}+2\frac{\gamma^{\dagger}_{j}}{(1-2q)^{2}}$, then
$3(1-A(\beta,q)x_{j})/2+(A(\beta,q)-1)/2)\geq 1-\mu^{2}_{k}A(\beta,q)$ and
(195) gives

$\displaystyle\sum^{d}_{k=1}\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]$
$\displaystyle\leq\frac{1}{(1-2q)^{2}}\sum^{d}_{k=1}\left[\frac{3}{2}(1-Ax_{j})+\frac{A-1}{2}\right]\prod^{d}_{j=1,j\neq
k}x_{j}$
$\displaystyle\leq\frac{d}{(1-2q)^{2}}\left[\frac{3}{2}(1-Ax)+\frac{A-1}{2}\right]x^{d-1}.$
(197)

The latter is maximized at $x^{*}=(A+2)\left(1-\frac{1}{d}\right)$/3 and
$A\in(0,1]$, thus we have

$\displaystyle\frac{d}{(1-2q)^{2}}\left[\frac{3}{2}(1-Ax)+\frac{A-1}{2}\right]x^{d-1}$
$\displaystyle\leq\frac{d}{(1-2q)^{2}}\left[\frac{3}{2}(1-A\frac{A+2}{3}+A\frac{A+2}{3d})+\frac{A-1}{2}\right]\left(\frac{A+2}{3}\right)^{d-1}\left(1-\frac{1}{d}\right)^{d-1}$
$\displaystyle=\frac{d}{(1-2q)^{2}}\left[\frac{3}{2}-\frac{A(A+2)}{2}+\frac{A-1}{2}\right](x^{*})^{d-1}+\frac{A(A+2)}{2(1-2q)^{2}}(x^{*})^{d-1}$
$\displaystyle=d\frac{2-A^{2}-A}{2(1-2q)^{2}}\left(\frac{A+2}{3}\right)^{d-1}\left(1-\frac{1}{d}\right)^{d-1}+\frac{A(A+2)}{2(1-2q)^{2}}\left(\frac{A+2}{3}\right)^{d-1}\left(1-\frac{1}{d}\right)^{d-1}$
$\displaystyle\leq
d\frac{2-A^{2}-A}{2(1-2q)^{2}}\left(\frac{A+2}{3}\right)^{d-1}\left(1-\frac{1}{2}\right)+\frac{A(A+2)}{2(1-2q)^{2}}\left(\frac{A+2}{3}\right)\left(1-\frac{1}{2}\right)$
$\displaystyle=d\frac{(A+2)(1-A)}{4(1-2q)^{2}}\left(\frac{A+2}{3}\right)^{d-1}+\frac{A(A+2)^{2}}{12(1-2q)^{2}}$
$\displaystyle\leq
d\frac{3(1-A)}{4(1-2q)^{2}}\left(\frac{A+2}{3}\right)^{d}+\frac{3}{4(1-2q)^{2}}\triangleq
G(\beta,q)$ (198)
$\displaystyle\leq\frac{(1-A)}{4(1-2q)^{2}}\frac{3}{e\log\frac{3}{A+2}}+\frac{3}{4(1-2q)^{2}}$
$\displaystyle=\frac{3(1-A)}{e4(1-2q)^{2}\log\frac{3}{A+2}}+\frac{3}{4(1-2q)^{2}}$
$\displaystyle\leq\frac{3\left(3e^{-1}+1\right)}{4(1-2q)^{2}}.$

In (198) we define the function $G(\beta,q)$ and we proved that it has an
upper bound independent of $d\in[p-1]$,

$\displaystyle G(\beta,q)\triangleq
d\frac{3(1-A(\beta,q))}{4(1-2q)^{2}}\left(\frac{A(\beta,q)+2}{3}\right)^{d}+\frac{3}{4(1-2q)^{2}}\leq\frac{3\left(3e^{-1}\mathds{1}_{q\neq
0}+1\right)}{4(1-2q)^{2}}\equiv G.$ (199)

For the rest of the prove and the final result $G(\beta,q)$ can be replaced by
its upper bound in (199), however the definition of $G(\beta,q)$ shows the
continuity of the result for $q\rightarrow 0$.

The following inequality holds with probability $1$ for all $i\in[n]$ and
$k\in[d]$ under the event
$\mathrm{E^{edge}_{\dagger}(\mathcal{E}_{\mathrm{T}})}$ (Lemma D.2),

$\displaystyle|\xi^{(i)}_{k}|$ $\displaystyle\leq
2+\left|\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right|$
$\displaystyle=2+\frac{|\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)|}{(1-2q)^{2}}\frac{\prod^{k-1}_{j=1}|\hat{\mu}^{\dagger}_{j}|\prod^{d}_{j=k+1}|\mu^{\dagger}_{j}|}{(1-2q)^{2d-2}}$
$\displaystyle\leq 2+\frac{|\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)|}{(1-2q)^{2}}$
$\displaystyle=2+\frac{1}{(1-2q)^{2}}|\mu^{\dagger}_{k-1}||(\mu_{k}-\mu^{\dagger}_{k})|\frac{|\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}|}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle=2+\tanh^{2}(\beta)(1-(1-2q)^{2})\frac{\gamma^{\dagger}_{k-1}}{1-(\mu^{\dagger}_{k-1})^{2}}$
$\displaystyle\leq
2+\frac{(1-2q)^{2}}{6}(1-(1-2q)^{2})\tanh^{2}(\beta)\triangleq S(\beta,q).$
(200)

the last step comes form the inequality
$\gamma^{\dagger}_{e}\leq\frac{(1-2q)^{2}}{6}(1-(\mu_{e})^{2})$ (165), which
holds if the inequality $n>\frac{108e^{2\beta}}{K(\beta,q)(1-2q)^{4}}\log(4p)$
holds (see 163). Recall that Lemma D.2 gives

$\displaystyle\gamma_{e}$
$\displaystyle=\sqrt{3\frac{1-\mu_{e}^{2}}{nK(\beta,q)}\log(2p^{3}/\delta)}\leq\sqrt{3\frac{1-\tanh^{2}(\beta)}{nK(\beta,q)}\log(2p^{3}/\delta)}\leq\sqrt{\frac{3\log(2p^{3}/\delta)}{n}}\equiv\tilde{\gamma}.$
(201)

Also, for all $i\in[n]$ we have

$\displaystyle\left|\sum^{d}_{k=1}\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right|$
$\displaystyle=\left|\sum^{d}_{k=2}\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right|$
$\displaystyle\leq\sum^{d}_{k=2}\left|\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right|$
$\displaystyle=\sum^{d}_{k=2}\frac{|\hat{f}^{\mu_{k}}_{\mu_{k-1}}(q)|}{(1-2q)^{2}}\frac{\prod^{k-1}_{j=1}|\hat{\mu}^{\dagger}_{j}|\prod^{d}_{j=k+1}|\mu^{\dagger}_{j}|}{(1-2q)^{2d-2}}$
$\displaystyle\leq\frac{1}{(1-2q)^{2}}\sum^{d}_{k=2}|\mu^{\dagger}_{k-1}|(\mu_{k}-\mu^{\dagger}_{k})\frac{|\hat{\mu}^{\dagger}_{k-1}-\mu^{\dagger}_{k-1}|}{1-(\mu^{\dagger}_{k-1})^{2}}\prod^{k-1}_{j=1}\frac{|\hat{\mu}^{\dagger}_{j}|}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{|\mu^{\dagger}_{j}|}{(1-2q)^{2}}$
$\displaystyle\leq\tanh^{2}(\beta)(1-(1-2q)^{2})\frac{\gamma_{e}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sum^{d}_{k=2}\prod^{k-1}_{j=1}\frac{|\hat{\mu}^{\dagger}_{j}|}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{|\mu^{\dagger}_{j}|}{(1-2q)^{2}}$
(202)
$\displaystyle\leq\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sum^{d}_{k=2}\prod^{k-1}_{j=1}\frac{|\hat{\mu}^{\dagger}_{j}|}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{|\mu^{\dagger}_{j}|}{(1-2q)^{2}}$
(203)
$\displaystyle\leq\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sum^{d}_{k=2}\prod^{k-1}_{j=1}\frac{|\mu^{\dagger}_{j}|+\gamma_{j}}{(1-2q)^{2}}\prod^{d}_{j=k+1}\frac{|\mu^{\dagger}_{j}|}{(1-2q)^{2}}$
(204)
$\displaystyle=\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sum^{d}_{k=2}\prod^{k-1}_{j=1}\tanh(\beta)+\frac{\gamma_{j}}{(1-2q)^{2}}\prod^{d}_{j=k+1}\tanh(\beta)$
$\displaystyle\leq\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sum^{d}_{k=2}\prod^{d}_{j=1,j\neq
k}\tanh(\beta)+\frac{\gamma_{j}}{(1-2q)^{2}}$
$\displaystyle\leq\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sum^{d}_{k=2}\prod^{d}_{j=1,j\neq
k}\left(\tanh(\beta)+\frac{1}{6}(1-\tanh^{2}(\beta))\right)$
$\displaystyle=\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}(d-1)\left(\frac{5}{3}-\frac{1}{6}(\tanh(\beta)-3)^{2}\right)^{d-1}$
$\displaystyle\leq\tanh^{2}(\beta)\frac{(1-(1-2q)^{2})\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\frac{1}{-e\log\left(\frac{5}{3}-\frac{1}{6}(\tanh(\beta)-3)^{2}\right)}$
$\displaystyle\leq\frac{(1-(1-2q)^{2})\tanh^{2}(\beta)\tilde{\gamma}}{1-(1-2q)^{4}\tanh^{2}(\beta)}e^{2\beta-1}.$
$\displaystyle\leq\frac{(1-(1-2q)^{2})\tanh^{2}(\beta)e^{2\beta}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\sqrt{\frac{3\log(2p^{3}/\delta)}{n}}\triangleq\Delta,$
(205)

(202), (203) , (204) come from Lemma D.2 and (201). Finally,
$0<\frac{5}{3}-\frac{1}{6}(\tanh(\beta)-3)^{2}<1$ for all $\beta>0$ and
$-1/\log\left(\frac{5}{3}-\frac{1}{6}(\tanh(\beta)-3)^{2}\right)\leq
e^{2\beta}$.

We use the symbol $\mathbb{E}_{\mathcal{A}_{k-1}}[\cdot]$ to denote the
conditional expectation given the the event
$\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})$, for instance

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{k}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right]\equiv\mathbb{E}_{\mathcal{A}_{k-1}}\left[\exp\left(\lambda\sum^{k}_{i=1}M^{\dagger}_{i}\right)\right].$
(206)

Further we define the function $F(\cdot,\cdot)$ as

$\displaystyle F(t,\lambda)=\log\left(\frac{1}{1+t}e^{-\lambda
t}+\frac{t}{1+t}e^{\lambda}\right).$ (207)

For any $k\leq d$ we have,

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{k}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right]$
$\displaystyle=\mathbb{E}_{\mathcal{A}_{k-1}}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\mathbb{E}\left[\exp\left(\lambda
M^{\dagger}_{k}\right)\Bigg{|}\hat{\mu}^{\dagger}_{1},\ldots,\hat{\mu}^{\dagger}_{k-1}\right]\right]$
(208)
$\displaystyle=\mathbb{E}_{\mathcal{A}_{k-1}}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\mathbb{E}\left[\exp\left(\lambda\frac{1}{n}\sum^{n}_{i=1}Z^{(i)}_{k}\right)\Bigg{|}\hat{\mu}^{\dagger}_{1},\ldots,\hat{\mu}^{\dagger}_{k-1}\right]\right]$
(209)
$\displaystyle=\mathbb{E}_{\mathcal{A}_{k-1}}\Bigg{[}\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)$
$\displaystyle\qquad\times\mathbb{E}\left[\exp\left(\lambda\frac{1}{n}\sum^{n}_{i=1}\xi^{(i)}_{k}\right)\exp\left(\lambda\frac{1}{n}\sum^{n}_{i=1}\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)\Bigg{|}\hat{\mu}^{\dagger}_{1},\ldots,\hat{\mu}^{\dagger}_{k-1}\right]\Bigg{]}$
(210)
$\displaystyle\leq\exp\left(\lambda\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)$
$\displaystyle\qquad\times\mathbb{E}_{\mathcal{A}_{k-1}}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\mathbb{E}\left[\exp\left(\lambda\frac{1}{n}\sum^{n}_{i=1}\xi^{(i)}_{k}\right)\Bigg{|}\hat{\mu}^{\dagger}_{1},\ldots,\hat{\mu}^{\dagger}_{k-1}\right]\right]$
(211)
$\displaystyle\leq\exp\left(\lambda\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)$
$\displaystyle\qquad\times\mathbb{E}_{\mathcal{A}_{k-1}}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\exp\left\\{n\;F\left(\frac{\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]}{S(\beta,q)^{2}},|\lambda|\frac{S(\beta,q)}{n}\right)\right\\}\right]$
(212)
$\displaystyle\leq\exp\left(\lambda\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)$
$\displaystyle\qquad\times\exp\left\\{n\;F\left(\frac{\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]}{S(\beta,q)^{2}},|\lambda|\frac{S(\beta,q)}{n}\right)\right\\}\mathbb{E}_{\mathcal{A}_{k-1}}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\right]$
(213)

The equation (208) comes from change of measure and tower property, the
definitions (179) and (180) of $M^{\dagger}_{k}$ and $\xi^{(i)}_{k}$
respectively give (209) and (210). The (211) is derived by upper bounding the
quantity
$\left|\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right|$
similarly to (200), (212) is the upper bound on the moment generating function
of the suppermartingale Fan et al. (2012). To get a recurrence

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right]\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right)$
$\displaystyle=\mathbb{E}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\cap\mathrm{E^{edge}_{e_{k-1},\dagger}}\right]\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right)$
$\displaystyle=\mathbb{E}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\cap\mathrm{E^{edge}_{e_{k-1},\dagger}}\right]$
$\displaystyle\qquad\times\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right)\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right)$
$\displaystyle=\mathbb{E}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\cap\mathrm{E^{edge}_{e_{k-1},\dagger}}\right]$
$\displaystyle\qquad\times\mathbb{P}\left(\mathrm{E^{edge}_{e_{k-1},\dagger}}\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right)\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right)$
$\displaystyle=\mathbb{E}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\mathbf{1}_{\mathrm{E^{edge}_{e_{k-1},\dagger}}}\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right]\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right)$
$\displaystyle\leq\mathbb{E}\left[\exp\left(\lambda\sum^{k-1}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right]\mathbb{P}\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-2})\right).$
(214)

By applying the recurrence $d$ times, we derive the following bound

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{k}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right]$
$\displaystyle\leq\exp\left(\lambda\sum^{d}_{k=1}\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)$
$\displaystyle\qquad\times\exp\left\\{n\;\sum^{d}_{k=1}F\left(\frac{\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]}{S(\beta,q)^{2}},|\lambda|\frac{S(\beta,q)}{n}\right)\right\\}$
$\displaystyle\leq\exp\left(\lambda\sum^{d}_{k=1}\mathbb{E}\left[Z^{(i)}_{k}|\mathcal{F}^{k}_{i-1}\right]\right)$
$\displaystyle\qquad\times\exp\left\\{n\;dF\left(\frac{1}{d}\sum^{d}_{k=1}\frac{\mathbb{E}\left[\left(\xi^{(i)}_{k}\right)^{2}\Bigg{|}\mathcal{F}^{k}_{i-1}\right]}{S(\beta,q)^{2}},|\lambda|\frac{S(\beta,q)}{n}\right)\right\\}.$
(215)

Further (199), (200), (205) and (215) give

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{k}_{i=1}M^{\dagger}_{i}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{k-1})\right]$
$\displaystyle\leq\exp\left(\lambda\Delta(\beta,q)\right)\exp\left\\{nd\;F\left(\frac{1}{d}\frac{G(\beta,q)}{S^{2}_{\xi}(\beta,q)},|\lambda|\frac{S(\beta,q)}{n}\right)\right\\}$
$\displaystyle\leq\exp\left\\{nd\;F\left(\frac{G(\beta,q)}{d},|\lambda|\frac{S(\beta,q)}{n}\right)+\lambda\Delta(\beta,q)\right\\}.$
(216)

For shake of space, we denote the functions $G(\beta,q),$ $S(\beta,q)$, and
$\Delta(\beta,q)$ as $G$, $S$, and $\Delta$ respectively. It is true that

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{d}_{k=1}M^{\dagger}_{k}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]\mathbb{P}\left[\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\cap\mathrm{E}_{q}\right]$
$\displaystyle\leq\exp\left\\{nd\;F\left(\frac{G}{d},|\lambda|\frac{S}{n}\right)+\lambda\Delta\right\\}.$
(217)

Under the assumption $n>\frac{108e^{2\beta}}{(1-2q)^{4}K(\beta,q)}\log(4p)$,
we have

$\displaystyle\mathbb{P}\left[\left(\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right)^{c}\right]\leq\frac{1}{2}.$
(218)

The latter gives

$\displaystyle\mathbb{E}\left[\exp\left(\lambda\sum^{d}_{k=1}M^{\dagger}_{k}\right)\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]\leq
2\exp\left\\{nd\;F\left(\frac{G}{d},|\lambda|\frac{S}{n}\right)+\lambda\Delta\right\\},$
(219)

which implies that

$\displaystyle\mathbb{P}\left[\sum^{d}_{k=1}M^{\dagger}_{k}\geq\gamma\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]$
$\displaystyle\leq
2\min_{\lambda>0}\exp\left\\{nd\;F\left(\frac{G}{d},\lambda\frac{S}{n}\right)+\lambda\Delta-\lambda\gamma\right\\}$
$\displaystyle=2\min_{\lambda>0}\exp\left\\{nd\;F\left(\frac{G}{d},\lambda\frac{S}{n}\right)+\lambda\left(\Delta-\gamma\right)\right\\},$
(220)

and we define $\gamma^{\prime}\triangleq\gamma-\Delta$. The minimum value is
attained at

$\displaystyle\lambda^{*}$
$\displaystyle=\frac{n/S}{1+G/d}\log\frac{1+\frac{\gamma^{\prime}}{GS}}{1-\frac{\gamma^{\prime}}{dS}},$
(221)

by substituting the optimal value we get

$\displaystyle\exp\left\\{nd\;F\left(\frac{G}{d},\lambda^{*}\frac{S}{n}\right)-\lambda^{*}\gamma^{\prime}\right\\}$
$\displaystyle=\left[\frac{1}{1+\frac{G}{d}}\left(\frac{1+\frac{\gamma^{\prime}}{GS}}{1-\frac{\gamma^{\prime}}{dS}}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}+\frac{\frac{G}{d}}{1+\frac{G}{d}}\left(\frac{1+\frac{\gamma^{\prime}}{Gy}}{1-\frac{\gamma^{\prime}}{dS}}\right)^{\frac{1}{1+G/d}\left(1-\frac{\gamma^{\prime}}{Sd}\right)}\right]^{nd}$
$\displaystyle=\Bigg{[}\frac{1}{1+\frac{G}{d}}\left(1+\frac{\gamma^{\prime}}{GS}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{\frac{G/d}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}$
$\displaystyle\qquad+\frac{\frac{G}{d}}{1+\frac{G}{d}}\left(1+\frac{\gamma^{\prime}}{GS}\right)^{\frac{1}{1+G/d}\left(1-\frac{\gamma^{\prime}}{Sd}\right)}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{-\frac{1}{1+G/d}\left(1-\frac{\gamma^{\prime}}{Sd}\right)}\Bigg{]}^{nd}$
$\displaystyle=\Bigg{[}\frac{1}{1+\frac{G}{d}}\left(1+\frac{\gamma^{\prime}}{GS}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{\frac{G/d}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}-1}\left(1-\frac{\gamma^{\prime}}{dS}\right)$
$\displaystyle\qquad+\frac{\frac{G}{d}}{1+\frac{G}{d}}\left(1+\frac{\gamma^{\prime}}{GS}\right)^{\frac{1}{1+G/d}\left(1-\frac{\gamma^{\prime}}{Sd}\right)-1}\left(1+\frac{\gamma^{\prime}}{GS}\right)\left(1-\frac{\gamma^{\prime}}{dS}\right)^{-\frac{1}{1+G/d}\left(1-\frac{\gamma^{\prime}}{Sd}\right)}\Bigg{]}^{nd}$
$\displaystyle=\Bigg{[}\frac{1}{1+\frac{G}{d}}\left(1-\frac{\gamma^{\prime}}{dS}\right)+\frac{\frac{G}{d}}{1+\frac{G}{d}}\left(1+\frac{\gamma^{\prime}}{GS}\right)\Bigg{]}^{nd}$
$\displaystyle\qquad\times\left[\left(1+\frac{\gamma^{\prime}}{GS}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{\frac{G/d}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}-1}\right]^{nd}$
$\displaystyle=1^{nd}\times\left[\left(1+\frac{\gamma^{\prime}}{GS}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{\frac{G/d}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}-1}\right]^{nd}$
$\displaystyle=\left[\left(1+\frac{\gamma^{\prime}}{GS}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{\frac{-1}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\right]^{nd}.$
(222)

Then (220) and (222) give

$\displaystyle\mathbb{P}\left[\sum^{d}_{k=1}M^{\dagger}_{k}\geq\gamma\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]$
$\displaystyle\qquad\leq
2\left[\left(1+\frac{\gamma^{\prime}}{GS}\right)^{-\frac{G/d}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\left(1-\frac{\gamma^{\prime}}{dS}\right)^{\frac{-1}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}}\right]^{nd}.$
(223)

As a final step we want to express the upper bound as an exponential function
of $\gamma$, we define $\zeta\triangleq\gamma^{\prime}/(SG)$ and we proceed as
follows

$\displaystyle
d\left[\left(\frac{G/d}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}\right)\log\left(1+\frac{\gamma^{\prime}}{GS}\right)+\left(\frac{1}{1+G/4d}-\frac{\gamma^{\prime}/(dy)}{(1+G/4d)}\right)\log\left(1-\frac{\gamma^{\prime}}{dy}\right)\right]$
$\displaystyle\geq
d\Bigg{[}\left(\frac{G/d}{1+G/d}+\frac{\gamma^{\prime}/(dS)}{(1+G/d)}\right)\left(\frac{\gamma^{\prime}}{GS}-\frac{1}{2}\left[\frac{\gamma^{\prime}}{GS}\right]^{2}\right)$
$\displaystyle\qquad-\left(\frac{1}{1+G/d}-\frac{\gamma^{\prime}/(dS)}{(1+G/d)}\right)\log\left(1+\frac{\gamma^{\prime}/dS}{1-\gamma^{\prime}/dS}\right)\Bigg{]}$
$\displaystyle\geq\Bigg{[}\left(\frac{dG}{d+G}+\frac{d\gamma^{\prime}/S}{(d+G)}\right)\left(\frac{\gamma^{\prime}}{GS}-\frac{1}{2}\left[\frac{\gamma^{\prime}}{GS}\right]^{2}\right)$
$\displaystyle\qquad-\left(\frac{d^{2}}{d+G}-\frac{d\gamma^{\prime}/S}{(d+G)}\right)\left(\frac{\gamma^{\prime}/dS}{1-\gamma^{\prime}/dS}-\frac{1}{2}\left(\frac{\gamma^{\prime}/dS}{1-\gamma^{\prime}/dS}\right)^{2}\right)\Bigg{]}$
$\displaystyle=\frac{d}{d+G}\Bigg{[}\left(G+\gamma^{\prime}/S\right)\left(\frac{\gamma^{\prime}}{GS}-\frac{1}{2}\left[\frac{\gamma^{\prime}}{GS}\right]^{2}\right)$
$\displaystyle\qquad-\left(d-\gamma^{\prime}/S\right)\left(\frac{\gamma^{\prime}/dS}{1-\gamma^{\prime}/dS}-\frac{1}{2}\left(\frac{\gamma^{\prime}/dS}{1-\gamma^{\prime}/dS}\right)^{2}\right)\Bigg{]}$
$\displaystyle\geq\frac{d}{d+G}\left[\left(G+\gamma^{\prime}/S\right)\left(\frac{\gamma^{\prime}}{GS}-\frac{1}{2}\left[\frac{\gamma^{\prime}}{GS}\right]^{2}\right)-\gamma^{\prime}/S\right]$
$\displaystyle=\frac{dG}{d+G}\left[\left(1+\gamma^{\prime}/(SG)\right)\left(\frac{\gamma^{\prime}}{GS}-\frac{1}{2}\left[\frac{\gamma^{\prime}}{GS}\right]^{2}\right)-\gamma^{\prime}/(SG)\right]$
$\displaystyle=\frac{dG}{d+G}\left[\left(1+\zeta\right)\left(\zeta-\frac{1}{2}\zeta^{2}\right)-\zeta\right]$
$\displaystyle\geq\frac{2G}{2+G}\left[\left(1+\zeta\right)\left(\zeta-\frac{1}{2}\zeta^{2}\right)-\zeta\right]$
$\displaystyle\leq\left(\frac{3\gamma^{\prime}}{10GS}\right)^{2},\quad\forall\gamma^{\prime}\in(0,\frac{SG}{3}),$
(224)

recall that $\zeta\triangleq\gamma^{\prime}/(SG)$,
$\gamma^{\prime}=\gamma-\Delta$. If $\Delta<\gamma\leq
S(\beta,q)G(\beta,q)/3+\Delta$ then (223) and (224) give

$\displaystyle\mathbb{P}$
$\displaystyle\left[\sum^{d}_{k=1}M^{\dagger}_{k}\geq\gamma\Bigg{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]\leq
2\exp\left(-0.3^{2}n\frac{\left(\gamma-\Delta\right)^{2}}{S^{2}(\beta,q)G^{2}(\beta,q)}\right).$
(225)

In a similar way we derive the bound

$\displaystyle\mathbb{P}\left[\sum^{d}_{k=1}M^{\dagger}_{k}\leq-\gamma\big{|}\mathrm{E}^{\mathrm{edge}}_{\dagger}(\mathcal{A}_{d-1})\right]\leq
2\exp\left(-0.3^{2}n\frac{\left(\gamma-\Delta\right)^{2}}{S^{2}(\beta,q)G^{2}(\beta,q)}\right).$
(226)

Finally, we combine (177), Lemma D.2, (225) and (226) to derive the bound
(174) which guarantees that

$\displaystyle\mathbb{P}\left[\left|\prod^{d}_{i=1}\frac{\hat{\mu}^{\dagger}_{i}}{(1-2q)^{2}}-\prod^{d}_{i=1}\frac{\mu^{\dagger}_{i}}{(1-2q)^{2}}\right|>\gamma\right]\leq
2\delta/p^{2},\quad\forall d\geq 2.$ (227)

To summarize we proved that the event
$\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)$ happens
with probability at least $1-2\delta/p^{2}$ by combining Bresler’s and
Karzand’s technique, the Corollary 2.3 by Fan et al. (2012) and Lemma D.1.

##  E Predictive Learning, Proof of Theorem 1.3 and Theorem 3.3

Recall that our goal is to guarantee that the quantity
$\mathcal{L}^{(2)}(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger}))$
is smaller than a number $\eta>0$ with probability at least $1-\delta$. To do
this, we use the triangle inequality as

$\displaystyle\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})\right)\leq\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)\right)+\mathcal{L}^{(2)}\left(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})\right),$
(228)

and we find the required number of samples such that each of the terms
$\mathcal{L}^{(2)}(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right))$
and
$\mathcal{L}^{(2)}(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger}))$
in (228) is less than $\eta/2$ with probability at least $1-\delta$. The next
Lemma provides the necessary bounds on $\gamma_{\dagger}$ and
$\epsilon_{\dagger}$ that guarantee

$\mathcal{L}^{(2)}(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger}))\leq\eta/2.$

###### Lemma E.1

If $\gamma_{\dagger}\leq\frac{\eta}{3}$ and

$\displaystyle\epsilon_{\dagger}\leq(1-2q)^{2}e^{-\beta}\left[20\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)\right]^{-1}$

then
$\mathcal{L}^{(2)}(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger}))\leq\eta/2$
under the event
$\mathrm{E}_{\dagger}^{\text{corr}}\left(\epsilon_{\dagger}\right)\cap\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)\cap\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)$.

Proof  The derivation of the bound is similar to the approach by Bresler and
Karzand (2018, Section 6.1). In the hidden model, we consider the path between
two nodes $i,j$ in the estimated structure $\mathrm{T}^{\text{CL}}_{\dagger}$,
namely $\text{path}_{\mathrm{T}^{\text{CL}}_{\dagger}}(i,j)$, to be
$(\mathcal{F}_{0},e_{1},\mathcal{F}_{1},e_{1}...,\mathcal{F}_{t-1},e_{t},\mathcal{F}_{t})$,
and $\mathcal{F}_{i}$ are segments with all strong edges and $e_{i}$ are all
weak edges. We consider the case of at least one weak edge to exist in the
path. If there is no weak edge the bound reduces to the case of Lemma D.3. The
length of each sub-path $\mathcal{F}_{i}$ is denoted as $d_{i}$, for all
$i\in\\{0,1,\ldots,t\\}$. Each segment (sub-path) $\mathcal{F}_{i}$ has
exactly $d_{i}$ edges, and the total number of edges in the path are $d$; thus
$d=\sum^{t}_{i=0}d_{i}+t$. Note that $t\geq 1$ and $d_{i}\geq 0$ for all
$i\in\\{0,1,\ldots,t\\}$. Recall that

$\displaystyle\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)$
$\displaystyle=\frac{1}{2}\prod_{\left(i,j\right)\in\mathcal{E}_{\mathrm{T}^{\text{CL}}_{\dagger}}}\frac{1+x_{i}x_{j}\mathbb{E}\left[X_{i}X_{j}\right]}{2}=\frac{1}{2}\prod_{{\left(i,j\right)\in\mathcal{E}_{\mathrm{T}^{\text{CL}}_{\dagger}}}}\frac{1+x_{i}x_{j}\frac{\mathbb{E}\left[Y_{i}Y_{j}\right]}{\left(1-2q\right)^{2}}}{2}$
(229)

(the latter comes from (19)), and

$\displaystyle\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})$
$\displaystyle\triangleq\frac{1}{2}\prod_{\left(i,j\right)\in\mathcal{E}_{\mathrm{T}^{\text{CL}}_{\dagger}}}\frac{1+x_{i}x_{j}\frac{\mathbb{\hat{E}}\left[Y_{i}Y_{j}\right]}{\left(1-2q\right)^{2}}}{2}.$
(230)

Further, for any tree-structured Ising model distributions $P,\tilde{P}$ with
structures $\mathrm{T}=(\mathcal{V},\mathcal{E})$ and
$\tilde{\mathrm{T}}=(\mathcal{V},\tilde{\mathcal{E}})$ respectively, we have

$\displaystyle\mathcal{L}^{(2)}\left(P,\tilde{P}\right)$
$\displaystyle\triangleq\sup_{i,j\in\mathcal{V}}\quad\frac{1}{2}\sum_{x_{i},x_{j}\in\\{-1,+1\\}^{2}}\left|P(x_{i},x_{j})-\tilde{P}(x_{i},x_{j})\right|$
(231)
$\displaystyle=\sup_{i,j\in\mathcal{V}}\quad\frac{1}{2}\left|\prod_{e\in\mathrm{path}_{\mathrm{T}}\left(i,j\right)}\mu_{e}-\prod_{e^{\prime}\in\mathrm{path}_{\tilde{\mathrm{T}}}\left(i,j\right)}\tilde{\mu}_{e^{\prime}}\right|.$
(232)

To upper bound the quantity
$\mathcal{L}^{(2)}(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger}))$
we have

$\displaystyle
2\mathcal{L}^{(2)}\left(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})\right)$
$\displaystyle=\left|\prod_{e\in\mathrm{path}_{\text{$\mathrm{T}^{\text{CL}}_{\dagger}$}}\left(i,j\right)}\frac{\mu^{\dagger}_{e}}{\left(1-2q\right)^{2}}-\prod_{e\in\mathrm{path}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(i,j\right)}\frac{\hat{\mu}^{\dagger}_{e}}{\left(1-2q\right)^{2}}\right|$
$\displaystyle=\frac{1}{(1-2q)^{2d}}\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{0}}\prod_{i=1}^{t}\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}\hat{\mu}^{\dagger}_{e_{i}}-\mu^{\dagger}_{\mathcal{F}_{0}}\prod_{i=1}^{t}\mu^{\dagger}_{\mathcal{F}_{i}}\mu^{\dagger}_{e_{i}}\right|$
(233)
$\displaystyle\leq\frac{1}{(1-2q)^{2d}}\Bigg{[}\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{0}}-\mu^{\dagger}_{\mathcal{F}_{0}}\right|\prod_{j=1}^{t}\left|\mu^{\dagger}_{\mathcal{F}_{i}}\mu^{\dagger}_{e_{i}}\right|$
$\displaystyle\qquad+\sum_{i=1}^{t}\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}\hat{\mu}^{\dagger}_{e_{i}}-\mu^{\dagger}_{\mathcal{F}_{i}}\mu^{\dagger}_{e_{i}}\right|\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{0}}\right|\prod_{j=1}^{i-1}\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{j}}\hat{\mu}^{\dagger}_{e_{j}}\right|\prod_{k=i+1}^{t}\left|\mu^{\dagger}_{\mathcal{F}_{k}}\mu^{\dagger}_{e_{k}}\right|\Bigg{]}$
(234)
$\displaystyle\leq\frac{\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{0}}-\mu^{\dagger}_{\mathcal{F}_{0}}\right|}{(1-2q)^{2d_{0}}}\prod_{j=1}^{t}\left|\frac{\mu^{\dagger}_{\mathcal{F}_{i}}}{(1-2q)^{2d_{i}}}\frac{\mu^{\dagger}_{e_{i}}}{(1-2q)^{2t}}\right|$
$\displaystyle\qquad+\sum_{i=1}^{t}\frac{\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}\hat{\mu}^{\dagger}_{e_{i}}-\mu^{\dagger}_{\mathcal{F}_{i}}\mu^{\dagger}_{e_{i}}\right|}{(1-2q)^{2(d_{i}+1)}}\frac{|\hat{\mu}^{\dagger}_{\mathcal{F}_{0}}|}{(1-2q)^{2d_{0}}}\frac{\prod_{j=1}^{i-1}\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{j}}\hat{\mu}^{\dagger}_{e_{j}}\right|\prod_{k=i+1}^{t}\left|\mu^{\dagger}_{\mathcal{F}_{k}}\mu^{\dagger}_{e_{k}}\right|}{(1-2q)^{2(d-d_{i}-d_{0}-1)}}$
(235)
$\displaystyle\leq\gamma_{\dagger}\left(\frac{\tau^{\dagger}}{(1-2q)^{2}}\right)^{t-1}+\left(\frac{\tau^{\dagger}+\epsilon_{\dagger}}{(1-2q)^{2}}\right)^{t-1}\sum_{i=1}^{t}\frac{\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}\hat{\mu}^{\dagger}_{e_{i}}-\mu^{\dagger}_{\mathcal{F}_{i}}\mu^{\dagger}_{e_{i}}\right|}{(1-2q)^{2(d_{i}+1)}}$
(236)
$\displaystyle\leq\gamma_{\dagger}\left(\frac{\tau^{\dagger}}{(1-2q)^{2}}\right)^{t-1}+\left(\frac{\tau^{\dagger}+\epsilon_{\dagger}}{(1-2q)^{2}}\right)^{t-1}\sum_{i=1}^{t}\left(\frac{\left|(\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}-\mu^{\dagger}_{\mathcal{F}_{i}})\hat{\mu}^{\dagger}_{e_{i}}\right|}{(1-2q)^{2(d_{i}+1)}}+\frac{\left|\mu^{\dagger}_{\mathcal{F}_{i}}(\hat{\mu}^{\dagger}_{e_{i}}-\mu^{\dagger}_{e_{i}})\right|}{(1-2q)^{2(d_{i}+1)}}\right)$
$\displaystyle\leq\gamma_{\dagger}\left(\frac{\tau^{\dagger}}{(1-2q)^{2}}\right)^{t-1}+\left(\frac{\tau^{\dagger}+\epsilon_{\dagger}}{(1-2q)^{2}}\right)^{t-1}\sum_{i=1}^{t}\left(\gamma_{\dagger}+\frac{\epsilon_{\dagger}}{(1-2q)^{2}}\right)$
(237)
$\displaystyle\leq\left(\frac{\tau^{\dagger}+\epsilon_{\dagger}}{(1-2q)^{2}}\right)^{t-1}(2t+1)\max\left\\{\gamma_{\dagger},\frac{\epsilon_{\dagger}}{(1-2q)^{2}}\right\\}$
$\displaystyle\leq\left(\frac{4\epsilon_{\dagger}e^{\beta}\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)+\epsilon_{\dagger}}{(1-2q)^{2}}\right)^{t-1}(2t+1)\max\left\\{\gamma_{\dagger},\frac{\epsilon_{\dagger}}{(1-2q)^{2}}\right\\}$
(238)
$\displaystyle\leq\left(\frac{5\epsilon_{\dagger}e^{\beta}}{(1-2q)^{2}}\right)^{t-1}\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{t-1}(2t+1)\max\left\\{\gamma_{\dagger},\frac{\epsilon_{\dagger}}{(1-2q)^{2}}\right\\}$
$\displaystyle\leq\frac{2t+1}{4^{t-1}}\frac{\eta}{3}$ (239)
$\displaystyle\leq\eta.$ (240)

Telescoping summation and triangle inequality give (233) and (234). We use the
definition of $d$, $d=\sum^{t}_{i=0}d_{i}+t$ to get (235) and the inequalities
$\left|\mu^{\dagger}_{\mathcal{F}_{i}}\right|\leq(1-2q)^{2d_{i}},$
$\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}\right|\leq(1-2q)^{2d_{i}},$
$\left|\mu^{\dagger}_{e_{i}}\right|\leq\tau^{\dagger}$,
$\left|\hat{\mu}^{\dagger}_{e_{i}}\right|\leq\tau^{\dagger}+\epsilon_{\dagger}$,
which hold under
$\mathrm{E}_{\dagger}^{\text{corr}}\left(\epsilon_{\dagger}\right)$,
$\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)$.
Further, under event
$\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)$ (Lemma
D.3) it is true that
$\left|\hat{\mu}^{\dagger}_{\mathcal{F}_{i}}-\mu^{\dagger}_{\mathcal{F}_{i}}\right|\leq\gamma_{\dagger}$,
the latter gives (236) and (237). The bound $\tau^{\dagger}\leq
4\epsilon_{\dagger}e^{\beta}(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta})$
gives (238) (see (141)). Inequality (239) requires

$\displaystyle\max\left\\{\frac{\epsilon_{\dagger}}{(1-2q)^{2}},\gamma_{\dagger}\right\\}\leq\frac{\eta}{3},$
(241)

and

$\displaystyle\epsilon_{\dagger}\leq(1-2q)^{2}e^{-\beta}\left[20\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)\right]^{-1}.$
(242)

Finally 240 holds for all $t\in\mathbb{N}$. The latter completes the proof.

The next Lemma provides the set of values of $\epsilon_{\dagger}$ that
guarantee
$\mathcal{L}^{(2)}(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\mathrm{p}(\cdot)))\leq\frac{\eta}{2}$
with high probability.

###### Lemma E.2

If

$\displaystyle\epsilon_{\dagger}\leq\min\left\\{\frac{\eta}{16}(1-2q)^{2},\frac{(1-2q)^{2}e^{-\beta}}{24\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)}\right\\}.$
(243)

then
$\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)\right)\leq\frac{\eta}{2}$
under the event
$\mathrm{E}_{\dagger}^{\text{corr}}\left(\epsilon_{\dagger}\right)\cap\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)$.

Proof  Recall that

$\displaystyle\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)\right)$
$\displaystyle=\frac{1}{2}\left|\prod_{e\in\text{path}_{\mathrm{T}}(w,\tilde{w})}\frac{\mu^{\dagger}_{e}}{(1-2q)^{2}}-\prod_{e\in\text{path}_{\mathrm{T}^{\text{CL}}_{\dagger}}(w,\tilde{w})}\frac{\mu^{\dagger}_{e}}{(1-2q)^{2}}\right|$
$\displaystyle=\frac{1}{2}\left|\prod_{e\in\text{path}_{\mathrm{T}}(w,\tilde{w})}\mu_{e}-\prod_{e\in\text{path}_{\mathrm{T}^{\text{CL}}_{\dagger}}(w,\tilde{w})}\mu_{e}\right|.$
(244)

We follow Bresler’s and Karzand’s technique ”Loss due to graph estimation”
(Bresler and Karzand, 2018, Lemma 6.1) and we refer the difference that
appears in our setting. For the noisy case/hidden model, the argument changes
slightly in the following manner:

$\displaystyle
2\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)\right)$
$\displaystyle\leq|\mu_{f}\mu_{A}\mu_{\tilde{A}}\mu_{B}\mu_{\tilde{B}}||\mu^{2}_{C}\mu^{2}_{\tilde{C}}-1|+|\mu_{f}|\left(\Delta(k)+\Delta(\tilde{k})+\Delta(\tilde{k})\Delta(k)\right)$
$\displaystyle=\left|\frac{\mu^{\dagger}_{f}}{(1-2q)^{2}}\mu_{A}\mu_{\tilde{A}}\mu_{B}\mu_{\tilde{B}}\right|\left|\mu^{2}_{C}\mu^{2}_{\tilde{C}}-1\right|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left|\frac{\mu^{\dagger}_{f}}{(1-2q)^{2}}\right|\left(\Delta(k)+\Delta(\tilde{k})+\Delta(\tilde{k})\Delta(k)\right)$
$\displaystyle\leq
8\frac{\epsilon_{\dagger}}{(1-2q)^{2}}+\frac{\tau^{\dagger}}{(1-2q)^{2}}(2\eta+\eta^{2})$
(245) $\displaystyle\leq\eta.$ (246)

(245) holds since $|\mu^{\dagger}_{f}|-|\mu^{\dagger}_{g}|\leq
4\epsilon_{\dagger}$,
$|\mu_{f}|\left(1-\mu^{2}_{C}\mu^{2}_{\tilde{C}}\right)\leq
2|\mu_{f}|-2|\mu_{g}|$, $|\mu^{\dagger}_{f}|\leq\tau^{\dagger}$, and (246)
holds for all the values of $\epsilon_{\dagger}$ that satisfy

$\displaystyle\epsilon_{\dagger}\leq\min\left\\{\frac{\eta}{16}(1-2q)^{2},\frac{(1-2q)^{2}e^{-\beta}}{24\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)}\right\\}.$
(247)

The latter provides the statement of the Lemma.

The next Theorem provides the sufficient number of samples for predictive
learning that recovers exactly the noiseless setting for $q=0$. Note that the
dependence on $\beta$ changes from $e^{2\beta}$ to $e^{4\beta}$ when the data
are noisy. A key component of the bound is the following function

$\displaystyle\Gamma(\beta,q)\triangleq\left(\frac{1-(1-2q)^{2}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\right)^{2},\quad\beta>0\text{
and }q\in[0,1/2).$ (248)

Note that $\Gamma(\beta,q)\in[0,1]$ for all $\beta>0$ and $q\in[0,1/2)$, and
$\Gamma(\beta,0)=0$ for all $\beta>0$. Further we define

$\displaystyle
B(\beta,q)\triangleq\max\left\\{\frac{1}{K(\beta,q)},\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{2}\right\\},$
(249)

and the expression of $K(\beta,q)$ is given by (172).

###### Theorem E.3

Fix $\delta\in(0,1)$. Choose $\eta>0$ (independent of $\delta$). If

$\displaystyle n\geq$
$\displaystyle\max\Bigg{\\{}\frac{512}{\eta^{2}(1-2q)^{4}},\frac{1152e^{2\beta}B(\beta,q)}{(1-2q)^{4}},\frac{48e^{4\beta}}{\eta^{2}}\Gamma(\beta,q)\Bigg{\\}}\log\left(\frac{6p^{3}}{\delta}\right),$
(250)

then

$\displaystyle\mathbb{P}\left(\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{p}_{\dagger})\right)\leq\eta\right)\geq
1-\delta.$ (251)

Additionally, as a consequence of (250) , if

$\displaystyle n\geq$
$\displaystyle\max\Bigg{\\{}\frac{512}{\eta^{2}(1-2q)^{4}},\frac{1152\left(1+3\sqrt{q}\right)^{2}e^{2\beta(1+\mathds{1}_{q\neq
0})}}{(1-2q)^{4}},\frac{48e^{4\beta}}{\eta^{2}}\mathds{1}_{q\neq
0}\Bigg{\\}}\log\left(\frac{6p^{3}}{\delta}\right).$ (252)

then

$\displaystyle\mathbb{P}\left(\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{p}_{\dagger})\right)\leq\eta\right)\geq
1-\delta.$ (253)

Proof Recall that

$\displaystyle\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)\right)=\frac{1}{2}\left|\prod_{e\in\text{path}_{\mathrm{T}}(w,\tilde{w})}\mu_{e}-\prod_{e\in\text{path}_{\mathrm{T}^{\text{CL}}_{\dagger}}(w,\tilde{w})}\mu_{e}\right|.$
(254)

We combine the triangle inequality

$\displaystyle\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})\right)\leq\mathcal{L}^{(2)}\left(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right)\right)+\mathcal{L}^{(2)}\left(\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}\left(\mathrm{p}(\cdot)\right),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})\right),$
(255)

Lemma E.1 and Lemma E.2 to get that
$\mathcal{L}^{(2)}(\mathrm{p}(\cdot),\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger}))\leq\eta$
with probability at least $1-\delta$ if

$\displaystyle\gamma_{\dagger}\leq\frac{\eta}{3}\text{ and
}\epsilon_{\dagger}\leq\min\left\\{\frac{\eta}{16}(1-2q)^{2},\frac{(1-2q)^{2}e^{-\beta}}{24\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)}\right\\}.$
(256)

First, we find the necessary number of samples such that for
$\gamma_{\dagger}\leq\eta/3$ the probability of the complement of
$\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)$ is not
greater than $\delta/3$. Recall that

$\displaystyle G$
$\displaystyle\triangleq\frac{3\left(3e^{-1}\mathds{1}_{q\neq
0}+1\right)}{4(1-2q)^{2}},$ (257) $\displaystyle S$ $\displaystyle\triangleq
3-(1-2q)^{2}.$ (258)

Recall that

$\displaystyle\Gamma(\beta,q)\triangleq\left(\frac{1-(1-2q)^{2}}{1-(1-2q)^{4}\tanh^{2}(\beta)}\right)^{2},\quad\beta>0\text{
and }q\in[0,1/2).$ (259)

Lemma D.3 gives that for any $\Delta>0$ and $\eta>\Delta$ if

$\displaystyle
n\geq\max\left\\{\frac{0.3^{-2}S^{2}G^{2}}{(\eta-\Delta)^{2}},\frac{108e^{2\beta}}{(1-2q)^{4}K(\beta,q)},\frac{3e^{4\beta}}{\Delta^{2}}\Gamma(\beta,q)\right\\}\log\left(\frac{6p^{3}}{\delta}\right),$
(260)

then the probability of the complement of
$\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)$ is upper
bounded by $\delta/3$ and we write

$\displaystyle\mathbb{P}\left(\left(\mathrm{E}_{\dagger}^{\text{cascade}}\left(\gamma_{\dagger}\right)\right)^{c}\right)\leq\frac{\delta}{3}.$
(261)

Second, we find the necessary number of samples such that the complements of
the events
$\mathrm{E}_{\dagger}^{\text{strong}}\left(\epsilon_{\dagger}\right)$ and
$\mathrm{E}_{\dagger}^{\text{corr}}\left(\epsilon_{\dagger}\right)$ occur with
probability not greater than $\delta/3$ each. In fact the upper bound on
$\epsilon_{\dagger}$ (256) and Lemma B.1 gives that if

$\displaystyle
n\geq\max\left\\{\frac{512}{\eta^{2}(1-2q)^{4}},\frac{1152e^{2\beta}}{(1-2q)^{4}}\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{2}\right\\}\log\left(\frac{6p^{3}}{\delta}\right),$
(262)

then $\epsilon_{\dagger}$ satisfies the inequality in (256) with probability
at least $1-\delta/3$. Note that (260) holds for any $\Delta\in(0,\eta)$ and
we will choose $\Delta=\eta/4$. Under the choice $\Delta=\eta/4$

$\displaystyle\frac{0.3^{-2}S^{2}G^{2}}{(\eta-\Delta)^{2}}=\frac{0.3^{-2}S^{2}G^{2}}{(\eta-\eta/4)^{2}}<\frac{512}{\eta^{2}},\quad\forall\eta>0,q\in[0,1/2).$
(263)

Recall that

$\displaystyle
B(\beta,q)\triangleq\max\left\\{\frac{1}{K(\beta,q)},\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{2}\right\\}.$
(264)

(260), (262), (263) and (264) give

$\displaystyle n\geq$
$\displaystyle\max\Bigg{\\{}\frac{512}{\eta^{2}(1-2q)^{4}},\frac{1152e^{2\beta}B(\beta,q)}{(1-2q)^{4}},\frac{48e^{4\beta}}{\eta^{2}}\Gamma(\beta,q)\Bigg{\\}}\log\left(\frac{6p^{3}}{\delta}\right).$
(265)

The latter gives the samples complexity for accurate predictive learning, it
reduces exactly to the noiseless setting of prior work by Bresler and Karzand
(2018) and it is continuous because

$\displaystyle\lim_{q\rightarrow
0^{+}}\Gamma(\beta,q)=\Gamma(\beta,0)=0,\quad\forall\beta>0$ (266)

and

$\displaystyle\lim_{q\rightarrow
0^{+}}K(\beta,q)=K(\beta,0)=1,\quad\forall\beta>0$ (267)
$\displaystyle\lim_{q\rightarrow
0^{+}}\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{2}=1$
(268)

thus

$\displaystyle\lim_{q\rightarrow
0^{+}}B(\beta,q)=\Gamma(\beta,0)=1,\quad\forall\beta>0.$ (269)

To derive a simplified version of (265) note that

$\displaystyle\frac{1}{K(\beta,q)}\leq e^{2\beta\mathds{1}_{q\neq 0}}$ (270)

by the definition (172) of $K(\beta,q)$ and

$\displaystyle\left(1+2e^{\beta}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{2}$
$\displaystyle\leq\left(e^{\beta\mathds{1}_{q\neq
0}}+2e^{\beta\mathds{1}_{q\neq
0}}\sqrt{2\left(1-q\right)q\tanh\beta}\right)^{2}$
$\displaystyle\leq\left(1+3\sqrt{q}\right)^{2}e^{2\beta\mathds{1}_{q\neq 0}}.$
(271)

Then (264), (270) and (271) give

$\displaystyle
B(\beta,q)\leq\left(1+3\sqrt{q}\right)^{2}e^{2\beta\mathds{1}_{q\neq 0}}$
(272)

and by the definition (259) $\Gamma(\beta,q)\in[0,1)$ and $\Gamma(\beta,0)=0$
for all $\beta>0$, thus

$\displaystyle\Gamma(\beta,q)\leq\mathds{1}_{q\neq 0}.$ (273)

Finally, we combine (265), (272), (273) to get

$\displaystyle n\geq$
$\displaystyle\max\Bigg{\\{}\frac{512}{\eta^{2}(1-2q)^{4}},\frac{1152\left(1+3\sqrt{q}\right)^{2}e^{2\beta(1+\mathds{1}_{q\neq
0})}}{(1-2q)^{4}},\frac{48e^{4\beta}}{\eta^{2}}\mathds{1}_{q\neq
0}\Bigg{\\}}\log\left(\frac{6p^{3}}{\delta}\right).$ (274)

The latter completes the proof.

##  F Theorem 3.7: KL-Divergence Loss

Assume the Ising model tree distributions $\text{P}_{\boldsymbol{\theta}}$
according to a tree
$\mathrm{T}_{\boldsymbol{\theta}}=\left(\mathcal{V},\mathcal{E}_{\boldsymbol{\theta}}\right)$
and the estimate $\text{P}_{\boldsymbol{\theta^{\prime}}}$ according a tree
$\mathrm{T}_{\boldsymbol{\theta^{\prime}}}=\left(\mathcal{V},\mathcal{E}_{\boldsymbol{\theta}^{\prime}}\right)$
The goal is to upper bound the symmetric KL divergence

$\displaystyle\boldsymbol{S}_{\text{KL}}\left(\boldsymbol{\theta}||\boldsymbol{\theta}^{\prime}\right)$
$\displaystyle=\sum_{s,t\in\mathcal{E}}\left(\theta_{st}-\theta^{\prime}_{st}\right)\left(\mu_{st}-\mu^{\prime}_{st}\right)$

with high probability. Under the event
$\mathrm{E}^{\text{corr}}\left(\epsilon\right)$ we can upper bound the
quantity $\left|\mu_{st}-\mu^{\prime}_{st}\right|$ for all
$(s,t)\in\mathcal{E}$ with high probability.

By using bounds $\left|\theta_{st}-\theta^{\prime}_{st}\right|\leq 2\beta$ and
$\left|\mu_{st}-\mu^{\prime}_{st}\right|\leq\epsilon$ for all
$(s,t)\in\mathcal{E}$ under the event
$\mathrm{E}^{\text{corr}}\left(\epsilon\right)$ Bresler and Karzand (2018), we
have

$\displaystyle\boldsymbol{S}_{\text{KL}}\left(\boldsymbol{\theta}||\boldsymbol{\theta}^{\prime}\right)$
$\displaystyle=\left|\boldsymbol{S}_{\text{KL}}\left(\boldsymbol{\theta}||\boldsymbol{\theta}^{\prime}\right)\right|$
$\displaystyle=\left|\sum_{s,t\in\mathcal{E}}\left(\theta_{st}-\theta^{\prime}_{st}\right)\left(\mu_{st}-\mu^{\prime}_{st}\right)\right|$
$\displaystyle\leq\sum_{s,t\in\mathcal{E}}\left|\theta_{st}-\theta^{\prime}_{st}\right|\left|\mu_{st}-\mu^{\prime}_{st}\right|$
$\displaystyle\leq(p-1)\left|\beta-(-\beta)\right|\epsilon$
$\displaystyle\leq\eta_{S},$ (275)

by assuming $\epsilon\leq\frac{\eta_{s}}{2\beta(p-1)}$. The sufficient number
of samples satisfies the inequality

$\displaystyle n\geq
4\log\left(p^{2}/\delta\right)\frac{\beta^{2}(p-1)^{2}}{\eta_{s}^{2}}.$ (276)

Now assume that $n_{\dagger}$ samples of $\mathbf{Y}$ are given, by using the
estimate
$\text{P}_{\boldsymbol{\theta^{\prime}}}=\Pi{}_{\mathrm{T}^{\text{CL}}_{\dagger}}(\hat{\mathrm{p}}_{\dagger})$
defined in (230) under the event
$\mathrm{E}_{\dagger}^{\text{corr}}\left(\epsilon_{\dagger}\right)$ we have
$\left|\mu_{st}-\frac{\hat{\mu}^{\dagger}_{st}}{(1-2q)^{2}}\right|\leq\frac{\epsilon_{\dagger}}{(1-2q)^{2}}$
from Lemma B.1. In the same way by assuming
$\epsilon_{\dagger}\leq\frac{\eta_{s}(1-2q)^{2}}{2\beta(p-1)}$, we get

$\displaystyle n_{\dagger}\geq
4\log\left(p^{2}/\delta\right)\frac{\beta^{2}(p-1)^{2}}{(1-2q)^{4}\eta_{s}^{2}}.$
(277)

##  G Theorem 3.2 and Theorem 3.4: Proofs

We combine Fano’s inequality and a Strong Data Processing Inequality to prove
the necessary number of samples in the hidden model setting, first for
structure learning (Theorem 3.2) and then for inference (Theorem 3.4). We use
the following variation of Fano’s inequality.

###### Corollary G.1

(Tsybakov, 2009, Corollary 2.6): Assume that $\Theta$ is a family of $M+1$
distributions $\theta_{0},\theta_{1},\ldots,\theta_{M}$ such that $M\geq 2$.
Let $P_{\theta_{i}}$ be the distribution of the variable $X$ under the model
$\theta_{i}$, if

$\displaystyle\frac{1}{M+1}\sum^{M}_{i=1}\boldsymbol{D}_{\text{KL}}\left(P_{\theta_{i}}||P_{\theta_{0}}\right)\leq\gamma\log
M,\quad\text{for }\gamma\in(0,1)$ (278)

then for the probability of error $p_{e}$ the following inequality holds:
$p_{e}\geq\frac{\log(M+1)-\log(2)}{\log(M)}-\gamma$.

The construction from the noiseless case, with Corollary G.1 and the Strong
Data Processing Inequality for the BSC yield the bound of Theorem 3.2. We
start by presenting Bresler’s and Karzand’s construction Bresler and Karzand
(2018), which gives a sufficiently tight upper bound on symmetric KL
divergence.

Proof of Theorem 3.2: Consider a family of $M+1$ different Ising model
distributions $\\{P_{\theta^{i}}:i\in\\{0,\ldots,M\\}\\}$. This family of the
structured distributions is chosen such that the structure recovery task
(through The Chow-Liu algorithm) is sufficiently hard. First, we define
$P_{\theta^{0}}$ to be an Ising model distribution with underlying structure a
chain with $p$ nodes and parameters $\theta^{0}_{j,j+1}=\alpha$, when $j$ is
odd and $\theta^{0}_{j,j+1}=\beta$ when $j$ is even. The rest of family is
constructed as follows: the elements of each $\theta^{i}$, $i\in[M]$ are equal
to the elements of $\theta^{0}$ apart from two elements $\theta^{i}_{i,i+1}=0$
and $\theta^{i}_{i,i+2}=\operatorname{arctanh}(\tanh(\alpha)\tanh(\beta))$,
for each odd value of $j$. There are $(p+1)/2$ distinct distributions in the
constructed family. Through the expression (42), we derive the following upper
bound on the $\boldsymbol{S}_{\text{KL}}(P_{\theta^{0}}||P_{\theta^{i}})$, for
all $i\in[M]$, (Bresler and Karzand, 2018, Section 7.1),

$\displaystyle\boldsymbol{S}_{\text{KL}}(P_{\theta^{0}}||P_{\theta^{i}})=\alpha\left(\tanh(\alpha)-\tanh(\alpha)\tanh^{2}(\beta)\right)\leq
4\alpha\tanh(\alpha)e^{-2\beta}.$ (279)

Strong Data Processing Inequality: For each distribution $P_{\theta^{i}}$ and
$i\in\\{0,\ldots,M\\}$ we consider the distribution of the noisy variable in
the hidden model $P^{\dagger}_{\theta^{i}}\triangleq
P_{\mathbf{Y}|\mathbf{X}}\circ P_{\theta^{i}}$. We would like to find an upper
bound for the quantities
$\boldsymbol{S}_{\text{KL}}(P^{\dagger}_{\theta^{0}}||P^{\dagger}_{\theta^{i}})$,
$i\in\\{0,\ldots,M\\}$. For that purpose, we a use a strong data processing
inequality result for the BSC by Polyanskiy and Wu (2017). The input random
variable $\mathbf{X}$ is considered to have correlated binary elements, while
the noise variables $N_{i}$ are i.i.d $\mathrm{Rademacher}(q)$. This scheme is
equivalent to the hidden model that we consider in this paper. In fact we have
the following bound

$\displaystyle\eta_{\text{KL}}\leq 1-(4q(1-q))^{p},$ (280)

that is proved by Polyanski (Polyanskiy and Wu, 2017, “Evaluation for the
BSC”, equation (39)), where the quantity $\eta_{\text{KL}}$ is defined as

$\displaystyle\eta_{\text{KL}}\triangleq\sup_{Q}\sup_{P:0<\boldsymbol{D}_{\text{KL}}(P||Q)<\infty}\frac{\boldsymbol{D}_{\text{KL}}\left(P_{\mathbf{Y}|\mathbf{X}}\circ
P||P_{\mathbf{Y}|\mathbf{X}}\circ
Q\right)}{\boldsymbol{D}_{\text{KL}}\left(P||Q\right)},$ (281)

$P_{\mathbf{Y}|\mathbf{X}}$ is the distribution of the BSC and $P,Q$ are any
distributions of the input variable $\mathbf{X}$.

Since the supremum in (281) is with respect to all possible distributions, it
covers any pair of distributions in the desired family
$\\{P_{\theta^{j}}:j\in\\{0,\ldots,M\\}\\}$. Thus, for all
$k,\ell\in\\{0,1,\ldots,M\\}$ and $k\neq\ell$, it is true that

$\displaystyle\frac{\boldsymbol{D}_{\text{KL}}(P^{\dagger}_{\theta^{k}}||P^{\dagger}_{\theta^{\ell}})}{\boldsymbol{D}_{\text{KL}}(P_{\theta^{k}}||P_{\theta^{\ell}})}$
$\displaystyle\leq 1-(4q(1-q))^{p},$ (282)

which comes from (280),(281) and implies the following

$\displaystyle\boldsymbol{S}_{\text{KL}}(P^{\dagger}_{\theta^{k}}||P^{\dagger}_{\theta^{\ell}})$
$\displaystyle\leq[1-(4q(1-q))^{p}]\boldsymbol{S}_{\text{KL}}(P_{\theta^{k}}||P_{\theta^{\ell}}),\quad\forall
k\neq\ell\in\\{0,1,\ldots,M\\}.$ (283)

We combine (279) and (283) to get

$\displaystyle\boldsymbol{S}_{\text{KL}}(P^{\dagger}_{\theta^{k}}||P^{\dagger}_{\theta^{i}})$
$\displaystyle\leq[1-(4q(1-q))^{p}]4\alpha\tanh(\alpha)e^{-2\beta}\leq[1-(4q(1-q))^{p}]4\alpha^{2}e^{-2\beta}.$
(284)

Finally, from (284) and Corollary G.1 we derive the first part of Theorem 3.2.

Proof of Theorem 3.4: Theorem 3.4 is the extended version of Corollary 6.3 by
Bresler and Karzand (2018) to the hidden model. Following a similar technique,
we consider chain structured Ising models with parameters $\theta^{j}$ for
$j\in[M]$ such that $\theta^{j}_{j,j+1}=\alpha$ and
$\theta^{j}_{i,i+1}=\operatorname{arctanh}(\tanh(\alpha)+2\eta)$, for all
$i\neq j$. Then

$\displaystyle\mathcal{L}^{(2)}\left(P_{\theta^{j}},P_{\theta^{j^{\prime}}}\right)=\max_{s,t}\left|\mathbb{E}_{\theta^{j}}[X_{s}X_{t}]-\mathbb{E}_{\theta^{j^{\prime}}}[X_{s}X_{t}]\right|\geq
2\eta$ (285)

and

$\displaystyle\boldsymbol{S}_{\text{KL}}\left(P_{\theta^{j}},P_{\theta^{j^{\prime}}}\right)\leq
2\eta\left[\operatorname{arctanh}(\tanh(\alpha)+2\eta)-\alpha\right]\leq
2\eta\frac{2\eta}{1-\left[\tanh(\alpha)+2\eta\right]^{2}},$ (286)

where the last inequality is a consequence of Mean Value Theorem (see (Bresler
and Karzand, 2018, Corollary 6.3) for the original statement). We derive the
bound of Theorem 3.4 by combining the strong data processing inequality (281)
with (280), (286), and Corollary G.1.

A Structure-Preserving Case: Lemma G.2 considers a special case of tree
structures for the hidden variables, the set of edges is a set with
disconnected edges, no edge is connected to any other. Then we show that the
same structure is preserved for the observable variables.

###### Lemma G.2

Let $G=(\mathcal{V},\mathcal{E}_{G})$ be a graph with $|\mathcal{V}|=p$ and
$|\mathcal{E}_{G}|=\frac{p}{2}\in\mathbb{N}$ such no edge is connected to any
other edge. Assume that $X_{i}\in\\{-1,+1\\}$ and
$\mathbb{E}\left[X_{i}\right]=0$ for all $i\in[1,\ldots,p]$. Since the graph
is a forest its distribution $\mathrm{p}_{G}(\mathbf{x})$ belongs to
$\mathcal{P}_{\mathrm{T}}(0,\beta)$, for some interaction parameters
$\boldsymbol{\theta}$. If $\mathbf{Y}$ is the output of the BSC channel (in
the hidden model) with distribution $\mathrm{p}_{\dagger}(\mathbf{x})$, then
$\mathrm{p}_{\dagger}(\mathbf{x})$ belongs to
$\mathcal{P}_{\mathrm{T}}(0,\operatorname{arctanh}(c^{2}\tanh\beta))$, the
structure of the variables $\mathbf{Y}$ is $G$ and for the parameters
$\boldsymbol{\theta^{\prime}}$ of $\mathrm{p}_{\dagger}(\mathbf{x})$ we have
$\theta^{\prime}_{st}=\operatorname{arctanh}(c^{2}\tanh(\theta_{st}))$, for
all $(s,t)\in\mathcal{E}_{G}$.

Proof  We can start by giving the expression of any distribution of
$\mathbf{x}\in\\{-1,1\\}^{p}$: Using the indicator
$1_{X_{i}=x_{i}}=\frac{1+x_{i}X_{i}}{2}$ we have

$\displaystyle\mathbb{P}(\mathbf{X}=\mathbf{x})$
$\displaystyle=\mathbb{E}\left[\prod_{i}1_{X_{i}=x_{i}}\right]$
$\displaystyle=2^{-p}\Bigg{[}1+\sum_{i_{1}}x_{i_{1}}\mathbb{E}\left[X_{i_{1}}\right]+\sum_{i_{1}<i_{2}}x_{i_{1}}x_{i_{2}}\mathbb{E}\left[X_{i_{1}}X_{i_{2}}\right]+\sum_{i_{1}<i_{2}<i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}\mathbb{E}\left[X_{i_{1}}X_{i_{2}}X_{i_{3}}\right]$
$\displaystyle\qquad\qquad+\ldots+x_{1}x_{2}...x_{p}\mathbb{E}\left[X_{1}X_{2}...X_{p}\right]\Bigg{]}.$
(287)

We assume that a graph $G=(\mathcal{V},\mathcal{E}_{G})$, with
$|\mathcal{V}|=p$, $|\mathcal{E}_{G}|=\frac{p}{2}\in\mathbb{N}$ has no edge
connected to any other edge. We also assume that
$\mathbb{E}\left[X_{i}\right]=0,\forall i\in[1,\ldots,p]$. Then from (287) it
could be

$\displaystyle\mathrm{p}_{G}(\mathbf{x})=\frac{\prod^{p-1}_{i\in
2\mathbb{N}-1}\left(1+x_{i}x_{i+1}\mathbb{E}[X_{i}X_{i+1}]\right)}{2^{p}}$
(288)

as a specific example, or in general it may be written as

$\displaystyle\mathrm{p}_{G}(\mathbf{x})=\frac{\prod^{p-1}_{i\in
2\mathbb{N}-1}\left(1+x_{j_{i}}x_{j_{i+1}}\mathbb{E}[X_{j_{i}}X_{j_{i+1}}]\right)}{2^{p}}$
(289)

where the set of integers $\\{j_{1},j_{2},\ldots,j_{p}\\}$ can be any
permutation of $\\{1,2,\ldots,p\\}$. Since its value of
$i\in\\{1,3,5,\ldots,p-1\\}$ corresponds to an edge we have
$P_{G}(\mathbf{x})\in\mathcal{P}_{\mathrm{T}}(0,\beta)$. For the specific
choice of $G$, by expanding (289) we find the equivalent expression of (287)
as

$\displaystyle\mathrm{p}_{G}\left(\mathbf{x}\right)=\frac{1}{2^{p}}$
$\displaystyle\Bigg{[}1+\underset{i\in
2\mathbb{N}-1}{\sum^{p-1}}x_{j_{i}}x_{j_{i+1}}\mathbb{E}\left[X_{s}X_{t}\right]$
$\displaystyle\qquad+\sum^{p-1}_{i_{1}<i_{2}:i_{1},i_{2}\in
2\mathbb{N}-1}x_{j_{i_{1}}}x_{j_{i_{1}}}x_{j_{i_{2}}}x_{j_{i_{2}+1}}\mathbb{E}\left[X_{j_{i_{1}}}X_{j_{i_{1}+1}}\right]\mathbb{E}\left[X_{j_{i_{2}}}X_{j_{i_{2}+1}}\right]$
$\displaystyle\qquad+\ldots+\prod^{p-1}_{i\in
2\mathbb{N}-1}x_{j_{i}}x_{j_{i+1}}\mathbb{E}\left[\prod^{p-1}_{i=1:i\in
2\mathbb{N}-1}X_{j_{i}}X_{j_{i+1}}\right]\Bigg{]},$ (290)

or equivalently by enumerating the edges we have

$\displaystyle\mathrm{p}_{G}\left(\mathbf{x}\right)=\frac{1}{2^{p}}$
$\displaystyle\Bigg{[}1+\underset{(s,t)\in\mathcal{E}_{G}}{\sum}x_{s}x_{t}\mathbb{E}\left[X_{s}X_{t}\right]+\underset{(s,t)^{2}\in\mathcal{P}(\mathcal{E}_{G})}{\sum}x_{s_{i_{1}}}x_{t_{i_{1}}}x_{s_{i_{2}}}x_{t_{i_{2}}}\mathbb{E}\left[X_{s_{i_{1}}}X_{t_{i_{1}}}\right]\mathbb{E}\left[X_{s_{i_{2}}}X_{t_{i_{2}}}\right]$
$\displaystyle\qquad+\ldots+\prod^{p/2}_{j=1}x_{s_{i_{j}}}x_{t_{i_{j}}}\mathbb{E}\left[\prod^{p/2}_{j=1}X_{s_{i_{j}}}X_{t_{i_{j}}}\right]\Bigg{]},$
(291)

where
$(s,t)^{k}=(s_{i_{1}},t_{i_{1}})\times(s_{i_{2}},t_{i_{2}})\times\ldots\times(s_{i_{k}},t_{i_{k}})\in\mathcal{P}(\mathcal{E}_{G})$.
where the $\mathcal{P}$ symbol is the power set.

For the noisy model that we consider (BSC) the distribution of the channel
output variable
$\mathrm{p}_{\dagger}(\mathbf{y})\notin\mathcal{P}_{\mathrm{T}}(0,\beta)$ when
$\mathrm{p}(\mathbf{x})\in\mathcal{P}_{\mathrm{T}}(0,\beta)$ in the general
case. However, when the structure is the $G$ that is defined above we have
that both distributions of the input and output belong to
$\mathcal{P}_{\mathrm{T}}(0,\beta)$. The probability mass function of
$\mathbf{Y}$ can be found as

$\displaystyle\mathrm{p}_{\dagger}\left(\mathbf{y}\right)=\sum_{\boldsymbol{x,w}:x_{i}w_{i}=y_{i}}\mathrm{p}_{G}\left(\mathbf{x}\right)\mathrm{p}(\boldsymbol{w}),$
(292)

where the probability mass function of the noise is denoted as
$\mathrm{p}(\boldsymbol{w})$. Then, we may write

$\displaystyle\sum_{\boldsymbol{x,w}:x_{i}w_{i}=y_{i}}\mathrm{p}_{G}\left(\mathbf{x}\right)\mathrm{p}(\boldsymbol{w})$
$\displaystyle=$
$\displaystyle\frac{1}{2^{p}}\sum_{\boldsymbol{x,w}:x_{i}w_{i}=y_{i}}\mathrm{p}(\boldsymbol{w})\Bigg{[}1+\underset{(s,t)\in\mathcal{E}_{G}}{\sum}x_{s}x_{t}\mathbb{E}\left[X_{s}X_{t}\right]$
$\displaystyle\quad+\underset{(s,t)^{2}\in\mathcal{P}(\mathcal{E}_{G})}{\sum}x_{s_{i_{1}}}x_{t_{i_{1}}}x_{s_{i_{2}}}x_{t_{i_{2}}}\mathbb{E}\left[X_{s_{i_{1}}}X_{t_{i_{1}}}\right]\mathbb{E}\left[X_{s_{i_{2}}}X_{t_{i_{2}}}\right]+\ldots+\prod^{p/2}_{j=1}x_{s_{i_{j}}}x_{t_{i_{j}}}\mathbb{E}\left[X_{s_{i_{j}}}X_{t_{i_{j}}}\right]\Bigg{]}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{p}}\left[1+c^{2}\underset{(s,t)\in\mathcal{E}_{G}}{\sum}y_{s}y_{t}\mathbb{E}\left[X_{s}X_{t}\right]+c^{4}\underset{(s,t)^{2}\in\mathcal{P}(\mathcal{E}_{G})}{\sum}y_{s_{i_{1}}}y_{t_{i_{1}}}y_{s_{i_{2}}}y_{t_{i_{2}}}\mathbb{E}\left[X_{s_{i_{1}}}X_{t_{i_{1}}}\right]\mathbb{E}\left[X_{s_{i_{2}}}X_{t_{i_{2}}}\right]\right]$
$\displaystyle\quad+\frac{1}{2^{p}}\left[+...+c^{p}\prod^{p/2}_{j=1}y_{s_{i_{j}}}y_{t_{i_{j}}}\mathbb{E}\left[X_{s_{i_{j}}}X_{t_{i_{j}}}\right]\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2^{p}}\left[1+\underset{(s,t)\in\mathcal{E}_{G}}{\sum}y_{s}y_{t}\mathbb{E}\left[Y_{s}Y_{t}\right]+\underset{(s,t)^{2}\in\mathcal{P}(\mathcal{E}_{G})}{\sum}y_{s_{i_{1}}}y_{t_{i_{1}}}y_{s_{i_{2}}}y_{t_{i_{2}}}\mathbb{E}\left[Y_{s_{i_{1}}}Y_{t_{i_{1}}}\right]\mathbb{E}\left[Y_{s_{i_{2}}}Y_{t_{i_{2}}}\right]\right]$
$\displaystyle\quad+\frac{1}{2^{p}}\left[+...+\prod^{p/2}_{j=1}y_{s_{i_{j}}}y_{t_{i_{j}}}\mathbb{E}\left[Y_{s_{i_{j}}}Y_{t_{i_{j}}}\right]\right]$
$\displaystyle=$
$\displaystyle\frac{\prod^{p-1}_{i:\text{odd}}\left(1+y_{j_{i}}y_{j_{i+1}}\mathbb{E}[Y_{j_{i}}Y_{j_{i+1}}]\right)}{2^{p}}.$
(293)

Notice that the distribution of the output is identical to (289) when only the
correlations change from $\mu_{e}$ to $\mu^{\dagger}_{e}=c^{2}\mu_{e}$, for
all $e\in G$ (and $c\triangleq\mathbb{E}[N_{i}]=1-2q$, BSC). From the above
result we conclude that the noisy variable $\mathbf{Y}$ has the same structure
$G$ as $\mathbf{X}$ with weights
$\theta^{\prime}_{st}=\operatorname{arctanh}(c^{2}\tanh(\theta_{st}))$, for
all $(s,t)\in\mathcal{E}$.

## References

  * Anandkumar and Valluvan (2013) Animashree Anandkumar and Ragupathyraj Valluvan.  Learning loopy graphical models with latent variables: Efficient methods and guarantees.  _The Annals of Statistics_ , pages 401–435, 2013.  URL https://www.jstor.org/stable/23566568.
  * Anandkumar et al. (2014) Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky.  Tensor decompositions for learning latent variable models.  _The Journal of Machine Learning Research_ , 15(1):2773–2832, 2014.  URL http://jmlr.org/papers/v15/anandkumar14b.html.
  * Arulampalam et al. (2002) M Sanjeev Arulampalam, Simon Maskell, Neil Gordon, and Tim Clapp.  A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking.  _IEEE Transactions on signal processing_ , 50(2):174–188, 2002.  URL https://www.irisa.fr/aspi/legland/ensta/ref/arulampalam02a.pdf.
  * Banerjee et al. (2008) Onureena Banerjee, Laurent El Ghaoui, and Alexandre d Aspremont.  Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data.  _Journal of Machine learning research_ , 9(Mar):485–516, 2008.  URL http://www.jmlr.org/papers/volume9/banerjee08a/banerjee08a.pdf.
  * Banf and Rhee (2017) Michael Banf and Seung Y Rhee.  Enhancing gene regulatory network inference through data integration with Markov random fields.  _Scientific Reports_ , 7, 2017.  URL https://www.nature.com/articles/srep41174.
  * Barber et al. (2015) Rina Foygel Barber, Mathias Drton, et al.  High-dimensional Ising model selection with bayesian information criteria.  _Electronic Journal of Statistics_ , 9(1):567–607, 2015.  URL https://projecteuclid.org/euclid.ejs/1427203129.
  * Barnett et al. (2013) Lionel Barnett, Joseph T Lizier, Michael Harré, Anil K Seth, and Terry Bossomaier.  Information flow in a kinetic Ising model peaks in the disordered phase.  _Physical review letters_ , 111(17):177203, 2013\.  URL https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.111.177203.
  * Bennett (1962) George Bennett.  Probability inequalities for the sum of independent random variables.  _Journal of the American Statistical Association_ , 57(297):33–45, 1962.  URL https://www.jstor.org/stable/2282438?seq=1#page_scan_tab_contents.
  * Bilodeau (2014) Martin Bilodeau.  Graphical lassos for meta-elliptical distributions.  _Canadian Journal of Statistics_ , 42(2):185–203, 2014.  URL https://www.jstor.org/stable/43185177?seq=1#page_scan_tab_contents.
  * Bresler (2015) Guy Bresler.  Efficiently learning Ising models on arbitrary graphs.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pages 771–782. ACM, 2015.  URL https://arxiv.org/abs/1411.6156.
  * Bresler and Karzand (2018) Guy Bresler and Mina Karzand.  Learning a tree-structured Ising model in order to make predictions.  _arXiv preprint arXiv:1604.06749v3_ , 2018.  URL https://arxiv.org/abs/1604.06749.
  * Castellano et al. (2009) Claudio Castellano, Santo Fortunato, and Vittorio Loreto.  Statistical physics of social dynamics.  _Reviews of modern physics_ , 81(2):591, 2009\.  URL https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.81.591.
  * Chaganty and Liang (2014) Arun Tejasvi Chaganty and Percy Liang.  Estimating latent-variable graphical models using moments and likelihoods.  In _International Conference on Machine Learning_ , pages 1872–1880, 2014.  URL http://proceedings.mlr.press/v32/chaganty14.html.
  * Chandrasekaran et al. (2010) Venkat Chandrasekaran, Pablo A Parrilo, and Alan S Willsky.  Latent variable graphical model selection via convex optimization.  In _Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on_ , pages 1610–1613. IEEE, 2010.  URL https://ieeexplore.ieee.org/document/5707106/.
  * Chow and Liu (1968) C Chow and Cong Liu.  Approximating discrete probability distributions with dependence trees.  _IEEE transactions on Information Theory_ , 14(3):462–467, 1968.  URL https://ieeexplore.ieee.org/abstract/document/1054142.
  * Cover and Thomas (2012) Thomas M Cover and Joy A Thomas.  _Elements of information theory_.  John Wiley & Sons, 2012.
  * Daskalakis et al. (2006) Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch.  Optimal phylogenetic reconstruction.  In _Proceedings of the thirty-eighth annual ACM symposium on Theory of computing_ , pages 159–168. ACM, 2006.
  * Daskalakis et al. (2009) Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch.  Phylogenies without branch bounds: Contracting the short, pruning the deep.  In _Annual International Conference on Research in Computational Molecular Biology_ , pages 451–465. Springer, 2009.
  * Daskalakis et al. (2013) Constantinos Daskalakis, Sebastien Roch, et al.  Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis.  _The Annals of Applied Probability_ , 23(2):693–721, 2013.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing Ising models.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1989–2007. SIAM, 2018.  URL https://arxiv.org/abs/1612.03147.
  * Douc et al. (2011) Randal Douc, Eric Moulines, Jimmy Olsson, Ramon Van Handel, et al.  Consistency of the maximum likelihood estimator for general hidden Markov models.  _the Annals of Statistics_ , 39(1):474–513, 2011\.  URL https://projecteuclid.org/euclid.aos/1297779854.
  * Drton and Maathuis (2017) Mathias Drton and Marloes H Maathuis.  Structure learning in graphical modeling.  _Annual Review of Statistics and Its Application_ , 4:365–393, 2017.  URL https://www.annualreviews.org/doi/abs/10.1146/annurev-statistics-060116-053803?journalCode=statistics.
  * Dwork et al. (2006a) Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 486–503. Springer, 2006a.  URL https://www.iacr.org/archive/eurocrypt2006/40040493/40040493.pdf.
  * Dwork et al. (2006b) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006b.
  * Edwards et al. (2010) David Edwards, Gabriel CG De Abreu, and Rodrigo Labouriau.  Selecting high-dimensional mixed graphical models using minimal AIC or BIC forests.  _BMC bioinformatics_ , 11(1):18, 2010.  URL https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-18.
  * Erdős et al. (1999) Péter L Erdős, Michael A Steel, László A Székely, and Tandy J Warnow.  A few logs suffice to build (almost) all trees: Part ii.  _Theoretical Computer Science_ , 221(1-2):77–118, 1999.
  * Erten et al. (2017) E Yagmur Erten, Joseph T Lizier, Mahendra Piraveenan, and Mikhail Prokopenko.  Criticality and information dynamics in epidemiological models.  _Entropy_ , 19(5):194, 2017.  URL https://www.mdpi.com/1099-4300/19/5/194.
  * Fan et al. (2017) Jianqing Fan, Han Liu, Yang Ning, and Hui Zou.  High dimensional semiparametric latent graphical model for mixed data.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 79(2):405–421, 2017.  URL https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssb.12168.
  * Fan et al. (2012) Xiequan Fan, Ion Grama, and Quansheng Liu.  Hoeffding’s inequality for supermartingales.  _Stochastic Processes and their Applications_ , 122(10):3545–3559, 2012.  URL https://arxiv.org/abs/1109.4359.
  * Finegold and Drton (2011) Michael Finegold and Mathias Drton.  Robust graphical modeling of gene networks using classical and alternative t-distributions.  _The Annals of Applied Statistics_ , pages 1057–1080, 2011.  URL https://projecteuclid.org/euclid.aoas/1310562216.
  * Foygel and Drton (2010) Rina Foygel and Mathias Drton.  Extended bayesian information criteria for Gaussian graphical models.  In _Advances in neural information processing systems_ , pages 604–612, 2010.  URL https://arxiv.org/abs/1011.6640.
  * Friedman et al. (2008) Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  Sparse inverse covariance estimation with the graphical lasso.  _Biostatistics_ , 9(3):432–441, 2008.  URL https://www.ncbi.nlm.nih.gov/pubmed/18079126.
  * Gao et al. (2012) Xin Gao, Daniel Q Pu, Yuehua Wu, and Hong Xu.  Tuning parameter selection for penalized likelihood estimation of Gaussian graphical model.  _Statistica Sinica_ , pages 1123–1146, 2012.  URL https://www.jstor.org/stable/24309977.
  * Georgii (2011) Hans-Otto Georgii.  _Gibbs measures and phase transitions_ , volume 9.  Walter de Gruyter, 2011.
  * Goel et al. (2019) Surbhi Goel, Daniel M Kane, and Adam R Klivans.  Learning ising models with independent failures.  _arXiv preprint arXiv:1902.04728_ , 2019.
  * Højsgaard et al. (2012) Søren Højsgaard, David Edwards, and Steffen Lauritzen.  _Graphical models with R_.  Springer Science & Business Media, 2012.
  * Hyvärinen (2005) Aapo Hyvärinen.  Estimation of non-normalized statistical models by score matching.  _Journal of Machine Learning Research_ , 6(Apr):695–709, 2005.  URL jmlr.org/papers/volume6/hyvarinen05a/old.pdf.
  * Hyvärinen (2007) Aapo Hyvärinen.  Some extensions of score matching.  _Computational statistics & data analysis_, 51(5):2499–2512, 2007.  URL https://www.cs.helsinki.fi/u/ahyvarin/papers/CSDA07.pdf.
  * Isserlis (1918) Leon Isserlis.  On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables.  _Biometrika_ , 12(1/2):134–139, 1918.  URL https://www.jstor.org/stable/2331932?seq=1#page_scan_tab_contents.
  * Jalali et al. (2011) Ali Jalali, Christopher C Johnson, and Pradeep K Ravikumar.  On learning discrete graphical models using greedy methods.  In _Advances in Neural Information Processing Systems_ , pages 1935–1943, 2011.  URL https://papers.nips.cc/paper/4290-on-learning-discrete-graphical-models-using-greedy-methods.
  * Jazwinski (2007) Andrew H Jazwinski.  _Stochastic processes and filtering theory_.  Courier Corporation, 2007.
  * Kalogerias and Petropulu (2016) Dionysios S Kalogerias and Athina P Petropulu.  Grid based nonlinear filtering revisited: recursive estimation & asymptotic optimality.  _IEEE Transactions on Signal Processing_ , 64(16):4244–4259, 2016.  URL https://ieeexplore.ieee.org/document/7457725.
  * Karger and Srebro (2001) David Karger and Nathan Srebro.  Learning Markov networks: Maximum bounded tree-width graphs.  In _Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms_ , pages 392–401. Society for Industrial and Applied Mathematics, 2001.  URL https://www.biostat.wisc.edu/~page/markovnet.pdf.
  * Kasiviswanathan et al. (2008) S. A. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith.  What can we learn privately?  In _IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)_ , pages 531–540, 2008.  doi: 10.1109/FOCS.2008.27.  URL http://dx.doi.org/10.1109/FOCS.2008.27.
  * Kim and Smaragdis (2013) Minje Kim and Paris Smaragdis.  Single channel source separation using smooth nonnegative matrix factorization with Markov random fields.  In _Machine Learning for Signal Processing (MLSP), 2013 IEEE International Workshop on_ , pages 1–6. IEEE, 2013.  URL https://ieeexplore.ieee.org/document/6661909/.
  * Koller and Friedman (2009) Daphne Koller and Nir Friedman.  _Probabilistic graphical models: principles and techniques_.  MIT press, 2009.
  * Lauritzen (1996) Steffen L Lauritzen.  Graphical models, volume 17 of oxford statistical science series, 1996\.
  * Li and Wand (2016) Chuan Li and Michael Wand.  Combining Markov random fields and convolutional neural networks for image synthesis.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016.  URL https://ieeexplore.ieee.org/document/7780641.
  * Lin et al. (2016a) Guosheng Lin, Chunhua Shen, Anton van den Hengel, and Ian Reid.  Efficient piecewise training of deep structured models for semantic segmentation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3194–3203, 2016a.  URL http://openaccess.thecvf.com/content_cvpr_2016/papers/Lin_Efficient_Piecewise_Training_CVPR_2016_paper.pdf.
  * Lin et al. (2016b) Lina Lin, Mathias Drton, Ali Shojaie, et al.  Estimation of high-dimensional graphical models using regularized score matching.  _Electronic Journal of Statistics_ , 10(1):806–854, 2016b.  URL https://projecteuclid.org/euclid.ejs/1459967424.
  * Liu et al. (2011) Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John Lafferty, and Larry Wasserman.  Forest density estimation.  _Journal of Machine Learning Research_ , 12(Mar):907–951, 2011.  URL http://jmlr.csail.mit.edu/papers/volume12/liu11a/liu11a.pdf.
  * Liu et al. (2017) Ziwei Liu, Xiaoxiao Li, Ping Luo, Chen Change Loy, and Xiaoou Tang.  Deep learning Markov random field for semantic segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2017.  URL https://ieeexplore.ieee.org/document/8006236.
  * Ma et al. (2013) Shiqian Ma, Lingzhou Xue, and Hui Zou.  Alternating direction methods for latent variable Gaussian graphical model selection.  _Neural computation_ , 25(8):2172–2198, 2013\.  URL https://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00379?journalCode=neco.
  * Matsuda et al. (1992) Hirotsugu Matsuda, Naofumi Ogita, Akira Sasaki, and Kazunori Satō.  Statistical mechanics of population: the lattice lotka-volterra model.  _Progress of theoretical Physics_ , 88(6):1035–1049, 1992.  doi: 10.1143/ptp/88.6.1035.
  * Morningstar and Melko (2017) Alan Morningstar and Roger G Melko.  Deep learning the Ising model near criticality.  _arXiv preprint arXiv:1708.04622_ , 2017.  URL http://www.jmlr.org/papers/v18/17-527.html.
  * Nandy et al. (2015) Preetam Nandy, Alain Hauser, and Marloes H Maathuis.  High-dimensional consistency in score-based and hybrid structure learning.  _arXiv preprint arXiv:1507.02608_ , 2015.  URL https://projecteuclid.org/euclid.aos/1536307246.
  * Pearl (1988) Judea Pearl.  Morgan Kaufmann series in representation and reasoning. probabilistic reasoning in intelligent systems: Networks of plausible inference, 1988.
  * Polyanskiy and Wu (2017) Yury Polyanskiy and Yihong Wu.  Strong data-processing inequalities for channels and Bayesian networks.  In _Convexity and Concentration_ , pages 211–249. Springer, 2017\.  URL http://people.lids.mit.edu/yp/homepage/data/simple-IMA.pdf.
  * Raginsky (2016) Maxim Raginsky.  Strong data processing inequalities and $\phi$-Sobolev inequalities for discrete channels.  _IEEE Transactions on Information Theory_ , 62(6):3355–3389, 2016.  URL https://arxiv.org/pdf/1411.3575.pdf.
  * Ravikumar et al. (2010) Pradeep Ravikumar, Martin J Wainwright, John D Lafferty, et al.  High-dimensional Ising model selection using L1-regularized logistic regression.  _The Annals of Statistics_ , 38(3):1287–1319, 2010.  URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6940&rep=rep1&type=pdf.
  * Ray et al. (2015) Avik Ray, Sujay Sanghavi, and Sanjay Shakkottai.  Improved greedy algorithms for learning graphical models.  _IEEE Transactions on Information Theory_ , 61(6):3457–3468, 2015.  URL https://ieeexplore.ieee.org/document/7097023/.
  * Rebeschini et al. (2015) Patrick Rebeschini, Ramon Van Handel, et al.  Can local particle filters beat the curse of dimensionality?  _The Annals of Applied Probability_ , 25(5):2809–2866, 2015.
  * Schwing and Urtasun (2015) Alexander G Schwing and Raquel Urtasun.  Fully connected deep structured networks.  _arXiv preprint arXiv:1503.02351_ , 2015.  URL https://arxiv.org/abs/1503.02351.
  * Takaishi (2015) Tetsuya Takaishi.  Multiple time series Ising model for financial market simulations.  In _Journal of Physics: Conference Series_ , volume 574, page 012149\. IOP Publishing, 2015.  URL https://iopscience.iop.org/article/10.1088/1742-6596/574/1/012149/pdf.
  * Tan et al. (2010) Vincent YF Tan, Animashree Anandkumar, and Alan S Willsky.  Learning Gaussian tree models: Analysis of error exponents and extremal structures.  _IEEE Transactions on Signal Processing_ , 58(5):2701–2714, 2010.  URL https://ieeexplore.ieee.org/document/5406101.
  * Tan et al. (2011) Vincent YF Tan, Animashree Anandkumar, and Alan S Willsky.  Learning high-dimensional Markov forest distributions: Analysis of error rates.  _Journal of Machine Learning Research_ , 12(May):1617–1653, 2011.  URL https://dl.acm.org/citation.cfm?id=2021052.
  * Torquato (2011) Salvatore Torquato.  Toward an Ising model of cancer and beyond.  _Physical biology_ , 8(1):015017, 2011.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3151151/.
  * Tsybakov (2009) Alexandre B Tsybakov.  Introduction to non-parametric estimation. revised and extended from the 2004 French original. translated by Vladimir Zaiats, 2009.
  * Van Handel (2009) Ramon Van Handel.  Observability and nonlinear filtering.  _Probability theory and related fields_ , 145(1-2):35–74, 2009.  URL https://link.springer.com/article/10.1007/s00440-008-0161-y.
  * Vogel and Fried (2011) Daniel Vogel and Roland Fried.  Elliptical graphical modelling.  _Biometrika_ , 98(4):935–951, 2011.  URL https://www.jstor.org/stable/pdf/23076182.pdf?seq=1#page_scan_tab_contents.
  * Vogel and Tyler (2014) Daniel Vogel and David E Tyler.  Robust estimators for non-decomposable elliptical graphical models.  _Biometrika_ , 101(4):865–882, 2014.  URL https://arxiv.org/abs/1302.5251.
  * Wainwright et al. (2003) Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky.  Tree-reweighted belief propagation algorithms and approximate ML estimation by pseudo-moment matching.  In _AISTATS_ , 2003.  URL https://www.jstor.org/stable/23566568?seq=1#page_scan_tab_contents.
  * Wainwright et al. (2008) Martin J Wainwright, Michael I Jordan, et al.  Graphical models, exponential families, and variational inference.  _Foundations and Trends® in Machine Learning_ , 1(1–2):1–305, 2008.  URL https://www.nowpublishers.com/article/DownloadSummary/MAL-001.
  * Wang et al. (2017) Bin Wang, Zhijian Ou, and Zhiqiang Tan.  Learning trans-dimensional random fields with applications to language modeling.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2017.  URL https://ieeexplore.ieee.org/document/7906616.
  * Warner (1965) Stanley L. Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, March 1965.  doi: 10.2307/2283137.  URL http://dx.doi.org/10.2307/2283137.
  * Wisdom et al. (2016) Scott Wisdom, John Hershey, Jonathan Le Roux, and Shinji Watanabe.  Deep unfolding for multichannel source separation.  In _Acoustics, Speech and Signal Processing (ICASSP), 2016 IEEE International Conference on_ , pages 121–125. IEEE, 2016.  URL https://ieeexplore.ieee.org/document/7471649.
  * Wu et al. (2017) Baoyuan Wu, Bao-Gang Hu, and Qiang Ji.  A coupled hidden Markov random field model for simultaneous face clustering and tracking in videos.  _Pattern Recognition_ , 64:361–373, 2017.  URL https://www.sciencedirect.com/science/article/abs/pii/S0031320316303387.
  * Yuan and Lin (2007) Ming Yuan and Yi Lin.  Model selection and estimation in the Gaussian graphical model.  _Biometrika_ , 94(1):19–35, 2007.  URL https://www.jstor.org/stable/20441351?seq=1#page_scan_tab_contents.
  * Zhou and Sornette (2007) W-X Zhou and Didier Sornette.  Self-organizing Ising model of financial markets.  _The European Physical Journal B_ , 55(2):175–181, 2007.  URL https://epjb.epj.org/articles/epjb/abs/2007/02/b06183/b06183.html.
  * Zuo et al. (2017) Yiming Zuo, Yi Cui, Guoqiang Yu, Ruijiang Li, and Habtom W Ressom.  Incorporating prior biological knowledge for network-based differential gene expression analysis using differentially weighted graphical LASSO.  _BMC bioinformatics_ , 18(1):99, 2017.  URL https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-017-1515-1.