1}\Delta_{1j}^{t}\lambda_{j}^{t}+Cn^{2}\frac{(1-\rho_{1}^{t})^{2}}{\beta^{4}(1-\alpha)^{2}}+C\frac{n|U^{t}|(1-\rho_{1}^{t})}{\beta^{2}(1-\alpha)}+C\frac{n|U^{t}|^{2}(1-\rho_{1}^{t})}{\beta^{2}(1-\alpha)}$

We know that

$\sum_{j\neq 1}\Delta_{1j}^{t}\lambda_{j}^{t}\leq
4n\frac{1-\rho_{1}^{t}}{\beta^{2}(1-\alpha)}$

and

$1-\rho_{1}^{t}\lambda_{1}^{t}=1-\rho_{1}^{t}+\rho_{1}^{t}(1-\lambda_{1}^{t})\leq(1-\rho_{1}^{t})\left(1+\frac{2n}{1-\alpha}\right)$

Hence, we have that

$\displaystyle 1-\rho_{1}^{t+1}$
$\displaystyle\geq(1-\rho_{1}^{t})\left(1-\left(1+\frac{2n}{1-\alpha}\right)\frac{n(1-\rho_{1}^{t})}{\beta^{2}(1-\alpha)}-Cn^{2}\frac{(1-\rho_{1}^{t})}{\beta^{4}(1-\alpha)^{2}}-C\frac{n|U^{t}|}{\beta^{2}(1-\alpha)}\right)$

∎

We now have almost all the necessary ingredients required for the proof of
Lemma 28. The final Lemma we will prove says that if $\rho_{1}$ happens to
come very close to $1$, then after one iteration it will start moving away
from $1$. This is qualitatively similar to the proof of Theorem 25 in the
manuscript, but now we have to make precise quantitative predictions for how
close it should be to $1$. This is the content of the following Lemma.

######  Lemma 31.

Suppose that $\min(\min_{i}\rho^{0}_{i},\min_{i}\rho^{*}_{i})\geq
c_{1},1-\max(\max_{i}\rho^{0}_{i},\max_{i}\rho^{*}_{i})\geq c_{2}$, where
$c_{1},c_{2}\in(0,1)$ are constants. Suppose we run EM (18) with $m$ samples
and suppose $\rho_{1}^{t}>1-c^{\prime}/n^{k}>1-c/n^{2}$, where $c^{\prime}>0$
is a sufficiently small constant, $k\geq 12$ and $c$ is the constant of
Corollary 1. Finally, assume that
$m=\Omega(\log(n/\delta)/\min(c_{1},c_{2})^{2})$. Then, with probability at
least $1-\delta$, for all $t^{\prime}\geq t+1$ we have that if
$\rho_{1}^{t^{\prime}}>c^{\prime}/n^{k}$, then for some absolute constant
$C>0$ we have

$\rho_{1}^{t^{\prime}+1}\leq\rho_{1}^{t^{\prime}}-\frac{C}{2}(1-\rho_{1}^{t^{\prime}})^{2}$

###### Proof.

We first state a slight modification of Lemma 23. The proof is exactly the
same, but now we are applying Taylor in the update rule of the empirical EM
instead of the population.

######  Lemma 32.

Let $\rho^{t}$ be the current iteration of empirical EM (18) and define

$\epsilon^{t}:=\max(1-\rho_{1}^{t},\max_{i}|\hat{\alpha}_{1i}-\rho^{t}_{i}|)$

Suppose also that $\min_{i}\hat{\alpha}_{1i}\geq
c_{1},1-\max_{i}\hat{\alpha}_{1i}\geq c_{2}$, where $c_{1},c_{2}$ are
constants. Then, there exist absolute constants $C,K>0$ depending on
$c_{1},c_{2}$ such that

$\rho^{t+1}_{1}\leq\rho^{t}_{1}-C|\rho_{1}^{t}-1|^{2}+Kn^{3}(\epsilon^{t})^{3}$

By Corollary 1 we have that $\rho_{i}^{t}<1-c/n^{2}$. Thus, if we set
$\alpha=1-c/n^{2}$ and $\beta=1-c^{\prime}/n^{k}$ we get that

$(1-\beta)R(\alpha,\beta,n)\leq
C\frac{1}{n^{k}}\left(\frac{1}{n^{k-6}}+n^{3}\right)$

which can be made less than $1/2$ with $k\geq 3$. Thus, all the assumptions of
Lemma 29 are satisfied. By applying this result, we get that for some constant
C

$|\rho_{i}^{t+1}-\hat{\alpha}_{1i}|\leq
C\frac{n^{3}}{1-\frac{C^{\prime}}{n^{k-6}}}(1-\rho_{1}^{t+1})\leq
C^{\prime\prime}n^{3}(1-\rho_{1}^{t+1})$

Similarly, for any $t^{\prime}\geq t+1$ such that
$\rho_{1}^{t^{\prime}}>1-c^{\prime}/n^{k}$ the previous calculations apply,
hence we get for all $t^{\prime}\geq t+1$

$|\rho_{i}^{t^{\prime}}-\hat{\alpha}_{1i}|\leq
C\frac{n^{3}}{1-\frac{C^{\prime}}{n^{k-6}}}(1-\rho_{1}^{t+1})\leq
C^{\prime\prime}n^{3}(1-\rho_{1}^{t^{\prime}})$

Thus, for every $t^{\prime}\geq t+1$ we have

$\epsilon^{t^{\prime}}\leq C^{\prime\prime}n^{3}(1-\rho_{1}^{t^{\prime}})$

To apply Lemma 32, notice that the assumption on $\hat{\alpha}$ is
automatically satisfied by our assumption on the number of samples $m$. Hence,
by applying Lemma 32, we get that

$\rho_{1}^{t^{\prime}+1}=\rho_{1}^{t^{\prime}}-C(1-\rho_{1}^{t^{\prime}})^{2}+K^{\prime}n^{12}(1-\rho_{1}^{t^{\prime}+1})^{3}$

Now, if $k\geq 12$ and $c^{\prime}$ is a small enough constant, we have

$K^{\prime}n^{12}(1-\rho_{1}^{t^{\prime}+1})<C/2$

which implies that

$\rho_{1}^{t^{\prime}+1}\leq\rho_{1}^{t^{\prime}}-\frac{C}{2}(1-\rho_{1}^{t^{\prime}})^{2}$

∎

We are now ready to present the proof of the main Lemma of this section.

###### Proof of Lemma 28.

First of all, our assumption on $m$ implies that $\hat{\alpha}_{ij}$ is
bounded away from $0$ and $1$ with probability at least $1-\delta$. Hence, all
the claims that follow hold with probability at least $1-\delta$ (because the
boundedness property is required to apply some of these Lemmas). Initially, we
have $\rho_{i}^{0}<1-c^{\prime}/n^{k}$ for all $i$. Let $t$ by the first time
where $\rho_{i}^{t}>1-c^{\prime}/n^{k}$ for some $i$. Let $T$ be the first
time after $t$ such that $\rho_{i}^{t}\leq 1-c^{\prime}/n^{k}$. Then, by Lemma
31 we have that $\rho_{i}^{t^{\prime}+1}\leq\rho_{i}^{t^{\prime}}$ for all
$T>t^{\prime}\geq t+1$. Hence, we have $\rho_{i}^{t^{\prime}}\leq
max(\rho_{i}^{t},\rho_{i}^{t+1})$ for all $t^{\prime}<T$. Let us now try to
upper bound $\rho_{i}^{t+1}$ and $\rho_{i}^{t}$. First of all, we can write
$y^{t}=Ax_{i}^{t}+r^{t}$, where $x_{i}^{t}$ is the random variable of the leaf
$i$ sampled according to the parameters $\sigma_{x_{i}}^{t-1}$, $y^{t}$ is the
random variable that is sampled conditional on all $x_{i}^{t}$ and with model
parameters $\rho_{i}^{t-1}$ and $r^{t}$ is independent of $x_{i}^{t}$. Let
$v^{2}$ be the variance of $r^{t}$. Then, by definition

$\rho_{i}^{t}=\frac{A}{\sqrt{A^{2}+v^{2}}}=\frac{1}{\sqrt{1+(v/A)^{2}}}$

Then, we have that
$A=Cov(y^{t},x_{i}^{t})/\sigma_{x_{i}}^{t}\leq\sum_{i}\lambda_{i}^{t-1}/\sigma_{x_{i}}^{t}\leq
Cn$. Here we used the fact that $|\sigma_{x_{i}}^{t}-1|\leq C$, where $C$ is a
small constant, which is implied by the assumption on the number of samples
$m$. As for $v^{2}$, we can show that

$v^{2}\geq\frac{1}{1+\sum\frac{(\rho_{i}^{t-1})^{2}}{1-(\rho_{i}^{t-1})^{2}}}$

Indeed, the right hand side of this inequality is the conditional variance of
$y$ conditioned an all $x_{j}^{t}$ for $j\in[n]$. Since conditioning reduces
the variance, the inequality is obvious. Now, we know that
$1-(\rho_{i}^{t-1})^{2}>1-c^{\prime}/n^{k}$ for all $i$ by definition. Hence,

$v^{2}\geq\frac{C}{n^{2k+1}}$

Hence,

$\rho_{i}^{t}\leq\frac{1}{\sqrt{1+C/n^{2k+3}}}\leq
1-\frac{C^{\prime}}{n^{2k+3}}$

Using this bound, in a completely similar fashion we get that

$\rho_{i}^{t+1}\leq 1-\frac{C^{\prime\prime}}{n^{4k+9}}$

Hence, we have that $\rho_{i}^{t^{\prime}}\leq 1-C/n^{4k+9}$ for all
$t^{\prime}<T$. Now, let’s examine what happens after time $T$. We proved in
Lemma 32 that $|\rho_{j}^{T}-\hat{\alpha}_{ij}|\leq
Cn^{3}(1-\rho_{i}^{T-1})\leq C/n^{k-3}$ for all $j\neq i$. Hence, for $k\geq
2$ and small enough constant $q\in(0,1)$ we have that
$\rho_{j}^{T}\leq\hat{\alpha}_{ij}+q\leq 1-c^{\prime}/n^{k}$ for $j\neq i$. We
already know that $\rho_{i}^{T}\leq 1-c^{\prime}/n^{k}$ by definition of $T$.
Hence, at the $T$-th iteration all correlations will remain bounded away from
$0$. We can then consider the first time after $T$ such that some correlation
becomes bigger than $1-c^{\prime}/n^{k}$ and the same bounds that we already
established apply again and so on. Hence, we conclude that for all $i,t$,
$\rho_{i}^{t}\leq 1-C^{\prime\prime}/n^{4k+9}$.

∎

###  C.4 No correlation is close to $0$

In this Section, we prove a lower bound for all the correlations at any
iteration of the algorithm. We will prove the following Lemma.

######  Lemma 33.

Suppose that $\min(\min_{i}\rho^{0}_{i},\min_{i}\rho^{*}_{i})\geq
c_{1},1-\max(\max_{i}\rho^{0}_{i},\max_{i}\rho^{*}_{i})\geq c_{2}$, where
$c_{1},c_{2}\in(0,1)$ are constants. Suppose we have access to $m$ i.i.d.
samples $x^{(1)},\ldots,x^{(m)}$ from the distribution $\mu_{x}^{*}$. Let
$\rho_{i}^{t}$ be the correlations produced by the EM iteration (18) run using
these samples. Suppose $m=\Omega(\log(n/\delta)/\min(c_{1},c_{2})^{2})$. Then,
there exists a constant $c=c(c_{1},c_{2})$ such that with probability at least
$1-\delta$, for all $t$ and for all $i\in[n]$ $\rho_{i}>c/n^{k+2}$ for $k\geq
4$.

###### Proof.

We start by stating a slight modification of Lemma 22 in the case of sample
EM.

######  Lemma 34.

Let $\rho^{t}$ be the iteration of sample EM (18). If $\rho^{t}=0$ then
$\rho^{t+1}=0$. Further, there exists $C>0$ such that for all
$i,j,k\in\\{1,\dots,n\\}$ and all $\rho\in[0,1/2]^{n}$,

$\frac{d\rho^{t+1}_{i}}{d\rho^{t}_{j}}\bigg{|}_{0}=\begin{cases}1&i=j\\\
\hat{\alpha}_{ij}&i\neq
j\end{cases}~{};\qquad-C\leq\frac{d^{2}\rho_{i}^{t+1}}{d\rho^{t}_{j}d\rho^{t}_{k}}\bigg{|}_{\rho}\leq
C.$

By our assumption on the number of samples $m$, we get that all
$\hat{\alpha}_{ij}$ are bounded away from $0$ and $1$ depending on the
constants $c_{1},c_{2}$, with probability $1-\delta$. From now on, we will
assume this holds deterministically. Using Lemma 34 and Taylor’s Theorem, we
get that for all $i$

$\rho^{t+1}_{i}\geq\rho^{t}_{i}+\sum_{j\neq
i}\rho_{j}\hat{\alpha}_{ij}-\sum_{j,k}\frac{C}{2}\rho^{t}_{j}\rho^{t}_{k}.$
(29)

We now prove that during all iterations $t$ and for all $i\neq j$, we have
$\rho_{i}^{t}\geq c(n)\rho_{j}^{t}$, for some constant $c(n)$ that is
independent of the iteration $t$. For $t=0$, we can find some constant $c$
independent of $n$ such that this is satisfied (because we initially start at
a constant distance from the optimum). Now, suppose $t>1$. Suppose without
loss of generality that $\rho_{1}^{t-1}\geq\rho_{i}^{t-1}$ for all $i\neq 1$.
Let us fix $i\neq j$. By the update rule, we have that

$\rho_{i}^{t}\geq\frac{\lambda_{1}^{t-1}\hat{\alpha}_{1i}}{\sqrt{1+2n^{2}}}\geq\frac{\hat{\alpha}_{1i}}{n\sqrt{3}}\lambda_{1}^{t-1}$

On the other hand, we have that

$\rho_{j}^{t}\leq\sum_{k}\lambda_{k}^{t-1}\leq n\lambda_{1}^{t-1}$

since $\lambda_{1}^{t-1}\geq\lambda_{k}^{t-1}$ for all $k\neq 1$. Thus, we
conclude that

$\rho_{i}^{t}\geq\frac{\hat{\alpha}_{1i}}{n^{2}\sqrt{3}}\rho_{j}^{t}\geq\frac{K}{n^{2}}\rho_{j}^{t}$

so we set $c(n):=K/n^{2}$, where $K$ is some constant that depends on the
lower bound on $c_{1},c_{2}$ (it is lower bounded by assumption).

Now that we have proven this claim, we can use inequality(29). Suppose
w.l.o.g. that $1=\arg\max_{i}\rho_{i}^{t}$. Then

$\rho^{t+1}_{i}\geq\rho^{t}_{i}+\sum_{j\neq
i}\rho_{j}\hat{\alpha}_{ij}-\sum_{j,k}\frac{C}{2}\rho^{t}_{j}\rho^{t}_{k}\geq\rho_{i}^{t}+n\frac{K}{n^{2}}\rho_{1}^{t}-Cn^{2}(\rho_{1}^{t})^{2}=\rho_{i}^{t}+\frac{K}{n}\rho_{1}^{t}-Cn^{2}(\rho_{1}^{t})^{2}$

Suppose $\rho_{1}^{t}<c/n^{k}$, where $k$ will be determined later. Then,

$\rho_{i}^{t+1}\geq\rho_{i}^{t}+\rho_{1}^{t}(K/n-Cn^{2}/n^{k})>\rho_{i}^{t}$

if $k-2\geq 2$ and $c$ is small enough. Now suppose $\rho_{1}^{t}\geq
c/n^{k}$. Then, we have already proved that

$\rho_{i}^{t+1}\geq\frac{K}{n}\lambda_{1}^{t}$

Now, we have

$\lambda_{1}^{t}=\frac{\rho_{1}^{t}}{1+\sum_{j\neq
1}\frac{(\rho_{j}^{t})^{2}(1-(\rho_{1}^{t})^{2})}{1-(\rho_{j}^{t})^{2}}}\geq\frac{\rho_{1}^{t}}{n+1}$

since $1-(\rho_{1}^{t})^{2}\leq 1-(\rho_{j}^{t})^{2}$ for all $j\neq 1$. It
follows that

$\rho_{i}^{t+1}\geq\frac{cK}{n^{k+2}}$

Hence, if the maximum exceeds the threshold, all correlations are lower
bounded, otherwise they do not decrease. We conclude that for all iterations
$t$ and all $i$ the required bound holds. ∎

##  Appendix D Proof of Theorem 2: finite sample and finite iterate

###  D.1 A deterministic assumption

Note that our theorem holds with high probability. To remove the probabilistic
part, we assume a deterministic assumption on the sample, that will hold with
high probability. First, we present a definition:

######  Definition 2.

Let $\eta>0$. We say that a sample $x^{(1)},\dots,x^{(m)}$ is
$\eta$-representative of $\mu_{x}^{*}$ if the following hold:

  * •

For all $i=1,\dots,n$,

$1-\eta\leq\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left(x^{(k)}_{i}\right)^{2}}\leq
1+\eta.$

(recall that we assumed that the variance of each coordinate of $\mu^{*}_{x}$
is $1$).

  * •

For all $i\neq j\in\\{1,\dots,n\\}$:

$\rho^{*}_{i}\rho^{*}_{j}-\eta\leq\frac{1}{m}\sum_{k=1}^{m}x^{(k)}_{i}x^{(k)}_{j}\leq\rho^{*}_{i}\rho^{*}_{j}+\eta\enspace.$

  * •

For all $i\neq j$,

$\rho^{*}_{i}\rho^{*}_{j}-\eta\leq\hat{\alpha}_{ij}=\frac{\frac{1}{m}\sum_{k=1}^{m}x^{(k)}_{i}x^{(k)}_{j}}{\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left(x^{(k)}_{i}\right)^{2}}\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left(x^{(k)}_{j}\right)^{2}}}\leq\rho^{*}_{i}\rho^{*}_{j}+\eta\enspace.$

We will assume that the sample is $\eta$-representative, where $\eta$ is
sufficiently small. We note that from Chernoff-Hoeffding bound, the sample is
$\eta$-representative with probability $1-\delta$, if
$m\geq\Omega(\log(n/\delta)/\eta^{2})$.

###  D.2 Iterates are bounded away from 0 and 1

We start by recalling that in all iterates, the correlations $\rho^{t}_{i}$
are always bounded away from $0$ and $1$, assuming finite sample: (proof is in
Section C) See 5

Next, we would use the fact that the iterates are always bounded away from $0$
and $1$ for the remainder of the proof. For that purpose, we have the
following definition:

######  Definition 3.

We say that the iterates of the EM are $(A,B)$-bounded if
$A\leq\rho^{*}_{i}\leq 1-B$ and $A\leq\rho^{t}_{i}\leq 1-B$ for all $i$ and
$t\geq 0$.

###  D.3 Sample-EM is close to the population EM

Next, we will argue that one iterate of the sample EM close to one iterate of
the population EM, if the sample is $\eta$-representative.

######  Lemma 35.

Assume that the sample is $\eta$-representative, for some $\eta>0$. Fix values
of $\rho^{t}_{1},\dots,\rho^{t}_{n}$ and let
$\rho^{t+1}_{1},\dots,\rho^{t+1}_{n}$ denote the value of the next iterate
according to the finite-sample update of Lemma 26. Similarly, denote by
$\tilde{\rho}^{t+1}_{1},\dots,\tilde{\rho}^{t+1}_{n}$ the result of applying
the _population EM_ update, as described in Lemma 2. Assume that the iterates
of the EM are $(A,B)$-bounded, that $A\leq 1/n$ for some $A>0$ and assume that
$\eta\leq A^{2}/2$. Then,

$\left|\rho^{t+1}_{i}-\tilde{\rho}^{t+1}_{i}\right|\leq\eta\left(\frac{4\sqrt{8}n^{3}}{A^{3}}+\frac{\sqrt{8}n}{A}\right)$

###### Proof.

Fix $i\in\\{1,\dots,n\\}$. Let us denote the numerator and the denominator,
for both the expressions for $\rho^{t+1}_{i}$ and $\tilde{\rho}^{t+1}_{i}$, as
follows:

$X=\lambda^{t}_{i}+\sum_{j\neq i}\lambda^{t}_{j}\hat{\alpha}_{ij},\quad
X^{\prime}=\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}$

and

$Y=\sum_{i=1}^{n}(\lambda^{t}_{i})^{2}+\sum_{i\neq
j\in\\{1,\dots,n\\}}\lambda^{t}_{i}\lambda^{t}_{j}\hat{\alpha}_{ij},\quad
Y^{\prime}=\sum_{i=1}^{n}(\lambda^{t}_{i})^{2}+\sum_{i\neq
j\in\\{1,\dots,n\\}}\lambda^{t}_{i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}\enspace.$

Then, the quantity that we wish to bound is:

$\displaystyle\left|\frac{X}{\sqrt{Y}}-\frac{X^{\prime}}{\sqrt{Y^{\prime}}}\right|$
$\displaystyle=\left|\frac{X}{\sqrt{Y}}-\frac{X}{\sqrt{Y^{\prime}}}+\frac{X}{\sqrt{Y^{\prime}}}-\frac{X^{\prime}}{\sqrt{Y^{\prime}}}\right|\leq|X|\left|\frac{1}{\sqrt{Y}}-\frac{1}{\sqrt{Y^{\prime}}}\right|+\frac{1}{\sqrt{Y^{\prime}}}\left|X-X^{\prime}\right|$
(30)
$\displaystyle=\frac{X\left|\sqrt{Y}-\sqrt{Y^{\prime}}\right|}{\sqrt{YY^{\prime}}}+\frac{1}{\sqrt{Y^{\prime}}}\left|X-X^{\prime}\right|=\frac{X\left|Y-Y^{\prime}\right|}{\sqrt{YY^{\prime}}\left|\sqrt{Y}+\sqrt{Y^{\prime}}\right|}+\frac{1}{\sqrt{Y^{\prime}}}\left|X-X^{\prime}\right|\enspace.$

Our goal is to upper bound $X$, lower bound $Y$ and $Y^{\prime}$, and upper
bound $|X-X^{\prime}|$ and $|Y-Y^{\prime}|$, as computed below. First, notice
that

$|X-X^{\prime}|=\left|\left(\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\hat{\alpha}_{ij}\right)-\left(\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}\right)\right|\leq\sum_{j\neq
i}\lambda^{t}_{j}|\hat{\alpha}_{ij}-\rho^{*}_{i}\rho^{*}_{j}|\leq\eta\sum_{j=1}^{n}\lambda^{t}_{j},$
(31)

where the last inequality follows by assumption of this lemma that
$|\hat{\alpha}_{ij}-\rho^{*}_{i}\rho^{*}_{j}|\leq\eta$. Recall the expression
for $\lambda^{t}_{i}$ in (1), and notice that we can bound it as follows:

$\lambda^{t}_{i}=\frac{\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})}{1+\sum_{j=1}^{n}(\rho^{t}_{j})^{2}/(1-(\rho^{t}_{j})^{2})}\leq\frac{\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})}{1+(\rho^{t}_{i})^{2}/(1-(\rho^{t}_{i})^{2})}=\rho^{t}_{i}\leq
1.$

Then, $\sum_{i}\lambda_{i}\leq n$, which implies that

$|X-X^{\prime}|\leq\eta n.$

Next:

$|Y-Y^{\prime}|=\left|\sum_{j\neq
i}\lambda^{t}_{i}\lambda^{t}_{j}\hat{\alpha}_{ij}-\sum_{j\neq
i}\lambda^{t}_{i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}\right|\leq\sum_{j\neq
i}\lambda^{t}_{i}\lambda^{t}_{j}|\hat{\alpha}_{ij}-\rho^{*}_{i}\rho^{*}_{j}|\leq\eta
n^{2},$

using the fact that $\lambda^{t}_{i}\leq 1$ and the assumption of this lemma
that $|\hat{\alpha}_{ij}-\rho^{*}_{i}\rho^{*}_{j}|\leq\eta$. Further,

$X=\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\hat{\alpha}_{ij}\leq\sum_{j=1}^{n}\lambda^{t}_{j}\leq n.$

Further,

$Y^{\prime}\geq\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda^{t}_{i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}\geq\sum_{i=1}^{n}\sum_{j=1}^{n}A^{2}=\left(\sum_{i=1}^{n}\lambda^{t}_{i}\right)^{2}A^{2},$

using the assumption that $\rho^{*}_{i}\geq A$ for all $i$. Similarly, we
derive that

$Y\geq\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda^{t}_{i}\lambda^{t}_{j}\hat{\alpha}_{ij}\geq\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda^{t}_{i}\lambda^{t}_{j}A^{2}/2=\left(\sum_{i=1}^{n}\lambda^{t}_{i}\right)^{2}A^{2}/2,$

using the assumptions that $\rho^{*}_{i}\geq A$ for all $i$, and that
$|\hat{\alpha}_{ij}-\rho^{*}_{i}\rho^{*}_{j}|\leq A^{2}/2$. It remains to
lower bound the value of $\sum_{i}\lambda^{t}_{i}$:

$\sum_{i}\lambda^{t}_{i}=\frac{\sum_{i=1}^{n}\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})}{1+\sum_{i=1}^{n}(\rho^{t}_{i})^{2}/(1-(\rho^{t}_{i})^{2})}\geq\frac{\sum_{i=1}^{n}\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})}{1+\sum_{i=1}^{n}\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})}\geq\frac{\sum_{i=1}^{n}\rho^{t}_{i}}{1+\sum_{i=1}^{n}\rho^{t}_{i}}\geq\frac{nA}{1+nA}\enspace,$

where, for the last two inequalities, we used the fact that if $a\geq
a^{\prime}>0$ and $b\geq 0$ then $a/(a+b)\geq a^{\prime}/(a^{\prime}+b)$. We
will further use the assumption that $A\geq 1/n$ to derive that the right hand
side is lower bounded by $1/2$. We derive that

$Y,Y^{\prime}\geq A^{2}/8.$

Substituting our estimates from (30), we derive that, for some universal
constant $C>0$,

$\left|\frac{X}{\sqrt{Y}}-\frac{X^{\prime}}{\sqrt{Y^{\prime}}}\right|\leq\frac{n\cdot\eta
n^{2}}{A^{2}/8\cdot 2(A/\sqrt{8})}+\frac{1}{A/\sqrt{8}}\eta
n=\eta\left(\frac{4\sqrt{8}n^{3}}{A^{3}}+\frac{\sqrt{8}n}{A}\right)\enspace.$

∎

###  D.4 KL is comparable to the parameter $\ell_{2}$ distance

In our argument, we will prove that in each iteration, the KL divergence
between the iterate and the true distribution shrinks by a constant factor. In
order to argue about that, we would like to claim that the KL divergence
between two models is comparable to the $\ell_{2}$ distance between their
correlation parameters $\rho_{i}$, provided that those are bounded away from
$0$ and $1$:

######  Lemma 36.

Assume that the iterates of the EM are $(A,B)$-bounded. Then, for some
universal constant $C>0$ and for all $t\geq 0$,

$(n/AB)^{-C}\|\rho^{t}-\rho^{*}\|^{2}\leq\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})\leq(n/(AB))^{C}\|\rho^{t}-\rho^{*}\|^{2}.$

In the sections below we will prove statements that are slightly more general
(which will also be used further in the proof).

####  D.4.1 Upper bounding the KL

We start by proving the following lemma:

######  Lemma 37.

Assume that $\rho^{*}_{i},\rho^{t}_{i}\leq 1-B$ for all $i$ and some $B>0$.
Then,

$\left|\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}}\right|\leq\operatorname{poly}(n,1/B)\cdot\|\rho^{t}-\rho^{*}\|_{2}.$

Consequently, for $\rho$ and $\rho^{\prime}$,

$\left|\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho}_{x})-\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho^{\prime}}_{x})\right|\leq\operatorname{poly}(n,1/B)\max(\|\rho^{\prime}-\rho^{*}\|,\|\rho-\rho^{*}\|)\|\rho^{\prime}-\rho\|.$

Lastly,

$\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})\leq\operatorname{poly}(n,1/B)\cdot\|\rho^{t}-\rho^{*}\|_{2}^{2}.$

###### Proof.

We start by proving the first inequality. We use a few folklore equations:
first, we define for any real-valued function $f$ of a matrix $A$ by
$df(A)/dA$ the matrix whose $ij$-entry is the derivative of $f(A)$ as a
function of $A_{ij}$. The first folklore equation is:

$\frac{d\log\det(A)}{dA}=(A^{-1})^{\top}.$ (32)

For the second equation, assume that $A$ is a function of some parameter
$\lambda$. Then,

$\frac{dA^{-1}}{d\lambda}=-A^{-1}\frac{dA}{d\lambda}A^{-1},$

where $dA/d\lambda$ is a matrix whose $ij$ entry is the derivative of $A_{ij}$
as a function $\lambda$. Further:

$\frac{df(A)}{d\lambda}=\operatorname{trace}\left(\left(\frac{df(A)}{dA}\right)^{\top}\frac{dA}{d\lambda}\right).$
(33)

Lastly, if $A\in\mathbb{R}^{n\times n}$ is symmetric and $\|A\|$ is the
operator norm of $A$ then

$\operatorname{trace}(A)\leq n\|A\|.$ (34)

Indeed, this is true because $\operatorname{trace}(A)$ is the sum of its
singular values of $A$ while $\|A\|$ is the largest singular value in absolute
value.

Let us continue by analyzing the KL divergence. We note that the KL divergence
between two mean-zero Gaussian vectors and covariances $\Sigma_{1}$ and
$\Sigma_{2}$, is

$\operatorname{KL}(\Sigma_{1}\|\Sigma_{2})=\frac{1}{2}\left(-\log\frac{\det((\Sigma_{2})^{-1})}{\det((\Sigma_{1})^{-1})}-n+\operatorname{trace}((\Sigma_{2})^{-1}\Sigma_{1})\right).$

Applying this on the covariances $\Sigma^{*}$ and $\Sigma^{t}$ that correspond
to $\rho^{*}$ and $\rho^{t}$, we get that

$\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})=\frac{1}{2}\left(-\log\frac{\det((\Sigma^{t})^{-1})}{\det((\Sigma^{*})^{-1})}-n+\operatorname{trace}((\Sigma^{t})^{-1}\Sigma^{*})\right).$

Let us first compute the first derivative as a function of $\rho^{t}_{i}$. By
(33), we have that

$\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}}=\operatorname{trace}\left(\left(\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d(\Sigma^{t})^{-1}}\right)^{\top}\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}\right)~{}.$
(35)

Let us expand on the first term. By (32),

$\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d(\Sigma^{t})^{-1}}=\frac{1}{2}\frac{d}{d(\Sigma^{t})^{-1}}\left(-\log\det((\Sigma^{t})^{-1})+\operatorname{trace}((\Sigma^{t})^{-1}\Sigma^{*})\right)=\frac{1}{2}\left(-(\Sigma^{t})^{\top}+\Sigma^{*}\right)=\frac{1}{2}\left(\Sigma^{*}-\Sigma^{t}\right)\enspace.$

Note that the derivative at $\rho^{*}=\rho^{t}$ equals $0$, which implies that

$\left.\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}}\right|_{\rho^{t}=\rho^{*}}=0.$
(36)

By (35), for a general $\rho^{t}$, we have that

$\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}}=\frac{1}{2}\operatorname{trace}\left((\Sigma^{*}-\Sigma^{t})^{\top}\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}\right)=\frac{1}{2}\operatorname{trace}\left((\Sigma^{*}-\Sigma^{t})\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}\right)~{}.$

Let us differentiate this again. We have that

$\frac{d^{2}\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}d\rho^{t}_{j}}=\frac{d}{d\rho^{t}_{j}}\frac{1}{2}\operatorname{trace}\left((\Sigma^{*}-\Sigma^{t})\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}\right)=\frac{1}{2}\operatorname{trace}\left(-\frac{d\Sigma^{t}}{d\rho^{t}_{j}}\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}+(\Sigma^{*}-\Sigma^{t})\frac{d^{2}(\Sigma^{t})^{-1}}{d\rho^{t}_{i}d\rho^{t}_{j}}\right)\enspace.$

In order to bound the left hand side above, we use (34), to obtain that

$\displaystyle\operatorname{trace}\left(-\frac{d\Sigma^{t}}{d\rho^{t}_{j}}\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}+(\Sigma^{*}-\Sigma^{t})\frac{d^{2}(\Sigma^{t})^{-1}}{d\rho^{t}_{i}d\rho^{t}_{j}}\right)\leq
n\left\|-\frac{d\Sigma^{t}}{d\rho^{t}_{j}}\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}+(\Sigma^{*}-\Sigma^{t})\frac{d^{2}(\Sigma^{t})^{-1}}{d\rho^{t}_{i}d\rho^{t}_{j}}\right\|$
$\displaystyle\leq\left\|\frac{d\Sigma^{t}}{d\rho^{t}_{j}}\right\|\left\|\frac{d(\Sigma^{t})^{-1}}{d\rho^{t}_{i}}\right\|+\left\|(\Sigma^{*}-\Sigma^{t})\right\|\left\|\frac{d^{2}(\Sigma^{t})^{-1}}{d\rho^{t}_{i}d\rho^{t}_{j}}\right\|$

We note that each of the components above is bounded by
$\operatorname{poly}(n,1/B)$, using the formulas for $\Sigma^{t}$ and
$(\Sigma^{t})^{-1}$ that appear in (20) and (21). To conclude the first part
of this lemma, we use the fact that the derivative equals $0$ at
$\rho^{t}=\rho^{*}$ as shown in (36), and we integrate the second derivative
along the path $\rho(\tau)=(1-\tau)\rho^{*}+\tau\rho^{t}$. Define
$\mu_{x}^{\tau}$ the distribution obtained with correlations $\rho(\tau)$,
then

$\displaystyle\left|\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}}\right|$
$\displaystyle=\left|\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{t}_{x})}{d\rho^{t}_{i}}-\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{*}_{x})}{d\rho^{t}_{i}}\right|=\left|\int_{0}^{1}\frac{d}{d\tau}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\tau}_{x})}{d\rho^{t}_{i}}d\tau\right|$
$\displaystyle=\left|\int_{0}^{1}\sum_{j=1}^{n}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\tau}_{x})}{d\rho^{t}_{i}d\rho^{t}_{j}}\frac{d\rho(\tau)_{j}}{d\tau}d\tau\right|=\left|\int_{0}^{1}\sum_{j=1}^{n}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\tau}_{x})}{d\rho^{t}_{i}d\rho^{t}_{j}}(\rho^{t}-\rho^{*})d\tau\right|$
$\displaystyle\leq\int_{0}^{1}\sum_{j=1}^{n}\left|\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\tau}_{x})}{d\rho^{t}_{i}d\rho^{t}_{j}}\right|\left|\rho^{t}-\rho^{*}\right|d\tau\leq\int_{0}^{1}\sum_{j=1}^{n}\operatorname{poly}(n,1/B)\left|\rho^{t}-\rho^{*}\right|d\tau$
$\displaystyle\leq\operatorname{poly}(n,1/B)\|\rho^{t}-\rho^{*}\|_{1}\leq\sqrt{n}\operatorname{poly}(n,1/B)\|\rho^{t}-\rho^{*}\|_{2}.$

This concludes the first part of the lemma. The second part of this lemma is
bounded similarly, by integrating, now over the first derivative: define by
$\rho(\tau)=(1-\tau)\rho+\tau\rho^{\prime}$. Then,

$\displaystyle\left|\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho}_{x})-\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho^{\prime}}_{x})\right|=\left|\int_{0}^{1}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho(\tau)}_{x})}{d\tau}d\tau\right|=\left|\int_{0}^{1}\sum_{i=1}^{n}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho(\tau)}_{x})}{d\rho(\tau)_{i}}\frac{d\rho(\tau)_{i}}{d\tau}d\tau\right|$
$\displaystyle=\left|\int_{0}^{1}\sum_{i=1}^{n}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho(\tau)}_{x})}{d\rho(\tau)_{i}}(\rho^{\prime}_{i}-\rho_{i})d\tau\right|=\left|\int_{0}^{1}\sum_{i=1}^{n}\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho(\tau)}_{x})}{d\rho(\tau)_{i}}(\rho^{\prime}_{i}-\rho_{i})d\tau\right|$
$\displaystyle\leq\int_{0}^{1}\sum_{i=1}^{n}\left|\frac{d\operatorname{KL}(\mu^{*}_{x}\|\mu^{\rho(\tau)}_{x})}{d\rho(\tau)_{i}}\right||\rho^{\prime}_{i}-\rho_{i}|d\tau\leq\int_{0}^{1}\sum_{i=1}^{n}\operatorname{poly}(n,1/B)\|\rho(\tau)-\rho^{*}\|_{2}|\rho^{\prime}_{i}-\rho_{i}|d\tau$
$\displaystyle\leq\operatorname{poly}(n,1/B)\max_{\tau}\|\rho(\tau)-\rho^{*}\|_{2}\|\rho^{\prime}_{i}-\rho_{i}\|_{1}$
$\displaystyle\leq\sqrt{n}\operatorname{poly}(n,1/B)\max(\|\rho-\rho^{*}\|_{2},\|\rho^{\prime}-\rho^{*}\|)\|\rho^{\prime}_{i}-\rho_{i}\|_{2}\enspace.$

The last part of this lemma is obtained from the second part by substituting
$\rho^{\prime}=\rho^{*}$. ∎

####  D.4.2 KL upper bounds the parameter difference

######  Lemma 38.

Let $\mu$ and $\mu^{\prime}$ be two distribution. Assume that
$\operatorname{Var}_{\mu}[y]=1$ and further that
$\operatorname{Var}_{\mu}[x_{i}]=\operatorname{Var}_{\mu^{\prime}}[x_{i}]=1$.
Then,

$\operatorname{KL}(\mu^{\prime}\|\mu)\geq\max_{i}\frac{(\operatorname*{\mathbb{E}}_{\mu}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{i}y])^{2}}{2}.$

We would like to lower bound $\operatorname{KL}(\mu^{\prime}\|\mu)$ by
$(\operatorname*{\mathbb{E}}_{\mu}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{i}y])^{2}$.
Notice that by the data-processing inequality and by the chain rule for KL
divergence,

$\operatorname{KL}(\mu^{\prime}\|\mu)\geq\operatorname{KL}(\mu^{\prime}_{x_{i}y}\|\mu_{x_{i}y})=\operatorname{KL}(\mu^{\prime}_{x_{i}}\|\mu_{x_{i}})+\operatorname*{\mathbb{E}}_{x_{i}\sim\mu_{x_{i}}^{t+1}}[\operatorname{KL}(\mu^{\prime}_{y\mid
x_{i}}\|\mu_{y\mid
x_{i}})]=\operatorname*{\mathbb{E}}_{x_{i}\sim\mu_{x_{i}}^{t+1}}[\operatorname{KL}(\mu^{\prime}_{y\mid
x_{i}}\|\mu_{y\mid x_{i}})].$ (37)

We would like to compute the conditional distribution of $y$ given $x_{i}$,
for both $\mu$ and $\mu^{\prime}$. We use the following formula for
conditional Gaussians:

######  Lemma 39.

Let $Z$ and $W$ be jointly distributed Gaussian variables. Then,

$\operatorname*{\mathbb{E}}[W\mid
Z]=\operatorname*{\mathbb{E}}W+\operatorname*{\mathbb{E}}[ZW]\operatorname{Var}[Z]^{-1}Z,$

and

$\operatorname{Var}[W\mid
Z]=\operatorname{Var}[W]-\operatorname*{\mathbb{E}}[WZ]^{2}\operatorname{Var}[Z]^{-1}.$

Using the formula of Lemma 39,

$\operatorname*{\mathbb{E}}[y\mid
x_{i}]=\operatorname*{\mathbb{E}}[y]+\operatorname*{\mathbb{E}}[x_{i}y]\operatorname{Var}[x_{i}]^{-1}x_{i},$

while

$\operatorname{Var}[y\mid
x_{i}]=\operatorname{Var}[y]-\operatorname*{\mathbb{E}}[x_{i}y]^{2}/\operatorname{Var}[x_{i}].$

Computing some values for $\mu$ and $\mu^{\prime}$, we get that

$\operatorname*{\mathbb{E}}_{\mu}[y\mid
x_{i}]=\operatorname*{\mathbb{E}}_{\mu}[x_{i}y]x_{i}~{};\quad\operatorname*{\mathbb{E}}_{\mu^{\prime}}[y\mid
x_{i}]=\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{i}y]x_{i};\operatorname{Var}_{\mu}[y\mid
x_{i}]=1-\operatorname*{\mathbb{E}}_{\mu}[x_{i}y]^{2}\leq 1.$

We use the formula for the KL of two univariate Gaussians:

######  Lemma 40.

For two univariate Gaussians $X_{1},X_{2}$ with means $\mu_{1},\mu_{2}$ and
covariances $\sigma_{1}^{2},\sigma_{2}^{2}$, respectively,

$\operatorname{KL}(X_{1}\|X_{2})=\log\frac{\sigma_{2}}{\sigma_{1}}+\frac{\sigma_{1}^{2}}{2\sigma_{2}^{2}}-\frac{1}{2}+\frac{(\mu_{1}-\mu_{2})^{2}}{2\sigma_{2}^{2}}\geq\frac{(\mu_{1}-\mu_{2})^{2}}{2\sigma_{2}^{2}}$

###### Proof.

The first equality is folklore and follows from a direct calculation. To get
the inequality, notice that
$\log\frac{\sigma_{2}}{\sigma_{1}}+\frac{\sigma_{1}^{2}}{2\sigma_{2}^{2}}-\frac{1}{2}$
is the KL of two Gaussians with variances $\sigma_{1}$ and $\sigma_{2}$ and
the same means, hence it is nonnegative. ∎

we have that

$\operatorname{KL}(\mu^{\prime}_{y\mid x_{i}}\|\mu_{y\mid
x_{i}})\geq\frac{(\operatorname*{\mathbb{E}}_{\mu^{\prime}}[y\mid
x_{i}]-\operatorname*{\mathbb{E}}_{\mu^{t}}[y\mid
x_{i}])^{2}}{2\operatorname{Var}_{\mu^{t}}[y\mid
x_{i}]}\geq\frac{x_{i}^{2}(\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu}[x_{i}y])^{2}}{2}\enspace.$

Substituting this in the right hand side of (37) and using the fact that
$\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{i}^{2}]=1$, we get the desired
result.

####  D.4.3 Another upper bound on the KL

######  Lemma 41.

Let $\mu_{x}$ and $\mu^{\prime}_{x}$ be two leaf distributions with parameters
$\rho$ and $\rho^{\prime}$, respectively, which are $(A,B)$-bounded, namely,
for all $i$, $A\leq\rho_{i},\rho^{\prime}_{i}\leq 1-B$. Assume further that
$\operatorname{Var}_{\mu}[x_{i}]=\operatorname{Var}_{\mu^{\prime}}[x_{i}]=1$
for all $i$. Then,

$\operatorname{KL}(\mu^{\prime}_{x}\|\mu_{x})\geq
cA^{4}\max_{i}|\rho_{i}-\rho^{\prime}_{i}|,$

where $c>0$ is a universal constant.

Below, we prove Lemma 41. We note that there exist $i,j$ such that
$|\rho_{i}\rho_{j}-\rho^{\prime}_{i}\rho^{\prime}_{j}|$ is large. Indeed, let
$i$ be the maximizer of $|\rho_{i}-\rho^{\prime}_{i}|$. For the purpose of
lower bounding $|\rho_{i}\rho_{j}-\rho^{\prime}_{i}\rho^{\prime}_{j}|$, we can
assume that $\rho_{i}>\rho^{\prime}_{i}$. Denote, let
$\lambda=\rho_{i}/\rho^{\prime}_{i}$. Denote
$M=\max_{j}|\rho_{j}-\rho^{\prime}_{j}|$. Notice that

$\lambda-1=(\rho_{i}-\rho^{\prime}_{i})/\rho^{\prime}_{i}\geq\rho_{i}-\rho^{\prime}_{i}=\max_{l}|\rho_{l}-\rho^{\prime}_{l}|=M.$

Then, divide into cases:

  * •

If there exist two different values, $j,k$, such that
$\rho_{j}/\rho^{\prime}_{j},\rho_{k}/\rho^{\prime}_{k}\leq\sqrt{1/\lambda}$.
Then,

$\frac{\rho_{j}^{\prime}\rho_{k}^{\prime}}{\rho_{j}\rho_{k}}\geq\lambda,$

hence

$\rho_{j}^{\prime}\rho_{k}^{\prime}-\rho_{j}\rho_{k}=\frac{\rho_{j}^{\prime}\rho_{k}^{\prime}-\rho_{j}\rho_{k}}{\rho_{j}\rho_{k}}\rho_{j}\rho_{k}\geq(\lambda-1)\rho_{j}\rho_{k}\geq
M\rho_{j}\rho_{k}\geq MA^{2}.$

  * •

Otherwise, there is some $j$ such that
$\rho_{j}/\rho^{\prime}_{j}\geq\sqrt{1/\lambda}$. Then,

$\frac{\rho_{i}\rho_{j}}{\rho^{\prime}_{i}\rho^{\prime}_{j}}\geq\sqrt{\lambda}\geq\sqrt{M+1}\geq
1+cM,$

for some universal constant $c>0$. This implies that

$\rho_{i}\rho_{j}-\rho^{\prime}_{i}\rho^{\prime}_{j}=\frac{\rho_{i}\rho_{j}-\rho^{\prime}_{i}\rho^{\prime}_{j}}{\rho_{i}\rho_{j}}\rho_{i}\rho_{j}\geq
cM\rho_{i}\rho_{j}\geq cMA^{2}.$

This derives that there exist some $j,k$ such that
$|\rho_{j}\rho_{k}-\rho^{\prime}_{j}\rho^{\prime}_{k}|\geq cA^{2}M$ for some
universal constant $c>0$. This implies that

$|\operatorname*{\mathbb{E}}_{\mu}[x_{j}x_{k}]-\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{j}x_{k}]|\geq
cA^{2}M.$

From this point onwards, the proof is analogous to the proof of Lemma 38. We
start by arguing that by the data processing inequality,

$\operatorname{KL}(\mu^{\prime}_{x}\|\mu_{x})\geq\operatorname{KL}(\mu^{\prime}_{x_{j}x_{k}}\|\mu_{x_{j}x_{k}}).$

Then, we lower bound
$\operatorname{KL}(\mu^{\prime}_{x_{j}x_{k}}\|\mu_{x_{j}x_{k}})$ using the
fact that
$|\operatorname*{\mathbb{E}}_{\mu}[x_{j}x_{k}]-\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{j}x_{k}]|$,
exactly the same way as in Lemma 38 we lower bounded
$\operatorname{KL}(\mu^{\prime}_{x_{i}y}\|\mu_{x_{i}y})$ using the fact that
$|\operatorname*{\mathbb{E}}_{\mu}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{\prime}}[x_{i}y]|$
is large. The proof follows.

####  D.4.4 Proof of Lemma 36

The proof follows directly from Lemma 37 and Lemma 41 that were proven in the
previous subsections.

###  D.5 Contraction in KL - population EM

In this section, we prove that the KL between the true and the current model
contracts by a constant factor in each iteration, for the populatoin EM.
Later, we will show how to derive the same results for the sample-EM as well.

######  Proposition 1.

Let $\rho^{t}$ denote iterate $t$ of the population-EM, and assume that the
iterates are $(A,B)$-bounded. Then,

$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\leq(1-\kappa)\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t}),$

where $\kappa=A^{C_{1}}B^{C_{2}}/n^{C_{3}}$ for some universal constants
$C_{1},C_{2},C_{3}>0$.

We describe the proof of Proposition 1, in the subsections below.

####  D.5.1 First bound on the KL difference

We will prove the following lemma:

######  Lemma 42.

$\mathrm{KL}(\mu_{x}^{*}\|\mu_{x}^{t})-\mathrm{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\geq\mathrm{KL}(\mu^{t+1}\|\mu^{t})$

First of all, we use the following well-known behavior of the EM:

######  Lemma 43 (Folklore.).

$\mathrm{KL}(\mu_{x}^{*}\|\mu_{x}^{t})-\mathrm{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\geq\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t,*}}[\log\Pr_{\mu^{t+1}}[(x,y)]]-\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t,*}}[\log\Pr_{\mu^{t}}[(x,y)]]\enspace.$
(38)

###### Proof of Lemma 42.

We conclude Lemma 42 by analyzing the right hand side of (38). Notice that by
Lemma 1,

$\displaystyle\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t,*}}[\log\Pr_{\mu^{t+1}}[(x,y)]]=\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t,*}}\left[\log\Pr_{\mu^{t+1}}[y]+\sum_{i}\log\Pr_{\mu^{t+1}}[x_{i}\mid
y]\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t+1}}\left[\log\Pr_{\mu^{t+1}}[y]+\sum_{i}\log\Pr_{\mu^{t+1}}[x_{i}\mid
y]\right]=\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t+1}}[\log\Pr_{\mu^{t+1}}[(x,y)]]\enspace.$

Similarly,

$\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t,*}}[\log\Pr_{\mu^{t}}[(x,y)]]=\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t+1}}[\log\Pr_{\mu^{t}}[(x,y)]]\enspace.$

Hence, the right hand side of (38) equals

$\operatorname*{\mathbb{E}}_{x,y\sim\mu^{t+1}}[\log\Pr_{\mu^{t+1}}[(x,y)]-\log\Pr_{\mu^{t}}[(x,y)]]=\operatorname{KL}(\mu^{t+1}\|\mu^{t}),$

as required. ∎

####  D.5.2 Bounding the KL by the covariance difference

We apply Lemma 38 with $\mu=\mu^{t}$ amd $\mu^{\prime}=\mu^{t+1}$. Note that
this lemma requires that $\operatorname{Var}_{\mu^{t}}[y]=1$. Indeed, for the
purpose of proving Proposition 1, we can assume that, since this proposition
only argues about the $x$-marginal, and since the correlation parameters
$\rho^{t}$ and $\rho^{t+1}$ are not affected by
$\operatorname{Var}_{\mu^{t}}[y]$. Then, Lemma 38, in combination with Lemma
42, imply that

$\mathrm{KL}(\mu_{x}^{*}\|\mu_{x}^{t})-\mathrm{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\geq\mathrm{KL}(\mu^{t+1}\|\mu^{t})\geq\max_{i}\frac{\left(\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]\right)^{2}}{2}\enspace.$
(39)

####  D.5.3 Minimal eigenvalue bound

We would like to lower bound the right hand side of (39). To do so, we start
with an auxiliary lemma, bounding the minimal eigenvalue of some matrix.

######  Lemma 44.

Let $U$ be a matrix with $U_{ij}=u_{j}$ if $i\neq j$ and $\sum_{k\neq i}u_{k}$
otherwise, where $u_{i}>0$ for all $i$. Then,

$\sigma_{\min}(U):=\max_{a\colon\|a\|_{2}=1}\|Ua\|_{2}\geq\frac{(\min_{i}u_{i})^{3}}{\|u\|_{2}\|u\|_{1}}\cdot\frac{(n-2)^{3}}{128n^{3}}\enspace.$

Our goal is to show that the minimal singular value of this matrix is bounded
away from $0$. In particular, denote $Ua=K$ for some unit vector
$a=(a_{1},\dots,a_{n})$ and $K=(K_{1},\dots,K_{n})$ and our goal is to lower
bound $\|K\|$. The proof has multiple ingredients. First, we denote by
$s=\sum_{i}u_{i}$ and $t=\sum_{i}a_{i}u_{i}$. We have that

$K_{i}=a_{i}\sum_{j\neq i}u_{j}+\sum_{j\neq i}a_{j}u_{j}=t+a_{i}(s-2u_{i}),$

hence

$t+a_{i}(s-2u_{i})-K_{i}=0,$ (40)

In particular, we have for all $i\neq j$

$a_{i}(s-2u_{i})-K_{i}=a_{j}(s-2u_{j})-K_{j}.$

Let us assume that $u_{1}\geq u_{2}\geq\cdots\geq u_{n}\geq$.

##### If $|s-2u_{1}|$ is small.

######  Lemma 45.

Assume that $|s-2u_{1}|\leq(n-2)u_{n}/(8n)$. Then,
$\max_{i}|K_{i}|\geq(n-2)u_{n}/(16n)$.

###### Proof.

Denote $\epsilon=|s-2u_{1}|$ and let us lower bound $\|K\|$. Then, we have for
all $i$,

$a_{i}(s-2u_{i})-K_{i}=a_{1}\epsilon-K_{1}.$

Hence, for all $i>1$,

$a_{i}=\frac{a_{1}\epsilon-K_{1}+K_{i}}{s-2u_{i}}.$

Denote $K=\max_{i}K_{i}$. Then,

$|a_{i}|=\left|\frac{a_{1}\epsilon-
K_{1}+K_{i}}{s-2u_{i}}\right|\leq\frac{|\epsilon|+2K}{s-2u_{i}}.$

Notice that $s-2u_{i}\geq s-u_{1}-u_{2}\geq(n-2)u_{n}$. Then,

$|a_{i}|\leq\frac{|\epsilon|+2K}{(n-2)u_{n}}.$

Denote the right hand side by $m$. Then,

$|t|=|\sum_{i}a_{i}u_{i}|\geq|a_{1}u_{1}|-\sum_{i>1}|a_{i}|u_{i}\geq|a_{1}|u_{1}-m\sum_{i>1}u_{i}.$

Further, recall that $\sum_{i}a_{i}^{2}=1$ hence
$a_{1}^{2}=1-\sum_{i>1}a_{i}^{2}\geq 1-nm$ hence $|a_{i}|\geq\sqrt{1-nm}\geq
1/2$ assuming that $m<1/(2n)$. Hence, $t\geq u_{1}/2-m\sum_{i>1}u_{i}\geq
u_{1}/2-mnu_{1}\geq u_{1}/4$ assuming that $m<1/(4n)$. We derive that

$|K_{1}|=|t+a_{1}(s-2u_{1})|\geq|t|-|a_{1}||s-2u_{1}|\geq|t|-|\epsilon|\geq
u_{1}/4-|\epsilon|.$

In particular, if $|\epsilon|\leq u_{1}/8$ then $K_{1}\geq u_{1}/8$. Recall
that we further assumed that $m\leq 1/(4n)$ which is satisfied whenever

$|\epsilon|\leq\frac{(n-2)u_{n}}{8n}$

and

$K\leq\frac{(n-2)u_{n}}{16n}.$

We derive that if

$|\epsilon|\leq\frac{(n-2)u_{n}}{8n}$

then

$K\geq\frac{(n-2)u_{n}}{16n}.$

∎

#####  $t$ is large or $K_{i}$ is large.

######  Lemma 46.

Assume that $|s-2u_{1}|\geq\epsilon$. Then, either
$\sum_{i}|K_{i}|\geq\epsilon/2$ or $t\geq\epsilon/2n$.

###### Proof.

We assume that $|s-2u_{1}|\geq\epsilon$. Then, $|s-2u_{i}|\geq\epsilon$ for
all $i$. Further, recall from (40) that $|a_{i}(s-2u_{i})+t|=|K_{i}|$, which
implies that $|K_{i}|\geq|a_{i}(s-2u_{i})|-|t|\geq|a_{i}|\epsilon-t$. Then,
$\sum_{i}|K_{i}|\geq\epsilon\sum_{i}|a_{i}|-nt=\epsilon\|a\|_{1}-nt\geq\epsilon\|a\|_{2}-nt=\epsilon-
nt$. In particular, either $t\geq\epsilon/2n$ or
$\sum_{i}|K_{i}|\geq\epsilon/2$. ∎

##### Assuming that $u_{1}<s/2$.

######  Lemma 47.

Assume that $t\neq 0$ and that $s-2u_{1}\geq\epsilon$. Then,
$\|K\|_{2}\geq\epsilon t/\|u\|_{2}$.

###### Proof.

From (40), for all $i$,

$a_{i}=\frac{K_{i}-t}{s-2u_{i}}.$

From definition of $t$,

$t=\sum_{i}a_{i}u_{i}=\sum_{i}\frac{u_{i}K_{i}-u_{i}t}{s-2u_{i}}\leq\sum_{i}\frac{u_{i}K_{i}-u_{i}t}{s-2u_{i}}\leq\sum_{i}\frac{|a_{i}K_{i}|}{s-2u_{i}}\leq\sum_{i}\frac{|u_{i}K_{i}|}{\epsilon}\leq\frac{\|u\|_{2}\|K\|_{2}}{\epsilon}$
(41)

Hence

$\|K\|_{2}\geq\epsilon t/\|u\|_{2}.$

∎

##### The case that $u_{1}>s/2$.

######  Lemma 48.

Assume that $2u_{1}-s\geq\epsilon$ and that $t\neq 0$. Then,

$\|K\|_{2}\geq\frac{2(s-u_{1}-u_{2})\epsilon|t|}{\|u\|_{2}s}\enspace.$

###### Proof.

Using the first few equalities of (41) we get that

$t=\sum_{i}\frac{u_{i}K_{i}-u_{i}t}{s-2u_{i}}\enspace.$

or equivalently,

$1=\sum_{i}\frac{u_{i}K_{i}/t-u_{i}}{s-2u_{i}}=-\sum_{i}\frac{u_{i}}{s-2u_{i}}+R,\quad\text{where
}R=\sum_{i}\frac{u_{i}K_{i}}{t(s-2u_{i})}.$

Then,

$\sum_{i>1}\frac{u_{i}}{s-2u_{i}}-R=\frac{u_{1}}{2u_{1}-s}-1=\frac{s-u_{1}}{2u_{1}-s}=\sum_{i>1}\frac{u_{i}}{2u_{1}-s}.$

hence

$-R=\sum_{i}u_{i}\left(\frac{1}{2u_{1}-s}-\frac{1}{s-2u_{i}}\right)=2\sum_{i}u_{i}\frac{s-u_{1}-u_{i}}{(s-2u_{i})(2u_{1}-s)}\geq
2\sum_{i}u_{i}\frac{s-u_{1}-u_{2}}{s^{2}}=2\frac{s-u_{1}-u_{2}}{s}.$

We derive that

$\frac{2(s-u_{1}-u_{2})}{s}\leq|R|\leq\frac{1}{|t|}\left|\sum_{i}\frac{u_{i}K_{i}}{|s-2u_{i}|}\right|\leq\frac{1}{|\epsilon
t|}\left|\sum_{i}u_{i}K_{i}\right|\leq\frac{\|u\|_{2}\|K\|_{2}}{|\epsilon
t|}.$

In particular,

$\|K\|_{2}\geq\frac{2(s-u_{1}-u_{2})\epsilon|t|}{\|u\|_{2}s}\enspace.$

∎

We would like to culminate the proof of the main lemma. From Lemma 45 we can
assume that $|s-2u_{1}|\geq(n-2)u_{n}/8n:=\epsilon$, otherwise

$\|K\|_{2}\geq\max_{i}K_{i}\geq(n-2)u_{n}/(16n)$

and the proof follows. From Lemma 46 we can assume that $|t|\geq\epsilon/2n$,
otherwise

$\|K\|_{2}\geq\|K\|_{1}/\sqrt{n}\geq\epsilon/(2\sqrt{n})$

and the proof follows. Lastly, from Lemma 47 and Lemma 48 we can derive that

$\|K\|_{2}\geq\frac{\epsilon|t|}{\|u\|_{2}}\min\left(1,\
\frac{2(s-u_{1}-u_{2})}{\|u\|_{2}s}\right)\geq\frac{\epsilon|t|(n-2)u_{n}}{\|u\|_{2}s}\geq\frac{\epsilon^{2}(n-2)u_{n}}{2n\|u\|_{2}s}=\frac{(n-2)^{3}u_{n}^{3}}{128n^{3}\|u\|_{2}s}\enspace.$

####  D.5.4 Bounding the difference in covariance

We are ready to bound the right hand side of (39). This is stated in the
following lemma:

######  Lemma 49.

Assume that the iterates of the population EM are $(A,B)$ bounded, let $t\geq
0$. Then,

$\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2}\geq
c\frac{A^{12}(1-B)^{8}}{n^{11}}\sum_{i}(\rho^{t}_{i}-\rho^{*}_{i})^{2}\enspace,$

where $c>0$ is a universal constant.

We note that Lemma 49 together with (39) imply that

$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})-\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\geq\frac{CA^{C_{1}}B^{C_{2}}}{n^{C_{3}}}\sum_{i=1}^{n}\left(\rho_{i}^{t}-\rho_{i}^{*}\right)^{2}\enspace.$
(42)

Below, we prove Lemma 49. In the proof below, we use $a,b$ to denote bounds on
the iterates: $a\leq\rho^{t}_{i}\leq 1-b$ for all $t$ and $i$. Further, we use
$a^{*}$ and $b^{*}$ to denote bounds on $\rho_{i}^{*}$:
$a^{*}\leq\rho_{i}^{*}\leq b^{*}$. We recall that we assume
$\sigma_{x_{i}}^{t}=\sigma_{y}^{t}=1$ for all $i$. By Lemma 2, we derive that

$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]=\lambda_{i}^{t}+\sum_{j\neq
i}\rho^{*}_{i}\rho^{*}_{j}\lambda_{j}^{t}.$

We can use the same lemma to derive
$\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]$: indeed, if we apply this lemma
in a different scenario where the underlying distribution is $\mu^{t}$ (i.e.
substituting $\mu^{*}=\mu^{t}$), then $\mu^{t+1}=\mu^{t}$ as well. Hence, if
we substitute $\mu^{*}=\mu^{t}$ and $\mu^{t+1}=\mu^{t}$ in this lemma we get
that

$\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]=\lambda_{i}^{t}+\sum_{j\neq
i}\rho^{t}_{i}\rho^{t}_{j}\lambda_{j}^{t}.$

We get that

$(\lambda^{t}_{i})^{2}\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2}=\left(\sum_{j\neq
i}\rho^{*}_{i}\rho^{*}_{j}\lambda^{t}_{i}\lambda^{t}_{j}-\rho^{t}_{i}\rho^{t}_{j}\lambda^{t}_{i}\lambda^{t}_{j}\right)^{2}\enspace.$

Substituting $u_{i}=\lambda^{t}_{i}\rho^{*}_{i}$ and
$v_{i}=\lambda^{t}_{i}\rho^{t}_{i}$, we derive that

$(\lambda^{t}_{i})^{2}\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2}=\left(\sum_{j\neq
i}u_{i}u_{j}-v_{i}v_{j}\right)^{2}\enspace.$

We will prove the following lemma:

######  Lemma 50.

If $u=(u_{1},\dots,u_{n})$, $v=(v_{1},\dots,v_{n})$ where $u_{i},v_{i}>0$ for
all $i$, then

$\sum_{i}\left(\sum_{j\neq
i}u_{i}u_{j}-v_{i}v_{j}\right)^{2}\geq\sigma_{\min}(A)^{2}\cdot\|u-v\|_{2}^{2}$

where $A_{ij}=(u_{i}+v_{i})/2$ if $i\neq j$ and $A_{ii}=\sum_{j\neq
i}(u_{i}+v_{i})/2$.

We will first use Lemma 50 to complete the proof of Lemma 49, and then we’ll
prove Lemma 50.

###### Proof of Lemma 49.

First,

$\sum_{i}(\rho^{t}_{i}-\rho^{*}_{i})^{2}\leq\left(\min_{i}\lambda^{t}_{i}\right)^{-2}\sum_{i}(\lambda_{i}^{t})^{2}(\rho^{t}_{i}-\rho^{*}_{i})^{2}=\left(\min_{i}\lambda^{t}_{i}\right)^{-2}\sum_{i}(u_{i}-v_{i})^{2}.$

Then, by Lemma 50,

$\displaystyle\sum_{i}(u_{i}-v_{i})^{2}\leq\frac{1}{\sigma_{\min}(A)^{2}}\sum_{i}\left(\sum_{j\neq
i}u_{i}u_{j}-v_{i}v_{j}\right)^{2}=\frac{1}{\sigma_{\min}(A)^{2}}\sum_{i}(\lambda_{i}^{t})^{2}\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2}$
$\displaystyle\leq\frac{1}{\sigma_{\min}(A)^{2}}\sum_{i}\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2},$

as $\lambda^{t}_{i}\leq 1$. We conclude that

$\sum_{i}(\rho^{t}_{i}-\rho^{*}_{i})^{2}\leq\frac{1}{(\min_{i}\lambda^{t}_{i})^{2}\sigma_{\min}(A)^{2}}\sum_{i}\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2}\enspace.$
(43)

We would like to expand on this bound. Using the expression of
$\lambda^{t}_{i}$ from (1), we derive that

$\lambda^{t}_{i}=\frac{\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})}{1+\sum_{i=1}^{n}(\rho^{t}_{j})^{2}/(1-(\rho^{t}_{j})^{2})}\enspace.$

From the assumption that $0<a\leq\rho_{i}<b\leq 1$, we derive that

$\rho^{t}_{i}/(1-(\rho^{t}_{i})^{2})\geq\rho^{t}_{i}\geq a,$

while

$(\rho^{t}_{j})^{2}/(1-(\rho^{t}_{j})^{2})\leq 1/(1-(\rho^{t}_{j})^{2})\leq
1/(1-b^{2}).$

Therefore,

$\lambda^{t}_{i}\geq\frac{a}{1+n/(1-b^{2})}=\frac{a(1-b^{2})}{1-b^{2}+n}\geq\frac{a(1-b^{2})}{n+1}\enspace.$
(44)

Further, we want to bound $\sigma_{\min}(A)$. Using Lemma 44 applied on
$u\leftarrow(u+v)/2$, it suffices to estimate properties of $(u+v)/2$. First
of all, using the assumption $a^{*}\leq\rho^{*}_{i}\leq b^{*}$,

$\frac{u_{i}+v_{i}}{2}\geq\frac{u_{i}}{2}=\frac{\lambda^{t}_{i}\rho^{*}_{i}}{2}\geq\frac{a(1-b^{2})a^{*}}{2n+2}\enspace.$

Further, we have that

$\frac{\lambda^{t}_{i}(\rho^{t}_{i}+\rho^{*}_{i})}{2}\leq 1,$

which implies that

$\|(\overline{u}+\overline{v})/2\|_{1}\leq n,\
\|(\overline{u}+\overline{v})/2\|_{2}\leq\sqrt{n}\enspace.$

Using Lemma 44, the minimal eigenvalue of $A$ is at least

$\frac{(\min_{i}(u_{i}+v_{i})/2)^{3}}{\|(u+v)/2\|_{2}\|(u+v)/2\|_{1}}\cdot\frac{(n-2)^{3}}{128n^{3}}\geq\frac{a^{3}(1-b^{2})^{3}(a^{*})^{2}}{(2n+2)^{3}n^{3/2}}\cdot\frac{(n-2)^{3}}{128n^{3}}\geq
c\frac{a^{3}(1-b)^{3}(a^{*})^{2}}{n^{9/2}}\enspace,$

where $c>0$ is some universal constant. Substituting this and the lower bound
on $\lambda^{t}_{i}$ (Eq. (44)), in (43), we derive that

$\left(\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]-\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]\right)^{2}\geq
c^{\prime}\frac{a^{8}(1-b)^{8}(a^{*})^{4}}{n^{11}}\sum_{i}(\rho^{t}_{i}-\rho^{*}_{i})^{2}\enspace$

where $c^{\prime}>0$ is a universal constant. ∎

Now we will prove Lemma 50. Define for $i=1,\dots,n$ functions
$p_{i}(w)=\sum_{j\neq i}w_{i}w_{j}$ where $w=(w_{1},\dots,w_{n})$. Let
$p(w)=(p_{1}(w),\dots,p_{n}(w))$, then we want to show that
$\|p(u)-p(v)\|^{2}\geq C\cdot\|u-v\|^{2}$. We use the following simple
observation:

######  Lemma 51.

Let $p(x)$ be a second-degree polynomial of one variable $x$ and let
$p^{\prime}(x)$ denote its derivative. Then, for any $s,t\in\mathbb{R}$,

$p(s)-p(t)=p^{\prime}((s+t)/2)(s-t).$

###### Proof.

Let $p(x)=ax^{2}+bx+c$. Then, $p^{\prime}(x)=2ax+b$. Then,

$p(s)-p(t)=a(s^{2}-t^{2})+b(s-t)$

while

$p^{\prime}((s+t)/2)(s-t)=(a(s+t)+b)(s-t)=as^{2}-at^{2}+b(s-t)=p(s)-p(t).$

∎

We use the following corollary:

######  Lemma 52.

Let $p\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$ be a system of second-degree
polynomials, namely, $p(x)=(p_{1}(x),\dots,p_{n}(x))$ where each $p_{i}$ is a
second degree polynomial. Then,

$\overline{p}(\overline{s})-\overline{p}(\overline{t})=J^{p}|_{(\overline{s}+\overline{t})/2}(\overline{s}-\overline{t}),$
(45)

where $J^{\overline{p}}|_{\overline{x}}$ is the Jacobian matrix of
$\overline{p}$ evaluated at $\overline{x}$, namely,

$\left(J^{\overline{p}}|_{\overline{x}}\right)_{ij}=\frac{dp_{i}(\overline{x})}{dx_{j}}\enspace.$

Consequently,

$\|\overline{p}(s)-\overline{p}(t)\|\geq\sigma_{\min}(J^{\overline{p}}|_{\overline{x}})\|s-t\|,$
(46)

where $\sigma_{\min}(A)$ is the minimal singular value of a matrix $A$.

###### Proof.

To show the first part, look at the path
$\gamma(\lambda)=\lambda\overline{t}+(1-\lambda)\overline{s}$. Then,
$\gamma(1)=\overline{t}$ while $\gamma(0)=\overline{s}$. Applying Lemma 51 on
the polynomials $p_{i}(\gamma(\lambda))$ while substituting $s=0$ and $t=1$,
one obtains (45). Then, (46) follows from taking the norm in both sides of the
above equality, and using the fact that for a matrix $A$ and a vector
$\overline{v}$, $\|A\overline{v}\|\geq\sigma_{\min}(A)\|\overline{v}\|$. ∎

To complete the proof of Lemma 50, notice that the matrix $A$ in this lemma is
the Jacobian of $\overline{p}$ evaluated at $(u+v)/2$.

####  D.5.5 Bounding the parameter difference by the KL: conclusion of
Proposition 1

To conclude Proposition 1, we would like to bound the right hand side of (42).
Recall that this right hand side contains the term
$\|\rho^{t}-\rho^{*}\|_{2}^{2}$. By Lemma 37, this is lower bounded by

$\frac{B^{C_{1}}}{n^{C_{2}}}\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t}).$

In combination with (42), this concludes the proof of Proposition 1.

###  D.6 Contraction for the sample EM

While we have proven in Proposition 1 that the sample-EM contracts, we now
prove that the population EM contracts as well:

######  Lemma 53.

Let $\mu^{t}$ denote the $t$’th iterate of the sample EM, and assume that the
sample is $\eta$-representative. Assume that
$\eta\leq\min\left(1,\sqrt{\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})}\right)(AB/n)^{C}$
for some sufficiently large universal constant $C>0$. Then,

$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\leq(1-\kappa^{\prime})\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t}),$

where $\kappa\geq(AB/n)^{C^{\prime}}$ for some universal constant
$C^{\prime}>0$.

###### Proof.

Below, we prove Lemma 53. To argue about that, we would use the Lemma 35 which
argues that the sample step is close to the population step, in parameter
distance, and further, we will use Lemma 37 to argue that this implies that
the KL distance after one population step is close to that after one sample
step. To be more concrete, let $\rho^{t}$ denote the $t$’th iterate of the
sample EM, let $\tilde{\rho}^{t+1}$ denote the result of applying one step of
the population EM on $\rho^{t}$ and let $\rho^{t+1}$ denote iterate $t+1$ of
the sample EM, namely, $\rho^{t+1}$ is obtained from $\rho^{t}$ via one
iterate of the sample EM. Let $\tilde{\mu}_{x}^{t+1}$ and $\mu_{x}^{t+1}$
denote the corresponding distributions. Then, from Lemma 35, we obtain that
for all $i$,

$|\tilde{\rho}^{t+1}-\rho^{t+1}|\leq\eta\operatorname{poly}(1/A,1/B,n).$

By Lemma 37 this implies that

$\displaystyle\left|\operatorname{KL}(\mu_{x}^{*}\|\mu^{t+1}_{x})-\operatorname{KL}(\mu_{x}^{*}\|\tilde{\mu}^{t+1}_{x})\right|$
$\displaystyle\leq\operatorname{poly}(n,1/A,1/B)\|\rho^{t}-\rho^{t+1}\|\max\left(\|\rho^{t+1}-\rho^{*}\|,\|\tilde{\rho}^{t+1}-\rho^{*}\|\right)$
$\displaystyle\leq\operatorname{poly}(n,1/A,1/B)\eta\max\left(\|\rho^{t+1}-\rho^{*}\|,\|\tilde{\rho}^{t+1}-\rho^{*}\|\right)$
$\displaystyle\leq\operatorname{poly}(n,1/A,1/B)\eta\max\left(\|\rho^{t}-\rho^{*}\|+\|\rho^{t}-\rho^{t+1}\|,\|\tilde{\rho}^{t+1}-\rho^{*}\|\right)$
$\displaystyle=\operatorname{poly}(n,1/A,1/B)\eta\left(\|\rho^{t}-\rho^{*}\|+\|\rho^{t}-\rho^{t+1}\|\right)$
$\displaystyle\leq\operatorname{poly}(n,1/A,1/B)\eta\left(\|\rho^{t}-\rho^{*}\|+\operatorname{poly}(n,1/A,1/B)\eta\right).$

By Lemma 36, the right hand side is at least

$\operatorname{poly}(n,1/A,1/B)\eta\left(\sqrt{\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})}+\eta\right)$

By the assumption of Lemma 53 on $\eta$, this is at least

$2\operatorname{poly}(n,1/A,1/B)\eta\sqrt{KL(\mu_{x}^{*}\|\mu_{x}^{t})}.$

Again, by the assumption on this lemma on $\eta$, if the constant $C$ in this
assumption is sufficiently large, then the last term is bounded by

$KL(\mu_{x}^{*}\|\mu_{x}^{t})(AB/n)^{C_{1}},$

where $C_{1}$ can be chosen arbitrarily large (if $C$ is). Combining with
Proposition 1, this concludes the proof: indeed, let $\kappa$ be the constant
from the proposition. Then,

$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\leq\operatorname{KL}(\mu_{x}^{*}\|\tilde{\mu}_{x}^{t+1})+\left|\operatorname{KL}(\mu_{x}^{*}\|\mu^{t+1}_{x})-\operatorname{KL}(\mu_{x}^{*}\|\tilde{\mu}^{t+1}_{x})\right|\leq(1-\kappa)\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})+KL(\mu_{x}^{*}\|\mu_{x}^{t})(AB/n)^{C_{1}}.$

Recall that $\kappa=(AB/n)^{C_{2}}$ for some universal constant $C_{2}$. Since
we can select $C_{1}$ to be arbitrarily large, we can ensure that
$(AB/n)^{C_{1}}\leq\kappa/2$. This implies that

$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\leq(1-\kappa/2)\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})$

which suffices to conclude the proof. ∎

###  D.7 Concluding the proof of Theorem 2

###### Proof of Theorem 2.

We will assume that the sample is $\eta$-representative, for
$\eta\leq(AB/n)^{C}\epsilon$ for a sufficiently large $C>0$. This can be
guaranteed if the sample size is
$m=O(\log(1/\delta)/\eta^{2})=\operatorname{poly}(n,1/A,1/B)\log(1/\delta)/\epsilon^{2}$.
With this value of $\eta$, Lemma 53 guarantees that as long as
$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})\geq\epsilon(AB/n)^{C_{1}}$, then,

$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t+1})\leq(1-\kappa^{\prime})\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t}),$

where $C_{1}$ can be chosen arbitrarily large and $\kappa^{\prime}$ is
polynomial in $A,B,1/n$. The initial value of
$\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{0})$ is bounded by
$\operatorname{poly}(1/A,1/B,n)\|\rho^{0}-\rho^{*}\|^{2}\leq
n\operatorname{poly}(1/A,1/B,n)$, from Lemma 36. Hence, the number of
iterations that it takes $\operatorname{KL}(\mu_{x}^{*}\|\mu_{x}^{t})$ to drop
below $\epsilon(AB/n)^{C_{1}}$ is bounded by
$\operatorname{poly}(n,1/A,1/B)\log(1/\epsilon)$. Using Lemma 36, if $C_{1}$
is sufficiently large then once the KL divergence drops below that value,
$|\rho^{t}_{i}-\rho^{*}_{i}|\leq\epsilon$ for all $i$.

Lastly, notice that for all $t\geq 1$ and all $i$,
$\sigma^{t}_{i}=\hat{\sigma}_{i}$, from Lemma 26. Since the sample is
$\eta\leq\epsilon$ representative, this implies that
$|\sigma^{t}_{i}-\sigma^{*}_{i}|\leq\eta\leq\epsilon$. This concludes the
proof. ∎

##  Appendix E General tree model

We consider a multivariate Gaussian latent-tree distribution, that is
characterized by a tree $G=(V,E)$. Each vertex $u\in V$ corresponds to a
random variable $z_{u}$. Suppose the total number of nodes in the tree is
$n+m$. From now on, we might refer to the node itself as the random variable,
when it is clear from the context what we mean. We define a joint probability
distribution over the nodes as follows:

$\Pr[z_{1},\ldots,z_{n+m}]=\prod_{(i,j)\in E}\Pr[z_{i},z_{j}]$ (47)

The vertices $V$ are divided into two groups: nodes of degree $1$(leaves),
denoted by $x_{1},\ldots,x_{n}$ and nodes of degree at least $2$ (internal
nodes), denoted by $y_{1},\ldots,y_{m}$. When we want to refer to some node in
the tree without wanting to specify whether it is a leaf or an internal node,
we will use the symbol $z$. The edges $e\in E$ are divided into two groups:
the ones that are between $y$ nodes, called _internal edges_ and denoted by
$E_{yy}$, and the ones between one $y$ node and one $x$ node, called _boundary
edges_ and denoted by $E_{xy}$. Each leaf $x_{i}$ has a variance
$\sigma_{x_{i}}^{2}$ and so it corresponds to a random variable $x_{i}\sim
N(0,\sigma_{x_{i}}^{2})$. Likewise, each internal node $y_{i}$ has a variance
$\sigma_{y_{i}}^{2}$ and so it corresponds to a random variable $y_{i}\sim
N(0,\sigma_{y_{i}}^{2})$. For each edge $(y_{i},y_{j})\in E_{yy}$ we define
the correlation $\rho_{y_{i}y_{j}}$ of variables $y_{i},y_{j}$ and similarly,
for each edge $(x_{i},y_{j})\in E_{xy}$ we define the correlation
$\rho_{x_{i}y_{j}}$ between $x_{i},y_{j}$. It can be shown that in a Gaussian
Graphical Model that satisfies the product decomposition 47, it can be shown
that these parameters are enough to specify the joint distribution over all
$x$ and $y$.

$\rho_{z_{i}z_{j}}:=\frac{\operatorname*{\mathbb{E}}[z_{i}z_{j}]}{\sigma_{z_{i}}\sigma_{z_{j}}}=\prod_{(z_{u},z_{v})\in
P(z_{i},z_{j})}\rho_{z_{u}z_{v}}$

In other words, the correlation between a pair of nodes is the product of the
correlations along the edges of the path that connects them.

Define such distribution by $\mu_{G,\overline{\rho},\overline{\sigma}}$ where
$G$ is ommitted if it is clear from context. A sample
$\overline{z}\sim\mu_{\overline{\rho},\overline{\sigma}}$ can be drawn as
follows: first, $z_{r}\sim N(0,\sigma_{r}^{2})$ is drawn for the root $r$ (the
root can be assigned as any node of the tree). For any choice of the root,
there is a unique way to direct the edges going away from the root. This
defines parent-child relationships between the nodes. One assigns random
values from the remaining of the nodes, from top to bottom. Assuming that the
value $z_{u}$ on the parent $u$ of a node $v$ was already set, we draw $z_{v}$
as follows:

$z_{v}=\sigma_{v}\left(\rho_{uv}\frac{z_{u}}{\sigma_{u}}+\sqrt{1-\rho_{uv}^{2}}\epsilon_{v},\right)$

where $\epsilon_{v}\sim N(0,1)$ independently of the other variables and
$\rho_{uv}=\rho_{e}$ for the edge $e$ that connects $u$ and $v$. Up to scaling
the individual variables, one can assume that $\sigma_{v}=1$ for all $v$.

An equivalent way to characterize the distribution is through the information
matrix $J=\Sigma^{-1}$. Because of the factorization of the distribution, the
only non-zero entries $J_{ij}$ will be when $(i,j)$ is an edge or if $i=j$. In
general, the distribution could have an external field $h$. This will not
happen in the joint distribution, since we assume the means to be $0$.

In the following, we will also need the conditional distribution of the
internal nodes $y$ given the leaves $x$. Since the model is Gaussian, we know
that there exists a matrix $\lambda\in\mathbb{R}^{m\times n}$ such that

$\operatorname*{\mathbb{E}}[y_{i}|x]=\sum_{j}\lambda_{y_{i}x_{j}}x_{j}$ (48)

Lastly, the external field of $y$ in the conditional distribution is given by
the relation

$h_{y}=-J_{yx}x$

All these properties will prove useful in the sequel.

In an estimation setting, we observe independent samples from the latent
distribution over the leaves of the tree. In particular, each sample contains
the information of $(x_{l})_{l=1}^{n}$, obtained using one draw from the
marginal (joint) distribution over the leaves. The goal is to learn the
parameters $\rho_{e}$ for all the edges of the tree and the variances
$\sigma_{l}^{2}$ for all leaves $l$.

######  Remark 1.

The variances $\sigma_{y_{v}}^{2}$ on the internal nodes $y_{v}$ of the tree
cannot be estimated. This is due to the fact that samples from two
distributions
$\mu_{\overline{\rho},\overline{\sigma}},\mu_{\overline{\rho},\overline{\sigma}^{\prime}}$
that have the same correlations $\overline{\rho}$ and the same variances on
the leaves, differ only by a scaling of the unobseved nodes. In particular, we
can transfer a sample from one distribution to a sample from the other by just
multiplying the hidden nodes by constants. This change does not affect the
marginal distribution over the observed nodes.

######  Remark 2.

One has to assume that each internal node has degree at least $3$. Indeed, if
$v$ is an internal node with neighbors $u_{1},u_{2}$, then, as long as
$\rho_{u_{1}v}\rho_{vu_{2}}$ remains constant, the distribution over the
leaves is not affected. In case that such a node $v$ exists, one can remove it
while keeping the same distribution over the leaves. In particular, $u_{1}$ is
connected with $v$ and one sets $\rho_{u_{1}u_{2}}$ as equal to the value
$\rho_{u_{1}v}\rho_{vu_{2}}$ in the old graph.

##  Appendix F EM and the likelihood function for general trees

We are interested in analyzing the landscape of the likelihood function over
the space of unknown parameters $J$. In particular, we show that we can
characterize the stationary points of the likelihood function for a general
tree. To help us identify the stationary points, it is convenient to view them
as fixpoints of the EM algorithm.

Let $\mathcal{P}_{G}$ be the set of all distributions of the form
$\mu_{G,\rho,\sigma}$ for any possible values of $\rho$ and $\sigma$. In each
iteration $t=0,1,\dots$, the algorithm will hold some distribution $\mu^{t}$,
such that $\mu^{0}$ is arbitrary, and $\mu^{t}$ is obtained using $\mu^{t-1}$.
The goal is to find some unknown distribution $\mu^{*}\in\mathcal{P_{G}}$,
given only samples from $\mu^{*}_{x_{1}\cdots x_{n}}$, namely,
$y_{1},\ldots,y_{m}$ is not observed. The algorithm can be described as
follows: we set $\mu^{0}\in\mathcal{P}$ arbitrarily. Then, at any $t>0$,
define

$\mu^{t+1}=\max_{\mu\in\mathcal{P}_{G}}\operatorname*{\mathbb{E}}_{x_{1}\cdots
x_{n}\sim\mu^{*}_{x_{1}\cdots
x_{n}}}\operatorname*{\mathbb{E}}_{y\sim\mu^{t}_{y\mid x_{1}\cdots
x_{n}}}[\log\Pr_{\mu}(x_{1},\dots,x_{n},y)],$ (49)

where $\Pr_{\mu}$ denotes the density with respect to $\mu$. Denote by
$\sigma_{\cdot}^{t},\rho_{i}^{t},J^{t}$ the parameters corresponding to
$\mu^{t}$ and by $\lambda^{t}$ the coefficients from (48). Similarly,
$\sigma_{\cdot}^{*},\rho_{i}^{*}$ and $\lambda^{*}$ correspond to $\mu^{*}$.
We would like to understand what are the fixpoints of this iteration rule and
how they relate to the stationary points of the likelihood function. For this
purpose, we first describe more explicitly the update rule in each iteration.
The proof follows along the same lines as Lemma 1.

######  Lemma 54.

Let $\mu^{t,*}$ denote the joint distribution over $x_{1}\cdots
x_{n},y_{1},\ldots,y_{m}$ such that

$\mu^{t,*}(x_{1},\cdots,x_{n},y_{1},\ldots,y_{m})=\mu^{*}(x_{1},\cdots,x_{n})\mu^{t}_{y_{1},\ldots,y_{m}\mid
x_{1},\cdots,x_{n}}(y).$

Then, for any $x_{i},y_{j},y_{k}$, we have that

$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y_{j}]=\operatorname*{\mathbb{E}}_{\mu^{t,*}}[x_{i}y_{j}],\
\operatorname*{\mathbb{E}}_{\mu^{t+1}}[y_{j}y_{k}]=\operatorname*{\mathbb{E}}_{\mu^{t,*}}[y_{j}y_{k}],\
\operatorname{Var}_{\mu^{t,*}}[x_{i}]=\operatorname{Var}_{\mu^{t+1}}[x_{i}],\
\operatorname{Var}_{\mu^{t,*}}[y_{j}]=\operatorname{Var}_{\mu^{t+1}}[y_{j}]\enspace.$

We notice that the variance of the leaves remains the same at each iteration.
This means that the determining quantity for the distribution in each
iteration are the correlations $\rho^{t}$. In particular, during the execution
of the algorithm, the variances of the internal nodes might be different than
$1$, however the correlations always dictate the next iteration. Hence, for
any fixpoint $\tilde{\mu}$ of the procedure that is given by some parameters
$\tilde{\sigma},\tilde{J}$ can be converted into a fixpoint with the same
likelihood value but with all internal nodes $y$ having variance $1$.
Therefore, in the sequel when we analyze the fixpoint of this rule, we assume
w.l.o.g. that all variances are equal to $1$. By scaling the variances of the
internal nodes, we can obtain all equivalent fixpoints.

To see how the fixpoint of this rule relates to the stationary points of the
log-likelihood, let’s first choose a parametrization in terms of the inverse
covariance matrix $J$. This exponential family parametrization will enable us
to compute the stationary points easily by setting the derivatives to $0$.

We first define the function
$L:\mathbb{R}^{(n+m)\times(n+m)}_{+}\mapsto\mathbb{R}$ as

$L(J):=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\mu(J)}(x)$

We have the following Lemma, which connects the stationary points of $L$ with
the fixpoints of EM. The proof is standard and is omitted.

######  Lemma 55.

Let $\mu^{*}\in P_{G}$ be such that $\rho^{*}_{ij}\in(0,1)$ for all $(i,j)\in
E$. Then, for any $\tilde{J}\in\mathbb{R}^{(n+m)\times(n+m)}_{+}$ we have that
$\nabla L(\tilde{J})=0$ if and only if $\tilde{J}$ is a stationary point of
the update rule (49).

Hence, the two notions of stationarity are equivalent and we can focus on
understanding when the update rule (49) has a fixpoint.

##  Appendix G Uniqueness of stationary points of EM for general trees

We would like to prove that the only stationary point of the log-likelihood if
$\tilde{\rho}_{ij}\in(0,1)$ is when $\tilde{\rho}=\rho^{*}$. This is the
content of the following Theorem. See 3

###### Proof.

Let $\tilde{\mu}$ denote the distribution induced by the fixpoint
$\tilde{\rho}$. Let $\tilde{J}$ be the information matrix and $\tilde{\Sigma}$
the covariance matrix corresponding to $\tilde{\rho}$. Also, let $\mu^{*,f}$
denote the distribution with density

$\mu^{*,f}(x,y)=\mu^{*}(x)\tilde{\mu}(y|x)$

Using Lemma 54, we get that in the fixpoint we should have for all
$z_{i},z_{j}\in V$

$\operatorname{Var}_{\mu^{*,f}}(z_{i})=\operatorname{Var}_{\tilde{\mu}}(z_{i})\quad,\quad\operatorname{Cov}_{\mu^{*,f}}(z_{i},z_{j})=\operatorname{Cov}_{\tilde{\mu}}(z_{i},z_{j})$
(50)

where $z_{i},z_{j}$ are either leaf or non-leaf nodes that are connected in
the topology of $G$.

We will show that the only possible solution to this system of equations is
$\tilde{\rho}=\rho^{*}$. First, let us analyze these equations for two non-
leaf nodes $y_{1},y_{2}$ that are connected in $G$. Since all the variables
are zero mean, we have by the definition of $\mu^{*,f}$ that

$\displaystyle\operatorname{Cov}_{\mu^{*,f}}(y_{1},y_{2})$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mu^{*,f}}[y_{1}y_{2}]=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}y_{2}|x]]=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[\operatorname{Cov}_{\tilde{\mu}}(y_{1},y_{2}|x)+\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{2}|x]]$

We get a similar equation for $\tilde{\mu}$, namely that

$\operatorname{Cov}_{\tilde{\mu}}(y_{1},y_{2})=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[\operatorname{Cov}_{\tilde{\mu}}(y_{1},y_{2}|x)+\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{2}|x]]$

At this point, we notice that the first of the two terms contains the quantity
$\operatorname{Cov}_{\tilde{\mu}}(y_{1},y_{2}|x)$, which does not depend on
the value $x$ that we condition upon (this can be seen by just applying the
conditioning formula for gaussians). Hence, this term will appear in both
sides of the equation and can be cancelled. So, we only need to compute the
second term, which will depend on the values $x$. A similar argument for the
variance shows that

$\displaystyle\operatorname{Var}_{\mu^{*,f}}(y_{1})=\operatorname*{\mathbb{E}}_{\mu^{*}}\left[\operatorname{Var}_{\tilde{\mu}}(y_{1}|x)+\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]^{2}\right]$
$\displaystyle\operatorname{Var}_{\tilde{\mu}}(y_{1})=\operatorname*{\mathbb{E}}_{\tilde{\mu}}\left[\operatorname{Var}_{\tilde{\mu}}(y_{1}|x)+\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]^{2}\right]$
(51)

Again, the conditional variance does not depend on the value of $x$, hence it
will be the same for the two distributions.

After this preliminary observations, let’s see how the we can reduce this
problem to the one latent case. Suppose $y_{1}$ is a latent node and denote
its set of neighbors in $G$ by $N$. Notice that some of the neighbors will be
leaves and some will be non-leaves, which prompts us to partition $N$ into
corresponding subsets $N_{x},N_{y}$. Let’s denote
$s=|N|,s_{x}=|N_{x}|,s_{y}=|N_{y}|$. There is a natural partition of the
leaves $R_{1},\ldots,R_{s}$, which is induced by removing $y_{1}$ from the
graph and taking the leaves in each connected component. We will focus on the
fixed point equations that we get for the covariances of $y_{1}$ with it’s
neighbors. To do that, we should calculate the conditional expectations of
$y_{1}$ and it’s neighbors, given $x$. We will need to be careful when
calculating them, since we would like certain quantities to appear. Therefore,
we will start by marginalizing out all the non-leaf nodes except $y_{1}$ and
$N_{y}$. Let $Y^{c}$ denote these nodes. We first compute what is the external
field of $y_{1}$ and the nodes in $N_{y}$ when we do this marginalization.
Indeed, if $h_{y_{1}}$ was the original external field of $y_{1}$ and the new
external field is $h^{\prime}_{y_{1}}$, then we have that

$h^{\prime}_{y_{1}}=h_{y_{1}}-\tilde{J}_{y_{1}Y^{c}}\tilde{J}_{Y^{c}Y^{c}}^{-1}h_{Y^{c}}$

However, notice that the vector $\tilde{J}_{y_{1}Y^{c}}$ is the $0$ vector,
since $Y^{c}$ does not contain any neighbor of $y_{1}$. Hence, the external
field of $y_{1}$ does not change. Now let $y_{2}$ be a neighbor in $N_{y}$.
Then,

$h^{\prime}_{y_{2}}=h_{y_{2}}-\tilde{J}_{y_{2}Y^{c}}\tilde{J}_{Y^{c}Y^{c}}^{-1}h_{Y^{c}}$

Notice that $h_{y_{2}}$ is a linear combination of the leaves that are
neighbors of $y_{2}$. Also, we can show that the second term of the right hand
side is a linear combination of the leaves that belong to the connected
component corresponding to $y_{2}$ and are not neighbors of $y_{2}$. This is
established in the following Lemma.

See 13

###### Proof.

The leaves in $S_{y_{2}}$ can be partitioned into subsets $A,B$, where $A$ are
the leaves that are neighbors of $y_{2}$ and $B$ the remaining leaves. Let
$T_{2}$ be the topology of the connected component that $y_{2}$ belongs to,
when we remove $y_{1}$. Also, let $N_{2}$ be the neighborhood of $y_{2}$ in
$T_{2}$, with corresponding subsets $N_{2x},N_{2y}$. Clearly, $h_{y_{2}}$ is a
linear combination of the leaves in $A$. We will show that the second term is
a linear combination of the leaves in $B$, thus concluding the claim. First of
all, notice that $\tilde{J}_{Y^{c}Y^{c}}$ is the information matrix of a
gaussian model, whose graphical representation is the tree $G$ when $y_{1}$
and all nodes in $N_{y}$ have been removed. Let’s call $T_{3}$ this new
topology. In this topology, $T_{2}$ has been partitioned into $|N_{2}|$
subtrees, one for each neighbor of $y_{2}$ (because $y_{2}$ is removed).
Hence, the leaves $B$ of $T_{2}$ have been partitioned into $|N_{2y}|$ subsets
$Q_{1},\ldots,Q_{|N_{2y}|}$.

Since $\tilde{J}_{Y^{c}Y^{c}}$ is an information matrix, it’s inverse
$\tilde{J}_{Y^{c}Y^{c}}^{-1}$ is a covariance matrix, where the nodes have
standard deviations $w_{i}$ and normalized covariances (correlations)
$w_{ij}$. Since $T_{3}$ is a forest, there is at most one path connecting each
one of the nodes. Hence, it is well known that the covariances multiply across
paths in this structure, namely:

$(\tilde{J}_{Y^{c}Y^{c}})^{-1}_{ij}=\left\\{\begin{array}[]{ll}0&\text{ , if
$i,j$ are not connected in $T_{3}$}\\\ w_{i}w_{j}\prod_{e\in
P_{ij}}w_{ij}&\text{ , if $P_{ij}$ is the unique path connecting
$i,j$}\end{array}\right.$

Given this description, it is easy to see that for each $i\in Y^{c}$, we have
that $(\tilde{J}_{Y^{c}Y^{c}}^{-1}h_{Y^{c}})_{i}$ is a linear combination of
leaves that belong to the same component as $i$ in $T_{3}$. Hence, for each
$i\in N_{2y}$, $(\tilde{J}_{Y^{c}Y^{c}}^{-1}h_{Y^{c}})_{i}$ is a linear
combination of the leaves of the $Q_{i}$ that $i$ is connected to. Hence,
$\tilde{J}_{y_{2}Y^{c}}\tilde{J}_{Y^{c}Y^{c}}^{-1}h_{Y^{c}}$ is simply a
linear combination of the leaves in all the $Q_{i}$’s, which means it is a
linear combination of the leaves in $B$. ∎

Hence, overall the external field $h^{\prime}_{y_{2}}$ will be a linear
combination of the leaves in $S_{y_{2}}$. The same is true for all nodes in
$N_{y}$. It will be convenient to define the vector $H\in\mathbb{R}^{s}$,
which has one entry for each node in $N$. If the node is a $y_{i}\in N_{y}$,
then define $H_{i}=h^{\prime}_{y_{i}}$. If the node is an $x_{i}\in N_{x}$,
then define $H_{i}=x_{i}$. Let’s focus on some $y_{2}\in N_{y}$ and see what
relations we get in the fixed point. As we say in the earlier computation, the
relation for the covariance becomes

$\operatorname*{\mathbb{E}}_{\tilde{\mu}}[\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{2}|x]]=\operatorname*{\mathbb{E}}_{\mu^{*}}[\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{2}|x]]$
(52)

The inner expectation is common on both sides, so let’s start by calculating
that. Since we have already marginalized out all the nodes in $Y^{c}$, we only
need to marginalize out the nodes in $N_{y}$ other than $y_{2}$. For
convenience, denote $N_{2}=N_{y}\setminus\\{y_{2}\\}$. Then, if we marginalize
out nodes in $N_{2}$, the resulting extenal field $h^{\prime\prime}_{y_{1}}$
will be

$h^{\prime\prime}_{y_{1}}=h_{y_{1}}-\tilde{J}_{y_{1}N_{2}}(\tilde{J}^{\prime}_{N_{2}N_{2}})^{-1}h^{\prime}_{N_{2}}$

The reason why we write $J^{\prime}$ is that the information matrix has been
altered when marginalizing $Y^{c}$. Now, notice that since the neighbors of
$y_{1}$ are not connected with each other, the matrix
$\tilde{J}^{\prime}_{N_{2}N_{2}}$ is diagonal. This means that we have

$h^{\prime\prime}_{y_{1}}=\sum_{x_{i}\in
N_{x}}\tilde{J}_{y_{1}x_{i}}x_{i}+\sum_{y_{j}\in N_{y},y_{j}\neq
y_{2}}\frac{\tilde{J}_{y_{1}y_{j}}}{\tilde{J}^{\prime}_{y_{j}y_{j}}}h^{\prime}_{y_{j}}$

To write this more compactly, we introduce the vector $r\in\mathbb{R}^{s}$,
where $r_{i}=\tilde{J}_{y_{1}x_{i}}$ if $i\in N_{x}$ and
$r_{i}=\tilde{J}_{y_{1}y_{i}}/\tilde{J}^{\prime}_{y_{i}y_{i}}$ if $i\in
N_{y}$. Notice that $r_{i}\neq 0$ always. With this notation, the previous
equation becomes

$h^{\prime\prime}_{y_{1}}=\sum_{i\neq y_{2}}r_{i}H_{i}$ (53)

We also need to compute $h^{\prime\prime}_{y_{2}}$, which is a much easier
task, since

$h^{\prime\prime}_{y_{2}}=h^{\prime}_{y_{2}}-\tilde{J}_{y_{2}N_{2}}(\tilde{J}^{\prime}_{N_{2}N_{2}})^{-1}h^{\prime}_{N_{2}}=h^{\prime}_{y_{2}}$

since $J_{y_{2}N_{2}}$ is the zero vector (no connections between neighbors).
Hence, we have calculated the external field of $y_{1},y_{2}$ in the marginal
model that contains only these two nodes. Now, to calculate the conditional
expectations of these two nodes, we just have to use the relation

$\begin{pmatrix}\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{1}|x]\\\
\operatorname*{\mathbb{E}}_{\tilde{\mu}}[y_{2}|x]\end{pmatrix}=\tilde{\Sigma}_{y_{1}y_{2}|x}\begin{pmatrix}h^{\prime\prime}_{y_{1}}\\\
h^{\prime\prime}_{y_{2}}\end{pmatrix}$

that connects the external field to the mean of a gaussian. Here,
$\tilde{\Sigma}_{y_{1}y_{2}|x}$ is the $2\times 2$ covariance matrix of the
conditional distribution of $y_{1},y_{2}$ given $x$. The reason we have used
$\tilde{\Sigma}_{y_{1}y_{2}|x}$ is that the covariance matrix does not change
when we marginalize some nodes. Suppose

$\tilde{\Sigma}_{y_{1}y_{2}|x}=\begin{pmatrix}c_{1}&c_{2}\\\
c_{3}&c_{4}\end{pmatrix}$

with $c_{1}c_{4}-c_{2}c_{3}\neq 0$. The reason the variances are not
necessarily $1$ is that we are now in the conditional model. Then,
condition(52) translates to the following:

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(c_{1}h^{\prime\prime}_{y_{1}}+c_{2}h^{\prime\prime}_{y_{2}})(c_{3}h^{\prime\prime}_{y_{1}}+c_{4}h_{y_{2}})]=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[(c_{1}h^{\prime\prime}_{y_{1}}+c_{2}h^{\prime\prime}_{y_{2}})(c_{3}h^{\prime\prime}_{y_{1}}+c_{4}h_{y_{2}})]$

This implies that

$\displaystyle
c_{1}c_{3}(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(h^{\prime\prime}_{y_{1}})^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[(h^{\prime\prime}_{y_{1}})^{2}])+c_{2}c_{4}(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(h^{\prime\prime}_{y_{2}})^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[(h^{\prime\prime}_{y_{2}})^{2}])$
$\displaystyle+(c_{1}c_{4}+c_{2}c_{3})(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h^{\prime\prime}_{y_{1}}h^{\prime\prime}_{y_{2}}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h^{\prime\prime}_{y_{1}}h^{\prime\prime}_{y_{2}}])=0$
(54)

Similarly, from the variance condition on $y_{1}$ (Equations G) we obtain

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(c_{1}h^{\prime\prime}_{y_{1}}+c_{2}h^{\prime\prime}_{y_{2}})^{2}]=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[(c_{1}h^{\prime\prime}_{y_{1}}+c_{2}h^{\prime\prime}_{y_{2}})^{2}]$

This implies

$\displaystyle
c_{1}^{2}(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(h^{\prime\prime}_{y_{1}})^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[(h^{\prime\prime}_{y_{1}})^{2}])+c^{2}(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(h^{\prime\prime}_{y_{2}})^{2}]$
$\displaystyle-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[(h^{\prime\prime}_{y_{2}})^{2}])+2c_{1}c_{2}(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h^{\prime\prime}_{y_{1}}h^{\prime\prime}_{y_{2}}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h^{\prime\prime}_{y_{1}}h^{\prime\prime}_{y_{2}}])=0$
(55)

Similarly, for $y_{2}$ we get

$\displaystyle
c_{3}^{2}\left(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h_{1}^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h_{1}^{2}]\right)+c_{4}^{2}\left(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h_{2}^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h_{2}^{2}]\right)$
$\displaystyle+2c_{3}c_{4}\left(\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h_{1}h_{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h_{1}h_{2}]\right)=0$
(56)

We can think of equations (G), (G) and (G) as a $3\times 3$ system with matrix

$\begin{pmatrix}c_{1}c_{3}&c_{2}c_{4}&c_{1}c_{4}+c_{2}c_{3}\\\
c_{1}^{2}&c^{2}&2c_{1}c_{2}\\\ c_{3}^{2}&c_{4}^{2}&2c_{3}c_{4}\end{pmatrix}$

where the three unknown variables are

$\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h_{1}^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h_{1}^{2}],\
\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h_{2}^{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h_{2}^{2}],\
\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h_{1}h_{2}]-\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h_{1}h_{2}]$

The determinant of this matrix is $-(c_{1}c_{4}-c_{2}c_{3})^{3}$, which is
non-zero, since the matrix $\Sigma_{y_{1}y_{2}|x}$ is invertible. The reason
is that we have assumed that in the fixpoint $\tilde{\rho}$ all correlations
are strictly less than $1$. Hence, we conclude that

$\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[h^{\prime\prime}_{y_{1}}h^{\prime\prime}_{y_{2}}]=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[h^{\prime\prime}_{y_{1}}h^{\prime\prime}_{y_{2}}]$

Based on the calculations that were done earlier (equation (53)), this
equation can be written as

$\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\left[H_{y_{2}}\left(\sum_{i\neq
y_{2}}r_{i}H_{i}\right)\right]=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}\left[H_{y_{2}}\left(\sum_{i\neq
y_{2}}r_{i}H_{i}\right)\right]$

If $x_{j}$ is a non-leaf neighbor, the fixed point equations give us

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[x_{j}(\sum_{i\neq
j}r_{i}H_{i})]=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[x_{j}(\sum_{i\neq
j}r_{i}H_{i})]\implies$
$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[H_{j}(\sum_{i\neq
j}r_{i}H_{i})]=\operatorname*{\mathbb{E}}_{x\sim\tilde{\mu}}[H_{j}(\sum_{i\neq
j}r_{i}H_{i})]$

The key observation here is that the coefficients $r_{i}$ that appear will be
the same in all equations involving $y_{1}$. The last step of the argument
involves actually computing the expectation and seeing what it implies for
$\mu^{*,f}$. First, let’s try to compute
$\operatorname*{\mathbb{E}}[H_{i}H_{j}]$ for $y_{i},y_{j}\in N_{y}$. Remember
that we have established already that for each $i\in N$, $H_{i}$ is a linear
combination of the leaves in the partition corresponding to $i$. Hence,
computing $\operatorname*{\mathbb{E}}[H_{i}H_{j}]$ amounts to computing the
covariance between all pairs of leaves from the two different subsets. Suppose
$H_{i}=(a^{i})^{\top}X_{i}$, where $X_{i}$ is the vector of leaves in $S_{i}$.
As we said, correlations multiply across paths, so in particular we have that

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[H_{i}H_{j}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[(a^{i})^{\top}X_{i}(a^{j})^{\top}X_{j}]=\sum_{x_{k}\in
S_{i},x_{l}\in
S_{j}}a^{i}_{k}a^{j}_{l}\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[x^{i}_{k}x^{j}_{l}]$
$\displaystyle=\sum_{x_{k}\in S_{i},x_{l}\in
S_{j}}a^{i}_{k}a^{j}_{l}\prod_{e\in P_{x_{k},x_{l}}}\theta^{*}_{e}$

where $P(x_{k},x_{l})$ denotes the path between leaves $x_{k},x_{l}$. Now,
notice that all the paths from $X_{i}$ to $X_{j}$ will have to go through the
edges connecting $y_{1}$ to $i$ and $y_{1}$ to $j$. Let
$\rho^{*}_{i},\rho^{*}_{j}$ be the correlations in these two edges. Then,
there is a convenient factorization that can be written as follows

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}[H_{i}H_{j}]=\rho^{*}_{i}\rho^{*}_{j}\left(\sum_{x_{k}\in
S_{i}}a^{i}_{k}\prod_{e\in
P_{x_{k},y_{i}}}\rho^{*}_{e}\right)\left(\sum_{x_{l}\in
S_{j}}a^{j}_{l}\prod_{e\in P_{x_{l},y_{j}}}\rho^{*}_{e}\right)$

The exact same relations hold for $\tilde{\rho}$, since the topology is the
same. Hence, by writing out the condition

$\displaystyle\rho^{*}_{i}\left(\sum_{x_{r}\in S_{i}}a^{i}_{r}\prod_{e\in
P_{x_{r}y_{i}}}\rho^{*}_{e}\right)\sum_{z_{j}\in N,j\neq
i}\rho^{*}_{j}\left(\sum_{x_{s}\in S_{j}}a^{j}_{s}\prod_{e\in
P_{x_{s}z_{j}}}\rho^{*}_{e}\right)$
$\displaystyle=\tilde{\rho}_{i}\left(\sum_{x_{r}\in S_{i}}a^{i}_{r}\prod_{e\in
P_{x_{r}y_{i}}}\tilde{\rho}_{e}\right)\sum_{z_{j}\in N,j\neq
i}\tilde{\rho}_{j}\left(\sum_{x_{s}\in S_{j}}a^{j}_{s}\prod_{e\in
P_{x_{s}z_{j}}}\tilde{\rho}_{e}\right)$ (57)

The reason we used the notation $z_{j}$ is that this neighbor could be either
a leaf or an internal node. Hence, for each $i\in N_{y}$ we set

$w_{i}^{*}=\rho^{*}_{i}\left(\sum_{r\in X^{i}}a^{i}_{r}\prod_{e\in
P_{ri}}\rho^{*}_{e}\right)$

and similarly

$\tilde{w}_{i}=\tilde{\rho}_{i}\left(\sum_{r\in X^{i}}a^{i}_{r}\prod_{e\in
P_{ri}}\tilde{\rho}_{e}\right).$

Notice that if $i$ or $j$ is a leaf neighbor, then we get the same expression,
except that the parenthesis will be $1$ and we will simply have $\rho^{*}_{i}$
or $\rho^{*}_{j}$ as the variable. Hence, this definition can be extended to
all $i\in N$. Now, given these parametrizations, the fixed point conditions
are

$r_{j}w_{j}^{*}\left(\sum_{i\neq
j}r_{i}w_{i}^{*}\right)=r_{j}\tilde{w}_{j}\left(\sum_{i\neq
j}r_{i}\tilde{w}_{i}\right)$ (58)

for each $i\in N$. But this is exactly the system that we got for one latent..
As we proved in Lemma 7, the only solution for this system is
$r_{i}\tilde{w}_{i}=r_{i}w_{i}^{*}$ for each $i$, which implies that
$\tilde{w}_{i}=w_{i}^{*}$ for each $i$. Notice that if $N_{x}$ is nonempty,
then this implies that $\rho^{*}_{e}=\tilde{\rho}_{e}$ for all edges $e$
between $y_{1}$ and it’s neighboring leaves.

We can use this result to show that $\tilde{\rho}=\rho^{*}$. Our argument is
inductive. At each step, we pick an internal node $y$ that only has one non-
leaf neighbor (it’s parent). Then, for all edges of the form $e=(y,x_{i})$ for
some $x_{i}$, we have that $\rho_{e}^{*}=\tilde{\rho}_{e}$ by the previous
argument. Once we establish that, we remove all the leaf nodes that are
connected to $y$ from the tree along with their corresponding edges. This
means that in the next iteration, $y$ will be a leaf, so it will no longer be
selected. This means that this process terminates after $m$ steps.

The correctness of this procedure can be proven inductively as follows: for
the base case, we already saw that edges that are connected to leaves will be
equal in the two models. In each step, for the node $y$ that is selected at
that step, we know from the induction hypothesis that all of it’s leaves in
the remaining tree are either true leaves, or internal nodes who have already
been selected. This means that are descendants of $y$ have already been proven
to be equal in the two models. Then, for each leaf neighbor $z$ of the node
$y$ (it might not be a true leaf in the original tree) we have parameters
$w^{*},\tilde{w}$. These are proven to be equal by the previous arguments. Let
$e$ be the edge connecting $z,y$. Then $w^{*}$ is a multiple of $\rho_{e}^{*}$
and $\tilde{w}$ is a multiple of $\tilde{\rho}_{e}$. The multiplier for both
of these is the same in both quantities, since it only depends on descendant
edges, which are proven to be equal for the two models. It follows that
$\rho^{*}_{e}=\tilde{\rho}_{e}$ and the induction stpe is complete.

∎