Marginal inference in MRFs using Frank-Wolfe

We introduce an algorithm, based on the Frank-Wolfe technique (conditional gra-dient), for performing marginal inference in undirected graphical models by re-peatedly performing MAP inference. It minimizes standard Bethe-style convex variational objectives for inference, leverages known MAP algorithms as black boxes, and offers a principled means to construct sparse approximate marginals for high-arity graphs. We also offer intuition and empirical evidence for a rela-tionship between the entropy of the true marginal distribution of the model and the convergence rate of the algorithm. We advocate for further applications of Frank-Wolfe to marginal inference in Gibbs distributions with combinatorial en-ergy functions.