Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies contrastive learning from a theoretical perspective. Previous works on this topic showed the benefits of contrastive learning, assuming the pretraining loss is minimized over all sets of functions with no specific form. In this work, it is assumed that the pretraining loss is minimized by certain classes of functions, such as linear predictors and neural networks. Under different assumptions on the data and architecture, it is shown that contrastive learning can learn useful representations for downstream tasks. The results show that this can be achieved with representations of lower dimensionality compared to previous results.
strength_and_weaknesses: Strengths
1. Solid theoretical results.

2. Novel results for self-supervised learning with contrastive loss.

Weaknesses

The main weakness is that the presentation of the results and mathematical details are not very clear.

Here are the details:

1. The relevance of Theorem 1 in this paper is not clear. It is presented as the main result but is not used in the paper. Theorem 2 is used instead. It is claimed that Theorem 2 generalizes Theorem 1. However, because of the various assumptions, it is not shown if this generalization is strict, or there are cases where Theorem 1 guarantees better results. Generally, the connection between the assumptions in Section 3 and Section 4 are not clear. 
2. The details of the proof of Theorem 2 are not clear:
(a) Where is Eq. (57) used in the proof? Also, $\tilde{W}$ appears in the proof (Eq. 57), but later disappears. Where does it appear in the calculations?
(b) How is Eq. (59) derived from Lemma 1 and Eq. (55)? The details are not shown.
3. In Example 3, what does “contains lots of disconnected subsets” mean formally?
4. In Theorem 1, does the result hold for k>m? In Theorem 3, can we set k > s?
5. The experiments are not very convincing. The optimization method that first optimizes the contrastive loss and then whitens the result may not minimize Eq. (18).
6. Are the results in Section 5 specific to the regularization used? For example, if we slightly change the distribution in Example 1 to a general product distribution, do the results still hold?
7. The orange points in Figure 1 are missing.

clarity,_quality,_novelty_and_reproducibility: Quality. 

Strong theoretical results, but some of the mathematical details are not clear. Experiments are not very convincing.

Clarity.

The paper is mostly well-written, but as showed above, some of the details can be clarified.

Novelty.

The paper contains several novel theoretical results.
summary_of_the_review: This paper shows novel theoretical results on self-supervised learning with the contrastive loss. In several parts, the presentation of the mathematical results and writing are not clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Prior work by Saunshi et al. 2022 had highlighted the insufficiency of previous theoretical analyses that are function-class agnostic to completely explain the success of self-supervised learning. This paper provides theoretical guarantees for self-supervised learning that do incorporate the function class building on the framework of HaoChen et al 2021. 

In particular, the paper presents a notion of *minimal implementable clusters* for a function class $\mathcal{F}$, that is, the size of the smallest disjoint partition of the input space such that the positive pairs lie with high probability in the same cluster and the clusters within each partition are non-sparse under the geometry enforced by the underlying function class $\mathcal{F}$. At a high level, this notion intends to captures the ability of the function class $\mathcal{F}$ to break the underlying positive-pair graph (vertices = augmentations of images, edges = if two augmentations can be generated from the same image) into too many clusters. The main theorem then says that the embedding dimension needed to guarantee good downstream performance is dependent on the minimal implementable clusters which may be exponentially smaller than the total number of clusters independent of the the function class.
strength_and_weaknesses: **Strengths**:
- The main result in the paper improves the current theoretical understanding of self-supervised learning and formalizes the example presented in Saunshi et al. (2020).
- The eigenfunction perspective is a nice generalization and probably has connections directly to spectral clustering/kernel PCA.
- The authors do a good job of including several examples to instantiate the theorem.

**Weaknesses**:
- The main weakness of the paper is writing. The paper is written for a narrow set of the audience who is very familiar with the existing works of HaoChen et al. 2021, 2022 and Saunshi et al. 2022. Very little effort has been put to make the core ideas accessible to a broader audience. Furthermore, figure 1 is very hard to understand given that it has no “orange” points. Considering this is the main figure used to motivate the underlying study, this already makes it very hard to follow the paper.
- The experimental evaluation is not very convincing. Assumption 2 depends on all $f \in \mathcal{F}$ but the evaluation is based on a specific value of the learned $f$ from the contrastive solution (which encodes the inductive biases of the algorithm as well). It is hard to understand what these numbers mean and whether the trend is enough.
clarity,_quality,_novelty_and_reproducibility: The results are novel and reproducible from the proofs, however as discussed before, the paper requires a lot of work on the writing side to be accessible to the ICLR audience. Here are some particular suggestions:
- Fix Figure 1
- Explain HaoChen et al. 2021, particularly the positive-pair graph. Maybe add a figure.
- Further emphasize the role of dimensionality here, and the fact that the improvement is in terms of this
- Since the $m$-way partition is defined independent of $\mathcal{F}$, and tied to that using Assumption 1 & 2, it took me a bit of back and forth to understand. Would be great to abstract the definition separately from the assumptions, and then talk about the assumptions.
- Add more discussion regarding the assumptions, as to why they are necessary, especially Assumption 4, which seems redundant given that we use a linear map on top to predict anyway. Furthermore, the setting could be defined first (which includes assumption 1 & 5 which are only assumptions on the data generating process), and then the assumptions on the function class.
- Would be good to add a comparison to HaoChen et al. 2021, and whether you get their results assuming $\mathcal{F}$ is the class of all functions.
- More discussion on why the condition in the eigenfunction section compares to the assumption in the previous section, how the quantities relate
- Typos:
    - Wrong paper cited in the abstract
    - \cite → \citep in appropriate places
summary_of_the_review: Overall, I think the paper makes progress towards understanding the role of function class for contrastive learning and formalizing the observations in Saunshi et al. 2022. Given that the prior work did already propose a setting where the role of function class was highlighted, this paper’s primary contribution is a more refined theoretical treatment of this observation, and not the observation itself. This diminishes the contribution of the work slightly, however I still think it would be interesting to the ICLR audience. My major concern is writing and the experimental section, which is reflected in my comments above. Therefore, currently I think the paper is not ready for acceptance. I will be happy to increase my score if these are improved.

Post rebuttal: 5-> 6
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a theoretical analysis of contrastive learning in the setting where the hypothesis class has significantly smaller dimension than the data distribution (as measured by the number of clusters). They instantiate their framework on a few example settings and show that their results provide theoretical guarantees where previous approaches do not.
strength_and_weaknesses: Strengths:

- The paper is well-written and the authors provide intuition around each provided result, and motivate the problem well.
- The authors present the example from Saunshi et al (2021) and show how their results shed light on the actual behavior of contrastive learning in that setting.

Weaknesses:

- The experimental section is a bit confusing and I don't quite see the connection between the theory and the experimental results. In particular, the experiment shows that as the number of clusters gets higher, the loss of a contrastive classifier also gets higher. My issue with this experiment is that I do not see what the alternative is to the results shown in the table in page 9---clearly as r -> infinity the loss must increase, and for r = 1 the objective is trivial, so I'm not sure what I should take away from the loss increasing (the numbers themselves are not interpretable to me).
- A much more compelling experiment would be to show that the bounds proved in the previous sections are actually predictive of model behavior in some non-obvious way (e.g., by implicitly varying P_min and P_max, or by varying alpha and beta) and showing that Theorem 1 is predictive in this setting (at least in terms of trend)
clarity,_quality,_novelty_and_reproducibility: The work is clear and high-quality. I am not an expert in contrastive learning and cannot judge the novelty---I also skimmed the proofs for correctness but cannot attest to how theoretically interesting they are.
summary_of_the_review: This paper presents a theoretical analysis of inductive biases in contrastive learning. Their main result is that when the function class being learned over is restricted, one needs a representation size that is far smaller than the number of clusters in the data distribution. The paper is clearly written, the results seem correct, and also address issues raised by prior work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies inductive bias from the model class in contrastive learning. The paper proposes some mild and practical assumptions and studies the optimal solution of the spectral contrastive loss from the eigenfunction perspective. The paper argues that when the model has limited capacity, contrastive representations would recover certain special clustering structures (depending on model architecture) but ignore other clustering structures in the data distribution. Moreover, the paper also studies different model classes including linear functions, ReLU networks, Lipschitz continuous functions, and Convolutional neural networks. 
strength_and_weaknesses: Strength:
1. As far as I know, this is the first work to study inductive bias originating from the model class in contrastive learning. The paper is based on some reasonable assumptions and gets a non-trivial conclusion. In my opinion, Assumption 2 is the most critical one. The function class cannot be too powerful so that we can guarantee the generalization. The authors also introduce novel tools, eigenfunction methods, in analyzing contrastive learning. 
2. The paper has a clear motivation and a good structure. 

Weakness and Questions:
1.  I am not familiar with Eignfunction methods. I have some questions for Section 4. What is the relationship between $k$ orthogonal eigenfunctions and equations (9) and (10)? Are equations (9) and (10) additional assumptions here or can they be induced from $k$ orthogonal eigenfunctions? What is the connection between Assumption 6 and Assumption 2 and 3? I cannot get full insights into how is Therom 2 generalized from Theorem 1. 
2. One concern I have is that in practice the model has more than millions of parameters, e.g. vision transformer. Then, how to guarantee assumption 2 in a real empirical scenario. Note that Assumption 2 considers the whole function space. If assumption 2 is not guaranteed, how to explain the success in MoCo v3 [3]? 
3. There are some subtle weaknesses in the problem settings. The paper studies generalized spectral contrastive loss rather than the InfoNCE family loss. The authors also did not consider the sample complexity in the pre-training like [1,2]. 
4. The experiments part is weak.  It is acceptable considering it is a theoretical paper. The $b_r$ is not a clear metric for reader to understand the partition effect, e.g. for $r=500$, how bad is $b_r=0.315$. More explanation is needed here.

Typos:
1. In Figure 2, there are no orange points. 
2. In page 16, “wiht” -> “with”.

[1] Arora, Sanjeev, et al. "A theoretical analysis of contrastive unsupervised representation learning." arXiv preprint arXiv:1902.09229 (2019).

[2] HaoChen, Jeff Z., et al. "Provable guarantees for self-supervised deep learning with spectral contrastive loss." Advances in Neural Information Processing Systems 34 (2021): 5000-5011. 

[3] Chen, Xinlei, Saining Xie, and Kaiming He. "An empirical study of training self-supervised vision transformers." Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021.

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper has good clarification and motivation. 

Quality: I checked most proofs in the appendix. The statements look good to me. 

Novelty: The paper has its novelty as far as I know. 

Reproducibility: I believe the experiments part can be reproduced. 

summary_of_the_review: Although there are some questions I mentioned in the Weakness part that blocked me, the paper has its novelty and I tend to accept it.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: (a) The paper presents a theoretical analysis of contrastive learning. Previous work had shown that without any assumption on architecture, such learning can fail. Thus, this paper aims to prove success of contrastive learning for a particular architecture that is in a sense aligned 
with the true structure of the data. 
(b) Understanding such learning settings is challenging and important, and the paper does make progress on this question, demonstrating the type of structure that contrastive learning may be good in finding.
(c) There are some strong assumptions made (e.g., that dimensionality of model fits underlying dimensionality in data) that would be good to relax. The empirical evaluation is also very minimal, which is disappointing. 
justification_for_why_not_higher_score: As mentioned above, the paper does make some strong assumptions, and the empirical evaluation is almost non-existent, so I think a poster level presentation is adequate.
justification_for_why_not_lower_score: The paper does make progress on an important and challenging problem.
Decision: Accept: poster