A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs

2020/11/05 by Manon Romain, Romain, Manon, Alexandre d’Aspremont +1
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2011.02764

openalex publication_date 2020/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• Causal Discovery Toolbox: Uncover causal relationships in Python
• A Graph Autoencoder Approach to Causal Structure Learning
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs

Related

• Masked Gradient-Based Causal Structure Learning
• Causal Structural Learning from Time Series: A Convex Optimization Approach
• A Graph Autoencoder Approach to Causal Structure Learning
• Non-negative Weighted DAG Structure Learning
• Learning DAGs without imposing acyclicity