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 to find the most likely configuration of the discrete-valued model. Linear programming (LP) relaxations in the Sherali-Adams hierarchy are widely used to attempt to solve this problem, and smooth message passing algorithms have been proposed to solve regularized versions of these LPs with great success. This paper leverages recent work in entropy-regularized LPs to analyze convergence rates of a class of edge-based smooth message passing algorithms to $ε$-optimality in the relaxation. With an appropriately chosen regularization constant, we present a theoretical guarantee on the number of iterations sufficient to recover the true integral MAP solution when the LP is tight and the solution is unique.
Introduction
Maximum a posteriori (MAP) inference—finding the most likely configuration of variables in a graphical model—is a cornerstone of statistical machine learning. However, for discrete models common in computer vision or genomics, this is an NP-hard combinatorial problem. To make it tractable, researchers often employ Linear Programming (LP) relaxations, searching over a continuous space of "pseudo-marginals" rather than discrete values. While standard LP solvers exist, they scale poorly to massive graphs, leading to the development of message passing algorithms which are faster and inherently distributed.
To ensure reliable convergence, entropy regularization is often added to "smooth" the objective. While mathematically beneficial, this introduces an approximation error. This work provides the first non-asymptotic convergence rate analysis for smooth message passing in entropy-regularized MAP inference, bridging the gap between continuous optimization and discrete recovery.
Edge-based smooth Message Passing (EMP)
The paper focuses on a class of Edge-based smooth Message Passing (EMP) algorithms, viewing the regularized LP as a Bregman projection problem. Two primary variants are analyzed:
- EMP-cyclic: Updates every edge in the graph in a fixed order.
- EMP-greedy: Strategically updates the edge with the largest constraint violation first.
The authors utilize a novel Lyapunov function to track convergence, demonstrating that each update improves this function by an amount proportional to the squared Hellinger distance of the constraint violation. This approach allows for a precise determination of the regularization constant ($\eta$): it must be large enough to keep the smooth solution near the true MAP, yet small enough to maintain computational efficiency.
Theoretical Contributions
A key contribution of this work is proving convergence of the iterates themselves in $\ell_1$ distance, rather than just the objective value. This is critical for practitioners as it directly relates to the stability of the solution prior to rounding.
- Convergence Rate: The authors establish a convergence rate of $O(1/\epsilon^2)$ in $\ell_1$ distance for the iterates.
- Recovery Guarantee: Theorem 3 provides an explicit bound on the number of iterations required to guarantee that a standard rounding scheme will return the exact MAP assignment, provided the LP relaxation is tight and the solution is unique.
Experimental Evaluation
The theoretical findings were validated using synthetic Multi-label Potts models on various graph topologies, including grids and Erdős-Rényi random graphs.
The experiments confirmed the "Regularization Trade-off": while larger $\eta$ values improve the accuracy of the recovered MAP solution, they also slow down the convergence rate. Furthermore, the greedy variant was shown to be significantly more efficient in practice, as it prioritizes edges with the largest inconsistencies.
Conclusion
This research provides a rigorous theoretical foundation for using smooth message passing to solve discrete MAP inference problems. By establishing non-asymptotic convergence rates and recovery guarantees, it offers clear guidance on parameter selection for practitioners. Future work includes extending these results to cases where the LP relaxation is not tight and handling non-unique MAP solutions.
Summary updated