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

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 scorebased 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 rigorously 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. Historically, the use of the basic forward-backward greedy scheme for learning directed acyclic graphical (DAG) models predates some of this work, dating back to the classical greedy equivalence search [GES, 13] algorithm. Since its introduction, GES has become a gold-standard for learning DAGs, and is known to be asymptotically consistent under certain assumptions such as faithfulness and score consistency [13, 34] . Both of these assumptions are known to hold for certain parametric families [21], however, extending GES to distribution-free settings has proven difficult. Furthermore, 35th Conference on Neural Information Processing Systems (NeurIPS 2021).