A Theory-Driven Self-Labeling Refinement Method for Contrastive Representation Learning
Year: 2022

Abstract:
For an image query, unsupervised contrastive learning labels crops of the same image as positives, and other image crops as negatives. Although intuitive, such a native label assignment strategy cannot reveal the underlying semantic similarity between a query and its positives and negatives, and impairs performance, since some negatives are semantically similar to the query or even share the same semantic class as the query. In this work, we first prove that for contrastive learning, inaccurate label assignment heavily impairs its generalization for semantic instance discrimination, while accurate labels benefit its generalization. Inspired by this theory, we propose a novel self-labeling refinement approach for contrastive learning. It improves the label quality via two complementary modules: (i) selflabeling refinery (SLR) to generate accurate labels and (ii) momentum mixup (MM) to enhance similarity between query and its positive. SLR uses a positive of a query to estimate semantic similarity between a query and its positive and negatives, and combines estimated similarity with vanilla label assignment in contrastive learning to iteratively generate more accurate and informative soft labels. We theoretically show that our SLR can exactly recover the true semantic labels of label-corrupted data, and supervises networks to achieve zero prediction error on classification tasks. MM randomly combines queries and positives to increase semantic similarity between the generated virtual queries and their positives so as to improves label accuracy. Experimental results on CIFAR10, ImageNet, VOC and COCO show the effectiveness of our method.

heading: 1 Introduction
text: Self-supervised learning (SSL) is an effective approach to learn features without manual annotations, with great success witnessed to many downstream tasks, e.g. image classification and object detection [1–7]. The methodology of SSL is to construct a pretext task that can obtain data labels via well designing the task itself, and then build a network to learn from these tasks. For instance, by constructing jigsaw puzzle [8], spatial arrangement identification [9], orientation [10], or chromatic channels [11] as a pretext task, SSL learns high-qualified features from the pretext task that can well transfer to downstream tasks. As it gets rid of the manual annotation requirement in supervised deep learning, SSL has been widely attracted increasing researching interests [1, 12].
As a leading approach in SSL, contrastive learning [1, 4, 13–17] constructs a novel instance discrimination pretext task to train a network so that the representations of different crops (augmentations) of the same instance are close, while representations of different instances are far from each other. Specifically, for an image crop query, it randomly augments the same image to obtain a positive, and view other image crops as negatives. Then it constructs a one-hot label over the positive and negatives to pull the query together with its positive and push the query away its negatives in the feature space.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Motivation. But the one-hot labels in contrastive learning are indeed inaccurate and uninformative because of the following two reasons. Firstly, for a query, it could be semantically similar or even more similar to some negatives than its positives. Indeed, some negatives even belong to the same semantic class as the query [18–20]. It holds in practice, as (i) to achieve good performance, one often uses sufficient negatives that are much more than the semantic class number, e.g. tens of thousands of negatives for ImageNet [21] in MoCo [1], unavoidably leading to the issue on negatives; (ii) even for the same image, especially for an image containing different objects which occurs in ImageNet, random augmentations, e.g. crop, provide crops with (slightly) different semantic information, and thus some of the huge negatives could be more similar to query. Secondly, samples from different classes also have some similarity which is not characterized in the one-hot labels. For example, given a query cat, it is often more similar to a dog than a car though both dog and car are negatives. Learning from those similarity among samples is also important and can improve the performance. This point is also supported by knowledge distillation or self-training approaches [22, 23], where a teacher model or a currently-training model is used to predict semantic similarity of a sample on different classes for further supervising model training, achieving better performance. Therefore, the one-hot label cannot well reveal the semantic similarity between query and its positives and “negatives", and cannot guarantee the semantically similar samples to close each other, leading to performance degradation.
Contributions. In this work, we alleviate the above label issue, and derive some new results and alternatives for contrastive learning. Particularly, we theoretically show that inaccurate labels impair the performance of contrastive learning. Then we propose a self-labeling refinement method to obtain more accurate labels for contrastive learning. Our main contributions are highlighted below.
Our first contribution is proving that the generalization error of MoCo for instance discrimination linearly depends on the discrepancy between the estimated labels (e.g. one-hot labels) in MoCo and the true labels that really reflect semantical similarity between a query and its positives and negatives. Formally, given n training queries D= {xi}ni=1 with estimated labels {yi}ni=1 (e.g. one-hot labels in MoCo) and ground truth labels {y∗i }ni=1 on their corresponding positives and negatives, the generalization error of MoCo for instance discrimination is lower bounded by O ( ED[‖y−y∗‖2] ) where ED[‖y−y∗‖2] = 1 n ∑n i=1‖yi−y∗i ‖2, and is upper bounded by O (√ ln(|F|)/n +ED [‖y−y∗‖2] ) , where |F| is the covering number of the network hypotheses in MoCo. It means that the more accurate of the estimated labels {yi}ni=1, the better generalization of MoCo for instance discrimination. Inspired by our theory, we propose a Self-lAbeliNg rEfinement (SANE) method which iteratively employs the network and data themselves to generate more accurate and informative soft labels for contrastive learning. SANE has two complementary modules: (i) Self-Labeling Refinery (SLR) to explicitly generate accurate labels, and (ii) Momentum Mixup (MM) to increase similarity between query and its positive and implicitly improve label accuracy. Given a query, SLR uses its one positive to estimate semantic similarity between the query and its keys (i.e. its positive and negatives) by computing their feature similarity, since a query and its positive come from the same image and should have close similarity on the same keys. Then SLR linearly combines the estimated similarity of a query with its vanilla one-hot label in contrastive learning to iteratively generate more accurate and informative soft labels. Our strategy is that at the early training stage, one-hot label has heavy combination weight to provide relatively accurate labels; along with more training, the estimated similarity becomes more accurate and informative, and its combination weight becomes larger as it explores useful underlying semantic information between the query and its keys that is missing in the one-hot labels. Besides, we prove that when the semantic labels in the instance discrimination task are corrupted, our SLR can exactly recover the true semantic labels of training data, and networks trained with our SLR can exactly predict the true semantic labels of test samples.
Moreover, we introduce MM for contrastive learning to further reduce the possible label noise and also increase augmentation diversity. Specifically, we randomly combines queries {xi}ni=1 and their positives {x̃i}ni=1 as x′i=θxi + (1−θ)x̃k and estimate their labels as y′i= θȳi + (1−θ)ȳk, where indexes i and k are randomly selected, ȳi is the label of both xi and x̃i estimated by our label refinery, and θ∈ (0, 1) is a random variable. In this way, the component x̃k in the virtual query x′i directly increases the similarity between the query x′i and the positive key x̃k. So the label weight (1− θ) of label y′i on positive key x̃i to bring x ′ i and x̃k together is relatively accurate, as x ′ i really contains the semantic information of x̃k. Meanwhile, the possible noise at the remaining positions of label y′i is scaled by θ and becomes smaller. In this way, MM also improves the label quality.
Other Related Work. To estimate similarity between a query and its negatives, Wei et al. [20] approximated the similarity by computing cosine similarity between a positive and its negatives, and directly replaced the one-hot label for instance discrimination. Wang et al. [12] used similar similarity estimated on weak augmentations to supervise the learning of strong augmentations. In contrast, we respectively estimate the similarities of the query on all contrastive keys ( its positive and negatives) and on only negatives, and linearly combines two estimated similarities with vanilla one-hot label to obtain more accurate and informative label with provable performance guarantee. Learning from noisy label, e.g. [24–26] also uses soft labels generalized by a network to denoise crop labels and supervise representation learning, and often focus on (semi-)supervised learning that differs from our self-supervised learning.
Two relevant works [27, 28] performed vanilla mixup on all query instances to increase data diversity. Differently, our momentum mixup mainly aims to reduce label noise, as it randomly combines one query with one positive (instead of one query) of other instances to increase the similarity between the query and its its positive. Verma et al. [29] showed that mixup is a better domain-agnostic noise than Gaussian noise for positive pair construction. But they did not perform mixup on labels, which is contrast to [27, 28] and ours. See more discussion in Sec. 3.2 and empirical comparison in Sec. 4.3.

heading: 2 Inspiration: A Generalization Analysis of MoCo
text: In this section, we first briefly review the MoCo [1] method popularly studied for contrastive learning, and then analyze the impact of inaccurate label assignment on its generalization ability.
Review of MoCo. The MoCo method contains an online network fw and a target network gξ receptively parameterized byw and ξ. Both fw and gξ consists of a feature encoder and a projection head (e.g. 3-layered MLP). Given a minibatch {ci}si=1 at each iteration, it first randomly augments each vanilla image ci into two views (xi, x̃i) and optimizes the following contrastive loss:
Ln(w) = − 1
s ∑s i=1 log ( σ(xi, x̃i) σ(xi, x̃i) + ∑b l=1 σ(xi, bl) ) , (1)
where σ(xi, x̃i) = exp ( − 〈f(xi),g(x̃i)〉τ‖f(xi)‖2·‖g(x̃i)‖2 ) with a temperature τ . The dictionary B= {bi}bi=1 denotes the negative keys of current minibatch queries {xi}si=1, and is often of huge size to achieve satisfactory performance, e.g. 65,536 in MoCo. In practice,B in MoCo is updated by the minibatch features {g(x̃i)}si=1 in a first-in and first-out order. By fixing gξ and updating fw in Eqn. (1), MoCo pushes the query xi away from its negative keys in dictionaryB while pulling together its positive key x̃i. For gξ, it is updated via exponential moving average, i.e. ξ=(1−ι) ξ+ιw with a constant ι ∈ (0, 1). From Eqn. (1), one can observe that MoCo views each image as an individual class and uses one-hot label y∈Rb+1 (its nonzero position is at the position of its positive key) to train fw. However, as mentioned in Sec. 1, the one-hot labels cannot reveal the semantic similarity between a query xi and its positive and negatives and thus impair representation learning. In the following, we theoretically analyze the effect of inaccurate labels to the generalization of MoCo for instance discrimination.
Generalization Analysis. We focus on analyzing MoCo in the final training stage where the sample (key) distribution in the dictionary B is almost fixed. This simplified setup is reasonable because (i) in the final training stage, the target network gξ almost does not change due to the very small momentum updating parameter ι in practice and the oncoming convergence of the online network fw; (ii) dictionary is sufficient large to cover different patterns in the dataset. This fixed sample distribution simplifies the analysis, and also provides valuable insights.
Let D = {(xi, x̃i)}ni=1 denote the training positive pairs in MoCo sampled from an unknown distribution S. Moreover, the query xi has ground truth soft label y∗i ∈ Rb+1 over the key set Bi={x̃i ∪B}, where the t-th entry y∗it measures the semantic similarity between xi and the t-th key b′t inBi. In practice, given query xi and dictionaryBi, MoCo estimates an one-hot label of xi as yi ∈ Rb+1 whose first entry is one and remaining entries are zero. So yi ignores the semantic similarity between xi and keys inBi, and differs from y∗i . Then MoCo minimizes an empirical risk:
Q̃(fw) = 1
n ∑n i=1 `(h(fw(xi),Bi),yi), (2)
where h(fw(xi),Bi) = [σ(xi,x̃i), σ(xi,b1), · · ·, σ(xi,bb)] denotes the predicted class probability, and `(·, ·) is cross-entropy loss. Ideally, one should sample sufficient pairs (xi, x̃i) from the distribution S and use the ground truth label y∗i of xi to minimize the population risk:
Q(fw) = E(xi,x̃i)∼S [`(h(fw(xi),Bi),y ∗ i )] . (3)
Here we assume the ground truth label y∗i is soft which is indeed more reasonable and stricter than the one-hot label setting especially for contrastive learning [22]. It is because soft label requires the networks to capture the semantic similarity between query and the instances in Bi and bring semantically similar instances together, greatly helping downstream tasks (e.g. classification) where global semantic information is needed, while one-hot label only needs networks to distinguish each instance from others and does not consider the global semantic structures in the data. Actually, the semantic similarity among samples here is also known as “dark knowledge" in knowledge distillation [22] or “Bayes class-probability", and is often used to replace the one-hot label for training network with remarkable performance improvement in many tasks, e.g. classification [30]. As both the data distribution S and the ground truth labels are unknown, MoCo optimizes the empirical risk Q̃(fw) in (2) instead of the population risk Q(fw) in (3). In this way, the optimal network fw by minimizing Q̃(fw) differs from that via optimizing Q(fw). It is natural to ask whether fw by minimizing Q̃(fw) can well perform instance discrimination task in contrastive learning, i.e. whether fw can capture the semantic similarity (y∗i ) between any test sample (xi, x̃i)∼S and the keys (samples) in Bi. To solve this issue, Theorem 1 analyzes the generalization error of fw for instance discrimination. We are interested in the generalization error defined with the true soft labels to measure the semantic similarity learning performance of fw via optimizing Q(fw) on the instance discrimination task which can often better reflect the performance on the downstream tasks. Theorem 1. Suppose `(h(fw(x),Bx),y)∈ [a1, a2], `(·,y) is Ly-Lipschitz w.r.t. y. Let F be a finite class of hypotheses `(h(fw(x),Bx),y) :X×Y→R and |F| be its covering number under ‖·‖∞ metric. (1) Let ED∼S [‖y−y∗‖2] = ED∼S [ 1 n ∑n i=1‖yi−y∗i ‖2
] . For any ν∈(0, 1), it holds∣∣∣Q(fw)− Q̃(fw)∣∣∣ ≤LyED∼S [‖y − y∗‖2]
+
√ 2(a2 − a1)2VD ln(2|F|/ν)
n + 7(a2 − a1)2 ln(2|F|/ν) 3(n− 1) ,
with probability at least 1−ν, where VD is the variance of `(h(f(x),Bx),y∗) on the data D. (2) There exists a contrastive classification problem, a class of hypotheses `(h(fw(x),Bx),y) : X ×Y → R and a constant c0 such that the generalization error of fw is lower bounded∣∣Q(fw)− Q̃(fw)∣∣ ≥ c0 · ED∼S [‖y − y∗‖2] . See its proof in Appendix B. Theorem 1 shows that for the task of learning semantic similarity between a query and its positive and negatives which is important for downstream tasks (e.g., classification), the generalization error of fw trained with the one-hot labels y is upper bounded by O ( ED∼S [‖y − y∗‖2]+ √ VD ln(|F|)/n ) . It means that large training sample number n gives small generalization error, as intuitively, model sees sufficient samples and can generalize better. The loss variance VD on the dataset D measures data diversity: the larger data diversity VD, the more challenging to learn a model with good generalization. Here we are particularly interested in the factor ED∼S [‖y − y∗‖2] which reveals an important property: the higher accuracy of the training label y to the ground truth label y∗, the smaller generalization error. Moreover, Theorem 1 proves that there exists a contrastive classification problem such that the lower bound of generalization error depends on ED∼S [‖y − y∗‖2]. So the upper bound of generalization error is tight in terms of ED∼S [‖y − y∗‖2]. Thus, to better capture the underlying semantic similarity between query xi and samples in dictionaryBi to bring semantically similar samples together and better solve downstream tasks, one should provide accurate label yi to the soft true label y∗i . In the following, we introduce our solution to estimate more accurate and informative soft labels for contrastive learning.

heading: 3 Self-Labeling Refinement for Contrastive Learning
text: Our Self-lAbeliNg rEfinement (SANE) approach for contrastive learning contains (i) Self-Labeling Refinery (SLR for short) and (ii) Momentum Mixup (MM) which complementally refine noisy labels
respectively from label estimation and positive pair construction. SLR uses current training model and data to estimate more accurate and informative soft labels, while MM increases similarity between virtual query and its positive, and thus improves label accuracy.
We begin by slightly modifying the instance discrimination task in MoCo. Specifically, for the query xi in the current minibatch {(xi, x̃i)}si=1, we maximize its similarity to its positive sample x̃i in the key set B̄={x̃i}si=1∪{bi}bi=1 and minimize its similarity to the remaining samples in B̄:
Lc ( w, {(xi,yi)} ) = −1
s ∑s i=1 ∑s+b k=1 yik log ( σ(xi, b̄k)∑s+b l=1 σ(xi, b̄l) ) , (4)
where b̄k is the k-th sample in B̄, and yi is the one-hot label of query xi whose i-th entry yii is one. In this way, the labels of current queries {xi}si=1 are defined on a shared set B̄, and can be linearly combined which is key for SLR & MM. Next, we aim to improve the quality of label yi in (4) below.

heading: 3.1 Self-Labeling Refinery
text: Methodology. As analyzed in Sec. 1 and 2, the one-hot labels in Eqn. (4) could not well reveal the semantic similarity between xi and the instance keys in the set B̄, and thus impairs good representation learning. To alleviate this issue, we introduce Self-Labeling Refinery (SLR) which employs network and data themselves to generate more accurate and informative labels, and improves the performance of contrastive learning. Specifically, to refine the one-hot label yi of query xi, SLR uses its positive instance x̃i to estimate the underlying semantic similarity between xi and instances in B̄={x̃i}si=1∪{bi}bi=1, since xi and x̃i come from the same image and should have close semantic similarity with instances in B̄. Let b̄k be the k-th sample in B̄. Then at the t-th iteration, SLR first estimates the instance-class probability pti∈Rs+b of xi on the set B̄ whose k-th entry is defined as
ptik = σ1/τ ′ (x̃i, b̄k)∑s+b
l=1 σ 1/τ ′(x̃i, b̄l)
, (τ ′ ∈ (0, 1]).
The constant τ ′ sharpens pti and removes some possible small noise, since smooth labels cannot well distillate their knowledge to a network [31]. Then SLR uses pti to approximate the semantic similarity between xi and the instances in B̄ and employs it as the soft label of xi for contrastive learning.
However, since x̃i is highly similar to itself, ptii could be much larger than others and conceals the similarity of other semantically similar instances in B̄. To alleviate this artificial effect, SLR removes x̃i from the set B̄ and re-estimates the similarity between xi and the remaining instances in B̄:
qtik = σ1/τ ′ (x̃i, b̄k)∑s+b
l=1,l 6=iσ 1/τ ′(x̃i, b̄l)
, qtii = 0.
Finally, SLR linearly combines the one-hot label yi and two label estimations, i.e. pi and qi, to obtain more accurate, robust and informative label ȳti of xi at the t-th iteration:
ȳti = (1− αt − βt)yi + αtpti + βtqti , (5)
where αt and βt are two constants. In our experiments, we set αt = µmaxk ptik/z and βt = µmaxk q t ik/z, where z = 1+µmaxk p t ik+µmaxk q t ik, the constants 1, maxk p t ik and maxk q t ik respectively denote the largest confidences of labels yi, pti and q t i on a certain class. Here hyperparameter µ controls the prior confidence of pt and qt. So SLR only has two parameters τ ′ and µ to tune.
The Benefit Analysis of Label Refinery. Now we analyze the performance of our SLR on labelcorrupted data. We first describe the dataset. Let {ci}Ki=1⊂ Rd be K vanilla samples belonging to K̄ ≤K semantic classes, and {(xi,yi)}ni=1∈Rd×R be the random crops of {ci}Ki=1. Since in practice, one often cares more the semantic class prediction performance of a model which often directly reflects the performance on the downstream tasks, we assume that the labels {yi}ni=1 denote corrupted semantic-class labels. Accordingly, we will analyze whether SLR can refine the corrupted labels {yi}ni=1 and whether it helps a model learn the essential semantic-class knowledge of {xi}ni=1. Finally, while allowing for multiple classes, we assume the labels are scalars and take values in [−1, 1] interval for simplicity. We formally define our label-corrupted dataset below.
Definition 1 ((ρ, ε, δ)-corrupted dataset). Let {(xi,y∗i )}ni=1 denote the pairs of crops (augmentations) and ground-truth semantic label, where crop xi generated from the t-th sample ct obeys ‖xi − ct‖2≤ ε with a constant ε, and y∗i ∈{γt}K̄t=1 of xi is the label of ct. Moreover, samples and the crops are normalized, i.e. ‖ci‖2 =‖xk‖2 = 1(∀i, k). Each ci has ni crops, where cl nK ≤ni≤ cu n K with two constants cl and cu. Besides, different classes are separated with a label separation δ:
|γi − γk| ≥ δ, ‖ci − ck‖2 ≥ 2ε, (∀i 6= k).
A (ρ, ε, δ)-corrupted dataset {(xi,yi)}ni=1 obeys the above conditions but with corrupted label {yi}ni=1. Spefically, for each sample ci, at most ρni augmentations are assigned to wrong labels in {γi}K̄i=1.
This data model is rich enough to model realistic data, since different clusters can be assigned to the same label. This definition allows for a fraction ρ of corruptions in each cluster, and can well characterize the realistic data.
Then we study a network of one hidden layer as an example to investigate the label refining performance of our SLR. The network parameterized byW∈Rk×d and v∈Rk is defined as
x ∈ Rd 7→ f(W ,x) = v>φ(Wx), (6)
where φ is an activation function. Following [32–34] which analyze convergence of networks or robust learning of network, we fix v to be a unit vector where half the entries are 1/ √ k and other half are −1/ √ k to simplify exposition. So we only optimize over W that contains most network parameters and will be shown to be sufficient for label refinery. Then given a (ρ, ε, δ)-corrupted dataset {(xi,yi)}ni=1, at the t-iteration we train the network via minimizing the quadratic loss:
Lt(W )= 1
2 ∑n i=1 (ȳti −f(W,xi))2 = 1 2 ‖ȳt −f(W ,X)‖22.
Here the label ȳti of sample xi is estimated by Eqn. (5) in which p t i = f(Wt, x̃i) denotes predicted label by using the positive x̃i of xi, i.e. ‖x̃i − cl‖2 ≤ ε if xi is augmented from vanilla sample cl. We set βt=0 and τ ′=1 for simplicity, as (i) performing nonlinear mapping on network output greatly increases analysis difficulty; (ii) our refinery (5) is still provably sufficient to refine labels when βt=0 and τ ′=1. Then we updateW via gradient descent algorithm with a learning rate η:
Wt+1 = Wt − η∇Lt(Wt). (7)
Following most works on network convergence analysis [32–40], we use gradient descent and quadratic loss, since (i) gradient descent is expectation version of stochastic one and often reveals similar convergence behaviors; (ii) one can expect similar results for other losses, e.g. cross entropy, but quadratic loss gives simpler gradient computation. For analysis, we impose mild assumptions on network (6) and our SLR, which are widely used in network analysis [41–46].
Assumption 1. For network (6), assume φ and its first- and second-order derivatives obey |φ(0)|, |φ′(z)|, |φ′′(z)|≤Γ for ∀z and some Γ≥1, the entries of initializationW0 obey i.i.d.N (0, 1). Assumption 2. Define network covariance matrix Σ(C)=(CC>) Eu[φ′(Cu)φ′(Cu)>] where C=[c1 . . . cK ]
>, u∼N (0, I), is the elementwise product. Let λ(C)>0 be the minimum eigenvalue of Σ(C). For label refinery, assume 3 √ n ∑t0−1 t=0 |αt − αt+1| ≤ ψ1‖f(W0,X)− y∗‖2 and
3 √ n ∑t0−1 t=0 ( 1− ηα 2 4 )t0−t|αt − αt+1|≤ψ2‖f(W0,X)− y∗‖22, where t0 = c1Kηnλ(C) log( Γ√nlogK(1−αmax)ρ) with three constants ψ1, ψ2 and c1. Here αmax is defined as αmax =max1≤t≤t0αt.
Assumption 1 is mild, as most differential activation functions, e.g. softplus and sigmoid, satisfy it, and the Gaussian initialization is used in practice. We assume Gaussian variance to be one for notation simplicity, but our technique is applicable to any constant variance. Assumption 2 requires that the discrepancy between αt and αt+1 until some iteration number t0 are bounded, which holds by setting proper αt. Here we assume βt=0 and τ ′=1 for simplicity, as (i) performing nonlinear mapping on network output greatly increases analysis difficulty; (ii) we will show that even though βt = 0 and τ ′ = 1, our refinery (5) is still provably sufficient to refine labels. For λ(C), many works [34, 41–44] empirically and theoretically show λ(C)>0. Based on these assumptions, we state our results in Theorem 2 with constants c1∼c6.
Theorem 2. Assume {(xi,yi)}ni=1 is a (ρ, ε, δ)-corrupted dataset with noiseless labels {y∗i}ni=1. Let ξ= log ( Γ √ nlogK ρ ) . Suppose ε and the number k of hidden nodes satisfy ε≤ c2 min( λ(C)KΓ2ξ6 , ρ αmax ), k ≥ c3K 2Γ10ξ6‖C‖4
α2maxλ(C)4 . Let ψ′ = 1 + ψ12 + √ ψ2. If step size η ≤ K2cupnΓ2‖C‖2 , with probability
1−3/K100−K exp(−100d), after t≥ t0 = c4Kηnλ(C) log ( Γ √ n logK (1−αmax)ρ )
iterations, the gradient descent (7) satisfies: (1) By defining ζ=4ρ+c5εψ′KΓ3ξ √ logK/λ(C) and y∗ = [y∗1 ,· · · ,y∗n], the discrepancy between the label ȳt estimated by our SLR (5) and the true label y∗ of the augmentation data {xi}ni=1 is bounded:
1√ n ‖ȳt − y∗‖2 ≤ 1− αt√ n ‖y − y∗‖2 + αtζ.
where ȳt = [ȳt1,· · · , ȳtn]. Moreover, if ρ ≤ δ32 , ε ≤ c6δmin ( λ(C)2 ψ′Γ5K2ξ3 , 1 Γ √ d ) , 1− 34δ ≤ αt, the estimated label ȳt predicts true label y∗i of any crop xi:
γk∗ = y ∗ i with k ∗ = argmin1≤k≤K̄ |ȳti − γk|.
(2) By using the refined label ȳt in (5) to train network and letting f(Wt,X) = [f(Wt,x1), · · · , f(Wt,xn)], the error of network prediction on {xi}ni=1 is upper bounded
1√ n ‖f(Wt,X)− y∗‖2 ≤ ζ.
If assumptions on ρ and ε in (1) hold, for vanilla sample ck (∀k =1 · · ·K), network f(Wt, ·) predicts the true semantic label γk of its any augmentation x that satisfies ‖x−ck‖2≤ε:
γk∗ = γk with k∗ = argmin1≤i≤K̄ |f(Wt,x)− γi|.
See its proof roadmap and proof in Appendix C.2. The first result in Theorem 2 shows that after training iterations t0, the discrepancy between the label ȳt estimated by our label refinery (5), i.e. SLR, and ground truth label y∗ of cropped training data {xi}ni=1 is upper bounded by O ( ‖y − y∗‖2 + ζ ) . Both factors ‖y − y∗‖2 and ρ in the factor ζ reflect the label error of the provided corrupted label y. Another important factor in ζ is the smallest eigenvalue λ(C) of network covariance matrix Σ(C) in Assumption 2. Typically, the performance of a network heavily relies on the data diversity even without label corruption. For instance, if two samples are nearly the same but have different labels, the learning of a network is difficult. λ(C) can quantify this data diversity, as one can think of λ(C) as a condition number associated with the network which measures the diversity of the vanilla samples {ci}ni=1. Intuitively, if there are two similar vanilla samples, Σ(C) is trivially rank deficient and has small minimum eigenvalue, meaning more challenges to distinguish the augmentations x generated from ci. Moreover, when the label corruption ratio ρ and the augmentation distance ε are small, the label ȳti estimated by our SLR can predict the true semantic label y ∗ i for any crop sample xi, and thus can supervises a network to learn the essential semantic-class knowledges from {xi}ni=1. The second result in Theorem 2 shows that by using the refined label ȳt in our SLR (5) to train network f(W , ·), the error of network prediction on augmentations {xi}ni=1 can be upper bounded by ζ. Similarly, the factor ρ and λ(C) in ζ respectively reflect the initial label error and the data diversity, which both reflect the learning difficulty for a model on the augmentation data {(xi,yi)}ni=1. More importantly, our results also guarantee the test performance of the trained network f(Wt, ·). Specifically, when the label corruption ratio ρ and sample augmentation distance ε are small, for any vanilla sample ck (∀k=1 · · ·K), the network f(Wt, ·) trained by our SLR can exactly predict the true semantic label γk of its any augmentation x (i.e. ‖x−ck‖2≤ε). These results accord with Theorem 1 that shows the more accurate of training labels, the better generalization of the trained network. These results show the effectiveness of the refined labels by our method.

heading: 3.2 Momentum Mixup
text: Now we propose momentum mixup (MM) to further reduce the possible label noise in realistic data and increase the data diversity as well. Similar to vanilla mixup [47], we construct virtual instance as
x′i = θxi + (1− θ)x̃k, y′i = θȳi + (1− θ)ȳk, θ ∼ Beta(κ, κ) ∈ [0, 1], (8)
where x̃k is randomly sampled from the key set {x̃i}si=1, ȳi denotes the refined label by Eqn. (5), Beta(κ, κ) is a beta distribution. Here xi and x̃i share the same label ȳi on the set B̄={x̃i}si=1 ∪ {bi}bi=1, as they come from the same instance. We call the mixup (8) as “momentum mixup", since the sample x̃k is fed into the momentum-updated network gξ, and plays a contrastive key for instance discrimination. So MM differs from the vanilla mixup used in [27, 28] where x̃k is replaced with xk and both are fed into online network fw, and enjoys the following advantages. Firstly, MM can improve the accuracy of the label y′i compared with vanilla mixup. For explanation, assume ȳi in (8) is one-hot label. Then x ′ i has two positive keys x̃i and x̃k in B̄ decided by its label y ′ i. Accordingly, the component x̃k in x′i = θxi+(1−θ)x̃k directly increases the similarity between the query x′i and its positive key x̃k in B̄. So the label weight (1−θ) of label y′i on the key x̃k to bring x′i and x̃k together is relatively accurate, as x ′ i really contains the semantic information of x̃k. Meanwhile, the sum of label weights in y′i on remaining instance in B̄\x̃k is scaled by θ, which also scales the possible label noise on instances in B̄\x̃k smaller due to θ<1. By comparison, for vanilla mixup, the label weight (1−θ) of label y′i on the key x̃i does not improve label accuracy. It is because the positive pair xk and x̃k are obtained via random augmentation, e.g. crop, and may not be semantically similar, meaning that the component xk in x′i could not increase similarity with x̃k. So its label weight (1−θ) to push x′i close to the key x̃k is not as accurate as the one in MM. Another advantage of MM is that it allows us to use strong augmentation. As observed in [12], directly using strong augmentation in contrastive learning, e.g. MoCo, leads to performance degradation, since the instance obtained by strong augmentation often heavily differs from the one with weak augmentation. As aforementioned, the component x̃k in x′i = θxi + (1− θ)x̃k increases the similarity between the query x′i and the key x̃k in B̄, even though (xi, x̃i) is obtained via strong augmentation. So MM could reduce the matching difficulty between positive instances.
With all the components in place, we are ready to define our proposed SANE model as follows: L(w) = (1− λ)Lc ( w, {(xi,yi)} ) + λLc ( w, {(x′i,y′i)} ) , (9)
where Lc ( w, {(xi,yi)} ) defined in Eqn. (4) denotes the vanilla contrastive loss with one-hot label
yi, Lc ( w, {(x′i,y′i)} ) denotes the momentum mixup loss with label y′i estimated by our self-labeling refinery (5), and λ is a constant. Experimental results in Sec. 4 show the effectiveness of both loss terms. See algorithm details in Algorithm 1 of Appendix A.
Limitation Discussion. SANE follows MoCo-alike framework and hopes to obtain a more accurate soft label of a query over its positive and negatives for instance discrimination. So one limitation of SANE is that it does not apply to BYOL-alike methods [6] that only pulls positive pair together and does not require any labels. However, momentum mixup in SANE which increases the similarity of positive pair may also benefit BYOL, which is left as our future work to thoroughly test.
Societal Impact Discussion. As an unsupervised learning method, SANE could benefit many applications of societal interest where only low-resource labeled data are available, e.g. medical data [48], as SANE can use a mass of unlabeled data for pretraining and few labeled data for finetuning. But same to standard contrastive learning, SANE may suffer from learning bias caused by the potential data bias, and may provide bias or worse performance on smaller classes or groups.

heading: 4 Experiments
text: Our Pytorch code is available at https://openreview.net/forum?id=P84bifNCpFQ& referrer=%5BAuthor%20Console%5D.

heading: 4.1 Evaluation Results on CIFAR10 and ImageNet
text: Settings. We use ResNet50 [49] with a 3-layered MLP head for CIFAR10 [50] and ImageNet [21]. We first pretrain SANE, and then train a linear classifier on top of 2048-dimensional frozen features in ResNet50. With dictionary size 4, 096, we pretrain 2, 000 epochs on CIFAR10 instead of 4, 000 epochs of MoCo, BYOL, and i-Mix in [28]. Dictionary size on ImageNet is 65, 536. For linear classifier, we train 200/100 epochs on CIFAR10/ImageNet. See all optimizer settings in
Appendix A. We use standard data augmentations in [1] for pretraining and test unless otherwise stated. E.g., for test, we perform normalization on CIFAR10, and use center crop and normalization on ImageNet. For SANE, we set τ =0.2, τ ′=0.8, κ=2 in Beta(κ, κ) on CIFAR10, and τ =0.2, τ ′=1, κ=0.1 on ImageNet. For confidence µ, we increase it as µt=m2 −(m2 −m1)(cos(πt/T )+1)/2 with current iteration t and total training iteration T . We set m1 = 0, m2 = 1 on CIFAR10, and m1 = 0.5, m2 = 10 on ImageNet. For KNN on CIFAR10, its neighborhood number is 50 and its temperature is 0.05.
For CIFAR10, to fairly compare with [28], we crop each image into two views to construct the loss (9). For ImageNet, we follow CLSA [12] and train SANE in two settings. SANE-Single uses a single crop in momentum mixup loss Lc ( w,{(x′i,y′i)} ) in (9) that crops each image to a smaller size of 96×96, without much extra computational cost to process these small images. SANE-Multi crop each image into five sizes 224×224, 192×192, 160×160, 128×128, and 96×96 and averages their momentum mixup losses. This ensures a fair comparison with CLSA and SwAV. Moreover, we use strong augmentation strategy in CLSA. Spefically, for the above small image, we randomly select an operation from 14 augmentations used in CLSA, and apply it to the image with a probability of 0.5, which is repeated 5 times. We use “(strong)" to mark whether we use strong augmentations on the small images in momentum mixup loss. Thus, SANE has almost the same training cost with CLSA, i.e. about 75 (198) hours with 8 GPUs, 200 epochs, batch size of 256 for SANE-Single (-Multi). For vanilla contrastive loss on ImageNet, we always use weak augmentations. See more details of the augmentation, loss construction, and pretraining cost on CIFAR10 and ImageNet in Appendix A.
Results. Table 1 shows that with weak or strong augmentations, SANE always surpasses the baselines on CIFAR10. Moreover, SANE with strong (weak) augmentation improves supervised baseline by 1.0% (0.6%).
Table 2 also shows that for ImageNet under weak augmentation setting, for 200 (800) epochs SANE-Multi respectively brings 0.8% (0.6%) improvements over SwAV; with 200 (800) epochs, SANE-Single also beats the runner-up MixCo (i-Mix and SimSiam). Note, BYOL outperforms SANE-Single but was trained 1, 000 epochs. With strong augmentation, SANE-Single and SANEMulti also respectively outperform CLSA-Single and CLSA-Multi. Moreover, our self-supervised accuracy 76.4% is very close to the accuracy 76.5% of supervised baseline, and still improves 0.2% over CLEAN-Multi even for this challenging case. These results show the superiority and robustness of SANE, thanks to its self-labeling refinery and momentum mixup which both improve label quality and thus bring semantically similar samples together.

heading: 4.2 Transfer Results on Downstream Tasks
text: Settings. We evaluate the pretrained SANE model on VOC [61] and COCO [62]. For classification, we train a linear classifier upon ResNet50 100 epochs by SGD. For object detection, we use the same protocol in [1] to fine-tune the pretrained ResNet50 based on detectron2 [63] for fairness. On VOC,
Table 4: Effects of the components in SANE with strong augmentation on CIFAR10.
label p in (5) label q in (5) momentum mixup accuracy (%)
93.7 X 94.6
X 94.5 X 94.8
X X 94.9 X X 95.2 X X 95.1 X X X 95.9
Table 5: Effects of parameter λ in SANE with strong augmentation on CIFAR10.
regularization λ 0 0.25 0.5 0.75 1
accuracy (%) 94.3 95.8 95.9 95.5 94.5
we train detection head with VOC07+12 trainval data and tested on VOC07 test data. On COCO, we train the head on train2017 set and evaluate on the val2017. See optimization settings in Appendix A.
Results. Table 3 shows that SANE consistently outperforms the compared state-of-the-art approaches on both classification and object detection tasks, and enjoys better performance than supervised method pretrained on ImageNet. These results show the superior transferability of SANE behind which the potential reasons have been discussed in Sec. 4.1.

heading: 4.3 Ablation Study
text: We train SANE 1,000 epochs on CIFAR10 to investigate the effects of each component in SANE using strong augmentation. Table 4 shows the benefits of each component, i.e. the label estimations p and q in self-labeling refinery, and momentum mixup.
To investigate the robustness of our SANE to the regularization parameter λ in (9), we run 2,000 epochs on CIFAR10, and report the performance in Table 5. From the results, one can observe that the stable performance (robustness) of SANE on CIAFR10 when regularization parameter λ in (9) varies in a large range, thus testifying the robustness of SANE.
Then we compare our momentum mixup (8) with vanilla mixup in the works [27, 28]. Specifically, we use one-hot label in MoCo and replace x̃j in (8) with the query xj to obtain “MoCo+ mixup", and ours with one-hot label can be viewed as “MoCo+momentum mixup". Then we train them 1,000 epochs on CIFAR10 with weak/strong augmentation, and 200 epochs on ImageNet with weak augmentations. The results in Table 6 show that with weak augmentation, momentum mixup respectively makes about 1.1% and 0.6% improvements over vanilla mixup in [27, 28] on CIFAR10 and ImageNet. Moreover, momentum mixup using strong augmentation has accuracy 94.8% and improves its weak augmentation version, while vanilla mixup with strong augmentation suffers from performance degradation. It is because as discussed in Sec. 3.2, momentum mixup well reduces the possible label noise, especially for strong augmentations, and can enhance the performance more.

heading: 5 Conclusion
text: In this work, we prove the benefits of accurate labels to the generalization of contrastive learning. Inspired by this theory, we propose SANE to improve label quality in contrastive learning via self-labeling refinery and momentum mixup. The former uses the positive of a query to generate informative soft labels and combines with vanilla one-hot label to improve label quality. The latter randomly combines queries and positives to make virtual queries more similar to their corresponding positives, improving label accuracy. Experimental results testified the advantages of SANE.

heading: Acknowledgements
text: The authors sincerely thank the anonymous reviewers for their constructive comments on this work.
1. Funding. Pan Zhou, Caiming Xiong and Steven HOI are supported by Salesforce, mainly for their GPU resource support. Xiao-Tong Yuan is supported in part by the National Key Research and Development Program of China under Grant No. 2018AAA0100400 and in part by the Natural Science Foundation of China (NSFC) under Grant No.61876090 and No.61936005.
2. Competing Interests. Pan Zhou, Caiming Xiong and Steven HOI are staffs in Salesforce. XiaoTong Yuan works as a professor in Nanjing University of Information Science & Technology, Nanjing, China.

Review summaries:
This paper discusses why inaccurate one-hot label in contrastive learning cannot reveal well semantic similarities between samples, and how these inaccurate label assignment would impair its generalization for semantic instance discrimination.   To address this issue, a novel self-labeling refinement method is proposed to obtain more accurate labels for contrastive learning. This is done via two complementary modules that respectively generates accurate soft-labels and enhances semantic similarity between queries and their positives during training.  Both theoretical analysis and empirical results are provided to support the claims made in this paper.

The paper argues that the one-hot label for instance discriminative contrastive loss will impair the performance in downstream tasks. By assuming ground-truth soft labels, the authors prove that the generalization of the network depends on the discrepancy between ground-truth soft labels and refined labels. Therefore, two approaches, SLR and MM are proposed to address the issue. Empirically, the proposed approach outperforms the baselines by non-trivial margins.