Computation of maximum likelihood estimates in cyclic structural\n equation models

Mathias Drton, Chris Fox, Y. Samuel Wang

TL;DR

This paper introduces a robust Block-Coordinate Descent (BCD) algorithm for calculating Maximum Likelihood Estimates (MLEs) in linear Structural Equation Models (SEMs) that contain feedback loops (cycles). Unlike standard non-linear optimizers that often struggle with convergence in cyclic models, this approach provides closed-form solutions for each update step and offers a polynomial-time graphical criterion to ensure the algorithm is well-defined.

What Problem Does This Paper Address?

Structural Equation Models (SEMs) are the workhorse of causal modeling, representing how variables influence one another through systems of linear equations. While estimation is straightforward for acyclic models (where the "cause-effect" flow has no loops), things get messy when feedback cycles are involved—for example, when variable A influences B, and B simultaneously influences A.

Standard software packages typically use general-purpose non-linear optimization (like quasi-Newton methods) to find the MLE. These methods are notoriously finicky: they require "goldilocks" starting values to avoid diverging or getting stuck, and they often fail entirely on poorly fitting models. The presence of cycles makes the likelihood function much more complex, as the determinant of the model's transformation matrix is no longer a simple constant.

Methods

The authors propose a Block-Coordinate Descent (BCD) method. Instead of optimizing all parameters at once, the algorithm cycles through each variable $i$ in the system. In each "block" step, it updates only the parameters related to that specific variable (its incoming edges and its error variance/covariances) while holding everything else fixed.

Key Innovations: * Closed-Form Updates: The authors prove that even in the presence of feedback cycles, the sub-problem of updating a single variable's parameters can be reduced to minimizing a ratio of two quadratic functions. They provide an exact, numerically stable formula to solve this, avoiding the need for internal iterative optimization. * Graphical Characterization: They use mixed graphs (containing both directed edges for causation and bi-directed edges for latent correlation) to determine when the algorithm is "well-defined." * Polynomial-Time Check: They show that checking if a model is suitable for this BCD approach is equivalent to a network flow problem, which can be solved in $O(|V|^5)$ time, where $V$ is the number of variables.

Datasets

The paper evaluates the algorithm using two primary sources:

  1. Protein-Signaling Network: A real-world dataset from Sachs et al. (2005) containing abundance measurements of 11 signaling molecules in 853 human immune system cells. The authors use this to compare a cyclic model against an acyclic sub-model.
  2. Simulated Data: The authors generated 24 different configurations of random mixed graphs (varying the number of nodes, sample sizes, and cycle lengths) to benchmark their algorithm against the standard R package sem.

Key Insights and Ideas

  • Surprising Simplicity: It is mathematically elegant that the complex, high-degree algebraic problem of cyclic MLE can be broken down into a series of simple quadratic ratios.
  • Robustness over Precision: BCD methods are generally more stable than second-order methods like quasi-Newton. While they might take more iterations to reach extreme precision, they are far less likely to "blow up" or fail to converge from a random starting point.
  • Identifiability Link: The authors demonstrate a deep connection between the algorithm's "well-definedness" and the statistical identifiability of the model. If the graphical conditions for the BCD update fail, the model parameters are likely not uniquely identifiable from the data anyway.

Key Results

  • Superior Convergence: In simulations, the BCD algorithm achieved nearly 100% convergence across almost all scenarios. In contrast, the standard sem package failed frequently, especially with small sample sizes or complex cycles (in one case, sem only converged 47.9% of the time).
  • Speedup: For sparse graphs, the BCD algorithm was up to 6 times faster than the quasi-Newton approach.
  • Practical Utility: On the protein dataset, the BCD algorithm allowed for a stable Likelihood Ratio Test between cyclic and acyclic models, providing a p-value (0.78) that suggested the simpler acyclic model was sufficient.

Limitations and Future Work

  • Local Maxima: Like all descent-based methods, BCD is guaranteed to find a stationary point (a local maximum or saddle point), but not necessarily the global maximum of the likelihood function. The authors suggest running the algorithm from multiple starting points to mitigate this.
  • Hybrid Potential: The authors acknowledge that while BCD is robust, it can be slow to converge in the final stages compared to second-order methods. They suggest a hybrid approach—using BCD to get close to the solution and then switching to a quasi-Newton method for final "polishing"—as a promising direction for future software implementation.

Summary updated

Abstract

Software for computation of maximum likelihood estimates in linear structural\nequation models typically employs general techniques from non-linear\noptimization, such as quasi-Newton methods. In practice, careful tuning of\ninitial values is often required to avoid convergence issues. As an alternative\napproach, we propose a block-coordinate descent method that cycles through the\nconsidered variables, updating only the parameters related to a given variable\nin each step. We show that the resulting block update problems can be solved in\nclosed form even when the structural equation model comprises feedback cycles.\nFurthermore, we give a characterization of the models for which the\nblock-coordinate descent algorithm is well-defined, meaning that for generic\ndata and starting values all block optimization problems admit a unique\nsolution. For the characterization, we represent each model by its mixed graph\n(also known as path diagram), which leads to criteria that can be checked in\ntime that is polynomial in the number of considered variables.\n
BibTeX
@article{drton2019computation,
  author = {Mathias Drton and Chris Fox and Y. Samuel Wang},
  title = {{Computation of maximum likelihood estimates in cyclic structural\textbackslash\{\}n equation models}},
  journal = {The Annals of Statistics},
  year = {2019},
  doi = {10.1214/17-aos1602},
}
Figure