  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.
