Decomposition Bounds for Marginal MAP
  Marginal MAP inference involves making MAP predictions in systems defined
with latent variables or missing information. It is significantly more
difficult than pure marginalization and MAP tasks, for which a large class of
efficient and convergent variational algorithms, such as dual decomposition,
exist. In this work, we generalize dual decomposition to a generic power sum
inference task, which includes marginal MAP, along with pure marginalization
and MAP, as special cases. Our method is based on a block coordinate descent
algorithm on a new convex decomposition bound, that is guaranteed to converge
monotonically, and can be parallelized efficiently. We demonstrate our approach
on marginal MAP queries defined on real-world problems from the UAI approximate
inference challenge, showing that our framework is faster and more reliable
than previous methods.
