mlsanityData to 14 Oct 2026

Learning the Sherrington-Kirkpatrick Model Even at Low Temperature

arXiv 2411.11174 ↗First posted 17 Nov 2024cs.LG cs.DS math.STcited by 5

Not on the map. Why?

Abstract (arXiv)

We consider the fundamental problem of learning the parameters of an undirected graphical model or Markov Random Field (MRF) in the setting where the edge weights are chosen at random. For Ising models, we show that a multiplicative-weight update algorithm due to Klivans and Meka learns the parameters in polynomial time for any inverse temperature β ≤ √log n. This immediately yields an algorithm for learning the Sherrington-Kirkpatrick (SK) model beyond the high-temperature regime of β < 1. Prior work breaks down at β = 1 and requires heavy machinery from statistical physics or functional inequalities. In contrast, our analysis is relatively simple and uses only subgaussian concentration. Our results extend to MRFs of higher order (such as pure p-spin models), where even results in the high-temperature regime were not known.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 14 of its 46 references that are in the map. First posted on arXiv 17 Nov 2024.

Builds on

14 of 46 references.

References · 14

  1. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  2. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  3. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  4. 2017Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applicationscited by 21
  5. 2019Efficient Learning of Discrete Graphical Modelscited by 21
  6. 2020Near-Optimal Learning of Tree-Structured Distributions by Chow-Liucited by 20
  7. 2018Sparse Logistic Regression Learns All Discrete Pairwise Graphical Modelscited by 16
  8. 2020Privately Learning Markov Random Fieldscited by 14
  9. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  10. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 14
  11. 2019Learning Ising Models with Independent Failurescited by 8
  12. 2021Learning to Sample from Censored Markov Random Fieldscited by 6
2 more
  1. 2017A statistical physics approach to learning curves for the Inverse Ising problemcited by 4
  2. 2023Universality of Spectral Independence with Applications to Fast Mixing in Spin Glassescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025Learning Juntas under Markov Random Fieldscited by 3
  2. 2025Estimating Ising Models in Total Variation Distancecited by 3
  3. 2025Learning CNF formulas from uniform random solutions in the local lemma regimecited by 2
  4. 2026Learning mathsfAC0 under Locally Sampleable Graphical Modelscited by 1
  5. 2026Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescuecited by 0