# Convergence of Some Convex Message Passing Algorithms to a Fixed Point

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 7 Mar 2024.

## Builds on (most cited first, 12 of 12)

- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [Learning Deep Structured Models](https://mlsanity.com/paper/1407.2538/) (2014)
- [A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems](https://mlsanity.com/paper/1404.0533/) (2014)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [A new look at reweighted message passing](https://mlsanity.com/paper/1309.5655/) (2013)
- [Discrete graphical models -- an optimization perspective](https://mlsanity.com/paper/2001.09017/) (2020)
- [Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization](https://mlsanity.com/paper/2004.07715/) (2020)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems](https://mlsanity.com/paper/1612.05460/) (2016)
- [Solving Dense Image Matching in Real-Time using Discrete-Continuous Optimization](https://mlsanity.com/paper/1601.06274/) (2016)
- [Scalable Full Flow with Learned Binary Descriptors](https://mlsanity.com/paper/1707.06427/) (2017)

## Abstract (arXiv)

A popular approach to the MAP inference problem in graphical models is to minimize an upper bound obtained from a dual linear programming or Lagrangian relaxation by (block-)coordinate descent. This is also known as convex/convergent message passing; examples are max-sum diffusion and sequential tree-reweighted message passing (TRW-S). Convergence properties of these methods are currently not fully understood. They have been proved to converge to the set characterized by local consistency of active constraints, with unknown convergence rate; however, it was not clear if the iterates converge at all (to any point). We prove a stronger result (conjectured before but never proved): the iterates converge to a fixed point of the method. Moreover, we show that the algorithm terminates within O(1/varepsilon) iterations. We first prove this for a version of coordinate descent applied to a general piecewise-affine convex objective. Then we show that several convex message passing methods are special cases of this method. Finally, we show that a slightly different version of coordinate descent can cycle.