Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
arXiv:2110.04719
Abstract
Greedy algorithms have long been a workhorse for learning graphical models, and more broadly for learning statistical models with sparse structure. In the context of learning directed acyclic graphs, greedy algorithms are popular despite their worst-case exponential runtime. In practice, however, they are very efficient. We provide new insight into this phenomenon by studying a general greedy score-based algorithm for learning DAGs. Unlike edge-greedy algorithms such as the popular GES and hill-climbing algorithms, our approach is vertex-greedy and requires at most a polynomial number of score evaluations. We then show how recent polynomial-time algorithms for learning DAG models are a special case of this algorithm, thereby illustrating how these order-based algorithms can be rigourously interpreted as score-based algorithms. This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families, which we explore in detail. Explicit sample and computational complexity bounds are derived. Finally, we provide extensive experiments suggesting that this algorithm indeed optimizes the score in a variety of settings.
arXiv commentAccepted to NeurIPS 2021; 27 pages, 9 figures
References in corpus (16)
- A simple approach for finding the globally optimal Bayesian network structure
- CAM: Causal additive models, high-dimensional order search and penalized regression
- Identifiability of Gaussian structural equation models with equal error variances
- DAGs with NO TEARS: Continuous Optimization for Structure Learning
- Bayesian network learning with cutting planes
- -penalized maximum likelihood for sparse directed acyclic graphs
- Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions
- High-dimensional learning of linear causal networks via inverse covariance estimation
- Forward - Backward Greedy Algorithms for Atomic Norm Regularization
- On Causal Discovery with Equal Variance Assumption
- Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
- Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint
- High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods
- Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
- Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity
- Identifiability of Generalized Hypergeometric Distribution (GHD) Directed Acyclic Graphical Models