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

arXiv: https://arxiv.org/abs/2004.07715 · HTML: https://mlsanity.com/paper/2004.07715/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

## Built on by (most cited first, 8 of 8)

- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [A Comparative Study of Graph Matching Algorithms in Computer Vision](https://mlsanity.com/paper/2207.00291/) (2022)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective](https://mlsanity.com/paper/2201.02018/) (2022)
- [Convergence of Some Convex Message Passing Algorithms to a Fixed Point](https://mlsanity.com/paper/2403.07004/) (2024)
- [Virtual Arc Consistency for Linear Constraints in Cost Function Networks](https://mlsanity.com/paper/2509.17706/) (2025)
- [Leveraging 2D Priors and SDF Guidance for Dynamic Urban Scene Rendering](https://mlsanity.com/paper/2510.13381/) (2025)

## Abstract (arXiv)

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.