Large Scale Distributed Sparse Precision Estimation

Huahua Wang, Cho-Jui Hsieh, Arindam Banerjee, Pradeep Ravikumar, Inderjit Dhillon

Abstract:   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.

Download: pdf


  • Large Scale Distributed Sparse Precision Estimation (pdf, software)
    H. Wang, C. Hsieh, A. Banerjee, P. Ravikumar, I. Dhillon.
    In Neural Information Processing Systems (NIPS), December 2013.