Abstract

In this paper we investigate the computational complexity of learning the graph structure underlying a discrete undirected graphical model from i.i.d. samples. Our first result is an unconditional computational lower bound of for learning general graphical models on p nodes of maximum degree d, for the class of so-called statistical algorithms recently introduced by Feldman et al. [1]. The construction is related to the notoriously difficult learning parities with noise problem in computational learning theory. Our lower bound suggests that the runtime required by Bresler, Mossel, and Sly’s [2] exhaustive-search algorithm cannot be significantly improved without restricting the class of models. Aside from structural assumptions on the graph such as it being a tree, hypertree, tree-like, etc., many recent papers on structure learning assume that the model has the correlation decay property. Indeed, focusing on ferromagnetic Ising models, Bento and Montanari [3] showed that all known low-complexity algorithms fail to learn simple graphs when the interaction strength exceeds a number related to the correlation decay threshold. Our second set of results gives a class of repelling (antiferromagnetic) models that have the opposite behavior: very strong interaction allows efficient learning in time We provide an algorithm whose performance interpolates between depending on the strength of the repulsion.