Bethe-ADMM for Tree Decomposition based Parallel MAP Inference
This addresses the need for efficient parallel inference in graphical models, though it appears incremental as it builds on existing ADMM and tree decomposition techniques.
The paper tackles the problem of parallel maximum a posteriori (MAP) inference in discrete graphical models by proposing Bethe-ADMM, which combines tree decomposition and an inexact ADMM with a Bethe-divergence proximal function, resulting in a method that scales almost linearly with increasing cores.
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. The proposed algorithm is extensively evaluated on both synthetic and real datasets to illustrate its effectiveness. Further, the parallel Bethe-ADMM is shown to scale almost linearly with increasing number of cores.