Asynchronous parallel coordinate minimization for MAP inference

Research output: Contribution to journalConference article

Abstract

Finding the maximum a-posteriori (MAP) assignment is a central task for structured prediction. Since modern applications give rise to very large structured 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 messagepassing 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.

Original languageEnglish (US)
Pages (from-to)5735-5745
Number of pages11
JournalAdvances in Neural Information Processing Systems
Volume2017-December
StatePublished - Jan 1 2017
Event31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States
Duration: Dec 4 2017Dec 9 2017

Fingerprint

Computer vision
Decomposition
Data storage equipment
Processing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this

Asynchronous parallel coordinate minimization for MAP inference. / Meshi, Ofer; Schwing, Alexander Gerhard.

In: Advances in Neural Information Processing Systems, Vol. 2017-December, 01.01.2017, p. 5735-5745.

Research output: Contribution to journalConference article

@article{0f1ea64599cb4ec18f62aaf61d60de2b,
title = "Asynchronous parallel coordinate minimization for MAP inference",
abstract = "Finding the maximum a-posteriori (MAP) assignment is a central task for structured prediction. Since modern applications give rise to very large structured 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 messagepassing 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 = "Ofer Meshi and Schwing, {Alexander Gerhard}",
year = "2017",
month = "1",
day = "1",
language = "English (US)",
volume = "2017-December",
pages = "5735--5745",
journal = "Advances in Neural Information Processing Systems",
issn = "1049-5258",

}

TY - JOUR

T1 - Asynchronous parallel coordinate minimization for MAP inference

AU - Meshi, Ofer

AU - Schwing, Alexander Gerhard

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Finding the maximum a-posteriori (MAP) assignment is a central task for structured prediction. Since modern applications give rise to very large structured 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 messagepassing 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.

AB - Finding the maximum a-posteriori (MAP) assignment is a central task for structured prediction. Since modern applications give rise to very large structured 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 messagepassing 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.

UR - http://www.scopus.com/inward/record.url?scp=85047013478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85047013478&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85047013478

VL - 2017-December

SP - 5735

EP - 5745

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

SN - 1049-5258

ER -