Understanding Negative Samples in Instance Discriminative Self-supervised Representation Learning
Year: 2022

Abstract:
Instance discriminative self-supervised representation learning has been attracted attention thanks to its unsupervised nature and informative feature representation for downstream tasks. In practice, it commonly uses a larger number of negative samples than the number of supervised classes. However, there is an inconsistency in the existing analysis; theoretically, a large number of negative samples degrade classification performance on a downstream supervised task, while empirically, they improve the performance. We provide a novel framework to analyze this empirical result regarding negative samples using the coupon collector’s problem. Our bound can implicitly incorporate the supervised loss of the downstream task in the self-supervised loss by increasing the number of negative samples. We confirm that our proposed analysis holds on real-world benchmark datasets.

heading: 1 Introduction
text: Self-supervised representation learning is a popular class of unsupervised representation learning algorithms in the domains of vision [Bachman et al., 2019, Chen et al., 2020a, He et al., 2020, Caron et al., 2020, Grill et al., 2020, Chen and He, 2021] and language [Mikolov et al., 2013, Devlin et al., 2019, Brown et al., 2020]. Generally, it trains a feature extractor by solving a pretext task constructed on a large unlabeled dataset. The learned feature extractor yields generic feature representations for other machine learning tasks such as classification. Recent self-supervised representation learning algorithms help a linear classifier to attain classification accuracy comparable to a supervised method from scratch, especially in a few amount of labeled data regime [Newell and Deng, 2020, Hénaff et al., 2020, Chen et al., 2020b]. For example, SwAV [Caron et al., 2020] with ResNet-50 has a top-1 validation accuracy of 75.3% on the ImageNet-1K classification [Deng et al., 2009] compared with 76.5% by using the fully supervised method.
InfoNCE [van den Oord et al., 2018, Eq. 4] or its modification is a de facto standard loss function used in many state-of-the-art self-supervised methods [Logeswaran and Lee, 2018, Bachman et al., 2019, He et al., 2020, Chen et al., 2020a, Hénaff et al., 2020, Caron et al., 2020]. Intuitively, the minimization of InfoNCE can be viewed as the minimization of cross-entropy loss on K+1 instancewise classification, where K is the number of negative samples. Despite the empirical success of self-supervised learning, we still do not understand why the self-supervised learning algorithms with InfoNCE perform well for downstream tasks.
Arora et al. [2019] propose the first theoretical framework for contrastive unsupervised representation learning (CURL). However, there exists a gap between the theoretical analysis and empirical observation as in Figure 1. Precisely, we expect that a large number of negative samples degrade a supervised loss on a downstream task from the analysis by Arora et al. [2019]. In practice, however,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
a large number of negative samples are commonly used in self-supervised representation learning algorithms [He et al., 2020, Chen et al., 2020a].
Contributions. We show difficulty to explain why large negative samples empirically improve supervised accuracy on the downstream task from the CURL framework when we use learned representations as feature vectors for the supervised classification in Section 3. To fill the gap, we propose a novel lower bound to theoretically explain this empirical observation regarding negative samples using the coupon collector’s problem in Section 4.

heading: 2 InfoNCE-based Self-supervised Representations Learning
text: We focus on Chen et al. [2020a]’s selfsupervised representation learning formulation, namely, SimCLR.1 Let X be an input space, e.g., X ⊂ Rchannel×width×height for color images. We can only access a unlabeled training dataset {xi}Ni=1, where input x ∈ X . SimCLR learns feature extractor f : X → Rh modeled by neural networks on the dataset, where h is the dimensionality of feature representation. Let z = f(a(x)) that is a feature representation of x after applying data augmentation a : X → X . Data augmentation is a pre-defined stochastic function such as a composition of the horizontal flipping and cropping. Note that the output of f is normalized by its L2 norm. Let z+ = f(a+(x)) that is a positive feature representation created from x with different data augmentation a+(·). SimCLR minimizes the following InfoNCEbased loss with K negative samples for each pair of (z, z+):
ℓInfo(z,Z) := − ln exp (z · z+/t)∑
zk∈Z exp (z · zk/t) ,
(1)
where Z = {z+, z−1 , . . . , z−K} that is a set of positive representation z+ and K negative representations {z−1 . . . , z−K} created from other samples, (. · .) is an inner product of two representations, and t ∈ R+ is a temperature parameter.2 Intuitively, this loss function approximates an instance-wise classification loss by using K random negative samples [Wu et al., 2018]. From the definition of Eq. (1), we expect that f learns an invariant encoder with respect to data augmentation a. After minimizing Eq. (1), f works as a feature extractor for downstream tasks such as classification.

heading: 3 Extension of Contrastive Unsupervised Representation Learning Framework
text: We focus on the direct relationship between the self-supervised loss and a supervised loss to understand the role of the number of negative samples K. For a similar problem, the CURL framework [Arora et al., 2019] shows that the averaged supervised loss is bounded by the contrastive unsupervised loss. Thus, we extend the analysis of CURL to the self-supervised representation learning in Section 2 and point out that we have difficulty explaining the empirical observation as
1In fact, our theoretical analysis is valid with asymmetric feature extractors such as MoCo [He et al., 2020], where the positive and negative features do not come from feature extractor f .
2We perform the analysis with t = 1 for simplicity, but our analysis holds with any temperature.
in Figure 1 from the existing analysis. Table 2 in Appendix A summarizes notations used in this paper for convenience.
3.1 CURL Formulation for SimCLR
By following the CURL analysis [Arora et al., 2019], we introduce the learning process in two steps: self-supervised representation learning step and supervised learning step (see Section 3.1.1 and Section 3.1.2, respectively).

heading: 3.1.1 Self-supervised representation learning step
text: The purpose of the self-supervised learning step is to learn a feature extractor f on an unlabeled dataset. During this step, we can only access input samples from X without any relationship between samples, unlike metric learning [Kulis, 2012] or similar unlabeled learning [Bao et al., 2018].
We formulate the data generation process for Eq. (1). The key idea of the CURL analysis is the existence of latent classes C that are associated with supervised classes.3 Let ρ be a probability distribution over C, and let x be an input sample drawn from a data distribution Dc conditioned on a latent class c ∈ C. We draw two data augmentations (a,a+) from the distribution of data augmentation A and apply them independently to the sample. As a result, we have two augmented samples (a(x),a+(x)) and call a+(x) as a positive sample of a(x). Similarly, we draw K negative samples from Dc−k for each c − k ∈ {c−1 , . . . , c−K} ∼ ρK and K data augmentations from A, and then we apply them to negative samples. Definition 1 summarizes the data generation process. Note that we suppose data augmentation a ∼ A does not change the latent class of x ∈ X . Definition 1 (Data Generation Process in Self-supervised Representation Learning Step). 1. Draw latent classes: c, {c−k }Kk=1 ∼ ρK+1; 2. Draw input sample: x ∼ Dc; 3. Draw data augmentations: (a,a+) ∼ A2; 4. Apply data augmentations: a(x),a+(x); 5. Draw negative samples: {x−k }Kk=1 ∼ DKc−k ; 6. Draw data augmentations: {a − k }Kk=1 ∼ AK; 7. Apply data augmentations: {a−k (x−k )}Kk=1.
Note that the original data generation process of CURL samples a positive sample of x from Dc independently and does not use any data augmentations.
From the data generation process and InfoNCE loss (1), we give the following formal definition of self-supervised loss.
Definition 2 (Expected Self-supervised Loss).
LInfo(f) := E c,{c−k }Kk=1∼ρK+1 E x∼Dc (a,a+)∼A2 E {x−k ∼Dc− k }Kk=1
{a−k }Kk=1∼AK
ℓInfo(z,Z), (2)
where recall that z = f(a(x)) and Z = {f(a+(x)), f(a−1 (x−1 )), . . . , f(a−K(x−K))}.
Since we cannot directly minimize Eq. (2), we minimize the empirical counterpart, L̂Info(f), by sampling from the training dataset. After minimizing L̂Info(f), learned f̂ works as a feature extractor in the supervised learning step.

heading: 3.1.2 Supervised learning step
text: At the supervised learning step, we can observe label y ∈ Y = {1, . . . , Y } for each x that is used in the self-supervised learning step. Let S be a supervised data distribution over X × Y , and g ◦ f̂ : X → RY be a classifier, where g : Rh → RY and f̂ is the frozen feature extractor. Given the
3Technically, we do not need c to draw x for self-supervised representation learning. However, we explicitly include it in the data generation process to understand the relationship with a supervised task in Section 3.2. In the main analysis, we assume that the supervised classes in the downstream task are subset of C; however, different relationship between supervised and latent classes is discussed in Appendix B.
supervised data distribution and classifier, our goal is to minimize the following supervised loss:
Lsup(g ◦ f̂) := E x,y∼S a∼A
− ln exp
( gy(f̂(a(x))) )
∑ j∈Y exp ( gj(f̂(a(x))) ) . (3)
By following the CURL analysis, we introduce a mean classifier as a simple instance of g because its loss is an upper bound of Eq. (3).4 The mean classifier is the linear classifier whose weight of label y is computed by averaging representations: µy = Ex∼Dy Ea∼A f(a(x)), where Dy is a data distribution conditioned on the supervise label y. We introduce the definition of the mean classifier’s supervised loss as follows: Definition 3 (Mean Classifier’s Supervised Loss).
Lµsup(f̂) := E x,y∼S a∼A
− ln exp
( f̂(a(x)) · µy )
∑ j∈Y exp ( f̂(a(x)) · µj ) . (4)
We also introduce a sub-class loss function.5 Let Ysub be a subset of Y and Ssub be a data distribution over X × Ysub, then we define the sub-class losses of classifier g and mean classifier: Definition 4 (Supervised Sub-class Losses of Classifier g and Mean Classifier with f̂ ).
Lsub(g ◦ f̂ ,Ysub) := E x,y∼Ssub
a∼A
− ln exp
( gy(f̂(a(x))) )
∑ j∈Ysub ( gj(f̂(a(x))) ) , (5)
Lµsub(f̂ ,Ysub) := E x,y∼Ssub
a∼A
− ln exp
( f̂(a(x)) · µy )
∑ j∈Ysub exp ( f̂(a(x)) · µj ) . (6)
The purpose of unsupervised representation learning [Bengio et al., 2013] is to learn generic feature representation rather than improve the accuracy of the classifier on the same dataset. However, we believe that such a feature extractor tends to transfer well to another task. Indeed, Kornblith et al. [2019] empirically show a strong correlation between ImageNet’s accuracy and transfer accuracy.

heading: 3.2 Theoretical Analysis based on CURL
text: We show that InfoNCE loss (2) is an upper bound of the expected sub-class loss of the mean classifier (6).
Step 1. Introduce a lower bound We denote µ(x) = Ea∼A f(a(x)) and derive a lower bound of unsupervised loss LInfo(f).
LInfo(f) ≥ E c,{c−k }Kk=1∼ρK+1 E x∼Dc a∼A E {x−k ∼Dc− k }Kk=1
ℓInfo ( f(a(x)), { µ(x),µ(x−1 ), . . . ,µ(x − K) })
≥ E c,{c−k }Kk=1∼ρK+1 E x∼Dc a∼A ℓInfo
( f(a(x)), { µ(x),µc−1 , . . . ,µc−K })
≥ E c,{c−k }Kk=1∼ρK+1 E x∼Dc a∼A ℓInfo
( f(a(x)), { µc,µc−1 , . . . ,µc−K }) + d(f), (7)
where d(f) = 1
t E c∼ρ Ex∼Dc    E a∼A [f(a(x))] ·   E x+∼Dc a+1 ∼A [ f(a+1 (x +)) ] − E a+2 ∼A [ f(a+2 (x)) ]      .
4Concrete inequality is found in Appendix C. 5Arora et al. [2019] refer to this loss function as averaged supervised loss.
The first and second inequalities are done by using Jensen’s inequality for convex function. The proof of the third inequality is shown in Appendix D.1. It is worth noting that positive and negative features can be extracted from another feature encoder or memory back He et al. [2020].
Remark 5 (Effect of gap term d(f)). We confirm that d(f) is an almost constant among different K in practice (see Table 1). Therefore we focus on the first term in Eq. (7) in the following analysis.
Step 2. Decomposition into the expected sub-class loss We convert the first term of Eq. (7) into the expected sub-class loss explicitly. By following Arora et al. [2019, Theorem B.1], we introduce collision probability: τK = P(Col(c, {c−k }Kk=1) ̸= 0), where Col(c, {c−k }Kk=1) = ∑K k=1 I[c = c − k ] and I[·] is the indicator function. We omit the arguments of Col for simplicity. Let Csub({c, c−1 , . . . , c−K}) be a function to remove duplicated latent classes given latent classes. We omit the arguments of Csub as well. The result is our extension of Arora et al. [2019, Lemma 4.3] for self-supervised representation learning as the following proposition:
Proposition 6 (CURL Lower Bound of Self-supervised Loss). For all feature extractor f ,
LInfo(f) ≥ (1− τK) E c,{c−k }Kk=1∼ρK+1 [Lµsub(f , Csub)︸ ︷︷ ︸ sub-class loss | Col = 0]
+τK E c,{c−k }Kk=1∼ρK+1 [ln(Col + 1)︸ ︷︷ ︸ collision
| Col ̸= 0] + d(f). (8)
The proof is found in Appendix D.2.
Arora et al. [2019] also show Rademacher complexity-based generalization error bound for the mean classifier. Since we focus on the behavior of the self-supervised loss rather than a generalization error bound when K increases, we do not perform further analysis as was done in Arora et al. [2019]. Nevertheless, we believe that constructing a generalization error bound by following either Arora et al. [2019, Theorem 4.1] or Nozawa et al. [2020, Theorem 7] is worth interesting future work.

heading: 3.3 Limitations of Eq. (8)
text: The bound (8) tells us that K gives a trade-off between the sub-class loss and collision term via τK . Recall that our final goal is to minimize the supervised loss (4) rather than expected sub-class loss (6). To incorporate the supervised loss (4) into the lower bound (8), we need K large enough to satisfy Csub ⊇ Y . However, such a large K makes the lower bound meaningless. We can easily observe that the lower bound (8) converges to the collision term by increasing K since the collision probability τK converges to 1. As a result, the sub-class loss rarely contributes to the lower bound. Let us consider the bound on CIFAR-10, where the number of supervised classes is 10, and latent classes are the same as the supervised classes. When τK=32 ≈ 0.967, i.e., the only 3.3% training samples contribute to the expected sub-class loss, the others fall into the collision term. Indeed, Arora et al. [2019] show that small latent classes or large negative samples degrade classification performance of the expected sub-class classification task. However, even much larger negative samples, K + 1 = 512, yield the best performance of a linear classifier with self-supervised representation on CIFAR-10 [Chen et al., 2020a, B.9].

heading: 4 Proposed Lower Bound for Instance-wise Self-supervised Representation Learning
text: To fill the gap between the theoretical bound (8) and empirical observation from recent work, we propose another lower bound for self-supervised representation learning. The key idea of our bound is to replace τ with a different probability since τ can quickly increase depending on K. The idea is motivated by focusing on the supervised loss rather than the expected sub-class loss.

heading: 4.1 Proposed Lower Bound
text: Let υK be a probability that sampled K latent classes contain all latent classes: {ck}Kk=1 ⊇ C. This probability appears in the coupon collector’s problem of probability theory (e.g., Durrett [2019,
Example 2.2.7]). If the latent class probability is uniform: ∀c, ρ(c) = 1/|C|, then we can calculate the probability explicitly as follows.
Definition 7 (Probability to Draw All Latent Classes). Assume that ρ is a uniform distribution over latent classes C. The probability that K latent classes drawn from ρ contain all latent classes is defined as
υK :=
K∑
n=1
|C|−1∑
m=0
(|C| − 1 m ) (−1)m ( 1− m+ 1|C| )n−1 , (9)
where the first summation is a probability that n drawn latent samples contain all latent classes [Nakata and Kubo, 2006, Eq. 2].6
By replacing τ with υ, we obtain our lower bound of InfoNCE loss:
Theorem 8 (Proposed Lower Bound of Self-supervised Loss). For all feature extractor f ,
LInfo(f) ≥ 1
2
{ υK+1 E
c,{c−k }Kk=1∼ρK+1 [Lµsub(f , C)︸ ︷︷ ︸
sup. loss
| Csub = C]
+(1− υK+1) E c,{c−k }Kk=1∼ρK+1 [Lµsub(f , Csub)︸ ︷︷ ︸ sub-class loss | Csub ̸= C]
+ E c,{c−k }Kk=1∼ρK+1 ln(Col + 1)︸ ︷︷ ︸ collision
} + d(f). (10)
The proof is found in Appendix D.3.
Theorem 8 tells us that probability υK+1 converges to 1 by increasing the number of negative samples K; as a result, the self-supervised loss is more likely to contain the supervised loss and the collision term. The sub-class loss contributes to the self-supervised loss when K is small as in Eq. (8). Let us consider the example value of υ with the same setting discussed in Section 3.3. When υK=32 ≈ 0.719, i.e., 71.9% training samples contribute the supervised loss.

heading: 4.2 Increasing K does not Spread Normalized Features within Same Latent Class
text: We argue that the feature representations do not have a large within-class variance on the feature space by increasing K in practice. To do so, we show the upper bound of the collision term in the lower bounds to understand the effect of large negative samples.
Corollary 9 (Upper Bound of Collision Term). Given a latent class c, K negative classes {c−k }Kk=1, and feature extractor f ,
ln ( Col ( c, {c−k }Kk=1 ) + 1 ) ≤ α+ β E
x∼Dc (a,a+)∼A2 E x′∼Dc a′∼A
∣∣f(a(x)) · [ f(a′(x′))− f(a+(x)) ]∣∣ , (11)
where α and β are non-negative constants depending on the number of duplicated latent classes.
The proof is found in Appendix D.4. A similar bound is shown by Arora et al. [2019, Lemma 4.4].
Intuitively, we expect that two feature representations in the same latent class tend to be dissimilar by increasing K. However, Eq. (11) converges even if K is small in practice. Let us consider the condition when this upper bound achieves the maximum. Since f(a(x)) and f(a+(x)) are computed from the same input sample with different data augmentations, their inner product tends to be 1; thus, f(a′(x′)) is located in the opposite direction of f(a(x)). But, it is not possible to learn such representations because of the definition of InfoNCE with normalized representation and the dimensionality of feature space: Equilateral dimension. We confirm that Eq. (11) without α and β does not increase by increasing K (see Table 1 and Appendix F for more analysis).
6We show expected K+1 to draw all supervised labels for ImageNet-1K and all used datasets in Appendix E.

heading: 4.3 Small K can Give Consistent Loss Function for Supervised Task
text: As we shown in Theorem 8, LInfo with large K can be viewed as an upper bound of Lµsup. However, LInfo with smaller K can still yield good feature representations for downstream tasks on ImageNet1K as reported by Chen et al. [2020a]. Arora et al. [2019] also reported similar results on CIFAR-100 with contrastive losses.7 To shed light on this smaller K regime, we focus on the class distributions of both datasets, ImageNet-1K and CIFAR-100, which are almost uniform.
Proposition 10 (Optimality of Lsub). Suppose C ⊇ Y and ρ is uniform: ∀c ∈ C, ρ(c) = 1/|C|. Suppose a constant function q : x ∈ X q7→ [ q1, . . . , q|C| ]⊤ . Optimal q∗ is a constant function that outputs a vector with the same value if and only if it minimizes Ec,{c−k }Kk=1∼ρK+1 Lsub(q ∗, Csub). The optimal q∗ is also the minimizer of Lsup.
The proof is found in Appendix D.5 inspired by Titsias [2016, Proposition 2].
Proposition 10 does not argue that self-supervised representation learning algorithms fail to learn feature representations on a dataset with a non-uniform class distribution. This is because we perform a supervised algorithm on a downstream dataset after representation learning in general.

heading: 4.4 Relation to Clustering-based Self-supervised Representation Learning
text: During the minimization of LInfo, we cannot minimize Lµsup in Eq. (10) directly since we cannot access supervised and latent classes. Interestingly, we find a similar formulation in clustering-based self-supervised representation learning algorithms.
Remark 11. Clustering-based self-supervised representation learning algorithms, such as DeepCluster [Caron et al., 2018], SeLa [Asano et al., 2020], SwAV [Caron et al., 2020], and PCL [Li et al., 2021a], use prototype representations instead of z+, {z−k }Kk=1 by applying unsupervised clustering on feature representations. This procedure is justified as the approximation of latent class’s mean representation µc with a prototype representation to minimize the supervised loss in Eq. (10) rather than Eq. (2), as a result, the mini-batch size does not depend on the number of negative samples.
This replacement supports the empirical observation in Caron et al. [2020, Section 4.3], where the authors reported SwAV maintained top-1 accuracy on ImageNet-1K with a small mini-batch size, 200, compared to a large mini-batch, 4 096. On the other hand, SimCLR [Chen et al., 2020a] did not.

heading: 5 Experiments
text: We numerically confirm our theoretical findings by using SimCLR [Chen et al., 2020a] on the image classification tasks. Appendix F contains NLP experiments and some analyses that have been omitted due to the lack of space. We used datasets with a relatively small number of classes to compare bounds. Our experimental codes are available online.8
Datasets and Data Augmentations We used the CIFAR-10 and CIFAR-100 [Krizhevsky, 2009] image classification datasets with the original 50 000 training samples for both self-supervised and supervised training and the original 10 000 validation samples for the evaluation of supervised learning. We used the same data augmentations in the CIFAR-10 experiment by Chen et al. [2020a]: random resize cropping with the original image size, horizontal flipping with probability 0.5, color jitter with a strength parameter of 0.5 with probability 0.8, and grey scaling with probability 0.2.
Self-supervised Learning We mainly followed the experimental setting provided by Chen et al. [2020a] and its implementation.9 We used ResNet-18 [He et al., 2016] as a feature encoder without the last fully connected layer. We replaced the first convolution layer with the convolutional layer
7Arora et al. [2019, Table D.1] mentioned that this phenomenon is not covered by the CURL framework. 8https://github.com/nzw0301/Understanding-Negative-Samples. We used Hydra [Yadan, 2019], GNU Parallel [Tange, 2020], Scikit-learn [Pedregosa et al., 2011], Pandas [Reback et al., 2020], Matplotlib [Hunter, 2007], and seaborn [Waskom, 2021] in our experiments.
9https://github.com/google-research/simclr
with 64 output channels, the stride size of 1, the kernel size of 3, and the padding size of 3. We removed the first max-pooling from the encoder, and we added a non-linear projection head to the end of the encoder. The projection head consisted of the fully connected layer with 512 units, batchnormalization [Ioffe and Szegedy, 2015], ReLU activation function, and another fully connected layer with 128 units and without bias.
We trained the encoder by using PyTorch [Paszke et al., 2019]’s distributed data-parallel training [Li et al., 2020] on four GPUs, which are NVIDIA Tesla P100 on an internal cluster. For distributed training, we replaced all batch-normalization with synchronized batch-normalization. We used stochastic gradient descent with momentum factor of 0.9 on 500 epochs. We used LARC [You et al., 2017]10, and its global learning rate was updated by using linear warmup at each step during the first 10 epochs, then updated by using cosine annealing without restart [Loshchilov and Hutter, 2017] at each step until the end. We initialized the learning rate with (K + 1)/256. We applied weight decay of 10−4 to all weights except for parameters of all synchronized batch-normalization and bias terms. The temperature parameter was set to t = 0.5.
Linear Evaluation We report the validation accuracy of two linear classifiers: mean classifier and linear classifier. We constructed a mean classifier by averaging the feature representations of z per supervised class. We applied one data augmentation to each training sample, where the data augmentation was the same as in that the self-supervised learning step. For linear classifier g, we optimized g by using stochastic gradient descent with Nesterov’s momentum [Sutskever et al., 2013] whose factor is 0.9 with 100 epochs. Similar to self-supervised training, we trained the classifier by using distributed data-parallel training on the four GPUs with 512 mini-batches on each GPU. The initial learning rate was 0.3, which was updated by using cosine annealing without restart [Loshchilov and Hutter, 2017] until the end.
Bound Evaluation We compared the extension bound of CURL (8) and our bound (10) by varying the number of negative samples K. We selected K + 1 ∈ {32, 64, 128, 256, 512} for CIFAR10 and K + 1 ∈ {128, 256, 384, 512, 640, 786, 896, 1024} for CIFAR-100. After self-supervised learning, we approximated µc by averaging 10 sampled data augmentations per sample on the training dataset and evaluated Equations (8) and (10) with the same negative sample size K as in self-supervised training.11 We reported the averaged values over validation samples with 10 epochs: (⌊10 000/(K + 1)⌋ × (K + 1)× epoch) pairs of (z,Z). Note that we used a theoretical value of υ defined by Eq. (9) to avoid dividing by zero if a realized υ value is 0. We also reported the upper bound of collision (11) without constants α, β referred to as “Collision Bound” on the training data. See Appendix F for details.

heading: 5.1 Experimental Results
text: Table 1 shows the bound values on CIFAR-10 and CIFAR-100. We only showed a part of values among different numbers of negative samples due to the page limitation.12 We reported mean and linear classifiers’ validation accuracy as “µ acc” and “Linear acc”, respectively. As a reference, we reported practical linear evaluation’s validation accuracy as “Linear acc w/o”, where we discarded the non-linear projection head from the feature extractor [Chen et al., 2020a]. Since the CURL bound (8) does not contain †Lµsup explicitly, we subtracted †Lµsup from L µ sub in Eq. (8) and reported †Lµsup and subtracted L µ sub as
†Lµsub for the comparison. We confirmed that CURL bounds converged to †Collision with relatively small K. On the other hand, proposed bound values had still a large proportion of supervised loss Lµsup with larger K. Figure 1 shows upper bounds of supervised loss Lsup and the linear accuracy by rearranging Equations (8) and (10). The reported values were averaged over three training runs of both self-supervised and supervised steps with different random seeds. The error bars represented the standard deviation.
10https://github.com/NVIDIA/apex 11Precisely, µc = 1Nc ∑N i=1 I[yi = c] 1 10 ∑10 j=1 f(aj(xi)). 12Tables 4 and 5 in Appendix F provides the comprehensive results.

heading: 6 Related Work

heading: 6.1 Self-supervised Representation Learning
text: Self-supervised learning tries to learn an encoder that extracts generic feature representations from an unlabeled dataset. Self-supervised learning algorithms solve a pretext task that does not require any supervision and can be easily constructed on the dataset, such as denoising [Vincent et al., 2008], colorization [Zhang et al., 2016, Larsson et al., 2016] solving jigsaw puzzles [Noroozi and Favaro, 2016], inpainting blank pixels [Pathak et al., 2016], reconstructing missing channels [Zhang et al., 2017], predicting rotation [Gidaris et al., 2018], and adversarial generative models [Donahue and Simonyan, 2019] for vision; predicting neighbor words [Mikolov et al., 2013], generating neighbor sentences [Kiros et al., 2015], and solving masked language model [Devlin et al., 2019] for language. See also recent review articles [Le-Khac et al., 2020, Schmarje et al., 2021].
Recent self-supervised learning algorithms for the vision domain mainly solve an instance discrimination task. Exemplar-CNN [Dosovitskiy et al., 2014] is one of the earlier algorithms that can obtain generic feature representations of images by using convolutional neural networks and data augmentation. After van den Oord et al. [2018] proposed InfoNCE loss function, many state-of-the-art self-supervised algorithms minimize InfoNCE-based loss function, e.g., DeepInfoMax [Hjelm et al., 2019], AMDIM [Bachman et al., 2019], SimCLR [Chen et al., 2020a], CPCv2 [Hénaff et al., 2020], MoCo [He et al., 2020], and SwAV [Caron et al., 2020].

heading: 6.2 Theoretical Perspective
text: InfoNCE [van den Oord et al., 2018] was initially proposed as a lower bound of intractable mutual information between feature representations by using noise-contrastive estimation (NCE) [Gutmann and Hyvärinen, 2012]. Optimizing InfoNCE can be considered as maximizing the InfoMax principle [Linsker, 1988]. The history of InfoMax-based self-supervised representation learning dates back to more than 30 years ago [Hinton and Becker, 1990]. However, this interpretation does not directly explain the generalization for a downstream task. Indeed, Tschannen et al. [2020] empirically showed that the performances of classification on downstream tasks and mutual information estimation are uncorrelated with each other. Kolesnikov et al. [2019] also reported a similar relationship between the performances of linear classification on downstream tasks and of pretext tasks. McAllester and Stratos [2020] theoretically showed the limitation of maximizing the lower bounds of mutual information – accurate approximation requires an exponential sample size.
As the most related work, Arora et al. [2019] provide the first theoretical analyses to explain the generalization of the CURL. It is worth noting that our analysis focuses on the different representation learning setting. Shortly after our publishing a draft of this paper on arXiv, Ash et al. [2021] also
published a paper on the role of negative samples in CURL bound with InfoNCE loss for fully supervised classification using the coupon collector’s problem. Thus we believe that the coupon collector’s problem is a key ingredient to analyze the connection between contrastive learning and supervised classification based on the CURL analysis by Arora et al. [2019]. Their work was developed independently of ours and their analysis is for contrastive unsupervised learning rather than self-supervised learning that is done in this work. The proposed bound by Ash et al. [2021] has also similar issue to Arora et al. [2019] as in our analysis; however, their bound holds with smaller K than C. Bansal et al. [2021] decomposed the generalization error gap of a linear classifier given feature representations. Wang and Isola [2020] decomposed the self-supervised loss into alignment and uniformity and showed properties of both metrics. Li et al. [2021b] provided an interpretation of InfoNCE through a lens of kernel method. Mitrovic et al. [2021] provided another theoretical analysis with causality for instance discriminative self-supervised learning. Tosh et al. [2021] also analyzed self-supervised loss for augmented samples, but they only focused on one negative sample setting. Recently, Wei et al. [2021] proposed learning theoretical analysis by introducing “expansion” assumption for self-training where (pseudo) labels are generated from the previously learned model. Learning theory-based analyses were also proposed for other types of self-supervised learning problem such as reconstruction task [Garg and Liang, 2020, Lee et al., 2021] and language modeling [Saunshi et al., 2021]. The theoretical analysis on self-supervised representation algorithms without negative samples [Tian et al., 2021] cannot be applied to the contrastive learning setting.

heading: 6.3 Hard Negative Mining
text: In metric learning and contrastive learning, hard negative mining, such as Kalantidis et al. [2020], is actively proposed to make training more effective to avoid using inappropriate negative or too easy negative samples. The current work mainly focuses on the quality of negative samples rather than quantity of negative samples. However, removing false-negative samples can reduce the effect of the collision term in our bounds. Thus our analysis might provide a theoretical justification for hard negative mining.

heading: 7 Conclusion
text: We applied the CURL framework to the recent self-supervised representation learning formulation. We pointed out that the existing framework has difficulty explaining why large negative samples in self-supervised learning improve classification accuracy on a downstream supervised task as in Figure 1. We proposed a novel framework using the coupon collector’s problem to explain the phenomenon and confirmed our analysis on real-world benchmark datasets.
Limitations We did not discuss the properties of data augmentation explicitly in our framework. Practically, self-supervised representation learning algorithms discard the projection head after selfsupervised learning, but our analysis does not cover this procedure. We believe that extensions to cover these settings are fruitful explorations of future work.

heading: Acknowledgments
text: This work is supported (in part) by Next Generation AI Research Center, The University of Tokyo. The experiments were conducted using the SGI Rackable C2112-4GP3/C1102-GP8 (Reedbush-H/L) in the Information Technology Center, The University of Tokyo. We thank Han Bao, Yoshihiro Nagano, and Ikko Yamane for constructive discussion and Yusuke Tsuzuku for supporting our experiments. We also thank Junya Honda and Yivan Zhang for LATEX support, specifically, for solving our font issue and MathJax, respectively. We appreciate anonymous reviewers of ICML 2021 and NeurIPS 2021 for giving constructive suggestions to improve our manuscript. KN is supported by JSPS KAKENHI Grant Number 18J20470.

Review summaries:
This paper provides a new theoretical framework to analyze an empirical observation common in self-supervised representation learning, i.e., using a large number of negative samples than the number of supervised classes can improve performance. However, previous work for contrastive unsupervised representation learning cannot explain above observation theoretically. Therefore, the paper proposes a new lower bound using the coupon collector’s problem, and confirms this analysis on the CIFAR-10/100 datasets.

The authors point out a scenario where existing theory for contrastive self-supervised learning does not match up with what is seen empirically. Namely, that the work of Arora et al. (2019) predicts that increasing the number of negative samples will result is poorer generalisation performance, but the opposite is often seen in practice. The authors adapt the framework of Arora et al. (2019) to improve in this area, and experimentally show that their bound is tighter when the number of negative samples grows.

The authors present some theoretical analysis that extend the analysis in CURL [Arora et al 2019]. The task they study is two steps: first learning an encoder with self-supervised learning (SSL) without labels and then freezing the encoder and learning linear classifiers with supervised learning (Sup) and using the labels on the same dataset. The analysis is trying to explain why having a large number of negative samples during contrastive self supervised pretraining with SimCLR  does not degrade the performance of the supervised second stage. They study the relationship between the two losses and validate their bounds on CIFAR.