A Gradient-based Approach for Online Robust Deep Neural Network Training
  with Noisy Labels
Learning with noisy labels is an important topic for scalable training in
many real-world scenarios. However, few previous research considers this
problem in the online setting, where the arrival of data is streaming. In this
paper, we propose a novel gradient-based approach to enable the detection of
noisy labels for the online learning of model parameters, named Online
Gradient-based Robust Selection (OGRS). In contrast to the previous sample
selection approach for the offline training that requires the estimation of a
clean ratio of the dataset before each epoch of training, OGRS can
automatically select clean samples by steps of gradient update from datasets
with varying clean ratios without changing the parameter setting. During the
training process, the OGRS method selects clean samples at each iteration and
feeds the selected sample to incrementally update the model parameters. We
provide a detailed theoretical analysis to demonstrate data selection process
is converging to the low-loss region of the sample space, by introducing and
proving the sub-linear local Lagrangian regret of the non-convex constrained
optimization problem. Experimental results show that it outperforms
state-of-the-art methods in different settings.
Yifan Yang, Alec Koppel, Zheng Zhang
# A Gradient-based Approach for Online Robust Deep Neural Network Training with Noisy Labels

###### Abstract

Learning with noisy labels is an important topic for scalable training in many real-world scenarios. However, few previous research considers this problem in the online setting, where the arrival of data is streaming. In this paper, we propose a novel gradient-based approach to enable the detection of noisy labels for the online learning of model parameters, named Online Gradient-based Robust Selection (OGRS). In contrast to the previous sample selection approach for the offline training that requires the estimation of a clean ratio of the dataset before each epoch of training, OGRS can automatically select clean samples by steps of gradient update from datasets with varying clean ratios without changing the parameter setting. During the training process, the OGRS method selects clean samples at each iteration and feeds the selected sample to incrementally update the model parameters. We provide a detailed theoretical analysis to demonstrate data selection process is converging to the low-loss region of the sample space, by introducing and proving the sub-linear local Lagrangian regret of the non-convex constrained optimization problem. Experimental results show that it outperforms state-of-the-art methods in different settings.

## 1 Introduction

Online learning is a widely used learning framework for streaming data in many real-world scenarios. In recent years, online training of deep neural networks (DNNs) has garnered increased attention to enable large-scale training [1; 2; 3], to face the challenge of increasingly large datasets. Such a large-scale training process of DNNs, especially online DNNs training, is highly sensitive to the noisy labels in the datasets [4], which is more pronounced with the streaming and dynamically changing online data.

The noisy label problem refers to the presence of incorrect or mislabeled annotations in a training dataset. Usually, the data samples with incorrect labels are defined as noisy data, and the correct one is called clean data. This issue has been identified as a common challenge in many datasets. For instance, researchers in [5] found 6% label errors in the Imagenet validation set and 10% label errors in the QuickDraw dataset. Similarly, up to 30% label errors were found in the Google Emotions
dataset [6] and 37% errors in the MS COCO dataset [7]. Label errors vary across different datasets and appear with varying probabilities of occurrence in data streams at different time slots.

In recent years, the robustness issue of training with noisy labels has been widely studied in different research areas [4, 8, 9]. Among various approaches, sample selection methods enjoy the flexibility to support any type of deep learning architecture and do not need to maintain additional neural networks. The concept of multi-round sample selection for scalable models was first introduced in [10], where the authors proposed an iterative training loss minimization (ITLM) method that leverages samples selected at the beginning of each training epoch. Building on this idea, INCV [11] employs cross-validation to detect noisy training data and remove large-loss samples. O2U-Net [12] first repeats the entire training process to collect loss statistics, then retrains the neural network from scratch only with clean samples detected. These works proposed different methods to estimate the ratio of a dataset and using sorting methods to filter out noisy data based on that ratio, but they all follow the same idea of detecting clean samples based on a fixed pre-estimated scale parameter, which is hard to be set for streaming online datasets with changing clean ratios.

In this paper, we introduce **On**line **G**radient-based **R**obust **S**election (**OGRS**), a novel gradient-based multi-iteration sample selection approach that enables the online training of DNNs with dynamically changing proportions of noisy labels. Since clean data normally produces much lower training loss compared to noisy data based on the observations in [10], our proposed method capitalizes on the significant disparity in the gradient of the training loss at the clean and noisy data points respectively, which initially updates the data selection towards the clean region. To prevent the risk of overfitting, which may arise from the repeated selection of the same samples, we additionally propose a constraint function to mitigate the overlap of selected data. As a result, we formulate the problem as a non-convex constrained optimization problem. This structure enables our approach to dynamically adapt to varying noise proportions, thereby boosting the robustness of the online DNNs training against noisy labels.

In the realm of non-convex constrained optimization, a critical unresolved issue pertains to providing a theoretical guarantee for convergence analysis. Since the recent decade, gradient descent optimization methods have been widely used to solve a wide variety of problems, like the controls of robotic systems [13], bayesian inference [14], recommendation systems [15, 16] and the training of DNNs [17, 18, 19, 20, 45]. While [21] studied the constrained non-convex optimization problem using quadratic approximations, a straightforward analysis for this problem remains elusive due to the computational intractability of minimizing standard regret in non-convex cases. To address this challenge, we introduce a new metric for non-convex constrained optimization, termed local Lagrangian regret. We conduct a detailed theoretical analysis to validate our approach and show that a constant number of updating steps ensure our method finds a balance between the sample selection performance and the computation expense.

In the subsequent experimental evaluation, we incrementally input data selected by the OGRS method into various online training models. These results are then benchmarked against state-of-the-art methods to demonstrate the effectiveness of our approach. In general, our main contributions are summarized below:

* We introduce a novel gradient-based sample selection approach designed to facilitate effective online DNNs training with dynamically varying clean ratios.
* We define a new local Lagrangian regret for the non-convex optimization problem and propose an efficient algorithm that is specifically tailored to address the sample selection problem.
* We give a way for theoretical proof of the effectiveness and efficiency of our sample selection methods with our newly defined regret metric.
* We conduct experiments by simulating real-world online training cases and make comparisons between different sample selection methods.

## 2 Related Work

In this section, we review related work in the areas of learning with noisy labels and online DNNs training. Over the past decades, numerous deep-learning techniques have been developed to tackle the noisy label problem. These techniques are primarily grouped into five categories [4].
The first group of methods encompasses sample selection, which includes techniques of multi-network learning and multi-round learning. The multi-network learning involves the mentor network in the case of collaborative learning and multi-network learning in the case of co-training. For instance, [22] trained multiple DNNs simultaneously, with updates based solely on disagreements between different DNNs. On the other hand, MentorNet [23] employs a mentor network to guide the training of the student network. Multi-round learning, another sample selection method, refines a selected set of clean samples at the start of each epoch [10, 12]. Alongside methods using the small-loss trick [10, 12] introduced in the previous section, others improve the system efficiency using a single round refinement, like [24] and [25]. These techniques do not require the maintenance of additional DNNs, hence providing flexibility across various model architectures. In this paper, we mainly compare our results with the ITLM method in [10], since it refines the selection set for each epoch with the small-loss trick, which is the most suitable type of related method for online robust training. The other results, like [24], only do a single-time selection, it naturally unsuitable for the online setting.

Additionally, certain studies have sought to design robust architectures that incorporate a noise adaptation layer at the top of the training model. Recently, such methods have been adapted to handle noisy labels [26, 27]. Webly learning, for instance, uses the confusion matrix to initialize the weights of the noise adaptation layer [27]. In [28, 29], researchers designed robust policy gradient descent methods to deal with model uncertainties. Other methodologies include robust regularization [30, 31], robust loss function [32, 33], and closed-loop control [34]. Furthermore, it has been proven that designing a robust loss function for noisy data can approach the Bayesian optimal classifier [35]. Loss adjustment, instead of designing a new robust loss function, modifies the loss for all examples prior to the training process.

While some studies have considered online DNNs training [1, 36, 37] and robust optimization [38, 39], none have explored the problem of training with noisy labels. The inherent difficulty of online robust training lies in the dynamic nature of data streams. Existing techniques are unfit for the online scenario as it is computationally intractable to consistently modify parameters in traditional training techniques with noisy labels, such as sample selection and robust architecture. Hence, the new gradient-based sample selection method without the need for such pre-defined parameters is introduced in this paper.

## 3 Framework and Preliminaries

In this section, we introduce the general framework for the multi-round robust training of DNNs in an online setting with time slots \(t\in[1,T]\). During the training process, the online streaming data arrives at the training set \(\mathcal{D}_{t}\) at each time slot \(t\), where \(\mathcal{D}_{t}=(d_{1},y_{1}),\cdots,(d_{t},y_{t})\) consists of a series of data pairs \((d_{t},y_{t})\). For a single data pair \((d_{t},y_{t})\), \(d_{t}\in\mathbb{R}^{d}\) denotes the \(d\)-dimensional input features, and \(y_{t}\in\mathbb{R}^{C}\) represents the corresponding label for \(d_{t}\). Since we consider the training problem with noisy data, there exists a proportion of \(\phi_{t}\) labels that are mistaken in \(\mathcal{D}_{t}\) at the time slot \(t\).

### Problems in Directly Transferring Previous Method into Online Setting

The multi-round sample selection problem considered in this paper is a traditional problem that has been widely studied since [40], which contains two parts: (1) how to select a clean sample set \(S_{t}\) (2) how to use \(S_{t}\) to train a neural network with parameters \(\theta_{t}\). In Fig. 1, we summarize the workflow of the multi-round sample selection problem for a single time slot \(t\), where data pair \((d_{t},y_{t})\) arrives at \(\mathcal{D}_{t}\) and the sample selection algorithm select sample set \(S_{t}\) with the loss information provided by the training model to update the model parameter \(\theta_{t}\).

In this subsection, we will show that directly transferring some traditional sample selection methods like ITLM [10] in an online training setting didn't work well. To fit the ITLM into an online training

Figure 1: Workflow for the OGRS
framework, we need iteratively refines the clean set \(S_{t}\) at the beginning of each time slot \(t\). Since data with mistaken labels usually have high training loss based on observations. We sort all data samples \(d\in\mathcal{D}_{t}\) based on their training loss \(\ell_{\theta_{t}}(d)\) in their ITLM method. Then, the clean set \(S_{t}\) is selected by trimming the top \(1-\hat{\phi}_{t}\) proportion of the sorted data list, where the pre-known clean ratio \(\phi_{t}\) can be estimated by some techniques like crossed-validation [41, 42] before starting the sample selection at each time \(t\). Since there should have a total number of \(t\) samples in \(\mathcal{D}_{t}\) at time slot \(t\), this process can be formulated as:

\[S_{t}\leftarrow\operatorname*{arg\,min}_{S:|S|=\lfloor\phi_{t}t\rfloor}\sum_ {d_{i}\in S}\ell_{\theta_{t}}(d_{i}), \tag{1}\]

To update \(\theta_{t}\) with the clean set \(S_{t}\), the following optimization problem is solved in their training process:

\[\theta_{t+1}:=\operatorname*{arg\,min}_{\theta}\ell_{\theta_{t}}(s_{i}), \tag{2}\]

where \(s_{i}\in S_{t}\) is a batch of \(K\) data samples stochastically sampled from the clean set \(S_{t}\). Even though the online ITLM idea may work, it is obvious that directly transferring the previous method into the online setting is computationally intractable since we need to re-estimate the clean ratio at the beginning of each iteration.

### Problems for Using Traditional Local Regret Metric in Our Method

For the sample selection part of our method, instead of using the sorting method in the ITLM, we introduce a novel sample selection algorithm based on a non-convex constrained gradient descent algorithm. To select \(k\)-th data sample \(d_{t,k}\) in the clean sample set \(S_{t}\) at time slot \(t\), we run the constant number of gradient descent steps with iterations \(i\in[1,M]\). Thus, by repeatedly running this selecting process for \(K\) times, we can directly obtain a set of \(S_{t}=\{d_{t,1},\cdots,d_{t,K}\}\).

To illustrate the idea of local regret metric in [43], we focus on the updating process for selecting a single data \(d_{t,k}\), which bypasses a series of decisions \(d^{1},\cdots,d^{M-1},d^{M}_{t,k}\). To derive the local regret, we can gauge the average loss \(L_{t,w}(d^{i}_{t})\) of current \(w\) time slots loss values via a sliding window, which keeps track of the algorithm performance at the point of the current decision \(d^{i}_{t}\) at the iteration \(i\). The definition for the \(w\)-local regret is established by summing up the average gradient of the local loss over a total of \(M\) rounds, as described in the following equation:

\[R_{w}(M):=\sum_{i=1}^{M}\|\nabla L_{t,w}(d^{i}_{t})\|^{2}, \tag{3}\]

where the averaged local loss can be calculated by \(L_{t,w}(d^{i}_{t}):=\frac{1}{w}\sum_{j=0}^{w-1}\ell_{t-j}(d^{i}_{t})\). Besides the new definition of local regret, Hazan also proposed efficient new algorithms with the local loss and gives a sublinear local regret bound in their theoretical analysis.

Nevertheless, the original local regret metric was designed to address the unconstrained non-convex optimization problem. We cannot directly apply this setting to our sample selection problem, as we need to incorporate a constraint function to prevent the oversampling of certain samples.

## 4 Algorithms

As previously outlined, we have introduced the overall structure of our online robust training system designed for handling noisy labels. In this section, we will delve into more detailed discussions of the two main parts of the OGRS method, the sample selection process, and the model training aspects.

### Gradient-based Sample Selection

The key component of the OGRS is selecting the set of clean samples \(S_{t}\) at the beginning of each time slot \(t\). In order to obtain \(S_{t}\), we repeat the updating steps for selecting a single low-loss sample \(d_{t,k}\) for \(K\) times, where the updating steps \(d^{1},d^{2},\cdots,d^{M-1}\) toward the final choice \(d_{t,k}\) employ a modified constrained gradient descent method. Detail of the gradient-based sample selection algorithm can be found in Alg. 1.
To deal with the non-convex loss function, we use the local loss \(L_{t,w}(d)\) introduced in Sec. 3.2. In order to avoid repeatedly selecting the same samples, a global constraint function \(g^{i}_{t}\) is set as the difference between the total number of selected times for a sample \(d^{i}_{t}\) and a threshold \(\zeta\):

\[g^{i}_{t}(d^{i}_{t})=p^{i}_{t}(d^{i}_{t})-\zeta, \tag{4}\]

where \(p^{i}_{t}\) indicates the total number of times that \(d^{i}_{t}\) has been selected at the time slot \(t\) and iteration \(i\). \(\zeta\) is the maximum allowance for the repeat times. As a result, we can model the sample selection part as a constrained optimization problem:

\[d_{t,k}\in\operatorname*{arg\,min}_{d\in\mathcal{D}_{t}}L_{t,w}(d)\quad s.t. \quad g^{i}_{t}(d^{i}_{t})\leq 0 \tag{5}\]

To simplify the proof, we ignore the time slot \(t\) and only focus on a single optimization problem with iteration \(i\in[1,M]\) in the following part of this section. A widely used approach to solve the constrained optimization problem is to build the Lagrangian function that associates the loss with the constraints through a dynamically updating Lagrangian multiplier \(\mu^{i}\in R^{+}\)[44]. To enable the non-convex constrained optimization problem, we introduce a Lagrangian function built on the local loss instead, called local Lagrangian:

\[\mathcal{L}^{i}_{w}(d^{i},\lambda^{i})=L_{w}(d^{i})+(\mu^{i})^{\top}g^{i}(d^{ i}) \tag{6}\]

To optimize the local Lagrangian, we introduce a modified saddle point approach, which updates decision \(d^{i}\) in the primal update and \(\mu^{i}\) in the dual update. Thus, the sample \(d^{i+1}\) can be updated as the minimizer of the following optimization problem:

\[\min_{d\in\mathcal{D}_{t}}\nabla^{\top}L^{i}_{w}(d-d^{i})+(\mu^{i+1})^{\top}g ^{i}(d)+\frac{\|d-d^{i}\|^{2}}{2\alpha}, \tag{7}\]

where \(\frac{\|d-d^{i}\|^{2}}{2\alpha}\) is an added regularizer and \(\alpha\) is the positive stepsize. As the current decision \(d^{i}\) is revealed, the Lagrangian multiplier is updated based on the observation of \(g^{i}(d^{i})\) as:

\[\mu^{i+1}=\left[\mu^{i}+\gamma g^{i}\left(d^{i}\right)\right]^{+} \tag{8}\]

To provide the theoretical guarantee of the non-convex constrained optimization algorithm, we introduce the novel local Lagrangian regret, which is defined by combining the gradient of the local loss and the constraints. The idea of the local Lagrangian regret comes from the Karush-Kuhn-Tucker (KKT) stationary conditions, as:

\[RL=\|\sum_{i=1}^{M}\nabla L_{w}(d^{i})+(\mu^{i})^{\top}\nabla g^{i}(d^{i})\| \tag{9}\]

We will show later that the proposed local Lagrangian regret can help us better understand the theory of our sample selection method. One thing that needs to be noted. Different from the traditional setting of an optimization problem that iterates the gradient descent until the current decision is close enough to the optimal decision, we only run our algorithm for constant steps. The constant steps of updates help us to reduce the over-fitting problem during the training process and are enough to guarantee a sample loss below a certain threshold.

### Online Model Training

After we select \(S_{t}\) by using the proposed method. We update the model parameters \(\theta_{t}\) by solving the following optimization problem:

\[\theta=\operatorname*{arg\,min}_{\theta}\min_{\mathcal{S}_{t}}\sum_{t=1}^{T} \sum_{s\in\mathcal{S}_{t}}\ell_{\theta}(s) \tag{10}\]

These processes can be conducted by some widely used optimization methods, like the stochastic gradient descent (SGD) or the alternating direction method of multipliers (ADMM). The detail of the training process is summarized in Alg. 2.
```
0:loss function \(\ell_{\theta_{t}}(\cdot)\) of recent \(w\) iterations, dataset \(\mathcal{D}_{t}\), repeat threshold \(\zeta\)
0:\(S_{t}\)
1:for\(k\in[1,K]\)do
2:for\(i\in[1,M]\) epoch do
3: Update the selected sample \(d^{i}\) by minimizing the following optimization problem: \[\min_{d\in\mathcal{D}_{t}}\nabla^{\top}L_{t,w}^{i}(d-d_{t}^{i})+(\mu_{t}^{i+1} )^{\top}g_{t}^{i}(d)+\frac{\|d-d_{t}^{i}\|^{2}}{2\alpha},\] (11)
4: Observe the constraint violation \(g_{t}^{i}(d_{t}^{i})\), where: \[g_{t}^{i}(d_{t}^{i})=p_{t}^{i}(d_{t}^{i})-\zeta\] (12)
5: Update the dual variable \(mu_{i+1}\) by the following equation: \[\mu_{t}^{i+1}=[\mu_{t}^{i}+\gamma g_{t}^{i}(d_{t}^{i})]^{+}\] (13)
6: Append sample \(d^{M}\) in \(S_{t}\)
7: Return selected dataset \(S_{t}\)
```

**Algorithm 2** Online Gradient-based Robust Training

```
0:dataset \(\mathcal{D}_{t}\)
0:model parameter \(\theta_{t}\)
1:Initialize the model parameters \(\theta_{0}\)
2:for\(t=1,\cdots,T\)do
3:\(S_{t}=\) Algorithm 1\((\mathcal{D}_{t},\theta_{t})\)
4: Update model parameter \(\theta_{t}\) according to \(S_{t}\)
```

**Algorithm 3** Online Gradient-based Algorithm

## 5 Theoretical Analysis

In this section, we present a theoretical analysis of the sample selection component of the OGRS, demonstrating the reliability of our method via local Lagrangian regret. We focus specifically on the process of selecting a single sample \(d_{t,k}\) at time \(t\). Note that the optimization strategy outlined in eq. (5), aimed towards the optimal, may be overly ambitious for sample selection and could potentially lead to severe overfitting issues. Consequently, we limit ourselves to a constant number of total iterations \(M\) and show that constant \(M\) can also give a guarantee of maximum Lagrangian residual.

Next, we first establish the regret bound in a general scenario tied to \(M\). Subsequently, we delve into further exploration with a fixed setting of \(M\), illustrating our method's performance. This approach is akin to setting a threshold for the maximum sample loss, a concept that aligns with previous sample selection methods that leverage the clean ratio to manage this threshold. However, we can directly use OGRS on different tasks without necessitating the configuration of specific parameters.

Before presenting the local regret bound for the Lagrangian Residual, we first enumerate some frequently employed assumptions.

**Assumption 1**.: (Bounded gradient) For every iteration \(i\), both \(L_{t,w}(d)\) and \(g^{i}(d)\) are bounded and have bounded gradient, which is given as \(|L_{t,w}(x)|\leq F\), \(|\nabla L_{t,w}(x)|\leq F_{1}\), \(|g^{i}(d^{i})|\leq G\), \(\left|\nabla g^{i}(x)\right|\leq G_{1}\), \(\left|\nabla^{2}g^{i}(x)\right|\leq G_{2}\)

**Assumption 2**.: (Lipschitz continuous) The averaged loss function \(L_{w}\) and the constraints \(g^{i}\) are Lipschitz smooth, so its derivatives are Lipschitz continuous with constant \(L_{1}\) and \(L_{2}\), i.e., for two real vector \(d_{i},d_{j}\in\mathcal{D}_{t}\), we have:

\[\left|L_{w}(d^{i})-L_{w}(d^{j})\right| \leq L_{1}\|d_{1}-d_{2}\| \tag{14}\] \[\left|g^{i}(d^{i})-g^{i}(d^{j})\right| \leq L_{2}\|d_{1}-d_{2}\| \tag{15}\]

**Assumption 3**.: (Bounded decision set) The sample set \(\mathcal{D}_{t}\) is bounded, which means for some constant \(D\) and any \(d^{i},d^{j}\), we have \(\|d^{i}-d^{j}\|<D\)
**Assumption 4**.: (Salter Condition) There exists some positive constant \(\epsilon\) and an interior point \(d\in\mathcal{D}\), such that \(g^{i}(d)\leq-\epsilon\mathbf{I}\).

Assumptions 1 are broadly employed in the non-convex optimization community. Assumption 2 is crucial to ensure the validity and reasonableness of our analyses. Moreover, the Slater condition in assumption 4 is instrumental in establishing the boundary of the Lagrangian multiplier. We begin by establishing a bound for the norm of Lagrangian multiplier \(\|\mu^{i}\|\), as outlined in the following two lemmas:

**Lemma 5**.: _Let \(i_{0}\) be some arbitrary integer and \(\theta\) be some real constants. For \(i\in[1,M]\), the following bound holds:_

\[|||\mu^{i+1}\|-\|\mu^{i}\|\leq G\gamma \tag{16}\] \[|||\mu^{i+i_{0}}\|-\|\mu^{i}\|\|\leq-\frac{\epsilon i_{0}}{2}, \tag{17}\]

_when \(\|\mu^{i}\|\geq\frac{\gamma^{2}G^{2}}{\epsilon}+\frac{4\gamma F_{1}D}{ \epsilon}+\frac{D^{2}}{2\alpha\epsilon}\)_

Proof.: The detail of the proof can be found in Appendix A. 

Subsequently, we establish the bound for the norm of the Lagrangian Multiplier with lemma 5.

**Lemma 6**.: _Let Assumption 4 be satisfied. For the Lagrangian multiplier \(\mu^{i}\), we can bound its norm as:_

\[\|\mu^{i}\|\leq\frac{M^{-\frac{1}{2}}G^{2}}{\epsilon}+\frac{4M^{-\frac{1}{2}} F_{1}D}{\epsilon}+\frac{D^{2}}{2\alpha\epsilon}+i_{0}GM^{-\frac{1}{4}}+i_{0} \frac{8G^{2}M^{-\frac{1}{2}}}{\epsilon}\log[\frac{32G^{2}M^{-\frac{1}{2}}}{ \epsilon^{2}}] \tag{18}\]

Proof.: The detail of the proof can be found in Appendix B. 

Finally, we proceed to present the proof of the local Lagrangian residual regret. Commencing from the stationary condition in the KKT conditions, we individually bind the components associated with the gradient of the loss function and the constraints. This procedure brings us to the subsequent Theorem:

**Theorem 7**.: _Let \(L_{t,w}\) be the local loss function and \(g^{1},\cdots,g^{M}\) be the constraint functions in Alg. 1 and all assumptions satisfied. Set \(H^{i}=\nabla L_{w}+\mu^{i}\nabla g^{i}(d^{i})\) and involving the results in lemma 6, we have:_

\[RL(M)=\|\sum_{i=1}^{M}\nabla L_{w}+(\mu^{i})^{\top}\nabla g^{i}(d^{i})\|\leq \mathcal{O}(M^{\frac{1}{2}}) \tag{19}\]

_where \(M\) is the maximum number of the constraints functions_

Proof.: The detail of the proof can be found in Appendix C. 

**Remark:** From Theorem 7, it is evident that the sample selection algorithm can attain a \(\mathcal{O}(M^{1/2})\) local regret bound. This implies that the Lagrangian function may converge to zero when \(M\) is sufficiently large. However, ensuring full convergence of the Lagrangian isn't suitable for our sample selection objectives. Instead, we restrict the maximum iterations in our algorithm to \(M_{max}\), thereby setting a limit on the local Lagrangian regret with a threshold of \(\mathcal{O}(\sqrt{M_{max}})\). This aligns partially with previous sample selection methods that use the task-specific estimated clean ratios as thresholds to differentiate 'good' and 'bad' samples. Notably, our OGRS method eliminates the need for such specifications. With a fixed maximum iteration setting, OGRS can handle tasks with diverse noisy training data or especially online training tasks with dynamically changing clean ratios.
## 6 Experimental Results

In this section, we evaluate the performance of our proposed OGRS method. As other multi-round sample selection algorithms utilize a similar concept of estimating the clean ratio of the training dataset, our focus is primarily on a representative work titled ITLM (section 3.1). Initially, we present intuitive synthetic results to demonstrate the performance of the OGRS method and compare it with the other methods under different parameter settings. Subsequently, we compare these methods using several real datasets, under both static and dynamically changing clean ratios.

Our experiment primarily examines random label error scenarios, wherein a certain proportion \(1-\phi\) of data samples are randomly, independently, and equally likely mislabeled, where \(\phi\) represents the real clean ratio of the current arrived data. Despite deep learning models' ability to automatically fit these erroneous data, our experiments reveal that our methods outperform both naive training and state-of-the-art methods when dealing with noisy datasets. Code is available at [https://github.com/AnonymousSubmission100/OGRS_NeurIPS/tree/main](https://github.com/AnonymousSubmission100/OGRS_NeurIPS/tree/main).

### Synthetic Experiments

In this section, we evaluate performance on a synthetic dataset of 300 samples, delineated into two non-sensitive features \((x_{1},x_{2})\) and one label class \(y\). The dataset, visualized in a 3D scatter plot, is partitioned into a training set of 200 samples and a test set. Samples follow a Gaussian mixture distribution \((x_{1},x_{2})|y=1\)\(\mathcal{N}([1,1]:[5,1;1,5])\) and \((x_{1},x_{2})|y=0\)\(\mathcal{N}([-1,-1]:[10,1;1,3])\). We artificially flip \(40\%\) of training labels and apply the logistic regression (LR) model.

Our Optimal Gaussian Robustness Scoring (OGRS) method is compared against naive LR and ITLM, varying the pre-estimated clean ratio \(\hat{\phi}\). Unlike other methods, OGRS's parameters remain constant across tasks. Differing \(\hat{\phi}\) values simulate misestimation of the clean ratio with dynamically changing data. Results are detailed in Fig. 2.

Training data loss is depicted in four left-hand figures, where the axes \((x_{1},x_{2})\) represent features and the third axis signifies training loss \(\ell_{\theta_{T}}((x_{1},x_{2}))\) post-training. ITLM with \(\hat{\phi}=0.1\) outperforms other methods, as underestimation of \(\hat{\phi}\) enhances ITLM's selection accuracy. That's only happening in some simple tests like in this section. When the task becomes more and more complex, an underestimation of \(\hat{\phi}\) may seriously degrade the performance as it misses a lot of valuable data points. Naive LR and ITLM with higher \(\hat{\phi}\), however, struggle to differentiate good and bad data, whereas OGRS matches ITLM's performance without requiring a pre-estimated clean ratio.

Test accuracy for different methods is shown on the right, revealing that after an initial drop post the first 50 warm start rounds, OGRS quickly recovers and matches the best ITML case. In contrast,

Figure 2: The left four figures shows the loss \(\ell_{\theta_{T}}(d)\) after the training process, where a well-trained model should correctly distinguish clean and bad samples by assigning different loss. The right figure shows the averaged test accuracy along the time slots \(t\).
ITLM with incorrect parameters underperforms naive LR due to sample misselection and valuable data omission.

### Experiment on Real Datasets

In this subsection, we evaluate the robustness of the OGRS method against label-randomized error in multi-dimensional, multi-error ratio datasets using different models. We employ the MNIST and CIFAR-10 datasets, testing varying clean ratios from 30% to 70%. A 2-layer Multi-layer Perceptron (MLP) is utilized for MNIST, while CIFAR-10 is tested with the widely used ResNet-18 model. Four training methods are compared:

* OGRS: Our method with **fixed parameters** across all experiments.
* ITLM: A representative algorithm for multi-round sample selection, tested under different \(\hat{\phi}\). We introduce the way to transfer ITLM to an online training setting in section 3.1.
* Naive: Directly training using all samples.
* Oracle: Training using only clean samples. Note that the result can only reach around 0.75 for ResNet-18 since we randomly select samples in each time slot \(t\), which is different from the offline training case.

In this section, we compare various training algorithms while maintaining a constant real clean ratio \(\phi\) since holding \(\phi\) fixed allows for clear and plausible experimental analysis. Experiments are conducted under varying parameter configurations to highlight the advantage of OGRS, which does not necessitate a pre-estimated clean ratio. The models are trained for 10,000 rounds for experiments on both MNIST and CIFAR-10, each starting with a 500-round warm-up period using naive training.

Table 1 presents the results on both MNIST and CIFAR-10 datasets. In the majority of the tests, our Online Gradient-based Robust Sample selection (OGRS) method outshines the Iterative Training with Loss Minimization (ITLM) method, except for the test where \(\phi=0.7\) and the pre-estimated ratio for ITLM is set as \(\hat{\phi}=0.9\). This discrepancy arises due to the setting of \(\hat{\phi}=0.9\), which ensures that ITLM samples the top 10% of low-loss data, thereby increasing the likelihood of selecting clean data. However, this setting also causes ITLM to overlook certain observations, which in turn leads to underwhelming performance in other settings.

A vital aspect of this experiment involves testing the ITLM methods under various \(\hat{\phi}\) settings. When \(\hat{\phi}\) approximates the actual clean ratio \(\phi\), ITLM demonstrates robustness against label errors. However, when the discrepancy between these values becomes significant, the method experiences a substantial drop in accuracy. Specifically, ITLM fails to converge in certain tasks when applied to the CIFAR-10 dataset with \(\phi=0.3\) and \(\phi=0.7\), especially when the estimated value \(\hat{\phi}\) significantly deviates from the true value \(\phi\). Such a mismatch is a common occurrence in online training settings with fluctuating clean ratios, rendering the ITLM method less suited for online training with noisy labels.

Additional experiments can be found in the Appendix.

## 7 Conclusion

In this paper, we introduce a novel gradient-based sample selection method to first enable large-scale online robust training with varying proportions of noisy labels, which is a flexible method for training with noisy labels that can be added at the beginning of each iteration. We formulate the sample selection challenge as a non-convex constrained optimization problem and propose an efficient algorithm to address it. In order to give the theoretical analysis for our OGRS method, we introduce a novel metric called the local Lagrangian regret metric. We are the first to directly establish a sublinear local regret bound without resorting to the approximation of the objective function. Experimental results demonstrate that our proposed methods outperform alternatives, particularly when the pre-estimated clean ratio is hard to ascertain.

Future work can be conducted to further address the fairness issue for online training with noisy labels. Given that fairness constraints can feasibly be incorporated into the constrained optimization aspect of OGRS, which make the future research about fairness training possible.