Relaxed Scheduling for Scalable Belief Propagation

Abstract

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.

References in corpus (8)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• GraphLab: A New Framework for Parallel Machine Learning
• Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
• Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
• Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes
• Improved Dynamic Schedules for Belief Propagation
• Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms
• Relaxing Concurrent Data-structure Semantics for Increasing Performance: A Multi-structure 2D Design Framework