Pairwise Maximum Likelihood For Multi-Class Logistic Regression Model With Multiple Rare Classes
Authors: Xuetong Li
Danyang Huang
Hansheng Wang
Venue: ICML 2025 poster (2025)
Keywords: Multi-class logistic regression model
Pairwise maximum likelihood estimation
Rare class analysis
Car plate recognition
Primary area: applications->everything_else
TL;DR: We study multi-class logistic regression with multiple rare classes, proposing an efficient and effective parallel pairwise estimation method.

Abstract: We study in this work the problem of multi-class logistic regression with one major class and multiple rare classes, which is motivated by a real application in TikTok live stream data. The model is inspired by the two-class logistic regression model of Wang (2020) but with surprising theoretical findings, which in turn motivate new estimation methods with excellent statistical and computational efficiency. 
Specifically, since rigorous theoretical analysis suggests that the resulting maximum likelihood estimators of different rare classes should be asymptotically independent, we consider to solve multiple pairwise two-class logistic regression problems instead of optimizing the joint log-likelihood function with computational challenge in multi-class problem, which are computationally much easier and can be conducted in a fully parallel way. To further reduce the computation cost, a subsample-based pairwise likelihood estimator is developed by down-sampling the major class. We show rigorously that the resulting estimators could be as asymptotically efficient as the global maximum likelihood estimator under appropriate regularity conditions. Extensive simulation studies are presented to support our theoretical findings and a TikTok live stream dataset is analyzed for illustration purpose.

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
Xuetong Li'
Danyang Huang Hansheng Wang" 4
Abstract
We study in this work the problem of multi-class logistic regression with one major class and mul- tiple rare classes, which motivated by a real application in TikTok live stream data. The model is inspired by the two-class logistic regression model of Wang (2020) but with surprising theo- retical findings, which in turn motivate new es- timation methods with excellent statistical and computational efficiency. Specifically, since rigor- ous thcoretical analysis suggests that the resulting maximum likelihood estimators of different rare classes should be asymptotically independent, we consider to solve multiple pairwise two-class lo- gistic regression problems instead of optimizing the joint log-likelihan likelihood function with computa- tional challenge in multi-class problem, which are computationally much casier and can be con- ducted in fully parallel way. To further reduce the computation cost, a subsample-base wise likelihood estimator is developed by down- sampling the major class. We show rigorously that the resulting estimators could be as asymptot- ically efficient as the global maximum likelihood estimator under appropriate regularity conditions. Extensive simulation studies are presented to sup- port our theoretical findings and TikTok live stream dataset is analyzed for illustration purpose.
Figure 1. Examples of Audi Tik live streams. Each red bound- ing box annotates a local region containing car plate, which contains valuable model identity information.
This problem is well motivated by many real-world clas- sification tasks, such as recognizing rare animal species (George et al., 2023; Mou et al., 2023) and detecting un- common objects in traffic scenes (Mullapudi et al., 2021a; la; Zhang et al., 2024). In these real-world settings, the cate- gories of interest are often extremely rare. As pointed out by Mullapudi et al. (2021a;b), it is typically easy to collect large number of negative instances this case, which can be obtained through weak- or semi-supervised methods (Ratner et al., 2017: Chen et al., 2020), or as by-product of multi-label annotation (Deng et al., 2014), or with random sampling. This leads to an imbalanced image classification problem, where the "hackground" category overwhelmingly dominates, and rare classes (e.g., target objects) represent the minority.
pair-
To fix the idea, consider for example a car plate recognition problem in TikTok live streams. Figure I shows screenshots from TikTok live streams sponsored by different Audi car dealers. Through the live stream, the car dealers wish to entice as many potential buyers as possible from the TikTok users to make purchasing decisions (Su et al., 2023). To this end, important to understand Tik users' possible purchase intention, which can be partially reflected in their viewing behaviors (Ma, 2021; Sun et al., 2024). Interest- ingly, this important information is accurately shown on the car plate; see the red bounding boxes in Figure 1. Then, how to statistically analyze the graphical information provided by the car plate so that the car model can be accurately and automatically recognized becomes the key problem. Un-
1. Introduction
We study in this work the problem of multi-class logistic regression with one major class and multiple rare classes.
'School of Mathematics and Statistics, Xi'an Jiaotong Uni- versity, an. China "Center for Applied Statistics, Renmin Uni- versity of China, Beijing, China "School of Statistics, Renmin University of China, Beijing. China 'Guanghua School of Man- agement, Poking University, Beijing, China. Correspondence to: Danyang Huang <dyhuang89@ 126.com>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
fortunately, the position of the car plate in the image is not known in advance and its position is quite random. To capture the car plate, large number of bounding boxes are randomly generated over the entire screenshot image. This leads to a large number of sub-image samples; see Figure 4(c). Specifically, since these screenshot images are high-resolution images with small car plates, one can expect that most sub-images would reflect the background content. They can be labeled as k O ("background"), ). which is the major class and accounts for more than 95% of all samples. The remaining sub-images (less than 5%) are about the car plates and are classified into K = 8 classes indexed by 1 S k v K; see Figure 5 for an intuitive understanding. We formulate this problem as a classical multi-class logistic regression problem with a total of (K +1) classes. To accomplish this task, multi-class logistic regression model or its sophisticated variants can be used.
coefficients of each rare class might be estimated separately instead of jointly, without sacrificing the asymptotic effi- ciency. This interesting finding inspires the idea of the pairwise likelihood estimation. Specifically, we first decom- pose the original (K + 1)-elass classification problem into a total of K major-and-rane class pairs. Next, the MLE of the major-and-rare class pair can be easily computed by a standard Newton-Raphson (NR) algorithm. Theoretically, we find that the resulting pairwise maximum likelihood estimator (PMLE) is statistically efficient asymptotically, Practically, the PMLE enjoys nice computational properties. First, the Hessian matrix associated with each major-and- rare class pair is only of (p 1p+11 x (p+ + diddienni,,,, which is much smaller than (p + 1)K x (w + 1) K dimmension of the full-class maximum likelihood problem. Second, the PMLE for different class pairs can be computed in a fully parallel or distributed manner.
Most existing literature focuses on the multi-class logistic regression model (Nelder & Wedderburn, 1972) under a classical situation with broad applications (Maalouf, 2011: Tanha et al., 2020). By a classical situation, we mean that the number of classes is not very big, the class distribution fairly balanced and the feature dimension is relatively low. Unfortunately, this is not the case for many real applica- tions (e.g., the TikTok live streams problem as discussed before) (Nelder & Wedderburn, 1972). Instead, practitioners often face challenging problems with a number of classes (Abramovich et al., 2021), multiple rare classes (Mullapudi et al., 2021a), and high dimensional features (Wang et al., 2023). This makes the associated parameter estimation, e.g., the maximum likelihood estimator (MLE), extremely difficult. For example, if the traditional Newton-Raphson (NR) algorithm is to be used for computing the MLE, a Hessian matrix (i.e., the second-order derivative of the log- likelihood function) with dimension (p + 1)K x (p + 1)K needs to be inverted (McCullagh & Nelder, 2019). This makes the computation cost extremely high. As a useful alternative, various gradient based methods have been de- veloped and popularly used with better computational feasi- bility. However, they suffer from the tuming parameter (i.c., the learning rate) selection problem and slow convergence rate issue (Zhu et al., 2021). All those challenges inspire us to search for a new method, which can compute the MILE in a more efficient way.
Although the PMLE method is suitable for parallel or dis- tributed estimation, we find that the computation cost re- mains significant. The main reason is that the major class is fully involved for each major-and tionally, we theoretically verify that the convergence rate of the PMLE is mainly determined by the sample size of rare classes, instead of the major class. This further implies that the sample size of the major class might be too large to be necessary for PMLE. Therefore, we are inspired to consider a much reduced sample size for the major class, so that the computation cost can be further reduced. The subsample- based pairwise likelihood estimator (SPMLE) then constructed. Theoretically, we find that the SPMLE is also asymptotically efficient. However, compared with the global maximum likelihood estimator (GMLE) and PMLE, the SPMLE is easier to compute with much less computa- tional cost. Extensive simulation studies are presented in this paper to demonstrate the finite sample performance of these estimators. The aforementioned TikTok Screenshots dataset is also used for illustration purpose.
class pair. Addi-
The rest of this paper is organized as follows. In Section 2, we first introduce the model setting and the rare class phe- nomenon. We then present three estimation methods (i.c., GMLE, PMLE and SPMLE) and study their asymptotic properties. Simulation studies are given in Section A Tik- Tok live stream dataset analyzed for illustration purpose in Section 4. The article concludes with brief discussion and concluding remarks in Section 5. All technical details are delegated to the appendix in the supplementary material.
To solve the problem, first consider the standard MLE, of which the asymptotic theory has been well understood in the past literature, but for the situation with fairly balanced class distribution (Fox, 2015; McCullagh & Nelder, 2019). We are then motivated to fill this important theoretical gap. Our asymptotic theory suggests that, for a multi-class logis- tic regression model with one major class and multiple rare classes, the asymptotic covariance matrix of the resulting MLE is block-diagonal. This suggests that the regression
2. The Asymptotic Theory
2.1. Model Setup and Rare Class Phenomenon
Let (Y, Xx) be the observation collected from the i-th sub- ject with 1 < i S N. Here Y; E 10,,,.... .K} is the i-th
2

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
T E IP is the associ- ated p-dimensional feature. Assume that the random vector X; is sub-gaussian in the sense that the one-dimensional marginals a X; are sub-gau -abb-gassiin random variables for all a E RR (Vershynin, 2018). To model their regression rela- tionship, a standard multi-class logistic model is assumed as follows (McCullagh & Nelder, 2019)
class label and X; (X.,.... x
probability can be approximated as P(Y, = k X,) exp(X² B ax&).. We require the sizes of different rare classes to be comparable. This means that the class sizes should not be dramatically different. Otherwise, there must exist an even rarer class among rare classes. The size of this even rarer class would be too tiny to be of any practical rele- vance and can hardly be studied theoretically. Accordingly, we are inspired to assume P(Y; = K1 X.)/P(Y; = kg X;) z exp (3k, {k,)) exp(aNk) - -aNNk))= (1) for any 1 I ki, K2 I K. This condition can be eas- ily satisfied if ONK:: aNN2 CRr for some fixed constant Ck Equivalently, we can also assume that ONk = ON + 3%00 for some aN and Bkg- Accordingly, we require that 3an is a fixed constant, but (1) aN - -x0 and (2) a +log N - oC as N + co. These conditions are fairly standard in the literature. See, for example, equation (2) in Wang (2020), Section 2 in Wang al. (2021) and Song & Zou (2024).
exp [ Bk + +at) P(Y = = 1 > exp (X; Bx + +ak)
Here Bx= = (Bk1, 3kp) E R² is the regression coef- ficient associated with the k-th rare class, and ag E R is the intereept parameter accordingly. We know imme- diately that P(Y, 0 x=) =- P(Y,
k x²) = 1/f1- + Σ exp(X, Ax + }g)}. Accord- ingly, a log-likelihood function is constructed as [())= =
En1 Ex=o k= aik log wak. where 02 = (aa, )x) T E R
and θ_ = [ ................................ 00) T E R with q = (p + 1)K.
Unfortunately, the above nicely defined parameters o and 3до are not immediately identifiable. To see this, let c E R be an arbitrary scalar. We can then redefine oN == a, + c and 3k0 := 3x0 c. One can verify that the above model setup remains valid. It would be desirable to find a practi- cally convenient way to make both aN and 3k0 identifiable. To this end, note that P(Y; & 0) 2 Σkso Efexp(X,) (X Bx + aN + [ko]}
Here aik- = 1 1Y, = k) E [0,1] is a binary indicator and Wik P(Y,-
k[,,) = exp(X, 3x + aas)/11 +
Ek= exp(XTT3, 3R + } is the response probability of the k-th rare class (i.e., S k - K). Consequently, the MLE can be obtained as θ argmax ((O). where θ -0T "T) E IR2 and O2- = (āa, 3, E R
Recall there are a total of (K + 1) classes where the 0- th class is the major class and the other K classes are rare classes. To reflect this rare class phenomenon, two conditions need
C Exso Elexp(X; 3x + 320)]. De- fine c log Ex Elep((X 3x + }R0)}{ Redetine ON = aN + and BRO Sko c. We then have P(Y. # 0) = cax, This suggests that we might define aN = log P(Y, + 0). This might be a convenient way to specify ax. Once ON is fixed, other parameters (i.e., Ben and Bys) can be uniquely identified. Accordingly, we should have 3:0 = ANE ON = ONK log P(V, 7 0).
be imposed. First, we require that P(Y, = k) + 0 as N + do for every k with < k S K (Wang. 2020; Li et al., 2024). Following Wang (2020), we assume that 3g (1 < k < K) is a fixed parameter and does not change by the sample size N. Otherwise, we can hardly model the regression relationship between Y; and X; in a relative stable way. Accordingly, we have to assume ak + -00 as N + co. To reflect the fact that ag diverges with sample size N, we rewrite ag as d' Second, we ex- pect that the number of instances helonging to different rare classes should diverge to infinity. Otherwise, the sample sizes for the rare classes might be too small to support a valid asymptotic study. Define N₁- = E'= T(Y, = k) to be the size of the k-th class, where 1(-) the indicator function. We shall have E(Nx) Re P = k) + oo as N + 0o for 1 < k < K. This implies that aNz + log N - when N + x.. To summarize, to appropriately reflect the rare class phenomenon, two conditions must be imposed for ONk- They are, respectively,
Next, define an expanded feature vector Z, (1, Ro+1 with the intercept term included. Define 0% (Bro, )T E ge+t to be the associated regression coef- ficient parameter. Note that o% should be carefully differ- entiated from 0z. Recall 0g = =(ONN; 8 )T E RR++1, Thus, the only difference between 02 and 0g is the intercept term. Next, the model (1) can be re- re-parameterized as
exp (Z. 0% + +an) - x 1+ ΣK exp (ZT0g 02 + aNN)
(2)
for 1 S k A case of the model (I), which is a more general model. Compared with (1), the key feature of (2) lies in its assur- ance that different rare classes maintain comparable sizes. Next, recall that aN =log P(Y, * 0). Therefore, the re- re-parameterized log-likelihood function can be defined as [( = 1= -M R ask log w according to (2), where 0' = (8)
K. Note that the model (2) is a special
(1) ONNA + -oo and (2) aNk + log N + oa as N + oo for every 1 1 k K.
2.2. Peeameeamterr Likelihood Function
We next study the theoretical implications of those two con- ditions in more depth. We start with the first condition P(Y; = k) + 0 as N + co. Note that the rare class
.0K E R2 with q = (p + 1)K. Re- call that ask: = I (Y; = k) E {0.1] is a binary indica- tor. However, wice = P(V. = k|X,) = exp(2% 0g +
3

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
ox)/(1+E* -= expp og + +ay] is the response prob- ability of the k-th rare class under the re- re-parameterized model (2). Accordingly, another MLE can be defined as ① argmaxg. ((O)), where θ .... OK)T E TR:9 with 0/ = (3ko: 3% T
(
inal (K 1)-class problem into a total of K two-class problems. Each two-class problem corresponds the major class and one rare class. This leads to a major-and-rare class pair: see Figure 2. In other words, we take the major class as the benchmark class and one other rare class (i.e., k) as the matching class.
2.3. The Global Maximum Likelihood Estimation
Note that there are two GMLEs defined. The first one is 6, which is obtained under the model (1). The other one is
6, which is derived with the help of the re- re-parameterized model (2). Then is of interest to study their relationships. One can verify that the model (2) is essentially the same as the model (1). The only difference is that aN in the model (1) is re- parameterized in the model (2) as Qi -.x--B Consequently, the following relationship holds: (1) 3x is the
Mejor Cless
Rare Closses
same for é and θ and (2) aN*= = llgg P(Y; + 0) + 3ko for every 1 < k < K. Therefore, Ô - θ and é O* should share the same asymptotic distribution. We then have the following theorem.
Mijor-and Rare Class Poins
Figure 2. Illustration of the parallel or distributed computation for the PMLE. The whole dataset contains four classes with the circle class the major class. This leads three major-and- class pairs. By solving three two-class logistic regression problems, the PML.E can be obtained.
Theorem 2.1. Assume that ON - -00 and ON + log N + 00 as NN + Do.
We then have VNeax(0 (6 - Q)
Vee (Ô 0¹) +a ((0, 1) with Σx
diag (e(xp( (z Z,Z7 :11 S k K} N 00.
By the model (2) and condition on this major-and-rare class pair, we obtain a two-class logistic regression model as
The technical proof of Theorem 2.1 is given in the sup- plementary material Appendix A.1. By Theorem 2.1, we and
know that & (or equivalently +) is asymptotically normal. The asymptotic covariance matrix is given by Σ- = diag : S k- S K} and M = [exp(( 2, 0z) }. This implies two interesting findings. First, the convergence rate of θ is Vee instead of /N. This indicates that, with multiple rare classes, the convergence rate is mainly determined by the sample size of the rare classes instead of the total sample size. Simi- lar theoretical findings were also obtained by Wang (2020) but for an imbalanced two-class problem. Second, we sur- prisingly find that gn11 R2xy is a matrix of a block diagonal structure. It contains total of K blocks with the k-th block given by 2 R(++))((++)) By this asymptotic covariance matrix, we know that different 0&s are asymptotically independent with each other. Further- more, one can verify that the computational cost of the p² GMLE is O(N'" is used. This implies that the standard NR algorithm can hardly be used for the case with both high feature dimension p and multiple rare classes K.
cxp(Z; (2 0g + +aN) P(x k k {0, 1 1 exxx(( 0% + aNN)
for every rare class 1 S k S K. This suggests a pairwise log-likelihood function as (ot = Σi= ard (2, 0g + o,) (ast + 0zo) log (1 + exp Z 0% + +ax)). The PMLE can be easily obtained as 0.air argmax,; (Bt) whose theoretical properties are given by Theorem 2.2 as follows.
Theorem 2.2. Assume that aN + -00 and aN + log N - 0 as N - D. Then for < k S K, we
have VNEAN (@pair 02) -a N(0, Ex with Σj E Ec 2 0%) Z,2,T as N cc.
The proof of Theorem 2.2 is given in the supplementary material Appendix A.2. By Theorem 2.2, know that the PMLE @eair is also VNe conssitten and asymptotically normal. We surprisingly find that the asymptotic covariance matrix is given by Σ = [x[cpp(2, 81) which is the same that of @mile However, the difference is that the PMLE @pair is computationally much easier since @aair can be computed in a fully parallel way for different ks; see Figure 2. If standard NR algorithm is used, it could be verified that the computational cost for the PMLE is O(Nop² K + p2 K), which is much less than that of the GMLE. This makes it computationally efficient and feasible even with a large number of classes (i.e., K).
if standard NR algorithm
2.4. The Pairwise Maximum Likelihood Estimation
The surprising findings about asymptotic independence in Theorem 2.1 suggest that the regression coefficients associ- ated with different rare classes might be estimated separately instead of jointly. Accordingly, we need convert the orig-
4

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
2.5. Subsample-Base Based Pairwise Maximum Likelihood Estimation
Theorem 2.3. Assume that oN - -o and aN +log N + ao N + 00. Further assume NN/ ee -000 as N - DC.
Then for 1 S k S K, we have v Ve (0gu) - 01) tt
Compared with the GMLE, the PMLE is considerably easier to compute for two reasons. First. the dimension of Hessian matrix used in NR algorithm greatly reduces from (p + 1)K& x (p++1 K) to (p + 1) x (p+ 1 1). Second, the PMLEs for different class pairs can be computed in a fully parallel way. This makes the pairwise maximum likelihood method particularly suitable for parallel or distributed estimation. However, we find that the computation cost of this new method remains significant. This is mainly because the major class is fully involved for each major-and-rai class pair, whose sample size is about O(N) order. This leads to a significant amount of unnecessary computation cost. To see this, note that the sample size of this major class is about O(N) order. However by Theorem 2.2, we find that the convergence rate of Opair is only of the order 1/ 1/VNeaM, instead of //N. Recall that the convergence rate of @pair is mainly determined by the sample size of rare classes, instead of the major class. This further implies that the sample size of the major class might be too large to be necessary for pairwise maximum likelihood estimation. Thus, we are motivated to consider a much reduced sample size for the major class so that the computation cost can be further reduced.
(0, 2 with 23g = EE(exp(Z 8.) Ziz; as N + oc.
The proof of Theorem 2.3 is given in the supplementary material Appendix A.3. By Theorem 2.3, we know that the SPMLE Oeu is also VNeeN-cconisti cally normal. We find that the asymptotic covariance matrix is given by _t- = [E(exp( Z [[]]] which is the same that of 6: and 0 This suggests that B shares the same asymptotic efficiency with 0pile and Of as long as /x/ + oo as N + s0, recalling that TN is the sampling probability. In this case, the sample size of the subsampled major class remains substantially larger than that of the rare class. However, it is much smaller than that of the whole major class. In this regard, the com- putational cost for SPMLE is D(NoTNp? K + pd K)) if a standard NR algorithm is used. Since No is of the order o(N), this leads to a significant reduction in computation cost as compared with PMLE.
and asymptoti-
2.6. Some Extensions
CASE 1. the previous subsection, the number of classes K is treated as fixed. We next study the case with a diverg- ing K. Specifically, the expected percentage of rare classes in this case should be even smaller. To ensure diverging sample size for each rare class, the technical assumption aN - -co should be replaced by oN + log K + -cc. The resulting theoretical behavior of our proposed methods remains fairly the same. More specifically, the convergence rate of the PMLE remains VNe The PMLEs associ- ated with different rare classes remain mutually indepen- dent asymptotically. More importantly, the resulting PMLE remains asymptotically as efficient as GMLE.
To fix this idea, consider a fixed k with 1 S k S K. Next, for each observation i, define an independently and identically distributed binary random variable b; indicating whether this observation is sampled. Write P(b, = 1) - nN for some sampling probability 0 < nN < 1. We next consider the following interesting conditional probability P(Y; k|Z,, Y; = k or Y; 0 & b. 1). Note that the conditional probability P(Y; AlZ,, Y; E kO) should be evaluated whenever the i-th observation is generated by the rare class (i.e., Y; = k) or the major class (i.e., Y; = 0). However, the conditional probability P(Y,- = k| Y; = k or Y. = 0 & h, 1) might not be computed for an ob- servation i from the major class (i.e., Y, 0), unless it is also sampled (i.e., b, = 1). Simple algebra shows that for 1 1 k < K, we have
CASE 2. In the previous subsection, there exists only one major class (corresponding to = 0). In fact, our method can be readily extended to a more general setting with mul- tiple major classes. To fix the idea, consider, for example, the case with two major classes. Denote the two major classes by l 0 and i 1, respectively. Then, the logistic regression model becomes
P(Y, k Z,,Y, = or Y 0& =1)
exp(Z, 07 + +ogh)) aub)
wio = 1 exp exxp
1 1+ exp( 22, 0% + a)bb)'
(Z,TT) + Σx exp (Z. 8 + +aN)
exp (2,
where ag = ON - log NN. This leads to the fol- lowing subsample-based pairwise likelihood function as .V
(3)
1 exp (2, + Σk k= exp [ 0: + +aN)
Lak (aub(()) (0t) Di- aze au((Z Z 6: + aNb) - (at + aggb:) log i=
exp L 0 + aN)
{1+ exp(22 2 0% + eub)] for every rare class 1 < k 5 K. Then the SPMLE can be easily obtained as Bamb = argmax.- Cash (Bt), whose theoretical properties are given by the following Theorem 2.3.
w
+ exp (Z 01) + Σ ビす exp (Z, 02 + aN)
for < k < K. The key difference is that there are two major classes involved in (3). In contrast, there only one
5

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
major class involved in (2). To estimate the model param- eters, the pairwise log-likelihood in Section 2.4 remains valid. The only difference is that the convergence rate of 31 becomes vN. However, the convergence rate of the parame- ters associated with the rare classes (i.e., Ar. for 2 v k S K) remains v Neex,
are almost the same as those of the GMLE. Moreover, larger sample size N makes these three estimators more accurate with smaller log(RMSE) values. The nearly iden- tical results of both the NR and GD methods for GMLE suggest that both algorithms can be used to compute the GMLE. The nearly identical results between PMLE and GMLE (both NR and GD) suggest that the PMLE should be asymptotically as efficient as the GMLE. All these findings are consistent with the average CPU time values required for these three meth- ods increase as the sample size N increases. Compared to the NR algorithm, the GD algorithm requires more time for GMLE computation. Among all these three methods, we find that the PMLE costs the least amount of computation time.
3. Simulation Study
theoretical claims. By Figure 3(b),
3.1. Comparing GMLE and PMLE
To demonstrate the finite sample performance of the pro- posed methods, number of simulation studies are con- ducted. A multi-class logistic regression model (1) with multiple rare classes is used to generate the data. The co- variate X; E IRP independently generated from (0, Σ) with ( E RPxP and dij = 0.5la-j]. The total sample sizes are set as N 1 x 10a, 2 x 10t and 10a. For fixed N, set o. = 7 log N with 7 -0.5. Addi- tionally, 0g E I is generated from a (p 1)-dimension standard normal distribution for 1 1 k S K. To gain some intuitive understanding, we report in Table I the estimated values for E(N)) and E/N. We find that E(N))/N steadily decreases towards 0 as N + oc. Meanwhile, we find ((N) + 0o as N 20.
Aa
2048
2-11P
(43
(5)
mates PALL
Table 1. Rare class phenomenon with different p and K. Recall N is the total sample size. Define ((N+)) as the expected average sample size of K rare classes, and E(Nx)/N as the rare class percentage.
(00
p= 10 = B(MG/AN()
P= 50,K'
300, K 50
EiN,)
E(N,)
B(M.YN())
E(N,)
((N.)/N(()
10a
507
0,507
472
0,472
412
0,412
2 10
730
0.365
688
0.344
622
0,311
6x 10
0.234
0.224
To evaluate the performance of the GMLE and PMLE, dif- ferent numbers of rare classes (i.c., K) and different feature dimensions (i.e.,) p) are studied in three cases. For GMLE, the NR method and the gradient descent (GD) method are studied. We start with a relatively simple case with a small number of rare classes K 10 and low feature dimension
The left panel shows the boxplots of RMSE values in log- scale for the three estimation methods. The right panel presents the bar charts of the average CPU time values in log-scale for each method. The left white box shows the results for the GMLE computed by the NR algorithm. The middle light box illustrates the results for the GML F. computed by the GD algorithm. The right dark box presents the results for the PMLE by NR algorithm. Each box is summarized based on M 100 replications.
Figure 3.
p 10. Let (m) k.j 1 S S p 1,1 S S K)T be one particular estimator obtained in the m-th replication (e.g.. @pair). To evaluate the estimation accuracy, we calcu- late the Root Mean Square Error (RMSE) as RMSE
1 E th replication. This leads to total of M- 100 RMSE values. Those RMSE values are then log-transformed and box-plotted in Figure 3(a) and (b). To evaluate the computa- tion efficiency, the average CPU time values (multiplied by 10 and log- transfordd))) for each method are reported.
0x ) 1/2 for the m-
3.2. Larger p and K
We next consider cases with larger number of rare classes (i.e., K = 20) and higher feature dimension (i.e., p 50). In this case, the global Hessian matrix dimension becomes (p + 1)K x (p + 1)K = 1,020 x 1,020 (including the in- tercept term). Thus, a more challenging case for the NR algorithm, even though it remains implementable. The
By Figure 3(a), we find that log(RMSE) values of the PMLE
6

---

(IoU) score Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
resulting log(RMSE) values and average CPU time values in log-scale are computed as before and are plotted in Figure 3(c) and (d). By Figure 3(c), we find that log( values of these three methods are almost the same. A larger N makes these three estimators more accurate with steadily decreasing log(RMSE) values. These findings are consistent with our theoretical finding. As shown in Figure 3(d), the computational CPU time values of these three methods es- calates with the growth of the sample size N. However, the story changes for the NR algorithm and the GD algorithm for the GMLE, With the global Hessian matrix dimension expanding to 1,020 x 1,020, the NR algorithm becomes more expensive in the CPU time cost as compared with the GD algorithm. Moreover, it is observed that the computa- tional efficiency of the PMLE remains the best.
10 2 x 10 and 5 10 For fixed N, we set differ- ent sampling probabilities n -N0011 This satisfies the condition in Theorem 2.3 that /TN/ =N + do as N + oc. We report ((Nbb)) values as the estimated sample sizes of the major class used for SPMLE, which are much smaller than the estimated sample sizes of the major class used for PMLE (N)). The average RMSE values are computed as before and reported as RMSEsPMLE in Table 2. The average CPU time values and reported as TSPMLE in Table 2. For comparison, the av- erage RMSE values and average CPU time values of PMLE are also provided as RMSEPMLE and TPMLE. By Table 2, we find that the average RMSE values of SPMLE decrease as N becomes larger. Meanwhile, we find that the average RMSE values of the SPMLE are slightly larger than those of the PMLE but with much reduced computation cost. These findings are consistent with our theoretical finding that the SPMLE is a consistent estimator with the same asymptotic efficiency as the PMLE.
computed as before
We next study an even more challenging case with much larger number of rare classes (K = 50) and much higher feature dimension (p- = 500). In this case, the global Hes- sian matrix dimension becomes (p + 1)K x (p + I)K- = 25,050 x 25,050. The standard NR algorithm can hardly be used to compute the GMLE in this case. Therefore, a standard GD method is used compute the GMLE. How- ever, the PMLE can still be easily computed on parallel or distributed system. The resulting log(RMSE) values and average CPU time values in log-scale are computed as be- fore and are then plotted in Figure 3()) and (f). By Figure 3(c), we find that (RME) values of PMLE are slightly larger than GMLE. The difference of (RMSE) values between these two methods vanishes as N becomes larger. These findings are consistent with our theoretical finding that both the GMLE and PMLE are consistent estimators with the same asymptotic efficiency. As shown in Figure 3(f), the PMLE remains computationally more efficient than the GMLE computed by the GD) algorithm in the term of the CPU time cost.
4. TikTok Screenshots Dataset
4.1. TikTok Screenshots Dataset
We present in this section an interesting real data exam- ple. The dataset contains total of 2,559 screenshots of size 720 1,280 randomly taken from TikTok live streams sponsored by different Audi dealers in China. For conve- nience, we refer to this dataset as the TikTok Screenshots (TTS) dataset. For a reliable evaluation, we randomly split the entire TTS dataset into two parts. The first part con- tains a total of 2.047 high-resolution images (about 80% of the whole data) for training, while the remaining 512 high- regh-resolution images (about 20% of the whole data) are reserved for testing. For an intuitive understanding, ran- domly selected screenshot images are given in Figure 4(a). As can be seen, the screenshot images usually take an Audi car in the center place with detailed car model information displayed in the car plate; see the red box in Figure 4(b). A total of eight car models (i.e., classes) are included in the TTS dataset. They are, respectively, A3 Sportback, A4L, AS Sportback, A6L, A7 Sportback, Q5L Sportback, Q7, and RS5. Then the objective of this study is to analyze the graphical information provided by the car plate so that the car model can be automatically and accurately recognized.
Table 2. Simulation results with p 50 and K- = 20. Define E(No)) as the expected sample size of the major class used for PMLE, E(Nob:) as the expected sample size of the major class used for SPML.E, and F(Nx)) as the expected average sample size of K rare classes.
B136)
B(N)b)))
RMSEysas
RMSEaPSILE
Tyaus
10P
90,558
28,603
472
0.061
0.062
0.875
0.261
2 10P
186.241
54,30
688
0.500
0.050
1,688
0.489
477.607
128.541
1.100
0.099
0.039
3,309
0.895
To prepare the data for subsequent analysis, we annotate each screenshot image manually with tight bounding box for each car plate; see the red box shown in Figure 4(b). Next, a large number of 100 x 40 boxes are randomly generated within the image; see the blue boxes in Figure 4(c). Then the sub-images bordered by these blue boxes are extracted and saved on a hard drive. We treat each sub- image as one sample. For each sample (i.e., sub-image), we need calculate its intersection-over-ume
3.3. PMLE with Subsampling
As mentioned before, the SPMLE method adopts a much reduced sample size for the major class, so that the com- putation cost can be further reduced. We then study the performance of the SPMLE. For illustration, we fix p = 50 and K = 20. The total sample sizes are set to be N- =
7

---

Pairwise Maximum Likelihood for Multi-Clas Logistic Regression Model with Multiple Rare Classes
learning model (i.e., the Visual Geometry Group's VGG16 (Simonyan & Zisserman, 2014)), which is classic con- volutional neural network with 20 layers and 14,714,688 parameters. Given the limited sample size, we cannot es- timate those parameters accurately by using our dataset. Instead, we directly adopt the pre-trained estimates from the ImageNet dataset, which has 1, 1,341,167 images (Deng et al., 2009). With the pre-trained parameter estimates, we could use the VGG16 model to convert each image into a feature vector of 512 dimensions. We finally arrive at a complete dataset with sample size of N = 56, 016, p = 512 feature dimension and (K + 1) = 9 classes
(e)
(b)
(c)
Figure 4. Left panel presents an example of the original image with size 720 1,280; middle panel presents the annotated image with the car plate tightly bounded by a red bounding box; right panel presents total of 200 randomly generated blue boxes with size 100 x 40.
4.2. Performance Evaluation
We first consider how to compute the GMLE. As mentioned before, the current dataset has high dimensional features with = 512 and a total of (K + 1) = 9 classes. Conse- quently, the standard NR algorithm can hardly be used to compute the GMLE. To solve this problem, we consider the GD method (Dekel et al., 2012). Various learning rates are considered and the best learning rate is used. We next consider how to compute the PMLE. The PMLE is compu- tationally convenient for two reasons. First, for each class pair, the Hessian matrix of the pairwise loss function is only of dimensions 513 513, which can be easily inverted. Subsequently, the NR algorithm can be readily implemented without any tuning parameter (e.g., the learning rate) selec- tion issues. The algorithm converges extremely fast with a quadratic convergence rate, which is much larger than the linear convergence rate of a standard GD method (Curry, 1944). Second, by the pairwise likelihood, the original multi- class learning problem is divided into multiple two-class learning problems. This problem can be trained in a fully parallel or distributed manner. That makes distributed esti- mation feasible and then leads to a significant reduction in time cost. Lastly, the SPMLE method is also implemented with the sampling probability given as TN = 0.25. By do- ing so, a much reduced sample size for the major class can be used and the computation cost can be further reduced.
with the bounding box (Everingham et al., 2010). Here the IoU is defined as the area of IR n B over the area of R U IB, where I refers to the sub-image contained in the red box and IB refers to the sub-image contained in the blue box. Following Redmon et al. (2016) and Liu et al. (2016), we label the extracted sub-image as 0 if the corresponding IoU < 0.2. In contrast, we label it as a class & with 1 S & < K according to the model type indicated by the car plate if the IoU 0.8. The sub-images with 0.2 IoU < 0.8 are discarded. See Figure 5 for an intuitive understanding of the extracted sub-images and their corresponding class labels. This leads to total of N = 56, 016 sub-images belonging to nine classes, where the first class (i.e., k = 0) represents the background class; the remainder are car model classes. The major class (i.e.,& k- = 0) accounts for more than 95% of the total sample. The percentages of other classes are bar-plotted in Figure 6 of Appendix A.4. As shown, this dataset aligns well with our theoretical framework.
k=0
k=
k=0
k=0
k k=1
k=2
k-3
k=4
Als New Audi Sportback
Audi A4L
IN Sporans
Audi A6L
km5
k-6
k=7
k=8
Additionally, we have included the following competitive methods for comparison on the TTS dataset: the focal loss (FL.) of Lin et al. (2017), the class-balanced loss (CBL) of Cui et al. (2019), the cost sensitive loss (CSL) and random downsampling (RDS) of Fernández et al. (2018). Specifi- cally, FL introduces a modulating term to the cross-entropy loss, focusing on hard samples and downweighting easy negatives. CBL is proposed to reweight the loss inversely proportional to the effective sample count per class. CSL addresses the imbalanced distribution by adjusting misclas- sification costs. RDS is a technique that randomly sam- ple the instances in the major class to balance the class distribution. All methods are optimized according to the suggestions of the original papers. Code is available at
Audi Q7
Audi Sport
Spertback
OSL
Figure 5. Examples of sub-images extracted from the TTS dataset. The class label is given above each sub-image. Here k = 0 (back- ground) is the major class. All other classes represent different car models. Specifically, lt = (A3 Sportback), (A5 Sportback), &= = 4 (A6L), Is = 5 (A7 Sportback), & = 6 (Q5L Sportback), = 7 (Q7) and = 8 (RS5).
2 (A4L), &
We next consider how to represent each extracted sub-image by a feature vector. In this regard, we follow the trans- fer learning idea of Tan et al. (2018) and Zhuang et al. (2020). Specifically, we directly transfer a classical deep
8

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
multi-class logistic regression model with one major class and multiple rare classes. Next, we conduct rigorous asymptotic study of the standard MLE. Based on the special structure of the MLE's asymptotic covariance matrix, we propose the PMLE. To further reduce the computational cost, we propose the SPMLE by down-sampling the major class. Theoretically, the PMLE and SPMLE are statisti- cally efficient asymptoticalll. Both of them are suitable for distributed computation with lower computational cost. Moreover, the SPMLE is easier to compute with much less computation cost compared with the other two estimators. Extensive simulation studies and TikTok live stream data analysis are presented to demonstrate their finite sample performance. To conclude this work, we discuss some in- teresting directions for future research. First, we focus on the logistic regression model in this paper. It is interest- ing to investigate more complicated and general models for the multi-class data with one major class and multiple rare classes. Second, the performance of our method in a situa- tion that the sample sizes of the different rare classes are of different orders remains unknown and requires exploration. Therefore, how to extend these methods to more flexible settings an interesting direction for future work.
Table 3. Prediction results for the TTS dataset.
GMLE
PMLE
SPMLE
FL
CBL
CSL
RDS
ACC
0.836
0.835
0.824
0.794
0.789
0.747
0.763
AUC
0.997
0,999
0,999
0.998
0.998
0.991
0.996
Once estimator (c.g., the GMLE) is computed, it then applied to the testing dataset for the prediction evaluation. In this case, let é {0&- 1 S k S K} be the estima- tor computed from the training data and {(X), Y7) : < i S ] be the testing data. Then we can compute the prediction probability i:0 1/(1 + EE exp(X;T ) and was = (xp(X;T06)//E) + E exp(X; Bx) for
S k S K. We next follow the idea of Qiao & Liu (2009)
and predict the response by Y; argmaxp<*<< Was / where ne is the k-th class percentage of the training dataset. Then the prediction accuracy can be computed k) with the k-th sample size NE = EE [(, = k) for 0 < k < K. The overall accuracy is then calculated as ACC = (K + 1) - ACC, Next, for the k-th class, we pair each binary response Y, I(Y," = k) with its estimated class probability Wi and the AUC₁ value (Ling et al., 2003) can be computed. The overall AUC value is then calculated as AUC = (K + 1)-1 E the values for ACC and AUC are reported in Table 3.
as ACC2 = No- ENT I(,' = k) I(Y;
Acknowledgements
We thank the anonymous reviewers for helpful comments on earlier versions of this paper. Danyang Huang's 's research is partially supported by the National Natural Science Foun- dation of China (72471230), fund for building world-class universities (disciplines) of the Renmin University of China, the MOE Project of Key Research Institute of Humani- ties and Social Sciences (grant 22JJD1 10001) and Public Computing Cloud, Renmin University of China. Hansheng Wang's s research is partially supported by National Natural Science Foundation of China (72495123, 12271012).
-n AUC, Both
By Table 3, we find that our methods outperform all com- petitors. Among our methods, we observe that the overall ACC value of the GMLE method is 0.836, which is slightly higher than 0.835 of the PMLE method and 0.824 of the SPMLE method. In terms of AUC values, all the three meth- ods are extremely similar with very tiny difference, which might be due to random error. The key difference is the computational time. More specifically, the CPU time cost of GMLE is about 145.85 seconds. In contrast, those of PMLE and SPMLE are given as 42.12 seconds and 12. seconds, respectively. The outstanding computational efficiency of PMLE and SPMLE is mainly because they can be computed by the NR algorithm in a parallel way. The computation cost of the SPMLE method is lower due to a much reduced sample size for the major class.
Impact Statement
This paper addresses the problem of multi-class logistic regression with major class and multiple rare classes. We propose the PMLE and SPMLE methods. Unlike the computational challenges of traditional approaches, they reduce complexity by decomposing the problem into mul- tiple pairwise two-class problems, while ensuring asymp- totic efficiency and enabling parallel computation. This work provides an efficient solution for handling imbalanced multi-class data and contributes to related fields in machine learning.
5. Concluding Remarks
We study the problem of multi-class logistic regression with one major class and multiple rare classes, which is moti- vated by a real application about TTS data analysis. To motivate our method, we make a natural extension from the two-class logistic model in Wang (2020) and construct a
References
Abramovich, F., Grinshtein, V., and Levy, T. Multiclass classification by sparse multinomial logistic regression.

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
IEEE Trunsactions on Information Theory, 67(7):6677- 4646, 2021.
Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, P. Focal loss for dense object detection. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 1980029885 2017.
Chen, T., Kornblith, S., Swersky, K., Norouzi, M., and Hinton, G. Big self-super models are strong semi- supervised learners. Advances in Neural Information Processing Systems, 33:22243-22255,, 2020.
Ling, C. C. Huang. J., Zhang, H., et al. Auc: statisti- cally consistent and more discriminating measure than accuracy. In Ijeai, volume 3, pp. 519-524, 2003.
Cui, Y., Jia, M., Lin, T.-Y., Song. Y., and Belongie, S. Class- balanced loss based on effective number of samples. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 9268-9277 2019.
Liu, W., Anguelov, D., Erhan, D., Szegedy, C., Reed, S., Fu, C.-Y., and Berg, A. C. Ssd: Single shot multibox detector. In Proceedings of the European Conference on Computer Vision, pp. 21-37. Springer, 2016.
Curry, H. B. The method of steepest descent for non- non-linear minimization problems. Quarterly of Applied Mathemat- ics, 2(3):258-261, 1944.
Ma, Y. To shop or not: Understanding chinese consumers' live-stream shopping intentions from the perspectives of uses and gratifications, perceived network size, per- ceptions of digital celebrities, and shopping orientations. Telematics and Informatics, 59:101562, 2021.
Dekel, O., Gilad-Bachradd R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Maalouf, M. Logistic regression in data analysis: an overview. International Journal of Data Analysis Tech- niques and Strategies, 3(3):281-299 2011.
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vi- sion and Pattern Recognition, pp. 248-255. IEEE, 2009.
McCullagh, P. and Nelder, J. A. Generalized Linear Models. Routledge, 2019.
Deng, J., Russakovsky, O., Krause, J., Bernstein, M. S., Berg, A., and Fei-Fei, Scalable multi-label annotation. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 3099-3102, 2014.
Mou, C., Liang, A., Hu, C., Meng, F., Han, B., and Xu, F. Monitoring endangered and rare wildlife in the field: A foundation deep learning model integrating human knowledge for incremental recognition with few data and low cost. Animals, 13(20):3166 2023.
Everingham, M., Van Gool, L., Williams, C. K., Winn, J., and Zisserman, A. The pascal visual object classes (voc) challenge. International Journal of Computer Vision, 88 (2):303-338, 2010.
Mullapudi, R. T., Poms, F., Mark, W. R., Ramanan, D., and Fatahalian, K. Background splitting: Finding rare classes in a sea of background. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8043-8052. 2021a.
Fan, J. and Li, R. Variable selection via nonconcave pe- nalized likelihood and its oracle properties. Journal of the American Statistical Association, 168456) 2001.
Mullapudi, R. T., Poms, F., Mark, W. R., Ramanan, D., and Fatahalian, K. Learning rare category classifiers on a tight labeling budget. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 8423- 8432, 2021b.
Fernández, A., García, S., Galar, M., Prati, R. C., Kraweryk, B., and Herrera, F. Learning from Imbalanced Data Sets, volume 10. Springer, 2018.
Nelder, A. and Wedderburn, R. W. Generalized linear models. Journal of the Royal Statistical Society: Series (General), 135(3):370-385 1972.
Fox, J. Applied Regression Analysis and Generalized Linear Models. Sage Publications, 2015.
George, S. Turki, H., Feng, Z., Ramanan, D., Pillai, P., and Satyanarayanan, M. Low-bandwidth self-improving transmission of rare training data. In Proceedings of the 29th Annual International Conference on Mobile Com- puting and Networking, pp. 1-15, 2023.
Qiao, X. and Liu, Y. Adaptive weighted learning for un- balanced multicategory classification. Biometrics, 65(1): 159-168, 2009.
Ratner, A., Bach, S. H., Ehrenberg, H., Fries, J., Wu, S., and Ré. C. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases, vol- ume 11, pp. 269. NIH Public Access, 2017.
Li, X., Zhou, J., and Wang, H. Gaussian mixture models with rare events. Journal of Machine Learning Research, 25(252): 2024.
10

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
Redmon, J., Divvala, S., Girshick, R., and Farhadi, A. You only look once: Unified, real-time object detection, In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 779-788, 2016.
Zhu, Y., Huang, D., Gao, Y., Wu, R., Chen, Y., Zhang, B., and Wang, H. Automatie, dynamic, and nearly optimal learning rate specification via local quadratic approxima- tion. Neural Networks, 141:11-29) 2021.
Simonyan, K. and Zisserman, A. Very deep convolu- tional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
Zhuang. F., Qi, Z., Duan, K., Xi, D., Zhu, Y., Zhu, H., Xiong, H., and He, Q. A comprehensive survey transfer learning. Proceedings of the IEEE, 109(1):43-76, 2020.
Song. Y. and Zou, Minimax optimal rates with heavily imbalanced binary data. IEEE Transactions Informa- fion Theory, 2024.
Su, J., Wang, D., Zhang, F., Xu, B., and Ouyang, Z. A multi- criteria group decision-making method for risk assess- ment of live-streaming e-commerce platform. Journal of Theoretical and Applied Electronic Commerce Research, 18(2): (82)):126-11 11111126114111 111,, 2023.
Sun, Y. Zhong, Y., Zhang, Z.., Wang, Y., and Zhu, M. How technical features of virtual live shopping platforms affect purchase intention: Based the theory of interactive media effects. Decision Support Systems, 180: 14189, 2024.
Tan, C., Sun, F., Kong, T., Zhang, W., Yang, C., and Liu, C. A survey on deep transfer learning. In International Conference on Artificial Neural Networks, pp. 270-279. Springer, 2018.
Tanha, J., Abdi, Y., Samadi, N., Razzaghi, N., and Asadpour, M. Boosting methods for multi-class imbalanced data classification: experimental review. Journal of Big Data, 7(1):1-47, 2020.
Van der Vaart, A. W. Asymptotic statistics, volume 3. Cam- bridge university press, 2000.
Vershynin, R. High-dimensionee probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018.
Wang, H. Logistic regression for massive data with events. In International Conference Machine Learning, pp. 9829-9836. PMLR, 2020.
Wang, H., Zhang, A., and Wang, C. Nonuniform negative sampling and log odds correction with rare events data. Advances in Neural Information Processing Systems, 34: 19847-19859, 2021.
Wang, J., Wang, H., Nie, F., and Li, Feature selection with multi-class logistic regression. Neurocomputing, 543: 126268, 2023.
Zhang, H., Hu, Y., Qian, 7., Sha, J., Xie, M., Wan, Y., and Liu, P. Enhancing rare object detection on roadways through conditional diffusion models for data augmen- tation. IEEE Transactions on Intelligent Transportation Systems, 2024.

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
A. Supplementary Material
A.I. Proof of Theorem 2.1
To study the asymptotic property of MLE, we first derive the log-likelihood function [(0*) = Σi= -x= ai log a
based on (2), where 0* (Ø) .... 1 .k ) T E R is the stacked coefficient vector with dimension q = (p + 1) and
Og (3 8xx ) E RR++1 be the associated regression coefficient parameter. Here 0g (Y, = k) E {0, 1] is the binary
vector and i P(Y; k:|Z,,) is the rare class response probability vector. Next, can estimate the maximum likelihood
estimator = ar (())). Specifically, to show that θ is consiscon,,,, it suffices to verify there exists some
constant C > such that
sup EER- &ER-
C(O" +E/VNEaN) < <(0")
(5)
with probability tending to 1 as N goes to infinity (Fan & 2001). By Taylor's expansion, we have
c(0' + +//NNENN) - -(0)) - {sT ((0)) + t ((0")) (1+ (1+0,(1))
We can demonstrate that /(0))/ / NNex= (1) in Step and ((()))(Ne>*) converges to a negative definite constant matrix in probability in Step 2. Then we could verify (5) holds for sufficiently large C. Due to the strict convexity of
L(O*), we obtain that su C(0' + E/VNeax) < L())). As L(O") is maximized at θ, we know θ lies in the ball {0r +E/NNeux : ||l|| S C}. In other words, we have Q =
Given Ô is
we can apply the Taylor expansion and have
VNcaN G - (======) ((
- (E(O*)/VNEa))
where θ* lies between θ and O". In the following two steps, we would further prove when N -> oo, we have
(NeaN) 11/2((07) - E)), (NeaN) -1((0)) +p -Σ",
(6)
(7)
where E- diag Eg: : 1 k S K} and Σ E exp( 2, (TT }. This completes the proof of Theorem 2.1.
STEP 1. To verify (6), we compute the mean and covariance of (Ne (Ne)x)-12((()) respectively. For simplicity, we denote (0r) = a0(())))(e))))))) /00 Then, we can rewrite L(0*) = ((r( .... (0))) E R'. Since we have (x())) Ein (aik ) Z., suffices to compute the mean and covariance of (Ne 1/2 L/ (0*) respectively.
It can be verified that Ef(x = NET(E(aa 2.) - wi 2i] = O. Hence, we prove E { = O. Next, we calculate cov oor(((0r) }. Then, it suffices to work on the diagonal matrix cov (Nee*))11/2xx (6)) and the off-diagonal matrix cov (NNeaN) -1/2 Le, (0*), (N (0*) }. respectively.
First, we compute \//
One can verify that
exp (Z 0%)
cov 11 = = =x- (a+t -wtt) 21) E
2,2,
1 Σ k= exp (2 0z + tax)
exp (2Z, 0%)
ZiZi T
E5{ exp (z 02) Z,Z, T } (1+
(8)
11+ 1= exp (Z, 0% + +aNn)
To obtain the first equality of (8), we use the fact that coví - W = E[E((ax -
El Z,Z,) - E (w,ZZ,Z,") Consequently, we find that the second term E ( Z,Z,") ) is the higher order term. Thus, we focus on the first term E (wi. Z, Z,Z,") and prove the second equality of (8). To this end, we need to verify the fol- lowing three conditions. First, it is obvious that exp (Z, (1+
exp (Z 0 +an)} -1 |2,112 < exp (Z 0:) 12.1 Second, it is noteworthy that exp (7 (1 + Σ exp (7 0% + aN)) Z,7, converges to exp (Z. 0 Z,Z, almost
12

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
surely as N + oc. Lastly, we know that E(e % [2,1 < oc by the condition that E(e"IiZ.l)) < oo for any > 0 (Wang, 2020). Combining the above results, the second equality of (8) can be verified by the dominated convergence theorem. Then, by the similar technique, we calculate
cor((No (
Ex (0"), (N Lx. (0r)
- e aN
aNE E E (ath: - -Wik,) (aitz - -Wjkm) Zi 2 | |
exp 0%,0
0% + 0%,)
= EN F.
{1 + Σm= exp (Z/] 02 + (xx] } Z,,,7"
-EN { {exp (Z 0% + Z; p Z T| } { (1+
= O(e*x),
where the first equality is due to Elagx w 2,) = 0, and the second equality is because E (a - wit, (aiks - wiks- It refers that the off-diagonal matrix of cove / Vee [(e*) } is of the order O(exM) and converges to 0 when N + co.
(hk )Z }
E E(oik, 22ka wik Oskz + w k/ [z,)
We then verify the Lindeberg-Feller condition. Define 7/1 = ((a:) 2T .... (aik - 2 E R.. We then have
||mll (0ml1(((11))) [[|mx]]| vNeawe)
K
= NE Σ wikh { [I(1-- -
(1(11w;hh)2) 211l + Σ |u Zi|l 2 2=ll"'/10
-11((1==))) 2/12 + Σ
| Zill² > Ne 2)
ki
K
K
K
+NE u0o
Σ 21
|| 7,17 2:11? > 2)
+
1=
1=1
We first compute that
K
NE
Wik
[1(1 - [|(1-w5h)Z:11 w/h) + Σ |witr 2i11 (r(l()]((()))) with 1211+ + Σ
| 20ll²= > Neam?)
k'
k'g
K
K
NE
Wikk
Σ Wik
+1)1|2/1?
Σ
|wi/ |wii No }
k=1
k=1
k=1
K
K
<
Ne
E
Σ
e
7
6%
wit
22
+ 1) 11 |
Σ
|| Zol? NE 2)) = o(Ne
km
kmm
Am
Moreover, is can be verified that
K
K
| [ 2/ 1|2x
|w Li12 > 2N
NE
W
10
k= 1
1=
K
< NE
Wi Zz|l 1 T( Σ
|| 7il > NeaN 2) o(NeeN).
Thus, for any e >> O, we have En F 1/ the proof of (6) by applying the Lindeberg-Feide Feller central limit theorem (Van der Vaart, 2000).
7[ (Neaxc)) of )) Combining the above results, we finish
STEP 2. To verify (7), we compute the mean and covariance of (Ne ž(0-) respectively. For simplicity, we denote for 1 < k < K, and denote the (ki, k2) off-diagonal block matrix L (0-) = 0 (0)(()))))))))) /80 Tor e ((+++)x(++1)) for I k * k S K.
the k-th diagonal block matrix Ee (0r) = 8 ((0+) /00;00))0000TTT e R(++1)((++))
13

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
First, we compute the mean and covariance of (Neam)=+Lxx (0*) respectively for 1 S l K. We can derive (0*) E wit (1 w Z Then, we have
E (N
Ex (0)) } = - 10tt E Wis [,Z,'
exp (1)
exp (7 + +aN)
-E
1
ZiZ!
1 1k=1 exp ( 0% + aN)
K
K 1+ I exp ( 0% + (.N)
= - -E{ exp (Z 01) 2,2," _ { 1 +(1).
where the last step holds by applying the dominated convergence theorem. Then, we compute the covariance of (Nexx)-1((er) Consider the (Ji, component of L. (0*) with S j1, $ + 1, we could verify
var (NeaN)-1Laasl) (0") } 6 2ar with (1 w Zz.ji Zi.52
2
exp (22, 0%)
exp (2 0% + aNN)
= =N-EE
1 1+ Σ k= exp (,, 0% + taN)
Thi1 Ziis0
+1+)
K Σ 1= exp (Z, 0% + xNn}²
exp (2,0%)
exp (2 0% + aN)
-2
Zi.i Zenta
k= exp (Z, 0% + aN)
k
1+ k= exp (Z, 0% + aN)
' exp (z 02) Z1 Zi.ja } { + {1))]
where the last step is because of the dominated convergence theorem. Consequently, we know that var var((Ne (Neax)-1 ERSIiO (0)) } + when N + oc. Together with F((Nexx)=*Lxx we have (NeaN)-l (x*)) tp E{ cxp (z, ZzZ } as N - oc for the k-th diagonal block matrix.
Next, we compute the mean and covariance of (NeaN)-1 Eig (0*) respectively for 1 I bı F h2 S K. We can derive EK (0r) = - win wing Z,Z," Then, we have
B (NNoay)-1
0 caN Ef W/e wike Z,Z7
exp (2 0%, + +z 0,062 + +2aN)
axx E
7:.77
{1 RK exp (2. + aN)
= -xx E (exp 22, 02, + 2, 2 {1+
where the last step is due to the dominated convergence theorem. This refers that when N + oo, E Een) + O. We then compute the covariance matrix of (Nea*) E (0*). Here we focus on the (2, component of off-diagonal matrix ( (0') with 1 S J1.32 S p + 1, we have
var (NE " (0²) = N 22a var (wies Wike Zissr Ze.52) exp (22 02, + +22, 072- + +4aN)
N c 20x E
23.12
{1 EK exp (2 0/ + +aN)]
exp (Z 0% + z2.0%, 0% + +2aN)
-N-1 1-10--200 20N E²
{1+ ΣK k= exp [z, 0x + aax) 1 22.30 Ziss
= N 1- 20x var (exp (Z, 0% + 2, 0% Zi.ji Zo.i2 } { {1+0(1)}
where the last step is obtained by the dominated convergence theorem. Then we immediately know var var( (N Ekgks.hni (0r) + 0 when N - co. Further, this implies the maximum likelihood estimator converges asymptotically to a matrix with block diigonl structure. Combining the above results, we have (NeaM)- "Enn - (0*) -pp 0 as N - oo for
the off-diagonal block matrix. Thus, we accomplish the proof of (7).
14

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
A.2. Proof of Theorem 2.2
In this appendix, we study the properties of the pairwise maximum likelihood estimator @peir for 1 S k S K. Specifically, need to investigate set of major major-and-res and-rare class pair logistic regression models follows
cxp(Z; 0g + aa)
Z (0.K)))))))))) 1 exp((z 0% + aN)
Z.
for every rare class < k < K. Define wi,0k P(V;= k 2, Y (0, k)). Consequently, the conditional log-likelihood function for the two-class logistic regression problem
be written as Lox E aek log W2,uk + a.0 log(1 wr,ok) = Ei=1 (2, 0% + +ax)= - (ax + a.) log [1 + exp(2, 0% + aN)}. Then two-class MLE can be obtained as Oaair argmaxg; Lox (fg). Similarly with the proof of Theorem 2.1, to show that @pair is -Neew-consisten and asymptotically normal, We would further prove in the following two steps
.
(Near) - 1/2 Luu dd (0,, En), (NeaN) -1 Lox (0%) -pp -igg
(9)
-Lo
(10)
as N + oo in the following two steps, where Ex = E exp(Z, 0%) }. This completes the proof of Theorem 2.2.
PROOF OF (9). We compute the mean and covariance of Łos (0%) respectively. Note that LOx (0%) Σ {ass (a, +
wo)) } Zg. Consequently, the mean of Lox (6%) can be calculate as E Lus (et) NE { aax - (a. + aaa0)waaoo ] Zi| = NE wf - (wix + wio w Z 0 because of the fact that (wie + + w = wie In the meanwhile, the covariance of Los (0%) can be calculated as
-1/2 -112 Lon (0z) = (aaaas =
2 (asx + a:o) (ooo)wwsoo ZiZ,
eonN E { Osk + (at + aw)) wi.0 -2auwsi ZiZz7]
aa F { " + (wit + wio)o Ju,on 2m0u [7,77]]
aav E wii wi,ox) Z: Ex o(1)
where the first equality is due to the fact that E[{ Ask - (aa + 4 (oo))a,,k ok Zz] = 0, the third equality holds because (wit + who) = with and the last equality by the dominated convergence theorem.
We then verify the Lindeberg-Feile condition. For any > 0,
N
E (aax (ask + wi Zi| [[] [ar (aik + aso))ct Zill > VNeaxe) Σ
NE wif (1 wi (10
VNeanc)}
+NE (1- (1- |1 |2 (10T(([W,.//ll1 vNeexe)
< NE |2 2||| VNeaNe)] + NNE wp.0x |2/ | (1 Zill > VNeave)
s NN B |2 01 3 > vNeawe)] o(Nexx).
Combining the above results, finish the proof of (9) by applying the Lindeberg-Feet Feller central limit theorem (Van der Vaart, 2000).
PROOF OF (9). We compute the mean and covariance of Lox (0i) respectively. Note that LoR (0t) = - - (ast +
an)) a.)) (ko)wi,ok (1 wapok) Z,Z,T Hence, we obtain the mean of ΣaR (0z) E ) Eox (0z) -a E ((1t +
ax0) (oo) (1 -.,oo)) wr,.k)/ Z,7, = =- -e-aN w E (w + w wx, ) = -e-ax an E. w (1 -.i,o)
15

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
(1 (1 + o(1)) We then compute the variance of the (ii.j2)-th element of (Neav)- (0t) and have
var (NVEaN) (alean)=Coooooae (o)
N c 2aN F (ast + a:d) w²,00 (1) 2 Tizz }
2aa
-N-le e-lle-2xx N0 E² (aix + a:o) wi,) wi,0s) Zisi Zisz
N 2a, E wiewerkk (1 wr.00)) ) [ } E² W ( 2
Zish Zizz
= Iar var exp (Z. 02)72)) Zoja } (1 + o(1) = O(1/N),
where the last equality is because of the dominated convergence theorem. Consequently, we know that var (Neax)= Con (0t) + 0 when N + oc. Together with the result of E| (Neex) Zox) we have proved that (Ne*x) -1 Lox (fg) -tp Eg as + co. This accomplishes the proof of (9).
A.3. Proof of Theorem 2.3
In this appendix, we study the properties of the subsample-based pairwise maximum likelihood estimator @zub for 1 S k S K. Specifically, we need to investigate a set of major-and-ran class pair logistic regression models as follows
exp( 0 + ambb)
p(y:= = kb Z, Y = kr Y; = 0& bi =1) 1 exp( 0% + agpb))
where aN aN log NN. Define w P(Y. kZ,, Y, = k or Y; 0 = =). By the condition that /N/e"x + 0o as N + co, we have aub N' + -o, which makes wr,0x - 0 as N + co. Consequently, the conditional
log-likelihood function for the k-th two-class logistic regression problem can written as Lax (ot) = Σim1 ais log wiikk + a,ob; log w7,00 ΣN au (2, 0% +a (a.* + agob;) log {1+exp exp (2, 02 + +xx))) }. where a aN -log N and P(b; = 1) n for some sampling probability 0 AN < 1. Then SPMLE can be obtained as 0rab argmax,; 4 Caub (0t). Similarly with the proof of Theorem 2.1, to show that Orub is VNe -consiseett and asymptotically normal, We would further prove in the following two steps that
(Neax) - 1/2 Asub (0%) + NOO, ( (Ne*x)
Lok
(11)
-1 Auub OOk
(0t)
7
Si:
(12)
as N oo, where recall Σg- exxpp(Z (x), This finishes the proof of Theorem 2.3.
PROOF OF (11). We compute the mean and covariance of Ezub (ft) respectively. Note that Čaub (an)(8)) = = {aix
(ask + a;ob;) w } Zz.. Consequently, the mean of Laub (0%) can be calculate as E caub (0h) } EN (a:x +
1,0k } Z.] = 0 because of the fact that (Wir + w Ju = w Meanwhile, the covariance of ixub (0t) can be calculated as
dunb)) Z,] = [F[["G - (urt + = Junkuuk
cov (NNCx) -1/2 Lon (8%) = c coN cONNE((a - (att + azobs) wi.ukk 1 f Z
= e aN E { aik + (as + azob;) uubb -2a 2,0k
= NN Fz { Wij + (win + w aI N Nuu sub2
sub 2w
2 -
sub -N E (a(wia w0tk 24 Ex + o(1)},
where the first equality is due to the fact that E[(axx (ax + asob:)w:ut | Zi] = 0 and the third equality holds because (wie + WioN N Jwonkb wi-
16

---

Pairwise Maximum Likelihood for Multi-Class Logistic Regression Model with Multiple Rare Classes
We then verify the Lindeberg-Feller condition. For any > O,
N
E [11 aik (ais + a.pb;) wi sub /
Zi|l [ [I] (asx + a.pbi) wiikk } Z, VNeexe)
= NE
2 -i,0k
w wit0k) 2ell > vNeeas))
+NaxE E (1- 22 |2 2 2:11 > VNeanc) })
< NE Wik 2z [[|22|[112|1 > VNeaNe) + NNN E
sub2
( ( 2i|1 > vNeave))
wi.kk
s 2N Fl (l 011 12 [(12| vNeaxe)
o(NeN)).
Combining the above results, we finish the proof of (11) by applying the Lindeberg-Feide Feller central limit theorem (Van der Vaart, 2000).
PROOF OF (12). We compute the mean and covariance of Čaub (0;) respectively. Note that 2 (0t) - --
2i=1 (ask +
ax0d)) wolkk (1 sub
i,0k Zz Hence, we obtain the mean Laub (6%) as E (Neax) > Ssub
Log (0t) = - E (ask +
a,ob,)wr 2,0k (1 w 1,0k Z,Z," } -a
aN E (wf + T Juitok (1 winh Z ] - -
oN E w (1, Z
- Dg [1- + o(1)). We then compute the variance of the (2) element of (NeoN) Lov (0%) and have
var (Ne
Jija -L
jaub
(0t)
e-le-2os 20xx E (ase + axabs) w (1 Wi,kk! )² Zi. Z
-N-te 2aN E² (ask axub)) w (1 wii0k] Zisr Zijz
N 20x FB{ Wi (1 w((0k)) )² 22223,,550 72 }
F:a w (1
wiuh Zajn Zija }
-ar exp (2, 0%) Zisi Lito } } - o(1) O(1/N),
where the last equality is because of the condition that witk + 0 as N + xc and the dominated convergence theorem.
Hence, we know that var( (Neax) -1 caub
jok (07) + 0 as N + co. Together with the result of E (Ne Jsub (0%) }.
we have proved that (Ne**) -1 /sub
OO (0t) +p 2% as N + co. This finishes the proof of (12).
A.4. Illustration Details
In our TTS dataset analysis, there are total of N=56,016 sub-images belonging to nine classes, where the first class (i.e., k = 0) represents the background class; the remainder are car model classes. The major class (i.e., k 0) accounts for more than 95% of the total sample. The percentages of other classes are bar-plotted in Figure As shown, this dataset aligns well with our theoretical framework.
Percentages of Different Audi Car Modes (%)
1.0
0.8
0.6
0.0
Figure 6. Sample percentages of different Audi car models.
17


Reviews:
[{"review_id": "cyUbxvbeIY", "reviewer": "Reviewer_6Ats", "summary": "This paper studies the parameter estimation problem for Multi-class logistic model with one major class and $K$ rare classes. The main observation is that, under certain decay rate assumptions on the coefficients of rare classes. The joint MLE estimator is asymptotically equal to the pairwise MLE estimator between each rare class and major class, and the pairwise MLE estimator significantly save the computation complexity. Authors also extends the theoretical guarantee of pairwise estimators to the sub-sampled setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the constructive suggestions. All the concerns have been well received and carefully addressed as follows.\n\n1. **Relationship between Two Models.** Note that the model (2) is a special case of the model (1), which is a more general model. As you have correctly noted, we can indeed start with the model (2) directly. However, we then lose the opportunity to explain why the model (2) is specified in its current form. Specifically, by starting from the general model (1), it seems clear that we have to set $\\alpha_{N k}\\rightarrow -\\infty$. Otherwise, the rare class phenomenon cannot be theoretically reflected. Moreover, we cannot have balanced rare classes unless $\\alpha_{N k_1}-\\alpha_{N k_2}=O(1)$ for any $k_1\\neq k_2$. Both the conditions (i.e., $\\alpha_{N k}\\rightarrow -\\infty$ and $\\alpha_{N k_1}-\\alpha_{N k_2}=O(1)$) enable us to re-parameterize $\\alpha_{Nk} = \\alpha_{N}+\\beta_{0k}$. That leads to the model (2). We now have explained this issue in the revision more clearly. Thank you so much for this kind reminder. \n\n2. **Imbalanced Class Assumption.**\nRequiring the rare classes to be sufficiently balanced is a relatively loose sufficient condition and not very necessary. In fact, if rare classes are unbalanced, PMLE can still be applied without any difficulty.  However, there is one critical condition.\nThat is the sample size of the target rare class must be sufficiently large. Otherwise, no consistent classifier can be learned. This seems to be a very basic and reasonable condition, which has been widely used in the past literature (Wang, 2020, ICML; Li et al., 2024, JMLR; Wang et al., 2021, NeurIPS). However, this very basic and reasonable condition can be easily violated, if rare classes are highly unbalanced. In such cases, some classes may be even rarer than others. We refer to those even rarer classes as tiny classes, whose sample sizes are often too tiny to support any meaningful statistical learning. This is the only reason we focus on the balanced case in our theoretical analysis. We now have made it clear in the revision.\n\n3. **Multiple Major Classes.** Our method can be readily extended to a more general setting with multiple major classes. To fix the idea, consider, for example, the case with two major classes. Denote the two major classes by $k = 0$ and $k = 1$, respectively. Then, the logistic regression model becomes:\n$$\nP(Y\\_i = 0 \\mid X\\_i)=\\frac{1}{1+\\exp(Z\\_i^{\\top} \\theta^*\\_1)+\\sum\\_{k = 2}^K \\exp(Z\\_i^{\\top} \\theta^*\\_k+\\alpha\\_N)}, $$\n$$P(Y\\_i = 1 \\mid X\\_i)=\\frac{\\exp(Z\\_i^{\\top} \\theta^*\\_1)}{1+\\exp(Z\\_i^{\\top} \\theta^*\\_1)+\\sum\\_{k = 2}^K \\exp(Z\\_i^{\\top} \\theta^*\\_k+\\alpha\\_N)}, (A.1)$$\n$$P(Y_i = k \\mid X\\_i)=\\frac{\\exp(Z\\_i^{\\top} \\theta^*\\_k+\\alpha_N)}{1+\\exp(Z\\_i^{\\top} \\theta^*\\_1)+\\sum_{k = 2}^K \\exp(Z\\_i^{\\top} \\theta^*\\_k+\\alpha\\_N)} \\text{ for }2 \\leq k \\leq K. (A.2)$$\nThe key difference between (A.1) and (A.2) is that the diverging intercept $\\alpha_N$ is involved in (A.2) for rare classes but not in (A.1) for the major class. To estimate the model parameters, the pairwise log-likelihood in Section 2.4 remains valid. The only difference is that the convergence rate of $\\hat\\beta_1$ becomes $\\sqrt{N}$. However, the convergence rate of the parameters associated with the rare classes (i.e., $\\hat\\beta_k$ for $2 \\leq k \\leq K$) remains $\\sqrt{N e^{\\alpha_N}}$. We now have made it clear in the revision.\n\n4. **Minor issues.** For the other issues that you have mentioned, we have also corrected them carefully.\n\n(1) We have now formally stated the technical assumptions in the last paragraph of Section 2.1 as: \"Assume (C1) $\\alpha_{N k}\\rightarrow -\\infty$ and (C2) $\\alpha_{N k}+\\log N\\rightarrow \\infty$ as $N\\rightarrow \\infty$ for every $1\\leq k\\leq K$.\" \n\n(2) We have carefully discussed the decay rate condition $\\alpha_N+\\log N\\rightarrow \\infty$. Without this condition, we might have $\\alpha_N + \\log N \\to -\\infty$. Then, the expected sample size for the $k$th rare class becomes $E(N_k) \\approx NP(Y_i = k) \\to 0$ as $N \\to \\infty$ for every $1\\leq k \\leq K$. As a consequence, the sample sizes for the rare classes may be too small to yield any consistent estimator.\n\n**Additional Reference**\n\nWang, H., Zhang, A., & Wang, C., 2021, Nonuniform negative sampling and log odds correction with rare events data. NeurIPS.", "claims_and_evidence": "The theoretical statements and contributions made in this paper are easy to understand. However, there are several points that could further improve readability:\n\n\n1. I am a bit confused about the estimator under the model described in Equation (1). From my understanding, all subsequent operations (e.g., pairwise estimates, sub-sampling) are based on the model defined in Equation (2). Why not start directly with the model in Equation (2)? Additionally, the reductions made from the model in Equation (1) to the model in Equation (2) (paragraph 2 in section 2.2) should be explained more clearly.\n\n2. Please consider formally stating the technical assumptions mentioned in the last paragraph of Section 2.1.", "methods_and_evaluation_criteria": "The proposed method(pairwise MLE) is the main contribution of this paper, and is easy to apply. The applied evaluation criteria(estimation error) is standard.", "theoretical_claims": "I have not checked all the details of the theoretical proofs, but the independence structure revealed by Theorem 2.1 make sense to me given the assumptions made in this paper. And the Theorem 2.2 and 2.3 also seems reasonable given such independence structure.", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "This paper studies a special structure in multi-class logistic regression, which is new in this area. And the proposed new estimator provides a efficient algorithm under such structure, as demonstrated in their experiment.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:\n\nThe studied setting is new, and the proposed method is new and efficient.\n\nWeakness:\n\n1. In my opinion, the assumptions made regarding rare classes are too strong, which weakens the theoretical contributions of this paper. Specifically, the theoretical guarantees require the rare classes to be sufficiently balanced and impose an explicit rate bound on $\\alpha_N$. I tend to believe this is a relatively loose sufficient condition, as no lower bound results or counterexamples are provided to justify its necessity.\n\n2. The assumption that there exists only one major class (corresponding to $k=0$) seems restrictive. Can the current results be extended to a more general setting where there are $m$ major classes?", "other_comments_or_suggestions": "No", "questions_for_authors": "My questions are:\n\n1. Are there any necessity results on the decay rate condition $\\alpha + \\log N \\to +\\infty$ ?\n\n2. Can the assumption of a single major class be extended to accommodate a general case with $m$ major classes?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6O25qMRFZF", "reviewer": "Reviewer_wb9a", "summary": "This paper focuses on multi-class logistic regression with one major class and multiple rare classes, a problem arising from real applications.\nBy the suggestions from Theorem 2.1, the standard maximum likelihood estimators as well as the re-parametrized version are asymptotically independent for different rare classes, which in turn motivates the development of a new algorithm,  PMLE, by solving multiple pairwise log-likelihood functions. Since the pairwise log-likelihood functions contain the samples with large size in the major class,  minimizing the pairwise log-likelihood functions is still computationally challenging. To further accelerate the computation, the authors propose to solve subsample-based pairwise log-likelihood functions, termed as SPMLE. Theoretically, the authors prove that the newly-proposed algorithms, PMLE and SPMLE, require lower computational cost compared to the standard maximum likelihood estimators without compromising asymptotic efficiency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the constructive suggestions. All the concerns have been well received and carefully addressed as follows.\n\n1. **Diverging Number of Classes.** \nWith a diverging $K$, the expected percentage of rare classes should be even smaller.  To ensure a diverging sample size for each rare class, the technical assumption $\\alpha_N \\to -\\infty$ should be replaced by $\\alpha_N + \\log K \\to -\\infty$. The resulting theoretical behavior of our proposed methods remains fairly the same. More specifically, the convergence rate of the PMLE remains $\\sqrt{Ne^{\\alpha_N}}$-consistent. The PMLEs associated with different rare classes remain mutually independent asymptotically. More importantly, the resulting PMLE should be asymptotically as efficient as GMLE. To numerically demonstrate this point, we replicate the simulation example but with $K = [N^{0.25}]$. See below Table A for the detailed simulation results. We find that (1) both GMLE and PMLE remain statistically consistent, and (2) their asymptotic efficiency seems to be the same with extremely similar RMSE values. We now have made this point clear in the revision.\n\n### Table A: Simulation results with diverging $K$. \n| N         | $10^4$ | $2.5\\times10^4$ | $5\\times10^4$ | $7.5\\times10^4$ | $10^5$ |\n|-----------|--------|----------------|--------------|-----------|--------|\n| K         | 10     | 12             | 14           | 16             | 17     |\n| GMLE      | 0.114  | 0.091          | 0.077        | 0.068          | 0.064  |\n| PMLE      | 0.114  | 0.091          | 0.077        | 0.068          | 0.064  |\n| SPMLE     | 0.116  | 0.093          | 0.078        | 0.069          | 0.064  |\n\n2. **Minor Issues.** For the other issues that you have mentioned, we have also corrected them carefully.\n\n(1) In the revision, we have reorganized Lines 629-639 in the Appendix.\n\n(2)  In Line 93, it should be $1 \\le i \\le N$. We now have made it clear in the revision.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes. The proposed methods are corroborated by simulation studies and real-example analysis.", "relation_to_broader_scientific_literature": "A result similar to Theorem 2.1 in the submitted manuscript is also established by Wang (2020); however, their work focuses on an imbalanced two-class problem, whereas the manuscript addresses a multi-class setting with one major class and multiple rare classes. Notably, a new computationally efficient algorithm with theoretical guarantee is proposed in the manuscript, advancing beyond the scope of prior work.\n\n[1] Wang, H. Logistic regression for massive data with rare events. In International Conference on Machine Learning, pp. 9829–9836. PMLR, 2020.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. Inspired by the asymptotic covariance matrix of the global MLE,  the manuscript  proposed two methods, PMLE and SPMLE,  which \nhave a significant advantage in computation and are specifically designed for the problem of multi-class logistic regression with one major class and multiple rare classes.\n\n2. The established theory for PMLE and SPMLE  is quite impressive.  It reveals that the newly-proposed algorithms require lower computational cost without compromising asymptotic efficiency. \n\n3. Comprehensive numerical studies, including simulations and real-data analyses, demonstrate the effectiveness of the proposed methods.\n\n\nWeaknesses:\n\nThe appendix should be well-organized. For instance, Lines 629-639 currently appear cluttered and could be improved by using interline formulas for better clarity and readability.", "other_comments_or_suggestions": "Typographical remarks:\n\n1. In Line 93, it should be $1\\le i\\le N$.", "questions_for_authors": "In this work, the number of classes $K$ is treated as fixed. I think it may be interesting to investigate the theoretical behavior of the proposed method when considering the case where  $K$ diverges as the number of samples increases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wo630xmeDC", "reviewer": "Reviewer_rHhH", "summary": "This paper addresses the problem of multi-class logistic regression in scenarios with class imbalance: specifically, one class is overwhelmingly dominant and the remaining classes are rare. The authors develop a theoretical framework demonstrating that, under appropriate assumptions and asymptotic conditions, the maximum likelihood estimator (MLE) is asymptotically normal with a mean-zero error, and has an asymptotically block-diagonal covariance structure, implying that the parameters for the rare classes are asymptotically independent. Building on this insight, the paper proposes a pairwise maximum likelihood estimator (PMLE) that decomposes the multi-class problem into separate binary logistic regression problems, along with a subsample-based variant (SPMLE) that reduces computational costs by down-sampling the major class.  \n\n## Update After Rebuttal\nI raised my score as a result of a discussion with the authors (see below).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive suggestions. The concerns have been well addressed as follows.\n\n1. **Motivation and Practical Impact.**\n    - **Theoretical Motivation.** The focus here is the theoretical investigation of logistic regression with rare classes. Specifically, we find that the asymptotic covariance of the resulting MLE is block-diagonal, which further inspires the novel PMLE method. All the discussions in the introduction about customer purchase behavior are used to demonstrate the practical importance of our problem. However, with your kind reminder, we have realized that we might have overemphasized this point. We now have rewritten the section for better elaboration.\n    - **Comparison with Two-Stage Approach.** We consider a very ideal situation with all car plates having been correctly detected. All rare classes have been perfectly separated from the major one. We then only need to focus on rare classes. The detailed classification results on the TikTok Screenshots (TTS) dataset are given in Table A.1. Even under this ideal situation, the resulting classification accuracy (RARE) is much worse than our one-stage strategy (GMLE, PMLE and SPMLE). This is not surprising since the useful information contained in the major class was not effectively used in the second stage. In contrast, all the information from both major and rare classes is comprehensively used by the one-stage strategies.\n\n### Table A.1: Prediction results for the TTS dataset.\n|  | GMLE | PMLE | SPMLE | RARE |\n| --- | --- | --- | --- | --- |\n| ACC | 0.836 | 0.835 | 0.824 | 0.745 |\n| AUC | 0.997 | 0.999 | 0.999 | 0.969 |\n\n2. **Theoretical Properties.**\n    - **Assumption.** The theoretical assumption $\\alpha_N \\to -\\infty$ and $\\alpha_N+\\log N \\to \\infty$ are used for allowing rigorous asymptotic analysis. This leads to the block diagonal structure of the asymptotic covariance for MLE, and further leads to the novel PMLE method. Without this specific condition, we can never obtain those theoretical findings and then be inspired to develop PMLE method. Moreover, those conditions seem to be very standard in the literature. See, for example, Equation (2) in Wang (2020, ICML) and Section 2 in Wang et al. (2021, NeurIPS).\n    - **Convergence Rate.** The convergence rate reflects that sufficient amount of samples must be provided for both major and every rare class. Otherwise, no consistent parameter estimates can be obtained. The much slower convergence rate of $1/\\sqrt{Ne^{\\alpha_N}}$ is as expected. In fact, this is a phenomenon having been well documented in the literature. See, for example, Wang (2020, ICML), Song and Zou (2024, TIT), and Wang et al. (2021, NeurIPS). We now have made this point clear in the revision.\n\n3. **Empirical Comparison with Baseline Methods.** We have included the following methods for comparison on the TTS dataset: the focal loss (FL) of Lin et al. (2017), the class-balanced loss (CBL) of Cui et al. (2019), the cost sensitive loss (CSL) and random downsampling (RDS) of Fernández et al. (2018). All methods are optimized according to the suggestions of the original papers. The results are summarized below in Table A.2. We are happy to report that our method outperforms all competitors.\n\n### Table A.2: Prediction results for the TTS dataset.\n|  | GMLE | PMLE | SPMLE | FL | CBL | CSL | RDS |\n| --- | --- | --- | --- | --- | --- | --- | --- |\n| ACC | 0.836 | 0.835 | 0.824 | 0.794 | 0.789 | 0.747 | 0.763 |\n| AUC | 0.997 | 0.999 | 0.999 | 0.998 | 0.998 | 0.991 | 0.996 |\n\n4. **Minor Issues.** For the other issues, we have also addressed them carefully.\n    - “NR algorithm” has been referred to as the Newton-Raphson algorithm in the revision.\n    - The code has been made publicly available at [https://anonymous.4open.science/r/Anony-63CC](https://anonymous.4open.science/r/Anony-63CC).\n\n**Additional References**\n1. Cui, Y., Jia, M., Lin, T. Y., Song, Y., & Belongie, S., 2019, Class-balanced loss based on effective number of samples. CVPR.\n2. Lin, T. Y., Goyal, P., Girshick, R., He, K., & Dollár, P., 2017, Focal loss for dense object detection. ICCV.\n3. Song, Y., & Zou, H., 2024, Minimax optimal rates with heavily imbalanced binary data. IEEE TIT.\n4. Fernández, A., García, S., Galar, M., Prati, R. C., Krawczyk, B., & Herrera, F, 2018, Learning from imbalanced data sets. Springer.", "claims_and_evidence": "### Interesting theoretical results with limited motivation.\nThe paper presents intriguing theoretical results that decompose a multi-class classification problem with imbalanced classes into a set of pairwise binary problems. However, the overall motivation and practical impact remain questionable. The introduction discusses customer purchase behavior and related contexts, which might lead readers to expect approaches involving gaze tracking or attention mechanisms integrated into an object detection pipeline. Instead, the paper ultimately focuses on logistic regression applied to sub-image classification. For instance, one might naturally consider a two-stage approach—first detecting car plates and then classifying them—to mitigate the imbalance issue, an alternative not discussed by the authors.\n\n### Strong assumptions with limited practical relevance.\nThe theoretical guarantees rely on specific conditions such as $\\alpha_N \\to -\\infty$ and $a_N + \\log N \\to \\infty$. These conditions ensure that while the probability of a rare event converges to zero, the absolute number of rare events still diverges, allowing for asymptotic analysis. In practice, however, these assumptions may not hold. For example, in a dataset of car images, the probability that a car plate is visible might remain roughly constant regardless of $N$ (assuming each image reliably shows a car plate). Moreover, the convergence rate is effectively downgraded from $1/\\sqrt{N} \\to 1/\\sqrt{N e^{a_N}}, meaning that when the rare events are very infrequent (i.e., $e^{a_N}$ is very small), the effective sample size for estimation is substantially reduced, resulting in a much slower convergence. This raises concerns about the practical feasibility of the method even if the theoretical assumptions are met.\n\n### Limited experimental validation.\nWhile the paper supports its theoretical claims with simulation studies and a single real-world TikTok Screenshots dataset, the experimental evidence is limited. The evaluation compares only the authors’ own MLE-based variants (GMLE, PMLE, and SPMLE) without benchmarking against alternative methods—such as a detection-classification pipeline or other imbalance-handling techniques (e.g., cost-sensitive learning, upsampling, or downsampling) —that are commonly used in practice. This narrow scope of experiments makes it challenging to assess the broader impact and practical relevance of the proposed approach.\n\nOverall, although the paper’s theoretical contributions are solid, the motivation, practical relevance, and experimental validation leave several claims insufficiently supported by convincing evidence.", "methods_and_evaluation_criteria": "I incorporated methodological concerns into the above “Claims and Evidence” section.", "theoretical_claims": "I have reviewed the high-level theoretical claims but I did not perform a line-by-line verification of the detailed proofs in the main text and Appendix. Consequently, while the arguments appear plausible, there remains a possibility that oversights exist.", "experimental_designs_or_analyses": "I incorporated experimental concerns into the above “Claims and Evidence” section.", "relation_to_broader_scientific_literature": "Their theoretical findings, notably the asymptotically block-diagonal covariance structure and the derivation of a convergence rate, provide rigorous insights into the behavior of maximum likelihood estimators under extreme imbalance. While the focus is on logistic regression, these insights have the potential to inform future research on more complex models, advancing our understanding of algorithm design in extreme imbalance scenarios.", "essential_references_not_discussed": "The paper would benefit from a broader discussion of the imbalanced classification literature. For example, recent advances in deep learning for imbalanced data, such as focal loss (Lin et al., ICCV 2017) and class-balanced loss based on the effective number of samples (Cui et al., CVPR 2019), have shown promising results in mitigating imbalance issues, especially in object detection tasks. Discussing these methods would help situate the paper’s contributions within the broader context of imbalanced classification and highlight potential avenues for extending the theoretical results to more complex models.", "other_strengths_and_weaknesses": "### Other strengths to note:\nBuilding on their theoretical insights, the authors introduce the pairwise maximum likelihood estimator PMLE and its subsample-based variant, SPMLE. SPMLE keeps the same convergence rate as PMLE, efficiently reduce computational burdens without sacrificing benefits.\n\n### Minor weaknesses:\n- The term “NR algorithm” is undefined. I assume it refers to the Newton-Raphson algorithm, but a clear definition or brief explanation would improve clarity.\n- To ensure reproducibility, it would be beneficial if the authors made the code available.", "other_comments_or_suggestions": "The paper was an enjoyable read. Please note that my comments represent my initial impressions and may include misunderstandings. I welcome further discussion on these points and am open to revising my score once my questions and concerns are adequately addressed.", "questions_for_authors": "I have incorporated questions into the above sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper combines theoretical investigations and algorithmic results inspired by real-world problems related to multi-class classification. Reviewers appreciated the novelty and efficiency of the proposed methods, specifically designed to solve multi-class classification tasks in case of strong class imbalance. The theoretical analysis of the problem is based on the study of the statistical properties of the MLE and requires some assumptions that raised some concerns about the practical relevance of the results; nevertheless, the effectiveness of the proposed strategy has been appreciated by all referees and therefore I will therefore recommend *Accept*.
Decision: Accept (poster)