Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper analyzes contrastive learning by bounding the supervised loss with contrastive loss. The bounds are tighter than those proposed by previous works.
main_review: The paper address an important theoretical problem in contrastive learning. The paper is well-written and the contributions are stated clearly. I have a few questions and concerns.

1. Is CURL really unsupervised? The paper claims to analyze the “unsupervised” representation learning, however, the positive samples are drawn from class-conditioned distribution, which requires ground truth labels to estimate. I know this step is necessary to have some closed-form analyses, but this makes the study a bit deviated from the recent contrastive learning approaches. Does the observation still holds for general unsupervised contrastive learning, where positive samples are drawn via data augmentations? At least, in the experimental section, it would be great to see some results with standard framework such as SimCLR. Even though the results might not perfectly match the theory, some discussions are still valuable.


2. The class sampling assumption is stronger than Arora et al. [1]. In particular, the latent classes used in [1] is not equivalent to the output classes for supervised classification task. Can the current framework generalizes to this scenario?


3. Theorem 1 and 2 are nice. Maybe the authors can provide some proof sketch or at least discuss the key tool use to tighten the bounds? It seems that most of the approaches including Thm 1 applying Jensen Ineq at first, what makes the bound tighter? Giving a high level intuition of proof technique can help reader understand the theorems better.

4. Are the bounds also tighter in term of generalization error? With access to only finite samples, the bound could behave different from its expected value.

Overall, the theorems are solid and sound. However, I am concern about the applicability of the bounds. The assumption makes it hard to quantify the behavior of “actual” unsupervised contrastive learning algorithms. The insights from the analyses seem to not directly applicable to practical setting.



[1] Arora et al., A Theoretical Analysis of Contrastive Unsupervised Representation Learning, 2019
summary_of_the_review: The paper is well-written, but I am concern about the applicability of the bounds due to its assumptions. The authors claim to analyze an unsupervised algorithm, but the assumptions do require the access to full supervision.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the learning bounds of popular representation learning. Not only the improved tighter upper bound is provided, the lower bound is also studied. The paper is well written with thorough discussion and nice example for illustration. 
main_review: Strength:

* The new upper bound is tighter than the existing works, and provides a better insights of having the large size of negative example that people found useful in practice.  One thing I enjoy during reading is Section 3. After having lower bound, the discussion of feasible region is interesting, and also provide some aspects of having "small K", which is also quite aligned with some empirical findings. 

* The numerical figures in Sec 4 is a great illustration to understand and compare different bounds. 

Suggestions:

* It would be great to extend the mean classifier to a more general linear classifier setting, which is more commonly used. 

* Currently, the success of many contrastive learning heavily relying on data augmentations. It would be great the augmentation can be formulated into the analysis (e.g. as some stochastic process .. etc)
summary_of_the_review: The paper is well written with many great figures to explain ideas. The improved upper bound and lower bound are studied, which I think it's good to the community.  However, I don't closely follow the theory development of representation learning, which I can only follow the derivations in the paper, and judge from a practitioner perspective.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work establishes a downstream classification loss bound for contrastive learning which shows that larger negative samples improve the classification performance. Existing works cannot explain the experimental fact that larger negative samples improve the classification performance. 
main_review: Strengths:
(1)	Its theoretical results could explain larger negative samples improve the classification performance in contrastive learning by establishing lower and upper bound of downstream classification loss.
(2)	The authors also do some experiments to investigate their theories. 

Weaknesses: 
(1)	My biggest concern is that this work does not provide any useful and new insights. It can only explains a well-known experimental fact that larger negative samples improve the classification performance, and does not provide any insights to further improve contrastive learning which is actually the key for theoretical work in my viewpoint. for a theoretical work, providing a more sharp bound is not the goal but providing new insights is. For example, Arora first establish the relation between pretext contrastive loss and the downstream classification loss and shows why contrastive loss can work well for downstream tasks.  However, in this work, I did not find such kinds of insights. 

(2)	the bound in Nozawa & Sato actually also partially support that larger negative samples improve the classification performance, which can be illustrated by Fig. 3 (a). The authors may claim for possible best R*cont, the bound in Nozawa & Sato cannot explain the experimental fact. Actually, R*cont  is obtained under a simplified case where data augmentation is not considered, and the classification head in f is not discarded when training on downstream tasks, etc. So R*cont may not be achievable for one real contrastive learning or apart from the real optimal contrastive loss since the simplified case are different from the real contrastive learning. 

(3)	The authors should discuss the novelty of the proof techniques compared with existing one, such as Arora et al, Nozawa & Sato. It seems that the authors use the property that the function f is bounded to give a tight bound. So it is better to discuss your technique differences. 

summary_of_the_review: Overall, although this work provides new tighter bound for contrastive learning, it does not provide new insights and new proof technique/frameworks.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposes a new theoretical upper-bound for contrastive unsupervised learning loss and its downstream supervised loss. Compared to previously published upper-bounds, the newly proposed one is lower and decreases when the number of negative samples increases, which is expected according to empirical observations, but not shown in previous upper-bounds. The authors use experiments on multiple datasets to verify the theoretic results and the gaps between this and earlier upper-bounds.
main_review: Strengths:
1.	The proposed upper-bound on both contrastive loss and downstream supervised loss is lower compared to other upper-bounds, which make it sharper.
2.	The upper-bound on supervised loss decreases when K (the number of negative examples) increases. This does not happen for other upper-bounds and is important for understanding why the performance of models gets better with more negative samples.
3.	The empirical experiments on the synthetic datasets, CIFAR-10, and CIFAR-100 further show the clear advantage of this upperbound compared to the others.

Weaknesses:
1.	This upper-bound does not include the interaction between K and C (the number of classes). This makes it monotonically decrease when K increases, which is contradict to the empirical results on CIFAR-10 or CIFAR-100 (though the loss values do not change that much, the performance indeed decreases instead of increases as predicted). This interaction is in fact shown in earlier upper-bound. I wonder how this interaction can also be introduced into the current upperbound, especially giving the intuition that with more negative samples, there will also be more examples in the same class treated as positive examples.
2.	The proposed upperbound on downstream supervised loss is based on the intermediate upperbound on the mean supervised loss, which essentially uses the low-dimensional embeddings as the final representations to do the classification. Although this would serve as a right intermediate upperbound when the embedding is only one linear layer away from the typical layer the category readout is extracted, this would not be true when the embedding is several layers away from the typical layer, which is actually the case in most SOTA algorithms now. Can the authors explain how this would influence the results in this work?

summary_of_the_review: This work proposes a sharp loss upperbound for contrastive learning and its downstream supervised learning. It is validated by the empirical experiments conducted by the authors on different datasets, but lacks the interaction between the number of classes and the number of negative samples. Because it’s indeed lower than the earlier upperbound, I think it would be useful for the community and would recommend for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: === After Rebuttal ===

The author(s) have made many clarifications and improvements to the paper per reviewers' requests. I am happy to bump up my score by 1 to reflect the changes & promises made. 

=================

This paper provides some new theoretical insights on how contrastive representation help to improve downstream classification performance. In particular, it fixes the mismatch between prior theoretical predictions and empirical observations, that a larger negative sample size leads to better downstream performance. 
main_review: This paper has made some interesting points, and the experiment results strongly support its theories. However, I do have a few outstanding concerns that prevent me from granting a positive recommendation. I am happy to discuss these during the author-reviewer interaction round, and I am more than willing to change my score if the author(s) have made proper changes or managed to convince me. Details of my review comments are given below. 

**Strength**
* Strong theoretical analyses, clear writing, and nice illustrative figures. Overall the technical contents of the paper are easy to follow.
* Empirical results well aligned with the theories
* Very update-to-date coverage of the related literature, especially on the theoretical analyses of contrastive representation learning

**Weakness**
* My most concerning point is that: is this paper supervised representation learning in disguise? Because the contrastive loss used here clearly has leveraged class information (last equation on pp.2). This is clearly the setup in supervised contrastive learning [1]. In that case, it is not surprising that contrastive loss bounds the prediction loss: because they are essentially the same thing. In general, I do not think unsupervised learning can directly benefit supervised learning without some strong assumptions (see for example [2]).

* Apart from the above, another point I do not agree on is why larger K helps. The genuine unsupervised contrastive representation learning implicitly optimizes the MI across augmented views, and larger K drastically reduces estimator variance. The author(s) claimed that "the quantitative relationship between the negative sample size K and the MI estimation error has yet to be clearly known", which is not true, see theoretical analyses in [3,4]. 

* Following up on the last point, the author(s)' statement that "Note that Tian et al. (2020) and Tschannen et al. (2020) experimentally showed that maximizing MI does not necessarily lead to good representation." is also imprecise. To be more accurate, these works simply used tighter MI bounds for representation optimization, there is no guarantee that they indeed learned representations with higher MI. This view is supported by the empirical evidence from [5], where ground-truth representation MI strongly correlates with downstream classification, and tight MI bounds do not necessarily yield high MI representation. 

* Unlike the author(s) have claimed, the gap between learning upper and lower bounds has nothing to do with the estimation variance of the mean supervised loss (pp. 4).

* Figure 4 is very compelling, my suggestion is to present it earlier in the text, which may better serve to prove the author(s) points. 

* Per author(s)' theory, variance reduction is the key to performance gains. However, none of the experimental results shows the variance.

* What is the intuitive explanation for notation Col?

* Please label the equations with numbers.


**References**
* [1] P Khosla, et al. Supervised contrastive learning. NeurIPS 2020
* [2] J Robinson. Strength from weakness: Fast learning using weak supervision. ICML 2020
* [3] S Gao, et al. Efficient Estimation of Mutual Information for Strongly Dependent Variables. AISTATS 2015
* [4] D McAllester, et al. Formal Limitations on the Measurement of Mutual Information. AISTATS 2020
* [5] J Chen, et al. Simpler, Faster, Stronger: Breaking The log-K Curse On Contrastive Learners With FlatNCE. arXiv 2107.01152



summary_of_the_review: I am recommending weak rej at this stage. My main arguments are that (i) the author(s) actually analyzed supervised contrastive learning, not unsupervised contrastive learning; (2) need evidence to show the gains from large K are really from the variance reduction of sandwich bound, not from the variance reduction + bound tightening from the MI estimation perspective.
review_title: null

Meta-review: The paper presents an analysis of the benefit of unsupervised contrastive learning for downstream classification tasks using the cross-entropy loss. Building on prior work, the authors show that the contrastive loss can be bounded in terms of the cross=entropy term and an “intercept” term which depends logarithmically on the number of negative samples per positive sample (for contrastive learning) rather than polynomially as in the prior work. 

There are several differences between the setting here and that of the prior work by Arora et al. (2019). First, the work here focuses only on cross-entropy loss and leverages the similarity of the loss structure between the contrastive loss and the cross-entropy loss. Second, the assumptions here are different, e.g., boundedness of the representation. Finally, the assumption that latent classes are the same as the label classes (which is not the case in the prior work) is significantly restrictive. 

The writing is poor and the presentation is not clear. Despite the title and various references to learning bounds in the abstract and the main text, there are no learning bounds in the paper. The main result is to bound the contrastive loss in terms of the cross-entropy loss under the assumption that the latent classes and the label classes coincide. Authors state that getting generalization bounds is routine and, therefore, they chose not to give them — I do not see how generalization bounds follow in a straightforward manner here, and even if they do, it is important to write them for completeness. 

The main contribution here is that the bounds depend logarithmically in K — the number of negative samples per positive sample — compared to sqrt{K} in the previous work. The previous bound however holds for Lipschitz losses as well, for e.g., hinge loss. So the question remains whether this improvement is only for the cross-entropy loss. Regardless, K is typically small in practical applications. Even the experiments in the paper (Figure 7) suggest that the performance degrades for larger K even on simple tasks. So, the improvement is really somewhat insignificant. 
 
The reviewers were generally positive and appreciated the paper. However, in the light of comments above (of which I am quite certain), unfortunately, I am unable to accept the paper at this point. I believe the comments above (and from the other reviewers) will help improve the overall quality of the paper. I encourage the authors to incorporate the feedback and work towards a stronger submission.
Decision: Reject