Barrier Frank-Wolfe for Marginal Inference

By Rahul G. Krishnan, Simon Lacoste-Julien, David A. Sontag. 2015

40 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Molecular Biology, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Optimization & Training

Citations in the corpus

Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “Examples for this scenario include: when a parallel implementation is used for the entropy computation; or when the marginalization oracle uses an iterative approximate inference algorithms such as TRW BP whereas an approximation of the entropy is direct from the marginals (Krishnan et al., 2015).”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, background): “Optimization over the marginal polytope appears for example in structured SVM learning [21] and variational inference [18].”
SparseMAP: Differentiable Sparse Structured Inference (2018, background): “One family of such solvers is based on the conditional gradient (CG) algorithm (Frank & Wolfe, 1956; Lacoste-Julien & Jaggi, 2015), considered in prior work for solving approximations of the marginal inference problem (Belanger et al., 2013; Krishnan et al., 2015).”
Boosting Variational Inference: an Optimization Perspective (2017, background): “For example, [13] consider a variational objective for approximate marginal inference over the marginal polytope.”