Structured prediction requires manipulating a large number of combinatorialstructures, e.g., dependency trees or alignments, either as latent or outputvariables. Recently, the SparseMAP method has been proposed as adifferentiable, sparse alternative to maximum a posteriori (MAP) and marginalinference. SparseMAP returns a combination of a small number of structures, adesirable property in some downstream applications. However, SparseMAP requiresa tractable MAP inference oracle. This excludes, e.g., loopy graphical modelsor factor graphs with logic constraints, which generally require approximateinference. In this paper, we introduce LP-SparseMAP, an extension of SparseMAPthat addresses this limitation via a local polytope relaxation. LP-SparseMAPuses the flexible and powerful domain specific language of factor graphs fordefining and backpropagating through arbitrary hidden structure, supportingcoarse decompositions, hard logic constraints, and higher-order correlations.We derive the forward and backward algorithms needed for using LP-SparseMAP asa hidden or output layer. Experiments in three structured prediction tasks showbenefits compared to SparseMAP and Structured SVM.