Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data
Authors: Corinna Cortes
Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: ICML 2025 poster (2025)
Keywords: imbalanced data
consistency
margin bounds
learning theory
Primary area: general_machine_learning->supervised_learning

Abstract: Class imbalance remains a major challenge in machine learning, especially in multi-class problems with long-tailed distributions. Existing methods, such as data resampling, cost-sensitive techniques, and logistic loss modifications, though popular and often effective, lack solid theoretical foundations. As an example, we demonstrate that cost-sensitive methods  are not Bayes-consistent. This paper introduces a novel theoretical framework for analyzing generalization in imbalanced classification. We propose a new class-imbalanced margin loss function for both binary and multi-class settings, prove its strong $H$-consistency, and derive corresponding learning guarantees based on empirical loss and a new notion of class-sensitive Rademacher complexity. Leveraging these theoretical results, we devise novel and general learning algorithms, IMMAX (*Imbalanced Margin Maximization*), which incorporate confidence margins and are applicable to various hypothesis sets. While our focus is theoretical, we also present extensive empirical results demonstrating the effectiveness of our algorithms compared to existing baselines.

Balancing the Scales: Learning from Imbalanced Data
A Theoretical and Algorithmic Framework for
Corinna Cortes
Anqi Mao?
Mehryar Mohri
12 Yutao Zhong'
Abstract
real-world binary classification scenarios, and arguably even more so in multi-class problems with numerous classes. In such cases, a few majority classes often dominate the dataset, leading to a "long-tailed" distribution. Classifiers trained on these imbalanced datasets often struggle on the minority classes, performing similarly naive baseline that simply predicts the majority class.
Class imbalance remains major challenge in machine learning, especially in multi-class prob- lems with long-tailed distributions. Existing meth- ods, such as data resampling, cost-sensitive tech- niques, and logistic loss modifications, though popular and often effective, lack solid theoret- ical foundations. As an example, we demon- strate that cost-sensitive methods are not Bayes- consistent. This paper introduces novel theo- retical framework for analyzing generalization in imbalanced classification. We propose new alass-imbalanced margin loss function for both binary and multi-class settings, prove its strong H-consistency, and derive corresponding learn- ing guarantees based on empirical loss and a new notion of class-sensitive Rademacher complexity. Leveraging these theoretical results, we devise novel and general learning algorithms, IMMAX (Imbalanced Margin Maximization), which incor- porate confidence margins and are applicable to various hypothesis sets. While our focus theo- retical, we also present extensive empirical results demonstrating the effectiveness of our algorithms compared existing baselines.
The problem has been widely studied in the literature (Cardie & Nowe, 1997; Kubat & Matwin, 1997; Chawla et al., 2002; He & Garcia, 2009; Wallace et al., 2011). While a comprehensive review is beyond our scope, we summarize key strategies into broad categories and refer readers to a recent survey by Zhang et al. (2023) for further details. The primary approaches include the following.
Data modification methods. Techniques such over- sampling the minority classes (Chawla et al., 2002), under- sampling the majority classes (Wallace et al., 2011; Kubat & Matwin, 1997), or generating synthetic samples (e.g., SMOTE (Chawla et al., 2002; Qiao & Liu, 2008; Han et al., 2005)), aim rebalance the dataset before training (Chawla et al., 2002; Estabrooks al., 2004; Liu et al., 2008; Zhang & Pfister, 2021).
Cost-sensitive techniques. These assign different penaliza- tion costs to losses for different classes. They include cost- sensitive SVM (Iranmehr et al., 2019; Masnadi-Shiraa & Vasconcelos, 2010) and other cost-sensitive methods (Elkan, 2001; Zhou Liu, 2005; Zhao al., 2018; Zhang et al., 2018; 2019; Sun al., 2007; Fan al., 2017; Jamal et al., 2020). The weights are often determined by the relative number of samples in each class or a notion of effective sample size (Cui et al., 2019).
1. Introduction
The class imbalance problem, defined by significant dis- parity in the number of instances across classes within dataset, is common challenge in machine learning applica- tions (Lewis& & Gale, 1994; Fawcett & Provost, 1996; Kubat & Matwin, 1997; Kang et al., 2021; Menon et al., 2021; Liu et al., 2019; Cui et al., 2019). This issue is prevalent in many
These two approaches are closely related and can be equiv- alent in the limit, with cost-sensitive methods offering a more efficient and principled implementation of data sam- pling. However, both approaches act by effectively modify- ing the underlying distribution and risk overfitting minority classes, discarding majority class information, and inher- ently biasing the training distribution. Very importantly, these techniques may lead to Bayessinnon (proven in Section 6). So while effective in some cases, their perfor- mance depends on the problem, data distribution, predictors.
'Google Research, New York, NY; CCourant Institute of Mathematical Sciences, New York, NY. Correspondence Anqi Mao <aq-
to: Corinna Cortes <corinna wooaaegggooogooooooooooo mao@cims aero@iiiinnu..duu..... Mehryar Mohri <mohri @ gooml,.com>>, Yutao Zhong <yutaozhongeee @ wwwp:/hhoonnggggl..ooooo google.com>.
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning from Imbalanced Data
and evaluation metries (Van Hulse et al., 2007), and they often require extensive hyperparameter tuning. Hybrid ap- proaches aim to combine these two techniques but inherit many of their limitations.
tasks. Moreover, faimess involves broader considerations, and selecting the appropriate criterion requires complex trade-offs.. Evaluation metrics like Fl-score and AUC are also widely used in the context of imbalanced data. How- ever, these metrics can obscure the model's performance on the standard zero-one misclassification tasks, especially in scenarios with extreme imbalances or when the minority class exhibits high variability.
Logistic loss modifications. Several recent methods mod- ity the logistic loss to address class imbalance. Some add hyperparameters to logits, effectively implementing cost- sensitive adjustments to the loss's exponential terms. Ex- amples include the Balanced Softmax loss (Jiawei et al., 2020), Equalization loss (Tan et al., 2020), and LDAM loss (Cao et al., 2019). Other methods, such as logit adjustment (Menon et al., 2021; Khan et al., 2019), use hyperparame- ters for each pair of class labels, with Menon et al. (2021) showing calibration for their approach. Alternative multi- plicative modifications were advocated by Ye et al. (2020), while the Véctor-Scaling loss (Kini et al., 2021) integrates both additive and multiplicative adjustments. The authors analyze this approach for linear predictors, highlighting the specific advantages of multiplicative modifications. These multiplicative adjustments, however, are equivalent to nor- malizing scoring functions or feature vectors in linear cases, a widely used technique, regardless of class imbalance.
Our contributions. This paper presents comprehensive theoretical analysis of generalization for classification loss in the context of imbalanced classes.
In Section 3, we introduce a crass-imbalanced margin loss function and provide a novel theoretical analysis for binary classification. We establish strong HC-consistency bounds and derive learning guarantees based on empirical class- imbalanced margin loss and class-sensitive Rademacher complexity. Section 4 details new learning algorithms, IM- MAX (Imbalanced Margin Maximization), inspired by our theoretical insights. These algorithms generalize margin- based methods by incorporating both positive and negative confidence margins. In the special case where the logistic loss is used, our algorithms can be viewed as a logistic loss modification method. However, they differ from previous approaches, including multiplicative logit modifications, as our parameters are applied multiplicatively to differences of logits, which naturally aligns with the concept of margins.
Other methods. Additional approaches for addressing im- balanced data (see (Zhang et al., 2023)) include post-hoc ad- justments of decision thresholds (Fawcett & Provost, 1996; Collell et al., 2016) or class weights ( (Kang et al., 2020; Kim & Kim, 2020), and techniques like transfer learning, data augmentation, and distillation (Li et al., 2024b).
In Section 5, we extend our results to multi-class classifica- tion, introducing a generalized multi-class class-imbalanced margin loss, proving its K-consistency, and deriving gen- eralization bounds via confidence margin-weighht class- sensitive Rademacher complexity. We also present new IM- MAX algorithms for imbalanced multi-class problems based on these guarantees. In Section 6, we analyze two core methods for addressing imbalanced data. We prove that cost-sensitive methods lack Bayes-con and show that the analysis of Cao et al. (2019) in the separable binary case (for the balanced loss) leads to margin values conflict- ing with our theoretical results (for the misclassification loss). Finally, while the focus of our work is theoretical and algorithmic, Section 7 includes extensive empirical evalua- tions, comparing our methods against several baselines.
Despite the many significant advances, these techniques con- tinue to face persistent challenges. Most existing solutions are heuristic-driven and lack solid theoretical foundation, making their performance unpredictable across diverse con- texts. Among prior work, the most closely related is that of (Cao et al., 2019), which provides an analysis of gener- alization guarantees for the balanced loss, which equalizes the impact of each class by weighting errors inversely to class frequency. Their analysis also applies only to binary classification under the separable case and does not address the target misclassification loss. Jiawei et al. (2020) adopt classical margin theory to derive generalization bounds for multi-class softmax regression, while Wang et al. (2023) establish fine-grained generalization bounds based on data- dependent contraction. Despite these advances, all of these works focus exclusively the balanced loss. In contrast, our work establishes generalization guarantees with respect to the standard zero-one misclassification loss.
2. Preliminaries
Binary classification. Let X represent the input space, and y = (-1,++) the binary label space. Let D be a distri- bution over X x y, and H a hypothesis set of functions mapping from X to IR. Denote by Han the set of all measur- able functions, and by E:Hall X x y + R a loss function. The generalization error of a hypothesis h H and the best-in-class generalization error of H for loss function e are defined as follows: Re(h) B(r.g) [((h, x, B) and
Loss functions and fairness considerations. This work fo- cuses on the standard zero-one misclassification loss, which remains the primary objective in many machine learning applications. While the balanced loss is sometimes advo- cated for fairness, particularly when labels correlate with demographic attributes, such correlations are absent in many
2

---

Learning from Imbalanced Data
(H) hnf (b). The target loss function in binary classification is the zero-one loss function defined for all he e H and (xr X x y by (h, x. 2) == (sign(h(=))==)) where sagn(a) = la - la<o- For a labeled example (r,y) E xXx x y, the margin (2 y) of a predictor h e H is defined by ph. (x, = yh(x).
ours fundamentally distinct.
3.1. Imbalanced (p+, P-)-Mainnn Loss Function
We first extend the p-margin loss function (Mohri et al., 2018) accommodate the imbalanced setting. To account for different confidence margins for instances with label + and label -, we define the class-imbalanced (p+, p-)- margin loss function as follows:
Consisteney, A fundamental property of a surrogate loss fA for target loss function g is its Bayes-consistency (Zhang, 2004; Bartlett et al., 2006; Chen et al., 2004). Specifi- cally, if a sequence of predictors (hn naa c. Han achieves the optimal fa-loss asymptotically, then it also achieves the optimal Ealloss in the limit: lim Re (hw) = Ri, (Hfa)) = lim Re (h.)) = Rig (Hau). While cayes-consistency is a natural and desirable property, it inherently asymptotic and applies only to the family of all measurable functions Hall- A more applicable and in- formative notion is that of H-comsistent bounds, which ac- count for the specific hypothesis class H and provide non- asymptotic guarantees (Awasthi et al., 2022a;b; 202 a;;; 2023a;b; Mao et al., 2023fic:d;e;a;b;
Definition 3.1 (Class-imbalanced margin loss function). Let L ppi + min( 1, max 0, 1 (0,1-)) )) be the p-margin loss func- tion. For any p. > O and p. O, the class-imbalance (pr. (Pr.p-)-men -margin loss is the function Lp..o &Ha XXanxXXXX - TE,
:
defined as follows:
Lp (h, = = (vh(2))) + Pp (vh(z))
The main margin bounds in this section are expressed in terms of this loss function. The parameters p. and p-, both greater than O, represent the confidence margins im- posed by a hypothesis h for positive and negative instances, respectively. The following result provides an equivalent expression for the class-imbalanced margin loss function, see proof in Appendix D.I.
Zheng et al., 2023; Mao et al., 20: Mohri et al., 2024; Cortes et al., 2024; Mao et al., 2025a;b; Mao, 2025; Montreuil et al., 2024; 2;;5d;a;b;e; Zhong, 2025)). In the realizable setting, these bounds are of the form:
Lemma 3.2. The class-imbalanced (p+: p-) -marinn loss function can be equivalently expressed as follows:
Yh e H, Re,, Rig (J() T(RR, (N) Ri, (30),
where I is a non-increasing concave function with r(0)= O. In the general non-realizable setting, each side of the bound is augmented with minimizabily gap Me R2 (3)) [inffeee [E,[(hh,., v) æ]]. which measures the differ- ence between the best-in-class error and the expected best- in-class conditional error. The resulting bound is: Re (h) R2, (H) + Mrg (H)= s I (3ee, (h)- Rú, (H) + Me, (H)). H-consistenny bounds imply Bayes- coyessconnistency when H(= =
Spr.p-(h, x. y) = (tte:(i)))))tteooorx)oooo. (yh(()))
3.2. J6-Consistency
The following result provides a strong consistency guarantee for the innalanmalnnced margin loss introduced in relation to the zero-one loss. We say a hypothesis set is complete when the scoring values spanned by H for each instance cover I: for all x X, (h(z)): h JC = E. Most hypothesis sets widely considered in practice are all complete.
Hall (Mao al., 2024i;d) and provide stronger and more
applicable guarantees.
Theorem 3.3 (Jf-consistency bound for class-imbalances margin loss). Let H be a complete hypothesis set. Then, for all h E H, p. > O, and p- > 0, the following bound holds:
3. Theoretical Analysis of Imbalanced Binary Classification
Reo-1 (h) Rio. (3) Meo- (H)
Our theoretical analysis addresses imbalance by introduc- ing distinct confidence margins for positive and negative points. This allows us to explicitly account for the effects of class imbalance. We begin by defining a general class- imbalanced margin loss function based on these confidence margins. Subsequently, we prove that, unlike previously studied cost-sensitive loss functions in the literature, this new loss function satisfies H--conistenccy bounds. Further- more we establish general margin bounds for imbalanced bi- nary classification in terms of the proposed innsliimbllneee margin loss. While our use of margins bears some resem- blance to the approach of Cao et al. (2019), their analysis is limited to geometric margins in the separable case, making
S RR -- (h) R Ri (H) +MlL.. (H).
The proof is presented in Appendix D.2. Note that our H- consistency bounds in Theorem 3.3 can be extended directly to the uniformly bounded hypothesis sets considered in The- orem 4.1 below. In this case, the bounds would depend the complexity of the hypothesis class, similar to the H-consistency bounds presented in (Awasthi et al., 2022a). The next section presents generalization bounds based on the empirical dlas--mballnced margin loss, along with the sensitive Rademacher complexity and its em- pirical counterpart defined below. Given sample S
3

---

Learning from Imbalanced Data
(Z1y-..;;Tn) we define I, fie (I,...,,), m) y +1] and m. = [+|| as the number of positive instances. Similarly, we define -_ {i the number of negative instances.
can be generalized hold uniformly for all pt (0, 1]
and p- [0. at the cost of modest additional terms
m3 yı = -) and m [4_] as
log loga p= as shown Theorem D.1 in log losk Pt. and
2
Appendix D.4.
Definition 3.4 ((P-.P))cclass class--esssee sensitive Rademacher com- plexity). Let 9 be a family of functions mapping from 2. to [a. b] and 5 (21...., 2m) a fixed sample of size m with elements in 2. Fix P. O and p- > O. Then, the empirical Rademacher complexity of with respect to the sample S is defined as:
4. Algorithm for Binary Classification
In this section, we derive algorithms for binary classification in imbalanced settings, building the theoretical analysis from the previous section.
(p-, (--:P-)-s --l-aaassssssinnne
1 E sup Σ M
o:g(Zi) Σ
0i0(Z)) TT.
Explicit guarantees. Let S S (x:: ||ar| $ ()) denote a sample of size m. Define r, = sup;e/, |xx]| and r- = sup:er. || We assume that the empirical class-sensitive Rademacher complexity Rg..P (H+) can be bounded as:
(9)
gcg
Pt
where o= (o1,..., Om) with d,s independent uniform random variables taking values in {-1,+1}. For any integer class--snnsttive ity of 9 is the expectation of the empirical (px, p- p-)-class- sensitive Rademacher complexity over all samples of size m drawn according to D: Rei iP- (9) 15-11 [9tg (9)]
m 2 1, the (p+.p-) --las--lassssssss sensitive Rademacher complex-
Rg. (H) S
Age
m, p
m_
Ager
m,
m.
p2
where Agr depends on the complexity of the hypothesis set JC. This bound holds for many commonly used hypothesis sets. As an example, for a family of neural networks, Agr can be expressed as a Frobenius norm (Cortes et al., 2017: Neyshabur et al., 2015) or spectral norm complexity with respect to reference weight matrices (Bartlett et al., 2017). More generally, for the analysis that follows, we will as- sume that H can be defined by H (h e H. [4] s Arc). for some appropriate norm I. on some space H. For the class of linear hypotheses with bounded weight vec- tor, JC {I + w- 22: ||w| A], we provide the following explicit guarantee. The proof is presented in Appendix D.6.
3.3. Margin-Baan Based Guarantees
Next, we will prove general margin- based generalization bound, which will serve the foundation for deriving new algorithms for imbalanced binary classification.
Given sample S = Tm)) and a hypothesis h, margin loss is defined m Σi .p (h, y:). Note that the zero-one loss function fo-1 1 is upper-bounded by the class- imbalanced margin loss function Lp Reo.1 (h) S
the empirical elass-imbalancee by RZ- (h) = 1
RLp.. (h).
Theorem 4.1. Let S {a: |a| r be sample of size m and let H = {x + w- x: ||w| A). Let r, suptel_ ||xel and r_ supser ||=]]] Then, the following bound holds for all h
Theorem 3.5 (Margin bound for imbalanced binary classifi- cation). Let H be a set of real-valued functions. Fix > O and p- > O, then, for any 5 > O, with probability at least 1 1-8 8, each of the following holds for all h H(:
log
1
R PgH)) S m
m p
m_r
2
Ar
m4 p
m 2
Rio.1 s To..P (h) -2R0 (H) V
P
m
2m
log
Rio (h) s Fe P- (h) +2R .- (H) +3V
Combining the upper bound of Theorem 4.1 and Theo- rem 3.5 gives directly the following general margin bound:
2m
The proof is presented in Appendix D.3. The generaliza- tion bounds in Theorem 3.5 suggest a trade-off: increas- ing P. and p. reduces the complexity term (second term) but increases the empirical slass-imbalanced margin loss Reg..P (h) (first term) by requiring higher confidence mar- gins from the hypothesis h. Therefore, if the empirical class-imbalanced margin loss of h remains small for rel- atively large values of p+ and p-, h admits particularly favorable guarantee on its generalization error.
log DIl
Reo (0) (R) (h)
2AM m
m.
m_r2
p²
2m
As with Theorem 3.5, this bound can be generalized to hold uniformly for all p. E (0, 1] and p. (0, 1] the cost of ad-
ditional terms log loga and log loga 2 by combining the bound on the class-sensitive Rademacher complexity and Theorem D.1. The bound suggests that small gen- eralization error can be achieved when the second term
For Theorem 3.5, the margin parameters P. and p. must be selected beforehand. But, the bounds of the theorem
Axc
or Axcr.
m.
is small while the p²

---

Learning from Imbalanced Data
empirical class-imbalanced margin loss (first term) remains low.
algorithm which can be used with positive definite kernels, a strict generalization of the logistic regression algorithm when v defines the logistic loss.
Now, consider a margin- based loss function (h, v) L (zh(z)) defined using non-increasing convex function such that $p(u)= V (8) p
Beyond linear models, this algorithm readily extends to neural networks with various regularization terms and other complex hypothesis sets. This makes a general solution for tackling imbalanced binary classification problems.
for all u é R. Examples of such V include: the hinge loss, ((()= max(0, 1 u), the logistic loss, (u)= logz + "), and the exponential loss, (u))= = =
Separable case. When the training sample is separable, we can denote by Preom the geometric margin, that is the smallest distance of a training sample point to the decision boundary measured in the Euclidean distance or another metric appropriate for the feature space. As an example, for linear hypotheses, Pgeom corresponds to the familiar Euclidean distance to the separating hyperplane.
Then, choosing Aor = 1, with probability at least 1 1- 6, the following holds for all h e {h E Hi: and e r0,
[h]] s 1). 1), P+ r0,
yih((;))
(ch((zi)
Re (1)
Σ ic7
y
Σ
m
TeT
P-
The confidence margin parameters pt and p- then be chosen so that /- + p- Pgeomm ensuring that the empirical class-imbalanced margin loss term is zero. Minimizing the right-hand side of the bound then yields the following expressions for pt and p.:
4r
m+
m.
1
+
p
2
+
where the last term includes the log-log terms and the 8- confidence term.
Since for any p > 0, h/p admits the same generalization error as h, with probability at least 1-6 5, the following holds for all he e he H. |M] s p.tpp ). p+ and p.:
2m 2
2m
P+
Proom P- 3
Pgoom
m. r m
m. +
mm
For r- = -T- these expressions simplify to:
Σ V (U.
P
Rio-1 (1) s m Liel
2m
2m
P+
P+
Pgeom
p= 1/ m. m
I Pgeom
(2)
Σ wp (v)h(t))) Vel
(t+ P-
4r
m4
m.
m m
m
p
1
m
Note that the optimal positive margin p. is larger than the negative one p. when there are more positive samples than negative ones (m, > m.). Thus, in the linear case, this suggests selecting a hyperplane with large positive margin in that case, see Figure I for illustration.
Algorithm. Now, since only the first term of the right-hand side depends on h, the bound suggests selecting h, with as solution of:
[1h12 PitP
P: > 0 in the optimization Finally, note that, while a p--p- problem (1) can be freely searched over a range of values in our general (non-separable case) algorithm, can be beneficial to focus the search around the optimal values identified in the separable case.
min 1 Σ (v)h(x;)) Pnte- ) Σ (U)((a)))) 2ste) p
REJC m
sel,
sel-
Introducing a Lagrange multiplier À 2 O and free variable Ps > 0, the optimization problem can be written as Pptp
5. Extension to Multi-Clas Classification
1 m
11(
} (1)
min X 1a11 2 heTf
Σ Liel.
V
Σ
V
In this section, we extend our results to multi-class classifi- cation, with full details provided in Appendix E. Below, we present a concise overview.
where À and a can be selected via cross-validation.
This formulation provides a general algorithm for binary classification in imbalanced settings, called IMMAX (Im- balanced Margin Maximization), supported by strong the- oretical guarantees derived in the previous section. This provides a solution for optimizing the decision boundaries in imbalanced settings based on confidence margins. In the specific case of linear hypotheses (Appendix D.5), choosing T as the Hinge loss yields strict generalization of the SVM
We will adopt the same notation and definitions as previ- ously described, with some slight adjustments. In partic- ular, we denote the multi-class label space by y = [c] e} and a hypothesis set of functions mapping from Xx y to R by H.. For hypothesis h E H. the label h(x) assigned to x E X is the one with the largest score, de- fined as h(x) argmax h(x,y)) using the highest index for tie-brea For a labeled example (Ir y) E X y.
5

---

Learning from Imbalanced Data
the margin Ph (x,,y) of hypothesis h H is given by
with respect the sample S is defined as:
Pa (1r h(x,y) maxy'sy (a,,,//... y²), which is the differ- ence between the score assigned to (ar, y) and that of the next-highest scoring label. We define the multi-clas. class zero- one loss function as 001 := l)())ey- This is the target loss of interest multi-class classification.
1 m
h(2453) W)
(H)
E
sup helf
Σ
Σ FElN
Eiy
(4)
yey
Pk:
where = (Eiy) by with EiyS being independent variables uniformly distributed over (-1,+1}. For any integer m 2 1, the peclass-sensitive Rademacher complexity of H is the expectation of the empirical p-class-sensitive Rademacher complexity over all samples of size m drawn according to D: Re (H) Eg-.m [M))
We define the multi-class class-imbalanced margin loss function as follows:
Definition 5.1 (Multi-class class-imbalanced margin loss). For any p= ]xeccj the multi-class class-imbalanes p- margin loss is the function Lp:H,n X x y IR, defined by:
Margin bound. We establish a general multi-clat margin- based generalization bound in terms of the empirical multi- class class-imballe imbalanced p- p-margin loss and the empirical p- class-sensitive Rademacher complexity (Theorem E.3). The bound takes the following form:
Lp(h,,,,)) Σ pr (x,(
(3)
The main margin bounds in this section expressed in terms of this loss function. The parameters Ps > 0, for k é [c], represent the confidence margins imposed by hy- pothesis for instances labeled k. As in the binary case, we establish an equivalent expression for this class- masslimbbllncedd margin loss function.
Remute (h) s (h) + 24 (H) + 0(1/mm).
This serves as the foundation for deriving new algorithms for imbalanced multi-class classification.
Explicit guarantees. Let o be a feature mapping from X x y to R4. Let S s {(x,)) y): ( s r) denote a sample of size m, for some appropriate norm I on R. Define Th- supiela.ge'/ (I;, y)|l, for any k [c]. As in the binary case, we assume that the empirical class-sensitive Rademacher complexity RG(H) can be bounded as:
Lemma 5.2. The multi-class dlas--imbalanced p-margin loss can be equivalently expressed as follows:
Lo(h,x,y)- Σ pp ( 1-1
The proof is included in Appendix F.I. We also prove that our multi-class class-imbalanced p-margin loss is JC- consistent for any complete hypothesis set H. We say a hypothesis set is complete when the scoring values spanned by HC for each instance cover E: for all (a,y) X y, {h(2, y):h h HQ = IR. This covers all commonly used func- tion classes in practice, such as linear classifiers and neural network architectures.
RG(3()
Ax m Σ
MA
Σ m& R-
P
m
P
where Agr depends on the complexity of the hypothesis set H. This bound holds for many commonly used hy- pothesis sets. For a family of neural networks, Age can be expressed as Frobenius norm (Cortes et al., 2017; Neyshabur et al., 2015) or spectral norm complexity with respect to reference weight matrices (Bartlett et al., 2017). Additionally, Theorems F.3 and F.4 in Appendix F.6 address kernel-based hypotheses. More generally, for the analy- sis that follows, we will assume that H. can be defined by H = {h E H:: [|h] s Aor). for some appropriate norm || on some space H. Combining such an upper bound and Theorem E.3 or Theorem F.2, gives directly the following general margin bound:
Theorem 5.3 (O--Consistency bound for multi-class class-imbalanced margin loss). Let H be complete hy- pothesis set. Then, for all l é H and = [Pk]ke[e] > O, the following bound holds:
R Romata (h)) Rr Eimuti (F) M pmigte (H)
s RL (h) RI, (I() ML, (HO).
The proof is included in Appendix F.2. Our generalization bounds are expressed in terms of the following notions of p-class-sensitive Rademacher complexity.
pmmntt (h) s RR +
4 4/
m& P
o vmm
m
Definition 5.4 (p-class-sensities Rademacher complexity). Let H( be a family of functions mapping from X x y to IR and S = ((z), (((1..1)) ...... (xm. Vm)) a fixed sample of size m with elements in Xx x y. Fix p [p*]ee[a] > O. Then, the empirical p-class-sensitivv Rademacher complexity of H
where the last term includes the log-log terms and the confidence term. Let v be non-increasing convex function such that (n) s V (") non-increasing, for any (a, k), we have: & (p k)) max T (1( k) h h(x,))).
(P) for all u TR. Then, since t is
6

---

Learning from Imbalanced Data
Algorithm. This suggests regularization--aseed algorithm of the following form:
min An12 Ne3C
É
Σ m iel joh
1
E
max / (()))))))))))))) )
(5)
where À and PLS are chosen via cross volidaaali....n.. In partieu- lar, choosing V/ to be the logistic loss and upper-bounding the maximum by a sum yields the following form for our IMMAX (Imbalanced Margin Maximization) algorithm:
1
Figure 1. Solutions in the separable case. Left: Empirical data with negative (blue) and positive (orange) points. The black line is the SVM solution, the red dashed line is Cao et al. (2019)'s solution, and the blue dashed line is ours. Right: Full data distribution showing our solution achieves the lowest generalization error.
}
min X A heFe
2+ m
Σ
log
exp
h ((a,)))((.
k= fe
Algorithms of (Cao et al., 2019). The theoretical anal- ysis of Cao et al. (2019) is limited to the special case of binary classification with linear hypotheses in the separable case, They propose an algorithm based on distinct positive and negative geometric margins, justified by their analysis. (Note that our analysis is grounded in the more general no- tion of confidence margins and applies to both separable and non-separable cases, and general hypothesis sets.)
where X and P&S chosen via cross-validation. Let
=
p= Ei-1 Pk and r Ei mi T 2.2 where as defined previously, rh = suPieda.ge' (x;, for any ke [c]. Us- ing Lemma F.1 (Appendix F.4), the term under the square root in the second term of the generalization bound can be reformulated in terms of the Rényi divergence of order as: Thus, while P&S can be freely searched over a range of values in our general algorithm (6), for experimental efficiency it may be beneficial to focus the search for the vector pp/p]x near
Ei-1 maria Pf p
(rl f),
where
Their analysis contradicts the recommendations of our the- ory. Indeed, it is instructive to compare our margin values in the separable case with those derived from the analysis of Cao et al. (2019), in the special case they consider. The margin values proposed their work are:
When the number of classes e very large, the search space can also be significantly reduced by assigning iden- tical Pk values to underrepresented classes while reserving distinct Pl values for the most frequently occurring classes.
2m 1
2m
P+
Pgeom
p-
Pgeom.
m. m
m + m
Thus, disregarding the suboptimal exponent of 1 to 3. which results from a less precise technical analysis, the margin values recommended in their work directly con- tradict those suggested by our analysis, see Eqn. (2). Specif- ically, their analysis advocates for smaller positive margin when m. m, whereas our theoretical analysis prescribes the opposite. This discrepancy stems from the analysis in (Cao et al., 2019), which focuses the balanced loss, which equalizes the impact of each class by weighting er- rors inversely to class frequency, and deviates fundamentally from the standard zero-one loss we consider. Figure il- lustrates these contrasting solutions in a specific case of separable data. On the standard zero-one loss, our approach obtains lower error.
1 compared
6. Formal Analysis of Some Core Methods
This section analyzes two popular methods presented in the literature for tackling imbalanced data.
Resampling or cost-sensitive loss minimization. A com- mon approach for handling imbalanced data in practice is to assign distinct costs to positive and negative samples. This technique, implemented either explicitly or through resam- pling. is widely used in empirical studies (Chawla et al., 2002; He & Garcia, 2009; He Ma, 2013; Huang et al., 2016; Buda et al., 2018; Cui et al., 2019). The associated target loss Lea.e_ (h, xr y) can be expressed as follows, for any c. > 0, c_ > 0 and (h, y) Hall x X y:
co (h, x, 1--1 c- lo- (h, v, y)1 1y--1-
Although their analysis is restricted to the linearly separa- ble binary case, the authors extend their work to the non- separable multi-class setting by introducing a loss function (LDAM) and algorithm. Their loss function is an instance of the family of logistic loss modifications, with an additive class label-dependent parameter A = C/m their analysis in the separable case, where denotes the label and C' a hyperparameter. In the next section, we will compare our proposed algorithm with this technique as well
The following negative result, see also Appendix C, shows that this loss function does not benefit from a consistency, a motivating factor for our study of the class-imbalanced margin loss, Section 3, with strong consistency guarantees.
1/4 inspired by
Theorem 6.1 (Negative results for resampling and cost-sen- sitive methods). If C. * c,, then Leycc is not Bayes- consistent with respect to fa-1-
7

---

Learning from Imbalanced Data
Table Accuracy of ResNett 34 on long-tailed imbalanced CIFAR-
Table 2. Accuracy of ResNet-34 on CIFAR-I00 100 and Tiny ImageNet; M deviations over five rums for IMMAX and a number of baseline techniques.
CIFAR- 10.
10, CIFAR- 100 and Tiny ImageNet; Means + standard deviations over five runs for IMMAX and number baseline techniques.
Method
Ratio
CIFAR-10
CIFAR-100
Tiny ImageNet
Method
Ratio
CIFAR-10
CIFAR-100
Tiny ImageNet
CE
94.81 # 0.38
78.78 = 0.49
61.72 = 0.68
94.71 = 0.24
77.07 0.55
61.61 = 0.53
RW
92.36 a: 0.11
67.52 a: 0.76
48.16 = 0.72
RW
90.31 = 0.38
72.59 a 0.26
58.49 :: 0.61
BS
93.62 0.25
72.27 +: 0.73
54.18 0.65
BS
90.69 = 0.41
74.18 + 0.62
61.11 0.32
EQUAL
94.21 + 0.21
76,23 0.80
60.63 0.85
EQUAL
93.43 0.23
76.85 0.38
61.81 0.39
LA
200
94.59 + 0.45
78.54 0.49
61.83 = 0.78
LA
200
94.85 0.18
76.89 + 0.74
0.74
61,51 * 0.78
CB
94.95 0.46
79.36 = 0.81
62.51 = 0.71
CB
94.92
7
61,55 = 0.57
FOCAL
79.53 + 0.75
62.70 0.79
FOCAL
94.78
7
61.77 + 0.51
LDAM
95.45 + 0.38
79.18 +: 0.71
63.70 = 0.62
LDAM
94.85 0.23
77.18 0.50
62.54 + 0.51
IMMAX
96.11 + 0.34
80.47 + 0.68
65,20 = 0.65
IMMAX
95.42 = 0.30
78.21 + 0.48
63.57 + 0.36
CE
95.65 0.23
70.05 + 0.36
51.17 = 0.66
CE
95.03 = 0.21
76.92 # 0.27
60.62 = 0.53
RW
93.32 + 0.51
63.35 + 0.26
43.73 # 0.54
RW
90.74
68.17 + 0.82
53.24 + 0.65
BS
94.80 0.26
65.36 + 0.69
47.06 = 0.73
93.24 0.36
70.97 0.35
60.07 0.23
EQUAL
95.15 0.39
68.81 + 0.29
50.34 = 0.78
EQUAL
94.04 0.30
77.17 0.20
60.46 0.64
LA
100
95.75 0.17
70.19 0.78
51.27 = 0.57
LA
100
94.83
77.27 + 0.34
0.34
60.81 + 0.46
CB
95.83 a: 0.11
69.85 0.75
51.58 = 0.65
CB
95.08 + 0.28
76.88 a 0.44
60.63 0.37
FOCAL
95.72 0.11
70.33 0.42
51.66 0.78
FOCAL
95.07 a 0.34
77.00 0.34
60.72 0.36
LDAM
95.85 + 0.10
70.43 0.52
52.00 = 0.53
LDAM
95.17 0.24
77.05 + 0.45
62.33 = 0.46
IMMAX
96.56 + 0.18
71,51 + 0.34
53.47 = 0.72
IMMAX
96.05 = 0.15
78.17 + 0.35
63.04 0.60
CE
93.05 + 0.18
70.43 +: 0.27
53.22 # 0.42
CE
92.95 +: 0.18
74.43 4: 0.38
59.68 &: 0.29
RW
91.45 a: 0.26
67.35 0.51
48.46 = 0.78
RW
90.64 = 0.15
68.65 a 0.49
46.97 a: 0.73
BS
91.84 0.30
66.52 0.39
51.22 = 0.53
92.55 + 0.26
69.55 0.84
56.70 0.34
EQUAL
92.30 0.18
68.64
51.77 = 0.30
EQUAL
92.62 0.24
72.64 * 0.61
60.34 = 0.52
LA
10
92.84 à: 0.43
53.75 # 0.20
LA
10
93.55 + 0.30
74.60 + 0.26
60.36 a: 0.28
CB
92.96 0.27
70.31 +: 0.63
53.66 0.58
CB
93.54 0.15
74.63 a 0.36
59.88 0.29
FOCAL
93.09 0.33
70.70 0.36
0.50
FOCAL
93.11 + 0.16
74.51 0.41 0.41
59.75 0.44
LDAM
93.16 0.25
70.94 + 0.29
53.61 = 0.20
LDAM
93.34 = 0.16
74.82 + 0.46
61.11 # 0.30
IMMAX
93.68 0.12
71.93 = 0.36
54.89 = 0.44
IMMAX
93.93 = 0.18
75.86 0.26
61.93 0.25
as a number of other baselines.
Hutter, 2022) without restarts, with the initial learning rate set to 0.2. For all the baselines and the IMMAX algorithm, the hyperparameters were selected through cross-validation, see Appendix B for details.
7. Experiments
In this section, we present experimental results for our IMMAX algorithm, comparing it to baseline methods in minimizing the standard zero-one misclassification loss on CIFAR-10, CIFAR- (Krizhevsky, 2009) and Tiny Ima- geNet (Le & Yang. 2015) datasets.
To create imbalanced versions of the datasets, we reduced the percent of examples per class identically in the training and test sets. Following (Cao et al., 2019), we consider two types of imbalances: long-tailed imbalance (Cui et al., 2019) and step imbalance (Buda et al., 2018). The imbalance ratio, max me ming. E. m. represents the ratio of sample sizes between the most frequent and least frequent classes. In the long-tailed imbalance setting, class sample sizes decrease exponentially across classes. In the step setting, minority classes all have the same sample size, as do the frequent classes, creating a clear distinction between the two groups
Starting with multi-class classification, we strictly followed the experimental setup of Cao et al. (2019), adopting the same training procedure and neural network architectures. Specifically, we used ResNet-34 with ReLU activations (He et al., 2016), where ResNet-n denotes a residual network with n convolutional layers. For CIFAR- 10 and CIFAR- 100, we applied standard data augmentations, including 4-pixel padding followed by 32* x 32 random crops and random hor- izontal flips. For Tiny ImageNet, we used 8-pixel padding followed by 64 x 64 random crops. All models were trained using Stochastic Gradient Descent (SGD) with Nesterov momentum (Nesterov, 1983), a batch size of 1, 024, and a weight decay of x 10-3, Training spanned 200 epochs, using a cosine decay learning rate schedule (Loshchilov &
We compare our IMMAX algorithm with widely used base- lines, including the cross-entropy (CE) loss, Re- Weighting (RW) method (Xie & Manski, 1989; Morik et al., 1999), Bal- anced Softmax (BS) loss (Jiawei et al., 2020), Equalization loss (Tan et al., 2020), Logit Adjusted (LA) loss (Menon et al., 2022).1,, Class-Balanen (CB) loss (Cui et al., 2019), the FOCAL loss in (Ross& & Dollár, 2017) and the LDAM loss in
8

---

Learning from Imbalanced Data
(Cao al., 2019) also detailed in Appendix B. We average accuracies the imbalanced test over five runs and re- port the means and standard deviations. Note that IMMAX is not optimized for other objectives, such as the balanced loss, and thus is not expected to outperform state-of-the-art methods tailored to those metrics.
Table 3. Accuracy of linear models on binarized version of CIFAR-
10; Means = standard deviations for hinge loss, IMMAX and LDAM.
Method
Airplane
Automobile
Horse
HINGE
90.17 0.09
91.01 0.13
90.58 0.11
LDAM
90.37 0.01
90.44 0.02
90.17 0.01
IMMAX
91.02 0.06
91.26 0.05
91.03 0.03
Table 1 and Table 2 highlight that IMMAX consistently out- performs all baseline methods on both the long-tailed and imbalanaaaeddd datasets across all evaluated imbalance ra- tios (200, 100, and 10). In every scenario, IMMAX achieves an absolute accuracy improvement of at least 0.6% over the runner-up algorithm. Note, that for the long-tailed dis- tributioons, the more imbalanced the dataset is, the more beneficial IMMAX becomes compared to the baselines.
imbalanced data. When the training dataset is balanced, the theoretically optimal values of Pk: coincide across all classes, and IMMAX reduces standard methods. For exam- ple, with the logistic loss, it recovers the standard softmax cross-entropy loss with suitable regularization parameter, thus yielding the same performance.
Finally, in Table 3, we include binary classification results on CIFAR-10 10 obtained by classifying one category, e.g., airplane versus all the others using linear models. Table 3 shows that IMMAX outperforms baselines.
Large-scale datasets. The dependency of our solution on sample size and dimensionality is similar to that of standard neural networks trained with cross-entrppy loss (that is the logistic loss when softmax is applied to logits). Thus, our approach remains practical for large-scale datasets when using optimizers such as SGD (Bottou, 2010), AdaGrad (Duchi et al., 2011) or Adam (Kingma & Ba, 2015). Our solution does depend on the number of classes, but this de- pendency is inherent to standard multi-class neural network solutions as well.
Let us emphasize that our work is based on a novel, princi- pled surrogate loss function designed for imbalanced data. Accordingly, we compare our new loss function directly against existing ones without incorporating additional tech- niques. However, all these loss functions, including ours, can be combined with existing data modification methods such as oversampling (Chawla et al., 2002) and undersam- pling (Wallace et al., 2011; Kubat & Matwin, 1997), as well as optimization strategies like the deferred re-balancing schedule proposed in (Cao et al., 2019), to further enhance performance. For a fair comparison of loss functions, we de- liberately excluded these techniques from our experiments.
Contrastive loss and temperature scaling. The form of our IMMAX loss function has some similarity with super- vised contrastive losses (e.g., Khosla et al. (2020),, where scalar temperature parameter is used in the inner product argument of the exponential. However, in our case, dis- tinct parameters are introduced to allow different confidence margins across classes, serving a different purpose than in contrastive learning. Nevertheless, our margin analysis could provide useful tool for analyzing contrastive learn- ing. Alternatively, the IMMAX loss can be viewed as a form of class -tassdeepnndent temperature scaling derived from the lo- gistic loss. In fact, our theoretical framework offers insight into the role of temperature parameters more broadly.
8. Discussion
Balanced accuracy. Our work focuses on the standard and unmodified zero-one misclassification loss, which remains the primary objective in many machine learning applica- tions, as discussed in Section 1. Accordingly, we report standard accuracy based on this loss function in Section 7. In contrast, some previous studies (e.g., Cao et al. (2019)) report "balanced accuracy", which equalizes the impact of each class by weighting errors inversely to class frequency.
9. Conclusion
We introduced rigorous theoretical framework for address- ing class imbalance, culminating in the class-imbalanced margin loss and IMMAX algorithms for binary and multi- class classification. These algorithms are grounded in strong theoretical guarantees, including K-consistency and robust generalization bounds. Empirical results confirm that our algorithms outperform existing methods while remaining aligned with key theoretical principles. Our analysis is not limited to misclassification loss and can be adapted to other objectives like balanced loss, offering broad applica- bility. We believe these contributions offer a significant step towards principled solutions for class imbalance across a diverse range of machine learning applications.
Selection of Pk- As noted in Section 5, while Pk can be
freely tuned, the search can be guided by the vector [pk/ p] near the optimal values in the separable case, strategy we used in our experiments. For large multi-class settings, we further reduced the search space by assigning shared Pk: to rare classes and distinct ones to frequent classes, improving practicality with minimal performance impact.
Balanced data. IMMAX extends several classical algo- rithms, such SVM (Cortes& & Vapnik, 1995) and logistic regression (Verhulst, 1838), to the more general setting of

---

Learning from Imbalanced Data
Acknowledgements
Cao, K., Wei, C., Gaidon, A., Arechiga, N., and Ma, T. Learning imbalanced datasets with labtl-disti aware margin loss. In Advances in Neural Information Processing Systems, 2019.
We thank the anonymous reviewers for their valuable feed- back and constructive suggestions.
Impact Statement
Cardie, C. and Nowe, N. Improving minority class predic- tion using case-specific feature weights. In International Conference on Machine Learning, pp. 57-65, 1997.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. P. SMOTE: synthetic minority over-sampling tech- nique. Journal of Artificial Intelligence Research, 16: 321-357, 2002.
References
Chen, D.-R., Wu, Q., Ying, Y., and Zhou, D.-X. Support vec- tor machine soft margin classifiers: error analysis. Jour- nal of Machine Learning Research, 5(Sep): 143--1151 2004.
Awasthi, P., Frank, N., Mao, A., Mohri, M., and Zhong, Y. Calibration and consistency of adversarial surrogate losses. In Advances in Neural Information Processing Systems, pp. 9804-9815, 2021a.
Collell, G., Prelec, D., and Patil, K. R. Reviving threshold- moving: a simple plug-in bagging ensemble for binary and multiclass imbalanced data. CoRR, 2016.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.01550, 2021b.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. H- consistency bounds for surrogate loss minimizers. In International Conference Machine Learning, pp. 1117- 1174, 2022a.
Cortes, C. and Vapnik, Support-vector networks. Ma- chine Learning, 20(3):273-295 1995.
Cortes, C., Kuznetsov, V., Mohri, M., and Yang, S. Struc- tured prediction theory based on factor graph complexity. In Advances in Neural Information Processing Systems, 2016.
Awasthi, P.. Mao, A., Mohri, M., and Zhong, Y. Multi-class H H-consistency bounds. In Advances in Neural Informa- tion Processing Systems, pp. 782-795, 2022b.
Cortes, C.,, Gonzalvo, X., Kuznetsov, V., Mohri, M., and Yang. S. AdaNet: Adaptive structural learning of artificial neural networks. In International Conference on Machine Learning, pp. 874-883, 2017.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Theoreti- cally grounded loss functions and algorithms for adversar- ial robustness. In International Conference on Artificial Intelligence and Statistics, pp. 10077-10094, 2023a.
Cortes, C., Mao, A., Mohri, C., Mohri, M., and Zhong, Y. Cardinality-awart set prediction and top-k classification. In Advances in Neural Information Processing Systems, 2024.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. DC- programming for neural network optimizations. Journal of Global Optimization, 2023b.
Cui, J., Zhong, Z., Liu, S., Yu, B., and Jia, J. Paramet- ric contrastive learning. In International Conference on Computer Vision, 2021.
Bartlett, P. I.,, Jordan, M. I., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101 138-1556 2006.
Cui, J., Liu, S., Tian, Z., Zhong, Z., and Jia, J. Reslt: Resid- ual learning for long-tailed recognition. IEEE Transac- tions on Puttern Analysis and Machine Intelligence, 2022.
Bartlett, P. L., Foster, D. and Telgarsky, J. Spectrally- normalized margin bounds for neural networks. In Ad- vances in Neural Information Processing Systems, 2017.
Cui, Y., Jia, M., Lin, T.-Y., Song, Y., and Belongie, S. Class- balanced loss based on effective number of samples. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9268-9277 2019.
Bottou, L. Large-scale machine learning with stochastic gra- dient descent. In Proceedings of COMPSTAT'0010 19th
International Conference Computational Statistics, pp. 177-186, 2010.
Du, C., Han, Y., and Huang, G. Simpro: A simple prob- abilistic framework towards realistic long-tailed semi- supervised learning. In International Conference on Ma- chine Learning, 2024.
Buda, M., Maki, A., and Mazurowski, M. A. A systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, 106:249-2540 2018.
10

---

Learning from Imbalanced Data
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
Hong, Y., Han, S., Choi, K., Seo, S., Kim, B., and Chang, B. Disentangling label distribution for long-tailed visual recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2021.
Elkan, C. The foundations of cost-sensitive learning. In International Joint Conference on Artificial Intelligence, 2001.
Huang, Li, Y., Loy, C. C., and Tang, X. Learning deep representation for imbalanced classification. In Proceed- ings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 5375-5384, 2016.
Estabrooks, A., Jo, T., and Japkowicz, N. A multiple re- sampling method for learning from imbalanced data sets. Computational Intelligence, 20(1) (1 18-36, 2004.
Iranmehr, A., Hasnadi-Shhiaar H., and Vasconcelos, N. Cost-sensitive support vector machines. Nearocomputing. 343:50-64, 2019.
Fan, Y., Lyu, S., Ying, Y., and Hu, B. Learning with average top-k loss. In Advances in Neural Information Processing Systems, pp. 497-505, 2017.
Jamal, M. A., Brown, M., Yang, M.-H., Wang, L.,, and Gong, Rethinking class-balanced methods for long-tailed visual recognition from domain adaptation perspective. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 7610-7619, 2020.
Fawcett, T. and Provost, F. Combining data mining and machine learning for effective user profiling. In Inter- national Conference on Knowledge Discovery and Data Mining, pp. 8-13, 1996.
Jiawei, R., Yu, C., Ma, X., Zhao, H., Yi, S., et Bal- anced meta-softmax for long-tailed visual recognition. In Advances in Neural Information Processing Systems, pp. 4175 4186, 2020.
Gabidolla, M., Zharmagambetov, A., and
Perpiñán, M. Á. Beyond the ROC curve: Classification trees us- ing cost-optimal curves, with application to imbalanced datasets. In International Conference on Machine Learn- ing, 2024.
Kang, B., Xie, S., Rohrbach, M., Yan, Z., Gordo, A., Feng, J., and Kalantidis, Y. Decoupling representation and classifier for long-tailed recognition. In International Conference on Learning Representations, 2020.
Gao, J., Zhao, H., Li, Z., and Guo, Enhancing minor- ity classes by mixing: an adaptative optimal transport approach for long-tailed classification. In Advances in Neural Information Processing Systems, 2023.
Kang, B., Li, Y., Xie, S., Yuan, Z., and Feng. J. Exploring balanced feature spaces for representation learning. In International Conference on Learning Representations, 2021.
Gao, J., Zhao, H., dan Guo, D., and Zha, H. Distribu- tion alignment optimization through neural collapse for long-tailed classification. In International Conference on Machine Learning, 2024.
Kasarla, T., Burghouts, G., Van Spengler, M., Van Der Pol, E., Cucchiara, R., and Mettes, P. Maximum class separa- tion inductive bias in matrix. In Advances in Neu- ral Information Processing Systems, pp. 19553-19566, 2022.
Han, B. Wrapped cauchy distributed angular softmax for long-tailed visual recognition. In International Confer- ence on Machine Learning, pp. 12368-12333 2023.
Khan, S., Hayat, M., Zamir, S. W., Shen, J., and Shao, Striking the right balance with uncertainty. In Proceed- ings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 103-112, 2019.
Han, H., Wang, W.-Y., and Mao, B.-H. Corderline-smoter new over-sampling method in imbalanced data sets learning. In International Conference on Intelligent Com- puting, pp. 878-888 378-887,20 2005.
Khosla, P., Teterwak, P., Wang, C., Samna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Supervised contrastive learning. In Advances in Neural Information Processing Systems, pp. 18661-18677 2020.
He, and Garcia, A. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9):223-1124, 2009.
He, H. and Ma, Y. Imbalanced learning: foundations, algo- rithms, and applications. John Wiley & Sons, 2013.
Kim, and Kim, Adjusting decision boundary for class imbalanced learning. IEEE Access, 8:81674-81685, 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leam- ing for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.

---

Learning from Imbalanced Data
Kini, G. R., Paraskevas, O., Oymak, S., and Thrampoulidis, C. Label-imbalanceel and group-sensitive classification under overparamelerization. In Advances in Neural Infor- mation Processing Systems, pp. 18970-18983, 2021.
Mao, A. Theory and Algorithms for Learning with Mulli- Class Abstention and Multi- Expli-Exxprttte Deferral. PhD thesis, New York University, 2025.
Mao, A., Mohri, C.,, Mohri, M., and Zhong, Y. Two-stage learning to defer with multiple experts. In Advances in Neural Information Processing Systems, 2023a.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, Toronto University, 2009.
Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds: Characterization and extensions. In Advances Neural Information Processing Systems, 2023b.
Kubat, M. and Matwin, S. Addressing the curse of imbal- anced training sets: One-sided selection. In International Conference on Machine Learning, pp. 179-186, 1997.
Mao, A., Mohri, M., and Zhong, Y. H-consisteney bounds for pairwise misranking loss surrogates. International Conference on Machine learning, 2023c.
Le, Y. and Yang, X. Tiny imagenet visual recognition chal- lenge. CS 23/N, 7(7):3, 2015.
Lewis, D. D. and Gale, W. A. A sequential algorithm for training text classifiers. In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, 1994.
Mao, A., Mohri, M., and Zhong, Y. Ranking with abstention. ICML 2023 Workshop The Many Facets of Preference- Based Learning. 2023d.
Mao, A., Mohri, M., and Zhong, Y. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
Li, F., Xu, Q. Bao, S., Yang, Z., Cong, R., Cao, X., and Huang. Q. Size-invariance matters: Rethinking metrics and losses for imbalanced multi-object salient object de- tection. In International Conference on Machine Learn- ing, 2024a.
Mao, A., Mohri, M., and Zhong, Y. Cross-entropy loss functions: Theoretical analysis and applications. In Inter- national Conference on Machine Learning, 2023f.
Li, L., Li, X.C.,, Ye, H.-J., and Zhan, D.-C. Enhanc- ing haas--mbbllanced learning with pre-trained guidance through class-conditional knowledge distillation. In- lernational Conference on Machine Learning, pp. 28204- 28221, 2024b.
Mao, A., Mohri, M., and Zhong, Y. Principled approaches for learning to defer with multiple experts. In Interna- tional Symposium on Artificial Intelligence and Mathe- matics, 2024a.
Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, P. Focal loss for dense object detection. In International Conference on Computer Vision, pp. 2980-2988, 2017.
Mao, A., Mohri, M., and Zhong, Y. Predictor-rejector multi- class abstention: Theoretical analysis and algorithms. International Conference on Algorithmic Learning Theory, 2024b.
Liu, L., Hc. S., Ming. A., Xie, R., and Ma, H. Elta: An enhancer against long-tail for aesthetics-oriented models. In International Conference on Machine Learning, 2024.
Mao, A., Mohri, M., and Zhong, Y. Theoretically grounded loss functions and algorithms for score-based multi-class abstention. In International Conference on Artificial In- telligence and Statistics, 2024c.
Liu, X.-Y., Wu, J., and Zhou, Z.-H. Exploratory undersam- pling for class-imbalance learning. IEEE Transactions on Systems, Man, and Cybernetics, 39(2):539-55) -500, 2008.
Mao, A., Mohri, M., and Zhong, Y. Enhanced H- consistency bounds. In International Conference on Al- gorithmic Learning Theory, 2024d.
Liu, Z., Miao, Z., Zhan, X., Wang. J., Gong, B., and Yu, S. X. Lcrge-scale long-taid tailed recognition in an open world. In Proceedings of the IEFF Conference on Computer Vision and Pattern Recognition, pp. 2537-2546, 2019.
Mao, A., Mohri, M., and Zhong, Y. H-consistency guar- antees for regression. In International Conference on Machine Learning, pp. 34712-34737, 2024e.
Loffredo. E., Pastore, M., Cocco, S., and Monasson, R.
Mao, A., Mohri, M., and Zhong, Y. Multi-label learning with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2024f.
Restoring balance: principled under/oversampling of data for optimal classification. In International Conference Machine Learning, pp. 32643-32670, 2024.
Mao, A., Mohri, M., and Zhong, Y. Realizable H HCconsistent and Bayes-consistent loss functions for learning to defer. Advances in Neural Information Processing Systems, 2024g.
Loshchilov, I. and Hutter, F. SGDR: Stochastic gradient descent with warm restarts. In International Conference on Learning Representations, 2022.
12

---

Learning from Imbalanced Data
Mao, A., Mohri, M., and Zhong, Y. Regression with multi- expert deferral. In International Conference Machine Learning, pp. 34738-34759, 2024h.
Montreuil, Y., Carlier, A., Ng. L. X., and Ooi, W. T. One-stage top-k learning-to-defer: Score-based sur- rogates with theoretical guarantees. arXiv preprint (rXiv:2505.1016: 2025c.
Mao, A., Mohri, M., and Zhong, Y. A universal growth rate for learning with smooth surrogate losses. In Advances in Neural Information Processing Systems, 2024i.
Montreuil, Y., Yeo, S. H., Carlier, A., Ng. L. X., and Ooi, W. T. A two-stage noaring-ttoddefe approach for multi- task learning. In International Conference Machine Learning, 2025d.
Mao, A., Mohri, M., and Zhong, Y. Mastering multiple- expert routing: Realizable H H--onsiitencyy and strong guar- antees for learning to defer. In International Conference on Machine Learning, 2025a.
Morik, K., Brockhausen, P., and Joachims, T. Combining statistical learning with knowledge-based approach-a case study in intensive care monitoring. In International Conference on Machine Learning, pp. 268 277, 1999.
Mao, A., Mohri, M., and Zhong, Y. Principled algorithms for optimizing generalized metrics in binary classifica- tion. In International Conference on Machine Learning, 2025b.
Nesterov, E. A method for solving the convex program- ming problem with convergence rate o(1/k²). Dokl. akad. nauk Ssar, 269:543-547, 1983.
Masnadi-Shirazii H. and Vasconcelos, N. Risk minimization, probability elicitation, and cost-sensitive SVMs. In Inter- national Conference on Machine Learning, pp. 759-766, 2010.
Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. In Conference on learning theory, pp. 1376-1401, 2015.
Qiao, X. and Liu, Y. Adaptive weighted learning for un- balanced multicategory classification. Biometries, 65: 159-68, 2008
Meng, L., Dai, X., Yang, J., Chen, D., Chen, Y., Liu, M., Chen, Y.-L.. Wu, Z., Yuan, L., and Jiang, Y.-G. Learning from rich semanties and coarse locations for long-tailed object detection. In Advances in Neural Information Processing Systems, 2023.
Ross, T.-Y. and Dollár, G. Focal loss for dense object detec- tion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2980-2988, 2017.
Menon, A. K., Jayasumana, S., Rawat, A. S., Jain, H., Veit, A., and Kumar, S. Long-tail tail learning via logit adjustment. In International Conference on Learning Representations, 2021.
Shi, J.-X., Wei, T., Xiang, Y., and Li, Y.-F. How re-sampling helps for long-tail learning? In Advances in Neural Information Processing Systems, 2023.
Mohri, C.,, Andor, D., Choi, E., Collins, M., Mao, A., and Zhong, Y. Learning reject with a fixed predictor: Ap- plication to decontextuulizaatin. In International Confer- ence on Learning Representations, 2024.
Shi, J.-X., Wei, T., Zhou, Z., Shao, J.-J., Han, X.-Y., and Li, Y.-F. Long-tail learning with foundation model: Heavy fine-tuning hurts. In International Conference on Ma- chine Learning, 2024.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning. MIT Press, second edition, 2018.
Suh, M.-K. and Seo, S.-W. Long-tailed recognition by mutual information maximization between latent features and ground-truth labels. In International Conference on Machine Learning, pp. 122770-32782. 2023.
Montreuil, Y., Yeo. S. H., Carlier, A., Ng, L. X., and Ooi, W. T. Optimal query allocation in extractive QA with LLMs: A learning-to-dffer framework with theoretical guarantees. arXiv preprint arXiv:2410. 15761, 2024.
Sun, Y., Kamel, M. S., Wong, A. K., and Wang, Y. Cost- sensitive boosting for classification of imbalanced data. Pattern Recognition, 40(12):3358-33) -37788388888888888 2007.
Montreuil, Y., Carlier, A., Ng, L. X., and Ooi, W. Ad- versarial robustness in two-stage learning-to-defer: Algo- rithms and guarantees. In International Conference Machine Learning, 2025a.
Tan, J., Wang, C., Li, B., Li, Q., Ouyang, W., Yin, C., and Yan, J. Equalization loss for long-tailed object recogni- tion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11662-11671, 2020.
Montreuil, Y., Carlier, A., Ng, L. X., and Ooi, W. T. Why ask one when you can ask k?? two-stage learning-to-deft to the top-k experts. arXiv preprint arXiv:2504.12980 2025b.
Tang, K., Huang, J., and Zhang, H. Long-tailed classifica- tion by keeping the good and removing the bad momen- tum causal effect. In Advances in Neural Information Processing Systems, 2020.
13

---

Learning from Imbalanced Data
Tian, J., Liu, Y-C.,, Glaser, N., Hsu, Y.-C., and Kira, Z. Pos- terior re-calibration for imbalanced datasets, In Advances in Neural Information Processing Systems, 2020.
Yang, Y. and Xu, Z. Rethinking the value of labels for improving class-imbalanced learning- In Advances in Neural Information Processing Systems, 2020.
Van Hulse, J., Khoshgoftaar, T. M., and Napolitano, A. Experimental perspectives on learning from imbalanced data. In International Conference Machine Learning, 2007.
Yang, Y., Chen, S., Li, X., Xie, L., Lin, Z., and Tao, D. Inducing neural collapse in imbalanced learning: Do we really need Iearnable classifier at the end of deep neural network? In Advances in Neural Information Processing Systems, pp. 37991-38002, 2022.
Verhulst, P. F. Notice sur la loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10:113-121, 1838.
Yang, Z.,, Xu, Q Wang. Z., Li, S., Han, B., Bao, S., Cao, X., and Huang, Q. Harnessing hierarchical label distribu- tion variations in test agnostic long-tail recognition. In International Conference on Machine Learning. 2024.
Wallace, B. C., Small, K., Brodley, C. E.E and Trikalinos, T. A. Class imbalance, redux. International Conference on Data Mining, pp. 754-763. 2011.
Ye, H.-J., Chen, H.-Y., Zhan, D.-C., and Chao, W.-L, Iden- tifying and compensating for feature deviation in imbal- anced deep learning. arXiv:2001.01388 2020.
Wang, H., Xia, M. Li, Y., Mao, Y.. Feng, L., Chen, G., and Zhao, J. Solar: Sinkhorn label refinery for imbalanced partial-label learning. In Advances Neural Information Processing Systems, pp- 81 $104-8117 2022.
Zhang, T. Statistical behavior and consistency of classifi- cation methods based on convex risk minimization. The Annals of Statistics, 32(1 5:56-85, 2004.
Wang, J., Lukasiewicz, T.. Hu, X., Cai, J., and Xu, Z. Rsg: A simple but effective module for learning imbalanced datasets. In Proceedings of the IEEE Conference on Com- puter Vision and Puttern Recognition, pp. 3784-3793, 2021a.
Zhang. Y., Zhao, P., Cao, J., Ma, W., Huang, J., Wu, Q.. and Tan, M. Online adaptive asymmetric active learning for budgeted imbalanced data. In SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2768 2768-2777, 2018.
Wang, X., Lian, L., Miao, Z., Liu. Z., and Yu, S. X. Long- tailed recognition by routing diverse distribution-aware experts. In International Conference on Learning Repre- sentations, 2021b.
Zhang, Y., Zhao, P., Niu, S., Wu, Q.. Cao, J., Huang. J., and Tan, M. Online adaptive asymmetric active learning with limited budgets. IEEE Transactions on Knowledge and Data Engineering, 2019.
Wang, Z., Xu, Q., Yang. Z., He, Y., Cao, X., and Huang, Q. A unified generalization analysis of re-weighting and adjustenjutt for imbalanced learning. In Advances in Neural Information Processing Systems, pp. 48417- 48430, 2023.
Zhang, Y., Hooi, B., Hong, L., and Feng, J. Self-super aggregation of diverse experts for test-agnostic long- tailed recognition. In Advances in Neural Information Processing Systems, pp. 34077-34090, 2022.
Wei, T., Mao, Z., Zhou, Z.-H., Wan, Y., and Zhang, M.- L. Learning label shift correction for test- aesttagnostic long- tailed recognition. International Conference on Ma- chine Learning. 2024.
Zhang, Y., Kang, B., Hooi, B., Yan, S., and Feng. J. Deep long-tailed learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(9):10795- 10816, 2023.
Xiang, L.,
Ding, G., and Han, J. Learning from multiple experts: paced knowledge distillation for long-tailed classification. European Conference on Computer Vision, pp. 247-263, 2020.
Zhang, Z. and Pfister, T. Learning fast sample re- re-ieiihting without reward data. In International Conference on Computer Vision 2021.
Xiao, Z., Chen, Z., Liu, S., Wang, H., Feng, Y., Hao, J., Zhou, J. T., Wu, J., Yang. H., and Liu, Z. Fed-grab: Fed- erated long-tailed learning with self-adjusting gradient balancer. In Advances in Neural Information Processing Systems, 2023.
Zhao, P., Zhang, Y., Wu, M., Hoi, S. C., Tan, M., and Huang, Adaptive cost-sensitive online classification. IEEE Transactions Knowledge and Data Engineering, 31(2):214-228 2018.
Zheng, C., Wu, G., Bao, F. Cao, Y., Li, C., and Zhu, J. Revisiting discriminative vs. generative classifiers: The- ory and implications. In International Conference on 2023.
Xie, Y. and Manski, C. F. The logit model and response- based samples. Sociological Methods Research, 17(3): 283-302, 1989.
Machine Learning, pp.
14

---

Learning from Imbalanced Data
Zhong, Y. Fundamental Novel Consistency Theory: H- Consistency Bounds. PhD thesis, New York University, 2025.
Zhong, Z., Cui, J., Liu, S., and Jia, J. Improving calibration for long-tailed recognition. Proceedings of the IEEE Conference Compuler Vision and Puttern Recognition, 2021.
Zhou, B., Cui, Q. Wei, X.-S., and Chen, 7.-M. Bbn: Bilateral-branch network with cumulative learning for long-tailed visual recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1019-9999999 9728, 2020.
Zhou, Z.-H. and Liu, X.-Y. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on Knowledge and Data Engineering, (8(1):63777,2000
Zhu, M., Fan, C., Chen, H., Liu, Y., Mao, W., Xu, X., and Shen, C. Generative active learning for long-tailed instance segmentation. In International Conference Machine Learning, 2024.
15

---

Learning from Imbalanced Data
Contents of Appendix
Related Work
17
Experimental details
18
Proof of Theorem 6.1
20
Binary Classification: Proofs
21
D.1 Proof of Lemma 3.2
21
D.2 Proof of Theorem 3.3
21
D.3 Proof of Theorem 3.5
22
D.4 Uniform Margin Bound for Imbalanced Binary Classification
22
D.5 Linear Hypotheses
23
D.6 Proof of Theorem 4.1
25
Extension to Multi- Classification
25
E.1
Multi-Class Imbalanced Margin Loss
25
E.2 HC-Consistency
26
E.3 Margin-Based Guarantees
26
E,4 General Multi-Class Classification Algorithms
27
Multi-Class Classification: Proofs
27
F.1 Proof of Lemma 5.2
27
F2 Proof of Theorem 5.3
28
F3 Proof of Theorem E.3
28
F4 Analysis of the Second Term in the Generalization Bound
30
F.5 Uniform Margin Bound for Imbalanced Multi-Class Classification
30
F6 Kernel-Based Hypotheses
31
F.7 Proof of Theorem F.3 and Theorem F.4
32
16

---

Learning from Imbalanced Data
A. Related Work
This section provides an expanded discussion of related work on class imbalance in machine learning.
The class imbalance problem, defined by a significant disparity in the number of instances across classes within dataset, is a common challenge in machine learning applications (Lewis & Gale, 1994; Fawcett & Provost, 1996; Kubat & Matwin, 1997; Kang et al., 2021; Menon et al., 2021; Liu et al., 2019; Cui et al., 2019). This issue is prevalent in many real-world binary classification scenarios, and arguably even more so in multi-class problems with numerous classes. In such cases, a few majority classes often dominate the dataset, leading to a "long-tailed" distribution. Classifiers trained on these imbalanced datasets often struggle, performing similarly to a naive baseline that simply predicts the majority class.
The problem has been widely studied in the literature (Cardie & Nowe, 1997; Kubat Matwin, 1997; Chawla et al., 2002; He & Garcia, 2009; Wallace et al., 2011). It includes numerous methods including standard Softmax, class-sensitive learning, Weighted Softmax, weighted 0/1 loss (Gabidolla et al., 2024), iizerinvari metrics for Imbalanced Multi-object Salient Object Detection studied by Li et al. (2024a) as well as Focal loss (Lin et al., 2017), LDAM (Cao et al., 2019), ESQL (Tan et al., 2020), Balanced Softmax (Jiawei et al., 2020), LADE (Hong et al., 2021)), logit adjustment (UNO-IC (Tian et al., 2020), LSC (Wei et al., 2024)), transfer learning (SSP (Yang & Xu, 2020)), data augmentation (RSG (Wang et al., 2021a), BSGAL (Zhu et al., 2024), ELTA (Liu et al., 2024). OT (Gao et al., 2023)), representation learning (OLTR (Liu et al., 2019), PaCo (Cui et al., 2021), DisA (Gao et al., 2024), RichSem (Meng et al., 2023), RBL (Meng et al., 2023), WCDAS (Han, 2023)), classifier design (De-confound (Tang et al., 2020), ( (Yang et al., 2022; Kasarla et al., 2022), LIFT (Shi et al., 2024), SimPro (Du et al., 2024)), decoupled training (Decouple-IB-CRT (Kang et al., 2020), CB-CRT (Kang et al., 2020), SR-CRT (Kang al.. 2020), PB-CRT (Kang et al., 2020), MISLAS (Zhong et al., 2021)), ensemble learning (BBN (Zhou et al., 2020), LFME (Xiang et al., 2020), RIDE (Wang et al., 2021b), ResLT (Cui et al., 2022), SADE (Zhang et al., 2022), DirMixB (Yang et al., 2024)). An interesting recent study characterizes the asymptotic performances of linear classifiers trained on imbalanced datasets for different metrics (Loffredo et al., 2024).
Due to space restrictions, we cannot give a detailed discussion of all these methods. Instead, we will describe and discuss several broad categories of existing methods to tackle this problem and refer to reader to a recent survey of Zhang et al. (2023) for more details. These methods fall into the following broad categories.
Data modification methods. These include methods such as oversampling the minority class (Chawla et al., 2002), undersampling the majority class (Wallace et al., 2011: 1; Kubat & Matwin, 1997), or generating synthetic samples (e.g.. SMOTE (Chawla et al., 2002; Qiao & Liu, 2008; Han et al., 2005)), aim to rebalance the dataset before training (Chawla et al., 2002; Estabrooks et al., 2004; Liu et al., 2008; Zhang & Pfister, 2021; Shi et al., 2023).
Cost-sensitive techniques. These techniques. including cost-sensitive learning and the incorporation of class weights assign different penalization costs to losses on different classes. They include cost-sensitive SVM (Iranmehr al., 2019; Masnadi-Shiran & Vasconcelos, 2010) and other cost-senstive methods (Elkan, 2001; Zhou & Liu, 2005; Zhao et al., 2018; Zhang et al., 2018; 2019; Sun et al., 2007; Fan et al., 2017; Jamal et al., 2020; Zhang et al., 2022; Wang et al., 2022; Xiao et al., 2023; Suh & Sco, 2023). The weights are often determined by the relative number of samples in each class or a notion of effective sample size (Cui et al., 2019).
These two method categories are very related and can actually be shown to be equivalent in the limit. Cost-sensitive methods can be viewed more efficient, flexible and principled techniques for implementing data sampling methods. However, these methods often risk overfitting the minority class discarding valuable information from the majority class. Both methods inherently bias the input training data distribution and suffer from Bayes-inconsissee inconsistenccy (in Section 6, prove that cost-sensitive methods do not admit Bayes-consistency). While they have been both reported to be effective in various instances, this varies and depends on the problem, the distribution, the choice of predictors, and the performance metric adopted and they have been reported not to be effective in all cases (Van Hulse et al., 2007). Additionally, cost-sensitive methods often resort to careful tuning of hyperparameters. Hybrid approaches attempt to combine the strengths of data modification and cost-sensitive methods but often inherit their respective limitations.
Logistic loss modifications. A family of more recent methods rely on logistic loss modifications. They consist of modifying the logistic loss by augmenting each logit (or predicted score) with additive hyperparameter. They can be equivalently described as a cost-sensitive modification of the exponential terms appearing in the definition of the logistic loss. They include the Balanced Softmax loss (Jiawei et al., 2020), the Equalization loss (TTn et al., 2020), and the LDAM loss (Cao et al., 2019). Other similar additive change methods use quadratically many hyperparameters with a distinct additive parameter for each pair of logits. They include the logit adjustment methods of Menon et al. (2021) and Khan et al. (2019). Menon
17

---

Learning from Imbalanced Data
al. (2021) argue that their specific choice of the hyperparameter values is Bayes-consistent. A multiplicative modification of the logits, with one hyperparameter per class label is advocated by Ye et al. (2020). This can be equivalently viewed as normalizing scoring functions (or feature vectors in the linear case) beforchand, which is standard method used in many learning applications, irrespective of the presence of imbalanced classes. The Vector-Scaling loss of Kini et al. (2021) combines the additive modification of the logits with this multiplicative change. These authors further present an analysis of this method in the case of linear predictors, underscoring the specific benefits of the multiplicative changes. As already pointed out, the multiplicative changes coincide with prior rescaling or renormalization of the feature vectors, however.
Other methods. Additional approaches for tackling imbalanced datasets (see Zhang et al. (2023)) include post-hoc correction of decision thresholds (Fawcett & Provost, 1996; Collell et al., 2016) or weights (Kang et al., 2020; Kim & Kim, 2020)]. as well as information and data augmentation via transfer learning, or distillation (Li et al., 2024b).
Despite significant advances, these techniques face persistent challenges.
First, most existing solutions are Ssuristic-driver and lack a solid theoretical foundation, making their performance difficult to predict across varying contexts.
In fact, we are not aware of any analysis of the generalization guarantees for these methods, with the exception of that of (Cao al., 2019; Jiawei et al., 2020; Wang al., 2023). However, as further discussed in Section 6, the analysis presented by these authors is limited to the balanced loss, which equalizes the impact of each class by weighting errors inversely to class frequency. More specifically, the analysis in (Cao et al., 2019) is limited to binary classification and holds only for the separable case. The balanced loss function differs from the target misclassification loss. It has been argued, and that is important, that the balanced loss admits beneficial fairness properties when class labels correlate with demographic attributes as treats all class errors equally. The balanced loss is also the metric considered in the analysis of several of the logistic loss modifications papers (Cao et al., 2019; Menon et al., 2021; Ye et al., 2020; Kini et al., 2021). However, class labels do not alway relate to demographic attributes. Furthermore, many other criteria are considered for fairness purposes and in many machine learning applications, the misclassification remains the key target loss function to minimize. We will show that, even in the special case of the analysis of (Cao et al., 2019), the solution they propose is the opposite of the one corresponding to our theoretical analysis for the standard misclassification loss. We further show that their solution is empirically outperformed by ours.
Second, the evaluation of these methods is frequently biased toward alternative metries such as Fl-measure, AUC, or other metrics weighting false or true positive rate differently, which may obscure their true effectiveness standard misclassification. Additionally, these methods often seem to struggle with extreme imbalances when the minority class exhibits high intra-class variability.
We refer to Zhang et al. (2023) for more details about work related to learning from imbalanced data.
B. Experimental details
In this section, we provide further experimental details. We first discuss the loss functions for the baselines and then provide ranges of hyperparameters tested via volssvaali.
Baseline algorithms. In Section 7, we compared our IMMAX algorithm with well-known baselines, including the cross- entropy (CE) loss, Re- Se-Weighting (RW) method (Xie & Manski, 1989; Morik et al., 1999), Balanced Softmax (BS) loss (Jiawei et al., 2020), Equalization loss (Tan et al., 2020), Logit Adjusted (LA) loss (Menon et al., 2021), (CB) loss (Cui et al., 2019), the FOCAL loss in (Ross & Dollár, 2017) and the LDAM loss in (Cao et al., 2019).
The IMMAX algorithm optimizes the loss function:
(( Py
A Yh,,,; x. y),
LISMAx SlxMax(h,x, (h, = loog Σ
where Pk > 0 for A e [c] are hyperparameters. In comparison, the baselines optimize the following loss functions:
Cross-entropy (CE) loss:
M2x,y)
v(h,,,y), v),
Loe(h, (h,,,,))) v. = -log
Σ5 c
18

---

Learning from Imbalanced Data
Re-Weighting (RW) method (Xie & Manski, 1989; Morik al., 1999): Each sample is re-weighted by the inverse of its class's sample size and subsequently normalized such that the average weight within each mini-batch is 1. This is equivalent to minimizing the loss function given below:
c(r,y))
(h, Lgw (h,
log
Σj eli(x:5)
my
Balanced Softmax (BS) loss (Jiawei et al., 2020):
my mye ch(2,)))
v(,, (,, log
Σ3-1 my ((())())))
Equalization loss (Tan al., 2020):
((ass)
v(,,2,)) 2, v), LEQUAL (h, x. v) = loog
Ej=1 Wyeh(ad)
with the weight wy computed by wj = 1 31 es Luzj where 8 Bernoulli(p) is Bernoulli distribution. Here, 1> p> and > are two hyperparameters.
Logit Adjusted (LA) loss (Menon et al., 2021):
((
v(, (,, log
Σj ch(or logg(m)))
where 7 > is hyperparameter.
Class-Balanced (CB) loss (Cui et al., 2019):
1 1-7
v (h, Len Scn,,,,,))
log
Σj-1 ch(mw))
1 1-
where >> y > 0 is hyperparameter.
FOCAL loss in (Ross Dollár, 2017):
vh,,,yy), (1o,kl(,,,,g) =-(1= Ej=1 ch((,()
h(axy)
c M(z,))
log
Σラ=1 ch((,)))
where 2 is hyperparameter.
LDAM loss in (Cao et al., 2019):
( ch(o.))
v (h, v), (h, = -log ( A, ch(,s)
where A, = for j E [c] and C' > is a hyperparameter.
Discussion. Among these baselines, Rw method, CB loss, and FOCAL loss are cost-sensitive methods, while loss, EQUAL loss, LA loss, and LDAM loss logistic loss modification methods. Note that when 1, the LA loss is the same the BS loss; when = 0, the FOCAL loss is the same as the CE loss. Also note that in the balanced setting where m, m/c for j [c], the RW method, BS loss, I.A loss and CB loss are the same as the CE loss.
Hyperparameter search. As mentioned in Section 7, all hyperparameters were selected through cross-validation for all the baselines and the IMMAX algorithm. More specifically, the parameter ranges for each method are as follows. Note that the CE loss, RW method and BS loss do not have any hyperparameters.
19

---

Learning from Imbalanced Data
and is chosen EQUAL loss: following (Tan et al., 2020), p is chosen from (0.1, 0,,,003,,,0,,,,,,,,,,,,,,,,,,,,, from (0.176, 0.5, 0.8, 1.5, 1.76, 2.0, 3.0, 5.0) x 10-3
0.4,
LA loss: following (Menon et al., 2021), т is chosen from {0.1, (0.3,,.,,,33,00,,,,,, 0,,,,,22...3,,4,,,,,,00.00.77,,, (1.5, 2.0, 2.5, 3.0,3.5, 2.0, 4.0, 4.5, 5.0, 6.0, 6.5, 7.0, 7.5, 8.0, 8.5, 9.0, 9.5, 10.0). When (the suggested value in (Menon et al., 2021)), the LA loss is equivalent to the BS loss. We observed improved performance for small values of 7 < 1 when minimizing the standard zero-one misclassification loss. Therefore, we conducted a finer search between 0 and 1.
and
CB loss: following (Cui et al., 2019), is chosen from {0.1, 0.3, 0.5, 0.6, 0.7, 0.999 0.999, 0.9999). While the default values of (0.9, 0.99, 0.999, 0.9999) are suggested in (Cui et al., 2019), we observed that they are not effective for minimizing the standard zero-one misclassification loss. We found that performance is typically better when y is close to O.
FOCAL loss: 7 is chosen from 11,0, 2.0, 3.0,330,3335, 4.0, 5.0, 5.5, 6.0, 6.5, 7.0, 7.5, 8.5, 10.0) 0.2, and {0.0, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7,0.8, 0.9) following (Ross Dollár, 2017). We observe that performance typically better when y less than Therefore, we conducted finer search between 0 and 1.
LDAM loss: following (Cao et al., 2019), chosen from (10-*, 10-3, 1002, 2, 10 1.0, 10.0, 100.0, 1000.0, 10000.0) and (5x x 10_4, x 10- 55 10-2, ,,5 10-1, 5.0, 50.0, 500.0, 5000.0).
IMMAX loss: following Section and Appendix F.4, each p is searched within symmetric interval centered at the theoretically optimal value Pk
with width ox: that is, over the interval [p] du, Pi + 6x., where 0g is Σx-te]
m
chosen relative to the scale of PE. In particular, we set 6% 0.8pI and evaluate approximately 10 values within each interval. Empirically, performance is not sensitive to variations within this neighborhood. In the step imbalanced setting, we assign identical pk values minority classes and distinct Pk values frequent classes before the search.
C. Proof of Theorem 6.1
Theorem 6.1 (Negative results for resampling and cost-sensitive methods), If c. # c.,, then Lo,.o. is not Bayes-consistent with respect to fy-1-
Proof. Consider a singleton distribution concentrated at a point æ. Without loss of generality, assume that C, > c- > 0. Next, consider the conditional distribution y)xx) Ply +1 X x] denote the conditional probability that +1 given X = with n=x) = 1 e, for e (0, 5)) By the proof of Theorem 3.3, the best-in-class error for the zero-one loss can be expressed
as follows:
inf Re (b) n(x),
which can be achieved by any 1i; such that h2 (2) < O, that is a hypothesis all-negative on x. For the cost-sensitive loss function Ler.e_, the generalization error can be expressed as follows:
Ri... (1)) Incakoo (1- (()))c_n(o))0
Thus, for any e > c. > 0, there exists (0, ( such that the following holds:
2 +
(1-n(x))c < <n(c),, =
2 - c
24 _c_
0<<<
C, c 2
where used the fact that (1 x)/x 1/x 1 is bijection from (0,1) to [0, +o0). For this c, the best-in-class of La is
inf RL., (h) (1-1(x))c, heak
which can be achieved by any all all-positive hi such that hi (x) 2 0. Thus, hi differs from hi which implies that Le.c. not Bayss-con with respect to f--1-
20

---

Learning from Imbalanced Data
D. Binary Classification: Proofs
D.I. Proof Lemma 3.2
Lemma 3.2. The class-imbalanced (p (p-: p-) -margin loss function can be equivalently expressed as follows:
pe (h,, 2,,) = pp (yh(())) 4p (yh(()) Mxx)<O
Proof. When yh(x) $ O, we have p, (z)((r)) = (ph(xx))) 1, so the equality holds. When y/((x) > O, we have y > h(x) > and y <0 = h(z) O, which also implies the equality.
D.2. Proof of Theorem 3.3
Theorem 3.3 (H-connisteney bound for alass-imbalanced margin loss). Let H be complete hypothesis set. Then, for all he H. pt and p- > O, the following bound holds:
Re (h) -Raa. (IC) Me (3() Re R
Ri (3() + ML (H().
(I)
= +1 X x denote the conditional probability that Y +1 given X = x. Without loss of generality, assume (2) [0, }. Then, the conditional error and the best-in-class conditional error of the zero-one loss can be expressed as follows:
Proof. Let (7=) = =
(//0-1(h,221) - (=)) + (1-m(=)) "
inf E[ (h, [²] = min()()),1--<()) - (2))
hetk
Furthermore, the difference between the terms is given by:
1 - 22
h(x) 2 h(æ) < 0
E Lo-1 2,)) inf Ef x,)) xx]
0
For the class-imbalanced margin loss, the conditional error can be expressed as follows:
E[La o (1, xx] '()),, (h(x)) + (1 -1-110 (x))) (-h(=))
0, (0. h(x) )) + - ((((()x)) min 1, ma 0, h(x))
= (1) min 1, max
p_
1 (2)
M(x) 2 p+ P+ > h(x))())))))))))))) 20
(1=)(1-h))) h(x)) (1-n(a))
((0)= (1 (1-n( (1-n(z)) h(x)
-p- < h(x) <0
(x))
M(x) < -p_.
Thus, the best-in-class conditional error can be expressed as follows:
inf E[ P[Lp..... (h, x] min(n(2), (xx)} = 17(2)
heet
Consider the case where l(xx) The difference between the two terms given by:
- (1)))))
h(x) 2 p-
E EL (1, ( [x] heD
inf LL (H,,,, [x]
n)x)) (1 M(x)
P. ) +1 27((x) 111-((xx) p+ > h(xh((())))))))))) 20
y
2 1-2
f0 (h, |x]
inf E lo- (h, v) x). heel y
By taking the expectation of both sides, we obtain:
Rin- (1)) - Ri (H) Men. (HI Rip.o (h) Ri.... (H) + Mr (H)
which completes the proof.
21

---

Learning from Imbalanced Data
D.3. Proof of Theorem 3.5
Theorem 3.5 (Margin bound for imbalanced binary classification). Let H be set of real-valued functions. Fix p. 0 and p- O, then, for any 5 O. with probability at least 1 8, each of the following holds for all h HC:
log
Ri &
s Rg - (h) + 2P (3C) +
2m
log 2
Re (h) R P- (h) 2 (3() + 3
2m
Proof. Consider the family of functions taking values in [0, 1]:
-t= f2 = (x. y) ~ p. (h, x, y): H}.
By (Mohri et al., 2018, Theorem 3.3), with probability at least 1 - 8, for all g H.
1 m gg()) 20 (3t)
log 3 2m
[[g(z}}s m F=
and thus, for all he e H.
log 3 2m
Bl (1,x, s Te (h) + 29 (F) 2m +
Since Rio (h) S Re (1) p (0, we have
log
Re & (h) + 22m (F) +
2m
Since pp is 1 p_ Lipschhit, by (Mohri et al., 2018, Lemma 5.7), Rm (I() can be rewritten as follows:
Rm (H)
1
E
sup
oz p. .a (1,
m
S.0
heM
1
E
sup
o (0gh(r;))1 + &p (1))
m
8,0
[heee
Σ canlarr)
)+
1 1 Σ -o,((as)) p- #c
<
E
sup
m
8.0
hesh
P=
iel.
RR (J)),
where the last equality stems from the fact that the variables and -o; are distributed in the same way. This proves the first inequality. The second inequality, can be derived in the same way by using the second inequality of (Mohri et al., 2018, Theorem 3.3).
D.4. Uniform Margin Bound for Imbalanced Binary Classification
Theorem D.1 (Uniform margin bound for imbalanced binary classification). Let H be set of real-valued functions. Fix T+ > 0 and r_ > 0. Then, for any > O, with probability at least - 6, each of the following holds for all h H, p+ E (0, r+] and p_ e (0.r]):
log logz 2r p. m
log logz 2r p. m
log 1
Rig (h) s SR R...P. (h) + 49R6+.P-(3H) (H))
2m
log log2 2r
log logz p_
2r-
log 2m
Rea. (h) s Re (h) + +DR5 (H()
33V
m
m
22

---

Learning from Imbalanced Data
Proof. First, consider two sequences (p+) k21
and (ex) with ej (0, By Theorem 3.5, for any fixed k 2 1 and p_
P sup Reo (h)) Re (h) > 20 (H) ek Se 2mr
hefe
Choosing E = c
lo then, by the union bound, the following holds for any fixed p- >
Re (h) - Teph - (h) 2 (3()
sup hele k2l
cx >0
2mc
etV
Iogg
c Σ R21
2me2 222ogk
Σ R2l
1/k2
22me 22me?
exp
$
k21
k2l
We can choose p. r 12 For any Pt E (0,r.). there exists à 2 such that p+ E p.-1p= 1, with p. = r+. For that k D+ p4-1 2pt, thus 1/p. 2/p,, and vlog k Vlog Bogllgg(r.//bl Vlog logg (2r./p.) Furthermore, for any h e H and p_ 0, Rs (h) Ri (h). Thus, the following inequality holds for any fixed p_ 0:
log loglog2(22 (2r+
sup Ri-- (n) Rei (h) -2926//2.p ()))) heff Pre(0.r)
0 $ 2e -2me?
m
Next, consider sequences (p=))21 and (#1) with E (0, 1]. By inequality (7), for any fixed / 1,
Rio-1 (h) - -R.. (h) 22 (2000) log loglog,22r-/11
P
sup
6s >
2e 2me
heDr p-E(U.r_]
m
Choosing = + V logi then, by the union bound, the following holds:
Reo1 (h) -Rg. (1)) 12 (H)
log logg (2r
P
sup heft
E2
m
(0.r.)
121
s Σ 2e
2m17 =2 Σ
exp
2m
ctV
lagi
$2
De E
2me2
e
-2log!
1.2211 1/12 121
22me? S 2mm
2me?
121
121
121
We can choose pL r-/2'. For any (0,r-). there exists 1 1 such that p. (p',, pt-] with p" = = For that I P- p-11 2pL_, thus 1/p². s 2/p- and Vlogl Vlog looglogg( /log (org Furthermore, for any h H.
Re-.pt (h) PP (h). Thus, the following inequality holds:
log log, (2r+/p+)
log log, (2r-/p-) 4e 2me?
P sup
Reas (h) - Re..P (h) 49A6 (I()
heff p0.(U.r=] p_e(0.r_]
m
m
where we used the fact that R 000=/2.0-12 = 221 (3(). This proves the first statement. The second statement can be proven in similar way.
D.5. Linear Hypotheses
Combining Theorem 4.1 and Theorem 3.5 gives directly the following general margin bound for linear hypotheses with bounded weighted vectors.
23

---

Learning from Imbalanced Data
Corollary D.2. Let K. { +s ||oo|| A} and assume X s {a= ||]|||||||| sr). Let Letr, suptel, | and supter |aygl
Fix P+ and p- O, then, for any > O, with probability at least 1 5 over the choice of sample S of size m, the following holds for any h H.
log 2
Rto (h) s Re..P. (1))
2A
m,r
P+
2
+
m_
P
31
2m
$ Reps P- (1)
2Ar
M4
m-
31
log
p
p
2m
Choosing 1, by the generalization of Corollary D.2 uniform bound over pt (0,r=] and p. E (0, for any 8 with probability at least
5, the following holds for all h {x w 2: ||w|| s 1}. P. (0,r+) and p- r0,r-]:
Re (h) s = P- (h)
4r
m+
m
loglog 2r
2r loglog2
3
log
(8)
2m
Now, for any p> 0, the p-margin loss function is upper bounded by the p-hinge loss:
Vu E IR, (p(u) = min (1,
max ma. (,,1- ")) S max 0,1- " -)
Thus, with probability at least - 5, the following holds for all h for os w x: ||oo|| s $1}. P. (0,r=) and p. (0,
1 m Lief.
0, vuh(xz))
max 0,1 1 sch(zz))
Reo (h)
Σ
max
P+
P-
(9)
2r, logz
2r_ log logz
log 2m
4 h
m_
m p
+
m
m
Since for any p> 0, h/p admits the same generalization error as h, with probability at least E for x w-s x: |wl p.tp- ). P+ e (0,r+] and p- E (0,r-]:
6, the following holds for all
1
1 Σ max (0, yih(s;)
P+ + P ))+ 0+
max 0, m
P+ f ))]
Rio (h)
Σ
vih(
m Liel.
ief
P_
2r. log log
log log.
2r
log 2m
m.
m_
m
Now, since only the first term of the right-hand hantt-handan side depends on w, the bound suggests selecting w as the solution of the following optimization problem:
min
Σ Liel.
max 0,1 1 ::11-yh(x;)
max 0, max(0.1 ( Σ iel
sh((zs)
( p-
1)}
|
m7
p+
Introducing Lagrange variable À 2 0 and free variable equivalently
0. the optimization problem be written
P.
24 min X w/|l Σ max 0. Vi a
max 0, 34 Σ
24
(10)
m Liet.
SET_
where A and a can be selected via cross-validation. The resulting algorithm can be viewed as an extension of SVMs.
Note that while a can be freely searched over different values, we can search near the optimal values found in the separable
case in (2). Also, the solution can actually be obtained using regular SVM by incorporating the a multipliers into the feature
24

---

Learning from Imbalanced Data
vectors. Furthermore, can replace the hinge loss with general margin-based loss function V: u IR,,, and we add bias term b > O for the linear models if the data is not normalized:
min 8.5
w Al|
2
1/1
+
V Σ TET
2, 6
(11)
m
iel,
1-a
For example, can be chosen as the logistic loss function u ~ log2(1 + e e) or the exponential loss function u ++ eT
D.6. Proof of Theorem 4.1
Theorem 4.1. Let S S {a: ||a]]] < be a sample of size m and let H = fxr me w xs |wll s Aj. Let r. supier, ||x|| and
r- sep zi||. Then, the following bound holds for all h HC:
(3()
A
m.
1
Ar
1
m
m
P
P
p
Proof. The proof follows through series of inequalities:
Rg (H)
E
sup w. = SA
Σ iel,
o
Σ
m
p+
P_
lec
A
1
1
E
Σ
Σ
0,4
Σ
o
+
Σ
m
P+
p-
ieT
m
P+
p-
leT
Σ -
Σ
m
A
m
m_r
Ar
m1
m p2
m
m
m
The first inequality makes use of the Schwaa- inequality and the bound on ||w], the second follows by Jensen's inequality, the third by E[a,a,]= B[o,]E[o,) 0 for i j. the fourth by supiez, | r, and supeer |xa]|| r-, and the last one by | Sr.
E. Extension to Multi-Clane Classification
In this section, we extend the previous analysis and algorithm to multi-class classification. We will adopt the same notation and definitions as previously described, with some slight adjustments. In particular, we denote the multi-class label space by [c] = cc) and a hypothesis set of functions mapping from X y to by H. For a hypothesis e H,, the label h(z) assigned to x is the one with the largest score, defined as h(z) argmax,ey ((x,y). using the highest index for tie-brea For labeled example (x, X y, the margin pa (a v) of hypothesis h e K is given by Ph. (I, h(2, v) max. (xx, which is the difference between the score assigned to (I, () and that of the next- highest scoring label. We define the multi-class zero-one loss function as Armiti In(x)ay- This is the target loss of interest in multi-class classification.
E.1. Multi Class Imbalanced Margin Loss
We first extend the class-imbalanced margin loss function to the multi-class setting. To account for different confidence margins for instances with different lahels, we define the multi-class class-imbalanced margin loss function as follows: Definition E.1 (Multi-class class-imbalanced margin loss). For any p [ot]ke[e]] the multi-class class-imbalen clas--imalanced p-margin loss is the function Lp: Lai X x IR, defined follows:
Lh, = Σ S (p,(
(12)
The main margin bounds this section are expressed in terms of this loss function. The parameters Ps. > O, for k [c], represent the confidence margins imposed by a hypothesis h for instances labeled k. The following result provides an equivalent expression for the class-imbalanced margin loss function. The proof is included in Appendix F.I.
25

---

Learning from Imbalanced Data
Lemma 5.2. The multi-class class-imbalanced p-margin loss can be equivalently expressed as follows:
Lp 1) = Σ (P.
E.2. HC-Consistency
The following result provides strong consistency guarantee for the multi-class class-imbalanced margin loss introduced in relation the multi-class zero-one loss, We say a hypothesis set is complete when the scoring values spanned by H for each instance cover R: for all (2, y) Ixx x y, (h(2, y): h H) = RR
Theorem 5.3 (H--Consiseency bound for multi-class class-imbalann imbalanced margin loss). Let H be complete hypothesis set. Then, for all h e H and p= [pa]ketc] O, the following bound holds:
R Rimalti (h) - Rimont (II) + Mmmur (3C) s ( (h) - RI, (3() + (3).
(4)
0-1
The proof is included in Appendix F.2. The next section presents generalization bounds based on the empirical multi-class class-imbalanced margin loss, along with the p-class-sensitive Rademacher complexity and its empirical counterpart defined below. Given a sample S (EI....,Tmm) for any k [c]. we define I = {i é (1....,m) m. y: k} and m [4 as the number of instances labeled k.
Definition E.2 (p-class-sensitiee Rademacher complexity). Let be a family of functions mapping from X x to RR and S ((#1,91) ...., (Imm ym)) fixed sample of size m with elements in X y. Fix p= [p=]ue[e] 0. Then, the empirical Rademacher complexity of H with respect to the sample S is defined as:
]
h 9) Pk
]
(H)
sup hEDl
Σ LET yely
Σ
Cit
(13)
m
R=
where == (. with CiyS being independent variables uniformly distributed over {-1,+1). For any integer m 1, the p-class-sensilive Rademacher complexity "C's o is the expectation of the empirical p-class-sensitive Rademacher complexity over all samples of size m drawn according D: RR, (JC) Es-DD [3G]
E.3. Margin-Based Guarantees
Next, we will prove general margin-bascd generalization bound, which will serve as the foundation for deriving new algorithms for imbalanced multi-class classification.
Given sample S = (x1,..., ) and hypothesis h. the empirical multi-class class- dass-imbalanced margin loss is defined by (h) = Σ (h,, x4, 24,;:) Note that the multi-class zero-one loss function gmulti is upper bounded by the multi-class class imbalanced margin loss Lp: Remates (h) S (h).
Theorem E.3 (Margin bound for imbalanced multi-class classification). Let H be a set of realevalued functions. Fix Pk: > 0 for k [c], then, for any with probability at least 8, each of the following holds for all e H.:
log
R gmmates (h) S RR + 4v 2C +
2m
log 2
R Amali (h) s (h) 4, 2012 +
2m
The proof is presented in Appendix F.3. As in Theorem D. these bounds can be generalized to hold uniformly for all loglogz for k e [c]. as shown in Theorem F.2 in Appendix F.5.
2
Pk: (0, 1]. at the cost of additional terms m
As for margin bounds in imbalanced binary classification, they show the conflict between two terms: the larger the desired margins p. the smaller the second term, at the price of a larger empirical multi-class class-imbalanced margin loss Rgg Note, however, that here there is additionally a dependency on the number of classes c. This suggests either weak guarantees when learning with large number of classes or the need for even larger margins for which the empirical multi-class dlss-imballaced margin loss would be small.
26

---

Learning from Imbalanced Data
E.4. General Multi-Class Classification Algorithms
Here, we derive IMMAX algorithms for multi-class classification in imbalanced settings, building on the theoretical analysis from the previous section.
Let + be feature mapping from X x y to Re.. Let 5 E {(2, v): (x, v) s denote sample of size m, for some appropriate norm ||- on R. Define Tæ wey (1x,,)) [], for any A E [e]. As in the binary case, we assume that the empirical class-sensitive Rademacher complexity Ri (H) can be bounded as:
RI(
S
Avrve m
mArE P
AocrVe m
Σ k-1
m P
where Asx depends the complexity of the hypothesis set H. This bound holds for many commonly used hypothesis sets. For family of neural networks, Aar can be expressed as a Frobenius norm (Cortes et al., 2017; Neyshabur et al., 2015) or spectral norm complexity with respect to reference weight matrices (Bartlett et al., 2017). Additionally, Theorems F.3 and F.4 in Appendix F.6 address kernel-based hypotheses. More generally, for the analysis that follows, we will assume that H can be defined by HC = {h E Hc: |h| & A9t). for some appropriate norm || on some space H. Combining such an upper bound and Theorem E.3 or Theorem F.2, gives directly the following general margin bound:
4V2Agere m
R smule (h) & (h) 0-1
m& Pk
+
where the last term includes the log-log terms and the 5-confidence term. Let V be a non-increasing convex function such that (u) v (%) for all R. Then, since Φ, is non-increasing, for any k2, we have: (p(p((x,k)) maxjek L (h(z,, k) ()), This suggests a regularizaaiio--asse algorithm of the following form:
min A |1 + heTE
C Σ Σ
max v (((.,))h((x))) jek
(14)
TO Lel
Ph.
where \ and p& are chosen via cross-validation. In particular, choosing V be the logistic loss and upper-bounding the maximum by sum yields the following form for our IMMAX (Imbalanced Margin Maximization) algorithm:
min 1l11 2 1
Σ log ie
Σ exp
Mz -h(x;,
(15)
m
Jowl
where and P&S are chosen via cross-validation. Let p pendix F.4), the expression under the square root in the second term the generalization bound can be reformulated terms of the Rényi divergence of order 3 as: Ei-1
Σi- Pk and r Σi- m 12 Using Lemma F.I (Ap-
merka Pt
2D1(11 :), where
Thus, while p&s can be freely
par
searched over range of values in our general algorithm, it may be beneficial to focus the search for the vector [p]/P] near This strictly generalizes our binary classification results and the analysis of the separable case.
When the number of classes e is very large, the search space can be further reduced by constraining the values for underrepresented classes to be identical and allowing distinct values only for the most frequently occurring classes.
F. Multi-Class Classification: Proofs
F.1. Proof of Lemma 5.2
Lemma 5.2. The multi-class class-imbalanced p-margin loss can be equivalently expressed as follows:
Lp(h, Σ & (P)
Proof. When (x.xx) s 0, we have Φp (2, v)) 1 for any l: E [c]. so the equality holds. When pa (2, y) > O, we have y = = Pa(a, k) > = h(x) k. which also implies the equality.
27

---

Learning from Imbalanced Data
F.2. Proof of Theorem 5.3
Theorem 5.3 (HH-Consisteney bound for multi-class class-imbalanced margin loss). Let H be a complete hypothesis set. Then, for all he H and p [pk]kete O, the following bound holds:
R Rpmqu (h) - Riggu (H) + M pauqua ( s Re, (h) Ri, (3() (3).
(4)
Proof. Letp u)) P(Y y X 2) denote the conditional probability that Y y given X æ. Then, the conditional error and the best-in-class conditional error of the zero-one loss can be expressed as follows:
E| co (h, 2. y)
Σ t/
((yl=))((m)))))) p(h(=))2).
E emuli (h, -, v) | helf
inf
max (yyx((y)x)
Furthermore, the difference between the two terms given by:
mmlti
6-1 (h, x y) x)
inf E emulti (h, x. x] maxp(u/x)) -
hebf
gey
For the multi-class class-imbalanced margin loss, the conditional error can expressed as follows:
(hL y
Σ
ply ( ( (2,()))))
yey
p min 1, max 0. Pa(2.)))
Σ gey
Py
1 -1 11-(((x)) p((h))))))))))))) max (0,
Ph Pn(xx h(x))
Pn(z)
pa pala, h(x))
1 11-p(h(x)(>) min
Ph(w)
Thus, the best-in-class conditional error be expressed follows:
inf E EhLp(h, xr y) [x]= max p() heDC #
wey
The difference between the terms is given by:
inf EI,, |z] maxp(y/l p(h(2)(=) min 1, Ph h(x)) heeh y
ElLo x, y) |x]
y
yey
Ph(at)
Ca (h,
[=]
inf E emetti (h, x., y) |z].
hedi 0-1
By taking the expectation of both sides, we obtain:
R
(h)) R 0-1 oo
(H) M
s RR - -Rt (H)) MM (H)),
0-1
which completes the proof.
F.3. Proof of Theorem E.3
Proof. Consider the family of functions taking values in [0, 1]:
F = {a (z, Lo, y): HC..
By (Mohri et al., 2018, Theorem 3.3), with probability at least 1 5, for all e H.
1 Σ(()) [[g())]
+ - ( 3
log
2m
2-1
28

---

Learning from Imbalanced Data
and thus, for all he H.
log
(1 [)],,,)]] Rg(h)) + 2Rs((() + 3V Since Romati (1)) S (1) - (h, vr w)], we have 8-1
2m
log 2
R Ramquu (h) s (h) (R) +3V
2m
For convenience, define p(t) Ei= Paliel, for i 1, ,,...,m m. Since Dp is Lipsschitz, by (Mohri et al., 2018, Lemma 5.7), (F) can be rewritten as follows:
(H)
1
o.L p (h, 2i..))
sup
m
hESh
1
E
sup
(pn (11::
m
beet
Ph (211 vil
E
sup
p(i)
h(24, ((2))3))= maxx wy. h(x, 80)
E
sup
m
hett
p(i)
1
(2 vi)
}
maxy/ew ey:
m
E
heef
sup
0
p(i)
E
sup he?
p(i)
max,roy, M(x.1/) Then, for any
Now bound the second term above. For any 1, ..... m, consider the mapping V h h, h E H, we have
p())
IM(,,, v/) (xx,1')
M (h) - w2(h')) s max
y/
P(i)
1
Σ
(1((,,))) 11' (x:;,)))
p(i)
Dey
Ve
s
Σ
(1 v) h (xx,
p(i)
yey
Thus, v,
Lipschitz with respect to the 1:112 norm. Thus, by (Cortes et al., 2016, Lemma 5), p())
Le
m sup hE?
maX.'sy. M(IA,3))
Vc
E
sup
Tiv
h(r,,y)
p(1)
p(1)
hEF
yey
V2c
h v)
E
sup
Σ T
Eiy
m
heD(
Rm1
pk:
/ (g))()())
We proceed similarly with the first term to obtain
1 E sup Σ m σ
M(r, vi)
5 SV2cRR((3)
oi
p(i)
heTC
1==1
Thus, RT) can be upper bounded as follows:
Rs(F() R3
This proves the second inequality. The first inequality, can be derived in the same way by using the first inequality (Mohri al., 2018, Theorem 3.3).
29

---

Learning from Imbalanced Data
F.4. Analysis of the Second Term in the Generalization Bound
In this section, we analyze the second term of the generalization bound in terms of the Rényi entropy of order Recall that the Rényi divergence of positive order between two distributions p and with support [c] is defined as:
(p a log Σ -
1-a
with the conventions : and o oo for x > 0. This definition extends to E {0, 10) by taking appropriate limits. In particular, D1 corresponds to the relative entropy (KL divergence).
Lemma F.1. Let p= Ei- Pke and r Ei-
m k.2
Then, the following identity holds:
m
72
(r1
Pk
p
8
where
mi kk
ke[c]
7² Proof. The expression can be rewritten as follows after putting
Σi-1 in factor:
0²
m&
k.2
Pk
my
2
73
3-1
k-1
22
m N
R.2
Pk
exp
2
ka[c]
ke[c]
This completes the proof.
The lemma suggests that for fixed p. choosing [Pk/P]s close to tends to minimize the second term of the generalization bound. Specifically, the separable case where the empirical margin loss is zero, this analysis provides guidance on selecting P&s. The optimal values in this scenario align with those derived in the analysis of the separable binary case.
F.5. Uniform Margin Bound for Imbalanced Multi-Clan Classification
Theorem F2 (Uniform margin bound for imbalanced multi-class classification). Let H. be a set of real-valued functions. Fix Tk > 0 foror & [c]. Then, for any 8 O, with probability least 8, each of the following holds for all H and Pk r0, with is e [c]:
log log, 2nd m
2 log R
Pematti (1) RR 4ee44/2200/ 209ee (H) +
2m
log log
2ra.
log 2011
Rymat (R) 4cv 4e/ (IC)
Σ
31
m
2m
30

---

Learning from Imbalanced Data
F.6. Kernel-Based Hypotheses
For some hypothesis sets, a simpler upper bound can be derived for the p-class-sensitive Rademacher complexity of H, thereby making Theorems E.3 and F.2 more explicit. We will show this for bernel-based hypotheses. Let K:X x X be PDS kernel and let d: + IH be feature mapping associated to K. We consider kernel-basee hypotheses with bounded weight vector: HCp {22 y) w ((2, y): e I I|wll S Ap), where ((x,)) y) (Φ1 (z, v)...... ..... D2 v)) is d-dimensional feature vector. A similar analysis can be extended to hypotheses of the form (x, - wy ((x, y), where | S Ap, based on c weight vectors wi...., Wh E IR.. The empirical p-class- sensstive Rademacher complexity of Hep with p= and = can be bounded as follows.
Theorem F.3. Consider H{ {(z, v) + w (a yiw w Rd, | s A1). Let 1, sup wey wey (| v) loo for any E [c]. Then, the following bound holds for all h H.:
A1v2c 2c
Mar 2 R,
Rg(H))
PI. log(2d).
Theorem FA. Consider H2 = {(x, y) ++ w (xx, y):w Rd 11wl2 s A2)- Let r4.2 = supieh ((x..)))) for any [c]. Then, the following bound holds for all h e H:
RG(H)) $ A2ve
mark22
P
The proofs of Theorems F.3 and F.4 included in Appendix F.7. Combining Theorem E.3 or Theorem F.4 with Theorem E.3 directly gives the following general margin bounds for kernel-basee hypotheses with bounded weighted vectors, respectively.
Corollary F.5. Consider H[ {(xx)) v) + (xx, y) e Rd | s A1). Let Tk supielg wey ( 3) ol for any &E E [c]. Fix Pkc for & [c], then, for any 5 O, with probability least 1 8 over the choice of sample of size m, the following holds for any h K.
8A1c
m P
log 8 2m
Rematt (h) s
SR +
log(2d)
Corollary F.6. Consider H2 = {xx,)) y) w 4 ((x, w) e IRd, 1|l|| A2). Let fk.2 supiel, wey (z,, 1) for any ke [c]. Fix pk 0 for & [c]. then, for any ō 0, with probubility least 1 8 over the choice sample of size m, the following holds for any h H.
4v222c m
mark22
log 8 2m
R smalts (1) (R))
P
As with Theorem E.3, the bounds of these corollaries can be generalized to hold uniformly for all Ps E (0, 1] with l é [c],
log log2 ps. for l [c] by combining Theorem F.3 or Theorem F.4 with Theorem F.2, respectively. Next, describe an algorithm that be derived directly from the theoretical guarantees presented above.
the cost of additional terms V
m
The guarantee of Corollary F.6 and it generalization to uniform bound can be expressed as: for any 6 > O, with probability at least 1 - 8, for all h E HC, {xx, v) w- ((x, w) Idd, |/w $ A2).
max 0, 1. Pro (ro ht)
)
4 A2222c
marZ k.2 P
R Remaits (h) s m 1-l TeTx
Σ Σ
Pk
m
m
where Pw (2, k) = w e k) max (w ((x,,)/)))))))))))) and we used the fact that the p-margin loss function is upper bounded by the p-hinge loss.
31

---

Learning from Imbalanced Data
This suggests regularizatiion-asse algorithm of the following form:
1 m
max 0, Peo Pro }
min weRd
Al [wl
Σ Σ
(16)
R-1 be
Pk
where, as in the binary classification, P&S are chosen via cross-validation.
While p&s can chosen freely, the analysis of [bf[c]
lemma F.1 suggests concentrating the search around
The above can be generalized other multi-class surrogate loss functions. In particular, when using the eross-entropy loss function applied the outputs of neural network, the (multinomial) logistic loss, our algorithm has the following form:
h(a, ()
min A|w|
Σ sel
log 1
Σ 1t
Pk
(17)
where P& chosen via -ross-vvlidation. When the number of classes e is large, restrict search by considering the same Ps for classes with small representation, and distinct P&s for the top classes. Similar algorithms can be devised for other I-,,, upper bounds on w, with E [1, oo). We can also derive group-norm based generalization guarantee and corresponding algorithm.
F.7. Proof of Theorem F.3 and Theorem F.4
Theorem F3. Consider H{, {(z, v) + u ((x, v) E R., [ s A1). Let rk supiel. weyl (1 E [c]. Then, the following bound holds for all h H:
lm for any
AIV2c 2c
m 1,00
RGG))
log (2)).
P
Proof. The proof follows through series of inequalities:
(KG
1
c
1 (Ixzy)
sup W.
Σ
Σ sedR yay
Σ
cig
||xe||l SA1
Nem
Pk
Ai
A E
T
(2
E
Eig
max
Σ Bet
Eiy
m
sede yEM
Pk
m
je[ se
(11,+]
Pk
A1
me
A1 A1
mari.
2c
log(2d)
log(2d).
m
Pk
m
The first inequality makes use of Hölder's inequality and the bound ||l|| and the second one follows from the maximal inequality and the fact that Rademacher variable is Lsub-Gaussian, and suP ( 0k
Theorem F4. Consider Hg {1x, y) ((x, w) TRd 11ll1 s A2)- Let F2.2 suPictawey I [c]. Then, the following bound holds for all h e HC:
(( v) for any
AuVe
mar k.2
Rg(H))
Σ
m
k=1
Pk
32

---

Learning from Imbalanced Data
Proof. The proof follows through series of inequalities:
(3(2)
Σ k= sELe DE!!
Σ
E
sup
W
ciy
PR
277
A2
A2
$ ( v)
Σ Σ
Σ
Ciy
E
Σ
Σ
Cip
m
A-1 s
MEy
Pk
m
k= tele wey
Pk.
A2
A2
m
Aave
m
Pk
dele yey
P
PK
The first inequality makes of the Schwar-Schwarz inequality and the bound ||00||2- the second follows by Jensen's inequality, the third by B[EiySjy] = Elety] B[e O for i # and # y', and the fourth one by suPsele.ye) ( v) 12
T-
33


Reviews:
[{"review_id": "iDmiVSRmfL", "reviewer": "Reviewer_zC71", "summary": "The paper addresses the challenge of class imbalance in machine learning, particularly in multi-class problems with long-tailed distributions. The authors propose a novel theoretical framework for analyzing generalization in imbalanced classification, introducing a class-imbalanced margin loss function for both binary and multi-class settings. They prove the strong H-consistency of this loss function and derive learning guarantees based on empirical loss and a new notion of class-sensitive Rademacher complexity. Leveraging these theoretical results, the authors devise the IMMAX algorithm, which incorporates confidence margins and is applicable to various hypothesis sets. The paper also presents extensive empirical results demonstrating the effectiveness of IMMAX compared to existing baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Weaknesses 1: The experimental results presented in the paper (including the results of the comparison methods) are significantly better than those reported in previous papers. Could the authors provide further explanation for this discrepancy? For example, are there differences in the experimental setup, data preprocessing, or evaluation metrics that could account for the improved performance?**\n\n**Question 1: The results in Table 1 appear to differ significantly from those reported in previous papers ... Could the authors provide an explanation for these differences?**\n\n**Response:** Our work focuses on the standard and unmodified zero-one misclassification loss, which remains the primary objective in many machine learning applications, as discussed in the introduction. Accordingly, we report standard accuracy based on this loss function. In contrast, some previous studies report \"balanced accuracy,\" which averages misclassification errors uniformly across classes (i.e., the balanced loss). This difference in evaluation metrics explains the higher values reported in our results. The balanced accuracy of Balanced Softmax (BS) on CIFAR-10 with a ratio of 100 in our experimental setting is also around 80%. We will provide further elaboration in the final version.\n\nRegarding the experimental setup and data preprocessing, we strictly followed the procedure of Cao et al. (2019), ensuring consistency in all these aspects.\n\n**2. Weaknesses 2: The selection of $\\rho$ appears to be based on the validation set ... Could the authors discuss potential strategies for selecting these parameters in real-world scenarios where validation data may be limited?**\n\n**Response:** We tune the hyperparameters using a validation set held out separately from the training set. Additional details on cross-validation are provided in Appendix B, and further elaboration will be included in the final version. Empirically, performance is not sensitive to variations in the neighborhood of the theoretically optimal values of the $\\rho_k$s indicated below.\n\nAs discussed at the end of Section 5 (Lines 302-309, second column), while the $\\rho_k$ values can be freely searched over a range of values in our general algorithm, the search can be guided by the vector $[\\rho_k / \\sum_{k = 1}^c \\rho_k]_k$ near $\\mathbf{r}$, which corresponds to the theoretically optimal values of $\\rho_k$ in the separable case. We adopted this approach in our experiments. Moreover, in scenarios with a large number of classes, the search space can be significantly reduced by assigning identical $\\rho_k$ values to underrepresented classes, while reserving distinct $\\rho_k$ values for the most frequently occurring classes. This strategy enhances practicality when validation data is limited, with only a minor impact on results.\n\n**3. Question 2: The IMMAX loss function differs significantly in form from Softmax ... If the training dataset were balanced, would IMMAX perform better than the standard softmax cross-entropy loss?**\n\n**Response:** When the training dataset is balanced, the theoretically optimal values of $\\rho_k$ are identical across all classes. In this case, IMMAX becomes equivalent to the standard softmax cross-entropy loss with an appropriate regularization parameter. Therefore, IMMAX would perform similarly to the standard softmax cross-entropy loss in the balanced setting.\n\n**4. Question 3: IMMAX seems more akin to a contrastive loss. Could it be applied in a supervised contrastive learning scenario? If so, how would it compare to existing supervised contrastive learning methods?**\n\n**Response:** The form of our loss function has some similarity with supervised contrastive losses (e.g., [1]), where a scalar temperature parameter is used in the inner product argument of the exponential. However, in our case, distinct parameters are introduced to allow different confidence margins across classes, serving a different purpose than in contrastive learning. Nevertheless, our margin analysis could provide a useful tool for analyzing contrastive learning. We will acknowledge this connection, include a brief discussion, and thank the reviewer for the suggestion.\n\n[1] Khosla et al. Supervised Contrastive Learning. NeurIPS 2020.\n\n**5. Other Comments Or Suggestions: In the paper, the meaning of $\\rho$ appears to be ambiguous, as it is redefined in line 366.**\n\n**Response:** Thank you for pointing this out. We will change the notation here to avoid any overlap with our confidence margin definition of $\\rho$ throughout the paper.", "claims_and_evidence": "The claims made in the paper are generally supported by clear and convincing evidence. The authors provide rigorous theoretical proofs for the H-consistency of their proposed class-imbalanced margin loss function and derive generalization bounds based on class-sensitive Rademacher complexity.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem of class imbalance in machine learning. The authors use standard benchmark datasets and compare their algorithm against several well-known baselines, including cross-entropy loss, Re-Weighting, Balanced Softmax, and LDAM loss.", "theoretical_claims": "I am not particularly familiar with the relevant theories, so I am unable to assess the correctness of the theoretical proofs.", "experimental_designs_or_analyses": "The experimental design is sound and valid. However, I have summarized some questions in the weaknesses and questions sections.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-aligned with the broader scientific literature on class imbalance in machine learning. The authors build on existing work on data resampling, cost-sensitive techniques, and logistic loss modifications, providing a more principled theoretical foundation for these methods.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n- The paper provides a rigorous theoretical framework for addressing class imbalance, which is a significant contribution to the field.\n- The proposed IMMAX algorithm is general and can be applied to various hypothesis sets, making it a versatile solution for imbalanced classification problems.\n- The empirical results are convincing and demonstrate the effectiveness of the proposed method across multiple datasets and imbalance ratios.\n\nWeaknesses:\n- The experimental results presented in the paper (including the results of the comparison methods) are significantly better than those reported in previous papers. Could the authors provide further explanation for this discrepancy? For example, are there differences in the experimental setup, data preprocessing, or evaluation metrics that could account for the improved performance?\n- The selection of $\\rho$ appears to be based on the validation set. However, the paper does not explain how the validation set was constructed. Given that one of the challenges in imbalanced learning is the scarcity of samples in the minority class, it may be difficult to obtain a sufficient number of samples for a reliable validation set. Could the authors clarify how the validation set was constructed and how they ensured its representativeness? Additionally, $\\rho$ do not seem to provide a directly applicable, general parameter prior, which could limit the practical application of the method. Could the authors discuss potential strategies for selecting these parameters in real-world scenarios where validation data may be limited?", "other_comments_or_suggestions": "In the paper, the meaning of  $\\rho$  appears to be ambiguous, as it is redefined in line 366.", "questions_for_authors": "1. The results in Table 1 appear to differ significantly from those reported in previous papers. For example, in the CIFAR-10 dataset with a ratio of 100, the accuracy of Balanced Softmax (BS) is typically around 80, whereas in this paper, it reaches 95. This discrepancy is quite unusual. Similarly, the experimental results on other datasets and settings also seem to be generally higher. Could the authors provide an explanation for these differences?\n2. The IMMAX loss function differs significantly in form from Softmax. In contrast, methods like Balanced Softmax (BS), Logit Adjusted (LA), and LDAM loss revert to the standard softmax cross-entropy loss when the training dataset is balanced. However, IMMAX does not exhibit this behavior. This seems somewhat unreasonable. If the training dataset were balanced, would IMMAX perform better than the standard softmax cross-entropy loss?\n3. IMMAX seems more akin to a contrastive loss. Could it be applied in a supervised contrastive learning scenario? If so, how would it compare to existing supervised contrastive learning methods?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}, {"review_id": "6Q55HvrF5Y", "reviewer": "Reviewer_H6YG", "summary": "This paper introduces a novel theoretical framework for analyzing generalization in imbalanced classification. It proposes a new class-imbalanced margin loss function for both binary and multi-class settings, proves its strong $\\mathcal{H}$-consistency, and derives corresponding learning guarantees based on empirical loss and a new notion of class-sensitive Rademacher complexity. It then devises novel and general learning algorithms, IMMAX (Imbalanced Margin Maximization), which incorporate confidence margins and are applicable to various hypothesis sets. Experiments demonstrate the effectiveness of the proposed method.\n\n## update after rebuttal\nThe authors' rebuttal addresses concerns. I would like to keep my rating and support the acceptance of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Essential References Not Discussed: The paper cites key literature in the field of imbalanced learning, including data modification techniques, cost-sensitive methods, and logistic loss modifications. However, it could benefit from discussing more recent advances in deep learning-based approaches for imbalanced data, such as those involving neural network architectures specifically designed to handle class imbalance.**\n\n**Response:** We aimed to provide a comprehensive overview of related work given the space constraints. We would be happy to expand our discussion to include architecture-based solutions, some of which are already covered in the survey paper we referenced. If the reviewer has specific publications in mind, we would gladly incorporate and discuss them in more detail.\n\n**2. Weaknesses: The performance of IMMAX in large-scale datasets is not clear, which is the key to its application in practical scenarios.**\n\n**Questions: How does the IMMAX algorithm scale with increasing dataset size and dimensionality? Are there any computational limitations that might affect its practicality for very large datasets?**\n\n**Response:** The dependency of our solution on sample size and dimensionality is similar to that of standard neural networks trained with cross-entropy loss (that is the logistic loss when softmax is applied to logits). Thus, our approach remains practical when using optimizers such as SGD, Adam, or AdaGrad. Our solution does depend on the number of classes, but this dependency is inherent to standard multi-class neural network solutions as well.\n\n**3. Other Comments Or Suggestions: It is suggested to add the top and bottom lines in Tables 1, 2, and 3 to make them more intuitive.**\n\n**Response:** Thank you for the suggestion. We’ll add the lines to the tables in the final version.", "claims_and_evidence": "The claims are supported by theoretical analysis and experimental verification.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the studied problem. The IMMAX algorithm incorporates confidence margins and is applicable to various hypothesis sets, and the evaluation metrics are appropriate for assessing the performance of the proposed method.", "theoretical_claims": "The theoretical claims are correctly established. The authors provide detailed proofs and discussions of the theoretical results, demonstrating a solid understanding of the underlying principles.", "experimental_designs_or_analyses": "The experimental designs are sound and demonstrate the effectiveness of the proposed methods.", "relation_to_broader_scientific_literature": "The paper's contributions are well-related to the broader scientific literature on class imbalance in machine learning.", "essential_references_not_discussed": "The paper cites key literature in the field of imbalanced learning, including data modification techniques, cost-sensitive methods, and logistic loss modifications. However, it could benefit from discussing more recent advances in deep learning-based approaches for imbalanced data, such as those involving neural network architectures specifically designed to handle class imbalance.", "other_strengths_and_weaknesses": "### Strengths\n\n- The problem studied in this paper is interesting.\n\n- This paper is well written and in good sharp, which is easy to follow.\n\n- The experimental results are somehow promising.\n\n- The theoretical work and empirical studies of this paper are sufficient, which improves the value of the paper.\n\n  \n\n### Weaknesses\n\n- The performance of IMMAX in large-scale data sets is not clear, which is the key to its application in practical scenarios.", "other_comments_or_suggestions": "It is suggested to add the top and bottom lines in Tables 1, 2, and 3 to make them more intuitive.", "questions_for_authors": "How does the IMMAX algorithm scale with increasing dataset size and dimensionality? Are there any computational limitations that might affect its practicality for very large datasets?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sqnjHInral", "reviewer": "Reviewer_aY6w", "summary": "The first main result is a consistency bound for a class-imbalanced margin loss when the hypothesis set is complete. The second result is a margin-based generalization bound for imbalanced binary classification in terms of Rademacher complexity. The last result is a bound for the Rademacher complexity when the hypothesis set is a class of linear hypotheses with bounded weight vectors. The analysis is also extended to multi-class classification.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Methods And Evaluation Criteria: The methods used for the theoretical study in the paper are based on functional analysis for the related generalization error and 0-1 error and Rademacher analysis. These are appropriate and convincing. If more approximation theory or deep neural network analysis could be used, they would lead to further research activities in dealing with nonlinear or bounded hypotheses.**\n\n**Response:** To clarify, the margin-based generalization bounds we presented also apply to families of neural networks. The reviewer is correct that a deeper analysis from the perspective of approximation theory could further complement our results. However, this is a broader question that extends to other types of learning guarantees as well.\n\n**2. Essential References Not Discussed: Consistent bounds for imbalanced binary classification have been well studied, much earlier than the first reference. One can find such results in the literature of Zhang (Ann. Stat. 2004), Bartlett-Jordan-McAuliffe (JASA 2006), Chen-Wu-Ying-Zhou (JMLR 2004).**\n\n**Response:** Thank you for your suggestion. We will add these references. However, we note that these studies focus on Bayes consistency in standard binary classification, rather than specifically addressing the imbalanced setting.\n\n**3. Other Comments Or Suggestions: It would be better if more general hypothesis sets generated by deep neural networks could be considered. Moreover, the authors might consider consistency bounds for a class-imbalanced margin loss when the hypothesis set is not complete, especially those corresponding to Theorem 4.1, with uniformly bounded hypotheses.**\n\n**Response:** Thank you for the suggestions. Our H-consistency bounds in Theorem 3.3 can indeed be extended to the uniformly bounded hypothesis sets considered in Theorem 4.1. In this case, the bounds would depend on the complexity of the hypothesis class, similar to the H-consistency bounds presented in [1]. We will include this extension in the final version.\n\nWe would be happy to discuss extensions to other neural network families the reviewer might suggest.\n\n[1] Awasthi et al. H-Consistency Bounds for Surrogate Loss Minimizers. ICML 2022.", "claims_and_evidence": "The claims are supported by clear and convincing theoretical results. The results are nice. It is enjoyable to read the paper. \nThe first main result, Theorem 3.3, is given when the hypothesis set is complete. Here the completeness is essential for the bound. The last result, Theorem 4.1, is stated only when the hypothesis set is a class of linear hypotheses with bounded weight vectors. This is rather special, though some hypothesis sets generated by deep neural networks with bounded Frobenius norms or spectral norms are covered. It would be better if more general hypothesis sets generated by deep neural networks could be considered. Moreover, the authors might consider consistency bounds for a class-imbalanced margin loss when the hypothesis set is not complete, especially those corresponding to Theorem 4.1, with uniformly bounded hypotheses.", "methods_and_evaluation_criteria": "The methods used for the theoretical study in the paper are based on functional analysis for the related generalization error and 0-1 error and Rademacher analysis. These are appropriate and convincing. If more approximation theory or deep neural network analysis could be used, they would lead to further research activities in dealing with nonlinear or bounded hypotheses.", "theoretical_claims": "Yes, I check the correctness of the proofs. The proofs are correct but are pretty easy to give, which is suitable for a conference paper.", "experimental_designs_or_analyses": "The experimental designs seem reasonable.", "relation_to_broader_scientific_literature": "The key contributions of the paper are about imbalanced data which appear in many practical applications. They can be useful for theory of fair machine learning, a timely and important topic.", "essential_references_not_discussed": "Consistent bounds for imbalanced binary classification have been well studied, much earlier than the first reference. One can find such results in the literature of Zhang (Ann. Stat. 2004), Bartlett-Jordan-McAuliffe (JASA 2006), Chen-Wu-Ying-Zhou (JMLR 2004).", "other_strengths_and_weaknesses": "none.", "other_comments_or_suggestions": "It would be better if more general hypothesis sets generated by deep neural networks could be considered. Moreover, the authors might consider consistency bounds for a class-imbalanced margin loss when the hypothesis set is not complete, especially those corresponding to Theorem 4.1, with uniformly bounded hypotheses.", "questions_for_authors": "none.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XIwKXyODc6", "reviewer": "Reviewer_Rew5", "summary": "This paper presents a theoretical and algorithmic framework for addressing the class imbalance problem in machine learning, particularly in multi-class settings with long-tailed distributions. The authors introduce a novel class-imbalanced margin loss function for both binary and multi-class classification, proving its strong H-consistency and deriving learning guarantees based on empirical loss and class-sensitive Rademacher complexity. They propose a new algorithm, IMMAX (Imbalanced Margin Maximization), which incorporates confidence margins and is applicable to various hypothesis sets. The paper also provides extensive empirical results demonstrating the effectiveness of IMMAX compared to existing baselines on benchmark datasets like CIFAR-10, CIFAR-100, and Tiny ImageNet.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Please find responses to your specific questions below.\n\n**1. Essential References Not Discussed: The key contribution ... However, [1] has extended Cao's analysis to multiclass scenarios. Moreover, recent advances [2] also provide a fine-grained and tighter generalization guarantee for re-weighting and loss adjustment. I strongly suggest the authors provide some more essential discussion.**\n\n**Weaknesses 1. Insufficient citation of relevant literature: The paper asserts that only one study has analyzed generalization guarantees. However, this overlooks several other significant works [1,2]. In particular, [2] offers insights that align closely with your research and analyzes existing reweighting methods by deriving tighter bounds. It might be beneficial to reference these works and compare their approaches with your findings to enrich the discussion.**\n\n**Response:** Thank you very much for bringing these references to our attention. They are indeed important contributions to the analysis of generalization guarantees in imbalanced learning. Briefly, these works focus on generalization with respect to the balanced loss, whereas our work addresses generalization guarantees with respect to the standard zero-one misclassification loss. We will include a more detailed discussion and comparison in the final version.\n\n**2. Weaknesses 2. Lack of empirical analysis on the hyperparameter: The IMMAX loss function introduces a hyperparameter for each class, which could pose significant tuning challenges, especially in large-scale datasets. The presence of numerous hyperparameters may also lead to unstable outcomes. A thorough empirical analysis is crucial to understand the impact and manageability of these hyperparameters. Conducting tests on a widely recognized dataset like ImageNet, which contains 1000 labels, would be highly beneficial to assess the scalability and robustness of the proposed method.**\n\n**Response:** The number of hyperparameters is indeed an important consideration. As discussed at the end of Section 5, when the number of classes is very large, the search space can be significantly reduced by assigning identical $\\rho_k$ values to underrepresented classes while reserving distinct values for the most frequently occurring ones.\n\nMoreover, while $\\rho_k$ values can be freely searched, the search can be guided by the vector $[\\rho_k / \\sum_{k = 1}^c \\rho_k]_k$ near $\\mathbf{r}$, which corresponds to the theoretically optimal values in the separable case. This approach was also adopted in our experiments.\n\nWe have not observed instability issues in our experiments. However, as suggested by the reviewer, we will include additional experimental results in the final version to further study this point empirically. ImageNet would indeed be an interesting dataset to try.\n\n**3. Questions: Does the proposed IMMAX loss function work like a class-wise temperature scaling technique based on the CE loss? Can I interpret it this way?**\n\n**Response:** Yes, one could interpret it as a class-based temperature scaling derived from the logistic loss. However, our choice is grounded in a theoretical argument that justifies its ability to establish distinct confidence margins across classes, as elaborated in our analysis. In fact, our theoretical framework could provide an insightful interpretation and justification for the familiar temperature parameters.", "claims_and_evidence": "Yes, the claims are supported by a clear presentation and rigorous theoretical explanation.", "methods_and_evaluation_criteria": "Yes, the proposed method make sense, and the evaluation criteria follows the common practice.", "theoretical_claims": "Yes, I have checked the proof, and the theoretical claims are sound and well-justified.", "experimental_designs_or_analyses": "The authors follow a rigorous experimental setup, using standard data augmentations and training procedures. The results are averaged over multiple runs, and standard deviations are reported, ensuring the reliability of the findings. The experiments cover a range of imbalance ratios, demonstrating the effectiveness of IMMAX in different scenarios.", "relation_to_broader_scientific_literature": "The paper is well-situated within the broader literature on class imbalance in machine learning. The authors discuss various existing approaches, including data modification methods, cost-sensitive techniques, and logistic loss modifications. They highlight the limitations of these methods, particularly their lack of theoretical foundations and Bayes inconsistency. The proposed framework addresses these limitations by providing a principled approach to learning from imbalanced data supported by strong theoretical guarantees.", "essential_references_not_discussed": "The key contribution includes presenting a comprehensive theoretical analysis of generalization for classification loss in the context of imbalanced classes. The authors state that \"only (Cao et al., 2019) provides an analysis of generalization guarantees, which is limited to\nthe balanced loss, the uniform average of misclassification errors across classes. Their analysis also applies only to binary classification under the separable case and does not address the target misclassification loss.\". However, [1] has extended Cao's analysis to multiclass scenarios. Moreover, recent advances [2] also provide a fine-grained and tighter generalization guarantee for re-weighting and loss adjustment.  I strongly suggest the authors provide some more essential discussion.\n\n[1] Balanced Meta-Softmax for Long-Tailed Visual Recognition. NeurIPS 2020.\n\n[2] A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment for Imbalanced Learning. NeurIPS 2023.", "other_strengths_and_weaknesses": "Strengths:\n- **Strong Theoretical Foundation**: The authors introduce a novel class-imbalanced margin loss function and provide detailed proofs of its H-consistency. The paper not only proposes a new loss function but also derives generalization bounds based on empirical loss and class-sensitive Rademacher complexity. These theoretical guarantees are crucial for understanding why the proposed method works and under what conditions it can be expected to perform well. \n- **Novelty and Innovation**: The introduction of class-sensitive Rademacher complexity is a novel and innovative contribution. This concept allows the authors to derive generalization bounds that explicitly account for class imbalance, which is a key challenge in imbalanced learning. By incorporating confidence margins into the loss function, the authors address the limitations of existing methods, such as their tendency to overfit minority classes or discard valuable information from majority classes.\n\nWeaknesses:\n- **Insufficient citation of relevant literature**： The paper asserts that only one study has analyzed generalization guarantees. However, this overlooks several other significant works [1,2]. In particular, [2] offers insights that align closely with your research and analyzes existing reweighting methods by deriving tighter bounds. It might be beneficial to reference these works and compare their approaches with your findings to enrich the discussion.\n- **Lack of empirical analysis on the hyperparameter $\\rho_k$**： The IMMAX loss function introduces a hyperparameter for each class, which could pose significant tuning challenges, especially in large-scale datasets. The presence of numerous hyperparameters may also lead to unstable outcomes. A thorough empirical analysis is crucial to understand the impact and manageability of these hyperparameters. Conducting tests on a widely recognized dataset like ImageNet, which contains 1000 labels, would be highly beneficial to assess the scalability and robustness of the proposed method.\n\n[1] Balanced Meta-Softmax for Long-Tailed Visual Recognition. NeurIPS 2020.\n\n[2] A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment for Imbalanced Learning. NeurIPS 2023.", "other_comments_or_suggestions": "I hope the authors can address the aforementioned weaknesses and do not have more comments.", "questions_for_authors": "Does the proposed IMMAX loss function work like a class-wise temperature scaling technique based on the CE loss? Can I interpret it this way?\nFor other questions, please refer to Weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a new theoretical framework for addressing class imbalance in both binary and multi-class classification tasks, filling a critical gap in existing methods that lack rigorous foundations. It proposes a novel class-imbalanced margin loss function with strong H-consistency guarantees and derives principled generalization bounds via a new notion of class-sensitive Rademacher complexity. Building on this foundation, the authors present IMMAX， a family of margin-based learning algorithms that are broadly applicable and outperform many established baselines. Unlike traditional cost-sensitive or resampling methods, this approach is Bayes-consistent and analytically grounded. Extensive empirical results further demonstrate the effectiveness and robustness of the proposed algorithms.

During the rebuttal phase, the authors addressed the raised concerns, resulting in improved reviewer scores from (4, 4, 4, 3) to (4, 4, 4, 4). Therefore, I recommend accepting this paper. Notably, the manuscript would benefit from further revision, especially in elaborating on recent theoretical advances and the role of $\rho$.
Decision: Accept (poster)