# Hardness of parameter estimation in graphical models

arXiv: https://arxiv.org/abs/1409.3836 · HTML: https://mlsanity.com/paper/1409.3836/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2014.

## Built on by (most cited first, 5 of 5)

- [Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach](https://mlsanity.com/paper/2208.04405/) (2022)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise](https://mlsanity.com/paper/2102.08554/) (2021)
- [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)

## Abstract (arXiv)

We consider the problem of learning the canonical parameters specifying an undirected graphical model (Markov random field) from the mean parameters. For graphical models representing a minimal exponential family, the canonical parameters are uniquely determined by the mean parameters, so the problem is feasible in principle. The goal of this paper is to investigate the computational feasibility of this statistical task. 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 the monograph by Wainwright and Jordan (2008)) 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. Our reduction entails showing that the marginal polytope boundary has an inherent repulsive property, which validates an optimization procedure over the polytope that does not use any knowledge of its structure (as required by the ellipsoid method and others).