# Barrier Frank-Wolfe for Marginal Inference

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

## Key facts

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

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

- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Learning with Local Search MCMC Layers](https://mlsanity.com/paper/2505.14240/) (2025)
- [Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps](https://mlsanity.com/paper/2105.13913/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)
- [Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise](https://mlsanity.com/paper/2607.25190/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)

## Abstract (arXiv)

We introduce a globally-convergent algorithm for optimizing the tree-reweighted (TRW) variational objective over the marginal polytope. The algorithm is based on the conditional gradient method (Frank-Wolfe) and moves pseudomarginals within the marginal polytope through repeated maximum a posteriori (MAP) calls. This modular structure enables us to leverage black-box MAP solvers (both exact and approximate) for variational inference, and obtains more accurate results than tree-reweighted algorithms that optimize over the local consistency relaxation. Theoretically, we bound the sub-optimality for the proposed algorithm despite the TRW objective having unbounded gradients at the boundary of the marginal polytope. Empirically, we demonstrate the increased quality of results found by tightening the relaxation over the marginal polytope as well as the spanning tree polytope on synthetic and real-world instances.