Sparse inverse covariance matrix estimation using quadratic approximation

By Inderjit S. Dhillon, Cho-Jui Hsieh, Mátyás A. Sustik, Pradeep Ravikumar. 2011

349 citations recorded by the source corpus.

The l1 regularized Gaussian maximum likelihood estimator has been shown to have strong statistical guarantees in recovering a sparse inverse covariance matrix, or alternatively the underlying graph structure of a Gaussian Markov Random Field, from very limited samples. We propose a novel algorithm for solving the resulting optimization problem which is a regularized log-determinant program. In contrast to other state-of-the-art methods that largely use first order gradient information, our algorithm is based on Newton's method and employs a quadratic approximation, but with some modifications that leverage the structure of the sparse Gaussian MLE problem. We show that our method is superlinearly convergent, and also present experimental results using synthetic and real application data that demonstrate the considerable improvements in performance of our method when compared to other state-of-the-art methods.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Federated Multi-Task Learning (2017, background): “This is a well-studied problem, and many scalable algorithms have been proposed to solve it [50, 15, 18].”
Optimization Methods for Large-Scale Machine Learning (2016, background): “cture created by a quadratic plus an ‘ 1-norm term, various methods are available for minimizing such a nonsmooth function. For example, coordinate descent is particularly well-suited in this context [153,78] since the global minimizer of q k along a coordinate descent direction can be computed anal”
Robust High-Dimensional Precision Matrix Estimation (2014, methodology): “, 2008], the quadratic approximation method for sparse inverse covariance learning (QUIC) [Hsieh et al., 2011] and the constrained L1-minimization for inverse matrix estimation (CLIME) [Cai et al.”
Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, background): “graphical models [36]–[42], especially in the case when the number of observations is smaller than the sample dimension and the sample covariance becomes singular.”
Efficient Dimensionality Reduction for High-Dimensional Network Estimation (2014, methodology): “For Glasso, we used CRAN R package QUIC (Hsieh et al., 2011); for SIMoNe, we used CRAN R package simone; and for RMLD, we used LogdetPPA (Wang et al.”
Estimating structured high-dimensional covariance and precision matrices: Optimal rates and adaptive estimation (2016, methodology): “Recently, Hsieh et al. (2013) further improved this result and claimed that the optimization problem (27) can be solved even for a million variables.”
On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data (2014, positive): “Inspired by a recent paper [50] which shows that second-order solvers can be faster due to their fast convergence speed, we may turn to second-order algorithms in future studies.”
Large Scale Distributed Sparse Precision Estimation (2013, methodology): “Spurred by these advances in the statistical theory of precision matrix estimation, there has been considerable recent work on developing computationally efficient optimization methods for solving the corresponding statistical estimation problems: see [1, 8, 14, 21, 13], and references therein.”
Learning Graphs From Data: A Signal Representation Perspective (2018, background): “G Such models are known as probabilistic graphical models [5], [6], [14]–[16], where the edges (or lack thereof) in the graph encode conditional independence relationship among the random variables represented by the vertices.”
Dropping Convexity for Faster Semi-definite Optimization (2015, background): “…modern machine learning includes matrix completion [21, 42, 49, 22], aﬃne rank minimization [65, 41, 8], covariance / inverse covariance selection [38, 50], phase retrieval [64, 18, 77, 68], Euclidean distance matrix completion [56], ﬁnding the square root of a PSD matrix [40], and sparse PCA…”
Handbook of Big Data (2016, background): “26 is known as the graphical lasso and has been studied extensively from a computational (Friedman et al., 2007; d’Aspremont et al., 2008; Yuan, 2008; Boyd et al., 2010; Scheinberg et al., 2010; Hsieh et al., 2011; Witten et al., 2011; Mazumder and Hastie, 2012a; Tran-Dinh et al., 2015) and theoreti”
Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems (2012, methodology): “For large k, we can accelerate the computation by maintaining the residual matrix R, Rij ≡ Aij −wTi hj , ∀(i, j) ∈ Ω.”
An improved GLMNET for l1-regularized logistic regression (2011, methodology): “6 The overall procedure of newGLMNET with two-level shrinking is shown in Algorithm 2.”