Convergent message passing algorithms - a unifying view

Talya Meltzer, Amir Globerson, Yair Weiss
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:401-409, 2009.

Abstract

Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright’s non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-meltzer09a, title = {Convergent message passing algorithms - a unifying view}, author = {Meltzer, Talya and Globerson, Amir and Weiss, Yair}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {401--409}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/meltzer09a/meltzer09a.pdf}, url = {https://proceedings.mlr.press/r7/meltzer09a.html}, abstract = {Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright’s non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Convergent message passing algorithms - a unifying view %A Talya Meltzer %A Amir Globerson %A Yair Weiss %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-meltzer09a %I PMLR %P 401--409 %U https://proceedings.mlr.press/r7/meltzer09a.html %V R7 %X Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright’s non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains. %Z Reissued by PMLR on 04 October 2026.
APA
Meltzer, T., Globerson, A. & Weiss, Y.. (2009). Convergent message passing algorithms - a unifying view. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:401-409 Available from https://proceedings.mlr.press/r7/meltzer09a.html. Reissued by PMLR on 04 October 2026.

Related Material