Information Theoretic Properties of Markov Random Fields, and their
  Algorithmic Applications
  Markov random fields area popular model for high-dimensional probability
distributions. Over the years, many mathematical, statistical and algorithmic
problems on them have been studied. Until recently, the only known algorithms
for provably learning them relied on exhaustive search, correlation decay or
various incoherence assumptions. Bresler gave an algorithm for learning general
Ising models on bounded degree graphs. His approach was based on a structural
result about mutual information in Ising models.
  Here we take a more conceptual approach to proving lower bounds on the mutual
information through setting up an appropriate zero-sum game. Our proof
generalizes well beyond Ising models, to arbitrary Markov random fields with
higher order interactions. As an application, we obtain algorithms for learning
Markov random fields on bounded degree graphs on $n$ nodes with $r$-order
interactions in $n^r$ time and $\log n$ sample complexity. The sample
complexity is information theoretically optimal up to the dependence on the
maximum degree. The running time is nearly optimal under standard conjectures
about the hardness of learning parity with noise.
