Multi-Class $H$-Consistency Bounds
Authors: Pranjal Awasthi
Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-class classification
consistency
surrogate losses
adversarial learning

Abstract: We present an extensive study of $H$-consistency bounds for multi-class classification. These are upper bounds on the target loss estimation error of a predictor in a hypothesis set $H$, expressed in terms of the surrogate loss estimation error of that predictor. They are stronger and more significant guarantees than Bayes-consistency, $H$-calibration or $H$-consistency, and more informative than excess error bounds derived for $H$ being the family of all measurable functions. We give a series of new $H$-consistency bounds for surrogate multi-class losses, including max losses, sum losses, and constrained losses, both in the non-adversarial and adversarial cases, and for different differentiable or convex auxiliary functions used. We also prove that no non-trivial $H$-consistency bound can be given in some cases. To our knowledge, these are the first $H$-consistency bounds proven for the multi-class setting. Our proof techniques are also novel and likely to be useful in the analysis of other such guarantees.

Multi-Class H- H--onnsitenccy Bounds
Pranjal Awasthi Google Research
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims nyu. edu
New York, NY 10011 pranjalannsthhiooogge... com
Mehryar Mohri
Yutao Zhong Courant Institute
Google Research Courant Institute New York, NY 10011
New York, NY 10012 yutaoêcims myy nyu..du.. edu
mobri@google.com
Abstract
We present extensive study of H--consistency bounds for multi-class classifi- cation. These are upper bounds on the target loss estimation error predictor in hypothesis set H, expressed in terms of the surrogate loss estimation enror of that predictor. They are stronger and more significant guarantees than Bayes- consistency, K-calibration H-consistency, and more informative than excess error bounds derived for H being the family of all measurable functions. We give series of new K-consistency bounds for surrogate multi-class losses, including max losses, sum losses, and constrained losses, both in the non-adversarial and adversarial cases, and for different differentiable or convex auxiliary functions used. We also prove that no non-try con-trivial H- H--oonistenccy bound can be given in some cases. To our knowledge, these are the first H-consistency bounds proven for the multi-class setting. Our proof techniques are also novel and likely to be useful in the analysis of other such guarantees.
Introduction
The loss functions optimized by learning algorithms are often distinct from the original one specified for a task. This is typically because optimizing the original loss computationally intractable or because it does not admit some favorable properties of differentiability or smoothness. As an example, the loss function minimized by the support vector machine (SVM) algorithm is the hinge loss (Cortes and Vapnik, 1995) the one associated AdaBoost is the exponential loss (Schapire and Freund, 2012), both distinct from the binary classification loss used as a benchmark in applications. But, what learning guarantees can we rely on when using surrogate loss? This is fundamental question in learning theory that directly relates to the design of algorithms.
The standard property of losses (Zhang, 2004a,b; Bartlett, Jordan, and McAuliffe, 2006; Tewari and Bartlett, 2007; Steinwart, 2007), does not supply a sufficient guarantee, since it only ensures that, asymptotically, near optimal minimizers of the surrogate excess loss nearly optimally minimize the target excess error. Moreover, this asymptotic property only holds for the full family of measurable functions, which of course is distinct from the more restricted hypothesis set used by learning algorithm. In fact, it has been shown by Long and Servedio (2013) 3), both theoretically and empirically, that for some hypothesis sets and distributions, the expected error of an algorithm minimizing Bayes-consistent loss bounded below by positive constant, while that of algorithm minimizing inconsistent loss goes to zero.
which has been shown to hold for several surrogate
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

This suggests that a hypothesis set-dependent notion of J[-consistency is more pertinent to the study of consistency for learning (Long and Servedio, 2013), which has been used by Kuznetsov al. (2014); Cortes et al. (2016a,b) and Zhang and Agarwal (2020) and more generally by Awasthi, Frank, Mao, Mohri, and Zhong (2021a) an extensive study of both binary classification and adversarial binary classification losses, as defined in (Goodfellow et al., 2014; Madry et al., 2017; Tsipras et al., 2018; Carlini and Wagner, 2017). Nevertheless, H-conssstency remains an asymptotic property and does not provide guarantees for approximate surrogate loss minimizers that rely on finite samples.
Awasthi, Mao, Mohri, and Zhong (2022a) recently presented a series of results providing H(- consistency bounds in binary classification. These are upper bounds on the target loss estimation error of a predictor that predictor. These guarantees are significantly stronger than the H-calibration or J[-consistency properties studied by Awasthi et al. (2021b,c). They are also more informative than similar excess error bounds derived in the literature, which correspond to the special case where H. is the family of all measurable functions (Zhang. 2004a; Bartlett et al., 2006; Mohri et al., 2018). Combining H-consistencyy bounds with existing surrogate loss estimation bounds directly yields finite sample bounds on the estimation error for the original loss. See Appendix for a more detailed discussion.
hypothesis set H, expressed in terms of the surrogate loss estimation error of
This paper presents an extensive study of H--consistency bounds for multi-class classification. We show in Section 4.1 that, in general, no non-trivial H-consistency bounds can be derived for multi- class max losses such as those of Crammer and Singer (2001), when used with convex loss auxiliary function such as the hinge loss. On the positive side, we prove multi-class JC-consistnccy bounds for max losses under realizability assumption and give multi-class H-cconistency bounds using as an auxiliary function the p- m-margin loss, without requiring a realizability assumption. For sum losses, that is multi-elass losses such as that of Weston and Watkins (1998), we give series of results, including a negative result when using as auxiliary function the hinge-loss, and H-ccossitenccy bounds when using the exponential loss, the squared hinge-loss, and the p-margin loss (Section 4.2). We also present a series of results for the so-called constrained losses, such as the loss function adopted by Lee et al. (2004) in the analysis of multi-class SVM. Here, we prove multi-class H-coossitency bounds when using as an auxiliary function the hinge-loss, the squared hinge-loss, the exponential loss, and the p-margin loss (Section 4.3). We further give multi-class adversarial H-consistency bounds for all three of the general multi-class losses just mentioned (max losses, sum losses and constrained losses) in Section 5.
We are not aware of any prior H-consistency bound derived in the multi-class setting, even in the special case of H. being the family of all measurable functions, whether in the non-adversarial or adversarial setting. All of our results are novel, including our proof techniques. Our results are given for the hypothesis set H. being the family of all measurable functions, the family of linear functions, or the family of one-hidden-layer ReLU neural networks. The binary classification results of Awasthi et al. (2022a) do not readily extend to the multi-class setting since the study of calibration and conditional risk is more complex, the form of the surrogate losses is more diverse, and in general the analysis is more involved and requires entirely novel proof techniques in the multi-class setting (see Section for more detailed discussion of this point).
We give a detailed discussion of related work in Appendix A. We start with the introduction of several multi-class definitions, as well as key concepts and definitions related to the study of JFCcoonssttnccy bounds (Section 2).
2 Preliminaries
We consider the familiar multi-class classification scenario with c 2 classes. We denote by X the input space and by y {l...., c} the set of classes or categories. Let H be a hypothesis set of functions mapping from X x y to IR. The label h(x) associated by a hypothesis E H to x E X is the one with the largest score: h(x) argmnaxyey h(x, v) with an arbitrary but fixed deterministic strategy used for breaking ties. For simplicity, we fix that strategy to be the one selecting the label with the highest index under the natural ordering of labels. See Appendix B for more detailed discussion of this choice.
The margin Pa (1 y) of a hypothesis h E H for a labeled example vx e e.X x y is defined by
(1. y) h(x,y) v) max h (x,11) v/),
*/
2

---

that is the difference between the score assigned to (I, 8) and that of the runner-up. Given
distribution D over y and a loss function E: X y + R. the generalization error of a hypothesis h E H. and the minimal generalization error are defined as follows:
E (h) (a.w)-D [((h, x. [
and R2 inf (h)).
helk
The goal in multi-class classification is to select a hypothesis h H with small generalization error with respect to the multi-class 0/1 loss defined, for any E H, by lo-1 (h, [xx))e In the adversarial scenario, the goal is to select hypothesis h E H with small adversarial generalization error defined, for any 7 E (0, 1) and pe [0,+, by Rt, (h) E (x 1l (h, x, y)], where
x,,
I (=).)) = Milffaiile =ll,, p)(x) - -
sup
is the adversarial multi-class 0/1 loss. More generally, the adversarial generalization error and minimal adversarial generalization error for loss function E(h, 2r, y) are defined as follows:
Rg(h)
E (5.31)-1) [[(h, v, v.l]
and R E inf (2()),
heek
where E(h, 1,, 9) = sup=/pu==11pp ((h, x', ,y) is the supremum-based counterpart of E.
For a distribution D over X x y, we define, for any x e X. p(x) (p(x, ((,,,))))..,,.,.. e)), where p(z, 3) D(Y= y/ r) is the conditional probability of y given X zz We can then write the generalization error as R2 (t) = [x[C, by C,( = Eyey p(z, (), x. y). We will denote by P a set of distributions D) over Xx x x and by Paul the set of all such distributions. For convenience, we define Ymax by 1/max arginayey p(x,, y). When there is a tie, we pick the label with the highest index under the natural ordering of labels.
where C, x) is the conditional f-risk defined
The minimal conditional f-risk is denoted by C (x) iinfnem Ce(h,z) x). We also use the following shorthand for the gap A (h Ce( (x)) and call Aee. (h, 11) ae, x (h,x))> the conditional e-regret for L. For convenience, we also define, for any vector T (TI...., ......... Te) in the probability simplex of R. Cz(h, = Eyey Ty (h, x, y), Ci (2, T) = inf Co x, and ACe,or(h, r) Co
x. 7) (x, Thus, we have AC (h, (h, xx,(()))= = AC se x). For any <> 0, we will denote by [t] the e-truncation of t E R defined by tllese. Thus, the conditional e-regret can be rewritten as [Aeg,e (C,,o((h,x)) Il.
For hypothesis set H. and distribution 'D we also define the (e, miiimiiiiiii gap as Mc, Ri Ex[ (x)))()).. that is the difference between the best-in class error and the expectation of the minimal conditional f-risk. This is a key quantity appearing in our bounds that we cannot hope to estimate minimize. Its value only depends the distribution 'D and the hypothesis set H. As an example, when H is the family of all measurable functions, then the minimizability gap for the multi-class 0/1 loss zero for any distribution D.
3 General theorems
The general form of the H-consistency bounds that we are secking for a surrogate loss ε of a target loss & is (h) Ri 35 S f (Rx, (h) - -R; Ri) for all h e H. for some non-decreasing function Rig f. To derive such bounds for surrogate multi-class losses, we draw on the following two general theorems, which show that, under some conditions, the target loss estimation error can be bounded by some functional form of the surrogate loss estimation eπror involving minimizability gaps.
Theorem 1 (Distribution
V-bound). Assume that there exists a convex function V.R. R with (0) 2 0 and 2 0 such that the following holds for all h e K, E X and D P. ([See, x))) AC,, (h, Then, for any hypothesis h E H and any distribution DeP,
V(Ri, (h) oc + Me, s Re, (h) R2, + MM + max (O))()))))))))))))))))))) (()))
Theorem 2 (Distributiio-ddeeedde))
I'-bound). Assume that there exists a concave function T.R. - R and 2 0 such that the following holds for all h e H, x e X and D e P: (h,,), < <TAEe, (c, Then, for any hypothesis h H and any distribution D P.
Reg (h) RE, Je I(Re, (h) Ri oe Me, Meg t
3

---

The theorems show that, to derive such bounds for a specific hypothesis set and a set of distributions, it suffices to verify that for the same hypothesis set and set of distributions, the conditional c-regret for the target loss can be upper bounded with the same functional form of the gap between the conditional risk and minimal conditional risk of the surrogate loss. These results are similar their binary classification counterparts due to Awasthi et al. (2022b). In particular, the conditional E-risk C,(h, x) in our theorems is the multi-class generalization of their binary definition. The proofs are similar and are included in Appendix E for completeness.
For given hypothesis set H., the resulting bounds suggest three key ingredients for the choice of a surrogate loss: (1) the functional form of the H-consistency bound, which is specified by the function or r; (2) the smoothness of the loss and more generally its optimization virtues, as needed for the minimization of Re, (h) R2 (3) and the approximation properties of the surrogate loss function which determine the value of the minimizability gap M,, Our quantitative Hy-connistencyy bounds can help select the most favorable surrogate loss function among surrogate losses with good optimization merits and comparable approximation properties.
In Section 4 and Section 5, we will apply Theorem and Theorem 2 to the analysis of multi-class loss functions and hypothesis sets widely used in practice. Here, we wish to first comment on the novelty of our results and proof techniques. Let emphasize that although the general tools of Theorems 1 and 2 are the multi-class generalization of that in (Awasthi et al., 2022a), the binary classification results of Awasthi al. (2022a) do not readily extend to the multi-class setting. This is true, even in the classical study of Bayes-consistency, where the multi-class setting (Tewari and Bartlett, 2007) does not readily follow the binary case (Bartlett et al., 2006) and required an alternative analysis and new proofs. Note that, additionally, in the multi-class setting, surrogate losses are more diverse: we will distinguish max losses, sum losses, and constrained losses and present an analysis for each loss family with various auxiliary functions for each (see Section 4).
Proof techniques. More specifically, the need for novel proof techniques stems from the following. To use Theorem and Theorem 2, we need to find V and I such that the inequality conditions in these theorems hold. This requires us characterize the conditional risk and the minimal conditional risk of the multi-class zero-one loss function and the corresponding ones for diverse surrogate loss functions in both the non-adversarial and adversarial scenario. Unlike the binary case, such characterization in the multi-class setting is very difficult. For example, for the constrained loss, solving the minimal conditional risk given a hypothesis set is equivalent to solving a c-dimensional constrained optimization problem, which does not admit an analytical expression. In contrast, in the binary case, solving the minimal conditional risk is equivalent to solving a minimization problem for univariate function and the needed function V can be characterized explicitly by the H-estimation error transformation, as shown (Awasthi et al., 2022a). Unfortunately. such binary classification transformation tools cannot be adapted to the multi-class setting. Instead, in our proof for the multi- class setting, we adopt new idea that avoids directly characterizing the explicit expression of the minimal conditional risk.
For example, for the constrained loss, we leverage the condition of (Lee et al., 2004) that the scores sum to zero, and appropriately choose a hypothesis h that differs from h only by its scores for h(z) and Vmax (see Appendix K). Then, we can upper bound the minimal conditional risk by the conditional risk of h without having to derive the closed form expression of the minimal conditional risk. Therefore, the conditional regret of the surrogate loss can be lower bounded by that of the zero-one loss with an appropriate function V. To the best of our knowledge, this proof idea and technique are entirely novel. We believe that they can be used for the analysis of other multi-class surrogate losses. Furthermore, all of our multi-class K-consistency results are new. Likewise, our proofs of the K-consistency bounds for sum losses for the squared hinge loss and exponential loss similarly new technique and idea, and so does the proof for the p-margin loss. Furthermore, also present an analysis of the adversarial scenario (see Section 5), for which the multi-class proofs are also novel. Finally, our bounds in the multi-class setting are more general: for c= 2, we recover the binary classification bounds of (Awasthi et al., 2022a). Thus, our bounds benefit from the same tightness guarantees shown by (Awasthi et al., 2022a). A further analysis of the tightness of our guarantees in the multi-class setting is left to future work.

---

H-coonsisencyy bounds
In this section, discuss JK-consistency bounds in the non-adversarial scenario where the target loss lg is fg-1. the multi-class 0/1 loss. The lemma stated next characterizes the minimal conditional f--1- risk and the corresponding conditional c-regret, which will be helpful for instantiating Theorems and 2 in the non-adversarial scenario. For any X, we will denote, by H(x) the set of labels generated by hypotheses in HC: H(z) (h(x): H..
Lemma 3. For any x X, the minimal conditional 1--i-risk and the conditional e-regret for lo-1 can be expressed as follows:
()))) =[0=)==
max p(x,)) yeH(z)
[AC 1. (h,x)))
max p(r,)) -((,)(())) ycH(a)
The proof of Lemma 3 is given in Appendix F. By Lemma 3, Theorems and can be instantiated as Theorems 4 and 5 in the non-adversarial scenario follows, where KCcoosistencyy bounds provided between the multi-class 0/1 loss and a surrogate loss É.
Theorem 4 (Non-adversarial distribution-depeneee
V V-bound). Assume that there exists convex function V: R. R with (0) 2 0 and 2 0 such that the following holds for all h H, e X and D P:P:
V max p(z, plc,)))-((,,h))) (h, ycH(a)
Then, for any hypothesis h E H and any distribution D E P,, have
(Rroo 1 (h) Rio-1,3 30" Mr, 1.9e) R2(h) R2, Me max (O)),, V(+)).
Theorem 5 (Non-adversarial distribution-dependee r-bound). Assume that there exists con- cave function T.R. R and 2 such that the following holds for all H, x E X and
max p(z, v) p(x,,(2)) p(zxh)))((,, s gcH(z)
sT(Ae,p((h.)))
(3)
Then, for any hypothesis E H and any distribution E P, we have
Rig (h) Ria.. . s ((Re(h)- R + MM,cc) Me, 1.91 +
(4)
In the following, will apply Theorems and study the K-consistency bounds for different families of multi-class losses parameterized by various auxiliary functions, for several general hypothesis sets. It is worth emphasizing that the form of the surrogate losses more diverse in the multi-class setting and each case requires a careful analysis and that the techniques used in the binary case (Awasthi al., 2022a) do not apply and cannot be readily extended our case.
S denote the d-dimensional by-ball with radius r, with p [1, too]. Without loss of generality, in the following, we choose X (1)... Let [o,+ be conjugate indices, that is 1 + = 1. In the following, we will specifically study three families: the family of all measurable functions Han. the family of linear hypotheses
Hypothesis sets. Let (r) {=c Rd |=1,,-r)
Hmm = (x. v) + Wy x w [wyll, W, W,lbyl B).
and that of one- mee-hddeen layer ReLU networks defined by the following, where (.), max(:;0)
HNN = -( (z. (z:0) + Σ U uy.s(wy, x by.))+ + 1 1 s A, www.y/llllll//// s W. (by. / s B)
Multi-class loss families. We will study three broad families of multi-class loss functions: mux losses, sum losses and constrained losses, each parameterized by an auxiliary function & on R. assumed to be non-increasing and non-negative. In particular, we will consider the following
5

---

1.0
Hinge
Squared
0.8
Exporintaa
p-llargin
0.4
Hinge
Squared hinge
p-Margin
0.0
Figure 1: Left: auxiliary functions with p 0.8. Right: H-consistency dependence between fo-1 and Bestad with p 0.8.
common auxiliary functions: the hinge loss Phinge (1) max 1-.1--1) (). the squared hinge loss beg-binge (t) max (0, -- the exponential loss Lexp (t) e- and the p-margin loss p,(t) main(max(O.. (0, 1 - p) 1}. Note that the first three auxiliary functions are convex, while the last one not. Figure shows plots of these auxiliary functions.
We will say that a hypothesis set H is symmetric there exists a family F of functions f mapping from X R such that ([h(x, (,,,1,,)),,;;;, [[(()): f FH 2 2 for any x E X. The hypothesis sets defined above (Hal. Hiin and HNN) are all symmetric. Note that for symmetric hypothesis set H, we have H(x)) y.
H) (I]....)..,,_.()))) fi,... F) and
We will say that a hypothesis set PC is complete if the set scores it generates spans R. that is, [h(zz, y):h E HC} I., for any (z,y) X x y. The hypothesis sets defined above, Hall Hiin and HNN with B +o are all complete.
4.1 Max losses
In this section, we discuss guarantees for max losses, that is loss functions that can be defined by the application of an auxiliary function & to the margin ph (x, as in (Crammer and Singer, 2001):
(x, y) E y, Tm (max((, xr max 4 (,((,,)) h(r,y') (()((r,)))
(5)
Negative results. We first give negative results showing that max losses m x, 8) with convex and non-increasing auxiliary functions & do not admit useful HC-consistnncy bounds for multi-class classification (c > 2). The proof is given in Appendix G.
Theorem 6 (Negative results for convex 4). Assume that e 2. Suppose that & is convex and con-increasing. and H satisfies there exist x and h e H such that (H(x) 2 2 and h(x, y) are equal for all y E y. for non-decreasing function f:R. + IR., the following H-consistency bound holds for any hypothesis e H and any distribution D:
Rio (h) Ria.. 3t S (Romax (h) - Ripmax
(6)
then, f is lower bounded by 2-
The condition on the hypothesis set in Theorem 6 is very general and all symmetric hypothesis sets verify the condition, e.g. Hally Hii and HNN. also worth pointing out that when e 2, that is, in binary classification, Thcorem 6 does not hold. Indeed, Awasthi et al. (2022a) present a series of results providing H-coossstenccy bounds for convex in the binary case. In the proof, we make use of the assumption that e 2 and thus are able to take probability vector p(x) whose dimension is at least three, which is crucial for the proof.
ii) Positive results without distributional assumptions. On the positive side, the max loss with the non-convex auxiliary function &b D admits H JC-consistency bounds.
Theorem 7 (H-connistency bound of mmxx). Suppose that H. is symmetric. Then, for any hypothesis h H and any distribution D.
Regais (h) RRipmax + Mymoa H
Rea (h) Rian o S
-M
min inf supaey en (n,xh(())))
See Appendix for the proof. Theorem is very powerful since only requires K to symmetric. We can use it to derive H-consistency bounds for 4maax with common symmetric hypothesis sets

---

Table 1: H-consistency bounds for 4max with common symmetric hypothesis sets.
Hypothesis H-consisteney bound of Dpax (Corollaries 18, 19 and 20)
Hall
Rio (h) - -R 1 S Rgmaa (h) paus, Kall
Ramax (h) yuaa Pin +Maaaax .Kin
Hiin
Rto (h) R 1.
MMg 16h6
min 1,
Rayax (h) Ri mmax Nx
+M +MMmms, PNN
HNN
Re (h)) - -R -Ro0-1, MNN
min (1 21B
such Han, Hin and HNN, summarized in Table 1. The proofs with corresponding summarized Corollaries 18, 19 and 20 are included in Appendix H. In the proofs, we characterize the term infzex SuPhent (I h(x)) for each hypothesis set.
Note that by Theorem 6, there is no useful K-consistency bound for the max loss with t Phinges P Paq-binge or t Pexp in these cases. However, under the realizability assumption (Definition 8), we will show that such bounds hold.
iif) Positive results with realizable distributions. We consider the H--realizability condition (Long and Servedio, 2013; Kuznetsov al., 2014; Cortes et al., 2016a,b; Zhang and Agarwal, 2020; Awasthi et al., 2021a) which is defined as follows.
Definition 8 (Hf-realizabilitty. A distribution DD over X x y is H-realizaall if it labels points according to a deterministic model in H, i.e., if E H such that P (( (2. y) > 0) = 1.
Theorem 9 (Realizable co-noisity bound of m. Suppose that H is symmetric and complete, and & is non-increasing and satisfies that lim ((t) = 0. Then, for any hypothesis h E H and any H--ralizabll distribution D, we have
Rio-1 (h) - -R I Rgimax (h) Rijuax D6 + M J
(8)
See Appendix G for the proof. Long and Servedio (2013, Theorem 9) show that hinge is realizable K-consistent for any symmetric hypothesis set H. that is closed under scaling. Since for any H realizable distribution, the assumption that H. is closed under scaling implies that H complete and Mgsaas or 0, Theorem 9 also yields quantitative relationship in that case that is stronger than the asymptotic consistency property of that previous work.
4.2 Sum losses
In this section, we discuss guarantees for sum losses, that is loss functions defined via a sum, as in (Weston and Watkins, 1998):
sum (h, (,) = Σ *(h(x, -((,)))))((xx))
y'+y
i) Negative results. We first give a negative result showing that when using as auxiliary function the hinge-loss, the sum loss cannot benefit from any useful K-consistency guarantee. The proof is deferred to Appendix J.
Theorem 10 (Negative results for hinge loss). Assume that e 2. Suppose that H is symmetric and complete. If for non-decreasing function IR, + Ik, the following H-consistencyy bound holds for any hypothesis h e H and any distribution D:
Reg- (h) Righ P S { Rgggun (h) - -Ri
Rijuam hing 26)
(10)
hinge
then, f is lower bounded by 1
ii) Positive results. We then complement this negative result with positive results when using the exponential loss, the squared hinge-loss, and the p-margin loss, as summarized in Table The proofs with corresponding summarized Theorems 22, 23 and 24 are included in Appendix for completeness. For 5 the symmetry and completeness assumption can be relaxed to symmetry and the condition that for any x X. there exists a hypothesis / such that (,(x;)) - haxx, 2 p for any + j y, as shown in Theorem 24. In the proof, we introduce an auxiliary Lemma 21 in Appendix I, which would be helpful for lower bounding the conditional regret of T with that of the multi-class 0/1 loss.
7

---

Table 2: H-coniiity bounds for sum losses with symmetric and complete hypothesis sets. Sum loss H-consistency bound (Theorems 22, 23 and 24)
Deum
Re (fi) Rio S
(h) R
binge o0 Maaum Ht Me
sq sq-hinge
eq-hinge
sq-hings
Deum heum P
Re (h) R2 fo-1111 J( S 222
(2(RR Rquam (h)
R 4ean H M.aam 24 Men.. oxp
Ri (hi Ro- H( S Raquu (h) Rappum,3 24 + Maguu Pe Me
Table 3: coconsistyyy bounds for constrained losses with symmetric and complete hypothesis sets. Constrained loss K-consistency bound (Theorems 25, 26, 27 and 28)
Bestnd hinge
Riz-1 (h) -R ,4 S.
Rig
Rgentnd (h)
Ri aaeend or
M.pcatad
MM
hinge
binge
J0
gestnd sa--hiun sq-hinge
Rea. (1t) - -Ri Ria-in
Roestnd (h) sq-hingo
R2
grated eq-iing
Je M
Macaan oer hingo 3f
d pestnd exp
Re (h) -
-Ri Ria--1.0 S V2 (2(R
Repcaraa (h) R Reatud ge + M.portad ,36 Mea.
ge eestnd
R (li) Rig-1, Rogatnal ( (h) Rágennd 2t Magand H Mo.
4.3 Constrained losses
In this section, we discuss guarantees for constrained loss, that is loss functions defined via constraint, as in (Lee et al., 2004):
gestnd (h, {-)M(a)))
(11)
y+y
with the constraint that Eyey M1 y) = O. We present series of positive results by proving multi-class H-consistency bounds when using as an auxiliary function the hinge-loss, the squared hinge-loss, the exponential loss, and the p-margin loss, as summarized in Table 3. As with the binary case (Awasthi et al., 2022a), the bound admits a linear dependency for daated and 4- in contrast
with a square-root dependency for & cestnd sq-hinge and gestnd exp as illustrated in Figure 1. The proofs with corresponding summarized Thcorems 25, 26, 27 and 28 are included in Appendix K for completeness. For 4estnd, the symmetric and complete assumption can be relaxed to be symmetric and satisfy that for any X,, there exists hypothesis h H such that h(,, S -p for any y Vmmxx shown in Theorem 28.
The main idea of the proofs in this section is to leverage the constraint condition of Lee et al. (2004) that the scores sum to zero, and appropriately choose a hypothesis h that differs from h only by its scores for h(x) and ymax- We can then upper bound the minimal conditional risk by the conditional risk of T without having to derive the closed form expression of the minimal conditional risk.
As shown by Steinwart (2007, Theorem 3.2), for the family of all measurable functions, the min- imizability gaps vanish: Mea.1.Han Mquam KKa Mggaand .Yn,. O, for & Phinge- bing Peep and 4,, Therefore, when HC = Fan. our quantitative bounds in Table 2 and Table 3 imply the asymptotic consistency results of those multi-class losses in (Tewari and Bartlett, 2007), which shows that our results are stronger and more significant. We also provide bounds for multi-class losses using a non-conver auxiliary function, which are not studied in the previous work.
5 Adversarial H-consistency bounds
In this section, we analyze multi-class H-consistency bounds in the adversarial scenario (f2 = Ey). For any X, denote by (x) the set of hypotheses h with positive margin the ball of radius 7 around a, Hx)x) = h H. inf inf h(x)) > 0). and by (,,x)) the set of labels generated by these hypotheses, H,(x)) e When K. is symmetric, we have (z) = y iff (x) # Ø. The following lemma characterizes the conditional e-regret for
8

---

adversarial 0/1 loss, which will be helpful for applying Theorem 1 and Theorem 2 to the adversarial scenario.
Lemma 11. For any x X, the minimal conditional f--risk and the conditional c-regret for eg can be expressed as follows:
()) =1 max L(, (aH
(4,, [max p(x,y) h(x)) (x) + #Ø
otherwise.
The proof of Lemma 11 is presented in Appendix F. By Lemma 11. Theorems 1 and 2 can be instantiated as Theorems 12 and 13 in the adversarial scenario as follows, where H-consistency bounds are provided between the adversarial multi-class 0/1 loss and a surrogate loss l.
Theorem 12 (Adversarial distribution-deeeedeett V-bound). Assume that there exists a convex function V: IR. R with (0) 0 and e 2 O such that the following holds for all h e H, x (o E X: H., (a) = Φ) and e P::
v(
1) (c,
max p(r,v) - p(x, hxx)) (x),(z)
(12)
Then, for any hypothesis E H and any distribution D P, we have
V (Re, (b) - Ri, + Mc, s Rh) - Ri Me + max (r))).
(13)
Theorem 13 (Adversarial distribution
r-bouund). Assume that there exists a non-
negative concave function T.R. R and e 2 such that the following holds for all h e H E {x E X (x) + Ø} and D E P:
max p(x,9) p(z, h(z))] <T),e,)();,)) (w),
(14)
Then, for any hypothesis h E H and any distribution DD E P, we have
Re (h) R2 oc s ( -Ri + Me.x) Me, +c.
(15)
Next, we will apply Theorem 12 and Theorem 13 to study various hypothesis sets and adversarial surrogate loss functions in Sections 5.1 for negative results and Section 5.2, 5.3, and 5.4 for positive results. A careful analysis is presented in each case (see Appendix L, M, N and O).
5.1 Negative results for adversarial robustness
The following result rules the K-consistency guarantee of multi-class losses with convex auxiliary function, which are commonly used in practice. The proof is given in Appendix L.
Theorem 14 (Negative results for convex functions). Fix c 2. Suppose that t is conver and non- increasing, and H. contains 0 and satisfies the condition that there exists x E X such that (x) $ Ø. for a non-decreasing function f:E.- Rr, the following H-coosissenccy bound holds for any hypothesis h E H and any distribution D:
- Re, R2, or S (f) >R
(16)
then, is lower bounded by for ? Tmax Foum and Hestad
Instead, we show in Sections 5.2, 5.3, and 5.4 that the max, sum and constrained losses using as auxiliary function the non-convex p-margin loss admit favorable H-coossstencyy bounds in the multi-class setting, thereby significantly generalizing the binary counterpart in (Awasthi et al., 2022a).
5.2 Adversarial max losses
We first consider the adversarial max loss maxx defined as the supremum based counterpart (5):
(1, maxx(h,
max
sup (p at = مميا
(17)
For the adversarial max loss with d- = pp. we can obtain JC-consistency bounds as follows.

---

Theorem 15 (H-eonsistennyy bound of (pax), Suppose that H is symmetric. Then. for any hypoth- esis h H and any distribution D, we have
R Aamux (h)
R Bann o + M Maguun 36
Re, (1) - Ri,00 $
Me, (18)
inf (x suphom (2) 21 =1 =1, (n(s))((())()))
min
5.3 Adversarial sum losses
Next, we consider the adversarial sum loss Trnm defined as the supremum based counterpart of (9):
Toum 21,
sup -' 1,
0(h('' v) 1((2', ,()
(19)
Using the auxiliary Lemma 21 in Appendix I, we can obtain the H-coossitency bound of Teum.
Theorem 16 (H-connistency bound of Baum)), Assume that H is symmetric and that for any E X, there exists a hypothesis h oe inducing the same ordering of the labels for any I' fa':|x-ae x''l, 57 and such that =f h(1x', ,J) 2 for any i * j e y. Then, for any hypothesis h E H and any distribution D, the following inequality holds:
Re, (h) R2,, $ R (h) - R Tg 2 + MTmum or Me,,
(20)
5.4 Adversarial constrained loss
Similarly, we define the adversarial constrained loss Festnd as supremum based counterpart of (11):
Tattdd (h,
sup Σ +(-h(x',1)) ,'))
(21)
-'112-0'| p s'
with the constraint that Evey h(,, v) O. For the adversarial constrained loss with 1b Dp. obtain the H-consistency bound of Testad as follows.
Theorem 17 (JC-consistency bound of Testudy. Suppose that K is symmetric and satisfies that p
for any x E X, there exists hypothesis H with the constraint Eney h(, v) = O such that sup=*/--xl|ss ((0',)) S fpo any # Ymax- Then, for any hypothesis h E H and any distribution,
Re, (h) R7,x x Roaand (h) R Regand K Miferand or Me,
(22)
The proofs of Theorems 15, 16 and 17 are included in Appendix M, N and O respectively. These results are significant since they apply sets Hall Hiin and HNN with B = +oo all verify the conditions of those theorems. When B < too, the conditions Theorems 16 and 17 can still be verified with suitable choice of p. where we can consider the hypotheses such that wy = 0 in Hig and HNNN while Theorem 15 holds for any p 0.
general hypothesis sets. In particular, symmetric hypothesis
Conclusion
We presented comprehensive study of "C-consistencyy bounds for multi-class classification, including the analysis of the three most commonly used families of multi-class surrogate losses (max losses, sum losses and constrained losses) and including the study of surrogate losses for the adversarial robustness. Our theoretical analysis helps determine which surrogate losses admit a favorable guarantee for given hypothesis set JC. Our bounds can help guide the design of multi-class classification algorithms for both the adversarial and non-adveraa settings. They also help compare different surrogate losses for the same setting and the same hypothesis set. Of course, in addition to the functional form of the K-consistency bound, the approximation property of a surrogate loss function combined with the hypothesis set plays important role.
10

---

References
A. Agarwal and S. Agarwal. On consistent surrogate risk minimization and property clicitation. In Conference Learning Theory, pages 4-22, 2015.
P. Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. In Advances in Neural Information Processing Systems, pages 9804-9815, 202
Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. arXiv preprint www.iv:210.099666 2021b.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.0155: 2021c
Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-ccossiteneyy bounds for surrogate loss minimizers. In International Conference on Machine Learning, pages 1117-1174, 2022a.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. K-consistency estimation error of surrogate loss minimizers. arXiv preprint arXiv:2205.08017 2022b.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2023.
H. Bao, C. Scott, and M. Sugiyama. Calibrated surrogate losses for adversarially robust classification. In Conference on Learning Theeor, pages 408 401-451, 2020.
P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-1555 2006.
M. Blondel. Structured prediction with projection oracles. In Advances in neural information processing systems, 2019.
N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (SP), pages 39-57, 2017.
D.-R. Chen and T. Sun. Consistency of multiclass empirical risk minimization methods based on convex loss. Journal of Machine Learning Research, 7:2435-2447 2006.
D.-R. Chen and D.-H. Xiang. The consistency of multicategory support vector machines. Advances in Computational Mathematics, 24(1):155-16) 2006.
C. Ciliberto, L. Rosasco, and A. Rudi. A consistent regularization approach for structured prediction. In Advances in neural information processing systems, 2016.
C. Cortes and V. Vapnik. Support-vector networks. Mach. Learn., 20(3):273-297, 1995.
C. Cortes, G. DeSalvo, and M. Mohri. Leamning with rejection. In Algorithmic Learning Theory, pages 67-82, 2016a.
C. Cortes, G. DeSalvo, and M. Mohri. Boosting with abstention. In Advances in Neural Information Processing Systems, pages 1660-1668, 2016b.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 2(Dec):265-292, 2001.
K. Dembezynski, W. Kotlowski, and E. Hüllermeier. Consistent multilabel ranking through univariate losses. arXiv preprint arXiv: 64001, 2012.
U. Dogan, T. Glasmachers, and C. Igel. A unified view on multi- support vector classification. Journal of Machine Learning Research, 17:1-32, 2016.
J. Finocchiaro, R. M. Frongillo, and B. Waggoner. An embedding framework for the design and analysis of consistent polyhedral surrogates. arXiv preprint arXiv:2206. 14707, 2022.
R. Frongillo and Waggoner. Surrogate regret bounds polyhedral losses. Advances Neural Information Processing Systems, pages 21159-215580 2021.

---

W. Gao and Z.-H. Zhou. On the consistency of multi-labe learning. In Conference on learning theory, pages 341-358, 2011.
W. Gao and Z.-H. Zhou. On the consistency auc pairwise optimization. In International Joint Conference Artificial Intelligence, 2015.
I. J. Goodfellow, Shlens, and Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6577, 2014.
V. Kuznetsov, M. Mohri, and U. Syed. Multi-class deep boosting. In Advances in Neural Information Processing Systems, pages 2501-2509 2014.
Y. Lee, Y. Lin, and G. Wahha. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data, Journal of the American Statistical Association, 99(465):67-81, 2004.
Y. Liu. Fisher consistency of multicategory support vector machines. In Artificial intelligence and statistics, pages 291-298, 2007.
P. Long and R. Servedio. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809, 2013.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083 2017.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, second edition, 2018.
H. Narasimhan, H. Ramaswamy, A. Saha, and S. Agarwal. Consistent multiclass algorithms for complex performance measures. In International Conference on Machine Learning, pages 2398- 2407, 2015.
A. Osokin, Bach, and S. Lacoste-Julien. On structured prediction theory with calibrated convex surrogate losses. In Advances in Neural Information Processing Systems, 2017.
Pedregosa, Bach, and A. Gramfort. On the consistency of ordinal regression methods. Journal of Machine Learning Research, 18:1-35, 2017.
B. A. Pires and Szepesvári. Multiclass classification calibration functions. arXiv: arXiv:1609.06:: 06385, 2016.
arXiv preprint
B. A. Pires, C. Szepesvari, and M. Ghavamzadeh. Cost-sensitive multiclass classification risk bounds. In International Conference on Machine Learning, pages 1391-1399, 2013.
H. G. Ramaswamy and S. Agarwal. Classification calibration dimension for general multiclass losses.
In Advances Neural Information Processing Systems, 2012.
H. G. Ramaswamy and S. Agarwal. Convex calibration dimension for multiclass loss matrices. Journal of Machine Learning Research, 17(1):397-441, 2016.
H. G. Ramaswamy, S. Agarwal, and A. Tewari. Convex calibrated surrogates for low-rank loss matrices with applications to subset ranking losses. In Advances in Neural Information Processing Systems, 2013.
H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classification with reject option. arXiv preprint arXiv: 1505::5500044 04137, 2015.
Ravikumar, A. Tewari, and E. Yang. On NDCG consistency of listwise ranking methods. In International Conference Artificial Intelligence and Statistics, pages 618-626, 2011.
R. Schapire and Y. Freund. Boosting: Foundations and Algorithms. MIT Press, 2012.
Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-287, 2007.
12

---

A. Tewari and P. L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36):0007-1025, 2007.
A. Thilagar, R. Frongillo, J. J. Finocchiaro, and E. Goodwill. Consistent polyhedral surrogates for top-k classification and variants. In International Conference on Machine Learning, pages 21329-21 21359, 2022.
D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry, Robustness may be at odds with accuracy. arXiv preprint arXiv: 12152, 2018.
K. Uematsu and Lee. theoretically optimal ranking functions bipartite ranking. Journal of the American Statistical Association, 1115119:1311-1222 2017.
Y. Wang and C. Scott. Weston-watkins hinge loss and ordered partitions. In Advances in neural information processing systems, pages 19873-19883, 2020.
J. Weston and C. Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
R. C. Williamson, E. Vernet, and M. D. Reid. Composite multiclass losses. Journal of Machine Learning Research, 17:1-52, 2016.
M. Zhang and S. Agarwal. Bayes consistency vs. H-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances in Neural Information Processing Systems, pages 16927-16936, 2020.
M. Zhang, H. G. Ramaswamy, and S. Agarwal. Convex calibrated surrogates for the multi-label I-measure. In International Conference on Machine Learning, pages 11246-11255, 2020.
Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1): (211:566888)) 85, 2004a.
T. Zhang. Statistical analysis of some multi-categon large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1225-122211 1251, 2004b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See abstract and introduction.
(b) Did you deseribe the limitations of your work? [Yes] See Appendix D.
(c) Did you discuss any potential negative societal impacts of your work? [No] We don't foresee any negative societal impact of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of theoretical results? [Yes] See Section 3, Section 4 and Section 5.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix E, F, G,
H, J, K, L, M, N, O.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wqe4oBJct-", "reviewer": "Reviewer_UKY2", "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.", "questions": ".", "limitations": ".", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\nThe paper is well written and the mathematical statements are clear and precise.\nNevertheless, I found the paper hard to follow. This may be due to my lack of familiarity with this kind of bounds.\nThe 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.\nThe paper is clean but a bit arid in the current state.\nI was not able to assess the relevance and the impact of this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WlkS5mfRci0", "reviewer": "Reviewer_HTLU", "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.", "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?\n\nHow can one estimate the bounds? Can the results indicate which surrogate loss is a better choice for a given hypothesis set H?\n\nFigure 1 showed \\rho-margin loss but didn’t specify the value of \\rho in the figure.\n\nL175, L187: any distribution “D”", "limitations": "The reviewer has not yet seen the potential negative societal impact of the work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "La3Nx1C_MDn", "reviewer": "Reviewer_haLt", "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.", "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", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. To my knowledge, this paper is the first work to study multi-class H-consistency.\n2. This paper is well-written and easy to follow.\n3. The theoretical results and proofs are sound, based on my judgement.\n\nWeakness:\nThe 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. \n\n\n[1] Pranjal Awasthi, et al. \"H-Consistency Estimation Error of Surrogate Loss Minimizers.\" *International Conference on Machine Learning* (2022). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept