Dual Decomposition from the Perspective of Relax, Compensate and then
  Recover
  Relax, Compensate and then Recover (RCR) is a paradigm for approximate
inference in probabilistic graphical models that has previously provided
theoretical and practical insights on iterative belief propagation and some of
its generalizations. In this paper, we characterize the technique of dual
decomposition in the terms of RCR, viewing it as a specific way to compensate
for relaxed equivalence constraints. Among other insights gathered from this
perspective, we propose novel heuristics for recovering relaxed equivalence
constraints with the goal of incrementally tightening dual decomposition
approximations, all the way to reaching exact solutions. We also show
empirically that recovering equivalence constraints can sometimes tighten the
corresponding approximation (and obtaining exact results), without increasing
much the complexity of inference.
