Towards fast mixing MCMC methods for structure learning

Music City Center 

This talk focuses on Markov chain Monte Carlo (MCMC) methods for structure learning of high-dimensional directed acyclic graph (DAG) models, a problem known to be very challenging because of the enormous search space and the existence of Markov equivalent DAGs.  We show that it is possible to construct a random walk Metropolis-Hastings sampler on the space of equivalence classes with rapid mixing guarantee under some high-dimensional assumptions; in other words, the complexity of Bayesian learning of sparse equivalence classes grows only polynomially in n and p. We will also discuss the use of equal error variance assumption and show that, interestingly, imposing this assumption tends to facilitate the mixing of MCMC samplers and improve the posterior inference even when the model is mis-specified. 

Bayesian network

Directed acyclic graph

Markov equivalence class

Metropolis-Hastings algorithm

mixing time

order-based sampler