Efficient Stochastic Subgradient Descent Algorithms for High-dimensional Semi-sparse Graphical Model Selection

Abstract

We consider the structure learning problem of Gaussian graphical models when the underlying graph is semi-sparse. More specifically, we assume that the number of edges in the graph grows quadratically with the dimension P. Similar to the case of sparse graphs, the problem is formulated as maximizing the data log-likelihood with an ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> norm penalty on the precision matrix (the inverse covariance matrix) that promotes sparsity. We notice that the time complexity of all existing methods is at least O(P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) under the scenario of semi-sparse graphs, thus severely hindering their applications to high-dimensional data. By contrast, the time complexity of the proposed method is only O(P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) with the help of stochastic gradients. We prove the convergence of the proposed algorithm. Numerical results show that the computational time of the proposed method is shorter than that of the state-of-the-art methods when the graph is semi-sparse.