Label-Imbalanced and Group-Sensitive Classification under Overparameterization
Authors: Ganesh Ramachandra Kini
Orestis Paraskevas
Samet Oymak
Christos Thrampoulidis
Venue: NeurIPS 2021 Poster (2021)
Keywords: fairness
overparameterization
cost-sensitive methods

Abstract: The goal in label-imbalanced and group-sensitive classification is to optimize relevant metrics such as balanced error and equal opportunity. Classical methods, such as weighted cross-entropy, fail when training deep nets to the terminal phase of training (TPT), that is training beyond zero training error. This observation has motivated recent flurry of activity in developing heuristic alternatives following the intuitive mechanism of promoting larger margin for minorities. In contrast to previous heuristics, we follow a principled analysis explaining how different loss adjustments affect margins. First, we prove that for all linear classifiers trained in TPT, it is necessary to introduce multiplicative, rather than additive, logit adjustments so that the interclass margins change appropriately. To show this, we discover a connection of the multiplicative CE modification to the cost-sensitive support-vector machines. Perhaps counterintuitively, we also find that, at the start of training, the same multiplicative weights can actually harm the minority classes. Thus, while additive adjustments are ineffective in the TPT, we show that they can speed up convergence by countering the initial negative effect of the multiplicative weights. Motivated by these findings, we formulate the vector-scaling (VS) loss, that captures existing techniques as special cases. Moreover, we introduce a natural extension of the VS-loss to group-sensitive classification, thus treating the two common types of imbalances (label/group) in a unifying way. Importantly, our experiments on state-of-the-art datasets are fully consistent with our theoretical insights and confirm the superior performance of our algorithms. Finally, for imbalanced Gaussian-mixtures data, we perform a generalization analysis, revealing tradeoffs between balanced / standard error and equal opportunity.

Label-Imbalanced and Group-Sensitive Classification under Overparameteriration
Ganesh Ramachandra Kini University of California, Santa Barbara kini@ucsb.edu
Orestis Paraskevas University of California, Santa Barbara
orestisqucsb.edu
Samet Oymak
Christos Thrampoulidis University of British Columbia cthrampo@ece. ubc.ca
University of California, Riverside oymakθece ucr.edu
Abstract
The goal in label-imbalancee and group-sensitive classification is to optimize relevant metrics such as balanced error and equal opportunity. Classical methods, such weighted cross-entropy, fail when training deep nets to the terminal phase of training (TPT), that training beyond zero training error. This observation has motivated recent flurry of activity developing heuristic alternatives following the intuitive mechanism promoting larger margin for minorities. In contrast to previous heuristies, we follow a principled analysis explaining how different loss adjustments affect margins. First, prove that for all linear classifiers trained in TPT, is necessary to introduce multiplicative, rather than additive, logit adjustments that the interclass margins change appropriately. To show this, discover a connection of the multiplicative CE modification to the cost-sensit support-vector machines. Perhaps counterintuitively we also find that, the start of training, the same multiplicative weights can actually harm the minority classes. Thus, while additive adjustments are ineffective in the TPT, we show that they can speed up convergence by countering the initial negative effect of the multiplicative weights. Motivated by these findings, we formulate the vector-sealing (VS) loss, that captures existing techniques special cases. Morcover, we introduce natural extension of the VS-loss to group-sensitive classification, thus treating the two common types of imbalances (label/group) state-oftthe-arl datasets are fully consistent with our theoretical insights and confirm the superior performance our algorithms. Finally, for imbalanced maittian-mixxures data, perform generalization analysis, revealing tradeoffs between balanced / standard error and equal opportunity.
unifying way. Importantly, our experiments on
1 Introduction
1.1 Motivation and contributions
Equitable learning in the presence of data imbalances is classical machine learning (ML) problem, but one with increasing importance as ML decisions are adapted in increasingly more complex applications directly involving people [3]. Two common types of imbalances are those appearing in label-imbllanced and group-sensitive classification. In the first type, examples from target class are heavily outnumbered by examples from the rest of the classes. The standard metric of average misclassification error is insensitive to such imbalances and among several classical alternatives the balanced is a widely used metric. In the second type, the broad goal is to ensure fairness with respect to a protected underrepresented group
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

(e.g. gender, race). While acknowledging that there is no universal fairness metric [27, 13], several suggestions have been made in the literature including Equal Opportunity favoring same true positive rates across groups [15].
Methods for imbalanced data broadly categorized into data- and algorithm- level ones. In the latter category, belong cost-sensitive methods and, specifically, those that modify the training loss to account for varying class/group penalties. Corresponding (SOTA) research is motivated by observations that classical methods, such as weighted cross-cntropy (wCE) fail when training overparameterized deep nets without regularization and with train-loss minimization continuing well beyond zero train-crror, in the so-called terminal phase of training (TPT) ([43] and references therein). Intuitively, failure of wCE when trained in TPT is attributed to the failure to appropriately adjust the relative margins between different. classes/grond groups in a way that favors minorities. To overcome this challenge, recent works have proposed so-called logit-adjusted (LA) loss that modifies the cross-entropy (CE) loss by including extra additive hyper- arper-parameters acting on the logits [24, 8, 32]. Even more recently, [54] suggested yet another modification that introduces multiplicative hyper- parameters on the logits leading to a class-depeudent temperature (CDT) loss. Empirically, both adjustments show performance improvements over wCE. However, it remains unclear: popeer-praamterss lead to maarinn-adjsttmnn favoring
saate-of-the-arr
Do both additive and multiplicative minority closses? If so, what are the individual mechanisms that lead to this behavior? How effective are different adjustments at each stage of training?
This paper answers the above questions. Specifically, we argue that multiplicative hyper- parameters are most effective for margin adjustments in TPT, while additive parameters can be useful in the initial phase of training. Importantly, this intuition justifies our algorithmic contribution: we introduce the vector-scaling (VS) loss that combines both types of adjustments and attains improved performance SOTA imbalanced datasets. Finally, using the same set of tools, we extend the VS-loss to instances of group-sensitive classification. We make multiple contributions as summarized below; see also Figure 1.
Explaining the distinct roles of additive/multee ceadttivemmultiilicattieee adjustments. We show that when optimizing in TPT multiplicative logit adjustments are critical. Specifically, we prove for linear models that multiplicative adjustments find classifiers that are solutions to cost-sensitive
(CS-SVM), which by design create larger margins for minority classes. While effective in TPT, we also find that, at the start of training. the same adjustments can actually harm minorities. Instead, additive adjustments can speed up convergence by countering the initial negative effect of the multiplicative ones. The analytical findings are consistent with our experiments.
An improved algorithm: VS-loss. Motivated by the unique roles of the two different types of adjustments, we propose the vector-scaling (VS) loss that combines the best of both worlds and outperforms existing techniques on benchmark datasets.
Introducing logit-adjustments for group- imbalanced data. We introduce version of VS-loss tailored to group-imbalanced datascts, thus treat- ing, for the first time, loss-adjustments for label and group imbalances in a unifying way. For the latter, we propose new algorithm combining our VS-loss with the previously proposed DRO-methed to achieve ftate-offre the-art performance in terms of
Adjustment
Induuctiv hiss
Additiv:
Maltiplicaive
SVM
CS-SVM
LA-ins 30R-30++e)
CDTs pocxa))
VS-loss
Prior Ouns
Indrcctive blas Group imbalances Generallation "uudeoffs
both Equal Opportunity and worst-subgroup error.
Generalization analysis / fairness trade- offs. We present a sharp gencralization analysis of the VS-loss on binary overparameterized Gaussian mixtures. Our formulae are explicit in terms of data geometry, priors, parameterization ratio and hyperparameters: thus, leading to tradeoffss between standard error and fairness measures. We find that VS-loss can improve both balanced and standard error over CE. Interestingly, the optimal hyperparameters that minimize balanced error also optimize Equal Opportunity.
Figure Summary of contributions.
2

---

1.2 Connections to related literature
CE adjustments. The use of wCE for imbalanced data is rather old [53], but it becomes ineffective under overparameterization, e.g. [6]. This deficiency has led to the idea of additive label-based parameters by on the logits [24, 8, 50, 32, 52]. Specifically, [32] proved that setting by = (T)( (Ty denotes the prior of class y) leads to Fisher consistent loss, termed L.-lloss, which outperformed other heuristics (e.g., focal loss [28)) on SOTA datasets. However, Fisher consistency is only relevant in the large sample size limit. Instead, we focus on overparameterized models. In a recent work, [54] proposed the CDTT-lss,, which instead uses multiplicative basel-based parameters Ay on the logits. The authors arrive at the CDT-loss as a hcuristic means of compensating for the empirically observed phenomenon of that the last-layer minority features deviate between training and test instances [25]. Instead, we arrive at the CDT-loss via different viewpoint: we show that the multiplicative weights are necessary to move decision boundaries towards majorilies when training overparameteriixt linear models in TPT. Moreover, we argue that while additive weights are not so effective in the TPT, they can help the initial phase of training. Our analysis sheds light on the individual roles of the two different modificat iinns proposed in the literature and naturally motivates the VS-loss in (2). Compared to the above works we also demonstrate the successful use of VS-Loss in group-imbalanced setting and show its competitive performance over alternatives in [45, 18, 40). Beyond CE adjustments there is active rescarch alternative methods to improve fairness metrics, c.g. [23, 56, 29, 41]. These are orthogonal to CE adjustments and can potentially be used in conjunction.
Relation to vector-scaling calibration. Our naming of the VS-loss is inspired by the vector scaling (VS) calibration [14], a post-hoe procedure that modifies the logits v after training via A @ v + L, where O is the Hadamard product. [55] shows that VS can improve calibration for imbalanced classes, but, in contrast to VS calibration, the multiplicative/addiin additive scalings in our VS-loss are part of the loss and directly affect training. Overparameterizatio acts as a catalyst for deep neural networks [38]. In terms of optimization, [47, 42, 20, 2] show that gradient-based algorithms are implicilly biased towards favorable min-norm solutions. Such solutions, are then analyzed in terms of generalization showing that they can in fact lead to benign overfitting e.g. [4, 16). While implicit bias is key to benign overfitting it may come with certain downsides. As a matter of fact, we show here that certain hyper- arper-parameters (e.g. additive ones) can be ineffective in the interpolating regime in promoting fairness. Our argument essentially builds on characterizing the implicit bias of wCF./AA WCF//AA/CDT--osse /CDT-losses. Related to this, [46] demonstrated the ineffectiveness of Wy in learning with groups.
Blessings/ cursss of overparameterization
2 Problem setup
Data. Let training set {(x;; 9s: (/)))) HL consisting of i.i.d. samples from a distribution D over X x G y); X s Rd is the input space, y = [C[ = (1,.... C) the set of C labels, and, [-[K] refers to group membership among K 2 1 groups. Group-assinmments are known for training data, but unknown at test time. For concreteness, we focus here on the binary setting, i.e. C= 2 and y [[-1++++;; we present multiclass extensions in the Experiments and in the Supplementary Material (SM). We assume throughout that y y= is minority class.
Fairness metrics. Given a training set we learn fw : X H y parameterized by w E R". For instance, linear models take the form fw = (w, (x)) for some feature representation h: X' - RP. Given a new sample x, we decide class membership 9 = sign([w(x] (standard) risk or misclassifiention error is R : P (ú for given values of and g. We also define the class-corditiion and, the sub-group- lob-group-codddtional error averages the conditional risks of the two classes: Rbal (R. + R- )/2.. Assuming
The y). Let = (v..)) define subgroup
risks R_ = P (ū # yly=
conditional risks R2,= P (0 y yly wly= =1.g= }}. j jE [K]. The balanced
K 2 groups, Equal Opportunity requires Rt,1 = RR, [15]. More generally, we consider the (signed) difference of equal opportunity (DEO) Ruco == Rt,1 - R.,22 In our experiments, we also measure the worst-case subgroup error (v Ry.g-
Terminal phase of training (TPT). Motivated by modern training practice, assume overparameterized fw so that Rtrain = 1 Exe(m] [[sign(fwxx # y:] can be driven to zero. Typically, training such large models continues well-beyond zero training error as the training loss is being pushed toward zero. As in [43], we call this the terminal phase of training.
3

---

2.1 Algorithms
Cross-entropy adjustments. We introduce the vector-scaling (VS) loss, which combines both additive and multiplicative logit adjustments, previously suggested in the literature in isolation. The following is the binary VS-loss for labels y [+1}, weight parameters wa 0, additive logit parameters 4 E R, and multiplicative logit parameters A. > 00;
(vs (x)) = wiy log (1 ee -
For imbalanced datasets with C' > classes, the VS-loss takes the following form: fv -wy log (
Σ cE(C]
(2)
is the vector of logits. The VS-loss (Equs. (2), captures existing techniques special cases by tuming accordingly the additive additive//multillccativ multipliccateiv hyperparameters. Specifically, we recover: (i) weighted CE (wCE) loss by 4, 4, 0, ,yy; (ii) LA-loss by Ay = (iii) CDT-loss by 1y=
Here fw Rd RC and fx =
With the goal of (additionally) ensuring fairness with respect to sensitive groups, we extend the VS-loss by introducing parameters (Ay.gr (y.9 that depend both on class and group membership (specified by and g, respectively). Our proposed group-sensitive VS-loss is as follows (multiclass version can be defined accordingly):
(Group-vs( [x)) = Wv.9 log (1 + e'uie e ( Ankk(((()))
(3)
CS-SVM. For linear classifiers fx(x) = (w, h(x)) with h: X + R2, CS-SVM [31] solves
min |w/l2 sub. to (w, (xxx)) 2 , = +1 (x,,)(x,)) 5-1 : --1 2 [m].
(4)
for hyper-parameter 5e R2, representing the ratio of margins between classes. 6 = 1 corre- sponds to (standard) SVM, while luning 6 > 1 (resp. 8 < 1) favors a larger margin 5/ wsl2 for the minority 1/| wxll for the majority classes. Thus, to the decision boundary starting right at the boundary of class = -1 (resp. = +1).
400 (resp. 8- 0) corresponds
Group-sensitive SVM. The group-sensitive version of CS-SVM (GS-SVM), for K = 2 protected groups adjusts the constraints in (4) so that y (w 9 2.) d >> 1, GS-SVM favors larger margin for the sensitive group g
2 6 (or 2 1), if g, = (or Refined versions
when classos are also imbalanced modify the constraints to y: hC h(x,)) ) 2 5g.9. Both CS- SVM and GS-SVM are feasible iff data are lincarly separable (sce SM). However, cantion that the GS-SVM eeper-parameted are in general harder to interpret as "margin-ratios..
3 Insights on the VS-loss
Here, we shed light on the distinct roles of the VS-loss syper-parameters Wy, by and Ay
3.1 CDT-loss vs LA-loss: Why multiplicative weights?
We first demonstrate the unique role played by the multiplicative weights Ay through motivating experiment on synthetic data in Fig. 2. We generated a binary Gaussian-mixte mixture dataset of n 100 examples in R300 with data means sampled independently from the Gaussian distribution and normalized such that |パ-1]|2 2 2 for the minority class +1. For varying model size values p [ 50, 75 25 300] we trained linear classifier (x) = hxx)) using only the first p features, i.e. h(x) x(1 pp:p) e RR.
4. We set prior x, = 0.1
This allows us to investigate performance versus the parameterization ratio y = p/n.. 1 We
train the model w using the following special cases of the VS-loss (Eqn. (1)): (i) CDT-loss
with A. = 6, A_ = 1 (ō. > 0 is set to the value shown in the inset plot; see SM for details).
(it) LDAM-loss: L. = π 1/4 1- = (1- (1-x) -114 (special case of LA-loss [8]). (iii) LA loss:
L. = log 1 ), 1-= log (-=z Wrishhe-consisteer values [32]). We ran gradient descent and averaged over 25 independent experiments. The balanced error was computed on test
set of size 1 and reported values are shown in red/blue/ black markers. We also plot the
Such simple models have been used in e.g. [16, 10, 9, 11, 49] for analytic studies of double descent [5, 38] in terms ofclassification error. Fig. 2(a) reveals a double descent for the balanced error.
4

---

CDT/VS Oe 50/Oan))
Balaneed Tee Emoe
0.4
CS-VM
Trining & Balaned Exrce
0.4
888
LA (Manon al. 200 SVM
LDAM
0.
0.3
0.2
107
0.2
Gip CS SYM
10P
CR/CC//A RVM
0.1
10-2
CDR/VV-lew
0
0.5
10'
10 Inaration: 10"
Medial (TTriining
())
Figure 2: Insights on various cost-sensitive modifications of the CEElloss. (a) CDT has superior balanced-error performance over LA in the separable regime. Also, its performance matches that of CS-SVM, unlike LA matching SVM; Sec. 3.1 for more details. Solid lines follow theory of Sec. 4. (b) Although critical in TPT, multiplicative weights (aka CDT) can harm minority classes in initial phase of training by guiding the classifier in the wrong direction. Properly tuned additive weights (aka LA) can mitigate this effect and speed up convergence. This explains why VS can be superior compared to CDT (see Observation 1). Dashed lines show where TPT starts for each loss. (c) CDT and VS converge to CS-SVM, unlike LA and wCE. We prove this in Theorem 1.
training errors, which are zero for y 2 0.45. The shaded region highlights the transition to the overparameterized / separable regime. In this regime, we continued training in the TPT. The plots reveal the following clear message: The CDT-loss has better bolanced-error performance compared to the LA-loss when both trained in TPT. Moreover, they offer an intuitive explanation by uncovering connection to max-margin classifiers: In the TPT, (a) LA-loss performs the same as SVM, and, (b) CDT-loss performs the same as CS-SVM.
We formalize those empirical observations in the theorem below, which holds for arbitrary linearly separable datasets (beyond Gaussian mixtures of the experiment). Specifically, for a sequence of cont-censtrained minimizations of the VS-loss, we show that: As the norm constraint R increases (thus, the problem approaches the original unconstrained loss), the direction of the constrained minimizer WR converges to that of the CS-SVM solution Wa-/A.
Fir binary braining set (x with al least one erample from each of the two classes. Assume feature map h(-)) such that the data are linearly separable, that is 3w: h.w:"((x;) 2 Vi [n]. Consider training a linear model fx) (ww h(x)) by mindmizing the VS-loss (n(w) == Eis[n] Evs(yt. fxx))) with Evs desoned in (1) for posilive porameters A.: 2 0 and arbilrary 64- Define the norm-consteenn corm-construined optimal classifier wn = arg
Theorem (VS-loss=CS-SVN
(n(w). Let ws be the CS-SVM solution of (4) with
8 = A.A., Then, limg-x wx/ ha/llwll2-- waa wa/llw/ll.
On the one hand, the theorem makes clear that wa and 4 become ineffective in the TPT as they all result in the same SVM solutions. On the other hand, the multiplicative parameters A lead to the same classifier as that of CS-SVM, thus favoring solutions that move the classifier towards the majority class provided that A_ > A. 8 >>> 1. The proof is given in the SM together with extensions for multiclass datasets. In the SM, we also strengthen Theorem by characterizing the implicit. bias of gradient-flow on VS-loss. Finally, we show that group-sensitive VS-loss with Ay.g = Ag converges to the corresponding GS-SVM.
Remark 1. Thm is reminiscent of Thm. 2. 1 in [44] who showed for a regularized ERM with CE-loss that when the regularization parameter vanishes, the normalized solution converges to the SVM classifier. Our result connects nicely to [44] extending their theory to VS-loss / CS-SVM, as well as, to the group-case. In a similar way, our result on the implicit bias of gradient-flow on the VS-loss connects to more recent works [47, 20] that pioneered corresponding results for CE-loss. Although related, our results on the properties of the VS-loss are not obtained as special cases of these eristing works. We remark that, when combined with a recent result by (19), our Theorem also implies that gradiend descent on the VS-loss with sufficienlly small step size converyes in direction to the solution of the CS-SVM. In other words, Theorem 1 characterizes the implicil bias of gradient descent on the VS-loss. As a final note, in Fig. 2(b,c) we kept constont learning rate 0.1. Significantly faster
5

---

convergence is observed with normalized GD schemes [36, 21,; see the SM for detoiled numerical study. We also note that Thm. gives a modern interpretation to the CS-SVM via the lens of implicil bias theory.
3.2 VS-loss: Best of two worlds
We have shown that multiplicative weights A are responsible for good balanced accuracy in the TPT. Here, show that, at the initial phase of training, the same multiplicative weights can actually harm the minority classes. The following observation supports this claim.
Observation 1. Assume fw O at initialization. Then, the gradients of CDT-loss with multipkicative logit factors By are identical to the gradients of wCE-loss with weights wy = Ag. Thus, we conclude the following where say y =1 is minorily. On the one hand, wCE, which typically sels w. > w- (e.g., Wy = 1/TTy) helps minority examples by weighing down the loss over majorily. On the other hand, the CDT-loss requires the reverse direction A, < A_ as per Theorem 1, thus initially it guides the classifier in the wrong direction to penalize minorities.
To see why the above is true note that for Lw (z) = (w,)(x)) the gradient of VS-loss is Vwevs(y, fw (x)) - of Ayyf + ty) yx((x) where (t) = (1 exp(-())- is the sigmoid function. It is then clear that at fx(x)= = 0, the logit factor Ay plays the same role as the weight wy. From Theorem 1, we know that pushing the margin towards majorities (which favors balancing the conditional errors) requires A, A... Thus, gradient of minorities becomes smaller, initially pushing the optimization in the wrong direction. Now, we lurn our focus at the impact of by the start of training. Noting that o()) is increasing function, we see that setting 4, > t. increases the gradient norm for minorities. This leads us to a second observation: By properly tuning the additive logit adjustments by we can counter the initial negative effect of the maltiplicative adjustment, thus speeding up training. The observations above naturally motivated us to formulate the VS-loss in Eqn. (2) bringing together the best of two worlds: the Ay 's that play a critical role in the TPT and the by 's that compensate for the harmful effoct of the Ay's 's in the beginning of training.
Figure 2(b,c) illustrate the discussion above. In the binary linear classification setting of Fig. 2(a), we investigate the effect of the additive adjustments on the training dynamics. Specifically, we trained using gradient descent: (i) CE; (ii) wCE with wy = 1/Ty; (iii) LA-loss with by = =log(1/m)); (iv) CDT-loss with A, 5,=5, A- = 11; (v) VS-loss with A, = 1-- - A.A. by = log(1/mg) and Wy = 1; (vi) VS-loss with same A by 0 and wy = 1/4y. Figures 2(b) and (c) plot balanced test error Roal and angle-gap to CS-SVM solution as a function of iteration number for each algorithm. The vertical dashed lines mark the iteration after which training both
error stays zero and we enter the TPT. Observe in Fig. 2(c) that CDT/VS-lossee converge to the CS-SVM solution as TPT progresses verifying Theorem 1. This also results in lowest test error in the TPT in Fig. 2(b). However, compared to CDT-loss, the VS-loss enters faster in the TPT and converges orders of magnitude faster small values of Roal. Note in Fig. 2(c) that this behavior is correlated with the speed at which the two losses converge to CS-SVM. Following the discussion above, we attribute this favorable behavior during the initial phase of training to the inclusion of the ty 's. This is also supported by Fig. 2(c) as we see that LA-loss (but also wCE) achieves significantly better values of R at the first stage of training compared to CDT-losss. In Sec. 5.1 we provide deep-net experiments on an imbalanced CIFAR-10 dataset that further support these findings.
4 Generalization analysis and fairness tradeoffs
Our results in the previous section regarding "S-loss/CS-SSY hold for arbitrary linearly- separable training datasets. Here, under additional distributional assumptions, we establish a sharp asymptotic theory for VS-loss/CS-SV and their group-sensitive counterparts.
Data model. We study binary Gaussian-mixturr generative models (GMM) for the data distribution D. For the label y E (+1], let क == Pp = +1}. Group membership is decided conditionally on the label such that Vj E [K] Plgg =jly +1} Pa.j: with Σje( Pt,j [ean]ーー 1. Finally, the feature conditional given label y and group g is a multivariate Gaussian of mean py. E Rd and covariance Σ, i.e. x((v.g)
(N E). Specifically
for imbalanem,,, we let K 1 and xly ~ -Ny, Ia) (see SM for Σ La). For group- imbalances, we focus on two groups with p+,1 P-,1 p < - p p-, p-2, j 1,2 and

---

0.25
1.0.5
1-0
02
EVA
balanced enror
c3 5V1
0.15
24
0.1
1.6
0.4
08-SHAKL
6.1
10.5
-0.1
1215--2
0.05
4.1
0 4.1
CS-5HANUU
0.2
misdaasiiication
(a)
(b)
Figure 3: Fairness tradeoffs between classification error and error-imibalance/ aaaaaallaneeeeaaaae balaacedderrrrr DEE
GMM data achieved by (a) CS-SVM for class prior 0.05 and (b) GS-SVM for group prior p 0.05, as a function of the margin-ratio hyperparameter 82 and for various values of overparameterization
y. Plots in (a) are generated using our sharp predictions in Theorem 2. Plots in (b) use corresponding result for GS-SVM given in the SM. See text for interpretations.
x (v,g) ~ (yWp,, Ia). In both cases, M denotes the matrix of means, i.e. M [1+, p-] and M [[ u2]. respectively. Also, consider the cigen-decomposition:: M VS"V"" S Oxxrs V E Rexr,r {1,2), with S an orthonormal matrix obeying VTV-I, We study lincar classifiers with h(x)= x.
diagonal positive-defiite matrix and V an
Learning regime. We focus on the separable regime. For the models above, linear sep- arability undergoes sharp phase-transition as d, n - co at a proportional rate =. That is, there exists threshold 7. == 7 (V.S. s 1/2 for the label-case, such that data are linearly separable with probability approaching one provided that 7 7. (accordingly for the group-case) [7, 34, 10, 22, 26). See SM for formal statements and explicit definitions.
Analysis of CS/GS- AS/GSSSVM. We use - to denote convergence in probability and Q() the standard normal tail. We let (z)- == min z, 0}; I[E] the indicator function of event E; B2 the unit ball in R"; and, = [1,0]]
[0, standard basis vectors in R2. We further need the
following definitions. Let random variables as follows: G ~ (O, 1), symmetric Bernoulli
with P(Y- = +1} = x, By e e = 1] e [[ = -1] and Dy 8. 1 [[ +1] + [[Y = -1],
for > 0. With these define key function V6 Roo x B3 x R + R as 1/8 (,(1,p,)) == [((
Finally, define (gs, Ps, b5) as the unique triplet (see SM for proof) satisfying n6(45, bs) 0 and (ps.bs) ) arg arg Iplast no(96, p, Note that these triplets can be easily computed numerically for given values of 7, O, n. P and means' Gramian M V
B VSp+ q
-
Theorem 2 (Balanced error of CV-S. Let GMM data with label imbalances and learning regime as described above. Consider the CS-SVM classifier in (4) with h(x) x, intercept b (i.e. constraints (x, w) b2 {8 or 1} in (4)) and fired margin-ratio 8 Define R. := Vep'sSpp bx/qs) and R_ == Q-ee VSPs bs/4s). Then, as n, + oo with d/n 7 T,: P
it holds that R,, P, R. and R_ _ R.. In particular, Real - R == (R, R. 1/2.
(gs, by is the asymptotic the intercept, 17 is the asymptotic ic classifier's margin 1/| to the majority, and ps determines the asymptotic alignment the classifier with the class mean. The proof uses the convex Gaussian min-max theorem (CGMT) framework [48, 51]; see SM for background, the proof, as well as, (a) simpler expressions when the means are antipodal (=#) and (b) extensions to general covariance model (Σ + I). The experiment (solid lines) in Figure 2(a) validates the thcorem's 's predictions. Also, in the SM, we characterize the DEO of GS-SVM for GMM data. Although similar in nature, that characterization differs to Thm. 2 since each class is now itself a Gaussian mixture as described the model above.
The theorem further shows (l1l, w ph W.t bb) - (qs, (g VSps, oj VSps, bz). Thus, Twola Twlla
Fairness tradeoffs. The theory above allow us to study tradeoffs between misclassification / balanced error / DEO Fig. 3. Fig. 3(a) focuses on label imbalances. We make the following observations. (1) The optimal value 8, minimizing Rbal also achieves perfect

---

balancing between the conditional errors of the two classes, that is RR (((a)))) prove this interesting property in the SM by deriving an explicit formula for ò. that only requires computing the triplet (g), PI, for 8 = 1 corresponding to the standard SVM. Such closed-form formula is rather unexpected given the seemingly involved nonlinear dependency of Raal on 8 in Thm. 2. In the SM, we also use this formula to formulate theory-inspired heuristic for hyperparameter tuning, which shows good empirical performance on simple datasets such as imbalanced MNIST. (2) The value of ó minimizing standard error R (shown in magenta) is not equal to 1, hence CS-SVM also improves R (not only Roat). In Fig. 3(b), we investigate the effect of 5 and the improvement of GS-SVM over SVM. The largest DEO and smallest misclassification error are achieved by the SVM (6=1). 1). But, with increasing 6, misclassification error is traded-off for reduction in absolute value of DEO. Interestingly, for some 6n = (n()) (with value increasing with 7) GS-SVM guarantees Equal Opportunity (FO) Rdco = 0 (without explicitly imposing such constraints as in [39, 12])-
) We
Experiments
We show experimental results further justifying theoretical findings. (Code available in [1])-
5.1 Label-imbalanced data
Our first experiment (Table 1) shows that non-trivial combinations of additive/muuliilicaane mmultpplicative adjustments can improve balanced accuracy over individual ones. Our second experiment (Fig. 4) validates the theory of Sec. 3 by examining how these adjustments affect training.
Datascts. Table 1 evaluates LA/CDT VVSsssssss on imbalanced instances of CIFAR-10/100. Following [8], we consider: (1) STEP imbalance, reducing the sample size of half of the classes to a fixed number. (2) Long-tailed (LT') imbalance, which exponentially decreases the number of training images across different classes. We set an imbalance ratio Nmax/NNmin = 100, where N Maxx= max, Numn ming Ny and N, are sample sizes of class y. For consistency with [17, 8, 32, 54] we keep a balanced test set and in addition to evaluating our models on it, we treat it our validation set and use it to tune our hyperparameters. More sophisticated tuning strategies (perhaps using bi-level optimization) are deferred to future work. We use data-augmentation exactly in [17, 8, 32, 54]. See SM for more implementation details.
We compare the following: (1) CF-loss. (2) Re- Re-Sampling that includes each data point in the batch with probabil- ity Ty (3) wCE with weights wy = Ty -1 (4) LDAM-loss [S], spe- (Nmii/N,,) is subtracted from the logits.
Model and Basclines,
cial case of LA-loss where by
(5) LDAM-DRW [8], combining LDAM with deferred re-weighting.
Table 1: Top-1 accuracy results on balanced validation set (%).
(6) LA-loss [32]. with the Fisher-consistent
Dataset Imbalance Proffle
CIFAR 10
CIFAR 100
LT-100
STEP-100
LT-100
STEP-100
parametric
choice
CE
71.94
0.38
62.69 0.50
38.52
0.69
39.49 0.16
by = Tlog(TT)) (7)
Re Sampling
71.2
65.0
34.7
38.4
CDT-loss [54], with (8)
WCE
72.6
67.3
40.5
40.1
LDAM R..
13.35
06.58
39.60
39.58
Ay = (Ng//Nmae)
LDAM-DRW [
77.03
76.92
42.01
45.36
VS-loss, with com- bined hyperparameters yy T llgg(T)) TT)) and
LA (T - +") [32]
80.81
0.30
78.23 a 0.32
42.87
0.32
45.69
0.27
CDT (7 (4
79.55 = 0.35
73.26 0.29
42.57 0.32
44.12 0.17
VS ( (')))))
80.82 a 0.37
79.10 à 0.66
43.52
0.46
46.53 a 0.17
A, (Ny/Nmax)), ), pa-
rameterized by 7,7> > 0 respectively 2 The works introducing (5)-(7) above, all trained for a different number of epochs, with dissimilar regularization and learning rate schedules. For consistency, we follow the training setting in [8]. Thus, for LDAM we adapt results reported by (8), but for LA and CDT, we reproduce our own in that setting. Finally, for a fair comparison we ran LA-loss for optimizod 5 == (rather than 7 1 in (32]).
VS-loss balanced accuracy. Table 1 shows Top-1 accuracy balanced validation set (averaged over 5 runs). We use a grid to pick the best. 7 / 7 / (7,7)-pair for the LA
2 Here, the hyperparameter 7 is used with some abuse of notation and is important to not be confused with the parameterization ratio in the linear models in Sec. 3 and 4. We have opted to use the same notation in [54] to ease direct comparisons of experimental findings.
8

---

CDT / VS losses on the validation set. Since VS includes LA and CDT as special cases (corresponding to y = and r respectively), we expect that it at least as good as the latter over our hyper-parameter grid search. We find that the optimal (r", "-paiirs correspond to non-trivial combinations of each individual parameter. Thus, VS-loss has better balanced accucy as shown in the table. See SM for optimal hyperparameters choices.
P=0000 00
=-0p
15
Fw0.20) 20)
bpodss
bpodss
(a) Ay 's (parameterized by 7) can hurt training.
(b) LA trains easier than CDT.
091
Balnnced Test Accunicy
199
Traning Accursty
85
T=0.0
0.0
5
0.5
Epochs
200
240
250 Epochs
203
190
370
180
150
200
220
240
Epochs
202
200
300
(c) by mitigate the effect of Ay's (cl,e2), but Ays dominate TPT performance (c3,c4).
Figure 4: Experiments on CIFAR10 with Long-tailed LT-100 imbalance demonstrating the effects of Anditive/multillice parameters at different phases of training. All results are averaged over 5 runs and shaded regions indicate the 93% confidence intervals. See text for details and interpretations.
How hyperparameters affect training? We perform three experiments. (a) Figure 4(a)
shows that larger values of hyperparameter (corresponding to more dispersed A,'s 's between classes) hurt training performance and delay entering TPT. Complementary Figures 4(c1,c2) show that eventually, if we train longer, then, train accuracy approaches 100%. These findings are in line with Observation in Sec. 3.2. (b) Figure 4(b) shows training accuracy of LA-loss for changing hyperparameter т controlling additive adjustments. On the one hand, increasing values of r delay training accuracy to reach 100%. On the other hand, when compared to the elfect of Ay 's in Fig. 4(a), we observe that the impact of additive adjustments on training significantly milder than that of multiplicative adjustments. Thus, LA trains easier than CDT. (c) Figure 4(c) shows train and balanced accuracies for (i) CDT-loss in blue: = 0, 7 = 0.15, (ii) VS-loss orange: T -0.5, 7 = 0.15. In Fig. 4(c1,c3) trained for 200 epochs, while in Fig. 4(c2,c4) we trained for 300 epochs. For 7 0.15, CDT-loss does not reach good training accuracy within 200 epochs (~ 93% at epoch 200 in Fig. 4(cl)), but the addition of by 's with = -0.5 mitigates this effect achieving improved ~ 97% accuracy at 200 epochs. This also translates to balanced test accuracy: VS-loss has better accuracy
the end of training in Fig. 4(c3). Yet, CDT-loss has not yet entered the interpolating regime in this case. So, we ask: What changes if we train longer so that both CDT and VS loss get (closer) to interpolation. In Fig. 4(c2) train accuracy of both algorithms increases when training continues to 300 epochs. Again, thanks to the by VS-loss trains faster. However, note in Figure 4(c4) that the balanced accuracies of the two methods are now very close to each other. Thus, in the interpolating regime what dominates the performance are the multiplicative adjustments which are same for both losses. This is in agreement with the finding of Theorem and the synthetic experiment in Fig. 2(b,c).
5.2 Group-sensitive data
The message of our experiments on ioup-imbalaaceed datasets is three-fold. (1) We demon- strate the practical relevance of logit-adjusted CE modifications to settings with imbalances at the level of (sub)groups. (2) We show that such methods are competitive to alternative state-of-the-art; specifically, distributionally robust optimization (DRO) algorithms. (3) We propose combining logit-ndjustments with DRO methods for even superior performance.
9

---

Dataset. We study a setting with spurious correlations strong associations between label and background in image classification- which can be cast as a subgroup-sensitive classification problem [45]. We consider the Waterbirds dataset [45]. The goal is to classify images as either "waterbirds' or 'landbirds', while their background either 'water' or 'land'- can be spuriously correlated with the type of birds. Formally, each example has label y E < = [+1] = (waterbird, landbird] and belongs to a group g 5 [+1] = {water, land). Let then
(v.g) E {+1} x {=1} be the four sub-groups with (+1,-1), (-1,+1) being minorities (specifically, P-1,.1 = 0.22, 1-11-11 = 0.012, f-.11.1111111 = 0.038 and f-1,-1 0.73.). Denote N, the number of training examples belonging to sub-group s and Nmax == max, N. For notational consistency with Sec. 2, we note that the imbalance here is in subgroups: thus, Stoup-VS-lose in (3) consists of logit adjustments that depend the subgroup = (v.9).
Model and Baselines. As in [45], we train a ResNet50 starting with pretrained weights on Imagenet. Let f--(1.0) = (N (v..)/
We propose training with the group-sensitive VS-loss in (3) with 4 g.g A, = 33 and 6, = - with 7 0.3. We compare against CE and the DRO method of [45]. We also implement a new training scheme that combines Group- DRDDO. We show additional results for Group-LA/CDD in group contexts). For fair comparison, we reran the baseline experiments with CE and report our reproduced numbers. Since class +1 has no special meaning here, we use Symm-DEO ((R++1 R(+1,-1]+ +R(_1,+1) - R(-1--1)))2 and also report balanced and worst sub-group accuracies. We did not fine-tune 7 as the heuristic choice already shows the benefit of Group- VS-loss. We expect further improvements tuning over validation set.
(not previously used
Results. Table 2 reports test values obtained at last epoch (300 in total). Our Group-VS loss significantly im- proves performance (measured with all three fairness metrics) over CE, provid- ing cure for the poor CE performance reported
Table 2: Symmetric DEO, balanced and worst-case subgroup accuracies on Waterbirds dataset; averages over 10 runs, along with standard deviations.
under overparameterivaliin [46). Group-CDT/ /VS have comparable performances, with or without DRO. Also, both outperform Group-LA that only uses additive adjustments. While these conclusions hold for the specific heuristic tuning of Ly's, 8,, Ay's 's described above, they are in alignment with Group-VS
Loss
Symm. DEO
Bal. acc.
Worst acc.
CE
25.3=00.6
84.9+0.29
68.1+2.2
Group LA
24.0+2.4
84.2+3.0
70.1
Group CDT
18.5=0.46
87.2=1.2
75.4+2.2
Group VS
18.1+0.65
88.1+0.38
76.7.2.3
CE + DRO
16.320.37
88.720.31
75.242.1
Group LA + DRO
16.3=0.82
88.7+0.40
74.3+2.5
Group CDT + DRO
11.7=0.15
90.3=0.2
79.9= 1.5
Group VS + DRO
11.8=0.70
90.2+0.22
78.9+1.0
Theorem 1. Interestingly, improves by small margin the worst accuracy over CE+DRO, despite the latter being specifically designed to minimize that objective. Our proposed Group-VS + DRO outperforms the CE+DRO algorithm used in [45] when training contimues in TPT. Finally, Symm. DEO appears correlated with balanced accuracy, in alignment with our discussion in Sec. 4 (see Fig. 3(a)).
6 Concluding remarks
We presented a theoretically-grouddee study of recently introduced cost-sensitive CE mod- ifications for imbalanced data. To optimize key fairness metrics, we formulated new such modification ion subsuming previous techniques as special cases and provided theoretical justification, as well as, empirical evidence on its superior performance against existing methods. We suspect the VS-loss and our better understanding on the individual roles of different hyperparameters can benefit NLP and computer vision applications; we expect future work to undertake this opportunity with additional experiments. When it comes to group-sensitive learning, it is of interest to extend our theory to other fairness metrics of interest. Ideally, our precise asymptotic theory could help contrast different fairness definitions and assess their pros/cons Our results are the first to theoretically justify the benefits/ benefits/pitfalls of specific logit adjustments used in [24, 8, 32, 54]. The current theory is limited to settings with fixed features. While this assumption is prevailing in most related theoretical works [20, 37, 16, 4, 35), it is still far from deep-net practice where (last-layer) features are learnt jointly with the classifier. We expect recent. theoretical developments on that front [43, 33, 30) to be relevant. in our setting when combined with our ideas.
10

---

Acknowledgments
This work is supported by the National Science Foundation under grant Numbers CCF- 2009030, by HDR-1934644, by CRG8 award from KAUST and by NSERC Discovery Grant. C. Thrampoulidis would also like to acknowledge his affiliation with University of California, Santa Barbara. Oymak is partially supported by the NSF award CNS-1932254 and by the NSF CAREER award CCF-2046816.
References
[4] Code for paper: Label-imbalanced and group-sensitive classification under overparame- terization. https://github com/ orparask/VS-Loss.
[2] Navid Azizan and Babak Hassibi. Stochastic gradient/mirre /mirror descent: Minimax opti- mality and implicit regularization. arXiv preprinl arxi 00952, 2018.
3 Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. L. Rev., 104:671, 2016.
[4] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in lincar regression. Proceedings of the National Academy of Sciences, :17043))30063- 30070, 2020.
5 Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Leurning, pages 541 549, 2018.
6 Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pages 872 881. PMLR, 2019.
[7] Emmanuel J Candès, Pragya Sur, et al. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27-42, 2020.
[8] Kaidi Cao. Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with nabel-listribution-wwwr margin loss. In Advances in Neural Information Processing Systems, pages 1567-1578, 2019.
19] Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterization in model compression: From double descent to pruning neural networks, 2020.
[10] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. arXiv preprint 1XX.:1911100899 2019.
[1] Oussama Dhifallah and Yue M. Lu. A precise performance analysis of learning with random features, 2020.
[12] Michele Donini, Luca Oncto, Shai Ben-David, John Shawc-Taylos and Massimil- iano Pontil. Empirical risk minimization under fairness constraints. arXiv preprint #xXi::100.006220 2018.
[13] Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. On the (im) possibility of fairness. arXiv preprint NYi:16099007253 2016.
[14] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
[15] Moritz Hardt, Fric Price, and Nathan Srebro. Equality of opportunity in supervised learning. ar preprint arXiv:1610.02// 0.02413, 2016.
11

---

[16] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in nigh-dimensional ridgeless least squares interpolation. arXiv preprint arXic:1903. 085600 2019.
[17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[18] Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2029 2037. PMLR, 10-15 Jul 2018.
[19] Ziwci Ji, Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pages 2109 2136. PMLR, 2020.
[20] Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. ar Xiv preprint arX:::8803007300, 2018.
[21] Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via a primal-dual analysis. PMI.R, 2021.
In Algorithmic Learning Theory, pages
[22] Abla Kammoun and Mohamed- Alouini. On the precise error analysis of support vector machines. arXiv preprint arXie:2003. 12972, 2020.
[23] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition, 2020.
[24] Salman H. Khan, Munawar Hayat, Mohammed Bennamoun, Ferdous A. Sohel, and Roberto Togneri. Cost-sensitive learning of deep feature reprosentations from imbalanced data. IEEE Transactions on Neural Networks and Learning Systems, 29(5):3573 3587, 2018.
[25] Byungju Kim and Jummo Kim. Adjusting decision boundary for class imbalanced learning. IEEE Access, 8:81674-81685, 2020.
[26] Ganesh Ramachandra Kini and Christos Thrampoulidis. Phase transitions for one- vs-one and one-vs-all linear separability in multiclass gaussian mixtures. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4020 4024, 2021.
[27] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. arXiv preprint arXiv: 1eet1.60..00 008007 2016.
[28] Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection, 2018
[29] Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X. Yu. Large-scale long- tailed recognition in an open world, 2019.
[30] Jianfeng Lu and Stefan Steinerberger. Neural collapse with cross-entropy loss. arXiv preprint Xrx:::2012.00 085,04 2020.
[31] Hamed Masnadi-Shhraai and Nuno Vasconcelos. Risk minimization, probability clicita- tion, and cost-sensitive svms. In ICML, pages 759-766. Citescer, 2010.
[32] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. ar preprint arXiv:2007.0731. 2020.
[33] Dustin G. Mixon, Hans Parshall, and Jianzong Pi. Neural collapse with unconstrained features, 2020.
12

---

[34] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint arxiv: 1911.014444 2019.
[35] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? arXiv preprint arXiv:2005. 08054, 2020.
[36] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages
3420 3428. PMLR, 2019.
[37] Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051 11-90059, 2019.
[38] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. aix preprint or Xiv: 1912. 02292, 2019.
[39] Mahbod Olfat and Anil Aswani. Spectral algorithmss for computing fair support vector machines. In International Conference on Artificial Intelligence and Statistics, pages 1933-1942. PMLR, 2018.
[40] Yonatan Oren, Shiori Sagawa, Tatsunori B. Hashimoto, and Percy Liang. Distribationally robust language modeling, 2019.
[41] Wanli Ouyang, Xiaogang Wang, Cong Zhang, and Xiaokang Yang. Factors in finetuning deep model for object detection, 2016.
[42] Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlincar learning: Gradi- ent descent takes the shortest path? In International Conference on Machine Learning, pages 4951 4960. PMLR, 2019.
[43] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40) (7(44))22455 24663, 2020.
[44] Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. In NIPS, pages 1237- 1244, 2003.
[45] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst- case generalization. arxiv preprint arXiv:1911.08 2019.
(46) Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparancterization exacerbates spurious correlations. In International Conference on Machine Learning, pages 8346-888 8356. PMLR, 2020.
[47] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 29):222222-225 2278,, 2018
[48] Mihailo Stojnic. A framework to characterize performance of lasso algorithms. Xrxiv preprinl Xrx:;:1303 7291, 2013.
[49] Pragya Sur and Emmanuel J. Candès. A modern maximum-likeelioon theory for high-ddiennsional logistic regression. Proceedings of the National Academy of Sciences, 116(29):145166 14525, 2019.
[50] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan. Equalization loss for long-tailed object recognition. In Proceedings of the TEEF/CVF Conference on Computer Vision and Pattera Recográtion, pages 11662 11671, 2020.
13

---

[51] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pages 1683 1709, 2015.
[52] Feng Wang, Jian Cheng, Weiyang Liu, and Haijun Liu. Additive margin softmax for face verification. IEEE Signal Processing Letters, 25(7):926-993) Jul 2018.
[53] Yu Xic and Charles F Manski. The logit model and response- samples. Sociological Methods & Research, (8)3)28833022 1989.
[54] Han-Jia Ye, Hong- You Chen, De-Chual Zhan, and Wei-Lun Chao. Identifying and compensating for feature deviation in imbalanced deep learning, 2020.
[55] Yuan Zhao, Jiasi Chen, and Samet Oymak. On the role of dataset quality and hetero- geneity model confidence. arXiv preprint arXiv:2022.000 09831, 2020.
[56] Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen. Bbu: Bilateral-branch network with cumulative learning for saig-tilldd visual recognition, 2020.
14


Reviews:
[{"review_id": "Slcw5-jIhom", "reviewer": "Reviewer_jHmz", "summary": "This paper studies the training loss used by neural networks for class-imbalanced learning/group-sensitive. It wants to investigate among two terms, multiplicative and additive, added to the weighted cross-entropy loss, how do they contribute to the class-imbalanced/group-sensitive learning and in what phase. By studying this problem, the paper did some experiments to get some insights and proved the equivalence of the solution achieved by the weighted cross-entropy loss with the additional terms, and the solution achieved by the cost-sensitive SVM on a linear model. The conclusion is drawn that the multiplicative term is more effective than the other one. On the other hand, it discusses that at the initial phase, the additive term may take effect. By additional distribution assumption of GMM model, the paper also derives generalization analysis and the trade-off between balanced error and imbalanced error. Finally, it shows some experimental results.\n\n============\nThank you for the rebuttal. I think the contribution of the paper is that it studies from the theoretical aspect a commonly met problem, and the insights drawn from theoretical studies can be used to design better loss functions.  In this way, I would keep my positive rate for this paper. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is a quite novel theoretical study of the imbalanced loss functions used. While it is intuitively correct that adding both the terms may make the weighted cross-entropy loss better suitable for class-imbalanced data, there are no theoretical studies on this aspect. Specially, the paper provides some quite novel insights from the theoretical studies, that one commonly used term is effective in the end phase, and another one is only effective in the initial phase of training. I believe such a conclusion has practical applicability in designing new algorithms. This paper, as a theoretical study, is significant not only theoretically but also practically. \n\nTechnically, the paper also gives solid theoretical studies. Its claims are well supported by the theorems provided, as well as the experimental results. However, as the authors admitted in the conclusion, this is still far from deep-net practice while its focus is mainly on linear models. While we understand clearly that a linear model is not usually considered as an overparameterization model, the paper still needs efforts to make itself more “deep” from the theoretical point of view. \n\nThe paper is generally clearly written, and there are a lot of discussions about the intuitions/insights drawn from the theoretical studies. On the other hand, it seems that the paper fails to follow the NIPS style. The layout is denser and the citations do not follow conventional form. The paper may need to give a clearer definition of some words used in the introduction, such as “favorable”/”favoring” and “individual mechanisms”. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "ESTSNV44I4V", "reviewer": "Reviewer_Umnd", "summary": "This paper mainly shows two insights: 1) When optimizing in the terminal phase of training, multiplicative logit adjustment is critical. 2) Compared with multiplicative adjustment, additive adjustment can speed up the convergence at the beginning of the training. Motivated by the insights, a new vector-scaling (VS) loss is proposed to exploit the advantages of both multiplicative adjustment and additive adjustment, which is further introduced to group-sensitive settings. What’s more, a generalization analysis of the VS-loss on binary over-parameterized Gaussian mixtures is presented, revealing tradeoffs between balanced/standard error and equal opportunity.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper reveals how multiplicative and additive adjustment methods affect margins and proposes a new loss function which combines the well-known LA and CDT loss functions. Additionally, a further extension to group-sensitive classification is given.\nQuality: Some insights and theoretical analyses are given in this paper, which is instructive but not sound enough. Specifically, to prove the multiplicative adjustment can be harmful at the initial phase of training, this paper claims that pushing the margin towards majorities requires Δ_+<Δ_-, which is derived from theorem 1. However, this conclusion may be improper for the following reasons: 1) Theorem 1 assumes feature mapping h(x) are linearly separable, which is unpractical. 2) according to the existing works, e.g., [1] and [2], reweighting methods could be harmful for the representation learning at the initial phase, thus it is not clear whether we should push the margin towards majorities at the beginning of network training. 3) This paper proves CDT loss function pushing the optimization in the wrong direction when f_w (x)  = 0, which can be inadequate for f_w (x)  = 0 is an extremely special case.\nMore experiments are required to prove the effectiveness of the proposed VS-loss. Specially, experiment results on iNaturalist, ImageNet-LT and Cifar-10/100-LT with imbalanced ratios 50 and 10 are required.\nClarity: This paper is clearly written, well-organized and provides adequate information to readers.\nSignificance: This paper provides some important results including the analysis and the extension to the group-sensitive learning. However, due to the lack of sufficient experiments, it if difficult to compare it with previous state-of-the-art methods.\n\n[1] Zhou B, Cui Q, Wei X S, et al. Bbn: Bilateral-branch network with cumulative learning for long-tailed visual recognition[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020: 9719-9728.\n[2] Kang B, Xie S, Rohrbach M, et al. Decoupling representation and classifier for long-tailed recognition[J]. arXiv preprint arXiv:1910.09217, 2019.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues are found in this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Bww1reFCFP-", "reviewer": "Reviewer_ahC8", "summary": "This paper studies loss functions in deep learning under imbalanced data. It focuses on the training and testing behavior after the training error is zero. It systematically reviews the previous loss functions, builds a connection between various loss functions and linear (cost-sensitive) SVMs, and then proposes a general way to set loss functions that recovers previous loss functions as special cases. It is claimed that this generalization is beneficial in improving the performance in the balanced test set for deep learning under imbalanced data beyond overparameterization. Specifically, the paper analyzes the performance metrics in fair machine learning like balance error and difference in equal opportunity and shows that the combined strategy in the loss function setup is beneficial for achieving more fair results.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The technical contribution is novel and interesting. I do have many questions which I detailed below. However the writing of this paper, I would say, is a bit messy. I also detailed my suggestions below.\n \nOn the technical side, I mainly have the following detailed feedback and questions:\n1. This is probably also due to writing issues but I generally have the question that how the two problems: imbalanced data and group sensitive (fair) learning connect with each other. Focusing on each of them could be a big topic. It turns out that, (at least my understanding is), good group sensitive learning results (when evaluated in those metrics) is a showcase/application of the proposed method. So the latter one is a by-product of a better understanding of the first problem. However, in the intro of this paper, it somehow seems you study the two problems in parallel. So if my understanding is correct, the writing should be changed. Or if my understanding is wrong, please clarify.\n\n2. I am not quite familiar with the literature on connections between different loss functions and maximum margin classifiers. However, I guess one legitimate question is, how the analysis in the linear classifiers generalizes to the deep learning cases. And how useful these theories are. For example, in the analysis, there is a bounded norm constraint, do you also implement this constraint in practice? Why or why not?\n\n3. This paper studies loss functions. My naive understanding is the optimization of these loss functions is all easily implemented easily by back-propagation. However, I feel it’s good to show how gradients or prediction forms would change when you use these losses. One related question is, how are they related to label smoothing?\n\n4. The general form of the loss function is good but also has more parameters. And it seems in the experiments, they are just chosen by grid search (5.1). However, the connection between the proposed loss and the cost-sensitive SVM seems to suggest the loss should be set by user knowledge (after all in CS-SVM), like we penalize mistakes in certain classes more. Can you comment on how to choose those parameters?\n\n5. On the group sensitive learning, an alternative approach is we just train for the performance metrics, which of course can be hard. But how learning from imbalanced data using specific loss functions is connected with group sensitive metrics? Is it connected by a certain way to set the parameters? Otherwise, we just can hope it works but we do not have guarantees or further understanding.\n\n6. The terminology can also be confusing here. There is recent work on multiplicative gradient update in learning, (not in loss functions), so I was confused at first. \n\n7. A final question, how imbalanced data learning differs from balanced data after overparametrization? Did you try your method on balanced data?\n\nI have some feedback on the writing: \n1. I found multiple instances of referring to equations or notations before definition, which makes this paper a bit hard to read. For example, in line 104, equation 2 is only introduced later. In line 88, \\pi_y is not defined. My suggestion is, at the beginning of the paper, you should prepare the reader better but do not try to go to too many details and notations. \n\n2. The order of the content can flow better. I would suggest giving the conclusion and takeaway first and early in the paper before going to details. For example, section 3.1 is inductive, getting from observation to theory. But the observation part is too detailed and the important message is buried after those details.\n\n3. The experimental section is filled with many experimental details, but I feel this paper needs more results and analysis, rather than details. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see the immediate negative societal impact. But as a paper discussing fair learning metrics, I think it could mention the \"better\" learning results on these metrics are not guaranteed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4hr"}, "extra_text": {}}, {"review_id": "BUqdvpDuDXJ", "reviewer": "Reviewer_x1aB", "summary": "This paper investigate the prediction problem under the settings of label-imbalance and group-sensitive. Previous literature propose several methods to solve it, such as weighted Cross-Entropy, additive/multiplicative adjustments on logits. This paper explore the mechanism and effect of these methods, and analyze the relationship to SVM and CS-SVM. It propose to combine additive/multiplicative adjustments to enjoy the benefit of both methods. The experimental results demonstrate the effectiveness of VS-loss which combine additive/multiplicative adjustments.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of label-imbalance and group-sensitive has been studied by some previous literature. This work combines additive/multiplicative adjustments on logits to achieve improvement on balanced error and DEO. The related works is well cited.\n\nThe technical contribution is not very sigificant. But the statement is well supported by theoretical analysis and experimental results. Although the theoretical results is built on the setting of simple data generation process abount Gaussian mixture, experimental result shows that the method can generalize to complex scenarios. I think the author can try to be extend the analysis results to the setting under weak assumption in future work.\n\nThe paper is almost clearly written. However, since the theory is built on fixed feature setting, I am not clear that whether the representation of data is fixed and only the classification layer is trained in the experiements. I guess the answer is yes. It would be better to emphasize it in the experimental section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are addressed in the paper. The potential negative societal impact of the method is not mentioned. It could be better to include it in conclusion section.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has obtained four favorable reviews. The reviewers laud the novelty of the theoretical study of the imbalanced loss functions used.  It is also practically valuable in the sense that it is useful to develop new algorithms. Many researchers would be interested in the result. The AC agrees with the reviewers. 
Decision: Accept (Poster)