Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models

Abstract

We characterize the effectiveness of a classical algorithm for recovering the Markov graph of a general discrete pairwise graphical model from i.i.d. samples. The algorithm is (appropriately regularized) maximum conditional log-likelihood, which involves solving a convex program for each node; for Ising models this is ${\ell }_1$-constrained logistic regression, while for more general alphabets an ${\ell }_{2,1}$ group-norm constraint needs to be used. We show that this algorithm can recover any arbitrary discrete pairwise graphical model, and also characterize its sample complexity as a function of model width, alphabet size, edge parameter accuracy, and the number of variables. We show that along every one of these axes, it matches or improves on all existing results and algorithms for this problem. Our analysis applies a sharp generalization error bound for logistic regression when the weight vector has an ${\ell }_1$ constraint (or ${\ell }_{2,1}$ constraint) and the sample vector has an ${\ell }_{\infty }$ constraint (or ${\ell }_{2,\infty }$ constraint). We also show that the proposed convex programs can be efficiently solved in $\tilde{O}(n^2)$ running time (where $n$ is the number of variables) under the same statistical guarantees. We provide experimental results to support our analysis.

arXiv comment30 pages, 3 figures

References in corpus (5)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Inverse Ising inference using all the data
• Regularization Techniques for Learning with Matrices
• Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
• Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications

Cited by in corpus (13)

• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
• A global approach for learning sparse Ising models
• Learning Ising Models with Independent Failures
• Privately Learning Markov Random Fields
• Efficient learning of ground & thermal states within phases of matter
• Learning of Discrete Graphical Models with Neural Networks
• Exact recovery and sharp thresholds of Stochastic Ising Block Model
• On Learning Continuous Pairwise Markov Random Fields
• Learning Restricted Boltzmann Machines with Sparse Latent Variables
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis
• Learning Functional Dependencies with Sparse Regression
• Learning and simulating bosonic systems via finite-energy locality
• Learning Restricted Boltzmann Machines with Arbitrary External Fields