Timezone: »

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

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #178
in Posters Tue »

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.

Keywords: Combinatorial Optimization · Convex Optimization · Graphical Models · Structured Prediction · Distributed Inference
[ Paper] 

Author Information

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

More from the Same Authors