Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimization
We study the estimation of the latent variable Gaussian graphical model (LVGGM), where the precision matrix is the superposition of a sparse matrix and a low-rank matrix. In order to speed up the estimation of the sparse plus low-rank components, we propose a sparsity constrained maximum likelihood estimator based on matrix factorization, and an efficient alternating gradient descent algorithm with hard thresholding to solve it. Our algorithm is orders of magnitude faster than the convex relaxation based methods for LVGGM. In addition, we prove that our algorithm is guaranteed to linearly converge to the unknown sparse and low-rank components up to the optimal statistical precision. Experiments on both synthetic and genomic data demonstrate the superiority of our algorithm over the state-ofthe-art algorithms and corroborate our theory.
The paper considers learning the dependency structure of Gaussian graphical models where some variables are latent. Directly applying the usual assumption of sparsity in the precision matrix is difficult because variables that appear correlated might actually both depend on a common latent variable. Previously, Chandrasekaran et al. proposed estimating the model structure by decomposing the full precision matrix into the sum of of a sparse matrix and a low-rank matrix. Likelihood is maximized while the components of the sparse matrix are penalized with an l1 regularizer and the low-rank matrix is penalized with a nuclear norm. Computing the proximal operator to update the low-rank component requires performing SVD in O(d^3) time at each iteration.
The authors propose replacing the low-rank component with its Cholesky decomposition ZZ^T and finding Z directly. The main technical contribution is that they prove linear converge of an alternating gradient algorithm, up to optimal statistical precision.
Experiments show that by avoiding the need for SVD at each iteration, the proposed method is orders of magnitude faster than the method of Chandrasekaran et al. or a related approach that uses ADMM to estimate the model. It is also more accurate on synthetic and gene network data.
Is Huang, Jianhua Z., et al. "Covariance matrix selection and estimation via penalised normal likelihood." Biometrika 93.1 (2006): 85-98 related? They propose regularizing the Cholesky factorization for precision matrix estimation, although without any latent variables. Their motivation is that it avoids needing to check that the estimated precision matrix is PSD, which takes O(d^3) time.