Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models

Abstract

We consider the problem of learning the underlying graph of an unknown Ising model on p spins from a collection of i.i.d. samples generated from the model. We suggest a new estimator that is computationally efficient and requires a number of samples that is near-optimal with respect to previously established information-theoretic lower-bound. Our statistical estimator has a physical interpretation in terms of "interaction screening". The estimator is consistent and is efficiently implemented using convex optimization. We prove that with appropriate regularization, the estimator recovers the underlying graph using a number of samples that is logarithmic in the system size p and exponential in the maximum coupling-intensity and maximum node-degree.

To be published in Advances in Neural Information Processing Systems 30

Cited by in corpus (22)

• Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
• High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware
• Evaluating Ising Processing Units with Integer Programming
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• A global approach for learning sparse Ising models
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• High-Temperature Structure Detection in Ferromagnets
• Learning Ising Models with Independent Failures
• Privately Learning Markov Random Fields
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Sample-Optimal and Efficient Learning of Tree Ising models
• Exact recovery and sharp thresholds of Stochastic Ising Block Model
• On Learning Continuous Pairwise Markov Random Fields
• Statistical Inference in the Differential Privacy Model
• Learning of Discrete Graphical Models with Neural Networks
• Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics
• Learning Gaussian Graphical Models via Multiplicative Weights
• On Model Selection Consistency of Lasso for High-Dimensional Ising Models
• Optimal Rates for Learning Hidden Tree Structures
• Learning Restricted Boltzmann Machines with Arbitrary External Fields
• High Dimensional Logistic Regression Under Network Dependence
• From Boltzmann Machines to Neural Networks and Back Again