Inferring structured predictions based on correlated covariates remains a central problem in many fields, including NLP, computer vision, and computational biology. Popular paradigms for training stru