Are all negatives created equal in contrastive instance discrimination?
Authors: Tiffany Cai
Jonathan Frankle
David J. Schwab
Ari S. Morcos
Venue:  (2021)
Keywords: self-supervised learning
contrastive learning
contrastive instance discrimination
negatives
understanding self-supervised learning
ssl

Abstract: Self-supervised learning has recently begun to rival supervised learning on computer vision tasks. Many of the recent approaches have been based on contrastive instance discrimination (CID), in which the network is trained to recognize two augmented versions of the same instance (a query and positive while discriminating against a pool of other instances (negatives). Using MoCo v2 as our testbed, we divided negatives by their difficulty for a given query and studied which difficulty ranges were most important for learning useful representations. We found that a small minority of negatives--just the hardest 5%--were both necessary and sufficient for the downstream task to reach full accuracy. Conversely, the easiest 95% of negatives were unnecessary and insufficient. Moreover, we found that the very hardest 0.1% of negatives were not only unnecessary but also detrimental. Finally, we studied the properties of negatives that affect their hardness, and found that hard negatives were more semantically similar to the query, and that some negatives were more consistently easy or hard than we would expect by chance. Together, our results indicate that negatives play heterogeneous roles and CID may benefit from more intelligent negative treatment.

Under review as a conference paper at ICLR 2021
ARE ALL NEGATIVES CREATED EQUAL IN CONTRASTIVE INSTANCE DISCRIMINATION?
Anonymous authors
Paper under double-blind review
ABSTRACT
Self-supervised learning has recently begun to rival supervised learning com- puter vision tasks. Many of the recent approaches have been based on contrastive instance discrimination (CID), in which the network is trained to recognize two augmented versions of the same instance (a query and positive) while discrimi- nating against pool of other instances (negatives). The learned representation is then used on downstream tasks such as image classification. Using methodology divided negatives by their difficulty for a
from MoCo v2 (Chen et al., (2020c), given query and studied which difficulty ranges were most important for learning useful representations. We found a minority of negatives the hardest 5% were both necessary and sufficient for the downstream task to reach nearly full accu- racy. Conversely, the easiest 95% of negatives were unnecessary and insufficient. Moreover, the very hardest 0.1% of negatives were unnecessary and sometimes detrimental, Finally, we studied the properties of negatives that affect their hard- ness, and found that hard negatives were more semantically similar to the query, and that some negatives were more consistently easy or hard than we would ex- pect by chance. Together, results indicate that negatives vary in importance and that CID may benefit from more intelligent negative treatment.
INTRODUCTION
In recent years, there has been tremendous progress on sulf-supervised learning (SSL), paradigm in which representations are learned using a pre-training task that uses only unlabeled data. These representations then used downstream tasks, such classification object detection. Since SSL pre-training does not require labels, can leverage unlabeled data, which is can be abundant and cheaper to obtain than labeled data. In computer vision, representations learned from unlabeled data have historically underperformed representations learned directly from labeled data. Recently, however, newly proposed SSL methods such MoCo (He et al. 2019 Chen et al. 2020c). SimCLR (Chen et al. 22200 b). SwAV (Caron et al. 2020), and BYOL Grill ct al. 2020) have dramatically reduced this performance gap.
The MoCo and SimCLR pre-training tasks use contrastive instance discrimination (CID), in which a network trained to recognize different augmented views of the same image (sometimes called the query and the positive and discriminate between the query and the augmented views of other random images from the dataset (called negutives)
Despite the empirical successes of CID, the mechanisms underlying its strong performance remain unclear. Recent theoretical and empirical works have investigated the role of mutual information between augmentations (Tian et al., 2020), analyzed properties of the learned representations such as alignment and uniformity (Wang & Isola 2020), and proposed a theoretical framework (Arora eet al., 2019), among others. However, existing works on CID have not investigated the relative importance or semantic properties of different negatives, even though negatives play a central role in CID. In other areas, works hard negative mining in metric learning (Kaya & Bilge 2019) and on the impact of different training examples in supervised learning (Birodkar et al. 2019) suggest that understanding the relative importance of different training data can be fruitful.
In MoCo, these are called the query and positive and treated slightly differently; in SimCLR, both are treated the same and called positives. The other SSL methods listed (not SimCL. .R and MoCo) are not CID.

---

Under review as a conference paper at ICLR 2021
Semantically dissimilar
Nelther necessary nor sufficient for good performance
mm
Easy negatives
Semantically similar, not identical
Necessary and sufficient good performance
Query
Hard negatives
Semantically identical Superficially dissimilar
Harmful to performance
r
Same class negatives
Figure 1: Schematic summary of main results. Easy negatives are unnccessary and insufficient (green) and are more often dissimilar (i.c., in unrelated ImageNet classes) to the query (light blue) compared to harder negatives. Hard (but not the very hardest) negatives were necessary and sufficient (orange) and are more often semantically similar to the query compared to easier negatives. The very hardest negatives are unnecessary and sometimes detrimental and also (red). This illustrative schematic; images and trees are not from ImageNet.
often in the
class the query, compared to easier negatives
In this work, empirically investigate how the difficulty of negatives affects the downstream per- formance of the learned representation. We measure difficulty using the dot product between the normalized contrastive-space embeddings of the query and the negative. A dot product closer suggests a negative that is more difficult to distinguish from the query. We ask how different nega- tives, by difficulty, affect training. Are some negatives more important than others for downstream accuracy? If so, we ask: Which ones? To what extent? And what makes them different?
We focus on MoCo v2 (Chen ImageNet (Deng et al. 2009), and have similar results for SimCLR in Appendix A.2 We make the following contributions (see Figure for summary):
2020c) and the downstream task of linear classification on
The easiest 95% of negatives are unnecessary and insufficient, while the top 5% hard- est negatives are necessary and sufficient: We reached within 0.7 percentage points of full accuracy by training on the 5% of hardest negatives for each query, suggesting that the 95% easiest negatives are unnecessary. (and, therefore, the hardest negatives are necessary): accuracy drops substantially when training on only the easiest 95% of negatives. The hardest 5% of negatives are especially important: training on only the next hardest 5% lowers accuracy by 15 percentage points.
contrast, the easiest negatives are insufficient
The hardest 0.1 % of negatives are unnecessary and sometimes detrimental: Down- stream accuracy was unchanged or improved when we removed these hardest negatives. These negatives were more often in the same ImageNet class the query, compared to easier negatives, suggesting that semantically identical (but superficially dissimilar) nega- tives were unhelpful detrimental.
Properties of negatives: Based on our observations that the importance of a negative varies with its difficulty, we investigate the properties negatives that affect their difficulty.
We found that hard negatives were more semantically similar to the query than were easy negatives: the hardest 5% negatives were more likely to be of the same Im- ageNet class as the query, compared easier negatives. These hard negatives were also closer to the query as measured by depth of the least common ancestor for the negative and the query the WordNet tree (which ImageNet is built upon).
We also observed that the pattern is reversed for the =50% of easier negatives: there, the easier the negative, the more semantically similar is the query.
There exist negatives that are more consistently hard across queries than would be expected by random chance.
2

---

Under review as a conference paper at ICLR 2021
We emphasize that primary aim is to better understand the differences between negatives and the impact of these differences on existing methods rather than to propose a new method. However, results suggest that there may be unexploited opportunities to reduce the cost of modern CID methods (Chen et al., 2020c). For any particular query. only a small fraction of the negatives are necessary. Our observations differences in negative importance block for the understanding and improvement of contrastive learning methods. For example, there may be further room choose specific examples for training, similar to hard negative mining and curriculum learning (Chen et al. [2020a] Chuang et al. 2020 Kaya & Bilge 2019). to reduce costs and improve performance per data sample.
serve valuable building
2 METHODS AND PRELIMINARIES
Contrastive instance discrimination and momentum contrast. Momentum Contrast (MoCo v2) is CID method that reaches accuracy within 6 percentage points of supervised accuracy on Im- ageNet with ResNet-50 (Chen al., 2020c). In MoCo, the task is to learn representation that succeeds at the following: given query (an augmented view of an image), correctly pick a positive (a different augmented view of the same image) from large set of negatives (augmented views of randomly chosen images). Our experiments focus on aspects that are common between CID meth- ods rather than those specific MoCo. We discuss implementation details that may be specific to MoCo v2 here.
The MoCo v2 encoder is ResNet-50 network. For pre-training. the outputs of this base network are fed into a multi-layer perceptron (MLP) head; we refer to the normalized output from the MI. head as the contrastive-spen space embedding. For downstream tasks, the MLP head is discarded and only the base network is used; refer to the output of the base network as the learned representation. A distinguishing feature MoCo is that it has two encoders, one of which is actively trained (used for the query) and the other which is moving average of the trained encoder (used for the positive and negatives). MoCo stores the embeddings of each batch of positives in large queue and uses them as negatives for future batches, enabling the use of more negatives than can fit in batch.
MoCo uses the InfoNCE loss (Gutmann & Hyvärinen 2010 van den Oord et al. 2018):
explq kt/T) 2x-eepp ks/T)
Cy -- log
where q is the embedding of a query (using the learned encoder), k_ is the embedding of a positive (using the momentum encoder), and k; are the embeddings of the negatives in the queue (added using previous states of the momentum encoder). 7 is a temperature hyperparameter.
Difficulty of negatives. To compute the difficulty for set of negatives given particular query, we calculate the dot product between the normalized contrastive-spac embedding of each negative the query. We then sort the dot products and
with the normalized contrastive-space embedding consider the negatives with dot products closer to I to be harder negatives and those with smaller dot products to easier negatives. We use this terminology because it fits intuition: all else being equal, harder negatives increase the loss. Since embeddings are normalized, the dot product is the cosine of the angle between the embeddings the instances and ranges from -1 to 1.
Note that difficulty is defined per query and that it is function of the current state of the network. Thus, a negative can be easy for some queries and hard for others, and the hardness of a negative for given query can vary over training epochs and across different training runs and configurations.
Experimental setting. Our experiments focus on MoCo v2 (Chen et al., 2020c), an improved version of MoCo which combines MoCo v1 (He et al. 2019) with several features of SimCLR (Chen) et al. 2020a). We use ImageNet for pre-trate vre-trainig and evaluate performance using linear classification on ImageNet from the representation learned in the pre- training CID task. The network used, in MoCo v2, is a ResNet-50 with MLP head, and trained for 200 epochs. Unless otherwise noted, we each experiment three times with different seeds; error bars represent mean + standard deviation.
3

---

Under review as a conference paper at ICLR 2021
1055
Meosesayy (Trs on 20. (8650%
92%
Necussary? (Tain on X86 01+2114
Sufficentt (Tran 01 0% to
Suffciant7 (Th on to Xh1
87%
674
6.0%
2 196
33%
27%
375
20%
37%
39%
110
196
37%
15.23%
33.03%
25-3006
35.00%
93335
55-330%
5.00%
3.25%
0.85%
6.30%
6-25%
Figure 2: Easy negatives neither necessary nor sufficient, while hard negatives are both necessary and sufficient. a-b) Top-1 (a) and Top-5 (b) performance of networks trained on only segments of 5% of negatives ordered by difficulty. For example, 95-100% means that only the top 5% hard negatives were used for training. c-d) T (c) and top-5 (d) performance of networks trained on increasingly larger fractions of the easiest negatives. Error bars standard deviation across 3 seeds.
3 WHICH NEGATIVES ARE NECESSARY OR SUFFICIENT?
We examine which negatives, by difficulty, are necessary or sufficient for learning representations that have strong downstream performance. Outside of CID, there are varying perspectives on the value of casy negatives. Research on hard negative mining suggests that harder negatives can be more important than easier negatives for relevant tasks (Kaya & Bilge 2019). However, in some supervised contexts, much all training data seems important for reaching the highest accuracy (Birodkar et al.) 2019). We aim to experimentally assess which of these perspectives applies when using MoCo v2 on ImageNet classification.
To determine whether a set of negatives was necessary, we removed the corresponding negatives on each pre-training step; if the resulting representations still led to accuracy close baseline on the downstream task, then we considered those negatives to have been unnecessary. To determine whether set of negatives was sufficient, we removed all negatives except those in that range on each pre-training step: if the resulting representations still led to strong accuracy on the downstream task, then we considered the negatives in that range to have been sufficient
The easy negatives are unnecessary; the hard negatives are sufficient. First, we asked whether the easy negatives were necessary (or equivalently, whether the hard negatives were sufficient). That is, does the network maintain downstream accuracy when it is pre-trained without the easy negatives? To test this, we evaluated how accuracy changed as different subsets of negatives were removed. Interestingly, we found that using only the hardest 5% of negatives was largely sufficient to recover baseline accuracy (Figure 2 95- 95-100%) suggesting that the overwhelming majority unnecessary. Moreover, the hardest 5% (95- were substantially
of the easier negatives more informative than the next 5% (90-95%) top-1 accuracy dropped by only 0.7 percentage points when trained only the hardest 5% vs. 15 percentage points for the next hardest 5% (90-95%) and 47 percentage points for the third 5% (85-90%; Figure 2b. Going forward, we use 5% as a cutoff' and call the negatives harder than this cutoff hard and those easier than this cutoff easy.
The easy negatives are largely insufficient; the hard negatives are necessary. We next asked whether the easy negatives were sufficient (or, equivalently, whether the hard negatives were neces- sary). Although we found in the previous section that the easy negatives were unnecessary, that does not necessarily mean they are insufficient. For example, it could be that the easy negatives, while individually less important, collectively provide sufficient signal for learning good representations on the downstream task. Alternatively, it is possible that the information contained all of the easy negatives still lacks enough signal; in this case, the easy negatives, even when combined together, would still be insufficient.
We found that even when the easiest 95% of negatives were combined together, accuracy was 5.4% below baseline (Figure -d). In contrast, recall that using only the hardest 5% of negatives (19x fewer) achieved top-1 performance within 0.7% of baseline (Figure 2 Using the easiest 90% of negatives harms accuracy even further (0-90%; Figure Together, these results demonstrate that the easiest negatives, even when they comprise the vast majority of negatives, are still insufficient.
The very hardest negatives are harmful at lower temperatures. We have found that the hard negatives, i.e. the 5% hardest, are largely necessary and sufficient for CID. However, top-1 accuracy actually improved slightly when we removed the very hardest 0. %% of negatives (p = 0.03 for an
We removed sets of negatives by treating them through they were not present in the queue.
4

---

Under review as a conference paper at ICLR 2021
a)
Top 1 Accuracy
b)
Top 5 Accuracy
0.1
10.02%
66.48%
67.6 67%
20.06%
10.10%
66 44%%
67.5%
0.1
87.10% 20.07%
87, 73% 10.13%
87.06%
10.05%
-8.8%
0.3 Temperature
67.2%
Temperature
0.2
20.08%
66.
20.02%
1:0. 07%
67.0%
20. 20.08%
20.05%
87.99%
1.0.0%%
87.6%
66.8%
66. 28%
67.07%
67 033
87.11%
87.79%
97.77%
-...2%%
66.5%
20.04%
2:0.09%
-87.2%
99.0%
99.9%
100.0%
99.0%
99.9%
100.0%
Most difficult negatives included (percentile)
Most difficult negatives included (percentile)
Figure 3: The hardest 0.1 % of negatives hurt, especially at lower temperatures. Top-1 (a) and top-5 (b) accuracy of networks trained on all but hard and hardest negatives, at different temperatures. The baseline temperature is 0.2.
unpaired 1-test) This effect was most pronounced at lower temperatures (Figure 3]: for example, at temperature 0.1 (as opposed to baseline temperature 0.2), training without the hardest 0.1 % of negatives improved downstream top-1 accuracy by 0.23% (p = 0.0003) and top-5 accuracy by 0.67%. One might expect such a difference between temperatures because the hardest negatives are weighted more in the loss at lower temperatures. Interestingly, the effect was larger for top-5 accuracy than top-1 accuracy (compare Figure 3b with Bap.
One hypothesis for why the hardest negatives hurt is that because negatives are randomly sampled, some negatives can be too similar to the query (e.g. augmentations of near-duplicates to the query). Because negatives are randomly sampled, they can included augmented views of images that are near-duplicates of the query otherwise visually very similar to the query. If both the query and negative contain identical semantic content, the contrastive loss might rely on non-semantic features distinguish between them, thus emphasizing these non-semantic features in the representation (Figure These same-class negatives may thus be harmful to learning representations for down- stream linear classification.
If this is the case, we would expect that removing same class negatives would improve performance, perhaps even more than removing the hardest 0.1% of negatives overall. As shown in Table [ removing same-class negatives indeed leads to slightly higher accuracy than removing the hardest 0.1% of negatives. Removing only the subset of the hardest 0.1% of negatives with the same class as the query accounts for all of the improvement from removing the hardest 0.1% of negatives. Alternatively, removing only the subset of the 0.1% hardest negatives with different classes shows no improvement over baseline and in fact decreases top-1 accuracy low temperature.
These results demonstrate that the accuracy benefit of removing the 0.1% hardest negatives can entirely be accounted for by the fact that it removes many elements of the same class as the query, so that removing the 0.1% hardest negatives approximates removing the same-class negatives without requiring access privileged label data. This observation also consistent with recent work which has attempted to "debias" contrastive learning away from same-class negatives (Chuang et al.) 2020).
UNDERSTANDING NEGATIVES BY DIFFICULTY
Hard negatives more semantically similar to the query. We have shown that casy negatives are unnecessary and insufficient, and that, inversely, hard negatives are necessary and sufficient. However, the properties that distinguish easy from hard negatives itively, we might imagine that to learn a representation that is useful for a fine-grained classification task such as ImageNet, a network must learn to distinguish between categories that are similar but semantically distinct, e.g.. different breeds of dogs. If this were the case, we would expect that the 5% hardest negatives, which were both necessary and sufficient for training, would also be more semantically similar to the query than the 95% easiest negatives.
yet understood. Intu-
Forr this section, to remove a set of negatives, we replace them with slightly older negatives, so that the total number of negatives used does not change. To accommodate this change, the queue is made slightly larger, with the additional length remaining unused except replace negatives want remove.
5

---

Under review as a conference paper at ICLR 2021
Temperature
=0.07 Top-5 Ace
Temperature
0.2 Top-5 Acc
Top-1 Acc
Top-1 Acc
Baseline (remove none)
64.78 = 0.31
85.86 = 0.12
67.48 0.07
87.93 0.05
Remove 0.1 1% hardest
66.25 = 0.23
86.98 = 0.09
67.64 = 0.22
87.88
0.07
Remove same class
66.61 = 0.10
86.96 = 0.07
68.07 = 0.12
88,30 + 0.15
Remove 0.1% % hardest n same class
66,43 = 0.04
86.78 + 0.06
67.67 = 0.02
88.09 + 0.18
Remove 0.1 % hardest different class
63.69 = 0.04
85.44 + 0.00
67.38 0.06
87.86 0.08
Remove 99.9% easiest same class
65.06 + 0.11
85.91 + 0.01
67.79 + 0.07
88.05 0.05
The hardest 0.1 % negatives hurt because of same-class negatives: Downstream accu- racy when removing negatives of same/different class as the query and easier/hardest negatives at different temperatures. At temperature 0.07, accuracy improves when removing same-class nega- tives and/or hard negatives. At temperature 0.2 (default), there a similar but smaller effect.
Table I:
b)
Werdlee similant (higher more similar)
1.4
Pinegative quary (abal)
1.0
0.6
0.4
0.2
0.0
Easiest 95%
Hardest 5%
Easiest 95%
Hardest 5%
Figure 4: Semantic similarity is higher for the 5% of hard negatives than for the 95% of easy negatives Proportion of shared labels (higher is more similar) (a) and WordNet distance depth of least common ancestor (lower more similar) (b) for the 5% of hard negatives and the 95% of casy negatives. Error bars are standard deviation on plot values across seeds.
To test this hypothesis, we first examined the fraction the easy and hard negatives that had the same class the query label Similar to our results above regarding the 0.1% very hardest negatives, found that negatives of the same class were significantly overrepresented among the 5% hardest negatives relative to the easy negatives (p- 5.1 10-7, unpaired t-test; Figure 4a).
However, this experiment can only tell us whether the hard negatives contain more negatives that semantically identical to the query (in that they have the same class); it cannot distinguish be- tween negatives of different semantic similarity with the query (which have classes that are related, but distinet from the query). To evaluate semantic similarity
used the ImageNet class hierarchy derived from WordNet (Deng et al. 2009). For each negative, we computed the tree depth of the least common ancestor between the negative and the query; higher WordNet similarity means that the least common ancestor is deeper in the tree and that the negative is therefore more similar to the query As shown in Figure 4b) we found that the hard negatives were significantly more se- mantically similar to the query than the easy negatives (p=4.8e-7, unpaired t-test). Together, these results demonstrate that semantic similarity is a property that distinguishes easy and hard negatives; however, evaluation of whether this relationship is causal is left for future work.
Some of the easiest negatives are both anti-correlated and semantically similar to the query. Perhaps surprisingly.
also found that small subset of the very casiest examples are anti- correlated with the query (i.c., the dot product between these negatives and the query is highly negative; Figure While the presence of negatives orthogonal the query might be expected (as the two might be unrelated to one another) the presence of a high magnitude negative dot product suggests that the network learned anti-correlate these negatives with the query.
Moreover, these negatives are also substantially more semantically similar to the query than the ma- jority of easy negatives (Figure 5b): in fact, by the WordNet tree similarity (depth of least common ancestor), their semantic similarity nearly matches those of the hard negatives. In addition, quali- tatively, the positive and negative classes with the highest mean pairwise negative dot product are
IIn this section, use 2K query images and 2K negatives; use trained non-momentum encoder at 200 epochs. AAthhough WordNet similarity not perfect measure, we do believe it valuable.

---

Under review as a conference paper at ICLR 2021
Wondle aodiitsmaa (Hgper mom
Avcroga det product buswoos negethue and qndqurry
0.6
0.4
0.2
5.333 52
A
4.
0.0
30%
20 40%
40 500
50 50%
70V
10 100000
0.10%
29.20%
40.50%
50.00%
69-10%
70-
10-52%
20%
30%
40%
50%
40%
7P%
40%
1008
hardey
Rese
dangerte
Reladive negative difcuityy (larger harder)
Figure 5: Semantic similarity with query increases with easier negatives, for the easy half of negatives
Similarity, as measured by proportion of shared labels (higher is more similar) (a) and depth of least common ancestor in WordNet tree (higher is more similar) (b) increases with casier negatives, for the easy half of negatives. Similarity also increases with negative difficulty for the harder half of negatives. Average negative distance is negative for the easy half of negatives (c). Error bars are standard deviation on plot values across 3 seeds (for b and c, error bars are so small that they are not visible).
consistently of closely related classes such similar breeds of dog (see Table A4 In contrast to the hard negatives, however, these casiest negatives do not contain many negatives of the same class as the query, although there is slight increase for the very easiest negatives (see inset, Figure 5a Some negatives are consistently easy or hard across queries. The hard negatives drive the majority of learning in CID. However, the negatives are ranked independently for each query, so hard negative for one query may be
4%
Proportion of negatives
(random (wd)
x-thx-xxis x-3xixxxxx valuee
3%
easy for another. Alternatively, are there negatives that are consistently hard or easy across queries? To test this, we started by measuring the percentage of queries for which
2%
with
1%
each negative was hard, i.c. in the hardest 5%. In Fig-
u we plot the empirical density of the frequency with which each negative is hard; the median is 5% by defini- tion. As baseline for comparison, we randomized the negatives for each query to approximate the distribution would expect by chance (orange in Figure (6) The real data distribution (blue) is broader than that expected by chance, so that there are indeed negatives that are more consistently hard and easy than we would expect by ran- dom chance. Perhaps maintaining consistently hard neg- atives in the queue and removing consistently easy ones could improve learning.
0%
0%
2%
4%
6%
8%
10%
positives for which negative is in hardest 5%
Figure 6: There exist negatives that are consistently harder or easier than pected by chance. Distribution tives based on the proportion of positives for which negative is in the hardest 5% for the real data (blue) compared to the distribution obtained by shuffling the negatives for cach query (orange).
nega-
5 RELATED WORK
Contrastive instance discrimination. Recently, CID has been utilized in number of works in- cluding NPID (Wu et al.) 2018), CMC (Tian et al., 2019). Moco (He et al. (2019), SimCLR (Chen) jet al. (020a)). MoCo v2 (Chen et al. (2020c). in chronological order. Inspired by its impressive per- formance, recent works have tried to understand CID from a variety of perspectives. In particular, Tian et. al. 2020) investigated the degree of shared information between two augmentations and how it connects to downstream performance, Wang & Isola (020)) suggested that contrastive objectives implicitly try to align similar instances while uniformly utilizing the embedding space, and AArora et al. (2019) proposed theoretical framework for understanding contrastive learning. Recent work attempted to mitigate the effects of same-class negatives via reweighting scheme (Chuang et al., 2020), but did not study negatives by difficulty, which is our focus here.
Non-imstance-ddicciiinatoo self-supervised learning methods. Beyond CID, a number of other approaches for self-supervised have been proposed that do not work within the CID paradigm, in- cluding RotNet (Gidaris et al. 2018). Jigsaw (Noroozi & Favaro 2016). DeepCluster (Caron et al. 2018). SWAV CCron et al. 2020), SeLa (Asano et al.) 2020). PCL (Li et al.) 2020), and BYOL (Grill et al. 2020). Since these did not employ negatives in the same way as CID, our results do not directly relate to these methods.
7

---

Under review as a conference paper at ICLR 2021
Hard negative mining, There is recurring theme in the machine learning literature of focusing training on the most difficult examples. In active learning, for example, it is common to favor examples which the model is most uncertain (Fu et al. 2013). Work in object detection has also benefited from efforts to find hard examples (Sung) 1996; Canévet & Fleuret, Shrivvsssaa et al., 2016). However, none of the aforementioned work explicitly involved negative examples in the context of CID.
Closest CID is work on metric learning, where the goal is to learn a representation for each example that is conducive to clustering (Kaya & Bilge 2019). A standard approach is to use a triplet loss. where the loss encourages representing query (often called an anchor) example in fashion that is close to positive examples from the same class and far from negative examples from other classes (Weinberger Saul 2009). In this paradigm, selecting the hardest (Bucher et al.) (016) or harder (Schroff et al., 20155) negatives has improved both the rate of learning and final performance. Similar to our findings about MoCo, WW et al. (2017) found that mining the very hardest negatives hurts performance (purportedly because it increases the variance of the gradients); they suggested mining harder (but not the hardest) negatives instead.
Example importance in classification. In contrast to our work and the aforementioned work on hard negative mining in metric learning, nearly all examples are necessary in image classification. No paper that are aware of could eliminate more than 20% of examples from CIFAR- 10 (Toneva) et al. 2018) or 10% from ImageNet (Vodrahalli et al. 2018 Birodkar et al. 2019) without decreases in accuracy. However, not all examples are learned at the same time: the networks learn "easy" examples first (Arpit et al. [0117] Mangalam & Prabhu 2019) and "hard" examples later in training. However, our notions of easy, hard, and necessary are different than this work: we determine these qualities on a per-query basis (meaning different examples can be easy or hard for different queries) while this work assigns these qualities to specific examples for all of training or across training runs.
DISCUSSION
Negatives are critical to CID. We studied the relative importance of subsets of negatives, by diffi- culty, in the context of MoCo v2 Chen et al. (2020c), and found that negative importance varied dramatically by difficulty (Figure I]: the vast majority (casiest 95%) of negatives were insufficient without the hardest and were unnecessary when those 5% were included (Section B). Moreover, we found that the very hardest negatives were unhelpful or even harmful to performance and that this could be accounted for by an over-representation of same-class negatives. To understand why the hard negatives are helpful, we showed that the hard negatives are more semantically similar to the query than the easy negatives (Section 4. We also found that there exist easy negatives that are both anti-correlated and semantically similar to the query. and that some of the negatives are consistently easy or hard across queries. Many of these observations are line with what has been found in other contexts on hard negative mining for metric learning, where accuracy and sample complexity have improved through judicious negative selection methods. Insights from our work may motivate approaches that yield benefits of similar nature in CID.
6.1 LIMITATIONS AND FUTURE WORK
While we focused our experiments on MoCo v2, similar results may be observed for other CID frameworks. However, we leave this to future work along with a study of other downstream tasks. is also possible that the lessons learned here may be useful for non-CID based contrastive approaches such as SWAV (Caron et al. 2020) and PCL (Li et al. 2020).
One of our most surprising findings was that there exist negatives that are anti-correlated with the query and also more semantically similar to than average. This seems undesirable for down- stream task of linear classification. Why would the network learn to anti-align two closely related concepts? Understanding the role of such negatives and discovering whether this behavior can be exploited corrected could be an important direction for future work.
Another avenue for future investigation involves exploring the use of curricula for negative difficulty. For example, larger quantity of easy negatives may be useful during the early stages of training while harder negatives are more useful later. While developing a negative curriculum is beyond the scope of this work, currieula have shown utility in many other contexts (Bengio et al. 2009).
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning, 2019.
Devansh Arpit, Stanistaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, al. A closer look at memorization in deep networks. arXiv preprint arXiv: 15534440 2017.
Yuki-Markus Asano, Christian Rupprecht, and Andrea Vedaldi.
Self-labelling via simultancous clustering and representation learning. In International Conference on Learning Representations, 2020.
net. foret//orurffii www.:eddddiee-ee jyBFFr
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference Machine Learning. ICML '09. pp. 41 41-48, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585161. doi: 15314459 URL https:://ci.orrg///. 1145/
1553374. 1553380
Vighnesh Birodkar, Hossein Mobahi, and Samy Bengio. Semantic redundancies in image- classification datasets: The 10% you don't need. arXiv preprint arXiv:190..11400 2019.
Maxime Bucher, Stéphane Herbin, and Frédéric Jurie. Hard negative mining for metric learn- ing based zero-shot classification. In European Conference on Computer Vision, pp. 524-531. Springer, 2016.
Olivier Canévet and François Fleuret. Efficient sample mining for object detection. In Asian Con- ference on Machine Learning, pp. 48-63. PMLR, 2015.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features, 2018.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments, 2020.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self- supervised models are strong cemi-supervised learners. Neural Information Processing Systems (NeurIPS), 2020b.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning, 2020c.
Ching-Yar Chuang. Joshua Robinson, Lin Yen-Chen, Antonio Torralba, and Stefanie Jegelka. De- biased contrastive learning, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scall scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Yifan Fu, Xingquan Zhu, and Bin Li. A survey on instance selection for active learning. Knowledge and information systems, 35(2):249-283) 2013.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations, 2018, URL
https:://ppeneet
net forumm forrumidd=S1v4222
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Ghesh- laghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent: A approach to self-supervised learning, 2020.

---

Under review as a conference paper at ICLR 2021
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. volume 9 of Proceedings of Machine Learning Research, pp- 297-304, Chia Laguma Resort, Sardinia. Italy, 13-15 May 2010. JMLR Workshop and Conference Proceedings. URL httt:://prroeeeiiggat ml r prwssrrssss.ee ht9g/ggttmannnnn Da html
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. unsupervised visual representation learning, 2019.
Momentum contrast for
Mahmut Kaya and Hasan Şakir Bilge. Deep metric learning: A survey. Symmerry, 11(9))1066, 2019.
Junnan Li, Pan Zhou, Caiming Xiong, Richard Socher, and Steven C. H. Hoi. Prototypical con-
trastive learning of unsupervised representations, 2020.
Karttikeya Mangalam and Vinay Uday Prabhu. Do deep neural networks learn shallow learnable examples first? ICML Workshop on Deep Phenomena, 2019.
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles, 2016.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. 815-823, 2015.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 761-769, 2016.
Kah-Kay Sung. Learning and example selection for object and pattern detection. 1996.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding, 2019.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning. 2020.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv:1812.055153 2018.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding, 2018.
Kailas Vodrahalli, Ke Li, and Jitendra Malik. Are all training examples created equal? empirical study, arXiv preprint 1rXiv:1811.12555 2018.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere, 2020.
Kilian Q Weinberger and Lawrence Saul. Distance metric learning for large margin nearest neigh- bor classification. Journal of Machine Learning Research, 10(2), 2009.
Chao-Yuan Wu, R Manmatha, Alexander J Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2840-2848, 2017.
Zhirong Wu, Yuanjun Xiong, Stella Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance-level discrimination, 2018
10

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 ADDITIONAL NECESSITY/SSFFFIIENCYY RESULTS
Train on only
85-90%
90-95%
95-100%
Top-1 accuracy (%)
19.47 + 12.83
51.89 + 1.00
66.69 + 0.16
Top-5 accuracy (%)
36.78
17.93
75.44
0.74
87.35
0.09
Train on only
85-100%
90-100%
95-100%
Top-1 accuracy (%)
67.22 = 0.21
17.15:0.11
67.32 + 0.88
Top-5 accuracy (%)
87.67 = 0.09
87.60 + 0.02
87.52 = 0.63
Table Al: Extended sufficiency results, 3 seeds each.
Train on all except
85-90%
90-95%
95-100%
Top-1 I accuracy (%)
67.56 + 0.12
67.53
0.20
62.1 = 0.24
Top-5 accuracy (%)
87.98 = 0.12
87.94 + 0.12
84.0 0.15
Train on all except
85-100%
90-100%
95-100 %
Top-1 accuracy (%)
47.91 = 0.79
56.96 + 0.36
61.95 + 0.16 83.87 = 0.28
Top-5 accuracy (%)
72.13 = 0.83
80.14 + 0.20
Table A2: Extended necessity results, 3 seeds each.
A.2 SIMCLR RESULTS
abridged set of experiments were run on SimCLR Chen et al. (2020a), with one seed each. SimCLR was reimplemented in pytorch and tested with modifications analogous to experiments elsewhere this paper on MoCo v2, where only a portion negatives, based on their hardness, run for 200 epochs with batch size 4096
were used for pre-training. Pre-training 50. For training on the hardest 5% of negatives (95-100% in the table), the first pre- pre-training epoch was trained on all negatives, and all further pre-training epochs were trained on the hardest 5%; pre-training on just the hardest 5% of negatives for all epochs did not converge.
Resnet-
Train on only
85-90%
90-95%
95-100 %
Top-1 accuracy (%)
55.60
62.70
66.34
Top-5 accuracy (%)
80.46
85.30
87.43
Train on only
0-90%
0-95%
0- 100 %
Top-1 accuracy (%)
52,43
63.66
66.99
Top-5 accuracy (%)
78.46
86.06
87.73
Table A3: SimCLR results, seed each.
For MoCo v2, the hardest 5% of negatives had been found to be both necessary and sufficient for downstream linear classification accuracy (Figure 2 We find analogous results for SimCLR: the accuracy for training just the top 5% of negatives by difficulty (66.34%) is very close to the accuracy for training on negatives (66.99%) while there is a drop of several percentage points when training on the bottom 95% of negatives by difficulty (63.66%). This suggests the most difficult 5% of negatives are both necessary and sufficient for SimCLR, in addition to MoCo v2.
11

---

Under review as a conference paper at ICLR 2021
A.3 MOST CORRELATED AND MOST ANTI-CORRELATED CLASSES
Mean dot product
Negative Class
Positive Class
-0.591357
Ibizan hound, Ibizan Podenco Italian greyhound
keeshond
-0.572822
Kerry blue terrier
-0.562565
macaw
ruddy turnstone
-0.494559
Staffordshire bullterrier
affenpinscher
-0.487417
box turtle, box tortoise briard
nematode
-0.476078
refrigerator
-0.471706
Border collie
Mexican hairless chow, chow chow
-0.467 100
dalmatian
-0.460264
sports car Staffordshire bullterrier
steam locomotive
-0.459015
Tibetan terrier
Table A4: Most anti-correlated classes. Mean dot product was computed pairwise across each pair
of classes.
Mean dot product
Negative Class monarch
Positive Class
0.923779
daisy
0.901869
ground beetle rifle entertainment center
dung beetle
0.856066
rubber eraser
0.823796
home theater police van monarch, swimming trunks wing organ, pipe organ ski
0.798866
minibus
0.795254
bee
0.794521
maillot
0.789350
airliner
0.789099
altar
0.786902
dogsled
Table A5: Most correlated classes. Mean dot product was computed pairwise across each pair of
classes.
Mean dot product
Negative Class
Positive Class
-1.112930e-07 -2.239249e-07
hog
totem pole
canoe
tennis ball
6.617499e-07
Great Pyrenees
knot
6.956980e-07
magpie
Cardigan
-7. 07.122289-007
china cabinet
running shoe balance beam
-7.863385e-07
spiny lobster
8.588731e-07
screwdriver
sunglasses
-8. -8.760835e-07
limpkin
packet
8.906354e-07
impala
coho
-9.792857-007
boathouse
television
Table A6: Most orthogonal classes. Mean dot product was computed pairwise across each pair of
classes.
12


Reviews:
[{"review_id": "whha4woKnRo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors carried out a series of experiments to analyze the impact of negative samples in contrastive learning (instance discrimination - CID). In particular, they try to identify which difficulty range is important for representation learning. Of the many recent self-supervised learning approaches, they chose MOCO V2 as the testbed. They trained the MOCO model from an ImageNet pre-trained one. Various settings, which correspond to various ways of filtering our hard or easy negatives, were used. Hardness of samples are measured based on embedding distance to the query. I.e. ones with large distance are easy. Their main findings are, for negative samples, 1) Using the 5% hardest is enough for downstream tasks, 2) the easiest 95% of them were unnecessary and insufficient, 3) The hardest 0.1% is harmful and  4) hard negatives were more semantically similar to the query. \nIn general, in my opinion, this is a paper in which the authors tried to answers many interesting practical questions. The author provided experiments and convincing evidences for a number of insights. My main reservations with this paper are: \n1) most of the points are not new and are elaborations of what were pointed out before elsewhere, for example, in semi-hard mining for distance metric learning.\n2) the empirical results are only within the context of MOCO2 and for a linear classification task. It is not clear how such numbers as 0.1%, 5% or 95% would change when adopting other frameworks such as BYOL or SwAV… The reported gains seems a little bit sensitive to the temperature parameters of MOCO.\n3) The sample hardness is measured based on embedding distance, which would be evolved during the training process itself.  It is not clear how accurate it is especially in the early stage of training.\n\nMy suggestion for improvements is that either to empirically show that their findings (numbers) are consistent across a number of frameworks and downstream tasks, or to provide some theoretical justification for their findings if only MOCO v2 is used.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rhWkihm_zDE", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper mainly studied how the negative samples can affect the model performance in supervised learning CIO works. Through the experiments, this work has a few interesting findings, including the majority of negative samples are not important for the model learning, only a small subset of hard samples determine the model importance. These hard examples are also closely related with positive samples (more semantically similar).  We can see from experiments that it's very important  to fairly treat negative samples in supervised learning tasks. However, there is no frameworks proposed to help improve the learning representation or speed up the training task.  In general, the readers are more interested in the solutions after realizing the importance of negative samples treatment during the experiments.  It would be necessary to include the corresponding solutions by automatically setup these negatives samples in CID related task.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PqDj8vxIQCj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe findings of this work are that for contrastive learning, most of the negatives deemed easily separable are unnecessary, the most important negatives are somewhere in the top 5% closest to the positive sample, and that some of the exceedingly hard examples are detrimental.\n\n-In general, I felt the main findings of this work to be roughly in line with what we already know about contrastive learning. We can easily look at this work's findings with respect to the soft SVM margin, in that only the examples close to the decision boundary should matter (max margin), but some difficult examples  (the aforementioned exceedingly difficult ones) make the data inseparable, so we allow some violation (slack terms).  While I'm not suggesting that slapping a soft SVM here would solve the problem, there is a large body of SVM-based detection/classification literature that precedes the findings of this work.\n\n-Validity of WordNet as a measure of semantic similarity: Section 4 uses WordNet distances to estimate the semantic similarities between classes by finding their shared subtree root. The deeper the subtree, the more semantically similar. While I do not dispute the claim of the hardest negatives being from semantically similar classes. Different parts of the WordNet synset tree have semantic hierarchies of varying levels of coarseness. A 2 hop distance in one subtree could easily be more of a semantic jump than a 3 hop distance in another. \n\n-The exist prior works dealing with the neglected semantic hierarchies in ImageNet by setting up hierarchical classifiers. An example is [1].\n\n-I would further argue that there's some nuance in the correlation between semantic similarity and example hardness, in that it really depends on your choice of feature representation. Visual features will naturally correlate with closer semantic levels in visually-defined categories. However, this will not necessarily hold for semantic categories defined by function, in that two visually distinct items may fall under close semantic labels. \n\n-The related works section claims object detection works have not \"explicitly involved negative examples as in CID.\" I have to imagine this statement is poorly phrased, as [2] (also cited in this paragraph) very explicitly mines for  face-like non-face patterns. There is a very long list of hard-negative mining works in object detection.\n\nOverall, I value the empirical impact of this work, in that the rather detailed analysis may lead to improvements to future versions of the contrastive feature learning task. However, I do not find the findings of this work to be sufficiently novel for this conference, and therefore cannot recommend this work for acceptance in its current state.\n\n\n\n[1] Yan et al. HD-CNN: Hierarchical Deep Convolutional Neural Networksfor Large Scale Visual Recognition. ICCV 2015\n\n[2] Sung and Poggio. Example-Based Learning for View-Based Human Face Detection. TPAMI 1998", "extra_scores": {}, "extra_text": {}}, {"review_id": "H-A8mgdDXP2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper argues that in contrastive self-supervised learning, different negative instances have different importance. This importance is relevant to the ``difficulty\" of negative instances. On ImageNet and MoCo2, the authors show that using the most difficult 5% negative instances can achieve similar performance compared with using all negative instances. However, the most difficult 0.1% of negative instances yield bad performance.\n\nI recommend to reject this paper due to the following major concerns: 1) study is performed on a single dataset, which is not convincing; 2) study is performed on a single method, which casts doubts on whether the conclusions hold for other methods; 3) this study does not seem to have practical value.\n\nWhile this study is interesting, it lacks rigor, in the following aspects.\n1. The study is only performed on a single contrastive self-supervised learning method: MoCo2. It is unclear whether the conclusions hold for other contrastive SSL methods, such as BYOL and many others.\n2. The study is conducted on a single dataset: ImageNet. It is unclear whether the conclusions hold for other datasets.\n3. Another concern is this study does not seem to have practical value. In each iteration during training, finding the hardest examples for a query needs to calculate the inner-product between this query and all other training examples, which is computationally very heavy. \n4. In the author's measure of difficulty, the difficulty is a function of network weights. In early stage of the training, the network weights are random, which implies that the calculated difficulty may be meaningless. Can the authors comment on this?\n\nHowever, the paper does have a few strong points.\n1. The paper is well-written. The organization is clear and the paper is easy to follow.\n2. The studied problem is interesting and novel. \n\n\nOther comments.\n1. Figure 5a is difficult to interpret. The author may consider to reorganize it.\n2. In Figure 3, only three temperature values were considered, which may not be very convincing.\n\n-----------------------------------------------------------------------------------------------------------------------------------\nUpdate: I read the authors' rebuttal. The authors didn't address my concern \"The study is conducted on a single dataset: ImageNet. It is unclear whether the conclusions hold for other datasets.\"  sufficiently. I would like to keep my original rating. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper empirically studies the impact of different types of negatives used in recent contrastive self-supervised learning methods. Results were initially shown on Mocov2, though after rebuttal simCLR was also added, and several interesting findings were found including that only hardest 5% of the negatives are necessary and sufficient. While the reviewers saw the benefit of rigorously studying this aspect of recent advances in self-supervised learning, a number of issues were raised including: 1) The limited scope of the conclusions, given that only two (after rebuttal) algorithms were used on one datasets, 2) Limited connections drawn to existing works on hard negative mining (which is very common across machine learning including metric learning and object detection), and 3) Limited discussion of some of the methodological issues such as use of measures that are intrinsically tied to the model's weights (hence being less reliable early in the training) and WordNet as a measure for semantic similarity. Though the authors provided lengthy rebuttals, the reviewers still felt some of these issues were not addressed. As a result, I recommend rejection in this cycle, and that the authors bolster some of these aspects for a submission to future venues. 

I would like to emphasize that this type of work, which provides rigorous empirical investigation of various phenomena in machine learning, is indeed important and worth doing. Hence, the lack of a new method (e.g. to address the selection of negatives) was not the basis of the decision. While the paper clearly does a thorough job at investigating these issues for a limited scope (e.g. in terms of datasets), a larger contribution is expected for empirical papers such that 1) we can ensure the generality of the conclusions (across methods and datasets), 2) we have a conceptual framework for understanding the empirical results especially with respect to what is already known in adjacent areas (e.g. metric learning and object detection), and 3) we understand some of the methodological choices that were made and why they are sufficiently justified. 
Decision: Reject