Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models

Valentin Durante, George Katsirelos, Thomas Schiex
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:5726-5741, 2022.

Abstract

In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-durante22a, title = {Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models}, author = {Durante, Valentin and Katsirelos, George and Schiex, Thomas}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {5726--5741}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/durante22a/durante22a.pdf}, url = {https://proceedings.mlr.press/v162/durante22a.html}, abstract = {In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches.} }
Endnote
%0 Conference Paper %T Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models %A Valentin Durante %A George Katsirelos %A Thomas Schiex %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-durante22a %I PMLR %P 5726--5741 %U https://proceedings.mlr.press/v162/durante22a.html %V 162 %X In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches.
APA
Durante, V., Katsirelos, G. & Schiex, T.. (2022). Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:5726-5741 Available from https://proceedings.mlr.press/v162/durante22a.html.

Related Material