In order for a quartet to change topology during some epoch, at least one of it's leaves should be moved to some different position.
By Observation <ref> we know that a leaf is moved at most $\lceil D/2\rceil$ times in total. Hence, a quartet changes topology at most $4\lceil D/2\rceil$ times in total.

\sum_{s= 1}^{M'}  |U_{s}|  \leq {n \choose 4} 2D \leq Dn^4

Combining everything together, we get

\sum_{x \in \{-1,1\}^n} \lp|f_x^{T^{m}\setminus\{w,z,y,u\}}(\alpha^{wzyu})\rp| \leq
\sum_{x \in \{-1,1\}^n} f_x^{G_{m}^0}(\alpha^{wzyu}) + \frac{\epsilon}{Dn^4} Dn^4 = 1 + \epsilon

This holds for all $\{w,z,y,u\} \in U_{m}$. Hence, by using (<ref>) we get

\begin{align*}
\sum_{x \in \{-1,1\}^n} \lp|f_x^{T^{m+1}}(\alpha) - f_x^{T^{m}}(\alpha)\rp|
&\leq  \frac{\epsilon}{2Dn^4} \sum_{\{w,z,y,u\} \in U_{m}} \lp|f_x^{T^{m}\setminus\{w,z,y,u\}}(\alpha^{wzyu})\rp| \\
&\leq \frac{\epsilon}{2Dn^4} |U_{m}|(1 + \epsilon) \leq \frac{|U_{m}|\epsilon}{Dn^4}
\end{align*}

since $\epsilon \leq 1$.
This is the inductive claim that we wanted to prove.

We are now ready to conclude the proof of Theorem <ref>. To do it, we simply use Lemma <ref> to transition from $T$ to $\hat{T}$. Then, we use the bound for the fixed topology to change $\alpha$ to $\hat{\alpha}$.

We can assume without loss of generality that
$\hat{T}$ has a smaller diameter than $T$, otherwise we just reverse the roles of $T,\hat{T}$. We run Algorithm <ref> with input $T,\hat{T},\alpha$, which produces a sequence $T = T^0 , T^2, \ldots, T^M = \hat{T}$, where each element of the sequence corresponds to some move.
We have that

\begin{align}\label{eq:tv_bound}
TV(\mu,\hat{\mu}) &= \sum_{x \in \{-1,1\}^n} \lp|f_x^T(\alpha) - f_x^{\hat{T}}(\hat{\alpha})\rp|\nonumber\\
&\leq \sum_{x \in \{-1,1\}^n} \lp|f_x^T(\alpha) - f_x^{\hat{T}}(\alpha)\rp| +
\sum_{x \in \{-1,1\}^n} \lp|f_x^{\hat{T}}(\alpha) - f_x^{\hat{T}}(\hat{\alpha})\rp|
\end{align}

Define $\epsilon' = 40 Dn^5 \epsilon$.
Let us divide into cases.

Case 1: Suppose $\epsilon' < 1$.
Then, the first term of the RHS of (<ref>) can be bounded using the successive steps of the interpolation process. In particular, since $\epsilon = \epsilon'/(40Dn^5)$, we can apply Lemma <ref> to get

\begin{align*}
\sum_{x \in \{-1,1\}^n} \lp|f_x^T(\alpha) - f_x^{\hat{T}}(\alpha)\rp| \leq
\sum_{m = 1}^M \sum_{x \in \{-1,1\}^n}  \lp|f_x^{T^m}(\alpha) - f_x^{T^{m-1}}(\alpha)\rp|
\leq \sum_{m = 1}^M \frac{|U_m|\epsilon'}{Dn^4}
\end{align*}

By the proof of Lemma <ref>, this implies that

\sum_{x \in \{-1,1\}^n} \lp|f_x^T(\alpha) - f_x^{\hat{T}}(\alpha)\rp| \leq \frac{\epsilon'}{Dn^4} Dn^4 = \epsilon' = 40Dn^5\epsilon

As for the second term of the RHS of (<ref>), it is essentially the difference when we substitute $\hat{\alpha}$ with $\alpha$ in the fixed topology $\hat{T}$. Hence, we can directly apply Theorem <ref> to get

\sum_{x \in \{-1,1\}^n} \lp|f_x^{\hat{T}}(\alpha) - f_x^{\hat{T}}(\hat{\alpha})\rp|  \leq 2n^2\epsilon

Overall, this gives us

TV(\mu,\hat{\mu}) \leq 42Dn^5 \epsilon

which proves inequality (<ref>) in that case.

Case 2: Assume $\epsilon' \geq 1$. Then,

TV(\mu,\hat{\mu}) \leq 1 \leq 40Dn^5 \epsilon

which means that (<ref>) trivially holds in that case too.
The proof is now complete.

§ PROOF OF THEOREM <REF> (UNKNOWN TOPOLOGY)

§.§ Outline

In this section, we will present an algorithm that takes samples from the leaves of some tree Ising model with tree $T^*$ and weight $\theta^*$ and estimates a topology $\hat T$ together with weights on the edges, so that the distributions on the leaves of $T$ and $\hat T$ are $\epsilon$-close in TV distance.
The number of samples will be polynomial in $n$ and $1/\epsilon$.

We will use the results in [Daskalakis et al., 2009] about learning phylogenetic trees without assuming any upper/lower bounds on the edge weights.
We will show how we can use the guarantees of this prior work to obtain an algorithm for finding a good enough topology. Before explaining the result formally, we first want to give an intuition. We discuss how the output might be different from the original tree.
Firstly, without sufficient samples, it is impossible to determine the existence of edges that are far away from leaves. In such cases, the algorithm of [Daskalakis et al., 2009] will omit those edges and output a forest, as shown in Figure <ref>.

A forest that is created by deleting edges: the true tree contains all the solid and dashed edges. Yet, the algorithm of [Daskalakis et al., 2009] might not be able to identify some of the edges because they do not sufficiently correlate with the leaves, and so it will return a forest. In the example here, the forest is obtained from the original tree by removing the dashed edges. The three connected components of the output forest are colored red, blue and green.

Secondly, the algorithm may fail to split the tree in a topologically sensible way. This means that it will return a forest, yet, in contrast with the example in Figure <ref>, it is impossible to obtain this forest by cutting some edges in the ground truth tree.
Still, the topology within each connected component in this forest is preserved,
as illustrated in Figure <ref> (a)-(b).
After splitting the tree into two subtrees, those subtrees might contain some internal nodes of degree $2$. Such nodes cannot be identified from the leaves, and they will be contracted, as shown in Figure <ref> (c).

Splitting a tree into subtrees in a more complicated  fashion: In (a), the true tree contains both the solid and dashed edges. Yet, the algorithm might not identify completely the topology. Instead it will return two subtrees. Yet, the subtrees are not topologically sensible: one tree will contain the leaves $\{1,2,3,5\}$ and the other will contain $\{4,6,7,8\}$. The red edges correspond to the first tree, the blue edges to the second tree, while the dashed edges are shared by both trees. In figure (b), we split the original tree into the two subtrees, one containing the red and dashed edges and the other the blue and dashed edges. Notice that in Figure (b), the nodes labeled $a$-$f$ have degree $2$. Information theoretically, it is impossible to identify hidden nodes of degree $2$. Indeed, the same leaf distribution is obtained by removing each of these nodes, connecting its neighbors, and adjusting the weight of the new edges. Hence, the output of the algorithm will not have degree-$2$ nodes: instead, the transformation described above, that removes degree-2 nodes, will be performed. In (c) we demonstrate the result of removing such degree-$2$ nodes.

The two transformations that are applied to a tree in Figure <ref> and Figure <ref> can be viewed as a single transformation: separating the tree into subtrees, while preserving the topology within each subtree. This can be seen in Figure <ref>.

Separating a tree into multiple subtrees: In (a), the original tree contains all solid, dashed and dotted edges. It is split by the algorithm to three subtrees. The first subtree contains leaves $\{1,2,3\}$ and the red and dashed edges. The second subtree contains $\{4,5,6\}$ and the blue and dashed edges. The third contains $\{7,8\}$ and the green edges. Notice that the dashed purple edge is contained in two trees, while the dotted black edge is contained in no tree. Notice that the first and second subtrees intersect while the third subtree is disjoint from the other subtrees. In (b) we see the output of the algorithm.

Yet, the algorithm of [Daskalakis et al., 2009] might not be able to tell the exact topology within each subtree. In this case, the output will just contract some of the internal edges of this subtree. See Figure <ref> (a)-(c) for an example of a contracted subtree. In Figure <ref> (d) we depict some of the possible topologies that the algorithm could have confused between, which led to contracting a specific edge.

An example of edge contraction. In (a), we see the original tree. In (b), the algorithm splits the tree into two subtrees. Yet, the algorithm could not figure exactly the topology of the left subtree. Instead, it contracts the dashed edge, and the result is shown in (c). The reason for the contraction is: the algorithm could not tell the true topology. In (d), we show multiple topologies that the algorithm might confuse between, leading it to contract the edge. These are labeled Option 1-3.

Before we give the formal proof, let us give an imprecise intuition of the approach.
In particular, we show how to compare between the output of the algorithm and the true topology. For the simple case where the output is obtained from the true tree by only deleting edges, these edges are “distant” from the leaves, and so they cannot influence the leaf distribution significantly. Thus, it suffices to study the more complicated case where the subtrees are not obtained by simply cutting edges from the true tree.
Here, we first compare the true tree to a tree where all edges that appear in two different subtrees have been contracted, as shown in Figure <ref> (b). In the next step, each edge corresponds only to one subtree, and we can detach the different subtrees, as shown in Figure <ref> (c). Lastly, we can reconstruct the edges that were previously contracted, as shown in Figure <ref> (d).

Analyzing the difference between the true topology and the output of the algorithm. In (a), the true tree contains the union of solid and dashed lines. Yet, the algorithm splits the tree into two subtrees, with leaves $\{1,2,5,6\}$ and $\{3,4,7,8\}$. In (d), we can see the output of the algorithm. In order to compare between the true and output topologies, we construct two auxiliary forests: In (b), we contract all the edges that are shared between the two subtree. In this example, this amounts to contracting the dashed edge. Then, in (c), we split the different subtrees. In (d), we reconstruct the edge that was previously contracted. Yet, we reconstruct this edge separately for each subtree.

We can bound the total variation distance for each of these steps using the following guarantees:
(1)  edges that appear in multiple subtrees have weight close to $1$. Hence, contracting them, which is equivalent to changing their weight to $1$, does not influence significantly the total variation distance. (2) Leaves of different trees have a small correlation. Hence, detaching the different subtrees does not incur a high cost in total variation.

§.§ Definitions and probabilistic lemmas

We begin with some notations that are specific for this section: given a tree $T=(V,E)$ with weights $\theta_e$ on the edges $e\in E$, denote the resulting distribution over the values $x=(x_1,\dots,x_n)$ on the leaves by $\Pr_{T,\theta}[x]$. The total variation distance between two leaf-distributions of two models, $(T,\theta)$ and $(T',\theta')$ is denoted by $\TV(\Pr_{T,\theta}[x],\Pr_{T',\theta'}[x])$. The values on the internal nodes are denoted by $y_v$ for each internal node $v \in V$, and $\Pr_{T,\theta}[x,y]$ denotes the joint distribution over the leaves and internal nodes. We continue with some definitions:

Given a graph $G = (V,E)$ and an edge $e = (u,v)$ in the graph, we say that a graph $G'=(V',E')$ is obtained from $G$ by contracting $e$ if $G'$ is the result of removing $e$ from the graph and identifying $u$ and $v$ as a single vertex. Namely, if the new edge is denoted $z$, then

\[
V' = V \setminus \{u,v\}\cup \{z\}
\]

\[
E' = E \setminus \{(u,w) \colon w \in V\}
\setminus \{(v,w) \colon w \in V\}
\cup \{(z,w) \colon (u,w) \in V\}\enspace.
\]

For an example of an edge-contraction, see Figure <ref> (b)-(c): The dashed edge in (b) is contracted, resulting in the graph shown in (c).

We now define the contraction of all degree-2 nodes:

Given a graph $G=(V,E)$, we say that $G'=(V',E')$ is obtained from $G$ by contracting all the degree-2 nodes, if $G'$ is obtained from $G$ using the following process:

* $G'\gets G$.

* While $G'$ contains a node $w$ of degree $2$:

* Contract one of the edges incident with $w$.

For an example of a contraction of degree-2 nodes, see Figure <ref>, (b)-(c): In (b), there are some nodes of degree $2$, labeled $a$-$f$. In (c), we can see the result of contracting these nodes.

Given a tree $T$ and a subset $S$ of the leaves of $T$, the subtree of $T$ induced by $S$ is the tree that is obtained from $T$ by removing all the edges and all the nodes that are not in any path between two leaves $i,j \in S$.

In other words, the subtree of $T$ induced by $S$ is the minimal subtree of $T$ that contains $S$. For an example, in Figure <ref> (a), a tree is depicted, and its subtrees induced by $\{1,2,3,5\}$ and $\{4,6,7,8\}$ are depicted in Figure <ref> (b-1) and (b-2), respectively.

Throughout the proof, we will modify graphs by contracting edges. Whenever we contract an edge, we identify its two endpoints as a single vertex. If we contract multiple edges, the resulting graph may identify even more than two edges of the original as one edge. If a graph $T'$ is the result of multiple edge-contractions applied on a graph $T$, then, for each vertex $v'$ of $T'$, the set of preimages of $v'$ under the transformation from $T$ to $T'$ is defined as the set of all vertices of $T$ that were identified into $v'$. To be more formal, we provide the following definition:

Let $T'=(V',E')$ be obtained from $T=(V,E)$ via a sequence of edge contractions. For any vertex $v' \in T'$, the set of preimages of $v$ under the transformation from $T$ to $T'$ is defined as the following set, which we denote here by $A_{v'}$:

* Start with the tree $T$, and define $A_v = \{v\}$ for each $v \in V$.

* For any contraction of an edge $(u,v)$ into a single vertex $w$:

* Define $A_w = A_u \cup A_v$.

* Return $A_{v'}$ for each vertex $v' \in V'$.

Lastly, notice that if we contract edges then some of the nodes might change names. Hence, an edge that was connecting between two nodes $(u,v)$ in the original tree, might connect two other nodes in the contracted tree. Yet, the edge's function remain the same. Hence, we define the analogue of an edge $e$ in the contracted graph:

Let $T'$ be a tree that results from another tree $T$ via a sequence of edge contractions. Let $(u,v)$ be an edge in $T$ that is not contracted. Then, the analogue of $(u,v)$ in $T'$ is the obtained from $(u,v)$ in the following fashion:

* Set $e' \gets (u,v)$.

* For any contraction of edge $(z,w)$ into a node $q$ that $T$ undergoes:

* If $u \in \{z,w\}$ then $e' \gets (q,v)$.

* Otherwise, if $v \in \{z,w\}$ then $e'\gets (u,q)$,

* Return $e'$.

We continue with presenting some auxiliary lemmas that will be used for the proof.

Let $T=(V,E)$ and let $(\theta_e)_{e\in E}$ denote some weight-vector on the edges. Let $\theta'$ denote a weight vector that differs only on one edge $e'$. Then, $\TV(\Pr_{T,\theta}[x],\Pr_{T,\theta'}[x]) \le |\theta'_{e'}-\theta_{e'}|/2$.

Due to the equivalent definition of total variation in terms of coupling, it is sufficient to produce a coupling between $x \sim \Pr_{T,\theta}$ and $x'\sim \Pr_{T',\theta'}$ such that $\Pr[x\ne x'] \le |\theta'_{e'}-\theta_{e'}|/2$.
While $x$ and $x'$ denote the values of the leaves, we will use $y$ and $y'$ to denote the values on the internal nodes, such that $(x,y)$ and $(x',y')$ are jointly sampled from $\Pr_{T,\theta}$ and $\Pr_{T',\theta'}$, respectively. We will produce a coupling between $(x,y)$ and $(x',y')$ such that $\Pr[(x,y)\ne (x',y')] \le |\theta'_{e'}-\theta_{e'}|/2$ and this suffices to conclude the proof.

Let $e' = (u,v)$ denote the single edge where $\theta$ and $\theta'$ differ. We produce the coupling as follows:

* We start by sampling $y_u$ uniformly from $\{-1,1\}$ and $y'_u = y_u$

* Then, we sample $y_v$ such that $\Pr[y_v=y_u] = (1+\theta_e)/2$. Similarly, we sample $y'_v$ such that $\Pr[y'_v = y'_u] = \Pr[y'_v = y_u] = (1+\theta'_e)/2$. Note that we can couple $y_v$ and $y'_v$ such that $\Pr[y_v\ne y'_v] =\TV(y_v\mid y_u,~ y'_v\mid y_u) = |\theta_e - \theta'_e|/2$.

* Next, we will sample the remaining values of $x,y$ conditioned on $y_u$ and $y_v$, and the remaining values of $x',y'$ conditioned on $y'_u$ and $y'_v$. If $y_u=y'_u$ and $y_v=y'_v$, then these two conditional distributions are the same, hence, we can sample such that $(x,y)=(x',y')$. Otherwise, we will sample $x,y,x'$ and $y'$ arbitrarily.

Notice that with probability $1-|\theta_{e'}-\theta'_{e'}|/2$, $y_u=y'_u$ and $y_v=y'_v$. Hence, $\Pr[(x,y)=(x',y')] \ge 1- |\theta_{e'}-\theta'_{e'}|/2$, as required to complete the proof.

Let $T$ be a tree and $\theta$ a weight-function on its edges. Let $T'$ be obtained from $T$ by contracting an edge $e$ with $\theta_e=1$ and let $\theta'$ denote the restriction of $\theta$ to the edges of $T'$. Then, for any values $x=(x_1,\dots,x_n)$ on the leaves, $\Pr_{T,\theta}[x]=\Pr_{T',\theta'}[x]$.

Notice that by contracting the edge, the pairwise correlations $\alpha_{ij}$ between any two leaves do not change, hence the leaf distributions are identical (this is a known fact and it also follows directly from Lemma <ref>).

§.§ Proof body

We are ready to present the results of [Daskalakis et al., 2009]. They are written in a slightly different way than was originally present, but we translate their guarantees to our notation. (See Section <ref> for translating their guarantees).

There is a polynomial-time algorithm, for learning some unknown tree $T^* = (V^*,E^*)$, whose properties are presented below.
Its inputs are:

* Approximate correlations, $\hat{\alpha}_{ij}$, for any two leaves $i,j \in [n]$. These satisfy the guarantee that there exists an Ising model $\Pr_{T^*,\theta^*}$, whose correlations $\alpha^*_{ij}$ satisfy: $|\alpha^*_{ij} - \hat{\alpha}_{ij}| \le \eta$, for any two leaves $i,j$ and for some $\eta\in (0,1/2]$.

* Parameters $\xi,\delta>0$ such that $\xi\delta \ge \eta$.

The algorithm outputs a forest, whose connected components are trees, $\tilde{T}_1=(\tilde{V}_1,\tilde{E}_1), \dots, \tilde{T}_R=(\tilde{V}_R,\tilde{E}_R)$ with the following guarantees: (below, $C>0$ is a universal constant)

* Let $S_r$ denote the set of leaves of $\tilde T_r$ for any $r\in [R]$. Then, $\{S_1,\dots,S_R\}$ is a partition of the set of leaves of $T^*$.

* For all $r=1,\dots,R$, denote by $T_r=(V_r,E_r)$ the subtree of $T^*$ induced by $S_r$, as defined in Definition <ref>. Then, each tree $\tilde{T}_r$ is obtained from $T_r$ using the following operations:

* Contract a subset of the edges. Only edges $e$ of weight $\theta^*_e \ge 1-C\xi$ can be contracted.

* Contract all the nodes of degree-2 from the resulting tree.

* Any edge $e$ that is common to more than one of the trees $\{T_1,\dots,T_R\}$, satisfies $\theta^*_e \ge 1-C\xi$.

* Any leaves $i,j$ that belongs to different sets from $\{S_1,\dots,S_R\}$, satisfy $|\alpha^*_{ij}| \le C\sqrt{\delta}$.

For example, in Figure <ref> (a) a tree is depicted, whereas the output of the algorithm is given in Figure <ref> (c). Since the dashed edge $e$ connecting nodes $a$ and $b$ is contracted in the output, its weight must satisfy $\theta^*_e \ge 1 - \Omega(\xi)$.  Further, since nodes $1$ and $7$ reside in different subtrees in the output of the algorithm, their correlation must satisfy $|\alpha^*_{17}| \le O(\sqrt\delta)$. For another example, see Figure <ref>: in (a), the original tree is depicted, whereas, the output is the forest in (c). The induced trees $T_1$ and $T_2$ are shown in (b). Since the dashed edges in (a) are shared by both induced subtrees, their weight satisfies $\theta^*_e \ge 1-\Omega(\xi)$.

Below, we will prove the following central Lemma:

Let $\eta > 0$ be a parameter and $T^*$ be an unknown tree with weight vector $\theta^*$ and pairwise correlations $\alpha^*$ between the leaves.
Suppose we execute Algorithm <ref> with the following inputs:

* Pairwise correlations $\hat{\alpha}_{ij}$ that satisfy $|\hat{\alpha}_{ij}-\alpha^*_{ij}| \le \eta$.

* Parameters $\delta,\xi$ such that $\xi \delta \ge \eta$ and $\xi = C_1/n$, for some universal constant $C_1 > 0$.

* Parameter $\hat{\eta}$ that satisfies $\hat{\eta} = C_2 n \xi + \eta$, for some universal constant $C_2 > 0$.

Recall that the algorithm outputs a weighted forest, and denote the forest by $\tilde{F}$ and the weights by $\hat{\theta}$.
Then, $\TV(\Pr_{T^*,\theta^*}[x],\Pr_{\tilde{F},\tilde{\theta}}[x]) \in O(n^3\xi + n^2 \sqrt{\delta} + \eta)$. (We note that an Ising model over a forest is defined by taking the different tree components to be independent.)

The remainder of this section is dedicated to the proof of Lemma <ref>. In Section <ref> we conclude the proof of Theorem <ref> (unknown topology), by substituting the parameters $\xi,\delta$ and $\eta$ appropriately using the finite-sample estimates.

To analyze the algorithm, we will create auxiliary trees $T^{(i)} = (V^{(i)},E^{(i)})$ with weight function $\theta^{(i)}$ and pairwise correlations $\alpha^{(i)}_{ij}$ (for $i = \{1,2,3\}$) that interpolate between the true parameters $T^*, \theta^*$, and the Algorithm <ref>'s output $(\tilde F, \tilde\theta)$.
To bound the total variation distance between $(T^*, \theta^*)$ and $(\tilde F, \tilde\theta)$, we apply triangle inequality after individually bounding the total variation of the leaf distributions (i) between $(T^*, \theta^*)$ and $(T^{(1)}, \theta^{(1)})$, (ii) between $(T^{(1)}, \theta^{(1)})$ and $(T^{(2)}, \theta^{(2)})$, (iii) between $(T^{(2)}, \theta^{(2)})$ and $(T^{(3)}, \theta^{(3)})$, and (iv) between $(T^{(3)}, \theta^{(3)})$ and $(\tilde F, \tilde\theta)$.

Before defining the first intermediate distribution, $(T^{(1)},\theta^{(1)})$, we recall some definitions. First, recall that the algorithm of [Daskalakis et al., 2009] returns a forest whose connected components are $(\tilde{T}_1,\dots,\tilde{T}_R)$. Each $\tilde{T}_r$ is a modification of $T_r$, which is defined as the subtree of $T^*$ that is induced by the set of leaves of $\tilde{T}_r$. As an intermediate step, we start by modifying $T^*$ according to the induced subtrees $T_1,\dots,T_R$. Note that initially, we consider $T_r$ instead of $\tilde{T}_r$, as $T_r$ is closer to $T^*$ than $\tilde{T}_r$.

We start by defining $T^{(1)}$ as the tree that is obtained from $T^*$ by contracting all the edges that appear in more than one induced tree $T_r$ Further, the edge-weight for $\theta^{(1)}$ equals $\theta^*$ on all the remaining (non-contracted) edges. Note that $T^{(1)}$ still has a single connected component. (For example, in Figure <ref>, we contract the purple-dashed lines in (a) because they appear both in the induces red and blue trees. This results in the tree depicted in (b).)

A depiction of the intermediate trees, $T^{(1)},T^{(2)}$ and $T^{(3)}$ in the analysis of the algorithm. The original tree $T^*$ contains all the edges in (a). The output forest partitions the leaves into three connected components: $S_1 = \{1,2,5\}$, $S_2 = \{3,4,6,7,8\}$ and $S_3 = \{9,10,11\}$. The tree $T_1$, which is the subtree of $T^*$ induced by $S_1$, contains the red and purple-dashed edged. The tree $T_2$ contains the blue and purple-dashed edges. And $T_3$ contains the green edges. In (b), we depict $T^{(2)}$, which is obtained by contracting all the edges that are shared among multiple subtrees $T_r$, for $r=1,2,3$. In this example, those are the purple-dashed edges. In (c), we depict $T^{(2)}$, which is obtained from $T^{(2)}$ by adding auxiliary nodes: for each internal node $v$ and each subtree $T_r$ that it touches, we create a new node $v^r$, connect it with $v$ with an edge of weight $1$, and further, connect to $v^r$ all the edges in $T_r$ that were incident with $v$ in $T^{(1)}$. The forest $T^{(3)}$ is obtained from $T^{(2)}$ by removing all the edges that are incident with the nodes $a,b,c,d,e$. These are the dashed edges.

We would like to bound the total variation distance between $\Pr_{T^*,\theta^*}[x]$ and $\Pr_{T^{(1)},\theta^{(1)}}[x]$. Notice that for each contracted edge $e$, we have from Theorem <ref> that $\theta_e \ge 1-C\xi$ for some universal constant $C>0$. Contracting each such edge $e$ is equivalent to modifying $\theta_e$ to equal $1$, as argued in Lemma <ref>. Hence, the total variation distance for each contraction is bounded by $C\xi/2$ from Lemma <ref>. By the triangle inequality, since we contract at most $O(n)$ edges, then $\TV(\Pr_{T^*,\theta^*}[x],\Pr_{T^{(1)},\theta^{(1)}}[x]) \le O(n\xi)$.

Next, we continue to present the second intermediate model, parameterized by $T^{(2)}=(V^{(2)},E^{(2)})$ and $\theta^{(2)}$. To obtain $T^{(2)}=(V^{(2)},E^{(2)})$ and $\theta^{(2)}$, recall that each vertex of $T^{(1)}=(V^{(1)},E^{(1)})$ may correspond to multiple vertices of $T^*$ since $T^{(1)}$ was obtained by contracting edges in $T^*$.
For any $v\in V^{(1)}$, we denote by $A_v$ the set of preimages of $v$ under the transformation from $T^*$ to $T^{(1)}$ (see Definition <ref> and the paragraph above this definition). In other words, $A_v$ is the set of nodes of $T^*$ that were contracted into $v$. Denote by $\rho(v)$ the set of indices $r\in \{1,\dots,R\}$ of trees $T_r$ that intersect a node that was contracted into $v$. In other words, $\rho(v)$ is the set of indices $r$ such that $A_v \cap V_r \ne \emptyset$, where $V_r$ is the set of vertices of the subtree $T_r$.
Intuitively, for the construction of $T^{(2)}$, we would like to make $\rho(v)$ copies of node $v$, each for a subtree that contains $v$. To be precise, $T^{(2)}$ is constructed as follows:

* The set of vertices $V^{(2)}$ of $T^{(2)}$ is obtained from $V^{(1)}$ by adding a new vertex $v^r$, for each $v$ and $r$ such that $r \in \rho(v)$.

* For any $v\in V^{(1)}$ and $r\in \rho(v)$, define an edge $(v,v^r)$ of weight $\theta^{(2)}(v,v^r)=1$.

* For any edge $(u,v)\in E^{(1)}$, define a new edge in $E^{(2)}$ according to the following considerations:

* If $|\rho(u)\cap\rho(v)| = 1$, denote $\{r\} = \rho(u)\cap\rho(v)$ and add an edge $(u^r,v^r)$ in $E^{(2)}$, with weight $\theta^{(2)}_{(u^r,v^r)} = \theta^{(1)}_{(u,v)}$. This replaces the edge $(u,v)$.

* If $|\rho(u)\cap\rho(v)| = \emptyset$, add an edge $(u,v)$ to $E^{(2)}$ with weight $\theta^{(2)}_{(u,v)} = \theta^{(1)}_{(u,v)}$

* It is impossible that $|\rho(u)\cap\rho(v)| > 1$, otherwise, $(u,v)$ would have been contracted.

(See Figure <ref> for an example of a tree $T^{(2)}$.)
We note that $T^{(1)}$ can be obtained from $T^{(2)}$ by contracting all the edges $(v,v^r)$ for $v\in V^{(1)}$ and $r\in \rho(v)$.
Hence, from Lemma <ref>, $\Pr_{T^{(2)},\theta^{(2)}}[x] = \Pr_{T^{(1)},\theta^{(1)}}[x]$ for all values $x$ on the leaves. In particular,

\[
\TV\lp(\Pr_{T^{(2)},\theta^{(2)}}[x], \Pr_{T^{(1)},\theta^{(1)}}[x]\rp) = 0.
\]

Next, we define $T^{(3)}$ and $\theta^{(3)}$. Recall that the vertices of $T^{(2)}$ are of two types: (1) vertices that are copies of those in $V^{(1)}$; and (2) vertices $v^r$ for $v \in V^{(1)}$ and $r \in \rho(v)$. Then, $T^{(3)}$ is obtained from $T^{(2)}$ by removing all the edges incident to the vertices of category (1), as depicted in Figure <ref> (c). This creates a forest, and we remove from this forest each connected component that is disconnected from the leaves. We prove the following lemma:

There are $R$ connected components in $T^{(3)}$, and the sets of leaves of the connected components are exactly the sets of leaves of $T_1,\dots,T_R$. Namely, for each $T_r$ there exists one connected component of $T^{(3)}$ that has the same leaf-set as $T_r$.

First, we argue that any two leaves that are in the same tree $T_r$, are also in the same connected component of $T^{(3)}$. Let $i,j$ be two leaves of $T_r$ and consider the edges on the path $P$ between them in $T_r$. For any such edge $(u,v)$, there are two possibilities: (1) This edge was contracted at some point, and there is some $w\in T^{(1)}$ such that $u,v\in A_w$. (2) This edge was not contracted, and there exist some $(w,z)$ in $E^{(1)}$ that is the analogue of $(u,v)$ in $T^{(1)}$ (see Definition <ref> and its preceding discussion). By definition of $T^{(2)}$, this edge is moved in $T^{(2)}$ to connect $(w^r,z^r)$. In particular, the path from $i$ to $j$ in $T^{(2)}$ contains only vertices of the form $q^r$. Hence, this path is not disconnected in $T^{(3)}$ from the graph.

Next, we argue why two leaves $i,j$ in two different trees $T_r$ and $T_s$, respectively, cannot be connected in $T^{(3)}$. Indeed, the parent of leaf $i$ in $T^{(2)}$ must be of the form $v^r$ while the parent of $j$ must be of the form $v^s$. Notice that in $T^{(3)}$ there is no edge connecting a vertex from $v^r$ with a vertex from $v^3$, hence, these two leaves are necessarily disconnected.

We would like to use Theorem <ref> to bound the total variation distance between $\Pr_{T^{(2)},\theta^{(2)}}[x]$ and $\Pr_{T^{(3)},\theta^{(3)}}[x]$, by analyzing the change in the pairwise correlations. To do so, we use the fact that the pairwise correlations that have changed are only those between leaves $i,j$ of different trees $T_r$ and $T_s$, respectively, and by Theorem <ref> we have that in $T^*$ those have correlation $|\alpha^*_{ij}|\le C\sqrt{\delta}$ where $\delta$ is defined in Theorem <ref> and $C>0$ is a universal constant. Notice that, though, the correlation between two leaves in $T^{(2)}$ can be greater than their correlation in $T^*$. As argued above, the correlation in $T^{(2)}$ equals that in $T^{(1)}$. To compare between the correlations in $T^{(1)}$ and $T^*$, recall that $T^{(1)}$ is obtained from $T$ by contracting edges. Yet, any contracted edge has weight at least $1-C\xi$, hence, contracting the edge can increase the correlation by at most $1/(1-C\xi)$. Since any path between two leaves can contain at most $n$ edges, the contraction can increase the correlation by at most $1/(1-C\xi)^n$. By assumption, $\xi \le 1/(Cn)$, hence this factor is at most a constant. Under that assumption, the correlation in $T^{(2)}$ between any two leaves of different subtrees $T_r$ is bounded by $O(\sqrt{\delta})$. Since in $T^{(3)}$ their correlation becomes $0$, this implies that the pairwise correlations change by at most $O(\sqrt{\delta})$.

Hence, for any $i,j$, $|\alpha^{(2)}_{ij} - \alpha^{(3)}_{ij}| \le O(\sqrt{\delta})$. Since $T^{(2)}$ and $T^{(3)}$ both share the same underlying graph (as removing edges can be done by just replacing the weight with $0$), it follows from Theorem <ref> that the total variation distance between the leaf distributions of $T^{(2)}$ and $T^{(3)}$ is bounded by $O(n^2\sqrt{\delta})$.

Next, we would like to bound the total variation distance between the leaf distribution of $T^{(3)}$ and the output of the algorithm. Since $T^{(3)}$ and $\tilde{F}$ have the same connected components, the leaf distributions of both factorize the same. In particular, the leaf-sets $S_1,\dots,S_R$ of $T_1,\dots,T_r$ are independent in these product distributions. To bound the total variation distance between the leaf distributions of $T^{(3)}$ and $\tilde{F}$, it suffices to bound the total variation distance with respect to each connected component separately, and then sum the bounds for each component.
Hence, we will fix some $r \in \{1,\dots,R\}$.
For this end, let us analyze the weights $\tilde{\theta}_e$ given by Algorithm <ref> on the tree $\tilde{T}_r$. Recall that the last step of this algorithm is to use Algorithm <ref> on the tree $\tilde{T}_r$ with some parameter $\eta'>0$ and correlations $\hat{\alpha}_{ij}$ that were estmated from samples of the original tree $T^*$. Further, recall that Algorithm <ref> is guaranteed to return some weights $\tilde{\theta}_e$ on the edges, such that the pairwise correlations between the leaves, which we denote by $\tilde{\alpha}_{ij}$, are $\eta'$-close to the correlations $\hat{\alpha}_{ij}$ that were given to it as input, namely, $|\tilde{\alpha}_{ij} - \hat{\alpha}_{ij}| \le \eta$ for any pair $i,j$ of leaves. Yet, Algorithm <ref> will succeed only if there exist such weights $\tilde{\theta}_e$ that satisfy the above constraint. To that end, we claim the following:

Fix $r \in \{1,\dots,R\}$.
Then, there exist weights $\theta'_{ij}$ to the edges of $\tilde{T}_r$ such that the corresponding pairwise correlations, $\alpha'_{ij}$ satisfy $|\alpha'_{ij} - \hat{\alpha}_{ij}| \le \eta + O(n\xi)$ for any leaves $i,j\in S_r$.

Notice that it is sufficient to find weights $\theta'_e$ such that $|\alpha'_{ij} - \alpha^*_{ij}| \le O(n\xi)$, since $|\hat{\alpha}_{ij} - \alpha^*_{ij}|\le \eta$, by the assumption in Lemma <ref>. Since $T_r$ is the subtree induced by the set of leaves $S_r$, our goal is to show that $\alpha'_{ij}$ is $O(n\xi)$-close to the pairwise correlation of $i$ and $j$ accross $T_r$. Hence, this is what we will do.
As a first solution, we propose to set for each edge $e$ its weight $\theta'_e$ to equal its corresponding weight $\theta^*_e$ in $T_r$.
Recall, though, that in the process of transforming $T_i$ to $\tilde{T}_i$, there are two modifications, which implies that we cannot exactly match the edges of $\tilde{T}_i$ with those of $T_i$. We elaborate below on the transformations and how to set $\theta'_e$ given these transformations.

* The first transformation is obtained by contracting some edges of weight $\theta_e \ge 1-O(\xi)$. For these contracted edges, we will not define $\theta'_e$. Contracting these edges changes the pairwise correlations between the leaves by at most $O(n\xi)$, since there can be at most $O(n)$ edges along each path.

* The second transformation is a contraction of some nodes of degree $2$. Yet, for each such contraction, there is an easy way to modify the weights such that the pairwise correlations over the leaves does not change. In particular, if $u$ is a node and $v,w$ are its neighbors, then $u$ is being deleted from the graph and $v,w$ are being connected. If we set the weight of the new edge as a multiplication of the weights of the two old edges, then the pairwise correlations between the leaves do not change. In particular, we will define $\theta'$ under this logic: we will track the changes from $T_i$ to $\tilde{T}_i$, and whenever a degree-2 node is being contracted, we modify the weights accordingly: if edges $e$ and $e'$ were contracted to $e''$, we set the weight of $e''$ to equal the multiplication of weights of $e$ and $e'$.

Using the above definition of $\theta'_e$ and the above analysis, it follows that $|\alpha'_{ij} - \alpha^*_{ij}| \le O(n\xi)$. This suffices to complete the proof, as explained above.

It follows from Lemma <ref> that the execution of Algorithm <ref> succeeds, if it is run with $\eta' = Cn\xi+\eta$ and a sufficiently large $C>0$. This implies that for any $i,j\in S_r$, $|\tilde{\alpha}_{ij} - \hat\alpha_{ij}|\le \eta' \le \eta + O(n\xi)$. By the triangle inequality, $|\tilde{\alpha}_{ij} - \alpha^*_{ij}| \le 2\eta + O(n\xi)$. Lastly, following the analysis above, it is easy to show that also $|\alpha^{(3)}_{ij} - \alpha^*_{ij}| \le O(n\xi)$. Indeed, the only modification from $T$ to $T^{(3)}$ that affects the pairwise correlation between $i,j\in S_r$ is the contraction of edges of $\theta^*_e \ge 1-O(\xi)$. This affects the pairwise correlation by $O(n\xi)$. By the triangle inequality, we derive that $|\tilde{\alpha}_{ij} - \alpha^{(3)}_{ij}| \le O(n\xi + \eta)$. The last step would be to apply Theorem <ref> (same topology) to compare between the distribution over $\tilde{T_i}$ and its corresponding connected component in $T^{(3)}$. Yet, this theorem would apply only if the two components have the same topology. While they do not, we note that both trees are contractions of the same tree $T_r$. Hence, we can view both distributions as defined over the tree $T_r$, where the contracted edges have weight $1$. By Theorem <ref> (same topology) we derive that the total variation distance between the two distributions over $S_r$ is bounded by $O(n\xi |S_r|^2)$. By summing over all $r$, we derive that

\[
\TV\lp(\Pr_{T^{(3)}, \theta^{(3)}}[x],\ \Pr_{\tilde{F},\tilde{\theta}}[x]\rp)
\le O\lp( n\xi \sum_{r=1}^r |S_r|^2\rp)
\le O(n^3\xi).
\]

By summing up the total variation distances between the auxiliary distributions parameterized by $T^{(i)}$, this concludes the proof of Lemma <ref>.

§.§ Concluding the proof of Theorem <ref> (unknown topology)

We use Lemma <ref>. First of all, let us optimize $\xi$ and $\delta$ for a fixed value of $\eta$. This can be achieved by selecting $\delta = \eta^{2/3}n^{2/3}$ and $\xi = \eta^{1/3}n^{-2/3}$. We note that the requirement $\xi \le O(1/n)$ if $\eta \le O(1/n)$. The final bound is $O(n^{7/3}\eta^{1/3})$. To get this below $\epsilon$, we have to set $\eta \le O(\epsilon^3/n^7)$. This requires a sample of size $n \ge \Omega(\log(n/\delta)/\eta^2) = \Omega(n^{14}\log(n/\delta)/\epsilon^6)$.

§.§ Translating the notation of [Daskalakis et al., 2009]

We note that [Daskalakis et al., 2009] uses a different notation. For convenience, we explain the translation in the Ferromagnetic setting where $\alpha_{ij}, \theta_{kl} \ge 0$, however, in order to transition to the non-Ferromagnetic setting one would simply have to replace these quantities with their absolute values, $|\alpha_{ij}|$ and $|\theta_{kl}|$, respectively.

Instead of edge weight $\theta_{(k,\ell)}$, [Daskalakis et al., 2009] use the metric $d_{k,\ell} = -\log \theta_{(k,\ell)}$. Instead of $\alpha_{i,j}$ they use the metric $d_{i,j} = -\log \alpha_{i,j}$. They denote the true (underlying) metric by $d$, whereas they assume that the algorithm receives a $(\tau,M)$-distorted metric on the leaves, denoted $\hat{d}$. This means that $|\hat{d}_{i,j}-d_{i,j}|\le \tau$ whenever $d_{i,j} \le M$. Using our notation, this means that $|\log \hat{\alpha}_{ij} - \log \alpha^*_{i,j}| \le \tau$ whenever $\alpha^*_{ij} \ge e^{-M}$. Equivalently,

\[
-\tau \le \log \hat{\alpha}_{ij} - \log \alpha^*_{i,j} \le \tau \quad \text{whenever } \alpha^*_{ij} \ge e^{-M}
\]

which is equivalent to

\begin{equation}\label{eq:M-tau}
e^{-\tau} \le \hat{\alpha}_{ij}/\alpha^*_{i,j} \le e^{\tau} \quad \text{whenever } \alpha^*_{ij} \ge e^{-M}\enspace.
\end{equation}

We will show how their guarantees can be implied from our guarantees. First, notice that in order for (<ref>) to hold, it is sufficient to assume that $\tau \le 1$ and

\[
(1-\tau/2) \le \hat{\alpha}_{ij}/\alpha^*_{i,j} \le (1+\tau/2) \quad \text{whenever } \alpha^*_{ij} \ge e^{-M}\enspace.
\]

If we substitute $\xi = \tau/2$ and $\delta = e^{-M}$, the last inequality substitutes to

\[
\alpha^*_{i,j} - \xi \alpha^*_{ij} \le \hat{\alpha}_{ij} \le \alpha^*_{i,j} + \xi \alpha^*_{ij} \quad \text{whenever } \alpha^*_{ij} \ge \delta \enspace,
\]

which is equivalent to

\begin{equation}\label{eq:xi-delta}
|\hat{\alpha}_{ij} - \alpha^*_{i,j}| \le \xi \alpha^*_{ij} \quad \text{whenever } \alpha^*_{ij} \ge \delta \enspace.
\end{equation}

Eq. <ref> is guaranteed to hold if $|\hat{\alpha}_{i,j}-\alpha^*_{i,j}| \le \xi\delta$. Since in Theorem <ref> we assume that $|\hat{\alpha}_{i,j}-\alpha^*_{i,j}| \le \eta$, it suffices to assume that $\eta \le \xi\delta$ in order to imply (<ref>), which in turn implies the conditions in the paper of [Daskalakis et al., 2009].

§ INFORMATION THEORETIC BOUND

Upper bound.
While the result below was known, we prove it for completeness.

There is an algorithm that, given $m$ samples from the leaf-marginal of some tree structured Ising model with $n$ leaves, returns another tree structured Ising model whose total variation distance to the original model is bounded by $\epsilon$, with sample complexity $m = O(n\log(n/\epsilon)/\epsilon^2)$.

While it is apparent that the family of tree-structured Ising models is infinite, we will select a finite set which is an $\epsilon$-cover in total variation, and then we will use the following result to learn in total variation distance over a finite set:

Let $\epsilon,\delta>0$.
Given a finite family $\mathcal{C}$ of distributions and $m$ samples from some arbitrary distribution $\mu$, there exists an algorithm such that, with probability $1-\delta$, returns a distribution $\hat{\mu}\in \mathcal{C}$ that satisfies:

\[
\TV(\mu,\hat{\mu}) \le
3 \inf_{\nu \in \mathcal{C}} \TV(\mu,\nu) + \epsilon,
\]

with sample complexity $m = O(\log(|\mathcal{C}|/\delta)/\epsilon^2)$.

In order to apply Theorem <ref>, we will construct an $\epsilon$-cover to the set of tree structured Ising models.

For any $\epsilon>0$, there exists a family $\mathcal{C}$ of tree-structured Ising models of log cardinality $\log |\mathcal{C}|\le O(n\log(n/\epsilon))$, such that for any tree structured Ising model, there exists some model from $\mathcal{C}$ such that the total variation distance between these the two leaf distributions of these models is bounded by $\epsilon$.

For completeness, we prove this lemma using Theorem <ref>, yet, there are more direct ways to prove this lemma.

Each element of $\mathcal{C}$ will be parameterized by the following:

* A tree topology, with $n$ leaves labeled $1,\dots,n$. There can be at most $n^{O(n)}$ distinct trees.

* For each edge of the tree, its weight $\theta_e$ is one of $\{0,1/M, 2/M,\dots,1\}$, where $M = \Theta(n^3/\epsilon)$. There can be at most $M^{O(n)}$ possibilities to select the weights.

We derive that $|\mathcal{C}|\le (n/\epsilon)^{O(n)}$.

Given some tree $T$ and weight $\theta$, we will find an element of $\mathcal{C}$ that approximates it. In particular, we will take the element from $\mathcal{C}$ that has the same structure and additionally, each of its weights are $1/M$ close to $\theta$. It is easy to see from (<ref>) that the pairwise correlations between the leaves $\alpha_{ij}$, are $O(n/M)$-close in absolute value between the two models. Hence, by Theorem <ref> (fixed topology), the two models are $O(n^3/M)\le \epsilon$ close in total variation between the leaf distributions, provided that $M\ge \Omega(n^3/\epsilon)$.

To conclude the proof, we use the algorithm of Theorem <ref>, applying it on an $\epsilon/4$-cover using the construction in Lemma <ref>.

Lower bound

In order to learn latent tree-structured Ising models, when the topology is unknown, the sample complexity is lower bounded by $\Omega(n\log(n)/\epsilon^2)$.
This follows from [Koehler, 2020]: they prove that the number of samples that are required to learn a full tree from samples is $\Omega(n\log(n)/\epsilon^2)$, yet, this proof extends directly to the setting of latent nodes.

[Acharya et al., 2018]
Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, and Saravanan
Learning and testing causal models with interventions.
Advances in Neural Information Processing Systems, 31, 2018.

[Aigner et al., 1984]
Dennis J Aigner, Cheng Hsiao, Arie Kapteyn, and Tom Wansbeek.
Latent variable models in econometrics.
Handbook of econometrics, 2:0 1321–1393, 1984.

[Bartholomew et al., 2011]
David J Bartholomew, Martin Knott, and Irini Moustaki.
Latent variable models and factor analysis: A unified
approach, volume 904.
John Wiley & Sons, 2011.

[Bhattacharyya et al., 2021]
Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and NV Vinodchandran.
Near-optimal learning of tree-structured distributions by chow-liu.
In Proceedings of the 53rd Annual ACM SIGACT Symposium on
Theory of Computing, 2021.

[Bishop, 1998]
Christopher M Bishop.
Latent variable models.
In Learning in graphical models, pages 371–403. Springer,

[Blei et al., 2017]
David M Blei, Alp Kucukelbir, and Jon D McAuliffe.
Variational inference: A review for statisticians.
Journal of the American statistical Association, 1120
(518):0 859–877, 2017.

[Boix-Adsera et al., 2022]
Enric Boix-Adsera, Guy Bresler, and Frederic Koehler.
Chow-liu++: Optimal prediction-centric learning of tree ising models.
In 2021 IEEE 62nd Annual Symposium on Foundations of Computer
Science (FOCS), pages 417–426. IEEE, 2022.

[Bresler, 2015]
Guy Bresler.
Efficiently learning ising models on arbitrary graphs.
In Proceedings of the forty-seventh annual ACM symposium on
Theory of computing, pages 771–782, 2015.

[Bresler and Karzand, 2020]
Guy Bresler and Mina Karzand.
Learning a tree-structured ising model in order to make predictions.
The Annals of Statistics, 480 (2):0 713–737,

[Bresler et al., 2019]
Guy Bresler, Frederic Koehler, and Ankur Moitra.
Learning restricted boltzmann machines via influence maximization.
In Proceedings of the 51st Annual ACM SIGACT Symposium on
Theory of Computing, pages 828–839, 2019.

[Brustle et al., 2020]
Johannes Brustle, Yang Cai, and Constantinos Daskalakis.
Multi-item mechanisms without item-independence: Learnability via
In Proceedings of the 21st ACM Conference on Economics and
Computation, pages 715–761, 2020.

[Canonne et al., 2017]
Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart.
Testing bayesian networks.
In Conference on Learning Theory, pages 370–448. PMLR, 2017.

[Chang, 1996]
Joseph T Chang.
Full reconstruction of markov models on evolutionary trees:
identifiability and consistency.
Mathematical biosciences, 1370 (1):0 51–73,

[Chor and Tuller, 2005]
Benny Chor and Tamir Tuller.
Maximum likelihood of evolutionary trees is hard.
In Annual International Conference on Research in Computational
Molecular Biology, pages 296–310. Springer, 2005.

[Chow and Wagner, 1973]
C Chow and T Wagner.
Consistency of an estimate of tree-dependent probability
distributions (corresp.).
IEEE Transactions on Information Theory, 190
(3):0 369–371, 1973.

[Chow and Liu, 1968]
CKCN Chow and Cong Liu.
Approximating discrete probability distributions with dependence
IEEE transactions on Information Theory, 140
(3):0 462–467, 1968.

[Cryan et al., 2001]
Mary Cryan, Leslie Ann Goldberg, and Paul W Goldberg.
Evolutionary trees can be learned in polynomial time in the two-state
general markov model.
SIAM Journal on Computing, 310 (2):0 375–397,

[Csurös, 2002]
Miklós Csurös.
Fast recovery of evolutionary trees with thousands of nodes.
Journal of Computational Biology, 90 (2):0
277–297, 2002.

[Dagan et al., 2021]
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis
Learning ising models from one or multiple samples.
In Proceedings of the 53rd Annual ACM SIGACT Symposium on
Theory of Computing, pages 161–168, 2021.

[Daskalakis and Pan, 2017]
Constantinos Daskalakis and Qinxuan Pan.
Square hellinger subadditivity for bayesian networks and its
applications to identity testing.
In Conference on Learning Theory, pages 697–703. PMLR, 2017.

[Daskalakis and Pan, 2021]
Constantinos Daskalakis and Qinxuan Pan.
Sample-optimal and efficient learning of tree ising models.
In Proceedings of the 53rd Annual ACM SIGACT Symposium on
Theory of Computing, 2021.

[Daskalakis et al., 2006]
Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch.
Optimal phylogenetic reconstruction.
In Proceedings of the thirty-eighth annual ACM symposium on
Theory of computing, pages 159–168, 2006.

[Daskalakis et al., 2009]
Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch.
Phylogenies without branch bounds: Contracting the short, pruning the
In Annual International Conference on Research in Computational
Molecular Biology, pages 451–465. Springer, 2009.

[Daskalakis et al., 2011]
Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch.
Evolutionary trees and the ising model on the bethe lattice: a proof
of steel’s conjecture.
Probability Theory and Related Fields, 1490
(1):0 149–189, 2011.

[Daskalakis et al., 2019]
Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.
Testing ising models.
IEEE Transactions on Information Theory, 650
(11):0 6829–6852, 2019.

[Daskalakis et al., 2022]
Constantinos Daskalakis, Yuval Dagan, and Anthimos-Vardis Kandiros.
Where does em converge in gaussian latent tree models?
In Conference on Learning Theory (COLT), 2022.

[Daskalakis et al., 2018]
Costis Daskalakis, Christos Tzamos, and Manolis Zampetakis.
Bootstrapping em via power em and convergence in the naive bayes
In International Conference on Artificial Intelligence and
Statistics, pages 2056–2064. PMLR, 2018.

[Dempster et al., 1977]
Arthur P Dempster, Nan M Laird, and Donald B Rubin.
Maximum likelihood from incomplete data via the em algorithm.
Journal of the Royal Statistical Society: Series B
(Methodological), 390 (1):0 1–22, 1977.

[Devroye et al., 2020]
Luc Devroye, Abbas Mehrabian, and Tommy Reddad.
The minimax learning rates of normal and ising undirected graphical
Electronic Journal of Statistics, 140 (1):0
2338–2361, 2020.

[Ding et al., 2021]
Mucong Ding, Constantinos Daskalakis, and Soheil Feizi.
Gans with conditional independence graphs: On subadditivity of
probability divergences.
In International Conference on Artificial Intelligence and
Statistics, pages 3709–3717. PMLR, 2021.

[Erdős et al., 1999]
Péter L Erdős, Michael A Steel, László A Székely, and
Tandy J Warnow.
A few logs suffice to build (almost) all trees (i).
Random Structures & Algorithms, 140 (2):0
153–184, 1999.

[Everett, 2013]
B Everett.
An introduction to latent variable models.
Springer Science & Business Media, 2013.

[Felsenstein, 1973]
Joseph Felsenstein.
Maximum-likelihood estimation of evolutionary trees from continuous
American journal of human genetics, 250 (5):0
471, 1973.

[Felsenstein, 1981]
Joseph Felsenstein.
Evolutionary trees from gene frequencies and quantitative characters:
finding maximum likelihood estimates.
Evolution, pages 1229–1242, 1981.

[Felsenstein, 2004]
Joseph Felsenstein.
Inferring phylogenies, volume 2.
Sinauer associates Sunderland, MA, 2004.

[Goel, 2019]
Surbhi Goel.
Learning restricted boltzmann machines with arbitrary external
arXiv preprint arXiv:1906.06595, 2019.

[Goel et al., 2020]
Surbhi Goel, Adam Klivans, and Frederic Koehler.
From boltzmann machines to neural networks and back again.
Advances in Neural Information Processing Systems,
33:0 6354–6365, 2020.

[Gronau et al., 2008]
Ilan Gronau, Shlomo Moran, and Sagi Snir.
Fast and reliable reconstruction of phylogenetic trees with very
short edges.
In SODA, volume 8, pages 379–388, 2008.

[Hamilton et al., 2017]
Linus Hamilton, Frederic Koehler, and Ankur Moitra.
Information theoretic properties of markov random fields, and their
algorithmic applications.
Advances in Neural Information Processing Systems, 30, 2017.

[Huson et al., 1999]
Daniel H Huson, Scott M Nettles, and Tandy J Warnow.
Disk-covering, a fast-converging method for phylogenetic tree
Journal of computational biology, 60 (3-4):0
369–386, 1999.

[Jalali et al., 2011]
Ali Jalali, Pradeep Ravikumar, Vishvas Vasuki, and Sujay Sanghavi.
On learning discrete graphical models using group-sparse
In Proceedings of the fourteenth international conference on
artificial intelligence and statistics, pages 378–387. JMLR Workshop and
Conference Proceedings, 2011.

[Jordan, 2004]
Michael I Jordan.
Graphical models.
Statistical science, 190 (1):0 140–155, 2004.

[Kandiros et al., 2021]
Vardis Kandiros, Yuval Dagan, Nishanth Dikkala, Surbhi Goel, and Constantinos
Statistical estimation from dependent data.
In International Conference on Machine Learning, pages
5269–5278. PMLR, 2021.

[King et al., 2003]
Valerie King, Li Zhang, and Yunhong Zhou.
On the complexity of distance-based evolutionary tree.
In Proceedings of the fourteenth annual ACM-SIAM symposium on
Discrete algorithms, page 444. SIAM, 2003.

[Klivans and Meka, 2017]
Adam Klivans and Raghu Meka.
Learning graphical models using multiplicative weights.
In 2017 IEEE 58th Annual Symposium on Foundations of Computer
Science (FOCS), pages 343–354. IEEE, 2017.

[Koehler, 2020]
Frederic Koehler.
A note on minimax learning of tree models.

[Koller and Friedman, 2009]
Daphne Koller and Nir Friedman.
Probabilistic graphical models: principles and techniques.
MIT press, 2009.

[Lauritzen, 1996]
Steffen L Lauritzen.
Graphical models, volume 17.
Clarendon Press, 1996.

[Lee et al., 2006]
Chunghau Lee, Sigal Blay, Arne Ø Mooers, Ambuj Singh, and Todd H Oakley.
Comet: A mesquite package for comparing models of continuous
character evolution on phylogenies.
Evolutionary Bioinformatics, 2:0 117693430600200022,

[Moitra et al., 2021]
Ankur Moitra, Elchanan Mossel, and Colin P Sandon.
Learning to sample from censored markov random fields.
In Conference on Learning Theory, pages 3419–3451. PMLR,

[Mossel, 2007]
Elchanan Mossel.
Distorted metrics on trees and phylogenetic forests.
IEEE/ACM Transactions on Computational Biology and
Bioinformatics, 40 (1):0 108–116, 2007.

[Mossel and Roch, 2005]
Elchanan Mossel and Sébastien Roch.
Learning nonsingular phylogenies and hidden markov models.
In Proceedings of the thirty-seventh annual ACM symposium on
Theory of computing, pages 366–375, 2005.

[Narasimhan and Bilmes, 2004]
Mukund Narasimhan and Jeff A Bilmes.
Pac-learning bounded tree-width graphical models.
In Proc. 20th Ann. Conf. on Uncertainty in Artificial
Intelligence (UAI), 2004.

[Pearl, 1988]
Judea Pearl.
Probabilistic reasoning in intelligent systems: networks of
plausible inference.
Morgan kaufmann, 1988.

[Ravikumar et al., 2010]
Pradeep Ravikumar, Martin J Wainwright, and John D Lafferty.
High-dimensional ising model selection using l 1-regularized logistic
The Annals of Statistics, 380 (3):0
1287–1319, 2010.

[Roch, 2006]
Sebastien Roch.
A short proof that phylogenetic tree reconstruction by maximum
likelihood is hard.
IEEE/ACM Transactions on Computational Biology and
Bioinformatics, 30 (1):0 92–94, 2006.

[Roch, 2010]
Sebastien Roch.
Toward extracting all phylogenetic information from matrices of
evolutionary distances.
Science, 3270 (5971):0 1376–1379, 2010.

[Roch and Sly, 2017]
Sebastien Roch and Allan Sly.
Phase transition in the sample complexity of likelihood-based
phylogeny inference.
Probability Theory and Related Fields, 1690
(1):0 3–62, 2017.

[Santhanam and Wainwright, 2012]
Narayana P Santhanam and Martin J Wainwright.
Information-theoretic limits of selecting binary graphical models in
high dimensions.
IEEE Transactions on Information Theory, 580
(7):0 4117–4134, 2012.

[Stamatakis, 2006]
Alexandros Stamatakis.
Raxml-vi-hpc: maximum likelihood-based phylogenetic analyses with
thousands of taxa and mixed models.
Bioinformatics, 220 (21):0 2688–2690, 2006.

[Tan et al., 2011]
Vincent YF Tan, Animashree Anandkumar, Lang Tong, and Alan S Willsky.
A large-deviation analysis of the maximum-likelihood learning of
markov tree structures.
IEEE Transactions on Information Theory, 570
(3):0 1714–1735, 2011.

[Truell et al., 2021]
Michael Truell, Jan-Christian Hütter, Chandler Squires, Piotr Zwiernik, and
Caroline Uhler.
Maximum likelihood estimation for brownian motion tree models based
on one sample.
arXiv preprint arXiv:2112.00816, 2021.

[Vuffray et al., 2016]
Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov.
Interaction screening: Efficient and sample-optimal learning of ising
Advances in neural information processing systems, 29, 2016.

[Vuffray et al., 2022]
Marc Vuffray, Sidhant Misra, and Andrey Y Lokhov.
Efficient learning of discrete graphical models.
Journal of Statistical Mechanics: Theory and Experiment,
20210 (12):0 124017, 2022.

[Wang and Zhang, 2006]
Yi Wang and Nevin Lianwen Zhang.
Severity of local maxima for the em algorithm: Experiences with
hierarchical latent class models.
In Probabilistic Graphical Models, pages 301–308. Citeseer,

[Yang, 1997]
Ziheng Yang.
Paml: a program package for phylogenetic analysis by maximum
Computer applications in the biosciences, 130
(5):0 555–556, 1997.

[Yatracos, 1985]
Yannis G Yatracos.
Rates of convergence of minimum distance estimators and kolmogorov's
The Annals of Statistics, 130 (2):0 768–774,

[Zwiernik et al., 2017]
Piotr Zwiernik, Caroline Uhler, and Donald Richards.
Maximum likelihood estimation for linear gaussian covariance models.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 790 (4):0 1269–1292, 2017.

In this Section, we prove the following Theorem.
maybe make the intro theorem restatable

Let $\hat{T},T^*$ denote the topologies of two trees with $n$ leaves, where each non-leaf node has degree $3$. Let $\hat{\alpha},\alpha^* \in [0,1]^{n \choose 2}$ denote vectors of pairwise distances that are induced by some tree metric on $\hat{T}$ and $T^*$, respectively.
Also, let $\hat{mu}$ and $\mu^*$ be distributions over the leaves of $\hat{T}$ and $T^*$ when the pairwise

we present an improved algorithm for estimating the distribution of leaves in TV distance when the topology of the underlying tree is unknown. At the core of the argument lies a bound on the total variation distance of two distributions of leaves with potentially different underlying topologies. To motivate the discussion, let's start with some definitions. As always, the true topology is denoted by $T$ and the vector of all the correct pairwise distances is $\alpha$.

Let $i,j,k,l$ be a quartet of four leaves of $T$. We define

\Delta_{ijkl} := \max(\alpha_{12}\alpha_{34}, \alpha_{13}\alpha_{24}, \alpha_{14}\alpha_{23}) - \min(\alpha_{12}\alpha_{34}, \alpha_{13}\alpha_{24}, \alpha_{14}\alpha_{23})

\hat\Delta_{ijkl} := \max(\hat\alpha_{12}\hat\alpha_{34}, \hat\alpha_{13}\hat\alpha_{24}, \hat\alpha_{14}\hat\alpha_{23}) - \min(\hat\alpha_{12}\hat\alpha_{34}, \hat\alpha_{13}\hat\alpha_{24}, \hat\alpha_{14}\hat\alpha_{23})

Let $i,j,k,l$ be a quartet of four leaves of $T$. We say that this is an $\epsilon$-good quartet if

\Delta_{ijkl} \geq \epsilon

A quartet of leaves that is not an $\epsilon$-good quartet is called an $\epsilon$-bad quartet.
Intuitively, if a quartet is good, then it is easy for an algorithm to distinguish which is the correct topology of these four leaves out of the three possibilities. If it is bad, then the topology is very close to being a star and so all three possibilities are roughly equivalent.
One thing to note is that our estimates $\hat{\alpha}$ imply that

|\Delta_{ijkl} - \hat{\Delta}_{ijkl}| \leq \epsilon

for all $i,j,k,l$. Hence, it does not really make a difference whether a quartet is good or bad in $T$ or in $\hat{T}$, since there is only an $\epsilon$-additive error.

We now briefly describe the algorithm that we will use. We will not argue in detail about it's computational or statistical complexity, but instead focus on the quality of approximation that it gives in terms of TV distance. We will see that it is easy to argue about the sample complexity of the algorithm once we have everything else.

The algorithm works as follows: first it finds $\epsilon$-approximations for all the pairwise distances, and also classifies all quartets into $\epsilon$-good or $\epsilon$-bad. Then, it finds a topology $\hat{T}$ and estimates $\hat{\alpha}$ such that the following two properties hold

* $|\alpha_{ij} - \hat{\alpha}_{ij}| \leq \epsilon$

* If a quartet is $\epsilon$-good for $T$ or $\hat{T}$, then this quartet will have the same topology in $T$ and $\hat{T}$.

Our goal will be to prove that these properties are enough to guarantee that the estimated distribution is close enough to the true distribution.
For this purpose, we will prove the following Theorem.

Let $\hat{T}$ be the output of the algorithm with parameter $\epsilon/(2n^4)$.

TV(P,\hat{P}) \leq  \epsilon

The first step to the proof of the Theorem is the following Lemma, which showcases the main ideas needed in the proof.

Let $\epsilon > 0$ and suppose we run the algorithm with accuracy $\epsilon/ n^4$.
Suppose $i,j$ are two leaves that form a cherry in $\hat{T}$ but not in $T$. Let $u$ be their common parent in $\hat{T}$ and suppose that $\hat{\alpha}_{iu} < \hat{\alpha}_{ju}$. Let $\Bar{T}$ be the topology that results from $T$ if we cut leaf $i$ from it's place in $T$ (we also remove it's edge to the parent) and glue it so that it forms a cherry with $j$.

\sum_{x \in \{-1,1\}^n} |f_x^T(\alpha) - f_x^{\Bar{T}}(\alpha)| \leq \frac{\epsilon}{n}

Let $P(i,j) = v_1, \ldots, v_l $ be the path between leaves $i,j$ in $T$, meaning that $v_1 = i , v_l = j$.
We will define a series of topologies, starting with $T^1 = T$. $T^2$ is defined by cutting leaf $i$ from it's current place and splitting edge $(v_3,v_4)$ into two edges $(v_3,w_2),(v_4,w_2)$ and adding an edge $(w_2,i)$. In general, for $k \leq l -2$, we define $T^k$ to be the topology obtained by $T$ by cutting leaf $i$ from it's original place, splitting edge $(v_{2 + i},v_{3 + i})$ into two edges $(v_{2+i}, w_k), (w_k, v_{3+i})$ and adding the edge $(w_k ,i)$. It is clear from the definition that
$T^{l-2} = \Bar{T}$. Clearly, we do not have to define weights on each of these topologies, as we are only interested in the pairing that they induce for the various subsets of leaves. Using triangle inequality, we can write

\begin{equation}\label{eq:first_step}
\sum_{x \in \{-1,1\}^n} |f_x^T(\alpha) - f_x^{\Bar{T}}(\alpha)| \leq \sum_{k = 1}^{l-3} \sum_{x \in \{-1,1\}^n} |f_x^{T^{k+1}}(\alpha) - f_x^{T^k}(\alpha)|
\end{equation}

We will bound each term corresponding to some $k$ separately. Let $r_k$ be the number of quartets that will have different topology in $T^k$ and $T^{k+1}$.
Specifically, we are going to prove that for each $k$

\sum_{x \in \{-1,1\}^n} |f_x^{T^{k+1}}(\alpha) - f_x^{T^k}(\alpha)| \leq \frac{\epsilon r_k}{n^4}

We will prove this inductively. Let's start with the case $k = 1$. We examine which terms in the expressions $f_x^{T^{2}}(\alpha), f_x^{T^{1}}(\alpha)$ are different.  First of all, since all internal nodes have degree $3$, each node $v_i$ of the path has a subtree $U_i$ hanging from it, except $v_1,v_l$. We will examine all even subsets of leaves in terms of which subtrees they intersect. First of all, if a subset of leaves does not contain $i$, then the splitting into pairs is not affected by the change in the topology, since the relative topology of the leaves other than $i$ remains the same. Hence, let $S$ be an even subset that contains $i$. Then $S_i := S\setminus\{i\}$ has odd cardinality. Notice that $S_i$ can be partitioned into the subsets $S_i \cap (U_2 \cup U_3)$ and $S_i \cap \lp(\cup_{j \geq 4} U_j\rp)$.
There are two possibilities:

* $|S_i \cap (U_2 \cup U_3)|$ is odd and $|S_i \cap \lp(\cup_{j \geq 4} U_j\rp)|$ is even. In that case, the leaves in $S_i \cap (U_2 \cup U_3)$ will be paired in the same way in $T^1,T^2$, except one leaf, which will be paired with $i$ in both topologies. The leaves in $S_i \cap \lp(\cup_{j \geq 4} U_j\rp)$ will
be paired the same way in $T^1,T^2$. Hence, the term corresponding to subset $S$ will be the same in $T^1$ and $T^2$ in that case.

* $|S_i \cap (U_2 \cup U_3)|$ is even and $|S_i \cap \lp(\cup_{j \geq 4} U_j\rp)|$ is odd. In that case, there are two subcases:

* $|S_i \cap U_2|, |S_i \cap U_3|$ are both even. In that case, leaves in $S_i \cap U_2$ will be paired the same way in $T^1,T^2$ and the same holds for $S_i \cap U_3$. The leaves in $S_i \cap \lp(\cup_{j \geq 4} U_j\rp)$ will be paired in the same way and one leaf will be left alone and will be paired with $i$ in both $T^1,T^2$. As a result,
the term corresponding to $S$ will be the same in $T^1,T^2$.

* $|S_i \cap U_2|, |S_i \cap U_3|$ are both odd. In that case, the leaves in $S_i \cap U_2$ will be paired the same way in both $T^1,T^2$, with one leaf $u_2 \in U_2$ left alone. Similarly for $S_i \cap U_3$ and one leaf $u_3 \in U_3$. For leaves in $S_i \cap \lp(\cup_{j \geq 4} U_j\rp)$, they will again be paired the same way, leaving one leaf $u_4 \in \cup_{j \geq 4} U_j$ alone. Now, in $T^1$, $i$ will be paired with $u_2$ and $u_3$ will be paired with $u_4$. However, in $T^2$ $i$ will be paired with $u_4$ and $u_2$ with $u_3$.

After this case analysis, it is clear that $S$ will have a different expression in $T^1,T^2$ if and only if $S$ is of the form

S = \{i,u_2,u_3,u_4\}\cup S_2\cup S_3 \cup S_4

with $S_2 \subseteq U_2, S_3 \subseteq U_3, S_4 \subseteq \cup_{j\geq 4} U_j$ and the extra constraint that $U_2$ lies on the subtreee that is disconnected from $i$ if we remove the path from $u_2$ to $i$ and similarly for $U_3,U_4$. This proves first of all that $r_1 = |U_2||U_3||\cup_{j \geq 4} U_j|$. Second, it proves that up to constants

\begin{align}\label{eq:quartet_split}
\sum_{x \in \{-1,1\}^n} |f_x^{T^{k+1}}(\alpha) - f_x^{T^k}(\alpha)|  &= \lp|\sum_{x \in \{-1,1\}^n} \sum_{u_2 \in U_2, u_3 \in U_3, u_4 \in \cup_{j \geq 4}U_j} (\alpha_{iu_2}\alpha_{u_3u_4} - \alpha_{i u_4}\alpha_{u_2u_3}) x_i x_{u_2}x_{u_3}x_{u_4} P_{G\setminus \{i,u_2,u_3,u_4\}}(x) \rp|
\end{align}

where $P_{G\setminus \{i,u_2,u_3,u_4\}}(x)$ is the probability distribution of the rest of the leaves when the paths that belong to the quartet $i,u_2,u_3,u_4$ are removed. Notice that this topology will be the same regardless of whether we remove it from $T^1$ or $T^2$ and also that it is indeed a probability distribution. Now, the only thing we need to check in order to bound this quantity is that the quartet $i,u_2,u_3,u_4$ is bad. Suppose for contradiction that we have
\Delta_{iu_2u_3u_4} = \Omega(\epsilon/n^4)
We will figure out the constants later
Then, by the approximation guarantee of the algorithm

\begin{equation}\label{eq:posi}
\hat\Delta_{iu_2u_3u_4} = \Omega(\epsilon/n^4)
\end{equation}

We have chosen $i$ so that $\hat\alpha_{iu} < \hat{\alpha}_{ju}$ in the estimated model $\hat{T}$, so this implies that $j,u_2,u_3,u_4$ is also a good quartet, meaning

\begin{equation}\label{eq:posj}
\hat\Delta_{ju_2u_3u_4} = \Omega(\epsilon/n^4)
\end{equation}

Now, inequalities (<ref>) and (<ref>) give us a contradiction. The reason is that they suggest that both $i$ and $j$ are correctly positioned in $T$ relative to $u_2,u_3,u_4$ (correctly here means in terms of $\hat{T})$. But their relative positioning $i,j$ in $T$ is different and we know that they are siblings in $\hat{T}$, which means that
they should have the same positioning relative to any quartet. This leads us to a contradiction. This means that $iu_2u_3u_4$ is a bad quartet, hence $\Delta_{iu_2u_3u_4} = O(\epsilon/n^4)$. This implies that we did not violate any good quartets by changing from $T^1$ to $T^2$. Thus, equation (<ref>) implies

\begin{align*}
\sum_{x \in \{-1,1\}^n} |f_x^{T^{k+1}}(\alpha) - f_x^{T^k}(\alpha)|  &= \lp|\sum_{u_2 \in U_2, u_3 \in U_3, u_4 \in \cup_{j \geq 4}U_j} \sum_{x \in \{-1,1\}^n} (\alpha_{iu_2}\alpha_{u_3u_4} - \alpha_{i u_4}\alpha_{u_2u_3}) x_i x_{u_2}x_{u_3}x_{u_4} P_{G\setminus \{i,u_2,u_3,u_4\}}(x) \rp|\\
&\leq \sum_{u_2 \in U_2, u_3 \in U_3, u_4 \in \cup_{j \geq 4}U_j} \sum_{x \in \{-1,1\}^n} \Delta_{iu_2u_3u_4}  P_{G\setminus \{i,u_2,u_3,u_4\}}(x) \\
&\leq \frac{\epsilon}{n^4} |U_2||U_3||\cup_{j \geq 4} U_j| = \frac{\epsilon r_1}{n^4}
\end{align*}

Hence, the base case of the induction is complete. Now, let us try to complete the induction. Suppose the statement holds for all $k < m$. We will prove it for $ k = m$.
First of all, we examine which terms in the expressions $f_x^{T^{m+1}}(\alpha), f_x^{T^{m}}(\alpha)$ are different. It is not hard to see that similarly to the analysis for the base case, we have that a subset $S$ has different expression if and only if it can be written as

S = \{i, u_2, u_3, u_4\} \cup S_2 \cup S_3 \cup S_4

where $u_2 \in \cup_{j \leq m } U_j, u_3 \in U_{m+1}, u_4 \in \cup_{j \geq m+2}U_j$ and $|S_2|,|S_3|,|S_4|$ even any lying on the subtrees that result when removing the paths of the quartet $i,u_2,u_3,u_4$ from $T^m$. This shows that $r_m = |\cup_{j \leq m } U_j||U_{m+1}||\cup_{j \geq m+2}U_j|$. It also follows from this characterization that
the sets of quartets that change in each step of moving $i$ are disjoint from each other.
This means that

\sum_m r_m \leq n^3

since the total number of quartets that $i$ is involved in is $n^3$. Similar to the base case, we can write

\begin{align*}
\sum_{x \in \{-1,1\}^n} |f_x^{T^{m+1}}(\alpha) - f_x^{T^m}(\alpha)|  &= \lp|\sum_{u_2 \in \cup_{j \leq m} U_j, u_3 \in U_{m+1}, u_4 \in \cup_{j \geq m+2}U_j} \sum_{x \in \{-1,1\}^n} (\alpha_{iu_2}\alpha_{u_3u_4} - \alpha_{i u_4}\alpha_{u_2u_3}) x_i x_{u_2}x_{u_3}x_{u_4} P_{T^m\setminus \{i,u_2,u_3,u_4\}}(x) \rp|
\end{align*}

Notice that $P_{T^m\setminus \{i,u_2,u_3,u_4\}}$ is still a true distribution over the remaining leaves, since $i$ is disconnected from the topology and the remaining topology is the correct one. Using the same argument as in the base case, we can prove that by moving $i$ one step, we do not violate any of the good quartets(otherwise $j$ would violate them as well). Hence, we conclude that

\sum_{x \in \{-1,1\}^n} |f_x^{T^{k+1}}(\alpha) - f_x^{T^k}(\alpha)| \leq
\frac{r_m \epsilon}{n^4}

and the induction proof is complete.
Now, from inequality (<ref>) we obtain

\begin{align*}
\sum_{x \in \{-1,1\}^n} |f_x^T(\alpha) - f_x^{\Bar{T}}(\alpha)| &\leq \sum_{k = 1}^{l-3} \sum_{x \in \{-1,1\}^n} |f_x^{T^{k+1}}(\alpha) - f_x^{T^k}(\alpha)|\\
&\leq \frac{\epsilon}{n^4} \sum_k r_k \leq \frac{\epsilon}{n}
\end{align*}

We now move on with the proof of Theorem REF. The idea is to apply Lemma <ref> repeatedly, starting from $T$. Each time we reconstruct some cherry of $\hat{T}$ or a generalized cherry(cherry of two internal nodes whose subtrees already agree with $\hat{T}$). It is easy to see that a total of $n$ of these operations suffice to move from $T$ to $\hat{T}$. The challenge is that in every intermediate step other than the first one, the lipschitzness will actually not correspond to a true probability distribution. Therefore, we have to use the technique that was developed in the previous Section for fixed topology. That way we can control the errors and show that if they are small enough, we still get a good bound on the TV distance.

We will define a sequence of graphs $T_1,\ldots,T_{n-1}$ with $T_1 = T$ and $T_{n-1} = \hat{T}$. The general way of defining the sequence is as follows:
at every step $i$, we maintain that some internal nodes of $T_i$ might have a subtree that has identical topology with the one in $\hat{T}$. We treat this subtree as nonexistent for the problem of selecting the next cherry. By pruning these subtrees, we are left with a tree $\Bar{T_i}$. Then, we
pick two leaves $i,j$ that are cherries in $\hat{T}$ but not in $\Bar{T_i}$ (such a pair should exist, otherwise a larger subtree would have to be pruned). Suppose without loss of generality that $i$ has a weaker link than $j$ in $\hat{T}$ (the precise definition is similar to the one in Lemma <ref>).
Then, we define $T_{i+1}$ to be the tree that arises from $T_i$ if we cut $i$ from $T_i$ and glue it so that it becomes a cherry with $j$. During this process, any subtrees that are hanging from $i$
will also be transferred together with $i$. It is clear that $T_{i+1}$ is more similar to $\hat{T}$ than $T_i$ and after $n$ of these operations we will actually reach $\hat{T}$. The reason is that the total size of all the subtrees that agree with $\hat{T}$ increases by $1$.
We will bound the error in each of these steps separately. Lastly, we will substitute $\alpha$ with $\hat{\alpha}$ using the argument we have for a fixed topology and this will conclude the proof.

In order to go from topology $T_i$ to $T_{i+1}$ we use a procedure similar to the one defined in Lemma <ref>, by moving a leaf edge by edge until it reaches the correct spot. Hence, we have a sequence $\{T_i^j\}_{j = 1}^{l_i}$ with $T_i^1 = T_i, T_i^{l_i} = T_{i+1}$. Hence, for each step of the transformation, we can index it as $(i,j)$, if the current tree is $T_i^j$.

Our argument will be an induction on the total number of quartets that have been altered since our transformation began.
Clearly, when $i$ or $j$ increases, this number increases. We will prove that for any step $(i,j)$ in that process, if $K_{ij}$ is the total number of quartets that have been altered until that point in the transformation, we have

\sum_{x \in \{-1,1\}^n} |f_x^T(\alpha) - f_x^{T_i^j}(\alpha)| \leq \frac{\epsilon K_{ij}}{n^4}

The base case of the induction was  proved in Lemma <ref>. Suppose it holds for all $(i',j')$ up until $(i,j)$. We will prove it for $(i,j)$.
We have that

\begin{equation}\label{eq:Kij}
\sum_{x \in \{-1,1\}^n} |f_x^T(\alpha) - f_x^{T_i^j}(\alpha)| \leq
\sum_{k <  i} \sum_{m \leq l_k}\sum_{x \in \{-1,1\}^n}  |f_x^{T_k^{m+1}}(\alpha) - f_x^{T_k^m}(\alpha)| + \sum_{m \leq j} \sum_{x \in \{-1,1\}^n}  |f_x^{T_i^{m+1}}(\alpha) - f_x^{T_i^m}(\alpha)|
\end{equation}

Let's pick some $k < i, m \leq l_k$. The case $k = i$ is identical.
Let $u,v$ be the cherry picked at the step $k$ with $u$ moving towards $v$.

We would like to bound each individual term of the sum similarly to the way we did it in Lemma <ref>. However, the problem is that  the difference
$|f_x^{T_k^{m+1}} (\alpha) - f_x^{T_k^m}(\alpha)|$ does not necessarily correspond to a probability distribution. The reason is that part of the topology of $T_k$ corresponds to $T$ and part of it to $\hat{T}$ (only at the first step this isn't true). Hence,
we need to handle these errors with extra care. First of all, for a given $m$, we know that the expressions $f_x^{T_k^{m+1}} (\alpha) , f_x^{T_k^{m}} (\alpha) $ differ only in terms that involve some quartet $i,u_2,u_3,u_4$, where $u_2,u_3,u_4$ are defined exactly as in Lemma <ref>. Also, a similar argument shows that all these are bad quartets. This enables us to write

\begin{align*}
\sum_{x \in \{-1,1\}^n} |f_x^{T_k^{m+1}}(\alpha) - f_x^{T_k^m}(\alpha)|  =\\
=\sum_{x \in \{-1,1\}^n} \lp|\sum_{u_2 \in \cup_{j \leq m} U_j, u_3 \in U_{m+1}, u_4 \in \cup_{j \geq m+2}U_j}
\sum_{x \in \{-1,1\}^n} (\alpha_{iu_2}\alpha_{u_3u_4} - \alpha_{i u_4}\alpha_{u_2u_3}) x_i x_{u_2}x_{u_3}x_{u_4} P_{T_k^m\setminus \{i,u_2,u_3,u_4\}}(x) \rp|\\
\leq \sum_{x \in \{-1,1\}^n} \frac{\epsilon}{n^4} \sum_{u_2 \in \cup_{j \leq m} U_j, u_3 \in U_{m+1}, u_4 \in \cup_{j \geq m+2}U_j}
\sum_{x \in \{-1,1\}^n}
|P_{T_k^m\setminus \{i,u_2,u_3,u_4\}}(x)|
\end{align*}

Now, as we explained, $P_{T_k^p\setminus \{i,u_2,u_3,u_4\}}$ is not a true probability distribution, hence we cannot get rid of the absolute values.
However, we do have some information about the expression of $P_{T_k^m\setminus \{i,u_2,u_3,u_4\}}$. Indeed, it is generated by a tree like $T_k^m$ with the quartet $i,u_2,u_3,u_4$ removed. This breaks $T_k^m$ into disconnected subtrees, but the expression on each subtree is still not a probability distribution. However, we can do the following: reverse the cut-paste process in each component separately, using the exact same order. Then, you end up with a true distribution, not the original one, but still one that is defined on the disconnected tree topology. Moreover, the number of quartets that are displaced using this process is less than the number that was
displaced using the original process until time $k,m$. Hence, we can use the inductive hypothesis to prove

\sum_{x \in \{-1,1\}^n} |f_x^{T_k^{m+1}}(\alpha) - f_x^{T_k^m}(\alpha)|  \leq \frac{\epsilon r_{km}}{n^4} (1 + \frac{\epsilon}{n^4} K'_{ij}) \leq 2 \frac{r_{km}\epsilon}{n^4}

where we use $K'_{ij}$ to denote the number of misplaced quartets in the tree with the disconnected components and $r_{km}$ is the number of misplaced quartets in the current step from $T_k^m \to T_k^{m+1}$. Finally, using Equation (<ref>) we conclude that

\sum_{x \in \{-1,1\}^n} |f_x^T(\alpha) - f_x^{T_i^j}(\alpha)|  \leq 2\frac{\epsilon}{n^4} (\sum_{k<i, m\leq l_k} r_{km} + \sum_{m \leq j} r_{im}) = 2\frac{\epsilon K_{ij}}{n^4}

Hence, the inductive step is complete.
Applying this result for $T_n^{l_n}$ we get the result of the Theorem.

The figure illustrates how we transform the phylogenetic tree from (a) to (g) by shifting subtrees to form cherries.
(b) – (d) fixes the cherries $\{e,h\}$ (see blue edges).
(d) – (e) fixes the parents of the cherries $\{a,b\}$ and $\{f,g\}$ (see orange edges).
(e) – (f) fixes the parents of the cherries $\{c,d\}$ and $\{e,h\}$ (see red edges).

Appendix Fig 6

Appendix Fig 7

Appendix Fig 8

Appendix Fig 9

Appendix Fig 10

Appendix Fig 11

Appendix Fig 12