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.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-schwing14, title = {Globally Convergent Parallel MAP LP Relaxation Solver using the Frank-Wolfe Algorithm}, author = {Schwing, Alexander and Hazan, Tamir and Pollefeys, Marc and Urtasun, Raquel}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {487--495}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/schwing14.pdf}, url = {https://proceedings.mlr.press/v32/schwing14.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Globally Convergent Parallel MAP LP Relaxation Solver using the Frank-Wolfe Algorithm %A Alexander Schwing %A Tamir Hazan %A Marc Pollefeys %A Raquel Urtasun %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-schwing14 %I PMLR %P 487--495 %U https://proceedings.mlr.press/v32/schwing14.html %V 32 %N 2 %X 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.
RIS
TY - CPAPER TI - Globally Convergent Parallel MAP LP Relaxation Solver using the Frank-Wolfe Algorithm AU - Alexander Schwing AU - Tamir Hazan AU - Marc Pollefeys AU - Raquel Urtasun BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-schwing14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 487 EP - 495 L1 - http://proceedings.mlr.press/v32/schwing14.pdf UR - https://proceedings.mlr.press/v32/schwing14.html AB - 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. ER -
APA
Schwing, A., Hazan, T., Pollefeys, M. & Urtasun, R.. (2014). Globally Convergent Parallel MAP LP Relaxation Solver using the Frank-Wolfe Algorithm. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):487-495 Available from https://proceedings.mlr.press/v32/schwing14.html.

Related Material