Tightness Results for Local Consistency Relaxations in Continuous MRFs

Abstract

Finding the MAP assignment in graphical mod-els is a challenging task that generally requires approximations. One popular approximation ap-proach is to use linear programming relaxations that enforce local consistency. While these are commonly used for discrete variable models, they are much less understood for models with continuous variables. Here we define local consistency relaxations of MAP for continuous pairwise Markov Random Fields (MRFs), and analyze their properties. We begin by providing a characterization of models for which this relaxation is tight. These turn out to be models that can be reparameterized as a sum of local convex functions. We also provide a simple formulation of this relaxation for Gaus-sian MRFs. Next, we show how the above insights can be used to obtain optimality certificates for loopy belief propagation (LBP) in such models. Specif-ically, we show that the messages of LBP can be used to calculate upper and lower bounds on the MAP value, and that these bounds coincide at convergence, yielding a natural stopping crite-rion which was not previously available. Finally, our results illustrate a close connection between local consistency relaxations of MAP and LBP. They demonstrate that in the continu-ous case, whenever LBP is provably optimal so is the local consistency relaxation. 1