  Message-passing algorithms have emerged as powerful techniques for
approximate inference in graphical models. When these algorithms converge, they
can be shown to find local (or sometimes even global) optima of variational
formulations to the inference problem. But many of the most popular algorithms
are not guaranteed to converge. This has lead to recent interest in convergent
message-passing algorithms. In this paper, we present a unified view of
convergent message-passing algorithms. We present a simple derivation of an
abstract algorithm, tree-consistency bound optimization (TCBO) that is provably
convergent in both its sum and max product forms. We then show that many of the
existing convergent algorithms are instances of our TCBO algorithm, and obtain
novel convergent algorithms "for free" by exchanging maximizations and
summations in existing algorithms. In particular, we show that Wainwright's
non-convergent sum-product algorithm for tree based variational bounds, is
actually convergent with the right update order for the case where trees are
monotonic chains.
