Abstract
Gaussian graphical model selection is an important paradigm with numerousapplications, including biological network modeling, financial networkmodeling, and social network analysis. Traditional approaches assume access toindependent and identically distributed (i.i.d) samples, which is oftenimpractical in real-world scenarios. In this paper, we address Gaussiangraphical model selection under observations from a more realistic dependentstochastic process known as Glauber dynamics. Glauber dynamics, also called theGibbs sampler, is a Markov chain that sequentially updates the variables of theunderlying model based on the statistics of the remaining model. Such models,aside from frequently being employed to generate samples from complexmultivariate distributions, naturally arise in various settings, such asopinion consensus in social networks and clearing/stock-price dynamics infinancial networks. In contrast to the extensive body of existing work, we present the firstalgorithm for Gaussian graphical model selection when data are sampledaccording to the Glauber dynamics. We provide theoretical guarantees on thecomputational and statistical complexity of the proposed algorithm's structurelearning performance. Additionally, we provide information-theoretic lowerbounds on the statistical complexity and show that our algorithm is nearlyminimax optimal for a broad class of problems.