Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

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

Research output: Contribution to journalArticlepeer-review

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 ℓ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.
Original languageAmerican English
Pages (from-to)46-73
Number of pages28
JournalINFORMS Journal on Optimization
Volume3
Issue number1
StatePublished - 1 Jan 2021

Keywords

  • structural learning
  • directed acyclic graph
  • integer programming • c
  • continuous data

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