# IMPROVING THE ACCURACY OF LEARNING EXAMPLE WEIGHTS FOR IMBALANCED CLASSIFICATION

**Yuqi Liu & Bin Cao[∗]& Jing Fan**
College of Computer Science, Zhejiang University of Technology, Hangzhou, China
_{liuyuqi,bincao,fanjing}@zjut.edu.cn_

ABSTRACT

To solve the imbalanced classification, methods of weighting examples have been
proposed. Recent work has studied to assign adaptive weights to training examples through learning mechanisms. Specifically, similar to classification models,
the weights are regarded as parameters that need to be learned. However, the
algorithms in recent work use local information to approximately optimize the
weights, which may lead to inaccurate learning of the weights. In this work, we
first propose a novel mechanism of learning with a constraint, which can accurately train the weights and model. Then, we propose a combined method of
our learning mechanism and the existing work, which can promote each other to
perform better. Our method can be applied to any type of deep network model.
Experiments show that compared with state-of-the-art algorithms, our method has
significant improvement in varieties of settings, including text and image classification over different imbalance ratios, binary and multi-class classification.

1 INTRODUCTION

Classification is a fundamental task in machine learning, but in practical classification applications,
the number of examples among classes may differ greatly, even by several orders of magnitude.
Standard learning methods train the classification model on such an imbalanced data set, which
makes the trained model biased. This bias is that the model will prefer the majority class and easily
misclassify the minority class examples. This class-imbalance problem exists in many domains,
such as Twitter spam detection (Li & Liu, 2018), named entity recognition (Grancharova et al.,
2020) in text classification, and object detection (Oksuz et al., 2020), video surveillance (Wu &
Chang, 2003) in image classification.

There are very rich research lines on using the methods of weighting examples to solve the class
imbalance problem. In general, the weight of the minority class is higher than that of the majority
class, so that the bias towards the majority class is alleviated. Typically, the example weight value of
each class is often set to inverse class frequency (Wang et al., 2017) or inverse square root of class
frequency (Mahajan et al., 2018). However, the example weights in these methods are designed
empirically, hence they can not be adapted to different datasets and may perform poorly.

Recent work has studied the methods of using learning mechanisms to adaptively calculate the example weights. Ren et al. (2018) propose to use a meta-learning paradigm (Hospedales et al., 2020)
to learn the weights. In this method, the example weights can be regarded as a meta-learner and
the classification model is a learner. The meta-learner guides the learner to learn by weighting the
example loss in the model optimization objective. More specifically, the model objective is to get
_the optimal model that minimizes the example-weighted loss of the imbalanced training set. Ob-_
viously, different weights will affect the performance of the optimal model. Which weight values
make the corresponding optimal model the best? This method collects a small balanced validation
set and evaluates the weight values through the validation performance of the model. Therefore, the
meta-learner objective, namely meta-objective, gives the best weights that make the optimal model
_minimize the loss of the balanced validation set. This optimization problem is challenging. The key_
is that, in the meta-objective, the weights indirectly affect the loss through the optimal model, so it

_∗Corresponding author_


-----

is necessary to clearly define the dependence of the weights and the optimal model in the model ob_jective for optimizing the weights. However, it is expensive to get this dependence through multiple_
gradient descent steps in the model objective. Ren et al. (2018) propose an online approximation
method to estimate this dependence, that is, the method trains the model using a gradient descent
step in the model objective and then can determine the relationship between the weights and the
trained model in this step. Hu et al. (2019) propose to update the example weights iteratively to
replace the re-estimation proposed by Ren et al. (2018), but also adopt the local approximation to
optimize the weights. However, this approximation only considers the influence of the weights on
the trained model in a short term (in a descent step), resulting in inaccurate learning of the weights.

In this paper, we firstly propose a novel learning mechanism that can obtain the precise relationship
between the weights and the trained model in the model objective, so that the weights and model can
be optimized more accurately. In this mechanism, we convert the model objective into an equation
of the current model and weights. Then, we derive their relationship from this equation, and then
we use this relationship to optimize the weights in the meta-objective and update the corresponding
model. Since this optimization process always satisfies this equation, we call it learning with a
constraint. However, the mechanism only uses the model objective to calculate the relationship but
does not optimize the model for the model objective. To solve this problem, we integrate the method
proposed by Hu et al. (2019) into our learning mechanism and propose a combined algorithm. In this
algorithm, the method of Hu et al. can help to further optimize the model in the model objective, and
our learning mechanism can make the weights and model learn more accurately. Finally, we conduct
a lot of experiments to validate the effectiveness of this algorithm. The experimental settings include
(1) different domains, namely text and image classification; (2) different scenarios, namely binary
and multi-class classification, (3) different imbalance ratios. The results show that our algorithm
not only outperforms the state-of-the-art (SOTA) method in data weighting but also performs best
among other comparison methods in varieties of settings.

The remainder of this paper is organized as follows. Section 2 introduces preliminaries of the two
objectives and the main idea of Hu et al. (2019). Section 3 presents our mechanism of learning with
a constraint and the combined algorithm. Section 4 presents the experimental settings and evaluation
results. Section 5 summarizes the related work and Section 6 concludes this paper.

2 PRELIMINARIES AND NOTATIONS

Let (x, y) be the input and target pair. For example, in image classification, x is the image and y is
the image label. Let Dtrain denote the train set, and Dtrain = {(xi, yi), 1 ⩽ _i ⩽_ _N_ _}. Let Dval be a_
small balanced validation set, and Dval = {(xi, yi), 1 ⩽ _i ⩽_ _M_ _} where M ≪_ _N_ . We denote neural
network model as Φ(x, θ), where θ ∈ _R[K]_ is the model parameter. The predicted value ˆy = Φ(x, θ).
We use loss function f (ˆy, y) to measure the difference between predicted value ˆy and target value
_y, and the loss function of data xi is defined as fi(θ) for clarity. Standard training method is to_
minimize the expected loss on the training set: _i=1_ _[f][i][(][θ][)][, and each example has same weight.]_
However, for an imbalanced data set, the model obtained by this method will be biased towards the
majority class. Here, we aim to learn a model parameter θ that is fair to the minority class and the

[P][N]
majority class by minimizing the weighted loss of training examples:


_θ[∗](w) = arg minθ_


_wifi(θ)_ (1)
_i=1_

X


where w = (w1, ..., wN )[T] is the weights of all training examples. We use Ltrain to represent the
weighted loss on the training set _train. For a given w, we can obtain the corresponding optimal θ[∗]_
_D_
from Eq.1. Thus, there is a dependence between θ[∗] and w and we write it as θ[∗] = θ[∗](w).

**Learning to Weight Examples The recent work (Ren et al., 2018) proposed a method of learning**
the weights of training examples. In this method, the optimal w is to make the model parameter
_θ[∗]_ obtained from Eq.1 minimize the loss on a balanced validation set. It means that this model
performs well on a balanced validation set, and it can fairly distinguish examples from different
classes. Formally, the optimal w is given as


_w[∗]_ = arg minw


_fi[v][(][θ][∗][(][w][))]_ (2)
_i=1_

X


-----

where the superscript v stands for validation set. Let Lval be the loss on the validation set Dval.

**Learning the Parameters The recent work (Hu et al., 2019) introduced an algorithm of solving the**
model parameter θ[∗] and weight w[∗]. The algorithm optimizes θ and w alternately until convergence.
In each iteration, the algorithm utilizes a gradient descent step in Eq.1 to approximate the relationship between θ and w, and then calculates the gradient ∇wLval and ∇θLtrain to update w and θ
respectively.

More specifically, at the t-th iteration, the algorithm first calculates the approximate relationship
between θ and w through the t-th gradient descent step in Eq.1. We define a matrix F (θ) =
( _f1(θ), ...,_ _fN_ (θ)), whose column vector represents the derivative of fi(θ) with respect to θ,
_∇_ _∇_
so we calculate the derivative of ∇θLtrain with respect to θ as ∇θLtrain = F (θ)w. Then, the t-th
gradient descent step of θ is given as

_θˆt+1 = θt −_ _ηθF_ (θt)wt (3)

where ηθ is the descent step size on θ. In order to avoid very expensive calculations, the algorithm
ignores the influence of w on θt. Therefore, in the single gradient descent step, _θ[ˆ]t+1 linearly depends_
on w.

Then, based on this linear dependence, the algorithm can calculate the gradient ∇wLval and uses
gradient descent to update w, and then updates θ again to make it perform better on validation set.
Substituting the updated _θ[ˆ]t+1 into Eq.2, we have Lval =_ _M1_ _Mi=1_ _[f][ v]i_ [(ˆ]θt+1(w)). We can observe

that the w acts on _θ[ˆ]t+1 and then affects_ _val. Thus, combining Eq.3, we can calculate the gradient_

_T_ _L_ P
_∇wLval = (∇wθ[ˆ]t+1)_ _∇θˆt+1_ _[L][val][ =][ −][η][θ][F]_ [(][θ][t][)][T][ ∇]θ[ˆ]t+1 _[L][val][, so the update on][ w][ at][ t][ step is given as]_

_wt+1 = wt + ηwηθF_ (θt)[T] _θˆt+1_ _[L][val]_ (4)
_∇_

where ηw is the descent step size on w. According to gradient descent theory, when ηw is appropriately small, Lval(wt+1) ≤Lval(wt). This means using wt+1 to update θ performs better than wt.
Therefore, the algorithm substitutes the updated wt+1 into Eq.3 and obtain the new update on θ

_θt+1 = θt −_ _ηθF_ (θt)wt+1 (5)

where θt+1 satisfies Lval(θt+1) ≤Lval(θ[ˆ]t+1), that is, θt+1 have better validation performance than
_θˆt+1._

Finally, the algorithm repeatedly calculates Eq.3, 4 and 5 and alternately optimizes θ and w until
convergence.

3 NEW METHOD OF LEARNING THE PARAMETERS

In this section, we introduce a new method to learn the model parameter θ[∗] and weight w[∗] in Eq.1
and Eq.2. First, in Section 3.1, we propose to learn θ and w with a constraint, which can accurately
optimize θ and w. Then, in Section 3.2, we propose a combined method to train θ and w to make
the model parameter θ have better performance.

3.1 LEARNING WITH A CONSTRAINT

In the section, we first analyze the difficulty of solving θ[∗] and w[∗]. Gradient-based optimization is a
commonly used method in machine learning. Thus, we first need to calculate the gradient _θ_ _train_
_∇_ _L_
and _w_ _val. Based on Eq.2, we have_ _w_ _val = (_ _wθ[∗])[T]_ _θ∗_ _val. However, it is difficult to_
_∇_ _L_ _∇_ _L_ _∇_ _∇_ _L_
explicitly give the form of function θ[∗](w), resulting in ∇wLval cannot be calculated directly. The
previous work obtained the relationship between θ and w through the gradient descent process of
_θ, and only considered the influence of w on θ in a single gradient descent step. Based on this_
relationship, calculating the gradient and updating the parameter is not precise.

Here, we obtain the relationship between θ and w from a new perspective. First, we observe the
gradient _θ_ _train, that is,_
_∇_ _L_

_∇θLtrain = F_ (θ)w = c (6)


-----

**Algorithm 1: Learning to Weight Examples Using a Combination Method**
**Input : The network model parameter θ**
The weight of training examples w
Training set _train; Validation set_ _val_
_D_ _D_
The number of iterations of the combination method T
The number of iterations of our method T _[′]_

**1 Initialize model parameter θ and weight w**

**2 for t = 0 ... T −** 1 do

**3** Calculate the relationship between θ and w on Dtrain through Eq.3

**4** Optimize w on Dval through Eq.4

**5** Update θ through Eq.5

**6** **for t[′]** = 0 ... T _[′]_ _−_ 1 do

**7** Calculate the derivative ∇wθ on Dtrain through Eq.7

**8** Optimize w on Dval through Eq.8

**9** Update θ through Eq.9

**Output: Trained model parameter θ[∗]** and weight w[∗]

where c is the gradient value. We can see that changing the value of w can find corresponding θ to
satisfy Eq.6. It means that there is a functional relationship between θ and w in Eq.6. Because all
_θ and w satisfying this equation have the same value of_ _θ_ _train, we also call Eq.6 a constraint of_
_∇_ _L_
_θ and w. In particular, the optimal model parameter θ[∗]_ and w satisfy the constraint: F (θ[∗])w = 0.
Then, we can make use of the constraint to derive a precise relationship between θ and w. Our
network model may be very complex, and we cannot explicitly give the functional form of θ and w
according to the constraint. However, by applying the implicit function theorem, the derivative of θ
with respect to w in Eq.6 can be obtained as follow

_wθ =_ [ _θ(F_ (θ)w)][−][1]F (θ) = _H_ _[−][1]F_ (θ)
_∇_ _−_ _∇_ _−_

where H ∈ _R[K]_ _× R[K]_ is the Hessian matrix, namely, the second derivative of Ltrain with respect
to θ. However, calculating an exact Hessian matrix is very expensive. Especially nowadays network
models have a huge amount of parameters. In addition, in this case, we require the inverse of H,
rather than H itself. Therefore, we adopt diagonal approximation to evaluate H (Bishop, 2006).
In other words, we only need to calculate the diagonal elements of H. Furthermore, it is trivial to
calculate the inverse by taking the reciprocal of the diagonal elements. Let h ∈ _R[K]_ be the reciprocal
of the diagonal elements of H. Then, the derivative is evaluated as

_wθ =_ _diag(h)F_ (θ) (7)
_∇_ _−_

Next, we can make use of the derivative to calculate the gradient _w_ _val, and then update w and θ._
_∇_ _L_
The update process always satisfies the constraint of Eq.6, so we call it learning with a constraint.
Combining Eq.7, we have ∇wLval = −F (θ)[T] _diag(h)∇θLval. Thus, the update of w is_

_w[′]_ = w + ηw[′] _[F]_ [(][θ][)][T][ diag][(][h][)][∇][θ][L][val] (8)

where ηw[′] [is the step size. Then, we use the updated][ w][′][ to calculate the corresponding][ θ][′][ in the]
constraint. Since we do not know the explicit functional form of θ and w in Eq.6, we use the first
order derivative to approximate θ[′]. Combing Eq.7, θ[′] is evaluated as

_θ[′]_ _θ +_ _wθ(w[′]_ _w) = θ_ _diag(h)F_ (θ)(w[′] _w)_ (9)
_≈_ _∇_ _−_ _−_ _−_

Finally, under the condition of satisfying the constraint, we repeatedly optimize w and θ, corresponding to Eq.8 and Eq.9, until convergence. The detailed proof of this convergence can be found
in Theorem 1 in Appendix A.2.


3.2 LEARNING IN A COMBINED WAY AND IMPLEMENTATION

The method we proposed in Section3.1 still has a shortcoming. In the method, we make use of the
gradient ∇θLtrain of Eq.1 to obtain a constraint ∇θLtrain = c, and then calculate the solution of w
and θ under the constraint. However, this method only ensures that the solution is optimal in Eq.2


-----

under the constraint, and cannot guarantee that the solution of θ is optimal in Eq.1. Because our
method only use Eq.1 to obtain the constraint, but not to optimize θ for Eq.1, and when c ̸= 0, the
solution of θ is not optimal in Eq.1.

In order to calculate the better solution, our method needs to be combined with another algorithm
that can make θ reach the optimal in Eq.1. The method of Hu et al. in Section2 is a more appropriate
choice, rather than directly updating θ using the gradient _θ_ _train. Because it will first adjust w_
_∇_ _L_
and then update θ based on the new w. It is explained in Section2 that θ obtained in this way has a
better validation performance than θ directly using gradient descent.

Therefore, we propose a way to learn θ and w by combining our method in Section3.1 with the
method (Hu et al.) in Section2. In this way, we alternately use these two methods to learn θ and w.
In each iteration, we first update θ and w using the method (Hu et al.). It can make θ reduce the value
of Ltrain and approach the optimal in Eq.1, while θ also reduces Lval and perform well on validation
set. Then, we optimize θ and w using our method until convergence, so that θ further reduces _val_
_L_
and has the best verification performance among all θ with the same gradient _θ_ _train._
_∇_ _L_

This combined way can overcome the shortcomings of each method. On the one hand,the method
(Hu et al.) can use the gradient ∇θLtrain to update θ and make θ close to the optimal in Eq.1. It
makes up for the shortcoming that our method cannot optimize Eq.1. On the other hand, the method
(Hu et al.) only considers the influence of w on θ in a single gradient descent step, and then uses this
approximation to optimize Eq.2. Hence, θ obtained by the method (Hu et al.) may not be optimal for
Eq.2. Our method can make use of a constraint to derive an accurate functional relationship between
_θ and w. Thus, by optimizing θ through our method, a better solution can be obtained._

This combination algorithm is listed in Algorithm 1. It takes T iterations to alternately use two
methods to optimize θ and w. In t-th iteration, it first adopts the method (Hu et al.) to update w and
_θ (lines 3-5), and then it uses our method to optimize w and θ repeatedly T times (lines 6-9), making_
_θ converges under the current constraint. Finally, it outputs the trained model parameter θ[∗]_ and
weight w[∗]. The proof of convergence of the Algorithm 1 can be found in Theorem 2 in Appendix
A.2. In addition, we discuss the convergence rate of Algorithm 1. According to the conclusion in the
paper (Ren et al., 2018), when we take T steps to update the parameter θ through the method (Hu et
al.), it can achieve ∥∇θLval ∥≤O( _√[1]T_ [)][ where][ ∥∇][θ][L][val][ ∥] [is the update precision of parameter][ θ][.]

For the method in Section 3.1, achieving the same precision requires O(√T ) steps. More detailed

proofs are in Theorem 3 in Appendix A.3. Therefore, as the combined method, Algorithm 1 needs

3

_T × O(√T_ ) = O(T 2 ) to converge.

4 EXPERIMENTS

In this section, we perform extensive experiments to validate the effectiveness of our method. First,
we describe the experimental setup in detail. Second, we compare different methods in two domains:
text and image classification and in two situations: binary classification and multi-class classification. Third, we design experiments to study the performance of our method in different imbalance
ratios. Moreover, we evaluate the performance of our methods with different metrics on a large-scale
data set in Appendix A.1.

4.1 EXPERIMENTAL SETUP

**Models. We choose two network models for text and image classification. Specifically, in text**
classification, we use the BERT (base, uncased) model (Devlin et al., 2018) to extract the 768dimensional representation of text data (Xiao, 2018) and then use a simple 4-layer fully connected
network (FCN) for classification. The FCN model is given as Table 1. The pair of numbers in
brackets respectively indicate the sizes of input and output of the linear layer. In addition, the first
two layers apply rectified linear unit activation (ReLU) function to avoid the vanishing gradient
problem during training, and the third layer uses a nonlinear activation function (Tanh) to enhance
the model learning ability. The last layer is the classification layer, in which the size of output
depends on the number of classes in a classification task. In image classification, we use the ALLCNN-C network model that is a sequence of 9 convolution layers. Noting that our method does not
rely on the classification model, and can also be applied to other models.


-----

Table 1: The network model for text classification

Input 768-dimensional text representation

(768, 768) linear layer, ReLU
(768, 768) linear layer, ReLU
(768, 10) linear layer, Tanh
(10, size of labels) linear layer


Table 2: Description of four data sets

**Data sets** **Classes** **Fine-tune / Pretrain**

SST-2 2 2 × 500
SST-5 5 5 × 500
CIFAR10 10 10 × 4000
CIFAR100 2 0


**Data Sets and Model Preparation. We choose 4 data sets for text and image classification, and we**
use part of training examples in the data sets to prepare for the subsequent training of the models.
The information of the four data sets we used is shown in Table 2. In text classification, we use
two popular benchmark datasets. We use the SST-2 sentiment analysis benchmark (Socher et al.,
2013) for binary classification, and use the SST-5 sentence sentiment (Socher et al., 2013) with
5 categories for multi-class classification. In image classification, we adopt the commonly-used
CIFAR10 (Schneider et al., 2019) for multi-class classification experiment and select the examples
of class 0 and 1 from CIFAR100 (Schneider et al., 2019) to form a data set for binary classification.

To make subsequent experiments on strong models, we use part of training examples to fine-tune
the BERT and pre-train the ALL-CNN-C model respectively. In text classification, we use the text
data in a specific domain to fine-tune BERT, so that we can extract the better text representations
from the fine-tuned BERT and improve the performance of the FCN model. In image classification,
we first pre-train the ALL-CNN-C model using image data, and then the pre-trained model can be
helpful to improve downstream tasks for subsequent experiments. In Table 2, we list the number of
these examples. On SST-2 and SST-5 data sets, we take out 500 training examples of each class to
fine-tune the BERT model. For the experiments on CIFAR10, we use 4000 training examples per
class to pre-train the ALL-CNN-C model. In the experiments on CIFAR100, we do not pre-train the
model, because it can perform well on this binary classification task without pre-training. Noting
that the training examples used to improve the models will not be used in subsequent experiments.

**Comparison Methods. We compare our method with five approaches: (1) Baseline, a method**
without any processing. In other words, the classification model is directly trained on an imbalanced
training set. (2) Proportion, a commonly used method that weights examples by inverse class frequency. (3) Hu et al.’s, is the SOTA approach (Hu et al., 2019) for data weighting, which is described
in Section 2 and implemented using the code[1] provided by the authors. In addition, since we set a
small validation set in our experiments, the methods that need to be learned on the validation set are
easy to over-fit. Therefore, in the following methods, we add regularization for the model parameters in Eq.2. (4) Hu et al.’s+R, a method that adds regularization to the validation learning in the
method (Hu et al.). (5) Two-phase (Wahab et al., 2017), a learning method divided into two phases.
It first trains the model to learn a good classification representation on an imbalanced training set
and then adjusts the imbalance bias of the model by learning on a balanced validation set. When the
model is trained on the validation set, we also add regularization.

**Training and Evaluation. In our experiments, we first fine-tune the BERT model and pre-train**
the ALL-CNN-C model. In the following training, the text data is first converted into vector representations by BERT and then used to train the FCN model, and when training on CIFAR10, the
ALL-CNN-C model is initialized by the pre-trained model. Next, we apply different methods to
train the models. We divide this training process into 2 stages, and we take an imbalanced training
set and a small balanced validation set from the remaining training examples (not including the examples used for model preparation). In Stage 1, we only use the training set to train the models,
and the trained models can be regarded as the model initialization for subsequent training. For the
method (Hu et al.), the trained model has basic classification capabilities, so that it can use stable
gradient information to optimize the weights during weighting the examples (Ren et al., 2018). For
the two-phase method, Stage 1 corresponds to its first learning phase. In Stage 2, we train the models
according to their respective methods. Our method and the method (Hu et al.) will learn the model
and example weight using the training set and validation set together. For the two-phase method, we
only train the model on the balanced validation set, corresponding to its second phase. For Baseline
and Proportion, the models still learn on the training set.

1Code available at https://github.com/tanyuqian/learning-data-manipulation


-----

Table 3: Settings of the training process on 4 data sets

**Data sets** **Fine-tune / Pretrain** **Stage 1** **Stage 2**


Adam(5e-6)
SST-2 or SST-5 epochs:5
batch size:8

follow the training
CIFAR10
(Springenberg et al., 2014)


Adam(1e-2)
epochs:15
batch size:50

Adam(1e-6)
epochs:200
batch size:128


Adam(1e-2)
epochs:10
batch size:50

Adam(1e-5)
epochs:10
batch size:128

Adam(1e-4)
epochs:10
batch size:128


follow the training
CIFAR100 - 
(Springenberg et al., 2014)

Table 4: Results of six methods on four data sets


**SST-2** **SST-5** **CIFAR10** **CIFAR100**
**Methods**
**100:1000** **50:500** **50:500** **40:400**

Baseline 75.52 ± 2.99 40.24 ± 0.99 69.95 ± 3.35 85.00 ± 1.10
Proportion 79.59 ± 3.35 42.59 ± 1.12 79.58 ± 0.34 85.20 ± 1.21
Two-phase 81.99 ± 0.80 42.60 ± 1.44 79.63 ± 0.44 86.00 ± 1.61
Hu et al.’s 81.57 ± 0.74 39.82 ± 1.07 79.36 ± 0.51 85.40 ± 1.07
Hu et al.’s+R 82.25 ± 1.16 40.14 ± 0.39 79.55 ± 0.21 86.50 ± 2.41
**Ours.** **82.58 ± 0.98** **44.62 ± 1.08** **79.71 ± 0.37** **87.40 ± 1.66**

The settings of the training process on the four data sets are listed in Table 3. Each cell in the table
indicates the settings in the current stage, including the optimizer used, learning rate, number of
epochs, and batch size, where the value in brackets is the learning rate. In text classification, we use
Adam optimization. In image classification, we first follow the implementation of Springenberg et
al. to use SGD optimization, and then we use Adam to optimize in subsequent training.

Finally, we indicate the evaluation criteria and hyperparameters tuning. We use the accuracy on the
full test set of each data set to evaluate the performance of models. During the training process,
the final result may be over-fitting, so we record the best step corresponding to the highest accuracy
on the validation set. In addition, we also tune a series of hyperparameters for different methods
and report the best in the test set. For the method (Hu et al.), we follow (Hu et al., 2019) and set
the decay of weight to avoid exploding value. The decay value is selected from {1, 5, 10}. For
Hu+regularization, we set the learning rate for weight update, which is taken from {1, 1e-1, 1e-2,
1e-3}. For our method, we set the learning rate and epochs for updating the weights during learning
with constraint, and they are taken from {1e-2, 1e-3, 1e-4, 1e-5} and {1, 5, 10, 15, 30} respectively.
We adopt general regularization, namely Lp-norm (Bohra & Unser, 2020), for the methods that need
to be trained on the validation set. The value of p is selected from {2, 4, 6, 8}. The log value of
regularization coefficient is selected from {-4, ..., 4} for text data sets and {-4, ..., 9} for image data
sets. All experiments were implemented with Python 3.8 and PyTorch 1.8 and were evaluated on
a Linux server with RTX 3080 GPU and 128GB RAM. All results are averaged over 5 runs ± one
standard deviation.

4.2 RESULTS ON DIFFERENT DATA SETS

We compare the performance of different methods on the four data sets. The four data sets involve
text and image domains, as well as binary classification and multi-class classification scenarios.
They can more comprehensively reflect the performance of our method. In this experiment, we set
an imbalance ratio of 1:10, which is the ratio of the example size of the minority class to the majority
class. In all data sets, we set class 0 as the minority class, and the rest as the majority class. On
the four data sets, the size of training examples is different. We set the number of training examples
for each majority class of the data set SST-2, SST-5, CIFAR10, CIFAR100 to 1000, 500, 500, 400
respectively. In addition, for all data sets, the number of examples in the validation set is 10 for
each class. The training set and validation set are randomly selected from the remaining training
examples in each data set.


-----

Table 5: Results of different imbalance ratios on SST-2 data set

**Methods** **10:1000** **20:1000** **100:1000**

Baseline 49.92 ± 0.00 49.92 ± 0.00 75.52 ± 2.99
Proportion 60.63 ± 13.13 78.76 ± 2.40 79.59 ± 3.35
Two-phase 75.35 ± 8.90 80.52 ± 1.96 81.99 ± 0.80
Hu et al.’s 55.84 ± 11.84 73.61 ± 11.86 81.57 ± 0.74
Hu et al.’s+R 66.68 ± 13.99 79.53 ± 1.64 82.25 ± 1.16
**Ours.** **80.62 ± 0.93** **81.14 ± 1.25** **82.58 ± 0.98**

Table 6: Results of different imbalance ratios on CIFAR100 data set

**Methods** **4:400** **8:400** **40:400**

Baseline 64.40 ± 11.98 77.40 ± 12.23 85.00 ± 1.10
Proportion 60.50 ± 8.40 69.60 ± 8.56 85.20 ± 1.21
Two-phase 66.00 ± 13.95 79.50 ± 3.75 86.00 ± 1.61
Hu et al.’s 60.20 ± 8.19 69.10 ± 8.08 85.40 ± 1.07
Hu et al.’s+R 71.80 ± 11.73 82.50 ± 4.27 86.50 ± 2.41
**Ours.** **77.20 ± 3.75** **82.60 ± 3.87** **87.40 ± 1.66**

**Results The results on the four data sets are shown in Table 4. We can see that our method has**
the best performance in these 4 data sets. Especially on the SST-5 data set, our method exceeds the
second-best method by more than 2 accuracy points. It demonstrates that our method can perform
well in multiple domains and different classification scenarios. Hu et al.’+R and Two-phase are
competitive methods. On the SST-2 and CIFAR100, Hu et al.’+R is the second-best, and on the
SST-5 and CIFAR10, Two-phase also reaches the second-best. It shows that using a balanced data
set to simply adjust a biased model can also achieve good results. In addition, Hu et al.’+R performs
better than Hu et al.’s. on all data sets, and on the CIFAR100, it surpasses the latter by more than
1 accuracy point. It indicates that adding regularization to the validation learning can effectively
improve the method (Hu et al.). However, on the SST-5, the method (Hu et al.) performs worse than
the baseline, which may be due to the ineffectiveness of the approximation on SST-5. The accuracy
of the proportion method is lower than that of our method by more than 2 accuracy points on the
SST-2, SST-5, and CIFAR100. It shows that the method of learning weight has more advantages
than weighting empirically. The baseline method performs the worst on three data sets due to the
lack of measures to solve the imbalance.

4.3 RESULTS OF DIFFERENT IMBALANCE RATIOS

We study the performance of our method with different imbalance ratios. In this experiment, we
use the SST-2 and CIFAR100 data sets, and we vary the imbalance ratio from {1:10, 1:50, 1:100}.
The example size of majority classes in the training set and the validation set are consistent with the
setting of Section 4.2. In addition, the training set and validation set are also randomly constructed.

**Results Table 5 and Table 6 respectively shows the results of different imbalance ratios on SST-2**
and CIFAR100 data set. The results are listed in the order of imbalance ratios of 1:10, 1:50, 1:100.
There are three main observations. First, our method has achieved the highest accuracy rates in all
imbalance ratio settings. It further demonstrates that our method can have excellent performance in
different situations, such as slight imbalance, extreme imbalance, etc. Second, as the training data
becomes more imbalanced, the performance of our method is more dominant than other methods.
On the SST-2, the accuracy of our method exceeds the second-best method by about 0.3 at 100:1000
and more than 5 accuracy points at 10:1000. Similarly, on the CIFAR100, the accuracy of our
method improves the second-best method over 0.9 at 100:1000 and more than 6 accuracy points
at 10:1000. It shows that our method is more advantageous in extreme imbalance. Third, when
the imbalance ratios are 1:50 and 1:100, the accuracy rates of the proportion method are almost
lower than other imbalance classification methods. On the CIFAR100, the proportion method even
performs worse than the baseline. It indicates that as the data imbalance becomes serious, the
proportion method may not be effective. On the contrary, the advantage of the methods of learning
weights is more obvious.


-----

5 RELATED WORK

There have been very rich studies on weighting examples for imbalance classification, and these
studies can be grouped into two categories, namely empirical weighting and automatic weighting.

**Empirical Weighting. The empirical weighting methods assign the manual weight values to the ex-**
amples. Generally, the minority class example will be assigned a larger weight value than that of the
majority class, so as to relieve the bias of the model trained on the imbalanced data set. The methods
of weighting by class are first proposed (King & Zeng, 2001). In these methods, the examples of
each class are manually set to the same value, such as inverse class frequency (Wang et al., 2017;
Huang et al., 2016) or inverse square root of class frequency (Mikolov et al., 2013; Mahajan et al.,
2018). Cui et al. (2019) proposed to calculate the effective number of examples as class frequency
and then also use its inverse to weight examples and achieved significant improvements on longtailed training data. In addition, many methods of weighting by example have also been proposed.
Hard example mining (Shrivastava et al., 2016) thought focusing on the hard examples can improve
the model on the imbalanced data. Dong et al. (2017); Malisiewicz et al. (2011) proposed to utilize
the example loss to find hard examples and assign them higher weights. Lin et al. (2017) proposed
to use the predicted probability to calculate higher weights for the hard examples and dynamically
adjust the weight values during training. Empirical weighting is convenient to implement and can
achieve excellent performance, though it cannot adapt to different data sets and may cause poor
performance. In addition, manually setting weights will also increase the engineering burden.

**Automatic Weighting. The automatic weighting methods assign adaptive weights to the examples**
through learning mechanisms. Curriculum learning can provide an example weighting strategy for
neural network models to learn on corrupted labels (Jiang et al., 2018; Wei et al., 2021), but the
method focuses on examples that are easy to learn (Zhang et al., 2020). On the contrary, imbalance
learning prefers hard examples, so it is different from the methods of data weighting in imbalance
classification. Ren et al. (2018) proposed to learn the example weights by a meta-learning paradigm
(Zhang et al., 2021). This algorithm treats the example weights as a meta-learner and guides the
learner to learn on the imbalanced training set. The loss on the balanced validation set is used as
the meta-objective to optimize the example weights (Bai et al., 2021). In each iteration of updating
the weights, this algorithm uses a gradient descent step to approximate the relationship between the
weights and the learner. Hu et al. (2019) improved the algorithm by iteratively optimizing weights
instead of re-estimation at each iteration. Our work is based on the work of Ren and Hu et al. and
make further research. There is a key difference between our work and theirs. We use the model
optimization objective to derive the precise relationship between the model and weights, instead of
the local approximation strategy they used. Therefore, our algorithm can accurately optimize the
example weights and get a better model for imbalance classification. The massive experimental
results show that our algorithm makes significant improvements.

6 CONCLUSION

In this paper, based on the work of Ren and Hu et al., we further propose an improved algorithm
to learn the example weights for imbalance classification. In this algorithm, we propose a learning
mechanism that can accurately update the weights and the classification model under a constraint
and improves the validation performance of the model. This is a key improvement compared to
the method proposed by Ren et al. that uses the local approximation to optimize the weights. In
addition, the algorithm we proposed is a combination of our learning mechanism and the method
proposed by Hu et al., which can promote each other and make the model perform better. Finally,
the experimental evaluation shows that our algorithm can achieve significant improvement compared
with the SOTA method in data weighting and other imbalance methods. In our future work, we plan
to extend our algorithm and explore the performance of our algorithm in data augmentation.

**Acknowledgements.** This research was partially sponsored by the following funds: National
Key R&D Program of China (2018YFB1402800), Key Research Project of Zhejiang Province
(2022C01145), Fundamental Research Funds for the Provincial Universities of Zhejiang (RFA2020007) and Zhejiang Lab (2020AA3AB05).


-----

REFERENCES

Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming
Xiong. How important is the train-validation split in meta-learning? In International Conference
_on Machine Learning, pp. 543–553. PMLR, 2021._

CM Bishop. Pattern recognition and machine learning, m. jordan, j. kleinberg, and b. sch¨olkopf,
eds, 2006.

Pakshal Bohra and Michael Unser. Continuous-domain signal reconstruction using l {p}-norm regularization. IEEE Transactions on Signal Processing, 68:4543–4554, 2020.

Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based
on effective number of samples. In Proceedings of the IEEE/CVF conference on computer vision
_and pattern recognition, pp. 9268–9277, 2019._

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.

Qi Dong, Shaogang Gong, and Xiatian Zhu. Class rectification hard mining for imbalanced deep
learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1851–
1860, 2017.

[Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.](http://archive.ics.uci.edu/ml)
[ics.uci.edu/ml.](http://archive.ics.uci.edu/ml)

Mila Grancharova, Hanna Berg, and Hercules Dalianis. Improving named entity recognition and
classification in class imbalanced swedish electronic patient records through resampling. In
_Eighth Swedish Language Technology Conference (SLTC). F¨orlag G¨oteborgs Universitet, 2020._

Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural
networks: A survey. arXiv preprint arXiv:2004.05439, 2020.

Zhiting Hu, Bowen Tan, Ruslan Salakhutdinov, Tom Mitchell, and Eric P. Xing. Learning Data
_Manipulation for Augmentation and Weighting. Curran Associates Inc., Red Hook, NY, USA,_
2019.

Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for
imbalanced classification. In Proceedings of the IEEE conference on computer vision and pattern
_recognition, pp. 5375–5384, 2016._

Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels. In International Conference
_on Machine Learning, pp. 2304–2313. PMLR, 2018._

Gary King and Langche Zeng. Logistic regression in rare events data. Political analysis, 9(2):
137–163, 2001.

Chaoliang Li and Shigang Liu. A comparative study of the class imbalance problem in twitter spam
detection. Concurrency and Computation: Practice and Experience, 30(5):e4281, 2018.

Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Doll´ar. Focal loss for dense
object detection. In Proceedings of the IEEE international conference on computer vision, pp.
2980–2988, 2017.

Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li,
Ashwin Bharambe, and Laurens Van Der Maaten. Exploring the limits of weakly supervised
pretraining. In Proceedings of the European conference on computer vision (ECCV), pp. 181–
196, 2018.

Tomasz Malisiewicz, Abhinav Gupta, and Alexei A Efros. Ensemble of exemplar-svms for object
detection and beyond. In 2011 International conference on computer vision, pp. 89–96. IEEE,
2011.


-----

Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information pro_cessing systems, pp. 3111–3119, 2013._

Kemal Oksuz, Baris Can Cam, Sinan Kalkan, and Emre Akbas. Imbalance problems in object
detection: A review. IEEE transactions on pattern analysis and machine intelligence, 2020.

Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for
robust deep learning. In International Conference on Machine Learning, pp. 4334–4343. PMLR,
2018.

Frank Schneider, Lukas Balles, and Philipp Hennig. Deepobs: A deep learning optimizer benchmark
suite. arXiv preprint arXiv:1903.05499, 2019.

Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors
with online hard example mining. In Proceedings of the IEEE conference on computer vision and
_pattern recognition, pp. 761–769, 2016._

Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng,
and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment
treebank. In Proceedings of the 2013 conference on empirical methods in natural language pro_cessing, pp. 1631–1642, 2013._

Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for
simplicity: The all convolutional net. arXiv preprint arXiv:1412.6806, 2014.

Noorul Wahab, Asifullah Khan, and Yeon Soo Lee. Two-phase deep convolutional neural network
for reducing class skewness in histopathological images based breast cancer detection. Computers
_in biology and medicine, 85:86–97, 2017._

Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning to model the tail. In Proceedings
_of the 31st International Conference on Neural Information Processing Systems, pp. 7032–7042,_
2017.

Jerry Wei, Arief Suriawinata, Bing Ren, Xiaoying Liu, Mikhail Lisovsky, Louis Vaickus, Charles
Brown, Michael Baker, Mustafa Nasir-Moin, Naofumi Tomita, et al. Learn like a pathologist:
curriculum learning by annotator agreement for histopathology image classification. In Proceed_ings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 2473–2483,_
2021.

Gang Wu and Edward Y Chang. Class-boundary alignment for imbalanced dataset learning. In
_ICML 2003 workshop on learning from imbalanced data sets II, Washington, DC, pp. 49–56._
Citeseer, 2003.

[Han Xiao. bert-as-service. https://github.com/hanxiao/bert-as-service, 2018.](https://github.com/hanxiao/bert-as-service)

Lei Zhang, Yuehuan Wang, and Yang Huo. Object detection in high-resolution remote sensing
images based on a hard-example-mining network. IEEE Transactions on Geoscience and Remote
_Sensing, 2020._

Shen Zhang, Fei Ye, Bingnan Wang, and Thomas Habetler. Few-shot bearing fault diagnosis based
on model-agnostic meta-learning. IEEE Transactions on Industry Applications, 2021.

A APPENDIX

A.1 EXPERIMENTAL RESULTS WITH DIFFERENT METRICS

In this section, we evaluate the performance of our methods with different metrics on a large-scale
data set. In addition to the accuracy, we also adopt the Marco-F1 score and G-means that are often
used in imbalanced classification. In this experiment, we use an additional large-scale unbalanced
data set that is the operational data for Air Pressure System (APS) Failure at Scania trucks. The
settings and results of this experiment are as follows.


-----

Table 7: The network model for APS Failure
dataset

Input 171-dimensional examples

(171, 100) linear layer, ReLU
(100, 100) linear layer, Tanh
(100, 2) linear layer


Table 8: Description of APS Failure dataset

**Classes** **Train** **Validation** **Test**
**Set** **Set** **Set**

Negative 10000 1000 5
Positive 10 1000 5


Table 9: Results with different metrics on APS Failure dataset

**Methods** **Accuracy** **Marco-F1 score** **G-means**

Baseline 50.00 ± 0.00 33.33 ± 0.00 0.00 ± 0.00
Proportion 93.29 ± 2.59 93.27 ± 2.63 93.17 ± 2.78
Two-phase 93.19 ± 0.87 93.19 ± 0.87 93.15 ± 0.89
Hu et al.’s 94.09 ± 0.94 93.35 ± 1.73 93.28 ± 1.79
Hu et al.’s+R 93.98 ± 1.78 94.65 ± 0.76 94.65 ± 0.76
**Ours.** **94.49 ± 0.70** **95.10 ± 0.66** **94.86 ± 0.58**

**Dataset and Models. APS Failure dataset is from UCI Machine Learning Repository (Dua & Graff,**
2017). This dataset contains 76000 examples. We randomly construct the train, validation and test
data sets from the original data set. These sub-data sets are described in Table 8. The train set
consists of 10000 negative examples and 10 positive examples, which is extremely imbalanced, and
its imbalance rate reaches 1:1000. The validation and test sets are balanced data sets, and their
example sizes for each class are 5 and 1000 respectively. In addition, APS Failure dataset dataset
has 171 features, and we replace the missing feature values with the average of the examples in the
same class. Finally, we scale the all feature values to [0, 1]. The model for APS Failure dataset is
shown in Table 7 and is a simple 3-layer FCN.

**Other Settings.** During training, we use Adam optimization with an initial learning rate of 1e-2
and set the batch size to 128. Other hyperparameter settings are the same as the text classification in
Section 4.1.

**Results.** The results of different metrics on APS Failure dataset are shown in Table 9. There are
three main observations. First, our method achieves the best score in all metrics. It indicates that our
method has comprehensive advantages compared with other methods. Second, the score rankings
of the six methods are almost consistent among these metrics. It shows that the evaluation of these
metrics on a balanced test set is similar. Third, our method performs well on a large-scale data set.
It demonstrates that our method is also effective on large-scale data.

A.2 CONVERGENCE PROOF OF OUR METHOD

This section firstly provides a proof of the convergence of the learning method with a constraint in
Section 3.1, and then we prove the convergence of the combination method in Section 3.2.

**Definition 1. A function f** (x) : R[d] _→_ _R is said to be Lipschitz-smooth with constant L if_

_∥∇f_ (x) −∇f (y) ∥≤ _L ∥_ _x −_ _y ∥, ∀x, y ∈_ _R[d]_

**Definition 2. A function f** (x) has σ-bounded gradients if


_∥∇f_ (x) ∥≤ _σ, ∀x ∈_ _R[d]_

**Theorem 1. Suppose the validation loss function Lval is Lipschitz-smooth with constant L, and the**
_training loss function fi corresponding to the example xi has σ-bounded gradients and the Hessian_
_matrix H, namely, the second derivative of_ _train with respect to θ, is bounded by ρ. Let the_
2 _L_
_learning ratevalidation loss always decreases. More specifically, ηw[′]_ _t_ _[satisfies][ η]w[′]_ _t_ _[≤]_ _LN_ [2]σ[2]ρ[2][ . Then, after each iteration of the model parameter][ θ][, the]

_val(θt+1)_ _val(θt)_ (10)
_L_ _≤L_


-----

**Proof. The validation loss function Lval is Lipschitz-smooth, so we have**

_val(θt+1)_ _val(θt) + (_ _θ_ _val)[T]_ ∆θ + _[L]_ (11)
_L_ _≤L_ _∇_ _L_ 2 _[∥]_ [∆][θ][ ∥]


Let v = ( _θ_ _val)[T]_ ∆θ + _[L]2_

Then, substituting the∇ _L_ _θ update formula:[∥]_ [∆][θ][ ∥][. We can see that only] ∆θ = _wθ (w[ v]t[ ≤]+1_ [0][, there is]wt) and the[ L][val] w[(][θ][t] update formula:[+1][)][ ≤L][val][(][θ][t][)][.]
_∇_ _−_
_wt+1_ _wt = ηw[′]_ _t_ [(][∇][w][θ][)][T][ ∇][θ][L][val] [from Section 3.1 into][ v][, we have]
_−_

_v = (_ _θ_ _val)[T]_ _wθ (wt+1_ _wt) +_ _[L]_ _wt_ _[∇][w][θ][ (][w][t][+1]_ (12)
_∇_ _L_ _∇_ _−_ 2 _[∥]_ _[η][′]_ 2 _[−]_ _[w][t][)][ ∥]_

= _ηw[′]_ _t_ [(][∇][θ][L][val][)][T][ ∇][w][θ][(][∇][w][θ][)][T][ ∇][θ][L][val] [+][ Lη]w[′] _t_ _wθ(_ _wθ)[T]_ _θ_ _val_ (13)
_−_ 2 _∥∇_ _∇_ _∇_ _L_ _∥_

2
= ( _θ_ _val)[T]_ _wθ(_ _wθ)[T][ h]_ _[Lη]w[′]_ _t_ _wθ(_ _wθ)[T]_ _ηw[′]_ _t_ _[I]_ _θ_ _val_ (14)
_∇_ _L_ _∇_ _∇_ 2 _∇_ _∇_ _−_ _∇_ _L_

i

where I is the identity matrix.

2
Let S = _wθ(_ _wθ)[T][ h][ Lη]2wt[′]_ _wθ(_ _wθ)[T]_ _ηw[′]_ _t_ _[I]_, so v = ( _θ_ _val)[T]_ _S_ _θ_ _val. Next, we prove_
_∇_ _∇_ _∇_ _∇_ _−_ _∇_ _L_ _∇_ _L_

that S is a semi-negative definite matrix such that vi 0.
_≤_

We observe that in S, the term _wθ(_ _wθ)[T]_ is a symmetric and positive semi-definite matrix. We
_∇_ _∇_
use A to denote this term and define its eigendecomposition as A = Pdiag(λ)P _[−][1]_ where λ is a
vector composed of eigenvalues and λi 0 for all i. Substituting this eigendecomposition into S,
we have _≥_


_S = Pdiag(λ)P_ ( _[Lη]w[′]_ _t_

_[−][1]_ 2


_Pdiag(λ)P_ _[−][1]_ _−_ _ηw[′]_ _t_ _[I][)]_ (15)


= Pdiag( _[Lη]w[′]_ _t_


_λ ∗_ _λ −_ _ηw[′]_ _t_ _[λ][)][P][ −][1]_ (16)


where ∗ represents the hadamard product.

Therefore, in order to make S a semi-negative definite matrix, ηw[′] _t_ [must satisfies] _Lη2wt[′]_ 2 _λ[2]i_ _wt_ _[λ][i]_

2 _[−][η][′]_ _[≤]_
0 for all i, namely, 0 ≤ _ηw[′]_ _t_ _[≤]_ _Lλi_ [. Let][ λ][max][ =][ max][i][(][λ][i][)][, so finally][ η]w[′] _t_ [must satisfies]


0 _ηw[′]_ _t_
_≤_ _[≤]_


2

(17)
_Lλmax_


Further, we estimate the boundary of the scalar value λmax. In Section 2, we define a matrix
_F = (∇f1, ..., ∇fN_ ), where fi is the training loss function and N is the number of the training
examples. Since fi has σ-bounded gradients, we can obtain ∥ _F ∥≤_ _Nσ. Substituting ∇wθ in Eq._
7 into A, we have

_A_ = _wθ(_ _wθ)[T]_ = _diag(h)FF_ _[T]_ _diag(h)_ (18)
_∥_ _∥_ _∥∇_ _∇_ _∥_ _∥_ _∥_

_≤∥_ _diag(h) ∥∥_ _F ∥∥_ _F_ _[T]_ _∥∥_ _diag(h) ∥= N_ [2]σ[2]ρ[2] (19)

Since λmax is the eigenvalue of A, we can obtain

_λmax_ _A_ = N [2]σ[2]ρ[2] (20)
_≤∥_ _∥_

Therefore, combining Eq. 17 and Eq. 20, the satisfying range of ηw[′] _t_ [is]


0 _ηw[′]_ _t_
_≤_ _[≤]_

This finishes our proof for Theorem 1.


2

(21)
_LN_ [2]σ[2]ρ[2]


-----

**Theorem 2. Suppose the validation loss function Lval, the training loss function fi and the learning**
_rate ηw[′]_ _t_ _[satisfies Theorem 1 conditions. Same as Algorithm 1,][ t][ is denoted as the time step where]_
_the algorithm successively uses Hu et al. and our methods to update θ, and let t[′]_ _represent the time_
_step inside time-step t and the algorithm only apply our method to update θ. The range of t[′]_ _is_

[0, ..., T2 1]. Then the validation loss always decreases after the t-th iteration, namely,
_−_

_val(θt+1)_ _val(θt)_ (22)
_L_ _≤L_

**Proof.** The θt′=0 is the updated parameter through the method (Hu et al.). According to the
convergence theorem in the paper (Ren et al., 2018; Hu et al., 2019), we can obtain

_val(θt)_ _val(θt′=0)_ (23)
_L_ _≥L_

After that, we use our method to update the parameter T times. According to the Theorem 1, we
have

_Lval(θt′=0) ≥Lval(θt′=1) ... ≥Lval(θt′=T2−1)_ (24)

Here, the algorithm completes the update of the parameter in time-step t, namely, θt′=T2−1 = θt+1.
Combining Eq. 23 and Eq. 24, we can obtain

_val(θt+1)_ _val(θt)_ (25)
_L_ _≤L_

This finishes our proof of Theorem 2.

A.3 CONVERGENCE RATE OF OUR METHOD

This section provides a proof of the convergence rate of the learning method with a constraint in
Section 3.1.

**Theorem 3. Suppose the validation loss function Lval, the training loss function fi and the learn-**
_ing rate ηw[′]_ _t_ _[satisfies Theorem 1 conditions. Then the learning method in Section 3.1 achieves]_
_∥∇θt_ _Lval ∥≤_ _ϵ in O(_ [1]ϵ [)][ steps, namely,]


min
0<t<T _T_

_[∥∇][θ][t]_ _[L][val][ ∥≤]_ _[C]_


(26)


_where C is some constant_


**Proof. According to Eq. 11 and Eq. 14 in Theorem 1, we can obtain**

_val(θt+1)_ _val(θt)_ ( _θt_ _val)[T]_ _St_ _θt_ _val_ (27)
_L_ _−L_ _≤_ _∇_ _L_ _∇_ _L_

where St is the matrix S at time-step t and S is defined in Theorem 1.

Then we have

_T_

( _θt_ _val)[T]_ _St_ _θt_ _val_ _val(θT +1)_ _val(θ0)_
_t=0_ _∇_ _L_ _∇_ _L_ _≥L_ _−L_

X

_val(θ[∗])_ _val(θ0)_ (28)
_≥L_ _−L_

where _val(θ[∗]) is the minimum of function_ _val(θ). Then, we can observe that there exist a time-_
_L_ _L_
step 0 ≤ _τ ≤_ _T such that,_

_T_ ( _θτ_ _val)[T]_ _Sτ_ _θτ_ _val_ _val(θ[∗])_ _val(θ0)_ (29)
_∇_ _L_ _∇_ _L_ _≥L_ _−L_

We have proved that Sτ is a semi-negative definite matrix. According to Eq. 16, we have

_Sτ = Pdiag(λ[′])P_ _[−][1]_ = Pdiag(λ[′])P _[T]_ (30)


-----

where λ[′] is a vector composed of eigenvalues and λ[′]i
eigenvectors of A in Theorem 1 and P _[−][1]_ = P _[T]_ because[≤] A[0] is a symmetric matrix. Substituting Eq.[ for all][ i][.][ P][ is the matrix composed of]
30 into Eq. 29, we have

_val(θ[∗])_ _val(θ0)_ _T_ ( _θτ_ _val)[T]_ _Pdiag(λ[′])P_ _[T]_ _θτ_ _val_ (31)
_L_ _−L_ _≤= T_ (∇P _[T]_ _Lθτ_ _val)T diag(λ′)P T∇_ _θ Lτ_ _val_ (32)

_T_ (P _[T]_ _∇θτ Lval)T λ′max[IP][ T][ ∇] ∇[θ]τ_ _L_ (33)
_≤_ _∇_ _L_ _[L][val]_

= Tλ[′]max _τ_ (34)

_[∥∇][θ]_ _[L][val]_ _[∥]_


We can regard Eq. 32 as the quadratic form of the diagonal matrix diag(λ[′]), and we scale all the
eigenvalues λ[′]i [to][ λ]max[′] [where][ λ]max[′] [= max][i] _[λ][′]i[, so that we obtain the inequality in Eq. 33.]_

So we have


_val(θ[∗])_ _val(θ0)_
_L_ _−L_ = _[C]_

_λ[′]max_ _T_


_∥∇θτ Lval ∥≤_ _T[1]_


(35)


where C = _[L][val][(][θ][∗]λ[)][′]max[−L][val][(][θ][0][)]_ is a constant independent of T .

Therefore, we can obtain min0<t<T _T_ [. It means that our method can]

_[∥∇][θ][t]_ _[L][val][ ∥≤∥∇][θ][τ][ L][val][ ∥≤]_ _[C]_

achieve min0<t<T _T_ [)][ in][ T][ steps. This finishes our proof of Theorem 3.]

_[∥∇][θ][t]_ _[L][val][ ∥≤O][(][ 1]_


-----

