Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization
Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy
Abstract
We consider the maximum-a-posteriori inference problem in discrete graphical models and study solvers based on the dual block-coordinate ascent rule. We map all existing solvers in a single framework, allowing for a better understanding of their design principles. We theoretically show that some block-optimizing updates are sub-optimal and how to strictly improve them. On a wide range of problem instances of varying graph connectivity, we study the performance of existingsolvers as well as new variants that can be obtained within the framework. As a result of this exploration we build a new state-of-the art solver, performing uniformly better on the whole range of test instances.
BibTeX
@InProceedings{pmlr-v108-tourani20a,
title = {Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization},
author = {Tourani, Siddharth and Shekhovtsov, Alexander and Rother, Carsten and Savchynskyy, Bogdan},
booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics},
pages = {2775--2785},
year = {2020},
editor = {Chiappa, Silvia and Calandra, Roberto},
volume = {108},
series = {Proceedings of Machine Learning Research},
month = {26--28 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v108/tourani20a/tourani20a.pdf},
url = {https://proceedings.mlr.press/v108/tourani20a.html},
abstract = {We consider the maximum-a-posteriori inference problem in discrete graphical models and study solvers based on the dual block-coordinate ascent rule. We map all existing solvers in a single framework, allowing for a better understanding of their design principles. We theoretically show that some block-optimizing updates are sub-optimal and how to strictly improve them. On a wide range of problem instances of varying graph connectivity, we study the performance of existingsolvers as well as new variants that can be obtained within the framework. As a result of this exploration we build a new state-of-the art solver, performing uniformly better on the whole range of test instances.}
}