$H$-Consistency Bounds: Characterization and Extensions
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2023 poster (2023)
Keywords: consistency
H-consistency
characterization
learning theory

Abstract: A series of recent publications by Awasthi et al. have introduced the key notion of *$H$-consistency bounds* for surrogate loss functions.  These are upper bounds on the zero-one estimation error of any predictor in a hypothesis set, expressed in terms of its surrogate loss estimation error. They are both non-asymptotic and hypothesis set-specific and thus stronger and more informative than Bayes-consistency. However, determining if they hold and deriving these bounds have required a specific proof and analysis for each surrogate loss. Can we derive more general tools and characterizations? This paper provides both a general characterization and an extension of $H$-consistency bounds for multi-class classification. We present new and tight $H$-consistency bounds for both the family of constrained losses and that of comp-sum losses, which covers the familiar cross-entropy, or logistic loss applied to the outputs of a neural network. We further extend our analysis beyond the completeness assumptions adopted in previous studies and cover more realistic bounded hypothesis sets.  Our characterizations are based on error transformations, which are explicitly defined for each formulation. We illustrate the application of our general results through several special examples. A by-product of our analysis is the observation that a recently derived multi-class $H$-consistency bound for cross-entropy reduces to an excess bound and is not significant. Instead, we prove a much stronger and more significant guarantee.

H- H-Consistenccy Bounds:
Characterization and Extensions
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims.o nyu edu
Mehryar Mohri Google Research & CIMS New York, NY 10011 mohri@google.com
Yutao Zhong
Courant Institute New York, NY 10012 yutaoucims nyu edu
Abstract
A series of recent publications by Awasthi, Mao, Mohri, and Zhong [2022b] have introduced the key notion of K-consistency bounds for surrogate loss functions. These are upper bounds on the zero-one estimation error of any predictor in hy- pothesis set, expressed terms of its surrogate loss estimation error. They are both non-asymptotic and hypothesis set-specific and thus stronger and more informative than Bayes-consistency. However, determining if they hold and deriving these bounds have required a specific proof and analysis for each surrogate loss. Can we derive more general tools and characterizations? This paper provides both a general characterization and an extension of J[-consistency bounds for multi-class classification. We present new and tight HC-consistency bounds for both the family of constrained losses and that of comp-sum losses, which covers the familiar cross- entropy, or logistic loss applied to the outputs neural network. We further extend our analysis beyond the completeness assumptions adopted in previous studies and cover more realistic bounded hypothesis sets. Our characterizations are based on error transformations, which are explicitly defined for each formulation. We illustrate the application of our general results through several special examples. A by-product of our analysis is the observation that recently derived multi-class ce-conssstency bound for cross cross-entropy reduces to an excess bound and is not significant. Instead, we prove much stronger and more significant guarantee.
Introduction
coyyes-conssstenyyy is an important property of surrogate loss functions. It requires that minimizing the surrogate excess етror over the family of all measurable functions leads the minimization of the target eтror loss in the limit [Steinwart, 2007]. This property applies to broad family of convex margin-base based losses in binary classification [Zhang, 2004a, Bartlett et al., 2006], as well as some extensions in multi-class classification [Tewari and Bartlett, 2007]. However, Bayes-consistency does not apply to the hypothesis sets commonly used for learning, such as the family of linear models or that of neural networks, which of course do not include all measurable functions. Furthermore, is also only an asymptotic property and does not supply any convergence guarantee.
To address these limitations, a series of recent publications by Awasthi, Mao, Mohri, and Zhong [2022b] introduced the key notion of -Ccoosisteecyy bounds for surrogate loss functions. These are upper bounds on the zero-one estimation error of any predictor in hypothesis set, expressed in terms of its surrogate loss estimation error. They are both non-asymptotic and hypothesis set-specific and thus stronger and more informative than Bayes-consistency. However, determining the validity of these bounds and deriving them have required a specific proof and analysis for each surrogate loss. Can we derive more general tools and characterizations for H-connistency bounds?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper provides both general characterization and an extension of JCCconsisteney bounds for multi-class classification. Previous approaches deriving these bounds required the development of new proofs for each specific case. In contrast, we introduce the general concept of an error transformation function that serves as a very general tool for deriving such guarantees with tightness guarantees. We show that deriving an H-coosistency bound for comp-sum losses and constrained losses for both complete and bounded hypothesis sets can be reduced to the calculation of their corresponding error transformation function. Our general tools and tight bounds show several remarkable advantages: first, they improve existing bounds for complete hypothesis sets previously proven in [Awasthi et al., 2022b]; second, they encompass all previously comp-sum and constrained losses studied thus far as well as many new ones [Awasthi et al., 2022a, Mao et al.. 2023h]; third, they extend beyond the completeness assumption adopted in previous work; fourth, they provide novel guarantees for bounded hypothesis sets; and, finally, they help prove a much stronger and more significant guarantee for logistic loss with linear hypothesis set than [Zheng et al., 2023].
Previous work. Here, we briefly discuss recent studies of HC-ooniittnncy bounds by Awasthi et al. [2022a,b]. Mao et al. [2023h] and Zheng et al. [2023]. Awasthi et al. [2022a] introduced and studied H-consistency bounds in binary classification. They provided a series of tight H-consistency bounds for bounded hypothesis set of linear models and one-hidden-layer neural networks. The subsequent study [Awasthi et al., 2022b] further generalized the framework to multi-class classification and presented an extensive study of H-coossstencyy bounds for diverse multi-class surrogate losses, including negative results for max losses [Crammer and Singer, 2001] and positive results for sum losses [Weston and Watkins, 1998], and constrained losses [Lee et al., 2004]. However, the hypothesis sets examined in their analysis were assumed to be complete, which rules out the bounded hypothesis sets typically used in practice. Moreover, the final bounds derived from [Awasthi et al., 2022h] are based on ad hoc methods and may not be tight. [Mao et al., 2023h] complemented this previous work by studying a wide family of comp-sum losses in the multi-class classification, which generalizes the sum-losses and includes as special cases the logistic loss [Verhulst, 1838, 1845, Berkson, 1944, 1951] J, the generalized cross-entropy loss [Zhang and Sabuncu, 2018], and the mean absolute error loss [Ghosh et al., 2017]. Here too, the completeness assumption on the hypothesis sets was adopted and their JC-consistency bounds do not apply to common bounded hypothesis sets in practice. Recently, Zheng et al. [2023] proved JC-consistnncy bounds for multi-class logistic loss with bounded linear hypothesis sets. However, their bounds require a erucial distributional assumption, under which the minimizability gaps coincide with the approximation errors. Thus, their bounds can be recovered as excess error bounds, which are less significant.
Other related work on K-consistency bounds includes HH-consistency bounds for pairwise ranking [Mao, Mohri, and Zhong, 2023d,e]; theoretically grounded surrogate losses and algorithms for learning with abstention supported by H--consistnncy bounds, including the study of score-based abstention [Mao, Mohri, and Zhong, 2023f], predictor-rejector abstention [Mao, Mohri, and Zhong, 2023c] and learning to abstain with a fixed predictor with application in decontextuallzzatonn [Mohri, Andor, Choi, Collins, Mao, and Zhong, 2023]; principled approaches for learning to defer with multiple experts that benefit from strong --conssity bounds, including the single-stage scenario [Mao, Mohri, and Zhong, 2023b) and a two-stage scenario [Mao, Mohri, Mohri, and Zhong, 2023a]; K-consistency theory and algorithms for adversarial robustness [Awasthi et al., 2021a,b, 2023a, Mao al., 2023h, Awasthi et al., 2023b]; and efficient algorithms and loss functions for structured prediction with stronger K-consistency guarantees [Mao et al., 2023g].
Structure of this paper. We present new and tight H-consistency bounds for both the family
of comp-sum losses (Section 4. and that of constrained losses (Section 5.1), which cover the familiar cross-entropy, or logistic loss applied to the outputs of a neural network. We further extend our analysis beyond the completeness assumptions adopted in previous studies and cover more realistic bounded hypothesis sets (Section 4.2 and 5.2). Our characterizations are based on error transformations, which are explicitly defined for each formulation. We illustrate the application of our general results through several special examples. by-product of our analysis is the observation that recently derived multi-class H-consistency bound for cross- cross-entropy reduces to an excess bound independent of the hypothesis set. Instead, we prove a much stronger and more significant guarantee (Section 4.2).
We give a comprehensive discussion of related work in Appendix A. We start with some basic definitions and notation in Section 2.
2

---

2 Preliminaries
We denote by X the input space, by y the output space, and by D a distribution over Xx We consider the standard scenario of multi-class classification, where y = {l...., nn). Given a hypothesis set H of functions mapping X x R. the multi-class classification problem consists of finding hypothesis h E H with small generalization error R (h), defined by Ri (h) = B(a.))=l [fo (h, x, y)J, where f--1 (h, x, y) = h(x)+y is the multi-class zero-one loss with h(x)) = argmax yey h(,,, y) the prediction of h for the input point x. We also denote by H(x)) the set of all predictions associated to input x generated by functions in H, that is, H(x)= (h(:): h e H).
We will analyze the guarantees of surrogate multi-class losses in terms of the zero-one loss. We denote by l surrogate loss and by Re(h) its generalization error, Re(h) For a loss function E, we define the best-in-class generalization error within a hypothesis set H as (3()= inf (h),, and refer to (h) R2 (JC) the estimation error. We will study the key notion of H CC-oonisstnccy bounds [Awasthi et al., 2022a,b], which are upper bounds on the zero-one estimation error of any predictor in hypothesis set, expressed in terms of its surrogate loss estimation error, for some real-valued function f that is non-decreasing:
(rt.))>>((((,, x,))
E E HC, Rea. (h) - _ (30) s
- (30).
These bounds imply that the zero-one estimation error is at most f(c) whenever the surrogate loss estimation error is bounded by c. Thus, the learning guarantees provided by H-consistency bounds are both con-asymptotic and hypothesis set-specific. The function f appearing in these bounds is expressed in terms of minimizability gap, which is quantity measuring the difference of best- in-class error Ri (H) and the expected best-in-class conditional error [x x)) Mx( R3 (H) - x ( (H, where xc) = [((h,,r and ej (H. iinfeene C.(h,.)) are the conditional error and best-in-class conditional error respectively. We further write AC,, (h) e₂2 (H,,z) .z) to denote the conditional regret. Note that that the minimizability gap is an inherent quantity depending on a hypothesis set H and the loss function &.
By Lemma 1, the minimizability gap for the zero-one loss, Me.., (30), coincides with its approxi- mation error Ae (H) Ri (I()- RR,, (Hau) when the set of all possible predictions generated by H covers the label space y. This holds for typical hypothesis sets used in practice. However, for a surrogate loss f, the minimizability gap (H) is always upper bounded by and in general finer than approximation error Ar()() = (H) - (HGn) since Mc(3() = AA((3) - Le())) where Hall is the family of all measurable functions and (H()) = Es [e] (H, ez (Hall, x)) (see Appendix B for a more detailed discussion). Thus, an H-consistency bound, expressed as follows for some increasing function I:
Río (h) Ri,,, (H) Me, 1 (H) S -() M2))...
-
(1)
is more favorable than an excess error bound expressed in terms of approximation errors Ro (h) (3() + Ae. (3)) < (h) R7 (3() Ar()). Here, I' is typically linear the square-root function modulo constants. When H = Hall the family of all measurable functions, an H-consistency bound coincides with the excess error bound and implies cayss-consistency by taking the limit. is therefore stronger guarantee than excess error bound and Bayes-consistencyy
The minimizability gap always non-negative, since the infimum of the expectation is greater than or equal to the expectation of infimum. Furthenmore, as shown in Appendix B, when H is the family of all measurable functions or when the Bayes-error coincides with the best-in-class error, that is. R7 (I6) R2 (Hau), the minimizability gap vanishes. In such cases, (1) implies the H--consistnccy of a surrogate loss with respect to the zero-one loss 40-1:
(h - R2 (3C) 12++000
- Rea (hn) Ri (I)
O.
In the next sections, we will provide both a general characterization and an extension of --consistency bounds for multi-class classification. Before proceeding, we first introduce useful lemma from [Awasthi et al., 2022b] which characterizes the conditional regret of zero-one loss explicitly. We denote by p(x) = (p(x, 1), p(z, n)) as the conditional distribution of y given x.
Lemma 1. For zero-one loss fo-1, the
conditional error and the conditional regret for fo can be expressed as follows: for any I é X, we have
eia (H, ))= 1mmax
max p(x,y) and Aeton.c(h,, = max p(x, y) - pp( h(z)). gcH(2)
geH(z))
3

---

3 Comparison with previous work
Here, we briefly discuss previous studies of CC-cosistyy bounds [Awasthi et al., 2022a,b, Zheng et al., 2023, Mao et al., 2023h] in standard binary or multi-class classification and compare their results with those we present.
Awasthi et al. [2022a] studied H--consisencyy bounds in binary classification. They provided a series of tight H--consistency bounds for the bounded hypothesis set of linear models 3ch, and one-hidden-layer neural networks K defined as follows:
Jch {ar + w- x bl |w|| S W. 16 s B}
JoNN f-+ Σ Eul(wsxx+)) -)- |//|| s A, |wyll s W1 s B}.
where B, W, and A are positive constants and where (.)- = max(-, 0). We will show that our bounds recover these binary classification H cc-oosiisty bounds.
The scenario of multi-class, classification is more challenging and more crucial in applications. Recent work by Awasthi et al. [2022b] showed that max losses [Crammer and Singer, 2001]. defined as emaa (h, x. 3) = maxy'sy (1h(,,, y) ((xxy')) for some convex and non-increasing function T cannot admit meaningful H-consistency bounds, unless the distribution is deterministic. They also presented a series of H-consistency bounds for sum losses [Weston and Watkins, 1998] and constrained losses [Lee et al., 2004] for symmetric and complete hypothesis sets, that is such that:
H( 1=: R: M(: F Vy Vr X, [ R,
(symmetry) (completeness)
for some family I of functions mapping from to R. The completeness assumption rules out the bounded hypothesis sets typically used in practice such Him- Moreover, the final bounds derived from [Awasthi et al., 2022b] are based on ad hoc proofs and may not be tight. In contrast, we will study both the complete and bounded hypothesis sets, and provide very general tool to derive H-consistency bounds. Our bounds are tighter than those of Awasthi et al. [2022b] given for complete hypothesis sets and extend beyond the completeness assumption.
[Mao et al., 2023h] complemented the work of [Awasthi et al., 2022b] by studying a wide family of comp-sum losses in multi-class classification, which generalized the sum-losses and included as special cases the logistic loss [ [Verhulst, 1838, 1845, Berkson, 1944, 1951], the generalized cross- entropy loss [Zhang and Sabuncu, 2018], and the mean absolute error loss [Ghosh al., 2017]. Here too, the completeness assumption was adopted, thus their H-cconsistency bounds do not apply to common bounded hypothesis sets used in practice. We illustrate the application of our general results through a broader set of surrogate losses than [Mao et al., 2023h] and significantly generalize the bounds of [Mao et al., 2023h] to bounded hypothesis sets.
Recently, Zheng et al. [2023] proved K-consistency bounds for logistic loss with linear hypothesis sets in the multi-class classification: Hin (a: wy + by ||wy||| S W. W,lbyl s B,y e y). However, their bounds require a crucial distributional assumption under which, the minimizability gaps Me.., (HGn) and Ma (Hii) coincide with the approximation errors (HGn)) Habbn>>-R4 -Ry (Han) and Re (Hin)) Ri (Hau) respectively (see the note before [Zheng al., 2023, Appendix F)). Thus, their bounds
can be recovered as excess error bounds Rio_ (h) - RR (Har) S V2 (h) Ring (Ha)) which are less significant. In contrast, our Hiin connistency bound are much finer and take into account the role of the parameter B and that of the number of labels n. Thus, we provide stronger and more significant guarantees for logistic loss with linear hypothesis set than [Zheng et al., 2023].
In summary, our general tools offer the remarkable advantages of deriving tight bounds, which improve upon the existing bounds of Awasthi et al. [2022b] given for complete hypothesis sets, cover the comp-sum and constrained losses considered in [Awasthi et al., 2022a, Mao et al., 2023h] as well as new ones, extend beyond the completeness assumption with novel guarantees valid for bounded hypothesis sets, and are much stronger and more significant guarantees for logistic loss with linear hypothesis sets than those of Zheng et al. [2023].

---

4 Comp-sum losses
In this section, we present general characterization of JK-consistency bounds for comp-sum losses, a family of loss functions including the logistic loss [Verhulst, 1838, 1845, Berkson, 1944, 1951], the sum exponential loss [Weston and Watkins, 1998, Awasthi et al., 2022b], the generalized cross entropy loss [Zhang and Sabuncu, 2018], the mean absolute error loss [Ghosh et al., 2017], and many other loss functions used in applications.
This is a family of loss functions defined via the composition of a non non-negative and non non-decreasing function V with the sum exponential losses (see [Mao et al., 2023h)):
vh e H, V (2, y) x I x y, Coomp x, x) = v Σ
yray
This expression can be equivalently written as ecomp (h, 4) = 4b
Evey cliwwyy where 4: H
V(-"") a non-increasing auxiliary function from [0, 1] to R, {+00}. As an example, the logistic loss corresponds to the choice Φ: a + log(u) and the sum exponential loss to t: 1-u
4.1 -o-coniistyncy bounds
In previous work, deriving H-ccosiitencyy bounds has required giving new proofs for each instance. The following result provides very general tool for deriving such bounds with tightness guarantees. We introduce an error transformation function and show that deriving H-consistency bound for comp-sum losses can be reduced to the calculation of this function.
Theorem (H-consistency bound for comp-sum losses), Assume that H is symmetric and com- plete and that Jromp is convex. Then, the following inequality holds for any hypothesis h E H and any distribution
gromp (Ri--1 (h) Ri (30) M4 (H)) s Reoums (h) - Ricamp (H) Mgeamp (H),
(3)
with gromp an H-estimation error transformation for comp-sum losses defined for all [0, 1] by
gromp (t)
inf sup re(0.t] 1-1-
Lot (+(( - Φ(1 -1 [4] 1 (1- -( 1)]] 2
= 2
inf pe[ Pe[.i, ve,1 memox(To. ne(-72m11] 114221,11200
inf
sup
( - Φ - +)]+ ( $( + 11]] n > 2.
Furthermore, for any E [0, 1}, there exist a distribution D and a hypothesis l e H such that Rio (h) - Ro Ri (H) + Me. (3) = l and Reaam (h) Recomm (HC + Mgesmp (H) gromp (I).
Thus, Theorem 2 shows that, when Tromp is convex, to make these guarantees explicit, all that is needed is to calculate Tromp, Moreover, the last statement shows the tightness of the guarantees derived using this function. The constraints in Tromp are due to the forms that the conditional probability vector and scoring functions take. These forms become more flexible for > 2, leading to intricate constraints. Note that our HC-consisenccy bounds are distribution-indeeenddd and we cannot claim tightness across all distributions.
The general expression of Jeomp in Theorem 2 is complex, but it can be considerably simplified under some broad assumptions, as shown by the following result.
Theorem 3 (characterization of Jeomp). Assume that & is convex, differentiable at } and / (!) < O. Then, gromp can be expressed as follows:
( (1) inf uol +.] L ( + p)) + Ltt ( -+)} inf [inTee[ - (TT) - inf innfpee--- p-[- 1-t n1) 1 m)] n> 2.
n n= 2
gromp(t)
The proof of this result as well as that of other theorems in this section are given in Appendix C. Examples. We now illustrate the application of our theory through several examples. To do so, we compute the I6-estimation error transformation Jeomp for comp-sum losses and present the results in
5

---

Table 1: H-estimation enror transformation for common comp-sum losses.
Auxiliary function +b
log(t)
(1) (0,1)
t)2
Transformation Tromp
2n log(1 + 1/2 log(1 () v1-
(1r1) 1. 1 (1-1))
Table Remarkably, by applying Theorem 2, we are able to obtain the same H-consistency bounds for comp-sum losses with (() = - log((), 7 1. 1 {(1 (9), e (0,1) and 1 - those derived using ad hoc methods in [Mao et al., 2023h], and novel tight K-consistency bound for the new
M(x.)) 2
comp-sum loss lay 1 Evey ehtmaa
with (tt) (1 t)² in Theorem 4.
The calculation of Teomp for all entries of Table is detailed in Appendix C.3. To illustrate the effectiveness of our general tools, here, we show how the error transformation function can be straightforwardly calculated in the case of the new surrogate loss lsg.
Theorem (JC-consistency bound for a new comp-sum loss). Assume that H is symmetric and complete. Then. for all é H and any distribution, the following tight bound holds.
Rio- (h) R (H) s RR, (h) RR + Men, (30) MM (H).
Proof. For n 2, plugging in (t) (1 t)² in Theorem 3, gives
- t
1 1+t 1
2
1
1
-
t
t²
Jromp
inf
2 11
MC -
2
2
4
Similarly, for n > 2, plugging in (()) (1 t)² 2 in Theorem 3 yields
gromp
inf 74 [
(1-
inf -
1 1+1
(1-T+
1-1 2
(1---
2
inf r
((1-7)- (1-))
(minimum achieved at = t(r 1))
(minimum achieved at 5
By Theorem 2, the bound obtained is tight, which completes the proof.
4.2 Extension to non-complete/boundded hypothesis sets: comp-sum losses
As pointed out earlier, the hypothesis sets typically used in practice are bounded. Let I be family of real-valued functions of with ff()) S A(x) for all x X and such that all values in [-A(2),+++ +A()]] can be reached, where A(x) > 0 is a fixed function on X. We will study hypothesis sets H which each scoring function is bounded:
K (h x R (((.))) Vy
This holds for most hypothesis sets used in practice. The symmetric and complete hypothesis sets studied in previous work correspond to the special case of H. where A(x) to for all x X. The hypothesis set of linear models Hmm, defined by
Hmm {(x.y) + Wy x + by |wyl W. lbl B
is also a special instance of H where A(x) W W B. Let us emphasize that previous studies did not establish any H--consistnncy bound for these general hypothesis sets, H.
Theorem (H--onnistenecy bound for comp-sum losses). Assume that Teomp is convex. Then, the following inequality holds for any hypothesis h H and any distribution:
Tromp (Re.. (h) - -Ri (H) + Mea. (F)) Rgoamp (h) Recomp (H) + Mgcamp (F)

---

with T Jromp Tonmp
the --estimattin error transformation for comp-sum losses defined for all te [0. 1] by
sup re(u.3] (o [s 11---8min inf
inf
1t! - ( +(T+ n=
re
inf
sup ( P-t
- (T)) 2 (12++)]] []]]
n> 2,
Pel n-1 ve,1]
main Siin5722 572577775555 max acC
71+1251
where C' ( mmin T2. mmax),, min( Smax T2, smin Smax 1+(n=1)e Atj and I+(n-1)e2mn ME]. Furthermore, for any L [0, 1], there exist a distribution DD and h E K. such that Ro (h) Rio. (30) + Men1 (JC) = t and Recomp (h) - Rismm (IC) + Meeam (H() Jeomp(t).
8min
This theorem significantly broadens the applicability of our framework it encompasses bounded hypothesis sets. The last statement the theorem further shows the tightness of the H-consistency bounds derived using this error transformation function. We now illustrate the application of our theory through several examples.
A. Example: logistic loss. We first consider the multinomial logistic loss, that is gromp with o (u) log(u), for which we give the following guarantee.
Theorem (H--consistency bounds for logistic loss). For any he E H and any distribution, we have
Rto- (h) Rio.1 (F() Mo (H) 4 1 (h)- (H)
Meso (J)):
1+f log(1 1) + 1-1
log (1
Is Sman-SSii
where biog log
Eveoy Egey chiaryy and (t))
2
2
Smin +5max
log
Smax 8mnn
+ log
2 Amax
otherwise.
Smax 8mmin
The proof of Theorem 6 is given in Appendix E.2. With the help of some simple calculations, we can derive a simpler upper bound:
I (Smax T Sminn )2
2t
(1)
(1) sI((=
2(
2(Smin + Smmna) I. Smax Bona--Bii 5min
oerwess
When the relative difference between 8min and Smax is small, the coefficient of the linear term in explodes. On the other hand, making that difference large essentially turns I' into a square-root function for all values. In general, A is not infinite since regularization is used, which controls both the complexity of the hypothesis set and the magnitude the scores.
Comparison with [Mao et al., 2023h]. For the symmetric and complete hypothesis sets H consid- ered in [Mao et al., 2023h), A(x) +00, Smax 1, Smin O, (tt) 2 log(1 + t) 1-f log -t)
and [tt) 2t. By Theorem 6, this yields an HC-consistency bound for the logistic loss.
Corollary (H-consisteney bounds for logistic loss). Assume that H is symmetric and complete. Then, for any h H and any distribution, we have
Rin (h) - R io (I() S V (Remc Be (h) Rinm (I)) + M (30) - MM
where (t) 1t1 log(1 + t) 2 2
1-1 log(1 - t) and &r --1(t) 2t.
Corollary recovers the IC-consistency bounds of Mao al. [2023h].
Comparison with [Awasthi et al., 2022a] and [Zheng et al., 2023]. For the linear models Hin (x,y) + Wy x by |wwyl| W, W.|byl s B}. we have A(x) = W|x| B. By Theorem 6, we obtain connsisssttt bounds for logistic loss.
Corollary 8 conssisteny bounds for logistic loss). For any h E Hii and any distribution,
Rio- (h) Ri (Hiin)= s vn (Rtuae (h) Ri (Hiin) + Mena (Hin)) Mio. (Hia)
I+l log( 1 t) 1-t log 1- 2=(
ts (n- (n-1)(e2B 28, 20(n-1)(22
2
where (t)
1/ log
log
otherwise.
T=(x-1)e-25
2+(n ()(=B 26
7

---

++1 log(t 1)
1-1 log( 1 -
t 2
For 2, we have v())=
log
38 T+e 2e + log
2
(1
otherwise,
which coincides
2 te
with the special case the Pfjin-consisteng bounds given by Awasthi al. [2022a] for binary classification.
error transformation in [Awasthi et al., 2022a]. Thus, Corollary 8 includes as
Our bounds of Corollary 8 improves upon the multi-class -fin--oonssttecy bounds of recent work [Zheng et al., 2023, Theorem 3.3] in the following ways: i) their bound holds only for restricted distributions while our bound holds for any distribution; ii) their bound holds only for restricted values of the estimation error Reing (h) Ri (H(m)) while ours holds for any value in IR and more precisely admits piecewise functional form; iii) under their distributional as- sumption, the minimizability gaps ( and Me (HGnn) coincide with the approximation errors Ro (HGm)) Rio- (Han) and Reing (Him) Ri (Hau) respectively (see the note before [Zheng et al., 2023, Appendix FJ). Thus, their bounds can be recovered as an excess error bound
Re -h) R% (Hau)) S 2 /2(Re... (h) -R (Han) which is not specific the hypothesis set H and thus not as significant. In contrast, our Hiin -onsistency bound is finer and takes into account the role of the parameter B well the number of labels nı; iv) [Zheng et al., 2023, Theorem 3.3] only offers approximate bounds that are not tight; in contrast, by Theorem 5, our bound is tight.
Note that our H-consistencyy bound in Theorem 6 are not limited specific hypothesis set forms. They are directly applicable to various types of hypothesis sets including neural networks. For example, the same derivation can be extended to one- one-hidden-laye and their multi-class generalization by calculating and substituting the corresponding (xx). As a result, we can obtain novel and tight H--coniitencyy bounds for bounded neural network hypothesis sets in multi-class classification, which highlights the versatility of our general tools.
neural networks studied in [Awasthi et al., 2022a]
B. Example: sum exponential loss. We then consider the sum exponential loss, that is goomp with ((u)= 1-x By computing the error transformation Theorem 5, we obtain the following result.
Theorem (o-consistency bounds for sum exponential loss). For any E H and any distribution,
Re (h) - -Rio (31 Men. (H) s v V (Reemp(h) (h) R (IC) Me (J()
/1 - 12
1
where lexp = Ey'ey che.e))) -h(x.)) and (t))
Emax Smin / 28max
(Smaxe Emin
hewwise
2#maa Biiti 8min))
The proof of Theorem 9 is given in Appendix E.3. Observe that -1- 12 2 By Theorem making Smin close to zero, that is making A close to infinite for any x E X, essentially turns T into a square function for all values. In general, A is not infinite since regularization is used in practice, which controls both the complexity of the hypothesis set and the magnitude of the scores.
C. Example: generalized cross-entropy loss and mean absolute error loss. Due to space limita- tions, we present the results for these loss functions in Appendix E.
5 Constrained losses
In this section, we present a general characterization of H-cconsistnncy bounds for constrained loss, that is loss functions defined via constraint, in [Lee et al., 2004]:
gestnd (h, x. v) Σ #(-h(z,)))) y'-y
(5)
with the constraint that Eyey (xx,)) for non-negative and non-increasing auxiliary function T.
5.1 H--onsistenncy bounds
As in the previous section, we prove result that supplies a very general tool, an error trunsformation function for deriving H-consistency bounds for constrained losses. When Testud convex, to make these guarantees explicit, only need to calculate gestad
8

---

Table 2: H-estimation error transformation for common constrained losses.
Auxiliary function &
| (tpp())
Pringo max(0, 1 t) Pingoo (1) (1 2est Pag (1 1)2
Transformation grami (1) 2- v4- 12
(r)t (1)=
(1) E
geaend (1)
Theorem 10 (H-consistency bound for constrained losses). Assume that H is symmetric and complete. Assume that grestnd is convex. Then, for any hypothesis l E H. and any distribution,
gestnd (
(Rto-1 (h) Rig (9) + Meo-1 (30) Ryyeand (h) Regaina (H) + Mggarna (H)
with H-estimation error transformation for constrained losses defined on & E [0, by Frstnd(()
inf sup
r20 peR
1-t [ - 2 1 [ - (
2
n=
inf Pel 1:2maxx//a peB.
inf
sup 12---1 x p)] 2- - 1)] n 2.
Furthermore, for any E [0,1], 1]. there exist a distribution DD and hypothesis h E H such that Rig (h) - Ri (H) + Mes (3() I and Roosna (h) festnd (H) + Moann (H) = Festnd (1).
Here too, the theorem guarantees the tightness of the bound. This general expression of gestnd be considerably simplified under some broad assumptions, as shown by the following result.
Theorem 11 (characterization of grstnd). Assume that T is convex, differentiable at zero and & (0) < O. Then, Festad can be expressed as follows:
((0)- inf p 1 (()) + 2 Φ (w)
n 2
gostadd
inl-20 (2 | x ((-)) - inl ne
2-t- (--+((+++1))
2+t- 2
D( ((-TT= 10)]]
n 2
($(0) inf N ( 1-t ((1) + 1+ + (-11)
n1 = 2
2
2
[inf=2o (2 (20(-T) inl { (- +p)
2nd (-T mn}}
n1 2.
The proof of all the results in this section are given in Appendix D.
Examples. We now compute the I--sstimation error transformation for constrained losses and present the results in Table 2. Here, we present the simplified Testad by using the lower bound in Theorem 1 11. Remarkably, by applying Theorem 10, we are able to obtain tighter H-consistency bounds for constrained losses with & Phinge, hiuge, Pexp than those derived using ad hoc methods in [Awasthi et al., 2022b]. and a novel H-coosistency bound for the new constrained loss gestnd (h,,, x. v) En h(., y')² with o(1) = ((t)==(1-0)) (1-
5.2 Extension to non-complete or bounded hypothesis sets
As in the case of comp-sum losses, we extend our results beyond the completeness assumption adopted in previous work and establish H-coosistency bounds for bounded hypothesis sets. This significantly broadens the applicability of our framework.
Theorem 12 (Fé-consistency bound for constrained losses). Assume that J Jratud is convex. Then,
the following inequality holds for any hypothesis h E H and any distribution:
J Fostnd
(Rta (h) -K (H) Meg. (3() S Reanna (h) - -Riecund (H) Mesttu (H).
(6)
with T restnd the K-estimation error transformation for constrained losses defined for all t e [0,1] by gestad (t)=
inf r20
sup Am[7-Ami..7+
1-- (1=((((7) ( +)] (-( [1]]
n
inf Pe| .1 Ti 112max(T2.0)
inf
sup HeC
2- ( ( कه (- 1)1 + P (D-T2- m)]} n> 2,
where C = [max(TT, T Amins min( T1, } Aminn and Amin- = infrex A(x). Furthermore,
any t E [0, 11. there exist a distribution DD and a hypothesis h E H such that Rea (h) -R, (I()+
Mo. (IC) t and Reaand (h) R Re (3C) + M Meanu (IC) Festnd

---

The proof is presented in Appendix F.1. Next, we illustrate the application of our theory through an example of constrained exponential losses, that gestnd with ( ex By using the error transformation in Theorem 12, we obtain new H-consistency bounds in Theorem 13 (see Appendix F.2 for the proof) for bounded hypothesis sets H.
Theorem 13 (H--oonistencyy bounds for constrained exponential loss). Let @(1) = e- For any
E H. and any distribution,
Rea- (h) Rio (H) Men- (H) V (Reorrnd (h) RR ( M gestud H))
gestud
1- VI t Amnii - --Amin)) + 2-c -e Amin
2 e min+1
where (t)
otherwisc.
2
Awasthi et al. [2022b] proves H-consistency bounds for constrained exponential losses when H is symmetric and complete. Theorem 13 significantly generalizes those results to the non-complete hypothesis sets. Different from the complete case, the functional form our new bounds has two pieces which corresponds to the linear and the square root convergence respectively, modulo the constants. Furthermore, the coefficient of the linear piece depends on the the magnitude of Amin- When Amin is small, the coefficient of the linear term in V explodes. On the other hand, making Amin large essentially turns V into a square-root function.
Discussion
Here, we further elaborate the practical value of our tools and J--consistnncy bounds. Our contri- butions include more general and convenient mathematical tool for proving H-consiistnccy bounds, along with tighter bounds that enable better comparison of surrogate loss functions and extensions beyond previous completeness assumptions. As mentioned by [Awasthi et al., 2022b], given a hypothesis set H. JK-consistency bounds be used compare different surrogate loss functions and select the most favorable one, which depends on the functional form of the H--cossitenccy bound; the smoothness of the surrogate loss and its optimization properties; approximation properties of the surrogate loss function controlled by minimizability gaps; and the dependency on the number of classes in the multiplicative constant. Consequently, tighter #CCcoosistenccy bound provides more accurate comparison, as loose bound might not adequately capture the full ad advantage of using one does not take into account the hypothesis and an
surrogate loss. In contrast, asymptotic property, thereby failing to guide the comparison of different surrogate losses.
Another application of our H-consistency bounds involves deriving generalization bounds for rogate loss minimizers [Mao et al., 2023h], expressed in terms of the same quantities previously discussed. Therefore, when dealing with finite samples, a tighter K-consistency bound could also result in a corresponding tighter generalization bound. Moreover, our novel results extend beyond previous completeness assumptions, offering guarantees applicable to bounded hypothesis sets commonly used with regularization. This enhancement provides meaningful learning guarantees. Technically, our error transformation function serves as a very general tool for deriving FC-consist bounds with tightness guarantees. These functions are defined within each class of loss functions including comp-sum losses and constrained losses, and their formulation depends on the structure of the individual loss function class, the range of the hypothesis set and the number of classes. To derive explicit bounds, all that needed is calculate these error transformation functions. Under some broad assumptions on the auxiliary function within a loss function, these error transformation functions can further distilled into more simplified forms, making them straightforward to compute.
7 Conclusion
We presented a general characterization and extension of JC-consistency bounds for multi-class classification. We introduced new tools for deriving such bounds with tightness guarantees and illustrated their benefits through several applications and examples. Our proposed method is can
significant advance the theory of H--consistnccy bounds for multi-class classification. provide general and powerful tool for deriving tight bounds for wide variety of other loss functions and hypothesis sets. We believe that our work will open up new avenues of research in the field of multi-clas classification consistency.
10

---

References
A. Agarwal and S. Agarwal. On consistent surrogate risk minimization and property elicitation. In Conference Learning Theory, pages 4-22, 2015.
Awasthi, N. Frank, A. Mao, M. Mohri, and Zhong. Calibration and consistency of adversarial surrogate losses. In Advances in Neural Information Processing Systems, pages 9804-9815, 2021a.
Awasthi, A. Mao, M. Mohri, and Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.01550, 2021b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-consisteney bounds for surrogate loss minimizers. In International Conference on Machine Learning, pages 1117-1174, 2022a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H-cconsistnncy bounds. In Advances in neural information processing systems, 2022b.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statisties, pages 10077-10094, 2023a.
Awasthi, A. Mao, M. Mohri, and Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2023b.
P. L. Bartlett, M. L. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, (0((47))113--555 2006.
J. Berkson. Application of the logistic function to bio-assay. Journal of the American Statistical Association, 39:357 1944.
J. Berkson. Why prefer logits to probits. Biometrics, 7(4):327-339, 1951.
M. Blondel. Structured prediction with projection oracles. In Advances in neural information processing systems, 2019.
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-169, 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, G. DeSalvo, and M. Mohri. Learning 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.
C. Cortes, G. DeSalvo, and M. Mohri. Theory and algorithms for learning with rejection in binary classification. Annals of Mathematics and Artificial Intelligence, to appear, 2023.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 265222:26-2292, 2001.
K. Dembczynski, W. Kotlowski, and E. Hüllermeier. Consistent multilabel ranking through univariate losses. arXiv preprint arXiv: 6401, 2012.
U. Dogan, T. Glasmachers, and C. Igel. A unified view on multi-class support vector classification. Journal of Machine Learning Research, 17:1-32, 2016.
Finocchiaro, M. Frongillo, and B. Waggoner. An embedding framework for the design and analysis of consistent polyhedral surrogates. arXiv preprint arXiv:2206.14700 2022.
11

---

R. Frongillo and B. Waggoner. Surrogate regret bounds for polyhedral losses. In Advances in Neural Information Processing Systems, pages -1589-0 2021.
W. Gao and Z.-H. Zhou. On the consistency of multi-label learning. In Conference on learning theory, pages 341-358, 2011.
W. Gao and Z.-H. Zhou. On the consistency of AUC pairwise optimization. In International Joint Conference on Artificial Intelligence, 2015.
A. Ghosh, H. Kumar, and P. S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.
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. Wahba. 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. Mao, C. Mohri, M. Mohri, and Y. Zhong. Two-stage learning to defer with multiple experts. In Advances in neural information processing systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning defer with multiple experts. arXiv preprint arXiv:2310. 14774, 2023b.
A. Mao, M. Mohri, and Y. Zhong, Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. arXiv preprint arXiv:2310.1477: 2023c.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International conference on Machine learning, 2023d.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In 2023 Workshop The Many Facets of Preference-Bare Based Learning, 2023c.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. arXiv preprint arXiv:2310.14777 2023f.
A. Mao, M. Mohri, and Y. Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Informtion Processing Systems, 2023g.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning, 2023h.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with fixed predictor: Application decontextualization. arXiv preprint arX1v:2301.09044, 2023.
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning. MIT Press, second edition, 2018.
H. Narasimhan, H. Ramaswamy, Saha, and Agarwal. Consistent multiclass algorithms for complex performance measures. In International Conference on Machine Learning, pages 2398- 2407, 2015.
A. Osokin, F. 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.
12

---

B. A. Pires and C. Szepesvári. Multiclass classification calibration functions. arXiv preprint arXiv:160,.0638 2016.
B. A. Pires, C. Szepesvari, and M. Ghavamzadeh. Cost-sensitiis 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 in 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 a reject option. arXiv preprint wrXiv:1505.04137 2015.
P. Ravikumar, A. Tewari, and E. Yang. On NDCG consistency of listwise ranking methods. In International Conference on Artificial Intelligence and Statistics, pages 618-626, 2011.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation. 26(2):225-277, 2007.
A. Tewari and P. L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 1036))1007 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-21359, 2022.
K. Uematsu and Lee. On theoretically optimal ranking functions bipartite ranking. Journal of the American Statistical Association, 11(6119) 2017.
F. Verhulst. Notice sur loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10:113- 121, 1838.
F. Verhulst. Recherches mathématiques sur la loi d' d'accroissement de la population. Nouveaux Mémoires de I' l'Académie Royale des Sciences et Belles-Lettres de Bruxelles, 18:1-44. 1845.
Y. Wang and C. Scott. Weston-Watee hinge loss and ordered partitions. In Advances in neural information processing systems, pages 19873-19883, 2020.
Y. Wang and C. D. Scott. On classification-calibia of gamma-phi losses. arXiv preprint 2tt.:2302.07221. 2023.
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 f-measure. In International Conference on Machine Learning, pages 1 11246-11255, 2020.
T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-855 2004a.
Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(0ct): 1et.1122521111 2004b.
13

---

Z. Zhang and M. Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems. 2018.
C. Zheng, G. Wu, F. Bao, Y. Cao, C. Li, and Zhu. Revisiting discriminative vs. generative classifiers: Theory and implications. In International Conference Machine Learning, 2023,
14

---

Contents of Appendix
Related work
16
Minimizability gap
17
B.1 Zero minimizabilityy
17
B.2 Relationship with approximation error
17
B.3 Significance of (H-consistency bounds
18
Proofs for comp-sum losses
18
C.1 Proof of JC-consistency bounds with Tromp (Theorem 2)
19
C.2 Characterization of Tromp (Theorem 3)
21
C.3 Computation of examples
22
Proofs for constrained losses
23
D.1 Proof of JC-consistency bounds with gostad :i..............................
24
D.2
Characterization of [rettnd (Theorem 11).
26
D.3 Computation of examples
27
E Extensions of comp-sum losses
28
E.1 Proof of (K-consistency bounds with Toomp (Theorem 5)
................................
28
E,2 Logistic loss
................................
30
E,3 Sum exponential loss
................................
32
E,4 Generalized cross-entropy loss
................................
33
E.5 Mean absolute error loss
................................
Extensions of constrained losses
35
Proof of R-consistency bound with sett (Theorem 12)
F.1
35
F22
Constrained exponential loss
37
15

---

A Related work
The notions of Bayes-consistnnyy (also known as consistency) and calibration have been well studied not only with respect to the binary zero-one loss [Zhang. 2004a, Bartlett et al., 2006, Steinwart, 2007, Mohri et al., 2018], but also with respect to the multi-class zero-one loss [Zhang, 2004b, Tewari and Bartlett, 2007], the general multi-class losses [Ramaswamy and Agarwal, 2012. Narasimhan et al., 2015, Ramaswamy and Agarwal, 2016], the multi-class SVMs [Chen and Sun, 2006, Chen and Xiang, 2006, Liu, 2007, Dogan et al., 2016, Wang and Scott, 2020], the gamma-phi losses [Wang and Scott, 2023], the multi-label losses [Gao and Zhou, 2011, Dembezynski et al., 2012, Zhang et al., 2020], the losses with a reject option [Ramaswamy et al., 2015, Cortes ct al., 2016a,b, 2023], the ranking losses [Ravikumar et al., 2011, Ramaswamy et al., 2013, Gao and Zhou, 2015, Uematsu and Lee, 2017], the cost sensitive losses [Pires et al., 2013, Pires and Szepesvári, 2016], the structured losses [Ciliberto et al., 2016, Osokin et al., 2017, Blondel, 2019], the polyhedral losses [Frongillo and Waggoner, 2021, Finocchiaro et al., 2022], the Top-A classification losses [Thilagar et al., 2022], the proper losses [Agarwal and Agarwal, 2015, Williamson et al., 2016] and the losses of ordinal regression [Pedregosa et al., 2017].
Bayes-consistency only holds for the full family of measurable functions, which of course is distinct from the more restricted hypothesis set used by a learning algorithm. Therefore, a hypothesis set- dependent notion of H-consistency has been proposed by Long and Servedio [2013] in the realizable setting, used by Zhang and Agarwal [2020] for linear models, and generalized by Kuznetsov et al. [2014] to the structured prediction case. Long and Servedio [2013] showed that there exists case where a Bayes-consistent loss is not K--consistent while inconsistent losses can be H-consistent. Zhang and Agarwal [2020] further investigated the phenomenon in [Long and Servedio, 2013] and showed that the situation of losses that are not H-consistent with linear models can be remedied by carefully choosing larger piecewise linear hypothesis set. Kuznetsov et al. [2014] proved positive results for the H--oonsisenccy of several multi-class ensemble algorithms, as an extension of K-consistency results in [Long and Servedio, 2013].
Recently, Awasthi et al. [2022a.b]. Mao et al. [2023h], Zheng et al. [2023] presented a series of results providing H-consistency bounds. These are upper bounds on the zero-one estimation error of any predictor in a hypothesis set, expressed in terms of its surrogate loss estimation error. They are more informative guarantees 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]. Awasthi et al. [2022a] studied H-consistency bounds in binary classification. They provided a series of right K-consistency bounds for bounded hypothesis set of linear models and one-hidden-layer neural networks. The subsequent study [Awasthi al., 2022b] further generalized the framework to multi-class classification, where they presented a extensive study of H-coosistencyy bounds for diverse multi-class surrogate losses including negative results for max losses [Crammer and Singer, 2001] and positive results for sum losses [Weston and Watkins, 1998], and constrained losses [Lee et al., 2004]. However, the hypothesis sets adopted there were assumed to be complete, which rules out the bounded hypothesis sets typically used in practice. Moreover, the final bounds derived from [Awasthi et al., 2022b] are based on ad hoc methods and may not be tight. [Mao et al., 2023h] complemented the previous work by studying a wide family of comp-sum losses in the multi-class classification, which generalized the sum-losses and included as special cases the logistic loss [ [Verhulst, 1838, 1845, Berkson, 1944, 1951], the generalized cross-enirupy loss [Zhang and Sabuncu, 2018], and the mean absolute errur loss [Ghosh et al., 2017]. Here too, the completeness assumption on the hypothesis sets was adopted and their K-consistency bounds do not apply to common bounded hypothesis sets in practice. Zheng et al. [2023] proved PCCconsistency bounds for multi-class logistic loss with bounded linear hypothesis sets. However, their bounds require crucial distributional assumption under which, the minimizability gaps coincide with the approximation errors. Thus, their bounds can be recovered excess error bounds, which are less significant.
This paper provides both general characterization and an extension of (FCconssstency bounds for multi-class classification. Our general tools and tight bounds show several remarkable advantages: first, they improve existing bounds for complete hypothesis sets previously proven [Awasthi et al., 2022b), second, they encompass all previously comp-sum and constrained losses studied thus far as well as many new ones [Awasthi et al., 2022a, Mao et al., 2023h), third, they extend beyond the completeness assumption adopted in previous work, fourth, they give novel guarantees for bounded
16

---

hypothesis sets, and finally they help prove much stronger and more significant guarantee for logistic loss with linear hypothesis set than [Zheng et al., 2023].
Other related work on H-consistency bounds includes: H-cconsisennyy bounds for pairwise ranking [Mao et al., 2023d,e]; theoretically grounded surrogate losses and algorithms for learning with abstention supported by Jy-consistency bounds, including the study of score-based abstention [Mao al., 2023f], predictor-rejector abstention [Mao et al., 2023c] and learning to abstain with fixed predictor with application in decontextuallzzation [Mohri et al., 2023]; principled approaches for learning to defer with multiple experts that benefit from strong H-consistency bounds, including the single-stage scenario [Mao et al., 2023b] and two-stage scenario [Mao et al., 2023a]; FC-consistyncy theory and algorithms for adversarial robustness [Awasthi et al., 10,la,b, 2023a, Mao al., 2023h, Awasthi et al., 2023b]; and efficient algorithms and loss functions for structured prediction with stronger H-consistencyy guarantees [Mao et al., 2023g]-
B Minimizability gap
This is a brief discussion of minimizability gaps and their properties. By definition, for any loss function e, the minimizability gap is defined by
()() inf hesk (..N)-
1 [K(h ((,, 201
E
E
inf [[ v, y)] -30 - x1),
herk
B.1 Zero minimizability
Lemma 14. Let be a surrogate loss such that for (x.y) X x and any measurable function Ham, the loss 2(h, x, y) only depends on h(x) and (thus we can write E(h, x, E(h(z), for some function E). Then, the minimizabiliy gap vanishes: Mz(Ha))=
Proof. Fix e > O. Then, by definition of the infimum, for any x X, there exists ha Hall such that
E s/a
[ [
inf IE ((((,,x,))) +e.
hetKan u/e
Now, define the function h by h(z)= = h2 (x), for all e X. h can be shown to be measurable, for example, when X admits a countable dense subset. Then,
E (a.)) [(( (2.0)-D
[((h(z).))]
[((ho(z)))) (a.))-
(an)) [((h,,,,,))
$ E x
inf E [[((h,,,,)) +
he ofa
E e (Hall
=
Thus, have
inf IE [[(h, 2,11 s e (Han,, te. hefCan (2.0)=
Since the inequality holds for any 0, we have Ry (Hall inf E( [f(h, E, (HCn, This implies equality since the inequality Ri (H) 2 [, x)) holds for any H.
[ 2,,,) v)]
B.2 Relationship with approximation error
Let Ag denote the approximation error of loss function l and hypothesis set H: A,(A() R (H) - Ri (Hau). We will denote by (3) the difference of pointwise infima (H)
Eg [e] (3C, 2) e2 (Han, æ)], which is non-negative. The minimizability gap can be decomposed as
17

---

follows in terms of the approximation error and the difference of pointwise infima:
Mc(H() (30) E [et,
(90) - -R, (HCan) RR (Han) E, (e) = AA(())) + (3G.n) - EE [0] (HC -A,( E, [e] (Hall, e% (H, x)]
(By Lemma 14)
=AC(33)) Ie())..
The decomposition immediately implies the following result.
Lemma 15. Let i be surrogate loss such that for (æ,y) X x y and any measurable function h Han, the loss {(h, x,y) v) only depends on h(x) and (thus we can write {(h,z, ((h()))))) for some function 2). Then, for any loss function E and hypothesis set H. we have: M2 S (3C).
By Lemma 1, when é is the zero-one loss, Ie()() O when the hypothesis set generates labels that cover all possible outcomes for each input. However, for a surrogate loss function, ((()() is non-negative, and is generally non-zero.
Take the example binary classification and denote the conditional distribution as 77())) D(Y 1|X z). Let H. be family of functions h with [^xx)] s A for all x e X and such that all values in [-AA,+ +A] can be reached. Consider for example the exponential-base
margin loss: &(h, x, y) = >)(*), Then, <h) (T()) -h()) + (1 - (x)) (e e(*)) Upon observing this, becomes apparent that the infimum over all measurable functions can be expressed in the following way, for all a:
e, (Han, =>) (1= nx)),
while the infimum over H. (HC, depends on A and can be expressed as
(H, - max (nax(n(()11- (1=)()(1--(<))
1-
< log (xx)
I-m(a]
otherwise.
Thus, in the deterministic scenario,
Ie(3l) E, Ex(e, (HHlll x)] =
B.3 Significance of JC-consistency bounds
As shown in the previous section, for target loss fo-1, the minimizability gap coincides with the approximation error Mc,,, = Ata., (3C) when the hypothesis set generates labels that cover all possible outcomes for each input. However, for surrogate loss f, the minimizability gap is generally strictly less than the approximation error Mc(I() < Ac()).. Thus, an H-consistency bound, expressed follows for some increasing function I:
Ria (h) Ri (H) + Men- (H) s (h) - (30) M,)))).
more favorable than excess error bound expressed in terms of approximation errors:
Re (h) Ri (91) Aea. (3C) s (() R (3t) Ac()())
Here, I' is typically linear the square-root function modulo constants. When JC Hall, the family of all measurable functions, by Lemma 14, the H-consistencyy bound coincides with the excess error bound and implies Bayes-consistens by taking the limit. It is therefore stronger guarantee than an excess error bound and Bayes-consistency.
C Proofs for comp-sum losses
Let Ymax argmax,yey yey ((r, y) and ((x) argmaxx,et gey ((x, y), where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy.
18

---

C.1 Proof of HCconssstnncy bounds with Tromp (Theorem 2)
Theorem (H-consistency bound for comp-sum losses). Assune that H is symmetric and plete and that Tromp is convex. Then, the the following inequality holds for any hypothesis h E H.. and any distribution
Joomp (Rea (h) Ri (36) Me. (30) $ Rgoomp (h) Riooop (3() Mecomp (JC), (3)
with Tromp an I--sstmmation error transformation for comp-sum losses defined all [0,1] by
(t)mp
re(0.)] x 1
inf
sup
1+ ((T) - +01 - (1-)) -
2
n= 2
inf
inf
sup
P ( Φ( - -)]+ (t(((m))))))) $( [)]} n>
pe] n-T vt,1] mamax 1/.1/n) nd [1] 11*7s1l,72
Furthermore, for any E [0, there exist a distribution D and a hypothesis It E H such that Rto 1 (h) - R2 Ro (H)) + Mc. (3C) and Reomp (h) Reomm (H() + Mecomp (I() Jeomp (t).
Proof. For the comp-sum loss geomp, the conditional (comp-riss can be expressed as follows:
Cysomp (1,
Σ
p(x, v) poomp (h,, poomp v,y)
yey
p(z, v) 4
yey
E((x, v) (S,(zv)))
yey
p(x, Umaxx)
(( Umax )) + + ((S p(x, y) 1 (5,(,,))
Σ
+
yk(ymaz.h(x))
where we let Sx, Evey chla.vy for any y e with the constraint that Eyey Sn 1. For any he HC such that h(x) Imnx and X, can always find family of hypotheses {h JC
Mans)
hala.)
such that (1, Egeey ohularT take the following values:
(x, (z, Vmnax) + 4 Sn (z, h(x))
if y (ymax: h(x))
(2,p(2.v)
if y h(x)
y Vmax-
Note that Sh satisfies the constraint:
= = 1.
yey yey
19

---

Let p(z, Mmax), P2 = p(2), (z, h())) and T2 = Sa ymax) to simplify the notation. Then, by the definition Sn,r we have for any h and x
(poopp(),x))
inf [
Epomp (+)
pi (1( - - + p2(((T) - ( + p)]]
= sup ue[-12.11]
P p1 P2 (T) 4 - -1]]
P- pi P2 [M(TI) ( 2 + 191}
sup
pe[-Ta.51]
2
2
(P=p1 + P2 I v Pr - P2, 1)
P+p1 P2 P (T)((T)) Φ(T) - 1b]
$
inf
sup 1,
inf
Pe[ pe[ vpi pp.p1-P..]]]
[.2.1]2maxxxte 12m4x(22.1/m)
2
P P1 p2
-0(2
(Ti 2 max((,, 71 72 1,72,
2
= T (p1 - P2)
= =Tomp (AC
or
(by Lemma 1)
where for n 2, an additional constraint 72 is imposed and the expression of gromp is simplified. Since gromp convex, by Jensen's inequality, we obtain for any hypothesis h H. and any distribution,
Tromp (Rio (h) Rio (H) Mc. (H))
- FlACEo oe (h,,))]]
$ E [[comp (AC (h),
< E AC C. goomp H x)]
Rgoopp (h) - Riromp (IC) Mg (ft).
For the second part, we first consider n 2. For any [0, 1], we consider the distribution that concentrates on a singleton {z) and satisfies p(x,, 1) 2 p(x, 2) 1-t For any 0, by the definition of infimum, we can take E HC such that (Ir 1) T. E [0, 1 and satisfies
L:!
2
2]
1 ++
[ T.) - - m)] < <Fromp(t) te.
sup 1_[-
(T.)
4(1 p)] +
2
2
Then,
Rea (h) - R2 (3() + Me. (3() Réa (h) Ex [ee
[ (H(
Clar (h, ei, x)
and
gromp(() (1) < R Roomp (h) Ry Ri (H) M (H)
= Rycomp (h) [x [e[eemo (IC
= Croum (h,
Cpcmmo (HC x))
1+t
1-t [ [0(1-7)) D((T ((T.) --11-(1-1))
-T)e + m1]
sup
[e[-
2
< goomp (t) +
By letting + O, we prove the tightness for n = 2. The proof for n > 2 directly extends from the case when n = 2. Indeed, for any t [0, 1]. we consider the distribution that concentrates singleton 1tt
{z) and satisfies p(z, 1) 2 p(z, 2) p(x,)) 0, 3 < y For any 0, by the definition
20

---

of infimum, we can take h é HC such that (I, 1) = T1.. (x, T2.., Sz, = 3, and satisfies Ti,r + T2,c = 1, and
p+ (T((2,)) - - 4)] + p
[8(T).c) (((1),,)-((12))))) ( w)]
inf Pe| pel v1,
sup
pel Fee
2
2
1 +1
( (T2,) (TT,, ++]+ 1-1
2 (TI,e) - - ||]]
sup
T.. <JoomP(t) tc.
2
2
Then,
Rio- (h) -
(H) + Mi (H)
and
gromp(t) < groomp (t) + c.
By letting e 0, we prove the tightness for n
C.2
Characterization of Tromp (Theorem 3)
Theorem 3 (characterization of Joomp). Assume that & is convex, differentiable at 1/ and ('2)) < 0.. Then, Tromp can be expressed as follows:
((2) inf pel- +:2]( 1-t p + p)) + 1 12)(() [)]
n= 2
(tomp(t)
inf (e H] (T) - inn -inffee--,,1 ( (r 4) + 1 m) n>
Proof. For n = we have
groupp (1)
inf rE 00
sup
1+t [T(T) (11---))]
1-t
[01 ()) ( [T++
1-1
2
2
1+t t ((T)+
1-t [ -)]
[1+t Φ 1 T +
1-t
D T + (1)
inf re(o.;]
inf -c[-7,1-]]
2
2
1+| ((7)+
1- ( - -)]
1- l
1
1+ 1 1
11
inf
inf
o
11)
r0(0.2]
-
2
2 inf re(o.;]
④ [1
2
2
(1) 7 --) )
we 2
inf
[
2
+
1+t
2
2
m1
(Φ is convex)
-0())
1-t
1+t
inf
1-14
2 11
<0, ((T (
50)
2
2
2
where the equality can be achieved by r 7.
For > 2, we have
Jenmp(t) (t)
inf inf
sup F(P,T1.77
rel 2l.2. mmmax( 1/m) pe[-ram1
where we let F(P, T1, 72.14 P-t P ( Φ(π -)) ( P
क p)] For simplicity, we assume that is differentiable. For general convex t., we can proceed by using left and right derivatives, which non-decreasing. Differentiate F with respect to μ., have
OF P+ ('( n1) + P
(T2
Op
Using the fact that Pe (e(, n-1 v vt,1].t 11,t te e [o, 1] and E' is non-decreasing, we obtain that aF is non- du
increasing, Furthermore, 4' is non-decreasing and non-positive, &b is non-negative, obtain that
21

---

('(00) = O. This implies that 0F (+00) 0 and Of (-00) 2 0. Therefore, there exists pu é IR such 8y
that
OF
0u (po) = + & (π MD) + t-P Φ (T2 (o) = 0
2
2
By taking μ Ti 72 and using the fact that T2 2. (2)) < we have
aF
p+t
t-P 2 (T( <0.
0z ( T2)
4 (2))
2
2
Thus, since OF is non-increasing, we obtain po 8u
< TI T2. Differentiate with respect to 72 at po.
we have
OF
p+t D
V'(12 po). t-
(T2)
Since 4' non-decreasing, obtain
θT 5 1
OF p+1 (
+
L-P
1 -
0F
0p (T T2) < <0,
2
which implies that the infimum inf 2max(ra. is achieved when T2 Tı Differentiate F with respect P at pu and Ti T2, by the convexity of we obtain
OF
Op (TT) ④ pa) (TT) - + m4) s 0,
which implies that the infimum inf re[ ...,,]] .1] is achieved when P = 1. Above all, we obtain
(tomp(t) (t)
inf sup F(1, re [
1+
1-t 4 m)) ( -p)
inf + uel uc[-r.F]
((T) inf
2
C.3
Computation of examples
Example: ((t) -oog(t). For n 2, plugging in ((t) log(()) in Theorem 3, gives
1+t
log 2 m) -
gromp loog 2
inf Me| ul1---11
log
2 + 14)
2
2
1 1+ log( + +) +
1-
log( - t).
(minimum achieved at μ -b)
2
2
Similarly, for n > 2, plugging in ((t) -lo((()) in Theorem 3 yields
{
1-6
1+1 log( r 10)]
gromp
inf re re(
log T inf
log(r + (p)
pc[-7.7]
2
1 t log(1 (1 +t++
1 1-1 t 2
log(1 tt).
(minimum achieved at 1r -Tt)
Example: (tt)
1. For 2, plugging in +ft)= in Theorem 3, gives
1+t 1
Joomp 2
inf
na 2
2
2
+
2
(1-1)2-(1+0)
1
(minimum achieved at μ (1=1) (
Similarly, for 2, plugging in 4(t) = - in Theorem 3 yields
[1 [1+t 1
1+t T+
goomp
inf
inf ne[-T,]]
Te [
2 T
1
inf
/1
(minimum achieved at μ (1-0)=+((-0)3-
x 2r
=1- 11-vI-1t
(minimum achieved at 7 ==
22

---

Example: (tt) (1-t"), (0, For n = 2, plugging in (
1 ({1=tt) in Theorem 3,
gives
1+ t
)
gromp
inf
+1
14)
q2a
μe 2.2
29
2
29
2
1-9
1 (1+t) 1-9 (1 t)
1-1
929
929
(1-1) -
(minimum achieved at
2 ((11 ((
Similarly, for > 2, plugging in .(t)= (1 19)
in Theorem yields
Jeomp inf
7"
inf ne[-T,T]
1+1
(T-1))
un)
1-4
(T (T+1))))
re [.
2q
29
(1+t) -o + (1 - t) l
1-9
T
inf
re 2.
q
2
(minimum achieved at μ (--))-ar-(11 (1
(1+t) 1- +(1()) _ 7)
1-q
1
(1+ 1-4 + (1 (1-t) 1-0
(minimum achieved at T
qm9
2
qnd
Example: ((t) 1- t.
For 2, plugging in @(t) 1 - in Theorem 3, gives
1
1 1-1
1
1-t
gromp
inf
2 (1)
2 2 [1
= 2 2
2
pd
-
Similarly, for 2, plugging in ((t) 1- in Theorem 3 yields
[1+
1-t w)-
Jeomp_
inf
(1 (1-7)-
inf p
+ (1-T+
2
=
inf re [..1
rt
(minimum achieved at = -T)
t
(minimum achieved at
n
Example: (()) (1- - 1)2.
For 22 plugging in +(() (1 (1= in Theorem 3, gives
gromp 1
1- t
1+t 1
2
1
1
-
t2
t²
inf 212
11
+
pc
2
2 2
4
Similarly, for 2, plugging in ((t)= (1- 1)2 in Theorem yields
gromp_
inf
(1 (1-7)²- inf
[1+1
(1 (1)++ 1- (1 (1-7- =]
7C []
pe[-T.r]
inf ((1-
(minimum achieved μ = U(T 1))
re [
(minimum achieved at 2))
D Proofs for constrained losses
Let Ymax argmax,eyy yey ((ay)) y) and (ax) argmax,est bey h(x, y), where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy.
23

---

D.1 Proof of H-consistency bounds with Festad (Theorem 10)
Theorem 10 (HCconsistencyy bound for constrained losses). Assume that H symmetric and complete, Assume that Jestnd is convex. Then. for any hypothesis h E H and any distribution,
Jestad (Rea.. (h) Ri (3C) + Me (30) s Reeardd (h) Rianaa (3C) + Mieand (3()
with H-estimation error transformation for constrained losses defined t [0, 1] by Festnd (t)
inl sup
Int [+(([]])--)]])) 4(-T+ 1 (-T) - +
n1 = 2
r20 peR
2
inf Pel [e ": 1:2max(T2.0) pel
inf
sup 20-22---- 1 ( p)] 2-Pt ( ( [)]] n 2.
Furthermore, for any 10, there exist distribution D and hypothesis h. H such that Rio (1) - Ry (H) + Me, (3) = I and Reossa (h) fosana (H) + M (H) = Tratud(1)
Proof. For the constrained loss gestnd, the conditional gostad risk can be expressed as follows: Σ p(z, y) pestnd (h, y)
Cpearud ( x) =
yey
Σ p( v) Σ @6 ((-h(zzz))) yey
v'ay
Σ Φ ((-h(I,))) Σ p(z,1') 8'+0
Σ Φ Φ(-h(I, 8 (1 p( v)
$ (-h((x, Mmax () pl xr Ummos) - Σ
ye( (())
For any h e H. and x X, by the symmetry and completeness of H, we can always find a family of hypotheses {hr : u. R} HC such that (x,-) take the following values:
h(x.y)
if y (ymax h(x)}
(z.
h(x, Urmax) + p
y hax)
h(x, h(x)) - if y Fmax-
Note that the hypotheses hn satisfies the constraint:
(x,z) = Σ h(x y) = 0, V R. yey
yey
Let P1 = p(I, Mmaxx), P2 p(x, h(x),, T== h(x, h(z)) and T2 = h(I, Vlnax) to simplify the notation. Then, by the definition of hup, we have for any Hi and e X,
Exeaia x1,
inf Cgeind (1) Nez
(1 - p1) (0- [)] (1 (-1)))))(--n---------- -0((12--1)))0)0 1011
sup
peR
2- P - p1 + p2
2- 4-P+pi P2 ( 40 m0]
sup pel
( +
2
(P=p1 + pa E 1.
2 P P1 P22 (T(=2) (0 + +1))
inf
inf
sup
Pe[ - 1] n 72max( (2.0x(72.0) peR
2
2 2- P pi PP2 -
- 00- m11
0,22,55
2
- (pi -P2)
- Jostnd (ACadddAAooaaaa (AC(o..)c(h,xx)))
(by Lemma 1)
24

---

where for n 2, an additional constraint 0 is imposed and the expression of Jeomp is simplified. Since Jestad convex, by Jensen's 's inequality, we obtain for any hypothesis h 36 and any distribution,
grestnd (Rio-1 (h)
Ri Ri (H) Me.1 (F))
= gestnd
E
AC 3e
3e (h,
$ E
Jestnd
E2
Aorund Crreunddr((/ (h,
X
Rootnd (1t) Recat (H) Mggernd (H).
For the second part, we first consider n = 2. For any t [0, 1], we consider the distribution that concentrates on a singleton (x) and satisfies p(z, 1) = 1+f
I-t For any e O, by the definition of infimum, we can take E HC such that h(r, Te 0 and satisfies
2 p(r, 2) 2
11 (TTT)) *(-Te +
1+t [ (-(.))
:(Te - -001 <
sup WER 2
Then.
1 - -R (3) + Me. (3) = Rio (h) - Fx Ex( (H,
= Cto (h, x) e/a, (H,
= 1
and
grsstnd (t) Reasnd (h) Rgoannd (H) + gennd (JC)
R possna (h) Ex (erond [H,
Cyenne (h, x) - Cponnal (H,
[TT) ( p)] 1 -(T. [0]]
sup peR
Trsttdd
+..
By letting 6 0, we conclude the proof. The proof for n directly extends from the case when = 2. Indeed, For any E [0, 1], consider the distribution that concentrates and satisfies p(x, 1) 1+t p(x,2) of infimum, we can take h e DC such that h(z, 1) = Ti.., h(x, 2) T2.e, h(z,z) y) = 0, 3 < S n and satisfies T1, + T2, and
singleton {x} 2 p(x,)) 0, 3 S S For any >> 0, by the definition
I-
2 P -
2 P
(--Te))) (- w)l
inf sup Pe[ P
(--22)))
4--T1, x)]+
1] peR
2
2
1-t t
1+t
(--TI,)) $0- m)]
sup
[ ( ( 4)]
nek
2
< Festnd
(f) +c
Then,
Rio (1) - -Ri MM (H)
and
gestud (1) s Rpoand (lonmnd(h)-- - RRgonnd (H) + M gomed (H) grstud (t) +
25

---

D.2
Characterization of Festnd (Theorem 11)
Theorem 11 (characterization of Jestud,, Assume that & is convex, differentiable at zero and ((()) < O. Then, Testud can be expressed as follows:
(())- inf peR (1) + 2 1 (-1))
n 2
gratad())
inf (2 n ) inf
pell
2+t- 1- o p(- w)) 1 (-T (-T++1)++
n> 2
((0) inf uell { 1-t (1)) + 1t! {(H+1}
n=
2
iin ( 122
2-1 ( (2)
2+ 1 (-T-
n> 2.
2
Proof. For n = 2, we have
gestud (1) = inf sup
1-1
(T) - -((-++
+
1tt
((T)) - (T - 10)1 -1)]
+20 pei
2
2
1 1-t
((T) + 1+t [
1
1+t D(T - 1))
inf
(((r))]
inf
Φ -T + +1)
720
2
2
PER
2
2
1 1-
(T))+ + 1 1
1
1+1
inf
[
[0(-))]
inf
(2)
(1111)
720
2
2
peR
2
2
2 inf ($(() - 44 (0) inf
1
(11)
1
1+
(-11)
($ is convex)
r20
ne8
2
2
1+
= 4 (0) inf
2 (1)
4 (-11)
(0' < 0, tu 2))
pek
2
2
where the equality can be achieved by T= O.
For > 2, we have
gostnd (t) = inf inf sup (I,,T, 12,
p mm) peR
where we let F(P, TI, 72, 2 (- 0(- p)] 2-P ( 20-22-(212)))) For simplicity, we assume that & is differentiable. For general convex T we can proceed by using left and right derivatives, which are non-decreasing. Differentiate F with respect to μr, we have
OF P+t
0 B'(-TI + u) 2- P 8 (-)22-1)).
2
Using the fact that P E [ 1).t [o,1] and o' is non-decreasing, we obtain that 8F is non- By increasing. Furthermore, Ø' is necrdecrggn and non non-positive, +b is non-negative, we obtain that & (++o))= = O. This implies that or that
(+o0) 0 and OF Bn
(-o0) 2 0. Therefore, there exists po e IR such
Bp
OF
= p- क' (- + Mo)
2 P
0μ (Po)
o (-T-222 1o) =
2
2
By taking μ Tı 72 and using the fact that 1' F((1) 0, we have
OF (T T2) P+t 2
2 (-T2) P + D' ('(-1))< <0.
0u Thus, since OF is non-increasing, we obtain 1o Ti T2. Differentiate F with respect to 72 at No. op
we have
OF P+t-2 0 (-Tz)
2 P
2'(-T2 mo).
OT2 2
2
Since d' is non-decreasing, obtain
OF
P P=t-222 ((TT))
2 2-
P
OF
71
(T) - T2) < 0, 0μ
Or2
2
which implies that the infimum inf r, 2m2xx 0) is achieved when 72 = =1. Differentiate F with respect to P at Mo and 7 T2. by the convexity of Q. we obtain
0F
ap 4 po) ((-7)) - ( + ( - -o) 2 0,
26

---

which implies that the infimum inf Pel Pep [1
is achieved when P= _ n-1
Above all, we obtain
gratnd (t) = inf sup F
11 1n-1 1T.
720 peR
1
1-
2+
n-1 Φ(-T -T m2))}
inf 2
1 (b-r)
inf
n-1 4 (1-
720
2
2
2 inl sup F(0, TT)
r20 peR
2
2+1
$ -T 11)
inf ( 720
- inf wER
D -T +1)+
D.3 Computation of examples
Example: (()) Pexp (1) = e
For 2, plugging in &(1) e- in Theorem 11, gives
1
1
1
gromp
inf
6
6
WER
2
2
= t.
(minimum achieved at - log +::
For n > 2, plugging in (t) = e Theorem 11 yields
2 e-Tu
2+
gromp
2 inf 2c²
inf MeR
+
cttu
r20
2
2
2
2-t
2+t
2 2
inf
-M
E/
(minimum achieved at 0)
2
= V 12
(minimum achieved at fu = log 2-1
2+1
Example: ((t)
4 Phinge (t) = max 1-.. For n = 2, plugging in 4(t) max (0, 1 1-t) t in
Theorem 11, gives
1-t ma 1-4)
1+t ma m3
gromp 1 inf well
=t.
(minimum achieved at -1)
For 2, plugging in ((t) max (0, - in Theorem 11 yields
inf 2 max (0, 7) - iinl 22-t uel
2++
max (0, 10,1+770 (0,1+++p))) + mi]]
Jeomp
-1) max (0, 7
r20
2
2 inf HeR
2 max 1-.x6001110 n1 +
2
max 1 ++]] 10,1+1]
(minimum achieved at r = 0)
2
2
=t.
(minimum achieved μu -1)
Example: ((1) D hingo (1) = (1- 11 For n = 2, plugging in ((t) = (1 - 2 es1 in
Theorem 11, gives
goomp = inf [1 - (1 11) usa I
1tt (1 11 1
HeR
2
=t?
(minimum achieved at μ -t)
For > 2, plugging in ((t) = (1 - 1)²
tsl in Theorem 11 yields
2 2- t
2+t (1 (1+T+ (1)++++)2))0 1 mm
geomp 2 inf 2(1 7) 1 inf
(1 (1+T- (++r-1)) -r-ust
+ 11)
T20
ueR
2
2
2 1
2+1
2 2--in inf
(1 11) 21
psd +
(1 11)
(minimum achieved = 0)
Nel
2
2
(minimum achieved at p= -
2
27

---

Example: ((t) =tq = ( (1-t)?.
For nt 2, plugging in @ = (1-t)² in Theorem 11, gives
Jromp
inf peR
(1 - =1)=
1+t
2 (1+ 1)²
=12
(minimum achieved at μ = -t)
For n > 2, plugging in ((t) = (1 - 1)² in Theorem 11 yields
2-t t (1+T- -1)= 2+t (1 (1+ m)²
gromp
2 inf 2( + 7) 2- inf μel
2
inf
2-t t (1 - 11)² +
t
(1 + 11)2)
(minimum achieved at = 0)
ueR
2
2
(minimum achieved at μ -
2
E Extensions of comp-sum losses
E.1 Proof of H-consistency bounds with Toup (Theorem 5)
Theorem 5 (H-connistency bound for comp-sum losses). Assume that J Jomm is convex. Then, the
following inequality holds for any hypothesis l E H and any distribution:
Jomp (Re... Ri (H) Mig- (3() Rgoop (h) Reeoom
(H) + Mgramp (H)
with Fromp Toomp
the --estimation error transformation for comp-sum losses defined for all t [0. 1] by
inf sup re(0, pe (ustn 1, 7-1---mmin inf
2 ((((((T ((0(7))((11-00) +(1 [0 2 [1]]
n=
inf vt.1] Smin <725T1 Smaax Ti 71
sup
Pot ( 4 [d] ( क( m)]] 2,
Pe[ ve.11
peC
where C [max (smin T2, T1 Smax] m Smax T2, T1 Smin]] Smax 1+(n-1)e-2mt, AG) and
8min I+(n-1)e2ims MEJ. Furthermore, for any L [0, 1), there exist a distribution DD and h H such that Rio., (h) - Ri (H) Me (H) and Rgeomp (h) - R (HC) Mgcomp (H) Tromp (t).
Proof. For the comp-sum loss geomp, the conditional gcomp-risk can be expressed as follows:
Creum (h,
Σ p(z,1) geomp (h,
yey
Σ (p(,,y) y wey
Eveey chlaw))
Σ p(, y) (Sx())))))) wey
=p(z, Mmaxx (p (z, Vmmaa)) p(,, ((S
Σ p(z, (lc.))((S1) (s,()))))))))))
(e(Mmax.hha))
(a
where we let Sp. (x,z) that for any h E JC.
Eysy ehtrr for any y e y with the constraint that Eyey Sh(z, y) = 1. Note
A(x)
((x)
1 (n 2) e-A( + (n Ma) S (x(zz))
Mx) + (n - 1)a 1 (n e)e-22e2 2N(x)
Therefore for any v) X y. Sh Sn,x,, y) [Smin: Smax), where we let Smax [+ 1)e 2xtzr and Smin 1+(n-1jeRM(3) Furthermore, all values in [mmi: Smax] of Sn, can be reached for some h e H.
28

---

Observe that 0 I Smax Smin $ 1. Let Umax argmaxyey p(z, y), where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. For any h H such that h(x)) Umax and x e X, we can always find a family of hypotheses (h₂ c H. such that a²y(=n)
pn, (x,)) Eveny Eveye" c
take the following values:
Sh (x,
if y (ymax: h(2)3
Sh.p (2,
Sn (r, Munaxe
if y = h(z)
Sn h(x)) -
if Vmaxx
Note that Sh satisfies the constraint:
(n v)
-E (x,)))
yey
yey
Since (z,) v) [Smin Smax], we have the following constraints μ.:
Smin - (1, Vmmx) S p Smax Sp, (Z. Ymax) (,,x,(22) S maxx U... S1, h(x))())))))))))))))) Smin.
Let P1 = p(2, Vmax), ) P2 = (()), notation. Let C' = {HE I: verify constraint (7)). Since Sp (z, h(x))())-))))))))))))) Smax S S Smax Sn (I, 3mmxx) and Smin S₁, (z, Vmax) I (z, h(x)) - Smin. C is not an empty set and can be expressed as C [max{ S T2, Smax), m 72 }.
(z, and = Sy (I, ymaxx to simplify the
Then, by the definition of Sh, have for any h H and e X.
Cream (h, x) inf Cpcomp (My:: 2))
Nel
Pı (T2)) - (6(TT-110))) p2(]++)((())))))))))))))))))))>) 4( 101
sup μeC
PP+p1 P2 [ 4(TI - -+]]+
P-p1 P1 + P2 [ - 2 + w))]
sup
2
2
ucC
(P=p1 + + [+=l] v p2, 1)
P P1
P2 ( $(11 11]
inf
inf
sup μEC
Pc[ T. [ VP1-P.
S S S.5aaxx Ti 7147251
2
P P1 P2 (T((T) OTT + n)]
(Smin 52 ST Smaxe 71 + 72 $ 1)
P+ P1
P2
inf
sup Smin ST255 S uel 717751
inf
| (T2) 4(TI -1)
Pe| Pe[ VP1-PPP--
-P2.1]
2
P - P1 + p2 (d((T)
+
( - (1 [1]
(Smin S Smin S Smax S Smax)
2
= -comp (p1 -p2)
(ACmppAAta.i. (AC z))
(by Lemma 1)
where C = [max(5min 72, Ti Smax ) min (8max T1:71 8min)] c C, Smax I-(x-1)e 2indy Maj
and Smin (mn A Note that for 2, an additional constraint T₃ + T2 1 imposed and
the expression can be simplified as
Cocomp (1, - inf Cremm (he 2:) μeC
1 P1 P2 [T(T) - (((7))((111)))) - 7- -11)]+
1- + P2 ( -7 Φ(T m2]
2 inf re(0. 4 pel Mmtm
sup
2
= = (pi - p2)
= Joomp - (C
(by Lemma 1)
29

---

where we use the fact that Smax Smin 1 and P = 1 when = 2. Since Tromp is convex, by Jensen's s inequality, we obtain for any hypothesis E H and any distribution,
gromp (Rea-1 (1)) Ri (H) Men (H))
Tromp
E FLeen 30 (h,
$ Teomp (ACro ,,0((1,2)))
$ E A gromp s Ce [))
X
= Rycomp (h) - Ricomp (IC) My (JC).
For the second part, we first consider n = 2. For any E [0, 1], we consider the distribution that concentrates on a singleton {a} and satisfies p(x, 1) 2 p(x, 2) 1-t For any e 0, by the
definition of infimum, we can take E HC such that S (z. 1) T. E
[0,
1 and satisfies
2
D(1 - - -+]+ 2 + (((T))
[ - T.)) 2 + 10]] < <rommp(t) (t) +
sup
Mel Smin Te, smin
2
Then,
Re (h) - (h) Ri (IC) + Me., (30) = Reo (hi - Ex e (H)
= Cla (h, x) C%a (H(
and
Jromp (1) s Reomp (11 - Recomp (H) Mocomp (H)
= Rgoomp (h) Ex [C2comp [H,
Creum (h,x) Cx caomp (H,x)
1 ++
1-t (1- x)]+ (T()))
2 [ Te) 2T mi]
sup pe[#minn --. Smin
< <Tcomp (1) +
By letting c 0, conclude the proof. The proof for n 2 directly extends from the case when
n = 2. Indeed, For any E [0, 1], we consider the distribution that concentrates on a singleton {z} 1-t and satisfies p(x11)= = 2. (x,2)) = L't p(x,)) .,x, = 0, 3 S y S n. For any e <> 0, by the definition of infimum, we can take h E H such that Sn = T1.e (2, 2) T2, and S, (x, 0, 3 y
and satisfies The -2, 1, and
P+t
P-t (T(TT)) D( + w)]
inf sup Pe[ vt, pcc
[ (T(22)))
- 1)]
2
2
1
1 (TT.c) (TT,, - -w)]+ 1-1
[T(r)) $1 +11c+ w)]
sup peC'
2
< (t) +c
Then.
Rio (h) - (H) M4, (H) =
and
Jeomp (t) S Rg (f) - Ri (H) Mpoup (H) < Tromm (t) +e.
By letting 0, we conclude the proof.
E.2
Logistic loss
Theorem 6 (H-consistency bounds for logistic loss). For any h E H and any distribution, we have
Reo (h) Ri... (F) + Me.. (F) S v-1 (Riior (1t) - -R (FC) + Meno (Tt).
where liog - log Eyee and ((())
(a.,)
1-f log t) + I
2
2
(1-(1-t)
t
-mma-Smit
#min+
log
Smax Smnn
+ log
2- Fmaux Beiin Smin
otherwise.
30

---

Proof. For the multinomial logistic loss Elog. plugging in ((t) - -log(t) in Theorem 5, gives Trom
P (=)g)(T2) log(Ti (1 [4] P II [ol((())) log( [)]
inf Pe[ ve., Smin S S peC
inf
sup
T
where = |max ( (min 72:71 8max) ), m Smax 72, 71 - Smin Here, we only compute the expression for > 2. The expression for n 2 will lead to the same result since it can be viewed as a special case of the expression for n 2. By differentiating with respect to т2 and P. we can see that the infimum is achieved when 71 72 Sams and P modulo some elementary analysis.
Thus, Tromp
can be reformulated as
Joomp
sup GeC
1+ f
log
5mn Smax
log
Smin 9max
14 }]
2
2
/.
8min + 8max
Amin + 8max
log
log
p1)
2
2
2
8min + Smax
log
+ sup ((A) HeC
2
where C = Smin Since g is continuous, attains its supremum over a compact set. Note that is concave and differentiable. In view of that, the maximum over the open set (-o0, +00) can be obtained by setting its gradient to zero. Differentiate g(u) to optimize, we obtain
and g(n) 1+f log( Smint
2
11) 1-t log(
2
+ 11)
t(smin Smax)
g((² = 0,
2
Moreover, by the concavity, (()) is non-increasing when μ 2 n² Since 8max Smin 2 0, we have
n¹ SOS Smax Smin
In view of the constraint C, if 2 6min the maximum is achieved by f μ=" Otherwise, if ud #maxy since (()) is non-increasing when μ p", the maximum is achieved by μ Smii Smax Since p² 2 Emin Smax is equivalent to Amax-
the maximum can be expressed
smin " Smax
s()) (9(H()
t S
Smax--mm
max
HEC
(g( Emin Smin -8max
otherwise
Smiu tmaax
Computing the value of at these points yields:
1+t
(1 + (5min + 9 m
1-t log
(1 - (Smin + mmax)
g(u")
log
2
2
8 8min
8max
1+
log(s (max)
1-t log(smins
2
Then, if
Smax -imin we obtain
Smin +Smax
ccomp
=olog 8min + 8max
+ 1 log
(1 ()(min 8max)
1-
log
(1 -1-18 1) (mmi 8max
2
2
2
1 1 log(1 (1 +))
1-
log(1 t).
Otherwise, we obtain
cromp -lg
8min Smax
1+t 1og($maxx)
1-
(Smi))
2
2
2
8max
2 Smax
log
log
Smin
Smax + Smin
Since cromp is convex, by Theorem 5, for any E H and any distribution,
Réa (h) - RR, (IC) Me,. (It) w-- " (h) - -R (IC) Menc (3()
where
1st log(1 + +1)+ + 1-t log -)) log
1.
Smaze Santrs
((()=
Smin +hmax
fmax Smin
+ log
2maa Smin Smax + Smin
otherwise.
31

---

E.3
Sum exponential loss
Theorem 9 (H-consistency bounds for sum exponential loss). For any h E H and any distribution, v VV- (RREOp()) (1)
R -
Rio. (H) Men1 (H)
Ri H
M MonD
(
where lexp = Eyjty e )- and v((1)=
+6
min otherwise.
Smntr /
(Smaxe-Pmin)) Smin))
28 Stain
ma Smin (Rmax 5mmnn
Proof. For the sum exponential loss lexps plugging in +(t) = 1 in Theorem gives T
comp
P
P-
2 inf
inf T147
sup peC
Pe[ vt.1] Smin
2
T2
2 1I 12+
where C'= | I {minn 72: Smax) ). f Smax 72, --inn] Here, we only compute the will lead the same result since it can be viewed as special case of the expression for n 2. By differentiating with respect to 72 and P. we can see Smin +mmax and P modulo some elementary analysis. 2
Smin]]
expression for 2. The expression for
that the infimum achieved when T T2
Thus, Tooup
can be reformulated as
comp
1 t
sup ueC
Smin + Smax
8min + Smax 2/1
1
- t
Smin 8max
Smin 8max 2/1
2
+ sup (p)) peC
Smin Smax
where C = Smin - 9max Smna 8min and g(H)=
8oa=+tmax-22 Smmn Smaax + Since is continuous, compact set. Note that concave and differentiable. In view of
1+t
1-f
it attains its supremum that, the maximum over the open set +o0) can obtained by setting its gradient to zero. Differentiate s(4) to optimize, we obtain
Smin + Smax -I-t-VI+E
s(p"==0, =0, p
2
VI+++VI-E
Moreover, by the concavity, (2)) is non-increasing when μ n². Since Smnx Smin 2 0, we have
n¹" 2 0 8max 8min
2
In view of the constraint C, if 4t¹ > Swin Sman, the maximum is achieved by μ n², Otherwise,
if 1t" Smin -Bmax since ((1) is non-increasing when μ n²,, the maximum is achieved by "max - min -
Smin 8max, Since μ² 2 Smin Smax is equivalent to t 2
the maximum can be expressed
(u)) (9((") (g(
2 otherwise
max REC
Smin [mmm=8max
Computing the value of these points yields:
2
g(1²) ) =
Smin 8max
min
Smax
1 + t
1-t
28max
28min
Then, ift <
we obtain
42 422 min. maxe
comp
V1-
2
Smin + 8max
Smin
1 V1
32

---

Otherwise, we obtain
comp
2
1+t
1-t
Smin
Smax
28
28min
Smax
Smin
(Smax
Smin
28 min
max (5 + Smin)
Since Toomp is convex, by Theorem 5, for any h E H and any distribution,
R (h) - RRa. (3) Men- (H) v v- " (h) Rinn (3() Mexs (3)),
where
Smun Suin min +
F2
(1()==
Smax SSmiu 24 Smii
(Smas Smin)
otherwise,
29max Smin (Smax *8min))
E.4 Generalized cross-entropy loss
Theorem 16 (H-consistency bounds for generalized cross-entropy loss). For any h E H. and any distribution, we have
Rio-1 (h)-R% (H) + Men1 (H) s v VV- (1) RR ( Megr (H)):
+ )o
(1+ (- +(1-0))
1-y iiin
t
I uttmmu
where (t)
Fmim
and fgee
88 mmax min)
mmnn to
Smain Smax
)*)
otherwise.
((.,)) Eyeoy chicrwo
99
Proof. For generalized cross-entropy loss Egee. plugging o(t) = - (11-))) in Theorem 5, gives Tromp
P 1
1
P- t 1 (T.)* + ( #) q
2 inf Pe. vt,1] Smin SrgerisS 5S HeC 71t73l
inf
sup
(T2)
- (n -n)
q q
where C = [max(s
T1 8max) ). min mmax T2. Ti mmin Here, we only compute the will lead to the same result since it can be viewed as a special case of the expression for n 2. By differentiating with respect to T2 and P, we can see &Smax and P modulo some elementary analysis.
Smin].
expression for 2. The expression for
that the infimum achieved when T 72
Thus, comp
can be reformulated as
comp
1+ t
Smin + 5max
Smin + Smax 11) )
sup nec
+
2g
2
1 /
8min 8max
8min Smax 11) [)]
+
2q
2
1
Smin 8max
+ sup sup g(H) WEC
2
where C= | Smmin=-aaa Sumns Smin and g())=
Smin SminttSas -1)²+ 1-t Smin 1)) Since 2g
2q
continuous, it attains its supremum over a compact set. Note that g is concave and differentiable. In view of that, the maximum over the open set (-o0, +00) can be obtained by setting its gradient to zero. Differentiate g(4) to optimize, we obtain
((x")= =0, /²= (1-t)=++ (1+f)I+ 8min 8max
(1+1)T+ (1-+++++1+11
33

---

Moreover, by the concavity, (()) is non-increasing when μl p². Since Smax Smin 2 0, we have
μ0" 55 $max Smin
2
In view of the constraint C, 2
the maximum is achieved by jr f=" Otherwise, u < Smin--mme Smax since g(4) is non-increasing when 1², the maximum achieved by
Smin 1minn-Baa
2
Smin
Since n 2 is equivalent to /
Smax 11-9 min +5max
-s the maximum can be expressed
((1) (g(ue)
1-g 1-g main - otherwise
max
"iin
MEC
( (
Computing the value of these points yields:
(1+ (1+ 1o (1-t) 1-0 1-9
1
8min + Smax
g(0")
2
Smin
Smax
1 +
1-t
g
(5max)
(smin)
2q
2q
1-g
Then, if / S
we obtain
8
1-2
min +8max
1-9
comp
8min + 8max
(1+1) ro (1-1)
1
8min + 8max
q
2
2
9
2
1-9
1 8min + Smax
(1+1) Tv + (1-1)
-1
2
2
Otherwise, obtain
g comp
1
(
Smin + 8max
1
(mmax) +
1-1
(smin)"
9
2
29
29
t
9
1
min
+ S
max
|mmi + 8max 8
2q
max
min
g
2
2
Since Trompp is convex, by Theorem 5, for any E H and any distribution,
Re (h) - RRe,, (3t) + Men, (It) s v (Regon (h) - RR (H) + Mera (H)).
where
1-g
1 Emin Eimint )ol (1ee) (1-2)
1-g - I-q puin
(t))
2
mmin Arann
Shax smin)
2e to {
Amin Smax )9)
otherwise.
2q
E.5 Mean absolute error loss
Theorem 17 (H-consistency bounds for mean absolute error loss). For any h E H and any distribution, we have
2(Re (h)
R7 Eane H + M,
M. mone H))
Re (h) -
(H) Me, (H)
8 8max
8min
Proof. For mean absolute error loss lmacr plugging (+() in Theorem 5, gives T Trmmp
P+t
[-(72) + (Ti - -n)]+ P-t (T2+ ((2+)))((+
inf inf
sup
Pe[_ - vr,1] Smin Smins S.max HcC
2
34

---

where C' = [ 72: 71 Smax ). min ( ( Smax 72. 10.71-min]]. Here, we only compute the lead the same result since it can be viewed as
Smin
expression for 2. The expression for n special case of the expression for n > 2. By differentiating with respect to 72 and P. we can see that the infimum achieved when Ti 72 Sman +8max and p modulo some elementary analysis.
2
can be reformulated Thus, Joopp
T
comp
sup μeC
1 1+(
8min 8max
8min 8max
11)
2
1 t
Smin + Smax
Smin + 8 Smax
+
+
2
2
sup ttp WcC
where C'= Smin Sama C' can be achieved by
Sama - Smin
J. Since tt is monotonically non non-increasing, the maximum over
f Smin
Smax
comp
Smax
8min
Since T convex, by Theorem 5, for any e H and any distribution,
Rig (h) Ri (H) Me. (H) s 2(RR_.... mmc (h)
R7
H +
M.
H))
Smax
8min
Extensions of constrained losses
F1 Proof of H--consistency bound with Jettad (Theorem 12)
Theorem 12 (H-consistency bound for constrained losses). Assume that Testnd
is convex. Then,
the following inequality holds for any hypothesis h H and any distribution:
F (Reo-1 -h)- Ri.. (H) Me (H)) s Reenta (h) - -Rieaand (HC) Messud (H). (6)
with J gastnd the K-estimation error transformation for constrained losses defined for all t [0, 1] by T gestad (t)
inf r20
sup ue(r-Amin Amins Amin]
1-t (T( +(-T [d]
inf
inf
sup 2-
(1 1- (- p)] ( (- n)] n 2,
Pe| .1] 1 112 0) HeC
where C' = [max(TI, -T2} - Amin min 71, - + Amin] and Amin = inf A(x). Furthermore, for any [0, 1], there exist a distribution D and hypothesis H( such that Re (h) -R; (3()+
Mr. (H) l. and Rpeatna (h)
RR gearadd (H) + M (H)) = =restnd()
Proof. For the constrained loss gestnd the conditional gostnd -risk can be expressed as follows: Σ p(z, y)( eestnd (h, v)
Cgeatma (z,
vey
Σ p(x,y) y) Σ ((-h(s,,')) wey
Σ Φ6 (((-((x))))
Σ p(z,)') 8'+9
wey
Φ 16(-h(z, v)) p 9))
yey
((-1(( Vmax (1- )max) M0h
Σ
2 ((-N(2.)))
ye ((()))
35

---

For any h E Hh and x E X. by the definition of H[, we can always find a family of hypotheses { = 3 such that (x,-) take the following values:
y & (Ymax, h(m))
(2, =
h(x, Fmmxx) + p
if y h(x)
14 h(r, h(x))) -1 if y Vmax-
Note that the hypotheses hy satisfies the constraint:
Σ (x..))
Σ (xx, 0, VueR R. yey
yey
Since
(.)), we have the following constraints on μ.:
-A(x) (xxx Vmmax J.s. A(x) (mxx))
A(x) h(z)) & f A(x) h(2,,(z).
Let P1 = p(x, yhmax), P2 = p(a, herhh(()))))))))))))) TI h(:))())))))))) and T2 = 1( Ummax) to simplify the notation.
Then, the constraint μ can be expressed
e C, C (ma
min -72) + A(x)]
Since max mi, -22) 1 + 72l s|1l+
1//l+/// < C not an empty set. By the
definition of Nyh we have for any h é HC and x 6
Exextnd (h,x) inf Epentnd (1)
WeC
(1 - p=)[(((TT)) (0 + ++] (1 p2)[ - -0-722 w]1]
-
sup
weC
P--P- P p1 P2 (1)()) +0(-T++11)) 2 P-P+p P2 [ 4 m)]
sup
2
(P= + P2 11
2 P p1
inf
inf
sup
[ ( (--1++++
Pe[ A _1] n n2maax(22)) (72.0)
2
μEC
2 P + P1
P2
2 (1) 40-T2-2211 W)]]
(720075))
2
2 P- p1 + P2
2
inf
inf
sup
[ (--1++1)
Pe R _1] ti 2amaxx (1.00) 02.0) WcC
2
2 + Pi
P2 [ (m(-))) - 0 - [n]
+
2
(C = [max [T,, -T) Amin, min(TI, -72) Amin c C since Amin A(x))
2 P P1 + P2 4 P P1 P2 11 (-11)
inf
inf
Pe I n1mmax(72 (2.00
2
2
inf WeC
P- p1 P2
(T + p))
2 P p1
p2 $ T2 - (1)
2
-estndd (pi P2)
gestnd (ACt, 1 (h, 2))
(by Lemma 1)
Note that for n = 2, an additional constraint + simplified
fit.y T2 = 1 is imposed and the expression can be
Grornd (h, inf Cgaarna (hu,) x) HEC
1 P1 + P2 [T(T) - - + 1+p1 - P2 p'(((-T) - ((r
2 *inf 720 ua[ T-mmm..-AAmi
sup
-(rr))-(------ (((--))]
2
2
= - (p1 - -p2)
= Jestadd (A (Aerar (ACto.,,o(h,1)) 2))
(by Lemma 1)
36

---

Since Tratnd is convex, by Jensen's inequality, we obtain for any hypothesis h E H and any distribu- tion.
gestad (Re. (h) Rio (JT) 1 (H()
Frstndd
[ GLACTO ar (h,)))))
E
Jostnd
$ E AC ( (h)
X
= Restaa (h) R Reean (IC) Mg (Ht).
Let 2. For any e [0, 1]. we consider the distribution that concentrates on singleton (œ) and satisfies p(z, 1) 1+t
2 p(z, 2) مst For any 0, by the definition of infimum, we can take J
2
such that (xx, 2) T. 2 and satisfies
1+t [ - 2(T m)1} grestad (t) + - [T.))) ( + [)] +
1 -
sup
Amin. Amin]
2
Then,
R (h)
- Ri (30) Mec. (3() = Réo- (h) - Ex ( (H1
Cia (h, x) C%a (H)
=t
and
gestad (t) s Ryeatnd (h) R Rioana (H() M (H)
= Ryentnd (h) Ex [x xH)
Cronua x) Epeaiaal (H, x)
1 [d(TT) -
1+1 [ - D(Te m)]}
- (
sup pe(te-Amine Am Aminn
< &rsstnd (t) +e.
By letting e - 0, we conclude the proof. The proof for n > directly extends from the case when = 2. Indeed, for any / E [0, 1]. we consider the distribution that concentrates
singleton {x) 1+! p(x, 2) = I-! p(z, y) 0,3 S S n. For any 0, by the defimition of infimum, we can take / E HC such that h(z, 1) = TI.c. h(z, 2) T2.., h(x,3) = 0, 3 s S n and satisfies T1,c + T2, and
and satisfies p(x,1)
2
2 P-
2 P
(--TL,)) (- w)]
inf Pe - 1 aec
sup
(-T2)) (- m)]
2
2
sup
1 - t
4)] [ (-T2,e) (- +1)
1+t
(0((1,,)) 1 m)]
WeC
2
<Festnd
(f) +e.
Then,
Re (h) - (II) + Me (I() =
and
gestud (1) s 2 R (h) Rr Reea (H) M goand (H) grstud (1) +
By letting e c 0, we conclude the proof.
F22
Constrained exponential loss
Theorem 13 (K-consistency bounds for constrained exponential loss). Let (tt) et For any e H. and any distribution,
Rea (h) Ri (3C) Men. (3C) vr (R (h) Ri (II) + M (3()
1-
21 20mmn
where (1))
1 Amin c Ammis)) 2-e Amiia
otherwise.
2
37

---

Proof. For n 2, plugging in ((t) e in Theorem 12, gives
Jestud
1-11e= -
1 - -
inf 220
sup
u 7 Minu
2
By differentiating with respect to r, we can see that the infimum is achieved when T = modulo some elementary analysis. Thus, Jestan can be reformulated as
yestud
sup nel (- Amin Amiu)
2 1
[1-c")
1 1+1
- [1-c"1] e01}
2
sup
g()).
/el ue(-AAin::Amt))
where g(x) -
1 Since g is continuous, it attains its supremum over a compact set. Note that g is concave and differentiable. In view of that, the maximum over the open set (-o0, can be obtained by setting its gradient to zero. Differentiate s(4) to optimize, we obtain
1-6
(1n') 00 P
log 1+t
Moreover, by the concavity, g(p) non-increasing when μ p². Since μ s 0 and Amin have
J= 5 Amin
In view of the constraint, if μ² -Amin the maximum is achieved by μ p², Otherwise, if u² < Amiin since (()) is non-increasing when j 2 p², the maximum achieved by μ -Amin- 2Amin-1 the maximum can be expressed as Since n² -Amin is equivalent to t A
g(m) (9(()) (g(-Amin)
ts 2 e otherwise
pe| uel-Amin A Computing the value of at these points yields:
g(1²)
1 1-t
1+t
g( ((-Amin)
Amin
Amio
2
Then, if 20min 1
we obtain
J Jostad
= =1 -1 1-V1--2
Otherwise, we obtain
psttdd
1-6
2 c Amin
1+1
C -Amin
2
1 (e -e Amin
2 e.Ain Amin
For n. > 2, plugging @(t) = = Theorem 12, gives
restud (t)
J
2 P inf sup Pel 1| riamax 02 ycC
inf
- 2- P+ 1
2
where C = [max (71, - T2] - Amin, min(11,nim)) -T2) 7 + Amin]. By differentiating with respect to 72 and P. that the infimum achieved when T2 analysis. Thus, oottnd
and P modulo some elementary
can be reformulated
cstnd
1
1 [1 en1
suup C
"1
1 sup g(u). DcC
38

---

where C' = [[-Amin- Amia] and (( - e- "- 1+1 el, Since is continuous, it attains its supremum over compact set. Note that g is concave and differentiable. In view of that, the maximum over the open set (-o0, +00 can be obtained by setting its gradient to zero. Differentiate g(1) to optimize, we obtain
1-t
g(n) =0 p==
log 1+t
Moreover, by the concavity, g(p) non-in inninccressing when μ 2 μ². Since μ s 0 and Amin 2 0, we have
s Amin
In view of the constraint, if μz¹ 2 -Amin the maximum achieved by μ = μ²" Otherwise, μ² -Amin since g(p) is non-increasing when p 2 f the maximum is achieved by μ - Amin- 22Amin the maximum can be expressed as Since μ² -Amin is equivalent to ezAmin+1
H()) = (9(1")
max
e min++ otherwise
Aem-AAmin Aminn
(9(-Amin)
Computing the value of these points yields:
(("') =-v1-= -
1-t
Amin 1+t
(1-Amiu) 2
Amin
20min 2m
Then, if
we obtain
estad
11-
Otherwise, obtain
5 csttd
1-6 Awin 1+1
2 e Amin
1 (cAmia -e Aminn)
Amiu e Amin
Since Testad
convex, by Theorem 12, for any h Fi and any distribution,
Re
Rig- (I)) (h)-
Me (I) vr ' (Roestna (h) 3 Reannnd
([) + M
(F()
where
1 1-v1-1
2 mmmnn1
(t)
Amin Ammnn
2-aAmin Amtn
otherwise.
2
39


Reviews:
[{"review_id": "1mNRo7ViW1", "reviewer": "Reviewer_3BV1", "summary": "The authors present some extension study on the H-consistency bounds for various loss functions. They also introduce an error transformation function that the authors claim could be a general tool in deriving H-consistency bound.", "questions": "1. I understand the importance of introducing a more general mathematical tool in deriving H-consistence bound for a wide range of function (but I did not check the correctness of this part). I don't know what's the value of a tigher H-consistent bound. This bound does not seem really useful (or maybe I am wrong) in pratise to guide people's design decision. Whereas Awasthi et al introduced the H-consistent bound.\n\n2. Essentailly following 1 above, while we pushed the theoretical guranttee forward a little bit, application wise, what are the add-on values that this paper brings compared to the related work?", "limitations": "A bit hard for general audience to understand.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors seem very well aware of the related work and have solid comparison with them.", "weaknesses": "Maybe the authors can simplify the notation and presentation so as the paper can be consumed by more general audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your useful comments. We have carefully addressed all the questions raised. Please find our responses below.\n\n**Weaknesses:**\n**Maybe the authors can simplify the notation and presentation so as the paper can be consumed by more general audience.**\n\n**Limitations:**\n**A bit hard for general audience to understand.**\n\n**Response:** We will definitely follow your suggestions and will seek to simplify and improve the notation and presentation for readers. The extra page in the final version will also allow us to expand the discussion in the main body.\n\n**Questions:**\n\n**1. I understand the importance of introducing a more general mathematical tool in deriving H-consistence bound for a wide range of functions (but I did not check the correctness of this part). I don't know what's the value of a tighter H-consistent bound. This bound does not seem really useful (or maybe I am wrong) in practice to guide people's design decisions. Whereas Awasthi et al introduced the H-consistent bound.**\n\n**Response:** Indeed, one of our principal contributions lies in a more general and convenient mathematical tool for proving $H$-consistency bounds. However, the derivation of tighter $H$-consistent bounds is equally significant.\n\nAs mentioned by Awasthi et al, given a hypothesis set $H$, $H$-consistency bounds can be used to compare different surrogate loss functions and select the most favorable one, which depends on 1) The functional form of the $H$-consistency bound; 2) The smoothness of the loss and, more generally, its optimization properties; 3) Approximation properties of the surrogate loss function: for instance, given a choice of $H$, the minimizability gap for a surrogate loss may be more or less favorable; 4) The dependency of the multiplicative constant on the number of classes. Consequently, a tighter $H$-consistency bound provides a more accurate comparison, as a loose bound might not adequately capture the full advantage of using one surrogate loss. In contrast, Bayes-consistency does not take into account the hypothesis set and is an asymptotic property, thereby failing to guide the comparison of different surrogate losses.\n\nAnother application of our $H$-consistency bounds involves deriving generalization bounds for surrogate loss minimizers, expressed in terms of the same quantities previously discussed. Therefore, when dealing with finite samples, a tighter $H$-consistency bound could also result in a corresponding tighter generalization bound.\n\nWe will further elaborate on these aspects in the relevant section of our paper, underscoring the importance and the value of tighter $H$-consistency bounds.\n\n**2. Essentially following 1 above, while we pushed the theoretical guarantee forward a little bit, application wise, what are the add-on values that this paper brings compared to the related work?**\n\n**Response:** As already mentioned, our significant contributions include a more general and convenient mathematical tool for proving $H$-consistency bounds, along with tighter bounds that enable a better comparison of surrogate loss functions. These improved bounds also lead to tighter finite sample generalization bounds compared to previous work. Moreover, our novel results extend beyond previous completeness assumptions, offering guarantees applicable to bounded hypothesis sets commonly used with regularization. This enhancement provides meaningful learning guarantees. Further details will be expanded in the final version.\n"}, {"review_id": "Dygsry8Re2", "reviewer": "Reviewer_VFQY", "summary": "This paper presents an extension of previous works on $\\mathcal{H}$-consistency bounds for multi-classification using a novel method. The strength of the paper lies in proposing a new method and tool that guarantees tight $\\mathcal{H}$-consistency bounds for multi-classification. ", "questions": "Please refer to the weaknesses section for the identified limitations.\n", "limitations": "Please refer to the weaknesses section for the identified questions.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The paper proposes a general characterisation $\\mathcal{H}$-consistency bounds for multi-classification via new tools.", "weaknesses": "One weakness of the paper is the lack of clarity in the discussion of tightness guarantees. While the statement in lines 191-192 suggests the existence of a distribution $\\mathcal{D}$ and a hypothesis for which the upper bound in Theorem 2 is tight, it is not explicitly clarified if this bound holds tight for all data distributions. Therefore, it is recommended to provide further clarification regarding the tightness statement.\n\nTo enhance the comprehension of the paper, it would be beneficial to include an experimental design demonstrating the tightness of the proposed bounds in comparison to previous results.\n\nThe authors mention the application of a tool to derive new results, but it would be helpful to explicitly mention and explain the techniques employed in the main body of the paper. Currently, it is unclear what these tools entail.\n\nIn the proof of Theorem 3, it is advised to provide additional elaboration on the equalities following line 587. It should be noted that in the second equality, the infimum with respect to $\\tau$ is taken over all terms.\n\nIn line 318-319, the authors mentioned \"Next, we illustrate the application of our theory through an example of constrained exponential losses,\". However, the paper is finished.\n\nThe proof of Theorems 2 and 5 for the tightness is limited to n=2. For n>2, there is no discussion. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your useful comments. We have carefully addressed all the questions raised. Please find our responses below.\n\n**1. One weakness of the paper is the lack of clarity in the discussion of tightness guarantees. While the statement in lines 191-192 suggests the existence of a distribution $\\mathcal{D}$ and a hypothesis for which the upper bound in Theorem 2 is tight, it is not explicitly clarified if this bound holds tight for all data distributions. Therefore, it is recommended to provide further clarification regarding the tightness statement.**\n\n**Response:** We will further clarify that in the final version. In short, our $H$-consistency bounds are distribution-independent and we do not claim tightness across all distributions. Our analysis can be extended, however, to derive finer distribution-dependent bounds under assumptions such as Massart’s noise condition, as in (Awasthi et al., 2022).\n\n**2. To enhance the comprehension of the paper, it would be beneficial to include an experimental design demonstrating the tightness of the proposed bounds in comparison to previous results.**\n\n**Response:** This is certainly a natural suggestion. We will seek to add such experiments in the final version to empirically illustrate the tightness of our proposed bounds.\n\n**3. The authors mention the application of a tool to derive new results, but it would be helpful to explicitly mention and explain the techniques employed in the main body of the paper. Currently, it is unclear what these tools entail.**\n\n**Response:** We will further clarify that in the final version. Our error transformation function serves as a very general tool for deriving $H$-consistency bounds with tightness guarantees. These functions are defined within each class of loss functions including comp-sum losses and constrained losses, and their formulation depends on the structure of the individual loss function class, the range of the hypothesis set and the number of classes. To derive explicit bounds, all that is needed is to calculate these error transformation functions. Under some broad assumptions on the auxiliary function within a loss function, these error transformation functions can be further distilled into more simplified forms, making them straightforward to compute.\n\n**4. In the proof of Theorem 3, it is advised to provide additional elaboration on the equalities following line 587. It should be noted that in the second equality, the infimum with respect to $\\tau$ is taken over all terms.**\n\n**Response:** Thank you for the suggestion. You are absolutely correct, the infimum with respect to $\\tau$ is taken over all terms in the second equality. We will definitely add more explanation and clarify the derivation further in the final version.\n\n**5. In line 318-319, the authors mentioned \"Next, we illustrate the application of our theory through an example of constrained exponential losses,\". However, the paper is finished.**\n\n**Response:** Sorry for the confusion. The example of constrained exponential losses is deferred to Appendix F.2 due to space limitations. We will further improve our presentation for readers and use the extra page in the final version to add more discussions in the main body.\n\n**6. The proof of Theorems 2 and 5 for the tightness is limited to n=2. For n>2, there is no discussion.**\n\n**Response:** Sorry for the confusion. The proof for n>2 closely follows and directly extends from the case when n= 2, by considering the distribution that concentrates on a singleton. This was inadvertently omitted, but we will definitely include a thorough discussion in the final version.\n"}, {"review_id": "URs8R32sAc", "reviewer": "Reviewer_C2H4", "summary": "H-consistency bounds for surrogate loss function plays an important part in learning theory.\nThis manuscript provides a comprehensive characterization and extension of H-consistency\nbounds for multi-class classification. The authors introduce a novel error transformation function\nthat enables the derivation of tighter bounds, even under weaker assumptions compared\nto existing related works. Technically, this research presents a systematic approach to H-consistency bounds. Moreover,\nit contributes to the refinement of results concerning the consistency of multi-class\nclassification on a theoretical level.", "questions": "• As stated in the manuscript, H-consistency is a generalization of Bayes consistency,\nand new techniques have been developed in the analysis of H-consistency. Is it possible\nto illustrate the advantages of H-consistency over Bayes consistency with more specific\nexamples?\n\n• The H-consistency analysis for not only the linear hypothesis class but also the neural\nnetwork class has been done in [2]. Can the results in the manuscript be extended to\nthe neural network class as well? As far as I understand, the analysis in the manuscript\nrelies heavily on the explicit form of the hypothesis, does it mean that it is difficult to\nextend these inequalities to the deep neural network class?\n\n• Between Line 256 and 257: Φ−1 → Ψ−1\n\n[2] P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for surrogate loss\nminimizers. ICML 2022.", "limitations": "I suggest the authors illustrating more specifically the advantages of H-consistency over Bayes\nconsistency.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors present a systematic technique for H-consistency analysis and apply it to\nvarious types of loss functions.\n\nThe authors compare the results in the manuscript with those in related works in detail\nand show a significant advance.", "weaknesses": "This manuscript includes a wealth of work but only limited technical innovations compared\nto [1].\n\n[1] P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H-consistency bounds.\nNeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We have carefully addressed all the questions raised. Please find our responses below.\n\n**Weaknesses:**\n**This manuscript includes a wealth of work but only limited technical innovations compared to [1].**\n\n**Response:** Our work introduces a key technical innovation: error transformation functions. These functions enable a more systematic and straightforward derivation of $H$-consistency bounds. The versatility of this novel tool offers significant advantages, including tighter bounds surpassing those in [1] for complete hypothesis sets and, importantly, tailored guarantees for bounded hypothesis sets, going beyond completeness assumptions.\n\nWe are confident that our innovative approach will pave the way for advances in multi-class classification consistency research and benefit the analysis of consistency in various other scenarios.\n\n**Questions:**\n\n**1. As stated in the manuscript, H-consistency is a generalization of Bayes consistency, and new techniques have been developed in the analysis of H-consistency. Is it possible to illustrate the advantages of H-consistency over Bayes consistency with more specific examples?**\n\n**Limitations:**\n**I suggest the authors illustrating more specifically the advantages of H-consistency over Bayes consistency.**\n\n**Response:** Certainly, in the final version, we will provide illustrative examples. A critical issue with Bayes consistency lies in its assumption of access to the entire family of measurable functions, which contrasts with the limited hypothesis set $H$ a learning algorithm can rely on. The concept of $H$-consistency (and $H$-consistency bound) specifically aims to capture the properties of the particular hypothesis set $H$ used.\n\nFor instance, Long and Servedio (2013) presented a compelling case where they demonstrated both theoretically and empirically that the expected error of an algorithm minimizing a Bayes-consistent loss remains bounded by a positive constant. In contrast, the expected error of an algorithm minimizing an inconsistent but realizable $H$-consistent loss approaches zero. This example highlights the significance of considering the characteristics of the chosen hypothesis set $H$ in practical learning scenarios.\n\n\n**2. The H-consistency analysis for not only the linear hypothesis class but also the neural network class has been done in [2]. Can the results in the manuscript be extended to the neural network class as well? As far as I understand, the analysis in the manuscript relies heavily on the explicit form of the hypothesis, does it mean that it is difficult to extend these inequalities to the deep neural network class?**\n\n**Response:** Good question! Our $H$-consistency bounds, as demonstrated in Theorem 2, Theorem 4, Theorem 5, Theorem 6, Theorem 9, Theorem 10, and Theorem 12, are not limited to specific hypothesis set forms. They are directly applicable to various types of hypothesis sets, including linear functions and complex neural networks. For instance, Corollary 8, derived from Theorem 6, provides $H$-consistency bounds for linear hypothesis sets by explicitly computing and incorporating the term $\\Lambda(x)$ into the general formulation of $\\Psi$.\n\nThe same derivation can be extended to neural networks studied in [2] and their multi-class generalization, where we calculate and substitute the corresponding $\\Lambda(x)$ value. As a result, we obtain novel and tight $H$-consistency bounds for bounded neural network hypothesis sets in multi-class classification, highlighting the remarkable versatility of our general tools. We will further elaborate on that and include specific results related to the hypothesis set of neural networks in the final version.\n\n**3. Between Line 256 and 257: $\\Phi^{-1} \\to \\Psi^{-1}$**\n\n**Response:** Thank you, we will correct the typo.\n"}, {"review_id": "qaWRo6Y8rt", "reviewer": "Reviewer_x2ot", "summary": "The authors propose a general characterization and extension of H-consistency bounds for multi-class classification. They introduce an error transformation function that serves as a general tool for deriving these guarantees with tightness guarantees. The paper demonstrates that calculating the error transformation function enables the derivation of H-consistency bounds for various loss functions and hypothesis sets.\n\nThe general tools and tight bounds presented in the paper offer several advantages. They improve existing bounds for complete hypothesis sets, encompass a wide range of previously studied and new loss functions, extend beyond the completeness assumption, provide guarantees for bounded hypothesis sets, and offer a stronger guarantee for logistic loss with linear hypothesis sets compared to previous work.\n\nOverall, this paper contributes to the understanding and derivation of H-consistency bounds, providing a more general framework and tools for analyzing surrogate loss functions in machine learning.", "questions": "Can the theory be extended to derive tight bounds for more complicated models such as simple neural networks?", "limitations": "No potential negative societal impact", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well presented. It introduced a new general tool for deriving these H-consistency bounds with tightness guarantees. The results are carefully articulated and compared with existing work. I did not have enough time to verify all the math details, but the results look solid. ", "weaknesses": "See next section", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. Below please find responses to specific questions.\n\n**Can the theory be extended to derive tight bounds for more complicated models such as simple neural networks?**\n\n**Response:** Good question! Our $H$-consistency bounds, as demonstrated in Theorem 2, Theorem 4, Theorem 5, Theorem 6, Theorem 9, Theorem 10, and Theorem 12, are not limited to specific hypothesis set forms. They are directly applicable to various types of hypothesis sets, including linear functions and complex neural networks. For instance, Corollary 8, derived from Theorem 6, provides $H$-consistency bounds for linear hypothesis sets by explicitly computing and incorporating the term $\\Lambda(x)$ into the general formulation of $\\Psi$.\n\nThe same derivation can be extended to neural networks studied in [Awasthi et al., 2022a] and their multi-class generalization, where we calculate and substitute the corresponding $\\Lambda(x)$ value. As a result, we obtain novel and tight $H$-consistency bounds for bounded neural network hypothesis sets in multi-class classification, highlighting the remarkable versatility of our general tools. We will further elaborate on that and include specific results related to the hypothesis set of neural networks in the final version."}, {"review_id": "vIE5Zhk01b", "reviewer": "Reviewer_PRWE", "summary": "Unlike previous work on H-consistency bounds for surrogate loss functions, this paper attempts to analyze them from a more unified perspective.\nFor this purpose, the paper proposed a new error transformation method to present new tight H-consistency bounds for comp-sum losses and constrained losses in multi-class classification. With this method, the authors derived the\nH-consistency bounds in a unified manner for various loss functions, and a new theoretical analysis have developed for non-complete hypothesis sets.", "questions": "- In line 59, the author explained that the bound in Awasthi 2022b may not be tight due to its ad-hoc analysis. I would like to know what it means by ad-hoc analysis and when it is not tight to clarify the limitation of existing work.\n\n- In Appendix C.1, I could not follow the equation between lines 574 and 575. Could you explain how the condition is derived from the second equality to the third equality, where $\\inf_{\\tau_1 \\leq \\max(\\dots...)}$ appeared. \n\n- I found it hard to understand what is the intuition behind J^{comp} for $n>2$ in Theorem 2 since the constraint is very complex. Is there any clear explanation for that?\n\n- In theorem 2 and 5, the statement says that there exists a distribution D and h such that the equality holds. Could you present an explicit example of that ?", "limitations": "The limitation and assumption of the analysis is presented in detail.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "# Writing and Organization\n- The paper is well organized such that it is easy to understand the contribution of this paper, especially the technical difference from existing work.\n-  The extensive comparison in Appendix A is very helpful in understanding the recent progress in this field, and I thought this Appendix A should be placed in the main paper if there would be any spaces.\n\n# Technical contribution\n- This paper presents a significant improvement over the existing H-consistency bounds by developing a unified and consistent approach based on error transformation, which seems novel.", "weaknesses": "- I think the argument of section 2 should be improved to understand more easily.\n 1. The notation introduced in Sec 2 is hard to understand at first read. It would be helpful to add the summary of notations in the Appendix so that readers can easily follow the importance of this setting\n 2. I think the current argument in paragraph 106 is hard to follow. I finally understood the paragraph after reading Appendix B.2. It might be better to introduce  $I_l(\\mathcal{H})$ in the main paper, which only appears in the Appendix, better to understand the difference between $M_l$ and $A_l$.\n 3.  I like the explanation in Appendix B.2 and B.3 more than the current main paper since the importance of each concept is discussed mathematically and clearly. \n\n- The statement, especially Theorem 2, is very general and hard to understand. I understand that this is unavoidable because the developed analysis is a kind of unified viewpoint, but it would be better to add a little more discussion of the statements, for example,  under Theorem 2.\n\nTypos\n- In line 107, H_all is used before its formal definition. Currently, it is defined in Line 114, so it should be corrected.\n- Some parentheses are missing in equations from lines 532 to 533 in the Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We have carefully addressed all the questions raised. Please find our responses below.\n\n**Weaknesses:**\n\n**1. I think the argument of section 2 should be improved to understand more easily.**\n\n**Response:** We thank the reviewer for their suggestions. We will certainly incorporate them and will further improve our notation and presentation. In particular, we will include a notation summary in the appendix and a comprehensive discussion of each concept in the main body, by leveraging the extra page available in the final version.\n\n**2. The statement, especially Theorem 2, is very general and hard to understand. I understand that this is unavoidable because the developed analysis is a kind of unified viewpoint, but it would be better to add a little more discussion of the statements, for example, under Theorem 2.**\n\n**Response:** Thank you for your suggestions. We will definitely provide a more comprehensive discussion of the general results, particularly focusing on Theorem 2, in the final version.\n\n**3. Typos.**\n\nResponse: Thank you, we will correct them.\n\n**Questions:**\n\n**1. In line 59, the author explained that the bound in Awasthi 2022b may not be tight due to its ad-hoc analysis. I would like to know what it means by ad-hoc analysis and when it is not tight to clarify the limitation of existing work.**\n\n**Response:** When referring to their ''ad-hoc analysis'', we mean that their method of upper-bounding the estimation error of the target loss by that of the surrogate loss heavily depends on the specific loss function and does not extend to a new loss function. Their upper bounds may not be tight, as the ad-hoc inequality used in their derivation could, in some instances, be further improved. For instance, their bounds for constrained exponential losses are found not to be tight. In contrast, we offer a general tool to derive $H$-consistency bounds in a more systematic manner. Moreover, by using the error transformation functions, we succeed in obtaining bounds that are tighter than those provided by Awasthi et al. [2022b].\nWe will further clarify this in the final version.\n\n**2. In Appendix C.1, I could not follow the equation between lines 574 and 575. Could you explain how the condition is derived from the second equality to the third equality, where $\\inf_{\\gamma_1\\leq \\max(\\ldots)}$ appeared.**\n\n**Response:** Sorry for the confusion. There is a typo; the third equality should actually be an inequality, derived by directly taking the infimum. We will correct that in the final version.\n\n**3. I found it hard to understand what is the intuition behind J^{comp} for $n>2$ in Theorem 2 since the constraint is very complex. Is there any clear explanation for that?**\n\n**Response:** We acknowledge the complexity of the formulation for $n>2$, which is a result of its general and unifying nature, encompassing various loss functions. The conditional probability vector and scoring functions take on more flexible forms when $n>2$, leading to intricate constraints. We will provide a thorough explanation and clarification in the final version to make it more understandable.\n\n**4. In theorem 2 and 5, the statement says that there exists a distribution D and h such that the equality holds. Could you present an explicit example of that?**\n\n**Response:** The example of a particular distribution $\\mathcal{D}$ and a hypothesis $h$ will be contingent on the specific loss function and hypothesis set. This is because the conditional probability vector of $\\mathcal{D}$ and the scoring functions of $h$ must closely achieve the infimum in the transformation. In general, they are challenging to fully characterize, and often only existence can be shown. Nevertheless, we will seek to include in the final version an explicit example in simple cases for illustration.\n"}, {"review_id": "HC8yMe4J2A", "reviewer": "Reviewer_AHgy", "summary": "This work proposes a general characterization and an extension of H-consistency bounds for multiclass classification. By introducing an error transformation function, the paper provides a general tool for deriving H-consistency bounds with tightness guarantees. The paper demonstrates that the proposed tools and bounds can recover or even improve results from various recent works.", "questions": "Could you provide further explanation on the connection between the results presented in this study and the theory of calibration functions as described by Steinwart in 2007?", "limitations": "I could not find the location where the authors explicitly described the limitations of the work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is good work in the field, original with innovative methodologies and new insights. The paper provides a general characterization and extension of H-consistency bounds for multiclass classification. Focusing on two widely studied types of loss functions in the literature, comp-sum losses and constrained losses, a new tool is introduced to derive H-consistency bounds with tightness guarantees. Before this work, deriving such bounds often required proofs for each instance. The tool proposed in this work, based on error transformations (Theorem 2, 3, 5, 10, 11, 12), is general and can be applied to derive H-consistency bounds (Theorem 4, 6, 9, Corollary 7, 8) for various loss functions and hypothesis sets. The paper demonstrates that the proposed tools and bounds can recover or even improve results from various recent works (Line 201-206, 246-248, 253-255, 261-272, 301-306, 318-322).\n\nThe quality of research is good, with meticulous comparisons with several recent works and detailed analysis leading to convincing conclusions. Well-organized and well-written, the paper adeptly communicates complex concepts in a relatively understandable way. The work is significant, with findings that resonate beyond the specific area of study and are likely to stimulate further research in the field of H-consistency bounds for multiclass classification.\n\nOverall, this paper is a nice addition to the literature.", "weaknesses": "As far as I am concerned, I do not see any significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. Below please find responses to specific questions.\n\n**Could you provide further explanation on the connection between the results presented in this study and the theory of calibration functions as described by Steinwart in 2007?**\n\n**Response:** The calibration function is a general tool tailored to the family of all measurable functions, and is designed to provide excess error bounds between a surrogate loss and the target loss. The calibration function does not take into account the specific hypothesis set. On the other hand, our error transformation function is a general tool designed to provide $H$-consistency bounds between a surrogate loss and the target loss. These functions are tailored to the hypothesis set $H$ adopted. In the special case where $H$ is the family of all measurable functions, the error transformation function coincides with the calibration function, and the derived $H$-consistency bound coincides with an excess error bound. We will further clarify and detail these explanations in the final version.\n\n**Limitations:**\n**I could not find the location where the authors explicitly described the limitations of the work.**\n\n**Response:** Thank you for pointing it out. We will add an explicit discussion in the final version.\n\n\n\n"}]

Author rebuttal:

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a consensus that the paper contributes sound and interesting contributions. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers. Congratulations!
Decision: Accept (poster)