Globally Convergent Parallel MAP LP Relaxation Solver using the Frank-Wolfe Algorithm


Alexander Schwing, Tamir Hazan, Marc Pollefeys, Raquel Urtasun ;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):487-495, 2014.


While MAP inference is typically intractable for many real-world applications, linear programming relaxations have been proven very effective. Dual block-coordinate descent methods are among the most efficient solvers, however, they are prone to get stuck in sub-optimal points. Although subgradient approaches achieve global convergence, they are typically slower in practice. To improve convergence speed, algorithms which compute the steepest ε-descent direction by solving a quadratic program have been proposed. In this paper we suggest to decouple the quadratic program based on the Frank-Wolfe approach. This allows us to obtain an efficient and easy to parallelize algorithm while retaining the global convergence properties. Our method proves superior when compared to existing algorithms on a set of spin-glass models and protein design tasks.

Related Material