Augmenting Dual Decomposition for MAP Inference∗

André F. T. Martins∗†
Noah A. Smith∗
Eric P. Xing∗
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA

Pedro M. Q. Aguiar‡
Instituto de Sistemas e Robótica,
Instituto Superior Técnico, Lisboa, PortugalMário A. T. Figueiredo†
Instituto de Telecomunicações,
Instituto Superior Técnico, Lisboa, Portugal‡†

Abstract
In this paper, we propose combining augmented Lagrangian optimization withthe dual decomposition method to obtain a fast algorithm for approximate MAP(maximum a posteriori) inference on factor graphs. We also show how the proposed algorithm can efficiently handle problems with (possibly global) structural
constraints. The experimental results reported testify for the state-of-the-art performance of the proposed approach.

1

Introduction

Finding the most probable (usually called MAP) configuration of a probabilistic graphical model(e.g., a factor graph – FG [27]) is in general an NP-hard problem, a fact which has stimulated
much work on approximate methods. The dual decomposition (DD) [3, 4] is one such approximate
method, which has been recently used in computer vision [17] and natural language parsing [18]. In
a nutshell, DD works by breaking the original hard problem into a set of smaller (slave) subproblems.
This set of subproblems, together with the constraints that they should agree on the variables theyshare, yields a constrained optimization problem, the Lagrange dual of which is then usually attacked
with a subgradient method. While a subgradient algorithm handles this dual problem efficiently forlightweight decompositions (i.e., with few slaves), in the presence of a large number of slaves its
performance degrades, making accelerated methods worthy of study [14]. Here, we propose to ally
the strength of DD with the effectiveness of augmented Lagrangian (AL) methods, which have along and successful history in optimization [13, 21], and which have recently been shown to be
extremely competitive for some large scale problems [1, 7, 12]. Specifically, we use the alternating
direction method of multipliers (ADMM) [8, 11, 6] to handle the dual of the constrained problem
resulting from the DD, and show that the resulting method has state-of-the-art performance.
Being interested in problems with (possibly global) structural constraints (common in structured
prediction [2]), we show that the proposed method can handle this class of problems efficiently.
This efficiency is rooted in the fact that the slave problems associated with the hard factors enforcing
some of these structural constraints can be solved with the help of sort operations. Each ADMM
iteration thus has a cost comparable to that of an iteration of the message-passing algorithm or of
the subgradient method applied to the DD. Moreover, the residual term in the AL can be used asa primal feasibility test and to obtain optimality certificates for the approximate MAP problem, an
important advantage over other methods. Finally, our method is also heavily parallelizable.

2

Problem Formulation

Let X , (X1 , . . . , Xn ) ∈ X be a vector of discrete random variables, where each Xi ∈ Xi , with Xi
a finite set. We assume that X has a Gibbs distribution associated with
Pna FG G, composed
P of variablenodes {1, . . . , n} and a set of factor nodes A: Pθ,φ (x) ∝ exp
θ
(x
)
+
i
i
i=1
a∈A φa (xa ) ,1where each factor a ∈ A is linked to a subset of variables N (a) ⊆ {1, . . . , n}, xa stands forthe subvector indexed by the elements of N (a), and θi and φa are, respectively, unary and higherorder log-potentials. To accommodate hard constraints, we allow these functions to take values inR ∪ {−∞}. For simplicity, we write θ i , (θi (xi ))xi ∈Xi and φa , (φa (xa ))xa ∈Xa .
Given a FG G, a common task is to find the most probable assignment x̂ , arg maxx∈X Pθ,φ (x)(often termed MAP—maximum a posteriori—since Pθ,φ is usually the posterior distribution insome Bayesian inference problem). This (in general NP-hard) combinatorial problem can be transformed into a linear program (LP) by introducing marginal variables µ , (µi )ni=1 and ν , (ν a )a∈A
and letting M(G) be the marginal polytope of G – i.e. the set of realizable marginals [27]. This yields
X
X
OPT ,
max
θ>
φ>
(1)
i µi +a ν a,(µ,ν)∈M(G)aiwhich always admits an integer solution. Unfortunately, M(G) often lacks a concise representation(e.g., if G has loops), rendering (1) intractable. A common workaround is to replace M(G) by theouter bound L(G) ⊇ M(G)—the so-called local polytope, defined as
L(G) = (µ, ν) | 1> µi = 1, ∀i ∧ (Hia ν a = µi , ∀a, i ∈ N (a)) ∧ (ν a ≥ 0, ∀a) ,(2)
where Hia (xi , xa ) = 1 if xa agrees with xi , 0 otherwise. This yields the following LP relaxation:
X
X
OPT0 ,
max
(3)
θ>
φ>
a ν a,i µi +(µ,ν)∈L(G)ai0which will be our main focus throughout. Obviously, OPT ≥ OPT, since L(G) ⊇ M(G).

3Dual Decomposition

Several message passing algorithms [9, 15] are derived via some reformulation of (3) followed bydualization. The DD method [17] reformulates (3) by adding new variables ν ai (for each factor aand i ∈ N (a)) that are local “replicas” of the marginals µi , and enforcing agreement among thosevariables. Letting di = |{a|i ∈ N (a)}| be the degree of node i, (3) is rewritten as


X
X
> a
>


max
d−1
(4)
i θ i ν i + φa ν a
ν,µ

s.t.

a

i∈N (a)a(ν N (a) , ν a ) ∈ M(Ga ),∀a;ν ai = µi ,∀a, i ∈ N (a),where Ga is the subgraph of G comprised only of factor a and the variables in N (a), M(Ga ) is thecorresponding marginal polytope, and we denote ν aN (a) , (ν ai )i∈N (a) . Note that problem (4) would
be completely separable (over the factors) if it were not the “coupling” constraints ν ai = µi . With
Lagrange multipliers λai for these constraints, the dual problem is minλ∈Λ L(λ), where:
X
X

a > a
L(λ) ,maxd−1
ν i + φ>(5)a ν a,i θ i + λi
a
a


Λ

,

λ

(ν N (a) ,ν a )∈M(Ga )Xi∈N (a)λai = 0,


∀i .

(6)

a|i∈N (a)A closer look at (5) reveals a set of MAP subproblems of the same kind of (1), but now local toeach factor a: the so-called slave problems. The master problem is the minimization of L w.r.t.
λ, which can be carried out elegantly via the projected subgradient algorithm: a subgradient is
simply ∇λai L(λ) = ν̂ ai , where (ν̂ aN (a) , ν̂ a ) is solution of the slave problem associated with a(these slaves can be handled in parallel); a projection onto Λ is simply a centering operation. The
resulting algorithm is described in Alg. 1 (where we denote by MAP(ω N (a) , φa ) the MAP solution
for factor a, given unary log-potentials ω N (a) , (ω ai )i∈N (a) and factor log-potentials φa ). For
adequate choices of the stepsize sequence (ηt )t∈T , this method is guaranteed to converge; however,convergence can be slow if the number of slaves is large. In the next section we introduce a fastermethod which, instead of computing the MAP at each factor a, computes projections onto M(Ga ).
2

Algorithm 1 DD-Subgradient
1: input: factor graph G, parameters θ, φ, number of iterations T , sequence (ηt )T
t=1
2: Initialize λ = 0
3: for t = 1 to T do
4:for each factor a ∈ A doa5:
Set unary potentials ω ai = d−1i θ i + λi , for i ∈ N (a)aa6:Compute (ν̂ N (a) , ν̂ a ) = MAP ω N (a) , φa7:
end forP
8:
Compute average ν̄ i = di −1 a:i∈N (a) ν̂ ai
9:Update λai ← λai − ηt (ν̂ ai − ν̄ i )10: end for
11: output: λ4Augmented Lagrangian (AL) Method

Given an optimization problem with equality constraints, the AL function is the Lagrangian augmented with a quadratic constraint violation penalty. For the constraint problem (4), the AL isAη (µ, ν, λ) ,
X X
a


a > a
ν i + φ>d−1a νai θ i + λi

!
−

X X
a i∈N (a)i∈N (a)>λai µi −ηX Xkν ai − µi k2 ,2 ai∈N (a)where η controls the weight of the penalty. We want to maximize this function with respect to µ andν, subject to (ν aN (a) , ν a ) ∈ M(Ga ), ∀a. Unfortunately, the quadratic term breaks the separability,
making this maximization harder. In the ADMM approach, this difficulty is addressed by alternating
between maximizing w.r.t. µ and w.r.t. ν, followed by an adjustment of the Lagrange multipliers[8, 11, 6] (as shown in Alg. 2). Crucially, the maximization w.r.t. µ has closed form, while that w.r.t.
ν can be carried out in parallel at each factor, as in Alg. 1; the only difference is that, instead of
MAP, the slaves are now quadratic problems of the form
ηt X amin(7)kν i − ηt−1 ω ai k2 − φ>a ν a,
2
(ν a
,ν
)∈M(G
)
a
a
N (a)
i∈a
where ηt > 0 is the penalty parameter at iteration t. In Alg. 2, we denote by QUADηt(ω N (a) , φa )the solution of (7); note that as ηt → 0, QUADηt (ω N (a) , φa ) approaches MAP(ω N (a) , φa ), thus
Alg. 2 approaches Alg. 1. However, we will see that for a proper choiceof ηt , Alg. 2 converges√
faster. In practice, it is common to use a fixed ηt = η and 1 < τ ≤ ( 5 + 1)/2 ' 1.61 [10]. With
these choices, and assuming that QUADηt is computed exactly, convergence is guaranteed, since in(4), both the objective function (which is linear) and the feasible set are convex [10]. Under certain
conditions, convergence can still be guaranteed with only approximate solutions of (7) [6].
Algorithm 2 DD-ADMM
1: input: factor graph G, parameters θ, φ, number of iterations T , sequence (ηt )T
t=1 , parameter τ
2: Initialize µ uniformly, λ = 0
3: for t = 1 to T do
4:for each factor a ∈ A doa5:
Set unary potentials ω ai = d−1i θ i + λi + ηtµi , for i ∈ N (a)aa6:
Update (ν N (a) , ν a ) ← QUADηt ω N (a) , φa7:
end forP
8:Update µi ← di −1 a:i∈N (a) ν ai − ηt−1 λai
9:Update λai ← λai − τ ηt (ν ai − µi )10: end for
11: output: µ, ν, λThe remaining challenge is to devise efficient algorithms for solving (7). We next show a closed form
solution for the the case of binary pairwise factors, and an exact and efficient (O(|N (a)| log |N (a)|),3

since it is based on sorting) algorithm for several hard constraint factors that arise in practice (see,e.g., [19]). Up to log terms, this cost is the same as that of computing the MAP for those factors.
Binary pairwise factors. If factor a is binary and pairwise (|N (a)| = 2), problem (7) can be
re-written as the minimization of 12 (z1 − c1 )2 + 21 (z2 − c2 )2 − c12 z12 , w.r.t. (z1 , z2 , z12 ) ∈ [0, 1]3 ,under the constraints z12 ≤ z1 , z12 ≤ z2 , and z12 ≥ z1 + z2 − 1, where c1 , c2 and c12 are functionsof ω ai and φa . Considering c12 ≥ 0, without loss of generality (if c12 < 0, we recover this case by0
redefining c01 = c1 + c12 , c02 = 1 − c2 , c012 = −c12 , z20 = 1 − z2 , z12= z1 − z12 ), the lower boundconstraints z12 ≥ z1 + z2 − 1 and z12 ≥ 0 are always innactive and can be ignored. By inspecting∗
the KKT conditions we obtain the following closed form solution: z12= min{z1∗ , z2∗ } and(([c1 ]U ,[c2 + c12 ]U )if c1 > c2 + c12([c1 + c12 ]U ,[c2 ]U )if c2 > c1 + c12(z1∗ , z2∗ ) =(8)([(c1 + c2 + c12 )/2]U , [(c1 + c2 + c12 )/2]U ) otherwise,
where [x]U = min{max{x, 0}, 1} denotes the projection (clipping) onto the unit interval.
Hard constraint factors. Hard factors have indicator log-potential functions: φa (xa ) = 0, if
xa ∈ Sa , and −∞ otherwise, where Sa is an acceptance set. This type of factors has several
applications, such as error-correcting decoders [23], named entity resolution [26], and dependency
parsing [19]. For binary variables, hard factors impose logical constraints; e.g.,Pn• the one-hot XOR factor, for which SXOR = {(x1 , . . . , xn ) ∈ {0, 1}n | i=1 xi = 1},Wn• the OR factor, for which SOR = {(x1 , . . . , xn ) ∈ {0, 1}n | i=1 xi = 1},
Wn−1• the OR - WITH - OUTPUT factor, for which SOR - OUT = {(x1 , . . . , xn ) ∈ {0, 1}n | i=1 xi = xn }.
Variants of these factors (e.g., with negated inputs/outputs) allow computing a wide range of otherlogical functions; it can be shown that the marginal polytope of a hard factor with binary variables
and acceptance set Sa is defined by z ∈ conv Sa , where z , (µ1 (1), . . . , µn (1)) and conv denotes
the convex hull. Letting c = (ωai (1) + 1 − ωai (0))i∈N (a) , problem (7) becomes that of minimizingkz − ck2 subject to z ∈ conv Sa , which is a Euclidean projection onto a polyhedron:• conv SXOR is the probability simplex; the projection can be computed efficiently using a sort [5].
• conv SOR is a hypercube with a vertex removed and conv SOR - OUT is a pyramid whose base is a
hypercube with a vertex removed; in both cases, the projections can be efficiently computed using
one or two sorts; due to lack of space, we omit details.
Larger slaves. Finally, note that it is simple to address general, larger subgraphs using algorithms
with fast convergence guarantees: e.g., a primal-dual vanilla scheme, like the one proposed in [22],resulting in cyclic projection algorithms. These can be useful to tackle coarser decompositions, inwhich each subgraph is a chain or a tree. Even if each projection is not computed exactly, convergence of ADMM may still be guaranteed under certain conditions [6]; this deserves further study.

5

Experiments

We compare DD-ADMM (Alg. 2) with two other approximate MAP inference algorithms: DDsubgradient ([17], Alg. 1); Star-MSD (max-sum diffusion with star updates, [20]), which performs
dual block coordinate descent message-passing. Fig. 1 shows a typical plot for an Ising model (binary pairwise MRF) on a random grid. We observe that DD-subgradient is the slowest, taking a longtime to find a “good” primal feasible solution, arguably due to the large number of slave subproblems (we have only considered naive decompositions; coarser ones, i.e., fewer slave problems, arethe topic of future work). Star-MSD performs better but it is outperformed by DD-ADMM, which
manages to approach a near optimal primal-dual solution in a few tens of iterations.
A second set of experiments aims at assessing the ability of DD-ADMM for handling problems withheavily constrained outputs. The task is non-projective dependency parsing of natural language
sentences, to which DD approaches have recently been applied [18]. Fig. 2 depicts an example ofa sentence (the input) and its dependency tree (the output to be predicted). Second-order models
are state-of-the-art for this task: they include scores for each possible arc and for certain pairs of4

Non-projective 1135
Dependency Parsing using Spanning
Star−MSD dualTree Algorithms

Figure 1: Results for a randomly gener-

DD−Subgrad. dual
DD−ADMM dual

1130

ated 30 × 30 Ising model. Shown are thedual objectives and the best primal feasible solution at each iteration. For DDsubgradient, we set ηt = η0 /t and picked
the η0 yielding maximum dual improvement in 10 iterations, with halving steps(those iterations are not plotted). For DDADMM, we set η = 5.0 and τ = 1.5. All
decompositions are edge-based.

Star−MSD primal
Ryan McDonald
Fernando Pereira
DD−Subgrad. primal
DD−ADMM
primal1120
Departmentof Computer and Information
Science1115
University of Pennsylvania
1110{ryantm,pereira}@cis.upenn.edu
1105

Objective

1125

1100

Kiril Ribarov
Jan Hajič
InstituteofFormalandApplied
Linguistics
10
20
30
40
50
60
70
80
90
100
of iterations
CharlesNumber
University{ribarov,hajic}@ufal.ms.mff.cuni.cz
1095
1090

Abstract
root

John

hit

the

ball

with

the

bat

We formalize weighted dependency parsing as searching for maximum spanning
Figure 1: An example dependency tree.
OR
XOR
SIB
SIB
SIB
trees (MSTs) in directed graphs. Using
FLOW-IMPLIES-ARC
SINGLE-PARENT(h,m,k)representations,which link(m)words to(h,m�,m�)1this representation, the parsingGRAND
algorithm (h,m�,m�)
2 Dependency23 (h,m�,m�)
13
their arguments, have a long history (Hudson, 1984).
of Eisner (1996) is sufficient (g,h,m�)for search1
Figure 1 shows a dependency tree for the sentence
ing over all projective trees in O(n3 ) time.
ARC
FLOW
ARC
ARC
(h,m)
(h,m,k)(n,m)
John hit the ball with the bat. We(0,m)
restrict ourselves
More surprisingly, the representation istree analyses, in which each word de- FLOW-DELTA
extended naturally to non-projective pars- ARC to dependency
ARC
ARC
PATH-BUILDER
ARC
(h,k)
pends
on exactly
another wordXORor a(m,k)(h,m�)(h,m�)(h,m�)
3one parent, either
ing using Chu-Liu-Edmonds (Chu
and
1
2
(g,h)
dummy
root
symbol
as
shown
in
the
figure. The tree
Liu, 1965; Edmonds, 1967) MST alin Figure 1 is projective, meaning that if we put thegorithm, yielding an O(n2 ) parsing alwords in their linear order, preceded by the root, FLOWthe FLOW PATH
gorithm. We evaluate these methods
FLOW FLOW PATH(h,k)(h,1,k) (h,n,k)
edges TREE
can be drawn above the(0,m,k)words(n,m,k)
without
cross(m,k)
on the Prague Dependency Treebank usings, or, equivalently, a word and its descendants
ing online large-margin learning techa contiguous
substring
the sentence.
Figure2: Top:Example of aform
dependency
parsetree. ofEacharc (h, m) links a head word h to a modifierniques (Crammer
et al., 2003;
McDonald
left: Tree-based
factorgraphcorresponding
to a second-order dependency parsing model
et al., 2005) andword
showm.
thatBottom
MST parsing
In English, projective trees are sufficient to anawithandsiblingand forgrandparent
features [25]. Note the TREE hard constraint factor, which enforces the overall
increases efficiency
accuracy
lanlyze most sentence types. In fact, the largest source
variable assignment
to encode a valid parse tree. Bottom right: The flow-based factor graph is an alternative
guages with non-projective
dependencies.
of English dependency trees is automatically gener-

representation for the same model, in which extra flow and path variables are added, and the TREE factor isated from the Penn Treebank (Marcus et al., 1993)
replaced by smaller XOR, OR and OR - OUT factors to impose connectivity. See [19] for further information.

and is by convention exclusively projective. However, there are certain examples in which a nonDependency parsingarcs
has (e.g.,seen asiblings
surge ofandinterprojective treethe
is preferable.
the sentence
grandparents);
goal is toConsider
find a directedspanning tree maximizing theest lately for applications
such
as relation
extrac- John with
saw a twodog yesterday
which wasa Yorkshire
Teroverall
score.
We experimented
factor graphs
that
represent
this problem (see Fig. 2). Ourtion (Culotta and Sorensen,
machinetransrier.in
Heretheetrelative
clausewhichcombines
was a Yorkshire
model 2004),
is different
fromthe oneKoo
al. [18],
which
a tree constraint with factors thatlation (Ding and Palmer,2005),
synonymgenera-(instead
Terrierofandthe object
it modifies(the dog) are amounts
sepemulate
head
automata
pairs
of arcs);
this essentiallyto combining only twotion (Shinyama et al., 2002), and lexical resource arated by an adverb. There is no way
draw theor three slaves. In our case, both factor graphs yield O(n3 )toslaves(n being the number of words
augmentation (Snow et al., 2004). The primary dependency tree for this sentence in the plane within the sentence), which degrades the performance of standard DD methods. This is illustrated inreasons for using dependency structures instead of no crossing edges, as illustrated in Figure 2. In lanFig. 3, which shows that DD-subgradient is slow to converge, even for the more favorable treemore informative lexicalized phrase structures is guages with more flexible word order than English,
basedtofactor
graph
synthetic
andDutchreal-world
data).
For this problem, Star-MSD also hasthat they are more efficientlearn andparse(bothwhilewithsuch
as German,
and Czech,
non-projective
performance, whileconvergeRich
to a inflection
near-optimal solution very fast (notestill encoding much ofpoor
the predicate-argument
infor-DD-ADMM
dependenciesmanages
are moretofrequent.
the sharp decrease in relativesystems
error onthe reliancerighthandplot, ordercomparedwith DD-subgradient).
mation needed in applications.
reduceon word
to express

1 Introduction

Figure 3: Dependency parsing with second-order models. For DD-subgradient, we considered both tree-based
and flow-based factor graphs, and set η0 as in Fig. 1. DD-ADMM (η = 0.05 and τ = 1.5) and Star-MSD
ran on a flow-based factor graph. Left: synthetic model for a sentence with 10 words; we randomly generated(unary) arc log-potentials from N(0, 1), and (pairwise) grandparent and sibling log-potentials from N(0, 0.1).
Right: results on §23 of the Penn Treebank; the plot shows relative errors per iteration w.r.t. the dual optimum,
averaged over the 2,399 test sentences.

5

6

Related Work and Final Remarks

The DD method for MAP inference was first proposed for image segmentation using pairwise [17]and higher order factor graphs [16]. It was recently adopted for natural language parsing [24, 18],
with only a couple of slave subproblems handled with dynamic programming. Accelerated DD werefirst considered in [14], where the approach is to individually smooth each slave subproblem with theaddition of an entropic term, making the objective differentiable, thus adequate for gradient-based
methods. Although there are variants of ADMM that use entropic (rather than quadratic) penalties,
that does not lead to the same problem as in [14]. Quadratic problems (as in (7)) were also recently
considered in a sequential algorithm [22]; however, that algorithm tackles the primal formulationand only pairwise models are considered.
The proposed DD-ADMM algorithm is dual decomposable, hence the slaves can all be solved inparallel, making DD-ADMM particularly suitable for multi-core architectures, offering important
speed-ups. Finally, note that a significant amount of computation can be saved by caching andwarm-starting the subproblems, which tend to become more and more similar in later iterations. In
future work, we plan to experiment with larger slaves and approximate ADMM steps.

Acknowledgments
A. M. was supported by FCT/ICTI through the CMU-Portugal Program, and also by Priberam Informática.
N. S. was supported by NSF IIS-0915187 and an IBM faculty award. E. X. was supported by AFOSR
FA9550010247, ONR N000140910758, NSF CAREER DBI-0546594, NSF IIS-0713379, and an Alfred P.
Sloan Fellowship. This work was partially funded by the FET programme (EU FP7), under the SIMBAD
project (contract 213250), and by a FCT grant PTDC/EEA-TEL/72572/2006.

References[1] Afonso, M., Bioucas-Dias, J., and Figueiredo, M. (2010). Fast image recovery using variable splitting and constrained optimization. IEEE
Trans. on Image Processing, 19:2345–2356.
[2] Bakır, G., Hofmann, T., Schölkopf, B., Smola, A., Taskar, B., and Vishwanathan, S. (2007). Predicting Structured Data. The MIT Press.
[3] Bertsekas, D., Hager, W., and Mangasarian, O. (1999). Nonlinear programming. Athena Scientific.
[4] Dantzig, G. and Wolfe, P. (1960). Decomposition principle for linear programs. Operations research, 8(1):101–111.
[5] Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, T. (2008). Efficient projections onto the L1-ball for learning in high dimensions.
In ICML.
[6] Eckstein, J. and Bertsekas, D. (1992). On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone
operators. Mathematical Programming, 55(1):293–318.
[7] Figueiredo, M. and Bioucas-Dias, J. (2010). Restoration of Poissonian images using alternating direction optimization. IEEE Trans. on
Image Processing. to appear.
[8] Gabay, D. and Mercier, B. (1976). A dual algorithm for the solution of nonlinear variational problems via finite element approximation.
Computers and Mathematics with Applications, 2(1):17–40.
[9] Globerson, A. and Jaakkola, T. (2008). Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. NIPS, 20.
[10] Glowinski, R. (1984). Numerical methods for nonlinear variational problems. Springer-Verlag.
[11] Glowinski, R. and Marroco, A. (1975). Sur l’approximation, par elements finis dordre un, et la resolution, par penalisation-dualite dune
classe de problemes de Dirichlet non lineares. Revue Française dAutomatique, Informatique et Recherche Opérationelle, 9:41–76.
[12] Goldfarb, D., Ma, S., and Scheinberg, K. (2010). Fast alternating linearization methods for minimizing the sum of two convex functions.
Technical Report 10-02, UCLA CAM.
[13] Hestenes, M. (1969). Multiplier and gradient methods. Jour. Optim. Theory and Applic., 4:302–320.
[14] Jojic, V., Gould, S., and Koller, D. (2010). Accelerated dual decomposition for MAP inference. In Proc. of ICML.
[15] Kolmogorov, V. and Wainwright, M. (2005). On the optimality of tree-reweighted max-product message passing. In UAI, volume 21.
Citeseer.
[16] Komodakis, N. and Paragios, N. (2009). Beyond pairwise energies: Efficient optimization for higher-order MRFs. In Proc. of CVPR
2009, pages 2985–2992.
[17] Komodakis, N., Paragios, N., and Tziritas, G. (2007). MRF optimization via dual decomposition: Message-passing revisited. In
International Conference on Computer Vision. Citeseer.
[18] Koo, T., Rush, A. M., Collins, M., Jaakkola, T., and Sontag, D. (2010). Dual decomposition for parsing with non-projective head
automata. In Proc. of EMNLP.
[19] Martins, A. F. T., Smith, N. A., Xing, E. P., Figueiredo, M. A. T., and Aguiar, P. M. Q. (2010). Turbo parsers: Dependency parsing by
approximate variational inference. In Proc. of EMNLP.
[20] Meshi, O., Sontag, D., Jaakkola, T., and Globerson, A. (2010). Learning Efficiently with Approximate Inference via Dual Losses. In
Proc. ICML. Citeseer.
[21] Powel, M. (2009). A method for nonlinear constraints in minimization problems. In Fletcher, R., editor, Optimization, pages 283–298.
Academic Press.
[22] Ravikumar, P., Agarwal, A., and Wainwright, M. (2010). Message-passing for graph-structured linear programs: Proximal methods androunding schemes. JMLR, 11:1043–1080.
[23] Richardson, T. and Urbanke, R. (2008). Modern coding theory. Cambridge Univ Pr.
[24] Rush, A. M., Sontag, D., Collins, M., and Jaakkola, T. (2010). On dual decomposition and linear programming relaxations for natural
language processing. In Proc. of EMNLP.
[25] Smith, D. A. and Eisner, J. (2008). Dependency parsing by belief propagation. In Proc. of EMNLP.
[26] Tarlow, D., Givoni, I. E., and Zemel, R. S. (2010). HOP-MAP: Efficient message passing with high order potentials. In Proc. of AISTATS.
[27] Wainwright, M. J. and Jordan, M. I. (2008). Graphical Models, Exponential Families, and Variational Inference. Now Publishers.

6