# Learning the Sherrington-Kirkpatrick Model Even at Low Temperature

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

## 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 (most cited first, 14 of 14)

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Efficient Learning of Discrete Graphical Models](https://mlsanity.com/paper/1902.00600/) (2019)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [Privately Learning Markov Random Fields](https://mlsanity.com/paper/2002.09463/) (2020)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Learning Ising Models with Independent Failures](https://mlsanity.com/paper/1902.04728/) (2019)
- [Learning to Sample from Censored Markov Random Fields](https://mlsanity.com/paper/2101.06178/) (2021)
- [A statistical physics approach to learning curves for the Inverse Ising problem](https://mlsanity.com/paper/1705.05403/) (2017)
- [Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses](https://mlsanity.com/paper/2307.10466/) (2023)

## Built on by (most cited first, 5 of 5)

- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)
- [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026)

## 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.