Sparse Inverse Covariance Selection via Alternating Linearization Methods
Katya Scheinberg Department of ISE Lehigh University、Shiqian Ma, Donald Goldfarb Department of IEOR Columbia University
Abstract
Gaussian graphical models are of great interest in statistical learning. Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an $\ell_{1}$ -regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem’s special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an $\epsilon$ -optimal solution in $O(1/\epsilon)$ iterations. Numerical experiments on both synthetic and real data from gene association networks show that a practical version of this algorithm outperforms other competitive algorithms.
中文速览
稀疏逆协方差矩阵估计（sparse inverse covariance selection）是学习高斯图模型结构的核心问题，但现有一阶方法要么缺乏理论收敛保证，要么实际表现不理想。本文提出一种基于交替线性化（alternating linearization）的一阶优化算法（ALM），通过将目标函数的两项交替线性化并加近端正则项，使每次迭代的子问题都有解析闭合解，从而高效求解原始稀疏逆协方差问题。理论上证明该算法在 O(1/ε) 次迭代内可获得 ε-最优解，填补了同类方法普遍缺乏复杂度界的空白。在合成数据与真实基因关联网络数据上的大量实验表明，ALM 的实际运行速度和精度均显著优于当时最先进的投影次梯度法（PSM）和变步长平滑法（VSM），为大规模高斯图模型的结构学习提供了既有理论保障又高效实用的新工具。
原文 arXiv:1011.0097;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1011.0097v1