Alternating Directions Dual Decomposition
  We propose AD3, a new algorithm for approximate maximum a posteriori (MAP)
inference on factor graphs based on the alternating directions method of
multipliers. Like dual decomposition algorithms, AD3 uses worker nodes to
iteratively solve local subproblems and a controller node to combine these
local solutions into a global update. The key characteristic of AD3 is that
each local subproblem has a quadratic regularizer, leading to a faster
consensus than subgradient-based dual decomposition, both theoretically and in
practice. We provide closed-form solutions for these AD3 subproblems for binary
pairwise factors and factors imposing first-order logic constraints. For
arbitrary factors (large or combinatorial), we introduce an active set method
which requires only an oracle for computing a local MAP configuration, making
AD3 applicable to a wide range of problems. Experiments on synthetic and
realworld problems show that AD3 compares favorably with the state-of-the-art.
