mlsanityData to 7 Oct 2026

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

arXiv 1605.07252 ↗First posted 24 May 2016cs.LG cond-mat.stat-mech cs.ITcited by 43

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 3; 2023: 6; 2024: 11; 2025: 9; 2026: 5.

43 papers.

Sort:

By area:

  1. 2023A survey on the complexity of learning quantum statescited by 31
  2. 2023Provable benefits of score matchingcited by 18
  3. 2022Optimal estimation of Gaussian DAG modelscited by 14
  4. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 13
  5. 2021Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential familiescited by 10
  6. 2021A Computationally Efficient Method for Learning Exponential Family Distributionscited by 10
  7. 2021Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Modelscited by 9
  8. 2021High-quality Thermal Gibbs Sampling with Quantum Annealing Hardwarecited by 9
  9. 2021Optimal learning of quantum Hamiltonians from high-temperature Gibbs statescited by 8
  10. 2024Structure learning of Hamiltonians from real-time evolutioncited by 8
  11. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
  12. 2025Local Diffusion Models and Phases of Data Distributionscited by 8
31 more
  1. 2022Learning and Testing Latent-Tree Ising Models Efficientlycited by 7
  2. 2021Learning Continuous Exponential Families Beyond Gaussiancited by 6
  3. 2024Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelinescited by 6
  4. 2021Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamicscited by 5
  5. 2024Network reconstruction via the minimum description length principlecited by 5
  6. 2024Learning the Sherrington-Kirkpatrick Model Even at Low Temperaturecited by 5
  7. 2021Ising Model Selection Using ℓ1-Regularized Linear Regression: A Statistical Mechanics Analysiscited by 4
  8. 2022Masked prediction tasks: a parameter identifiability viewcited by 4
  9. 2023Learning Energy-Based Representations of Quantum Many-Body Statescited by 2
  10. 2023On Computationally Efficient Learning of Exponential Family Distributionscited by 2
  11. 2024A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimationcited by 2
  12. 2024Discrete distributions are learnable from metastable samplescited by 2
  13. 2024Efficient Hamiltonian, structure and trace distance learning of Gaussian statescited by 2
  14. 2025Learning Juntas under Markov Random Fieldscited by 2
  15. 2025Learning CNF formulas from uniform random solutions in the local lemma regimecited by 2
  16. 2025Estimating Ising Models in Total Variation Distancecited by 2
  17. 2021On Model Selection Consistency of Lasso for High-Dimensional Ising Modelscited by 1
  18. 2024Cyclic Group Projection for Enumerating Quasi-Cyclic Codes Trapping Setscited by 1
  19. 2025On the role of non-linear latent features in bipartite generative neural networkscited by 1
  20. 2025Learning Gaussian DAG Models without Condition Number Boundscited by 1
  21. 2026Learning mathsfAC0 under Locally Sampleable Graphical Modelscited by 1
  22. 2023Interaction Screening and Pseudolikelihood Approaches for Tensor Learning in Ising Modelscited by 0
  23. 2024Topology-Aware Exploration of Energy-Based Models Equilibrium: Toric QC-LDPC Codes and Hyperbolic MET QC-LDPC Codescited by 0
  24. 2024Quantum Maximum Entropy Inference and Hamiltonian Learningcited by 0
  25. 2025One-Shot Learning for k-SATcited by 0
  26. 2025Optimal structure learning and conditional independence testingcited by 0
  27. 2025Scientific Data Compression and Super-Resolution Samplingcited by 0
  28. 2026Computationally sufficient statistics for Ising modelscited by 0
  29. 2026Discrete Diffusion with Sample-Efficient Estimators for Conditionalscited by 0
  30. 2026Selecting Optimal Variable Order in Autoregressive Ising Modelscited by 0
  31. 2026Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithmcited by 0