Accelerated dual decomposition for MAP inference

Approximate MAP inference in graphical models is an important and challenging prob-lem for many domains including computer vi-sion, computational biology and natural lan-guage understanding. Current state-of-the-art approaches employ convex relaxations of these problems as surrogate objectives, but only provide weak running time guarantees. In this paper, we develop an approximate in-ference algorithm that is both efficient and has strong theoretical guarantees. Specifi-cally, our algorithm is guaranteed to converge to an -accurate solution of the convex relax-ation in