High-Dimensional Structure Estimation in Ising Models: Tractable Graph Families

We consider the problem of high-dimensional Ising (graphical) model selection. We propose a simple algorithm for structure estimation based on the thresholding of the empirical conditional variation distances. We intro-duce a novel criterion for tractable graph families, where this method is ef-ficient, based on the presence of sparse local separators between node pairs in the underlying graph. For such graphs, the proposed algorithm has a sam-ple complexity of n = (J−2min logp), where p is the number of variables, and Jmin is the minimum (absolute) edge potential in the model. We also establish nonasymptotic necessary and sufficient conditions for structure estimation. 1. Introduction. Th