Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

We study identity testing for restricted Boltzmann machines (RBMs), and more\ngenerally for undirected graphical models. Given sample access to the Gibbs\ndistribution corresponding to an unknown or hidden model $M^*$ and given an\nexplicit model $M$, can we distinguish if either $M = M^*$ or if they are\n(statistically) far apart? Daskalakis et al. (2018) presented a polynomial-time\nalgorithm for identity testing for the ferromagnetic (attractive) Ising model.\nIn contrast, for the antiferromagnetic (repulsive) Ising model, Bez\\'akov\\'a et\nal. (2019) proved that unless $RP=NP$ there is no identity testing algorithm\nwhen $\\beta d=\\omega(\\log{n})$, where $d$ is the maximum degree of the visible\ngraph and $\\beta$ is the largest edge weight in absolute value.\n We prove analogous hardness results for RBMs (i.e., mixed Ising models on\nbipartite graphs), even when there are no latent variables or an external\nfield. Specifically, we show that if $RP \\neq NP$, then when $\\beta\nd=\\omega(\\log{n})$ there is no polynomial-time algorithm for identity testing\nfor RBMs; when $\\beta d =O(\\log{n})$ there is an efficient identity testing\nalgorithm that utilizes the structure learning algorithm of Klivans and Meka\n(2017). In addition, we prove similar lower bounds for purely ferromagnetic\nRBMs with inconsistent external fields, and for the ferromagnetic Potts model.\nPrevious hardness results for identity testing of Bez\\'akov\\'a et al. (2019)\nutilized the hardness of finding the maximum cuts, which corresponds to the\nground states of the antiferromagnetic Ising model. Since RBMs are on bipartite\ngraphs such an approach is not feasible. We instead introduce a general\nmethodology to reduce from the corresponding approximate counting problem and\nutilize the phase transition that is exhibited by RBMs and the mean-field Potts\nmodel.\n