Learning DAGs without imposing acyclicity
This addresses a computational bottleneck in structural learning for researchers in statistics and machine learning, offering an incremental improvement over classical methods.
The paper tackles the problem of learning directed acyclic graphs (DAGs) from data by proposing a method that avoids explicit acyclicity constraints, framing it as a sparse matrix factorization problem for Gaussian distributions. The result shows that an ℓ₁-penalized optimization yields good graph recovery, produces almost-DAG graphs, and is computationally efficient without combinatorial complexity issues.
We explore if it is possible to learn a directed acyclic graph (DAG) from data without imposing explicitly the acyclicity constraint. In particular, for Gaussian distributions, we frame structural learning as a sparse matrix factorization problem and we empirically show that solving an $\ell_1$-penalized optimization yields to good recovery of the true graph and, in general, to almost-DAG graphs. Moreover, this approach is computationally efficient and is not affected by the explosion of combinatorial complexity as in classical structural learning algorithms.