  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.
