DAGs with NO TEARS: Continuous Optimization for Structure Learning

Pradeep Ravikumar
Carnegie Mellon University

Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian
networks) is a challenging problem since the search space of DAGs is combinatorial
and scales superexponentially with the number of nodes. Existing approaches
rely on various local heuristics for enforcing the acyclicity constraint. We introduce
a fundamentally different strategy: we formulate the structure learning problem
as a purely continuous optimization problem over real matrices that avoids this
combinatorial constraint entirely. This is achieved by a novel characterization of
acyclicity that is not only smooth but also exact. The resulting
problem can be efficiently solved by standard numerical algorithms, which also
makes implementation effortless. The proposed method outperforms existing
ones, without imposing any structural assumptions on the graph such as bounded
tree-width or in-degree.

Presentation (PDF File)

Back to Workshop III: Geometry of Big Data