COMPLEXITY ANALYSIS OF BAYESIAN LEARNING OF HIGH-DIMENSIONAL DAG MODELS AND THEIR EQUIVALENCE CLASSES

• 成果类型: Article
• 署名作者: Zhou, Quan; Chang, Hyunwoong
• 署名单位: Texas A&M University System; Texas A&M University College Station
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2280
• 发表日期: 2023
• 页码: 1058-1085
• 关键词: directed acyclic graphs; variable selection; NETWORK STRUCTURES; Consistency; CONVERGENCE; priors; rates; mcmc

摘要

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.