Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

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

Research output: Contribution to journalArticle

Abstract

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 [Formula: see text] and [Formula: see text] 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 [Formula: see text] 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.
Original languageEnglish (US)
Pages (from-to)46-73
Number of pages28
JournalINFORMS Journal on Optimization
Volume3
Issue number1
DOIs
StatePublished - Jan 2021

Fingerprint

Dive into the research topics of 'Integer Programming for Learning Directed Acyclic Graphs from Continuous Data'. Together they form a unique fingerprint.

Cite this