Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper's goal is to understand the phenomenon of linear transferability of contrastively learnt representations. Namely, representations learnt via contrastive learning on a certain subpopulation which enable linear classification between two classes are also amenable to transfer to a classification task between the same pair of classes but on a different subpopulation to what was seen at train time. 
A key underlying object which will help shed light on this phenomenon is the positive-pair graph which is a weighted graph between all possible inputs $x$. The weight of an edge between $x,x'$ is the probability of sampling $x'$ as the positive pair of $x$ or vice-versa.
Prior work which introduced the positive pair graph connects the success of contrastive learning to clustering and expansion properties of the positive pair graph. This work builds on this connection to establish expansion conditions on the positive pair graph for linear transferability to occur. The main technical criterion identified is that the connections between two example clusters belonging to the same class across different subdomains should be strictly stronger than the connections between two clusters belonging to different classes in different subdomains.
To enable linear transferability, rather than train a linear head using cross-entropy loss, the authors propose using a simple feature averaging head. This alone however can run into issues when there are complex asymmetries present in the problem. As a result, they propose a preconditioning step leading to their (Preconditioned Feature Averaging) PFA algorithm. They show that this linear head provides significantly better results empirically in transferring to out of domain settings on the BREEDS dataset.

strengths_and_weaknesses: **Strengths**
1. The paper touches upon an important and poorly understood problem in self-supervised learning today and makes a novel and significant contribution in this space.
2. The writing is clear and the flow of the paper is smooth. The authors provide intuition at multiple technical places in the paper which helps the reader.
3. The paper offers a graph theoretic explanation of the reasons why certain empirical approaches in ML are successful. This is an interesting intersection between graph theory and ML.

**Weaknesses**
1. The theoretical tools and insights used seem to have a significant overlap with prior work of HaoChen et al which make the significance of the theoretical contributions of the current paper a bit diminished.

Nonetheless, I think this a technically solid paper with interesting experimental results which clears the bar for acceptance at NeurIPS.

questions: **Suggestions**
1. For the experiments can you include a comparison to the baseline contrastive approach of using the InfoNCE loss and throwing away the head of the encoder and training a linear layer on top at time of fine-tuning (as is done for instance in SimCLR)?

limitations: The authors adequately addressed the potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper theoretically studies the previously reported success of contrastive learning on unsupervised domain adaptation, where unlabeled data is available for the source and target domains but labels are only available for the source domain. This involves 3 steps, (1) train representations using contrastive learning on the combined unlabeled data for source and target, (2) train a linear classifier on source representations using source labels, (3) use the linear classifier *directly* for the target representations. This idea works well in some domain adaptation setting and is referred to as *linear transferability* in this paper.

The paper identifies natural conditions under which this procedure can provably works: data from the same class in different domains are more related to each other than data from different classes in different domains. This idea is formalized using the (weighted) augmentation graph introduced in HaoChen et al. where there is an edge between two data points if they appear as a positive pair. The analysis requires 3 main properties to be satisfied by the graph to ensure linear transferability: (a) few edges going outside of any class, (b) high expansion within a class, (c) high expansion across the same class in different domains. Proving this result requires extending the analysis for spectral contrastive learning from HaoChen et al.

The paper also proposes a new algorithm (PFA) to learn the source linear classifier: use the mean representation for classes, multiplied by an appropriate pre-conditioner for a de-noising effect. Experiments on BREEDS (constructed from ImageNet) show that PFA outperforms the baseline of logistic regression.

strengths_and_weaknesses: Strengths

- The phenomenon of linear transferability is quite interesting, as is the fact that contrastive learning helps with it.
- The paper adequately positions the required assumptions and analysis compared to prior work on domain adaptation and contrastive learning. For e.g., the comparison to Cai et al. using multiple notions of source and target transferability was useful in understanding the effect of different assumptions.
- It is well written and easy to follow. The proof sketches with increasing level of difficulty is a very useful addition to provide intuitions for the analysis.
- I skimmed over some of the proofs in the appendix; they are reasonably well-structured, clearly written and I did not find any obvious mistakes.



Weaknesses

- There is currently no discussion about interesting future directions
- While PFA (mean classifier + preconditioner) works better than logistic regression, there is no justification or intuition provided for this finding. More on this in questions for authors
- While the assumption seems intuitive, no verification for it, experimental or otherwise, is provided


Overall I think this paper is a solid contribution towards better understanding contrastive learning for unsupervised domain adaptation and I vote for accepting this paper.
questions: Other comments and questions
- Any intuition for why learned classifier (logistic regression) is worse than PFA on target domain? Is it an issue of labeled sample complexity in the source domain or is it more fundamental and would happen even with infinite labeled samples? Perhaps some simple experiments (by varying amount of source labeled samples) could shed some light on this.
- Is there a way to test (directly or indirectly) whether such expansions assumption holds, especially for min and max notions of expansions? It could also be useful to discuss what could happen if one or more of the assumptions do not hold.
- L214: “vulnerable to complex asymmetric structures” could use some clarification
- Near L140 it would be useful to mention that $C_1, \dots, C_m$ will correspond to classes of interest
- L237: Typo in “equation (50)”?
- L263: Should it be $\tau \gg r \log^2(r/\alpha)$?
- Some typos in L616 ($w({\color{red}x’})$ at the end) and equations 40 and 41 ($w({\color{red}x}, \tilde{x})$).

limitations: Some limitations are discussed. No potential negative societal impact discussed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper aims to provide an analysis of the linear transferability of contrastive learning in a general domain adaptation setting. In particular, they theoretically show that contrastive learning can encode cluster identities and catch the inter-cluster relationship. Experimental results on only one data set show that the proposed preconditioned feature averaging (PFA) provides better results in a comparison with linear probe.
strengths_and_weaknesses: Originality: The authors claim that their paper can provide analyzes of the linear transferability with weaker and more realistic assumptions compared to existing theoretical works. However, to be honest, since I did not have enough time to verify this. I'll be then based on the evaluations from other reviewers.

Quality: My major concern is about the empirical demonstration of the paper. In particular, the experimental results of the paper are indeed poor since they are only evaluated on only one data set (BREEDS) and the proposed method is compared with only one other method (linear problem). Having said that, I think that the authors definitely need more work on the empirical part of the paper since the current version looks like incomplete work. 

Clarity: The paper is well-written and easy to follow

Significance: Besides the concern above about the empirical results of the paper, I personally think that only studying the linear transferability in domain adaptation is quite insignificant since it can restrict the application of contrastive learning and domain adaptation in modern deep learning.
questions: Please see my comments on the weaknesses of the paper
limitations: Please see my comments on the weaknesses of the paper
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes a simple linear classification algorithm to be applied on top of a feature representation pre-trained using a standard contrastive learning self-supervised pre-training approach. The algorithm is a simple modification of a prototypical network approach by Snell et al. by using a variant of Mahalanobis distance instead of Eucledian one (the covariance matrix power is discussed but used only as 2-1=1 in the experiments). Theoretical guarantees are attempted, however they rely on many assumptions that are: (a) unrealistic to validate/gain intuition in practice; (b) rely on single instance bounds which are very unstable to single instance outlier noise that for sure exists in any real-world learning problem. A single empirical experiment is provided using the BREEDS dataset comparing to a single baseline - linear probing. The experiment is claimed to be one of unsupervised domain adaptation while in fact is of sub-population shift (the goal towards which BREEDS was designed for).
strengths_and_weaknesses: Strength:
* very simple (although not novel) linear classification algorithm
* lots of theoretical derivations
* improves one particular application of linear probing on BREEDS (after pre-training on the entire data source+target via self-supervised method which is optimized for ImageNet and hence in prat for BREEDS which is derived from ImageNet)

Weaknesses:
* the algorithm (protonet + Mahalanobis) is not new
* the bounds are using quantities that do not seem to be practically measurable, nor any attempt is made to explain how to measure them in practice - hence it is hard to see how would they provide useful intuitions or guarantees that could be applied in practice
* the bounds rely on assumptions utilizing single sample "max/min-expansion" bounds - but those seem to be highly unstable in presence of outliers - which are always present in every practical learning task ... so it seems unclear how those will be practical to use
* the empirical evaluation on BREEDS is clearly not UDA (as claimed) it is of sub-population shift (labeled samples are one type of cat and unlableld samples are another type of cat). I also assume the main reason for gains over linear probing are: (a) overfitting of the linear probing, probably better hyper-params could improve it considerably for BREEDS; (b) too small data for self-supervised pre-training of the representation model - probably better to take a well-optimized full ImageNet pre-trained model like DINO or MocoV2
* a single experiment, not well defined and with a single very simplistic baseline (linear probe) does not seem to be sufficient
* writing is not very clear, many experimental details are omitted, and code is neither promised nor provided (claimed proprietary in the checklist) - as it stands the paper does not bring much value in the empirical sense as all that makes its (limited) empirical results not reproducible as it seems

POST Rebuttal:
I must say that even after an in-depth discussion with the authors following their rebuttal response, I am not convinced that this paper should be accepted in its current form. Mainly due to some concerns with the practicality of the proposed theory that in my view would require many additional experiments that are currently not performed (as I explained in detail in my discussion with the authors). I, however, would like to acknowledge the value of author's efforts during the rebuttal, as well as the more positive opinion of the other reviewers, and hence, am raising my score by 1 point to "borderline reject".
questions: please see weaknesses
limitations: not discussed, in fact, there is no "conclusions" section either
review_title: null

Meta-review: metareview: The manuscript provides theoretical analyses of why contrastive learning helps domain adaptation. It developed new proof techniques, advancing the current status of contrastive learning theory. The manuscript then studied a version of the existing prototypical network approach by Snell et al., called Preconditioned Feature Averaging PFA (mean classifier + preconditioner) and demonstrated both theoretically and empirically that this simple algorithm works well as a domain adaptation algorithm.

Reviewers acknowledged several positive aspects of the manuscript including the phenomenon of linear transferability and the fact that contrastive learning helps with it. There are concerns related to experiments, however, the theoretical contributions in the manuscript outweigh some of the empirical deficiencies. 

Discussion phase has addressed concerns related to more experiments and showing that the theory is robust to outliers. To further increase the impact of the manuscript in terms of theory indeed predicts several phenomena that are verified by experiments, the authors have responded positively to the suggestion about testing on much larger scale and common for SOTA unsupervised domain adaptation testing datasets such as DomainNet and VisDA. The results will be added to the camera ready version.

confidence: Certain
Decision: Accept