Abstract
Maximum a posteriori (MAP) inference is a fundamental computational paradigm for statistical inference. In the setting of graphical models, MAP inference entails solving a combinatorial optimization problem. This paper provides the first non-asymptotic convergence rates for smooth message passing algorithms to recover the exact MAP solution by combining entropy regularization with a vertex rounding scheme. The authors prove exactly how many iterations are needed to find the true discrete configuration, provided the underlying linear programming (LP) relaxation is "tight."
Introduction
MAP inference—finding the most likely state of a set of random variables—is a cornerstone of machine learning, used in everything from computer vision to genome research. However, for discrete-valued graphical models, this is generally an NP-hard combinatorial problem. To make it tractable, researchers often use Linear Programming (LP) relaxations, which turn the discrete problem into a continuous one. While standard LP solvers exist, they don't scale well to large graphs. This led to the development of message passing algorithms, which are faster and more distributed. To ensure these algorithms converge to a unique point, researchers "smooth" the objective using entropy regularization.
The gap? While we knew these smooth algorithms were fast, we didn't have a clear theoretical guarantee on how many iterations were required to actually recover the original discrete solution after rounding the continuous results. This paper bridges that gap between continuous optimization and discrete recovery.
Methods
The authors analyze a class of Edge-based Message Passing (EMP) algorithms. These algorithms solve the entropy-regularized version of the Sherali-Adams LP relaxation.
Key components include:
- Entropy Regularization: Adding a negative entropy term to the objective function. This makes the optimization problem strictly convex, ensuring a unique solution ($\mu^*_\eta$).
- Bregman Projections: The algorithm works by iteratively projecting the current solution onto the constraints of the "local polytope" (ensuring consistency between neighboring variables). The authors derive closed-form updates for these projections.
- Two Variants: EMP-cyclic, which updates every edge in a fixed order, and EMP-greedy, which updates only the edge with the largest constraint violation at each step.
- Rounding: After a certain number of iterations, a simple "argmax" is applied to the continuous pseudo-marginals at each vertex to produce a discrete assignment.
Key Insights and Theoretical Contributions
Most prior work focused on how fast the objective value improves. This paper focuses on primal iterate convergence—how fast the actual variable assignments move toward the optimal point in $l_1$ distance.
The Regularization Trade-off
There is a delicate balance for the regularization constant ($\eta$). If $\eta$ is too small, the algorithm is slow; if it's too large, the "smooth" solution drifts too far from the true discrete solution. The authors provide an explicit lower bound for $\eta$ that guarantees recovery.
Lyapunov Analysis
To prove convergence, the authors use a Lyapunov function based on dual variables. They show that every message passing update monotonically improves this function by an amount proportional to the "violation" of the constraints (measured via Hellinger distance).
Experimental Results
The authors evaluated their findings using synthetic experiments on Multi-label Potts Models with grid structures and Erdős-Rényi random graphs.
Convergence Rates
Both EMP-cyclic and EMP-greedy are shown to reach $\epsilon$-consistency in $O(1/\epsilon^2)$ iterations. Theorem 3 provides the "main event": a combined bound on iterations and regularization needed to guarantee that rounding the result yields the exact MAP solution.
Greedy vs. Cyclic and Graph Density
Empirically, the Greedy variant converges significantly faster in terms of projection steps, as it prioritizes fixing the "worst" parts of the graph first. Additionally, experiments confirmed that higher-degree graphs (more connections per node) require more iterations to reach the same level of accuracy.
Conclusion
This research provides a rigorous theoretical bridge between continuous message passing and discrete MAP recovery. By establishing non-asymptotic convergence rates, it offers practical guidance on choosing regularization parameters and iteration counts for reliable inference in graphical models. Future work may extend these techniques to higher-order polytopes and more general block-coordinate minimization schemes.
Summary updated