Understanding Negative Samples in Instance Discriminative Self-supervised Representation Learning
Authors: Kento Nozawa
Issei Sato
Venue: NeurIPS 2021 Poster (2021)
Keywords: representation learning
self-supervised representation learning

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.

Understanding Negative Samples in Instance Diseriminative Self-supervised Representation Learning
Kento Nozawa
Issei Sato The University Tokyo satoßg. ecc. u-tokyo ac ac.
The University of Tokyo RIKEN AIP nzwēg. ecc. u-tokuo. acc.u-tokyo.ac.jpp jp.
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 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 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 's problem. Our bound can implicitly incorporate the supervised loss of the downstream task the self- supervisdd loss by increasing the number of negative samples. We confirm that our proposed analysis holds on real-world benchmark datasets.
Introduction
Self-supervised representation learning is popular class of unsupervised representation learning algorithms in the domains of vision [Bachman et al., 2019, Chen 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 linear classifier attain classification accuracy comparable supervised method from scratch, especially in a few amount of labeled data regime [Newell and Deng, 2020, Hénaff al., 2020, Chen et al., 2020b]. For example, SwAV [Caron al., 2020] with ResNet-50 has top-1 validation accuracy of 75.3% on the ImageNet-1 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 oftt-e-att-h 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 the minimization of cross-entropp loss K + instance- wise classification, where is the number of negative samples. Despite the empirical success of self-supervised learning, 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 representa- tion learning (CURL). However, there exists gap between the theoretical analysis and empirical observation in Figure 1. Precisely, expect that large number of negative samples degrade supervised loss on downstream task from the analysis by Arora et al. [2019]. In practice, however,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

a large number of negative samples are commonly used in self-supervised representation learning algorithms [He et al., 2020, Chen 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 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.
2 InfoNCE-based Self-supervised Representations Learning
We focus on Chen et al. [2020a]'s self- supervised representation learning formulation, namely, SimCLR. Let X' be an input space, e.g.,
Arera et al.
10'-
Ours
Valeiation accuracyy (%) on CIFAR-100
X C Igchannelxwidte xheight for color images. We can only access unlabeled training dataset {x where input x X. SimCLR learns feature extractor f
Upper supervised loss
accuracy
-46
20"
-45
R modeled by neural networks on the dataset, where h is the dimensionality of feature representation. Let 2 f(a(x) that is feature representation of x after applying data augmentation a : X -> X. Data augmentation is pre-defined stochastic function such as composition the horizon- tal flipping and cropping. Note that the out- put of f is normalized by its L2 norm. Let zt f(a* (x)) that is positive feature rep- resentation created from x with different data augmentation a" (.).
201-
102-
128
256
384
512
640
768
896
1024
negative samples
Figure I: Upper bounds of supervised loss and validation accuracy CIFAR-100. By increasing the number of negative samples, validation accu- racy tends to improve. Left bars: The existing contrastive unsupervised representation learning bound (8) also inereases when the number of nega- tive samples increases because the bound of super- vised loss explodes due a collision term that is not related to classification loss (see Eq. (8) for the definition). Right bars with *: On the other hand, the proposed counterpart (10) does not explode. Section 5 describes the details of this experiment.
SimCLR minimizes the following InfoNCE- based loss with K negative samples for each pair of (z, z)):
exp (z xxt/// /1)
Linto (2, = -lnn
E Ez.eZ exp (z zx/t)"
(1)
where 2 2x) that is a set of positive representation zt and negative representations {zī ..., 2x3 created from other samples, (...) an inner product of two representations, and E IR, is a temperature parameter." 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. (I), we expect that f learns an invariant encoder with respect data augmentation After minimizing Eq. (1), f works feature extractor for downstream tasks such as classification.
3 Extension of Contrastive Unsupervised Representation Learning Framework
We focus on the direct relationship between the self-supervised loss and supervised loss to un- derstand the role of the number of negative samples K. For a similar problem, the CURL frame- work [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
In fact, our theoretical analysis valid with asymmetric feature extractors such as MoCo [He et al., 2020].
where the positive and negative features do not come from feature extractor We perform the analysis with é 1 for simplicity, but our analysis holds with any temperature.

---

in Figure 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], 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).
3.1.1 Self-supervised representation learning step
The purpose of the self-supervised learning step is to learn feature extractor 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. (I). The key idea of the CURL analysis is the existence of latent classes C that are associated with supervised classes. Let be probability distribution over and let x be an imput sample drawn from data distribution D. conditioned on latent class с E C. We draw two data augmentations (a, at) from the distribution of data augmentation A and apply them independently
the sample. As result, we have two augmented samples (a( x), a (x)) and call a (x) as positive sample of ax).. Similarly, we draw K negative samples from D for each C E <c....... . ~ DK and K data augmentations from A, and then apply them negative samples. Definition I summarizes the data generation process. Note that A does not change the latent class of x E X.
we suppose data augmentation
Definition (Data Generation Process in Self-supervised Representation Learning Step). Draw input sample: x De:
1. Draw latent classes: c, fcr K
k= K+1;
3. Draw data augmentations: (a,
A2;
Apply data augmentations: a(x), at (x))
5. Draw negative samples: {x k=1 DK
Draw data augmentations: {a k== AK;
7. Apply data augmentations: {a, (x, )
Note that the original data generation process of CURL samples positive sample of x from D. 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).
(f) ==
E
E (a.a m (ag
E (xE~D N= AK
Entoo Z),
(2)
where recall that f(a(x)) and (f(a* (x)), f(aj (x, )).... of (xx))
Since we cannot directly minimize Eq. (2), we minimize the empirical counterpart, Linto (f), by sampling from the training dataset. After minimizing (f), learned f works as a feature extractor in the supervised learning step.
3.1.2 Supervised learning step
At the supervised learning step, we can observe label y y== (1...., for each x that is used the self-supervised learning step. Let S be supervised data distribution over X' V, and o X + Y be a classifier, where g : A + YR and is the frozen feature extractor. Given the
3 'Technically, we not need e draw for self-supervised representation learning. However, we explicitly include it 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:
exp
By (f(((x))))
Luu (g o)
E X.ymSS a~A
In
Ejeyenp exp (g) (()((((x))))
By following the CURL analysis, we introduce mean classifier simple instance of because its loss an upper bound of Eq. (3).* The mean classifier is the linear classifier whose weight of label is computed by averaging representations: My Ex=D, Ea~A f(a(x)), where D is data distribution conditioned on the supervise label y. We introduce the definition the mean classifier's supervised loss as follows:
Definition 3 (Mean Classifier's Supervised Loss).
exp (f(a(x)) (4y)
LH
f
In
(4)
X.J-SS a~d
Ejey exp (f(a(x)) pb))
We also introduce a sub-class loss function. Let sub subset of y and Saub data distribution over X' Vuu. then define the sub-class losses of classifier and mean classifier:
Definition (Supervised Sub-class Losses Classifier g and Mean Classifier with f).
exp gy (f((()))))
Laub o o. Paub)) =
E X.yhSSaah amd
In Σ EjEymn (g(((((x))))
(5)
exp (f(a(x)) Myy
L (P, Vaub))
E x.y-S
(6)
Σ Σjeym exp ff(a(x) 14)
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 feature extractor tends to transfer well to another task. Indeed, Kornblith et al. [2019] empirically show strong correlation between ImageNet's accuracy and transfer accuracy.
3.2 Theoretical Analysis based on CURL
We show that InfoNCE loss (2) is upper bound of the expected sub-class loss of the mean classifier (6).
Step 1. Introduce lower bound We denote sx() = -Ena f(a(x)) and derive lower bound of unsupervised loss Ltnfo
Linto (f)
E e,te M N
E ~D Me
Ento (f(a(x)), (xx)) ((..)...... ((xx)))
D.D and
txn
E Lito (f(a(x)), { (1(x), Hei ........ .......
E
e,tej lim1 x
x
and
E Anto (((a(x)); {M (er M 1) + d(f),
E
s/ 18m xp111
x>D.
and
1
where d(f)=
- E
E cmpxNDD
E [f(a(x))) and
E ((af(x+))]
[f(at [x))] (x))
DD
a5 ~
Connrete inequality is found in Appendix C. Arora et al. [2019] refer to this loss function averaged supervised loss.

---

The first and second inequalities are done by using Jensen's 's inequality for convex function. The proof of the third inequality shown Appendix D.I. 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 col- lision probability:
= IP(Coll(, {cr h * 0), where Col(c, {or Hk=)) =>> Ilee = C₁ and ..... I[-] is the indicator function. We omit the arguments of Col for simplicity. Let Czub ..... 'k' h be function to remove duplicated latent classes given latent classes. We omit the arguments of Czub 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,
Into (f) 2 (1 - TK)
L Luu (f, Coub) Col
K cite I A+1
elase lows [InCCol 11 00
+ 0,66 o 1 K1
(8)
collision
The proof is found in Appendix D.2.
Arora et al. [2019] also show Rademacher complexity-base 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 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.
3.3 Limitations of Eq. (8)
The bound (8) tells us that K gives a trade-off between the sub-class loss and collision term via TK- 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 Crub 2 y However, such 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 тк converges to 1. As 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 T== 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 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 linear classifier with self-supervised representation on CIFAR-10 10 [Chen et al., 2020a, B.9].
4 Proposed Lower Bound for Instance-wiss Self-supervised Representation Learning
To fill the gap between the theoretical bound (8) and empirical observation from recent work, propose another lower bound for self-supervised representation learning. The key idea of our bound replace with different probability since 7 can quickly increase depending on K. The idea is motivated by focusing on the supervised loss rather than the expected sub-class loss.
4.1 Proposed Lower Bound
Let UK be a probability that sampled K latent classes contain all latent classes: {c 2 C. This probability appears in the coupon collector's problem of probability theory (e.g., Durrett [2019,
5

---

Example 2.2.7]). If the latent class probability is uniform: Vc,) = 1/|C|, then we can calculate the probability explicitly follows.
Definition (Probability to Draw All Latent Classes). Assume that p is a uniform distribution over latent classes C. The probability that K latent classes drawn from contain all latent classes is defined as
|C|
C (
(1
m + (1-
(-1)
VK
|C|
1=
02=0
where the first summation is probability that n drawn latent samples contain all latent classes [Nakata and Kubo, 2006, Eq. 2j.
By replacing with obtain our lower bound of InfoNCE loss:
Theorem (Proposed Lower Bound of Self-supervised Loss). For all feature extractor f,
1 Linto 2 2
uK+1
L c. de roph N sub (f,C) Csub = CJ
E
Loss
+(1 UK+1)
[ Caub)) Csub F
e. c. 1
sub-closs loss
E c,(0 (e pep R-1
In (n + d(f).
(10)
collision
The proof is found in Appendix D.3.
Theorem 8 tells us that probability UK+1 converges to 1 by increasing the number of negative samples K; 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 small as in Eq. (8). Let consider the example value of with the same setting discussed in Section 3.3. When =K=32 so 0.719, i..., 71.9% training samples contribute the supervised loss.
4.2 Increasing does not Spread Normalized Features within Same Latent Class
We argue that the feature representations do not have large within-class variance the feature space by increasing 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 (Upper Bound of Collision Term). Given latent class c, K negative classes {cy K and feature extractor f,
In (Col (c, k + +1) a
E
E
f(a(x)) (f((a(xx)) f(a (x)) (11)
XNDD
X'DD.
(a.a (a.at)~A'
where a and are non-negative constants depending on the number of duplicated latent classes.
The proof is found Appendix D.4. 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 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())). 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 a and | does not increase by increasing K (see Table I and Appendix for more analysis).
We show expected K + to draw all supervised labels for ImageNet- 1K and all used datasets in Appendix E.

---

4.3 Small K can Give Consistent Loss Function for Supervised Task
As we shown Theorem 8. Linfo with large K can be viewed as an upper bound of Lup However, Linfo with smaller K can still yield good feature representations for downstream tasks on ImageNet- IK as reported by Chen et [2020a]. Arora et al. [2019] also reported similar results on CIFAR-100 with contrastive losses.? To shed light on this smaller K regime, we focus on the class distributions of both datasets, ImageNet-1 K and CIFAR-10M 100, which are almost uniform.
Proposition 10 (Optimality of Laub). Suppose C y and p is uniform: Vc E C, 1/|C). Optimal o' is a constant function that
Suppose a constant function q x E X I [q).-.., ouipuss vector with the same value if and only if minimizes Be,cc VE Mo Tssub(q", C.ubb). The optimal q" also the minimizer of Laup
The proof is found in Appendix D.5 inspired by Titsias [2016, Proposition 2].
Proposition 10 does argue that self-supervised representation learning algorithms fail to learn feature representations on dataset with non-uniform class distribution. This is because we perform supervised algorithm downstream dataset after representation learning in general.
4.4 Relation Clustering-based Self-supervised Representation Learning
During the minimization of Linfo- we cannot minimize L in Eq. (10) directly since we cannot access supervised and latent classes. Interestingly, we find a similar formulation in clustering bbased 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 iz 1 k== by applying unsu- pervised clustering on feature representations. This procedure is justified as the approximation of latent class's ss mean representation Pe with prototype representation to minimize the supervised loss Eq. (10) rather than Eq. (2), as a result, the mini bati-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 ImageNet- IK with a small mini- mini-batch size, 200, compared to a large mini-batch, 4 096. On the other hand, SimCLR [Chen et al., 2020a] did not.
5 Experiments
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.
Datasets and Data Augmentations We used the CIFAR- 10 and CIFAR-100 100 [Krizhevsky, 2009] image classification datasets with the original 50 000 training samples for both self-supervised and supervised training and the original 10 validation samples for the evaluation of supervised learning. We used the same data augmentations in the CIFAR-10 experiment by Chen et [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 [2020a] and its implementation." 9 We used ResNet-18 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
We mainly followed the experimental setting provided by Chen et al.
Arora et al. [2019, Table D. mentioned that this phenomenon is not covered by the CURL framework. Negative-Samaeeeeeeeeeeeeeee Samples. We used Hydra (adan, 2019). al., 2011], Pandas [Reback et al., 2020], Mat-
'https:// //tpt/ggttttbb hom//nev000//ndeesttaaa
GNU Parallel [Tange, 2020). Seikit-learn [Pedregosa plotib [Hunter, 2007]. and seaborn [Waskom, 2021] in our experiments.
"https://ee //gg::///ttttut thub. com/google-
moooglerreeerreeee resear ceesearc//se himmmmcrr
7

---

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 non-linear projection head to the end of the encoder. The projection head consisted of the fully connected layer with 512 units, batch- normalization [Toffe 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 al., 2019]'s distributed data- 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-normallizttinn with synchronized batch-normalizatioo. We used stochastic gradient descent with momentum factor of 0.9 on 500 epochs. We used LARC [You et al., 2017]"0. 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] 7] at each step until the end. We initialized the learning rate with (K + 1)/256. We applied weight decay of 10- to all weights except for parameters of all synchronized batch-normalization and bias terms. The temperature parameter was set 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 2 per supervised class. We applied one data augmentation to each training sample, where the data augmentation was the same as that the self-supervised learning step. For linear classifier g, we optimized g by using stochastic gradient descent with Nesterov's '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-pat cattaparlllll training the four GPUs with 512 mini-batcher 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 CIFAR- 10 and K + 1 E {128, 256, 384, 512, 640, 786, 896, 1024) for CIFAR-100. After self-supervised learning, approximated pe by averaging 10 sampled data augmentations per sample the training dataset and evaluated Equations (8) and (10) with the same negative sample size K as in self-supervised training." We reported the averaged values over validation samples with 10 epochs: (110000/ (K + 1)J x (K- + +) x epoch) pairs of (z. Z). Note that we used a theoretical value u defined by Eq. (9) avoid dividing by zero if realized value is We also reported the upper bound of collision (1I) without constants a, B referred to as "Collision Bound" on the training data.
See Appendix F for details.
5.1
Experimental Results
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.. We reported mean and linear classifiers' validation accuracy as "H acc" and "Linear acc", respectively. As reference, we reported practical linear evaluation's '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 T.y explicitly, we subtracted T. from T. in Eq. (8) and reported sup and subtracted Li as "L for the comparison. We confirmed that CURL bounds converged to Collision with relatively small K. On the other hand, proposed bound values had still large proportion of supervised loss Liup with larger K. Figure I shows upper bounds of supervised loss Laup 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.
"nttps://githut htttpe///gttuub.cc/////WWWW/ss com//VVDIA//pex
"I Precissly, se = N. Σ.", M[. c Ej fxa))x))) 12 Tables 4 and 5 in Appendix F provides the comprehensive results.
8

---

Table The bound values on CIFAR-10/100 experiments with different + 1. CURL bound and its quantities are shown with f. The proposed ones are shown without Since the proposed collision values are half of Collision, they are omitted. The reported values contain their coefficient except for Collision bound.
CIFAR-10
CIFAR-100
128
512
1024
0.96
1.00
1.00
1.00
0.72
0.92
0.99
1.00
0.69
1.00
1.00
1.00
0.00
0.00
0.62
1.00
ucc
72.75
77.22
78.60
80.12
32.67
34.25
35.90
37.44
Linear acc
77.13
81.33
41.95
45.16
Linear ace wlo
82.02
85.43
86.68
87.66
57.92
58.91
59.30
59.46
Linta
Eq. (2)
2.02
3.29
3.96
1.64
3.32
3.98
4.66
5.31
d(f)
Eq. (7)
1.16
-1.18
-1.18
-1.19
-0.99
-0.98
-0.97
-0.95
Liato bound
Eq. (8)
0.23
1,41
2.08
2.75
0.72
0.46
0.78
1.42
Collision
1.32
2.58
3.26
3.91
0.69
1.15
1.73
2.37
T.aup
0.05
0.00
0.00
0.00
0.00
0.00
0.01
0.00
0.01
0.00
0.00
0.00
1.03
0.30
0.01
0.00
Linta bound
Eq. (10)
E
0.63
0.91
0.90
0.90
0.00
0.00
1.17
1.94
0.26
0.00
0.00
0.00
1.82
1.93
0.79
0.01
Collision bound
Eq. (I))
0.60
0.61
0.62
0.62
0.52
0.52
0.51
0.51
Related Work
6.1 Self-supervised Representation Learning
Self-supervised learning tries to learn an encoder that extracts generic feature representations from an unlabeled dataset. Self-supervised learning algorithms solve pretext task that does not require any supervision and can be casily constructed on the dataset, such as denoising [Vincent et al., 2008], colorization [Zhang et al., 2016. Larsson 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 al., 2015], and solving masked language model [Devlin 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 instance discrim- ination task. Exemplar-Crt (Dosovitskiy et al., 2014] 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-an self-supervised algorithms minimize InfoNCE-bor based loss function, e.g., DeepInf oMax [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 al., 2020].
DeMa
6.2 Theoretical Perspective
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 princi- 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 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 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.
ple [Linsker, 1988]. The history of InfoMax-bast
As the most related work, Arora et al. [2019] provide the first theoretical analyses explain the generalization of the CURL. It worth noting that our analysis focuses on the different representation learning setting. Shortly after our publishing a draft of this paper 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 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 al., 2021] and language modeling (Saunshi et al.. 2021]. The theoretical analysis on self-supervised representation algorithms without negative samples [Tian al., 2021] cannot be applied the contrastive learning setting.
6.3 Hard Negative Mining
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.
7 Conclusion
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 superviud learning improve classification accuracy 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 self- supervised learning, but our analysis does not cover this procedure. We believe that extensions to cover these settings are fruitful explorations of future work.
Acknowledgments
This work is supported (in part) by Next Generation AI Research Center, The University of Tokyo. The experiments were conducted using the SGI Rackable 12211/333/C110022000
(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 ITEX support, specifically, for solving our font issue and MathJax, respectively. We appreciate anonymous reviewers of ICML 2021 and NeurlPS 2021 for giving constructive suggestions to improve our manuscript. KN is supported by ISPS KAKENHI Grant Number 18J20470.
References
Arora, H. Khandeparkar, M. Khodak, O. Plevrakis, and N. Saunshi. A Theoretical Analysis of Contrastive Unsupervised Representation Learning. In ICMI., pages 5628-5637, 2019.
Y. M. Asano, C. Rupprecht, and A. Vedaldi. Self-labelling via Simultaneous Clustering and Representation Learning. In ICLR, 2020.
10

---

J. T. Ash, S. Goel, A. Krishnamurthy, and D. Misra. Investigating the Role of Negatives in Contrastive Representation Learning. 11Xi::106609944333 [cs.LG), 2021.
P. Bachman, R. D. Hjelm, and W. Buchwalter. Learning Representations by Maximizing Mutual Information Across Views. NeurlPS, pages 15535-15545, 2019.
Bansal, G. Kaplun, and B. Barak. For Self-Supervvsed Learning Rationality Implics Gencralization, Provably. In ICLR, 2021.
Bao, G. Niu, and M. Sugiyama. Classification from Pairwise Similarity and Unlaheled Data. ICML, pages 452-461, 2018.
Y. Bengio, A. Courville, and P. Vincent. Representation Learning: A Review and New Perspectives. IEEE Transactions Puttern Analysis and Machine Intelligence, 35(8):1798-1825 2013.
T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry.
A. Askell, S. Agarwal, A. Herbert- G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu,
C. Winter, C. Hesse, M. Chen, Sigler, Litwin, Gray, B. Chess, Clark, Berner, S. Mccandlish, A. Radford, Sutskever, and D. Amodei. Language Models are Few-Shot Learners. In NeurlPS, pages 1877-1901, 2020.
M. Caron, P. Bojanowski, A. Joulin, and M. Douze. Deep Clustering for Unsupervised Learning of Visual Features. In ECCV, pages 139-156, 2018.
M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin. Unsupervised Learning of Visual Features by Contrasting Cluster Assignments. In NeurlPS, pages 9912-9924, 2020.
T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. Simple Framework for Contrastive Learning of Visual Representations. In ICML, pages 1597-1607, 2020a.
Chen, S. Kornblith, K. Swersky, M. Norouzi, G. Hinton. Big Supervupe Models are Strong Supervsper Learners. In NeurlPS, 2020b.
X. Chen and K. Hc. Exploring Simple Siamese Representation Learning, In CVPR, pages 15750-15758, 2021.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR, pages 248 248-255, 2009.
J. Devlin, M.-W. Chang, K. Lec, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT, pages 4171-4186, 2019.
J. Donahue and K. Simonyan. Large Scale Adversarial Representation Learning. In NewrlPS, pages 10542-10552, 2019.
A. Dosovitskiy, P. Fischer, J. T. Springenberg, M. Riedmiller, and T. Brox. Discrininative Unsupervised Feature Learning with Convolutional Neural Networks. NearIPS, pages 766-774, 2014.
R. Durrett. Prohability: Theory and Examples. Cambridge Series Statistical and Prohabilistic Mathematics. Cambridge University Press, edition, 2019.
Flajolet, D. Gardy, and L. Thimonier. Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-organizing Search. Discrete Applied Mathematics, 39(3):207-233 229, 1992.
T. Gao, X. Yao, and D. Chen. SimCSE: Simple Contrastive Learning of Sentence Embeddings. In EMNLP. 2021.
S. Garg and Y. Liang. Functional Regularization for Representation Leaming: A Unified Theoretical Perspective. In NewrlPS, pages 17187-17199, 2020.
Gidaris, P. Singh, and N. Komodakis, Unsupervised Representation Learning Predicting Image Rotations. ICLR, 2018.
J.-B. Grill, Strub. F. Altché, C. Tallec, H. Richemond, E. Buchatskaya, C. Doersch, A. Pires. D. Guo, M. G. Azar, B. Piot, K. Kavukcuoglu, R. Munos, and M. Valko. Bootstrap Your Own Latent A New Approach to Self-Supervised Learning. In NewrIPS, pages 21271-21284, 2020.
M. U. Gutmann and A. Hyvärinen. ContraCvne Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics. Journal Machine Learning Research, 13:307-361, 2012.
11

---

K. He, X. Zhang, S. Ren, and J. Sun. Deep Residual Learning for Image Recognition. In CVPR. pages 770-778. 2016.
K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum Contrast for Unsupervised Visual Representation Learning. In CVPR. pages 9735, 2020.
O. J. Hénaff, A. Srinivas, J. De Fauw, A. Razavi, C. Doersch, S. M. A. Eslami, and A. Van den oord. Data- Efficient Image Recognition with Contrastive Predictive Coding. In ICML, pages 4182-4192 2020.
G. E. Hinton and S. Becker. An Unsupervised Learning Procedure that Discovers Surfaces in Random-dot Stercograms. In IJCNN, pages 218-222, 1990.
R. D. Hjelm. A. Fedorov, S. Lavoie-Marchine Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengio. Learning Deep Representations by Mutual Information Estimation and Maximization In ICLR, 2019.
J. D. Hunter. Marplotlib: A 2D graphics environment. Computing in Science & Engineering, 9(3):90-95 2007. doi: 10.1 109//CSE..200.55.
S. loffe and C. Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In ICML, pages 448 456, 2015.
A. Joulin, E. Grave, P. Bojanowski, and T. Mikolov. Bag of Tricks for Efficient Text Classification. In EACL, volume 2, pages 427-431, 2017.
Y. Kalantidis, M. B. Sariyildiz, N. Pion, P. Weinzaepfel, and D. Larlus. Hard Negative Mixing for Contrastive Learning. In NeurIPS, pages 21798 21809, 2020.
R. Kiros, Y. Zhu, R. Salakhurdinov, R. S. Zemel, A. Torralba, R. Urtasun, and S. Fidler. Skip- Thought Vectors. In NewrIPS, pages
2015.
A. Kolesnikov, X. Zhai, and L. Beyer. Revisiting seff-Supervised Visual Representation Learning. In CVPR, pages 1920-199999 1929, 2019.
S. Kornblith, J. Shlens, and Q. V. Le. Do Better ImageNet Models Transfer Better? In CVPR, pages 2661-2671, 2019.
A. Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Technical report, 2009.
B. Kulis. Metric Learning: A Survey. Foundations and Trendy@ in Machine Learning, 5(4):287-364, 2012.
Larsson, M. Maire, and G. Shakhnarovich. Learning Representations for Automatic Colorization. ECCV, pages 577-593, 2016.
Ke-Khae, Healy, and Smeaton. Contrastive Representation Learning: Framework and Review. IEEE Access, 8:193907- 193934, 2020.
D. Lee, Q. Lei, N. Saunshi. J. Zhuo. Predicting What You Already Know Helps: Provable Suler-uuer Learning. In NewrIPS, 2021.
J. P. Zhou, Xiong, and Hoi. Prototypical Contrastive Learning Unsupervised Representations. In ICLR, 2021a.
Li, Y. Zhao, Varma, O. Salpekar, P. Noordhuis, T. Li, A. Paszke, J. Smith, Vaughan, Damania, and Chintala. PyTorch Distributed: Experiences on Accelerating Data Parallel Training. VLDB, pages 3005-3018, 2020.
Y. Li, R. Pogodin, D. J. Sutherland, and A. Gretton. Self-Supervised Learning with Kernel Dependence Maximization. In NeurlPS, 2021h.
R. Linsker. Seff-Organizattin in a Perceptual Network. Computer, 21(3):105 117, 1988.
Logeswaran
An Efficient Framework Learning Sentence Representations. In ICLR, 2018.
I. Loshchilov and F. Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. In ICLR, 2017.
D. McAllester and K. Stratos. Formal Limitations on the Measurement of Mutual Information. In AISTATS. pages 875-884, 2020.
T. Mikolov. 1. Sutskever. K. Chen, G. Corrado, and J. Dean. Distributed Representations of Words and Phrases and their Compositionality, In NewrlPS, pages 3111-31111111 2013.
12

---

T. Mikolov, E. Grave, P. Bojanowski. C. Puhrsch, and A. Joulin. Advances in Pre- Pre-Trainng Distributed Word Representations. In LREC, pages 52 55, 2018.
J. Mitrovic, B. McWilliams, J. Walker, L.. Buesing, and C. Blundell. Representation Learning via Invariant Causal Mechanisms. In ICLR, 2021.
Nakata and Kubo. A Coupon Collector's Problem with Bonuses. Fourth Colloquium on Mathematics and Computer Science, pages 215-224, 2006.
A. Newell and J. Deng. How Useful is Self- Supervuueee Pretraining for Visual Tasks? In CVPR, pages 7345-7354 2020.
M. Noroozi and P. Favaro. Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles. In ECCV. pages 69-84, 2016.
K. Nozawa, P. Germain, and B. Guedj. PAC- PAC-Bayesian Contrastive Unsupervised Representation Learning. In UAI, pages 21-30, 2020. 2020.
A. Paszke, S. Gross, F. Massa. A. Lerer, J. Bradbury, G. Chanan. T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf. E. Yang. Z. DeVito, M. Raison, A. Tejani, Chilamkurthy, B. Steiner, L. Fang. Bai, and S. Chintala. PyTorch: An Imperative Style, High-PPeformance Deep Learning Library. NeurlPS, pages 8024-8035, 2019.
D. Pathak, P. Krähenbühl, J. Donahue, T. Darrell, and A. A. Efros. Context Encoders: Feature Learning by Inpainting. In CVPR, pages 2536-2544 2016.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Édouard Duchesmay. Scikit-leam: Machine Learning in Python. Journal of Machine Learning Research, 12(85):8225-2830, 2011.
J. Reback, W. McKinney, jbrockmendel. J. V. den Bossche, T. Augspurger, P. Cloud, gfyoung, Sinhrks, A. Klein, M. Roeschke, S. Hawkins, J. Tratner, C. She, W. Ayd, T. Petersen, M. Garcia, J. Schendel, A. Hayden, MomlsBccsFrriend V. Jancauskas, P. Battiston,
Scabold, chris-bl, h-vetinari, S. Hoyer, W. Overmeire, alimemaster1, K. Dong, C. Whelan, and M. Mchyar. pandas-dev/pandas: Pandas 1.0.3, Mar. 2020. URL https://doi. http:://doi.oo//1.... 10.g/10.550 5281/zenodo 3715232..
N. Saunshi, S. Malladi, and S. Arora. A Mathematical Exploration of Why Language Models Help Solve Downstream Tasks. In ICLR, 2021.
Schmarje, M. Santarossa, S.-M. Schröder, and R. Koch. A Survey on Semi-, Self-and Unsupervised Learning Image Classification. IEEE Access, 9:82146-8216,, 2021.
Snell, S. Twitter, and S. Zemel. Prototypical Networks for Few-shot Learning. NeurlPS, pages 4077-4087,201 2017.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the Importance of Initialization and Momentum in Deep Learning. In ICMI, pages 1139-1147 1147, 2013.
O. Tange. GNU Parallel, Nov. 2020. URL https:///olt http:://///oooo///////// 5281 2281/zemodo.oo 4284075.
Y. Tian, X. Chen, and S. Ganguli. Understanding Self-Supervised Learning Dynamies without Contrastive Pairs. ICML, pages 10268-10278, 2021.
M. K. Titsias. One-vs-Each Approximation to Softmax for Scalable Estimation of Probabilitics. In NeurlPS, pages 4168-4176, 2016.
C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive Learning, Multi-view Redundancy, and Linear Models, In ALT, pages 1179-1206. 2021.
M. Tschannen, J. Djolonga, K. Ruhenstein, S. Gelly, and M. Lucie. On Mutual Information Maximization for Representation Learning. In ICLR, 2020.
A. van den Oord, Y. Li, and O. Vinyals. Representation Learning with Contrastive Predictive Coding. arXiv: 037777374822 LG), 2018.
P. Vincent, H. Larochelle, Y. Bengio, and P.A. Manzagol. Extracting and Composing Robust Features with Denoising Autoencoders. In /CML, pages
2008.
13

---

P. Virtanen, R. Gommers. T. E. Oliphant. M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson. W. Weekesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. Nelson, E. Jones, Kern, Larson, C. Carey, I. Polat, Y. Feng. E. Moore, VanderPlas, Laxalde, J. Perktold, R. Cimrman, I. Hcnriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. Ribeiro, F. Pedregosa, van Mulbregt, and SciPy 1.0 Contributors, SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10. 10.0008/41192201-006666
T. Wang and P. Isola. Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere. In ICML, pages 9929-9999999 9939,9939, 2020.
W. Y. Wang and D. Yang. That's So Annoying!!!: A Lexical and Trame-Semanter Embedding Based Data Augmentation Approach to Automatic Categorization of Annoying Behaviors using #petpeeve Tweets. In EMNIP, pages 2557-2563, 2015.
M. L. Waskom, seaborn: Statistical Data Visualization. Journal of Open Source Software, 6(60):3021, 2021. doi: 10.21105/jjss.03022 URL httpa://doi. org/00...../.... 21105/joss 000221.
C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical Analysis of Self- Self-Training with Deep Networks Unlabeled Data. In ICLR, 2021.
Z. Wu, Y. Xiong, S. X. Yu, and D. Lin. Unsupervised Feature Leamingg via Non-Parametric Instance Discrimina- tion. In CVPR, pages 3733 3742, 2018.
O. Yadan. Hydra A Framework for Elegantly Configuring Complex Applications. GitHub, 2019. URL https://github www/faccceaaeeeee htt///fccooooreeerrrrrh///tt
Y. You, I. Gitman, and B. Ginsburg. Large Batch Training of Convolutional Networks. arXiv:1708.038883 [cs.CVJ, 2017.
R. Zhang, P. Isola, and A. A. Efros. Colorful Image Colorization. In ECCV, pages 649 666, 2016.
R. Zhang, P. Isola, and A. A. Efros. Split-Brain Autoencoders: Unsupervised Learning by Cross-Channel Prediction. In CVPR, pages 1058-1067, 2017.
X. Zhang, J. Zhao, and Y. LeCun. Character-level Convolutional Networks for Text Classification. In NeurlPS, pages 649 657, 2015.
14


Reviews:
[{"review_id": "bWxncVN58Xc", "reviewer": "Reviewer_QhKs", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Previous works on theoretical framework of contrastive unsupervised representation learning cannot explain the empirical observation that increasing the number of negative samples can improve performance. This paper proposes to analyze it with a novel lower bound with the help from the coupon collector’s problem of probability theory. The methodology part is organized in a clear form. Writing is good and easy to follow. The proposed bound is also evaluated in two CV datasets.\n\nHowever, the reviewer still has following three concerns.\nFirst, comparing to the important related work, i.e., CRUL (Arora et al., 2019), this paper only conducts experiments on image domains but ignoring text domains. More experiments on other domains should be investigated for robust performance and validation.\n\nSecond, Figure 1 is still unclear. It is mentioned in the second page, while readers have to read all equations until eq.(8) and (10) in fifth page to understand the meaning. Besides, the legend is confusing, why not using different color for left/right bars.\n\nThird, recent work of BYOL (Grill et al., 2020) and SimSaim (Chen et al., 2021) build self-supervised learning framework without negative samples, which are not discussed in this paper.\n\n### Post-rebuttal and discussions\n\nThanks to authors' responses. Actually, their response has answered most of my concerns.\n\nBesides my previous concerns, I also agree with other reviewers that the proposed theoretical framework is limited to no-transfer tasks in self-supervised learning. \nAlthough in authors’ response, they pointed out the proposed framework can be plugged into transfer learning case. Still, it requires a thorough analysis and empirical evaluation.\nI suggest authors to discuss above limitations in the paper, since they use a rather ambitious title.\n\nHowever, as mentioned in authors' response, this paper indeed provides a theoretical explanation on some important observations (increasing number of negatives helps improving accuracy) in previous works (SimCLR, MoCo, etc.), which is untouched in CRUL. Therefore, I choose to increase the score to 6, marginally above the borderline.\n\nI also think authors should try to demonstrate the main take-away in the introduction part, instead of the current statement in L40-41, which can possibly help readers better understanding their contributions.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see my main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "VmYvQgsqrUi", "reviewer": "Reviewer_Rz1c", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main goal of the paper is to improve the theoretical analysis from Arora et al. (2019) to better match phenomena that are seen in practice. This is accomplished using an argument based on the coupon counter's problem. I think the main take-away of the paper is an interesting contribution, but I find the derivations somewhat hard to follow in some places so I'm not sure if my assessment is entirely accurate. I would appreciate if the authors could answer a few questions so I can check my understanding of the paper:\n* What is the relationship between latent classes and supervised classes? From what I can tell, it is assumed that the set of supervised classes will be a subset of the latent classes, but would it not be more realistic to say that supervised classes are mixtures/unions of latent classes?\n* Definition 7 requires $\\rho$ to be a uniform distribution over latent classes, but from my understanding Arora et al. (2019) do not require this. What are the possible negative implications of this additional assumption?\n* Table 1 and Figure 1 seem to be at odds: the table shows that the proposed bound increases (albeit slower) as a function negative samples, but Figure 1 shows a peak and then decrease.\n\nFor now, I have set my rating to marginally below the acceptance threshold because of the concerns outlined in the questions above. I am open to revising this score upwards after reading feedback from the authors.\n\nPost response: my concerns have been somewhat addressed, so I have increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is some discussion of the limitations, where they mention that their approach does not take into account data augmentation explicitly. Looking at Table 1, I think another limitation is that their analysis does not completely solve the problem they identified with the work of Arora et al. (2019), though they do seem to have tighter bounds.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "A3IX-0a2hB", "reviewer": "Reviewer_TgcC", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**:\n- The paper offers an interesting analysis on why performance does not decrease with more negatives for infoNCE, for a task that is  common in SSL papers, eg learning on imagenet without labels and then testing on imagenet after learning linear classifiers on the same training data with the labels.\n- Overall the paper is well written and clear. Note that I did not go through the proofs in the appendix, but the main paper analysis seems reasonable.\n - The observations from Theorem 8 and the analysis on contributions from the sub-class loss is interesting.\n\n\n**Weaknesses** (and questions):\n\nA) The biggest weakness I think is that the analysis happens on a very restricted scenario, with no transfer: the authors study only the case where we have a single dataset and learn the encoder without using the label that we know exist and use to learn the classifiers - this is suboptimal and would not make sense in practive. I understand that this evaluation is common practice in SSL paper, however this is only a small part of the evaulations these papers have, and transfer learning is the more important and realisting setting. The authors do discuss this in lines 121-124 but justifying their choice by only citing empirical evidence of correlation of this \"task\" with transfer tasks, but I wouldn't say there are no guarantees there. Calling the second stage of classifier learning on the same dataset as traing as a  \"downstream supervised task\" is an exaggeration (I would suggest to the authors to rephrase). Although this task \"correlates\" with transfer tasks, it is not clear to me if also this analysis extends. It would be great to discuss this at least a bit further.\n\nB) Even for this task above, there are further simplifications to facilitate the analysis: 1) only the SimCLR case is covered and yet, there is no analysis on a seemingly important (see SimCLR-v2 and other recent papers that show that) part of that approach, ie the projection head. 2) The MoCo approach which is a very popular variant with a memory queue is not discussed. _How does the analysis extend to negatives from a memory queue and dual encoders with exponential moving average?_  3) There is a further sumplification by the use of a mean classifier, which is not common practice . _Why is that simplification there, and is it central for the analysis?_\n\nC) The (absolute) numbers in Table 1 are not so intutive, unbounded and hard to understand. It is really hard to understand what is the main message of Table 1 and some of the rows, eg colisions, could perhaps be made more informative by turning them into probabilities. It is unclear what is meant in line 269 by \"10 sampled data augmentation per sample\" and unclear what reporting the Collision bound without the alpha and beta constants offer (section 4.2 is very unclear to me). \n\nSome more notes/questions:\n- The discussion on clustering based SSL methods and Sec 4.4  is very restricted to this unrealistic task, that becomes even more unrealistic for clustering based pretraining. It is uncler to me what it offers. \n- A missing ref (Kalantidis et al \"Hard Negative Mixing for Contrastive Learning\" NeuriPS 2020) synthesizes hard negatives for contrastive SSL. Same as MoCo, it would be interesting to discuss how this analysis extends to synthetic negatives. \n\n**Rating**\n\nAlthough an interesting study, the paper has limitations (see \"weaknesses\" section above). I would say that the current version of the paper is marginally below the acceptance threshold, but I am looking forward to the authors addressing my concerns above in their rebuttal.\n\n-----------\n## Post-rebutal thoughts\n\nThe authors provided extensive responses to my questions, answering many in a satisfactory way. I still think however that a central concern listed in the original review stand: the fact that Arora et al study the same task that first learns without labels and the with labels on the same dataset (and only that task) doesn't mean that this is what should be the only task to study for \"Understanding Negative Samples in Instance Discriminative Self-supervised Representation Learning\".\n\nIn their response, the authors claim that\n\n> The self-supervised learning setting of our analysis is practical because the setting is quite similar to a semi-supervised learning setting, where we can access massive unlabeled samples and a few labeled samples.\n\nWith all due respect, I wouldn't compare this to semi-supervised learning for one key reason: as the authors also say here, in semi-supervised learning you have few labeled examples, a key property of the task. So, I would totally understand this analysis if the proposed bound was evaluated in a semi-supervised setting. This is not the case here, ie more than few labeled examples per class are used for learning the classifiers in this case.\n\nSimilarly, wrt the answer on the usage of a mean classifier:\n\n> a few-shot learning setting uses a mean classifier, namely, Prototypical Networks [9], which has been cited more than 2700 times, according to Google Scholar.\n\nAgain, in the same way, the use of a mean classifier is indeed justified for few-shot learning, but it is well known that in the case of datasets with many labels, a logistic regression classifiers is superior.\n\nOverall, I do see some merit in this paper, yet I think the breadth of the analysis is not enough; I will keep my score to 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do discuss some limitations, but not potential societal impacts. Given the nature of the work, the latter is not easy to assess and in my opinion it is fine to skip for a theoretical paper on SSL.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to understand a discrepancy between the theory literature (namely, Arora et al., 2019) and recent empirical results in self-supervised learning. Theory suggests that adding more negatives to contrastive learning should degrade downstream classification performance while empirical results have shown the contrary. To rectify this discrepancy, the authors expand prior analysis to introduce a new bound that is tighter in settings with large numbers of negatives.

Reviewers were conflicted about this paper. They all agreed that the problem is interesting and impactful, that the paper was clearly written, and that the contribution helps to resolve the conflict between theory and practice. There were also a number of technical concerns which were largely resolved through the discussion. However, several reviewers were concerned regarding the applicability of the theory to transfer settings in which the pre-training and downstream datasets differ since the current work only focuses on the case where these two datasets match. While I am sympathetic to this concern, I disagree that this addition is necessary for the paper to have impact or be a worthwhile contribution. Expanding the analysis to transfer settings is non-trivial and there is substantial value in addressing the case which is indeed de facto practice for many research papers on contrastive learning. I would encourage the authors, however, to consider the transfer setting for future work. 
Decision: Accept (Poster)