  Maximum a posteriori (MAP) inference in discrete-valued Markov random fields
is a fundamental problem in machine learning that involves identifying the most
likely configuration of random variables given a distribution. Due to the
difficulty of this combinatorial problem, linear programming (LP) relaxations
are commonly used to derive specialized message passing algorithms that are
often interpreted as coordinate descent on the dual LP. To achieve more
desirable computational properties, a number of methods regularize the LP with
an entropy term, leading to a class of smooth message passing algorithms with
convergence guarantees. In this paper, we present randomized methods for
accelerating these algorithms by leveraging techniques that underlie classical
accelerated gradient methods. The proposed algorithms incorporate the familiar
steps of standard smooth message passing algorithms, which can be viewed as
coordinate minimization steps. We show that these accelerated variants achieve
faster rates for finding $\epsilon$-optimal points of the unregularized
problem, and, when the LP is tight, we prove that the proposed algorithms
recover the true MAP solution in fewer iterations than standard message passing
algorithms.
