Convergence of Feedback Arc Set-Based Heuristics for Linear Structural Equation Models
Journal article, Peer reviewed
Published version
View/ Open
Date
2022Metadata
Show full item recordCollections
- Department of Informatics [992]
- Registrations from Cristin [10851]
Original version
Proceedings of Machine Learning Research (PMLR). 2022, 186, 157-168.Abstract
Score-based structure learning in Bayesian networks, where local structures in the graph are given a score and one seeks to recover a high-scoring DAG from data, is an NP-hard problem. While the general learning problem is combinatorial, the more restricted framework of linear structural equation models (SEMs) enables learning Bayesian networks using continuous optimization methods. Large scale structure learning has become an important problem in linear SEMs and many approximate methods have been developed to address it. Among them, feedback arc set-based methods learn the DAG by alternating between unconstrained gradient descent-based step to optimize an objective function and solving a maximum acyclic subgraph problem to enforce acyclicity. In the present work, we build upon previous contributions on such heuristics by first establishing mathematical convergence analysis, previously lacking; second, we show empirically how one can significantly speed-up convergence in practice using simple warmstarting strategies.