Skip to yearly menu bar Skip to main content


Poster

Asynchronous Parallel Coordinate Minimization for MAP Inference

Ofer Meshi · Alex Schwing

Pacific Ballroom #178

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


Abstract:

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.

Live content is unavailable. Log in and register to view live content