#  Investigating Why Contrastive Learning Benefits Robustness
against Label Noise

Yihao Xue  Kyle Whitecross  Baharan Mirzasoleiman

###### Abstract

Self-supervised Contrastive Learning (CL) has been recently shown to be very
effective in preventing deep networks from overfitting noisy labels. Despite
its empirical success, the theoretical understanding of the effect of
contrastive learning on boosting robustness is very limited. In this work, we
rigorously prove that the representation matrix learned by contrastive
learning boosts robustness, by having: (i) one prominent singular value
corresponding to each sub-class in the data, and significantly smaller
remaining singular values; and (ii) a large alignment between the prominent
singular vectors and the clean labels of each sub-class. The above properties
enable a linear layer trained on such representations to effectively learn the
clean labels without overfitting the noise. We further show that the low-rank
structure of the Jacobian of deep networks pre-trained with contrastive
learning allows them to achieve a superior performance initially, when fine-
tuned on noisy labels. Finally, we demonstrate that the initial robustness
provided by contrastive learning enables robust training methods to achieve
state-of-the-art performance under extreme noise levels, e.g., an average of
27.18% and 15.58% increase in accuracy on CIFAR-10 and CIFAR-100 with 80%
symmetric noisy labels, and 4.11% increase in accuracy on WebVision.

Machine Learning, ICML

##  1 Introduction

Large datasets have enabled deep neural networks to achieve a remarkable
success in various domains, such as vision and natural language processing
(Deng et al., 2009; Floridi & Chiriatti, 2020). However, this success is
highly dependent on the quality of the training labels. As datasets grow,
manual labeling of data becomes prohibitive and the commonly used web-
crawling, crowd-sourcing, and automated data labeling techniques result in
noisy labels being ubiquitous in large real-world datasets (Krishna et al.,
2016). Over-parameterized networks trained with first-order gradient methods
can fit any (even random) labeling of the training data (Zhang et al., 2016).
Hence, noisy labels drastically degrade the generalization performance of deep
models. To address this, techniques than can robustly learn from noisy labeled
data has attracted a lot of attention in recent years (Zheltonozhskii et al.,
2022; Li et al., 2020; Zhang et al., 2020; Cao et al., 2020; Mirzasoleiman et
al., 2020).

Classical work on robust learning from noisy labels is mainly focused on
estimating the noise transition matrix (Goldberger & Ben-Reuven, 2016; Patrini
et al., 2017), designing robust loss functions (Ghosh et al., 2017; Van Rooyen
et al., 2015; Wang et al., 2019; Zhang & Sabuncu, 2018), correcting noisy
labels (Ma et al., 2018; Reed et al., 2014; Tanaka et al., 2018; Li et al.,
2020), using explicit regularization techniques (Cao et al., 2020; Zhang et
al., 2020, 2017; Liu et al., 2020), and selecting or reweighting training
examples (Chen et al., 2019; Han et al., 2018; Jiang et al., 2018; Malach &
Shalev-Shwartz, 2017; Ren et al., 2018; Wang et al., 2019; Mirzasoleiman et
al., 2020). However as the level of noise increases, these techniques become
highly ineffective.

Very recently, self-supervised contrastive learning has shown a lot of promise
in boosting robustness of deep networks against noisy labels. Contrastive
learning discards all the labels, and learns representations by maximizing
agreement between differently augmented views of the same data point via a
contrastive loss in the latent space (Chen et al., 2020). Then a linear layer
is trained on the representations with the (potentially noisy) labels in a
supervised manner. Empirically, networks trained in this way enjoy a superior
degree of robustness against noisy labels (Zheltonozhskii et al., 2022;
Hendrycks et al., 2019; Ghosh & Lan, 2021).

Despite its empirical success, the theoretical understanding of the effect of
contrastive learning on improving robustness of deep networks against noisy
labels is very limited. To the best of our knowledge, the only existing
theoretical result is on training a binary classifier on pre-trained
embeddings obeying a Gaussian distribution (Cheng et al., 2021). The
corresponding theory is, however, derived under very limited assumptions, and
does not use any properties of self-supervised or contrastive learning.

In this work, we address the above limitations by theoretically characterizing
the beneficial properties of representations obtained by contrastive learning
for enhancing robustness against noisy labels. We prove that contrastive
learning produces a representation matrix that has: (i) a prominent singular
value corresponding to each sub-class in the data, and significantly smaller
remaining singular values; and (ii) a large alignment between the prominent
singular vectors and the ground-truth labels. Then we analyze the case where a
linear model is trained on the obtained representations with labels that are
either perturbed with Gaussian noise, or flipped at random to other classes.
We show that noise has minimal effect on learning the clean labels and the
model can hardly memorize the wrong labels.

We further show that deep networks pre-trained with contrastive learning and
fine-tuned on noisy labels can achieve a superior performance initially,
before overfitting the noise. This is attributed to the initial low-rank
structure of the Jacobian. Contrastive pre-training produces a Jacobian matrix
with a larger gap between the prominent singular values and the remaining
smaller ones, compared to a randomly initialized network. This gap effectively
slows down overfitting at the early phase of training. Finally, we demonstrate
that the initial robustness provided by contrastive learning can be further
leveraged by robust methods to achieve state-of-the-art performance under
extreme levels of noise. Such methods do not let the low-rank Jacobian matrix
to overfit the noise, even after a long number of training iterations.

We conduct extensive experiments on noisy CIFAR-10 and CIFAR-100 (Krizhevsky &
Hinton, 2009), where noisy labels are generated by random flipping the
original ones, and the mini Webvision datasets (Li et al., 2017) which is a
benchmark consisting of images crawled from websites, containing real-world
noisy labels. We show that contrastive learning enables robust training
methods to achieve state-of-the-art performance, e.g., an average of 27.18%
and 15.58% increase in accuracy on CIFAR-10 and CIFAR-100 with 80% symmetric
noisy labels, and 4.11% increase in accuracy on WebVision.

##  2 Additional Related Work

##### Contrastive learning and robustness against noise.

Recent empirical results demonstrated the effectiveness of self-supervised
learning in improving robustness of deep models against adversarial examples,
label corruption and input corruption (Hendrycks et al., 2019). Contrastive
learning has been also shown to boost robustness of existing supervised
methods (Ghosh & Lan, 2021; Zheltonozhskii et al., 2022) to learn with noisy
labels. Notably, Zheltonozhskii et al. (2022) found a large improvement by
combining contrastive learning with two state-of-the-art methods, namely ELR
(Liu et al., 2020) and DivideMix (Li et al., 2020).

Despise the recent success of contrastive learning in improving robustness of
deep networks, a theoretical explanation is yet to be found. Very recently,
Cheng et al. (2021) analyzed the performance of a linear binary classifier
trained on the embeddings obtained by self-supervised learning. However, their
results are based on the assumption that the embeddings follow a Gaussian
distribution. Nevertheless, the validity of such assumption and its relation
to self-supervised learning is not justified. In contrast, we rigorously prove
that contrastive learning extracts the underlying sub-class structure from the
augmented data distribution and encodes it into the embeddings. This
guarantees the robustness of the downstream supervised learning task.

##### Theoretical works on self-supervised learning.

A recent line of theoretical works have studied self-supervised learning
(Arora et al., 2019; Tosh et al., 2021; HaoChen et al., 2021). In particular,
it is shown that under conditional independence between positive pairs given
the label and/or additional latent variables, representations learned by
reconstruction-based self-supervised learning algorithms can achieve small
errors in the downstream linear classification task (Arora et al., 2019; Tosh
et al., 2021). More closely related to our work is the recent result of
HaoChen et al. (2021) that analyzed contrastive learning without assuming
conditional independence of positive pairs. Based on the concept of
augmentation graph, they showed that spectral decomposition on the augmented
distribution leads to embeddings with provable accuracy guarantees under
linear probe evaluation. Here, we further leverage the properties of the
augmentation graph and provide rigorous robustness guarantees for the
performance of linear models trained with representations learned by self-
supervised contrastive learning on noisy labels.

##  3 Problem Formulation and Background

Suppose we have a dataset
$\mathcal{D}=\\{(\boldsymbol{x}_{i},\boldsymbol{y}_{i})\\}_{i=1}^{n}$, where
$(\boldsymbol{x}_{i},\boldsymbol{y}_{i})$ denotes the $i$-th sample with input
$\boldsymbol{x}_{i}\in\mathbb{R}^{d}$ and its clean one-hot encoded label
$\boldsymbol{y}_{i}\in\mathbb{R}^{K}$ corresponding to one of the $K$ classes.
For example, for a data point $\boldsymbol{x}_{i}$ from class $j\in[K]$, we
have $\boldsymbol{y}_{i}=\boldsymbol{e}_{j}$ where $\textbf{e}_{j}$ denotes
the vector with a 1 in the $j$th coordinate and 0’s elsewhere. We further
assume that there are $\bar{K}\geq K$ sub-classes in the data. Sub-classes of
a class share the same label, but are distinguishable from each other. For
example, apple and orange could be two sub-classes of the class fruit.

We assume that for every data point $\boldsymbol{x}_{i}$, we only observe a
noisy version of its label $\hat{\boldsymbol{y}}_{i}$. The noise
$\Delta\boldsymbol{y}_{i}$ can be either generated from a Gaussian
distribution
$\Delta\boldsymbol{y}_{i}=\mathcal{N}(0,\sigma^{2}\boldsymbol{I}_{n}/K)$, or
by randomly flipping the label to one of the other classes. For example for a
data point $\boldsymbol{x}_{i}$ whose label is flipped from class $j$ to $k$,
we have $\Delta\boldsymbol{y}_{i}=\boldsymbol{e}_{k}-\boldsymbol{e}_{j}$. We
denote by $\boldsymbol{Y},\hat{\boldsymbol{Y}}\in\mathbb{R}^{n\times K}$ the
matrices of all the one-hot encoded clean and noisy labels of the training
data points.

We consider the case where the representations are learned with self-
supervised contrastive learning, and then a linear layer is trained with the
representations on the noisy labels.

###  3.1 Self-supervised Contrastive Learning

Self-supervised contrastive learning learns representations of different data
points by maximizing agreement between differently augmented views of the same
example and minimizing agreement between differently augmented views of
different examples. This is achieved via a contrastive loss in the latent
space, as we discuss below.

##### Augmentation graph.

The augmentations of different data points can be used to construct the
population augmentation graph (HaoChen et al., 2021), whose vertices are all
the augmented data points in the population distribution, and two vertices are
connected with an edge if they are augmentations of the same natural
(original) example. Hence, ground-truth classes naturally form connected sub-
graphs. Formally, let $P$ be the distribution of all natural data points (raw
inputs without augmentation). For a natural data point $\boldsymbol{x}^{*}\sim
P$, let $\mathcal{A}(\cdot|\boldsymbol{x}^{*})$ be the distribution of
$\boldsymbol{x}^{*}$’s augmentations. For instance, when $\boldsymbol{x}^{*}$
represents an image, $A(.|\boldsymbol{x}^{*})$ can be the distribution of
common augmentations (Chen et al., 2020) including Gaussian blur, color
distortion and random cropping. Then, for an augmented data point
$\boldsymbol{x}$, $\mathcal{A}(\boldsymbol{x}|\boldsymbol{x}^{*})$ is the
probability of generating $\boldsymbol{x}$ from $\boldsymbol{x}^{*}$. The edge
weights
$w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}=\mathbb{E}_{\boldsymbol{x}^{*}\sim
P}[\mathcal{A}(\boldsymbol{x}_{i}|\boldsymbol{x}^{*})\mathcal{A}(\boldsymbol{x}_{j}|\boldsymbol{x}^{*})]$
can be interpreted as the marginal probability of generating
$\boldsymbol{x}_{i}$ and $\boldsymbol{x}_{j}$ from a random natural data
point.

##### Contrastive loss.

The embeddings produced by contrastive learning can be viewed as a low-rank
approximation of the normalized augmentation graph. Effectively, minimizing a
loss that performs spectral decomposition on the population augmentation graph
can be succinctly written as a contrastive learning objective
$\mathfrak{C}(f)$ on neural network representations (HaoChen et al., 2021):

$\displaystyle\mathfrak{C}(f)\\!=\\!-2\mathbb{E}_{\boldsymbol{x},\boldsymbol{x}^{+}}[f(\boldsymbol{x})^{\top}\\!\\!\\!,f(\boldsymbol{x}^{+})]+\mathbb{E}_{\boldsymbol{x},\boldsymbol{x}^{-}}\\![\big{(}(f(\boldsymbol{x})^{\top}\\!\\!\\!,f(\boldsymbol{x}^{-})\big{)}^{2}],$
(1)

where $f(\boldsymbol{x})\in\mathbb{R}^{p}$ is the neural network
representation for an input $\boldsymbol{x}$, and
$\boldsymbol{x},\boldsymbol{x}^{+}$ are drawn from the augmentations of the
same natural data point, and $\boldsymbol{x},\boldsymbol{x}^{-}$ are two
augmentations generated independently either from the same data point or two
different data points. The above loss function is similar to many standard
contrastive loss functions (Oord et al., 2018; Sohn, 2016; Wu et al., 2018),
including SimCLR (Chen et al., 2020) that we will use in our experiments.
Minimizing this objective leads to representations with provable accuracy
guarantees under linear probe evaluation. We use $f_{\min}$ to denote the
minimizer, i.e., $f_{\min}=\operatorname*{arg\,min}_{f}\mathfrak{C}(f)$.

###  3.2 Training the Linear Head with Label Noise

Here, we introduce the notations for training a linear classifier on the
representations learned by contrastive learning, based on which we perform
theoretical analysis. In Section 4.2, we discuss how our idea can be extended
to understand the performance of fine-tuning all the layers of the neural
network.

We assume the representations are given by $f_{\min}$, the global minimizer of
the contrastive loss. In practice, this is easier to be achieved by larger
networks trained for longer (Chen et al., 2020). In Section 5.1, we confirm
superior robustness of representations learned by larger networks against
noisy labels by our experiments. Given a matrix
$\boldsymbol{F}\in\mathbb{R}^{n\times p}$ where each row
$\boldsymbol{F}_{i}=f_{\min}(\boldsymbol{x}_{i})^{\top}$ is the learned
representation of a data point $\boldsymbol{x}_{i}$, we consider the
downstream task of training a linear model, parameterized by
$\boldsymbol{W}\in\mathbb{R}^{p\times K}$, to minimize the MSE loss with
$l_{2}$ regularization with parameter $\beta$

$\min_{\boldsymbol{W}\in\mathbb{R}^{p\times
K}}\|\hat{\boldsymbol{Y}}-\boldsymbol{F}\boldsymbol{W}\|_{F}^{2}+\beta\|\boldsymbol{W}\|.$
(2)

Let $\hat{\boldsymbol{W}}^{*}$ denote the solution that has the following
closed-form expression

$\displaystyle\hat{\boldsymbol{W}}^{*}=(\boldsymbol{F}^{\top}\boldsymbol{F}+\beta\boldsymbol{I})^{-1}\boldsymbol{F}^{\top}\hat{\boldsymbol{Y}}.$
(3)

While we use MSE in our analysis, we empirically show that our results hold
for other losses, such as cross-entropy.

##  4 Contrastive learning Boosts Robustness

In this section we first show that training a linear head on representations
learned by contrastive learning is provably robust to label noise. Then we
look into the phenomenon that fine-tuning the deep network pre-trained by
contrastive learning achieves a superior performance at early phase of
training. Finally, we discuss how the initial robustness provided by
contrastive learning boosts robust training methods, and corroborate this with
extensive experiments in Section 5.

Figure 1: Training accuracy w.r.t. ground-truth labels and test accuracy of a
linear classifier trained on representations learned by contrastive learning
(SimCLR). Experiments are conducted on CIFAR-10 (C10) and CIFAR-100 (C100)
under different noise levels. Dashed lines show loss and accuracy on training
set w.r.t. ground-truth labels and solid lines show test loss and accuracy.

###  4.1 Provable Robustness of the Linear Head

To understand the robustness provided by contrastive learning, we assume
certain properties of the augmentation graph and analyze the low-rank
structure of the the resulting representation matrix. In particular, we
utilize the following natural assumptions that formalize the following two
properties on the data augmentation: (1) the augmented examples of one sub-
class are similar to each other; and (2) the augmented examples of one sub-
class are different from the augmented examples of other sub-classes.

######  Assumption 4.1 (Compact sub-class structure).

For a triple of augmented examples $\boldsymbol{x}_{j}$, $\boldsymbol{x}_{s}$
and $\boldsymbol{x}_{t}$ from the same sub-class, the marginal probability of
$\boldsymbol{x}_{s}$, $\boldsymbol{x}_{j}$ being generated from a natural data
point is close to that of $\boldsymbol{x}_{t}$, $\boldsymbol{x}_{j}$.
Formally, we have
${w_{\boldsymbol{x}_{s}\boldsymbol{x}_{j}}}/{w_{\boldsymbol{x}_{t}\boldsymbol{x}_{j}}}\in[\frac{1}{1+\delta},1+\delta]$,
for small $\delta\in[0,1)$.

######  Assumption 4.2 (Distinguishable sub-class structure).

For two pairs of augmentated examples
$(\boldsymbol{x}_{i},\boldsymbol{x}_{j})$ and
$(\boldsymbol{x}_{s},\boldsymbol{x}_{t})$ where $\boldsymbol{x}_{i}$,
$\boldsymbol{x}_{j}$ are from different sub-classes and $\boldsymbol{x}_{s}$,
$\boldsymbol{x}_{t}$ are from the same sub-class, the marginal probability of
$\boldsymbol{x}_{i}$, $\boldsymbol{x}_{j}$ being generated from a natural data
is much smaller than that of $\boldsymbol{x}_{s}$, $\boldsymbol{x}_{t}$.
Formally, we have
$w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}/{w_{\boldsymbol{x}_{s}\boldsymbol{x}_{t}}}\leq\xi$,
for small $\xi\in[0,\\!1)$.

The above assumptions result in an augmentation graph where augmented data
points from different subclasses form nearly disconnected subgraphs with
similar edge weights. In particular for $\xi=0$, we get diconnected subgraph
structure.

####  4.1.1 Desirable Properties of Cl Representations

The key to our analysis is that, based on compact and distinguishable sub-
class structure assumptions 4.1, 4.2, contrastive learning produces a low-rank
representation matrix $\boldsymbol{F}$ that captures the sub-class structure.
More formally, the representation matrix has $\bar{K}$ singular vectors that
align well with the ground-truth labels, and the corresponding $\bar{K}$
singular values are significant larger than the other singular values. The
following theorem is a summary of Lemmas A.2 A.3 B.2 B.3 and Corollary A.6 in
the Appendix which details the desirable properties of the representation
matrix.

######  Theorem 4.3.

Having $\bar{K}$ compact and distinguishable sub-classes in the data, the
representation matrix $\boldsymbol{F}$ learned by contrastive learning has
$\bar{K}$ prominent singular values of magnitude $\mathcal{O}(1)$. At the same
time, the sum of the remaining singular values is significantly smaller, i.e.,
$\mathcal{O}(\sqrt{\delta}+\xi)$. Furthermore, the most prominent $\bar{K}$
singular vectors and the ground-truth labels has a $\mathcal{O}(1)$ alignment,
measured by the normalized projection of the clean labels $~{}\boldsymbol{Y}$
onto the span of the singular vectors.

Intuitively, the above three properties of the representation matrix affect
the downstream training in the following sense: (1) the magnitude of largest
singular values determines the speed at which the model evolves as well as the
extent to which the model can fit the training data; (2) the alignment between
prominent singular vectors and clean labels indicates whether the model
evolves in the right direction; and (3) the magnitude of smaller singular
values dictates the amount of overfitting. As a result, Theorem 4.3 implies
that the model trained on such representation learns mainly the correct
information from the training data, which we formally show in Theorems 4.4 and
4.5.

####  4.1.2 Training performance w.r.t. Ground-truth Labels Reflects
Robustness

To simplify the theoretical analysis, instead of studying the generalization
performance (usually measured by the expected loss over the data
distribution), we will examine the loss and accuracy on the training data
w.r.t. ground-truth labels. This strongly correlates with the test accuracy,
especially under large noise. We empirically confirm this correlation in
Figure 1, where the dashed lines show training loss and training accuracy
w.r.t. ground-truth labels, and solid lines show test loss and test accuracy.
We clearly see the high correlation between training and performance, in
particular under significant levels of label noise.

####  4.1.3 Gaussian Label Noise

We first consider the case where label noise is generated from a Gaussian
distribution. Formally,
$\hat{\boldsymbol{Y}}=\boldsymbol{Y}+\Delta\boldsymbol{Y}$, where
${\boldsymbol{Y}}$ is the clean label matrix containing all the one-hot
encoded labels, and $\Delta\boldsymbol{Y}$ is the label noise matrix, where
each column drawn independently from
$\mathcal{N}(0,\sigma^{2}\mathbf{I}_{n}/{K})$. We consider this setting first,
as it provides the most convenient way to analyze robustness. Here, our
analysis mainly aims at breaking down the effect of label perturbations on
training dynamics, in terms of bias and variance. This could provide
theoretical insights into the benefits of contrastive learning for boosting
robustness.

The following theorem bounds the expected error on training data w.r.t.
ground-truth labels, and shows how contrastive learning exploits the augmented
sub-class structure to improve robustness.

######  Theorem 4.4.

For a dataset of size $n$ with $K$ classes, $\bar{K}$ balanced compact and
distinguishable sub-classes (c.f. assumptions 4.2, 4.1) and labels corrupted
with Gaussian noise $\mathcal{N}(0,\sigma^{2}\mathbf{I}_{n}/{K})$, a linear
model trained by minimizing the objective in Eq. (2) with the representations
obtained by minimizing contrastive loss in Eq. (1) has the following expected
error on the training set w.r.t. the ground-truth labels $\boldsymbol{Y}$:

$\displaystyle\mathbb{E}_{\Delta\boldsymbol{Y}}\frac{1}{n}\|\boldsymbol{Y}-\boldsymbol{F}\hat{\boldsymbol{W}}^{*}\|_{F}^{2}$
(4) $\displaystyle\leq$
$\displaystyle\underbrace{(\frac{\beta}{\beta+1})^{2}+\mathcal{O}(\delta+\xi)}_{\textbf{bias}^{2}}+\underbrace{\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\sigma^{2}\mathcal{O}(\frac{\sqrt{\delta}+\xi}{\beta})}_{\textbf{variance}}.$

We note that the above results can be easily extended to imbalanced sub-class
structure.

The proof can be found in the Appendix. The proof follows the intuition
discussed in Section 4.1.1 that the desirable properties of the learned
representation benefit the downstream training. In a nutshell, we derive the
bound by writing the error in terms of singular values and vectors of
$\boldsymbol{F}$ and then applying Theorem 4.3.

In Eq. (4), the error is decomposed into bias and variance. The bias captures
the mismatch between the average prediction of the model and the ground-truth
labels. It depends on the magnitude of the prominent singular values as well
as the alignment of the corresponding singular vectors with the ground-truth
labels. Contrastive learning reduces the bias by aligning the first $\bar{K}$
singular vectors with ground-truth labels (Theorem 4.3), thus producing a
small second term in the bias. The variance quantifies the sensitivity to
label noise, and is controlled by the magnitude of the non-prominent singular
values, which is guaranteed to be small by Theorem 4.3. The regularization
parameter $\beta$ appears in both terms and can be tuned as a trade-off
between underfitting and overfitting.

With small enough $\delta$ and $\xi$, one can select a small $\beta$ to not
explicitly penalize the variance much. This results in a small bias, and
subsequently a small total error. For example, when there exists a $\beta$
such that $\sqrt{\delta}+\xi\ll\beta\ll 1$, the error
$\approx\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}$, which is the
inevitable cost of achieving a small bias, when the representation matrix
$\boldsymbol{F}$ has $\bar{K}$ prominent singular values.

(a)  (b)  (c)  (d)

Figure 2: Jacobian spectrum and dynamics of training a randomly initialized
vs. fine-tuning a pre-trained ResNet32 on CIFAR-10 with 80% randomly flipped
labels. (a) distribution of singular values of the initial Jacobian, (b)
alignment of the clean labels with the initial Jacobian, (c) test accuracy and
(d) loss on mislabeled data points within the first 50 epochs. While pre-
training does not improve the alignment of the Jacobian with the labels, it
significantly slows down overfitting at the beginning by shrinking the smaller
singular values of the Jacobian matrix.

####  4.1.4 Random Label Flipping

Next, we study the case where the label noise
$\Delta\boldsymbol{Y}\\!=\\!\hat{\boldsymbol{Y}}\\!-\\!\boldsymbol{Y}$ is
generated by flipping a fraction of the clean labels at random. Formally, for
an example $\boldsymbol{x}_{i}$ belongs to class $j$ with
$\boldsymbol{y}_{i}=\boldsymbol{e}_{j}$, if its label is flipped to class $k$,
we have $\Delta\boldsymbol{y}_{i}=\boldsymbol{e}_{k}-\boldsymbol{e}_{j}$. We
introduce the following notations to analyze the case of asymmetric label
noise which mimics the real-world noise, where wrong labels are generated in a
(sub)class-dependent way. Let $m_{\bar{k}}$ be the number of mislabeled
examples in subclass $\bar{k}$, $m_{\bar{k},k}$ be the number of mislabeled
examples in subclass $\bar{k}$ that are labeled as class $k$, and $Z_{k}$ be
the set of sub-classes in class $k$. We define
$c_{k|\bar{k}}\coloneqq\frac{m_{\bar{k},k}}{m_{\bar{k}}}$ for all
$\bar{k}$,$k$ such that $\bar{k}\notin Z_{k}$, to be the fraction of
mislabeled examples in sub-class $\bar{k}$ that are mislabeled as $k$. We have
that $\sum_{k:~{}\bar{k}\notin
Z_{k}}c_{k|\bar{k}}=1,~{}\forall\bar{k}\in[\bar{K}]$. When
$c_{k|\bar{k}}=\frac{1}{K-1}~{}~{}\forall k\in[K],\bar{k}\in[\bar{K}]$, the
noise is symmetric.

For simplicity we assume $\xi=0$. The general case of $\xi\geq 0$ requires
more involved analysis which we discuss in the Appendix. The following theorem
shows that for a dataset with compact and distinguishable sub-class structure
the linear classifier trained on the representations obtained by contrastive
learning can recover the clean label for all training data.

######  Theorem 4.5 (Asymmetric Noise).

For a dataset with ${K}$ classes and $\bar{K}$ compact and distinguishable
sub-class structure (c.f. assumptions 4.2 4.1) with $\xi=0$, let
$n_{\min},n_{\max}$ be the size of the smallest and largest sub-class, and
$\alpha$ be the fraction of mislabeled examples in the training set. Let
$c_{\max}\coloneqq\max_{k\in[K],\bar{k}\in[\bar{K}]}c_{k|\bar{k}}\in[\frac{1}{K-1},1]$
be the maximum fraction of wrong labels in a subclass that are flipped to
another class. Then as long as

$\displaystyle{\alpha<\frac{1}{1+\frac{n_{\max}}{n_{\min}}c_{\max}}-\mathcal{O}\left(\frac{\sqrt{\delta}}{\beta}\right),}$
(5)

a linear model trained by minimizing the objective in Eq. (2) with the
representations obtained by minimizing contrastive loss in Eq. (1) can predict
the ground-truth labels for all training examples, i.e.,

$\displaystyle\forall
i,~{}\operatorname*{arg\,max}_{j\in[K]}(\boldsymbol{F}\hat{\boldsymbol{W}})_{i,j}\\!\\!=\\!\arg_{j\in[K]}({\boldsymbol{Y}}_{i,j}=1)\\!\\!.$

In other words contrastive learning can prevent the linear model from
memorizing any wrong label even under large noise. Theorem 4.5 also shows that
the model can tolerate more noise when the sub-class structure is more
compact, i.e., $\delta$ is smaller, or the noise is more symmetric, or the
sub-classes are more balanced. The following corollary for symmetric noise is
simply obtained by setting $c_{\max}=\frac{1}{K-1}$ in Theorem 4.5.

######  Corollary 4.6 (Symmetric Noise).

For symmetric noise, under the same assumption as in Theorem 4.5, as long as

$\displaystyle{\alpha<\frac{K\\!-\\!1}{K+\frac{n_{\max}}{n_{\min}}-1}-\mathcal{O}\left(\sqrt{\delta}\right),}$
(6)

a linear model trained by minimizing the objective in Eq. (2) with the
representations obtained by minimizing contrastive loss in Eq. (1) can predict
the ground-truth labels for all training examples.

If we further let $\delta=0$ and $n_{\max}/n_{\min}=1$, we get $(K-1)/K$ noise
tolerance. We note that this, however, does not imply that a dataset with more
classes necessarily has a higher noise tolerance. In Appendix B.1, we show
that less distinguishable sub-class structure, i.e. $\xi>0$, introduces a
$\mathcal{O}(\bar{K}^{5/2}\xi)$ perturbation to the singular values and a
$\mathcal{O}(\bar{K}^{5/2}\xi)$ rotation in the direction of singular vectors
of the representation matrix. Datasets with more classes usually contains more
sub-classes, which greatly reduces the noise tolerance. This is also reflected
by our empirical results (Figure 1) where the performance of the linear model
is worse on CIFAR-100 compared to CIFAR-10 under the same noise level.

###  4.2 Contrastive Learning Slows down Overfitting for Fine-tuning

In the previous section, we showed that training a linear model on
representations learned by contrastive learning is provably robust. Here, we
study fine-tuning all layers of the deep network. Interestingly, as is shown
in Fig. 2c, finetuning achieves a very high test accuracy under 80% label
noise in the early phase of training.

Recall that the theoretical guarantee for linear model (theorems 4.4 and 4.5)
is obtained by examining singular values and singular vectors of
$\boldsymbol{F}$. Here, we use a similar idea to understand benefits of
contrastive learning on robustness when all the layers are trained.
Intuitively, during the early stage of training, it is natural to assume that
the gradient does not considerably change, and therefore the model is nearly
linear. In this case, the initial Jacobian matrix plays the same role as the
representation matrix, $\boldsymbol{F}$, to the linear model. This is
supported by the recent studies suggesting the following properties of
training neural networks: the early learning dynamics can by mimicked by
training a linear model (Hu et al., 2020), SGD on neural networks learns a
linear model first (Kalimeris et al., 2019), and a network that provides a
better alignment between prominent directions of the Jacobian matrix and the
label vector is more likely to generalize well (Oymak et al., 2019).

We examine the SVD of the Jacobian of a ResNet pretrained with contrastive
learning and compare it to that of a randomly initialized network. Fig. 2a, 2b
present the distribution of singular values and the alignment of singular
vectors with clean labels. The Jacobian is computed on a random sample of 1000
data points from CIFAR10. Interestingly, Fig. 2b shows that while pre-training
does not considerably improve (in Appendix C we show a slight improvement) the
alignment between singular vectors of the Jacobian and the clean label vector,
it greatly shrinks the smaller singular values of the Jacobian, as is
illustrated by Fig. 2a. As a result, it takes substantially longer for the
pre-trained network to overfit the noisy labels. As Fig. 2d shows, while a
randomly initialized network experience a sharp drop in loss of noisy labeled
data points during the first few epochs of training, it takes much longer for
a pre-trained network to overfit the noise. Details of the experiment can be
found in Appendix D.

###  4.3 Contrastive Learning Boosts Robust Methods

As discussed, pre-training the network with contrastive learning effectively
shrinks the smaller singular values of the Jacobian and slows down overfitting
the noisy labels. The initial level of robustness provided by contrastive
learning can be leveraged by existing robust training methods to achieve a
superior performance under extreme noise levels. Next, we briefly discuss
three methods that prevent the pre-trained network from overfitting the noisy
labels, through regularization (Liu et al., 2020; Zhang et al., 2017), or
identifying clean examples (Mirzasoleiman et al., 2020).

##### ELR

(Liu et al., 2020) regularizes the loss by
$\frac{1}{n}\sum_{i=1}^{n}\log(1-\boldsymbol{p}(x_{i})^{\top}\boldsymbol{t}(x_{i}))$
to encourage the alignment between the model prediction $\boldsymbol{p}(x)$
and the running average of the model outputs in previous rounds
$\boldsymbol{t}(x)$. The effectiveness of ELR is attributed to the early-
learning phenomenon where the model first fits the correct labels and then
memorizes the noisy ones (Oymak et al., 2019). Effectively, the regularization
term stretches the prediction toward the clean labels predicted early by the
model. However, under extreme label noise, the memorization phase starts very
early, and does not let the model to learn clean labels and high-quality
targets. As discussed, contrastive learning makes a large separation between
learning and memorization and gives the network enough time to learn high-
quality targets. As we show in our experiments, applying ELR to fine-tune the
network learned by contrastive learning significantly boosts the
generalization performance.

##### Mixup

(Zhang et al., 2017) extends the training distribution by linear
interpolations of feature vectors and their associated labels:
$\hat{\boldsymbol{x}}=\lambda\boldsymbol{x}_{i}+(1-\lambda)\boldsymbol{x}_{j},\hat{\boldsymbol{y}}=\lambda\boldsymbol{y}_{i}+(1-\lambda)\boldsymbol{y}_{j}$,
where $\lambda\sim\text{Beta}(\alpha,\alpha)$. In doing so, mixup makes linear
transition in the decision boundary between classes and provide a smoother
estimate of uncertainty. Larger $\alpha$ prevents overfitting by generating
examples that are less similar to the training examples and are more difficult
for the network to memorize. In our experiments, we show that the network
learned by contrastive learning can be robustly fine-tuned by mixup to achieve
a superior generalization performance.

Table 1: Average test accuracy (3 runs) on CIFAR-10 and CIFAR-100. The best test accuracy is marked in bold. We note the higher performance of methods that use SimCLR (CL) pretraining, especially under higher noise levels. In particular, under $80\%$ noise, methods see an average of $27.18\%$, and $15.58\%$ increase in test accuracy for CIFAR-10 and CIFAR-100 respectively. Results marked with $(^{*})$ are reproduced from publicly available code. E2E refers to end to end fine-tuning the pre-trained network.  Dataset | CIFAR-10 | CIFAR-100
---|---|---
Noise Type | Sym | Asym | Sym | Asym
Noise Ratio | $20$ | $50$ | $80$ | $40$ | $20$ | $50$ | $80$ | $40$
F-correction | $85.1\pm 0.4$ | $76.0\pm 0.2$ | $34.8\pm 4.5$ | $83.6\pm 2.2$ | $55.8\pm 0.5$ | $43.3\pm 0.7$ | $-$ | $42.3\pm 0.7$
Decoupling | $86.7\pm 0.3$ | $79.3\pm 0.6$ | $36.9\pm 4.6$ | $75.3\pm 0.8$ | $57.6\pm 0.5$ | $45.7\pm 0.4$ | $-$ | $43.1\pm 0.4$
Co-teaching | $89.1\pm 0.3$ | $82.1\pm 0.6$ | $16.2\pm 3.2$ | $84.6\pm 2.8$ | $64.0\pm 0.3$ | $52.3\pm 0.4$ | $-$ | $47.7\pm 1.2$
MentorNet | $88.4\pm 0.5$ | $77.1\pm 0.4$ | $28.9\pm 2.3$ | $77.3\pm 0.8$ | $63.0\pm 0.4$ | $46.4\pm 0.4$ | $-$ | $42.4\pm 0.5$
D2L | $86.1\pm 0.4$ | $67.4\pm 3.6$ | $10.0\pm 0.1$ | $85.6\pm 1.2$ | $12.5\pm 4.2$ | $5.6\pm 5.4$ | $-$ | $14.1\pm 5.8$
INCV | $89.7\pm 0.2$ | $84.8\pm 0.3$ | $52.3\pm 3.5$ | $86.0\pm 0.5$ | $60.2\pm 0.2$ | $53.1\pm 0.4$ | $-$ | $50.7\pm 0.2$
T-Revision | $79.3\pm 0.5$ | $78.5\pm 0.6$ | $36.2\pm 1.6$ | $76.3\pm 0.8$ | $52.4\pm 0.3$ | $37.6\pm 0.3$ | $-$ | $32.3\pm 0.4$
L_DMI | $84.3\pm 0.4$ | $78.8\pm 0.5$ | $20.9\pm 2.2$ | $84.8\pm 0.7$ | $56.8\pm 0.4$ | $42.2\pm 0.5$ | $-$ | $39.5\pm 0.4$
Crust∗ | ${{85.3}\pm{0.5}}$ | ${{86.8}\pm{0.3}}$ | ${33.8}\pm{1.3}$ | ${{76.7}\pm{3.4}}$ | ${{62.9}\pm{0.3}}$ | ${{55.5}\pm{1.1}}$ | ${{18.5}\pm{0.8}}$ | ${{52.5}\pm{0.4}}$
Mixup | ${{89.7}\pm{0.7}}$ | ${{84.5}\pm{0.3}}$ | ${40.7}\pm{1.1}$ | ${{86.3}\pm{0.1}}$ | ${{64.0}\pm{0.4}}$ | ${{53.4}\pm{0.5}}$ | ${{15.1}\pm{0.1}}$ | ${{54.4}\pm{2.0}}$
ELR∗ | ${{90.6}\pm{0.6}}$ | ${{87.7}\pm{1.0}}$ | ${69.5}\pm{5.0}$ | ${{86.6}\pm{2.9}}$ | ${{63.6}\pm{1.7}}$ | ${{52.5}\pm{4.2}}$ | ${{23.4}\pm{1.9}}$ | ${{59.7}\pm{0.1}}$
CL+E2E∗ | ${{88.8}\pm{0.5}}$ | ${{82.8}\pm{0.2}}$ | ${72.0}\pm{0.3}$ | ${{83.5}\pm{0.5}}$ | ${{63.5}\pm{0.2}}$ | ${{56.1}\pm{0.3}}$ | $\bf{{{36.7}\pm{0.3}}}$ | ${{52.4}\pm{0.2}}$
CL+Crust∗ | ${{86.5}\pm{0.7}}$ | ${{87.6}\pm{0.3}}$ | $\bf{{77.9}\pm{0.3}}$ | ${{85.9}\pm{0.4}}$ | ${{63.0}\pm{0.8}}$ | $\bf{{{58.3}\pm{0.1}}}$ | ${{34.8}\pm{1.5}}$ | ${{53.3}\pm{0.7}}$
CL+Mixup∗ | ${{90.8}\pm{0.2}}$ | ${{84.6}\pm{0.4}}$ | ${74.8}\pm{0.3}$ | ${{87.5}\pm{1.3}}$ | ${{64.4}\pm{0.4}}$ | ${{55.5}\pm{0.1}}$ | ${{30.3}\pm{0.4}}$ | ${{55.5}\pm{0.8}}$
CL+ELR∗ | $\bf{{{91.3}\pm{0.0}}}$ | ${\bf{{89.1}\pm{0.1}}}$ | ${77.7}\pm{0.2}$ | ${\bf{{89.7}\pm{0.3}}}$ | ${\bf{{64.7}\pm{0.2}}}$ | ${{55.6}\pm{0.2}}$ | ${{35.9}\pm{0.3}}$ | $\bf{{{63.6}\pm{0.1}}}$

##### CRUST

(Mirzasoleiman et al., 2020) provides provable robustness guarantees by
extracting clean examples that cluster closely in the gradient space based on
the following observation: as the nuisance space is very high dimensional,
data points with noisy labels spread out in the gradient space. In contrast,
the information space is low-dimensional and data points with clean labels
that have similar gradients cluster closely together. Central clean examples
in the gradient space can be efficiently extracted by maximizing a submodular
function. To enable Crust to find the clean examples under extreme noise, we
first fine-tune the entire network on noisy labels for around 20 epochs and
then randomly label half of the examples with the prediction of the model. As
discussed, pre-training the network with contrastive learning shrinks the
smaller singular values of the Jacobian. This allows the clean examples to
make clear clusters around the large singular directions and be easily
extracted. In our experiments, we show that the pre-trained network can
significantly boost Crust’s performance under extreme noise.

##  5 Experiments

We evaluate the effectiveness of contrastive learning in boosting the
robustness of deep networks under various levels of label noise. We first
consider fine-tuning all layers of a network pre-trained with contrastive
learning on noisy labels, and show that it can achieve a comparable
generalization performance to the state-of-the-art robust methods. Then, we
show that the structure of the representation matrix obtained by contrastive
learning can be leveraged by robust methods to achieve a superior
generalization performance under extreme noise levels.

For our evaluation, we use artificially corrupted versions of CIFAR-10 and
CIFAR-100 (Krizhevsky & Hinton, 2009), as well as a subset of the real-world
dataset Webvision (Li et al., 2017), which naturally contains noisy labels.
Our method was developed using PyTorch (Paszke et al., 2017). We use 1 Nvidia
A40 for all experiments.

Baselines. We compare our results with many commonly used baselines for robust
training against label noise: (1) F-correction (Patrini et al., 2017) is a two
step process, where a neural network is first trained on noisily-labelled
data, then retrained using a corrected loss function based on an estimation of
the noise transition matrix. (2) Decoupling (Malach & Shalev-Shwartz, 2017) is
a meta-algorithm that trains two networks concurrently, only training on
examples where the two networks disagree. (3) Co-teaching (Han et al., 2018)
also trains two networks simultaneously. Each network selects subsets of clean
data with high probability for the other network to train on. (4) MentorNet
(Jiang et al., 2018) uses two neural networks, a student and a mentor. The
mentor dynamically creates a curriculum based on the student, while the
student trains on the curriculum provided by the mentor. (5) D2L (Ma et al.,
2018) learns the training data distribution, then dynamically adapts the loss
function based on the changes in dimensionality of subspaces during training.
(6) INCV (Chen et al., 2019) identifies random subsets of the training data
with fewer noisy labels, then applies Co-teaching to iteratively train on
subsets found with the most clean labels. (7) T-Revision (Xia et al., 2019)
learns the transition matrix efficiently using an algorithm that does not rely
on known points with clean labels. (8) L_DMI (Xu et al., 2019) uses a novel
information-theoretic loss function based on determinant based mutual
information. (9) ELR (Liu et al., 2020) uses semi-supervised learning
techniques to regularize based on the early-learning phase of training, to
ensure the noisy labels are not overfit. (10) CRUST (Mirzasoleiman et al.,
2020) dynamically selects subsets of clean data points by clustering in the
gradient space. (11) Mixup (Zhang et al., 2017) smooths the decision boundary
by adding linear interpolations of feature vectors and their labels to the
dataset.

###  5.1 Empirical Results on Artificially Corrupted CIFAR

We first evaluate our method on CIFAR-10 and CIFAR-100, which each contain
$50,000$ training images, and $10,000$ test images of size $32\times 32\times
3$. CIFAR-10 and CIFAR-100 have $10$ and $100$ classes respectively. We use
the same testing protocol as (Xu et al., 2019; Liu et al., 2020; Xia et al.,
2019), by evaluating our method on symmetric and asymmetric label noise. For
both CIFAR-10 and CIFAR-100, we use symmetric noise ratios of $0.2$, $0.5$,
$0.8$, and an asymmetric noise ratio of $0.4$.

In our experiments, we first pre-train ResNet-32 (He et al., 2016) using
SimCLR (Chen et al., 2020; SimCLR, ) for 1000 epochs using the Adam optimizer
(Kingma & Ba, 2014) with a learning rate of $3\times 10^{-4}$, a weight decay
of $1\times 10^{-6}$ and a batch size of 128. When pre-training, the last
linear layer of ResNet-32 is replaced with a 2-layer projection head with an
output dimensionality of 64. When pretraining is finished, we replace the
projection head with a new, randomly initialized classification layer, and
begin training normally. We also report the results when ELR, Mixup, and Crust
are applied to fine-tune the pre-trained network. For ELR, we use $\beta=0.7$
for the temporal ensembling parameter, and $\lambda=3$ for the regularization
strength. For mixup, we use a mixup strength of $\alpha=1$. For Crust, we
choose a coreset ratio of $0.5$.

The results are shown in Table 1. We note that SimCLR pretraining leads to an
across the board improvement for Crust, ELR, and Mixup. For lower noise
ratios, the improvement is marginal. However, for extreme noise ratios, the
improvement is more dramatic. In particular, pre-training boosts the
performance of Crust by up to 44.1%, ELR by up to 8.2%, and Mixup by up to
34.1% under 80% noise. We also note that under $80\%$ noise, SimCLR
pretraining alone outperforms all methods without SimCLR pretraining on
CIFAR-10 and CIFAR-100.

Effects of Network Size Empirically, larger networks trained for longer can
achieve smaller contrastive loss (Chen et al., 2020), thus providing a
representation closer to the optimal. In this regard, increasing network size
should further improve the robustness to label noise. We confirm this by
comparing pretrained ResNet34 (with 46x params) and ResNet32 in Table 2. Both
models are fintuned with Mixup. We see that increasing the network size can
greatly improve the performance.

Table 2: Comparison between ResNet34 and ResNet32. We finetune the contrastively pretrained network with Mixup on CIFAR10/100 with different fractions of noise.  Dataset | CIFAR-10 | CIFAR-100
---|---|---
Noise | Sym 80 | Asym 40 | Sym 80 | Asym 40
ResNet-32 |  74.8 $\pm$.3 |  87.5$\pm$1.3 |  30.3$\pm$.4 |  55.5$\pm$.8
ResNet-34 |  90.8$\pm$.6 |  90.4$\pm$.4 |  69.4$\pm$.3 |  65.2$\pm$.2
Table 3: Test accuracy on mini WebVision. The best test accuracy is marked in bold. SimCLR (CL) pre-training leads to average improvements of $4.11\%$ and $3.20\%$ for mini Webvision and ImageNet respectively.  | WebVision | ImageNet
---|---|---
Method | Top-1 | Top-5 | Top-1 | Top-5
F-correction | 61.12 | 82.68 | 57.36 | 82.36
Decoupling | 62.54 | 84.74 | 58.26 | 82.26
Co-teaching | 63.58 | 85.20 | 61.48 | 84.70
MentorNet | 63.00 | 81.40 | 57.80 | 79.92
D2L | 62.68 | 84.00 | 57.80 | 81.36
INCV | 65.24 | 85.34 | 61.60 | 84.98
Crust | 72.40 | 89.56 | 67.36 | 87.84
Mixup | 71.38 | 87.36 | 68.34 | 88.44
ELR | 76.26 | 91.26 | 68.71 | 87.84
CL + E2E | 71.84 | 88.84 | 68.48 | 89.32
CL + Mixup | 76.34 | 90.52 | 72.25 | 89.72
CL + ELR | 79.52 | 93.80 | 71.20 | 90.80

###  5.2 Empirical Results on WebVision

WebVision is large scale image dataset with noisy labels (Li et al., 2017). It
contains 2.4 million images crawled from Google Images search and Flickr that
share the same 1000 classes as the ImageNet dataset. The noise ratio in
classes varies from 0.5% to 88%, and the number of images per class varies
from 300 to more than 10,000 (Fig. 4 in (Li et al., 2017) shows the noise
distribution). We follow the setting in (Jiang et al., 2018) and create a mini
WebVision dataset that consists of the top 50 classes in the Google subset
with 66,000 images. We use both WebVision and ImageNet test sets for testing
the performance of the model. We train InceptionResNet-v2 (Szegedy et al.,
2017) for 120 epochs with a starting learning rate of $0.02$, which we anneal
by a factor of $0.01$ at epochs 40 and 80. We use the SGD optimizer with a
weight decay of $1\times 10^{-3}$, and a minibatch size of 32. For Mixup and
ELR, we use the same hyperparameters as CIFAR.

Table 3 shows the Top-1 and Top-5 accuracy of different methods evaluated on
WebVision and ImageNet. We see that for both ELR and Mixup, SimCLR pretraining
leads to average improvements of $4.11\%$ and $3.20\%$ for mini Webvision and
ImageNet respectively. Furthermore, we note that SimCLR pretraining on its own
outperforms every method without SimCLR pretraining, except ELR and Crust.

##  6 Conclusion

We showed that representations learned by contrastive learning provably boosts
robustness against noisy labels. In particular, contrastive learning provides
a representation matrix that has: (i) a significant gap between the prominent
singular values and the remaining ones; (ii) a large alignment between the
prominent singular vectors and the clean labels. The above properties allow a
linear layer trained on the representations to effectively learn the clean
labels well while barely overfitting the noise. Then we explained why fine-
tuning all layers of a network pre-trained with contrastive learning can also
achieve a good performance in the early phase. Crucially, contrastive learning
greatly reduces the magnitude of nonprominant singular values of the initial
Jacobian matrix, which slows down the overfitting. Finally, we demonstrated
that the initial robustness provided by contrastive learning can boost robust
methods and achieve state-of-the-art performance under extreme noise levels.
Our results confirm benefits of contrastive pretraining for robust machine
learning.

## Acknowledgements

This research was supported in part by Cisco Systems and UCLA-Amazon Science
Hub for Humanity and Artificial Intelligence.

## References

  * Arora et al. (2019) Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N.  A theoretical analysis of contrastive unsupervised representation learning.  _arXiv preprint arXiv:1902.09229_ , 2019.
  * Cao et al. (2020) Cao, K., Chen, Y., Lu, J., Arechiga, N., Gaidon, A., and Ma, T.  Heteroskedastic and imbalanced deep learning with adaptive regularization.  _arXiv preprint arXiv:2006.15766_ , 2020.
  * Chen et al. (2019) Chen, P., Liao, B. B., Chen, G., and Zhang, S.  Understanding and utilizing deep neural networks trained with noisy labels.  In _International Conference on Machine Learning_ , pp. 1062–1070, 2019.
  * Chen et al. (2020) Chen, T., Kornblith, S., Norouzi, M., and Hinton, G.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pp. 1597–1607. PMLR, 2020.
  * Cheng et al. (2021) Cheng, H., Zhu, Z., Sun, X., and Liu, Y.  Demystifying how self-supervised features improve training from noisy labels.  _arXiv preprint arXiv:2110.09022_ , 2021.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  ImageNet: A Large-Scale Hierarchical Image Database.  In _CVPR09_ , 2009.
  * Eckart & Young (1936) Eckart, C. and Young, G.  The approximation of one matrix by another of lower rank.  _Psychometrika_ , 1(3):211–218, 1936.
  * Floridi & Chiriatti (2020) Floridi, L. and Chiriatti, M.  Gpt-3: Its nature, scope, limits, and consequences.  _Minds and Machines_ , 30(4):681–694, 2020.
  * Ghosh & Lan (2021) Ghosh, A. and Lan, A.  Contrastive learning improves model robustness under label noise.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2703–2708, 2021.
  * Ghosh et al. (2017) Ghosh, A., Kumar, H., and Sastry, P.  Robust loss functions under label noise for deep neural networks.  In _Thirty-First AAAI Conference on Artificial Intelligence_ , 2017\.
  * Goldberger & Ben-Reuven (2016) Goldberger, J. and Ben-Reuven, E.  Training deep neural-networks using a noise adaptation layer.  2016\.
  * Han et al. (2018) Han, B., Yao, Q., Yu, X., Niu, G., Xu, M., Hu, W., Tsang, I., and Sugiyama, M.  Co-teaching: Robust training of deep neural networks with extremely noisy labels.  In _Advances in neural information processing systems_ , pp. 8527–8537, 2018.
  * HaoChen et al. (2021) HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T.  Provable guarantees for self-supervised deep learning with spectral contrastive loss.  _arXiv preprint arXiv:2106.04156_ , 2021.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hendrycks et al. (2019) Hendrycks, D., Mazeika, M., Kadavath, S., and Song, D.  Using self-supervised learning can improve model robustness and uncertainty.  _arXiv preprint arXiv:1906.12340_ , 2019.
  * Hu et al. (2020) Hu, W., Xiao, L., Adlam, B., and Pennington, J.  The surprising simplicity of the early-time learning dynamics of neural networks.  _Advances in Neural Information Processing Systems_ , 33:17116–17128, 2020.
  * Jiang et al. (2018) Jiang, L., Zhou, Z., Leung, T., Li, L.-J., and Fei-Fei, L.  Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels.  In _International Conference on Machine Learning_ , pp. 2309–2318, 2018.
  * Kalimeris et al. (2019) Kalimeris, D., Kaplun, G., Nakkiran, P., Edelman, B., Yang, T., Barak, B., and Zhang, H.  Sgd on neural networks learns functions of increasing complexity.  _Advances in neural information processing systems_ , 32, 2019.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Krishna et al. (2016) Krishna, R. A., Hata, K., Chen, S., Kravitz, J., Shamma, D. A., Fei-Fei, L., and Bernstein, M. S.  Embracing error to enable rapid crowdsourcing.  In _Proceedings of the 2016 CHI conference on human factors in computing systems_ , pp. 3167–3179, 2016.
  * Krizhevsky & Hinton (2009) Krizhevsky, A. and Hinton, G.  Learning multiple layers of features from tiny images.  Technical report, Citeseer, 2009.
  * Li et al. (2020) Li, J., Socher, R., and Hoi, S. C.  Dividemix: Learning with noisy labels as semi-supervised learning.  _arXiv preprint arXiv:2002.07394_ , 2020.
  * Li et al. (2017) Li, W., Wang, L., Li, W., Agustsson, E., and Van Gool, L.  Webvision database: Visual learning and understanding from web data.  _arXiv preprint arXiv:1708.02862_ , 2017.
  * Liu et al. (2020) Liu, S., Niles-Weed, J., Razavian, N., and Fernandez-Granda, C.  Early-learning regularization prevents memorization of noisy labels.  _arXiv preprint arXiv:2007.00151_ , 2020.
  * Ma et al. (2018) Ma, X., Wang, Y., Houle, M. E., Zhou, S., Erfani, S., Xia, S., Wijewickrema, S., and Bailey, J.  Dimensionality-driven learning with noisy labels.  In _International Conference on Machine Learning_ , pp. 3355–3364, 2018.
  * Malach & Shalev-Shwartz (2017) Malach, E. and Shalev-Shwartz, S.  Decoupling” when to update” from” how to update”.  In _Advances in Neural Information Processing Systems_ , pp. 960–970, 2017.
  * Minc (1970) Minc, H.  On the maximal eigenvector of a positive matrix.  _SIAM Journal on Numerical Analysis_ , 7(3):424–427, 1970.
  * Mirzasoleiman et al. (2020) Mirzasoleiman, B., Cao, K., and Leskovec, J.  Coresets for robust training of deep neural networks against noisy labels.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Oord et al. (2018) Oord, A. v. d., Li, Y., and Vinyals, O.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Oymak et al. (2019) Oymak, S., Fabian, Z., Li, M., and Soltanolkotabi, M.  Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian.  _arXiv preprint arXiv:1906.05392_ , 2019.
  * Paszke et al. (2017) Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A.  Automatic differentiation in pytorch.  2017\.
  * Patrini et al. (2017) Patrini, G., Rozza, A., Krishna Menon, A., Nock, R., and Qu, L.  Making deep neural networks robust to label noise: A loss correction approach.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 1944–1952, 2017.
  * Reed et al. (2014) Reed, S., Lee, H., Anguelov, D., Szegedy, C., Erhan, D., and Rabinovich, A.  Training deep neural networks on noisy labels with bootstrapping.  _arXiv preprint arXiv:1412.6596_ , 2014.
  * Ren et al. (2018) Ren, M., Zeng, W., Yang, B., and Urtasun, R.  Learning to reweight examples for robust deep learning.  In _International Conference on Machine Learning_ , pp. 4334–4343, 2018.
  * (35) SimCLR.  https://github.com/spijkervet/simclr.
  * Sohn (2016) Sohn, K.  Improved deep metric learning with multi-class n-pair loss objective.  In _Advances in neural information processing systems_ , pp. 1857–1865, 2016.
  * Stewart (1990) Stewart, G. W.  Matrix perturbation theory.  1990\.
  * Szegedy et al. (2017) Szegedy, C., Ioffe, S., Vanhoucke, V., and Alemi, A. A.  Inception-v4, inception-resnet and the impact of residual connections on learning.  In _Thirty-first AAAI conference on artificial intelligence_ , 2017\.
  * Tanaka et al. (2018) Tanaka, D., Ikami, D., Yamasaki, T., and Aizawa, K.  Joint optimization framework for learning with noisy labels.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 5552–5560, 2018.
  * Tosh et al. (2021) Tosh, C., Krishnamurthy, A., and Hsu, D.  Contrastive estimation reveals topic posterior information to linear models.  _Journal of Machine Learning Research_ , 22(281):1–31, 2021.
  * Van Rooyen et al. (2015) Van Rooyen, B., Menon, A., and Williamson, R. C.  Learning with symmetric label noise: The importance of being unhinged.  In _Advances in Neural Information Processing Systems_ , pp. 10–18, 2015.
  * Wang et al. (2019) Wang, X., Hua, Y., Kodirov, E., and Robertson, N. M.  Imae for noise-robust learning: Mean absolute error does not treat examples equally and gradient magnitude’s variance matters.  _arXiv preprint arXiv:1903.12141_ , 2019.
  * Wedin (1972) Wedin, P.-Å.  Perturbation bounds in connection with singular value decomposition.  _BIT Numerical Mathematics_ , 12(1):99–111, 1972\.
  * Wu et al. (2018) Wu, Z., Xiong, Y., Yu, S. X., and Lin, D.  Unsupervised feature learning via non-parametric instance discrimination.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 3733–3742, 2018.
  * Xia et al. (2019) Xia, X., Liu, T., Wang, N., Han, B., Gong, C., Niu, G., and Sugiyama, M.  Are anchor points really indispensable in label-noise learning?  In _Advances in Neural Information Processing Systems_ , pp. 6838–6849, 2019.
  * Xu et al. (2019) Xu, Y., Cao, P., Kong, Y., and Wang, Y.  L_dmi: A novel information-theoretic loss function for training deep nets robust to label noise.  In _Advances in Neural Information Processing Systems_ , pp. 6225–6236, 2019.
  * Zhang et al. (2016) Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Zhang et al. (2017) Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D.  mixup: Beyond empirical risk minimization.  _arXiv preprint arXiv:1710.09412_ , 2017.
  * Zhang et al. (2020) Zhang, H., Lee, H., Arik, S., Pfister, T., and Zhang, Z.  Distilling effective supervision from severe label noise.  2020\.
  * Zhang & Sabuncu (2018) Zhang, Z. and Sabuncu, M.  Generalized cross entropy loss for training deep neural networks with noisy labels.  In _Advances in neural information processing systems_ , pp. 8778–8788, 2018.
  * Zheltonozhskii et al. (2022) Zheltonozhskii, E., Baskin, C., Mendelson, A., Bronstein, A. M., and Litany, O.  Contrast to divide: Self-supervised pre-training for learning with noisy labels.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pp. 1657–1667, 2022.

##  Appendix A Analysis for Disconnected Subclasses

In this section we consider the case where $\xi=0$ in assumption 4.2, which
implies that the probability of two augmentation data from different
subclasses being generated from the same random natural datum is exactly zero.
And in section B we extend the results to any $\xi\in[0,1)$ via eigenvalue and
eigenvector perturbation. We use $\|\cdot\|_{1}$, $\|\cdot\|_{2}$ and
$\|\|_{F}$ to denote the $1$-norm, operator norm and Frobenius norm,
respectively.

###  A.1 Spectral Decomposition of Augmentation Graph

An important technical idea we use to formalize the representations obtained
by contrastive learning is augmentation graph (HaoChen et al., 2021), which is
an undirected graph with all augmentation data
$\\{\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}\\}$ as its
vertices and $w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}$ as the weight for edge
$(\boldsymbol{x}_{i},\boldsymbol{x}_{j})$. Let $\boldsymbol{A}$ denote the
adjacency matrix of the augmentation graph, that is, each entry
$a_{ij}=w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}$. And the normalized
adjacency matrix $\overline{\boldsymbol{A}}$ is defined as

$\displaystyle\overline{\boldsymbol{A}}\coloneqq\boldsymbol{D}^{-1/2}\boldsymbol{A}\boldsymbol{D}^{-1/2},$

where
$\boldsymbol{D}=\text{diag}(w_{\boldsymbol{x}_{1}},w_{\boldsymbol{x}_{2}},\dots,w_{\boldsymbol{x}_{n}})$
with
$w_{\boldsymbol{x}_{i}}=\sum_{j=1}^{n}w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}$.
For simplicity we index the augmentation data in the following way: the first
$n_{1}$ data are from subclass $1$, the next $n_{2}$ data are from subclass
$2$, …, the last $n_{\bar{K}}$ data are from subclass $\bar{K}$. Lemma A.1
states an important property of $\overline{\boldsymbol{A}}$.

######  Lemma A.1.

Assumption 4.2 with $\xi=0$ implies that $\overline{\boldsymbol{A}}$ is a
block diagonal matrix
$\textbf{diag}(\overline{\boldsymbol{A}}_{1},\overline{\boldsymbol{A}}_{2},\dots,\overline{\boldsymbol{A}}_{\bar{K}})$
where $\overline{\boldsymbol{A}}_{\bar{k}}\in\mathbb{R}^{n_{\bar{k}}\times
n_{\bar{k}}}$. This combined with 4.1 gives us: for each block
$\overline{\boldsymbol{A}}_{\bar{k}}$, the ratio between two entries in the
same column is bounded as follows

$\displaystyle\forall\bar{k}\in[\bar{K}],\max_{j,s,t}\frac{\bar{a}_{\bar{k},s,j}}{\bar{a}_{\bar{k},t,j}}\leq
1+\delta^{\prime},$

where $\bar{a}_{k,i,j}$ are the entries of
$\overline{\boldsymbol{A}}_{\bar{k}}$ and
$\delta^{\prime}=(1+\delta)^{3/2}-1=\frac{3}{2}\delta+\mathcal{O}(\delta^{2})$.

Let $f_{\min}=\operatorname*{arg\,min}_{f}\mathfrak{C}(f)$ and
$\boldsymbol{F}_{\min}=[f_{\min}(\boldsymbol{x}_{1})~{}f_{\min}(\boldsymbol{x}_{2})\dots
f_{\min}(\boldsymbol{x}_{n})]^{\top}$, according the theorem in (HaoChen et
al., 2021), $\boldsymbol{F}_{\min}$ is also the minimizer of the following
matrix factorization problem

$\displaystyle\min_{\boldsymbol{F}\in\mathbb{R}^{n\times
p}}\|\overline{\boldsymbol{A}}-\boldsymbol{F}\boldsymbol{F}^{\top}\|_{F}^{2},$
(7)

and therefore can be further decomposed as

$\displaystyle\boldsymbol{F}_{\min}=\boldsymbol{F}^{*}\boldsymbol{\Sigma}\boldsymbol{R},$
(8)

by Eckart–Young–Mirsky theorem (Eckart & Young, 1936), where
$\boldsymbol{F}^{*}\in\mathbb{R}^{n\times
p}=[\boldsymbol{v}_{1},\boldsymbol{v}_{2},\dots,\boldsymbol{v}_{p}]\in\mathbb{R}^{n\times
p}$,
$\boldsymbol{\Sigma}=\textbf{diag}(\sqrt{\lambda_{1}},\sqrt{\lambda_{2}},\dots,\sqrt{\lambda_{p}})$,
$\boldsymbol{R}\in\mathbb{R}^{p\times p}$ is some orthogonal matrix,
$\lambda_{1},\lambda_{2},\dots,\lambda_{p}$ are the $p$ largest eigenvalues of
$\overline{\boldsymbol{A}}$ and
$\boldsymbol{v}_{1},\boldsymbol{v}_{2},\dots,\boldsymbol{v}_{p}$ are the
corresponding unit-norm eigenvectors. W.l.o.g., we assume
$\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{p}$. Our following proofs are
based on this decomposition. To avoid cluttered notation we drop the subscript
of $\boldsymbol{F}_{\min}$, i.e., we use $\boldsymbol{F}$ for the _learned_
representation.

###  A.2 Properties of Singular Values/Vectors of the Representation Matrix

From the above section we know that the singular values/vectors of
$\boldsymbol{F}$ are the first $p$ eigenvalues/vectors of
$\overline{\boldsymbol{A}}$. For each block
$\overline{\boldsymbol{A}}_{\bar{k}}$, let
$\lambda_{\bar{k},1},\lambda_{\bar{k},2},\dots,\lambda_{\bar{k},n_{\bar{k}}}$
denote the eigenvalues (in descending order) and
$\boldsymbol{v}_{\bar{k},1},\boldsymbol{v}_{\bar{k},2},\dots,\boldsymbol{v}_{\bar{k},n_{\bar{k}}}$
denote the corresponding eigenvectors. The eigenvalues of
$\overline{\boldsymbol{A}}$ are the list of the eigenvalues of all blocks. The
corresponding eigenvectors are the block vectors
$(\vec{0}_{1},\vec{0}_{2},\dots,\vec{0}_{\bar{k}-1},\boldsymbol{v}_{\bar{k},i},\vec{0}_{\bar{k}+1},\dots,\vec{0}_{\bar{K}})\coloneqq\dot{\boldsymbol{v}}_{\bar{k},i}$
with each $\vec{0}_{j}$ being a zero vector of length $n_{j}$. Since
$\overline{\boldsymbol{A}}$ is a normalized adjacency matrix, each block
$\overline{\boldsymbol{A}}_{\bar{k}}$ is also normalized. Then the largest
eigenvalue for each block is exactly $1$, i.e., $\lambda_{\bar{k},1}=1$. It
immediately follow Lemma A.2.

######  Lemma A.2.

The $\bar{K}$ largest eigenvalues of $\overline{\boldsymbol{A}}$ are all $1$,
i.e., $\lambda_{1}=\lambda_{2}=\dots=\lambda_{\bar{K}}=1$.

As long as $p\geq\bar{K}$, all $\lambda_{\bar{k},1}$ and
$\boldsymbol{v}_{\bar{k},1}$ appear in the decomposition of $\boldsymbol{F}$.
Let $p_{\bar{k}}\geq 1$ be the number of eigenvalues/eigenvectors of block
$\overline{\boldsymbol{A}}_{\bar{k}}$ that also appear in the decomposition of
$\boldsymbol{F}$. The following Lemmas and Corollaries states other important
properties of eigenvalues/eigenvectors of $\overline{\boldsymbol{A}}$ .

######  Lemma A.3.

By assumption 4.1, the $1$-norm of $\boldsymbol{v}_{\bar{k},1}$ has the
following lower bound.

$\displaystyle\|\boldsymbol{v}_{\bar{k},1}\|_{1}^{2}\geq\frac{n_{\bar{k}}^{2}}{1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2}}=n_{\bar{k}}-2(n_{\bar{k}}-1)\delta^{\prime}-\mathcal{O}(\delta^{\prime
2}).$

###### Proof.

Write $\boldsymbol{v}_{\bar{k},1}$ as
$[e_{1},e_{2},\dots,e_{n_{\bar{k}}}]^{T}$. By Perron-Frobenius theorem, all
the elements here are positive since $\overline{\boldsymbol{A}}_{\bar{k}}$ is
a positive matrix. Then the quotient of any two elements in
$\boldsymbol{v}_{\bar{k},1}$ can be bounded in terms of the entries of
$\overline{\boldsymbol{A}}_{\bar{k}}$ (Minc, 1970) and therefore
$1+\delta^{\prime}$ by lemma A.1:

$\displaystyle\max_{i,j}\frac{e_{i}}{e_{j}}\leq\max_{j,s,t}\frac{\bar{a}_{\bar{k},s,j}}{\bar{a}_{\bar{k},t,j}}\leq
1+\delta^{\prime}.$

Let $e_{min}=\min_{i}e_{i}$, we have

$\displaystyle
1=\|\boldsymbol{v}_{\bar{k},1}\|_{2}^{2}=\sum_{i=1}^{n_{\bar{k}}}e_{i}^{2}\leq
e_{min}^{2}+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2}e_{min}^{2},$

and

$\displaystyle\|\boldsymbol{v}_{\bar{k},1}\|_{1}^{2}$
$\displaystyle=(\sum_{i=1}^{n_{\bar{k}}}e_{i})^{2}\geq
n_{\bar{k}}^{2}e_{min}^{2}.$

Combining the preceding two equations yields

$\displaystyle\|\boldsymbol{v}_{\bar{k},1}\|_{1}^{2}\geq\frac{n_{\bar{k}}^{2}}{1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2}}.$

∎

######  Lemma A.4.

The sum of squared eigenvalues of each block
$\overline{\boldsymbol{A}}_{\bar{k}}$ can be bounded.

$\displaystyle\sum_{i=1}^{n_{\bar{k}}}\lambda_{\bar{k},i}^{2}\leq\frac{(1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2})(1+\delta^{\prime})^{2}}{n_{\bar{k}}}.$

###### Proof.

First we have

$\displaystyle\sum_{i=1}^{n_{\bar{k}}}\lambda_{\bar{k},i}^{2}=\|\overline{\boldsymbol{A}}_{\bar{k}}\|_{F}^{2}=\sum_{j=1}^{n_{\bar{k}}}\|\boldsymbol{c}_{\bar{k},j}\|_{2}^{2},$
(9)

where
$\boldsymbol{c}_{\bar{k},j}=[\bar{a}_{\bar{k},1,j},\bar{a}_{\bar{k},2,j},\dots,\bar{a}_{\bar{k},n_{\bar{k}},j}]^{T}$
denotes the $j$-th column in $\overline{\boldsymbol{A}}_{\bar{k}}$. Analogous
to lemma A.3, here we can bound $\|\boldsymbol{c}_{\bar{k},j}\|_{2}^{2}$ in
terms of $\|\boldsymbol{c}_{\bar{k},j}\|_{1}^{2}$ by lemma A.1

$\displaystyle\|\boldsymbol{c}_{\bar{k},j}\|_{2}^{2}\leq\frac{(1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2})\|\boldsymbol{c}_{\bar{k},j}\|_{1}^{2}}{n_{\bar{k}}^{2}}.$
(10)

We also have

$\displaystyle\|\boldsymbol{c}_{\bar{k},j}\|_{1}^{2}\leq\max_{j}\|\boldsymbol{c}_{\bar{k},j}\|_{1}^{2}\leq(1+\delta^{\prime})^{2}\min_{j}\|\boldsymbol{c}_{\bar{k},j}\|_{1}^{2}\leq(1+\delta^{\prime})^{2}\lambda_{\bar{k},1}^{2}=(1+\delta^{\prime})^{2},$
(11)

where the second inequality holds because of assumption 4.1 and the third
inequality holds because of Perron-Frobenius theorem. Combining equations 9,
10 and 11 completes the proof. ∎

######  Corollary A.5.

The eigenvalues except the $\bar{K}$ largest ones are each upper bounded by

$\displaystyle\lambda_{\bar{k},i}~{}\leq~{}\sqrt{\frac{(1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2})(1+\delta^{\prime})^{2}}{n_{\bar{k}}}-1}=~{}\mathcal{O}(\sqrt{\delta^{\prime}}),\quad\forall
i=2,3,\dots,n_{\bar{k}},\quad\forall\bar{k}\in[\bar{K}].$

###### Proof.

By Lemmas A.2 and A.4

$\displaystyle\sum_{i=2}^{n_{\bar{k}}}\lambda_{\bar{k},i}^{2}=$
$\displaystyle\sum_{i=1}^{n_{\bar{k}}}\lambda_{\bar{k},i}^{2}-\lambda_{\bar{k},1}^{2}$
$\displaystyle\leq$
$\displaystyle\frac{(1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2})(1+\delta^{\prime})^{2}}{n_{\bar{k}}}-1$
$\displaystyle=$ $\displaystyle 4\delta^{\prime}+\mathcal{O}(\delta^{\prime
2}).$ (12)

Then

$\displaystyle\lambda_{\bar{k},i}\leq$
$\displaystyle\sqrt{\sum_{i=2}^{n_{\bar{k}}}\lambda_{\bar{k},i}^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{(1+(n_{\bar{k}}-1)(1+\delta^{\prime})^{2})(1+\delta^{\prime})^{2}}{n_{\bar{k}}}-1}$

∎

######  Corollary A.6.

For each block $\overline{\boldsymbol{A}}_{\bar{k}}$, the sum of the
eigenvalues from the second to the $p_{\bar{k}}$-th is bounded by

$\displaystyle\sum_{i=2}^{p_{\bar{k}}}\lambda_{\bar{k},i}\leq
2\sqrt{(p_{\bar{k}}-1)}\sqrt{\delta^{\prime}}+\mathcal{O}(\delta^{\prime}).$

And the sum of eigenvalues of $\overline{\boldsymbol{A}}$ from the
$\bar{K}+1$-th to the $p$-th is bounded by

$\displaystyle\sum_{i=\bar{K}+1}^{p}\lambda_{i}\leq
2\sqrt{(p-\bar{K})\bar{K}\delta^{\prime}}+\mathcal{O}(\delta^{\prime}).$

###### Proof.

Applying Cauchy–Schwarz inequality to equation 12 yields the bound for
$\sum_{i=2}^{p_{\bar{k}}}\lambda_{\bar{k},i}$. Summing both sides of equation
12 over $\bar{k}\in[\bar{K}]$ and then applying Cauchy–Schwarz inequality give
the bound for $\sum_{i=\bar{K}+1}^{p}\lambda_{i}$. ∎

###  A.3 Error under Gaussian Noise when $\xi=0$

With the decomposition in Equation 8, the learned parameter of the linear
model in Equation 3 can be rewritten as

$\displaystyle\hat{\boldsymbol{W}}^{*}=\boldsymbol{R}^{\top}\textbf{diag}(\frac{\sqrt{\lambda_{1}}}{\lambda_{1}+\beta},\frac{\sqrt{\lambda_{2}}}{\lambda_{2}+\beta},\dots,\frac{\sqrt{\lambda_{p}}}{\lambda_{p}+\beta})\boldsymbol{F}^{*\top}\hat{\boldsymbol{Y}}.$

The output on the training set $\boldsymbol{F}\hat{\boldsymbol{W}}^{*}$ is

$\displaystyle\boldsymbol{F}\hat{\boldsymbol{W}}^{*}=$
$\displaystyle\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}\hat{\boldsymbol{Y}},$

where $\boldsymbol{B}=\textbf{diag}(b_{1},b_{2},\dots,b_{p})$ with
$b_{i}=\frac{\lambda_{i}}{\lambda_{i}+\beta}$. And the error on training set
w.r.t. ground-truth labels can be therefore written in terms of the
eigenvalues and eigenvectors of $\overline{\boldsymbol{A}}$

$\displaystyle\mathbb{E}_{\Delta\boldsymbol{Y}}\frac{1}{n}\|\boldsymbol{Y}-\boldsymbol{F}\hat{\boldsymbol{W}}^{*}\|_{F}^{2}=$
$\displaystyle\mathbb{E}_{\Delta\boldsymbol{Y}}\left[\frac{1}{n}\|\boldsymbol{Y}-\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}(\boldsymbol{Y}+\Delta\boldsymbol{Y})\|_{F}^{2}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n}\|\boldsymbol{Y}-\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}\boldsymbol{Y}\|_{F}^{2}+\mathbb{E}_{\Delta\boldsymbol{Y}}\left[\|\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}\Delta\boldsymbol{Y}\|_{F}^{2}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n}\|\boldsymbol{Y}\|_{F}^{2}+\frac{1}{n}\sum_{i=1}^{p}\sum_{j=1}^{K}(b_{i}^{2}-2b_{i})(\boldsymbol{v}_{i}^{\top}\boldsymbol{y}_{j})^{2}+\frac{\sigma^{2}}{n}\sum_{i=1}^{p}b_{i}^{2}$
$\displaystyle=$
$\displaystyle\underbrace{1+\frac{1}{n}\sum_{i=1}^{p}\sum_{j=1}^{K}(b_{i}^{2}-2b_{i})(\boldsymbol{v}_{i}^{\top}\boldsymbol{y}_{j})^{2}}_{\textbf{bias}^{2}}+\underbrace{\frac{\sigma^{2}}{n}\sum_{i=1}^{p}b_{i}^{2}}_{\textbf{variance}},$
(13)

where $\boldsymbol{y}_{j}\in\mathbb{R}^{n}$ is the $j$-th _column_ of
$\boldsymbol{Y}$.

We first calculate the $\textbf{bias}^{2}$ term. We have $b_{i}^{2}-2b_{i}\leq
0$ since $b_{i}\in(0,1]$. Then we drop items with $i\geq\bar{K}+1$ in the
summation and apply Lemma A.2 to get an upper bound

$\displaystyle\textbf{bias}^{2}\leq$ $\displaystyle
1-\frac{1}{n}\sum_{i=1}^{\bar{K}}\sum_{j=1}^{K}(2b_{i}-b_{i}^{2})(\boldsymbol{v}_{i}^{\top}\boldsymbol{y}_{j})^{2}$
$\displaystyle=$ $\displaystyle
1-\frac{1}{n}\left(\frac{2}{1+\beta}-(\frac{1}{1+\beta})^{2}\right)\sum_{i=1}^{\bar{K}}\sum_{j=1}^{K}(\boldsymbol{v}_{i}^{\top}\boldsymbol{y}_{j})^{2}$
$\displaystyle=$ $\displaystyle
1-\frac{1}{n}\left(\frac{2}{1+\beta}-(\frac{1}{1+\beta})^{2}\right)\sum_{\bar{k}=1}^{\bar{K}}\sum_{j=1}^{K}(\dot{\boldsymbol{v}}_{\bar{k},1}^{\top}\boldsymbol{y}_{j})^{2}$

By Perron-Frobenious theorem all elements in $\boldsymbol{v}_{\bar{k},1}$ are
positive, thus the sum of elements of $\boldsymbol{v}_{\bar{k},1}$ can be
written as $\|\boldsymbol{v}_{\bar{k},1}\|_{1}$. With the observation that
$\dot{\boldsymbol{v}}_{\bar{k},1}^{T}\boldsymbol{y}_{j}=\|\boldsymbol{v}_{\bar{k},1}\|_{1}$
when $\bar{k}$ is a subclass within class $j$ and otherwise
$\dot{\boldsymbol{v}}_{\bar{k},1}^{T}\boldsymbol{y}_{j}=0$, the above equation
can be rewritten as

$\displaystyle\textbf{bias}^{2}\leq$ $\displaystyle
1-\frac{1}{n}\left(\frac{2}{1+\beta}-(\frac{1}{1+\beta})^{2}\right)\sum_{\bar{k}=1}^{\bar{K}}\|\boldsymbol{v}_{\bar{k},1}\|_{1}^{2}.$
(14)

Then by Lemma A.3,

$\displaystyle\textbf{bias}^{2}\leq$ $\displaystyle
1-\frac{1}{n}\left(\frac{2}{1+\beta}-(\frac{1}{1+\beta})^{2}\right)\sum_{\bar{k}=1}^{\bar{K}}\left(n_{\bar{k}}-2(n_{\bar{k}}-1)\delta^{\prime}-\mathcal{O}(\delta^{\prime
2})\right)$ $\displaystyle=$
$\displaystyle(\frac{\beta}{1+\beta})^{2}+2(1-\frac{\bar{K}}{n})\frac{(2\beta+1)}{(\beta+1)^{2}}\delta^{\prime}+\mathcal{O}(\delta^{\prime
2})$ $\displaystyle=$
$\displaystyle(\frac{\beta}{1+\beta})^{2}+3(1-\frac{\bar{K}}{n})\frac{(2\beta+1)}{(\beta+1)^{2}}\delta+\mathcal{O}(\delta^{2})$
(15)

Now we bound the variance term. By Lemma A.2

$\displaystyle\textbf{variance}=$
$\displaystyle\frac{\sigma^{2}}{n}\sum_{i=1}^{p}b_{i}^{2}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{n}\sum_{i=1}^{\bar{K}}b_{i}^{2}+\frac{\sigma^{2}}{n}\sum_{i=\bar{K}+1}^{p}b_{i}^{2}$
$\displaystyle=$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\frac{\sigma^{2}}{n}\sum_{i=\bar{K}+1}^{p}(1-\frac{\beta}{\lambda_{i}+\beta})$
$\displaystyle=$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\frac{\sigma^{2}}{n}(p-\bar{K})-\frac{\sigma^{2}}{n}\sum_{i=\bar{K}+1}^{p}\frac{\beta}{\lambda_{i}+\beta}.$
(16)

Apply Cauchy–Schwarz inequality and Corollary A.6 to bound the summation in
the last term

$\displaystyle\sum_{i=\bar{K}+1}^{p}\frac{\beta}{\lambda_{i}+\beta}\geq$
$\displaystyle~{}\frac{\beta(p-\bar{K})^{2}}{\sum_{i=\bar{K}+1}^{p}(\lambda_{i}+\beta)}$
$\displaystyle\geq$
$\displaystyle~{}\frac{\beta(p-\bar{K})^{2}}{2\sqrt{(p_{\bar{k}}-1)}\sqrt{\delta^{\prime}}+\mathcal{O}(\delta^{\prime})+(p-\bar{K})\beta}$
$\displaystyle=$
$\displaystyle~{}p-\bar{K}+\frac{2\sqrt{p-\bar{K}}}{\beta}\sqrt{\bar{K}\delta^{\prime}}+\mathcal{O}(\delta^{\prime}).$

Plugging the preceding into Equation 16 yields

$\displaystyle\textbf{variance}\leq$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\sigma^{2}\frac{2\sqrt{\bar{K}(p-\bar{K})}}{n}\frac{\sqrt{\delta^{\prime}}}{\beta}+\mathcal{O}(\delta^{\prime})$
$\displaystyle=$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\sigma^{2}\frac{\sqrt{6\bar{K}(p-\bar{K})}}{n}\frac{\sqrt{\delta}}{\beta}+\mathcal{O}(\delta)$

###  A.4 Accuracy under Label Flipping (Proof for Theorem 4.5)

We study the accuracy by looking at the entries of the output
$\boldsymbol{F}\hat{\boldsymbol{W}}^{*}$.

$\displaystyle\boldsymbol{F}\hat{\boldsymbol{W}}^{*}=$
$\displaystyle~{}\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}(\boldsymbol{Y}+\Delta\boldsymbol{Y})$
$\displaystyle=$
$\displaystyle\left[\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}(\boldsymbol{y}_{1}+\Delta\boldsymbol{y}_{1}),~{}\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}(\boldsymbol{y}_{2}+\Delta\boldsymbol{y}_{2}),~{}\dots,~{}\boldsymbol{F}^{*}\boldsymbol{B}\boldsymbol{F}^{*\top}(\boldsymbol{y}_{K}+\Delta\boldsymbol{y}_{K})\right]$
$\displaystyle=$
$\displaystyle\left[\sum_{i=1}^{p}b_{i}\boldsymbol{v}_{i}\boldsymbol{v}_{i}^{\top}(\boldsymbol{y}_{1}+\Delta\boldsymbol{y}_{1}),~{}\sum_{i=1}^{p}b_{i}\boldsymbol{v}_{i}\boldsymbol{v}_{i}^{\top}(\boldsymbol{y}_{2}+\Delta\boldsymbol{y}_{2}),~{}\dots,~{}\sum_{i=1}^{p}b_{i}\boldsymbol{v}_{i}\boldsymbol{v}_{i}^{\top}(\boldsymbol{y}_{K}+\Delta\boldsymbol{y}_{K})\right]$
$\displaystyle\coloneqq$
$\displaystyle\left[\boldsymbol{z}_{1},\boldsymbol{z}_{2},\dots,\boldsymbol{z}_{K}\right]$

For convenience we define the notations $C_{k}$ and $S_{\bar{k}}$ as the sets
of indices of examples from class $k$ and subclass $\bar{k}$, respectively

$\displaystyle C_{k}\coloneqq$ $\displaystyle\\{i:\text{$\boldsymbol{x}_{i}$
belongs to class $k$}\\}$ $\displaystyle S_{\bar{k}}\coloneqq$
$\displaystyle\\{i:\text{$\boldsymbol{x}_{i}$ belongs to subclass
$\bar{k}$}\\}=\\{i:\sum_{j=1}^{\bar{k}-1}n_{j}<i\leq\sum_{j=1}^{\bar{k}}n_{j}\\}.$

Let the notation $\boldsymbol{\mu}^{(j)}$ denote the $j$-th element of vector
$\boldsymbol{\mu}$. Then $\boldsymbol{z}_{k}^{(j)}$ can be written as
$\sum_{i=1}^{p}b_{i}\boldsymbol{v}_{i}^{(j)}\boldsymbol{v}_{i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$.
Let $\bar{k}_{j}$ denote the subclass that $\boldsymbol{x}_{j}$ belongs to,
i.e., $j\in S_{\bar{k}}$ and define
$e_{\min,s}\coloneqq\min_{j}\boldsymbol{v}_{\bar{k}_{j},1}^{(s)}$ and
$e_{\max,s}\coloneqq\max_{s}\boldsymbol{v}_{\bar{k}_{j},1}^{(s)}$. We have the
following two lemmas.

######  Lemma A.7.

$\boldsymbol{z}_{k}^{(j)}$ can be bounded

$\displaystyle\begin{cases}\boldsymbol{z}_{k}^{(j)}\geq&\frac{1}{\beta+1}e_{\min,j}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(j)}n_{\min}(1-\alpha)-\sqrt{n_{\max}}\frac{2\sqrt{p-1}}{\beta}\sqrt{\delta^{\prime}}-\mathcal{O}(\delta^{\prime}),\quad
j\in C_{k}\\\
\boldsymbol{z}_{k}^{(j)}\leq&\frac{1}{\beta+1}e_{\max,j}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(j)}n_{\max}\alpha
c_{\max}+\sqrt{n_{\max}c_{\max}}\frac{2\sqrt{p-1}}{\beta}\sqrt{\delta^{\prime}}+\mathcal{O}(\delta^{\prime}),\quad
j\notin C_{k}.\end{cases}.$

###### Proof.

Let $b_{\bar{k},i}$ denote
$\frac{\lambda_{\bar{k},i}}{\beta+\lambda_{\bar{k},i}}$. Recalling that one
property of the block vector $\dot{\boldsymbol{v}}_{\bar{k},i}$ is that
$\dot{\boldsymbol{v}}_{\bar{k},i}^{(j)}=0$ when $j\notin S_{\bar{k}}$, we have

$\displaystyle\boldsymbol{z}_{k}^{(j)}=$
$\displaystyle\sum_{i=1}^{p}b_{i}\boldsymbol{v}_{i}^{(j)}\boldsymbol{v}_{i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$
$\displaystyle=$
$\displaystyle\sum_{\bar{k}=1}^{\bar{K}}\sum_{i=1}^{p_{\bar{k}}}b_{\bar{k},i}\dot{\boldsymbol{v}}_{\bar{k},i}^{(j)}\dot{\boldsymbol{v}}_{\bar{k},i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$
$\displaystyle=$
$\displaystyle\sum_{i}^{p_{\bar{k}_{j}}}b_{\bar{k}_{j},i}\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{(j)}\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$
$\displaystyle=$ $\displaystyle
b_{\bar{k}_{j},1}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(j)}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})+\sum_{i=2}^{p_{\bar{k}_{j}}}b_{\bar{k}_{j},i}\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{(j)}\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$
$\displaystyle=$
$\displaystyle\frac{1}{\beta+1}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(j)}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})+\sum_{i=2}^{p_{\bar{k}_{j}}}b_{\bar{k}_{j},i}\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{(j)}\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$
(17)

For the nonzero elements in $\dot{\boldsymbol{v}}_{\bar{k}_{j},1}$, if $j\in
C_{k}$, there are at least $n_{\min}(1-\alpha)$ elements being $1$ at
corresponding positions in $\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k}$; if
$j\notin C_{k}$, there are at most $n_{\max}\alpha c_{\max}$ elements being
$1$ at corresponding positions in
$\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k}$.Then the inner product in the
first term in equation 17 can be bounded by

$\displaystyle\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})=\sum_{s=1}^{n_{\bar{k}_{j}}}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(s)}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})^{(s)}\begin{cases}\geq
e_{\min,j}n_{\min}(1-\alpha),\quad j\in C_{k}\\\ \leq
e_{\max,j}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(j)}n_{\max}\alpha
c_{\max},\quad j\notin C_{k}\end{cases}$

For the inner product in the second term in equation 17, if $j\in C_{k}$, then
$\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{\top}(\boldsymbol{y}_{k}+\Delta\boldsymbol{y}_{k})$
is the sum of at most $n_{\max}$ elements in
$\dot{\boldsymbol{v}}_{\bar{k}_{j},i}$. Since
$\|\dot{\boldsymbol{v}}_{\bar{k}_{j},i}\|_{2}^{2}=1$, the sum is bounded by
$[-\sqrt{n_{\max}},\sqrt{n_{\max}}]$. Similarly we can get the bound
$[-\sqrt{n_{\max}c_{\max}},\sqrt{n_{\max}c_{\max}}]$ for $j\notin C_{k}$. We
also know that $|\dot{\boldsymbol{v}}_{\bar{k}_{j},i}^{(j)}|\leq 1$. Now it
remains to bound $\sum_{i=2}^{p_{\bar{k}_{j}}}b_{\bar{k}_{j},i}$ by applying
Cauchy–Schwarz inequality and Corollary A.6

$\displaystyle\sum_{i=2}^{p_{\bar{k}_{j}}}b_{\bar{k}_{j},i}=$
$\displaystyle\sum_{i=2}^{p_{\bar{k}_{j}}}\frac{\lambda_{\bar{k},i}}{\beta+\lambda_{\bar{k},i}}$
$\displaystyle=$ $\displaystyle
p_{\bar{k}_{j}}-1-\sum_{i=2}^{p_{\bar{k}_{j}}}\frac{\beta}{\beta+\lambda_{\bar{k},i}}$
$\displaystyle\leq$ $\displaystyle
p_{\bar{k}_{j}}-1-\frac{\beta(p_{\bar{k}_{j}}-1)^{2}}{\sum_{i=2}^{p_{\bar{k}_{j}}}(\lambda_{\bar{k}_{j},i}+\beta)}$
$\displaystyle\leq$ $\displaystyle
p_{\bar{k}_{j}}-1-\frac{\beta(p_{\bar{k}_{j}}-1)^{2}}{2\sqrt{(p_{\bar{k}}-1)}\sqrt{\delta^{\prime}}+\mathcal{O}(\delta^{\prime})+\beta(p_{\bar{k}_{j}}-1)}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{p-1}\frac{\sqrt{\delta^{\prime}}}{\beta}+\mathcal{O}(\delta^{\prime})$

∎

######  Lemma A.8.

$e_{\min,j}$, $e_{\max,j}$ and $e_{max,j}/e_{\min,j}$ can be bounded.

$\displaystyle e_{\min,j}\geq$
$\displaystyle~{}\sqrt{\frac{1}{1+(n_{\max}-1)(1+\delta^{\prime})^{2}}}$
$\displaystyle e_{\max,j}\leq$
$\displaystyle~{}\sqrt{\frac{1}{1+(n_{\min}-1)/(1+\delta^{\prime})^{2}}}$
$\displaystyle\frac{e_{\max,j}}{e_{\min,j}}\leq$
$\displaystyle~{}(1+\delta^{\prime})\sqrt{\frac{(1+(1+\delta^{\prime})^{2}(n_{\max}-1))}{n_{\max}-1+(1+\delta^{\prime})^{2}}}$

###### Proof.

The proof is analogous to that for lemma A.3. ∎

Now we are ready to calculate the maximum noise level that allows correct
prediction on all training examples, i.e., $\boldsymbol{z}_{k:j\in
C_{k}}^{j}>\boldsymbol{z}_{k^{\prime}:j\notin C_{k^{\prime}}}^{j}$. Let the
preceding hold, then by lemma A.7 we get

$\displaystyle\alpha<\frac{1-\frac{2\sqrt{n_{\max}}(1+\sqrt{c_{\max}})\sqrt{p-1}}{\frac{\beta}{\beta+1}e_{\min,j}\dot{\boldsymbol{v}}_{\bar{k}_{j},1}^{(j)}n_{\min}}\sqrt{\delta^{\prime}}}{1+\frac{n_{\max}e_{\max,j}}{n_{\min}e_{\min,j}}c_{\max}}-\mathcal{O}(\delta^{\prime})$
(18)

Plugging lemma A.8 into equation 18 with some algebraic manipulation yields

$\displaystyle\alpha<\frac{1}{1+\frac{n_{\max}}{n_{\min}}c_{\max}}-\mathcal{O}\left(\frac{\sqrt{\delta^{\prime}}}{\beta}\right)=\frac{1}{1+\frac{n_{\max}}{n_{\min}}c_{\max}}-\mathcal{O}\left(\frac{\sqrt{\delta}}{\beta}\right).$
(19)

##  Appendix B Considering Off-Diagonal Entries in the Adjacency Matrix
(Connected Subclasses)

For here on we assume $n_{\bar{k}}=\frac{n}{\bar{K}},\forall\bar{k}\in\bar{K}$
for simplicity, despite that our results can easily extend to unbalanced
dataset.

######  Lemma B.1.

Under assumption 4.2, the off-diagonal entries in $A$ is no longer zero. Let
$\widetilde{\boldsymbol{A}}$ denote the new normalized matrix, which also
contains non-zero off-diagonal entries. With a bit abuse of notation, in the
following we use $\overline{\boldsymbol{A}}$ to denote the matrix obtained by
normalizing $A$ with off-diagonal elements ignored. Then all the properties of
eigenvectors and eigenvalues of $\overline{\boldsymbol{A}}$ stated before
including those lemma A.1, A.3, A.4 still hold. And
$\widetilde{\boldsymbol{A}}$ can be written as a perturbation of
$\overline{\boldsymbol{A}}$

$\displaystyle\widetilde{\boldsymbol{A}}=\overline{\boldsymbol{A}}+\boldsymbol{E},$

with $\|\boldsymbol{E}\|_{F}=\mathcal{O}\left(\bar{K}^{5/2}\xi\right)$.

###### Proof.

Let $\mathring{\boldsymbol{A}}$ be a matrix in the same shape of
$\overline{\boldsymbol{A}}$ containing all elements of
$\widetilde{\boldsymbol{A}}$ in the diagonal blocks. Let $\boldsymbol{H}$ be a
matrix that collects the remaining off-diagonal elements. Therefore
$\widetilde{\boldsymbol{A}}=\mathring{\boldsymbol{A}}+\boldsymbol{H}$, which
can be rewritten as

$\displaystyle\widetilde{\boldsymbol{A}}=\overline{\boldsymbol{A}}+\mathring{\boldsymbol{A}}-\overline{\boldsymbol{A}}+\boldsymbol{H}.$
(20)

For all off-diagonal elements $h_{i,j}$ in $\boldsymbol{H}$

$\displaystyle h_{i,j}\leq\frac{\bar{K}\xi}{n}.$

Since there are $n^{2}-\sum_{\bar{k}=1}^{\bar{K}}n_{\bar{k}}^{2}$ entries
outside of the diagonal blocks, the norm of $\boldsymbol{H}$ can be bounded by

$\displaystyle\|\boldsymbol{H}\|_{F}\leq\sqrt{1-\frac{1}{\bar{K}}}\bar{K}\xi$
(21)

Each element in the diagonal blocks of
$\overline{\boldsymbol{A}}-\mathring{\boldsymbol{A}}$ is non-negative. Also,
supposing $\boldsymbol{x}_{i}$ and $\boldsymbol{x}_{j}$ are from subclass
$\bar{k}$, we have

$\displaystyle(\overline{\boldsymbol{A}}-\mathring{\boldsymbol{A}})_{i,j}=$
$\displaystyle\frac{w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}}{\sqrt{\sum_{s:\boldsymbol{x}_{s}\in
C_{\bar{k}}}w_{\boldsymbol{x}_{i}\boldsymbol{x}_{s}}}\sqrt{\sum_{t:\boldsymbol{x}_{t}\in
C_{\bar{k}}}w_{\boldsymbol{x}_{t}\boldsymbol{x}_{j}}}}-\frac{w_{\boldsymbol{x}_{i}\boldsymbol{x}_{j}}}{\sqrt{\sum_{s=1}^{n}w_{\boldsymbol{x}_{i}\boldsymbol{x}_{s}}}\sqrt{\sum_{t=1}^{n}w_{\boldsymbol{x}_{t}\boldsymbol{x}_{j}}}}$
$\displaystyle\leq$
$\displaystyle\frac{n(\bar{K}-1)\xi}{\frac{n}{\bar{K}(1+\delta)}(\frac{n}{\bar{K}(1+\delta)}+n(\bar{K}-1)\xi)}$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\frac{\bar{K}^{3}(1+\delta)^{2}\xi}{n}\right),$

by which the norm of $\overline{\boldsymbol{A}}-\mathring{\boldsymbol{A}}$ is
bounded

$\displaystyle\|\overline{\boldsymbol{A}}-\mathring{\boldsymbol{A}}\|_{F}=\mathcal{O}\left(\bar{K}^{5/2}(1+\delta)^{2}\xi\right)=\mathcal{O}\left(\bar{K}^{5/2}\xi\right).$
(22)

Combining equations 20, 21 and 22 completes the proof. ∎

$\overline{\boldsymbol{A}}$ has the following eigendecomposition

$\displaystyle\overline{\boldsymbol{A}}=\begin{bmatrix}\boldsymbol{V}_{I}\boldsymbol{V}_{N}\end{bmatrix}\begin{bmatrix}\boldsymbol{\Sigma}_{I}&0\\\
0&\boldsymbol{\Sigma}_{N}\\\
\end{bmatrix}\begin{bmatrix}\boldsymbol{V}_{I}^{\top}\\\
\boldsymbol{V}_{N}^{\top}\\\ \end{bmatrix},$

where $\boldsymbol{\Sigma}_{I}$ collects the $\bar{K}$ largest eigenvalues
$\lambda_{1},\dots,\lambda_{\bar{K}}$ on the diagonal and
$\boldsymbol{\Sigma}_{N}$ collects the remaining
$\lambda_{\bar{K}+1},\dots,\lambda_{\bar{n}}$. $\boldsymbol{V}_{I}$ and
$\boldsymbol{V}_{N}$ collects the corresponding $\bar{K}$ and $n-\bar{K}$
eigenvectors, respectively. Let $\widetilde{\boldsymbol{A}}$ has analogous
decomposition

$\displaystyle\widetilde{\boldsymbol{A}}=\begin{bmatrix}\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{N}\end{bmatrix}\begin{bmatrix}\widetilde{\boldsymbol{\Sigma}}_{I}&0\\\
0&\widetilde{\boldsymbol{\Sigma}}_{N}\\\
\end{bmatrix}\begin{bmatrix}\widetilde{\boldsymbol{V}}_{I}^{\top}\\\
\widetilde{\boldsymbol{V}}_{N}^{\top}\\\ \end{bmatrix},$

with eigenvalues $\widetilde{\lambda}_{1},\dots,\widetilde{\lambda}_{n}$ and
eigenvectors
$\widetilde{\boldsymbol{v}}_{1},\dots,\widetilde{\boldsymbol{v}}_{n}$.
Eigenvalues of both matrices are indexed in descending order.

###  B.1 Perturbation in Eigenvalues and Eigenvectors

The following two lemmas bound the changes in eigenvalues, eigenvectos and the
alignment between labels and eigenvectors caused by $\xi$.

######  Lemma B.2.

We have the following bound for eigenvalues of $\widetilde{\boldsymbol{A}}$:

$\displaystyle\begin{cases}~{}~{}1-\mathcal{O}(K^{5/2}\xi)\leq\widetilde{\lambda}_{i}\leq
1,\quad&i=1,2,\dots,\bar{K}\\\
~{}~{}\sum_{i=\bar{K}+1}^{p}\lambda_{i}\leq\mathcal{O}(\sqrt{\delta}+\bar{K}^{5/2}\xi)\\\
\end{cases}$

###### Proof.

From Lemma A.2 and Corollary A.6 we know that

$\displaystyle\begin{cases}~{}~{}\lambda_{i}=1,\quad&i=1,2,\dots,\bar{K},\\\
~{}~{}\sum_{i=\bar{K}+1}^{p}\lambda_{i}\leq\mathcal{O}(\sqrt{\delta}).\\\
\end{cases}$ (23)

By Weyl’s inequality on perturbation, we have

$\displaystyle|\widetilde{\lambda}_{i}-\lambda_{i}|\leq\|\boldsymbol{E}\|_{2}.$

The right-hand-side is $\leq\|\boldsymbol{E}\|_{F}$ and therefore
$\mathcal{O}(\bar{K}^{5/2}\xi)$ by lemma B.1. Combining the preceding with
equation 23 completes the proof.

∎

######  Lemma B.3.

The norm of the projection of $\boldsymbol{Y}$ onto the range of
$\widetilde{\boldsymbol{V}}_{I}$ is bounded from below, i.e.,

$\displaystyle\|\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}\geq\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}-\mathcal{O}(n\bar{K}^{2}\xi).$

###### Proof.

By Lemma A.2 and Corollary A.5 we have

$\displaystyle\lambda_{\bar{K}}-\lambda_{\bar{K}+1}\geq
1-\mathcal{O}(\sqrt{\delta}).$

By Wedin’s Theorem (Wedin, 1972; Stewart, 1990), we have the following bound
on the principle angle between the range of $\widetilde{\boldsymbol{V}}_{I}$
and the range of $\boldsymbol{V}_{I}$ as long as
$1\geq\mathcal{O}(\sqrt{\delta}+\bar{K}^{5/2}\xi)$

$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}(\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}-I)\|_{F}\leq\mathcal{O}\left(\frac{\|\boldsymbol{E}\|_{F}}{\lambda_{\bar{K}}-\lambda_{\bar{K}+1}}\right)\leq\mathcal{O}\left(\frac{\mathcal{O}(\bar{K}^{5/2}\xi)}{1-\mathcal{O}(\sqrt{\delta})}\right)=\mathcal{O}(\bar{K}^{5/2}\xi).$

Thus

$\displaystyle\|\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}=$
$\displaystyle\|\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}\boldsymbol{Y}-\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}+\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}$
$\displaystyle\geq$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}+2\langle\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}\boldsymbol{Y}-\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y},~{}~{}\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\rangle_{F}$
$\displaystyle\geq$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}+2\operatorname{Tr}((\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}-\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T})\boldsymbol{Y}\boldsymbol{Y}^{T}\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T})$
$\displaystyle=$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}+2\operatorname{Tr}(\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}(\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}-I)\boldsymbol{Y}\boldsymbol{Y}^{T})$
$\displaystyle=$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}+2\langle\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}(\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}-\boldsymbol{I}),~{}~{}\boldsymbol{Y}\boldsymbol{Y}^{T}\rangle_{F}$
$\displaystyle\geq$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}-2\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}(\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}-\boldsymbol{I})\|_{F}\|\boldsymbol{Y}\boldsymbol{Y}^{T}\|_{F}$
$\displaystyle\geq$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}-\mathcal{O}(\bar{K}^{5/2}\xi)\frac{n}{\sqrt{K}}$
$\displaystyle=$
$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}-\mathcal{O}(n\bar{K}^{2}\xi).$

∎

###  B.2 Error under Gaussian Noise (Proof for Theorem 4.4)

Considering $\xi$, rewrite $\textbf{bias}^{2}$ as

$\displaystyle\textbf{bias}^{2}=$ $\displaystyle
1+\frac{1}{n}\sum_{i=1}^{p}\sum_{j=1}^{K}(\widetilde{b}_{i}^{2}-2\widetilde{b}_{i})(\widetilde{\boldsymbol{v}_{i}}^{\top}\boldsymbol{y}_{j})^{2}$
$\displaystyle\leq$ $\displaystyle
1-\frac{1}{n}\sum_{i=1}^{\bar{K}}\sum_{j=1}^{K}(2\widetilde{b}_{i}-\widetilde{b}_{i}^{2})(\widetilde{\boldsymbol{v}_{i}}^{\top}\boldsymbol{y}_{j})^{2}$
$\displaystyle\leq$ $\displaystyle
1-\frac{1}{n}(2\widetilde{b}_{\bar{K}}-\widetilde{b}_{\bar{K}}^{2})\sum_{i=1}^{\bar{K}}\sum_{j=1}^{K}(\widetilde{\boldsymbol{v}_{i}}^{\top}\boldsymbol{y}_{j})^{2}$
$\displaystyle\leq$ $\displaystyle
1-\frac{1}{n}(2\widetilde{b}_{\bar{K}}-\widetilde{b}_{\bar{K}}^{2})\|\widetilde{\boldsymbol{V}}_{I}\widetilde{\boldsymbol{V}}_{I}^{T}\boldsymbol{Y}\|_{F}^{2},$
(24)

where
$\widetilde{b}_{i}=\frac{\widetilde{\lambda_{i}}}{\widetilde{\lambda_{i}}+\beta}$.
Also, Lemma A.3 gives us the lower bound for
$\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}$

$\displaystyle\|\boldsymbol{V}_{I}\boldsymbol{V}_{I}^{T}\boldsymbol{Y}\|_{F}^{2}=$
$\displaystyle\sum_{\bar{k}}^{\bar{K}}\|\boldsymbol{v}_{\bar{k},1}\|_{1}^{2}$
$\displaystyle\geq$ $\displaystyle~{}n-\mathcal{O}(\delta).$ (25)

Combining lemma B.2, lemma B.3, equation 24 and equation 25 yields the bound
for the bias

$\displaystyle\textbf{bias}^{2}=$
$\displaystyle(\frac{\beta}{1+\beta})^{2}+\mathcal{O}(\delta+\xi).$

We bound the variance in the same manner as in Section A.3 by applying
Cauchy–Schwarz inequality, Corollary A.6 and Lemma B.2

$\displaystyle\textbf{variance}=$
$\displaystyle\frac{\sigma^{2}}{n}\sum_{i=1}^{p}\widetilde{b}_{i}^{2}$
$\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{n}\sum_{i=1}^{\bar{K}}\widetilde{b}_{i}^{2}+\frac{\sigma^{2}}{n}\sum_{i=\bar{K}+1}^{p}\widetilde{b}_{i}^{2}$
$\displaystyle\leq$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\frac{\sigma^{2}}{n}\sum_{i=\bar{K}+1}^{p}(1-\frac{\beta}{\widetilde{\lambda_{i}}+\beta})$
$\displaystyle=$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\frac{\sigma^{2}}{n}(p-\bar{K})-\frac{\sigma^{2}}{n}\sum_{i=\bar{K}+1}^{p}\frac{\beta}{\widetilde{\lambda_{i}}+\beta}$
$\displaystyle\leq$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\frac{\sigma^{2}}{n}(p-\bar{K})-\frac{\sigma^{2}}{n}\frac{\beta(p-\bar{K})^{2}}{\sum_{i=\bar{K}+1}^{p}(\widetilde{\lambda_{i}}+\beta)}$
$\displaystyle\leq$
$\displaystyle\sigma^{2}\frac{\bar{K}}{n}(\frac{1}{\beta+1})^{2}+\sigma^{2}\mathcal{O}(\frac{\sqrt{\delta}+\xi}{\beta}).$

##  Appendix C Contrastive Learning Slightly Improves the Alignment Between
Jacobian Matrix and Ground-truth Labels

We compare the alignments between the clean label vector and the initial
Jacobian matrix of (1) network pretrained using SimCLR for 1000 epochs, (2)
network pretrained using SimCLR for 100 epochs and (3) randomly initialized
network. $\boldsymbol{y}\in\mathbb{R}^{nK}$ is the vector obtained by
flattening the label matrix $\boldsymbol{Y}$, i.e., concatenating the $n$ rows
of $\boldsymbol{Y}$. Let
$\boldsymbol{z}(\boldsymbol{x}_{i},\boldsymbol{W})\in\boldsymbol{R}^{K}$ be
the output of the network given example $\boldsymbol{x}_{i}$ and parameters
$\boldsymbol{W}\in\mathbb{R}^{d}$ (we see the parameters of the network as a
vector). Then the Jacobian $\boldsymbol{J}$ is defined as

$\displaystyle\boldsymbol{J}(\boldsymbol{W})=\left[\frac{\partial\boldsymbol{z}(\boldsymbol{x}_{1},\boldsymbol{W})}{\boldsymbol{W}}\dots\frac{\partial\boldsymbol{z}(\boldsymbol{x}_{n},\boldsymbol{W})}{\boldsymbol{W}}\right]^{\top}.$

Note that
$\frac{\partial\boldsymbol{z}(\boldsymbol{x}_{i},\boldsymbol{W})}{\boldsymbol{W}}\in\mathbb{R}^{d\times
K}$, therefore $\boldsymbol{J}(\boldsymbol{W})\in\mathbb{R}^{nK\times d}$. In
table 4 $\Pi_{I}(\boldsymbol{y})$ is the projection of $\boldsymbol{y}$ onto
the span of the $10$ singular vectors of $\boldsymbol{J}(\boldsymbol{W}_{0})$
with larges singular values and $\Pi_{N}(\boldsymbol{y})$ is the projection of
$\boldsymbol{y}$ onto the span of the remaining singular vectors.
Interestingly, pretraining for more epochs leads to larger
$\Pi_{I}(\boldsymbol{y})$ and smaller $\Pi_{N}(\boldsymbol{y})$ and therefore
larger
$\|\boldsymbol{J}\boldsymbol{J}^{T}\boldsymbol{y}\|_{F}/\|\boldsymbol{J}\boldsymbol{J}^{T}\|_{F}$.
How much this slight improvement in the alignment contributes to the
robustness deserves further investigation.

##  Appendix D Training Only the Last Layer v.s. Training All Layers

Figure 3 compares the performance of training only the linear layer (i.e.,
with the encoder frozen) and fine-tuning all layers (i.e., with the encoder
unfrozen). For both CIFAR-10 and CIFAR-100 we first pretrain a Res-Net 32
using SimCLR for 1000 epochs and using the Adam optimizer with a learning rate
of $3\times 10^{-4}$, a weight decay of $1\times 10^{-6}$ and a batch size of
128. For downstream tasks, we use the SGD optimizer with a learning rate of
$5\times 10^{-3}$, a weight decay of $1\times 10^{-3}$, a batch size of 64. We
see that in most cases fine-tuning achieves a higher test accuracy. However,
finetuning will eventually overfit if trained for longer. Also, we note that
training all layers is more likely to overfit, especially under large noise
level (column 3 in figure 3).

Figure 3: Test accuracy of fine-tuning a pre-trained network with frozen encoder v.s. unfrozen encoder on CIFAR-10 (top) and CIFAR-100 (bottom) under 20%, 50%, 80% symmetric noise and 40% asymmetric noise (left to right).  | $\|\Pi_{\mathcal{I}}(\boldsymbol{y})\|_{F}$ | $\|\Pi_{\mathcal{N}}(\boldsymbol{y})\|_{F}$ | $\|\boldsymbol{J}\boldsymbol{J}^{T}\boldsymbol{y}\|_{F}/\|\boldsymbol{J}\boldsymbol{J}^{T}\|_{F}$
---|---|---|---
Pretrained for 1000 epochs | 10.063 | 29.979 | 3.184
Pretrained for 100 epochs | 10.036 | 29.988 | 3.175
Randomly initialized | 10.014 | 29.995 | 3.055
Table 4: Alignment between the Jacobian matrix and the clean labels.