Computation of maximum likelihood estimates in cyclic structural equation models

Mathias Drton, Christopher Fox, Y. Samuel Wang

TL;DR

This paper introduces a novel block-coordinate descent (BCD) algorithm for efficiently computing maximum likelihood estimates (MLEs) in structural equation models (SEMs) that include feedback cycles. This new method overcomes convergence issues common in existing approaches and provides a closed-form solution for parameter updates, even in complex cyclic models.

What Problem Does This Paper Address?

Estimating parameters in structural equation models (SEMs) using maximum likelihood estimation (MLE) is a fundamental task in statistical modeling, widely used across various scientific disciplines. However, when SEMs contain feedback loops (cyclic dependencies), the computation of MLEs becomes notoriously difficult. Standard optimization techniques, like quasi-Newton methods, often struggle with convergence and require careful initialization of parameters. This can be particularly problematic in model selection scenarios where many models need to be evaluated. The paper aims to provide a more robust and efficient method for computing MLEs in these challenging cyclic SEMs.

Methods

The core contribution is a block-coordinate descent (BCD) algorithm. Instead of optimizing all parameters simultaneously, the BCD approach iteratively updates parameters related to one variable (or a block of variables) at a time, while holding others fixed. A key innovation is that for each variable's update, the problem can be solved in closed form, even when the model has feedback cycles. This is achieved by leveraging properties of the determinant of the (I-B) matrix and carefully decomposing the log-likelihood function. The paper also provides a theoretical characterization of when these block updates are guaranteed to be unique and feasible, using the concept of mixed graphs (path diagrams) and identifying specific graphical structures (half-collider paths) that ensure well-definedness.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation studies.

Key Insights and Ideas

  • Closed-form updates for cyclic models: The most significant insight is that even with feedback loops, the optimization problem for each block update can be solved analytically. This is a major improvement over general-purpose non-linear optimizers that often require iterative approximations and can get stuck.
  • Graphical characterization of well-definedness: The paper establishes a direct link between the structure of the SEM (represented by a mixed graph) and the well-definedness of the BCD algorithm. Specifically, the presence of certain "half-collider paths" in the graph guarantees that the algorithm's updates are unique and feasible.
  • Overcoming convergence issues: The BCD approach, by breaking down the complex optimization into simpler, sequential steps, is shown to be more robust to convergence problems compared to standard methods.
  • Efficiency: The closed-form updates and the structured approach of BCD lead to computational efficiency, especially for sparse graphs.

Key Results

  • A novel block-coordinate descent algorithm is proposed for computing MLEs in cyclic SEMs.
  • The algorithm provides closed-form solutions for parameter updates in each block, even in the presence of feedback cycles.
  • A combinatorial characterization is derived for mixed graphs that ensure the BCD algorithm is generically well-defined (unique and feasible updates). This characterization involves identifying specific "half-collider path" structures.
  • Simulation studies demonstrate that the BCD algorithm is competitive in terms of computation time with existing methods (like the 'sem' R package) and alleviates convergence problems. In some cases, BCD is up to 6 times faster.

Limitations and Future Work

  • Global Maximum Guarantee: Like most iterative optimization procedures, the BCD algorithm does not guarantee finding the global maximum of the likelihood function, as the likelihood can be multimodal. The authors suggest running the algorithm from multiple initial values.
  • Identifiability: While the paper characterizes when the BCD algorithm is well-defined, it notes that non-identifiable models can lead to non-unique solutions for block updates.
  • Future Work: The authors suggest that hybrid methods combining BCD with quasi-Newton steps might further improve convergence speed in certain cases. They also highlight the importance of the graphical conditions for well-definedness, which were not previously known for cyclic models.

Summary updated

Abstract

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