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

Estimating the most likely configuration (MAP) is one of the fundamental tasks in probabilis-tic models. While MAP inference is typi-cally intractable for many real-world applica-tions, 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 pro-gram based on the Frank-Wolfe approach. This allows us to obtain an efficient and easy to par-allelize algorithm while retaining the global con-vergence properties. Our method proves superior when compared to existing algorithms on a set of spin-glass models and protein design tasks. 1