Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay

Belief propagation is a fundamental message-passing algorithm for probabilistic reasoning and inference in graphical models. While it is known to be exact on trees, in most applications belief propagation is run on graphs with cycles. Understanding the behavior of "loopy" belief propagation has been a major challenge for researchers in machine learning and other fields, and positive convergence results for BP are known under strong assumptions which imply the underlying graphical model exhibits decay of correlations. We show, building on previous work of Dembo and Montanari, that under a natural initialization BP converges quickly to the global optimum of the Bethe free energy for Ising models on arbitrary graphs, as long as the Ising model is ferromagnetic (i.e.