Timezone: »

BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
Cho-Jui Hsieh · Matyas A Sustik · Inderjit Dhillon · Pradeep Ravikumar · Russell Poldrack

Sun Dec 08 11:40 AM -- 12:00 PM (PST) @ Harvey's Convention Center Floor, CC

The l1-regularized Gaussian maximum likelihood estimator (MLE) has been shown to have strong statistical guarantees in recovering a sparse inverse covariance matrix even under high-dimensional settings. However, it requires solving a difficult non-smooth log-determinant program with number of parameters scaling quadratically with the number of Gaussian variables. State-of-the-art methods thus do not scale to problems with more than 20,000 variables. In this paper, we develop an algorithm BigQUIC, which can solve 1 million dimensional l1-regularized Gaussian MLE problems (which would thus have 1000 billion parameters) using a single machine, with bounded memory. In order to do so, we carefully exploit the underlying structure of the problem. Our innovations include a novel block-coordinate descent method with the blocks chosen via a clustering scheme to minimize repeated computations; and allowing for inexact computation of specific components. In spite of these modifications, we are able to theoretically analyze our procedure and show that BigQUIC can achieve super-linear or even quadratic convergence rates.

Author Information

Cho-Jui Hsieh (UCLA)
Matyas A Sustik (University of Texas)
Inderjit Dhillon (Google & UT Austin)
Pradeep Ravikumar (Carnegie Mellon University)
Russell Poldrack (University of Texas)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors