Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes

Abstract

Structure learning via MCMC sampling is known to be very challenging because of the enormous search space and the existence of Markov equivalent DAGs. Theoretical results on the mixing behavior are lacking. In this work, we prove the rapid mixing of a random walk Metropolis-Hastings algorithm, which reveals that the complexity of Bayesian learning of sparse equivalence classes grows only polynomially in $n$ and $p$, under some high-dimensional assumptions. A series of high-dimensional consistency results is obtained, including the strong selection consistency of an empirical Bayes model for structure learning. Our proof is based on two new results. First, we derive a general mixing time bound on finite state spaces, which can be applied to local MCMC schemes for other model selection problems. Second, we construct high-probability search paths on the space of equivalence classes with node degree constraints by proving a combinatorial property of DAG comparisons. Simulation studies on the proposed MCMC sampler are conducted to illustrate the main theoretical findings.

arXiv commentonly minor changes

References in corpus (13)

• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• A Transformational Characterization of Equivalent Bayesian Network Structures
• Bayesian variable selection with shrinking and diffusing priors
• Identifiability of Gaussian structural equation models with equal error variances
• Geometry of the faithfulness assumption in causal inference
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions
• Consistency of objective Bayes factors as the model dimension grows
• Global identifiability of linear structural equation models
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs
• Tight inequalities among set hitting times in Markov chains
• Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models

Cited by in corpus (1)

• Dimension-free Mixing for High-dimensional Bayesian Variable Selection