Barrier Frank-Wolfe for Marginal Inference
This work addresses the challenge of improving variational inference accuracy in probabilistic graphical models, which is incremental as it builds on existing tree-reweighted methods by tightening relaxations.
The paper tackles the problem of optimizing the tree-reweighted variational objective over the marginal polytope for marginal inference, introducing a globally-convergent algorithm based on the Frank-Wolfe method that leverages MAP solvers and achieves more accurate results than existing tree-reweighted algorithms, with empirical demonstrations on synthetic and real-world instances.
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.