It has been shown that noisy labels would lead to performance degradation when training deep neural networks (DNNs) because of over-fitting to the noise [1]}.
However, it is a fundamental principle for understanding the generalization of deep learning models [2]}.
Empirically, learning with noisily labeled data has been examined by many recent studies such as [3]}, [4]}, [5]}, [6]}, [7]}, [8]}. Most of them are designed to improve learning performance by make a supervised learning process more robust to label noise [9]}, [10]}. Rare studies focus on explaining the training behavior of noisily labeled data from the view of theory. Empirical results have shown that even with a significant portion of the training data assigned to random labels, we are still able to learn an appropriate prediction model that can make accurate prediction [6]}, [7]}. Two interesting phenomena have been observed from the task of learning from noisily labeled data. The first observation is clean data first, i.e. data points with clean labels will be learned first. Although it was shown “intuitively” through a linear binary classification case [7]}, the full story behind this belief is unclear. In the first epoch, we can consider the standard optimization analysis due to the statistical independence property of current model and sampled example(s)We could use the uniform sampling strategy without replacement when implementing stochastic gradient descent during the training process.. The convergence results shows that stochastic gradient descent (SGD) essentially converges to the objective function of examples with clean labels in the order of \(\widetilde{O}(1/m)\)  \(\widetilde{O}(\cdot )\)  suppresses a logarithmic factor, where \(m\)  is the number of training examples with clean labels. The second observation is phase transition, i.e. when \(\gamma \) , the percentage of data with corrupted class labels, is smaller than a certain threshold, continuously training model can lead to a further reduction in testing error after the stage of learning from clean data. However, when \(\gamma \)  exceeds the certain threshold, extensively training could result in an increase in testing error. In this draft, we aim to explain both phenomenon from a theoretical viewpoint, which could be considered as a theoretical understanding of learning with noisy labels.
