# LP-SparseMAP: Differentiable Relaxed Optimization for Sparse Structured Prediction

arXiv: https://arxiv.org/abs/2001.04437 · HTML: https://mlsanity.com/paper/2001.04437/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2020.

## Built on by (most cited first, 17 of 17)

- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [Can Rationalization Improve Robustness?](https://mlsanity.com/paper/2204.11790/) (2022)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [SPECTRA: Sparse Structured Text Rationalization](https://mlsanity.com/paper/2109.04552/) (2021)
- [On the Impact of Temporal Concept Drift on Model Explanations](https://mlsanity.com/paper/2210.09197/) (2022)
- [Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.04862/) (2022)
- [Improved Latent Tree Induction with Distant Supervision via Span Constraints](https://mlsanity.com/paper/2109.05112/) (2021)
- [Think Rationally about What You See: Continuous Rationale Extraction for Relation Extraction](https://mlsanity.com/paper/2305.03503/) (2023)
- [Give Me More Details: Improving Fact-Checking with Latent Retrieval](https://mlsanity.com/paper/2305.16128/) (2023)
- [Learning with Latent Structures in Natural Language Processing: A Survey](https://mlsanity.com/paper/2201.00490/) (2022)
- [Learning Discrete Structured Variational Auto-Encoder using Natural Evolution Strategies](https://mlsanity.com/paper/2205.01324/) (2022)
- [Efficient Learning of Discrete-Continuous Computation Graphs](https://mlsanity.com/paper/2307.14193/) (2023)
- [Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inference](https://mlsanity.com/paper/2204.03619/) (2022)
- [Differentiable Knapsack and Top-k Operators via Dynamic Programming](https://mlsanity.com/paper/2601.21775/) (2026)
- [Transferring Neural Potentials For High Order Dependency Parsing](https://mlsanity.com/paper/2306.10469/) (2023)
- [Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives](https://mlsanity.com/paper/2508.20978/) (2025)

## Abstract (arXiv)

Structured prediction requires manipulating a large number of combinatorial structures, e.g., dependency trees or alignments, either as latent or output variables. Recently, the SparseMAP method has been proposed as a differentiable, sparse alternative to maximum a posteriori (MAP) and marginal inference. SparseMAP returns a combination of a small number of structures, a desirable property in some downstream applications. However, SparseMAP requires a tractable MAP inference oracle. This excludes, e.g., loopy graphical models or factor graphs with logic constraints, which generally require approximate inference. In this paper, we introduce LP-SparseMAP, an extension of SparseMAP that addresses this limitation via a local polytope relaxation. LP-SparseMAP uses the flexible and powerful domain specific language of factor graphs for defining and backpropagating through arbitrary hidden structure, supporting coarse decompositions, hard logic constraints, and higher-order correlations. We derive the forward and backward algorithms needed for using LP-SparseMAP as a hidden or output layer. Experiments in three structured prediction tasks show benefits compared to SparseMAP and Structured SVM.