An incremental subgradient algorithm for MAP estimation in graphical models

Jeremy Jancsary, Gerald Matz, and Harald Trost
NIPS 2010 Workshop on Optimization for Machine Learning
December 2010, Whistler, Canada

We present an incremental subgradient algorithm for approximate computation of maximum-a-posteriori (MAP) states in cyclic graphical models. Its most striking property is its immense simplicity: each iteration requires only the solution of a sequence of trivial optimization problems. The algorithm can be equally understood as a degenerated dual decomposition scheme or as minimization of a degenerated tree-reweighted upper bound and assumes a form that is reminiscent of message-passing. Despite (or due to) its conceptual simplicity, it is equipped with important theoretical guarantees and exposes strong empirical performance.

Article

 

 

 

 

Please cite as:

@INPROCEEDINGS{Jancsary2010b,
title = {An incremental subgradient algorithm for MAP estimation in graphical models},
author = {Jeremy Jancsary and Gerald Matz and Harald Trost},
booktitle = {NIPS 2010 Workshop on Optimization for Machine Learning},
year = {2010}
}