Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model

For fixed parameter ✓ > 0 and a given graph G = (V, E), we denote the vector encoding G as ✓ = (✓ e ) 2 R d with ✓ e = ✓ for e 2 E(G) and ✓ e = 0 otherwise. For an edge set S, we denote its encoding vector similarly as ✓ S . Moreover, we use P 0 and E 0 to denote the probability measure and expectation of ferromagnetic Ising model with no edges, and P S , E S to denote the probability measure and expectation with encoding vector ✓ S . For statistical query oracle, for any S 2 E and any q 2 Q A , when |E S [q(X)] E 0 [q(X)]| is larger than the statstical deviation of the oracle, it would be possible to tell ✓ S from ✓ 0 . Based on this intuition, we define where ⌧ q,S is defined in (3) with expectations taken under P S . The following lemma from (Fan et al., 2018) states that when T • sup q2Q A |C(q)| < |E|, there would be an oracle that none of the T rounds can distirbutish P S from P 0 . Lemma A.1. For any algorithm A that queries the oracle r for at most T rounds, if T • sup q2Q A |C(q)| < |E|, then there exists a statistical oracle r defined in definition 2.1 s.t. By the above lemma, it suffices to show that T • sup q2Q A |C(q)|/|E| is asyptotically smaller than 1. To bound the term |C(q)|, we split it to the following two sets C + (q) = S 2 E : E S [q(X)] E 0 [q(X)] > ⌧ q,S , C (q) = S 2 E : E S [q(X)] E 0 [q(X)] < ⌧ q,S .