High-Dimensional Graphical Model Selection Using \ell₁-Regularized Logistic Regression

MaRDI QIDQ6209283zbMATH OpenFDO

Authors Pradeep Ravikumar, Martin J. Wainwright, John Lafferty

Publication date 25 April 2008

Abstract: We consider the problem of estimating the graph structure associated with a discrete Markov random field. We describe a method based on $el{l}_1$-regularized logistic regression, in which the neighborhood of any given node is estimated by performing logistic regression subject to an $el{l}_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}logp)$, with the error decaying as $order(exp(-Cn/d^3))$ for some constant $C$. If these same assumptions are imposed directly on the sample matrices, we show that $n=Omega(d^{2}logp)$ samples are sufficient.

This page was built for publication: High-Dimensional Graphical Model Selection Using $\ell_1$-Regularized Logistic Regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209283)