  Deep NLP models benefit from underlying structures in the data---e.g., parse
trees---typically extracted using off-the-shelf parsers. Recent attempts to
jointly learn the latent structure encounter a tradeoff: either make
factorization assumptions that limit expressiveness, or sacrifice end-to-end
differentiability. Using the recently proposed SparseMAP inference, which
retrieves a sparse distribution over latent structures, we propose a novel
approach for end-to-end learning of latent structure predictors jointly with a
downstream predictor. To the best of our knowledge, our method is the first to
enable unrestricted dynamic computation graph construction from the global
latent structure, while maintaining differentiability.
