An Embedding Framework for Consistent Polyhedral Surrogates
This provides a theoretical foundation for constructing consistent surrogate losses in machine learning, addressing a core problem in optimization for practitioners, though it is incremental in extending polyhedral surrogate theory.
The paper formalizes an embedding framework for designing convex surrogate loss functions in tasks like classification and ranking, showing that any polyhedral loss can be linked to a consistent surrogate for its embedded discrete loss, and vice versa, with proofs for consistency or inconsistency of existing 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 $\mathbb{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. Given any polyhedral loss $L$, we give a construction of a link function through which $L$ is a consistent surrogate for the loss it embeds. Conversely, we show how to construct a consistent polyhedral surrogate for any given discrete loss. Our framework yields succinct proofs of consistency or inconsistency of various polyhedral surrogates in the literature, and for inconsistent surrogates, it further reveals the discrete losses for which these surrogates are consistent. We show some 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.