Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to provide theoretical understanding for contrastive learning where "similar pairs" of points $x$ and $x^+$ are encouraged to have similar representations through an InfoNCE inspired objective function. Some prior works show the benefit of learned representations for linearly classifying downstream classes, by making conditional independence like assumption on the similar pairs or positive samples, i.e. $x$ and $x^+$ are (approximately) conditionally independent given downstream label $y$. This work argues that these assumptions are quite strong for contrastive learning with data augmentations, and aims to show guarantees under the following weaker and more realistic assumption: support of augmentation distribution of different inputs from the same class overlap to form a "connected graph" of inputs within a class, whereas support of augmentations of inputs from different classes do not overlap. Lower and upper bounds using this and some other assumptions, connecting the downstream performance of representation function to the contrastive loss. Some simulation experiments are presented to support some aspects of the theoretical analysis.

Using the insights from the analysis, the paper proposes an "Average Confusion Ratio (ACR)" metric that can be used to predict the ranking of downstream performances of different augmentations **using only unlabeled data**. Experimental evidence is provided on CIFAR and STL datasets to verify the efficacy of this metric for some practical augmentations. 


While there are some interesting aspects in the paper (especially the ACR metric), the theoretical analysis seems to have raised many questions and concerns that I have summarized below (details in main review). 

- **Soundness of assumptions**: Assumption 4.6, which is crucial, seems questionable and may not be coherent or appropriate to make in this setting. More on this in point (W2) of main review

- **Deeper dive into theoretical results**: There is a lack of discussion about the (non-)vacuousness of the bounds in the main results Theorem 4.2 and 4.8, that puts the interpretation and significance of the result in question. More on this and related issues in point (W2) of main review.

- **Comparison to prior work**: The work of HaoChen et al. in particular is not adequately compared to, especially since some of the points being addressed here are covered through a different kind of analysis in that paper. More on this in point (W3) of main review.
main_review: **Strengths**:

- (S1) The problem being addressed is very relevant. Contrastive learning has enjoyed a lot of empirical success, and various works on theoretically understanding lack in one of many aspects when it comes to closeness to practice. This paper addresses issues with the theoretical assumptions and results in many prior work.

- (S2) Theorem 4.2 that upper bounds the downstream classification loss without conditional independence is new and interesting. The ACR metric that can select good augmentations using just unlabeled data is also an interesting finding.

- (S2) Various parts of the paper are accompanied with experiments (simulations and on standard datasets) to relate the theoretical analysis to practice

- (S3) Paper is clearly written and easy to follow

**Weaknesses**:

Here are many concerns about the theoretical assumptions and results that would help to have addressed by the authors.

- (W1) Assumption 4.6: One of the main concerns is the perfect alignment assumption, which *assumes* that the optimal solution $f^*$ of the NCE loss will satisfy $f^*(x) = f^*(x^+)$ for all positive samples $x$ and $x^+$. This seems like an unnatural assumption to make directly on the optimal solution, and is implicitly an assumption on the distribution of positive samples $p(x, x^+)$, since the optimal unit norm representations that minimizes that infoNCE loss depends strongly on this distribution. While some arguments for perfect alignment have been made in prior work [3], it is not clear whether that can be coherently imported here as an assumption. In fact, it is quite likely that the optimal infoNCE solution will not satisfy this assumption exactly for most joint distributions $p(x, x^+)$ (at the very least, a lot more justification is needed). This benign looking assumption undercuts the point that results here are shown under "less restrictive assumptions" compared to prior work, and it kind of trivializes the result in Theorem 4.8. **Note that the concern here is not just that the assumption is too strong or unrealistic (which is often unavoidable and acceptable), but that its not clear when the assumption can even be true and whether or not it is mathematically compatible with the rest of the setting.**.

- (W2) (Non-)vacuousness of bounds: I found Theorem 4.2 interesting since it can show a bound similar to the bound from [1] but without the conditional independence. One discussion I found missing is about how vacuous/non-vacuous the upper bound can be. Since the upper bound looks like $\mathcal{L}_{NCE}(f) - \log(M/K) + \sqrt{\text{Var}(f(x) | y)}$, it is not entirely clear whether this bound can ever be non-vacuous, i.e. are there cases where the sum of these terms can be very small. For e.g., in Theorem 4.8 where $\text{Var}(f(x) | y) = 0$, I can estimate a rough lower bound on this upper bound of $\log(M/K + M(1-1/K)/e^2) - \log(M/K) \approx \log(1 + (K-1)/e^2)$ which can be large for a large value of $K$. (here I used $\|f(x)\| = 1$). A discussion about the vacuousness (or not) of the bound can be critical in understanding whether the bound is indeed meaningful. A side note, given Theorem 4.2 and Proposition 4.7, Theorem 4.8 just seems like a corollary rather than a theorem.

- (W3) The result in [2] does not need conditional independence kind of assumption and in fact does analyze a more general case, albeit for a different spectral version of the contrastive loss. In particular, Assumption 4.1 from this paper will lead to $\alpha=0$ from that paper, and Assumption 4.5 from this paper will lead to reasonably high value for the Dirichlet conductance $\rho_{K}$ that shows up in their bound. Given that their results for spectral contrastive learning hold for the setting being considered in this paper, it is worth making a more detailed comparison to that paper.


**Other comments and questions**

- Section 5.1 seems to have some potentially interesting hypersphere example to demonstrate many of the points, but I thought it was not discussed enough in the main paper. It would help to give a short and clear summary of the results in Section B in the main paper.

- Some statements made in the paper deserve much more justification or could be toned down. E.g. "the class collision terms that are incompressible in Saunshi et al. (2019) now disappear in our bounds by adopting the InfoNCE loss, which also explains why InfoNCE performs better in practice": this does not really seem like an explanation for why InfoNCE performs better in practice, it is a weak justification at best. "increasing M indeed leads to a lower approximation error and helps close the gap" this is not clear since $\mathcal{L}_{NCE}(f)$ also depends on $M$.

- The setting for Proposition 3.1 is not described clearly, with regards to what kind of augmentation distributions (overlapping or not) does it hold for. I can only guess that it is for the case where they don't overlap for any pair of inputs, so it is not applicable when Assumption 4.5 is satisfied for example. Some clarification on this would be appreciated.

- Assumption 4.1 says that the conditional label distribution $p(y|x) = p(y|x^+)$ matches for positive samples $x$ and $x^+$. However this assumption is invoked in many places to say that inputs from different classes do not have overlapping support of augmentations and that the label is deterministic given $x$ or $x^+$, e.g. "Besides, because proper data augmentation will not cause inter-class support overlap (Assumption 4.1)" on page 6. Perhaps this assumption needs to be modified appropriately, or may be a separate assumption is needed about augmentation distributions not overlapping between inputs from different classes.

- The ACR metric makes sense and it is interesting that it helps in practice. but connection to theory is weaker than it is made out to be. After all the theory only talks about the overlap between augmentation distributions, but nothing about the nearest neighbors w.r.t. randomly initialized network features or the learned features.

- Will help to explain what $f_j(x)$ means in Theorem 4.2; seems like it means that $j^{th}$ coordinate of $f(x)$.

- Proposition 4.7 should only be true for $f^*$ and not all $f$.

- Is "chaos" used as a technical term? If so, any citation for its prior usage would be useful to include.

- Missing citations: [4,5] theoretically analyze contrastive learning for downstream task, [6] reports inverted-U shaped curves as in Figures 7 and 8 in this paper.

[1] Arora et al., A theoretical analysis of contrastive unsupervised representation learning. 2019.

[2] HaoChen et al., Provable guarantees for self-supervised deep learning with spectral contrastive loss. 2021.

[3] Wang et al., Understanding contrastive representation learning through alignment and uniformity on the hypersphere. 2020.

[4] Tosh et al., Contrastive estimation reveals topic posterior information to linear models. 2020.

[5] Tosh et al., Contrastive learning, multi-view redundancy, and linear models. 2020.

[6] Tian et al., What Makes for Good Views for Contrastive Learning? 2020.
summary_of_the_review: The paper aims to provide some theoretical analysis for contrastive representation learning under weaker assumptions than prior work (like conditional independence) and has some interesting empirical findings about how performance of augmentations can be ranked using a metric that depends just on unlabeled data. While the general idea is nice, there are issues with the theoretical setup (as described in the main review), raising questions about the meaningful-ness of the assumptions and results. Furthermore the comparison to prior very relevant work is also inadequate. This leads me to assign a score of reject for the current version.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The current leading theory of what contrastive losses are doing and why they work interprets contrastive learning as balancing alignment with uniformity, as proposed in [2].  This paper seeks to augment that understanding of contrastive learning using a new perspective, focusing on the role of data augmentation.  It is well-known that contrastive learning techniques are highly sensitive to the data augmentation schemes used, most notably discussed in [1].  In this work, the authors interpret augmentation as a way to connect different intra-class images together.  Then, the contrastive loss is seen as a way to gradually cluster intra-class samples together by aligning augmented views, producing representations that are class-separated even in feature space.

On top of introducing a new lens with which to understand contrastive learning, the authors also provide proofs on performance guarantees, as well as a new evaluation metric.  The metric is inspired by their augmentation-oriented understanding, and was also found to align well with downstream performance.

The authors provide a scenario where alignment and uniformity are satisfied, but fails to translate well to downstream classification accuracy.  This suggests to them that the instance discrimination task alone cannot guarantee the learning of class-discriminative features that would enable better downstream classification, and directs their attention to the other important component of contrastive-learning to help explain the story: augmentation.  They then build off the analytical work of [3] to prove guarantees for the downstream performance with a relaxed assumption.


[1] Chen et al., A Simple Framework for Contrastive Learning of Visual Representations, 2021.

[2] Wang and Isola., Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere, 2020.

[3] Saunshi et al., A theoretical analysis of contrastive unsupervised representation learning, 2019.

main_review: In this exploration of data augmentation, much emphasis has been placed in the concept of "augmentation strength" - but what about the choices of augmentations themselves?  Can we perhaps use the ARC metric to evaluate, compare, and select data augmentation schemes themselves?  Separately, can the ARC metric be used to guide the selection of data augmentation parameters?  For example, for an arbitrary given augmentation scheme we can calculate the parameters that would maximize the ARC metric in an unsupervised way - then would applying those augmentations lead to comparable performance across different *choices* of augmentation strategies?  In other words, is the ARC metric a strong-enough metric that supercedes the selection of data augmentation strategies?  I would like to see more thought, analysis, and application regarding this new metric to fully convince me of its value and uses.

Additionally, to bridge the synthetic scenario and real data, I would like to see an augmentation graph of real augmented images, drawn with T-connections (where T can even be 1), and perhaps varied over different strength parameters.  I think there is definitely a gap between the authors' theoretical proposals/scenarios and that of actual natural data that can be closed with extra effort.  For example, the authors only mention one augmentation scheme to measure augmentation strength in real-world datasets, the RandomResizedCrop operator, and only evaluate it using their proposed metric.  Lastly, the reference section appears rather sparse, given the massive catalogue of work (including theoretical) surrounding contrastive learning.

Some typos:
- "alone cannot guarantee to learn class-discriminative..." should be "alone cannot guarantee the learning of class-discriminative..."
- "Comparing to Saunshi..., while ours only..." should be "Compared to Saunshi..., ours only" (page 6, Section 4.2).
- "and the surrogate could complete its mission..." should be " and the surrogate can complete its mission..." (page 7, Section 4.3)
- "different augmentation strength affects" should be "different augmentation strengths affect" (page 9, Section 6).
- "We take 500 sample as...For the encoder class , we..." should be "We take 500 samples as...For the encoder class, we" (page 16, Section D.1)
summary_of_the_review: The authors expand our understanding of contrastive learning on top of the existing alignment and uniformity perspective, by studying the role of data augmentation.  They provide theoretical guarantees on downstream performance, and propose an interesting new metric that can be evaluated using only the given unsupervised data.  Overall I think this is a strong submission, and would recommend an accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new theory for understanding contrastive representation learning. The novelty is the focus on the interplay between alignment and augmentation. Prior work has identified alignment as one of the factors of contrastive learning, but have not investigated how different types of augmentations may affect the learned embeddings. This work adds that missing piece. The results intuitively make sense, showing that proper amount of augmentation (that connects samples of the same class) has positive effect on downstream classification. Empirically, the authors verify that too weak or too strong augmentation harms performance. Based on observations, the authors define a metric on ratio of positive pairs among nearest (embedding) neighbors, and found the change of this metric throughout training positively correlate with performance.
main_review: Strengths:
+ Theory considering both augmentation and alignment, without making too much assumptions.
+ Empirical verification on the niceness of a proper amount of augmentation.
+ The ACR and ARC metrics characterizes the interplay between augmentation and alignment, and are indicative of task performance.

Weaknesses:
+ The theoretical results are a bit weak. E.g., as pointed out in paper, Thm 4.8 only talks about the minimizer of the contrastive loss.

  Maybe this is unavoidable with the current set of augmentations. But can there be a version with the perfect alignment assumptions relaxed into approximate alignment? If so, it might be possible to talk about non-minimizers.

+ Proposition 3.1 is incorrect (but fixable I think). 

  No finite samples can attain uniformity, because perfect alignment $\implies$ features are concentrated among finite number of vectors $\implies$ not a uniform distribution. The exact stated form is wrong, but I think some variants of it is true. 

+ Figure 6.

  What is the experiment setting for this?

+ Sec. 5.1 "... And when $r$ is too large ($r=3$), ... "
 
  Is $r$ the geodesic distance on sphere or Euclidean distance in the ambient space? Either case, it is really large... (almost) containing the entire sphere! Is there not a milder augmentation that can also show the difference?
   
summary_of_the_review: The paper provides a theoretical analysis on the interplay between alignment and augmentations. Empirical experiments nicely complement the theory, and lead to interesting metrics that reveal the properties of this interplay. Overall the paper is also nicely written. While there is one slightly incorrect claim (which I think is fixable) and some places that would need clarification, I think the findings in this paper are valuable to the field. Thus, I recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors provided a new understanding of contrastive learning from the perspective of data augmentation for intra-class samples. In particular, the authors proposed to understand the role of data augmentation as to create certain ``chaos'' between intra-class samples so to encourage the clustering of intra-class samples and also the learning of class-separated representations. Additionally, a new metric ARC is proposed to evaluate the downstream performance. The conclusion is validated via both synthetic and real-world datasets. 
main_review: Strengths:

The authors provided a new understanding of contrastive learning from the perspective of data augmentation for intra-class samples. Moreover, to evaluate the effect of data augmentation a quantitative analysis is provided along with a new metric. 

############

Weaknesses:

. Theorem 4.2: For the downstream classification, the loss is upper and lower bounded in terms of the L_NCE loss. The authors provided comparison with Saunshi et al. (2019) from the technical perspective. Is there any intuitive explanation on how to evaluate the classification performance in terms of contrastive learning (loss)? 

. Assumption 4.5 (intra-class connectivity): This assumption is strong. Without the label information, it seems impossible to derive such augmentation set. Please add discussion on the practicality of this assumption, and show an example on some datasets if possible.

. Proposition 4.7: Based on the proof provided in the appendix the conclusion not only relies on the existence of such augmentation set (Assumption 4.5), but also that such augmentation should be applied to intra-class samples, ie, t_i(x_i) = t_j(x_j). This kind of operation is impractical without the label information. Please add comment on that.

. In the experiments, RandomResizedCrop is used to illustrate the relationship between Aug Strength and ACC(ARC). The best performance for different datasets all achieves at Aug Strength = 0.92. Any comments on that? eg., in terms of data augmentation for intra-class samples at Aug Strength = 0.92?

. In practice, there are different kinds of data augmentation, eg, flipping, rotation, and scaling. The authors only showed results on RandomResizedCrop. Can you show results for other data augmentation types? Do you have similar conclusion as that for RandomResizedCrop? 

. Different data augmentation types are often used together in practice (eg, randomly pick two augmentations from the augmentation set for the raw image). Then how to apply the proposed analysis in such practical case? In particular, how to measure the Aug Strength? 

. The authors emphasized the importance of the data augmentation design for intra-class samples (ie, perfect overlapping). 1) The study on applying the analysis to existing contrastive learning algorithms is, however, preliminary (only with RandomResizedCrop). 2) Based on the proposed analysis how to find the sweet spot of data augmentation for contrastive learning is crucial, but this is not discussed. 


summary_of_the_review: The idea of understanding contrastive learning from the perspective of data augmentation for intra-class samples is interesting. However, 1) some key assumption for the analysis is too strong; 2) the analysis on the existing contrastive learning algorithms is preliminary and needs more work; and 3) the authors emphasized the importance of finding the sweet spot of data augmentation (ie, perfect overlapping). But how to achieve that in practice is not discussed.
review_title: null

Meta-review: The paper under review provides a theoretical analysis for contrastive representation learning. The paper proposes a guarantee on the performance (specifically upper and lower bounds) without resorting to previously used conditional independence assumptions. Throughout, the theoretical results and assumptions are supported by experiments. 

After a lively discussion, and after changes made to the paper in the revision stage, all four reviewers recommend this paper for acceptance. 
- Reviewer tWSB appreciates that the paper makes weaker assumptions than prior work (i.e., not assuming conditional independence), but raises a number of serious concerns on the theoretical results: The review questions whether assumption 4.6 used in the theory can be true, and whether the bound is vacuousness. The authors argue that this assumption was used in prior work, point out that only some of their results rely on this assumption, and that the assumption is compatible with the theory. The response of the authors partly resolved the reviewers concern and the reviewer raised their score. 
- Reviewer bTLa finds the idea of understanding contrastive learning for intra-class samples interesting, but finds some key assumptions too strong, a critique similar to that raised by reviewer tWSB. The authors responded and the reviewer increased their score, and mentioned that most concerns were addressed. The response partially resolved the reviewers concern, and the reviewer now also recommends acceptance. 

I recommend to accept the paper. Understanding contrastive learning better is an important problem, and based on my own reading, I agree with the reviewers that the paper contributes to the understanding of contrastive learning. Two reviewers had concerns about unrealistic assumptions, but those have been largely resolved in the discussion.
Decision: Accept (Poster)