  Loopy and generalized belief propagation are popular algorithms for
approximate inference in Markov random fields and Bayesian networks. Fixed
points of these algorithms correspond to extrema of the Bethe and Kikuchi free
energy. However, belief propagation does not always converge, which explains
the need for approaches that explicitly minimize the Kikuchi/Bethe free energy,
such as CCCP and UPS. Here we describe a class of algorithms that solves this
typically nonconvex constrained minimization of the Kikuchi free energy through
a sequence of convex constrained minimizations of upper bounds on the Kikuchi
free energy. Intuitively one would expect tighter bounds to lead to faster
algorithms, which is indeed convincingly demonstrated in our simulations.
Several ideas are applied to obtain tight convex bounds that yield dramatic
speed-ups over CCCP.
