jmlr jmlr2011 jmlr2011-39 jmlr2011-39-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Shuheng Zhou, Philipp Rütimann, Min Xu, Peter Bühlmann
Abstract: Undirected graphs are often used to describe high dimensional distributions. Under sparsity conditions, the graph can be estimated using ℓ1 -penalization methods. We propose and study the following method. We combine a multiple regression approach with ideas of thresholding and refitting: first we infer a sparse undirected graphical model structure via thresholding of each among many ℓ1 -norm penalized regression functions; we then estimate the covariance matrix and its inverse using the maximum likelihood estimator. We show that under suitable conditions, this approach yields consistent estimation in terms of graphical structure and fast convergence rates with respect to the operator and Frobenius norm for the covariance matrix and its inverse. We also derive an explicit bound for the Kullback Leibler divergence. Keywords: graphical model selection, covariance estimation, Lasso, nodewise regression, thresholding c 2011 Shuheng Zhou, Philipp R¨ timann, Min Xu and Peter B¨ hlmann. u u ¨ ¨ Z HOU , R UTIMANN , X U AND B UHLMANN
O. Banerjee, L. El Ghaoui, and A. d’Aspremont. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research, 9:485–516, 2008. P. Bickel and E. Levina. Some theory for Fisher’s linear discriminant function, ”naive Bayes”, and some alternatives when there are many morevariables than observations. Bernoulli, 10:989–1010, 2004. P. Bickel and E. Levina. Regulatized estimation of large covariance matrices. The Annals of Statistics, 36:199–227, 2008. P. Bickel, Y. Ritov, and A. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. The Annals of Statistics, 37:1705–1732, 2009. P. B¨ hlmann and L. Meier. Discussion: One-step sparse estimates in nonconcave penalized likeliu hood models. The Annals of Statistics, 36:1534–1541, 2008. T. Cai, W. Liu, and X. Luo. A constrained ℓ1 minimization approach to sparse precision matrix estimation. Journal of the American Statistical Association, 106:594–607, 2011. E. Cand` s and T. Tao. The Dantzig selector: statistical estimation when p is much larger than n. e Annals of Statistics, 35(6):2313–2351, 2007. S. Chaudhuri, M. Drton, and T. Richardson. Biometrika, 94:1–18, 2007. Estimation of a covariance matrix with zeros. 3023 ¨ ¨ Z HOU , R UTIMANN , X U AND B UHLMANN A. d’Aspremont, O. Banerjee, and L. El Ghaoui. First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and Applications, 30:56–66, 2008. J. Fan, Y. Feng, and Y. Wu. Network exploration via the adaptive lasso and scad penalties. The Annals of Applied Statistics, 3:521–541, 2009. J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical Lasso. Biostatistics, 9:432–441, 2007. J. Friedman, T. Hastie, and R. Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software, 33, 2010. R. Furrer and T. Bengtsson. Estimation of high-dimensional prior and posterior covariance matrices in Kalman filter variants. Journal of Multivariate Analysis, 98:227–255, 2007. J. Huang, N. Liu, M. Pourahmad, and L. Liu. Covariance matrix selection and estimation via penalised normal likelihood. Biometrika, 93:85–98, 2006. J. Huang, S. Ma, and C. Zhang. Adaptive Lasso for sparse highdimensional regression. Statistica Sinica, 18:1603–1618, 2008. I. Johnstone. Chi-square oracle inequalities. In State of the Art in Probability and Statistics, Festchrift for Willem R. van Zwet, M. de Gunst and C. Klaassen and A. van der Waart editors, IMS Lecture Notes - Monographs, 36:399–418, 2001. C. Lam and J. Fan. Sparsistency and rates of convergence in large covariance matrices estimation. The Annals of Statistics, 37:4254–4278, 2009. E. Levina, A. Rothman, and J. Zhu. Sparse estimation of large covariance matrices via a nested Lasso penalty. The Annals of Applied Statistics, 2:245–263, 2008. N. Meinshausen. Relaxed Lasso. Computational Statistics and Data Analysis, 52:374–393, 2007. N. Meinshausen. A note on the Lasso for gaussian graphical model selection. Statistics and Probability Letters, 78:880–884, 2008. N. Meinshausen and P. B¨ hlmann. High dimensional graphs and variable selection with the Lasso. u The Annals of Statistics, 34:1436–1462, 2006. N. Meinshausen and B. Yu. Lasso-type recovery of sparse representations for high-dimensional data. Annals of Statistics, 37(1):246–270, 2009. J. Peng, P. Wang, N. Zhou, and J. Zhu. Partial correlation estimation by joint sparse regression models. Journal of the American Statistical Association, 104:735–746, 2009. P. Ravikumar, M. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation by minimizing ℓ1 -penalized log-determinant divergence. Electronic Journal of Statistics, 4:935–980, 2011. 3024 H IGH - DIMENSIONAL C OVARIANCE E STIMATION A. Rothman, P. Bickel, E. Levina, and J. Zhu. Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2:494–515, 2008. M. Rudelson and S. Zhou. Reconstruction from anisotropic random measurements, 2011. University of Michigan, Department of Statistics, Technical Report 522. Available at arXiv:1106.1151v1. P. R¨ timann and P. B¨ hlmann. High dimensional sparse covariance estimation via directed acyclic u u graphs. Electronic Journal of Statistics, 3:1133–1160, 2009. C. Uhler. Geometry of maximum likelihood estimation in gaussian graphical models. Available at arXiv:1012.2643v1, 2011. S. van de Geer, P. B¨ hlmann, and S. Zhou. The adaptive and the thresholded Lasso for potentially u misspecified models (and a lower bound for the lasso). Electronic Journal of Statistics, 5:688– 749, 2011. N. Verzelen. Adaptive estimation of covariance matrices via cholesky decomposition. Electronic Journal of Statistics, 4:1113–1150, 2010. M. West, C. Blanchette, H. Dressman, E. Huang, S. Ishida, R. Spang, H. Zuzan, J.A. Olson Jr., J.R. Marks, and J.R. Nevins. Predicting the clinical status of human breast cancer by using gene expression profiles. PNAS, 98:11462–11467, 2001. A. Wille, P. Zimmermann, E. Vranova, A. F¨ rholz, O. Laule, S. Bleuler, L. Hennig, A. Prelic, P. von u Rohr, L. Thiele, E. Zitzler, W. Gruissem, and P. B¨ hlmann. Sparse graphical Gaussian modeling u of the isoprenoid gene network in arabidopsis thaliana. Genome Biology, 5:R92, 2004. W. Wu and M. Pourahmadi. Nonparametric estimation of large covariance matrices of longitudinal data. Biometrika, 90:831–844, 2003. M. Yuan. High dimensional inverse covariance matrix estimation via linear programming. Journal of Machine Learning Research, 11:2261–2286, 2010. M. Yuan and Y. Lin. Model selection and estimation in the gaussian graphical model. Biometrika, 94:19–35, 2007. P. Zhao and B. Yu. On model selection consistency of Lasso. Journal of Machine Learning Research, 7:2541–2563, 2006. S. Zhou. Thresholding procedures for high dimensional variable selection and statistical estimation. In Advances in Neural Information Processing Systems 22. MIT Press, 2009. S. Zhou. Thresholded Lasso for high dimensional variable selection and statistical estimation. University of Michigan, Department of Statistics Technical Report 511. Available at arXiv:1002.1583v2, 2010a. 3025 ¨ ¨ Z HOU , R UTIMANN , X U AND B UHLMANN S. Zhou. Restricted eigenvalue conditions on subgaussian random matrices, 2010b. Manuscript, earlier version available at arXiv:0904.4723v2. S. Zhou, J. Lafferty, and L. Wasserman. Time varying undirected graphs. In Proceedings of the 21st Annual Conference on Computational Learning Theory (COLT’08), July 2008. S. Zhou, S. van de Geer, and P. B¨ hlmann. Adaptive Lasso for high dimensional regression and u gaussian graphical modeling, 2009. Available at arXiv:0903.2515. H. Zou. The adaptive Lasso and its oracle properties. Journal of the American Statistical Association, 101:1418–1429, 2006. H. Zou and R. Li. One-step sparse estimates in nonconcave penalized likelihood models. The Annals of Statistics, 36:1509–1533, 2008. 3026