An Analytical Model for Overparameterized Learning Under Class Imbalance
Authors: Eliav Mor
Yair Carmon
Venue: Accepted by TMLR ()

Abstract: We study class-imbalanced linear classification in a high-dimensional Gaussian mixture model. We develop a tight, closed form approximation for the test error of several practical learning methods, including logit adjustment and class dependent temperature. Our approximation allows us to analytically tune and compare these methods, highlighting how and when they overcome the pitfalls of standard cross-entropy minimization. We test our theoretical findings on simulated data and imbalanced CIFAR10, MNIST and FashionMNIST datasets.

Published in Transactions on Machine Learning Research (02/2025)
An Analytical Model for Overparameterized Learning Under Class Imbalance
Eliav Mor
moreHaav@mail.tuu.cc..
Deportment of Computer Science
Tel Aviv Univeristy
Yair Carmon
ycurmon wwwwer.
Deportment of Computer Science Tel Aviv Univeristy
Reviewed on OpenReview: https: // openreview. net/ pormff id= 698n tSRF5K
Abstract
We study class-imbalanced linear classification in a high-dimensional Gaussian mixture model. We develop a tight, closed form approximation for the test error several practical learning methods, including logit adjustment and class dependent temperature. Our approx- imation allows us to analytically tune and compare these methods, highlighting how and when they overcome the pitfalls of standard cross-ent ropy minimization. We test the- oretical findings simulated data and imbalanced CIFAR10, MNIST and FNSH datascts.
1 Introduction
Learning from class-imbalanced data is a longstanding and central challenge in machine learning (He & Garcia, 2009; Van Horn Perona, 2017; Buda et al., 2018; Huang et al., 2019). Its importance stems from the fact that in many applications some classes are under-ropresented in the training data, yet we still desire classifiers that perform well these minority classes. Examples include face recognition (Merler el al., 2019; Wang et al., 2018; Deng al., 2019), wildlife conservation (Tuia et al., 2022; Sullivan et al., 2009; Van Horn et al., 2018), medical diagnosis (Mac Namee et al., 2002), and fraud detection (Singh et al., 2022).
Standard machine learning methods are particularly sensitive to class imbalance in the overparamelerized regime", in which the model is capable of perfectly fitting the entire training data. The predominant approach for multi-class classification, namely minimizing an empirical cross-entropy loss, often generalizes very poorly to minority classes. One may intuitively explain this fact by viewing empirical cross-entropy as a surrogate for the population classification error, which discounts minority classes. It. is therefore natural to seek loss that approximates class- balance population error, leading to classical techniques such as re-weighting the losses or re-sampling of the training data (He & Garcia, 2009). However, this intuition and the resulting techniques both fail in the overparameterrzed setting, where the training cross cooss-entopyy loss becomes zero (and hence does not approximate the population error) (Rossct et al., 2003; Soudry et al., 2018; Lyu & Li, 2020) and re-weighting or re-sampling the data has little effect on the resulting classifier (Byrd Lipton, 2019; Fang al., 2020; Xu al., 2021; Zhai et al., 2023).
These observations have led to extensive work methods that modify the cross-entropy objective to improve the performance of overparameterized models on minority classes (Cao al., 2019; Menon et al., 2021; Ye et al., 2020; Lu et al., 2022; Nguyen et al., 2021; Kini et al., 2021; Lin et al., 2017; Cui et al., 2019; Hong et al., 2021; Ren et al., 2020; Samuel & Chechik, 2021; Li et al., 2021; Behnia et al., 2023). We focus on
The 'overparameterized regime" characterizes setting where the number parameters in model significantly exceeds the size of the training set, allowing the model interpolate the training set.

---

Published in Transactions on Machine Learning Research (02/2025)
Common classes weaker signal
Common classes have stronger signal
Less class imbalance
worst worst class error
0.75
0.75
0.75
0.50
0.50
0.25
0.25
0.25
0
0
0.00
10a
'1'*
10a
10c
dimension
dimension
dimension
Maximum margin (MM) theoretical
Maximum margin (MM) empirical
Class dependent temperature (CDT) theoretical
Class dependent temperature (CDT) empirical
Margin adjustment (MA) theoretical
Margin adjustment (MA) empirical
Logit adjustment (LA) theoretical
Logit adjustment (LA) empirical
Figure 1. Illustration of our main findings. We plot the lest error of the worst-performing class as function of model dimension, for the different learning methods we consider. The shaded areas indicate empirical measurements and the solid lines show our analytical approximation prediction. Each panel shows different set of model parameters; see Appendix G.1 for detailed description.
three leading approaches: logit adjustment (LA) (Menon et al., 2021). class-dependent temperature (CDT) Ye et al. (2020), and margin adjustment? (MA) (Behnia et al., 2023; Lu et al., 2022; Nguyen et al., 2021) (see Section 6 for discussion of additional pertinent methods). While LA, MA and CDT are effective in the overparameterized llass-imbalanced setting, they each introduce additional hyperparameters, and is unclear whether one method is fundamentally preferable to the other.
Our contribution. In this work, shed light the failure mechanism of class-imbalanced overparame- terized cross-entropy minimization, and the relative merits of LA, MA, and CDT. To do so, consider high-dimensional (overparameterized) linear classification in a simple class-imbalanced Gaussian mixture data model with varying signal strengths between classes. We focus on learning by applying (stochastic) gradient descent on the empirical risk until reaching loss zcro, which is equivalent to solving a (modificd) margin maximization problem (Soudry al., 2018; Behnia et al., 2023; Kini al., 2021). this setting, we develop tractable analytical approximation for the test error as a function of the model parameters and balancing hyperparamcters. Figure 1 illustrates the tightness of our approximation, well as our key findings:
1. Our model clearly exhibits the failure of cross-entropy ie., the maximum margin (MM) classifier on minority classes. Morcover, our approximation quantitatively shows how class imbalance affects test error, and reveals the failure mechanism of cross-entropy minimization: minority classifier vectors become dominated by noise from majority examples.
2. Our approximations allow derive closed form expressions for near-optimal hyperparameter tuning for MA and LA, and shows that both methods successfully mitigate class imbalance.
3. While CDT is sometimes helpful, there exist problem instances where MA and LA perform well and CDT performs arbitrarily badly, for any choice of its hyperparameters. Moreover, CDT sometimes fails to reach zero training error even for linearly separable training data.
4. Our analysis delineates the combined effect of class imbalance and class signal strength on test error across different losses. Notably, even in our simplified setting, no method universally dominates the other: carefully-tuned LA performs better when the signal strength is either identical across classes positively correlated with per-class sample size, while MA may perform better in other settings.
Overall, we believe that our work provides a helpful perspective on the challenges of overparameterized learning of imbalanced data, as well as a useful theoretical proving ground for new techniques. Going beyond linear classification on Gaussian mixtures. To test whether our conclusions hold beyond the stylized sctting that we analyze, we experiment with non-linear classifiers and a standard class- imbalanced benchmark. More specifically, we study an imbalanced version of the CIFAR10 (Krizhevsky
2MA does have standard name the literature: Behnia et al. (2023) call it "lahel dependent temperature," " La (2022) call "importance tempering" and Nguyen al. (2021) call it "margin scaling."
2

---

Published in Transactions on Machine Learning Research (02/2025)
al., 2009), MNIST (Deng, 2012) and FashionMNNIT (Xiao al., 2017) datasets using either radial basis function (RBF) kernel or fine-tuning a pre-trained CLIP model (Radford et al., 2021). In the kernel experiments, our conclusions hold fairly well: cross-entrope generalizes poorly, CDT fails in certain settings, and our thcoretically-derive tuning of MA and LA performs well. In the CLIP experiments, CDT performs about as well as MA but seems more sensitive to parameter-tuning and our theoredically-derivel tuning for LA performs comparably to standard tuning.
Paper organization. In Section 2 we present the problem setting, data model, and the methods we consider. In Section
describe our analytical approximation for the classifiers learned by the different methods and their test performance. In Section 4 we apply our approximation on MA, MM, LA and CDT, providing expressions for near-optimal hyperparameter luning and comparing the different methods. In Section 5 we report on experiments within our model and beyond. Finally, Section 6, we present an extended discussion covering additional related work, limitations of our study, and directions for future rescarch.
2 Preliminaries
Notation. We denote matrices by capital letters, and vectors and scalars by lowercase letters, We denote the i'th column of A by a,, and we use brackets to refer to specific matrix or vectors entries, i.e. Apyl dsfz] We write ||a|| for the Euclidean norm v, while ||l[e and || denote the Frobenius and & operator norm of A, respectively. We let ((e) denote the indicator of event E.
2.1 Hypothesis class and error metrics
We consider linear predictors that classify d-dimensional features one of c classes. A predictor is parameter- ized by weights W dxe and biases E RR Given input E Rd, it predicts arg max (c) { [w,] T x + b// }.
The prediction error for examples of class is
Err, (W, = Exjy 1 v)]
where = = W x + and (0,(2,1) = [ugarg max; #1te is the 0-1 loss. We also define the worst class error
as
Ertwn (W.b) = max ErT, (W,
(2)
yE(c]
Finally, write the probability of class & obtaining larger score than the true class y
Eir F (W,b) 1> ((wX, 1r) + 1ig (wy, x)) blv)
(3)
and note that
max Erry-sk(W.)) S Errwe (W,b) S max key
Σ ke
Eir Err,,s((W,b) S c. max Err, (W,)).
(4)
2.2
Learning methods
We now formally define the methods that our work analyzes and compares. Given a training set (n,, y6 he(M) we consider minimizing empirical risks of the form
N C (W, = Σ e (W + b.
N
1m1
W. b, where &: IR R2 is classification loss function.
3

---

Published in Transactions on Machine Learning Research (02/2025)
Cross-entropy, MA and CDT. Perhaps the most common multiclass classification loss, cross-entropy is given by
h (2; log Σ 74 Pll
We analyze two modified versions of the cross-entropy loss that aim to improve overparameterized learning over imbalanced data: margin adjustment (MA) (Behnia et al., 2023; Wang et al., 2022) and class-dependent temperature (CDT) (Ye et al., 2020; Kini et al., 2021), given by
2u "M Σ kE(C
"u
(z; = log
by
and godt (o;)(;;))) = log
Σ JE
e 22
respectively. Both losses have per-class hyperparameters {o.) for which increasing ó; pushes the model to prefer class i. The standard approach for selecting these hyperparameters is setting = N,7 and tuning 2 0 (Lu et al., 2022; Kini et al., 2021; Ye et al., 2020; Behnia et al., 2023), where for = 0 we recover cross-entropy.
Equivalent margin problems. For linearly separable training data and for each of the empirical loss functions we consider, gradient descent converges to zero loss, and its implicit bias is given by the solution to constrained optimization problem. More specifically, consider gradient descent steps of the form
W4+1 Wt LW,, and bet1 b. V.Vo be), where
" T7
=
Then, for any p and sufficiently small 17, if l Ema we have Err, (W,,by) '2 where
(mma for all y E [c].
W Wm gma
arg min w WeRexe.bes
|W]] + b11
subject to (wg, - wk) T xs + blool - bMl 2 6g. for all is N and & + ys.
(5)
When = godt we instead have ErI, bi) " Erig (Wede (oat) for all y [c]. where
Wodt godt = arg min
||W]||2 + p|bb12
WeRdxe.
subject to
(wJ, + b(oi)) 5e (wy a; + blj) 2 for all is N and k + ye-
(6)
By,
Substituting 6, for all i [c] into either eq. (5) or eq. (6) yiclds the standard maximum margin scparator, which is the implicit bias of gradient descent for -= gee See Appendix B for more formal statement of these claims, and a proof based on the prior work (Soudry et al., 2018; Ji et al., 2020; Kini et al., 2021). Remark 2.1 (Limitations of CDT). The MA constraint eq. (5) guarantees zero training error, i.e., arg maxyels) ( w x + } yi for all training points (I1, B1)...., (Zn. By contrast, the CDT con- straint oq. (6) generally does not offer such a guarantee. Consequently, for three more classes, optimizing the CDT loss does not always fit all the training dala. Furthermore, for two classes, the choice of 8, and d2 has no effect on the solution to eq. (6). See more details in Appendix F.3.
Logit adjustment. The LA method finds W and b by minimizing the empirical cross-entropy risk, and adjusts the bias vector by subtracting proposal (Menon et al., 2021), this is the "post-hoc" correction variant of logit adjustment. Menon et al. (2021) also propose an "LA loss" for empirical risk minimization. However, we nole that the implicit bias of the LA loss is identical to that of normal cross-entropy; Le., after long enough gradient descent training, it also converges in direction the standard max margin separator. See Appendix B and Kini al. (2021, Theorem 4) for more formal statement of these claims, The standard approach for selecting is setting "|] log N, and tuning 0.
IR ie., replacing b with b-4 c. In the terminology of the original
4

---

Published in Transactions on Machine Learning Research (02/2025)
2.3 Data model
Inspired by Sagawa et al. (2020b); Wald et al. (2022); Kini et al. (2021); Wang et al. (2021); Glasgow et al. (2023); Carmon et al. (2019) we model our data as a high-dimensional Gaussian mixture. Specifically, conditional on the label the input x E Id has the following Gaussian distribution
aly ~ N(
for some M1...., Me E Rd and o > O, where La denoles the unit matrix.
Scaling with dimension. To ensure that the problem we study becomes neither trivial nor impossible to learn as the dimension d grows, we must carefully set its parameters as a function of d. To that end, we choose
a² = and ||lll = Va and (ps Pb) = OVi4j.
(8)
The scaling of |//=11//0²= vd is essential for obtaining non-trivial error as + do with the training set size fixed, while the choice o²d without loss of generality, Assuming orthogonal Pis..re Me facilitates interpretable analytical expression, though potentially some loss of generality.
3 Analytical approximation
This section describes the two key steps in deriving our analytical approximation for the error of different learning methods in our data model: replacing the empirical kernel with its expectation and replacing the score statistics (defined below) with their expectation.
3.1 Expected kernel approximation
The MA and CDT problems we consider (oqs. (5) and (6) respectively) are quadratic in W. and therefore their solutions are of the form wy = Eie(ny Buggs where the optimal . B. IR,, and E R depend on the data only through the N x N kernel matrix (see substitution of wy in eq. (5) at eq. (10))
K K(is] (as, (z))
(9)
Σ 3 T KB: + Ab/
gma gma =
arg min
8 AI....IEER beRE i=1
subject to (3y, - Bx) h; + bin, - big 2 6n for all i N and k * ys-
(10)
The first step in our approximation is to replace K by its expectation EK = llpy. || [(((==))) + o dd(=)) We justify this approximation by observing that, under our dimension scaling, eq. (8), the empirical kernel
concentrates to its expectation as |K -KKKl = 0 Va + (1 Nd max; s:) vlog !) with probability at least 1- d; see Appendix A.2 for proof.
Let {8, } be the (deterministic) values of (Bi, baj}} under the expected kernel approximation. By symmelry of EK, the entries of 3 are identical for examples of the same class. That is, for every j E N, we have 3 ā for some o; E Re. The approximate predictor W is of the form
w Σ āyje where I
Σ x,
(11)
jES,
is the sum of all feature vectors from the i'th class. That is, under the expected kernel approximation, all the data points become support vectors, whose weight depends only on their class identity. To find {ā., bagh in closed form (as we do in the next section) it convenient to express them in terms of the reduced c expected kernel:
ad N;
K (..) == E( (,), N(51((=))) where &, ||
(12)
5

---

Published in Transactions on Machine Learning Research (02/2025)
3.2 Expected score statistics approximation
For zly (Nyy ( and classifier (W,b), b), the prediction errors
b,, = (MM 2 0) and Erry-x =Q
1
(13)
(v) [R.AA]
where Erry and Erry-s are defined in eqs. (1) and (3), respectively, Q(1) (O 1) 1) the Gaussian error function, and, for every i.j E [c]
( (wy wj) My + bbg by and
(wy w:) (wy wz).
(14)
[F:5]
We refer to (2(w), } as the score statistics. See derivation in Appendix A.4.
Applying the expected kernel approximation described above, we substitute (W, with (W, b), where i. Eie(d & and {āz, big) are deterministic. This yields the following approximate score statistics
A X My + b b and g(0) = A X (
cl
where X = [Ti,...,5e E Rdxe and A(r) E Rexe is a matrix whose i'th row is āg - āz.
The second and final step in our approximation is to replace the score statistics plu) and E(0 by their expectation with respect to the training data X, given by
b(v) = EE(M) 10llu,1122 + 114 1 1-b and (( = =ES(0 Aw) (
(15)
σ
with K as in eq. (12) and a!! denoting the y y'th column of A Again we justify this approximation using rancent of measure under parameter scaling eq. (8); see Appendix A.
The expected score statistics z(v) and (()) are deterministic quantities which we obtain in closed form for MA, CDT and LA (sce summary in Appendix E). By substituting them into the expressions eq. (13) we obtain tight analytical approximations for the generalization performance of these methods.
4 Analysis of class balancing interventions
We now apply our approximation strategy to MA (and MM as special case), LA, and CDT. For MA and LA we obtain near-oplimal parameter values with which these methods successfully mitigate class imbalance. In contrast, our analysis shows that MM and CDT may fail catastrophically.
4.1 Margin adjustment and maximum margin
We begin by applying the expected kernel approximation (Section 3.1) to MA, and finding the resulting coefficients in closed form (see Appendix C.1 for proof).
Theorem 4.1. Let Wama Juna be the expected kernel approzimation for the MA predictor eq. (5) with any 8 that satisfies 5, > 0 for all e [c]. Then, for all y [c] we have i. Ei=
ma y
T where,
Σ =
&
b2
6
di N.E.
(((=v)) -2)
1)
E
Ev
and Ima
Ev E
v|
C.,C, (M + p)
(M
using := || 2
ddd N,
and M Ei=
6

---

Published in Transactions on Machine Learning Research (02/2025)
(b Substituting {ar"" Ii [o Ji=1 into eq. (15), we complete approximation for the error of MA. We defer the full expressions to Appendix D.1 and here we highlight key consequences, focusing on the limit d - oc with the scaling eq. (8). To that end, we define for every and å (with the latter possibly depending on d)
Wr (6. p) max lim Errg-s (W (6, p), bms (6, p).
(16)
kØy d=000
lim Er (Wym>,mm is between 1 and c.
By eq. (4) we have that
Err (6,p)
Performance of maximum margin (MM) In the special case = for all i E [c], obtain simple approximation for the worse-class error of the implicit bias of gradient descent on the standard cross-entropy loss, i.e. the MM separator.
No Nk Ny
m Q
p = xc, i.e,, b fixed to 0
Errwe
mmm
(p) = Errwe (1,
ma
(17)
P
eq. (17) highlights a significant. limitation of cross-entropy under class imbalance. Specifically, for any set of signal strengths {&r} we can bring the worst-class error arbitrarily close to 1/2 simply by increasing the sample size of some class & so that Na Ny >> Ny for some class y. Moreover, and perhaps surprisingly, learning a bias parameter (i.e., setting p < oo) using cross-entropy results catastrophic failure (worst class error of 1) in the limit d oo; we validate this observation empirically (and explore behavior for finite d) in Appendix G.2.
The failure mechanism of MM. To gain further insight for why MM can generalize poorly in our overparameterized linear model, consider the expected kernel approximation coefficients āmm in the limit d - 0o and without bias learning (p = (o). Theorem 4.1 shows that in this case we have lim mm = [(k)
[(y=k) -1 1. Therefore, the classifier for class y tends to viy Iy - 1 Eketa Tky where H; Eyes. Ij is the sum of feature vectors with label i. When y is a minority class, i..., N, & N₂ for some class k, we have |ا < || and the classifier uy is dominated by training examples from majority classes, impairing its ability to generalize to new data. In contrast, with MA parameters { we obtain (for p co and d + oo) that visi = 6y Ekeld ŌgT Thus, increasing å for minority classes lets us compensate for class imbalance.
Ncar-optimal 8 values. In Appendix D.1 we derive a set of margin adjustment paramcters that minimize Errwe ma p))
81 12 25 Es + +P)
E arg min Errwe (6. p),
(18)
where we recall that & 11 + odd N. and note that the minimization above is over ö as function of d given the scaling eq. (8). In the limit d + cc, the value of o tends to 1 N, for < co, and becomes proportional to N, at p (Multiplication of 5 by scalar has effect the resulting modcl).
I
The optimal value of Errwe
maxk#y Q
((RNN)) + (.4N.))++((NNN)) (c
p 0
(19)
totez
maxk+y
p 0:0000 00.
2 Ny ++N
We observe discontinuity in P that is due to taking d + oc; in Appendix G.3 we illustrate how in finite d the transition between the two error values occurs for p around vd. However, in contrast to MM, learning bias with carefully-tuned MA is sometimes helpful (see proof in Appendix F.1).
In eq. (17), the case P < no assumes that N₂ # N₂ for some j.k E [c].

---

Sc (we use * instead of superscript to Published in Transactions on Machine Learning Research (02/2025)
Proposition 4.2. Let N1 S N2 S S No and let p xc. 1f 82 S Se then Errwe (0", ,) S mis
Errwe una
(Ó" xc), with equality when 81 = 82 ... Sc- When 81 > > ... > Se then either Errwe (6", > ErTwe (6 oc) or we (6*,)) p) Errwe (ö xc)))) is possible.
4.2 Logit adjustment
Recall that LA consists of performing standard cross-entropy training, followed by shifting the bias vector by -L for some L R.. We analyze LA in our approximation framework by taking the expected score statistics eq- (15) for the MM expected kernel approximation Wmm, Jumm and replacing jum with jmm We defer the full expression for the resulting approximation to Appendix D. 2 and, in the previous section, focus on approximating the worst-class error in the limit d - oo with the scaling eq. (8). To that end, we define
la Err we (1)
max lim Erry- (W (W (p), (mm(()) t). kfy d'+00
(20)
Near-optimal y. for equal signals. Tet & = || +
let M Eield き. and let M M add
1. We
N.
Ev-
show that taking
2 + || [ [M + p]
(21)
25, [M + pl
minimizes Errwe p) over for instances where 52- denote this condition).
Remark 4.3. Prior work (Menon et al., 2021; Kini et al., 2021) recommend setting 4 x log N₁. In contrast, for p (i.c., bias is learned) and at the limit d - co, we have that 1 N₁. We empirically compare these different recommendations in the next section.
Substituting back the by above into our error approximation yields (for general signal strengths).
sy Sy + s2 NT (1M)) 1sy No
Err (c'
max Q kzy
(22)
N'n.k N' 2/ (N₂ N2
+ N2TTRRD NoT
where A Eigy. N₂ and Tay) 2N; + NWsa +
For equal-strength signals, LA dominates MA (see proof in Appendix F.2).
Proposition 4.4. If 81 82 P, we have Errwe (1", .) S Errwe p))
se then (er is monotonic decreasing in p and, for all values of
Discussion Although Proposition 4.4 is limited to the case of equal strength due to technical reasons, we remain interested in understanding whether the LA predictor (using near-optimal parameters for equal strength signals) is superior to the MA predictor (using near-optimal parameters), when the signal strengths are reversed aligned. We investigate this question in depth in Appendix G.9. Our findings in Figure 18 show that for aligned signals, it appears that LA (tuned for equal signals) is still uniformly better than MA without bias, but on rare occasions MA with bias outperforms it. For reversed signals, LA is mostly worse than MA with bias, but there are rare exceptions to this. These findings strongly suggest that LA is uniformly better than MA without bias for aligned signals, line with our additional experiments Section 5. Moreover, we see that the converse is not true. For reversed signals MA is not always superior to LA, even when the latter is sub-optimally tuned.
4.3 Class dependent temperature
Finally, we consider CDT, where for simplicity we focus on the bias-free setting (p= oo). First, we apply the expected kernel approximation and find the CDT coefficients in closed form (See Appendix C.3 for proof).
8

---

Published in Transactions on Machine Learning Research (02/2025)
Theorem 4.5. Let Woot be the expected kernel opprozimation for the CDT predictor eq. (6) with any 6 that salisfies 6; > 0 for all i E [c], using co. Then, for all E [c] we have weght = -i= a where (for
& =11u.11 + o²d
6,6 Σj=1 87
cddt v
((imy)
=
Comparing Theorem 4.5 to Theorem 4.1 (with p= 0), we see that the only difference between a and ag is a factor of 1 that turns into 8y 5. Unfortunately, following through our approximation procedure
Σ 83
reveals that CDT, with any 8, > 0, may fail to mitigate class imbalance, which we formalize in the following (see proof in Appendix F.4).
Proposition 4.6. For any >> 0 and
classes, there erists instance Ni)== for which
lim Er (Wood: .0) 2 2 while d0000
lim Errwe (6", S.
The proof of Proposition 4.6 relies instances with very strong class imbalance; in the next section we empirically show that CDT fails in such settings.
5 Empirical validation
To test observations both within and beyond the scope of our model, compare CDT, MA, and LA in three different setups. First, we test. linear classification (Section 2.3). Second, we consider classification with an RBF kernel over artificially imbalanced CIFAR10 data (Krizhevsky et al., 2009; Cao et al., 2019; Cui et al., 2019) using features extracted from a CLIP model (Radford et al., 2021). Finally, using the same data, we compare MA, CDT and (post-hoe) LA when fine-tuning the CLIP model. We report full experimental details and provide results on additional problem instances in Appendix G.
data generated from our Gaussian model
Loss hyperparameter tuning. We tune each method by sweeping over scalar hyperparameter. In the first experiment, we tune MA and LA using our thcoretical expressions from Section 4, setting 5; (6;)² and 4 = = respectively, and sweeping over 7 and 7 such that value 1 recovers the theoretical tuning and value 0 reduces to standard maximum margin. Tn the second and third experiments we assume equal signals and, following our theory, set 6, = N, for MA and 4 = TN./N for LA; in the third experiment we also test the standard setting 4, = 7 log N,. For CDT (where our theory does not find good hyperparameters) we set 6, N, is standard.
Linear classification with Gaussian model. We begin by simulating three instances of our theoretical model (for d = 10º), with signal strengths that are either (a) aligned with class sample size, (b) the same for all classes, or (c) inversely aligned with class sample size. Figure shows excellent agreement between theory and practice, with our approximation tightly matching empirical performance and our key predictions upheld. Namely, our theoretically-derivel luning parameters (7,7= 1) are optimal; for aligned signals, LA is better than MA with bias, which is in turn better than MA; for reversed signals, the opposite is true. Additionally, both CDT and MM (corresponding to 7, 0) can fail badly, with MM and < oo obtaining worst class error as predicted. In addition to the worst-class error studied so far, Figure 2 also displays our analytical approximation and empirical measurements for class-balanced error and the macro Fj score. Here too we see excellent agreement between the approximation and measurements. Moreover, the best tuning parameters for worst-class perform well under balanced error and macro F; score well. See Appendix G.6 for more details.
Classification with RBF kernel. To test our predictions beyond the setting of our model, we perform RBF kernel classification on imbalanced CIFAR10 data featurized using the ViT-B/32 CLIP model (Radford et al., 2021). We consider two class size profiles. The first standard "long-tailed" exponential profile (Cui et al., 2019; Cao et al., 2019) with 500 examples for the majority class and 5 examples for the minority class. The second has the same majority and minority sizes, but we increase the sample size of other classes to
9

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA (with bias)
werst class eiro
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.25
0.25
0.25
0.25
0.00
0.00
1.0
2.0
1.0
2.0
1.00
1.00
1.00
balanced error
0.75
0.75
0.75
0.75
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
mecra F1 sccorr
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
2.0
Y
Y
Equal signals
Reversed signals
Aligned signals
Figure 2. Worst class error, balanced error, and macro Fi score loss Luning hyperparameter for the different methods we consider and linear classification synthetic data from our model. The shaded region shows empirical results (two standard deviations over 5 random seeds), and the solid lines show our analytical approximation.
CDT
MA
MA (with bias)
worst class etrer
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
1.0
2.0
2.0
0.0
2.0
0.5
Y
Y
Exponential class profile
Modified class profile
Figure Empirical worst class test error vs. loss tuning hyperparameter for different methods we consider and kernel classification two iubalanced versions of CIFAR10. The markers show the minimun error for each instance.
make the theoretically-preett
CDT worse. Figure 3 shows that many of our predictions continue to hold for this setting, most notably the high errors of CDT and MM (particularly with bias) and optimal tuning around =1 Similar experiments on MNIST and FashionMNIST datasets yield results that are mostly aligning with our observations on CIFARIO, see in Appendix G.4.
CLIP fine-tuning. Taking step further, experiment with end-to-end fine-tuning of the VIT-B/32 CLIP model (with zero-shot initialization), on imbalanced subsets of CIFAR10 with different numbers of classes, where à smaller number of classes allows sharper class imbalance. Figure 4 shows only partial agreement with our theory, as CDT performs comparably to MA, and our theoretical setting of LA is slightly better at the 10 class instance but worse at the other two. Nevertheless we note that CDT is much more sensitive to the tuning of y than MA, which opposite to the conclusions of Behnia al. (2023). We also observe that CDT does not converge to training error (see Appendix G.5), corroborating Remark 2.1.
6 Discussion
In this section, we provide an extended discussion of prior work on the implicit bias of gradient mothods, loss functions for class imbalance, and robustness spurious correlations. We conclude by reviewing the limitations of our study and outlining directions for future work to extend model.
10

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
LA (standard)
LA (theoretical)
40
40
40
40
werst class error
30-
30-
30-
20-
20
10
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
2.5
10
20
30
10 classes
4 classes
- 3 classes
Figure 4. Empirical worst class test error loss tuning hyperparameter for the different methods consider and neural network fine- tine-tuning on innasiimbllnceed subsets CIFAR10.
The implicit bias of gradient methods on separable training data. The implicit bias of gradient descent when applied to certain loss functions and separable training data plays a central role in our study, Rosset et al. (2003) show that the regularization path of a family of loss functions (including cross-entropy) converges direction to maximum margin separator the limit of vanishing regularization. Later, Soudry et al. (2018) show that the same limit holds for gradient descent without any regularization, characterizing its implicit bias. Subsequent work generalizes these results to stochastic gradient methods (Nacson et al., 2019) and shows that the equivalence between regularization path limit and implicit bias holds to high degree of gencrality (Ji et al., 2020). We build on these results, as well as an analysis of CDT by Kini et al. (2021), to lie the different loss functions we consider to margin maximization problems, as explained in Section 2.2. We note that the connection between gradient descent and margin regularization extends to neural network models (Lyu & Li, 2020), though there it is more involved (Vardi ct al., 2022).
Properties of margin maximizers in high dimension. Our expected kernel approximation (Section 3.1) effectively assumes that all data-points are support vectors, with weight determined only by their labels. While this assumption may seem strong, the resulting approximate test error provides tight fit to ex- periments even at moderate dimension (see Figure 1). Moreover, the realization that in ligh-dimensional Gaussian models all data points become support vectors is more or less apparent in a number of prior works. Sagawa et al. (2020b) and Wald et al. (2022) implicitly use this property in order to outline a robustness lim- itation of learned data separators. Glasgow et al. (2023) leverage similar property to analyze gencralization error of different data separators. Frei et al. (2023a;b) generalize this property to nonlinear classification of lincarly separable training data. Finally, Wang et al. (2021) give explicit conditions under which all exam- ples are support vectors, instantiating them for a Gaussian mixture model very similar to the one we study, except that the model they consider is basanee and has uniform signal strengths.
Losses for imbalanced data. There is extensive literature proposing and analyzing loss functions for class-imbalanced data, which we now briefly review. There are also many additional approaches to counter class-imbalance such as specialized model architectures, data augmentation, and ensembling, but they fall outside our scope; see (Zhang et al., 2023) for a recent survey.
As previously mentioned, techniques based on upweighting oversampling minority classes (He & Garcia, 2009; Cui et al., 2019) often have limited success when combined with overparameterized models since the implicit bias of gradient descent on the cross-entropy loss is insensitive to these operations (Soudry et al., 2018; Byrd & Lipton, 2019; Lyu & Li, 2020; Zhai et al., 2023; Xu et al., 2021). The focal loss (Lin et al., 2017) attempts to weinh easy examples and focus the model on challenging instances. However, it admits the same implicit bias as cross-cntropy since not class-dependent and has an exponential tail. SMOTE by Chawla et al. (2002) can potentially get around this limitation by oversampling synthetic minority examples, though in separable linear classification the augmentation proposed in (Chawla et al., 2002) will not affect the implicit bias of gradient descent on cross-entropy.
In contrast to oversampling minority classes, undersampling majority classes (He & Garcia, 2009; Buda et al., 2018) is an effective class balancing intervention even in the overparameterized setting (Byrd & Lipton, 2019), but has the obvious disadvantage of ignoring part of the training data. Our analysis clearly demonstrates the benefits and costs of undersampling: for maximum margin classification (i.e., the implicit bias of cross- entr minimized with gradient descent), the approximation equation 17 for the worst class error decreases
11

---

Published in Transactions on Machine Learning Research (02/2025)
when decreasing the sample size of the majority class. In contrast, for well-tuned margin adjustment, our approximation equation 19 suggests that decreasing the sample size never helps.
Several prior works design losses to directly address classification margins. The label distribution aware margin (LDAM) loss (Cao et al., 2019) adds a class-dependent offset to the logit of the correct label, while Menon et al. (2021) propose the LA loss that offsets the logits of all labels and is Fisher consistent, i.e., given infinite data, minimizing it also minimizes the infinity (as they typically do in unconstrained overparameterized classification), either type of logit offset becomes negligible and the learned model again degenerates to maximum margin separator. Therefore, in our work, we study a post-hoc variant of L.A. In the face detection literature, losses that combine logit normalization and margin adjustment have proven successful (Wang et al., 2018; Deng et al., 2019); we believe exploring the connection between such losses and margin adjustment (MA) (Behnia et al., 2023; Wang et al., 2022; Nguyen et al., 2021) is an interesting topic for future work.
error. However, when model weights grow to
Ye el al. (2020) propose the class dependent temperature (CDT) loss to compensate for a minority feature deviation phenomenon, also observed in (Kang et al., 2020). Our analysis suggests that while CDT is sometimes effective at mitigating class imbalance, it also has significant limitations. Kini et al. (2021) propose combining the LA and CDT losses into a single loss called vector scaling (VS) loss and provides a theoretical analysis for the binary case. However, the binary classification loss they analyze is a two-class version of MA, whereas two-class CDT is always equivalent to maximum margin (Behnia et al., 2023). Li et al. (2021) suggest learning the parameters of VS-loss via bi-level optimization.
Finally, Kang et al. (2020) show that losses that yield good classifiers under class imbalance do not necessarily learn good representations, and (Samuel & Chechik, 2021; Jitkrittum et al., 2022) propose losses that directly larget representation learning. Our analysis deals with linear classification and therefore has no direct implications for representation learning. Nevertheless, Kang et al. (2020) show that separately learning the reprosentation and classifier is often effective, and our result can provide guidance for the latter part.
Neural and minority collapse. Building on the notion of neural collapse (Papyan el al., 2020), Fang et al. (2021) and Ji et al. (2021) introduce a "layer peeled model" for neural network training where they identify "minority collapse" phenomenon, which potentially explains the tendency of neural networks to generalize poorly to minority classes. Lu et al. (2022); Behnia et al. (2023) show that MA and CDT can prevent minority collapse.
There are three differences between our results and (Fang et al., 2021; Lu et al., 2022; Behnia et al., 2023). First, our analysis focuses on a linear setting where the representation is fixed rather than part of the optimization objective. Second, we consider multi-class classification under general class size distribution whereas (Fang et al., 2021; Lu et al., 2022; Behnia et al., 2023) consider a special case where there are only two class sizes. Finally-and most importantly-we directly analyze the test performance of different balanced losses, while finding a direct link between neural collapse and generalization is an open problem.
Robustness to spurious correlations. The problem of lcarning under spurious correlations (i.c., signals that appear in part of the training data but not in the test data) has several parallels to class-imbal lanced learning. In particular, cross- eooss-y minimization tends to rely on spurious features, and re-weighting tochniques are not effective in the overparameterized sctting (Sagawa et al., 2020a). Furthermore, loss functions proposed for addressing class imbalance are typically also relevant for balancing different sub- populations in the training data (Kini et al., 2021; Tu et al., 2022) and vice versa (Wang et al., 2022; Nguyen et al., 2021). Finally, number of works use Gaussian models similar to the one we study in order to shed light on how spurious correlations affects generalization (Sagawa et al., 2020a; Nagarajan et al., 2021; Wald et al., 2022).
However, class imbalance is also fundamentally different from spurious correlation. The former is ubiquitous in practice while the latter is often challenging to define, identify and address (Hendrycks et al., 2021; Gulrajani & Lopez-Paz, 2021). Moreover, for overparameterized Gaussian mixture models there exists information-theoretii barrier that prevents any interpolating method (such MA) from generalizing well (Wald et al., 2022); our results indicate such a barrier does not exist in the ilballaeneee setting.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Limitations and future work. The main limitations of our work is the assumption of a very specific data distribution and (to lesser extent) the focus on linear classification. Our preliminary experiments suggest that our theoretical predictions translate well to some non-linear, real-data kernel classification problems, but may be less directly applicable to neural network training.
We identify two potential reasons for this discrepancy. First, our neural network experiments do not involve very long training, while our analysis pertains to solutions obtain after infinitely many steps. Even in our simple Gaussian model, understanding the impact of shorter training, early stopping, and regularization is fascinating topic for future work. Second, prior work observes that losses leading to good classifiers for imbalanced data do not necessarily induce good neural representations, and suggest approaching each task separately (Kang et al., 2020), while Behnia et al. (2023) argues that some losses can produce both good representations and good classifiers in the context of class imbalance. Consequently, future work can apply our approximation method for analyzing classifier-learning methods, or extend our model in order to also capture representation learning.
7
Acknowledgments
The authors acknowledge support from the Israeli Science Foundation (ISF) grant no. 2486/21 and the Alon Fellowship.
13

---

Published in Transactions on Machine Learning Research (02/2025)
References
Behnia, T., Kini, G. R.,, Vakilian, V., and Thrampoulidis, C. On the implicit geometry of cross-entropy parameterizations for label-imbalanced data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Buda, M., Maki, A., and Mazurowski, M. A. A systematic study of the class imbalance problem in convo- lutional neural networks. Neural Networks, 106:249-2555 2018.
Byrd, J. and Lipton, Z. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning (TCML), 2019.
Cao, K., Wei, C., Gaidon, A., Arechiga, N., and Ma, T. Learning imbalanced datasets with label-distribution aware margin loss. Advances in neural information processing systems, 32, 2019.
Carmon, Y., Raghumathan, A., Schmidt, L., Liang, P., and Duchi, J. C. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 2002.
Cui, Y., Jia, M., Lin, T.-Y., Song, Y., and Belongie, S. Class-balanced loss based on effective number of samples. In Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Deng, J., Guo, J., Xue, N., and Zafeirion, S. Arcface: Additive angular margin loss for deep face recognition. In Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Deng, L. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2964:114,4,,, 2012.
Diamond, S. and Boyd, S. CVXPY: A python-ombeddded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):2909 2913, 2016.
Fang, C., He, H., Long, Q., and Su, W. J. Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118(43))e20030) 2021.
Fang, T., Lu, N., Niu, G., and Sugiyama, M. Rethinking importance weighting for deep learning under distribution shift. Advances in newral information processing systems, 2020.
Frei, S., Vardi, G., Bartlett, P. L., and Srebro, N. Benign overfitting linear classifiers and leaky ReLU networks from KKT Conditions for margin maximization. arXim:2303.01400 2023a.
Frei, S., Vardi, G., Bartlett, P. T.., and Srebro, N. The double-edged sword of implicit bias: Generalization (0tr:2303.01566, 2023b.
vs. robustness in ReLU networks.
Glasgow, M., Wei, C., Wootters, M., and Ma, T. Max-margin works while large margin fails: Generalization without uniform convergence. In International Conference on Learning Representations (ICLR), 2023.
Gulrajani, I. and Lopez-Paz, D. In search of lost domain generalization. In International Conference on Learning Representations (ICLR), 2021.
He, H. and Garcia, E. A. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9))1263 1284, 2009.
Hendrycks, D., Basart, S., Mu, N., Kadavath, S., Wang, F., Dorundo, E., Desai, R., Zhu, T., Parajuli, S., Guo, M., et al. The many faces of robustness: A critical analysis of out-of-distribation generalization. In Conference Computer Vision and Pattern Recognition (CVPR), 2021.
Hong, Y., Han, S., Choi, K., Seo, S., Kim, B., and Chang, B. Disentangling label distribution for visual recognition. In Conference on Computer Vision and Pottern Recognition (CVPR), 2021.
14

---

Published in Transactions on Machine Learning Research (02/2025)
Huang, C., Li, Y., Loy, C. C., and Tang, X. Deep imbalanced learning for face recognition and attribute prediction. TEEE trunsactions patlern analysis and machine intelligence, 42((1):278112777 2019.
Ji, W., Lu, Y., Zhang, Y., Deng, Z. and Su, W. J. An unconstrained layer-peeled perspective on neural collapse. In International Conference on Learning Representations (ICLR), 2021.
Ji, 7.,, Dudfk, M., Schapire, R. E.,, and Telgarsky, M. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory (COLT), 2020.
Jitkrittum, W., Menon, A. K., Rawat, A. S., and Kumar, ELM: Embodding and logit margins for long-tail tail learning. ar arXiv:2204.138 13208, 2022.
Kang, B., Xie, S., Rohrbach, M., Yan, Z., Gordo, A., Feng, J., and Kalantidis, Y. Decoupling representation and classifier for long-tailed recognition. In International Conference on Learning Represenlations (TCLR), 2020.
Kini, G. R., Paraskevas, O., Oymak, S., and Thrampoulidis, C. Tabel-imbalanced and group-sensitive classification under overparameterizztion. Advances in Neural Information Processing Systems, 34:18970 18983, 2021.
Krizhevsky, A., Hinton, G., el al. Learning multiple layers of features from tiny images, 2009.
Laurent, B. and Massart, P. Adaplive estimalion of quadratic functional by model selection. Institute of Mathematical Statistics, 2000.
Ledoux, M. and Talagrand, M. Probability Banach Spaces: isoperimetry and processes. Springer Science & Business Media, 2013.
Li, M., Zhang, X., Thrampoulidis, C., Chen, J., and Oymak, S. AutoBalance: Optimized loss functions for imbalanced data. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, Focal loss for dense object detection. In Conference on Compuler Vision and Pallern Recognition (CVPR), 2017.
Lu, Y., Ji, W., Iozo, Z., and Ying, L. Importance tempering: Group robustness for overparameterized models. ar arXiv:2209.087 2022.
Lyu, K. and Li, J. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference Learning Representations (ICLR), 2020.
Mac Namee, B., Cunningham, P., Byrne, S., and Corrigan, O. The problem of bias in training data in regression problems in medical decision support. Artificial intelligence in medicine, 24(1):51 70, 2002.
Menon, A. K., Veit, A., Rawat, A. S., Jain, H., Jayasumana, S., and Kumar, S. Long-tail learning via logit adjustment. In International Conference on Learning Representations (ICLR), 2021.
Merler, M., Ratha, N., Feris, R. S., and Smith, J. R. Diversity in faces. 1rXi::1901.10440 2019.
MOSEK ApS. MOSEK optimizer API for Python 10.0, 2023. URL https://docs. mosek. c0m/10.0/
pythonapi/index. html.
Nacson, M. S., Srebro, N., and Soudry, D. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In International Conference on Artificial Intelligence and Statisties (AISTATS), 2019.
Nagarajan, V., Andreassen, A., and Neyshabur, B. Understanding the failure modes of out-of-distribution generalization. In International Conference on Learning Represenlations (ICLR), 2021.
Nguyen, T., Nagarajan, V., Sedghi, H., and Neyshabur, B. Avoiding spurious correlations: Bridging theory and practice. In NewrIPS DistShift Workshop, 2021.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Papyan, V., Han, X., and Donoho, D. L. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, (0000))446222220 2020.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga; L., Desmaison, A., Kopf, A., Yang, E., DcVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: An imperative style, high-performanee doep learning library. In Advances in Neural Information Processing Systems (NeurIPS): 2019.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P.. Clark, J., et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning (ICML), 2021.
Ren, J., Yu, C., Sheng, S., Ma, X., Zhao, H., Yi, S., and Li, H. Balanced meta-softmax for long- Boigetailed visual recognition. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Roman, V. Introduction to the non-osymptotic analysis of random matrices. Cambridge Univ. Press, 2012.
Rosset, S., Zhu, J., and Hastie, T. Margin maximizing loss functions. In Advances in Newral Information Processing Systems (NeurIPS), 2003.
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-casc generalization. In International Conference on Learning Represenlations (ICLR), 2020a.
Sagawa, S., Raghunathan, A., Koh, P. W., and Liang, P. An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning (ICML), 2020b.
Samuel, D. and Chechik, G. Distributional robustness loss for long-tail learning. In International Conference on Computer Vision (ICCV), 2021.
Singh, A., Ranjan, R. K., and Tiwari, A. Credit card fraud detection under extreme imbalanced data: a comparative study of data-level algorithms. Journal of Experimental & Theoretical Artificial Intelligence, 34(4):571-3) -58,, 2022.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(1): 2878, 2018.
Sullivan, B. L., Wood, C. L., Tlif, M. J., Bonney, E., Fink, D., and Kelling, eBird: citizen-basod bird observation network the biological sciences. Biological conservation, 142(10):2282 2292, 2009.
Tuia, D., Kellenberger, B., Beery, S., Costelloe, B. R., Zuffi, S., Risse, B., Mathis, A., Mathis, M. W., van Langevelde, F., Burghardt, T., et al. Perspectives in machine learning for wildlife conservation. Nature communications, 13(1) 2022.
Van Horn, G. and Perona, P. The devil in the tails: Fine-grained classification in the wild. arXiv:17090011 700.01440. 2017.
Van Horn, G., Mac Aodha, O., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., and Belongic, S. The iNaturalist species classification and detection dataset. In Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
Vardi, G., Shamir, O., and Srebro, N. On margin maximization in linear and ReLU networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Wald, Y., Yona, G., Shalit, U., and Carmon, Y. Malign overfitting: Interpolation can provably preclude invariance. orXiv:2211.1572,, 2022.
Wang, H., Wang, Y., Zhou, Z., Ji, X., Gong, D., Zhou, J., Li, Z., and Liu, W. Cosface: Large margin cosine loss for deep face recognition. In Conference Computer Vision and Pattern Recognition (CVPR), 2018.
16

---

Published in Transactions on Machine Learning Research (02/2025)
Wang, K., Muthukumar, V., and Thrampoulidis, C. Benign overfitting in multiclass classification: All roads lead to interpolation. Advances in Newral Informalion. Processing Systems, 2021.
Wang, K. A., Chatterji, N. S., Haque, S., and Hashimoto, T. Is importance weighting incompatible with interpolating classifiers? In International Conference Learning Representations (ICI.R) 2022.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. 2017.
Xu, D., Ye, Y., and Ruan, C. Understanding the role of importance weighting for deep learning. In International Conference on Learning Representations (ICLR), 2021.
Ye, H.-J., Chen, H.-Y., Zhan, D.-C., and Chao, W.-L. Identifying and compensating for feature deviation in imbalanced deep learning. arXiv:2001.0138 2020.
Zhai, R., Dan, C., Kolter, Z., and Ravikumar, P. Understanding why generalized reweighting does not improve over ERM. In Intervational Conference on Leurning Representations (ICLR), 2023.
Zhang, Y., Kang, B., Hooi, B., Yan, S., and Feng, J. Deep long-tailed learning: A survey. IEEE Transactions on Paltern Analysis and Machine Intelligence, 2023.
17

---

Published in Transactions on Machine Learning Research (02/2025)
Appendix
A Approximation method
A.1 Notation
Training set distribution. We let
Pa (15;
denote the distribution of training set of size N = Eield N₂ containing (for each E [c]) N, examples from class y drawn i..dd from eq- (7), with model parameters given by eq. (8). For dataset {( Vs (a)) Ne[N] Pa (18,, N)) we let St = {i 1/4 k} be the set of indices for training examples belonging to class k.
A.2 Expected kernel approximation
In this section we justify the use of EK instead of K at the limit of + oc. Recall the maximum margin predictor problem defined by:
Σ Bi K3 + pDts)
gum pmm
arg min
BIE.. bERE i==
subject to (3p, - Bx) Th: h: bimn) 1lg 2 1 for all i s N and k & ye-
(23)
Lemma A.1. Given a dataset = ((1,, u))) let E Nxd be the matric of the features X- (rI,...,IIN M [M I be the matrix of the corresponding signal vectors of each data point in X, and G = X - M. Then for every > O with probability at least - 4 (cc+ e)xpp)=t it holds that
t I Smin (GT) s smax (G s 1+
N V d
t Vd
+
(24)
d Vd
ld ||uum|| S /V |
(25)
Lemma A.1 was largely derived from Wald et al. (2022). but in our case obtain different probability factor for the event to occur due to the union bound over c 1 events. For the reader's convenience, we have included the proof again here.
Proof. G is random Gaussian matrix with G ~ (N(Odd-)) hence from Roman (2012, Cor 5.35) it holds that with probability at least 1 - eexpp (xxp(-t//2] /2) eq. (24) holds. In addition, since G is random Gaussian matrix, it holds that Gμ4 ~ W 12 We use a bound on a norm of Gaussian vectors (Ledoux & Talagrand, 2013, eq 3.5) and get that for any t; > O,
P|||Gu|| 4] < 4exp
Specifically, for 4; // A ||ll it holds that with probability at least 1 - 1 eq. (25) holds. Taking the union bound over e + events and using the fact that exxp(=f" 4cxp( -f)) for any t > 0 results proving the desired lemma.
18

---

Published in Transactions on Machine Learning Research (02/2025)
Lemma A.2. (Concentration of features kernel) Given dateset D Pa Nfs,, let X R be the matria of the features X [zi,.... INI and K XXT be the features kernel of X. Then for any > 0, with probability at least 4 (c + 1) exp(-+2/88 holds that
VN++ (VN+ +t2 I vd +
KK-EKK]loo $2
max 8i
d
d3/1
XE(e]
Therefore for any dataset D ~~ Pa (a let K bet the kernel matrin of the feature vectors in D then, limg-ro F[|K - E [K]] 0] 1.
Proof. Similarly to Lemma A.1 Gb.)) (0,, Since GGT ~ W (d- it holds that E [GG]] = 7, then from eq. (24) it holds that
view X G M where G is random Gaussian matrix with
2
|GG IE [GG Illop &
(1+V
1+
N
t
-1
(26)
d
vd
Combining this and eq. (25) we get
K E [K]llpp v |IGGT
[GG ][loppllopp + 2||GM 1lop
N
t
+
-1+2
max |IGM* x||
Vd
a: |||a||
N +1
(vN
+ 1)2
+ 2 max -=|==|
|GM x||
Vd
d
VN +t
(VN- t)2 d
2
+ 2 max x=||=|=1
Vx MGT GM
Vd
VN +t
(VN + t)2
+ 2 max *: +|||=|
(GPD))) (GHT)
Vd
d
VN +t
(VN - t)2
+ 2 max ==|-=111
max iEld
Gp, [13||1111
Vd
d
N +1
(VN + 1)2
+ 2 max rE
Gp lIv
Vd
d
+t
(VN + +)2
IN
2
max max||
d
Vi
rEld]
where transitions (a) and (b) are justified by Lemma A.1, which leads us to conclude the desired bound.
Essentially Lemma A.2 show that under our data assumption, Section 2.3, at the limit of + oo K, converge to EK. This motivates us to substitute K by EK and derive the margin problem in the overparameterized regime. Specifically the approximated maximum margin predictor problem defined by
c
gm pmm-
arg min B.E. BER=
Bi T E|K]3 + pbj Σ
subject (By, 3 [E big. bi 1 for all is N and k + di-
(27)
We continue by explaining why this substitution helps to simplify the optimization in eq. (23).
Proposition A.3. For any pair of coefficients //1)) 2mm associated with points belonging to the same class,
the optimal solution of Equation 27 guarantees that guan is equal to 3mm
a[s]
19

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. Let D1 {(2) 1))l be linearly separable dataset in I& such that for any E [N]
3i My; n4 where TM N (0, TT))
Let D2 be dataset that is composed of the data points in D1 with a different permutation of the data points (within the same class). Additionaly, denote by K(() be the kernel matrix of D, and notice that:
B ( = E (1
Which means that the optimal solutions of eq. (27) under D1 and D2 are identical. Hence, for any pair of coefficients h * z of the same class, it holds that 2 [
Proposition A.3 shows that eq. (27) actually involve only c x (c+ 1) parameters (including the bias) under ex (c - 1) constraints instead of ex N +e parameters with N x (c 1) constraints. This allows us to simplify the optimization eq. (27) and conclude our final optimization problem:
ā mm Jum
arg min
Σ a Kä + pbj.)
01
Kg Ny
subject to (ā, )x)
+by bia]
for all [c] and k + y
(28)
where K is the expectation of the features sum vectors kernel.
= N
Kb
10
i + j
Specifically, denote x; = Ejes, 2j and E 11m112 + a²d then,
)
K = Bi, T.lI = E
Σ
Σ
Iii
Jijz
ViES
SaES.
= E
11s/1 + Σ
Nelnin
+ Σ
Ni(nsss +
Σ
(
JiES, J2ES.
JiES,
$2ES.
J.ES: JoES
11 + E
Σ SiE JaES;
Σ
(n n3a)
(2) N?llmil + Noodd=
were (1) and (2) are justified by linearity expectation and i.dd random samples of gaussian noise. addition Kia)] where # j as the product of two i.i.d random variables with orthogonal signal component.
A.3 Prediction error parameter approximation
Lemma A.4. Let x and y be two independent vectors drawn from N (0, Ia). Then, for any d 2 2, fized Rdd and (0, 2) we have
1
(2, > ||u||| V 2log
< 8,
8
2
IP |||a||2 - al Avd AVdlog
$ 6, and
g
4 z
TP (1r, w\ll > vdlog
s d.
20

---

4vdlog 1 8" Published in Transactions on Machine Learning Research (02/2025)
Note that the last two inequalities sacrifice mid-tail dependence (i.e., depending on log &/ instead of vlog for values of 6 above e vd) in favor of cleaner expressions.
Proof. For the first bound we note that (a, u) N (o. [1(l]]))) and therefore I ([(xz, u)) > 2Q
Tu]l
lh The second bound follows from substituting 0; 1 and log in Lemma 1 of Laurent & Massart (2000), which yields
[1al| <11eIl--d [1al|2-d2 d d= 2 d doog
2 + 2 log 1d,
2 8
and we note that, since d and log are both larger than 1, we have
1 v doog + 2og g s 2Vdlog 2 + 2vdlog 1 g
Let us briefly derive the final bound from first principles. First, let h and & be independent standard Gaussians. Then, for all [^]
< 1,
Be Akz = E [E (e-Mez) | 2z = IB 4
00 1
(1-2²) dz 1- X2
22T
-00
Applying Chernoff bound, we have that for all XE (0,1),
P ((xx v) > 1) s (((rr0))1) = (Eenks) d = = (oR(1->²)~>)
3,, Now pick X = va and note that - -d (1 2) is decreasing in d, and therefore
1 log ( - d - log 2.
2
for every d 2 2. Therefore, taking Vdlogg = t log we obtain
P (1..0)> vālog ) < dooog--oost 8 5
Since (x. ÿ) and -(x, y) are identically distributed, we also have ((r,)) < villgg 2) S G. yielding the claimed bound on (x.
Lemma A.5. (Concentration of v/1) and E(U) Let W, be an approzimate predictor of the form eq. (11)
under data assumptions (Section 2.3). Then for any E (0, 1) w.p holds that
1.5e(c+ + 1)
[1]
u [
(v)
V
2N s, log
8
i=1
and
((()) Pill
3/2
Smax
(v)
(v) [j.k]
6c(c + 1)
S
log
Vd
where
2(())
(v)
N || 112
+
blvl
b1g
(x)))
[
Σ
[t,2]
"
(v)
N2C. and
(2) = dv4l 0apl
(29)
2=1
21

---

Published in Transactions on Machine Learning Research (02/2025)
Σ() then we continue by deriving the concentration bound for each parameter and use the union bound the get the desired result.
Proof. We start by showing that E[ al)) and B|
Recall in the define of )
Σj [aأiه anl (Ti, My) + 1/yl
b[g
(3) [r,5] (T My) + blul blg
Hence,
2j=1 "
[[J]] (Tg kz) + b/yl Up
(v)
E
(2)
E
(1)
رر وy + rījz Myyl + 1lv
[t,J]
2=1
N₂
2 bw
byg
2 [.yl
where (1) holds by definition of Σ2 and since the biases fixed, (2) holds since (14 [(=s} and since
the expectation of the noise vectors is zcro.
Similarly we calculate the expectation of 5(() [Fa]' Recall in the definition of E((0 (1.i)
[ [[ta]]aay aymal (2,,
( (2) [B,s) U.A
(5, Bz).
and the expectation is
E
D
E
[k. (. (5=z Ftc)
(z) (w)
(v)
(
(1)
[i,2] (1,= [6 ēz)1
(2)
Σ
(9) (v) [1.]] Ui [م
NZC. = S:(1)
where (1) is justified by that F, and Ty are random variables with orthogonal mean vectors (when h: * 2). We are now ready to prove the concentration bounds.
Σj= u [[o]
(v) (ā. Pb) + blsl
bbg
"Foo (v) N2 plllyyll 2 + b(o) big
Σj=1 j=1 [.,]
(1)
Nyt + ngg Mb) binl
bbg
(2) (Fx)
N |1 b(o) b1g
(1)
(2)
1
(9) [i]]
(n.z Myy)
(3)
(9)
Ny (m)
1=1
22

---

Published in Transactions on Machine Learning Research (02/2025)
(1) holds by definition of V,. (2) by (1,, =) 11 ((رس)) and (3) since ny N (0,N with N (0, Ta).
Hence we can use Lemma A.4 to bound
e(2)
with probability 1-8 3 as follows:
P [1)
(v)
(0))
1
(1) [6.]
1 2N log
(30)
Moving on to bound
[(0)
S(w)
[1]
(50) [.
(S())
[b,)]
u أا=ة 2
(1)) (2)
[i
(T xx)
[8,=] (3,2 No
(1) (1)
N2C:
==1 k=
[i,= إممر
(1))
(ج Ft.)
+
(v) (v) [جايا [ديراا
(ā .z)
[i,2]] [1,
(v) (v)
NºC..
(31)
Looking left sum of z #
(v) (1) "i, [3 [
[T2, Tx)
(v) (v) [(,s]] [z.k] (N n., NeRu + mx)
==1 x
[j.k] [r,=l (
(v) (g)
(NNg nu) + (NaKk: no) + (12, mk)).
(32)
where (1) holds since (p) my) = || 122 ((==s))
Using Lemma A.4 we can bound each term in eq. (32) such that w.p 33 the following holds:
NN
1
No
(NaMi, ūx) + (Naua, m2) + (x)
VN2==
+ VNSSR
2
log
Vd
3/2 / /mmxx "//d
1
Nmax vd
4
2oo
log
7
7
Moving on to bound the residual terms in eq. (31):
o (o)) (v) Σ
[1,) ( Biel ((ū2, N2E.)
Σ
(1)
(w)
(2N, (M2, + || N.o²d).
(33)
Ria) [iae]
Again using Lemma A.4 we can bound each term in eq. (33) such that w.p - 28 the following holds:
N /8s
N
2N, + || Noo2d
2 log
+ 4
log
s//d
1-3/2 Vinx
/ /max
N Ninx
2 2log
+ 4
log
s//d
Hence we get that w.p 1 (2c +
3 (2c+302
for any i,j E [c] it holds that:
[t.j]
(12)
w 21
(v)
bi.k
(v)
2
3/22 / 9max
3//d
2 log
+
Nmax log
d
2
==1 Am
N 3/2
( Smaxx + 1)
(v)
(v)
2 log
Vd
[k,] u
[.,
7
A=
23

---

Published in Transactions on Machine Learning Research (02/2025)
and
(
1
2
(9) [..j]
2N 2N log )
Vd
where we used = concentration bounds for the case of 2 + k and additional 2e concatenation bounds 2 for the case of k (notice that these bounds also hold for the concentration of o(w) Finally we set 8 [5a[c+1) since 2c + - 1.5c(c 1) and get the desired result.
A.4 The error of the approximate model
We now show the correctness of the expression for Erry-k (W, were W, b is a predictor that is learned under our data assumption (Section 2.3). Then we continue by showing that given predictor of the form of eq. (11) the error of the predictor at the limit of d - can be expressed as a multivariate Gaussian distribution in Re that is defined by the predictor's coefficients {ā=}i=z and the problem parameters. Fact 1. Let æly ((yiioPaa) Then, for any predictor (W,b) that is learned under our data assumption (Section 2.3) and any k + we have
(W = 1- P (N(( [(0) 2 0) and Ew,--x(W,D) = =Q
(v) (EEA)]
where Erry and Erry are defined in eqs. (1) and (3), respectively, Q(() TP(N (0, 1) >> 1) is the Gaussian error function, and, for every i.j E [c]
(wy w Mr + bpg byl
(v) (w, w:) (wy wy).
and
[ (b.j)
where {u(t), E00 are defined as the score statistics of the predictor W, b. Proof.
P Plwwk 2) + bk (wy. x) + by]
P [(wk My n) + by (wy, My + n2) + bby
IP [(w Wy, n) > {wy why Myy) by bx]
IP [N (0, 11ly wxll 02 Ia) > {wy
wk: (by) + by bR]
IP N (O,11a) (wy wk. My) + by bk
σ o11 wkll
= Q (wr - wk. Myy + by bb
(34)
Fllla wkll
Theorem A.6. Let D Pa Pa(ts N.)r=)) be dalaset from Pa N.) as defined in Section 2.3 and W, i be predictor over D of the form of eg. (11). Then,
lim ErT, (W. 1 N (D,,) 20]. d0000
where,
(v) (āylu) [w(y)] N2 1, 12 + (my bya and (1())
c
Σ | a+t=il [ägl=] [
[1]
[F.]]
In addition, the worst class error of W, at the limit of d + ao is lower bounded by:
[āplي] السll N2 |1,1,11112 + blg bi41
max lim Q
max lim Erry (W, lim Errwe (W, b). (35) u.n d
key d=+00 0 / Ei= (āgl)) .m1)) "NEE
d=+00
24

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. Recall that the test error of given predictor W, b of the form of eq. (11) is defined by the probability of misclassifying new test sample (z. y)-
Euly 140- (W, by (x, = [P fv (wx, x) + bba > (iy x) + b101)
(36)
crror
eq. (36) can be rewritten by its complementary event,
Erly [6-1 (W, b; (a, w))] = 1 PP [ak E [c] (Ty, a) + b121 2 (ūKK x.) + ]mn]]
error
accuracy
= 1 P lkk E [c] (MTy - -ik Myy + (ity - (x + 1/oi - Bln) 2 0]
= 1 - P (N (LW)) I(1)) 2 0)
where ((1) and (10) are defined as follows:
(, Tk Myy + b1g bm and
(()
5:(0) [61l
= (10, W/s 1 wzz).
[6]
o
Hence,
lim Exly [co-1 (x, - lim P N (b( (1))), E(() 2 0
d=
From Lemma A.5 it holds that at the limit of d + oo, vlw 2s E [1o0] and Σ & E E[E()). Additionally, since the multivariato-Gaussian distribution is continuous
parameters we get that:
lim (DW (()) 20 [P[=[[(()) k E (w)) 20]
Which leads to the desired results,
[ăyiil dwيy Nyllay/1 + (1g) byn and E
E
(v) [1.1]]
> [a a=]=[[ā Eل|=a N2C.. N
2=1
See explicit calculation for these expressions in Appendix A.3. Additionally, this means that the test error (at the limit of d + oo) of given class y can be lower bounded by the score lima Erry of a single
k # y as follows:
lim Enly (fo-1 (W; (I, v))1 = 1- lim P N 210) (00) 20] d=000
d=000
lim d=+00
P
3i + y N
[/100 Z 20(1))
2 max
lim P N
((()
2 20(0)) (v)
iyy d=+o0
max lim ky d=000
N(0,1)
(n)
Therefore we conclude that the worst class error at the limit of d + oo is lower bounded as follows:
[1lyl1 ā + buul - klw)
max lim Q ky d=s00 ov Eem [āyle]] الم=ةة 2 N2C. )
< lim Exrwe (W; b)
d00
25

---

Published in Transactions on Machine Learning Research (02/2025)
B Implicit bias of gradient descent
In this section, we provide a straightforward extensions of prior work on the implicit bias of gradient descent (GD) to account training the bias parameter (with a separate learning rate), and the MA and CDT losses. We empirically validate these implicit biases in Appendix G.S.
B.1 Implicit bias of cross entropy
Recall the standard definition for the maximum margin predictor.
Wmm. arg min ||W]|i WeRexe
subject to (wy, T x 21 for all is N and k + yc-
(37)
In addition recall the definition of the log-loss objective for multiclass classification.
N
c (W;
(WT x; + bbbiit where e (2; = log Σ EE
e Fla)
(38)
N
1=1
Soudry al. (2018) show that minimizing the log-loss eq. (38) on a separable dataset using unregularized gradient descent with small enough learning rate y) converges in direction to the maximum margin classifier eq. (37). Where gradient descent minimizes L(W) with iterates of the form:
W = - 7/ ((W
Proposition B.1 (Soudry et al. (2018), Theorem 7). For almost all multiclass datasets which are linearly separable (i.e. the constraints in eq. (37) are feasible), any starting point Wo and small enough stepsize n S ml we have
1
((t)
Wmm
lim
[W
[ mm
where lim4- [[]] 00.
Remark B.2. To extend the result of Proposition B.1 to non-homogenous linear predictors, all input vectors Ti need to be extended with an additional 1 component.
We extend the implicit bias of gradient descent for the where the weights and biases are learned with different learning rates n and 1/. Specifically, we show that for any 0 such that p = (#) gradient decent converges in the direction of:
mmm pmm = arg min
[|II p||b11
W BeEx.
subject to (wy, wh) x, + bln) bip 2 1 for all is N and k + ys.
where gradient descent iterates are defined by:
1(++1)=WW w(t) V ((W))) and b(t = b(t) (1),
(39)
and L is defined in eq- (38). In addition denote the concatenation of the weights and biases i.e., adding the bias vector as the last row of W by [W]b].
Lemma B.3. Let > and D (I y be a linearly seporable dataset (t) and b(t) be the iterates of gradient descent 39 with L as defined in 38 with learning rate r) S maxe[|os] and nf 9 for the weights and biases respectively. Then,
W (t)
[
gmm
lim
W (1)6(())]
mm pmm
26

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. The proof of Lemma B.3 is direct result of Proposition B.1. Specifically, we extend each point in
the training set by vp and run gradient descent with of < mmax|| ))= From Lemma B.9 holds that & max [ || --smooth. Therefore, according to the implicit. bias the iterates of GD converge in the direction of
Wmm pmm
arg min weRexe,beR
[| + ||b||2
1 vp
subject
(wy, wx)" TTa 24 +
lll 2
for all S N and & # yr.
vp
Rearranging the bias terms as b, Jpb,, get
Wmm pmm arg min WER
||WI| plli11
subject to (wy, wK) Iz + by. b 2 1 for all i is and k + ys:
which results in the desired margin problem. Furthermore, notice that setting the bias feature to /p (instead of 1) is equivalent to adjusting the learning rate of the biases to " vp r// This equivalence arises due to
the effect of applying factor of vp to the bias terms, resulting in the same factor in the gradient. Thus
p= ②
B.2 Implicit bias of margin adjustment
Recall the definition of the MA predictor:
W Wmma 1
arg min
[W]] + p|1b11
W WeRdxe.bes
subject to (w - wk) T x. + blool
blx) 2 69.
for all is N and & * ys.
(40)
In addition the margin adjustment loss is
"It sjvl c
e (2:0) = log
Σ NiEle]
cv
by
(41)
To oblain the convergence of GD with the MA loss the direction of the MA predictor eq. (40) we reduce the problem standard cross-entropy training margin maximization with rescaled features. Specifically notice that for any dataset {(,,, y)) N it holds that
N
N
N eee (WTTaaT 24:8)
ma ( 2 = Σ log Σ
e
by
=
(42)
jE(c)
where o4 Og:
Lemma B.4. Let p and D y:) be linearly separable dataset (t) and b(t) be the iterates of gradient descent (39) on ((W,b) = N ENNee ema eg. (41), with (8,1 > O, learning rates
82
7) S minke[N] PT, and rf S for the weights and biases respectively. Then,
[a ma
lim +000
(t]b((t)]
[[[
Jmm ||
Proof. We prove this by demonstrating that the itcrates of gradient descent with the log-loss on the scaled features of D converge in the direction of the MA predictor. From eq. (42), we conclude the desired result.
27

---

Published in Transactions on Machine Learning Research (02/2025)
First, extend the data points by factor of vp
and scale each point by factor of L, i.c.,
24
69.
It should be noted that this augmentation alters the upper bound of smoothness for the log-loss to maxie[N] || Consequently, based on eq. (42), Proposition B.10, and Lemma B.3 it is guaranteed 8%
that running GD with 7 I [in ! will converge in the direction of the max margin.
Wmm fmm
arg min WERdxe.bERe
[[ p||611
Fe 8y.
subject to (Wy: - wx)
+
buol
5y, big 2 for all S N and # ye-
(43)
Notice that eq. (43) is equivalent to the MA prodictor margin problem, eq. (40) as for any i E [N] and l + y:
1 (wy, w az 8ys
1
1
b1g 2 1 1 (Wy, wx) T Ja
blnd byj 2 8y,
bg
6gs
Finally, the convergence of GD using different. learning rates for the weights and biases is derived from Lemma B.3. In this case, scaling rates, yielding
24 vp
by 1/6g. does not affect the ratio of the weights and biases learning
n
B.3 Implicit bias of class dependent temperature
To show the implicit bias of gradient descent when using the CDT loss (eq. (45) below), we establish connection between two findings from previous studies by Ji et al. (2020) and Kini et al. (2021). Ji et al. (2020) show that when running unregularized gradient descent on convex, strictly decrcasing loss function f that is bounded below by zero and has an unattainable infimum, it converges in direction to the limit of the minimizer of f in a ball of radius R, as R + xo. Additionally, Kini et al. (2021) show that the regularized CDT loss minimizer converges in the direction of the CDT predictor (Equation (6)). We proceed by presenting the relevant theorems from Ji et al. (2020) and Kini al. (2021), followed by an explanation why the CDT loss satisfies the necessary conditions for the implicit bias of unregularized gradient descent.
Wedt arg min [W]]
WeRdxe
T
Wyg 8y
Wk 8%
subject to
Ij
2
for all S N and & # ye-
(44)
The CDT loss is defined by:
Fill Flul
godt
(z;w) = log
(45)
VEE
In addition,
w x
eo (ddia (1
(W v: loo
51 "i.....,68 WTapp
(46)
vE(c]
Proposition B.5 (Ji et al. (2020), Theorem 4). Suppose f is convex, 8-smooth, bounded below by O, and has an unallained infimum, slep size salisfies S min T[wo - 11
: 3). Consider the gradient descent iteroles
28

---

Published in Transactions on Machine Learning Research (02/2025)
(W2 given by W(t + = W(t) nV)(((()), and the regularized solution given by t R
arg min f(w).
|w
If limm [W u for some unit vector u, then also lim [
W(t)
Proposition B.6 (Kini et al. (2021), Theorem 4). Consider a c-classes classification problem as in eq. (44) and define the norm-constrained optimal classifier
W(R) arg min |
pddt (od I;; ys)
(47)
for positive parameters {6:);=1 > O. Assume that the training dalaset is linearly seporable and that Wedt is
the solution of Equation (44). Then it holds that,
W(R)
Wredt
lim R-200 (R)]E
|
minjeto 8
Corollary B.7. Runniing gradient descent with the CDT loss, using step size 1j < converges in the direction of the CDT predictor, eg. (44), if the limit of the gradient descending iterates
max, x. l and {6.) >
lime-400 W(t) erists.
[W]]
Proof. The CDT loss, is convex, differentiable, minyete] 87 -smooth (eq- (46) and Proposition B.11), bounded below by 0, as scaling the weights by ō does not affect these properties of the log-loss. Consequently, based on Proposition B.5, it holds that the unregularized gradient descent iterates converge in the direction of the regularized solution the CDT loss. Furthermore, by applying Proposition B.6, we conclude that this solution converges to the direction of the CDT prodictor.
max; [ar
To generalize the implicit bias of gradient descent with the CDT loss to eq. (6) (with p and bias), we can use the argument previously described for the maximum margin classifier.
B.4 Implicit bias of logit adjustment
We explain why applying gradient descent on the logit adjustment loss eventually results in the maximum margin predictor with bias adjustment. The logit. adjustment (LA) loss is defined by
(2: = log Σ exp(21g + 40] - 2bo 4wi)
(48)
vElc
Lemma B.8. Let 'D be a linearly separable dataset and denote by Wmm and Jam the mazimum margin predictor on D. In addition let Wla(t) and (t) be the weights and biases of the iterates of gradient descent with logit adjustment loss eq. (39) with C(W,b) EN el yi) on D with hyperporameter E R and n 1F. Then,
W (t)
mm bmm
lim 6-000
[
(ix
ham
Proof. The key observation is that running GD on the LA loss is equivalent to running it on CE with offset biases, i.e.,
n (WT b: log Σ
exp w x + bpj + 40 w. x biy 4ui) (
vE(e
29

---

Published in Transactions on Machine Learning Research (02/2025)
Hence from Proposition B.1 it holds that,
(1) (1) + 2] lim [[ (1) + = t0000 [[ (f)
[ (1)669))))
W |mm
lim
(49)
mm |amm]
where (t)(t) and be (t) are the iterates of gradient descent, eq. (39), with the log loss. that
Additional, notice
(1) +1 lim
(1)
[0|d
lim [[ + +ollo 20000
[[ (1) + +dllF
(1
&|1lF
(W) (1)
lim
[[W1(())) + allF
where (1) hold by Proposition B.1 as limy-soo = [[]]=()])6]))]] = 00.
([W)))))0d(())+o111 exists. This allows us to conclude the desired result
We continue by showing that lim [==0(0)000))]] using limit arithmetics.
(1) + 1111
E [10++
lim
80000
80000
E (t)]2+
Σ (t)l2 (8/+()+++
lim 8-000
Σ == (t)11 (t)
Σi=1 26t (1)44))) + +
+ lim
80000
Σ -i=1 / (1)1 + (1))
Σi=1 26 (1)4g)
+ lim
100
Ei 1/w! (1)l2 (1))
Where (2) holds since is fixed and the numerator goes to infinity. We show that (3) holds by bounding >i 1i (0)gg
Upper bound.
Ei 2b/((()
Σ 2i=1 (1)4g
Σ w! (t) (t)112 + (t))
ΣE (t))
and f-+ 00
lim E (1)4g) 0
Σi= (1))
Lower bound.
miniele 6) Σ i= ( (2) + (t))
Σ S 26th (t)4g) c w! (t)112 + (t))
and at + 00
c miniele (1)4g)
0
[w] (bl
1=
30

---

Published in Transactions on Machine Learning Research (02/2025)
Therefore, by limit arithmetics, if the limit of two scries lim A(t) and lim, B(t) exist then,
lim A(I) B(I) = lim (A (I)... 21+00
x-+00
Thus,
[W))
(t) (t) + lim
(t (t)
[Wmm [mm]
lim 1-00
lim
t-+00
[[ + +]]lF t-000
[[[ (t]]))
[ mmm bmm
a8 needed.
B.5 Helper lemmas for smoothness of analyzed losses
In this subsection we present helper lemmas for bounding the smoothness of cross entropy, margin adjustment and cross dependent temperature losses.
Lemma B.9. Let D = {1r, )= in Rd and let DD' be a dalaset in Rd+1 that contains all data points from D extended by a single coordinate with fixed volue r 2 O. Then, L (W; b) over D' is |N7 + y2 smooth.
Proof. We show this by bounding the Hessian of (W; b)
N 80 (W i3.)
(W;b)
log
e
Plal
log
Σ e iEj
21u)
N 1=1
N
N
se/d
==
Hence,
N
2 72 (W;b)
V2
log Σ 114
N
KE(c]
as 2[y] linear in W and b.
1
N
OC
1
(e*
and
OW
N
Eie(o)
ea
ab..
Eield
In addition,
L
1
" Eiela e ((1=)) Js(m] F
aW
1mm @Wabl
N
(Eie(e e*(1)
1=1
Cce
1
2 Eielo 74 [(==)) 6 N
N
1=1
Eield e+(()
Le
1
rr Eielo 60 4|==1 - e
Bby @WHDI
N
Eiele) ePww)
1
rXajmee Eiclo) 7 ((1=)) rTTismee"
AW WWinm000g 0b10
NV
(Eelto) e*1)) 2
Which means
1 N Σ
2
(W:))
(o(1)) diag 2ia PPTP)
N
31

---

Published in Transactions on Machine Learning Research (02/2025)
where p()) R and (24) R defined as
[
Σ
MM
k < d
e nn 20tb
(() [k]
eel
and (2 =
(50)
(A]
k = d
EjEld e zetbbal
EE|c
Therefore,
N
V L (W;b))lop = =11 Σ
(v()) diag (igg
- -
- P) 1 max
1 + +
(E(N]
needed.
Proposition B.10. Let D = ((,,) villi in Wd and let D be a dataset in R++1 that contains all data points from D extended by a single coordinate with a fized value r 2 O. Further, each data point Ig E is scaled by a factor qs > O. Then, (W:b) over D' is ma 9: (1|=,;12 + r²) smooth.
Proof. Following the same calculation as in Lemma B.9 we get that each entree of the Hessian of (*)(W) has additional factor of of as follows:
N
Σ of (o(()) (a (f)))....,,,))))))) -PT)) V (W:b) = N
where p(o) Rdxx and (xx) R are defined as in eq. (50) Therefore,
N
N Σ a
... - PT PTPPlopp S max o (112;11 + r²)
N
iE(N]
Proposition B.11. Let D = (i) in Rdd and let {6: > 0 then, L (ding
.............. ...., (d..
0) over
D is maxie|M [N] [|=]]] mintee 82
smooth.
Proof. By the chain rule holds that
cce diag 1 51 ..... dc w)) (
1
1
1
= diag
diag 5 ....
W
diag
57 ..... 5z
81
5
Therefore,
1 ... 5e
max
2 ce diag
1lop < W
miniele of
C
Methods analysis
In this section we show detailed derivations for the ă coefficients of each predictor we mention in Section 4. Then in Appendix we use these expressions to lower bound the test-error of each predictor and derive near optimal parameters for the worst class error. The order of predictors we analyze in this section is: MA (Appendix C.1), LA (Appendix C.2) and CDT (Appendix C.3). Notice that MM coefficients can be easily recovered from MA's 's by setting 8 = 1.
32

---

Published in Transactions on Machine Learning Research (02/2025)
C.1 Margin adjustment
Theorem 4.1. Let Wia Jus be the expected kernel approrimation for the MA predictor eq. (5) with any 8 that satisfies d, > 0 for all E [c]. Then, for all y [c] we have uyg
Σ Di=1
a
v D where,
Σ j=1
6 CN..
6y
mA v
de (Li=z) - ))
Ev
and b
Ey
4
NcG:
(M + p)
(M
+
using &: == || + ddd N,
and M = Di=i.
Proof. The approximated margin adjustment predictor is
{ Ji=1 (br "
arg min BER
Σ By T Ka, + pbina
Kwvl Ny
subject to (ay ax)
+ bby bmd) 2 6y for all [c] and & + v.
(51)
where b/yl represents the bias parameter of the y'th class predictor. Recall that:
K
Hence we can rewrite the optimization eq. (51) in its explicit form:
ΣΣ a N + pgjs
Ke=, (6Thh Di = arg min
aERS bER
subject
(aglul ass)) NvE blui 6TK) 2 8y for all
y e [c] and &s # y.
(52)
Next we isolate only of each constraint and assume equality holds:
by avlol NwSu- - [bi biol
(53)
Taking the power of akjy)
(6, [b blil)²
N.S, (8, 2..
[b/b] bn]) 2/1g
(54)
N752
for any pair y +
Let's plug in eq. (54) in the objective of eq. (52):
oi N/G
pbly
N2C,
pbipt
2ia N?E.
(55)
Ulul
s=
y=1
y=1 iz
a alvl N2 + pll
(5s [b0] - b 20010 N.E. (5; v=1 in
[a4g b[al) + N?E F.
E
We continue by calculating the optimality condition for aufz), i.e. Baviel
OF 0:
aF
) +[c 1]aggn) 0.
20yyyl N35, 2N,, [c [c- 1]6,
[c 11bbo)
Σ bis)
daylvl
33

---

Published in Transactions on Machine Learning Research (02/2025)
Which means that,
[c 1|6 [[c []b(y]
Exzy b[N]
ayyyl
Lemma C.1. Let م:m, Ima be optimal for eq. (51) with p > 0 then the sum of biases is zero i.e.,
8pm 0.
Proof. Assume by contradiction that Lemma C.1 does not hold. Then we can use āmaa, 5 to find better solution (with lower objective) than ama, fma follows:
â a and b, 80
mms
clearly,
Σ
6
mm
j=1
We'll now show that 6, is feasible and optimal in contradiction to optimality of āma, Jun. Feasibility For any y and k + y it holds that
K + by be- = [(a
K N
16g 6x) Ny
ma
y
+
[M]
2 8y.
Optimality
2
y Kā + pb = Σ ma
Ka
iuna y
Σ
Juna
1=1
y=1
y=1
jml
Σ y=1
mm
Ka ma y
+
(Gmaa) 2
26ma
jma
1
ima
ima
y=1
j=l
ma
Kama y
+ p
(ma y
2
6
ma
Jim
1
>
Σ
c
y
c
y=1
j=1
j=1
(amaa)
K ma Kama
+
(maa)
2
P
1
ma
y=1
assumption
may y
Ka + P Σ
imma "
y
y=1
9=1
In contradiction to optimality of mm Jma
From Lemma C. holds that case p > then Jua must satisfy iga always take the optimal biases Jua and normalize them (by subtracting constant from all the biases)
EK Lma. In case p = we [R]
34

---

Published in Transactions on Machine Learning Research (02/2025)
similarly Lemma C.1 and get that bym E k [k] Hence, add this as "implicit" constraint to the optimization problem and get that eq. (55) can be simplified as follows:
[c 116y cbiol
(56)
cNuCv
Continue by plugging [yl in eq. (53) to conclude (ss(s)
by ax(v) No [P(M] bald
NyLu
6y --- الااا NoSu 1i
cNuLu
8y + cbil
(57)
cN
Now all its left is to find a set of biases that satisfy the optimality conditions Let's plug in andi
(E [lg]
0).
and
Oviyl in F:
2 plul N255
pbl +
2
N.C.
y iz
[c- 1] 2cbjul (e- 1J8y + c2
68 + 2cb + (c00
N2S, + pbo
+
Σ
N?E.
2223
e N2??
==1
y=1 itu
[c- 11208 wcblylc - 1 + c22
07 + 2cb1o) di + c22bg
+ pbb [vl
2v
ci
1= k
Moving on to calculate
Of and find ima.. bl
OF 2/c 1]6, + 2cbjul
25;
2by
0
cly
ch
c
(
Denote & = II E then,
aF
-cc 1-1885y + cb(m) [1 + PEylEp + Σ
8,E, +
b(u)
Σ
c5. - 0
aby
it
which means
cc- 1c-1 Eity fma
Ei=
4
Ey
(58)
Eiin +p)
<i M p)
Finally, let us plug in eq. (58) in eq. (56) and oq. (57) and conclude
plc 1)8, Eity & [[c 166, + 8.1
a [
(59)
cN + p)
and
pōy
+ t 1)44
+ Σe=
8y-8
ma ('Ey)]
Ex
E:
(60)
c., cN M p)
Which yields:
Σラ=1 b 5n
6;
((i=y) 1
Es
Ev
N:E:
c
cN..((M + p)
where M = Di=1 g.
35

---

Published in Transactions on Machine Learning Research (02/2025)
C.2 Logit adjustment
As explained in Appendix at convergence of gradient descent LA converges to the maximum margin with bias adjustment of Thercfore its ā and b are the same as MM with bias adjustment of -1. From Appendix C.1
(1=y) - 2)
Σj=1 1
1 E Ev
Σ Ey C
y|
N
cN p)
and b
M
M+
by
(61)
where M = Σ 2i=1 5
C.3 CDT
Theorem 4.5. Let Wodt be the expected kernel approzimation. for the CDT predictor eq. (6) with any 6 that
satisfies 6, > 0 for all E [c], using = co. Then, for all y E [c] we have iight = Di=1 v/1
godt T where (for
& = =1:111 + o²d N.
6z NG
6,6 Σラ 87
cdit á vf
|
Proof. Recall the expected kernel approximation of the CDT predictor at oc (learning without bias):
{a
(oodtic
arg min
Σ
ay
Kay
y=1
T
K [vl
subject to
ay 8y
akk
2
for all E [c] and + y.
(62)
Ōk
N
We repeat the same analysis as (C.1).
First explicitly write the optimization problem:
{a 1 = arg min
ΣΣ i=
big
N?
(63)
aER
(Qy/v)
antyl
subject
NyCo 2
for all y E [c] and + y.
8y
ds
Next we assume the constraints are tight and gel:
6y0n avlv) -VEy
-kkppl
(64)
Ny
Plug in eq. (64) in the objective of eq. (63):
min
o
N?
min
N?C + ΣΣ
T N2E.
1=1 us
878 28.5 ox wayl NyS,, + 02 N3N3
min
0 |
N?E
Σ
836
484
min F(a).
36

---

Published in Transactions on Machine Learning Research (02/2025)
Moving on to calculate the optimality condition of F for Oyylo]
OF
2ox
Σ 0z
0 No + 2
Alvl 0g N2
Eizy 8,
Nい Ei=1 8,
Denote
Σ 8 and A =
8
Then
A 1 by
6,
cdt vly]
and
cdtt y[d
(65)
A N
N
where gedt (lg)]
was obtained by plugging
aedt
in eq. (64). Hence vvill
5y0
sddt d yli
N.C:
Which means we find solution that satisfy the constraints and the optimality condition and due convexity this is sufficient to know we find the optimum.
D Error approximation
In this section we show how to use the ā and expressions of each predictor (from Appendix C) to derive the error score parameters. Then for MA and LA we use the error expressions to derive near optimal parampaarssters for the worst class error. The order of predictors in this section is: MA, MM, LA and CDT.
D.1 Margin adjustment
We show the derivation for plv) and (()) using the optimal solution of the approximated margin problem, eq. (51).
6,
6g
by 5 5v
8; N,E,
((i=y)
5 Ex
and
ma
Di=1
E.
.N..2 (M + p)
cMM + p)
Therefore,
6; NiC,
A N:E: (M + p)
ma ['
(1(i=v) ((i=k)) +
and
A (M + p)
Jan
Jma-
where
6%
6y
A
and
M
Ek
Ey
E.
1=1
37

---

Published in Transactions on Machine Learning Research (02/2025)
Consequently eq. (29)
Σ E|p
Σ
(ama ma n[1
ma
(a
ma N²
dx(i))
(x((t)
1
ARRM
(B B(w,))) un)
M + p
(M + p)
where
ARt, Σ 80 (Li=y) ((i=k)) (1(=y)) - ((==k))
8²
"
+ 0z
(k==))
Ey
E
d;
by
BlaAM= Σ &
((izz)) (((=))) AN
DK
A BWN
Ey
Ek
CRRAY = Σ A = MARAE.
Substituting back, have
82 0
2
M
[KK
[k=
A&DR
Ey
&k
M +
(M p)²
82
62
M + 2p
6x
by
by
[R=
Ey
(M + p)²
Ex
Ey
Ex
8
6%
[(k=k(} + t.kkw(p)
(66)
Ey
En
Now look at p(n), from eq. (29):
(
(v)
1
((03))
No 1111
iym 8mm
(1)
sy Ey
8y
+ Φ (p)
(67)
where,
6 (m) (p)
By
vd
A (M p) and (p) = (M p)²
M + 2p
88
ōy
Oe 8g
=
Ey
Ex
Ey
Exr
Ew
(1) holds since
Vd and 1|,/|12= S Therefore,
=Q ) 8y N, + Imma (p)
lim Erry Erry-s Junn) d
(89NN 82.42 (g
where 83 = limo-roo dz.
Remark D.1. The expressions for the maximum margin predictor are obtained by setting d; = 1.
Recall that the lower bound for the worst class error of MA is defined by:
ma Errwe (ō,
max lim Err,- (W (W/ma( (8, p), Jm p)).
kæy d=
We now continue by showing how find ncar-optimal margins for promoting fairness by the MA predictor.
Near optimal margins.
Theorem D.2. For any dataset D ~ P ((s N: it holds that
E
arg min Err (6, p),
| + 2(M + p)
38

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. We would like to find set of margins that minimizes the worst class error, eq. (2). To do so, we are looking for a set of margins, {6:) that minimizes the lower bound of the worst class error at the limit of + 20. To find such margins we would have analyze Errwe (6, p) at finite dimension, d, since the order of limits of p + oo and d so matters.
dk Eo + (A + Pp] + vd
fy Ey
Ak Eu
min max Q kzy
Lk Ex
+8 [ar
( +ōu [M+++)))
6y
2 Mink
4v
Eo
Eu
where M = Eitu &
By the monotonicity of the Q-function this equivalent find a set of margins that maximizes:
6= + by (M's + p) vdl +6 [ar + (ou
dz
&k o))
Ex
Ex
max min min 8
(68)
y
usk
+6
Ay
Mirk
+
We start by explaining why d (that satisfy eq. (68)) equalizes each oy dr dependent pair:
8y 6k
+ 5y (Mr'y + p)
6y
5x =
5k by + de (MA + +)) + vd E
òx
6y
+ vd
(69)
Ey
Ek
Ey
&
EL Ey
Ey
Remark D.3. Notice that denominator of eq. (68) is symmetric for y and k, hence we can analyze the numerators.
First note that there is always set of positive margins that satisfy eq. (69). Let 6f & and plug in 8y 8/ in eq. (69).
8
(MW++) +D) + vā(o,, 5%] = 8k6g + sno% (M + + vd(5% -8]]
+ S [
(70)
E,
&s
Let 6y = Ex
=
8y = I and substitute in eq. (70).
o (/' + p) Va(o", - 1] = skd
sy
+ 8 (M +0) + vd[1 -8y]
Ey
&e
Which yields:
sx(M + p) + +2/
8g
8
Ey
sy(M + P) +2d
8x
E
EN
In addition, 8, > 0 since:
2vd
8y
8% (1)
2v d
Vd
Vd
> 0.
Ey
E
+
Vd
Va No
Nv
5 N. Note that this set of margins is not necessarily feasible for the case of <>> 2 (multiclass). However, we later show that we can make ö, depends only on its parameters which is asymptotically optimal. We continue by showing that the error term of the y'th class is monotonically increasing in 8, and that the error term of the k'th class is monotonically decreasing in 6 which means that the optimum of eq. (68) is obtained at the intersection of the error term functions. We start by rearranging the term inside the Q-function of eq. (68) follows (for & and 8% as described above):
where (1) holds since & = || o3d
N.
8 + P) [Va
E, 2/118' 1111-11 1]
(Mive]) + (St+ee(Mr++o])) 5
+ (1 - (8,) 2
En
39

---

Published in Transactions on Machine Learning Research (02/2025)
Let f(6)) and o(8)) be defined as the functions of the ky. 6x dependent terms as follows:
S p) + Vd 10' 11-1] 1]
(1)))
(6%)
(1+6,e ( Ey + (06+ee (Ni+++))** + (1 86)"''1 Mii
1(())
and,
sM(M - p) Vd
26 [1 -1-)
91 (6%)
g(%))
Ek
(66
(
+ (1 (1-8))² 2 Mrru.
k(g))
Ex
Et
Starting by looking at the derivative of h(8)):
((8)) = (1 + 8 80 [MW + p]) (6, + Ex [MV k x])²
-1/2
+ +(1 (1-8)) 3 2
x
Ev
&
(1+ ( M + pl) [AN' + +0]
(6, + Ex MM pP] (1- 8y M luck
Ek
+ +(1 +1--8') (0)) AM Miru (1 + 8 50 MW + p])² (6' + Ex [M + p]]
-1/2
En
EN
20
(1+8/60 Miv + ol) / + o] + (8' + ExP)
1 + 20
+ 8yM
E
Ev
Therefore h is monotonically increasing in 5y We continue by showing that fi and 92 are monotonically increasing and decreasing in 8, respectively.
s, +) + Vd
$y
(
and
2
(((6)) Vd
Ek
(*) for large enough d, which means that and are monotonically increasing and decreasing in 8, respec- tively.
Therefore, the optimal must satisfy eq. (69) which obtained by
s (M + p) + 2/d
Sy
5t
E, Ea
and 8% =1 1.
s, + p) 2
Sy. 5%
Ey
E
In order to make it symmetric we can multiply both deltas by (c(M)))22Z
and obtain
zk
1
8 SM p) 2
and 8%
86 EL
(M + p) + 2 d
8k.
Ev
5u
40

---

Published in Transactions on Machine Learning Research (02/2025)
Which means that:
Ey
Ex
and 0%
(M
(MM+
2vd
2v de,
2v dE
2vd
2vd5, 2v
Since oy can not be dependent on & and sy for all the classes ko * y we neglect the 2vde, 2v
Py "e factor. This valid since when looking eq. (68) at the limit of d + oo the only term that affected by this
factor is vd
(in any other case this factor vanishes). Additionally notice that when we plug in 8*
6x
Ex
in vdl
6 8
6
we get:
Eo
d
8
b
vd
1
5y
Ex
+ 1
(M(
+ 1
By
2/d
2/d5,
2/d
2vd
2v
2v dv
Vd
(M + p)
+1 Sy
Sy(M + p)
+
8y
+
Sk
2vd
2vdG, dey
2Vd
2vd
2v dEv
2v dE
8M(M + p)
(M p)
Vd
2vd
2vd
Which is essentially the same expression that is obtained for
6, = 1 12 + 2(M + p)
Sy
Therefore, at d the error terms of dr and 8 converge to the same value and
E | 2 + 2 + p)
E arg min ErT, (6.p).
Following Theorem D.2 we evaluate the lower bound of the worst class error of MA at 8* when p = 0o and p i.e., a predictor without and with bias respectively. Recall that
lim Errg-> (Wmm Jus = =Q ( N 8, + 3 (p) d0000
60N NR. (2T2(()
where
8x
HTTH (p) =
$y E,
Ev
and mm (p) + 2p
6k
6y
6x
8y
M
(M + p)²
Ex
Ey
EN
Ex
Notice that for p oo it holds that:
TTT (00) = 0
K (oo) 0 and lim Err, B Jima) = Q
d-+00
+
N
For the case of < oo we get when looking at the error term at finite it hold that: E, N [Ay 3 +2(M+p)- + (x(p)
Ny +
Ek ||ax 11M=)=+((MM0)- ) No + tbb(((p))
111 2
+ x
By N₂
Vdl
(M + p)
+2(M+t)
+2(M+t))
3. +2(M+
3 -
2
+ + +
2
N₂ +
No
M42p (M+p)²
+2(M++))-
3 +2(
3 +2
3/ +2(+)+)))
41

---

Published in Transactions on Machine Learning Research (02/2025)
which results at the limit of d - in
By + 8k
2 Ny + No
Corollary D.4. We have
max
Q
Vo ( (0fNN2)
p
Errwe (6", p)
(71)
maX Q
ty+
p oc.
2/ No +NN
As in eq. (71) get discontinuity in p at the limit of d - empirically investigate this in Appendix G.3 by testing the effect of when d is finite.
D.2 Logit adjustment
As we explain in Appendix B running gradient descent with logit adjustment is equivalent to running gradient descent with cross-entropy and post-hoc update its biases. From Appendix D.1 it holds that the approximated maximum margin ((v) is:
1 1 L4 Ex
M + 2p
( 1
2
Ey
(M + p)²
&k
Ey
Exr
On the other hand, when adjusting the biases by factor of we get:
(v)
- ((a
mun amm dljl)
8ym jm
1|yl + 11t))
Ex 5/) + NyS, (M pp)
Vd Ek 5. + (1iv) - (p:) (M + p)
= No Ny
(M+
Corollary D.5. Let Wmm From be the marimum margin expected kernel approzimation and let 11.... bo be addiline factors for the predictor'ss 's biases:
[
44
Then for every y + k E [c],
Sy + (p((e)
lim Err, (Wmm Blu) = =Q
d00
/N,, + No + Jm (p)
where,
( By - Vd) -Vdd
Ev -x-)
(1)
-1)
(p)
vd((p) -4m)
M +p
Ex E
M 2p
(1
1
VK (p)
(M p)²
Ex
Ev
Ex/
Ev
Recall that the lower bound for the worst class error of the logit adjustment predictor is defined by
Err (v, = max lim Err, + (Wmmm (p), fm (p) 1).
kg d-+00
42

---

Published in Transactions on Machine Learning Research (02/2025)
Near optimal hyperparamcters.
Theorem D.6. For any dataset D P ((s; N=) such that the signals are within equals strength || Va. for some posilive 8 E R, then it holds that
2 M
M Pl] 2g M +
"
arg min (t)
Proof. Similarly to analysis of MA, since the order of limits of p and d + matters we investigate the lower bound of the worst class crror at finite dimension. Recall that:
+ M + p) vdl
11
Vdllx b + p)
Erry- (WMM, bLA) = Q
Ev Ex
Ev
Ex
Mw++o))
[MM +p))
( +t2 M Mise
Ev
EN
(+) in case that the signals are within equal strengths.
M
p
Vdl
+ Valux
-yll + p]
Ev
EE
Ex
Ek
E arg min migmmma
Q
(72)
MM++p]
[M+++p)
1 M wvkk
Ev
By the monolonicity of the Q-function it holds that finding an that minimizes eq. (72) is equivalent to find that maximizes:
1 M + p] + vdl 1
Ev Ex + Vdlle -WI[MM + pl
Ev
Ek
E arg max min M.key
(73)
[arv+e)))
(2) (2 +ar++++++))*
+
+v)
Mrr.
Ey
Similarly to MA analysis we show that the iota that maximizes the minimal term in eq. (73) is the one that makes each by: iR dependent terms equals.
1
1
M
MM
+
p
vd
Vdlu 'ol[M +l
Ey
Ex
Ev
Ek
1
1
+
M
+
v.
+ Vally *][M pl
(74)
&
Ey
Ek
Ev]
Remark D.7. By the symmetry of the expression inside the Q-function of eq. (73) it is sufficient to compare the numerators of it.
First notice that:
2 + | 11 [MM' + by
2 + p)
satisfy eq. (74). In addition we define the functions that control the error score of the class y - k and is y as f and g as follows:
[ 1 + M/ + +|) + Va
1 Vdzz
[(zyx)
Ey Ex
E
Ex
and
g(2yh)=
8.
M 1 +
+ Vdl
1
1
Vd
Ex
En
Ey
43

---

Published in Transactions on Machine Learning Research (02/2025)
where Zyk: 1k bv. Then it is clear that f and g are monotonically increasing and decreasing in Zyk- Therefore the minimal element is maximized in the intersection of ʃ and Which is obtained at
2+ 1 12 [M v + p]
" 25 M + pl
Discussion. Our analysis for near-optimal for the case of equal strength signals show that adjusting the logits of the maximum margin predictor can help mitigating its calastrophically failure on minorities. Specifically by removing the negative effect of -va &x Corollary D.8. In case the signals are wilhing equal strengths it holds that
la Err (p)
Sy Ny + 8N NoT 18y 8N N
-max Q kzy
(75)
2 (No. N2) Nikk + NoTRRrN + NoT (W(N)
where N.u.k = Eijy, No and T(ms) 2N, + N +p.
D.3 CDT
From Appendix C.3 it holds that for any pair y, i [c]:
ad v
5,
5,0 A
where A
Σ 87
N,E,
Substituting into eq. (29), obtain expressions for p(v) and E(v) for every y [c]
6y58
p/
A + 6mmm))
D
Notice that by definition of godt y[i
holds that:
82 N.E.A
aodt
(1(==y)A- - 1(c=/s A + +2 - -5y))
Substituting this in (()) [k
((l)) [R,b0]]
crit y
axdls] N2Ec.
52
(1 - [2=x] A + 82(5s- - -8y) (1))((((=))) A 1[a=k A + 05x - -5,)
E
82
(1) (0)
(2)
4,4
Where
(A + ((0) x ) ( ( + 6 )
1 102
A + 8-
11 A + 5(h)) )-
(w)
(k')
A + (4) k
)
(I + 6047)
44

---

Published in Transactions on Machine Learning Research (02/2025)
and for all i + k. k.
1a, (1)
(2)
6 0
Which means
67
(()) [M.A*]
(A
0/ ) A +
6//
A + ( (maai1) 00-12)
+
A
5
(1)
y-k
(A+
0
Sk,k'
+ [((K()}
+
AZEA'
A
where
6/ = 5x (8; - 6g) and (v)
Ek
Corollary D.9. The CDT expected kernel approrimation predictor salisfies, for every & k E [c].
By Ng
lim EIr, Erry-ss(WWeee (Woode)= = Q d=00
2
2 2(y)
1 5k
y-c 3+
No.
+
N,
1+
Ng
where
525
(k) (K)
A = Σ 5
i-y 5x(0; 5y) and c.u)
Σ
j-y
VE[c]
k
and tilde denotes the limit infinity, e.g.,
Â lim A.
d
E Analytical approximation summary
In this section summarize the parameterized that define the error of each predictor we analyze in this work. Denote by || a'd N. M Ei= & and M = Eitg 6.-
Max margin. The expected kernel approximation gives
1 ((i=w) - 1)
Σj 1 5v) and jmm
Σi= Ev 5
N.E.
CN,E. (M + p)
c(M + p)
and the expected score statistics approximation gives
1
2(0) = syNV
+
5
Vd
5 E
and
NyEy
Noty (M + p)
(M +p)
(1) + E
M + 2p
(1
Ex Ev )
( 1-1 1
111
1(kk=))-
[R.Ag)
Ey
(M 2)²
Ex'
Ey
45

---

Published in Transactions on Machine Learning Research (02/2025)
Margin adjustment. The expected kernel approximation gives
de [[t=x) - )) Σラ= 8
82 Σi=1
Ma v
and
NEC
CN (M + p)
c.
c(M
+ p)
and the expected score statistics approximation gives
6
6
(.u) [R]
= N,
by
+
EN
&
Vd
Ey
and
Now
N₁ (M + p)
M
+ P
(v)) o9 [R, Ey
5% [(==) (M + p)²
M + 2p
6y
(
by
+
Ek
Ev
EN
Ey
Additionally, the expected score statistics at the near-optimal margin, eq. (18), gives
(M + p) + Eu 8yg-1
0(4) [6] 8y
(suo+()(oo0+1)
1
8y 82
and
Eo (M +P)
(4y. + 1)(8 +1) 2
((2)) [k,A1]
Ey
&K
M + 2p
8y
8k' 89
(s + 1)²
+
(nkg + 1)²
(k)=k)))
4d
($yq + () + 1)
(s + 1)(8g) +1) 11)
q = (M + p) (2V
-1 and 8
&, |1lll3(M - p)2-1 +1
where
1 Notice that we scale 8* in eq. (18) by (M+p)2-T (as scaling all the parameters by a scalar does not change the solution).
Logit adjustment. The expected kernel approximation is the same maximum margin, except we offset the bias by iota. This results in obtaining the same parameters as the maximum margin with bias adjustment of
a
m.m
and
Blg
((x)-
The expected score statistics are
(
1
1
+ (1/y) - (M + +
((8)
Ny
+
Eu
Ev
vd
Ev
and
Ny
Nycy (M +p)
(M p)
(v) [R,A
1
M + 2p
+
1(k=k)
Ey
Ex
(M + p)²
Ee
Ey
Exr
Ex
Class dependent temperature. The expected kernel approximation gives
di NoC
8yó; where A = 8
edtt yM
[11=0)
A
The expected score statistics
(v)
8ysy
A + 6/4))
where ((1) k -5(0s - -5y)
[8]
DE,
and
(1)
[A,A1]
A
82
y
A + sl(0)
(A (1+
+
2
82
( + 14 0/411)
(4umi)) + -
+ 1(K5AA0
AZEN'
(a+
(a+
8662
+
A
where
Sk.k
(v)
Σ
Ex
46

---

Published in Transactions on Machine Learning Research (02/2025)
F Methods comparison
In this section present missing proofs from Section 4.
F.1 Margin adjustment
Proposition 4.2. Let Ni S N2 S ... S No and let p < oc. If 91 S 82 S S
Se then Errwe (6", p) _
Sc. When $1 82 EIT we (8", 00) or EIT (8*, p) < EIr (6", oc) is possible.
Err (6" 00), with equality when $1 $2
then either Eri we (8 p)
mia
Proof. We prove Proposition 4.2 by showing that the relevant equality and inequality hold for any pair & # y which implies that they hold for the worst class error as well.
Recall Errwe (6", 00) and Errwe (8*, for p < oo:
Err we 00) max Q 1-g
and Errwe (6*
max Q kigh
(sy+ (Ny + N)
Nys
NEs
The expressions are clearly equal when Sy 80 we focus on the other two cases, assuming without loss of generality that Ny < NR. Note that
Q
<Q
(s, ts (Nyy + N=E
Noog + Nust
if and only if
(Ny + +N= < (,t + (s2Nz)
(sy + sx)
N₂ Writing g N₂
and
e the inequality above is equivalent
=() = (1 r)+ (++1) 4(1 + 0.
Note that
f((r 2(1 (( 2
and therefore, we have (r) > for r > 1. Since f(1) = O, this implies that f(r) > for all r Sy > and a S 1. Therefore, when signal strengths are aligned with class sizes (i.e., Sy < sx) we have
Q
1 (2 (N, +NE2))
and hence lower crror for p oc as claimod.
Nu*
When the signals not aligned and 1, the sign of (r( depends the value of q, and hence both relative orders are possible, concluding the proof.
F.2 Logit adjustment
Proposition 4.4. sf 82 so then Err (t",p) is monotonic decreasing in p and, for all values of -laa la
P, have Err (v", p) < Frr (8*,0) p)-
47

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. First notice that by the assumption in the lemma it holds that || Va for all E [c] and for some 0.
Recall the expressions for we (t", p) eq. (75) and Errwe (6", ,) eq. (71):
( ( (NyT(A + &N (v(
EIT (1', = max Q
2 (N
N2) N 2
+ NoTRAr NoT
and
Err m& we (6', p) = max Q
(N11 + No (~T=+
y.
where Nlv. = -iigy N₂ and T(w) -N, + N +p.
We show that the inoquality Q ", k y and therefore holds for the maximum over pairs. By the monotonicity of the Q function it is enough to show that for any pair y + k,
NN, No
S SQ (
N holds for any pair
N₂ + Nisk + P) NN (2N, + Niok +P))
2
2
(76)
VIN. - N, NN)
+ (2N₂ + Nivk + p)² + (2N, + Niik + N₂ VNyy N
We start by showing that the LHS of eq. (76) is minimized when p=0. Tet [1
(p) where
9:(0)
gr(p) = N2 2NN + Ni + P) + No (2,2N, + Niin +p)
and
hp(p) V(Ne- N2)2N (2N₂ + NN + +))²N, N, +2NN, NN + +p)² Nk-
Then,
= - No
and
1 1 (N₂ - N2 + ((2N. + Nick + +D) ))² Nr + (2N, + Nint +p)² No.
-1/2
M(()) 2
(8N, + 22 + NN) 20(N + No))
Therefore,
(N, No) ((No 2 + (2N& N + + N, + (2N,, N + +p)²ND No
f((0)
(INa- - N + (2N₂ + N + 2) + (2N, + Nisk + +p) +)2NNN) 3/2
(4NyNe + NWW No) + M(N, + NON + NO + No) + p(N,, + No))
( 22 + (2N₂ + Ni + =)² N2 + (2N, + Nook + +)) 3/2
(N,, + Na. N N, ((NN + Ni*k + p) + (2.N, + Vi + +n))
0.
(Ne -N,) 2 + (2No + N + +))2Ng N2 + (2N, + Niik + +))²NZ NN)
3/2
48

---

Published in Transactions on Machine Learning Research (02/2025)
which means that fi is monotonicity increasing in p (and the composition of the Q-function on it is mono- tonicity decreasing) and
(2N2 Nivi) + N2N, + NiVA
fi(e) 2 fi(0) = V(Na - N2, lurk + (2N+ + Nivi) Nr + (2N, + Mook) 2 No
Next we define fz as function of N'sk as follows:
(2N + Nwwk) + (2N,, + N/WA
fo (AVlo))) (NV. - N (2N + N'IA) 'N + (2N + +Nook No
Similarly to the former step, we look at the derivative of (Nllu)))):
M(NWu (Ny, + Nx)
N1))(())) NN++ (INs - 22) + (2N + PN, (2N, - Niou 2 No. 3/2 )877
-Ny N + (2N + NNiM) 2 NN + (2N, + N 3
(N,-
N2 + NN + No + -Nion)) ) (NV, MM1M + N& + +())))
3/2
(N& - N + (2N4 + NWWA N, (2N, + +No NN.
(N2 N2y) Nivk (Ny + No. AN,,NK No -
3/2 >
((Na= N., 22y) + (2N₂ + +NND N2 - (2N, + +luR) NN,)
Where the last inequality holds since N + Ny 2 2. Therefore it holds that:
2 f2(0) (N
v N + No
and we get
(2N2 + + P) + (2N, + +Nokk + Pp)
2
V (Nk- N2) Niok + (2N Niwk =) Nr + (2N,, +Nikk +p)²
V VNy + No
required.
F.3 An intuition why CDT attains non-zero training error
Let us consider the optimization problem associated with the CDT predictor:
Wodt godt
arg min W WeRaxe .bER ||W|| + 2||b11
subject to 5y. (w,,z, x, + blw.1)
ōz (ww x, + bbg) 2 1 for all i S and t + yc.
(77)
Based on the definition of the CDT predictor optimization, eq. (77), it holds that for any (2t 91) in the training set, the CDT predictor satisfies:
1
1 (w) x, bat) > 1.
(w 2 + blv))
6v
49

---

Published in Transactions on Machine Learning Research (02/2025)
It is worth noting that this condition can be satisfied even in scenarios when the predictor attain non-zero
training error. For example, assume that fgg = 1 and òg = 4 when wy nz + bludl 2 and mog x; + lhg 3, shown below:
1 (w) xs + b11) 2 2 1,
( T + blu:)) d%
y/
the condition of eq. (77) holds. However, during inference, the learned predictor does not use the terms to compensate for incorrect predictions. This leads to the following scenario:
(wJ t. + b(aa) (w as + b(a) 2 3
which implics that:
arg max jEdd
(w] b()) + yi-
Thus the training error of the predictor is greater than zero. We verify this intuition using simple setting of synthetic Gaussian data in R2, see in Appendix G.7.
F.4 The limitation of CDT in multiclass classification
Proposition 4.6. For any c > and c 2 classes, there erists on instance (8,, N,)i=1 for which
lim Errwe (Wortt 0) 2 while d000
lim Errwe (W" o) se.
d
Proof. Corollary D.9 gives
lim Errwe (virodt, ,0) 2 max Q
8y
N
d=000
1 y
y-k
No. +
Sk.k
byy
8+
N,
83 N₂
Sy v
Nv
max Q kEy
(78)
8 by
N1
3 A+
Ny
where (1) holds by monotonicity of the Q-function and
S2.2 8,N,
0.
Let Âk.y = Eitt.r 83 and denote by vhy.
8
8
Åny + 8 + 3
k-y
Ny =
8k
(N)
8x
Anwy + 83 8 82
y-
D (x + 5g + 5y
1 + ÂB. 1/6₂ 1/5
(79)
Dx.g/ 1 15, + 5y + 8x
kkyy 5 + by + 8k
To establish our result, we define the signal strengths > 82 as follows. For every [c], we set
8. and class sizes N₁ < N2 < ... < N
2Q 2Q (e/cc
$y N2
(80)
50

---

Published in Transactions on Machine Learning Research (02/2025)
and we take N1 1, and, for every i 1, set
) N; = max ( 1, 4 Q- --1(3- -t)
( (2-1()))))))
c² (c/0) 2
+
(81)
We consider two cases.
Case 1: There exists < k such that by < dg. Therefore, by eq. (79) we have Vyy < 1 and, by eq. (78),
lim Errwe (Wodt, .) 2Q d
8y
N
N₂
Ny
By definitions of N, and 8t in eqs. (80) and (81) above, have Now notice that by definition for Ni, eq. (81), it holds that
8y $vVN, N₂
( )
<
V
N2 N₂
giving the claimed bound.
Case 2: For all y k it holds that 8z 8y. In this case have
1/82 1/81
11 = 1+ A
<1 +
A 1.2/ 81 + 01
02
820
+
82
(c 2
1
11
8201 + 82
2
2
Which means that
81 M
lim Frrwe (Wredt d
22 2Q
1 +
4 N₂
22
By the same explanation of case it holds that
8y
V N
1 - 2 -c)
Q
4 N /
02
Therefore for any
lim Errwo (Wrodt, 0) 2 2
d=300
as claimed.
To conclude the proof, we show that the worst class error MA is less than equal to e. Recall that
lim Errwe (T* ,x), & c max Errwe (6*, oo),
ma
key
and note that eq. (19) and our choices of s, and N give
8y N
12Q (20-1 (c/c)
Err (6", oc) max Q Kishtl
Q
1 +
$2 N
c'
No
completing the proof.
51

---

Published in Transactions on Machine Learning Research (02/2025)
F.5 The limitation of CDT in binary classification
We show that when using CDT with = 2, the direction of the classifiers are independent of ō1 and 62, and therefore CDT is no better than the MM. We note that while Kini et al. (2021) claim to analyze CDT in the binary case (and show improved performance on minority classes), the method they analyze is really a binary version of MA.
Lemma F.1. Let D = ((11, (1,,,,,,..,,, Rw. Hn)} be separable training set such that for any i E [n] Vi e {1, E Rdd Assume W1, w2 E R comprise the CDT predictor with porameters d1, 02 > O. In addition let ú1, 2y be the marimum margin predictor over D then for any E {1,2],
Wi
W;
||ū;
Proof. From the dual problem it holds that the learned predictor is of the form:
1
Aytes and 51
AahTi
82
where A the dual variable that correspond the (I M1) sample. In addition, notice that since 81, 82 there cxists 0 < c R such that d1 82, which means that:
0
1
W1
cd² w' and
Ay
82 w'
(82)
cO2
62 ==1
Recall that the CDT predictor solve the following optimization problem:
minimize||wal1 2 + || : [N] yi
W1
W22
2
1
(83)
11,002
01
82
plug in eq. (82) in eq. (83):
1
minimize
2003
| 2
82
w vi
[N]
y:
c2
w/
82
w
21
which is equivalent to:
1
mininizellww'11- Vi [N]
y/1
c282
w
34
1.
(84)
Recall that the maximum margin predictor satisfies v = 02 (which essentially results in learning a single predictor à 2.²)). Hence eq. (84) implies that
628
200
w
2
w 1
2
we can plug this back in wi and wy and get that the CDT predictor is just scaling of the maximum margin predictor:
2c d1 and wa
20a
2ca c
0
1 c²
1 2
See empirical validation in Appendix G.7.
52

---

Published in Transactions on Machine Learning Research (02/2025)
G Experiments
In this section, we provide a detailed presentation of our experiments. We showcase experiments conduct on multiple seeds and settings, including additional experiments omitted from the main paper due to space constraints.
How we compute predictors. Unless stated otherwise, we find the MM, MA, CDT and LA predictors we consider by solving the corresponding margin maximization problems (defined in Section 2.2) using CVXPY (Diamond & Boyd, 2016) with the MOSEK solver (MOSEK ApS, 2023).
How we compute error approximation. To compute the error approximation, we use the expressions for à and (refer to details in Appendix C)) to construct the statistics score parameters p(v) and E(v as described in Appendix D. Then, for calculating the error of the y y'th class, we employ Monte Carlo simulation. Specifi- cally, we sample 10,000 random samples from N -((Ww) (lw)) ) using numpy.random.mn manaiiaaaallii normal and record the number of positive vectors as N4. The error approximation of the y'th class is subsequently set N₂
to - ,4, where क 10,000
Gaussian mixture model datasets. To generate a Gaussian mixture dataset that aligns with our data assumptions, we follow the steps outlined below. For a dataset with e classes, we define the first e standard basis vectors as the directions of , Specifically, each μ4g is
H4 e
V
8; Va
such that ||
Vd
84
Additionally, for each data point, we sample noise vector from multivariate Gaussian distribution with o² 1. resulting in n, IRd Then, each data point is constructed as the sum of its signal and noise vectors as follows:
23 = Ply + T2.
Exponential long-tail profile. Whenever we mention the use of an exponential long-tail profile, we are referring to the exponential profile proposed by Cui et al. (2019). Specifically, for a desired imbalance ratio R N /max/Nun Niin and a maximum sample size Nmax the number samples for each class defined as:
c-1+1
N N max
R
G.1 Evaluating the impact of dimension on the validity of our approximation (Figure 1)
The approximations employed in this study rely on dimension dependent concentration bounds. To evaluate their effectiveness, we generate three distinct instances of our problem across varying dimensions, aiming to measure how accurately our approximation predicts the actual error obtained by the exact predictors (i.e., predictors that are obtained using the true feature kernel rather than the expected kernel). Each sub-figure in Figure displays the empirical and theoretical worst-class errors eq. (2) for the maximum margin (MM), class-dependent temperature (CDT), margin adjustment (MA), and logit adjustment (LA) predictors. Specifically, for MA and LA, we present the worst class error achieved at the near-optinal
parameters discussed in Section For CDT, we employed 6 = that results in the lowest worst class error based on our theoretical predictions.
where 7" represents the ry value
Our main goal in conducting experiments with diverse problem instances is to showcase situations where MA surpasses LA and vice versa, as well as instances where all methods demonstrate comparable performance. We repeat each experiment with 10 seeds; in the figures, the shaded area corresponds to two standard deviations from the empirical mean (one standard deviation above and below), providing a measure of variability. The solid line with markers represents our thcoretical approximation for the worst-class error, enabling comparison between the empirical and theoretical outcomes. Lastly, in all the experiments we use 4 classes and balanced test set with 500 samples per class.
53

---

Published in Transactions on Machine Learning Research (02/2025)
Common classes have weaker signals (left panel). We used N; values of 5, 50, 100 and 200, and corresponding values of of 0.5, 0.3, 0.2 and 0.1. MA performs better than LA, and CDT performs nearly as badly as MM, consistent with Proposition 4.4 and Proposition 4.6.
Common classes have stronger signals (middle panel). We used the same N; values as in the previous panel, but changed the corresponding & values to 0.5, 0.7, 0.9 and 1.1. LA performs better than MA, and CDT performs nearly badly as MM, consistent with Proposition 4.4 and Proposition 4.6.
Less class imbalance (right panel). We used N, values of 20, 35, 80, 100, and corresponding 8; values of of 0.4, 0.3, 0.25 and 0.2. In this less imbalanced instance, CDT performs similarly to MA and LA, while MM still performs noticeably worse.
G.2 Performance of the MM predictor and norm deviation
In this section, we provide detailed empirical analysis of the failure of the maximum margin (MM) predictor under class imbalance.
Recall the approximate error of the MM prodictor from Appendix D:
Ny + "
(p)
lim Erry - (Wrmm Jmmm) = Q d0000
(/N,
N₂ + No + 2
where,
(p)
lim d-+00
vd Ek &x (M p)
and
wim (p)
lim d
M + 2p
(
Ev )
[
(M + p)² Ex
By examining these equations, we observe that when p < 0o, i.e, learning with bias, and N2 > Ny, holds that:
mum (p) = -00
This results in a worst-class error lower bound of 1. On the other hand, when p = oc i.c., learning without bias, we get that:
Ny ( [N + Nk
Syy N
lim - (W (W/m Jmmn = d
= Q
(85)
N₂
This observation indicates that as the imbalance ratio Na inereases, the lower bound for the worst-class error N, becomes 1, which leads to a high test error. other words, when there is a significant class imbalance, the predictor more likely misclassify instances from minority classes, resulting in a higher overall error rate. We validate this observation in the following experiment.
Experiment details. We use four classes, with Nmax 200, and vary the exponential long tail profiles from an imbalance ratio of 1 to 100 in Id where d = 10 The signal strengths are set inversely proportional to the number of samples in each class, i.e., 8; = 1.2 (which allows us to fix the signal effect in the numerator of eq. (85) 1.2). For testing the performance of the learned predictor, 500 samples per class. The results are reported over 5 different seeds, where the shaded area represents two standard deviations from the empirical mean (one above and one below), and the solid line with markers represents our theoretical model prediction for the class error.
VN.
use balanced test with
Discussion. Figure demonstrates that our approximation is tight even at moderate dimension. Specifi- cally, we observe a catastrophic failure of the MM predictor with bias even in scenarios with extremely small class imbalance. Furthermore, the error of the predictor without bias on minority classes increases as the imbalance ratio becomes larger.
54

---

Published in Transactions on Machine Learning Research (02/2025)
Max margin
Max margin with bias
1.0
1.0
test error
0.4
0.4
0.2
0.2
0.0
0.0
20
40
100
0
20
40
60
80
100
imbalance ratio
imbalance ratio
class 4
class
class 2
class 1
Figure 5. Per-class error vs. imbalance ralio for MM predictors. The z-axis shows the imbalance ratio, ie., the ratio between the largest and smallest per-class sample sizes. The y-axis represents test error, and we plot the test error of each class. The left side shows the test eтror of the maximum margin (MM) predictor without bias, while the right side shows the lest error of the MM predictor with bias. The shaded regions show empirical results (two standard deviations over 5 random seeds) and the solid lines show our analytical approximation.
Common classes have stronger signals
Common classes have weaker signals
1.0
1.0
worst group error
000000
0.6
0.6
00
0.4
0.4
0.2
0.2
0.0
000000
0.0
P
MA
+
MM
+
MA with bias
MM with bias
LA
sqrt(d)
Figure 6. Worst class error vs. P for MM, MA and LA in linear classification on synthetic Gaussian data al the near-oplimal hyperparaneleess presented in Section 4. The shaded regions show empirical results (two standard deviations over random seeds) and the solid lines show our analytical approximation.
G.3 Testing discontinuity in
Our analysis of the MA and MM predictors in Section 4 reveals a discontinuity in the lower bound of the worst class error with respect to P as the dimension d approaches infinity. Specifically, for p < oc, we observe a certain value the lower bound of the worst class error at the near-optimal margins MA, while for p oC, we encounter different lower bound that is independent of p eq. (86).
maxieyy Q
p=
((BN,,) (stNN)) tyt
Err we (8*,p)
(86)
max Q
0:000
No ++
This raises an interesting question regarding how p affects the transition between learning with bias and without bias in finite dimension. To investigate this, we conduct experiments where we vary the value of p in finiteddimensional setting. By sweeping over different p values, we observe how the errors of the MM, MA, and LA predictors change function of (at the near-optimal parameters).
55

---

Published in Transactions on Machine Learning Research (02/2025)
Experiment details. We generate two Gaussian datasets, each containing four classes in RC with d = 109. Additionally, both datasets contain 5, 50, 100, and 200 samples per class. Tn the first dataset, the signal strengths are aligned with the order of the sample sizes, with values of 0.5, 0.7, 0.9, and 1.1. In the second datasct, the signal strengths are in reversed order, with values of 0.5, 0.3, 0.2, and 0.1. We utilize this setup to illustrate several observations. When the signals align with the class Irequencies, the LA predictor outperforms MA, and MA with bias is superior to MA without bias. Conversely, when the signal strengths are reversed, MA without bias becomes the most effective choice. Moreover, we anticipate that MM with bias will yield worse performance in both cases. As p increases, expect MA and MM (with bias) to converge to their corresponding predictors without bias. Furthermore, we employ a balanced test set consisting of 500 samples per class.
Discussion. Our results in Figure 6 demonstrate a smooth convergence between predictors with and without bias. Specifically, we observe that there is no midpoint of p that surpasses p or p = co. Moreover, as our thcory suggests we observe catastrophic failure of the MM predictor with bias even in scenarios with extremely small class imbalance. Additionally, we see the expected behavior of MA when the signals are aligned and reversed. Moreover, our approximation eq. (67) suggests, see that the transition between the < oo regime to the oo regime starts when is of the order of vd.
G.4 Classification with RBF kernel
To test the validity of our predictions beyond the scope of our model, we conduct classification experiments using the RBF kernel on imbalanced CIFAR1O, MNIST and FashionMNIST datasets that were featurized using V/T-B/32 CLIP model (Radford et al., 2021). Specifically we solve the kernel form of the optimization problems in Section 2.1 (sce Appendix A) when K is the RBF kernel (defined below). We consider two different class size profiles. The first profile follows a standard "long-tailed" exponential distribution (Cui et al., 2019; Cao et al., 2019), with 500 examples for the majority class and 5 examples for the minority class. The second profile maintains the same majority and minority sizes but increases the sample sizes of the other classes to worsen the theoretical predictions for CDT.
Data generation. For each dataset use in our tests (CIFAR1O, MNIST and FashionMNIST), we sample 5, 8, 13, 23, 38, 64, 107, 179, 299, 500 and 5, 100, 120, 140, 160, 180, 200, 220, 300, 500 samples per class for the exponential and modified profiles, respectively. We use the image encoder of pre-trained ViT-B/32 CLIP model (Radford et al., 2021) to extract features in R512 for each image. In addition, we featurize the standard test sets of each dataset and use to test the learned predictors.
Hyperparameter sweep. Taking random feature perspective, using the RBF kernel essentially corre- sponds to taking d -> co. Therefore, we use our theoretical tuning that matches this specific setting. For
11) while for the LA predictor, we use 4 = (%) (assuming
the CDT and MA predictors, we use 6; = N: the signals have equal strengths).
RBF Kernel. The RBF kernel is
||., 22,11
K
RBF [.
exp
2ç
where KRBB is an N x N matrix and ( is the kernel width. It is important to note that C becomes smaller, the kernel becomes closer to diagonal matrix, agreeing with our expected kernel approximation with the scaling ||22 = & and in the limit in the limit d + co. Conversely, as Ç becomes larger, the kernel widens and becomes less diagonal. We illustrate this in Figures 7a to 7c.
Distance from theory. To quantify the similarity between KRBF and the expected K kernel (see eq. (9)) used in our theoretical analysis, we define the "distance from theory" as follows:
DT((KREF) = min
||RBBF aq az! I|p
.gRR
where I is the N x N identity matrix and B E R has elements Bii,j] = (m Thus, the distance from theory measures the Euclidean (Frobenius) distance between RBBF and the block matrix K' af B + 0g
56

---

Published in Transactions on Machine Learning Research (02/202))
Kernel Width Distance from Theary 0.8316
Kernel Width 5 Distance from Theary 0.1851
Kernel Width Disrance from Theory 0.69122
Keme! Width
Kemel Width Distance from Theary 4.5960
Distance from Theary 2,0011
N
N
N
(a) CIFAR1O RBF Kernels
Karnel Widtth
Kornel Width 5
Kornel Width
Kome! Widthh 7
Komel Width
pistance from hherry 0. 0.6692
Distance from Theory 2883
Distance from Theory 5. 5.3653
Distance from heory 10.2091
Distance from Theory 17.1004
(b) MNIST REF Kernels
Kernel Distance from Theory 2.2584
Theory 0,6659
Distance Theory 5.5407
Distance Theory 10.8805
Distance Theory 18 18.3433
N
N
N
(c) MNIST RBF Kernels
Figure 7. Illustration of the RBF kernel on (a) CIFAR10 (b) MNIST and (c) PNShionMNIST with varying widths using 100 samples per class. The "distance from theory" at the widest kernel width indicates that CIEAR10 has properties that fits the best to our theoretical model.
that best approximates KBBF and is consistent with our data model (see sections 2.3 and 3.1) when the signals have equal strengths.
Discussion. In Figure 8, we extend Figure (which corresponds to kernel width 6.0) to show results with additional kernel widths. The figure illustrates that many of our predictions continue hold in this setting, particularly the high errors of CDT and MM (especially with bias), which persist across all tested kernel widths. Additionally, observe that kernel width of 6.0 appears to agrec most closely with our theory. As seen in Figure 8, approach this kernel width, the optimal tuning parameters tend to be around 7.7 = 1. Conversely, as we move away from it (e.g., kernel widths of 7.0 and 8.0), the optimal tuning parameters deviate from 1.
Moreover, Figures 9 and show similar observations for MNIST and FashionMNNST datasets. Specifically, in both datascts, we observe that the "modified class profile" leads CDT to failure in all kernel widths. Margin adjustment with bias, on the other hand, has optimal hyperparameters around 7 =.
For margin adjustment without bias and logit adjustment, FAR10 than they do for MNIST and FashionMNIST. This is consistent with the higher "distance from theory" computed for the latter two datasets Figures 7a to 7c. Two likely causes for the higher distance are: (1) the class signals are non-orthogonal, and (2) the signal strengths are not of equal magnitude. For Fash- JonMNIST (Figure 7c), both causes seem be at play, since there are significant kernel magnitudes across classes (indicating class signals are not orthogonal), and also the classes have unequal signal strengths. For MNIST (Figure 7b), we that in high kernel width, KBBF looks like the signal vectors of different classes
theoretical predictions hold better for Cl-
57

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA (with blas)
1.0
1.0
1.0
1.0
kornel wioth 6,0
0.5
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
0.0
1.0
1.5
10
0.5
2.0
1.0
1.0
1.0
1.0
kemel width 5.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
1.50
1.75
1.0
1.0
1.0
1.0-
keme width 6.0
0.5
0.5
0.5
0.5-
worst
0.0
0.0
0.0
0.0
1.0
1.5
1.0
2.0
0.5
2.0
1.5
2.0
1.0
1.0
1.0
1.0
kerme width 7.0
0.5
0.5
0.5
0.5
worst
120
0.0
0.0
0.0
1.00
1.25
1.50
1.75
1.0
1.0
1.0
1.0
kermel width 8.0
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
0.5
1.0
1.5
0.0
0.5
1.0
2.0
0.0
0.5
1.0
2.0
0.0
0.5
1.5
2.0
Exponential class profile
Modified class profile
Figure 8.
Empirical worst class Lest error vs. loss luning hyperparameter for the different methods we consider and kernel classification two imbalanced versions of CIFAR10 with varying kernel widths.
are nearly orthogonal (as there bright blocks cells that not centered around the diagonal), but still the classes have unequal strengths, some class blocks are much brighter than other class blocks.
G.5 CLIP fine-tuning
We conduct experiments to test our theoretical observations beyond the realm of linear classifiers and Gaus- sian data by fine-tuning zero-shot CLIP (ViT-B/32) (Radford et al., 2021) on three imbalanced CIFARIO datasets, each varying in the number of classes used.
In the three-class dataset, we include images of airplanes, cats, and horses from CIFAR10, with sample sizes per class of 1000, 500 and 5, respectively.
The four-class dataset consists of images of airplanes, cats, deer, and horses from CIFAR10, with sample sizes per class of 1000, 500, 300 and 5, respectively.
The ten-class dataset comprises images from all classes of CIFARIO, with 500, 450, 350, 300 280, 250, 230, 200, 150, and 5 sample sizes per class, respectively.
We consider a reduced number of classes in an attempt to make more challenging for CDT to succeed, as our theory suggests that a significant imbalance between consecutive classes hinders CDT's performance. For each model, we use the official CIFARIO test set and keep only the relevant classes for each experiment.
58

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA (with blas)
1.0
1.0
1.0
1.0
kornel width 4,0
0.5
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
0.0
1.5
1.0
1.0
1.0
1.0
keme width 5.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
error
1.0
1.0
1.0
1.0
keme width 6.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
2.0
1.5
2.0
0.5
1.5
1.0
1.0
1.0
1.0
kardal width 7.0
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
1.0
2.0
0.0
0.5
1.5
2.0
0.5
1.5
2.0
0.0
0.5
1.0
1.5
1.0
1.0
1.0
1.0
kermal width 8.0
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
1.0
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1,0
1.5
2.0
0.0
0.5
1.0
1.5
Exponential class profile
Modified class profile
Figure 9. consider and kernel classification two imbalanced versions of MNIST with varying kernel widths.
Empirical worst class Lest error vs. loss luning hyperparaneter for the different methods we
For each instance, we use PyTorch (Paszke et al., 2019) to fine-tune CLIP by minimizing the CDT and MA losses using the standard tuning parameter 6; = over the training set. addition we test the post-hoc bias adjustment of the MM predictor using both standard log ( and theoretical tuning = = N; N
Zero-shot initialization. To initialize the zero-shot model, we utilize templates from the official GitHub repository CLIP (Radford et al., 2021) for CIFAR10.
Training procedure. Fino-tuning performed using PyTorch (Paszke et al., 2019) while training is con- ducted for 1000 epochs, employing the SGD optimizer with batch size of 128, momentum, no weight decay, and gradient clipping with global norm threshold of 1. The learning rate is set to 1e-4 with cosine learning rate schoduler, and the training is distributed across 4 GPUs.
Figure 11 demonstrates partial agreement with our theory. CDT performs comparably to MA, and our theoretical setting LA slightly superior in the ten-class dataset but inferior in the other two cases. We note that CDT exhibits greater scnsitivity to the tuning of 7 than MA, which contradicts the predictions of Behnia al. (2023). Additionally, we observe that CDT does not converge zero training error (Figure 1 11b), supporting Remark 2.1.
Discussion.
59

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA (with blas)
1.0
1.0
1.0
1.0
kornel width 6,0
0.5
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
0.0
1.5
1.0
1.0
1.0
1.0
keme width 5.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
1.5
error
1.0
1.0
1.0
1.0
keme width 6.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
2.0
1.5
0.5
1.5
1.0
1.0
1.0
1.0
kerdl width 7.0
0.5
0.5
0.5
worst
0.0
0.0
0.0
0.0
1.0
2.0
0.0
0.5
1.5
2.0
0.5
1.5
2.0
0.0
0.5
1.0
1.5
1.0
1.0
1.0
1.0
kemel width 8.0
0.5
0.5
0.5
0.0
0.0
0.0
0.0
1.0
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1,0
1.5
2.0
0.0
0.5
1.0
1.5
Exponential class profile
Modified class profile
Figure 10.
Empirical worst class test error vs. loss luning hyperparameter for the different methods we consider and kernel classification two imbalanced versions of FashionMNIST with varying kernel widths.
G.6 Linear classification with Gaussian model
To validate the theoretical observations presented in Section 4, we conduct experiments to test the perfor- mance of the predictors we analyze in this work on various instances of our model. The empirical validation aims to demonsttrat the following key points:
The theoretical predictions for the error of all predictors tight even in finite dimension.
2. There instances of data where CDT performs very poorly, while MA and LA perform extremely well.
3. When the signals are of equal strength, MA with and without bias achieve the same optimum for the worst class error. Additionally, LA surpasses MA.
There are instances where MA without bias outperforms MA with bias and LA.
At least in a one-dimensional hyperparameter sweep, the near-optimal value predicted from our theory indeed optimal.
In certain scenarios, our theoretical tuning outperforms standard tuning.
60

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA
LA (standard)
LA (theoretical)
30
30
10-
10
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
10
20
30
10 classes
- 4 classes
classes
(a) CLIP fine-tuning and post-hoc hias adjustment worst class error (repeating Figure 3)
CDT
MA
CDT
MA
15.0
15.0
12.5
12.5
10
10-1
10.0
10.0
train loss
1.04
train
10-3
400 000000
10-1
2.5
000
2.5
20000
10-3
00000
0.0
0.0
00000
0.0
0.5
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
15
2.0
C=10
C=4
C=3
(b) Train error and train loss of CDT and MA
Figure 11. (a) Empirical worst class lest error vs. loss tuning hyperparameter and (b) training loss and егтor vs. loss tuning hyperparameter for CDT and MA in neural network fine-tuning on class-ibbalanced subsets of CIFAR1O.
Data setting. We conduct. experiments using five different instances of Gaussian mixture datasets that conform to data model described in Section 2.3. Each dataset. consists of four classes in Rd where d = 10 The test set for each instance is balanced, with 500 samples per class. The instances differ in terms of the following characteristics:
Instance (equal signals): has 5, 50, 100 and 200 samples per class and signal strengths 0.5 for all classes.
Instance (reversed signals): has 5, 50, 100 and 200 samples per class and signal strengths 0.5, 0.3 0.2
and 0.1, respectively.
Instance 3 (aligned signals): has 5, 6, 100 and 200 samples per class and signal strengths 0.5, 1.0, 1.5 and 2.0.
Instance 4 (weak aligned signals): has 5, 50, 100 and 200 samples per class and signal strengths 0.5, 0.7.0.9 and 1.1.
Instance (strong aligned signals): has 5, 50, 100 and 200 samples per class and signal strengths 0.5, 1.0, 1.5 and 2.0., respectively.
Experiment details. We tune each method by sweeping MA and LA using our theoretical expressions from Section 4, setting &; = (5;)7 and = TH, respectively, and sweeping over 7 and 7 such that value 1 recovers the theoretical tuning and value 0 reduces to standard maximum margin. For CDT we use standard tuning and set 6, = N,-". Additionally, whenever we mention that we use standard tuning for MA and LA we use 8, = N;" and 44 = 7 log N, respectively.
scalar hyperparameter. Specifically tune
Balanced error. The balanced error is defined by
1 Σ c
Errbal (W,6)
Err, (W,
Where Erry (W,b) is defined in eq. (1)-
61

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA
MA (with blas)
LA
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.2
0.2
0.2
0.0
0.0
0.0
0.0
Equal signals
Reversed signals
Aligned signals
(a) Instances 1-3
CDT
MA
MA (with bias)
LA
1.0
1.0
1.0
1.0
0.8
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Aligned signals
Strong aligned signals
(b) Instances 4-5
Figure 12. Worst class error vs, loss tuning hyperparameter for the different methods we consider in linear classification synthetic data from model. The shaded region show empirical results (two standard deviations over 5 random seeds) the solid lines show our analytical approximation. Figure 12a is exactly the same as the top row (showing worst class error) in Figure 2.
Macro Fi score. The macro Fi score is calculated by averaging the F1 scores for each class. The F1 score for each class y given by:
2 precision, recally (Fi), precision, recall,
where
TPp
TP.
precision, TP, + FP,
and recally TP, + FN,
and TP,, FP,, g. FNy are the true positive, false positive and false negative rates for class y, respectively, assuming the data comes from the (class imbalanced) training distribution.
The macro Fj score is then computed by averaging the F1 scores across all C' classes:
macro Fi = (A))
Discussion. Our experimental findings, as illustrated in Figures 12 and 13, provide strong support for the validity of our theory. Specifically, in Figure 12a, observe that when the signal strengths are equal, both MA with and without bias exhibit equivalent performance when 7 1, while LA outperforms MA when r = 1. Furthermore, across all test cases, we find no value of y that improves CDT's performance worst class. Additionally, Figure 12b demonstrates that CDT can achieve good performance in certain cases. In Figure 13, we compare the worst class error of standard tuning to theoretical tuning for all methods, The results indicate that, in all tested scenarios except for instance 5, thcorctical tuning consistently outperforms standard tuning, particularly in the case of LA. Finally, Figures 14 illustrate the tightness of our analytical expression per class in each tested instance
the
62

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
(with bias)
0.8
Instance 2
0.6
0.4
0.4
0.0
0.0
0.0
1.0
1.0
1.0
0.8
0.0
Instance
0.6
0.6
0.6
0.6
test
0.2
0.2
0.2
0.2
1.0
1.0
1.0
1.0
Instance
0.6
0
0.6
0.6
0.6
0.2
0.2
6.2
0.2
0.0
1.0
1.0
1.0
1.0
Instance
0.6
0.6
0.6
0.6
0.2
0.2
6.2
0.2
0.0
0.0
1.0
1.5
2.0
3.0
0.5
1.5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
3.0
1.5
2.0
1.0
1.0
Instance
0.6
0.2
0.0
0.0
0.5
3.0
1.5
2.
3.5
0.5
1.0
1.5
2,2
0.0
0.
1.0
1.5
2.0
0.0
0.5
1.0
3.5
2.0
standard tuning
standard tuning wcet
theoretical tuning
theoretical tuning wee
Figure 13. Worst class error vs. tuning hyperparameter (standard blue theoretical orange) for the different methods we consider in linear classification synthetic data from our model. The shaded regions show empirical results (two standard deviations over random seeds) and the solid lines show our analytical approximation.
G.7 Empirical demonstration of the limitations of CDT
We conduct two additional experiments to examine the effect of the 5 hyperparameter on the decision boundary of the CDT and MA predictors (without learning a bias parameter).
Data generation. We generate synthetic datasets (binary and multiclass) in g² by following these steps for each class:
Sample N; random samples from NN 12).
Generate a random projection matrix Q from R2 to R22
3. Perform random projection using Q; and add the signal vector μa to the projected points.
Where for the binary experiment use:
[1]
141 = and P2 =
63

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA
MA (with bias)
LA
1.0
1.0
1.0
1.0
test error
0.8
0.8
0.8
0.8
Instance
0.6
0.4
0.4
0.4
0.4
0.2
0.0
0.0
0.5
10
1.5
2.0
0.0
0.5
1.0
1.5
2,0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
1.0
test error
0.8
0.8
0.8
0.8
instance
0.6
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.5
1.0
15
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
1.0
test error
0.8
0.8
0.8
0.8
Instance
0.6
0.6
0.6
0.6
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.0
0.5
1.0
15
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
2.0
1.0
1.0
1.0 **0**0**
1.0
***.*0**
peeasco
test error
Instance
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.0
1.5
1.0
1.0
1.0
0000000
1.0
00000009
000000
2000
test error
0.8
0.8
0.8
Instance
0.6
0.6
0.4
0.4
0.4
0.4
0.0
0.0
0.0
0.5
1.5
0.5
1.5
1.0
2.0
0.0
1.0
Y
V
class 1
class
class
class 4
Figure 14. Per class error loss theoretical tuning hyperparameter for the different methods consider in linear classification on synthetic data from our model. The shaded regions show empirical results (two standard deviations over random seeds) and the solid lines show our analylical approximation.
and for the multiclass experiment we use: Where for the binary experiment we use:
41 =
P2
3 and
f2
3
Discussion. In Figure 15, we observe that the binary case, the hyperparameter d has no effect on the decision boundary of the CDT predictor (sce Figure 15a). However, when used the MA prodictor, it allows for shifting the decision boundary towards the majority class, which leads potential improvement of generalization minority classes (see Figure 15b). Similarly, in Figure 16, see that the hyperparameter
64

---

Published in Transactions on Machine Learning Research (02/2025)
y= 0.0
y= 0.1
y= 0.2
y= 0.3
y= 0.4
y = 0.5
y= 0.6
y= 0.7
y 0.8
y 0.9
Class
Class
(a) The CDT predictor decision boundary using different choice of hyperparameters
y= 0.0
y= 0.1
y= 0.2
y= 0.3
y= 0.4
Y = 0.5
y= 0.6
Y= 0.7
Y= 0.8
y= 0.9
Class
(b) The MA predictor decision boundary using different choice of hyperparameters
Figure 15.
The effect of y on the decision boundary (a) CDT (b) MA predictors binary classification. As it can be seen, in binary classification the hyperparameter has no affect on the decision boundury of the CDT predictor while in MA it changes the angle of the margin towards majority.
8 can lead to non-trivial training errors for CDT (scc Figure 16a), while for MA, it changes the angle of the learned predictor towards the majority class (see Figure 16b).
G.8 Implicit bias of gradient descent
To validate the implicit bias of gradient descent on the MA and CDT losses described in Appendix B, we compare the test error of the classifiers obtained by gradient descent (Figure 17a) with their corresponding predictors (Figure 17b) on a synthetic Gaussian dataset.
Datasct. We use a Gaussian datasct Rd for 10 with four classes. Each class contains 5, 50, 80, and 100 samples, respectively. The signal strengths for all classes are set s; 0.5. Additionally, we use a balanced test set containing 500 samples per class.
65

---

and for MA we use our Published in Transactions on Machine Learning Research (02/2025)
y= 0.0
y= 0.1
y= 0.2
y= 0.3
y= 0.4
y=
y 0.6
y= 0.7
y 0.8
y 0.9
Class
Class
Class
(a) The CDT predictor decision boundary using different choice of hyperparameters
y= 0.0
y= 0.1
y= 0.2
y= 0.3
y= 0.4
y= 0.5
y= 0.6
= 0.7
y= 0.8
y= 0.9
Class 2
(b) The MA predictor decision boundary using different choice of hyperparameters
Figure
The effect of y on the decision boundary of the (a) CDT and (b) MA predictors in multiclass classification. As it can be seen, in multiclass classification the hyperparameter can lead CDT to have uou-trivial train error, while in MA it changes the angle of the margin towards majority.
Gradient descent training. We use PyTorch (Paszke et al., 2019) to run gradient descent the MA and CDT losses (without learning the bias parameter) bias for 20,000 epochs. To avoid learning rate tuning and accelerate convergence we employed a variant of the Polyak step size for functions whose minimal value O:
(W,)
?i 0.05
(87)
(VC(W)) 1
In all experiments we initialized Wo and did not use weight decay.
Hyperparameter sweep. For CDT we use the standard tuning i.e., 6, = N, theoretical tuning from Section 4.
66

---

Published in Transactions on Machine Learning Research (02/2025)
CDT
MA
1.0
1.0
error
0.6
0.6
0.4
0.4
08.00
0.00
0.25
0.50
0.75
1,00
1.25
1.50
1.75
0.00
0.25
0.50
0.75
1,00
1.25
1.50
1.75
Y
Y
Class 1 (W 5)
Class 2 (N m 50)
Class (N 80)
Class 4 (N 100)
(a) Gradlent descent classifier emor per class
CDT
MA
0.8
0.8
test error
0.6
0.6
0.2
0.2
0.0
1.50
8.00
Y
Y
Class (N=5) 5)
Class (W 50)
Class (N 80)
Class 4 (N= 100)
(b) Exact predictors per class
Figure 17. An illustration the implicit bias of gradient descent on linear classifiers over Gaussian data. (a) Per class error vs. loss hyperparameter using gradient descent (b) Per class error vs. loss hyperparameter using CVXPY (Diamond & Boyd, 2016) solve the corresponding margin prohlem. The shaded regions show empirical results (# one standard deviation over random seeds) and the dashed lines show our analytical approximation for the error.
Discussion. Figure 17 shows that, our theory suggests, gradient descent on different losses converges in the direction of their corresponding predictors, as described in Section 2.1.
G.9 Extended comparison between LA and MA predictors
To validate whether the LA predictor, tuned for near-optimal parameters with equal strength signals, out- performs the MA predictor under reversed aligned signal strengths, compare their worst. class error lower bounds at the near-optimal parameters of MA (with and without bias) eq. (19) and LA eq. (22), and calculate the histogram of bound differences for these cases.
Use case parameter generation. For each case study, we conduct 500 experiments where, each exper- iment, we sample the number of classes uniformly from 3 10. Each class size is sampled uniformly from to 200, the dimension d is sampled uniformly from 10 to 107, the signal strengths are sampled uniformly from 0.01 to and p is sampled uniformly from to 1000.
Discussion. Our findings in Figure 18 show that for aligned signals, LA (tuned for equal signals) is consis- tently better than MA without bias, though in rare cases MA with bias slightly outperforms it. For reversed signals, LA is generally worse than MA with bias, but there are occasional exceptions. These findings strongly suggest that LA consistently better than MA without bias for aligned signals, aligning with our additional experiments in Section 5. Additionally, the converse does not hold: for reversed signals, MA is not always superior to LA, even when LA is optimally tuned.
67

---

Published in Transactions on Machine Learning Research (02/2025)
the Optimal parmaeter Difference Equal Strength Signals
LA- MA without bias
LA MAwith
with MA without bies
400
80
60
RoQusncy
Resuanc
500
200
20
20
0.0
-0.2
0.0
0A
-lex15
-0.5e133
0.5e-15
bo
difference
(a)
WCE Lower Bound at the Near Optimal parmaeter Difference Aligned Signals
MA without
LA with bias
MA MA without bias
100
300
100
Frowuarcy
Froduancy
6.
60
60
20
20
20-
WACE
difference
WCE Lower Bound the Near Optimal parmaeter Difference Reversed Signals
LA MA without blas
LA MA with bias
MA with
MA without blas
80
80
80
Prequenc
60
heqquery
60
Proquency
4.0
40
20
20
-2.6
-2.2
0.5
0.2
0.
-0.4
-0.2
0.0
5.2
0.4
-0.4
-0.2
6.0
0.2
2-4
WCE lower bound deforence
WCCE lower bound difference
WICE lowar bound difference
(c)
Figure 18. Histogram of the worst-class parameter 1 eq. (22) and MA with and without bias at the near-optimal parameter 5 eq. (19). Shown for cases with (a) equal signal strengths, (b) aligned signal strengths, and (c) reversed signal strengths. Each case confirms the validity proposition 4.2. Row (a) also confirms proposition 4.4. Row (b) demonstrates that, even with near-optimal parameters for the equal-strength signals case, LA is consistently superior to MA. Row (c) shows that, in most cases, MA outperforms LA for reversed signals, though there instances where LA, tuned for equal signal strengths surpasses MA.
lower bound differences between LA at its near-optinal
68


Reviews:
[{"review_id": "ZGhEyGWWWE", "reviewer": "Reviewer_JvdP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Clear writing and notation. Paper is easy to follow.\n\nApproximations seem to follow empirical findings, especially for synthetic data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an analytical approximation of classification error for imbalanced data, under the setting of linear classification with data sampled from a Gaussian mixture model. The authors analyze their approximation for various loss functions used in the literature under settings of data imbalance, like margin adjustment, class-dependent temperature, and logit adjustment. The approximation relies on viewing the classification problem as an equivalent margin problem and approximating the kernel via its expectation. The authors validate their approximation across 3 experiments: a synthetic GMM setting, RBF kernel on imbalanced CIFAR10 data, and CLIP model.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In Sec. 3.1 around Eq. (9), the paper asserts that the solution to Eqs. (5) and (6) are dependent only on the kernel matrix. I understand intuitively how this is true and it is sort of demonstrated in Eq. 14, if I understand correctly. Nevertheless, this seems like a bit of a jump in the paper that is not immediately clear to me. Perhaps there could be some justification here or in the Appendix, or perhaps it could be reworded. Especially as this seems to be a central point in the paper.\n\nSome notation with subscripts and bracket indexing was confusing, and took me a bit to understand. E.g. Eq. (10) where the $[i]$ in $\\alpha_{y[i]}$ is not the i'th index of $y$ but the i'th index of $\\alpha_y$.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rAmEAsA77T", "reviewer": "Reviewer_BKTX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The paper provides a theoretical framework for understanding class imbalance in overparameterized settings.\n2. It systematically compares MA, LA, and CDT, and identifies their strengths and weaknesses.\n3. The paper offers concrete guidelines for hyperparameter tuning, making the results actionable for practitioners.\n4. Experimental results support the theoretical analysis.\n\n**Weaknesses:**\n1. The paper assumes a simple setting, Gaussian mixture data and linear classifiers, which may limit the applicability of findings to complex neural networks.\n2. The description of experiments is not very clear. Especially how the empirical results validate theoretical analysis is unclear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper leverages a high-dimensional Gaussian mixture model to study class-imbalanced learning in overparameterized settings. It introduces an analytical framework to estimate test errors for various methods, including logit adjustment (LA), class-dependent temperature (CDT), and margin adjustment (MA). The authors derive closed-form approximations for test errors across different configurations and identify failure modes of cross-entropy minimization in imbalanced scenarios. Additionally, the paper offers practical insights into the optimal tuning of hyperparameters for MA and LA, with experimental results that support the theoretical analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. What does $N$ represent?\n2. Please write a more clear explanation about Figure 1. In Section G.1, the authors claim that Figure 1 demonstrates the empirical and theoretical worst-class errors eq (2). It's unclear to me which subfigure is for empirical and which is for theoretical.\n3. Comparing different methods in Figures 2, 3, and 4 is difficult. If the authors want to compare different methods for various settings, it's better to include all methods (CDT, MA, LA,...) in the same figure and separate settings independently. Or give a table for a more visual comparison.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "t3hHSHGZyc", "reviewer": "Reviewer_kJEg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- this paper provides a useful theoretical analysis, that enables to gain insights on the behavior of MM, LA, CDT and MA which are not easy to intuit just by looking at the definition of these classifiers\n- the theoretical framework is clearly stated, and the limitations of the hypothesis made are discussed\n- there is a clear consistency between the theoretical predictions and the numerical results.\n\nWeakness: \n- the supplementary material is very long and I did not read it", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the behavior of various methods to mitigate the class imbalance problem in multi-class regression such as logit adjustment (LA), class-dependent temperature (CDT) and margin adjustment (MA). In a high-dimensional Gaussian mixture setting, the authors are able to derive key properties of the classifiers learnt by these methods, exhibiting their advantages and pitfalls, their hyper-parameter scalings and confirming these theoretical insights in numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Nothing important. Small remark about the first footnote on the overparameterized regime: it is not clear what is meant here (typically, \"overparameterized\" means that the number of parameters is higher than the number of input points isn't it?)", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an analytical approximation of classification error for imbalanced data and studies the solutions found by various methods in terms of this novel approximation. This is clearly of interest to some in the community. The reviews were all positive to begin with and what minor concerns there were were addressed fully in rebuttal. This is a clear accept.
Decision: Accept (poster)