# Continuous Relaxation of MAP Inference: A Nonconvex Perspective

arXiv: https://arxiv.org/abs/1802.07796 · HTML: https://mlsanity.com/paper/1802.07796/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2018.

## Built on by (most cited first, 1 of 1)

- [Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond](https://mlsanity.com/paper/2110.14759/) (2021)

## Abstract (arXiv)

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.