Poster
Asynchronous Parallel Coordinate Minimization for MAP Inference
Ofer Meshi · Alexander Schwing

Tue Dec 5th 06:30 -- 10:30 PM @ Pacific Ballroom #178 #None

Finding the maximum a-posteriori (MAP) assignment is a central task in graphical models. Since modern applications give rise to very large problem instances, there is increasing need for efficient solvers. In this work we propose to improve the efficiency of coordinate-minimization-based dual-decomposition solvers by running their updates asynchronously in parallel. In this case message-passing inference is performed by multiple processing units simultaneously without coordination, all reading and writing to shared memory. We analyze the convergence properties of the resulting algorithms and identify settings where speedup gains can be expected. Our numerical evaluations show that this approach indeed achieves significant speedups in common computer vision tasks.

Author Information

Ofer Meshi (Google)
Alex Schwing (University of Illinois at Urbana-Champaign)

More from the Same Authors