On the Information Theoretic Limits of Learning Ising Models
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.
This theoretical paper derives low bounds on the number of samples needed to learn graphs (and not factors) from data. The paper uses various versions of the Fano lemma, e.g.  conditional to particular graph classes. Derivations and arguments are purely information-theoretic.  The results are probably correct (I did not check the algebra), however I am not sure about the value of what is reported.  Here is the list of deficiencies/questions troubling me in this paper:1)	Assumption on the ferromagnetic and zero-field nature of the Ising model is highly unrealistic for majority of interesting cases.  2)	Assumption on the constancy of the factors (leaving only an “effective temperature” in otherwise uniform ferromagnetic Ising model) within the graph makes it even more restrictive. I am not aware of any learning or inference application where such an assumption may be of a practical inference. 3)	Once the (conditional) Fano lemma is formulated (and this part is rather straightforward and formal) the authors turn to finding subsets of sub-graphs which are large in size and yet have small KL-diameter. Question of the KL divergence is then linked to analysis of the difference in correlations between two representative graphs within the class. Next , the authors suggest that the difference between correlations will be small if one of the correlations is very large, that is when ``spins” at a pair of measurement points are completely aligned (very small temperature), or (another scenario) when  compared graphs are simply close to each other.  These two principles are then used in the ``application” part to modify a preselected candidate sub-graph (as a good candidate) in the way that the new sub-graph would remain close (in terms of the KL divergence). These arguments are correct but trivial – using very little information about the potentially rich correlations GM of the Ising type can provide. This observation emphasizes the very loose nature of the bounds derived.4)	In the application sections (#5,6) the authors apply the scheme to estimate the lower bounds for graphs of special types --- limited by path-length or girth and finally random Erdos-Renyi graphs.  And here again, straightforward estimations (algebra used) seem correct, however I don’t really see a value in any of these results. 5)	The story sold is not constructive. I did not find anywhere in the paper discussion of possible consequences of the information-theoretic consideration for actual learning algorithms.