the constraints, which is always tight [8]. This LP dual should be distinguished from our Lagrangian dual (12) that is the subject of our paper.

Introducing non-negative Lagrange multipliers µ(x
′) ≥ 0 for each inequality constraint, indexed by x
′ ∈ X
′, we obtain the LP Lagrangian:

$$M(h,\lambda;\mu)=h+\mu\left[\langle a(x^{\prime}),\lambda\rangle+b(x^{\prime})-h\right]\tag{14}$$ $$=\langle\mu[a],\lambda\rangle+\mu[b]+(1-\mu[1])h,$$
  **Acknowledgments**  I would like to thank my supervisor, for his kind of support. I would like to thank my supervisor, for his kind of support.  
where µ denotes µ-weighted summation, e.g., µ[a] =
∑x
′ µ(x
′)a(x
′). The LP dual function is then:

$$M^{*}(\mu)\triangleq\min_{h,\lambda}M(h,\lambda;\mu)=\left\{\begin{array}{ll}\mu[b],&\mu[1]=1\mbox{and}\mu[a]=0\\ -\infty,&\mbox{otherwise.}\end{array}\right.\tag{15}$$

Note that µ > 0 and µ[1] = 1 imply that µ is a probability distribution and µ[·] an expectation operator. Recalling a(x
′) , (φA(x
′)−φB(x
′),A ≡ B) and b(x
′) , f
′(x
′), we obtain the dual LP:

the dual $\mathbb{L}$.  $$\max_{\mu\geq0}M^{*}(\mu)=\left\{\begin{array}{ll}\mbox{maximize}&\mu[f^{\prime}]\\ \mbox{subject to}&\mu[\phi_{A}]=\mu[\phi_{B}]\mbox{for}A\equiv B\end{array}\right.\tag{16}$$  We seek a probability distribution over all configurations
of the augmented model that maximizes the expected value of f
′(x
′) subject to constraints that the moments specifying marginal distributions are consistent for replicated nodes and edges of the graph. This is a convex relaxation of the constrained version of problem (4), where the objective and constraint functions have been replaced by their expected values under µ. Note that only marginals µE′ over hyperedges E ∈ G
′are needed to evaluate both the objective and the constraints of this LP. Hence, it reduces to one defined over the *marginal polytope* M(G
′) [9], defined as the set of all *realizable* collections of marginals over the hyperedges of G

′. Moreover, if the graph G
′is *chordal* [2], then its marginal polytope has a simple characterization. Let Mlocal(G
′) denote the *local marginal polytope* defined as the set of all edgewise marginal specifications that are consistent on intersections of edges. In general, M(G
′) ⊂ Mlocal(G
′). However, in chordal graphs it holds that M(G
′) = Mlocal(G
′). Thus, if G
′is a thin chordal graph, we obtain a tractable LP whose value is equivalent to g
∗in our framework.3 One last step shows the connection to LP approaches [9],
[11], [12]. The key observation is that, roughly speaking, Mlocal(G
′)∩ {µ|µ(xA) = µ(xB),A ≡ B} ≡ Mlocal(G ). (17)
This is seen by replicating marginals from G to G
′, or by copying (consistent) replicated marginals back to G . For such consistent µ, we have µ[ f
′] = µ[ f ], which gives:

$$g^{*}=\max_{\mu\in\mathscr{M}_{\rm local}(\mathscr{G})}\mu[f]\geq\max_{\mu\in\mathscr{M}(\mathscr{G})}\mu[f]=f^{*}.\tag{18}$$

The maximum over Mlocal(G ) gives an upper-bound on the maximum over M(G ) ⊂ Mlocal(G ). The latter is equivalent 3Some graphs shown in Fig. 2 are not chordal, but they can be extended to a thin chordal graph by adding a few edges. If no two of these new edges are equivalent when mapped into G , then this does not change g
∗.

![0_image_0.png](0_image_0.png)

to exact MAP estimation and the bound becomes tight if G is the set of maximal cliques of a chordal graph. This discussion leads to the following characterization of LR:
Proposition 2 (LR Hierarchy): Equivalence: Let G
′1 and G

′2 be the set of maximal cliques of two chordal augmented graphs. If Γ
−1(G1) = Γ
−1(G2) then g
∗1 = g
∗2 for the respective dual problems. Let g
∗(G ) denote the common dual value of all such chordal relaxations where Γ
−1(G
′) = G . *Monotonicity:* If G1 ⊂ G2 then g
∗(G1) ≥ g
∗(G2). *Strong Duality:*
If G is the set of maximal cliques of a chordal graph, then g
∗(G ) = f
∗.

## E. Smooth Relaxation Of The Dual Problem

In this section, we develop an approach to solve the dual problem. One approach to minimize g(λ) is to use non-smooth optimization methods, such as the subgradient method [8]. Here, we consider an alternative, based on the following smooth approximation of g(λ):

$$g(\lambda;\tau)\triangleq\tau\log\sum_{x^{\prime}\in\mathbb{X}}\exp\left({\frac{L(x^{\prime};\lambda)}{\tau}}\right)$$
$$(19)$$

(19)
As illustrated if Fig. 4, the parameter τ > 0 controls the trade-off between smoothness of g(λ;τ) and how well it approximates g(λ). This is known as the "log-sum-exp" approximation to the "max function" [14]:

$$g(\lambda)\leq g(\lambda;\tau)\leq g(\lambda)+\tau\log|\mathbb{X}|{\mathrm{~for~all~}}\tau>0.$$
$\mathcal{F}$ /-. 
Hence, g(λ;τ) → g(λ) *uniformly* as τ → 0 and, hence, g
∗(τ) , minλ g(λ;τ) converges to g
∗.

The function g(λ;τ) has another useful interpretation.

Consider the Gibbs distribution defined by

$$(20)$$
$$p_{\lambda,\tau}(x^{\prime})=\exp\left({\frac{L(x^{\prime},\lambda)-g(\lambda;\tau)}{\tau}}\right)$$
$$(21)$$

(21)
Here, τ > 0 is the "temperature" and g(λ;τ) normalizes the distribution for each choice of λ and τ, and is equal to the Helmholtz free energy FH(θ
′) = τΦτ (θ
′), where Φτ (θ
′) =
logΣexp(τ
−1hθ
′,φ
′(x
′)i) is the usual log-partition function.

Thus, g(λ;τ) is a strictly convex, analytic function. Using the moment-generating property of Φτ (θ
′), the gradient of