A Caltech Library Service

High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion

Anandkumar, Animashree and Tan, Vincent Y. F. and Huang, Furong and Willsky, Alan S. (2012) High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion. Journal of Machine Learning Research, 13 . pp. 2293-2337. ISSN 1533-7928.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n=Ω(J_(min)^(-2) log p), where p is the number of variables and J_(min) is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2012 Animashree Anandkumar, Vincent Tan, Furong Huang and Alan Willsky. Submitted 7/11; Revised 4/12; Published 8/12. An abridged version of this paper appeared in the Proceedings of NIPS 2011. The first author is supported in part by the setup funds at UCI and the AFOSR Award FA9550-10-1-0310, the second author is supported by A*STAR, Singapore and the third author is supported in part by AFOSR under Grant FA9550-08-1-1080. The authors thank Venkat Chandrasekaran (UC Berkeley) for discussions on walk-summable models, Elchanan Mossel (UC Berkeley) for discussions on the necessary conditions for model selection and Divyanshu Vats (U. Minn.) for extensive comments. The authors thank the Associate Editor Martin Wainwright (Berkeley) and the anonymous reviewers for comments which significantly improved this manuscript.
Funding AgencyGrant Number
University of California, IrvineUNSPECIFIED
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
Record Number:CaltechAUTHORS:20170927-091743601
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81870
Deposited By: Tony Diaz
Deposited On:27 Sep 2017 16:25
Last Modified:03 Oct 2019 18:48

Repository Staff Only: item control page