# Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 48 references that are in the map.
- First posted on arXiv 24 Oct 2024.

## Builds on (most cited first, 6 of 6)

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Frequentist Consistency of Variational Bayes](https://mlsanity.com/paper/1705.03439/) (2017)
- [On Statistical Optimality of Variational Bayes](https://mlsanity.com/paper/1712.08983/) (2017)
- [A practical tutorial on Variational Bayes](https://mlsanity.com/paper/2103.01327/) (2021)
- [Dense Distributions from Sparse Samples: Improved Gibbs Sampling Parameter Estimators for LDA](https://mlsanity.com/paper/1505.02065/) (2015)

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

- [Logic, Optimization, and Artificial Intelligence](https://mlsanity.com/paper/2607.15532/) (2026)

## Abstract (arXiv)

Many Bayesian statistical inference problems come down to computing a maximum a-posteriori (MAP) assignment of latent variables. Yet, standard methods for estimating the MAP assignment do not have a finite time guarantee that the algorithm has converged to a fixed point. Previous research has found that MAP inference can be represented in dual form as a linear programming problem with a non-polynomial number of constraints. A Lagrangian relaxation of the dual yields a statistical inference algorithm as a linear programming problem. However, the decision as to which constraints to remove in the relaxation is often heuristic. We present a method for maximum a-posteriori inference in general Bayesian factor models that sequentially adds constraints to the fully relaxed dual problem using Benders' decomposition. Our method enables the incorporation of expressive integer and logical constraints in clustering problems such as must-link, cannot-link, and a minimum number of whole samples allocated to each cluster. Using this approach, we derive MAP estimation algorithms for the Bayesian Gaussian mixture model and latent Dirichlet allocation. Empirical results show that our method produces a higher optimal posterior value compared to Gibbs sampling and variational Bayes methods for standard data sets and provides certificate of convergence.