On the Information Theoretic Limits of Learning Ising Models
This work addresses the fundamental limits of learning Ising models, which is important for researchers in statistical learning and graphical models, but it is incremental as it builds on prior specialized results by generalizing them.
The authors tackled the problem of determining the sample complexity lower bounds for learning the underlying graphs of Ising models from i.i.d. samples, by introducing a general framework that isolates key graph-structural properties, which recovers existing results and provides new bounds for previously unconsidered graph classes.
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 Erdős-Rényi graphs in a certain dense setting.