Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the generative power of contrastive learning from a theoretical perspective. To enable the analysis, this paper considers the linear model with random masking augmentation. Training data are assumed to be generated by the spiked covariance model. The main result is that contrastive learning can recovery the core features since the random masking augmentation can mitigate the influence of random noise on the diagonal entries in the covariance matrix, while the autoencoder is unable to recover the core features due to the large noise. Then this paper shows that downstream excess risk can be upper bounded by contrastive learning but cannot be less than a universal constant for an autoencoder. Beyond the unsupervised setting, this paper also studies the role of labeled data in supervised contrastive learning and gives the upper bound of sine distance between the supervised contrastive learned model and the true model.

main_review: The main result of this paper sounds interesting, despite the analysis conducted on linear models.
The result shows that in some cases (large noise regime), the autoencoder cannot recover the core features and thus performs badly on downstream tasks, but the contrastive learned model has the ability to recover the core features due to the random augmentation.
Therefore, we can see the strong power of contrastive learning, at least in the large noise regime.
The analysis of supervised contrastive learning is also novel and convincing.

I have some detailed questions about the comparison between autoencoder and contrastive learning (Thm 3.2 and 3.3).
- Does $c'$ in Thm 3.4 depend on $r$ or $r_c$? If so, can we say that $c'$ is worse than the bias term (first term) in Thm 3.3? If not, why do we need to assume that $r\le r_c$ for all $r$? Sorry for that the proofs in the appendix are not clear for me to read.
- Do we use data augmentations for autoencoder training in the analysis? If so, the comparison between autoencoder and contrastive learning is fair. If not, contrastive learning seems to involve more human knowledge for the training.

Moreover, I wonder how much insight of this paper can be extended to non-linear models and other augmentations? Do you have any empirical studies to verify how many theoretical observations still hold for those cases?

Minor comment: The appendix is not well organized. It is hard to see a clear one-to-one match between theorems in the main text and the proofs in the appendix.
summary_of_the_review: Overall, I think this paper is good and interesting. My main concern is 1) whether the comparison between autoencoder and contrastive learning is fair, and 2) how much insight can be extended to the more realistic scenarios.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper performs a theoretical study of various empirical phenomena regarding contrastive learning in a simplified setting, with a linear representation function, spiked covariance data model and linearized version of contrastive loss. In such a setting, the following results are shown theoretically (a) contrastive learning with a particular data augmentation can learn much better feature than an autoencoder by virtue of learning the underlying low rank signal as features, (b) supervised contrastive learning can do better than contrastive learning by getting rid some bias that data augmentation introduces, (c) for transfer learning, a combination of unlabeled contrastive loss and supervised learning can do better than either of them individually. Simulation experiments are used to verify many of these findings.
main_review: **Strengths**

The theoretical results explaining various interesting phenomena about contrastive learning are novel to the best of my knowledge. Contrastive learning and its variants have enjoyed a lot of success recently, and theoretical understanding of these methods is appreciated. The simplicity of the data model used to understand these phenomena is good in some ways; more on its weaknesses later. The paper is well written and easy to follow for most part. The notations, assumptions, theorem statements and discussions that ensued are clearly presented. Simulations verify many of the theoretical findings, e.g. existence of optimal $\alpha$ (relative strength of supervised learning and contrastive learning) when not enough source tasks available in transfer learning. The results seem mostly believable and a quick read of some parts of the Appendix did not raise any red flags; in fact the Appendix presentation also seemed clean.


**Weaknesses**

While the simplicity of the setting is not a huge weakness, it certainly raises the question of relevance of the analysis to practice. Evidence for a lot of empirical phenomena studied in this paper is provided by citing Khosla et al. and Islam et al. at various points in the paper. It would help to make these connections more explicit and present findings from prior work more clearly. One way to justify the setting would be to experimentally demonstrate relevance of some of the theoretical components on some real benchmark datasets. This would also increase the impact and visibility of the theoretical results.

It would also help to provide some more intuition for some of the results, for e.g. what is the reason for the extra bias term in contrastive learning compared to supervised contrastive learning? It seems like this arises from not learning the diagonal entries of $U^* {U^*}^{\top}$ due to the augmentation, but it's not clear why this is not a big issue for supervised learning. Similarly it will help to include some more intuition for why transfer learning fails and how self-supervised contrastive learning can save from that.




*Other comments/questions*

- Abstract should clearly specify that theoretical results are shown for simplified linear representation setting for a particular data model. The current phrasing makes the results seem very general

- It would be nice to present Theorem 3.1 and 3.2 for the same (or comparable) values of $\rho$ (signal to noise ratio), or perhaps make the dependency more explicit. Although both work for $\rho = \Theta(1)$, the dependence is hidden.

- The choice of augmentation (random coordinate subsets) is such that it aligns with independence structure of noise in data ($\Sigma$ being diagonal). This seems important for the superiority of contrastive learning over autoencoders. Could this have any connection to its superiority in practice?

- (Minor) The augmentation generation process from Definition 2.1 is different from what is done in practice, where the two views are typically independent of each other given an input $x$. In this paper the two views are dependent since they use complementary subset of coordinates. Perhaps the analysis could be extended to this independence case, e.g. two views can correspond to 2 random subsets of coordinates.

- Is there any specific reason for choosing HSIC apart from ease of analysis?
summary_of_the_review: Overall the theoretical results are quite interesting, for a very relevant problem of contrastive learning. The main negative point is about the relevance of the results to more practical settings.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents theoretical results to explain the effectiveness of contrastive learning (CL). For the self-supervised model, the authors prove new sin-distance-based error bounds for autoencoder (AE) and CL. For the fully-supervised model, the generalization error bound is derived. Numerical experiments validate the theoretical finds.
main_review: Overall, I appreciate the plentiful theoretical analysis in this paper. However, some concerns are preventing its acceptance.

1). Theorem 3.1 and Theorem 3.2 provide the sin-distance error bounds, which measure the divergence between the optimal eigenvector U* and the solution U.  And it is good to see that the upper bound of CL is lower than the lower bound of AE (with the increase of d and n). However, I do not think such an inequality relation can really interpret the good generalization performance of CL. Firstly, this error bound is just based on training data which cannot be generalized to the unseen test data. Secondly, the recovered variable is merely U, but the optimization variable W contains U, S, and V.

2). The generalization error bound in Theorem 3.3 is similar to existing work [R1, R2]. The authors can further elaborate on the difference or merit of their error bound compared with those existing works.

3). For the supervised CL case (Theorem 4.2), I have the same concern as my first point. The error bound merely focuses on the training data, which cannot be generalized to unseen test data. Thus it does not really explain the effectiveness of the existing supervised CL model. Actually, we know that the supervised CL can also be regarded as a (supervised) similarity metric learning problem that has been widely studied in both theoretical and experimental aspects.

Given the above my concerns, I would like to vote for a weak reject. I will increase my score if I misunderstand something.

[R1]. Saunshi N, Plevrakis O, Arora S, et al. A theoretical analysis of contrastive unsupervised representation learning, ICML'19.
[R2]. Chen S, Niu G, Gong C, et al. Large-Margin Contrastive Learning with Distance Polarization Regularizer, ICML'21.
summary_of_the_review: See the above.
review_title: null

Meta-review: While the reviewers appreciated the theoretical analysis performed in this work, some concerns were raised during discussion, such as how relevant the obtained results are wrt current contrastive learning practices, and whether the comparison against a simple auto-encoder (basically PCA) is fair or insightful. The authors' response did not satisfactorily address these concerns. Overall, the current work appears to be preliminary, and important questions were left out: (a) how realistic the assumptions are (linear, spike covariance, Bernoulli random augmentation)? (b) performing better than PCA in a specifically designed setting may not be as impressive as it appears; what can we say about the optimality of CL against any algorithm? (c). validation on existing benchmark and CL algorithms would be welcome. The authors are encouraged to revise the current draft by incorporating the reviewers' comments and submit again. In its current form, we believe this work is not ready yet.
Decision: Reject