A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs

Abstract

We develop a Bregman proximal gradient method for structure learning on linear structural causal models. While the problem is non-convex, has high curvature and is in fact NP-hard, Bregman gradient methods allow us to neutralize at least part of the impact of curvature by measuring smoothness against a highly nonlinear kernel. This allows the method to make longer steps and significantly improves convergence. Each iteration requires solving a Bregman proximal step which is convex and efficiently solvable for our particular choice of kernel. We test our method on various synthetic and real data sets.

References in corpus (12)

• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• CAM: Causal additive models, high-dimensional order search and penalized regression
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Geometry of the faithfulness assumption in causal inference
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• High-dimensional learning of linear causal networks via inverse covariance estimation
• DeepPINK: reproducible feature selection in deep neural networks
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• A Graph Autoencoder Approach to Causal Structure Learning
• Causal Discovery Toolbox: Uncover causal relationships in Python
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression