×

Alternating direction methods for latent variable Gaussian graphical model selection. (English) Zbl 1418.62234

Summary: V. Chandrasekaran et al. [Ann. Stat. 40, No. 4, 1935–1967 (2012; Zbl 1257.62061)] proposed a convex optimization problem for graphical model selection in the presence of unobserved variables. This convex optimization problem aims to estimate an inverse covariance matrix that can be decomposed into a sparse matrix minus a low-rank matrix from sample data. Solving this convex optimization problem is very challenging, especially for large problems. In this letter, we propose two alternating direction methods for solving this problem. The first method is to apply the classic alternating direction method of multipliers to solve the problem as a consensus problem. The second method is a proximal gradient-based alternating-direction method of multipliers. Our methods take advantage of the special structure of the problem and thus can solve large problems very efficiently. A global convergence result is established for the proposed methods. Numerical results on both synthetic data and gene expression data show that our methods usually solve problems with 1 million variables in 1 to 2 minutes and are usually 5 to 35 times faster than a state-of-the-art Newton-CG proximal point algorithm.

MSC:

62H12 Estimation in multivariate analysis
90C25 Convex programming
05C90 Applications of graph theory
62F12 Asymptotic properties of parametric estimators
62P10 Applications of statistics to biology and medical sciences; meta analysis
92D20 Protein sequences, DNA sequences

Citations:

Zbl 1257.62061

Software:

RecPF; MIM; glasso
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmed, A., & Xing, E. P. (2009). Recovering time-varying networks of dependencies in social and biological studies. Proceedings of the National Academy of Sciences, 106(29), 11878-11883. ,
[2] Banerjee, O., El Ghaoui, L., & d’Aspremont, A. (2008). Model selection through sparse maximum likelihood estimation for multivariate gaussian or binary data. Journal of Machine Learning Research, 9, 485-516. , · Zbl 1225.68149
[3] Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 1-122. , · Zbl 1229.90122
[4] Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge: Cambridge University Press. , · Zbl 1058.90049
[5] Cai, T., Liu, W., & Luo, X. (2011). A constrained ##img## minimization approach to sparse precision matrix estimation. Journal of the American Statistical Association, 106(494), 594-607. , · Zbl 1232.62087
[6] Candès, E. J., & Tao, T. (2007). The Dantzig selector: Statistical estimation when p is much larger than n. Annals of Statistics, 35(6), 2313-2351. , · Zbl 1139.62019
[7] Chandrasekaran, V., Parrilo, P., & Willsky, A. (2012). Latent variable graphical model selection via convex optimization. Annals of Statistics, 40(4), 1935-1967. , · Zbl 1257.62061
[8] Chen, G., & Teboulle, M. (1994). A proximal-based decomposition method for convex minimization problems. Mathematical Programming, 64, 81-101. , · Zbl 0823.90097
[9] Combettes, P. L., & Pesquet, J. C. (2007). A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE Journal of Selected Topics in Signal Processing, 1(4), 564-574. ,
[10] Combettes, P. L., & Wajs, V. R. (2005). Signal recovery by proximal forward-backward splitting. SIAM Journal on Multiscale Modeling and Simulation, 4(4), 1168-1200. , · Zbl 1179.94031
[11] D’Aspremont, A., Banerjee, O., & El Ghaoui, L. (2008). First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and Its Applications, 30(1), 56-66. , · Zbl 1156.90423
[12] Deng, W., & Yin, W. (2012). On the global and linear convergence of the generalized alternating direction method of multipliers (Tech. Rep.). Houston, TX: Rice University CAAM. · Zbl 1379.65036
[13] Dobra, A., Eicher, T. S., & Lenkoski, A. (2009). Modeling uncertainty in macroeconomic growth determinants using gaussian graphical models. Statistical Methodology, 7, 292-306. ,
[14] Douglas, J., & Rachford, H. H. (1956). On the numerical solution of the heat conduction problem in 2 and 3 space variables. Transactions of the American Mathematical Society, 82, 421-439. , · Zbl 0070.35401
[15] Duchi, J., Gould, S., & Koller, D. (2008). Projected subgradient methods for learning sparse gaussian. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence. N.p.: AUAI Press.
[16] Eckstein, J. (1989). Splitting methods for monotone operators with applications to parallel optimization. Unpublished doctoral dissertation, MIT.
[17] Eckstein, J. (1994). Some saddle-function splitting methods for convex programming. Optimization Methods and Software, 4(1), 75-83. ,
[18] Eckstein, J., & Bertsekas, D. P. (1992). On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55, 293-318. , · Zbl 0765.90073
[19] Edwards, D. (2000). Introduction to graphical modelling. New York: Springer-Verlag. , · Zbl 0952.62003
[20] Fazel, M., Pong, T., Sun, D., & Tseng, P. (2012). Hankel matrix rank minimization with applications to system identification and realization. Preprint. · Zbl 1302.90127
[21] Friedman, J., Hastie, T., & Tibshirani, R. (2008). Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3), 432-441. , · Zbl 1143.62076
[22] Friedman, N. (2004). Inferring cellular networks using probabilistic graphical models. Science, 303(5659), 799-805. ,
[23] Gabay, D. (1983). Applications of the method of multipliers to variational inequalities. In M. Fortin & R. Glowinski (Eds.), Augmented Lagrangian methods: Applications to the solution of boundary value problems.Amsterdam: North-Holland. , · Zbl 0561.90029
[24] Glowinski, R., & Le Tallec, P. (1989). Augmented Lagrangian and operator-splitting methods in nonlinear mechanics. Philadelphia: SIAM. , · Zbl 0698.73001
[25] Goldfarb, D., & Ma, S. (2012). Fast multiple splitting algorithms for convex optimization. SIAM Journal on Optimization, 22(2), 533-556. , · Zbl 1254.65075
[26] Goldfarb, D., Ma, S., & Scheinberg, K. (in press). Fast alternating linearization methods for minimizing the sum of two convex functions. Mathematical Programming. · Zbl 1280.65051
[27] Goldstein, T., & Osher, S. (2009). The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci., 2, 323-343. , · Zbl 1177.65088
[28] He, B. S., Liao, L. Z., Han, D., & Yang, H. (2002). A new inexact alternating direction method for monotone variational inequalities. Math. Program., 92, 103-118. , · Zbl 1009.90108
[29] Hong, M., & Luo, Z. (2012). On the linear convergence of the alternating direction method of multipliers. Preprint.
[30] Hughes, T. R., Marton, M. J., Jones, A. R., Roberts, C. J., Stoughton, R., Armour, C. D., (2000). Functional discovery via a compendium of expression profiles. Cell, 102(1), 109-126. ,
[31] Kolar, M., Song, L., Ahmed, A., & Xing, E. P. (2010). Estimating time-varying networks. Annals of Applied Statistics, 4(1), 94-123. , · Zbl 1189.62142
[32] Lauritzen, S. L. (1996). Graphical models. New York: Oxford University Press. · Zbl 0907.62001
[33] Li, L., & Toh, K. C. (2010). An inexact interior point method for L_1-regularized sparse covariance selection. Mathematical Programming Computation, 2, 291-315. , · Zbl 1208.90131
[34] Lions, P. L., & Mercier, B. (1979). Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16, 964-979. , · Zbl 0426.65050
[35] Liu, H., Han, F., Yuan, M., Lafferty, J., & Wasserman, L. (2012). High dimensional semiparametric Gaussian copula graphical models. Annals of Statistics, 40, 2293-2326. , · Zbl 1297.62073
[36] Lu, Z. (2009). Smooth optimization approach for sparse covariance selection. SIAM J. Optim., 19(4), 1807-1827. , · Zbl 1179.90257
[37] Ma, S. (2011). Alternating direction method of multipliers for sparse principal component analysis. Preprint.
[38] Ma, S. (2012). Alternating proximal gradient method for convex minimization. Preprint. · Zbl 1371.65056
[39] Malick, J., Povh, J., Rendl, F., & Wiegele, A. (2009). Regularization methods for semidefinite programming. SIAM Journal on Optimization, 20, 336-356. , · Zbl 1187.90219
[40] Meinshausen, N., & Bühlmann, P. (2006). High-dimensional graphs and variable selection with the lasso. Annals of Statistics, 34(3), 1436-1462. , · Zbl 1113.62082
[41] Natsoulis, G., Ghaoui, L. E., Lanckriet, G., Tolley, A., Leroy, F., Dunlea, S., (2005). Classification of a large microarray data set: Algorithm comparison and analysis of drug signatures. Genome Research, 15, 724-736. ,
[42] Parikh, N., & Boyd, S. (2011). Block splitting for large-scale distributed learning. Presented at the Neural Information Workshop on Big Learning.
[43] Peaceman, D. H., & Rachford, H. H. (1955). The numerical solution of parabolic elliptic differential equations. SIAM Journal on Applied Mathematics, 3, 28-41. , · Zbl 0067.35801
[44] Peng, J., Wang, P., Zhou, N., & Zhu, J. (2009). Partial correlation estimation by joint sparse regression models. Journal of the American Statistical Association, 104(486), 735-746. , · Zbl 1388.62046
[45] Qin, Z., Goldfarb, D., & Ma, S. (2011). An alternating direction method for total variation denoising. Preprint. · Zbl 1326.94024
[46] Ravikumar, P., Wainwright, M. J., Raskutti, G., & Yu, B. (2008). High-dimensional covariance estimation by minimizing ##img##-penalized log-determinant divergence. In D. Köller, D. Schuurmans, Y. Bengio, & L. Bottou (Eds.), Advances in neural information processing systems, 21. Cambridge, MA: MIT Press. · Zbl 1274.62190
[47] Rothman, A. J., Bickel, P. J., Levina, E., & Zhu, J. (2008). Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2, 494-515. , · Zbl 1320.62135
[48] Scheinberg, K., Ma, S., & Goldfarb, D. (2010). Sparse inverse covariance selection via alternating linearization methods. In J. Lafferty, C.K.I. Williams, J. Shawe-Taylor, R. S. Zernal, & A. Culotta (Eds.), Advances in neural information processing systems, 23. Red Hook, NY: Curran.
[49] Scheinberg, K., & Rish, I. (2009). Sinco: A greedy coordinate ascent method for sparse inverse covariance selection problem. Preprint. http://www.optimization-online.org/DB_HTML/2009/07/2359.html
[50] Tao, M., & Yuan, X. (2011). Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM Journal on Optimization, 21, 57-81. , · Zbl 1218.90115
[51] Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58(1), 267-288. · Zbl 0850.62538
[52] Wang, C., Sun, D., & Toh, K. C. (2010). Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm. SIAM Journal on Optimization, 20, 2994-3013. , · Zbl 1211.90130
[53] Wang, Y., Yang, J., Yin, W., & Zhang, Y. (2008). A new alternating minimization algorithm for total variation image reconstruction. SIAM Journal on Imaging Sciences, 1(3), 248-272. , · Zbl 1187.68665
[54] Wen, Z., Goldfarb, D., & Yin, W. (2010). Alternating direction augmented Lagrangian methods for semidefinite programming. Mathematical Programming Computation, 2, 203-230. , · Zbl 1206.90088
[55] Wille, A., Zimmermann, P., Vranová, E., Fürholz, A., Laule, O., Bleuler, S., (2004). Sparse graphical gaussian modeling of the isoprenoid gene network in Arabidopsis thaliana. Genome Biology, 5(11), R92. ,
[56] Witten, D. M., Friedman, J. H., & Simon, N. (2011). New insights and faster computations for the graphical lasso. Journal of Computational and Graphical Statistics, 20(4), 892-900. ,
[57] Xue, L., Ma, S., & Zou, H. (2012). Positive definite ##img## penalized estimation of large covariance matrices. Journal of the American Statistical Association, 107(500), 1480-1491. , · Zbl 1258.62063
[58] Xue, L., & Zou, H. (2012). Regularized rank-based estimation of high-dimensional nonparanormal graphical models. Annals of Statistics, 40, 2541-2571. , · Zbl 1373.62138
[59] Yang, J., & Zhang, Y. (2011). Alternating direction algorithms for ##img## problems in compressive sensing. SIAM Journal on Scientific Computing, 33(1), 250-278. , · Zbl 1256.65060
[60] Yuan, M. (2010). High dimensional inverse covariance matrix estimation via linear programming. Journal of Machine Learning Research, 11, 2261-2286. · Zbl 1242.62043
[61] Yuan, M., & Lin, Y. (2007). Model selection and estimation in the gaussian graphical model. Biometrika, 94(1), 19-35. , · Zbl 1142.62408
[62] Yuan, X. (2012). Alternating direction methods for sparse covariance selection. Journal of Scientific Computing, 51, 261-273. , · Zbl 1255.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.