Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions
This work addresses computational bottlenecks in MAP-MRF inference for researchers in optimization and machine learning, representing an incremental improvement.
The paper tackles the problem of solving LP relaxations for MAP-MRF inference by proposing an efficient implementation using in-face Frank-Wolfe directions, resulting in a state-of-the-art LP solver for certain problem classes.
We consider the problem of solving LP relaxations of MAP-MRF inference problems, and in particular the method proposed recently in (Swoboda, Kolmogorov 2019; Kolmogorov, Pock 2021). As a key computational subroutine, it uses a variant of the Frank-Wolfe (FW) method to minimize a smooth convex function over a combinatorial polytope. We propose an efficient implementation of this subproutine based on in-face Frank-Wolfe directions, introduced in (Freund et al. 2017) in a different context. More generally, we define an abstract data structure for a combinatorial subproblem that enables in-face FW directions, and describe its specialization for tree-structured MAP-MRF inference subproblems. Experimental results indicate that the resulting method is the current state-of-art LP solver for some classes of problems. Our code is available at https://pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html.