This work considers the relationship between convex surrogate loss and learning problem such as classification and ranking. The authors prove that this approach is equivalent, in a strong sense, to working with polyhedral (piecewise linear convex) losses, and give a construction of a link function through which L is a consistent surrogate for the loss it embeds. Some examples are presented to verify the theoretical analysis. This is an interesting direction in learning theory, while I have some concerns as follows: 1) What's the motivation of polyhedral losses? The authors should present some real applications and shows its importance, especially for some new learning problems and settings.

Top-$k$ classification is a generalization of multiclass classification used widely in information retrieval, image classification, and other extreme classification settings. Several hinge-like (piecewise-linear) surrogates have been proposed for the problem, yet all are either non-convex or inconsistent. For the proposed hinge-like surrogates that are convex (i.e., polyhedral), we apply the recent embedding framework of Finocchiaro et al. (2019; 2022) to determine the prediction problem for which the surrogate is consistent. These problems can all be interpreted as variants of top-$k$ classification, which may be better aligned with some applications. We leverage this analysis to derive constraints on the conditional label distributions under which these proposed surrogates become consistent for top-$k$. It has been further suggested that every convex hinge-like surrogate must be inconsistent for top-$k$. Yet, we use the same embedding framework to give the first consistent polyhedral surrogate for this problem.