Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization

Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:2775-2785, 2020.

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 this Paper

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.} }
Endnote
%0 Conference Paper %T Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization %A Siddharth Tourani %A Alexander Shekhovtsov %A Carsten Rother %A Bogdan Savchynskyy %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-tourani20a %I PMLR %P 2775--2785 %U https://proceedings.mlr.press/v108/tourani20a.html %V 108 %X 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.
APA
Tourani, S., Shekhovtsov, A., Rother, C. & Savchynskyy, B.. (2020). Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:2775-2785 Available from https://proceedings.mlr.press/v108/tourani20a.html.

Related Material