A replica analysis of under-bagging
Authors: Takashi Takahashi
Venue: Accepted by TMLR ()

Abstract: Under-bagging (UB), which combines under-sampling and bagging, is a popular ensemble learning method for training classifiers on an imbalanced data. Using bagging to reduce the increased variance caused by the reduction in sample size due to under-sampling is a natural approach. However, it has recently been pointed out that in generalized linear models, naive bagging, which does not consider the class imbalance structure, and ridge regularization can produce the same results. Therefore, it is not obvious whether it is better to use UB, which requires an increased computational cost proportional to the number of under-sampled data sets, when training linear models. Given such a situation, in this study, we heuristically derive a sharp asymptotics of UB and use it to compare with several other standard methods for learning from imbalanced data, in the scenario where a linear classifier is trained from a two-component mixture data. The methods compared include the under-sampling (US) method, which trains a model using a single realization of the subsampled data, and the simple weighting (SW) method, which trains a model with a weighted loss on the entire data. It is shown that the performance of UB is improved by increasing the size of the majority class while keeping the size of the minority fixed, even though the class imbalance can be large, especially when the size of the minority class is small. This is in contrast to US, whose performance is almost independent of the majority class size. In this sense, bagging and simple regularization differ as methods to reduce the variance increased by under-sampling. On the other hand, the performance of SW with the optimal weighting coefficients is almost equal to UB, indicating that the combination of reweighting and regularization may be similar to UB.

Published in Transactions on Machine Learning Research (07 (024))
A replica analysis of under-bagging
Takashi Takahashi" Institute for Physics of Intelligence, The University of Tokyo
takashi-takahashii@ www.::hhii......uto....... acc.u-tokyo.ac.)
Reviewed on OpenReview: http:://ppaarriii...eee////////0
Abstract
Under-bagging (UB), which combines under-sampling and bagging, is popular ensemble learning method for training classifiers on an imbalanced data. Using bagging to reduce the increased variance caused by the reduction in sample size due to under-sampling is natural approach. However, it has recently been pointed out that in generalized linear models, naive bagging, which does not consider the class imbalance structure, and ridge regularization can produce the same results. Therefore, it is not obvious whether is better to use UB, which requires an increased computational cost proportional to the number of under-sampled data sets, when training linear models. Given such situation, in this study, we heuristically derive sharp asymptotics of UB and use it to compare with several other popular methods for learning from imbalanced data, in the scenario where a linear classifier is trained from a two-component mixture data. The methods compared include the under-sampling (US) method, which trains a model using single realization of the under-sampled data, and the simple weighting (SW) method, which trains model with weighted loss on the entire data. It is shown that the performance of UB is improved by increasing the size of the majority class while keeping the size of the minority fixed, even though the class imbalance large, especially when the size of the minority class is small. This is in contrast to US, whose performance is almost independent of the majority class size. In this sense, bagging and simple regularization differ as mothods to reduce the variance increased by under-sampling. On the other hand, the performance of SW with the optimal weighting coefficients is almost equal UB, indicating that the combination of reweighting and regularization may be similar to UB.
be
1 Introduction
In the context of binary classification, class imbalance refers to the situations where class overwhelms the other in terms of the number of data points. Learning on class imbalanced data often occurs in real- world classification tasks, such as medical data analysis (Cohen et al. 2006), image classification (Khan et al. 2018), and so on. The primary goal when training classifiers on such imbalanced data is to achieve good generalization to both minority and majority classes. However, standard supervised learning methods without any special care often results in poor generalization performance for the minority class. Therefore, special treatments (ML) community for decades.
necessary and have been one of the major research topics in the machine learning
Under- bagging (UB) Wallace et al. 2011 is a popular and efficient method for dealing with a class imbalance
that combines under-sampling (US) and bagging (Breiman) 1996). The basic idea of UB is to deal with class imbalance using under mamer-gnmping that randomly discards a portion of the majority class data to ensure an

---

Published in Transactions on Machine Learning Research (07/2024)
equal number of data points between the minority and the majority classes. However, this data reduction increases the variance of the estimator, because the total number of the training examples is reduced. To mitigate this, UB aggregates estimators for different under-sampled data sets, similar to the aggregation performed in bootstrap aggregation (Breiman 1996). US corresponds to a method of training a classifier on a single undersampled data. (Wallace et al. 2011 | argues that UB is particularly effective for training of overparameterizet models, where the number of the model parameters far exceods the size of the training data.
There is another line of approach, that is, cost-sensitive methods, which modify the training loss at each data point depending on the class it belongs to. However, it has recently been argued that training overpa- rameterized models using cost-sensitive methods requires delicate design of loss functions (Lin et al. 2017
Khan et al., 2018 Byrd & Lipton 2019 Ye et al. 2020 Kini et al. 2021] instead of the naive weighted cross-entropy (King & Zeng 2001) and so on. In contrast to such delicate cost-scnsitive approaches, UB has the advantage of being relatively straightforward to use, since it can achieve complete class balance in any
under-sampled dalaset.
Bagging is natural approach to reduce the increased variance of weak learners, resulting from the smaller data size due to the resampling. However, unlike decision trees, which are the primary models used in bagging, neural networks can use simple regularization methods such as the ridge regularization to reduce the variance. In fact, it has recently been reported experimentally that naive bagging, which ignores the structure of the class balance, does not improve the classification performance of deep neural networks (Nixon) et al.) 2020). Furthermore, in generalized linear models (GLMs), it has been reported both theoretically (Sollich & Krogh 1995 Krogh & Sollich 1997; LeJeune et al. 2020 Du al., 2023) and experimentally (Ya et al. 2021] that bagging with a specific sampling rate is exactly equivalent to the ridge regularization with a properly adjusted regularization parameter. These results indicate that naive bagging, which ignores the class imbalance structure, plays the role of an implicit ridge regularization in linear models. Given these results, the question arises whether it is better to use UB, which requires an increased computational cost proportional to the number of under-sampled data sets, when training linear models or neural networks, rather than just using US and the ridge regularization.
Given the above situation, this study aims to clarify whether bagging ridge regularization should be used when learning linear classifier from a inbalannaee data. Specifically, we compare the performance of classifiers obtained by UB with those obtained by (i) the under-sampling (US) method, which trains a model using a single realization of the subsampled dataset, and (ii) the simple weighting (SW) method, which trains a model with a weighted loss on the entire data, when training a linear model on two-component mixture data, through the F-measure, the weighted harmonic mean of specificity and recall (see Section 2 for the formal definition). To this end, we heuristically derive a sharp characterization of the classifiers obtained by minimizing the randomly reweighted empirical risk in the asymptotic limit where the input dimension and the parameter dimension diverge at the same rate, and then use it to analyze the performance of UB, US,
and SW.
The contributions of this study are sunmarized as follows:
A sharp characterization of the statistical behavior of the linear classifier is derived, where the classifier is obtained by minimizing the reweighted empirical risk function on two-component mixture data, in the asymptotic limit where input dimension and data size diverge proportionally (Claim 3 This includes the properties of the estimator obtained from the under-sampled data and the simple weighted loss function. There, the statistical property of the logits for a new input is described by a small finite set of scalar quantities that is determined as solution of nonlinear equations, which we call self-consistent equations (Definition 1. The sharp characterization of the F-measure is also obtained (Claim 4.. The derivation is based on the replica method of statistical physics (Mézard
et al. 1987 Charbonneau et al. 2023 Montanari & Sen 2024).
Using the derived sharp asymptotics, is shown that the estimators obtained by UB have higher generalization performance in terms of F-measure than those obtained by US. Although the perfor- mance of UB in terms of the F-measure is improved by increasing the size of the majority class while
2

---

Published in Transactions on Machine Learning Research (07/2024)
keeping the size of the minority class fixed, the performance of US is almost independent of the size of the excess examples of the majority class (Section 4.1 and 4.3) This result. is clearly different from the case of the naive bagging in training GLMs without considering the structure of the class imbalance, where the ensembling and ridge regularization yield the same performance. That is, the ensembling and the regularization are different. when using under-sampled data.
On the other hand, the performance of SW with carefully optimized weighting coelficients is almost equal to UB (Section 4.2p. In this sense, the combination of the weighting and ridge regularization similar to UB. However, in SW, the weighting coefficients are not well optimized and the default values in ML packages such the scikit-learn are used (Podregosa et al. 2011). the performance deteriorates rapidly as the number of exess majority samples increases (Section 4.2 and Appendix
D although UB does not requires such careful tuning.
Furthermore, it is shown that UB is robust to the existence of the interpolation phase transition, where data goes from linearly separable to inseparable training data (Section 4.1.1). In contrast, the performance of the interpolator obtained from a single realization of balanced data is affected by such a phase transition as reported in the previous study (Mignacco et al. 2020
1.1 Further related works
Learning under class imbalance is a classic and notorious problem in data mining and ML. In fact, the development of dealing with imbalanced data was selected as "10 CHALLENGING PROBLEMS IN DATA MINING RESEARCH" (Yang & Wul 2006) about 20 years ago in the data mining community. Due to its practical relevance, a lot of methodological research has been contimously conducted and are summarized in
reviews (He & Garcia 2009 Longadge & Dongre 2013 Johnson & Khoshgoftaar 2020).
2019 Mohammed et al.
Learning methods for imbalanced data can broadly be classified into two categories: cost- and data-level ones. In cost-sensitive methods, the cost function itself is modified to assign different costs to each class. A classic method includes a weighting method that assigns a different constant multiplier to the loss at cach data point depending on the class it belongs to. However, when training overparameterized models, it has been argued that a classic weighting method fails and a more delicate design of the loss function is required to properly adjust the margins between classes (Lin et al. 2017 Khan et al. 2018 Byrd & Lipton 2019 Ye lt al., 2020 Kini et al.) 2021). In data-level methods, the training data itself is modified create class- balanced dataset using resampling methods. The major approaches include US (Drummond et al.) 2003)
which randomly discards some of the majority class data, and SMOTE (Chawla et al.) 2002), which creates synthetic minority data points. Although the literature (Wallace et al. 2011) argues that a combination of US and bagging is more effective for learning overparameterized models than the naive SW method, the comparison with other rogularization techniques is not discussed. Intuitively, when the mumber of data points is small and the data is linearly separable, the position of the classification plane (i.e., the bias) cannot be uniquely determined without regularization even if the cost function is weighted by a multiplicative factor. In this situation, resampling can be more efficient control the bias term than the simple weight decay. On the other hand, this intuitive picture cannot explain how much performance difference would be observed quantitatively until the values are evaluated precisely. Showing this difference qualitatively is one goal of this paper.
Technically, our work is an analysis of the sharp asymptotics of resampling methods in which the imput dimension and the size of the data set diverge at the same rate. The analysis of ML. methods in this asymptotic regime has been actively carriod out since the 1990s, using techniques from statistical physics OOppe & Kinzel, 1996 Opper |001]] Engel & Van den Broeck] 2001). Recently, it has become one of the standard analytical approaches, and various mathematical techniques have also been developed to deal with it The salient feature of this proportional asymptotic regime is that the macroscopic properties of the learning results, such as the predictive distribution and the generalization error, do not depend on the details of the realization of the training datef] when using convex loss. That is, the fluctuations of
In contrast, microscopic quantities such as each element of the weight vector fluctuate depending on each realization of the training data.
3

---

Published in Transactions on Machine Learning Research (07/2024)
these quantities with respect to the training data vanish, allowing us to make sharp theoretical predictions
(Barbier et al. 2019; Charbonneau et al.
2023) The technical tools for analyzing such asymptotics include
the replica method [Gerace et al. 2020 Charbonneau et al.) 2023 Montanari & Sen, 2024), convex Gaussian
minimax theorem (Thrampoulidis ct al.,
2018),
random matrix thoory (Mei & Montanari 2022). adaptive
interpolation method (Barbier & Macris 2019 Barbier et al. 2019 approximale message passing (Sur &
Candès 2019
Feng et al. 2022).
Classification of Gaussian mixture data using linear models has been extensively studied in such propor- tional asymptotic regime (Mignacco et al. 2020 Loureiro et al., 2021 Mannelli et al. 2024]. (Mignacco et al, 2020) studies empirical risk minimization on binary Gaussian mixture models and reports that ridge regu- larization with an infinitely large regularization parameter yields the Bayes optimal classifier for balanced clusters with the same covariance structure. (Loureiro et al., 2021) extends the results to K-component Gaussian mixture models with K > and investigates the role of regularization
more detail. (Pesce ct al., 2023) investigates when and how the phenomenology found in the above solvable setups is shared with weal-world setups. Also, (Mannelli et al., 2024) investigales classification problem when the ground truth labels are given by cluster dependent teacher models especially from the viewpoint of fairness. Our work can be seen as an extension of these analyses to ensemble lcarning in the simplest setup.
Resampling methods have also been studied in the same proportional asymptotics. (Sollich & Krogh 1995;
Krogh & Sollich| 1997; Malzahn & Opper, 2001 2002; 2003 LeJeune et al.] 2020 Ando & Komaki, 2023
Bellec & Koriyama, 2024 Clarté et al. 2024 Patil & LeJeune 2024) analyze the performance of the ensemble
average of the linear models, and (Takahashi) 2023) analyzes the distribution of the ensemble average of the de-biased elastic-net estimator (Javanmard & Montanari, 2014a|b) However, these analyses do not address the structure of the class imbalance. (Lofiredo et al. 2024) investigates the under/over sampling for linear support vector machines and reports that the combination of under/over sampling yields the optimal result at severely label imbalanced cases, although the effect of ensembling is not considered. Ensembling in random fcature models as a mothod to reduce the effect of random initialization are also considered in (D Ascoli Loureiro el al., 2022). Furthermore, the literature (Obuchi & Kabashima 2019 Takahashi &
et al. 2020:
Kabashima
2019 2020) derives the properties of the estimators trained on the resampled data set in the analysis of the dynamics of approximate message passing algorithms that yield exact results in Gaussian
rotation-invariant feature data.
1.2 Notations
Throughout the paper, we use some shorthand notations for convenience. We summarize them in Table 1
2
Problem setup
This section presents the problem formulation and our interest in this work. First, the assumptions about the data generation process are described, and then the estimator of interest is introduced.
Let D+ = (( 1) o E R and D- = -1),, x5 E N be the sets of positive and negative examples; in total we have M = M + M examples. In this study, the positive class is assumed to be the minority class, that is, M+ < M Also, is assumed that positive and negative samples are drawn from a mixture model whose centroids are located at te/VN with v E N being a fixed vector as follows:
1
x
v + = VN
(1)
x5
1 v 2 zū,
(2)
where z and 25 are noise vectors. We assume that = Zy. Rid Pa, E [M+], v E [M-], E [N], where the mean and the variance of pa are zero and A, respectively, and also the higher order moments are finite. From the rotational symmetry, we can fix the direction of the vector a as = (,.,,...,1) 1)T without loss of generality. The goal is to obtain classifier that generalize well to both positive and negative inputs from D D+ U D The performance metric for classifiers cannot. be uniquely determined because they
4

---

Published in Transactions on Machine Learning Research (07/2024)
Notation
Description
N
input dimension
M+
size of the positive examples (assumed to be the minority class) size of the negative examples (assumed to be the majority class)
M
M
M+ + M the size of the overall training data indices of data points
P,
i.j
indices of the weight vector w
bn]
for an positive integer n, the set [1...., i-th element of vector v for vectors æ; y E RR,, the inner product of them: x. v = -i= 2:th- an N-dimensional vector (I, E RV indicator function
a
1N
1(.)
N(,, o²)
Gaussian density with mean l and variance o²
(oisson((s.)
Poisson distribution with mean f4, independent and identically distributed Expectation regarding random variable X where p is the density function for the random variable X
iid
Ex~px [f(X)
(lower subscript X ~ px or px can omitted if there is no risk confusion) Variance: [X] [E][()]²
V Vx-px [[())
(lower subscript X px or px can be omitted if there is no risk of confusion)
5.(.)
Dirac's delta function
Table 1: Notations
can depend on factors such as how much importance is given to errors for each class. For simplicity, in this work, we take the position that errors are treated equally for positive and negative examples, and measure performance by the F-measure, which is defined as the harmonic mean of specificity S and recall Specificity and recall are the expected error rates conditioned that inputs are positive and negative examples, respectively. Let ((x) be the predicted label for an input x. Then, specificity and recall are defined
1
S = Ez-p, [1(((x+) ) + 1)],
x
v + 2,
(3)
VN
1
R E Ez-p, [(j(x= + 1)]
x
2,
(4)
VN
Using these two quantities, the F-measure F given as
F
(5)
3
This is independent of the label imbalance of the target distribution since specificity and recall are defined thorough the conditional distributions.
We focus on the training of the linear model, i.c., the model's output f(x) at an input x is a function of linear combination of the weight w and the bias B:
(1
Smodel (x:)
(6)
where the factor 1//N is introduced to ensure that the logit w/ /N + B should be of O(1), and f is noulinear function. In the following, we denote 0 for the shorthand notation of the linear model's parameter.
We consider specificity instead precision here avoid making the F-measure dependent on prevalence.
5

---

Published in Transactions on Machine Learning Research (07/2024)
To obtain classifier, we consider minimizing the following randomly reweighted empirical risk function:
M+
arg min (w. N+1
E
c (2
w/VN-D/
Σ
( w/VN
r(w,),
(7)
when the bias B estimated by minimizing the cost function. When the bias is fixed as during the training, one can simply replace with В 7 and optimize only with respect to w E RRN. Here, I+ and 1- the convex loss for positive and negalive examples, respectively. For example, the choice of (x) log(a(z)) and [ (x)
logg11 oxx),, with o(-) being the sigmoid function, yields the cross- entropy loss. Also, of wid Pe and op ~id Pe are the random coefficients that represent the effect of the resampling or the weighting. In the following, we use the notation e = {et U ( ~ Pe- Finally, Ar(x) = x is the ridge regularization for the weight vector with a regularization parameter X E (0, oo).
By appropriately specifying the distribution p the estimator 7 can represent estimators for different types of costs for resampled or reweighted data as follows:
US without replacement (subsampling):
pt (c+) =dalet - 1)
(8)
Pe (c --.aacec 1) (1 pua)aacc
(9)
where μa E (0, 1] be the resampling rate. μ., = M+ /M- is a natural guess to balance the size of the sizes of positive and negative examples.
US with replacement (bootstrap):
ps (c+) = dalct 1),
(10)
Pe Poisson((..)
(11)
where us E (0, 1] be the resampling rate.
Simple weighting:
p=(ct) = da(ct - -,
(12)
PE (c = da(c -7 Y
(13)
where ,t, E oo) the reweighting coefficient for the positive and negative classes. y+ MM)++M)/(MM is naive candidate used default value major ML packages such the scikit-learn (Pedregosa et al. 2011 King & Zeng 2001
(M+ M2M)
The ensemble average of the prediction for new input æ is thus obtained as follows:
Ec x. ((c, + B(c, D)] when bias is estimated
(14)
E, x w.c, Dlc,
when bias fixed
The predicted labels are given by the sign of these averaged quantitics. In this study, we mainly focus on the case of subsampling as a method of resampling - except for Section 4.3 which briefly compares the sampling with and without replacement, since the the computational cost is usually smaller than the bootstrap.
The purpose of this study twofold: the first to characterize how the prediction a w(c DY/NN + B(c, D) (or B) depends statistically on and e, and the other is to clarify the difference in performance

---

Published in Transactions on Machine Learning Research (07/2024)
with the UB obtained by 14h and the US SW obtained by 77 with fixed C. We are interested in the generalization performance for both positive and negative inputs. Therefore, we will evaluate the generalization performance using the F-measure, the weighted harmonic mean of specificity and recall.
To characterize the properties of the estimators we consider the large system limit where N, W,M+, MM + xo, keeping their ratios as (M+ /N, / = (at,a" E (0, o0). In this asymptotic limit, the behavior of the estimators 7 can be sharply characterized as shown in the next section. We call this asymptotic limit large system limit (LSL). In the following, N + oo represents the LSL as shorthand notation to avoid cumbersome notation.
3 Asymptotics of the estimator for the randomized cost function
In this section, present the asymptolic properties of the estimators 7 for the randomized cost functions. It is described by small finite set of scalar quantities determined as solution of nonlinear equations, which we refer to as self-consistent equations. The derivation is outlined in Appendix A Readers unfamiliar with replica analysis may have difficulty in interpreting Definition and Claim 1 In that case, we recommend to proceed to Claims 4 first,, and then go back to Definition and Claim to understand how the constants are defined.
First, let us define the self-consistent equations that determines set of scalar quantities B E R. (g,m, x) o0) R oz) x (0, xo) and Ô (Q, m. & 0) E (0, x R x (0) (0, that
characterize the statistical behavior of 77.
Definition 1 (Self consisconsi equations) The set of quantities and Ô are defined as the solution of the following set of non-linear equations that are referved to as self- relf-consistent equations. Let w and ú# be the solution of the following one-dimensional randomized optimization problems:
Q Qw= how + Xr(w),
W arg min
(15)
WER
2
u²
0 arg min aeR
(16)
2xA
where
h = m + V8Ew + Vonw: Eur Tho ~ No0 1), h = B m VOEu + Vonu. Enr Tu ~ N0, A),
(17)
(18)
and c+ ~ N C ~ De- Then, the self-consistent equations are given as follows:
d
= E Be dh w
(19)
9 [(. (E [w]]]
(20)
m = E The ~((.1) [w]
(21)
E (m V \ Ww
(22)
Q 1
a d 0+ a-
d dhn
E
(23)
X
dhi
8 =
EE.~N(O.s)
a Mnma) 10+ + E
(24)
Ax²
1
E
latat a - ú_
(25)
Ax
0 EE,-N(0,S)
av wTT.VNNN...s.cooooo [ut V [6
(26)
Ax²

---

Published in Transactions on Machine Learning Research (07/2024)
Furthermore, depending whether the bias is estimated or fized, the following equation is added to the self-consistent equation
0 (o..n.a((..)))). latat +a when bias is estimated
(27)
B = B,
when bias is fixed
It is also noteworthy to comment the interpretation of the parameter B and (q. m,v) in the self-consistent equations.
Claim (Intcrpretation of the paramcters Q) At the LSL, the solution of the self-consistent equations are related with the weight vector ib D) as follows:
N
lim
Ec (c, D)}?
(28)
N
N
1
lim
Ec (c, D)],
(29)
N
N
V lim
Ve (c, D)]
(30)
N
N
1im B(c, when bias is estimated
B
(31)
B
when bias is fixed
That is, m, v. B represents the squared norm of the averaged weight vector, the inner product with the cluster center, the variance with respect to the resampling, and the bias, respectively, at LSL.
Using the solution of the self-consistent equations, we can obtain the following expression for the average of the prediction.
Claim (I-th moments of the predictor) Let (B, m. U, be the solution of the self-consistent equation Definition and let 1, ... N be the non-negalive integer. Also, 8* D) = = át(c, D)/VN + i D) and 5 D) + -lc VN be the predictions of the estimator 7 for an input x which is generated as
x = +IN/VA
rid Pe, E [N].
(32)
Then, for any 1, we can obtain the following result regardless of whether the bias is estimated or not:
ED [Ba[v(s*)]]] = (G.-N(0..) [E +m+ VOEw + Vonw)l
(33)
where sa arbitrary as long as the above integrals are convergent.
This result indicates that the fluctuation with respect to resampling conditioned by æ is effectively described by the Gaussian random variable nu, and the fluctuation with respect to the noise term in æ is described by the Gaussian random variable &.. Schematically, this behavior be represented as follows:
+
(+m)
VeL. fluctuation from the noise
Vonu fluctuation from random reweighting conditioned by #
(34)
bias
correlation with cluster center
Therefore, the distribution of the prediction averaged over K-realization of the reweighing coefficient {cx K can be described as follows.
Claim 3 (Distribution of the averaged prediction) Let (B, m. be the solution of the self- consistent, equation in Desinition 1 Then, the distribution of x Ek w(c,, D)/V////// B(cs, D) (or

---

Published in Transactions on Machine Learning Research (07 2024)
0.8
0.15
K
4
0.3
K
0.6
K-
64
64
pal
0.2
pdr
0.10
0.1
0.2
0.0
0.0
0.00
-4
-2
0
2
-6
-3
0
3
6
15
-10
-5
5
10
15
K
$
K
(a)
M+
v) = (0.01, -1)
(b)
Mr M
v) = (0.05, -1)
(c)
MT
v) (0.2, -1)
M
M
0.8
K
K
0.15
0.3
K
0.6
pdf
pdi
0.2
pdf
0.10
0.1
0.05
0.2
0.0
-3
-2
-1
0
1
2
3
-6
-3
10
-5
10
15
K
K
(d)
M M .3) (0.01, +1)
(e)
Mr M 8) (0.05, +1)
MT (1) (
M y) (0.2, +1)
Figure 1: Comparison between the empirical distribution of s (histogram), which is obtained by a single realization of the training data D of finite size with N = 213, and the theoretical prediction in Claim 3 (dashed). Different colors represent resampling averages with different numbers of realizations of reweighting coefficient c.
K B when the bias is flaed), the prediction averaged over K-realization of the reweighing coefficient {cu]km when the noise term fluctuates, is equal to that of the following random quantity:
B + m Voa + K
Na; Eu, ~ NNO, A).
(35)
K
The US, which uses single realization of the resampled data set, corresponds to the case of K 1. Using the above result, one obtains the expression of the F-measure as follows:
Claim (F-measure) Let (g. m, u. B) be the solution of the self-consistent equations in Definition 1 Then, for 8 Ek x. (0(r, D)/ /N + B(cx, D) (or B when the bias is fised), the prediction averaged over K K-realization of the reweighing coefficient {cH] the specificity S, the recall R, and the F F-measure are given as follows:
m + B
S= H
(36)
VA(a x)
m + B V R)
R = 1 1- H
(37)
F 2
(38)
3 +
R
where H-) is the complementary error function:
H(x) (g [T(E > x))-
(39)
9

---

Published in Transactions on Machine Learning Research (07 2224)
100
25
75
1.5
50
15
10
0.0
10" 2
10
16
10"
10
(a) (vA, A) (1.5, 10
(b) (vA, X) (1.5, 10
(c) (v A X) (1,5,10
X (N
30
(N
100
1.5
(N 2
m (N 2
10
50
10
0.5
(N 2
(N 2
B
B (N 2"
10
10
10
1d
10a²
10'
B (N 2
(d) (VA, A) = (0.75, 9)
(e) (vA, A) = (0.75, 775,10 10
(f) (v A, X (0.75, 10
255
2.0
100
80
15
10
20
10.
10'
10
10'
10 10'
a-
(g) (VA,A) (0.5, 1)
(h) (VA, (0.5, 10-3)
(VA,)) (0.5, 10-1)
Figure 2: Comparison of the comparison of (q, m, v, B), obtained as the solution of the self-consistent equation (lines), and (N- Σ; Ee (c, D)J N Ee D)J, - -. V _ (c, D)1, B(c, D)) (markers with error bars). Reported experimental results are averaged over several realization of D depending on the size N. The error bars represent standard deviations. Each panel corresponds to different values of (A, A). Different colors of the lines represent the result for different input dimensions N.
We remark that for any K 2 1, the variable m, which represents the correlation between the cluster conter
u and the weight. vector ár(e, D) a constant, that is, the bagging procedure just reduces the variance of the prediction and does not improves the direction of the classification plane. An important consequence is that for any regularization parameter À > UB with K >> is higher value of the F-measure when B 0 and > 0, indicating the superiority of UB over US.
3.1 Cross-checking with numerical experiments
To check the validity of Claim which is the most important result for characterizing the general- ization performance, we briefly compare the result of numerical solution of the self-consistent equa- tions with numerical experiments of finite-size systems. We also compare the values of (g. m, v, B) with [, (c, D)]2, N, Ee[wi(c, D)), N- Ve(miic, D)}, (ec obtained by numerical experi- ments with finite N, that is, the hight-hand-siee of equations in Claim [ but with finite N.
We consider the case of subsampling (8- For the loss function, we use the cross-entropy loss; I+ (x))) and 1-(x) log(1 (x)),, where a(.) is the sigmoid function. The regularizer is the ridge:
10

---

Published in Transactions on Machine Learning Research (07/2024)
r(z) = =2/ Also, the bias is estimated by minimizing the loss as in 7 In experiments, the scikit-learn package is used (Pedregosa et al. 2011). For simplicity, we fix the size of the overall training data (M+ + M = 1/2. For evaluating the distribution of k empirically, we use 10 examples of x=
Predictive distributions Figure I shows the comparison between the distribution in Claim 3 and the empirical distribution obtained by experiments with single realization of the training data D of finite size N = 213 Different colors corresponds to different numbers of samples for the resampling average. Each panel corresponds to a different set of (M+/M, y, N), where y is the label to indicate positive (v = 1) or negative (y- = -1) classes. For simplicity, we fix the regularization parameter as À = 10-4, and the variance of the noise as A 0.75². In all cases, they are in good agreement, demonstrating the validity of Claim 3 and Assumption See Appendix
B for the result with smaller N.
Parameters Figure shows the comparison of (g, m, v, B), obtained as the solution of the self-consistent equation, and (N-1 Σ, E [1, D) N E, Be[0, D) Σ, Velw,(e, DJ}, B(c, ((e,,D) D)). The values are plotted as functions of o at, the difference of the normalized size of the majority and the minority classes. Each panel corresponds to a different set of (A, VD). For mumerical experiments, two different input dimensions N = 256(= 28), and 2048(= 2 are used. To take the average over c, 128 independent realizations are used. Reported experimental results are averaged over several realization of D depending on the size N. The results show that the theoretical predictions and the experimental values are in good agreement. Also, the error bars represent standard deviations that decrease as N grows, indicating the concentration of these quantitics. Overall, the figure confirms the validity of Claim
4 Under-bagging and regularization
In this section, using Claim 4 we compare the performance of several estimators, that is, US, UB, and SW. In the following, we consider the limit K - 0o in -31-137 which yiclds the smallest variance.
For simplicity, we focus on the case of ridge-regularized cross-entropy loss as in subsection sampling method, we mainly focus on the sampling without replacement defined as ()- 99. except for subsection 4.3 When sampling without replacement B(c, D) to be zero, since the number of positive and negative samples is balanced. See also Figure 2 Therefore, we set the bias to zero priori when using sampling without replacement. Otherwise, the bias is estimated as in 77) Furthermore, investigated in the previous studies (Dobriban & Wager 2018 Mignacco et al. 2020), when training a linear classifier using balanced data and a ridge-regularized cross-entropy loss, an infinitely large regularization parameter yields the best direction for the classification plane. Hence we obtain infinitely large regularization parameter we optimize the regularization parameter. However, as reported in (Mignacco el al. 2020; Takahashi 2024), the discrepancy between the theory and experiment with finite N can be huge too large regularization parameter is used because the norm of the weight vector can be pathologically small. Therefore we consider several finite and fixed regularization parameters instead of optimizing them
As a re-
usod, we can expect that the estimated bias term
4.1 US and UB
In this subsection, we compare the performance of US and UB, through the values of F-measures.
Figure 3 shows the dependence of the F-measure F on - a+, which is the difference in the scaled size between the majority (negative) and minority (positive) classes, or equivalently, the scaled size of the excess majority examples. Each panel corresponds to different values of the variance A and the regularization parameter X. Rocall that the F-mcasure is uppder bounded by unity. In UB, the F-mcasure increases monotonically as the number of excess data points in the majority class a' - a increases, despite of the large class imbalance. However, in the case of US, the F-measure does not depends on a - at, i.e., it is not affected by the class imbalance, but cannot utilize the excess data points in the majority class. This
3T we consider nom-symmttric Gaussian cluster setups, the optimal regularization parameter would be non-trivial values, but this is beyond the scope of this work, and leave here as future work.
11

---

Published in Transactions on Machine Learning Research (07 2204)
1.0
1.0
1.0
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
10"2
10
10
10"2
10
10
10"²
10
10
0
a
a
a
(a)
(vā, A) (1.5, 10 10
(b) (v A) (1.5, 10
(c) (v A) (1.5,10))
1.0
1.0
1.0
0.9
0.9
0.01
a
0.03
0.8
5. 0.8
6. 0.8
a
0.1
0.31
1.0
0.7
0.7
3.27
10.0
0.6
0.6
10
10"
10
10"²
10
10
10
10
10
(d) (VA, A) = (0.75, 10 10
(0)
(v A, A) - 10.
(f) (v A) = (0.75, 10
1.0
1.0
1.0
0.9
0.9
0.9
0.8
0.8
0.7
0.7
0.7
10a2
10
10
10a2
10a
10
10"²
10
10
a
a
a
(g) (VA,A) A) (0.5, 10 10-3) 3)
(h) (VA. X) (0.5, 10-1)
(i) (VA, (0.5, 10
Figure 3: Comparison of the dependence of the F-measure F on a which is the difference in the size between the majority (negative) and the minority (positive) classes, between US (dashed) and UB (solid). Each panel corresponds to different values of (). Different colors of the lines represent the result for different sizes of the minority classes a+.
tendency does not depend on the values of (A, A). Actually, when subsampling is used as the resampling method, one can show that the performance of the classifier does not depends on a a as shown in Appendix Intuitively, this is because considering uniform subsampling without replacement essentially is just using smaller size of negative examples.
C
Figure $ shows heatmap of the relative F-measure Fun/Fus, where FUB and Fus are the F-measure for UB and US, respectively. It is clear that the values of the F-measures are improved when the variance is small, the size of the minority class is small and the excess size of the majority class is large. When the variance is large, the improvement at extremely small a region is small because m in (38) can small due to the large overlap between two clusters. We remark that the boundary where data is linearly separable/inseparabb /inssparaabaeeeeeee is roughly in the region of a (10%, 10²) (see Figure 5). Therefore, the large improvement in generalization performance below this boundary indicates that UB is effective in the overparameterized settings, as indicated in the literature WWallace et al. 2011)
4.1.1 Double-descent-like like behavior
It is also noteworthy that the improvement may be large around some values of a when the regularization parameter is extremely small. This is because the variance associated with random reweighting coefficient
12

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
1.100
1.06
10
1.075
10
16
1.04
1.03
1.02
1.025
1.01
1.01
10
10
10-7
10
1df
10
10
1df
10
10"
100
10
(a) (v A) = (1.5, 10
(b) (Vā, A) = (1.5,10
(c) (VA, A) (1.5, 10
1.08
1.07
1.07
1.07
1.06
1.06
16
10
10
1.05
1.05
1.05
1.04
1.04
1.04
1.03
1.03
1.03
1.02
1.02
1.01
1.01
1.01
10
10
10-2
10"2
1d
10
10"2
10f
10
10
10
10
(d) (V2,)) = (0.75, 10 10-5)
(e) (VA, (0.75, 10-1)
(I) (VD, (0.75, 109)
1.09
1.09
1.08
1.08
1.08
1.07
1.07
16
1.06
10
10
1.05
1.05
1.04
1.04
1.03
1,02
1.01
10
1
1df
10²
10
10
10
10 2
10
10a
(g) (V = (0.5, 10 10
(h) (VA, = (0.5, 10
(i) (V = (0.5, 10
Figure 4: Heatmap plot for the relative F-mcasure FUB/Fus, where FUB and Fus are the F-measure for CB and US, respectively. Each panel corresponds to different values of (A,A).
с exhibits double-descent-like behavior with respect to a and takes large value at certain at. This point evident in Figure that shows the relative variance v/(q + u) for several values of A. is clear that the relative variance lakes a peak value at the interpolation threshold obtained by the formula the logistic regression with balanced two-component Gaussian mixture with data size a N (Mignacco al., 2020). Similar double-descent-like behavior is also observed an analysis of bagging without class imbalance structure (Clarté al. 2024). This indicates that the UB, which can remove the contribution from v, is robust to the existence of the phase transition from linearly separable to inseparable training data, although the performance of standard interpolator obtained by single realization of training data is affected by such a phase transition as reported [Mignacco et al. 2020
4.2 UB and SW
In this section, we compare the performance of UB with SW, through the values of F-measure. For SW, we consider two types of weighting coefficients y The first choice is
(Ntaive Ynaive) ((M+ + (-)/(2M+),, (M+ M-))(2M-)), which is a naive guess often used the default value of the major MI. packages such as the scikit-learn (King & Zeng 22001 Podregosa al. 2011 Another scenario considers the where the weighting coefficients are optimized so to maximize the F-value using the Nelder-
13

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
0.6
0.5
log u
0.5
0.4
12 0.4
0.3
0.3
log a
0.2
0.2
0.1
0.1
0.1
0.0
0.0
0.0
10 2
10
10"
2
10
10"
10
+
(a) (V = (1.5,10 10
(b) (v A) (0.75, 10
(c) (V A) (0.5, 10
0.5
0.40
16
10
0,35
0.30
1d
0.3
0.25
0.25
0.20
0.20
0.2
0.15
0.15
0,10
0.05
0.05
10
10-
10
10"2
10f
10
10"2
10
10
10
10
10
(d) (VA. = (1.5, 50
(e) (VA, A) = (0.75, 10 10-8)
(1) (VA, = (0.5, 10-5)
Figure Relative variance v/(q + v). Upper panels: the relative variance shown as a function of a for some selected values of a at The legend is common across all panels. Red dashed lines represent the interpolation threshold. Lower pancls: the relative variance shown 2d-heatmap.
Mead method in Optim.jl package (Mogensen & Riseth 2018
In order to make fair comparison with the UB with the regularization strength X, the regularization parameter for the SW with optimal weighting coefficient is optimized in the range below Aus < (7itaive + J For simple weighting with the naive coofficients, the regularization paramcter just fixed as a constant valuc.
Figure Sigure@ssower shows the comparison of the a - dependence of the F-measure between UB and SW for selected values of at. It is clear that the performance of UB (solid line) and SW with the optimized coefficients (dashed line) are comparable in all cases. This is more clearly evident in the heatmap in Figure 7 which shows that the relative F-measure (FuB Fsw)/FuB is within about 1 + 10 On the other hand, the performance of the SW method with the naive weighting coefficients Tnaive (dash-dot)) is catastrophically worse than UB where a is small and a- a is large. As a - a increases, the F-measure decreases monotonically. See also Figure 13 in Appendix D for a heatmap view. Figure shows the ratio between the optimal and naive weighting coefficients. It is clear that when the variance cocfficient for the majority class (dash) should be reduced by an order of magnitude from the naive value, indicating that delicate tuning of the weighting coefficients is needed for the SW method.
the cluster is large, the
These results indicate that the combination of the weighting and regularization can be similar to the combina- tion of the under-sampling and bagging, although UB does not require delicate adjustment of the resampling rale.
4.2.1 UB and SW in real-world dataset
Unfortunately, it is unclear whether the above similarity between bagging with class-dependent resampling and weighting generally holds beyond Gaussian data. However, to verify the universality of the similarity between SW with the optimal coefficients and UB, we show here the results of simple experiment using Fashion-MNIST data (Xiao et al. 2017), which consists of N 28 784 dimensional images from 10 classes. For this, we performed binary classification with the logistic regression using the classes "T-shirt/top and "Shirt". Specifically, we chose the "T-shirt/top" class as positive class and extracted M+ 50 data
14

---

Published in Transactions on Machine Learning Research (07 /204)
1.0
1.0
1.0
0.9
0.9
0.9
0.8
0.8
0.8
0.7.
6. 0.7
6 0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.4
0.4-
0.4
10"²
16
10
10"²
10
10
10"²
10f
10
0
0
0
a
a
a
(a)
(vA, A) (1.5, 10 3)
(b)
(vA, X) (1.5, 10
(c) (v A) (1.5,10))
1.0
1.0
1.0
0.9
0.9
0.9
0.01
0.8
0.8
0.8
0.03
01
0.7
0.7
0.7
0.31
0.6
0.6
0.6
1.0
3.27
0.5
0.5
0.5
10.0
10
10d
10
10-²
10
10
10
10
10
(d) (v A, A) = (0.75, 10 10
(e)
(v A, A) = (0.75,10
10
(f) (v A A) (0.75, 109)
1.0
1.0
1.0
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.6
0.6
0.6
0.5
0.5
0.5
10
10
10a
10
10a
10
10
10
10
-a"
a
Q
(g) (VA, (0.5, 10-3) 3)
(h) (VA, A) (0.5, 10-1)
(i) (V A) (0.5,
Figure 6: The comparison of the dependence of the F-measure F on a' - at, which is the difference in the size between the majority (negative) and the minority (positive) classes, between weighting with optimal coefficients (dashed), weighting with naive coefficients (dashdot), and UB (solid). Each panel corresponds to different values of (A, A), where À is the regularization parameter. Different colors of the lines represent the result for different sizes of the minority classes at.
points. Then, the size of the "Shirt" class, which was specified as negative, was varied from M- = 51 to 3000 to check the behavior of the F-measure and the weighting coefficients. The weighting coefficients were optimized using validation data with 400 images, and the F-measure was computed using test data with 1600 images.
Figure g shows the results of the experiment. The behavior of the F-measure and the weighting coefficients are similar to those observed for Gaussian mixture data in Section The performance of SW with the naive coefficients drops rapidly with the number of excess majority samples. However, the performance of SW with the optimal coefficients is similar to that of UB. Moreover, the optimal weighting coefficients for the majority class are several orders of magnitude smaller than the naive coefficients, although the statistical fluctuation is large.
Of course, a more thorough experiment or theoretical proof is needed to fully verify the universality of the above results, but this is beyond the scope of this study and is left future work.
15

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
101
10
10
10
10
100
10-1
10-1
10-1-
10
10:2
10
10-2
10
10a
10-2
10
10a
10-2
10
102
a
a
a
0
(a)
A, A) (1.5,10")) 10
(b) (vA, A) = (1.5, 10
(c) (v A, A) = (1.5, 10")
10
10
10
0.010
10
10
10
0.005
10-1
10-1
10-1
0.000
10 2
10
10
10.2
10
10a
10
10
102
10
10
102
a
-a"
a -a a
a
(d) (VA,)) A) (0.75, 10
(e) (V4, = (0.75, 10
(I) (vA, A) = (0.75, 10
-0.005
10
10
10
10
10
10
10-1
10-1
10-1
10-2 .
10-2
10
10-2
10
10a
10:2
10"
102
10
10"
102
a-
a
a
(g) (VA,)) (0.5, 10
(b) (VA. (0.5, 10
(i) (V (0.5, 10
Figure The heatmap plot for the relative F-measure: (FUB Fsw)/FUB, where FUB and Fsw are the F-measure for UB and the weighting method, respectively. Each panel corresponds to different values of (A,A), A), where À is the regularization parameter used in UB.
4.3 Sampling with and without replacement
replacement and without ( replacement. The difference between these resampling methods mainly whether or not the resampled data contains multiple instances of the same data point. We are interested in whether this makes significant performance difference in terms of the F-measure.
In this section, we compare the behavior of the estimators obtained by sampling with 10
Unlike sampling without replacement, which we have considered so far, the expression for the optimal resampling rate cannot be obtained explicitly even in naive sense. In this paper, motivated by the fact that the F-measure considered here treats the classification error equally for positive and negative samples, we numerically find the resampling rate such that the bias term is estimated to zero. As shown in Appendix E. the F-mcasure actually takes the highest value at this resampling rate. Morcover, we focus on the case of A 0.75?, since it is expected from the results of sampling without replacement so far that the qualitative behavior of the F-measure does not strongly depend the value of A.
16

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
16
1.0
1.00
50.
10"1
20.75
0.8
10
0.25
10"²
10
10
10
10
10'
10
10
10
a
a
0
0
-0"
(a) (VA, A) (1.5, 10 3)
(b) (vA, A) = (1.5, 10
(c) (v A, A) (1,5,10)
10P
1.1
1.000
1.0
0.03
0.9
0.975
0.1
20.8
80.950
10
0.7
10
3.27
0.6
0,900
10.0
0.5
0.875
10"2
10
10
10-2
10
10
10"2
10
10
(d) (vA, A) (0.75, 10 3)
(e)
(v A, A) (0.75, 10 10"1)
(f) A, A) (0.75, 109)
16
1.0
1.00
0.99
50.9
0.98
0.8
0.97
10-1.
0.96
0.7
0.95
0.94
10
10
10
10
10"
10
10
10
10a
(g) (VA, (0.5, 10-3)
(h) (v (vA, (0.5, 10-1)
(i) (VΣ, (0.5, 10
Figure 8: The comparison the weighting coefficients / as function of a The ratio for the majority class is shown by dashed lines, and that for the minority class is shown by solid lines. Each panel corresponds to different values of (A, A), where À is the regularization parameter for UB. Different colors of the lines represent the result for different sizes of the minority classes a
Figure 10 shows the comparison of the F-measures obtained by sampling with and without replacement. Pancls (a)-(c) show the F-measures for the UB cstimators obtained by each resampling method. It is clear that the predictive performance of the UB estimator shows little difference between sampling with and without replacement in terms of the F-measure. In particular, they agree almost perfectly for a -aa > 1, because the resampling rate pa for sampling with replacement is small in this region and there are almost no duplicate data points. On the other hand, for a - a < 1, sampling with replacement shows slightly better performance than sampling without replacement, because sampling with replacement induces more variation in cach of the resampled data, and the regularization effect of ensembling can be stronger. Recall that cach resampled data set produced by sampling without replacement is nearly identical when a a < 1. Also, shown in panels (f)-(f), the performance of the US estimator depends slightly because the size of the resampled majority class data is not constant due to the effect of duplication of the data points.
at. This is
Figure II shows the resampling rate, which is the expected size of the resampled majority class data, to make the bias term zero. As expected, there is almost no difference between the two resampling methods for a + > 1 since the effect of duplication quite small. However, the resampling rate of sampling with replacement larger than the other for a a & because large resampling rate is required to
17

---

Published in Transactions on Machine Learning Research (07 /024)
Hall
0.8
10
0.7
6.
0.6
10
Tuairo
I
naive weighting
Yopt
0.5
opt. weighting
10
UB
Yoopt
10
10-2
10-1
10
10
10
10 (M M 1/N
10
(M M )/N
(a) F-measure
(b) y
Figure 9: F-measure and weighting coefficients in the Fashion-MNIST data. Markers with error bars represent the experimental results. Dashed lines represent the naive reweighting coefficients: 7tt (M+ + (22M Here, N 28 784. The regularization parameter is set to X 10-3, Error bars are constructed from 2.5 and 97.5 percentile points over 64 independent random train and validation splits.
1.0
1.0
1.0
0.9
0.9
0.9
0.8.
6.0.8
6. 0.8
0.7
0.7
0.7
0.6
0.6
0.6
10
10º
10
10a
10
10a
0.01
-a
-a
-
(a)
UB: (VA, A) (0.75,10 10 3)
(b)
UB: (VA, (0.75, 10-1)
UB: (vA, A) (0.75,
01
0.31
1.0
1.0
1.0
10
3.27
10.0
6,00
6, 0.8
0.7
0.7
0.6
0.6
3
10a
10
100
10a
10a
(d) US: (VA, = (0.75, 10
(e) US: (VA,)) A) (0.75, 10
(f) US: (VA, A) (0.75, 10
Figure 10: The comparison of the dependence of the F-measure F on a- aa which is the difference in
the size between the majority (negative) and the minority (positive) classes, between sampling with (solid) and without (dashed) replacement. Pancls (a)-(c): the comparison between UB estimators. Pancls (d)-(c):
the comparison between the US estimators. The variance is fixed to VA 0.75.
include all majority class data points each resampled data, suggesting that sampling without replacement is superior in terms of computational efficiency.
18

---

Published in Transactions on Machine Learning Research (07 /024)
2.0
1.00
1.2
1.5
0.75
0.01
0.9
0.03
1.0
0.6
0.50
0.1
0.5
0.3
0.25
10
3
0.0
0.0
0.00
10.0
10
10
10
10
10"a
10a
0
0
0
a
(a) (vD, A) (0.75, 3)
(b) (v (0.75, 10
(c) (vā, (0.75, 10")
Figure 11: The comparison of the dependence of the optinal resampling rale μ. on a- a+ between sampling with (solid) and without (dashed) replacement. The variance is fixed to VA = 0.75.
5 Summary and Discussions
In this work, we derived a sharp asymptotics of the estimators obtained by the randomly reweighted losses ( in the limit where the data size and the input dimension diverge proportionally. The derivation was based on the standard use of the replica method. The results are summarized in Claim 15
Using the derived sharp asymptotics, we investigated the performance of UB, US, and SW. Our main findings were (i) UB can improve the performance of the classifier in terms of the F-measure by increasing the size of the majority class while keeping the size of the minority class fixed, even when the degree of class imbalance becomes large, (ii) the performance of the classifier obtained by US was almost independent of the size of the excess majority examples, and (iii) the performance of the SW method was almost. equivalent to UB the weighting coefficients are carefully optimized, but if not properly adjusted, the performance drops rapidly as the number of the excess majority examples increases. (iv) Furthermore, UB was robust to the interpolation phase transition in contrast to US. In conclusion, ensembling and ridge regularization are different when using under-sampled data. This result is different from the of naive bagging in training GLMs without considering the class imbalance structure, where ensembling with uniform resampling rate and the simple ridge regularization give exactly the same performance. Rather, UB is similar to the combination of the weighting method with optimal weighting coefficients and the ridge regularization. These result may indicate that one can obtain performance improvements considering class-dependent resampling or rewcighting in learning classifiers from imbalanced data contrast to the past results Nixxn et al. 2020).
Although UB is a powerful method for learning in imbalanced data, it requires an increased computational cost proportional to the number of under-sampled datasets, which be scrious problem in learning deep neural networks. Therefore, the development of simple heuristics to achieve similar results as UB would be promising future direction.
Acknowledgments
This study was supported by JSPS KAKENHI Grant No. 21K21310 and 23K16960, and Grant-in-Aid for Transformative Research Areas (A), "Foundation of Machine Learning Physics" (22H05117).
References
Ryo Ando and Fumiyasu Komaki. On high-dinnensional asymptotic properties of model averaging estimators. arXiv preprint arXiv:2308.094F79 2023.
Jean Barbier and Nicolas Macris. The adaptive interpolation method: simple scheme to prove replica formulas Bayesian inference. Probability Theory and Related Fields, 174(3):1133 1185, August 2019. ISSN 1432-2064. doi: 10:1007//00444000088887779909 http://////////aaaoo///////////0
19

---

Published in Transactions on Machine Learning Research (07/2024)
Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12):5451 5460, 2019.
Pierre C Bellec and Takuya Koriyama. Asymptotics of resampling without replacement in robust and logistic regression. arXiv preprint (iXi::244.0000000 2024.
Leo Breiman, Bagging predictors. Machine learning, 24:123 140, 1996.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In Kamalika Chaudhuri and Ruslan Salakhutdinov (ods.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 872 881. PMLR, 09 15 Jun 2019. CRL httpss:/prroceedingg/ mlr, www.erpesseeeo httpas/vv////// h9r/byd. html
Patrick Charbonneau, Enzo Marinari, Mare Mézard, Giorgio Parisi, Federico Ricci- Tersenghi, Gabriele Si- curo, and Francesco Zamponi. Spin Glass Theory and Far Beyond. WORLD SCIENTIFIC, 2023. doi: 10.1142/13341. URL
111///334111
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
Lucas Clarté, Adrien Vandenbroucquu, Guillaume Dalle, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborova. Analysis of bootstrap and subsampling in nigh-dimensional regularized regression. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. URL htttps://openreviiew wtw.eerrrrvieeeneeffunnnmm
1d yd=y2aX33OxVS
Gilles Cohen, Mélanie Hilario, Hugo Sax, Stéphane Hugonnet, and Antoine Geissbuhler. Learning from im- balanced data in surveillance of nosocomial infection. Artificial Intelligence in Medicine, 37(1):7-18, 2006. ISSN 0933-3657. doi:
a00m 00000.0000022. URL http:: http:://wwwwwsee www.sccienceiirec... Intelligent Data Analysis in Medicine.
Stéphane D'Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance(s) in the lazy regime. In Hal Daumé III and Aarti Singh (ods.), Proccodings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. PMLR, 13 13-18 Jul 2020. URL httpps://proceedings mlr www.ppressvvviie http:///v11//aaaolll1a1a html
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018. ISSN 00905364, 21688966. URL https:
//www.jster org/ st//s////ee22//424/4
Chris Drummond, Robert C Holte, et al. C4. 5, class imbalance, and cost sensitivity: why under-sampling beats over-sampling. Tn Workshop on learning from imbalanced datasets IT, 2003.
Jin-Hong Du, Pratik Patil, and Arun K. Kuchibhotla. Subsample ridge ensembles: Equivalences and gen- eralized cross-validation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlott (ods.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 8585-8631. PMLR, 23-29 Jul 2023. URL
.ml...gss..r......m.. wttp://nnn........ss///////oo/./ du23d.
A. Engel and C. Van den Broeck. Statistical Mechanics of Learning. Cambridge University Press, 2001.
Oliver Y. Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth. A unifying tutorial on approximate message passing. Foundations and Trends@ in Machine Learning, 15(4):335-530 2022. ISSN 1935-8237. doi: 02.1601/2000000992 URL http://dx
htt.tt:://dx.ddorrrrrrg www.o/./........o.ooo 1ttp///00.161//220000099
Federica Gerace, Bruno Lourciro, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. Gencralisation error in learning with random features and the hidden manifold model. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings
20

---

Daniel LeJeune, Hamid Javadi, and Richard Baraniuk. The implicit regularization of ordinary least squares ensembles. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine press/ Published in Transactions on Machine Learning Research (07/2024)
of Machine Learning Research, pp. hhtml
PMLR, 13-18 Jul 2020. URL htsL:tttsp//rocceedigss.. mlr.
Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, (1)):1263-1283) 2009. doi: 1000000D..000......
Adel Javanmard and Andrea Montanari. Hypothesis testing in high-dimensional regression under the gaus- sian random design model: Asymptotic theory. IEEE Transactions on Information Theory, 60(10))6522 6554, 2014a. doi: 10.1109/TTI 2014.234362..
Adel Javanmard and Andrea Montanari. Confidence intervals and hypothesis testing for high-dimensional regression. Journal of Machine Learning Research, 15(82):2869 2909, 2014b. URL
org/
(opers//155/avammett
html
Justin M. Johnson and Taghi M. Khoshgoftaar. Survey on deep learning with class imbalance. Journal of Big Data, 6(1):27, March 2019. ISSN 2196-1115. doi: 10.1180//440337--111009222 URL https:
//doi org/10..110 0111/111//337-1199900 0100//001116//0055---0----1---11
Salman H. Khan, Munawar Hayat, Mohammed Bennamoun, Ferdous A. Sohel, and Roberto Togneri. Cost- sensitive learning of deep feature representations from imbalanced data. IEEE Transactions Neural Networks and Learning Systems, 39(8):357333555) 2018. doi: 10.1109/TNNTS.201111
Gary King and Langche Zeng. Logistic regression in rare events data. Political Analysis, 9(2):137-163, 2001.
doi: 10. /wtpo//oooonall..aann.aaoo
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparamettrrization. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 18970 18983. Curran Associates, Inc., 2021. URL Itttps:/proceddings pddf
Anders Krogh and Peter Sollich. Statistical mechanics of ensemble learning. Phys. Rev. E, 55:811 825, Jan 1997. doi: D0.1103/PhysRevea
URL https::/link: wrw.app......a.o..... hrgg//o./10.110//hhheeeeee
Florent Krzakala and Lenka Zdeborová. Statistical physics methods in optimization and machine learning. Notes. pdf, 2021.
Learning Research, pp. 3525 3535. PMLR, 26 28 Aug 2020. URL v108/1ejeune20b.co
Tsung-Yi Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollar. Focal loss for dense object detection. In Proceedings of the IEEE International Conference Computer Vision (ICCV), Oct 2017.
Emanuele Loffredo, Mauro Pastore, Simona Cocco, and Remi Monasson. Restoring balance: principled /oder//versampling of data for optimal classification. In Forty-first International Conference on Machine Learning, 2024. URL htttps://ppereviiee http:s//ppppaeeeeeeeeeee//ooorrp
Rushi Longadge and Snehalata Dongre. Class imbalance problem in data mining review. arXiv preprint arX1v:1305.1707, 2013.
Bruno Lourciro, Gabriele Sicuro, Codric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zde- borová. Learning gaussian mixtures with generalized linear models: Precise asymptotics in high- dimensions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (ods.). Advances in Neural Information Processing Systems, volume 34, pp. 10144-10157. Cur- ran Associates, Inc., 2021. URL 7235e3377422444472222222 /aa.4//444eaaba//aaaaaaaaeeeeare wew.ooeedinggs.uuripss..... htt.://wwwp.pppppppeeee/e///r//p /ttpp///ssseeppp////////////////
21

---

Published in Transactions on Machine Learning Research (07/2024)
Bruno Loureiro, Cedric Gerbelot, Maria Refinetti, Gabriele Sicuro, and Florent Krzakala. Fluctuations, bias, variance &; ensemble of learners: Exact asymptotics for convex losses in high-dimension. In Ka- malika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.); Proccodings of the 39th International Conference on Machine Learning, volume 162 of Procoedings of Machine Learning Research, pp. 14283 14314. PMLR, 23 Jul 2022. URLhhttss. httttpp://rrooeeiings. mlr. prees//v1//lourerr222.... html
Dörthe Malzahn and Manfred Opper. A variational approach to learning curves. In T. Dietterich, S. Bocker, and Z. Ghahramani (ods.), Advances in Neural Information Processing Systems, vol- une 14. MIT Press, 2001. URL httpps:/ htw.ooeedddnnnneeeiii.p..pp www.:neuuuccceeeee wttpccppppp.lpee/eeeeeee.ceeeeee /ttaapps..cppppee..lllll//////// ffiles//paper/201/ille 2BFoddaaaeEFFa000152226666600000 pdf
Dörthe Malzahn and Manfred Opper. Statistical mechanics of learning: A variational approach for real data. Phys. Rev. Lett., 89:108302, Aug 2002. doi: 10.
URL /attps://link. aps.
org/doi/10. http://....1////eeeeeettt......
108302
Dörthe Malzahn and Manfred Opper. Learning curves and bootstrap estimates for inference with gaussian processes: A statistical mechanics study. Complexity, 8(4):57-63, 2003.
Stefano Sarao Mannelli, Foderica Gerace, Negar Rostamzadch, and Luca Saglictti. Bias-inducing goometries: exactly solvable data model with fairness implications. In ICML 2024 Workshop on Geomelry-groundde Representation Learning and Generative Modeling, 2024. URL httg::///paareevieee.ntfffoooooo oupizzpMpy
Song Mci and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667 766, 2022. doi: https:/ //oi.org/ 1////100..00/pppee./ 22008. URL https://oollinelibbaayy http://ccoo//oo//////ooo..
cp002
Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy gaussian mixture. In International Conference on Machine Learning, pp.
PMLR, 2020.
Patrick Kofod Mogensen and Asbjorn Nilsen Riseth. Optim: A mathematical optimization package for Julia. Journal of Open Source Software, 3(24):615, 2018. doi: 10.21105/joss.000
Roweida Mohammed, Jumanah Rawashdeh, and Malak Abdullah. Machine learning with oversampling and undersampling techniques: Overview study and experimental results. In 2020 11th International Conference on Information and Communication Systems (ICICS), pp. 243-248, 2020. doi: 10.1109/
CCICS494499.0020.2330
Andrea Montanari and Subhabrata Sen. A friendly tutorial on mean-field spin glass techniques for non- physicists. Foundations and Trends@ in Machine Learning, 17(1):1-173, 2024. ISSN 1935-8237. doi: 10. 10.1561/2200000105. URL //ttp://dxx doi 1501000.1511/222000110
Jeremy Nixon, Balaji Takshminarayanan, and Dustin Tran. Why are bootstrapped deep ensembles not better? In "I Can't Believe It's Not Better!" NeurIPS 2020 workshop, 2020. URL https::/openrevvier.
het/foorum'id-dTCrrooes
Tomoyuki Obuchi and Yoshiyuki Kabashima. Semi-analytic resampling in lasso. Journal of Machine Learning Research, 20(70):1-33 2019. URL
html
html
Manfred Opper. Learning to generalize. Frontiers of Life, 3(part 2):763-775, 2001.
Manfred Opper and Wolfgang Kinzel. Statistical mechanics of generalization. In Models of Neural Networks III Association, Generalization, and Representation, pp. 251-009. Springer, 1996.
22

---

Published in Transactions on Machine Learning Research (07/2024)
Pratik Patil and Daniel LeJeune. Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning. In The Twelfth International Conference on Learning Representations, 2024. URL https: //openreview //oppnreriee..s///forrrr///////e wetf/forrurrrdddd1issiittt
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapcau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan. Are gaussian data all you need? The extents and limits of universality in high-dimensional generalized linear estimation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proccodings of the 40th International Conference on Machine Learning, volume 202 of Procoedings of Machine Learning Research, pp. 27680 27708. PMLR, 23 29 Jul 2023. httL:https:/// hattps://proceedingg: mlr.
press/v202/pesce25a. html
Peter Sollich and Anders Krogh. Learning with ensembles: How overfitting can be useful. In D. Touret- sky, M.C. Mozer, and M. Hasselmo (eds.), Advances Neural Information Processing Systems, vol- ume 8. MIT Press, 1995. URL https:://rooeeedngss new.eeeeeinnnnnnnnnnn....... httpa///ss.cpppppppe..aaaapp//ap fflles/papee//1///11
pdf
Pragya Sur and Emmanuel Candès. A modern maximmm--lkkellhooe theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516-14522 14525, 2019. doi: 10.1073/ p114.2810420116, URL httts:://www pnas. wwwp//o//gs///a/ooooooeoooaa 1073/100..ppp.... httpp/ppw....rraaaa///////0000/.
1810420116
Takashi Takahashi. Role of bootstrap averaging generalized approximate message passing. In 2023 IEEE
International Symposium on Information Theory (ISIT), pp. 767-772, 2023, doi: 10.1109/1SIT344713.220 10206490.
Takashi Takahashi. The role of pseudo-labels self-training linear classifiers on high-dimensiinall gaussian mixture data. arXiv preprint arXiv:2205.07739, 2024. URL https://arxivvorr//////2222
Takashi Takahashi and Yoshiyuki Kabashima. Replicated vector approximate message passing for resampling problem. arXiv preprint arXiv:1905.0954 2019. URL httpgs//arxiiv..rr//b/////5
Takashi Takahashi and Yoshiyuki Kabashima. Semi-analytic approximate stability selection for correlated data in gencralized linear modcls. Journal of Statistical Mechanics: Theory and Experiment, 2020(9): 093402, sep 2020. doi: 10. ababff
URL bittps://ah http://xxxdooiioo www.:oo.......oooooooo 2ttg///1...0///77755565653
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis regularized m estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5502-5622 2018. doi: 201.//TTT..21181000000
Byron Wallace, Kevin Small, Carla E Brodley, and Thomas A Trikalinos. Class imbalance, redux. In 2011 IEEE 11th international conference on data mining, pp. 754-763. Ieco, 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image datasct for benchmarking machine learning algorithms, 2017.
Qiang Yang and Xindong Wu. 10 challenging problems in data mining research. International Journal of Information Technology & Decision Making, 05(04):597 604, 2006. doi: 10.112//S12112220002223 www.ooo./11..... ottp///.....0//22150000002222220 URL /ttp::///oi.orr/11.11100.
Tianyi Yao, Daniel LeJeune, Hamid Javadi, Richard G. Baraniuk, and Genevera I. Allen. Minipatch learning as implicit ridge-like regularization. Tn 2021 TEEE International Conference on Big Data and Smart Computing (BigComp), pp. 65 68, 2021. doi: 10.1109/BBI. B1119///iCComp51266 /000////Biccmmm11112222000011111 202000
Han-Jia Ye, Hong- You Chen, Chaan Zhan, and Wei-Lun Chao. Identifying and compensating for feature dcviation in imbalanced deep learning. arXiv proprint xrXiv:2001.0338: 2020.
23

---

Published in Transactions on Machine Learning Research (07/2024)
Notation
Description
extra f(x)
extremization with respect to with æ E RN,, mcasure over RR with #1...., In R" measure over N identity matrix of size N x N for function F(x) and integer k, the partial derivative of F with respect to its argument at == y:
dæ d' IN
F*F(1)
F*x(x) Oxt ==y
f(n) Og](n)
Landau's 's O as n 0; [[(n)/g(n) < < n n
Table 2: Additional notations used in the appendix
A Derivation
In this appendix, we outline the derivations of Claim 2 The derivation is based on the standard use of the replica method of statistical physics (Mézard et al. 1987 Charbonneau et al. 2023 Montanari & Sen 2024). For a pedagogical introduction to the replica method computation for the linear models, see literature [Kzakala & "Zdeboroáá 202I), , for example.
As noted in the related works section, the salient feature of the asymptotics in the LSL is that the macroscopic properties of the learning results, such the predictive distribution, typically do not depend on each realization of the training data. In this paper, we assume these concentration propertics in advance to derive the formulas for the asymptotic properties.
Assumption (Concentration of the macroscopic properties of the learning results) We as- sume that the macroscopic properties of the estimators 7 will concentrate LSL. Concretely, we assume that the values of (N- B, [c, N-1 N.-NN--,,,, Ee (c, N- Vo[ū,(c, D)}, B(c, D)) does not Ructuate with respect to the realization of D LSL. Also, Let x= to/VN 2, z Mid Pz, E [N] be new input. We assume that the distribution of the prediction for this new input (c, a -w(c, DV/VN + B(e, D) (or В when the bias is fixed) with respect e and does not fluctuate with respect to the realization of D at LSL.
A.1 Additional notations
To describe the derivations, some additional shorthand notations. We summarize them in Table 2
A.2 Boltzmann distribution
Let starting with rewriting the training probability density function PB, which is termed the Boltzmann distribution, as follows. Let L(0; D) be the cost function to be optimized in 7 Then, the Boltzmann distribution is defined as
a statistical physics problem. For this, we introduce a
Pa (b( Z(D,c) A.((..)))
(40)
where 3 E (0, oo) is the positive parameter termed the inverse temperature following the custom of statistical physics, and c) = Iee (.C., is the normalization constant. For simplicity, we use the same notation for the model's parameter whether the bias fixed or not. We basically consider the case when the bias is estimated, but just replace with when the bias fixed.
At 3 + co, the Boltzmann distribution converges to the uniform distribution over the minimum of L(0; D, c). Since are considering convex loss function, the Boltzmann distribution converges to the Delta function at B + oc:
lim pn D, = 6a O(D,c))
(41)
80000
Therefore, analyzing the Boltzmann distribution this limit equivalent to analyzing the estimator defined in
24

---

Published in Transactions on Machine Learning Research (07 (274))
A.3 Distribution of the prediction
In the following, we use the replica method to consider the distribution of the prediction for new input.
A.3.1 Replicated system
We are interested how the prediction for a new input 8 =) wec, D/C. D) depends on a and c. For this, we introduce another probability density, which we refer to as the replciated system, follows. Let n1, ng N be the positive integers. Then, the replicated system defined as follows:
1 ED =
T1 II EC,,
u2 II
p((0a))
(42)
where a = (a102) is the shorthand notation for the subscript, and is the normalization constant. This is the density over (R(++)xx xna) if the bias trained and N xma) if the bias is fixed. Recall that the replicated system not conditioned by or c since the average taken explicitly.
ag")), ).... a = (a be Let 1 1...... be the positive integer, and take nı > I. Also, let a = (af " a2
set of indices such that (k) + dj (k') for any + W' E [4] Then, for an arbitrary function s²(-) such that subsequent integrals converge, we consider the following expectation:
OF F
II v(* w was) w / Baw))
(43)
By formally taking the integral with respect to (0a), we obtain the following:
D Ee
Bawne
E. E. |m( w//N +NN+B) B)] Z(D.c)
IZI,
ED Be [e|
m2
(4)
Since the above expression depends on nı and n2 the form of the power function, we can consider formal analytical continuation of 71, T2 E n1, R, and take the limit n1, f2 - 0. Then, we obtain the following expression:
Ee Eo-pn [e(ot w//V =
lim O L,
ED
(45)
At the limit 8 + 0o, the above converges to the following:
lim lim Ω Tin ED Ee (b(x ((D,cc/VN B(D,C))
(46)
8-00 m1
In addition, the predictive distribution does not fluctuate with respect to cach realization of D as assumed in Assumption [ Therefore, we can obtain a nontrivial information about the distribution (= D) if we obtain nontrivial expression of Ω and continue the result to n1, no E R. In the following, we describe the handling of the expectation
A.3.2 Handling of the expectation over the replicated system
Since the normalization constant E = Ep (D) just yields the unity at Rı, n2 0, focus the numerator of the expectation over (0a) ~ p in S2 12, .=2" Instead of first taking the integral over (0a) } as in the computation to obtain (44), we here first consider the average over æ and D. Then, using independence of the each data point in D and the reweighting coefficient c, we obtain the following expression of 2 m
1
Pi XE= E,
II
(++ N
w (am - Bal + w Wa(k) 2)
VN
25

---

Published in Transactions on Machine Learning Research (07 (07/2024)
1s+
Boa, ( w0 Ba vx u
x E ((c,)
M
x E deal
80ay [ ma ut Bt Jx "u =7)
Br d
(47)
1=1
where et Midd P Ca Wid , an [m1] and 2i, 25 aid Pz, E [N]. An important observation is that the noise appears only through the form of the scaled inner product with wa. At N > 1, such quantity follows the Gaussian distribution for fixed set of }wa due to the central limit theorem. Let us define ù IR' and u= E R as
U w (A)
(48)
1
u
Wa
(49)
Wa 2
(50)
Then, these quantitics follows the Gaussian distributions as u ~ N(0, 8), u= ~ (0, S), where the covariance matrices are given as
3R A W (+) atu)
(51)
N
Sab = A N Wa wb-
(52)
Also, the center of the clusters v only appears through the inner product wa w/N. Thus, the integrand in 47p depends on [wa} only through their inner products, which capture the geometric relations between the estimators and the centroid of clusters v. We call these quantities as order parameters.
The above observation indicates that the factors regarding the loss function in 447 can be evaluated by Gaussian integrals once the order parameters are fixed. To implement this idea, insert the trivial identities of the delta functions
II
(NQQu wa -wbddQub
(53)
a&b
8a wa v)dma:
(54)
into 47
Then O Dimmymm x can be rewritten as follows
Di xE=/ Bu--(o.5)
I +b (= + Bal + ūx)
Naatt+No
N
x Il 5a(NQab - wa wbb II
8a wa
Br mi 0d0
(55)
b
a
1=1
50t log E (.
Bot, 1 (ma+Batu!)
(56)
6 = log E
Be 17 (-ma m t0)
(57)
26

---

Published in Transactions on Machine Learning Research (07 (07/2024)
where θ is the collection of the variables {Qab). {ma). To complete the remaining integrals over {wa). we use the Fourier representations of the delta functions:
da (N Wa ws.
1
C wa wn) wa]Qan dQ
(58)
2T
6a(NNa wa 2) 2
1
e-(Nmoo--eejin dmaa.
(59)
After using these expressions, the integrals over {wa,s can be independently performed for each i, leading the following expression of S T. E:
g i, x x== =
f Banv(o.S))
II (b + Bath) + ūx) e (o(e,6)
(60)
1==1
G(0,6) Σ
QabRab Σ Emama + attt + tap 10 + Pw
(61)
a.b
2.E Qaswa wa+ Eo Rawa
Pw = log
e
(62)
where θ is the correction of variables (Qat), {ma). At N 1, using the saddle point method, it is understood that the intogral over O, θ is dominated at the extremum extr ((O, θ). Hence, we obtain
Tim x xE = =E=E (0,33)
II (bmmae + Bats + ūs) No
(63)
where O θ is obtained by the extremum condition mathope.6 ((0,
At this point, obtain the general expression of the extreme condition. Let define densities Peff, and Pet, as follows:
Pott,ar(u))
E.,o Qas ua En ma wa
Il -r((w))
(64)
Zroft,u
Pett (ul (ul
II
Iet 1t (#mm+ tua) x 0(u;0,AQ)
(65)
Z
where Q = [Qab] E gmimaxninn Then, the exremum condition given as follows:
Qab Ewepot [Wawbl,
(66)
ma = E Ew-ppat [wa]:
(67)
Qab -a AB (ct,)
Eutapte |ct, o 01 (ma Ba + va) + Bb + ub)
Bet gert (ma Ba u 1(a bb]]]
a AE (oog1 Eu-rrinn 15,00,8--01 (-ma Ba + ua)00 (-mb + Bb ub)
Bc, 821 (-maa + Ba + ua ua) ll = b)]
(68)
ma = aa aa B((tt) Su [Bctt ot (ma + Ba + ua)]
+ E (cT,)
E Bu-noinn [Bc,, ol (-ma + Ba + wa)l
(69)
Also, the next is added if the bias is estimated:
a a
E E Sn
let 01 (maa + Ba + ua)l
+ a (c5
E Em-ap-
[co, Øl (-Ma + Ba - val]
(70)
27

---

one Published in Transactions on Machine Learning Research (07 /024)
A.3.3 Replica symmetric ansatz
Since ( Q) depends on the discrete nature of R1, f2,, we cannol analytically continue the result to n1 12 E R. To make an analytical contimuation, the key issue is to identify the correct form the extreme condition.
The choice that reflect the symmetry of the replicated system when R1, n2 is the following:
Qab = + 1(a1 = biju u + 1(a = b)
(71)
ma = m,
(72)
Qab x I[(a = 61) 0+ + I1(a =b)3
(73)
Ma = 3m,
(74)
Ba = B.
(75)
Evaluating the replicated system using this symmetric form of the extremum and analytically continuing R1 0 is called the replica symmetric (RS) ansatz. When considering the estimation of the linear models with convex loss, it is empirically known that the RS ansatz yiclds the exact result (Obuchi & Kabashima 2019 Takahashi & Kabashima 2020).
Using this symmetric form of the extremum, after simple algebra, one can find that G can ana- lytically continued to nı, n2 E and also = O(m) + O(n2). Furthermore, the remaining factor I ( Baik) + +ss) can be rewritten follows
E Ea
Ea-A((,8) Il (++mam Bath) + +x)
Beu~N(O.A) (Ennsr(Oss) [v(=m B + VaLu venaal (76)
After all, we obtain the following result:
lim lim Dit 8-000 01 Kiiing E( (m [v(#m + B vqt. venull]
(77)
where m, 9, determined by the extreme condition under the RS ansatz at 3 - co, which is given
the self-consistent equation in Definition] [ This yields the Claim 2
Similarly, by considering the expectations such as Eso, --plw ((o, Io.N can obtain Claim 1
B Cross-checking with numerical experiments at small N
the main text we observed that the empirical distribution the weight vector is almost perfectly consistent
with the theory when = 213 In this appendix, we also show that the experimental results can be well approximated by the theoretical predictions even for a smaller size with N 20 shown in Figure 12 Note that the average number of positive examples M+ when M /M 0.01, N 20 (M++M--) / 1/2, which is obviously far from the LSL. Therefore, this result may indicate rapid convergence to the LSL.
C On US estimator without replacement
In this appendix, we show that the F-measure for the estimator obtained by US when using sampling without replacement does not depends on the size of the excess majority samples.
The F-measure for the estimator obtained by US which corresponds to the case of K = in Claim is
determined by q 7=00 q u. Let us also define X = X + 0. Then, by adding both side of equations (20 and (2
as well as (24) and (6).. and taking the average of c# ~ p explicitly, the following modified self-consistentt equations that determine 7, m, B are obtained follows.
28

---

Published in Transactions on Machine Learning Research (07 (07/2024)
0.8
0.15
K 4
0.3
K
K 64
K
64
0.10
pdt
pdt
pdr
0.4
0.1
0.2
0.0
0.00
-2
-6
-3
0
3
6
15
-10
-5
5
10
15
K
K
(a) (
Mr
v) = (0.01,-1 11)
(b)
Mr
M v) = (0.05,
1)
(c)
MT
V) (0.2, -1)
M
M
0.8
K
0.15
0.3
0.6
pdf
ndf
0.2
pdf
0.4
0.2
0.1
-2
0
7.5
0.0
2.5 5.0 7.5
15
-10
-5
0
5
10
15
k
$x
8
(d)
M M7 v) (0.01, +1)
(e) MT M
(0.05, +1)
MT (1)
(0.2, +1)
M
Figure 12: Comparison between the empirical distribution of 3 (histogram), which is obtained by single realization of the training data D of finite size with N = 2 and the thcoretical prediction in Claim 3 (dashed). Different colors represent resampling averages with different mumbers of realizations of reweighting coefficient c.
Claim 5 (Modified self-consistent equations for US) Let - and E X Them, the set of quantities q, m, X and Q x, i are given as the solution of the following set of modified celf-consistent equations when subsampling
used for the resampling method. Let and u= be the solution of the sollowing one-dimensional randomized oplimization problems:
Q 2²
W arg min
w w + Ar(w),
(78)
WER
2
u²
u= arg min dER
1 (u + h
(79)
2x
where
hw = n + ViEu, Ew, Ew,~ ~NO,11 1),
(80)
h B m VoLa, Eu N(0, A).
(81)
Then, the modified self-con cofficonsistent equations are given as follows:
d
X = Eg (o,,11
w
(82)
dh
7 = E
w
(83)
m Ee,rN((0.1) [w]
(84)
a
d
Q =
E (E,~N(00,)
ū+
+
(85)
dhi
dh
29

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
10
10"
10
10
10"
10-1
10-1
10
10
10
10
10
10a
10-2
10
10a
10
10
10a
-"-
a
(a)
(v A, A) = (1.5, 10
(b)
(v 4, A) = (1.5, 10
(c)
(v A, A) = (1.5, 10
10
10
10
6
5
10
100
100
4
10-1
10-1
3
10
10
10
2
10
10
102
10-2
10
10
10
10
10a
a"-a"
(d) (VA,A) A) = (0.75, 10 8)
(o)
(v4, A) = (0.75, 10
(I)
(v A, A) = (0.75, 10
10
10'
10
10
10
10
-0
10-1_
10
10
10-2
10
10
10a
10:2
100
10
2
10
10a
(g) (VA, (0.5,
30
(h) (V4, = (0.5, 10
(1) (VA, = (0.5, 109)
Figure 13: The heatmap plot for the relative F-measure in log-scale: log10
where FUB and Fwiighting are the F-measures for UB and the weighting method with naive coefficients, respectively.
x at
A₁2 Be Beu-No)))) [1 + (
(86)
m
Ax BB., -
(87)
Furthermore, depending on whether the bias is estimated or fized, the following equation is added to the modified self-consistent equation
Be.~((o,)) jut +ū]] when bias is estimated
(88)
B
when bias is fixed
It clear that the above modified self-consistent equation only depends on a and does not depends on a at. Therefore, the F-measure of US cannot be improved by the excess examples the majority class
4This is exactly with the equations determine the behavior of linear classifiers trained the data generated from symmetric Gaussian mixture model with data size N and an input dimension obtained in Mignaaco 2020
30

---

Published in Transactions on Machine Learning Research (07 (07/2024) /224)
100
0.75
0.75
0.75
0.50
00
000
000
2
0
10
16
(a) 10 10-3
(b) A 10
(c) A == 10
Figure 14: The resampling rate dependence of the F-measure when using sampling with replacement for selected values of X. Here the parameters are set as (at, a vA) = (0.05, 0.1, 0.75). The vertical line shows the value of the resampling rate that makes the bias term to be zero.
SW with naive re-weighting coefficient
Figure 13 show the heatmap plot for the relative F-measure log-scale: log10 F where Fun and F weighhting are the F-measures for UB and the weighting method with the naive coefficients Tnaive (M* + M (2M#.. It is clear that, with the naive rewcighting coefficient, the F-measure of SW is catastrophically worse that of UB, especially when the minority class data is small and the excess majority samples large. This suggests that delicate tuning of the reweighting coefficients are required in overparameterized settings.
E Resampling rate dependence for sampling with replacement
In this section, show the resampling rate dependence of the F-measure when using sampling with re- placement. As shown in Figure 14 the F-measure takes the highest value when the bias term is estimated to be zero. This is because the F-measure considered here treats the positive and negative examples equally.
31


Reviews:
[{"review_id": "Rp60bMoFPb", "reviewer": "Reviewer_5dJq", "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- The authors consider a relevant problem of ML.\n- The analysis and the comparison of US, UB and SW is novel and significant.\n- Up to section 3 (included) the paper is mostly (see below) well-written and nice to read.\n- Equation 32 is clear and easy to interpret.\n- The double descent phenomenon associated with reweighing is interesting and new. \n\n# Weeknesses\n- The discussion of the results is often superficial and stops without analysing in detail the implications of the equations. For instance, the authors obtained the equations for US with replacement but never used them. Another example, the authors decided to consider only the \"standard choice\" of re-weighing coefficients and the \"standard choice\" of US, without exploring other possibilities that the equations offered. In ML practice often there is no \"standard choice\" and people rely on cross-validation steps. So it wouldn't be unrealistic to compare with the optimal value.\n- The comparison with US is trivial. The authors considered uniform under-sampling, which in a high-dimensional model is equivalent to the performance of the same model with less data. Indeed, not surprisingly, in Fig.3 the authors observe that the performance for US is constant as the majority class is increased. Two alternatives to make it more interesting would be: not considering uniform undersampling (which is actually a standard practice), or considering US with replacement.\n- The discussion of the results seems to be actually lacking an understanding of the results. The authors limit the discussion to an evaluation of the equations, there is no discussion of why, for instance, UB outperforms SW for large majority classes but the vice-versa occurs for small majority classes.\n- In the introduction, the authors comment on some inconsistencies in the literature, for instance they mention Nixon, et al. (2020), however the authors never go back to discuss these issues. It is not clear how the initial motivation justifies the analysis and what the results helped us understand. \n- The authors stressed in the introduction that most of the literature considers overparameterised models, which appears to be an important aspect of the problem. However, in their discussion of the results, the overparameterisation aspect is never mentioned.\n- The authors don't specify the value of K (the number of realisations used in bagging) and never discuss the effect of changing that coefficient in practice. The only discussion is related to Figure 1 which is actually intended to show the validity of the equations rather than the effect on performance.\n \n## Additional comments\n- The F-measure is never defined. This is quite important, the authors should probably first introduce it informally in the introduction (when it appears for the first time) and then formally in the problem setup.\n- Figures 2, 3, and 6 are suboptimal. In each figure, all the panels share the same legend that ends up occupying a large portion of the figure. The authors could show a single legend (maybe on top or at the bottom of the figures) increasing the individual panels a making the figures more readable. \n- Claim 5 is a repetition of Definition 1 adapted to US. It seems quite unnecessary to be reported in the main text, maybe it would be better to move it to the appendix.\n- Figure 7 aims to show the performance ratio of UB and SW. However, the choice of the colours is not helping. The authors should use a divergence colourmap, centring the white (or black) to 1, to distinguish the two regions. \n- The authors don't discuss [1-4] that consider Gaussian mixture models using a replica-theory approach, in particular [3,4] consider specifically data imbalance. \n- Page 3, after generating the tools for asymptotic analysis, the authors concluded with \"and so on\". They should be specific indicating what is left out of the list, or just end the sentence before.\n- Is equation 5 necessary, can it be written in words? \n\nRefs \n- [1] Pesce, L., Krzakala, F., Loureiro, B., & Stephan, L. (2023, July). Are Gaussian data all you need? The extents and limits of universality in high-dimensional generalized linear estimation. In International Conference on Machine Learning (pp. 27680-27708). PMLR.\n- [2] Loureiro, B., Sicuro, G., Gerbelot, C., Pacco, A., Krzakala, F., & Zdeborová, L. (2021). Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions. Advances in Neural Information Processing Systems, 34, 10144-10157.\n- [3] Mannelli, S. S., Gerace, F., Rostamzadeh, N., & Saglietti, L. (2022). Unfair geometries: exactly solvable data model with fairness implications. arXiv preprint arXiv:2205.15935.\n- [4] Loffredo, E., Pastore, M., Cocco, S., & Monasson, R. (2024). Restoring balance: principled under/oversampling of data for optimal classification. arXiv preprint arXiv:2405.09535.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 authors analysed theoretically different mitigation strategies used for imbalanced data, in particular under-sampling (US), sample re-weighing (SW), and under-bragging (UB). In particular, quantifying UB's performance is the main objective of the paper. The authors used methods from statistical physics to reduce the complexity of the problem and evaluate the asymptotic performance of a shallow neural network trained on a Gaussian mixture model. Furthermore, the authors identified a double descent phenomenon associated with reweighing.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please, refer to \"Strengths and Weaknesses\" for more details.\n\nThe analysis should be further extended and the results need a more thorough discussion. \nAt the moment, the paper mostly reports a relevant technical result, but it doesn't improve our understanding of mitigation methods for class imbalance.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eJs2EGrjsr", "reviewer": "Reviewer_ihfu", "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": "1) **Strengths** : \n- The contributions of the paper and its conclusion on the performance of the methods are clear, its conclusions are interesting and might be of practical relevance. Also, the authors provide numerous plots showing the sharpness of their predictions in the large system limit (LSL). The appendix containing the replica computation is overall clear.\n\n2) **Weaknesses** :\n- In general, I think the paper would be difficult to understand for a reader not familiar with the replica computation / state-evolution equations. Indeed, the structure of the argument might be weird for an unfamiliar reader : the author first introduces the state-evolution equations without detailing the interpretation of the overlaps $m, q, v$, making the equations . Only after (Claim 1) do they provide this interpretation. I think it would be helpful \n- The analysis of the method is made only at constant $\\lambda$ and not at $\\lambda$ that would be cross-validated to minimize a validation loss, as it is done in practice. It would be interesting to see how choosing $\\lambda$ \"optimally\" changes the results of the paper.\n\n3) **Other remarks** : \n- Formulating Assumption 1 as an assumption and not as a property of the problem seems a bit strange to me. Indeed, it is standard that the macroscopic properties do not fluctuate with $D$ in the LSL.\n- \"estiamted\" Equation 29\n- “Comparison of the comparison of” in Figure 2 might be a typo ? \n- Figure 1 : not very readable because of the many plots, especially using the two different sizes $N = 2^{10}$ / $2^{13}$ feel redundant\n- In general, the presentation of the Figures could be improved to be more readable. For instance, the legend may not be required in all subplots for Figure 2 and clusters the figure.\n- \"mathop\" is not defined (maybe the author meant \"ext\" instead ?) just after equation 72", "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 performance of different statistical methods for linear classification when the training data is imbalanced between two classes (i.e one class is more represented in the training data than the other). The methods considered are undersampling (US), underbagging (UB) which combines undersampling and ensembling, and sample weighting (SW). These methods are studied in the asymptotic regime where the dimension and number of data are large and of same order, and in a synthetic data model (Gaussian mixture model).\nThe author shows that the performance for the F-score of UB is improved by having more data of the majority class, while US is insensitive to the imbalance. On the other hand, the performance of SW decreases with the data imbalance, hinting that this method is not efficient to counter data imbalance.\nOn the technical side, the author use the standard replica method to compute the asymptotic properties of the different methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I request no change that would be critical for acceptance, but the following changes would strenghten the work in my opinion : \n* Reorganizing the main so that the state-evolution equation are more easily understandable for readers unfamiliar with these.\n* Improving the readability of the figures", "broader_impact_concerns": "Data imbalance is an important topic in statistics. However I do not think that this paper requires adding a Broader Impact Statement as it is concerned with a theoretical analysis of existing methods, and the analysis is done on synthetic data.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XShM0HqsVg", "reviewer": "Reviewer_eAxG", "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": "*Strenghts*\nThe paper quantifies the beneficial effects of bagging by relating the improved performances to the suppression of sampling fluctuations, at the same time exploiting in its entirety the information contained in the abundance of the dominant class in a classification task. The paper complements some recent findings in a similar setting, eg the paper by [Clarté et al.](https://arxiv.org/pdf/2402.13622) on bootstrap and subsampling in high dimensional regression.\n\n*Weaknesses*\nThe paper appears as a variation, in a new setting, of methodologically similar investigations available in the literature, in which the replica method is used to extract asymptotic performances of convex GLM under ensembling and bootstrap. The replica method is non-rigorous, but it proved to be a very powerful technique, and, nevertheless, the theoretical results are supported by numerical simulations. Bayes-optimal references for the performances are not discussed.", "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 submitted paper presents an asymptotic analysis of the under-bagging (UB) method for the training of classifiers in the case of unbalanced datasets. The authors derive a collection of self-consistent equations for a set of low-dimensional order parameters, expressing the variance of the estimator and its alignment with the signal, in the asymptotic proportional regime, in which the dimension of the data points and size of the dataset diverge keeping a fix ration. By means of such order parameters, the $F$-score of the estimator is computed. The same analysis extends to the case of estimators obtained via under-sampling (US) and simple reweighting (SW), allowing for a direct performance comparison of the various methods. As a result, it is shown that the ensembling procedure within the under-bagging strategy is beneficial, as it leads to a suppression of the sampling fluctuations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I list below some remarks on the paper.\n- As a general recommendation, I advise the authors to add an explicit definition of the UB estimator. Surprisingly (considering the fact that it is central in the paper), the UB setting is compared with, e.g., the US and SW but is not described in detail. I assume that the UB estimator considered by the authors is obtained by ensembling an infinite number ($K\\to+\\infty$) of under-sampled set-ups. If this is the case, this has to be stated explicitly somewhere in the manuscript. For example, at the end of page 8, the authors specify that ```UB with $K>1$ is [has?] a higher value of the $F$-measure``` which suggests that the authors consider UB any $K>1$. However, in Section 4, $K$ is not discussed anymore: the results and the analogy with ensembling results by [D'Ascoli et al.](https://proceedings.mlr.press/v119/d-ascoli20a.html) or [Loureiro et al.](https://arxiv.org/abs/2201.13383v1) leads to infer that therein $K\\to+\\infty$: if this is the case, this should be stated explicitly.\n- Unless I missed it, it is always assumed, but never specified, that the true distribution of the data points is balanced between the two clusters. This should be stated somewhere, for example in the ```Problem setup``` section.\n- The standard definition of the [$F$-score]() $\\mathcal F$ in Eq 36 involves the *precision* in place of the *specificity*: I suppose that the authors followed [Wallace et al.](https://ieeexplore-ieee-org.ezproxy.unibo.it/document/6137280) who used specificity to avoid dependence on the prevalence. I think that this should be specified explicitly.\n- It is expected that the subset of figure for $N=2^{10}$ in Fig. 1 are indeed affected by strong finite-size effects (it is maybe surprising that they are not that strong) as in this case $\\frac{M^+}{M}=10^{-2}$ means that $M^+\\sim 5$. I wonder if it is sensible to keep them in the text or not given that the main interest is the LSL.\n- As observed by the authors themselves, Claim 5 coincides with the results of [Mignacco et al.](https://proceedings.mlr.press/v119/mignacco20a.html) as, in the US case, the problem is intrinsically a classification task of $\\alpha^+N$ points. Is the conclusion given at the end of Sec. 4.1 an immediate consequence of the fact that, in this case, $\\alpha^-$ plays no role? If this is the case, the authors might consider moving it to the Appendix.\n\nFinally, I list here some typos that the authors might fix. I think $p_c^+(c^-)$ in Eq. 7 should be $p_c^-(c^-)$. Also in Section 3.1 $N$ is referred to as *system size*, although it is the dimension. In Eqs 42 and 44, $E$ should be replaced by $\\mathbb E$. The label of Fig 2 starts with ```Comparison of the comparison```. After Eq 72 there is a reference to a ```mathop``` which is likely meant to be $\\min$ (as a general remark, the Appendix appears to be in a very sketchy form).", "broader_impact_concerns": "No broader impact statement is required for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers considered the manuscript addressess a relevant problem and considered the contribution interesting. However, some concerns were raised on the lack of clarity in the initial manuscript. During the discussion phase, several recommendations were made, and the manuscript saw a substancial rewritting. All reviewers agree that the revised version has been significantly improved, and recommended for acceptance at TMLR. 

As a final remark, Reviewer *5dJq* added: "*The authors present a real data experiment in the appendix that agrees with the theoretical results. As a side note, I would suggest pushing this result into the main text as this is relevant for the reader.*".

Therefore, I am happy to recommend this work for acceptance conditioned on this small change.
Decision: Accept (poster)