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.

only minor changes

References in corpus (6)

• A Transformational Characterization of Equivalent Bayesian Network Structures
• Bayesian variable selection with shrinking and diffusing priors
• Geometry of the faithfulness assumption in causal inference
• 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

Cited by in corpus (1)

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