Relaxed Scheduling for Scalable Belief Propagation
This addresses the problem of scaling classic machine learning algorithms for practitioners needing faster inference on large datasets, though it appears incremental as it builds on existing parallelization methods.
The paper tackled the challenge of efficiently parallelizing belief propagation for inference on graphical models, showing that their approach outperforms previous implementations in scalability and wall-clock convergence time across practical applications.
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.