Improved Balanced Classification with Theoretically Grounded Loss Functions
Authors: Corinna Cortes
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2025 poster ()
Keywords: balanced loss
imbalanced data
consistency
surrogate loss
learning theory
Primary area: theory

Abstract: The *balanced loss* is a widely adopted objective for multi-class classification under class imbalance. By assigning equal importance to all classes, regardless of their frequency, it promotes fairness and ensures that minority classes are not overlooked. However, directly minimizing the balanced classification loss is typically intractable, which makes the design of effective surrogate losses a central question. This paper introduces and studies two advanced surrogate loss families: Generalized Logit-Adjusted (GLA) loss functions and Generalized Class-Aware weighted (GCA) losses. GLA losses generalize Logit-Adjusted losses, which shift logits based on class priors, to the broader general cross-entropy loss family. GCA loss functions extend the standard class-weighted losses, which scale losses inversely by class frequency, by incorporating class-dependent confidence margins and extending them to the general cross-entropy family. We present a comprehensive theoretical analysis of consistency for both loss families. We show that GLA losses are Bayes-consistent, but only $H$-consistent for complete (i.e., unbounded) hypothesis sets. Moreover, their $H$-consistency bounds depend inversely on the minimum class probability, scaling at least as $1/\mathsf p _{\min}$. In contrast, GCA losses are $H$-consistent for any hypothesis set that is bounded or complete, with $H$-consistency bounds that scale more favorably as $1/\sqrt{\mathsf p _{\min}}$, offering significantly stronger theoretical guarantees in imbalanced settings. We report the results of experiments demonstrating that, empirically, both the GCA losses with calibrated class-dependent confidence margins and GLA losses can greatly outperform straightforward class-weighted losses as well as the LA losses. GLA generally performs slightly better in common benchmarks, whereas GCA exhibits a slight edge in highly imbalanced settings. Thus, we advocate for both GLA and GCA losses as principled, theoretically sound, and state-of-the-art surrogates for balanced classification under class imbalance.

Improved Balanced Classification with Theoretically Grounded Loss Functions
Corinna Cortes
Mehryar Mohri
Yutao Zhong Google Research New York, NY 10011
Google Research New York, NY 10011
Google Research & CIMS New York, NY 10011
corinna@google.com
cchri@google..oom
yutaozzhngg@poogee.coo
Abstract
The balanced loss is widely adopted objective for multi-class classification der class imbalance. By assigning equal importance to all classes, regardless their frequency, it promotes faireess and ensures that minority classes not overlooked. However, directly minimizing the balanced classification loss is typ- ically intractable, which makes the design of effective surrogate losses central question. This paper introduces and studies two advanced surrogate loss families: Generalized Logit-Adjusted (GLA) loss functions and Generalized Class-Aware weighted (GCA) losses. GLA losses generalize Logit-Adjusted losses, which shift logits based on class priors, the broader general cross-entropy loss fam- ily. GCA loss functions extend the standard class-weighted losses, which scale losses inversely by class frequency, by incorporating class dependennnd confidence margins and extending them to the general cross-entrops family. We present a comprehensive theoretical analysis of consistency for both loss families. We show that GLA losses are Bayes-consistent, but only H-consistent for complete (i.e., unbounded) hypothesis sets. Moreover, their H--consistnncy bounds depend in- versely on the minimum class probability, scaling at least as 1/Pmin- In contrast, GCA losses are H-consssteent for any hypothesis set that is bounded or complete, with 3K-consistency bounds that scale more favorably as L/VPmin offering sig- nificantly stronger theoretical guarantees in imbalanced settings. We report the results of experiments demonstrating that, empirically, both the GCA losses with calibrated ftass-dependent confidence margins and GLA losses can greatly out- perform straightforward class- weighted losses well the LA losses. GLA generally performs slightly better in common benchmarks, whereas GCA exhibits slight edge in highly imbalanced settings. Thus, we advocate for both GLA and GCA losses as principled, theoretically sound, and state-of-the-art surrogates for balanced classification under class imbalance.
Introduction
Class imbalance is prevalent challenge in real-world multi-class classification problems. Appli- cations such as medical diagnosis, fraud detection, and rare event prediction often involve highly skewed label distributions, where small subset of classes dominate data, while others, sometimes the most critical, are heavily underrepresented. Standard training objectives, such as minimizing the unweighted cross-entropy loss, tend be biased toward majority classes, leading to poor performance on minority classes and undermining the faimess, soundness and reliability of learned models.
To address this issue, widely studied approach is minimize the balanced loss, which assigns equal importance to all classes regardless of their frequency in the training data [Chan and Stolfo, 1998, Brodersen et al., 2010, Kotlowski et al., 2011, Menon al., 2013, Cao et al., 2019, Menon
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

et al., 2021, Cui et al., 2019]. This promotes faimess by equalizing performance across demographic groups [Khalili et al., 2023, Hardt et al., 2016] and ensures that minority classes are not overlooked in long-tailed datasets [Feldman, 2020, Zhang et al., 2023] (see Appendix A). It is also crucial in federated learning. where data imbalances across clients can lead biased models that favor heavy users [Li al., 2021, McMahan et al., 2017, Mohri et al., 2019]. By reweighting the loss contributions from different classes, the balanced loss promotes equitable treatment of all labels and has been shown to better align with metrics such as balanced accuracy and macro-F1. However, directly optimizing the balanced classification loss is typically intractable in practice. Thus, the design of effective surrogate losses that are tractable to optimize is central challenge in imbalanced learning.
This paper introduces and studies two families of surrogate losses: Generalized Logit- Adjis--djstted (GLA) loss functions and Generalized Class-Aware weighted (GCA) losses. GLA losses generalize Logit-Adjusted losses [Menon et al., 2021], which shift logits based on class priors, to the broader general cross-entropy loss family [Mao et al., 2023f]. GCA loss functions extend the standard class- weighted losses, which scale losses inversely by class frequency, by incorporating class-dependent confidence margins and extending them to the general cross-entropy family.
We present a comprehensive theoretical analysis of their consistency. We show that GLA losses are Bayes-consistent [Zhang, 2004a, Bartlett et al., 2006, Zhang, 2004b, Tewari and Bartlett, 2007, Steinwart, 2007], but only J[-consistent/ [Awasthi et al., 2022a,b, Mao et al., 2023f,b] for complete (i.e.. unbounded) hypotheses. Moreover, their H-coossisency bounds depend inversely on the minimum class probability, Pmni. scaling at least as 1/Pmin- In contrast. GCA losses are HC-consistent for any hypothesis set that is bounded or complete, with H-consistency bounds that scale more favorably as 1/ offering significantly stronger theoretical guarantees in imbalanced settings.
We also report the results of experiments demonstrating that, empirically, both the GCA losses with calibrated class-dependent confidence margins and GLA losses comfortably outperform straight- forward wless-weighted losses as well as the LA losses. GLA generally performs slightly better in common benchmarks, whereas GCA exhibits slight edge in highly imbalanced settings.
Taken together, our results establish GLA and GCA losses as theoretically grounded and practically effective classification algorithms for tackling class imbalance in multi-class learning. Their comple- mentary strengths make them well-suited for a wide range of real-world applications where fairness across classes is paramount.
The rest of this paper is structured as follows. Section reviews fundamental concepts related to class imbalance in multi-class classification, introduces the balanced loss (Section 3.1), discusses existing surrogate losses (Section 3.2), and highlights the limitations of current approaches (Section 3.3). Sec- tion 4 introduces two novel surrogate loss families: Generalized Logit-Adjusted (GLA) (Section 4.1) and Generalized Class-Awe Aware weighted (GCA) losses (Section 4.2). A comprehensive theoretical analysis of their consistency and margin bounds is provided in Section 5 and Appendix B. Finally, Section reports empirical results on CIFAR-10, 10, CIFAR- -00, and Tiny ImageNet, demonstrating the effectiveness of our algorithms, which are based on the minimization of these loss functions.
2 Preliminaries
Let X denote the input space and y [m] := (1...., n. represent the set of'n possible labels. We consider data distribution D over the combined input-label space X' y. Our hypothesis set, denoted by H., consists of functions that map an input-label pair (z, y) to a real-valued score, h: Xxx y + R. We denote by p(x) the marginal probability density of an input æ. and by pạy) the marginal probability of a class label y. The minimum class marginal is defined as Pmain = mingey Pt)). The conditional distributions p(= y) and p(y] a:) represent the probability of input x given label y. and label y given input v, respectively.
Let Han denote the set of all measurable functions, and a E:H x Xxx y + IR the loss function adopted to penalize inaccurate predictions. Then, the generalization error of a hypothesis h H is defined as its expected loss: (h) within the hypothesis set H. is the best-in-class generalization error, R2 (H)= inf Re(h).
(e(hr)/e_hhha, x.)]. The lowest possible generalization error achievable
For any input x XX, hypothesis is e H. assigns a predicted label h(x) by selecting the class with the highest score: h(x) argmax h(x, y) (ties are broken by choosing the highest index). The
2

---

standard zero-one loss function for multi-class classification is defined as (0-1(h, = a which is 1 the prediction is incorrect and 0 otherwise.
The margin Ph (rr y) for predictor h E H on a labeled example (a, y) measures the confidence of the correct prediction: Ph (x.y) y) h(x, maxy'+y hx,, 1/)) This is the difference between the score of the true label y and the highest score among all other labels y'.
The generalization error of a hypothesis / can also be expressed as the expectation of the conditional error over the input x: Re(h) = Ez x)), where x) Egey p(y x) x, y). The best-in-class conditional error ej (H. inl Cz(h, The difference, A,,,r C₂ (h) ez (H, is termed the conditional regret for the loss function l. These concepts and definitions are useful our analysis of the consistency of loss functions.
Background and Related Work
We first review fundamental concepts related to class imbalance in multi-class classification, introduce the balanced loss, discuss existing surrogate losses, and highlight the limitations of current approaches.
3.1 Class Imbalance and Balanced Loss
Class imbalance in multi- clats- settings arises when the label distribution p(y) is highly skewed, with some classes (often referred as "tail" labels) having much lower probabilities of occurrence compared to others (the "head" or majority classes). In such cases, many recent studies [Chan and Stolfo, 1998, Brodersen et al., 2010, Kotlowski et al., 2011, 1, Menon et al., 2013, Cao al., 2019, Menon et al., 2021, Cui et al., 2019] suggest that the balanced loss (LBAL) is more appropriate loss function than the standard zero-one loss. The balanced loss assigns equal importance to all classes, irrespective of their frequency, and is thus viewed as promoting fairness by equalizing performance across demographic groups [Khalili et al., 2023, Hardt al., 2016, Conitzer et al., 2019] and ensuring minority classes are not overlooked in long-tailed datasets [Feldman, 2020, Zhang et al., 2023] (see Appendix A). is also crucial in federated learning, where data imbalances across clients can lead to biased models that favor majority users [Li et al., 2021, McMahan et al., 2017, Mohri et al., 2019].
The balanced loss reduces the influence of class imbalances by averaging the per-class loss by weighting the error for each example (h, 2,,.) y) by the inverse of the probability of the true class p(y):
(AL Cha (,, y) In(x)ev
p(v)
The following lemma characterizes the best-in-clas conditional error and the corresponding con- ditional regret for the balanced loss. For any input æ X, we denote by H(r) the set of labels that be predicted by hypotheses in H for that input: H(x) = (h(x):h H). The proof of Lemma is provided in Appendix D.
Lemma For any I X, the best-in-class conditional error and the conditional regret for BAAL can be expressed as follows:
Ciaa (H, = Σ x()l2)
p(y (x)
P(y x)
p(h(x)) a))
(h) = max
yey (④))
max geH(x)
p(y)
yeH(x) p(v) p(h(z))
3.2 Existing Surrogate Losses for Balanced Learning
Several surrogate losses have been proposed for optimizing the balanced loss. Here, review two prominent Bayess-onsistent examples:
Class Mlsss-eeihheed Cross-Entropy A common strategy is to use the class-weighted cross-entropy loss [Xie and Manski, 1989, Morik et al., 1999], which adjusts the standard cross-entropy loss by weighting each example inversely proportional to its class frequency p(y):
Ma.w)
EwCB x,))
p(v) log
Evey (yeye)((.w)))
As pointed by [Byrd and Lipton, 2019], the limitation of (wCE that in separable cases, class- weighted cross-entropy may still yield solutions with zero training loss that do not adjust decision
3

---

boundaries meaningfully toward minority or majority classes. This is because class weighting does not influence the classifier once perfect separation is achieved. As a result, the method fails to address imbalance in such regimes.
Logit-Adjusted (LA) Losses: More recently, Menon al. [2021] introduced Logit-Adjusted (LA) losses. These losses modify the logits (outputs before softmax) based on class priors, typically by adding a term 7 log(p())) with 0:
(((ss))+
LLA (h, (,) log
(
As we will show in Section 5, ELA is not Bayes-consistent for the balanced loss when T
A detailed discussion of other approaches for handling class imbalance, including alternative loss weighting schemes [Cui et al., 2019, Fan et al., 2017, Jamal et al., 2020, Wang et al., 2023, 2025, Li et al., 2025], margin modifications [Masnadi -hirraii and Vasconcelos, 2010, Iranmehr et al., 2019, Zhang et al., 2017, Cao et al., 2019, Tan et al., 2020, Jiawei et al.. 2020], data augmentation and sampling techniques [Kubat and Matwin, 1997, Wallace et al., 2011, Chawla et al., 2002, Yin et al., 2018], threshold adjustments [Fawcett and Provost, 1996, Provost, 2000, Maloof, 2003, King and Zeng, 2001, Collell et al., 2016, Menon et al., 2021, Zhu et al., 2023], and weight normalization methods [Zhang al., 2019 Kim and Kim, 2019, Kang et al., 2020] is included in Appendix A.
3.3 Limitations of Existing Approaches
Despite their usefulness, existing surrogate losses and related methods admit some limitations. Class- weighted cross-entropy often has minimal effect in settings where data is easily separable. In such cases, solutions that achieve zero training loss (perfect separation) remain optimal even with class weighting, failing to shift decision boundaries effectively towards dominant classes as might be desired [Byrd and Lipton, 2019]. Logit-Adjusted (LA) losses, as we will demonstrate in Section 5, not Bayes-consistent for the balanced loss when the temperature parameter T Consequently, optimal tuning of T often lacks a theoretical guarantee, and the method itself offers limited flexibility, Other margin modification techniques [e.g.. Cao al., 2019, Tan et al., 2020] may not be Bayes- consistent for the balanced loss, even in simpler binary classification problems [Menon et al., 2021]. The drawbacks of other strategies beyond direct loss modification, such weight normalization. have also been previously noted [Menon et al., 2021].
4 Surrogate Loss Families
This section generalizes two surrogate loss families designed for learning with class imbalance: Generalized Logit-Adjusted (GLA) loss functions and Generalized Class-Aware weighted (GCA) losses. Both families are derived from the general cross-entropy (GCE) framework [Mao al.. 2023f]. For any (h, x y) E H x X y. the GCE loss is defined as:
Ma,v)
with VT((1) = -log(t) if ( (1- (0,
(acm(h, = 4/9
Eyeey ch(aar))
Specific choices of g recover well-known loss functions: q= 0 yields the logistic loss (or standard cross-entropy) [Verhulst, 1838, 1845, Berkson, 1944, 1951]; q E (0, 1) gives the generalized cross- entropy loss notable for its robustness to label noise [Zhang and Sabuneu, 2018]; and q corresponds to the mean absolute error loss [Ghosh et al., 2017].
4.1 Generalized Ldgit-Adjusted (GLA) Losses
A Generalized Logit-Adjusted (GLA) Loss modifies the logits within the GCE family by incorporating a muss-prior-based bias term, log (((())))((11)))))
hZx (okte(u))
ÍGLA (h, = 4
(4)
Eveyy Mxx,y/)+ 1n
The GLA loss family generalizes the Logit- (LA) loss with T 1. Specifically, when q == 0,
Eq. (4) recovers the LA loss with r previously defined in Eq. (3). Thus, GLA extends the concept

---

of logit adjustment to the broader GCE family. As will be detailed in Section 5.2, GLA losses are Bayes-consistent for any q E [0. 1). offering greater flexibility compared the original LA loss (whose limitations were discussed in Section 3.3).
The term inside the Tp function in Eq. (4) can be rewritten to highlight its behavior:
C ((x,))= (om(p(u))
ch(x,)) p(v) F
Evey e Mas/) 1nstot
Eyeychhass ch(aw)) p(()) i-
p(v) p(v)
In this formulation, the term (p(v")/(v)) acts as weighting factor in the denominator, effec- tively creating a pairwise label margin adjustment that depends on the relative frequencies of class y (the true class) and other classes y This mechanism encourages a larger separation (margin) when a rare class (low p(y)) and y' is a dominant class (high p(v')) and reduces the risk that scores for dominant classes overshadow those for rare classes.
4.2 Generalized Class-Aware (GCA) Losses
Generalized Class-Aware (GCA) loss introduces class sensitivity by inversely weighting the GCE loss by class frequency p(v) and incorporating class dass-dependent confidence margins Py:
e Masilos
1 Evey cleas
locA(h, (,,
V
(5)
p(v)
where p= (PI...., Pn) is a vector of positive confidence margin parameters for each class. The GCA formulation encompasses standard class-weighting as special case. For instance, the class-weighted cross-entropy loss (Eq. (2)) is recovered when q 0 and all confidence margins Py are set to 1. If
all Pg 1, Eq. (5) simplifies to: ÊGCA (h, y)
- Tr9
Entry chtx.wr) ). thereby extending the class-
h(x.0)
p(z)
weighted cross-entropy concept to the entire GCE family. The motivation for using the inverse of the prior in GCA remains the same for 1 as for 1. The parameter simply specifies particular loss within the generalized cross-entropy family, applicable in both standard and imbalanced settings. The inverse of the prior is used to align with the definition of the balanced loss, which reduces the influence of class imbalance by reweighting each example's ' error accordingly. This ensures that GCA losses benefit from consistency guarantees with respect to the balanced loss.
The introduction of distinct confidence margin parameters p is key aspect of GCA losses. These parameters allow for fine-tuned adjustments to the decision boundaries. By applying class-specific scaling with factors related to Py the logit differences [M(x, y) h( y ]-terms that inherently represent margins, the GCA loss (through an effective transformation to (h(z, y) h(x, y P/))) can more effectively separate dominant and rare classes, as such transformation modulates how confidently each class needs to be separated. Such margin adjustments, as highlighted by recent work of Cortes al. [2025], play a crucial role in effectively shifting decision boundaries across classes and mitigating imbalance. This, in turn, addresses the limitations of simpler class-weighting schemes mentioned in Section 3.3.
Note that while the values can be treated as tunable hyperparameters and freely tuned via cross- validation, the search can be effectively guided by focusing vectors [p*]s near [m]]]] where my denotes the number of samples in class k. as suggested by Cortes et al. [2025] and followed in our experiments. A similar derivation theirs, adaptable to setting, shows these values theoretically optimal in a separable case, providing justification and guidance for selecting Pk: for GCA losses. Empirically, we also found GCA losses to be robust variations in pr around these values. Consequently, while Pk can be tuned, the default choice of m performs well. When the number of classes n. is large, the search space can be further reduced by assigning identical Pk values to underrepresented classes and reserving distinct values for the most frequent ones.
For fixed hyperparameters, the computational cost of GLA and GCA losses is comparable to that of standard neural networks trained with cross-entropy loss (that is, logistic loss with softmax) and to that of the baselines. Our loss functions are adapted from the general cross-entropy family and both share similar convergence behavior and remain practical when optimized with commonly used optimizers such as SGD, Adam, and AdaGrad. While methods introduce additional hyperparameters, namely
5

---

Pk and in GCA losses and q in GLA losses, the value of Pt: has default choice (as discussed above), and q serves similar role to hyperparameters the baseline methods listed in Table 1 in Section 6, many of which also involve at least one extra tunable parameter.
5 Theoretical Analysis
In this section, we leverage Lemma to present a comprehensive theoretical analysis of the consis- tency for the two proposed surrogate loss families: Generalized Logit-Adjusted (GLA) losses and Generalized Class-Aware (GCA) losses.
5.1 Consistency Notions
A critical characteristic of surrogate loss function l,, used in place of a target loss function Lg. is its moyes-coonssstneyy [Steinwart, 2007]. This property ensures that a sequence of predictor {hn NeN within Hau (the set of all measurable functions) asymptotically minimizes the surrogate loss É it will also asymptotically minimize the target loss fg. Formally: lim Re (h.,) = Ri (Han)
lim R2 (h₂) Rig (Hal).. However, Bayes-consistency is an asymptotic concept and is defined only for the comprehensive class of all measurable functions Hall A more practically relevant and informative concept is that of CC-ooniste bounds. These bounds are non-asymptotic and tailored to a specific hypothesis class H. [Awasthi et al., 2022a.b, 2021a,b, b023a,b, Mao et al., 20,ea,,,c.d.eff, 20,.a.b,c.d.e.fgg Mohri et al., 2024, Cortes et al., 2024, Mao al., 2025c,a,b, Mao, 2025, Zhong, 2025, DeSalvo et al., 2025]). In the realizable setting, these bounds take the form:
Reg (h) R2, (3O) s [3 (h) - -x2 (3)))
Here, I is a non-increasing concave function such that ((0) = 0. In the more general non-realizable setting, the bound is augmented by minimizability gap, M,))) R2 (H) (HH,,))))))) (H,+)). This gap quantifies the difference between the best-in-class error and the expected best-in-class conditional error. The augmented bound is:
Re, (h) Rig (3C) Me, (3() s (M), (30) Me, (30).
As demonstrated by Mao et al. [2024h], Mohri and Zhong [2025], the minimizability gap is always non-negative and is bounded above by the approximation error A, (3() ()C) R (Han). i... 0 & (H) s (J)). The minimizability gap becomes zero when H Hall or, more generally, when the approximation error Ax()) O. In other cases, it is typically non-zero and offers more refined measure than the approximation error. In particular, K-consistency bounds imply Bayes-consistency when K KAll and generally provide stronger and more applicable guarantees.
5.2 GLA Losses
We now analyze the consistency properties of the GLA loss family. We establish that the LA loss only Bayes-consistent for 7 =1
CoressConsstency. It known that the Logit-Adjusted (LA) loss is Bayes-consistent with respect to the balanced loss when its temperature parameter is set to one, t = 1 [Menon et al., 2021]. We begin by establishing negative result: this consistency does not extend to other values of T.
Theorem 2. When 7 1, the LA loss LL is not Bayes-consistent with respect to the balanced loss (BAL-
The proof, which involves characterizing the Bayes classifiers for both the LA loss and the balanced loss, is detailed in Appendix F. In contrast, the following result establishes the Bayes-consistency of the GLA loss with respect to the balanced loss for any q E [0,
Theorem 3. For any g E [0, 1), the GLA Loss EGLA is Bayes-consistent with respect to the balanced loss ÉALL
The proof, provided in Appendix G, characterizes the Bayes classifiers for the GLA loss. Note that Theorem recovers the Bayes-consistency of the LA loss (when q 0) as a special case, consistent with [Menon et al., 2021].
H-- FC-Consistency Bounds. We first present counter-example (Figure 1) demonstrating that even when

---

T = (that is. for the standard LA loss, which is GLA with
100
q = 0). fLA is not H-consistent with respect the balanced loss
0.75
{AL for certain bounded hypothesis sets. In this example, con-
0.50
sidering a two-dimensional distribution where xi ~ U[O. 1] and
32 (f) with y following Bernoulli distribution (P(+1) = 3). if the hypothesis set consists of linear models with bounded weights, specifically {(v.y) - Wyy x: wyll 100). the best-in-class classifier for both the balanced loss and GCA loss is I2 = 0. However, the best-in-class classifier for the LA loss (with T= 1) differs and is not parallel 22- O. This implies that the LA loss with 7 = 1 is not H-consistent for this bounded hypothesis set.
-0.25
-0.50
GCA
-0.75 75
LA 1355
Bewenedd lina
1.00
DG
0.2
0.4
24
0.5
Figure 1: Counterexample to the H-consistency of &LA for bounded hypothesis sets.
This counterexample shows that GLA losses do not guarantee H-coosiisenccy for bounded hypothesis sets. The following theorem establishes that the GLA loss lCLA is H--consistett with respect to the balanced loss BAAT. if the hypothesis set H is complete that is, for every instance X, the scoring vectors spanned by H cover the entire space I=: (h(2;)): E H} IR". Naturally, bounded hypothesis sets cannot satisfy this condition. Note that complete set be strict subset of Hall For example, linear models with unbounded weights are complete, yet they do not equal Hall Note, the same positive result does not hold for LA losses with general TS. Being not Bayes-consistent, LA losses are not "C-consistent for complete hypothesis sets.
Theorem Assume that H. is complete. Then, for any q [0, 1), the following H-consistency bound holds for the GLA loss LGLA:
Rai (H) + MiBAL (H) S I' Reeaa (h) - REarA (H) + MeCLa (H)), REBAL (h) -
for q (0, 1). In the special case where the approximation error ARCLA (HC 0, the bound simplifies to:
where r(t)= LLE for q = O, and l'(t)= (pmin) I-a (1 (1-4)+
2tt
Puiin
REBAL (h) - Ri (H() & T(REGLA (h) Ri (3().
The proof, presented in Appendix H, consists of first defining a Gibbs distribution induced by h and next of applying a Pinsker-type inequality. Our technique is novel: it constructively upper- bounds the conditional regret of the balanced loss by that of the GLA loss, leveraging Lemma 1. Remarkably, when q Theorem 4 yields HC-oosissency guarantees for the LA loss with 1 under the completeness assumption, a significantly stronger guarantee that the previously established Bayes-consistency result of Menon et al. [2021]. The J-consistenccy bounds for GLA losses depend inversely on the minimum class probability, scaling as L/Pmin when O and, more generally, as (1/Pmin) when q E 1),
5.3
GCA Losses
This section presents consistency guarantees for GCA losses. We define a hypothesis set H as regular if, for any x é X, the predictions made by the hypotheses in H cover the complete set of possible classification labels: H(x) (h(x):h h HQ = [n]. Widely used hypothesis sets, such as linear models, neural network families, as well as the family of all measurable functions, are all regular. In particular, every complete hypothesis set is regular, while regularity alone is much weaker yet natural assumption practice.
The following theorem shows that for a regular hypothesis set, if a GCE loss fGCE is H-consistent with respect fo-1 then its corresponding GCA loss lCCA (Eq. (5)) is also H-coosistent with respect to the balanced loss BALL (Eq. (1)). For simplicity, we assume Pg 1 for all y throughout this section.
Theorem 5. Let H be a regular hypothesis set and fGCE a GCE loss. Assume that there exists function (tt) = 3 ta for some (0, 1] and B > O, such that the following K-consistency bound holds for all h H. and any distribution,
Rio ,hh) Ria, (H) Mr, (H) T(Rtece (h) Ri (H) MAaCE (H)). Then, the following H-consistency bound holds for LOCA with respect fAr all h e H and any distribution:
RiBAL (h) -Riea ()() + MenAr (3C) s SIRROCA (1) -Rioca (3() Mecca (90),
7

---

where ((t) 33
I
1-a
ta. In the special case where the approximation error Atacs (3C) = 0, this
Paiin
bound simplifies to:
RIBAL (h) -
s (TRRCC (M)-Ricce, (H)).
The proof is provided in Appendix E, where constructively define new conditional probabilities
q x) along with a normalization factor (ax) Egey p(v) Pmin
P(ylu) ___ These probabilities transform
the conditional regret of the balanced loss and the GCA loss into the conditional regrets of the zero-one loss and the GCE loss, respectively, under the newly defined distribution.
When Ascos (H) O, the K-consistency bound guarantees that if the surrogate estimation error Recos (h) - Ri Faca (H) is optimized up to e, the estimation error for the balanced loss, RegAL (h) Ry ERAL (H), is upper-hounded by [(c). For common choices of V in LCCA. Mao et al. [2023f,b]
show that 1 takes specific forms: for (I) log((), r(I) = /21 (so a = 1/2 and B 22; for
(t)) = 7 (1 - t9) with q E (0, 1), r(t) = /2 (so a = 1/2 and 3 = 229)). This leads to the
following corollary for GCA losses:
Corollary 6. Under the assumptions of Theorem 5, for all h E H and any distribution, the following H-coonsisencyy bound holds for EOCA with respect to lBAL:
RenAi. (1) - -D--RR Ri + Menas (31) S T[(REGC (h) - -RiocA (HI) + MEsCC (3)),
where [(1) = J for (1) = log(t) and [())= =
VBuin for (V( (1 - 19) with E (0, 1). In
/2ner
VPminn
the special case where the approximation error ALGCA (H) = O, this bound simplifies to:
RIBAL (1) - RRn S (RRECCA (h) ReacA (30);
I Hall, taking the limit on both sides implies the cayes-consistency of these GCA losses LGCA with respect to the balanced loss fAAL More generally, Corollary 6 demonstrates that ÊGCA admits an excess error bound relative to BAL if fACE has such a bound relative to f--1-
Mao et al. [2023[] and Mao et al. [2023b] showed that loss functions belonging to the widely used general cross-entropy (GCE) family (including logistic loss) admit H--cossstency bounds with respect to the multi-class zero-one loss fo-1 when the hypothesis set is complete and bounded, respectively. We say a hypothesis set JC is bounded if JC {h: y + E h(:3)) E F, Vy E У). where I is a family of real-valued functions f satisfying [f(z) S Azx) for all x E X, and all values in [-A(x),+AM +A(x)] are attainable. Here, A(z) 0 is fixed function on X. Boundedness also implies regularity. Thus, a key advantage of GCA losses is their general H--consistncyy: they are H--consistent for any hypothesis set that bounded or complete. Furthermore, their consistency bounds exhibit an improved scaling with the minimum class probability, 1/ /Pmin This contrasts favorably with GLA losses, offering potentially stronger theoretical support in highly imbalanced settings.
Comparison and Discussion. families: GLA losses are Bayes-consistent (for q E [0, 1)). However, their H-consistency requires the hypothesis set J( to be complete (and thus unbounded). The corresponding bounds depend on the minimum class probability Pmins scaling as 1/Pmin (for q = 0) or less favorably as (1/Pmin) + ( for E (0, 1)). In contrast, GCA losses demonstrate (K-consistency for any hypothesis set that is bounded or complete. Their H-consistency bounds scale more favorably with the minimum class probability, as 1/ This suggests GCA losses offer stronger theoretical guarantees, particularly in settings with significant class imbalance or when using more restricted hypothesis sets.
Our theoretical analysis reveals distinct characteristics for the two loss
The trade-offss between these theoretical properties and empirical performance are important. As we will show in the next experimental section (Section 6). GLA losses often achieve slightly better empirical results on common benchmarks. Conversely, GCA losses tend to have an edge in highly imbalanced scenarios. This empirical behavior aligns with our theoretical findings: GLA losses may be preferred for moderately imbalanced scenarios when using expressive, potentially unbounded hypothesis sets where their specific form of logit adjustment is beneficial; GCA losses are theoretically better-suited for highly imbalanced settings due to their favorable consistency scaling and applicability to wider range of hypothesis sets. For bounded hypothesis sets where GLA''s H -onnsisitt not guaranteed, GCA is the theoretically preferred option.
8

---

The assumptions in this section primarily concern properties of the hypothesis set. These are standard and typically satisfied in practice. Most natural hypothesis sets, such as linear models, neural networks, and the set of all measurable functions, are regular, meaning they produce predictions across all n classes. Whether a hypothesis set is bounded or complete depends on the modeling choice (e.g., bounded weights in linear models). Importantly, our results do not assume any specific data distribution and hold for arbitrary distributions, including those arising in real-world settings,
Compared to the previous work [Cortes et al., 2025], the key difference is that IMMAX [Cortes et al., 2025] is designed for optimizing the standard multi-class 0-1 loss under imbalanced data, whereas the proposed GCE and GCA losses are designed to optimize the balanced loss. As a result, IMMAX enjoys consistency with respect to the standard 0-1 loss, while GCE and GCA are consistent with respect to the balanced loss, a property most existing surrogate losses lack, as discussed in Section 3.3.
Appendix B further provides margin bounds for both the GCA and GLA losses in the more general cost-sensitive multi-class classification setting. We show that both losses benefit from margin guarantees, with more favorable bounds for GCA losses, as the GLA bounds depend on 1/Pmin
Theoretical novelty. Classical margin bounds have been extensively studied (see, for example [Koltchinskii and Panchenko, 2000, 2002, Schapire et al., 1997, Cortes et al., 2021, Mohri et al., 2018]). In particular, Mohri et al. [2018] derived margin bounds for standard multi-class classification. In contrast, we derive new margin bounds for cost-sensitive classification, a setting that introduces additional complexity due to the presence of instance- dependden cost functions. This requires the development of new proof techniques, including the derivation of an upper bound on the loss function expressed in terms of a margin loss and a maximum operator, along with an analysis of the Rademacher complexity of this maximum term via the vector contraction lemma. Moreover, in addition to the resulting margin bounds for GCA loss functions, our margin bounds for GLA loss functions are non-trivial and require specific and entirely new analysis (Appendix B.2), Mao et al. [2023f,b] studied H-consistencyy bounds for loss functions in the general cross-entropy (GCE) family with respect to the standard zero-one loss. In contrast, our work establishes H-coosistency bounds for the proposed GCA and GLA losses with respect to the balanced loss, where both the surrogate and target losses are more complex. This required several novel technical contributions, including a characterization of the conditional regret of the balanced loss, the use of Gibbs distributions and Pinsker-type inequalities for analyzing GL.A losses, and reduction of the conditional regrets of the balanced and GCA losses to those of the zero-one and GCE losses under a newly defined distribution.
6 Experiments
This section details the empirical evaluation of our proposed Generalized Logit-Adjusted (GLA) and Generalized Class-Aware (GCA) loss functions. We compare their effectiveness in minimizing the balanced loss against several baseline methods on the CIFAR-10, CIFAR- [Krizhessky, 2009], and Tiny ImageNet [Le and Yang, 2015] datasets with respectively 10, 100 and 200 classes. To simulate class imbalance, we reduced the percentage of examples per class identically in both training and test sets, following exactly the protocol in [Menon et al., 2021]. Two types of imbalance were considered: Long-tailed imbalance where class sample sizes decrease exponentially across sorted classes [Cui et al., 2019], and Step imbalance where minority classes share one sample size, and majority classes share another, creating a distinct two-group split [Buda et al., 2018J. The severity of maxi- me
imbalance is quantified by the imbalance ratio, p= min me.
where my is the number of samples
in class k. We evaluated performance at p = 100 (C), following Menon et al. [2021], and at a more extreme setting of p 1000 (M).
Our experimental setup, including training procedures and neural network architectures, strictly followed Menon et al. [2021]. We used a ResNet-32 architecture with ReLU activations [He et al., 2016]. Standard data augmentation techniques were applied: for 10 and CIFAR-100, this involved 4-pixel padding followed by 32 x 32 random crops and random horizontal flips; for Tiny ImageNet, 8-pixel padding was used, followed by 64 x 64 random crops. All models were trained for 200 epochs using Stochastic Gradient Descent (SGD) with Nesterov momentum [Nesterov, 1983]. We used batch size of 1, 024, weight decay of 10-3 and cosine decay learning rate schedule [Loshchilov and Hutter, 2016] without restarts, with an initial learning rate of 0.2.
9

---

Table 1: Balanced error of ResNet-32 on long-tailed (left) and -mmbllaaedee (right) imbalanced CIFAR-1O, CIFAR-100 and Tiny ImageNet, means standard deviations over 5 runs. Note, we are
reporting total error and not dividing by number of classes. Imbalance ratios p 1000 (M), 100 (C).
Method
CIFAR-10
CIFAR-100 100
Tiny L.eet
Method CE
CIFAR-10
CIFAR-100
Tiny LNet
CE
2,46 a 0,09
38.45 a 0.37
70.23 0.38
6,33 a 0.01
12.47
0.12
39.41 a 0.40
WCR
2.52 0.17
39.89
75.89 0.67
WCE
6.44 0.02
13.66
0.45
39.28 a 0.31
LA ()
2.18
35.92 a 0.47
67.17 0.49
LA ()=
5.54 0.48
37,44 0.25 12.24 0.20
11.42
EQUAL
2.38
37.33 0.36
68.44 a 0.72
EQUAL
5,89 0.24
38.43 = 0.44
M
41.46 0.03
80.22 0.59
CB
M
6.38 0.01
14.96 0.32
47.35 0.73
FOCAL
0.10
38.02 + 0.54
69.13 = 0.83
FOCAL
6.35 0.01
12.25
39.21 0.31
LDAM
2.39 0.08
37.39 0.36
68.27 0.81
6.34
38.21 0.27
GCA
2.02 0.15
33.17 a: 0,57
64,88 = 0.66
GCA
5,35 0.02
10,43 + 0.15
36.32 = 0.32
GLA
0.15
33.99
0.52
65.57 0.27
GLA
$.39 0.02
10.58
2.72:00.02
61,53 a: 0.29
106.93 a 0.89
CE
3.66 0.15
60.16
0.09
39.68 0.25
WCB
2
62.20 a: 0,57
112.50 a: 0.97
WCC
3.68 a: 0.11
61.40
0.51
43.68 0.42
LA (T 1)
2.28
56.23 0.21
102.81 0.89
LA (==
2.70 0.12
0.63 55.43
3842 0.14
EQUAL
2.60 0.08
57.25 + 0.40
104.91 + 0.84
EQUAL
3,18 0.12
$7.73
0.54
38.91 = 0.20
C
2.76 0.04
61.55 0.28
115.22 0.71
CR
3.81 0.02
66.41 0.11
50,51 0.45
FOCAL
2.70 0.06
61.21 + 0.24
105.47 a 0.59
DOCAL
3.60 0.11
60.06
1.06:0.11 0.13
39.63 = 0.27
LDAM
2.66 0.08
60.37 0.60
103.99 +: 0.58
LDAM
3.41 0.10
58.95
0,11
38.67 0.19
GCA
2.19 = 0.08
$4.02 + 0.38
101 + 0.81
GCA
2.57 a: 0.04
53.85
0.47
37,59
0.43
GLA
2.07 0.06
53.68
100.70 + 0.83
GLA
2.48
52.70
0.15
36.71 0.33
We compared our GLA and GCA losses against suite of widely used baseline methods: standard cross-entropy (CE) loss, weish-weighted cross-entropy (WCE) loss [Xie and Manski, 1989, Morik et al., 1999], Logit Adjusted (LA) loss [Menon al., 2021], Equalization (EQUAL) loss [Tan et al., 2020]. Maass-Bllanced (CB) loss [Cui et al., 20191, FOCAL loss [Ross and Dollár, 2017] and the LDAM loss [Cao al., 2019]. For all methods, including our GLA and GCA losses, we tune the hyperparameters using validation set held out separately from the training set. For the parameter g in both GLA and GCA, we selected values from {0.0, 0.1. 0.9], which are standard choices within the general cross-entropy family. Its performance depends on dataset imbalance (e.g., long-tailed vs. step imbalance). Further details about the experiments including baselines are provided in Appendix C. Performance was primarily evaluated using the balanced error on the imbalanced test sets (i.e., the average of the balanced loss over the test data). Results were averaged over five independent runs, and we report means and standard deviations. Table 1 presents the balanced error for ResNet-32 on long-tailed and step-imbarg -mbbllnnadd versions of CIFAR-10. 10, CIFAR-100 100, and Tiny ImageNet.
The results in Table highlight that both our proposed GCA losses and GLA losses generally outperform key baselines such as class weighted cross-entropy (WCE) and Logit-Adjusted (LA) losses across the tested datasets and imbalance types. This demonstrates the efficacy of our novel loss formulations in achieving better balanced error, indicating improved fairness and accuracy on minority classes. Comparing our two proposed families, GLA losses often achieve the best overall results on several benchmarks, particularly under moderate imbalance (p- = 100). However, GCA losses in accordance with its better /Pmmn bound tend to exhibit an advantage in settings with high class imbalance (p= = 1000).
The strong performance of GCA losses, especially their edge in highly imbalanced scenarios (p= 1000), underscores the impact of using class-dependent confidence margins. These margins allow GCA to adapt more effectively to severe skews in data distribution compared to simpler weighting or logit adjustment techniques. The performance difference observed between p = 100 and p = 1000 across all methods, and particularly the relative strengths of GLA and GCA, highlights the sensitivity of these approaches to the severity of class imbalance.
7 Conclusion
We introduced two novel families of surrogate losses, GLA and GCA losses, for balanced multi-class classification under class imbalance. Both are principled extensions of widely used loss designs, and our theoretical analysis establishes their consistency propertics, highlighting the more favorable H-- consistency bounds of GCA losses in imbalanced regimes. Empirically, both loss families outperform existing baselines, with GLA performing better in common benchmarks and GCA offering an edge in highly imbalanced settings. These results position GLA and GCA losses as state-of-thr --tt surrogates for balanced classification, bridging the gap between fairness, consistency, and practical performance. The extension of these surrogate loss families to structured prediction or multi-label classification could significantly broaden their impact. Finally, refining consistency bounds under realistic hypothesis classes and leveraging recent enhanced H-coosistencyy bounds could provide deeper insights into the behavior of these and related loss functions in balanced learning settings.
10

---

References
Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses, In Advances in Neural Information Processing Systems, pages 9804-9815, 2021a.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.0/5550 2021b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-consisteney bounds for surrogate loss minimizers. In International Conference on Machine Learning, pages 1117-1174, 2022a.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H --consistencyy bounds. In Advances in Neural Information Processing Systems, pages 782-795, 2022b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference Artificial Intelligence and Statistics, pages 10077-10094, 2023a.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2023b.
P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):188-156 2006.
P. L. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normalized margin bounds for neural networks. CoRR,
2017.
J. Berkson. Application of the logistic function to bio-assay. Journal of the American Statistical Association, 39:357-365, 1944.
J. Berkson. Why prefer logits to probits. Biometrics, 7(4):327-339, 1951.
K. H. Brodersen, C. S. Ong, K. E. Stephan, and J. M. Buhmann. The balanced accuracy and its posterior distribution. In International Conference Pattern Recognition, pages 3121-3124, 2010.
M. Buda, A. Maki, and M. A. Mazurowski. A systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, (96:249-259, 2018.
J. Byrd and Z. Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pages 872-881, 2019.
K. Cao. C. Wei, A. Gaidon, N. Arechiga, and T. Ma. Learning imbalanced datasets with label- distribution- aware margin loss. In Advances in Neural Information Processing Systems, 2019.
C. Cardie and N. Nowe. Improving minority class prediction using case-specific feature weights. In International Conference on Machine Learning, pages 57-65, 1997.
P. K. Chan and S. J. Stolfo. Learning with non-uniform class and cost distributions: Effects and distributed multi-classffier approach. In Workshop Notes KDD-98 Workshop on Distributed Data Mining, pages 1-9, 1998.
N. V. Chawla, K. W. Bowyer, O. Hall, and W. P. Kegelmeyer. SMOTE: synthetic minority over-sampling technique. Journal Artificial Intelligence Research, 16:321-357, 2002.
G. Collell, D. Prelec, and R. Patil. Reviving mreshold-mmoiing a simple plug-in bagging ensemble for binary and multiclass imbalanced data. CoRR, abs/1606.088ll 606688 2016.
V. Conitzer, Freeman, N. Shah, and W. Vaughan. Group fairness for the allocation of indivisible goods. In Proceedings of the AAAI Conference Artificial Intelligence, pages 1853-1860, 2019.
C. Cortes, Kuznetsov, M. Mohri, and Yang. Structured prediction theory based on factor graph complexity. In Advances in Neural Information Processing Systems, 2016.

---

C. Cortes, X. Gonzalvo, V. Kuznetsov, M. Mohri, and S. Yang. AdaNet: Adaptive structural learning of artificial neural networks. In International Conference on Machine Learning, pages 874-883, 2017.
C. Cortes, M. Mohri, and A. T. Suresh. Relative deviation margin bounds. In International Conference on Machine Learning, pages 2122-2131, 2021.
C. Cortes, A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Cardinality-aware set prediction and top-k classification. In Advances in Neural Information Processing Systems, 2024.
C. Cortes, A. Mao, M. Mohri, and Y. Zhong. Balancing the scales: A theoretical and algorithmic framework for learning from imbalanced data. In International Conference on Machine Learning, 2025.
J. Cui, Z. Zhong, S. Liu, B. Yu, and J. Jia. Parametric contrastive learning, In International Conference on Computer Vision, 2021.
Cui, S. Liu, 7. Tian, 7. Zhong, and J. Jia. Reslt: Residual learning for long-tailed recognition. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie. Class-balanced loss based effective number of samples. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9268-9277, 2019.
G. DeSalvo, C. Mohri, M. Mohri, and Zhong. Budgeted multiple-expert deferral. arXiv preprint arXiv:2510.26706, 2025.
C. Du, Y. Han, and G. Huang. Simpro: A simple probabilistic framework towards realistic long-tailed semi-supervised learning. In International Conference on Machine Learning, 2024.
C. Elkan. The foundations of cost-sensitive learning. In International Joint Conference on Artificial Intelligence, 2001.
A. Estabrooks, T. Jo, and N. Japkowicz. A multiple resampling method for learning from imbalanced data sets. Computational Intelligence, 2081):18 2004.
Y. Fan, S. Lyu. Y. Ying, and Hu. Learning with average top-k loss. In Advances in Neural Information Processing Systems, pages 497-505, 2017.
T. Faweett and F. Provost. Combining data mining and machine learning for effective user profiling.
In International Conference on Knowledge Discovery and Data Mining, pages 8-13, 1996.
V. Feldman. Does learning require memorization? a short tale about long tail. In Symposium on Theory of Computing, pages 954-959, 2020.
M. Gabidolla, A. Zharmagambetov, and M. Á. Carreira-Perpiñal Beyond the ROC curve: Classifi- cation trees using opttmol curves, with application imbalanced datasets. In International Conference on Machine Learning, 2024.
J. Gao, H. Zhao, Z. Li, and D. Guo. Enhancing minority classes by mixing: adaptative optimal transport approach for loig-tailed classification. In Advances in Neural Information Processing Systems, 2023.
Gao, H. Zhao, D. dan Guo, and H. Zha. Distribution alignment optimization through neural collapse for long-tailed classification. In International Conference on Machine Learning, 2024.
A. Ghosh, H. Kumar, and P. S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
B. Han. Wrapped cauchy distributed angular softmax for long-tailed visual recognition. In Interna- tional Conference on Machine Learning, pages 12368-12388, 2023.
H. Han, W.Y Wang, and B.-H. Mao. Borderline-smote: a new over-sampling method in imbalanced data sets learning. In International Conference Intelligent Computing, pages 878-887, 2005.
12

---

M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, 2016.
H. He and A. Garcia. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9):2233-1288 2009.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
Y. Hong, S. Han, K. Choi, S. Seo, B. Kim, and B. Chang. Disentangling label distribution for long-tailed visual recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2021.
A. Iranmehr, H. Masnadi-Shiruu and N. Vasconcelos. Cost-sensitive support vector machines. Neurocomputing, 343:50-40 64. 2019.
M. Jamal, M. Brown, M.-H. Yang. L. Wang, and B. Gong. Rethinking claanebllanced methods for long-tailed visual recognition from domain adaptation perspective. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7610-7619, 2020.
R. Jiawei, C. Yu, Ma, H. Zhao, Yi, et al. Balanced meta-softmax for long-tailed visual recognition. In Advances in Neural Information Processing Systems, pages 4175-4188 2020.
B. Kang, S. Xie, M. Rohrbach, Z. Yan, A. Gordo, J. Feng, and Y. Kalantidis. Decoupling rep- resentation and classifier for long-tailed recognition. In International Conference on Learning Representations, 2020.
B. Kang, Y. Li, S. Xie, Z. Yuan, and Feng. Exploring balanced feature spaces for representation learning. In International Conference on Learning Representations, 2021.
T. Kasarla, G. Burghouts, M. Van Spengler, E. Van Der Pol, R. Cucchiara, and P. Mettes. Maximum class separation inductive bias in one matrix. Advances Neural Information Processing Systems, pages 19553-19566 2022.
M. M. Khalili, X. Zhang, and M. Abroshan. Loss balancing for fair supervised learning. In International Conference on Machine Learning, pages 16271-16290, 2023.
S. Khan, M. Hayat, S. W. Zamir, J. Shen, and L. Shao. Striking the right balance with uncertainty. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 103-112, 2019.
B. Kim and J. Kim. Adjusting decision boundary for class imbalanced learning, 2019.
G. King and L. Zeng. Logistic regression in rare events data. Political Analysis, 12):137-163, 2001.
G. R. Kini, O. Paraskevas, S. Oymak, and C. Thrampoulidis. Label-imbalanced and group-sensitive classification under overparameterization.. In Advances Neural Information Processing Systems, volume 34, pages 19900-18983, 2021.
V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of function learning. In High Dimensional Probability II, pages 443-459, 2000.
V. Koltchinskii and D. Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. Annals Statistics, 30, 2002.
W. Kotlowski, K. Dembezynski, and E. Hüllermeier. Bipartite ranking through minimization of
univariate loss. In International Conference on Machine Learning, pages 1113-1120 2011.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Toronto University, 2009.
M. Kubat and S. Matwin. Addressing the curse of imbalanced training sets: One-sided selection. In International Conference Machine Learning. 1997.
Y. Le and X. Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
13

---

D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. In Proceedings of the ACM SIGIR Conference on Research and Development Information Retrieval, 1994.
Li, Q. Xu, Bao, Z. Yang, R. Cong, X. Cao, and Q. Huang. Size-invariance matters: Rethinking metrics and losses for imbalanced multi-object salient object detection. In International Conference on Machine Learning, 2024a.
L. Li, X.-C. Li, H.-J Ye, and D.-C. Zhan. Enhancing class-imbalanced learning with pre-trained guidance through class-conditional knowledge distillation. In International Conference on Machine Learning, pages 28204-28221, 2024b.
M. Li, X. Zhang, C. Thrampoulidis. J. Chen, and S. Oymak. Autobalance: Optimized loss functions for imbalanced data. In Advances in Neural Information Processing Systems, pages 3163-3177, 2021.
Li, Q. Xu, Z. Yang, Z. Wang, I.. Zhang, X. Cao, and Q. Huang. Focal-sam: Focal sharpness-aware minimization for long-tailed classification. In International Conference on Machine Learning, 2025.
T.Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár. Focal loss for dense object detection. In International Conference Computer Vision, pages 2980-2988, 2017.
L. Liu, S. He, A. Ming, R. Xie, and H. Ma. Elta: An enhancer against long-tail for aesthetics-oriented models. In International Conference on Machine Learning, 2024.
X.-Y. Liu, J. Wu, and Z.-H. Zhou. Exploratory undersampling for class-imbalance learning. IEEE Transactions on Systems, Man, and Cyhernetics, 39(2):539-55) 5500, 2008
Z. Liu, Z. Miao, X. Zhan, J. Wang. B. Gong, and S. Yu. Large-scale long-tailed recognition in an open world. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 2537-2546, 2019.
E. Loffredo, M. Pastore, S. Cocco, and R. Monasson. Restoring balance: der/oversampling of data for optimal classification. In International Conference on Machine Learning, pages 32643-32670, 2024.
principled un-
I. Loshchilov and F. Hutter. SGDR: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.0398 2016.
M. A. Maloof. Learning when data sets are imbalanced and when costs are unequal and unknown. In ICML 2003 Workshop on Learning from Imbalanced Datasets, 2003.
A. Mao. Theory and Algorithms for Learning with Multi- Class Abstention and Multi Aulti-Exppet Deferral. PhD thesis, New York University, 2025.
A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Two-stage learning defer with multiple experts. In Advances in Neural Information Processing Systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.
A. Mao, M. Mohri, and Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International Conference on Machine learning, 2023c.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In ICML 2023 Workshop The Many Facets of Preference-Bast Learning, 2023d.
A. Mao, M. Mohri, and Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Informaionn Processing Systems, 2023e.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning. 2023f.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning to defer with multiple experts. In International Symposium on Artificial Intelligence and Mathematics, 2024a.
14

---

A. Mao, M. Mohri, and Y. Zhong. peedictor-rejectee multi-class abstention: Theoretical analysis and algorithms. In International Conference on Algorithmic Learning Theory, 2024b.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. In International Conference on Artificial Intelligence and Statistics, 2024c.
A. Mao, M. Mohri, and Y. Zhong. H-consistency guarantees for regression. In International Conference on Machine Learning, pages 34712 34712-34737, 2024d.
A. Mao, M. Mohri, and Y. Zhong. Multi-label learning with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2024e.
A. Mao, M. Mohri, and Y. Zhong. Realizable H-connistentt and Bayes-consistent loss functions for learning to defer. In Advances in Neural Information Processing Systems, 2024f.
A. Mao, M. Mohri, and Y. Zhong. Regression with multi-expert deferral. In International Conference on Machine Learning, pages 14738-34759) 2024g.
A. Mao, M. Mohri, and Y. Zhong. A universal growth rate for learning with smooth surrogate losses. In Advances Neural Information Processing Systems, 2024h.
A. Mao, M. Mohri, and Zhong. Mastering multiple-expert routing: Realizable H Hcconsistency and strong guarantees for learning to defer. In International Conference Machine Learning. 2025a.
A. Mao, M. Mohri, and Y. Zhong. Principled algorithms for optimizing generalized metrics in binary classification. In International Conference on Machine Learning, 2025b.
A. Mao, M. Mohri, and Y. Zhong. Enhanced K-consistency bounds. In International Conference Algorithmic Learning Theory, 2025c.
H. Masnadi-Shirazi and N. Vasconcelos. Risk minimization, probability elicitation, and cost-sensitive
SVMs. In International Conference on Machine Learning, page 759-766, 2010.
A. Maurer. vector-contraction inequality for rademacher complexities. International Conference Algorithmic Learning Theory, 2016.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficiennn learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. 2017.
L. Meng, X. Dai, Yang, Chen, Y. Chen, M. Liu, Y.-L. Chen, Wu, L. Yuan, and Y.-G. Jiang. Learning from rich semantics and coarse locations for long-tailed object detection. In Advances in Neural Information Processing Systems, 2023.
A. Menon, H. Narasimhan, S. Agarwal, and S. Chawla. On the statistical consistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pages 603-611, 2013.
A. K. Menon, S. Jayasumana, A. S. Rawat, H. Jain, A. Veit, and S. Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations, 2021.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with fixed predictor: Application decontextualization. In International Conference on Learning Representations, 2024.
M. Mohri and Y. Zhong. Beyond tsybakov: Model margin noise and !i-consistency bounds, arXiv preprint arXiv:2511.15816 2025.
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning. MIT Press, second edition, 2018
M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In International Conference on Mchine Learning, pages 4615-4625, 2019.
15

---

K. Morik, P. Brockhausen, and T. Joachims. Combining statistical learning with knowledge- based approach-a case study intensive care monitoring. In International Conference on Machine Learning, pages 268-277, 1999.
Y. E. Nesterov. A method for solving the convex programming problem with convergence rate (11Kk2). Dokl. akad. nauk Sssr, 269:543-544 1983.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks. CoRR, 503/1503.00036, 2015.
F. Provost. Machine learning from imbalanced data sets 101. In Proceedings of the AAAI-2000 Workshop on Imbalanced Data Sets, 2000.
X. Qiao and Y. Liu. Adaptive weighted learning for unbalanced multicategory classification. Biomet- rics, 65:159-68. 2008.
A. E. Rastegin. Bounds of the pinsker and fannes types the tsallis relative entropy. Mathernatical Physics, Analysis and Geometry, 16(3):213-225 2013.
T.-Y. Y. Ross and G. Dollár. Focal loss for dense object detection. In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, pages 2980-2988, 2017.
R. E. Schapire, Y. Freund, P. Bartlett, and W. S. Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. In International Conference on Machine Learning, pages 322-330 1997.
J.-X Shi, T. Wei, Xiang, and Y--F Li. How re-sampling helps for long-tail learning? In Advances in Neural Information Processing Systems, 2023.
J.-X Shi, T. Wei, Z. Zhou, J.-J. Shao, X.-Y. Han, and Y--F Li. Long-tail learning with foundation model: Heavy fine-tuning hurts. In International Conference on Machine Learning, 2024.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation, (6(2):225-287 2007.
M.-K. Suh and S.-W. Sco. Long-tailed recognition by mutual information maximization between latent features and ground-truth labels. In International Conference on Machine Learning, pages 12770-32788 2023.
Y. Sun, M. S. Kamel, A. K. Wong, and Y. Wang. Cost-sensitive boosting for classification of imbalanced data. Pattern Recognition, 40(12):3358-311 -3788, 2007.
Tan, C. Wang, Li, Q. Li, W. Ouyang, C. Yin, and Yan. Equalization loss for long-tailed object recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1662-11677, 2020.
K. Tang, J. Huang, and H. Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. In Advances Neural Information Processing Systems, 2020.
A. Tewari and P. L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8036):1007-1025, 2007.
J. Tian, Y.C. Liu, N. Glaser, Y.C.. Hsu, and Z. Kira. Posterior re-calibration for imbalanced datasets. In Advances Neural Information Processing Systems, 2020.
J. Van Hulse, T. M. Khoshgoftaar, and A. Napolitano. Experimental perspectives on learning from imbalanced data. In International Conference on Machine Learning, 2007.
F. Verhulst. Notice sur loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10: 10:113-121, 1838.
F. Verhulst. Recherches mathématiques sur la loi d'accroissement de la population. Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettre, de Bruxelles, 18:1-42, 1845.
16

---

B. C. Wallace, K. Small, C. E. Brodley, and T. A. Trikalinos. Class imbalance, redux. In International Conference on Data Mining, pages 754-763, 2011.
H. Wang, M. Xia, Y. Li, Y. Mao. L. Feng, G. Chen, and J. Zhao. Solar: Sinkhorn label refinery for imbalanced partial-label learning. In Advances in Neural Information Processing Systems, pages 8104-81 8117,11111 2022.
J. Wang. T. Lukasiewicz, X. Hu, J. Cai, and Z. Xu. Rsg: A simple but effective module for learning imbalanced datasets. In Proceedings of the IEEE Conference on Computer Vision and Putlern Recognition, pages 3784-3793, 2021a.
X. Wang. L. Lian, Z. Miao, Z. Liu, and X. Yu. Long-tailed recognition by routing diverse distribution-awand experts. In International Conference Learning Representations, 2021b.
Z. Wang, Q. Xu, Z. Yang, Y. He, X. Cao, and Q. Huang. unified generalization analysis of re-weighting and logit-adjustment for imbalanced learning. In Advances in Neural Information Processing Systems, pages 94410-4843, 2023.
Z. Wang. Q. Xu, Z. Yang, Z. Xu, L. Zhang, X. Cao, and Q. Huang. A unified perspective for loss- oriented imbalanced learning via localization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025.
T. Wei, Z. Mao, Z.-H. Zhou, Y. Wan, and M.-L. Zhang. Learning label shift correction for test-agnostic long- tailed recogmition. In International Conference on Machine Learning. 2024.
P. Wen, Q. Xu, S. Dai, R. Cong, and Q. Huang. Semantic concentration for self- superviee dense representations learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025.
L. Xiang, G. Ding, and J. Han. Learning from multiple experts: Self-paced knowledge distillation for long-tailed classification. In European Conference on Computer Vision, pages 247-263, 2020.
Z. Xiao, Z. Chen, S. Liu, H. Wang, Y. Feng. J. Hao, J. T. Zhou, J. Wu, H. Yang, and Z. Liu. Fed- grab: Federated long-tailed learning with self-adjusting gradient balancer. In Advances Neural Information Processing Systems, 2023.
Y. Xie and C. Manski. The logit model and response- based samples. Sociological Methods & Research, 17(3):283-302. 1989.
Y. Yang and Z. Xu. Rethinking the value of labels for improving class-imbalanced learning. In Advances in Neural Information Processing Systems, 2020.
Y. Yang. S. Chen, X. Li, L. Xie, Z. Lin, and D. Tao. Inducing neural collapse in imbalanced learning: Do we really need learnable classifier at the end of deep neural network? In Advances in Neural Information Processing Systems, pages 198002,, 2022.
Z. Yang, Q. Xu, Z. Wang, S. Li, B. Han, S. Bao, X. Cao, and Q. Huang. Harnessing hicrarchical label distribution variations in test agnostic long-tail recognition. In International Conference Machine Learning, 2024.
H.-. Ye, H.-Y. Chen, D. Zhan, and W.-L. Chao. Identifying and compensating for feature deviation in imbalanced deep learning, 2020.
X. Yin, X. Yu, K. Sohn, X. Liu, and M. Chandraker. Feature transfer learning for deep face recognition with long-tail data. CORR, htts/1803.0900 2018.
J. Zhang, I. Liu, P. Wang, and C. Shen. To balance or not to balance: A simple-yet-effective approach for learning with long-tailed distributions, 2019a.
Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals Statistics, 32(1):56-88) 85, 2004a.
Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1et.-122221111 2004b.
17

---

X. Zhang, Z. Fang, Y. Wen, Z. Li, and Y. Qiao. Range loss for deep face recognition with longet training data. In International Conference on Computer Vision, pages 5409-5418, 2017.
Y. Zhang, P. Zhao, J. Cao, W. Ma, Huang, Q. Wu, and M. Tan. Online adaptive asymmetric active learning for budgeted imbalanced data. In SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2768-2777, 2018.
Y. Zhang, P. Zhao, S. Niu, Q. Wu, J. Cao, J. Huang, and M. Tan. Online adaptive asymmetric active learning with limited budgets. JEEE Transactions on Knowledge and Data Engineering, 2019b.
Y. Zhang. B. Hooi, L. Hong. and J. Feng. Self-supervised aggregation of diverse experts for test- agnostic long-tailed recognition. Advances Neural Information Processing Systems, pages 34077-34090, 2022.
Y. Zhang, B. Kang, B. Hooi, S. Yan, and J. Feng. Deep long-tailed learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15795510795- 2023.
Z. Zhang and T. Pfister. Learning fast sample re- re-weighting without reward data. In International Conference on Computer Vision, 2021.
Z. Zhang and M. Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in Neural Information Processing Systems, 2018.
P. Zhao, Y. Zhang, M. Wu, S. C. Hoi, M. Tan, and J. Huang. Adaptive cost-sensitive online classification. IEEE Transactions on Knowledge and Data Engineering, 31(2):214 228, 2018.
Y. Zhong. Fundamental Novel Consistency Theory: H-Consistency Bounds. PhD) thesis, New York University, 2025.
Z. Zhong. Cui, S. Liu, and Jia. Improving calibration for long-taiin recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2021.
Zhou, Q Cui, X.-S. Wei, and Z.-M. Chen. Bhn: Bilateral-branch network with cumulative learning for long-tailed visual recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9719-9728, 2020.
H. Zhou and X.-Y. Liu. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on Knowledge and Data Engineering, 18(1):63-77, 2005.
B. Zhu, K. Tang, Q. Sun, and H. Zhang. Generalized logit adjustment: Calibrating fine-tuned models by removing label bias in foundation models. In Advances in Neural Information Processing Systems, pages 64663-64680, 2023.
M. Zhu, C. Fan, H. Chen, Y. Liu, W. Mao. X. Xu, and C. Shen. Generative active learning for long-tailed instance segmentation. In International Conference on Machine Learning, 2024.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Section The paper contains both the theory and experiments described.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
18

---

The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: These results position GLA and GCA losses as state-of-the-art surrogates for balanced classification, bridging the gap between faimess, consistency, and practical performance. The extension these surrogate loss families to structured prediction or multi- label classification could significantly broaden their impact. Finally, refining consistency bounds under realistic hypothesis classes and leveraging recent enhanced H--consistnccy bounds could provide deeper insights into the behavior of these and related loss functions in balanced learning settings.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificatiin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have sections that introduces formalism and explains terminology. Every proof lists conditions. See Section 4, Section 5, Appendix B, Appendix D, Appendix E, Appendix Appendix G, Appendix H, and Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
19

---

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

---

Please see the NeurIPS code and data submission guidelines thttps://nips.cr public/ /ttli//gu/s/////eeeee Code Suiomi ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips... cc/ http:cpppppcccccccccccc publica ht//guideeee Codee uumi as i ciioooiiiiy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
See Section 6 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See Table 1.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
21

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Model training was performed using hardware accelerators providing the equivalent computational power of 64 GPUs.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /twwunnuu.pp...// cc wwtppblicc/.ticccieeeeeeeeeeeeee
Answer: [Yes]
Justification:
The authors have reviewed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Balanced loss promotes fairness by equalizing performance across demo- graphic groups and ensures that minority classes are not overlooked in long-tailed datasets. It is also crucial in federated learning, where data imbalances across clients can lead to bi- ased models that favor heavy users. This represents broader impact of balanced multi-class classification under class imbalance.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

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

---

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

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: / //neurieipp/////eeeee /trperrrss..cc/ooffeeeeeeee Sacc/onffereneess / 2025/ LLM) for what should should not described.
25

---

Contents of Appendix
Related work
27
B Margin bounds
29
B.1 Theoretical analysis.
29
B.2 Margin bounds for GLA lossess
30
B.3 Algorithms.
32
Experimental details
33
C.1 Loss function formulations
33
C.2 Hyperparameter search protocol
34
Conditional regret for the balanced loss: proof of Lemma
35
E H--Consisenncy for the GCA losses: proof of Theorem 5
35
Negative results for the LA losses: proof Theorem
36
G Bayes-Consistency for the GLA losses: proof of Theorem 3
37
H Ji-Consisteney for the GLA losses: proof of Theorem
38
Margin bound: proof of Theorem 7
41
26

---

A Related work
Class imbalance is a prevalent challenge in real-world multi-class classification problems [Cui et al., 2019, Fawcett and Provost, 1996, Kang et al., 2021, Kubat and Matwin, 1997, Lewis and Gale, 1994, Liu et al., 2019, Menon et al., 2021J. Applications such as medical diagnosis, fraud detection, and rare event prediction often involve highly skewed label distributions, where a small subset of classes dominate the data, while others, sometimes the most critical, are heavily underrepresented. Standard training objectives, such as minimizing the unweighted cross-entropy loss, tend to be biased toward majority classes, leading poor performance on minority classes and undermining the faimesss soundness and reliability of learned models.
The extensive literature on class imbalance has yielded a diverse array of techniques [Cardie and Nowe, 1997, Chawla et al., 2002, He and Garcia, 2009, Kubat and Matwin, 1997, Wallace et al., 2011]. Due to space constraints, comprehensive review of every method infeasible. Instead, we will categorize and discuss several major strategic directions, referring the reader to recent surveys, such as Zhang al. [2023], for more exhaustive treatment. These strategies can be broadly grouped as follows:
1. Data-Level Approaches These methods aim to directly modify the training dataset's 's class distribution to create a more balanced representation.
Re-sampling Techniques: This is the most traditional approach, involving either oversam- pling the minority classes (e.g.. by duplicating instances or more advanced interpolation) undersampling the majority classes (by removing instances) [Kuhat and Matwin, 1997,
Wallace et al., 2011].
Synthetic Data Generation: More sophisticated methods generate new synthetic samples for minority classes SMOTE (Synthetic Minority Over-sampling Technique) and its variants are prominent examples [Chawla al., 2002, Han et al., 2005, Qiao and Liu, 2008].
Advanced Data Augmentation: Recent works explore targeted data augmentation strategies to enhance minority class representation, sometimes using generative models or optimal transport principles (e.g.. [Gao et al., 2023, Liu et al., 2024, Wang al., 2021a, Zhu et al., 2024)). While these methods can improve minority class recognition, oversampling may lead overfitting, undersampling can discard valuable data, and the effectiveness of synthetic data depends heavily on the generation quality [Estabrooks et al., 2004, Liu et al., 2008, Shi et al., 2023, Zhang and Pfister, 2021].
2. Algorithm-Level Cost-Sensitive Learning This category focuses on modifying the learning algorithm to treat classes differently, typically by assigning higher misclassification costs to errors on minority classes.
Class Re-eeighting: A common implementation involves incorporating class weights directly into the loss function, where weights are often inversely proportional to class frequencies or based on concepts like the "effective number samples" [Cui et al., 2019]. Examples include weighted versions of Softmax or the 0/1 loss [Gabidolla et al., 2024, Morik et al., 1999, Xie and Manski, 1989].
Some learning algorithms, like SVMs, have explicit cost- sensitive formulations [Iranmehr et al., 2019, Masnadi-Shirazi and Vasconcelos, 2010]. Many other methods adapt standard learners to be cost-aware [Elkan, 2001, Fan al., 2017, Jamal et al., 2020, Sun et al., 2007, Wang et al., 2022, Suh and Seo, 2023, Wang et al., 2023, 2025, Li et al., 2025, Xiao et al., 2023, Zhang et al., 2018 2019b, 2022, Zhao et al., 2018, Zhou and Liu, 2005]. Cost-sensitive methods offer a principled way to emphasize underrepresented classes. While they can be viewed as algorithmically achieving effects similar to re-sampling, they avoid explicit data duplication or removal. However, their success often hinges on the appropriate selection of costs/weights, and they may not fundamentally alter the decision boundaries if the classes are inherently hard to separate or if the chosen weights are not optimal [Van Hulse et al., 2007].
Cost-Sensitive Classifiers:
3. Loss Function and Logit Adjustment This broad category involves designing or modifying loss functions to be more robust to class imbalance or to directly optimize for balanced performance metrics.
27

---

Modulating Sample Contributions: Some losses dynamically adjust the contribution of each sample the total loss based on its difficulty or class. The Focal loss [Lin et al., 2017]. for instance, down-weights well-classifedd (often majority class) examples, allowing the model to focus on hard, minority examples.
Margin-Basee Modifications: Several approaches aim to enforce larger decision margins for minority classes or between specific class pairs. Examples include LDAM [Cao et al., 2019], Equalization loss (ESQL) [TTnn et al., 2020], and Balanced Softmax [Jiawei et al., 2020J. LADE [Hong et al., 2021] also explores disentangling label distributions.
Direct Logit Adjustments: This sub-group directly modifies the logits (pre-softmax outputs) of the model, often by adding class-specific biases. The Logit Adjustment (LA) method by Menon al. [2021], Khan et al. [2019] and related techniques like UNO-IC [Tian et al., 2020, Wei et al., 2024] and LSC [Wei et al., 2024] fall here. Menon et al. [2021] showed that specific form of logit adjustment can achieve Bayes-consistency for the balanced error. Other works explore multiplicative logit modifications [Ye et al., 2020] or combinations of additive and multiplicative changes, like the Vector Scctor-Saaling loss [Kini et al., 2021], though multiplicative changes can sometimes be seen equivalent to input feature re-normalization. To capture how these modified loss functions handle different classes, Wang et al. [2023] proposed novel technique named data-dependent contraction. Wang et al. [2025] showed that the additive and multiplicative logit modifications essentially correspond to different local calibration assumptions. These methods directly influence the optimization landscape and decision boundaries but may introduce new hyperparameters requiring careful tuning.
4. Representation Learning for Imbalanced Data Instead of (or in addition to) modifying data or loss functions, these techniques focus on learning feature representations that are inherently more robust class imbalance or that better highlight minority class characteristics.
Examples include OLTR [Liu et al., 2019], PaCo [Cui et al., 2021]. DisA [Gao et al.. 2024], and other recent methods focused on semantic richness or distribution alignment (e.g.. RichSem [Meng al., 2023], RBL [Meng al., 2023], WCDAS [Han, 2023]). Learning discriminative and balanced representations is a fundamental goal, and these methods often aim to decouple feature learning from classifier training to some extent.
5. Decoupled Training and Post-Hoe Adjustments This strategy involves separating the learning process into stages applying corrections after an initial model has been trained.
Representation learning and classifier training are often performed separately. For example, model might first be trained with instance-balanced sampling or standard loss, and then the classifier head is fine-tuned using a bllanebalanced approach (e.g., Decouple-IB-CRP [Kang et al., 2020], CB-CRT [Kang et al., 2020], SR-CRT [Kang et al., 2020], PB-CRT [Kang et al., 2020], MiSLAS [Zhong et al., 2021J). Weight normalization techniques [Kim and Kim, 2019, Kang et al., 2020, Zhang et al., 2019a] also often fall under this paradigm.
Decoupled Training:
Post-Hoc Correction:
These methods adjust the outputs or decision thresholds of a pre- trained classifier to improve performance on imbalanced data, without retraining the model [Collell et al., 2016, Fawcett and Provost, 1996, Zhu et al., 2023]. These approaches offer flexibility and can be applied to existing models, but post-hoc methods may not achieve the same level of performance as methods that incorporate imbalance considerations throughout training.
Ensemble Learning Approaches Ensemble methods combine multiple classifiers to achieve better predictive performance than any single constituent classifier. For imbalanced learning, ensembles are often constructed by training base learners on different re-sampled versions of the data or by using different cost-sensitive strategies for each member.
Examples include BBN [Zhou et al., 2020), LFME [Xiang al., 2020], RIDE [Wang et al., 2021b], ResLT [Cui et al., 2022], SADE [Zhang et al., 2022], and DirMixE [Yang et al., 2024]. Ensembles are often robust but can increase computational expense and reduce model interpretability.
7. Other Notable Strategies The field also includes various other specialized techniques:
28

---

Transfer Learning: Leveraging knowledge from related tasks or datasets can help, espe-
cially for data-scarce minority classes (e.g.. SSP [Yang and Xu, 2020]).
Specialized Classifier Design: Some works focus on designing classifier architectures or
objective functions specifically robust to long tails or confounding factors (e.g.. De-confound
[Tang et al., 2020], [Kasarla al., 2022, Yang et al., 2022], LIFT [Shi et al., 2024]. SimPro
[Du et al., 2024]).
Metric-Focused Optimization: Recent studies also analyze the asymptotic performance of classifiers under different metries on imbalanced data [Loffredo et al.. 2024], develop size-invariant metrics for specific tasks like salient object detection [Li et al., 2024a]. and propose improved Average Precision (AP) losses for the AUPRC metric that are robust to noisy and imbalanced pseudo-labels [Wen et al., 2025]. Information and data augmentation via distillation have also been explored [Li et al., 2024b].
This categorization highlights the multifaceted nature of addressing class imbalance. Our work contributes to the area of loss function and logit adjustment, aiming for theoretically grounded and empirically effective solutions. For further details on the landscape of imbalanced learning, we again refer the reader to comprehensive surveys like Zhang et al. [2023].
B Margin bounds
This section provides margin-based based theoretical analysis of cost-sensitive multi-class classification. We derive margin bounds for both the GCA and GLA families. The analysis for the GLA family is more complex, and the resulting bound is generally less favorable, with a dependence on 1/Pmin-
The proof involves the derivation of an upper bound on the cost-sensitive zero-one loss function ex- pressed in terms of a margin loss and a maximum operator, along with an analysis of the Rademacher complexity of this maximum term via the vector contraction lemma. Moreover, our margin bounds for GLA loss functions are non-trivial and require a specific and entirely new analysis (Appendix B.2).
B.1 Theoretical analysis
Let Xx [n] I be scoring function belonging the hypothesis set H. We define the cost-sensitive zero-one loss function L as follows: for all (h, xz y) E D( x X x [n].
L(h, n k) = c(2, y) h())))>
where c(x,y) is non-negative cost that is upper bounded by C. Note that BAL a special case of L.
A. Cost-sensitive margin loss functions. We first introduce new cost-sensitive margin loss functions which will play central role in our derivation of margin-based guarantees for cost-sensitive learning.
Let up: min(1 1, max(0, 1 1011- u/p)) denote the p-margin loss function. We can upper-bound the cost-sensitive zero-one loss function L as follows:
L x) c( (pp
c(xx,)) (h(I,8) (1(x,)) - max maxx((x,)))
hx=))))))
=c(x.v) max (2(2),h(,)))) 1i--hhx, h(x,z/)))
The second inequality follows from the fact that when y = h(z) we have h(z,y) y) h(z, h(x))())))))))))))))) =ax ((xx,y)). Otherwise, for # h(x), the runner-up prediction satisfies argmax, by hlzz h(x).
The analysis above motivates the definition of the cost-sensitive margin loss function as the function Lg: Han x X x [n]] + R, defined as follows, for any fixed p 0:
Lo x, 8) = c(x.3) 3) max (2 (1(x, ((xz/)))))
s'[nn]
29

---

B. Margin bounds. We now establish a general margin based generalization bound, which serves as the foundation for deriving new algorithms for cost-sensitive classification.
Given a sample 5 = (Ii,.... Im) and hypothesis h, the empirical cost-sensitive margin loss is defined by (h) 1 Ex=1 (h,,, Fz. 3/) and the empirical GCA loss is defined by Rs.EacA (h) 1 Ei LGCA (1, The empirical Rademacher complexity of H for sample S is defined as: m
22 ΣΣ
Rs(H))
sup hest
Eiyh(xs y) E1yl
Σ
m
where 6 (tiy) 1,v represents a matrix of independent Rademacher variables etys, each uniformly distributed over +1) For any integer m 2 1, the Rademacher complexity of H the expectation of (IC) over all samples S of size m: (JC) = Es.DD [F)).
Using these notions of complexity, we prove the following cost-sensitive margin-based based guarantees. Theorem 7 (Margin bound for cost-sensitive classification). Let K be a family of functions mapping from Xx [n]] to R. Then. for any 5 O, with probability at least 1-6, each of the following inequalities holds for all h K. Rh) s 4C (J()+
log
2m
log
Re (h) s RR R 40 Rs())) + 3V
2m
The proof is included in Appendix I. These bounds can be generalized to hold uniformly for all P E 10. at the cost additional log log-terms, using standard proof techniques [Mohri et al., 2018, Theorem 5.9]. As with standard margin bounds, these learning guarantees suggest trade-off: Increasing P reduces the complexity term (second term) but simultancously increases the empirical cost-sensitive margin loss, (h) (first term), by imposing stricter confidence margin requirements. Thus, if h maintains a low empirical cost-sensitive margin loss even with relatively large value, admits a strong generalization error guarantee. Using the fact that (h) is upper bounded by LGCA (h/p), where c(x,g) p(v)
C, we derive the margin bounds for GCA losses below.
Pmii
RiBAL (h) Rs,laca (h/p)+ 4
log
(.. + V
Pmin
2m
log
REBAL (h) S RR (h/p) + /n sn +3
Pmin
2m
B.2 Margin bounds for GLA lossess
The previous section established margin bounds for GCA losses by leveraging their class weighted structure. In contrast, deriving analogous bounds for GLA losses is non-trivial due to their different formulation, which involves shifting logits based on class priors. To address this, we will rely on a non-trivial inequality presented in Lemma 8.
Given sample 5 (I Rm) and a hypothesis h, the empirical GLA loss is defined by Rs.ECLA (h) 1 Σm ÉGLA x, y.). For simplicity, our analysis focuses on the GLA loss with q= O. A similar line of reasoning allows for the extension of this proof to the general case where E (0, 1). In our setting of the balanced loss, the costs only depend on with c(y) = 1/p(y). Our analysis holds for arbitrary such y-dependent costs. Let Gmax denote upper bound Cmin lower bound on the costs. Define Cimax
Canax
Then, for any y. y y. the following holds:
log
Cmain
c(v)
c(y)
S Cmax-
log 1 +
c(y) e(v') log
Canin. Cmaae
Thus, for any p > and y. 1/ e y. we have (see illustration in Figure and proof of Lemma 8)
c(y) c(v
c(y) (1) S Ciax log 1
exp
30

---

20
min(1, max(o, W2))
Slep (1)
lnp G
15.
10
01
-6
-2
2
V
Figure Illustration of the bound in the proof of the margin loss for ÉLA
Using the monotonicity of the logarithm and upper-bounding a maximum of non-negative terms by sum yields the following any p 0 and any (x. y) E X y:
log 1 c(y)
1(2, v/) -1(2,1)
c(v) max 2 (b(x,)))) -(x,, s maax max v'*y
c(3/) exp
4'
8
cly)
h(2, (/0 11(20. 1)
S C max
log
max
exp
*+v c(v'
1 Σ d(y)
h(x 5¹) - -1(x,8)
$ Caax
log
exp
y' cly')
P
(1)
[(x,,15)) -h(ar,y))
CCmax
log
Σ
exp
c(r)
V'Ey
=max EGLA (h/p. 2. y).
Thus, this yields the margin-based based bounds for the GLA loss below. In our setting, Cmin 1 p(v) and
Cmax
Thus, as with the H-consistency guarantees, the margin bounds here depend
Pain
Puin
log 8 2m
RipAL (h) S
R Rs.aGLa (h/p) 22 Rm
Pmiin log[1 1 + Pmin]
Pmin
4
log
REnAi. (h) s
Rss.GLA (h/p) +
2n Rs
3
Punin log[1 1 Puin
Pinin
2m
Lemma 8. For any > and y.y' e yy we have
cly) 16 (v) s Cinax log 1 c(y) c(v')
exp -2)
for every R.
Proof. Fix labels y. y/ and a margin value u e R. Write c(y)
V and recall the bounds
c(v')
P
Cmin $ c(y)) S Cmax- By definition, Cmaxx
Cmax
Then, for any y e y, the following
log
Smin
emaxx
holds:
(1y)
c(y)
(6)
log 1
c(v) o(3)))
log
Sain
Omax
Next, we analyze case by case. (i) 0 (t S 0). Then (1) I and exp(-t) using (6) gives
Cmax log( 1 ae-t) Cmax log + a) c(y) (())
31

---

(ii) 0 S u p (0 s 5 1).
Define h(t) log(1 + ae - (1 log( + a). Since (t())
ae
a
+ ac loggllg(++0 + 2 I+a
+ logg + a) 2 0 (because log(1 + u) 2 u/ (1 u) for all u 2 0), we
have h(t) 2 h(0) 0; hence
(1- t) log(1 slog aE
Multiplying by Cmax and using (6) gives
Cmax log(1 ae Cmax log(1 a) ( =
(iii) p 2 1). Then @ (v) 0 and the desired inequality is trivial because the right- side is non-negative.
In conclusion, all three cases yield
c(y) d3y')
--"
(p)) maa log 1
exp
for every U R. This completes the proof.
B.3 Algorithms
The margin guarantees established in the previous section provide a foundation for developing new algorithms. We begin by deriving more explicit learning guarantee within broad framework. which we then use to define general cost-sensitive learning algorithm.
A. Explicit upper bounds. To make these guarantees more explicit, we introduce the following setup. Given feature mapping 4 X x [n]] + Rd we can identify [V(x,, y) Xy for all x e X and X max Xy, for some norm 1. We assume H is given by H = {h é Hi: |h| s H). for some appropriate norm 1-11, on some space H and H formulation covers wide range of hypothesis sets, including linear, kernel- -ased, and neural network models. In particular, captures the settings of neural networks with weight matrices constrained by Frobenius norm bound [Cortes et al., 2017, Neyshabur et al., 2015] or spectral norm complexity constraint relative reference weight matrices [Bartlett et al., 2017]. In all of these cases, the empirical Rademacher complexity can be upper bounded as follows:
[n]] with subset of Rd with
This
VTH
VTHX
Rs(JC
Σ m
m
where the complexity term depends on H. Combining this upper bound with Theorem yields the following more explicit guarantee.
Corollary 9. Fix p= [pn]ke[n] then, for any 5 > O, with probability at least 1 - over the choice of a sample S of size m, the following holds for any f H(:
2mH
log
RL) s (h)
Σ m 3
2m
As with Theorem this bound can generalized to hold uniformly for e (0. 1], at the cost of additional log log- log-terms. This generalized guarantee provides a basis for designing algorithms choosing h H( and o minimize the bound.
Let T be a decreasing convex function such that (>(x) s v (:) for all x and p > 0. may be the hinge loss, (zx)) max (0, 1.11-217 æ), any member of the broad family of composition-sum (comp-sum) losses [Mao et al., 2023f] defined by (xx) 20 (e "), with d for r 0 given by
+ ((1+ log(1 w)
0,+#1
Th (u)
1=
for all u. 0. This family includes the logistic loss 1) and the exponential loss (7 = 0). Using the fact that (t) < v (+)) the guarantee of Corollary 9 and its generalization to uniform bound
32

---

can be expressed as: for any > O, with probability at least 1 8, for all f é H, where the last term accounts for the log-log terms and the 6-confidence term
40V2nH
Ry (h) S
Σ class vi) max TM
Σ
m
s/((m]
m
B. General cost-sensitive algorithm. The bound leads the following regularization- bassd algo- rithm:
1 m
min
A|Mi|
Σ c( v.) max V s/((n]]
Rc3E
P
where À and ps are selected via cross-validation. This equivalent minimizing the following surrogate loss:
((h,,,)) = c(a y) max (M( y'e[n]
The preceding derivation shows that this form can be further upper-bounded by both GCA and GLA losses. Consequently, both loss families benefit from margin guarantees, though GCA losses achieve
more favorable bounds due the GLA bounds' dependence on 1/Pmin-
C Experimental details
This appendix provides supplementary information regarding the experimental setup discussed in Section 6. We first present the precise mathematical formulations for our algorithms and baseline loss functions used in the comparative analysis. Then, detail the specific hyperparameter ranges explored during the cross-valise validaaali process for each method.
Since our work focuses on principled surrogate losses for imbalanced data, our experiments aimed for a direct comparison with existing losses in their basic forms. We excluded common enhancements from data modification or optimization strategies to isolate the performance of the loss functions.
C.1 Loss function formulations
Let my be the number of samples in class k, and m be the total number of samples. Below the definitions of the loss functions optimized by our algorithms and those optimized by the baseline methods. For any triplet (h, x, y), where the hypothesis, x is the input, and is the label from set of classes:
Cross-Entropp (CE) Loss:
e ((x2))
lea x) -log
Σn-1 ch(a.))
Class Weishte Cross-Entropy (WCE) loss [Morik et al., 1999, Xie and Manski, 1989]:
@wer(h,
log
my Σ eh((e.))
Logit Adjusted (LA) Loss (7 [Menon al., 2021]:
ME.u))oog(mm)))
laa x, y) = -log Σソ- (l(r))))
Equalization (EQUAL) Loss [Tan et al., 2020]:
e b(x.y)
LEQUAL (h, -log
Σラ= (..h(a.))
with weight wy = 1- 31 12 1(883), where 3 Bernoulli(p), and > p>> 0, 1 A> are hyperparameters.
33

---

Balss-Bllacced (CB) Loss [Cui et al., 2019]:
lea (c,(h,200) 1-7 log my
ch(x,w)
Σ eh((z))
where 1> y is typerparaaeete.
FOCAL Loss [Ross and Dollár, 2017]:
b(ayy)
M(a.y)
FOCCAL (h. -
log
En=1 ch(zr))
Eラ= eh(z.))
where 2 is a hyperparameter.
LDAM Loss [Cao et al., 2019]:
e (a
L (h, log cl(z,y) By Ejty ch(=5))
where A for j e [n], and C 0 is hyperparameter.
Generalized Class-Aware (GCA) Loss:
m To b(z.i)lng
lGCA focA(h,
Eyyey eh(z.))ies
my
where E [0, 1) and p= (Piy..., Pr) is vector of positive parameters for each class. Generalized Logit-Adjusted (GLA) Loss:
M(a,)))+ lool my
EGLA EGLA(h, T79
Evey ((xe)) loo m ye/mm) 109
where g [0, 1) is a hyperparameter.
C.2
Hyperparameter search protocol
As stated in Section 6, all hyperparameters for the baseline methods and our algorithms were optimized via cross-validation. The search ranges for each tunable parameter were as follows:
CE Loss, WCE Loss: These methods do not have tunable hyperparameters beyond standard optimization settings.
LA Loss: We fixed the hyperparameter 7 as the algorithm only Bayes-consistent for that value.
EQUAL Loss: P was selected from {0.1, (0.1,022..... 0. 0.9). and À was selected from {0.176, 0.5, 0.8, 1.5, 2.0, 3.0, x 10-3 by following Tan et al. [2020].
CB Loss: 7 was selected from (0.1, .... 0.9, 0.99, 0.999, 0.9999) by following Cui et al. [2019],
FOCAL Loss: y was selected from 1.5. 10.0} and {0.0, Ross and Dollár [2017].
by following
LDAM Loss: was selected from {10-4 Cao et al. [2019].
104) and (5x 10-4 ...... 500%) by following
my/a
2/3 Σx_, m
GCA Loss: p was chosen as
by following Cortes al. [2025].
En. m was selected from {0.0, 0.1, ...l,....00. 0.9).
GLA Loss: g was selected from (0.0, 0.1......................... 0.9}.
34

---

D Conditional regret for the balanced loss: proof of Lemma
Lemma For any a X, the best-in-class conditional error and the conditional regret for BAL can be expressed as follows:
p
p x))
p(y x))
p(h(x)) a))
(H, ( = Σ
(b,
max gcH(x)
max ycH(x) p
(
p(y)
p(h(x)
yey
Proof. By the definition and Bayes' theorem, the conditional error can be expressed as follows:
p x)
(h,
Σ
h(z)=y
yc p(3)
p x)) p(h(2)
Σ yey
p(v) p(h(x))
Since (h(z):/ JC3 H(x), the best-in-class conditional error can be expressed as follows:
pvy (x)
p(y x:) yeH(x)
(H,
Σ
max
p
p(v)
yEy
which proves the first part of the lemma. This leads to which proves the second part of the lemma.
p(y x)) p(h(x) .x)
ACtRAt (h, CénAr (h, ClaAe (H(,x)
max yeH(x)
p(y) p(h(x))
E H--Consistency for the GCA losses: proof of Theorem
Theorem 5. Let H be a regular hypothesis and lACE a GCE loss. Assume that there exists function I'(t) = 31 for some E (0, and 3 > O, such that the following K-consistency bound holds for all h H and any distribution,
Reo (h) Ria (Hf) Meo (H) T ((Rtoon (h) R
Rioon (H) Miace (H)).
Then, the following H H-consistency bound holds for lGCA with respect to far all e H and any distribution:
RÉBAL (h) - -R (.) + Me (3O) S I(ReaeA (h) - Riccs (HI + Mecca (H)),
la
where T(() 3
ta In the special case where the approximation error Alcos (H) O, this
Pritn bound simplifies to:
RETAI. (n) - Ripa (I() & T(REGCA (i)-RR (3)).
-R)
Proof. The proof involves reduction of the conditional regrets of the balanced and GCA losses to those of the zero-one and GCE losses under newly defined distribution and the use of known H-consistency bounds for GCE losses. We define a new conditional probability q x) as q(y
ar) p(viz)
p(v) 2(²). where 7(x) Σ Eyey
p(giz) < 1_ is the normalization factor. By Lemma 1, the
p(x)
Pain
35

---

conditional regret of BAL can be expressed and bounded as follows:
p x) p(h(2)) x))
(h,,) = max
ply) p(h(2:)
(x) max q(v) q( -(<[(()(())))
yEy
(xx) ACo,
$ Z (x)I((ACaarra)). (h,
(H-consistency bound of (CCE)
= Z(x)
Σ
q ( ()) ( x))GGE(h, inf
Σ
DEy
hey
yeB
pvy x))
p(y x)) p(3)
= Z(x)
Σ wey
(aCR(h,
inf hey
Σ
(h,,)
((x)
p())
yey
T
Σ Dey
inf ply #:)GG (h, hey
Σ
p(v (lvla))cc it)acca (h,
(xx)
yey
= [
AC (c
2(x))
3 4(z))
1-a ACeacc, (h,
1-a A (h,
$
Pmin
Thus, taking expectations gives:
Renai. (h) (o)--Rignd
Riass (H) MenAi. (9)) E[ C
$ 1 ((AC (AAErccs.
E DC Ae
(concavity of I and Jensen's ineq.)
-((REGU (M) -Rissa Meacs (H)),
where Itt) 3 111 1-a
Pain ta. This concludes the first part of the proof. The second part follows directly from the fact that the minimizability gap Mecca (H) vanishes when the approximation error, Atoes (H), is zero. This concludes the first part of the proof. The second part follows directly using the fact that when the approximation error is zero: Atacx (H) = O, the minimizability gap
Micca (H) vanishes.
Note that, for simplicity, we assumed Py = for all y in Theorem and its proof. To handle varying values of Py, we can directly extend the "C-consistency bounds for the general cross-entropy (GCE) family, as derived in [Mao et al., 2023f.b], the setting where GCE uses distinct Py values. We can then similarly show that these extended bounds for the GCE family can be transformed into bounds for the GCA losses.
Negative results for the LA losses: proof of Theorem
Theorem 2. When 7 + the LA loss ELA not Bayes-consistent with respect to the balanced loss {BAL-
Proof. The Bayes classifier Li of the LA loss satisfies the following condition:
Mi (n log((()))
Evey (o.) log(p(())) = p(v x)
36

---

By rearranging the terms, we have
p(v x))
(z.())))
P(v) Σ (laaas)))
seey
p(x) y)((()
ppu) Σ (laaass)tTroogllo
(Bayes' theorem)
V'y
p( v)p(1) 1-T
Σ (7
p(z)
g'ey
Evecy e'En (oltr()
Thus, since the term
does not depend on y, we obtain
p(z)
hi,A (2) argmax (x, argmax (L. argmax =)
ycy
yey
By Lemma 1, we know that the Bayes classifier Maal of the Balanced loss satisfies that
ply x)
hal
argmax yey
argmax p(2: l
p(y)
yey
Therefore, for any # 1, there exists a distribution such that hi (x) # h This implies that when T # 1, the LA loss LA not Bayes-consistent with respect the balanced loss BALL
G Banss-Con for the GLA losses: proof of Theorem 3
Theorem 3. For any g [0,1), 1), the GLA Loss LOLA Bayes-consistent with respect to the balanced loss BAL
Proof. The Bayes classifier LLA of the GLA loss satisfies the following condition:
MoLa (2.z)+ (og(n(u))
F
(p(v x))
loxtere Evey MaLa (a.s))+ loxtete
Evey(P(y' x)) 1-
By rearranging the terms, we have
Eveey Mana (x.s/)) lostocy
(aLA(H.)) (p(v) | x)) (p())) 1-
Evey(p(D'' x))) i-
Eyrey Maoalan loalotu's)
p(x 11)
(Bayes' theorem)
p(x)
Epry(p(v [x))
Evecy HGLA (x.n)) lex(e(v()) 1-
Thus, since the term
does not depend on we obtain
Evey (p(w(()) -
heLA (w) argmaxhi (z, y) argmaxe HaLA argmax y). yey
yеy
yey
By Lemma 1, we know that the Bayes classifier Niai of the Balanced loss satisfies that
p(y x))
him argmax yey
argmax l
p(y)
yey
Therefore, we have hIGA (x) higt- This implies that the GLA loss fGLA is Bayes-consistent with respect to the balanced loss LALL
D
37

---

H H--Consistency for the GLA losses: proof of Theorem
Theorem 4. Assume that H. is complete. Then, for any q [0, 1), the following H-consistency bound holds for the GLA loss lGLA:
REBAL (h) R7 FEL + MEALL (H) s &T(ReaLA (h) - RiaLA (H) + Meaaa (H)),
where ((1) 22 for q O, and T(!) (pmin) I (1-g)
2 for q (0, 1). In the special case where the
Punt
approximation error ALGiA (IC) O, the bound simplifies to:
Renai. (h) -
- Rani. s (RRGIAA (h) - ReGiA (H)),
(h)-Praa
Proof. The proof involves characterization of the conditional regret of the balanced loss and the use of Gibbs distributions and Pinsker-type inequalities for analyzing GLA losses.
By Lemma 1, for complete hypothesis sets, the conditional regret of the balanced loss be expressed as follows:
A A Se max pv x)) p(h(=)) p(V) p(h(2))
ye
p(ulz) Let yx)) argmaxyey p(v) where we choose the label with the same deterministic strategy for
breaking ties as that of h(x) argmax (). We analyze by cases.
Case I: q O. In this case, the conditional regret for the GLA loss be written
((ww))log((())) Exyech(eessoossstte
CeGrA (h, = Σ yey
p(yl x)) log
Σp(u x) log(8(2.,)))
yey
where we let 8(x,8) y) Evey chle. E [0, 1] for any E y with h(2,8) v) h(z, y) + log(p(y)) and
the constraint that Egez 8(x, 1. Note that 5 can be viewed as a Gibbs distribution induced by
with prior p(y). Leveraging the facts that 8 is surjection and H is complete, minimizing over 8, know that e EGLA (H, x) has the following form:
Cioss (H,
Σ P(v x)) log(p(y) (:)).
yey
Thus, we obtain
AC (h, ClaLs (h, x) Cioca (HC,z)
plul x)) log(p()) x))
Σ p(y (z) log(((()))))
yey
yeh
e (zzy)+lg(((())
Σ ply 1)) log(p()) x)) Σ p(y x)) log log yey
Evey Hosss)))))))
yey
Evey ch (og(((()))
Σ p(y 1)) log p(u 2)) (((x))))((((v))) ycy
(pp =))))())))))
where D(pllq) is the relative entropy of two distributions p and q. Consider the case where y(r) h(x). Then, by Pinsker's 's inequality [Mohri et al., 2018, Proposition E.7], we have
=D(p(-1 ())))((x,)))
2 |pc. (lp(112) -0((1)))((x..))))
((2..)1;
(Pinsker's inequality)
((p(v(z)) -x)) -the)))))))
P(C())) p(y(2) x) 5(z,y(z))
+ +(h())) p(h(z) [x) 3(x,h(=))
)
p(y(z)) p(y(z))
p(h(z)) p(h(x))
38

---

Plugging the expression of The we have
A (Cte
1
p(y(z)) p(y(z) x=)
ch(av(()))
p(h(2)) 2x)
ch(a,((=))
p(((()))
2 2
p(y(z))
Evey (eeeee)ooooo
p(h(2))
Evey (Moos)))oop(((r e(a,((a))
( (pmin)
)²
(1
| (x)
(M(x(())
p(h(x) | (x)
2
2
2
p(y(=))
Eyeyy (hoecchoesss
p(h(x))
Σ Evey chater
(Pmin) 2²
p(y(x)) x) p(h(2) x)) p(y(2))
el(z,)(w))
el(a(()))
2
2
p(h(z))
+
E Eveyy ((ryeellsss
Eyeey (oogooo)))((()
(a) + |b| 2 la B)
(minn)
p(y())
p(h(2) x) 2
2
p(y(a))
p(h(a)
p(h(>))) 2 0 and Every an pelggttts p()(a))
p(h(x))ar)
Mans(()) Eyeey elt "'looooooo 2 0 by def. of y2z and h(x))
p(y(a))
(Pmin)
(AC (ACtnAl. (h,
2
Then, by taking the expectation on both sides and using the Jensen's inequality, we obtain
REBAL (h) - BAL + (H)) s I(ReaLa (h) - RRiaLA (9C) + MeGaa (3)),
-
where T(t)
V2
Pintn
Case II: q E (0, 1). In this case, the conditional regret for the GLA loss can be written as
e M(2,))+ (on(e(u))
CioLA (I), P(y ((vl)))p
1-9 Eneey e h(2:00)) (nc(ply
yey
DEy
where we let 8(x,1) =
Evey c [0, 1] for any y y with M(r,)) h(x log(p(v)) and I-q
the constraint that Eyey 8(x,y) =1 Note that & can be viewed as Gibbs distribution induced by h. Leveraging the facts that 8 is surjection and H is complete, minimizing over S, we know that
e: Claa (JC, x) has the following form:
- ply 1 1)) 1- (- p(u p(u|| 12)+ ( yey
Evey P(V (x) i- )
p(u x))
)
( Σ p(v T7
Eyen P(U i-
yey
Thus, we obtain
ACtora)(h,
= Crans (hi, x) - Cicca (H,
1 Σ p(vl
1
p(u x)) 2 Eyey ((u) x ))
p(y|
Σ
p(y [x)
1-
1 yey
② bey
P(alun) +
9
Evey p(vl x))
5(2
Ensy P()))) -
p(v 1h Evey p(s)ar)
1-9
1-0
1 1- Eyey
S(x,
Σ ply ro wey
1-8
Σ p(v T) yey
(s.1 (0)[(,))))({
39

---

where T (pllq) denotes the Tsallis relative entropy of order q between the distributions and q, and s(y x) Kull)
Σyny p(yz) Consider the case where y(x) * h(z). Then, by a Pinsker-type inequality [Rastegin, 2013, Eq. (4.13)), we have
A (Cronno((h,
1-9
Σ y86y
p (((yl))111
Ti (1=(s((1x)([((x,)
1-9
1-
Σ p(y )))
(s((12))- (1()))((r,))) ((
Jey
(Pinsker-type inequality [Rastegin, 2013, Eq. (4.13)))
1-9
9
Σ
pty 1))= +
((s((())
2
yey
1-9
1 ?
Σ
p 2))
2
WEy
s(y(x) x)
((z,)()))
+p(h(z)) - s(h(2) 5(z,h(z))
p(h(x)) - p(h(,:)) ))
x p(y(x))
p((()))) -
p(y(+))
1-9
2 (Pmin)
1-0
Σ p(v| 2
wEy
((y((z)) (x)
s(h(x)) x))
5(z,h(z)) {(x,y(x))
(aa) + |8| la Bl)
|P((())) - p(h(x:)) E p(h(a))
p(y( E.v
2 (Pmin) s(x(x))l) s(h(w)ll)
9
Σ p(u < p(y())) 1-7 p(h(x))=
s(y(x) (x)
s(h(x) x))
p(y(1)) p(h(z)) 2 0 and S(xh((x)) S(xy(=))
2 0 by def. of y(z) and h(x))
p(h(z)) 1-
p(v(=))
Plugging the expression s(- x)), we have
A (h,
2
1 q
(Pmin)
T-g
Σ p(y =
s(y(x) s(h(z) x))
2
p(y(z)) p(h(x))
yey
1 1-4
1
(pmin)
1-g
Σ p(y 2/ wey
p(y(z)
-(p(h(=))z) (2)(z)) (x)
2
p(y(x))
p(h(x))
5
1 1-9
(pmin)
I-m
Σ p(y = Mey
p(y(z) x)
p(y(z) (x)
((h(z) ())
((((x)) x))
2
p(y(*)) p(y(x))
p(h()))
p(h(::)
F4 p(h(2) ())
(((((z) x)) r4
2
1
q
(Pmiu)
Σ p(yl = Deyy
p(y(=) x) p(y(*))
(P((() x))
2
p(y(x))
p(h(x))
p(h(x))
7-
1-
p(y(x)
p(y(z) x))
p(h(z) [
(pmin)
1-1
Σ p(y 2)
p(y(x))
p(y(z))
p(h(z))
yey
40

---

Next, using Egey (1)2))=+ = |
1-g s lp( | 1- and p(v(x)=)
p(ula)
1,
p(y(z))
p(g)
we can write:
1 1-9
- p(y(x) (x) p(h(2)) (x)
AC (h)
(pmin)
2
p(y(x)) p(h(r))
1- q (Pmin)
(ACEBAL 36 x))
Then, by taking the expectation on both sides and using the Jensen's inequality, we obtain
Renai (h) RnAi. (H) + MMAAI.HH) s (RRaai (h) RiaiA (HC + Me (H));
where I'(t) (Pmin)) T (1-9)
/2
This concludes the first part of the proof. The second part follows
directly using the fact that when the approximation error is zero: AlaLa (H) = O, the minimizability gap MeGLa (IC) vanishes.
I Margin bound: proof of Theorem 7
Theorem 7 (Margin bound for cost-sensitive classification). Let H. be a family of functions mapping from Xx [ni] to R. Then, for any 8 O, with probability at least 1 ō, each of the following inequalities holds for all h e 9C:
log
(n) s 4CC
2m
log
(h) S Rs, 40 Rs + 3\
2m
Proof. Consider the family of functions taking values [0, 1]: H = {z (x,y) - L, x, y): : h H}.
By [Mohri et al., 2018, Theorem 3.3]. with probability at least 1 6, for all e K",
B[s(=)] 1 Σ Eg(z) 25(( + +31 m
log 2m
and thus, for all e H.
log 2
E E[L 2. y)] ] (s, (3C) + 31
2m
Since R((h) RR, (h) B (h, v) we have
log A 2m
Ri (h) (1) 2Rs(H() +31
Fix h, (Ii, and p 0, define Vi follows:
([h(s,, v)] = c(x;,))) max ( M(x, v/)). s'((m]
Then, by the sub-additivity of the maximum operator, we can write for any f. JC:
& ([h(=,, 9) (=())))) -((
s c( vi) max (1( v:) h (II,, //))//))))))))) -((;, vi) max ( (T(2;, v.) Fr ()), s'c(n)
s'([n]
20(x1. vi) <
(by !-Lipschitzness of b)))
20 2 (I -)(
41

---

Thus, V/ is 2/n Lipschitz with respect to the I-l2 norm. Thus, by the vector contraction lemma [Maurer, 2016, Cortes et al., 2016), Rs(" can be bounded as follows:
Rg (H') s 2CV22m 5 (HHHH)
This proves the second inequality. The first inequality, can be derived in the same way by using the first inequality of [Mohri et al., 2018, Theorem 3.3].
42


Reviews:
[{"review_id": "m5tw7QZlEJ", "reviewer": "Reviewer_oVh8", "summary": "The authors give two novel surrogate loss function families for addressing class imbalance in multi-class classification: Generalized Logit-Adjusted (GLA) losses and Generalized Class-Aware weighted (GCA) losses. \n\nThe authors provide theoretical analysis showing that GLA losses are Bayes-consistent but only $H$-consistent for complete hypothesis sets with bounds scaling as $1/p_{min}$, while GCA losses are $H$-consistent for both bounded and complete hypothesis sets with more favorable bounds scaling as $1/\\sqrt{p_{min}}$. \n\nExperimental results on image datasets show that both loss families outperform existing baselines.", "questions": "Line 14: \"H-consistent for unbounded and complete hypothesis sets\" - The conjunction \"and\" is confusing here. Should clarify if both conditions are required or if it's \"unbounded or complete.\"\n\nLine 92: \"The margin $\\rho_h(x, y)$ for a predictor $h \\in H$\" - The margin notation $\\rho$ conflicts with the imbalance ratio $\\rho$ used later.  Could you clarify? \n\nLine 130: The LA loss definition uses $\\tau$ but the text doesn't clearly explain what happens when $\\tau \\neq 1$ until much later.\n\nLine 177: $\\rho = (\\rho_1, \\ldots, \\rho_n)$ - This reuses the margin notation from Page 3.\n\nLine 191: \"Note that while the $\\rho_k$ values can be freely tuned\" - What do you mean? \n\nLine 258: The bound $\\Gamma(t) = \\sqrt{\\frac{2t}{p_{min}}}$ -  Is this a tight bound?\n\nLine 283: The theorem statement is quite dense and could benefit from more intuitive explanation.\n\nLine 343: \"imbalance ratio, $\\rho = \\frac{\\max_{k=1}^c m_k}{\\min_{k=1}^c m_k}$\" - The notation $c$ for number of classes conflicts with the usage of $n$ elsewhere.\n\nLine 351: \"200 epochs\" - No justification for this choice or sensitivity analysis.\n\nEq (5): The confidence margin parameters $\\rho_y$ should be clearly distinguished from the margin function $\\rho_h(x,y)$ defined earlier.\n\nHow sensitive are the GCA losses to the choice of confidence margin parameters $\\rho_y$?\n\nWhat is the computational complexity comparison between GLA and GCA losses?\n\nAre there convergence guarantees for the optimization of these loss functions?\n\nIt would be great if the authors clarify the proof novelty compared to Mohri et al., 2018 and Mao et al., 2023b,a.", "limitations": "N.A.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper provides rigorous theoretical analysis (in the supplement) with well-established consistency results. \n\nThe presentation is good, especially Sections 2 and 3, which provide a good foundation for the main results of the paper.\n\nThe experiments include proper statistical reporting.  They compare against relevant baselines across different datasets.\n\nWeaknesses:\n\nThe theoretical novelty is limited. It would be great if the authors clarify the proof novelty compared to Mohri et al., 2018 and Mao et al., 2023b,a in the main part of the paper.\n\nThe experiments are restricted to image classification tasks (CIFAR-10/100, Tiny ImageNet) with relatively simple architectures (ResNet-32). The generalizability to other domains and modern architectures is unclear.\n\nThe paper mentions that $\\rho_k$ values in GCA losses can be tuned via cross-validation but provides limited guidance on computational complexity or sensitivity analysis. The suggestion to use $[m_k^{1/3}]_k$ as starting points without any intuitions theoretical justification.\n\n\nWhile the paper mentions training details, it doesn't thoroughly analyze the computational cost of the proposed methods compared to baselines.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns. Some concerns remain regarding the novelty of the proofs with respect to Mohri et al. (2018) and Mao et al. (2023a, 2023b)", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n\n**1. The theoretical novelty is limited. It would be great if the authors clarify the proof novelty compared to Mohri et al., 2018 and Mao et al., 2023b,a in the main part of the paper.**\n\n**Response:** Mohri et al. (2018) presented margin bounds for standard multi-class classification. In contrast, we derive new margin bounds for cost-sensitive classification, a setting that introduces additional complexity due to the presence of instance-dependent cost functions. This requires the development of new proof techniques, including the derivation of an upper bound on the loss function expressed in terms of a margin loss and a maximum operator, along with an analysis of the Rademacher complexity of this maximum term via the vector contraction lemma. Moreover, in addition to the resulting margin bounds for GCA loss functions, our margin bounds for GLA loss functions are non-trivial and require a specific and entirely new analysis (Appendix B.2).\n\nMao et al. (2023a,b) studied H-consistency bounds for loss functions in the general cross-entropy (GCE) family with respect to the standard multi-class 0-1 loss. In contrast, our work establishes H-consistency bounds for the proposed GCA and GLA losses with respect to the balanced loss, where both the surrogate and target losses are more complex. This required several novel technical contributions, including a characterization of the conditional regret of the balanced loss, the use of Gibbs distributions and Pinsker-type inequalities for analyzing GLA losses, and a reduction of the conditional regrets of the balanced and GCA losses to those of the 0-1 and GCE losses under a newly defined distribution.\n\nWe will further elaborate on the novelty of our proof techniques and provide a more detailed account of our technical contributions in the main body of the final version, making use of the additional page limit.\n\n**2. The experiments are restricted to image classification tasks (CIFAR-10/100, Tiny ImageNet) with relatively simple architectures (ResNet-32). The generalizability to other domains and modern architectures is unclear.**\n\n**Response:** We followed closely the experimental setup of prior work cited in Section 6, using standard image benchmarks (CIFAR-10/100, Tiny ImageNet) and ResNet-32 to ensure comparability. We agree that a broader evaluation is important and are happy to report results for additional tasks and architectures in the final version.\n\n**3. The paper mentions that $\\rho_k$ values in GCA losses can be tuned via cross-validation but provides limited guidance on computational complexity or sensitivity analysis. The suggestion to use $[m_k^{1/3}]_k$ as starting points without any intuitions theoretical justification.**\n\n**Response:** We followed (Cortes et al., 2025) in using $\\rho_k = m_k^{1/3}$ in our experiments. A similar derivation to theirs can be adapted to our setting, showing that these values are theoretically optimal in a separable case, which provides a justification and guidance for selecting $\\rho_k$ for GCA losses. Empirically, we also found GCA losses to be robust to variations in $\\rho_k$ around these values. While $\\rho_k$ can be tuned via cross-validation, the default choice of $m_k^{1/3}$ performs well. We will further clarify these points and include a discussion in the final version.\n\n**4. While the paper mentions training details, it doesn't thoroughly analyze the computational cost of the proposed methods compared to baselines.**\n\n**Response:** For fixed hyperparameters, the computational cost of our proposed methods is comparable to that of standard neural networks trained with cross-entropy loss (that is, logistic loss with softmax) and to that of the baselines. Our approach remains practical with commonly used optimizers such as SGD, Adam, and AdaGrad. While our methods introduce additional hyperparameters, namely $\\rho_k$ and $q$ in GCA losses and $q$ in GLA losses, the value of $\\rho_k$ has a default choice (as discussed above), and $q$ serves a similar role to hyperparameters in the baseline methods listed in Table 1, many of which also involve at least one extra tunable parameter. We will further elaborate on the computational cost and provide more detailed comparisons in the final version.\n\n**Questions:**\n\n**1. Line 14: \"H-consistent for unbounded and complete hypothesis sets\" - The conjunction \"and\" is confusing here. Should clarify if both conditions are required or if it's \"unbounded or complete.\"**\n\n**Response:** Thank you. Here, \"unbounded\" and \"complete\" refer to the same condition, and \"and\" was intended to mean \"or.\" We will revise the wording to clarify this in the final version.\n\n**2. Line 92: \"The margin $\\rho_h(x, y)$ for a predictor $h \\in H$\" - The margin notation $\\rho$ conflicts with the imbalance ratio $\\rho$ used later. Could you clarify?**\n\n**Response:** Thank you. We will revise the notation.\n\n**3. Line 130: The LA loss definition uses $\\tau$ but the text doesn't clearly explain what happens when $\\tau \\neq 1$ until much later.**\n\n**Response:** Thank you. We will move the comment on the case $\\tau \\neq 1$ directly after the loss definition for better clarity.\n\n**4. Line 177: $\\rho = (\\rho_1, \\ldots, \\rho_n)$ - This reuses the margin notation from Page 3.**\n\n**Response:** Thank you. We will revise the notation to avoid this conflict.\n\n**5. Line 191: \"Note that while the $\\rho_k$ values can be freely tuned\" - What do you mean?**\n\n**Response:** We mean that the $\\rho_k$ values can be treated as tunable hyperparameters in practice, which may further improve performance. In our experiments, we use the theoretically guided values $\\rho_k = m_k^{1/3}$.\n\n**6. Line 258: The bound $\\Gamma(t) = \\sqrt{\\frac{2 t}{p_{\\min}}}$  - Is this a tight bound?**\n\n**Response:** The bound can be tightened by using the exact expression, such as the inverse of the function $T$ in Theorem 3.1 of (Mao et al., 2023b), instead of the square root approximation. We used the square root form for simplicity of presentation, following the same approximation approach as in (Mao et al., 2023b).\n\n**7. Line 283: The theorem statement is quite dense and could benefit from more intuitive explanation.**\n\n**Response:** Thank you. We will use the additional page in the final version to provide more intuitive explanations of the theorems.\n\n**8. Line 343: \"imbalance ratio, $\\rho = \\frac{\\max_{k = 1}^c m_k}{\\min_{k = 1}^c m_k}$\" - The notation $c$ for number of classes conflicts with the usage of $n$ elsewhere.**\n\n**Response:** Thank you. We will revise the notation to consistently use $n$ for the number of classes.\n\n**9. Line 351: \"200 epochs\" - No justification for this choice or sensitivity analysis.**\n\n**Response:** We followed (Cortes et al., 2025) in using 200 epochs, which is a standard choice in the literature.\n\n**10. Eq (5): The confidence margin parameters $\\rho_y$ should be clearly distinguished from the margin function $\\rho_h(x, y)$ defined earlier.**\n\n**Response:** Thank you. We will revise the notation to clearly distinguish the two.\n\n**11. How sensitive are the GCA losses to the choice of confidence margin parameters $\\rho_y$?**\n\n**Response:** We followed (Cortes et al., 2025) in using $\\rho_k = m_k^{1/3}$, which can be shown to be theoretically optimal in our setting as well. Empirically, GCA losses are robust to variations around these guided values.\n\n**12. What is the computational complexity comparison between GLA and GCA losses?**\n\n**Response:**  For fixed hyperparameters, the computational cost of GLA and GCA losses is comparable to standard training with cross-entropy loss. Both involve a hyperparameter $q$, and GCA additionally uses per-class margins $\\rho_k$, for which we adopt a default choice $\\rho_k = m_k^{1/3}$. We will include more detailed comparisons in the final version.\n\n**13. Are there convergence guarantees for the optimization of these loss functions?**\n\n**Response:** Our loss functions are adapted from the general cross-entropy family and share similar convergence behavior when optimized with standard methods such as SGD, Adam, and AdaGrad. We will clarify this and provide more discussion in the final version.\n\n**14. It would be great if the authors clarify the proof novelty compared to Mohri et al., 2018 and Mao et al., 2023b,a.**\n\n**Response:** We refer to our response to “Weakness 1” for clarification on the proof novelty."}, {"review_id": "iavOL2WpQv", "reviewer": "Reviewer_Swme", "summary": "The authors present generalized versions of the logit-adjust (LA) loss and the class-aware (CA) loss. They extend these through the generalized cross-entropy framework and show that they admit strong theoretical guarantees in terms of bayes consistency and $\\mathcal{H}$ consistency.  The authors also demonstrate the efficacy of their methods on CIFAR10 and 100 with imbalance.", "questions": "1. How well-behaved are these loss functions in terms of optimization? Similar methods like $\\alpha$-loss (Sypherd et al.) can make the optimization procedure quite slow in practice. \n2. Ablations demonstrating the impact of the choice of $q$ could help readers better internalize its meaning and importance for tuning.\n3. Ablations for the inclusion of $\\rho$ in GCA would also be helpful.\n4. A key shortcoming of standard weighted cross entropy is in the highly overparameterized setting. How do GCA and GLA fare when data is limited?\n5. The weighting factor for GCA need not be the class prior. Tuning over this would be very interesting and give insights into whether the prior is an optimal choice for $q\\ne1$.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n1. The paper is clear and well-written\n2. The theoretical guarantees for both GLA and GCA are quite strong, and the proofs themselves have novelty. The favorable scaling of GCA with $p_\\text{min}$ is especially compelling.\n3. The empirical performance of these methods is compelling, especially compared with more specialized methods like focal loss. \n\n# Weaknesses\n1. The novelty of the generalization is somewhat limited, simply be a simple extension of LA and CA under the GCE framework. \n2. The additional positive margins $\\rho$ included in GCA are new hyperparameters to tune, and their impact is not completely clear. Similarly with $q$ in both GLA and GCA. Including ablations to demonstrate the sensitivity to these choices would be helpful.\n3. The choice of the inverse of the prior for GCA is not clearly justified in the setting of $q\\ne1$ as it could be for $q=1$.", "was_revised": true, "final_justification": "Additional discussion of the proof novelty will be included in the revision which will greatly strengthen the results. Additionally, the authors' rebuttal addressed my major concerns and those of other reviewers. I believe this work will be interesting to the community at large.", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n\n**1. The novelty of the generalization is somewhat limited, simply be a simple extension of LA and CA under the GCE framework.**\n\n**Response:** The novelty of the generalization lies in ensuring that the extended formulations satisfy consistency guarantees. For example, the $(1 - q)$ factor in Eq. (4) is essential to the definition of GLA losses, ensuring Bayes-consistency for any $q \\in [0, 1)$ (as shown in Section 5.2). This offers greater flexibility than the original LA loss, which is only Bayes-consistent when $\\tau = 1$. Moreover, GLA losses enjoy stronger $H$-consistency guarantees when the hypothesis set $H$ is complete. We also refer to our response to Reviewer oVh8 (“Weakness 1”) for a more detailed discussion of the novel proof techniques used to establish these guarantees.\n\n**2. The additional positive margins $\\rho$ included in GCA are new hyperparameters to tune, and their impact is not completely clear. Similarly with $q$ in both GLA and GCA. Including ablations to demonstrate the sensitivity to these choices would be helpful.**\n\n**Question 2. Ablations demonstrating the impact of the choice of $q$ could help readers better internalize its meaning and importance for tuning.**\n\n**Question 3. Ablations for the inclusion of $\\rho$ in GCA would also be helpful.**\n\n**Response:** We followed (Cortes et al., 2025) in using $\\rho_k = m_k^{1/3}$ in our experiments. A similar derivation to theirs can be adapted to our setting, showing these values are theoretically optimal in the separable case, thereby providing a principled default. Empirically, GCA losses are robust to variations in $\\rho_k$ around these values, though they can be tuned via cross-validation if desired. We will further elaborate on that in the final version.\n\nFor the parameter $q$ in both GLA and GCA, we selected values from ${0.1, 0.2, \\ldots, 0.9}$, which are standard choices within the general cross-entropy family. Its performance depends on dataset imbalance (e.g., long-tailed vs. step imbalance).\nWe will clarify these points and include additional ablation analysis in the final version.\n\n**3. The choice of the inverse of the prior for GCA is not clearly justified in the setting of $q \\neq 1$ as it could be for $q = 1$.**\n\n**Response:** The motivation for using the inverse of the prior in GCA remains the same for $q \\neq 1$ as for $q = 1$. The parameter $q$ simply specifies a particular loss within the generalized cross-entropy family, applicable in both standard and imbalanced settings. The inverse of the prior is used to align with the definition of the balanced loss, which reduces the influence of class imbalance by reweighting each example's error accordingly. This ensures that GCA losses benefit from consistency guarantees with respect to the balanced loss. We will clarify this in the final version.\n\n**Questions:**\n\n**1. How well-behaved are these loss functions in terms of optimization? Similar methods like $\\alpha$-loss (Sypherd et al.) can make the optimization procedure quite slow in practice.**\n\n**Response:** Our loss functions are adapted from the general cross-entropy family and share similar convergence behavior when optimized with standard methods such as SGD, Adam, and AdaGrad. We will clarify this and provide more discussion in the final version.\n\n**4. A key shortcoming of standard weighted cross entropy is in the highly overparameterized setting. How do GCA and GLA fare when data is limited?**\n\n**Response:** Our study did not aim to specifically favor either overparameterized or standard parameterized settings. Rather, we closely followed the experimental setup used in prior work cited in Section 6 to ensure comparability. Investigating the behavior of GCA and GLA in overparameterized or data-limited regimes is indeed a compelling direction for future work. Regarding weighted cross-entropy, we note that such methods have been shown empirically not to be effective in general, including in non-overparameterized settings, depending on various factors (e.g., Van Hulse et al., 2007).\n\n**5. The weighting factor for GCA need not be the class prior. Tuning over this would be very interesting and give insights into whether the prior is an optimal choice for $q \\neq 1$.**\n\n**Response:** From a theoretical perspective, the use of the inverse of the prior in GCA for $q \\neq 1$ is motivated by the same reasoning as for $q = 1$: it aligns with the definition of the balanced loss and ensures consistency guarantees. However, from a practical standpoint, exploring alternative weighting schemes is indeed interesting and could provide insight into whether the prior is optimal. We will consider including this analysis in the final version."}, {"review_id": "yOkVPqDZ71", "reviewer": "Reviewer_S8CM", "summary": "This paper proposes two novel surrogate loss functions for multi-class classification under class imbalance: Generalized Logit-Adjusted (GLA) loss and Generalized Class-Aware weighted (GCA) loss, building on the existing general cross-entropy (GCE) framework (Mao et al. ICML 2023). GLA losses generalize Logit-Adjusted losses, which shift logits based on class priors, to the broader general cross-entropy loss family. It includes theoretical analysis of consistency of the two proposed surrogate loss functions. Extensive experiments are conducted to evaluate the performance of GLA and GCA, in comparison with existing surrogate loss functions, demonstrating different operating characteristics of GLA and GCA.", "questions": "1) How to assess whether the key assumptions underlying the theoretical results in Section 5 hold in real-world data? Under what real-world settings are these assumptions plausible?\n\n2) How do the proposed GCE and GCA compared to IMMAX (Cortes et al. 2025) in terms of their theoretical properties? \n\n3) It would strengthen the experiemental results to more recent baseline methods such as \nIMMAX (Cortes et al. 2025) and LSC (Wei et al., 2024).", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: Building on the existing general cross-entropy (GCE) framework (Mao et al. ICML 2023), this work proposes and studies two surrogate loss functions, the generalized logit-adjusted (GLA) loss and the generalized class-aware (GCA) loss. In GCA, $\\rho$ is motivated by Cortes et al. (2025). Strong theoretical results are provided for consistency of GLA and GCA, showing that GLA is Bayes-consistent, but only $\\mathcal{H}$-consistent for unbounded and complete hypothesis sets whereas GCA is $\\mathcatl{H}-consistent for any hypothesis set that is bounded or complete and offers significantly stronger theoretical guarantees in imbalanced settings. Extensive experiments are conducted to demonstrate the superior performance of GLA and GCA in comparison with existing surrogate loss functions and also show different operating characteristics of GLA and GCA.\n\n\nWeakness: It is unclear why directly optimizing the balanced classification loss is intractable.\n\nIt is unclear whether the key assumptions underlying the theoretical results in Section 5 are plausible in real-world data.\n\nIt is unclear How the proposed GCE and GCA compared to IMMAX (Cortes et al. 2025) and other existing surrogate losses in terms of theoretical properties.\n\nSection 6: The numerical experiments did not include more recent baseline methods such as  IMMAX (Cortes et al. 2025) and LSC (Wei et al., 2024).", "was_revised": true, "final_justification": "I don't have additional major comments and will maintain my positive score for this paper.", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Weakness 1. It is unclear why directly optimizing the balanced classification loss is intractable.**\n\n**Response:** Directly optimizing the balanced classification loss is intractable because it involves an indicator function over the prediction and true label, making the objective discrete and non-differentiable. This is analogous to the standard 0-1 loss, which is also known to be intractable to optimize directly in the literature.\n\n**2. Weakness 2. It is unclear whether the key assumptions underlying the theoretical results in Section 5 are plausible in real-world data.**\n\n**Question 1. How to assess whether the key assumptions underlying the theoretical results in Section 5 hold in real-world data? Under what real-world settings are these assumptions plausible?**\n\n**Response:** The assumptions in Section 5 primarily concern properties of the hypothesis set. These are standard and typically satisfied in practice. Most natural hypothesis sets, such as linear models, neural networks, and the set of all measurable functions, are regular, meaning they produce predictions across all $n$ classes. Whether a hypothesis set is bounded or complete depends on the modeling choice (e.g., bounded weights in linear models). Importantly, our results do not assume any specific data distribution and hold for arbitrary distributions, including those arising in real-world settings.\n\n**3. Weakness 3. It is unclear how the proposed GCE and GCA compared to IMMAX (Cortes et al. 2025) and other existing surrogate losses in terms of theoretical properties.**\n\n**Question 2. How do the proposed GCE and GCA compared to IMMAX (Cortes et al. 2025) in terms of their theoretical properties?**\n\n**Response:** The key difference is that IMMAX (Cortes et al., 2025) is designed for optimizing the standard multi-class 0-1 loss under imbalanced data, whereas the proposed GCE and GCA losses are designed to optimize the balanced loss. As a result, IMMAX enjoys consistency with respect to the standard 0-1 loss, while GCE and GCA are consistent with respect to the balanced loss, a property most existing surrogate losses lack, as discussed in Section 3.3.\n\n**4. Weakness 4. Section 6: The numerical experiments did not include more recent baseline methods such as IMMAX (Cortes et al. 2025) and LSC (Wei et al., 2024).**\n\n**Question 3. It would strengthen the experimental results to more recent baseline methods such as IMMAX (Cortes et al. 2025) and LSC (Wei et al., 2024).**\n\n**Response:** IMMAX is designed to optimize the standard multi-class 0-1 loss under imbalanced data, whereas our proposed losses are specifically tailored to optimize the balanced loss. Therefore, we expect IMMAX to be inferior to our methods in terms of balanced error, which is our primary objective. We are happy to include comparisons with IMMAX (Cortes et al. 2025) and LSC (Wei et al., 2024) in the final version."}, {"review_id": "KRJBGoLlau", "reviewer": "Reviewer_UxSp", "summary": "This paper motivates a new algorithm for conducting class-balanced cross entropy (CE) minimization. The paper states that class-balanced CE minimization has been addressed via heuristic methods such as class-weighted CE and logit-adjusted loss, but that these methods lack desired theoretical properties such as Bayes consistency. The paper then develops two new loss functions - Generalized Logit-Adjusted Loss (GLA) and Generalized Class-Aware Loss (GCA), as algorithms that upper bound the true cost-sensitive loss while having strong theoretical properties of Bayes consistency and H-consistency. The experimental results show that the new loss functions perform the best in terms of balanced-error when used in multi-class classification, for different kinds of class-skew in the training data.", "questions": "The paper is as a whole excellent and significant, the following are my suggestions to make it more accessible to readers not as familiar with this style of work and further increase adoption:\n1. Add further details for why class-weighted CE does not work well. This is (in my experience) by far the most common approach to handling this very general problem. Identifying the errors more clearly can go a long way to further boost the significance of the results. For example, the graph on the (lack of) H-consistency of LA loss is great.\n2. When introducing the GCA loss, it says that $\\rho$ is \"is a vector of positive confidence margin parameters for each class.\" Practically speaking, what is this supposed to be? More hyperparameters typically yields more complications when trying to use a loss in practice, so helping clarify what these are meant to represent may provide more transparency around using this loss.\n3. The proofs could really use more annotation. A \"plan\" before the proof starts would go a long way, as would more details about how one step flows into the next. There appear to be some interesting techniques used, such as in the H-consistency results of GCA where the authors transform GCA to GCE via the change of measure and then use known consistency results. Hence, it would be really helpful to have some description. \n4. Most of the notation seems to be clearly defined, but I could not find where $\\mathcal{E}$ was defined. I'm guessing it's the empirical loss, but overall I recommend one more parse through the paper to check that notation is clearly defined.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Quality**: This paper is overall excellent. The GLA and GCA algorithms are very well-grounded, as they are motivated by the true balanced loss and naturally derived as being tractable surrogates through manipulation of the margin loss. Additionally, the theorems go beyond traditional convergence under convexity style proofs and show Bayes consistency/H-consistency, adding another layer of theoretical backing to the algorithms. The experiments are well-conducted and benchmarks against several well-known, relevant algorithms in this domain (e.g. focal loss, logit-adjusted, class-weighted CE, etc.). The experimental setting is slightly limited (three CV datasets) but is nonetheless appropriate and well-justified, as there are indeed several classes and the authors clearly explain how class imbalanced is induced. The proofs are difficult to read as they do not have much annotation, but from what I can gauge, they appear correct and have a logical development (e.g. $\\rho$-margin loss -> upper bound -> GLA loss). The differences between the GLA and GCA loss are also clearly elucidated. \n\n**Clarity**: Despite the excellent theoretical results, this paper was difficult to parse in multiple parts and needs some improvement (although I fully acknowledge the space limitations). At a high level, the lack of clarity is in some details, such as why weighted CE does not work well when data is easily separable, what the confidence margin parameters are supposed to represent, what the evaluation \"balanced error\" actually is, etc. Most importantly the proofs are hard to read. More details in the suggestions.\n\n**Significance**: This is a very significant advancement in the development of class-balanced error minimization. Class-balanced error indeed has several applications, including in fairness, fraud-detection, rare-event detection, etc. In practice, class-weighted CE is used (or equivalently, data resampling), but this paper proposes a new path forward that presents a more theoretically disciplined, yet tractable approach. The proofs are also quite novel, and may be useful for future research in this area.\n\n**Originality**: This paper is very original. It appropriately reviews existing literature around this topic and identifies the key works. The methods use to develop the GCA/GLA are relatively novel, as they take a principled approach to upper bounding the class-weighted 0/1 loss and develop a surrogate accordingly. I am not as familiar with proofs in Bayes consistency/H-consistency to judge if they are novel, but considering these results are rarely developed in research regarding loss-functions, they feel novel to me.", "was_revised": true, "final_justification": "This paper overall presents a novel solution to a fairly foundational problem in ML - weighted class cross entropy. The solution and techniques used in the paper are interesting to read and provide a theoretically justified and practical approach to improving solving class imbalance classification problems. My main concerns were around the accessibility and clarity of the paper, but provided that the authors work to improve the interpretability and more hand-holding through the relatively dense proofs, my rating is an accept.", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Strengths And Weaknesses: Quality ... Originality.**\n\n**Response:** We sincerely thank the reviewer for their positive assessment of the paper’s quality, significance, and originality. We appreciate your recognition of the principled derivation of GLA and GCA, the theoretical contributions on Bayes and H-consistency, and the relevance of our empirical evaluation.\n\nRegarding clarity, we agree that certain parts of the paper would benefit from improved exposition. In the final version, we will use the additional page to enhance the presentation for readers. Specifically, we will clarify why weighted cross-entropy can perform poorly in the separable regime, explain the interpretation of the confidence margin parameters (see responses to specific questions for more details), define and motivate the “balanced error” metric (i.e., the average of the balanced loss over the test data), and provide more intuitive explanations to help guide the reader through the proofs. Thank you again for your constructive feedback.\n\n**Questions:**\n\n**1. Add further details for why class-weighted CE does not work well. This is (in my experience) by far the most common approach to handling this very general problem. Identifying the errors more clearly can go a long way to further boost the significance of the results. For example, the graph on the (lack of) H-consistency of LA loss is great.**\n\n**Response:** Thank you for the insightful comment. In separable cases, class-weighted cross-entropy may still yield solutions with zero training loss that do not adjust decision boundaries meaningfully toward minority or majority classes. This is because class weighting does not influence the classifier once perfect separation is achieved. As a result, the method fails to address imbalance in such regimes. We will add further details and discussion of this issue in the final version to better highlight the limitations of class-weighted CE.\n\n**2. When introducing the GCA loss, it says that $\\rho$ is \"a vector of positive confidence margin parameters for each class.\" Practically speaking, what is this supposed to be? More hyperparameters typically yield more complications when trying to use a loss in practice, so helping clarify what these are meant to represent may provide more transparency around using this loss.**\n\n**Response:** Thank you for the thoughtful question. The confidence margin parameters $\\rho_y$ allow for fine-grained adjustment of decision boundaries on a per-class basis. Specifically, by scaling the logit differences $h(x, y) − h(x, y')$ by $\\rho_y$, the GCA loss effectively adjusts margins in a class-specific way. This transformation enables the model to better distinguish between dominant and rare classes, as it modulates how confidently each class needs to be separated. As highlighted by Cortes et al. (2025), such margin adjustments play a key role in shifting decision boundaries and mitigating imbalance, addressing limitations of simpler class-weighting schemes. \n\nWe followed (Cortes et al., 2025) in using $\\rho_k = m_k^{1/3}$ in our experiments. A similar derivation to theirs can be adapted to our setting, showing these values are theoretically optimal in the separable case, thereby providing a principled default. Empirically, GCA losses are robust to variations in $\\rho_k$ around these values, though they can be tuned via cross-validation if desired. We will further elaborate on that in the final version.\n\n**3. The proofs could really use more annotation. A \"plan\" before the proof starts would go a long way, as would more details about how one step flows into the next. There appear to be some interesting techniques used, such as in the H-consistency results of GCA where the authors transform GCA to GCE via the change of measure and then use known consistency results. Hence, it would be really helpful to have some description.**\n\n**Response:** Thank you for the helpful suggestion. We agree that adding more annotations and an outline before key proofs would significantly improve readability. In the final version, we will provide a brief “proof plan” before each major result to explain the high-level strategy and highlight key steps and techniques, such as the change of measure used to relate GCA to GCE in the $H$-consistency proof. We will also add more intermediate explanations to clarify how each step follows, especially in technically involved arguments.\n\n**4. Most of the notation seems to be clearly defined, but I could not find where $\\mathcal{E}$ was defined. I'm guessing it's the empirical loss, but overall I recommend one more parse through the paper to check that notation is clearly defined.**\n\n**Response:** Yes, $\\widetilde{\\mathcal{E}}$ refers to the empirical loss. We will do another careful pass through the manuscript to ensure all notation is clearly defined and consistently used. Thank you for bringing this to our attention."}]

Author rebuttal:

Meta-review: The paper addresses the problem of imbalanced multi-class classification. The Authors propose two surrogate loss families: Generalized Logit-Adjusted (GLA) losses and Generalized Class-Aware weighted (GCA) losses. They analyze their Bayes- and 
${H}$-consistency, showing that GLA losses are Bayes-consistent but only ${H}$-consistent for complete hypothesis sets, with bounds scaling as $1/p_{\min}$. In contrast, GCA losses are  ${H}$-consistent for both bounded and complete hypothesis sets, with more favorable bounds scaling as $1/\sqrt{p_{\min}}$.

This is a very good and interesting paper that addresses an important theoretical problem. All Reviewers are positive about the contribution. The main critical remarks concern the readability of the paper, as it is rather dense from a theoretical perspective, and the relation to previous theoretical works on similar topics. The Authors have promised to improve the writing, and they have clarified that the relation to prior work lies in extending it to a new and specific problem, which required the development of new proof techniques.
Decision: Accept (poster)