# EM’s Convergence in Gaussian Latent Tree Models

Yuval Dagan
MIT, EECS
<EMAIL_ADDRESS>Constantinos Daskalakis
MIT, EECS
<EMAIL_ADDRESS>Anthimos Vardis Kandiros
MIT, EECS
<EMAIL_ADDRESS>
###### Abstract

We study the optimization landscape of the log-likelihood function and the
convergence of the Expectation-Maximization (EM) algorithm in latent Gaussian
tree models, i.e. tree-structured Gaussian graphical models whose leaf nodes
are observable and non-leaf nodes are unobservable. We show that the unique
non-trivial stationary point of the population log-likelihood is its global
maximum, and establish that the expectation-maximization algorithm is
guaranteed to converge to it in the single latent variable case. Our results
for the landscape of the log-likelihood function in general latent tree models
provide support for the extensive practical use of maximum likelihood based-
methods in this setting. Our results for the EM algorithm extend an emerging
line of work on obtaining global convergence guarantees for this celebrated
algorithm. We show our results for the non-trivial stationary points of the
log-likelihood by arguing that a certain system of polynomial equations
obtained from the EM updates has a unique non-trivial solution. The global
convergence of the EM algorithm follows by arguing that all trivial fixed
points are higher-order saddle points.

##  1 Introduction

Estimating latent variable models is a widely-studied task in Statistics and
Machine Learning. It is also a daunting one, computationally and
statistically. Even if the underlying, fully observable distribution is an
exponential family and therefore has a concave log-likelihood function,
marginalizing out the latent variables makes the log-likelihood non-concave,
in most cases. In the same exponential-family setting, under mild conditions,
the population (i.e. infinite sample) log-likelihood of the complete model has
a unique maximum at the true model parameters, yet even in this setting very
little is understood about the landscape of the partially observable model’s
log-likelihood or its stationary points.

A widely-applicable method for estimating latent variable models is the
Expectation-Maximization (EM) algorithm of [9]. Given a parametric family of
distributions
$\\{p_{\boldsymbol{\theta}}(\boldsymbol{X},\boldsymbol{Y})\\}_{\boldsymbol{\theta}\in\Theta}$,
where variables $\boldsymbol{X}$ are observable and variables $\boldsymbol{Y}$
are unobservable, and given independent observations
$\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots$ from some model in this family,
the EM algorithm starts with some initialization $\boldsymbol{\theta}^{(0)}$
and iteratively performs a sequence of interleaved “E-steps” and “M-steps,” a
consecutive pair of which are called an “EM update.” Specifically, for all
$t\geq 0$, the algorithm updates the current vector of parameters
$\boldsymbol{\theta}^{(t)}$ by performing the following:

  * •

(E-step) for each sample $i$, compute a posterior belief about the values of
the unobservable variables by setting, for all $\boldsymbol{y}$,
$Q_{i}^{(t)}(\boldsymbol{y})=p_{\boldsymbol{\theta}^{(t)}}(\boldsymbol{Y}=\boldsymbol{y}|\boldsymbol{X}=\boldsymbol{x}_{i})$;

  * •

(M-step) update the parameters to
$\boldsymbol{\theta}^{(t+1)}\in\arg\max_{\boldsymbol{\theta}}\sum_{i}\int_{\boldsymbol{y}}Q_{i}^{(t)}(\boldsymbol{y})\log{p_{\boldsymbol{\theta}}(\boldsymbol{X}=\boldsymbol{x}_{i},\boldsymbol{Y}=\boldsymbol{y})\over
Q_{i}^{(t)}(\boldsymbol{y})}d\boldsymbol{y}.$

Notice that, by Jensen’s inequality, the function maximized in the M-step of
the algorithm lower bounds the log-likelihood of the samples and, by the
choice made in the E-step of the algorithm, this lower bound equals the log-
likelihood of the samples at $\boldsymbol{\theta}=\boldsymbol{\theta}^{(t)}$.
Thus, whenever the EM update results in
$\boldsymbol{\theta}^{(t+1)}\neq\boldsymbol{\theta}^{(t)}$, the likelihood of
the samples increases. Moreover, when the class of models
$\\{p_{\boldsymbol{\theta}}\\}_{\boldsymbol{\theta}\in\Theta}$ is an
exponential family, the M-step becomes a concave maximization problem, making
the algorithm quite attractive in this setting.

Despite its wide use and study, with north of 66k citations, relatively little
is known about EM’s behavior. Conditions have been identified under which the
EM iterates converge to or cluster at stationary points of the log-likelihood
— see e.g. [35, 32, 5], or exhibit _local_ convergence to the maximum of the
likelihood — see e.g. [23, 1, 39, 18]. Conditions under which EM exhibits
_global_ convergence to the maximum of the likelihood are rare [35] with a
surge of recent results inching towards establishing global convergence
guarantees in more and more settings — from balanced mixtures of two Gaussians
[36, 8] to balanced mixtures of two truncated Gaussians [22], balanced
mixtures of two Laplace distributions [2], unbalanced mixtures of two
Gaussians [37], binary variable naive Bayes models [7], and mixtures of linear
regression models [20, 16, 17, 19] — and towards understanding the role of
overparametrization in EM’s global convergence [37, 10].

To the best of our knowledge, recent works on the global convergence of EM are
for single-latent-variable models. Extending this recent line of work, our
paper studies the convergence of EM in Latent Gaussian Tree Models (LGTMs),
i.e. tree-structured Gaussian Graphical Models whose leaf variables are
observable and non-leaf variables are unobservable. Latent tree models in
general, and LGTMs in particular have found wide use in scientific and applied
domains due to their combined expressiveness and tractability of inference;
see e.g. [21, 40] for recent surveys. Some notable applications of LGTMs are
in phylogenetics, where they have been used to model the evolution of
continuous traits [14, 15, 31], in network tomography, to model network delays
[4, 12, 3], and in linguistics, for modelling the evolution of languages using
acoustic data [24, 29].

Given observations from a latent tree model, a long line of research has
studied whether the structure of the model can be recovered and, if the
structure is known, whether the parameters of the model can be recovered. Most
techniques with provable guarantees are based on defining and estimating tree
metrics from the samples; see e.g. [11, 13, 6, 25, 26, 27] and their
references. On the practical front, however, some of the most popular packages
are based on maximum likelihood estimation; see e.g. [38, 30]. Even when the
latent structure is known, however, the landscape of the likelihood function
is not well understood [14, 31]. This is true even in the population limit,
i.e. when infinitely many samples are available, even when the tree is
trivial, i.e. there is a single latent node, and even when the latent tree
model is a LGTM. For this paradigmatic and widely used family of models we
study the following question:

Main Question: Given a LGTM model
$p_{\boldsymbol{\theta^{*}}}(\boldsymbol{X},\boldsymbol{Y})$ on a tree $T$
whose leaves $\boldsymbol{X}$ are observable and internal nodes
$\boldsymbol{Y}$ are unobservable, can we characterize the stationary points
of the population log likelihood
$\ell_{\boldsymbol{\theta}^{*}}(\boldsymbol{\theta})\equiv\mathbb{E}_{\boldsymbol{x}\sim
p_{\boldsymbol{\theta^{*}}}(\boldsymbol{X})}[\log
p_{\boldsymbol{\theta}}(\boldsymbol{X}=\boldsymbol{x})]$? Does it have
spurious stationary points $\boldsymbol{\theta}\neq\boldsymbol{\theta^{*}}$
and under what conditions does EM converge to $\boldsymbol{\theta^{*}}$?

We study the afore-described questions in the setting where all the nodes of
$T$ are single-dimensional Gaussian variables and assume, without loss of
generality, that they have zero mean and that the setting is ferromagnetic,
i.e. assume that for every pair of variables their correlation lies in
$(0,1)$. Our first main result is the following (the formal version is Theorem
3, combined with Lemma 11):

######  Informal Theorem 1.

In the setting of our main question, and that of the preceding paragraph,
suppose that $\boldsymbol{\theta}$ is a stationary point of the population
log-likelihood $\ell_{\boldsymbol{\theta}^{*}}(\cdot)$ that is non-trivial,
i.e. in model $p_{\boldsymbol{\theta}}(\boldsymbol{X},\boldsymbol{Y})$ there
is no edge of the tree whose endpoints have correlation in $\\{0,1\\}$. Then
$\boldsymbol{\theta}=\boldsymbol{\theta}^{*}$.

Our result guarantees that, if gradient-descent, EM, or similar method
converges to a stationary point of the population log-likelihood that is non-
trivial, then this point indexes the true model. While there are other
criteria that can be used, our result implies that the stationarity of the
log-likelihood can be used as an alternative, post-hoc criterion to argue that
the correct model has been identified. In particular, our result substantiates
the extensive use of maximum-likelihood-based methods in practice [38, 30],
and the experimental evidence that EM succeeds with high probability in this
setting [34]. Next, we study whether we can guarantee that EM converges to a
non-trivial stationary point in our setting. We show this for the case where
there is a single latent node in the model (the formal statement is Theorem
1):

######  Informal Theorem 2.

In the setting Informal Theorem 1, suppose additionally that there is a single
latent node. In this case, EM is guaranteed to converge to
$\boldsymbol{\theta}^{*}$. If $n$ is the number of leaves and $\epsilon$ is
the desired accuracy for all the parameters (in absolute value), then the
sample complexity is $O(\mathrm{poly}(n)/\epsilon^{2})$ and the number of
iterations is $O(\mathrm{poly}(n)\log(1/\epsilon))$.

##### Proof Ideas.

Starting with Informal Theorem 2, it is known that EM converges to some
$\boldsymbol{\theta}$ that is a fixed point of the EM update. Hence, the proof
follows by making the following arguments: (1) ${\boldsymbol{\theta}}^{*}$ is
the only non-trivial fixed point of the EM update; if we parametrize the model
via correlations on its edges this the same as saying that
${\boldsymbol{\theta}}^{*}$ is the only fixed point of the EM update in the
interior of the parameter space $\Theta$; and (2) While there are fixed points
at the boundary of $\Theta$, EM does not converge to any of those. To show
(1), we analyze the EM update and show that its fixed points are solutions to
a system of degree-2 polynomial equations. By using a simple special form of
the Jacobian Conjecture we argue that these have a unique non-trivial
solution. To show (2), we analyze the behavior of the EM around the fixed
points at the boundary, by computing the derivatives of the update rule around
these points. This requires careful analysis since these fixed points are
higher-order saddle points. For the case of general trees (Informal Theorem
1), we show that the fixed points are solutions of higher-degree polynomial
equations. We establish a novel reduction of these algebraic equations to the
second-degree polynomial system from the single-latent-model case, and use
this reduction to certify that there is a unique fixed point at the interior
of the parameter space, which is ${\boldsymbol{\theta}}^{*}$.

##  2 Tree models with one latent node

We start by elaborating on the simpler setting with one latent node. For
simplicity, we start by anayzing the _population EM_ , which amounts to
running the EM algorithm on the whole population (rather than a finite
sample). So simplify even more, we analyze asymptotic convergence, namely, in
the limit as the number of iterations goes to infinity. Later, in Section 2.6,
we describe the finite-sample and finite-iterate result.

###  2.1 Definitions and properties of the model

We consider the family of multivariate Gaussian distributions over zero-mean
variables, with latent node $y$ and observed nodes $x_{1},\dots,x_{n}$, that
have the property

$\Pr[x_{1},\dots,x_{n},y]=\Pr[y]\prod_{i=1}^{n}\Pr[x_{i}\mid y]\enspace.$

Each such distribution is uniquely defined by the following parameters:

$\sigma_{y}^{2}:=\operatorname{Var}(y);\
\sigma_{x_{i}}^{2}:=\operatorname{Var}[x_{i}];\
\rho_{i}:=\frac{\operatorname{Cov}(x_{i},y)}{\sqrt{\operatorname{Var}(x_{i})\operatorname{Var}(y)}},\
\text{for }i=1,\dots,n\enspace,$

We note that generally $\rho_{i}\in[-1,1]$, yet, we analyze the ferromagnetic
setting where $\rho_{i}\in[0,1]$. Denote by $\mathcal{P}$ the set of all such
distributions with $\rho_{i}\in[0,1]$ and $\sigma_{y},\sigma_{x_{i}}>0$. We
use the following convenient properties of distributions in $\mathcal{P}$:

######  Claim 1.

For any $i\neq j$,
$\operatorname{Cov}(x_{i},x_{j})=\sigma_{x_{i}}\sigma_{x_{j}}\rho_{i}\rho_{j}$.
Further, $\operatorname*{\mathbb{E}}[x_{i}\mid
y]=\frac{\sigma_{x_{i}}\rho_{i}}{\sigma_{y}}y$ and

$\operatorname*{\mathbb{E}}[y\mid x_{1}\cdots
x_{n}]=\sigma_{y}\sum_{i=1}^{n}\lambda_{i}\frac{x_{i}}{\sigma_{i}},\quad\text{where
}\lambda_{i}=\frac{\rho_{i}/(1-\rho_{i}^{2})}{1+\sum_{j=1}^{n}\rho_{j}^{2}/(1-\rho_{j}^{2})}\enspace.$
(1)

Given any distribution $\mu\in\mathcal{P}$, denote its marginals and
conditionals as $\mu_{x_{1}\cdots x_{n}}$, $\mu_{y\mid x_{1}\cdots x_{n}}$
etc. Lastly, denote $\overline{\rho}=(\rho_{1},\dots,\rho_{n})$ and
$\overline{x}=(x_{1},\dots,x_{n})$.

###  2.2 The expectation-maximization algorithm - over the population

We analyze the EM algorithm. We start by analyzing the _population EM_ : this
assumes that each iteration of the EM is executed over the _whole population_
, rather than over a finite sample. This greatly simplifies the analysis (see
Section 2.6 for the results on finite sample). The population EM can be
described as follows: we set $\mu^{0}\in\mathcal{P}$ arbitrarily. Then, at any
$t>0$, define

$\mu^{t+1}=\operatorname*{argmax}_{\mu\in\mathcal{P}}\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)],$

where $\Pr_{\mu}$ denotes the density with respect to $\mu$. Denote by
$\sigma_{\cdot}^{t},\rho_{i}^{t}$ the parameters corresponding to $\mu^{t}$
and by $\lambda_{i}^{t}$ the coefficients from (1). Similarly,
$\sigma_{\cdot}^{*},\rho_{i}^{*}$ and $\lambda_{i}^{*}$ correspond to
$\mu^{*}$. We would like to understand how these parameters update in each
iteration of the EM algorithm. For this purpose, we have the following lemma:

######  Lemma 1.

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

$\Pr_{\mu^{t,*}}[x_{1},\cdots,x_{n},y]=\Pr_{\mu^{*}}[x_{1},\cdots,x_{n}]\Pr_{\mu^{t}}[y\mid
x_{1},\dots,x_{n}].$

Then, for any $i$, we have that

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

###### Proof.

Notice that $\mu^{t+1}$ is the MLE over $\mathcal{P}$, given samples drawn
from $\mu^{t,*}$. Hence, for any $\mu\in\mathcal{P}$,

$\displaystyle\operatorname*{\mathbb{E}}_{\overline{x},y\sim\mu^{t,*}}\log\Pr_{\mu}(\overline{x},y)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\overline{x},y\sim\mu^{t,*}}\log\Pr_{\mu}(y)\prod_{i}\Pr_{\mu}(x_{i}\mid
y)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\overline{x},y\sim\mu^{t,*}}\log\Pr_{\mu}(y)+\sum_{i}\operatorname*{\mathbb{E}}_{\overline{x},y\sim\mu^{t,*}}\log\Pr_{\mu}(x_{i}\mid
y).$ (2)

Recall that each $\mu\in\mathcal{P}$ can be decomposed as
$\Pr_{\mu}[x,y]=\Pr_{\mu_{y}}[y]\prod_{i}\Pr_{\mu_{x_{i}\mid y}}[x_{i}\mid
y]$, and each term in this decomposition can be chosen to maximize its
corresponding summand from (2). By Gibbs inequality111Gibb’s inequality states
that for any distribution $P$,
$\operatorname*{argmax}_{Q}\operatorname*{\mathbb{E}}_{x\sim
P}\log\Pr_{Q}[x]=P$, where $Q$ is taken over all the probability measures.
This inequality can be similarly applied on conditional distributions., the
maximizing choice is obtained by selecting $\mu_{y}\sim\mu^{t,*}_{y}$ and
$\mu_{x_{i}\mid y}\sim\mu^{t,*}_{x_{i}\mid y}$. This choice satisfies
$\mu_{x_{i}y}\sim\mu_{y}\mu_{x_{i}\mid y}\sim\mu^{t,*}_{y}\mu^{t,*}_{x_{i}\mid
y}\sim\mu^{t,*}_{x_{i},y}$. Hence, the pairwise marginals between $x_{i}$ and
$y$ are conserved, which concludes the proof. ∎

As a corollary, we obtain the following update rules for the parameters
$\sigma^{t}_{y},\sigma^{t}_{i}$ and $\rho^{t}_{i}$, using the analogous
parameters of $\mu^{t,*}$, that are calculated using formulas for the
conditional Gaussian measure (proof appears in Section A.3).

######  Lemma 2.

For any $i\neq j$, denote by
$\Delta^{t}_{ij}=\rho^{*}_{i}\rho^{*}_{j}-\rho_{i}\rho_{j}$. For any $t>0$ and
any $i$, $\sigma^{t}_{i}=\sigma^{*}_{i}$,

$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]=\sigma^{t}_{i}\sigma^{t}_{y}\left(\lambda_{i}^{t}+\sum_{j\neq
i}\rho^{*}_{i}\rho^{*}_{j}\lambda_{j}^{t}\right)=\sigma^{t}_{i}\sigma^{t}_{y}\left(\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}^{t}\lambda_{j}^{t}\right)\enspace,$
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[y^{2}]=(\sigma_{y}^{t+1})^{2}=(\sigma^{t}_{y})^{2}\left(\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}\right)=(\sigma_{y}^{t})^{2}\left(1+\sum_{j\neq
k}\Delta_{ij}^{t}\lambda_{j}^{t}\lambda_{k}^{t}\right)$
$\rho_{i}^{t+1}=\frac{\lambda_{i}^{t}+\sum_{j\neq
i}\lambda_{j}^{t}\rho^{*}_{i}\rho^{*}_{j}}{\sqrt{\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}}}=\frac{\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}\lambda_{j}^{t}}{\sqrt{1+\sum_{j\neq
k}\Delta_{ij}\lambda_{j}^{t}\lambda_{k}^{t}}}\enspace.$ (3)

###  2.3 Asymptotic Convergence of the population EM

We would like to argue that the iterates of the EM converge to $\mu^{*}$,
which is characterized by the parameters $\sigma_{y}^{*},\sigma_{x_{i}}^{*}$
and $\rho_{i}^{*}$ for $i=1,\dots,n$. Yet, notice that one only observes
samples from the marginal $\mu^{*}_{x_{1}\cdots x_{n}}$, which is a function
of only $\sigma_{x_{i}}^{*}$ and $\rho_{i}^{*}$ but not of $\sigma_{y}^{*}$.
Hence, we cannot expect to learn $\sigma_{y}^{*}$. With regard to the other
parameters, we prove:

######  Theorem 1.

Assume that the correlations in the underlying distribution $\mu^{*}$ satisfy
$\rho_{i}^{*}\in(0,1)$ for all $i$ and that the first iterate of the
population EM satisfies $\rho^{0}_{i}\in(0,1)$ for all $i$. Then, the iterates
$\rho^{t}_{i}$ and $\sigma^{t}_{i}$ of the population EM converge to the
parameters of the underlying distribution:

$\lim_{t\to\infty}\rho^{t}_{i}=\rho^{*}_{i},\quad\text{and
}\sigma^{t}_{i}=\sigma^{*}_{i}\text{ for all }i=1,\dots,n\text{ and }t\geq
1\enspace.$

We will stay under the assumptions that $\rho^{*}_{i},\rho^{0}_{i}\in(0,1)$
for all $i$ throughout the proof. Recall that Lemma 2 argues that for any
$t\geq 1$, $\sigma_{x_{i}}^{t}=\sigma_{x_{i}}^{*}$. Hence, it remains to argue
about the convergence of $\rho_{i}^{t}$ to $\rho_{i}^{*}$. We use the
following definition:

######  Definition 1.

A point $\overline{\rho}=(\rho_{1},\dots,\rho_{n})$ is a stationary point of
the EM if $\overline{\rho}^{t}=\overline{\rho}$ implies that
$\overline{\rho}^{t+1}=\overline{\rho}$.

Denote the set of all stationary points by $\mathcal{S}$. The following is
proved in Section A.3:

######  Lemma 3.

The iterates of the population EM converge to some stationary point
$\overline{\rho}\in\mathcal{S}$. Further, for any
$\overline{\rho}\in\mathcal{S}$, if $\overline{\rho}^{t}=\overline{\rho}$ then
for any $i$, $\mu^{t+1}=\mu^{t}$

Since the EM converges only to a stationary point, it is useful to
characterize the set of stationary points, as stated below:

######  Lemma 4.

The set $\mathcal{S}$ of stationary points of the population EM equals

$\mathcal{S}=\\{(\rho^{*}_{1},\dots,\rho^{*}_{n}),(0,\dots,0)\\}\cup\\{\overline{\rho}^{(i)}\colon
i=1,\dots,n\\},\quad\text{where
}\overline{\rho}^{(i)}_{j}=\begin{cases}1&j=i\\\
\rho^{*}_{i}\rho^{*}_{j}&j\neq i\end{cases}\enspace.$

We will rule out the possibility of convergence to any point that is not the
true parameter.

######  Lemma 5.

The correlation parameters of the population EM converge to a point in
$(0,1)$:

$0<\lim_{t\to\infty}\rho^{t}_{i}<1\quad\text{for all }i=1,\dots,n\enspace.$

Combining the two lemmas above, we obtain that $\rho_{i}^{t}$ must converge to
$\rho^{*}_{i}$, which concludes Theorem 1. In Section 2.4 we will prove that
there are no stationary points where $\rho_{i}\in(0,1)$ for all $i$. In
Section A.1 we will prove that the only stationary point with some
$\rho_{i}=0$ is $(0,\dots,0)$, and that the algorithm does not converge to
this point. In Section A.2 we will prove that the only stationary points where
some $\rho_{i}=1$ are $\overline{\rho}^{(i)}$ and that the algorithm does not
converge to these points. In Section B we combine these results to prove
Lemmas 4 and 5. In Section 2.5 we sketch the proofs from Section A.1 and
Section A.2.

###  2.4 No stationary points at the interior

In this section, we will prove that there are no stationary points of the EM
with $\rho_{i}\in(0,1)$ for all $i$, as summarized in the following lemma:

######  Lemma 6.

Let $\overline{\rho}=(\rho_{1},\dots,\rho_{n})\in(0,1)^{n}$. If
$\overline{\rho}\neq\overline{\rho}^{*}$ then $\overline{\rho}$ is not a
stationary point.

Below, fix some stationary point
$\overline{\rho}^{t}=(\rho_{1},\dots,\rho_{n})\in(0,1)^{n}$ and we will prove
that $\overline{\rho}=\overline{\rho}^{*}$. By Lemma 3,
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]=\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]$
for all $i$, and by Lemma 2 this translates to

$\sigma_{x_{t}}^{t}\sigma_{y}^{t}\rho_{i}^{t}=\sigma^{t}_{i}\sigma^{t}_{y}\left(\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}^{t}\lambda_{j}^{t}\right)~{}\Longrightarrow~{}\sum_{j\neq
i}\Delta^{t}_{ij}\lambda_{j}^{t}=0~{}\Longrightarrow~{}\sum_{j\neq
i}\rho^{*}_{i}\rho^{*}_{j}\lambda^{t}_{j}=\sum_{j\neq
i}\rho^{t}_{i}\rho^{t}_{j}\lambda^{t}_{j}\enspace.$

Multiplying by $\lambda^{t}_{i}$ and substitute
$\rho^{t}_{i}\lambda^{t}_{i}=u^{t}_{i}$ and
$\rho^{*}_{j}\lambda^{t}_{j}=u^{*}_{j}$, we obtain

$\forall i=1,\dots,n\colon\quad\sum_{j\neq
i}\rho^{*}_{i}\rho^{*}_{j}\lambda^{t}_{i}\lambda^{t}_{j}=\sum_{j\neq
i}\rho^{t}_{i}\rho^{t}_{j}\lambda^{t}_{i}\lambda^{t}_{j}~{}\Longrightarrow~{}\sum_{j\neq
i}u^{t}_{i}u^{t}_{j}=\sum_{j\neq i}u^{*}_{i}u^{*}_{j}\enspace.$ (4)

By the assumption that $\rho^{t}_{i},\rho^{*}_{i}\in(0,1)$ and by definition
of $\lambda_{i}$ in (1), we have that $\lambda^{t}_{i}>0$, hence
$u^{t}_{i},u^{*}_{i}>0$. We will prove that this set of equations imply that
$\overline{u}^{t}=\overline{u}^{*}$, as summarized below:

######  Lemma 7.

Let $\overline{u},\overline{v}\in(0,\infty)^{n}$, and assume that for all
$i=1,\dots,n$, $\sum_{j\neq i}u_{i}u_{j}=\sum_{j\neq i}v_{i}v_{j}$. Then
$\overline{u}=\overline{v}$.

Lemma 7 will imply that
$\lambda^{t}_{i}\rho^{t}_{i}=\lambda^{t}_{i}\rho^{*}_{i}$ which implies that
$\rho^{t}_{i}=\rho^{*}_{i}$ as required to conclude the proof of Lemma 6.

In the remainder of this section, we prove Lemma 7. For this purpose, we have
the following lemma, which is a special case of the Jacobian Conjecture on the
uniqueness of solutions of polynomial systems. Its special case for degree-2
polynomials was proven by [33]. We state and prove a corollary of this
statement:

######  Lemma 8.

Let $p_{1},\dots,p_{n}\colon\mathbb{R}^{n}\to\mathbb{R}$ a collection of
quadratic polynomials. If there are two distinct vectors, $\overline{u}$ and
$\overline{u}^{\prime}$ such that
$p_{j}(\overline{u})=p_{j}(\overline{u}^{\prime})$ for all $j$, then, the
Jacobian matrix of $\overline{p}$ computed at
$(\overline{u}+\overline{u}^{\prime})/2$,
$J^{\overline{p}}((\overline{u}+\overline{u}^{\prime})/2)$, is singular, where

$J^{\overline{p}}_{i,j}(\overline{v})=\frac{dp_{i}(\overline{v})}{dv_{j}}.$

###### Proof.

Look at the path $\gamma\colon[0,1]\to\mathbb{R}^{n}$ defined by
$\gamma(s)=s\overline{u}+(1-s)\overline{u}^{\prime}$. Then, $p_{i}(\gamma(s))$
is a quadratic polynomial in $s$, that satisfies
$p_{i}(\gamma(0))=p_{i}(\gamma(1))$. Therefore, $1/2$ is a stationary point,
hence

$\displaystyle
0=\frac{d}{ds}p_{i}(\gamma(s))\bigg{|}_{s=1/2}=\sum_{j}\frac{dp_{i}}{dv_{j}}\bigg{|}_{\overline{v}=\gamma(1/2)}\frac{d\gamma_{j}}{ds}\bigg{|}_{s=1/2}=\sum_{j}\frac{dp_{i}}{dv_{j}}\bigg{|}_{\overline{v}=\gamma(1/2)}(u^{\prime}_{j}-u_{j}).$

Combining these equalities in a matrix form for all $i=1,\dots,n$, we derive
that
$0=J^{\overline{p}}(\overline{\gamma}(1/2))(\overline{u}^{\prime}-\overline{u})=J^{\overline{p}}((\overline{u}+\overline{u}^{\prime})/2)(\overline{u}^{\prime}-\overline{u})$
hence $J^{\overline{p}}((\overline{u}+\overline{u}^{\prime})/2)$ is singular.
∎

To complete the proof of Lemma 7, let us substitute
$p_{i}(\overline{u})=\sum_{j\neq i}u_{i}u_{j}$. The following lemma proves
that the Jacobian matrix of this system is non-singular at any point
$\overline{u}$ with positive entries, which suffices to conclude the proof:

######  Lemma 9.

Let $u_{1},\dots,u_{n}>0$. Then the following matrix $J$ is non singular:

$J_{ij}=\begin{cases}\sum_{k\neq i}u_{k}&i=j\\\ u_{i}&i\neq j\end{cases}.$ (5)

Notice that this matrix can be written as $D+\overline{v}\overline{w}^{\top}$,
where $D$ is diagonal and $\overline{v},\overline{w}\in\mathbb{R}^{n}$. Such a
matrix is singular if and only if $1+\overline{v}^{\top}A^{-1}\overline{w}=0$
[28]. Proving that this matrix is non-singular from this formula is not
immediate. For completeness, we present in Section A.3 a proof that does not
rely on this formula. This concludes Lemma 7 and Lemma 6 follows.

###  2.5 The limiting point is bounded away from the boundary

In this section, we sketch the proof that $0<\lim_{t\to\infty}\rho^{t}_{i}<1$,
whose full version appears in Section A.1 and Section A.2. First, by
inspecting the update rule from Lemma 2, it is easy to verify that the only
stationary points with some $\rho_{i}\in\\{0,1\\}$ are
$\overline{0}=(0,\dots,0)$ and $\overline{\rho}^{(i)}$ (defined formally in
Lemma 4). It remains to prove that the EM does not converge to these
stationary points. To argue about $\overline{0}$, we write the Taylor series
of $\rho^{t+1}_{i}$ around $0$ and obtain

$\rho^{t+1}_{i}\geq\rho^{t}_{i}+\sum_{j\neq
i}\rho^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}-O\left(\sum_{j,k}\rho^{t}_{j}\rho^{t}_{k}\right)\geq\rho^{t}_{i}+\Omega\left(\max_{j\neq
i}\rho^{t}_{j}\right)-O\left(\max_{j\in\\{1,\dots,n\\}}(\rho^{t}_{j})^{2}\right)\enspace.$

This can be used to show that whenever $\overline{\rho}^{t}$ approaches
$\overline{0}$, in the subsequent iteration it will repel from $\overline{0}$
and particularly, $\sum_{i}\rho^{t+1}_{i}\geq\sum_{i}\rho^{t}_{i}$. Hence, the
algorithm cannot converge to $\overline{0}$.

Next, we explain why EM does not converge to $\overline{\rho}^{(i)}$. Assume
w.l.o.g that $i=1$ and recall that
$\overline{\rho}^{(1)}=(1,\rho^{*}_{1}\rho^{*}_{2},\dots,\rho^{*}_{1}\rho^{*}_{n})$.
The proof is more involved than the proof at $\overline{0}$, due to (1) one is
required to derive a second-order Taylor series (compared to a first-order
computed around $\overline{0}$), and (2) one would like to argue that if
$\overline{\rho}^{t}\approx\overline{\rho}^{(1)}$ then
$\|\overline{\rho}^{t+1}-\overline{\rho}^{(1)}\|\geq\|\overline{\rho}^{t}-\overline{\rho}^{(1)}\|$
(in some norm). Yet, this is true only for some values of
$\overline{\rho}^{t}$: in particular, this holds whenever
$\max_{i}|\rho^{t}_{i}-\rho^{(1)}_{i}|\leq O(|\rho^{t}_{1}-\rho^{(1)}_{1}|)$.
By analyzing the update step of the EM, it can be shown that even if
$\rho^{t}$ does not satisfy this condition, which might happen with a bad
initialization ($t=0$), $\rho^{t+1}$ will always satisfy it and the proof
follows.

###  2.6 Finite sample and finite iteration

In this section we assume that $m$ draws from the marginal distribution over
the leaves are given, where sample $i$ is denoted by
$(x^{(i)}_{1},\dots,x^{(i)}_{n})$, for $i\in\\{1,\dots,m\\}$. Then, the EM
iterate is defined by

$\mu^{t+1}=\operatorname*{argmax}_{\mu\in\mathcal{P}}\sum_{i=1}^{m}\operatorname*{\mathbb{E}}_{y\sim\mu^{t}_{y\mid
x_{1}^{(i)}\cdots
x_{n}^{(i)}}}\left[\log\Pr_{\mu}\left(x_{1}^{(i)},\dots,x_{n}^{(i)},y\right)\right].$

We have the following theorem, which bounds the sample complexity and the
convergence time of sample-based EM (the proof appears in Section D):

######  Theorem 2.

Let $\alpha,\beta>0$ and assume that $\theta^{0}_{i},\theta^{*}_{i}\geq\alpha$
for all $i$ and $\theta^{0}_{i},\theta^{*}_{i}\leq 1-\beta$ for all $i$. Then,
there exist constants $C_{1}(\alpha,\beta),C_{3}(\alpha,\beta)$ that depend
only on $\alpha$ and $\beta$ and universal constants $C_{2},C_{4}$ such that
the following holds: let $\epsilon,\delta>0$ and assume that the number of
samples $m$ is at least
$m\geq(C_{1}(\alpha,\beta)n^{C_{2}}+\log(1/\delta))/\epsilon^{2}$ and let
$T\geq C_{3}(\alpha,\beta)n^{C_{4}}\log(1/\epsilon)$. Then, with probability
$1-\delta$ over the sample, for any $t\geq T$,
$|\rho^{t}_{i}-\rho^{*}_{i}|\leq\epsilon$ and
$|\sigma^{t}_{i}-\sigma^{*}_{i}|\leq\epsilon$ for all $i\in\\{1,\dots,n\\}$.

##  3 General Tree models

We now extend the analysis for more complicated tree topologies.

###  3.1 Definitions and properties of the model

We consider a multivariate Gaussian latent-tree distribution, that is
characterized by a tree $G=(V,E)$ with $n$ leaves $x_{1},\dots,x_{n}$ (of
degree 1) and $m$ internal nodes $y_{1},\dots,y_{n}$ (of degree at least $2$).
The vertices $u\in V$ corresponds to random variables $\\{z_{u}\colon u\in
V\\}$ with the joint distribution

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

where $z_{x_{i}}$ are observed by the algorithm and $z_{y_{i}}$ are latent
variables. The variables are assumed zero-mean and the distribution is
uniquely characterized by the variance parameters
$\sigma_{u}^{2}:=\operatorname{Var}[Z_{u}]$ for $u\in V$ and the correlation
parameters
$\rho_{uv}:=\operatorname{Cov}[Z_{u}Z_{v}]/\sqrt{\operatorname{Var}(Z_{u})\operatorname{Var}(Z_{v})}$
for each edge $(u,v)\in E$. As with one latent, we assume $\rho_{uv}\in[0,1]$.
The correlation between any two nodes $u,v\in E$ can be expressed as the
product of correlations along the path connecting them,

$\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}},\quad\text{where $P(z_{i},z_{j})$ is the path
connecting $i$ and $j$}.$

Similarly to the argument regarding topologies of one latent node, the
variances of the latent nodes $\sigma_{y_{j}}^{2}$ cannot be estimated (see
Remark 1).

An equivalent way to characterize the distribution is through the exponential
family parametrization $(J=-\Sigma^{-1},h)$, where $\Pr[z_{1}\cdots
z_{n+m}]\propto\exp\left(\sum_{ij}J_{ij}z_{i}z_{j}/2+\sum_{i}h_{i}z_{i}\right).$
Since the distribution factorizes as (6), the only non-zero entries $J_{ij}$
correspond to edges $(i,j)\in E$ and for diagonal elements $i=j$. While in the
original model $h_{i}=0$ since the random variables are zero mean, in the
conditional distribution of $y$ given $x$ this is no longer true and
$h_{y}=-J_{yx}x$.

Lastly, we remark that the parameters are information-theoretically
identifiable only when all the latent nodes have degree at least $3$, yet, any
graph can be modified to to satisfy this property, while retaining the
distribution over observables (see Remark 2).

###  3.2 EM and likelihood for general trees

In this section, we analyze the EM iteration on latent tree models (see
Section 2.2 for an elaborate exposition). Given an initial point
$\mu^{0}\in\mathcal{P}_{G}$, its iteration $\mu^{t}$ is defined as:

$\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_{1},\cdots,y_{m}\sim\mu^{t}_{y\mid
x_{1}\cdots x_{n}}}[\log\Pr_{\mu}(x_{1},\dots,x_{n},y_{1},\dots,y_{m})],$ (7)

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}$. Similarly, $\sigma_{\cdot}^{*},\rho_{i}^{*}$ and $\lambda^{*}$
correspond to $\mu^{*}$. Using the same arguments as in Lemma 1, the following
can be shown:

######  Lemma 10.

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

$\Pr_{\mu^{t,*}}[x_{1},\cdots,x_{n},y_{1},\ldots,y_{m}]=\Pr_{\mu^{*}}[x_{1},\cdots,x_{n}]\Pr_{\mu^{t}}[y_{1},\ldots,y_{m}\mid
x_{1},\ldots,x_{n}].$

Then, for any $u\in V$ and any $(v,w)\in E$,

$\operatorname{Cov}_{\mu^{t+1}}(z_{v},z_{w})=\operatorname{Cov}_{\mu^{t,*}}(z_{v},z_{w}),\
\operatorname{Var}_{\mu^{t,*}}[z_{u}]=\operatorname{Var}_{\mu^{t+1}}[z_{u}]\enspace.$

Denote by $\mathcal{S}$ the set of fixpoints of the EM, namely, the points
$\rho$ such that $\overline{\rho}^{t}=\overline{\rho}$ implies
$\overline{\rho}^{t+1}=\overline{\rho}$. Analogously to Lemma 3, these
correspond to the set of fixpoints $\mu$ of (7). We can equivalently consider
the EM iteration under the natural parametrization $J,h$, as discussed in
Section 3.1. Hence, a fixed point $\tilde{\rho}$ corresponds to some
$\tilde{J}$, meaning that $\mathcal{S}$ remains unchanged if we change
parametrization. The reason we choose the parameter $J$ is that the likelihood
has a more convenient form as an exponential family. The importance of
$\mathcal{S}$ is further exemplified by the following lemma, which states that
the notions of EM fixpoints and stationary points of the log-likelihood are
equivalent. The proof is folklore.

######  Lemma 11.

Let $\mu^{*}\in P_{G}$ be such that $\rho^{*}_{ij}\in(0,1)$ for all $(i,j)\in
E$ and define
$L(J):=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\mu(J)}(x)$. 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 (7).

###  3.3 Uniqueness of EM fixpoints for general trees

In this section, we prove that the only fixpoint of EM with non-degenerate
edge weights is the true model $\mu^{*}$. A detailed proof of all the claims
in this Section is given in Section G.

######  Theorem 3.

Let $G=(V,E)$ be a tree and $\mu^{*}\in P_{G}$ be a distribution with
$\rho^{*}_{ij}\in(0,1)$ for all $(i,j)\in E$. Suppose $\tilde{\rho}$ is a
stationary point of the EM update rule (49) with $\tilde{\rho}_{ij}\in(0,1)$
for all $(i,j)\in E$. Then $\tilde{\rho}_{ij}=\rho^{*}_{ij}$ for all $(i,j)\in
E$.

We will denote by $\mu^{*,t}$ the distribution defined as
$\mu^{*,t}(x,y):=\mu^{*}(x)\tilde{\mu}(y|x)$. We begin by exploring a simple
implication of the fixpoint conditions, according to the rules (7). The proof
follows by noticing that the conditional distribution of $y$ given $x$ is the
same in $\tilde{\mu}$ and $\mu^{*,t}$.

######  Lemma 12.

Let $\mu^{*},\tilde{\mu}$ be the distributions defined in Theorem 3. Then, for
any internal nodes $y_{1},y_{2}$ that are connected by and edge in $G$

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

Hence, all we have to do is compute these conditional expectations in a
suitable way, so as to reveal some structure. Let $N$ be the set of neighbors
of $y_{1}$ in $G$ and assume w.l.o.g. that they are all non-leaf nodes (the
case of leaf neighbors is even easier). The first step will be to marginalize
all the other non-leaf nodes except $y_{1}$ and $y_{2}$. Denote by $Y^{c}$ the
set of non-leaf nodes that are not neighbors of $y_{1}$. Then, let
$h^{\prime}_{y_{1}},h^{\prime}_{y_{2}}$ be the information parameters of
$y_{1},y_{2}$ after the marginalization of $Y^{c}$. Since no neighbor of
$y_{1}$ was marginalized, we will have $h^{\prime}_{y_{1}}=0$. Suppose we
remove the edge $(y_{1},y_{2})$ from the tree. Then the set of leaves is
partitioned into two subsets. Call $S_{y_{2}}$ the subset that is connected to
$y_{2}$ after the removal. We show that $h^{\prime}_{y_{2}}$ is a linear
combination of the values of the leaves in $S_{y_{2}}$. To do that, we utilize
the marginalization formulas for Gaussian distributions, as well as the fact
that $\tilde{J}_{Y^{c}Y^{c}}^{-1}$ can be thought of as a covariance matrix of
some Gaussian tree distribution and hence satisfies the multiplication over
paths property.

######  Lemma 13.

Let $y_{2}$ be a non-leaf neighbor of $y_{1}$ and $S_{y_{2}}$ be the
corresponding set of leaves for the partition that $y_{2}$ belongs to. Then,
the quantity
$h^{\prime}_{y_{2}}=h_{y_{2}}-\tilde{J}_{y_{2}Y^{c}}\tilde{J}_{Y^{c}Y^{c}}^{-1}h_{Y^{c}}$
is a linear combination of the leaves in $S_{y_{2}}$.

A similar result holds for any neighbor $y_{i}$ of $y_{1}$. Our strategy is to
build a system of equations similar to the one in Lemma 7. But in the proof of
one latent, the variables of the system corresponded to the covariances of the
latent node with individual leaves. Here, for neighbor $y_{2}$ we will define
some variable that depends on a linear combination of the paths leading to
leaves in $S_{y_{2}}$. In this direction, let’s define the vector
$H\in\mathbb{R}^{s}$, which has one entry for each node in $N$. We define
$H_{i}=h^{\prime}_{y_{i}}$.

So far we have marginalized on everyone except nodes in $N$. To gain specific
information about the interaction of $y_{1},y_{2}$, we now marginalize also
over the neighbors of $y_{1}$, except $y_{2}$. Denote by $N_{2}$ that set of
neighbors. Let
$h^{\prime\prime}_{y_{1}},h^{\prime\prime}_{y_{2}},\tilde{J}^{\prime\prime}$
be the resulting parametrizations. From standard properties of the Gaussian,
we can compute these as follows

$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}}=\sum_{y_{j}\in
N,y_{j}\neq
y_{2}}\frac{\tilde{J}_{y_{1}y_{j}}}{\tilde{J}^{\prime}_{y_{j}y_{j}}}h^{\prime}_{y_{j}},\
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}}$

This follows by the fact that the matrix $\tilde{J}^{\prime}_{N_{2}N_{2}}$ is
diagonal, since the neighbors of $y_{1}$ are not connected to each other, and
$J_{y_{2}N_{2}}=0$. To write this more compactly, we introduce the vector
$r\in\mathbb{R}^{s}$, where
$r_{i}=\tilde{J}_{y_{1}y_{i}}/\tilde{J}^{\prime}_{y_{i}y_{i}}$ if $i\in N$.
Notice that $r_{i}\neq 0$ always. Hence, this relation becomes

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

We are now close to arriving at the desired form of the polynomial equations.
Since we have marginalized over all nodes except $y_{1},y_{2}$, we can now
determine the conditional expectations by the formula

$\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 two parametrizations in 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, the first
fixpoing condition of Lemma 12 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}})]$

We observe that this relation can be viewed as a linear equation in terms of
the variables
$\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 coefficients of these variables are functions of
$c_{1},c_{2},c_{3},c_{4}$. We can obtain two other such equations from the
other two conditions of Lemma 12. It turns out that this $3\times 3$ system
has a unique solution if and only if $\tilde{\Sigma}_{y_{1}y_{2}|x}$ is
invertible. This is the content of the following Lemma.

######  Lemma 14.

Let $\tilde{\Sigma}_{y_{1}y_{2}|x}$ be invertible. Then the conditions of
Lemma 12 imply 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}}],\
\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}],\
\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}]$

Using the previous calculations for
$h^{\prime\prime}_{y_{1}},h^{\prime\prime}_{y_{2}}$, the first equality of
this Lemma 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]$ (9)

Now we are almost in the algebraic form of Lemma 7. All we need to do is get
rid of the expectations. So, it is time to compute them. Let $i,j\in N$ be two
neighbors. Then, we know that $H_{i},H_{j}$ are linear combinations of leaves
in the partitions of $i,j$. Thus, by the multiplication property
$\operatorname*{\mathbb{E}}[H_{i}H_{j}]$ involves the covariances of all pairs
of leaves from $S_{y_{i}}$ to $S_{y_{j}}$. Suppose that
$H_{i}=(a^{i})^{\top}X_{y_{i}}$, where $X_{y_{i}}$ is the vector of leaves in
$S_{y_{i}}$. By the path multiplication property

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

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

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

In this form, we can define

$w_{i}^{*}=\rho^{*}_{i}\left(\sum_{x_{r}\in S_{y_{i}}}a^{i}_{r}\prod_{e\in
P(x_{r},y_{i})}\rho^{*}_{e}\right),\
\tilde{w}_{i}=\tilde{\rho}_{i}\left(\sum_{x_{r}\in
S_{y_{i}}}a^{i}_{r}\prod_{e\in P(x_{r},y_{i})}\tilde{\rho}_{e}\right).$

Now the condition is

$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)$ (11)

which is exactly in the form of the system of Lemma 7. By applying this Lemma,
we immediately get the following corollary.

######  Lemma 15.

Let $\mu^{*},\tilde{\mu}$ be defined as in Theorem 3. Then for every node $i$,
if we define $S_{y_{i}}$ in reference to some neighbor $y_{1}$, it holds
$w_{i}^{*}=\tilde{w}_{i}$.

If a node $y_{1}$ is connected to a leaf $x_{j}$ with correlation
$\rho_{j}^{*}$, then we can extend all the previous statements and define
$w_{j}^{*}=\rho_{j}^{*},\tilde{w}_{j}=\tilde{\rho}_{j}$. This immediately
implies that $\rho_{j}^{*}=\tilde{\rho}_{j}$. The proof of Theorem 3 relies
exactly on using the equalities implied by Lemma 15 in the correct order, in
order to guarantee that all correlations are the same in the two models.

###### Proof sketch of Theorem 3.

We use the following procedure: in each iteration, we select an internal node
$y$ that only has one non-leaf neighbor in the remaining tree (there is always
one such node). If $e$ is some edge connecting $y$ with some leaf in the tree,
we declare that $\rho_{e}^{*}=\tilde{\rho}_{e}$ and remove this edge along
with the leaf from the tree. After we do this for all such edges, the current
iteration ends.

First of all, it is clear that if a node $y$ is selected for some iteration,
then for the remaining iterations it will be a leaf and not be selected.
Hence, the process terminates after $m$ steps, at which point all edges have
been examined. We prove inductively that at each step the algorithm correctly
infers the equality of the edges. For the base case, we already argued that
edges that are adjacent to leaves will agree in the two models. For some
arbitrary iteration, if $y$ is selected and has a leaf neighbor $x$, then we
use Lemma 15 on $x$ with $y_{1}=y$ to infer that $w_{x}^{*}=\tilde{w}_{x}$.
From the definition of $w$ and the inductive hypothesis, the parentheses
multiplying $\rho_{i}^{*}$ and $\tilde{\rho}_{i}$ are equal in the two models,
which implies that $\rho_{i}^{*}=\tilde{\rho}_{i}$ and the proof is complete.
∎

##  4 Acknowledgements

Constantinos Daskalakis was supported by NSF Awards CCF-1901292, DMS-2022448
and DMS2134108, a Simons Investigator Award, the Simons Collaboration on the
Theory of Algorithmic Fairness, a DSTA grant, and the DOE PhILMs project (DE-
AC05-76RL01830). Vardis Kandiros was supported by a Fellowship of the Eric and
Wendy Schmidt Center at the Broad Institute of MIT and Harvard and by the
Onassis Foundation-Scholarship ID: F ZP 016-1/2019-2020.

## References

  * [1] Sivaraman Balakrishnan, Martin J Wainwright and Bin Yu  “Statistical guarantees for the EM algorithm: From population to sample-based analysis”  In _The Annals of Statistics_ 45.1 Institute of Mathematical Statistics, 2017, pp. 77–120
  * [2] Babak Barazandeh and Meisam Razaviyayn  “On the behavior of the expectation-maximization algorithm for mixture models”  In _2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_ , 2018, pp. 61–65  IEEE
  * [3] Shankar Bhamidi, Ram Rajagopal and Sébastien Roch  “Network delay inference from additive metrics”  In _Random Structures & Algorithms_ 37.2 Wiley Online Library, 2010, pp. 176–203
  * [4] Rui Castro et al.  “Network tomography: Recent developments”  In _Statistical science_ 19.3 Institute of Mathematical Statistics, 2004, pp. 499–517
  * [5] Stéphane Chrétien and Alfred O Hero  “On EM algorithms and their proximal generalizations”  In _ESAIM: Probability and Statistics_ 12, 2008, pp. 308–326
  * [6] Constantinos Daskalakis, Elchanan Mossel and Sébastien Roch  “Optimal phylogenetic reconstruction”  In _Proceedings of the thirty-eighth annual ACM symposium on Theory of computing_ , 2006, pp. 159–168
  * [7] Constantinos Daskalakis, Christos Tzamos and Manolis Zampetakis  “Bootstrapping EM via EM and Convergence Analysis in the Naive Bayes Model”  In _Proceedings of the International Workshop on Artificial Intelligence and Statistics_ , 2018
  * [8] Constantinos Daskalakis, Christos Tzamos and Manolis Zampetakis  “Ten steps of EM suffice for mixtures of two Gaussians”  In _Conference on Learning Theory_ , 2017, pp. 704–710  PMLR
  * [9] Arthur P Dempster, Nan M Laird and Donald B Rubin  “Maximum likelihood from incomplete data via the EM algorithm”  In _Journal of the royal statistical society. Series B (methodological)_ , 1977, pp. 1–38
  * [10] Raaz Dwivedi et al.  “Singularity, misspecification and the convergence rate of EM”  In _The Annals of Statistics_ 48.6 Institute of Mathematical Statistics, 2020, pp. 3161–3182
  * [11] 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 (I)”  In _Random Structures & Algorithms_ 14.2 Wiley Online Library, 1999, pp. 153–184
  * [12] Brian Eriksson, Gautam Dasarathy, Paul Barford and Robert Nowak  “Toward the practical use of network tomography for internet topology discovery”  In _2010 Proceedings IEEE INFOCOM_ , 2010, pp. 1–9  IEEE
  * [13] Joseph Felsenstein  “Inferring phylogenies”  Sinauer associates Sunderland, MA, 2004
  * [14] Joseph Felsenstein  “Maximum-likelihood estimation of evolutionary trees from continuous characters”  In _American journal of human genetics_ 25.5 Elsevier, 1973, pp. 471
  * [15] Gordon Hiscott, Colin Fox, Matthew Parry and David Bryant  “Efficient recycled algorithms for quantitative trait models on phylogenies”  In _Genome biology and evolution_ 8.5 Oxford University Press, 2016, pp. 1338–1350
  * [16] Jason M Klusowski, Dana Yang and WD Brinda  “Estimating the coefficients of a mixture of two linear regressions by expectation maximization”  In _IEEE Transactions on Information Theory_ 65.6 IEEE, 2019, pp. 3515–3524
  * [17] Jeongyeol Kwon and Constantine Caramanis  “EM converges for a mixture of many linear regressions”  In _International Conference on Artificial Intelligence and Statistics_ , 2020, pp. 1727–1736  PMLR
  * [18] Jeongyeol Kwon and Constantine Caramanis  “The EM algorithm gives sample-optimality for learning mixtures of well-separated gaussians”  In _Conference on Learning Theory_ , 2020, pp. 2425–2487  PMLR
  * [19] Jeongyeol Kwon, Nhat Ho and Constantine Caramanis  “On the minimax optimality of the EM algorithm for learning two-component mixed linear regression”  In _International Conference on Artificial Intelligence and Statistics_ , 2021, pp. 1405–1413  PMLR
  * [20] Jeongyeol Kwon et al.  “Global convergence of the EM algorithm for mixtures of two component linear regression”  In _Conference on Learning Theory_ , 2019, pp. 2055–2110  PMLR
  * [21] Raphaël Mourad et al.  “A survey on latent tree models and applications”  In _Journal of Artificial Intelligence Research_ 47, 2013, pp. 157–203
  * [22] Sai Ganesh Nagarajan and Ioannis Panageas  “On the Analysis of EM for truncated mixtures of two Gaussians”  In _Algorithmic Learning Theory_ , 2020, pp. 634–659  PMLR
  * [23] Richard A Redner and Homer F Walker  “Mixture densities, maximum likelihood and the EM algorithm”  In _SIAM review_ 26.2 SIAM, 1984, pp. 195–239
  * [24] Don Ringe, Tandy Warnow and Ann Taylor  “Indo-European and computational cladistics”  In _Transactions of the philological society_ 100.1 Wiley Online Library, 2002, pp. 59–129
  * [25] Sebastien Roch  “A short proof that phylogenetic tree reconstruction by maximum likelihood is hard”  In _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ 3.1 IEEE, 2006, pp. 92–94
  * [26] Sebastien Roch  “Toward extracting all phylogenetic information from matrices of evolutionary distances”  In _Science_ 327.5971 American Association for the Advancement of Science, 2010, pp. 1376–1379
  * [27] Sebastien Roch and Allan Sly  “Phase transition in the sample complexity of likelihood-based phylogeny inference”  In _Probability Theory and Related Fields_ 169.1 Springer, 2017, pp. 3–62
  * [28] Jack Sherman and Winifred J Morrison  “Adjustment of an inverse matrix corresponding to a change in one element of a given matrix”  In _The Annals of Mathematical Statistics_ 21.1 JSTOR, 1950, pp. 124–127
  * [29] Nathaniel Shiers, John AD Aston, Jim Q Smith and John S Coleman  “Gaussian tree constraints applied to acoustic linguistic functional data”  In _Journal of Multivariate Analysis_ 154 Elsevier, 2017, pp. 199–215
  * [30] Alexandros Stamatakis  “RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models”  In _Bioinformatics_ 22.21 Oxford University Press, 2006, pp. 2688–2690
  * [31] Michael Truell et al.  “Maximum Likelihood Estimation for Brownian Motion Tree Models Based on One Sample”  In _arXiv preprint arXiv:2112.00816_ , 2021
  * [32] Paul Tseng  “An analysis of the EM algorithm and entropy-like proximal point methods”  In _Mathematics of Operations Research_ 29.1, 2004, pp. 27–44
  * [33] Stuart Sui-Sheng Wang  “A Jacobian criterion for separability”  In _Journal of Algebra_ 65.2 Elsevier, 1980, pp. 453–494
  * [34] Yi Wang and Nevin Lianwen Zhang  “Severity of Local Maxima for the EM Algorithm: Experiences with Hierarchical Latent Class Models.”  In _Probabilistic Graphical Models_ , 2006, pp. 301–308  Citeseer
  * [35] CF Jeff Wu  “On the convergence properties of the EM algorithm”  In _The Annals of statistics_ , 1983, pp. 95–103
  * [36] Ji Xu, Daniel Hsu and Arian Maleki  “Global analysis of Expectation Maximization for mixtures of two Gaussians”  In _the 30th Annual Conference on Neural Information Processing Systems (NIPS)_ , 2016
  * [37] Ji Xu, Daniel J Hsu and Arian Maleki  “Benefits of over-parameterization with EM”  In _Advances in Neural Information Processing Systems_ 31, 2018
  * [38] Ziheng Yang  “PAML: a program package for phylogenetic analysis by maximum likelihood”  In _Computer applications in the biosciences_ 13.5 Citeseer, 1997, pp. 555–556
  * [39] Ruofei Zhao, Yuanzhi Li and Yuekai Sun  “Statistical convergence of the EM algorithm on Gaussian mixture models”  In _Electronic Journal of Statistics_ 14.1 Institute of Mathematical StatisticsBernoulli Society, 2020, pp. 632–660
  * [40] Piotr Zwiernik  “Latent tree models”  In _Handbook of Graphical Models_ CRC Press, 2018, pp. 283–306

##  Appendix A Deferred proofs for one latent node

We structure this Section as follows. In Section A.1 we prove that the only
stationary point of EM with a zero coordinate is the all zeroes vector and EM
never converges to it. In Section A.2 we prove that EM will not coverge to any
stationary point where some $\rho_{i}=1$. The main technical result in that
section is Theorem 4. In Section A.3 we collect the proofs of some Lemmas of
the main text, including Lemma 9, which implies Lemma 6. Finally, in Section B
we prove Lemmas 4 and 5, which combined with Lemma 3 imply Theorem 1.

###  A.1 The EM does not converge to $0$

In this section, we will prove the following two lemmas:

######  Lemma 16.

The point $\overline{0}=(0,\dots,0)$ is a stationary point and there is no
other stationary point $\overline{\rho}$ with some $\rho_{i}=0$.

######  Lemma 17.

The iterate of the EM algorithm satisfies
$\lim_{t\to\infty}\overline{\rho}^{t}\neq\overline{0}$.

First, we notice that the point $\overline{0}=(0,\dots,0)$ is a stationary
point. Indeed, by (1), $\overline{\rho}^{t}=(0,\dots,0)$ then
$\lambda^{t}_{i}=0$. Together with, Lemma 2, this implies that
$\overline{\rho}^{t+1}=(0,\dots,0)$ which concludes that $\overline{0}$ is a
stationary point. The following concludes the proof of Lemma 16:

######  Lemma 18.

If $\rho^{t}_{i_{1}}>0$ for some $i_{1}>0$ then, $\rho^{t+1}_{i}>0$ for all
$i$. Consequently, if $\overline{\rho}$ satisfies $\rho_{i_{0}}=0$ and
$\rho_{i_{1}}>0$ for some $i_{0}$ and $i_{1}$, then $\rho$ is not a stationary
point.

###### Proof.

We start with the first part of the proof. Recall the update rule for the
covariances, from Lemma 2:

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

Further, from (1), we know that $\lambda^{t}_{i}>0$ whenever $\rho^{t}_{i}>0$.
In particular, $\lambda^{t}_{i_{1}}>0$, which implies that for all $i$,
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]\geq\sigma_{x_{i}}^{t}\sigma_{y}^{t}\rho^{*}_{i}\rho^{*}_{i_{1}}\lambda^{t}_{i_{1}}>0$.
This concludes the first part of the proof. For the second part, notice that
if $\mu^{t}=\mu$ then, by the first part,
$\rho^{t+1}_{i_{0}}>0=\rho^{t}_{i_{0}}$, hence $\mu$ cannot be a stationary
point. ∎

The first part of the lemma follows from the update rule analyzed in Lemma 2,
while the second part follows directly from the first part and the definition
of a stationary point. This concludes Lemma 16.

For the remainder, we prove Lemma 17. The first part of Lemma 18 implies that
if $\overline{\rho}^{0}\neq\overline{0}$ then
$\overline{\rho}^{t}\neq\overline{0}$ for all $t>0$. It remains to prove that
$\overline{\rho}^{t}$ does not converge to $\overline{0}$ and we will analyze
the updates of the EM rule in the neighborhood of
$\overline{\rho}^{t}=\overline{0}$, viewing $\overline{\rho}^{t+1}$ as a
function of $\overline{\rho}^{t}$.

######  Lemma 19.

If $\overline{\rho}^{t}=\overline{0}$ then
$\overline{\rho}^{t+1}=\overline{0}$. Further, there exists $C>0$ such that
for all $i,j,k\in\\{1,\dots,n\\}$ and all $\overline{\rho}\in[0,1/2]^{n}$,

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

###### Proof.

We use the formula for $\overline{\rho}^{t+1}$ from Lemma 2:

$\rho_{i}^{t+1}=\frac{\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}\lambda_{j}^{t}}{\sqrt{1+\sum_{j\neq
k}\Delta_{ij}\lambda_{j}^{t}\lambda_{k}^{t}}}:=\frac{f_{i}(\overline{\rho}^{t})}{\sqrt{g_{i}(\overline{\rho}^{t})}}\enspace.$

Before computing the derivatives of $\rho^{t+1}_{i}$, let us compute the
derivatives of $\lambda^{t}_{i}$ as a function of $\rho^{t}_{j}$ where the
formula of $\lambda^{t}_{i}$ appears in (1). For any $i,j,k$ and
$\overline{\rho}\in[0,1/2]^{n}$,

$\frac{d\lambda^{t}_{i}}{d\rho^{t}_{j}}\bigg{|}_{\overline{0}}=\begin{cases}1&i=j\\\
0&i\neq j\end{cases}~{};\quad\text{and
}-C\leq\frac{d^{2}\lambda^{t}_{i}}{d\rho^{t}_{j}d\rho^{t}_{k}}\bigg{|}_{\overline{\rho}}\leq
C$

for some constant $C>0$. Using the fact that $\lambda^{t}_{i}=0$ if
$\rho^{t}_{i}=0$, we derive that

$\frac{df_{i}(\overline{\rho}^{t})}{d\rho^{t}_{j}}\Bigg{|}_{\overline{0}}=\begin{cases}1&j=i\\\
\Delta_{ij}=\rho^{*}_{i}\rho^{*}_{j}&j\neq i\end{cases},\quad
f_{i}(\overline{0})=\overline{0},\quad\frac{dg_{i}(\overline{\rho}^{t})}{d\rho^{t}_{j}}\Bigg{|}_{\overline{0}}=0,\quad
g_{i}(\overline{0})=1.$

Hence,

$\frac{d\rho^{t+1}_{i}}{d\rho^{t}_{j}}\Bigg{|}_{\overline{0}}=\frac{df_{i}(\overline{\rho}^{t})}{d\rho^{t}_{j}}=\begin{cases}1&j=i\\\
\rho^{*}_{i}\rho^{*}_{j}&j\neq i\end{cases}\enspace.$

Similarly, the second derivatives of $\rho^{t+1}_{i}$ are bounded, using the
bounds on the second derivatives of $\lambda^{t}_{j}$. ∎

This implies that if $\overline{\rho}^{t}$ approaches $\overline{0}$, then
$\overline{\rho}^{t+1}$ repels from $\overline{0}$:

######  Lemma 20.

There exists some $c>0$ such that if $\max_{i}\rho^{t}_{i}\leq c$ then
$\sum_{i}\rho^{t}_{i+1}\geq\sum_{i}\rho^{t}_{i}$.

###### Proof.

Using Lemma 19, we can write $\rho^{t+1}_{i}$ as a Taylor series around
$\overline{0}$

$\rho^{t+1}_{i}\geq\rho^{t}_{i}+\sum_{j\neq
i}\rho_{j}\rho^{*}_{i}\rho^{*}_{j}-\sum_{j,k}\frac{C}{2}\rho^{t}_{j}\rho^{t}_{k}.$

Summing over $i$, we derive that

$\sum_{i}\rho^{t+1}_{i}\geq\sum_{i}\rho^{t}_{i}+\sum_{i\neq
j}\rho_{j}\rho^{*}_{i}\rho^{*}_{j}-\sum_{i,j,k}\frac{C}{2}\rho^{t}_{j}\rho^{t}_{k}.$

While the second term in the right hand side is
$\Omega(\max_{j}\rho^{t}_{j})$, the third term is
$O(\max_{j}(\rho^{t}_{j})^{2})$. In particular, if the constant $c>0$ from the
definition of this lemma is sufficiently small, then the second term dominates
the third and the proof follows. ∎

To conclude the proof of Lemma 17, assume toward contradiction that
$\overline{\rho}^{t}\to\overline{0}$. Let $c>0$ be the parameter from Lemma
20, and let $T>0$ be the iteration such that for any $t\geq T$,
$\max_{i}\rho^{t}_{i}<c$. From Lemma 20, this implies that for any $t\geq T$,
$\sum_{j}\rho^{t}_{j}\geq\sum_{j}\rho^{T}_{j}$. From Lemma 18,
$\sum_{j}\rho^{T}_{j}>0$. In particular,
$\liminf_{t\to\infty}\sum_{j}\rho^{t}_{j}\geq\sum_{j}\rho^{T}_{j}>0$ which
implies that $\lim_{t\to\infty}\overline{\rho}^{t}\neq\overline{0}$, as
required.

###  A.2 Stationary points with some $\rho_{i}=1$

In this Section, we analyze the case of stationary points such that there
exists at least one $i$ with $\rho_{i}=1$. We show that EM will never converge
to any of those points. Let us start with the case where there are at least
two $i,j$ such that $\rho_{i}=\rho_{j}=1$. In that case, let $\mu$ be the
distribution at this point. Also, let

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

be the log-likelihood function. The following lemma shows that the EM
algorithm will never converge to this stationary point.

######  Lemma 21.

We have that

$\lim_{\rho_{i}\to 1,\rho_{j}\to 1}L(\rho)=-\infty$

###### Proof.

We can write the log-likelihood function as follows:

$\displaystyle L(\rho)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\rho}(\overline{x})$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\left(\Pr_{\rho}(x_{i},x_{j})\Pr_{\rho}\left(\overline{x}_{[n]\setminus\\{i,j\\}}\mid
x_{i},x_{j}\right)\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\rho}(x_{i},x_{j})+\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\rho}\left(\overline{x}_{[n]\setminus\\{i,j\\}}\mid
x_{i},x_{j}\right)$

The second term is clearly upper bounded over the whole region. For the first
term, it is clear that

$\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\rho}(x_{i},x_{j})=-KL(\mu^{*}(x_{i},x_{j}),\mu(x_{i},x_{j};\rho))-\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\mu^{*}(x_{i},x_{j})$

and it is clear that

$\lim_{\rho_{i}\to 1,\rho_{j}\to
1}KL(\mu^{*}(x_{i},x_{j}),\mu(x_{i},x_{j};\rho))=\infty$

while the second term is constant. It follows that

$\lim_{\rho_{i}\to 1,\rho_{j}\to
1}\operatorname*{\mathbb{E}}_{x\sim\mu^{*}}\log\Pr_{\rho}(x_{i},x_{j})=-\infty$

which completes the proof. ∎

Since the EM is guaranteed to improve the value of the likelihood at every
step, it is impossible to converge to this point.

First, we give a Lemma that characterizes the set of stationary points where
some $\rho_{i}=1$.

######  Lemma 22.

Define for all $i\in[n]$ a vector $g^{i}\in\mathbf{R}^{n}$ as

$(g^{i})_{j}=\left\\{\begin{array}[]{ll}1&\text{ if $i=j$}\\\
\rho_{i}^{*}\rho_{j}^{*}&\text{ if $i\neq j$}\end{array}\right.$

The set of stationary points of the population EM update where some
$\rho_{i}=1$ is exactly the set

$\\{g^{i}:i\in[n]\\}$

###### Proof.

Let us consider the case of a stationary point where there is exactly one $i$
with $\rho_{i}=1$. The reason is that if at least two coordinates are $1$,
then as we showed earlier, the value of the likelihood is $-\infty$ so these
are not stationary points. Without loss of generality, suppose $\rho_{1}=1$.
The reason this is a fixpoint is that if $\rho^{t}_{1}=1$, then $y=x_{1}$ in
the conditional model of $y$ given $x$, which means that $\rho^{t+1}=1$. Then,
by the fixpoint equations we immediately get that in the fixpoint we should
have

$\tilde{\rho}_{i}=\rho_{i}^{*}\rho_{1}^{*}$

for $i\neq 1$, which is the vector $g^{1}$. Similarly, by setting $\rho_{i}=1$
we get exactly one such fixpoint $g^{i}$. ∎

From now on, when we refer to $\tilde{\rho}$, it will be implied that it is
equal to $g^{1}$. We would like to show that when we start running EM from a
point in the interior of the region, we will not converge to this stationary
point. However, we already know that if we start from a point with
$\rho_{1}=1$, then inevitably in the next iteration we will converge to the
stationary point values for the other variables as well. Hence, this
stationary point will be a saddle point of the log-likelihood.

In particular, we will prove the following Theorem.

######  Theorem 4.

Let $\rho$ be a stationary point with $\rho_{1}=1$. Then, there exists an
$\epsilon_{0}>0$, such that the following condition holds: if we start running
EM from any initial point $\rho^{0}$ that satisfies
$\|\rho^{0}-\rho\|_{2}<\epsilon_{0}$ and such that $\rho^{0}_{i}<1$ for all
$i$, then after a finite number of iterations $t=t(\rho_{0})$ we have

$\|\rho^{t}-\rho\|_{2}>\epsilon_{0}$

We stress that the number of iterations $t$ depends on the initial value
$\rho_{0}$. Let us argue why Theorem 4 implies that EM does not converge to
$\rho$ from any initial point inside the region. Indeed, if EM converged for
some initial value $\rho^{0}$, then for any $\epsilon>0$, and in particular
for $\epsilon=\epsilon_{0}$, there exists some iteration $T$ such that for
$t\geq T$ we get

$\|\rho^{t}-\rho\|\leq\epsilon$

However, if we apply Theorem 4 for $\rho^{0}=\rho^{T}$, we get that there
should exists some $t>T$ with $\|\rho^{t}-\rho\|>\epsilon_{0}$. This is a
contradiction to the convergence claim. Hence, it suffices to prove Theorem 4.
The first step is to establish the following Lemma. It’s purpose is to show
that if the distances of all the coordinates are roughly equal, then
$\rho_{1}$ will move away from the fixpoint value of $1$.

######  Lemma 23.

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

$\epsilon:=\max_{i}|\tilde{\rho}_{i}-\rho^{t}_{i}|$

Then, there are constants $C,K>0$ such that

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

###### Proof.

The proof consists of viewing the update rule as a function of the previous
step and writing the Taylor expansion of the this function around the fixpoint
$\rho$. In particular, we define the function

$f(\rho)=\frac{\rho_{1}+\sum_{j\neq
1}(\rho_{1}\rho_{j}-\rho^{*}_{1}\rho^{*}_{j})\lambda_{j}}{\sqrt{1+\sum_{j,k\colon
j\neq k}(\rho_{j}\rho_{k}-\rho^{*}_{j}\rho^{*}_{k})\lambda_{j}\lambda_{k}}}$

where

$\lambda_{j}=\frac{\frac{\rho_{j}}{1-\rho_{j}^{2}}}{1+\sum_{k}\frac{\rho_{k}^{2}}{1-\rho_{k}^{2}}}$

Clearly, we have that

$f(\rho^{t})=\rho^{t+1}$

We will compute the Taylor expansion of $f$ around the fixpoint $\rho$. We
start by computing the first derivatives of $f$ at the fixpoint
$\tilde{\rho}$. To do that, we need the derivatives of $\lambda_{j}$ with
$\rho_{i}$. We start with the case $i=j$

$\displaystyle\frac{\partial\lambda_{1}}{\partial\rho_{i}}$
$\displaystyle=\frac{\frac{\partial}{\partial\rho_{i}}\left(\frac{\rho_{i}}{1-\rho_{i}^{2}}\right)}{1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}}-\frac{\partial}{\partial\rho_{i}}\left(1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}\right)\frac{\left(\frac{\rho_{i}}{1-\rho_{i}^{2}}\right)}{\left(1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}\right)^{2}}$
$\displaystyle=\frac{\frac{1}{1-\rho_{i}^{2}}+\frac{2\rho_{i}^{2}}{(1-\rho_{i}^{2})^{2}}}{1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}}-\left(\frac{2\rho_{i}}{(1-\rho_{i}^{2})^{2}}\right)\frac{\left(\frac{\rho_{i}}{1-\rho_{i}^{2}}\right)}{\left(1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}\right)^{2}}$
$\displaystyle=\frac{\lambda_{1}}{\rho_{i}}+2\frac{\rho_{i}\lambda_{1}}{1-\rho_{i}^{2}}-2\frac{\lambda_{1}^{2}}{1-\rho_{i}^{2}}$

Let’s evaluate the limit as $\rho\to\tilde{\rho}$. We know that as
$\rho_{1}\to 1$, we will have $\lambda_{1}\to 1$ and $\lambda_{j}\to 0$ for
$j\neq 1$. Based on these observations, we have that

$\displaystyle\lim_{\rho_{1}\to 1}\frac{\rho_{1}-\lambda_{1}}{1-\rho_{1}^{2}}$
$\displaystyle=\frac{\rho_{1}-\frac{\frac{\rho_{1}}{1-\rho_{1}^{2}}}{1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}}}{1-\rho_{1}^{2}}$
$\displaystyle=\lim_{\rho_{1}\to
1}\frac{\rho_{1}+\rho_{1}\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}-\frac{\rho_{1}}{1-\rho_{1}^{2}}}{\left(1+\sum_{j}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}\right)(1-\rho_{1}^{2})}$
$\displaystyle=\lim_{\rho_{1}\to
1}\left(\rho_{1}+\frac{\rho_{1}^{3}-\rho_{1}}{1-\rho_{1}^{2}}+\rho_{1}\sum_{j\neq
1}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}\right)$ $\displaystyle=\sum_{j\neq
1}\frac{\rho_{j}^{2}}{1-\rho_{j}^{2}}$

Hence,

$\lim_{\rho\to\tilde{\rho}}\frac{\partial\lambda_{1}}{\partial\rho_{1}}=2\sum_{j\neq
1}\frac{\tilde{\rho}_{j}^{2}}{1-\tilde{\rho}_{j}^{2}}+1=2\sum_{j\neq
1}\frac{(\rho^{*}_{j})^{2}(\rho^{*}_{1})^{2}}{1-(\rho^{*}_{j})^{2}(\rho^{*}_{1})^{2}}+1$

For $j\neq 1$, we have

$\displaystyle\frac{\partial\lambda_{j}}{\partial\rho_{i}}$
$\displaystyle=\frac{\partial}{\partial\rho_{i}}\frac{\frac{\rho_{j}}{1-\rho_{j}^{2}}}{1+\sum_{k}\frac{\rho_{k}^{2}}{1-\rho_{k}^{2}}}=-\frac{\frac{\rho_{j}}{1-\rho_{j}^{2}}}{\left(1+\sum_{k}\frac{\rho_{k}^{2}}{1-\rho_{k}^{2}}\right)^{2}}\frac{\partial}{\partial\rho_{i}}\left(\frac{\rho_{i}^{2}}{1-\rho_{i}^{2}}\right)$
$\displaystyle=-\frac{\frac{\rho_{j}}{1-\rho_{j}^{2}}}{\left(1+\sum_{k}\frac{\rho_{k}^{2}}{1-\rho_{k}^{2}}\right)^{2}}\frac{2\rho_{i}}{(1-\rho_{i}^{2})^{2}}$
$\displaystyle=-2\frac{\lambda_{1}\lambda_{j}}{1-\rho_{i}^{2}}$

We know that as $\rho_{i}\to 1$, we have $\lambda_{1}\to 1$. Also,

$\lim_{\rho_{i}\to
1}\frac{\lambda_{j}}{1-\rho_{i}^{2}}=\rho_{j}/(1-\rho_{j}^{2})$

Hence,

$\lim_{\rho\to\tilde{\rho}}\frac{\partial\lambda_{j}}{\partial\rho_{i}}=-2\frac{\rho^{*}_{j}\rho_{1}^{*}}{1-(\rho^{*}_{j}\rho_{1}^{*})^{2}}$

What we mostly care about is that these derivatives are bounded. Now, we are
ready to compute the various derivatives of $f$ at the fixpoint. We will use
the notation $\Delta_{jk}:=\rho_{j}^{*}\rho_{k}^{*}-\rho_{j}\rho_{k}$.

$\displaystyle\frac{\partial f}{\partial\rho_{1}}$
$\displaystyle=\frac{\frac{\partial}{\partial\rho_{1}}\left(\rho_{1}+\sum_{j\neq
1}\Delta_{1j}\lambda_{j}\right)}{\sqrt{1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}}}-\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
1}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\frac{\partial}{\partial\rho_{1}}\left(1+\sum_{j,k\colon
j\neq k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)$
$\displaystyle=\frac{1+\sum_{j\neq
1}\Delta_{1j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}-\sum_{j\neq
1}\lambda_{j}\rho_{j}}{\sqrt{1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}}}$
$\displaystyle-\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
1}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\left(2\sum_{j\neq
1}\frac{\partial\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\Delta_{1j}-2\sum_{j\neq
1}\lambda_{1}\lambda_{j}\rho_{j}-\sum_{j\neq k\neq
1}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{1}}\Delta_{jk}\right)$

Now, let us examine what happends when we plug in the fixpoint. We know that
$\Delta_{1j}\to 0$ and $\lambda_{j}\to 0$ for $j\neq 1$, hence the entire
first term tends to $1$. As for the second term, we have

$\lim_{\rho_{1}\to 1}\frac{\rho_{1}+\sum_{j\neq
1}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}=1$

Also, notice that

$\frac{\partial\lambda_{1}\lambda_{j}}{\partial\rho_{1}}=\frac{\partial\lambda_{1}}{\partial\rho_{1}}\lambda_{j}+\frac{\partial\lambda_{j}}{\partial\rho_{1}}\lambda_{1}$

is bounded, hence

$\lim_{\rho\to\tilde{\rho}}\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{d\rho_{i}}\Delta_{1j}=0$

It is also clear that

$\lim_{\rho_{i}\to 1}\sum_{j\neq 1}\lambda_{1}\lambda_{j}\rho_{j}=0$

Lastly, we have

$\frac{\partial\lambda_{j}\lambda_{k}}{d\rho_{i}}=\lambda_{j}\frac{d\lambda_{k}}{d\rho_{i}}+\lambda_{k}\frac{\partial\lambda_{j}}{d\rho_{i}}\to
0$

Hence, the second term tends to $0$. Hence,

$\lim_{\rho\to\tilde{\rho}}\frac{\partial f}{\partial\rho_{1}}=1$

Let’s now calculate $\partial f/\partial\rho_{u}$ for some $u\neq 1$. Using
the exact same calculation, we arrive at the formula

$\displaystyle\frac{\partial f}{\partial\rho_{u}}=\frac{\sum_{j\neq
1}\Delta_{1j}\frac{\partial\lambda_{j}}{\partial\rho_{u}}-\lambda_{u}\rho_{1}}{\sqrt{1+\sum_{j,k\colon
j\neq k}\Delta_{jk}\lambda_{j}\lambda_{k}}}$
$\displaystyle-\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
1}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\left(2\sum_{j\neq
u}\frac{d\lambda_{u}\lambda_{j}}{\partial\rho_{u}}\Delta_{uj}-2\sum_{j\neq
u}\lambda_{j}\lambda_{u}\rho_{j}-\sum_{j\neq k\neq
u}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{u}}\Delta_{jk}\right)$

This time, both the first and the second terms converge to $0$, hence

$\lim_{\rho\to\tilde{\rho}}\frac{\partial f}{\partial\rho_{u}}=0$

Now, we move on to the second derivatives. First of all, let’s compute the
ones for $\lambda_{1}$. We just want to ensure that they will be bounded.

$\displaystyle\frac{\partial^{2}\lambda_{j}}{\partial^{2}\rho_{1}}$
$\displaystyle=\frac{\partial}{\partial\rho_{1}}\left(-2\frac{\lambda_{1}\lambda_{j}}{1-\rho_{1}^{2}}\right)$
$\displaystyle=-2\frac{(\partial\lambda_{1}/\partial\rho_{1})\lambda_{j}}{1-\rho_{1}^{2}}-2\frac{(\partial\lambda_{j}/\partial\rho_{1})\lambda_{1}}{1-\rho_{1}^{2}}-4\frac{\lambda_{1}\lambda_{j}\rho_{1}}{(1-\rho_{1}^{2})^{2}}$
$\displaystyle=-2\frac{(\partial\lambda_{1}/\partial\rho_{1})\lambda_{j}}{1-\rho_{1}^{2}}+4\frac{\lambda_{j}\lambda_{1}^{2}}{(1-\rho_{1}^{2})^{2}}-4\frac{\lambda_{1}\lambda_{j}\rho_{1}}{(1-\rho_{1}^{2})^{2}}$
$\displaystyle=-2\frac{(\partial\lambda_{1}/\partial\rho_{1})\lambda_{j}}{1-\rho_{1}^{2}}+4\frac{\lambda_{1}\lambda_{j}}{1-\rho_{1}^{2}}\left(\frac{\lambda_{1}-\rho_{1}}{1-\rho_{1}^{2}}\right)$

The first term is constant in the limit and the second term is also constant,
since the limit $\lim_{\rho_{1}\to 1}(\lambda_{1}-\rho_{1})/(1-\rho_{1}^{2})$
has been shown to be constant. Similarly, we have

$\displaystyle\frac{\partial^{2}\lambda_{j}}{\partial\rho_{1}\partial\rho_{u}}$
$\displaystyle=\frac{\partial}{\partial\rho_{u}}\left(-2\frac{\lambda_{1}\lambda_{j}}{1-\rho_{1}^{2}}\right)$
$\displaystyle=-2\frac{(\partial\lambda_{1}/\partial\rho_{u})\lambda_{j}+(\partial\lambda_{j}/\partial\rho_{u})\lambda_{1}}{1-\rho_{1}^{2}}$
$\displaystyle=4\frac{\lambda_{1}\lambda_{j}\lambda_{u}}{(1-\rho_{1}^{2})(1-\rho_{u}^{2})}+4\frac{\lambda_{j}\lambda_{u}\lambda_{1}}{(1-\rho_{1}^{2})(1-\rho_{u}^{2})}$

It’s clear that both terms tend to $0$. Finally, let’s calculate

$\displaystyle\frac{\partial^{2}\lambda_{1}}{\partial^{2}\rho_{1}}$
$\displaystyle=\frac{\partial}{\partial\rho_{1}}\left(\frac{\lambda_{1}}{\rho_{1}}+2\frac{\rho_{1}\lambda_{1}}{1-\rho_{1}^{2}}-2\frac{\lambda_{1}^{2}}{1-\rho_{1}^{2}}\right)$
$\displaystyle=\frac{\partial}{\partial\rho_{1}}\left(\frac{\lambda_{1}}{\rho_{1}}\right)+2\frac{\partial\lambda_{1}}{\partial\rho_{1}}\frac{\rho_{1}-\lambda_{1}}{1-\rho_{1}^{2}}+2\lambda_{1}\frac{\partial}{\partial\rho_{1}}\left(\frac{\rho_{1}-\lambda_{1}}{1-\rho_{1}^{2}}\right)$

By taking the limit $\rho_{1}\to 1$ we verify easily that the second
derivative is bounded.

Now, let’s compute the second derivative $\partial^{2}f/\partial^{2}\rho_{1}$.
To make the presentation easier, we derive each of the two terms separately.

$\displaystyle\frac{\partial}{\partial\rho_{1}}\left(\frac{1+\sum_{j\neq
1}\Delta_{1j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}-\sum_{j\neq
1}\lambda_{j}\rho_{j}}{\sqrt{1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}}}\right)=\frac{\sum_{j\neq
1}\Delta_{1j}\frac{\partial^{2}\lambda_{j}}{\partial^{2}\rho_{1}}-\sum_{j\neq
1}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\rho_{j}-\sum_{j\neq
1}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\rho_{j}}{\sqrt{1+\sum_{j,k\colon
j\neq k}\Delta_{jk}\lambda_{j}\lambda_{k}}}$
$\displaystyle-\frac{1}{2}\frac{1+\sum_{j\neq
1}\Delta_{1j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}-\sum_{j\neq
1}\lambda_{j}\rho_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\left(2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\Delta_{1j}-2\sum_{j\neq
1}\lambda_{1}\lambda_{j}\rho_{j}-\sum_{j\neq k\neq
i}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{1}}\Delta_{jk}\right)$

In the first term, the final result once we take the limit is

$-2\sum_{j\neq
1}\rho_{j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\mid_{\rho=\tilde{\rho}}$

As for the second term, the rightmost parenthesis is $0$, as shown in the
calculation of the first derivative. Now, let’s move to the second term. We
want

$\frac{\partial}{\partial\rho_{1}}\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
i}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\left(2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\Delta_{1j}-2\sum_{j\neq
1}\lambda_{1}\lambda_{j}\rho_{j}-\sum_{j\neq k\neq
i}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{1}}\Delta_{jk}\right)$

We can view this as a product of three terms and use the product rule. Notice
that the third term is $0$ in the fixpoint, so when deriving the first two
terms we will get $0$ in the final expression. Hence, the only term that
matters is

$\displaystyle\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
i}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\frac{\partial}{\partial\rho_{1}}\left(2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\Delta_{1j}-2\sum_{j\neq
1}\lambda_{1}\lambda_{j}\rho_{j}-\sum_{j\neq k\neq
i}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{1}}\Delta_{jk}\right)$
$\displaystyle=\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
i}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\left(2\sum_{j\neq
1}\frac{\partial^{2}\lambda_{1}\lambda_{j}}{\partial^{2}\rho_{1}}\Delta_{1j}-2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\rho_{j}-2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\rho_{j}-\sum_{j\neq k\neq
i}\frac{\partial^{2}\lambda_{j}\lambda_{k}}{\partial^{2}\rho_{1}}\Delta_{jk}\right)$

First of all, as usual we have

$\lim_{\rho\to\tilde{\rho}}\frac{\rho_{1}+\sum_{j\neq
i}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}=1$

Also, we have

$\displaystyle\lim_{\rho\to\tilde{\rho}}\sum_{j\neq
1}\frac{\partial^{2}\lambda_{1}\lambda_{j}}{\partial^{2}\rho_{1}}\Delta_{1j}=0$
$\displaystyle\lim_{\rho\to\tilde{\rho}}\sum_{j\neq
1}\frac{\partial\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\rho_{j}=\lim_{\rho\to\tilde{\rho}}\sum_{j\neq
1}\left(\lambda_{1}\frac{\partial\lambda_{j}}{\partial\rho_{1}}+\lambda_{j}\frac{d\lambda_{1}}{\partial\rho_{1}}\right)\rho_{j}=\sum_{j\neq
1}\rho_{j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\mid_{\rho=\tilde{\rho}}$

Hence, we get the same expression as in the first term and these two cancel
each other. We are only left with computing the term

$\lim\sum_{j\neq k\neq
1}\frac{\partial^{2}\lambda_{j}\lambda_{k}}{\partial^{2}\rho_{1}}\Delta_{jk}$

If we set $g(x)=x/(1-x^{2})$, then we get

$\displaystyle\lim_{\rho\to\tilde{\rho}}\sum_{j\neq k\neq
1}\frac{\partial^{2}\lambda_{j}\lambda_{k}}{\partial^{2}\rho_{1}}\Delta_{jk}$
$\displaystyle=\lim_{\rho\to\tilde{\rho}}\sum_{j\neq k\neq
1}\left(\frac{\partial^{2}\lambda_{j}}{\partial^{2}\rho_{1}}\lambda_{k}+\frac{\partial^{2}\lambda_{k}}{\partial^{2}\rho_{1}}\lambda_{j}+2\frac{\partial\lambda_{j}}{\partial\rho_{1}}\frac{d\lambda_{k}}{d\rho_{i}}\right)\Delta_{jk}$
$\displaystyle=8\sum_{j\neq k\neq
1}g(\rho_{1}^{*}\rho_{j}^{*})g(\rho_{1}^{*}\rho_{k}^{*})\rho_{j}^{*}\rho_{k}^{*}(1-(\rho_{1}^{*})^{2})$

Hence,

$\frac{\partial^{2}f}{\partial^{2}\rho_{1}}=-4\sum_{j\neq k\neq
1}g(\rho_{1}^{*}\rho_{j}^{*})g(\rho_{1}^{*}\rho_{k}^{*})\rho_{j}^{*}\rho_{k}^{*}(1-(\rho_{1}^{*})^{2})<0$

Let’s define

$C:=2\sum_{j\neq k\neq
1}g(\rho_{1}^{*}\rho_{j}^{*})g(\rho_{1}^{*}\rho_{k}^{*})\rho_{j}^{*}\rho_{k}^{*}(1-(\rho_{1}^{*})^{2})$

Clearly $C$ is a constant depending only on the true model. Now, let’s compute
the other mixed derivatives. Let $u\neq 1$. We will compute
$\partial^{2}f/\partial\rho_{1}\partial\rho_{u}$. Again, for convenience we
will derive each of the two terms of
$\partial\rho_{1}^{\prime}/\partial\rho_{1}$ separately. We have

$\displaystyle\frac{\partial}{\partial\rho_{u}}\left(\frac{1+\sum_{j\neq
1}\Delta_{1j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}-\sum_{j\neq
1}\lambda_{j}\rho_{j}}{\sqrt{1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}}}\right)=\frac{\sum_{j\neq
1}\Delta_{1j}\frac{\partial^{2}\lambda_{j}}{\partial\rho_{1}\partial\rho_{u}}-\frac{d\lambda_{u}}{\partial\rho_{1}}\rho_{1}-\sum_{j\neq
1}\frac{\partial\lambda_{j}}{\partial\rho_{u}}\rho_{j}-\lambda_{u}}{\sqrt{1+\sum_{j,k\colon
j\neq k}\Delta_{jk}\lambda_{j}\lambda_{k}}}$
$\displaystyle-\frac{1}{2}\frac{1+\sum_{j\neq
1}\Delta_{1j}\frac{\partial\lambda_{j}}{\partial\rho_{1}}-\sum_{j\neq
1}\lambda_{j}\rho_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\left(2\sum_{j\neq
u}\frac{d\lambda_{u}\lambda_{j}}{\partial\rho_{u}}\Delta_{uj}-2\sum_{j\neq
u}\lambda_{u}\lambda_{j}\rho_{j}-\sum_{j\neq k\neq
u}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{u}}\Delta_{jk}\right)$

From the first term, the only term that survives in the limit is

$-\frac{d\lambda_{u}}{\partial\rho_{1}}\rho_{1}\mid_{\rho=\tilde{\rho}}=-\frac{d\lambda_{u}}{\partial\rho_{1}}\mid_{\rho=\tilde{\rho}}$

We turn to the second term that needs differentiation. This is similar to what
we had previously, where the only term that matters is

$\displaystyle\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
i}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\frac{\partial}{\partial\rho_{u}}\left(2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{1}}\Delta_{1j}-2\sum_{j\neq
1}\lambda_{1}\lambda_{j}\rho_{j}-\sum_{j\neq k\neq
i}\frac{\partial\lambda_{j}\lambda_{k}}{\partial\rho_{1}}\Delta_{jk}\right)$
$\displaystyle=\frac{1}{2}\frac{\rho_{1}+\sum_{j\neq
i}\Delta_{1j}\lambda_{j}}{\left(1+\sum_{j,k\colon j\neq
k}\Delta_{jk}\lambda_{j}\lambda_{k}\right)^{3/2}}\times$
$\displaystyle\times\left(2\sum_{j\neq
1}\frac{\partial^{2}\lambda_{1}\lambda_{j}}{\partial\rho_{1}\partial\rho_{u}}\Delta_{1j}-2\frac{d\lambda_{1}\lambda_{u}}{\partial\rho_{1}}\rho_{1}-2\sum_{j\neq
1}\frac{d\lambda_{1}\lambda_{j}}{\partial\rho_{u}}\rho_{j}-2\lambda_{1}\lambda_{u}-\sum_{j\neq
k\neq
1}\frac{\partial^{2}\lambda_{j}\lambda_{k}}{\partial^{2}\rho_{1}\rho_{u}}\Delta_{jk}-2\sum_{j\neq
u,1}\frac{\partial\lambda_{j}\lambda_{u}}{\partial\rho_{1}}\rho_{j}\right)$

The only terms that survive in the second parenthesis are

$-2\frac{\partial\lambda_{1}\lambda_{u}}{\partial\rho_{1}}\rho_{1}$

In the limit, this is equal to

$-2\frac{\partial\lambda_{u}}{\partial\rho_{1}}\mid_{\rho=\tilde{\rho}}$

We see that this exactly cancels with what we got in the first term. Hence,

$\frac{\partial^{2}f}{\partial\rho_{1}\partial\rho_{u}}\mid_{\rho=\tilde{\rho}}=0$

Similarly, for $u\neq v\neq 1$ we get

$\frac{\partial^{2}f}{\partial\rho_{u}d\rho_{v}}=0$

By similar calculations we can easily show that the third derivatives will
also be bounded in a neighborhood of $\tilde{\rho}$. By using the second order
Taylor Theorem, we get that

$\displaystyle\rho^{t+1}_{1}$ $\displaystyle=1+(\rho^{t}_{1}-1)\frac{\partial
f}{\partial\rho_{1}}\mid_{\rho=\tilde{\rho}}+\frac{1}{2}\frac{\partial^{2}f}{\partial^{2}\rho_{1}}\mid_{\rho=\tilde{\rho}}(1-\rho^{t}_{1})^{2}+O(\epsilon^{3})$
$\displaystyle=\rho^{t}_{1}-C|\rho_{1}^{t}-1|^{2}+O(\epsilon^{3})$

∎

Using Lemma 23, it is clear that there is a second order term that is pushing
$\rho_{1}^{t}$ away from $1$. Notice that this implies that we do not have a
strict saddle point. However, the third order term depends on the distance of
all the other coordinates from their fixpoint values. Hence, in order for the
second order term to dominate the third order term, we need to prove that
$|\rho_{i}^{t}-\rho_{i}^{*}\rho_{1}^{*}|$ is roughly the same size as
$1-\rho_{1}^{t}$ for all $i\neq 1$. Obviously, with a bad initialization, this
might not happen. However, we can prove that after one iteration of the EM,
this will always happen, no matter the starting point. This is the content of
the following lemma.

######  Lemma 24.

Let $\rho^{t}$ be the current iteration of EM. Then, there exists an
$\epsilon>0$ such that if $\|\rho^{t}-\tilde{\rho}\|_{\infty}<\epsilon$, then
there exists an absolute constant $M>0$ such that for all $i\neq 1$

$|\rho_{i}^{t+1}-\rho_{i}^{*}\rho_{1}^{*}|\leq M(1-\rho^{t+1}_{1})$

###### Proof.

Let us fix an $i\neq 1$ and define the functions

$\displaystyle f_{i}(\rho):=\frac{\rho_{i}+\sum_{j\neq
i}(\rho_{i}\rho_{j}-\rho^{*}_{i}\rho^{*}_{j})\lambda_{j}}{\sqrt{1+\sum_{j,k\colon
j\neq k}(\rho_{j}\rho_{k}-\rho^{*}_{j}\rho^{*}_{k})\lambda_{j}\lambda_{k}}}$
$\displaystyle f_{1}(\rho):=\frac{\rho_{1}+\sum_{j\neq
1}(\rho_{1}\rho_{j}-\rho^{*}_{1}\rho^{*}_{j})\lambda_{j}}{\sqrt{1+\sum_{j,k\colon
j\neq k}(\rho_{j}\rho_{k}-\rho^{*}_{j}\rho^{*}_{k})\lambda_{j}\lambda_{k}}}$
$\displaystyle
r_{i}(\rho):=\frac{f_{i}(\rho)-\rho_{i}^{*}\rho_{1}^{*}}{f_{1}(\rho)-1}$

We will show that the limit

$\lim_{\rho\to\tilde{\rho}}r_{i}(\rho)$

exists and is bounded. First, let’s fix the coordinates $\rho_{i}$ for $i\neq
1$ and have $\rho_{1}\to 1$. This means that $\lambda_{1}\to 1$ and
$\lambda_{j}\to 0$ for $j\neq 1$. Notice however that we do not have
$\Delta_{ij}\to 0$, as the values of the other coordinates are not in the
fixpoint yet. However, we will see that this will not matter for the
computation of the limit. We have by L’Hospital’s rule

$\displaystyle\lim_{\rho_{1}\to 1}r_{i}(\rho)$
$\displaystyle=\lim_{\rho_{1}\to 1}\frac{\frac{\partial
f_{i}(\rho)}{\partial\rho_{1}}}{\frac{\partial
f_{1}(\rho)}{\partial\rho_{1}}}$ $\displaystyle=\sum_{j\neq
i}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\Delta_{ij}-\lambda_{1}\rho_{i}-\sum_{j\neq
1}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\Delta_{1j}$

Now, we take the limit with respect to the remaining variables, which gives

$\displaystyle\lim_{\rho\to\tilde{\rho}}r_{i}(\rho)$
$\displaystyle=\sum_{j\neq
i}\frac{\partial\lambda_{j}}{\partial\rho_{1}}\mid_{\rho=\tilde{\rho}}\rho_{i}^{*}\rho_{j}^{*}(1-(\rho_{1}^{*})^{2})-\rho_{i}^{*}\rho_{1}^{*}$

This is a finite quantity that depends only on the true parameters, hence it
is a constant. Since the function $r_{i}(\rho)$ is continuous, we get that
there exists an $\epsilon>0$ such that if
$\|\rho-\tilde{\rho}\|_{\infty}<\epsilon$ then

$|r_{i}(\rho)|\leq M$

for some $M>0$. Substituting $\rho=\rho^{t}$ gives

$\left|\frac{\rho^{t+1}_{i}-\rho^{*}_{i}\rho^{*}_{1}}{\rho^{t+1}_{1}-1}\right|\leq
M$

which is what we wanted to prove.

∎

With Lemmas 23 and 24 in our hands, we can proceed to prove Theorem 4. The
idea is the following: if in the starting point $\rho^{0}$ the distance of
$\rho^{0}_{1}$ from $1$ is much less that the distances of the other
coordinates from the fixpoint values, then in the following iteration they
will all come closer to the fixpoint, so that all the distances are
comparable. This means that even if the algorithm starts from a bad angle, it
will quickly correct itself to a good angle in the next iteration. After that,
in the following iterations, the second order term computed in Lemma 23 will
dominate the third order term and repel $\rho_{1}$ away from $1$, until it
gets out of the ball.

###### Proof of Theorem 4.

Let $\epsilon_{1}$ be the value of $\epsilon$ from Lemma 23 and $\epsilon_{2}$
be the value from Lemma 24. Also, let $\epsilon_{3}$ be small enough so that

$C\epsilon^{2}/2>KM\epsilon^{3}$

for all $\epsilon<\epsilon_{3}$. We choose
$\epsilon_{0}=\min(\epsilon_{1},\epsilon_{2},\epsilon_{3})$. Let $\rho^{0}$ be
a starting point of EM with $\|\rho^{0}-\tilde{\rho}\|_{2}\leq\epsilon_{0}$
and $\rho_{i}^{0}<1$ for all $i$.

Let $t\geq 1$. If $\|\rho^{t^{\prime}}-\tilde{\rho}\|_{2}>\epsilon_{0}$ for
some $t^{\prime}\leq t$, then we have nothing to prove. Suppose
$\|\rho^{t^{\prime}}-\tilde{\rho}\|_{2}<\epsilon_{0}$ for all $t^{\prime}\leq
t$. Then, by applying Lemma 24 we get that

$|\rho_{i}^{t}-\rho_{i}^{*}\rho_{1}^{*}|\leq M(1-\rho^{t}_{1})$

for all $i\neq 1$. This means that by applying Lemma 23 and by the particular
choice of $\epsilon_{0}$, we have that

$\displaystyle\rho_{1}^{t+1}$
$\displaystyle\leq\rho_{1}^{t}-C(1-\rho_{1}^{t})^{2}+KM(1-\rho^{t}_{1})^{3}\leq\rho_{1}^{t}-\frac{C}{2}(1-\rho_{1}^{t})^{2}$

This implies that

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

This holds for all times up to $t$. If we set $\alpha_{t}=1-\rho_{1}^{t}$,
this implies the recursive relation

$\alpha^{t+1}\geq\alpha^{t}+\frac{C}{2}(\alpha^{t})^{2}$

It is obvious that $\alpha^{t}$ is an increasing function of $t$, meaning that
$\alpha^{t}\geq\alpha^{0}$. This means that
$\alpha^{t+1}\geq\alpha^{t}+\frac{C}{2}(\alpha^{0})^{2}$. Since
$\alpha^{0}=1-\rho^{0}_{1}>0$, we have that
$\lim_{t\to\infty}\alpha^{t}=\infty$. This implies that there exists a finite
time $T$ such that

$1-\rho_{1}^{t}=\alpha^{t}>\epsilon_{0}$

This implies that $\|\rho^{t}-\tilde{\rho}\|_{2}>\epsilon_{0}$ and the proof
is complete.

∎

###  A.3 Deffered proofs from Section 2

###### Proof of Lemma 2.

Using Lemma 1 and Claim 1, we derive that

$\displaystyle\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mu^{t,*}}[x_{i}y]=\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[x_{i}y]\right]=\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[x_{i}\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[y]\right]=\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[x_{i}\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}x_{j}\right]$
(12)
$\displaystyle=\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[x_{i}x_{j}\right]=\sigma^{t}_{y}\sigma^{t}_{i}\lambda^{t}_{i}+\sum_{j\neq
i}\sigma^{t}_{y}\sigma^{t}_{i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}=\sigma^{t}_{y}\sigma^{t}_{i}\left(\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\rho^{*}_{i}\rho^{*}_{j}\right)\enspace.$

This concludes the first expression for
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]$. Next, we would like to show
that the second expression equals the first expression. First, recall that in
(12) we have shown that

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

If we substitute $\mu^{t}$ instead of $\mu^{*}$, we derive that

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

Since the right hand side equals

$\operatorname*{\mathbb{E}}_{\mu^{t}}[x_{i}y]=\sigma^{t}_{i}\sigma^{t}_{y}\rho^{t}_{i},$

we derive that

$\sigma^{t}_{i}\sigma^{t}_{y}\rho^{t}_{i}-\sigma^{t}_{i}\sigma^{t}_{y}\left(\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\rho^{t}_{i}\rho^{t}_{j}\right)=0\enspace.$ (13)

Adding the left hand side of (13) to (12), we derive that

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

which is exactly the second expression for
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]$. Next, we compute the
variance for $y$, again, using Lemma 1 and Claim 1:

$\displaystyle\operatorname*{\mathbb{E}}_{\mu^{t+1}}[y^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mu^{t,*}}[y^{2}]=\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[y^{2}]\right]=\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[\left(\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}x_{j}\right)^{2}\right]$
(14)
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{i}}\lambda^{t}_{i}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}\operatorname*{\mathbb{E}}_{\mu^{*}_{x}}\left[x_{i}x_{j}\right]=(\sigma^{t}_{y})^{2}\left(\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}\right)\enspace.$

This derives the first expression for the variance of $y$. We derive the
second expression using a similar logic as in the calculation in the second
expression for $\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]$. First,
substituting $\rho^{t}$ instead of $\rho^{*}$ in (14), we derive that

$(\sigma_{y}^{t})^{2}=\operatorname*{\mathbb{E}}_{\mu^{t}}[y^{2}]=\operatorname*{\mathbb{E}}_{\mu^{t}_{x}}\left[\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[y^{2}]\right]=(\sigma^{t}_{y})^{2}\left(\sum_{i=1}^{n}(\lambda^{t}_{i})^{2}+\sum_{i\neq
j\in\\{1,\dots,n\\}}\lambda^{t}_{i}\lambda^{t}_{j}\rho^{t}_{i}\rho^{t}_{j}\right)\enspace.$

This implies that

$(\sigma_{y}^{t})^{2}\left(1-\sum_{i=1}^{n}(\lambda^{t}_{i})^{2}-\sum_{i\neq
j\in\\{1,\dots,n\\}}\lambda^{t}_{i}\lambda^{t}_{j}\rho^{t}_{i}\rho^{t}_{j}\right)=0.$

Adding this to the expression in (14), this yields the second expression for
the covariance of $y$, as required.

Lastly, the expression of $\rho^{t+1}_{i}$ is derived, by definition of
$\rho_{i}$,

$\rho^{t+1}_{i}=\frac{\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]}{\sqrt{\operatorname{Var}_{\mu^{t+1}}[x_{i}]\operatorname{Var}_{\mu^{t+1}}[y]}},$

and by substituting the expressions for the covariance of $x_{i}$ and $y$, the
variance of $y$, and using Lemma 1 which argues that
$\operatorname{Var}_{\mu^{t+1}}[x_{i}]=\sigma_{i}^{2}$. ∎

###### Proof of Lemma 3.

The convergence of $\overline{\rho}^{t}$ to some
$\overline{\rho}\in\mathcal{S}$ follows directly from [35]. For the second
part of the lemma, assume that $\overline{\rho}\in\mathcal{S}$ and by
definition of a stationary point, $\overline{\rho}^{t+1}=\overline{\rho}^{t}$.
Further, by Lemma 2, we know that
$\sigma_{x_{i}}^{t+1}=\sigma_{x_{i}}^{*}=\sigma_{x_{i}}^{t}$ for all $t$. This
implies that $\mu^{t}_{x_{1}\cdots x_{n}}=\mu^{t+1}_{x_{1}\cdots x_{n}}$. In
particular,
$\operatorname{KL}(\mu^{*}\|\mu^{t})=\operatorname{KL}(\mu^{*}\|\mu^{t+1})$.
Yet, [35] implies that if $\mu^{t+1}\neq\mu^{t}$ then
$\operatorname{KL}(\mu^{*}\|\mu^{t+1})<\operatorname{KL}(\mu^{*}\|\mu^{t})$.
Hence, $\mu^{t+1}=\mu^{t}$ as required. ∎

###### Proof of Lemma 9.

We will analyze the transpose of the matrix in (5), assuming that
$J_{ij}=u_{j}$ for any $i\neq j$. Indeed, the original matrix is singular if
and only if its transpose is.

We would like to show that there is no nontrivial solution $a$ for $Ja=0$. We
have

$(Ja)_{i}=\sum_{j\neq i}a_{j}u_{j}+a_{i}(\sum_{j\neq
i}u_{j})=\sum_{j}a_{j}u_{j}+a_{i}(\sum_{j}u_{j}-2u_{i}).$

Substitute $s=\sum_{j}u_{j}$ and $u=\sum_{j}a_{j}u_{j}$, we have

$(Ja)_{i}=u+a_{i}(s-2u_{i}).$

To solve the system of equations $Ja=0$, we assume without loss of generality
that $u_{1}=\max_{j}u_{j}$ and divide into cases according to $u_{1}$. First,
assume that $u_{1}<s/2$. Then,

$(Ja)_{i}=u+a_{i}(s-2u_{i})=0$ (15)

implies

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

The equation $\sum_{i}u_{i}a_{i}=u$ implies

$\sum_{i}u_{i}a_{i}=\sum_{i}\frac{-uu_{i}}{s-2u_{i}}=u.$ (16)

Notice that $u\neq 0$. Assume towards contradiction that $u=0$. Then, we have

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

Dividing by $s-2u_{i}$ we get $a_{i}=0$ for all $i$. Since we look for
nontrivial solutions $a$ to $Ja=0$, we assume that $a\neq 0$ which implies
that $u\neq 0$. Dividing (16) by $u$ we get

$\sum_{i}\frac{-u_{i}}{s-2u_{i}}=1.$ (17)

By the assumption $u_{1}<s/2$ we have $s-2u_{i}\geq s-2u_{1}>0$. In
particular, the left hand side of (17) is negative while the right hand side
is positive, hence there is no solution! Next, assume that $u_{1}>s/2$. In
this case, we have $u_{i}<s/2$ for all $i\geq 2$, since $\sum_{i}u_{i}=s$.
Here, (17) is still valid, and is equivalent to

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

which is equivalent to

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

Here, we will show that the left hand side is strictly greater than the right
hand side, which implies that there is no equality. First, notice that for any
$i\geq 2$, $2u_{1}-s<s-2u_{i}$. Indeed, this follows from
$s=\sum_{j}u_{j}>u_{1}+u_{i}$, since all $u_{j}$ are positive and $n\geq 3$.
We derive that

$\frac{s-u_{1}}{2u_{1}-s}=\sum_{i\geq 2}\frac{u_{i}}{2u_{1}-s}>\sum_{i\geq
2}\frac{u_{i}}{s-2u_{i}}\enspace,$

which arrives at a contradiction. Lastly, assume that $u_{1}=s/2$. Since
$s=\sum_{i=1}^{n}u_{i}$ and $n\geq 3$, then for all $i\geq 2$ we have
$u_{i}<s/2$. Recall (15) which states that

$0=(Ja)_{i}=u+a_{i}(s-2u_{i}).$

Applying with $i=1$ we obtain

$u=0.$

For all $i\geq 2$ we have

$a_{i}(s-2u_{i})=0$

which implies that $a_{i}=0$ for $i\geq 2$. By definition of $u$ and by the
computations above,

$0=u=\sum_{i}a_{i}u_{i}=a_{1}u_{1}.$

Since $u_{1}>0$ we have

$a_{1}=0.$

We conclude that $a_{i}=0$ for all $i$ which implies that there is no
nontrivial solution for $Ja=0$, as required. ∎

##  Appendix B Proofs of Lemmas 4 and 5

###### Proof of Lemma 4.

By Lemma 16 we know that the only stationary point with some $\rho_{i}=0$ is
$(0,\ldots,0)$. By Lemma 22 we know that the only stationary points with some
$\rho_{i}=1$ are the $g^{i}$ for $i\in[n]$ (see the statement of Lemma 22 for
definitions). Finally, Lemma 6 implies that the only stationary point where
$\rho_{i}\in(0,1)$ for all $i$ is $\rho^{*}$. All these facts imply the
statement of the Lemma.

∎

###### Proof of Lemma 5.

By Lemma 17 we know that $\lim_{t\to\infty}\rho^{t}\neq\overline{0}$. By the
discussion after the statement of Theorem 4 we know that
$\lim_{t\to\infty}\rho^{t}\neq g^{i}$ for all $i$. Hence, we should have for
all $i$ $\lim_{t\to\infty}\rho_{i}^{t}\in(0,1)$.

∎

##  Appendix C Upper and Lower bounds for empirical EM iteration

This Section is devoted to proving that the finite sample iterates of EM are
upper and lower bounded with high probability. This fact will be used
repeatedly in the proof of Theorem 2, which will presented in later Sections.
We denote by $\mu_{\rho}$ the density of the distribution on leaves with
correlations $\rho$. The main Theorem that we prove in this Section is the
following.

######  Theorem 5.

Suppose that
$\min(\min_{i}\rho^{0}_{i},\min_{i}\rho^{*}_{i})\geq\alpha,1-\max(\max_{i}\rho^{0}_{i},\max_{i}\rho^{*}_{i})\geq\beta$,
where $\alpha,\beta\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(\alpha,\beta)^{2})$. Then, there are constants
$C(\alpha,\beta),C^{\prime}(\alpha,\beta)>0$ such that with probability at
least $1-\delta$, for all $t>0$, $i$ and $k=12$:

$\frac{C(\alpha,\beta)}{n^{k+2}}\leq\rho_{i}^{t}\leq
1-\frac{C^{\prime}(\alpha,\beta)}{n^{4k+9}}$

Theorem 5 says that if we initialize EM at a constant distance away from the
optimum, it will always remain in a bounded distance within that optimum.
Theorem 5 essentially follows directly by combining Lemmas 28 and 33. We will
break the proof of these two Lemmas into multiple lemmas over the next few
Sections. The final proof of Lemma 28 is in Section C.3 and the one for Lemma
33 is in Section C.4. In the next Section, we derive the precise formula for
the finite sample EM iterate.

###  C.1 Finite sample update rule for EM

To describe the EM update, we have the following analogue of Lemma 1 for the
sample EM:

######  Lemma 25.

Denote by $\hat{\mu}_{x}$ the uniform distribution over the $m$ samples. Let
$\mu^{t,^{\prime}}$ denote the joint distribution over $x_{1}\cdots x_{n},y$
such that

$\Pr_{\mu^{t,^{\prime}}}[x_{1},\cdots,x_{n},y]=\Pr_{\hat{\mu}_{x}}[x_{1},\cdots,x_{n}]\Pr_{\mu^{t}}[y\mid
x_{1},\dots,x_{n}].$

Then, for any $i$, we have that

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

The proof follows the same lines as the proof of Lemma 1, where the only
difference is that here we are considering the sample-EM. As a consequence, we
have the following analogue of Lemma 2:

######  Lemma 26.

For any $i$, denote

$\hat{\sigma}_{i}=\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left(x_{i}^{(k)}\right)^{2}}$

For any $i\neq j$, denote

$\hat{\alpha}_{ij}=\frac{1}{\hat{\sigma}_{i}\hat{\sigma}_{j}}\frac{1}{m}\sum_{k=1}^{m}x_{i}^{(k)}x_{j}^{(k)}\enspace.$

Denote by $\Delta^{t}_{ij}=\hat{\alpha}_{ij}-\rho_{i}\rho_{j}$. Then, for any
$t>0$ and any $i$:

$\sigma^{t}_{i}=\hat{\sigma}_{i},$
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]=\sigma^{t}_{i}\sigma^{t}_{y}\left(\lambda_{i}^{t}+\sum_{j\neq
i}\hat{\alpha}_{ij}\lambda_{j}^{t}\right)=\sigma^{t}_{i}\sigma^{t}_{y}\left(\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}^{t}\lambda_{j}^{t}\right)\enspace,$
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[y^{2}]=(\sigma_{y}^{t+1})^{2}=(\sigma^{t}_{y})^{2}\left(\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}\right)=(\sigma_{y}^{t})^{2}\left(1+\sum_{j\neq
k}\Delta_{ij}^{t}\lambda_{j}^{t}\lambda_{k}^{t}\right)$
$\rho_{i}^{t+1}=\frac{\lambda_{i}^{t}+\sum_{j\neq
i}\lambda_{j}^{t}\hat{\alpha}_{ij}}{\sqrt{\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}}}=\frac{\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}\lambda_{j}^{t}}{\sqrt{1+\sum_{j\neq
k}\Delta_{ij}\lambda_{j}^{t}\lambda_{k}^{t}}}\enspace.$ (18)

###### Proof.

The proof is similar to the proof of Lemma 2. First,
$\hat{\sigma}_{i}=\sigma^{t}_{i}$ follows directly from Lemma 1. Next, Using
Lemma 25 and Claim 1, we derive that

$\displaystyle\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mu^{t,^{\prime}}}[x_{i}y]=\operatorname*{\mathbb{E}}_{\hat{\mu}_{xo}}\left[\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[x_{i}y]\right]=\operatorname*{\mathbb{E}}_{\hat{\mu}_{x}}\left[x_{i}\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[y]\right]=\operatorname*{\mathbb{E}}_{\hat{\mu}_{x}}\left[x_{i}\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}x_{j}\right]$
$\displaystyle=\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}\operatorname*{\mathbb{E}}_{\hat{\mu}_{x}}\left[x_{i}x_{j}\right]=\sigma^{t}_{y}\sigma^{t}_{i}\lambda^{t}_{i}+\sum_{j\neq
i}\sigma^{t}_{y}\sigma^{t}_{i}\lambda^{t}_{j}\hat{\alpha}_{ij}=\sigma^{t}_{y}\sigma^{t}_{i}\left(\lambda^{t}_{i}+\sum_{j\neq
i}\lambda^{t}_{j}\hat{\alpha}_{ij}\right)\enspace.$

This concludes the first expression for
$\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]$. The second equality is
derived similarly to the proof of Lemma 2. Next, we compute the variance for
$y$, again, using Lemma 25 and Claim 1:

$\displaystyle\operatorname*{\mathbb{E}}_{\mu^{t+1}}[y^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mu^{t,^{\prime}}}[y^{2}]=\operatorname*{\mathbb{E}}_{\hat{\mu}_{x}}\left[\operatorname*{\mathbb{E}}_{\mu^{t}_{y\mid
x}}[y^{2}]\right]=\operatorname*{\mathbb{E}}_{\hat{\mu}_{x}}\left[\left(\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}x_{j}\right)^{2}\right]$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\sigma^{t}_{y}}{\sigma^{t}_{i}}\lambda^{t}_{i}\frac{\sigma^{t}_{y}}{\sigma^{t}_{j}}\lambda^{t}_{j}\operatorname*{\mathbb{E}}_{\hat{\mu}_{x}}\left[x_{i}x_{j}\right]=(\sigma^{t}_{y})^{2}\left(\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}\right)\enspace.$

This derives the first expression for the variance of $y$. The second
expression is derived similarly to its analogue in Lemma 2.

Lastly, the expression of $\rho^{t+1}_{i}$ is derived, by definition of
$\rho_{i}$,

$\rho^{t+1}_{i}=\frac{\operatorname*{\mathbb{E}}_{\mu^{t+1}}[x_{i}y]}{\sqrt{\operatorname{Var}_{\mu^{t+1}}[x_{i}]\operatorname{Var}_{\mu^{t+1}}[y]}},$

and by substituting the expressions for the covariance of $x_{i}$ and $y$, the
variance of $y$, and using that
$\operatorname{Var}_{\mu^{t+1}}[x_{i}]=\hat{\sigma}_{i}^{2}$. ∎

From Lemma 26, it follows that the convergence rate of the EM is not affected
by the variance of the nodes. In particular, the correlation parameters
$\rho^{t}_{i}$ are independent of these. Therefore, we will assume for
simplicity that $\sigma^{*}_{i}=1$ for all $i$.

###  C.2 Two correlations cannot be close to $1$

We will first be concerned with establishing that all $\rho_{i}$ remain
bounded away from $1$ in all iterations. Our first Lemma contributes in this
direction. It says that no $2$ coordinates $i,j$ can have $\rho_{i},\rho_{j}$
simultaneously close to $1$.

######  Lemma 27.

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 run using
these samples. Suppose $m=\Omega(\log(n/\delta))$. Then, with probability at
least $1-\delta$, there exists a constant $c=c(c_{1},c_{2})$ such that for all
$t$, there exists at most one $i\in[n]$ such that $\rho^{t}_{i}>1-c/(n^{2}).$

###### Proof.

We use the fact that EM always improves the value of the likelihood function.
We consider the likelihood of a given observation on the leaves as a function
of the standard deviations at the leaves $\sigma_{x_{i}}$ and the correlations
$\rho_{i}$ between $x_{i},y$. Let $\sigma_{x}$ be the vector of standard
deviations and $\rho$ the vector of correlations. The empirical likelihood
function can be written as

$L(\rho,\sigma_{x};x^{(1)},\ldots,x^{(k)})=\frac{1}{m}\sum_{k=1}^{m}\log\mu_{\rho,\sigma_{x}}(x^{(k)})$

From now on, we will omit the dependence on the samples
$x^{(1)},\ldots,x^{(k)}$ whenever it is implied. We have that

$\displaystyle L(\rho,\sigma_{x})$
$\displaystyle=\frac{1}{m}\sum_{k=1}^{m}\log\mu_{\rho,\sigma_{x}}(x^{(k)})$
$\displaystyle=-\frac{1}{2}\log\left(2\pi\left|\Sigma_{\rho,\sigma_{x}}\right|\right)-\frac{1}{2m}\sum_{k=1}^{m}(x^{(k)})^{\top}\Sigma_{\rho,\sigma_{x}}^{-1}x^{(k)}$
$\displaystyle=-\frac{1}{2}\log\left(2\pi\left|\Sigma_{\rho,\sigma_{x}}\right|\right)-\frac{1}{2}tr\left(\Sigma_{\rho,\sigma_{x}}^{-1}\hat{\Sigma}\right)$
(19)

where $\hat{\Sigma}$ is the empirical covariance matrix of the samples. Recall
the closed form expression for KL of Gaussians.

$KL(\mathcal{N}(0,\Sigma_{1})||\mathcal{N}(0,\Sigma_{2}))=\frac{1}{2}\left(\log\frac{|\Sigma_{2}|}{|\Sigma_{1}|}-n+tr(\Sigma_{2}^{-1}\Sigma_{1})\right)$

From this, we conclude that

$L(\rho,\sigma_{x})=-\frac{n}{2}-\frac{1}{2}\log\left(2\pi\left|\hat{\Sigma}\right|\right)-KL(\mathcal{N}(0,\hat{\Sigma})||\mathcal{N}(0,\Sigma_{\rho,\sigma_{x}}))$

Let us start by lower bounding $L(\rho^{0},\sigma_{x}^{0})$. We are going to
upper bound
$KL(\mathcal{N}(0,\hat{\Sigma})||\mathcal{N}(0,\Sigma_{\rho^{0},\sigma_{x}^{0}})))$.
The matrix $\Sigma_{\rho,\sigma_{x}}$ can be written as a sum of a rank $1$
matrix and a diagonal matrix. We will use this to evaluate determinants and
inverses of these matrices. Specifically, for any $\rho$, if $\sigma_{x}$ is
the all $1$’s vector, we have that

$\Sigma_{\rho,\sigma_{x}}=\begin{pmatrix}1-\rho_{1}^{2}&0&\ldots&0\\\
0&1-\rho_{2}^{2}&\ldots&0\\\ \vdots&\vdots&&\vdots\\\
0&0&\ldots&1-\rho_{n}^{2}\end{pmatrix}+\rho\rho^{\top}$ (20)

We will denote this diagonal matrix as $diag(1-\rho^{2})$ for convenience.
From now on, we will omit the dependence on $\sigma_{x}$ if we have unit
variances (which happens for $\rho^{0}$ and $\rho^{*}$ for example). Using the
Sherman-Morrison formula, we get that

$\Sigma_{\rho}^{-1}=diag(1-\rho^{2})^{-1}-\frac{diag(1-\rho^{2})^{-1}\rho\rho^{\top}diag(1-\rho^{2})^{-1}}{1+\rho^{\top}diag(1-\rho^{2})^{-1}\rho}$
(21)

We will first try to bound $tr(\Sigma_{\rho^{0}}^{-1}\Sigma_{\rho^{*}})$ and
then show that it is close to $tr(\Sigma_{\rho^{0}}^{-1}\hat{\Sigma})$ Thus,
after some algebraic manipulations, we have that

$\displaystyle tr(\Sigma_{\rho^{0}}^{-1}\Sigma_{\rho^{*}})$
$\displaystyle=n+\frac{\left(\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}\right)^{2}-\left(\sum_{i}\frac{\rho_{i}^{0}\rho_{i}^{*}}{1-(\rho_{i}^{0})^{2}}\right)^{2}+\sum_{i}\frac{(\rho_{i}^{0})^{2}(\rho_{i}^{*})^{2}}{(1-(\rho_{i}^{0})^{2})^{2}}-\sum_{i}\frac{(\rho_{i}^{0})^{4}}{(1-(\rho_{i}^{0})^{2})^{2}}}{1+\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}}$
$\displaystyle=n+\frac{\left(\sum_{i}\frac{(\rho_{i}^{0})(\rho_{i}^{0}-\rho_{i}^{*})}{1-(\rho_{i}^{0})^{2}}\right)\left(\sum_{i}\frac{(\rho_{i}^{0})(\rho_{i}^{0}+\rho_{i}^{*})}{1-(\rho_{i}^{0})^{2}}\right)+\sum_{i}\frac{(\rho_{i}^{0})^{2}((\rho_{i}^{*})^{2}-(\rho_{i}^{0})^{2})}{(1-(\rho_{i}^{0})^{2})^{2}}}{1+\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}}$

Now, notice that the function $x\mapsto x^{2}/(1-x^{2})$ is increasing. This
implies, using the assumption of the Lemma, that

$\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}\geq
n\frac{c_{1}^{2}}{1-c_{1}^{2}}$

Also, since the function $x\mapsto x/(1-x^{2})$ is increasing, this implies
that

$\sum_{i}\frac{(\rho_{i}^{0})(\rho_{i}^{0}+\rho_{i}^{*})}{1-(\rho_{i}^{0})^{2}}\leq
2n\frac{1-c_{2}}{1-(1-c_{2})^{2}}$

and

$\left|\sum_{i}\frac{(\rho_{i}^{0})(\rho_{i}^{0}-\rho_{i}^{*})}{1-(\rho_{i}^{0})^{2}}\right|\leq
2n\frac{1-c_{2}}{1-(1-c_{2})^{2}}$

Also, for all $i$ we have

$|(\rho_{i}^{*})^{2}-(\rho_{i}^{0})^{2}|=|\rho_{i}^{*}-\rho_{i}^{0}||\rho_{i}^{*}+\rho_{i}^{0}|\leq
2$

By monotonicity again, this implies

$\left|\sum_{i}\frac{(\rho_{i}^{0})^{2}((\rho_{i}^{*})^{2}-(\rho_{i}^{0})^{2})}{(1-(\rho_{i}^{0})^{2})^{2}}\right|\leq
2\sum_{i}\frac{(\rho_{i}^{0})^{2}}{(1-(\rho_{i}^{0})^{2})^{2}}\leq
2n\frac{(1-c_{2})^{2}}{(1-(1-c_{2})^{2})^{2}}$

Putting all these facts together, we conclude that there exists a constant
$C=C(c_{1},c_{2})$, such that

$\left|\frac{\left(\sum_{i}\frac{(\rho_{i}^{0})(\rho_{i}^{0}-\rho_{i}^{*})}{1-(\rho_{i}^{0})^{2}}\right)\left(\sum_{i}\frac{(\rho_{i}^{0})(\rho_{i}^{0}+\rho_{i}^{*})}{1-(\rho_{i}^{0})^{2}}\right)+\sum_{i}\frac{(\rho_{i}^{0})^{2}((\rho_{i}^{*})^{2}-(\rho_{i}^{0})^{2})}{(1-(\rho_{i}^{0})^{2})^{2}}}{1+\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}}\right|\leq
Cn$ (22)

Now, let’s focus on $tr(\Sigma_{\rho^{0}}^{-1}\hat{\Sigma})$. By standard
Chernoff bounds, we have that with probability at least $1-\delta$, for all
$i,j$

$\left|(\Sigma_{\rho^{*}})_{ij}-\hat{\Sigma}_{ij}\right|=O\left(\sqrt{\frac{\log(n/\delta)}{m}}\right):=\eta$

By assumption on the number of samples $m$, $\eta=O(1)$. We have

$tr\left(\Sigma_{\rho^{0}}^{-1}(\hat{\Sigma}-\Sigma_{\rho^{*}})\right)=\sum_{i,j}(\Sigma_{\rho^{0}}^{-1})_{ij}\left((\Sigma_{\rho^{*}})_{ij}-\hat{\Sigma}_{ij}\right)$

Hence, all we have to do is bound the entries of $\Sigma_{\rho^{0}}^{-1}$. For
this, we can use the Sherman-Morrison formula, which we also used earlier.
Let’s start with a non-diagonal element $i\neq j$. Then, the formula gives

$\left|(\Sigma_{\rho^{0}})_{ij}\right|=\frac{\frac{\rho^{0}_{i}}{1-(\rho^{0}_{i})^{2}}\frac{\rho^{0}_{j}}{1-(\rho^{0}_{j})^{2}}}{1+\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}}\leq\frac{1}{c_{2}^{2}}$

For $i=j$, we have

$\left|(\Sigma_{\rho^{0}})_{ii}\right|=\left|\frac{1}{1-(\rho^{0}_{i})^{2}}-\frac{\left(\frac{\rho^{0}_{i}}{1-(\rho^{0}_{i})^{2}}\right)^{2}}{1+\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}}\leq\frac{1}{c_{2}^{2}}\right|\leq\frac{1}{c_{2}}+\frac{1}{c_{2}^{2}}$

Hence, with probability at least $1-\delta$

$\left|tr\left(\Sigma_{\rho^{0}}^{-1}(\hat{\Sigma}-\Sigma_{\rho^{*}})\right)\right|\leq
Cn^{2}\eta\leq C^{\prime}n^{2}$ (23)

where $C$ is some constant. Now, let’s calculate the determinant. We use the
matrix determinant lemma to compute $|\Sigma_{\rho}|$.

$|\Sigma_{\rho}|=(1+\rho^{\top}diag(1-\rho^{2})^{-1}\rho)|diag(1-\rho^{2})|=(1+\sum_{i}\frac{\rho_{i}^{2}}{1-\rho_{i}^{2}})\prod_{i}(1-\rho_{i}^{2})$

This gives us

$\log\frac{|\Sigma_{\rho^{0}}|}{|\Sigma_{\rho^{*}}|}=\log\frac{1+\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}}{1+\sum_{i}\frac{(\rho_{i}^{*})^{2}}{1-(\rho_{i}^{*})^{2}}}+\sum_{i}\log\frac{1-(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{*})^{2}}$

The function $x\mapsto\log(1-x^{2})$ is decreasing, hence we have

$\sum_{i}\log\frac{1-(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{*})^{2}}\leq
n\log\frac{1-c_{1}^{2}}{c_{2}}$

We also have

$\sum_{i}\frac{(\rho_{i}^{0})^{2}}{1-(\rho_{i}^{0})^{2}}\leq n\frac{1}{c_{2}}$

Finally

$\sum_{i}\frac{(\rho_{i}^{*})^{2}}{1-(\rho_{i}^{*})^{2}}\geq Cn$

It follows that there exists a constant $C^{\prime}=C^{\prime}(M,\rho^{*})$,
such that

$\left|\log\frac{|\Sigma_{\rho^{0}}|}{|\Sigma_{\rho^{*}}|}\right|\leq
C^{\prime}n$ (24)

However, in the expression we have $\hat{\Sigma}$ instead of $\Sigma^{*}$. We
use the property that

$\frac{\partial\log|A|}{\partial A}=A^{-1}$

We already showed that the entries of $\Sigma_{\rho}^{-1}$ are bounded if
$\rho$ is upper and lower bounded by constants. Using this and Taylor’s
Theorem, we get

$\left|\log\frac{|\Sigma_{\rho^{*}}|}{|\hat{\Sigma}|}\right|\leq Cn^{2}$ (25)

for some constant $C$.

Using inequalities (22) and (24) together with the expression of KL, we
conlcude that

$KL(\mathcal{N}(0,\Sigma_{\rho^{*}})||\mathcal{N}(0,\Sigma_{\rho^{0}}))\leq
Kn$

where $K=K(\rho^{*})$. Also, using this result and inequalities (25) and (23)
we get

$KL(\mathcal{N}(0,\hat{\Sigma})||\mathcal{N}(0,\Sigma_{\rho^{0}}))\leq
K^{\prime}n^{2}$

Overall, by equation(C.2) we get that

$L(\rho^{0})\geq-\frac{n}{2}-\frac{1}{2}\log\left(2\pi\left|\hat{\Sigma}\right|\right)-K^{\prime}n^{2}$

for some $K^{\prime}=K^{\prime}(c_{1},c_{2},\rho^{*})$.

Now, suppose for some iteration $t$ there exist two indices $i,j$ with
$\rho_{i}^{t}>1-\epsilon,\rho_{j}^{t}>1-\epsilon$, where $\epsilon$ will be
determined in the sequel. Now, let us upper bound $L(\rho^{t})$. By KL
subadditivity, we have

$\displaystyle L(\rho^{t},\sigma_{x}^{t})$
$\displaystyle=-\frac{n}{2}-\frac{1}{2}\log\left(2\pi\left|\hat{\Sigma}\right|\right)-KL(\mathcal{N}(0,\hat{\Sigma})||\mathcal{N}(0,\Sigma_{\rho^{t},\sigma_{x}^{t}}))$
$\displaystyle-\frac{n}{2}-\frac{1}{2}\log\left(2\pi\left|\hat{\Sigma}\right|\right)-KL(\mathcal{N}(0,\hat{\Sigma}_{x_{i},x_{j}})||\mathcal{N}(0,(\Sigma_{\rho^{t},\sigma_{x}^{t}})_{x_{i},x_{j}}))$

where in the last equation we are comparing the marginals of the distributions
on $x_{i},x_{j}$. The marginal distribution of $x_{i},x_{j}$ is a gaussian
with zero mean. First, we will analyze the ideal situation where we have
$\Sigma^{*}$ instead of $\hat{\Sigma}$. Using the closed form of the KL
divergence between two Gaussians, we obtain:

$\displaystyle
KL(\mathcal{N}(0,\Sigma^{*}_{x_{i},x_{j}})||\mathcal{N}(0,(\Sigma_{\rho^{t},\sigma_{x}^{t}})_{x_{i},x_{j}}))$
$\displaystyle=\frac{1}{2}\left(\log\frac{1-(\rho_{i}^{t}\rho_{j}^{t})^{2}}{1-(\rho_{i}^{*}\rho_{j}^{*})^{2}}-2+\frac{1}{(1-(\rho_{i}^{t}\rho_{j}^{t})^{2}}tr\left(\begin{pmatrix}1&-\rho_{i}^{t}\rho_{j}^{t}\\\
-\rho_{i}^{t}\rho_{j}^{t}&1\end{pmatrix}\begin{pmatrix}1&\rho_{i}^{*}\rho_{j}^{*}\\\
\rho_{i}^{*}\rho_{j}^{*}&1\end{pmatrix}\right)\right)$
$\displaystyle=\frac{1}{2}\left(\log\frac{1-(\rho_{i}^{t}\rho_{j}^{t})^{2}}{1-(\rho_{i}^{*}\rho_{j}^{*})^{2}}-2+2\frac{1-\rho_{i}^{t}\rho_{j}^{t}\rho_{i}^{*}\rho_{j}^{*}}{1-(\rho_{i}^{t}\rho_{j}^{t})^{2}}\right)$

Then,

$KL(\mathcal{N}(0,\Sigma^{*}_{x_{i},x_{j}})||\mathcal{N}(0,(\Sigma_{\rho^{t},\sigma_{x}^{t}})_{x_{i},x_{j}}))\geq\frac{1}{2}\left(\log(1-(\rho_{i}^{t}\rho_{j}^{t})^{2})-2+2\frac{1-\rho_{i}^{*}\rho_{j}^{*}/4}{1-(\rho_{i}^{t}\rho_{j}^{t})^{2}}\right)$

Now, for any constant $c>0$, consider the function $f(x)=x(\log x+c/x)$. This
is a continuous function on $(0,1)$ and it is easy to see that it is
decreasing for $x<1/e$. Let $x_{0}$ be a small enough constant such that
$x_{0}\log x_{0}+c>c/2$. Then, for $x<x_{0}$

$f(x)\geq f(x_{0})\implies\log x+c/x\geq\frac{c/2}{x}$

Now let $c=2(1-\rho_{i}^{*}\rho_{j}^{*}/4)$. If we set
$\epsilon=c^{\prime}/(n^{2})$ for some suitable constant $c^{\prime}$, then we
have that

$1-(\rho_{i}^{t}\rho_{j}^{t})^{2}<x_{0}$

and

$KL(\mathcal{N}(0,\Sigma^{*}_{x_{i},x_{j}})||\mathcal{N}(0,(\Sigma_{\rho^{t},\sigma_{x}^{t}})_{x_{i},x_{j}}))>(K^{\prime}+K^{\prime\prime})n^{2}$

where $K^{\prime\prime}$ is a constant that will be determined now. Using the
exact same arguments as in the case of $\rho^{0}$, we can show that

$\left|KL(\mathcal{N}(0,\hat{\Sigma}_{x_{i},x_{j}})||\mathcal{N}(0,(\Sigma_{\rho^{t},\sigma_{x}^{t}})_{x_{i},x_{j}}))-KL(\mathcal{N}(0,\Sigma^{*}_{x_{i},x_{j}})||\mathcal{N}(0,(\Sigma_{\rho^{t},\sigma_{x}^{t}})_{x_{i},x_{j}}))\right|\leq
C\eta\leq K^{\prime\prime}$

for some constant $C$. It follows that

$L(\rho^{t},\sigma_{x}^{t})<-\frac{n}{2}-\frac{1}{2}\log\left(2\pi\left|\hat{\Sigma}\right|\right)-K^{\prime}n^{2}<L(\rho^{0})$

This is a contradiction, since the likelihood value increases at each step of
EM. This gives us the desired result.

∎

###  C.3 No correlation can be too close to $1$

In the previous Section, we showed that two corrrelations cannot be close to
$1$ at the same time. In this Section, building on this result, we show that
in fact no correlation can be too close to $1$. Hence, each $\rho_{i}$ is
upper bounded at all iterations of the algorithm. This is the topic of the
following Lemma:

######  Lemma 28.

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,
with probability at least $1-\delta$, for all $i$ and for all $t$,
$\rho_{i}^{t}\leq 1-C^{\prime\prime}/n^{4k+9}$, where $C^{\prime\prime}$ is an
absolute constant and $k\geq 12$.

To prove it, we will essentially prove that no $\rho_{i}$ will ever get really
close to $1$. The proof will be similar to the one that established divergence
from the saddle points at the boundary. We start by stating a direct Corollary
of Lemma 27.

######  Corollary 1.

Suppose that $\min_{i}\rho^{0}_{i}\geq c_{1},1-\max_{i}\rho^{0}_{i}\geq
c_{2}$, where $c_{1},c_{2}\in(0,1)$ are constants. Suppose we run EM (18) with
$m=\Omega(\log(n/\delta))$ samples. Then, with probability at least
$1-\delta$, we have the following: if for some $t$ we have
$\rho_{1}^{t}>1-c/n^{2}$, then for all $i\neq 1$ we have $\rho_{i}^{t}\leq
1-c/n^{2}$, where $c$ is the constant of Lemma 27.

Our strategy now will be the following: we want to show that $\rho_{1}$ will
not be very close to $1$, without loss of generality. First of all, we want to
argue that if it comes close to $1$, it will immediately start moving away. We
do this by showing that after one iteration of EM, the errors of the others
will be comparable to the error of $\rho_{1}$. We showed a similar claim in
the proof of divergence from stationary points. The difference here is that
the errors of the other $\rho_{i}$ can be close to $1$, while in the original
proof they were assumed to lie in some ball around the fixpoint. Hence, we
prove the following Lemma.

######  Lemma 29.

Suppose that for some $t$ we have $\rho_{i}^{t}\leq\alpha$ for all $i\neq 1$
and $\rho_{1}^{t}>\beta$, for some $\alpha,\beta\in(0,1)$. Also, suppose
$\hat{\alpha}_{ij}\in[0,1]$ for all $i,j$. Define

$R=R(\alpha,\beta,n):=n^{2}\frac{1-\beta}{\beta^{4}(1-\alpha)^{2}}+\frac{n}{\beta^{2}(1-\alpha)}$
(26)

and assume that $(1-\beta)R\leq 1/2$. Then, for all $i\neq 1$

$|\rho_{i}^{t+1}-\hat{\alpha}_{1i}|\leq
C\frac{1+\frac{2n}{1-\alpha}+R}{1-\left(1+\frac{2n}{1-\alpha}\right)\frac{n(1-\beta)}{\beta^{2}(1-\alpha)}-Cn^{2}\frac{(1-\beta)}{\beta^{4}(1-\alpha)^{2}}-C\frac{n(1-\beta)R}{\beta^{2}(1-\alpha)}}(1-\rho_{1}^{t+1})$

where $C$ is some absolute constant(it is assumed that $\alpha,\beta$ are such
that the quantity in the denominator is positive).

The first step to proving this Lemma will be to show that if all $\rho_{i}$
are bounded away from $1$ except $\rho_{1}$, then $\lambda_{i}$ will be small
for $i\neq 1$. This is the content of the following Lemma.

######  Lemma 30.

Suppose for some $\rho$ we have $\rho_{i}\leq\alpha$ for all $i\neq 1$ and
$\rho_{1}>\beta$, for some $\alpha,\beta\in(0,1)$.Then,

$\lambda_{1}>\frac{\rho_{1}}{1+2n\frac{1-\rho_{1}}{1-\alpha}}$

and

$\lambda_{i}\leq\frac{2(1-\rho_{1})}{\beta^{2}(1-\alpha)}$

for all $i\neq 1$.

###### Proof.

We have

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

For $i\neq 1$, this implies

$\lambda_{i}\leq\frac{1}{\sum_{j\neq
i}\frac{\rho_{j}^{2}(1-\rho_{i}^{2})}{1-\rho_{j}^{2}}}\leq\frac{1-\rho_{1}^{2}}{\rho_{1}^{2}(1-\rho_{i}^{2})}$

We have $1-\rho_{1}^{2}=(1-\rho_{1})(1+\rho_{1})<2(1-\rho_{1})$ and
$1-\rho_{i}^{2}=(1-\rho_{i})(1+\rho_{i})\geq 1-\alpha$. This gives

$\lambda_{i}\leq\frac{2(1-\rho_{1})}{\beta^{2}(1-\alpha)}$

We also have

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

We have that

$\sum_{j\neq 1}\frac{\rho_{j}^{2}(1-\rho_{1}^{2})}{1-\rho_{j}^{2}}\leq
2n\frac{1-\rho_{1}}{1-\alpha}\implies\lambda_{1}\geq\frac{\rho_{1}}{1+2n\frac{1-\rho_{1}}{1-\alpha}}$

∎

We are now ready to prove Lemma 29.

###### Proof of Lemma 29.

We will first prove that

$|\rho_{i}^{t+1}-\hat{\alpha}_{1i}|\leq C(\alpha,\beta)|\rho_{1}^{t}-1|$ (27)

for some constant $C(\alpha,\beta)$ that will be specified in the sequel. We
have that

$|\rho_{i}^{t+1}-\hat{\alpha}_{1i}|=\left|\frac{\rho_{i}^{t}+\sum_{j\neq
i}(\hat{\alpha}_{ij}-\rho_{i}^{t}\rho_{j}^{t})\lambda_{j}^{t}}{\sqrt{1+\sum_{j\neq
k}\lambda_{j}^{t}\lambda_{k}^{t}(\rho_{j}^{*}\rho_{k}^{*}-\rho_{j}^{t}\rho_{k}^{t})}}-\hat{\alpha}_{1i}\right|$

As usual, denote $\Delta_{ij}^{t}=\hat{\alpha}_{ij}-\rho_{i}^{t}\rho_{j}^{t}$.
Also, let

$U^{t}:=\sum_{j\neq
k}\lambda_{j}^{t}\lambda_{k}^{t}(\hat{\alpha}_{jk}-\rho_{j}^{t}\rho_{k}^{t})$

Hence, we can write

$\displaystyle|\rho_{i}^{t+1}-\hat{\alpha}_{1i}|$
$\displaystyle=\left|\frac{\rho_{i}^{t}+\sum_{j\neq
i}\Delta_{ij}^{t}\lambda_{j}^{t}-\hat{\alpha}_{1i}\sqrt{1+U^{t}}}{\sqrt{1+U^{t}}}\right|$
$\displaystyle=\left|\frac{\rho_{i}^{t}+\lambda_{1}^{t}(\hat{\alpha}_{1i}-\rho_{i}^{t}\rho_{1}^{t})-\hat{\alpha}_{1i}\sqrt{1+U^{t}}+\sum_{j\neq
i,1}\Delta_{ij}^{t}\lambda_{j}^{t}}{\sqrt{1+U^{t}}}\right|$
$\displaystyle=\left|\frac{(\lambda_{1}-\sqrt{1+U^{t}})(\hat{\alpha}_{1i}-\rho_{i}^{t}\rho_{1}^{t})+\rho_{i}^{t}(1-\rho_{1}^{t}\sqrt{1+U^{t}})+\sum_{j\neq
i,1}\Delta_{ij}^{t}\lambda_{j}^{t}}{\sqrt{1+U^{t}}}\right|$

Let’s start by bounding $U^{t}$. Using lemma 30 have that for $j,k\neq 1$:

$|\lambda_{j}^{t}\lambda_{k}^{t}\Delta_{jk}^{t}|\leq
2\left(\frac{2(1-\rho_{1}^{t})}{\beta^{2}(1-\alpha)}\right)^{2}$

where we have used the fact that $\hat{\alpha}_{ij}\leq 1$. If $j=1$ then

$|\lambda_{1}^{t}\lambda_{k}^{t}(\hat{\alpha}_{1k}-\rho_{1}^{t}\rho_{k}^{t})|\leq
2\frac{2(1-\rho_{1}^{t})}{\beta^{2}(1-\alpha)}$

Hence, we conclude that

$|U^{t}|\leq
n^{2}\frac{8(1-\rho_{1}^{t})^{2}}{\beta^{4}(1-\alpha)^{2}}+4n\frac{1-\rho_{1}^{t}}{\beta^{2}(1-\alpha)}$

By Assumption(26) we have that the right hand side of the last inequality is
$<1/2$. This gives, by a simple Taylor approximation, that

$|\sqrt{1+U^{t}}-1|\leq C|U^{t}|$

for some constant $C$. Hence,

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

We also have

$\displaystyle|1-\rho_{1}^{t}\sqrt{1+U^{t}}|$ $\displaystyle\leq
1-\rho_{1}^{t}+\rho_{1}^{t}|1-\sqrt{1+U^{t}}|\leq
1-\rho_{1}^{t}+Cn^{2}\frac{8(1-\rho_{1}^{t})^{2}}{\beta^{4}(1-\alpha)^{2}}+4Cn\frac{1-\rho_{1}^{t}}{\beta^{2}(1-\alpha)}$

Lastly, we have

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

Hence,

$\displaystyle|\rho_{i}^{t+1}-\hat{\alpha}_{1i}|$
$\displaystyle\leq\frac{\left(2+\frac{2n}{1-\alpha}\right)(1-\rho_{1}^{t})+Cn^{2}\frac{8(1-\rho_{1}^{t})^{2}}{\beta^{4}(1-\alpha)^{2}}+4Cn\frac{1-\rho_{1}^{t}}{\beta^{2}(1-\alpha)}+4n\frac{1-\rho_{1}^{t}}{\beta^{2}(1-\alpha)}}{\sqrt{1-n^{2}\frac{8(1-\rho_{1}^{t})^{2}}{\beta^{4}(1-\alpha)^{2}}-4n\frac{1-\rho_{1}^{t}}{\beta^{2}(1-\alpha)}}}$
$\displaystyle\leq
C(1-\rho_{1}^{t})\left(1+\frac{2n}{1-\alpha}+n^{2}\frac{1-\beta}{\beta^{4}(1-\alpha)^{2}}+\frac{n}{\beta^{2}(1-\alpha)}\right)$

for some constant $C$, since we have assumed (26). If we set $C(\alpha,\beta)$
equal to the multiplier of $1-\rho_{1}^{t}$, we have obtained (27). The second
step is to show that

$1-\rho_{1}^{t+1}\geq K(\alpha,\beta)(1-\rho_{1}^{t})$ (28)

Inequalities (27) and (28) together give us the desired result. We have that

$\displaystyle\rho_{1}^{t+1}$ $\displaystyle=\frac{\rho_{1}^{t}+\sum_{j\neq
1}(\hat{\alpha}_{1j}-\rho_{1}^{t}\rho_{j}^{t})\lambda_{j}^{t}}{\sqrt{1+\sum_{j\neq
k}\lambda_{j}^{t}\lambda_{k}^{t}(\hat{\alpha}_{jk}-\rho_{j}^{t}\rho_{k}^{t})}}$

First of all, by Taylor we have that if $|x|\leq 1/2$

$(1+x)^{-1/2}\leq 1-\frac{x}{2}+cx^{2}$

We have already shown that $|U^{t}|$ is smaller than a constant (using also
assumption (26)). This gives

$\displaystyle\rho_{1}^{t+1}$ $\displaystyle\leq\left(\rho_{1}^{t}+\sum_{j\neq
1}(\hat{\alpha}_{1j}-\rho_{1}^{t}\rho_{j}^{t})\lambda_{j}^{t}\right)\left(1-\frac{U^{t}}{2}+c|U^{t}|^{2}\right)$
$\displaystyle=\rho_{1}^{t}+\sum_{j\neq
1}(\hat{\alpha}_{1j}-\rho_{1}^{t}\rho_{j}^{t})\lambda_{j}^{t}-\rho_{1}^{t}\lambda_{1}^{t}\sum_{j\neq
1}(\hat{\alpha}_{1j}-\rho_{1}^{t}\rho_{j}^{t})\lambda_{j}^{t}-\frac{\rho_{1}^{t}}{2}\sum_{j\neq
k\neq
1}\Delta_{ij}^{t}\lambda_{j}^{t}\lambda_{k}^{t}-\frac{U^{t}}{2}\sum_{j\neq
1}\Delta_{1j}^{t}\lambda_{j}^{t}$
$\displaystyle\quad\quad\quad+c|U^{t}|^{2}(\rho_{1}^{t}+\sum_{j\neq
1}\Delta_{1j}^{t}\lambda_{j}^{t})$
$\displaystyle\leq\rho_{1}^{t}+(1-\rho_{1}^{t}\lambda_{1}^{t})\sum_{j\neq