BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
复制标题
DOI：
--
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
Cho-Jui Hsieh;Mátyás A. Sustik;I. Dhillon;Pradeep Ravikumar;R. Poldrack
中科院分区：
文献类型：
--
作者：
Cho-Jui Hsieh;Mátyás A. Sustik;I. Dhillon;Pradeep Ravikumar;R. Poldrack
L1正则化的高斯极大似然估计(MLE)在恢复稀疏逆协方差矩阵方面具有很强的统计保证，即使在高维环境下也是如此。然而，它需要求解一个困难的非光滑对数行列式规划，其中参数的数量与高斯变量的数量成二次函数关系。因此，最先进的方法不适用于变量超过20,000的问题。在这篇文章中，我们开发了一个算法BIGQUIC，它可以用一台机器和有限的内存来求解100万维的L1正则化的高斯MLE问题(因此有1000亿个参数)。为了做到这一点，我们仔细地利用了问题的基本结构。我们的创新包括一种新颖的块坐标下降方法，通过聚类方案选择块，以最大限度地减少重复计算；并允许对特定组件进行不准确的计算。尽管有这些修改，我们仍然能够从理论上分析我们的过程，并证明BIGQUIC可以达到超线性甚至二次收敛速度。
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.