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 |