Continuous Relaxation of MAP Inference: A Nonconvex Perspective

D. Khuê Lê-Huu, Nikos Paragios; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 5533-5541

Abstract


In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this relaxation is tight, and a discrete stationary point of it can be easily reached by a simple block coordinate descent algorithm. In addition, we study the resolution of this relaxation using popular gradient methods, and further propose a more effective solution using a multilinear decomposition framework based on the alternating direction method of multipliers (ADMM). Experiments on many real-world problems demonstrate that the proposed ADMM significantly outperforms other nonconvex relaxation based methods, and compares favorably with state of the art MRF optimization algorithms in different settings.

Related Material


[pdf] [Supp] [arXiv]
[bibtex]
@InProceedings{Lê-Huu_2018_CVPR,
author = {Khuê Lê-Huu, D. and Paragios, Nikos},
title = {Continuous Relaxation of MAP Inference: A Nonconvex Perspective},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2018}
}