DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018-03-04T00:00:00.000000Z)

TL;DR

This paper forms the structure learning problem as a purely continuous optimization problem over real matrices that avoids this combinatorial constraint entirely and achieves a novel characterization of acyclicity that is not only smooth but also exact.

Abstract

Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint. In this paper, we introduce a fundamentally different strategy: we formulate the structure learning problem as a purely continuous optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting problem can be efficiently solved by standard numerical algorithms, which also makes implementation effortless. The proposed method outperforms existing ones, without imposing any structural assumptions on the graph such as bounded treewidth or in-degree.

Authors

E. Xing

15 papers

Bryon Aragam

3 papers

Pradeep Ravikumar

5 papers

References63 items

Numerical Optimization

Practical Gauss-Newton Optimisation for Deep Learning

Bayesian Network Learning via Topological Order

A million variables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images

TL;DR

Abstract

Authors

References63 items

Numerical Optimization

Practical Gauss-Newton Optimisation for Deep Learning

Bayesian Network Learning via Topological Order

A million variables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images

Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables

Optimization Methods for Large-Scale Machine Learning

Training Neural Networks Without Gradients: A Scalable ADMM Approach

On the number of cycles in a graph

Learning Bayesian Networks with Thousands of Variables

Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression

Machine Learning of Bayesian Networks Using Constraint Programming

No penalty no tears: Least squares in high-dimensional linear models

Polyhedral aspects of score equivalence in Bayesian network structure learning

Adam: A Method for Stochastic Optimization

Proximal Quasi-Newton for Computationally Intensive L1-regularized M-estimators

Penalized estimation of directed acyclic graphs from discrete data

Addendum on the scoring of Gaussian directed acyclic graphical models

Concave penalized estimation of sparse Gaussian Bayesian networks

A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables

High-dimensional learning of linear causal networks via inverse covariance estimation

Integrated Systems Approach Identifies Genetic Nodes and Networks in Late-Onset Alzheimer’s Disease

Learning Sparse Causal Gaussian Networks With Experimental Intervention: Regularization and Coordinate Descent

Inferring large graphs using $$\ell _1$$ℓ1-penalized likelihood

Bayesian network learning with cutting planes

Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation

A New Scaling and Squaring Algorithm for the Matrix Exponential

Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm

Learning Causal Bayesian Network Structures From Experimental Data

The Tradeoffs of Large Scale Learning

Sparse inverse covariance estimation with the lasso

Learning Graphical Model Structure Using L1-Regularization Paths

Model selection and estimation in the Gaussian graphical model

A Linear Non-Gaussian Acyclic Model for Causal Discovery

The max-min hill-climbing Bayesian network structure learning algorithm

A Simple Approach for Finding the Globally Optimal Bayesian Network Structure

Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks

Smooth minimization of non-smooth functions

Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data

Large-Sample Learning of Bayesian Networks is NP-Hard

Emergence of scaling in random networks

Collective dynamics of ‘small-world’ networks

Efficient Approximations for the Marginal Likelihood of Bayesian Networks with Hidden Variables

A Limited Memory Algorithm for Bound Constrained Optimization

Learning Bayesian networks: The combination of knowledge and statistical data

Probalistic Network Construction Using the Minimum Description Length Principle

An Algorithm for Fast Recovery of Sparse Causal Graphs

Structure Discovery in Bayesian Networks by Sampling Partial Orders

Learning Bayesian networks with ancestral constraints

QUIC: quadratic approximation for sparse inverse covariance estimation

CVX: Matlab software for disciplined convex programming, version 2.1

MAXIMUM LIKELIHOOD FOR SPARSE DIRECTED ACYCLIC GRAPHS

Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood

Finding optimal Bayesian networks by dynamic programming

Finding optimal gene networks using biological constraints.

Optimal Structure Identification With Greedy Search

Optimization II: Standard Numerical Methods for Nonlinear Continuous Optimization

Emergence of Scaling in Random Networks

Symbolic and Quantitative Approaches to Reasoning and Uncertainty

Learning Bayesian Networks is

Causation, prediction, and search

Counting unlabeled acyclic digraphs

Model Selection Through Sparse Max Likelihood Estimation Model Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data

Field of Study

Venue Information

Name

Type

URL

Alternate Names