Google Research

Asynchronous Parallel Coordinate Minimization for MAP Inference

Advances in Neural Information Processing Systems (NIPS) 30 (2017)


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 them asynchronously in parallel. In this case message-passing inference is performed by multiple processing units simultaneously, all reading and writing to shared memory, without coordination. 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.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work