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.

本文介绍了一种基于条件梯度法和最大后验概率调用的全局收敛算法，用于优化边际多面体上的树重新加权(TRW)变分目标，此算法模块化结构使我们能够利用黑盒MAP求解器(精确和近似)进行变分推理，并获得比优化本地一致性放宽的tree重新加权算法更准确的结果，从理论上解释了该算法的次优性，并在合成和实际应用实例中展示了收缩边际多面体和生成树多面体可以提高结果质量。

边缘推断的障碍型 Frank-Wolfe