Designing and implementing efficient, provably correct parallel machine
learning (ML) algorithms is challenging. Existing high-level parallel
abstractions like MapReduce are insufficiently expressive while low-level tools
like MPI and Pthreads leave ML experts repeatedly solving the same design
challenges. By targeting common patterns in ML, we developed GraphLab, which
improves upon abstractions like MapReduce by compactly expressing asynchronous
iterative algorithms with sparse computational dependencies while ensuring data
consistency and achieving a high degree of parallel performance.

We propose a new distributed algorithm for computing a truncated Newton
method, where the main diagonal of the Hessian is computed using belief
propagation. As a case study for this approach, we examine the sensor selection
problem, a Boolean convex optimization problem. We form two distributed
algorithms. The first algorithm is a distributed version of the interior point
method by Joshi and Boyd, and the second algorithm is an order of magnitude
faster approximation. As an example application we discuss distributed anomaly
detection in networks.