On the Convergence of Continuous Constrained Optimization for Structure Learning

Abstract

Recently, structure learning of directed acyclic graphs (DAGs) has been formulated as a continuous optimization problem by leveraging an algebraic characterization of acyclicity. The constrained problem is solved using the augmented Lagrangian method (ALM) which is often preferred to the quadratic penalty method (QPM) by virtue of its standard convergence result that does not require the penalty coefficient to go to infinity, hence avoiding ill-conditioning. However, the convergence properties of these methods for structure learning, including whether they are guaranteed to return a DAG solution, remain unclear, which might limit their practical applications. In this work, we examine the convergence of ALM and QPM for structure learning in the linear, nonlinear, and confounded cases. We show that the standard convergence result of ALM does not hold in these settings, and demonstrate empirically that its behavior is akin to that of the QPM which is prone to ill-conditioning. We further establish the convergence guarantee of QPM to a DAG solution, under mild conditions. Lastly, we connect our theoretical results with existing approaches to help resolve the convergence issue, and verify our findings in light of an empirical comparison of them.

AISTATS 2022. A preliminary version of this paper was presented at the NeurIPS 2020 Workshop on Causal Discovery and Causality-Inspired Machine Learning. The code is available at https://github.com/ignavierng/notears-convergence

References in corpus (12)

• Bayesian network learning with cutting planes
• DAG-GNN: DAG Structure Learning with Graph Neural Networks
• A Graph Autoencoder Approach to Causal Structure Learning
• Learning Neural Causal Models from Unknown Interventions
• DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks
• Differentiable Causal Discovery Under Unmeasured Confounding
• Differentiable Causal Discovery from Interventional Data
• Causal Discovery from Incomplete Data: A Deep Learning Approach
• Graphical Normalizing Flows
• Causal Adversarial Network for Learning Conditional and Interventional Distributions
• Causal Discovery with Multi-Domain LiNGAM for Latent Factors
• Structure Mapping for Transferability of Causal Models

Cited by in corpus (2)

• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• Towards Federated Bayesian Network Structure Learning with Continuous Optimization