High-Dimensional Graphical Model Selection Using $\ell_1$-Regularized Logistic Regression

By Pradeep Ravikumar, Martin J. Wainwright, John D. Lafferty. 2008

174 citations recorded by the source corpus.

We consider the problem of estimating the graph structure associated with a discrete Markov random field. We describe a method based on $\ell_1$-regularized logistic regression, in which the neighborhood of any given node is estimated by performing logistic regression subject to an $\ell_1$-constraint. Our framework applies to the high-dimensional setting, in which both the number of nodes $p$ and maximum neighborhood sizes $d$ are allowed to grow as a function of the number of observations $n$. Our main results provide sufficient conditions on the triple $(n, p, d)$ for the method to succeed in consistently estimating the neighborhood of every node in the graph simultaneously. Under certain assumptions on the population Fisher information matrix, we prove that consistent neighborhood selection can be obtained for sample sizes $n = \Omega(d^3 \log p)$, with the error decaying as $\order(\exp(-C n/d^3))$ for some constant $C$. If these same assumptions are imposed directly on the sample matrices, we show that $n = \Omega(d^2 \log p)$ samples are sufficient.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis. (2012, methodology): “Indeed it has been used successfully in learning logistic regression (Lee et al. 2006b) and in various graphical models (Lee et al. 2006a, Wainwright et al. 2007), as well as in point process models of neuronal spike trains (Kelly et al. 2010).”
Sparse and Locally Constant Gaussian Graphical Models (2009, background): “First, we propose local constancy, which encourages finding connectivities between two close or distant clusters of variables, instead of between isolated variables.”
Estimating time-varying networks (2008, methodology): “In the i.i.d. case, when the graph structure does not change over time, Wainwright et al. (2006) have considered an `1 penalized maximum likelihood approach for estimation of the signed neighborhood using (2).”
Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials (2010, methodology): “To address this problem, one can use pseudo-likelihood (Wainwright et al., 2006; Höfling and Tibshirani, 2009) or other approximate methods (Lee et al., 2006; Banerjee et al., 2008).”
An Interior-Point Method for Large-Scale l1-Regularized Logistic Regression (2007, methodology): “It is not surprising that `1-regularized LR can outperform `2-regularized LR, especially when the number of observations is smaller than the number of features (Ng, 2004; Wainwright et al., 2007).”