  The ability to leverage large-scale hardware parallelism has been one of the
key enablers of the accelerated recent progress in machine learning.
Consequently, there has been considerable effort invested into developing
efficient parallel variants of classic machine learning algorithms. However,
despite the wealth of knowledge on parallelization, some classic machine
learning algorithms often prove hard to parallelize efficiently while
maintaining convergence.
  In this paper, we focus on efficient parallel algorithms for the key machine
learning task of inference on graphical models, in particular on the
fundamental belief propagation algorithm. We address the challenge of
efficiently parallelizing this classic paradigm by showing how to leverage
scalable relaxed schedulers in this context. We present an extensive empirical
study, showing that our approach outperforms previous parallel belief
propagation implementations both in terms of scalability and in terms of
wall-clock convergence time, on a range of practical applications.
