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