Elementary Estimators for Graphical Models | Center for Big Data Analytics

Abstract: We propose a class of closed-form estimators for sparsity-structured graphical models, expressed as exponential family distributions, under high-dimensional settings. Our approach builds on observing the precise manner in which the classical graphical model MLE “breaks down” under high-dimensional settings. Our estimator uses a carefully constructed, well-defined and closed-form backward map, and then performs thresholding operations to ensure the desired sparsity structure. We provide a rigorous statistical analysis that shows that surprisingly our simple class of estimators recovers the same asymptotic convergence rates as those of the $ell_1$-regularized MLEs that are much more difficult to compute. We corroborate this statistical performance, as well as significant computational advantages via simulations of both discrete and Gaussian graphical models.

Download: pdf

Citation

Elementary Estimators for Graphical Models (pdf, software)
E. Yang, A. Lozano, P. Ravikumar.
In Neural Information Processing Systems (NIPS), December 2014.

Bibtex:
@inproceedings{yang2014elementary, author = "Eunho Yang AND Aurelie Lozano AND Pradeep Ravikumar", title = "Elementary Estimators for Graphical Models", booktitle = "Neural Information Processing Systems (NIPS)", year = "2014", month = "dec", abstract = "We propose a class of closed-form estimators for sparsity-structured graphical models, expressed as exponential family distributions, under high-dimensional settings. Our approach builds on observing the precise manner in which the classical graphical model MLE “breaks down{'}{'} under high-dimensional settings. Our estimator uses a carefully constructed, well-defined and closed-form backward map, and then performs thresholding operations to ensure the desired sparsity structure. We provide a rigorous statistical analysis that shows that surprisingly our simple class of estimators recovers the same asymptotic convergence rates as those of the $ell_1$-regularized MLEs that are much more difficult to compute. We corroborate this statistical performance, as well as significant computational advantages via simulations of both discrete and Gaussian graphical models." }