A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment for Imbalanced Learning
Authors: Zitai Wang
Qianqian Xu
Zhiyong Yang
Yuan He
Xiaochun Cao
Qingming Huang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Imbalanced Learning
Re-weighting
Logit Adjustment
Genralization Analysis

Abstract: Real-world datasets are typically imbalanced in the sense that only a few classes have numerous samples, while many classes are associated with only a few samples. As a result, a naive ERM learning process will be biased towards the majority classes, making it difficult to generalize to the minority classes. To address this issue, one simple but effective approach is to modify the loss function to emphasize the learning on minority classes, such as re-weighting the losses or adjusting the logits via class-dependent terms. However, existing generalization analysis of such losses is still coarse-grained and fragmented, failing to explain some empirical results. To bridge this gap between theory and practice, we propose a novel technique named data-dependent contraction to capture how these modified losses handle different classes. On top of this technique, a fine-grained generalization bound is established for imbalanced learning, which helps reveal the mystery of re-weighting and logit-adjustment in a unified manner. Furthermore, a principled learning algorithm is developed based on the theoretical insights. Finally, the empirical results on benchmark datasets not only validate the theoretical results but also demonstrate the effectiveness of the proposed method.

A Unified Generalization Analysis of Re- Re-eeighting and Logit-Adjustmen for Imbalanced Learning
Zitai Wang Qianqian Xu Yuan He
Zhiyong Yang"
Xiaochun Cao
Qingming Huang 4,3,7
SKLOIS, Institute of Information Engineering, CAS School of Cyber Security, University of Chinese Academy of Sciences Key Lab. of Intelligent Information Processing, Institute of Computing Tech., CAS School of Computer Science and Tech., University of Chinese Academy of Sciences Alibaba Group
School of Cyber Science and Tech., Shenzhen Campus of Sun Yat-sen University
BDKM, University of Chinese Academy of Sciences
vangzitai@iie.ce www.:liieeea.........ooooooo...e cn heyuan.
xuqianqianßict... ac. cn
yangzhiyong21 Qucass ac en
parpua.hy@alibaa--iiie www.ibbaabannnn...e com
caoxi caoxiaochun@mail. sysu.edu..c. edu.cm
quhuangducas.ee ac.
Abstract
Real-world datasets are typically imbalanced in the sense that only few classes have numerous samples, while many classes are associated with only a few samples. As result, a naive ERM learning process will be biased towards the majority classes, making difficult to generalize to the minority classes. To address this issue, one simple but effective approach is to modify the loss function emphasize the learning on minority classes, such as re- reiweiggting the losses or adjusting the logits via class-dependent terms. However, existing generalization analysis of such losses is still coarse coarse-grained and fragmented, failing to explain some empirical results. To bridge this gap, propose novel technique named data-dependent contraction to capture how these modified losses handle different classes. On top of this technique, fine-grained generalization bound is established for imbalanced learning, which helps reveal the mystery of re-weighting and logit-adjustment in a unified manner. Furthermore, a principled learning algorithm developed based on the theoretical insights. Finally, the empirical results on benchmark datasets not only validate the theoretical results but also demonstrate the effectiveness of the proposed method.
Introduction
In recent years, machine learning has achieved great success with the help of well-collected datasets, where the number of samples is artificially balanced among classes [1, 2]. However, the real-world datasets are generally imbalanced in the sense that only a few classes have numerous samples (i.e.. the majority ones). while the others are associated with only a few samples (i.e., the minority ones) [3-5]. Owing to this issue, naïve Empirical Risk Minimization (ERM) learning process will be biased towards the majority classes, and the generalization on the minority ones becomes challenging. Hence, the imbalanced learning problem has attracted increasing attention in recent years [6-9].
One simple yet effective approach for imbalanced learning is to modify the naïve loss function, such that the learning process can pay more attention to the minority classes (Please refer to Appendix A for more orthogonal approaches). In this direction, existing approaches generally fall into two categories: re-weighting [10, 11] and logit-adjustment [12-16]. The former category assigns larger weights to
"Corresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the losses of the minority classes. Although intuitive, this approach might lead to difficulties and instability in optimization [11, 12, 17]. To tackle this issue, Cao et al. [12] propose an effective scheme named Deferred Re- Re-Weighting (DRW), where the re-weighting approach is applied only during the terminal phase of training. The latter category adjusts the logits by class-dependent terms. For example, the Label Distribution Aware Margin (LDAM) loss enforces larger margins for minority classes to achieve strong regularization [12]. The Logit- segit--ddusteent (LA) loss [13] and the Class-Dependent Temperatures (CDT) loss [14] utilize additive and multiplicative terms to adjust the logits, respectively. Most recently, Kini et al. [16] combine the two types of terms and proposes a unified loss named Vector- Veetor-Scaling (VS) for imbalanced learning.
Although existing modifiiiiiintion methods have achieved promising performance, the theoretical insights are still fragmented and coarse- grainedd.. To be specific, Cao et al. [12] and Ren et al. [18] utilize the classic margin theory to explain the necessity of the additive terms in the LDAM loss. However, the theory fails to explain the significant improvement induced by the DRW scheme. Menon al. [13] analyzes the Fisher consistency property [19] of the additive terms in the LA loss, while providing no further generalization analysis. Kini et al. [16] provides generalization analysis of the VS loss, but the results can only explain the role of the multiplicative terms under the assumption that a linear model is trained on linearly separable data. Besides, we find that the VS loss is rather incompatible with the DRW scheme, which is also out of the scope of existing theory. Hence, a gap still exists between the theory and the practice of the loss- modification approaches.
To bridge this gap, this paper provides a systematical and fine- fine-grained analysis of loss- modification approaches. After revisiting prior arts, we find that the only property of the loss function utilized in existing proofs is the classic Lipschitz continuity [19, 20]. However, this property global in nature such that the whole analysis provides no insight into how the losses handle different classes. Inspired by this observation, we extend the classic Lipschitz continuity with a local technique. In this way, the local Lipschitz constants different classes exactly correspond to the class-dependent terms of the modified loss functions. And a fine-grained generalization bound is established by a novel technique named data-dependent contraction. By applying this bound to the VS loss, the mystery of re- weighting and bogit-adjustment is finally uncovered. Last but not least, a principled learning algorithm is proposed based on our theoretical insights.
To sum up, the main contributions of this paper are listed as follows:
New technique. We extend the classic Lipschitz continuity and propose a novel technique named data-dependent contraction to obtain fine-grained generalization bound for imbalanced learning.
Theoretical insights. Based on the fine-grained bound, a systematical analysis succeeds in explain- ing the role of re-weighting and results that are out of the scope of existing theories.
in a unified manner, as well as some empirical
Principled Algorithm. A principled algorithm is proposed based on the insights, where the re- weighting term is aligned with the generalization bound, and the multiplicative logit-adjustment term is removed during the DRW phase to avoid the incompatibility between terms.
Empirical Validation. The empirical results on multiple benchmark datasets not only validate the theoretical results, but also demonstrate the superiority of the proposed method.
2
Preliminary
We first introduce the basic notations and the imbalanced learning problem in Sec.2.1. Then, we briefly review existing generalization analysis for imbalanced learning in Sec.2.2.
2.1 Notations and Problem Definition
We assume that the samples are drawn i.i.d. from a product space 2 = X' x y, where X' is the input ) be the imbalanced training
space and y = f1..... ..) is the label space. Let S = (T) y (m))) set sampled from the imbalanced distribution D defined on 2, S, {x (x.y) E S) be the set of samples from the class y. N, := |S denote the size of Sy, and n. := NN/N.. Without loss of
generality, we assume that Ni N2 2 2 No.
Let Daai be the balanced distribution defined on 2. Specifically, a class y is first uniformly sampled from y, and then the input is sampled from the class-conditional distribution D,, := IP [z v).
2

---

Then, our task is to learn score function distribution:
f:A' + RC to minimize the risk defined on the balanced
1 C Real Rfal = C y=1
c
E
())(())))).
(I)
2~D,
y=1
where Ry is the risk defined on the class y, and M : :RCC x
Rt is the measure that evaluates the model performance at z E 2. For example, one of the most popular choices is to check whether the top-1 prediction is right: (f(x), y) = [y & arg m f(z)y') where [-] is the indicator
function. Since M generally non-differential and thus hard to optimize, one has to select differential surrogate loss L: R
- Rt, which induces the following surrogate risk:
C
Raal()) = T Rt -
E [L(f()).)).
(2)
y wnyy
= L= /: F} denote the hypothesis set. Next, we consider family of loss functions named Vector-Scaling (VS) [16]:
eBy1(a)) Ey (oyyy
Lvs(f(x),n) = aa log
(3)
The advantage behind this loss family is two-fold. On one hand, the VS loss generalizes popular re- re-weighting and logit-adjustment methods. For example, when ay = 1, = 1, 1,4, = 0, becomes the traditional CE loss [19]. When By = 1, Dy = O, re-weighting terms ay = -y and
ay = (1 pp) - ) E (0,1) 1) recover the classic balanced loss [10] and balsn-Blldcced (CB) loss [11], respectively, ay 1, B, I, A = T log Ty. T > 0 yield the LA loss [13]. When a1 = 1, B, = (N,/N1)2, ",,, = 7, > O, we can deduce the CDT loss [14]. On the other hand, an ideal surrogate loss should be Fisher consistent such that minimizing (f) not only can put more emphasis on minority classes, but also helps bound (sa [19, 21j. Fortunately, prior arts [13]
have shown that a subset of the VS loss family satisfies such property:
8y log[1
ōy ( f(m))
Listerr (f(x), 8)
Σ 4'
(4)
8y
Ty
where 6, is an arbitrary positive constant.
2.2 Existing Generalization Analysis for Imbalanced Learning
In balanced learning, we can directly minimize the empirical balanced risk defined on the balanced datasets Shal sampled from Doat
Rha())= = N
Σ I(((z))
(5)
(m.
Then, the generalization guarantee is available by traditional concentration techniques [19]. However, in imbalanced learning, we can only minimize the empirical risk on the imbalanced dataset S:
1 Σ T.(((x),))
R²(
(SS
To handle this issue, Cao et al. [12] and Ren al. [18] aggregate the wise generalization bound directly with union bound over class-wise results [19]:
Proposition 1 (Union bound for Imbalanced Learning [12]). Given the function set F. and loss function L : BCC x y + M), then for any E (0. 1), with probability at least 1 - 8 over the training set S, the following generalization bound holds for all g E E::
Rhaa() = E
C
R4(0) + (5, 3M -M
log 2C/0
V
2N,
where ())()) is the empirical risk on Syj E5(g) == Ee(sup geg 1 the empirical complexity of the function set G, and & := (g(1), (()) ,.... ,(()) are sampled from independent distributions such as the uniform distribution with (1, -1]: denotes the asymptotic
NV. E g(=)g(2(())] denotes
notation that omits undominated terms, that is, ft) 2 g(t) + 3 constant C > 0, f() S C-g(t).
3

---

To further bound the complexity term Es, (9). Cao et al. [12] assume that the loss function L satisfies the Lipschitz continuity and applies the traditional contraction lemma [20]:
Definition 1 (Lipschitz Continuity). Let denote the 2-norm. Then, say the loss function L(f.v) is Lipschitz continuous with constant μs if for any f. f E F.
[T(fv)) T( v)1 S p. [If())) (x))l-
(8)
Lemma (Contraction Lemma). Assume that the loss function L(f, x) is Lipschitz continuous with constant μ. Then, the following inequality holds:
(s(g) μ Cs(F).
Finally, the standard margin-based generalization bound [22] is directly applied to obtain the upper bound of Cs, (F). However, this union bound has the following limitations:
Theoretically, this generalization bound is coarse-ger grrsseegr and not sharp enough. To be specific, the differences among different loss functions lie in the choice of Oyy By, A,- However, the I Lipschitz continuity, which is the only property of T. utilized in the proof, is global in nature and thus obscures these differences. Although the margin theory can provide some theoretical insights into the role of Ay, the roles of Cty By are still mystery. Besides, since
(R = C Bound
ERJMN
Σ M
Bound (R,g (n))
(10)
a sharper bound might be available if can bound Rea (f) directly.
Empirically, although the induced LDAM loss outperforms the CE loss, the improvement is not so significant. Fortunately, when combining the Deferred Re- Se-Weighting (DRW) technique [12], where ag (1 p)/(1 "))), p& E (0, 1) [1]] during the terminal phase of training, the improvement becomes much more impressive. However, (q. fails to explain this phenomenon.
Recently, Kini et al. [16] provide a generalization analysis for the VS loss. However, the results, which only hold for linear models with linearly separable data, can only explain the roles of 3y For the role of Ay they resort analyzing the gradient of the VS loss and provide coarse-rrained analysis.
To sum up, existing generalization analysis for imbalanced learning is poasse-grained and fragmented. Next, we aim to build a more fine- fine-grained and systematical generalization bound that can unify the roles of both re-weighting and logit-adjustment.
3 Fine-Grained Generalization Analysis for Imbalanced Learning
In Sec.3.1, 1, we first establish a sharp generalization bound based on novel technique named data- dependent contraction. Then, in Scc.3.2, we apply this generalization bound to the VS loss to provide a series of theoretical insights. Finally, in Sec.3.3, a principled algorithm is proposed based on the theoretical insights.
3.1
Generalization Bound Induced By Data-Dependent Contraction
Different from Eq.( we hope to build a direct bound between RL (f) and ( To this end, our analysis is based on the following lemma, whose proof can be found Appendix B:
Lemma 2. Güven the function set F and loss function L RRC x y [0. then for any 6 E (0, 1), with probability at least - 8 over the training set S, the following generalization bound holds for all g E G:
(t) 2 ((L
Cs(9), -c(s)))
(11)
CTG
where (LL,8)== := C
Cne (T + 3M
log 2/6 2N
contains the empirical risk on S and the å term.
2.. ... Nç. Hence, this lemma reveals how the model performance depends the imbalance degree of the data.
Remark 1. Recall that अC == Nc/N, N₁ N

---

As shown in Sec.2.2, the fine-grained analysis is unavailable due to the global nature of the classic Lipschitz continuous property. In view of this, we extend this traditional definition with a local technique [23]:
Definition (Local Lipschitz Continuity). We say the loss function () is local Lipschitz. contin- uous with constants {my]s=1 for any f, f F. y. E D, Sg.
[L - L("", w)1 S Py (I)())) (x))l-
(12)
Then, the following data-dependent contraction inequality helps us obtain sharper bound, whose proof is given in Appendix C.
Assumption 1. Next, we assume that (F(FF O(I/VN). based models with traditional techniques { [19] and neural networks with the latest techniques [24, 25 And the prior arts also adopt this assumption [12].
Note that this result holds for kernel-
Lemma (Data- Deta--eeendeet Contraction). Assume that the loss function L(f. x)) local Lipschitz continuous with constants [Py MMyhy= Then, the following inequality holds under Asm.
Σ 8=1
Ty
(13)
Combining Lem.2 and Lem.3, we have the following theorem:
Theorem (Data- DependDeepnd Bound for Imbalanced Learning). Given the function set F and a loss function L: Rº y' + [0, M. for any ò E (0, 1), with probability at least 1 - ô over the training set S. the following generalization bound holds for all f E F:
Cs(F) C.c
C
Rea (0, +
Σ Pgy
(14)
gml
At the first glance, Eq.(14) seems a little loose since E VTy > 1. In fact, this intuition holds when local Lipschitz continuity degenerates to Def.1. However, when By is decreasing w.r.f Ty- shaper bound might be available. To build an intuitive understanding, proposition, whose proof can be found in Appendix D.
present the following
Proposition Assume that Hy X NT", K > Then, when k. 1, the data-dependent bound presented in Thm.1 1 is sharper than the union bound defined in Prop.
3.2 Application to the VS Loss
Next, we apply Thm.1 to the VS loss to reveal the role of both re- re-weighting and lojit-adjustment. To this end, it is necessary to analyze the local Lipschitz property of the VS loss, whose proof is presented in Appendix E.
Lemma 4. Assume that the score function is bounded. Then, the VS loss local Lipschitz continuous with constants { M where
Py -, [1 sootmax +,BB())+Aa)))
(15)
B, :- 1 (Enrey Bw )xr softmax (-) denotes the softmax function; By( denotes the minimal prediction on the ground-truie truth class y, i.e., By(f) == minxes, f(x)y-
Remark By(f) closely related to the minimal margin defined by margin; = minxes, (f(x)
maxj4y f()))). It is not difficult to check that (f) margin; I maxxeS,,14y f(x),. Hence, as we improve the model performance on class y. the RHS of the above inequality, i.e., the gap between (f) and margin, will decrease, and both the minimal margin and Bf) will increase.
Then, combining Thm. I and Lem.4, we have the following proposition, which reveals how the existing loss-oriented methods improve generalization performance by exploiting the data priors.
5

---

Proposition 3 Data-Dependent Bound for the VS Loss). Given the function set F and the VS loss Lvs. for any (0. 1), with probability at least 1 over the training set S. the following generalization bound holds for all f E F:
(s(F) CTC
(f) 2 (LLss, 6)
softmax (f, + A,)1.
(16)
y=1
From (16() we have the following insights, whose empirical validation can be found in Sec.4.2.
(In1) Why re-weighting and logit-adjustmnnt are necessary? Due to the term the generalization bound is also imbalanced among classes. Both re-weighting and Yogit-adji
and By (f). logit-adjustment can obtain a sharper generalization bound by assigning different weights to the classes with different v My and (f).). In this process, Cty mainly rebalances the generalization performance among classes, Le., VTy. while By and A, focus adjusting the imbalance of the terms (J) among classes.
(In2) Why the deferred scheme is necessary? As pointed out in [11, 17], weighting up the minority classes will cause difficulties and instability in optimization, especially when the distribution is extremely imbalanced. To fix this issue, Cao et al. [12] develops a deferred scheme, where ag = 1 and (1 p) -, E (0, 1) during the initial and terminal phase of training, respectively. Although this scheme shows significant improvement, there is still lack of theoretical explanation.
Fortunately, Prop.3 can give us some inspiration. Specifically, although a weighted loss can boost the optimization on the minority classes, it is harmful to the further improvement on the majority classes, as shown in Fig.3. Hence, the majority/minority classes will have relatively small/large (f) respectively, and the generalization bound becomes even looser. By contrast, in the DRW scheme, we have ay = during the initial phase of training. Such a warm-up phase will encourage the model to focus on the majority classes and induce a small (J) for both majority and minority classes after weighting up the minority classes. On top of this, the generalization bound can become sharper, which explains the effectiveness of the deferred scheme.
(In3) How does our result explain the design of existing losses? On one hand, for re-weighting losses, ag should decrease as Ty increases, which is consistent with the balanced loss with ay = " (1-p))(L1 (1- p (0, 1) [11]. On the other hand, from the insight (In2), we know that when a2 = 1, (f) will be increasing w.t.t Ty. Hence, for logit- adjustment losses, both B, and A, should increase as Ty increases. This insight is consistent with the LDAM loss (Ay OC -Ny 1/t) [12]. the logit-adjusted loss (A, = T log Fy)) [13], and the CDT loss (B, = (N₂/N1)7) [14].
[10] and 0g
(In4) Are re-weigting and logit-adjustment fully compatible? (a) Unfortunately, the answer is negative. To be specific, the re- re-weighting term ay is decreasing w.r.t Ty. whereas the multiplicative logit-adjustment term By is increasing w.r.f. π.. As a result, 3, will weaken the effect of at. (b) Fortunately, ay is compatible with the additive logit-adjustment term Ag since both terms can induce a sharper generalization bound.
3.3 Principled Learning Algorithm induced by the Theoretical Insights
In this part, we present a principled learning algorithm induced by the theoretical insights in Sec.3. First, according to (In1)-(In3), it is crucial to comprehensively utilize re-weighting, logit-adjustment, and the DRW scheme, as they all contribute to improving the generalization bound. Second, according to (In4), we propose Truncated Logit-Adjustment (TLA) scheme to avoid the conflict between dg and By. In this scheme, By still increases w.r.t. Ny during the initial phase of training but truncated to 1 during the terminal phase of training. Third, we set ay Ty >> 0 to align ay with /Ty. which we name Aligned DRW (ADRW). Note that such a re-weighting scheme also follows the Fisher consistency property presented in [13]. Finally, the overall algorithm is summarized in Alg. I, where the logit-adjustment methods mentioned in Sec.2.1 are all reasonable options for By, Ay the line 5 and A, in the line 7,

---

Algorithm 1: Principled Learning Algorithm induced by the Thcoretical Insights
Require: Training set = {( y=) and a model ff parameterized by 6. Initialize the model parameters è randomly.
2: for t = 1,2, ... T do
3: B <- SampleMimiBatch(,,, m)
mini-batch m samples
4: it' < To then
5: Set 1, By. Ay
Adjust logits during the initial phase
6: else
7: Set Oty & Tyy B = L, 1, 0
b TLA and ADRW
8:
end if'
9:
T. - 1 Elanjes vvs (f()),)))
Calculate the loss
θ θ - ,)VaL(J,B)
D One SGD step
11:
Optional: anneal the learning rate 7/
Required when To
12: end for
Balaaced Accuracy
Belenced Accuracy
Balanced Accuracy
Belsnned Accuracy
78-
20-
62-
78-
41-
02-
04-
GEMORRN
88
80
38
(a) CIFAR-IOLT (b) CIFAR- 10 Step
(c) CIFAR- LT
(d) CIFAR-100 100 Step
Figure 1: The balanced accuracy of the CE loss and the LDAM loss w.t. By n. the CIFAR datasets, where the imbalance ratio p = 100. Both weighttg and logit-adjustment boost the model
performance, which is consistent with the theoretical insight (Inl) and (In4-b).
10
10
0.5
Perfommance
Perfonmacce
(a) CIFAR-10 LT
(b) CIFAR-10 Step
Figure 2: Sensitivity analysis of VS+ADRW w.r.t ay & R."" and A, log Fy on the CIFAR-10 dataset, where the imbalance ratio = 100. Both re-weighting and logit-adjustment boost the model performance, which is consistent with the theoretical insights (In1) and (In4-b).
4 Experiments
4.1
Experiment Protocols
Here, we briefly introduce the experiment protocols, and more details can found in Appendix F.
Datasets. We conduct the experiments four popular benchmark datasets for imbalanced learning. (a) CIFAR-10 and CIFAR-100. Following the protocol in [26, 11, 12], we consider two types of imbalance: maile imbalance (LT) and step imbalance (Step). For both imbalance types,
7

---

1.00
Min. MMjj Train Acc
4-
CENDRW
Test Accuracy
Train Acc
0.75
0.50
C3 Major
2-
0.25
DDWW Major Wi
Minee
20-
CE+DRW
0.00
0
50
100
150
200
50
100
150
50
100
150
Training Epoch
DRW Epoch To
Epoch To
(a) CIFAR-I00 LT (p = 100)
(b) CIFAR-100 LT (p 100)
(c) CIFAR- 100 LT (p 100)
Figure 3: (a) Training accuracy of CE+DRW (To 160) and the CB loss w.E.f. training epoch. (b) Acemin/ ACCmaj W.E.t. the DRW epoch To. where Accmin and Acemaj denote the training accuracy of the best model the minority/majority classes, respectively. (c) The test accuracy of the best model w.E. the DRW epoch Tp. We can find that the DRW scheme balances the training accuracy between the majority classes and the minority classes and thus improves the model performance on the test set, which is consistent with the theoretical insight (In2).
Accuracy
80.2-
Balenced Accuracy
Balanced Accuracy
$7.6
Balenced Accuracy
80.0
88.8
88.5
$5.0
85.0
82.5
50.0
45.0
VS-Nona
87.0
VS-teen
413
40.0
VS-heon
(a) CIFAR-IO LT
(b) CIFAR-10 10 Step
(c) CIFAR- 100 LT
(d) CIFAR-100 Step
Figure 4: The balanced accuracy of the VS loss w.f. By = (Ny (N)N on the CIFAR datasets, where the imbalance ratio p 10. We can find that VS+DRW performs inferior VS+None, especially when y is large, which is consistent with the theoretical insight (In4-a).
report the balanced accuracy averaged over random seeds with imbalance ratio p: Ni/No {10, 1003. (b) ImageNet-LT and iNaturalist: We use the long-tailed version of the ImageNet dataset? [2] proposed by [27], and iNaturalist [5] is a real-world long-tailed dataset.
Baselines and Competitors. For the CIFAR datasets, we aim validate the theoretical results and the performance gain induced by the proposed method. Hence, we select the following baselines:
the CE loss (CE) [19], the LDAM loss (LDAM) [12], LDAM+DRW [12], and the VS loss (VS) [16]
that generalizes the LA loss [13] and the CDT loss [14]. We tune all the hyperparameters according to the suggestions in the original papers. For the ImageNet-LT and iNaturalist datasets, we select
state-of-the-are methods, listed in Tab.2, as the competitors to validate the effectiveness of the method.
Implementation Details. We implement three instances of the proposed learning algorithm: the CE loss equipped with the ADRW scheme (CE+ADRW), the LDAM loss equipped with the ADRW scheme (LDAM+ADRW) and the VS loss equipped with the TLA and the ADRW scheme (VS+LLAADDWW) We tune the hyperparameter and the other hyperparameters follow those used in the baselines. In addition, we incorporate the Sharpness-AWe
Minimization (SAM) technique [28] to facilitate the optimization of the minority classes, allowing them to escape saddle points and converge to flat minima [29].
4.2 Theory Validation
In this part, we aim to validate our theoretical insights presented in Sec.3.2 on the CIFAR datasets.
Some more empirical results can be found in Appendix G.
"https://wwwcc..tt www.:w.w.torooo..oooooooo sasraatt..dbu/kkrii//ittaa. html. Licensed MIT.
hhttpa://image-ne http//mmmeeeet...r///deeeeee php. Licensed MIT.
'https://githul "ttpp:///tthal.../aaaappddttt/t http:/a/iiaaaaaeateo///oe//eee/e httpp///eee/mmmte///1/// Licensed MIT.

---

Table The balanced accuracy averaged over random seeds on the CIFAR datasets. The best and the runner-up method for each protocol are marked with red and blue, respectively. The best baseline model marked with underline.
Dataset
CIFAR-10
CIFAR-100
Imbalance Type
LT
Step
LT
Step
Imbalance Ratio
100
10
100
10
100
10
100
10
w/o SAM
CR
41.5
87. 87.0
64.820.9
85. +0.3
38.3
56.7+0.4
38.640.2
54.440.3
LDAM
73.8
86.4
65.8.20.6
85 +0.3
39.940.7
55.7+0.5
39.2+000
50.5
VS
78.8
88.7+0.1
76. 2007
88. 88.3
41.8
58.4+0.2
46.2+0.3
59.940.2
CE+DRW
75.8
87.9 aa.a
72.2
88 +
40.8
58.1
59.1 45.4
LDAM+DRW
77.7+0.4
87.5 500.2
77.8
87.8 47.8
42.7+a..
57.5+0.3
56.9 45.3
VS+DRW
80.1
88.610.1
78.2.10.2
88. 10.1
41.310.
57.610.3
44.0
58.010.3
CE+ADRW
78.610.5
88.2
75.5
88.5 18.5
41.8
58.3
59.210.3 46.5
LDAM+ADRW
79.110.2
87.610.2
78.5
88.1
43.0
58.010.1
45.8
57.610.3
VS+TLA+DRW
80.810.2
88.8
80.0
89.2
43.0
58.9
46.8
60.0
VS+TLA+ADRW
81.1
89.0
80.9
89.3
43.4
59.2g0.2
27.8
60.5
w/ SAM
CE+DRW
80.5
89.8
79.5
90.2
44.7+0.6
60.7+a.4
48.5
61.7+az
LDAM+DRW
81.61022
89.410.2
81.2
89.4
45.2
59.910.2
49.1
59.3
VS
82.6102
90.0
83.2
90.5
45.9
61.01a.3
47.4
61.6103
CE+ADRW
82.6102
90.1
82.8
90.2
44.9
61.0
48.9
62.1
LDAM+ADRW
83.0
89.7
82.4
90.0
46.340.4
60.3
49.3
60.3
VS+TLA+ADRW
83.640.2
90.3
83.8
90.8
46.440.6
61.9
49.1
62.3
Validation of (In1) and (1n4-b). We report the model performance of the baselines w.r.t. the hyperparameters in 1ig.1 and 2 From these results, can find that (1) Both CE+ADRW and LDAM perform better than CE. In other words, either re-weighting or logit-adjustment can boost the model performance. (2) LDAM+ADRW outperforms both CE+ADRW and LDAM, and for VS+ADRW, increasing the hyperparameters v and t appropriately can also bring performance gains. All these results validate the compatibility between re-weighting and the additive logit-adjustment.
Validation of (In2). We present a series of results in Fig.3, where the training accuracy of different classes represents the corresponding By (y). To be specific, Fig.3(a (()) demonstrates the trend of training accuracy on the majority classes and the minority classes. For the CB loss, the learning process only focuses on the minority classes and hinders the performance improvement on the majority classes (CB Major v.s. CB Minor). Hence, an extremely imbalanced (f) induces a poor generalization performance. By contrast, the DRW scheme first focuses the majority classes (CE+DRW Major v.s. CE+DRW Minor with the training epoch < To = 160) and then pays more attention to the minority classes during the terminal phase of training (CE+DRW Major v.s. CE+DRW Minor with the training epoch / > To 160). Benefiting from the DRW scheme, both the majority classes and the minority classes well-trained and thus have balanced term B,y (Fig.3(b)), leading to corresponding improvement on the test accuracy (Fig.3(c)). Even if we remove the re- re-weighting term (CE+None), the imbalance degree of (f) is still consistent with the test performance. Note that the learning rate of CE+None is also decreased at the corresponding epoch To, making the line in Figure 3(b) and 3(c) not constant.
Validation of (In4-a). In Fig.4, we present the model performance of the VS loss w.r.t. the hyperpa- rameter of the multiplicative odjit-adjusmment 7 We can find that VS+DRW performs inferior to VS, especially when y is large. This phenomenon validates the incompatibility between re-weighting and multiplicative lugit-adjustment.
4.3 Performance Comparison
We report the empirical results on the CIFAR datasets in Tab. where the imbalance ratio p (10, 100). From these results, we have the following observations: (1) The proposed learning algorithm consistently outperforms the baselines, especially when the dataset is more imbalanced.

---

Table 2: The balanced accuracy the ImageNet-LT and iNaturalist datasets.
ImageNet-LT
iNaturalist
Method
One stage
Many
Med.
Few
All
Many
Med.
Few
All
OLTR [27]
X
43.2
35.1
18.5
35.6
59.0
64.1
64.9
63.9
LFMR [30]
X
47.1
35.0
17.5
37.2
BBN [31]
X
49.4
70.8
65.3
66.3
cRT [32]
X
61.8
46.2
27.3
49.6
69.0
66.0
63.2
65.2
T-norm [32]
X
59.1
46.9
30.7
49.4
65.6
65.3
65.5
65.6
DiVE [33]
X
64.1
50.4
31.5
53.1
70.6
70.0
67.6
69.1
DisAlign [34]
X
61.3
52.2
31.4
52.9
69.0
71.1
70.2
70.6
WB [35]
X
62.5
50.4
41.5
53.9
71.2
70.4
69.7
70.2
[32]
65.9
37.5
7.7
44.4
72.2
63.0
57.2
61.7
CE+CB [1]]
39,6
32.7
16.8
33.2
53.4
54.8
53.2
54.0
Focal [1]]
36.4
29.9
16.0
30.5
61.1
De-confound [36]
62.7
48.8
31.6
51.8
DRO-LT [37]
64.0
49.8
33.1
53.5
69.7
SAM [29]
62.0
52.1
34.8
53.1
64.1
70.5
71.2
70.1
Ours
62.9
52.6
37.1
54.1
64.7
70.7
72.1
70.7
Such performance gains validate the effectiveness of the proposed methods (2) Both re-weighting and logit-adjustment can improve the model performance, which is consistent with the theoretical insight (In1) and (In4-b). (3) When
10 or on the CIFAR-100 100 dataset, VS+DRW performs inferior to VS. Fortunately. when equipped with the proposed TLA scheme, VS+TLA+DRW outperforms both VS and VS+DRW. These results again validate our theoretical insight (In4-a). (4) When 10, CE+ADRW outperforms LDAM+ADRW, and similar counter-intuitive phenomena are also observed in [29]. We conjecture that in this case, re-weighting is enough to rebalance the generalization bound, and the additional LDAM loss might induce other issues such as inconsistency.
We present the overall balanced accuracy on the ImageNet-LT and iNaturalist datasets in Tab.2, where SAM and Ours denotes LDAM+DRW+SAM and VS+TLA+ADRW-SAN respectively. These results demonstrate that the proposed learning algorithm outperforms the competitors, especially the one-stage ones, which again confirms the effectiveness of the proposed learning algorithm.
Conclusion and Future Work
In this work, with the proposed local Lipschitz property and the data-dependent contraction technique, we present unified generalization analysis of the loss-modification approaches for imbalanced learning. Benefiting from this fine-grained analysis, we not only reveal the role of both re- re-weighting and logit-adjustment approaches but also explain some empirical phenomena that are out the scope of existing theories. Moreover, principled learning algorithm is proposed based the theoretical insights. Finally, extensive experimental results on benchmark datasets validate our theoretical analysis and the effectiveness of the proposed method.
Theoretically, one important future work provide a systematical Fisher consistency analysis for the VS loss, providing more insights to design re- re-weighting and logit-adjustment terms. Method- ologically, it might be a promising direction to design an adaptive scheme that can automatically determine the hyperparameters of the learning algorithm.
Acknowledgments
This work was supported in part by the National Key R&D Program of China under Grant 2018AAA0102000, part by National Natural Science Foundation of China: 62236008. U21B2038, U2001202, 61931008 62122075, 61976202 and 62206264, in part by the Fundamental Research Funds for the Central Universities, in part by Youth Innovation Promotion Association CAS, in part by the Strategic Priority Research Program of Chinese Academy of Sciences (Grant No. XDB28000000) and in part by the Innovation Funding of ICT, CAS under Grant No. E000000.
10

---

References
[1] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. pages 1-60, 2009.
[2] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Fei- Fei. Imagenet large scale visual recognition challenge. Int. J. Comput. Vis., 115:211-22 12,22, 2015.
[3] Mark Everingham, Luc Van Gool, Christopher K. Williams, John M. Winn, and Andrew Zisserman. The pascal visual object classes (VOC) challenge. Int. J. Comput. Vis., 88:303-338, 2010.
[4] Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft COCO: common objects in context. In European Conference on Computer Vision, pages 740-755, 2014.
[5] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alexander Shepard, Hartwig Adam, Pietro Perona, and Serge J. Belongie. The inaturalist species classification and detection dataset. In IEEE Conference on Computer Vision and Pattern Recognition, pages 8769-87777 8778. 2018.
[6] Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Trans. Knowl. Data Eng., 11:1263-1284 2009.
[7] Grant Van Horn and Pietro Perona, The devil is in the tails: Fine- ainengrained classification in the wild. CoRR, abs/ htss/1709.015000 2017.
[8] Kemal Oksuz, Baris Can Cam, Sinan Kalkan, and Emre Akbas. Imbalance problems in object detection: A review. IEEE Trans. Pattern Anal. Mach. Intell., 43:3388-3415, 2021.
[9] Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan, and Jiashi Feng. Deep bnng-tailed learning: A survey. CoRR, abs/21 10.04596, 2021.
[10] Katharina Morik, Peter Brockhausen, and Thorsten Joachims. Combining statistical learning with knowledge-bel Conference on Machine Learning, pages 268-277, 1999.
approach case study in intensive monitoring. In International
[11] Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge J. Belongie. Class- balanced loss based effective number of samples. In IEEÉ Conference Computer Vision and Pattern Recognition, pages 9268-9277, 2019.
[12] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Aréchiga, and Tengyu Ma. Learning imbalanced datasets with label-dissributionnaaaar margin loss. In Annual Conference Neural Information Processing Systems, pages 1565-1576, 2019.
[13] Aditya Krishna Mcnon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In International Conference Learning Representations, 2021.
[14] Han-Jia Ye, Hong- You Chen, De-Chuan Zhan, and Wei-Lun Chao. Identifying and compensat- ing for feature deviation in imbalanced deep learning. CoRR, abs/2001.01385. 2020.
[15] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan. Equalization loss for long-tailed object recognition. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1659-116688 2020.
[16] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label-imbalanced and group-sensitive classification under overparameterization. Annual Conference Neural Information Processing Systems, pages 18970-18983, 2021.
[17] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. IEEE Conference on Computer Vision and Puttern Recognition, pages 5375-5384, 2016.

---

[18] Jiawei Ren, Cunjun Yu, Shunan Sheng, Xiao Ma, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Balanced meta-sofimax for long-tailed visual recognition. In Annual Conference on Neural Information Processing Systems, 2020.
[19]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
[20] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
[21] Aditya Krishna Menon, Harikrishna Narasimhan, Shivani Agarwal, and Sanjay Chawla. On the statistical consistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pages 601-611, 2013.
[22] Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Annual Conference on Neural Information Processing Systems, pages 793-800, 2008.
[23] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Localized rademacher complexities. In Annual Conference on Computational Learning Theory, pages 44-58, 2002.
[24] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299, 2018.
[25] Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. International Conference on Learning Representations, 2020.
[26] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski. A systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, 106:249-259, 2018,
[27] Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X. Yu. Large-scale long-tailed recognition in an open world. In IEEE Conference on Computer Vision and Pattern Recognition, pages 2537-2546, 2019.
[28] Pierre Foret, Ariel Kleiner, Hossein Mobahi. and Behnam Neyshabur. Sharpness-awe awaree min- imization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
[29] Harsh Rangwani, Sumukh K. Aithal, Mayank Mishra, and R. Venkatesh Babu. Escaping saddle points for effective generalization on llss-imbalanced data. In Advances in Neurul Information Processing Systems, pages 22791-22805, 2022.
[30] Liuyu Xiang. Guiguang Ding, and Jungong Han. Learning from multiple experts: Self- Self-paced knowledge distillation for long-tailed classification. In European Conference on Computer Vision, pages 247-263, 2020.
[31] Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen. BBN: bilateral-branch network with cumulative learning for long-tailed visual recognition. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2020.
[32] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In International Conference on Learning Representations, 2020.
[33] Yin-Yin He, Jianxin Wu, and Xiu-Shen Wei. Distilling virtual examples for long-tailed recogni- tion. In IEEE/CVF International Conference on Computer Vision, pages 235-244, 2021.
[34] Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun. Distribution alignment: unified framework for long-tail visual recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pages 2361-2370, 2021.
[35] Shaden Alshammari, Yu-Xiong Wang, Deva Ramanan, and Shu Kong. Long-tailed recognition via weight balancing. In IEEE/CVF Conference on Computer Vision and Pattern Recognition,, pages 6887-6897, 2022.
12

---

[36] Kaihua Tang, Jianqiang Huang, and Hanwang Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. In Annual Conference on Neural Information Processing Systems, 2020.
[37] Dvir Samuel and Gal Chechik. Distributional robustness loss for long-tail learning. In /EEE//VV International Conference Computer Vision, pages 9475-9484, 2021.
[38] Lu Yang, He Jiang, Qing Song, and Jun Guo. A survey on long-tailed visual recognition. Int. J. Comput. Vis., 130:1837-1872, 2022.
[39] Miroslav Kubat and Stan Matwin. Addressing the curse of imbalanced training sets: One-sided selection. In International Conference on Machine Learning, pages 179-186, 1997.
[40] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16: 321-357, 2002.
[41] Inderjeet Mani and I Zhang. knn approach to unbalanced data distributions: case study involv- ing information extraction. In Workshop on Learning from Imbalanced Datasets, International Conference Machine Learning, pages 1-7, 2003.
[42] Chris Drummond, Robert C Holte, et al. C4. 5, class imbalance, and cost sensitivity: why under-sampling beats over-sampling. In Workshop Learning from Imbalanced Datasets II, International Conference on Machine Learning, pages 1 1-8, 2003.
[43] Justin M. Johnson and Taghi M. Khoshgoftaar. Survey on deep learning with class imbalance.
J. Big Data, 6:27, 2019.
[44] Guillem Collell, Drazen Prelec, and Kaustubh R. Patil. Reviving threshold-moving: a simple plug-in bagging ensemble for binary and multiclass imbalanced data. CoRR, (tbs/160600668.. 2016.
[45] Jiarui Cai, Yizhou Wang, and Jenq-Neng Hwang. ACE: ally complementary experts for solving long-tailed recognition in one-shot. In IEEE/CVF International Conference Computer Vision, pages 112-121, 2021.
[46] Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella X. Yu. Long-tailed recogni- tion by routing diverse distribution-aware experts. In International Conference on Learning Representations, 2021.
[47] Jiequan Cui, Zhisheng Zhong, Shu Liu, Bei Yu, and Jiaya Jia. Parametric contrastive learning. In IEEE/CVF International Conference on Computer Vision, pages 695-704, 2021.
[48] Zhisheng Zhong, Jiequan Cui, Shu Liu, and Jiaya Jia. Improving calibration for long-tailed recognition. In IEEE Conference on Computer Vision and Pattrn Recognition, pages 16489- 16498, 2021.
[49] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778. 2016.
[50] Ilya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning. In International Conference Machine Learning, pages 1139-1147, 2013.
[51] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019.
13

---

[52] Charles R. Harris, K. Jarrod Millman, Stéfan van der Walt, Ralf Gommers, Pauli Virtanen, David Coumaaeaa, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fer- nández del Río, Mark Wiehe, Pearu Peterson, Pierre Gérard-Marchant. Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with numpy. Nat., 585:357-362, 2020.
[53] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- Plas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay. Scikit-learn: Machine learning in python. J. Mach. Learn. Res., 12:2825-288 2830, 2011.
[54] Sébastien Marcel and Yann Rodriguez. Torchvision the machine- machine-vision package of torch. In Proceedings of the 18th International Conference Multimedia 2010, Firenze, Italy, October 25-29, 2010, pages 1485-1488, 2010.
14


Reviews:
[{"review_id": "HRCKvzRAkM", "reviewer": "Reviewer_2B2B", "summary": "This paper provides a unified generalization analysis of the loss-modification approaches for imbalanced learning. It analyzes the gap between balanced accuracy and empirical loss (the loss may involve re-weighting and logit-adjustment approaches). It further provides empirical analysis that matches the theoretical insights. And a new method induced by the theoretical results with better performance is also proposed. ", "questions": "SEE Weaknesses.", "limitations": "NAN.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper directly establishes a theoretical connection between balanced accuracy and empirical loss, which is not attained in previous work. \n2. In this paper, the existing methods are systematically reviewed, and according to the new theoretical results, the existing methods are well classified and discussed. \n3. The charts and tables are beautifully formatted and laid out. \n", "weaknesses": "1. What we would like to bound is the balanced accuracy $\\mathcal{R}_{bal}$, where the loss is measured by $M$. However, in the imbalanced learning setting, $L$ is not just a differential surrogate version of $M$, but instead is an adjusted version that puts more emphasis on the small classes. In such circumstances, what is the meaning of bounding $\\mathcal{R}_{bal}^L$? Measuring under a class-balanced distribution while small classes are still emphasized in the loss? (By the way, please check the mapping of L in line 84.)\n2. How is ‘data-dependent’ exhibited in the theoretical result? Is it just about the sample size in each class, i.e., label distribution? Is there anything more than label distribution?\n3. In Eq.(14), what is By(f)? I checked the supplementary and I see it is a constant. What is the meaning of it? Is it the minimal margin on class y? I think these points should be made clear in the main body of the paper. And at the moment, I am also doubtful about the argument ‘balanced / imbalanced By(f)’ in the paragraph of line 192-200, which may involve the mechanisms in By(f). \n4. Maybe I misunderstood it, I suppose in Figure 3, T0 marks the start of DRW, and the total epoch T is fixed. Then why the line ‘CE+None’ is not constant in Figure 3(b) and 3(c)？\n5. In section 3.3, there is no mention of the setting of $\\Delta_y$. So does the setting of $\\beta_y$ in the $t<T_0$ stage. And in experiments, it would be better if provided more details on how these hyperparameters are tuned. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments, and the response is as follows. \n\n> **Q1**: The meaning of bounding $\\mathcal{R}_{bal}^L$.\n\n**A1**: In the `non-asymptotic` level (finite samples), bounding $\\mathcal{R}\\_{bal}^L$ can put more emphasis on minority classes, which is consistent with your understanding. But if we take an `asymptotic` view (infinite samples), it is beyond an adjusted version. Ideally, a small $\\mathcal{R}\\_{bal}^L$ should induce a small $\\mathcal{R}\\_{bal}$. To this end, a basic requirement is Fisher consistency. That is, optimizing $\\mathcal{R}\\_{bal}^L$ can recover the optimal solution to $\\mathcal{R}\\_{bal}$:\n$$\n    \\mathcal{R}\\_{bal}^L(f) \\to \\min\\_f \\mathcal{R}\\_{bal}^L(f) \\Rightarrow  \\mathcal{R}\\_{bal}(f) \\to \\min\\_f \\mathcal{R}\\_{bal}(f).\n$$\nAs mentioned in Sec.2.1, the generalized loss we consider has a consistent special case [13]:\n$$\n    L\\_F(\\boldsymbol{s}, y) := \\frac{\\delta\\_y}{\\pi\\_y} \\log [1 + \\sum\\_{y' \\neq y} \\frac{\\delta\\_{y'}}{\\delta\\_{y}} e^{\\boldsymbol{s}\\_{y'} - \\boldsymbol{s}\\_{y}}], \n$$\nwhere $\\delta_y > 0$ is an arbitrary constant. Hence, if we select such a $L$, bounding $\\mathcal{R}\\_{bal}^L$ also helps bound $\\mathcal{R}_{bal}$. Of course, not all losses are consistent, and we need a systematic analysis in future work. \n\n---\n\n> **Q2**: Check the mapping of $L$.\n\n**A2**: Thanks for your careful reading! The mapping of $L$ should be $\\mathbb{R}^C \\times \\mathcal{Y} \\to \\mathbb{R}_+$. We will correct it in the future version.\n\n---\n\n> **Q3**: How is data-dependent exhibited?\n\n**A3**: Compared with the union bound [12], data-dependent is exhibited in:\n- The basic lemma, *i.e.*, Lemma 2 introduces $1 / \\pi_C$ to the generalization bound. Since $\\pi_C$ denotes the ratio of the most minor class, it can be regarded as a measure of imbalance degree. In other words, this lemma shows how the model performance depends on the imbalance degree of the data. \n- Based on the proposed techniques, Theorem 1 and Proposition 3 reveal how existing loss-oriented methods improve generalization performance by exploiting data priors, which is also beyond the label distribution itself.\n\n---\n\n> **Q4**: The meaning of $B_y(f)$ and 'balanced/imbalanced $B_y(f)$'.\n\n**A4**: Perhaps due to the way of our writing, it is a pity to leave the impression that $B_y(f)$ is not well formulated. As described in line 462, $B_y(f)$ is the minimal prediction on the ground-truth class $y$, i.e., $B_y(f) := \\min\\_{\\mathbf{x} \\in S_y} s_y$. Following your understanding, $B_y(f)$ is closely related to the minimal margin, which is defined as $\\text{margin}\\_y^\\downarrow := \\min_{\\mathbf{x} \\in S_y} (s_y - \\max_{j \\neq y} s_j)$. In other words, **a large $B_y(f)$ can implicitly increase the minimal margin of the class $y$**. Meanwhile, we have \n$$\n    B_y(f) - \\text{margin}\\_y^\\downarrow \\le \\max\\_{\\mathbf{x} \\in S_y, j \\neq y} s_j.\n$$\nHence, **as we improve the model performance on class $y$, the RHS of the above inequality, i.e., the gap between $B_y(f)$ and $\\text{margin}_y^\\downarrow$ will decrease, and both the minimal margin and $B_y(f)$ will increase.**\n\nKeeping this mechanism in mind, the argument 'balanced/imbalanced $B_y(f)$' becomes easier to understand. In fact, `balanced/imbalanced` are indeed a little confusing, thus we next use `take into account`. As shown in Fig.3a, a weighted loss can boost the model performance on minority classes but hinders further improvement on majority classes. As a result, majority/minority classes have relatively small/large $B_y(f)$, respectively (*i.e.*, fail to take into account the $B_y(f)$ of majority classes). By contrast, DRW helps both majority classes and minority classes have a small $B_y(f)$ (*i.e.*, take into account $B_y(f)$ of both majority classes and minority classes). This explains why DRW can bring a better generalization performance, which is our main point.\n\n---\n\n> **Q5**: The line 'CE+None' is not constant in Figure 3.\n\n**A5**: In DRW, both reweighting and small learning rates will be used when $t > T_0$ [12]. To provide a more informative comparison, we also decrease the learning rates of `CE+None` at the corresponding epoch $T_0$ as `CE+DRW`, making the line in Fig.3 not constant. We will clarify this issue in the future version.\n\n---\n\n> **Q6**: The setting of $\\Delta_y$ and $\\beta_y$.\n\n**A6**: Perhaps due to the way of our writing, it is a pity to leave the impression that $\\beta_y$ and $\\Delta_y$ are not well defined in Sec.3.3. In fact, our analysis and the induced algorithm are both based on the generalized loss defined in Sec.2.1. Hence, all the $\\beta_y$ and $\\Delta_y$ mentioned in Sec.2.1 are reasonable options. In general, the loss family can be written as:\n$$\n    L_\\text{VS}(\\boldsymbol{s}, y) = - \\alpha_y \\log \\left( \\frac{e^{\\beta_y s_y + \\Delta_y}}{\\sum_{y'} e^{\\beta_{y'} s_{y'} + \\Delta_{y'}} } \\right).\n$$\nAnd \n- $\\beta_y \\in \\{1, (N_y / N_1)^{\\gamma}\\}$, where $N_y$ denotes the number of samples in the class $y$, and $\\gamma > 0$.\n- $\\Delta_y \\in \\{0, \\tau \\log \\pi_y, - \\frac{C}{N_y^{1 / 4}} \\}$, where $\\tau, C >0$. If $\\Delta_y = - \\frac{C}{N_y^{1 / 4}}$ for the ground-truth label $y$, $\\Delta_{y'} = 0$ for $y' \\neq y$ [12].\n\nWe will clarify this issue in the future version.\n\n---\n\n> **Q7**: Details of hyperparameter search.\n\n**A7**: To validate our theoretical results, we first tune these parameters via grid search as suggested in [13, 16]. Specifically, $\\alpha_y \\propto \\pi_y^{-\\nu}$, and $\\nu$ is searched in $\\\\{0.15, 0.25, 0.75, 1.0, 2.0, 3.0\\\\}$; $\\Delta_y = \\tau \\log \\pi_y$, and $\\tau$ is searched in $\\\\{0.5, 0.75, 1.0, 1.25, 2.0\\\\}$; $\\beta_y = (N_y / N_1)^\\gamma$, and $\\gamma$ is searched in $\\\\{0.05, 0.1, 0.15, 0.2, 0.25\\\\}$. \n\nBenefiting from the theoretical validation in Sec.4.2, the complexity can be significantly decreased. For example, according to Fig.4, we will choose a small $\\gamma$ when $\\nu$ is large to avoid the incompatibility issue. We will update this detail in the future version."}, {"review_id": "NzMUaKAb83", "reviewer": "Reviewer_D9Eg", "summary": "This paper proposes a sharpened generalization bound of imbalance learning by directly bounding the balanced empirical risk. The authors achieve this by generalizing the Lipschitz Continuity to the Local Lipschitz Continuity with a group of constants, which, in VS Loss, is parameterized by a re-weighting term, a generalization term, and a logit adjustment term. By adjusting the above three terms with their proposed algorithm TLA and ADRW, the authors achieve keeping the balance between class balance and generalization of a model.", "questions": "I have no questions from the authors.", "limitations": "The authors have discussed their limitations in the form of future work in Section 5.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper unified re-weighting and logit adjustment, two common methods for solving the imbalance problem, which I think is a good contribution to this field. Moreover, the authors' entry point is novel, providing sophisticated proof for their theory, the paper is well-written, and the experiments also well demonstrate their claims.", "weaknesses": "The authors only perform their experiment on the ResNet family for all the baselines and their proposed method. I hope the authors can provide the experiment result of their proposed method on different network structures in future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your nice suggestions, and we would like to make the following response. \n\n> **Q**: The authors only perform their experiment on the ResNet family for all the baselines and their proposed method. I hope the authors can provide the experiment result of their proposed method on different network structures in future work.\n\n**A**: Thank you for this nice suggestion! As mentioned in Appendix E, we follow the protocols of the prior arts [12, 28, 37]. To further investigate the effect of backbone, we conduct a preliminary experiment based on DenseNet121 on CIFAR-100 LT ($\\rho=100$). Due to the time limit, we only tune $\\alpha_y, \\beta_y, \\Delta_y$ and fix the other parameters such as the learning rate, weight decay, and the training epoch. The empirical results averaged on three seeds are listed as follows, which are consistent with those of ResNet. We will provide more results in future work.\n\n| Dataset | CIFAR-100 | \n|:------- |:---------:|\n| Imbalance Type | LT ($\\rho=100$) |\n| CE | 42.8 $\\pm$ 0.3 |\n| CE + DRW | 44.1 $\\pm$ 0.6 |\n| CE + ADRW | 45.2 $\\pm$ 0.4 |\n| VS | 47.5 $\\pm$ 0.5 |\n| VS + DRW | 47.5 $\\pm$ 0.3 |\n| VS + TLA + ADRW | 48.0 $\\pm$ 0.4 |"}, {"review_id": "CaXqy50eXm", "reviewer": "Reviewer_sr97", "summary": "In this paper, the authors study the problem of class imbalance. To be specific, they identify that there is a gap between the generalization theory of re-weighting & logit adjustment techniques and the practice. To be specific, they identify that the existing generalization bounds fail to account the imbalance among classes. The authors propose to close the gap by introducing an imbalance-specific bound, and then perform an analysis with existing methods to gain more insights about the effects of certain design choices. Finally, they introduce a variation on existing loss functions that perform better than existing approaches.\n\nAfter the rebuttal:\n\nWith the rebuttal, the authors addressed my minor comments about clarifications on certain details. This is a solid NeurIPS paper. I recommend accepting the paper.", "questions": "None.", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper provides theoretical as well as practical results & insights.\n\n2. The four insights are very valuable.\n\n3. Strong improvements over the baselines.\n\n4. Generally easy to follow text.", "weaknesses": "I am generally happy with the paper. My only concern is that it contains many typos and grammatical errors. Moreover, I would find it easier if Fig 1, 2 and 3 analyzed the performances with respect to the imbalance ratio as commonly performed in the literature.\n\n\nMinor comments:\n\n- \"[12] proposes an effective scheme\" => Reference numbers should not be a part of a sentence. A correct way to write this is \"Cao et al. [12] propose an effective scheme\". \n\n- The paper uses many many acronyms without introducing them.\n\n- Lines 18-45: Already in these lines you should start with formulations (of ERM, margin theory etc.) since this paper is making theoretical contributions.\n\n- Line 47: \"loss function utilized in existing proof\" => \"loss function utilized in existing proofs\"?\n\n- Line 111: \"Let ||.|| denotes\" => \"Let ||.|| denote\".\n\n- Line 114: \"constants \\mu\" => \"constant \\mu\".\n\n- Line 207: \"Do re-weigting and logit-adjustment fully compatible?\" => \"Are re-weigting and logit-adjustment fully compatible?\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your nice suggestions, and we would like to make the following response. \n\n> **Q1**: Typos and grammatical errors.\n\n**A1**: Thanks for your careful reading! We will correct these typos and grammatical errors in the future version.\n\n---\n\n> **Q2**: The paper uses many many acronyms without introducing them.\n\n**A2**: Thanks for this careful comment! We will check all the acronyms and provide their introduction in the future version:\n- The Class-Balanced (CB) loss [11]: This method proposes a re-weighting term that depends on the effective number of each class, where the effective number is based on the idea that diminishing marginal returns for additional samples.\n- The Label-Distribution-Aware Margin (LDAM) loss [12]: this loss function uses additive terms, which depend on the label distribution, to encourage the model to have the optimal trade-off between per-class margins.\n- The Deferred Re-Weighting (DRW) scheme [12]: This scheme deploys the re-weighting loss with a small learning rate after a vanilla ERM training period. In other words, the re-weighting phase is deferred.\n- The Logit-Adjustment (LA) loss [13]: this loss function uses additive terms to adjust the logits, such that the induced objective is Fisher consistent with the balanced accuracy.\n- The Class-Dependent Temperatures (CDT) loss [14]: this method introduces multiplicative terms, also named temperature, to compensate for the effect of feature deviation between training and test data. \n- The Vector-Scaling (VS) loss [16]: this loss function combines the advantages of both the additive terms of the LA loss and the multiplicative terms of the CDT loss. \n\n---\n\n> **Q3**: Lines 18-45: Already in these lines you should start with formulations (of ERM, margin theory etc.) since this paper is making theoretical contributions.\n\n**A3**: Thanks for this constructive suggestion! In the future version, we will update the introduction to provide more formulations. For example, the naive Empirical Risk Minimization (ERM) can be denoted as \n$$\n    \\min_f \\hat{\\mathcal{R}}(f) := \\frac{1}{N} \\sum_{(\\boldsymbol{x}, y) \\in \\mathcal{S}} L(f(\\boldsymbol{x}), y), \n$$\nwhere $L: \\mathbb{R}^C \\times \\mathcal{Y} \\to \\mathbb{R}\\_{+}$ measures the performance of the model $f: \\mathcal{X} \\to \\mathbb{R}^C$ on the data point $(\\boldsymbol{x}, y)$ belonging to the training set $\\mathcal{S}$, and $C$ denotes the number of classes. As another example, we will provide the union bound based on the margin theory [12]:\n$$\n    \\mathcal{R}\\_\\text{bal}(f) \\precsim \\frac{1}{C} \\sum\\_{y=1}^{C} \\frac{1}{\\text{margin}\\_y^{\\downarrow} \\sqrt{N_y}},\n$$\nwhere $\\text{margin}\\_y^{\\downarrow}$ represents the minimal margin of the class $y$, and $N_y$ denotes the number of samples in class $y$. In contrast, our bound can be formulated by:\n$$\n    \\mathcal{R}\\_\\text{bal}(f) \\precsim \\frac{1}{C \\pi_C} \\sum\\_{y=1}^{C} \\mu_y \\sqrt{\\pi_y},\n$$\nwhere $\\pi_y := N_y / N$, and $\\mu_y$ is the local Lipschitz constant of $f$ for the class $y$. Next, we will point out that our result is shaper and can provide a series of insights, which can help highlight our theoretical contributions.\n\n---\n\n> **Q4**: I would find it easier if Fig 1, 2 and 3 analyzed the performances with respect to the imbalance ratio as commonly performed in the literature.\n\n**A4**: Thank you very much for this constructive comment! We will update the results with respect to the imbalance ratio $\\rho=10$ in the future version of Appendix. According to the policy, we first attach these figures in the PDF file of the “global” response."}, {"review_id": "WiwSRIa4MX", "reviewer": "Reviewer_4AC3", "summary": "For class-imbalanced learning, many studies modified the loss function to emphasize the learning on minority classes by reweighting or logit adjustment. These studies showed high epirical classification performance, but existing generalization analysis of such studies is not unified. In this paper, the authors propose a data-dependent contraction to capture how the modified losses affect each class. With the data-dependent contraction technique, a fine-grained generalization bound is established and the authors analyze existing class imbalanced learning studies in a unified manner by applying the generalization bound to the VS loss. The authors propose two principled algorithm : TLA and ADRW based on the theoretical insights, and verify effectiveness of the two proposed algorithm through extensive experiments on benchmark datasets.", "questions": "I have no questions.", "limitations": "The proposed algorithms (TLA, ADRW) improved classification performance, but the improvement seems not that significant under some settings (specifically between VS and VS+TLA+ADRW under CIFAR-10-LT, step w/sam and CIFAR-100-LT w/sam).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Well written paper, it is easy to follow the paper.\n\nGreat theoretical analysis and insights are given in this paper.\n\nNovel algorithms are proposed based on the analysis and the insights.\n\nExtensive experiments were conducted.", "weaknesses": "Code is not submitted. Thus I can not reproduce the experiment results in the paper.\n\nRecently proposed class imbalanced learning algorithms based on multiple experts, contrastive learning, knowledge distillation are not reviewed, and also not compared in the section 4.3. It seems that the proposed algorithms achive lower classification performance than recently proposed algorithms such as PACO, RIDE and ACE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Q1**: Code is not submitted. Thus I can not reproduce the experiment results in the paper.\n\n**A1**: Thanks for your constructive concern! According to the policy \n\n> If you were asked by the reviewers to provide code, please send an anonymized link to the AC in a separate comment (make sure the code itself and all related files and file names are also completely anonymized).\n\nwe have sent the anonymized link to the AC. In this repository, we provide:\n- the **checkpoints and the log files** that exactly correspond to the results reported in the response **A2**, which is stored in the folder `existing_results`\n- the **code** that can reproduce the results, as well as the **bash script** stored in the file `bash_scripts/run.sh`. Since the proposed methods, i.e., ADRW and TLA work only when $t > T_0$, we resume from the checkpoint in the folder existing_results with $t = T_0$, such that the randomness can be eliminated. For example\n\n```bash\npython cifar_train_sam.py --dataset cifar100 --imb_type exp --imb_factor 0.01 --loss_type VS --train_rule ADRW_T --gpu 1 --seed 0 --tro 0.25 --gamma 0.05 --tau 0.75 --rho 0.5 --wd 0.0005 --epochs 400 --t_reweight 320 --resume 'existing_results/better_wd+400epoch/320_ckpt.pth.tar' --exp_str Better_WD_400\n```\n\n---\n\n> **Q2**: Recently proposed class imbalanced learning algorithms based on multiple experts, contrastive learning, knowledge distillation are not reviewed, and also not compared in the section 4.3. It seems that the proposed algorithms achive lower classification performance than recently proposed algorithms such as PACO, RIDE and ACE.\n\n**A2**: Thanks very much for this constructive suggestion! Since this paper focuses on the loss-oriented methods for imbalanced learning, we mainly review prior works in this direction. According to your suggestion, we will update a more systematic review in the new version of the appendix to cover these orthogonal methods.\n\nWe did not compare the mentioned methods since the experimental protocols are quite different. Taking CIFAR-100-LT ($\\rho=100$) as an example, where `Simple Aug` denotes random crop and random flip, and `wd` represents weight decay.\n\n| | Ours | RIDE | ACE | PaCo |\n|:---|:---|:---|:---|:---|\n| Expert | Single | Multiple | Multiple | Single |\n| Training Epoch | 200 | 200 | 400 | 400 |\n| Data Augmentation | `Simple Aug` | `Simple Aug` + `Random Rotation` | `Simple Aug` + `Mixup` | `Simple Aug` + `RandAug` |\n| Better wd | $\\times$ | $\\checkmark$ | $\\checkmark$ | $\\checkmark$ |\n\nIn fact, if we align these protocols, the proposed method can outperform these methods. Here are the results on CIAFR-100 LT ($\\rho=100$), and we will provide more results in the future version.\n\n| Method | Balanced Accuracy | \n|:-|:-:|\n| RIDE | 49.10 |  \n| ACE | 49.60 |  \n| PaCo | 52.00 |  \n| Ours | 46.40 |  \n| Ours + Better wd | 49.54 |  \n| Ours + Better wd + 400 epoch | 50.16 |  \n| Ours + Better wd + 400 epoch + RandAugment | 52.97 |  \n\n---\n\n> **Q3**: The proposed algorithms (TLA, ADRW) improved classification performance, but the improvement seems not that significant under some settings (specifically between VS and VS+TLA+ADRW under CIFAR-10-LT, step w/sam and CIFAR-100-LT w/sam).\n\n**A3**: Thanks for your careful reading! Imbalanced learning is a challenging task, and even a small performance improvement is not trivial. In Sec.4, we reported the results averaged on 5 random seeds, and the proposed method outperforms the competitors consistently. \n\nBesides, we notice that the protocol might limit the improvement. After we adopt the protocol `Better wd + 400 epoch + RandAugment`, as mentioned in the response **A2**, for both VS and Ours, the improvement will be more significant:\n\n| Method | Balanced Accuracy | \n|:-|:-:|\n| VS | 51.83 |  \n| Ours | 52.97 |"}]

Author rebuttal:
Dear reviewers,

First, we would like to express our sincere gratitude for your valuable comments. Following the valuable suggestions, we have carefully polished and improved the corresponding details. Now we present a brief summary of the response.

- **We clarify some important concepts** such as 
    - the meaning of bounding $\mathcal{R}_\text{bal}^L$, (**Q1** for Reviewer 2B2B)
    - the meaning of 'data-dependent', (**Q3** for Reviewer 2B2B)
    - the mechanisms of $B_y(f)$, (**Q4** for Reviewer 2B2B)
    - the line of 'CE+None' in Fig.3, (**Q5** for Reviewer 2B2B)
    - the setting of $\beta_y, \Delta_y$, (**Q6** for Reviewer 2B2B)
    - the strategy for tuning the hyper-parameters, (**Q7** for Reviewer 2B2B)
    - the meaning of acronyms. (**Q2** for Reviewer sr97)
    - the formulation provided in the future version of the introduction. (**Q3** for Reviewer sr97)
- **We provide more empirical results**, including
    - those with different backbones (DenseNet121), (**Q** for Reviewer D9Eg)
    - those with a imbalance ratio $\rho=10$ (Fig.1-3), (**Q4** for Reviewer sr97)
    - those with different protocols (weight decay, epochs, and data augmentation). (**Q2,Q3** for Reviewer 4AC3)
- **We uploaded the code to an anonymized repository and sent its link to AC**. (**Q1** for Reviewer 4AC3)
- **We checked the typos and grammatical errors**. (**Q2** for Reviewer 2B2B, **Q1** for Reviewer sr97)

Please refer to the respective response for more details, and we will update all these improvements in the future version.

Meta-review: Reviewers were unanimously supportive of this paper, which provides an interesting new analysis of re-weighting and logit adjustment for learning with label imbalance. The paper makes solid theoretical and empirical contributions, and is likely to be of broad interest to the community.
Decision: Accept (spotlight)