Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models

Nicholas Ruozzi, Sekhar Tatikonda
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:499-499, 2010.

Abstract

The max-product algorithm, which attempts to compute the most probable assignment (MAP) of a given probability distribution, has recently found applications in quadratic minimization and combinatorial optimiza- tion. Unfortunately, the max-product algo- rithm is not guaranteed to converge and, even if it does, is not guaranteed to produce the MAP assignment. In this work, we provide a simple derivation of a new family of message passing algorithms by “splitting” the factors of our graphical model. We prove that, for any objective function that attains its maxi- mum value over its domain, this new family of message passing algorithms always contains a message passing scheme that guarantees cor- rectness upon convergence to a unique es- timate. Finally, we adopt an asynchronous message passing schedule and prove that, un- der mild assumptions, such a schedule guar- antees the convergence of our algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-ruozzi10a, title = {Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models}, author = {Ruozzi, Nicholas and Tatikonda, Sekhar}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {499--499}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/ruozzi10a/ruozzi10a.pdf}, url = {https://proceedings.mlr.press/r8/ruozzi10a.html}, abstract = {The max-product algorithm, which attempts to compute the most probable assignment (MAP) of a given probability distribution, has recently found applications in quadratic minimization and combinatorial optimiza- tion. Unfortunately, the max-product algo- rithm is not guaranteed to converge and, even if it does, is not guaranteed to produce the MAP assignment. In this work, we provide a simple derivation of a new family of message passing algorithms by “splitting” the factors of our graphical model. We prove that, for any objective function that attains its maxi- mum value over its domain, this new family of message passing algorithms always contains a message passing scheme that guarantees cor- rectness upon convergence to a unique es- timate. Finally, we adopt an asynchronous message passing schedule and prove that, un- der mild assumptions, such a schedule guar- antees the convergence of our algorithm.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models %A Nicholas Ruozzi %A Sekhar Tatikonda %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-ruozzi10a %I PMLR %P 499--499 %U https://proceedings.mlr.press/r8/ruozzi10a.html %V R8 %X The max-product algorithm, which attempts to compute the most probable assignment (MAP) of a given probability distribution, has recently found applications in quadratic minimization and combinatorial optimiza- tion. Unfortunately, the max-product algo- rithm is not guaranteed to converge and, even if it does, is not guaranteed to produce the MAP assignment. In this work, we provide a simple derivation of a new family of message passing algorithms by “splitting” the factors of our graphical model. We prove that, for any objective function that attains its maxi- mum value over its domain, this new family of message passing algorithms always contains a message passing scheme that guarantees cor- rectness upon convergence to a unique es- timate. Finally, we adopt an asynchronous message passing schedule and prove that, un- der mild assumptions, such a schedule guar- antees the convergence of our algorithm. %Z Reissued by PMLR on 04 October 2026.
APA
Ruozzi, N. & Tatikonda, S.. (2010). Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:499-499 Available from https://proceedings.mlr.press/r8/ruozzi10a.html. Reissued by PMLR on 04 October 2026.

Related Material