High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods

Christopher Johnson, Ali Jalali, Pradeep Ravikumar
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:574-582, 2012.

Abstract

In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two novel greedy approaches to solving this problem. The first estimates the non-zero covariates of the overall inverse covariance matrix using a series of global forward and backward greedy steps. The second estimates the neighborhood of each node in the graph separately, again using greedy forward and backward steps, and combines the intermediate neighborhoods to form an overall estimate. The principal contribution of this paper is a rigorous analysis of the sparsistency, or consistency in recovering the sparsity pattern of the inverse covariance matrix. Surprisingly, we show that both the local and global greedy methods learn the full structure of the model with high probability given just O(d log(p)) samples, which is a significant improvement over state of the art L1-regularized Gaussian MLE (Graphical Lasso) that requires O(d^2 log(p)) samples. Moreover, the restricted eigenvalue and smoothness conditions imposed by our greedy methods are much weaker than the strong irrepresentable conditions required by the L1-regularization based methods. We corroborate our results with extensive simulations and examples, comparing our local and global greedy methods to the L1-regularized Gaussian MLE as well as the nodewise L1-regularized linear regression (Neighborhood Lasso).

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-johnson12, title = {High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods}, author = {Johnson, Christopher and Jalali, Ali and Ravikumar, Pradeep}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {574--582}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/johnson12/johnson12.pdf}, url = {https://proceedings.mlr.press/v22/johnson12.html}, abstract = {In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two novel greedy approaches to solving this problem. The first estimates the non-zero covariates of the overall inverse covariance matrix using a series of global forward and backward greedy steps. The second estimates the neighborhood of each node in the graph separately, again using greedy forward and backward steps, and combines the intermediate neighborhoods to form an overall estimate. The principal contribution of this paper is a rigorous analysis of the sparsistency, or consistency in recovering the sparsity pattern of the inverse covariance matrix. Surprisingly, we show that both the local and global greedy methods learn the full structure of the model with high probability given just O(d log(p)) samples, which is a significant improvement over state of the art L1-regularized Gaussian MLE (Graphical Lasso) that requires O(d^2 log(p)) samples. Moreover, the restricted eigenvalue and smoothness conditions imposed by our greedy methods are much weaker than the strong irrepresentable conditions required by the L1-regularization based methods. We corroborate our results with extensive simulations and examples, comparing our local and global greedy methods to the L1-regularized Gaussian MLE as well as the nodewise L1-regularized linear regression (Neighborhood Lasso).} }
Endnote
%0 Conference Paper %T High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods %A Christopher Johnson %A Ali Jalali %A Pradeep Ravikumar %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-johnson12 %I PMLR %P 574--582 %U https://proceedings.mlr.press/v22/johnson12.html %V 22 %X In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two novel greedy approaches to solving this problem. The first estimates the non-zero covariates of the overall inverse covariance matrix using a series of global forward and backward greedy steps. The second estimates the neighborhood of each node in the graph separately, again using greedy forward and backward steps, and combines the intermediate neighborhoods to form an overall estimate. The principal contribution of this paper is a rigorous analysis of the sparsistency, or consistency in recovering the sparsity pattern of the inverse covariance matrix. Surprisingly, we show that both the local and global greedy methods learn the full structure of the model with high probability given just O(d log(p)) samples, which is a significant improvement over state of the art L1-regularized Gaussian MLE (Graphical Lasso) that requires O(d^2 log(p)) samples. Moreover, the restricted eigenvalue and smoothness conditions imposed by our greedy methods are much weaker than the strong irrepresentable conditions required by the L1-regularization based methods. We corroborate our results with extensive simulations and examples, comparing our local and global greedy methods to the L1-regularized Gaussian MLE as well as the nodewise L1-regularized linear regression (Neighborhood Lasso).
RIS
TY - CPAPER TI - High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods AU - Christopher Johnson AU - Ali Jalali AU - Pradeep Ravikumar BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-johnson12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 574 EP - 582 L1 - http://proceedings.mlr.press/v22/johnson12/johnson12.pdf UR - https://proceedings.mlr.press/v22/johnson12.html AB - In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two novel greedy approaches to solving this problem. The first estimates the non-zero covariates of the overall inverse covariance matrix using a series of global forward and backward greedy steps. The second estimates the neighborhood of each node in the graph separately, again using greedy forward and backward steps, and combines the intermediate neighborhoods to form an overall estimate. The principal contribution of this paper is a rigorous analysis of the sparsistency, or consistency in recovering the sparsity pattern of the inverse covariance matrix. Surprisingly, we show that both the local and global greedy methods learn the full structure of the model with high probability given just O(d log(p)) samples, which is a significant improvement over state of the art L1-regularized Gaussian MLE (Graphical Lasso) that requires O(d^2 log(p)) samples. Moreover, the restricted eigenvalue and smoothness conditions imposed by our greedy methods are much weaker than the strong irrepresentable conditions required by the L1-regularization based methods. We corroborate our results with extensive simulations and examples, comparing our local and global greedy methods to the L1-regularized Gaussian MLE as well as the nodewise L1-regularized linear regression (Neighborhood Lasso). ER -
APA
Johnson, C., Jalali, A. & Ravikumar, P.. (2012). High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:574-582 Available from https://proceedings.mlr.press/v22/johnson12.html.

Related Material