MAP inference via Block-Coordinate Frank-Wolfe Algorithm
This work addresses optimization efficiency for structured prediction tasks, offering incremental improvements in computational methods for specific domains.
The paper tackles MAP inference in structured energy minimization by introducing a proximal bundle method using a block-coordinate Frank-Wolfe algorithm, showing it outperforms state-of-the-art Lagrangean decomposition methods on challenging problems like Markov Random Fields and graph matching.
We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation 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 decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems.