DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks

Understand

This paper re-examines a continuous optimization framework dubbed NOTEARS for learning Bayesian networks.

• We first generalize existing algebraic characterizations of acyclicity to a class of matrix polynomials.
• Next, focusing on a one-parameter-per-edge setting, it is shown that the Karush-Kuhn-Tucker (KKT) optimality conditions for the NOTEARS formulation cannot be satisfied except in a trivial case, which explains a behavior of the associated algorithm.
• We then derive the KKT conditions for an equivalent reformulation, show that they are indeed necessary, and relate them to explicit constraints that certain edges be absent from the graph.