Part of Advances in Neural Information Processing Systems 24 (NIPS 2011)
Animashree Anandkumar, Vincent Tan, Alan Willsky
We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based known as conditional mutual information test. This simple local algorithm requires only low-order statistics of the data and decides whether two nodes are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent) when the number of samples scales as n= Omega(J{min}^{-4} log p), where p is the number of nodes and J{min} is the minimum edge potential. We also prove novel non-asymptotic necessary conditions for graphical model selection.