Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion
This work addresses the scalability issue in statistical learning for large datasets, offering a practical solution for high-dimensional covariance estimation, though it is incremental as it builds on prior theoretical results.
The paper tackles the computational bottleneck of graphical lasso for large-scale sparse inverse covariance estimation by proving an extension that allows solving it via thresholding and maximum determinant matrix completion, and introduces a Newton-CG algorithm that achieves O(n log(1/ε)) time and O(n) memory complexity, solving problems with up to 200,000 variables to high accuracy in under an hour on a standard laptop.
The sparse inverse covariance estimation problem is commonly solved using an $\ell_{1}$-regularized Gaussian maximum likelihood estimator known as "graphical lasso", but its computational cost becomes prohibitive for large data sets. A recent line of results showed--under mild assumptions--that the graphical lasso estimator can be retrieved by soft-thresholding the sample covariance matrix and solving a maximum determinant matrix completion (MDMC) problem. This paper proves an extension of this result, and describes a Newton-CG algorithm to efficiently solve the MDMC problem. Assuming that the thresholded sample covariance matrix is sparse with a sparse Cholesky factorization, we prove that the algorithm converges to an $ε$-accurate solution in $O(n\log(1/ε))$ time and $O(n)$ memory. The algorithm is highly efficient in practice: we solve the associated MDMC problems with as many as 200,000 variables to 7-9 digits of accuracy in less than an hour on a standard laptop computer running MATLAB.