MAP inference via Block-Coordinate Frank-Wolfe Algorithm

Paul Swoboda and Vladimir Kolmogorov.

In CVF/IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.


We present a new proximal bundle method for Maximum- A-Posteriori (MAP) inference in structured energy minimiza- tion problems. The method optimizes a Lagrangean relax- ation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decom- position. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label dis- crete tomography and graph matching problems.


arXiv version

implementation of FWMAP:
implementation of MRF, discrete tomography and graph matching solvers built on top of FWMAP (by Paul Swoboda):