# Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families

arXiv: https://arxiv.org/abs/2110.04719 · HTML: https://mlsanity.com/paper/2110.04719/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 61 references that are in the map.
- First posted on arXiv 10 Oct 2021.

## Builds on (most cited first, 19 of 19)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions](https://mlsanity.com/paper/1301.6697/) (2013)
- [A polynomial-time algorithm for learning nonparametric causal graphs](https://mlsanity.com/paper/2006.11970/) (2020)
- [Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity](https://mlsanity.com/paper/1703.01196/) (2017)
- [Optimal structure and parameter learning of Ising models](https://mlsanity.com/paper/1612.05024/) (2016)
- [Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)](https://mlsanity.com/paper/1704.08783/) (2017)
- [Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression](https://mlsanity.com/paper/1511.08963/) (2015)
- [Forward - Backward Greedy Algorithms for Atomic Norm Regularization](https://mlsanity.com/paper/1404.5692/) (2014)
- [Maximum Likelihood Bounded Tree-Width Markov Networks](https://mlsanity.com/paper/1301.2311/) (2013)
- [Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint](https://mlsanity.com/paper/1401.0086/) (2013)

## Built on by (most cited first, 11 of 11)

- [Learning Linear Causal Representations from Interventions under General Nonlinear Mixing](https://mlsanity.com/paper/2306.02235/) (2023)
- [On the Origins of Linear Representations in Large Language Models](https://mlsanity.com/paper/2403.03867/) (2024)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Learning Interpretable Concepts: Unifying Causal Representation Learning and Foundation Models](https://mlsanity.com/paper/2402.09236/) (2024)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Effective Causal Discovery under Identifiable Heteroscedastic Noise Model](https://mlsanity.com/paper/2312.12844/) (2023)
- [An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysis](https://mlsanity.com/paper/2311.18048/) (2023)
- [Heteroscedastic Causal Structure Learning](https://mlsanity.com/paper/2307.07973/) (2023)
- [Distributionally Robust Skeleton Learning of Discrete Bayesian Networks](https://mlsanity.com/paper/2311.06117/) (2023)
- [On the Identifiability of Mixed Ordinal and Exponential Family Causal DAGs under Linear Parametric Models](https://mlsanity.com/paper/2609.17942/) (2026)
- [Learning Non-Gaussian SEMs with Conditional Risk, and Why the Direction of Recursion Matters](https://mlsanity.com/paper/2610.14246/) (2026)

## Abstract (arXiv)

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.