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

2020/04/16 by Siddharth Tourani, Tourani, Siddharth, Alexander Shekhovtsov +5 · 2 citations
Engineering · Physics and Astronomy · #Advanced Numerical Methods in Computational Mathematics #Electromagnetic Scattering and Analysis #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks

paper · pdf · doi:10.48550/arxiv.2004.07715

openalex publication_date 2020/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 existing solvers 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.

Citations

• Relative Interior Rule in Block-Coordinate Minimization

Cited by

• Leveraging 2D Priors and SDF Guidance for Dynamic Urban Scene Rendering
• Virtual Arc Consistency for Linear Constraints in Cost Function Networks

Related

• MAP inference via Block-Coordinate Frank-Wolfe Algorithm
• Proximal Stochastic Dual Coordinate Ascent
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical\n Models
• Automatically selecting inference algorithms for discrete energy\n minimisation
• A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems