Barrier Frank-Wolfe for Marginal Inference

Rahul G. Krishnan 1, * Simon Lacoste-Julien 2, 3, 4 David Sontag 1
* Auteur correspondant
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : 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.
Type de document :
Communication dans un congrès
NIPS 2015 - Advances in Neural Information Processing Systems 28, Dec 2015, Montreal, Canada. 〈〉
Liste complète des métadonnées
Contributeur : Simon Lacoste-Julien <>
Soumis le : lundi 28 décembre 2015 - 04:40:56
Dernière modification le : mardi 29 janvier 2019 - 15:05:44

Lien texte intégral


  • HAL Id : hal-01248674, version 1
  • ARXIV : 1511.02124



Rahul G. Krishnan, Simon Lacoste-Julien, David Sontag. Barrier Frank-Wolfe for Marginal Inference. NIPS 2015 - Advances in Neural Information Processing Systems 28, Dec 2015, Montreal, Canada. 〈〉. 〈hal-01248674〉



Consultations de la notice