TY - JOUR

T1 - High-temperature structure detection in ferromagnets

AU - Cao, Yuan

AU - Neykov, Matey

AU - Liu, Han

N1 - Funding Information:
National Science Foundation (BIGDATA 1840866, RI 1408910, CAREER 1841569, TRIPODS 1740735 to H.L.); Alfred P Sloan Fellowship to H.L.
Publisher Copyright:
© 2020 The Author(s) 2019. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.

PY - 2022/3/1

Y1 - 2022/3/1

N2 - This paper studies structure detection problems in high-temperature ferromagnetic (positive interaction only) Ising models. The goal is to distinguish whether the underlying graph is empty, i.e., the model consists of independent Rademacher variables, vs. the alternative that the underlying graph contains a subgraph of a certain structure. We give matching upper and lower minimax bounds under which testing this problem is possible/impossible, respectively. Our results reveal that a key quantity called graph arboricity drives the testability of the problem. On the computational front, under a conjecture of the computational hardness of sparse principal component analysis, we prove that, unless the signal is strong enough, there are no polynomial time tests which are capable of testing this problem. In order to prove this result, we exhibit a way to give sharp inequalities for the even moments of sums of i.i.d. Rademacher random variables which may be of independent interest.

AB - This paper studies structure detection problems in high-temperature ferromagnetic (positive interaction only) Ising models. The goal is to distinguish whether the underlying graph is empty, i.e., the model consists of independent Rademacher variables, vs. the alternative that the underlying graph contains a subgraph of a certain structure. We give matching upper and lower minimax bounds under which testing this problem is possible/impossible, respectively. Our results reveal that a key quantity called graph arboricity drives the testability of the problem. On the computational front, under a conjecture of the computational hardness of sparse principal component analysis, we prove that, unless the signal is strong enough, there are no polynomial time tests which are capable of testing this problem. In order to prove this result, we exhibit a way to give sharp inequalities for the even moments of sums of i.i.d. Rademacher random variables which may be of independent interest.

KW - ferromagnetic Ising model

KW - graph structure detection

KW - minimax testing

KW - total variation distance

UR - http://www.scopus.com/inward/record.url?scp=85128196343&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85128196343&partnerID=8YFLogxK

U2 - 10.1093/imaiai/iaaa032

DO - 10.1093/imaiai/iaaa032

M3 - Article

AN - SCOPUS:85128196343

SN - 2049-8772

VL - 11

SP - 55

EP - 102

JO - Information and Inference

JF - Information and Inference

IS - 1

ER -