Abstract
Maximum a-posteriori (MAP) estimation is an important task in many applications of probabilistic graphical models. Although finding an exact solution is generally intractable, approximations based on linear programming (LP) relaxation often provide good approximate solutions. In this paper we present an algorithm for solving the LP relaxation optimization problem. In order to overcome the lack of strict convexity, we apply an augmented Lagrangian method to the dual LP. The algorithm, based on the alternating direction method of multipliers (ADMM), is guaranteed to converge to the global optimum of the LP relaxation objective. Our experimental results show that this algorithm is competitive with other state-of-the-art algorithms for approximate MAP estimation.
Introduction
In fields ranging from computer vision to computational biology, graphical models are essential for representing complex dependencies between variables. A fundamental challenge in these models is Maximum A-Posteriori (MAP) estimation—identifying the single most probable state of the system. Since exact MAP estimation is NP-hard, researchers frequently turn to Linear Programming (LP) relaxations.
However, standard LP solvers often struggle with the scale of real-world models. Specialized alternatives have significant drawbacks: Coordinate Descent methods like MPLP are fast but can stall at local optima due to a lack of strict convexity in the dual problem. Subgradient Descent offers global convergence but is often prohibitively slow. Primal ADMM approaches, while globally convergent, have historically been limited to simple binary pairwise models. This paper introduces the Augmented Dual LP (ADLP) algorithm to provide a globally convergent, efficient, and general-purpose solver.
Methodology: The ADLP Algorithm
The authors propose applying the Alternating Direction Method of Multipliers (ADMM) to the dual formulation of the MAP-LP problem. This approach, termed ADLP, incorporates several key innovations:
- Augmented Lagrangian: By adding a quadratic penalty term to the dual objective, the authors "smooth" the optimization landscape. This overcomes the non-strict convexity that typically causes coordinate descent methods to fail.
- Variable Splitting: Auxiliary variables and agreement constraints are introduced to maintain consistency across the model's various components.
- Efficient Updates: The optimization is decomposed into smaller subproblems with closed-form solutions. A specialized
TRIMsubroutine is used to efficiently project values onto constraints in linear time. - Parallelization: The decoupled nature of the variable and factor updates makes ADLP naturally suitable for parallel computing architectures.
Experimental Evaluation
The algorithm was tested on dense, high-order protein design and side-chain prediction tasks from the Yanover et al. (2006) dataset. These problems are particularly challenging because variables can have up to 100 possible states.
Key Results
The experiments yielded several critical insights:
- Global Optimality: Unlike MPLP, which frequently stalled at suboptimal points in dense protein design tasks, ADLP consistently reached the global optimum of the LP relaxation.
- Competitive Efficiency: ADLP's convergence speed is comparable to Accelerated Dual Decomposition (ADD), the state-of-the-art at the time of publication.
- Dual vs. Primal Advantage: A direct comparison between the dual-based ADLP and a generalized primal ADMM (APLP) revealed that the dual formulation is significantly faster and more flexible for handling general factors.
- Decoding Quality: There is a strong correlation between the dual objective's quality and the quality of the final decoded integer solution (the MAP assignment).
Discussion and Future Work
While ADLP is robust and efficient, its worst-case complexity is $O(1/\epsilon^2)$. Future work may explore "accelerated" ADMM variants to reach the theoretical $O(1/\epsilon)$ lower bound. Additionally, while the penalty parameter $\rho$ does not affect the final accuracy, its selection impacts convergence speed; adaptive penalty strategies could further optimize performance. Finally, a hybrid approach—using MPLP for initial rapid progress before switching to ADLP for global convergence—could leverage the strengths of both methods.
Summary updated