High-Dimensional Graphical Model Selection Using ${\ell }_1$-Regularized Logistic Regression

Abstract

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.

Appeared as UC Berkeley, Department of Statistics, Technical Report

Cited by in corpus (13)

• Projected Subgradient Methods for Learning Sparse Gaussians
• Which graphical models are difficult to learn?
• PRISMA: PRoximal Iterative SMoothing Algorithm
• Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data
• Testability of high-dimensional linear models with non-sparse structures
• Selection and Estimation for Mixed Graphical Models
• Convergence Rates of Biased Stochastic Optimization for Learning Sparse Ising Models
• Bayesian Structure Learning for Markov Random Fields with a Spike and Slab Prior
• Improved Estimation in Time Varying Models
• A parallel algorithm for penalized learning of the multivariate exponential family from data of mixed types
• Learning a Common Substructure of Multiple Graphical Gaussian Models
• Dimension reduction and variable selection in case control studies via regularized likelihood optimization
• Decomposition and Model Selection for Large Contingency Tables