  In this work we provide a theoretical framework for structured prediction
that generalizes the existing theory of surrogate methods for binary and
multiclass classification based on estimating conditional probabilities with
smooth convex surrogates (e.g. logistic regression). The theory relies on a
natural characterization of structural properties of the task loss and allows
to derive statistical guarantees for many widely used methods in the context of
multilabeling, ranking, ordinal regression and graph matching. In particular,
we characterize the smooth convex surrogates compatible with a given task loss
in terms of a suitable Bregman divergence composed with a link function. This
allows to derive tight bounds for the calibration function and to obtain novel
results on existing surrogate frameworks for structured prediction such as
conditional random fields and quadratic surrogates.
