Research map / Learning theory and algorithms / Sample complexity

Sample Complexity of Branch-length Estimation by Maximum Likelihood

ICML 2025 · Learning theory and algorithms › Sample complexity · approach: Minimax estimation rates

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that cyclic coordinate maximization provably converges exponentially fast to the MLE for branch-length estimation on binary trees deep in the Kesten-Stigum regime, with polynomial sample complexity for balanced trees and O(1/sqrt(m)) statistical error.

Problem

Branch-length estimation by maximum likelihood on a bifurcating phylogenetic tree under a two-state symmetric Markov (CFN) model: the log-likelihood is non-concave, so convergence and statistical guarantees of optimization are unclear.

Approach

Within a universal parameter box deep in the Kesten-Stigum regime, the empirical log-likelihood is uniformly strongly concave and smooth with high probability (via a uniform matrix Bernstein inequality and Lipschitz control of the Hessian), so cyclic coordinate maximization converges exponentially fast to the MLE, which is O(1/sqrt(m))-consistent.

Key results

• Empirical log-likelihood is Theta(1/delta)-strongly concave and smooth on an L-infinity box of diameter Theta(delta) around the true parameter with probability 1-eps, given m >= (C/delta)^(diam(T)+8) log(1/eps) samples.
• The MLE is within C sqrt(|E|/m) log(|E|/eps) of the true parameter with probability at least 1-3eps, with m = Omega(|E|^2/eps).
• Cyclic coordinate maximization converges at a universal exponential rate independent of tree size, so C log(1/eps) iterations suffice for computational error eps.

Limitations

• Sample complexity grows exponentially in the tree diameter, so polynomial guarantees hold only for balanced trees.
• Convergence requires the initial estimate to be within O(delta) of the true parameter in L2 norm.
• Tree topology is assumed known; only edge lengths are optimized.

Experimental setup

Metrics: strong concavity and smoothness bounds of empirical Hessian estimation error O(sqrt(|E|/m) log(|E|/eps)) exponential convergence rate of coordinate maximization

Builds on: Clancy et al. population landscape result uniform matrix Bernstein inequality Guidon-Gascuel coordinate maximization (PHYML-style)

Closest papers by meaning

• Likelihood-free inference of phylogenetic tree posterior distributions (NeurIPS 2026 · similarity 0.86)
• Low Degree Hardness for Broadcasting on Trees (NeurIPS 2024 · similarity 0.85)
• Variational Phylogenetic Inference with Products over Bipartitions (ICML 2025 · similarity 0.85)
• Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.85)
• PhyloGFN: Phylogenetic inference with generative flow networks (ICLR 2024 · similarity 0.85)
• Deep Generative Models for Phylogenetic Inference with Complex Evolutionary Processes (NeurIPS 2026 · similarity 0.84)