Research map / Optimization / Nonconvex and smooth optimization
Convergence of Some Convex Message Passing Algorithms to a Fixed Point
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that coordinate descent on piecewise-affine max-of-affine objectives, and hence max-sum diffusion and max-marginal averaging (convex message passing), converges to a fixed point in O(1/ε) iterations, and shows a mid-point-rule variant can cycle.
Problem
Convergence of convex (dual LP / Lagrangian) message passing methods for MAP inference, such as max-sum diffusion and TRW-S-style max-marginal averaging, which were known only to approach locally consistent sets without guaranteed convergence of iterates.
Approach
Introduces an energy function E_k(y) = sum_i k^i sort(y)_i with k = 1 + C/c that strictly decreases with every non-trivial coordinate update of ignore-constant-affine-functions coordinate descent; with bounded energy this gives iterate convergence to a fixed point and an O(1/ε) termination bound, which then transfers to max-sum diffusion and max-marginal averaging.
Key results
- Proves that the iterates of coordinate descent on max-of-affine objectives converge to a fixed point, terminating within O(1/ε) iterations under bounded energy.
- Shows max-sum diffusion weights are bounded below, so max-sum diffusion converges to a fixed point in O(1/ε) steps.
- Constructs an example where coordinate descent with the mid-point rule cycles.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Resolve non-unique coordinate minimizers by ignoring affine functions that do not depend on the updated variable | Coordinate descent on pointwise maxima of affine functions · Pointwise maximum of affine functions with bounded energy | iterations to precision ε: O(1/ε) | Helped |
| Apply the convergent coordinate-descent update to max-sum diffusion | Max-sum diffusion · MAP inference | iterations to precision ε: O(1/ε) | Helped |
| Apply the convergent coordinate-descent update to pairwise max-marginal averaging | Max-marginal averaging · Lagrangian decomposition | iterations to precision ε: O(1/ε) | Helped |
| Choose the midpoint of the coordinate-minimizer interval instead of using the rule that ignores constant affine functions (ablation) | Coordinate descent · Constrained convex coordinate descent | cycling: six updates | Hurt |
Surprising findings
- The mid-point rule for coordinate descent can cycle, unlike the ignore-constant rule.
- Skipping updates that do not decrease the objective is not allowed: the method can still need them to reach the global minimizer.
Limitations
- The O(1/ε) constant may depend exponentially on problem size and is not known to be tight.
- Convergence of iterates requires assuming boundedness of the energy, which is shown only for max-sum diffusion and max-marginal averaging.
- No empirical evaluation is provided.
Experimental setup
Baselines: max-sum diffusion max-marginal averaging TRW-S SRMP
Builds on: max-sum diffusion TRW-S max-marginal averaging relative interior rule for coordinate descent
Closest papers by meaning
- Relative Interior Rule in Block-Coordinate Descent (CVPR 2020 · similarity 0.93)
- Accelerated Message Passing for Entropy-Regularized MAP Inference (ICML 2020 · similarity 0.89)
- Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models (ICML 2022 · similarity 0.88)
- The Theory and Practice of MAP Inference over Non-Convex Constraints (ICML 2026 · similarity 0.87)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.84)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.