Connect, Not Collapse: Explaining Contrastive Learning for
Unsupervised Domain Adaptation

Kendrick Shen††footnotemark: ***Equal contribution. Robbie
Jones††footnotemark:  Ananya Kumar††footnotemark:  Sang Michael
Xie††footnotemark:
Jeff Z. HaoChen Tengyu Ma Percy Liang

Stanford University

Department of Computer Science

{kshen6, rmjones, ananya, xie, jhaochen, tengyuma<EMAIL_ADDRESS>
###### Abstract

We consider unsupervised domain adaptation (UDA), where labeled data from a
source domain (e.g., photos) and unlabeled data from a target domain (e.g.,
sketches) are used to learn a classifier for the target domain. Conventional
UDA methods (e.g., domain adversarial training) learn domain-invariant
features to generalize from the source domain to the target domain. In this
paper, we show that contrastive pre-training, which learns features on
unlabeled source and target data and then fine-tunes on labeled source data,
is competitive with strong UDA methods. However, we find that contrastive pre-
training does not learn domain-invariant features, diverging from conventional
UDA intuitions. We show theoretically that contrastive pre-training can learn
features that vary subtantially across domains but still generalize to the
target domain, by disentangling domain and class information. We empirically
validate our theory on benchmark vision datasets.

##  1 Introduction

Machine learning models can perform poorly when the train and test data are
drawn from different distributions, which is especially troublesome for
performance-critical applications such as image recognition for self-driving
cars (Yu et al., 2020; Sun et al., 2020) or medical image diagnosis (AlBadawy
et al., 2018; Dai & Gool, 2018). In this work, we study the unsupervised
domain adaptation (UDA) setting where we have access to labeled data from a
source domain and unlabeled data from a target domain, and the goal is to get
high accuracy on the target domain.

Conventional algorithms for UDA aim to learn domain-invariant features (Tzeng
et al., 2014; Ganin et al., 2016; Tzeng et al., 2017; Shu et al., 2018; Sun et
al., 2019)—intuitively, if the distributions over features for the source and
target domains are indistinguishable and the accuracy is high on the source,
then the accuracy should be high on the target as well. This is typically
intuitively justified by theoretical notions such as
$\mathcal{H}\Delta\mathcal{H}$-divergence, which measures the
distinguishability of source and target feature spaces (Ben-David et al.,
2010). However, Zhao et al. (2019) show that domain invariance is not
sufficient for target generalization, and thus some recent works have begun to
develop principled algorithms for domain adaptation (Kumar et al., 2020; Wei
et al., 2021; Cai et al., 2021).

In this paper, we find that a surprisingly simple and effective method for UDA
is out-of-the-box contrastive pre-training on source and target unlabeled
data, followed by fine-tuning on source labeled data. In our experiments,
contrastive pre-training obtains comparable or better results to strong UDA
methods based on domain adversarial neural networks (Ganin et al., 2016; Shu
et al., 2018) and self-training (Prabhu et al., 2021) on visual adaptation
benchmarks including DomainNet, BREEDS Living-17, BREEDS Entity-30, and
STL-10$\to$CIFAR-10 (results in Table 2).

However, we show that contrastive pre-training diverges from conventional UDA
intuitions and learns features that are easily separable between domains; for
example in the learned feature space in DomainNet, we can predict the domain
of an image with only 8% error, which is much lower than in the DANN feature
space (14%)—see Table 1 in Section 4. In fact, in the contrastive pre-trained
feature space for DomainNet, it is as easy to distinguish betweeen two domains
as it is to distinguish between two classes.

How does contrastive pre-training learn features that generalize to the target
domain without domain invariance? To theoretically analyze contrastive pre-
training, we consider a graph (see Figure 1) where input examples are nodes
and the edge weight between two inputs is the probability that they are
generated by sampling two augmentations of the same original input. By
considering the total edge weight between two class-domain pairs (e.g., all
edges connecting a clock photo to a butterfly sketch), we can define class-
domain connectivities. These connectivities describe how much overlap to
expect amongst the randomly augmented inputs from two class-domain pairs. Our
key assumption intuitively states that augmentations of clock photos should be
more similar to clock sketches and butterfly photos than to butterfly
sketches. Concretely, we assume that that both (1) the probability that
augmentation changes the domain only, keeping the class constant, and (2) the
probability that augmentation changes the class only, keeping the domain
constant, should be higher than (3) the probability that augmentation changes
both domain and class. Under a stochastic block model (a standard randomized
model for the edges of the graph), we prove that contrastive pre-training
achieves good target accuracy without domain invariance—by learning a
“disentangled” feature space that is simultaneously predictive of domain and
class (Theorem 1). Importantly, in our analysis the source and target domains
can be very far apart, and the features can be easily distinguished
(Proposition 2).

We empirically validate our theory on benchmark UDA datasets. We first
heuristically estimate the connectivities between different class-domain pairs
(e.g., clock photos and butterfly sketches) on Living-17 (Santurkar et al.,
2020) and DomainNet (12 domain pairs) (Peng et al., 2019), showing that they
satisfy our theoretical condition for contrastive pre-training to learn
transferable features. Next, we find that the target accuracy of contrastive
pre-training on DomainNet can be well-explained ($R^{2}=0.78$) using the terms
that appear in our theory: the ratios of the estimated connectivities.
Furthermore, pre-training on a selected subset of the data to adversely change
the connectivities consistently underperforms pre-training on randomly
selected subsets of the same size (resulting in 4%-16% drops in target
accuracy). Finally, we give evidence that contrastive pre-training learns
features that contain class and domain information along approximately
different dimensions, allowing the features to be transferable across domains
without requiring domain invariance. Our results provide a first step for
theoretically understanding contrastive pre-training for UDA, which can be
used to improve data augmentation and selection strategies.

Figure 1: (Left) Edges between class-domain pairs indicate how “connected”
they are by augmentations (e.g., cropping, colorization). For example,
$\alpha$ denotes the probability that augmentations connect examples of the
same class across different domains. Small crop sizes (e.g., the red
rectangles) can increase the connectivity between disparate domains. (Right)
When $\alpha$ and $\beta$ (which measure the connectivity between images of
the same class or same domain respectively) are larger than $\gamma$
(different domain and different class), fine-tuning with labeled source data
(sketch: green, filled) in the feature space achieves high accuracy on the
target (real: gray, hollow).

##  2 Related work

#### Conventional domain adaptation methods bring source and target domains
together.

Ben-David et al. (2010) prove generalization bounds for domain adaptation that
rely on small $\mathcal{H}\Delta\mathcal{H}$-divergence between the source and
target (i.e., distributions of $\phi(x)$ for both domains are similar and
therefore difficult to distinguish). Many methods such as domain adversarial
training (Tzeng et al., 2014; Ganin et al., 2016; Tzeng et al., 2017) and
moment matching (Peng et al., 2019) have objectives that aim to minimize
$\mathcal{H}\Delta\mathcal{H}$-divergence between the source and target
features. More recent works propose alternate measures of domain divergence to
minimize (Li et al., 2021), propose dynamically weighting domain divergence
and classification losses (Xiao & Zhang, 2021), and improve on prior work that
uses optimal transport to bring the domains together (Li et al., 2020).

#### Contrastive learning for self-supervised learning.

Contrastive learning methods (Chen et al., 2020a; He et al., 2020; Caron et
al., 2020) perform self-supervised learning of a feature encoder on unlabeled
data. Broadly, the contrastive learning objective aims to learn an encoder
that maps augmentations (e.g., crops) of the same input to similar features
and augmentations of random inputs to different features. The pre-trained
encoder is then fine-tuned on a downstream dataset like ImageNet (Russakovsky
et al., 2015) where the downstream train and test examples come from the same
distribution. Several theoretical works provide guarantees on the performance
of contrastive learning in this setting of identical train and test
distributions (Arora et al., 2019; Tosh et al., 2021; HaoChen et al., 2021).
In contrast, we consider contrastive pre-training for domain adaptation, where
the downstream training data are from the source domain and the test data are
from the target domain.

#### Domain adaptation with self-supervision.

Prior works have explored the application of self-supervision to UDA. However,
to the best of our knowledge they have all attempted to minimize domain
distance either as part of their objective (Kang et al., 2019; Wang et al.,
2021; Thota & Leontidis, 2021) or for model selection (Sun et al., 2019).
Conversely, contrastive pre-training has no explicit objective involving
domain distance and is still competitive with conventional UDA methods, a
phenomenon that is explained by our connectivity theory. Recent work (Mishra
et al., 2021) has shown that in the semi-supervised domain adaptation setting
(where a small numbers of target labels are given), a method based on self-
supervised rotation prediction and input consistency regularization
simultaneously achieves higher accuracy and learns features with larger domain
distance than prior methods.

#### Assumptions about distribution shift.

A classical assumption is covariate shift (Shimodaira, 2000), a setting in
which the marginal distribution over $\mathcal{X}$ can change between domains
but the label conditioned on $x$ is fixed. However, if the source and target
have disjoint support then covariate shift is trivially satisfied, and
therefore recent works have proposed alternative definitions. Kumar et al.
(2020) assumes the shift is gradual in a Wasserstein metric and does not
explicitly assume covariate shift. Wei et al. (2021) analyzes UDA with two
assumptions: 1) the source classifier has reasonable accuracy on the target,
and the target satisfies an “expansion” condition. Cai et al. (2021) assume
that there is significant overlap (expansion) between the source and target
after augmentations and analyzes self-training for UDA. Our theoretical
connectivity model is an alternative method for describing distribution shift
so that contrastive pre-training adapts even under large
$\mathcal{H}\Delta\mathcal{H}$-divergence.

##  3 Setup

###  3.1 Unsupervised Domain Adaptation (UDA)

We consider a classification problem from an input space
$\mathcal{X}\subseteq\mathbb{R}^{d}$ to a label space
$\mathcal{Y}=\\{1,\dots,r\\}$.

#### Data, model, and metrics.

Each input $x\in\mathcal{X}$ is associated with a deterministic label
$y_{x}\in\mathcal{Y}$ and a domain $d_{x}\in\\{1,2\\}$ (where domain 1 is the
source and domain 2 is the target)†††The deterministic assumption is not
strictly necessary, but greatly simplifies the setup. In general, we have a
label distribution $p(y\mid x)$ and domain distribution $p(d\mid x)$ that are
shared across all inputs, thus making the covariate shift assumption.. Let
$P_{S}$ and $P_{T}$ denote the source and target input distributions
respectively (both over $\mathcal{X}$). Let $P_{U}=\theta
P_{S}+(1-\theta)P_{T}$ for some $\theta\in[0,1]$ be a mixture of the source
and target domains. This mixture distribution serves as the unlabeled data
distribution over both source and target domains. For simplicity, we consider
the population data setting in the theory.

We consider the unsupervised domain adaptation (UDA) setting: algorithms have
access to labels $y_{x}$ for source examples $x\sim P_{S}$ but not for target
examples $x\sim P_{T}$. Algorithms are allowed to use _unlabeled_ data from
all domains. The goal is to learn a classifier
$f:\mathcal{X}\rightarrow\mathbb{R}^{r}$ with low error on the target
distribution $\mathcal{L}_{0-1}(f)=\mathbb{E}_{x\sim
P_{T}}[\mathbf{1}[\operatorname*{arg\,max}_{i}f(x)_{i}\neq y_{x}]]$.

#### Augmentations.

Modern ML models are trained with augmentations such as crops and color
distortions (Krizhevsky et al., 2012; Chen et al., 2020a). For any input
$x\in\mathcal{X}$, let $\mathcal{A}(\cdot\mid x)$ be the distribution of its
augmentations (also over $\mathcal{X}$).

###  3.2 Methods

We consider methods using a classification loss
$\ell:\mathbb{R}^{r}\times\mathcal{Y}\rightarrow\mathbb{R}$ (e.g., cross
entropy or squared loss). We also overload the loss
$\ell:\mathbb{R}^{2}\times\\{1,2\\}\rightarrow\mathbb{R}$ for domain
classification depending on the arguments.

Empirical risk minimization (ERM) minimizes the loss $\ell$ over augmentations
$x^{\prime}\sim\mathcal{A}(\cdot\mid x)$ of source examples $x\sim P_{S}$ and
the original labels $y_{x}$:

$\displaystyle\mathcal{L}_{\text{ERM}}(f)=\mathbb{E}_{x\sim
P_{S},x^{\prime}\sim\mathcal{A}(\cdot\mid x)}[\ell(f(x^{\prime}),y_{x})],$ (1)

ERM learns a classifier
$\widehat{f}_{\text{erm}}\in\operatorname*{arg\,min}_{f}\mathcal{L}_{\text{ERM}}(f)$.
Augmentations improve the target accuracy of ERM and our results also hold
without augmentations.

Domain adversarial neural networks (DANN) (Ganin et al., 2016) optimizes the
sum of two terms: a source classification loss, and a “domain confusion” loss
that makes it difficult to predict the domain $d_{x}$ from the feature
$\phi(x)$. Here, $\phi:\mathcal{X}\rightarrow\mathbb{R}^{k}$ is a feature
encoder, $h:\mathbb{R}^{k}\rightarrow\mathbb{R}^{r}$ is a head that predicts
the class, and ${h}_{\text{dom}}:\mathbb{R}^{k}\rightarrow\mathbb{R}^{2}$ is a
head that predicts whether the input comes from the source or target.

$\displaystyle\mathcal{L}_{\text{DANN}}(\phi,h,{h}_{\text{dom}})=\mathbb{E}_{x\sim
P_{S},x^{\prime}\sim\mathcal{A}(\cdot\mid
x)}[\ell(h(\phi(x’)),y_{x})]-\lambda\;\mathbb{E}_{x\sim
P_{U},x^{\prime}\sim\mathcal{A}(\cdot\mid
x)}[\ell({h}_{\text{dom}}(\phi(x^{\prime})),d_{x})],$ (2)

where $\lambda>0$ is a tradeoff parameter between the two losses and
${h}_{\text{dom}}$ is a domain classifier. The classifier
$\widehat{f}_{\text{dann}}=\widehat{h}_{\text{dann}}\circ\widehat{\phi}_{\text{dann}}$
is learned by minimizing the loss:
$\widehat{\phi}_{\text{dann}},\widehat{h}_{\text{dann}}\in\operatorname*{arg\,min}_{\phi,h}\max_{{h}_{\text{dom}}}\mathcal{L}_{\text{DANN}}(\phi,h,{h}_{\text{dom}})$.

Contrastive pre-training aims to learn useful features on the unlabeled data
from both source and target by training an encoder which maps data-augmented
views of the same input $x$ to similar features (the “positive pairs”) and
data-augmented views of random pairs of inputs to dissimilar features (the
“negative pairs”). Intuitively, contrastive pre-training will embed
augmentations of clock photos relatively closer to clock sketches than to
butterfly sketches, but the embeddings may all be far apart in absolute
distance. Formally, let $S_{+}$ be the distribution (on
$\mathcal{X}\times\mathcal{X}$) of “positive pairs” (augmentations of a single
input $\bar{x}$), given by:

$\displaystyle S_{+}(x,x^{+})=\mathbb{E}_{\bar{x}\sim
P_{U}}[\mathcal{A}(x\mid\bar{x})\mathcal{A}(x^{+}\mid\bar{x})].$ (3)

We apply contrastive pre-training to UDA—we pretrain an encoder $\phi$ on
source and target unlabeled data from $P_{U}$, and then fine-tune a
classification head $h$ on only source labeled data from $P_{S}$.

  1. 1.

(Pre-train on unlabeled source and target data) We first pre-train an encoder
$\phi:\mathcal{X}\rightarrow\mathbb{R}^{k}$ to minimize the distance $d_{+}$
between positive pairs, and maximize the distance $d_{-}$ between random pairs
of inputs:

$\displaystyle\mathcal{L}_{\text{pretrain}}(\phi)\triangleq\,\,$
$\displaystyle\mathbb{E}_{(x,x^{+})\sim
S_{+}}\left[d_{+}(\phi(x),\phi(x^{+}))\right]$ (4) $\displaystyle-\,\,$
$\displaystyle\mathbb{E}_{x\sim P_{U},x^{\prime}\sim
P_{U}}\left[d_{-}(\phi(x),\phi(x^{\prime}))\right],$

where the learned encoder is
$\widehat{\phi}=\operatorname*{arg\,min}_{\phi}\mathcal{L}_{\text{pretrain}}(\phi)$.

  2. 2.

(Fine-tune on labeled source data) We learn a classification head
$\widehat{h}=\operatorname*{arg\,min}_{h}\mathcal{L}(h)$ on pretrained
features $\widehat{\phi}(x)$ and their labels $y_{x}$ where the loss is

$\displaystyle\mathcal{L}(h)\triangleq\mathbb{E}_{x\sim
P_{S}}[\ell(h(\widehat{\phi}(x)),y_{x})].$ (5)

The final classifier is $\widehat{h}\circ\widehat{\phi}$. In our experiments,
we fine-tune both the head $h$ and encoder $\phi$.

##  4 Intuitions and Analysis

| Feature space | Across | Across | Across
---|---|---|---|---
Dataset | learned by | class ($\beta$) | domain ($\alpha$) | both ($\gamma$)
Living-17 | Input space | 21.43 | 36.58 | 19.55
| DANN+strong-augs | 3.44 | 18.00 | 3.38
| SwAV | 2.06 | 12.67 | 1.26
DomainNet | Input space | 32.88 | 27.36 | 25.12
| CLIP | 1.44 | 4.58 | 0.54
| DANN+strong-augs | 5.65 | 13.64 | 3.89
| SwAV | 7.03 | 7.54 | 2.46

Table 1: Average error of classifying augmented images of two class-domain
pairs (as a proxy for connectivity) in the input space and feature spaces
learned by CLIP, DANN+strong-augs, and SwAV (contrastive pre-training).
Classes are very distinguishable in both the DANN and SwAV feature spaces, but
the domains are much more difficult to distinguish in the DANN feature space
than in the SwAV feature space.

In this section, we explain when contrastive pre-training can learn
transferable features—i.e., simply training a classifier on labeled source
data leads to good predictions on the unlabeled target domain—despite keeping
the source and target features very different. We extend the spectral
contrastive learning framework (HaoChen et al., 2021) to incorporate
distribution shift—we give intuitions in Section 4.2, a proof for the
stochastic block model setting in Section 4.3, and a setting where contrastive
pre-training outperforms domain adversarial neural networks (Ganin et al.,
2016) (even when both use the same data augmentations), in Section 4.4.

###  4.1 Theoretical setup

#### Spectral contrastive learning.

HaoChen et al. (2021) theoretically analyzed contrastive learning from the
perspective of an augmentation graph in which the inputs $x$ from
$\mathcal{X}$ constitute the nodes, and the edge weight
$S_{+}(x,{x^{\prime}})$ represents the probability of the inputs being
selected as a positive pair (augmentations of the same image $x$). As in
HaoChen et al. (2021), we analyze the spectral contrastive learning objective,
which achieves similar empirical results to other contrastive learning methods
but is more amenable to theoretical analysis:

$\displaystyle\mathcal{L}_{\text{pretrain}}(\phi)=-2\cdot\mathbb{E}_{(x,x^{+})\sim
S_{+}}\left[\phi(x)^{\top}\phi(x^{+})\right]+\mathbb{E}_{x,x^{\prime}\sim
P_{U}}\left[\left(\phi(x)^{\top}\phi(x^{\prime})\right)^{2}\right].$ (6)

The pre-training step learns the encoder
$\widehat{\phi}:\mathcal{X}\to\mathbb{R}^{k}$ by minimizing (6).

#### Linear classification.

After pre-training, we train a linear probe on source domain features with
parameters $B\in\mathbb{R}^{r\times k}$ (where $k$ is the feature dimension
and $r$ is the number of classes). We learn the parameters $\widehat{B}$ by
minimizing

$\displaystyle\mathcal{L}(B)=\mathbb{E}_{x\sim
P_{S}}\left[\ell(B\widehat{\phi}(x),y_{x})\right]+\eta\|B\|_{F}^{2},$ (7)

where $\ell$ is the squared loss. The resulting classifier is
$\widehat{f}(x)=\operatorname*{arg\,max}_{i\in[r]}(\widehat{B}\widehat{\phi}(x))_{i}$.

###  4.2 Simple example

We first consider a toy example that captures the core intuitions of our
theory. For this example, we compute an exact (closed-form) expression for the
representations learned by contrastive pre-training on unlabeled data, which
are visualized in Figure 2. We then show that a linear classifier trained on
source representations also gets high accuracy on examples from the target
domain, _without using any target labels_.

#### Setup.

The goal is to classify between images of clocks and butterflies—see Figure 2.
The input space $\mathcal{X}$ consists of 4 points: [clock sketch, butterfly
sketch, clock photo, butterfly photo], where the $i$-th input refers to the
$i$-th element in the list (e.g., $i=2$ corresponds to butterfly sketch). The
label space $\mathcal{Y}$ contains two classes, clock ($y_{x}=1$) and
butterfly ($y_{x}=2$). We only have labeled data for the source inputs
(sketches, $d_{x}=1$), and the goal is to achieve high accuracy on the target
inputs (photos, $d_{x}=2$). The source distribution $P_{S}$ places equal
probability on sketches ($P_{S}(x)=0.5$ if $d_{x}=1$ and $P_{S}(x)=0$
otherwise), and the target distribution $P_{T}$ places equal probability on
photos ($P_{T}(x)=0.5$ if $d_{x}=2$ and $P_{T}(x)=0$ otherwise). The unlabeled
distribution $P_{U}$ places equal probability on all images (sketches and
photos).

#### Augmentations.

The key ingredient in contrastive pretraining is the augmentation
strategy—contrastive pretraining aims to map augmentations of the same input
$x$ to similar representations. These augmentations include aggressive crops
which keep only a small part ($8\%$) of an image (e.g., the tail or fur of an
animal), and can blur the line between classes. Augmentations such as color
jitter, which also randomly ‘drops’ colors, can also transform the style of an
image, blurring the line between domains such as sketches and photos. As such,
we consider augmentations that can change the class or domain of an image. We
define the probability that an image $x$ can augment to an image $x^{\prime}$
as follows:

$\displaystyle A(x^{\prime}\mid x)=\begin{cases}\rho^{\prime}&\text{if}\quad
y_{x}=y_{x^{\prime}},d_{x}=d_{x^{\prime}}\\\ \alpha^{\prime}&\text{if}\quad
y_{x}=y_{x^{\prime}},d_{x}\neq d_{x^{\prime}}\\\ \beta^{\prime}&\text{if}\quad
y_{x}\neq y_{x^{\prime}},d_{x}=d_{x^{\prime}}\\\
\gamma^{\prime}&\text{if}\quad y_{x}\neq y_{x^{\prime}},d_{x}\neq
d_{x^{\prime}}\end{cases},$

#### Key condition for contrastive pre-training in the UDA setting.

We explain in our simple example how contrastive pre-training achieves zero
target error when $\rho^{\prime}>\max\\{{\alpha}^{\prime},{\beta}^{\prime}\\}$
and $\min\\{{\alpha}^{\prime},{\beta}^{\prime}\\}>{\gamma}^{\prime}$, and we
prove a more general version in Section 4.3. The first condition is satisfied
when an augmented image is more likely to stay within the same domain and
class, than change the domain or class. The second condition is satisfied when
data augmentation is less likely to change both the domain and class of an
image than just one of domain or class. For example, an augmentation is less
likely to augment a clock photo into a butterfly sketch, since it involves
changing both the style (sketch vs. real) and the semantic content (butterfly
vs. clock).

#### Deriving a closed-form expression for pre-trained representations.

Consider a 4-node graph $G$ where the nodes are input examples in
$\mathcal{X}$ and where the edge weight between $x,x^{+}\in\mathcal{X}$ is the
probability of sampling augmentations $x$ and $x^{+}$ from the same original
image $\bar{x}$ (Equation 3): $S_{+}(x,x^{+})$. We illustrate this graph in
Figure 2 (left). Let $A$ denote the weighted adjacency matrix for $G$, which
depends on the augmentation parameters
$\rho^{\prime},\alpha^{\prime},\beta^{\prime},\gamma^{\prime}$:

$\displaystyle A$
$\displaystyle=\begin{bmatrix}[r]{\rho}&{\beta}&{\alpha}&{\gamma}\\\
{\beta}&{\rho}&{\gamma}&{\alpha}\\\ {\alpha}&{\gamma}&{\rho}&{\beta}\\\
{\gamma}&{\alpha}&{\beta}&{\rho}\\\ \end{bmatrix},\text{ where
}\begin{cases}\rho=\frac{1}{4}&({\rho^{\prime}}^{2}+{\alpha^{\prime}}^{2}\\\
&+{\beta^{\prime}}^{2}+{\gamma^{\prime}}^{2})\\\
\alpha=\frac{1}{2}&(\rho^{\prime}\alpha^{\prime}+\beta^{\prime}\gamma^{\prime})\\\
\beta=\frac{1}{2}&(\rho^{\prime}\beta^{\prime}+\alpha^{\prime}\gamma^{\prime})\\\
\gamma=\frac{1}{2}&(\rho^{\prime}\gamma^{\prime}+\alpha^{\prime}\beta^{\prime})\end{cases}$

Recall that we assumed
$\rho^{\prime}>\max\\{{\alpha}^{\prime},{\beta}^{\prime}\\}$ and
$\min\\{{\alpha}^{\prime},{\beta}^{\prime}\\}>{\gamma}^{\prime}$. With some
algebra, this implies that the same condition holds for the positive pair
probabilities as well: $\rho>\max\\{{\alpha},{\beta}\\}$ and
$\min\\{{\alpha},{\beta}\\}>{\gamma}$.

Contrastive pre-training learns an encoder
$\widehat{\phi}:\mathcal{X}\to\mathbb{R}^{k}$ given by Equation 6—we use $k=3$
here. Let $\widehat{\Phi}\in\mathbb{R}^{4\times k}$ be the learned feature
matrix, where the $i$-th row of $\widehat{\Phi}$ contains representations for
example $i$, so $\widehat{\Phi}_{i}=\widehat{\phi}(i)$.

From a few lines of algebra (Lemma 3.2 in HaoChen et al. (2021)),
$\mathcal{L}_{\text{pretrain}}(\widehat{\phi})=\frac{1}{16}\|16A-\widehat{\Phi}\widehat{\Phi}^{\top}\|_{2}^{2}+c$,
where $c$ is a constant that does not depend on $\widehat{\phi}$. Here, $A$
has rank 4, while $\widehat{\Phi}\widehat{\Phi}^{\top}$ has rank 3—the
minimizer $\widehat{\Phi}$ is given by the eigenvectors corresponding to the 3
largest eigenvalues of $A$. We can compute the (unordered) eigenvalues
$\lambda_{a},\lambda_{b},\lambda_{c},\lambda_{d}$ and corresponding
eigenvectors $u_{a},u_{b},u_{c},u_{d}$ of $A$ explicitly:

$\displaystyle\lambda_{a}=\alpha+\beta+\gamma+\rho,\quad$
$\displaystyle\lambda_{b}=-\alpha+\beta-\gamma+\rho,$
$\displaystyle\lambda_{c}=\alpha-\beta-\gamma+\rho,\quad$
$\displaystyle\lambda_{d}=-\alpha-\beta+\gamma+\rho,$ $\displaystyle
u_{a}=(1,1,1,1)^{\top},\quad$ $\displaystyle u_{b}=(1,1,-1,-1)^{\top},$
$\displaystyle u_{c}=(1,-1,1,-1)^{\top},\quad$ $\displaystyle
u_{d}=(1,-1,-1,1)^{\top}.$

Since $\beta>\gamma$ and $\alpha>\gamma$, we have:

  1. 1.

$\lambda_{a}>\lambda_{d}$ since all $\rho,\beta,\alpha,\gamma$ are
nonnegative,

  2. 2.

$\lambda_{b}>\lambda_{d}$ when $\beta-\gamma>-\beta+\gamma$, which is implied
by $\beta>\gamma$,

  3. 3.

$\lambda_{c}>\lambda_{d}$ when $\alpha-\gamma>-\alpha+\gamma$, which is
implied by $\alpha>\gamma$.

So $\lambda_{d}$ is the smallest eigenvalue, and the learned features are
given by (up to rotational symmetries):

$\displaystyle\widehat{\Phi}$
$\displaystyle=\begin{bmatrix}[c]\widehat{\phi}(\text{clock sketch})^{\top}\\\
\widehat{\phi}(\text{butterfly sketch})^{\top}\\\ \widehat{\phi}(\text{clock
photo})^{\top}\\\ \widehat{\phi}(\text{butterfly
photo})^{\top}\end{bmatrix}=4\begin{bmatrix}[r]\sqrt{\lambda_{a}}&\sqrt{\lambda_{b}}&\sqrt{\lambda_{c}}\\\
\sqrt{\lambda_{a}}&\sqrt{\lambda_{b}}&-\sqrt{\lambda_{c}}\\\
\sqrt{\lambda_{a}}&-\sqrt{\lambda_{b}}&\sqrt{\lambda_{c}}\\\
\sqrt{\lambda_{a}}&-\sqrt{\lambda_{b}}&-\sqrt{\lambda_{c}}\end{bmatrix}$

Figure 2: (Left) Illustrative example in binary classification, where each
class-domain pair is a single node in the graph. Edge weights denote
connectivity (probability of sampling the endpoints as a positive pair). The
self-loop weight ${\rho}$ denotes the probability of sampling a pair of the
same domain and class. (Middle) When $\alpha$ (same class, different domain)
and $\beta$ (different class, same domain) are greater than $\gamma$
(different domain, different class), the features are oriented so that a
source-trained linear classifier generalizes to the target. The class and
domain information are disentangled along the vertical and horizontal axes,
respectively. (Right) When $\alpha<\gamma$, the target features are flipped
and the source-trained classifier does not generalize.

#### Fine-tuning on source examples gets zero error on target.

So far, we have calculated the features learned by contrastive pretraining. We
note that the first feature dimension is the same for all examples and
therefore not useful—we visualize the remaining 2-D features in the middle
panel of Figure 2. We see that the features disentangle the domain and class
information—the second feature dimension can be used to distinguish domains
while the third feature can distinguish classes. Therefore, training a max-
margin classifier $\widehat{f}$ on only labeled sketch images (first two rows
of the feature matrix $\widehat{F}$) produces a classifier that uses only the
third feature, which extrapolates to photos correctly and gets _zero OOD
error_ ($\mathcal{L}_{0-1}(\widehat{f})=0$). The key difference from
conventional intuitions in domain adaptation is that contrastive pre-training
does not learn domain-invariant features—the source and target are perfectly
distinguishable but the domain and class information are disentangled,
enabling generalization.

Note that if our key condition on the augmentations does not hold e.g.,
$\alpha<\gamma$ but $\gamma<\beta$, then the learned features $\widehat{F}$
exclude the eigenvector corresponding to $\lambda_{c}$ as the smallest. Again,
the first feature is constant and not useful. In the visualization (Figure 2
right), we show the features learned by contrastive pre-training. In this
case, a max-margin classifier $\widehat{f}$ trained on sketch images (red
line) mislabels the photos ($\mathcal{L}_{0-1}(\widehat{f})=1$) because the
orientation of the classes is flipped between domains.

###  4.3 Theory for multi-class stochastic block model

We extend the simple example in Section 4.2 to a stochastic block model
setting with $r$ classes, where we have $n$ points for each class and domain.
The unlabeled data distribution $P_{U}$ is the uniform distribution over
$\mathcal{X}$.

The stochastic block model (SBM) (Holland et al., 1983) is a random graph
model widely used in theoretical computer science to model communities,
networks, and topic models in NLP (Bouveyron et al., 2016; Abbe, 2018; Mehta
et al., 2019). The graph $G=(\mathcal{X},E)$ is defined as follows: for each
pair of nodes $x,{x^{\prime}}\in\mathcal{X}$, the corresponding edge
(undirected, unweighted) is in the edge set $E$ with probability:

$\displaystyle\begin{cases}\rho&\text{if}\quad
y_{x}=y_{x^{\prime}},d_{x}=d_{x^{\prime}}\\\ \alpha&\text{if}\quad
y_{x}=y_{x^{\prime}},d_{x}\neq d_{x^{\prime}}\\\ \beta&\text{if}\quad
y_{x}\neq y_{x^{\prime}},d_{x}=d_{x^{\prime}}\\\ \gamma&\text{if}\quad
y_{x}\neq y_{x^{\prime}},d_{x}\neq d_{x^{\prime}}\end{cases},$

and all edges are sampled independently. The distribution of positive pairs
$S_{+}$ is the uniform distribution over $E$.

Our key condition is that 1) augmentations are less likely to change both the
domain and class ($\min\\{\alpha,\beta\\}>\gamma$) and 2) augmentations are
more likely to keep both class and domain unchanged than to change either one
of the two ($\rho>\max\\{\alpha,\beta\\}$) . Assuming this and using a feature
dimension $r+1$, the following result shows that contrastive pre-training on
unlabeled source and target data learns transferable features so that a linear
head trained on the source features achieves high accuracy on the target.

######  Theorem 1.

In the SBM setting above, let $\rho>\max\\{\alpha,\beta\\}$ and
$\min\\{\alpha,\beta\\}>\gamma$ and let the pre-training feature dimension be
$r+1$. Then, for any
$n\geq\Omega\left(\frac{r}{\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}}\right)$
and regularization strength
$\eta\in\left(0,\frac{\alpha-\gamma}{8r\rho}\right)$, with probability at
least $0.999$, we have

$\displaystyle\mathcal{L}_{0-1}(\widehat{f})\leq
O\left(\frac{1}{\eta^{4}\cdot(\min\\{\alpha,\beta\\}-\gamma)^{2}\cdot
n}\right)\cdot\text{poly}\left(r\right).$

where $\widehat{f}(x)$ is the linear classifier trained on source domain pre-
trained features (Section 4.1).

The rate at which the error decreases with the number of samples $n$ (per
class-domain pair) is controlled by the gap between the across-class/across-
domain connectivities $\beta,\alpha$ and the across-both connectivity
$\gamma$. Thus, augmentations that tend to change only one of class or domain
will improve the downstream transferability of the learned features.

#### Proof sketch.

The features learned by contrastive pre-training are given by the top $k$
eigenvectors of the adjacency matrix $A$, which is a random matrix defined by
the SBM. For the expected adjacency matrix $\mathbb{E}[A]$, similarly to the
simple example, we can compute the eigenvectors in closed form and show that
the linear head learned on the source data achieves low error on the target.
The main challenge is to show an analogous result for the sampled graph, where
each of the data points per class-domain pair can have a different set of
edges. We use matrix concentration bounds to concentrate the top eigenvectors
of $A$ to those of $\mathbb{E}[A]$ and use matrix perturbation analysis to
show that the predictor learned using $A$ is close to the “ideal” one learned
using $\mathbb{E}[A]$. This shows that contrastive pre-training on the random
graph defined by $A$ also learns transferable features with high probability,
which gives the result.∎

The full proof is in Appendix A.1, where we show that the result holds even
when we have more than 2 domains. This suggests that we can pre-train one
model on the unlabeled data of many domains and the features can transfer
across all of them. Our bound in the appendix also holds with probability
arbitrarily close to 1.

As discussed earlier, contrastive pre-training does not merge source and
target features. Our next result mirrors this observation theoretically in the
SBM setting, showing that a linear classifier on top of the pre-trained
features can classify the domain with low error. Letting
${h}_{\text{dom}}:\operatorname{\mathbb{R}}^{k}\rightarrow\\{1,2\\}$ be a
domain classifier , we define the 0-1 loss for domain classification as
$\mathcal{L}^{D}_{0-1}({h}_{\text{dom}}\circ\widehat{\phi})=\mathbb{E}_{x\sim
P_{U}}[\mathbf{1}[{h}_{\text{dom}}(\widehat{\phi}(x))\neq d_{x}]]$.

######  Proposition 2.

In the setting of Theorem 1, with probability at least $0.999$, there exists a
linear classifier
${h}_{\text{dom}}:\operatorname{\mathbb{R}}^{k}\rightarrow\\{1,2\\}$, such
that ${h}_{\text{dom}}$ composed with the encoder $\widehat{\phi}$ can
distinguish the domains:

$\displaystyle\mathcal{L}^{D}_{0-1}({h}_{\text{dom}}\circ\widehat{\phi})\leq
O\left(\frac{1}{\min\\{\alpha-\gamma,\beta-\gamma\\}^{6}\cdot
n}\right)\cdot\text{poly}\left(r\right).$

The proof is in Appendix A.1 and is similar to Theorem 1.

###  4.4 Setting where ERM/DANN underperform contrastive pre-training

We theoretically show a simple setting in which contrastive learning on
unlabeled data can have higher target extrapolation accuracy than both ERM and
DANN (Equations 1 and 2, respectively). The main intuition of our construction
is that ERM and DANN may underperform when there are subsets of the target
data distribution that are unreachable via data augmentation on any labeled
source input—in other words, inputs $x$ with $d_{x}=2$ such that
$\mathcal{A}(x\mid x^{\prime})=0$ for all $x^{\prime}$ with
$d_{x^{\prime}}=1$. This makes the problem underconstrained for both ERM and
DANN, while contrastive pre-training better leverages the connectivity
information from augmentations on unlabeled source and target inputs to learn
transferable features.

######  Proposition 3.

There exists a set $\mathcal{X}$, a distribution $P_{U}$ and data augmentation
$\mathcal{A}$, such that for some feature dimension $k\in\mathbb{Z}^{+}$, a
linear classifier trained on contrastive pre-trained features achieves 0
target error: $\mathcal{L}_{0-1}(\widehat{f})=0$. However, for all
$k\in\mathbb{Z}^{+}$, there exist minimizers $\widehat{f}_{\text{erm}}$ and
$\widehat{f}_{\text{dann}}$ of the ERM and DANN objectives, respectively, that
have non-zero error:
$\mathcal{L}_{0-1}(\widehat{f}_{\text{erm}})=\mathcal{L}_{0-1}(\widehat{f}_{\text{dann}})=1/3$.

The proof is in Appendix A.2. For ERM, an optimal predictor that minimizes the
ERM objective (1) can make arbitrary predictions on unseen target examples.
For DANN, simply matching the marginal input distributions (even with
augmentations) across domains can potentially swap the classes of the
unreachable target data—this is consistent with the well-known drawback that
DANN with an expressive feature extractor can learn domain-invariant features
by arbitrarily pairing the source and target examples (Shu et al., 2018; Zhao
et al., 2019). Conversely, contrastive pre-training learns features that
enable perfect transferability.

##  5 Contrastive pre-training is a strong domain adaptation method

Our theory gives conditions for which contrastive learning produces effective
features for domain adaptation. We now empirically validate contrastive pre-
training as a competitive domain adaptation method. We observe that
contrastive pre-training achieves comparable performance to strong UDA methods
on four standard domain adaptation datasets.

#### Datasets.

We conduct experiments on DomainNet (Peng et al., 2019; Prabhu et al., 2021),
which contains 40 classes and 4 domains, BREEDS Living-17 and Entity-30
(Santurkar et al., 2020), which are adaptation benchmarks derived from
ImageNet, and STL-10$\to$CIFAR-10 (Coates et al., 2011; Krizhevsky, 2009;
French et al., 2018), which are two classical image recognition datasets often
paired together for domain adaptation.

#### Contrastive pre-training algorithm.

We use SwAV (Caron et al., 2020), a contrastive pre-training algorithm with
high accuracy on ImageNet, for our ImageNet-like datasets (BREEDS and
DomainNet). SwAV uses a multi-crop data augmentation strategy with several
crops of different sizes, followed by horizontal flipping, color distortion,
and Gaussian blurring. We pre-train on the combined source and target
unlabeled data and fine-tune on the source using the same augmentation
pipeline used during pre-training. For STL$\to$CIFAR, we use a publicly
available SimCLR (Chen et al., 2020a) model that is pre-trained on CIFAR.
SimCLR applies random cropping, color distortions, and Gaussian blur for data
augmentation. In our theory we linear probe with the squared loss, but in our
experiments we follow a more standard approach and fine-tune the model (pre-
trained encoder and randomly initialized linear head) with the cross-entropy
loss.

#### Baselines.

We compare with standard ERM on the labeled source data and two strong domain
adaptation methods: DANN (Ganin et al., 2016) and SENTRY (Prabhu et al.,
2021). SENTRY achieves SoTA results on DomainNet when initialized with
ImageNet-pre-trained models. However, to ensure the methods all use the same
data, we initialize the domain adaptation methods with the ERM baseline (no
ImageNet pre-training). For STL$\to$CIFAR, we compare to Dirt-T (Shu et al.,
2018), a SoTA domain adaptation algorithm for this task. For a more complete
comparison, we consider not only using each method’s default augmentations but
also using the contrastive pre-training augmentations to all baselines
(denoted +strong-augs).

###  5.1 Results

#### Main comparison (Table 2).

Method | ERM | SENTRY | DANN | Pre-training | SwAV+extra
---|---|---|---|---|---
Augmentations | Standard | Strong | Standard | Strong | Standard | Strong | Strong | Strong
DomainNet (avg. of 12 pairs) | 26.67 | 37.68 | 31.58 | 25.82 | 38.38 | 45.81 | 44.91 | 51.73
Living-17 | 60.17 | 63.29 | 75.53 | 74.53 | 65.59 | 71.29 | 75.12 | 82.00
Entity-30 | 52.68 | 52.52 | 56.10 | 58.90 | 57.45 | 57.52 | 62.03 | 65.90
STL-10$\to$CIFAR-10 | 44.83 | 57.40 | 53.84 | 43.71 | 46.77 | 55.18 | 75.41 | N/A

Table 2: Test accuracy (%) of baselines and contrastive pre-training on 4
benchmark visual adaptation datasets. The first and second highest numbers for
each dataset are bolded and underlined, respectively. The pre-training
algorithm is SwAV for DomainNet, Living-17, and Entity-30, and SimCLR for
STL$\to$CIFAR. Contrastive pre-training is competitive with the baselines for
all datasets. On STL$\to$CIFAR, SimCLR is slightly higher than Dirt-T, the
previous SoTA (75.3% as reported in Shu et al. (2018)). SwAV+extra is not
bolded as it uses additional data and is therefore not directly comparable.

On average over all pairs of DomainNet, SwAV is within 1% of the best
baseline, DANN+strong-augs (44.91% vs. 45.81%). Contrastive pre-training is
comparable with the best baseline (SENTRY) on Living-17 (75.12% vs. 75.53%)
and improves over the best baseline (SENTRY+strong-augs) by 3.1% on Entity-30.
On STL$\to$CIFAR, the SimCLR target accuracy (75.4%) is very close to the
Dirt-T accuracy reported in the original paper (75.3%). We find that replacing
the default data augmentation used by each baseline with the augmentations
used by contrastive pre-training consistently boosts performance for DANN but
only sometimes boosts performance for SENTRY. Table 4 provides the individual
results for each pair of domains on DomainNet, and Tables 4 and 9 contain
results from additional contrastive pre-training methods, MoCo-V2 (Chen et
al., 2020b) and MoCo-V3 (Chen et al., 2021) (all trained on the same data).

#### Extra unlabeled data from related domains.

We also consider adding extra unlabeled data from other (related) domains in
DomainNet, Living-17, and Entity-30. In particular, we pre-train once on an
unlabeled dataset consisting of a superset of the domains we want to adapt to,
fine-tune on labeled data from one of the domains, and evaluate on all other
domains. While this is not a fair comparison to other domain adaptation
methods, the ability to scale to large unlabeled datasets by pre-training on
all domains simultaneously is a natural advantage of pre-training. This
method, which we denote as SwAV+extra, gives further improvements over SwAV
(nearly 7% on DomainNet, 7% on Living-17, and 4% on Entity-30). In Table 9 we
show results from pre-training on different splits of the BREEDS data, as well
as using additional pre-training methods: Dino+extra (Caron et al., 2021) and
Barlow Twins+extra (Zbontar et al., 2021).

##  6 Evaluating connectivity on real datasets

Recall that our theory (Theorem 1) provides conditions on connectivities
between classes and domains for which contrastive pre-training provably
obtains good target accuracy. We heuristically estimate each of the
connectivity measures on Living-17 and DomainNet to verify the predictions
from our theory in Section 4. We show that the empirical connectivities
satisfy our theoretical conditions for contrastive pre-training to learn
transferable features (e.g., across-domain $>$ across-both connectivity) and
that the connectivity ratios (e.g., across-domain / across-both) are
predictive of target domain accuracy of contrastive pre-training.

#### Estimating connectivity on benchmark datasets.

To verify whether real datasets and augmentations satisfiy the connectivity
requirements for Theorem 1, we compute empirical estimates of the connectivity
measures. Using augmented images from 2 class-domain pairs, we train a
classifier to predict the class-domain pair from which the image originated.
For example, to estimate across-domain connectivity ($\alpha$ from Section
4.2), we choose 2 class-domain pairs with the same class and different domain.
We find that connectivity ratios satisfy our theoretical conditions in all
cases, and the estimates are reported in Table 1. The input space connectivity
is calculated by training classifiers from scratch on individual class-domain
pairs, leading to much smaller training dataset sizes compared to SwAV and
DANN (which are trained on all classes and both domains). Therefore, because
the input space connectivity numbers may be overestimates of the true
connectivity, we also considered fine-tuning a CLIP (Radford et al., 2021)
pre-trained model rather than training from scratch. See Appendix D for more
discussion and details.

Figure 3: (Left) True target accuracy of SwAV (gain over the worst
source/target pair with the same target) vs. the predicted accuracy using the
connectivity ratios on 12 pairs of DomainNet domains. The predictions have a
high coefficient of determination with the observed ($R^{2}=0.78$). (Right)
Ablation of connectivity: pre-training only on inputs far from the margin of a
domain classifier (“most confident”) consistently degrades target accuracy
more than both on random subsets (mean and standard deviation over 3 random
subsets shown) and on inputs nearest the margin (“least confident”).

#### Connectivity ratios correlate with target accuracy.

Section 4 suggests that when the across-domain ($\alpha$) and across-class
($\beta$) connectivities are larger than the across-both ($\gamma$)
connectivity (i.e., $\alpha/\gamma$ and $\beta/\gamma$ are large), contrastive
pre-training learns features with good target accuracy. To investigate the
relation between the connectivity ratios and target accuracy, we consider
fitting the following function, with parameters $w_{1}$ and $w_{2}$, to the
SwAV target accuracy on the 12 pairs of DomainNet domains:

$\displaystyle\text{target
accuracy}\approx(\alpha/\gamma)^{w_{1}}\cdot(\beta/\gamma)^{w_{2}}.$ (8)

Since our theory predicts that target accuracy is high when both ratios are
large, we multiply them to express the logical “and”. To normalize by the
differing intrinsic difficulties of transferring to each target domain of
DomainNet, we fit Eq. 8 to the improvement over the worst pair over all
source/target pairs with the same target domain. Linear regression in log
space yields $w_{1}=14.9$ and $w_{2}=2.7$, with a strong coefficient of
determination ($R^{2}=0.78$) between the predicted and observed accuracies
(left panel of Figure 3). Thus, the target accuracy can be well-explained
using the connectivity ratios alone.

Figures 5 and 6 show that the predicted target accuracies using this method
are also accurate for MoCo-V2 (Chen et al., 2020b) ($R^{2}=0.79$) and MoCo-V3
(Chen et al., 2021) ($R^{2}=0.60$), but much less accurate for the baselines
(both with and without augmentations; average $R^{2}=0.21$).

#### Ablating connectivity degrades target accuracy.

We find that the across-domain connectivity is very important, as those
examples “bridge” the domains—for instance, our linear regression fit puts the
largest weight on the across-domain connectivity ratio. We verify this
intuition by training a domain classifier on Living-17 and pre-training on the
subset of examples on which the classifier is most confident (i.e., the
examples farthest from the classifier’s decision boundary, which intuitively
contribute the least to across-domain connectivity). As controls, we also pre-
train on 1) random subsets of the same size and 2) the examples on which the
classifier is least confident. For 5 different subset sizes, our confidence
pruning method consistently reduces target accuracy compared to both controls
(Figure 3 right).

#### Pre-trained features approximately disentangle class and domain.

| Class (S) | Class (S) | Class (T)
---|---|---|---
| vs. Class (T) | vs. Domain | vs. Domain
Living-17 | 0.397 | 0.013 | 0.016
DomainNet (avg.) | 0.187 | 0.018 | 0.018

Table 3: Cosine similarity of class and domain classifiers trained on SwAV
representations on Living-17 and DomainNet (average over all classes). Linear
classifiers trained to predict the class on the source and target
representations individually learn similar weights and are nearly orthogonal
to the linear weights learned by domain classifiers.

In Section 4, we showed theoretically that contrastive pre-training can learn
a feature space that is simultaneously predictive of the class and domain by
disentangling the information along separate directions. Here, we verify this
empirically using the SwAV feature space. Given a source and target dataset,
we test disentanglement by training the following linear classifiers on the
feature space: 1) Source classifier, which predicts class in the source
domain; 2) Target classifier, which predicts class in the target
domain;‡‡‡Although this cannot be done in practice, we only use the target
labels here for exploratory analysis. and 3) Domain classifier, which predicts
domain (source or target). If the class and domain information are
approximately disentangled along different dimensions, then the linear weights
of the source/target classifier should be orthogonal to the weights of the
domain classifier.

We train the linear classifiers and compute the cosine similarity between
their weights on Living-17 and all pairs of domains from DomainNet (Table 3).
First, we find that the domain classifier is nearly orthogonal to the source
and target classifiers, with an average cosine similarity $<0.02$ between the
linear weights of the domain classifier and the weights of the source and
target classifiers. Second, we find that the source and target classifiers are
relatively well-aligned: on average over all classes, the cosine similarity of
linear weights for the same class from the source and target classifiers is
high (0.40 on Living-17 and average 0.19 on DomainNet). Full results are in
Appendix C.

##  7 Conclusion

While off-the-shelf contrastive pre-training is not intentionally a domain
adaptation method, we find that not only does it theoretically and empirically
transfer well across distribution shifts, but it does so in a way that runs
counter to conventional domain adaptation theory and practice by not learning
domain-invariant features. Given some of the practical advantages of pre-
training (such as being able to pre-train once and then finetune for many
different downstream tasks), we hope that our connectivity theory leads to
improvements for contrastive pre-training as a domain adaptation method, such
as improving pre-training data selection, developing augmentations to increase
connectivity, and improving fine-tuning methods that exploit the geometry of
the pre-trained feature space. Our connectivity theory can also potentially
explain when contrastive pre-training for domain adaptation does _not_ perform
well, such as on the iWildCam2020-WILDS dataset (Sagawa et al., 2022). Future
work may also lead to new domain adaptation methods that focus on increasing
connectivity rather than collapsing domains.

Our theoretical setup is highly stylized and the stochastic block model may
not be a realistic assumption; in particular, it requires a uniform marginal
input distribution. Follow-up work (HaoChen et al., 2022) proves the linear
transferability of contrastive pre-training in a more general setting and only
requires that the same-class across-domain connectivity is larger than the
across-class across-domain connectivity (rather than also requiring across-
class same-domain connectivity to be large). Their analysis leads to an
improved linear probing algorithm which outperforms both SwAV and MoCo-V3 on
Entity-30.

##  8 Ethics

Our experiments use standard benchmark vision datasets in domain adaptation,
which is publicly available data. In general, however, large-scale
unsupervised learning can involve data scraped from the internet which may
lead to privacy concerns. Care should be taken when curating datasets for
large scale contrastive pre-training in practice.

##  9 Acknowledgements

This work was in part supported by the Open Philanthropy Project and NSF Award
Grant No. 1805310, and NSF IIS 2045685. KS was also supported by the Stanford
Computer Science department’s CURIS program. AK was also supported by the
Rambus Corporation Stanford Graduate Fellowship. SMX was also supported by an
NDSEG Fellowship. We would like to thank Kaylee Burns, Aditi Raghunathan, and
the anonymous reviewers, for helpful comments on our draft.

## References

  * Abbe (2018) Emmanuel Abbe.  Community detection and stochastic block models: Recent developments.  _Journal of Machine Learning Research_ , 18(177):1–86, 2018.  URL http://jmlr.org/papers/v18/16-480.html.
  * AlBadawy et al. (2018) EA AlBadawy, A Saha, and MA Mazurowski.  Deep learning for segmentation of brain tumors: Impact of cross-institutional training and testing.  _Med Phys._ , 45, 2018.
  * Arora et al. (2019) Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi.  A theoretical analysis of contrastive unsupervised representation learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pp. 5628–5637, 2019.
  * Ben-David et al. (2010) Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  _Machine Learning_ , 79(1):151–175, 2010.
  * Bouveyron et al. (2016) Charles Bouveyron, P Latouche, and Rawya Zreik.  The stochastic topic block model for the clustering of vertices in networks with textual edges.  _Statistics and Computing_ , 2016.  doi: 10.1007/s11222-016-9713-7.  URL https://hal.archives-ouvertes.fr/hal-01299161.
  * Cai et al. (2021) Tianle Cai, Ruiqi Gao, Jason Lee, and Qi Lei.  A theory of label propagation for subpopulation shift.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 1170–1182. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/cai21b.html.
  * Caron et al. (2020) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 33, pp. 9912–9924, 2020.
  * Caron et al. (2021) Mathilde Caron, Hugo Touvron, Ishan Misra, Herve Jegou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In _International Conference on Computer Vision (ICCV)_ , 2021.
  * Chen et al. (2020a) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International Conference on Machine Learning (ICML)_ , pp. 1597–1607, 2020a.
  * Chen et al. (2020b) Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  _arXiv_ , 2020b.
  * Chen et al. (2021) Xinlei Chen, Saining Xie, and Kaiming He.  An empirical study of training self-supervised vision transformers.  _arXiv preprint arXiv:2104.02057_ , 2021.
  * Coates et al. (2011) Adam Coates, Andrew Ng, and Honlak Lee.  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , volume 15, pp. 215–223, 2011.
  * Dai & Gool (2018) Dengxin Dai and Luc Van Gool.  Dark model adaptation: Semantic image segmentation from daytime to nighttime.  In _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , pp. 3819–3824, 2018.  doi: 10.1109/ITSC.2018.8569387.
  * Davis & Kahan (1970) Chandler Davis and William Morton Kahan.  The rotation of eigenvectors by a perturbation. iii.  _SIAM Journal on Numerical Analysis_ , 7(1):1–46, 1970.
  * Engstrom et al. (2019) Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras.  Robustness (python library).  https://github.com/MadryLab/robustness, 2019.
  * French et al. (2018) Geoff French, Michal Mackiewicz, and Mark Fisher.  Self-ensembling for visual domain adaptation.  In _International Conference on Learning Representations_ , 2018.
  * Ganin et al. (2016) Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Francois Laviolette, Mario March, and Victor Lempitsky.  Domain-adversarial training of neural networks.  _Journal of Machine Learning Research (JMLR)_ , 17, 2016.
  * HaoChen et al. (2021) Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma.  Provable guarantees for self-supervised deep learning with spectral contrastive loss.  _arXiv preprint arXiv:2106.04156_ , 2021.
  * HaoChen et al. (2022) Jeff Z. HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma.  Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations.  _arXiv_ , 2022.
  * He et al. (2020) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In _Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Holland et al. (1983) Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  _Social Networks_ , 5(2):109–137, 1983.
  * Kang et al. (2019) Guoliang Kang, Lu Jiang, Yi Yang, and Alexander G Hauptmann.  Contrastive adaptation network for unsupervised domain adaptation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 4893–4902, 2019.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 1097–1105, 2012.
  * Kumar et al. (2020) Ananya Kumar, Tengyu Ma, and Percy Liang.  Understanding self-training for gradual domain adaptation.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Kumar et al. (2022) Ananya Kumar, Aditi Raghunathan, Robbie Jones, Tengyu Ma, and Percy Liang.  Fine-tuning can distort pretrained features and underperform out-of-distribution.  In _International Conference on Learning Representations (ICLR)_ , 2022.
  * Lei & Rinaldo (2015) Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  _The Annals of Statistics_ , 43:215–237, 2015.
  * Li et al. (2021) Jingjing Li, Erpeng Chen, Zhengming Ding, Lei Zhu, Ke Lu, and Heng Tao Shen.  Maximum density divergence for domain adaptation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 43(11):3918–3930, 2021.
  * Li et al. (2020) Mengxue Li, Yi-Ming Zhai, You-Wei Luo, Peng-Fei Ge, and Chuan-Xian Ren.  _Enhanced transport distance for unsupervised domain adaptation_.  Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * Loshchilov & Hutter (2019) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Mehta et al. (2019) Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai.  Stochastic blockmodels meet graph neural networks.  In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 4466–4474. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/mehta19a.html.
  * Mishra et al. (2021) Samarth Mishra, Kate Saenko, and Venkatesh Saligrama.  Surprisingly simple semi-supervised domain adaptation with pretraining and consistency.  _arXiv preprint arXiv:2101.12727_ , 2021.
  * Peng et al. (2019) Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang.  Moment matching for multi-source domain adaptation.  In _International Conference on Computer Vision (ICCV)_ , 2019.
  * Prabhu et al. (2021) Viraj Prabhu, Shivam Khare, Deeksha Karthik, and Judy Hoffman.  Selective entropy optimization via committee consistency for unsupervised domain adaptation.  In _International Conference on Computer Vision (ICCV)_ , 2021.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning (ICML)_ , volume 139, pp. 8748–8763, 2021.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  ImageNet large scale visual recognition challenge.  _International Journal of Computer Vision_ , 115(3):211–252, 2015.
  * Sagawa et al. (2022) Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, H. Marklund, Sara Beery, E. David, I. Stavness, Wei Guo, J. Leskovec, Kate Saenko, Tatsunori B. Hashimoto, S. Levine, Chelsea Finn, and Percy Liang.  Extending the WILDS benchmark for unsupervised adaptation.  In _International Conference on Learning Representations (ICLR)_ , 2022.
  * Santurkar et al. (2020) Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry.  Breeds: Benchmarks for subpopulation shift.  _arXiv_ , 2020.
  * Shimodaira (2000) Hidetoshi Shimodaira.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of Statistical Planning and Inference_ , 90:227–244, 2000.
  * Shu et al. (2018) Rui Shu, Hung H. Bui, Hirokazu Narui, and Stefano Ermon.  A DIRT-T approach to unsupervised domain adaptation.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Stewart (1977) Gilbert W Stewart.  On the perturbation of pseudo-inverses, projections and linear least squares problems.  _SIAM review_ , 19(4):634–662, 1977.
  * Sun et al. (2020) Pei Sun, Henrik Kretzschmar, Xerxes Dotiwalla, Aurelien Chouard, Vijaysai Patnaik, Paul Tsui, James Guo, Yin Zhou, Yuning Chai, Benjamin Caine, Vijay Vasudevan, Wei Han, Jiquan Ngiam, Hang Zhao, Aleksei Timofeev, Scott Ettinger, Maxim Krivokon, Amy Gao, Aditya Joshi, Sheng Zhao, Shuyang Cheng, Yu Zhang, Jonathon Shlens, Zhifeng Chen, and Dragomir Anguelov.  Scalability in perception for autonomous driving: Waymo open dataset, 2020\.
  * Sun et al. (2019) Yu Sun, Eric Tzeng, Trevor Darrell, and Alexei A. Efros.  Unsupervised domain adaptation through self-supervision.  _arXiv preprint arXiv:1909.11825_ , 2019.
  * Tan et al. (2020) Shuhan Tan, Xingchao Peng, and Kate Saenko.  Class-imbalanced domain adaptation: An empirical odyssey.  _arXiv preprint arXiv:1910.10320_ , 2020.
  * Thota & Leontidis (2021) Mamatha Thota and Georgios Leontidis.  Contrastive domain adaptation.  _arXiv_ , 2021.
  * Tosh et al. (2021) Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu.  Contrastive estimation reveals topic posterior information to linear models.  _Journal of Machine Learning Research (JMLR)_ , 22(281):1–31, 2021.
  * Tzeng et al. (2014) Eric Tzeng, Judy Hoffman, N. Zhang, Kate Saenko, and Trevor Darrell.  Deep domain confusion: Maximizing for domain invariance.  In _Computer Vision and Pattern Recognition (CVPR)_ , 2014.
  * Tzeng et al. (2017) Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell.  Adversarial discriminative domain adaptation.  In _Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Wang et al. (2021) Rui Wang, Zuxuan Wu, Zejia Weng, Jingjing Chen, Guo-Jun Qi, and Yu-Gang Jiang.  Cross-domain contrastive learning for unsupervised domain adaptation.  _arXiv_ , 2021.
  * Wei et al. (2021) Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma.  Theoretical analysis of self-training with deep networks on unlabeled data.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=rC8sJ4i6kaH.
  * Xiao & Zhang (2021) Ni Xiao and Lei Zhang.  _Dynamic weighted learning for unsupervised domain adaptation_.  Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
  * Yu et al. (2020) Fisher Yu, Haofeng Chen, Xin Wang, Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell.  Bdd100k: A diverse driving dataset for heterogeneous multitask learning.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Zbontar et al. (2021) Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stephane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  In _International Conference on Machine Learning (ICML)_ , volume 139, 2021.
  * Zhao et al. (2019) Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon.  On learning invariant representations for domain adaptation.  In _International Conference on Machine Learning (ICML)_ , 2019.

##  Appendix A Additional details for Section 4

###  A.1 Proof of Theorem 1

We first summarize the setting of the multi-domain multi-class classification
problem that we will analyze.

Consider a multi-way classification problem, where $r$ is the number of
classes, $m$ is the number of domains, $n$ is the number of data in each class
of each domain. The total number of data is $N=rmn$. The set of all nodes is
$\mathcal{X}$.

For data $x\in\mathcal{X}$, we use $d_{x}\in[m]$ and ${y_{x}}\in[r]$ to denote
its domain and class, respectively.

We consider a stochastic block model for the graph, where the probability of
existence of an edge between $x$ and $x^{\prime}$ is: (1) $\rho$ if
$d_{x}=d_{x^{\prime}}$ and ${y_{x}}={y_{x^{\prime}}}$, (2) $\alpha$ if
$d_{x}\neq d_{x^{\prime}}$ and ${y_{x}}={y_{x^{\prime}}}$, (3) $\beta$ if
$d_{x}=d_{x^{\prime}}$ and ${y_{x}}\neq{y_{x^{\prime}}}$, (4) $\gamma$ if
$d_{x}\neq d_{x^{\prime}}$ and ${y_{x}}\neq{y_{x^{\prime}}}$.

Let $A\in\operatorname{\mathbb{R}}^{N\times N}$ be the adjacency matrix of the
graph. A random positive pair $(x,x^{+})$ is a uniform random edge (i.e.,
$p_{+}(x,x^{+})=A_{xx^{+}}/\sum_{x^{\prime},x^{\prime\prime}}A_{x^{\prime}x^{\prime\prime}}$),
a negative pair $(x,x^{-})$ are two uniform random nodes. Let $k=m+r-1$ be the
feature dimension and $f:\mathcal{X}\rightarrow\operatorname{\mathbb{R}}^{k}$
be the feature map learned by minimizing the population spectral contrastive
loss:

$\displaystyle-2\operatorname{\mathrm{\mathbb{E}}}_{x,x^{+}}[f(x)^{\top}f(x^{+})]+\operatorname{\mathrm{\mathbb{E}}}_{x,x^{-}}\left[\left(f(x)^{\top}f(x^{-})\right)^{2}\right].$
(9)

Let $\mathcal{S}=\\{x\in\mathcal{X}:d_{x}=1\\}$ and
$\mathcal{T}=\\{x\in\mathcal{X}:d_{x}\neq 1\\}$ be source and target domains,
respectively. Given the labeled source domain data, we learn the linear head

$\displaystyle\hat{h}=\operatorname*{arg\,min}_{h\in\operatorname{\mathbb{R}}^{(k\times
r)}}\sum_{x\in\mathcal{S}}\left(\left\lVert
b^{\top}f(x)-\vec{y}_{x}\right\rVert_{2}^{2}+\eta\left\lVert
b\right\rVert_{F}^{2}\right),$ (10)

where
$\vec{y}_{{x}}=e_{{y_{x}}}-\frac{1}{r}\cdot\mathbf{1}\in\operatorname{\mathbb{R}}^{r}$
is the mean-zero one-hot embedding of the label, $\eta>0$ is the
regularization strength. For data $x\in\mathcal{T}$, we use
$\textup{pred}(x)=\operatorname*{arg\,max}_{i}(\hat{b}^{\top}f(x))_{i}$ as the
predictor.

We have the following more generalized version of Theorem 1.

######  Theorem 4.

Let $\zeta>0$ and $\epsilon\in\left(0,\frac{1}{2}\right)$ be arbitrary
constants. In the above stochastic block model, assume
$\rho>\max\\{\alpha,\beta\\}$ and $\gamma<\min\\{\alpha,\beta\\}$. Then, there
exists $\tilde{\xi}\in[1-\epsilon,1]$, such that for any
$n\geq\Omega\left(\frac{rm}{\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}}\right)$
and regularization strength
$\eta\in\left(0,\frac{(\alpha-\gamma)\epsilon}{2r\rho}\right]$, with
probability at least $1-n^{-\zeta}$, we have

$\displaystyle\sum_{x\in\mathcal{T}}\left\lVert\hat{b}^{\top}f(x)-\tilde{\xi}\vec{y}_{x}\right\rVert_{2}^{2}\leq
O\left(\frac{1}{\eta^{4}\cdot\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}}\right)\cdot\textup{poly}(r,m).$
(11)

Furthermore, the target error can be bounded by

$\displaystyle\text{I\kern-1.49994ptP}_{x\sim\mathcal{T}}\left(\textup{pred}(x)\neq{y_{x}}\right)\leq
O\left(\frac{1}{\eta^{4}\cdot\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}\cdot
n}\right)\cdot\textup{poly}(r,m).$ (12)

Note that setting $\epsilon=\frac{1}{4}$ and $\zeta=1$ proves Theorem 1. In
the rest of this subsection, we will give a proof of Theorem 4.

Let $A_{k}\in\operatorname{\mathbb{R}}^{N\times N}$ be the rank-$k$
approximation of the adjacency matrix $A$, which contains the top $k$
components of $A$’s SVD decomposition. We use
$A_{k,(\mathcal{T},\mathcal{S})}$ to denote the matrix by restricting $A_{k}$
to the rows corresponding to the source and the columns corresponding to the
target. We use $A_{k,(\mathcal{S},\mathcal{S})}$ to denote the matrix by
restricting $A_{k}$ to the rows and columns corresponding to the source.

Let $Y\in\operatorname{\mathbb{R}}^{N\times r}$ be the label matrix where on
the $x$-th row it contains the label target
$\vec{y}_{{x}=}e_{{y_{x}}}-\frac{1}{r}\cdot\mathbf{1}$. Let
$Y_{\mathcal{S}}\in\operatorname{\mathbb{R}}^{|\mathcal{S}|\times r}$ and
$Y_{\mathcal{T}}\in\operatorname{\mathbb{R}}^{|\mathcal{T}|\times r}$ be the
matrices by restricting $Y$ to the source and target domain, respectively.

Let $\textup{pred}\in\operatorname{\mathbb{R}}^{N\times r}$ be the matrix with
$\hat{b}^{\top}f(x)$ on its $x$-th row. Let $\textup{pred}_{\mathcal{T}}$ be
the matrix by restricting pred to the target domain. The following lemma gives
a closed-form expression for the prediction on the target domain.

######  Lemma 1.

In the setting of Theorem 4, let
$|E|\triangleq\sum_{x,x^{\prime}}A_{xx^{\prime}}$ be the total number of
edges. Then,

$\displaystyle\textup{pred}_{\mathcal{T}}=A_{k,(\mathcal{T},\mathcal{S})}\left(A_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}},$ (13)

where $(\cdot)^{\dagger}$ is the Moore–Penrose inverse, $|\mathcal{S}|$ is the
number of data in the source domain.

###### Proof of Lemma 1.

By the definition of spectral contrastive loss, we can rewrite the loss
function as

$\displaystyle-2\sum_{x,x^{\prime}}\frac{A_{xx^{\prime}}}{|E|}f(x)^{\top}f(x^{\prime})+\sum_{x,x^{\prime}}\frac{1}{N^{2}}\left(f(x)^{\top}f(x^{\prime})\right)^{2}$
(14) $\displaystyle=$
$\displaystyle\left\lVert\frac{N}{|E|}\cdot{A}-\left(\frac{1}{\sqrt{N}}\cdot
F\right)\left(\frac{1}{\sqrt{N}}\cdot
F\right)^{\top}\right\rVert_{F}^{2}+\textup{const},$ (15)

where $F\in\operatorname{\mathbb{R}}^{N\times k}$ is the matrix which the
$x$-th row contains $f(x)^{\top}$. According to the Eckart–Young–Mirsky
theorem, the minimizer of this loss function is $F=\frac{N}{\sqrt{|E|}}S_{k}$
where $S_{k}\in\operatorname{\mathbb{R}}^{N\times k}$ is a matrix such that
$A_{k}=S_{k}^{\top}S_{k}$.

Let $S_{k,\mathcal{S}}\in\operatorname{\mathbb{R}}^{|\mathcal{S}|\times k}$ be
the matrix gotten by restricting $S_{k}$ to the rows corresponding to the
source data, and $S_{k,\mathcal{T}}$ be the matrix gotten by restricting
$S_{k}$ to the rows corresponding to the target data. The head learned on the
source domain can be expressed as

$\displaystyle\hat{h}$
$\displaystyle=\operatorname*{arg\,min}_{h\in\operatorname{\mathbb{R}}^{(k\times
r)}}\sum_{x\in\mathcal{S}}\left(\left\lVert
h^{\top}f(x)-\vec{y}_{{x}}\right\rVert_{2}^{2}+\eta\left\lVert
h\right\rVert_{F}^{2}\right)$ (16) $\displaystyle=\frac{\sqrt{|E|}}{N}\cdot
S_{k,\mathcal{S}}^{\top}\left(S_{k,\mathcal{S}}S_{k,\mathcal{S}}^{\top}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}.$ (17)

Therefore, the prediction on the target domain $\textup{pred}_{\mathcal{T}}$
is

$\displaystyle\textup{pred}_{\mathcal{T}}=F_{\mathcal{T}}\hat{h}=S_{k,\mathcal{T}}S_{k,\mathcal{S}}^{\top}\left(S_{k,\mathcal{S}}S_{k,\mathcal{S}}^{\top}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}=A_{k,(\mathcal{T},\mathcal{S})}\left(A_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}.$ (18)

∎

The following lemma shows that the prediction in the expectation graph is
accuracte.

######  Lemma 2.

Let $\tilde{A}\triangleq\operatorname{\mathrm{\mathbb{E}}}[A]$ be the
expectation of the adjacency matrix. Then, for any $\xi>0$, we have

$\displaystyle\tilde{A}_{k,(\mathcal{T},\mathcal{S})}\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\xi
I\right)^{\dagger}Y_{\mathcal{S}}=\frac{\lambda_{c}}{\lambda_{c}+m\xi}\cdot
Y_{\mathcal{T}},$ (19)

where $k=r+m-1$ and $\lambda_{c}\triangleq
n\rho-n\beta+n(m-1)\alpha-n(m-1)\gamma$. Furthermore, if we use
$\tilde{\lambda}_{i}$ to denote the $i$-th largest eigenvalue of $\tilde{A}$,
we have
$\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1}=n\min\left\\{r(\beta-\gamma),m(\alpha-\gamma)\right\\}$
and $\tilde{\lambda}_{1}\leq nrm\rho$.

###### Proof of Lemma 2.

By the definition of the graph, every entry $\tilde{A}_{xx^{\prime}}$ is in
the set of $\\{\rho,\beta,\alpha,\gamma\\}$, depending on whether $x$ and
$x^{\prime}$ belong to the same domain/class. We can index every node $x$ as
$(d_{x},{y_{x}},{\textup{id}_{x}})$, where ${\textup{id}_{x}}\in[n]$ is the
index of $x$ within domain $d_{x}$ and class ${y_{x}}$. For any integer $i\geq
1$, we use $\mathbf{1}_{i}$ to denote the $i$-dimensional all-one vector, and
$\bar{\mathbf{1}}_{i}=\mathbf{1}_{i}/\left\lVert\mathbf{1}_{i}\right\rVert$ be
its normalized unit vector. We use $\mathbb{S}^{i}$ to denote the
$i$-dimensional unit-norm sphere.

It can be verified that $\tilde{A}$ can be decomposed into the sum of several
matrix Kronecker products:

$\displaystyle\tilde{A}=\ \ \ $ $\displaystyle(\beta-\gamma)\cdot
I_{m}\otimes(\mathbf{1}_{r}\mathbf{1}_{r}^{\top})\otimes(\mathbf{1}_{n}\mathbf{1}_{n}^{\top})$
(20) $\displaystyle+$
$\displaystyle(\alpha-\gamma)\cdot(\mathbf{1}_{m}\mathbf{1}_{m}^{\top})\otimes
I_{r}\otimes(\mathbf{1}_{n}\mathbf{1}_{n}^{\top})$ (21) $\displaystyle+$
$\displaystyle(\rho-\beta-\alpha+\gamma)\cdot I_{m}\otimes
I_{r}\otimes(\mathbf{1}_{n}\mathbf{1}_{n}^{\top})$ (22) $\displaystyle+$
$\displaystyle\gamma\cdot(\mathbf{1}_{m}\mathbf{1}_{m}^{\top})\otimes(\mathbf{1}_{r}\mathbf{1}_{r}^{\top})\otimes(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}).$
(23)

As a result, $\tilde{A}$ has the following four sets of eigenvectors with non-
zero eigenvalues:

  * •

$\bar{\mathbf{1}}_{m}\otimes\bar{\mathbf{1}}_{r}\otimes\bar{\mathbf{1}}_{n}$.
The corresponding eigenvalue is $\lambda_{a}\triangleq
n\rho+n(r-1)\beta+n(m-1)\alpha+n(m-1)(r-1)\gamma$.

  * •

$u\otimes\bar{\mathbf{1}}_{r}\otimes\bar{\mathbf{1}}_{n}$, where
$u\in\mathbb{S}^{m}$ and $u^{\top}\mathbf{1}_{m}=0$. The corresponding
eigenvalue is $\lambda_{b}\triangleq n\rho+n(r-1)\beta-n\alpha-n(r-1)\gamma$.

  * •

$\bar{\mathbf{1}}_{m}\otimes v\otimes\bar{\mathbf{1}}_{n}$, where
$v\in\mathbb{S}^{r}$ and $v^{\top}\mathbf{1}_{r}=0$. The corresponding
eigenvalue is $\lambda_{c}\triangleq n\rho-n\beta+n(m-1)\alpha-n(m-1)\gamma$.

  * •

$u\otimes v\otimes\bar{\mathbf{1}}_{n}$, where $u\in\mathbb{S}^{m}$,
$v\in\mathbb{S}^{r}$ and $u^{\top}\mathbf{1}_{m}=0$,
$v^{\top}\mathbf{1}_{r}=0$. The corresponding eigenvalue is
$\lambda_{d}\triangleq n\rho-n\beta-n\alpha+n\gamma$.

Since $\rho>\max\\{\beta,\alpha\\}$ and $\min\\{\beta,\alpha\\}>\gamma$, we
know that all of these eigenvalues are positive. When $k=r+m-1$,
$\tilde{A}_{k}$ will contain exactly the first three sets of eigenvectors
since they correspond to the top-$k$ eigenvalues. This suggests that we can
write $\tilde{A}_{k}$ as follows

$\displaystyle\tilde{A}_{k}=\lambda_{a}\cdot\bar{\mathbf{1}}_{m}\bar{\mathbf{1}}_{m}^{\top}\otimes\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}+\lambda_{b}\cdot(I_{m}-\bar{\mathbf{1}}_{m}\bar{\mathbf{1}}_{m}^{\top})\otimes\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}+\lambda_{c}\cdot\bar{\mathbf{1}}_{m}\bar{\mathbf{1}}_{m}^{\top}\otimes(I_{r}-\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top})\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}.$
(24)

Restricting to the source domain, we have

$\displaystyle\tilde{A}_{k,(\mathcal{S},\mathcal{S})}=\frac{\lambda_{a}+(m-1)\lambda_{b}}{m}\cdot\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}+\frac{\lambda_{c}}{m}\cdot(I_{r}-\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top})\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}.$
(25)

By the definition of pseudoinverse, we have

$\displaystyle\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\xi
I\right)^{\dagger}=\left(\frac{\lambda_{a}+(m-1)\lambda_{b}}{m}+\xi\right)^{-1}\cdot\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}+\left(\frac{\lambda_{c}}{m}+\xi\right)^{-1}\cdot(I_{r}-\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top})\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}.$
(26)

Notice that $Y_{\mathcal{S}}$ satisfies
$\left(\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}\right)Y_{\mathcal{S}}=0$
and
$\left((I_{r}-\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top})\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}\right)Y_{\mathcal{S}}=Y_{\mathcal{S}}$,
we have

$\displaystyle\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\xi
I\right)^{\dagger}Y_{\mathcal{S}}=\left(\frac{\lambda_{c}}{m}+\xi\right)^{-1}Y_{\mathcal{S}}.$
(27)

We can also write $\tilde{A}_{k,(\mathcal{X},\mathcal{S})}$ in the form of
kronecker products as follows:

$\displaystyle\tilde{A}_{k,(\mathcal{X},\mathcal{S})}=\frac{\lambda_{a}}{m}\cdot\mathbf{1}_{m}\otimes\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}+\lambda_{b}\cdot(e_{1}-\frac{1}{m}\mathbf{1}_{m})\otimes\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}+\frac{\lambda_{c}}{m}\cdot\mathbf{1}_{m}\otimes(I_{r}-\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top})\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}.$
(28)

Again, using the fact that
$\left(\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top}\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}\right)Y_{\mathcal{S}}=0$
and
$\left((I_{r}-\bar{\mathbf{1}}_{r}\bar{\mathbf{1}}_{r}^{\top})\otimes\bar{\mathbf{1}}_{n}\bar{\mathbf{1}}_{n}^{\top}\right)Y_{\mathcal{S}}=Y_{\mathcal{S}}$,
we have

$\displaystyle\tilde{A}_{k,(\mathcal{X},\mathcal{S})}\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\xi
I\right)^{\dagger}Y_{\mathcal{S}}=\frac{\lambda_{c}}{\lambda_{c}+m\xi}\mathbf{1}_{m}\otimes
Y_{\mathcal{S}}.$ (29)

Finally, noticing that $\mathbf{1}_{m}\otimes Y_{\mathcal{S}}=Y$ finishes the
proof.

∎

The followng lemma shows that when a matrix $A$ is close to $\tilde{A}$, their
rank-$k$ approximations $A_{k}$ and $\tilde{A}_{k}$ are also close.

######  Lemma 3.

Let $\tilde{A}\triangleq\operatorname{\mathrm{\mathbb{E}}}[A]$ be the
expectation of the adjacency matrix. Let $A_{k}$ and $\tilde{A}_{k}$ be the
rank-$k$ approximations of $A$ and $\tilde{A}$, respectively. Let
$\tilde{\lambda}_{i}$ be the $i$-th largest eigenvalue of $\tilde{A}$,
$\left\lVert\cdot\right\rVert$ be the operator norm of a matrix or
$\ell_{2}$-norm of a vector. Then, when $\left\lVert
A-\tilde{A}\right\rVert<\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1}$, we have

$\displaystyle\left\lVert
A_{k}-\tilde{A}_{k}\right\rVert\leq\left(1+\frac{2\left\lVert
A-\tilde{A}\right\rVert+2\left\lVert\tilde{A}\right\rVert}{(\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1})-\left\lVert
A-\tilde{A}\right\rVert}\right)\cdot\left\lVert A-\tilde{A}\right\rVert.$ (30)

###### Proof of Lemma 3.

Let the SVD decomposition of $A$ and $\tilde{A}$ be as follows:

$\displaystyle
A=\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}\begin{bmatrix}\Sigma_{1}&0\\\
0&\Sigma_{2}\end{bmatrix}\begin{bmatrix}U_{1}^{\top}\\\
U_{2}^{\top}\end{bmatrix},$ (31)
$\displaystyle\tilde{A}=\begin{bmatrix}\tilde{U}_{1}&\tilde{U}_{2}\end{bmatrix}\begin{bmatrix}\tilde{\Sigma}_{1}&0\\\
0&\tilde{\Sigma}_{2}\end{bmatrix}\begin{bmatrix}\tilde{U}_{1}^{\top}\\\
\tilde{U}_{2}^{\top}\end{bmatrix},$ (32)

where $\Sigma_{1}$ and $\tilde{\Sigma}_{1}$ contain the top $k$ eigenvalues of
$A$ and $\tilde{A}$, respectively. By the definition of rank-$k$
approximation, we have $A_{k}=U_{1}\Sigma_{1}U_{1}^{\top}$ and
$\tilde{A}_{k}=\tilde{U}_{1}\tilde{\Sigma}_{1}\tilde{U}_{1}^{\top}$.
Therefore,

$\displaystyle\left\lVert A_{k}-\tilde{A}_{k}\right\rVert=\left\lVert
U_{1}\Sigma_{1}U_{1}^{\top}-\tilde{U}_{1}\tilde{\Sigma}_{1}\tilde{U}_{1}^{\top}\right\rVert=\max_{v\in\operatorname{\mathbb{R}}^{N}:\left\lVert
v\right\rVert=1}\left\lVert\left(U_{1}\Sigma_{1}U_{1}^{\top}-\tilde{U}_{1}\tilde{\Sigma}_{1}\tilde{U}_{1}^{\top}\right)v\right\rVert$
(33) $\displaystyle\leq$
$\displaystyle\underbrace{\max_{v\in\operatorname{\mathbb{R}}^{N}:\left\lVert
v\right\rVert=1,v^{\top}\tilde{U}_{2}=0}\left\lVert\left(U_{1}\Sigma_{1}U_{1}^{\top}-\tilde{U}_{1}\tilde{\Sigma}_{1}\tilde{U}_{1}^{\top}\right)v\right\rVert}_{C_{1}}+\underbrace{\max_{v\in\operatorname{\mathbb{R}}^{N}:\left\lVert
v\right\rVert=1,v^{\top}\tilde{U}_{1}=0}\left\lVert\left(U_{1}\Sigma_{1}U_{1}^{\top}-\tilde{U}_{1}\tilde{\Sigma}_{1}\tilde{U}_{1}^{\top}\right)v\right\rVert}_{C_{2}}.$
(34)

Let
$\delta\triangleq\min\\{\lambda_{k}-\tilde{\lambda}_{k+1},\tilde{\lambda}_{k}-\lambda_{k+1}\\}$.
According to Weyl’s inequality, we have

$\displaystyle\left\lVert\begin{bmatrix}\Sigma_{1}&0\\\
0&\Sigma_{2}\end{bmatrix}-\begin{bmatrix}\tilde{\Sigma}_{1}&0\\\
0&\tilde{\Sigma}_{2}\end{bmatrix}\right\rVert\leq\left\lVert
A-\tilde{A}\right\rVert.$ (35)

So we have
$\delta\geq\left(\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1}\right)-\left\lVert
A-\tilde{A}\right\rVert>0$. Now we bound $C_{1}$ and $C_{2}$ separately. To
bound $C_{1}$, we have

$\displaystyle C_{1}\leq$ $\displaystyle\left\lVert
A-\tilde{A}\right\rVert+\max_{v\in\operatorname{\mathbb{R}}^{N}:\left\lVert
v\right\rVert=1,v^{\top}\tilde{U}_{2}=0}\left\lVert\left(U_{2}\Sigma_{2}U_{2}^{\top}-\tilde{U}_{2}\tilde{\Sigma}_{2}\tilde{U}_{2}^{\top}\right)v\right\rVert$
(36) $\displaystyle\leq$ $\displaystyle\left\lVert
A-\tilde{A}\right\rVert+\left\lVert
U_{2}\right\rVert\cdot\left\lVert\Sigma_{2}\right\rVert\cdot\left\lVert
U_{2}^{\top}\tilde{U}_{1}\right\rVert$ (37) $\displaystyle\leq$
$\displaystyle\left(1+\frac{\left\lVert\Sigma_{2}\right\rVert}{\delta}\right)\left\lVert
A-\tilde{A}\right\rVert$ (38)

where the first line follows the triangle inequality, the second line uses
$v^{\top}\tilde{U}_{2}=0$, and the third line uses Davis-Kahan theorem (Davis
& Kahan, 1970). Similarly, to bound $C_{2}$, we have

$\displaystyle C_{2}$
$\displaystyle=\max_{v\in\operatorname{\mathbb{R}}^{N}:\left\lVert
v\right\rVert=1,v^{\top}\tilde{U}_{1}=0}\left\lVert
U_{1}\Sigma_{1}U_{1}^{\top}v\right\rVert_{2}$ (39)
$\displaystyle\leq\left\lVert
U_{1}\right\rVert\cdot\left\lVert\Sigma_{2}\right\rVert\cdot\left\lVert
U_{1}^{\top}\tilde{U}_{2}\right\rVert\leq\frac{\left\lVert\Sigma_{1}\right\rVert\cdot\left\lVert
A-\tilde{A}\right\rVert}{\delta}.$ (40)

Adding $C_{1}$ and $C_{2}$ together we have

$\displaystyle\left\lVert A_{k}-\tilde{A}_{k}\right\rVert\leq$
$\displaystyle\left(1+\frac{\left\lVert\Sigma_{1}\right\rVert+\left\lVert\Sigma_{2}\right\rVert}{\delta}\right)\cdot\left\lVert
A-\tilde{A}\right\rVert$ (41) $\displaystyle\leq$
$\displaystyle\left(1+\frac{2\left\lVert
A-\tilde{A}\right\rVert+2\left\lVert\tilde{A}\right\rVert}{(\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1})-\left\lVert
A-\tilde{A}\right\rVert}\right)\cdot\left\lVert A-\tilde{A}\right\rVert,$ (42)

where the second line again uses Weyl’s inequality. ∎

To bound the differene between $A$ and $\tilde{A}$, we use the following lemma
which is adapted from Theorem 5.2 of (Lei & Rinaldo, 2015).

######  Lemma 4.

Let $A$ be the adjacency matrix of a random graph on $N$ nodes in which edges
occur independently. Let $E[A]=\tilde{A}=(\tilde{A}_{ij})_{i,j=1,...,N}$ be
the expectation adjacency matrix and assume that
$N\max_{ij}\tilde{A}_{ij}\geq\log N$. Then, for any $\zeta>0$ there exists a
constant $C=C(\zeta)$ such that

$\displaystyle\left\lVert A-P\right\rVert\leq C\sqrt{N}$ (43)

with probability at least $1-N^{-2\zeta}$.

Now we prove Theorem 4 using the above lemmas.

###### Proof of Theorem 4.

By Lemma 1, we have that the prediction on the target domain is

$\displaystyle\textup{pred}_{\mathcal{T}}=A_{k,(\mathcal{T},\mathcal{S})}\left(A_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}.$ (44)

Let $|\tilde{E}|\triangleq\mathbf{1}_{N}^{\top}\tilde{A}\mathbf{1}_{N}$ be the
expectation of number of edges in the graph. We define the ideal prediction as

$\displaystyle\widetilde{\textup{pred}}_{\mathcal{T}}=\tilde{A}_{k,(\mathcal{T},\mathcal{S})}\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\frac{|\tilde{E}|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}.$ (45)

We will bound the difference between $\textup{pred}_{\mathcal{T}}$ and
$\tilde{\textup{pred}}_{\mathcal{T}}$. For every class $c\in[r]$, define the
following error vector

$\displaystyle e^{c}\triangleq
A_{k,(\mathcal{T},\mathcal{S})}\left(A_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y^{c}_{\mathcal{S}}-\tilde{A}_{k,(\mathcal{T},\mathcal{S})}\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y^{c}_{\mathcal{S}},$ (46)

where $Y^{c}_{\mathcal{S}}$ is the $c$-th column of $Y_{\mathcal{S}}$.

Using the perturbation bound for the pseudoinverse matrix (Stewart, 1977), we
have

$\displaystyle\left\lVert e^{c}\right\rVert\leq$ $\displaystyle\left\lVert
A_{k,(\mathcal{T},\mathcal{S})}-\tilde{A}_{k,(\mathcal{T},\mathcal{S})}\right\rVert\cdot\left\lVert\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}\right\rVert\cdot\left\lVert
Y_{\mathcal{S}}^{c}\right\rVert$ (47) $\displaystyle+\left\lVert
A_{k,(\mathcal{T},\mathcal{S})}\right\rVert\cdot\left\lVert\left(A_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}-\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\frac{|E|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}\right\rVert\cdot\left\lVert
Y_{\mathcal{S}}^{c}\right\rVert$ (48) $\displaystyle\leq$
$\displaystyle\left\lVert
A_{k}-\tilde{A}_{k}\right\rVert\cdot\frac{N^{2}}{\eta|E|\cdot|S|}\cdot\left\lVert
Y_{\mathcal{S}}^{c}\right\rVert+\left\lVert
A_{k}\right\rVert\cdot\frac{1+\sqrt{5}}{2}\cdot\left(\frac{N^{2}}{\eta|E|\cdot|S|}\right)^{2}\cdot\left\lVert
A_{k}-\tilde{A}_{k}\right\rVert\cdot\left\lVert
Y_{\mathcal{S}}^{c}\right\rVert.$ (49)

By lemma 4, there exists constant $C=C(\zeta)$ such that $\left\lVert
A-\tilde{A}\right\rVert\leq C\sqrt{N}$ with probability at least
$1-N^{-2\zeta}$ for any $N>\Omega(1/\rho)$. From now on, we assume this high
probability event happens. Let
$\Delta\triangleq\min\\{r(\beta-\gamma),m(\alpha-\gamma)\\}$. According to
Lemma 2, we know that $\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1}=n\Delta$. If
our choice of $N$ further satisfies
$N\geq\left(\frac{2rmC}{\Delta}\right)^{2}$, we have $\left\lVert
A-\tilde{A}\right\rVert\leq\frac{1}{2}(\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1})$,
so from Lemma 3 we have

$\displaystyle\left\lVert A_{k}-\tilde{A}_{k}\right\rVert\leq
O\left(\frac{\tilde{\lambda}_{1}}{\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1}}\cdot\left\lVert
A-\tilde{A}\right\rVert\right)\leq
O\left(\frac{\tilde{\lambda}_{1}}{\tilde{\lambda}_{k}-\tilde{\lambda}_{k+1}}\cdot\sqrt{N}\right).$
(50)

According to Lemma 2, we know that $\tilde{\lambda}_{1}\leq nrm\rho$, so we
have

$\displaystyle\left\lVert A_{k}-\tilde{A}_{k}\right\rVert\leq
O\left(\frac{rm\rho\sqrt{N}}{\Delta}\right).$ (51)

By Hoeffding’s inequality, with probability at least $1-2e^{-2N^{2}}$ we have
$||E|-|\tilde{E}||\leq N$. From now on, we assume this high-probability event
happens. The total failure probability so far is $N^{-2\zeta}+2e^{-2N^{2}}\leq
N^{-\zeta}$. By the definition of graph, we have $|\tilde{E}|\geq\frac{\rho
N^{2}}{rm}$. If our choice of $N$ further satisfies $N\geq\frac{2rm}{\rho}$,
we have $|E|\geq\frac{\rho N^{2}}{2rm}$, hence

$\displaystyle\frac{|E|\cdot|S|}{N^{2}}\geq\frac{\rho N}{2rm^{2}}.$ (52)

Substituting (51) and (52) into (49) gives:

$\displaystyle\left\lVert e^{c}\right\rVert\leq
O\left(\frac{1}{\Delta\eta^{2}\sqrt{N}}\right)\cdot\textup{poly}(r,m)\cdot\left\lVert
Y_{\mathcal{S}}^{c}\right\rVert.$ (53)

Summing over all classes $c$ and noticing that $\left\lVert
Y_{\mathcal{S}}^{c}\right\rVert\leq\sqrt{N}$ leads to

$\displaystyle\left\lVert e\right\rVert_{F}\leq
O\left(\frac{1}{\Delta\eta^{2}}\right)\cdot\textup{poly}(r,m)$ (54)

Let $\xi=\frac{|E|}{N^{2}}\cdot\eta\cdot|S|$ and
$\tilde{\xi}=\frac{|\tilde{E}|}{N^{2}}\cdot\eta\cdot|S|$. We have

$\displaystyle\left|\frac{\lambda_{c}}{\lambda_{c}+m\xi}-\frac{\lambda_{c}}{\lambda_{c}+m\tilde{\xi}}\right|\leq\frac{m}{\lambda_{c}}\cdot|\xi-\tilde{\xi}|\leq\frac{\eta}{N}\cdot\textup{poly}(r,m).$
(55)

From Lemma 2 we have

$\displaystyle\left\lVert\tilde{A}_{k,(\mathcal{T},\mathcal{S})}\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\frac{|{E}|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}-\tilde{A}_{k,(\mathcal{T},\mathcal{S})}\left(\tilde{A}_{k,(\mathcal{S},\mathcal{S})}+\frac{|\tilde{E}|}{N^{2}}\cdot\eta\cdot|S|\cdot
I\right)^{\dagger}Y_{\mathcal{S}}\right\rVert_{F}$ (56) $\displaystyle=$
$\displaystyle\left|\frac{\lambda_{c}}{\lambda_{c}+m\xi}-\frac{\lambda_{c}}{\lambda_{c}+m\tilde{\xi}}\right|\cdot\left\lVert
Y_{\mathcal{T}}\right\rVert_{F}\leq\frac{1}{\sqrt{N}}\cdot\textup{poly}(r,m).$
(57)

Combining (54) and (57) we have

$\displaystyle\left\lVert\textup{pred}_{\mathcal{T}}-\widetilde{\textup{pred}}_{\mathcal{T}}\right\rVert_{F}\leq
O\left(\frac{1}{\eta^{2}\cdot\min\\{\alpha-\gamma,\beta-\gamma\\}}\right)\cdot\textup{poly}(r,m).$
(58)

Notice that the $x$-th row of $\widetilde{\textup{pred}}_{\mathcal{T}}$ is
$\frac{\lambda_{c}}{\lambda_{c}+m\tilde{\xi}}\cdot y_{y_{x}}$. Since
$\lambda_{c}=n\left(\rho-\beta+(m-1)\alpha-(m-1)\gamma\right)\geq\frac{1}{2}nm(\alpha-\gamma)$,
and
$\tilde{\xi}=\frac{|\tilde{E}|}{N^{2}}\cdot\eta\cdot|S|=\frac{n^{2}rm\rho+n^{2}m(r^{2}-r)\beta+n^{2}r(m^{2}-m)\alpha+n^{2}(r^{2}-r)(m^{2}-m)\gamma}{n^{2}m^{2}r^{2}}\cdot\eta\cdot
rn\leq\eta rn\rho$, we have

$\displaystyle\frac{\lambda_{c}}{\lambda_{c}+m\tilde{\xi}}\geq\frac{1}{1+\frac{2r\rho\eta}{m(\alpha-\gamma)}}\geq
1-\epsilon,$ (59)

where the second inequality follows our assumption on $\eta$.

Since $\textup{pred}_{\mathcal{T}}$ is incorrect on the $x$-th row only if its
difference from the $x$-th row of $\widetilde{\textup{pred}}_{\mathcal{T}}$
has larger norm than $\Omega(1-\epsilon)$, we know the final total error on
the target domains is bounded by
$O\left(\frac{1}{\eta^{4}N\cdot\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}}\right)\cdot\textup{poly}(r,m)$.

Collecting all the requirements of $N$, this bound holds so long as
$N\geq\Omega\left(\left(\frac{rm}{\min\\{\alpha-\gamma,\beta-\gamma\\}}\right)^{2}\right)$,
which is equivalent to
$n\geq\Omega\left(\frac{rm}{\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}}\right)$.

∎

###### Proof of Proposition 2.

Notice that the roles of domain and class are the same in stochastic block
model. Let $\zeta>0$ and $\epsilon\in\left(0,\frac{1}{2}\right)$ be arbitrary
constants. If we train a domain classifier head on class 1 with regularization
strength $\eta\in\left(0,\frac{(\beta-\gamma)\epsilon}{2r\rho}\right]$, then
following the same proof of Theorem 4, we know that when
$n\geq\Omega\left(\frac{rm}{\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}}\right)$,
with probability at least $1-n^{-\zeta}$, we have that the global error of
this domain predictor is bounded by
$O\left(\frac{1}{\eta^{4}\cdot\min\\{\alpha-\gamma,\beta-\gamma\\}^{2}\cdot
n}\right)\cdot\textup{poly}(r,m)$. Setting $\epsilon=\frac{1}{4}$, $\zeta=1$
and $\eta=\frac{\beta-\gamma}{8r\rho}$ finishes the proof. ∎

###  A.2 Proof of Proposition 3

Figure 4: Example distribution of data and augmentations in which ERM and DANN
generalize more poorly than contrastive learning. ERM and DANN minimizers are
only guaranteed to correctly label inputs that are either in the source domain
or reachable from source inputs via data augmentation, while connectivity
throughout the target domain allows contrastive pre-training to generalize
even to target inputs that are multiple “hops” away from the source. The
orange dotted lines on the far left and far right connect to each other but
are illustrated as straight dotted lines for cleanliness.

#### Data distribution (Figure 4).

In the setting of binary classification with 2 domains, let
$\mathcal{S}=\\{x\in\mathcal{X}:d_{x}=1\\}$ and
$\mathcal{T}=\\{x\in\mathcal{T}:d_{x}=2\\}$ and assume that $P_{S}$ and
$P_{T}$ are uniform over $\mathcal{S}$ and $\mathcal{T}$, respectively. We
refer to each input by its ID, so that $\mathcal{X}=\\{1,\dots,8\\}$. The
source domain $\mathcal{S}=\\{1,2\\}$ contains 2 points while the target
domain $\mathcal{T}=\\{3,4,5,6,7,8\\}$ contains 6 points. The label space is
$\mathcal{Y}=\\{2,1\\}$. The label for $x\in\\{1,3,5,7\\}$ is $y_{x}=1$ and
the label for $x\in\\{2,4,6,8\\}$ is $y_{x}=2$. The marginal distribution over
unlabeled examples $P_{U}$ (used by contrastive pre-training in Equation 4) is
the uniform distribution over $\mathcal{X}$. Only the inputs in the source
domain $\mathcal{S}$ have labels for supervised learning.

#### Augmentation distribution.

The augmentation distribution $\mathcal{A}(\cdot\mid x)$ is

$\displaystyle\mathcal{A}({x^{\prime}}\mid
x)=\begin{cases}{\rho^{\prime}}&x={x^{\prime}}\\\
{\alpha^{\prime}}&y_{x^{\prime}}=y_{x},x\neq{x^{\prime}}\\\
{\beta^{\prime}}&\\{{x^{\prime}},x\\}\in\\{\\{1,2\\},\\{3,4\\},\\{5,6\\},\\{7,8\\}\\}\\\
{\gamma^{\prime}}&\\{{x^{\prime}},x\\}\in\\{\\{1,4\\},\\{2,3\\},\\{3,6\\},\\{4,5\\},\\{5,8\\},\\{6,7\\},\\{1,8\\},\\{2,7\\}\\}\\\
\end{cases}.$ (60)

By the edge structure of the graph, we have that
${\rho^{\prime}}+2{\alpha^{\prime}}+{\beta^{\prime}}+2{\gamma^{\prime}}=1$. We
assume that ${\rho^{\prime}},{\alpha^{\prime}},{\beta^{\prime}}$, and
${\gamma^{\prime}}$ are all distinct and obey the following inequalities:
${\rho^{\prime}}>\max\\{{\alpha^{\prime}},{\beta^{\prime}}\\}$ and
$\min\\{{\alpha^{\prime}},{\beta^{\prime}}\\}>{\gamma^{\prime}}$.

#### Distribution over positive pairs.

The augmentation distribution induces a distribution $S_{+}$ over positive
pairs, which is defined similarly:

$\displaystyle S_{+}({x^{\prime}},x)=\begin{cases}{\rho}/{C}&x={x^{\prime}}\\\
{\alpha}/{C}&y_{x^{\prime}}=y_{x},x\neq{x^{\prime}}\\\
{\beta}/{C}&\\{{x^{\prime}},x\\}\in\\{\\{1,2\\},\\{3,4\\},\\{5,6\\},\\{7,8\\}\\}\\\
{\gamma}/{C}&\\{{x^{\prime}},x\\}\in\\{\\{1,4\\},\\{2,3\\},\\{3,6\\},\\{4,5\\},\\{5,8\\},\\{6,7\\},\\{1,8\\},\\{2,7\\}\\}\end{cases}$
(61)

where the normalization is ${C}=8{\rho}+16{\alpha}+8{\beta}+16{\gamma}$. The
normalization ensures that the sum of $S_{+}({x^{\prime}},x)$ over all pairs
${x^{\prime}},x$ is 1. At the end of this section (paragraph A.2), we show how
to derive ${\rho},{\alpha},{\beta},{\gamma}$ as functions of
${\rho^{\prime}},{\alpha^{\prime}},{\beta^{\prime}},{\gamma^{\prime}}$,
respectively. We also show that the assumptions that
${\rho^{\prime}}>\max\\{{\alpha^{\prime}},{\beta^{\prime}}\\}$ and
$\min\\{{\alpha^{\prime}},{\beta^{\prime}}\\}>{\gamma^{\prime}}$ imply that
${\rho}>\max\\{{\alpha},{\beta}\\}$ and $\min\\{{\alpha},{\beta}\\}>{\gamma}$.

We recall Proposition 3:

See 3

We will consider $\ell$ to be the squared loss for all methods in this proof.

#### ERM.

We claim that a classifier $\widehat{f}_{\text{erm}}$ that makes the following
predictions is a minimizer of the ERM objective with data augmentation
(Equation 1):

$\displaystyle\operatorname*{arg\,max}_{i}(\widehat{f}_{\text{erm}}(x))_{i}=\begin{cases}1&\text{if}\quad
x\in\\{1,3,6,7\\}\\\ 2&\text{if}\quad x\in\\{2,4,5,8\\}.\end{cases}$ (62)

Since this classifier outputs the incorrect prediction on 2/6 of the target
points ($\\{5,6\\}$), it has a target 0-1 error of 1/3. It remains to show
that $\widehat{f}_{\text{erm}}$ is a minimizer of the ERM objective.

To see why, we first define the reachable set $\mathcal{R}=\\{1,2,3,4,7,8\\}$
as the inputs that are sampled with probability greater than 0 as
augmentations of the labeled source data, and rewrite Equation 1 as

$\displaystyle\mathcal{L}_{\text{ERM}}(f)$ $\displaystyle=\mathbb{E}_{x\sim
P_{S},{x^{\prime}}\sim\mathcal{A}(\cdot\mid
x)}[\|f({x^{\prime}})-e_{y_{x}}\|^{2}]$ (63)
$\displaystyle=\sum_{x\in\\{1,2\\}}P_{S}(x)\sum_{{x^{\prime}}\in\mathcal{X}}\mathcal{A}({x^{\prime}}\mid
x)[(f({x^{\prime}})-e_{y_{x}})^{2}]$ (64)
$\displaystyle=\sum_{x\in\\{1,2\\}}P_{S}(x)\sum_{{x^{\prime}}\in\mathcal{R}}\mathcal{A}({x^{\prime}}\mid
x)[(f({x^{\prime}})-e_{y_{x}})^{2}]$ (65)

where $e_{y_{x}}\in\mathbb{R}^{r}$ is a one-hot vector for the label. In the
last step, we replace the sum over the entire input space $\mathcal{X}$ with
the reachable set $\mathcal{R}$ since $\mathcal{A}({x^{\prime}}\mid x)=0$ when
${x^{\prime}}$ is not in the reachable set. Since $x\in\\{5,6\\}$ are not
included in this sum, the prediction of $f$ on $\\{5,6\\}$ can be arbitrary
(and wrong). This shows that there exists a minimizer of the ERM objective
with 0-1 error at least 1/3, since the minimizer can classify 2/6 target
inputs incorrectly.

However, all minimizers of ERM output the correct prediction for the other
inputs. From above, we have

$\displaystyle\mathcal{L}_{\text{ERM}}(f)$
$\displaystyle=P_{S}(x=1)\left(\sum_{x^{\prime}\in\mathcal{R}}\mathcal{A}(x^{\prime}\mid
x=1)\|f(x^{\prime})-e_{1}\|^{2}\right)+P_{S}(x=2)\left(\sum_{x^{\prime}\in\mathcal{R}}\mathcal{A}(x^{\prime}\mid
x=2)\|f(x^{\prime})-e_{2}\|^{2}\right)$ (66)
$\displaystyle=\frac{1}{2}\sum_{x^{\prime}\in\mathcal{R}}\mathcal{A}(x^{\prime}\mid
x=1)\cdot\|f(x^{\prime})-e_{1}\|^{2}+\mathcal{A}(x^{\prime}\mid
x=2)\cdot\|f(x^{\prime})-e_{2}\|^{2}$ (67)

since $P_{S}(x=1)=P_{S}(x=2)=1/2$. For each ${x^{\prime}}\in\mathcal{R}$, the
minimizer of this objective outputs

$\displaystyle\frac{\mathcal{A}(x^{\prime}\mid
x=1)e_{1}+\mathcal{A}(x^{\prime}\mid x=2)e_{2}}{\mathcal{A}(x^{\prime}\mid
x=1)+\mathcal{A}(x^{\prime}\mid x=2)}.$ (68)

The argmax is $1$ if $\mathcal{A}({x^{\prime}}\mid
x=1)>\mathcal{A}({x^{\prime}}\mid x=2)$. For ${x^{\prime}}=1$, we have that
$\mathcal{A}({x^{\prime}}\mid x=1)={\rho^{\prime}}$, which by assumption is
larger than $\mathcal{A}({x^{\prime}}\mid x=2)={\beta^{\prime}}$. For
${x^{\prime}}\in\\{3,7\\}$, we have that $\mathcal{A}({x^{\prime}}\mid
x=1)={\alpha^{\prime}}$, which by assumption is larger than
$\mathcal{A}({x^{\prime}}\mid x=2)={\gamma^{\prime}}$. Therefore any minimizer
of the ERM objective will output a vector with argmax $1$ for
$x\in\\{1,3,7\\}$. By symmetry, any minimizer of the ERM objective will output
a vector with argmax $2$ for $x\in\\{2,4,8\\}$. Thus any minimizer of the ERM
objective will correctly classify these 6 inputs (including 4/6 of the target
inputs). This shows that $\widehat{f}_{\text{erm}}$ is a minimizer of the ERM
objective and has target 0-1 error 1/3.

#### DANN.

Let $z_{1},z_{2}\in\mathbb{R}^{k}$ be distinct points in the representation
space such that $z_{1}\neq z_{2}$. We claim that the following encoder
$\widehat{\phi}_{\text{dann}}$ and classification head
$\widehat{h}_{\text{dann}}$ (with the following constraint) minimize the DANN
objective (Equation 2):

$\displaystyle\widehat{\phi}_{\text{dann}}(x)=\begin{cases}z_{1}&\text{if}\quad
x\in\\{1,3,6,7\\}\\\ z_{2}&\text{if}\quad
x\in\\{2,4,5,8\\}\end{cases}\qquad\text{and}\qquad\operatorname*{arg\,max}_{i}{\widehat{h}_{\text{dann}}(z)_{i}}=\begin{cases}1&\text{if}\quad
z=z_{1}\\\ 2&\text{if}\quad z=z_{2}\end{cases}.$ (69)

The first term in the DANN objective is equivalent to the ERM objective, and
the classifier
$\widehat{f}_{\text{dann}}:\widehat{h}_{\text{dann}}\circ\widehat{\phi}_{\text{dann}}$
outputs the same predictions as the ERM minimizer $\widehat{f}_{\text{erm}}$.
Therefore, $\widehat{f}_{\text{dann}}$ minimizes the first term of Equation 2
by the same argument from the ERM section, and also gets a target 0-1 error of
1/3.

It remains to show that $\widehat{\phi}_{\text{dann}}$ is an optimal solution
for the second term of Equation 2,

$\displaystyle\lambda\max_{\phi}\min_{{h}_{\text{dom}}}\mathbb{E}_{x\sim{P_{U}},{x^{\prime}}\sim\mathcal{A}(\cdot\mid
x)}[\|{h}_{\text{dom}}(\phi({x^{\prime}}))-e_{d_{x}}\|^{2}].$ (70)

We write this as a maximization for simplicity, while the DANN objective is a
minimization over the negation.

First, we show that this max-min loss is upper bounded by
$\frac{3\lambda}{8}$. For any encoder $\phi$, we could choose
${h}_{\text{dom}}$ such that it always outputs the vector
$\frac{1}{4}e_{1}+\frac{3}{4}e_{2}$ for all input representations. Since $1/4$
of the inputs sampled from $P_{U}$ are from the source domain, on these inputs
the domain classifier would have squared loss

$\displaystyle\frac{\lambda}{4}\|\frac{3}{4}(e_{2}-e_{1})\|^{2}=\frac{9\lambda}{32}.$
(71)

For inputs originally from the target domain, the domain classifier incurs
squared loss

$\displaystyle\frac{3\lambda}{4}\|\frac{1}{4}(e_{1}=e_{2})\|^{2}=\frac{3\lambda}{32}.$
(72)

In total, the squared loss is $\frac{3\lambda}{8}$. This is an upper bound
since any encoder will incur at most this loss.

Second, we show that the proposed $\widehat{\phi}_{\text{dann}}$ attains the
upper bound. Fixing the encoder to be $\widehat{\phi}_{\text{dann}}$, we
compute the objective and maximize over the domain classification head
${h}_{\text{dom}}$:

$\displaystyle\lambda\min_{{h}_{\text{dom}}}\mathbb{E}_{x\sim{P_{U}},{x^{\prime}}\sim\mathcal{A}(\cdot\mid
x)}$
$\displaystyle[\|{h}_{\text{dom}}(\widehat{\phi}_{\text{dann}}({x^{\prime}}))-e_{d_{x}}\|^{2}]$
(73)
$\displaystyle=\lambda\min_{{h}_{\text{dom}}}\sum_{x\in\mathcal{X}}P_{U}(x)\sum_{{x^{\prime}}\in\mathcal{X}}\mathcal{A}({x^{\prime}}\mid
x)\|{h}_{\text{dom}}(\widehat{\phi}_{\text{dann}}({x^{\prime}}))-e_{d_{x}}\|^{2}$
(74)
$\displaystyle=\min_{{h}_{\text{dom}}}\frac{\lambda}{8}\sum_{x\in\mathcal{X}}\sum_{{x^{\prime}}\in\mathcal{X}}\mathcal{A}({x^{\prime}}\mid
x)\|{h}_{\text{dom}}(\widehat{\phi}_{\text{dann}}({x^{\prime}}))-e_{d_{x}}\|^{2}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ (\text{since }P_{U}(x)=\frac{1}{8}).$ (75)

We can further break this down into a sum of 4 terms, which simplify the loss
terms:

$\begin{split}\min_{{h}_{\text{dom}}}&\frac{\lambda}{8}\sum_{x\in
S}\sum_{x\in\\{1,3,6,7\\}}\mathcal{A}({x^{\prime}}\mid
x)\|{h}_{\text{dom}}(z_{1})-e_{1}\|^{2}\\\ +&\frac{\lambda}{8}\sum_{x\in
S}\sum_{x\in\\{2,4,5,8\\}}\mathcal{A}({x^{\prime}}\mid
x)\|{h}_{\text{dom}}(z_{2})-e_{1}\|^{2}\\\ +&\frac{\lambda}{8}\sum_{x\in
T}\sum_{x\in\\{1,3,6,7\\}}\mathcal{A}({x^{\prime}}\mid
x)\|{h}_{\text{dom}}(z_{1})-e_{2}\|^{2}\\\ +&\frac{\lambda}{8}\sum_{x\in
T}\sum_{x\in\\{2,4,5,8\\}}\mathcal{A}({x^{\prime}}\mid
x)\|{h}_{\text{dom}}(z_{2})-e_{2}\|^{2}.\end{split}$ (76)

Using the augmentation graph and the fact that
${\rho^{\prime}}+2{\alpha^{\prime}}+{\beta^{\prime}}+2{\gamma^{\prime}}=1$, we
can calculate the sum of the augmentation probabilities for each term,
resulting in the objective

$\begin{split}\min_{{h}_{\text{dom}}}&\frac{\lambda}{8}\|{h}_{\text{dom}}(z_{1})-e_{1}\|^{2}\\\
+&\frac{\lambda}{8}\|{h}_{\text{dom}}(z_{2})-e_{1}\|^{2}\\\
+&\frac{3\lambda}{8}\|{h}_{\text{dom}}(z_{1})-e_{2}\|^{2}\\\
+&\frac{3\lambda}{8}\|{h}_{\text{dom}}(z_{2})-e_{2}\|^{2}.\end{split}$ (77)

The minimizer of this objective (taking the gradient and setting to 0) always
outputs

$\displaystyle{h}_{\text{dom}}(z_{1})={h}_{\text{dom}}(z_{2})=\frac{1}{4}e_{1}+\frac{3}{4}e_{2}$
(78)

for any input representation. This attains the error $\frac{3\lambda}{8}$,
showing that $\widehat{\phi}_{\text{dann}}$ is optimal for the second term of
the DANN loss. Therefore, the proposed $\widehat{\phi}_{\text{dann}}$ and
$\widehat{h}_{\text{dann}}$ minimize the DANN objective and get a target 0-1
error of 1/3.

#### Contrastive pre-training.

We show that contrastive pre-training achieves 0 target error on this example
as long as ${\alpha}>{\gamma}+{\beta}$. Examining Figure 4, ${\alpha}$
intuitively corresponds to the probability that an image $x$ augments to a
different image $x^{\prime}$ of the same class, while ${\gamma}$ and ${\beta}$
correspond to the probability that $x$ augments to $x^{\prime}$ of a different
class. Roughly speaking, the condition ${\alpha}>{\gamma}+{\beta}$ means that
augmentations should preserve the class more often than not.

We prove that contrastive pre-training achieves 0 target error by first
deriving the representations learned by contrastive learning on unlabeled data
$P_{U}$ (Equation 6), and then deriving the linear probe learned by optimizing
the squared loss on source examples $\mathcal{S}$ (Equation 7) and examining
its accuracy on target examples $\mathcal{T}$.

Step 1 (Pretraining): During the pre-training phase, we use inputs sampled
from $P_{U}$ to learn an encoder $\widehat{\phi}$ which minimizes the spectral
contrastive loss (Equation 6). We define the embedding matrix
$\widehat{F}\in\mathbb{R}^{8\times k}$ as follows: the $i$-th row of
$\widehat{F}$ is the feature vector for example $i$—that is,
$\widehat{F}_{i}=\widehat{\phi}(i)$ where $\widehat{F}_{i}\in\mathbb{R}^{k}$
denotes the $i$-th row of $\widehat{F}$.

In this step of the proof we will compute $\widehat{F}$ analytically.
$\widehat{F}$ is given by the top $k$ eigenvectors and eigenvalues of the
adjacency matrix $A$, following the analysis in HaoChen et al. (2021). We
begin by computing these eigenvectors and eigenvalues.

Let $A$ be the adjacency matrix, where $A_{ij}=S_{+}(i,j)$ is the probability
of sampling a positive pair $(i,j)$. Writing $A$ out explicitly,

$A=\frac{1}{{C}}\begin{bmatrix}[r]{\rho}&{\beta}&{\alpha}&{\gamma}&0&0&{\alpha}&{\gamma}\\\
{\beta}&{\rho}&{\gamma}&{\alpha}&0&0&{\gamma}&{\alpha}\\\
{\alpha}&{\gamma}&{\rho}&{\beta}&{\alpha}&{\gamma}&0&0\\\
{\gamma}&{\alpha}&{\beta}&{\rho}&{\gamma}&{\alpha}&0&0\\\
0&0&{\alpha}&{\gamma}&{\rho}&{\beta}&{\alpha}&{\gamma}\\\
0&0&{\gamma}&{\alpha}&{\beta}&{\rho}&{\gamma}&{\alpha}\\\
{\alpha}&{\gamma}&0&0&{\alpha}&{\gamma}&{\rho}&{\beta}\\\
{\gamma}&{\alpha}&0&0&{\gamma}&{\alpha}&{\beta}&{\rho}\\\ \end{bmatrix}$ (79)

for normalization constant ${C}=8{\rho}+16{\alpha}+8{\beta}+16{\gamma}$.

Let $\lambda^{\prime}\in\mathbb{R}^{8}$ be the eigenvalues of $A$, and
$U\in\mathbb{R}^{8\times 8}$ be a matrix where the columns are corresponding
unit-norm eigenvectors of $A$. We can explicitly write out these eigenvectors
and eigenvalues as follows:

$U=\begin{bmatrix}[r]1&1&0&-1&0&1&-1&-1\\\ 1&-1&0&-1&0&-1&-1&1\\\
1&0&1&0&-1&-1&1&-1\\\ 1&0&-1&0&-1&1&1&1\\\ 1&-1&0&1&0&1&-1&-1\\\
1&1&0&1&0&-1&-1&1\\\ 1&0&-1&0&1&-1&1&-1\\\ 1&0&1&0&1&1&1&1\end{bmatrix}\cdot
D,$ (80)

where each column of $U$ is an eigenvector of $A$, and $D$ is a diagonal
matrix that normalizes the eigenvectors to unit norm, given by:

$D=\mbox{diag}\left(\left[\frac{1}{\sqrt{8}},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{\sqrt{8}},\frac{1}{\sqrt{8}},\frac{1}{\sqrt{8}}\right]\right).$
(81)

The corresponding eigenvalues are given by
$\lambda^{\prime}\in\mathbb{R}^{8}$, where $\lambda^{\prime}_{i}$ is the
eigenvalue corresponding to the $i$-th column of $U$. For convenience, let
$\lambda=C\lambda^{\prime}$ to avoid re-writing the $C$ term, and we have:

$\displaystyle\lambda_{1}$ $\displaystyle={\rho}+2{\alpha}+{\beta}+2{\gamma}$
$\displaystyle\lambda_{2}$ $\displaystyle=\lambda_{3}=-{\beta}+{\rho}$
$\displaystyle\lambda_{4}$ $\displaystyle=\lambda_{5}={\beta}+{\rho}$
$\displaystyle\lambda_{6}$ $\displaystyle=-2{\alpha}-{\beta}+2{\gamma}+{\rho}$
$\displaystyle\lambda_{7}$ $\displaystyle=-2{\alpha}+{\beta}-2{\gamma}+{\rho}$
$\displaystyle\lambda_{8}$ $\displaystyle=2{\alpha}-{\beta}-2{\gamma}+{\rho}.$

We choose $k=3$ for the representation dimension of contrastive learning,
following Theorem 1. We now show that the top $3$ eigenvalues includes
$\lambda_{1}$ and $\lambda_{8}$ and does not include $\lambda_{2}$ and
$\lambda_{6}$.

Since ${\rho},{\alpha},{\beta},{\gamma}>0$, from basic algebra:

$\lambda_{1}>\lambda_{4}=\lambda_{5}>\lambda_{2}=\lambda_{3}.$ (82)

Since ${\alpha}>{\gamma}+{\beta}$ and ${\beta}>0$, we also have
${\alpha}>{\gamma}$, which means:

$\lambda_{3}>\lambda_{6}.$ (83)

Using these facts, we also get:

$\lambda_{1}>\lambda_{8}>\lambda_{2}=\lambda_{3}.$ (84)

We assumed that ${\alpha}>{\gamma}+{\beta}$, which gives us:

$\lambda_{8}>\lambda_{4}=\lambda_{5}.$ (85)

Finally, we note that $\lambda_{1}>\lambda_{8}$ and $\lambda_{1}>\lambda_{7}$
because ${\rho},{\alpha},{\beta},{\gamma}>0$.

Collating all these inequalities, we find that $\lambda_{1}$ is the largest
eigenvalue, and that $\lambda_{8}$ is larger than
$\lambda_{2},\lambda_{3},\lambda_{4},\lambda_{5},\lambda_{6}$ (all eigenvalues
except possibly $\lambda_{7}$, which can be larger or smaller than
$\lambda_{8}$). This shows that the top $3$ eigenvalues includes $\lambda_{1}$
and $\lambda_{8}$. Since $\lambda_{2}$ is smaller than
$\lambda_{1},\lambda_{8},\lambda_{4},\lambda_{5}$ and $\lambda_{6}$ is even
smaller than $\lambda_{2}$, we also get that $\lambda_{2},\lambda_{6}$ (and
$\lambda_{3}$) are not among the top 3 eigenvalues.

We now write out the embedding matrix $\widehat{F}$ in terms of the top 3
eigenvectors and eigenvalues. From above, we know that the top 3 eigenvalues
are $\lambda_{a},\lambda_{1},\lambda_{8}$, where $a\neq 2$ and $a\neq 6$. Let
$u_{a},u_{1},u_{8}$ be the corresponding eigenvectors: the $a$-th, $1$-st, and
$8$-th column of $U$ respectively. From HaoChen et al. (2021) (specifically,
Lemma 3.2 and then using Eckart–Young–Mirsky theorem), for some orthonormal
(rotation) matrix $R\in\mathbb{R}^{k\times k}$, we have:

$\widehat{F}=\big{[}\sqrt{\lambda^{\prime}_{8}}u_{8};\sqrt{\lambda^{\prime}_{1}}u_{1};\sqrt{\lambda^{\prime}_{a}}u_{a}]R=\frac{1}{\sqrt{C}}\big{[}\sqrt{\lambda_{8}}u_{8};\sqrt{\lambda_{1}}u_{1};\sqrt{\lambda_{a}}u_{a}]R.$
(86)

Let $\tau_{8}=\sqrt{\lambda^{\prime}_{8}}\cdot
D_{88}=\sqrt{\lambda^{\prime}_{8}}/\sqrt{8}$,
$\tau_{1}=\sqrt{\lambda^{\prime}_{1}}\cdot
D_{11}=\sqrt{\lambda^{\prime}_{1}}/\sqrt{8}$, and
$\tau_{a}=\sqrt{\lambda^{\prime}_{a}}\cdot D_{aa}$. We can then write
$\widehat{F}$ as follows, where $\tau_{8},\tau_{1},\tau_{a}>0$. Focus on the
values in the first column since this will be especially important in step 2
of the proof:

$\widehat{F}=\begin{bmatrix}[r]-\tau_{8}&\tau_{1}&\tau_{a}U_{1a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{2a}\\\ -\tau_{8}&\tau_{1}&\tau_{a}U_{3a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{4a}\\\ -\tau_{8}&\tau_{1}&\tau_{a}U_{5a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{6a}\\\ -\tau_{8}&\tau_{1}&\tau_{a}U_{7a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{8a}\\\ \end{bmatrix}R.$ (87)

Next, we show that $U_{1a}=U_{2a}$. To see this, recall that
$a\not\in\\{1,2,6,8\\}$. Inspecting $U$ above in Equation 80, we see that for
all other possible choices of $a$ (so $a\in\\{3,4,5,7\\}$), $U_{1a}=U_{2a}$.

Therefore, we can write $\widehat{F}$ as (we have only changed the third
column on the second row, notice now that the first two rows only differ on
the first coordinate):

$\widehat{F}=\begin{bmatrix}[r]-\tau_{8}&\tau_{1}&\tau_{a}U_{1a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{1a}\\\ -\tau_{8}&\tau_{1}&\tau_{a}U_{3a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{4a}\\\ -\tau_{8}&\tau_{1}&\tau_{a}U_{5a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{6a}\\\ -\tau_{8}&\tau_{1}&\tau_{a}U_{7a}\\\
\tau_{8}&\tau_{1}&\tau_{a}U_{8a}\\\ \end{bmatrix}R.$ (88)

Step 2 (Linear probing): We consider the target error of a classification head
$\widehat{h}$ composed with the encoder $\widehat{\phi}$ learned by
contrastive pre-training. The classification head minimizes the following
objective (originally defined in Equation 7):

$\displaystyle\mathcal{L}(B)=\mathbb{E}_{x\sim
P_{S}}\left[\|\widehat{\phi}(x)^{\top}B-y_{x}\|_{2}^{2}\right]+\eta\|B\|_{2}^{2}$
(89)

where $B\in\mathbb{R}^{k}$, the regularization is nonzero ($\eta>0$), and
predictions are made by $\text{sign}(\widehat{\phi}(x)^{\top}B)$. The pre-
trained encoder $\widehat{\phi}$ is fixed and obtained from step 1 above, and
so the minimization is over $B$. In our case we only have two source labeled
points, so the objective is minimized over these two labeled source points
$x\in\\{1,2\\}$. Since the objective is rotationally symmetric, without loss
of generality we can omit the rotation matrix $R$ in the pretrained
representation above in Equation 88. We consider the minimizer $\widehat{B}$
of the fine-tuning objective $\mathcal{L}$. Since the regularization strength
$\eta$ is strictly greater than 0, the $j$-th coordinate of the minimizer
$\widehat{B}_{j}$ is 0 when the features for the labeled data $x\in\\{1,2\\}$
are identical on the $j$-th coordinate:
$\widehat{\phi}(1)_{j}=\widehat{\phi}(2)_{j}$.

Note that $y_{1}=1$ and $y_{2}=-1$, and $\widehat{\phi}(1)$ and
$\widehat{\phi}(2)$ are given above in Equation 88. Solving the optimization
problem in Equation 89 analytically (e.g., by taking derivatives setting to
$0$), we get for some $\omega>0$:

$\widehat{B}=[-\omega,0,0].$ (90)

Finally we show that this classifier (composed with the features learned in
the previous step) predicts every target example correctly. Inspecting the
feature matrix in Equation 88, we have for $x\in\\{1,3,5,7\\}$:

$\widehat{B}^{\top}\widehat{\phi}(x)=\tau\omega>0\mbox{ and }y_{x}=1,$ (91)

and for $x\in\\{2,4,6,8\\}$,

$\widehat{B}^{\top}\widehat{\phi}(x)=-\tau\omega<0\mbox{ and }y_{x}=-1.$ (92)

In other words, $\text{sign}(\widehat{\phi}(x)^{\top}\widehat{B})=y_{x}$ for
all $x$, and so the target error is 0, as desired.

#### Conversion from augmentation to positive pair distribution.

Above, we worked out the proof for contrastive pre-training in terms of the
positive pair distribution $S_{+}({x^{\prime}},x)$. We showed that if
${\alpha}>{\gamma}+{\beta}$ then contrastive pre-training achieves $0$ target
error. We still need to show that such a setting exists—we started out by
defining the augmentation probabilities, and we show that there is indeed some
setting of
${\rho^{\prime}},{\alpha^{\prime}},{\gamma^{\prime}},{\beta^{\prime}}$ such
that the condition ${\alpha}>{\gamma}+{\beta}$ holds.

Recall that the positive pair distribution is defined as

$\displaystyle S_{+}({x^{\prime}},x)=\mathbb{E}_{\bar{x}\sim
P_{U}}[\mathcal{A}(x\mid\bar{x})\mathcal{A}({x^{\prime}}\mid\bar{x})].$ (93)

The distribution $S_{+}$ induced by $\mathcal{A}$ on $\mathcal{X}$ is

$\displaystyle
S_{+}({x^{\prime}},x)=\begin{cases}{\rho}=\frac{1}{8C}[{\rho^{\prime}}^{2}+2{\alpha^{\prime}}^{2}+{\beta^{\prime}}^{2}+2{\gamma^{\prime}}^{2}]&x={x^{\prime}}\\\
{\alpha}=\frac{1}{4C}[{\rho^{\prime}}{\alpha^{\prime}}+{\beta^{\prime}}{\gamma^{\prime}}]&y_{x}=y_{x^{\prime}},x\neq{x^{\prime}}\\\
{\beta}=\frac{1}{4C}[{\rho^{\prime}}{\beta^{\prime}}+2{\alpha^{\prime}}{\gamma^{\prime}}]&\left\\{{x^{\prime}},x\right\\}\in\left\\{\left\\{1,2\right\\},\left\\{3,4\right\\},\left\\{5,6\right\\},\left\\{7,8\right\\}\right\\}\\\
{\gamma}=\frac{1}{4C}[{\rho^{\prime}}{\gamma^{\prime}}+{\alpha^{\prime}}{\beta^{\prime}}]&\left\\{{x^{\prime}},x\right\\}\in\left\\{\left\\{1,4\right\\},\left\\{2,3\right\\},\left\\{3,6\right\\},\left\\{4,5\right\\},\left\\{5,8\right\\},\left\\{6,7\right\\},\left\\{1,8\right\\},\left\\{2,7\right\\}\right\\}\end{cases}$
(94)

where the constant $C$ ensures that the probabilities sum to 1.

By setting
${\gamma^{\prime}}=0,{\beta^{\prime}}=0,{\alpha^{\prime}}>0,{\rho^{\prime}}>0$
such that $2{\alpha^{\prime}}+{\rho^{\prime}}=1$, we get the desired condition
${\alpha}>{\gamma}+{\beta}$. This shows that there exists one such scenario,
where the condition holds, as desired. However, we note that there are many
situations where the condition ${\alpha}>{\gamma}+{\beta}$ holds.

##  Appendix B Additional Details for Section 5

###  B.1 Additional Experiments

#### Table 4.

Table 4 contains target test accuracies on all individual pairs of DomainNet
domains (Table 2 contains only the average) with all baselines and SwAV, in
addition to MoCo-V2 and MoCo-V3 (additional contrastive pre-training methods).
The MoCo-V2 and MoCo-V3 hyperparameters were tuned on ImageNet in their
original papers, and we did not tune either method further; therefore, for
MoCo-V2 the target test accuracies are lower than several of the baselines on
DomainNet (which is very different from ImageNet). However, MoCo-V3
outperforms all methods except for SwAV and DANN+strong-augs (41.59% vs. the
next best, DANN: 38.38%).

#### Tables 5 and 6.

Tables 5 and 6 contain target test accuracies on DomainNet and BREEDS of
baselines with early stopping. The top halves of both tables contain results
of early stopping with source test accuracy (i.e., selecting the epoch to use
based on the highest source test accuracy achieved over all epochs), and the
bottom halves contain results of early stopping with target test accuracy
(i.e., the highest target test accuracy achieved over all epochs; this should
be interpreted as an “oracle” method). As expected, early stopping improves
over simply using the final iterate (as in Tables 2 and 4). However, even with
early stopping only DANN+strong-augs outperforms SwAV (which uses no early
stopping)—by 1.3% and 3.2% for early stopping with source and target accuracy,
respectively.

#### Tables 7 and 8.

Tables 7 and 8 contain target test accuracy when we standardize the compute
requirements as much as possible between the baselines and pre-training
methods, since our primary experiments allow the baselines to run for nearly
twice as many epochs as the pre-training methods. Specifically, here we
enforce that all methods are run for 1) the same the number of epochs with
unlabeled data and 2) the same the number of epochs with unlabeled data. In
particular, the baselines are initialized from an ERM baseline trained for 100
to 150 epochs, rather than 500 to 550. As a result, the resulting target
accuracies are significantly lower for SENTRY and SENTRY+strong-augs (SENTRY
was developed using ImageNet-pre-trained models and requires a decently
accurate initialization); however, the accuracy for DANN and DANN+strong-augs
is less substantial.

#### Table 9.

To verify that other contrastive learning methods are also competitive as UDA
methods, Table 9 contains target test accuracies on BREEDS of SwAV (with
source-only and target-only splits of the pre-training data), MoCo-V3 (with
source and target pre-training), and Dino and Barlow Twins (both with ImageNet
pre-trained weights downloaded from official Github repositories). Target
accuracy increases from SwAV (S) to SwAV (T) to SwAV (S+T), and the accuracies
of SwAV (S+T) and MoCo (S+T) are comparable (within 1% of each other for both
Living-17 and Entity-30). Dino+ and Barlow Twins+ are both higher (up to 3%)
than SwAV+ on Living-17 and slightly lower (1.4%) on Entity-30.

###  B.2 Datasets

#### BREEDS.

BREEDS is a subpopulation shift benchmark derived from ImageNet by
constructing a hierarchical tree structure of classes from WordNet. Nodes at a
specified depth of the tree become the labels for the classification task, and
descendant nodes are treated as subpopulations that can be randomly
partitioned into source and target domains.

We use the dataset creation functions defined in the `robustness` Python
library to generate the Living-17 and Entity-30 tasks from the original
ImageNet dataset (Engstrom et al., 2019; Russakovsky et al., 2015). The
Living-17 dataset is an animal classification task which consists of nodes in
the subtree rooted at the “living thing” node in the WordNet hierarchy. An
example of a label is “ape” with subpopulations of gibbons, orangutans,
gorillas, and chimpanzees. The Entity-30 dataset is a much more general task,
incorporating nodes in the “entity” subtree. Labels include “building” and
“home appliance”. The trailing number in the dataset name is the total number
of classes in that dataset.

#### DomainNet.

DomainNet is a large unsupervised domain adaptation task, consisting of
approximately 600,000 images and 345 classes in 6 domains. Each image belongs
to one of 6 domains, including sketches, clipart, and photographs. For our
experiments we utilize the same filtered version of DomainNet from Prabhu et
al. (2021), which uses 40 of the 345 classes and the sketch, painting,
photograph, and clipart domains. This refinement is done to eliminate much of
the noise present in the original DomainNet dataset (Tan et al., 2020).

For our baseline experiments with the SENTRY algorithm (Prabhu et al., 2021),
we use the authors’ official repository
(https://github.com/virajprabhu/SENTRY), which filters the original DomainNet
dataset automatically as described above.

#### STL$\to$CIFAR.

CIFAR10 consists of $32\times 32$ images from the former TinyImages dataset,
and STL10 is derived from ImageNet and contains images with resolution
$96\times 96$. Both are classical image recognition datasets and are often
paired together for domain shift tasks (Shu et al., 2018; French et al.,
2018). We resize the STL-10 images to $32\times 32$ to match the resolution of
CIFAR10, as done in French et al. (2018). The two non-overlapping classes
(“monkey” in CIFAR-10 and “frog” in STL10) are removed from both datasets
before training, making the task a 9-class classification problem.

###  B.3 Algorithms and Hyperparameter Tuning

For joint-training baselines, we use the final iterate and we select
hyperparameters based on target test accuracy (i.e., OOD accuracy).

#### ERM.

  * •

DomainNet. The SENTRY algorithm runs ERM with class balancing (starting with
ImageNet-pre-trained initialization) prior to beginning entropy minimization,
and therefore the SENTRY repository contains an ERM implementation and
hyperparameters for DomainNet. Therefore, using that ERM implementation we run
ERM for 550 epochs and multiply the initial learning rate by 10x, keeping all
other hyperparameters from (Prabhu et al., 2021) constant.

  * •

BREEDS. We use almost the same hyperparameters as Santurkar et al. (2020).
However, on Entity30, we train for 500 epochs and divide the learning rate by
10 every 500/3 = 167 epochs. On Living17, we train for 500 epochs and divide
the learning rate by 10 every 167 epochs. For both datasets we use a learning
rate of 0.1, a weight decay of $10^{-4}$, and a batch size of 128.

  * •

STL $\to$ CIFAR. The STL10 training set is much smaller than those of
DomainNet and BREEDS, which gives us more freedom to sweep over
hyperparameters. In turn, we vary the number of training epochs amongst
$\\{100,150,200,250,300\\}$, the learning rate amongst
$\\{0.0001,0.001,0.01,0.1\\}$, the softmax temperature amongst
$\\{0.5,0.75,1.0\\}$, and the weight decay parameter amongst
$\\{0.0005,0.005,0.05,0.5\\}$. We train the ERM model for 1000 epochs.

#### SENTRY.

We use the official implementation (https://github.com/virajprabhu/SENTRY).

  * •

DomainNet. For each pair of domains, we conduct a hyperparameter search
through $\lambda_{\text{src}}\in\\{0.5,1.0,1.5\\}$ (the weight on the
supervised classification loss) and learning rates $\in\\{0.01,0.001\\}$. We
run all hyperparameter settings for 100 epochs from a 150-epoch ERM checkpoint
and select the best one (based on target test accuracy). We then initialize
the SENTRY model with the ERM model described earlier (i.e., trained for 550
epochs) and run SENTRY for 400 epochs (for a total of 950 epochs).

  * •

BREEDS. We keep the default hyperparameters from the SENTRY repo but search
over 3 learning rates $\\{0.001,0.01,0.1\\}$ for 100 epochs and then run the
best hyperparameter setting for 300 additional epochs for 400 total epochs. We
initialize the model with the ERM model described earlier (i.e., trained for
500 epochs).

  * •

STL $\to$ CIFAR. We initialize SENTRY with an ERM model trained for 100 epochs
and then train SENTRY for 1000 epochs, varying the learning rate between
$\\{0.001,0.01,0.1\\}$, the weight decay between
$\\{0.0005,0.005,0.05,0.5\\}$, and the unsupervised loss weight between
$\\{0.01,0.1,1.0\\}$.

For the “strong augmentation” version of SENTRY, we replace the RandAug
algorithm used for consistency regularization with the augmentations used for
SwAV (in DomainNet and BREEDS) or SimCLR (for STL / CIFAR).

#### DANN.

We use the implementation provided in the SENTRY repository
(https://github.com/virajprabhu/SENTRY).

  * •

DomainNet. For each pair of domains, we conduct a hyperparameter search
through learning rates $\in\\{0.01,0.001\\}$ and temperature
$\in\\{0.9,1.0\\}$. As with SENTRY, we run all hyperparameter setting for 100
epochs from a 150-epoch ERM checkpoint, select the best one (based on target
test accuracy). We initialize the DANN model with the ERM model described
earlier (i.e., trained for 550 epochs) and run DANN for 400 epochs (for a
total of 950 epochs).

  * •

BREEDS. We sweep over two learning rates of 0.001 and 0.0005 for 100 epochs
and choose the learning rate that achieves the highest OOD accuracy. We then
run DANN for 300 additional epochs for 400 total epochs. We initialize the
SENTRY model with the ERM model described earlier.

  * •

STL $\to$ CIFAR. We follow an identical procedure to that of SENTRY,
initializing DANN with an ERM model trained for 100 epochs and sweeping over
the same hyperparameter set. DANN was run for 1000 epochs.

For the “strong augmentation” version of DANN we simply replace the input
augmentations with the augmentations used by SwAV (for DomainNet and BREEDS)
or SimCLR (for STL / CIFAR) and initialize DANN from an ERM checkpoint trained
with SwAV augmentations.

#### DIRT-T.

DIRT-T (Shu et al., 2018) is a domain adaptation method that addresses two
flaws of domain adversarial neural networks (Ganin et al., 2016): 1)
distribution matching is a weak constraint, and 2) in some domain adaptation
settings there does not exist a good joint classifier on both source and
target. The authors address the first shortcoming by adding a conditional
entropy regularization term so that the model’s decision boundaries do not
overlap high-density regions of data. This is inspired by the cluster
assumption, which states that the input space is divided into well-separated
clusters, one for each class in the label space. The lack of a good classifier
on both source and target is then addressed via self-training on the unlabeled
target data. We report the STL$\to$CIFAR DIRT-T results from Shu et al.
(2018).

###  B.4 SwAV

We use the official SwAV implementation
(https://github.com/facebookresearch/swav) and keep almost all of the
hyperparameters provided by the original paper for 400 epoch, 256-batch-size
training on ImageNet. However, we use a batch size of 512 and tuned SwAV
slightly on Living-17 using only the training curves (no labels) and following
the advice from the Github README and issues answered by the original authors:

  * •

In order to stabilize training, we do not use a queue on DomainNet and the
subsampled variants of Living-17. For pre-training on the full Living-17 and
Entity-30 datasets, we introduce the queue at epoch 60.

  * •