An Alternating Direction Method for Dual MAP LP Relaxation

Ofer Meshi, Amir GlobersonECML/PKDD 2011 · OpenReview

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:

  1. 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.
  2. Variable Splitting: Auxiliary variables and agreement constraints are introduced to maintain consistency across the model's various components.
  3. Efficient Updates: The optimization is decomposed into smaller subproblems with closed-form solutions. A specialized TRIM subroutine is used to efficiently project values onto constraints in linear time.
  4. 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.

Convergence of ADLP compared to MPLP and ADD on protein design benchmarks 1jo8 and 1ycc.

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.
Performance on dataset 1a8i (left) and comparison between dual ADLP and primal APLP on 1jo8 (right).
  • 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

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.
BibTeX
@inproceedings{meshi2011alternating,
  author = {Ofer Meshi and Amir Globerson},
  title = {{An Alternating Direction Method for Dual MAP LP Relaxation}},
  booktitle = {ECML/PKDD},
  year = {2011},
  url = {https://openreview.net/forum?id=Hw3SRYsljrC},
}
Figure