Structure Learning of Antiferromagnetic Ising Models
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 Ω(p[superscript d/2]) for learning general graphical models on p nodes of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Neural Information Processing Systems Foundation
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101040 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-1303-582X |
| _version_ | 1826216259116597248 |
|---|---|
| author | Bresler, Guy Gamarnik, David Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bresler, Guy Gamarnik, David Shah, Devavrat |
| author_sort | Bresler, Guy |
| collection | MIT |
| description | 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 Ω(p[superscript d/2]) for learning general graphical models on p nodes of maximum degree d, for the class of statistical algorithms recently introduced by Feldman et al. The construction is related to the notoriously difficult learning parities with noise problem in computational learning theory. Our lower bound shows that the [~ over O](p[superscript d+2]) runtime required by Bresler, Mossel, and Sly's 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., most recent papers on structure learning assume that the model has the correlation decay property. Indeed, focusing on ferromagnetic Ising models, Bento and Montanari 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 \emph{opposite} behavior: very strong repelling allows efficient learning in time [~ over O](p[superscript 2]). We provide an algorithm whose performance interpolates between [~ over O](p[superscript 2]) and [~ over O](p[superscript d+2]) depending on the strength of the repulsion. |
| first_indexed | 2024-09-23T16:44:31Z |
| format | Article |
| id | mit-1721.1/101040 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:44:31Z |
| publishDate | 2016 |
| publisher | Neural Information Processing Systems Foundation |
| record_format | dspace |
| spelling | mit-1721.1/1010402022-09-29T21:12:47Z Structure Learning of Antiferromagnetic Ising Models Bresler, Guy Gamarnik, David Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Sloan School of Management Bresler, Guy Gamarnik, David Shah, Devavrat 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 Ω(p[superscript d/2]) for learning general graphical models on p nodes of maximum degree d, for the class of statistical algorithms recently introduced by Feldman et al. The construction is related to the notoriously difficult learning parities with noise problem in computational learning theory. Our lower bound shows that the [~ over O](p[superscript d+2]) runtime required by Bresler, Mossel, and Sly's 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., most recent papers on structure learning assume that the model has the correlation decay property. Indeed, focusing on ferromagnetic Ising models, Bento and Montanari 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 \emph{opposite} behavior: very strong repelling allows efficient learning in time [~ over O](p[superscript 2]). We provide an algorithm whose performance interpolates between [~ over O](p[superscript 2]) and [~ over O](p[superscript d+2]) depending on the strength of the repulsion. National Science Foundation (U.S.) (Grant CMMI-1335155) National Science Foundation (U.S.) (Grant CNS-1161964) United States. Army Research Office. Multidisciplinary University Research Initiative (Award W911NF-11-1-0036) 2016-02-01T18:32:57Z 2016-02-01T18:32:57Z 2014 Article http://purl.org/eprint/type/ConferencePaper 1049-5258 http://hdl.handle.net/1721.1/101040 Bresler, Guy, David Gamarnik, and Devavrat Shah. "Structure Learning of Antiferromagnetic Ising Models." Advances in Neural Information Processing Systems 27 (NIPS 2014). https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-1303-582X en_US https://papers.nips.cc/paper/5319-structure-learning-of-antiferromagnetic-ising-models Advances in Neural Information Processing Systems (NIPS) Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Neural Information Processing Systems Foundation MIT web domain |
| spellingShingle | Bresler, Guy Gamarnik, David Shah, Devavrat Structure Learning of Antiferromagnetic Ising Models |
| title | Structure Learning of Antiferromagnetic Ising Models |
| title_full | Structure Learning of Antiferromagnetic Ising Models |
| title_fullStr | Structure Learning of Antiferromagnetic Ising Models |
| title_full_unstemmed | Structure Learning of Antiferromagnetic Ising Models |
| title_short | Structure Learning of Antiferromagnetic Ising Models |
| title_sort | structure learning of antiferromagnetic ising models |
| url | http://hdl.handle.net/1721.1/101040 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-1303-582X |
| work_keys_str_mv | AT breslerguy structurelearningofantiferromagneticisingmodels AT gamarnikdavid structurelearningofantiferromagneticisingmodels AT shahdevavrat structurelearningofantiferromagneticisingmodels |