Timezone: »

 
Poster
Globally Convergent Dual MAP LP Relaxation Solvers using Fenchel-Young Margins
Alex Schwing · Tamir Hazan · Marc Pollefeys · Raquel Urtasun

Tue Dec 04 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
in Poster Session »
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 $\epsilon$-descent approach and present a method to efficiently optimize for a descent direction in the subdifferential using a margin-based extension 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 interactions problems and show that our approach outperforms state-of-the-art solvers.
[ PDF] 

Author Information

Alex Schwing (University of Illinois at Urbana-Champaign)
Tamir Hazan (Technion)
Marc Pollefeys (ETH Zurich)
Raquel Urtasun (University of Toronto)

More from the Same Authors