Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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:
* 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?
* 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?
* 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.

For 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.

Post response: my concerns have been somewhat addressed, so I have increased my score.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

However, the reviewer still has following three concerns.
First, 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.

Second, 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.

Third, 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.

### Post-rebuttal and discussions

Thanks to authors' responses. Actually, their response has answered most of my concerns.

Besides my previous concerns, I also agree with other reviewers that the proposed theoretical framework is limited to no-transfer tasks in self-supervised learning. 
Although 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.
I suggest authors to discuss above limitations in the paper, since they use a rather ambitious title.

However, 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.

I 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.

limitations_and_societal_impact: Please see my main review above.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: **Strengths**:
- 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.
- 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.
 - The observations from Theorem 8 and the analysis on contributions from the sub-class loss is interesting.


**Weaknesses** (and questions):

A) 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.

B) 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?_

C) 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). 

Some more notes/questions:
- 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. 
- 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. 

**Rating**

Although 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.

-----------
## Post-rebutal thoughts

The 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".

In their response, the authors claim that

> 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.

With 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.

Similarly, wrt the answer on the usage of a mean classifier:

> 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.

Again, 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.

Overall, 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.
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_title: null

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)