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

arXiv: https://arxiv.org/abs/1605.07252 · HTML: https://mlsanity.com/paper/1605.07252/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2016.

## Built on by (most cited first, 30 of 43)

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Provable benefits of score matching](https://mlsanity.com/paper/2306.01993/) (2023)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families](https://mlsanity.com/paper/2110.04719/) (2021)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware](https://mlsanity.com/paper/2109.01690/) (2021)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Optimal learning of quantum Hamiltonians from high-temperature Gibbs states](https://mlsanity.com/paper/2108.04842/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Local Diffusion Models and Phases of Data Distributions](https://mlsanity.com/paper/2508.06614/) (2025)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning Continuous Exponential Families Beyond Gaussian](https://mlsanity.com/paper/2102.09198/) (2021)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines](https://mlsanity.com/paper/2407.21046/) (2024)
- [Network reconstruction via the minimum description length principle](https://mlsanity.com/paper/2405.01015/) (2024)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Ising Model Selection Using ℓ1-Regularized Linear Regression: A Statistical Mechanics Analysis](https://mlsanity.com/paper/2102.03988/) (2021)
- [Masked prediction tasks: a parameter identifiability view](https://mlsanity.com/paper/2202.09305/) (2022)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Learning Energy-Based Representations of Quantum Many-Body States](https://mlsanity.com/paper/2304.04058/) (2023)
- [On Computationally Efficient Learning of Exponential Family Distributions](https://mlsanity.com/paper/2309.06413/) (2023)
- [A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation](https://mlsanity.com/paper/2409.18209/) (2024)
- [Discrete distributions are learnable from metastable samples](https://mlsanity.com/paper/2410.13800/) (2024)
- [Efficient Hamiltonian, structure and trace distance learning of Gaussian states](https://mlsanity.com/paper/2411.03163/) (2024)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [On Model Selection Consistency of Lasso for High-Dimensional Ising Models](https://mlsanity.com/paper/2110.08500/) (2021)

## Abstract (arXiv)

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.