Structure learning of antiferromagnetic Ising models
Authors: Guy Bresler, David Gamarnik, Devavrat Shah
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 Ω(pd/2) 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 paper presents theorems, lemmas, and algorithms without empirical evaluation on datasets. |
| Researcher Affiliation | Academia | Guy Bresler1 David Gamarnik2 Devavrat Shah1 Laboratory for Information and Decision Systems Department of EECS1 and Sloan School of Management2 Massachusetts Institute of Technology {gbresler,gamarnik,devavrat}@mit.edu |
| Pseudocode | Yes | Algorithm 1 simple HC( (1), . . . , (n)) 1: FOR each i, j, k: 2: IF (k) j = 1, THEN S = S fi{i, j} 3: OUTPUT ˆE = Sc. The paper also includes 'Algorithm 2 Strong Repelling' and 'Algorithm 3 Weak Repelling'. |
| Open Source Code | No | The paper does not provide any statement or link regarding the release of source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and analyzes algorithms based on samples from graphical models, but it does not use or provide concrete access information for any publicly available or open dataset for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation with specific training, validation, or testing dataset splits. It discusses 'samples' from models in a theoretical context. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and analysis, not empirical implementation. No specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experimental setup, including hyperparameters or specific training configurations. |