Dual Decomposition from the Perspective of Relax, Compensate and then Recover
This work provides incremental insights for researchers in probabilistic graphical models by offering a new perspective on dual decomposition and heuristics for improving approximations.
The paper tackles the problem of approximate inference in probabilistic graphical models by characterizing dual decomposition within the Relax, Compensate and then Recover (RCR) paradigm, proposing novel heuristics to tighten approximations and achieve exact solutions, with empirical results showing that recovering constraints can tighten approximations without significantly increasing inference complexity.
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.