High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression

Abstract

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.

Published in at http://dx.doi.org/10.1214/09-AOS691 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• High-dimensional graphs and variable selection with the Lasso
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• Sparse permutation invariant covariance estimation
• Support union recovery in high-dimensional multivariate regression
• Consistent estimation of the basic neighborhood of Markov random fields

Cited by in corpus (189)

• Sparse and compositionally robust inference of microbial ecological networks
• Improved contact prediction in proteins: Using pseudolikelihoods to infer Potts models
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Strong oracle optimality of folded concave penalized estimation
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Inverse statistical problems: from the inverse Ising problem to data science
• Inverse Statistical Physics of Protein Sequences: A Key Issues Review
• Inverse Ising inference using all the data
• Estimating time-varying networks
• Multivariate Bernoulli distribution
• Adaptive Cluster Expansion for Inferring Boltzmann Machines with Noisy Data
• Bayesian Structure Learning in Sparse Gaussian Graphical Models
• Mean Field Theory For Non-Equilibrium Network Reconstruction
• Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
• High-dimensional structure estimation in Ising models: Local separation criterion
• Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
• Adaptive cluster expansion for the inverse Ising problem: convergence, algorithm and tests
• The Bethe approximation for solving the inverse Ising problem: a comparison with other inference methods
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Honest variable selection in linear and logistic regression models via ${\ell }_1$ and ${\ell }_1+{\ell }_2$ penalization
• Stable Graphical Model Estimation with Random Forests for Discrete, Continuous, and Mixed Variables
• Global analysis of more than 50,000 SARS-Cov-2 genomes reveals epistasis between 8 viral genes
• Pseudolikelihood Decimation Algorithm Improving the Inference of the Interaction Network in a General Class of Ising Models
• On Graphical Models via Univariate Exponential Family Distributions
• mgm: Estimating Time-Varying Mixed Graphical Models in High-Dimensional Data
• On Learning Discrete Graphical Models Using Greedy Methods
• Mean-field theory for the inverse Ising problem at low temperatures
• Reconstruction of recurrent synaptic connectivity of thousands of neurons from simulated spiking activity
• Change-Point Estimation in High-Dimensional Markov Random Field Models
• Nonconcave penalized composite conditional likelihood estimation of sparse Ising models
• On perturbed proximal gradient algorithms
• Learning Large-Scale Bayesian Networks with the sparsebn Package
• Sequential anomaly detection in the presence of noise and limited feedback
• Efficient Distributed Learning with Sparsity
• Spectral Methods for Learning Multivariate Latent Tree Structure
• High-Dimensional Inference with the generalized Hopfield Model: Principal Component Analysis and Corrections
• High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods
• Bethe-Peierls approximation and the inverse Ising model
• Tight conditions for consistency of variable selection in the context of high dimensionality
• Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• Graphical Models for Zero-Inflated Single Cell Gene Expression
• Mapping of attention mechanisms to a generalized Potts model
• Estimating heterogeneous graphical models for discrete data with an application to roll call voting
• Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
• Large Pseudo-Counts and $L_2$-Norm Penalties Are Necessary for the Mean-Field Inference of Ising and Potts Models
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Assessing the accuracy of direct-coupling analysis for RNA contact prediction
• Sparse Nonparametric Graphical Models
• U.S. stock market interaction network as learned by the Boltzmann Machine
• Introduction to correlation networks: Interdisciplinary approaches beyond thresholding
• Marginal Pseudo-Likelihood Learning of Markov Network structures
• The log-linear group-lasso estimator and its asymptotic properties
• Higher-order interactions in statistical physics and machine learning: A model-independent solution to the inverse problem at equilibrium
• Bayesian Graphical Models for Multivariate Functional Data
• On Semiparametric Exponential Family Graphical Models
• Solving the inverse Ising problem by mean-field methods in a clustered phase space with many states
• Online Optimization in Dynamic Environments
• Post-Selection Inference for Generalized Linear Models with Many Controls
• Dynamics and Performance of Susceptibility Propagation on Synthetic Data
• Inverse design of disordered stealthy hyperuniform spin chains
• Correlation-Compressed Direct Coupling Analysis
• Inference of the sparse kinetic Ising model using the decimation method
• Square Root Graphical Models: Multivariate Generalizations of Univariate Exponential Families that Permit Positive Dependencies
• Learning Mixed Graphical Models
• High-dimensional Mixed Graphical Models
• High-Dimensional Multivariate Time Series With Additional Structure
• Optimal regularizations for data generation with probabilistic graphical models
• Sparsistent Estimation of Time-Varying Discrete Markov Random Fields
• Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)
• Estimating the interaction graph of stochastic neural dynamics
• SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax
• Quantum algorithms for hedging and the learning of Ising models
• High Dimensional Structure Learning of Ising Models on Sparse Random Graphs
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
• Learning Loosely Connected Markov Random Fields
• Network reconstruction via the minimum description length principle
• The Stochastic complexity of spin models: Are pairwise models really simple?
• Statistical mechanics of the inverse Ising problem and the optimal objective function
• Inverse Ising inference with correlated samples
• Regularization and decimation pseudolikelihood approaches to statistical inference in $XY$-spin models
• Sparse model selection in the highly under-sampled regime
• Resummed mean-field inference for strongly coupled data
• Generalized Direct Change Estimation in Ising Model Structure
• High-dimensional structure learning of binary pairwise Markov networks: A comparative numerical study
• A survey on independence-based Markov networks learning
• On the Correctness and Sample Complexity of Inverse Reinforcement Learning
• Structure Learning of Contextual Markov Networks using Marginal Pseudo-likelihood
• Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields
• Statistical Genetics in and out of Quasi-Linkage Equilibrium (Extended)
• The IBMAP approach for Markov networks structure learning
• Improved Pseudolikelihood Regularization and Decimation methods on Non-linearly Interacting Systems with Continuous Variables
• Active Learning Algorithms for Graphical Model Selection
• A global approach for learning sparse Ising models
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Learning performance in inverse Ising problems with sparse teacher couplings
• An Efficient Pseudo-likelihood Method for Sparse Binary Pairwise Markov Network Estimation
• Network inference in the non-equilibrium steady state
• Approximating faces of marginal polytopes in discrete hierarchical models
• 1-d Ising model using Kronecker sum and Kronecker product
• Biases in Inverse Ising Estimates of Near-Critical Behaviour
• Swapping Variables for High-Dimensional Sparse Regression with Correlated Measurements
• Omitted variable bias of Lasso-based inference methods: A finite sample analysis
• Support Consistency of Direct Sparse-Change Learning in Markov Networks
• PANDA: AdaPtive Noisy Data Augmentation for Regularization of Undirected Graphical Models
• Inference of stochastic time series with missing data
• Selection and Estimation for Mixed Graphical Models
• High-Temperature Structure Detection in Ferromagnets
• Inverse problem for multi-body interaction of nonlinear waves
• Privately Learning Markov Random Fields
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
• Data-driven effective model shows a liquid-like deep learning
• Inverse Ising inference from high-temperature re-weighting of observations
• Nonparametric density estimation by histogram trend filtering
• Learning Max-Margin Tree Predictors
• Sparse Hopfield network reconstruction with ${\ell }_1$ regularization
• 3D Protein Structure Predicted from Sequence
• Model Selection in Undirected Graphical Models with the Elastic Net
• Sparse estimation in Ising Model via penalized Monte Carlo methods
• Pseudo-likelihood-based $M$-estimation of random graphs with dependent edges and parameter vectors of increasing dimension
• A Junction Tree Framework for Undirected Graphical Model Selection
• Information criteria for non-normalized models
• Active Sampling for the Quickest Detection of Markov Networks
• Using Latent Binary Variables for Online Reconstruction of Large Scale Systems
• Graphical Models for Non-Negative Data Using Generalized Score Matching
• Markov random fields factorization with context-specific independences
• Cycle-based Cluster Variational Method for Direct and Inverse Inference
• Covariate-Assisted Bayesian Graph Learning for Heterogeneous Data
• Inferring Multiple Graphical Structures
• Learning the effect of latent variables in Gaussian Graphical models with unobserved variables
• Predictive Learning on Hidden Tree-Structured Ising Models
• On the typical properties of inverse problems in statistical mechanics
• Dichotomization invariant log-mean linear parameterization for discrete graphical models of marginal independence
• Learning high-dimensional graphical models with regularized quadratic scoring
• Post-Regularization Confidence Bands for Ordinary Differential Equations
• Structure learning of undirected graphical models for count data
• Mixtures of Sparse Autoregressive Networks
• On the Sample Complexity of Graphical Model Selection for Non-Stationary Processes
• A Tutorial on Libra: R package for the Linearized Bregman Algorithm in High Dimensional Statistics
• Region Detection in Markov Random Fields: Gaussian Case
• Learning of Discrete Graphical Models with Neural Networks
• Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization
• Exact recovery and sharp thresholds of Stochastic Ising Block Model
• Adaptive Reduced Rank Regression
• Multivariate binary probability distribution in the Grassmann formalism
• Structure Learning of Partitioned Markov Networks
• The neighborhood lattice for encoding partial correlations in a Hilbert space
• Group Invariance and Computational Sufficiency
• Linear and Parallel Learning of Markov Random Fields
• Error bounds for sparse classifiers in high-dimensions
• A Unified Dynamic Approach to Sparse Model Selection
• A parallel algorithm for penalized learning of the multivariate exponential family from data of mixed types
• Bayesian Analysis of High-dimensional Discrete Graphical Models
• Optimal Rates for Learning Hidden Tree Structures
• Structure Learning in Inverse Ising Problems Using ${\ell }_2$-Regularized Linear Estimator
• On the trade-off between complexity and correlation decay in structural learning algorithms
• Learning Exponential Family Graphical Models with Latent Variables using Regularized Conditional Likelihood
• Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
• On Model Selection Consistency of Lasso for High-Dimensional Ising Models
• Learning Undirected Graphical Models with Structure Penalty
• A causal fused lasso for interpretable heterogeneous treatment effects estimation
• Worldwide bilateral geopolitical interactions network inferred from national disciplinary profiles
• Controlling the False Discovery Rate for Binary Feature Selection via Knockoff
• Stationary Geometric Graphical Model Selection
• Provable Training Set Debugging for Linear Regression
• Penalized polytomous ordinal logistic regression using cumulative logits. Application to network inference of zero-inflated variables
• Learning Data Dependency with Communication Cost
• Data quality for the inverse Ising problem
• Inferring network structure in non-normal and mixed discrete-continuous genomic data
• Kernel Ordinary Differential Equations
• Feature ranking for multi-label classification using Markov Networks
• GDN: A Stacking Network Used for Skin Cancer Diagnosis
• Fine-Gray competing risks model with high-dimensional covariates: estimation and Inference
• Consistent model selection for estimating functional interactions among stochastic neurons with variable-length memory
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis
• Vanilla Lasso for sparse classification under single index models
• Classification of SARS-CoV-2 Variants through The Epistatical Circos Plots with Convolutional Neural Networks
• Learning Pairwise Graphical Models with Nonlinear Sufficient Statistics
• Robust Variable and Interaction Selection for Logistic Regression and Multiple Index Models
• Hub Detection in Gaussian Graphical Models
• Logistic regression and Ising networks: prediction and estimation when violating lasso assumptions
• Structure Learning of Markov Random Fields through Grow-Shrink Maximum Pseudolikelihood Estimation
• Tuning parameter calibration for ${\ell }_1$-regularized logistic regression
• Learning binary undirected graph in low dimensional regime
• High Dimensional Logistic Regression Under Network Dependence
• Improved error rates for sparse (group) learning with Lipschitz loss functions
• Learning pairwise Markov network structures using correlation neighborhoods