Carnegie Mellon University
file.pdf (773.89 kB)
Download file

An Augmented Lagrangian Approach to Constrained MAP Inference

Download (773.89 kB)
journal contribution
posted on 2011-06-01, 00:00 authored by Andre F.T. Martins, Mario A. T. Figeuiredo, Pedro M.Q. Aguiar, Noah A. Smith, Eric P Xing

We propose a new fast algorithm for approximate MAP inference on factor graphs, which combines augmented Lagrangian optimization with the dual decomposition method. Each slave subproblem is given a quadratic penalty, which pushes toward faster consensus than in previous subgradient approaches. Our algorithm is provably convergent, parallelizable, and suitable for fine decompositions of the graph. We show how it can efficiently handle problems with (possibly global) structural constraints via simple sort operations. Experiments on synthetic and real-world data show that our approach compares favorably with the state-of-the-art.


Publisher Statement

Copyright 2011 by the author(s)/owner(s)



Usage metrics