An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates
We formalize and study the natural approach of designing convex surrogate
loss functions via embeddings, for problems such as classification, ranking, or
structured prediction. In this approach, one embeds each of the finitely many
predictions (e.g. rankings) as a point in $R^d$, assigns the original loss
values to these points, and "convexifies" the loss in some way to obtain a
surrogate. We establish a strong connection between this approach and
polyhedral (piecewise-linear convex) surrogate losses: every discrete loss is
embedded by some polyhedral loss, and every polyhedral loss embeds some
discrete loss. Moreover, an embedding gives rise to a consistent link function
as well as linear surrogate regret bounds. Our results are constructive, as we
illustrate with several examples. In particular, our framework gives succinct
proofs of consistency or inconsistency for various polyhedral surrogates in the
literature, and for inconsistent surrogates, it further reveals the discrete
losses for which these surrogates are consistent. We go on to show additional
structure of embeddings, such as the equivalence of embedding and matching
Bayes risks, and the equivalence of various notions of non-redudancy. Using
these results, we establish that indirect elicitation, a necessary condition
for consistency, is also sufficient when working with polyhedral surrogates.