A Caltech Library Service

High-dimensional structure estimation in Ising models: Local separation criterion

Anandkumar, Animashree and Tan, Vincent Y. F. and Huang, Furong and Willsky, Alan S. (2012) High-dimensional structure estimation in Ising models: Local separation criterion. Annals of Statistics, 40 (3). pp. 1346-1375. ISSN 0090-5364.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.

[img] PDF - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


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 introduce a novel criterion for tractable graph families, where this method is efficient, based on the presence of sparse local separators between node pairs in the underlying graph. For such graphs, the proposed algorithm has a sample complexity of n=Ω(J^(−2)_(min)log p), where p is the number of variables, and J_(min) is the minimum (absolute) edge potential in the model. We also establish nonasymptotic necessary and sufficient conditions for structure estimation.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2012 Institute of Mathematical Statistics. Supported by the setup funds at UCI and the AFOSR Award FA9550-10-1-0310. Supported in part by A*STAR, Singapore. Supported in part by AFOSR under Grant FA9550-08-1-1080. The authors thank Sujay Sanghavi (U.T. Austin), Elchanan Mossel (UC Berkeley), Martin Wainwright (UC Berkeley), Sebastien Roch (UCLA), Rui Wu (UIUC) and Divyanshu Vats (U. Minn.) for extensive comments, and Béla Bollobás (Cambridge) for discussions on random graphs. The authors thank the anonymous reviewers and the co-editor Peter Bühlmann (ETH) for valuable comments that significantly improved this manuscript.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-10-1-0310
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-1080
Subject Keywords:Ising models, graphical model selection, local-separation property
Issue or Number:3
Classification Code:MSC2010 subject classifications: Primary 62H12; secondary 05C80
Record Number:CaltechAUTHORS:20170927-101515951
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81876
Deposited By: Tony Diaz
Deposited On:27 Sep 2017 17:29
Last Modified:03 Oct 2019 18:48

Repository Staff Only: item control page