Attentional-Biased Stochastic Gradient Descent
Authors: Qi Qi
Yi Xu
Wotao Yin
Rong Jin
Tianbao Yang
Venue: Accepted by TMLR ()

Abstract: In this paper, we present a simple yet effective provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. The individual-level weight of a sampled data is systematically proportional to the exponential of a scaled loss value of the data, where the scaling factor is interpreted as the regularization parameter in the framework of distributionally robust optimization (DRO). Depending on whether the scaling factor is positive or negative, ABSGD is guaranteed to converge to a stationary point of an information-regularized min-max or min-min  DRO problem, respectively. Compared with existing class-level weighting schemes, our method can capture the diversity between individual examples within each class. Compared with existing individual-level weighting methods using meta-learning that require three backward propagations for computing mini-batch stochastic gradients, our method is more efficient with only one backward propagation at each iteration as in standard deep learning methods.  ABSGD is flexible enough to combine with other robust losses without any additional cost. Our empirical studies on several benchmark datasets demonstrate the effectiveness of the proposed method.

Published in Transactions on Machine Learning Research (05/2023)
Attentional-Biased Stochastic Gradient Descent
Qi Qi', Yi Xu², Wotao Yin?, Rong Jin Tianbao Yang
qi gi@uiiowa.ede edu, statay@gmail. com, wotao. wotao.yin Galibabba cetdlbabb--iccccm. inc.com, rouginomailggmmil.com com, tiandao- sranbao-aangttam...om edu.cn Deportment of Computer Science, The University of Iowa
Alábaba Group
Meta Inc
Department of Computer Science and Engineering, Teaas A&M University * *corresponding author
Reviewed on OpenReview: https: // wpwp://veeeee..w...mmmmo net/ nor/forum? id- BOWYWUVA2r
Abstract
In this paper, we present simple yet effective provable method (named ABSGD) for ad- dressing the data imbalance label noise problem in deep learning. Our method is simple modification to momentum SGD where we assign an individual importance weight to cach sample in the mini-batch. The individual-eveel weight of sampled data is systematically proportional to the exponential of a scaled loss value of the data, where the scaling factor is interpreted as the regularization parameter in the framework of distributionally robust op- timization (DRO). Depending on whether the scaling factor is positive or negative, ABSGD is guaranteed to converge to a stationary point of infformationnregulaiiieee min-max or min-min DRO problem, respectively. Compared with existing class-level weighting schemes, our method can capture the diversity between individual examples within each class. Com- pared with existing individual-level weighting methods using meta-learning that require three backward propagations for computing mini-batch stochastic gradients, our method is more efficient with only one backward propagation at each iteration as standard deep learning methods. ABSGD is flexible enough to combine with other robust losses without any additional cost. Our empirical studies on several benchmark datasets demonstrate the effectiveness of the proposed method.
1
Introduction
Deep Learning (DI.) has emerged as the most popular machine learning technique in recent years. It. has brought transformative impact in industries and quantum leaps in the quality of wide range of everyday
technologies including face recognition (Schroff et al. 2015 Taigman et al. 2014 Parkhi et al. 2015 Wen
et al.
2
Liu et al.] 2019 Qi & Ardeshir! 2023). speech recognition (Graves et al.] 2013 Chung et al.
2014
Kim 2014 Graves 2013 Ravanelli et al. 2018 and machine translation (Cho et al. 2014 Bahdanau
et al.
2014
Sutskever et al. 2014 Luong et al., 2015 Vaswani et al. 2018). Most of these systems are
built based on learning a deep neural network (DNN) model from a huge amount of data. However, it
has been observed that these deep learning systems could fail in some cases caused by undesirable data distribution, such data imbalance (Johnson Khoshgoftaar 2019 Lin et al.] 2017 Chan al. 2019:
Fernández et al.) 2018 Huang et al.] 2019) and noisy labels in the dataset (FAN et al. Herzig et al. 2013
Kim et al. 2011 To be more specific, for example, Apple's FacelD (a face recognition system) is much less accurate for recognizing a child than an adult (Bud. 2018), and an autonomous driving car might fail at night under the same road condition (Wakabayashi] 2018). The key factors that cause these problems are (i) the training data sets collected from the real-world are usually follows a highly skewed distribution (e.g., the number of facial images of children are much less than that of adults), and/or contain noisily labelled samples due to the inaccurate annotation process [Zhang et al. 2016);; (ii) current deep learning systems are not robust enough to overcome negative influence incurred by the real-world imperfect data as most existing

---

Published in Transactions on Machine Learning Research (05/2023)
Initial
SGD
ABSGD
Robust Weights
ABSED
SGD
C4-
14
@
12
C2-
31
24
05
30
Sampp Index
(a)
(b)
(c)
Figure 1: (a): A synthetic data for imbalanced binary classification (green vs purple) with random linear decision boundary (black line). (b), (c): Learned linear models optimized by SGD and ABSGD with logistic loss for 100 iterations, respectively. (d): The averaged weights of circled samples in the training process of SGD and ABSGD.
deep learning techniques the literature are crafted and evaluated on well-designed benchmark datasets with balanced distributions among different classes (e.g., ImageNct data for image classification).
Extensive studies have shown that standard empirical risk minimization (ERM) is not sufficient to address the above deficiencies in training on large-scale datasets. Specifically, ERM can lead to biased models toward the majority class and perform poorly in predicting minority class for data imbalance problems (He & Garcia 2009 Sun et al. 2007 Chawla el al. 2002 Batista et al. 2004). Similarly, label noise can result in incorrect empirical risks during training (Natarajan et al. 2013 Wang et al.) 2018 Zhang et al.) 2021 To overcome this, recent studies have been explored to learn to improve model robustness to overcome the above deficiencies. Those studies can be divided into two directions, data manipulation, and robust learning,
Popular data manipulation methods include under under/over-san /over-samlling based approaches (Chawla et al.
2002:
Han et al. 2005 Chawla 2009) for data imbalance problem and label correction methods (Xiao et al. 2015
Vahdat 2017 Lee et al. 2018 Veit et al. 2017) for label noise problem, etc. Existing studics in these methods are not very successful for deep learning with big data. For example, several studies have found
that over-sampling yields better performance than using under-sampling (Johnson & Khoshgoftaar 2019
But over-sampling will add more examples to the training data, which will lead to increased training time.
While the label correction methods (Xiao et al., [2155] Vahdat 2017: Lee et al. 2018 Veit et al. 2017) usually require extra clean data that are expensive to collect.
Robust learning methods include robust weighting and robust loss, where robust weighting assigns weights to different losses of individual data which are either hand-crafted or learned, and robust loss refers to new loss functions that are heuristic-driven or theoretically inspired for addressing data imbalance or label noise issucs. The cxisting robust weighting methods either require significant tuning or suffer from significant computational burden. In this paper, we propose a simple yet systematic attentional-biase gradient descent (ABSGD) method for addressing the class imbalance or the label noise problem in a unified framework, which falls in the category of robust weighting methods. ABSGD is a simple modification of the popular momentum SGD method for deep learning by injecting individual-level importance weights to stochastic gradients in the mini-batch. These importance weights allow our method either to focus on examples from the minority classes for the data imbalance problem or the clean samples for the label noise problem. This idea is illustrated in Figure | on a toy imbalanced dataset by comparing it with the standard momentum SGD hot for deep learning. Unlike existing meta-learning methods for learning individual- level weights, our individual-level weights are self-adaptive that are computed basod on the loss value of each individual data. In particular, the weight for each example is proportional to exponential of a scaled loss value that example. The weighting scheme is grounded in the theoretically justifiable distributionally robust optimization (DRO) framework.
stochastic
Specifically, our method can be considered as a stochastic momentum method for solving an information- regularized distributionally robust optimization (IR-DRO) problem defined on all possible data ZZuu et al., 2019). From this perspective, our method has several unique features. (i) The weights for all examples the mini-batch have a proper normalization term to ensure the method optimizes the IR-DRO problem, which is updated online. We prove theorem to show that our method converges to stationary solution
2

---

Published in Transactions on Machine Learning Research (05/2023)
of the non-convex IR-DRO problem (with certain convergence rate). (ii) The scaling factor before the loss value in the exponential function is interpreted as the regularization parameter in the DRO framework. In addition, our method has two benefits: (i) it is applicable in online learning, where the data is received soquentially; (ii) it is loss independent, and can be combined with all existing loss functions crafted for lackling data imbalance and label noise. Finally, we summarize our contributions below:
We propose a simple robust stochastic gradient descent method with momentum and self-adaptive importance weighting to tackle deep learning tasks with imbalanced data or label noise, which is named as ABSGD. ABSGD can be generalized broader family of AB methods that employ other updating methods, e.g., AB-ADAM that uses the ADAM scheme to update the model parameter.
We prove that ABSGD finds a stationary solution of a non-convex IR-DRO problem for learning a deep neural network, and establish its convergence rate.
We compare ABSGD with a varicty of existing techniques for addressing the data imbalance and label noise problems, including crafted loss functions, class-balancing weighting methods, individual-level weighting meta-learning methods, and demonstrate superb performance of ABSGD.
2
Related Work
Class-level Weighting. The idea of class-level weighting is introduce weights to examples at the class level to balance the contributions from different classes. This idea is rooted in cost-sensitive classification in
machine learning (Zou & Liu 2005 Sun et al. 2007 Scott, 2011
Parambath el al. 2014 Narasimhan et al.
2015 Elkan 2001 Busa-Fekete et al. 2015
Traditional cost-sensitive methods typically tune the class-level weights. Recently, a popular approach is to set the class-wise weights to be proportional
Yan et al.
2017).
to the inverse of class sizes (Huang et al. 2016 Yin et al. 2018). Cui et al. (2019) proposed an improved class-level weighting scheme according to inverse of the "effective number" of examples per class. Tt also notable that pver/unde-sant samdl-- mothods have the same effect of introducing the class-level weighting to the training alg.rithm. We can see that these class-level weighting schemes usually require certain knowledge about the size (distribution) of each class, which makes them not suitable to online learning where the size of each class is not known beforchand. These methods also neglect the differences between different examples from the same class (cf. Figure| D].
Individdual-weightingg by Meta- Learning. The individual-level weights learning methods typically use meta-learning to learn the individual-level weights along with updating the model paramcters (Jamal et al., 2020 Ren et al. 2018). The idea is to learn individual-level weights by solving two-level optimization problem. In particular,
Σ 2(w())::)) where w(0) arg min Z:EC
1 Σ 0,L(w;2;)
min |C|
D
Z,ED
where D denotes the training dataset, C denotes balanced validation dataset, denotes the model pa- rameter, denotes a data, I(w;2) denotes the loss value of model w on data 2, and 0 = (0I...., 0pp) denotes the weights on the training examples. Ren et al. (2018) directly optimized the individual weights in the framework of meta-learning with a hcuristic trick by normalizing the weights of all examples in a training batch so that they sum up to one. Jamal et al. (2020) considered the problem from the perspective of domain adaptation and decomposed the individual weight into sum of a non-lcarnable class-lcvel weight and a learnable individual-level weight. One issue of these meta-learning methods is that they require three propagataass at each iteration, which is computationally more expensive than our method that is about the same cost of standard SGD for DL.
Crafted Individual Loss Functions. Some crafted individual loss functions have been proposed for tackling data imbalance or label noise. A popular loss function is known as the focal loss (Lin et al., 2017). which is modification of the standard cross-entropy loss. Specifically, is defined as -(1 - pt)"' (p:) where y > 0 is a tuning parameter, P: is the estimated probability for the ground-trute truch class. The focal loss has been observed to be effective for dense object detection and is also widely used for classification with
3

---

Published in Transactions on Machine Learning Research (05/2023)
imbalanced data due to its simplicity (Goyal & Kaiming 2018 However, the focal loss lacks theoretical foundation. To complement this, (Cao et al. 2019) proposed theoreticalll-ppriciihhe label-distribution- aware margin loss, which injects uneven margins into the cross-entropy loss, where the margin for each class is proportional to inverse of cach class size to the power of 2/5. For tackling label noise, symmetric losses have been proposed, e-g-, symmetric cross entropy loss (SCE) (Wang et al. 2019) and generalized cross entropy loss (TCE) (Zhang & Sabuncu, 2018). Our method is loss independent and hence can be combined with these existing crafted individual loss functions.
Optimization of DRO. DRO is useful technique for domain adaptation, which has been shown both thcoretically and empirically promising for learning with imbalanced data (Shalv--hwwarzz & Wexler 2016 Namkoong & Duchi 2017 Qi et al. 2019 2022). However, most existing optimization algorithms for DRO are not practical for deep learning. which dims the usefulness of DRO. In the literature, DRO is formulated
as (Rahimian & Mchrotra
2019
Namkoong & Duchi 2017 :
n
min max p. p,L(w;z)) h(p, 1/n) + r((), weR" PEAn i=1
(1)
where A, = (p RR E. 2 0} denotes an n-dimensional simplex, h(p, 1/n) is a divergence measure or constraint between and uniform probabilities 1/n, r(w) is a standard regularizer on w. We can see DRO aims to minimize the worst-case loss over all the underlying distribution p in an uncertainty set specified by h(p 1/n). Many primal-dual optimization algorithms have been designed for solving the above problem for DL (Rafique et al. 2018 Yan et al. 2020). However, the dual variable p in the above min-max form is an n-dimensional variable restricted to a simplex, which makes existing primal-dual opti- mization algorithms computationally expensive and not applicable for the online setting where the data is coming sequentially. Our method can be considered as a solution to addressing these issues by considering a specific information-oriente regularizer h(, 1/n) = EE, Pi log(np:) that is the KL divergence between p and uniform probabilitics 1/n,, which allows us to transform the min-max formulation into an equivalent minimization formulation with compositional objective. From this perspective, our method resembles re- cently proposed dual-free algorithm RECOVER (Qi ct al., 2020). However, RECOVER requires computing stochastic gradients at two different points in each iteration, which causes their GPU cost to double ours. In addition, RECOVER. is a variance-reduction method, which might have poor generalization performance.
Several recent studies also proposed stochastic algorithms for DRO (Qi et al. 2022 Duchi & Namkoong,
2021 Levy ct al., 2020 Jin et al. 2021 Levy et al. 2020 Amid et al.] 2019), which are arguably more complicated than our methods.
It was brought to our attention that several papers have developed algorithms based on certain formulations of DRO for tackling noisy data and/or imbalanced data. Li et al. (2021) investigated the effectiveness of optimizing the KL, regularized DRO objective in dealing with class imbalance, which is similar to our paper. The difference from this work is that our algorithm is simpler which only uses one mini-batch of samples per-iteration. In contrast, their algorithm requires two independent mini-batches for updating the model parameter. Majidi et al. (2021) proposed an Exponentiated Gradient (EG) reweighting method to optimize the min-min DRO formulation (4) to handle the label noise problem. Unlike that in our algorithm, the normalization term for computing the weights in the mini-batch is simply calculated from the mini-batch, which does not provide any convergence guarantee for solving the min-min DRO formulation. Kumar & Amid (2021) proposed Constrained Instance Weighting (CIW) method that is similar to EG to optimize f-divergence min-min DRO, however, no thcoretical guarantees have been provided. Later on, Bar et al. 22021] proposed a different algorithm for solving a min-min DRO formulation such that the weights in a constrained simplex {Σ> Pi = 1,0 < p. < <//n). Their algorithm requires periodic projection onto the constrained simplex, which takes O(n?) complexity when μ < n and O(n) complexity when l = n, where n is the size of the training set. They established a convergence rate of / BT where denotes the batch size, and T denote, which is worse than the rate of our proposed algorithm by a factor of n/B.
n.
4

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm ABSGD (A 8, Wo.
for L 0.... T do Sample/Receive mini-batch of B samples (21, 20)
Compute ((w, B Di=
Compute 81+1 (1 (1-7)8t + (ww)
5: Compute P; = exp( ((())))))
for -= 1..... B
Update Wi+1 by Equation
7: end for
8: Return Wr
3
Attentional-biasel SGD with Momentum (ABSGD)
In this section, we present the proposed method ABSGD and its analysis. We first describe the algorithm and then connect it lo the DRO framework. Then present the convergence result of our method for solving IR- DRO. Throughout this paper, we let z = (x, y) denote a random sample that includes an imput x E Rd and the class label y E {l,..., K}, w E Ø denote the weight of the underlying DNN to be learned. Let f(x) E R* be the prediction score of the DNN on data x, and E(f:y) denote a loss function. For simplicity, we let L(w; z) (f(x)::)) A standard loss function is the cross-entropy loss where ((f; y) log Σ exp(fe (x))
(x)(
We emphasize that our method is loss independent, and can be applied with any loss functions {(f: (ff:0] y).
Specifically, ABSGD can employ the class-level weighted loss functions such as the class-balanced loss Cui
et al. 2019 crafted individual loss functions such as label-distribution aware margin loss (Cao et al., 2019
3.1 Algorithm
The proposed algorithm ABSGD is presented in Algorithm ! The key steps are described in Step 2 to Step 6, and the key updating step for We+1 given by
B ABSGD: W++1 = - 17( Σ
(.V((w + Vr(w:)) + 3(3,: w.-1)
(2)
t=1
where r(w) x 1/2 denotes a standard & norm regularization (i.c., for contributing weight decay in the update). The above update a simple modification of the standard momentum method (Polyak) 1964).
where the last term 8(w; - 1 is momentum term. The modification lies the introduced weight pt for each data 2, in the mini-batch The individual weight Pa is computed in Step 7 and is proportional to exp(L((,; where À is scaling parameter that À (R)00. Intuitively, can that sample with large loss value tends to get higher weight with À > 0. It makes sense for learning with imbalanced data since the model tends to fit the data from the majority class while making the loss value larger for the minority class. Hence, the data from the minority class tends to get a larger weight p. This phenomenon is demonstrated on toy dataset in Figure [ Similarly, if X O, large value losses have smaller weights. As the noisy samples incurs larger losses than the clean samples, pi would further emphasize more on the clean samples with larger weights, hence À
preferred in the presence of label noise.
It is notable that the weight p. is properly normalized by dividing quantity s:41 that is updated online. In particular, 8t+1 maintains a moving average of the exponential of the scaled loss value on the sampled data (Step 4). It is notable that the normalization does not make the sum of p. in the mini-batch equal to 1. We emphasize that this normalization essential in twofold: (i) it stabilizes the update without causing significant numerical issue; (ii) it ensures the algorithm converges to a meaningful solution as presented in the next subsection.
3.2 Connection with Min-man or Min-min Robust Optimization
In the next subsection, we will show that ABSGD converges to a stationary solution of two robust opti- mization problems depending whether À is positive negative. In particular, given training samples
5

---

Published in Transactions on Machine Learning Research (05/2023)
[Zi...., (n)) we consider the following min-max and min-min robust optimization:
min max WER A
p LLL(W:)))
T E Ps (n(p;)) +r(w).
(3)
1=1
p! (w) (w)
min min WER" PEA,
P.L (w: 2.) + Σ pi In(np,) +r(w)
(4)
(w)
where and A, is a simplex. In the Appendix, we show that F.
(w() (w) r Flg : Σ, exp(L(w::))))))) +r()). Similar min-max and min-min formulations have been considered in the literature under the framework of tilting log- likeliihodd (Choi et al.) 2000 Recently, there is some renaissance of solving the min-max and min-min formulation in machine learning. For example, the min-max formulation 33 is also closely related to distributionally robust optimization (Namkoong & Duchi, 2017) with a difference that a regularization is imposed on p instead of a constraint function. The min-min formulation has been considered
and p.P (w) - log + exp(([(((,
(Mjjidi et al. 2021) for tackling noisy data. Recently, the titled risk functions F (w) and FT(2) (w) have been also studied in (Li et al. 2021). We describe the difference between ABSGD and the algorithm in Li et al. 2021 in detail in section 3.5
By considering the explicit 7 >; p: log(np:) regularizer in the two DRO formulations, our algorithm is appli- cable to solving the min-max objective (3) by setting À = T and the min-min objective (4 by setting À = -T. When r = +00, Pt = 1/n according to the close form solution derived in Equ (5). Then above DRO objectives, Equ 33) and (4), become the standard empirical risk minimization problem: min 1
n Σ When 5 = 0, then p has only one component equal to 1 that corresponds to the data with largest loss value for Equ (3) and the data with smallest loss value for Eqn 4 Hence, when + O, DRO objective (3) becomes the maximal loss minimization: min max; L (w; 2,) + +(w). And when T + O, DRO objec- live 4 becomes the minimal loss minimization: min min, L(w;2) + r(w). The above maximal loss minimization has been studied for learning with imbalanced data shown thcorctically to yicld better generalization performance than empirical risk minimization for imbal- anced data. However, the maximal loss minimization is sensitive to outliers. Hence, by varying the value of can enjoy the balanced robustness between the imbalanced data and outliers.
Shwale-Shwartz & Wexler 2016). was
3.3 Optimization Analysis
It is nice that the DRO formulation is robust to imbalanced data (Fqn (3) and noisy data (Fqn (4) How- ever, the min-max min formulation of DRO is not friendly to the design of efficient optimization algorithms, especially given the constraint p E A,, To this end, we transform the min-max min formulation (3) and (4) into an equivalent minimization formulation following (Qi et al. 2020). In particular, we first compute the optimal solution of dual variable p" for the inner maximization, minimization problem given w. By taking
the first-derivation equation and (4 in terms of p and setting it to zero, i.e. FpF(w, p) = O, we have
p":
p exp( L(W.R.)
i= 1.....,,
Σ exp( (w:z.)) A
where À 7 for equation and X - for equation equivalent minimization formulation:
44. By substituting p back, we obtain the following
) + +r(ww.
L L(w; (w:zz))
min Fx(w) Alog weRd
exp
(6)
In online learning setting, can further generalize the above formulation
min Fx(w) =Alog (E& exp(L(w:z)/A)) +(w).
(7)
WERd

---

Published in Transactions on Machine Learning Research (05/2023)
Given the above minimization formulations, our method ABSGD can be considered as a stochastic algorithm for optimizing (6] in offline learning or optimizing 7 in online learning. Our method is rooted in stochastic optimization for compositional optimization that has been studied in the literature (Wang et al.) 2017] Ghadimi et al. 2020; Chen et al., 2020: Qi ct al. 2020 Intuitively, we can understand our weighting scheme p as following. In oflline learning with big data size where n is huge, it is impossible to calculate the p as in ( at every iteration due computation and memory limits. As a result, we need to approximate p in systematic way.
In our method, we use moving average estimate S(+1 to approximate the denominator in p., i.e. 1 Σ exp( L(wxx)) ), and use to compute a scaled weight of data in the mini-batch by Step 5, i.c.,
exp( L(WE:R))
P;
i (1, (1....B.
(8)
88+1
More rigorously, our method ABSGD is stochastic momentum method for solving compositional problem in the form [(g(w))+r(ww To this end, we write the objective in 7 as ((((w))+r(W) where f(g) = À log(g) and g(w)= = Ex (exp(L(w;
The difficulty of stochastic optimization for the compositional function f(((w)) lies on computing an approximate gradient at W.. By the chain rule, its gradient is given by
g(w.): we use a moving average to estimate g(w)) inspired by (Wang et al. 2017). which is updated in Step 4 of Algorithm i.c.,
v ([(((w))) Vg(w)) = g(w)) Vg(w.). To approximate Vg(((w))) = A
8141 = (1 (1- 7)s, + 75W,,,, where g(w,)= 1
Σ
B
expl
L(we, zi) ) {zi} are random samples.
B
And Vg(W,) can be estimated by mini-batch stochastic gradient, i.e.,
Vo(w.)= = exp(L(w;;))/AA) VL(w;;2) X
1 B B
Σ
Hence, the true gradient V
is able to be approximated by
Vg(w.) = B
1
Σ
81+1
1=1 8111
which is exactly the approximate gradient used in the update of Wi+1 as in equation (2) intuition about the benefit of using 8t41 for normalization weights. Let us consider a simple case such that only one data is sampled for updating. For the imbalanced data setting, if the sampled data denoted by 2, at the i-th iteration is from minority group and hence has a large loss. We would like to penalize more on such example. The estimator $t+1 (1-7)ss+ y 2 ()) is likely to be smaller than exp(L(W,,, 2/)A) due to 7 < 1. As result, normalization using 8++1 will give a larger weight. to the sampled minority data compared with using the mini-batch normalization, i.e., exp(E(w,.,)/A
Let us provide an
exp(L(w,,e1/A) exp(I.(w,P.1/A) Similarly, in the noisy label setting, if the sampled data is a noisy sample and hence has a large loss, then exp(L(w,, 2)2 would be small due to that À is set to be nogative in this case. As a result $111 = (1-7)s + exp(L(w,, //A) is likely to be larger than exp(L(w, 2)) Then normalization using 8t+1 will give smaller weight to the sampled noisy data compared with using the mini-batch normalization, i.c., exp(L(er,
A1t1
2xp(L(w..e)/A) <exp([(w. (W)))))) We can see that in both cases using $141 for normalization intuitively makes sense. In Figure 4, we will empirically demonstrate the benefit of our algorithm design with variant that uses 7 = which is just using the mini-batch normalization.
8:11
Finally, we comment on the final update of model parameters. Instead of directly using this gradient estimator to update the model parameter following (Wang et al.) 2017), we employ a momentum update. The reason is that the algorithm in (Wang et al.) (2017) has larger sample complexity, which is O(1/e) for finding an e-stationary point of the objective function (cf. Section 3.5 By using momentum update

---

Published in Transactions on Machine Learning Research (05/2023)
in able to establish optimal sample complexity. It is notable that the momentum update
be seen a simplification of the NASA method proposed in (Ghadimi et al. 2020 which was designed to address the constrained compositional optimization.
3.4 Other AB methods
In light of the discussion about the connection between ABSGD and optimization of IR-DRO, we can generalize ABSGD to employ other updating schemes, e.g., AdaGrad (Duchi et al. 2011), RMSProp (Ruder, 2016 Guo et al. 2021), Adam (Kingma & Ba 2015). Below, we present the ABAdam method. The key idea is to replace the standard mini-batch gradient estimator in Adam by the weighted mini-batch gradient estimator. The key steps of ABAdam are presented below.
G(wi) Σ i=1
Pi (VV((;
ABAdam:
Vi+1 B1 Vt + (1- ()))(w))
(9)
U+41 = B2u + (1 (1- (G
W++1 = W. n Vi+1 + Vr(w.))
Vu++1 + Go
where Go is a constant to increase stability, 81,82 are the constant hyperparameters that are usually set as 0.9 and 0.999, respectively. ABAdam could potentially benefit the applications that Adam has better generalization performance than the SGD (Nadkarni et al.) 2011 Kang et al. 2020). In the appendix, we provide a theoretical analysis for ABAdam for optimizing IR-DROO, and leave the experimental exploration for the future.
3.5 Convergence Analysis
In this subsection, we provide convergence result of ABSGD for solving the min-max or the min-min objective under some standard assumptions in non-convex optimization. For presentation simplicity, use the notations g(w) Ez (e))(((w;z)) /)A] and g(w;z) exp( (w;;))/)/)) We first state standard assumption (Qi et al. 2020: Wang et al. 2017) and then present our main theorem.
Assumption 1. Let Vg, La are constaut sculars,
For a fized X, there exists V, > 0 such that E Exllg((;;)) (e]l(((w)))((()l1+ Bgl Vg(w)) Vg and L(w;z) for any z is an Lu-smooth function, i.e., [L(w:z) vL(w'z)) - L w/l kw, w'
min ((")(w) (w) - A F!!2 (w1) F(P((w1) min F. F(?((w) - For given T, there exists Do such that F(" min AF.
Theorem
Assume assumption holds and there erists Co Cr such that exp(L(weizz)) S (o.,,V)(w,, S C1, for all w. and any 2; Then, S 3 11 = 2/13-11012 3 1
For x = = 0, ABSGD ensures that E
s e² after T = 0(1/et) iterations, and for VF (w)
A = ABSGD ensures that E
T
Σ
2 |
2 after T 0(1/e)) ilerations, where (w:))l
exhibit the constant in the big O in Appendiz.
Remark: Before ending this section, we present some remarks. First, we notice that in concurrent work [i et al. 2021), the authors proposed similar algorithm to ABSGD without the momentum term, i.., 7 = However, they only prove the convergence for the algorithm with independent mini- batches for I(w; z) and VL(w;z)). In our experiments, we show that the momentum term is important for spooding up the convergence. In another concurrent work (Mjjidi et al. 2021) the authors proposed an algorithm for solving the min-min objective
4 The difference is that in their algorithm the normalization for computing

---

Published in Transactions on Machine Learning Research (05/2023)
the weight is computed only from the current mini-batch while that in ABSGD depends on all historical data. In addition, (Majidi et al. 2021) provides no convergence analysis for solving the min-min robust optimization problem.
3.6 Two-stage Training Strategy for A
Since À can be interpreted as the regularization parameter in IR-DRO, we can understand its impact on the learning of model. With a larger [A|, the IR-DRO is getting closer to ERM and ABSGD is getting close to the standard momentum SGD method without robust weighting. When | = co, the update becomes exactly the same as the standard momentun SGD method. When |Δ] becomes smaller, the update will focus more on data with larger loss values (e.g., from the minority class). This uneven weighting is helpful to learn a robust classifier. However, it might harm the learning of feature extraction layers. This phenomenon has been also observed in previous works (Cao et al. 2019 Kang et al. 2019).
To address this issue, we employ a two-stage training method following the existing literature (Kang et al. 2019), where in the first stage we employ momentum SGD to learn a basis network, and in the second stage we employ ABSGD to learn the classifier and finetune the feature layers. As momentum SGD is a special case of ABSGD with |A] = oc, the two-stage method is equivalent to running ABSGD with ||] = oo first and then restarting it with a decayed [^] < oo. In the ablation study, we will show that damping |^] is critical for balancing the learning of feature extraction layers and classifier layers. Finally, it is notable that in the second stage, we can fix some lower layers and only fine-tune upper layers using ABSGD,
4 Experimental Results on Data Imbalance Problem
We conduct experiments on multiple imbalanced benchmark datasets, including CIFAR-10 (LT), CIFAR-10 (ST), CIFAR-100 (LT), CIFAR-100 (ST), ImagetNet-LLT (Liu et al. 2019), Places-LT (Zhou et al. 2017). and Natuuclist2018 (iNatrualist 2018). and compare ABSGD with several state-of-tho-art (SOTA) methods,
including meta-learning (Jamal et al. 2020), class-balanced weighting (Cao et al. 2019), and two-stage decoupling methods (Kang et al. 2019). We use the ResNets (He et al. 2016) as the main backbone in our experiments. For fair comparison, ABSGD is implemented with the same hyperparameters such as momentum parameter, initial step size, weight decay and step size decaying strategy, as the baseline momentum SGD method. For ABSGD, the moving average parameter ? are tuned in [0.1 0.1 1] by default. Without additional mentions, we directly use the results of basclines from their original papers by default.
Datasets: The original CIFAR-10 and CIFAR-100 data contain 50,000 training images and 10,000 validation with 10 and 100 classos, respectively. We construct the imbalanced version of training set of CIFAR10, CIFAR100 following the two strategies: Long-Tailed (LT) imbalance (Cao el al. (019) and Step (ST) imbalance (Buda et al. 2018) with two different imbalance ratio p 10, 100, and keep the testing set unchanged. The imbalance ratio p is defined as the ratio between sample sizes of the most frequent and least frequent classes. The LT imbalance follows the exponentially decayed sample size between different categories. Tn ST imbalance, the number of examples are both equal within minority classes and majority classes but differs between the majority and minority classes. We denote the imbalanced versions of CIFAR1O, CIFAR100 as CIFARIO-LT/ST. CIFAR100-LT/ST according the imbalanced strategies. ImageNet-LT Liu et al. 2019) is a long-tailed subset of the original TmageNet-2012 by sampling a subset following the Pareto distribution with the power value 6. It has 115.8K images from 1000 categorics, which include 4980 for the head class and 5 images for the tail class. The Places-LT dataset was also created by sampling from Places- 2 (Zhou et al., 2017) using the same strategy ImageNet- LT. It contains 62.5K training images from 365 classes with an imbalance ratio p = 4980/5. iNaturalist 2018 is a real world datasot whose class-frequency follows a heavy-tail distribution (iNatrualist 2018). It contains 437K images from 8142 classes. The loig-tail and step imbalance label distribution of the datasets are shown in Figure 2
Libti-Disttibution Independent Losses We first compare the effectiveness of our ABSGD method with standard momentum SGD method for DL. In particular, we consider two loss functions, cross-entropy (CE) loss and focal loss. The baseline method is the momentum SGD optimizing these losses, denoted by
9

---

Published in Transactions on Machine Learning Research (05/2023)
Inaggetue..1
307 210
Long-tail tail label distributions of ImageNet-LT,, Places-LT, iNaturalist2018 and CIFAR100 with imbalance ratio p 100, and Step imbalance label distribution of CIFAR10 with imbalance ratio p p= 10.
Figure 2:
SGD (CE) and SGD (Focal). Our methods are denoted by ABSGD (CE) and ABSGD (Focal) that employ the two losses in our framework. This comparison is meaningful as in the online learning setting the prior knowledge of class- frequeccy is not known.
Label-distribution Dependent Losses Next, we compare ABSGD with baseline methods that use label- distribution dependent losses. In particular, we consider bass-balanced (CB) versions of three individual losses, including CE loss, focal loss, label-distribution--vee
margin (LDAM) loss (Cao et al. 2019). The class-balanced weighing strategy is from (Cui et al. 2019). which uses the effective number of samples to define the weight. As a result, there are three categories of CB losses, i.e., CB-CE, CB-Focal, CB-LDAM. uses
We use our method ABSGD with these different losses. In particular, ABSGD + OB-CE/Focal/LDD a combination class-level weighting and instance-level weighting, which is expected to have outstanding performance as it considers diversity between examples at both class level and individual level. For cach of these losses, we consider two baseline optimization methods. The first method is the standard momentum SGD method with practical useful trick (Cao et al.] 2019) that defers adding the class-level weighting after number of pre-training steps with no class-level weights to improve the performance. We denote the first method by SGD (XX), where XX denotes the loss function. The second method is the meta learning method (Jamal et al. 2020) that uses meta-learning on a separate validation data to learn individual weights and combines them with balss-bllanced weights. The meta learning method has been observed with SOTA results on these benchmark imbalanced datascts. We let META (XX) denote the second method. Our method is denoted by ABSGD (XX).
In the following, we compare ABSGD, SGD, and meta-learning methods by optimizing the same label- dependent and label-independent losses on inbalanced CIFAR datasets, and including more baselines on Lm,g Places-LT, and iNaturalistLLT.
Table 1: Top-1 testing accuracy (%), mean (std), of ResNet32 on imbalanced CIFAR-10 and CIFAR-100 trained with distldiittributinn independent losses. The results are reported over 3 independent runs.
Imbalance Type
long-tailed (LT)
step (ST)
Datasct
Imbalance Ratio
100
10
100
10
SGD (CE)
71.75 (+ 0.75)
87.64 (# 0.45)
63.12 (#: 0.63)
85.23 (# 0.41)
ABSGD (CE)
72.43 (+ 0.31)
87.93 (# 0.25)
66.24 (= 0.35)
85.84 (+ 0.27)
Cifar10
SGD (Focal)
70.86 (+: 0.68)
87.10 (#: 0.41)
63.31 (+: 0.61)
85.55 (#: 0.46)
ABSGD (Focal)
72.48 (+: 0.28)
87.26 (# 0.35)
65.03 (= 0.33)
85.67 (+ 0.30)
SGD (CE)
38.35 (+ 0.63)
56.91 (# 0.44)
39.23 (+ 0.58)
55.09 (# 0.35)
ABSGD (CE)
39.77 (+: 0.34)
57.44 (#: 0.25)
39.76 (+ 0.37)
55.15 (+ 0.29)
Cifar100
SGD (Focal)
39.05 (# 0.71)
56.89
(= 0.41)
39.32 (# 0.61)
54.45
(# 0.43)
ABSGD (Focal)
39.37 (+: 0.38)
57.08 (+ 0.29)
39.75 (= 0.39)
55.40
(+ 0.33)
4.1 Experimental Results on CIFAR Datasets
Setups Following the experimental setting in the literature, the initial learning rate is 0.1 and decays by a factor of 100 at the 160-th, 180-th epoch for both ABSGD and SGD in our experiments, respectively. The value of X in ABSGD tuned in [1 1: 10].
Results. We report the results with label independent losses in Table and with label dependent losses in Table 2 We can see that ABSGD consistently outperforms SGD with noticeable margin regardless
10

---

Published in Transactions on Machine Learning Research (05/2023)
Table 2: Top-1 testing accuracy (%) of ResNet32 on imbalanced CIFAR-10 and CIFAR-100 trained with label-
distribution dependent losses. The red numbers indicate the best in each category of class-weighted loss. The bold red numbers indicate the best each imbalanced setting. The original paper META does not include the results the ST imbalanced setting, hence their missing results are marked by
Datasets
Imbalanced CIFAR-10 10
Imbalanced CIFAR- 100
Imbalance Type
long-
step
long-tailed
step
Imbalance Ratio
100
10
100
10
100
10
100
10
Resampling (CE)
71.78
86.99
61.16
84.59
38.87
56.92
38.84
54.35
SGD (CB-CI)
Cui et al..
2019
72.37
86.77
61.84
83.80
38.70
57.56
21.31
53.39
META (CB-CE) Jamal et a..
2020
76.41
88.85
43.35
59.58
ABSGD CB-CE)
79.34
88.57
72.93
88.42
45.54
61.12
45.89
60.77
SGD (CB-Focal)
Cui et al.
2019
74.57
87.10
60.27
83.46
36.02
57.99
19.76
50.02
META (CB-Focal)
J Jamal cl al.
2020
78.90
88.37
44.70
59.59
ABSGD CB-Facal
79.53
88.76
76.33
85.90
44.11
59.14
45.41
59.75
SGD (LDAM) Cao et. al.
2019
73.35
86.69
66.58
85.00
39.60
56.91
39.58
56.27
SGD (CB-LDAM) Cao et al.
2019
77.03
88.12
76.92
87.81
42.04
58.71
45.36
59.46
META (CB-LDAM) Jamal et
2020
80.00
87.40
44.08
58.80
ABSGD (CB-LDAM)
80.45
88.27
78.33
88.40
44.71
59.21
45.65
58.74
of imbalance strategics and imbalance ratio p. In particular, we have more than 2% improvements on the CIFARIO-ST and CIFARI00-LT, respectively with p 100. For the label dependent losses, we have the following observations, comparing ABSGD with SGD, we can see that our method that incorporates the self-adaptive robust weighting scheme performs consistently better in all imbalanced settings. This verifies that the proposed self-adaptive weighting scheme is also effective even when applied on top of the class-level weighting strategy. It is notable that META requires a separate validation data and is more comput iomputaaiionally expensive than our method, Hence, our method is a strong choice even compared with the SOTA meta learning method, especially for highly imbalancod tasks. Also, the improvements of ABSGD with CB losses over ABSGD with label independent losses verify the importance of prior label information in addressing the data imbalance problem.
4.2 Experimental Results on ImageNet-LT, Places-LT and iNaturalist2018
Setups and baselines. Next, we conduct experiments on large-scale datasets and compare ABSGD with more baselines. We conduct experiment on two different architectures, ResNet50 for ImageNet-LTT and iNat- uralist2018, and 152 for Places-LT and iNaturalist0018, We compare ABSGD with several methods, which include singlo-stage methods such as momentum SGD for optimizing LDAM loss, CB-CE loss and CB-Focal loss, two-stage methods such as 7-normalized (CB-CE), LWS (CB-CE) proposed (Kang et al., 2019), and meta-learning method (META) (Jamal al. 2020). For the two-stage decoupling strategy base- line methods (Kang et al.] 2019), the first stage uses the standard uniform sampling to train the model with the CE loss, and the second stage fine tunes part of parameters in higher layers such as the fully connected (FC) layers and last block of (I.B) feature layers. META also uses the two-stage strategy to improve the performance.
Here, to achieve the SOTA results, we investigate two-stage decoupling strategy for ABSGD. Hence, the two-stage decay À training scheme can be automatically applied. For ImageNet-LT, we jointly train the feature representation and classifier using momentum SGD in the first stage for 90 epochs from scratch, and finetune the FC layer for 90 epochs of ABSGD in the second stage. For Places-LT, (LB) of the convolutions layer and Fully Connected (FC) layer for 90 epochs in the first stage using SGD with momentum from an ImageNet pretrained model, and finetune the FC and LB layer for 30 epochs in second stage using ABSGD. For INaturalist2018, we run momentun SGD (B = 0.9) for 200 epochs in the first stage from the ImageNet pretrained model, and in the second stage we only finetune FC layer and LB of the neural network using ABSGD with > for 30 epochs. is tuned in (10, 20, 30) for all datascts.
train the Last Block
The initial learning rates and learning scheme are described in Table (Appendix). All of our results are reported based on 3 independent. runs.
11

---

Published in Transactions on Machine Learning Research (05/2023)
Table Test top-1 accuracy(%) of different baseline methods on ImageNet-LI with Resnet50.
Methods
Sampling
Loss
Stago-1
TV
Stago-2 TV
Results
Vanilla Model (Jamal
20200
None
CE
All
41.0
CB-CE (Cui
2019
None
CE
All
41.8
Joint Kang et al.
2019
CB
CE
All
All
41.6
NCM Kang et al.
2019
CB
CE
All
FC
44.3
cRT
(Kang et. al.]
2019)
CB
CE
All
FC
43.3
r-normalizer (Kang et al.
2019
CB
CE
All
FC
46.7
META (Jamal et al.
2020)
None
CE
All
FC
48.0
ABSGD
None
CE
All
FC+LB
48.2
Table 4: Test top-1 accuracy different baseline methods on Places-LT using ResNet50.
Methods
Sampling
Loss
Stage-1 TV
Stage-2 TV
Results
Vanilla Model
Jamal et al.
2020
CE
FC/LB+FC
27.9/30.3
Vanilla, Model (Zhang al.
2017)
Range
FC
35.1
Joint KKng et al.
2019
CB
CE
LB+FC
LB+FC
30.2
NCM Kang et al.
2019
CB
CE
LB+FC
FC
36.3
cRT
Kang et al. 2019
CB
CE
LB+FC
FC
36.7
T-normalized
[ Kang el. al
2019
None
CE
LB+FC
FC
37.9
OLTR
Liu et al. 2019
CB
CE
LB+FC
FC
35.9
META Jamal al. 2020
None
CE
LB+FC
FC
37.1
ABSGD
None
CE
LB+FC
FC
38.7
Results Table are the experimental results of ImageNet-LT, Places-LT and iNaturalist2088, respec- tively. To better understanding results, we make some notes in the table. TV represents Trainable Variable. All represents standard training process that optimizes all the parameters of the backbone. FC represents fully connected layer, LB represents the last block of feature layers in the backbone, The CB in the Sampling column denotes balanced data set is required in the second stage. denotes an additional memory is required in the second stage. The bold numbers and the numbers with underline in the table represent the best and the second best the numbers with underline on each dataset, respectively.
Sampling (Cui et al. 2019) in the second stage. represents an additional
We can see that ABSGD combining with the two stage training strategy achieves best on all three datasets. For the ImageNet-LT dataset in Table 3 ABSGD has 0.2% improvements over the next best META method while has requirements on the additional balanced validation datasels. For Places-LT. ABSGD has 0.9% improvements over than the best baseline, 7-normalized. For the INaturalist0118-11 in Table 5 ABSGD outperforms all other baselines by a large margin 0.3% and 0.6% for using both ResNet50 and ResNet152, respectively. To the best of our knowledge, 73.1% is the SOTA result on iNtuuralis20118 dataset. In addition, worth mention that all the other baselines takes the advantage of the Class-Balancee Sampling or additional balanced validation datasets (META), which makes ABSGD more favorable than the baselines.
4.3 Ablation Studies on CIFAR Datasets
In the ablation study, we first study ABSGD from different perspectives: a) the stagewise decay X; b) the influence of the moving average parameter 7 on the testing accuracy. Then we plot the average instance robust weights for each class show the attention of ABSGD towards the minority class.
Two-stage decay of X. To verify the model enjoys the benefits of stagewise decay X the same as the learning rate n, we compare the feature representations in both training and lesting data between adopting the two-stage decay training strategy and using a fixed value of during the training. For two-stage stratogy, we use À 100 the first phase and decay we use = 1. The results are plotted in the second column of Figure B on CIFAR10-IT. It is clear see using the stagewise strategy À yields much better feature representations that are well separated bet
1 the second phase. For fixed values of X,
12

---

Published in Transactions on Machine Learning Research (05/2023)
Taining
Figure 3: t-SNE visualization of feature representations training & testing set on CIFARIO-LT (p 100) with different À strategies. Left two figures: Two-stage decay of X: first phase À = 100 and second phase À = 1. Right two figures: Fixed 1.
Table 5: Top-1 testing accuracy(%) of different methods on iNaturalist2018 using ResNet50, 525
Methods
Results ResNet55
Results
Stage-2 TV
Network
1es
CE (Cui al.
2019
65.8
69.0
LDAM [Cao et al. 2019
68.0
CB-Focal (Cui et al. 2019
61.1
NCM (CE) (Kang et al. 2019
FC
63.1
67.3
cRT (CB-CE) (Kang et al.
2019
FC
68.2
71.2
7-Normalized (CE) [Kang et al.
2019
FC
69.3
72.5
LWS (CB-CE) (Kang et al. 2019
FC
69.5
72.1
META (CB-CE) (Jamal et al. 2020
All
67.6
META² (CB-Fo (Jamal al.
2020
All
67.7
ABSGD (CB-CE)
FC
69.8
73.1
different classes. In contrast, the learned feature representations with a fixed value = are more cluttered. Thus the stagewise decay \ strategy is better than using a fixed value of X, which verifies our algorithmic choice. We also provide the convergence curves of different À strategies in Appendix.
The sensitivity of the moving average parameter y In the derivation of Theorem 1 7 == ( which decreases to 0 when the total number of iterations increases. In practical training, we tune the Y E {0.1, 0.3, 0.5, 0.7,0.9). We report the testing accuracy over independent runs in Figure (left two) and compare it with standard SGD training, the green dashed line. Here we can see that ABSGD achieves highest testing accuracy with 7 0.5 on both CIFAR10-LT and CIFARI00-LT. All the results of ABSGD with different are better or comparable than momentum SGD verifies the effectiveness of the moving average estimator Step 4 in Algorithm [
The average instance weights per-class ABSGD is an instance-level weighting method. For each sample, ABSGD assigns a robust weight that is proportional to the scaled loss value. For ABSGD (CE), we plot the average robust weights for the samples in the minority and majority class in Figure 4 (right two). It can be clearly seen that the average weights of samples in minority class is greater than the average weights of samples in majority class, which verifies the intuition behind ABSGD.
5 Experimental Results on Label Noise Problem
To show the effectiveness of ABSGD for handling noisy labels, we provide empirical studics on the noisy label datasets in this section. We conduct experiments on CIFAR10, CIFAR100, and Clothing (Xiao el al. 2015) datasets. The noise rate is defined as the portion of samples whose ground truth label are randomly flipped. We follow the same sctting as (Wang et al., 2019) and consider both the symmetric label noise and asymmetric label noise on CIFAR10 and CIFAR100 with the noisy rates {0.2, 0.4) (Wang et al, 2019: Patrini et al. 2017: Zhang & Sabuncu 2018) in our experiments. The symmetric (uniform) noisy labels are
13

---

Published in Transactions on Machine Learning Research (05/2023)
CIFRROO
CIFRRL0O LT
0HAR100-L
CHARL00
Figure 4: Left two: the influence of y on the CIEARIO-TT and CTFARI00-LT with imbalance ratio 100. The results are reported over 3 independent runs. The green error bar is the stand deviation of each results. Right two: the average instance weights for difference classes during the training process on CIFARI00-LT and CIFAR100-ST with imbalanced ratio 100 on ResNet32.
generated by flipping the labels of a given proportion of training samples to one of the other class labels uniformly. The asymmetric noisy labels are class-dependent noise, in which the flipping of labels only occur within a specific set of classes. Please refer to the Noise setting section in (Wang et al. 2019) for details. The Clothing1M M is a real-world large-scale label noisy dataset and includes 14 classes with 1M training images in total.
Basclines We compare ABSGD with SGD and a mini-batch basod mothod for solving the min-min DRO formulation (4) named EG (Majidi et al.) 2021) and CTW with a = (Kumar & Amid 2027) with different losses. The first is the standard CE loss. Then theoretically grounded generalized cross entropy loss, named as TCE, has been proposed later on (Zhang & Sabuncu 2018). Furthermore, (Wang et al. 2019) proposed a symmetric loss, named SCE, to address the under learning and overfitling problem that widely exists in the noisy labels. For crafting loss hyperparameters, we tune the symmetric parameters in SCE a, B E {0.1, 1, 0.5, 1, and the truncated parameter in TCE is tuned in (0.1,0.5,0.77 The momentum parameter y for ABSGD is tuned in {0.1, 0.9).
5.1 Experimental Results on CIFAR Datasets
Experimental Setting. Following the setting in WWng et al., 2019), we use a 4-layer CNN proposed in (Wang et al. 2019) for CIFARIO data. For the CIFARI00, we use ResNet18 for the symmetric noisy labels and the asymmetric noisy labels. We report the results of using CE and TCE losses optimized by SGD, and SCE optimized by SGD, EG, CIW and ABSGD, respectively. The weight decay for different methods are tuned in (1e-4, 5c-4, 1e-3, 5e-3). We train the model for 120 epochs and the batch size is fixed as 128 for all settings. The initial learning rates are luned in {le-3, le-2, le-1] and decayed at the epoch of 40, and 80 epochs by factor of 10. The ABSGD hyper-parameter À is tuned in {-0.1, -0.5, -1, 2, -3).
Results. The results are reported in Table 6 Among the three baselines, SCE achieves better / comparable experimental results in most of the different models, settings and datasets. Then the testing accuracy is consistently improved further by optimizing SCE with the proposed ABSGD. By comparing the results across different noisy rates, we can see that our ABSGD(SCE) improves more when the noisy rate increases.
5.2 Experimental Results on Clothing1M
Experimental Setting. We train the ResNet50 starting from the ImageNet pretrained model for all the basclines following the same sctting as (Wang et al. 2019) on the ClothingIM dataset. The training phase includes 10 epochs, and the initial learning rate is fixed as 0.002 and decayed by a factor of 10 at the 5th epoch for all the methods. The weight decay is set as 1e-2. The À for ABSGD is tuned in (-1, (-1,-5,-0 -10 15). We report the results on CE, TCE, SCE optimized by standard SGD, EG and ABSGD, respectively.
Results. The results are reported in Table We can see that ABSGD has better testing accuracy than SGD and EG for all losses.
14

---

Published in Transactions on Machine Learning Research (05/2023)
Table Top-1 testing accuracy (%) on noisy labelled CIFARIO and CIEAR100 data different methods. Results are reported over 5 independent runs. Bold and underline represent the best and second results
Symmetric
Asymmetric
Noisy Rate
0.2
0.4
0.2
0.4
(GD(CE)
88.59 (+ 0.21)
85.75 (# 0.31)
86.62 (# 0.27)
80.81 (+ 0.29)
CIFARIO
SGD(TCE)
89.87 (# 0.27)
86.84 (# 0.32)
88.97 (# 0.31)
80.85 (# 0.27)
SGD(SCE)
90.05 (#: 0.23)
87.83 (=: 0.33)
90.25 (#: 0.34)
81.91 (# 0.42)
EG(SCE)
90.25 (# 0.21)
88.13 (# 0.29)
90.55 (= 0.32)
84.47 (= 0.25)
CIW(CE)
90.29 (+: 0.23)
87.92 (# 0.19)
88.99 (= 0.24)
87.18 (+ 0.21)
CIW(SCE)
90.79 (#: 0.25)
88.21 0.22)
89.97 (= 0.23)
85.13 (# 0.19)
ABSGD(CE)
90.64 0.20)
88.31 0.19)
90.15 (= 0.22)
87.84 (# 0.25)
ABSGD(SCE)
91.15 (+ 0.18)
88.65 (+ 0.21)
91.04 (= 0.21)
86.10 (+ 0.21)
SGD(CE)
68.21 (# 0.27)
62.54( 0.22)
69.57 (= 0.32)
62.93 (# 0.28)
CIFAR100
SGD(SCE)
68.28 (+ 0.29)
60.72 (= 0.23)
69.31 (= 0.31)
64.22 (+ 0.21)
SGD(TCE)
65.12 (# 0.39)
59.61 (# 0.32)
67.98(1 0.28)
60.88 (# 0.27)
FG(SCF)
69.53 (+ 0.21)
65.36 (+ 0.19)
69.61 (+ 0.23)
67.01 (+ 0.24)
CIW(CE)
70.21 (# 0.20)
65.89 (= 0.19)
69.29 (= 0.22)
64.75 (# 0.23)
CIW(SCE)
69.53 (+ 0.19)
65.38 (= 0.23)
70.07 (= 0.21)
67.19 (# 0.24)
ABSGD(CE)
70.63 {= 0.19)
66.23 (= 0.24)
70.70 (= 0.21)
68.16 (= 0.22)
ABSGD(SCE)
71.23 (+ 0.19)
66.39 (+ 0.20)
69.98 (= 0.23)
65.26 (#: 0.24)
Table 7: Top-1 testing accuracy (%) on ClothingIM data of different methods. Results are reported over inde-
pendent
loss
SGD
EG
CIW
ABSGD
CE
69.05
(+: 0.21)
69.42 (#: 0.20)
69.53
0.31)
69.79 (#: 0.18)
SCE
69.31
0.31)
69.32 (#: 0.21)
69.22
0.29)
69.93 (#: 0.11)
TCE
68.28
(1: 0.23)
68.66 (#: 0.19)
68.51 (#: 0.33)
68.69
(#: 0.18)
6
Conclusion
In this paper, we propose unified framework, ABSGD, for addressing the data imbalance and noisy label problem. We provide the theoretical analysis both for the SGD-style and Adam-style updates. Empirical studies on multiple benchmark datasets with different models show the outstanding performance of ABSGD compared with several strong baselines.
Acknowledgments
Q. Qi and T. Yang are partially supported by NSF Career Award #1844403, NSF Grant #2110545, and NSF-Amazon Joint Grant #2147253. Part of this work was supported by Alibaba Gift funding. T. Yang supervised the work including formulations, analysis and experiments, and helped write the paper. Q. Qi is responsible for conducting experiments, writing proofs and papers. Y. Xu, W. Yin and R. Jin provided suggestions in the early stage of this work. The work of Y. Xu and R. Jin were done when they were Alibaba Group at Seattle.
References
Ehsan Amid, Manfred KK Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic loss based on bregman divergences. Advances in Neural Information Processing Systems, 32, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. XiXio preprint ar Xiw:1409.000 2014.
15

---

Published in Transactions on Machine Learning Research (05/2023)
Noga Bar, Tomer Koren, and Raja Giryes. Multiplicative reweighting for robust neural network optimization. arXiv preprint or Xin:21102. 12192, 2021.
Gustavo EAPA Batista, Ronaldo C Prati, and Maria Carolina Monard. A study of the behavior of several methods for balancing machine learning training data. ACM SIGKDD explorations newsletter, 6(1):20-22) 29, 2004.
Andrew Bud. Facing the future: The impact of apple faceid. Biometric Technology Today, 2018(1):5 7, 2018.
Mateusz Buda, Atsuto Maki, and Maciej A Mazurowski. A systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, 106:249 259, 2018.
Róbert Busa-Fekete, Balázs Szörényi, Krzysztof Dembezynski, and Eyke Hillermeier. Online f-measure oplimization. In Advances in Newral Information Processing Systems, pp. 595-603, 2015.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribution-aaaa margin loss. In Advances in Neural Information Processing Systems, pp. 1567-1578, 2019.
Robin Chan, Matthias Rottmann, Fabian Hüger, Peter Schlicht, and Hanno Gottschalk. Application of decision rules for handling class imbalance in semantic segmentation. arXiv preprint (tb::99010899, 2019.
Nitesh V Chawla. Data mining for imbalanced datasets: An overview. In Data mining and knowledge discovery handbook, pp. 875- Springer, 2009.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-355 2002.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. arXiv preprint 1184:77008.088/7, 2020.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bongares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rmn encoder-decoder for statisti- cal machine translation. arxiv preprint Xrxiv:1466. 1078, 2014.
E Choi, P Hall, and B Presnell. Rendering parametric procedures more robust by empirically tilting the model. Biometrika, 87(2))453 465, 06 2000. ISSN 0006-3444. doi: 10.1093/biomet, 2iomet/877...45. URL https:
//doi.org// wtt.://///..119//ommmme....... ww..e//....... 253
Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. Empirical evaluation of gated
recurrent neural networks on sequence modeling. arXiv preprint arXin:1412.3555, 2014.
Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongic. Class-balanced loss based on effective number of samples. In Proceedings of the IEEE Conference on Compuler Vision and Pallern Recognition, pp. 9268 9277, 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, (2(Jul)22211-2133) 2159, 2011.
John C Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 19(3):1378-1400 2021.
Charles Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint. Conference Artificial Intelligence Volume 2, pp. 973 978, 2001.
Yuanrui FAN, Xin XIA, Daniel A COSTA, David LO, Ahmed E HASSAN, and Shanping LI. The impact of changes mislabeled by szz on just-in-time defect prediction(2011).. IEEE Transactions on Software Engineering, pp. 1-26.
16

---

Published in Transactions on Machine Learning Research (05/2023)
Alberto Fernández, Salvador Garcia, Francisco Herrera, and Nitesh V Chawla. Smote for learning from im- balanced data: progress and challenges, marking the 15-year anniversary. Journal of arlificial intelligence research, 61:863 905, 2018.
Saced Ghadimi, Andrzcj Ruszezynski, and Mengdi Wang. single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Oplimization, 30(1):960 979, 2020.
Priyal Goyal and He Kaiming. Focal loss for dense object detection. IEEE transactions on pattern analysis and machine intelligence, 1112999-3007) 2018.
Alex Graves. Generating sequences with recurrent neural networks. aiv preprint arXic: 0850, 2013.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645 6649.
IEEE, 2013.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. novel convergence analysis for algorithms of the adam family and beyond. arXiv e-prints, pp. arXiv 2104, 2021.
Hui Han, Wen- Wang, and Bing-Huan Mao. Borderline-smotc:
over-sampling method in im-
balanced data sets learning. In International conference on intelligent computing, pp. 878-887. Springer, 2005.
Haibo He and Edwardo A Garcia. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9):1263-1288 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Kim Herzig, Sascha Just, and Andreas Zeller. It's not bug, it's feature: how misclassífication impacts bug prediction. In 2013 35th international conference on software engineering (ICSE), pp. 392 401. IEEE, 2013.
Chao Huang, Xian Wu, Xuchao Zhang, Suwen Lin, and Nitesh V Chawla. Deep protolypical networks for imbalanced time series classification under data scarcity. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 2141 2144, 2019.
Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In Proceedings of the IEEE conference on compuler vision and pollern recogration, pp. 5375-5384, 2016.
NNttrualst. The inaturalist 2018 competition dataset. 2018. URL http::///ggghuu...c//ssssaaaaaaa comp/tree//master/000
Muhammad Abdullah Jamal, Matthew Brown, Ming-Hsuan Yang, Liqiang Wang, and Boqing Gong. Re- thinking blasneealanced methods for long-tailed visual recognition from a domain adaptation perspective. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattera Recognition, pp. 7610-7619 2020.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymplotic analysis. Advances in Newral Information Processing Systems, 34:2771-277 2021.
Justin M Johnson and Taghi M Khoshgoftaar. Survey on deep learning with class imbalance. Journal of Big Data, 6(1):27, 2019.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalan- tidis. Decoupling representation and classifier for long-tailed recognition. arXio preprint or orxiv:1111 092117 2019.
17

---

Published in Transactions on Machine Learning Research (05/2023)
management research: A literature review. Journal of Management Analylics, 7(2):139-177 172, 2020. Yue Kang, Zhao Cai, Chee-Wee Wee Tan, Qian Huang, and Hefu Liu. Natural language processing (nlp) in
Sunghun Kim, Hongyu Zhang, Rongxin Wu, and Liang Gong. Dealing with noise in defect prediction. In 2011 33rd international conference on software engineering (ICSB), pp. 481 490. LEEE, 2011.
Yoon Kim. Convolutional neural networks for sentence classification. arXiv preprint arXiv:1408.5880 2014.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Abhishek Kumar and Ehsan Amid. Constrained instance and class reweighting for robust. learning under label noise. Xiv preprint arXiv:2111.055 15,288 2021.
Kuang-Hun Huei Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for scalable image classifier training with label noise. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5447-5456, 2018.
Danicl Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scalc methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33:8847 8860, 2020.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. On tilted losses in machine learning: Theory and applications, 2021.
Tsung-Y Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pp. 2980-2988, 2017.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large-scale long- tailed recognition in an open world. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2537 2546, 2019.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arxiv preprinl arXiv:1608.0300 2016.
Minh- Thang Luong, Hieu Pham, and Christopher D Manning, Effective approaches to attention attention-based neural machine translation. arXiv preprint arXiv: 1508.000000 2015.
Negin Majidi, Ehsan Amid, Hosscin Talebi, and Manfred K. Warmuth. Exponentiated gradient rewcighting for robust. training under label noise and beyond. CoRR, abs/2104.014993, 2021. URL httts://arxiv.
org/abs/2100 01493
01444
Prakash M Nadkarni, Lucila Ohno-Machado, and Wendy W Chapman. Natural language processing: an introduction. Journal of the American Medical Informatics Association, 18(5)5544-551, 2011.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in neural information processing systems, pp. 2971-2998 2017.
Harikrishna Narasimhan, Purushottam Kar, and Prateck Jain. Optimizing non-decomposable performance measures: A tale of two classes. In International Conference on Machine Learning, pp. 199 208, 2015.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances in neural information processing systems, 26, 2013.
Shameem Puthiya Parambath, Nicolas Usunier, and Yves Grandvalet. Optimizing f-measures by cost- scnsitive classification. Advances in Neural Information Processing Systems (NIPS), pp. 2123-2131, 2014.
Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman. Deep face recognition. 2015.
18

---

Published in Transactions on Machine Learning Research (05/2023)
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 1944 1952, 2017.
Boris Polyak. Some methods speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Qi Qi and Shervin Ardeshir. Improving identity- robusttesss for face models. arXiv preprint arXhu:2304408888, 2023.
Qi Qi, Yan Yan, Zixuan Wu, Xiaoyu Wang, and Tianbao Yang. a simple and effective framework for pairwise deep metric learning. arXic preprint orXiv:1912. 1119,, 2019.
Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. A practical online method for distributionally deep robust optimization. arXiv preprint arXiv:2006. 101388,0.1118,, 2020.
Qi Qi, Jiameng Lyu, Er Wei Bai, Tianbao Yang, et al. Stochastic constrained dro with complexity independent of sample size. arXiv preprint XrXic:2210.0555 05.4400 2022.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXio:1810.02061 2018.
Hamed Rahimian and Sanjay Mehrotra, Distributionally robust optimization: A review. orXiv preprint Stl::1908.05654 2019.
Mirco Ravanelli, Philemon Brakel, Maurizio Omologo, and Yoshua Bengio. Light gated recurrent units for speech recognition. IEEE Transactions on Emerging Topics in Computational Intelligence, 2(2):92-100) 102, 2018.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning, Xiv preprint arXiv: 303.09050, 2018.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arxiv preprint arXio:1609.0477. 2016.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference computer vision and pattern recognàtion, pp. 815 823, 2015.
Clayton Scott. Surrogate losses and regret bounds for cost-sensitive classification with example-dependent costs. In Proceedings of International Conference of Machine Learning (ICML), pp. 153-160, 2011.
Shai Chalev-Shwarte and Yonatan Wexler. Minimizing the maximal loss: How and why. In JCML, pp. 793 793-801, 2016.
Yanmin Sun, Mohamed S Kamel, Andrew KC Wong, and Yang Wang. Cost-sensitive boosting for classifi- cation of imbalanced data. Pottern Recognition, (0(12):3358-3377 2007.
Ilya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, pp. 3104-3112, 2014.
Yaniv Taigman, Ming Yang, Marc' Aurelio Ranzato, and Lior Wolf. Deepface: Closing the gap to human-level performance in face verification. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1701-1708, 2014.
Asher Trockman and J Zico Kolter. Patches are all you need? arXiv preprint arXiw:2201.09722 2022.
Arash Vahdat. Toward robustness against label noise in training deep discriminative neural networks. Ad-
vonces in neural information processing systems, 30, 2017.
19

---

Published in Transactions on Machine Learning Research (05/2023)
Ashish Vaswani, Samy Bengio, Eugene Brevdo, Francois Chollet, Aidan N Gomez, Stephan Gouws, Llion Jones, Eukasz Kaiser, Nal Kalchbrenner, Niki Parmar, et al. Tensor2tensor for neural machine translation. arXiv preprint orXic:1803.074 07, 2018.
Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie. Learning from noisy large-scale datasets with minimal supervision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 839- 199-847, 2017.
Daisuke Wakabayashi. Self-driving uber car kills pedestrian in arizona, where robots roam. The New York Times, 19, 2018
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2):119 449, 2017.
Yisen Wang, Weiyang Liu, Xingjun Ma, James Bailey, Hongyuan Zha, Le Song, and Shu-Tao Xia. Iterative learning with open-set noisy labels. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8688 8696, 2018.
Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 322 330, 2019.
Yandong Wen, Kaipeng Zhang, Zhifeng Li, and Yu Qiao. A discriminative feature learning approach for deep face recognition. In European conference on compuler vision, pp. 199-515 Springer, 2016.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 2691 2699, 2015.
Yan Yan, Tianbao Yang, Yi Yang, and Jianhui Chen. A framework of online learning with imbalanced streaming data. In Proceedings of the Thirly-First AAAI Conference on Artificial Intelligence (AAAI), 2017.
Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Sharp analysis of epoch stochastic gradient descent ascent methods for min- max optimization. arXiv preprint arXiv:2002.0538 05300, 2020.
Xi Yin, Xiang Yu, Kihyuk Sohn, Xiaoming Liu, and Manmohan Chandraker. Feature transfer learning for deep face recognition with under-represented data. arXiv preprint arXiv:1803.0900 2018.
Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewisc training accelerates convergence of testing error over sgd. In Advances in Neural Information Processing Systems, pp. 2604 2214,, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. CoRR, abs/1611 111661.000 .03530, 2016. URI. http:/ttt/aai..rrrrg.... www.:.rgg//aaaaa /
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commmunications of the ACM, 64(3):107 115, 2021.
Xiao Zhang, Zhiyuan Fang, Yandong Wen, Zhifeng Li, and Yu Qiao. Range loss for deep face recognition with long-tailed training data. In Proceedings of the IEEE International Conference on Computer Vision pp. 5418, 2017.
Zhilu Zhang and Mert Sabuneu. Generalized cross entropy loss for training deep neural networks with noisy labels. Advances in neural information processing systems, 31, 2018.
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE transactions on pattern analysis and machine intelligence, 40(6): 1452-1463 2017.
20

---

Published in Transactions on Machine Learning Research (05/2023)
Zhi-Hua Zhou and Xu- Ying Liu. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on knowledge and data engineering, 18(1):63-T 77, 2005.
Dixian Zhu, Zhe Li, Xiaoyu Wang, Boqing Gong, and Tianbao Yang. A robust zero-sum game framework for pool-based active learning. In The 22nd international conference artificial intelligence and statistics, pp. 517-526, 2019.
21

---

Published in Transactions on Machine Learning Research (05/2023)
7 Appendix
Table 8: General hyperparameter settings in different experiments of section
Datasets
Initial Step Size
Weight Deray
Schedule
Batch Size
Momentum
CIFARIO-ST/LT
0.1
2e-1
Stagewise Decay
Yuan et al.
2019
128
CIFAR100-ST/LL
Stagewise Deray
al.
128
ImageNet-LLT
0.05
5e-4
Cosine Aunealing
Loshchilov
2016
512
Places- LT
0.05
5e-4
Cosine Aunealing
Loshcliloo
Hutter
2016
512
2Naturalis20088
0.2
1o-4
Cosine Aunealing Losbchllov
Hutter
2016
512
The benefits of momentum Next, we verify that adding the momentuun term can dramatically improve performance. The results are plotted in the left two columns of Figure (5) on CIFAR10-LT (p= 100) and CIFAR100-LT (p- 100) datasets, where we plot the testing accuracy vs the epochs of optimization with an average of 3 runs. The results clcarly show that including a momentum term helps improve performance and stabilize the training process.
The Effect of Damping on Convergence. Figure 3 shows the advantage of using the damping strategy on À on feature representation learning. Here, we plot the convergence curves in terms of testing accuracy in Figure 5 It is obvious to that damping À achieves higher test accuracy over fixed values of X, which also verifies our choice of damping X.
Running Time Comparison To show the efficiency of ABSGD, we conduct an experiment on CIFAR-10 data with different networks on NVIDIA GeForee GTX 1080 Ti. The running time per iteration (scconds) of SGD, ABSGD and МETA methods are shown the following table. It clear to see that ABSGD has a comparable running time as SGD, while the per iteration running time of META way slower than SGD and ABSGD.
Table 9: Tumning time (seconds) per iterations of SCD, ABSGD, and META Jamal et al. 2020 methods CIFAR-10 dataset with different networks.
Network(# # Param.)
SGD
ABSGD
META
ResNet32 (0.46M)
0.0167
0.0176
0.376
ResNet44 (0.44M)
0.0234
0.0250
0.474
ResNet56 (0.85M)
0.0284
0.0296
0.566
ResNet110 10 (1.7M)
0.0684
0.0692
0.882
Experiements on Convmixer We have implemented the newly proposed structure, named as Con- vmixer (Trockman Kolter 2022), which operates convolutional layers on small patches. Convmixer has been shown to achieve competitive results ViT models but with faster training speed and fewer parame- ters. We conducted experiment by comparing ABSGD with CE loss and SGD for optimizing CE loss with on CIFAR10 dataset in the long tail setting with an imbalance ratio of 10, and 100. The result is presented in Table 10
Table 10: Empirical Results on imbalanced dataset CIFARIO-LT with Convmixer structure
Imbalance Ratio
SGD (CE)
ABSGD (CE)
10
82.1 (+ 0.28)
83.90 (+ 0.23)
100
63.2 (#: 0.31)
66.31 (#: 0.21)
Comparison with optimal sample complexity algorithm with RECOVER.
In this section, we compare ABSGD with RECOVER on the CIFAR datasct, which achieves optimal sample complexity when solving regularized DRO with KL-divergence. The results are reported in Table II We see that. ABSGD achieve better empirical that RECOVER on imbalanced datasets.
22

---

Published in Transactions on Machine Learning Research (05/2023)
Table 11: Experimental results on imbalanced CIFATIO-ST, CIFARI00 on ResNet32
Imbalance Ratio
ABSGD
RECOVER
10
85.84 (# 0.27)
82.61 (# 0.43)
CIFARIO-ST
100
66.24 (# 0.35)
63.53 (# 0.71)
10
55.15 (= 0.29)
52.52 (# 0.61)
CIFARI00-ST
100
39.76 (+ 0.37)
37.21 (= 0.64)
Nomentum on CIFARID-LT
Nomentum on CIFAR1DO-LT
Strategies CIFARIO-LT
Strategies CIFARI00-LT
45
Nomenium
A-100
35-
A=1
60-
30-
9:40
15-
10
100 Tppche
255
125 Eportt
100 275
75
Esorhs
Spacts
Figure 5: Ablation studies on CIFARIO-LT and CIFAR100-LT datasets: Left two images: comparing ABSGD with (W/) momenttmm vs without(W/O) momentum. Right two images: comparing ABSGD with different À strategies on CIFAR-LT datasets. The black dashed lines represent the epoch where the learning rates are decayed. For the red line, À also decays from A to A2 at the dashed line epoch. The results are averaged over 3 random trials.
8 Theoretical Analysis of Theorem 1
Notations Denote f(s) = A log(ss) g(w; z) exp( L(wiz) and g(w) = Ex (elg(w;;)) z)], then
Fx(w)= f(((w)) = 1t ((Ex))(w;))))
And Ly., L,, Cg. Cj, D,, Dg are positive constants. By denoting Ly= = Cola + CoCi Cg = CoVei Lp X and Cf = X, we first derive the smooth and continuous property f(-) and g(w;z) for Vz D implied by Assumption [ with the following propositions.
X2
Proposition 1. g(w) a T.g-smooth and Cy-Tipschilz continuous function.
Proof. By Assumption 1 and Theorem (V( VL(w'22)| I Lallw w'l, w', g(w;2)
exp( L(wiz) < Co. L(w;z) and VL z): < C1, we have S g(w; z) I Co. Vz ~ D and
|V (w))l
- Σ g w: z 1|
5 n
V ((;;
exp( L(W:z)
L(W; 2)
VL( z
= =E,1IV2 g w:
E,1
2 L(w, 2)
+ cxp(
(w; 2w:
A
(10)
L( w z
expl L(w;z)
< 1 L( w:
expp
exp(
|||
[L(w:2)VL(w;z)>
x2
CoLi
Co F [[:
CoLi CoCi
x2
X²
In addition, with the assumption in Theorem
L L(w; 2)
[ Fk Vg
S ([
Fe, ([][: exp(
||]
X
(11)
Co (VL
Co
COvTT
F,
x
x
X
23

---

Published in Transactions on Machine Learning Research (05/2023)
Proposition 2. f(s) Alog(s) is -msmooohh and Cy- -ipscchttt continuous function.
Proof. V.((s) A.. As g(w:z) E (1, Col. Vf(s) S X, which implics [V S X. In addition,
[Vf(s)) vf(s2)] =
|| s2 < A||s 52
(12)
82
8182
Following the assumption 1 Proposition and 2 and the conditions in Theorem D then by let G max ma Cg), LF T.f the following inequalities hold:
[Vg(w; - Gz Sf(s)
Ellg(w; 2) - (w)
F(w) is LF smooth.
Next, we provide the following lemma to describe the objective gap between adjacent solutions for any Lp-smooth function F(w): Id - with the We+1 = Wt 1 update. Vi E Ed can be any vector.
Lemma 1. Consider sequence update We+1 = W. -W- f/v++1, suppose em I ό S cun for a Lm-smooth function F, with The S a/220 we have
F(W++1) S F(w:) + " IVF(w.) v.-
" "
7 1lve-
Proof. Due the smoothness of F, prove that under nLf S a/ 222
F(Wr+1) S F(w.) - VF(w:)) (W++1 w.) + LF
|| well
LFT
= =F(w.) -V.((..) Ve+1
||2+1 1|2
S F(w,)) + VF((:) Ve41
ijcr
VF(::))1
LFT 11
11v+++111
2
2
< <F(w)) + 1/cu
VF((,,) V(+1/1
79
+
L
nctt
vlve2=11
)l
2
2
2
< F(w.) + 1/Cu
VF((w)) - 2
77
[VF((,)))
79
||4e11122
2
4
Remark When Ve41 is stochastic gradient estimator, [[V V represents the stochastic gradient estimator variance. In the following, we show that [[W)(w)-- vz+1 112 decreasing for the proposed stochastic ostimator in ABSGD and ABAdam, which guarantees the convergence of the algorithms.
Next, the next lemma describes track the (VF(w)-Vetl))
Lemma 2. Suppose Assumption 7 holds, then with the updates of 81+1 = (1 - 7) + (w(,;;
Vt+1
(1 3)v, + 3V (Wr; 2,) V (sc+1), for Vt > 0, the following inequality holds:
E, VF (w, 112
< (1 - 3) VF((LL1) vell2
L3 w
w ( s141112 + G²
8o
The third term the right hand side be bounded with the following lemma:
24

---

Published in Transactions on Machine Learning Research (05/2023)
Lemma 3 (Lemma 2, wang2017sttochastie). Consider moving average sequence SL41 =1- zi) for tracking g( ((We), where [x(g((r:?) = g(we) and is Cg-Lipchilz continuous operalor. Then we have
Ballst41 = -x(x ((llx(((x - -xxx)))))) 2T, We - w
Proof of Lemma
[VF(w,) vet1l
= -1
< [I(1
- -
+ (1- ()W)))))) ( Vf
Taking expectation on both sides over conditioned on historical randomness and noting that E, (F((w) Vo(w:2))V[(((.))) = 0, we have
B.ILVF((,)) - 11+1/1
+ V Vdd
1 Vo( [f
+ 2,3 Vg W:; (V(((w))) Vg(ww: 21 ((++)) - Vg((,;
(1
12 +2(1+ + (1 Iw: w.-1 +1
+ -
(EEell((w.) -142
+ +2 Ww( 11 3 Ge 8841
(6)
$ (1 (]I - v.112 / w. w. w.- -f
48GG,, 11
C4 96 $2+1l12
w ( (1- 3) - vell2 + 1/ -/ ww - -821112
+ C2
where the inequality (a) is due to x (1++)](((+++ and ab < 2 + The inequality (b) ap-
plies B < 1, 1, S F( - /|
Vg(w,; [ s < 2G2 and the
( w:)) (w:)) FE, [| (l.))) ||
last inequality (c) is due to 3G 2 PG.
8.1 Convergence Analysis of ABSGD
Without loss of generality, ignore and consider the objective in the form of F(w) = f(((w)) where f Alog(-) is a deterministic function and g = E]exp(L(w; is stochastic function, and at each iteration, we only sample one data 2; for evaluating g(w;; 2,) and Vg(w;; To provide the convergence analysis for ABSGD, the updates of Steps 3-6 in Algorithm can be equivalently written as:
81+1 (1 (1-7)s: (g(W;
V2+1 fy,, V V (8
W W, V
25

---

Published in Transactions on Machine Learning Research (05/2023)
With some change of variable, the above update is equivalent to
St+1 (1 7)8 + 7g(
Vi+1 (1 -,)vv, + 8o V.(
W++1 = W. Ve++++1
When no80 17, 8 1 1-80, Bo, the above two updates are equivalent. Hence, below we will analyze the second update.
Hence Lemma and 3 are applicable to ABSGD updates with ij no, Cu = 1, = 30- Based on this, we provide the convergence analysis for Theorem
Proof of Theorem
Then by A, = (w.) - V++1ll and according to Lemma 2
we have
A A.
413 vill
B
A
E
48. + 5G||s4+1 s(w.)ll
Bo
P
Taking summation, we have
A 1+
4
ve+1
E
A
E
+
48 + 5G Σ |1112 s(we+1))?
(13)
30
t=
Next we bound E E 1
||8111 g(w:))]l1 = BI T-1
||0.22 (W(++)) by the following Lemma
21 W: w/-1
E|11s141 - g(w:))l?] & (1 - >)]s - - + +
(1I g(w, 1112 B&ll 1--1|10-1111001 ((w.)ll3)
2L S12l,, w.
wi-1ll
||5 s(w,-1)11 <
+VV +
g)
7/2
As a result,
T E,
[[[| g(wi)ll
T 21 vell
8141 s(w))l] <
+ +V,T +
(14)
Combining the equation
13 and
14
incqualitics together we have
Ao
L
1++1
5GB 9(w1))l3]
10G13
E
A
E
+ 43
Σ
+ +5GVVTT
g
7
72
(15)
Finally, combining Equation
15 with Lemma 1 and 30 = 7, we have
< F(w1) - F(Wr)
T-
T-1
|v+1ll
E
V F w: 1
T
NoT
T
2
T
4
1=0
1=0
F(w1)=
F+
E[Ao + 5/13 2(
+ xx(422 + +5VV,)
noT
7T
(L2 + 10G12)
Ve+ 11?
|lve+111
+ E
72
1=0
where F(W1) F. S
AP, Ao = 1lv VF(wo)l12
Vg 2n (f)
VF(wo)]12
3051 v
|100 V/)gg// 20)) VF(wo)]2 2.60.03 +22
20 +203 and ||8| g(wi))?
26

---

Published in Transactions on Machine Learning Research (05/2023)
[I11 7)81 + WW. 21) ((1))l =0 |[ (1g zo)) + (9(w1, z1) o(w1)]l
40 +
408 + 200 = -100
Then by sctting Bu = S 3(GG*+5GV,) 170
2²
T 2 max
" 0
2 +
ety
ety
max 0(4 +540"+ +203+ +203))
15(46)+5GV,), / +10G1 AF
J. MOLF S
MoLF S 2 we have that o 2
E T Σ
VF
Se
Therefore, by 7 7007; B 7, which finishes the proof of ABSGD in Theorem
8.2 Convergence Analysis of ABAdam
Theorem 2. Assume assumption holds and there erists Co, C1 such that ssp(L(wez.)// Co. Co.1IVT(w: 21 & C1, for all We and any 24, Then, For X = T 0 with oppropriate 1), T: B1, B2, ABAdam
ensures that E
Σ IVF! (wo)lp S Se after T O(1/ct) iterations, where we V I (w.)))]
S e² afler T = O(1/et) ileralions, and for X =- < 0 with appro-
priate n, Y, 3, ABAdam ensures that E
eahibit the constant in the big O.
A B Adam The updates of ABAdam:
Se+11 1 (1 - 17788 + (w;
Ve+1 Biv; (1 V.) V (5++1)
Uc+1 8zu, (1 VV) (((+4)))
Wi+1 W. m
Vi+1
Ur+1 + Go
To provide theoretical analysis for ABAdam, we add another assumption following the proof of (Guo et al. 2021
Proposition 3. Suppose Assumplion holds, there exists conslant a = 1/(Go + G), G max Cf), and Ca Go then q: 1///u, + Go is lower and upper bounded, such that Vi, I ||qr.il S Cu, where qr denoles the i-th element of qr-
1
Proof. Then
[VV[s<4)VV((ww)) o V((H4))V(( S [[ S &C0 S G²
where +
represents Hadamard product. By set u0.i
C G2
003
u
(1
32)
Vol I G2 vt 0. Therefore 1 vu++i++oo
2 0o46
Proof of ABAdam. The proof of ABAdam reuse the steps of ABSGD up to Equation 31 = Bo. îj. In addition, by setting na S Ω GotYu.. & n/s
15 by setting
27

---

Published in Transactions on Machine Learning Research (05/2023)
Then according to proposition 3
and Lemma 1 and let y 1 - B1, we have
T-1
Σ VF
(w])l
F(wi) F(WT)
+ qT
Ca
T-1
Σ
A.
T-1
2
T
4
1=0
F(wi) - F.
C. Be + +51882 (wi))l
+ 7(G2 + 55VV) -
CTTT
TTa
CL + 10GL ve+1ll
|l1v+t111
+
E
472
The same as ABSGD, F(wi) F, < AF, Do S 2G + 20%, Peq
- ||52-1(ww) g(w))l I 100 Then by set-
ting - 31 S 3r, (4,
Very
T max
3ew "20" +20 "y &D1++0013A
2nd +L,G,
2407
Aan
96 (4G2 + max
+1220++227++-- +203++100 100 cto
18cu (1G2 5GVV) D. 110GLAA
}, MoLp S 2 we have that
E
VF(w:)]l se,
which finishes the proof of ABAdam Theorem
8.3 Equivalence derivation between Min-max Robust Optimization and Composition formulation
In the section, we show the equivalence between the min-max formulation 3 i.e,
Σ
P:L( - Σ Pi In(pp.) +r(w), T 0
min max wER" P 1=1
(w)
min min wER" PEA,
Σ (w:; + Σ (r())
(w)
and the composition formulations, i.e,
1 ()p(((w:2))/)++r())) T> 0
(w) = log 72
FPP) = -T log
Σ exp(<L((wzz)//) <<0
Proof. Here, we provide the detailed derivation for T 0. Similarly, the derivation for 0 can be done using the same method. Recall the problem:
min max (w(w)= = Σ -h(p 1/n) + +r(w), weRd PEA.
where A, = {p E R" Σ:P = 1,0 < < In order to solve the inner maximization, we will fix w and derive an optimal solution p" (w) that depends on w. To this end, we consider the following problem:
Σ pil((w;)))++ + h(p 1/n)
min A
1=1
where r(w) was neglected since it does not involve p. Note the expression of hpp. 1/n) E. log(np:) E; Pi log(p:) + 7 log(n) due to E.P: 1. There are three constraints to handle, i.e., P; Vi and
28

---

Published in Transactions on Machine Learning Research (05/2023)
Pi S v, and E, 1. Note that the constraint P; 2 0 is enforced by the term p. log(p:), otherwise the above objective will become infinity. As result, the constraint, p; < is automatically satisfied due to EiP: = 1 and 2 0. Hence, we only need to explicitly tackle the constraint E;p: = 1. To this end, we define the following Lagrangian function
(p, p1)
Σ pil(w;z,) Tllog n + Σ Pr log(p:)) + p E Pi- 1)
where y is the Lagrangian multiplier for the constraint E.pr 1. The optimal solutions satisfy the KKT conditions:
- ((w;))) + T(oo(pp) (w)) + 1) =
Σe((w)= =1
Due to the second equation, conclude that p. (w) exp(f(w:z)/A) Plugging this optimal p" (w) into the original min-max objective, we have
From the first equation, derive (w)
exp(((W:))AA)"
Σ pj (w))(w::.) Flog log(() + +r())= log 1 Σ (sp((((;z))/T) r(w).
which is the (w).
29


Reviews:
[{"review_id": "615cdrX9RG", "reviewer": "Reviewer_Mbkp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. the paper accompanies the proposal with sound theory\n\nWeakness:\n1. lack of novelty. Ref. (59) and (66) already propose this method. In comparison, the authors argue that their proposal suggested how to incorporate momentum, but adding the momentum seems rather trivial. \n\n2. motivation is poor. If the idea is to improve the robustness of SGD to data imbalance or label noise, the authors should first present some convincing evidence showing that SGD does have a serious problem here -- not just on a toy example, and the comparison is only made for the first iteration\n\n3. in fact, the empirical result of this work implies one of the following two things: (1) SGD does not have a problem with data imbalance, or (2) the proposed method does not do better than SGD in dealing with SGD. See Table 1; even at an imbalance ratio of 100, the proposed method only improves SGD by 0.7%, which is actually with the error bar of the result for SGD. I see no significant difference between the proposed method and SGD\n\n4. a question about the theory. in theorem 1, does one have to decrease the learning rate as a power to ensure convergence? If so, it should be stated clearly. Or does the theory apply to a constant learning rate?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a variant of SGD that assigns different weights to different data points. The method is shown to be relevant for problems such as class imbalanced learning and label noise learning", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors might want to significantly improve the motivation part of the paper and align the results with the motivation. Currently, I do not find the motivation convincing, nor do the results answer the stated motivation\n\nTheory-wise, it would be more convincing if the authors presented a theory/proof of how the proposed method improves the robustness of SGD in toy examples. Proof of convergence is nice, but does not help with the main claims of the paper", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "v9YBZjHvzs", "reviewer": "Reviewer_c8Ys", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The proposed method is simple and easy to implement.\n- The modification can be applied to multiple gradient-based optimization methods.\n\n## Weaknesses\n\n- It is nice that the author aimed to solve two problems: label imbalance and label noise. However, it is weird that the author treated them as two disjoint problems (Eqs. (3) and (4), depending on positive or negative $\\lambda$). In some real-world situations, both can happen at the same time. Based on the alleged dichotomy, it is unclear how to deal with the case when imbalance and noise are present.\n- Many existing works on noisy labels assume a noise model (symmetric, class-conditional, instance-dependent, etc.), but it seems this work did not specify one. Hence, it is unclear what kind of noisy label problems can be solved by the proposed method.\n\n## Technical issues\n\nThe presentation of the proposed method is a bit confusing. The weight regularization and the momentum term seem not essential to the proposed method. The weight $\\tilde{p}_i$ in Eq. (2), which is the novel part of the proposed method, is a fraction of an $i$-dependent part $\\exp(\\frac{L\\_i}{\\lambda})$ and an $i$-independent part $s\\_{t+1}$. If I did not misunderstand anything, the update step contributed by the $i$-th example is\n\\begin{equation}\n\\frac{\\eta}{B s\\_{t+1}} e^\\frac{L\\_i}{\\lambda} \\nabla L\\_i = \\frac{\\eta}{B s\\_{t+1}} \\nabla (\\lambda e^\\frac{L\\_i}{\\lambda})\n\\end{equation}\nThen, we can see that the proposed method essentially changes the loss function from $L$ to $\\lambda e^\\frac{L}{\\lambda}$ and uses an adaptive learning rate based on the reciprocal of a moving average of the empirical risk of each batch.\n\nThen, why does the proposed method solve label imbalance or label noise problems? The theoretical analysis provides little insight.\n\n## Minor issues\n\n- The term \"attentional-biased\" is confusing because it hints at the attention architecture (e.g., transformer), but it is only reweighting here.\n- The author claimed that the method is \"systematic,\" but its meaning is unclear.\n- The author used Apple's FaceID and autonomous driving cars as examples in the introduction section, but they seem not to be classification problems studied in this work.\n- \"Existing studies in these methods are not very successful for deep learning with big data\": insufficient support.\n- As far as I know, \"robust weighting\" is not widely accepted in the community and was not properly defined in this paper.\n- \"The focal loss lacks theoretical foundation\": see https://arxiv.org/abs/2011.09172.\n- \"Most existing optimization algorithms for DRO are not practical for deep learning\": insufficient support.\n- A [simplex](https://en.wikipedia.org/wiki/Simplex) in $\\mathbb{R}^n$ is $(n-1)$-dimentional.\n- Step 7?\n- $\\lambda \\in \\\\{\\mathbb{R} \\setminus 0\\\\}$ should be $\\lambda \\in \\mathbb{R} \\setminus \\\\{0\\\\}$\n- Do $F_\\tau^{(1)}(\\mathbf{w})$ and $F_\\tau^{(2)}(\\mathbf{w})$ include $r(\\mathbf{w})$ or not?\n- The expression $\\min A = B$ is ambiguous, which means $B$ is the minimal value of $A$, but it seems that $B$ is defined as or equal to $A$ here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a modification of gradient-based optimization methods, which is claimed to be effective for label imbalance and label noise. The proposed method essentially combines a loss function modification and an adaptive learning rate. The proposed method was evaluated on the image classification task.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The explanation of why the proposed method can solve label imbalance/noise problems and the minor issues listed above.", "broader_impact_concerns": "The author did not provide a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oKpmfQM9bC", "reviewer": "Reviewer_HCLQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points:\n\n(1) the motivation of this paper is clear and meaningful, where the label imbalance and noisy problems in DL are critical and challengeable especially considering the efficiency as well.\n\n(2) the technical part is sound and without obvious flaw for me.\n \n\nWeak points:\n\n(1) there are several typos, grammar issues, and layout problems (e.g., Table 8 is totally missing) through the manuscript.\n\n(2) since the meta-learning based method is the main competitive baseline (from the prospect of accuracy compared with ABSGD), it is recommended to adopt other mainstream backbones (e.g., transformer-based architectures) instead of only comparing the performance with ResNet series to demonstrate the robustness of ABSGD. \n\n(3) As mentioned in this paper, compared with existing individual-level weighting methods using meta-learning that require three backward propagations for computing mini-batch stochastic gradients, ABSGD is more efficient with only one backward propagation at each iteration as in standard deep learning methods. In other words, the efficiency improvement could be reflected in the training runtime, where there is no related experiments justified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes an end-to-end SGD variant namely ABSGD to handle the problem of data imbalance and label noises. With comprehensive theoretical analysis on the model update and experiments on multiple benchmark datasets, the paper demonstrates that ABSGD shows better performance than baselines in terms of the effectiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weak points aforementioned in the revision. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iVqUQNdwPX", "reviewer": "Reviewer_Nn3h", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Major Comments\n- The proposed method is strikingly similar to CIW (Kumar and Amid, 2021), where the updates are motivated via a min-min formulation with an $\\alpha$-divergence constraint on the weights (although the authors seem to have missed this work). $\\alpha=1$ corresponds to the KL divergence and the Exponentiated Gradient (EG) updates in the current paper. However, the only difference between the proposed method is the denominator. In CIW, the denominator is set to the sum of the numerator terms, therefore, yielding a probability distribution for the weights. In the proposed approach, the denominator is replaced with an EMA over training batches. However, my main concern is with the correctness of this replacement. In Eq. (6), the minimization is given over all examples in the training set, thus, motivating Eq. (8), where the denominator is replaced with $s_{t+1}$. However, the actual update is given in Eq. (2), which is over the mini-batch of examples $B$. Thus, I find this motivation conflicting, and I don't see any reason to use a different normalizer than the one in CIW. If the authors believe that this heuristic change works significantly better in practice, they should perform a clear comparison with CIW with and without this alteration.\n- The min-max formulation can also be derived from CIW, although no experiments are given for the min-max formulation in the CIW paper.\n- The convergence results for Majidi et al. (2021) are given by Bar et al. (2021) (Theorem 4), which is essentially the same result in the current work.\n- The additional derivation for ABAdam in Eq. (9) is essentially redundant. Basically, the reweighted gradient can be passed into any optimizer (including Adam) without any alteration to the optimizer. The update in Eq. (9) precisely yields this procedure.\n\n\n### Minor Comments\n- Please use the standard (author, year) bibliography format of TMLR.\n- Please use $\\log$ instead of $\\text{ln}$ consistently throughout (Eq. (6) and Eq. (7)).\n- The robust bi-tempered loss (Amid et al., 2019) is the correct generalization of the cross entropy loss (in terms of properness). Please also include it in the related work on robust losses.\n- The experimental results using EG seem to be weaker than expected. The results are in contrast with the ones reported by Kumar and Amid (2021). EG has a long-term memory (at the cost of storing one weight per example) and, thus, works better than the reweighting methods that rely on only batch information. The EMA in the proposed method is unlikely to produce such improvement (since it aggregates information over different batches, not the same examples in the batch over multiple trials). Please check your tuning procedure and make sure the learning rate schedules for the EG weights are consistent with Majidi et al. (2021).\n\n### References\n- Abhishek Kumar and Ehsan Amid. \"Constrained Instance and Class Reweighting for Robust Learning under Label Noise.\" arXiv preprint arXiv:2111.05428 (2021).\n- Noga Bar, Tomer Koren, and Raja Giryes. \"Multiplicative Reweighting for Robust Neural Network Optimization.\" arXiv preprint arXiv:2102.12192 (2021).\n- Ehsan Amid, Manfred K. Warmuth, Rohan Anil, and Tomer Koren. \"Robust Bi-Tempered Logistic Loss Based on Bregman Divergences.\" Neurips (2019).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces an example weighting approach to learning from class-imbalanced data (or hard examples) as well as noisy examples. The method consists of assigning weights to the examples in a batch based on their loss value. The form of the weights mimics the exponentiated gradient update. However, the denominator is replaced by an EMA instead of the sum of the numerator. A convergence analysis of the algorithm is provided, and the results are validated on standard datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please provide a better motivation for using an EMA instead of the sum for normalizing the weights. The current motivation based on alternating between minimizing the loss over all examples vs. the examples in the batch is inconsistent. If the EMA does not have a proper theoretical motivation but shows significant improvements in practice, please show this empirically and perform a thorough comparison with CIW.\n- Please verify the experimental results using EG. The results seem to be inconsistent with the ones reported by Kumar and Amid (2021).\n- Please draw a distinction between the results in Theorem 1 and the results in Bar et al. (2021), Theorem 4.\n- Please use the standard (author, year) bibliography format of TMLR.\n- Please replaces $\\text{ln}$ with $\\log$.\n- Please add the robust bi-tempered loss (Amid et al., 2019) and more examples of robust losses to the references (see Kumar and Amid (2021)).", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper designs an instance-wise weighting mechanism for stochastic optimization in gradient based algorithms for robust optimization. The algorithm can be explained by the min-max or min-min distributionally robust optimization principles, and is well justified by both theory and experiment results.

There are 4 reviewers, and they hold different opinions about the paper. I went through the paper, the comments and the rebuttal, and I believe most of the reviewer concerns have been addressed, and thus the paper is acceptable after a minor revision. Specifically, I summarize the main concerns and my opinions below:

Reviewer Mbkp: 1) motivation and novelty: the revision has incorporated more examples and detailed explanations, 2) experiments: more explainations and results are added in the revision. I believe the rebuttal has cleared out the problems.

Reviewer c8Ys: 1) separation of label imbalance and label noise: this is minor and can be resolved by more explanations; 2) technical issues: I believe the rebuttal has addressed the issues.

Reviewer HCLQ: more comparisons with existing methods: the rebuttal has added more experimental results, which I believe has addressed the problem.

Reviewer Nn3h: the reviewer has more fundamental problems, and he has communicated with the authors in the rebuttal. The interaction cleared most of the questions, but the reviewer still concerns about the following: 1) the calculating the normalization in CIW and EG (baselines) being expensive: I believe this is a misunderstanding, the authors did not claim this; 2) the proposed algorithm does not have normalized weights in a minibatch: I agree with the authors that this is unnecessary, and the reasoning of the authors is convincing; 3) why using the EMA for computing the normalization: the authors provide detailed explanations as well as theoretical guarantees, which are lack of in other methods, which I agree with; 4) methods of Majidi et al. and Bar et al. are the same: I agree with the authors there are some differences between these two algorithms, and in addition, this does not impact the contribution of the proposed method too much.

Overall, I believe the concerns raised by the reviewers have been well addressed in the rebuttal. However, I request the authors to incorporate the comments from the reviewers and revise their paper accordingly, to make it more complete and clear.

Decision: Accept (poster)