# Bethe-ADMM for Tree Decomposition based Parallel MAP Inference

arXiv: https://arxiv.org/abs/1309.6829 · HTML: https://mlsanity.com/paper/1309.6829/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2013.

## Built on by (most cited first, 1 of 1)

- [Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing](https://mlsanity.com/paper/2207.02087/) (2022)

## Abstract (arXiv)

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.