On the convergence of the convex relaxation method and distributed optimization of Bethe free energy.
Ming Su · 2010
Exact probabilistic inference in graphical models can be computationally intractable. One often resorts to ap-proximate inference methods. We give a convergence analysis of a convex relaxation method for approxi-mate inference. This method is a natural generalization of Unified Propagation and Scaling (UPS) algorithm. We derive sufficient conditions for the method’s con-vergence from a mathematical programming point of view. We also propose a distributed implementation of the method and show how the synchronization cost can be minimized at the algorithmic level. 1