Bethe-ADMM for Tree Decomposition based Parallel MAP Inference

Understand

We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models.

• We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM).
• However, unlike the standard ADMM, we use an inexact ADMM augmented with a Bethe-divergence based proximal function, which makes each subproblem in ADMM easy to solve in parallel using the sum-product algorithm.
• We rigorously prove global convergence of Bethe-ADMM.