Sample Complexity of Branch-length Estimation by Maximum Likelihood

Thank you for the review and thoughtful comments.

• 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?

Response

In general, optimizing over both the edge lengths $\mathbf{\theta}$ and the tree $T$ is NP-hard [Chor, Tuller, 2006] and [Roch, 2006]. Polynomial-time algorithms for finding the true tree under the CFN model with sufficient amount of data have been obtained [Daskalais et al., 2011] 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]. But there are significant roadblocks in dropping the lattice assumption in that paper (an assumption which is also made in [Daskalais et al., 2011]), and that result does not shed light on the convergence of common optimization schemes (unlike our results).

• 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?

Response

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.

• 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?

Response

The CFN model can be used to model the nitrogenous base (purine/pyrimidine) of a nucleotide. This groups AG (purine) and CT (pyrimidine) together. 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] (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.

Thank you for your comments and for pointing out the typos. We will incorporate them in the revision.

1. Given the submission to a machine-learning conference, how does this work relate to machine learning?

Response

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.

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:

Step 1: Show that the population likelihood  is strongly concave and smooth over some parameter space  containing the true parameter .

Step 2: Establish that the entries of the population Hessian vary in a Lipschitz manner with respect to the parameter.

Step 3: Demonstrate that the per-sample empirical Hessian has a uniformly bounded spectral norm almost surely.

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.

2. 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?

Response

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] 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.

3. Numerical example.

Response

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.

Thank you for your thoughtful comments and remarks.

• 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.

Response:

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.

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.