Hardness of parameter estimation in graphical 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 | Our main result shows that parameter estimation is in general intractable: no algorithm can learn the canonical parameters of a generic pair-wise binary graphical model from the mean parameters in time bounded by a polynomial in the number of variables (unless RP = NP). Indeed, such a result has been believed to be true (see [1]) but no proof was known. Our proof gives a polynomial time reduction from approximating the partition function of the hard-core model, known to be hard, to learning approximate parameters. |
| Researcher Affiliation | Academia | Laboratory for Information and Decision Systems Department of EECS1 and Sloan School of Management2 Massachusetts Institute of Technology {gbresler,gamarnik,devavrat}@mit.edu |
| Pseudocode | No | The paper describes methods in prose and mathematical equations but does not contain any structured pseudocode or algorithm blocks that are clearly labeled or formatted like code. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described, nor does it explicitly state that code is released or available. |
| Open Datasets | No | This is a theoretical research paper that focuses on computational hardness proofs and does not involve empirical studies with datasets. Therefore, it does not mention or provide access information for any dataset used for training. |
| Dataset Splits | No | As a theoretical paper, it does not conduct empirical experiments with data. Consequently, there are no discussions or details regarding training, validation, or test dataset splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe any computational experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper focuses on theoretical proofs and does not describe empirical experiments or specific software implementations that would require listing software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical research paper proving computational hardness, and as such, it does not involve practical experiments with specific setup details like hyperparameters or training configurations. |