Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

Hasan Manzour, Simge Küçükyavuz, Hao-Hsiang Wu, Ali Shojaie

    研究成果: Article同行評審


    Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a mathematical programming model that can naturally incorporate a superstructure to reduce the set of possible candidate DAGs. We use a negative log-likelihood score function with both ℓ1 and ℓ0 penalties and propose a new mixed-integer quadratic program, referred to as a layered network (LN) formulation. The LN formulation is a compact model that enjoys as tight an optimal continuous relaxation value as the stronger but larger formulations under a mild condition. Computational results indicate that the proposed formulation outperforms existing mathematical formulations and scales better than available algorithms that can solve the same problem with only ℓ1 regularization. In particular, the LN formulation clearly outperforms existing methods in terms of computational time needed to find an optimal DAG in the presence of a sparse superstructure.
    原文American English
    頁(從 - 到)46-73
    期刊INFORMS Journal on Optimization
    出版狀態Published - 1 一月 2021


    深入研究「Integer Programming for Learning Directed Acyclic Graphs from Continuous Data」主題。共同形成了獨特的指紋。