Structured Prediction with Projection Oracles
  We propose in this paper a general framework for deriving loss functions for
structured prediction. In our framework, the user chooses a convex set
including the output space and provides an oracle for projecting onto that set.
Given that oracle, our framework automatically generates a corresponding convex
and smooth loss function. As we show, adding a projection as output layer
provably makes the loss smaller. We identify the marginal polytope, the output
space's convex hull, as the best convex set on which to project. However,
because the projection onto the marginal polytope can sometimes be expensive to
compute, we allow to use any convex superset instead, with potentially
cheaper-to-compute projection. Since efficient projection algorithms are
available for numerous convex sets, this allows us to construct loss functions
for a variety of tasks. On the theoretical side, when combined with calibrated
decoding, we prove that our loss functions can be used as a consistent
surrogate for a (potentially non-convex) target loss function of interest. We
demonstrate our losses on label ranking, ordinal regression and multilabel
classification, confirming the improved accuracy enabled by projections.
