High-dimensional Ising model selection using _1-regularized logistic regression

DOI10.1214/09-AOS691zbMATH Open1189.62115arXiv1010.0311WikidataQ98839732 ScholiaQ98839732MaRDI QIDQ973867FDOQ973867

Authors: Pradeep Ravikumar, Martin J. Wainwright, John Lafferty 

Publication date: 26 May 2010

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: We consider the problem of estimating the graph associated with a binary Ising 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. 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}logp)$ 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}logp)$ 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.

Full work available at URL: https://arxiv.org/abs/1010.0311

Recommendations

• High-dimensional Ising model selection with Bayesian information criteria
• Sparse estimation in Ising model via penalized Monte Carlo methods
• High-dimensional structure estimation in Ising models: local separation criterion
• High-dimensional graphs and variable selection with the Lasso
• Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data

zbMATH Keywords

model selectiongraphical modelsstructure learninghigh-dimensional asymptoticsMarkov random fields\(\ell _1\)-regularizationconvex risk minimization

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Random fields; image analysis (62M40) Applications of graph theory (05C90) Generalized linear models (logistic models) (62J12) Artificial intelligence (68T99)

Cites Work

• Causation, prediction, and search
• Graphical models, exponential families, and variational inference
• Matrix Analysis
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• High-dimensional graphs and variable selection with the Lasso
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Model Selection and Estimation in Regression with Grouped Variables
• Sparse permutation invariant covariance estimation
• Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• The Group Lasso for Logistic Regression
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Probability Inequalities for Sums of Bounded Random Variables
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Approximating discrete probability distributions with dependence trees
• Local operator theory, random matrices and Banach spaces.
• Just relax: convex programming methods for identifying sparse signals in noise
• Convex Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximum likelihood bounded tree-width Markov networks
• Blockwise sparse regression
• Support union recovery in high-dimensional multivariate regression
• An interior-point method for large-scale \(l_1\)-regularized logistic regression
• Title not available (Why is that?)
• Consistent estimation of the basic neighborhood of Markov random fields
• Learning factor graphs in polynomial time and sample complexity
• Reconstruction of Markov random fields from samples: some observations and algorithms

Cited In (only showing first 100 items - show all)

• Probabilistic graphical models and Markov networks
• Estimating time-varying networks
• Nonparametric discriminant analysis with network structures in predictor
• Combinatorial approach to exactly solve the 1D Ising model
• Region selection in Markov random fields: Gaussian case
• Robust Variable and Interaction Selection for Logistic Regression and General Index Models
• Graphical models for zero-inflated single cell gene expression
• A sparse ising model with covariates
• Sparse directed acyclic graphs incorporating the covariates
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Stable graphical model estimation with random forests for discrete, continuous, and mixed variables
• Simple method for inference in inverse Ising problem using full data
• Graphical-model based high dimensional generalized linear models
• Reconstruction of recurrent synaptic connectivity of thousands of neurons from simulated spiking activity
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Structure estimation for discrete graphical models: generalized covariance matrices and their inverses
• Adaptive cluster expansion for the inverse Ising problem: convergence, algorithm and tests
• High-dimensional Ising model selection with Bayesian information criteria
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• On model selection consistency of regularized M-estimators
• Tuning parameter calibration for \(\ell_1\)-regularized logistic regression
• Honest variable selection in linear and logistic regression models via \(\ell _{1}\) and \(\ell _{1}+\ell _{2}\) penalization
• Statistical mechanics of the inverse Ising problem and the optimal objective function
• Estimating finite mixtures of ordinal graphical models
• Covariance structure approximation via gLasso in high-dimensional supervised classification
• Universality of the mean-field for the Potts model
• Sparse linear models and \(l_1\)-regularized 2SLS with high-dimensional endogenous regressors and instruments
• Network-based discriminant analysis for multiclassification
• Sparse and low-rank matrix regularization for learning time-varying Markov networks
• Tight conditions for consistency of variable selection in the context of high dimensionality
• Computational implications of reducing data to sufficient statistics
• Estimating heterogeneous graphical models for discrete data with an application to roll call voting
• Poisson dependency networks: gradient boosted models for multivariate count data
• Structure Learning of Contextual Markov Networks using Marginal Pseudo‐likelihood
• A Unified Framework for Structured Graph Learning via Spectral Constraints
• Estimation of high-dimensional partially-observed discrete Markov random fields
• Loglinear model selection and human mobility
• Log‐mean Linear Parameterization for Discrete Graphical Models of Marginal Independence and the Analysis of Dichotomizations
• Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields
• Cycle-based cluster variational method for direct and inverse inference
• Structure learning in inverse Ising problems using ℓ ₂-regularized linear estimator
• A joint convex penalty for inverse covariance matrix estimation
• Parameter inference in a probabilistic model using clustered data
• Latent binary MRF for online reconstruction of large scale systems
• Inferring multiple graphical structures
• Bayesian structure learning in sparse Gaussian graphical models
• A general algorithm for covariance modeling of discrete data
• Comment on ``Hypothesis testing by convex optimization
• Dimension reduction and variable selection in case control studies via regularized likelihood optimization
• Local conditional and marginal approach to parameter estimation in discrete graphical models
• Learning loopy graphical models with latent variables: efficient methods and guarantees
• The log-linear group-lasso estimator and its asymptotic properties
• Bayesian graphical models for differential pathways
• Kernel Knockoffs Selection for Nonparametric Additive Models
• Composite mixture of log-linear models with application to psychiatric studies
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Sparse nonparametric graphical models
• Multivariate Bernoulli distribution
• Title not available (Why is that?)
• Estimation of high-dimensional graphical models using regularized score matching
• High-dimensional structure estimation in Ising models: local separation criterion
• Nonconcave penalized composite conditional likelihood estimation of sparse Ising models
• The IBMAP approach for Markov network structure learning
• Fluctuations in mean-field Ising models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Kernel Ordinary Differential Equations
• ROCKET: robust confidence intervals via Kendall's tau for transelliptical graphical models
• Sparse covariance estimation in heterogeneous samples
• Nonparametric augmented probability weighting with sparsity
• Title not available (Why is that?)
• Direct Learning of Sparse Changes in Markov Networks by Density Ratio Estimation
• Multiclass analysis and prediction with network structured covariates
• An oracle approach for interaction neighborhood estimation in random fields
• Title not available (Why is that?)
• Exact recovery in the Ising blockmodel
• Title not available (Why is that?)
• Robust measurement via a fused latent and graphical item response theory model
• Learning performance in inverse Ising problems with sparse teacher couplings
• A global approach for learning sparse Ising models
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Identifying interacting pairs of sites in Ising models on a countable set
• Unified analysis of stochastic gradient methods for composite convex and smooth optimization
• An Additive Graphical Model for Discrete Data
• Sparse inverse covariance estimation for high-throughput microRNA sequencing data in the Poisson log-normal graphical model
• Structure learning of exponential family graphical model with false discovery rate control
• FDR control and power analysis for high-dimensional logistic regression via Stabkoff
• Time Series Source Separation Using Dynamic Mode Decomposition
• High-dimensional structure learning of binary pairwise Markov networks: a comparative numerical study
• Inference under Fine-Gray competing risks model with high-dimensional covariates
• Ising models for neural activity inferred via selective cluster expansion: structural and coding properties
• Title not available (Why is that?)
• A stochastic block Ising model for multi-layer networks with inter-layer dependence
• Bayesian model selection for high-dimensional Ising models, with applications to educational data
• Empirical comparison study of approximate methods for structure selection in binary graphical models
• Transmission matrix inference via pseudolikelihood decimation
• Tensor recovery in high-dimensional Ising models
• High-dimensional undirected graphical models for arbitrary mixed data
• Inference of large modified Poisson-type graphical models: application to RNA-seq data in childhood atopic asthma studies

Uses Software

• spatial
• pcalg
• TETRAD

This page was built for publication: High-dimensional Ising 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 Q973867)