Learning to Reject Meets Long-tail Learning
Authors: Harikrishna Narasimhan
Aditya Krishna Menon
Wittawat Jitkrittum
Neha Gupta
Sanjiv Kumar
Venue: ICLR 2024 spotlight (2024)
Keywords: Learning to reject
balanced error
evaluation metrics
selective classification
plug-in approach
long-tail learning
class imbalance
non-decomposable metrics
Primary area: learning theory
TL;DR: Theoretically-grounded approach for learning to reject with general evaluation metrics including the balanced and worst-group errors

Abstract: Learning to reject (L2R) is a classical problem where one seeks a classifier capable of abstaining on low-confidence samples. Most prior work on L2R has focused on minimizing the standard misclassification error. However, in many real-world applications, the label distribution is highly imbalanced,  necessitating alternate evaluation metrics such as the balanced error or the worst-group error that enforce equitable performance across both the head and tail classes. In this paper, we establish that traditional L2R methods can be grossly sub-optimal for such metrics, and show that this is due to an intricate  dependence in the objective between the label costs and the rejector. We then derive the form of the Bayes-optimal classifier and rejector for the balanced error, propose a novel plug-in approach to mimic this solution, and extend our results to general evaluation metrics. Through experiments on benchmark  image classification tasks, we show that our approach yields better trade-offs in both the balanced and worst-group error compared to L2R baselines.

Published as a conference paper at ICLR 2024
LEARNING TO REJECT MEETS LONG-TAIL LEARNING
Harikrishna Narasimhan, Aditya Krishna Menon,
Wittawat Jitkrittum
Neha Gupta, Sanjiv Kumar
Google Research
(hnarasimhan, adityakmenon, wittawat, nehagup, sanjivkH@goolee.co
ABSTRACT
Learning to reject (L2R) is a classical problem where one seeks a classifier capable of abstaining on low-confidence samples. Most prior work on L2R has focused on minimizing the standard misclassification error. However, in many real- real-world applications, the label distribution is highly imbalanced, necessitating alternate evaluation metrics such as the balanced error or the worst-group error that enforce equitable performance across both the head and tail classes. In this paper, we establish that traditional L2R methods can be grossly sub-optimal for such metrics, and show that this is due an intricate dependence in the objective between the label costs and the rejector. We then derive the form of the Bayes-optimal classifier and rejector for the balanced error, propose novel plug-in approach to mimic this solution, and extend our results to general evaluation metrics. Through experiments on benchmark image classification tasks, we show that our approach yields better trade-offs in both the balanced and worst-group error compared to 1.2R baselines.
INTRODUCTION
Multi-class classification is typically framed as learning classifier that can provide accurate predic- tions on any test sample. However, in many weal-world problems, it may be preferable to allow the classifier to abstain from making a prediction on low-confidence samples. Learning to reject (L2R) is the problem of learning such a classifier capable of abstaining certain samples, at the expense of incurring a fixed cost (Bartlett et al., 2006; EI- Yaniv Wiener, 2010; Cortes et al., 2016; Gangrade thresholding strategies which pose the problem as an instance of
et al. 2021: Cortes et al., 2023). Common L2R approaches include confidence-bast or Chow's 's rule (Chow, 1970), and cost-sensitive learning (Cortes al., 2016; Ramaswamy al., 2018; Ni et al., 2019; Mozannar & Sontag, 2020; Charoenphakdee et al., 2021; Verma & Nalisnick, 2022; Mao et al., 2023a).
Most prior studies on L2R have focused on the goal of minimizing the standard misclassification error. However, the misclassification error may not be well-suited to evaluate the performance of classifier when the label distribution is highly imbalanced long-tailed (Buda et al., 2017). In such applications, one often employs evaluation metrics such as the balanced error (Brodersen et al., 2010) or the worst- worst-group error (Sagawa et al., 2020), which enforce equitable performance across different label groups (e.g.. head and tail). This raises natural, but surprisingly under-explored question: what is an appropriate L2R mechanism for such generalised evaluation measures?
In this paper, we present a formal study of the problem of L2R with general evaluation metrics. In the standard classification setup, one typically minimizes a given evaluation measure by formulating an equivalent cost-sensitive problem (Menon et al., 2013; Koyejo et al., 2014). For example, with the balanced error metric, one may re-weight the per-elass errors by the inverse class priors. Similarly, many commonly used classification metrics can be reduced to minimizing cost-sensitive error with fixed label costs (Narasimhan et al., 2015b). However, applying these reduction techniques to the L2R setup is not straightforward. In particular, even with metric as simple as the balanced classification error, the resulting label costs are no longer constants, and have an intricate dependence on the rejection mechanism. We characterize the optimal solution for this non non-trivial formulation, propose novel plug-in approaches to mimic the solution, and demonstrate their efficacy in experiments.
In summary, we make the following contributions:

---

Published as a conference paper at ICLR 2024
Table 1: Summary of Bayes-optimal classifier h" and rejector r" for different metrics. We assume cost abstention. With the standard 0-1 error (row 1) and the conditional 0-1 error (row 2). the optimal rejector is a thresholding of the true class ttass-probabiligg of the predicted label. With the balanced error (row 3), the rejector takes fundamentally different form, and involves all class class-probabee probabilities, with per-class coefficients E It* that distribution-depene dependent. With general evaluation metric such as the worst-group emror (row 4), have stochastic comhination of multiple classifier-rejector pairs.
L2R Risk
ht (a)
r' (a)
Reference
Standard (I)
arg m (2)
maxy (1) <
Chow (1970) Lemma 8 (App. C)
Conditional (22)
arg max, (z)
maxy 7h (xx) <1-6
Balanced (6)
arg max, My ny (2) maxy My (z) < Σ, U/ n7 (2)
Theorem
Generalized (14)
Stochastic combination of (h pairs of the form in 3
Theorem: 3
0.6
Cheafenik nul
Congitional Hoad Erry
0.4
Choare rale
Choar's mile (Dwlaneed
0.8
Baleeeed Enee
Plagon (Woon)
Plupin [lwkenced]
0.3
Plap-is (islanzed)
Plageis Wond)
Plug-in (Wirm))
3.44
0.5
Chows
0.3
Conertonn
0.4
Plugin (Balanced
(Wors]
0.2
2.2
0.1
0.1
0.0
0.0
0.0
0.0
0.8
Proportion Bejuctions
Progetiion Dejections
Propention Dejections
Proper rion Dajection
(b)
(c)
(d)
Figure I: Comparison of balanced eгror as a function of proportion of samples rejected on the ImageNet-LTT dataset. We compare Chow's 's rule with the proposed plug-in in methods. We also include plots of the individual head and tail errors, and the differences between them. We designate classes with 20 or fewer samples in the training set as "tail" classes, and the remaining as "head" classes. The base classifier uses a ResNet-50 architecture. Chow's 's rule is seen to be substantially better on the head group compared to the tail group. In contrast, the proposed plug-in rules yield significantly lower balanced (worst-group) error. They also seen to yield a lower gap between the tail and head errors.
(i) We first derive the Bayes-optimal classifier and rejector for the balanced error metric, and show that they have fundamentally different form from classical baselines such Chow's rule (Chow, 1970), which reject samples with low prediction confidence ($3, Table 1, Theorem 1).
(ii) We show that vanilla modifications to Chow's rule such as changing the loss used in the base model training are also theoretically sub-optimal for the balanced error. As an alternative, we propose a novel plug-in in approach that seeks to mimic the Bayes-optimal solution without making any changes to the base model training ($4).
(iii) We then extend our Bayes-optimal characterization to any evaluation metric that can be expressed as general function of the per-class errors (Theorem 3), and as concrete example, showcase how to extend our plug-in approach to minimize the worst-group error ($5).
(iv) Through experiments on benchmark long-tailes image classification datasets, we demonstrate that our plug-in approach yields significantly better trade-offs than Chow's rule, and is competitive with variants of Chow that require changes to the training process ($6).
2 LEARNING TO REJECT AND LONG-TAIL CLASSIFICATION
We begin with some background material. Let X be an instance space, y y [L] =
L} be
the label space, and be the underlying distribution over X x y. Furthermore, let n1 (x) Py x)) denote the conditional distribution over labels. Given a training set S {(In, yn. ) hn comprising N i..dd draws from F. multi class classification canonically seeks classifier h: X y with low misclassification error Ro-1 (h) = P(y * h(z)). We may parameterise h(z) = arg max ey for (z) for scorer f: X R.,, which is typically trained by minimizing an empirical surrogate risk on S.
2.1 LEARNING TO REJECT
We are interested in settings where the classifier is provided the option of abstaining on select samples. To this end, we consider the goal of learning a classifier h: + y and a rejector r: X + {0. 1}. For given instance v, abstain sample whenever r(x) 1, and predict h(x) otherwise.
2

---

Published as a conference paper at ICLR 2024
Prior literature has explored minimizing the standard misclassification error with a constant penalty for abstaining on a sample (Cortes et al., 2016):
R (h, r) P (y + M(x), r(x) = 0) + c.
(1)
Intuitively, when r chooses not to abstain, we incur the usual misclassification error; otherwise, we incur the cost > Under mild distributional assumptions, this objective can be equivalently seen as constraining the proportion of abstentions to be within budget, a formulation often referred to as selective classification (Geifman EI- Yaniv,, 2017; Gangrade et al., 2021). More precisely, via a I Lagrangian analysis (following, e.g., the Keyman-Pearson lemma (Neyman & Pearson, 1933)), for any such abstention budget, there exists an equivalent cost e Eq. (1); see Appendix B for details.
Bayes-optimal L2R. The Bayes-optimal solution for Eq. (1) admits intuitive form:
h" (x) argmax My (z));
(z) =1
max Tly (a) < 1 vE(L.
(2)
vE(
The classifier abstains whenever the maximum conditional probability falls below certain threshold, and otherwise, predicts the class with the maximum class probability.
Post-hoc L2R. A classical baseline for L2R, often dubbed as Chow's rule (Chow, 1970), seeks to mimic the rejector in Eq. (2). In practice, one may implement Chow's rule by training scorer f: + TR to minimize the softmax cross-entropy (CH) loss:
(a. (v, fx))) B(2 [log] [Evel c - fy(z)].
(3)
One then uses the learned scorer to compute estimates Py (a) exp(fp (x)) of the class probabilities 1g (z), and constructs the rejector by thresholding the maximum probability max, (y(x) at 1 c.
Loss-based L2R. As an alternative to Chow's rule, which constructs rejector post-hoc given an existing classifier, the literature has also explored the design of loss functions that jointly learn both the classifier and rejector to optimize the L2R risk (Cortes et al., 2016; Geifman & El-Yaniv, 2017; Ramaswamy et al., 2018; 8; Ni et al., 2019; Mozannar & Sontag, 2020: Charoenphakdee et al.. 2021). Of these, Geifman & EI- Yaniv minimize a variant of the L2R risk in Eq. (1) where the classification error is conditioned on non-rejected samples. As shown in Appendix C, the optimal rejector for this conditional risk has the same form as Eq. (2), but uses different (distribution-depeeden) threshold.
2.2 LONG-TAIL CLASSIFICATION
In many real-world applications, the label distribution is highly class imbalanced (He & Garcia, 2009), or long-tailed (Buda et al., 2017). In such setting. one may wish to evaluate performance separately on minority and majority classes. For example, common partitioning of the classes is into head and tail classes, the primary setting of interest in this paper. More generally, let GI...., .......G. C y denote a paritioning of the labels into K disjoint groups, with G, G = 0, Vi + j and UkEiK] y. Let Th = P (y E G denote the proportion of samples belonging to group G The misclassification error for label group G3 can then be measured as P (y & h(x) y E Ga).
A key metric of interest in this setting is the balanced error that computes the average error across label groups (Brodersen et al., 2010; Menon et al., 2013; 2021b):
Rbat
1 K
Σ KE(K]
Σ KE(K]
1 .P + M(x), y E
(4)
K
In practice, one may minimize the balanced error by using a balanced version of the cross-entropy loss, implemented, e.g., through adjustments to the model logits (Menon et al., 2021a). The literature also explores plethora of other techniques to perform well on the balanced error, including data modifications (Yin et al., 2019; Zhang et al., 2019), loss modifications (Cui et al., 2019; Cao et al., 2019; Tan et al., 2020; Jamal et al., 2020; Ren et al., 2020; Wu et al., 2020a; Deng et al., 2021; Kini et al., 2021; Wang et al., 2021), and prediction modifications (Kang et al., 2020; Zhang et al., 2021).
Another evaluation metric of interest is the worst- group error, which is typically minimized through distributionally robust optimization (DRO) (Sagawa et al., 2020; Menon et al., 2021b):
Royst (h) = max P (y
Mxx) 1y y Gk) max KE[K]
P + h(x) y Gt).
(5)
kE K
3

---

Published as a conference paper at ICLR 2024
Beyond the balanced (worst-group) errors, there are many other metries popular in the class imbal- anced literature, such as the F-measure or the G-mean, which can be generally expressed as functions of the confusion matrix (Menon et al., 2013; Narasimhan et al., 2015b). When learning stand-alone classifier, minimizing these can be reduced to a cost-sensitive learning problem with constant lahel costs (Narasimhan et al., 2019). We next that such simple reduction is not possible when jointly learning classifier and rejector in an L2R setup, even with metric as simple as the balanced error.
3 LEARNING TO REJECT WITH BALANCED ERROR
In this paper, we provide formal framework for L2R with general evaluation metrics, beginning in this section with the balanced error metric.
3.1 DOES CHOW'S S RULE SUFFICE FOR BALANCED ERROR?
The classical Chow's rejection rule described Eq. (2) can be grossly sub-optimal for the balanced error, and can in fact have an adverse impact on the tail classes. Figure ((d) provides an illustration of latter on the long-tailed ImageNet-LLT dataset (Liu et al., 2019), where we group classes with fewer than 20 samples in the training set the tail classes, and show that Chow's w rule is substantially better on the head classes compared to the tail. This suggests that one cannot naïvely apply existing L2R methods in settings involving evaluation measures beyond the standard accuracy.
Jones et al. (2021) similarly show in a setting where the groups are defined by spurious attributes that Chow's rule unfairly favors the majority groups. They propose mitigating this by modifying Chow's 's rule to use a base model trained with DRO. Follow-up work explores the use of a "sufficiency" constraint in the base model training alleviate group disparities (Lee al., 2021). However, formal understanding of L,R with the balanced error remains elusive; we aim to resolve this in the sequel.
3.2 FORMULATION WITH REJECTOR-DEPEEE DEPENDENT COSTS
We now formally deseribe the problem of L2R with the balanced error. For base classifier h and a rejector r, we define the error that the classifier makes non-abstained samples from each group by:
(v + h(x) ((x) 0, y Gs),
where we condition samples from group Gk which the rejector does not reject (Jones et al., 2021). We consider the goal of minimizing the average per-group error, with a constraint on the total proportion of abstentions. One may equivalently impose rejection penalty of c 0:
Ree (h, r) =
Σ P(y+h(x)) KE[K]
r((x) = 0, y y Gx) cc.P 1).
(6)
K
We will refer to this objective the balanced L2R risk, which we re-write as:
Regal (h,
1
Σ KE[K]
1 (T)
P + h(x), r(z) = O, e Gt) Pr-
K
where (r) PP (r(x) - 0. y E G+)) is the proportion of samples from group G& that were not rejected by r. Similar to the balanced error in Eq. (4), each group is weighted by the inverse group prior; however, the coefficients here are not constants and are intricately tied to the rejector In fact, the above risk has a non-decomposable dependence on r: both the numerator and the denominator depend r, making the minimization problem non-tre con-irivial and challenging. This is in contrast to prior work on cost-sensitive rejection (deferral), where the costs on the misclassification errors are fixed and have dependence on "Santos-Perein & Pires, 2005; Alves al., 2024).
3.3 BAYES-OPTIMAL CLASSIFIER AND REJECTOR
As first step towards learning classifier and rejector that minimizes the balanced L2R risk in Eq. (6), we seek to understand the form of the Bayes-optimal solution for the objective. To this end, re-write the risk into equivalent form where the denominators do not explicitly depend
4

---

Published as a conference paper at ICLR 2024
on the rejector. Specifically, decouple the dependence of the denominators the rejector by introducing auxiliary variable aj,...,, a E (0, 1), and reformulate the minimization over and r equivalent constrained optimization problem:
min 0,
Σ
.P Pv h(x),, r(x) 0, E Gk) c (((x)) =1
ak
KE|K]
s.t.
K (r(z))) Gk) = OA vk E [K].
This then allows us to provide a characterization of the Bayes-optimal solution. By computing the Lagrangian for Eq. (7) with multipliers -i,..., R for the K equality constraints, we have: Assumption 1. For x ~ P, assume that [n (z), (x)) a continuous random vector.
Assumption 2. The minimizer (h* ,r") of the balanced L,R risk in Eq. (6) is such that F(r* 0,y E G+) 2 K, Yk, for some > 0.
Theorem 1. Under Assumptions and 2, there exists proup-specffic parameters af E K) and 4et E R such that the optimal classifier and rejector for Eq. (6) take the form:
(x)) = arg max DE(L)
Bl (x):
r' (x) =1
max WE[L] [v)
Th (z) <
(M0) Th (x)
-c,
(8)
"brl
V'ElL]
where [v] is the index of the group class y belongs to; moreover of K P(r"(
Gk).
Assumption 1 is fairly common in the analysis of Bayes-optimal solutions for evaluation metrics (Narasimhan et al., 2015b; Yan et al., 2018; Yang et al., 2020). This together with Assumption allows us pose Eq. (7) as an equivalent (unconstrained) Lagrangian minimization problem.
(z) as measure of classifier confidence, and The optimal rejector uses the term maX %
checks it falls below a sample-depender threshold. The multipliers uÇs in the threshold can be per-group adjustments that ensure that the acceptance rate for group i is proportional of In fact, in the special case where we have binary labels, each in separate group, the rejector takes much simpler form, with a constant threshold for each class (details Appendix D.4).
Remark 1 (Sub-optimality of L2R Baselines). Unlike the classical Chow's 's rule in Eq. (2) or its conditional variant in Eq. (23), which apply a constant threshold to the maximum conditional probability max, 7 (x), the optimal rejector in Theorem takes fundamentally different form, involving all paassprrbabiliites. In fact, can be seen as applying a sumple-dependent threshold to re-weighted probabilities. This suggests that Chow's rule is sub-optimal for the balanced L2R risk. This also suggests that approaches which optimize a surrogate loss for the L2R risk (Cortes et al., 2016; Geifman & El- Elniv,,v, 2017; Ramaswamy al., 2018; Ni et al., 2019; Mozannar & Sontag, 2020; Charoenphakdee et al., 2021) are also sub-optimal for the balanced L2R risk, as they are also designed to learn the same thresholded rejector in Eq. (2) that Chow's rule seeks to mimic.
4 ALGORITTM FOR BALANCED L2R
We next present an algorithm for learning a classifier and rejector that is optimal for the balanced L2R risk in Eq. (6). We begin by exploring simple modifications to Chow's rule.
4.1 CHOw's RULE WITH MODIFIED BASE LOss
One obvious variation Chow's 's rule to modify the base model training to optimize a balanced version of the CE loss in Eq. (3):
bal argmin,
L E GR) (cc(u.((x))
(9)
kE(K]
One may then implement Chow's rule via the class probability estimates (x))(()) (x) exp(f))al (x:):
h bal( E arg max,e(()) p ball (x);
max p bal (x)
(10)
5

---

Published as a conference paper at ICLR 2024
Although intuitive, this simple modification to Chow's 's rule does not yield the optimal classifier and rejector for the balanced L2R risk.
Lemma 2. cross-entropy loss, results in classifier and rejector of the form:
The variant of Chow's 's rule in Eq. (10), where the base model is trained with the balanced
h bal (x) = arg max
(2)
vE[L]
bal (x)
max
(1)
"Ty
Σ V'E(Li "[v]]
Tor (x)) (1 -),,
(11)
E L
Tbl
where [y] is the index of the group to which class y belongs.
There are two key differences between the above rejector and the optimal rejector in Theorem 1. First, in the above rejector, the abstention cost is part of a multiplicative term whereas it is part of an additive term in the rejector Theorem 1. Second, the per-class weights in the above rejector depend on the fixed group priors Te, whereas those in Theorem 1 depend more intricately on the underlying distribution through the parameters og (which depend on the optimal rejector) and multipliers jlg More generally, any re- re-weighting of the base loss with constant coefficients will result in a rejector with multiplicative penalty term different from the form Theorem (see Appendix A.2).
4.2 PLUG-IN APPROACH WITH No CHANGES TO THE BASE LOSS
As an alternative to modifying the base loss in Chow's rule, we propose a new plug-in approach that seeks directly mimic the optimal classifier and rejector for the balanced L,2R risk. Like standard Chow's 's rule, we assume access to only a class probability estimator Py (z) trained to minimize the softmax CE loss in Eq. (3). We then wish approximate the Bayes-optimal classifier and rejector from Theorem by plugging in estimates Py (z) of the class probabilities:
?(x) = arg max
(2)(x);
(12)
vC[r]
[M)
f(x)) =1
1 [v)
Py
1 arw'
Mo1) po)
(13)
VE[
D'E(L]
for choices of & E (0, KYK and j E R One may carry out an exhaustive search to pick á and that the resulting classifier-rejector pair yields the lowest balanced error held-out sample. However, searching over 2K parameters can quickly become infeasible even when K is small.
To make the search more efficient, we exploit the additional constraint in Theorem that requires âg to match the rejector's s coverage for group Gg. i.e., á K - Ply E Gk, f(x)) = 0). Specifically, propose applying grid search over only the multipliers j., while using power-iteration- heuristic to choose é. Starting with initial values (0) (0, K)K, we propose alternating between constructing the classifier-rejector pair and updating the group priors using the rejector's coverage:
Construct (1/m), ((mm)))(())))) (m)) using equations 12-13 with (m) and the fixed multipliers ja;
(m+1) K P(y E Gk, (mm) (x) = 0).
Set 0
One may repeat these steps until the iterates a (1)s converge to stationary point, and return the corresponding classifier and rejector.
For moderate number of groups K, one may apply the above procedure for different values of multipliers ý E R and pick the one for which the returned classifier-reeector pair yields the lowest balanced error on validation set. The details are outlined in Algorithm 1, where A is the set of multiplier values we wish to search over, and 3r = & for the balanced error. fact, one can further prune the search space by re- re-parameterizing the rejection criterion in Eq. (13) to search over only K - parameters (see Appendix E. for details). For problems with two groups (e.g. head and tail), this would mean that we only have single parameter to tune. For larger number of groups, we prescribe applying an alternate Lagrangian -egrae min-max optimization to tune the multiplier parameters. We elaborate this procedure in Appendix E.2.

---

Published as a conference paper at ICLR 2024
Algorithm 1 Cost-sensitive Plug-in (CS-plug-in)
1: Input: Rejection e, Group weights E Ar., Pre-trained model p X' A.. Sample $
2: Parameters: Multiplier A RK Itteationn M, Initial prior ( E (0, 1)x, Initial (h, f)
3: For in A:
4: For m = 0 M - 1:
(m) Dv
5:
Construct (1(m+1), (((+))) using equations 12-13 with àg
and j p
0kk (m+1) = [S] ((z))es 1 E GR. 7 (()+)(()) = 0), Ak [K]
6:
7:
(h, -(h(), ((80)) if Σx BR (e(1) < Σx Br én (h,
8: Return: (h
Algorithm 2 Worst-group Plug-in
Input: Rejection cost c, Pre-trained model p X Ar Sample s divided into S₁, S2
2: Parameters: Inital group weights g(0) E Åz, Iterations T, Step-size
3: For t = 0 to T
,00,,, 4: (h(t), (t))= = CS CS-plug-in(e,, (()) ,, S1)
5: $ g(++1) = - -exp(e-épe (x(!)) r())), Ak E [K], where Z -= 0800 exp((f-,,(10) (()))
6: Return: (1(T), ((T)
Figure 2: Plug-in algorithm for the cost-sensitive error Σ, 34 éx (h, r) (Algorithm 1) and worst-group enror max; én (h,,)) r) (Algorithm 2). where és (x.(hr) Einges 1(s7th()) Einyles ((x=0).)(z)=0) Algorithm can be applied to minimize the balanced L2R risk in Eq. (6) by setting 3r 1/K, V& [K].
EXTENSION TO GENERAL EVALUATION METRICS
We next extend our results to evaluation metrics more general than the balanced error. To this end, we denote the conditional error of classifier h and rejector r on group G2 by: ex (h, r) = P (y + 1((r) r(x) 0, E Gk). We then consider the problem of minimizing general function of the per- group errors (1 r).... ch,,, r), with a cost of c for abstention: (h, r))
/ : [0, 1]
Reel (h, v/ (ei(h, (f.
(r(x) 1).
(14)
This generalized L2R risk includes the balanced error from Eq. (6) as a special case when (bzz) = 1 K Ex 2k. It also captures more general evaluation metrics defined by non-linear function such as the worst-group error with (zz) maX 2 (Sagawa et al., 2020), and the G-mean metric when (b(z)
- (1 ///
/K (Menon et al., 2013; Narasimhan al., 2015b).
5.1 BAYES-OPTIMAL CLASSIFIER AND REJECTOR
As with prior work on optimizing general evaluation metrics (Narasimhan et al., 2015a; Yang et al., 2020), the generalized L.2R risk is minimized by classifier-rejeccor mechanism that is stochastie.
Theorem 3. For any non-linear dh, there exists coefficients (")), e(1), ...., kl)+)) (K++) E R and a distribution v E AK+1, +1, such that, the generalized L2R risk in Eq. (14) is minimized by
stochastic mechanism that randomizes over K + classífier-rjjes rrejecor pairs: for any x, it predicts using (1((), ,(00 with probability
(x) arg max, Ut (1)
(2), iE [E[+1]) +1]
(x) 1 maxy uy Bly (1) Ey w (x) iE [
Stochastic classifiers are widely used in the design of learning algorithms for complex evaluation metries (Narasimhan et al., 2015b; Cotter et al., 2019b; Narasimhan al., 2019; Yang et al., 2020). In applications where the use of stochastic classifiers is infeasible, one may use techniques offered in Cotter et al. (2019a) convert them into similar performing deterministic classifier.
7

---

Published as a conference paper at ICLR 2024
Method
CIFAR-100
ImageNet
NNaturalist
Balanced
Worst
Balanced
Worst
Balanced
Worst
Chow
0.509 + 0.002
0.883 +: 0.007
0.409
0.003
0,685 = 0.007
0.131
0.004
0.162 :: 0.004
CSS
0.483 + 0.002
0.785 + 0.003
0.526 + 0.002
0.784 0.003
0.200
0.005
0.246 + 0.006
Chow [BCE)
0,359 = 0.017
0.570 + 0.030
0.213 + 0.001
0.274
= 0.003
0.111
0.003
0.114 = 0.003
Chow [DRO]
0.325 0.004
0.333 + 0.003
0.197 0.001
0.211 0.004
0.110
0.001
0.117 + 0.002
Plug-in in [Balanced]
11.292 + 0.006
0.416 + 0.015
0.205 + 0.001
0.248 + 0.001
0.108
0.003
0.118 + 0.004
Plug-in [Worst]
0.287 0.008
0.321 +: 0.018
0.198 0.001
0.213 = 0.004
0.108
0.001
0.113 +: 0.002
Table 2: Area Under the Risk- Coverage curve (AURC) with the balanced and worst worst-group error. Chow and CSS are L2R baselines. We evaluate two variants of Chow (BCE, DRO) with a modified base loss (84.1), and plug-in methods (Balanced, Worst) that require changes to the base model training (84.2, $5).
5.2 MINIMIZING WORST-GROUP ERROR
One can minimize the risk in Eq. (14) by exploiting the form of the function b. For example, if ab is convex, one can reduce it to a sequence of minimization problems of the form:
Es 30 (x(h,r) c c.P (P((()(()))))))))))))()) = 1)
for coefficients ( (,0),, ,.... E R.KK each of which can be solved by adapting the plug-in method described in $4.2. Prior work has shown how this can be done in the standard classification setup (without rejection) by applying gradient-
optimization to & (Narasimhan et al., 2019; 2022a; Yang et al., 2020). As a concrete example, we showcase how a similar reduction can be done for the worst-group L2R risk with y (Z1..... 2x) = ma 2x. The details are in Algorithm
The algorithm maintains group-specific weights g(0) E A where Ax is the probability simplex over K coordinates. At each iteration, it updates g(4) using exponentiated gradient-descent, up-weighting groups with high empirical error én r), . It then invokes the plug-in approach in Algorithm 1 to minimize the resulting weighted error Σx (()) êx (h, r). Below, we provide convergence guarantees for the algorithm in terms of the optimality gap in the weighted error minimization step (line 4).
Theorem 4. Let R (h denote the generalized L2R risk in Eq. (14) with (/ =x) = max; Let et = (t(t) ,((1) Ex((()) (())) denote the estimation error in iteration t of Algorithm 2. Let = 165) (h(t)) ((1) inf Σx 3/00 ex ex(h, r) denote the excess cost-sensitive risk for the classifier-rejectrn pair (h(0), ,(0) returned in line Then stochastic mechanism that picks one among ((h(4) ((1)), ,,,)))..... (1(7), ,r(())) with equal probability satisfies:
max Es (c((h))) [()]] + [F(r (1) (x) 1)] s inf Rici K][K]
Rea (h,r) + -00 + +2gen + 2/ log(K)
hrr
wheret is drawn uniformly from {1..... TH. = Exeryy & and J Exerry gon
To ensure fair comparison against other deterministic baselines, when implementing Algorithm 2, we do not employ a stochastic solution, but instead use the final classifier-rejector pair (f( ,(T),
EXPERIMENTAL RESULTS
We present experiments on long-tailed image classification tasks to showcase that proposed plug-in approaches for the balanced error ($4) and the worst-group error ($5) yield significantly better trade-off's than Chow's rule, despite using the same base model, and are competitive with variants of Chow's 'oo's rule which require re- re-training the base model with modified loss.
Datasets. We replicate the long-tail experimental setup from Menon et al. (2021a). We use long-tailed versions of CIFAR- 100 (Krizhevsky, 2009), ImageNet (Deng et al., 2009) and iNaturalist (Van Horn et al., 2018). For CIFAR- 100, we downsample the examples per label following the Exp profile of Cao et al. (2019), and for ImageNet, we use the long-tail version provided by Liu et al. (2019). The train, test and validation splits have the same label distributions (see Appendix F for details). We train ResNet-32 (50) model for CIFAR (ImageNet and iNaturalist..
8

---

Published as a conference paper at ICLR 2024
0.6
0.35
0.5
0.30
CSS
0.4
Balanced Enot
0.4
0.25
Plug-in (Balanced)
Chow [SCE)
0.20
0.3
0.3
0.15
0.2
CSS
Chow
Chow
CSS
0:10
0.1
0.05
Plugein (fwianced)
Plugein [Awlanced)
0.00
0.2
0.4
0.4
0.6
Proportion Rejections
Proportion of Rejections
Proportion of Rejectiors
0.8
0.4
Chew
Worst Porst-9roa Enor
0.0
0.6
Worst-group Emoo
0.3
Plugein [Wers]]
Chow [BRO]
30.6
0.4
Chow [DRO]
0.2
0.4
Chow
Plugen [Worst]
C5S
0.1
0.2
Chow [DRO]
Plug (Worst]
0.0
0.0
0.2
0.4
0.5
0.8
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.5
0.8
Proportion of Rejections
Proportion of Rejections
Proportion of Rejections
(a) CIFAR-I0N
(b) ImageNet
(c) iNaturalist
Figure 3: Balanced and worst-group errors as functions of proportion of rejections. Lower is better.
Evaluation metrics. For each dataset, we divide the classes into two groups, namely head and taill. We designate all classes with 20 or fewer samples in the training set as tail classes (Liu et al., 2019), and the remaining as the head. We evaluate both the balanced error and the worst-group error across the head and tail groups. We train classifiers and rejectors with different rejection costs c, and plot these metrics as a function of the proportion of rejections. We summarize the performance across different rejection rates by computing the areas under the respective curves (averaged over 5 trials); this summary metric is referred to as the area under risk-coverage curve (AURC) (Moon et al., 2020).
Comparisons. We compare against two representative L2R baselines that optimize the standard 0-1 error: (i) Chow's rule, which trains a base model by optimizing the CE loss, and thresholds the estimated max probability (Eq. (2)); and (ii) the cost-sensitive softmax (CSS) loss of Mozannar & Sontag (2020), which jointly trains a classifier and rejector using a surrogate loss (with the ResNet model predicting L + logits, and the (L + 1)-th denoting the 'abstain' option). We evaluate our plug-in methods for the balanced error (Alg. 1) and the worst-case error (Alg. 2), both of which use the same base model as Chow's rule. We also evaluate variants of Chow's 's rule ($4.1), where the base model is trained with either a balanced cross- coss--ntropy (BCE) loss implemented through logit adjustments (Menon et al., 202 la), or the DRO loss prescribed by Jones et al. (2021).
We present plots of the balanced and worst-group errors as a function of the rejection rate (for varying values c) in Figure 3. We summarize the area under these curves in Table 2. On all three datasets, the proposed plug-in methods are substantially better than both Chow's 's rule and the CSS baseline. The plug-in methods are also comparable to or better than the variants of Chow's ss rule that uses balanced or DRO base loss. As shown in Figures 4-5 in Appendix F.5, Chow's 's rule is unsurprisingly the best on the standard 0-1 error. On the other hand, Figures 6-7 show that our plug-in methods yield lower gap between the tail and head errors compared to the L2R baselines. Finally, in Appendix F.6, we show on CIFAR-100 that the heuristic we employ in our plug-in approach to pick the group coverage ($4.2) performs comparable to exhaustive grid search over a.
Results.
CONCLUSION
We have shown that standard L2R can be sub-optimal for general evaluation metrics, and proposed simple plug-in methods that yield significantly better trade-off's for both the balanced and worst-group error. Our methods require only pre-trained model optimized with the CE loss, and are competitive with complex loss modification approaches. In the future, it is of interest explore joint training of the classifier and rejector using surrogate losses (Cao et al., 2022), and extensions to hierarchical classification (Wu al., 2020b) and pairwise ranking (Shen al., 2020; Mao et al., 2023b).

---

Published as a conference paper at ICLR 2024
REFERENCES
Jean V Alves, Diogo Leitão, Sérgio Jesus, Marco OP Sampaio, Javier Liébana, Pedro Saleiro, Mário AT Figueiredo, and Pedro Bizarro. Cost-sensitive learning defer multiple experts with workload constraints. arXiv preprint arXi::2403.06906 2024.
Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 1413 2006.
Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M. Buhmann. The balanced accuracy and its posterior distribution. In 2010 20th International Conference on Pattern Recognition, pp. 3121 -1244, 2010. doi: 10. 10.1109/CCR..200....6
Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski. A systematic study of the class imbalance [cs, stat), October 2017.
problem in convolutional neural networks. arXi::
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with bebell-distrbuuto--wwaaaa margin loss. In Advances in Neural Information Processing Systems, 2019.
Yuzhou Cao, Tianchi Cai, Lei Feng. Lihong Gu, Jinjie Gu, Bo An, Gang Niu, and Masashi Sugiyama. Generalizing consistent multí-class classification with rejection to be compatible with arbitrary losses. Advances in Neural Information Processing Systems, 35:521-534, 2022.
Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classification with rejection based on cost-sensitive classification. In Marina Meila and Tong Zhang (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp. 1507-1517. PMLR, 18 28-24 Jul 2021.
C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970. doi: 199///TT7..9 10544406.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In ALT, 2016.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Theory and algorithms for learning with rejection in binary classification. Annals of Mathematics and Artificial Intelligence, 2023.
Andrew Cotter, Maya Gupta, and Harikrishna Narasimhan. On making stochastic classifiers deter- ministic. Advances in Neural Information Processing Systems, 32, 2019a.
Andrew Cotter, Heinrich Jiang, Maya Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research, 10517)) 2019b. URL http: http:////.oorrr////..////../o
jwlr.oorrr papprs/ 18 616.html.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song. and Serge Belongie. effective number of samples. In CVPR, 2019.
loss based on
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 245-255. Ieee, 2009.
Zongyong Deng, Hao Liu, Yaoxing Wang, Chenyang Wang. Zekuan Yu. and Xuchong Sun. PML: progressive margin loss for loig-tailed age classification. CoRR, abs/2103.02140, 2021. URL https://arxln org/ ab///bs///ee 2203.2111.. 02140.
Ran El- Elniv and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11653):1605-1641, 2010. URL
vi1/el-yanivioz htm.n.liio..ml....
Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective classification via one-sided prediction. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th In- ternational Conference
Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2179-2187. PMLR, 13-15 Apr 2021. URL https: //proceedings. mlr wwwpssrsssve..eee wwt.://eggggggreeaa.a.. html. wttp:/iinnng.......reeeeeeieee
10

---

Published as a conference paper at ICLR 2024
Yonatan Geifman and Ran El-Yaniv. Selective classification for deep neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, PP- 4885 4894, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering. 21(9):12633 2009.
Muhammad Abdullah Jamal, Matthew Brown, Ming-Hsuan Yang, Liqiang Wang, and Boqing Gong. Rethinking class-balanced methods for long-tailed visual recognition from domain adaptation perspective. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Erik Jones, Shiori Sagawa, Pang Wei Koh, Ananya Kumar, and Percy Liang. Selective classi- fication can magnify disparities across groups. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openreviie net/ forum? 1eeeiiddeeooM055S55
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yan- nis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In Eighth International Conference on Learning Representations (ICLR), 2020.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameterization. CoRR, abs/2103.01550, 2021. URL
httg//bb//21033/ 01550.
Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep K Ravikumar, and Inderjit S Dhillon. Con- sistent binary classification with generalized performance metries. NIPS, pp. 2744-2752, 2014.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Joshua K Lee, Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das, and Gregory W Wornell. Fair selective classification via sufficiency. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. https: / https://ppoceedingg.
PMLR, 18 24 Jul 2021. URL /ttsss//11/// v139 V139//ee21b.bbb.o html.
m....rr.... p
Zachary C Lipton, Charles Elkan, and Balakrishnan Naryanaswamy. Optimal thresholding of classifiers to maximize fl measure. In Machine Learning and Knowledge Discovery Databases: European Conference, ECML PKDD 2014, Nancy, France. September 15-19, 2014. Proceedings. Part 11 14, pp. 225-239. Springer, 2014.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X. Yu. Large- scale long-tailed recognition in an open world. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Anqi Mao, Christopher Mohri, Mehryar Mohri, and Yutao Zhong. Two-stage learning to defer with multiple experts. sevethh Conference on Neural Information Processing Systems, 2023a. URL
net forum?
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Ranking with abstention. arXiv preprint arXiv:2307.02035, 2023b.
Aditya K Menon, Ankit Singh Rawat, Sashank Reddi, Seungyeon Kim, and Sanjiv Kumar. A statistical perspective on distillation. In International Conference on Machine Learning, pp- 7632-7642. PMLR, 2021a.
Aditya Krishna Menon, Harikrishna Narasimhan, Shivani Agarwal, and Sanjay Chawla. On the statistical consistency of algorithms for binary classification under class imbalance. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pp. 603-611 2013.
11

---

Published as a conference paper at ICLR 2024
Aditya Krishna Menon, Ankit Singh Rawat, and Sanjiv Kumar. Overparameeterisatoon and worst-case generalisation: friend or foe? In 9th International Conference on Learning Representations, ICLR 2021. Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021b. URL https:
//openreview.
Jooyoung Moon, Jihyo Kim, Younghak Shin, and Sangheum Hwang. Confidence-aware learning for deep neural networks. In international conference on machine learning, pp. 7034-7044, PMLR, 2020.
Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7076-7087. PMLR, 13-18 Jul 2020.
Harikrishna Narasimhan. Learning with complex loss functions and constraints. In International Conference on Artificial Intelligence and Statistics, pp. 1646-1654, 2018.
Harikrishna Narasimhan and Aditya Menon. Training over-parameterried models with non- decomposable objectives. Advances in Neural Information Processing Systems, 34:18165-18188
2021.
Harikrishna Narasimhan, Harish Ramaswamy, Aadirupa Saha, and Shivani Agarwal. Consistent multiclass algorithms for complex performance measures. In ICML, pp. 2398-2407, 2015a.
Harikrishna Narasimhan, Harish Ramaswamy, Aadirupa Saha. and Shivani Agarwal. Consistent multiclass algorithms for complex performance measures. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2398-2407, Lille, France, 07-09 Jul 2015b. PMLR.
Harikrishna Narasimhan, Andrew Cotter, and Maya Gupta. Optimizing generalized rate metries with three players. In Advances in Neural Information Processing Systems, pp. 10746-10757, 2019.
Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Ku- mar. Post-hoc estimators for learning to defer to an expert. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp- 29292-29300 Curran Associates, Inc., 2022a. URL https::/prooeeediggg... neurips httpppssccpppppppppppppppp ffle//ocff66cccaddd6//7755522262 www.dddeeeddaappe---eeee- ceneer-Coffeeece..o. pdff.
2022/
Harikrishna Narasimhan, Harish G Ramaswamy, Shiv Kumar Tavker, Drona Khurana, Praneeth Netrapalli, and Shivani Agarwal. Consistent multiclass algorithms for complex metrics and constraints. arXiv preprint arXiv:2210.09695, 2022b.
Jerzy Neyman and Egon Sharpe Pearson. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, (896669970))229222229
1933.
Chenri Ni, Nontawat Charoenphakder, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 2582-2592, 2019.
Harish G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics, 12(1):530 554, 2018. doi: 10.1214/17-EJS
Jiawei Ren, Cunjun Yu, shunan sheng, Xiao Ma, Haiyu Zhao, Shuai Yi, and hongsheng Li. Balanced meta-softmax for tailed visual recognition. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4175 4186. Curran Associates, Inc., 2020.
12

---

Published as a conference paper at ICLR 2024
S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. In International Conference Learning Representations (ICLR), 2020.
Carla M. Pertis-Pereira and Ana M. Pires. On optimal reject rules and ROC curves. Pattern Recognition Letters, 26(7):943-952, 2005. ISSN 0167-8655. doi: https://dii.or//10.100 cttp/ectccccccccccccc///rttiiiit
satrec.2004.09.000 URL https:
pJ1/55016885554022222.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
Song-Qing Shen, Bin-Bin Yang. and Wei Gao. AUC optimization with a reject option. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3684-5691, 2020.
J. Tan, C. Wang, B. Li, Q. Li, W. Ouyang, C. Yin, and Yan. Equalization loss for long-tailed object recognition. In 2020 JEEE/CVE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 11619-11666,,, 2020.
S. K. Tavker, H. G. Ramaswamy, and H. Narasimhan. Consistent plug-in classifiers for complex objectives and constraints. In Advances in Neural Information Processing Systems, 2020.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, 2018.
Rajeev Verma and Eric Nalisnick. Calibrated learning to defer with one-vs-all classifiers. arXiv preprint 2rXiv:2202.03673. 2022.
Jiaqi Wang, Wenwei Zhang, Yuhang Zang, Yuhang Cao, Jiangmiao Pang. Tao Gong, Kai Chen, Ziwei Liu, Chen Change Loy, and Dahua Lin. Seesaw loss for long-tailed instance segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2021.
Serena Wang. Harikrishna Narasimhan, Yichen Zhou, Sara Hooker, Michal Lukasik, and Aditya Kr- ishna Menon. Robust distillation for worst-class performance: on the interplay between teacher and student objectives. In Uncertainty in Artificial Intelligence, pp. 2237-2247. PMLR, 2023.
Tong Wu, Qingqiu Huang, Ziwei Liu, Yu Wang. and Dahua Lin. Distribution ballancced--- loss for multi- label classification in long-tailed datasets. Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michadl Frahm (eds.). Computer Vision - ECCV 2020, pp. 162-178, Cham, 2020a. Springer International Publishing. ISBN 978-3-030-58548-.
Tz. Ying Wu, Pedro Morgado, Pei Wang, Chih-Hui Ho, and Nuno Vasconcelos. Solving long-tailed recognition with deep realistic taxonomic classifier. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part VIII 16, pp. 171-189. Springer, 2020b.
Bowei Yan, Sanmi Koyejo, Kai Zhong. and Pradeep Ravikumar. Binary classification with karmic, breeshold-qusi-coneee metrics. In International Conference on Machine Learning, pp. 5531- 5540. PMLR, 2018.
Forest Yang, Moustapha Cisse, and Sanmi Koyejo. Fairness with overlapping groups NeurIPS, 2020.
Xi Yin, Xiang Yu, Kihyuk Sohn, Xiaoming Liu, and Manmohan Chandraker. Feature transfer learning for face recognition with under-represented data. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Junjie Zhang, Lingqiao Liu, Peng Wang, and Chunhua Shen. To balance or not to balance: A simple-yet-effective approach for learning with long-tailed distributions, 2019.
Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun. Distribution alignment: A unified framework for long-tail visual recognition. In CVPR, 2021.
13

---

Published as a conference paper at ICLR 2024
Appendix
A PROOFS FOR RESULTS IN MAIN TEXT
A. PROOF OF THEOREM 1
The proof follows as corollary of Theorem 12 in Appendix D.3 by setting 8x K. Ak, and scaling the resulting parameters a2 by K. Note that Theorem 12 considers a minimization problem that allows for stochastic classificr-rejector mechanisms. However, since the optimal solution is deterministic classifier-rejectorr pair, still remains the optimal solution when the minimization is over only deterministic classifier-rejector pairs.
A.2 PROOF OF LEMMA 2
We prove more general version of Lemma 2. Consider variation of Chow's rule where modify the base model training to optimize weighted version of the CE loss in Eq. (3):
Σ KE[K]
Bx E - f()))
(15)
for some E IR One may then use the class probability estimates (²)(2) xc exp(ff"(xx) from the learned scorer fwr to implement Chow's 's rule:
h (x) E arg ye()) Py wt (z);
p (x) =1 +
ya (x) <1-c.
(16)
Lemma 5. The variant of Chow's 's rule in Eq. (16), where the base model is trained with the balanced cross-entropy loss, results in classifier and rejector of the form:
h (x)
xx)
arg max Pby (x)x))
sE(l]
bal (z)
3p) (x)
(E VELL
B no(o)) (1 c).
(17)
vE[L
where [y] is the index of the group which class y belongs.
Proof. We re- write the weighted CE loss in Eq. (15)
E
[B (v.
Since the softmax CE loss is strictly proper-composite loss, we have that the minimizer py pyt(2) (z) exp(fX (I:) of this objective takes the form:
p (x)
((x) Bigi (y(x),
where 7(x)= Eyr Bly my (x). When applying Chow's rule to these probabilities, we get:
(x)
maxp wt c.
which is the same as:
wt (x) 11
max B/y (x)
Σ Awl my mo((s)) (1 c),
as desired.
Proof of Lemma 2. The proof follows from Lemma by setting 3x Rx
14

---

Published as a conference paper at ICLR 2024
A.3 PROOF OF THEOREM 3
See Appendix D.5.
A.4 PROOF OF THEOREM 4
The proof follows from an application of the standard convergence guarantees for the exponentiated gradient descent algorithm (Shalev-Shwartz et al., 2012). One can further bound the estimation errors & gen in each iteration of Algorithm using standard generalization analysis (Narasimhan et al., 201 Sa; Tavker et al., 2020; Wang et al., 2023), noting that the classifier and rejectors (h²,r") are plug-in estimators chosen from a finite capacity class (namely that of post-hoe linear adjustments to fixed model p).
Proof. Recall that the worst-group L2R risk is given by:
Rend (h, r) max qax, r) + c. P(r(x)) 1).
This risk can be equivalently re-written as: Rws (h, r)
Pc- P(((())) 1).
max BEAR
We apply standard guarantees for the exponentiated gradient ascent algorithm (Shalev-Shwartz et al., 2012) to treating è1 (h(*), ((.))..... êx (h(0,, (()) as the losses incurred by K experts. We have that when E
log(K) the iterates (N(1), ((1)), ....,, (,(T), in Algorithm 2 satisfy:
log( K)
ΣΣ
M 8k (x (0)) $
86 (x(b))),,0) + 2
max BEAR
T
T
t=1
Bounding by the estimation error in each iteration, we get:
T
Σ
3x (ex(te eqen)
max BEAN
T
k
log K) T
(1(0), (gen 2/
1=1
which is the same as:
1 Σ Be (1() (0))
T
(1) cx(h(()) ,((0)) + 2z +2 2/
log K)
max BEAK
I
k
T
T
1=1
Adding c. (1) (xx) = 1) on either side, we have:
C-P((
T
)(()) (1, Be en (1
c. (()
max SEAR
T
log K)
<
(1) %
ek (1))) ,(()) c. (x) = 1) + 27 + 2/
T
T
1=1
<
1
inf
(1)
+c 1) }
Σ
Σ c + 20 + 2
log K)
(18)
hrr
T
T
log(K)
< inf
tc =1 + ~ + 2g + 2/
br
k
T
log( K)
< inf Σ
Br
= 1) + ~ + 2z + 2/
(19)
b
T
15

---

Published as a conference paper at ICLR 2024
log( K)
inf max
Σ By hrr BEAR
1) + E0 2ggen + 2
T
2 + 21 log(K)
S inf max ex (h, cc- P(.((((()))))))))))))))(()))). 1) E0
hrr
log(K) K)
= innf R r) + - + 27 + 2V T
(20)
where in Eq. (18), we apply the bound on the excess cost-sensitive risk in line 4 of the algorithm, and in Eq. (19), we denote 3rg T Σ o6 We can re-write the LHS as:
1
Σ
Σ
BK ((c(h())))())) + ((r(p(r())))))) =10 1))
BEAK!
T
1=1
K
E
Bk EE [ea(h(0, r(t)) cc. p(((( =1}
max BEAX
[et(h(), +c. P(p(()))) =1]
max
E E
kE[K]
|(0)] (10))))000) c. BE-U(L.....) [P(r(()= =1)
E EE kE[K]
max
Substituting back into Eq. (20) completes the proof.
B EQUIVALENCE BETWEEN SELECTIVE CLASSIFICATION AND L2R
Selective classification seeks to learn classifier and rejector that minimizes the misclassification error with a constraint on the proportion of abstentions:
min P (y h(x), r(z) s.t. (r((x) 1) s b,
(21)
where b is an abstention budget.
Theorem 6. Suppose Ply x)) and (P(x:) continuous in For any such abstention budget b in the constrained problem in Eq. (21), there exists a cost c 2 0 cost such that the minimizer of the L2R risk below is also minimizer for Eq. (21):
P ( + h(x), r(z) = 0) + e P.c..PP. (r(x)) 1).
The Lagrangian for the constrained problem in Eq. (21) is given by:
L(h, r, A) P (yr + h(x), r(x) 0) + A (F(r(z) = 1) - -b),
where X 2 0 the Lagrange multiplier.
We will find it useful to state the following lemma:
Lemma 7. Let (hy, r3) be the minimizer of L(h, r, A) for Lagrange multiplier 2 0. Then:
P hx(2), xx)x) 0) S P (y # h(z), r(x) 0),
for all r) such that (P(((x) = 1) - (x) = 1).
Proof. Since (h3, rz) minimizes the Lagrangian, for any (h, L(h3 ri
i.c.
P (y + (z),,, (x) = 0) < P (v + M(r), r(z) = 0) + (P(r(x) = -P)((((( 1)) Since 0, for any (h, r) such that P(r(z) 1) < (z) = 1), P (v + (x),), xx(x) = 0) s (v M(x).
as desired.
We ready prove Theorem 6.
16

---

Published as a conference paper at ICLR 2024
Proof of Theorem 6. For fixed À 0, the following is minimizer of the Lagrangian (h,, A):
(x) E arg max (1 x);
vE[l.]
(x) =
max Py x)) < 1 A. vE[c]
The abstention rate for (x) can then be written as:
(()2()) = f
m1xx P(y)=)<1-X P(x)) dr.
Since P(y| z)) and P(x) are continuous in 2,, we can always find a 2 for which P(r(()) 1) = b. Applying Lemma 7 with this choice of X, then have that
( + (x), (z) = 0) - P (y + h(z), r(z) 0) for all (h, r) such that P(r(2) = 1) = b. Setting c À completes the proof.
C CONDITIONAL LEARNING TO REJECT
Geifman & Yaniv (2017) minimize a variant of the L2R risk in Eq. (1), where the misclassification error is conditioned on samples that are not rejected:
Re (h,, r) PP (v + h(x) r(x) = 0) +c. (r((x) = 1).
(22)
We show below that the optimal classifier and rejector for this conditional L2R risk continues to have the same form as Eq. (2), but
different (distribution-der) )etpnddeoondeeeeeent)) rejection threshold:
Lemma 8. Under Assumption I, the Bayes-optimal solution to Eq. (22) is given by:
(x) argmax (y (z));
r" rxxx==1 =1 -
max my (2())) < d' sE[
(23)
sE(M)
for some distributionnddepedden dependent threshold d [0, 1].
Proof. The conditional L2R risk in Eq. (22) can be expressed as: Reei (h, r) IP (y h(z), = 0) + + Pc-P(r(z)=1)) =1)
(r(z)= =)
Minimizing this risk can be posed equivalent constrained optimization problem:
min 1 (y + M(x), (xx) = 0) + c. Pr((()))))) 1) s.t. (r((z) = =1
(0 a
In particular, there exists an a E (0, 1), such that the minimizer of the following constrained problem also minimizes Eq. (22):
min hrr
PP = 0) + P((x)) 1) s.t. (r(xz) = 1) = 11 Q
(24)
Using arguments similar the Neyman-Pearson lemma (Neyman & Pearson, 1933), one can show that, under Assumption I, there exists a Lagrange multiplier J¹ E R such that the minimizer to the following problem is also a minimizer Eq. (24):
min hor a
Ply (h)((())r(t)) = 0) (c+ P(((z) 1),
or equivalently:
min hr
Ex az
-1- (I-mm=)<=)) (r(x) = 0) (c+ -1)
The following are then minimizers of the above objective:
h (2) E arg max (x:)
wE(L)
and
(x) =1
max (x) < 1 - a² (r)
yE[L]
Setting a0" (c+ 1²²)
completes the proof.
17

---

Published as a conference paper at ICLR 2024
D BAYES-OPTIMAL CLASSIFIESS AND REJECTORS
We derive the Bayes-optimal classifier and rejector for the balanced 1.2R risk (6) and the generalized L2R risk (14). We will will first consider general formulation where we allow stochastic classifier- rejector mechanisms and then specialize to the case of deterministic classifiers and rejectors.
D.1 CONFUSION STATISTICS
We begin with some useful definitions. Suppose y [n] (I.....n). We define the confusion matrix for classifier-rejector pair r) by:
Ciy(h, r) = -( [1 (y = i, h(x)) = j. r(z) 0)]
We allow for stochastic mechanisms F that are defined by a distribution over classifier-rejector pairs. We adopt the convention in Narasimhan et al. (2015a) and define the confusion matrix for stochastic mechanism F by:
(F) =F (C, r)].
We will also find useful to define the space of all confusion matrices realizable by distributions over classffiers-reecctor pairs:
C (C(FF) E []m1] distributions F over (h, r)}.
is easy to show that the set C is convex.
Lemma 9, C convex set.
Proof. For any C(),, ( and [0, 1]. we will show y C()) + (1 7) C(2) E C. Clearly, there exists stochastic mechanisms F1, F2 such that ((1) = =C(F) and ( C(22). Since F' 7.Fi (1-7)) represents a valid stochastic mechanism, C(F') ( + (1-7) ( EC. O
D.2 OPTIMAL SOLUTIONS TO LINEAR MINIMIZATION OVER
We first state a couple of helper lemmas that characterize the optimal solutions to linear minimization problems over the set C. Suppose wish to minimize the following objective stochastic mechanisms F:
min ΣwN Wij C.,lF),
for coefficients W RLx1, One may equivalently formulate this linear minimization over C:
min CEC
Σ Wej Cig.
(25)
25
Lemma 10. Suppose Assumption 1 holds. Let W E BLXL be a coefficient matrix such that two columns are identical. Then Eq. (25) admits unique solution. Furthermore, the minimizing confusion matrix is achieved by the following deterministic classifier-rejectrr pair:
(x) E arg min
Σ Ws (x(x))
wE(L]
r (2) =
Σ Wew mx(x) 0. WE[L]
min
Proof. The first part (uniqueness claim) directly follows from Lemma 24 in Narasimhan et al. (2022b). For the second part, we re-write Eq. (25) into an minimization problem over stochastic mechanisms F:
min Σ CEC
Wij Cij = min Σ
Wy Ci)(F)
F
min F(h.r)=F
Σ Wis Cg(()r)
18

---

Published as a conference paper at ICLR 2024
min (hrr)
Wiy Cir(hr)
min (hrr)
Ex
Wij P(y= = h(x)) - r(z) - =0]
i.j
min
Ex
Σ 1.j
Wiy (1(x) 1(h(x) = -, r(x) r(=)= 0)
(26)
(hrr)
where the third step follows from the fact that for any function ye the expectation (R, (((h,, r)] minimized by point mass on arg (i.) soh, r).
The minimizer of Eq. (26) minimizes the term within the expectation pointwise: for any given (h" (x), r (x)) arg min (e(L),
W,y (=(x) 1( 0),
which takes the form in the statement of the lemma.
For helper lemma, we consider constrained minimization problem stochastic mecha-
nisms
min Σ Wis Ct,[P] s.t. Σ w CtylF by. Ak [K],
for coefficients W E LXL and we(1) ,...,.... (K) E TR. Once again, we may formulate this as an equivalent constrained linear minimization over C:
Wis C.s s.A. Σ E (K) Cit = bk, Wk E [K].
min CEC
(27)
Suppose Assumption I holds. Let W E RLLL be a coefficient matrix such that no two columns are identical. Let w(l) ..... (K) E R. be constraint coefficients so that Eq. (27) admits feasible solution. Then there exists multipliers μ E IRK such that the minimizer to Eq. (27) coincides with the minimizer the following unconstrained linear minimization over C:
Lemma 11.
min CEC
(Was
Σ kE[K]
Cig.
(28)
Proof. We first write the Lagrangian for Eq. (27):
p(C, Σ W Wiy.Co Cij
Σ pk
(Eul 1
-
Cij bx) bx).
(29)
kE[K]
where ,i...., uKK E R are multipliers associated with the K constraints.
Since the objective and constraints in Eq. (27) are linear in C, and C is convex from Lemma 9, Eq. (27) is convex minimization problem. Furthermore, since it has least one feasible solution, Slater's condition is satisfied, and strong duality holds. As result, there exists an optimal primal solution C* that satisfies the constraints in Eq. (27), and optimal dual solution Y such that:
C(C" .c") = min C(C, (²) = max L(C*, ,4) = Σ Ewi C mERK
(30)
CEC
Furthermore, we have that:
min 1(C, min CEC where Lij W.j - EnE(K] 14 w (R)
Σ (w Σ
(K) Cipy + + = min
Σ
Lag City + +
CEC
CEC
kE[K]
and wn = ExE(K] Mb by is independent C.
Observe that the coefficient matrix L on the right-hand side has no two columns identical. To see this, each column of L is of the form L.j- = W. =EE(K] P (k), where (.(k) = [[w] (k) ..... wi (k) columns identical, i.e., W. + W. op Vj + jr. we have that L. + L.
Since W has
Using Assumption and the above observation, we can apply the first part of Lemma 10 to show that mingec L(C, μ²") has unique solution. Since C(C*, μ mincee L(C, u²) from Eq. (30), have that the optimal primal solution C is a unique minimizer to mincec L(C, p*). In other words, C is the unique minimizer to the unconstrained linear problem in Eq. (28).
19

---

Published as a conference paper at ICLR 2024
D.3 BAYES-OPTIMAL CLASSIFIER AND REJECTOR FOR COST-SENSITIVE L2R
In this section, we derive the Bayes-optimal stochastic mechanism that minimizes the following cost-sensitive objective, with penalty of e > 0 for abstention. Specifically, define:
R (h = Σ 3x P(v + h(x)) r(x) - 0, E - -
(31)
KE[K]
where 3 E Ax the costs associated with the K groups. One can re-define Eq. (31) in terms of the confusion matrices Chh, r) as follows:
Ply h()), r(x) 0, V.
R (h, = Σ
B
(r-P(((x)= =
0, 0 G
kE[K]
BR EiEr,
Σ kE[K]
EiEG. Ejeny rij(h,r) + (1-E
For stochastic mechanism F, we similarly define
BR Eieg, Ejjr Ci((F) EiEG, EJE(4) Cis(P) +c. (1- EG((r)
(F)
Σ
(32)
kE|K]
We derive an optimal stochastic classifier that minimizes Eq. (32):
Theorem 12. Under Assumptions 1 and 2, there exists group-specific parameters a' E (0, 1)K and
ux" E R such that the following deterministic classifier- pair is an optimal solution Eq. (32):
3yl
ht arg max DEILi
(b)
P/ my (T(x))
Bw HWw1 (x) -c (33)
(x)=
max DE
y)
WELL
ofv'l
where [y] is the index of the group class y belongs to. Furthermore, of = P(r = =0, E Gt).
Proof. From the boundedness condition in Assumption 2, we know that there exists a* E (0, 1)
such that the minimizer to the following problem also minimizes Eq. (32):
3x
min
ΣΣ SEGR J#
Σ
CG((F) + c (1-Ea(())
(34)
O
kE[K]
Σ
Cl((F)
Vk [K].
SEG (E
One may equivalently formulate constrained linear minimization problem over C:
3x Of
ΣΣ Co + (1-
min CEC
(35)
K
LEGA j
Σ
Σ
Cy az Vk E [K].
NEG.
JELL]
One can now directly apply the result in Lemma 11 with Wi Exe[K] A 1(i Gb, #
and w (k) = 1(i Gt). Vi E [L], noting that no two columns of W are identical. Consequently, we have that there exists multipliers μ² E RK* such that the minimizer to the following unconstrained linear minimization over C also minimizes Eq. (35):
Wes
Σ Mx w. (0(()) Cig- kE[K]
min CEC
1.
20

---

Published as a conference paper at ICLR 2024
Applying Lemma 10, have that the above problem admits unique minimizer C* which is achieved by the following deterministic classifier-rejector pair:
ht (z) E arg min
Σ
Wiy
E kE|K]
uh w!!h) -T((a);;
wE(L]
(x) =1
min vE(L)
Σ
Was
Σ kE|K]
me n/- (b( 77((x) >
Substituting for W and w; (k)
then gives us:
3x
10 (x) E arg min
E kE[R] LEG
Σ
1(y 1) - 11/) -m(x)) -
yE(L]
Bk
(x)=
min WELLi
1(y #1) 142) (m(x)) >
kE[K]
iEG
The optimal classifier h then simplifies to:
h" (x) arg max vE[r]
Σ
Σ
BR
(z)x)
WEG; aj
kE[K]
Since each class y belongs exactly one group, this is the same as:
Plvl
(x) E arg max
Th (x),,
vE[L]
[b]
where [y] is the index of the group class y belongs to.
Similarly, the optimal rejector r" simplifies to
(x)=1
min wE[L
Bc ox
ni)) mp(z)
Σ
Σ
Be
my(())
O
kE|K]
E
kE[K] DEGR
which is the same as:
r (xx)
max [ (9)
Ty < Σ
MDr1)
"Ty - c,
N'E(T]]
as desired.
D.4 SPECIAL CASE OF BINARY GROUPS WITH BINARY LABELS
In the special case where we have binary labels, each in a separate group, the rejector in Theorem 12 takes much simpler form, with constant threshold for each class.
Corollary 13. Suppose = 9 = 10. Under Assumption 1, the optimal classifier and rejector for Eq. (32) simplifies to applying class-specific thresholds TØ . E IR and 7 E (0, 1):
hr (x))) (m >"); r"(x)= =1
(=)(2)) < Th-(())
Proof. When 9 {0, 1}, have from Theorem 12 that the optimal classifier takes the form:
3o
B1 mla) = ( mm(x)
Bi aj m((r) 1 (m) 7"),
h" h+())) arg max
(=))
aj
an
Bo/og where 7-h 3. 80/af+8//at
desired; the last equality uses the fact that (x) + m/ (x) =
Similarly, the optimal rejector is given by:
(x)(x) ax-(m)
30
( (
r r*(x) =1 =
Th (x) <
1b)
(o(x)) +
pi) (x) - (36)
ag
aj
21

---

li Published as a conference paper at ICLR 2024
Consider the case when h (=))) 1. right-hand side of Eq. (36) as:
We can then use the fact that nu())) + 1/1 (2)
to re- re-write the
51 mz() aj
fu aj
( B1
<
- 16)
(1 - mm(x))))
Hi
m (x)
aj
which simplifies to:
m (x) < r
where
8o
H0
og
7
8n
Mi
Ho
Similarly, when (x) 1, the right-hand side of Eq. (36) simplifies to:
(0(x)
< -
where
8
14
70
81
Pg
which completes the proof.
D.5 BAYES-OPTIMAL CLASSIFIER AND REJECTOR FOR GENERALIZED L2R
We next derive the Bayes-optimal classifier and rejector for the generalized L2R risk in Eq. (14), which we restate below:
Ra (h, r) v/ (t. + c- (r(x) = 1),
(37)
where a : [0, 1]K + R4, is a general function, and encompasses several common metrics (Lipton al., 2014; Menon al., 2013; Narasimhan et al., 2015a).
One may equivalently write Eq. (37) in terms of the confusion matrix C(h,r),
(5( LiEG, Ejji Ciy(h.r) Rrel (h, r) 2/ (iec, Eje ( Cis(hrr)"
ΣIEGH Ejst Ciy(h, EiEOR Ejelo Ci,(hrr) + 1e-e--1 (1-Eo((h.r))
i
Allowing for stochastic mechanisms F that are defined by distribution over classifier-rejector pairs, we would like to minimize:
EiEG, Ejst Cy(F)
EiEOR Ejer Cif(F)
Eieon Ejery Cis(F) tc. (1- (1-Ea(())
min vi Eiec, Ejeny Ci)(F)
or equivalently:
④n (C(F))
(x(((P))
cc. E1-E TH (C(P)))
min
(38)
(C(P)) Tx(C(F)))
where d& (C) = EiEg, Ejet (F)(F) and TH (c( = CieleCCy(B
Theorem 7 (restated), For any non-linear v. there exists coefficients (0), vl0 ERK iE [K [K+1] and a parameter A A1-1, such that, the generalized L2R in Eq. (14) minimized by a stochastic mechanism that for any x, predicts using (h6), r(0) with probability vs:
h (x) arg max ulf) my(x), i [K 1];
(x) =1
max ( ()(x)
6 Σ
my (x) c, iE [K +1].
22

---

Published as a conference paper at ICLR 2024
Proof. One may reformulate Eq. (38) optimization over the space of all confusion statistics realizable through distribution over classifier--rejector pairs C, or equivalently over a smaller space of transformed confusion matrices:
C' = { T), where Ø (cI(C)....,, (C)( and π (TI(C),..... TA CC
We can then solve Eq. (38) by solving:
min (#.T)EC
ΦK + (1-
Σ T
(39)
T1
KK
We know from Lemma that C is convex; consequently, Therefore any point (Ø. π C' can be expressed as a convex combination of extreme points of C'. In fact, following Proposition 10 in Narasimhan et (2022b), any (Ø: π C' can be expressed as convex combination of K + extreme points (Φ(11, (,))",,,. (Ø (K +1), π (K+1)), each of which is unique linear minimizer over C²:
easy to see that C' is also convex.
(Φ 11) E arg min
Σ ((.
(3)
w Φx
4k
for coefficients w(() g()) E BRK E K IJ. Therefore this is also true for the minimizer (db", )²) E C' Eq. (39).
All that remains to show is that these K + linear minimizers are realized by K + classifier-rejector pairs of the form in the theorem statement. To show this, we note that for coefficients w(() g9() E R minimizing the linear objective over C²:
min (C)
Σ
w OR
Tk
h
is equivalent to minimizing the same objective over the boundary points of C", and equivalently, over deterministic classifier-rejector pairs:
min
Σ w (c(CCh,r) +
Σ q
(C(h,))))
(40)
Expanding the above objective, we get:
Σ I"
E. ( = 0, Gx)] + Σ
9k
which is the same as:
Eg
Σ
W
[x(x) 1 # hz)), 0) Σ
4
Σ
Tz(2) 1(r(x) 0)
y
yEGr
or:
Σ
W
(8) [
my
(x)
w [+aa) Ma( (x)
(8)
Σ l
ny((r) 1(((=)=0)
y/
The minimizer of Eq. (40) then takes the form:
h0 (x) E arg max
(1) [p) (z);
SE(T.
1 (x) =1
vE[L] [
max w
(x) <
(wl (
+ (6) (z)
VE[L]
Setting (0) w/ and uy
wl + qvl + the above is equivalent to:
h (x) arg max u
(t)
ml (x);
DE[L)
max (1) vE[r]
(x) Σ
TTy(x)
DE[L]
It thus follows that the minimizer (0" = (#(C(F))) ग (C(F*)) to Eq. (39) is real- ized by a stochastic mechanism F" that randomizes over the K classifier-rejector pairs (M(1), (1))), (1))),..., (K+), p(K+1)).
23

---

Published as a conference paper at ICLR 2024
Algorithm 3 Lagrangian-based Plug-in for Balanced Error
1: Input: Rejection cost Pre-trained p X' - Ar. Sample S
2: Parameters: Iterations M, I, Step-sizes Eur Ea. Initial (0)) E (0, kK* Lower bound K > 0
3: For m M
4: 16m) (I) arg vE[L] uyy") (z))), where uy (mm)
(m)
"(sl
5: Initialize (m E R
6: For = 1100 totoT -1 (mit) + Ev (a! (mm) - E ( Gui) Ak E [K]
-1
(mm,f+1) 7: Mk
K
8:
plm,+t1 = =
maxye[4] uy
(m))
P2(x)) Ey v/(m)
-py Ppy - c,
where (())
(m,++1)
9:
[m]
10: End For
(m+1) (m) - Ea.
(Ak (m..) (a/- êb (h(m), r(in.Ti)
11: 0k
Oxk
(m+1) proj K-x] (())) where projta, [ (z) max min b).
12:
13:
End For Return: (h(M), (((1),((MMTT) ((M.T)
E PLUG-IN APPROACH: FURTHER DETAILS
We provide further details about the plug-in in approach in $4.
E. RE-PARAMETERIIZNG THE REJECTOR FOR THE BALANCED ERROR
One can further prune the search space multipliers ji by re-parameterizing the rejection criterion in Eq. (13) to search over only parameters. To this end, using the fact that Lye Pr(x) =
we re-write the criterion as:
max WE[L] llv
(x(
Py( - Σ (Mo') - PK) pv(xx) pxx Σ NE((L]
Py Pv c,
WE(L
which is the same as:
max
(x(
(x) -
Σ (ix - pk)
Σ
(x) - pk
WE[L]
E'ELL]
kE[K-1]
V'EGr
This can be equivalently re-paramterized as:
max
1
P2) < Σ
Por(()) (x)
Σ
Σ
de Pg) -
VE[ 0lv)
3/ J'ELL] [
kE(K
V'EG2
where d₂ fix AK. for l [K- - 1), and 2 pix
Note that in practice, one is often prescribed a target rejection rate, and picks the rejection cost c to achieve this rejection rate. For fixed Å!,..., Å one may equivalently pick the threshold (instead of cost c) to reach the desired rejection rate. So given target rejection rate, all one needs to do is to apply brute-force search to tune the remaining K - unknowns to minimize the balanced error on a validation set, with the threshold & set to a percentile that matches the desired rejection rate. When K = 2 (head and tail), i.e., S = f0, 1}, this would mean that we only have single parameter Ån AÃ وa to tune, which can be efficiently done using simple line search.
E.2 LAGRANGIAN-BASHR PLUG-IN APPROACH
As an alternative to plug-in in approach in Algorithm 1, we explore Lagrangian- bagrangian-based approach that handles the constraints more intricately. We begin by introducing multipliers. μ R& for the K
24

---

Published as a conference paper at ICLR 2024
0.35
0.30
Chow
Standard Ereo
0.30
Standard Error
0.3
Standard Enror
Chow [BCE]
Plug [Balanced]
0.20
0.20
0.2
0.15
0.15
Chow
Chow
0.10
C55
0.1
CSS
Chow [BCE]
Chow [BCE]
0.05
Plug-in [Balanced]
Plug-in [Balanced]
0.00
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
Proportion Rejections
Propertion Rejections
Proportion of Rejections
(a) CIFAR-IU 100
(b) ImageNet
(c) iNaturalist
Figure 4: Balanced L2R: Standard 0-1 error as function of proportion of rejections.
0.5
0.30
0.4
CSS
Standard Error
0.4
Standard Error
0.25
Chow [DRD]
0.3
0.20
Plug-in
0.3
Standard
0.15
0.2
0.2
Chow
Chow
0.10
CSS
CSS
Chow [DRO]
0.1
Chow [DRO]
0.05
Plug-in [Worst]
Plug-In [Worst]
0.0
0.0
0.00
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
Proportion of Rejections
Proportion of Rejections
Proportion of Rejections
(a) CIFAR-100
(b) ImageNet
(c) iNaturalist
Figure 5: Worst-group L22:: Standard error as function proportion rejections.
constraints in the optimization problem in Eq. (7) and writing out the Lagrangian:
C(,,r, Σ
. (y h(z),r(x) 0, E Gk) + (r((x) 1)
ak P
kE(K]
Σ
pa (m.-(K-((((e)) -0, Gk) - -ak),
KE[K]
and formulate an equivalent saddle point optimization problem:
min max
L(h, a),
(41)
a. HER
For fixed a, we can solve the min-max problem over h and by alternating between gradient- ascent updates the multipliers μr:
(2) (1+1) = Pk + En (ax (P(()) = 0, y G+)), Vk E [K].
for step size E,, > O, and a full minimization over h and r. The procedure outlined in Algorithm then solves the saddle point optimization problem in Eq. (41) by performing gradient-descent and the combination the gradient- and full minimization procedure described above over h, r and μ.
worth noting that this Lagrangian procedure is made possible by viewing Eq. (7) as an opti- mization problem over the space of the space of realizable confusion statistics C (Narasimhan, 2018; Narasimhan et al., 2022b), which we can then show is a continuous constrained optimization problem that is amenable be solved with Lagrangian style updates.
25

---

Published as a conference paper at ICLR 2024
1.0
Chow
Chow
Teil Erer HHad Error
Tail Error Hoad Error
0.5
Error Head Error
Chow [BCE]
Chow [BCE]
Plug-in [Balanced]
Plug-in [Balanced]
0.6
CSS
0.05
0.3
Chow [BCE)
Plug-in
0.2
0.1
-0.05
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
0.00
0.25
0.50
0.75
Proportion of Rejections
Propertion Rejections
Proportion of Rejections
(a) CIFAR-IU 100
(b) ImageNet
(c) iNaturalist
Figure 6: Balanced L2R: Difference between tail and head errors as a function of proportion of rejections.
1.0
0.6
0.125
Tail Error Head Error
0.8
Tail Error Head Error
0.5
Error Head Emro
0.100
0.075
CSS
0.3
CSS
CSS
Chow [DRO] Plug-in [Worst]
Chow [DRO]
Chow [DRO]
0.4
0.2
Plug [Worst]
0.025
Plug (Worst)
0.2
0.1
0.000
0.0
-0.025
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
0.00
0.25
0.50
0.75
Proportion of Rejections
Proportion Rejections
Proportion Rejections
(a) CIFAR-100
(b) ImageNet
(c) iNaturalist
Figure Worst-group L2R: Difference between tail and head errors as a function of proportion of rejections.
F ADDITIONAL EXPERIMENTAL RESULTS
We discuss the data splits, syper-parameter choices and further implementation details in our exper- iments. also include additional experimental plots. All results are averaged over 5 trials. We report 95% confidence intervals in Table 2.
F.1 HYPER-PARE PARER-PRRAMEERR CHOICES
We apply the same data pre-processing as Menon al. (2021a). We trained the models using SGD with momentum of 0.9 and weight decay of 10 We summarise the hyper-parameter choices in Table 3 below.
Dataset
Belasses
Tail prop.
Model
Base I.R
Schedule
Epochs
Batch size
CIFAR 100-1.T
100
50,000
10,000
0.03
CIFAR ResNet-32
0.4
anneal
256
128
ImageNet-LT
1,281,167
50,000
ResNet-50
0.4
cosine
200
512
INaturalist 2018
8143
437,513
24.426
0.12
ResNot-50
0.4
cosine
200
1024
Table 3: Dataset details and hyper-parameter choices.
For 100, apply warm up with linear learning rate for 15 steps until reach the base learning rate. We apply a learning rate decay of 0.1 at the 96th, 192nd and 224th epochs.
For ImageNet and iNaturalist, apply reach the base learning rate. We apply a learning rate decay of 0.1 at the 45th, 100th and 150th epochs.
up with linear learning rate for steps until
26

---

Published as a conference paper at ICLR 2024
F.2 DATASET SPLITS
The train, test and validations samples all follow the same long-tailed label distributions. Each dataset comes with an original test set with equal proportions of all labels. We re-weight the samples the original test sel to replicate the same label proportions the training set. Furthermore, we hold out 20% the original test set as a validation sample and use the remaining as the test sample.
F.3 IMPLEMENTATION DETAILS
For the proposed plug-in method for the balanced error (Algorithm 1), set the number of iterations M to 10, and tune the single parameter Åo ioo A1 (see Appendix E. from three values {1, 6, 11}. For the proposed plug-in method for the worst- iterations 7' 25 and the step-size & to for the inner call Algorithm I, we M 10 and tune the parameter Åo from {1, 611.
error (Algorithm 2), we set the number of outer
We implement the cost-sensitive softmax (CSS) loss of Mozannar & Sontag (2020) described in Equation 3 in their paper. We set the cost vector c(I),-..,c(l 1) this loss to c(i) 1 # i), Vi E [T. and c( + 1) to the rejection cost c.
For Chow [Balanced], there exists a plethora of options the long-tail literature to train the base model (see $2.2 for brief list of representative approaches). We pick the logit-adjusted cross-entropy loss of Menon et al. (2021a) as a representative approach.
For Chow [DRO]. prescribed in Jones et al. (2021), we use the group DRO approach proposed in Sagawa et al. (2020), but modify the inner weighted minimization step to use a logit-adjusted loss (Narasimhan & Menon, 2021; Wang et al., 2023). This modification the approach of Sagawa et al. (2020) to multi-class classification with a large number of classes. Their method requires tuning step-size for DRO and regularization parameter C. We pick these parameters from the sets {0.0005, 0.001 and {1.0, 2.0} respectively, by maximizing the worst-group error on the validation sample.
necessary to adapt
F,4 TRADE-OFF PLOTS: FURTHER DETAILS
To generate the trade-off plots in Figure 3-7 for each method, we train rejectors with different rejection rates. For this, one may vary the cost parameter c, or equivalently, vary the rejection threshold the case of Chow's 's rule and the threshold f in the proposed plug-in method (see Appendix E. For target rejection rate, this can be done with a simple percentile computation.
For the CSS baseline, we re-train a model for different values of c in 0..0,0.1,0.3 0.75, 0.85, 0.91, 0.95, 0.97, 0.99). Unfortunately, we find that with the ImageNet and iNaturalist datasets, the resulting models do not exceed a rejection rate of 40% and 75% respectively, despite using the entire range of с E [0, 1].
F.5 ADDITIONAL PLOTS
We present additional plots of the standard 0-1 error as function of rejection rate for different methods in Figures 4-5, We also present plots of the difference between the tail and head errors as function of rejection rates in Figures 6-7.
F.6 COMPARISON TO EXHAUSTIVE SEARCH OVER
We repeated the CIFAR-100 experiments in $6 choosing the multiplier parameter from finer grid of values: (0.25, 0.5, 0.75. 113. We additionally replaced our heuristic procedure $4.2 with exhaustive grid search group prior a, choosing the head-to-tail ratio from the range {0, 0.01, 0.02............................ 1.0). We pick the parameter combination that yields the lowest balanced error on the held-out validation sample.
We show below the balanced error on the test and validation samples. Although the grid search provides gains the validation set, the test set, heuristic approach picking the multipliers
27

---

Published as a conference paper at ICLR 2024
and group priors yields metrics that are only slightly worse than grid-search. Moreover, the differences are within standard errors.
Test
Validation
Chow
0.509 + 0.002
0.498 + 0.011
Plug-in [Balanced]
0.291 + 0.008
0.282 = 0.007
Plug-in [Balanced, grid search]
0.284 + 0.007
0.264 + 0.008
28


Reviews:
[{"review_id": "a88oEOQJMp", "reviewer": "Reviewer_RJqn", "summary": "The manuscript considers the problem of learning optimal classifiers with reject option, i.e., there's a certain budget, and a fixed cost, for refraining from making any predictions on test instances. The problem of 'learning to reject' has been studied before, but mostly in the setting when the performance metric of interest is classification accuracy (or 0-1 loss). In this work, the authors consider more general and practical performance measures, balanced error and worst-group error in particular. The authors derive Bayes optimal classifiers (and rejectors) for the general measures, and provide a practical algorithm for estimating them with samples. \n\nTwo key contributions: 1) Clear formulations of the learning to reject problem, various metrics of interest, and deriving Bayes optimal forms for the different metrics. While general performance measures have been considered before in different supervised learning settings, deriving general results for classifiers with reject option is novel as far as I can tell. 2) Algorithm for estimating the classifiers and rejectors in practice for general performance measures, and supportive empirical results on standard datasets.\n\nOverall, I find the paper to be sufficiently interesting to any ML audience, with technical depth and contributions par for the venue. I've some questions for the authors listed below, but the paper is a clear accept for me.", "questions": "I would like the authors to address the questions in the 'weaknessess' section in their rebuttal.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As I mentioned in my summary the paper makes key contributions, and each of the contributions involves good technical rigor and presentation which I very much appreciate: 1) Clear formulations of the learning to reject problem, various metrics of interest, and deriving Bayes optimal forms for the different metrics. While general performance measures have been considered before in different supervised learning settings, deriving general results for classifiers with reject option is novel as far as I can tell. 2) Algorithm for estimating the classifiers and rejectors in practice for general performance measures, and supportive empirical results on standard datasets.\n\nThe paper is well-written, ideas flow coherently, related results are placed well in context, and it was a pleasure to read!", "weaknesses": "These are more nit picks than weaknesses.\n1. Some intuitive justification for the Bayes optimal forms would have been useful. As it stands, the material is somewhat dense, and for a reader outside the area, some of these results might be confusing. For instance, I would love to know if there's an intuitive explanation for the 'discount' factor $-\\mu^*_{[y']}$ in (2). \n2. I found it a bit of a leap to go from deterministic classifiers in Theorem 2 to stochastic classifiers in Theorem 5. Balanced error does involve weights that are distribution dependent, while general $\\psi$ metrics studied in Theorem 5 I believe are functions that do not depend on the distribution in any way other than via the arguments $e_j(h,r)$'s. So where is the stochasticity arising from? Also, it would be good to draw corollaries where for some simple forms of \\psi functions, you indeed get deterministic classifiers and rejectors (when $h^{(1)} = h^{(2)}$ holds, etc.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B2uiISOBvH", "reviewer": "Reviewer_iFdp", "summary": "This paper derives and examines the Bayes optimal solution to minimizing the balanced error metric when a reject option is available (rejection is assumed to have a fixed cost). This problem is much more challenging than learning to reject for plain error because, as the authors show, the rejection thresholds for the various classes are coupled. Moreover, no reduction to cost sensitive learning with fixed per-class misclassification costs exist, since these costs change depending on the fraction of examples in each class not rejected.\n\nGiven the challenges, the authors present an approximate scheme for minimizing balanced-error with a reject option, and they compare its effectiveness to recent methods for learning to reject on 3 image classification datasets. The proposed method out-performs or matches the compared-to methods across all datasets.\n\nAdditionally, the authors formulate the Bayes optimal solution for minimum balanced error rate with rejection to one for any metric that is a function of the per-class error rates. This allows for minimizing the maximum per-class error rate, and the G-mean metric; as well as for balancing error rates across an arbitrary partition of classes -- e.g., balancing the error rate across the set of frequent classes and the tail classes.", "questions": "1) Is it possible to say how much grid search over the space of lagrange multiplers is needed to find a good solution?\n\n2) the proposed optimization scheme finds a fixed point of the alpha parameters for given values of lagrange multipliers. But is this fixed point unique, and if not, are they all equally good?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is the first paper to formulate the Bayes optimal solution for minimum balanced error classification with a rejection option, and to provide a means of optimizing it. The problem itself is rather significant since there are high stakes scenarios in which it's desirable for a classifier to perform equally well across groups, and for a rejection or abstention option to be available so that cases can be escalated to humans for more careful consideration.\n\nThe experiments reasonably demonstrate the method's effectiveness, and the authors generalize the form of the given solution to metrics other than balanced accuracy.", "weaknesses": "The major weakness of this paper is that the proposed optimization scheme is only approximate and an analysis of the gap is not given. Is it possible to say how much grid search over the space of lagrange multiplers is needed to find a good solution? Also, the proposed optimization scheme finds a fixed point of the alpha parameters for given values of lagrange multipliers. But is this fixed point unique? And if not, are they all equally good? These questions are not addressed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sjadiBHyEg", "reviewer": "Reviewer_RZqs", "summary": "This paper considers the problem of classification with rejection when data distribution is long-tailed. In this case, metrics considering the data distribution such as balanced error is more appropriate than traditional misclassification error. For the case when learning a classifier and a separate rejector, authors derive corresponding Bayes optimal solutions for the problem setting, showing many existing methods are not optimal for metrics such as balanced error. Authors then propose a modification method based on the derived Bayes optimal solution, and empirically show its superiority.", "questions": "This paper considers the learning setting where a classifer and a separate rejector function exist. There is also another framework learning solely one classifier and later uses its output distribution over labels to conduct abstention. Is it impossible for this approach to derive Baye optimal solutions, or it is simply not the scope of the paper?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper considers an important problem setting combination, learning with rejection and class-imbalanced distribution.\n- The analysis is rigorously conducted with high quality and significance.\n- The paper is overall well structured and well written. It is easy and joyful to follow.\n- The paper provide appropriate literature reivew for related work.", "weaknesses": "Limit of the proposed framwork is not properly addressed. For example, are there any popular metrics not covered?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0631RSpvPM", "reviewer": "Reviewer_91tX", "summary": "This paper works on learning to reject (L2R) under long-tailed scenarios. They find that Chow's rule is suboptimal for this setting and propose a new approach with theoretical guarantees. Extensive experiments on benchmark datasets validate the effectiveness of the proposed approach.", "questions": "Please see the \"Weaknesses\" section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written. Even those unfamiliar with L2R can easily understand the setting.\n- The setting is novel and meaningful, since the long-tailed setting is quite common but rarely studied in the context of L2R.\n- The proposed method is novel and interesting, and the theoretical results are not trivial.", "weaknesses": "- If I understand correctly, the solution of the optimization problem in equation (9) seems to be heuristic. Is $\\mu$ not optimized, but selected from a predefined set? I am afraid that such solutions may not lead to an optimal solution. Will the authors provide some theoretical or empirical analysis of this problem and prove that the solution can be close to optimal?\n\n- What is the candidate value of $\\mu$? The authors say that they propose to do a grid search over $\\mu$, but what's the search space? If the search space is very large, the speed of the algorithm may be slow.\n\n- In the experimental section, only two compared methods are used. I am not sure if more compared methods are needed to validate the effectiveness of the proposal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)