High-dimensional Ising model selection using ℓ1-regularized logistic regression

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

997 citations recorded by the source corpus.

We consider the problem of estimating the graph associated with a binary Ising 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. The method is analyzed under high-dimensional scaling in which both the number of nodes $p$ and maximum neighborhood size $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)$ and the model parameters for the method to succeed in consistently estimating the neighborhood of every node in the graph simultaneously. With coherence conditions imposed 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 exponentially decaying error. When these same conditions are imposed directly on the sample matrices, we show that a reduced sample size of $n=\Omega(d^2\log p)$ suffices for the method to estimate neighborhoods consistently. Although this paper focuses on the binary graphical models, we indicate how a generalization of the method of the paper would apply to general discrete Markov random fields.

Subfields: Artificial Intelligence, Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

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

In Artificial Intelligence

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

Protein 3D Structure Computed from Evolutionary Sequence Variation (2011, background): “A partial analogy can be drawn to the inverse Ising or Potts problem, in which heterogeneous local couplings between discrete state variables are derived from measurements of twopoint correlation functions [34,35,36,37,38].”
Direct-coupling analysis of residue coevolution captures native contacts across many protein families (2011, background): “9] suggest perturbative expansion schemes, whereas [10] uses pseudo-likelihoods decoupling inference for different”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, methodology): “For generalized linear models (GLMs) and exponential family models, estima ors based onl1-regularized maximum likelihood have also been studied, including results on ris k consistency [18] and model selection consistency [11].”
Multivariate Bernoulli distribution (2012, background): “[13] pointed out that the higher order interactions, which is referred to as clique effects in this paper, can be converted to pairwise ones through the introduction of additional variables and thus retain the Markovian structure of the network defined in [19].”
A Constrained ℓ1 Minimization Approach to Sparse Precision Matrix Estimation (2011, methodology): “Ravikumar and Wainwright (2009) considered high-dimensional Ising model selection using 1- regularized logistic regression.”
Dynamical Models and tracking regret in online convex programming (2013, methodology): “…of Dynamic Mirror Descent (DMD) combined with the Fixed share algorithm (which we call Dynamic Fixed Share (DFS)), we consider two scenarios: reconstruction of a dynamic scene (i.e., video) from sequential compressed sensing observations, and tracking connections in a dynamic social network.”
Efficient Distributed Learning with Sparsity (2016, background): “As shown in (Meinshausen and Bühlmann, 2006; Ravikumar et al., 2010), these model selection problems can be reduced to solving parallel `1 regularized linear regression and logistic regression problems, respectively.”
Learning the Structure of Sum-Product Networks (2013, methodology): “The methods of Della Pietra et al. (1997) and Ravikumar et al. (2010) are denoted as DP and L1, respectively.”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “`1-reguralized logistic regression [33], LASSO regression [41] and Elastic Net regression [47].”
Bayesian model choice and information criteria in sparse generalized linear models (2011, methodology): “…selection, where regressions are performed to model each node’s dependence on the other nodes in the graph (“neighborhood selection” for each node), and these neighborhoods are then combined to hypothesize a sparse graphical model; see Meinshausen and Bühlmann (2006) and Ravikumar et al. (2010).”
Inverse statistical problems: from the inverse Ising problem to data science (2017, neutral): “Setting the derivatives of with respect to p ( sss ) to zero yields the Ising model (1).”
Learning the Structure of Generative Models without Labeled Data (2017, methodology): “Whereas the rate of Corollary 2 depends on the maximum number of dependencies that could affect a variable in the model class, the rate of Ravikumar et al. (2010) depends cubically on the maximum number of dependencies that actually affect any variable in the true model and only logarithmically in…”