# On the Information Theoretic Limits of Learning Ising Models

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2014.

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

- [A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning](https://mlsanity.com/paper/2103.04446/) (2021)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Information-Theoretic Bounds for Integral Estimation](https://mlsanity.com/paper/2102.10199/) (2021)
- [Entropy-driven Unsupervised Keypoint Representation Learning in Videos](https://mlsanity.com/paper/2209.15404/) (2022)

## Abstract (arXiv)

We provide a general framework for computing lower-bounds on the sample complexity of recovering the underlying graphs of Ising models, given i.i.d samples. While there have been recent results for specific graph classes, these involve fairly extensive technical arguments that are specialized to each specific graph class. In contrast, we isolate two key graph-structural ingredients that can then be used to specify sample complexity lower-bounds. Presence of these structural properties makes the graph class hard to learn. We derive corollaries of our main result that not only recover existing recent results, but also provide lower bounds for novel graph classes not considered previously. We also extend our framework to the random graph setting and derive corollaries for ErdHos-R'enyi graphs in a certain dense setting.