Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The target loss in multi-class classification problems is usually the 0/1 loss, while the learning algorithms usually optimize with respect to surrogate losses. The work provided a comprehensive study of how well an optimization problem with respect to surrogate losses represents the results using the target loss in multi-class classification problems. The work considered the max loss, the sum loss, and the constrained loss, and provide the corresponding bounds or negative results.
strengths_and_weaknesses: The paper is well presented. The basis of the results (Theorem 1 - Theorem 5) is a generalization of the results in Awasthi et al. (2022) from binary classification to multi-class classification. However, since loss functions used in binary classification and multi-class classification are different, most of the results in the following sections are new. The work provided a systematic and comprehensive study of surrogate losses in multi-class classification problems, which can most likely lead the community to a better understanding of the use of different surrogate losses under different problem settings.
questions: For the negative result in Theorem 6, it is not yet clear to me whether the problem comes from using convex \Phi or having a h giving equal scores. Will the problem be solved if one removes such h in the hypothesis class?

How can one estimate the bounds? Can the results indicate which surrogate loss is a better choice for a given hypothesis set H?

Figure 1 showed \rho-margin loss but didn’t specify the value of \rho in the figure.

L175, L187: any distribution “D”
limitations: The reviewer has not yet seen the potential negative societal impact of the work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work is interested in deriving theoretical guarantees on the generalization error for the 0-1 loss in a multi-class setting when the learner minimize a surrogate loss like the hinge loss. This problem has already been widely studied in the literature with notions like Bayes-consistency or H-consistency. However, the authors argue that all the previous notions either hold only for the full family of measurable functions and/or are asymptotic. In contrast, this work aims at deriving non-asymptotic guarantees of consistency for a specific set H called H-consistency bounds. A previous paper have investigated the case of binary classification. This paper shows similar results for the multi-class setting also proving negative results when such extensions were not possible.
strengths_and_weaknesses: The main contribution of the paper is to show H-consistency bounds (notion introduced in a previous paper) in the multi-class setting. Four surrogates are studied. The results are summarized in the three tables of the paper.
The paper is well written and the mathematical statements are clear and precise.
Nevertheless, I found the paper hard to follow. This may be due to my lack of familiarity with this kind of bounds.
The paper may benefit from moving some of the theorems to the appendices (keeping the tables unchanged) and using the remaining space to add more informal explanations, maybe focusing on one result.
The paper is clean but a bit arid in the current state.
I was not able to assess the relevance and the impact of this work.
questions: .
limitations: .
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The aim of this work is to study the H-consistency bounds for multi-class classification. To this end, the authors give a series bounds for surrogate multi-class losses, including max losses, sum losses and constrained loss. Then they extend their results to adversarial setting. Lastly, they prove that no non-trivial H-consistency bound can be given in some cases.
strengths_and_weaknesses: Strength:
1. To my knowledge, this paper is the first work to study multi-class H-consistency.
2. This paper is well-written and easy to follow.
3. The theoretical results and proofs are sound, based on my judgement.

Weakness:
The H-consistency for binary setting has been well studied in [1], which is somewhat similar to this paper in structure. Most results are also generalized from [1]. Besides, some important aspects of [1] are not covered in this paper, e.g. the tightness of the bounds. 


[1] Pranjal Awasthi, et al. "H-Consistency Estimation Error of Surrogate Loss Minimizers." *International Conference on Machine Learning* (2022). 
questions: As mentioned above, I have some concerns about the contribution of this work, so I would appreciate it if the authors can describe the novelty of their proof techniques.
limitations: N/A
review_title: null

Meta-review: metareview: This work studies the generalization error in the multi-class classification setting for the minimizer of the ERM with a surrogate loss. The authors present non-asymptotic guarantees using the concept of H-consistency. The present work extends a previous work which was only considering binary classification. The reviewers have found the contribution important and relevant. They also found that the presentation could be improved (e.g., by better referencing to known proof techniques) to have the paper more accessible to non-expert. I do recommend acceptance and ask the authors to revise the paper accordingly for the camera-ready version. 
confidence: Less certain
Decision: Accept