EM's Convergence in Gaussian Latent Tree Models

Yuval Dagan, Constantinos Daskalakis, Anthimos Vardis Kandiros

Abstract

We investigate the optimization landscape of the log-likelihood function and the convergence properties of the Expectation-Maximization (EM) algorithm in latent Gaussian tree models (LGTMs). These models feature tree-structured Gaussian graphical representations where leaf nodes are observable and internal nodes remain unobservable. Our analysis demonstrates that the unique non-trivial stationary point of the population log-likelihood is its global maximum. Furthermore, we establish that the EM algorithm is guaranteed to converge to this global maximum in the single latent variable case. By characterizing the fixed points of the EM update as solutions to a system of polynomial equations and identifying trivial fixed points as higher-order saddle points, we provide a theoretical foundation for the widespread practical success of maximum likelihood methods in this domain.

Introduction

Latent variable models are fundamental to modern statistics, providing a framework to model hidden factors that influence observable data. However, estimating these models is notoriously difficult. While fully observable exponential family models benefit from concave log-likelihoods, the process of "marginalizing out" latent variables typically destroys this property. The resulting optimization landscape is often characterized by a "bumpy" surface filled with local maxima and saddle points, where standard algorithms like Expectation-Maximization (EM) can easily become trapped.

Gaussian Latent Tree Models (LGTMs) are a specific, widely used class of these models. In an LGTM, variables are organized in a tree structure; internal nodes are hidden, while leaf nodes are observable. These models are critical in fields ranging from phylogenetics to network tomography. Despite their utility, theoretical guarantees for the global convergence of EM in these settings have remained elusive—until now.

The Optimization Landscape of LGTMs

The core contribution of this research is the discovery that the population log-likelihood landscape for LGTMs is remarkably "clean." In the limit of infinite data (the population limit), the authors prove that there are no spurious non-trivial stationary points.

This means that if an optimization algorithm finds a point where the gradient is zero—and that point does not represent a trivial case where correlations are 0 or 1—it has found the global maximum. This result suggests that for LGTMs, the non-convexity introduced by latent variables does not create the treacherous local optima typically feared in latent variable estimation.

Methodology: Polynomial Systems and Saddle Points

To reach these conclusions, the study employs a sophisticated mathematical framework centered on the population EM algorithm. The analysis follows several key stages:

  1. Polynomial Characterization: The authors show that the fixed points of the EM update rule correspond to solutions of a system of degree-2 polynomial equations.
  2. Uniqueness via the Jacobian Conjecture: By applying a special case of the Jacobian Conjecture, the researchers establish the uniqueness of the stationary point within the interior of the parameter space for any latent Gaussian tree.
  3. Boundary Analysis: A significant hurdle in EM analysis is the presence of "trivial" fixed points (e.g., where correlations are zero). Through higher-order Taylor expansions, the authors prove these points are actually higher-order saddle points. These points act as "repellers," pushing the EM algorithm toward the true interior solution rather than trapping it.
  4. Structural Reduction: For complex topologies, a novel reduction technique simplifies the algebraic equations of a large tree into a system equivalent to the single-latent-variable case, allowing the uniqueness results to generalize across tree structures.

Key Results and Complexity

The research provides both qualitative insights and quantitative bounds for the single-latent-node case (one hidden node with $n$ leaves):

  • Global Convergence: EM is guaranteed to converge to the true parameters from any initialization in the interior of the parameter space.
  • Sample Complexity: The study establishes that $O(poly(n)/\epsilon^2)$ samples are sufficient to estimate the true parameters within an accuracy of $\epsilon$.
  • Iteration Complexity: The algorithm achieves this accuracy in $O(poly(n) \log(1/\epsilon))$ iterations, demonstrating efficient convergence.

Discussion and Limitations

While this work represents a major step forward, it introduces specific constraints that invite future research. The proofs currently operate under the ferromagnetic assumption, where all correlations between variables are assumed to be positive. While this is common in biological and physical modeling, extending the theory to anti-ferromagnetic models (negative correlations) is a logical next step.

Furthermore, while the "no spurious peaks" result holds for general trees, the explicit global convergence proof for the EM algorithm itself is currently localized to the single-latent-node case. Extending this convergence guarantee to arbitrary tree topologies remains an open challenge in the field. Finally, while the landscape results are robust in the population limit, the dynamics of finite-sample behavior in complex trees offer a rich area for further investigation.

Summary updated

Abstract

We study the optimization landscape of the log-likelihood function and the convergence of the Expectation-Maximization (EM) algorithm in latent Gaussian tree models, i.e. tree-structured Gaussian graphical models whose leaf nodes are observable and non-leaf nodes are unobservable. We show that the unique non-trivial stationary point of the population log-likelihood is its global maximum, and establish that the expectation-maximization algorithm is guaranteed to converge to it in the single latent variable case. Our results for the landscape of the log-likelihood function in general latent tree models provide support for the extensive practical use of maximum likelihood based-methods in this setting. Our results for the EM algorithm extend an emerging line of work on obtaining global convergence guarantees for this celebrated algorithm. We show our results for the non-trivial stationary points of the log-likelihood by arguing that a certain system of polynomial equations obtained from the EM updates has a unique non-trivial solution. The global convergence of the EM algorithm follows by arguing that all trivial fixed points are higher-order saddle points.
BibTeX
@inproceedings{dagan2022em,
  author = {Yuval Dagan and Constantinos Daskalakis and Anthimos Vardis Kandiros},
  title = {{EM's Convergence in Gaussian Latent Tree Models}},
  booktitle = {Conference on Learning Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=rko0_LtgOV},
}
Figure