BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
The 1 -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 1 -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.
Summary: This paper presents several extensions to 
      the QUIC algorithm for sparse inverse covariance estimation, which 
      together enable the method to scale to much larger domains that previously 
      possible, with a maximum demonstrated size of a 1 million by 1 million 
      sparse covariance matrix. The main innovations are: 1) a block coordinate 
      descent approach that first clusters the inverse covariance matrix into 
      near-diagonal blocks and then performs an l1 regularized Newton method on 
      the largest size blocks that fit into memory; 2) an incremental approach 
      to computing the log-det term for step size computation, and 3) a method 
      that only computes certain Hessian terms approximately (this and the 
      gradient computations both use conjugate gradient methods, but Hessian 
      terms can use fewer iterations). The authors apply the method to two large 
      synthetic data sets and a real fMRI data set, and show the method is able 
      to learn these large models on a single multi-core machine. 
      Comments: Overall, I think that this is a very good paper. 
      Since this is really an algorithmic paper, there may be some concern that 
      it represents an incremental advance over the QUIC and DC-QUIC papers 
      themselves, but given that the orders of magnitude here are quite 
      significant (20,000^2 -> 1,000,000^2), I think that the methods 
      described are definitely worthy of publication on their own. A few 
      comments/questions: - Can the authors elaborate on how they went about 
      choosing the regularization parameter for domains this large? Normally 
      this is fairly straightforward via cross-validation, but given that a 
      single run here can take many hours, I'm not quite clear how they went 
      about actually finding the choices of lambda mentioned in Section 5. 
      Especially since methods like QUIC tend to have many more non-zero 
      parameters during the optimization than at the final solution, this seems 
      worth discussing. - Similar to the above, would it be possible to 
      show or highlight the number of non-zeros during the optimization phase, 
      and the amount of time this ends up taking? - Is the choice of 
      lambda to achieve degree 20 for the fMRI data actually reasonable? Can we 
      verify that this is a reasonable choice via held-out log-likelihood, or 
      some similar metric? Given that this real data set was by far the most 
      impressive demonstration in my mind, I'm curious if the proposed approach 
      is learning a good model here, or just solving a hard optimization 
      problem. Right now the only analysis is qualitative, which is nice but not 
      ultimately that convincing especially given that they are ultimately just 
      described as "similar" to those discovered by ICA even though that 
      requires first reducing the dimension. - Given that these methods 
      are starting to become quite complex and difficult to independently 
      implement, I hope the authors consider releasing a public version of this 
      code. - Did the authors consider using multifrontal LLT 
      factorizations, etc? Given that they're already using PARMETIS, there are 
      a number of similar "embarrassingly" parallelizable parallel Cholesky 
      factorizations, and for the sparsity levels considered it doesn't seem 
      completely implausible that they might be able to fit factorizations into 
      memory (though of course not the inverse itself). This is a fairly minor 
      point, since I'm sure the authors have put a lot of engineering into these 
      efforts, but I'm genuinely curious if there are interesting tradeoffs 
      involved here. In my experience, CG methods can be widely variable (in 
      terms of the number of iterations needed), for getting an accurate 
      inverse, even with preconditioning.