DEMYSTIFYING HOW SELF-SUPERVISED FEATURES IMPROVE TRAINING FROM NOISY LABELS
Year: 2021

Abstract:
The advancement of self-supervised learning (SSL) motivates researchers to apply SSL on other tasks such as learning with noisy labels. Recent literature indicates that methods built on SSL features can substantially improve the performance of learning with noisy labels. Nonetheless, the deeper reasons why (and how) SSL features benefit the training from noisy labels are less understood. In this paper, we study why and how self-supervised features help networks resist label noise using both theoretical analyses and numerical experiments. Our result shows that, given a quality encoder pre-trained from SSL, a simple linear layer trained by the cross-entropy loss is theoretically robust to symmetric label noise. Further, we provide insights for how knowledge distilled from SSL features can alleviate the over-fitting problem. We hope our work provides a better understanding for learning with noisy labels from the perspective of self-supervised learning and can potentially serve as a guideline for further research.

heading: 1 INTRODUCTION
text: Deep Neural Networks (DNNs) have achieved remarkable performance in many areas including speech recognition (Graves et al., 2013), computer vision (Krizhevsky et al., 2012; Lotter et al., 2016), natural language processing (Zhang & LeCun, 2015) etc. The high-achieving performance often builds on the availability of quality-annotated datasets. In real world scenario, data annotation inevitably brings in label noise which degrades the performance of the network, primarily due to DNNs’ capability in “memorizing” noisy labels (Zhang et al., 2016).
In the past few years, a number of methods have been proposed to tackle the problem of learning with label noise including robust loss design (Ghosh et al., 2017; Zhang & Sabuncu, 2018; Liu & Guo, 2020), sample selection (Han et al., 2018; Yu et al., 2019; Cheng et al., 2021) and noise transition matrix estimation (Patrini et al., 2017; Zhu et al., 2021b). Among all these methods, arguably the most efficient treatment is to adopt robust losses, since sample selection and noise transition matrix estimation always involve training multiple networks or need multi-stage training. Nonetheless, though the designed losses are theoretically proven robust, they often suffer from significant performance drop when noise rate is high (Wang et al., 2019; Ma et al., 2020; Cheng et al., 2021; Zhu et al., 2021a), hinting that the ability of converging to the optimal classifier is also important.
Very recent works (Zheltonozhskii et al., 2021; Nodet et al., 2021; Ghosh & Lan, 2021; Yao et al., 2021; Tan et al., 2021) started applying self-supervised learning to solving the problem of learning from noisy labels. The experiments show that methods built on the self-supervised features can achieve exceptional performance even when the noise rate is high and largely outperform previously reported SOTA approaches. Despite the empirical observations, the reasons why self-supervised features lead to significant performance improvement are not well understood. In this paper, we provide theoretical insights to understand how self-supervised features improve classification with label noise and perform extensive experiments to support our theory. Our analysis provides a new understanding on learning with noisy labels from the perspective of self-supervised learning. We summarize our main contributions below: • We theoretically and experimentally show that by using self-supervised features to fine-tune the
network on noisy datasets, Cross Entropy itself is robust to label noise (Theorem 1–2). The theory also answers the question of whether or not to fix the encoder when performing fine-tuning.
• We theoretically and experimentally show that by using self-supervised features, a regularizer commonly used in knowledge distillation (Hinton et al., 2015) (where the dataset does not contain label noise) can greatly alleviate over-fitting problem of DNN on noisy datasets (Theorem 3–4).

heading: 1.1 RELATED WORKS
text: Learning with Noisy Labels: Due to the over-fitting problem of DNN, many works design robust loss to improve the robustness of neural networks. (Ghosh et al., 2017) proves MAE is inherently robust to label noise. However, MAE has a severe under-fitting problem. (Zhang & Sabuncu, 2018) propose a loss which can combine both the advantage of MAE and CE, exhibiting good performance on noisy datasets. (Liu & Guo, 2020) introduces peer loss, which is proven statistically robust to label noise without knowing noise rate. The extension of peer loss also shows good performance on instance-dependent label noise (Cheng et al., 2021; Zhu et al., 2021a). Another efficient approach to combat label noise is by sample selection (Jiang et al., 2018; Han et al., 2018; Yu et al., 2019; Northcutt et al., 2021; Yao et al., 2020; Wei et al., 2020; Zhang et al., 2020). These methods regard “small loss” examples as clean ones and always involve training multiple networks to select clean samples. Semi-supervised learning is also popular and effective on learning with noisy labels in recent years. Some works (Li et al., 2020; Nguyen et al., 2020) first perform clustering on the sample loss and divide the samples into clean ones and noisy ones. Then drop the labels of the ”noisy samples” and perform semi-supervised learning on all the samples.
Self-Supervised Learning: The goal of self-supervised learning (SSL) is to learn good presentation without using the information of the labels. Generally, the methods of SSL can be divided into two categories: designing pretext tasks or designing loss functions. The designed tasks or losses do not involve any labels. Some popular tasks include patch orderings (Doersch et al., 2015; Noroozi & Favaro, 2016), tracking (Wang & Gupta, 2015) or clustering features (Caron et al., 2018; 2019). However, the SSL performance of pretext tasks is limited. Recent SOTA methods for SSL is by designing contrastive loss functions. The representative works include Moco (He et al., 2020) and SimCLR (Chen et al., 2020) which train neural networks based on InfoNCE loss (Oord et al., 2018). In our paper, we also adopt InfoNCE for performing self-supervised training to get SSL pre-trained features. The first part of our paper relates to the works that apply SSL features to perform finetuning on noisy dataset (Nodet et al., 2021; Ghosh & Lan, 2021) and our goal is to build theoretical understanding on this aspect.
Knowledge Distillation: The second part of our paper is very related to the research field of knowledge distillation (KD). The original idea of KD can be traced back to model compression (Buciluǎ et al., 2006), where authors demonstrate the knowledge acquired by a large ensemble of models can be transferred to a single small model. (Hinton et al., 2015) generalize this idea to neural networks and show a small, shallow network can be improved through a teacher-student framework. Due to its great applicability, KD has gained more and more attention in recent years and numerous methods have been proposed to perform efficient distillation (Mirzadeh et al., 2020; Zhang et al., 2018; 2019). However, the dataset used in KD is assumed to be clean. Thus it is hard to connect KD with learning with noisy labels. In this paper, we theoretically and experimentally show that a regularizer generally used in KD (Park et al., 2019) can alleviate the over-fitting problem on noisy data by using SSL features which offers a new alternative for dealing with label noise.

heading: 2 PRELIMINARY
text: We introduce preliminaries and notations including definitions and problem formulation.
Problem Formulation: Consider a classification problem on a set of N training examples denoted by D := {(xn, yn)}n∈[N ], where [N ] := {1, 2, · · · , N} is the set of example indices. Examples (xn, yn) are drawn according to random variables (X,Y ) from a joint distribution D. The classification task aims to identify a classifier C that maps X to Y accurately. Our theoretical analyses focus on binary classifications thus Y ∈ {0, 1}. In real-world applications, the learner can only observe noisy labels. For instance, human annotators may wrongly label some images containing cats as ones that contain dogs accidentally or irresponsibly. The label noise of each instance is assumed to be class-dependent (Liu & Tao, 2015), i.e., P(Ỹ |Y ) = P(Ỹ |X,Y ). Thus the error rates are defined as e+ = P(Ỹ = 0|Y = 1), e− = P(Ỹ = 1|Y = 0). The corresponding
noisy dataset and distribution are denoted by D̃ := {(xn, ỹn)}n∈[N ] and D̃. Define the expected risk of a classifier C as R(C) = ED [1(C(X) 6= Y )]. The goal is to learn a classifier C from the noisy distribution D̃ which also minimizes R(C), i.e., learn the Bayes optimal classifier such that CBayes(x) = arg maxi∈{0,1} P(Y = i|X = x). For better presentation, we define the following notations: X+ = X|Y = 1, X− = X|Y = 0, and Xclean = X|Y = Ỹ , Xnoisy = X|Y 6= Ỹ . Evaluation of SSL (Self-Supervised Learning): SSL is usually evaluated by two steps: First, use SSL to train an encoder f with only unlabeled data X , then add a linear classifier g following the pre-trained encoder f and only fine-tune g on (X,Y ) with a fixed f . The high-level intuition is that, if the encoder f is well learned by SSL, only fine-tuning linear classifier g is often sufficient to achieve good performance on test data. If the test performance is comparable to SL (Supervised Learning), we call the gap between SSL and SL is small (Chen et al., 2020). Denote by G the space of linear classifier g. Fine-tuning linear layer g on (X,Y ) ∼ D can be represented as:
min g∈G
ED[CE(g(f(X)), Y )],
where CE denotes the Cross-Entropy loss. Note the dimension of f(X) is determined by the network structure, e.g., 512 for ResNet34. In binary classifications, g(f(X)) ∈ [0, 1] where g(f(X)) < 0.5 indicates predicting class-0 and g(f(X)) > 0.5 corresponds to class-1. g(f(X)) is supposed to predict the same label as CBayes(x).

heading: 3 ROBUSTNESS OF CROSS-ENTROPY WITH SSL FEATURES
text: We will analyze the robustness of Cross-Entropy with SSL features by comparing three different learning paths as illustrated in Figure 1. Path-1 is the traditional learning path that learns both encoder f and linear classifier g at the same time. Path-2 is the strategy applied in (Ghosh & Lan, 2021) that firstly pre-trains encoder f with SSL, then treats the pre-trained model as a network initialization and jointly fine-tunes f and g. Path-3 is an alternate SSL-based path that first learns the encoder f then only fine-tunes the linear classifier g with fixed f .

heading: 3.1 THEORETICAL TOOLS
text: We prepare some theoretical tools for our analyses. Our first theorem focuses on demonstrating the effectiveness of only fine-tuning linear classifier g as in Path-3. We present Theorem 1 below.
Theorem 1 Let g1 = arg ming∈G ED[CE(g(f(X)), Y )], g2 = arg ming∈G ED̃[CE(g(f(X)), Ỹ )]. Then if e+ = e− < 0.5, we have:
Round(g1(f(X))) = Round(g2(f(X))) (1)
where f is fixed encoder and g is the linear classifier, g(f(·)) denotes the output whose value ranges from 0 to 1. Round(p) is a predictor function that outputs 1 if p > 0.5 and outputs 0 otherwise.
Theorem 1 shows with balanced error rates, simply fine-tuning a linear classifier g on the noisy data distribution D̃ can achieve the same decision boundary as the optimal linear classifier obtained from the corresponding clean distribution D. i.e., g1(f) and g2(f) have the same predictions for all the samples. Theorem 1 can be generalized to the case with an arbitrary classifier beyond linear.
However, admittedly with limited data, training complicated classifiers is hard to converge to the optimal decision boundary. We defer more details to the next subsection.
We then evaluate the former part of Path-3, i.e., the performance of SSL. Recall in Section 2, SSL is usually evaluated by performance gap between f ◦ gBayes and CBayes, where gBayes is the optimal linear classifier trained on D, f ◦ gBayes denotes the joint model given by gBayes(f(X)). We consider a tractable case in Assumption 1.
Assumption 1 The encoder outputs f(X+) and f(X−) follow Gaussian distribution with parameters (µ1,Σ) and (µ2,Σ), where Σ = σ2 · I , I is the identity matrix.
Assumption 1 states that the self-supervised features for each class follow simple Gaussian distributions. We check the effectiveness of this assumption by Figure 2. It can be observed that the features of each class may have overlaps, but a good SSL method is supposed to return features with good separations (small overlaps). In Assumption 1, we use ||µ1 − µ2|| and σ to capture the overlapping area of two classes. If ||µ1 − µ2|| is large and σ is small, then there exists small overlapping. Based on this assumption, we show the performance of SSL in Theorem 2.
Theorem 2 If P(Y = 1) = P(Y = 0), the risk (error rate) of Bayes optimal classifier f ◦ gBayes follows as:
R(f ◦ gBayes) = 1− Φ ( ||µ1 − µ2||
2 · σ
) (2)
where Φ is the cumulative distribution function (CDF) of the standard Gaussian distribution.
Wrap-up With Theorem 1, we know CE is robust, the performance of which is subject to f . Theorem 2 implies that if SSL features learned by f exhibit good property, i.e., when ||µ1 − µ2|| is large and σ is small, only fine-tuning g can approach the Bayes optimal classifier CBayes. Therefore, good SSL features induce high performance. In summary, Theorem 1 and Theorem 2 connect SSL features with robustness and generalization ability of CE loss, providing an insight on why SSL features improve classification with label noise.

heading: 3.2 CAN WE FIX THE ENCODER?
text: We compare the performance of Path-2 with Path-3 in this subsection.

heading: 3.2.1 THEORETICAL ANALYSES
text: Denote by VC(G) the VC-dimension of G. Always fix good encoders When we fine-tune g on fixed f , the learning errors will come from two parts: the encoder error and the classification error. The encoder error is bounded in Theorem 2. Noting that g ∈ G is a linear classifier with relatively low VC-dimension and CE is a calibrated and convex function, the optimization can achieve global optimum with enough samples (Bartlett et al., 2006), e.g., w.p. 1 − δ, the learning error will be ε with Θ(VC(G)+ln 1/δε ) i.i.d. instances (Vapnik,
2013). Recall Theorem 1 also guarantees the optimality of g learned under the noisy distribution D̃. Therefore, given a good encoder with large enough ‖µ1−µ2‖σ1 , we should keep it fixed since the simple linear classifier g trained under label noise only requires N = Θ(VC(G)+ln 1/δε ) i.i.d. instances in D̃ to achieve around ε errors with high probability, which performs well enough to approximateCBayes.
Updating f is not stable If f is unfixed, due to the non-convexity and over-fitting capability of f , network trained on vanilla D̃ will likely and ultimately overfit to noisy labels (Zhang et al., 2016), particularly when the number of instances is insufficient. For example, w.p. 1 − δ, jointly learning f and g and achieving error ε requires Θ(VC(F◦G)+ln 1/δε ) i.i.d. instances, which is far more than the number required in only tuning g due to the huge capacity of DNNs. Note the effective i.i.d. instances would decrease with the increase of noise rates. Although a good initialization contributes to better convergence, f will be misled by label noise in extreme cases. Therefore it is unreasonable to assume that CE will stably induce the network to approximate the Bayes optimal classifier under label noise. In other words, if f is not fixed, due to the overfitting capability of f , the outputs of f(X) would be contaminated by the label noise before g. In contrast, the original SSL features are independent from the label noise if f is fixed. We therefore conclude that CE on vanilla D̃ is not robust. Note Nodet et al. (2021) claimed the encoder should not be fixed during fine-tuning based on some experiments. We include more discussions in Appendix.

heading: 3.2.2 EMPIRICAL EVIDENCE
text: We conduct experiments in Figure 3 to support our theorems and analyses above.
Overall performance From Figure 3(a)–(c), when encoder f is fixed, the performance of CE (fixed encoder) exhibits great robustness as noise rate increases and only has a little drop when the symmetric noise rate approximates the maximum theoretical value for each dataset (0.5 for DogCat, 0.9 for CIFAR10) which verifies Theorem 1 and Theorem 2. Note that the drop is because, to reach the condition specified in Equation (1), a substantial number of training samples are needed. However, for example, each class only has 500 samples in CIFAR100. As the noise rate increases, the number of clean samples will further decrease which makes the classifier hard to learn from the distribution.
Fixed encoder benefits extreme label noise Next, we observe the performance gap between SSL and SL when datasets are clean. This gap can be visualized in Figure 3 (a) (b) (c) at noise rate = 0. For DogCat , the gap is very small, thus CE with fixed encoder always exhibits better performance. For CIFAR10, the gap is moderate, the performances of CE (fixed encoder) and CE (unfixed encoder) are close when noise rate is small. However, when noise rate is high, CE with fixed encoder still exhibits better performance. For CIFAR100, the gap is large, thus CE with fixed encoder shows better performance only when noise rate is over 0.7.
Fixed encoder has better convergence Note that the performance in Figure 3 (a) (b) (c) are selected from best epoch accuracy. If we take the last epoch accuracy into consideration. CE with fixed encoder has great advantage over unfixed encoder. Figure 3 (d) depicts the performance of CE in
terms of training epochs under 0.6 symmetric noise rate on CIFAR10. We find that even though these two approaches have almost same best epoch accuracy, CE with fixed encoder is more robust as training proceeds. For CE with unfixed encoder, since the self-supervised pre-trained network’s weights serve as a better initialization, it shows good performance in the beginning. However, because of the memorizing effect of DNN, it will still over-fit to noisy labels in the end.
Generalize to class- and instance-dependent label noise: Theorem 1 shows that CE is robust to label noise when e− = e+. However, for a more general label noise such as asymmetric classdependent label noise or instance-dependent label noise, CE with fixed encoder on vanilla (f(X), Ỹ ) is hard to be guaranteed to be robust because for instance noise, noise rate varies for each class. But it does not mean SSL features can not help. We may still fix the encoder and perform a simple downsampling to balance the noisy dataset before fine-tuning the linear classifier. The down-sampling is conducted to make P(Ỹ = i) = P(Ỹ = j) in the noisy dataset which can well approximate the condition in Theorem 1 (Illustration is deferred to Appendix). Note that with down-sampling, the target distribution of clean labels also changes. However, Theorem 1 is proved without specifying the distribution of clean labels, suggesting that classifier is consistent even for imbalanced dataset under symmetric label noise. Secondly, with SSL features, classifier is robust to imbalanced imbalanced dataset (Yang & Xu, 2020). Thus down-sampling strategy to reduce error rate imbalances is helpful for other noise types beyond symmetric. We perform an experiment in Table 1 to verify the effectiveness of the down-sampling in the setting of instance-dependent label noise (generation of label noise is followed by (Cheng et al., 2021)). From the experiments, if no sampling strategy is conducted, CE with fixed encoder does not show many benefits. In some cases, it even performs worse than CE baseline (unfixed f with random init). However, with down-sampling, CE with fixed encoder even outperforms CORES (Cheng et al., 2021) by a large margin. Even though our main purpose in the paper is not to develop new methods for achieving SOTA, we think this downsampling strategy motivated by Theorem 1 can inspire further research on instance-dependent label noise by using SSL features.

heading: 3.3 TAKEAWAYS
text: Our both theoretical and empirical results demonstrate that: We need to simply fix the encoder when 1) the encoder is sufficiently good, 2) the high noise rate decreases the number of effective i.i.d. instances to a certain level, 3) the over-parameterized model makes it easy to overfit label noise. However, there are some concerns: 1) If the gap between SL and SSL is relatively large, CE with unfixed encoder has more advantage on small noise rate (e.g., Figure 3 (c)); 2) Consider an online classification system which always needs new training data to update itself. If we only fine-tune the linear classifier for keeping robustness to label noise, then due to the limited learnability of affine functions, this online classification system may learn very limited knowledge from unseen data. Therefore, it is necessary to update the encoder while keeping it stable and robust to label noise, which is the focus in the next section.

heading: 4 REGULARIZER FROM KD IMPROVES NETWORK ROBUSTNESS
text: In this section, we show that a regularizer from knowledge distillation (KD) (Park et al., 2019) can well alleviate the over-fitting problem by using the structure of SSL features. Different from classical KD settings where the dataset is clean, our analyses aim at regularizing classifiers learned with noisy
supervisions by SSL features. Understanding the working mechanism is important since it may contribute to the community a new perspective to learn with label noise by distilling information from SSL features. In the rest of this section, we will first provide theoretical understanding towards the regularizer under label noise, then perform experiments on different settings to test our analyses.

heading: 4.1 TRAINING FRAMEWORK
text: The training framework is shown in Figure 4, where a new learning path (SSL training) f → h is added to be parallel to Path-2 f → g (SL-training) in Figure 1. The newly added projection head h is one-hidden-layer MLP (Multi Layer Perceptron) whose output represents SSL features (after dimension reduction). Its output is employed to regularize the output of linear classifier g as Reg(h(f(X)), g(f(X))). InfoNCE from SimCLR (Chen et al., 2020) is adopted for SSL training and CE is for SL training. InfoNCE and CE share a common encoder, inspired by the design of self distillation (Zhang et al., 2019). The loss function is defined as:
L = ED̃ { CE(g(f(X)), Ỹ ) + InfoNCE(h(f(X))) + Reg(h(f(X)), g(f(X))) } (3)
Intuitively, SL features is supposed to be benefited from the structure information from SSL features, e.g., clusterability (Zhu et al., 2021b) that instances with similar SSL features should have the same true label and instance with different SSL features should have different true labels. Mathematically, let ti = h(f(xi)), si = g(f(xi)) and XN to be the set of N tuples of data samples. The distance between ti and tj can be represented as φw(ti, tj) = 1m‖ti − tj‖
w, where w ∈ {1, 2} and m is a normalization term:
m = 1 |X 2| ∑
(xi,xj)∈X 2 ||ti − tj ||w. (4)
Then the expectation of Reg(h(X), g(X)) in Equation (3) can be estimated by:
EX [Reg(h(X), g(X))] ≈ 1 |X 2| ∑
(xi,xj)∈X 2 d(φw(ti, tj), φ w(si, sj)) (5)
where d(·) is a distance measure for two inputs. Popular choices are l1, l2 or square l2 distance.

heading: 4.2 ANALYTICAL FRAMEWORK
text: Under the label noise setting, denote by di,j = d(φw(ti, tj), φw(si, sj)), we have the following decomposition:
1 |X 2| ∑
(xi,xj)∈X 2 di,j =
1
|X 2| ( ∑ (xi,xj)∈X 2clean di,j
︸ ︷︷ ︸ Term-1
+ ∑
(xi,xj)∈X 2noisy
di,j
︸ ︷︷ ︸ Term-2
+ ∑
xi∈Xclean,xj∈Xnoisy 2 · di,j︸ ︷︷ ︸ Term-3
) . (6)
where X = Xclean ⋃ Xnoisy, Xnoisy denotes the set of samples whose labels are flipped. Note the regularizer mainly works when SSL features “disagree” with SL features, i.e., Term-3. For further analyses, we write Term-3 in the form of expectation with d chosen as square l2 distance, i.e., MSE loss:
Lc = EXclean,Xnoisy ( ||g(f(Xclean))− g(f(Xnoisy))||1
m1 − ||h(f(X clean))− h(f(Xnoisy))||2 m2
)2 (7)
where m1 and m2 are normalization terms in Equation (4). Note in Lc, we use w = 1 for SL features and w = 2 for SSL features.1 Denote the variance by var(·). Define notations:
Xnoisy+ := X|(Ỹ = 1, Y = 0), X noisy − := X|(Ỹ = 0, Y = 1).
To theoretically measure and quantify how feature correction relates to network robustness, we make three assumptions as follows:
Assumption 2 (Memorize clean instances) ∀n ∈ {n|ỹn = yn},CE(g(f(xn)), yn) = 0.
Assumption 3 (Same overfitting) var(g(f(Xnoisy+ ))) = 0 and var(g(f(X noisy − ))) = 0.
Assumption 4 (Gaussian-distributed SSL features) The SSL features follow Gaussian distributions, i.e., h(f(X+1)) ∼ N (µ1,Σ) and h(f(X−1)) ∼ N (µ2,Σ).
Assumption 2 implies that a DNN has confident predictions on clean samples. Assumption 3 implies that a DNN has the same degree of overfitting for each noisy sample. For example, an overparameterized DNN can memorize all the noisy labels (Zhang et al., 2016; Liu, 2021). Thus these two assumptions are reasonable. Assumption 4 follows Assumption 1. Note in Figure 4, SSL features are from h(f(X)) rather than f(X).

heading: 4.3 THEORETICAL UNDERSTANDING
text: Based on Assumptions 2–4, we present Theorem 3 to analyze the effect of Lc. Recall X noisy + := X|(Ỹ = 1, Y = 0), Xnoisy− := X|(Ỹ = 0, Y = 1).
Theorem 3 When e− = e+ and P(Y = 1) = P(Y = 0), minimizing Lc respect to g(f(Xnoisy)) on DNN results in the following solutions:
EXnoisy+
[ g(f(Xnoisy+ )) ] = 1
2 − 1 2 + ∆(Σ, µ1, µ2) , EXnoisy−
[ g(f(Xnoisy− )) ] = 1
2 +
1
2 + ∆(Σ, µ1, µ2) ,
where ∆(Σ, µ1, µ2) := 8 · tr(Σ)/||µ1 − µ2||2, tr(·) denotes the matrix trace, .
Theorem 3 reveals a clean relationship between the quality of SSL features (given by h(f(X))) and the network robustness on noisy samples. Note the true label for Xnoisy+ is 0 and the true label for Xnoisy− is 1. Theorem 3 shows the regularizer is leading the classifier to predict the feature with corrupted label to its corresponding true label, and the guidance is particular strong when ∆(Σ, µ1, µ2) → 0, e.g., tr(Σ) → 0 or ‖µ1 − µ2‖ → ∞, such that EXnoisy+ [g(f(X noisy + ))] → 0 and EXnoisy− [g(f(X noisy − ))]→ 1. Beyond this ideal case, we discuss more interesting findings as:
• Worst case: The regularizer can always have a positive effect to avoid memorizing wrong labels as long as the model f ◦ h is better than randomly initialized models. This is because ∆(Σ, µ1, µ2) > 0 when µ1 and µ2 are different, and the regularizer is leading the classifier to the true direction when ∆(Σ, µ1, µ2) > 0. • Practical case: The model f ◦ h is always better than randomly initialized models since SL training can guarantee the performance of encoder f on clean instances, which may generalize to noisy instances, and SSL training can further improves the quality of f ◦ h. Thus in practical cases, using SSL features to regularize learning with noisy labels is always beneficial.
• More possibilities: Note the proof of Theorem 3 does not rely on any SSL training process. From our first finding, we know any encoder helps if it is better than random models. This makes it possible to use some pre-trained encoders from other tasks.
High-level understanding on structure regularization: Even though we have built Theorem 3 to show SL features can benefit from the structure of SSL features by performing regularization, there
1Practically, different choices make negligible effects on performance. See more details in Appendix.
still lacks high-level understanding of what the regularization is exactly doing. Here we provide an insight in Theorem 4 which shows the regularization is implicitly maximizing mutual information between SL features and SSL features.
Theorem 4 Suppose there always exists a mapping ξ to map h(f(X)) to g(f(X)). I.e., g(f(X)) = ξ(h(f(X))). Then minimizing Equation (5) is implicitly maximizing Mutual Information between h(f(X)) and g(f(X)). I.e., when Equation (5) achieves 0, the mutual information I(h(f(X)), g(f(X))) achieves maximum.
The above results facilitate a better understanding on what the regularizer is exactly doing. Note that Mutual Information itself has several popular estimators (Belghazi et al., 2018; Hjelm et al., 2018). It is a very interesting future direction to develop regularizes based on MI to perform regularization by utilizing SSL features.

heading: 4.4 EXPERIMENTS
text: We provide experiments on CIFAR10 to verify our theory and analysis. The overall experiments are shown in Figure 5. In the experiments, Regularizer is added at the very beginning since recent studies show that for random initialized network, the model tends to fit clean labels first (Arpit et al., 2017) and we hope the regularizer can improve the network robustness when DNN begins to fit noisy labels. From Figure 5 (c) (d), for CE training, the performance first increases then decreases since the network over-fits noisy labels as training proceeds. However, for CE with regularizer, the performance is more stable after it reaches the peak. For 60% noise rate, the peak point is also much higher than vanilla CE training. For Figure 5 (a) (b), since the network is not randomly initialized, it over-fits noisy labels at the very beginning and the performance gradually decreases. However, for CE with regularizer, it can help the network gradually increase the performance as the network reaches the lowest point (over-fitting state). This observation supports Theorem 3 that the regularizer can prevent DNN from over-fitting to noisy labels. More experiments and ablation studies can be found in the Appendix.

heading: 5 CONCLUSIONS AND DISCUSSIONS
text: In this paper, we have provided a theoretical understanding on why and how self-supervised features improve training from noisy labels and perform experiments to verify our analysis. • We show that with SSL pre-trained encoder, CE itself is theoretically robust to symmetric label
noise. With the down-sampling strategy, it can also exhibit great power on class- and instancedependent label noise. This part answers why SSL features help (Theorem 1–2).
• We show that by utilizing SSL features, the regularizer in KD can help DNN alleviate the overfitting problem on the noisy dataset and build theoretical insights on how SSL features relate to the network robustness. This part answers how SSL features help (Theorem 3–4).
Future directions can be done to develop more efficient sampling strategies for solving instancebased label noise with theoretical guarantees and develop efficient regularizers to combat label noise. The key for these future works is to leverage the nice structural property of SSL features.

heading: APPENDIX
text: The Appendix is arranged as follows: Section A proves Theorem 1 and Theorem 2 in the main paper. Section B proves Theorem 3 and Theorem 4 in the main Paper. Section C illustrates why down-sampling can decrease the gap of noise rates. Section D provides additional discussions and experiments including further discussion of whether or not to fix the encoder when fine-tuning DNN on noisy dataset; analyses of why robust losses (Wang et al., 2019; Ma et al., 2020) may suffer severe performance degradation under high noise rates; the effect of distance measure in Equation (4) (w = 1 or 2); ablation study in Section 4; visualization of features trained by vanilla CE loss; the effect of different SSL pre-trained methods; Experiments with human-annotated label noise. Section E elaborates the detailed experimental setting of all the experiments in the paper. Section F generalizes Theorem 1 to multi-class classification. Section G provides theoretical and experimental proof on why directly fine-tuning SSL features cannot be robust on asymmetric and instance label noise.

heading: A PROOF FOR THEOREM 1,2

heading: A.1 PROOF FOR THEOREM 1
text: Define g1 = ming ED[CE(g(f(X)), Y )] and g2 = ming ED̃[CE(g(f(X))), Ỹ )]. Suppose g Bayes 1 and gBayes2 are Bayes optimal classifiers under P(f(X), Y ) and P(f(X), Ỹ ), respectively. Since CE is a calibrated and convex loss, with enough samples, g1 and g2 will converge to (approximate to) gBayes1 and g Bayes 2 (Bartlett et al., 2006). Thus to prove g1 and g2 have the same prediction for f(X), it is identical to prove gBayes1 and g Bayes 2 have the same predictions for f(X).
Let p+(x) be the distribution of f(X+) and p−(x) be the distribution of f(X−), according to the bayes rules:
P(Y = 1|x) = P(Y = 1) · p+(x) P(Y = 1) · p+(x) + P(Y = 0) · p−(x)
(8)
P(Y = 0|x) = P(Y = 0) · p−(x) P(Y = 1) · p+(x) + P(Y = 0) · p−(x)
(9)
Define ψ(x) = P(Y = 1) · p+(x) − P(Y = 0) · p−(x). Thus ψ(x) = 0 is the decision boundary for optimal Bayes classifier gBayes1 on clean dataset. Since when ψ(x) > 0,P(Y = 1|x) > P(Y = 0|x) from Equation (8) (9), the classifier will output the prediction as 1 and vice versa. Since the generation of label noise is independent to f(X), the samples for each class whose labels are flipped also follows original distribution. Denote pe+(x) to be the distribution of samples whose observed labels are 1 under label noise. Thus pe+(x) and p e −(x) can be represented as:
pe+(x) = m1 · {P(Y = 1) · (1− e+) · p+(x) + P(Y = 0) · e− · p−(x)} pe−(x) = m2 · {P(Y = 1) · e+ · p+(x) + P(Y = 0) · (1− e−1) · p−(x)}
where m1 and m2 are normalization term to make distribution valid. Specifically, m1 = 1 P(Y=1)·(1−e+)+P(Y=0)·e− and m2 = 1
P(Y=1)·e++P(Y=0)·(1−e−) . Under label noise, P(Ỹ = 1) = P(Y = 1) · (1 − e+) + P(Y = 0) · e− and P(Ỹ = 0) = P(Y = 1) · e+ + P(Y = 0) · (1 − e−). According bayes rules, we have:
P(Ỹ = 1|x) = P(Ỹ = 1) · pe+(x)
P(Ỹ = 1) · pe+(x) + P(Ỹ = 0) · pe−(x) (10)
P(Ỹ = 0|x) = P(Ỹ = 0) · pe−(x)
P(Ỹ = 1) · pe+(x) + P(Ỹ = 0) · pe−(x) (11)
Without loss of generality, we assume there exits a x0 in the feature space which satisfy ψ(x0) > 0. Thus for clean dataset, P(Y = 1) · p+(x) > P(Y = 0) · p−(x) and P(Y = 1|x0) > P(Y = 0|x0). We aim to show that for noisy dataset, P(Ỹ = 1|x0) > P(Ỹ = 0|x0), which means ψ(x) = 0 is also the decision boundary that gives Bayes optimal classifier gBayes2 under label noise.
According to Equation (10) and Equation (11),
P(Ỹ = 1|x0)− P(Ỹ = 0|x0)
= (1− 2 · e+) · P(Y = 1) · p+(x0)− (1− 2 · e−) · P(Y = 0) · p−(x0)
normalization
(12)
where normalization = P(Ỹ = 1) · pe+(x) + P(Ỹ = 0) · pe−(x) > 0. Since P(Y = 1) · p+(x0) > P(Y = 0) · p−(x0), if e+ = e− < 0.5, we have P(Ỹ = 1|x0)−P(Ỹ = 0|x0) > 0. Thus ψ(x) = 0 is also the decision boundary of gBayes2 . g Bayes 1 and g Bayes 2 will output the same prediction for all the samples.
Proof done.

heading: A.2 PROOF FOR THEOREM 2
text: Let d = ||µ1 − µ2||. Without loss of generality, we assume µ1 = (−d2 , 0, . . . , 0) and µ2 = (d2 , 0, . . . , 0) (This can be done by applying affine transformation on original coordinates without changing actual positions of f(X+) and f(X−)). Under the distribution of Gaussian assumption, we write the distribution of f(X+) as follows:
p+(x) = 1
(2π) k 2 σk exp{− 1 2σ2 (x− µ1)T (x− µ1)} (13)
where x = (x1, . . . , xk)T ∈ Rk, xk denotes the variable of x in the k-th dimension. Similarly, the pdf of f(X−) can be represented as:
p−(x) = 1
(2π) k 2 σk exp{− 1 2σ2 (x− µ2)T (x− µ2)} (14)
Following notations from A.1, solving ψ(x) = 0 under the conditions of P(Y = 1) = P(Y = 0) gives x1 = 0 (x1 is the variable of x in the first dimension). Thus, when x1 < 0, the Bayes optimal classifier f ◦ gBayes outputs prediction as 1. I.e., for samples whose labels are 1, f ◦ gBayes gives right prediction when x1 < 0 and wrong prediction when x1 > 0. The risk of of f ◦ gBayes can be written as:
R(f ◦ gBayes) = EX,Y 1(f ◦ gBayes(X) 6= Y ) = EY EX|Y 1(f ◦ gBayes(X) 6= Y ) = P(Y = 1) · EX|Y=11(f ◦ gBayes(X) 6= 1) + P(Y = 0) · EX|Y=01(f ◦ gBayes(X) 6= 0)
= 1
2 · EX|Y=11(f ◦ gBayes(X) 6= 1) +
1 2 · EX|Y=01(f ◦ gBayes(X) 6= 0)
(a) = EX|Y=11(f ◦ gBayes(X) 6= 1)
= {∫ x|x1<0 p+(x)dx } · 0 + {∫ x|x1>0 p+(x)dx } · 1
(b) = 1− Φ( d
2 · σ )
(a) is satisfied because of the symmetry of p+(x) and p−(x). We derive (b) as follows:
∫ x|x1<0 p+(x)dx
= ∫ x|x1<0
1
(2π) k 2 σk exp{− 1 2σ2 (x− µ1)T (x− µ1)}dx
= ∫ x|x1<0
1
(2π) k 2 σk
exp{− (x1 +
d 2 ) 2 + x22 + · · ·+ x2k 2σ2 dx
= ∫ x2 1√ 2πσ exp{− x 2 2 2σ2 }dx2 · · · ∫ xk 1√ 2πσ exp{− x 2 k 2σ2 }dxk ∫ x1<0 1√ 2πσ exp{− (x1 + d 2 ) 2 2σ2 }dx1
= 1 · 1 · · · · · ∫ x1<0 1√ 2πσ exp{− (x1 + d 2 ) 2 2σ2 }dx1
Since ∫ x1 1√ 2πσ exp{− (x1+ d 2 ) 2 2σ2 }dx1 is one dimensional gaussian with mean − d 2 and deviation σ, it
is easy to calculate that ∫ x1<0 1√ 2πσ exp{− (x1+ d 2 ) 2 2σ2 }dx1 = Φ( d
2·σ ), where Φ is the cdf of standard gaussian distribution.
Thus ∫ x1>0 1√ 2πσ exp{− (x1+ d 2 ) 2 2σ2 }dx1 = 1 − ∫ x1<0 1√ 2πσ exp{− (x1+ d 2 ) 2 2σ2 }dx1 = 1 − Φ( d
2·σ ) and Equation (b) is satisfied.
Proof done.

heading: B PROOF FOR THEOREM 3,4
text: Lemma 1 If X and Y are independent and follow gaussian distribution: X ∼ N (µX ,ΣX) and Y ∼ N (µY ,ΣY ), Then: EX,Y (||X − Y ||2) = ||µX − µY ||2 + tr(ΣX + ΣY ).

heading: B.1 PROOF FOR THEOREM 3
text: Before the derivation, we define some notations for better presentation. Define the labels of Xclean as Y clean and the labels ofXnoisy as Y noisy. Under the label noise, it is easy to verify P(Y clean = 1) = P(Y=1)·(1−e+) P(Y=1)·(1−e+)+P(Y=0)·(1−e−) and P(Y noisy = 1) = P(Y=0)·e−P(Y=0)·e−+P(Y=1)·e+ . Let p1 = P(Y clean = 1), p2 = P(Y noisy = 1), g(f(X)) and h(f(X)) to be simplified as gf(X) and hf(X).
In the case of binary classification, gf(x) is one dimensional value which denotes the network prediction on x belonging to Y = 1. Lc can be written as:
EXclean,Xnoisy ( ||gf(Xclean)− gf(Xnoisy))||1 m1 − ||hf(X clean)− hf(Xnoisy)||2
m2 )2︸ ︷︷ ︸
denoted as Ψ(Xclean,Xnoisy)
(a) = E(Xclean,Y clean)
(Xnoisy,Y noisy)
Ψ(Xclean, Xnoisy)
= p1 · p2 · EXclean+ ,Xnoisy+ Ψ(X clean + , X noisy + ) + (1− p1) · p2 · EXclean− ,Xnoisy+ Ψ(X clean − , X noisy + )
+ p1 · (1− p2) · EXclean+ ,Xnoisy− Ψ(X clean + , X noisy − ) + (1− p1) · (1− p2) · EXclean− ,Xnoisy− Ψ(X clean − , X noisy − )
where m1 and m2 are normalization terms from Equation (4). (a) is satisfied because Ψ(Xclean, Xnoisy) is irrelevant to the labels. We derive Ψ(Xclean+ , X noisy + ) as follows:
EXclean+ ,Xnoisy+ Ψ(X clean + , X noisy + )
(b) = EXclean+ ,Xnoisy+ (
||1− gf(Xnoisy+ )||1 m1 − ||hf(Xclean+ )− hf(X noisy + )||2 m2 )2
(c) = EXclean+ ,Xnoisy+ ( 1− gf(Xnoisy+ ) m1 − ||hf(Xclean+ )− hf(X noisy + )||2 m2 )2
(d) = EXclean+ ,Xnoisy+ (
gf(Xnoisy+ )
m1 − ( 1 m1 − ||hf(Xclean+ )− hf(X noisy + )||2 m2 ))2
(b) is satisfied because from Assumption 2, DNN has confident prediction on clean samples. (c) is satisfied because g(f(x)) is one dimensional value which ranges from 0 to 1. From Assumption 4, hf(X+) and hf(X−) follows gaussian distribution with parameter (µ1,Σ) and (µ2,Σ). Thus according to Lemma 1, we have EXclean+ ,Xnoisy+ ||hf(X clean + )−hf(X noisy + )||2 = ||µ1−µ2||2 + 2 · tr(Σ). Similarly, one can calculate EXclean− ,Xnoisy+ ||hf(X clean − )−hf(X noisy + )||2 = 2 · tr(Σ). It can be seen that (d) is function with respect to gf(Xnoisy+ ). Similarly, Ψ(X clean − , X noisy + ) is also a function with respect to gf(Xnoisy+ ) while Ψ(X clean + , X noisy − ) and Ψ(X clean − , X noisy − ) are functions with respect to gf(X noisy − ). Denote d(+,+) = EXclean+ ,Xnoisy+ ||hf(X clean + )−hf(X noisy + )||2. After organizing Ψ(Xclean+ , X noisy + ) and Ψ(Xclean− , X noisy + ), we have:
min gf(Xnoisy+ )
p1 · p2 · EXclean+ ,Xnoisy+ Ψ(X clean + , X noisy + ) + (1− p1) · p2 · EXclean− ,Xnoisy+ Ψ(X clean − , X noisy + )
⇒ min gf(Xnoisy+ ) (EXnoisy+ gf(X noisy + )) 2
− (2 · p1(1− m1 · d(+,+)
m2 ) + 2 · (1− p1)( m1 · d(−,+) m2 )) · EXnoisy+ gf(X noisy + )
+ constant with respect to gf(Xnoisy+ )
(15)
Note in Equation (15), we use (EXnoisy+ gf(X noisy + )) 2 to approximate EXnoisy+ gf(X noisy + ) 2 since from Assumption 3, var(g(f(Xnoisy+ )))→ 0. Now we calculate m1 and m2 from Equation (4):
m1 = p1 · p2 · (1− EXnoisy+ gf(X noisy + )) + (1− p1) · p2 · EXnoisy+ gf(X noisy + )
+ p1 · (1− p2) · (1− EXnoisy− gf(X noisy − )) + (1− p1) · (1− p2) · EXnoisy− gf(X noisy − )
(16)
m2 = p1 ·p2 ·d(+,+)+(1−p1) ·p2 ·d(−,+)+p1 · (1−p2) ·d(+,−)+(1−p1)(1−p2) ·d(−,−)
Under the condition of P(Y = 1) = P(Y = 0), e− = e+, we have p1 = p2 = 12 , m2 = 4·tr(Σ)+||µ1−µ2||2 2 , m1 = 1 2 , which is constant with respect to EXnoisy+ gf(X noisy + ) and EXnoisy− gf(X noisy − ) in Equation (16). Thus Equation (15) is a quadratic equation with respect to EXnoisy+ gf(X noisy + ). Then when Equation (15) achieves global minimum, we have:
EXnoisy+ gf(X noisy + ) = p1 − m1 m2 (p1 · d(+,+)− (1− p1) · d(−,+))
= 1 2 − 1
2 + 8·tr(Σ)||µ1−µ2||2
(17)
Similarly, organizing Ψ(Xclean+ , X noisy − ) and Ψ(X clean − , X noisy − ) gives the solution of EXnoisy− gf(X noisy − ):
EXnoisy− gf(X noisy − ) = p1 + m1 m2 (p1 · d(−,−)− (1− p1) · d(+,−))
= 1
2 +
1
2 + 8·tr(Σ)||µ1−µ2||2
(18)
Proof Done.

heading: B.2 PROOF FOR THEOREM 4
text: We first refer to a property of Mutual Information:
I(X;Y ) = I(ψ(X);φ(Y )) (19)
where ψ and φ are any invertible functions. This property shows that mutual information is invariant to invertible transformations (Cover, 1999). Thus to prove the theorem, we only need to prove that ξ in Theorem 4 must be an invertible function when Equation (5) is minimized to 0. Since when ξ is invertible, I(h(f(X)), g(f(X))) = I(h(f(X)), ξ(h(f(X)))) = I(h(f(X)), h(f(X))).
We prove this by contradiction.
Let ti = h(f(xi)) and si = g(f(xi)). Suppose ξ is not invertible, then there must exists si and sj where si 6= sj which satisfy tj = ξ(si) = ti. However, under this condition, ti − tj = 0 and si − sj 6= 0, Equation (5) can not be minimized to 0. Thus when Equation (5) is minimized to 0, ξ must be an invertible function.
Proof done.

heading: B.3 PROOF FOR LEMMA 1
text: By the independence condition, Z = X − Y also follows gaussian distribution with parameter (µX − µY ,ΣX + ΣY ). Write Z as Z = µ + LU where U is a standard gaussian and µ = µX − µY , LLT = ΣX + ΣY . Thus
||Z||2 = ZTZ = µTµ+ µTLU + UTLTµ+ UTLTLU (20)
Since U is standard gaussian, E(U) = 0. We have
E(||Z||2) = µTµ+ E(UTLTLU) = µTµ+ E( ∑ k,l (LTL)k,lUkUl)
(a) = µTµ+ ∑ k (LTL)k,k
= µTµ+ tr(LTL)
= ||µX − µY ||2 + tr(ΣX + ΣY )
(21)
(a) is satisfied because U is standard gaussian, thus E(U2k ) = 1 and E(UkUl) = 0 (k 6= l). Proof Done.
C ILLUSTRATING DOWN-SAMPLING STRATEGY
We illustrate in the case of binary classification with e+ + e− < 1. Suppose the dataset is balanced, at the initial sate, e+ > e−. After down-sampling, the noise rate becomes e∗+ and e ∗ −. We aim to prove two propositions:
Proposition 1 If e+ and e− are known, the optimal down-sampling rate can be calculated by e+ and e− to make e∗+ = e ∗ −
Proposition 2 If e+ and e− are not known. When down-sampling strategy is to make P(Ỹ = 1) = P(Ỹ = 0), then 0 < e∗+ − e∗− < e+ − e−.
Proof for Proposition 1: Since dataset is balanced with initial e+ > e−, we have P(Ỹ = 1) < P(Ỹ = 0). Thus down-sampling is conducted at samples whose observed label are 0. Suppose the random down-sampling rate is r, then e∗+ = r·e+ 1−e++r·e+ and e ∗ − = e− r·(1−e−)+e− . If e ∗ + = e ∗ −, we have: r · e+
1− e+ + r · e+ = e− r · (1− e−) + e−
(22)
Thus the optimal down-sampling rate r = √
e−·(1−e+) e+·(1−e−) , which can be calculated if e− and e+ are
known.
Proof for Proposition 2: If down sampling strategy is to make P(Ỹ = 1) = P(Ỹ = 0), then r · (e+ + 1− e−) = 1− e+ + e−, we have r = 1−e++e−1−e−+e+ . Thus e ∗ + can be calculated as:
e∗+ = r · e+
1− e+ + r · e+
= (1− e+ + e−) · e+
(1− e+) · (1− e− + e+) + e+ · (1− e+ + e−)
Denote α = 1−e++e−(1−e+)·(1−e−+e+)+e+·(1−e++e−) . Since e+ > e−, 1 − e− + e+ > 1 − e+ + e−, α = 1−e++e−(1−e+)·(1−e−+e+)+e+·(1−e++e−) < 1−e++e− (1−e+)·(1−e++e−)+e+·(1−e++e−) = 1.
Similarly, e∗− can be calculated as:
e∗− = e−
e− + r · (1− e−)
= (1− e− + e+) · e−
e− · (1− e− + e+) + (1− e−) · (1− e+ + e−)
Denote β = 1−e−+e+e−·(1−e−+e+)+(1−e−)·(1−e++e−) . Since e+ > e−, 1 − e− + e+ > 1 − e+ + e−, β = 1−e−+e+e−·(1−e−+e+)+(1−e−)·(1−e++e−) > 1−e−+e+ e−·(1−e−+e+)+(1−e−)·(1−e−+e+) = 1. Since α · e+ < e+ and β · e− > e−, we have e∗+ − e∗− = α · e+ − β · e− < e+ − e−. Next, we prove e∗+ > e ∗ −, following the derivation below:
e∗+ > e ∗ −
=⇒ r · e+ 1− e+ + r · e+ > e− e− + r · (1− e−)
=⇒ r > √ e− · (1− e+) e+ · (1− e−)
=⇒ 1− e+ + e− 1− e− + e+ > √ e− · (1− e+) e+ · (1− e−)
=⇒ e+ · (1− e+) + e+ · e2− 1− e+ > e− · (1− e−) + e− · e2+ 1− e−
(23)
Let f(e+) = e+ · (1− e+) + e+·e2− 1−e+ − e− · (1− e−)− e−·e2+ 1−e− . Since we have assumed e− < e+ and e− + e+ < 1. Thus proving e∗+ > e ∗ − is identical to prove f(e+) > 0 when e− < e+ < 1− e−.
Firstly, it is easy to verify when e+ = e− or e+ = 1 − e−, f(e+) = 0. From Mean Value Theory, there must exists a point e0 which satisfy f ′(e0) = 0 where e+ < e0 < 1−e−. Next, we differentiate
f(e+) as follows:
f ′(e+) = (1− e+)2 · (1− e−) + e2− · (1− e−)− 2 · e+(1− e+)2
(1− e+)2 · (1− e−) (24)
It can be verified that f ′(e−) = 1−e− (1−e−)2·(1−e−) > 0 and f ′(1− e−) = 0e2−·(1−e−) = 0.
Further differentiate f ′(e+), we get when e+ < 1 − ((1 − e−) · e2−) 1 3 , f ′′(e+) < 0 and when e+ > 1 − ((1 − e−) · e2−) 1 3 , f ′′(e+) > 0. Since e− < e+ and e− + e+ < 1, we have e− < 12 and e− < 1 − ((1 − e−) · e2−) 1 3 < 1 − e−, i.e., 1 − ((1 − e−) · e2−) 1 3 locates in the point between e− and 1− e−. Thus, when e− < e+ < 1− ((1− e−) · e2−) 1 3 , f(e+) is a strictly concave function and when 1− ((1− e−) · e2−) 1 3 < e+ < 1− e−, f(e+) is a strictly convex function.
Since f ′(e−) > 0 and f ′(1− e−) = 0, e0 must locates in the point between e− and 1− ((1− e−) · e2−) 1 3 which satisfy f ′(e0) = 0. Thus when e− < e+ < e0, f(e+) monotonically increases and when e0 < e+ < 1− e−, f(e+) monotonically decreases. Since f(e−) = f(1− e−) = 0. We have f(e+) > 0 when e− < e+ < 1− e−. Proof done.
We depict a figure in Figure 6 to better show the effect of down-sampling strategy. It can be seen the curves in the figure well support our proposition and proof. When e+ − e− is large, down-sampling strategy to make P(Ỹ = 1) = P(Ỹ = 0) can well decrease the gap even we do not know the true value of e− and e+. Thus down-sampling strategy can approximate the condition in Theorem 1, which explains why CE with fixed encoder can also work well on instance-dependent label noise in Table 1.

heading: D MORE DISCUSSIONS AND EXPERIMENTS

heading: D.1 WHETHER OR NOT TO FIX THE ENCODER
text: Nodet et al. (2021) experimentally test many methods and losses based on the pre-trained SSL features and draw the conclusion that the encoder should not be fixed during fine-tuning. We argue that this conclusion is not complete and neglects the specialty of each loss and the gap between SSL and SL varies for each dataset. First, the robustness of CE in Equation (1) is based on the fact that CE is a calibrated and convex loss respect to the linear classifier. However, the losses tested by Nodet et al. (2021) do not all satisfy this property when performing fine-tuning. For example, GCE
(Zhang & Sabuncu, 2018) is not convex with respect to linear classifier. Second, if the gap between SSL and SL is large, then the encoder should not be fixed since supervised features can exhibit better performance. However, if the gap between SSL and SL is very small, it is guaranteed by Theorem 1 and Theorem 2 that CE on noisy dataset can approximates SL on clean dataset when encoder is fixed. The observation can be seen in Figure 3 (a). Thus, the above argument suggests that whether to fix the encoder or not is determined by the gap between SSL and SL for a given dataset.

heading: D.2 PROBLEM OF OTHER ROBUST LOSSES
text: Many robust losses have been proposed in recent years. For example, some losses (Natarajan et al., 2013; Liu & Guo, 2020) are also proven statistically robust which satisfy:
min g,f EX,Y [CE(g(f(X)), Y )]⇐⇒ min g,f EX,Ỹ [`(g(f(X)), Ỹ )] (25)
where ` is the robust loss and f , g in Equation (25) are simultaneously updated. However, Equation (25) not only needs sufficient training samples to achieve small learning error ε, but also does not consider the optimization difficulty of deep neural networks. Because of the great non-convexity of f , it is very hard to guarantee that f and g will converge to global optimal when noise rate varies. Thus the performance of ` in Equation (25) may suffer severe performance degradation under high noise rate. However, for Equation (1), when f is fixed, CE loss with respect to g is strictly convex which is very friendly for optimization.
To further verify our analysis, we compare CE with SSL pre-trained encoder with some robust losses including SCE (Wang et al., 2019), APL (Ma et al., 2020) and Peer loss (Liu & Guo, 2020) on CIFAR10 with symmetric label noise. The results are shown in Table 2. It can be observed that when noise rate is very high, the performance of these robust losses will drop significantly. However, when SSL pre-trained encoder is fixed, CE loss with respect to linear classifer is strictly convex. Thus the performance is more stable when noise rate increases.

heading: D.3 THE EFFECT OF DISTANCE MEASURE IN EQUATION (4)
text: In this paper and experiment, we use l2 norm to calculate the feature distance between SL features and square l2 norm to calculate the distance between SSL features. This choice can lead to good performance from Theory 3 and Figure 5. Practically, since structure regularization mainly captures the relations, different choice does not make a big effect on the performance. We perform an experiment in Figure 7 which shows that the performance of both types are quite close.

heading: D.4 ABLATION STUDY
text: In Figure 4, SSL training is to provide SSL features to regularize the output of linear classifier g. However, SSL training itself may have a positive effect on DNN. To show the robustness mainly comes from the regularizer rather than SSL training, we perform an ablation study in Figure 8. From the experiments, it is the regularizer that alleviates over-fitting problem of DNN.
D.5 VISUALIZING FEATURES OF DNN TRAINED BY CE WHEN ENCODER IS NOT FIXED
We visualize the features of DNN trained by CE when encoder is not fixed. Figure 9 shows the Tsne visualization of features before linear classifier under different noise rate. It can be seen, as analyzed
in the paper, due to non-convexity and great over-fitting capability of f (encoder), the features of f(X) have already been contaminated by the label noise before linear classifier, thus CE on vanilla (X, Ỹ ) is not robust.

heading: D.6 THE EFFECT OF DIFFERENT SSL-PRETRAINED METHODS
text: Our analyses and experiments are not restricted to any specific SSL method. Experimentally, other SSL methods are also adoptable to pre-train SSL encoders. In Figure 3, SimCLR (Chen et al., 2020) is adopted to pre-train SSL encoder. For a comparison, we pre-train a encoder with Moco (He et al., 2020) on CIFAR10 and fine-tune linear classifier on noisy labels in Table 3.
It can be observed that different SSL methods have very similar results, which further verifies our Theorems in the paper.

heading: D.7 EXPERIMENTS ON HUMAN-ANNOTATED NOISY DATASET
text: We perform experiments on CIFAR100-N (A challenging human-annotated noisy dataset) (Wei et al., 2021) with structure regularization. From Table 4, it can be observed that by using SSL features, Structure Regularization can outperform many benchmark methods on real-world human annotated noisy dataset.

heading: E DETAILED SETTING OF EXPERIMENTS
text: Datasets: We use DogCat, CIFAR10 and CIFAR100 for experiments. DogCat has 25000 images. We randomly choose 24000 images for training and 1000 images for testing. For CIFAR10 and CIFAR100, we follow standard setting that use 50000 images for training and 10000 images for testing.
Setting in Section 3: SimCLR is deployed for SSL pre-training with ResNet50 for DogCat and ResNet34 for CIFAR10 and CIFAR100. Each model is pre-trained by 1000 epochs with Adam optimizer (lr = 1e-3) and batch-size is set to be 512. During fine-tuning, we fix the encoder and only fine-tune the linear classifier on noisy dataset with Adam (lr = 1e-3) for 100 epochs and batch-size is set to be 256.
Setting in Section 4: The basic hyper-parameters are identical to Section 3, except when we train from scratch (random initialization), learning rate is set to be 0.1 at initial state and is decayed by 0.1 at 50 epochs. In Equation (7), we use MSE loss for measuring the relations between SL features and SSL features. However, since MSE loss may cause gradient exploration when prediction is far from ground-truth, we use smooth l1 loss instead. Smooth l1 loss is an enhanced version of MSE loss. When prediction is not very far from ground-truth, smooth l1 loss is MSE, and MAE when prediction is far.
The code with running guideline has already been attached in the supplementary material.

heading: F GENERALIZE THEOREM 1 TO MULTI-CLASS CLASSIFICATION
text: Theorem 5 For K-class classification, let g1 = arg ming∈G ED[CE(g(f(X)), Y )], g2 = arg ming∈G ED̃[CE(g(f(X)), Ỹ )]. Then if symmetric noise ratio < K−1 K , for each sample xi, we have arg max
k g1(f(xi))k = arg max k g2(f(xi))k (26)
where f is fixed encoder and g is the linear classifier, g(f(·)) denotes the network output after softmax layer.
proof: Following the proof for Theorem 1, suppose gBayes1 and g Bayes 2 are Bayes optimal classifiers under P(f(X), Y ) and P(f(X), Ỹ ), respectively. We aim to show gBayes1 and g Bayes 2 are consistent. I.e., the decision boundaries are the same.
Denote Xi = X|Y = i. Define pi(x) to be the distribution of f(Xi). According to the bayes rules:
P(Y = i|x) = P(Y = i) · pi(x)∑K j=1P (Y = j) · pj(x)
(27)
Let X be the space of f(X): X = X1 ∪ X2 · · · ∪ XK (28)
where Xi = {x ∈ f(X)|P(Y = i|x) > P(Y = j|x), i 6= j}. Let p i(x) be the distribution of samples whose observed labels are i under symmetric label noise rate . We have:
p i(x) = mi · P(Y = i) · (1− ) · pi(x) +∑ j 6=i P(Y = j) · K − 1 · pj(x)  (29) where mi is the normalization term to make distribution valid. Specifically, mi = 1 P(Y=i)·(1− )+ ∑ j 6=i P(Y=j)· K−1 . Under label noise, P(Ỹ = i) = P(Y = i) · (1− ) + ∑ j 6=i P(Y = j) · K−1 = 1 mi . According to the bayes rules, we have:
P(Ỹ = i|x) = P(Ỹ = i) · p i(x)∑K
j=1P (Ỹ = j) · p j(x) (30)
Let X = X 1 ∪ X 2 · · · ∪ X K , where X i = {x ∈ f(X)|P(Ỹ = i|x) > P(Ỹ = j|x), i 6= j}. To prove gBayes1 and g Bayes 2 are consistent, it is equivalent to show Xi = X i when < K−1K .
Without loss of generality, we prove X1 = X 1 when < K−1K . When j 6= 1, we have:
P(Ỹ = 1|x)− P(Ỹ = j|x)
= (1− − K−1 ) · P(Y = 1) · p1(x)− (1− − K−1 ) · P(Y = j) · pj(x)
normalization
(31)
Since X1 = {x ∈ f(X)|P(Y = 1|x) > P(Y = j|x), j 6= 1}, X1 = X 1 if 1 − − K−1 > 0, i.e., < K−1K .
Proof Done.
G ILLUSTRATING BAYES CLASSIFIER IS NOT CONSISTENT UNDER ASYMMETRIC AND INSTANCE LABEL NOISE
Asymmetric label noise: We give an example on K-class classification (K=3). Following the definition and notation in Section F, suppose the asymmetric label noise ratio is , which is generated between two adjacent label (1⇔ 2,2⇔ 3,3⇔ 1), we have:
P(Ỹ = 1|x)− P(Ỹ = 2|x)
= (1− ) · P(Y = 1) · p1(x)− (2 · − 1) · P(Y = 2) · p2(x)− · P(Y = 3) · p3(x)
normalization
(32)
P(Ỹ = 1|x)− P(Ỹ = 3|x)
= (1− 2 · ) · P(Y = 1) · p1(x)− · P(Y = 2) · p2(x)− (1− ) · P(Y = 3) · p3(x)
normalization
(33)
SinceX1 = {x ∈ f(X)|P(Y = 1|x) > P(Y = j|x), j 6= 1} andX 1 = {x ∈ f(X)|P(Ỹ = 1|x) > P(Ỹ = j|x), j 6= 1} , it is easy to verify X1 = X 1 only when = 0. Thus asymmetric label noise does not induce consistent Bayes classifier. We also provide an experiment on CIFAR10 to further verify our analysis in Table 5. It can be seen that for asymmetric label noise, there is only marginal improvement compared to symmetric label noise in Figure 3.
Instance-dependent label noise: Instance-dependent label noise behaves like symmetric label noise, i.e., the noisy labels may exist in all the classes. However, the noise ratio for each class is not the same and dependent on the features. From Section F, when noise ratio for each class is not the same, the Bayes classifier is not consistent. However, from Table 1 and Section C we theoretically and experimentally show that simple down-sampling strategy can approximate condition in Theorem 1 and Theorem 5 which is helpful for instance level label noise.

Review summaries:
This paper studies how self-supervised pre-training impacts the resistance of the neural network to noisy labels. The paper provides both theoretical analyses and numerical experiments of their study.  The main contribution of the provided study is (i) given a quality encoder pre-trained from SSL, a simple linear layer trained by the cross-entropy loss is theoretically robust to symmetric label noise (ii) providing insights for how knowledge distilled from SSL features can alleviate the over-fitting problem.

The authors illustrate why self-supervised learning can help learning in training with noisy labels. The main contributions are: 1. The authors illustrate theoretically why learning good representation can help learning with noisy labels 2. The authors describe why fixed encoders are important. 3. The authors motivate a regularizer between the SL and SSL.

This paper studies the usefulness of self-supervised features when encountering data with noisy labels. It presents an array of ideas on this topic: including the question of fine-tuning pre-trained representations, using ideas from distillation as regularisation to improve generalisation. Some theoretical and empirical results are relating to the authors arguments.