Large Scale Distributed Sparse Precision Estimation
We consider the problem of sparse precision matrix estimation in high dimensions using the CLIME estimator, which has several desirable theoretical properties. We present an inexact alternating direction method of multiplier (ADMM) algorithm for CLIME, and establish rates of convergence for both the objective and optimality conditions. Further, we develop a large scale distributed framework for the computations, which scales to millions of dimensions and trillions of parameters, using hundreds of cores. The proposed framework solves CLIME in columnblocks and only involves elementwise operations and parallel matrix multiplications. We evaluate our algorithm on both shared-memory and distributed-memory architectures, which can use block cyclic distribution of data and parameters to achieve load balance and improve the efficiency in the use of memory hierarchies. Experimental results show that our algorithm is substantially more scalable than state-of-the-art methods and scales almost linearly with the number of cores.
Summary of the paper This paper is 
      concerned with the resolution of covariance selection problems in a very 
      large scale setup (up to millions of features and trillions of 
      parameters). The estimator considered is the CLIME, which is known to 
      provide an estimator of the precision matrix of a Gaussian vector that can 
      be solved column by column, thus more easily amenable to distributed 
      computations. Theoretical analysis is also claimed to be easier than for 
      the Graphical-Lasso. The authors developed a new algorithm to fit the 
      CLIME by solving the problem block wise rather than column wise, couple to 
      an inexact direction method of multipliers. Theoretical results on the 
      convergence rate of this algorithm are stated, in term of both objective 
      function and distance to optimality. Special attention is paid for special 
      matrix structures (sparse and low rank) along the computation to reduce 
      the computational burden. The algorithm is implemented within a scalable 
      parallel computation framework for both shared and distributed memory 
      systems. In the numerical studies, comparison are made in term of runtime 
      with its direct competitors on both synthetic and real data. A detailed 
      study concerning this new algorithm is also provided to evaluate the 
      speedup regarding the block sizes and the number of cores on both shared 
      memory and distributed memory systems. Comments This paper 
      is well written and very clear. Novelty and contributions brought by the 
      method are clearly stated in the introduction and connexion to existing 
      works clearly established, with sounded bibliographical references. The 
      algorithm is nicely introduced with a good balance between technical 
      points of numerical analysis/algebra and theoretical guarantees for 
      convergence rates. The numerical analysis is appropriate and the 
      implementation of the algorithm shows very impressive performances. 
      My only concern is the availability of such a method: if the 
      source code (mostly based upon open source libraries) is not made 
      available to the community, their is no point in such a work.