Complementary Benefits of Contrastive Learning and Self-Training Under Distribution Shift
Authors: Saurabh Garg
Amrith Setlur
Zachary Chase Lipton
Sivaraman Balakrishnan
Virginia Smith
Aditi Raghunathan
Venue: NeurIPS 2023 poster (2023)
Keywords: contrastive learning; self training; distribution shift; semi supervised learning; unsupervised domain adaptation
TL;DR: Our work examines the synergy between self-training and contrastive learning, finding complementary benefits under distribution shift setups and up to 8% accuracy improvement in certain datasets.

Abstract: Self-training and contrastive learning have emerged as leading techniques for incorporating unlabeled data, both under distribution shift (unsupervised domain adaptation) and when it is absent (semi-supervised learning). However, despite the popularity and compatibility of these techniques, their efficacy in combination remains surprisingly unexplored. In this paper, we first undertake a systematic empirical investigation of this combination, finding (i) that in domain adaptation settings, self-training and contrastive learning offer significant complementary gains; and (ii) that in semi-supervised learning settings, surprisingly, the benefits are not synergistic. Across eight distribution shift datasets (e.g., BREEDs, WILDS), we demonstrate that the combined method obtains 3--8\% higher accuracy than either approach independently. Finally, we theoretically analyze these techniques in a simplified model of distribution shift demonstrating scenarios under which the features produced by contrastive learning can yield a good initialization for self-training to further amplify gains and achieve optimal performance, even when either method alone would fail.

Complementary Benefits of Contrastive Learning and Self-Training Under Distribution Shift
Saurabh Garg" Carnegie Mellon University sgarg20andrew cmu. edu
Amrith Setlur*
Zachary Lipton
Carnegie Mellon University asetlur@andreu cmu edu
Carnegie Mellon University
zlipton@andrew. cmu. edu
Sivaraman Balakrishnan
Virginia Smith
Aditi Raghunathan
Carnegie Mellon University sbalakri aakricaanee @anddre.. cmu. edu
Carnegie Mellon University smithv@andrew. cmu. edu
Carnegie Mellon University
aditirag@andrew, cmu. edu
Abstract
Self-training and contrastive learning have emerged as leading techniques for incorporating unlabeled data, both under distribution shift (unsupervised domain adaptation) and when it is absent (semi-supervised learning). However, despite the popularity and compatibility of these techniques, their efficacy in combination this paper, we first undertake a systematic
remains surprisingly uncxplored. empirical investigation of this combination, finding (i) that in domain adaptation settings, self-training and contrastive learning offer significant complementary gains; and (ii) that in semi-supervised learning settings, surprisingly, the benefits are not synergistic. Across eight distribution shift datasets (e.g.. BREEDs, WILDS), we demonstrate that the combined method obtains 3-8% higher accuracy than either approach independently. Finally, we theoretically analyze these techniques in simplified model of distribution shift demonstrating scenarios under which the features produced by contrastive learning can yield good initialization for self-training further amplify gains and achieve optimal performance, even when either method alone would fail.
Introduction
Even under natural, von-adversarial distribution shifts, the performance of machine learning models often drops [65] 83 47 29]. While we might hope to retrain our models on labeled samples from the new distribution, this option is often unavailable due to the expense impracticality of collecting new labels. Consequently, researchers have investigated the Unsupervised Domain Adaptation (UDA) setting. Here, given labeled source data and unlabeled out-of-distribution (OOD) target data, the goal is to produce a classifier that performs well on the target. Because UDA is generally underspecified (7). researchers have focused two main paths: (i) domain adaptation papers that explore heuristics for incorporating the unlabeled target data, relying on benchmark datasets ostensibly representative of "real-worid shifts" to adjudicate progress [72 85 47]: and (ii) theoretically motivated papers that explore structural assumptions under which UDA problems are well posed [77, (4).. This work engages with the former focusing on two popular methods: self-training and contrastive pretraining.
were both proposed, initially, for traditional Semi- Seni-Supere Learning (SSL) problems, where the labeled and unlabeled data drawn from the same distribution. Here the central challenge statistical: to exploit the unlabeled data learn better predictor than would get by training on the (small) labeled data alone. More
Self-training
75 52
90 86 and contrastive pretraining
[3] 16 93
$ Equaal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Aggregate SSL results (no dist. shift)
Aggregate UDA results (w dist. shift)
ST
ERM
70
dependency on spurious feature after ERM
Cl offers a good initialization for STOC
80.1
67.6
80
79.2
CCL
ID Accuracy
0OD Accuracy
62.4
STOC
75
Invariant
72.8
57.0
Feature
70
67.8
48.9
Targtt Unlabbled
STOC amplities CL gains under distribution shill
Labeled
Spucious
Feature
ERM ST CL STOC
ERM CL STOC
Augmentaation
(a)
(b)
Figure 1: Self-training over Contrastive learning (STOC) improves over Contrastive Learning (CL) under distribution shift. (a) We observe that in SSL settings, where labeled and unlabeled data are drawn from the same distribution, STOC offers negligible improvements over CL. In contrast, in UDA settings where there is distribution shift between labeled and unlabeled data, STOC offers gains over CL. Results aggregated across benchmarks. Results on individual data in Table D and 2 (b) 2-D illustration of our simplified distribution setup, depicting decision boundaries learned by ERM and CL and how Self-Training (ST) updates those. ①, @ and summarize our theoretical results in Sec.
recently, these methods have emerged as favored empirical approaches for UDA, demonstrating efficacy on many popular benchmarks [70] 30 12 76.. In self-training, one first learns a predictor using source labeled data. The predictor then produces pseudolabels for the unlabeled target data, and a new predictor is trained on the pseudolabeled data. Contrastive pretraining learns representations from unlabeled data by enforcing invariance to specified augmentations. These representations are subsequently used to learn classifier. In UDA, the representations are trained on the union of the source and target data. attempts to explain their strong empirical performance, several researchers have attempted analyses under various assumptions on the data, task, and inductive biases of the function class [8 39 73, 76 12 40, 38 [T]. Despite the strong strong results, there has been surprisingly little work (both empirically and theoretically) exploring when either might be expected to perform best and whether the benefits might be complementary.
In this paper, we investigate the complementary benefits of self-training and contrastive pretraining. Interestingly, we find that the combination yields significant gains in UDA despite producing negli- gible gains in SSL. In experiments across eight distribution shift benchmarks (e.g. BREEDs [72]. FMoW 477, Visda (63),, we observe that re-using unlabeled data for self-training (with Fix- Match 79 after learning contrastive representations (with SWAV [33,, yields > 5% average im- provement on OOD accuracy in UDA as compared to < 0.8% average improvement in SSL (Fig. I..
Next, we address the question why the combination of self-training and contrastive learning proves synergistic in distribution shift scenarios. To facilitate our analysis, we consider simplified distribu- tion shift setting that includes two types of features: (i) invariant features that perfectly predict the label; and (ii) domain-dependent features that are predictive of the label just source. Our theoreti- cal analysis reveals that self self-training can achieve optimal target performance but requires a "good" enough classifier to start with. We observe that source-only ERM fails to provide a "good" initializa- tion. On the other hand, contrastive pretraining on unlabeled data performs better than ERM but is still sub-optimal. This implies that contrastive pretraining ends up decreasing reliance on domain- dependent features (as compared to ERM) but doesn't 't completely eliminate them. Nevertheless, contrastive pretraining does provide a "good" initialization for self fff-itraning. i.e., "good" initial pseu- dolabels on the target unlabeled data. As result, self-training top of contrastive learned features effectively unlearns the reliance on Nomain-dependeen features and generalizes perfectly OOD. In contrast, for SSL settings (i.e., in distribution), our analysis highlights that contrastive pretraining al- ready acquires sufficient predictive features such that linear probing with (a small amount of) labeled data picks up those features and attains near-optimal ID generalization.
Finally, we connect our theoretical understanding of "good" representations from contrastive learning and improved linear transferability from self self-training back to observed empirical gains. We linearly probe representations (fix representations and train only the linear head) learned by contrastive pretraining vs. no pretraining and find: (i) contrastive pretraining substantially improves the ceiling on

---

the target accuracy (performance of optimal linear probe) compared to ERM: (ii) self self-training mainly improves linear transfer, i.e. OOD performance for the linear probe trained with source labeled data.
2 Setup and Preliminaries
Task. Our goal is to learn a predictor that maps inputs I' E X' C Fd to outputs E y We parameterize predictors f = h o & R - V/ where & Fd - R2 is a feature map and h R is classifier that maps the representation to the final scores or logits. Let Ps. PT be the source and target joint probability measures over X' x y with ps and pr as the corresponding probability density (or mass) functions. The distribution over unlabeled samples from both the union of source and target is denoted as Pu- (1/2) (a( (1/2) Pr(x).
We study two particular scenarios: (i) Unsupervised Domain Adaptation (UDA); and (ii) Semi- Supervised Learning (SSL). In UDA, we assume that the source and target distributions have the same label marginals (y( = Pr(y) (i.e., no label proportion shift) and the same Bayes optimal predictor, i.e., arg , Ps y z) arg max, PT (y zz.. We given labeled samples from the source, and unlabeled pool from the target. In contrast in SSL, there is no distribution shift, i.e., Ps PT Pu. Here, are given small number of labeled examples and comparatively large amount of unlabeled examples, both drawn from the same distribution, which we denote as PT.
Unlabeled data is typically much cheaper to obtain, and our goal in both these settings is to leverage this along with labeled data achieve good performance on the target distribution. In the UDA scenario, the challenge lies in generalizing out-of- -i--rr-biiiiitiinn while in SSL, the challenge is to generalize in-distribution despite the paucity of labeled examples. A predictor ʃ evaluated on distribution P via its accuracy, i.e., P) Ep(arg max [(x) = y)
Methods. We now introduce the algorithms used for learning from labeled and unlabeled data.
1. Source-only ERM (ERM): A standard approach is to simply perform supervised learning on the labeled data by minimizing the empirical risk Σm= E(h o ((x), y). for some classification loss 8: IR x y R (e.g., softmax cross-entropy) and labeled points {(T,,, 3))
2. Contrastive Learning (CL): We first use the unlabeled data to learn a feature extractor. In particular, the objective is to learn a feature extractor Pei that maps augmentations (for e.g. crops or rotations) of the same input close to each other and far from augmentations of random other inputs [13 16 93). Once we have Pet, we learn a linear classifier h on top to minimize a classification loss on the labeled source data. We could either keep Pei fixed propagate gradients through.
When clear from context, also use CL to refer to just the contrastively pretrained backbone without training for downstream classification.
3. Self-training (ST): This is a two-stage procedure, where the first stage performs source-only ERM by just looking at source-labeled data. In the second stage, we iteratively apply the current classifier on the unlabeled data to generate "pseudo-labels" and then update the classifier by minimizing a classification loss on the pseudolabeled data [52]
3 Self-Training Improves Contrastive Pretraining Under Distribution Shift
Self-Training Over Contrastive learning (STOC). Finally, rather than starting with a source-only ERM classifier, we propose to initialize self-training with CL classifier, that was pretrained on unlabeled source and target data. ST uses that same unlabeled data again for pseudolabeling. As we demonstrate experimentally and thcoretically, this combination of methods improves substantially over each independently.
Datasets. For both UDA and SSL, we conduct experiments across eight benchmark datasets: four BREEDs datasets 772 Entity 13, Entity30. Nonliving26, Living17: FMoW [8] from WILDS
benchmark; Officehome 83); Visda (64 [3 and CIFAR-10 48] Each of these datasets consists of
domains, enabling us to construct source- source-target pairs (e.g., CIFAR10, we consider CIFARIO-CINIC shift (22)). In the UDA setup, we adopt the source and target domains standard to previous studies (details in App. C.2 Because the SSL setting lacks distribution shift, we do not need to worry about domain designations and default using source alone. To simulate limited supervision SSL we sub-sample the original labeled training set to 10%.
3

---

Table 1: Results the UDA setup. We report accuracy on target (OOD) data from which we only observe unlabeled examples during training. For benchmarks with multiple target distributions (e.g.. OH, Visda), we report avg accuracy on those targets. Results with source performance, individual target performance, and standard deviation numbers are in App.
Method
17
Nonliv26
Entity
Entity30
FMoW
Visda (2 igts)
OH
CIFAR- CINIC
Avg
(2 tgts)
(3 (gss))
HRM
60.31
45.54
68.32
55.75
56.50
20.91
9.51
74.33
48.90
ST
71.29
56.79
77.93
66.37
56.79
38.03
10.47
78.19
56.98
CL 74.14
57.02
76.58
66.01
61.78
63.49
22.63
77.51
62.39
STOC (ours)
82.22
62.23
81.84
72.00
65.25
70.08
27.12
79.94
67.59
Table 2: Results in the SSLssetp. We report accuracy on hold-out ID data. Recall that SSL uses labeled and unlabeled data from the same distribution during training. Refer to App. C.5 for ERM and ST.
Method
1i
Nonliv26
En 3
Entity30
FMo
Visda
OH
CIFAR
Avg
CL
91.15
84.58
90.73
85.47
43.05
97.67
49.73
91.78
79.27
STOC (ours)
92.00
85.95
91.27
86.14
44.43
97.70
49.95
93.06
80.06
Experimental Setup and Protocols. SwAV 13] is the specific algorithm that we use for contrastive pretraining. In all UDA settings. unless otherwise specified, we pool all the (unlabeled) data from the source and target to perform SwAV. For self-training, we apply FixMatch (79), where the loss on source labeled data and on pseudolabeled target data are minimized simultaneously. For both methods, we fix the segorrthm-speciffi hyperparameters to the original recommendations. For SSL settings, we perform SWAV and FixMatch on in-distribution unlabeled data. We experiment with Resnet18, Resnet50 42 trained from scratch (i.e. random initialization). We not consider off- the-shelf pretrained models (e.g., on Imagenet (68) to avoid confounding our conclusions about contrastive pretraining. However, we note that our results on most datasets tend to be comparable to and sometimes exceed those obtained with mmaggeNet-rrttriing with other methods (FixMatch, SwAV), we default to using strong augmentation techniques: random horizontal flips, random crops, augmentation with Cutout (24), and RandAugment (21). Moreover, unless otherwise specified, we default to full finetuning with source-only ERM, both from scratch and after contrastive pretraining, and for ST with FixMatch. For UDA, given that the setup precludes access to labeled data from the target distribution, we use source hold-out performance to pick the best hyperparameters. During pretraining, early stopping is done according to lower values of pretraining loss. For more details on datasets, model architectures, and experimental protocols, see App.
models. For source-only ERM, as
Results on UDA setup. Both ST and CL individually improve over ERM across all datasets, with CL significantly performing better than ST on out of 8 benchmarks (see Table I]. Even on datasets where ST is better than CL, their performance remains close. Combining ST and CL with STOC shows an 3-8% improvement over the best alternative, yielding an absolute improvement in average accuracy of 5.2%. Note that by default, we train with CL on the combined unlabeled data from source and target. However, to better understand the significance of unlabeled target data in contrastive pretraining, we perform an ablation where the CL model was trained solely on unlabeled source data (refer to this as CL (source only); see App. C.4). We observe that ST on top of CL (source only) improves over ST (from scratch). However, the average performance of ST over CL (source only) is similar to that of standalone CL, maintaining an approximate 6% performance gap observed between CL and ST. This brings two key insights to the fore: (i) the observed benefit is not merely a result of the contrastive pretraining objective alone, but specifically CL with unlabeled target data helps; and (ii) both CL and ST leverage using target unlabeled data in a complementary nature.
Results on SSL setup. While CL improves over ST (as in UDA), unlike UDA, STOC doesn't 't offer any significant improvements over CL (see Table 2 ERM and ST results (refer to App. C.5 We conduct ablation studies with varying proportions of labeled data used for SSL, illustrating that there's considerable potential for improvement (see App. C.5). These findings highlight that the complementary nature of STOC over CL and ST individually is artifact of distribution shift.

---

4 Theoretical Analysis and Intuitions
Our results on real-world datasets suggest that although self-training may offer little to no improve- ment over contrastive pretraining for in-distribution (i.e., SSL) settings, it leads to substantial im- provements when facing distribution shifts in UDA (Sec. B. Why do these methods offer comple- mentary gains, but only under distribution shifts? In this section, we seek to answer this question by first replicating all the empirical trends of interest a simple data distribution with an intuitive story (Sec. 4.1). In this toy model, we formally characterize the gains afforded by contrastive pretraining and self-training both individually (Secs. 4.2 and when used together (Sec. (44).
Data distribution We consider binary classification and model the inputs as consisting of two kinds of features: [ Zspl, where Tin E 1d the invariant feature that is predictive of the label across both source Ps and target PT and Tspp E Ee is the spurious feature that is correlated with the label y only on the source domain Ps but uncorrelated with label in Pr. Formally, we sample y Unif{- and generate inputs x conditioned on y as follows:
Ps Fin ~ N( yor,yw", Mmn) Esp yldop
PT: Tin ~ ~N (Ww("y"","" Ein) Zsp ~ -N(00, Exp).
(I)
where 7 is the margin afforded by the invariant feature" We set the covariance of the invariant features Ein = oh (Idi. w'w"T, This makes the variance along the latent predictive direction w" to be zero. Note that the spurious feature is also completely predictive of the label in the source data. In fact, when dep is sufficiently large, Tsp is more predictive (than Xin) of in the source. In the target, Tap is distributed as a Gaussian with Eup = JTg. We use Win "n==w=, ",,",,,.... .......0) 0]T to refer to the invariant direction/feature, and Wap
[O..... .... O, / / Vá.. for the spurious direction.
Data for UDA vs. SSL For convenience, we assume access to infinite unlabeled data and replace their empirical quantities with population counterparts, For SSL, we sample both finite labeled and infinite unlabeled data from the same distribution PT. where spurious features are absent (to exclude easy-to-generalize features). For UDA, we assume infinite labeled data from Ps and infinite unlabeled from PT. Importantly, note that due distribution shift, population access of Ps doesn't 't trivialize the problem as "ERM" on infinite labeled source data does not achieve optimal performance on target.
Methods and objectives Recall from Section 2 that we learn linear classifiers over feature extractor 4 For our toy setup, we consider linear feature extractors i.e. & is matrix in Rd and the prediction is given by sgn(h" (x)). We use the exponential loss {(f(z). v) exp (z))
Self-trainin. ST performs ERM in the first stage using labeled data from the source, and then subsequently updates the head h by iteratively generating pseudolabels on the unlabeled target:
(h; ④) = Ep 4x, sgn(g (x))))
ht - n Ch';
Update: h++1
| - V b)
For ERM and ST, we train both h and & (equivalent to & being identity and training linear head).
Contrastive pretraining. We obtain t. := arg ming Le ()) by minimizing the Barlow Twins objective [93]. which prior works have shown is also equivalent to spectral contrastive and non- contrastive objectives [33 [.. Given probability distribution Pa(a x)) for input x, and marginal PA. we consider a constrained form of Barlow Twins in (3) which enforces features of "positive pairs" a1 02 be close while ensuring feature diversity. We assume a strict regularization (p 0) for the theory arguments in the rest of the paper, and in App. D.2 we prove that all our claims hold for small o as well. For augmentations. we scale the magnitude of each co-ordinate uniformly by an independent amount, i.c., (- | æ) C x, where e ~ Unif 1]a. We try to mirror practical settings where the augmentations are fairly "generic", not encoding information about which features are invariant or spurious, and hence perturb all features symmetrically.
Lat ()) = Eg-P oa [b(a))
((2)))l
s.t. E o ((a)
I <
(3)
See App. D.I for similarities and differences of setup with prior works.
5

---

UDA setup
STOC vs. in UDA
STOC vs. CL
Effect of problem parameters
100
98.3
100
100
Target accaracy
80
79.4
00D Accuracy
80
Accuracy
80
00D Accuracy
80
ERM
60
STOC
CL
STOC
CL
60
ST
60
53.7
ERM
ERM
STOC
40
300
600
900
50 100
150
0.4 0.6 0.8
1.2 1.4 7/05pp
1.0
ERM ST
CL STOC
Cl. training epochs
CL. training spochs
(a)
(c)
Figure 2: Our simplified model of shift caplures real-world trends and theoretical behaviors: (a)
Target (OOD) accuracy separation in the UDA setup (for problem parameters in Example (b)
Comparison of the benefits of STOC (ST over CL) over just CL in UDA and SSL settings, done across training iterations for contrastive pretraining. (c) Comparison between different methods in UDA setting, we vary problem parameters y and sp. connecting our theory results in Sec.
Keeping the Pel fixed, we then learn linear classifier hel over &et to minimize the exponential loss on labeled source data (refer to linear probing). For STOC, keeping the Pet fixed and initializing the linear head with the CL linear probe (instead of source only ERM), we perform ST with (
Example 1. For the setup in ① we choose 7 0.5, oe 1., and of 0.05 with din 5 and dep 20 for our running example. aTp controls signal noise ratio in the source such that spurious feature is easy-to-learn and the invariant feature is harder-to-lear. d2 controls the noise in target which we show later is critical in unlearning the spurious feature with CL.
4.1 Simulations and Intuitive Story: A Comparative Study Between SSL and DA
Our setup captures real-world trends in UDA setting. Our toy setup (in Example T accentuates the behaviors observed on real-world datasets (Fig. 2 a)): (i) both ERM and ST yield close random performance (though ST performs slightly worse than ERM); (ii) CL improves over ERM but still yields sub-optimal target performance; (iii) STOC then further improves over CL, achieving near- optimal target performance. Note that, a linear predictor can improve target performance only by reducing its dependence on spurious feature Tap and increasing on invariant feature Tin (along w*). Given this, we can explain our trends if we understand the following: (i) how ST reduces dependence on spurious feature when done after CL; (ii) why CL helps reduce but not completely eliminate the reliance of linear head on spurious features. Before we present intuitions, we ablate over key problem parameter that affects both the target performance and conditions for ST to work.
Effect of 7/0ap on success of ST. By increasing the ratio of margin 7 and variance of spurious feature on target sp (keeping others constant), the problem becomes casier because y directly affects the signal on Zin and reducing Jap helps ST to unlearn Tap (see App. D.3) In Fig. (cc). we see that a phase transition occurs for ST. i.e., after a certain threshold of 7/ sp ST successtully recovers the optimal target predictor. This hints that ST has binary effect, where beyond certain magnitude of //Oop. ST can amplify the signal on domain invariant feature obtain optimal target predictor. On the other hand, the performance of CL and ERM improve gradually where CL achieves high performance even at small ratios of 7/Osp. One way of viewing this trend with CL is that it magnifies the effective 7//aap ap in its representation space, because of which a linear head trained these representations have a good performance
low values of the ratio. Consequently, the phase transition of STOC occurs much sooner then that of ST. Finally, we note that for CL the rate of performance increase diminishes at high values // because CL fails to reduce dependency along Tap beyond a certain point.
An intuitive story. We return to the question of why self-training improves over contrastive learning under distribution shift in our Example When the classifier initialization of ST relies more on spurious features, ST aggravates this dependency. However, as the problem becomes easier (with increasing 7//xp), the source-only ERM classifier will start relying more on invariant rather than spurious feature. Once this ERM classifier is sufficiently accurate on the target, ST unlearns any dependency on spurious features achieving optimal target performance.
contrast, we observe that CL performs better than ERM but is still sub-optimal. This implies that CL ends up decreasing reliance on spurious features (as compared to ERM) but doesn't completely eliminate them. Combining ST and CL, natural hypothesis explaining our trends is that CL provides "favorable" initialization

---

for ST by sufficiently increasing signal on invariant features. Our empirical findings emphasize an intriguing contrast suggesting that ST and CL improve target performance in complementary ways.
Why disparate behaviors for out-of-distributtion vs. in distribution? In the SSL setup, recall, there is no distribution shift. In Example [ we sample 50k unlabeled data and 100 labeled data from the same (target) distribution to simulate SSL setup. Substantiating our findings on real- world data, we observe that STOC provides a small to negligible improvement over CL (refer to App. D). To understand why such disparate behaviors emerge, recall that in the UDA setting, the main benefit of STOC lies in picking up reliance on "good" features for OOD data, facilitated by CL initialization. While contrastive pretraining uncovers features that are "good" for OOD data, it also learns more predictive source-only features (which are not predictive at all on target). As a result, linear probing with source-labeled data picks up these source-only features, leaving considerable room for improvement on OOD data with further self-tral erff-trainin. On the other hand, in the SSL setting, the limited IID labeled data might provide enough signal to pick up features predictive on Il) data, leaving little to no room for improvement for further self self-training. Corroborating our intuitions, throughout the CL training in the toy setup, when CL doesn't 't achieve near-perfect generalization, the improvements provided by STOC for each checkpoint remain minimal. On the other hand, for UDA setup, after reaching a certain training checkpoint in CL, STOC yields significant improvement (Fig. b)).
In the next sections, we formalize our intuitions and analyze why ST and CL offer complementary benefits when dealing with distribution shifts. Formal statements and proofs are in App.
4.2 Conditions for Success and Failure of Self-training over ERM from Scratch
In our results on Example 1 observe that performing ST after ERM yiclds classifier with near- random target accuracy. In Theorem 2 we characterize conditions under which ST fails and succeeds. Theorem 2 (Informal; Conditions for success and failure of ST over ERM). The target accuracy of ERM classifier, is given by 0.5 erfe (->"/(/2dn
Then ST performed in the second stage yields: (i) classifier with 0.5 target accuracy when Y < 3/20.p and aap 2 1; and (ii) classifier with near-perfect target accuracy when y B Osp-
The informal theorem above abstracts the exact dependency of 7, Jap, and dap for the success and failure of ST over ERM. Our analysis highlights that while ERM learns perfect predictor along win (with norm 7), it also learns to depend on Wsp (with norm /dap) because of the perfect correlation of Tap with labels on the source. Our conditions depict that when the a/ is sufficiently small, then ST continues to erroneously enhance its reliance on the Tap feature for target prediction, resulting in near-random target performance. Conversely, when 7/0spp is larger than 1, the signal in win is correctly used for predictor on the majority of target points, and ST climinates the Tap dependency, converging to an optimal target classifier.
Our proof analysis shows that if the ratio of the norm of the classifier along in the direction of w" smaller than Vep by a certain ratio then the generated pseudolabels (incorrectly) use Tsp for its prediction further increasing the component along Wssp- Moreover, normalization further diminishes the reliance along w",, culminating in near-random performance. The opposite occurs when the ERM classifier achieves signal along w" that is sufficiently stronger than along Wap- Upon substituting the parameters used in Example [ the ERM and ST performances as determined by Theorem 2 align with our empirical results, notably, ST performance on target being near-random.
4.3 CL Captures Both Features But Amplifies Invariant Over Spurious Features
Here we show that minimizing the contrastive loss 33 on unlabeled data from both Ps and PT gives us feature extractor Φ. that has a higher inner product with the invariant feature over the spurious feature. First, we derive a closed form expression for &el that holds for any linear backbone and augmentation distribution. Then, we introduce assumptions on the augmentation distribution (or cquivalently on w*) and other problem parameters, that are sufficient to prove amplification.
Proposition (Barlow Twins solution). The solution for B is U.T >T where Uş are the top l eigenvectors of Σ 1/2 E E>11 Here, ΣA := Ea-Pa J the covariance over augmentations, is the covariance matrix of mean augmentations a ()) [r)(s
and Σ =
The above result captures the effect of augmentations through the matrix Ug. If there were no augmentations, then ΣA- Σ, implying that U3 could then be any random orthonormal matrix. On
7

---

the other hand if augmentation distributions change prevalent covariances in the data, i.e., ΣA is very different from Σ, the matrix UR would bias the CL solution towards directions that capture significant variance in marginal distribution on augmented data, but have low conditional variance, when conditioned on original point precisely the directions with low invariance loss. Hence, we can expect that CL would learn components along both invariant Win and spurious Wep because: (i) these directions explain a large fraction of variance in the raw data; (ii) augmentations that randomly scale down dimensions would add little variance along Wap and Win compared to noise directions in their null space. On the other hand it is unclear which of these directions is amplified more in Pel- The following assumption and amplification result conveys that when the noise target (Asp) is suficiently large, the CL solution amplifies the invariant feature over the spurious feature.
Assumption 4 (Informal: Alignment of w" with augmentations). We assume that wn aligns with Pa(: I)) i.e., Vx, Ba|z [aww] w"] 1/2 x diag( (1a) w is high. Hence, we assume w -lan///am /am.
One implication of Assumption 4 is that when w" Jam/VVm. only the top two eigenvectors lie in the space spanned by Win and Wapp- To analyze amplification with fewer eigenvectors from Proposition 3 while retaining all relevant phenomena, we assume w- = /u///din for mathematical convenience. While Assumption 4 permits a tighter theoretical analysis, our empirical results in Sec. 4.1 hold more generally for w (V.,
Theorem 5 (Informal; CL recovers both win and d'sp but amplifies win). Under Assumption + the CL solution [01, $2,.... (b)] satisfies ob} Win Qj Wap 0 Vjj > 3, di = cywinn + C33Usp and Φ2 C2llin + Callepp- For constants K1, K2 0, 7 KiKa/o.p dap o K3. Ve O, 30 such that for Jap e Jspa |s/ea- - K, /K3dm/22o0. (dm -1) & e, and ||ss/ca| L ad//// < e, where L = 1 K3.
We analyze the amplification of Win/ /upp with contrastive learning in the regime where Cap is large enough. In other words, if the target distribution has sufficient noise along the spurious feature, the augmentations prevent the CL solution from extracting components along Wap. Thus, in our analysis, we first analyze the amplification factors asymptotically (aap - 00), and then use the asymptotic behavior to draw conclusions for the regime where ssp is large but finite.
Theorem 5 conveys two results: (i) CL recovers components along both Win and Wap through 11, Φ2 and (ii) it increases the norm along Win more than Wap- The latter is evident because the margin separating labeled points along Win is now amplified by factor of |ca/cal
/(//))//)) in Φ2. Naturally, this will improve the target performance of a linear predictor trained over CL representations. At the same time, also see that in Φ1. the component along W'sp is still significant (e//ss = O(YLo,,)) Intuitively, CL prefers the invariant feature since augmentations amplify the noise along Wepp in the target domain. At the same time, the variance induced by augmentations along Wsp in source is still very small due to which the dependence on Wap is not completely alleviated. Due to the remaining components along Wap. the target performance for CL can remain less than ideal. Both the above arguments on target performance are captured in Corollary 6
Corollary 6 (Informal; CL improves OOD error over ERM but is still imperfect). For 71, app dap de- fined as in Theorem 5 30sp1 such that for all aap 2 Jsp1 the target accuracy of CL (linear predictor on aa) is 3/ 0.5 (- Tl' -1(/)))))))))) and & 0.5 erfc (-AT' 7//22m)), where T!' K3 K3Kija i (o))) When Dsp1 > Jin
1/dua, the lower bound on accuracy is strictly better than ERM from scratch.
While P is still not ideal for linear probing, in the next part we will see how P can instead be sufficient for subsequent self-training to unlearn the remaining components along spurious features.
4.4 Improvements with Self-training Over Contrastive Learning
The result in the previous section highlights that while CL may improve over ERM, the linear probe continues to depend on the spurious feature. Next, we characterize the behavior STOC. Recall, in the ST stage, we iteratively update the linear head with (2) starting with the CL backbone and head.
Theorem 7 (Informal; ST improves over CL). Under the conditions of Theorem 5 and dep &
K7- k the target accuracy of ST over CL is lower bounded by 0.5 erfe (- |(2/cs] 7/(22))) 2 0.5 erfe (-Iv Lv
(V2)))))))) where 02 and C4 are the coefficients of feature d2 along win and Wap learned by BT.
8

---

The above theorem states that when Vdn/aan > 1 the target accuracy of ST over CL is close to 1. In Example the lower bound of the accuracy of ST over CL is erfe (-v10) 2 showing near- perfect target generalization. Recall that Theorem showss that CL yields a linear head that mainly depends on both the invariant direction Win and the spurious direction Wsp- At initialization, the linear head trained on the CL backbone has negligible dependence on Φ2 (under conditions in Theorem [ Building on that, the analysis in Theorem 7 captures that ST gradually reduces the dependence on Wsp by learning a linear head that has a larger reliance on ch2, which has a higher "effective" margin on the target, thus increasing overall dependency Win-
Theoretical comparison with SSL. Our analysis until now shows that linear probing with source labeled data during CL picks up features that are more predictive of source label under distribution shift, leaving a significant room for improvement on OOD data when self-trained further. In UDA, the primary benefit of ST lies in picking up the features with a high "effective" margin on target data that are not picked up by linear head trained during CL. In contrast, in the SSL setting, the limited ID labeled data may provide enough signal in picking up high-margin features that are predictive on ID data, leaving little to no room for improvement for further ST. We formalize this intuition in App. E
4.5 Reconciling Practice: Implications for Deep Non-Linear Networks
In this section, we experiment with deep non-linear backbone (i.e., Pe1). When we continue to fix Pat during CL and STOC, the trends we observed with linear networks in Sec. [.]] continue to hold. We then perform full fine-tuning with CL and STOC, i.e., propagate gradients even to Fel. as commonly done in practice. We present key takeaways here but detailed experiments are in App. D.4
Benefits of augmentation for self-training. ST while updating del can hurt due to overfitting issues when training with the finite sample of labeled and unlabeled data (drop by >10% over CL). This is due to the ability of deep networks to overfit on confident but incorrect pseudolabels on target data (94). This exacerbates components along Wap and we find that augmentations (and other heuristics) typically used in practice (e.g. in FixMatch (79] help avoid overfitting on incorrect pscudolabels.
Can ERM and ST over contrastive pretraining improve features? We find that self-training can also slightly improve features when we update the backbone with the second stage of STOC and when the CL backbone is early stopped sub-optimally (i.e. at earlier checkpoint in Fig. (b)) This feature finetuning can now widen the gap between STOC and CL in SSL settings, as compared to the linear probing gap (as in 2) This is because STOC can now improve performance beyond just recovering the generalization gap for the linear head (which is typically small). However, STOC benefits are negligible when CL is not early stopped sub-optimally, i.e., trained till convergence. Thus. it remains unclear if STOC and CL have complementary benefits for feature learning in UDA or SSL settings. Investigating this is an interesting avenue for future work.
5 Connecting Experimental Gains with Theoretical Insights
Our theory emphasizes that under distribution shift con- trastive pretraining improves the representations for target data, while self-training primarily improves linear classi- fiers learned on top. To investigate different methods in our UDA setup, we study the representations learned by each of them. We fix the representations and train linear heads over them to answer two questions: (i) How good are the representations in terms of their ceiling of target accuracy (performance of the optimal linear probe)?- we evaluate this by training the classifier head on target la- beled data (i.e., target linear probe); and (ii) How well do heads trained on source generalize to target?- assess this by training head on source labeled data (source lin- ear probe) and evaluate its difference with target linear probe. For both, we plot target accuracy. We make two intriguing observations Fig.
Transfer with linear probe
80
ERM
79.480.7
Target Accuracy
70
STOC
65.3
67.1
63.3
60
57.0
59.7
50
49.0
Source probe
Target probe
Figure 3: Target accuracy with source and target linear probes, which freezes backbones trained with various objec- tives and trains only the head in UDA setup. Avg. accuracy across all datasets. We observe that: (i) ST improves the lin- ear transferability of source probes, and (ii) CL improves representations.
Does CL improve representations over ERM features?
Yes. We observe a substantial difference in accuracy (* 14% gap) of target linear probes on backbones trained

---

with contrastive pretraining (i.e. CL, STOC) and without it (i.e., ERM, ST) highlighting that CL significantly pushes the performance ceiling over non-contrastive features. As side, our findings also stand in contrast to recent studies suggesting that ERM features might be "good enough" for OOD
generalization (67 46]. Instead, the observed gains with contrastively pretrained backhones (i.e. CL. STOC) demonstrate that target unlabeled data can be leveraged to further improve over ERM features.
Do CL features yield perfect linear transferability from source to target? Recent works 40 76 conjecture that under certain conditions CL representations, linear probes learned with source labeled data may transfer perfectly from souree to target. However, we observe that this doesn't ''t hold strictly in practice, and in fact, the linear transferability can be further improved with ST. We first note a significant gap between the performance of source linear probes and target linear probes illustrating that linear transferability is not perfect in practice. Moreover, while the accuracy of target linear probes doesn't I change substantially between CL. and STOC, the accuracy of the source linear probe improves significantly. Similar observations hold for ERM and ST, methods trained without contrastive pretraining. This highlights that ST performs "feature refinement" to improve source to target linear transfer (with relatively small improvements in their respective target probe performance). The findings highlight the complementary nature of benefits on real-world data: ST improves linear transferability while CL improves representations.
6 Connections to Prior Work
Our empirical results and our analyses offer a perspective that contrasts with the prior literature that argues for the individual optimality of contrastive pretraining and self-training. We outline the key differences from existing studies here, and delve into other related works in App.
Limitations of prior work analyzing contrastive learning Prior works 40, 76 analyzing CL first make assumptions the consistency of augmentations with labels [39]
11 73 44], and specifically
for UDA make stronger ones on the augmentation graph connecting examples from same domain or ones. While this is sufficient prove linear transferability,
class more than cross-clas//eros-domee it is unclear if this holds in practice when augmentations are imperfect, i.e. if they fail to mask the spurious features completely- in our simplified setup in App. F.I
corroborated by findings in Sec. 5 We show why this also fails
Limitations of prior work analyzing self-training Prior research views self-training as consistency regularization, ensuring pseudolabels for original samples align with their augmentations [22 87 79). This approach abstracts the role played by the optimization algorithm and instead evaluates the global minimizer of a population objective promoting pseudolabel consistency. It also relies on specific assumptions about class-conditional distributions to guarantee pseudolabel accuracy across domains. However, this framework doesn't address issues in iterative label propagation. For example, when augmentation distribution has long tails, the consistency of pseudolabels depends on the sampling frequency of "favorable" augmentations (for more discussion see App. F.2) Our analysis thus follows the iterative examination of self-training [17
Conclusion
In this study, we highlight the synergistic behavior of self-training and contrastive pretraining under distribution shift. Shifts in distribution are commonplace in real-world applications of machine learn- ing, and even under natural, adversaaaali distribution shifts, the performance of machine learning models often drops. By simply combining existing techniques in self-training and constrastive learn- ing, we find that we can improve accuracy by 3-8% rather than using either approach independently. Despite these significant improvements, we note that one limitation of this combined approach is that performing self-training sequentially after contrastive pretraining increases the computation cost for UDA. The potential for integrating these benefits into one unified training paradigm is yet unclear, presenting an interesting direction for future exploration.
Beyond this, we note that our theoretical framework primarily confines the analysis to training the backbone and linear network independently during the pretraining and time-tunin//sef--taaittee phases. Although our empirical observations apply to deep networks with full fine-tuning, we leave a more rigorous theoretical study of full fine-tuning for future work. Our theory also relies on a covariate shift assumption (where we assume that label distribution also doesn't 't shift). Investigating the complementary nature of self-training and contrastive pretraining beyond the covariate shift assumption would be another interesting direction for future work.
10

---

Acknowledgements
SG acknowledges the JP Morgan Al Ph.D. Fellowship and Bloomberg Ph.D. Fellowship for their support.
References
[1] Alexandari, A., Kundaje, A., and Shrikumar, A. (2021). Adapting label shift with bias- corrected calibration. In International Conference on Machine Learning (ICML).
[2] Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N. (2019). A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.0922.
[3] Azizzadenesheli, K., Liu, A., Yang, F,, and Anandkumar, A. (2019). Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations (ICLR).
[4] Bardes, A., Ponce, J., and LeCun, Y. (2021). Vicreg: Variance-ivaarane--ovvaaann regulariza- tion for sele-supervieed learning. arXiv preprint arXiv:2105.04900
[5] Baricz, A. (2008). Mills' ratio: Monotonicity patterns and functional inequalities. Journal of Mathematical Analysis and Applications, 140(2):132213770
[6] Bekker, J. and Davis, J. (2020), Learning from positive and unlabeled data: a survey. Machine Learning.
[7] Ben-David, S., Lu. T., Luu, T., and Pál, D. (2010). Impossibility Theorems for Domain Adaptation. International Conference on Artificial Intelligence and Statistics (AISTATS).
[8] Berthelot, D., Carlini, N., Cubuk, E. D., Kurakin, A., Sohn, K., Zhang, H., and Raffel, C. (2019). Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring. arXiv preprint 1xXiv:1911.09785.
[9] Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
[10] Blanchard, G., Lee, G., and Scott, C. (2011). Generalizing from several related classification tasks unlabeled sample. Advances in neural information processing systems, 24.
[11] Cabannes, V., Kiani, B. T., Balestriero, R.,
LeCun, Y., and Bietti, A. (2023). The ssi interplay: Augmentations, inductive bias, and generalization. arXiv preprint 2r2.::2302.02777.
[12] Cai. T., Gao, R., Lee, J., and Lei, Q. (2021). A theory of label propagation for subpopulation shift. In International Conference Machine Learning, pages 1170-1182 PMLR.
[13] Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., and Joulin, A. (2020). Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systems, 23:9912-9922
[14] Caron, M., Touvron, H., Misra, I., Jégou, H., Mairal, J., Bojanowski, P., and Joulin, A. (2021). Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF international conference computer vision, pages 9650-9660.
[15] Chapelle, O., Scholkopf, B., and Zien, A. (2006). Semi-supervised learning. 2006. Cambridge, Massachusettes: The MIT Press View Article, 2.
[16] Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. (2020a). simple framework for contrastive learning of visual representations. In International conference machine learning, pages 1597-1607, PMLR.
[17] Chen, X., Chen, W., Chen, T., Yuan, Y., Gong, C.,, Chen, K., and Wang, Z. (2020b). Self-pu: Self boosted and calibrated positive-unlabeles training. International Conference on Machine Learning, pages 1510-1519, PMLR.

---

[18] Christie, G., Fendley, N., Wilson, J., and Mukherjee, R. (2018). Functional map of the world. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
[19] Cortes, C., Mansour, Y., and Mohri, M. (2010). Learning Bounds for Importance Weighting, In Advances in Neural Information Processing Systems (NIPS).
[20] Cortes, C. and Mohri, M. (2014). Domain adaptation and sample bias correction theory and algorithm for regression. Theoretical Computer Science, 519.
[21] Cubuk, E. D., Zoph, B., Shlens, J., and Le, Q. V. (2020). Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition workshops, pages 702-703.
[22] Darlow, L. N.. Crowley, E. J., Antoniou, A., and Storkey, A. J. (2018). Cinic-10 10 is not imagenet or cifar-10. arXiv preprint arXiv:1810.03505.
[23] Deledalle, C.-A., Denis, L., Tabti, S., and Tupin, F. (2017). Closed-form expressions of the eigen decomposition of x and 3 Hermitian matrices. PhD thesis, Université de Lyon.
[24] DeVries, T. and Taylor, G. W. (2017). Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:1708.0455:
[25] Elkan, C. and Noto, K. (2008). Learning classifiers from only positive and unlabeled data. In International Conference Knowledge Discovery and Data Mining (KDD), pages 213-22122 213-220.
[26] Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., Marchand, M. and Lempitsky, V. (2016). Domain-adversarial training of neural networks. The journal of machine learning research.
[27] Gardner, J., Pleiss, G., Weinberger, K. Q., Bindel, D., and Wilson, A. G. (2018). Gpytorch: Blackbox
gaussian process inference with gpu acceleration. In Advances Neural Information Processing Systems (NeurIPS).
[28] Garg, S., Balakrishnan, S., and Lipton, Z. (2022a). Domain adaptation under open set label shift. In Advances in Neural Information Processing Systems (NeurIPS).
[29] Garg, S., Balakrishnan, S., Lipton, Z., Neyshabur, B., and Sedghi, H. (2022b). Leveraging unlabeled data to predict dut-o--disttibution performmmneeepnnrnnememeoo performance. In International Conference on Learning Representations (ICLR).
[30] Garg. S., Erickson, N., Sharpnack, J., Smola, A., Balakrishnan, S., and Lipton, Z. (2023). Risbench: A large-scale empirical study of domain adaptation under relaxed label shift. In International Conference on Machine Learning (ICML).
[31] Garg, S., Wu, Y., Balakrishnan, S., and Lipton, Z. (2020). A unified view of label shift estimation. Advances in Neural Information Processing Systems (NeurIPS).
[32] Garg, S., Wu, Y., Smola, A., Balakrishnan, S., and Lipton, Z. (2021). Mixture proportion estimation and PU learning: A modern approach. In Advances Neural Information Processing Systems (NeurIPS).
[33] Garrido, Q., Chen, Y., Bardes, A., Najman, L., and Lecun, Y. (2022). On the duality between contrastive and non-contrastive self-supervised learning. arXiv preprint arXiv:2206.02574
[34] Grandvalet, Y. and Bengio, Y. (2006). Entropy regularization.
[35] Gretton, A., Smola, A. J., Huang, J., Schmittfull, M., Borgwardt, K. M., and Schölkopf, B. (2009). Covariate Shift by Kernel Mean Matching. Journal of Machine Learning Research (JMLR).
[36] Grill, J.-B., Strub, F,, Altché, F,, Tallec, C., Richemond, P., Buchatskaya, E., Doersch, C., Avila Pires, B., Guo, Z.,, Gheshlaghi Azar, M., et al. (2020). Bootstrap your own latent-a new approach to self-supervised learning. Advances in neural information processing systems, 33:21271-21221
12

---

[37] Gulrajani. I. and Lopez-Paz, D. (2020). In search of lost domain generalization. arXiv preprint 01X1442007.11434
[38] HaoChen, J. Z. and Ma, T. (2022). theoretical study inductive biases in contrastive learning. arXiv preprint arXiv:2211.14699
[39] HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, (2021). Provable guarantees for self-supervieed deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-5011.
[40] HaoChen, J. Z.,, Wei, C., Kumar, A., and Ma, (2022). Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. arXiv preprint arXiv:2204.0000 026833
[41] He, K. Fan, H., Wu, Y. Xie, S., and Girshick, R. (2020). Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729-9738.
[42] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep Residual Learning for Image Recognition. Computer Vision and Pattern Recognition (CVPR).
[43] Joachims, T. et al. (1999). Transductive inference for text classification using support vector machines. In Ieml, volume 99, pages 200-209.
[44] Johnson, D. D., Hanchi, A. E., and Maddison, J. (2022). Contrastive learning can find an optimal basis for approximately view-invariant functions. arXiv preprint arXiv:2210.01883
[45] Kakade, S. M., Sridharan, K., and Tewari, A. (2008). On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in neural information processing systems, 21.
[46] Kirichenko, P., Izmailov, P., and Wilson, A. G. (2022). Last layer re-trinning is sufficient for robustness to spurious correlations. arXiv preprint ar arXiv:2204.02937.
[47] Koh, P. W. Sagawa, S., Marklund, H., Xie, S. M., Zhang, M.. Balsubramani, A., Hu, W., Yasunaga, M., Phillips, R. L.,, Gao, I., Lee, T., David, E., Stavness, I., Guo, W., Earnshaw, B. A., Haque, I. S., Beery, S., Leskovee, J., Kundaje, A., Pierson, E., Levine, S., Finn, C., and Liang, P. (2021). WILDS: A benchmark of in-the-wild distribution shifts. International Conference on Machine Learning (ICML).
[48] Krizhevsky, A. and Hinton, G. (2009). Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer.
[49] Kschischang, F. R. (2017). The complementary error function. Online, April.
[50] Kumar, A., Ma, T., and Liang, P. (2020). Understanding self-training for gradual domain adaptation. In International Conference on Machine Learning, pages 5468-5479. PMLR.
[51] Kumar, A., Raghunathan, A., Jones, R. M., Ma, T., and Liang, P. (2022). Fine-tuning can distort pretrained features and underperform -ut-of-distribution. In International Conference on Learning Representations.
[52] Lee, D.-H. et al. (2013). Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, page 896.
[53] Lipton, Z. C., Wang, Y.-X., and Smola, A. (2018). Detecting and Correcting for Label Shift with Black Box Predictors. International Conference on Machine Learning (ICML).
[54] Long, M., Cao, Y., Wang, J., and Jordan, M. (2015). Learning transferable features with deep adaptation networks. International conference on machine learning, pages 97-105, PMLR.
[55] Long, M., Zhu, H., Wang, J., and Jordan, M. (2017). Deep transfer learning with joint adaptation networks. In International conference machine learning. PMLR.
13

---

[56] Loshchilov, I. and Hutter, F. (2016). Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint a60iv 033883.
[57] Ma, M. Q.. Tsai, Y.-H. H., Liang, P. P., Zhao, H., Zhang, K., Salakhutdinov, R., and Morency, L.-P. (2021). Conditional contrastive learning for improving fairness in self-supervised learning. arXiv preprint arXiv:2106.02866
[58] Mishra, S., Saenko, K., and Saligrama, V. (2021). Surprisingly simple semi-supervised domain adaptation with pretraining and consistency. arXiv preprint arXiv:2101.12727.
[59] Muandet, K., Balduzzi, D., and Schölkopf, B. (2013). Domain generalization via invariant feature representation. In International Conference Machine Learning, pages 10-18. PMLR.
[60] Nagarajan, V., Andreassen, A., and Neyshabur, B. (2020). Understanding the failure modes of nuttof-disttrbuttin generalization. arXiv preprint arXiv:2010.15775.
[61] Oord, A. v. d., Li, Y., and Vinyals. O. (2018). Representation learning with contrastive predictive coding. arXiv preprint Nttd:3880.03777
[62] Peng, X., Bai, Q. Xia, X., Huang, Z., Saenko, K., and Wang. B. (2019). Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF international conference computer vision, pages 1406-1415.
[63] Peng, X., Usman, B., Kaushik, N., Hoffman, J., Wang, D., and Saenko, K. (2017). Visda: The visual domain adaptation challenge.
[64] Peng, X., Usman, B., Saito, K., Kaushik, N., Hoffman, J., and Saenko, K. (2018). Syn2real: new benchmark forsynthetic-to-rell visual domain adaptation. arXiv preprint arXiv: 180600977
[65] Quinonero-Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D. (2008). Dataset shift in machine learning. Mit Press.
[66] Roberts, M., Mani, P., Garg, S., and Lipton, Z. (2022). Unsupervised learning under latent label shift. In Advances in Neural Information Processing Systems (NeurIPS).
[67] Rosenfeld, E., Ravikumar, P., and Risteski, A. (2022). Domain-adjusted regression or: Erm may already learn features sufficient for out-of-distribution generalization. arXiv preprint 0rXiv:2202.06856.
[68] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. (2015). Imagenet large scale visual recognition challenge. International journal of computer vision, 11 11(3))211-252.
[69] Saerens, M., Latinne, P., and Decaestecker, C. (2002). Adjusting the Outputs of Classifier to New a Priori Probabilities: A Simple Procedure. Neural Computation.
[70] Sagawa, S., Koh, P. W., Lee, T., Gao, I., Xie, S. M., Shen, K., Kumar, A., Hu, W., Yasunaga, M., Marklund, H., Beery, S., David, E., Stavness, I., Guo, W., Leskovec, J., Saenko, K., Hashimoto, T., Levine, S., Finn, C., and Liang, P. (2021). Extending the wilds benchmark for unsupervised adaptation. In NeurIPS Workshop on Distribution Shifts.
[71] Sagawa, S., Raghunathan, A., Koh, W., and Liang, P. (2020). An investigation of why overparameterizzation exacerbates spurious correlations. In International Conference on Machine Learning, pages 8346-8356. PMLR.
[72] Santurkar, S., Tsipras, D., and Madry, A. (2021). Breeds: Benchmarks for subpopulation shift. In International Conference Learning Representations (ICLR).
[73] Saunshi, N., Ash. J.. Goel, S., Misra, D., Zhang, C., Arora, S., Kakade, S., and Krishnamurthy, A. (2022). Understanding contrastive learning requires incorporating inductive biases. In International Conference on Machine Learning, pages 99250-19286 PMLR.
(74] Schölkopf, B., Janzing, D., Peters, J., Sgouritsa, F.,, Zhang, K., and Mooij, J. (2012). On Causal and Anticausal Learning. In International Conference Machine Learning (ICML).
14

---

[75] Scudder, H. (1965). Probability of error of some adaptive mattem-recogninn machines. 1EEE Transactions on Information Theory. 11(3):363-371
[76] Shen, K., Jones, R. M., Kumar, A., Xie, S. M., HaoChen, Z., Ma, T., and Liang, P. (2022). Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. In International Conference on Machine Learning, pages 19847-19878. PMLR.
[77] Shimodaira, H. (2000). Improving Predictive Inference Under Covariate Shift by Weighting the Log-Likelihood Function. Journal of Statistical Planning and Inference.
[78] Shu, R., Bui, H. H., Narui, H., and Ermon, S. (2018). A dirt-t approach unsupervised domain adaptation. arXiv preprint arXiv:1802.0877
[79] Sohn, K., Berthelot, D., Carlini, N., Zhang. 7.,, Zhang, H., Raffel, C. A., Cubuk, F. D., Kurakin, A., and Li, C.-L. (2020). Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances Neural Information Processing Systems, 33.
[80] Stewart, G. W. (1993). On the early history of the singular value decomposition. SIAM review, 35(4):551-566.
[81] Sun, B., Feng, J., and Saenko, K. (2017). Correlation alignment for unsupervised domain adaptation. In Domain Adaptation in Computer Vision Applications. Springer.
[82] Sun, B. and Saenko, K. (2016). Deep coral: Correlation alignment for deep domain adaptation. In European conference on computer vision. Springer.
[83] Torralba, A. and Efros, (2011). Unbiased look at dataset bias. In CVPR 2011, pages 1521-1528. IEEE.
[84] Van Engelen, J. E. and Hoos, H. H. (2020). A survey semi-supervised learning. Machine learning, 109(2))373-440
[85] Venkateswara, H.. Eusebio, J., Chakraborty, S., and Panchanathan, S. (2017). Deep hashing network for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5018-5027.
[86] Wang, D., Shelhamer, E., Liu, S., Olshausen, B., and Darrell, T. (2021). Tent: Fully test-time adaptation by entropy minimization. In International Conference on Learning Representations.
[87] Wei, C., Shen, K., Chen, Y., and Ma. T. (2020). Theoretical analysis of self-training with deep networks unlabeled data. arXiv preprint 22X:v22010.03622.
[88] Wu, Z., Xiong, Y.. Yu, S. X., and Lin, D. (2018). Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733-3742.
[89] Xie, Q., Luong, M.-T., Hovy, E., and Le, Q. V. (2020a). Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 10687-10698.
[90] Xie, x., Chen, J., Li, Y., Shen, L., Ma, K., and Zheng, Y. (2020b). Self-supervised cyclegan for object-preserving image-to-imee domain adaptation. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23 23-28, 2020, Proceedings, Part XX 16, pages 498- 513. Springer.
[91] Yang. X., Song, Z., King, I., and Xu, Z. (2022). survey on deep semi-supervised learning. IEEE Transactions Knowledge and Data Engineering.
[92] Zadrozny, B. (2004). Learning and Evaluating Classifiers Under Sample Selection Bias. In International Conference on Machine Learning (ICML).
[93] Zbontar, J., Jing, L., Misra, I., LeCun, Y., and Deny, S. (2021). Barlow twins: Self-supervised learning via redundancy reduction. International Conference on Machine Learning, pages 13300- PMLR.
15

---

[94] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2017). Understanding deep learn- ing requires rethinking generalization. In International Conference on Learning Representations (ICIR).
[95] Zhang, J., Menon, A.. Veit, A., Bhojanapalli, S., Kumar, S., and Sra, S. (2021). Coping with label shift via distributionally robust optimisation. In International Conference on Learning Representations (ICLR).
[96] Zhang. K., Schölkopf, B., Muandet, K., and Wang. Z. (2013). Domain Adaptation Under Target and Conditional Shift. In International Conference on Machine Learning (ICML).
[97] Zhang, R. (2019). Making convolutional networks shift-invariant again. In ICML.
[98] Zhang, W., Ouyang, W., Li, W., and Xu, D. (2018). Collaborative and adversarial network for unsupervised domain adaptation. In Proceedings of the IEEE conference on computer vision and pattern recognition.
[99] Zhang. Y., Liu, T., Long, M., and Jordan, M. (2019). Bridging theory and algorithm for domain adaptation. In International Conference on Machine Learning. PMLR.
[100] Zhu, X. and Ghahramani, Z. (2003). Learning from labeled and unlabeled data with label propagation. CMU CALD tech report CMU-CALD-02-107, 2002.
16

---

Appendix
Appendix Table of Contents
Other Related Works
17
More Details Problem Setup
18
Additional Experiments and Details
19
C.1
Additional setup and notation
19
Dataset details
19
Method details
20
C.4
Additional UDA experiments
22
Additional SSL experiments
23
C.6
Other experimental details
23
D
Additional Results in Toy Setup
23
D.I
Detailed description of our simplified setup
23
D.2
Discussion on self seff-training and contrastive learning objectives
25
D.3
Additional empirical results in our simplified setup
26
D.4
Reconciling Practice: Experiments with deep networks toy setup
27
Formal Statements from Sec.
29
E.1
Analysis of ERM and ST: Formal Statement of Theorem
29
E.I.1
Proof of Proposition
34
E.1.2
Analysis with >
in Contrastive Pretramiigg Objective
36
1.3
Proof of Theorem
38
E. 4.1.4
1.4
Proof of Corollary
41
Analysis of STOC: Formal Statement of Theorem
E.3
Analysis for SSL
48
L
Limitations of Prior Work
48
Contrastive learning analysis
48
F2
Self-training analysis
48
Additional Lemmas
49
A Other Related Works
Unsupervised domain adaption. Without assumption on the nature of shift, UDA is underspeci- fied [7]. This challenge has been addressed in various ways by researchers. One approach is inves-
tigate additional structural assumptions under which UDA problems are well posed [7
74]. Popular
settings for which DA well-posed include (i) covariate shift (96] 92
19
20
35
where p x:) can
change from source to target but p(y]ar) remains invariant; and (ii) label shift 69 53
95 66
30 where the label marginal p(y) can change but p(æly) is shared across source and target. Princi-
pled methods with strong theoretical guarantees exists for adaptation under these settings when target
17

---

distribution's 's support is subset of the source support. Other works [25] 6 32 28 extend the label shift setting to scenarios where previously unseen classes may appear in the target and p(rly) remains invariant among seen classes. A complementary line of research focuses on constructing benchmarks to develop heuristics for incorporating the unlabeled target data, relying on benchmark datasets os-
tensibly representative of "real-world shifts" to adjudicate progress 722 85 70
62
63 As result, 26
various benchmark-drivee heuristics have been proposed [54] 55, 82 81
99
98
79 Our work
engages with the latter, focusing two popular methods: self-training and contrastive pretraining.
Domain generalization. In domain generalization, the model is given access to data from multiple different domains and the goal is to generalize to a previously unseen domain at test time [IO] [3]. For survey of different algorithms for domain generalization, we refer the reader Gulrajani and Lopez-Paz (37. A crucial distinction here is that unlike the domain generalization setting, in DA problems, we have access to unlabeled examples from the test domain.
Semi-supervised learning. To learn from a small amount of labeled supervision, semi-supervised learning methods leverage unlabeled data alongside improve learning models. One of the seminal works in SSL is the pscudolabeling method [75]. where a classifier is trained on the labeled data and then used classify the unlabeled data, which are then added the training set. The work of Zhu and Ghahramani [TO0] built on this by introducing graph-based methods, and the transductive SVMs 43 presented an SVM-based approach. More recent works have focused on deep learning techniques. and similar to UDA, self-training and contrastive pretraining have emerged as two prominent choices. We delve into these methods in greater detail in the following paragraphs. For a discussion on other SSL methods, we refer interested readers to 15
91
Self-training. Two popular forms of self-training are pseudolabeling
[52
and conditional entropy
minimization [34], which have been observed to be closely connected [8
52
79
78 Motivated
by its strong performance in SSL and UDA settings [79
89
30
78 several theoretical works have
made attempts to understand its behavior [50] 87 17
88
12 aims to understand the behavior of
the global minimizer of self-training objective by studying input consistency regularization, which enforces stability of the prediction for different augmentations of the unlabeled data. Our analysis of self training motivated by the work of Chen al. [17] which explores the iterative behavior of self-training to unlearn spurious features. The setting of spurious features is of particular interest, since prior works have specifically analyzed the failures of -ut-r--diitributiinn generalization in the presence of spurious features 660 71
Contrastive learning. An alternate line of work that unlabeled data for learning representations in the pretraining stage is contrastive learning [36] 61
[3 16 88). Given an augmentation distribution, the main goal of contrastive objectives is map augmentations drawn from the same input (positive pairs) to similar features, and force apart features corresponding to augmentations of different inputs (negative pairs)
Prior works contrastive [6] 39 and non contraaste objectives 4 133. Consequently, in our analysis pertaining to the toy setup we focus on the mathematically non-contrastive objective Barlow Twins (93). Using this pretrained backbone (either as an initialization or as fixed feature extractor) downstream predictor have analyzed the in-distribution generalization of the downstream predictor via label consistency arguments on the graph of positive pairs (augmentation graph). contrast, we study the impact of contrastive learning under distribution shifts in the UDA setup. Other works 776 40 that examine contrastive learning for UDA also conform to the augmentation graph view point, making additional assumptions that guarantee linear transferability. In our simplified setup involving spurious correlations, these abstract assumptions break easily when the augmentations are of generic nature, akin to practice. Finally, some empirical works (58) (7) have found self- supervisdd objectives like contrastive pretraining reduce dependence on spurious correlations. Corroborating their findings, we extensively evaluate the complementary benefits of contrastive learning and self-training on real-world datasets. Finding differing results in SSL and UDA settings, we further examine their behavior theoretically in our toy setup.
13
38 have also shown a close relationship between
learned using labeled examples. Several works [39 73 38
B More Details on Problem Setup
In this section, we elaborate on setup and methods studied in our work.
18

---

Unsupervised Domain Adaptation (UDA). We assume that we are given labeled data from the source distribution and unlabeled data from a shifted, targer distribution, with the goal of performing well on target data. We assume that the source and target distributions have the same label marginals Ps(y) Pr(y) (i.e., no label proportion shift) and the same Bayes optimal predictor, Le., arg max,, y (5 .)) = arg max, PT a.. Here, even with infinite labeled source data, the challenge lies in generalizing out-of-distribution In experiments, we assume access to finite data but in theory, we assume population access to labeled source and unlabeled target.
Semi-Supervised Learning (SSL). Here, there is no distribution shift, ie., Ps PT Pu. We are given a small number of labeled examples and a comparatively large amount of unlabeled examples, both drawn from the same distribution. Without loss of generality, we denote this distribution with PT. The goal in SSL is to generalize in-distribution. The challenge is primarily due to limited access to labeled data. Here, in experiments, we assume limited access to labeled data but comparatively larger amount of unlabeled in-distribution data. In theory, we assume population access to unlabeled data but limited labeled examples.
Methods. As discussed in the main paper, we compare four methods for learning with labeled and unlabeled data. Tableß summarizes the main methods and key differences between those methods in UDA and SSL setup. For exact implementation in our experiments, we refer reader to App. C.3
C Additional Experiments and Details
C.1 Additional setup and notation
Recall, our goal is to learn a predictor that maps inputs x X S Ie to outputs y E y. We parameterize predictors f o $ Rd - V, where + Rd RRtt is feature map and h e RR* is a classifier that maps the representation to the final scores or logits. With A X' - A. we denote the augmentation function that takes in an input v and outputs an augmented view of the input A(z). Unless specified otherwise, we perform full-fnettunin in all of our experiments on real-world data. That is, we backpropagate gradients in both the linear head and the backbone Φ. For UDA, we denote source labeled points as {(2;, yo) W)) and target unlabeled points {(x{)]==- use the same notation for labeled and unlabeled in-distribution data.
Im For SSL,
C.2 Dataset details
For both UDA and SSL, we conduct experiments across eight benchmark datasets. Each of these datasets consists of domains, enabling
construct source-targe pairs for UDA. The adopted source and target domains are standard to previous studies [76] 30 [7].. Because the SSL setting lacks distribution shift, we do not need to worry about domain designations and default to using source alone. To simulate limited supervision in SSL., we sub-sample the original labeled training set to 10%. Below provide exact details about the datasets used in our benchmark study.
We use the original CIFAR1O dataset 48 as the source dataset. For target domains, we consider CINIC1O [22] which is a subset of Imagenet restricted to CIFAR10 classes and downsampled to 32x 32.
CIFAR10
FMoW In order to consider distribution shifts faced in the wild, we consider SMoW-WILDS [47] 18 from WILDS benchmark, which contains satellite images taken in different geographical regions and at different times. We use the original train as source and OOD val and OOD test splits as target domains as they are collected over different time-period. Overall, we obtain 3 different domains (1
source and 2 targets).
BREEDs We also consider BREEDs benchmark 72 in our setup to assess robustness to
subpopulation shifts. BREEDs leverage class hierarchy in ImageNet (68] to re-purpose original classes to be the subpopulations and defines classification task on superclasses. We consider distribution shift due to subpopulation shift which is induced by directly making the subpopulations present in the training and test distributions disjoint. BREEDs benchmark contains 4 datasets Entity-13, Entity-30, Living-17, and Non-living-26, each focusing on different subtrees and levels in the hierarchy. Overall, for each of the 4 BREEDs datasets (i.c., Entity-13, 13, Entity-30. Living-
19

---

Dataset
Domains
CIFAR1OV1
CINIC1O
CIFAR10
Year 113-11
116-18
FMoW
Syntherie
Real-1
Real-2
Visda
Sub
Sub-pop,
Entity13
Sub
Sub-pop.
Entity30
pop.
Sub-pop.
Living17
Sub-pop.
Sub pap.
Nonliving26
Product
Real
ClipAt
Art
Officehome
Figure 4: Examples from all the domains in each dataset.
17, and Non-living-26), we obtain one different domain which we consider target. We refer to source and target as follows: BREEDs sub tob-population 1, BREEDs sub- uub-population. 2.
OfficeHome We use four domains (art, clipart, product and real) from OfficeHome dataset [85
We use the product domain as source and the other domains as target.
Visda We use three domains (train, val and test) from the Visda dataset 64 While 'train' domain contains synthetic renditions of the objects, 'val' and 'test' domains contain real world images. To avoid confusing, the domain names with their roles as splits, we rename them as 'synthetic', 'Real-1' and 'Real-2'. We use the synthetic (original train set) as the source domain and use the other domains as target.
We summarize the information about source and target domains Table
Train-fest splits We partition each source and target dataset into 80% and 20% i.i.d. splits. We use 80% splits for training and 20% splits for evaluation validation). We throw away labels for the 80% target split and only use labels in the 20% target split for final evaluation. The rationale behind splitting the target data to use completely unseen batch of data for evaluation. This avoids evaluating on examples where a model potentially could have overfit. over-fitting to unlabeled examples for evaluation. In practice, the aim is make predictions on all the target data (i.e., transduction), we can simply use the (full) target set for training and evaluation.
Simulating SSL settings and limited supervision. For SSL settings, choose the in-distribution domain as the source domain. To simulate limited supervision in SSL., we sub-sample the original labeled training set to 10% and use all the original dataset as unlabeled data. For evaluation, further split the original holdout set into two partitions (one for validation and the other to report final accuracy numbers).
C.3 Method details
For implementation, build on top of WILDs [70] and RLSbench [3 open source libraries.
20

---

Dataset
Source
Target
CIFARIO
CIFARIÓv1
CINICIO
FMoW
FMoW (2002-113)
FMoW (2013-166, FMoW (2016-118)
Entity13
Entity13 (suh-population 1)
Entity13 13 (sut-population 2)
3n
En 30 (sub-pupulation 1)
Entit300 (sub-population 2).
Living17
Living17 (sub-population 1)
Living17 (sub-population 2),
Nonliving26
Nonliving26 (sub- cub--opulation 1)
Nonliving26 (sub population 2),
Officehome
Product
Product, Art, ClipArt, Real
Synthetic
Synthetic, Real-1 (originally referred to as val), Real-2 (originally referred to as test)
Visda
(originally referred to as train)
Table 3: Details of source and target sets in each dataset considered in our testhed.
ERM (Source only) training. We consider Empirical Risk Minimization (ERM) on the labeled source data as baseline. Since this simply ignores the unlabeled target data, we call this as source only training. As mentioned the main paper, we perform source only training with data augmentations. Formally, we minimize the following ERM loss:
Lamurce only (
((((Ac;))
where the stochastic data augmentation operation and is loss function. For SSL, the ERM baseline only uses the small of labeled data available.
Contrastive Learning (CL). We perform contrastive pretraining on the unlabeled dataset to obtain the backbone éa. And then we perform full fine-tuning with source labeled data by initializing the backbone with 6at- We use SwAV [13] for contrastive pretraining. The main idea behind Sw is train model to identify different views of the same image as similar, while also ensuring that finds different images to be distinct. This is accomplished through a swapped prediction mechanism, where the goal is compute code from augmented version of the image and predict this code from other augmented versions of the same image. In particular, given two image features o(x',1) A(x'), SwAV
and o<x(22) from different augmentations of the same image x', i.c.. z' a'a computes their codes 2a and 2,2 by matching the features to set of K prototypes {cI, .x). Then SwAV minimizes the following loss such that ((xaa) ) can compute codes Za2 and 6(x"22) can compute codes Za1:
LSwAv Σ
Σ
+ El (6(x)) (1022)
Zia1)) (4,1))
A(x))
where e' computes KL-divergence between codes computed with features (e.g. d(x.1) and the code computed by another view (e.g. =a2). For more details about the algorithm, we refer the reader to Caron al. [3.. In all UDA settings, unless otherwise specified,
pool all the (unlabeled) data from the source and target to perform SwAV. For SSL, we leverage in-distribution unlabeled data.
We employ SimCLR 16 for the CIFAR10 dataset, aligning with previous studies that have utilized contrastive pretraining on the same dataset [51 76). The reason for this choice that SwAV relies on augmentations that involve cropping images to smaller resolution, making it more suitable for datasets with larger resolutions beyond 32 32.
Self- Sulf-raining (ST). For self- self-training, we apply FixMatch 79 where the loss on labeled data and on pseudolabeled unlabeled data are minimized simultaneously. Sohn et al. 79 proposed FixMatch as variant of the simpler Pseudo-label method This algorithm dynamically generates psuedolabels and overfits on them in each batch. Fix employs consistency regularization on the unlabeled data. In particular, while pscudolabels are generated on weakly augmented view of
21

---

the unlabeled examples, the loss is computed with respect to predictions strongly augmented view. The intuition behind such an update encourage model make predictions on weakly augmented data consistent with the strongly augmented example. Moreover, FixMatch only overfits to the assigned labeled with weak augmentation the confidence of the prediction with strong augmentation is greater than some threshold 7. Refer to Awak as the auk-eeugmenttiion and A strong as the Airong-augmentationn function. Then, FixMatch uses the following loss function:
1
Fiixaatch (f)
E(S AAtrong (x,),
{[((Auro (x))m max Le (Astong (x()
m
where 3; arg max,, (Tewk (x;)). For UDA, our unlabeled data is the union of source and target unlabeled data. For SSL, we only leverage in-distribution unlabeled data.
We adapted our implementation from Sagawa et al. (70) which matches the implementation of Sohn et al. (79] except for one detail. While Sohn et al. (79] augments labeled examples with weak augmentation. Sagawa al. 770 proposed strongly augment the labeled source examples.
Self-nraining Over Contrastive learning (STOC). Finally, rather than performing FixMatch from a randomly initialized backbone, we initialize FixMatch with contrastive pretrained backbone.
C.4 Additional UDA experimemts
Table Results the UDA setup. We report accuracy on target (OOD) data from which we only observe unlabeled examples during training. For benchmarks with multiple target distributions (e.g.. OH, Visda), we report average accuracy on those targets.
Method
Living17
Nonliv26
Entity13
Entity30
FMoW (2 (gts)
Visda (2 igts)
(3 (gts)
OH
CIFAR CINIC
ERM
60.2.0.1
45.4
68.6.0.1
55.7 10.0
56.5
20.8
9.5
74.310.
71.1=n.2
56.820.1
78.020.3
66.7
56.920.4
39.1
11.1
78.320.3
CL
74.1
57.4+0.3
76.9+0.2
66.6+0.3
61.5+0.5
63. 03.2+0.2
22.8+0.1
77.5+0.1
STOC (ours)
82.6 82.610.1
62. 62.1:0.2
81.910.2
72.0.0.2
65.3 65.3
70.1:0.2
27.1:0.3
79.910.3
Table Results in the UDA setup with source only contrastive pretraining. We report accuracy on target (OOD) data from which we only observe unlabeled examples during training. For benchmarks with multiple target distributions (e.g., OH, Visda), we report average accuracy on those targets.
Method
Living17
Nonliv26
Entity13
Entity30
FMoW (2 tgts)
Visda (2tst)
OH
CIFAR-+ CINIC
(3 tgts)
CL (source only)
67.3g0.1
49.120.2
71.5g0.1
58.520.a
53.940.1
33.31n.2
21.720.1
77.720.1
STOC (snurce only)
75.0+0.2
58.4+0.1
79.8+0.3
67.5+0.1
56.3+0.a
42.7+0.1
25.7+0.1
77.8-0.
CL
74.1
57.420.3
76.920.2
66. 66.62o.a
61.5g0.5
63.220.2
22.820.1
77.520.1
STOC
82.6+0.1
62.1
72.0+b.2
65.3+0.1
70.1+0.2
22

---

C.5
Additional SSL experiments
Table 6; Results in the SSL setup. We report accuracy hold-out ID data. Recall that SSL uses labeled and unlabeled data from the same distribution during training.
Method
Living17
Nonliv26
Entity 13
Entity30
FMoW
Visda
OH
CIFAR
ERM
76.810.1
64.910.2
80. 10.1
70.410.3
33.610.4
99.210.0
32.010.2
85.510.1
ST
85.4
75.7
85.4+0.2
77.3+0.1
33.6+0.3
99.2+0.1
32.0+0.1
93.1
CL
91.1+0.5
84.620.6
90. 00.74
85.540.a
43.1
07.620.3
49. 20.7
91.7+0.2
STOC (ours)
92.0
85.810.2
91.310.3
86.1
44.4
97.710.2
49.910.2
93.0610.3
C.6 Other experimental details
Augmentations. For weak augmentation, we leverage random horizontal flips and random crops of pre-defined size. For SwAV, we also perform multicrop augmentation as proposed Caron et al. [13]
For strong augmentation, we apply the following transformations sequentially: random horizontal flips, random crops of pre-defined size, augmentation with Cutout [24], and RandAugment [21] For
the exact implementation of RandAugment, Unless specified otherwise, for all methods, we default to using strong augmentation techniques.
directly the implementation of Sohn et al. [79
Architectures. In our work, we experiment with Resnet1 88 Resnet50 [42 trained from scratch (i.e. random initialization). We do not consider off-the-shelf pretrained models (e.g., on Imagenet (68 to avoid confounding our conclusions about contrastive pretraining. However, we note that our results on most datasets tend be comparable and sometimes exceed those obtained with ImageNet pretrained models. For BREEDs datasets, we employ Resnet18 architecture. For other datasets, train a Resnet50 architecture.
Except for Resnets on CIFAR dataset, we used the standard pytorch implementation 27 For Resnet on Cifar, we refer the implementation here: /htpps:/ /gthtut com/ wwwp///laaannttrnroeeeooe cifar For all the architectures, whenever applicable, we add antialiasing [97]. We use the official library released with the paper.
Hyperparameters. For all the methods, we fix the algorithm-specific hyperparameters to the original recommendations. For UDA, given that the setup precludes access to laheled data from the target distribution, we use source hold-out performance to pick the best hyperparameters. During pretraining, early stopping done according to lower values of pretraining loss.
We tune the learning rate and & regularization parameter by fixing the batch size for each dataset that corresponds to the maximum rate schedule [56]. We set the number of epochs for training as per the suggestions of the authors of respective benchmarks. For SSL, run both ERM and FixMatch for approximately 2000 epochs. Note that we define the number of epochs as a full pass over the labeled training source data. We summarize the learning rate, batch size, number of epochs, and regularization parameter used in our study in Table 7
fit to 15GB GPU memory. We default to using cosine learning
Compute infrastructure. Our experiments were performed across combination of Nvidia T4, A6000, and V100 GPUs
D Additional Results in Toy Setup
In this section we will first give more details on our simplified setup that captures both contrastive pretraining and self-training the same framework. Then, we provide some additional empirical results that are not captured theoretically but mimic behaviors observed in real world settings, highlighting the richness of our setup.
D.1 Detailed description of our simplified setup
In this subsection, we will first re-iterate the problem setup in Sec. Fand provide some comparisons between our setup and those in closely related works. We will then describe the four methods: ERM,
23

---

Dutaset
Batch size
E2 regularization set
Learning rate set
CIFARIO
200
{0.001, 0.0001, 10 110...00000 .000]
[0.2, 0.1, 0.05, 0.01, 0.003, 0.001
FMoW
64
{0.001, 0.0001, 10 ..000
(0.01, 0.003, 0.001, 0.0003, 0.0001)
Entity 13
256
{0.001, 0.0001, 10.0)
[0.4.0.2, 0.1, 0.05, 0.02, 0.01, 0.005)
Em
256
[0.001, 0.0001, 10"2.0.0]
{0.4.0.2, 0.1, 0.056 0.02, 0.01,0.005)
En
256
{0.001, 0.0001, 10.0)
[0.4,0.2, 0.1, 0.05, 0.02, 0.011 0.00,
Nonliving26
2.56
[0.001, .0.0)
(0.4,0.2, 0.05, 0.02, 0.002,000.000000000....
Officchome
0.0001, 10 ,000)
(0.01,0.003) 0.000,0
Visda
96
{0.001, 0.000,, 10 *.0.0)
(0.03, 0,0030001...003,,,000000000000
Table 7: Details of the batch size, learning rate set and & regularization set considered in our testbed.
ST, CL, and STOC, providing details on the exact estimates returned by these algorithms in the SSL and UDA settings.
Data distribution. We consider binary classification and model the inputs as consisting of two kinds of features: = [zin where Tin E R is the invariant feature that is predictive of the label across both source Ps and target PT and Zsp E Rd is the spurious feature that is correlated with the label only on the source domain Ps but uncorrelated with label in PT. Here, Iin E IR Rd determines the label using the ground truth classifier wn Unif(San- "), and Tep Re is strongly correlated with the label on source but random noise on target. Formally, we sample y ~ Uniff -1 and generate inputs x conditioned on y as follows
Ps Tin ~ N(7 yw", Min) Tap ylddp
PT: Tin ~ N(7 yww,""""" Eim) Tup
where 7 is the margin afforded by the invariant feature. We set covariance of the invariant features En = of (Ia.. w "o=w"T ) to capture structure in the invariant feature that the variance is less along the latent predictive direction w". Note that the spurious feature is completely predictive of the label in the source data, and is distributed as spherical Gaussian in the target data with Mip = o2
Why is our simplified setup interesting? In our setup, Tia is the hard to learn feature that generalizes from source to target. The hardness of learning this feature determined by the value of the margin y and how it compares with size of the spurious feature (Vdap). Since, 7/ /dp is small in our setup, Tin is much harder to learn on source data (even with population access) compared to the spurious feature Tap which generalizes poorly from source to target. These two types of features have
been captured in similar analysis on spurious correlations 71 60] since it imitates pitfalls emanating from the presence of spurious features in real world datasets (e.g., the easy to learn background feature in image classification problems). While this setup is simple, it is also expressive enough to elucidate both self-training and contrastive learning behaviors we observe in real world settings. Specifically, it captures the separation results we observe in Sec. 3
Differences of our setup with prior works. While our distribution shift settings bears the above similarities it also has important differences with works analyzing self-training and contrastive pretraining individually. Chen et al. [17 analyze the iterative nature of self-training algorithm, where the premise is that we are given a classifier that not only has good performance on source data but in addition does not rely too much on the spurious feature. Under the strong condition of small norms along the spurious feature, they show that self- training can provably unlearn this small dependence when the target data along the spurious feature is random noise. This assumption is clearly violated in setups where the spurious correlation is strong (as in our toy setup), i.e., the dependence on the spurious feature is rather large (much larger than that on the invariant feature) for any classifier that is trained directly on source data. Consequently, we show the need for "good" pretrained representations from contrastive pretraining over which if we train linear predictor (using source labeled data), it will provably have a reduced "effective" dependence on the spurious feature.
Using an augmentation distribution similar to ours, Saunshi et al. 73 carried out contrastive pretrain- ing analysis with the backbone belonging to a capacity constrained function class (similar analysis also in 40).. Our setup differs from this in two key ways: (i) we specifically consider distribution
24

---

shift from source to target. Unlike their setting, it is not sufficient to make augmentations consistent with ground truth labels, since the predictor that uses just the spurious feature also assigns labels consistent with both ground truth predictions and augmentations on the source data; and (ii) our aug- mentation distribution assumes no knowledge of the invariant feature, which why we augment all dimensions uniformly, as opposed to selectively augmenting a set of dimensions. In other words, we assume no knowledge of the structure of the optimal target predictor. For e.g., if we had knowledge of the spurious dimensions we could have just selectively augmented those. Assuming knowledge of these perfect augmentations is not ideal for two reasons: (a) it makes the problem so easy that just training an ERM model source data with these augmentations would already yield good target predictor (which rarely happens in practice); and (b) in real-world datasets perfect augmentations for the downstream task are not known. Hence, stick to generic augmentations in setup.
D.2
Discussion on self-training and contrastive learning objectives
Method
UDA Sctup
SSL Sctup
herm arg min, +. Ei_, ((h(2.))
ERM:
Aam = min, Bp (h((())(),))) v)
((2. 36) Pr"
Starting from harm optimize over h (to get ha): (Mrr)))(((()),guu(((((
Starting from harm optimize over h (to get ha)::
ST:
2 arg min, La (2)
2. arg (+)
CL:
Use (Ps(x) + PT(x)) (+)
Use PT(x) for (b)
hat mrgmin, ( (2))),
ha = arg 3 Σ. f(h (x)))))))
Starting from ha optimize over h (to get hatc)::
Starting from ha optimize over get hatoe):
STOC:
(pt (a(z))sgn(( (=)))
Epr(ajE(h Da sgu(h (a())))
Table 8: Description of methods for SSL UDA: For each method provide exact objectives used for experiments and analysis in the SSL and UDA setups (pertaining to Sec. 4
In text will describe our objectives and methods for the UDA setup. In Table g we constrast the differences in the methods and objectives for SSL and UDA setups. Recall from Section 2 that we learn linear classifiers h over features extractors 4. We consider linear feature extractor 1.c. 4 is matrix in R For mathematical convenience, we assume access to infinite unlabeled data and hence replace the empirical quantities over unlabeled data with their population counterpart. In the UDA setting, we further assume access to infinite labeled data from the source. Note that due to distribution shift between source and target, "ERM" infinite labeled data from the source does not necessarily achieve optimal performance on the target. For binary classification, we assume that the linear layer h maps features exponential loss {[((), y) = exp (=yf(((())) as the classification loss.
scalar in R such that the prediction is sgn(h (h T 4zr). We use the
Contrastive pretraining. We obtain da = arg ming La(()) by minimizing the Barlow Twins objective 933. which prior works have shown is also equivalent to spectral contrastive and non- contrastive objectives [33 In Sec. 4 we consider constrained form of Barlow Twins in (3) which enforces representations of different augmentations a1 a2 of the same input x to be close in representation space, while ensuring feature diversity by staying in the constraint set. We assume strict constraint on regularization (p- = 0) for the theoretical arguments the rest of the main paper. In App. 1.1 we prove that all our claims hold for small p as well. In (7). redefine the pretraining objective with a regularization term (instead of a constraint set) where k controls the strength of the regularization term, with higher values of corresponding stronger constraints feature diversity. We then learn linear classifier ha over d to minimize the exponential loss on labeled source data.
(T) == Ep- Er a2 Pa(-a) ( (a,) - (a2))11 + K EE-PA c ((a) 7
I
(7)
25

---

CL vs. STOC across
CL vs. STOC across
CL dimension k
CL regularization strength
OOD Accuracy
100
OOD Accuracy
100
80
90
80
70
40
CL
ERM
60
CL
ERM
20
STOC
50
STOC
40
1
4 7 10 13 16 19 22 25
0.05
0.15
0.25 0.35 0.45
k: CL feature dimension
K: CL regularization strength
Figure 5: Ablations on pretraining hyperparameters: In the UDA setup we plot the performance of CL and STOC the feature extractor Φ; and (right) the strength (k) of the regularizer in the Barlow Twins objective in 77. While ablating & we fix 0.5, and while ablating we fix k 10. Other problem parameters are taken from Example
vary two pretraining hyper-parameters: (left) the output dimension (k) of
Augmentations. Data augmentations play a key role in contrastive pre-training (and also as we see later, sfate-of-the-ar self- self-training variants like FixMatch)). Given input E X, let Pa(a x)) denote the distribution over its augmentations, and PA denote the marginal distribution over all possible augmentations. We the following simple augmentations where scale the magnitude of each co-ordinate by a uniformly independent amount, i.e.,
PA x)) c where, e~ Unif[o, 1j
(8)
The performance of different methods heavily depends on the assumptions we make augmentations. We try to mirror practical settings where the augmentations are fairly "generic", not encoding any information about which features are invariant or spurious, and hence perturb all features symmetrically.
Self-training. ST performs ERM in the first stage using labeled data from the source, and then subsequently updates the head h by iteratively generating pseudolabels on the unlabeled target:
1'+1 h v/ Co
Lee 3) = 0(h Dx, sgn ((x)))
Update:
(9)
The 1, natt (h"; +)
For convenience, we keep the feature backbone fixed across the self-training iterations and only update the linear head on the pseudolabels.
STOC(Self-training after contrastive learning). Finally, we can combine the two unsupervised objectives where we do the self- self-training (2dates([) with hg ha and Q & starting with the contrastive learning model rather than just source-only ERM. Here, we only update and fix a
D.3 Additional empirical results in our simplified setup
We conduct two ablations on the hyperparameters. for contrastive pretraining. First, we vary the dimensionality & of the linear feature extractor gixd Second, we vary the regularization strength that enforces feature diversity in the Barlow Twins objective 7 In Figure 5 we plot these ablations in the UDA setup.
Varying feature dimension. We find that CL recovers the full set of predictive features (i.e. both spurious and invariant) only when & large enough (Figure left)). Since the dimensionality of the true feature is 5 in our Example 1, reducing & below the true feature dimension hurts CL. Once k crosses a certain threshold, CL features completely capture the projection the invariant feature win- After this point, it amplifies the component along Win It retains the amplification over the spurious feature Wap even as we increase This confirmed by our finding that further increasing & does not hurt CL performance. This is also inline with our theoretical observations, where we find that for
26

---

Results in UDA setup
Results in SSL setup
100
98.3
100
98.1
OOD accuracy
755
ID accuracy
79.4
50
51.1
25
53.7
ERM
ST
CL
STOC
ERM
ST
CL
STOC
Figure 6: Results with linear backbone: We plot the OOD accuracy for ERM, CL., ST and STOC in the UDA setup and ID accuracy in the SSL setup when the feature extractor o is linear network. Note, that the feature extractor still fixed during CL and STOC.
suitable w", the subspace spanned by Win and Wspp are contained in a low rank space (as low as rank 2) of the contrastive representations (Theorem 5 Once CI. has amplified the dependence along Win STOC improves over CL by unlearning any remaining dependence on the spurious Wsp- The above arguments for the CL trend also explain why the performance of STOC continues to remain s 100% as we vary k.
Varying regularization strength. In our main theoretical arguments we consider the constrained form of the Barlow Twins objective B with a strict constraint of p (we relax this theoretically as well, see E.1.2). For our experiments, we optimize the regularized version of this objective (7), where the constraint term now appears as a regularizer which enforces feature diversity, i.e. the features learned through contrastive pretraining span orthogonal parts of the input space (as governed under the metric defined by augmentation covariance matrix EA). If i very low, then trivial solutions exist for the Barlow Twins objective. For e.g., Φ & 0 (zero vector) achieves very low invariance loss. When x < 0.05, we find that CL recovers these trivial solutions CL and STOC perform poorly. As we increase the performance of both CL and STOC improve, mainly because the features returned by Pe now comprise of the predictive directions Win and Wsp- as predictive by our theoretical arguments for p 0 (which corresponds to large k). On the other hand, when & is too high optimization becomes hard since λ directly effects the Lipschitz constant of the loss function. Hence, the performance of CL drops by some value. Note that this does not effect the performance of STOC since CL continues to amplify Win over Wap even if returning suboptimal solutions with respect the optimization loss of the pretraining objective.
(nngure(rrigtt))) Hence, both
D.4 Reconciling Practice: Experiments with deep networks in toy setup
In this section delve into the details of Sec. 4.5 i.e., we analyze performance of different methods when we make some design choices that imitate practice. First, we look at experiments involving a deep non-linear backbone & Here, the non-linear & is learned during contrastive pretraining and
Results UDA setup
Results in SSL setup
99.7
96.3
87.7
OOD accuracy
75
ID accuracy
80
72.6
50
51.1
60
25
51.2
ERM
ST
CL
STOC
ERM
ST
CL
STOC
Figure 7: Results with non-linear backbone: We plot the OOD accuracy for ERM, CL., ST and STOC in the UDA setup and ID accuracy in the SSL setup when the feature extractor & is non- linear one-hidden layer network with ReLU activations. Note, that the feature extractor still fixed during CL and STOC.
27

---

UDA setup: Full-finetuning STOC (non-linear backbone)
SSL setup: Full-finetuning STOC
(linear backbone)
100
99.2
100
OOD accuracy
ID Accuracy
80
77.6
80
CL
70.9
STOC
60
ERM
60
CL
STOC w/o STOC with aug.
30
150 180 CL training epochs
60 90
120
aug.
Figure 8: Finetuning the contrastive representations during STOC: We propagate gradients to the feature backbone & when running STOC algorithm. Note that CL still fixes the contrastive representations when learning a fixed linear head over it. On the (left) we show results in UDA setup where compare the performance of STOC with and without augmentations (along with other practical design choices like confidence thresholds and continuing to optimize source loss as done in FixMatch) when the feature backbone is non-linear. On the (right) we show results for STOC and CL in the SSL setup when the feature backbone is linear.
fixed for CL and STOC. Then, we investigate trends when we continue to propagate gradients onto during STOC (we call this full-finetuning). Unlike previous cases, this allows features to be updated.
Results with non-linear feature extractor 4. In Fig- methods when we use non-lineat feature extractor during contrastive pretraining. This feature extractor is a one-hidden layer neural network (hidden dimension 500) with ReLU activations. We find that the trends observed with linear backbones in Fig. 6 are also replicated with the non- linear one. Specifically,, we note that STOC improves over CL under distribution shifts, whereas CL is already close to optimal when there are no distribution shifts. We also see that CL and ST individually are subpar. SSL, we see huge drop in the performance of ST (over ERM) mainly because we only fit on pseudolabels during ST. This is different from practice where we continue to optimize loss on labeled data points while fitting the pseudolabels. Consequently, when we continue to optimize performance on source labeled data the performance of ST in SSL setup is improves from 51.1% 72.6%.
plot the performance of the four
Results with full fine-tuning. Up till this point, we have only considered the case (for both SSL and UDA) where we fix the contrastive learned features when running CL and STOC, i.e., we only optimized the linear head h. Now, we shall consider the setting where gradients are propagated to & during STOC. Note that we still fix the representations for training the linear head during CL. Results for this setting are in Figure g We show two interesting trends that imitate real world behaviors.
STOC benefits from augmentations during full-finetuning: In the UDA setup find that ST while updating &. can hurt due to overfitting issues when training with the finite sample of labeled and unlabeled data (drop by 7% over CL.. This is due overfitting on confident but incorrect pseudolabels on target data. This can exacerbate components along spurious feature Wspp from source. One reasoning behind this is that deep neural networks can perfectly memorize them on finite unlabeled target data (94). Heuristics typically used in practice (e.g. in FixMatch [79]) help avoid overfitting on incorrect pseudolabels: (i) confidence thresholding; pick confident pseudolabel examples: (ii) pseudolabel different augmented input than the one on which the self-tran self-training loss is optimized; and (iii) optimize source loss with labeled data simultaneously when fitting pseudolabels. Intuitively, thresholding introduces curriculum where we only learn confident examples in the beginning whose pseudolabels are mainly determined by component along the invariant feature win- Augmentations prevent the neural network from memorizing incorrect pseudolabels and optimizing source loss prevents forgetting features learned during CL. When we implement these during full- finetuning in STOC see that STOC now improves over CL (by 20%).
28

---

Can we improve contrastive pretraining features during STOC? We find that self self-training can also improve features learned during contrastive pretraining when we update the full backbone during STOC (see Figure 8 right)). Specifically, in the SSL setup we find that STOC can now improve substantially over CT., Recall, that when we fixed &et this was not possible (see E.3 and Fig. 2)).. This is mainly because STOC can now improve performance beyond just recovering the generalization gap for the linear head (which is typically small). This feature improvement is observed even when fully finetune linear feature extractor. Similar trends are also observed with the non-linear backbone. But, it becomes harder to identify a good stopping criterion for CL training. Thus, remains unclear if STOC and CL have complementary benefits for feature learning in UDA or SSL settings. Investigating this is an interesting avenue for future work.
E
Formal Statements from Sec.
Recall from Section that learn linear classifiers over features extractors 4. We consider linear feature extractor i.e. is matrix in Rd and the linear layer h R2 IR with prediction as sgn(h (w)) We use the exponential loss {(f(x)))) exp (-)f(x)).
E.1
Analysis of ERM and ST: Formal Statement of Theorem 2
For ERM and ST. we train both h and Φ. This is equivalent to O = [axd being identity and training linear head h. Recall that the ERM classifier is obtained by minimizing the population loss on labeled source data:
hERM = arg min Px [((
(10)
We split Theorem 2 into Theorem 8 and Theorem Before we characterize the ERM solution, we
recall some additional notation. Deñne Win - [w* 0 ..... O]T, and Usp [O..... ..... 0, /d.pp" The
following proposition characterizes MERM and 0-1 error of the classifier on target:
Theorem (ERM classifier and its error on target). ERM classifier obtained in (10) given
hERM /hERMll2
? Win + dap Usp
77²+ dap
The target accuracy of hERM is given by 0.5 erfe (-dd/(/2ddn (2
Proof. To prove this theorem, we first derive a closed-form expression for the ERM classifier and then use Lemma 29 to derive its 0-1 error target. For Gaussian data with the same covariance matrices for class conditional Ps(zly = 1) and Ps(xly = 0), Bayes decision rule is given by the Fisher's linear discriminant direction (Chapter 4; Bishop (
[1,
if T x
h(z) = 0.
otherwise
where h (w(m) + 2 (dpp(psp))) Plugging h in Lemma 29 we get the desired result.
ST performs ERM in the first stage using labeled data from the source, and then subsequently updates the head & by iteratively generating pseudolabels on the unlabeled target:
Lat (h) = EPT(c) sgggh(h x)))
(11)
Starting with hg h 2 (the classifier obtained with ERM) we perform the following iterative procedure for self self-training:
ASST V) n (11ST)
(12)
V.Ca (nS
Next, characterize ST solution:
Theorem 9 (ST classifier and its error target). Starting with ERM solution, ST will lead to:
29

---

(i) (Necessary condition) h57 Wap as È - 00, such that the target accuracy is 50% for all sp e and 2./0
(ii) (Sufficient condition) hisr Win as t - oc, such that the target accuracy is 100% when the problem parameters Y,, Sap satisfy: > Osp-
Proof. The proof can be divided into two parts: (i) deriving closed-form expressions for updates on hisT in terms of hSs and (ii) obtaining conditions under which the component along Win mono- tonically increases decreases with & after re-normalizing the norm of updated h. For notation convenience, we denote lşT with in the rest the proof.
Part-1. First, the loss of self- self-training with classifier h = [hims hapl where hig E R and hap Rd is given by:
(h) (P)(a) [e(h 2, sgn xx)]]
(13)
EP((a) cxp (- sign(M x)) (TTx)) x))]
(14)
Epr(x) [exp (- |1 xx]]
(15)
(PT(a) |exp (- [ + Tap
(16)
Ey- (Py-((1111) (-1.1),=~N(0.11 [exp 1-17.3 17.37 w w*
+ oin (1 1 (h (0)"))) + Jap |1hapl12 [ =1]
(17)
(-/7
| IT=""= + Iin (1liinm (n + Jsp 1hp 12] : :)]] (18)
(E=-A(0.1)
exp
where [66 to 17 implied by simply replacing the definition of target distribution and (17) to (18) is implied by the symmetry of the function with respect to y and -y due the symmetry of the absolute function and Gaussian distribution. For a classifier h², we denote μr = y hi w" and
at [ (1 (Min T )²) + Osp [1%plla] With this notation, we can re-write the loss in 18 as (h') o(,, [exp (- l 2|)].
Now we derive closed-form expression of (h") in Lemma 30
1 Cai(h') = 2
o Me)
erfe (- 1200, (-120)
+ Ot
o + ps)
H+.
St
exp
exp
erfc
+
2
v2
2
/20,
/2 (19)
Define the Mill's ratio as (I) = exp (x3/2) erfc (x/v2) .V 2/2 as in Baricz [5]. We will frequently use standard properties of the Mill's ratio. We list them Lemma 21 for completeness. Define:
a1 (Utr, σt) = exx
c
Me
erfe
(-Me He
+
Tt
+
exp
o +
erfe
+
σt
2
220
v2
2
V20,
/2
2
m
Mt
1t
=Va
exp
0z
(20)
20
Te
[7
Pt
Tt
o
M1
Tt
a2(1,, = exp
Mt
erfc
exp
Me)
erfc
2
V20,
v2
1/20,
/2
2/2
exp
TIVIT
π
20
2
14
Mi
#4
2
exp
o
+r
0:
(21)
π
20
ot
σe
oe
Let 7141 denote the un-normalized gradient descent update at iterate & ++ 1. We have:
2L (h²)
7 h²
(22)
ōh
30

---

Now we will individually argue about the update of h along the first du dimensions and the last dsp dimensions. First, have:
(h9)
T in
1//1 - 11.
Ohin
7
oi
Me
oi
exp
pt
erfe
2
V20,
v2)
0
14
+exp
14
erfe
+
-7.w w
22
V2
7
Ht
exp
pt
erfe
2
2
V20g
v2
0i
Ht
0t
+exp
+
14
erfc
+
2
/20+
/2
2v2
Mi
exp
(2h
2(h w w')w") o
TIVI π
20
hi an (1i; σ1) . w²
a2( σI) (2 2(1 "=""")) onu
(23)
2
Notice that the update of +++1 is split into two components, one along w" and the other along the orthogonal component 2h 2 w")"". We will now argue that since at initialization, the component along (1 w w'"" is zero then it will remain zero. In particular, have:
T (1 w"w" a wn (1 - w'w" =0.
(24)
With 23
we can argue that if (I w"w" )h O, then (J w-w" ) 0 implying that for all t > 0. Hence, we have:
(I w w T yhi
11.1 (h))
inv
ôhin
h/ 2 a1 (14, 0z) --
17
(25)
Second, have the update htt1 given by:
(h")
11p -1 1)
sp
Ōhap
hrp
"7
2
exp
0i
2
Ut
erfe
220,
H1
V2
01
+exp
10
2
14
erfe
V200
11
2
0t
OLV
2
exp
20
m1
-h
oz
hip
a2241, or)
hhpp
(26)
Re-writing the expressions
25 and
26
for the update 71-1 we have:
h
h/n (1
"
an (14,, στ) -22/p))
(27)
2
T+41 sp
(1
a2 σ.) -
(28)
2
Here, we replace hrp Me w* /y in (25) to get 27 Updates in 27 and (28) show that h++1 remains in the direction of hf, and h remains in the direction of h
31

---

Part-2. Now we will derive conditions under which hn and h will show monotonic behavior for necessary and sufficient conditions. We will first argue the condition under which ST will provably fail and converge to classifier with random target performance. For this, at every i, if we have:
h++1 sp
2
|1
(29)
h+++1
2
then we can argue that as -- c0, we have || and hence, the ST classifier will have random target performance. Thus, we will focus conditions, under which the norm on | increases with &. Re-writing (29). we have:
A++1
sp
2
>
RA+1
|Mppll
(30)
M++1
7 1
1b)))))
1
(31)
2
12"
(1
(1spl12)
|iplle
(32)
Min
12
(33)
h
|h
Plugging in 27 and 28
into
33
we get:
ag(Me, σ,)
>
1 1-
7 a (Pt, σ1) -72/1//
(34)
For small enough 7) we have the necessary condition for the failure of ST as:
a2( o < an (1) 72//p-
(35)
Now we show in Lemma and Lemma 10 that if the conditions assumed in the theorem continue to hold, then we can success and failure respectively.
Lemma 10 (Necessary conditions for ST). Define an and a2 in 20 and 21
respectively. If
Tsp 2 1 and y & T. then we have for all I:
dg 1e
02 ag 0i)
& ai (He,o))
(36)
72
Proof. We upper bound and lower bound a and a2 by using the properties of r (-). Recall:
an 0z)) 22
]
20
r
o
o.
(37)
and
a2(u,, =
2 exp π
r
ot
He
+
P1
2
(38)
20
σt
0t
We now use Taylor's expansion on r (+) and we get:
2
r (o.) + r' (at)
ar
11
$ <r + (ot)
R²"
(39)
at
(
and similarly, we get:
2
r(a)) - r (ot)
[1
rr
a:
14
& <((o)) - (((o))
[1t
+
R"
F1g
(40)
σz
32

---

where R" = rr (ou). This is because r" (+) takes positive values and is a decreasing function in oe We now lower bound an (He, oz) and upper bound a2(14, ot);
(refer Lemma 21
an (1)
(11)
2r (os)
R"
(41)
2 V
Exx
0
0
2077
022
Oe)
2r (0x) + 2. R"
Mt
2
(42)
exp
20
Substituting the lower bound and upper bound in condition (i.e.. 43) implies (6)):
36 gives us the following as stricter a necessary
(o.) + R"
2
ft
$
2r'
(0t)
(14)
[+t
R"
(43)
0
0t
2
(o,) + R"
Mt
2
0g
2t (01)
1
R"
H
(44)
Tt
7/
0t
(a,) + R"
0t
Pt
d
22
ap
<
<r(o))
0t
1
R"
2
o
Ht
(45)
(1 (
R"
P
0 sp
+
R"
14
$ (((o)) -
_
op
(46)
Tt
2
2
0f
R"
sp
R"
14
< (a (01) - 1).
sp
(47)
72
2
Now, we will argue the monotonicity of LHS and RHS in Observe that LHS is increasing in pe and decreasing in o, and RHS is decreasing in as (ø,r (T)) 1) is increasing (and the multiplier negative). Moreover, if (47) holds true for maximum value of RHS and minimum of LHS, then we
would have 36.. Thus substituting Pr 7 and 0r 0o in LHS and o. Osp in RHS, we get:
R"
& (JspI (Osp) - 1). 1 - of
R"
ap
(48)
00
72
2
72
R"
2
R"
7
< (aap (aap) - 1).
1- 1-
sp
(49)
0
2
72
(50)
Taking 7 & 22o..p
1 and substituting R" = r" (oo): (5/4) r" (oo) aa & (a (aap) 1). (1-4.03)
(51)
Analytically solving the above expression, we get that (1) is satisfied for all values of dep > 1 when dep e 1. For example, the expression in (5T) is also satisfied for the problem parameter used in the running example of the main paper.
As a remark, we note that in the proof of Lemma 10 the conditions derived are loose because of the relaxations made to simply the proof. In principle, the proof (and hence the conditions) can be tightened by carefully propagating second-order terms (which depend on σ,) in (40).
Lemma 11 (Sufficiency conditions for ST), Define an and a2 as in 20 and 21 respectively. If Tap & 7, then we have for all t::
oep 1t 72
a2 0.)
3 ai(1:: 0z).
(52)
33

---

Proof. We upper bound and lower bound a1 and a2 by using the properties of r (-). Recall:
2
H4 o:
122
0e ]
a1 0z) -
exp
σo
(53)
20
and
2 a2(U,, ot) V =exp (-
(
He
P
2
r
oe
+
(54)
20
ot
Ft
0+
We now use Taylor's expansion on (+) and we get:
r ((o)) (o))
He & r
(r(o,)+1( (ot)
U4 0z
+ (ot)
+o)()))
F4
(55)
o
oz
0x
and similarly, get:
- (( (ot)
(1)) 1" (ot)
2 [44
oz &
ao
14
<r(or) - (o)) σx
(!) +
14
R"
14
0
(56)
where R" = 1" (oo). This is because r" (.) takes positive values and is a decreasing function in oz
(refer to Lemma 21 We now lower bound a; (Hl, 02) and upper bound a2([4,, o.):
an a1(M,,00 σ.) 42 207
Fe
$ (r:)))
(57)
V2
0:2 (2( σr)
2
> 2r (ot) + +r" (o))
(58)
/ eexp
12
a
Ft
20
Substituting the lower bound and upper bound in 52 condition (i.c., (59) implies (2)):
gives us the following as stricter a sufficient
2x (ot) + (o.)
1
2
2
21
(o,)
ft
(59)
9
22
2 2
2
2r (ot) + 1" (a1)
> 2r (ai)
14
(60)
0t
02
2r (at) 1" ((t)
[Mt
2
2
2r (at)
Mt
7
0
(61)
0
σt
2
sp
72
2r())) 2x -
ot + 1" (a.)
2
2
(at)
0
(62)
0²
a:
1
72
- 2r (ox) r" (at)
2r (ot)
0
(63)
at
22
- r (ot)
+ 2r (at)
> 0
(64)
σt
2 sp
Hence, when 1 - 3/ < 0, we have condition in (64) hold true as r' (ar) is always negative. Hence, d.
the condition 7 > dsp gives us the necessary condition.
E.1.1 Proof of Proposition 3
For convenience, we first restate the Proposition which gives us a closed form solution for when p = 0. Then, we provide the proof, focusing first on the case of 1, and then showing that extension to k > 1 is straightforward and renders the final form in the proposition that follows.
34

---

Proposition 12 (Barlow Twins solution). The solution for is U EA where Uk are the top k eigenvectors of A Σ A 1-1 Here, Ea == Ea-PAlaa is the covariance over augmentations, and Σ Pu (())(())) ]
is the covariance matrix of mean augmentations a(x) Epa(s/)]aa.
Proof. We will use ((z) to denote o where & E Rd Throughout the proof. we use to denote augmentation and denote the input. We will use PA(a x) as the probability measure over the space of augmentations A, given some imput & E X' (with corresponding density) Pa(- 2). Next, we use Pa(-) to denote the density associate with the marginal probability measure augmentations: PA Sx Pa(a 2r)dPu. Finally, the joint distribution over positive pairs A+ (a1, 42) = Sx PA(a) ( z)dPu, gives us the positive pair graph over augmentations.
Before solve the optimization problem in (3) for + Rexd for any general k, let first consider the case where k = 1, i.e. we only want to find a single linear projection Φ. The constraint = 0, transfers onto & in the following way:
Ea Ea-pald(a
Φ EAΦ =1
(65)
Under the above constraint want to minimize the invariance loss, which according Lemma 22 given by 2 SA (a) dPA, where L-))(-) is the following linear operator.
(a))(a) = o(a) -J .
A+ a') PA(a)
o(a') da'
(66)
Based on the definition of the operator, we can reformulate the constrained optimization for contrastive pretraining as:
S ((a) (a) APA
arg min dh E
(67)
E Pa-ra[((a)) J. I ((a) o(a') A+(a,a)) dada'
arg min
(68)
ox ExØ=1
[a-p)(((a))] J [ pa(al a)pa(a' (x) M(a)(la)) aPu
arg min
(69)
o: ExΦ=1
arg min
Ea Ea-Palo(a)9] [o(z)] dPu.
(70)
o:p E
where δ(x) = En- = Uni (c
x)]. (c Note that,
)(x)²= (Be- ())x)))²
(71)
= (B [c x
(72)
-
J x
[2
dPu Φ T
(73)
Further, since E. [o(a) as:
Ed we can now rewrite our main optimization problem for k 1
arg min
Φ EnS - TSx
(74)
d E=
arg max ΣΦ
(75)
do T 1-
Recall that in our setup both E and ΣA are positive definite and invertible matrices. To solve the above problem, let's consider ne-parameterization: o' >و o, thus T E 1, is equivalent to the constraint 6' d'12 1. Based on this ce-paaamttrrization are solving:
35

---

arg max
Σ 1/2 Σ. D 1/2 8
(76)
1=
which is nothing but the top eigenvector for Σ
Σイ 5. ΣA 1/2
Now, to extend the above argument from h: 1 1, we need to care of one additional form of constraint in the form of feature diversity: 6, AaØ; 0 when i * j. But, we can easily redo the reformulations above and arrive at the following optimization problem:
1 ..]] 17 Σ. Σ 1,, 12.. [k]
arg max
(77)
o 2 L, Vi 0, 6 0, Vi :
where of - Φ, The above is nothing but the top k eigenvectors for the matrix ΣT Σ. En 1/2 This completes the proof of Proposition 12
E.1.2 Analysis with > 0 in Contrastive Pretraining Objective
3
In 3 we considered the strict version of the optimization problem where 0. Here, we will consider the following optimization problem that we optimize for our experiments in the simplified setup:
Le((D,)) K) = Ey Ba [{)())) ((22)1 k. |A-PA [o(a)[(a)]] I1 (78)
where n >> 0 is some finite constant (note that every corresponds to some k and particularly O. corresponds к = o0). Let 4* be the solution for (3) with p i.e. the solution described in
Proposition 3 Now, we will show that in practice we can provably recover something close to + when & is large enough.
Theorem 13 (Solution for 78 is approximately equal to Φ²). If is some solution that achieves
low values of the objective La ( x) (78). i.e., Lei (,, x) e, then there exists matrix W B such that:
he 27
E Pall v'(a) (())
71
where, M++
V R
where 7h41 is the the k + th eigenvalue for I Σイ 1/2 E 1/2
Here, A & d2 g.... & Ad-
Proof. Since we know that (ō, k) & e, we can individually bound the invariance loss and the regularization term:
E Be @((1)) - (0 < 2 I
(79)
EaPPA {(a))(a))]
e $ F k
(80)
Thus.
Wie [M]
K E ΣA 32 1 V cz
(81)
Vi E [k]: E Ep,, oz PA (.1 (m) /5 a1 - क. 2 E
Ear
(82)
36

---

Let i. 17.02,10 Pj....,07 oz be the solution returned by the analytical solution for p = 0, i.e. the solution
in Proposition 3 Now, since o" would span F. when DA is full rank, we can denote:
(83)
Now from Lemma
22 the invariance loss for 3. can be written using the operator (())(a)
((a)=
A+ (a.a") SA
(aa') da':
Pa(a)
Invariance Loss(
= Eg-Po Part (0) 1 a2)²
(84)
=2. -2.Ba~PA -2-Ba--xl0((a((0001
(85)
2. P-Ba-PA
Σ
ni
(
L
Σ
of
(a)
(86)
y=1
d
d
2- 2BaMPA
?i
(1)
oj
7
(3)
L(o3(aa)
(87)
d
2. Σ
Ea-PA [0;(0)((0))())
(88)
j-1
+
Σ
Thi
( E. (+)
(89)
m-11n-1,mm4
Since, ()) are eigenfunctions of the operator L
38 we can conclude that:
TBi Th
(m)) (n)
Ea-PA
1 (a))() 0,
m 1,7 1.
and if 7/2 & 72 E 73... < Va are the eigenvalues for Φi, 02, Ø5. ........... où under the decomposition of
(-))(-) then:
Bar -gn 02)) = 22 Σ 7 ==1
(1,0)²
(90)
Recall, we also aware of a condition on the regularization term: 1
V2 x T..
ΣA
6
1 +
V
क. EA
Z.
d
1/
(
ΣA
d
?
03
d Σ
(n()))) 2
(91)
j=1
E
(
2
< 1
+
E
Vi.
(92)
In order to show that the projection of &. on $* is significant, we need to argue that the term (i) is small. The argument for this begins with the condition on invariance loss, and Ej 17
the fact that 71 72 & & T & Yh41
Ta:
Σ
11
(1)
Ti
Mh+1
Σ
d
(n,,)))² 2
(93)
2
j= k+1
j=k+1
Σ
d
(1))))
2
<
E
(94)
27x+1
j 11
37

---

Extending the above result vi by simply adding the bounds completes the claim of our first result
in Theorem 13 Next, will lower bound the eigenvalue 76+1- Recall that, -5-1 (1/3
(5)
1
Thus,
278+1
n (
Σ 7/ (n10)) & kop+1 2
(95)
2
We assume that all eigenvalues are strietly positive, which is true under our augmentation distribution. Given, 7 2 " we can rearrange the above to get:
2
(1-1)
71
7k+1
(96)
hee
k
This completes the claim of our second result in Theorem
13
E.1.3 Proof of Theorem
In this section, prove our main theorem about the recovery of both spurious Waps invariant win features by the contrastive learning feature backbone, and also amplification of the invariant over the spurious feature (where amplification is defined relatively with respect to what is observed in the data distribution alone). We begin by defining some quantities needed for analysis, that are fully determined by the choice of problem parameters for the model in (6).
From Section 4 we recall the definitions of Win := [w* ......... 0] and Usp :- [o...... O. w'] where w/ 1d.// V dep- Let us now define u1 1/2 as the top two eigenvectors Σa with eigenvalues \1 A2 0, (note that in our problem setup both AA and Σ are full rank positive definite matrices), and := / Next we define a as the angle between 01 and Win- ie., cos(a) = un] Win Based on the definitions of a and т, both of which are fully determined by the eigen decomposition of the gost-augmentation feature covariance matrix AA now restate Theorem
Theorem 14 (Formal; CL recovers both invariant Win and spurious Wap but amplifies win). Under Assumption 4 (w" = dam///dm), the CL solution oa=[01, $2...., Φk satisfies Φ5 Win Φ) Wap 0 Vj > 3. For T, a as defined above, the solution for Φ1, Φ2 is:
Tw" Tw" co)(T) w/ 1/7,
w² cos 0, sin 0 w' w/tc)(())
sin 0, cos 0
where 0 & a, & 7/2. Let us redefine Φ1 clW + Cy and Φ2 c2 + C1Wsp-
For constants K1, K2 0, y
KiKa/omp dap K2./K3, Ve 0, 3o such that for dsp Ospe
K₁ KjK3dnn
K1 KiKddm
Ci
+ >
Lo (din - 1)
Lo (din 1)
L dap
L dap
+
2
C,
7
C4
7
where L. + K2.
Proof. We will first show that the only components of interest are Φi, Φ2. Then, we will prove conditions on the amplification of win over Wap Φi, Φ2. Following the proof overview:
I. When w' = / / din from the closed form expressions for ΣA and E. show that the solution returned by solving the Barlow Twins objective depends on win and Wep only through the first two components Φ1, Ø2.
38

---

II. For the components Φ1 Φ2, we will show that the dependence along win is amplified compared to ussp when the target data sufficiently denoises the spurious feature (i.e., Sp sufficiently large).
Part-l:
We can divide the space & into two subspaces that are perpendicular to each other. The first subspace
W (by Win + b2 Wap : b1, b2 R], i.e. the rank subspace spanned by Win and Wspp The second subspace is W1 where W1 = {u e R : u Win = O, u W'sp = 0). Then, from Lemma 23
can conclude that the matrix EA can be written as:
Σa Eaw + Eawi
1 (72 1/ad.) + o1/s(1 1/dw)) - wn== (de//2 + 1/3 62p + 1/6) w wt
W /2 w wtT
EAw = 4 // w w'w"
(97)
where Eaw_ = Ea-PA [w. (II,, (a)) is the covariance matrix the null space W, and Tw (a) is the projection augmentation a into the null space of W, ie. the covariance matrix in define:
the space of non- non-predie on-preddictive (noise) features. Similarly
Σ = Ew + Em
/ w wT Ew A (//dv0/2 wwwt (dwo/2 + 22//2) w WT
w- 72 -/2.w="*
(98)
Here again Ew, Ex-Py [w (Ee-Unif(o. (c [ (Eo~Unif(o, ())):))(( is the co- variance matrix of mean augmentations after they are projected onto the null space of predictive features. The above decomposition also follows from result in Lemma 23
3 the closed form expression for the solution returned by optimizing the Barlow Twins objective in is U Σ 1/2 where U are the top-k eigenvectors of:
From Proposition
Σ E
(99)
When w² 1d / din then EAwy Sw, + B where B is diagonal matrix with diagonal given by diag( (Ew,). Further, since diag (w_) = p 1a for some constant > 0, the eigenvectors of Ew, and Eaw, are exactly the same. Hence, when we consider the SVD of the expression Σ "E the matrices Eaw, and Σw. have no effect on the SVD components that lie along the span of the predictive features. In fact, we only need to consider two rank 2 matrices (first terms
in (77) and only do the SVD of A'
1/2 Σw -' Sw
There are only two eigenvectors of An Ew ΣT We use Å1 A2 denote the eigenval- ues of Eaw, and [cos(a:)"*, sin())w"] [sin(a)"",- ccs(a)w"] for the corresponding eigen- vectors. Similarly,
X1, Xa denote the eigenvalues of Ew, and [cos(3)w", sin(3)wr) Siin{)ww" cos( (a))) w'J for the corresponding eigenvectors. Let SVDz(.) denote the operation of obtaining the singular vectors of matrix. Then, compute the components of the final expression:
SV 1/22 T T that lies along the span of predictive features (in W), we need only look at the decomposition of the following matrix:
VT. 0
cos 0
sin(
1/VAT, 0 1/v
cos(a- - 3), sin(a Bnna-B))
SVD.
sin(a - 3), -cos(a- B -
sin cos(()
0, T
(100)
Based the above definitions of 0, X1, A2, can then formulate ái and Φ2 in the following way:
39

---

cos(a)
sin(()
w'
w
cos
sin(0)
[61, 22)
A2
(101)
w
sinta)
W
cos(a)
sin 0 cos
Vx
To summarize, using arguments in Lemma focus on just two rank two matrices Eaw> Ew in the operation: SVD (E 7 1/2 ) 1/2 The other singular vectors from the SVD only impact directions that span W1. and the singular vectors obtained by considering only the rank 2 matrices lie only in the space of W.
23 and the fact that w" 1d, / din, we can afford to
Part-ll:
From the previous part we obtained forms of Φ1, d2 in terms of: X1, A2, a, 0, all of which fully specified by the SVD of Aw and Ew. we define = AA1 Vxa"
we can evaluate C12 C22 C32 Cj as:
C1 cot(a)
+ tan
(102)
C2 cot(a) tan
(103)
1
C3 cot(a) tan
(104)
C1 Lan 0)
+ cot(a)
(105)
Now, we are ready to begin proofs for our claims on the amplification factors, i.e. on the ratios ca/es. lo2/cal.
We will first prove some limiting conditions for ci/e3, followed by those on le2/ca). For each of these conditions we will rely on the forms for c,, C2, C3, derived in the previous part, in terms of 0, (where a, 0 & m/2). We will also rely on some lemmas that characterize the asymptotic behavior of a. 0 and 7 as we increase Sp..
We defer the full proof of these helper lemmas to later sections.
Asymptotic behavior of c1/c3.
From Lemma
25 and Lemma when Ki/V3 and Ssp = K22 2, then:
lim C1 cot a + tan 0
K KiK
lim T tan (1+ K3) 1/d..)'
(106)
C3 1 cot tan
where we apply Moore- Osgood when applying limits on intermediate forms. We can do this since tan 0 approaches a constant, and each of cot a, J and tan & continuous and smooth functions of
(see Lemma 24
Asymptotic behavior of |0//a//-
When we consider the limiting behavior of ca/ouz, as we increase or equivalently osp when ? Ki/// and Ssp K2v2, then get:
- + cot(ai) tan(O)
lim
(107)
C42
(an( + cot(a)=
From Lemma 26
tan 0 - 0. Next, if we consider lim, - = tan e/n lim x tan 0 2/72. For 2/73, we invoke Lemma 28 which states that when Ki// and Osp = K2v 2, then:
2020/311 1/dm.)
lim
(108)
4/3K3
Further, in our bound on 61/ 61/e3, we derived that Lan 0 Ki (133/14 (1-V/e.. Once again using Osgood plug this along with (08]] to get:
40

---

(a)
K K1K K3
lim
(109)
200
(1 + K2) + 4K2)
Finally, from Lemma 27 when = Ki// and Ssp = K2v2, then:
K
lim 2-00 tan at
(110)
(1 + 4/a33)
Plugging,
109 and
into
107 we get the following limit:
1 + K2
lim
(111)
C42
K1
Since Kj K1y
lim x
C27
+
K2
lim 2000
C caydgy
1 1 K3
(112)
C4
K1
dap
K1
Since both ei/eg and ca/cal are continuous functions of with lim inf=-ac and lim simsupp_ez converg- ing to the limits in [06 and 107 for both quantities respectively, we conclude that Ve there exists apu such that for all sp spg. the following is true:
K2 K2K
K K3din
2o 2 (din 1)
+
213 I
2o (din
1)
(113)
(1 K2) dda
(1 + K2 K /dap
+
(114)
This completes both Part-I and Part-ll of the proof for Theorem
E.1.4 Proof Corollary
Corollary 15 (CL improves OOD error over ERM but is still imperfect). For Y Ssp. dap defined as in Theorem 5 3 such that Va 2 Jsp1 the target accuracy of CL (linear predictor on Pa) is 0.5 erf L' 7//2/oww) and & 0.5 erfe (-AL' 7///2o.)), where L' K3KK/02, (1-)) When Ssp1 Om 1/dm, the lower bound accuracy is strictly better than ERM from scratch.
Proof. Recall from Theorem 14 all Φ;. for j 2 3, lie in the null space of win and Wap- Since, the predictive features are strictly contained in the rank two space spanned by Win and Waps without loss of generality we can restrict ourselves to the case where k 2, and when doing training head h = [h,, h R2 over contrastive pretrained representations using source labeled data, get the following max margin solution:
h 4 03 v dap h2 = 02 7 Ca v dep
(115)
Without loss of generality we can divide both h and h2 by h1 and get the final classifier to be
Φ1 +
hg hi
Φ2:
h2 h1
(crwm + CyWep) +
(c2Wmn + cgWap)
(027 C1 Cay
(c + (3 +
(c + wgwa))
(116)
(crr ca dap)
From Lemma 29 be the following:
we can derive the target accuracy of the classifier h on top of CL representations to
41

---

c1 1 8c2 7
e.f
(117)
C3 + Scs
V20sp
where B = (canttay (oros
Substituting 3 into the expression
4 get:
og +/r4
oin an+ c8n+ + 62c4y Jap
(118)
c1037 + 2
ddy dap C2047 + oj dap
We first substitute expressions for c1, C2, expression. Then for = K1/ /z, sp K we substitute the expressions for cot a, tan A. and
from I02
103
104
and (055 in the above
T = A1/22 with their corresponding closed form expressions (as functions of 2) from Lemma 24 On the resulting expression we apply do repeated applications of L'Hôpital's rule to get the following result:
lim cin + eaa Jap + o7 c2C4y dap
2K
(119)
01037 + 25 dap 02C4Y + ei dap
(1 1/dw.)
in
Based on y, dap sp defined in Theorem Csp 20 Jsp1"
and 119) we can conclude that 30 such that for all 5
4K3Kg o a1 3/dw.)
cin + 11cs + ei + c2 dap
K3K1 0 (1 - 1/di..)
(120)
c,037 + c dap + C2047 + eiv dap
Finally, applying (100) Lemma 29 we conclude the following:
When 7 Ki KiKa/oap dap
on KGg there exists Osp1 such that for any Jsp
Jsp1' target accuracy of CL is least K2K,
crfe (-I'. /20
and at most 0.5 (-4L'- /20
where L' (1-1/__)
Comparison with ERM. Recall from Theorem 8 the performance of ERM classifier (trained from scratch) 0.5 erfe /2dy/aa The lower bound on performance of classifier over representations is strictly better than ERM when:
L'
V dap
K2K1
? dap
K3K1 1/dm.))
K K1K
0
1/dm))
2
ap Oin
V1
1/diu
pap
0in v1 1/24n-
This completes our proof of Corollary 6
E.2 Analysis of STOC: Formal Statement of Theorem 7
Recall ERM solution contrastive pretraining. We showed that without loss of generality when k (the output dimensionality of Φ) is greater than 2, we can restrict & to 2 and the & can denoted as [di, dul where Φ1 -iw CyWup and Φ2 Czw" CgWap. The ERM solution of the linear head
is then given by h1, h2 e R:
h1
C1 7y C3
dap and h2 = C2 + CA
dap-
(121)
STOC performs self- training of the linear head over the CL solution. Before introducing the result, we need some additional notation. Let h denote the solution of the linear head at iterate l. Without loss of generality, assume that the coefficients in Φ1 CyWin + cytlipp and Φ C2 + C4Wlsp are such that 62 is positive and C1, C3, and 64 are negative, Moreover, for simplicity exposition, assume that |cal > |ca/-
42

---

Theorem 16. Under the conditions of Corollary 15 and when
dap 102+a)ooo
the target accuracy of ST over CL is lower bounded by 0.5 erfe |<2/o|| erfc (-L 2 with L 1.
7/v2m)))
0.5
Before proving Theorem 16 we first connect the condition result obtained with contrastive learning.
Tap (r2
3
-4-
v
with the
Remark 1.
We first argue that te2 Fele
term dominates and hence, if have
C4 (02+01) m
then we get the result in Theorem 16
First, recall that as sp increases, have 9
converge to
2Lof. (da
K₁ K2dd
C2 and
ei 62
0. Using these limits, we get:
2
K2
2L in (din -1) 1)
(122)
sp
K2
3/2
K KjKžd
2/3
which reduces the following condition: dap < K2K
2/3
2L (dm--1)
Proof. First, we create an outline the proof. We argue about the updates of ht showing that both and h2 increase with | becoming greater than [h4] for some large Then we show that [42] > [h] is sufficient to obtain near peer--erffcct target generalization.
Part
Recall the loss of used for self- self-training of h:
(h) = Ex)(x) ((h T Qx, sgn(h" sgn(hT ox))]
(123)
Ep+(z) eexp (- (nTx)))
(124)
E.-,((011) [exp (- kinh + canhe + (c30sp/11 + c20sp)2) =D]
(125)
Define μ4, = cryhf 027 and or ca c4 With this notation, we can re-write the loss in (25) as (h²) = E. (o, [exp 1 + =[)].
Similar to the the treatment in Theorem g we now derive a closed-form expression of Cat (h') in Lemma 30
1
oī erfe
(- Mr +
a + nt
Me.
Lus (1e((t)) 1/2
exp
2
14
~20,
v2
+ exp
2
erfe
2200
+
/
(126)
Define:
( o7
Pr.
A1(1), exp
exp
14
erfc
22
v2
2
= =V -ex
exp
207
0t
0t
(127)
A2(11, exp
14
erfc
P4
v V20
/2
2
Pt
= exp
0x +
(128)
20
As((),0)) exp
2
11
(129)
T
20
43

---

Let h1 denote the un-normalized gradient descent update at iterate t + 1. We have:
aL (h²)
7+ h² 7) @h
(130)
Now we will individually argue about the update of 1 First, we have:
M1t1 11--1 11
2hn
M++1 1i--1 17 LA1 (01030ap -17) + A2 (0r030ap 917) Agc3oapl
(131)
61
and second, we have:
hit11 1/2 11 2c (h1)
dhv2
Ti5t1 1/2 n [A1 (arc44sp - -22) + A2 (01c44sp 027) A3c40
(132)
62
We will now argue the conditions under which h22 increases till its value reaches 1/ 1/v2. In particular, we will argue that when h/ is negative, the norm [A1] decreases and when h becomes positive, then its norm increases. We show that the following three conditions are sufficient to argue the increasing value of hț: for all t. we have (i) Pr 3 pe and lo,1 < de for constant Me =cc > / and o, = |c4 ; (ii) 82 < O: (iii) 182) e 81. In Lemma 18, we argue that our assumption on the initialization of the backbone learned with BT implies the previous three conditions.
Case-1. When h2 is negative (and after the update, it remains negative). Then we want argue the following:
(h1- n222)
(hh - 2)222 + (h{ - 181)2 & (ht)2
(133)
(h/ - =22)²
$ (hh - n722)2 + (h) - 17,1)
(134)
(h2)²
h122 26 2112212
4
h22 17282 2nh252 + hi² 17287
2nh
(h2)2
(135)
2 211ō2h2
1+
11
17203 2nhh 2 + 17287 2
(136)
(hb)²
1/ - 21
11 2n111502 17² 2m 5, (h5)2
(137)
1/ )283(1()2 (1)])))))))((1
27 (hb)2
(138)
720)) - x
2n/ (h2)²
(139)
(1+)) -
-
(11)((1)) + 178 (h()) < 2 [nd2(h)) - (h²))
(140)
[nt)(1tt + n/1 (nt) & 2h
(141)
Since 52 0, 182| |6, and h4 hf < 0, we have [112 (hf) 99, (nt) as positive. This implies inequality (140) to [141 and for small enough 77, (141) will continue to hold true.
44

---

Case-2. When h is positive but less than 1/v2. Then we want to argue the following:
(122 - 1722)
(h2)²
(142)
(h2 n122)² + (hî 1722)
(h₂ 1102)
(122 n722)² (hi n
(143)
(h2)²
h22 + 172
21122h2
11² + 1 2nh282 + 112 + + 2nh1d1
(h2)²
(144)
14 1/ -211222
1+ 1 1 21y1 + 1 2n
(145)
(h2)²²
n/82 2nd2211
[r/ 27/11222 172 2nyh 5.] (15)²
(146)
1 {8)(1)) - (2))) r²)(())) - 27/h 81 (hx)²
(147)
(29)2 r/b)( 2no2h 2nh (h2)
(148)
- 1o) (1)2(1() + n71 (h6) 2hgh4 [182(11) - 1751
(149)
(166(11() + n711 (h:)] > 2hzh1
(150)
Since 52 < 0, 1821 1811. h $ -1/v2 and 0 hy 1/v2, we have [171 (nd))({f) no1 (ha)] as positive. This implics incquality (149) to (10). Focusing on (10),, we note that h 82 is positive and greater in magnitude than h4 81. Moreover, since high is negative, (150) will continue to hold true.
Now, when h2 is positive and greater than 1/v2,, then h2 will stay in that region. Convergence of STOC together with conditions of convergence as in Lemma 17 will imply that the convergence hi
will remain greater than 12, such that A/c á1, Now we bound the target error of STOC. hg
82
Part To bound the accuracy at any iterate when 1/2 > 1/v2, we have from Lemma 29
Ep, y (neT dc1z) of EE-NiO..)
cryht 02
(151)
C3 + c1aaphbl
We now upper bound and lower bound the fraction
in RHS in 151): (i) cn +
le Mf ht
co hh since both eryh4 and czyht have same sign; (ii) leg + cp & lc1 because (chdsphty i |c3 and they have opposite signs. Hence, from ([5)). we have:
Ept y. (Ne )n1)) = 00 EE.A(O.11)
c27hts
C27
>>
= Es-A((01)
2
cpp
Cea
(152)
Substituting the definition of erfe, the expression 152 gives us the required lower bound on the target accuracy.
Lemma 17 (Convergence of STOC). Assume the gradient updates as in 131 and 132
Then STOC Aif & For > tor [13l and (122 make no updates to the linear h.
converges at t to when
8.
When the gradient updates 8n and 6g are such that 14+11 matches 14, we have convergence of STOC.
Proof.
45

---

(h2 17222
(n3 - 11622 + (Mi - - =11)22
(153)
(11g - -182)²
-h12 - n/22)² + (hi - -7,1)
(154)
(hb)²
h₂2 5263 21162112
h22 + + 2nh202 + +ni² +n888 2nhf
(h2)²
(155)
1 1+ n263 2112222
1 n/2 21hh + - 2 (156)
(h2)²
1/ n263 21p5221
[18:83 - 21)11262 + 1/ 2n 51 (ng)²
(157)
1/ 1²83(11))2 - 2n622 = 1889(1622 - 27yh (hb) 1/0)2(1))² - 176)(1))2² (/52))(h1)² 2nh 51 (h2)² [110((15) - noi (o) [TT6((1]] + 1781 (16)] = 24gh4 [Td2(1h] - 1701 (12)
(158)
(159)
(160)
Thus either (1)) 171 (h5)]
0 or (1f) + n7 (15)]
(
2h244- Since n is such that
h1 - 1701 < 0. (ht) + 1752 (12)
* 245h4 implying that [1)2(111) - (k5)) = 0 giving us the
required condition.
L
Lemma 18. Under the initialization conditions assumed in Theorem
16 for all I, we have: (i)
14 E Pa and lar| & for constant μrc = |c1 - 71/2 and a. = spl:
(ii)
62 < 0; (iii) |82| > 81,
where 81 A (010335s c17) + A2 (o + c17) Azc3osp and 82 A (axCa
c27) + A2 . (atc10ep + +22) - ap for A1. A2 and Ag defined in 127
(128) and 129).
Proof. Recall, 14 cn + 027hh and o; c30sphi + cpo First, we argue that be increases from the initialization value. Notice that Mu cryh + h2. Due to Corollary 15 we have h2 > 0. And since [c2] > |c1]. we get Po 2 |cn as both ej and hi are of same sign. Moreover, as training progresses with hi remaining negative and hi remaining positive, we have 14 stays greater than /oo-
Recall the definition of A1, A2, and Ag in 127 aj (Ht,, and a2(M),
128 and 129 Moreover, recall the definition of
2
Hi
#
a1 a1 01) = 1 exp
20
r
oo
+
-
o,
(161)
and
2
(_
He
M4
2
a2(H), 01) = = exp
r
ot +
+r σ:
(162)
20
Tt
σt
Thus, we have as (He, o,) AA = A and a2(4,, o1) - Ag = o. (A2 - 3 Ass..
Replacing the
definition of A,, A2, and Ag in 82 and 82 we get:
σ1 sp - a2(ue, 01) + c1701(H and 82 = opp4psp a2(1u, 01) + 02701 o1)
(163)
We now upper bound and lower bound an and a2 by using the properties ofr We use Taylor's expansion on r (-) and we get:
(
(a. Mt)
(M)) (.)
2 (1t) (164)
r (())) +r (ot) (r)))
<
$ <
+r (r
+1" (at)
(0,)
σ1
and similarly, we get:
2
r (o.)) r' (a.)
Mt (1
r" (or)
[e
r
σt
< < r' (0))
(
+ R²
0
T2 (165)
46

---

where R" = rr (ou). This is because r" (+) takes positive values and is a decreasing function in oz We now lower bound an (Ht, oz) and upper bound a2(14, Ft):
(refer Lemma 21
2r' (at)
(166)
V 22exp
201
02( σr.)
14 2
3 2r (or) + (oi)
(167)
V 2 x
exp
H2 200
Fe
Part-1. We first prove that 82 & O. Substituting the lower bound and upper bound in (63 gives us the following as stricter sufficient condition (i.e., (168) implies 82 $ 0):
2r (o.) (
Ht 0
2
2
ap (-ca)
3 2r (or)
f1
(168)
7.02
2 2
2r + +1"(ar)
14
2r (σt)
14
7:02
(169)
(1
0x
Ssp
(-c4)
- (rt) + r (0t)
U1
2
2r (at)
7 C2
3 0
(170)
0x
a
spp (-ca)
C4)
2r( ao + + (ot)
1
2 - 21 (ot)
14
02
3 0
(171)
Tt
3sp
(-ca)
= 2r (o1) + r" (0,)
2r' (0t)
7 0
2 0
(172)
σt
ssp
(-c1
r (ot)
2r (0t)
1- pr
7. C2
00
(173)
Jsp" (-ca)
Thus, if we have U
اممم= then 168] holds true. y-
Part-2. Next, we prove that |69| > 81. Substituting the lower bound and upper bound in ( gives
us the following as stricter a sufficient condition (i.e., (174) implies |óg| > 81):
(o,) + +1" (ot)
ft 2
2
ap (-c4 - c3)
3 2r (at)
11
(174)
γ (02 + +c)
2r (o,) + +1" (at))
H4
2
2
> 2r (ot)
14
7 (02 + G1)
(175)
0t
Jsp (-44 - -ca)
>2r(at) " (at)
2
2/ (a.)
μ4
7 (02 + CI)
(176)
01
dt
Jsp (-C4 (3)
7 (02 + (1)
2r oo + 1" (ot)
2 2 (0t)
> 0
(177)
σt
Tap
(-44 03)
7 (02 + 91)
21' + 1 (0.)
21 (at) Ht
> 0
(178)
Jep (-04 C3)
2 r" + 2r (ot)
Mt 7. (02 + t()
3 0
(179)
asp (-C4 03)
Thus, if we have p 2 مم(ممーم) then 174 holds true which in-turn implies |62| > 8j. Plugging in Ht 2 Pa. we get the required condition.
((c+,))
47

---

E.3
Analysis for SSL
For SSL analysis, we argue that the projection learned by contrastive pretraining can significantly improve the generalization of the linear head learned on top, leaving little to no room for improvement for self-training. Our analysis leverages the margin- based bound for linear models from Kakade et al. 45 Before introducing the result, we present some additional notation. Let (rr
denote 0-1 error of a classifier on a distribution D. Define 0-1 error with margin y as Err (w) [=wT2
Theorem 19 (Corollary 6 in Kakade et al. 45 probability at least -: 8:
For all classifiers w and margin % we have with
B
1
log(1/5)
log (4g(l))244B/7))
Erry (w) & Err (w) + 4
(180)
n
n
where B an upper bound on the Eg norm of the input points 2.
When Err (w) is close zero, the denominating term in RHS of (80 is 4 7 V n. With Proposition 3
CL solution & obtained on the target domain alone (for SSL setup) is Win when = 1. For larger sss
the CL solution is dominated by the Φ1 Win- Thus, SSL mainly reduces the B on the projected data by reducing the dependency from order / to where is the dimensionality of the output of without altering the margin. Thus, we get a tighter upper bound for linear probing performed on top CL features when compared with linear probing done on inputs directly.
Intuitively, since the target data has only one predictive feature (along Win),, CL. directly recovers this predictive feature as it is the predominant direction that minimizes invariance loss.
F
Limitations of Prior Work
F.1
Contrastive learning analysis
Prior works that analyze contrastive learning show that minimizers of the CL objective recover clusters in the augmentation graph, which weights pairs of augmentations with their probability of being sampled as positive pair [39 73 44 When there is no distribution shift in the downstream task, assumptions made on the graph in the form of consistency of augmentations with downstream labels, is sufficient to ensure that linear probed head has good ID generalization. Under distribution shift, these assumptions are not sufficient and stronger ones are needed. E.g. some works assume that same-domain/llass examples are weighted higher that cross-class cross-domain pairs 40 (6).
Using notation defined in (7). the assumption on the augmentation graph requires cross-class and same-domain weights (3)) to be higher than cross-class and cross-doman weights (7). It is unclear if examples from different classes in the same domain will "connected" if strong spurious features exist in the source domain and augmentations fail to mask them completely (e.g., image background may not be completely masked by augmentations but it maybe perfectly predictive of the label on source domain). In such cases, the linear predictor learnt over CL would fail to generalize OOD. In our toy setup as well, the connectivity assumption fails since on source Tap is perfectly predictive of the label and the augmentations are imperfect, i.e., augmentations do not mask Tsp and examples of different classes do not overlap in source (i.e., 3 = 0). On the other hand, since Tap is now random on target, augmentations of different classes may overlap, i.e., O, thus breaking the connectivity assumption. This is also highlighted in our empirical findings of CL furnishing representations that do not fully enable linear transferability from source target (see Sec. 5). These empirical findings also call into question existing assumptions on data augmentations, highlighting that perfect linear transferability may not typically hold in practice. It is in this setting that we believe self- training can improve over contrastive learning by unlearning source-only features and improving linear transferability.
F.2 Self-training analysis
Some prior works on self-training view it as consistency regularization that constrain pseudolabels
of original samples to be consistent with all their augmentations [12 87 79 This framework
48

---

abstracts the role played by the optimization algorithm and instead evaluates the global minimizer of population objective that enforces consistency of pseudolabels. In addition, certain expansion assumptions on class-conditional distributions are needed to ensure that pseudolabels have good aceuracy on source and target domains. This framework does not account for challenges involved in propagating labels iteratively. For e.g., when augmentation distribution has long tails, the consisteney of pscudolabels depends on the sampling frequency of "favorable" augmentations. As an illustration, consider our augmentation distribution in the toy setup in Sec. If it were not uniform over dimensions, but instead something that was highly skewed, then a large number of augmentations need to be sampled for every data point to propagate pseudolabels successfully from source labeled samples to target unlabeled samples during self-training. This might hurt the performance of ST when we optimizing for only finitely many iterations and over finitely many datapoints. This is why in our analysis we instead adopt the iterative analysis of self-training 17
G Additional Lemmas
In this section we define some additional lemmas that use in theoretical analysis in Lemma 20 (Upper bound and lower bounds on erfe; Kschischang (49)) Define erfc(z)
She exp(-=²) dz. Then we have:
exp(-x²)
2 VR + v x2 + 4/TT
exp(- xx)
V I V22 < erfc(x) <
Lemma 21 (Properties of Mill's ratio (5)) Define the Mill's ratio as r(x) exp (x²/2)
erfe (x/v2) 1/2. Then following assertions are true: (i) (x) is a strictly decreasing log-
convex function; (ii) r((x)= = x- (x) is an increasing function with (x() < 0 for all x; (iii) decreasing function with (=) > for all x; (iv) x² r((x) is
r"(x) I (x) +x² (x)x
decreasing function of x.
Lemma 22 (invariance loss product with operator L). The invariance loss for some & Rd is given as: 2 SA ((a) (a) dPA where the operator L is defined as:
(()) = 0(a) - Sx A+ d') Pa(a)
"(a') da'
Proof.
The invariance loss for di is given by:
Ex-Py Em, Pa aT == =2E, 2E [o(a]]]
21 L ( [
(181)
=2. 0(a)² dp - - d(a) (J,
A+ (a, o(0z) da2 dPA PA(a)
(182)
= 2. ((a) (a))(a) dPA
(183)
Lemma 23, W is the space spanned by Win and Wap, and W1 is the null space W, then for any u E W and any E WL, the covariance along these directions Ea<Pa[a Tu a] 0.
Proof: We can write the covariance over augmentations after we break down the augmentation into two projections: a (lw(a) Iw)
Ea~Pala uv a] Ea~PA [(u (IIw(a) 11w (a))) (v (IIw(a) + 1w (a)))]
(184)
Ea-PA [uu Iw(aa) (o (w]]]
(185)
= u T (Ea~Pa [Iw(a) (a) v= 0
(186)
where the last inequality follows from the fact that Ea-r, [ww [a) Ea [T] Ea-P, [Tw,, (a))*, since the noise in the null space of W drawn independent of the component along W, and furthermore the individual expectations evaluate to zero.
49

---

Lemma 24 (closed-form expressions for eigenvalues and eigenvectors of AA, E), For a 2 x 2 real
a, b c, d
symmetric matrix (a + +6) X2
the eigenvalues \1, X2 are given by the following expressions:
(a + b 0)
A1
2
where 8 = /4c² + (a b)?. Further, the eigenvectors are given by U- = cos(0), sin(0)
where:
sin(O), -cos (0)
b a à
tan
2c
For full proof of these statements see (23]. Here, we will use these statements to arrive at closed form expressions for the eigenvalues and eigenvectors of E.. Σ.
Proof. We can now substitute the above formulae with o, b, c, d taken from the expressions of Σ and Σ, to get the following values: A1 A2 are the eigenvalues of L. with a determining the corresponding eigenvectors [cos(a, a)) sin (a)], [sin(a). - cos(a)]; and Y1, X2 are the eigenvalues of Σ, with 8 determining the corresponding eigenvectors: (3) sin( [sin(3). cos(
A1
1
72
1+
1
im
1
1
dgp
2
1
3dmn
3
d1n
dop + ((12) (1+
1
)) 1
111
dap
2a ap
))
1
+
+
in
-
+
(187)
3dln
3
din
2
3
6
A2
72
1 +
1
in
1
1
+
dgp
+
20
sp
1
8
3dhn
3
dn
2
3
6
((12)
1
1))
dap
20 sp
1
))
2
dop
+
1+
in
1
-
(188)
3din
3
din
2
3
6
dap
o-
dap
2
X1
2 +
+
72d +
72 72-
+
(189)
8
2
2
X2
1
dap
02
?2d +
72
dgp
+
02
(190)
tan(a)
1
dap
2
2
ap
72
1+
1
inn
7V dep
3
3dm
3
din
V 72ddp
((1²
1+
1
1
)
-
dap
202
ap
1
)
(191)
3din
3
din
2
3
dap
(73-(dg))
ddpp +
o2
2
tan(3) (3
72
+ 1 +
(192)
YV dop
2
2
2
Consider the subclass of problem parameters, dap 7,7 Ks/V2 and asp K2y² for fixed constants K1, K2 0 and some variable O, which we can vary to give us different problem instances for our toy model in 6
50

---

K?
1
1
2K 2
A1
1
1
3din
din
2
3
K?
1
2
2K 2
1
+ 1
K? +
1
+
+
1
(193)
3d
3
dn
2
6
1
K
1
2
1
2 2
2K
2
12
1
+
1
+
8
3rlm
3
din
3
K?
1
)
2K3
)))²
K?
+
1+
+
11
(194)
2
3djn
3
dm
2
6
X1
1
K?
2 +
K3
+
K?
KT
K3z
2
(195)
8
2
2
2
2
2
A2
1
K
2 +
K32
K?
(
K?
K32
(196)
8
2
2
2
2
(a)
2 +
2K
K2
+
+
0
in
K1
2
6
2
3din
3
dm
K
1
2
2K
+ σ 1))
2
K?
+
+
+
(197)
2
3d
3
dna
3
1
2
K3
K?
K?
K32
2
tan (a)
+
K?
(198)
K
2
2
2
From Stewart 80)
we can use the closed form expression for the singular vectors of 2 x 2 full rank
a, 6) c, d
asymmetric matrix
The singular vectors are given by
cos 0 sin sin 0, cos 0
where, tan(2f) is given by:
2ac + 2bd
Lan L2n(
a 12 d²
Now, substituting the values in the expression from 100). get singular vectors of the above form
where 0 E [0, 7/2] satisfies:
1 tan
2 tan(33 a): (Ni - T2) Vddeo
(199)
(Ae X1d2) (Ai Xede) tan? B)
Lemma 25 (asymptotic behavior of T tan 0). For y Ks///, Tap K2vE,
K KiK3
lim 7 tan 0 2-
(1 + K2) (1 1/dmm)
Proof. In order to determine the asymptotic nature of tan (f) as - CD, we take the limit of slightly different term first, since we have the closed form expression of t2n(
51

---

and, 2 2tan(a - B] (21//a- -1)
A1
lim 7 (an(20) = =Vx, x2
2-20
(2//22 21/2aa (A12:/A2R8 1) tan 3)
21/22- -1
= 2 lani (r - -3) Xs/Tx= >g/A1 -1'
since it is easy that lim tan (a- B)
A Azd2
- 1) -0.
If use tan 3) tan tan 8
t-t is taa 1 and substitute the functions of 2, for all the quantities in the
above expression using Lemma 24 we derive: lim=--o 7 tan 20 = 2K, (2 (1-1/4n)
Since oc, t20 O, and further from Taylor approximation of tan tan(20) 20. We can use this to derive the limit for r tan 0 which would just be 1/2 2k, ( K3 Ki K3 /3
(1- (1-1/aa) =
Lemma 26 (asymptotic behaviors of cot o; tan 0). For 7 Ks/v2, Osp expressions in Lemma 24
K2y following the
lim cot a
lim tan O.
Proof. For tan 0, since 7 0C, and tan O approaches a constant (from Lemma 25 lim tan 0. For cot a,
we conclude
lim 2
2K3z
1
K? 2
1
)
1+
+
00,
2 +
2
6
3d
3
dim
lim
K2 +
K2
+
1-
2
+
2K3 x
)) OC.
6
1
2
3din
3
din
2
3
Thus, cot a
Lemma 27 (asymptotic behavior of 2 cot a). For ry K1/V2, Jap in Lemma 24
K2 / following the expressions
K₁
lim 2 cot a -+
1 1 4/3K2
Proof. The expression for z cot a or a/ann follows from Lemma 24
2K1
lim cota
$000
p V22 K?
where p-
K?
1
2K3
Applying L'Hôpital's (relevant
3dm
expressions are continuous in 2) rule we get: lim Z col a I+40K?
Lemma 28 (asymptotic behavior of e/+"), yor K2///,, Tsp K2 following the expressions in
Lemma 24
lim 5/1² = 20 1/dmm)
1 +//3K33
Proof. For 7 Xr/22, substituting the relevant expressions from Lemma 24
we get:
2d2
x/7²
2K (1 + 1/3dm)) + 20 (1- 1/d..) p K 12
2 (1 + 1/3dm.. ) + 20 (1 (1- 1/d..)
Ki +
52

---

where p = 8/2 + 2/24/3 1/6. Applying L' L'Hôpital's (relevant expressions are continuous in 2) rule we get: lim 8/7" 22f,//(11 14/g
Lemma 29 (0-1 error of classifier on target), Assume classifier of the form w Win + l Wap where 1,12 and [m= O..., O]T, and wsp ..,,.. 0, /dss/ dxp] Then the target accuracy of this classifier is given by 0.5 erfe V2-12.0pp
11
Proof. Assume (I, y) ~ Pr. Accuracy of w given by Ep, [(sign (w x) = v)}.
Ep, [sign (w (w'x) = =y] Epy [V sign (w 2) 1]
-Ep [y (w x) > 0]
= =Epy [V (z T (4 win + 112 Wap) 0]
=Ep, [y (7 y + 1 dap) > 0]
=
-Bz-N((.1) [(7 h + y 12 up 2) 0]
BE-A((0.1) Iv 1/ up
7 4]
B=-A((.1)
1/2 Ss -7 41]
7 1
B2-A((01)
l2 Jsp
Using the definition of erfe function, we get the aforementioned accuracy expression. Lemma 30. For > and μ E I. we have
g(u, o) =V [exp (- 1 =[]] (exp (0 11) erfe (-H/w20 + 0/v2) + exp (02/2 u) erfe (4/V20 + o/v2))
(200)
(201)
Proof.
The proof uses simple algebra and the definition of erfc function.
g(u,,) BemN((0,)) [exp( (- 1 + =1)]
x
exp (- 11 + x1) cxp
dz
v fm
20²
a
2
exp (- 1 2|) exp
dz
2m
20
2²
x²
exp (-u+ 2) exp
dz
exp (u 2) exp
exxp
dz
2m
20²
2
-
20
Lz
eexp (0²/2 11)
00
exp(-2² dd + exp (02 + 11)
V2c
exp(
expl-2²)dz
+
- (exp (0²/2 14)
erfc (-n/V2o + 22 + exp (0 + n)
erfe (1/v20 + o/12))
53


Reviews:
[{"review_id": "dSg2rgDN8m", "reviewer": "Reviewer_272G", "summary": "This paper investigates the complementary benefits of combining self-training and contrastive pretraining for domain adaptation under distribution shifts. Through an empirical study on 8 benchmarks, the authors demonstrate that applying self-training (FixMatch) after contrastive pretraining (SwAV) yields substantial accuracy gains over either approach alone. To understand this synergy, the authors analyze a simplified theoretical setup indicating that while contrastive pretraining can amplify signal along invariant features, it may retain dependence on spurious source-only correlations. On the other hand, self-training can effectively unlearn these spurious dependencies and improve linear transfer of representations, achieving optimal target performance. The authors further apply linear probing on representations to verify their theoretical findings empirically. Overall, this work highlights the potential of combining self-training and contrastive learning to address challenges posed by distribution shifts, grounded by both empirical evidence and theoretical analysis.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: The paper explores the promising yet underexplored direction of combining self-training and contrastive learning to address distribution shifts. The extensive empirical study systematically investigates their complementary benefits across diverse benchmarks. The theoretical analysis offers unique insights into their synergistic effects.\n\n**Quality**: The empirical study is relatively extensive, spanning 8 datasets with careful controls. Despite simplifying assumptions, the theory makes falsifiable predictions that are precisely analyzed and align well with observations. Additional probing experiments further validate the theoretical intuitions. \n\n**Clarity**: The paper is clearly presented overall. The problem setup and motivation are lucid, and the methods and experiments are thoroughly explained. The authors effectively convey the core conceptual messages and insights from their theoretical analysis. \n\n**Significance**: Distribution shifts ubiquitously challenge ML model generalization in practice. This paper highlights the significant potential of combining self-training and contrastive learning to address this problem, demonstrating substantial empirical gains and proposing explanations grounded in both theory and experiments. Overall, I think this paper will be of interest to the ML research community of distribution shifts.", "weaknesses": "**Small Pre-training Set**: The authors have chosen to train models using contrastive learning (CL) from scratch on a selection of small datasets from BREEDS and WILDS. The authors have justified this approach by stating, \"We have opted not to use off-the-shelf pretrained models (e.g., on Imagenet [67]) to avoid confounding our conclusions about contrastive pretraining.\" However, in practice, pretraining CL models on small datasets is not a common practice, given the availability of powerful off-the-shelf CL models that have been pretrained on larger datasets (e.g., from SimCLR, iBot to DINOv2). If the paper's results only apply to CL models pretrained on small datasets and do not generalize to more powerful contemporary CL models, the utility of this work could be limited. I would recommend that the authors conduct studies of modern off-the-shelf CL models to strengthen this work. For instance, off-the-shelf ImageNet-pretrained CL models could be used as initialization, followed by self-training, and then evaluation on various shifted datasets (numerous ImageNet shifted datasets are available). Please note, it is not necessary to strive for results during the rebuttal period. This paper is already commendable in my view, I merely want to offer suggestions that could further enhance its impact.\n\n**Limited Combination of CL+ST Algorithms** In this study, the authors have exclusively utilized SwAV+FixMatch, which are indeed effective algorithms. However, the presentation would be more compelling if a wider range of combinations were explored. Given that the authors employ Barlow Twins in their theoretical analysis, would it not be more fitting to also include Barlow Twins as a CL algorithm in the empirical studies?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment of our work and their detailed and constructive feedback. For the rebuttal, we **added new results with Barlow Twins** as the pretraining algorithm and some **preliminary results with Imagenet pretrained networks**.  Please let us know if this addresses all outstanding concerns or if there are any additional questions.\n\n> **Small Pretraining Set** \n\nThanks for your suggestion; we agree this would be an interesting direction of study that could further strengthen the results. We performed preliminary experiments where finetune Imagenet pretrained networks and performed experiments with FixMatch training (e.g., we replace contrastive pretraining with imagenet pretraining) and we observe that FixMatch continues to improve over ERM (source-only) models both pretrained with Imagenet.  \n\n| Dataset      | ERM (Imagenet pretrained)   |FixMatch (Imagenet pretrained) |\n|--------------|-------|------------------|\n| OfficeHome (avg on 3 shifts)   | 47.1 | 57.4            | \n| Visda | 44.9 | 72.8           |\n\nNote, we did not perform these experiments with BREEDs datasets, because they are subsets of Imagenet and Imagenet-pretraining leaks information about target. We will plan to explore the impact of leveraging large off-the-shelf pretrained models, e.g. DINOv2 and CLIP for our revision. \n\n\n> **Results with Barlow Twins as a CL algorithm** \n\nWe have included results with BT as a CL algorithm and Pseudolabeling as self-training algorithm in the general response. Overall, we observe that results with these two new algorithms match the trends we observed with our default choices. This highlights that the complementary benefits of self-training and contrastive learning hold across different variations of each of them. We thank the reviewer for their suggestion.\n"}, {"review_id": "h7McQCO2Ls", "reviewer": "Reviewer_fFuY", "summary": "This paper empirically explores and theoretically studies the complementary benefits of using self-training (ST) and contrastive learning (CL) for unsupervised domain adaptation (UDA), where unlabeled data is available from source and target domains, whereas labels are only available from the source domain. Firstly, experiments on many distribution shift datasets show that combining self-training over contrastive learning (STOC) yields significant benefits for target domain accuracy (~5% on average) over just doing CL or ST. However the benefit in-distribution is shown to be much lower (<1%).\n\nMotivated by these findings, the paper delves into the theoretical study of this phenomenon through a toy Gaussian data model, where each example is composed of domain-invariant (useful for source and target) and spurious features (only useful for source). Experiments on the toy model are shown to follow similar trends to real data. Through analysis on this toy model, the paper provides the following intuitions: \n\n(a) ST can learn a good target classifier if it starts from a good enough initial classifier\n\n(b) ERM on source domain cannot provide a good initializer because it focusses too much on spurious features\n\n(c) CL (with some \"generic\" augmentations) learns representations that focus more on domain-invariant features, thus providing better features for ST to improve. Although CL classifier itself is not sufficient for good target performance\n\nThis theoretical model provides many insights into the role of CL and ST. Finally the paper empirically verifies some of these claims through further probing experiments on real data. ", "questions": "(Q1) How many labeled examples were used for experiments in Section 5? I'm wondering if the target probe results in Fig. 3 are due to worse sample complexity rather than expressivity of the features themselves\n\n(Q2) What are the limitations of the proposed theoretical framework? Does the toy model fail in crucial ways to capture realistic distributions? Does the theory for this model predict something that does not hold in practice. A discussion about this would be useful for future work on this topic\n\n(Q3) Does the choice of contrastive learning/self-training method affect the findings?\n\n(Q4) Does linear probe (instead of fine-tuning everything) also work well in practice?", "limitations": "See Q2 above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper studies an unexplored (to my knowledge) space of combining two popular ideas for domain adaptation. The idea is natural and seemingly effective\n\n- Experiments on standard datasets are convincing enough on the efficacy of the proposed approach. Theoretical analysis on the toy example seems solid, and provides useful intuitions & insights into why the proposed approach could work well. Overall the quality of the technical work seems good. The insights about \"CL provides better features while ST improves the head\" is a clean contribution\n\n- The paper is clearly written and easy to follow. Sufficient intuitions are provided for many of the theoretical claims. \n\nI didn't read through all the proofs, but the intuitions made sense and the contrastive learning results seemed believable. On the whole, I think this is a solid contribution and vote for accepting.", "weaknesses": "- One minor criticism is about the presentation of Section 5. That one required multiple passes to follow, and it might help to include a clearer description of what is being tested. For instance in L377, it would help to explain how the 14% number was calculated. Some more questions about this in the next section\n\n- A bit more discussion about prior work, in the main paper, would have been useful to see. Sections 5 and 6 do a bit of this in some parts, but I only partially understand how this analysis different from previous ones, especially for self-training\n\n- The paper discusses contrastive learning and self-training in general, but only tests on one pair of methods (SwaV and FixMatch). Including more methods (even in 1 setting) would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments and positive feedback. In our revision, we will elaborate on the setup in Sec 5, and move the discussion on related work from App B to the main paper. We **add experiments with two additional combinations of CL+ST** algorithms (see general response) and hope that our responses address any outstanding concerns. Please let us know if there are any additional questions. \n\n> **In L377 … explain how the 14% number was calculated.**\n\nThe 14% target probe performance difference is calculated based on the right half of Fig 3. The target linear probe performance of CL+ST (80.7%) is about 14% greater than that of ST (67.1%). The difference is higher when comparing CL with ERM. This leads us to believe that contrastive pretraining significantly raises the ceiling on target performance. We apologize for the confusion and will make this clearer in our final version.\n\n>  **More discussion about prior work, especially for self-training.**\n\nWe deferred discussion on extended related works to App  B. Further, in App G.2 we specifically focus on distinguishing our analysis from prior self-training analyses that treat self-training as a consistency regularization objective. In principle, these works assume strong expansion assumptions on class conditional distributions, and ignore the challenges involved in propagating pseudolabels iteratively when the expansion assumptions are difficult to satisfy. If we get an extra page for the final version, we will move this discussion to the main paper.\n\n> **Only one pair of CL+ST algorithms. Does the choice of contrastive learning/self-training method affect the findings?**\n\nPlease see the general response for our reply to this question. We have included results with BT as a CL algorithm and Pseudolabeling as self-training algorithm in the general response. This gives us two additional pairs for  CL + ST. Overall, we observe that results with these two new algorithms match the trends we observed with our default choices. This highlights that the complementary benefits of self-training and contrastive learning hold across different variations of each of them. We thank the reviewer for their suggestion.\n \nIn theory, we analyze Barlow Twins which has been shown to be equivalent to spectral contrastive loss, and even other non-contrastive objectives (see L949 in App E.2 for more). Similarly, the self-training method we analyze in Sec 4 captures generic iterative pseudolabeling methods done in two stages. \n\n\n> **How many labeled examples were used for experiments in Section 5?** \n\nFor each dataset the number of training examples for linear probes are of order $10^4$ (except for OfficeHome where the target dataset is of order 3000) obtained by 80:20 split of all the target data. The impact of finite sample nature of target samples is negligible because we only train a linear head over the representations, so the generalization error is very small $O(\\sqrt{1/n})$ where $n$ is number of samples used to learn head. \n\n\n> **What are the limitations of the proposed theoretical framework? Does the toy model fail in crucial ways to capture realistic distributions?**                                                                                                                                                                                                                                                                                                                                                         \n\nFollowing are some limitations of our theoretical setup for analyzing the complementary nature of CL and ST, which we are actively exploring as directions of future work. We mention some of these in Appendix A.\n\n-  We only analyze the case of spurious correlations in source data, as opposed to more general shifts in the covariate distribution.\n\n- Our theory assumes general augmentations that scale each feature independently (similar to [2]) and doesn’t capture more specific conditions for the augmentations.\n\n- While empirically we see our trends hold with full finetuning (Sec 4.5, App E.4), we only analyze linear probing (as done in prior works [1, 3]).\n\n\n> **Does the theory for this model predict something that does not hold in practice** \n\nThe only important trend that shows a deviation between theory and practice is the following: self-training performs as worse as ERM (Fig 2. and Thm. 2), whereas in practice self-training is not necessarily worse (Sec 3). This is mainly due to the normalization step in the self-training iteration (Eq. (2)), which is not done in practice. This normalization is done for mathematical convenience (similar to analysis [3]), so that we can control the $l_2$ norm of the self-training iterates. We thank the reviewer for bringing this up and will add this discussion to our theory section.\n\n\n\n\n> **Does linear probe (instead of fine-tuning everything) also work well in practice**\n\nWe observe that training linear head with ST (source labeled + target unlabeled) improves performance over just training head with source labeled data. In fact, if we used the optimal stopping criterion in hindsight (using target labeled data), the benefits are almost as much as full finetuning. However, since we do not have target labeled data in practice, we use source hold data for early stopping and resort to full finetuning which usually yields slightly better performance than only training the linear head.\n\nIn our theoretical setup, we observe that source early stopping works and yields optimal performance. Hence, to analyze CL and ST, we perform linear probing which is amenable to theoretical treatment (as in prior works [1, 2, 3]) . \n\n[1] Shen et al. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation.  \n\n[2] Saunshi et al. Understanding contrastive learning requires incorporating inductive biases\n \n[3] Chen et al. Self-training avoids using spurious features under domain shift."}, {"review_id": "qWnQ823e9w", "reviewer": "Reviewer_Srqn", "summary": "The paper explores the synergy of self-training and contrastive learning in semi-supervised learning (SSL) and unsupervised domain adaptation (UDA). It discovers their complementary effect in UDA. Furthermore, it proposes Self-Training Over Contrastive learning (STOC) to combine the benefits of the two approach. The STOC algorithm pretrains the self-training model by contrastive learning on source and target data.Finally, it theoretically analyzes the outcome of initializing with contrastive learning under a specific distribution shift.", "questions": "- The role of the classification head architecture and deep fine-tuning is missing from the experiments. ", "limitations": "The paper does not discuss the limitations and societal impacts of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides good theoretical support and empirical evidence to defend their hypothesis. It provides valuable insights into the factors that contribute to the success of contrastive learning and self-training.\n- The paper proposes a novel method that can improve unsupervised domain adaptation.\n- The findings of this paper have important implications for incorporating unlabeled data.\n- The paper is well-written.", "weaknesses": "- The combination of semi-supervised learning with self-supervised learning has been proposed in prior work [1], which is not included in the related work. An updated variety of this method can constitute as a relevant benchmark.\n- The assumptions about infinite unlabeled data, linear classifier $h$, and scaling the magnitude of the coordinates for augmentation, are restrictive.\n- The benchmarks are not competitive. There are several self-supervised methods such as DINO that can supplement the benchmarks.\n- There are typos such as in line 40: 'the strong strong results'.\n\n[1] Zhai, Xiaohua, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. \"S4l: Self-supervised semi-supervised learning.\" In Proceedings of the IEEE/CVF international conference on computer vision, pp. 1476-1485. 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments and positive feedback. In the next revision, we will **add discussion on Zhai et al. [1]** and correct typos. We hope our responses address any outstanding concerns. Please let us know if there are any additional questions. \n\n> **The combination of semi-supervised learning with self-supervised learning has been proposed in prior work [1], which is not included in the related work.** \n\nZhai et al. [1] differs from our work significantly in two ways: (1) they only focus on the semi-supervised learning (SSL) setting where there is no distribution shift between the input distribution of the unlabeled and labeled sets, while we focus more on the distribution shift setting (DA), and further contrast our findings in SSL and DA settings; and (2) they use rotation prediction as their pre-training objective while we analyze contrastive learning objectives. We will include this discussion in our related work section (currently in Appendix B).\n\n> **The assumptions about infinite unlabeled data, linear classifier , and scaling the magnitude of the coordinates for augmentation, are restrictive.**\n\nSince the aim of our study is to mainly explain the effects of distribution shift between labeled source and unlabeled target distributions, we avoid complicating the analysis stemming from the finite sample nature of the data. Further the main aim of our theoretical analysis is to explain our empirical findings (complementary nature of CL and ST) in a specific setup for UDA and SSL, as opposed to describing generic conditions for CL+ST to outperform CL/ST. Our choice of a linear classifier is common in theoretical analysis on contrastive learning and self-training [2,3,4], and our augmentation distribution has also been studied in prior work [3]. We note that our augmentations assume no knowledge of spurious features, and are similar in principle to augmentations like cropping or blurring that effectively reduce the magnitude of image features (see L191).\n\n> **The benchmarks are not competitive. There are several self-supervised methods such as DINO that can supplement the benchmarks.**\n\nIn DINO the self-supervised learning objective used is derived from knowledge distillation and is very different from the contrastive pretraining objective we study. Therefore, we do not include experiments with DINO. Extending our study from CL to other pretraining techniques like DINO  is an interesting direction of further research. For our study on studying CL/ST and their combinations we include results on 8 datasets, each with two settings (SSL/UDA), and four methods (ERM, CL, ST, CL+ST). During the rebuttal period, we also ran experiments with additional combinations of CL+ST methods (beyond SWaV+FixMatch) that we will append to the revised paper. Please see the general response for these results.\n\n> **The role of the classification head architecture and deep fine-tuning is missing from the experiments.**\n\nWe are not sure if we understand this question completely. If the question is about ''classification head architecture'', then we default to using a linear layer head for the classification, as is common practice. In Section 4.5 and Appendix E.4 we provide experimental results for full finetuning for our simulations in Sec 4, and for real world experiments we always finetune the full backbone. Please let us know if we misunderstood your question in which case we would be happy to provide further clarifications. \n\n> **The paper does not discuss the limitations and societal impacts of this work.**\n\nWe discuss limitations of our work in Appendix A. For the final version, we will move this discussion to the main paper. \n \n\n\n[2] Shen, Kendrick, et al. \"Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation.\" International Conference on Machine Learning. PMLR, 2022.   \n[3] Saunshi, Nikunj, et al. \"Understanding contrastive learning requires incorporating inductive biases.\" International Conference on Machine Learning. PMLR, 2022.   \n[4] Chen, Yining, et al. \"Self-training avoids using spurious features under domain shift.\" Advances in Neural Information Processing Systems 33 (2020): 21061-21071.   \n \n"}, {"review_id": "GoI42TuISu", "reviewer": "Reviewer_C2y1", "summary": "This paper proposes to combine contrastive learning and self-training for unsupervised domain adaptation. Experimental results on UDA benchmarks demonstrate the empirical effectiveness of the approach and a thorough study demonstrates the theoretical benefits.", "questions": "- In Table 1, are concurrent models your reimplementation, or pretrained models from the SwAV and FixMatch papers ?", "limitations": "Some limitations are discussed in the analysis, for exemple regarding the limited performance improvement on semi-supervised tasks.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The results on UDA tasks are consistently better than simple contrastive learning and self-training approaches.\n\n- The theoretical analysis is very thorough and demonstrates the fundamental benefits of contrastive learning and self-training individually and of combining them in the case of UDA.", "weaknesses": "- The proposed method STOC is vaguely described in L104-108. It would be clearer to describe it formally in more details.\n\n- The contributions are not clearly stated. Among the methods presented in L90-108, please clarify that STOC is your contribution.\n\n- Some popular UDA benchmarks are missing, many concurrent work are using Office-31 and Office-Home. Evaluation on these datasets would be appreciated.\n\n- Concurrent work are missing, such as [1, 2, 3]. Please position your work against these paper, and compare your approach both conceptually and empirically to the approaches presented in these papers. More generally, it seems that the presented method is only compared to simple baselines and not to methods that are specifically designed to tackle UDA tasks.\n\n[1] DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation, Damodaran et al., ECCV 2018\n\n[2] Implicit Class-Conditioned Domain Alignment for Unsupervised Domain Adaptation, Jiang et al., ICML 2020\n\n[3] Semantic-aware Message Broadcasting for Efficient Unsupervised Domain Adaptation, Li et al., ArXiv: 2212.02739", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment of our work and for their thoughtful feedback. We will improve the exposition of the final version as per your suggestions (e.g., a bulleted list of contributions, algorithmic description of STOC). \n\n \n> **The proposed method STOC is vaguely described in L104-108. It would be clearer to describe it formally in more details.**\n\nWe have updated the draft to include an Algorithmic description of STOC. \n\n> **The contributions are not clearly stated. Among the methods presented in L90-108, please clarify that STOC is your contribution.** \n\nThanks for your suggestion; we have updated the draft to list our main contributions:\nWe propose Self-Training Over Contrastive learning (STOC) to explore benefits of combining self-training and contrastive learning. \n- Our experiments across eight benchmark datasets highlight that: (i) in domain adaptation settings, self-training and contrastive learning offer significant complementary gains; and (ii) in semi-supervised learning settings, surprisingly, the benefits are not synergistic.\n- We theoretically analyze these techniques to understand why self-training improves over contrastive learning under distribution shift in a simplified model of distribution shift.  \n\nOverall, our findings demonstrate that under distribution shift features produced by contrastive learning can yield a good initialization for self-training to further amplify gains and achieve improved performance, even when either method alone would yield comparatively worse performance. \n\n> **Some popular UDA benchmarks are missing, many concurrent work are using Office-31 and Office-Home. Evaluation on these datasets would be appreciated.** \n\nWe would like to clarify that we indeed perform experiments on Office-Home and results are included in Table 1 and Table 2 (columns abbreviated with header OH). We do not include results on Office-31 because (i) the task is similar to Officehome; and (ii) Office-31 dataset is much smaller in size than OfficeHome. \n\n> **Concurrent work are missing, such as [1, 2, 3]. Please position your work against these paper ... More generally ... only compared to simple baselines and not to... specifically designed to tackle UDA tasks.** \n\nWe thank the reviewer for pointers to the related work. We will update the draft to include discussion on these papers in our related work. \n\nPlease note that the main focus of our paper is to investigate when constrastive learning and self-training benefits are complementary and not to establish a new state-of-the-art for unsupervised domain adaptation. For this reason, we also do not use imagenet pretraining to avoid confounding our conclusions about contrastive pretraining. Fair comparisons to other domain adaptation algorithms would require repeating experiments with Imagenet pretrained models which we leave for future work. Nevertheless, recent large-scale studies [4,5,6] hint that self-training (e.g. FixMatch) and constrastive learning methods (e.g. SwAV) empirically outperform other existing approaches specifically proposed for domain adaptation (e.g., DANN, CDANN). \n\nSpecifically, for [1, 2, 3] we will include the following discussion. Jiang et al. proposes an alternative of psuedolabling to handle label imbalances. In our study, we do not focus on simulating label proportion shifts and datasets included in our study mainly focus on shifts in the covariate distribution. Hence, the approach proposed by Jiang et al. will be similar to pseudolabeling in absence of label proportion shifts, which we compare with in our additional experiments (see general response, where our trends continue to hold). Damodaran et al. proposed DeepJDOT which uses optimal transport loss to align the features on target data with features on source data, and as part of future work it would be interesting to see if distribution matching methods also benefit from contrastive learning. Li et al. proposed a message passing variant to perform domain adaptation specifically for vision transformer architectures (i.e., ViT). In our work, we perform experiments with ResNet architectures and it remains unclear how to extend Li et al. to our setting. \n\n\n> **In Table 1, are concurrent models your reimplementation, or pretrained models from the SwAV and FixMatch papers ?** \n\nAll models included in our paper are trained again in our experimental setup with (adaptation) of original code from SwAV and FixMatch papers. \n\n[4] Sagawa, Shiori, et al. \"Extending the WILDS benchmark for unsupervised adaptation.\" arXiv preprint arXiv:2112.05090 (2021).    \n[5] Garg, Saurabh, et al. \"Rlsbench: Domain adaptation under relaxed label shift.\" International Conference on Machine Learning. PMLR, 2023.   \n[6] Shen, Kendrick, et al. \"Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation.\" International Conference on Machine Learning. PMLR, 2022.   "}]

Author rebuttal:
We are grateful to the reviewers for their thoughtful feedback and are glad to see all of them recommending acceptance. Per their feedback we have **added experiments on more combinations of CL+ST** where we find our empirical findings on SWaV+FixMatch continue to hold. In the general response, we address one common concern shared by reviewers, and address others as individual responses to each reviewer. Please let us know if you have any additional concerns or if all outstanding concerns are addressed.


> **Limited combination of contrastive learning and self-training algorithms.**

In our experiments, we default to using the SWaV backbone for contrastive pretraining and FixMatch for self-training mainly because prior works [1, 2, 3] note that SWaV outperforms other contrastive pretraining methods like SimCLR, BYOL, etc. Having said that, for the rebuttal, we provide experimental results for two additional combinations: (1) SWaV + pseudolabeling (different self-training method), and (2) Barlow Twins + FixMatch (different contrastive pretraining method). Due to rebuttal time constraints we could only run on two datasets for each, but will add results on the remaining six in our revision.

| Dataset      | ERM   | ST (FixMatch) | CL (Barlow Twins) | STOC (Barlow Twins + FixMatch) |
|--------------|-------|---------------|-------------------|--------------------------------|
| Entity-13    | 68.32 | 77.93         | 81.04             | 86.23                          |
| Nonliving-26 | 45.54 | 56.79         | 62.17             | 71.46                          |


| Dataset      | ERM   | ST (Pseudolabel) | CL (SwAV)    | STOC (SwAV+Pseudolabel) |
|--------------|-------|------------------|-------|------------------------|
| Living-17    | 60.31 | 69.34            | 74.14 | 79.81                  |
| Nonliving-26 | 45.54 | 58.25            | 57.02 | 67.87                  |


Results with these two new combinations match the trends in Sec 3 (i.e., we observe that STOC improves over CL and ST alone), similar to what we observed with SWaV+FixMatch. In fact, on these datasets Barlow Twins pretraining improves over SwAV pretraining. This reinforces that the complementary benefits of self-training and contrastive learning hold across different variations of pretraining and self-training objectives. We thank the reviewers for their suggestion and will include these ablations on all datasets in our revision. 

[1] Sagawa et al. "Extending the WILDS benchmark for unsupervised adaptation." arXiv preprint arXiv:2112.05090 (2021).   
[2] Garg et al. "Rlsbench: Domain adaptation under relaxed label shift." International Conference on Machine Learning. PMLR, 2023.   
[3] Shen et al. "Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation." International Conference on Machine Learning. PMLR, 2022.   

Meta-review: The paper proposed an approach to combine both self-training and contrastive pretraining for domain adaptation under distribution shifts. The main strength of the work lies in its entensive empirical studies, including consistent accuracy gains over 8 benchmark datasets. All the reviewers like the paper and recommend acceptance. I have read the rebuttal and the reviews. I agree with the reviewers that the rebuttal addressed most of the concerns. I recommend acceptance.
Decision: Accept (poster)