TY - GEN
T1 - Globally convergent dual MAP LP relaxation solvers using Fenchel-Young margins
AU - Schwing, Alexander G.
AU - Hazan, Tamir
AU - Urtasun, Raquel
AU - Pollefeys, Marc
PY - 2012/12/1
Y1 - 2012/12/1
N2 - While finding the exact solution for the MAP inference problem is intractable for many real-world tasks, MAP LP relaxations have been shown to be very effective in practice. However, the most efficient methods that perform block coordinate descent can get stuck in sub-optimal points as they are not globally convergent In this work we propose to augment these algorithms with an ε-descent approach and present a method to efficiently optimize for a descent direction in the subdifferential using a margin-based formulation of the Fenchel-Young duality theorem. Furthermore, the presented approach provides a methodology to construct a primal optimal solution from its dual optimal counterpart. We demonstrate the efficiency of the presented approach on spin glass models and protein interaction problems and show that our approach outperforms state-of-the-art solvers.
AB - While finding the exact solution for the MAP inference problem is intractable for many real-world tasks, MAP LP relaxations have been shown to be very effective in practice. However, the most efficient methods that perform block coordinate descent can get stuck in sub-optimal points as they are not globally convergent In this work we propose to augment these algorithms with an ε-descent approach and present a method to efficiently optimize for a descent direction in the subdifferential using a margin-based formulation of the Fenchel-Young duality theorem. Furthermore, the presented approach provides a methodology to construct a primal optimal solution from its dual optimal counterpart. We demonstrate the efficiency of the presented approach on spin glass models and protein interaction problems and show that our approach outperforms state-of-the-art solvers.
UR - http://www.scopus.com/inward/record.url?scp=84877748576&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84877748576&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84877748576
SN - 9781627480031
T3 - Advances in Neural Information Processing Systems
SP - 2384
EP - 2392
BT - Advances in Neural Information Processing Systems 25
T2 - 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Y2 - 3 December 2012 through 6 December 2012
ER -