Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization
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.
Cite
Text
Tourani et al. "Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization." Artificial Intelligence and Statistics, 2020.Markdown
[Tourani et al. "Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization." Artificial Intelligence and Statistics, 2020.](https://mlanthology.org/aistats/2020/tourani2020aistats-taxonomy/)BibTeX
@inproceedings{tourani2020aistats-taxonomy,
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 = {Artificial Intelligence and Statistics},
year = {2020},
pages = {2775-2785},
volume = {108},
url = {https://mlanthology.org/aistats/2020/tourani2020aistats-taxonomy/}
}