Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation

Akshat Kumar, Shlomo Zilberstein
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:485-492, 2011.

Abstract

Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems confirm that our new approach is competitive with max-product and its variations. Compared with CPLEX, we achieve more than an order-of-magnitude speedup in solving optimally the convex QP relaxation.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-kumar11a, title = {Message-Passing Algorithms for Quadratic Programming Formulations of {MAP} Estimation}, author = {Kumar, Akshat and Zilberstein, Shlomo}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {485--492}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/kumar11a/kumar11a.pdf}, url = {https://proceedings.mlr.press/r9/kumar11a.html}, abstract = {Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems confirm that our new approach is competitive with max-product and its variations. Compared with CPLEX, we achieve more than an order-of-magnitude speedup in solving optimally the convex QP relaxation.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation %A Akshat Kumar %A Shlomo Zilberstein %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-kumar11a %I PMLR %P 485--492 %U https://proceedings.mlr.press/r9/kumar11a.html %V R9 %X Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems confirm that our new approach is competitive with max-product and its variations. Compared with CPLEX, we achieve more than an order-of-magnitude speedup in solving optimally the convex QP relaxation. %Z Reissued by PMLR on 04 October 2026.
APA
Kumar, A. & Zilberstein, S.. (2011). Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:485-492 Available from https://proceedings.mlr.press/r9/kumar11a.html. Reissued by PMLR on 04 October 2026.

Related Material