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

Greedy algorithms have long been a workhorse for learning graphical models,\nand more broadly for learning statistical models with sparse structure. In the\ncontext of learning directed acyclic graphs, greedy algorithms are popular\ndespite their worst-case exponential runtime. In practice, however, they are\nvery efficient. We provide new insight into this phenomenon by studying a\ngeneral greedy score-based algorithm for learning DAGs. Unlike edge-greedy\nalgorithms such as the popular GES and hill-climbing algorithms, our approach\nis vertex-greedy and requires at most a polynomial number of score evaluations.\nWe then show how recent polynomial-time algorithms for learning DAG models are\na special case of this algorithm, thereby illustrating how these order-based\nalgorithms can be rigourously interpreted as score-based algorithms. This\nobservation suggests new score functions and optimality conditions based on the\nduality between Bregman divergences and exponential families, which we explore\nin detail. Explicit sample and computational complexity bounds are derived.\nFinally, we provide extensive experiments suggesting that this algorithm indeed\noptimizes the score in a variety of settings.\n