# Decomposition Bounds for Marginal MAP

arXiv: https://arxiv.org/abs/1511.02619 · HTML: https://mlsanity.com/paper/1511.02619/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2015.

## Built on by (most cited first, 4 of 4)

- [Neural Network Approximators for Marginal MAP in Probabilistic Circuits](https://mlsanity.com/paper/2402.03621/) (2024)
- [Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees](https://mlsanity.com/paper/2309.08883/) (2023)
- [MPE inference using an Incremental Build-Infer-Approximate Paradigm](https://mlsanity.com/paper/2206.01954/) (2022)
- [Solving Satisfiability Modulo Counting Exactly with Probabilistic Circuits](https://mlsanity.com/paper/2503.01009/) (2025)

## Abstract (arXiv)

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.