Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models
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
Text
Durante et al. "Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models." International Conference on Machine Learning, 2022.Markdown
[Durante et al. "Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models." International Conference on Machine Learning, 2022.](https://mlanthology.org/icml/2022/durante2022icml-efficient/)BibTeX
@inproceedings{durante2022icml-efficient,
title = {{Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models}},
author = {Durante, Valentin and Katsirelos, George and Schiex, Thomas},
booktitle = {International Conference on Machine Learning},
year = {2022},
pages = {5726-5741},
volume = {162},
url = {https://mlanthology.org/icml/2022/durante2022icml-efficient/}
}