Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: ICML 2025 poster (2025)
Keywords: learning theory
consistency
generalized metrics
Primary area: general_machine_learning->supervised_learning

Abstract: In applications with significant class imbalance or asymmetric costs, metrics such as the $F_\beta$-measure, AM measure, Jaccard similarity coefficient, and weighted accuracy offer more suitable evaluation criteria than standard binary classification loss. However, optimizing these metrics present significant computational and statistical challenges. Existing approaches often rely on the characterization of the Bayes-optimal classifier, and use threshold-based methods that first estimate class probabilities and then seek an optimal threshold. This leads to algorithms that are not tailored to restricted hypothesis sets and lack finite-sample performance guarantees. In this work, we introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds. Our approach reformulates metric optimization as a generalized cost-sensitive learning problem, enabling the design of novel surrogate loss functions with provable $H$-consistency guarantees. Leveraging this framework, we develop new algorithms, METRO (*Metric Optimization*), with strong theoretical performance guarantees. We report the results of experiments demonstrating the effectiveness of our methods compared to prior baselines.

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Anqi Mao Mehryar Mohri 21 Yutao Zhong?
Abstract
coefficient (Sokolova & Lapalme, 2009), the weighted accuracy preferred over the standard zero-one misclas- sification loss. These metrics are particularly relevant in scenarios with significant class imbalance, such as fraud de- tection, medical diagmosis, and information retrieval (Lewis, 1995b; Drummond & Holte, 2005; He & Garcia, 2009; Gu et al., 2009), in settings where classification costs are asymmetrical. However, optimizing these alternative met- rics presents both computational and statistical challenges, as they deviate from the standard single-loss expectation framework commonly used surrogate loss function analy- sis (Steinwart, 2007).
In applications with significant class imbalance or asymmetric costs, metrics such as the Fg- measure, AM measure, Jaccard similarity coeffi- cient, and weighted accuracy offer more suitable evaluation criteria than standard binary classifi- cation loss. However, optimizing these metrics present significant computational and statistical challenges. Existing approaches often rely on the characterization of the Bayes-optimal classi- fier, and use threshold-based methods that first estimate class probabilities and then seek op- timal threshold. This leads to algorithms that are not tailored to restricted hypothesis sets and lack finite-sample performance guarantees. In this work, we introduce principled algorithms for optimizing generalized metrics, supported by H-consistency and finite-sample generalization bounds. Our approach reformulates metric opti- mization generalized cost-sensitive learning problem, enabling the design of novel surrogate loss functions with provable H--consistency guar- antees. Leveraging this framework, we develop new algorithms, METRO (Metric Optimization), with strong thcoretical performance guarantees. We report the results of experiments demonstrat- ing the effectiveness of our methods compared to prior baselines.
Research on the design of algorithms for specific instances of such metrics or the general family has largely focused on the characterization of the Bayes-optimat classifier. For the standard zero-one binary classification loss, it is known that the Bayes classifier can be defined as x + sign (1())) (()z)=+ }). where (xx) is the probability of a positive label conditioned on X. A similar characterization applics to the weighted zero-one loss (Scott, 2012), where the threshold corresponds to a weight different from J. For imbalanced metrics, Ye et al. (2012) characterized the Bayes- class--clasiffir for the Fi- measure, while Menon et al. (2013) characterized the Bayes classifier for the AM measure as x + (ign()(x==68)) for some 8" (0, 1). These results were later generalized by Koyejo et al. (2014) to a broader family of metrics that can be formulated as ratio of two linear functions of true positive (TP), false positive (FP), true negative (TN), and false negative (FN) statistics. This family of Innar-frractonall metrics includes the aforementioned weighted accuracy, F'g- measures, the AM measure, as well as the Jaccard similarity coefficient (Sokolova & Lapalme, 2009), among others.
1. Introduction
In many applications. performance metrics such as the Fg- measure (Lewis, 1995a; Jansche, 2005; Ye et al., 2012), the AM measure (Menon al., 2013), the Jaccard similarity
Existing algorithms for optimizing these metrics heavily rely on the structure of the Bayes-optimal solution (Koyejo et al., 2014: Parambath et al., 2014). These methods generally adopt two-stage approach: first estimating the conditional probability 7/x)) and then searching for suitable threshold 8 specific to the metric.
CCourant Institute of Mathematical Sciences, New York. NY; Goooge Research, New York, NY. Corre- spondence to: Angi Mao giamao@cims.nyu.edee Mehryar Mohri <mohri@ goohi@@ooogl..omm Yutao Zhong <yu- taozhong @ gom....com>>.
These algorithms naturally come with consistency guar- antees (Koyejo et al., 2014). However, consistency is an asymptotic property and does not provide explicit conver- gence rate guarantees. Moreover, it applies only to the
Proceedings of the r2nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
overly broad class of all measurable functions, making it less relevant in practical scenarios where learning is con- strained to restricted hypothesis class (Long& & Servedio, 2013; Zhang& & Agarwal, 2020).
(Section 4.2). We further establish strong H H-consisteney guarantees for these surrogate losses (Section 4.3). In Sec- tion 5, we leverage these theoretical insights to design new algorithms for optimizing generalized metrics, METRO (Mer- ric Optimization), for which we prove strong performance guarantees. Finally, we present experimental results in Sec- tion 6, demonstrating the effectiveness of our algorithms in comparison to prior basclines.
Beyond these theoretical limitations, a key drawback of prior work is its reliance on the structure of the Bayes- optimal classifier, which may differ significantly from the best predictor within given hypothesis class, For exam- ple, we show that in a wwo-dimensional setting with linear classifiers (see Section 5, Figure I), the best linear classifier derived via margin-maximize maximizing classifier can have a sig- nificantly different orientation from the best linear classifier optimized for an -aamuuuree.
2. Preliminaries
Binary classification. We consider the familiar setting of binary classification, where the input space is denoted by X, the label space by y = [+1,-1}, and the data is distributed according to an unknown distribution D over Xx y. We will consider prediction functions h mapping from X R and will denote by Han the family of all measurable functions of this type. For a given loss function & mapping from Han x X x y to I. the expected loss of a hypothesis h and the best-in-class expected loss of a hypothesis set H. g Hall are defined by (x( = B(a [(,, [ infnezt (h). The excess error of hypothesis h, (h) Ez (Hal), can be decomposed as the sum of its estimation error, (b) - E3 (H), and the approximation error of K, Ex (3t) - E7 (Han)). Given sample S = (Z1:..., Tm) and hypothesis h, the empirical error is defined by (h)) m Σ. (h,,,,
Contributions. In contrast to previous work, we introduce hypothesis set-specific analysis grounded in recent advances in C-cossiistey bounds (Awasthi, Mao, Mohri, and Zhong, 2022a;b; Mao, Mohri, and Zhong, 2023f; 2024i). Unlike Bayes-consistency, these bounds are non-asymptotic and explicitly account for the hypothesis set H used in practice. They provide direct upper bounds on the target estimation error in terms of the surrogate estimation error, making them more relevant to practical learning. We leverage this framework to develop new algorithms with strong theoreti- cal guarantees, including finite-sample learning bounds.
x, y)] and E (3) =
Related work. A comprehensive discussion on consistency and generalized metrics in binary classification is provided in Appendix A. Here, we briefly summarize the most rele- vant prior work. Koyejo et al. (2014) studied broad family of performance metrics, including the Fa-measure, AM measure, Jaccard similarity coefficient, and weighted ac- curacy. They proposed two-stage thresholding algorithms that first train a binary classifier (e.g., logistic regression) to estimate 7=x) and then optimize a threshold 0 to maxi- mize the empirical metric of interest. Their approach comes with a consistency-type guarantee but lacks finite-sample guarantees. Parambath al. (2014) focused specifically on optimizing the Fi-measure. Their algorithm is similar to the second approach in Koyejo et al. (2014) but addi- tionally considers an extra threshold 8", both of which are optimized to maximize the empirical metric. They provide stability-type guarantees, though their analysis lacks explicit details.
Consistency guarantees. Given a surrogate loss function E and a target loss function lg, a fundamental property of l with respect to E2 is Bayes-consistency (Zhang, 2004; Bartlett et al., 2006; Steinwart, 2007).
Definition 2.1 Conyes-Conissteny). A loss function E is Bayes-consistent with respect to a loss function &g if, for all distributions and sequences } [Ee, (h,,) E7, (Hau)] tends zero when n tends to +00, then [&,, (h..) - E7, (Han)) also tends to zero
Han, if
While Bayes consistency is a natural and desirable property, it is inherently asymptotic and applies only to the family of all measurable functions. As such, it offers no insights into convergence rates or the behavior of learning algorithms when restricted hypothesis classes are used, as is typical in machine learning applications. In this context, a more informative property is an H-consistency bound (Awasthi, Mao, Mohri, and Zhong, 2022a; Mao, Mohri, and Zhong, 2023f; Zhong, 2025), which provides a quantitative guaran- tee tailored to specific hypothesis classes.
Structure of the paper. We introduce principled algo- rithms for optimizing broad family of generalized met- rics, supported by K-consistency bounds and finite-sample generalization bounds. We first present an equivalent refor- mulation of the problem of minimizing generalized metrics (Section 3). This reformulation allows us to interpret the problem as minimizing generalized cost-sensitive target loss function (Section 4.1.. We then address this broader cost-sensitive learning problem by introducing a new fam- ily of surrogate loss functions tailored to this framework
Definition 2.2 (JC- CCC-Consistency bound). A surrogate loss L admits an H- H-consistency bound with respect to the target loss &g if there exists a non non-decreasing concave function T: PR, R. with (())= = 0 such that, for all h e K and all
2

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
distributions, the following inequality holds:
covers several widely used metrics, including the AM mea- sure (Menon et al., 2013), the Fa-measure (Ye et al., 2012), the Jaccard similarity coefficient (JAC) (Sokolova & La- palme, 2009), Weighted Accuracy (WA), and many others of interest. Given a hypothesis set H, our goal is to find a hy- pothesis h E H with small loss [hh). We denote the best-in- class expected loss by L (*()) = inf (h)). Given sam- ple S = (Z1,..., Fmm) and a hypothesis h, the empirical loss _ Σr |an (ttpaattttahhs)) m
(h) - (3)) + (H) $ sT(Ee, (h) (3() + Me, (30), (1)
where, for any loss function f, (3C) is defined as M)))) 87 ()t) Eiinnnerr B[e(h, 2t v) ær], and is re- ferred to as the minimizability gap.
is defined by (h)
E [A h(a.)(() (ag. Pah(as)-
For K = Hall the second term coincides with Ej (H) (Stein- wart, 2007; Mao, Mohri, and Zhong, 2024i) and the mini- mizability gap is zero. In this case, the bound simplifies to - (J() s T(Ee, (h) - E (9()) which, in partic- ular, implies cayes-consisteney.. More generally, the min- imizability gap vanishes when (H) = Ej (Hau). The minimizability gap is always upper bounded by the approx- imation error but it can be strictly smaller in many cases. In general, H-consistency bounds provide a stronger, non- asymptotic, and hypothesis set-dependent consistency guar- antee.
3.2. Equivalent Problem
(h) 2
The generalized metrics introduced above are defined the ratio of two expected loss functions. This formulation differs from the more familiar single-loss expectations, which are commonly used for deriving and analyzing surrogate loss functions in machine learning. In this section, we present an equivalent reformulation of the problem of minimizing [(h). This reformulation will provide a more convenient framework for designing surrogate loss functions.
For any (h, v) Hall x Xx y, we define two loss func- tions: fai (h, (1, y) to on hn)()) + 022 + ogh(2) 04 and fg: (h,,,y) + Bi h())yy 32y + 3ah(2) + Ba. Using these definitions, L(h) can be rewritten as follows:
3. Problem Formulation
Our goal is to devise principled learning algorithm seeking to optimize any instance within a broad family of general- ized metrics. We first define this family and then reformulate the learning problem using an alternative loss function.
L(h) = ( ( xr y)] E( Ex ( xr, y)]*
that is, the fractional form of the expected losses of fa and fg. Next, to minimize [(h). we reformulate it as equiv- alent optimization problem, which will facilitate further analysis and surrogate design.
3.1. Generalized Metries
We study generalized metrics for binary classification, de- fined as follows for any h E Han::
E(.,))- [a h( (zyy azy + azh(x) + a4]
For any (and a and 3), define the loss function ea by:
[(h)= 1 (x (ith(z) y + Bay + 83h(x) B.]]
(2)
vh,, (h 2, v) = ta (h, x, v) Neg(h, (3)
where h(z) = sign(h(z)) represents the prediction of a hypothesis on an input xf E X. with sign(a)= = 1.20 - Laco, 03, and with a = [a1, 0r2, 03, a4], 3 [31, 32, 3,] e RR To avoid notational clutter, (a, () is understood from the context and omit it when it is not necessary. Note that the true positive (TP), false positive (FP), true negative (TN), and false negative (FN) statistics can be expressed in terms of E ((a,)) [h(z)y]. (x)))) and [hx,)][(()]]:
We will denote by EØx,s the empirical loss of ed over a sam- ple S. Without loss of generality, we assume throughout that yyr [lg (h, x, y) is positive for all h e HC If this condi- tion does not hold, it can be enforced by redefining f/ -La and fa - lla, needed. For convenience, we will further define Ls- inf [(r.))-(Ls(h,, x, y)] and assume fo O. Similarly, let 7,3 = supneæ E( [Lx xt, y)], where L < +o0. The following theorem establishes that minimiz- ing L(h) over H. is equivalent to minimizing (h) over H,, where X = (36).
assume the dependence
TP= E [())7] (x.g)
FN= E [1- h(x) g+ h())] (x.y)
Theorem 3.1. The equality [(h") = (X) holds for ht e H if and only if (hx)((+))= = (HH) =
TN = E y h()vy]
FP- = E
h(xx) - h(
(z.g)
(z.g)
Proof. Assume that there exists a hypothesis h² H. such that L(h") L- (H)) holds. We have for all h e H:
2+1 E (0, 13. Thus, where h(x)= h(x)+1 (0, and T= 2
any ratio of two linear combinations of TP, FP, TN, and FN, which are considered in (Koyejo et al., 2014), can be expressed equivalently in the form of (2). This formulation
x -(k')= Elaa(h a., 2,,)] Blla x. v)] [l ",,"",,,", x, x,,)] (h, x. y)]
3

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
Thus, under the assumption, the following holds for all he e H:
where Ly is cost-sensitive function over y y defined
'1 + 12 + 73 + 74
y' = 1, y = 1,
(a.))-
(l 2,,,
| (h,,,,,))) (a.v)-D
E
(,(1'))==
-71 - 72 73 + 74
y = 1, = -1,
X
E [aa x, x.,y]== (na))-
E
a 2z, ,2,
-1+ +
-21
722
+
y' = =-1,3 = 1,
(a.1))-))
71 - 72 73 + 7/
y' = -1 y/ = -1.
o/=-1,30
This implies that & (h*) Exx (Jt) = 0, which completes one direction of the proof.
Adding constant to Lyy does not affect its minimization. Therefore, we can augment it with non-negative constant to ensure Ly + 2 0. A suitable choice is = 1al + Inal has + Iaal-
Assume now that there exists h² e H such that (x-(hh)) = ())) = 0 holds. We have for all h E HC:
E [aa (,,,",,,,,)]))) -0, (x,0)- E (x.z)-2
X*
E L'(h"" ,,,0),,,))))) .r,y]] =0
This can be regarded as a special case of the general cost- sensitive learning problem (Elkan, 2001). In this context, we consider a cost-sensitive loss function L: L:(+1,-1) (+1,-1} RR,, which defines four non-negative costs: L(+1,+1), [(+1,-1), L(-1,+1), and L(-1,-1). These costs depend on the prediction h(r)) e (-1,+1) and the true label y E {-1, +1}. We denote by L the target loss function
(z,z)-
E
1 (l (h, x, y) ]]]]]]000
(α.
Thus, we have X Bl Lea ..yI]
E(a.u)-2 (p(hh"22))) 2.1)] = f(h') s ((h)
for all h e H. which implies [(h*) (*(H), This com- pletes the proof.
induced by [, defined as:
(h, L(h,x,y) [(h(x).))
(5)
More generally, the following non-asymptotic equivalence holds. The proof is given in Appendix B.
This approach is referred to as general cost-sensitive learn- ing, as opposed to the specific cost-sensitive learning prob- lem analyzed in (Scott, 2012). where L(+1,-1) -1) = 0, [(-1,+1) = 1 1- 0, and +1) = [(-1,-)) -1) = 0. Fur- thermore, the existing 0-weighted surrogate losses (Scott, 2012) are not applicable in this general setting.
Theorem 3.2. Fix 7 2 O and h e H. Then, the inequal- ity Eex= (h) S 1) holds if and only if C(h) - ())) s B(c.v)-=((((hhe..)))
Theorems 3.1 and 3.2 show that our problem can be re- duced to minimizing the expected value of the loss function e*. However, this remains intractable because eA is non- differentiable and even non-continuous (as it is linear in h). In the next section, we will define general family of consistent surrogate losses for g* that are more suitable for practical optimization techniques.
4.2. General Surrogate Losses
function of h
As with many target loss functions in learning problems, such as the zero-one loss in binary classification, directly minimizing the general cost-sensitive loss function L is in- tractable for most hypothesis sets due to its non-continuity and non-diiferentiabiiityy Instead, surrogate losses are typ- ically adopted in practice. These surrogate losses are de- signed to be consistent, or even H-consistent in the stan- dard classification settings (Zhang, 2004; Bartlett et al., 2006; Awasthi et al., 2022a;b; Mao et al., 2023f). They are frequently formulated as margin-based loss functions (Lin, 2004), which are defined by non-increasing functions Φ: l + R that upper bound L ++ 1ıgo. For example, & could be the hinge loss, t + max 1 f), or the logistic loss, t + log(1++e")
4. General Cost-Sensitive Learning
In this section, we first establish that e** can be interpreted as generalized cost-sensitive target loss function. We then consider the broader problem of cost-sensitive learning and introduce novel family of surrogate loss functions tailored to this framework. Finally, we present strong theoretical guarantees for these surrogate losses, demonstrating that minimizing them yields efficient algorithms for both general cost-sensitive learning and the optimization of ex"
Here, we define the following surrogate loss functions for the general cost-sensitive loss function L by extending the standard margin-based loss function to the general cost- sensitive setting:
4.1. General Target Loss
Define = [71, 72, 73, 7a.. where 7/- = a, X B,, for i {1, 11,2,,,44, 4). Then, for any h E H and (x,y) e X x y. e^ (h, x, y) can be expressed as:
ABB,,
(6) lists common examples of &b along with the corre- sponding general cost-sensitive surrogate losses. special
L. (h, =
Table
71 vih(x)y + +2 + rah(2) + 74 7744-yy (hxx))
(4)

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
Table 1. Common Margin- Based Losses and Their General Cost-Sensitive Surrogate Extensions.
Name
(())
Cost-Sensitive Surrogate Loss L
Exponential
(tep(t) = e-
+ [++1.g)e
Logistic
(rog(1) log(1 (1+
[(+I.y) log(1+ [(-1,y) log +e
Quadratic
(tua max{ (,,3
([(()) Quand (A(x))
Hinge
2 Painge (t) (1,,0)
(xt.))) Baig (h(x))
(h(x))
Sigmoid
(t) 1- tanh(ktt,
p-Margin
(x())= = min (1, 0.1 p
+ (L
case of (6) arises when the costs satisfy [(+1,-1) 0, [(-1,+1) 1- 8, and [(+1,+ = [(-1.-1) = 0. This corresponds to the w-weggtted surrogate loss considered in (Scott, 2012; Koyejo et al., 2014). Our formulation general- izes and significantly extends this surrogate loss framework to address the broader context of general cost-sensitive learn- ing.
cost-sensitive surrogate losses La (Eq. (6)) also admit H-- consistency bounds with respect to the cost-sensitive loss L (Eq. (5)).
Theorem 4.1. Assume that L takes values in [0, mmnx] Let H be regular hypothesis set and 4 a margin- based loss function for the binary zero-one loss function fo-1- Assume that & admits I-3E-consistency bound with respect to 1 for a function I:t + Bt", with a E (0, 1] and B > O. Then, Lg admits a . T-H--onsiitency bound with respect to L, where T(t) = (22 1-
It is important highlight that our proposed algorithm, detailed in Section 5, for optimizing generalized metries differs fundamentally from the second algorithm introduced in (Koyejo et al., 2014) (see also (Parambath et al., 2014)), despite both leveraging a sub-algorithm for cost-sensitive learning. As discussed in Section I, their approach involves approximating the Bayes-classifier, threshold function, us- ing the w-wightted cost-sensitive surrogate loss function. In contrast, our algorithm minimizes a general cost-sensitive surrogate loss function that is H-consistent (see Section 4.3) with respect to general cost-sensitive target loss func- tion (4), with label-dependent costs that take into account the best-in-class error of the generalized metric in binary classification, which can be approximated through binary search-based algorithm (see Section 5).
The proof is included in Appendix C. Based on the results of Awasthi et al. (2022a), the theorem holds with r(t)= = 2 for the logistic loss and the exponential loss (a = 1/2), T(t) = vt for the quadratic loss, and [(t) = t for the hinge loss, sigmoid loss and p-margin loss (a = 1).
As already mentioned, when the best-in-class error coincides with the Bayes error, E E7 (Han) for é Lg and l L, the minimizability gaps ML and ML. (H) van- ish. Under these conditions, the H--consistency bound guar- antees that when the surrogate estimation error & (h)
et, (IC) is reduced to e, the estimation error of the cost- sensitive loss &L (h) (3) is upper bounded by I'(e).
4.3. Theoretical Guarantees
More generally, since a concave function I' is sub-additive over R,,, the following guarantee holds:
In this section, we establish strong theoretical guarantees for a surrogate loss Lg. Specificallyy, we derive H--onnistency bounds for Le with respect to the cost-sensitive loss function L, focusing on commonly used hypothesis sets.
EL ((()) $ <T (h) Et. (H)) + (M)) - (3H.
We define a hypothesis set HC as regular if, for any E X. the set of predictions made by the hypotheses in H on x covers all possible labels: (h(z): h e F(} = -1]. Commonly used hypothesis sets, such as linear models, neural networks, and the family of all measurable functions, all naturally satisfy this regularity condition.
When the minimizability gaps (or the upper bound- ing approximation errors) are small, the last terms, [M,,, (FO) - MM (3)] is also small and close to zero In particular, when H = Han, the family of all measur- able functions, all minimizability gap terms in Theorem 4.1 vanish, yielding the following result.
It was shown by Awasthi, Mao, Mohri, and Zhong (2022a) that common margin-based loss functions, such as the hinge loss, logistic loss, and exponential loss, admit strong HC- consistency bounds with respect to the binary zero-one loss function lu-1: (h, y) In(z)ey when using such regular hypothesis sets. The next result shows that, for such margin- based loss functions o their corresponding
Corollary 4.2. Fix margin-based -baeed loss function D. Assume that there exists a function T()) = B t for some a (0, 1] and ( > 0, such that the following excess error bound holds for all h E Hall and all distributions:
ELo (1) - EE..,
- (Hal) & &T(E (h) E.p (Hau)).
5

---

over the draw of a Principled Algorithms for Optimizing Generalized Metries in Binary Classification
Then, the following excess error bound holds for all h Hall and all distributions:
Algorithm Binary search estimation of X*
input
1: Initialize [a, bJ +- [Aminy Amax]
EL(h)- - (ICan) S ( Ei, (PG))),
repeat
where T(t)= = 3 (mx 1m000
3: A - a+b
2 4: if (f (H) 0) then
Building the results of Awasthi et al. (2022a) for [tt) already mentioned and Corollary 4.2, we now derive the following result.
5:
[a,b] = =[x,b]
6: else
7: [a. b] = [a, A]
Corollary 4.3. For all h E Hall and all distributions.
end
until |b- al sc
EL(h) ( (HHan) s E(LLo (h) - EL. (H(al)),
10: return À
where T(t)= = 2//L t for o- Pexp and Plug. f(t)
2 mmax L for 4- 4 quaa,, and [() = t for Pninges
This naturally suggests a binary search-based algorithm to compute an c-approximation of X", assuming oracle access to the sign of Eqa (H). The pseudocode of this algorithm is provided in Algorithm 1,where Amin and Amax denote the minimum and maximum possible values of X, respectively, These bounds can be determined from the range of X using the formulation (2) for the given pair (or,3).
sig. and p-
By taking the limit on both sides, establish the Bayes- consistency of these cost-sensitive surrogate losses Lg with respect to the cost-sensitive target loss L. More generally, Corollary 4.2 demonstrates that Le admits an excess error bound with respect to L if & admits an excess error bound with respect to 10-1-
Theorem 5.2. Let O be fixed. Algorithm I returns an e-approximation À of X in O(logz( (Amax-Amin)) time, such that the following property holds:
5. Algorithm for Generalized Metrics
Eex (H) s (H) + cls clg.
In this section, we build on the previous theoretical analysis to develop algorithms for optimizing general metrics with strong guarantees. We first characterize A", motivating a binary search algorithm under oracle access to the sign of the expected loss. We then propose an algorithm based on empirical minimization of surrogate loss L. for e and introduce simpler cross vallss-iiiatiion approach for selecting A. Finally, we discuss the theoretical foundations of our algorithms, compare them to prior work, and highlight cases where existing methods may fail due to reliance on the Bayes-optimal solution.
The proof is presented in Appendix E. Of course, in practice, we do not have oracle access to the sign of E% (H). How- ever, we can approximate E/ (IC) by computing the solu- tion lis that minimizes a surrogate loss Lg of Ed on a labeled sample S of size m. To do that, tion bound for the target loss fat by using our H-consiitency bounds presented in Section 4.3. Given a sample S of size m. we denote by RR (H) the Rademacher complex- ity of the function class {(x, y) + Loph, x, y): e H{ and Bx supp, (h, x. y) an upper bound on La-
first provide generaliza-
First, note that in the general cost-sensitive learning problem, the costs [(+1,y) and [(-1, y) are known priori. In our scenario, the costs defining f* depend on X", which is not known. We will seek determine or approximate X"
Theorem 5.3. Assume that the surrogate loss La admits a T-H-consistency bound with respect to Lt, Then, for any 8 0, with probability at least sample S from D the following estimation bound holds for an empirical minimizer hg H of the Lo over S:
3( (fa. Recall that X = L (H) = inf E(s. (aa,,,) and that the expected loss of H with respect to the loss function f* can be expressed as follows:
Era (nss)-(Eaa (H)
εex (h) (2.
IE (h, x.,)]
E 2, (a.V)-
( ML (H) 499 (H) 2B,
log 2
Mex (H).
The following provides a key characterization of x* Theorem 5.1. We have (H)) = and, for any X e IR sign( Eg (3)) sign(X* (X* >).
Note that such e> -stimmation loss guarantees for the mini- mizer of a surrogate loss Lo can rarely be found in the litera- ture. The proof is presented in Appendix F. For Theorem 5.3, the parameter À is fixed. But, the bound of the theorem can be generalized to hold uniformly for all X e [Amin Amax] by covering the interval using aub-intervals of size 1/m.
The proof is included in Appendix D. Theorem 5.1 provides a characterization of the sign of the best-in-class expected loss Ep (H) in terms of the sign of X X.
6

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
Theorem 5.4. Assume that the surrogate loss Lı admits T-H--consistency bound with respect to & Then, for any ó > O, with probability at least 1 1-6 ô over the draw of a sample S from D the following estimation bound holds for an empirical minimizer hig e H of the surrogate loss La over S and A E [mmins )
Algorithm 2 Generalized metrics optimization algorithm
input E, em
Initialize with [a, [] Dmin Amax]
repeat
3: A o+b
4: hi + argmin SLo
if (EEE,,, g(,x)))))>)))))){()))) ) Cm) then
5:
Eer (hs) E/a (30) T ML. (IO) ML. 8 8max,|3:14 m² + 2Bx+
A (IL)
6:
[a,b]= [[1bb]
7:
else (E s s(hx) ) <mm) then
4max||3;|Bg
V
log 2. m 2m
[a, b] [a, A]
else
m
10:
return Ti
11: end if
where AA = Amax- Amin. In particular, when T(t)
12:
until [b al S
2(Lmuxx # for Blog. the bound can be expressed as
13:
return h2
follows:
Algorithm 3 Generalized metrics optimization algorithm with cross- vosss-vvlidttion
Eer (hi) Egg (H) s (2 mmxx)
Mi (30) 429 (H)
input
$ Za
1: Initialize with [a, [Amin Amax X" Amax. i 0
8maxx|BilBo m²
2B mmxx Bo
log 2mm
m(a)) R
2: repeat
m
3:
<- a ie
4: hi + argmin (h)
Then, for any 8 0, with probability at least - 6, for all A E [Amin ). we have
5:
if (TCSsTss) < X*) then
6:
X= A
7:
X + (hx)
Ee (hs) E22 (J))
end if
s (T (2) (H) + (rmava Amnn )m/6) Mi (H)))
i i++
10: until + ie
11: return Ti
The proof is presented in Appendix G. We denote the right- hand of this bound by 6m- Building on the ideas from Algorithm 1, we introduce the modified algorithm Algo- rithm Note that, with high probability, Exx_s (hx) Cm implies Ei (H)) O and, similarly, (hx) -cm im- plies E/ (3) < O. Thus, this follows conditions used in the previous algorithm. The algorithm benefits from the following guarantee.
cases. In such scenarios, À can be treated as hyperpa- rameter and tuned via cross-validation, as outlined in Algo- rithm 3. The following result establishes convergence and performance guarantees for this algorithm. Compared to Algorithm 2, its computational complexity is linear rather than logarithmic.
Theorem 5.5. Lete= fm., For any ô >>0000000 O, with probability 21,"
Theorem 5.6. For any 8 > O, with probability at least 1 - 8, for S Sm,, Algorithm 3 returns in O Amns Aumn--min) time a 28 , hypothesis hy that admits the following guarantee:
least 1- 6, Algorithm returns in Ologg( Amax Amain time hypothesis hi that admits the following guarantee:
46m LB
+ 26m
((T)) S L- ( (J()
fo
The proof can be found in Appendix H. Thus, when em small, that is, when the sample size is sufficiently large relative to the complexity of H and the minimizability gap is small, the performance of Tix closely approaches the optimal performance achievable with H.
The proof is presented in Appendix I. We refer to Algo- rithms and 3 as METRO (Metric Optimization). The effec- tiveness of METRO compared to prior basclines is demon- strated by the experimental results reported in Section 6.
Note that the quantities Tix and ε ,s (Tx) in Algorithm 2, as well as h2 and (hx) in Algorithm 3, are approximated using data sampled from the same distribution, but they can be obtained from different samples. In practice, as done in
In practice the theoretical expression for c. may not be sufficiently tight due to constants or the minimizability gap, which cannot be accurately approximated in non-realizable
7

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
cation only by an offset, their approach first trains a binary classifier and then selects an optimal threshold offset. However, this approach typically fails to find the best pre- dictor within a restricted hypothesis set.
Figure 1 illustrates this issue with a simulated exam- plc. The best-in-class linear hypothesis for L with a 5. and / (o. 5. 1 8) (corresponding to the Fo.5-measure is significantly different from the linear hypothesis obtained by thresholding the best-in-clas SVM classifier. The two decision boundaries are not even parallel, highlighting the fundamental inadequacy of thresholding- based approaches such as those in (Koyejo et al., 2014). In contrast, our algorithm successfully finds a linear hypothesis that closely matches the best-in-class solution for L.
-16 16 16 16
best-in class SVM classtier
best in cass classifieroo Fas measure
gonthh
Figure 1. Comparison of the best-in-class SVM classifier, the opti- mal linear hypothesis for the Fo.s-measure, and the linear hypoth- esis returned by our algorithm.
Finally, note that when 31 = -3 0 for generalized metrics, the independence of X* from the hypothesis h in the target loss (Eq. (4)) significantly simplifies our algorithm, as X no longer needs to be estimated.
(Koyejo et al., 4), we can split the training data into two parts: Ā is obtained from one part, and then used to train the hypothesis lig on the other.
Theorems 5.5 and 5.6 remain valid long as the data are sampled independently from the same distribution. How-
6. Experiments
ever, in over-parameterized settings, the value of em may be larger due to the high complexity of the model. This quan- tity becomes small only when the sample size is sufficiently large relative to the complexity of the hypothesis set. This limitation applies broadly to most generalization bounds for complex neural networks.
In this section, we present empirical results for our princi- pled algorithms for optimizing generalized metries on the CIFAR-10 (Krizhevsky, 2009). CIFAR- 100 (Krizhevsky, 2009) and SVHN (Netzer et al., 2011) 1) datasets.
Our experiments use a three-hidden-layer CNN with ReLUU activations (LeCun et al., 1995). Standard data augmenta- tions were applied CIFAR-10 and CIFAR- 100, includ- ing 4-pixel padding followed by 32 32 random cropping and random horizontal flipping- Training was conducted using Stochastic Gradient Descent (SGD) with Nesterov momentum (Nesterov, 1983). The initial learning rate, batch size, and weight decay were set to 0.02, 1,024, and x 10-4, respectivey, A cosine decay learning rate schedule (Loshchilov & Hutter, 2022) was used over the course of 100 epochs. During training, we extract two classes from each dataset to form binary classification task.
The current analysis of over- reee-parameteriee settings typically requires alternative tools, particularly those that account for the optimization algorithm (e.g.. Stochastic Gradient Descent (SGD) (Bottou, 2010) and its dynamics. Such analyses often apply only to more restricted model families.
Comparison of our algorithms with prior work. As dis- cussed in previous sections, our algorithms METRO for opti- mizing general metrics are supported by strong theoretical guarantees. These guarantees apply to arbitrary hypoth- esis sets and provide samite-sample bounds. In contrast, prior methods (Koyejo et al., 2014) rely solely on Bayes- consistency, which holds only for the class of all measurable functions. This makes their analysis less relevant in realis- tic settings where learning is restricted to specific function classes, an issue explicitly left open in (Koyejo et al., 2014) 14). Furthermore, their approach does not provide convergence rate guarantees, in contrast with our finite-sample bounds. In many modern applications, particularly with complex neural networks, the minimizability gap often small or close to zero due to near-separable data. In such cases, our learning guarantees become even more favorable.
We evaluated the models using their averaged general- ized metric L. In particular, we consider the F' measure (Ye et al., 2012), where a = - [1+0² 1-g² 1+6² 1+02)
4
and B (o, : tt1). and the Jaccard similarity co- efficient (JAC) (Sokolova & Lapalme, 2009), where a 2 H) and B = (2 3 - .)). The reported metric is averaged over five runs, with standard deviations included. We compared the METRO algorithm using cross-validation (Algorithm 3) with four baselines: the standard empirical risk minimization (ERM), the first algorithm (Algorithm 1) and the second algorithm (Algorithm 2) from (Koyejo et al., 2014), as well as the algorithm from (Parambath et al., 2014), as detailed in Section 1. For METRO algorithm, we used the surrogate loss Ls in (6) with the auxiliary func-
Beyond theoretical advantages, a key limitation of prior methods is their reliance on the structure of the Bayes- optimal solution. Since the Bayes-optimal predictor for a given metric typically differs from that of binary classifi-
8

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Table F9 measure and JAC of three-hidden-layer neural network CIFAR-IO, CIFAR-100 and SVHN; mean standard deviation over five runs for ERM. Algorithm and Algorithm 2 in (Koyejo et al., 2014), Algorithm in (Parambath et al., 2014), and METRO Algorithm.
Algorithm
Metric
CIFAR-10
CIFAR-100
SVHN
ERM
0.9004 0.0015
0.9265 + 0.0067
0,9676 + 0.0028
Algorithm in (Koyejo al., 2014)
0.9040 0.0134
0.9320 0.0065
0.9679 + 0.0035
Algorithm 2 in (Koyejo et al., 2014)
Fi
0.9090 0.0070
0.9317 0.0114
0.9677 = 0.0022
Algorithm in (Parambath et al., 2014)
0.9185 0.0029
0.9343 = 0.0111
0.9682 # 0.0021
METRO Algorithm
0.9359 0.0041
0.9405 = 0.0103
0.9713 = 0.0029
ERM
0,9418 + 0.0092
0.9338 = 0.0216
0.9689 = 0.0037
Algorithm in (Koyejo et al., 2014)
0.9476 + 0.0032
0.9510 = 0.0138
0.9715 = 0.0035
Algorithm in (Koyejo et al., 2014)
Fo.5
0.9503 0.0028
0.9435 = 0.0140
0,9730 = 0.0017
Algorithm in (Parambath et al., 2014)
0.9507 + 0.0036
0,9515 = 0.0105
0,9746 + 0.0011
METRO Algorithm
0.9585 + 0.0023
0.9759 + 0.0115
0.9807 + 0.0015
ERM
0.9234 0.0074
0.9279 0.0160
0.9675 # 0.0035
Algorithm in (Koyejo et al., 2014)
0.9305 0.0029
0.9331 0.0218
0.9688 # 0.0025
Algorithm 2 in (Koyejo et al., 2014)
Fi.5
0.9263 0.0036
0.9340 0.0119
0.9677 + 0.0020
Algorithm in (Parambath et al., 2014)
0,9312 + 0.0044
0.9345 = 0.0118
0.9702 + 0.0023
METRO Algorithm
0.9459 0.0030
0.9449 = 0.0115
0.9771 + 0.0018
ERM
0.4689 0.0022
0.4693 # 0.0063
0.4767 + 0.0036
Algorithm in (Koyejo et al., 2014)
0.4821 + 0.0024
0.4728 = 0.0109
0.4814 + 0.0031
Algorithm in (Koyejo et al., 2014)
JAC
0.5746 0.0121
0.4753 = 0.0119
0,4875 = 0.0017
Algorithm in (Parambath et al., 2014)
0.6428 0.0130
0.4924 = 0.0152
0,4934 + 0.0019
METRO Algorithm
0.6575 0.0018
0.5017 = 0.0046
0.4965 + 0.0024
tion (t)= log(1 + e) which corresponds to the logistic loss function used in logistic regression. The logistic loss was also used for ERM and Algorithm in (Koyejo et al., 2014), while Algorithm in (Koyejo et al., 2014) 4) and the algorithm from (Parambath et al., 2014) used the weighted logistic loss. All the hyperparameters in these algorithms were selected through cross validatio..
datasets, which often present greater challenges and are more representative of real-world applications. We plan to include such experiments and comparisons in future work.
One may wonder about the difficulty of directly optimizing a general metric defined as the ratio of the expectations of two loss functions, both linear in h, where h(x) sign (x)).. While the metric is quasi-concave in h, optimizing it with respect to h is NP-hard, even when the denominator is con- stant and / is restricted to a linear hypothesis set. In con- trast, each surrogate loss optimization problem we consider (framed as supervised learning) can be solved in polyno- mial time over convex hypothesis set, as the surrogate loss functions we adopt are convex. Furthermore, directly optimizing the empirical ratio of the numerator and denomi- nator may not yield a provably good approximation of the metric, since their expectation does not align with the ratio of expectations.
Table 2 shows that our algorithm consistently outperforms the four baselines across all datasets. Notably, the algo- rithm in (Parambath et al., 2014) consistently outperforms Algorithms 1 and 2 in (Koyejo et al., 2014) by using two hyperparameters: 9 for weighting the logistic loss and 6' for thresholding the classifier. In contrast, the relative perfor- mance of Algorithms 1 and 2 in (Koyejo et al., 2014) varies across datasets, although both outperform ERM.
Note that the per-epoch computational cost of our method is comparable to that of Algorithm 2 in (Koyejo et al., 2014). Both methods involve a single hyperparameter, and for a fixed value of this parameter, the computational cost is simi- lar to training standard binary classifier using standard surrogate loss.
7. Conclusion
We presented series of theoretical, algorithmic, and empir- ical results for optimizing generalized metrics in binary clas- sification, highlighting the significance of our algorithms supported by H--conistency guarantees. Looking ahead, a natural direction is extending our theory and algorithms to cover generalized metrics in multi-class classification and multi-label learning, broadening their applicability.
In line with prior work (Koyejo et al., 2014), we used stan- dard image classification datasets for our empirical evalua- tion to demonstrate the effectiveness of our methods relative to existing baselines. However, we acknowledge the im- portance of evaluating our algorithms on more imbalanced

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Acknowledgements
Berman, M., Triki, A. R., and Blaschko, M. B. The lovász- softmax loss: A tractable surrogate for the optimization of the intersection-over-uniin measure in neural networks. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 4413-4421, 2018.
We thank the anonymous reviewers for their valuable feed- back and constructive suggestions.
Impact Statement
Bottou, L. Large-scale machine learning with stochastic gra- dient descent. In Proceedings of COMPSTAT 19th International Conference on Computational Statistics, pp. 177-186, 2010.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Busa-Fekkte, R., Szörényi, B., Dembezynski, K., and Hüllermeier, E. Online F-measure optimization. In Ad- vances in Neural Information Processing Systems, 2015.
References
Awasthi, P., Frank, N., Mao, A., Mohri, M., and Zhong, Y. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Sys- tems, pp. 9804-9815, 2021a.
R., Choi, H., Dembezynski, K., Gentile, C., Reeve, H., and Szorenyi, Regret bounds for multilabel classification in sparse label regimes. In Advances in Neural Information Processing Systems, pp. 5404-5416, 2022.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.01550, 2021b.
Cheng, F., Zhou, Y., Gao, J., and Zheng, S. Efficient opti- mization oF o-mmasuue with cost-sensitive svm. Mathemat- ical Problems in Engineering, 2016(1): 1111)))))11,20111
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. HC- consistency bounds for surrogate loss minimizers. In International Conference Machine Learning, 2022a.
Cortes, C., Mao, A., Mohri, C., Mohri, M., and Zhong, Cardinality set prediction and top-k classification. In Advances in neural information processing systems, 2024.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Multi-class H-cconsistency bounds. In Advances in Neural Informa- fion Processing Systems, 2022b.
Cortes, C., Mao, A., Mohri, M., and Zhong, Y. Balancing the scales: A theoretical and algorithmic framework for learning from imbalanced data. In International Confer- ence Machine Learning, 2025.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Theoreti- cally grounded loss functions and algorithms for adversar- ial robustness. In International Conference on Artificial Intelligence and Statistics, pp. 10077-10094, 2023.
Dai, B. and Li, C. Rankseg: a consistent ranking-based framework for segmentation. Journal of Machine Learn- ing Research, 24(224):1-50, 2023.
Awasthi, P., Mao. A., Mohri, M., and Zhong, Y. DC- programming for neural network optimizations. Journal of Global Optimization, 2024.
Dembezynski, K., Jachnik, A., Kotlowski, W., Waegeman, W., and Hüllermeier, E. Optimizing the F-measure in multi-label classification: Plug-in rule approach versus structured loss minimization. In International Conference Machine Learning, pp. 1 1130-11.20 1138, 2013.
Bao, H. and Sugiyama, M. Calibrated surrogate maximiza- tion of finear-fractions utility in binary classification. In International Conference Artificial Intelligence and Statistics, pp. 2337-2347, 2020.
Dembezyúski, K., Kotlowski, W., Koyejo, O., and Natarajan, Consistency analysis for binary classification revisited. In International Conference on Machine Learning, pp- 961-969 2017.
Bartlett, P. L., Jordan, M. I., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 2006.
Bascol, K., Emonet, R., Fromont, E., Habrard, A., Met- zler, G.. and Sebban, M. From cost-sensitive to tight F-measure bounds. In International Conference Artifi- cial Intelligence and Statistics, pp. 1245-1251 2019.
Drummond, C. and Holte, R. C. Severe class imbalance: Why better algorithms aren't the answer. In European Conference on Machine Learning, pp. 339-546, 2005.
Eban, E., Schain, M., Mackey, A., Gordon, A., Rifkin, R., and Elidan, G. Scalable learning non-decomposable objectives. In Artificial Intelligncce and Statistics, pp. 832-840, 2017.
Berger, A. and Guda, S. Threshold optimization for mea- sure of macro-averaged precision and recall. Pattern Recognition, 102:107250, 2020.
10

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Elkan, C. The foundations of cost-sensitive learning. In International Joint Conference on Artificial Intelligence, pp. 973-978, 2001.
Kotlowski, W. Wydmuch, M., Schultheis, E., Babbar, R., and Dembezyński, K. A general online algorithm for op- timizing complex performance metrics. In International Conference on Machine Learning, 2024.
Fathony, R. and Kolter, Z. Ap-perf: Incorporating generic performance metrics in differentiable learning. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 4130 4140, 2020.
Koyejo, O., Natarajan, N., Ravikumar, P., and Dhillon, S. Consistent binary classification with generalized perfor- mance metrics. In Advances in Neural Information Pro- cessing Systems, pp. 2744-2752, 2014.
Flach, P. and Kull, M. Precision-recall-ee curves: Pr analysis done right. In Advances in Neural Information Processing Systems, 2015.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, Toronto University, 2009,
LeCun, Y., Bengio, Y., et al. Convolutional networks for images, speech, and time series. The Handbook of Brain Theory and Neural Nenworks, 3361(10): 1995.
Gu, Q. Zhu, L., and Cai, Z. Evaluation measures of the classification performance of imbalanced data sets. In Computational Intelligence and Intelligent Systems: 4th International Symposium, pp. 461-471, 2009.
Lewis, D. D. Evaluating and optimizing autonomous text classification systems. In Proceedings of the 18th An- nual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 246-254, 1995a.
He, H. and Garcia, E. A. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, 21(9):1263-122) 1284, 2009.
Jansche, M. Maximum expected F-measure training of logistic regression models. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pp. 692-699, 2005.
Lewis, D. D. A sequential algorithm for training text clas- sifiers: Corrigendum and additional data. In Acm Sigir Forum, volume 29, pp. 13-19, 1995b.
Lin, Y. A note on margin-based loss functions in classi- fication. Statisties & Probability Letters, 68(1):73-82, 2004.
Jansche, M. A maximum expected utility framework for binary sequence labeling. In Proceedings of the 45th Annual Meeting of the Association of Computational Lin- guistics, pp. 736-743, 2007.
Lipton, Z. C., Elkan, C., and Narayanaswamy, B. Thresh- olding classifiers maximize F1 score. Stat, 1050:14, 2014.
Jasinska, K., Dembezynski, K., Busa-Fekete, R., Pfannschmidt, K., Klerx, T., and Hullermeier, E. Ex- treme F-measure maximization using sparse probability estimates. In International Conference on Machine Learn- ing, pp. 1435-1444, 2016.
Long, P. and Servedio, R. Consistency versus realizable H- consistency for multielass classification. In International Conference on Machine Learning, pp. 801-809, 2013.
Loshchilov, I. and Hutter, F, SGDR: Stochastic gradient descent with warm restarts. In International Conference on Learning Representations, 2022.
Jiang, Q., Adigun, O., Narasimhan, H., Fard, M. M., and Gupta, M. Optimizing black-box metrics with adap- tive surrogates. In International Conference Machine Learning, pp. 4784 4793, 2020.
Luo, J., Qiao, H., and Zhang, B. A minimax probability machine for nondecomposable performance measures. IEEE Transactions on Neural Networks and Learning Systems, 34(5):2353-2365 2021.
Joachims, T. A support vector method for multivariate performance measures. In International Conference on Machine Learning, pp. 377-384, 2005.
Mao, A. Theory and Algorithms for Learning with Multi- Class Abstention and Multi-Expert Deferral. PhD thesis, New York University, 2025.
Kar, P., Narasimhan, H., and Jain, P. Online and stochastic gradient methods for non-decomposable loss functions. In Advances in Neural Information Processing Systems, 2014.
Mao, A., Mohri, C., Mohri, M., and Zhong, Y. Two-stage learning to defer with multiple experts. In Advances in neural information processing systems, 2023a.
Kotlowski, W. and Dembczyński, K. Surrogate regret bounds for generalized classification performance metrics. In Asian Conference on Machine Learning, pp. 301-316, 2016.
Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds for pairwise misranking loss surrogates. In International conference on Machine learning, 2023c.
Menon, A., Narasimhan, H., Agarwal, S., and Chawla, S. On the statistical consistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pp. 201-3.1,0013.
Mao, A., Mohri, M., and Zhong, Y. Ranking with abstention. In ICML 2023 Workshop The Many Facets of Preference- Based Learning, 2023d.
Menon, A., Van Rooyen, B., Ong, C. S., and Williamson, B. Learning from corrupted binary labels via class- probability estimation. In International Conference on Machine Learning, pp. 125-134, 2015.
Mao, A., Mohri, M., and Zhong, Y. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
Menon, A. K. and Williamson, R. C. The cost of fairness in binary classification. In Conference on Fairness, Ac- countability, and Transparency, pp. 107-118, 2018.
Mao, A., Mohri, M., and Zhong, Y. Cross-entropy loss functions: Theoretical analysis and applications. In Inter- national Conference on Machine Learning, 2023f.
Mohri, C., Andor, D., Choi, E., Collins, M., Mao, A., and Zhong, Learning to reject with fixed predictor: Ap- plication to decontextuullzzatonn. In International Confer-
Mao, A., Mohri, M., and Zhong, Y. Principled approaches for learning defer with multiple experts. In Interna- fional Symposium on Artificial Intelligence and Mathe- matics, 2024a.
ence Learning Representations, 2024.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning. MIT Press, second edition, 2018.
Mao, A., Mohri, M., and Zhong, Y. Predictor-rejector multi- class abstention: Theoretical analysis and algorithms. In International Conference on Algorithmic Learning Theory, pp. 822-867, 2024b.
Montreuil, Y., Yeo, S. H., Carlier, A., Ng. L. X., and Ooi, W. T. Optimal query allocation in extractive QA with LLMs: learning-to-defer framework with theoretical guarantees. arXiv preprint arXiv:2410.15760 2024.
Mao, A., Mohri, M., and Zhong, Y. Theoretically grounded loss functions and algorithms for score-based multi-class abstention. In International Conference on Artificial In- felligence and Statistics, pp. 4753-4761, 2024c.
Montreuil, Y., Carlier, A., Ng, L. X., and Ooi, W. T. Ad- versarial robustness in two-stage learning-to-defer: Algo- rithms and guarantees. In International Conference on Machine Learning, 2025a.
Mao, A., Mohri, M., and Zhong, Y. Enhanced H- consistency bounds. In International Conference on Al- gorithmic Learning Theory, 2024d.
Mao, A., Mohri, M., and Zhong, Y. H-consistency guar- antees for regression. In International Conference Machine Learning, pp. 347 14712-34737,,000 2024e.
Montreuil, Y., Carlier, A., Ng. L. X., and Ooi, W. T. Why ask one when you can ask k? two-stage Sarning-to-defer to the top-k experts. arXiv preprini urXiv:2504. /2988, 2025b.
Mao, A., Mohri, M., and Zhong, Y. Multi-label learning with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2024f.
Montreuil, Y., Carlier, A., Ng, L. X., and Ooi, W. T. One-stage top-k learning-to-defer: Score-based sur- rogates with theoretical guarantees. arXiv preprint 2rXi::2505.00/6 2025c.
Mao, A., Mohri, M., and Zhong, Y. Realizable H H-consistent and Bayes-consistent loss functions for learning to defer. In Advances in Neural Information Processing Systems, 2024g.
Montreuil, Y., Yeo, S. H., Carlier, A., Ng, L. X., and Ooi, W. T. A two-stage learning-to-defer to-defer approach for multi- task learning. In International Conference on Machine Learning, 2025d.
Mao, A., Mohri, M., and Zhong, Y. Regression with multi- expert deferral. In International Conference Machine Learning, pp. 34738-34759, 2024h.
Narasimhan, H., Vaish, R., and Agarwal, On the statistical consistency of plug-in classifiers for non-decomposable performance measures. In Advances in Neural Informa- tion Processing Systems, 2014.
Mao, A., Mohri, M., and Zhong, Y. A universal growth rate for learning with smooth surrogate losses. In Advances in Neural Information Processing Systems, 2024i.
Mao, A., Mohri, M., and Zhong, Y. Mastering multiple- expert routing: Realizable H H-consistency and strong guar- antees for learning to defer. International Conference on Machine Learning, 2025.
Narasimhan, H., Kar, P., and Jain, P. Optimizing non- decomposable performance measures: A tale of two classes. In International Conference on Machine Learn ing, pp. 109-208,770 2015a.
12

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Narasimhan, H., Ramaswamy, H., Saha, A., and Agarwal, S. Consistent multiclass algorithms for complex perfor- mance measures. In International Conference Ma- chine Learning, pp. 2398-229920 2000222072220 2015b. 2015b..
Scott, C. Calibrated asymmetric surrogate losses. Electronic
Journal of Statistics, 6:958, 2012.
Sokolova, M. and Lapalme, G. A systematic analysis of per-
formance measures for classification tasks. Information Processing & Management, 45(4):427 437, 2009.
Narasimhan, H., Pan, W., Kar, P., Protopapas, P., and Ra- maswamy, H. G. Optimizing the multiclass F-measure via biconcave programming. In International Conference on Data Mining, pp. 1101-1106, 2016.
Steinwart, I. How compare different loss functions and their risks. Constructive Approximation, 26(2):225-28) 2007.
Narasimhan, H., Cotter, A., and Gupta, M. Optimizing generalized rate metrics with three players. In Advances in Neural Information Processing Systems, 2019.
Tavker, S. K., Ramaswamy, H. G., and Narasimhan, H. Consistent plug-in classifiers for complex objectives and constraints. In Advances in Neural Information Process- ing Systems, pp. 20366-20377 2020.
Natarajan, N. and Jain, P. Regret bounds for non- decomposable metrics with missing labels. In Advances in Neural Information Processing Systems, 2016.
Yan, B., Koyejo. S., Zhong, K., and Ravikumar, Binary classification with karmic, threshold waahholdd-uu---cccnaaa met- rics. In International Conference Machine Learning, pp. 5531-5540, 2018.
Natarajan, N., Koyejo, O., Ravikumar, P., and Dhillon, I. Optimal classification with multivariate losses. In Interna- tional Conference on Machine Learning, pp. 1530-1538, 2016.
Ye, N., Chai, K. M. A., Lee, W. S., and Chicu, H. L. Opti- mizing F-measures: a tale of two approaches. Interna- tional Conference on Machine Learning, pp. 1555-1562, 2012.
Nesterov, Y. E. A method for solving the convex program- ming problem with convergence rate o( (1/k²). Dokl. akad. nauk Sssr, 269:543-547, 1983.
Yu, J. and Blaschko, M. Learning submodular losses with the lovász hinge. In International Conference on Machine Learning, pp. (623-1631, 2015.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Reading digits in natural images with unsupervised feature learning. In Advances Neural Information Processing Systemx, 2011.
Zhang, M. and Agarwal, S. Bayes consistency vs. H- consistency: The interplay between surrogate loss func- tions and the scoring function class. In Advances in Neural Information Processing Systems, 2020.
Parambath, S. P., Usunier, N., and Grandvalet, Y. Opti- mizing F-measures by cost-sensitive classification. In Advances in Neural Information Processing Systems, pp- 2123-2131, 2014.
Zhang, M. and Agarwal, S. Multiclass learning from noisy labels for non-decomposable performance measures. In International Conference on Artificial Intelligence and Statistics, pp. 2170-2178, 2024.
Pillai, Fumera, G., and Roli, F. Designing multi-label classifiers that maximize F measures: State of the art. Puttern Recognition, 61:394-404, 2017.
Ramaswamy, H. G., Narasimhan, H., and Agarwal, S. Consistent classification algorithms for multi-class non- decomposable performance metrics. arXiv preprint arXiv: 00287, 2015.
Zhang, M., Ramaswamy, H. G., and Agarwal, S. Con- calibrated surrogates for the multi-label F-measure. In International Conference on Machine Learning, pp. 1 11246-11221 11266, 2020.
Reid, M. D. and Williamson, R. C. Surrogate regret bounds for proper losses. In International Conference on Ma- chine Learning, pp. 897-904, 2009.
Zhang, M., Lee, J., and Agarwal, S. Learning from noisy labels with no change the training process. In Inter- national Conference Machine Learning, pp. 12468 12478, 2021.
Sanyal, A., Kumar, P., Kar, P., Chawla, S., and Sebastiani, F. Optimizing -eooopoooeee measures with deep networks. Machine Learning, 107:1597-1620, 2018.
Zhang, T. Statistical behavior and consistency classifi- cation methods based on convex risk minimization. The Annals of Statistics, 32(1):56-85, 2004.
Schultheis, F.,, Kotlowski, W., Wydmuch, M., Babbar, R., Borman, S., and Dembezyíski. K. Consistent algorithms for multi-label classification with macro-at-k metrics. In International Conference on Learning Representations, 2024.
Zhang, X., Liu, M., Zhou, X., and Yang, T. Faster online learning of optimal threshold for consistent F-measure optimization. In Advances in Neural Information Pro- cessing Systems, 2018
13

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classificatinn
Zhao, M.-J,, Edakunni, N., Pocock, A., and Brown, G. Be- yond fano's inequality: Bounds the optimal F-score, ber, and cost-sensitive risk and their implications. Journal of Machine Learning Research, 14(1):1033-100 1090,, 2013.
Zheng, C., Wu, G., Bao, F., Cao, Y., Li, C., and Zhu, Revisiting discriminative vs. generative classifiers: The- ory and implications. In International Conference Machine Learning, pp.
2023.
Zhong, Fundamental Novel Consistency Theory: H- Consistency Bounds. PhD thesis, New York University, 2025.
14

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
Contents of Appendix
Related work
16
Proof of Theorem 3.2
17
Proof of Theorem 4.1
17
Proof of Theorem 5.1
19
Proof of Theorem 5.2
19
Proof of Theorem 5.3
19
Proof of Theorem 5.4
20
H Proof of Theorem 5.5
21
Proof of Theorem 5.6
22
15

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
A. Related work
In binary classification, zero-one misclassification loss may not always serve as an appropriate evaluation metric, particularly in scenarios where more complex metrics are better suited the problem. For instance, in scenarios with significant class imbalance. which frequently arise in applications such as fraud detection, medical diagnosis, and text retrieval (Lewis, 1995b; Drummond & Holte, 2005; He & Garcia, 2009; Gu et al., 2009), metrics like the F3-measure (Lewis, 1995a; Jansche, 2005; Ye et al., 2012) 2) and the AM measure (Menon et al., 2013) are commonly used. Similarly, weighted accuracy is often used to address the asymmetrical costs associated with different classes in real-world applications. However, optimizing these generalized performance metrics introduces both computational and statistical challenges, as they do not conform to the standard single-loss expectations commonly used for analyzing surrogate loss functions in machine learning (Steinwart, 2007).
Research on the design of algorithms for specific instances of such metrics or the general family has largely focused on the characterization of the Bayes-optimal classifier. For the standard zero-one binary classification loss, it is known that the Bayes classifier can be defined as x - (1))( })), where ()x) is the probability of a positive label conditioned on x. A similar characterization applies to the weighted zero-one loss (Scott, 2012), where the threshold corresponds to a weight different from 1. For imbalanced metrics, Ye et al. (2012) characterized the Bayes-classffier for the F meeeusee while Menon et al. (2013) characterized the Bayes classifier for the AM measure as I H sign(n(>)) - 5²)) for some 8* E (0, 1). These results were later generalized by Koyejo et al. (2014) to broader family of metrics that can be formulated as a ratio of two linear functioos of true positive (TP), false positive (FP), true negative (TN), and false negative (FN) statistics. This metries includes the aforementioned weighted accuracy. F'g "gg-masures, the AM measure, as well as the Jaccard similarity coefficient (Sokolova & Lapalme, 2009), among others. Existing algorithms for optimizing these solution (Koyejo et al., 2014; Parambath et al., 2014). These
family of
metrics heavily rely on the structure of the methods generally adopt a two-stage approach: first estimating the conditional probability n)(r) and then searching for a suitable threshold 8* specific to the metric.
In particular, Koyejo et al. (2014) study a general family of performance metrics, including the Fg-measure, AM measure, Jaccard similarity coefficient (JAC), and Weighted Accuracy (WA). These metries can be expressed as the ratio of two linear combinations of four fundamental classification quantities. The authors propose two relatively simple algorithms. Their first algorithm consists of training a standard binary classifier such as logistic regression to return a real-valued predictor h. Next, a threshold 0 is chosen to maximize the empirical L-measure for binary classifier x + sign(h(z) f), where I. represents the metric of interest. The authors do not discuss how to find f but presumably this can be done via cross-validation based on a grid, or by binary search over all possible values. Their second algorithm consists of training for each fixed value of a cost-sensitive logistic regression (or other margin-based algorithm) with weights and (1 - O) and return he. Then, they find to maximize the empirical L-measure for the binary classifier x (gg(hh(x)) The authors provide a consistency-type guarantee for these two-stage algorithms. Parambath et al. (2014) address the specific case of the F meaeuaueee Their al algorithm coincides with the second algorithm of Koyejo et al. (2014). However, the authors also suggest returning sign (x) 0') where both 0 and 0' are selected to maximize the L-measure. The authors provide a stability-type guarantee for their method, although the analysis lacks explicit details.
These algorithms naturally come with consistency guarantees (Zhang, 2004; Bartlett et al., 2006; Steinwart, 2007; Koyejo et al., 2014; Mohri et al., 2018). However, consistency is an asymptotic property and does not provide explicit convergence rate guarantees. Moreover, it applies only the overly broad class of all measurable functions, making it less relevant in practical scenarios where learning is constrained to restricted hypothesis class (Long & Servedio, 2013; Zhang & Agarwal, 2020; Awasthi et al., 2021 a;;; 2023; 2024; Mao et al., 2023d;caa;b;;; Zheng et al., 2023; Mao et al., 2024a,bxe:h:::ddggr Mohri et al., 2024; Cortes et al., 2024; 2025; Mao et al., 2025; Mao, 2025; Montreuil et al., 2024; 2025d;a;b;;; Zhong, 2025).
Other related work on generalized metrics includes studies on surrogate regret bounds (Reid Williamson, 2009; Kotlowski & Dembezyáski, 2016), extensions of the plug-in rule (Ye et al., 20 Dembezynski et al., 2013; Narasimhan et al., 2014; Lipton et al., 2014; Dembezyáski et al., 2017; Yan et al., 2018; Tavker et al., 2020; Berger & Guda, 2020), and structural loss optimization (Joachims, 2005; Kar et al., 2014; Yu & Blaschko, 2015; Eban et al., 2017: Berman et al., 2018: Bao & Sugiyama, 2020). Additionally, various optimization approaches have been explored, including online optimization (Kar et al., 2014; Zhang et al., 2018; Kotlowski et al., 2024; Busa-Fekete et al., 2015) and constrained optimization (Narasimhan et al., 2019). Further extensions address multi-class classification and multi-label learning (Dembezynski et al., 2013; Narasimhan et al., 2015a; Ramaswamy et al., 2015; Narasimhan et al., 2015b; 2016; Cheng et al., 2016; Natarajan et al.,
16

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
2016; Sanyal et al., 2018; Fathony & Kolter, 2020; Zhang al., 2020; Luo al., 2021; Busa-Fekete al., 2022; Schultheis al., 2024), well generalized metries under missing, corrupted, noisy labels (Menon et al., 2015; Natarajan & Jain, 2016; Zhang et al., 2021; Zhang & Agarwal, 2024). Theoretical analyses and algorithms have also been developed for specific metrics, including the F- F-measure (Jansche, 2007; Jasinska et al., 2016; Pillai et al., 2017; Bascol et al., 2019; Jiang et al., 2020; Berger Guda, 2020; Zhang et al., 2020; Dai & Li, 2023), fairmess measures (Menon & Williamson, 2018), 8), precision-recall (Flach Kull, 2015), and the balanced error rate (BER) (Zhao et al., 2013).
B. Proof of Theorem 3.2
Theorem 3.2. Fix 0 and h e H. Then, the inequality Egx (h) in holds if and only of (3)) (t
Proof. Since we have (4),))
0, the following equivalence holds for all h e H. and 1) 0:
(hx Sn = E
la (a 2, X
E (#.))
[ x, v)l
(def. of (*))
(xy))-
Elas)) (h, s
"
E Dea
L(h) L (H)
7
(A* = (H))
This completes the proof.
C. Proof of Theorem 4.1
We will use the following definitions. For any i e X, we adopt the definition 77)) = P(Y = +1 X = x). Then, the conditional loss of a hypothesis h at point a X for loss function & defined as follows:
(()),) + + (1),(
The best-in-class conditional loss of hypothesis set H at x X is defined by e, xX,, inf Co(h,
Lemma C.1. Assume that the following H-connsssenccy bound holds for all h H and all distributions:
Ela (h) Ei,,, (H) Me. (H) (h) Eg (3) (Y))...
Then, for any 17 [0, and E X, we have
f0-1h, x, +1)m -1-1-,,)
- - -))
heti
(((((()))))+((((())))) (((
inf hest
Proof. For any x X, consider distribution & that concentrates on that point. Let 1) PPYY +1| X x)). Then, by definition, Elo., (h) E7 (H) + Me.. (H) can be expressed as
Eea (h)- (00)+M,,,.0. p- (3() fo-1 +1)m+ -1) 7)- inf ( +1)m lo 60-1(,,2 -1) 1))-
heft
Similarly, & (h) E (J) + Mo (H) can be expressed as
<hh()))) (-
inf (n))))i((((((())))))))))) (((()))))+()(()))))))))))))))))) ((-M()))1--)) heft
Since the H-consistency bound holds by the assumption, we complete the proof.
Theorem 4.1. Assume that takes values in [0, Lmax]. Let K. be regular hypothesis set and margin-based loss function for the binary zero-one loss function fo-1. Assume that & admits ---H-consistency bound with respect to lo-1 for function T:t + Bt", with e (0, 1] and > 0. Then, Ls admits T-I--consistency bound with respect to L, where T(t) = (max)
1- 10000
17

---

Principled Algorithms for Optimizing Generalized Metries in Binary Classification
Proof. Let n(x) P(Y x| = =) be the conditional probability of Y given X x. By the definition, the conditional
loss of the target loss be expressed follows:
2h) = (
= 1atp:l/||||001010//0000140411110
= [b4t11+-HH100++44000000001111110
where d(x)
e [0,2Lmax] and
n/ (x) ((B3(clai)e((((()))((+-)))))>>)0 [0.1] c(x)
Thus, the best-in-class conditional
can loss can be expressed follows:
C[(H(,))= = inf [co-1 (h, 2, 10-1 -
hefk
By the definition,
2 x)(, - ej x))
[[oo-1 -1),,) t0- (1)) inf 10 beel
The conditional loss of the surrogate loss can be expressed as follows:
CL. 2h) + [t000//|||hhaaarkkk/o///////o/aa
= o|c"13|||||HH.ae....3.3..1..0113
=
Thus, the best-in-class conditional loss can be expressed as follows:
ei, ()) inf
By the definition,
(h,
= 2h, et, (H,x)
By Lemma C.I, we have
AlL,,i(h,2)
2 1-1
he* -
1/ c(x)
3d
inf (a "()))))
(c(t))
hele 1
(ACL.X (h, x)) ( (2
2
8#
By taking the expectation on both sides and applying Jensen's inequality, we obtain:
(h( (3C) + Mr (96) T(EL. (h) - Ei. (91) + Mro (9().
where T(t)= (32 Lmax) 1-0,a
18

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
D. Proof of Theorem 5.1
Theorem 5.1. We have (H)) and, for any X IR, sign( E (3)) sign(A-
Proof. For any e Ht, define fh) and g(h) to simplity notation:
B(aw))D (h, x.]] f(h)
9(h)= E (c
E (x,))) ( (h, v. y)]
(x.z)-
By assumption, we have g(h) > 0 for all h E H and X infnene f(h) and ()( inf ne (f((h))**)(() (h)) Since upper-bounded by lo and (f(h) X*) 2 0, follows that
Ejx- (H) s inf (.( -- 23
hell
By definition of (30) as infimum, for any 7) O, there exists f,, E HC such that
E (9() + (f(h)) X² (h,,) 2 O.
Since (H) 17 0 for all y O, it follows that (H) 2 0. Combining the two inequalities yields (H) 0. This establishes the first equality.
Next, assume X A -. O. By the definition of X as an infimum, we have f(h) - for all H. This implies E/ (H) inf hert ((((h) -)) Lg inf - {)} (x A) 0, thus (H) O, which proves one direction of the statement.
Now, assume X - À < O. By the definition of X as infimum, for any 17 0, there exists h, H such that f(,,) X* + 17 Choose < (A- X²). This implies Ex (IC) (f(h,)) (X*+77>)gg(t)) A)g())) Since (X* + A) < 0 and g(,,) 0. it follows that E/ (H) < O. This proves the other direction.
E. Proof of Theorem 5.2
Lemma E.1. Fix and assume |X X+1 c. Then, the following inequality holds:
Ez (Ht) s elg.
Proof. By definition of Era (h), the following holds for any h E JC:
Ee (h) (h) (X* A) E (2.0)-
(h,,,,,,11) Exx-(1) + cla.
Thus, by definition of Eg (H) infimum, for any h H, we have (3) S (h) Elg. Taking the infimum of the right-hand side over H yields Ejg (IC) s (Ht) + elg. By Theorem 5.1, we have (HH) = O. This completes the proof.
Theorem 5.2. Let be fixed. Algorithm 1 returns an e-approximation X of X* in Ologz( )mme))-in) )) time, such that the following property holds:
Eg (H) (H) + el, =l
Proof. By definition of the binary search, we have A < 6. Thus, the inequality holds by Lemma E.1. The time complexity follows straightforwardly the property of the binary search.
F. Proof of Theorem 5.3
Theorem 5.3. Assume that the surrogate loss L. admits a I-M--cosiittency bound with respect to l. Then, for any > O, with probability at least 1-6 over the draw of a sample from D the following estimation bound holds for an empirical minimizer fig H of the Lg over S:
E,p (Tss) 87 (Ht) r ML. (3) 49r2) (F() 2Bx
log 3 2m
19

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Proof. By the standard Rademacher complexity bounds (Mohri et al., 2018), the following holds with probability least 1- 8 for all h HC
LL (h) ( 2 (H) + BAV log(2/6)
20m
Fix e > 0. By the definition of the infimum, there exists h² H such that ÊLD (h*) s Ei, (30) + By definition of ìx we have
EL. (Nix) EL, (H)
EL (hx) )- LL. (Tix) ELo
EL, (H)
LL (mx) EL..S (T1x) SL..s(1i E (H)
LLO (hx) ELo.s (fix) ) EL (h")
E (h") +
< 2 2 (IC) + BA log(2/8)
+
2m
Since the inequality holds for all 0, it implies:
(Tss) (H) S 49h, (HH) 2B,
log(2/5)
2m
Substituting this inequality into the H-consistency bound in the assumption completes the proof.
G. Proof of Theorem 5.4
Let Bg be an upper bound for the function This boundedness holds in practice when we consider bounded input space. Lemma G.1. Fix > and assume A^ >2l S e. Then, the following inequalities hold:
4max,|2/[ppe m
Ri (JC)= (30)
[Bx; -Bxal s 4mx
Proof. Let L be the surrogate loss (6) with the parameter A. By the definition of the cost function (4), the following holds for any (h, y) JC Xx
1 (h, y) (h, x.) max]]3 Aal-
Thus, by definition of Rademacher complexity and using Bx suph,x,8 La (h,,, we have
4max, |ma
s (3t) - -D422 (J+) S
[Ax, BAal s 3, Boc.
m
This completes the proof.
Theorem 5.4. Assume that the surrogate loss Lt admits a I-H-consistency bound with respect to L., Then, for any ô > O, with probability at least - over the draw of a sample S from D"m, the following estimation bound holds for an empirical minimizer Tig H. of the surrogate loss Lo over S and X [[min, \max]
8 Smax,|Bp [B/LB + 2Bx 4mxx:13|BB.
V
log 253
+ ts
Eea (rs)) E7x & T ML. (90) 499, (3C) +
m²²
2m
where AA >max Amin- In particular, when F(t) = 2( 2(Lmax) 2b for + Dioge the bound can be expressed as follows:
Eex Gex(is) - s L2x Mr (9t) + 499 (IF) + Smax, BB
4max,|B.|Ba
Ing 2(AA)
E
2B +
m²
2m
20

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Proof. To derive the uniform bound, cover the interval [Amin Amax] using sub-intervals of size 1/m. Consider sequences (Ak) where A Amin A=1 s m() Amin). ) By Theorem 5.3 and the standard uniform bounds (Mohri et al.,
2018), for any ô O, with probability at least 1 ó, the following bound holds for all k:
Ex. Exe (hs) Ex, (9C) s 1 ML. (9() 4 (3() 2BAB
log 20 2AAaax Aminn
2mp
Then, for any Dminn Amax], there exists & such that Xpl
1. 2m
By Lemma E.1 and Lemma G.I, we obtain
Exa (hsh)) E (36) s T
(TML MLo (30) + 49 (3()+
mmax|
2B +
4
4max/13,BB
log
2(A -Amin on
Eg
m?
m
2m
m
This completes the proof of the first bound. The second bound follows directly by substituting [(t) = 2(Lmax) first bound.
2 into the
H. Proof of Theorem 5.5
Theorem 5.5. Let fmm, For any 8 0, with probability at least 28,"
Algorithm 2 returns (logz (Aums
)) time
hypothesis Tú, that admits the following guarantee:
46m Eg
((hx) s (T() +
Proof. Suppose that Ti is the solution returned at step 10 of Algorithm 2. Then, by definition of the algorithm, we must have EEgx (fx)] S Ens which, by the standard generalization bound (Mohri et al., 2018), implics that (with high probability)
Ee (fx) $ 2cm
Expanding the definition of the surrogate risk, this gives
(h, x, y)1 A 2em
Dividing through by B[La(h, v)] yields
sA+ 20m B(Es(h,z, Lo
2
((TN) S
77)
Next, observe that for all h H. we have
( (A- Ex)))))()
Rearranging gives
(A x²= Eer (e) (1) E[Co(h, xr,
Since Ey)+(H)= = 0, by definition of the infimum, it follows that Ex. (h) O. In view of that, we can write:
Ex (h)
(A- E[l x, x,,
Applying this inequality with h Fex and substituting into (7), we obtain
26m
E (Tx)
X 46m
((Tx)s x
Lg
E (Tx,
Lg
This ends the analysis of that case.
21

---

Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Now, consider the where the algorithm terminates with lb al $ cm- In this case, have (with high probability) A s. By Lemma E,1, this implies
Ez (H) eLgg
Combining this with the estimation bound for es we have (with high probability)
Eạa (hx) (H() cm 1 cl 6m.
Thus,
clg cm
Dividing by ELLg (xx,,,)) both sides yields
d2 cn
dg + Cm
(as) s At
sX +ct
Lg
Lg
Choosing (2lg)))) yields
(hs) s +
Elz dlg+ cm
sx
6m
3mm 5x +
2cm Lg
Lg
22.
2L.
This completes the proof.
Proof of Theorem 5.6
Theorem 5.6. For any 8 O, with probability at least 1 - 8, f fm, hypothesis hú, that admits the following guarantee:
Algorithm 3 returns in O ( time 26,"
2cm Lg
((hx)
Proof. Since the algorithm terminates with + ic we have A s c. By Lemma E.1, this implies
E (H) elag.
Combining this with the estimation bound for e*, we have (with high probability)
Ega (Tix) s Epx (H) em S Eha + cm-
Thus,
2 (h,, clg + cm
Dividing by E[E3 both sides yields
am+tm
dlg + 6m Lg
(hs s
X2 +ct
Lg
Choosing (2lg) yields
Elg + 6m
3cm
5 x + 2
La,e(hx) s A
x*
&g
21
21
8
This completes the proof.
22


Reviews:
[{"review_id": "WKtHKnEhuT", "reviewer": "Reviewer_TFXy", "summary": "This article introduces a novel optimization approach for generalized metrics in binary classification. The primary method involves converting the fractional form into a summation form. However, the method introduces a parameter, $\\lambda$, whose optimal value is unknown and requires estimation, indicating that cross-validation may be necessary to identify the appropriate parameter.\n\n### update after rebuttal\n\nThe authors have provided explanations for the theoretical technical details I raised and discussed the limitations of their approach. They have also clarified aspects of their experimental design and incorporated relevant discussions of the literature I suggested.\n\nOverall, I appreciate the theoretical results and motivation behind the authors' proposed method. However, from practical perspective, the approach does have certain limitations, such as the selection of $\\lambda$ and/or the sacrifice of data for cross-validation. Additionally, more comparisons with existing consistency methods in the literature will be better. Nevertheless, I believe this paper is worthy of publication. Therefore, I maintain my current rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "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. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Method:** Thank you for the insightful comments. The quantities $\\hat{\\mathcal{E}} _{\\ell^{\\lambda}}$ and $\\hat{h}$ are approximated using data sampled from the same distribution, but they can be obtained from different samples. In practice, as done in Koyejo et al. (2014), we can split the training data into two parts: $\\hat{\\lambda}$ is obtained from one part, and then used to train the hypothesis $\\hat{h} _{\\hat{\\lambda}}$ on the other.\n\nTheorems 5.4 and 5.5 remain valid as long as the data are sampled independently from the same distribution. Regarding your observation: in the case of an overparameterized model, it is true that $\\mathcal{E} _{\\ell^{\\lambda}}(\\hat{h} _{\\lambda}) \\leq 2\\epsilon_m$ still holds by the standard generalization bound (Mohri et al., 2018), but the value of $\\epsilon_m$ may be larger due to the high complexity of the model. As you correctly noted, $\\epsilon_m$ becomes small only when the sample size is sufficiently large relative to the complexity of the hypothesis set. This limitation applies broadly to most generalization bounds for complex neural networks.\n\nThe current analysis of overparameterized settings typically requires alternative tools, particularly those that account for the optimization algorithm (e.g., SGD) and its dynamics. Such analyses often apply only to more restricted model families.\n\nWe will elaborate on these points and revise the presentation of Algorithms 2 and 3 for improved clarity in the final version.\n\n**2. Experiments:** Thank you for the valuable suggestions. As indicated on line 435 (left), we used the METRO Algorithm 3 in our experiments. We will follow the reviewer’s recommendation to add more details about the datasets and include additional experimental results using alternative models in the final version. We also plan to incorporate experiments on more imbalanced datasets, as suggested by Reviewer wfsZ.\n\n**3. Relation To Broader Scientific Literature:** First, we should emphasize that the guarantees for these methods differ fundamentally. Our METRO algorithms for optimizing general metrics are backed by strong theoretical guarantees that apply to arbitrary hypothesis sets and include finite-sample bounds. In contrast, prior methods (Koyejo et al., 2014) provide only Bayes-consistency guarantees, which hold solely for the class of all measurable functions and offer no convergence bound. Moreover, their approach lacks convergence rate guarantees for parameter tuning, unlike our finite-sample bounds.\n\nBeyond these theoretical advantages, a key limitation of prior methods is their dependence on the structure of the Bayes-optimal solution. Since the Bayes-optimal predictor for a given metric often differs from binary classification only by an offset, their approach first trains a binary classifier and then selects an optimal threshold or offset. However, this strategy fails when the best predictor within a restricted hypothesis set does not align with the Bayes-optimal form (see Figure 1). Consequently, irrespective of parameter estimation or tuning, their approach does not succeed in general, as our example illustrates.\n\nIn contrast, our approach and algorithms provide convergence rate guarantees for arbitrary hypothesis sets and do not rely on the specific form of the Bayes-optimal solution, ensuring robust and theoretically grounded optimization.\n\n**4. Essential References Not Discussed:** We thank the reviewer for pointing out these relevant references on optimizing the F-score. They are indeed closely related to our work, and we will be sure to include and discuss them in the final version.", "claims_and_evidence": "Yes, the method has been validated through both theoretical analysis and experimental results. I have included some comments in the following comment boxes.", "methods_and_evaluation_criteria": "### **Method**\n\nOverall, the methods presented in the article are motivated by several theorems, primarily Theorem 3.1 and Theorem 5.1, which I find to be a particularly interesting aspect of the work.\n\nI would like to double-check the estimation of $\\lambda$ using the proposed method.\n\nIn both Algorithms 2 and 3, $\\hat{\\mathcal{E}_{l^{\\lambda}}}$ and $\\hat{h}$ are estimated based on the same dataset, will this approach be effective?\n\nMoreover, is it valid to derive the result of Theorems 5.4 and 5.5? I can understand if the data were different.\n\nSpecifically, in the proof of Theorem 5.4, \n\n$$\n\\hat{\\mathcal{E}_{l^{\\lambda}}}(\\hat{h}) \\leq \\epsilon,\n$$\n\nimplies \n\n$$\n\\mathcal{E}_{l^{\\lambda}}(\\hat{h}) \\leq 2\\epsilon.\n$$\n\nConsider the case of an overparameterized model $h$ such that $\\hat{\\mathcal{E}}_{l^{\\lambda}}(\\hat{h})$ is pretty small; \n\nbut, in this scenario, it appears that $\\mathcal{E}_{l^{\\lambda}}(\\hat{h})$ could still be large.\n\n### **Experiments**\n\nThe experimental section could be improved.\n\nSome statements lack clarity; for instance, it is unclear whether the METRO Algorithm ultimately employs Algorithm 2 or Algorithm 3. Additionally, since the datasets are generated from multiclass datasets into binary datasets, providing more details would be beneficial.\n\nThe model only utilizes a three-hidden-layer CNN with ReLU activations; incorporating additional models could enhance the overall convincingness of the results.", "theoretical_claims": "I reviewed the proofs of Theorems 3.1 and 5.1, as well as part of Theorem 5.4. \n\nTheorems 3.1 and 5.1 are correct; \n\nI have posed some questions regarding Theorem 5.4 in the previous comment box.", "experimental_designs_or_analyses": "The experimental design is reasonable, but it could be further improved or clarified. Please refer to the detailed comments in the previous comment box.", "relation_to_broader_scientific_literature": "I do not fully understand why the proposed method outperforms Koyejo et al. (2014). Both approaches theoretically present correct methods with an additional parameter; it seems to me that the difference lies primarily in how this parameter is tuned. I currently cannot grasp why the proposed algorithm has an advantage in tuning this parameter.", "essential_references_not_discussed": "The paper systematically discusses the literature, and I would like to add few references.\n\n### Bayes-rule for F-score\n\nJansche, M. (2007, June). A maximum expected utility framework for binary sequence labeling. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics (pp. 736-743).\n\nDai, B., & Li, C. (2023). RankSEG: a consistent ranking-based framework for segmentation. Journal of Machine Learning Research, 24(224), 1-50.\n\n### Threshold study for F-score\n\nLipton, Z. C., Elkan, C., & Narayanaswamy, B. (2014). Thresholding classifiers to maximize F1 score. arXiv preprint arXiv:1402.1892.", "other_strengths_and_weaknesses": "N.A.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "N.A.", "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": "zLi0KpAZKw", "reviewer": "Reviewer_wfsZ", "summary": "This paper proposes METRO for generalized metric optimization in binary classification. The authors reformulate metric optimization as a generalized cost-sensitive learning problem, and introduce a new family of surrogate loss functions. They theoretically prove the $\\mathcal{H}$-consistency guarantees for theses losses and develop finite-sample learning bounds for the proposed algorithm. Experiments  on image classification demonstrate that their algorithm outperforms other baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Weaknesses: The experiments were limited to the classic image classification task. Algorithms were not applied to scenarios such as significant class imbalance, which is a fundamental motivation for this paper as stated in Section 1.**\n\n**Response:** Thank you for the valuable suggestion. Following previous work, we used standard image classification datasets for our empirical evaluation to demonstrate the effectiveness of our methods compared to prior baselines. However, we agree that evaluating our algorithms on more imbalanced datasets would be beneficial, and we plan to include such experiments and comparisons in the final version.\n\n**2. Questions: I am curious about how the runtime of the proposed method compares to other baselines.**\n\n**Response:** The per-epoch computational cost of our method is comparable to that of Algorithm 2 in Koyejo et al. (2014). Both methods involve a single hyperparameter, and for a fixed value of this parameter, the computational cost is similar to training a standard binary classifier using a standard surrogate loss. We will include a more in-depth discussion of this topic in the relevant section of the paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Proofs seem correct to me.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The proposed framework can be used to design algorithms with finite-sample learning bounds, unlike Bayes-consistency.", "essential_references_not_discussed": "I am not very familiar with Bayes learning and related works are well discussed as far as I am concerned.", "other_strengths_and_weaknesses": "Strengths \n1. The motivation and the introduction to the generalized metrics optimization framework are clear.\n2. The reformulation of generalized cost-sensitive learning and the derivation of finite-sample learning bounds seem novel to me.\n\nWeaknesses\n1. The experiments were limited to the classic image classification task. Algorithms were not applied to scenarios such as significant class imbalance, which is a fundamental motivation for this paper as stated in Section 1.", "other_comments_or_suggestions": "See Questions.", "questions_for_authors": "I am curious about how the runtime of the proposed method compares to other baselines.", "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": "DArwQsoFnx", "reviewer": "Reviewer_dynv", "summary": "This paper studies the problem of optimizing a broad class of metrics used in class imbalance or class asymmetric scenarios. Previous approaches rely on threshold-based methods that approximates Bayes-optimal classifiers with guarantees of consistency which is asymptotic. This paper first shows that optimizing such kind of metrics can be interpreted into the problem of optimizing an alternative cost-sensitive loss, provided an oracle access of the loss value of the best hypothesis in hypothesis set. The authors then shows that the cost-sensitive loss of the above form can all be optimized with non-asymptotic theoretical guarantee via the technique of surrogate loss. Meanwhile, the oracle access required to compute the loss can also be relaxed by leveraging binary search using Rademacher bounds as separating condition. Experimental results show the effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their strong support of our work. Below please find responses to specific questions.\n\n**1. Questions: The authors propose to leverage Rademacher bounds, which can be approximated via classical learning process such as ERM. I am curious on the inherent difficulty in the metric optimization step (i.e., finding $\\lambda^\\*$) in this paper. For example, is metric optimization at least as difficult as supervised learning multiple times with alternative losses that are independent of the metric learning process? Anyway, the answer to this question may not let me increase my evaluation to this paper, since it cannot be increased anymore.**\n\n**Response:** This is a natural question. The reviewer is asking about the difficulty of directly optimizing a general metric defined as the ratio of the expectations of two loss functions, both linear in ${\\mathsf h}$, where ${\\mathsf h}(x) = \\text{sign}(h(x))$.\n\nWhile the metric is quasi-concave in ${\\mathsf h}$, its optimization with respect to $h$ is NP-hard (even with a constant denominator), even for a linear hypothesis set. In contrast, each surrogate loss optimization problem we consider (framed as supervised learning) can be solved in polynomial time over a convex hypothesis set, as the surrogate loss functions we adopt are convex.\n\nMoreover, directly optimizing the empirical ratio of the numerator and denominator may not yield a provably good approximation of the metric, since their expectation does not align with the ratio of expectations.\n\nWe will include this discussion in the final version. If our interpretation of the reviewer’s question is incorrect, please clarify, and we will be happy to address it.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The authors propose a novel approach to deal with class-imbalanced and cost-sensitive binary classification problems, which is fundamental in many other literatures.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "- Strength: The problem investigated in the paper is fundamental. The solution is intuitive and make sense, and specifically, using Rademacher bounds to make binary search for metric optimization is a nice idea. The structure of the paper is clear, each section covers a relatively self-contained step. \n- Weakness: I do not have concern on weakness.", "other_comments_or_suggestions": "No.", "questions_for_authors": "(1) The authors propose to leverage Rademacher bounds, which can be approximated via classical learning process such as ERM. I am curious on the inherent difficulty in the metric optimization step (i.e., finding $\\lambda^*$) in this paper. For example, is metric optimization at least as difficult as supervised learning multiple times with alternative losses that are independent of the metric learning process? Anyway, the answer to this question may not let me increase my evaluation to this paper, since it cannot be increased anymore.", "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 introduces a novel method for optimizing generalized metrics in binary classifications. The theoretical foundation is backed by H-consistency and uniform convergence results. Additionally, the proposed method demonstrates strong empirical performance across various datasets.

Overall, the reviewers have provided consistently positive feedback regarding this paper, and I recommend its acceptance. Nevertheless, the authors are strongly encouraged to include all necessary details in their rebuttal in the final version.
Decision: Accept (poster)