Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies how does contrastive learning works from a theoretical perspective focusing on the spectral properties of the graph of the data induced by augmentations. They propose a new loss that is close up to a constant to the matrix factorization of the normalized adjacency matrix of the augmentations graph, under some assumptions they show that minimizing this loss provides downstream classification guarantees. Then, using standard Rademacher analysis they move from population guarantees to finite sample guarantees. Finally, they show empirically that their loss gives results close to state of the art. 
main_review: The paper is interesting and original. Connecting spectral graph theory with SSL is a surprising finding that I would not have foreseen a-priori. Moreover, the theory seems sound to my understanding and the paper is well written and accessible. I have few minor reservations:

The authors assume that "G cannot be partitioned into too many disconnected sub-graphs". This assumption seems rather strong for real data. Every *real* image therefore will be a disconnected subgraph with its augmentations, especially so for high resolution images. Where does this come about in the bounds? As far as I understand this should appear in \rho in Theorem 3.7. However, for example, if \alpha is 0 the bound should be 0. This seems unreasonable to me. What am I missing here?

A related issue that I'm wondering about is when does this construction break? Do assumptions 3.5 and 3.6 suffice to guarantee good downstream performance (assuming perhaps that the Rademacher complexity is small)? If so why don't we get 99% accuracy on ImageNet in the experiments? 

Other comments:
* Line 179 I think there is some confusion between R and Q.
* Line 189 Is this u_x'?

======

I would like to thank the authors for their detailed an enlightening comments that addressed my main concerns. After reading the comments and discussion with the other reviewers I would like to raise my score to 7. 
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper derives generalization bounds for learning using a contrastive objective under realistic assumptions on the positive pair generation process. The approach taken is to consider the so-called augmentation graph - the set of nodes comprises all augmented views of population distribution, with edges connecting nodes that correspond to different views of the same input datapoint. The core assumption made is that this graph cannot be split into a large number of disconnected subgraphs. This set-up aligns well with the intuition that in order to generalize, the contrastive notion of “similarity” must extent beyond the purely single-instance-level, and must somehow connect distinct inputs points.

My view is that this work is the most significant advance in the statistical learning theory of contrastive learning since the paper “A theoretical analysis of contrastive unsupervised representation learning” by Arora et al. This paper under review addresses the primary weakness in the work by Arora et al., which used an unrealistic assumption on positive pair generation. I will strongly advocate for acceptance of this paper.


main_review: 
## Discussion:

Prior work on contrastive and/or self-supervised learning theory typically either 1) assumes positive pairs are near-independent when conditioned on class label, or 2) is based on an information theoretic analysis (this is to the best of my knowledge, at least). The first case is clearly unrealistic, and the second suffers from at least a couple of drawbacks - a) the degree to which the success of contrastive learning (particular InfoNCE) can be attributed to its relation to mutual information has been experimentally disputed [1], and b) do not adequately explain why linear probes are sufficient to yield effective downstream performance. 

This paper avoids both of these drawbacks by proposing a new set of assumptions on positive pair generation (which in my view are much more realistic that previous assumption used) and directly analyzing a contrastive loss (which they actually propose in this work) instead of relating contrastive leanring to information theoretic concepts.  

**The assumptions on positive pair generation:**

Contrastive learning algorithms work on the level of individual instances - enforcing the similarity of embeddings of different views of *the same* individual instance. Despite this, the performance under linear probe is high on many downstream tasks. This empirical fact strongly indicates that learned encoders must be doing more than learning instance-level invariances. So how does the instance-level approach of contrastive methods extend to enforce relations between the embeddings of distance inputs? 

The paper under review takes a step towards answering this question by showing that under what I consider to be a fairly intuitive set of assumptions (but which are hard to verify empirically) the error of a linear probe can be bounded. The plausibility of these assumptions is the key to this work. If other reviewers are critical, it will almost certainly be due to some misgivings around these assumptions. 

As well as a fresh perspective on the assumptions underlying positive pair generation, this paper imports new tools (from spectral theory) to the analysis of contrastive leanring. The introduction of “new” analysis tools (new in the context of contrastive learning) is welcome in my eyes, and my be of use to others working on the theory of contrastive learning. 

I should note that due to time pressure I have not carefully checked the soundness of the proofs. From what I can tell so far I have seen nothing out of order.

---
## Minor criticisms:

I have already made my overall assessment of this work clear. This section contains minor criticisms.

- The finite sample bounds in Sec 4 are still somewhat separated from the objective used in practice. The finite sample objective in Sec 4 still takes expectations over the augmentation distribution: in practice this is approximated by drawing a single sample. 
- A very minor gripe: there are some suboptimalities in the experimental protocols. E.g. the authors report for SimCLR an accuracy of 46.5% on tinyImageNet with ResNet-50 backbone and 400 epochs of training, and batch size 512. In my own experiments in the past I have obtained over 53% using the same backbone, epochs, and batch size. This isn’t a big deal, though, and the experiments as they are suffice to illustrate the important point - that the proposed spectral loss can learn encoders with comparable performance to other popular methods of the day. 

---
## Clarity:

- l.179 I think R=Q here?
- l.48 I suppose \cal Z^+ denotes the positive integers. I would suggest using the more standard \mathbb{Z}^+, or simply saying “positive integer m” instead. 

---
## Questions: 
- You analysis, like many others, focuses on downstream classification tasks. How might your viewpoint relate to non-classifcation tasks that contrastive methods also enjoy empirically success on - e.g. object detection and image segmentation?

limitations_and_societal_impact: In my view the authors have adequately addressed the limitations and potential negative impacts of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the theoretical foundations of contrastive self-supervised learning. To do so, the authors study contrastive learning through the lens of the augmentation graph - the graph of augmented examples, with edges connecting "similar" examples. The authors suggest a novel contrastive loss function, s.t. minimizing this loss is equivalent to spectral clustering on the augmentation graph. Using this, the authors prove that if the augmentation graph has few edges that cross between sub-graphs of different labels, then using a linear readout on the learned representation, a small loss can be achieved w.r.t the supervised objective. The authors also analyze the sample complexity of learning the representation and learning the linear probe from sampled data. Finally, the authors show empirically that the suggested contrastive loss performs similarly to some baseline contrastive loss functions.
main_review: Overall, I think this is a very good paper. It is very clearly written, the results are novel, and give a new characterization of contrastive learning using the augmentation graph. The connection between self-supervised learning, graph theory and spectral clustering is very interesting, and to my knowledge this is the first work that connects these fields. The theoretical results are very clean, and their presentation makes it easy for the reader to understand and appreciate the results.

One thing that I think is still missing is a sample complexity analysis of learning both the representation and the linear probe. The paper studies the sample complexity of learning the representation, and then using the optimal linear classifier, or otherwise learning the linear probe from a finite sample using the optimal representation. However, in practice self-supervised learning uses large unlabeled data to learn the representation, and then a small labeled dataset to learn the linear classifier. Since the sample complexity is analyzed separately for the representation and the linear probe, it is not clear whether or not we gained anything from using self-supervised learning over supervised learning. That is - we have a trivial sample complexity bound for supervised learning of Bf(x), e.g. using Radamacher complexity. Is this sample complexity larger than the sample complexity of learning only B from labeled data? If so, what is the cost in unlabeled data?

Minor:
Line 189 - x_{x'} should be u_{x'}
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper theoretically analyzes contrastive learning relying on a concept of population augmentation graph. In the graph, two augmented samples are connected if they can be augmented from the same original instance. Based on this setup,
- This paper shows that spectral decomposition can be reformulated as a contrastive learning objective. Furthermore, this paper shows that minimizing the objective can guarantee a high linear probe accuracy under some mild assumptions.
- This paper shows the guarantee can be extended to the finite-sample regime and learning the linear probe with labeled data.
- This paper demonstrates the efficacy of the proposed spectral contrastive objective empirically in the standard setup: the proposed objective achieves similar performance as other state-of-the-art SSL methods.

main_review: Strengths
- This paper is well-written and well-organized. I believe that this paper has good readability for not only theorists but also practitioners.
- The proposed concept of the population augmentation graph and the spectral decomposition approach is convincing.
- It seems that Assumption 3.5 is practically reasonable for contrastive learning analysis. This is because SSL methods often assume that two augmented samples have the same semantic (i.e., underlying class) information; in other words, they also assume that correct predictions from the augmented samples are available (with high probability).
- This paper extends the guarantee (Theorem 3.7) to more practical scenarios. I feel that the result in Section 5 is interesting because the setting is almost the same as the standard linear evaluation benchmark.
- The proposed spectral contrastive loss shows competitive performance compared to state-of-the-art SSL methods. I think more empirical studies could improve the performance.

Concerns & Questions
- There is no empirical study related to the theoretical results.
  - This paper considers $k$ as a fixed constant, but one can choose $k$ arbitrarily in practice. In this case, how can we choose $k$? In Theorem 3.7 and 5.1, there is a trade-off in the upper bound. Therefore, we may need to choose proper $k$ for achieving the best performance. Can we observe the trade-off empirically, as stated in the theorems?
  - I'm also interested in the $\rho_k$'s growth because $\rho_k$ is the main factor of the error bound. Although L246 said that the growth would be characterized in Section 3.4, I cannot fully understand which point explains the growth. Could you provide more details? Also, can we approximate $\rho_k$ empirically? I wonder whether the error bound is still meaningful in practice or not.
- What is the role of the projection MLP in a theoretical perspective? The projection MLP is commonly used in self-supervised learning, and this work also uses it in the provided experiments (Section 6). However, the guarantees are obtained without considering the projection MLP.
- Can we omit $\log k$ in Theorem 3.7? By definition, $\rho_k\le 1$. Also, intuitively, $\rho_k\approx 1$ when $k$ is sufficiently large. In this case, the upper bound becomes large due to $\log k$. In my opinion, it would be better to do not hide $\log k$ in Theorem 3.7 and do not use the $\tilde{O}$ notation. This might confuse some readers: for example, one can think the upper bound goes to $\alpha$ for sufficiently large $k$.

Typos
- In Eq. (7), the second term might be $f(x)^\top f(x')$.
- In L215, Why $\phi_G(\{x\})=1$? In my opinion, $\phi_G(\{x\})=\frac{\sum_{x'\neq x} w_{xx'}}{\sum_{x'} w_{xx'}}<1$ because $w_{xx}>0$ for any $x\in\mathcal{X}$.
- In Eq. (11), does the second equality hold? I think the $\sqrt{w_x}$ terms should be in the numerator.

== after rebuttal ==

I sincerely appreciate your efforts to address my concerns. Like other reviewers, I think this paper's theoretical contribution is convincing, and I like the empirical results based on the theoretical findings. Hence, I would like to keep my positive score.

limitations_and_societal_impact: Yes. This paper addressed the limitations and potential negative societal impact.
review_title: null

Meta-review: This paper provides a new theoretical framework for contrastive learning. In particular, the authors find a new type of assumption, connecting spectral graph theory with self-supervised contrastive learning, which is much more realistic than what is common in prior statistical theory for contrastive learning. All reviewers agree on the significance of theoretical contribution provided by the paper. One of major concerns was on the connectivity assumption of the augmentation graph raised by Reviewer 1aqU. As the authors did in their rebuttal, it is quite useful to provide some concrete visual examples in the final draft, to avoid some misunderstanding. AC thinks it is also useful to provide some (real-world or synthetic) scenarios when the assumption breaks, possibly with supporting experiments (to see how much the assumption is crucial). In overall, AC thinks that the paper is very well written and could be a pioneering work, not only for theoretical purposes, but also for some better algorithmic solutions in the future.
Decision: Accept (Oral)