file.pdf (2.15 MB)

AD3 : Alternating Directions Dual Decomposition for MAP Inference in Graphical Models

Download (2.15 MB)
journal contribution
posted on 01.03.2015 by Andre F.T. Martins, Mario A. T. Figueiredo, Pedro M.Q. Aguiar, Noah A. Smith, Eric P Xing

We present AD3, a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs, based on the alternating directions method of multipliers. Like other dual decomposition algorithms, AD3 has a modular architecture, where local subproblems are solved independently, and their solutions are gathered to compute a global update. The key characteristic of AD3 is that each local subproblem has a quadratic regularizer, leading to faster convergence, both theoretically and in practice. We provide closed-form solutions for these AD3 subproblems for binary pairwise factors and factors imposing first-order logic constraints. For arbitrary factors (large or combinatorial), we introduce an active set method which requires only an oracle for computing a local MAP configuration, making AD3 applicable to a wide range of problems. Experiments on synthetic and real-world problems show that AD3 compares favorably with the state-of-the-art.


Publisher Statement

Copyright 2015 Andre F. T. Martins, Mario A. T. Figueiredo, Pedro M. Q. Aguiar, Noah A. Smith, and Eric P. Xing