SparseMAP: Differentiable Sparse Structured Inference

1. Introduction

• SparseMAP represents structured predictions as sparse combinations of a small number of often-overlapping global structures, between single-structure MAP and dense marginal inference.It extends sparsemax to structured inference and is a continuous yet sparse relaxation of MAP.Source: §1 · p. 2
• SparseMAP can be computed using a MAP solver as a subroutine, including for problems such as linear assignment where marginal inference is intractable.The method uses the problem’s sparsity and quadratic curvature.Source: §1 · p. 2
• Its general backward pass is differentiable almost everywhere and efficient through solution sparsity and reuse of forward-pass quantities.The expressions apply to any type of structure.Source: §1 · p. 2
• The SparseMAP loss extends the CRF and structured SVM losses, with efficient loss and gradient computation when MAP inference is available.The loss inherits desirable properties of SparseMAP inference.Source: §1 · p. 2
• Experiments report more accurate dependency parsers with sparse, interpretable predictions that adapt to ambiguity, and natural-language-inference models with good predictive performance and visualizations concentrated on few structures.The dependency parsing predictions adapt to the ambiguity, or lack thereof, of test examples.Source: §1 · p. 2

2.1. Regularized Max Operators: Softmax, Sparsemax

• Sparsemax replaces softmax’s entropy penalty with a squared ℓ2 penalty, producing sparse outputs through projection onto the simplex.Softmax is continuous and differentiable but dense; sparsemax is also continuous and differentiable almost everywhere.Source: §2.1 · p. 2

2.2. Structured Inference

• Structured problems have combinatorially many possible outputs, so scores are parameterized as θ := A⊤η, with η lower-dimensional than the structure space.A specifies the problem structure, and k ≪ D.Source: §2.2 · pp. 2–3
• MAP optimizes over the marginal polytope’s structure vertices, but its piecewise-constant output is discontinuous.The polytope has one vertex for each possible structure.Source: §2.2 · p. 3
• Marginal inference is differentiable, but its entropy term lacks a closed form, computation may be difficult, and backpropagation is limited to specialized instances.The entropy regularizer favors dense distributions.Source: §2.2 · p. 3
• Sequence tagging uses joint tag assignments as structures, with Viterbi for MAP inference and forward-backward for marginal inference.The structure also encodes transitions between consecutive tags.Source: §2.2 · p. 3
• Non-projective dependency parsing represents structures as rooted spanning trees; linear assignment uses permutations, whose marginal inference is #P-complete.Parsing supports MAP inference with maximal-arborescence algorithms and marginal inference via the Matrix-Tree theorem; assignment MAP can use Hungarian or Jonker–Volgenant algorithms.Source: §2.2 · p. 3

3.1. Definition

• SparseMAP regularizes MAP inference with a squared ℓ2 penalty, favoring sparse solutions on faces of the marginal polytope while ensuring a unique solution.Its solutions can be sparse combinations of sequence labelings, parse trees, or matchings.Source: §3.1 · pp. 3–4

3.2. Solving SparseMAP

• SparseMAP solvers avoid enumerating the exponentially many vertices by using sequences of MAP problems, including conditional-gradient and active-set methods.The active-set method updates the estimated support and solves a restricted quadratic program at each iteration.Source: §3.2 · p. 4
• The active-set solver substantially outperforms conditional-gradient variants in objective value and sparsity, so the paper uses it for the remaining experiments.The solver comparison uses random potentials on a dependency-parsing instance; the figure reports a 20-node tree factor.Source: §3.2 · p. 4, Figure 2 · p. 4

3.3. Backpropagating Gradients through SparseMAP

• SparseMAP is differentiable almost everywhere, and its backward pass costs O(k|I|) by using only active structures and quantities available from the forward pass.The gradient approach is structure-independent and derives its efficiency from solution sparsity.Source: §3.3 · p. 5

4. Structured Fenchel-Young Losses and the SparseMAP Loss

• Fenchel–Young losses are defined from a convex penalty and a structure-encoding matrix, and include commonly used structured losses.The family is named after the corresponding Fenchel–Young duality gap.Source: §4 · p. 5
• Choosing a quadratic penalty in the Fenchel–Young loss construction gives SparseMAP losses, whose subgradients can be computed through SparseMAP inference using MAP calls.The stated penalty choices include SparseMAP and margin SparseMAP.Source: §4 · p. 5
• SparseMAP and margin SparseMAP produce the best parser on 4/5 datasets in the reported unlabeled attachment accuracy comparison.The comparison uses a bi-LSTM parser and includes the CoNLL 2017 UDPipe baseline trained under the same conditions.Source: Table 1 · p. 6
• For strongly convex penalties, the loss is a smoothed perceptron loss, and its penalty strength can be adjusted by scaling the scores.The passage also states that minimizing the loss aligns models with the true label.Source: §4 · p. 6

5.1. Dependency Parsing with the SparseMAP Loss

• Test-set results indicate that SparseMAP losses outperform SVM and CRF losses on 4 out of the 5 languages considered, suggesting SparseMAP is a good middle ground between MAP-based and marginal-based losses in smoothness and gradient sparsity.Source: §5.1 · p. 6
• SparseMAP solutions converge toward sparse parses, often exposing genuine linguistic ambiguities and retaining the gold parse even when it is not highest-scoring.When examples are confident, SparseMAP can return a single tree; unlike K-best heuristics, its output sparsity adjusts dynamically.Source: §5.1 · p. 6, Figure 3 · p. 7

5.2. Latent Structured Alignment for Natural Language Inference

• Sequential alignment models continuity and monotonicity through binned transitions, while matching alignment averages a few maximal matchings without extra learned parameters.The matching approach uses the Hungarian algorithm; sequential alignment requires learning 18 additional scalar parameters.Source: §5.2 · p. 7
• Structured alignments are competitive with softmax in accuracy and orders of magnitude sparser, yielding interpretable global alignment structures.Table 2 reports test accuracy and the percentage of word pairs with nonzero alignment scores.Source: Table 2 · p. 6, §5.2 · p. 7
• Latent-structure models take roughly the same training and validation time as softmax and become faster as models grow more certain.This comparison holds despite the overhead of GPU memory copying.Source: §5.2 · p. 7

• Structured attention methods use tractable marginal inference and specialized backward passes, whereas SparseMAP uses MAP inference and a modular backward pass.SparseMAP also produces sparse solutions with statistical, computational, and visual appeal.Source: §6 · p. 8
• Unlike K-best inference, SparseMAP is convex, differentiable, modular, and returns a distribution that reveals gaps between selected structures.K-best inference can be roughly K times slower than MAP inference.Source: §6 · p. 8
• Mean-entropic optimal-transport relaxations do not apply to general structures or directly express solutions as combinations of a few permutations.Source: §6 · p. 8
• Earlier ℓ2 regularization work targets LP-MAP approximate inference, not sparse structured prediction; further connections remain open for exploration.The passage notes that some formulations share properties with SparseMAP.Source: §6 · p. 8

• SparseMAP provides a sparse structured-inference framework and corresponding loss, with efficient forward and backward computation.Source: §7 · p. 8
• Experiments show sparse, interpretable predictions for structured prediction and strong, interpretable networks for structured hidden layers.The conclusion identifies local ambiguities as a good fit for SparseMAP’s structured-prediction use case.Source: §7 · p. 8
• Because it is modular and requires MAP inference, SparseMAP can be applied to structured problems including linear assignment.Source: §7 · p. 8

A.1. Conditional Gradient Variants

• Conditional-gradient variants use MAP inference for the linear minimization step and combine direction selection, gap checks, and line search.The appendix covers vanilla, pairwise, and away-step variants.Source: §A.1 · pp. 11–12

A.2. The Active Set Algorithm

• The active-set algorithm solves a relaxed SparseMAP quadratic program restricted to the current active set and adds structures when the MAP-based gap test fails.Source: §A.2 · pp. 12–13
• Its design matrix changes by one row and column at a time, allowing its inverse or decomposition to be maintained and updated efficiently.A feasible line search updates toward the relaxed solution; when the step size is at most 1, it zeros a coordinate.Source: §A.2 · p. 12

B. Computing the SparseMAP Jacobian: Proof of Proposition 1

• The proof begins from SparseMAP’s definition as the optimizer of the quadratic program in Equation 5.This supplies the optimization problem whose solution the Jacobian derivation analyzes.Source: B. Computing the SparseMAP Jacobian:… · p. 13
• Strong convexity of the 2-norm term gives a unique SparseMAP minimizer, and smoothness of the conjugate makes SparseMAP Lipschitz-continuous and differentiable almost everywhere.The proof identifies the unique minimizer as the reason SparseMAP is well-defined.Source: B. Computing the SparseMAP Jacobian:… · p. 13
• The proof rewrites the quadratic program using a convex combination of marginal-polytope vertices, then uses KKT conditions to relate the solution to x.It defines the active support as the configurations with positive y⋆ entries and derives an expression using that support.Source: B. Computing the SparseMAP Jacobian:… · pp. 13–14
• When the support is locally constant, differentiating with respect to a configuration score gives the Jacobian expression in (20; support changes occur only on a measure-zero set.At support changes, the proof describes SparseMAP as subdifferentiable and the assumption as yielding a generalized Jacobian.Source: B. Computing the SparseMAP Jacobian:… · p. 14

C. Fenchel-Young Losses: Proof of Proposition 2

• The restriction of a convex function to the convex set △ is convex, a fact used in the loss proof.The passage cites Boyd & Vandenberghe (2004, Section 3.1.2).Source: C. Fenchel-Young Losses: Proof of… · p. 14
• Property 1 is proved using the Fenchel–Young inequality and the condition that y belongs to △d.The proof cites Fenchel (1949) and Boyd & Vandenberghe (2004, Sections 3.3.2).Source: C. Fenchel-Young Losses: Proof of… · p. 14
• For fixed y, the proof rewrites the loss and uses convexity of a convex conjugate, linear functions, their sum, and composition with a linear function to establish convexity of ℓΩ,A in η.Convexity in y is described as straightforward because the loss is the sum of a convex and a linear function (Boyd & Vandenberghe, 2004, Sections 3.2.1, 3.2.2, 3.3.1).Source: C. Fenchel-Young Losses: Proof of… · p. 14
• The proof derives Property 3 from the scaling property of the convex conjugate.The cited reference is Boyd & Vandenberghe (2004, Section 3.3.2).Source: C. Fenchel-Young Losses: Proof of… · p. 14