A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing

1. Introduction

• The decoding problem is to find the highest-scoring structure, but the candidate set typically grows exponentially with input size.Examples include tag sequences, parse trees, and translations.Source: §1 · p. 1
• Dual decomposition separates decoding into subproblems linked by linear agreement constraints, which are incorporated with Lagrange multipliers.Iterative methods such as subgradient optimization minimize the resulting dual objective.Source: §1 · pp. 1–2
• Subgradient algorithms are typically simple and efficient, alternating combinatorial optimization for each subproblem with additive multiplier updates.Each iteration first solves the subproblems, then updates the multipliers.Source: §1 · p. 2
• When the underlying LP relaxation is tight, the method gives an exact solution with an optimality certificate; otherwise, approximate recovery or tightening is possible.The tutorial also describes adding constraints until the relaxation becomes tight.Source: §1 · p. 2
• The tutorial surveys Lagrangian-relaxation and dual-decomposition decoding methods developed for a range of NLP models.Examples include parsing, tagging, machine translation, event extraction, and semantic parsing.Source: §1 · p. 2
• The tutorial treats Lagrangian relaxation with a broader class of combinatorial algorithms than max-product belief propagation, extending inference beyond graphical models.Dual decomposition, which uses two or more combinatorial algorithms, is a special case of Lagrangian relaxation.Source: §1 · pp. 2–3

2. Related Work

• The tutorial surveys relevant work from combinatorial optimization, machine learning, and NLP.It frames the methods described later against contributions from these fields.Source: §2 · p. 3

2.1 Combinatorial Optimization

• Lagrangian relaxation has roots in combinatorial optimization, with direct connections to linear programming relaxations.The passage traces its history to Held and Karp’s traveling-salesman work and relates it to LP decomposition.Source: §2.1 · p. 3

2.2 Belief Propagation, and Linear Programming Relaxations for Inference in MRFs

• For general MRFs, loopy max-product belief propagation is heuristic, while LP-relaxation methods provide stronger guarantees and can certify optimality.Komodakis et al. describe dual decomposition that provably optimizes an LP relaxation using subgradient methods.Source: §2.2 · pp. 3–4

2.3 Combinatorial Algorithms in Belief Propagation

• Combinatorial algorithms have been incorporated into belief-propagation methods, but the tutorial argues that Lagrangian-relaxation methods offer stronger formal guarantees than loopy variants.Prior work used such algorithms for MAP inference and marginal computation.Source: §2.3 · p. 4

2.4 Linear Programs for Decoding in Natural Language Processing

• Prior NLP work used ILP formulations for tasks including sequence labeling, word alignment, and dependency parsing; this tutorial instead aims to exploit problem structure with combinatorial algorithms.The stated aim is to speed decoding relative to using a general-purpose solver.Source: §2.4 · p. 4

3.1 Lagrangian Relaxation

• The score of a structure is represented as a linear function of its feature vector, often a sum of scores for the parts it contains.The tutorial assumes the decoding problem is computationally challenging, whether NP-hard or simply too slow in practice.Source: §3.1 · p. 5
• Lagrangian relaxation replaces a difficult constrained problem with optimization over a larger set, while incorporating the dropped linear constraints through multipliers.The relaxed set is chosen so optimization is easier than over the original feasible structures.Source: §3.1 · p. 5
• Subgradient optimization iteratively finds a structure under multiplier-adjusted scores and updates the multipliers using that structure.The relaxed maximization is efficient because the multiplier terms can be incorporated into the objective.Source: §3.1 · p. 6
• The dual objective upper-bounds the optimal primal score, and suitable step sizes make subgradient iterations converge to the minimum dual value.If an iterate satisfies the original linear constraints, it solves the original optimization problem.Source: §3.1 · pp. 6–7
• Minimizing the dual recovers the optimum of an LP relaxation; when that relaxation is tight, subgradient optimization is guaranteed to recover an exact decoding solution.When the relaxation is not tight, approximate LP recovery or incremental tightening are alternatives.Source: §3.1 · p. 7

3.2 Dual Decomposition

• Dual decomposition optimizes a pair of structures subject to linear constraints, which often encode agreement between the structures.It is a special case of Lagrangian relaxation and uses two or more combinatorial algorithms.Source: §3.2 · p. 8
• Dropping the agreement constraints separates the dual into subproblems that can be solved independently, with multiplier updates coordinating the solutions.The tutorial describes a subgradient algorithm for minimizing the dual objective.Source: §3.2 · p. 9
• The formal framework is broad enough to include the algorithms described in the paper, whose remaining sections address examples, experiments, practical issues, and theory.The two-component formulation generalizes straightforwardly to more components.Source: §3.2 · p. 10

4.1 Definition of the Problem

• Combining WCFG parse scores with finite-state POS-tag scores adds adjacent-tag information, while classical grammar intersection can multiply runtime by T^6 for trigram tagging.The dual-decomposition runtime is O(k(G^3n^3 + T^3n)), compared with O(G^3T^6n^3) for the intersection construction.Source: §4.1 · pp. 12–13

4.2 The Dual Decomposition Algorithm

• Each iteration decodes a parse and tag sequence, updates multipliers for POS disagreements, and returns when their tag sequences agree.The subproblems can be solved efficiently under the stated assumptions; agreement guarantees an optimal solution to the original problem.Source: §4.2 · pp. 15–16
• When few iterations are needed, separate CKY parsing and Viterbi tagging yield an additive tagging cost rather than the intersection method’s multiplicative T^6 cost.For a trigram tagger, the stated dual-decomposition runtime is O(k(G^3n^3 + T^3n)).Source: §4.2 · p. 16

4.3 Relationship of the Approach to Section 3

• The formulation represents parsing and tagging structures as vectors and encodes shared POS tags as linear constraints, placing the example within the dual-decomposition framework.The vectors encode the respective model scores, and the constraints equate their tag indicators.Source: §4.3 · p. 16

4.4 An Example Run of the Algorithm

• Over 99% of examples received exact solutions, and over 94% received one within 10 iterations, in the reported parser–tagger experiments.Figure 3 plots the percentage of examples with exact solutions against the number of iterations.Source: Figure 3 · p. 18, §4.4 · p. 18
• For the illustrated input, the initial parser and tagger hypotheses agree on POS tags, so the algorithm terminates with an optimal solution.The experiments separately show that agreement is not guaranteed on every example, although it is achieved for over 99% in the reported setting.Source: §4.4 · p. 18

5.1 Three Theorems

• Under the stated assumptions, the dual objective can be calculated as two efficiently solvable maximization subproblems.Source: §5.1 · p. 19
• For any multiplier values, the dual objective upper-bounds the optimal score; a small gap to a candidate solution bounds how far that solution is from optimal.Source: §5.1 · p. 20
• With appropriate step sizes, the algorithm converges to the minimum dual value, the tightest upper bound provided by the dual.Source: §5.1 · pp. 20–21
• If the algorithm reaches agreement between the solutions, the resulting solution is optimal for the original problem.Source: §5.1 · pp. 20–21
• Dual convergence means convergence to the minimum dual value, whereas exact convergence means agreement, which the algorithm is not guaranteed to reach.Source: §5.1 · p. 21

5.2 Subgradients

• The dual objective is convex but nondifferentiable, so the method uses subgradients rather than ordinary gradient descent.Source: §5.2 · p. 22
• Subgradient updates use a positive step size and, under suitable step-size conditions, converge to the minimum of the dual objective.Source: §5.2 · p. 22

6.1 Combined Constituency and Dependency Parsing

• Over 99% of examples e-converged, with over 90% converging in 10 iterations or less; parsing accuracy significantly improved over Collins (1997) and a forced-structure baseline.The baseline forces the lexicalized CFG parser to use the dependency parser’s first-best dependency structure.Source: Figure 5 · p. 24, §6.1 · p. 25

6.2 The MAP Problem for Pairwise Markov Random Fields

• For pairwise binary MRF MAP inference, Komodakis et al. (2007, 2011) decompose the graph into trees and use multipliers to enforce agreement between exact tree inferences.When the tree solutions agree, the algorithm is guaranteed to solve the optimization problem; the general method can use more than two trees when a two-tree decomposition is unavailable.Source: §6.2 · pp. 26–27

6.3 The Held and Karp Algorithm for TSPs

• Held and Karp (1971) relax the TSP’s degree-two constraints over 1-trees, using one efficient combinatorial algorithm; satisfying the constraints guarantees a solution.A 1-tree is found by combining a maximum spanning tree on vertices 2 through n with the two highest-scoring edges incident to vertex 1.Source: §6.3 · pp. 28–30

6.4 Phrase-Based Translation

• Chang and Collins (2011) describe a Lagrangian relaxation algorithm for phrase-based translation decoding, whose lexicon pairs source-language sequences with target-language sequences.The section introduces phrases as source spans paired with target strings and assigned model scores.Source: §6.4 · pp. 30–31
• Exact decoding is NP-hard because a direct dynamic program must track which source words have been covered, producing exponentially many states.Source: §6.4 · p. 32
• The relaxation requires only that the total number of translated source words equal n, so dynamic programming tracks a count rather than an exponentially large coverage bit string.Source: §6.4 · p. 32
• Whenever every source word is translated exactly once at an iteration, the solution is guaranteed optimal for the original decoding problem.Source: §6.4 · p. 32
• Subgradient updates penalize words translated more than once and favor untranslated words, steering phrase scores toward translating each source word exactly once.Source: §6.4 · p. 33
• The method recovers exact solutions under a phrase-based translation model and is far more efficient than general-purpose integer linear programming approaches.The described approach also includes a tighter dynamic program and incrementally adds constraints if it does not initially e-converge.Source: §6.4 · p. 33

7. Practical Issues

• The section tracks dual and primal quantities at each iteration and uses their best-so-far values and gap to assess algorithm progress.A recovered primal solution can be useful even when the subproblem solutions disagree.Source: §7 · pp. 33–34, §7.1 · p. 35

7.1 An Example Run of the Algorithm

• The best dual value is a decreasing upper bound and the best primal value increases; a small gap guarantees a near-optimal primal solution, although raw iterates fluctuate.At e-convergence, the solutions are guaranteed optimal.Source: §7.1 · p. 35

7.2 Choice of the Step Sizes δk

• A fixed step size trades smoothness for speed: small steps converge slowly, while large steps move faster initially but fluctuate erratically.The authors recommend a decreasing step size that shrinks only when the dual value increases.Source: §7.2 · p. 36

7.3 Recovering Approximate Solutions

• When exact convergence fails, one option is to return the best primal solution found after a fixed number of iterations; the best-dual bound limits its possible suboptimality.Tightening the relaxation is another route to an exact solution.Source: §7.3 · pp. 36–37

7.4 Early Stopping

• Early-stopped solutions can quickly approach their final accuracy and often match the eventual primal solution, while lacking its optimality certificate.For combined constituency and dependency parsing, over 95% of cases e-converge in roughly 50 iterations; a second algorithm takes closer to 1,000.Source: §7.4 · p. 38

• TRW-S monotonically improves the dual but may not reach the LP optimum, whereas subgradient optimization is guaranteed to converge to that optimum despite sometimes slower initial progress.TRW-E and TRW-T also lack a guarantee of convergence to the optimal LP value.Source: §8 · p. 38
• TRW-based algorithms can outperform generic LP solvers by exploiting MRF structure, and the tutorial’s Lagrangian relaxation algorithms likewise specialize LP optimization to combinatorial structure.Source: §8 · p. 38
• MPLP can improve dual values quickly but may get stuck suboptimally, and its max-marginal computations can be slower than MAP decoding.For directed spanning-tree models, MAP takes O(n^2), while no max-marginal algorithm better than O(n^4) is known to the authors.Source: §8 · p. 39
• Accelerated subgradient can reduce iteration counts in some experiments but require more iterations in others, and it also requires subproblem marginals.Its stated convergence rate is O(1/ϵ) time to reach an ϵ-close solution.Source: §8 · p. 39
• ADMM guarantees optimization of the LP relaxation and can retain dual-decomposition-style decomposability, but its quadratic penalty may complicate subproblem decoding.Reported experiments found a comparable iteration count to MPLP for finding a good primal solution.Source: §8 · p. 39

9.1 The Linear Programming Relaxation

• The relaxation replaces binary structure-selection variables with distributions over structures, yielding a linear program whose feasible sets are convex hulls of the integral choices.The original optimization is recovered when the variables are restricted to 0/1 values; the relaxed LP allows fractional values.Source: §9.1 · pp. 40–41

9.2 The Dual of the New Optimization Problem

• The LP relaxation’s dual function equals the dual decomposition objective, and the LP optimum equals its minimum, though this need not equal the original problem’s optimum.The subgradient algorithm minimizing L(u) therefore also minimizes the LP dual; unlike the original problem’s dual bound, the LP dual achieves equality with the relaxed primal optimum.Source: §9.2 · p. 42

9.3 An Example

• The relaxed solution is fractional and scores 2, whereas the original problem’s only constraint-satisfying pair scores 0, revealing a gap between the minimum dual value and optimal primal score.After nine iterations, the subgradient method reaches L(u(9)) = 2.06, close to the optimal dual value, but it does not reach agreement and instead alternates among structures with positive weight in the fractional solution.Source: §9.3 · pp. 44–45

9.4 Fixing E-Convergence: Tightening Approaches

• Adding all tag-bigram consistency constraints makes the LP relaxation integral and guarantees exact convergence, but can require parsing as expensive as exact bigram-HMM/PCFG intersection.Adding only selected constraints can eliminate a fractional solution and restore convergence; selecting a few positions can be more efficient than adding constraints throughout the sentence.Source: §9.4 · pp. 46–47

9.5 Compact Linear Programs

• Compact LPs use polynomial-size descriptions of convex hulls to avoid the exponentially many structure variables, making LP solvers practical for debugging dual decomposition.When the combinatorial algorithm’s feasible-set convex hull has a polynomial-size linear characterization, the resulting LP is polynomial in size.Source: §9.5 · pp. 47–48
• Combinatorial algorithms for the component problems yield explicit representations of a compact LP with polynomial-size matrices; such formulations can be solved by generic LP solvers and help debug decomposition algorithms.Source: §9.5 · p. 49, §9.6 · p. 49

9.6 Summary

• The function L(u) is the dual of a linear-programming relaxation of the original problem.Source: §9.6 · p. 49
• The subgradient method d-converges to min_u L(u) even when the optimal LP solution is fractional, but its primal solutions can alternate without satisfying y(i, t) = z(i, t).Source: §9.6 · p. 49
• Tightening can improve convergence by selectively adding constraints, often those frequently violated, at the cost of greater complexity in finding y(k) and/or z(k).Source: §9.6 · p. 49

10. Conclusions

• Experiments on several NLP problems show that LR methods are often considerably more efficient than existing exact methods and have stronger formal guarantees than approximate search methods.The conclusion does not specify individual tasks or numerical results.Source: §10 · p. 50
• LR combines combinatorial algorithms with linear constraints introduced through Lagrange multipliers, then iteratively minimizes the resulting dual objective.The described algorithms typically repeat the underlying combinatorial algorithm and make simple additive multiplier updates.Source: §10 · p. 50
• The dual objective provides an upper bound, and when the method produces an exact solution, it can provide a certificate of optimality.The conclusion also notes close connections to linear programming relaxations.Source: §10 · p. 50

Appendix A. Proofs

• The appendix develops results for the combined parsing and tagging problem using its Lagrangian and dual objective.It identifies n as the sentence length and T as the finite set of part-of-speech tags.Source: Appendix A · p. 50
• The appendix proves that L(u) is convex and derives an expression for its subgradients.Source: Appendix A · p. 50
• It gives a convergence theorem for the subgradient algorithm that minimizes L(u) and proves Theorem 6.Source: Appendix A · p. 50

A.1 Proof of Convexity of L(u)

• The subsection introduces Theorem 9 as the result to establish.Source: §A.1 · pp. 50–51
• Theorem 9 states that L(u) is convex.Source: §A.1 · p. 51
• The proof develops the convexity claim through intermediate relations and a final equality involving a convex combination of L values.Source: §A.1 · p. 51

A.2 Subgradients of L(u)

• The section states that γ(u) is a subgradient of L(u) under the stated index conditions.The supplied passage specifies indices i ∈ {1 . . . n} and t ∈ T.Source: §A.2 · p. 52
• The theorem is presented as a special case of a result for maxima of affine functions with coefficient vectors a_i and offsets b_i.The proof passages use the active affine term a_j · u + b_j to establish the claim.Source: §A.2 · p. 52
• When a_j · u + b_j attains the maximum at u, a_j is a subgradient of L at u.The proof establishes the subgradient inequality for every v by comparing the active affine function at v with the maximum over all affine functions.Source: §A.2 · p. 52

A.3 Convergence Proof for the Subgradient Method

• The subgradient method updates u by subtracting δ_k times a subgradient g_k at each iteration.The method initializes u at u(0); δ_k > 0 is the step size at iteration k.Source: §A.3 · p. 52
• Theorem 11 assumes ||g_k||_2 ≤ G for every iteration, and its proof sums the update-based subgradient inequalities before rearranging them.The theorem is introduced as useful for proving convergence of the method.Source: §A.3 · pp. 52–53
• With constant step size h, the limiting value is within Gh/2 of the optimal solution.The convergence discussion also introduces a result under positive step sizes tending to zero, with an additional condition whose full statement is not included in the supplied passage.Source: §A.3 · p. 53

A.4 Proof of Theorem 6

• The proof organizes its construction around two cases for the target claim.The supplied passages introduce the target and then explicitly transition from the first case to the second.Source: §A.4 · p. 54
• In the first case, the proof selects y* and sets α_y* = 1 and α_y = 0 for every other y.It then says this setting satisfies the target condition.Source: §A.4 · p. 54
• In the second case, the proof first selects a setting α* and then chooses a member y* of Y.The following passages say the construction is verified and yields the target condition.Source: §A.4 · p. 54