Bethe-ADMM for Tree Decomposition based Parallel MAP Inference

Qiang Fu, Huahua Wang, Arindam Banerjee
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:105-114, 2013.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-fu13a, title = {{B}ethe-{ADMM} for Tree Decomposition based Parallel {MAP} Inference}, author = {Fu, Qiang and Wang, Huahua and Banerjee, Arindam}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {105--114}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/fu13a/fu13a.pdf}, url = {https://proceedings.mlr.press/r11/fu13a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bethe-ADMM for Tree Decomposition based Parallel MAP Inference %A Qiang Fu %A Huahua Wang %A Arindam Banerjee %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-fu13a %I PMLR %P 105--114 %U https://proceedings.mlr.press/r11/fu13a.html %V R11 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Fu, Q., Wang, H. & Banerjee, A.. (2013). Bethe-ADMM for Tree Decomposition based Parallel MAP Inference. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:105-114 Available from https://proceedings.mlr.press/r11/fu13a.html. Reissued by PMLR on 04 October 2026.

Related Material