A Universal Growth Rate for Learning with Smooth Surrogate Losses
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2024 poster (2024)
Keywords: surrogate loss functions
Bayes-consistency
H-consistency bounds
excess error bounds
estimation error bounds
generalization bounds
learning theory
Primary area: learning_theory

Abstract: This paper presents a comprehensive analysis of the growth rate of $H$-consistency bounds (and excess error bounds) for various surrogate losses used in classification. We prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification, providing both upper and lower bounds under mild assumptions. This result also translates to excess error bounds. Our lower bound requires weaker conditions than those in previous work for excess error bounds, and our upper bound is entirely novel. Moreover, we extend this analysis to multi-class classification with a series of novel results, demonstrating a universal square-root growth rate for smooth *comp-sum* and *constrained losses*, covering common choices for training neural networks in multi-class classification. Given this universal rate, we turn to the question of choosing among different surrogate losses. We first examine how $H$-consistency bounds vary across surrogates based on the number of classes. Next, ignoring constants and focusing on behavior near zero, we identify *minimizability gaps* as the key differentiating factor in these bounds. Thus, we thoroughly analyze these gaps, to guide surrogate loss selection, covering: comparisons across different comp-sum losses, conditions where gaps become zero, and general conditions leading to small gaps.  Additionally, we demonstrate the key role of minimizability gaps in comparing excess error bounds and $H$-consistency bounds.

A Universal Growth Rate for Learning with Smooth Surrogate Losses
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims.o .ny..n.ee.. 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
This paper presents comprehensive analysis of the growth rate of H-coosistenccy bounds (and excess error bounds) for various surrogate losses used in classification. We prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification, providing both upper and lower bounds under mild assumptions. This result also translates to excess error bounds. Our lower bound requires weaker conditions than those in previous work for excess eттоr bounds, and our upper bound is entirely novel. Moreover, we extend this analysis to multi-class classification with series of novel results, demonstrating universal square-root growth rate for smooth comp-sum and constrained losses, covering common choices for training neural networks in multi-class classification. Given this universal rate, we turn to the question of choosing among different surrogate losses. We first examine how H-consistency bounds vary across surrogates based on the number of classes. Next, ignoring constants and focusing behavior near zero, we identify minimizability gaps as the key differentiating factor these bounds. Thus, thoroughly analyze these gaps, to guide surrogate loss selection, covering: comparisons across different comp-sum losses, conditions where gaps become zero, and general conditions leading to small gaps. Additionally, we demonstrate the key role minimizability gaps in comparing excess error bounds and H-consistency bounds.
Introduction
Learning algorithms frequently optimize surrogate loss functions like the logistic loss, in lieu of the task's true objective, commonly the zero-one loss. This is necessary when the original loss function is computationally intractable optimize lacks essential mathematical properties such as differentiabilityy But, what guarantees can we rely on when minimizing a surrogate loss? This is a fundamental question with significant implications for learning.
The related property of Bayes-consistency surrogate losses has been extensively studied in the context of binary classification. Zhang [2004a], Bartlett al. [2006] and Steinwart [2007] established Bayss-consistency for various convex loss functions, including margin-bart based surrogates. They also introduced excess error bounds (or surrogate regret bounds) for margin- based surrogates. Reid and Williamson [2009] extended these results to proper losses in binary classification.
The Bayes-consistency of several surrogate loss function families in the context of multi-class classification has also been studied by Zhang [2004b] and Tewari and Bartlett [2007]. Zhang [2004b] established series of results for various multi-class classification formulations, including negative results for multi-class hinge loss functions [Crammer and Singer, 2001], as well as positive results for the sum exponential loss [Weston and Watkins, 1999, Awasthi et al., 2022a], the (multinomial) logistic loss [Verhulst, 1838, 1845, Berkson, 1944, 1951], and the constrained losses [Lee et al., 2004].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Later. Tewari and Bartlett [2007] adopted different geometric method to analyze suyes-consistence yielding similar results for these loss function families. Steinwart [2007] developed general tools to characterize Bayes consistency for both binary and multi-class classification. Additionally, excess error bounds have been derived by Pires et al. [2013] for family of constrained losses and by Duchi et al. [2018 8) for loss functions related to generalized entropies.
For surrogate loss E, an excess error bound holds for any predictor and has the form (h) e% s ( - - where (4) and (h) represent the expected losses of h for the zero-one loss and surrogate loss respectively, &/o-, and E the Bayes errors for the zero-one and surrogate loss respectively, and V/ a non-decreasing function. The growth rale of excess error bounds, that is the behavior of function Yi' near zero, has gained attention in recent research [Mahdavi et al., 2014, Zhang et al., 2021, Frongillo and Waggoner, 2021, Bao, 2023]. Mahdavi et al. [2014] examined the growth rate for smoothed hinge losses in binary classification, demonstrating that smoother losses result in worse growth rates. The optimal rate achieved with the standard hinge loss, which exhibits linear growth. Zhang et al. [2021] tied the growth rate of excess error bounds in binary classification to two properties of the surrogate loss function: consistency intensity and conductivity. These metries enable comparisons of growth rates across different surrogates. This prompts a natural question: can we establish rigorous lower and upper bounds for excess error growth rates under specifie regularity conditions?
Frongillo and Waggoner [2021] pioneered research on this question binary classification settings. They established critical square-root lower bound for excess error bounds when a surrogate loss is locally strongly convex and has a locally Lipschitz gradient. Additionally, they demonstrated a linear excess error bound for Bayes-consisterr
polyhedral loss functions (convex and piecewise-linean [Finocchiaro et al., 2019] (see also [Lapin et al., 2016, Ranaswamy et al., 2018, Yu and Blaschko, 2018, Yang and Koyejo, 2020J). More recently, Bao [2023] complemented these results by showing that proper losses associated with Shannon entropy, exponential entropy, spherical entropy, squared a-norm entropies and ex ce-polynomial entropies, with 1, also exhibit square-root lower bound for excess error bounds relative to the f ddditannce.
However, while Bayes-consisteney and excess error bounds are valuable, they are not sufficiently informative, as they are established for the family of all measurable functions and disregard the crucial role played by restricted hypothesis sets in learning. As pointed out by Long and Servedio [2013], in some cases, minimizing Bayes-consistent losses can result in constant expected error, while minimizing inconsistent losses can yield an expected loss approaching zero. To address this limitation, the authors introduced the concept of realizable K-consistency, further explored by Kuznetsov et al. [2014] and Zhang and Agarwal [2020]. Nonetheless, these guarantees are only asymptotic and rely on a strong realizability assumption that typically does not hold in practice.
Recent research by Awasthi, Mao, Mohri, and Zhong [2022b,a] and Mao, Mohri, and Zhong (2023f,c,e.b) has instead introduced and analyzed K-consistency bounds. These bounds are more informative than Bayes-consistency since they are hypothesis set-specific and non- aon-tsyyptoiic.. Their work covers broad families of surrogate losses in binary classication, multi-class classification, struc- tured prediction, and abstention [Mao, Mohri, Mohri, and Zhong, 2023a]. Crucially, they provide upper bounds on the estimation error of the target loss, for example, the zero-one loss classification, that hold for any predictor h within hypothesis set H. These bounds relate this estimation error to the surrogate loss estimation eтror.
Their general form is: (h) - -E,, Meg (H) S ((E,(h)- - (H)) + Mc(H)), where (3() and E7 (HC) represent the best-in-class expected losses for the zero-one and surrogate loss respectively. r is a non-negative concave function and Mr, (H) and Mc(H) are minimizubility gaps. The exact definition of these gaps will be detailed later. For now, let us mention that they are non-negative quantities, upper- bounded by the approximation error of their respective loss functions. K-consistency bounds subsume excess error bounds as a special case when the hypothesis set is expanded to include all measurable functions, in which case the minimizability gaps vanish. More generally, an H-coonsisenccy bound with a I function implies E (h) { Mc., (H)) (h) E (3()) + I(M, since a concave function I' with I(0) 2 0 sub-additive over P,, Thus, when the surrogate estimation loss Ex(h) - EHH is minimized to the zero-one estimation error E (h) Ex (H) bounded by T(e) + T(M, (11))~MoM) M (H). Can we characterize the growth rate of HH-consistency bounds, that is how quickly the functions I' increase near zero?

---

Our results. This paper presents comprehensive analysis of the growth rate of H-consiiteney bounds for all margin-based surrogate losses in binary classification, as well as for comp-sum losses and constrained losses in multi-class classification. We establish square-root growth rate near zero for margin-bane biiii- surrogate losses & defined by x, ((-yh(x)), assuming only that + is convex and twice continuously differentiable with both upper and lower bounds (Theorem 4.2). These results directly apply to excess error bounds as well. Importantly, our lower bound requires weaker conditions than [Frongillo and Waggoner, 2021, Theorem 4], and our upper bound is entirely novel. This work demonstrates that the H-consistency bound growth rate for these loss functions is precisely square-root, refining the "at least square-root" finding of these authors (for excess error bounds). It is known that polyhedral losses admit linear grow rate [Frongillo and Waggoner, 2021]. Thus. striking dichotomy emerges that reflects previous observations by these authors: H--consistency bounds for polyhedral losses exhibit a linear growth rate in binary classification, while they follow a square-root rate for smooth loss functions.
>0 and &" (0) >0 (Section 4). This includes
Moreover, we significantly extend our findings to key multi-class surrogate loss families, including comp-sum losses [Mao et al., 2023f] (e.g.. logistic loss or cross-entropy with softmax [Berkson, 1944], sum-losses [Weston and Watkins, 1999], generalized cross entropy loss [Zhang and Sabuncu, 2018)), and constrained losses [Lee et al., 2004, Awasthi et al., 2022a] (Section 5). In Section 5.1, we prove that the growth rate of HC-consistency bounds for comp-sum losses is exactly square-root. This applies when the auxiliary function & they are based upon is convex and twice continuously differentiable with &' P'(u)== <0 and ("(u)>0 >0 for all u in (0, }. These conditions hold for all common loss functions used in practice. Further, in Section 5.2, we demonstrate that the square-rode growth rate also extends to H-consistency bounds for constrained losses. This requires the auxiliary function & to be convex and twice continuously differentiable with Φ'(u) > 0 and 4" (u) 0 for any 0, alongside an additional technical condition. These are satisfied by all constrained losses typically encountered in practice.
These results reveal a universal square-root growth rate for smooth surrogate losses, the predominant choice in neural network training (over polyhedral losses) for both binary and multi-class classification in applications. Given this universal growth rate, how do we choose between different surrogate losses? Section 6 addresses this question in detail. To start, we examine how JC-consistnncy bounds vary across surrogates based on the number of classes. Then, focusing on behavior near zero (ignoring constants), isolate minimizability gaps as the key differentiating factor in these bounds. These gaps depend solely on the chosen surrogate loss and hypothesis set. We provide a detailed analysis of minimizability gaps, covering: comparisons across different comp-sum losses, conditions where gaps become zero, and general conditions leading to small gaps. These findings help guide surrogate loss selection. Additionally, we demonstrate the key role of minimizability gaps in comparing excess error bounds and H-consistency bounds (Appendix F). Importantly, combining K-consistency bounds with surrogate loss Rademacher complexity bounds allows us derive zero-one loss (estimation) learning bounds for surrogate loss minimizers (Appendix O).
For more comprehensive discussion of related work, please refer to Appendix A. We start with the introduction of necessary concepts and definitions.
Preliminaries
Notation and definitions. We denote the input space by X and the label space by y, a finite set of cardinality n with elements ..)....n.. D denotes a distribution over x y.
We write Hau to denote the family of all real-valued measurable functions defined over X x y and denote by H subset, H s Hall The label assigned by h E H an input x E X is denoted by h(z) and defined by h(x)= = argmaxyey 1(x, y), with an arbitrary but fixed deterministic strategy used for breaking the ties. For simplicity, we fix that strategy be the one selecting the label with the highest index under the natural ordering of labels.
We will consider general loss functions &H x X x y + R.. For many loss functions used in practice, the loss value at (x,y), , E(h, xr, y). only depends on the value h takes at x and not on its values on other points. That is, there exists measurable function R x y + R, such that ((h, Jr, y) = ((h(z).y). where h(x) [h(x,, 1).....,dd .,.,,, ni]] is the score vector of the predictor h. We will then say that is a pointwise loss function. We denote by Ee(h) the generalization error expected loss of a hypothesis h e H and by EY (3C) the best-in in class error: (h)
3

---

B(ax)) [((,, xt), (3)) = -inf (h). (HCa)) is also known as the Bayes ervor. We write ply v) = D(Y = y = 2) to denote the conditional probability of Y = given X and for the conditional probability vector for any x E X. We denote by xx) x) the conditional error of h H at point I E X and by (3C, the best-in-class conditional ennor: (e(h, = E,[[eh,,
p(x) (((]
x] yeu pvy 1:) E(h, x, 9). ej x) inf Cr 4)) and use the shorthand A AC,,oc (h, Cx 3)) - C. a)) for the calibration gap or conditional regret for f. The generalization error of h can be written as (h) Ex[er (e[ee(h, .) For convenience, we also define, for any vector p= (Pi..... Pn) E A", where A is the probability simplex of E. Ce x, p) Eyey Py ((h, x, y), Ci (z, = infnemt Ce I,, and (h, = Ce(h, x, p) (2.p) Thus, we have ( I, p()) = (e,,,c(h,z)
We will smudy the properties of surrogate loss function E for target loss function &g. In multi-class classification, &g is typically the zero-one multi-class classification loss function fo-1 defined by fo-1(h, z. y) = In(=)ay. Some surrogate loss functions L include the max losses [Crammer and Singer, 2001], comp-sum losses [Mao et al., 2023f] and constrained losses [Lee et al., 2004].
Binary classification. The definitions just presented were given for the general multi-class classifica- tion setting. In the special case of binary classification (two classes), the standard formulation and definitions slightly different. For convenience, the label space is typically defined as y = {-1,+1] Instead of two scoring functions, one for each label, a single real-valued function is used whose sign determines the predicted class. Thus, here, a hypothesis set H is a family of measurable real-valued functions defined over X and Han is the family of all such functions. E is pointwise if there exists a measurable function &. x y + R. such that E(,, = {(h(z).)) The tar- get loss function typically the binary loss fo-1, defined by fo-1 xr, y) = siig(((())) where sign(h(=)) Ix(=)>0 Ix(x)<)- Some widely used surrogate losses E for la-1 are margin-based losses, which are defined by (h, (--yh(x)), for some non-decreasing convex function Φ: RR. - R.. Instead of two conditional probabilities, one for each label, a single conditional probabil- ity corresponding to the positive class +1 is used. That is, let ()x)) D(Y +1 | X x:) denote the conditional probability of Y +1 given X = x. The conditional error can then be expressed as:
ch) E[ x, v) x] ()=))((h, +1) (1 (x)))(((,, -1).
"'
For convenience, we also define, for any e [0. 1]. (h = pl +1) + (1 (),h)) x, -1), Ci,xe (x. infnere Ce(h, x. and (h, C, inffner Ce p)). Thus, have A,,,,ch,, (x))) Aee, (..
To simplify matters, we will use the same notation for binary and multi-class classification, such as y for the label space or H for hypothesis set. We rely on the reader to adapt to the appropriate definitions based on the context.
Estimation, approximation, and excess errors. For hypothesis h. the difference E (Hal)) known as the excess error. It can be decomposed into the sum of two terms, the estimation error, (Ex(h) - (3)) and the approximation error Ax()) = (E; (H)) - 87 (Hau)):
(h) - E (HG.)) = (
(1)
A fundamental result for pointwise loss function E is that the Bayes error and the approximation error admit the following simpler expressions. We give a concise proof this lemma in Appendix B, where we establish the measurability of the function Lemma 2.1. Let f be a pointwise loss function. Then, the Bayes error and the approximation error can be expressed as follows: ETHan) E., x)] and Ae())) E (J() - Er, [e] HH
C₁ (Hal.
For restricted hypothesis sets (H * Han)), the infimum's 's super-additivity implies that E (H) 2 E. ( (K,=)), This inequality is generally strict, and the difference, (H)) E.g [et (H, x)), plays a crucial role in our analysis.
3 H-consistency bounds
A widely used notion of consistency is that of Bayes-consistency given below [Steinwart, 2007].
Definition 3.1 (Bayes-consistency)) A loss function & is Bayes--onsistent with respect to loss func- tion f,, if for any distribution D and any sequence (hn JeN c Hall lim Ee, (hn,) 1 (Han) = 0
implies lim Elg (hn) Ei, (Han) 0.

---

Thus, when this property holds, asymptotically, a nearly optimal minimizer of E over the family of all measurable functions is also a nearly optimal optimizer of Z2. But, cones-con does not supply any information about a hypothesis set H not containing the full family Han, that is typical hypothesis set used for learning. Furthermore, it only an asymptotic property and provides no convergence guarantee. In particular, it does not give any guarantee for approximate minimizers. Instead, we will consider upper bounds on the target estimation error expressed in terms of the surrogate estimation error, H--consistnncy bounds [Awasthi et al., 2022b,a, Mao et al., 2023f], which account for the hypothesis set H adopted.
Definition 3.2 (H--conistencyy bounds). Given a hypothesis set H. an K-consistency bound relating the loss function & to the loss function Eg for hypothesis set H is an inequality of the form
Ah E H. (b) - Eig (J( + Me, (36) s T(E,, (h) E,, (30 + Me, (H)),
that holds for any distribution D, where T:R. - RR, is a non-decreasing concave function with r [Awasthi et al., 2022b,a]. Here, Me, (H) and (H,,() are minimizability gaps for the respective loss functions. The minimizability gap for a hypothesis set H and loss function E is denoted by (H) and defined as: Mc (3t) - [ (3,, z)). It quantifies the discrepancy between the best possible expected loss within a hypothesis class and the expected infimum of pointwise expected losses. This gap is always non-negative: Mc({() inf E, (h, E., [infreer Cx xH),))] O. by the infimum's 's super-additivity, and is bounded above by the approximation error (x( inf [E,[[e(h,, h, x=] Ex [en e₁ ). We further study the key role of minimizability gaps in I connsissyyy bounds and their properties in Section and Appendix D. As shown in Appendix C, under general assumptions, minimizability gaps are essential quantities required in any bound that relates the estimation errors of two loss functions with an arbitrary hypothesis set H.
Thus, an H-coosissencyy bound provides the guarantee that when the surrogate estimation loss (h) - E7 (H) is minimized to c, the following upper bound holds for the zero-one estimation error: Eg - E; (30) < I(c+ (39) - -M,,, r(e) + ((M((3)))) - MM,,
where the second inequality follows from the sub-additivity of a concave function I over R., We will demonstrate that, for smooth surrogate losses, I(c) scales as vc. Note, however, that, while I(e) tends to zero when + 0 for functions I' derived in H-consiitency bounds, the remaining terms in the bound are constant. This not surprising as, in general, minimizing the surrogate estimation error to zero cannol guarantee that the zero-one estimation error will also converge to zero. This is well-known, for example, in the case of linear models [Ben- -avid et al., 2012]. Instead, an J--consistency bound provides the tightest possible upper bound on the estimation error for the zero-one loss when the surrogate estimation error is minimized.
The upper bound simplifies to r(c) when the minimizability gaps are zero which occurs when either H Hall (the set of all measurable functions) or in realizable cases, which are particularly relevant to the practical use of complex neural networks in applications. In Appendix I, we examine more general cases of small minimizability gaps, taking into account the complexity of H and the distribution.
Our results cover in particular the special case of excess bounds (H Han). Let us emphasize that, for H. Hall K-consistency bounds offer tighter and more favorable guarantees the estimation error compared to those derived from excess bounds analysis alone (see Appendix F).
When f f0-1, the zero-one loss, say that T is the K-esttmaaiinn error transformation function of a surrogate loss E if the following holds:
vh E H. ((Eto-1(h) - -Ei
Mo. (30) s E)) M,(3(,,
and the bound is tight. That is, for any L E [0. 1], there exists a hypothesis h H. and a distribution such that E (h)- E (H)++M (H) = i and of T has been characterized for binary margin-based losses [Awasthi et al., 2022b], as well as comp- sum losses and constrained losses in multi-class classification [Mao et al., 2023b]. In the following sections, we will prove the property J(t) = (tt?) (under mild assumptions), demonstrating a square- root growth rate for H-consistency bounds. Appendix provides examples of HK-conisstnncy bounds for both binary and multi-class classification. Our analysis also suggests choosing appropriately H. and the function I' to ensure a small minimizability gap and to take into account the number of classes and other properties, as discussed in Section 6.
= =[().. An explicit form
5

---

4 Binary classification
We consider the broad family of margin-based loss functions defined for any h e H, and (x, v) e X y by 2(h, 1/) ((-yh(x)), where & is non-decreasing convex function upper-bounding the zero-one loss. Margin-based loss functions include most loss functions used in binary classification. As an example, $(u)= = log(1 (1 e*) for the logistic loss or B(u)= exp(u) for the exponential loss. We say that a hypothesis set H is complete, if for all æ X, we have {h(z): E J() R. As shown by Awasthi et al. [2022b], the transformation J has the following form for complete hypothesis sets:
J((): = inf [+(w) inf fe(u). M50
MER
Here, for any t E [0.1]. fo is defined by: Vu R. f((u) = 2 (()) + 1 ((u)). The following result is useful for proving the growth rate in binary classification.
Theorem 4.1. Let H be complete hypothesis set. Assume that & is convex and differentiable at zero and satisfies the inequality 4 (0) > O. Then, the transformation J can be expressed as follows:
E E [0, 1], I(t) 5+(0) - inf fe(u).
ueR
Proof. By the convexity of 4, for any LE [0, I] and u E IR_, we have
fi(u) 1-t (u)) + 1 1+ t ( 2 ((0) tu 2(0).
2
Thus, we can write I(t)= infaga fa(u)- inf weR fe(u) 2 (0) - inf ft(u)= = f+()) - inf fu)
where equality is achieved when u
Theorem 4.2 (Upper and lower bound for binary margin-based losses). Let H. be complete hypoth- esis set. Assume that & convex, twice continuously differentiable, and satisfies the inequalities 4'(0) > O and 4" (0) > 0. Then, the following property holds: J(t) = O(t); that is, there exist positive constants C 0, <> 0, and T such that Ct z I(t) ct for all TT.
Proof sketch First, we demonstrate that, by applying the implicit function theorem, inf fe(u) is attained uniquely by at and that of is continuously differentiable over [0, for some > 0. The minimizer of satisfies the following condition: fa() = 1/ &' (aī)) - 1-1 ('((a;) = O. Specifically, at t O, we have & (ajt) = & ( Then, by the convexity of & and monotonicity of the derivative s', we must have ag = 0 and since &' is non-decreasing and 4"(0) O, we have oj 0 for all t e (0,e), eJ. Furthermore, since af is a function of class C²,, we can differentiate this condition with da,
2
respect and take the limit 0, which gives the following equality: de (0) (5 > 0. Since
4'(0)
di (0) --"(0) > 0, we have a; =(t). By Theorem 4.1 and Taylor's 's theorem with an integral remainder, I can be expressed as follows: for any t [0, (()) fe(0) - inf fe(u) "=""" du. Since (0 > 0 and 4" is continuous, there is non-empty interval [-a, +a] over which Φ" is positive. Since aj there exists a sub-interval [0, c' S [O.c] over which a; S a. Since &" is continuous, it admits minimum and a maximum over any compact set and
lim of = dot
+'(0)
Jo (u) du du= fo u[ 1=(4(())
and a; is continuous,
define minwe[[o.o) &² Φ²(u) and C' max @b (u))). and C' are both positive since we have 4" (0) 0. Thus, for t in [0, the following inequality holds: c(a = So uC du 2 J(t)= = fo un + 1 * du (a:)²
foi ucdu= = c(
2 This implies that J(t) = (t2). The full proof is included in Appendix K.
Theorem 4.2 directly applies to excess error bounds as well, when H( = Haall Importantly, our lower bound requires weaker conditions than [Frongillo and Waggoner, 2021, Theorem 4], and our upper bound is entirely novel. This result demonstrates that the growth rate for these loss functions precisely square-root, refining the "at least square-root" finding of these authors. It known that polyhedral losses admit a linear grow rate [Frongillo and Waggoner, 2021]. Thus, striking dichotomy emerges: H--conistency bounds for polyhedral losses exhibit linear growth rate, while they follow square-root rate for smooth loss functions (see Appendix G for detailed comparison).

---

5 Multi-class classification
In this section, we will study two families of surrogate losses in multi-class classification: comp-sum losses and constrained losses, defined in Section 5.1 and Section 5.2 respectively. Comp-sum losses and constrained losses are general and cover all loss functions commonly used in practice, We will consider any hypothesis set H. that is symmetric and complete. We say that a hypothesis set symmetric when does not depend on a specific ordering
the classes, that is, when there exists family F of functions f mapping from I to R such that {[h(x, 1)................... h(x, n)]: he I(} (z). ( f......... E eJ), for any x X. We say that a hypothesis set H is complete the set of scores it generates spans R, that is, {h(2, y): h JC} = R. for any (z, 3) E X y.
5.1
Comp-sum losses
Here, we consider comp-sum losses [Mao, Mohri, and Zhong, 2023f], defined as
(
vh E H. (2r,)) Xx y, geomp (hmp(,, + Eveey ch(aww)
where R.R. + R, is a non -on-increasing function. For example, & can be chosen as the negative log function - loog(u u) for the comp-sum losses, which leads to the multinomial logistic loss. As shown by Mao, Mohri, and Zhong [2023b], for symmetric and complete hypothesis sets, the transformation T for the family of comp-sum losses can be characterized as follows.
Theorem 5.1 (Mao et al. [2023b. Theorem 3)). Let H be symmetric and complete hypothesis set. Assume that & is convex, differentiable at 1 and satisfies the inequality 2'(b) < Then, the transformation T can be expressed
1+ D( -u) 1-1 D(T+ + u)
I(t) = inf sup re re( juss
((T)
2
2
Next, we will show that as with the binary case, for the comp-sum losses, the properties T(t) = 12(2) and T(t) O(t²) hold. We first introduce generalization of the classical implicit function theorem where the function takes the value zero over a set of points parameterized by a compact set. We treat the special case of function F defined over R3 and denote by (t, a, r) e R3 its arguments. The theorem holds more generally for the arguments being in R x R2 I2 and with the condition on the partial derivative being non-zero replaced with a partial Jacobian being non-singular.
Theorem 5.2 (Implicit function theorem with compact set). Let FxRRRRR R be continuously differentiable function in a neighborhood of (0, 0, T), ). for any T in a non non-empty compact set C. with F(0, 0, 7) = O. Then, if 8F
Ba (0, 0, T) is non-zero for all in C, then, there exist neighborhood of and a unique function a defined over 0 C that is continuously differentiable and satisfies
A (L,T)
F(1,ū(1,7),7) =0.
Proof. By the implicit function theorem (see for example [Dontchev and Rockafellar, 2009I), for any T e C, there exists an open set U (-Ir, +l7) (T - 6,, 7 + e7), (L, > 0 and e, 0), and a unique function ā,; U, R that is in C and such that for all (I, e U, (1),), =
By the uniqueness of ā,, for any r' and (t1, Uy n U,,, we have a (11,7)= a, (t,, (f1,TT) TI). Thus, we can define a function à over Ul = Uree U, that is of class C²l and such that for any (t, U, F(t, (),
Now, Uree(T-G,T+C, is cover of the compact set via open sets. Thus, we can extract from a finite cover (T-G. for some finite cardinality set I. Define (-to. +to) Nrez (-t,,+tttt which is a non-empty open interval as an intersection of (embedded) open intervals containing zero. Then, is continously differentiable over (-lo,+ly e and for any (1,7) (-lo++lo) x C, we have F(I, ((),
Theorem 5.3 (Upper and lower bound for comp-sum losses), Assume that is convex, twice continuously differentiable, and satisfies the properties ('()) 0 and ("(u) 0 for any u ( 1 Then, the following property holds: J(t)= e(t))
7

---

Proof sketch For any T E [.: 5.1 define the function J, by [t(t) ft.+(0) - infiulsr ft), where 1t
(u) 1-t (u) + 2 (-(-,), te [0. 1] and @ 0(T + ut)
We aim establish a lower and upper bound for inf [ Jt(t). For any fixed T I } this situation is parallel to that of binary classification (Theorem 4.1 and Theorem 4.2), since we have (0) (7) 0 and (0) ("(r) O. By Theorem 5.2 and the proof of Theorem 4.2, adopting a similar notation, while incorporating the subscript to distinguish different functions 2 and ft.,, we can write Vt [o) {+( = So - "I (-") + 1
2 (u)) du, where 07,-
- कt (0) "5(()] C, < O. Then, by further analyzing this equality, can show - = O(t) for some te [0, 0. Finally, using the fact that 4" reaches its maximum and minimum over compact set, we obtain that I(t)= inf 2 T+(() = @(²). The full proof is included in Appendix L.
(0)
verifies - 0 and
the lower bound inf +]] - = Qt(t) and the upper bound [ +
Theorem 5.3 significantly extends Theorem 4.2 to multi-class comp-sum losses, which include the logistic loss or cross-entropy used with softmax activation function. It shows that the growth rate of H-consistency bounds for comp-sum losses is exactly square-root, provided that the auxiliary function & they are based upon convex, twice continuously differentiable, and satisfies & (u()) < and &" (u) 0 for any (0, 1 which holds for most loss functions used in practice.
5.2 Constrained losses
Here, we consider constrained losses (see [Lee al., 2004]), defined as
Wh E H., (x, x xx y, gostnd (h, x. = Σ ((h(z,3))) subject to
h(z, = =0, yey
+/+
where क: R. - IR. is non-decreasing function. On possible choice for T is the exponential function. As shown by Mao et al. [2023b], for symmetric and complete hypothesis sets, the transformation T for the family of constrained losses can be characterized as follows.
Theorem 5.4 (Mao et al. [2023b, Theorem I I1]). Let H be symmetric and complete hypothesis set. Assume that & is convex, differentiable at zero and satisfies the inequality 4 d'(0) 0. Then, the transformation T can be expressed as
T(I) = inf sup r20 welt
(2
1
(T)
2
n-1
(T + u)
2-11 n-
2
Φ(T D(T-U) w)
2
2
Next, we will show that for the constrained losses, the properties I(t) ={(()) and T(t) O(t) hold as well. Note that by Theorem 5.4, we have
x((2 -((2---1
1 - -(2 1-11- inf sup ((T) n n-1
1- Φ + u2
1+1
( - w)
n-1
720 well
2
2
Therefore, to prove J(t)= O(t2), we only need to show
1100-1100000 1-t 1-t ((T ( u)
1+t D ( u) =
inf sup 720 acR
((()
2
For simplicity, we assume that the infimum over + 2 can be reached within some finite interval [0, A]. A> 0. This assumption holds for common choices of &. as discussed in [Mao et al., 2023b). Furthermore, as demonstrated in Appendix N, under certain conditions on &", the infimum over T [0, A] is reached at zero for sufficiently small values of t. For specific examples, see [Mao et al., 2023b, Appendix D.3], where (tt) = et is considered.
Theorem 5.5 (Upper and lower bound for constrained losses), Assume that & is convex, twice continuously differentiable, and satisfies the properties E' (u) 0 and Φ0 (u) 0 for any 0. Then, for any A 0, the following property holds:
inf sup {upp<ot (2() re(O,A] weR
1-t 2 + u)
1+t < u) = -(()
2
2
8

---

Proof sketch For any T [], define the function J, by (-(t)= f(,(()) - inf ft. (u), where ft.- (u) = 2 (u) 1+2
(-u)) t [0, and (-) 4(r +u). We aim to establish lower
and upper bound for i (t). For any fixed T [0, AJ, this situation is parallel to that of binary classification (Theorem 4.1 and Theorem 4.2), since we also have (0) ('(7) ) > 0 and (0) (T) O. By applying Theorem 5.2 and leveraging the proof of Theorem 4.2, adopting similar notation, while incorporating the т subscript to distinguish different functions D and Jt.7-
(""""""(") + 1+ (-("" du, where oi,r verifies o we can write Vt E [0,40], T+(()= So" "I
and 80 (0) +0(0) C > 0. Then, by further analyzing this equality, we can show the lower bound inf inf A] "i,r = (tt) and the upper bound (0 oi (t) for some te [0,41]: 4 O.
+'(00)
0t
Finally, using the fact that Φ" reaches its maximum and minimum over some compact set, we obtain that J(t) = imfrr(0,44 J. -tt)) The full proof is included in Appendix M.
Theorem 5.5 significantly expands our findings to multi-class constrained losses. It demonstrates that, under some assumptions. which are commonly satisfied by smooth constrained losses used in practice, constrained loss H-consistency bounds also exhibit a square-root growth rate.
6 Minimizability gaps
As shown in Sections 4 and 5, H-consistency bounds for smooth loss functions in both binary and multi-class classification all admit square-root growth rate near zero. In this section, we start by examining how the number of classes impacts these bounds. We then turn our attention to the minimizabilitty gaps, which are the only distinguishing factors between the bounds.
6.1 Dependency on number of classes
Even with identical growth rates, surrogate losses can vary their H-consistency bounds due the number of classes. This factor becomes crucial to consider when the class count is large. Consider the family of comp-sum loss functions goomp with e [0, 2), defined as
b(a-y)
1- (Eareyehtnss 1
-1)
7 1+1, (0,2)
peomp (h,
x, (h,
2-
EEvey (bcceer
log Eveey (hase
7=1.
where ('(u) lo= - 1 (w--1-1) 1)),r2 for any T E (0. Mao et al. [2023f, Eq. (7) &
Theorem 3.1], established the following bound for any h H and E [1,
Re (h) R2, (HI s T (R (h) R Recomp (3() + Mg.or (J() Mea1 (3(),
where [+(() 1 Thus, while all these loss functions show square-root growth, the number of classes acts as a critical scaling factor.
6.2 Comparison across comp-sum losses
In Appendix H, compare minimizability gaps comp-sum losses. We will that minimiz- ability gaps decrease as 7 increases. This might suggest favoring 7 close to 2. But when accounting for n. goomp with minimizability gaps are essential in loss selection. In Appendix J, we will show that the minimizability gaps can become zero or relatively small under certain conditions multi-class classification. such scenarios, the logistic loss is favored, which can partly explain its widespread practical application.
(logistic loss) is optimal since n then vanishes. Thus, both class count and
6.3 Small surrogate minimizability gaps
While minimizability gaps vanish in special scenarios (e.g., unrestricted hypothesis sets, best-in- class error matching Bayes error), we now seek broader conditions for zero or small surrogate minimizability gaps to make our bounds more meaningful.
Due to space constraints, we focus on binary classification here, with multi-class results given in Appendix J. We address pointwise surrogate losses which take the form {(h(z),)) y) for labeled point

---

(z. y). We write = = {h(=):h JC} to denote the set of predictor values at x, which we assume to be independent of æ. All proofs for this section are presented in Appendix
Deterministic scenario. We first consider the deterministic scenario, where the conditional probabil- ity p x) is either zero or one. For deterministic distribution, denote by X, the subset of X over which the label is +1 and by X_ the subset of X over which the label is -1. For convenience, let ((a,-1))
l. a E(a,+ +1) and f_
Theorem 6.1. Assume that D is deterministic and that the best-in-class error is achieved by some he* K. Then, the minimizability gup is null, M(H) 0, iff
2(h' (I),
(z),+13 +1) lu a.s. over ov. (x)" -1) E- a.s. over X...
If further a + E(a, +1) and a + ((a,-1) are injective and l, = ((a,,+1), l- = ((a_,1)). then, the condition is equivalent to h² (x) a, + a a_lxxx__ Furthermore, the minimizability gap is
bounded by e iff p(E[é(h" (z).+1) = +1] -+) 2.+++ (L-P)(E)((((()))) 1y -1] --) S e. In
particular, the condition implies:
B[e(h' (1),+1) 1 y= +1] c and B[e(h" (1)
1-p
The theorem suggests that, under those assumptions, for the surrogate minimizability gap to be zero, the best-in-class hypothesis must be piece- wise constant with specific values on X, and X... The existence of such a hypothesis in HC depends both on the complexity of the decision surface separating X, and X_ and on that of the hypothesis set H. More generally, when the best-in-class classifier e-approximates a4, over X. and a. over X._, then the minimizability gap is bounded by e. As an example, when the decision surface is hyperplane, a hypothesis set of linear functions combined with a sigmoid activation function can provide such a good approximation (see Figure 1 for illustration in simple case).
ai
X+
Figure 1: Approximation provided by sigmoid acti- vation function.
Stochastic scenario. Here, we present a general result that is direct extension of that of the deterministic scenario. We show that the minimizability gap is zero when there exists ht E H that matches a² (z) for all xr, where a² (æ) the minimizer of the conditional error. We also show that the minimizability gap is bounded by when there exists h" E H whose conditional error e-approximates best-in-class conditional error for all x.
Theorem 6.2. The best-in-class error is achieved by some h" H and the minimizability gap is null, M(H) = 0, iff there exists h² H such that for all x.
E[E(h" (x). x]] = inf ([[((a))) y) x] a.s. over X.
ae
further a + Ey[((a.)) x is injective and inf [[[((a,)) y) x] (x)==))(("""))))) æ1. then, the condition is equivalent to h² (x)= (x) for x E X. Furthermore, the mininizability gap is bounded by e, M(H) s c, iff there exists h" E H such that
E
B[E(h" (x). x] inf B[ (().y)))) xx] sc a y
(4)
In deterministic settings, condition (4) coincides with that of Theorem 1. However, in stochastic scenarios, the existence of such a hypothesis depends on both decision surface complexity and the conditional distribution's 's properties. For illustration, see Appendix J.3 where we analyze the exponential, logistic (binary), and multi-class logistic losses.
We thoroughly analyzed minimizability gaps, comparing them across comp-sum losses, and identify- ing conditions for zero or small gaps, which help inform surrogate loss selection. In Appendix F, we show the crucial role of minimizability gaps in comparing excess bounds with HCconsssty bounds. Importantly, combining H-coossstenccy bounds with surrogate loss Rademacher complexity bounds yields zero-one loss (estimation) learning bounds for surrogate loss minimizers (see Appendix O).
7 Conclusion
We established a universal square-root growth rate for the widely-used class of smooth surrogate losses in both binary and multi-class classification. This underscores the minimizability gap as a crucial discriminator among surrogate losses. Our detailed analysis of these gaps can provide guidance for loss selection.
10

---

References
S. Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses. The Journal of Machine Learning Research, (00)1665--674, 2014.
Awasthi, N. Frank, A. Mao, M. Mohri, and Zhong. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Systems, pages 9804 9104-9815, 9815, 202 la.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.01550 2021b.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H -consistency bounds. In Advances in neural information processing systems, pages 782-795, 2022a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. H H-consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, pages 1117-1174, 2022b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pages 10077-10094, 2023a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2023b.
H. Bao. Proper losses, moduli of convexity, and surrogate regret bounds. In Conference on Learning Theory, pages 525-547, 2023.
L. Bartlett and M. H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 98),, 2008.
L. Bartlett, M. Jordan, and J. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 10133)) 156, 2006.
S. Ben-David, D. Loker, N. Srebro, and K. Sridharan. Minimizing the misclassification error rate using a surrogate convex loss. In International Coference on International Conference on Machine Learning, pages 83-90, 2012.
Berkson. Application the logistic function to bio-assay. Journal of the American Statistical Association, 39:357-366 1944.
Berkson. Why prefer logits probits. Biometrics, 7(4):327-333) 1951.
M. Blondel. Structured prediction with projection oracles. In Advances in neural information processing systems, 2019.
Y. Cao, Cai, L. Feng. L. Gu, Gu, B. An, Niu, and M. Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In Advances in neural information processing systems, 2022.
N. Charoenphakdee, Z. Cui, Y. Zhang, and M. Sugiyama. Classification with rejection based on cost-sensitive classification. International Conference on Machine Learning, pages 1507-1517, 2021.
D.-R. Chen, Q. Wu, Y. Ying, and D.-.. Zhou. Support vector machine soft margin classifiers: error analysis. The Journal of Machine Learning Research, 5:1143-1175, 2004.
C. Ciliberto, L. Rosasco, and A. Rudi. A consistent regularization approach for structured prediction. In Advances neural information processing systems, 2016.
C. Ciliberto, L. Rosasco, and A. Rudi. A general framework for consistent structured prediction with implicit loss embeddings. The Journal of Machine Learning Research, 21(1)3352233188 2020.
C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. International Conference on 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 algorithmss for learning with rejection in binary classification. Annals Mathematics and Artificial Intelligence, 2023.
C. Cortes, A. Mao, C. Mohri, M. Mohri, and Zhong. Cardinality- set prediction and top-k classification. In Advances in neural information processing systems, 2024.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 2(Dec):265-292, 2001.
A. L.. Dontchev and R. T. Rockafellar. Robinson's implicit function theorem and its extensions. Math. Program., 117(1-2):129-17,, 2009.
J. Duchi, K. Khosravi, and F. Ruan. Multiclass classification, information, divergence and surrogate risk. The Annals of Statistics, 46(6B):3246-322) 2018.
J. Finocchiaro, R. Frongillo, and B. Waggoner. An embedding framework for consistent polyhedral surrogates. In Advances in neural information processing systems, 2019.
R. Frongillo and Waggoner. Surrogate regret bounds for polyhedral losses. In Advances in Neural Information Processing Systems, volume 34, pages 21569-21588 2021.
W. Gao and Z.-H. Zhou. On the consistency of AUC pairwise optimization. In International Joint Conference on Artificial Intelligence, 2015.
W. Kotlowski, K. J. Dembezynski, and E. Huellermeier. Bipartite ranking through minimization of univariate loss. International Conference on Machine Learning, pages 1113-1120, 2011.
K. Kuratowski and C. Ryll-Nardzewski. A general theorem on selectors. Bull. Acad. Pol. Sci., Sér. Sei. Math. Astron. Phys., (3(8):397-4033 1965.
Kuznetsov, M. Mohri, and U. Syed. Multi-class deep boosting. Advances in Neural Information Processing Systems, pages 2501-2509, 2014.
M. Lapin, M. Hein, and B. Schiele. Loss functions for top-k error: Analysis and insights. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1468-1477, 2016.
Y. Lee, Lin, and Wahba. Multicategory support vector machines: Theory and application the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67-81, 2004.
P. Long and R. Servedio. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809 2013.
M. Mahdavi, L. Zhang, and R. Jin. Binary excess risk for smooth convex surrogates. arXiv preprint arXiv: 1af.::1402.7922 2014.
A. Mao, Mohri, M. Mohri, and Y. Zhong. Two-stage learning defer with multiple experts. In Advances in neural information processing systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International conference on Machine learning, 2023c.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In /CM1.2023 Workshop The Many Facets of Preference-Based Learning, 2023d.
A. Mao, M. Mohri, and Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
12

---

A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning, 2023f.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning to defer with multiple experts. In International Symposium on Arlificial Intelligence and Mathematics, 2024a.
A. Mao, M. Mohri, and Y. Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. In International Conference on Algorithmic Learning Theory, 2024b.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. In International Conference on Artificial Intelligence and Statistics, 2024c.
A. Mao, M. Mohri, and Y. Zhong, Enhanced H -cconsistency bounds. arXiv preprint arXiv:2407.1372. 2024d.
A. Mao, M. Mohri, and Zhong. H-consistency guarantees for regression. International Conference on Machine Leurning, pages 34712-34737, 2024e.
A. Mao, M. Mohri, and Y. Zhong. Multi-label learning with stronger consistency guarantees. In Advances in neural information processing systems, 2024f.
A. Mao, M. Mohri, and Y. Zhong. Realizable H-consistent and Bayes-consistent loss functions for learning defer. In Advances in neural information processing systems, 2024g.
A. Mao, M. Mohri, and Y. Zhong. Regression with multi-expert deferral. In International Conference on Machine Learning, pages 34738-34759, 2024h.
A. K. Menon and R. C. Williamson. Bayes-optimal scorers for bipartite ranking. In Conference on Learning Theory, pages 68-106, 2014.
C. Mohri, D. Andor, Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with a fixed predictor: Application to decontextuulizzatinn. In International Conference on Learning Representations, 2024.
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning. MIT Press, second edition, 2018.
H. Mozannar and D. Sontag. Consistent estimators for learning to defer to expert. In International Conference on Machine Learning, pages 7076-7087, 2020.
H. Mozannar, H. Lang, D. Wei, P. Sattigeri, S. Das, and D. Sontag, Who should predict? exact algorithms for learning defer to humans. In International Conference Artificial Intelligence and Statistics, pages 10520-10545, 2023.
C. Ni, N. Charoenphakdee, J. Honda, and M. Sugiyama. On the calibration of multiclass classification with rejection. In Advances in Neural Information Processing Systems, pages 2582-2592 2019.
A. Nowak, F. Bach, and Rudi. Sharp analysis of learning with discrete losses. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1920-1929, 2019.
A. Nowak, F. Bach, and A. Rudi. Consistent structured prediction with max-min margin markov networks. In International Conference on Machine Learning, pages 7381-7391, 2020.
A. Nowak, A. Rudi, and F. Bach. On the consistency of max-margin losses. In International Conference on Artificial Intelligence and Statistics, pages 4612-4633, 2022.
A. Nowak-Vila, F. Bach, and A. Rudi. A general theory for structured prediction with smooth convex surrogates. arXiv preprint arXiv:
2019.
A. Osokin, F. Bach, and S. Lacoste-Julien. On structured prediction theory with calibrated convex surrogate losses. Advances in Neural Information Processing Systems, 2017.
B. Pires, C. Szepesvari, and M. Ghavamzadeh. Cost-sensitive multiclass classification risk bounds.
In International Conference on Machine Learning, pages 1391-1399, 2013.
13

---

H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics, 12(1):530-555 2018.
M. D. Reid and R. C. Williamson. Surrogate regret bounds for proper losses. Conference Machine Learning, pages 897-904, 2009.
International
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-28) 287, 2007.
A. Tewari and P. I.. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36):1007-1025, 2007.
K. Uematsu and Lee. On theoretically optimal ranking functions bipartite ranking. Journal of the American Statistical Association, 1265119:1311-122, 2017.
P. F. Verhulst. Notice sur la loi que la population suit dans son accroissement. Correspondance mathématique el physique, 10:113--121, 1838.
F. Verhulst. Recherches mathématiques sur la loi d' d'accroissement de la population. Nouveaux Mémoires de d l'Académie Royale des Sciences Belles-Lettres de Bruxelles, 18:1 -42, 1845.
R. Verma and E. Nalisnick. Calibrated learning defer with one-vs-all classifiers. In International Conference on Machine Learning, pages 22184-22202. 2022.
R. Verma, D. Barrejón, and E. Nalisnick. Learning to defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In International Conference on Artificial Intelligence and Statistics, pages 1111--11444 2023.
J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. European Symposium on Artificial Neural Networks, 4(6), 1999.
Yang and Koyejo. On the consistency of top-k surrogate losses. In International Conference on Machine Learning, pages 10727-10735, 2020.
J. Yu and M. B. Blaschko. The lovász hinge: A novel convex surrogate for submodular losses. IEEE transactions on pattern analysis and machine intelligence, 42(3):735-748, 2018.
M. Yuan and M. Wegkamp. Classification methods with reject option based on convex risk minimiza- tion. Journal of Machine Learning Research, 11(1), 2010.
Zhang, T. Liu, and D. Tao. On the rates of convergence from surrogate risk minimizers to the Bayes optimal classifier. IEEE Transactions Neural Networks and Learning Systems, 33(10): 5766-5774, 2021.
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.
T. Zhang, Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56 85, 2004a.
Zhang. Statistical analysis some catti-ya large margin classification methods. Journal of Machine Learning Research, 5(Oct): 225-1251, 2004b.
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.
14

---

Contents of Appendix
Related work
16
B Pointwise loss functions Proof of Lemma 2.1
17
General form of H-consistency bounds
18
D Properties of minimizability gaps
18
Examples of H--consistnncy bounds
19
F Comparison with excess error bounds
20
Polyhedral losses versus smooth losses
H Comparison of minimizability gaps across comp-sum losses
22
Small surrogate minimizability gaps: proof for binary classification
22
J Small surrogate minimizabilitty gaps: multi-class classification
24
J.1
Deterministic scenario
24
J.2
Stochastic scenario
25
J.3 Examples
26
K Proof for binary margin- based losses (Theorem 4.2)
27
L Proof for comp-sum losses (Theorem 5.3)
28
M Proof for constrained losses (Theorem 5.5)
30
N Analysis of the function of 7
32
Generalization bounds
Future work
33
15

---

A Related work
The Bayes-consistency of surrogate losses has been extensively studied in the context of binary classi- fication. Zhang [2004a], Bartlett et al. [2006] and Steinwart [2007] established Bayes-consistency for various convex loss functions, including margin-based surrogates. They also introduced excess error bounds (or surrogate regret bounds) for margin-based surrogates. Other works include Chen et al. [2004], which specifically studied the SVM g-norm soft margin loss and established a square-root excess error bound with an optimal constant for that specific family, and Reid and Williamson [2009], which established tight excess error bounds for proper losses in binary classification.
The caaes--cosssstenss of several surrogate loss function families in the context of multi- classification has also been studied by Zhang [2004b] and Tewari and Bartlett [2007]. Zhang [2004b] established a series of results for various multi-class classification formulations, including negative results for multi-class hinge loss functions [Crammer and Singer, 2001], as well as positive results for the sum exponential loss [Weston and Watkins, 1999, Awasthi, Mao, Mohri, and Zhong, 2022a], the (multinomial) logistic loss [Verhulst, 1838, 1845, Berkson, 1944, 1951], and the constrained losses [Lee et al., 2004]. Later, Tewari and Bartlett [2007] adopted a different geometric method to analyze Bayes-consistency, yielding similar results for these loss function families. Steinwart [2007] developed general tools to characterize Bayes consistency for both binary and multi-class classification. Additionally, excess error bounds have been derived by Pires et al. [2013] for a family of constrained losses and by Duchi et al. [2018] for loss functions related to generalized entropies.
For surrogate loss E, an excess error bound holds for any predictor h and has the form ( eg, s V (h) - EJ), where ELp (4) and E, represent the expected losses of h for the zero-one loss and surrogate loss respectively, E7 and & the Bayes errors for the zero-one and surrogate loss respectively, and V non-decreasing function.
The growth rate of excess error bounds, that is the behavior of function &i near zero, has gained attention in recent research [Mahdavi et al., 2014, Zhang et al., 2021, Frongillo and Waggoner, 2021, Bao, 2023]. Mahdavi et al. [2014] examined the growth rate for smoothed hinge losses in binary classification, demonstrating that smoother losses result in worse growth rates. The optimal rate is achieved with the standard hinge loss, which exhibits linear growth. Zhang et al. [2021] tied the growth rate of excess error bounds in binary classification to two properties of the surrogate loss function: consistency intensity and conductivity. These metrics enable comparisons of growth rates across different surrogates. But, we establish lower and upper bounds for the growth rate of excess error bounds under specific regularity conditions?
Frongillo and Waggoner [2021] pioneered research on this question in binary classification settings. They established critical square-root lower bound for excess error bounds when a surrogate loss is locally strongly convex and has a locally Lipschitz gradient. Additionally, they demonstrated a linear excess error bound for Bayes-consistent polyhedral loss functions (convex and piecewise-linear) [Finocchiaro et al., 2019] (sec also [Lapin et al., 2016. Ramaswamy et al., 2018, Yu and Blaschko, 2018, Yang and Koyejo, 2020D. More recently, Bao [2023] complemented these results by showing that proper losses associated with Shannon entropy, exponential entropy, spherical entropy, squared a-norm entropies and a- a-polynomial entropies, with a > 1, also exhibit a square-root lower bound for excess error bounds relative the fiddistance.
However, while Bayes-consistency and excess error bounds are valuable, they are not sufficiently informative, as they are established for the family of all measurable functions and disregard the crucial role played by restricted hypothesis sets learning. As pointed out by Long and Servedio [2013], in some cases, minimizing Bayes-consistent losses can result in constant expected error, while minimizing inconsistent losses can yield an expected loss approaching zero To address this limitation, the authors introduced the concept of realizable K-consistencyy further explored by Kuznetsov et al. [2014] and Zhang and Agarwal [2020]. Nonetheless, these guarantees are only asymptotic and rely on strong realizability assumption that typically does not hold in practice.
Recent research by Awasthi, Mao, Mohri, and Zhong [2022b,a] and Mao, Mohri, and Zhong [2023f,c.e.b] has instead introduced and analyzed H-consistency bounds. These bounds are more informative than Bayes-consistency since they are hypothesis set-specific and non-asymptotic. Their work covers broad families of surrogate losses in binary classication, multi-class classification, struc- tured prediction, and abstention [Mao, Mohri, Mohri, and Zhong, 2023a]. Crucially, they provide upper bounds on the estimation error of the target loss, for example, the zero-one loss in classification,
16

---

that hold for any predictor h within hypothesis set J.. These bounds relate this estimation error to the surrogate loss estimation error. Their general form is: (h. - " 2 f({ ( (J))) where (,g and & (H) represent the best-in-class expected losses for the zero-one and surrogate loss respectively, and f is non-decreasing function continuous zero. H-consistency bounds imply in particular excess enror bounds, when the hypothesis set is taken to be the family of all measurable functions.
The authors have further analyzed K-conssitency bounds in structured prediction, ranking, and abstention.
Mao, Mohri, and Zhong [2023e] revealed limitations of existing structured prediction loss functions, demonstrating they lack Bayes-consistency. They introduced new surrogate loss families proven to benefit form H--consistency bounds, thus also establishing sayes-consistency. This complements earlier negative finding about the Bayes-consistency of Struct-SVM and positíve results for quadratic surrogate (QS) losses or some non-smooth polyhedral-type loss functions [Osokin et al., 2017, Ciliberto et al., 2016, Blondel, 2019, Nowak- Vila et al., 2019, Nowak al., 2019, 2020, Ciliberto et al., 2020, Nowak et al., 2022].
Mao et al. [2023c] showed that there are no meaningful H-consistency bounds for general pairwise ranking and bipartite ranking surrogate losses with equicontinuous hypothesis sets, including linear models and neural networks. They proposed ranking with abstention as solution. These results demonstrated that although these surrogate loss functions have been shown to be Bayes-consistent in various studies [Kotloskii et al., 2011, Menon and Williamson, 2014, Agarwal, 2014, Gao and Zhou, 2015, Uematsu and Lee, 2017], they are, in fact, not K-consistent.
Mao et al. [2023a] applied co-nonsisyy bounds to two-stage learning to defer scenarios. designing new surrogate losses. This complemented the Bayes-consistent surrogate losses in the single-stage scenario of learning to defer [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022. Verma et al., 2023, Mozannar et al., 2023] or learning with abstention [Bartlett and Wegkamp, 2008, Yuan and Wegkamp, 2010, Cortes et al., 201 b,,,, Ramaswamy et al., 2018, Ni et al., 2019, Charoenphakdee et al., 2021, Cao al., 2022, Cortes al., 2023].
Mao, Mohri, and Zhong [2024d] recently established enhanced K--consistnncy bounds based on more general inequalities relating conditional regrets. They derived more favorable distribution- and predictor-dependent bounds in various scenarios including standard multi-class classification, binary and multi-class classification under Tsybakov noise conditions, and bipartite ranking. JC-consistency bounds have also been studied in the scenario of adversarial robustness [Awasthi et al., 202 la.b, 2023a,b], bounded regression [Mao al., 2024e], regression with multi-expert deferral [Mao et al., 2024h]. top-k classification [Cortes et al., 2024], multi-label learning [Mao et al., 2024f], score-based abstention [Mao al., 2024c], medictor-rejecton abstention [Mao et al., 2024b], learning to abstain with a fixed predictor with application in decontextualization [Mohri et al., 2024], ranking with abstention [Mao et al., 2023d], realizable learning to defer [Mao et al., 2024g], and learning to defer with multiple experts [Mao et al., 2024a].
This papers presents characterization of the growth rate of K-consistency bounds, that is how quickly the functions/ f increase near zero, both in binary and multi-class classification.
B Pointwise loss functions - Proof of Lemma 2.1
Lemma 2.1. Let & be a pointwise loss function. Then, the Bayes error and the approximation error can be expressed as follows: E7 E(Haa) [x x)) and A. = EJ) - E., (H.,,,
Proof. By definition, for a pointwise loss function E, there exists a measurable function é: x R, such that E(h, xr, y) = ((h(x), y). where h(x) = [h( "),...,,(((,). Mxx,)) n)] is the score vector of the predictor h. Thus, the following inequality holds:
e, (Hall, x) inf [[ x. []] inf L [[[((a,))))) y) [=].
heth
Since è (a., y) + RR measurable, the function (a, + E.y E.[ (1)))) v) xx] is also measurable. We now show that the function + () infoeR Ey [(((( y) [x] is also measurable.
17

---

To do this, we consider for any B > O, the set (2: [y(((a))) |=]
3) which can be expressed
x: inf [[((a,)) oeR
< 3a E IR" such that " B(((a,v) | <
Uxx (a. x): {
where Iy is the projection onto X. By the measurable projection theorem, inf Ey[e(a, v) æ is measurable. Then, since pointwise difference of measurable func- tions is measurable, for all n e N, the set { (.. [(( y) æ inf Ey y) x²] # is measurable. Thus, by Kuratowski and Ryll-Nardzewski [1965]'s measurable selection theorem, for all n e N, there exists a measurable function h, x + a e IR" such that the following holds:
1
Ce x)) =) = inf Elf(a, x
ej (Hall, x) n
ocR" y
Therefore, we have
1 (HC.) s El (h m)1 Ele, (Hall, x)] }]+ (HC.n)
"
By taking the limit +00, obtain 87 (Hall) (.r[eT(Han =)] By definition, At(H)
et (IC) E (Han)) = Eg (H) E2 [et (Hall 2. This completes the proof.
C General form of K-consistency bounds
Fix target loss function & and surrogate loss é, Given hypothesis set H, bound relating the estimation errors of these loss functions admits the following form:
vh H. (h) E7, (I0) To (h) E3,0))))) (JO).
(5)
where, for any distribution D, R2 + R., a non decreasing function on R.. We will assume that TD is concave. In particular, the bound should hold for any point mass distribution &g. X. We will operate under the assumption that the same bound holds uniformly over X and thus that there exists fixed concave function I' such that T's_ T for all
Observe that for any point mass distribution 8,, the conditional loss and the expected loss coincide and therefore that we have Ee, (h) 87, (HC) oC, æ), and similarly with L1. Thus, we can write:
Vh H. Vx e X, Aee, (h, x) < I(AC Therefore, by Jensen's inequality, for any distribution D, we have
Vh e HC, E[Ae,, xx (h,
Since E. Ex [e
(h, x)] 9
&e, Eh, (I0)+Me, (3() and similarly with f1. we obtain the following
bound for all distributions D:
Vhe H. (h) E (I))= M,, & S(EE, (h) E7, (30) Me, (3O).
This leads the general form of H-consistencyy bounds that we will be considering, which includes the key role of the minimizability gaps.
D Properties of minimizability gaps
By Lemma 2.1, for a pointwise loss function, we have & (Hai) TE,, [e (Han,,))) thus the minimizability gap vanishes for the family of all measurable functions.
Lemma D.I. Let be pointwise loss function. Then, have Mc(HCa)) 0.
18

---

((u)
margin-
margin-based based losses & vh(x))
H. HC-Consitenccy bounds
(l. (h) E (H) Me-i (9) /2((,(h)))))))))))))))))))>)))) (00 (.))))
log(1 +ea)
log(1 + E =
Elo (hi E (9() Ma-1 (9() s (2((()))))))) (30) M((1)*
max maxx0,110 u]
max 0, 2)(x2)²
E (ht E (H() Ma (30) 5 (E)
max(0,1+*0
max(0, 1 3)((1))
El (fi) Efg (9) Me.. (30 -()))) +M((J))
Table
Examples of H-cconsisenccy bounds for binary margin-based losses.
Thus, in that case, (6) takes the following simpler form:
vh e H, Egg Ei, (Han) & TEE (h) Eg (Han)).
In general, however, the minimizabiliy gap is non-zero for restricted hypothesis set DC and is therefore important to analyze. Let Jx) be the difference of pointwise infima (HH [y (H - ez (Han; which is non-negative. Note that, for pointwise loss function, the min- imizability gap can be decomposed as follows in terms of the approximation error and the difference of pointwise infima:
Mc( (3() -
(T ( =A,(H)) + (7G.) [[[e (HC,
87 (Han) (H.,
=A(())) (3)( s (.)())).
Thus, the minimizabiliy gap can be upper bounded by the approximation error. It however a finer quantity than the approximation error and can lead to more favorable guarantees. When the difference of pointwise infima can be evaluated or bounded, this decomposition can provide a convenient way to analyze the minimizability gap in terms of the approximation error.
Note that (J() can be non-zero for families of bounded functions. Let y = [-1,+1} and H( be a family of functions h with [h(x)] s A for all x X and such that all values in [-A, +A] can be reached. Consider for example the exponential- based margin loss: {(h,,,,)
e wh((), Let (()) ((+1|z) = D(Y= + z). Thus, (h) = n(z)e h(a)) + (1 (=))))(()), Then, it is not hard that e7 x)) 211(=)(1 (xx) for all but ()(, depends on A with (²) log n(a) A if (xx) 1/2, max 2 log I-n(2), -A)
the minimizing value for hxx)) being: min [1 2 1-)(2)
otherwise. Thus, in the deterministic case, J.()) = A
When the best-in-class error coincides with the Bayes enror, (H) (Hau), both the approxima- tion error and minimizability gaps vanish.
Lemma D.2. For any loss function such that (H() (3Can) = E.[e, (Han, 2) we have Mc(H)) = (T( O.
Proof. By definition, Ae(J)) (T() Ex (Hau) 0. Since have Mc(H)) s Ae(H),, this implies M+HH)=
E
Examples of H-ccosissenccy bounds
Here, we compile some common examples of "H-consistency bounds for both binary and multi-class classification. Table 1, 2 and include the examples of "C-consistency bounds for binary margin-based losses, comp-sum losses and constrained losses, respectively.
These bounds are due to previous work by Awasthi et al. [2022b] for binary margin-basse based losses, by Mao et al. [2023f] for multi-class comp-sum losses, and by Awasthi al. [2022a] and Mao al. [2023b] for multi-class constrained losses, respectively. We consider complete hypothesis sets for binary classification (see Section 4), and symmetric and complete hypothesis sets for multi-class classification (sce Section 5).
19

---

<(u)
Comp-sum losses E
H-CConsitencyy bounds
1-
Egee M(x'')) )-f(a)))
E (h) E (H))+ + Mi. (96) (E) 8100+ -()00))))))0))00)))00 -
log(u)
log
Ela (h) E (H) Me (9) s (2((((())))))))))))))))))))))))) - (0) +M((H))*
Evroy chisivts
1 [[ ==]
1
E (h) ,,, (H) Ma.. (9) s V2n -00 + +M)()))
Extry eMcarss
1 u
Eveoy obia.u's
Elg- (h) E,,, (Hf) + Mip. ( ( (30 Mc(9))
s
Table 2: Examples of H-consistency bounds for comp-sum losses.
2(u)
Constrained losses
91- J1-Consisenncy bounds
Exsy ((x.d')
Eto. (1)) - E2__, ((0_000022...(()2222((0000000000
ma 10..1+100 u3²
Eyey max(0, + {/
Eto. (h) - E2__ MM,, (C0)))00)0
(1 + u)²
Evru (1 + h(2,1/))²
Efo (h) - Eú (3() (10) (000000000000
max(0,1+1))
Ey'ry max 1+ (()
Eto.s - (00)))00000
Table 3: Examples of H-consistency bounds for constrained losses with Eyey h(2; v) O.
F Comparison with excess error bounds
Excess error bounds can be used to derive bounds for hypothesis set H expressed in terms of the approximation error. Here, we show, however, that, the resulting bounds are looser than H-consistency bounds.
Fix a target loss function & and surrogate loss é, Excess error bounds, also known as surrogate regret bounds, are bounds relating the excess errors of these loss functions of the following form:
Vhe E Hall,
eEEe (h) E7, (Han)) s &e, (h) E7, (Han),
(8)
where th: RR + R. is a non-decreasing and convex function on R... Recall that as shown in (1), the excess error can be written as the sum of the estimation error and the approximation error. Thus, the excess error bound can be equivalently expressed as follows:
Vh é Hall,
v (h) (36 + Ae, (J))= s &e, (h) E2, (30) + Ac, (J)).
In Section 3, we have shown that the minimizabiliy gap can be upper bounded by the approximation error (HF x AAH)) and is in general a finer quantity for surrogate loss 4-- However, we will show that for a target loss Eg that is discrete, the minimizabiliy gap in general coincides with the approximation error.
Definition F.1. We say that a target loss Eg is discrete if we can write l2 x, y) = L(h(z),)) y) for some binary function L: y x y R.,.
In other words, a discrete target loss &a is explicitly a function of both the prediction h(x) and the true label where both belong to the label space y. Consequently, it can assume at most n² distinct discrete values.
Next, we demonstrate that for such discrete target loss functions, if for any instance, the set of predictions generated by the hypothesis set completely spans the label space, then the minimizability gap is precisely equal to the approximation error. For convenience, we denote by H(z) the set of
predictions generated by the hypothesis set on input x e X, defined as H(x) (h(z):h E HC)
Theorem F.2. Given discrete targer loss function e- Assume that the hypothesis set H. satisfies, for any x E X,, H(x)= = y. Then, we have Jr, (H) = 0 and Mc,(H) = Ar, (H).
Proof. As shown in Section 3, the minimizabilityy gap can be decomposed in terms of the approxima- tion error and the difference of pointwise infima:
Mc, (F) = Ar, (3)) - Je, (H)
= (3)) - E e (H, x)) - Ci, (Han,
x
20

---

By definition and the fact that Eg is discrete, the conditional eπror can be written as
C₁2 (h, x)
Σ (2,,
Σ [(())=)(((()))))) ye
yey
Thus, for any x X. the best-in-class conditional error can be expressed as By the assumption that H(x:) y, obtain
ei xH, = inf
Σ
[(()))))((())))))= - inf s/eH(n) yey
Ep(vl=)((/.v)
helf yey
Vo E X, C₁ xH ()
inf
Σ (v)'))) inf Σ L(vl=))('''>)) )) -C (Han,
y g'eH(2) yey
v'ey yey
Therefore, Jt, (3() = Ex ei (H, x) City (Hall, x)) and and (H) (3).
By Theorem F.2, for a target loss & that is discrete and hypothesis sets H modulo mild assumptions, the minimizabiliy gap coincides with the approximation error. In such cases, by comparing an excess error bound (9) with the H-consistency bound (6):
Excess error bound:
(h) (90) Ac, A3, & &t, (h) - E,, (3() + As, (H) (h) E (H) Mr, (H)) Ee, (h) E7, (H) Mr, (H),
H--consstennyy bound:
obtain that the left-hand side of both bounds equal (since Mr, (H) Ai, (H)), while the right-hand side of the JC-consistnccy bound is always upper bounded by and can be finer than the right-hand side of the excess error bound (since Mr, (J)) s Ac, (H))), which implies that excess error bounds (or surrogate regret bounds) are in general inferior to H-conssisenccy bounds.
G Polyhedral losses versus smooth losses
Since H(-consistency bounds subsume excess error bounds as a special case (Appendix F), the linear growth rate of polyhedral loss excess error bounds (Finocchiaro al. [2019]) also dictates linear growth rate for polyhedral HC-consistency bounds, if they exist. This is illustrated by the hinge loss or p-margin loss which have been shown to benefit from H-consistency bounds [Awasthi al., 20226].
Here, we compare in more detail polyhedral losses and the smooth losses. Assume that a hypothesis set H is complete and thus H(x) for any X. By Theorem F.2, we have Ale (H) Mc, (H). As shown by Frongillo and Waggoner [2021, Theorem 31, Bayes-consisten polyhedral loss $ poly admits the following linear excess bound, for some O.
vh E H. 31 (E (h) Eto (H) M4o- (H)) E (h) E. Eo (H) As poty (H). (10)
However, for smooth loss T ssmoohh, if it satisfies the condition of Theorem 4.2, T smmoohh admits the following K-consistency bound:
Vh H. J(Eta Ei + Mo.. s Egaanarn (h) smooth (H) smonth (H). (11)
where J(t) (t)). Therefore, our theory offers a principled basis for comparing polyhedral losses (10) and smooth losses (11), which depends on the following factors:
The growth rate: linear for polyhedral losses, while square-root for smooth losses.
The optimization property: smooth losses are more favorable for optimization compared to polyhedral losses, in particular with deep neural networks.
The approximation theory: the approximation error Aspa, (H) appears the right-hand side of the bound for polyhedral losses, whereas finer quantity, the minimizability gap Mopamooe (9(), is present the right-hand side of the bound for smooth losses.
21

---

H Comparison of minimizability gaps across comp-sum losses
For Ccomp loss functions, T [0, 2), we can characterize minimizability gaps as follows.
Theorem H.1. Assume that for any I X, we have (1h(,,1)..... n)): JC3 = [-A, +A]".
Then, for comp-sum losses Gooup and any deterministic distribution, the mininizability gaps can be expressed as follows:
Mggoop (3C) S Mg.omo (3C) = fr (Ro
( for ( (HC,))
(12)
where fr (u) (og((+u))r.a) T ((1 u) 1-T 1) and C gooan (H, = =E E (n-A1 Moreover,
Mc.om (H) is non-increasing function of
Proof. Since fr is concave and non-decreasing, and the equality & fo (Lr-o) holds, the minimiz- ability gaps can be upper bounded follows, for any 20,
M Mecm (HC)& fo RRjeome (3O) ElC x)]
Since the distribution is deterministic, the conditional error can be expressed as follows:
Cyomp (1,, =fr
exp(h(ar,)) - 11(2,, Umax)) y'myymax
Σ
(13)
where Unnx = argmax p x).. Using the fact that f+ is increasing for any T > O, the hypothesis h" (x, A1 ym A1 y= achieves the best-in-class conditional error. Thus,
e Cgomm (H, Cxcamp (h* 2x) f- Gooun (H,
where Cxonn (H,x) = 2A (n 1). Therefore,
M Morop (H) fr (R (0 f. f-(eeeono (H,
This completes the first part of the proof. Using the fact that T + (+ (11)= f- (u2) is a non-increasing function of for any U1 2 U2 0, the second proof is completed as well.
The theorem shows that for comp-sum loss functions eoomp, the minimizability gaps are non- increasing with respect to r. Note that t5 satisfies the conditions of Theorem 5.3 for any T [0. 2). Therefore, focusing on behavior near zero (ignoring constants), the theorem provides principled comparison of minimizability gaps and H-consistenccy bounds across different comp-sum losses.
I Small surrogate minimizability gaps: proof for binary classification
Theorem 6.1. Assume that 'D is deterministic and that the best-in-class error is achieved by some h" H. Then, the minimizability gap is null, M(J() 0, iff
((h'()),1)) = lu a.s. over Xx,, E(h" -z). = a.s. over X_..
If further E(a, +1) and a ((a,-1) are injective and l, f(a,,+1), l_ ((a. then, the condition is equivalent to h² h²(x)) = a4 L + a Laex__ Furthermore, the minimizability gap is bounded by iff p(E[((h" (z),+1) y +1] 2.) (1-p)(E[((H(x))) (x), -1=--))y=-11---- s In particular, the condition implies:
B[e(h' (x),+1) 1y= la - c and (T)(
l. c 1-p
Proof. By definition of h², using the shorthand p= Ply +1], we can write inf [[((h(z),)) [[((h"(x)vv) helt
22

---

Since the distribution is deterministic, the expected pointwise infimumm can be rewritten as follows:
inf ([((h(=), heat
xm]
E
inf B[[(a, y) [t]
inf ((a, +1) +1 (1-p) inf ((a aed
LoeA
asA
= =pl+ + (1 -p)_,
A ((a,-1 -1). Thus, have where 4 = anf +(a++1) and L- and
- pp +1) - 4, y = +1] (1 (1- B[C(h" (x), -
In view of that, since, by definition 4 and f_, the expressions within the conditional expectations are non-negative, the equality M(3C) 0 holds iff e(h" ((h"(x), +1) 4 = 0 almost surely for any in X, and (1)) -1) &_ almost surely for any x X.. This completes the first part of the proof. Furthermore, M(H) is equivalent to
(B(E()(()) - & - (1-
that is
y= P(E y --1 - -x)) sc.
In light of the non-negativity of the expressions, this implies in particular:
+1] E[e(h" (z), +1) +1] +1] - and B(e(h"(z), (x),-))>===11 -
p
This completes the second part the proof. Theorem 6.2. The best-in-class error is achieved by some ht H and the minimizability gap is mill, M(J)== 0, iff there exists h² H such that for all x.
E[E(K" (x)..) x]
inf [[[((a,)) x] a.s. over X. osA y
If further - E,,L(a, v) x is injective and infos Ey (((a,))) E,l (x). æ]. then, the condition equivalent to h (a) xx (x) a.s. for x E X. Furthermore, the minimizability gap is bounded by e, M(H) S iff there exists He e H such that
B (z). [x] inf E[ y) m1] se.
E
(4)
Proof. Assume that the best-in-class error achieved by some h1* E H.. Then, we can write
inf ([[((((())))))))) F[((h =[((( =
heth
The expected pointwise infimum can be rewritten as follows:
E inf B[<(h()),))
E inf E[[((,, [x]] LoaA y
heetC y
Thus, we have
M(H
El (x) 2
inf B[((a,y) xx]
and
In view of that, since, by the definition of infimum, the expressions within the marginal expectations are non-negative, the condition that M(()) implies that
B[[(hh (x).v) [=] inf R[((a,)) |x: a.s. over X. aeA
On the other hand, if there exists ht H such that the condition (3) holds, then,
M(H) = inf B[((h(x). v) E inf B[E(a, v) []] s E (()(((())))) inf (aa--naa(aaaa v) |x]
kel
a Lae
asA
Since M(J() is non-negative, the inequality is achieved. Thus, we have
M(F() 0 and inf =[) (x). hefi
23

---

If there exists h* 6 T such that the condition (4) holds, then,
M(()) = inf B[((h(z), v)
E inf B[<(a, Laed
æ]] s E Ele (2).v))
- x =6
inf El ac
hel
On the other hand, since we have
M(H) = E (x).)) -nf
inf Enf
and
M(H) s implies that
E (x)( inf E[ x] =
and
This completes the proof.
J Small surrogate minimizability gaps: multi-class classification
We consider the multi-class setting with label space (1, n). In this setting, the surrogate loss incurred by predictor h labeled point (2r.)) be expressed by ((h(rr,,), where M(x)= = [h(x, 1)...., ()r,,)) is the score vector of the predictor h. We denote by A the set of values in RD taken by the score vector of predictors in H x, which assume be independent of æ: A (h()):h HC, for all e X.
J.1 Deterministic scenario
We first consider the deterministic scenario, where the conditional probability p(y|z) is either zero or one. For a deterministic distribution, we denote by Ig the subset of X over which the label For convenience, let l inf ((a,)) k), for any k E [n].
Theorem J.1. Assume that D is deterministic and that the best-in-class error is achieved by some he K. Then, the minimizability gap is null, M(H) 0, iff
wk [m], E(h" (x), = lg a.s. over Xx.
further a + [(a, k) is injective and Ey laa,, for all k E [n]. then, the condition is equivalent to Vk E [n], ht" (x) = Og a.s. a.s.for for E Xy. Furthermore, the minimizability gap is bounded by e, M(H) S Se, iff
Σ (E] (x)((((((x)) y= = k] 4x) Se. kE[[
In particular, the condition implies:
[[]( y= k] lx wk e [n].
pk
Proof. By definition of h² using the shorthand pı: Ppy for any ls é [n]] we can write
inf ([[(((x)).))) E[(h) = Σ ps E[((h" (T)(("))),))) 1 =k k]. k=[n]
heSe
Since the distribution is deterministic, the expected pointwise infimum can be rewritten follows:
inf (B(((h()),)) æ]] Lhest
E inf El((a, | LasA
Σ ke[m]
ph inf E(a, k) Σ pulk, aeA
ke[n]
where 4 infaes E(a; k). for any [m]. Thus, have
M(H Σ pa B[((h" - le 1y k). ke[m]
In view of that, since, by definition of Cx. the expressions within the conditional expectations
non non-negatin negative, the equality M(H)) = holds iff E(h" (x), k) - Ea = 0 almost surely for any x in Xg.
vk e [n]. Furthermore, (()) is equivalent to
Σ kc[n]
Pa E[((h' (x), k) 4 y k kl
24

---

that is
Σ Pa (E(E(( y= k] [4]-4x 4x) S.
Ac(n]
In light of the non-negativity of the expressions, this implies in particular: (z), y= k] Ex s _ L.k vkk[n]
Ps
This completes the proof.
The theorem suggests that, under those assumptions, for the surrogate minimizability gap be zero, the score vector of best-in-class hypothesis must be piecewise constant with specific values on Xş- The existence of such a hypothesis in H depends both on the complexity of the decision surface separating Nr and on that of the hypothesis set H. The theorem also suggests that when the score vector of best-in-class classifier c-approximates og over Xg for any e [n]. then the minimizability gap is bounded by The existence of such a hypothesis in H depends the complexity of the decision surface.
J.2 Stochastic scenario
In the previous sections, we analyze instances featuring small minimizability gaps in a deterministic setting. Moving forward, we aim to extend this analysis to the stochastic scenario. We first provide two general results, which are the direct extensions of that in the deterministic scenario. The following result shows that the minimizability gap is zero when there exists h H that matches a" (ar) for all 2, where a" (x) is the minimizer of the conditional error. It also shows that the minimizability gap is bounded by when there exists e H whose conditional error e-approximates best-in-class conditional error for all x.
Theorem J.2. The best-in-class ervor is achieved by some ht e H and the minimizability gap is null, M(H) = O, iff there exists h² H such that
E[E(h" (z). x]= [=]= inf E[((a,)) x] a.s. over X.
(14)
aεA
If further a + Ey[e(a, v) x] is injective and onf E, [((,,v)) B, (xx.)) I+) then, the condition equivalent to h² (x) at (x) a.s. for x X. Furthermore, the minimizability gap is bounded by e, M(J() s iff there exists h e H such that
E
(x). x] inf B[E(a, [z] sc
(15)
acd
Proof.
Assume that the best-in-class error achieved by some h²* e eH. Then, we can write inf ([((((=)))))))) E((()) (z), v)]
Ele(h
hest
The expected pointwise infimum can be rewritten as follows:
E
inf E[((h(x).))
E inf E[((a,)) |x]
LhefC
Thus, we have
M(H = E (1))
inf E[((a) ( and
=
In view of that, since, by the definition of infimum, the expressions within the marginal expectations are non-negative, the condition that M(H) = 0 implies that
([ (x). x=] inf B[((a,)) v) [x] a.s. over X.
ae y
On the other hand, if there exists ht H such that the condition (3) holds, then,
M(3() inf ([((h(z).v)) hel
E inf B[l(a,))
E[ ([((h"()).)))) [z] inf Enf(ay
|x]
x Lae
aeA
25

---

Since M(() is non- non-negative, the inequality is achieved. Thus, we have M(H) 0 and inf F[((h(=).))] hede
there exists h" such that the condition (4) holds, then,
M(H) = inf B[e(h(2), v) E inf B[((a, æ] Lad
s E (x), and
inf El
[x] =6.
hel
On the other hand, since we have
M(H) Ele(h" (()(h(()),)) x] inf ([ [2]
M(H) < implies that
E (()(
inf inf E[ y) x] se
add
This completes the proof.
J.3 Examples
Note that when the distribution assumed to be deterministic, the condition (4) and condition (15) are reduced to the condition of Theorem 6.1 in binary classification and that of Theorem J.1 in multi-elass classification, respectively. In the stochastic scenario, the existence of such a hypothesis
not only depends on the complexity of the decision surface, but also depends on the distributional assumption on the conditional distribution p(x) (p(y(z)) yyyy where p(y] x) = D(Y = yy X z) given = x. In the binary classification, we have p(x)
the conditional probability of (p(+1 |2:) (x)) where p(+1 x)) + p(-1 .>) 1. For simplicity, we use the notation r)(x)) and 1 - (xx) to represent p(+1|2) a)) and p xx) respectively.
the multi-class classification with y [1, (1,...,7) n,, have p(x) = (p) ....... p(n()))))) where is the number of classes. As examples, here too, we examine exponential loss and logistic loss in binary classification and multi-class logistic loss in multi-class classification.
A. Example: binary classification. Let e e [0, j.-. We denote by X. the subset of over which (x)) -e and by X_ the subset over which n(()) = 6. Let H be a family of functions h with (+))) & A for all a X and such that all values in [-A, +A] can be reached. Thus, A = [-A, A] for any X. Consider the exponential loss: E(h, x, y) e- Then, for any e X and A. we have
x X, cee c)ea r X_
(1 c)e ao + cea
[[((a,v)
Thus, it is not hard to see that for any es ب the infimum inf Ey[[(a, y) æ] can be achieved
Ir Xc, e A. Similarly, for the logistic loss l(,, y) log( e-ub(x)), we have x Ee
by a (x)
1-A
that
B[((a,y) [)g[c)lo((1 +c clog(1 + Ea) x NE telog(1+e + (1 - e) log(1 + + x TEX.
AA re
and for .... the infimum infae [, u) can be achieved by a' a'(x) (x)))
1-A xe X_
Therefore, by Theorem 6.2, for these distributions and loss functions, when the best-in-class classifier h" c-approximates a4 = A over X,, and a = -A over X.,, then the minimizability gap is bounded the complexity of the decision surface.
by The existence of such hypothesis in H. depends For example, as previously noted, when the decision surface is characterized by a hyperplane, hypothesis set of linear functions, coupled with a sigmoid activation function, can offer highly effective approximation (see Figure I for illustration).
B. Example: multi-class classification. Let [0, 111 We denote by X4 the subset of X over which p(k: æ) 1 and p(j x) n for j k. Let HC be family of functions h with
26

---

11(2,-) s A for all 2 é X' and such that all values in [-A,+ +A] can be reached. Thus, A [], for any x X. Consider the multi-class logistic loss: 2(,, y) log
M(av)
For any
Eysry e
[at ,...,, o". om]e A, denote by Sk Exi(a en Then, for any E X and ar A, B[e(a,)) 2] (1-c)
Σ log(Sk) if Xg. Risk
n
Thus, it is not hard to see that for any 6 5 8-1 2 the infimum an (( y) xr] can be achieved by a" (x) = --A,.... .. A................... -A], where occupies the k-th position for æ Xg. Therefore, by Theorem 6.2, for these distributions and loss functions, when the best-in-class classifier h"
approximates or:: -A,..., A
over Xg, then the minimizability gap is bounded by c.
1-thh
The existence of such a hypothesis in H depends on the complexity of the decision surface.
K Proof for binary margin-based losses (Theorem 4.2)
Theorem 4.2 (Upper and lower bound for binary margin-base based losses). Let H be a complete hypoth- esis set. Assume that 4 is convex, twice continuously differentiable, and satisfies the inequalities ('()) > and 4" *"(0) (0) > 0. Then, the following property holds: J(t) = =@(f); that is, there exist 0, c> 0, and T > such that Ct 2 I(t) ct for all <T
positive constants
Proof. Since & is convex and in C²2, ft is also convex and differentiable with respect to u. For any te [0, differentiate ft with respect to we have
1- (')) 2
1+1 4' ('u-..
fu)
2
Consider the function defined over TR2 by F(I, a) = 2
11(0'()) (a) 1 (= Observe that F(0,0)
7
0 and that the partial derivative F with respect to at (0,0) is T" (0(0) 0:
aF da (1,
1 1-1 क" a + 2
0F
T" (-a);
da (0,0) (0" 00
2
Consequently, by the implicit function theorem, there exists continuously differentiable function such that (tt, a(1)) = in a neighborhood [-c,e] around zero. Thus, by the convexity fa and the definition of F, for i и [0, inf fe(u) is reached by @(t) and we can denote it by at. Then, of is continuously differentiable over [0, c]. The minimizer at satisfies the following equality:
f( 1-t D'(a;)
1+t Φ ('(=)))
(16)
2
Specifically, at / O, we have E' (a())) = ('(ag)) Since + is convex, its derivative क is non- decreasing. Therefore, if aj were non-zero, then Ø' would be constant over the segment [-laš]. [a This would contradict the condition &² > 0, as a constant function cannot have positive second derivative at any point. Thus, we must have aj 0 and since & is non-decreasing and 4²(0) 0.
we have at 0 for all e e), By Theorem 4.1 and Taylor's theorem with an integral remainder, T can be expressed as follows: for any t [0, c].
T(t) = f(( inf fi(u) weR
= f((0) f((a;)
= f((at) att + (((-- ((--)) du
(l((a)) = =0)
-fa (1)) du
S101 a (1-t
1+t x" (-u) (-w)du.
w
"" ("(u)=
(17)
2
27

---

Since of is function of class C², we can differentiate (16) with respect to t. which gives the following equality for any in (0,e):
1 (a;)
1 "" (a;)
dai
1 (1) D3 (-a,)
dag
कb (-aa),
dt (t) = 0.
2 Taking the limit - 0 yields
2
dt 2
2
_ (0)) (0)
1 T"
da (0) (0)
da;
(0(0)
o5 (0)
(0) 0.
2
dl
This implies that
da
40) >0
dt (0) ("(
Since lim;-o ": do;
di (0) (0)) (0) O, we have of (t).
Since (0) > and &" is continuous, there is a non-empty interval [=a,+ over which &" is positive. Since ag 0 and of is continuous, there exists sub-interval [0, <'] S [0,c] over which aj S a. Since s" is continuous, it admits a minimum and a maximum over any compact set and we can define minuel-a,al ("(u) and C' maxuel-a.a] ("(u). and C are both positive since we have (0) > O. Thus, for t in [0,c'], by (17), the following inequality holds:
C (a;) 2 J. dC 2 I(t)) J."
1 8" (-u) du 2 Soa uC uC (at)² 1-t o" (((w)=
2
2
2
This implies that J(t)= = O(1²)
L Proof for comp-sum losses (Theorem 5.3)
Theorem 5.3 (Upper and lower bound for comp-sum losses). Assume that & is convex, nvice continuously differentiable, and satisfies the properties ('(u) < 0 and v"(u) O for any u e (0, 21 Then, the following property holds: T(t) (tt))
Proof. For any E [ 1 define the function J by
4E [0, (t(() sup ((7) 1-t t 14|57
Φ u)
1+t
Φ m)
(0, - inf (e,r(u), Ju|sr
where
(u) = --' ΦD (u) + 1+t
Φ (-u) and 1,(u) = 4(T uu)
2
2
We aim to establish lower bound for inf 7e T+((). For any fixed E [ 2]. this situation parallel that of binary classification (Theorem 4.1 and Theorem 4.2), since we have ( ('(r) < 0 and (0) (²(r) O. Let oj.r denotes the minimizer of für over R. By applying Theorem 5.2 to the function F: (f, + ff.
3 (u((() 1t 2 (-u) and the convexity of 2
ftr with respect to oj,r exists, is unique and is continuously differentiable over [0, [0,4] x [ J]. for some 1 > O. Moreover, by using the fact that fa.- (r) O and Só,, (-T) < O, and the convexity of forr with respect to u, have | S T, VT 1 }. By the continuity of of we have |ai, S over [0, to] [ ]. for some to 0 and to $ tg.
Next, we will leverage the proof of Theorem 4.2. Adopting a similar notation, while incorporating the 7 subscript to distinguish different functions + and ft,,, we can write
1-th T" (-w)
1+t
V E [0,ta],
J+(1)=
x du.
2
where ai,r verifies
Da
(0(
-b.- 0 and
(0)
= Cy 0.
(18)
dt
(0)
28

---

We first show the lower bound inf re - = Qtt).. Given the equalities (18), it follows that for any T, the following holds: lime-o (onp--o((aa,,)) (a + c,t) 0. For any т [ 2 t (- + +c,t) is continuous function over [0, to] since at, is function of class C Since the infimum over fixed compact set of a family of continuous functions is continuous, ( ++ inf [- + c70) is continuous. Thus, for any O, there exists 4 O, L1 S to. such that for any E [0,4]]
inf ( crt) sc. ree 22
which implies
VT = 2 oir 2 -c- - 6 ct-
where e inf [e[ Since (0) and (0) are positive and continuous functions of this infimum is attained over the compact set [ 1 leading to 0. Since the lower bound holds uniformly over т, this shows that for t E [1, we have 7e - 12(t).
Now, since for any T [ 2 - is a function of class C and thus continuous, its supremum
over compact set, sup,e # -i. is also continuous and is bounded over [0, f1, by some a > 0. For |u| & and 7 [ 11 we have _ a S T + S 2 + and _ a S t S 1/2 a. Since 4" is positive and continuous, it reaches its minimum C > over the compact set [ a, a]. Thus, can write
2
1 6"
1+(
V [0,t]. VT
2
J+(t)=
(-u)
40 (u) du
2
[ - | C+
1 C
u
du
2
iis
(-ai,7)
Cu C
2
Thus, for S l1, we have
(inf (infre 1. - 1((t)).
inf (t) 2 C [..1
2
Similarly, we aim establish upper bound for inf, [ J+(). We first show the upper bound supre[ - = O(t). Given the equalities (18), it follows that for any т, the following holds: lim;-o( (-a + c+t)= O. For any T e [1> 2).+t t (-ai,r + c+t) is a continuous function over [0,to] since of, is a function of class C Since the supremum over fixed compact set of family of continuous functions is continuous, + []] + c,t) is continuous. Thus, for any
there exists & > O, t S to. such that for any tE [0,t,].
{ + crlf Se,
sup ref 2
which implies
Vr E
s cs ct
2
where e suPre[2. Since ('((0) and (0()) are positive and continuous functions of r, this
supremum is attained over the compact set [1 1], leading to > 0. Since the upper bound holds uniformly over t, this shows that for t E [0, t1], we have s + -7,, = O(t).
Now, since for any [ 1. -aïr is function of class C and thus continuous, its supremum over compact set, sup, 2] -i. is also continuous and is bounded over [0, (t by some 0.
For |u] S and [ ]. we have 1 a T 1 and 1 aas s 1 Since 4" is
29

---

positive and continuous, it reaches its maximum C > 0 over the compact set [ - a, 1 + aa. Thus, we can write
e [0,t]] V
- 2
I+(t)= = f
U
+ (-u)
1
("()) du
2
2
1 - t
1 t
u
C+
C
du
2
Cudu = C )²
(-a
2
Thus, for s h,, have
(sup [ () -
inf (1(()= s C re +
S (19)
2
This completes the proof.
M Proof for constrained losses (Theorem 5.5)
Theorem 5.5 (Upper and lower bound for constrained losses), Assume that & is convex, twice continuously differentialle, and satisfies the properties v'(u) 0 and v"(u) for any u 2 0. Then, for any 0, the following property holds:
Supf0( (T)
1+ 2 ( u) =(F=-))==0() = 1-t 2 + u)
inf sup re[O.A] ueR
2
2
Proof. For any e [0, A]. define the function J, by
Vt [0. 1]. J+(t)= sup (() 1- weR
σ u)
1+t
Φ(T u)
2
2
(0,
inf (t) weR
where
ft.(u)= - 1-1 (u) + 1 Φ (-u) and (- :(T + uu). 2
2
We aim to establish lower bound for inf A] J (1). For any fixed [0, A], this situation parallel to that of binary classification (Theorem 4.1 and Theorem 4.2), since we also have (0) 4'(T) 0 and 40 4" 0. Let ai, denotes the minimizer of fú, over R. By applying Theorem 5.2 the function
(u) 1 (u) 1 (-u) and the convexity of fer with respect u. ai,r exists, is unique and is continuously differentiable over [0,4)] AJ. for some 4n
Next, we will leverage the proof of Theorem 4.2. Adopting a similar notation, while incorporating the 7 subscript to distinguish different functions 4 and fe,r, write
[1 t Φ (u)
1+ (-() du.
Vt E [0,
T+(t)=
u
where ai,, verifies
cor =0 0 and Dai,
20(
(0)
(7 = G > 0.
(19)
0t
We first show the lower bound inf [A. ai = (1). Given the equalities (19), it follows that for any the following holds: lim c,t) O. For any A], t + (ai,r c,t) is continuous function over [0, to] since at a function of class C²., Since the infimum over fixed compact set of family of continuous functions continuous, ++ infrejo.A11 af c-1} is continuous. Thus, for any > O, there exists t > 0, t S to. such that for any E [1,
inf (aï,r a se, [e[[o.A]
30

---

which implies
VT E [0, oir 2cttcctt
where e re[0AA] Cr. Since $ (0) and (0) are positive and continuous functions of т, this infimum is attained over the compact set [0. A], leading to c 0. Since the lower bound holds uniformly over T, this shows that for t [0, t1], we have [] oi, 22().
Now, since for any т E [0, A], oirr is a function of class C' and thus continuous, its supremum over compact set, [1 oi,r, is also continuous and is bounded over [0, &1] by some > 0. For lu| and [0, AJ. we have A-a s u 2 A and A S T A + a. Since &" is positive and continuous, it reaches its minimum 0 over the compact set [A - a, A + a]. Thus, we can
write
(
1 2
1+1
Vt [0,t]], [0, A]. [+(()=
(u)
"" (-u) du
2
[-t C+
1+t
C
du
Lo oir Cudu C
(qi,r)
2
Thus, for s (1, we have
inf T+(() C (infre(o.A) ai )² re(0.4]
2 2(12).
Similarly, we aim to establish an upper bound for inf =] [T).). We first show the upper bound A] 07 O()). Given the equalities (19), it follows that for any the following holds: oo (oir c) O. For any E [0, A]. L + (ai,, - c7l) is continuous function over [0, 4o] since or,r is a function of class C Since the supremum over a fixed compact set of family of continuous functions is continuous, + supre(o,.a] (ai, ( - ctt} is continuous. Thus, for any 0, there exists & > 0, 4 & to. such that for any E [0,
{ai,r c,t) se,
sup rE(0,A]
which implies
V [0, oir5 S S
where e = supre[o.A] c.. Since (0) and (0) are positive and continuous functions of r, this supremum is attained over the compact set [0, A]. leading to e > 0. Since the upper bound holds uniformly over 7, this shows that for / [1, we have s(Pre[ ai,- O(1).
Now, since for any 7 [0, AJ, aj,r a function of class C² and thus continuous, its supremum over compact set, sup)<[o.A]] a.,,, is also continuous and bounded over [0,t1] by some > 0. For lu] s a and 7 E [0. A]. we have A a + S A + and A-a 7 u A+ a. Since &" is positive and continuous, it reaches its maximum C' > 0 over the compact set [A A + a]. Thus, we can write
1 [0.4), Vr [0, A], Jz(()= = (orr "
1+1
(u)
+
Φ" du
2
2
1
1-t
1+t
C+
du
0
2
Cudu C (
2
Thus, for t 5 tt, we have
inf J,(t) s (SUPre(o.A) or
$ 0((P).
<<(0,A]
2
This completes the proof.
31

---

N Analysis of the function of T
Let F be the function defined by
1-t ((r u) Φ(r -))
1+t
e [0, 2 TE R. T(t,T)
sup ((T) uei
where + is convex function in C² with Φ', Φ" 0. In light of the analysis of the previous sections, for any (T,1), there exists a unique function de,r solution of the maximization (supremum in F), C function over neighborhood U of (r, 0) with ag.r 0, 0t, 0 for 0, and Bal (0,T)= ('r)) ("()) C,. Thus, we have lim4-0
Aiz = 1. The optimality of at, implies tcr
1-t 4'(T ac,))
1 + ar,))
2
Thus, the partial derivative of over the appropriate neighborhood U is given by
OF Or (t,T)=
1-t 4 (T a
dou.
1+t 2'(r ae.r) das, Ør
(-or (t,
(t, +
Ør
2
=T((T) 1- 1 T ( (T+ + a,, ))
dorr (1,
dau, Ør (1, ++1
Ør
= (T( - (1- t) ( a.,r)
Since &' is continuous, by the mean value theorem, there exists & & (T, ac,)) such that 4'(r + at,7) 2 (T) o 4" )()) Thus, we can write
OF
θr (t, r) = 1 ('()) - -1-1) (1-t) (1 t)
= (T) (1 (1+))),,)((44))
4" (E)
= = 1 (1 t) to, D" (T)
Note that if 4" is locally non-increasing then we have x" (E) s ("(E)
("(7) and for f sufficiently small,
since Ø' is increasing and St. 1: Ir,
OF (1, (1.7)
Ut.5 0.
(20)
tc,
In that case, for any A> 0, we can find a neighborhood O of t around zero over which OF defined for all (t, 7) e [0, A] and (f(t, 2 O. From this, we can conelude that the infimum of F over E [0, A] is reached zero for t sufficiently small O).
Br (f, r) is
O Generalization bounds
Let S= = ((#1: y1)...., (Im, ym be sample drawn from D Denote by hi an empirical minimizer within H. for the surrogate loss E: Tig E argmin 1. Σm {(h, xi, 9:). Let H, denote the hypothesis
set (xx, w) + E(h, v. E HG and Ry (H) its Rademacher complexity. We also write B, to denote an upper bound for f. Then, given the following H-consistency bound:
vh E H, Eio (h) E7 (H) + Mc, (3) s r(εx(h) 87 (H() + Mc(H)))
(21)
for any 5 > 0, with probability at least 1 - 5 over the draw of an i.i.d. sample S of size m, the following estimation bound holds for hg:
wh E H, Eto (h: Eto., (H) & ST (H)) (Hf) 2BL
log
M.(33)
-Mo (H).
2m
Proof. By the standard Rademacher complexity bounds [Mohri et al., 2018], for any > 0, with probability at least 1 6, the following holds for all h H:
(e<(h) - Ex,,((h) 2 (3() + B.y
log log(2/8) (2/8)
32

---

For any <> 0, by definition of the infimum, there exists h 6 36 such that Ex(h²) (7()) + c. By
the definition of hig we obtain
Ee(hs) - =2()) = E((hs) (hs) + Eg,s (J)
(hss (r,s (, (7(
s ((())) Er,s (his) + Ee,s(h" (h²) +
2 2 (9C) Br log(2/6)
2m
Since the inequality holds for all e > 0, it implies the following:
Ee E, (3() 2 4 (3C) 2BrV
log (2/6))
Plugging in this inequality in the HCcoosissenccy bound (21) completes the proof.
These bounds for surrogate loss minimizers, expressed terms of minimizability gaps, offer more detailed and informative insights compared to existing bounds based solely on approximation errors. Our analysis of growth rates suggests that for commonly used smooth loss functions, varies near zero with square-root dependency. Furthermore, this dependency cannot be generally improved for arbitrary distributions.
Future work
We demonstrated universal square-root growth rate for smooth surrogate losses commonly used in binary and multi-class classification. This result holds across all data distributions. A promising direction for future research would be further investigate how incorporating specific distributional assumptions could refine these results.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the section "Our results" in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix P.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
34

---

Justification:
See Section 3, Section 4, Section 5, Section 6, and Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
35

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. wttpccccpppccccceecocc.cccccccct ptpppppgguides...p.pppppppppaaee /Codeeeooiisseeeeeee
gutie//eeiceeeooeeuuuiiiiiiiiiii wetiuummmssiioooee ssisnnolloooo onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
36

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / http///eerip...// wwwtrrps.ccppuuuue
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is theoretical in nature and we do not anticipate any immediate negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
37

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "FR6Am5oQfo", "reviewer": "Reviewer_ZEpV", "summary": "The paper provides an analysis of the growth rate of H-consistency bound for surrogate losses in binary and multi-class classification. The authors prove square root growth rate near zero for smooth margin-based surrogate losses for binary classification as well as  for smooth comp-sum and constrained losses for multiclass classification. Since minimizability gaps makes a big difference between the bounds of different surrogates, the authors also analyze these gaps to guide in selecting better surrogates.  In section , the authors introduce H consistency bounds and they build upon this to derive results for binary and multi-class classification in later sections.", "questions": "See above.", "limitations": "See above.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I must say, I am not an expert in this area of research. I find this paper pretty well written. In theorem 4.2, the authors prove that the transformation function tau is precisely of the order t^2 for a class of margin based loss function that is smooth and follows some other properties as mentioned in the main statement.  Hence, the growth rate for these loss functions is precisely square-root.  Further, the authors derive similar result for multiclass classification for comp sum losses and constrained losses. Because there is a minimizability gap term in the H consistency bound hence even with identical growth rates, surrogate losses can vary in their H-consistency bounds. The authors show that in the case of multiclass classification, minimizability gap scales with number of classes.", "weaknesses": "I have a few very basic questions, regarding the work.\n1. I understand that H consistency-based bound helps convert a surrogate-based bound to a bound that we require. How is it an improvement over earlier work Bartlett et al. (Convexity, Classification, and Risk Bounds). H consistence based bound contains the term minimizability gap which was not existent in the previous work that I cited. \n\n\n2. I also understand that the faster the bound for surrogate loss will be, the better bound for the actual loss could be obtained. However, I am wondering if we provide a fast rate using small ball method or local Rademacher complexity based method for the surrogates, under what conditions the fast rate for the actual loss can still be recovered or is it lost always ?\n\nIt would be also great if you could explain simply the implications of getting a precise rate for the transformation function as I understand it might not give you a lower bound on the estimation error because of equation 2 is not an eqaulity. Am I missing something?\n\nI am currently giving it a borderline accept and am happy to reconsider it after the rebuttal.", "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 detailed responses below and let us know if there is any other question.\n\n**1. I understand that H consistency-based bound helps convert a surrogate-based bound to a bound that we require. How is it an improvement over earlier work Bartlett et al. (Convexity, Classification, and Risk Bounds). H consistency based bound contains the term minimizability gap which was not existent in the previous work that I cited.**\n\n**Response:** The results of Bartlett et al. (2006) hold only for the family of all measurable cases, that is for $H = H_{\\mathrm{all}}$. They also focus exclusively on binary classification (other studies, such as those of Tewari and Bartlett (2007) and Zhang (2004) analyze certain multi-class classification loss functions).\n\nIn contrast, $H$-consistency bounds hold for arbitrary hypothesis sets. They provide the tightest possible upper bound on the estimation error for the actual loss, such as the zero-one loss, in terms of the surrogate estimation error, for an arbitrary hypothesis set $H$. They admit as special cases the excess bounds of Bartlett et al. (2006) in binary classification, when setting $H$ to $H_{\\mathrm{all}}$.\n\nFor the more realistic scenario where the hypothesis set $H$ does not include all measurable functions, as demonstrated in Appendix C, under general assumptions, minimizability gap terms appear. These are necessary terms to relate the surrogate estimation error to the actual estimation error. In the special case $H = H_{\\mathrm{all}}$, minimizability gaps vanish. They are also zero in realizable cases.\n\nThus, $H$-consistency bounds provide a strict generalization of previous work, needed to analyze the standard case where $H$ does not include all measurable functions. Our paper further provides a detailed analysis of minimizability gaps.\n\n**2. I also understand that the faster the bound for surrogate loss will be, the better bound for the actual loss could be obtained. However, I am wondering if we provide a fast rate using small ball method or local Rademacher complexity based method for the surrogates, under what conditions the fast rate for the actual loss can still be recovered or is it lost always?**\n\n**Response:** This is a very good question. It is well-established that local Rademacher complexity or small ball methods can be used to derive fast rate generalization bounds under Tsybakov noise conditions. Remarkably, under the same conditions, indeed, one can also derive more favorable $H$-consistency bounds (as shown in our concurrent work), that is with better exponents. Combining both yields more favorable generalization bounds on the actual loss, as suspected by the Reviewer. We will elaborate on this in the final version.\n\nMore generally, more favorable $H$-consistency bounds can be derived under various distributional assumptions.\n\n**3. It would be also great if you could explain simply the implications of getting a precise rate for the transformation function as I understand it might not give you a lower bound on the estimation error because of equation 2 is not an equality. Am I missing something?**\n\n**Response:** Like excess error bounds, $H$-consistency bounds are worst-case bounds that hold for any distribution. As noted in Lines 232-235, estimation error transformation functions provide tight $H$-consistency bounds. This means that for any $t \\in [0, 1]$, there exists a hypothesis $h \\in H$ and a distribution such that the inequality of the bound can be achieved. Thus, a square root growth rate for transformation functions implies a square root growth rate of estimation errors in the worst case.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2yjn2yVo7s", "reviewer": "Reviewer_cQ3k", "summary": "This paper presents a comprehensive analysis of the growth rate of H-consistency bounds (and excess error bounds) for various\nsurrogate losses for some intractable loss used in classification. The authors prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification and comp-sum and constrained loss used in multi-class classification, providing both upper and lower bounds under mild assumptions.", "questions": "1. The error bounds are local bounds. Can the author provide insights on how to have global bounds and the neighborhood for the local bounds to hold?\n 2. Can the authors provide more insights on how these bounds help us select surrogate functions?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides solid analysis for the H-consistency and excess error bound and these provide good guidance for selecting good surrogate loss for classification tasks where the target loss is hard to optimize.\nThe theoretical analysis is novel and provides good insight for handling intractable target loss.", "weaknesses": "The paper should provide a more intuitive statement on the motivation and implication of these error bounds and provide more insights about the proof.", "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 and for your suggestions to improve its readability. Please find our detailed responses below.\n\n**Weaknesses: The paper should provide a more intuitive statement on the motivation and implication of these error bounds and provide more insights about the proof.**\n\n**Response:** Thank you for your suggestions. We will continue to work on improving our presentation for readers. The addition of one extra page in the final version will also allow us to include more detailed discussions of the motivation, implications, and proof techniques in the main body.\n\n**Questions:**\n\n**1. The error bounds are local bounds. Can the author provide insights on how to have global bounds and the neighborhood for the local bounds to hold?**\n\n**Response:** $H$-consistency bounds hold for all predictors $h$ in the hypothesis set $H$ considered and for all distributions. We provide a tight analysis of their growth rate for smooth surrogate losses in both binary and multi-class classification, demonstrating that it follows a square-root function.\n\nWe suspect the reviewer refers to these square-root growth rate bounds as \"local bounds\" and is inquiring about \"global bounds\" that do not rely on growth rates. Previous works by Awasthi et al. (2022a,b) and Mao et al. (2023b,e) offer precise global bounds for both binary and multi-class classification across various commonly used loss functions, along with general methods for deriving such bounds. Our paper focuses on analyzing the growth rate of any of these bounds for smooth loss functions.\n\nPlease let us know if we are not answering the question appropriately, as we are unsure about what meant. Thank you.\n\n**2. Can the authors provide more insights on how these bounds help us select surrogate functions?**\n\n**Response:** Our theoretical analysis assists in selecting surrogate loss functions by considering several factors related to their $H$-consistency bounds:\n\n- Their growth rate. For example, the growth rate for polyhedral surrogate losses is linear, while it is square-root for smooth losses.\n\n- Their optimization property. For example, smooth losses are more favorable for optimization compared to polyhedral losses, particularly with deep neural networks.\n\n- Their functional form. For example, comp-sum loss functions can vary in their forms of $H$-consistency bounds due to the dependency on the number of classes (see Section 6).\n\n- Their approximation property. For example, the minimizability gaps differ in $H$-consistency bounds for smooth surrogate losses, even with the same growth rate (see comparison in Section 6). Also, under certain conditions, minimizability gaps can be zero or close to zero.\n\nFor smooth loss functions, in particular comp-sum losses, please see further our discussion in Section 6.2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3hMoXYVnTe", "reviewer": "Reviewer_s9tD", "summary": "Since optimizing zero-one loss is intractable and it does not have properties such as differentiability, a common approach in learning theory is to replace it with a surrogate loss function. H-consistency bounds relate the excess error for surrogate loss to zero-one loss. This paper establishes a square-root growth rate near zero for smooth surrogate losses in binary and multi-class classification, providing both upper and lower bounds under mild assumptions.", "questions": "The results are based on the assumption that the hypothesis class is complete. Can you explain why this condition is necessary and what happens to the growth rate when this is not satisfied? It seems that many practical hypothesis classes don't meet this condition.", "limitations": "The paper does not have any potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proves both upper and lower bounds for H-consistency with smooth surrogate losses. Previous results only provided lower bounds, but this paper presents lower bounds with fewer conditions and also shows a matching upper bound of the square root, applicable to both binary classification and multiclass classification, such as Comp-sum losses.", "weaknesses": "The paper studies only smooth surrogate losses, not piecewise linear ones such as hinge loss. However, using smooth surrogate loss functions is very common in machine learning applications.", "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. Please find our detailed responses below.\n\n**Weaknesses: The paper studies only smooth surrogate losses, not piecewise linear ones such as hinge loss. However, using smooth surrogate loss functions is very common in machine learning applications.**\n\n**Response:** Indeed, smooth surrogate loss functions are the most commonly used ones in current training of neural networks. Our focus on smooth surrogate loss functions was also motivated by the fact that the prior work of Frongillo and Waggoner (2021) implies a linear growth rate for polyhedral losses. In Appendix G, we give a brief discussion comparing polyhedral losses with smooth losses.\n\n**Questions: The results are based on the assumption that the hypothesis class is complete. Can you explain why this condition is necessary and what happens to the growth rate when this is not satisfied? It seems that many practical hypothesis classes don't meet this condition.**\n\n**Response:** Completeness means that for any instance, the set of possible scores generated by a hypothesis set spans $\\mathbb{R}$. This condition is met by common hypothesis sets, for instance the family of all linear models, $H_{\\mathrm{lin}} = \\\\{ (x,y) \\mapsto W_{y} x + b_{y} \\\\}$, or that of multi-layer neural networks, $H_{\\mathrm{NN}} = \\\\{ (x, y)\\mapsto u_y \\cdot \\rho_{n}(W_{y, n}(\\cdots \\rho_2(W_{y, 2} \\rho_1(W_{y, 1} x + b_{y, 1})+b_{y, 2})\\cdots)+b_{y, n}) \\\\}$, where $\\rho_j$ is an activation function.\n\nMore broadly, our analysis and results can be extended to bounded hypothesis sets even when completeness is not satisfied. This can be done by leveraging the characterization of the error transformation function given by Awasthi et al. [2022b] and Mao et al. [2023b] without assuming completeness.\n\nWe expect that the square root growth rate still holds in bounded cases for smooth surrogate losses. This is because, for bounded hypothesis sets, the estimation error transformation function typically admits two segments; however, our primary focus is on the segment where $t$ is close to zero, which aligns with the complete case. Thus, a similar analysis can be applied in these situations as well. We will elaborate on this in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HCIJacEegF", "reviewer": "Reviewer_jALT", "summary": "This paper analyzes the growth rate of the H-consistency bounds (which subsume excess risk bounds) for various smooth surrogate losses commonly used in binary and multiclass classification. Specifically, for binary classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for margin-based surrogate losses. For multiclass classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for two families of surrogate losses: comp-sum and constrained losses. Finally, the work also studies how the number of classes affects these bounds, as well as the minimizability gaps in the bounds.", "questions": "1. Based on this work, do you have any concrete suggestions for practitioners to choose surrogate losses (assuming they do not know about H-consistency at all)?", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Originality**\n\nA comprehensive analysis of the growth rate of the H-consistency bounds (which subsume excess risk bounds) for various smooth surrogate losses commonly used in binary and multiclass classification:\n-  For binary classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for margin-based surrogate losses (Theorem 4.2). In particular, the lower bound requires weaker conditions than [Frongillo and Waggoner, 2021,\nTheorem 4], and the upper bound is new.\n- For multiclass classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for two families of surrogate losses: comp-sum and constrained losses (Theorems 5.3 and 5.5).\n\nRelated work has been properly cited.\n\n**Quality**\n\nThe work is technically sound. Proofs are given for theoretical results.\n\n**Clarity**\n\nThe paper is clearly written and well-organized. Although it is a bit dry, as a researcher working in the related field, I did not find it very hard to read.\n\n**Significance**\n\nThe comprehensive analysis presented in this work promotes a deeper understanding of different surrogate losses. It is helpful for researchers studying surrogate losses and consistency.", "weaknesses": "I did not find any obvious 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. Please find our detailed responses below.\n\n**Questions: Based on this work, do you have any concrete suggestions for practitioners to choose surrogate losses (assuming they do not know about H-consistency at all)?**\n\n**Response:** We have discussed some practical implications of our analysis in Section 6 and Appendix H.\n\nIn practice, in realizable or nearly realizable cases where minimizability gaps are zero or relatively small, we believe that the logistic loss is a favorable choice because it is advantageous for optimization and its bound is independent of the number of classes. This in fact can partly explain its widespread practical application.\n\nIn other scenarios, both the number of classes and the minimizability gaps are essential in loss selection and a good choice out of the family of comp-sum losses might suggest a parameter $\\tau$ closer to 2.\n\nMore generally, our theoretical analysis can help in selecting surrogate loss functions by considering several factors related to their $H$-consistency bounds:\n- Their growth rate. For example, the growth rate for polyhedral surrogate losses is linear, while it is square-root for smooth losses.\n- Their optimization property. For example, smooth losses are more favorable for optimization compared to polyhedral losses, particularly with deep neural networks.\n- Their functional form. For example, comp-sum loss functions can vary in their forms of $H$-consistency bounds due to the dependency on the number of classes (see Section 6).\n- Their approximation property. For example, the minimizability gaps differ in $H$-consistency bounds for smooth surrogate losses, even with the same growth rate (see comparison in Section 6). Also, under certain conditions, minimizability gaps can be zero or close to zero.\n\nFor smooth loss functions, in particular comp-sum losses, please see further our discussion in Section 6.2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper further develops the theory of H-consistency, which relates the effect of minimizing a surrogate loss
over a hypothesis set H to the zero-one loss. In particular, one contribution of this work is to prove relatively general
results to determine the rate in the case of smooth loss functions. This paper builds upon the discoveries of previous works, 
but all of the reviewers appreciated the current contribution at a technical level and discussion of the position of this work to previous work. I recommend acceptance but encourage the authors to revise the final version of the work based on these discussions.
Decision: Accept (poster)