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. https://resolver.caltech.edu/CaltechAUTHORS:20170927-101515951
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
See Usage Policy. 358kB |
|
PDF
- Submitted Version
See Usage Policy. 476kB |
|
PDF
- Supplemental Material
See Usage Policy. 320kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170927-101515951
Abstract
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: |
| |||||||||
| 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. | |||||||||
| Funders: |
| |||||||||
| 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: | https://resolver.caltech.edu/CaltechAUTHORS:20170927-101515951 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 81876 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 27 Sep 2017 17:29 | |||||||||
| Last Modified: | 03 Oct 2019 18:48 |
Repository Staff Only: item control page
