Convergence Rates of Smooth Message Passing with Rounding in Entropy-Regularized MAP Inference

Jonathan Lee, Aldo Pacchiano, Michael I. Jordan

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:

  1. EMP-cyclic: Updates every edge in the graph in a fixed order.
  2. 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.

Convergence of EMP-greedy and EMP-cyclic algorithms for $n=2500$ across different regularization strengths $\eta$.

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.

Recovery of the integral MAP solution as a function of graph size $n$ and regularization strength $\eta$. Higher $\eta$ values consistently lead to lower Hamming distances from the optimal solution.

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

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.
BibTeX
@inproceedings{lee2020convergence,
  author = {Jonathan Lee and Aldo Pacchiano and Michael I. Jordan},
  title = {{Convergence Rates of Smooth Message Passing with Rounding in Entropy-Regularized MAP Inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=BtLIMN-7mDK},
}
Figure