Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations
Authors: Jeff Z. HaoChen
Colin Wei
Ananya Kumar
Tengyu Ma
Venue: NeurIPS 2022 Accept (2022)
Keywords: representation learning theory
self-supervised learning theory
contrastive learning theory
domain adaptation theory
deep learning theory

Abstract: Contrastive learning is a highly effective method for learning representations from unlabeled data. Recent works show that contrastive representations can transfer across domains, leading to simple state-of-the-art algorithms for unsupervised domain adaptation. In particular, a linear classifier trained to separate the representations on the source domain can also predict classes on the target domain accurately, even though the representations of the two domains are far from each other. We refer to this phenomenon as linear transferability. This paper analyzes when and why contrastive representations exhibit linear transferability in a general unsupervised domain adaptation setting. We prove that linear transferability can occur when data from the same class in different domains (e.g., photo dogs and cartoon dogs) are more related with each other than data from different classes in different domains (e.g., photo dogs and cartoon cats) are. Our analyses are in a realistic regime where the source and target domains can have unbounded density ratios and be weakly related, and they have distant representations across domains. 

Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations
Jeff Z. HaoChen
Colin Wei Stanford University col @stiirtrnnoorded
Stanford University
Thaochen@stanffrdd.edh
Ananya Kumar
Tengyu Ma Stanford University tengyuma@stanford.o edu
Stanford University ananya@cs.stanfordd.ee stanford.edu
Abstract
Contrastive learning is a highly effective method for learning representations from unlabeled data. Recent works show that contrastive representations can transfer across domains, leading to simple state-of-the-arr algorithms for unsupervised domain adaptation.
particular, a linear classifier trained to separate the representations on the source domain can also predict classes on the target domain accurately, even though the representations of the two domains are far from each other. We refer to this phenomenon as linear transferability. This paper analyzes when and why contrastive representations exhibit linear transferability in a general unsupervised domain adaptation setting. We prove that linear transferability can occur when data from the same class in different domains (e.g., photo dogs and cartoon dogs) more related with each other than data from different classes in different domains (e.g., photo dogs and cartoon cats) are. Our analyses are in a realistic regime where the source and target domains have unbounded density
ratios and be weakly related, and they have distant representations across domains.
Introduction
In recent years, contrastive learning and related ideas have been shown to be highly effective for
representation learning [Chen al. 2020a by He al. 2020 Caron et al.) 2020 Chen al. 2020c
Gao et al. 2021 Su et al. 2021 Chen and He 2020 Contrastive learning trains representations on unlabeled data by encouraging positive pairs (e.g., augmentations of the same image) to have closer representations than negative pairs (e.g., augmentations of two random images). The learned representations are almost linearly separable: one can train a linear classifier on top of the fixed representations and achieve strong performance many natural downstream tasks (Chen) et al., 2020aa Prior theoretical works analyze contrastive learning by proving that semantically similar datapoints (e.g.. datapoints from the same class) are mapped to geometrically nearby representations [Arora et al. 2019 Tosh et al., 2020 2021 HaoChen et al. 202T]. In other words, representations form clusters in the Euclidean space that respect the semantic similarity; therefore. they are linearly separable for downstream tasks where datapoints in the same semantic cluster have the same label.
Intriguingly, recent empirical works show that contrastive representations carry richer information beyond the cluster memberships they can transfer across domains in linear way elaborated below. Contrastive learning is used in many unsupervised domain adaptation algorithms Thota
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

class
Brittany
Sang
Persian
Dog
Cat
Dog
Cat
Saup
Seat
San
Sext
transfer
Test 9g
Tavp
Fdss
Teot
Bulldog
Tong
Yaut
Tabby
domain
Representations with linear transferability
Representations
Positive-pai siriive-pairraee graph
without linear transferability
Figure 1: The linear transferability of representations. We demonstrate the linear transferability of representations when the unlabeled data contains images of two breeds of dogs (Brittanys, Bulldogs) and two breeds of cats (Persians, Tabbies). Left: A visualization of the positive- saaiiiveepairrrae graph with four semantic clusters. Inter-cluster edges (dashed) have much smaller weight than intra-cluster edges (solid). Inter-cluster edges between two breeds of dogs (or cats) have more weight than that between dog cluster and cat cluster. Middle and right: A visualization of two different types of representations: both have linear separability, but only the middle one has linear transferability. The red line is the decision boundary of dog-vs-cat linear classifier trained in the representation space on labeled Brittanys (Soog) vs. Persians (Seat images. The representation has linear transferability this classifier is accurate unlabeled Bulldogs (Toog) vs. Tabbies (Tea) images.
and Leontidis, 2021 Sagawa al. 2022 and the transferability leads simple oftte-of-the-ar
algorithms (Shen et al. 2022 Park et al. 2020 Wang et al. 2021]. In particular, [Shen et al. [2022] observe that the relationship between two clusters can be captured by their relative positions in the representation space. For instance, as shown in Figure | (middle), suppose Stog and Seat are two classes in a source domain (c.g.. Brittany dogs and Persian cats), and Tdog and Teat are two classes in a targer domain (c.g., Bulldogs and Tabby cats). A linear classifier trained to separate the representations of Saug and Sea turns out classify Taog and Tea as well. This suggests the four clusters of representations are not located in the Euclidean space randomly (e.g., as in Figure [ (right)), but rather in a more aligned position as in Figure | (middle). We refer this phenomenon as the linear transferability of contrastive representations.
This paper analyzes when and why contrastive representations exhibit linear transferability in general unsupervised domain adaptation setting. Evidently, linear transferability can only occur when clusters corresponding to the same class in two domains (e.g., Brittany dogs and Bulldogs) are somewhat related with each other. Somewhat surprisingly, we found that a weak relationship suffices: linear transferability occurs long corresponding classes in different domains are more related than different classes in different domains. Concretely, under this assumption (Assumptions 3.] or B.3). linear head learned with labeled data on one domain (Algorithm can successfully predict the classes on the other domain (Theorems 3.2 and 3.4). Notably, our analysis provably shows that representations from contrastive learning not only encode cluster identities but also capture the inter-cluster relationship, hence explains the empirical success of contrastive learning for domain adaptation.
Compared to previous theoretical works on unsupervised domain adaptation [Shimodaira 2000
Huang et al. 2006 Sugivama et al.) 2007 Gretton al.) 2008 Ben-David al. 2010 Mansour et al. 2009 Kumar et al. 2020 Chen et al. 2020d Cai et al. 2021], our results analyze ze modern, practical algorithm with weaker and more realistic assumptions. We do not require bounded density ratios or overlap between the source and target domains, which were assumed in some classical
works (Sugiyama al.) [007 Ben-David et al.) 2010 Zhang al., 2019 Zhao al.) 2019) Another line of prior works Kumar et al., 2020, Chen et al. 2020d] assume that data is Gaussian or near- Gaussian, whereas our result allows more general data distribution. Cai et al.
202TT] analyze
pseudolabeling algorithms for unsupervised domain adaptation, but require that the same-class cross-domain data are more related with each other (i.e., more likely form positive pairs) than cross-class same-domain data are. We analyze contrastive learning algorithm with strong empirical

---

performance, and only require that the same-class cross-domain data are more related with each other than cross-class rross-domain data, which is intuitively and empirically more realistic as shown
in Shen et al. 2022 (See related work and discussion below Assumption 3.1 for details).
Technically, we significantly extend the framework of HaoChen al. [202T] to allow distribution shift-our setting only has labels on one subpopulation of the data (the source domain). Studying transferability to unlabeled subpopulations requires both novel assumptions (Assumptions 3.1 and and novel analysis techniques (as discussed in Section
Our analysis also introduces variant of the linear probe instead of training the linear head with the logistic loss, we learn it by directly computing the average representations within a class, multiplied by preconditioner matrix (Algorithm D. We empirically test this linear classifier benchmark datasets and show that it achieves superior domain adaptation performance in Section S
Additional Related Works. A number of papers have analyzed the linear separability of representations from contrastive learning [Arora et al. 2019 Tosh al. 2020 2021 HaoChen et al. 2021] and sele-supe learning [Lee et al. 2020] whereas we analyze the linear transferability. Shen et al. 2022 also analyze the linear transferability but only for toy examples where the data is generated by a stochastic block model. Their technique requires strong symmetry of the positive-pair graph (which likely does not hold in practice) so that top eigenvectors can be analytically derived. Our analysis is much more general and does not rely explicit, clean form of the eigenvectors (which is impossible for general graphs).
Empirically, pre-training on larger unlabeled dataset and then fine-tuning on smaller labeled dataset one of the most successful approaches for handling distribution shift [Blitzer et al. 2007
Ziser and Reichart 2018 2017 Ben-David et al.) 2020 Chen et al.) [012 Xie et al.
[2020] Jean et al.
2016 Hendrycks et al. 2020 Kim et al.) [022| Kumar et al. 2022 Sagawa et al.
2022 Thota and
Leontidis 2021 Shen et al. [0222] Recent advances in the scale of unlabeled data, such as in BERT
and CLIP, have increased the importance this approach [Wortsman et al., 2022 202T]. Despite the empirical progress, there has been limited theoretical understanding of why pre- training helps domain shift. Our work provides the first analysis that shows pre-trained representations with a supervised linear head trained on one domain provably generalize to another domain.
2 Preliminaries
In this section, we introduce the contrastive loss, define the positive-paie pair graph, and introduce the basic assumptions on the clustering structure in the positive-pair graph.
Positive pairs. Contrastive learning algorithms rely on the notion of "positive pairs", which are pairs
of semantically similar/related data. Let X' be the set of population data and P++ be the distribution of positive pairs of data satisfying P+ x²) = P+ .x) for any 2, 2' X. We note that though positive pair typically consists of semantically related data, the vast majority of semantically related pairs are positive pairs. In the context of computer vision problems (Chen et al., 2020a these pairs are usually generated via data augmentation on the same image.
For the ease of exposition, we assume X' is finite but large set (e.g., all real vectors in Ied with bounded precision) of size N. We use Px to denote the marginal distribution of i.c., Px(x) ;= Exex P+ (Ir, x²). Following the terminology in the literature |Arora et al. 2019], we call (z, 2²) "negative pair" if x and x' are independent random samples from Px.
Generalized spectral contrastive loss. Contrastive learning trains representation function (feature extractor) by minimizing a certain form of contrastive loss. Formally, let f R be a mapping from data to k-dimensioonll features. In this paper, we consider more general version of the spectral contrastive loss proposed in HaoChen et al. [2021]. Let L be the k-dimensional identity matrix. We consider the following loss with regularization strength o > O:
Lo(f)
E (e,
[l] fx 112 +o -(ff),
where the regularizer is defined as R(f)
E [f()) - -nxe The loss C, intuitively
minimizes the closeness of positive pairs via its first term, while regularizing the representations'
3

---

covariance to be identity, avoiding all the representations to collapse to the same point. Simple algebra shows that L, recovers the original spectral contrastive loss when (see Proposition [B.] for a formal derivation). We note that this loss is similar in spirit to the recently proposed Barlow Twins loss [hontar et al. 2021
The positive-pair graph. One useful way to think of positive pairs is through a graph defined by their distribution. Let the positive-pair graph be weighted undirected graph G w) such that the vertex set is X, and for x, , E Ex, the undirected edge (z, x²) has weight w(r, x²) = (1, (x,x²) x'). This graph was introduced by HaoChen et al. [02T]] as the augmentation graph when the positive pairs are generated from data augmentation. We introduce a new name to indicate the more general applications
of the graph into other use cases of contrastive learning (e.g. see Gao et al. (202T). ). We use
w(x) = Px (x) = Evex w(x,x') x') to denote the total weight of edges connected to a vertex x. We
call A R N the normalized adjacency matrix of G(X, w) if Agx' w(r, x²)/ //l/////////// (=())((z') and call == INXN A the Laplacian of G(X, w).
2.1 Clustering assumptions
Previous work accredits the success of contrastive learning to the clustering structure of the positive- pair graph because the positive pairs connect data with similar semantic contents, the graph can be partitioned into many semantically meaningful clusters. To formally describe the clustering structure of the graph, we will use the notion of expansion. For any subset A of vertices, let w(A) A EPEa wxxx) be the total weights of vertices in A. For any subsets A, B of vertices, let w(A, B) e EEEATEE w(x, x') be the total weights between set A and B. We abuse notation and use w1x, B) to refer to w((x). B) when the first set is a singleton.
Definition 2.1 (Expansion). Let A, B be two disjoint subsets of X. We use o(A, B), o(A, B) and é(A, B) to denote the expansion, max-expansion and min- ciiinnxxansionn from A to B respectively, defined as
B(A, w(A, B)
w(x, B) ZEA w(x)
w(x B) ZEA w(x)
((A. = max
6(A, = min
(2)
Note that ((A, S w(AA
Intuitively, (AA the average proportion of edges adjacent to vertices in A that go to B, whereas the max- max-penin-e is an upper (lower) bound of this proportion for each a E A.
Our basic assumption the positive-pair graph is that the vertex set X' can be partitioned into m groups Cj,..., C.,, with small connections (expansions) across each other.
Assumption 2.2 (Cross-clustes connections). For some (0. 1). we assume that the vertices of the
positive-pair graph G can be partition into m disjoint clusters ....., Cm such that for any i E [m].
o(C,,
S
(3)
We will mostly work with the regime where a < Intuitively, each C, corresponds to all the data with certain semantic meaning or a class of interest. For instance, C, may contain dogs from certain
breed. Our assumption is slightly stronger than in HaoChen et al. 2021] In particular, they assume that the average expansions cross clusters is small, i.e., _ie(m (CC,, X C.)) w((.)) S ar, whereas we assume that the max-expansion is smaller than a for each cluster. In fact, since Eie(m) w(C,)
and dCC,, X') < HCC, X') Ct), Assumption 2.2 directly implies their assumption. However, we note that Assumption 2. is still realistic in many domains. For instance, any bulldog æ has way more neighbors that are still bulldogs than neighbors that are Brittany dog, which suggests the max-expansion between bulldogs and Brittany dogs is small.
We also introduce the following assumption about intra-cluster expansion that guarantees each cluster can not broken into two well-separated aub-clusters.
Assumption 2.3 (Intra-cluster conductance). For all E [m], assume the conductance of the subgraph restricted to C₁ is large, that is, every subset A of C₂ with at most half the size of C₂ expands to the rest:
VA C C satisfying w(A) < (C,)22, ((A,))A) 27
(4)
We index A (2, X X. Generally, we will index the N-dimensional axis of array by X.

---

We have < 1 and we typically work with the regime where y is decently large (e.g.. Q(1), or inverse polynomial in dimension same regime where prior work HaoChen et al. [02T] guarantees the representations of clusters are linearly separable.
H and much larger than the cross-cluster connections a. This the
We also remark that all the assumptions are on the population positive-pair graph, which is sparse but has reasonable connected components (as partially evaluated in Wei al. [2020]. The rest of the
paper assumes access to population data, but the main results can be extended to polynomial sample results by levering model class for representation functions with bounded Rademacher complexity as shown in HaoChen et al. 2021
3 Main Results on Linear Transferability
In this section, we analyze the linear transferability of contrastive representations by showing that representations encode information about the relative strength of relationships between clusters.
Let S and T be two disjoint subsets of X. each formed by clusters corresponding to classes. We say representation function has linear transferability from the source domain to the target domain T if linear head trained on labeled data from S can accurately predict the class labels T. E.g.. the representations in Fig. 1 (middle) has linear transferability because the max-margin linear classifier trained Sang vs. Seat also works well on Taog vs. Teat. We note that linear separability is a different, weaker notion, which only requires the four groups of representations to be linearly separable from each other.
Mathematically, we assume that the source domain and target domain are formed by r clusters among C1..... Cm for I m/2. Without loss of generality, assume that the source domain consists of cluster S₁ = C1...., S, = C, and the target domain consists of Ti = Cy+1..... T, = Cgyy- Thus, S S; and T Ui We assume that the correct label for data in S; and T; is the cluster identity& i. Contrastive representations are trained on (samples of) the entire population data (which includes all C₃'s). The linear head is trained the source with labels, and tested on the target.
Our key assumption is that the source and target classes are related correspondingly in the sense that there are more same-class cross-domain connections (between S; and T2) than cross-class cross-domain connections (between S, and Tj with i + j), formalized below.
Assumption 3.1 (Relative expansion). Lei minsejri Φ(T;, Si) be the minimum min exianxxpasssons from T, to St. For some sufficiently large universal constant (e.g., c works), we assume that 2 a²a and that
p min oTT,, S.) c. -max max-o((T,,))) ST), E
(5)
if)
Intuitively, equation (5) says that every vertex in T. has more edges connected to S, than Sj- The condition p Z a says that the min-expansion p is bigger than the square of max-expansion a. This is reasonable because a < 1 and thus a² < a, and we consider the min-expansion p and be somewhat comparable. In Section 3.1 we will relax this assumption and study the case when the average expansion oTT,, S2) is larger than of (T;; Sy)-
max-expansion
Our assumption is weaker than that in the prior work (Cai et al. [021] which also assumes expansion from S, to T; (though their goal is to study label propagation rather than contrastive learning). They assume the same-class cross-domann conductance (T,;,S to be larger than the cross-class same- domain conductance o(S,, S,). Such an assumption limits the application to situations where the domains are far away from each other (such as DomainNet Peng al. 2019
Moreover, consider an interesting scenario with four clusters: photo dog, photo cat, sketch dog, and sketch cat. [Shen et al. [022) empirically showed that transferability can occur in the following two settings: (a) we view photo and sketch as domains: the source domain photo dog vs photo cat, and the target domain is sketch dog vs sketch cat; (b) we view cat and dog as domains, whereas photo and
EEg., suppose each cluster's distribution is a Gaussian distribution with covariance 1, and the data augmentation is Gaussian blurring with a covariance isoperimetric inequality [Bobkov et all [997]. The same also holds with a Lipschitz transformation Gaussian. "n contrast, the positive-graph built only on empirical examples will barely have any edges, and does not exhibit any nice properties. However, the sample complexity bound does not utilize the empirical graph at all.
then the intra-cluster expansion is 12(1) by Gaussian
5

---

sketch are classes: the source domain is photo dog vs sketch dog, and the target is photo cat vs sketch cat. The condition that cross-domain expansion is larger than cross-class expansion will fail to explain the transferability for one of these settings-if if (phhoo dog, sketch dog) < @pphoto dog, photo cat), then it cannot explain (a), whereas if (pphoto dog, sketch dog) > Φ p(photo dog, photo cat), it cannot explain (b). In contrast, our assumption only requires conditions such as @(photo dog, sketch dog) > @pphoto dog, sketch cat), hence works for both settings.
We will propose a simple and novel linear head that enables linear transferabilityy Let Ps be the data distribution restricted to the source domain For E [r], we construct the following average representation for class i in the source
b;
E [(x) E R
(6)
One of the most natural linear head is to use the average feature b, 's as the weight vector for class i, as in many practical few shot learning algorithms (Snell et al. 2017 6 That is, we predict
( arg max (f) .E[r]
This classifier can transfer to the target under relatively strong assumptions (see the special cases in the proof sketch in Section 4 but is vulnerable to complex asymmetric structures in the graph. To strengthen the result, we consider a variant of this classifier with a proper preconditioning.
To do so, we first define the representation covariance matrix which will play an important role:
Σ E [[+)S(()T] P~
(8)
The computation of this matrix only uses unlabeled data. Since Σ E R is a low-dimensional matrix for i not too large, we can accurately estimate using finite samples from Px. For the ease of theoretical analysis, we assume that we can compute this matrix exactly. Now we define family of linear heads on the target domain: for E Z+, define
Se (x) arg max (f(x), E' bb))) vE[r]
The case when = 1 corresponds to the linear head in equation When / is large, It. will care more about the correlation between (xr and b; in those directions where the representation variance is large. Intuitively, directions with larger variance tend to contain information also in a more robust way, hence the preconditioner has a "de-noising" effect. See Section 3 for more on why the preconditioning improve the target error. Algorithm I gives the pseudocode for this linear classification algorithm.
Algorithm 1
Preconditioned feature averaging (PFA)
Require: Pre-trained representation extractor f, unlabeled data Px, source domain labeled data Ps. target domain test data ã. integer E Z
1: Compute the preconditioner matrix Σ := EI~Px [xxx)
2: for every class i E [r] do
3: Compute the mean feature of the class i: b, = ((aw) [1l yy = 1) f(x)).
4: return prediction arg max (f(z), E'-b))
We note that this linear head different from prior work Shen et al. 2022 where the linear head is trained with logistic loss. We made this modification since this head is more amenable to theoretical analysis. In Section we show that this linear head also achieves superior empirical performance.
The error of head on the target domain is defined as:
Eg(g)
R P-Pr
[1 TT
(10)
The following theorem (proved in Appendix E) shows that the linear head ge achieves high accuracy on the target domain with a properly chosen t:
4 Formally, we have Ps(x)) == (xx)
w(S |x E S) and (x is defined similarly.
'ee assume access to independent samples from Ps and thus can be accurately estimated with finite labeled samples the source domain.
We note that shot learning algorithms do necessarily consider domain shift settings.

---

Theorem 3.2. Suppose that Assumption 2.2 and 3.7 holds. Px(S)/Px(T) I O(1. Let f be minimizer of the contrastive loss (z(-) and the head gr be defined 9 p/(8a²), we have
Then, for any 1 v
1 x²x -xp(p=xppppe (( -xp(-22Ne1))
Er S
(11)
where Akt1 the k+1-th smallest eigenvalue of the Laplacian of the positive-por graph. Furthermore, suppose Assumption 2.3 also holds and k 2m, with t p/(8"), we have
(r( S a²g2 exp (-2
pr
(12)
To see that RHS of equation 12 implies small error, one can consider reasonable setting where the intra-cluster conductance on the order of constants (i.e., 7 2 9(1)). In this case, long as p a² log(r/a), we would have error bound (g()) < In general, long as 7 a= (the intra-cluster conductance is much larger than cross-cluster connections or its square root) and is comparable a, we have pr² > a² and thus small upper bound of the error.
Theorem 3.2 shows that the error decreases as increases. Intuitively, the PFA algorithm can be thought of computing low-rank approximation of "smoothed" graph with normalized adjacency matrix A', where the normalized adjacency matrix of the original positive-pate graph. A larger t will make the low-rank approximation of A' more accurate, hence smaller error. However, there's also an upper bound 2 p/ (8a²), since when / is larger than this limit, the graph would be smoothed much, hence the corresponding relationship in the graph between source and target classes would be erased. more formal argument can be found in Section
We also note that our theorem allows "overparamccterizaioon"" in the sense that larger representation dimension & always leads to a smaller error bound (since A&+11 is non-decreasing in k). Morcover, theorem can be easily generalized to the setting where only polynomial samples of data are used to train the representations and the linear head, assuming the realizability of the function class.
3.1 Linear transferability with average relative expansion
In this section, we relax Assumption 5. and only assume that the total connections from T; S; is larger than that from T; to Sj, formalized below.
Assumption 3.3 (Average relative expansion (weaker version of Assumption 3.1 For some sufficiently large > 0, we assume that
Vi, (T.,, 7 a²
and Vi $
(T) ST)
(13)
The following theorem (proved in Appendix generalizes Theorem 3.2 in this setting.
Theorem 3.4. Suppose Assumptions 2.2
2.3 and
3.3 hold, Px(S)/Px(T) I O(1), and feature
dimension k 2 2m. Then, for some
Ω
log we have
r Er S TTB
log² (
(14)
Again, consider reasonable setting where the intra-cluster conductance is the order of constants (i.e., 7 2 ((1)). this case, so long as т, the gap between same-class cross-domain connection and cross-class cross- donss- connection is sufficiently large (c.g.. r > r rlog" (1/a)). we would have an error bound Er (g.) < 1.
We note that the intra-cluster connections (Assumption 2.3 are necessary, when we only use the average relative expansion (Assumption 3.3 as opposed to Assumption B.1). Otherwise, there may exist subset T; C T; that is completely discomnected from X' X',T, hence no linear head trained on the source can be accurate on T.

---

4
Proof Sketch
Key challenge: The analysis will involve careful understanding of how the spectrum of the normalized
adjacency matrix of the positive-pair graph is influenced by three types of connections: (i) intra-cluster
connections; (ii) connections between same-class cross-domain clusters (between St and T:), and (iii) connections between cross-class and cross-domain clusters (between S; and Tú for i * j). Type (i) connections have the dominating contribution to the spectrum of the graph, contributing the top eigenvalues. When analyzing the linear separability of the representations of the clusters. [HaoChen ct al. 2021] essentially show that type (ii) and (iii) are negligible compared to type (i) connections. However, this paper focuses on the linear transferability, where we need to compare how type (ii) and type (iii) connections influence the spectrum of the normalized adjancency matrix. However, such a comparison is challenging because they are both low-order terms compared to type (i) connections. Essentially, we develop a technique that can take out the influence of the type (i) connections so that they don't tt negatively influence our comparisons between type (ii) and type (iii) connections.
Below we give a proof sketch of sligthly weaker version of Theorem 3.2 under simplified setting. First, we assume r = 2, that is, there are Iwo source classes S and S2, and two target classes Ti and T2. Second, we assume the marginal distribution over is uniform, that is, w(x) 1/N as this case typically capture the gist of the problem in spectral graph theory. Third, we will consider the simpler case where the normalized adjacency matrix A is PSD, and the regularization strength a = 1.
Let f(x) = vw(x)- f(x) and F Nx be the matrix with f(x) on its x-th row. HaoChen et al. 2021 (or Proposition
C.1 showed that matrix FFT contains the top-k eigenvectors of A. We will first give a proof for the case where FFT exactly (Section 4. or near exactly (Section 4.2 recovers
A. Then we'll give proof for the more realistic case where F F is not guaranteed to approximate
A accurately (Section 4.3)
4.1 Warmup case: when l = oc and FFT = À
In this extremely simplified setting, the inner product between the embeddings perfectly represents the graph (that is, (z) f(x')) = ). As a result, the connections between subsets of vertices, a graph quantity, can be written as a linear algebraic quantity involving F:
1 w( A, B) = N 1 TA
1 N
FIFF
(15)
where 1 E {0. 1). is the indicator vector for the set A and we used the assumption w(()) = 1/N.
and
We start by considering the simple linear classifier which computes the difference between the means of the representations in two clusters.
U E S~
[f(z)] - E
[f()) =F FT(s,
(1s, - 1s,)= E R
(16)
S
This classifier corresponds to the head gi defined in Section
3 which suffices for the special case
when FFT- A. Applying v to any data point x E Ti UT2 results the output (xx) = f(x) v. For notational simplicity, we consider ~(x) = f(x) v vw(x)f(x) FT (1s, 1s,). Because ((x)
and ((x) has the same sign, it suffice show that ((x) 0 for x E Ti and ((x) < 0 for E Th. Using equation (5) that links the linear algebraic quantity to the graph quantity.
((x) 1 FF (1s, 1s,) 1. A(1s, 1s,) N- (w(x, - w( S2))
(17)
In other words, the output ÿ depends on the relative expansions from æ to S and from x to S2. By Assumption 3. or Assumption [.3] we have that when E Tı, x has more expansion to S1 than S2. and vice versa for x E Tg. Formally, by Assumption 3. we have that
Vx E T, (xx, S1) 2 p 2 ((x, S2) and Va E T2, 6(x, 2 p d(a, St) Because d0x S,) w1rr, S.) (mxx))
(18)
N N S,). have for x E Tú, w(s, S1) wrxx, and therefore by equation (7). ((x) ) > 0. Similary when x E T2, f(x) < 0.
7 Formally, we have (1))= iff E A.
'Here because of the binary setting, the classifier can only involve one weight vector in ied; this is equivalent using two linear heads and then compute the maximum in equation
8

---

4.2
When & < N and is almost rank-k
Assuming oc unrealistic since in most cases the feature is www-dimeniional, i.e., & < N. However, so long as A is almost rank-k, the above argument still works with minor modification. More concretely, suppose A's (k+ 1++h)-th largest eigenvalue,
> 1, less than c. Then we have ||A FF llap = 1 - Ak+1 I E. It turns out that when e < 1, we can straightforwardly adapt the proofs for the warm-up case with additional error in the final target performance. The error comes from second step of equation
4.3 When Á is far from low-rank
Unfortunately, realistic graph's A&+1 is typically not close to 1 when & < N (unless there's very strong symmetry in the graph as those cases in Shen et al. [022]). ) We aim to solve the more realistic and interesting case where X is a relatively small constant, c.g., 1/3 inverse polynomial
in d. The previous argument stops working because FFT is very noisy upproximation of A: the error | Flop llop Our main approach is considering the power of A, which reduces the negative impact of smaller cigenvalues. Concretely, though ||A - FF llop = 1 - A6+1 is non-negligible, (FFT) y is much better approximation A::
AR+1 is non-negligible and can be larger than || llop = A
|| - (FFT) = -
(19)
when t 2 (llog((/e)). Inspired by this, we consider the transformed linear classifier
e' = Σ PT (1s, 1s,),
(20)
where Σ = FTFFF is the covariance matrix of the representations. Intuitively, multiplying Σ forces the linear head pay more attention to those aarge-varinnee directions of the representations, which are potentially more robust. The classifier outputs the following on target datapoint (with rescaling of / (x) for convenience)
f((x) =
F1ss - 11,)
=1 (FF)) 1s,) (1s -1s))
(21)
where the last step uses equation 19 Thus, to understand the sign of (z)).. it suffices to compare 1__ A'1, with 1__ A'1ss. In other words, it suffices to prove that for æ E Tı. 1 A'1s, > 1 A'1s,
We control the quantity 1 JA'ss,; by leveraging the following connection between Á and a random walk on the graph. First, let D = diag(u ()) be the diagonal matrix with DRw w(x), A E NNN be the adjacency matrix, i.e., Aga' wxx x'). Observe that AD-1 transition matrix that defines a random walk on the graph, and (AD-1)e correspond to the transition matrix for steps of the random walk, denoted by To, It..... Because A' (D- 1022222D AD-AAD-11/2 = (D A) D-122 1/2 and = 1/N INXN we can verify that 1 A''ss s, = Pr(x, E S1 xo = z]. That is, 1, A' and 1 A'1,,, are the probabilities to arrive at S, and S2, respectively. form zi = x. Therefore, to prove that _ A'1s, 1 A'1s, > for most x E Ti, suffices to prove that a t-step random walk starting from Ti is more likely to arrive at S₁ than Sz. Intuitively, because Ti has more connections to S₁ than S2, hence random walk starting from Ti more likely to arrive at S₁ than at S2. In Section E we prove this by induction.
Simulations
We empirically show that our proposed Algorithm I achieves good performance on the unsupervised domain adaptation problem. We conduct experiments on BREEDS [Santurkar et al. 2020 a dataset for evaluating unsupervised domain adaptation algorithms (where the source and target domains are constructed from ImageNet images). For pre-training, we run the spectral contrastive learning algorithm [HaoChen et al., 202T] on the joint set of source and target domain data. Unlike the previous convention of discarding the projection head, we use the output after projection MIP as representations, because we find that significantly improves the performance (for models learned by spectral contrastive loss) and is more consistent with the theoretical formulation. Given the

---

pre-trained representations, we run Algorithm | with different choices of t. For comparison, we use the linear probing baseline where we train a linear head with logistic regression on the source domain. The table below lists the test accuracy on the target domain for Living-17 17 and Entity-30 two datasets constructed by BREEDS. Additional details can be found Section
Linear probe
PFA (ours, t t= 1)
PFA (ours, t 2)
Living-17 17
54.7
67.4
72.0
Entity-30
46.4
62.3
65.1
Our experiments show that Algorithm| Tachevves better domain adaptation performance than linear probing given the pre-trained representations. When / 1, algorithm is simply computing the mean features of each class in the source domain, and then using them as the weight of a linear classifier. Despite having lower accuracy than linear probing on the souree domain (see section A for the source domain accuracy), ) this simple algorithm achieves much higher accuracy on the target domain. When 2, our algorithm incorporates the additional preconditioner matrix into the linear classifier, which further improves the domain adaptation performance. We note that our results on En0ity-30 is better than [hhen [002] who compare with many state-of-the-art unsupervised domain adaptation methods, suggesting the superior performance of our algorithm.
Conclusion
In this paper, study the linear transfcrability of contrastive representations, propose simple linear classifier that can be directly computed from the labeled source domain, and prove that this classifier transfers to target domains when the positive-pair graph contains cross-domain connections between the same class than cross-domain connections between different classes. We hope that our study can facilitate future theoretical analyses of the properties of self-supervised representations and inspire new practical algorithms.
References
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In International Conference Machine Learning, 2019.
Eyal Ben-David, Carmel Rabinovitz, and Roi Reichart. Perl: Pivot-based domain adaptation for pre- trained deep contextualized embedding models. Transactions of the Association for Computational Linguistics, 8:504-521, 2020.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 19(1-2):151-175, 2010.
John Blitzer, Mark Dredze, and Fernando Pereira. Biographies, bollywood, foom-boxes and blenders: Domain adaptation for sentiment classification. In Proceedings of the 45th annual meeting of the association of computational linguistics, pages 440-447, 2007.
2007.
Sergey G Bobkov et al. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in gauss space. The Annals of Probability, 25(1):206-214, 1997.
Tianle Cai, Ruiqi Gao, Jason Lee, and Qi Lei. A theory of label propagation for subpopulation shift.
In International Conference on Machine Learning, pages 1170-1182. PMLR, 2021.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprini arXiv:2006.09888 33:9912-9924, 2020.
Minmin Chen, Zhixiang Xu, Kilian Q Weinberger, and Fei Sha. Marginalized denoising autoencoders for domain adaptation. In Proceedings of the 29th International Coference on International Conference Machine Learning, pages 1627-1634, 2012.
10

---

Ting Chen, Simon Korbllith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning. volume 119 of Proceedings of Machine Learning Research, pages 1597-1607. PMLR, PMLR, 13-18 Jul 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton, Big self-supervised models are strong semi-supervised learners. arXiv preprint arXiv:2006.1002, 2020b.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. arXiv preprini arXiv:201 I. 10566,, pages 15750-15758, June 2020.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0422 2020c.
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift. In Advances in Neural Information Processing Systems (NeurIPS), 2020d.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourleenth international conference on artificial intelligence and statistics, pages 213-223. JMLR Workshop and Conference Proceedings, 2011.
Geoffrey French, Michal Mackiewicz, and Mark Fisher. Self-ensembling for visual domain adaptation. arXiv preprint arXiv: 706.05208. 2017.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. aovainiadversarial training of neural networks. The journal of machine learning research, 17(1):2096-2 200200000000,00 2016.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simcse: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv: 222.000440)2211 2021.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. In Dataset Shift in Machine Learning. 2008.
Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss, 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729-997299 9738, June 2020.
Dan Hendrycks, Xiaoyuan Liu, Eric Wallace, Adam Dziedzic, Rishabh Krishnan, and Dawn Song. Pretrained transformers improve out-of-distribution robustness. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7744-2751, 2020.
Jiayuan Huang, Arthur Gretton, Karsten M Borgwardt, Bernhard Schölkopf, and Alex J Smola. Correcting sample selection bias by unlabeled data. Advances in neural information processing systems, pages 601-608, 2006.
Neal Jean, Marshall Burke, Michael Xie, W. Matthew Davis, David Lobell, and Stefano Ermon. Combining satellite imagery and machine learning to predict poverty. Science, 353, 2016.
Donghyun Kim, Kaihong Wang, Stan Selaroff, and Kate Saenko. A broad study of pre-training for domain generalization and adaptation. arXiv preprint 2203. 2022.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In International Conference Machine Learning (ICML), 2020.
11

---

Ananya Kumar, Aditi Raghunathan, Robbie Jones, Tengyu Ma, and Percy Liang, Fine-tuning can distort pretrained features and underperform out-of-distributton. arXiv preprint 4rXiv:2202.10054, 2022.
James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher- order cheeger inequalities. Journal of the ACM (JACM), 61(6):1-30, 2014.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo. Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008. 010604 2020.
Anand Louis and Konstantin Makarychev. Approximation algorithm for sparsest k- k-partitioning. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1244-1255. SIAM, 2014.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3450 2009.
Changhwa Park, Jonghyun Lee, Jaeyoon Yoo, Minhoe Hur, and Sungroh Yoon. Joint contrastive learning for unsupervised domain adaptation. arXiv preprint arXiv:2006. 10297, 2020.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. Proceedings of the IEEE International Conference on Computer Vision, pages 1406-1415, 2019.
Viraj Prabhu, Shivam Khare, Deeksha Kartik, and Judy Hoffman. Sentry: Selective entropy optimization via committee consistency for unsupervised domain adaptation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8558 8567, 2021.
Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Kendrick Shen Sang Michael Xie, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Sara Beery Henrik Marklund, Etienne David, Ian Stavness, Wei Guo, Jure Leskovec, Tatsunori Hashimoto Kate Saenko, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the wilds benchmark for unsupervised adaptation. In International Conference on Learning Representations, 2022.
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopulation shift. arXiv, 2020.
Kendrick Shen, Robbie Jones, Ananya Kumar, Sang Michael Xie, Jeff Z. HaoChen, Tengyu Ma, and Percy Liang. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. In International Conference Machine Learning (ICML), 2022.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
Yixuan Su, Fangyu Liu, Zaiqiao Meng, Tian Lan, Lei Shu, Ehsan Shareghi, and Nigel Collier. Tacl: Improving bert pre-training with loken-aware contrastive learning, 2021.
Masashi Sugiyama, Matthias Krauledat, and Claus-Robers MÅÄleer. Covariate shift adaptation by importance weighted eross validation. Journal of Machine Learning Research, 2007.
Mamatha Thota and Georgios Leontidis. Contrastive domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2209-2218, 2021.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. w.Xiv2203..022.33 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. Algorithmic Learning Theory, pages 1179-1226. PMLR, 2021.
12

---

Rui Wang, Zuxuan Wu, Zejia Weng, Jingjing Chen, Guo-Jun Qi, and Yu-Gang Jiang. Cross-domain contrastive learning for unsupervised domain adaptation. arXiv preprint arXiv:2106.05526 2021.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self self-training with deep networks on unlabeled data, 2020. URL https://opennreveett ierpeerreieeennne//oruumm
IC8sJ4i6kaH
Mitchell Wortsman, Gabriel Ilharco, Mike Li, Jong Wook Kim, Hannanch Hajishirzi, Ali Farhadi, Hongseok Namkoong, and Ludwig Schmidt. Robust fine-tuning of zero-shot models. arXiv preprint arXiv:2109.01903 2021.
Mitchell Wortsman, Gabriel Ilharco, Samir Yitzhak Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Korblithh, al. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. arXiv preprint arXiv:2203.cm 0.44822 2022.
Sang Michael Xie, Ananya Kumar, Robbie Jones, Fereshte Khani, Tengyu Ma, and Percy Liang, In- n-out: Pre-training and self- traintrannngg using auxiliary information for out-of-distribution robustness. In International Conference on Learning Representations, 2020.
Jure Zbontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny, Barlow twins: Self-supervised learning via redundancy reduction. arXiv preprint arXiv: 103.032300 2021.
Yuchen Zhang. Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. International Conference on Machine Leurning, pages 7404-7413, PMLR, 2019.
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In Proceedings of the 36th International Conference on Machine Learning, pages 7523-7532, PMLR, 09-15 Jun 2019. URL httpp://proceeddnngs
mlr. ptt.spres/vv/////// httasss/////zao09a... html
Yftah Ziser and Roi Reichart. Neural structural correspondence learning for domain adaptation. In Proceedings of the s Conference Computational Natural Language Learning (CoNLL 2017), pages 400-410, 2017.
Yftah Ziser and Roi Reichart. Deep pivot-based modeling for cross-language cross-domain transfer with minimal guidance. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pages 238-249, 2018.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
13

---

(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experiments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "wgwdMyhK1Su", "reviewer": "Reviewer_GwWK", "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.\n\nThe 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.\n\nThe 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.\n", "questions": "Other comments and questions\n- 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.\n- 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.\n- L214: “vulnerable to complex asymmetric structures” could use some clarification\n- Near L140 it would be useful to mention that $C_1, \\dots, C_m$ will correspond to classes of interest\n- L237: Typo in “equation (50)”?\n- L263: Should it be $\\tau \\gg r \\log^2(r/\\alpha)$?\n- Some typos in L616 ($w({\\color{red}x’})$ at the end) and equations 40 and 41 ($w({\\color{red}x}, \\tilde{x})$).\n", "limitations": "Some limitations are discussed. No potential negative societal impact discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The phenomenon of linear transferability is quite interesting, as is the fact that contrastive learning helps with it.\n- 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.\n- 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.\n- 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.\n\n\n\nWeaknesses\n\n- There is currently no discussion about interesting future directions\n- 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\n- While the assumption seems intuitive, no verification for it, experimental or otherwise, is provided\n\n\nOverall I think this paper is a solid contribution towards better understanding contrastive learning for unsupervised domain adaptation and I vote for accepting this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nOTAUro5_V3", "reviewer": "Reviewer_RBh1", "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).", "questions": "please see weaknesses", "limitations": "not discussed, in fact, there is no \"conclusions\" section either", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* very simple (although not novel) linear classification algorithm\n* lots of theoretical derivations\n* 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)\n\nWeaknesses:\n* the algorithm (protonet + Mahalanobis) is not new\n* 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\n* 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\n* 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\n* a single experiment, not well defined and with a single very simplistic baseline (linear probe) does not seem to be sufficient\n* 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\n\nPOST Rebuttal:\nI 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\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i0XCtsztLwl", "reviewer": "Reviewer_TUn2", "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.", "questions": "Please see my comments on the weaknesses of the paper", "limitations": "Please see my comments on the weaknesses of the paper", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nQuality: 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. \n\nClarity: The paper is well-written and easy to follow\n\nSignificance: 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2QRYMaHTyeG", "reviewer": "Reviewer_1Rjf", "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. \nA 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.\nPrior 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.\nTo 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.\n", "questions": "**Suggestions**\n1. 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)?\n", "limitations": "The authors adequately addressed the potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. 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.\n2. 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.\n3. 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.\n\n**Weaknesses**\n1. 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.\n\nNonetheless, I think this a technically solid paper with interesting experimental results which clears the bar for acceptance at NeurIPS.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept