Sample Complexity of Branch-length Estimation by Maximum Likelihood
Authors: David Clancy Jr.
Hanbaek Lyu
Sebastien Roch
Venue: ICML 2025 poster (2025)
Keywords: branch length estimation
statistical estimation on networks
coordinate maximization
sample complexity
Primary area: probabilistic_methods

Abstract: We consider the branch-length estimation problem on a bifurcating tree: a character evolves along the edges of a binary tree according to a two-state symmetric Markov process, and we seek to recover the edge transition probabilities from repeated observations at the leaves. This problem arises in phylogenetics, and is related to latent tree graphical model inference. In general, the log-likelihood function is non-concave and may admit many critical points. Nevertheless, simple coordinate maximization has been known to perform well in practice, defying the complexity of the likelihood landscape. In this work, we provide the first theoretical guarantee as to why this might be the case. We show that deep inside the Kesten-Stigum reconstruction regime, provided with polynomially many $m$ samples (assuming the tree is balanced), there exists a universal parameter regime (independent of the size of the tree) where the log-likelihood function is strongly concave and smooth with high probability. On this high-probability likelihood landscape event, we show that the standard coordinate maximization algorithm converges exponentially fast to the maximum likelihood estimator, which is within $O(1/\sqrt{m})$ from the true parameter, provided a sufficiently close initial point.

Sample Complexity of Branch-length Estimation by Maximum Likelihood
David Claney, Jr."
Hanbaek Lyu"
Sebastien Roch
Abstract
One seeks estimate 0 E + such that
We consider the branch-length estimation prob- lem on bifurcating tree: a character evolves along the edges of binary tree according to a two-state symmetric Markov process, and we seek to recover the edge transition probabilities from repeated observations the leaves. This problem arises in phylogenetics, and is related to latent tree graphical model inference. In general, the log-likelihood function is non-concave and may admit many critical points. Nevertheless, simple coordinate maximization has been known to per- form well in practice, defying the complexity of the likelihood landscape. In this work, pro- vide the first theoretical guarantee as why this might be the case. We show that deep inside the Kesten-Stigum reconstruction regime, provided with polynomially many m samples (assuming the tree balanced), there exists universal pa- rameter regime (independent of the size of the tree) where the log-likelihood function strongly concave and smooth with high probability. On this high-probability likelihood landscape event, we show that the standard coordinate maximiza- tion algorithm converges exponentially fast to the maximum likelihood estimator, which is within OL1/vm) from the true parameter, provided a sufficiently close initial point.
i E arg max E(0; 10;211.1 21, (i,...,,mm) Im); where OEE
E(O; ((0:41,-00 Fm
log Po(o)))
(I)
which maximizes the likelihood of seeing the observed data.
Classical theory (Cramér, 1946; Wald, 1949) tells us that whenever the population landscape (i.e. the oo limit)
B(((O)) Ex~Pa- log (o())
is concave and the likelihood is maximized at a unique point that agrees with the true parameter 0", then a good esti- mator of 0" Much of the rigorous theoretical foundation of MLE assumes that one can extend this population landscape to the empirical landscape ((0) ø ................................ Im). This relies on being able to approximate [[[(O)] by 0(0; .mm) so that optimizing ((0:r1,... Zm) approximately finds 0". See (Li & Babu, 2019). However, many natural MLE prob- lems such as those arising from mixture models (Murphy, 2012) involve maximizing non-concave log-likelihoods.
A similar story arises in the optimization literature, where one typically minimizes (hopefully convex) loss function. Many natural questions on that side are non-convex due to either the loss function being non-convex or having to optimize over a non-convex parameter space, such as princi- pal component analysis and best subset selection problems (Beale al., 1967: Hocking & Leslie, 1967). Within the class of non-convex problems, there many examples of benign non-convex problems which, while not actually convex, possess sufficiently nice structures that make them manageable. These include some additional symmetries, such as those phase retrieval (Sun et al., 2018) and dic- tionary learning (Arora et al., 2014; Bai et al., 2019), or the loss function possesses sufficient regularity (e-g. the Polyak- Lojasiewicz (Polyak, 1963; Lojasiewiez, 1963) condition) that gradient-based methods converge linearly despite non-convexity (Karimi et al., 2016). See (Jain al., 2017; Zhang et al., 2020) for general overview.
1. Introduction
Maximum likelihood estimation (MLE) for parameter esti- mation is fundamental technique in statistics and machine learning. For this, one has parametric probabilistic model (Po: 0 E @ C. Rd) and some data r., I' assumed to be i.i.d. observations from Pg- for some unknown 0" E e.
'Equal contribution 'Department of Mathematics, Uni- versity of Wisconsin-Matisonn. WI, USA. Correspon- dence David Clancy, Jr. <delancy@@ weet@@maat...eeee.. Hanback Lyu <hlyu@ Chlyu@math.we www.u@@aa...iiicd...... wisc, Sebastien Roch <roch@ math. wisc.edu'.
Here we investigate a specific maximum likelihood estima- tion problem along the following lines. Even though the population and empirical landscapes may non-concave
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
6" mm)
(Empirical likelihood landscape, Thm. 3.2) With enough samples (polynomial in the size of the tree in the balanced case), the empirical log-likelihood is strongly concave and smooth on an Loe box around the true parameter 0* with large probability.
(Statistical estimation guarantee, Thm. 3.3) For any fixed problem size, the MLE is O (LL//mm-co/ conssisttt with the true parameter with arbitrarily large probability.
(Computational guarantee of coordinate maximization, Thm. 3.4) The iterates of the coordinate maximization algorithm (Alg. 1) converge exponentially fast to the confined MLE Ø with rate independent of the tree, provided sufficiently close initial point.
Figure 1. A cartoon depiction of non-concave 2D likelihood land- scape (left) and contour plot (right). Thm. 3.2 and 3.3 asserts that the empirical likelihood landscape has well-conditioned strongly concave landscape over a box @n(6) size order around the true parameter 0* Thm. 3.4 asserts that coordinate maximization initialized in the box converges to the MLE Og in ((1) iterations.
While we focus on a particular likelihood function and a partieular optimization algorithm, general approach re- lies on three essential ingredients for analyzing such non- concave MLE problems. Namely:
and contain numerous local (or even global) maximizers, under particular assumptions one can still extract a semi- global region inside which there a unique maximizer and all other local maximizers lie strictly outside this region. This semi-global region is one that does not shrink the sample size or the problem dimension grows large, but is not the entire parameter space θ either. If this is the case, then one should be able to recover the true parameter 0* using standard likelihood maximization techniques and assess the incurred statistical and computational errors rigorously.
Step 1. Show that the population likelihood E[{(0)] is strongly concave and smooth some parameter space
B S @ containing the true parameter 0"
Step 2. Show that entries of the population Hessian vary in Lipschitz manner with respect to the parameter; and
Step 3. Show that the per-sample empirical Hessian has uniformly bounded spectral norm almost surely.
More specifically. along this line of approach, we ana- lyze the MLE problem for branch-length estimation (Guin- don & Gascuel, 2003), arising in phylogenetics, under the Cavender-Farris Farris-Neyman model (Neyman, 1971; Farris, 1973; Cavender, 1978). Roughly speaking, it is the prob- lem of estimating the probabilities of corruption in a noisy channel along the edges of a communication tree, where we are only allowed to observe signals at the tips of the tree (see Sec. 2). While arising in phylogenetics, it has applications to theoretical computer science, signal process- ing, and statistical physics (Mossel, 2022). This problem is hard as the population log-likelihood function admits expo- mentially many critical points (in the problem dimension) and there are instances where the empirical log-likelihood has multiple global maximizers. We work deep inside the Kesten-Stigum reconstruction regime (Kesten & Stigum, 1966; Bleher et al., 1995; loffe, 1996) where the corruption probabilities are sufficiently small so that signal at internal nodes can be approximated with good accuracy from just observing the signals at the leafs.
These conditions are enough show that, with arbitrarily large probability, with enough samples m., the empirical like- lihood landscape concentrates around the population likeli- hood landscape on B with high probability. Hence, on this high-probabbiltty event, the empirical likelihood landscape restricted on B looks 'benign', and standard algorithms for computing MLE, initialized in B, converges rapidly to a parameter i that is within (lI//m) from the true param- eter. In short, the Lipschitz condition on the entries of the Hessian allows us to control the fluctuations of the eigen- values of the Hessian in a non-trivial region around the true parameter. One can then use a uniform version of matrix concentration (Lemma 4.5) to turn this local behavior at points to the desired semi-global statement around 0"
1.2. Related Works
The model we analyze is the Cavender-Farri--eyyne (CFN) model (Neyman, 1971; Farris, 1973; Cavender, 1978) used to study molecular evolution along evolutionary tree.
1.1. Contribution
It has been a long-standing open problem to establish rigor- ously conditions under which standard gradient/coordinale descent algorithms for the maximum maximum-likclihood principle can solve the branch-length estimation problem (Felsenstein,
For this branch length estimation problem, we establish the following results under some assumptions stated later on (see Fig. 1 for illustrations):
2

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
Heatmap of ((0) with m= 2, 4
methods we need high probability statements for the Hes- sian uniformly around the true parameter. Uniform matrix concentration requires us to obtain reasonable bounds on the derivative of the Hessian (as a function of the parameter 0) not covered in (Clancy, Jr. et al., 2025a). This implies that the empirical MLE is close to the true parameter with large probability. Furthermore, we analyze a coordinate up- date algorithm (see Alg. 1) to show that a commonly used optimization algorithm converges to the MLE exponentially fast, provided a sufficiently close initial point.
0.0
-0.2
-14
Perturbation in (O.
1.6
-0.4
-0.6
2.0
-0.8
-0.8
-0.6
-0.4
-0.2
Perturbation in (1. 1. 0.0.0"
Figure 2. A 2D slice of SD 2-sample empirical log-likelihodd f(0; o _² containing 0" on tree with 4 leaves.
2. The Branch-length Estimation Problem
2.1. Problem Statement
Consider a tree = EV, where all nodes have either degree or 3. Information transmitted from an internal root p to the leaves where each edge can corrupt the signal. More precisely, the root node p is assigned uniform spin op E {+1), this spin is propagated to the leaves where, independently, across each edge = {u, v} the signal is changed on + a, with some probability σ.). Equivalently, a evolves along the edges according to the symmetric two-state inhomogeneous Markov chain with transition matrices (Poje E E))
1981). The corresponding joint likelihood function in gen- eral is non-concave, admitting potentially many (complex) critical points (Gareía Puente al., 2024) for generic data g()), Notably, Steel (1994) provided an explicit example where there are multiple global maximizers to (2) with two samples on the tree with four leaves, two internal nodes, and five edges. A 2D slice of the 5D likelihood function is shown in Figure 2, which is already non-concave despite the small tree size and projection.
= =Pee of
Despite all these challenges, optimization of the likelihood function has proven remarkably effective in practice. For example, Guindon & Gascuel (2003); Guindon et al. (2010) developed PHYMI., a coordinate-ascent algorithm that per- forms well empirically, even with small number of co- ordinate updates. Other popular likelihood-based methods include RAxML (Stamatakis, 2014) and IQ-TREE (Nguyen et al., 2015). However, until today, it remains unclear as to why this method works well and there has not been very much theoretical understanding of the optimization land- scape of the MLE.
P.
1 Pc Pe
Pe Pe
1+ 0
A
Here 0 = (0.i E E) is convenient reparametrization of the parameter space. While the possible values for Og E [-1, 1]. we will focus on the "ferromagnetic regime" 0 E 1 where spins at neighboring vertices are positively correlated. That is, it is more likely that there is no signal corruption than there is corruption across each edge.
The problem are interested in is to recover the true un- known parameter 0* from repeated, independent observa- tions of the signals at the leaves of the tree. Namely, let L denote the set of all leaves in the unrooted binary tree T and suppose we have m independent samples o()),.. ,(),....,off (m)) from the process as described above sampled from the true model Før. We only get to observe the signals the leaves, which we denote as o = (al E L) for = 1...., m. The goal is to estimate the true parame- ter 0" from these leaf observations ((1), . This equivalent to the classical branch-length estimation problem (Felsenstein, 1981), as can view the true parameter 0 monotonic function of the 'length' 1 of the edge along which there is constant rate (in continuous time) of mutation.
Recent work in statistical estimation theory has highlighted the importance of analyzing the geometric structure of like- lihood landscapes (see, e.g., (Ma et al., 2020; Chen & Chen, 2019; Chi et al., 2019)). Very recently, Clancy, Jr. et al. (2025a) showed that the likelihood landscape of the branch length estimation problem in the population limit is very well-conditioned in a noxhhhigbbor of the true param- eter of size (1). Their population likelihood landscape result is an important building block of the present work on the empirical likelihood landscape and optimization for finding the MLE.
The paper (Clancy, Jr. al., 2025a) provides bounds for the eigenvalues of the population Hessian in an _ neighborhood of the true parameter 0" which is just Step of our three-step program. There are challenges in establish- ing Steps and 3. Using the population Hessian, it is easy to obtain high probability statements for the empirical Hessian for a fixed parameter 0 however, to do coordinate update
With lea observations o (L)),.... (mm) Ic, we seek to find the maximum likelihood estimator (MIE) as
ÓMLL E arg max {(0: (())(11) L,, ((/))1))) (2)
0E[-1.1]
3

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
To simplify the notation, throughout we drop the explicit reference the leaves in all likelihoods.
A1 (Parameter regime). Assume that 0* E (6))) and 0
(6)). Moreover, the constants C4 > C3 > c3 > cg satisfy C4 2 2c4.
Here we consider the phylogenetic tree T to be fixed and known so that the MLE problem above is only optimizing over the edge-length parameter and not the tree T. In general, one is also interested in optimizing over the phylo- genetic tree T in the MLE (2); doing so introduces further complications of a combinatorial nature. In particular, this more general problem is known to be NP-hard in the worst case (Chor& & Tuller, 2006; Roch, 2006). The work of (Roch & Sly, 2017) (together with the results of (Daskalakis et al., 2011)) shows that an ad hoc polynomial- compute the true parameters with high probability when- ever the edge lengths take values in a lattice eZE, under optimal sample complexity. This present article can be seen as step towards understanding the properties of optimiza- tion approaches. specicically deep inside the Kesten-Stigum reconstruction regime (and without the additional lattice constraint). Many other algorithms with theoretical guaran- tees are known for reconstructing phylogenetic trees and their branch lenghts (see, e.g., (Steel, 2016; Warnow, 2018) and references therein).
We will frequently say 0 or i satisfy (3) and (4), respec- tively, which means that these parameters belong to the sets defnned in these equations.
3.2. Comments on Notation
Before continuing, we introduce the following convention that is used throughout the article. Given any non-negative function fa 0) depending on the signals o = (aws u E T) and the estimator O Oo satisfying Assumption A1, we write Eg- [f 0)] = O for some o E R to mean the there exists a K (c3, C2 C4, C4) E (0, oo) and 60 = (c C3, c1, C1) such that
algorithm can
Eg- [1 (c,00] S K8
sup (0.0)E.,
The constants K K(c3; C3, E (0) and 8u 5u Ca, Ca. C2) depend on the constants appear- ing in Assumption A1, but otherwise independent of both the size and topology of the tree T.
3. Statement of Results
We formally state our main results in this section. We also sketch the proofs. Detailed proofs are in the appendix. We begin with some assumptions.
We will similarly write f(or, θ) = (88) if there exists a constant K = K K(e3, C3, e4, C4) oo) and & = S0(Cs, C2, ca. Ca) such that for all E (0, dol and (0. 0) E Oo x Oo
3.1. Assumptions
Po. (o(o, S ((8)) = =1
Our analysis operates under the assumption that we are well within the Kesten-Stigum reconstruction regime (Kesten & Stigum, 1966; Bleher al., 1995; Ioffe, 1996), that is, roughly speaking that mutation probabilities are sufficiently small that an ancestral state can be reconstructed with better- than-random accuracy.
Here we remind the reader that Og T are sets that depend on 5. We similarly use (265)) for analogous statements in- volving the lower bounds of K and use O(5²) for the funcitons that are both ((8)) and ((8m).
Throughout the paper, constants are numbered by the equa- tion in which they appear. We introduce the following re- stricted parameter spaces that depend on
3.3. Empirical Maximum Likelihood Landscape
Our first main result concerns high-probability characteri- zation of the landscape of the empirical -og-likeldhood func- tion in (1). Namely, we establish that is O ((t-')-strongly concave and
Definition 3.1 (Restricted parameter spaces). Let C1 > C > C3 > C4 > 0 fixed constants. For a fixed 5 > 0, define two subsets (o) _ 66) c [-1, by
with probability 1 - e inside a T -bx with universal (tree-independent) diameter (()) around the true parameter 0* provided the number of sam- ples m large enough.
On( = { (0.- =1 -2pe)EER czd S Pc S CaôVe Ve E E
Theorem 3.2 (Finite-sample sample ligeliiel landscape: strong concavity and smoothness). Let ô be smaller than some universal constant and let H denote the Hessian of the m-sample nigliikll function E in (1). Fix e E (0, 1).
= -2Cgō, -2cz5
(3)
(n) = { (0. = 2fc)
cad S S Ve Ve E E
E
Then there exists constants C₁ > 0, Co > Co > s.t. if
= [1 11-201 -2C 8.
(4)
m N (C5 dimmi))s log(s-1)
(5)
4

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
then for any binary tree T, and 0' E =.,()).
nice structure of being strictly concave when restricted to single branch length Og for E (see Lem. 4.2). Thus, it is natural to cycle through the branch lengths and optimize one at time, maximizing the me--imensioonal restricted likelihood function. This yields the following "cyelic co- ordinate maximization" algorithm for computing the MLE 0- Namely, given our estimate 02 = (0 e E E) after iterations, our algorithm proceeds by optimizing for single branch length 0k:e by
Po. (CC66- <
inf Amin (H)))
(6)
0 @E)
I sup Xmax (()))) - -Co--1 2 21-E. (c
The required sample complexity for Theorem 3.2 grows exponentially in the diameter of the tree T, which can be as small as O) when the tree is wwell-balanced'. In such case, Theorem 3.2 below establishes a polynomial sample complexity to obtain a strongly concave and smooth optimization landscape for the MLE problem with high probability. To the best of our knowledge, this is the first re- sult in the literature establishing strong regularity properties of the maximum likelihood landscape for the branch length optimization problem with polynomial sample complexity.
0k+1;e - arg max m J (=:c((), (0), 8E1-1,11
where
(8)
m
Reze (0) = m Σ ((0++1::--1, 0
θ 0kiky- == (Okzi, 0k.t1. Bk-z)
assuming that we label the edge set E as integers from 1 through [F]. The one-dimensional objectives (0) in (8) are known to be strictly concave (Fukami & Tateno, 1989) and they have a unique maximizer in (-1,1) at a unique critical point:
To establish such a result, we use a uniform version of ma- trix Bernstein's s inequality (Lemma 4.5) to show that the Hessian of the empirical log- log-likelihood function is concen- trated near its expectation uniformly over the box () with high probability. Then the assertion will follow from the population landscape result in Lemma 4.4 below.
k:e (0) = 0.
3.4. Statistical and Computational Guarantees
Hereafter, we will denote a generic global maximizer of the empirical log-likelihood function E(-) (in (I)) over (6) (which always exists) by 0" A particular consequence of Theorem 3.2 is that i" is uniquely determined with high probability and enough samples. In Theorem 3.3 below, we prove a stronger result that with high probability, in addition to the nice geometry of É(-) on the box, the MLE i is 1/ /m-cossistent estimator of the true parameter 0" with high probability. This consistency (up to a constant depending on 2) does not depend on our choice of norm on E for any fixed tree. We write || for the -2-norm of a vector.
The unique zero of the above critical -point equation can be found rapidly by using standard rero-finding algorithms (e.g., (Brent, 2013)). See Alg. in Appendix A for a de- tailed implementation of the algorithm. See e.g. (Guindon & Gascuel, 2003) for a practical implementation of this type of algorithm.
Despite the popularity and the empirical success of the coor- dinate maximization algorithm above, however, due to the non-concavity of the optimization landscape, there has been no guarantee about the convergence of this algorithm the maximizer of & or the true parameter 0" In Theorem 3.4 below, we establish that the coordinate maximization algo- rithm above (8) converges exponentially fast to the MLE Ø which is within C(T, -1/2 from the true parameter 0*, provided the initial estimate @ within O()) from the true parameter 0 in Le norm.
Theorem 3.3 (Statistical estimation guarantee). Assume the hypothesis of Theorem 3.2 holds. Let Eg denote the event in (6). Fix e E (0, 1). Then there exists a constant C7 > 0 such that, provided m
Theorem 3.4 (Statistical and computational estimation guar- antee). Suppose the hypothesis of Theorem 3.3 holds. Let (0x) denote the sequence of estimated parameters gen- erated by the coordinate maximization algorithm (see Alg. (7)
Pe- (Ea n { 110 -0 s Cr CLV/LE//mogll (E)/=)))
2 1 1-133 3E.
1) with the initial estimate Ou with ||0, - 0' = O(6). Then with probability at least 1 3e, for all k: 2 O.
Now that we know the MLE 0" is close to the true pa- rameter O* with high probability, we turn our attention to how we can compute the MLE Ø' from the observed samples o')),..., ( restricted to the leaves. While the log- likelihood function e in (1) non-coneave, it has the
Öo
(1
Ca h-1
110" - -Ou11
100
0 (10)
Co
Co
5

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
In particular,
the magnetization at the root of Tu as Zu (0;00) by (12)
Zu = (ō. +1 +1 = =LL.)
0x s CTV (
(11)
pg (ā 111 = Ll.):
statistical error
where ē is a random spin configuration on T sampled from Pa.
Co
Co Co
(k-1)/2
100
doll
CB
If consists of a single node u, then Z, on as get to observe the spin at u. In general, Zu is random variable de- termined by the spin configuration ot., on the leaves of To and takes values in [-1, The magnetization Zu at a node u also depends implicitly on the choice of the descendant subtree Tu. In (Borgs al., 2006), Borgs et al. established that the magnetization of root on any tree can be obtained an explicit function of the magnctizations of the descen- dant subtrees for all the children and the edge parameters. We recall this in the appendix, see (29) in particular.
ccmmputational ervor
is important to note that the exponential rate of con- vergence of the coordinate maximization in Theorem 3.4, Öo Co E (0, 1), is a universal constant that does not depend on the tree T and also the parameter ö (as long as is less than some universal constant in Thm. 3.2). This means that the computational error for computing the MLE can be made to be less than desired tolerance within C'log e e-1 iterations for some universal constant C. This gives some theoretical support for the empirical fact that coordinate maximiza- tion algorithm performs well empirically, even with small number of coordinate updates (Guindon & Gascuel, 2003; Guindon et al., 2010).
Consider the log- likeliiodd function {(;; ) in (1) and two edges E = {a, y) and f = {u, v} E E(T). Let Ta and Tú denote the subtrees rooted at xr and y (resp.) obtained by removing e from the edges of T. Suppose that
((T,)) and that u is closer to y than v, i.e., d(u, y) < d(e, v). Enumerate the vertices on the path from to u by =
It would be of interest to show that the assumption that |10 1 O(5) can be dropped; however, our proof needs the initial iterate to be sufficiently close to 0* in order to know that the empirical Hessian is smooth and strongly concave with high probability (Thm. 3.2) and that the subsequent iterates also lie in this "good" region.
VN UN -N-1..... V/, yo u and set y-1 = and yN+1 = z. Note that for each vertex yj with j E (o..... NY. the vertex yj has degree three and so has neighbors {リ₃- Mj+t, wr} for some other vertex wy. Accordingly, we have T. Twy+ and T, = T yN and for every node in T.p the descendant subtree T, is with respect to the root x:
4. Sketch of Proofs
The following key lemma relates the derivatives of the log- likelihood and the magnetizations.
4.1. Characterizing the Likelihood Landscape Using Magnetization
Lemma 4.2 (Likelihood and magnetization). The following formulas hold.
Fix two distinct nodes u, in T. We call a node w de- scendant of u with respect to node v if the shortest path between w and v contains u. The descendant subtree at u with respect to v is the subtree Ty, rooted at u consisting of all descendants of u with respect to v. A subtree of T rooted at is descendant subtree of if is descendant subtree of u with respect to some node
ii (Gradient) For edge e = {22, (2..y. we have
à - -(0:
ZoZy
(13)
20.
1 Zz Og0
(ii) (Hessian) For edges e {x, and f {u, v} with dist(e, N as above, we have
The following notion of 'magnetization' is central to com- puting the derivatives of the log-likelihood. Roughly speak- ing, the magnetization Z,, of a node u with respect to a descendant subtree Tú, rooted at u is the 'bias' on its spin after observing all spins at the leaves of the descendant sub- tree Tu. For instance, if all spins on the leaves of Tú are +. then will be quite likely to have spin as well. The formal definition of magnetization is given below.
0²
8. (1 (1+ d 1e 2n Zyy2
N
((0:0)
II
00.00,
1=1
(1 - (0iv) Zuc,)
II 5=0
(14)
2'
1 (ws, (u5 15-) Zwn Zuy-11
(iii) (Third-order derivatives) If 0 E @o(5), then for all edges e1, E2, e3:
Definition 4.1 (Magnetization). Let Tū be descendant subtree of T rooted at a node u. Let L,, denote the set of all
leaves in Tg. For a generic parameter e [o, 1] (TT, and Lo on the leaves of Tu. define spin configuration 7 E {
03 00 00 00
4 4diam())
(0:00)
5 (2c,0)4 diam(T)-2 (15)
6

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
The expression for the Hessian in (14) above is rather com- plicated. Looking the denominators in (14), see that each of them is (at worst) ((6)), and as there are most diam(T) many a naive bound on the Hessain gives
expectation. To this end, we establish a uniform version of the well-known matrix Bernstein inequality (Thm. 1.4 in (Tropp, 2012)) for sums of self-adjoint independent random matrices. Given pre-compact parameter space θ C R", we let ||]|| == sup,, yee | - yl denote the (..am)diameter of O.
8²
{ r))
0 - (0-2dian(())
06
Lemma 4.5 (Uniform Matrix Bernstein). Fix compact parameter space @ C R.. Consider a finite sequence (Xx(f))<<k<n of self-adjoint independent random matri- ces in dimension d parameterized by 9 E O. Assume that there exists constant R 2 O such that for each 0 O,
however, we can provide a much better bound. We state this as the following lemma.
Lemma 4.3. There exists constants Cis. Čoe and d1s such that for all binary trees T and 8 I 816
S ls that almost surely
diam(T)/2+4
[[]x = and Amax Amax (Xx(()) S R
0
Či6
0(0:0)
S Sis
(16)
00.00,
Furthermore, suppose that the random matrices depend on the parameter smoothly: There exists a constant L >> 0 such that
4.2. Sketch of the Proof of Thm. 3.2
To analyze the MLE landscape in (1) we rely on knowledge of the population landscape obtained in (Clancy, Jr. et al., 2025a) which we now recall. Define H()) to be the Hessian of the oae-sample population log- likelhodd
[|x((0) (x 12 I L|0 8'1l
(20)
almost surely for all 1 5 k: S n and 0, 0' e O. Then for all 2 0, denoting の² = supace Σg E [xx
H())- = D=
[((O:o]]
= Eo- [Dee(0:0]]
(17)
IP
sup AE
Σ
Xx(O) 21
(21)
&
Bg
00.00,
e(0:0)
;e, (e.fEE(T))
(18)
s 2d 1 (1+
4nL
2 //8 0² + RI/6
exp
In (Clancy, Jr. et al., 2025a), the following population likeli- hood landscape result is shown:
Sketch proof. The statement can be deduced by using an s-net argument with the standard matrix Bernstein in- equality. Lipschitz continuity of the parameterized random matrix X-(-) is needed to do so. See Appendix B for more details.
Theorem 4.4 (Population log-likelihood landscape: strong concavity and smoothness). There exists a constant 619 E (0, 1) depending only on C3. C3, Cs, C4 such for all bi- nary frees T, 5 & 8ig and E (5) and 0² E @Q)
Now we sketch the proof of Theorem 3.2. The key is to look at the fluctuation of the empirical Hessian about its population expectation:
01
82
C19 8
<
E.
{(::0) 0)
s
for all e E E(T)
8
002
C19
C19 8
8
26 < Amin (H())) )mi)(((()) S
Amax (H(0)) S
+ +2
((0)-H(0)-- Σ m H (0) - -H(O))
(22)
(19)
=x,
where Amin (.) and ( denote the minimum and the maximum eigenvalues of a matrix. In particular, in the pop- ulation limit m - sc, the tog-likelihood function in (2) is
where H2 denotes the (random) Hessian of the kth leaf observation o()) Once we verify the hypothesis of Lemma 4.5, it implies that the random matrix the left-hand side above has a small spectral norm. By Weyl's inequality, this implies that the maximum eigenvalue of the empirical Hes- sian is concentrated around that of the expected Hessian: Uniformly over all 0 E 2))
(Sg= 26) - stroongy concave and (Gaa + smooth. In particular, the true parameter 0* is the unique maximizer of over Oo-
Now, how do we transfer this population landscape result to the empirical landscape with high probability? We essen- tially need some type of uniform concentration bound on parameterized matrix-valued random functions around its
Amax (i) Amax (H())) [i(0) H(0)]l S
with high probability (provided m is sufficiently large).
7

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
In order verify the hypothesis of the uniform matrix Bern- stein inequality (Lem. 4.5), we crucially use the determinis- tic bounds on the entries of the Hessian (in Lem. 4.3) and the third-order derivatives of the log-likeihhood (in Lem. 4.2). Namely, by Lem. 4.3, the entries in the Hessian (0) at any parameter 0 E ()()) are uniformly bounded by
fourth-order derivative of the likelihood function, which is somewhat complicated. Instead, we directly use the random empirical Hessian for the second order term and use our previous result that with high probability, the empirical Hes- sian has bounded maximum eigenvalue uniformly within a "good box' in the parameter space.
J = 5 (((diam(T)/2)) Hence the entries of the deviation matrix (0) are also uniformly bounded by J. Then by Gershgorin's 's circle theorem, it follows that
To sketch the proof of Theorem 3.3, we will write ((0) ((0; ,,....,.,, = m 11 ΣØ= f(0; xy). Then, by a first-
order Taylor expansion around l
Xx (2(0 12 S [B = |E|ō ((di-((amm))))
(23)
{ - {(00) = (V ) 0- 0*) + + 1100001110 (10-00 0 0-1²²)
uniformly over all A E Go()), as this is an upper bound of the absolute row sums.
|00 - 0
Im Im 0 0²)
m
Next, note that each entry of H2 (0) is uniformly bounded by [E]J?, so by similar argument and application of Weyl's inequality, the maximum eigenvalue of
where
m
Tm (0)
(V 100 0*1l
- - 0 0*)
E (0) = Oml| (24)
and the big-O error term depends on the empirical Hessian. This allows us to write the big-O error term above in terms of some (explicit) function of the empirical Hessian of Z()). say Am- In turn,
k=1
Lastly, for the Lipschitz continuity in (20), we may use the mean value theorem and the uniform bound on the third- order derivative in Lem. 4.2 deduce
say
0
((0) - ((0)) S
Tmm (0) + Am.l1 0 0-12.
(0) - H (0))l2
< |B| (0) (0'0')l max
(25)
If we restrict our attention to θ such that ||0 0"1l
S M E - 6'11
(26)
Rm 1/22 for some R > 0
= | diamm116 O(diam(T)) 10 O'Il
(27)
{(0) E(0)) 1|0 110-0"0 1-12
S R Tm + Am
(28)
for all 0, 0' E (o)) where M denotes the largest absolute value of the third-order derivatives of ((0; oه)) over all E @o) Since the above bound holds almost surely for all parameters in the box, it also holds for the expected Hessians, and hence for their deviations from the mean.
If we can show that there is some non non-random choice of R (depending on T and E) such that the right-hand side above is strictly negative then we can use our previous result on the concavity of (()) near 0' to conclude that the maximizer 0*| S Rm -1/2
satisfies | MMLE
4.3. Sketch of the Proof of Thm. 3.3
This final task boils down to showing that Tm concen- trates around 0 uniformly in Ô close to 0" and showing that there is some t > O such that Pe- (Am < -t) 2 1 E. We can use Berry-Esseen to accomplish the former and our previous result controlling the eigenvalues of the empirical Hessian accomplishes the latter.
The reason why we should expect to see an 0(1 (m) error term appearing in Theorem 3.3 is the central limit theorem tells us that {() should be within -1/2) of E[e(O)] as it has finite variance (Lemma 4.3). We can make this the-
quantitative and non-asymptotic with the Berry- orem. In order to turn this idea into a statement about the maximizers, we use a first-order Taylor expansion of their difference 0-
4.4. Sketch of the Proof of Thm. 3.4
In standard maximum likelihood analysis, one uses the Fisher information (expected Hessian at the true parameter) for the second-ordes term and controls the error subsumed in the third-order term. But in our context, this requires us to understand the continuity of the third-order derivative of the log-likelihood, which in turn reduces to bounding the
As already mentioned, the concavity of the empirical log- likelihood, showing that the right-hand side of (28) is strictly negative with large probability implies that the (unique) maximizer satisfies ||@ 0" || < Rm 112 One of the key steps in proving Theorem 3.4 is to show that not only in the global maximizer within Rm - 1/2 of 0" but also all the
8

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
iterates from the coordinate maximization algorithm (Alg- 1) are also within Rm-11/2 of 0- 'hhtt means we do not escape an Le neighborhood of 0" with large probability whenever we start with good initialization.
Acknowledgments
HL was partially supported by NSF grant DMS-2206296. DC and SR were partially supported by the Institute for Foundations of Data Science (IFDS) through NSF grant DMS- DMS-2023239 (TRIPODS Phase II). It is also based upon work supported by the NSF under grant DMS-1929284 while one of the authors (SR) was in residence at the Insti- tute for Computational and Experimental Research in Math- ematics (ICERM) in Providence, RI, during the Theory, Methods, and Applications of Quantitative Phylogenomics semester program. SR was also supported by NSF grant DMS-2308444 2308495, as well as a Van Vleck Research Professor Award and Vilas Distinguished Achievement Professor- ship.
The last step is to analyze the coordinate maximization algo- rithm without confinement constraints. In the optimization literature, the block coordinate minimization iterates for p- strongly convex and smooth landscapes with two blocks is known to converge linearly (Beck & Tetruashvili, 2013). Moreover, the rate of convergence depends on the parameter and the soothhssssss parameter L1, L2. We extend this to arbitrarily many blocks to deal with arbitrarily large trees.
Lemma 4.6 (Block coordinate minimization for strongly convex and smooth objectives). Fix parameter space Q := I 4; S 12P, where 1; S IR is an open convex subset with pi +pp = p ffr some b {l,...,P}, Let f S R be p-strongly convex function for some p 0. Further assume that, there exists constants LI,... IL such that f restricted on the ith block I; is Li-smooth for I,...,b.
Impact statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Consider the following cyclic block coordinate minimization algorithm: Given On-1- E S2 On = (Ongii = I,...,b,, b) be as
References
0u + arg mig f(ongI..... Onz- 0,0 Gn 1a+1. 1:6) BEL,
Arora, S., Bhaskara, A., Ge, R., and Ma. T. More algo- rithms for provable dictionary learning, arXiv preprint arXiv: /401.0579, 2014.
Assume these iterates are well-defined. Suppose f := mingen f(0)= > -00 and the minimum is attained. Then for all n 2 1,
Bai, Y., Jiang, Q.. and Sun, J. Subgradient descent learns orthogonal dictionaries. In 7th International Confer- ence on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL http::////ppeeeviewww nnt//ouummttfr id=Hk 1d=Hk1sf3Cqu F
f(O.)) - 1 (1
P min (1-min(L L Lb}
(((0))-))
Conclusion
In this work, we analyzed maximum likelihood estimation (MLE) problem with non-concave likelihood landscape. Specifically, for branch-length estimation in phylogenetics, we showed that even when the likelihood landscape may contain multiple local maxima, one can identify semi- global region where the landscape behaves well-exhibiting strong concavity and containing unique maximizer. Our analysis demonstrates that with polynomial sample com- plexity when the tree is balanced, the empirical likelihood concentrates around its population counterpart within this region.
Beale, E. M. L., Kendall, M. G., and Mann, D. W. The dis- carding of variables in multivariate analysis. Biometrika, 54:357-366, 1967. ISSN 0006-3444, 1466-344,114643510 doi: 10. 1093/biomee/543-4.33.,, URL https: /tt..oo...../oooo 10. http:///.mmett////// 3.4..3343355
Beck, A. and Tetruashvili, L. On the convergence of block coordinate descent type methods. SIAM journal on Opti- mization, 23(4):2037-2000, 2013.
Bleher, P. M., Ruiz, J., and Zagrebnov, V. A. On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Statist. Phys., 79(1-2):473 482, 1995.
Relying strong concavity of the population likelihood in a suitable neighborhood, the key steps of our approach are: proving Lipschitz continuity of the population Hessian tries and bounding the spectral norm of the per-sample em- pirical Hessian. While we focused on branch-length estima- tion, some aspects of our methodology may be relevant to a broader class of non-concave maximum likelihood problems where similar "benign" non-concavity structures exists.
Borgs, C., Chayes, J., Mossel, E.,, and Roch, S. The Kesten- Stigum reconstruction bound is tight for roughly symmet- ric binary channels. In 2006 47th Annual IEEE Sympo- sium on Foundations of Computer Science (FOCS'06) 06), pp. 518-530. IEEF, 2006.

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
Brent, R. Algorithms for minimization withoul derivatives. Courier Corporation, 2013.
Guindon, S. and Gascuel, O. A simple, fast, and accurate algorithm estimate large phylogenies by maximum likelihood. Systematic biology, 52(5):696-704, 2003.
Cavender, J. A. Taxonomy with confidence. Mathematical biosciences, 40(3-4):271-280) 1978.
Guindon, S., Dufayard, J.-F., Lefort, V., Anisimova, M., Hordijk, W., and Gascuel, O. New algorithms and meth- ods to estimate maximum maximun-lkkelioodd phylogenies: assess- ing the performance of PhyML 3.0. Systematic Biology, 59(3):307-322 321-11, 2010.
Chen, X. and Chen, Y. Inference for high-dimensional sparse econometric models. Annual Review of Economics, 11:291-317, 2019.
Chi, Y., Lu, Y. M., and Chen, Y. Nonconvex optimization meets low-rank matrix factorization: overview. Trans. Sig. Proc., 67(20):5239-9266) October 2019, ISSN 1053- 587X. doi: 10.1 10.1009/TSS22019222972222. URL https: 2937282..
Hocking, R. R. and Leslie, R. N. Selection of the best subset in regression analysis. Technometrics, 9:531-540, 1967. ISSN 0040-1700,,533--723, doi: 10.2307/1266192. URL https:ttppoccmm /
//doi org 10. 110011101000111
loffe, D. On the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys., 37(2): 137-143, 1996.
Chor, B. and Tuller, T. Finding a maximum likelihood tree is hard. Journal of the ACM (JACM), 53(5):722-744, 2006.
Jain, P., Kar, P., et al. Non-convex optimization for machine learning. Foundations and Trends@ in Machine Learning, 10(3-4):142335 2017.
Clancy, Jr., D., Lyu, H., and Roch, S. Likelihood land- scape of binary latent model on tree. 17X2v 2025a.
Karimi, H., Nutini, J., and Schmidt, M. Linear convergence of gradient and proximal proximal-gradient methods under the Dolyyk--.ojasiewiin condition. In Frasconi, P., Landwehr, N., Manco, G., and Vreeken, J. (eds.), Machine Learning and Knowledge Discovery Databases, pp. 795-811, Cham, 2016. Springer International Publishing.
Clancy, Jr., D., Lyu, H., Roch, S., and Sly, A. Likelihood- based root state reconstruction tree: Robustness to parameters. arXiv:2501.13208 2025b.
Cramér, H. Mathematical Methods of Statistics, volume 9 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1946.
Kesten, and Stigum, B. P. Additional limit theorems for indecomposable multidimensional galton-watson pro- cesses. The Annals of Mahematical Statistics, 37(6): 1463-1481, 1966.
Daskalakis, C., Mossel, E., and Roch, Evolu- tionary trees and the ising model on the bethe lat- tice: proof of steel's conjecture. Probability The- ory and Related Fields, 149:149-189 2011. ISSN
Li, B. and Babu, J. A Graduate Course on Statistical Inference. Springer Texts in Statistics. Springer, New York, 2019. ISBN 978-1 1778-1-4999-975559 -959699 978-1-4939-976 9. doi: 10. 1-177788---999999777 URL https:/ 4ot.
0178-8051. URL http: / dx doi org/10 100 1007/ s s00440-009-0246-
22.10007/0044400009--04466
Durrett, R. Probability: Theory and Examples, volume 49. Cambridge University Press, 2019.
Farris, S. probability model for inferring evolutionary trees. Systematic Biology, 22(3):20--256, 1973.
Lojasiewicz. S. A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées par- tielles, 117(87-89):2, 1963.
Felsenstein, J. Evolutionary trees from DNA sequences: maximum likelihood approach. Journal of Molecular Evolution, 17(6)336-3376 1981.
Ma, C., Wang, K., Chi, Y., and Chen, Y. Implicit regulariza- tion in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Found. Comput. Math., 20:45 632, 2020.
Fukami, K. and Tateno, Y. On the maximum likelihood method for estimating molecular trees: uniqueness of the likelihood point. Journal of Molecular Evolution, 28: 460-464, 1989.
Mossel, Combinatorial statistics and the sciences. In Proceedings of the ICM, 2022.
García Puente, L. D., Garrote-López, M., and Shehu, E.
Computing algebraic degrees of phylogenetic varieties. Algebraic Statistics, 14(2):215-231, 2024.
Murphy, K. P. Machine Learning: Probabilistic Perspec- tive. MIT Press, 2012.
10

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
Neyman, Molecular studies of evolution: source of novel statistical problems. In Statistical decision theory and related topics, pp. 1-27. Elsevier, 1971.
Warnow, T. Computational Phylogenetics: An Introduction
Designing Methods for Phylogeny Estimation. Cam- bridge University Press, 2018. ISBN 978-1-107-18471-
8. URL https: /books http:/oooooooooooaoooogoooo com/books? i id=7-k4DwAQQBAU
Nguyen, L.-T., Schmidt, H. A., von Haeseler, A., and Minh, B. Q. IQ-TREE: fast and effective stochastic algorithm for estimating maximum- -ile--iiiliood phylogenies. Molec- ular Biology and Evolution, 52(1):268--2) 274, 2015.
Zhang, Y., Qu, Q. and Wright, J. From symmetry ge- ometry: Tractable nonconvex problems. arXiv preprint arXiv:200.006553, 2020.
Polyak. B. T. Gradient methods for the minimisation of func- tionals. USSR Computational Mathematics and Mathe- matical Physics, 3(4):864- -7.88, 1963.
Roch, S. A short proof that phylogenetic tree reconstruction by maximum likelihood hard. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(1):92- 94, 2006.
Roch, S. Modern Discrete Probability: An Essential Toolkit. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024. doi: 10.1017797810099051223
Roch, and Sly, A. Phase transition in the sample com- plexity of likelihood-basse phylogeny inference. Prob- ability Theory and Related Fields, 169(1):3-62, Oct
2017. doi: 10.10077/000444000--0799444 URL https: 1000:1..000000000 //000...rr/00.110777744400000000
Stamatakis, A. RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies. Bioinfor- matics, 3009):111--131,, 2014.
Steel, M. The maximum likelihood point for a phylogenetic tree not unique. Systematic Biology, 43(4)5560-564 1994.
Steel, M. Phylogeny: Discrete and Random Processes in Evolution. CBMS-NSF Regional Conference Se- ries Applied Mathematics. Society for Industrial and Applied Mathematics, 2016. ISBN 978-1-61197-4477
8. URL https: gwogle.oooooooooooooooooooo.. com/books? 1d id=t:ddcD@AAQAAU.
Sun, J., Qu, Q. and Wright, J. A geometric analysis of phase retrieval. Found. Comput. Muth., 1135 1198, 2018. ISSN 1615-3375, 16155333,, doi: 1007 s10208-011-9965-9, URL https: /ttt:::://oo..or/1..... 1007/s10208 1117-9365-9,
Tropp, J. A. User-friendly tail bounds for sums of random
matrices. Found. Comput. Math., 12:389-434, 2012.
Wald, A. Note on the consistency the maximum likeli- hood estimate. The Annals of Mathematical Statistics, (4):595-60) 601, 1949.

---

Z, 2(0 ((0 (2,a) Zo 0 [x,b) 7b) Sample Complexity of Branch-length Estimation by Maximum Likelihood
Sample complexity of branch-length estimation by maximum likelihood Supplementary Material
A. detailed implementation of coordinate maximization algorithm (8)
Here we provide a detailed implementation of the coordinate maximization algorithm (8) for branch length estimation. A key step is to solve the critical point equation (9), for which we need to compute the first-order derivatives of the log-likelihowe function. In (Clancy, Jr. et al., 2025b), Clancy et al. obtained a simple recursive formula for the gradient of the log- log-likelihood of single sample using the magnetization Def. 4.1. In particular, they show for a single sample a that
a E(: σ) = 1 (000((0)))000000000 a0.
Zz(0:o)Z.((::0)
where e {u, u} and Z.((:: o), Zu (0; σ)) can computed recursively as follows. Consider the subtree T, of T obtained by deleting the edge and rooted at u. For the leafs a E T, define Ze = Zz (0; = On and for any other vertex æ with children a, define
(29)
where ((,,1) = stt This yields the following explicit and easily executable implementation of the coordinate maximization algorithm in (8).
14st
Algorithm Empirical likelihood maximization by cyclic coordinate maximization
1: Input: T = -V,E) (Binary phylogenetic tree);; Og (0or))EE (initial estimate); m (number of samples); iterations); >> 0 (optional step-size)
M (number of
Sample m i.i.d. spin configurations o (1) ,..... (m) on 7 under the true model Fg-
3: for h = 0,..., M do:
Set 0.+1
(0x+1;))cE + O
5: for edges e = uv E do:
6: for i = 1,..., m do:
7: Compute the magnetizations ( and ( using (()) L and 0x41
8: end for
9: Compute the empirical gradient:
a (0.) 06
= 1 Em
a rational function 0.)
146, 2i 20
10: PR+LE + zero 0
80, fn.e(0e)== = in [-1,
(b update the coordinate e of 0u-1 by coordinate maximization)
end
12:
end for
13:
output: P.
B. A uniform matrix Bernstein's inequality
Proof of Lemma 4.5. Since C RRP is compact, it can covered by a finite number of T.2-balls of any given radius >> Let Ug denote a smallest collection e-balls that cover & and let N(s) [&g]] denote the smallest number of e-balss cover O It is easy to verify (see, e.g., (Roch, 2024))
N(e) < [1 (2/e))²
(30)
Let "1.....,NNE be the centers of e-balls in Ug. Then for each θ, there exists S s N(e) such that ||e 0,1l E. Next, denote Y(x)= Ee (x( for each O, which self-adjoint. By Weyl's inequality and the hypothesis, for each Ryy O
() (Y(x)) Amax (Y < (x)) Y())lla < |1xx(<) Xa(v)lla S <nLll yll-
12

---

Sample Complexity of Braacch-ength Estimation by Maximum Likelihood Hence for each O there exists s (e) such that
Amax ( (Y()) < A (Y(0)) + (mmax(Y m (V(0)))
S Amax (Y)))) + nLe.
If follows that, by choosing E InI.
and using a union bound with (30),
IP
sup Amax (Y(()) 21
P Pmmmax ((Amax(Y(83)) 2 1/2)
AEE
j=1
4nL P
- 18
d |
1
exp
xZ Rt/6
Rt/6
Here the second inequality uses the standard matrix Bernstein inequality for self-adjoint random matrices (see, Thm. in (Tropp, 2012)), where o² is defined in the statement.
To finish, note that
A
sup max [x: S max AEO ISi
sup max XY (0)), sup max (EE 1gied
AE ISidd
Therefore, applying the argument for (0) and combining the resulting concentration bounds using union bound, we can derive (21).
C. Proof of results for statistical and computational guarantees
In this section, we prove Theorems 3.2, 3.3, and 3.4.
We now prove Theorem 3.2, which we re-state below with more explicit constants.
Theorem C.1 (Fimite-sample log-likelihood landscape: strong concavity and smoothness, Thm. 3.2). Let 5 S 619 and let A denote the Hessian of the m-sample log-likelihood function E (1). Fix e E (0, 1). Then there exists a constant Cai > such that if
m 2 (Cs1/0)
(C)dmmi)(())) (T)
log(e-1)
(31)
then for any binary tree T, and 0* E (d)))
C19
C19 27 21-E.
Pe-
27 < inf Amin (H())) S sup Amax (H(() S 0g
(32)
Proof. Recall that we denote by H() the Hessian of the population likelihood (see (17)). Let H0) = V V 7 {(0 x.)
denote the Hessian of the log-likelihood of the ith configuration x; at parameter Ô. Then H()) = m m- -> H, (0) is the
Hessian of the empirical likelihood function in (1) at Ô. Denote H()) H()) Eg- [[)]] H())) H()).
First, we will use the uniform matrix Bernstein inequality (Lemma 4.5) to deduce that the empirical Hessian uniformly concentrates its population expectation in the spectral norm. To do so, we need to verify the hypothesis of Lemma 4.5. First, by using Lemma 4.2, the entries in the Hessian (θ) at any parameter 0 E O)()) are uniformly bounded by
= C16 (Cio/6) diamm1))/+4
.y Gershgorin's 's circle theorem, follows that the eigenvalues the Hessian of H, (0) are
2 is uniformly uniformly bounded by JEJ (as this is upper bound of the row sums). Next, note that each entry of (0)²
bounded by T2 by similar argument, the maximum eigenvalue of Σ E H (0)² are uniformly bounded by ml m Lastly, for the Lipschitz continuity in (20), may use the mean value theorem to deduce
(0) H.,(')) l|2
L (0) H,(O')l mm S M 0'11
for all 0,0' ..(
13

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
where M denotes the largest absolute value of the third-order derivatives of E( o()) over all 0 E @o(0). According Lemma 4.2(ii), M Σ 4 diiam(T) (2c44))_diamna -ddiam()) Since the above bound holds almost surely for all parameters in the box, it also holds for the expected Hessians, and hence for their deviations from the mean.
Thus, by the uniform matrix Bernstein inequality (Lemmaa 4.5), we get
|6l (2VIBI(C -c))) )
(1+
16 diam (T) (ec)))4ciam(T)+ (T)
EE
m² /8 02 + Rmm/6
Pe- sup HH(2))2 < 2| (E)
exp
(33)
where == J and o² ml m J?. We will choose the sample size m that the right-hand hand side of (33) is most 8/2. For this, it is sufficient have
(2)(2 log (2V ca (6(1 16 diam (0 ( + [2 + |E|//
-m/8
I log 2/g
Rearranging, it is enough to have
diam diam(T)+ +T)+
C16
2 8 1+ 1
(34)
log((1 + |E| log 22/ -ca) (1+
(2c40) diam )) + log(2/6)
16 diam (T)
We choose C31 large enough that (Cs1/8) ( dominates the right-hand side above with the term log(2/e) disre- garded. Then we increase C31 so the right-hand side above is dominated by (C31 (C31/8)dia (8)d)am(())+ log(1/e), which is the sample complexity bound in (31).
Next, we will deduce that the extreme eigenvalues of H()) are uniformly concentrated around the extreme eigenvalues of the expected Hessian over all parameters 0 E (d) with high probability, For the maximum eigenvalue, by Weyl's inequality for self-adjoint matrices,
Amax (ii(0) Amax (B((((O)) || < [(]]l]
Thus (33) implies that Amax (π(()) s Amax (EL + for all Ô @o(6) with probability at least 1 (s/2). By applying the same argument for -()) we have that Amin (H()) Amin (E(H(O)) for all θ @o(6) with probability least 1 (s/2). Hence by union bound and Lemma 4.4, deduce the assertion (32).
Next, we prove Theorem 3.3, which re-state below with more explicit constants.
Theorem C.2 (Statistical estimation guarantee, Thm. 3.3). Assume the hypothesis of Theorem 3.2 holds. Let Egg denote the event in (32). Fix e E (0, 1) and denote = Cin 27 and Cy
16C1a
Then we have
Cis
iPo (Esa n { 1100-011 (rr/11//mlo(((111)) 2 21-3a
|
provided that m satisfies (31) and m 2 10 -"
Proof. Fix E > 0. By Theorem 3.2, Pa- (Es2) 2 - E. At present let R > 0 be some cot-to-be-determneed quantity.
We will show that the log- ligeliill function attains local maximizer within Cm 1mm-11 1/2-ball around 0":
Po- Hence by a union bound, the intersection of Esg and the event in (35) occurs (under Pø-) with probability at least
sup (
-I 1/2 ((0:a) - ((0') <0)0)>0)000) 2 - 25.
(35)
1 3c. On the event Fzz, since l strictly concave over ()))) follows that the local maximizer near 0* must be
14

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
0- the global maximizer of over (8)) This is enough deduce (7). In the remainder of this proof we will write
{ - ((0:
2;) but write E(0; r;) to refer to a single sample.
Fix 0 (o( such that | 0* some concentration inequalities:
Rm 1/2, We introduce two random variables that we will bound be small by using
Tm (0)
/m
Vol [Q)(0')] 0 0²)
|0
001
1 @ H')' 8*).
Sm (0)
sup
0- 1
2 (8)
where denotes the Hessian the m-sample log- log-likelihood function in (1). By first-order Taylor expansion,
{()) ((0") S (V))( 0 0-)
10
0 (0
0 0'
<
Tm (0) 2
0 0-1 sup Amax (H())) e
m
where the second inequality uses V Vg and that (0 - 00) both sides by ||0
0*) s Amax (H(z))100 0- Dividing
0*
2| = R2m m and rearranging.
(()) e()))
S R
Tm (0)
Rp
+
sup x
Amax (())) + +
(36)
0 1
4
=:11
where = Cia 27. We wish to show that the supremum of the left-hand side of (36) overall E O)()) with
8
1 0*1 Rm-112 1/2 is strictly negative with probability c. Indeed, by Theorem 3.2, we have
Po- (I2 S p/4) 2 2
provided the sample complexity of (31). Thus is enough show that 11 < 0 least with probability 1-5 e. Asymptotically -> oc, (0) is of order with high probability by the central limit theorem. Below give non-asymptotic argument using Berry-Esseen theorem. We will show the following inequality
Rp 4
R282 64|E|C?
3 E| 10 m
Fe.
sup @
(0) 2
S E exp
(37)
0 0 1||RR 1/2
Supposing (37) for the moment, Theorem 3.3 follows once we find (resp. m) large enough so that the first (resp. second) term on the right-hand side above are at most The first term smaller than by simply rearranging (7) with R (og The second term is clearly satisfied by the choice of m in the statement.
It remains to verify (37). To this end, write Vo((O") = Vol(O') E V ((()))
Σ U. where U, == ( E RI We write U.(k) for the 4thh coordinate of U, Then by using Cauchy-Schwar inequality and noting that 0 0- Cm 1/2 112 we get
E
0 0"
(0)
U.
U
Ui(k)
0"
is important to note that the distribution of the random variable on the last term above does not depend on Ô. Note that U, for 1,..., n are independent mean zero i.i.d. random vectors in TR. E) as we will see below, their respective coordinates
15

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
have uniformly bounded variances. Hence by union bond,
Po-
sup OE (d))
Tm (0)2 26
[
P
1 U.(k)
Σ
m
t
(38)
m
E
||0 o" ||=--1/
Let 2 1 Ei= (k).. Then by the Derry-Esseee Theorem (Thm. 3.4.17 in (Durrett, 2019)) and the hypothesis, for
ym
Z ~ N00, 1),
3E (
sup Po (0 < az) P (Z s {= zEk
where
o² = ok) Varg- (U,(k)) Bo- (O-[))
σ vm
Write Omin ming (k) and max max; (k). Combining with (38) and using triangle inequality, obtain
3
3 E
Eg
I (A))
Pa.
sup (E)
(0) 21
E
22
(39)
2/
1max
m
0
min
100 0 1|=--/1-
To simplify the last term above, note that for each edge E with corresponding coordinate & for U. Lemma 4.2 and A1 yield [U)(k:]]
2,2,
< 1/(204))
1+Z.2,01
E Eg
E
[|U((k)]]
-
(2c,8)3*
k=1
Furthermore, using
8 ((0))
8
2,2,
2,2, 1- Zu Z.Z
)²
{(0)))
-UU((k)) from Lemma 4.2(i)
092
86,
1+2. 2,
08
see that
O2
C19
C19
(²) Vare- (U)())) Eg. [U]( -og-
(())
002
To get the last inclusion above used Lemma 4.4. Going back to (39), this shows
t8
3
Po-
sup @E@n( 0 0 ||=m-1/
Tm 21
< E
2>
2
Vm 8C c3332/
1282
1
3
< exp
4 A Ci
Vm
SCB c3350/2
where used the standard Gaussian tail bound P(Z 2 x) exp(=x> /2). Setting t == Rp gives (37), desired.
In the remainder of this section, we prove Theorem 3.4.
Theorem C.3 (Statistical and computational estimation guarantee, Thm. 3.4). Suppose the hypothesis of Theorem 3.3 holds. Let (0z) denote the sequence of estimated parameters generated by the coordinate maximization algorithm (see Alg. 1) with the initial estimate Oo satisfying
||0g 00 (C19
275) 8
(40)
C19 + C19 2'
16

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
where Cio (C1 C3) A (c4 - c3) > 0. Then with probability least 1 3e, for all k: 2 O,
C1g 277
(1
Ci9o 1 27
k-1
10" 1x -
10 0011
(41)
Ci9 276
C196-1 - 27
In particular,
Cig 278
Ci96
- (k-1)/2 C196
110- 0 s CtV(Bl/m l0
110 0oll
(42)
C19 278
277
sstatistical enor
=computational error
A crucial ingredient is the following local confinement result of coordinate maximization for the maximum likelihood landscape.
Lemma C.4 (Local confinement of coordinate maximization). Suppose the hypothesis of Theorem 3.3 holds. Fix g E (0,1) and let En denote the event in (7). If (Ox)s20 is a sequence of parameters computed by the coordinate maximization algorithm (Alg. 1) with the initial estimate Og satisfying (40), then
Pa- (Ei E Int (Go(o) for all 2 07) 2 13s,
(43)
provided m 2. is large enough so that
Ct E log E
C40
C19 8. C19 + C19
(44)
vm
Proof. In this proof, we denote / = -é for the negative of the empirical log-likelihood in (1). We will crucially use the fact that coordinate minimization generates a sequence of iterates that monotonically decreases the objective f. Namely, let Ao denote the event of interest in (43). Define the following events:
A = (0 E @o(d) ((() S {((o)) C Int (0o(0))
C4n
2 E + C19 8 _
C19
A2 = 110 00' <
)
Esg the event in (32) in Theorem 3.2.
Note that both and 0 are random and so both A₁ and A2 indeed events. We claim that the following inclusions hold:
E, S E S A Eg2
S
Ao
The first inclusion is immediate by the definition of the events and the choice of sample size (44). Since Po- Po-(EE) 21 3e by Theorem 3.3, this implies that Ao occurs with probability least 3s, as desired. We first show A₁ C. Ao by induction. For the base step, note that, by A1, 0* E +0(8) and that (o(6) a closed box contained the Groô-interior of the closed box (5) (see A1). Hence,
(0 110 - 10-0-11 <Caod] C Int (6.(0)).
(45)
Since the initial estimate Oy satisfies (40), in particular it holds that ||0g - 0*|l < Canō. Hence from the above inclusion, we have 0, Int (0)( This verifies the base step.
For the induction step, suppose A n Eag holds and i...... Og E Int (oo(6)) for some k 2 0. We wish to show that 0x+1 E Int @)(()) Recall that 0x41 is obtained from 0x by updating a coordinate ox corresponding to some unique edge in T. We now use the fact that the restriction of f each coordinate is strictly convex almost surely (Fukami & Tateno, 1989). Denote this function 0g + f() by fc. Then by definition
0 = arg min fe(
0E.-1.1)
17

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
In addition, define
0k+1;e
arg min fc(
0E[1-2C46.1-244
and let 0k+1 denote the parameter obtained from 0% by replacing 0kte with 0x+1,e. By induction hypothesis, 0% Int ())()): In particular, Onze E (1 2C46, 2c46). Hence f(0++1) S s(Ox) S S f(0o). Thus, on the event A1, we deduce 0x+1 Int (0o(6)). This implies 1s+1ce is in fact in the open interval (1 - 2C46, 1 2c46).. Now since fe is strictly convex on the whole interval [-1, 1], it follows that 0x+1;e = 0k+1;e; in words, the strictly convex function Je attains its global minimizer in the whole domain [-1,1] inside the open interval (1 2C - 2c,6). This yields
0x+1 0x+1 E Int (ōu(6)) which completes the induction step. This shows the inclusion A1 n Es2 Ao-
It remains to show A2 n Esg A1 as it is obviously subset of Exg- To this effect, suppose that A2 Esg holds and choose A E @o(8) with f(0)= I f(Ou). We wish to show that A E Int (0o())) By (45), it suffices to show that 0 - 0*1 < Cnoô. Note that on the event Ag, we have that 0" is in the interior of @o())) by (45). Since 0" is the global maximizer of the empirical log- likelihood & over the box (6))), it follows that ff(0") = 0 on A2. Let μ Cie - 27 and
L : ميe + 27. On the event E22. f is u-strongly convex and L-smooth over Oo) On this event, f restricted on Oo(d) is upper and lower bounded by quadratic functions as
4 f(0 ) -リ1
0'1 f(0))
0 2
for all 0 E Oo(8).
Hence it follows that, for each 0 On(o), (()) < ((0) implies 0 0'1 s 1 0l0 011 Using the hypothesis (40), this yiclds
0 0' S |00 0'| + |00 - 0')
L - 0 - 0'11
< 1 0'
+
s L + P (10' 00 1100 001)
"
< C1o + C19
Co0 C19 276
+ 110 - 0-1)
C19 276
2 Č1 + C19
< Cang.
According to (45), this implies 0 E Int (6)(5) as desired.
We now prove Theorem 3.4, which we re-state below with a more explicit dependence on constants. In the proof, we will use a general result (Lemma 4.6) on linear convergence of coordinate minimization algorithm for minimizing strongly convex and smooth objectives with closed constraint set. For the flow of the paper, we relegated its statement and proof in Section D.
Proof of Theorem 3.4/C.3. Let Eas denote the event in (43). By Lemma C.4, Pa- (Eas) 2 2 3e. On the event Ess, the iterates (0x) (02) are confined the interior of the box constraint set @n( Since the log-likelihooe function e strictly convex in each coordinate, it follows that if we had imposed the additional open box constraint Int(@u(()) when we computed the coordinate maximization iterates in Alg. 1, the same iterates would have been generated. Thus, without loss of generality, we will assume that the iterates (0 )220 are computed via the coordinate maximization algorithm for the following constrained maximization problem:
max @cint @EIn(((.(5))
((0).
(46)
18

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
On the event E13. is p (C190-1- 27) strongly concave and L = (C19ō-1 -27)-smooth over Oo Hence apply Lemma 4.6 with = (C196-1 27) and (L E (Ei) are any uniform (over @b()) upper-bounds for corresponding diagonal entry of the empirical Hessian on E43- Clearly,
max 14 S sup
sup (w, H(0)v) S
( wE
Therefore, we may choose Lmax = L. This gives, for all h 2 O,
6110 0- -(0)) ((0)) - (1- 1) (100)) - L
k-1
-0-01
0
From this, can deduce (41) immediately. Lastly, (42) follows by combining (41) and Theorem 3.3 with triangle inequality.
D. Coordinate minimization for constrained strongly convex and smooth problems
is a classcial result optimization by Beck and Tehruashvili (Beck Tetruashvili, 2013) that alternating minimization (two-block unconstrained coordinate minimization) converges the global minimizer at linear rate min(L...zf for p-strongly convex and blockwise (L1, L2) -smooth objectives. It is straightforward to extend this result for multi-block unconstrained coordinate minimization to obtain linear convergence with rate 1 wmmti....... where f is b-block smooth with block-smoothness parameters L,...., Lg- This result is stated and proved below.
Proof of Lemma 4.6. We follow the approach of (Beck & Tetruashvili, 2013) and write
0, (0m:11 -M Onss 11-1,111 .. 1,.1 for = n + for E (0,1,,6 1}.
We will always write f = n + i/b for some n 2 and some i E {0, 1,,b - 1} in the sequel. follows from Lemma 5.1 (Beck & Tetruashvili, 2013) that
i 1 t= n + D
((O.) s(0+11/0) 2 2T.+1
(V]
whenever
Hence, whenever t = n + i/b for some i (0, 1}:
f(0.) f(0++1) 2 f(0.) - f(0++1/6) 2 2L
[f(0.))1
(47)
Since f is convex, with unique minimum 0" we can apply the Cauchy-Schward inequality to get f(0.) - f s (0.)) 0, 0*) < [ - e" for all
Moreover, since 0g is attained by repeated minimization problems f(0.) < (0,) and so where C' = =ssup[]] - 0" || f(0) s f(0n)) < co.
f(Ox) f < C(IV
Combining this with (47) we have
(
whenever = i
f(0.) f(0++)) 2
2L C
If we set On = (i) = f(Onts/b) - f then
a, 0n+1 = f(O +i/b) f(e ((0++44/00) (f(0 ((0n+i/h) ff-²
where 7 = 1 2L C
ya
2L
19

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
By Lemma 3.5 in (Beck Tetruashvili, 2013), we conclude On S 2L for all n 2 1. Next, by strong convexity, and for ( n i/b
a, ( = f(0,) f 1 (0.))
(strong convexity)
2p
Lit1
(f(O,) - f(0++1)) Li+1 (an(1) - an)1(1))
(by (47)).
Upon rearranging,
- f(0 - 8f (1 - (f(Onti/b) -r) = -011011111
P
Liti an(i)
and so, by induction.
f(O f(0n+i/b)- - x(1 P (((0))))-) (1 - (S(0o) - -
(1-Tm)
1i+11
Now just choose the index such that L = Li = min Le so that
f(0n+1) f s f(0 - 11/0) pr - 11) (J(0o) - f*).
This is simply re-indexing the desired statement.
E. Almost Sure Statements for the Hessian
In this section we prove Lemma 4.2, noting that the first two are contained in (Clancy, et al., 2025a) and so we just need to show (15) holds. Maintaining the notation from the Hessian, see that (Clancy, Jr. et al., 2025a) essentially computed
0 ,
N
N
(Otu), Zwnz²
Z
Z.
0
II
Ub
(1+ 1 m,, (vs us 1) Zw, Zyy-1)
1=1
==
provided that the edge f is contained in the subtree Ty, In particular, since each of the denominators is at least (2c,6)², we get the following claim:
Claim 1. Let T. be binary tree rooted at y and let denote the maximum distance from to a leaf in T Then
Zy 5 (2c,8)2d"
a0,
Proof of Lemma 4.2. This bound trivially holds for all e₁ 62 cz, and using Lemma 4.2(i,ii it is also easily checked (using the symmetry of mixed partial derivatives) if e, eg and eg for distinct i, since
g3
8²
ZnZy
-2
((0a))
00,
00,00 (1+ 0. k.y
00, (1 G.
-22 Z, (2 0.Z.2. Zgg
0
Zy
(1 + 0 Zz
00,
So, using Claim and the maximum distance from y to a leaf in Ty,
g3
6
((:0))
<
(2c46)4 (2cq8)2d 6(2cad) -2 2diam(T)-4
00 ,0
Therefore, we just check when e,, 62, eg are distinct. There are two cases to consider (again using symmetry of mixed partials). Say 63 {z.y). Either e E Tx and e2 Ty or both 61, E Ty-
20

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
In the of the former, see
8
0²
Zz
0 00.,
Ux + By à
((000)
Zx
4n
e0,, a0,g 80.g
00,, 00,₂
+ 0eg 7 7ty
(1 + Ozg 7e 72y)
O6.2
and, since the sum of distance from x to any leaf in T3 and the distance from y to any leaf in Ty most the diameter,
2
((:0) = (2c,0)² (2c4 d'diim((2))
,0., 00 00.s
The latter case is a bit harder. In this case we will assume that 63
v) as in Lemma 4.2. Thus {a, y) and e2 =f= ff,,=1,00
7g abe, (1+ Z, ((0:0)=
N
(1 (01 x Zw;)²)
II j=0
ad,, 00., o0..
j=1
(1 (1+
f w 1 (15:00 1) Zwz Zzy-1)
Note, can suppose that ei A {y و for any of the edges on the path from these are covered by the previous case. Therefore either e₁ {yk, w&} for some e1 Two for some k. If it is an edge e {Me, 3 then Z,, depends on de, for j k but none of the other magnetizations appearing in the right-hand side of the above equation; while if el Tan then there is the additional dependence Zwn Note that for any N 2 j >> k and e1 {yk, wx it holds that
well as also that ei & T. as
0
1 - (0 (1)) Zw,)2
0be, (1 0 (,,,, (us. 1 12
(0 (0(ssnes) Ne, 3no,) 12)
105 Zwu (1 (0 (Ouss Me, (wr )
Zu Ode,
(1 0 (u), (15,)13-1) Zuy Z )3
1 (0(s, mr0z)²
Eअ (say)
(1 (1), (15 1) Zen, -1,-1)
as well
0
1-(0 (0( Zon,)
27 (0 (0(ve.v) we Mon + 10 1 7u 1)
ade, (1 + 0 (/v. vo 10 1) Zwn y2
(1 + (on.um } (on 1) Zwn Zyy_,)"
1 (0 (1(ue.ue) }2
E2
(1+ + 0lue.ww) 110.00h-11 Lw,, 4yr-1)
0
7g Zo
-27
0
ZgZo
Zy =
Es (say).
00., (1 + 2z
(1 1. dc,
(1 2.
Here E1, E2, Es are (signed) errors satisfying
2
(2c48)
diamm)))
4
|E/
<
(2c40)2
2
1
(2c40)
diimmi))
21

---

Sample Complexity of Branch-length Estimation by Maximum Likelihood
Therefore by the product rule when e1 {yk, wk} then
(1- (0 (05. my Zee, )2)
8 0de, 00 00
0 Zabo
10:0)
II
II
eg
Obe,
(1 0. Z. 2y)
j=1
j=0
1 0 (us
n0; O (us -1 Zen, Z-,=-1)
1) II (1- (0(u), Zu,)2
Zg
II
0 (M
(diam(() max [Ei [E2) (Ea)))
(1 + Zy
j=0 [ (lus,w,) (Ms (1s Zue, 7,,
4 (diam(T)
(2cc6))ddamm())++
where the exponent in the denominator is 2 dTamm() + (2 diam(T) 1) which is the worst-case bound for each of the denominators in the Hessian and maximum bound from Ez, respectively.
The bound for whenever e E Twx is similar, except the error for the corresponding "Eg term" is the same as the bound for Eg above. We omit the details.
We finally prove Lemma 4.3.
Proof of Lemma 4.3. start with the simple observations that from (14) and the fact that Ô [0, _j and + OZzZz" z
2 that
(1 (1- (1s Zro,)²
82 00.00,
0.ZoZo
((,or)
5
II
0 Oiy
II
Toyyy 7,y)
j=1
5=0
(1, v0,) (00 185- Teon 7rys-1
N
[ 1 (1)))) Lw,} )2)
< (2c
II 1=0
1 + 6 (1))
(Msiis 1) Zwo Zyy-1)
By Proposition 6.8 in (Clancy, Jr. et al., 2025a), there is some constant C' >>> 0 (depending only the constants in A1) such that
(1 (0 Zmnz)
(1 1 (0 Zroz )2
C
I
for all j 0, 1, .N
(I 1 ( Zwo - (1 110011 ,1) Zwzat Zui
8
Note that for each we have (1 (1+0 (1ss (0s.00 Zen, Zos- 2cg8 since 0. s 2c.6 and Z, E [-1, 1] for all
follows that
22


Reviews:
[{"review_id": "3ZK0k4G6zm", "reviewer": "Reviewer_9aGs", "summary": "The paper provides analysis of optimization landscape of the MLE problem in phylogenetics under the Kesten-Stigum (KS) regime. As a corollary, they obtain quantitative results for consistency of the MLE and convergence rate for coordinate descents, which are often used in practice.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and remarks.\n\n* My biggest concern is that the related work session is not well down, with very few direct comparisons to relevant literature. Indeed I think the paper has substantial overlaps with Clancy, Ryu and Roch's preprint on \"Likelihood landscape of binary latent model on a tree\" (which the paper did cited) as both analyze the landscape of MLE and arrive at a regularity condition.\n\n\n\n**Response:**\n> We will flesh out the related works section and include a discussion on the paper of Roch and Sly you mention and what distinguishes our results from theirs. For example, they make a crucial additional assumption that the parameter lives on a lattice while we do not need that assumption. Moreover Roch and Sly show that, given sufficiently many samples, the likelihood is maximized at the true discretized parameters (including the tree parameter) with high probability, but they do not address the question of the convergence of standard optimization algorithms - the focus of our work. \n\n \n> In the paper by Clancy et al. that you mention, the authors establish eigenvalue bounds of the population Hessian in an $L^\\infty$ ball around the true parameter $\\theta^*$. We indeed use this result in our paper - this is Step 1 in our three-step program described on page 2. Our paper is a demonstration that a commonly used optimization algorithm for MLE with non-concave likelihood landscapes does work for this particular model. Moreover, the paper by Clancy et al. is not sufficient in itself to guarantee that the empirical log-likelihood is strongly concave and smooth uniformly in some region. Standard matrix concentration results applied to the empirical Hessian would only allow for high-probability statements of the empirical Hessian for a fixed $\\theta$ (or finitely many $\\theta$'s). To improve this to uniform, we need stronger matrix concentration results and (usable) a.s. bounds on the Lipschitz constant of the Hessian to obtain high-probability and uniform control over the fluctuations of the empirical Hessian about its mean (this is our Appendix E). This, combined with our uniform matrix Berstein's inequality, give us high-probability control of the empirical log-likelihood function.", "claims_and_evidence": "The paper is theoretical in nature. All claims written in theorem formats are carefully written and are correct, as far as the reviewer has investigated the proof. However, I believe that some out-of-theorem-format claims could be written a bit more carefully. \n\nFor instance, the whole paper assumes that we are working in the KS regime, which is a major assumption, since the KS regime is known to be 'easier' for phylogenetics MLE.", "methods_and_evaluation_criteria": "The suggested methods to analyze optimization landscape, starting with population Hessian bounds and translate to empirical results via a concentration inequality is well known and correct. The paper is novel in the particular optimization object that is being applied, as well as a new uniform concentration inequality, which might be of independent interest.", "theoretical_claims": "I have checked the proof strategies and I believe that they are sound. There might still be typos in the proof since I did not check the proof line by line, but the overall idea is correct.", "experimental_designs_or_analyses": "Experiments are small-scaled and mostly toyish, which is expected and appropriate for a heavily theoretical paper.", "relation_to_broader_scientific_literature": "MLE is one of the most used methods in tree inference in phylogenetics analysis due to its nice statistical guarantees (e.g. low sample complexity, statistical consistency, etc.). However, it is also NP hard to compute and practical applications of the method employs local heuristics, which lacks theoretical understandings. This paper is part of a recent effort to understand the success of descent-based heuristics used in practice.", "essential_references_not_discussed": "Roch and Sly's \"Phase transition in the sample complexity of likelihood-based phylogeny inference\" shows that the sample complexity in the KS regime can be proven to be very small (logarithmic in the number of taxa). Given that the proposed name of the paper is about 'sample complexity', a more direct comparison with Roch and Sly's paper is in order. Note that the optimization landscape results are still novel, just that the sample complexity results need more comparisons to be placed in existing literature.\n\nClancy, Ryu and Roch earlier this year also has a preprint on \"Likelihood landscape of binary latent model on a tree\", which also analyze the optimization landscape of the same problem. Given that this paper also derives their main theorems from a landscape study, I believe that a more in depth discussion of how this results differ from that of Clancy et al. paper is warranted", "other_strengths_and_weaknesses": "The paper is overall interesting and addresses a timely problem in analyzing loss landscape of optimization that seems to be well-solved by  descent-based algorithms. The theoretical analysis is sound. My biggest concern is that the related work session is not well down, with very few direct comparisons to relevant literature. Indeed I think the paper has substantial overlaps with Clancy, Ryu and Roch's preprint on \"Likelihood landscape of binary latent model on a tree\" (which the paper did cited) as both analyze the landscape of MLE and arrive at a regularity condition. The second improvement that the paper can make is to clarify very early on, and in the abstract, that the paper is assuming the KS regime, which makes MLE tree inference (which is NP hard in general) much easier in time complexity. The third improvement would be a more detailed discussion on this crucial regime (perhaps in the appendix) so that the proof intuition can be derived quicker. I am giving the paper a borderline acceptance score, simply to do substantial overlap with previous work, which can be seen as concurrent work, but would be willing to raise it higher if my concerns are addressed.", "other_comments_or_suggestions": "See strengths and weaknesses.", "questions_for_authors": "See strengths and weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "sjigoMBgCw", "reviewer": "Reviewer_TiSt", "summary": "This work concerns the maximum-likelihood estimation in a particular model for branch-length estimation relevant in phylogenetics. This work seems to provide theoretical support for the finding that a rather naive coordinate ascent algorithm works well for this problem even though the likelihood is known to be non-concave.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and for pointing out the typos. We will incorporate them in the revision.\n\n1. Given the submission to a machine-learning conference, how does this work relate to machine learning?\n\n**Response**\n> We appreciate the reviewer’s question. Maximum Likelihood Estimation (MLE) is a fundamental principle underlying many problems in machine learning. In classical statistics, the MLE landscape is often assumed to be strictly concave, ensuring robust computation and high-probability estimation of the population parameter. However, in modern machine learning applications, MLE problems are often highly non-concave, rendering conventional tools for statistical robustness and computational guarantees inapplicable.\n\n> While our work focuses on a specific MLE problem from phylogenetics, we believe our broader framework—analyzing non-concave MLE problems using the widely adopted coordinate descent algorithm—can be applied to other non-concave MLE settings in machine learning. To this end, we have formalized the following three-step approach in the Contributions section:\n\n> Step 1: Show that the population likelihood ￼ is strongly concave and smooth over some parameter space ￼ containing the true parameter ￼.\n\n> Step 2: Establish that the entries of the population Hessian vary in a Lipschitz manner with respect to the parameter.\n\n> Step 3: Demonstrate that the per-sample empirical Hessian has a uniformly bounded spectral norm almost surely.\n\n> Following this framework, researchers can establish the benign non-concavity of MLE problems. We hope our work provides a foundation for studying challenging MLE problems beyond the reach of classical methods and serves as a guideline for future research in this direction.\n\n2. How crucial is the \"warm-start\" requirement in Thm 3.4, i.e. the requirement that the optimisation is started within distance of the true parameter. Is this a concern/problem in practice?\n\n**Response**\n> The warm-start requirement may not be needed and whether or not it is needed is indeed a very interesting topic for future research; however, in general, greedy coordinate maximization should not always find the global maximizer of a non-concave objective function. Indeed, there is a classical counterexample by [[Powell, 1973](https://link.springer.com/article/10.1007/BF01584660)] on coordinate maximization failing to even converge to a stationary point of a smooth objective. The likelihood function in our setting is known to have exponentially many critical points in terms of the size of the tree, so it is highly likely that the success of coordinate maximization cannot be warranted with arbitrary initialization. Our analysis circumvents this issue by placing the initialization sufficiently inside the \"good box\" $\\hat{\\Theta}_{0}(\\delta)$ (please refer to Fig. 1 in the paper) so that, with high probability, the coordinate maximization algorithm can only experience strongly convex landscape without knowing how large it is.  \n\n3. Numerical example.\n\n**Response**\n> The population landscape paper by Clancy et al. that we cite does not contain precise control over how small the parameter $\\delta$ needs to be and so we cannot guarantee that any numerical example would relate to the results we prove; however, we will certainly try to conduct numerical experiments. If any are successful, we will include them in the updated version.", "claims_and_evidence": "This work is entirely theoretical and all the evidence consists of mathematical proofs.", "methods_and_evaluation_criteria": "This work is entirely theoretical. This is appropriate. But it would have been useful/insightful to add at least one numerical experiment. This would allow the authors to, e.g., compare empirical convergence rates with the theoretical convergence rates from Thm 3.3 and 3.4. Such an experiment could also give some insight into the \"warm-start\" requirement in Thm 3.4 (i.e., the need for starting the optimisation close to the true value).", "theoretical_claims": "I did not check the proofs in detail. But I did not spot any issue which would lead me to suspect that the analysis was not carried out with a sufficient amount of mathematical rigour.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "I am no expert in this area. But this work provides careful theoretical support for a finding (which seems to be known in the literature) that a naive coordinate ascent algorithm works well in the studied model for branch-length estimation despite the fact that  the likelihood is not concave in this problem. More generally, this work may provide a basis for establishing convergence rates for maximum-likelihood estimation in other models with irregular likelihood surfaces.", "essential_references_not_discussed": "I have nothing to add here.", "other_strengths_and_weaknesses": "I think this paper is quite well written, motivated and structured. The contributions seem original and significant enough to warrant publication.", "other_comments_or_suggestions": "- Line 69: converges -> converge\n- Page 3, 2nd column: There is some confusion/ambiguity here as to whether $\\sigma^{(j)}$ is a sample from all nodes of the tree or just the leaf nodes. That is, is $\\sigma^{(j)} = {\\sigma|}_L^{(j)}$? And if so, why is the 2nd notation needed?\n- Lines 135, 136, 249: use natbib's citet not citep\n- Line 205: maybe remind the reader of the definitions of these symbols.\n- Line 220--221: (non-)convex -> (non-)concave\n- Thm 3.4: is it clear what kind of norm is being used here?", "questions_for_authors": "1. Given the submission to a machine-learning conference, how does this work relate to machine learning?\n2. How crucial is the \"warm-start\" requirement in Thm 3.4, i.e. the requirement that the optimisation is started within $O(\\delta)$ distance of the true parameter. Is this a concern/problem in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gwK4CKOFaa", "reviewer": "Reviewer_JvJP", "summary": "This paper focuses on the branch lengths maximum likelihood estimation problem. Arises in phylogenetic inference, this problem aims at estimating the transition probability over each edge of a bifurcating tree give repeated and independent observation of leaf node states.\nThe authors prove that, with the assumption of interval-bounded transition probabilities and positive correlations of adjacent states, the empirical likelihood function is convex with high probability, with polynomial many observations.\nBased on this, the coordinate ascent algorithm proves to exponentially converges to the ground truth estimate.\nThe problem setting is very interesting and the authors give a detailed theoretical analysis, which may have a general impact on bioinformatics.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and thoughtful comments.\n\n* The equation (2) does not include a tree shape component, which may also affect the estimation. Have the author considered how to perform MLE with additional freedom on tree shapes?\n\n**Response**\n>In general, optimizing over both the edge lengths $\\mathbf{\\theta}$ and the tree $T$ is NP-hard [[Chor, Tuller, 2006](https://link.springer.com/chapter/10.1007/11415770_23)] and [[Roch, 2006](https://ieeexplore.ieee.org/document/1588849)]. Polynomial-time algorithms for finding the true tree under the CFN model with sufficient amount of data have been obtained [[Daskalais et al., 2011](https://arxiv.org/abs/math/0509575)] but involve ad hoc methods not used in practice; our work focuses on a common method to estimate the branch length parameters. Moreover, the MLE yields the correct pair ($\\theta,T$) under the same amount of data from the CFN model *provided* that $\\theta$ takes finitely many discrete values (i.e. the parameter lies on a lattice); we will include more of a discussion of this in the revised article, but see Section 2.3 in [[Roch and Sly, 2017](https://arxiv.org/abs/1508.01964)]. But there are significant roadblocks in dropping the lattice assumption in that paper (an assumption which is also made in [[Daskalais et al., 2011](https://arxiv.org/abs/math/0509575)]), and that result does not shed light on the convergence of common optimization schemes (unlike our results).\n\n* The \"ferromagnetic regime\" in line 111 assumes positive correlations of adjacency state, this is not the case for real phylogenetics problems. How does this assumption affect your conclusion?\n\n**Response**\n> The CFN model requires that the edge probability $p_e\\in [0,1/2)$ which implies that $\\theta_e = 1-2p_e \\in (0,1]$. This is because the signal/character $X$ evolves as a two-state continuous-time Markov chain with generator $\\displaystyle \\begin{bmatrix} -1&1\\\\\\\\ 1&-1\\end{bmatrix}$. In this case, it can be shown that $P(X_t = 1|X_0 = 1) = 1-\\frac{1}{2}e^{-t}$ which decreases from $1$ at $t = 0$ to $1/2$ as $t\\to\\infty$. Hence, the ferromagnetic assumption is in fact standard in this case.\n\n\n* In many real problems, the class $\\sigma_\\rho\\in \\\\{-1,1\\\\}$ seems not practical. For DNAs, this can be four types of nucleotides. Can your analysis easily transfer to such a case?\n \n **Response**\n \n >The CFN model can be used to model the nitrogenous base (purine/pyrimidine) of a nucleotide. This groups AG (purine) and CT (pyrimidine) together.\n >There appear to be significant roadblocks for handling the $4$-state (or more general $q$-state) models. For example, for the 2-state model the gradient $\\nabla \\ell(\\theta;\\sigma|_L)$ can be represented succinctly in terms of the magnetizations (equation (13) in the article). While there are formulas for the log-likelihood $\\theta_e\\mapsto \\ell(\\theta;\\sigma|_L)$ for more general models, the precise recursive formula from [[Borgs et al. 2006](https://arxiv.org/abs/math/0604366)] (or equation (29) in the article) that is used to compute the empirical gradient appears to completely breakdown. This would make understanding the population Hessian that much harder.", "claims_and_evidence": "The claims in this submission are supported by clear evidence.", "methods_and_evaluation_criteria": "Overall, I think this paper presents a sound methodology and gives a meaningful conclusion on the convergence rate of the coordinate ascent for branch length MLE. Below are two potential unsatisfactory points:\n- The equation (2) does not not include a tree shape component, which may also affect the estimation. Have the author considered how to  perform MLE with additional freedom on tree shapes?\n- The \"ferromagnetic regime\" in line 111 assumes positive correlations of adjacency state, this is not the case for real phylogenetics problems. How does this assumption affect your conclusion?", "theoretical_claims": "I do not check the correctness of the proofs.", "experimental_designs_or_analyses": "There is no experimental design in this paper. I encourage the authors to verifies their conclusion empirically, which would not demand so much time on toy examples (a tree with less than 10 leaves?).", "relation_to_broader_scientific_literature": "This problem is closely related to phylogenetics, or more generally, inference on black-box graphs with finite observations. The conclusion would be meaningful for broader audience.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "This paper has a clear presentation and is easy to follow.", "other_comments_or_suggestions": "The authors should distinguish the use of \\citet and \\citep.", "questions_for_authors": "- In many real problems, the class $\\sigma_\\rho \\in \\\\{-1,1\\\\}$ seems not practical. For DNAs, this can be four types of nucleotides. Can your analysis easily transfer to such a case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper analyzes the optimization landscape of the MLE problem for phylogenetic tree branch length estimation under the Kesten-Stigum regime; the main focus is on explaining the success of coordinate ascent methods.

The reviewers noted some weaknesses, including insufficient discussion of related work, the realism of assumptions, and the lack of numerical experiments. Additionally, the scope of the work, while technically solid, may be somewhat limited for a broad machine learning venue like ICML. However, the reviewers found the theoretical contributions to be sound and novel.

The authors are encouraged to take into account the reviewers’ suggestions; this will strengthen the manuscript.
Decision: Accept (poster)