# Cycle Self-Training for Domain Adaptation

Hong Liu
Dept of Electronic Engineering
Tsinghua University
<EMAIL_ADDRESS>&Jianmin Wang
School of Software, BNRist
Tsinghua University
<EMAIL_ADDRESS>&Mingsheng Long
School of Software, BNRist
Tsinghua University
<EMAIL_ADDRESS>Corresponding author: Mingsheng Long
<EMAIL_ADDRESS>
###### Abstract

Mainstream approaches for unsupervised domain adaptation (UDA) learn domain-
invariant representations to narrow the domain shift, which are empirically
effective but theoretically challenged by the hardness or impossibility
theorems. Recently, self-training has been gaining momentum in UDA, which
exploits unlabeled target data by training with target pseudo-labels. However,
as corroborated in this work, under distributional shift, the pseudo-labels
can be unreliable in terms of their large discrepancy from target ground
truth. In this paper, we propose Cycle Self-Training (CST), a principled self-
training algorithm that explicitly enforces pseudo-labels to generalize across
domains. CST cycles between a forward step and a reverse step until
convergence. In the forward step, CST generates target pseudo-labels with a
source-trained classifier. In the reverse step, CST trains a target classifier
using target pseudo-labels, and then updates the shared representations to
make the target classifier perform well on the source data. We introduce the
Tsallis entropy as a confidence-friendly regularization to improve the quality
of target pseudo-labels. We analyze CST theoretically under realistic
assumptions, and provide hard cases where CST recovers target ground truth,
while both invariant feature learning and vanilla self-training fail.
Empirical results indicate that CST significantly improves over the state-of-
the-arts on visual recognition and sentiment analysis benchmarks.

##  1 Introduction

Transferring knowledge from a source domain with rich supervision to an
unlabeled target domain is an important yet challenging problem. Since deep
neural networks are known to be sensitive to subtle change in underlying
distributions [70], models trained on one labeled dataset often fail to
generalize to another unlabeled dataset [58, 1]. Unsupervised domain
adaptation (UDA) addresses the challenge of distributional shift by adapting
the source model to the unlabeled target data [50, 43].

The mainstream paradigm for UDA is _feature adaptation_ , a.k.a. _domain
alignment_. By reducing the distance of the source and target feature
distributions, these methods learn invariant representations to facilitate
knowledge transfer between domains [34, 22, 36, 54, 37, 73], with successful
applications in various areas such as computer vision [63, 27, 77] and natural
language processing [75, 49]. Despite their popularity, the impossibility
theories [6] uncovered intrinsic limitations of learning invariant
representations when it comes to label shift [74, 32] and shift in the support
of domains [29].

Figure 1: Standard self-training vs. cycle self-training. In standard self-
training, we generate target pseudo-labels with a source model, and then train
the model with both source ground-truths and target pseudo-labels. In cycle
self-training, we train a target classifier with target pseudo-labels in the
inner loop, and make the target classifier perform well on the source domain
by updating the shared representations in the outer loop.

Recently, self-training (a.k.a. _pseudo-labeling_) [21, 78, 30, 32, 47, 68]
has been gaining momentum as a promising alternative to feature adaptation.
Originally tailored to semi-supervised learning, self-training generates
pseudo-labels of unlabeled data, and jointly trains the model with source
labels and target pseudo-labels [31, 39, 30]. However, the _distributional
shift_ in UDA makes pseudo-labeling more difficult. Directly using all pseudo-
labels is risky due to accumulated error and even trivial solution [14]. Thus
previous works tailor self-training to UDA by selecting trustworthy pseudo-
labels. Using confidence threshold or reweighting, recent works try to
alleviate the negative effect of domain shift in standard self-training [78,
47], but they can be brittle and require expensive tweaking of the threshold
or weight for different tasks, and their performance gain is still
inconsistent.

In this work, we first analyze the quality of pseudo-labels with or without
domain shift to delve deeper into the difficulty of standard self-training in
UDA. On popular benchmark datasets, when the source and target are the same,
our analysis indicates that the pseudo-label distribution is almost identical
to the ground-truth distribution. However, with distributional shift, their
discrepancy can be _very large_ with examples of several classes mostly
misclassified into other classes. We also study the difficulty of selecting
correct pseudo-labels with popular criteria under domain shift. Although
entropy and confidence are reasonable selection criteria for correct pseudo-
labels without domain shift, the domain shift makes their accuracy decrease
sharply.

Our analysis shows that domain shift makes pseudo-labels _unreliable_ and that
self-training on selected target instances with accurate pseudo-labels is less
successful. Thereby, more principled improvement of standard self-training
should be tailored to UDA and address the domain shift explicitly. In this
work, we propose Cycle Self-Training (CST), a principled self-training
approach to UDA, which overcomes the limitations of standard self-training
(see Figure 1). Different from previous works to select target pseudo-labels
with hard-to-tweak protocols, CST learns to generalize the pseudo-labels
across domains. Specifically, CST cycles between the use of target pseudo-
labels to train a target classifier, and the update of shared representations
to make the target classifier perform well on the source data. In contrast to
the standard Gibbs entropy that makes the target predictions over-confident,
we propose a confidence-friendly uncertainty measure based on the Tsallis
entropy in information theory, which adaptively minimizes the uncertainty
without manually tuning or setting thresholds. Our method is simple and
generally applicable to vision and language tasks with various backbones.

We empirically evaluate our method on a series of standard UDA benchmarks.
Results indicate that CST outperforms previous state-of-the-art methods in 21
out of 25 tasks for object recognition and sentiment classification.
Theoretically, we prove that the minimizer of CST objective is endowed with
general guarantees of target performance. We also study hard cases on specific
distributions, showing that CST recovers target ground-truths while both
feature adaptation and standard self-training fail.

##  2 Preliminaries

We study unsupervised domain adaptation (UDA). Consider a source distribution
$P$ and a target distribution $Q$ over the input-label space
$\mathcal{X}\times\mathcal{Y}$. We have access to $n_{s}$ labeled _i.i.d._
samples $\widehat{P}=\\{x_{i}^{s},y_{i}^{s}\\}_{i=1}^{n_{s}}$ from $P$ and
$n_{t}$ unlabeled _i.i.d._ samples $\widehat{Q}=\\{x_{i}^{t}\\}_{i=1}^{n_{t}}$
from $Q$. The model $f$ comprises a feature extractor $h_{\phi}$ parametrized
by $\phi$ and a head (linear classifier) $g_{\theta}$ parametrized by
$\theta$, i.e. $f_{\theta,\phi}(x)=g_{\theta}(h_{\phi}(x))$. The loss function
is $\ell(\cdot,\cdot)$. Denote by
$L_{P}(\theta,\phi):=\mathrm{\mathbb{E}}_{(x,y)\sim
P}\ell(f_{\theta,\phi}(x),y)$ the expected error on $P$. Similarly, we use
$L_{\widehat{P}}(\theta,\phi)$ to denote the empirical error on dataset
$\widehat{P}$.

We discuss two mainstream UDA methods and their formulations: feature
adaptation and self-training.

Feature Adaptation trains the model $f$ on the source dataset $\widehat{P}$,
and simultaneously matches the source and target distributions in the
representation space $\mathcal{Z}=h(\mathcal{X})$:

$\displaystyle\mathop{\min}_{\theta,\phi}L_{\widehat{P}}(\theta,\phi)+d(h_{\sharp}{\widehat{P}},h_{\sharp}{\widehat{Q}}).$
(1)

Here, $h_{\sharp}{\widehat{P}}$ denotes the pushforward distribution of
$\widehat{P}$, and $d(\cdot,\cdot)$ is some distribution distance. For
instance, Long et al. [34] used maximum mean discrepancy $d_{\textup{MMD}}$,
and Ganin et al. [22] approximated the $\mathcal{H}\Delta\mathcal{H}$-distance
$d_{\mathcal{H}\Delta\mathcal{H}}$ [7] with adversarial training. Despite its
pervasiveness, recent works have shown the intrinsic limitations of feature
adaptation under real-world situations [6, 74, 33, 32, 29].

Self-Training is considered a promising alternative to feature adaptation. In
this work we mainly focus on pseudo-labeling [31, 30]. Stemming from semi-
supervised learning, standard self-training trains a source model $f_{s}$ on
the source dataset $\widehat{P}$:
$\mathop{\min}_{\theta_{s},\phi_{s}}L_{\widehat{P}}(\theta_{s},\phi_{s})$. The
target pseudo-labels are then generated by $f_{s}$ on the target dataset
$\widehat{Q}$. To leverage unlabeled target data, self-training trains the
model on the source and target datasets together with source ground-truths and
target pseudo-labels:

$\displaystyle\mathop{\min}_{\theta,\phi}L_{\widehat{P}}(\theta,\phi)+\mathrm{\mathbb{E}}_{x\sim\widehat{Q}}\ell(f_{\theta,\phi}(x),\mathop{\arg\max}_{i}\\{f_{\theta_{s},\phi_{s}}(x)_{[i]}\\}).$
(2)

Self-training also uses label-sharpening as a standard protocol [31, 57].
Another popular variant of pseudo-labeling is the teacher-student model [4,
61], which iteratively improves the quality of pseudo-labels via alternatively
replacing $\theta_{s}$ and $\phi_{s}$ with $\theta$ and $\phi$ of the previous
iteration.

###  2.1 Limitations of Standard Self-Training

Standard self-training with pseudo-labels uses unlabeled data efficiently for
semi-supervised learning [31, 39, 57]. Here we carry out exploratory studies
on the popular VisDA-2017 [45] dataset using ResNet-50 backbones. We find that
domain shift makes the pseudo-labels biased towards several classes and
thereby unreliable in UDA. See Appendix C.1 for details and results on more
datasets.

Pseudo-label distributions with or without domain shift. We resample the
original VisDA-2017 to simulate different relationship between source and
target domains: 1) _i.i.d._ , 2) covariate shift, and 3) label shift. We train
the model on the three variants of source dataset and use it to generate
target pseudo-labels. We show the distributions of target ground-truths and
pseudo-labels in Figure 2 (Left). When the source and target distributions are
identical, the distribution of pseudo-labels is almost the same as ground-
truths, indicating the reliability of pseudo-labels. In contrast, when exposed
to label shift or covariate shift, the distribution of pseudo-labels is
significantly different from target ground-truths. Note that classes 2, 7, 8
and 12 appear rarely in the target pseudo-labels in the covariate shift
setting, indicating that the pseudo-labels are biased towards several classes
due to domain shift. Self-training with these pseudo-labels is risky since it
may lead to misalignment of distributions and misclassify many examples of
classes 2, 7, 8 and 12.

Figure 2: Analysis of pseudo-labels under domain shift on VisDA-2017. Left:
Pseudo-label distributions with and without domain shift. Middle: Changes of
pseudo-label distributions throughout training. Right: Quality of pseudo-
labels under different pseudo-label selection criteria.

Change of pseudo-label distributions throughout training. To further study the
change of pseudo-labels in standard self-training, we compute the total
variation (TV) distance between target ground-truths and target pseudo-labels:
$d_{\textup{TV}}(c,c^{\prime})=\frac{1}{2}\sum_{i}\|c_{i}-c_{i}^{\prime}\|$,
where $c_{i}$ is the ratio of class $i$. We plot its change during training in
Figure 2 (Middle). Although the error rate of pseudo-labels continues to
decrease, $d_{\textup{TV}}$ remains almost unchanged at $0.26$ throughout
training. Note that $d_{\textup{TV}}$ is the lower bound of the error rate of
the pseudo-labels (shown in Appendix C.1). If $d_{\textup{TV}}$ converges to
$0.26$, then the accuracy of pseudo-labels is upper-bounded by $0.74$. This
indicates that the important denoising ability [66] of pseudo-labels in
standard self-training is hindered by domain shift.

Difficulty of selecting reliable pseudo-labels under domain shift. To mitigate
the negative effect of false pseudo-labels, recent works proposed to select
correct pseudo-labels based on thresholding the entropy or confidence criteria
[35, 21, 37, 57]. However, it remains unclear whether these strategies are
still effective under domain shift. Here we compare the quality of pseudo-
labels selected by different strategies with or without domain shift. For each
strategy, we compute False Positive Rate and True Positive Rate for different
thresholds and plot its ROC curve in Figure 2 (Right). When the source and
target distributions are identical, both entropy and confidence are reasonable
strategies for selecting correct pseudo-labels (AUC=0.89). However, when the
target pseudo-labels are generated by the source model, the quality of pseudo-
labels decreases sharply under domain shift (AUC=0.78).

##  3 Approach

We present Cycle Self-Training (CST) to improve pseudo-labels under domain
shift. An overview of our method is given in Figure 1. Cycle Self-Training
iterates between a forward step and a reverse step to make self-trained
classifiers generalize well on both target and source domains.

###  3.1 Cycle Self-Training

Forward Step. Similar to standard self-training, we have a source classifier
$\theta_{s}$ trained on top of the shared representations $\phi$ on the
labeled source domain, and use it to generate target pseudo-labels as

$\displaystyle
y^{\prime}=\mathop{\arg\max}_{i}\\{f_{\theta_{s},\phi}(x)_{[i]}\\},$ (3)

for each $x$ in the target dataset $\widehat{Q}$. Traditional self-training
methods use confidence thresholding or reweighting to select reliable pseudo-
labels. For example, Sohn et al. [57] select pseudo-labels with softmax value
and Long et al. [37] add entropy reweighting to rely on examples with more
confidence prediction. However, the output of deep networks is usually
miscalibrated [25], and is not necessarily related to the ground-truth
confidence even on the same distribution. In domain adaptation, as shown in
Section 2.1, the discrepancy between the source and target domains makes
pseudo-labels even more unreliable, and the performance of commonly used
selection strategies is also unsatisfactory. Another drawback is the expensive
tweaking in order to find the optimal confidence threshold for new tasks. To
better apply self-training to domain adaptation, we expect that the model can
gradually refine the pseudo-labels by itself without the cumbersome selection
or thresholding.

Reverse Step. We design a complementary step with the following insights to
improve self-training. Intuitively, the labels on the source domain contain
both useful information that can transfer to the target domain and harmful
information that can make pseudo-labels incorrect. Similarly, reliable pseudo-
labels on the target domain can transfer to the source domain in turn, while
models trained with incorrect pseudo-labels on the target domain cannot
transfer to the source domain. In this sense, if we explicitly train the model
to make target pseudo-labels informative of the source domain, we can
gradually make the pseudo-labels more accurate and learn to generalize to the
target domain.

Specifically, with the pseudo-labels $y^{\prime}$ generated by the source
classifier $\theta_{s}$ at hand as in equation 3, we train a target head
$\hat{\theta}_{t}(\phi)$ on top of the representation $\phi$ with pseudo-
labels on the target domain $\widehat{Q}$,

$\displaystyle\hat{\theta}_{t}(\phi)=\mathop{\arg\min}_{\theta}\mathrm{\mathbb{E}}_{x\sim\widehat{Q}}\ell(f_{\theta,\phi}(x),y^{\prime}).$
(4)

We wish to make the target pseudo-labels informative of the source domain and
gradually refine them. To this end, we update the shared feature extractor
$\phi$ to predict accurately on the source domain and jointly enforce the
target classifier $\hat{\theta}_{t}(\phi)$ to perform well on the source
domain. This naturally leads to the objective of Cycle Self-Training:

$\displaystyle\mathop{\textup{minimize}}_{\theta_{s},\phi}L_{\textup{Cycle}}({\theta_{s},\phi}):=L_{\widehat{P}}(\theta_{s},\phi)+L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi).$
(5)

Bi-level Optimization. The objective in equation 5 relies on the solution
$\hat{\theta}_{t}(\phi)$ to the objective in equation 4. Thus, CST formulates
a _bi-level_ optimization problem. In the inner loop we generate target
pseudo-labels with the source classifier (equation 3), and train a target
classifier with target pseudo-labels (equation 4). After each inner loop, we
update the feature extractor $\phi$ for one step in the outer loop (equation
5), and start a new inner loop again. However, since the inner loop of the
optimization in equation 4 only involves the light-weight linear head
$\theta_{t}$, we propose to calculate the analytical form of
$\hat{\theta}_{t}(\phi)$ and directly back-propagate to the feature extractor
$\phi$ instead of calculating the second-order derivatives as in MAML [18].
The resulting framework is as fast as training two heads jointly. Also note
that the solution $\hat{\theta}_{t}(\phi)$ relies on $\theta_{s}$ implicitly
through $y^{\prime}$. However, both standard self-training and our
implementation use label sharpening, making $y^{\prime}$ not differentiable.
Thus we follow vanilla self-training and do not consider the gradient of
$\hat{\theta}_{t}(\phi)$ w.r.t. $y^{\prime}$ in the outer loop optimization.
We defer the derivation and implementation of bi-level optimization to
Appendix B.2.

###  3.2 Tsallis Entropy Minimization

Gibbs entropy is widely used by existing semi-supervised learning methods to
regularize the model output and minimize the uncertainty of predictions on
unlabeled data [24]. In this work, we generalize Gibbs entropy to Tsallis
entropy [62] in information theory. Suppose the softmax output of a model is
$y\in\mathbb{R}^{K}$, then the $\alpha$-Tsallis entropy is defined as

$\displaystyle S_{\alpha}(y)=\frac{1}{\alpha-1}\left(1-\sum
y_{[i]}^{\alpha}\right),$ (6)

where $\alpha>0$ is the entropic-index. Note that
$\operatorname{lim}_{\alpha\rightarrow
1}S_{\alpha}(y)=\sum_{i}-y_{[i]}\textup{log}(y_{[i]})$ which exactly recovers
the Gibbs entropy. When $\alpha=2$, $S_{\alpha}(y)$ becomes the Gini impurity
$1-\sum_{i}y_{[i]}^{2}$.

Algorithm 1 Cycle Self-Training (CST)

1: Input: source dataset $\widehat{P}$ and target dataset $\widehat{Q}$.

2: for $\textup{epoch}=0$ to MaxEpoch do

3: Select $\hat{\alpha}$ as equation 10 at the start of each epoch.

4: for $t=0$ to MaxIter do

5: Forward Step

6: Generate pseudo-labels on the target domain with $\phi$ and $\theta_{s}$:
$y^{\prime}=\mathop{\arg\max}_{i}\\{f_{\theta_{s},\phi}(x)_{[i]}\\}$.

7: Reverse Step

8: Train a target head $\hat{\theta}_{t}(\phi)$ with target pseudo-labels
$y^{\prime}$ on the feature extractor $\phi$:
$\displaystyle\hat{\theta}_{t}(\phi)=\mathop{\arg\min}_{\theta}\mathrm{\mathbb{E}}_{x\sim\widehat{Q}}\ell(f_{\theta,\phi}(x),y^{\prime}).$

9: Update the feature extractor $\phi$ and the source head $\theta_{s}$ to
make $\hat{\theta}_{t}(\phi)$ perform well on the source dataset and minimize
the $\hat{\alpha}$-Tsallis entropy on the target dataset:
$\displaystyle\phi\leftarrow\phi$
$\displaystyle-\eta\nabla_{\phi}[L_{\widehat{P}}(\theta_{s},\phi)+L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)+L_{\widehat{Q},\textup{Tsallis},\hat{\alpha}}({\theta_{s},\phi})].$
(7)
$\displaystyle\theta_{s}\leftarrow\theta_{s}-\eta\nabla_{\theta_{s}}[L_{\widehat{P}}(\theta_{s},\phi)+L_{\widehat{Q},\textup{Tsallis},\hat{\alpha}}({\theta_{s},\phi})].$
(8)

10: end for

11: end for

We propose to control the uncertainty of target pseudo-labels based on Tsallis
entropy minimization:

$\displaystyle
L_{\widehat{Q},\textup{Tsallis},\alpha}({\theta,\phi}):=\mathrm{\mathbb{E}}_{x\sim\widehat{Q}}S_{\alpha}(f_{\theta,\phi}(x)).$
(9)

Figure 3: Tsallis entropy vs. entropic-index $\alpha$.

Figure 3 shows the change of Tsallis entropy with different entropic-indices
$\alpha$ for binary problems. Intuitively, smaller $\alpha$ exerts more
penalization on uncertain predictions and larger $\alpha$ allows several
scores $y_{i}$’s to be similar. This is critical in self-training since an
overly small $\alpha$ (as in Gibbs entropy) will make the incorrect dimension
of pseudo-labels close to $1$ and have no chance to be corrected throughout
training. In Section 5.4, we further verify this property with experiments.

An important improvement of the Tsallis entropy over Gibbs entropy is that it
can choose the suitable measure of uncertainty for different systems to avoid
over-confidence caused by overly penalizing the uncertain pseudo-labels. To
automatically find the suitable $\alpha$, we adopt a similar strategy as
Section 3.1. The intuition is that if we use the suitable entropic-index
$\alpha$ to train the source classifier $\theta_{s,\alpha}$, the target
pseudo-labels generated by $\theta_{s,\alpha}$ will contain desirable
knowledge of the source dataset, i.e. a target classifier $\theta_{t,\alpha}$
trained with these pseudo-labels will perform well on the source domain.
Therefore, we semi-supervisedly train a classifier $\hat{\theta}_{s,\alpha}$
on the source domain with the $\alpha$-Tsallis entropy regularization
$L_{\widehat{Q},\textup{Tsallis},\alpha}$ on the target domain as:
$\hat{\theta}_{s,\alpha}=\mathop{\arg\min}_{\theta}L_{\widehat{P}}(\theta,\phi)+L_{\widehat{Q},\textup{Tsallis},\alpha}({\theta,\phi})$,
from which we obtain the target pseudo-labels. Then we train another head
$\hat{\theta}_{t,\alpha}$ with target pseudo-labels. We automatically find
$\alpha$ by minimizing the loss of $\hat{\theta}_{t,\alpha}$ on the source
data:

$\displaystyle\hat{\alpha}=\mathop{\arg\min}_{\alpha\in[1,2]}L_{\widehat{P}}(\hat{\theta}_{t,\alpha},\phi)$
(10)

To solve equation 10, we discretize the feasible region $[1,2]$ of $\alpha$
and use discrete optimization to lower computational cost. We also update
$\alpha$ at the start of each epoch, since we found more frequent update leads
to no performance gain. Details are deferred to Appendix B.3. Finally, with
the optimal $\hat{\alpha}$ found, we add the $\hat{\alpha}$-Tsallis entropy
minimization term $L_{\widehat{Q},\textup{Tsallis},\hat{\alpha}}$ to the
overall objective:

$\displaystyle\mathop{\textup{minimize}}_{\theta_{s},\phi}L_{\textup{Cycle}}({\theta_{s},\phi})+L_{\widehat{Q},\textup{Tsallis},\hat{\alpha}}({\theta_{s},\phi}).$
(11)

In summary, Algorithm 1 depicts the complete training procedure of Cycle Self-
Training (CST).

##  4 Theoretical Analysis

We analyze the properties of CST theoretically. First, we prove that the
minimizer of the CST loss $L_{\textup{CST}}(f_{s},f_{t})$ will lead to small
target loss $\textup{Err}_{Q}(f_{s})$ under a simple but realistic expansion
assumption. Then, we further demonstrate a concrete instantiation where cycle
self-training provably recovers the target ground truth, but both feature
adaptation and standard self-training fail. _Due to space limit, we state the
main results here and defer all proof details to Appendix A_.

###  4.1 CST Provably Works under the Expansion Assumption

We start from a $K$-way classification model,
$f:\mathcal{X}\rightarrow[0,1]^{K}\in\mathcal{F}$ and
$\tilde{f}(x):=\arg\max_{i}f(x)_{[i]}$ denotes the prediction. Denote by
$P_{i}$ the conditional distribution of $P$ given $y=i$. Assume the supports
of $P_{i}$ and $P_{j}$ are disjoint for $i\neq j$. The definition is similar
for $Q_{i}$. We further Assume $P(y=i)=Q(y=i)$. For any $x\in\mathcal{X}$,
$\mathcal{N}(x)$ is defined as the _neighboring set_ of $x$ with a proper
metric $d(\cdot,\cdot)$,
$\mathcal{N}(x)=\\{x^{\prime}:d(x,x^{\prime})\leq\xi\\}$.
$\mathcal{N}(A):=\cup_{x\in A}\mathcal{N}(x)$. Denote the expected error on
the target domain by $\text{Err}_{Q}(f):=\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\tilde{f}(x)\neq y)$.

We study the CST algorithm under the expansion assumption of the mixture
distribution [66, 11]. Intuitively, this assumption indicates that the
conditional distributions $P_{i}$ and $Q_{i}$ are closely located and
regularly shaped, enabling knowledge transfer from the source domain to the
target domain.

######  Definition 1 ($(q,\epsilon)$-constant expansion [66]).

We say $P$ and $Q$ satisfy $(q,\epsilon)$-constant expansion for some constant
$q,\epsilon\in(0,1)$, if for any set $A\in\mathcal{X}$ and any $i\in[K]$ with
$\frac{1}{2}>P_{\frac{1}{2}(P_{i}+Q_{i})}(A)>q$, we have
$P_{\frac{1}{2}(P_{i}+Q_{i})}(\mathcal{N}(A)\backslash
A)>\mathop{\min}\\{\epsilon,P_{\frac{1}{2}(P_{i}+Q_{i})}(A)\\}$.

Based on this expansion assumption, we consider a _robustness-constrained_
version of CST. Later we will show that the robustness is closely related to
the uncertainty. Denote by $f_{s}$ the source model and $f_{t}$ the model
trained on the target with pseudo-labels. Let
$R(f_{t}):=P_{\frac{1}{2}(P+Q)}(\\{x:\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})$
represent the robustness [66] of $f_{t}$ on $P$ and $Q$. Suppose
$\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\tilde{f}_{s}(x)\neq\tilde{f}_{t}(x))\leq c$ and
$R(f_{t})\leq\rho$. The following theorem states that when $f_{s}$ and $f_{t}$
behave similarly on the target domain $Q$ and $f_{t}$ is robust to local
changes in input, the minimizer of the cycle source error
$\textup{Err}_{P}(f_{t})$ will guarantee low error of $f_{s}$ on the target
domain $Q$.

######  Theorem 1.

Suppose Definition 1 holds for $P$ and $Q$. For any $f_{s},f_{t}$ satisfying
$\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\tilde{f}_{s}(x)\neq\tilde{f}_{t}(x))\leq c$ and
$R(f_{t})\leq\rho$, the expected error of $f_{s}$ on the target domain $Q$ is
bounded,

$\displaystyle\textup{Err}_{Q}(f_{s})\leq\textup{Err}_{P}(f_{t})+c+2q+\frac{\rho}{\min\\{\epsilon,q\\}}.$
(12)

To further relate the expected error with the CST training objective and
obtain finite-sample guarantee, we use the multi-class margin loss:
$l_{\gamma}(f(x),y):=\psi_{\gamma}(-\mathcal{M}(f(x),y))$, where
$\mathcal{M}(v,y)=v_{[y]}-\max_{y^{\prime}\neq y}v_{[y^{\prime}]}$ and
$\psi_{\gamma}$ is the ramp function. We then extend the margin loss:
$\mathcal{M}(v)=\max_{y}(v_{[y]}-\max_{y^{\prime}\neq y}v_{[y^{\prime}]})$
(The difference between the largest and the second largest scores in $v$), and
$l_{\gamma}(f_{t}(x),f_{s}(x)):=\psi_{\gamma}(-\mathcal{M}(f_{t}(x),\tilde{f}_{s}(x)))$.
Further suppose $f_{[i]}$ is $L_{f}$-Lipschitz w.r.t. the metric
$d(\cdot,\cdot)$ and $\tau:=1-2L_{f}\xi\min\\{\epsilon,q\\}>0$. Consider the
following training objective for CST, denoted by
$L_{\textup{CST}}(f_{s},f_{t})$, where
$L_{\widehat{P},\gamma}(f_{t}):=\mathrm{\mathbb{E}}_{(x,y)\sim{\widehat{P}}}l_{\gamma}(f_{t}(x),y)$
corresponds to the cycle source loss in equation 5,
$L_{\widehat{Q},\gamma}(f_{t},f_{s}):=\mathrm{\mathbb{E}}_{(x,y)\sim{\widehat{Q}}}l_{\gamma}(f_{t}(x),f_{s}(x))$
is consistent with the target loss in equation 4, and $\mathcal{M}(f_{t}(x))$
is closely related to the uncertainty of predictions in equation 11.

$\displaystyle\mathop{\min}L_{\textup{CST}}(f_{s},f_{t}):=L_{\widehat{P},\gamma}(f_{t})+L_{\widehat{Q},\gamma}(f_{t},f_{s})+\frac{1-\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(\widehat{P}+\widehat{Q})}\mathcal{M}(f_{t}(x))}{\tau}.$
(13)

The following theorem shows that the minimizer of the training objective
$L_{\textup{CST}}(f_{s},f_{t})$ guarantees low population error of $f_{s}$ on
the target domain $Q$.

######  Theorem 2.

$\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})$ denotes the empirical
Rademacher complexity of function class $\mathcal{F}$ on dataset
$\widehat{P}$. For any solution of equation 13 and $\gamma>0$, with
probability larger than $1-\delta$,

$\displaystyle\textup{Err}_{Q}(f_{s})$ $\displaystyle\leq
L_{\textup{CST}}(f_{s},f_{t})+2q+\frac{4K}{\gamma}\left[\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})+\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})\right]+\frac{2}{\tau}\left[\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})+\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{Q}})\right]+\zeta,$

where
$\zeta=O\left(\sqrt{\textup{log}(1/\delta)/{n_{s}}}+\sqrt{\textup{log}(1/\delta)/{n_{t}}}\right)$
is a low-order term. $\tilde{\mathcal{F}}\times\mathcal{F}$ refers to the
function class $\\{x\rightarrow
f(x)_{[\tilde{f^{\prime}}(x)]}:f,f^{\prime}\in\mathcal{F}\\}$.

Main insights. Theorem 2 justifies CST under the expansion assumption. The
generalization error of the classifier $f_{s}$ on the target domain is bounded
with the CST loss objective $L_{\textup{CST}}(f_{s},f_{t})$, the intrinsic
property of the data distribution $q$, and the complexity of the function
classes. In our algorithm, $L_{\textup{CST}}(f_{s},f_{t})$ is minimized by the
neural networks and $q$ is a constant. The complexity of the function class
can be controlled with proper regularization.

###  4.2 Hard Case for Feature Adaptation and Standard Self-Training

To gain more insight, we study UDA in a quadratic neural network
$f_{\theta,\phi}(x)=\theta^{\top}(\phi^{\top}x)^{\odot 2}$, where $\odot$ is
element-wise power. In UDA, the source can have multiple solutions but we aim
to learn the one working on the target [34]. We design the underlying
distributions $p$ and $q$ in Table 6 to reflect this. Consider the following
$P$ and $Q$. $x_{[1]}$ and $x_{[2]}$ are sampled _i.i.d._ from distribution
$p$ on $P$, and from

Table 1: The design of $p$ and $q$. Distribution | $-1$ | $+1$ | $0$
---|---|---|---
Source $p$ | $0.05$ | $0.05$ | $0.90$
Target $q$ | $0.25$ | $0.25$ | $0.50$

$q$ on $Q$. For $i\in[3,d]$, $x_{[i]}=\sigma_{i}x_{[2]}$ on $P$ and
$x_{[i]}=\sigma_{i}x_{[1]}$ on $Q$. $\sigma_{i}\in\\{\pm 1\\}$ are _i.i.d._
and uniform. We also assume realizability: $y=x_{[1]}^{2}-x_{[2]}^{2}$ for
both source and target. Note that $y=x_{[1]}^{2}-x_{[i]}^{2}$ for all
$i\in[2,d]$ are solutions to $P$ but only $y=x_{[1]}^{2}-x_{[2]}^{2}$ works on
$Q$. We visualize this specialized setting in Figure 4.

Figure 4: The hard case where $d=3$. Green dots for $y=1$, red dots for $y=0$,
and blue dots for $y=-1$. The grey curve is the classification boundary of
different features. The good feature $x_{[1]}^{2}-x_{[2]}^{2}$ works on the
target domain (shown in (a) and (c)), whereas the spurious feature
$x_{[1]}^{2}-x_{[3]}^{2}$ only works on the source domain (shown in (b) and
(d)). In Section 4.2, we show that feature adaptation and standard self-
training learn $x_{[1]}^{2}-x_{[3]}^{2}$, while CST learns
$x_{[1]}^{2}-x_{[2]}^{2}$.

To make the features more tractable, we study the norm-constrained version of
the algorithms (details are deferred to Section A.3.2). We compare the
features learned by feature adaptation, standard self-training, and CST.
Intuitively, feature adaptation fails because the _ideal_ target solution
$y=x_{[1]}^{2}-x_{[2]}^{2}$ has larger distance in the feature space than
other spurious solutions $y=x_{[1]}^{2}-x_{[i]}^{2}$. Standard self-training
also fails since it will choose randomly among all solutions. In comparison,
CST can recover the ground truth, because it can distinguish the spurious
solution resulting in bad pseudo-labels. A classifier trained with those
pseudo-labels cannot work on the source domain in turn. This intuition is
rigorously justified in the following two theorems.

######  Theorem 3.

For $\epsilon\in(0,0.5)$, the following statements hold for feature adaptation
and self-training:

  * •

For failure rate $\xi>0$, and target dataset size
${n_{t}}>\Theta(\log\frac{1}{\xi})$, with probability at least $1-\xi$ over
the sampling of target data, the solution
$(\hat{\theta}_{\textup{FA}},\hat{\phi}_{\textup{FA}})$ found by feature
adaptation satisfies

$\displaystyle\textup{Err}_{Q}(\hat{\theta}_{\textup{FA}},\hat{\phi}_{\textup{FA}})\geq\epsilon.$
(14)

  * •

With probability at least $1-\frac{1}{d-1}$, the solution
$(\hat{\theta}_{\textup{ST}},\hat{\phi}_{\textup{ST}})$ of standard self-
training satisfies

$\displaystyle\textup{Err}_{Q}(\hat{\theta}_{\textup{ST}},\hat{\phi}_{\textup{ST}})\geq\epsilon.$
(15)

######  Theorem 4.

For failure rate $\xi>0$, and target dataset size
${n_{t}}>\Theta(\log\frac{1}{\xi})$, with probability at least $1-\xi$, the
solution of CST ($\hat{\phi}_{\textup{CST}},\hat{\theta}_{\textup{CST}})$
recovers the ground truth of the target dataset:

$\displaystyle\ \ \
\quad\textup{Err}_{Q}(\hat{\theta}_{\textup{CST}},\hat{\phi}_{\textup{CST}})=0.$
(16)

##  5 Experiments

We test the performance of the proposed method on both vision and language
datasets. Cycle Self-Training (CST) consistently outperforms state-of-the-art
feature adaptation and self-training methods. Code is available at
https://github.com/Liuhong99/CST.

###  5.1 Setup

Datasets. We experiment on visual object recognition and linguistic sentiment
classification tasks: Office-Home [64] has $65$ classes from four kinds of
environment with large domain gap: Artistic (Ar), Clip Art (Cl), Product (Pr),
and Real-World (Rw); VisDA-2017 [45] is a large-scale UDA dataset with two
domains named Synthetic and Real. The datasets consist of over 200k images
from 12 categories of objects; Amazon Review [10] is a linguistic sentiment
classification dataset of product reviews in four products: _Books_ (B),
_DVDs_ (D), _Electronics_ (E), and _Kitchen_ (K).

Implementation. We use ResNet-50 [26] (pretrained on ImageNet [53]) as feature
extractors for vision tasks, and BERT [16] for linguistic tasks. On
VisDA-2017, we also provide results of ResNet-101 to include more baselines.
We use cross-entropy loss for classification on the source domain. When
training the target head $\hat{\theta}_{t}$ and updating the feature extractor
with CST, we use squared loss to get the analytical solution of
$\hat{\theta}_{t}$ directly and avoid calculating second order derivatives as
meta-learning [18]. Details on adapting squared loss to multi-class
classification are deferred to Appendix B. We adopt SGD with initial learning
rate $\eta_{0}=2e-3$ for image classification and $\eta_{0}=5e-4$ for
sentiment classification. Following standard protocol in [26], we decay the
learning rate by $0.1$ each $50$ epochs until $150$ epochs. We run all the
tasks $3$ times and report mean and deviation in top-1 accuracy. For
VisDA-2017, we report the mean class accuracy. Following Theorem 2, we also
enhance CST with sharpness-aware regularization [19] (CST+SAM), which help
regularize the Lipschitzness of the function class. Due to space limit, we
report mean accuracies in Tables 2 and 3 and defer standard deviation to
Appendix C.

###  5.2 Baselines

We compare with two lines of works in domain adaptation: feature adaptation
and self-training. We also compare with more complex state-of-the-arts and
create stronger baselines by combining feature adaptation and self-training.

Feature Adaptation: DANN [22], MCD [54], CDAN [37] (which improves DANN with
pseudo-label conditioning), MDD [73] (which improves previous domain
adaptation with margin theory), Implicit Alignment (IA) [28] (which improves
MDD to deal with label shift).

Self-Training. We include VAT [40], MixMatch [8] and FixMatch [57] in the
semi-supervised learning literature as self-training methods. We also compare
with self-training methods for UDA: CBST [77], which considers class imbalance
in standard self-training, and KLD [78], which improves CBST with label
regularization. However, these methods involve tricks specified for
convolutional networks. Thus, in sentiment classification tasks where we use
BERT backbones, we compare with other consistency regularization baselines:
VAT [40], VAT+Entropy Minimization.

Feature Adaptation + Self-Training. DIRT-T [56] combines DANN, VAT, and
entropy minimization. We also create more powerful baselines: CDAN+VAT+Entropy
and MDD+Fixmatch.

Other SOTA. AFN [69] boosts transferability by large norm. STAR [38] aligns
domains with stochastic classifiers. SENTRY [48] selects confident examples
with a committee of random augmentations.

Table 2: Accuracy (%) on Office-Home for unsupervised domain adaptation (ResNet-50). Method | Ar-Cl | Ar-Pr | Ar-Rw | Cl-Ar | Cl-Pr | Cl-Rw | Pr-Ar | Pr-Cl | Pr-Rw | Rw-Ar | Rw-Cl | Rw-Pr | Avg.
---|---|---|---|---|---|---|---|---|---|---|---|---|---
DANN [22] | 45.6 | 59.3 | 70.1 | 47.0 | 58.5 | 60.9 | 46.1 | 43.7 | 68.5 | 63.2 | 51.8 | 76.8 | 57.6
CDAN [37] | 50.7 | 70.6 | 76.0 | 57.6 | 70.0 | 70.0 | 57.4 | 50.9 | 77.3 | 70.9 | 56.7 | 81.6 | 65.8
CDAN+VAT+Entropy | 52.2 | 71.5 | 76.4 | 61.1 | 70.3 | 67.8 | 59.5 | 54.4 | 78.6 | 73.2 | 59.0 | 82.7 | 67.3
FixMatch [57] | 51.8 | 74.2 | 80.1 | 63.5 | 73.8 | 61.3 | 64.7 | 51.4 | 80.0 | 73.3 | 56.8 | 81.7 | 67.7
MDD [73] | 54.9 | 73.7 | 77.8 | 60.0 | 71.4 | 71.8 | 61.2 | 53.6 | 78.1 | 72.5 | 60.2 | 82.3 | 68.1
MDD+IA [28] | 56.2 | 77.9 | 79.2 | 64.4 | 73.1 | 74.4 | 64.2 | 54.2 | 79.9 | 71.2 | 58.1 | 83.1 | 69.5
SENTRY [48] | 61.8 | 77.4 | 80.1 | 66.3 | 71.6 | 74.7 | 66.8 | 63.0 | 80.9 | 74.0 | 66.3 | 84.1 | 72.2
CST | 59.0 | 79.6 | 83.4 | 68.4 | 77.1 | 76.7 | 68.9 | 56.4 | 83.0 | 75.3 | 62.2 | 85.1 | 73.0
Table 3: Accuracy (%) on Multi-Domain Sentiment Dataset for domain adaptation with BERT. Method | B-D | B-E | B-K | D-B | D-E | D-K | E-B | E-D | E-K | K-B | K-D | K-E | Avg.
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Source-only | 89.7 | 88.4 | 90.9 | 90.1 | 88.5 | 90.2 | 86.9 | 88.5 | 91.5 | 87.6 | 87.3 | 91.2 | 89.2
DANN [22] | 90.2 | 89.5 | 90.9 | 91.0 | 90.6 | 90.2 | 87.1 | 87.5 | 92.8 | 87.8 | 87.6 | 93.2 | 89.9
VAT [40] | 90.6 | 91.0 | 91.7 | 90.8 | 90.8 | 92.0 | 87.2 | 86.9 | 92.6 | 86.9 | 87.7 | 92.9 | 90.1
VAT+Entropy | 90.4 | 91.3 | 91.5 | 91.0 | 91.1 | 92.4 | 87.5 | 86.3 | 92.4 | 86.5 | 87.5 | 93.1 | 90.1
MDD [73] | 90.4 | 90.4 | 91.8 | 90.2 | 90.9 | 91.0 | 87.5 | 86.3 | 92.5 | 89.0 | 87.9 | 92.1 | 90.0
CST | 91.5 | 92.9 | 92.6 | 91.9 | 92.6 | 93.5 | 90.2 | 89.4 | 93.8 | 87.9 | 88.3 | 93.5 | 91.5
Table 4: Mean Class Accuracy (%) for unsupervised domain adaptation on VisDA-2017. Method | ResNet-50 | ResNet-101 | Method | ResNet-50 | ResNet-101
---|---|---|---|---|---
DANN [22] | 69.3 | 79.5 |  CBST [77] | – |  76.4 $\pm$ 0.9
VAT [40] |  68.0 $\pm$ 0.3 |  73.4 $\pm$ 0.5 |  KLD [78] | – |  78.1 $\pm$ 0.2
DIRT-T [56] |  68.2 $\pm$ 0.3 |  77.2 $\pm$ 0.5 |  MDD [73] | 74.6 |  81.6 $\pm$ 0.3
MCD [54] | 69.2 | 77.7 |  AFN [69] | – | 76.1
CDAN [37] | 70.0 | 80.1 |  MDD+IA [28] | 75.8 | –
CDAN+VAT+Entropy |  76.5 $\pm$ 0.5 |  80.4 $\pm$ 0.7 | MDD+FixMatch |  77.8 $\pm$ 0.3 |  82.4 $\pm$ 0.4
MixMatch |  69.3 $\pm$ 0.4 |  77.0 $\pm$ 0.5 |  STAR [38] | – | 82.7
FixMatch [57] |  74.5 $\pm$ 0.2 |  79.5 $\pm$ 0.3 |  SENTRY [48] | 76.7 | –
CST |  79.9 $\pm$ 0.5 |  84.8 $\pm$ 0.6 | CST+SAM |  80.6 $\pm$ 0.5 |  86.5 $\pm$ 0.7

###  5.3 Results

Results on 12 pairs of _Office-Home_ tasks are shown in Table 2. When domain
shift is large, standard self-training methods such as VAT and FixMatch suffer
from the decay in pseudo-label quality. CST outperforms feature adaptation and
self-training methods significantly in 9 out of 12 tasks. Note that CST does
not involve manually setting confidence threshold or reweighting.

Table 4 shows the results on _VisDA-2017_. CST surpasses state-of-the-arts
with ResNet-50 and ResNet-101 backbones. We also combine feature adaptation
and self-training (DIRT-T, CDAN+VAT+entropy and MDD+FixMatch) to test if
feature adaptation alleviates the negative effect of domain shift in standard
self-training. Results indicate that CST is a better solution than simple
combination.

While most traditional self-training methods include techniques specified for
ConvNets such as Mixup [72], CST is a _universal_ method and can directly work
on sentiment classification by simply replacing the head and training
objective of BERT [16]. In Table 3, most feature adaptation baselines improve
over source only marginally, but CST outperforms all baselines on most tasks
significantly.

###  5.4 Analysis

Table 5: Ablation on VisDA-2017. Method |  Accuracy $\uparrow$ |  $d_{\textup{TV}}$ $\downarrow$
---|---|---
FixMatch [57] |  74.5 $\pm$ 0.2 | 0.22
Fixmatch+Tsallis |  76.3 $\pm$ 0.8 | 0.15
CST w/o Tsallis |  72.0 $\pm$ 0.4 | 0.16
CST+Entropy |  76.2 $\pm$ 0.6 | 0.20
CST |  79.9 $\pm$ 0.5 | 0.12

Ablation Study. We study the role of each part of CST in self-training. CST
w/o Tsallis removes the Tsallis entropy $L_{\textup{Tsallis},\alpha}$.
CST+Entropy replaces the Tsallis entropy with standard entropy.
FixMatch+Tsallis adds $L_{\textup{Tsallis},\alpha}$ to standard self-training.
Observations are shown in Table 5. CST+Entropy performs $3.7\%$ worse than
CST, indicating that Tsallis entropy is a better regularization for pseudo-
labels than standard entropy. CST performs $5.4\%$ better than FixMatch,
indicating that CST is better adapted to domain shift than standard self-
training. While FixMatch+Tsallis outperforms FixMatch, it is still $3.6\%$
behind CST, with much larger total variation distance $d_{\textup{TV}}$
between pseudo-labels and ground-truths, indicating that CST makes pseudo-
labels more reliable than standard self-training under domain shift.

Figure 5: Analysis. Left: Error of pseudo-labels and reverse pseudo-labels.
The error of target classifier $\theta_{t}$ on the source domain decreases,
indicating the quality of pseudo-labels is refined. Right: Histograms of the
difference between the largest and the second largest softmax scores. Tsallis
entropy avoids over-confidence.

Quality of Pseudo-labels. We visualize the error of pseudo-labels during
training on VisDA-2017 in Figure 5 (Left). The error of target classifier
$\theta_{t}$ on the source domain decreases quickly in training, when both the
error of pseudo-labels (error of $\theta_{s}$ on $Q$) and the total variation
(TV) distance between pseudo-labels and ground-truths continue to decay,
indicating that CST gradually refines pseudo-labels. This forms a clear
contrast to standard self-training as visualized in Figure 2 (Middle), where
the distance $d_{\textup{TV}}$ remains nearly unchanged throughout training.

Comparison of Gibbs entropy and Tsallis entropy. We compare the pseudo-labels
learned with standard Gibbs entropy and Tsallis entropy on Ar$\rightarrow$Cl
with ResNet-50 at epoch 40. We compute the difference between the largest and
the second largest softmax scores of each target example and plot the
histogram in Figure 5 (Right). Gibbs entropy makes the largest softmax output
close to 1, indicating over-confidence. In this case, if the prediction is
wrong, it can be hard to correct it using self-training. In contrast, Tsallis
entropy allows the largest and the second largest scores to be similar.

##  6 Related Work

Self-Training. Self-training is a mainstream technique for semi-supervised
learning [13]. In this work, we focus on pseudo-labeling [52, 31, 2], which
uses unlabeled data by training on pseudo-labels generated by a source model.
Other lines of work study consistency regularization [4, 51, 55, 40]. Recent
works demonstrate the power of such methods [67, 57, 23]. Equipped with proper
training techniques, these methods can achieve comparable results as standard
training that uses much more labeled examples [17]. Zoph et al. [76] compare
self-training to pre-training and joint training. Vu et al. [65], Mukherjee &
Awadallah [42] show that task-level self-training works well in few-shot
learning. These methods are tailored to semi-supervised learning or general
representation learning and do not take domain shift into consideration
explicitly. Wei et al. [66], Frei et al. [20] provide the first nice
theoretical analysis of self-training based on the expansion assumption.

Domain Adaptation. Inspired by the generalization error bound of Ben-David et
al. [7], Long et al. [34], Zellinger et al. [71] minimize distance measures
between source and target distributions to learn domain-invariant features.
Ganin et al. [22] (DANN) proposed to approximate the domain distance by
adversarial learning. Follow-up works proposed various improvement upon DANN
[63, 54, 37, 73, 28]. Popular as they are, failure cases exist in situation
like label shift [74, 32], shift in support of domains [29], and large
discrepancy between source and target [33]. Another line of works try to
address domain adaptation with self-training. Shu et al. [56] improves DANN
with VAT and entropy minimization. French et al. [21], Zou et al. [78], Li et
al. [32] incorporated various semi-supervised learning techniques to boost
domain adaptation performance. Kumar et al. [30], Chen et al. [15] and Cai et
al. [11] showed self-training provably works in domain adaptation under
certain assumptions.

##  7 Conclusion

We propose cycle self-training in place of standard self-training to
explicitly address the distribution shift in domain adaptation. We show that
our method provably works under the expansion assumption and demonstrate hard
cases for feature adaptation and standard self-training. Self-training (or
pseudo-labeling) is only one line of works in the semi-supervised learning
literature. Future work can delve into the behaviors of other semi-supervised
learning techniques including consistency regularization and data augmentation
under distribution shift, and exploit them extensively for domain adaptation.

## Acknowledgements

This work was supported by the National Natural Science Foundation of China
under Grants 62022050 and 62021002, Beijing Nova Program under Grant
Z201100006820041, China’s Ministry of Industry and Information Technology, the
MOE Innovation Plan and the BNRist Innovation Fund.

## References

  * Albadawy et al. [2018] Albadawy, E. A., Saha, A., and Mazurowski, M. A.  Deep learning for segmentation of brain tumors: Impact of cross-institutional training and testing.  _Medical Physics_ , 45(3), 2018.
  * Arazo et al. [2019] Arazo, E., Ortego, D., Albert, P., O’Connor, N. E., and McGuinness, K.  Pseudo-labeling and confirmation bias in deep semi-supervised learning.  _CoRR_ , abs/1908.02983, 2019.
  * Arora et al. [2019] Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R.  On exact computation with an infinitely wide neural net.  In _NeurIPS_ , pp. 8141–8150. 2019.
  * Bachman et al. [2014] Bachman, P., Alsharif, O., and Precup, D.  Learning with pseudo-ensembles.  In _NeurIPS_ , volume 27, pp. 3365–3373, 2014.
  * Bartlett & Mendelson [2002] Bartlett, P. L. and Mendelson, S.  Rademacher and gaussian complexities: Risk bounds and structural results.  _JMLR_ , 3(Nov):463–482, 2002.
  * Ben-David & Urner [2012] Ben-David, S. and Urner, R.  On the hardness of domain adaptation and the utility of unlabeled target samples.  In _ALT_ , pp. 139–153, 2012.
  * Ben-David et al. [2010] Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W.  A theory of learning from different domains.  _Machine Learning_ , 79(1-2):151–175, 2010.
  * Berthelot et al. [2019] Berthelot, D., Carlini, N., Goodfellow, I., Papernot, N., Oliver, A., and Raffel, C.  Mixmatch: A holistic approach to semi-supervised learning.  _arXiv preprint arXiv:1905.02249_ , 2019.
  * Bertinetto et al. [2019] Bertinetto, L., Henriques, J. F., Torr, P., and Vedaldi, A.  Meta-learning with differentiable closed-form solvers.  In _ICLR_ , 2019.
  * Blitzer et al. [2007] Blitzer, J., Dredze, M., and Pereira, F.  Biographies, Bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification.  In _ACL_ , pp. 440–447, 2007.
  * Cai et al. [2021] Cai, T., Gao, R., Lee, J. D., and Lei, Q.  A theory of label propagation for subpopulation shift, 2021.
  * Carlini [2021] Carlini, N.  Poisoning the unlabeled dataset of semi-supervised learning, 2021.
  * Chapelle et al. [2006] Chapelle, O., Schölkopf, B., and Zien, A.  _Semi-supervised learning_.  MIT press Cambridge, 2006.
  * Chen et al. [2019] Chen, C., Xie, W., Huang, W., Rong, Y., Ding, X., Huang, Y., Xu, T., and Huang, J.  Progressive feature alignment for unsupervised domain adaptation.  In _CVPR_ , pp. 627–636, 2019.
  * Chen et al. [2020] Chen, Y., Wei, C., Kumar, A., and Ma, T.  Self-training avoids using spurious features under domain shift.  In _NeurIPS_ , pp. 21061–21071, 2020.
  * Devlin et al. [2019] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , pp. 4171–4186, 2019.
  * Du et al. [2021] Du, J., Grave, E., Gunel, B., Chaudhary, V., Celebi, O., Auli, M., Stoyanov, V., and Conneau, A.  Self-training improves pre-training for natural language understanding.  In _NAACL_ , pp. 5408–5418, 2021.
  * Finn et al. [2017] Finn, C., Abbeel, P., and Levine, S.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _ICML_ , pp. 1126–1135, 2017.
  * Foret et al. [2021] Foret, P., Kleiner, A., Mobahi, H., and Neyshabur, B.  Sharpness-aware minimization for efficiently improving generalization.  In _ICLR_ , 2021.
  * Frei et al. [2021] Frei, S., Zou, D., Chen, Z., and Gu, Q.  Self-training converts weak learners to strong learners in mixture models.  _arXiv preprint arXiv:2106.13805_ , 2021.
  * French et al. [2018] French, G., Mackiewicz, M., and Fisher, M.  Self-ensembling for visual domain adaptation.  In _ICLR_ , 2018.
  * Ganin et al. [2016] Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Marchand, M., and Lempitsky, V.  Domain-adversarial training of neural networks.  _JMLR_ , 17(1):2096–2030, 2016.
  * Ghiasi et al. [2021] Ghiasi, G., Zoph, B., Cubuk, E. D., Le, Q. V., and Lin, T.-Y.  Multi-task self-training for learning general representations.  In _ICCV_ , pp. 8856–8865, 2021.
  * Grandvalet & Bengio [2004] Grandvalet, Y. and Bengio, Y.  Semi-supervised learning by entropy minimization.  In _NeurIPS_ , pp. 529–536, 2004.
  * Guo et al. [2017] Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q.  On calibration of modern neural networks.  In _ICML_ , pp. 1321–1330, 2017.
  * He et al. [2016] He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _CVPR_ , pp. 770–778, 2016.
  * Hoffman et al. [2018] Hoffman, J., Tzeng, E., Park, T., Zhu, J., Isola, P., Saenko, K., Efros, A. A., and Darrell, T.  Cycada: Cycle-consistent adversarial domain adaptation.  In _ICML_ , pp. 1994–2003, 2018.
  * Jiang et al. [2020] Jiang, X., Lao, Q., Matwin, S., and Havaei, M.  Implicit class-conditioned domain alignment for unsupervised domain adaptation.  In _ICML_ , pp. 4816–4827, 2020.
  * Johansson et al. [2019] Johansson, F. D., Sontag, D., and Ranganath, R.  Support and invertibility in domain-invariant representations.  In _AISTATS_ , pp. 527–536, 2019.
  * Kumar et al. [2020] Kumar, A., Ma, T., and Liang, P.  Understanding self-training for gradual domain adaptation.  In _ICML_ , pp. 5468–5479, 2020.
  * Lee [2013] Lee, D.-H.  Pseudo-label : The simple and efficient semi-supervised learning method for deep neural networks.  _ICML Workshop: Challenges in Representation Learning (WREPL)_ , 2013\.
  * Li et al. [2020] Li, B., Wang, Y., Che, T., Zhang, S., Zhao, S., Xu, P., Zhou, W., Bengio, Y., and Keutzer, K.  Rethinking distributional matching based domain adaptation.  _ArXiv_ , abs/2006.13352, 2020.
  * Liu et al. [2019] Liu, H., Long, M., Wang, J., and Jordan, M.  Transferable adversarial training: A general approach to adapting deep classifiers.  In _ICML_ , volume 97, pp. 4013–4022, 2019.
  * Long et al. [2015] Long, M., Cao, Y., Wang, J., and Jordan, M. I.  Learning transferable features with deep adaptation networks.  In _ICML_ , pp. 97–105, 2015.
  * Long et al. [2016] Long, M., Zhu, H., Wang, J., and Jordan, M. I.  Unsupervised domain adaptation with residual transfer networks.  In _NeurIPS_ , pp. 136–144, 2016.
  * Long et al. [2017] Long, M., Zhu, H., Wang, J., and Jordan, M. I.  Deep transfer learning with joint adaptation networks.  In _ICML_ , pp. 2208–2217, 2017.
  * Long et al. [2018] Long, M., Cao, Z., Wang, J., and Jordan, M. I.  Conditional adversarial domain adaptation.  In _NeurIPS_ , pp. 1640–1650. 2018.
  * Lu et al. [2020] Lu, Z., Yang, Y., Zhu, X., Liu, C., Song, Y.-Z., and Xiang, T.  Stochastic classifiers for unsupervised domain adaptation.  In _CVPR_ , pp. 9111–9120, 2020.
  * Mey & Loog [2016] Mey, A. and Loog, M.  A soft-labeled self-training approach.  In _ICPR_ , 2016.
  * Miyato et al. [2018] Miyato, T., Maeda, S., Ishii, S., and Koyama, M.  Virtual adversarial training: A regularization method for supervised and semi-supervised learning.  _TPAMI_ , 2018.
  * Mohri et al. [2018] Mohri, M., Rostamizadeh, A., and Talwalkar, A.  _Foundations of machine learning_.  MIT press, 2018.
  * Mukherjee & Awadallah [2020] Mukherjee, S. and Awadallah, A.  Uncertainty-aware self-training for few-shot text classification.  In _NeurIPS_ , volume 33, pp. 21199–21212, 2020.
  * Pan & Yang [2010] Pan, S. J. and Yang, Q.  A survey on transfer learning.  _TKDE_ , 22(10):1345–1359, 2010.
  * Paszke et al. [2019] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  Pytorch: An imperative style, high-performance deep learning library.  In _NeurIPS_ , volume 32, pp. 8026–8037, 2019.
  * Peng et al. [2017] Peng, X., Usman, B., Kaushik, N., Hoffman, J., Wang, D., and Saenko, K.  Visda: The visual domain adaptation challenge.  _CoRR_ , abs/1710.06924, 2017.
  * Peng et al. [2019] Peng, X., Bai, Q., Xia, X., Huang, Z., Saenko, K., and Wang, B.  Moment matching for multi-source domain adaptation.  In _ICCV_ , pp. 1406–1415, 2019.
  * Prabhu et al. [2020] Prabhu, V., Khare, S., Kartik, D., and Hoffman, J.  Sentry: Selective entropy optimization via committee consistency for unsupervised domain adaptation, 2020.
  * Prabhu et al. [2021] Prabhu, V., Khare, S., Kartik, D., and Hoffman, J.  Sentry: Selective entropy optimization via committee consistency for unsupervised domain adaptation.  In _ICCV_ , pp. 8558–8567, October 2021.
  * Qu et al. [2019] Qu, X., Zou, Z., Cheng, Y., Yang, Y., and Zhou, P.  Adversarial category alignment network for cross-domain sentiment classification.  In _NAACL_ , 2019.
  * Quionero-Candela et al. [2009] Quionero-Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D.  _Dataset Shift in Machine Learning_.  The MIT Press, 2009.
  * Rasmus et al. [2015] Rasmus, A., Berglund, M., Honkala, M., Valpola, H., and Raiko, T.  Semi-supervised learning with ladder networks.  In _NeurIPS_ , volume 28, pp. 3546–3554, 2015.
  * Rosenberg et al. [2005] Rosenberg, C., Hebert, M., and Schneiderman, H.  Semi-supervised self-training of object detection models.  In _WACV_ , volume 1, pp. 29–36, 2005.
  * Russakovsky et al. [2015] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L.  ImageNet Large Scale Visual Recognition Challenge.  _IJCV_ , 115(3):211–252, 2015.
  * Saito et al. [2018] Saito, K., Watanabe, K., Ushiku, Y., and Harada, T.  Maximum classifier discrepancy for unsupervised domain adaptation.  In _CVPR_ , pp. 3723–3732, 2018.
  * Sajjadi et al. [2016] Sajjadi, M., Javanmardi, M., and Tasdizen, T.  Regularization with stochastic transformations and perturbations for deep semi-supervised learning.  In _NeurIPS_ , volume 29, pp. 1163–1171, 2016.
  * Shu et al. [2018] Shu, R., Bui, H., Narui, H., and Ermon, S.  A DIRT-t approach to unsupervised domain adaptation.  In _ICLR_ , 2018.
  * Sohn et al. [2020] Sohn, K., Berthelot, D., Carlini, N., Zhang, Z., Zhang, H., Raffel, C. A., Cubuk, E. D., Kurakin, A., and Li, C.-L.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  In _NeurIPS_ , 2020.
  * Szegedy et al. [2014] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  In _ICLR_ , 2014.
  * Talagrand [2014] Talagrand, M.  _Upper and lower bounds for stochastic processes: modern methods and classical problems_ , volume 60.  Springer Science & Business Media, 2014.
  * Tan et al. [2020] Tan, S., Peng, X., and Saenko, K.  Class-imbalanced domain adaptation: An empirical odyssey.  In _ECCV Workshop_ , 2020.
  * Tarvainen & Valpola [2017] Tarvainen, A. and Valpola, H.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  In _NeurIPS_ , volume 30, pp. 1195–1204, 2017.
  * Tsallis [1988] Tsallis, C.  Possible generalization of boltzmann-gibbs statistics.  _Journal of Statistical Physics_ , 52(1-2):479–487, 1988.
  * Tzeng et al. [2017] Tzeng, E., Hoffman, J., Saenko, K., and Darrell, T.  Adversarial discriminative domain adaptation.  In _CVPR_ , pp. 7167–7176, 2017.
  * Venkateswara et al. [2017] Venkateswara, H., Eusebio, J., Chakraborty, S., and Panchanathan, S.  Deep hashing network for unsupervised domain adaptation.  In _CVPR_ , pp. 5018–5027, 2017.
  * Vu et al. [2021] Vu, T., Luong, M.-T., Le, Q. V., Simon, G., and Iyyer, M.  Strata: Self-training with task augmentation for better few-shot learning.  _arXiv preprint arXiv:2109.06270_ , 2021.
  * Wei et al. [2021] Wei, C., Shen, K., Yining, C., and Ma, T.  Theoretical analysis of self-training with deep networks on unlabeled data.  In _ICLR_ , 2021.
  * Xie et al. [2020] Xie, Q., Luong, M. T., Hovy, E., and Le, Q. V.  Self-training with noisy student improves imagenet classification.  In _CVPR_ , 2020.
  * Xie et al. [2021] Xie, S. M., Kumar, A., Jones, R., Khani, F., Ma, T., and Liang, P.  In-n-out: Pre-training and self-training using auxiliary information for out-of-distribution robustness.  In _ICLR_ , 2021.
  * Xu et al. [2019] Xu, R., Li, G., Yang, J., and Lin, L.  Larger norm more transferable: An adaptive feature norm approach for unsupervised domain adaptation.  In _ICCV_ , 2019.
  * Yosinski et al. [2014] Yosinski, J., Clune, J., Bengio, Y., and Lipson, H.  How transferable are features in deep neural networks?  In _NeurIPS_ , pp. 3320–3328. 2014.
  * Zellinger et al. [2017] Zellinger, W., Grubinger, T., Lughofer, E., Natschläger, T., and Saminger-Platz, S.  Central moment discrepancy (CMD) for domain-invariant representation learning.  In _ICLR_ , 2017.
  * Zhang et al. [2018] Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D.  mixup: Beyond empirical risk minimization.  In _ICLR_ , 2018.
  * Zhang et al. [2019] Zhang, Y., Liu, T., Long, M., and Jordan, M.  Bridging theory and algorithm for domain adaptation.  In _ICML_ , pp. 7404–7413, 2019.
  * Zhao et al. [2019] Zhao, H., Combes, R. T. D., Zhang, K., and Gordon, G.  On learning invariant representations for domain adaptation.  In _ICML_ , volume 97, pp. 7523–7532, 2019.
  * Ziser & Reichart [2018] Ziser, Y. and Reichart, R.  Pivot based language modeling for improved neural domain adaptation.  In _NAACL_ , pp. 1241–1251, 2018.
  * Zoph et al. [2020] Zoph, B., Ghiasi, G., Lin, T.-Y., Cui, Y., Liu, H., Cubuk, E. D., and Le, Q.  Rethinking pre-training and self-training.  In _NeurIPS_ , volume 33, pp. 3833–3845, 2020.
  * Zou et al. [2018] Zou, Y., Yu, Z., Vijaya Kumar, B. V. K., and Wang, J.  Unsupervised domain adaptation for semantic segmentation via class-balanced self-training.  In _ECCV_ , pp. 297–313, 2018.
  * Zou et al. [2019] Zou, Y., Yu, Z., Liu, X., Kumar, B. V., and Wang, J.  Confidence regularized self-training.  In _ICCV_ , October 2019.

##  Appendix A Details in Section 4

###  A.1 Proof of Theorem 1

In Section 4.1, we study CST theoretically. In Theorem 1, we show that when
the population error of the target classifier $f_{t}$ on the source domain $P$
is low and $f_{t}$ is locally consistent, the source classifier $f_{s}$ is
guaranteed to perform well on the target domain $Q$. We further show that the
consistency (robustness) is guaranteed by the confidence of the model (Lemma
3). Finally, we show in Theorem 2 that the minimizer of an objective function
consistent with the CST objective in Section 3.1 leads to small target loss of
the source classifier $\textup{Err}_{Q}(f_{s})$.

We first review the assumptions made in Section 4.1 in order to prove Theorem
1. Consider a $K$-way classification problem.
$f:X\rightarrow[0,1]^{K}\in\mathcal{F}$ and
$\tilde{f}(x):=\arg\max_{i}f(x)_{[i]}$. We first state the properties of
source and target distributions $P$ and $Q$. Assume the source and target
distributions are composed of $K$ sub-populations, each corresponding to one
class, and the sub-populations of different classes have disjoint support.
This indicates that a ground truth labeling function exists, which is a common
assumption as in [7, 66, 11]. We also assume for simplicity of presentation
that $P(y=i)=Q(y=i)$. Note that our techniques can be directly applied to the
case where $\frac{P(y=i)}{Q(y=i)}$ is bounded as in [11].

######  Assumption 1.

Denote by $P_{i}$ and $Q_{i}$ the conditional distribution of $P$ and $Q$
given $y=i$. We assume that: (1) $P(y=i)=Q(y=i)$, and (2) the supports of
$P_{i}$ and $P_{j}$ are disjoint for $i\neq j$.

Our analysis relies on the expansion assumption [66, 11], which intuitively
states that the data distribution has good continuity within each class.
Therefore, the subset in the support of a class will connect to its
neighborhood, enabling knowledge transfer between domains. Wei et al. [66]
justifies this assumption on real-world datasets with BigGAN.

######  Assumption 2 ($(q,\epsilon)$-constant expansion [66]).

For any $x\in\mathcal{X}$, $\mathcal{N}(x)$ is defined as the _neighboring
set_ of $x$, $\mathcal{N}(x)=\\{x^{\prime}:d(x,x^{\prime})\leq\xi\\}$, where
$d$ is a proper metric. $\mathcal{N}(A):=\cup_{x\in A}\mathcal{N}(x)$. We say
$P$ and $Q$ satisfy $(q,\epsilon)$-constant expansion for some constants
$q,\epsilon\in(0,1)$, if for any set $A\in\mathcal{X}$ and any $i\in[K]$ with
$\frac{1}{2}>P_{\frac{1}{2}(P_{i}+Q_{i})}(A)>q$, we have
$P_{\frac{1}{2}(P_{i}+Q_{i})}(\mathcal{N}(A)\backslash
A)>\mathop{\min}\\{\epsilon,P_{\frac{1}{2}(P_{i}+Q_{i})}(A)\\}$.

Based on this expansion assumption, we consider a _robustness-constrained_
version of CST for now. In Theorem 2, we will show that the population
robustness loss is closely related to the uncertainty of of CST. Denote by
$f_{s}$ the source model and $f_{t}$ the model trained on the target with
pseudo-labels. Let $R(f_{t}):=P_{\frac{1}{2}(P+Q)}(\\{x:\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})$
represent the robustness [66] of $f_{t}$ on $P$ and $Q$. Suppose
$\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\tilde{f}_{s}(x)\neq\tilde{f}_{t}(x))\leq c$ and
$R(f_{t})\leq\rho$. Theorem 1 states that when $f_{s}$ and $f_{t}$ behave
similarly on $Q$ ($f_{t}$ fits the pseudo-labels generated by $f_{s}$ on the
target domain) and $f_{t}$ is robust to local changes in input, the minimizer
of the cycle source error $\textup{Err}_{P}(f_{t})$ will guarantee low error
on the target domain $Q$.

######  Theorem 1.

Suppose Assumption 1 and Assumption 2 hold for $P$ and $Q$. For any
$f_{s},f_{t}$ satisfying $\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\tilde{f}_{s}(x)\neq\tilde{f}_{t}(x))\leq c$ and
$R(f_{t})\leq\rho$, the expected error of $f_{s}$ on the target domain $Q$ is
bounded,

$\displaystyle\textup{Err}_{Q}(f_{s})\leq\textup{Err}_{P}(f_{t})+c+2q+\rho\ /\
\min\\{\epsilon,q\\}.$ (17)

We now turn to the proof of Theorem 1. We want to show the error of $f_{t}$ on
the source domain $P$ is close to the error of $f_{s}$ on the target domain
$Q$. We first show that when the robustness error $R(f_{t})$ is controlled,
the error of $f_{t}$ on the source and the target will be close. This is done
by analyzing the error on each sub-population $P_{i}$ and $Q_{i}$ separately.
Then we use the fact that the losses of $f_{s}$ and $f_{t}$ are also close
when their disagreement on the target domain is controlled to obtain the final
result.

######  Lemma 1 (Robustness on sub-populations).

Divide $[K]$ into $S_{1}$ and $S_{2}$, where for every $i\in S_{1}$,
$\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})<\min\\{\epsilon,q\\}$,
and for every $i\in S_{2}$,
$\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})\geq\min\\{\epsilon,q\\}$.
Under the condition of Theorem 1, we have

$\displaystyle\sum_{i\in S_{1}}P(y=i)\geq
1-\frac{\rho}{\min\\{\epsilon,q\\}}.$ (18)

###### Proof of Lemma 1.

Suppose $\sum_{i\in S_{1}}P(y=i)<1-\frac{\rho}{\min\\{\epsilon,q\\}}$. Then we
have $\sum_{i\in S_{2}}P(y=i)>\frac{\rho}{\min\\{\epsilon,q\\}}$, which
implies

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P+Q)}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})$
$\displaystyle=\sum_{i\in[K]}\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})P(y=i)$
$\displaystyle\geq\sum_{i\in
S_{2}}\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})P(y=i)$
$\displaystyle>\min\\{\epsilon,q\\}\sum_{i\in S_{2}}P(y=i)$
$\displaystyle=\rho.$

Since we have
$R(f_{t})=\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P+Q)}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})<\rho$,
this forms a contradiction. ∎

We have established that for a large proportion of the sub-populations, the
robustness is guaranteed. The next lemma shows that for each sub-population
where the robustness is guaranteed, $\textup{Err}_{P_{i}}(f_{t})$ and
$\textup{Err}_{Q_{i}}(f_{t})$ is close to each other by invoking the expansion
assumption [66].

######  Lemma 2 (Accuracy propagates on robust sub-populations).

Under the condition of Theorem 1, if the sub-populations $P_{i}$ and $Q_{i}$
satisfy
$\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})<\min\\{\epsilon,q\\}$,
we have

$\displaystyle\left|\textup{Err}_{P_{i}}(f_{t})-\textup{Err}_{Q_{i}}(f_{t})\right|\leq
2q.$ (19)

###### Proof of Lemma 2.

We claim that either $\textup{Err}_{\frac{1}{2}(P_{i}+Q_{i})}(f_{t})\leq q$ or
$\textup{Err}_{\frac{1}{2}(P_{i}+Q_{i})}(f_{t})\geq 1-q$. On the one hand, if
$\frac{1}{2}>\textup{Err}_{\frac{1}{2}(P_{i}+Q_{i})}(f_{t})>q$, by the
$(q,\epsilon)$-expansion property (Definition 1),
$P_{\frac{1}{2}(P_{i}+Q_{i})}(\mathcal{N}(\\{x:\tilde{f}_{t}(x)\neq
i\\})\backslash\\{x:\tilde{f}_{t}(x)\neq i\\})>\min\\{\epsilon,q\\}$. Note
that in $\mathcal{N}(\\{x:\tilde{f}_{t}(x)\neq
i\\})\backslash\\{x:\tilde{f}_{t}(x)\neq i\\}$, $\tilde{f}_{t}(x)=i$. Thus,
for $x$ in the set $\mathcal{N}(\\{x:\tilde{f}_{t}(x)\neq
i\\})\backslash\\{x:\tilde{f}_{t}(x)\neq i\\}$, there exists
$x^{\prime}\in\mathcal{N}(x)$,
$\tilde{f}_{t}(x^{\prime})\neq\tilde{f}_{t}(x)=i$.

$\displaystyle R(f_{t})$
$\displaystyle=\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})$
$\displaystyle\geq\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})\mathbb{I}(x\in\mathcal{N}(\\{x:\tilde{f}_{t}(x)\neq
i\\})\backslash\\{x:\tilde{f}_{t}(x)\neq i\\})$
$\displaystyle=P_{\frac{1}{2}(P_{i}+Q_{i})}(\mathcal{N}(\\{x:\tilde{f}_{t}(x)\neq
i\\})\backslash\\{x:\tilde{f}_{t}(x)\neq i\\})$
$\displaystyle>\min\\{\epsilon,q\\},$

which contradicts the condition that $R(f_{t})<\min\\{\epsilon,q\\}$.

On the other hand, if
$\frac{1}{2}\leq\textup{Err}_{\frac{1}{2}(P_{i}+Q_{i})}(f_{t})<1-q$, the
argument is similar. By the $(q,\epsilon)$-expansion property (Definition 1),
$P_{\frac{1}{2}(P_{i}+Q_{i})}(\mathcal{N}(\\{x:\tilde{f}_{t}(x)=i\\})\backslash\\{x:\tilde{f}_{t}(x)=i\\})>\min\\{\epsilon,q\\}$.
Note that in
$\mathcal{N}(\\{x:\tilde{f}_{t}(x)=i\\})\backslash\\{x:\tilde{f}_{t}(x)=i\\}$,
$\tilde{f}_{t}(x)\neq i$. Thus, for $x$ in the set
$\mathcal{N}(\\{x:\tilde{f}_{t}(x)=i\\})\backslash\\{x:\tilde{f}_{t}(x)=i\\}$,
there exists $x^{\prime}\in\mathcal{N}(x)$,
$i=\tilde{f}_{t}(x^{\prime})\neq\tilde{f}_{t}(x)$.

$\displaystyle R(f_{t})$
$\displaystyle=\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})$
$\displaystyle\geq\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P_{i}+Q_{i})}\mathbb{I}(\exists
x^{\prime}\in\mathcal{N}(x),\tilde{f}_{t}(x)\neq\tilde{f}_{t}(x^{\prime})\\})\mathbb{I}(x\in\mathcal{N}(\\{x:\tilde{f}_{t}(x)=i\\})\backslash\\{x:\tilde{f}_{t}(x)=i\\})$
$\displaystyle=P_{\frac{1}{2}(P_{i}+Q_{i})}(\mathcal{N}(\\{x:\tilde{f}_{t}(x)=i\\})\backslash\\{x:\tilde{f}_{t}(x)=i\\})$
$\displaystyle>\min\\{\epsilon,q\\},$

which also contradicts the condition that $R(f_{t})<\min\\{\epsilon,q\\}$.

Note that
$\textup{Err}_{\frac{1}{2}(P_{i}+Q_{i})}(f_{t})=\frac{1}{2}\textup{Err}_{P_{i}}(f_{t})+\frac{1}{2}\textup{Err}_{Q_{i}}(f_{t})$.
Also we have $\textup{Err}_{P_{i}}(f_{t})\in[0,1]$. In consequence, we have
either $\textup{Err}_{P_{i}}(f_{t}),\textup{Err}_{Q_{i}}(f_{t})\in[0,2q]$ or
$\textup{Err}_{P_{i}}(f_{t}),\textup{Err}_{Q_{i}}(f_{t})\in[1-2q,1]$, which
completes the proof. ∎

With Lemma 1 and Lemma 2 at hand, we can prove Theorem 1 by putting the
analysis on each sub-population together.

###### Proof of Theorem 1.

$\displaystyle\textup{Err}_{Q}(f_{t})$
$\displaystyle=\sum_{i\in[K]}\textup{Err}_{Q_{i}}(f_{t})P(y=i)$
$\displaystyle\leq\sum_{i\in[S_{1}]}\textup{Err}_{Q_{i}}(f_{t})P(y=i)+\sum_{i\in[S_{2}]}P(y=i)$
$\displaystyle\leq\sum_{i\in[S_{1}]}(\textup{Err}_{P_{i}}(f_{t})+2q)P(y=i)+\sum_{i\in[S_{2}]}P(y=i)$
$\displaystyle\leq\textup{Err}_{P}(f_{t})+2q+\frac{\rho}{\min\\{\epsilon,q\\}},$

where the second inequality holds due to Lemma 2, and the last holds due to
Lemma 1. Also note that
$\textup{Err}_{Q}(f_{s})\leq\textup{Err}_{Q}(f_{t})+\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\arg\max_{[i]}f_{s}(x)_{[i]}\neq\arg\max_{[i]}f_{t}(x)_{[i]})$ by
the triangle inequality. Adding these two equations results in Theorem 1. ∎

###  A.2 Proof of Theorem 2

To obtain finite-sample guarantee, we need additional assumptions on the
function class $\mathcal{F}$.

######  Assumption 3.

The function class $\mathcal{F}$ satisfies the following properties: (1)
$\mathcal{F}$ is closed to permutations of coordinates, (2) $0\in\mathcal{F}$,
and (3) each coordinate of $f$ is $L_{f}$-Lipschitz w.r.t. $d(\cdot,\cdot)$.

This assumption is also standard since common models for multi-class
classification are symmetric for each class. Setting all the weight parameters
of neural networks to $0$ will result in $0$ output.

We review the definition of terms in Theorem 2. The ramp function
$\psi_{\gamma}:\mathbb{R}\rightarrow[0,1]$ is defined as:

$\displaystyle\psi_{\gamma}(x)=\left\\{\begin{array}[]{lr}1,&x\leq 0\\\
1-\frac{x}{\gamma},&0<x\leq\gamma\\\ 0,&x>\gamma\end{array}\right.$ (23)

The margin function is defined as
$\mathcal{M}(v,y)=v_{[y]}-\max_{y^{\prime}\neq y}v_{[y^{\prime}]}$ and
$\mathcal{M}(v)=\max_{y}\\{v_{[y]}-\max_{y^{\prime}\neq
y}v_{[y^{\prime}]}\\}$. For multi-class classification problems,
$\mathcal{M}(v)$ is closely related to the confidence, since it is equal to
the difference between the largest and the second largest scores. The multi-
class margin loss is composed of $\psi_{\gamma}(x)$ and $\mathcal{M}$:
$l_{\gamma}(f(x),y):=\psi_{\gamma}(-\mathcal{M}(f(x),y))$. Denote by
$L_{\widehat{P},\gamma}(f_{t})$ the empirical margin loss of $f_{t}$ on the
source dataset $\widehat{P}$,
$L_{\widehat{P},\gamma}(f_{t})=\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{P}}l_{\gamma}(f_{t}(x),y)$.
To measure the inconsistency of $f_{s}$ and $f_{t}$, we extend the multi-class
margin loss as
$l_{\gamma}(f_{s}(x),f_{t}(x)):=\psi_{\gamma}(-\mathcal{M}(f_{s}(x),\tilde{f_{t}}(x)))$.
Denote by $L_{\widehat{P},\gamma}(f_{t},f_{s})$ the empirical margin
inconsistency loss of $f_{t}$ and $f_{s}$ on the source dataset $\widehat{P}$,
$L_{\widehat{P},\gamma}(f_{t},f_{s})=\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{P}}l_{\gamma}(f_{t}(x),f_{s}(x))$.

Consider minimizing the following objective:

$\displaystyle\mathop{\min}L_{\textup{CST}}(f_{s},f_{t}):=\underbrace{L_{\widehat{P},\gamma}(f_{t})}_{\textup{Cycle
Loss}}+\underbrace{L_{\widehat{P},\gamma}(f_{t},f_{s})}_{\textup{Target
Loss}}+\underbrace{\nicefrac{{1-\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(\widehat{P}+\widehat{Q})}\mathcal{M}(f_{t}(x))}}{{\tau}}}_{\textup{Uncertainty
Loss}}.$ (24)

Note that $L_{\widehat{P},\gamma}(f_{t})$ is the loss of $f_{t}$ on the source
dataset (the cycle loss), and $L_{\widehat{P},\gamma}(f_{t},f_{s})$ is the
training error of $f_{t}$ on the target dataset. $\mathcal{M}(f_{t}(x))$
equals the difference between the largest and the second largest scores of
$f_{t}(x)$, indicating the confidence of $f_{t}$. Thus,
$1-\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(\widehat{P}+\widehat{Q})}\mathcal{M}(f_{t}(x))$
is the uncertainty of $f_{t}$ on the source and target datasets.

The following theorem shows that the minimizer of the training objective
$L_{\textup{CST}}(f_{s},f_{t})$ guarantees low population error of $f_{s}$ on
the target domain $Q$.

######  Theorem 2.

Under the condition of Theorem 1 and Assumption 3. For any solution of
equation 13 and $\gamma>0$, with probability larger than $1-\delta$,

$\displaystyle\textup{Err}_{Q}(f_{s})$ $\displaystyle\leq
L_{\textup{CST}}(f_{s},f_{t})+2q+\frac{4K}{\gamma}\left[\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})+\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})\right]+\frac{2}{\tau}\left[\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})+\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{Q}})\right]+\zeta,$

where
$\zeta=O\left(\sqrt{\textup{log}(1/\delta)/{n_{s}}}+\sqrt{\textup{log}(1/\delta)/{n_{t}}}\right)$
is a low-order term. $\tilde{\mathcal{F}}\times\mathcal{F}$ refers to the
function class $\\{x\rightarrow
f(x)_{[\tilde{f^{\prime}}(x)]}:f,f^{\prime}\in\mathcal{F}\\}$.
$\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})$ denotes the empirical
Rademacher complexity of function class $\mathcal{F}$ on dataset
$\widehat{P}$.

We provide the function classes used in the proof. For a function class
$f\in\mathcal{F}:\mathbb{R}^{d}\rightarrow[0,1]^{K}$, $\mathcal{F}_{[i]}$
denotes each coordinate of $\mathcal{F}$: $\mathcal{F}_{[i]}=\\{x\rightarrow
f(x)_{[i]}:f\in\mathcal{F}\\}$. We also need other function classes based on
$\mathcal{F}_{[i]}$. $\cup\mathcal{F}_{[i]}$ denotes the union of
$\mathcal{F}_{[i]}$: $\cup\mathcal{F}_{[i]}=\cup_{i\in[K]}\mathcal{F}_{[i]}$.
$\max_{i}\mathcal{F}_{[i]}$ is composed of the maximum coordinate of
$f\in\mathcal{F}$ for all $x$:
$\max_{i}\mathcal{F}_{[i]}=\\{x\rightarrow\max_{i}f_{[i]}(x):f\in\mathcal{F}\\}$.
$\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}$ denotes
the function class composed of the second largest coordinate of
$f\in\mathcal{F}$ for all $x$:
$\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}=\\{x\rightarrow\max_{i\neq\tilde{f}(x)}f_{[i]}(x):f\in\mathcal{F}\\}$,
which we require to study the finite sample properties of the confidence loss
$\mathcal{M}(f(x))$. $\tilde{\mathcal{F}}\times\mathcal{F}$ denotes the
function class $\\{x\rightarrow
f_{\tilde{f}^{\prime}(x)}(x):f,f^{\prime}\in\mathcal{F}\\}$. The Rademacher
complexity of $\mathcal{F}_{[i]}$ on set $S=\\{x_{j}\\}_{j=1}^{n}$ of size $n$
is:
$\widehat{\mathcal{R}}(\mathcal{F}_{[i]}|_{S})=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\mathop{\sup}_{f\in\mathcal{F}}\sum_{j=1}^{n}\sigma_{j}f(x_{j})_{[i]}$.
The Rademacher complexity of $\cup\mathcal{F}_{[i]}$ is
$\widehat{\mathcal{R}}(\cup\mathcal{F}_{[i]}|_{S})=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\mathop{\sup}_{f\in\mathcal{F},i\in[K]}\sum_{j=1}^{n}\sigma_{j}f(x_{j})_{[i]}$.
The Rademacher complexity of $\max_{i}\mathcal{F}_{[i]}$ is
$\widehat{\mathcal{R}}(\max_{i}\mathcal{F}_{[i]}|_{S})=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\mathop{\sup}_{f\in\mathcal{F},i\in[K]}\sum_{j=1}^{n}\sigma_{j}\max_{i}f(x_{j})_{[i]}$.
We further denote by $\widehat{\mathcal{R}}(\mathcal{F}|_{S})$ the sum of the
Rademacher complexity of each $\mathcal{F}_{[i]}$,
$\widehat{\mathcal{R}}(\mathcal{F}|_{S})=\sum_{i=1}^{K}\widehat{\mathcal{R}}(\mathcal{F}_{[i]}|_{S})$.

To prove Theorem 2, we first observe the relationship between the confidence
objective
$\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(\widehat{P}+\widehat{Q})}\mathcal{M}(f_{t}(x))$
and the robustness constraint $R(f_{t}):=P_{\frac{1}{2}(P+Q)}(\\{x:\exists
x^{\prime}\in\mathcal{N}(x),\max_{[i]}f_{t}(x)\neq\max_{[i]}f_{t}(x^{\prime})\\})$
in Theorem 1. In fact, as shown in Lemma 3, when the output of the model is
confident on the source and target dataset, i.e.
$\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(\widehat{P}+\widehat{Q})}\mathcal{M}(f_{t}(x))$
is large, the model is also robust to the change in input.

######  Lemma 3 (Confidence guarantees robustness).

Under the conditions of Theorem 2, we have

$\displaystyle
R(f_{t})\leq\frac{1-\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P+Q)}\mathcal{M}(f_{t}(x))}{1-2L_{f}\xi}.$
(25)

###### Proof of Lemma 3.

We first note that when $\max_{y}\\{f_{t}(x)_{[y]}-\max_{y^{\prime}\neq
y}f_{t}(x)_{[y^{\prime}]}\\}>2L_{f}\xi$, the $\arg\max_{i}f_{t}(x)_{[i]}$ will
not change in the neighborhood $\mathcal{N}(x)$ since $f_{[i]}$ is
$L_{f}$-Lipschitz for all $i$. Suppose $y^{*}=\arg\max_{y}f_{t}(x)_{[y]}$. For
all $y^{\prime}\neq y^{*}$ and $x^{\prime}\in\mathcal{N}(x)$,

$\displaystyle f_{t}(x^{\prime})_{[y^{*}]}-f_{t}(x^{\prime})_{[y^{\prime}]}$
$\displaystyle>f_{t}(x)_{[y^{*}]}-L_{f}d(x,x^{\prime})-(f_{t}(x^{\prime})_{[y^{\prime}]}+L_{f}d(x,x^{\prime}))$
(26) $\displaystyle\geq\max_{y}\\{f_{t}(x)_{[y]}-\max_{y^{\prime}\neq
y}f_{t}(x)_{[y^{\prime}]}\\}-2L_{f}d(x,x^{\prime})$ (27) $\displaystyle\geq
0.$ (28)

Therefore, we have

$\displaystyle R(f_{t})$ $\displaystyle\leq
1-P_{\frac{1}{2}(P+Q)}\left(\mathcal{M}(f_{t}(x))>2L_{f}\xi\right)$ (29)
$\displaystyle\leq\frac{1-\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P+Q)}\mathcal{M}(f_{t}(x))}{1-2L_{f}\xi},$
(30)

where the second inequality holds because $f_{[i]}\in[0,1]$, and
$\mathcal{M}(f(x))\in[0,1]$. ∎

To obtain finite sample guarantee, we aim to show that each term in equation
13 is close to its population version. We first present Lemma 4, the classical
result for multi-class classification.

######  Lemma 4 (Lemma 3.1 of [41]).

Suppose $f\in\mathcal{F}$ and $\gamma>0$, with probability at least $1-\delta$
over the sampling of $\widehat{P}$, the following holds for all
$f\in\mathcal{F}$ simultaneously,

$\displaystyle\textup{Err}_{P}(f)\leq
L_{\widehat{P},\gamma}(f)+\frac{4K}{\gamma}\widehat{\mathcal{R}}(\cup\mathcal{F}_{[i]}|_{\widehat{P}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{s}}\right).$ (31)

We then extend Lemma 4 to study the finite sample properties of
$L_{\widehat{Q},\gamma}(f_{t},f_{s})$ and
$\mathrm{\mathbb{E}}\mathcal{M}(f_{t}(x))$.

######  Lemma 5.

Suppose $f\in\mathcal{F}$ and $\gamma>0$, with probability at least $1-\delta$
over the sampling of $\widehat{P}$, the following holds for all
$f\in\mathcal{F}$ simultaneously,

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim
P}\mathcal{M}(f(x))\leq\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{P}}\mathcal{M}(f(x))+4\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{s}}\right).$ (32)

###### Proof of Lemma 5.

By standard Rademacher complexity bound (Theorem 7 of Bartlett & Mendelson
[5]), we have

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim
P}\mathcal{M}(f(x))\leq\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{P}}\mathcal{M}(f(x))+2\widehat{\mathcal{R}}(\mathcal{M}\circ\mathcal{F}|_{\widehat{P}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{s}}\right).$ (33)

Thus it remains to show
$\widehat{\mathcal{R}}(\mathcal{M}\circ\mathcal{F}|_{\widehat{P}})\leq
2\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})$. In fact,

$\displaystyle\widehat{\mathcal{R}}(\mathcal{M}\circ\mathcal{F}|_{\widehat{P}})$
$\displaystyle=\frac{1}{n_{s}}\mathrm{\mathbb{E}}_{\sigma}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n_{s}}\sigma_{i}\max_{y}\\{f(x_{i})_{[y]}-\max_{y^{\prime}\neq
y}f(x_{i})_{[y^{\prime}]}\\}$
$\displaystyle=\frac{1}{n_{s}}\mathrm{\mathbb{E}}_{\sigma}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n_{s}}\sigma_{i}(\max_{y}f(x_{i})_{[y]}-\max_{y^{\prime}\neq\tilde{f}(x_{i})}f(x_{i})_{[y^{\prime}]})$
$\displaystyle\leq\frac{1}{n_{s}}\mathrm{\mathbb{E}}_{\sigma}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n_{s}}\sigma_{i}\max_{y}f(x_{i})_{[y]}+\frac{1}{n_{s}}\mathrm{\mathbb{E}}_{\sigma}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n_{s}}\sigma_{i}\max_{y^{\prime}\neq\tilde{f}(x_{i})}f(x)_{[y^{\prime}]}$
$\displaystyle=\widehat{\mathcal{R}}(\max_{i}\mathcal{F}_{[i]}|_{\widehat{P}})+\widehat{\mathcal{R}}(\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}|_{\widehat{P}}).$

As will be shown in Lemma 7, both
$\widehat{\mathcal{R}}(\max_{i}\mathcal{F}_{[i]}|_{\widehat{P}})$ and
$\widehat{\mathcal{R}}(\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}|_{\widehat{P}})$
are smaller than $\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})$, which
completes the proof. ∎

######  Lemma 6.

Suppose $f_{s},f_{t}\in\mathcal{F}$ and $\gamma>0$, with probability at least
$1-\delta$ over the sampling of $\widehat{Q}$, the following holds for all
$f_{s},f_{t}\in\mathcal{F}$ simultaneously,

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim Q}\mathbb{I}(f_{t}(x)\neq
f_{s}(x))\leq
L_{\widehat{Q},\gamma}(f_{t},f_{s})+\frac{2K}{\gamma}\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{t}}\right).$ (34)

###### Proof of Lemma 6.

By the definition of multi-class margin loss, we have
$\mathrm{\mathbb{E}}_{(x,y)\sim Q}\mathbb{I}(f_{t}(x)\neq f_{s}(x))\leq
L_{Q,\gamma}(f_{t},f_{s})$. Denote by $\mathcal{G}$ the set of
$\\{x\rightarrow(-\mathcal{M}(f_{t}(x),f_{s}(x))):f_{t},f_{s}\in\mathcal{F}\\}$.
By standard Rademacher complexity bound, we have,

$\displaystyle L_{Q,\gamma}(f_{t},f_{s})\leq
L_{\widehat{Q},\gamma}(f_{t},f_{s})+2\widehat{\mathcal{R}}(\psi_{\gamma}\circ\mathcal{G}|_{\widehat{Q}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{t}}\right).$

By Talagrand contraction Lemma [59],
$\widehat{\mathcal{R}}(\psi_{\gamma}\circ\mathcal{G}|_{\widehat{Q}})\leq\frac{1}{\gamma}\widehat{\mathcal{R}}(\mathcal{G}|_{\widehat{Q}})$.
Thus, it remains to show
$\widehat{\mathcal{R}}(\mathcal{G}|_{\widehat{Q}})\leq
K\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})$.
We have

$\displaystyle\widehat{\mathcal{R}}(\mathcal{G}|_{\widehat{Q}})$
$\displaystyle=\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\mathcal{M}(f_{t}(x_{i}),\tilde{f}_{s}(x_{i}))$
$\displaystyle=\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\left(f_{t}(x_{i})_{[\tilde{f}_{s}(x_{i})]}-\max_{y^{\prime}\neq\tilde{f}_{s}(x_{i})}f_{t}(x_{i})_{[y^{\prime}]}\right)$
$\displaystyle\leq\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}f_{t}(x_{i})_{[\tilde{f}_{s}(x_{i})]}+\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\max_{y^{\prime}\neq\tilde{f}_{s}(x_{i})}f_{t}(x_{i})_{[y^{\prime}]}$
$\displaystyle=\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})+\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\max_{y^{\prime}\neq\tilde{f}_{s}(x_{i})}f_{t}(x_{i})_{[y^{\prime}]}.$

It remains to show
$\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\max_{y^{\prime}\neq\tilde{f}_{s}(x_{i})}f_{t}(x_{i})_{[y^{\prime}]}\leq(K-1)\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})$,
which is done by noting the closure of $\mathcal{F}$ under the permutation of
coordinates. Consider the permutation
$\upsilon:\mathbb{R}^{K}\rightarrow\mathbb{R}^{K}$:
$\upsilon(v)_{[i]}=v_{[i-1]}$ for $i\in[2,3,\cdots K]$ and
$\upsilon(v)_{[1]}=v_{[K]}$.

$\displaystyle\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\max_{y^{\prime}\neq\tilde{f}_{s}(x_{i})}f_{t}(x_{i})_{[y^{\prime}]}=\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\max_{k\in[K-1]}\upsilon^{k}f_{t}(x_{i})_{[\tilde{f}_{s}(x_{i})]}.$

We have $\upsilon\mathcal{F}\subset\mathcal{F}$ by the closure of
$\mathcal{F}$. Thus,
$\tilde{\mathcal{F}}\times\upsilon\mathcal{F}\subset\tilde{\mathcal{F}}\times\mathcal{F}$.
By Lemma 7, the Rademacher complexity of maximum of function classes is
bounded with their sum, so we have
$\frac{1}{n_{t}}\mathrm{\mathbb{E}}_{\sigma_{i}}\sup_{f_{s},f_{t}}\sum_{i=1}^{n_{t}}\sigma_{i}\max_{k\in[K-1]}\upsilon^{k}f_{t}(x_{i})_{[\tilde{f}_{s}(x_{i})]}\leq(K-1)\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})$.
∎

The next lemma shows the relationship between function classes. We establish
the Rademacher complexity bounds of $\cup\mathcal{F}_{[i]}$,
$\max_{i}\mathcal{F}_{[i]}$, and
$\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}$. We show
that the Rademacher complexity of these function classes can be bounded with
$\widehat{\mathcal{R}}(\mathcal{F}|_{S})=\sum_{i=1}^{K}\widehat{\mathcal{R}}(\mathcal{F}_{[i]}|_{S})$.

######  Lemma 7.

Suppose $\max_{i}\mathcal{F}_{[i]}=\\{\max_{i}f_{[i]}:f\in\mathcal{F}\\}$,
$\cup\mathcal{F}_{[i]}=\\{f_{[i]}:f\in\mathcal{F},i\in[K]\\}$, and
$\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}=\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}|_{\widehat{P}}=\\{x\rightarrow\max_{i\neq\tilde{f}(x)}f_{[i]}(x):f\in\mathcal{F}\\}$.

$\displaystyle\widehat{\mathcal{R}}(\cup\mathcal{F}_{[i]}|_{S})\leq\widehat{\mathcal{R}}(\mathcal{F}|_{S}),\
\widehat{\mathcal{R}}(\max_{i}\mathcal{F}_{[i]}|_{S})\leq\widehat{\mathcal{R}}(\mathcal{F}|_{S})\quad\text{and}\quad\widehat{\mathcal{R}}(\max_{i^{\prime}\neq\tilde{\mathcal{F}}}\mathcal{F}_{[i^{\prime}]}|_{S})\leq\widehat{\mathcal{R}}(\mathcal{F}|_{S}).$
(35)

###### Proof of Lemma 7.

Consider the $K=2$ case. Then we can repeat the arguments for $K-1$ times to
get the final results.

For the first inequality, consider
$\mathcal{F}_{[i]}^{\prime}:=\mathcal{F}_{[i]}\cup-\mathcal{F}_{[i]}=\\{x\rightarrow\pm
f(x):f\in\mathcal{F}_{[i]}\\}$. Then we have

$\displaystyle\widehat{\mathcal{R}}(\mathcal{F}_{[1]}\cup\mathcal{F}_{[2]}|_{S})$
$\displaystyle=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[i]}\in\mathcal{F}_{[1]}\cup\mathcal{F}_{[2]}}\sum_{j=1}^{n}\sigma_{j}f_{[i]}(x_{j})$
(36)
$\displaystyle=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[i]}^{\prime}\in\mathcal{F}^{\prime}_{[1]}\cup\mathcal{F}_{[2]}^{\prime}}\sum_{j=1}^{n}\left|\sigma_{j}f_{[i]}^{\prime}(x_{j})\right|$
(37)
$\displaystyle\leq\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[i]}^{\prime}\in\mathcal{F}^{\prime}_{[1]}}\sum_{j=1}^{n}\left|\sigma_{j}f_{[i]}^{\prime}(x_{j})\right|+\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[i]}^{\prime}\in\mathcal{F}^{\prime}_{[2]}}\sum_{j=1}^{n}\left|\sigma_{j}f_{[i]}^{\prime}(x_{j})\right|$
(38)
$\displaystyle=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[i]}\in\mathcal{F}_{[1]}}\sum_{j=1}^{n}\sigma_{j}f_{[i]}(x_{j})+\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[i]}\in\mathcal{F}_{[2]}}\sum_{j=1}^{n}\sigma_{j}f_{[i]}(x_{j})$
(39)
$\displaystyle=\widehat{\mathcal{R}}(\mathcal{F}_{[1]}|_{S})+\widehat{\mathcal{R}}(\mathcal{F}_{[2]}|_{S}),$
(40)

where equation equation 37 and equation 39 hold by the definition of
$\mathcal{F}_{[i]}$.

For the second inequality, note that
$\max\\{x,y\\}=\frac{x+y}{2}+\frac{|x-y|}{2}$. Then we apply Talagrand
contraction lemma for the absolute value ($|\cdot|$ is $1$-Lipschitz),

$\displaystyle\widehat{\mathcal{R}}(\max_{i}\mathcal{F}_{[i]}|_{S})$
$\displaystyle=\frac{1}{n}\mathrm{\mathbb{E}}_{\sigma_{j}}\sup_{f_{[1]}\in\mathcal{F}_{[1]},f_{[2]}\in\mathcal{F}_{[2]}}\sum_{j=1}^{n}\sigma_{j}\left(\frac{f_{[1]}(x_{j})+f_{[2]}(x_{j})}{2}+\frac{|f_{[1]}(x_{j})-f_{[2]}(x_{j})|}{2}\right)$
$\displaystyle\leq\frac{1}{2}\widehat{\mathcal{R}}(\mathcal{F}_{[1]}|_{S})+\frac{1}{2}\widehat{\mathcal{R}}(\mathcal{F}_{[2]}|_{S})+\frac{1}{2}\widehat{\mathcal{R}}(|\mathcal{F}_{[1]}-\mathcal{F}_{[2]}||_{S})$
$\displaystyle\leq\frac{1}{2}\widehat{\mathcal{R}}(\mathcal{F}_{[1]}|_{S})+\frac{1}{2}\widehat{\mathcal{R}}(\mathcal{F}_{[2]}|_{S})+\frac{1}{2}\widehat{\mathcal{R}}(\mathcal{F}_{[1]}-\mathcal{F}_{[2]}|_{S})$
$\displaystyle\leq\widehat{\mathcal{R}}(\mathcal{F}_{[1]}|_{S})+\widehat{\mathcal{R}}(\mathcal{F}_{[2]}|_{S}).$

For the third inequality, observe that the second largest of the set
$\\{x,y,z\\}$ can be expressed as
$\max\\{\min\\{x,y\\},\min\\{\max\\{x,y\\},z\\}\\}$. Following argument
similar to the second inequality gives the proof. ∎

Now equipped with the lemmas above, we are ready to prove Theorem 2.

###### Proof of Theorem 2.

By Lemmas 4, 5, and 6, we have the following inequalities hold with
probability larger than $1-\frac{\delta}{3}$,

$\displaystyle\textup{Err}_{P}(f)\leq
L_{\widehat{P},\gamma}(f)+\frac{4K}{\gamma}\widehat{\mathcal{R}}(\cup\mathcal{F}_{[i]}|_{\widehat{P}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{s}}\right).$ (41)
$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P+Q)}\mathcal{M}(f(x))$
$\displaystyle\leq\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(\widehat{P}+\widehat{Q})}\mathcal{M}(f(x))+2\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{P}})+2\widehat{\mathcal{R}}(\mathcal{F}|_{\widehat{Q}})$
(42) $\displaystyle+O\left(\sqrt{\textup{log}(1/\delta)\ /\
n_{s}}+\sqrt{\textup{log}(1/\delta)\ /\ n_{t}}\right).$
$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim Q}\mathbb{I}(f_{t}(x)\neq
f_{s}(x))\leq
L_{\widehat{Q},\gamma}(f_{t},f_{s})+\frac{2K}{\gamma}\widehat{\mathcal{R}}(\tilde{\mathcal{F}}\times\mathcal{F}|_{\widehat{Q}})+O\left(\sqrt{\textup{log}(1/\delta)\
/\ n_{t}}\right).$ (43)

We also have the following due to Lemma 3,

$\displaystyle
R(f_{t})\leq\frac{1-\mathrm{\mathbb{E}}_{(x,y)\sim\frac{1}{2}(P+Q)}\mathcal{M}(f_{t}(x))}{1-2L_{f}\xi}.$
(44)

We use equation 42 and equation 43 as conditions. Plugging equation 41,
equation 42, equation 43, and equation 44 into Theorem 1 and applying a union
bound complete the proof of Theorem 2. ∎

###  A.3 Details in Section 4.2

We instantiate the domain adaptation setting in a quadratic neural network
that allows us to compare various properties of the related algorithms. For a
specific data distribution, we prove that (1) cycle self-training recovers
target ground truth, and (2) both feature adaptation and standard self-
training fail on the same distribution.

####  A.3.1 Setup

We study a quadratic neural network composed of a feature extractor
$\phi\in\mathbb{R}^{d\times m}$ and a head $\theta\in\mathbb{R}^{m}$.
$f_{\theta,\phi}(x)=g_{\theta}(h_{\phi}(x))$, where
$g_{\theta}(z)=\theta^{\top}z$ and
$h_{\phi}(x)=(\phi^{\top}x)\odot(\phi^{\top}x)$, $\odot$ is element-wise
product. In training, we use the squared loss $\ell(f(x),y)=(f(x)-y)^{2}$. In
testing, we map $f(x)$ to the nearest point in the output space:
$\tilde{f}(x):=\mathop{\arg\min}_{y\in\\{-1,0,1\\}}|y-f(x)|$. Denote the
expected error by $\text{Err}_{Q}(\theta,\phi):=\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(\tilde{f}_{\theta,\phi}(x)\neq y)$.

Structural Covariate Shift and Label Shift. In domain adaptation, the source
domain can have multiple solutions but we aim to learn the solution which
works on the target domain [34]. Recent works also pointed out the source and
the target label distributions are often different in real-world applications
[74]. Following these properties, we design the underlying distributions $p$
and $q$ as shown in Table 6 to allow both structural covariate shift and label
shift.

Table 6: Comparison of the design of the source and target. Distribution | $-1$ | $+1$ | $0$
---|---|---|---
Source $p$ | $\quad 0.05\quad$ | $\quad 0.05\quad$ | $\quad 0.90\quad$
Target $q$ | $\quad 0.25\quad$ | $\quad 0.25\quad$ | $\quad 0.50\quad$

We study the following source distribution $P$. $x_{[1]}$ and $x_{[2]}$ are
sampled _i.i.d._ from distribution $p$, and for $i\in[3,d]$,
$x_{[i]}=\sigma_{i}\times x_{[2]}$. $\sigma_{i}\in\\{\pm 1\\}$ uniformly. In
the target domain, $x_{[1]}$ and $x_{[2]}$ are sampled _i.i.d._ from
distribution $q$, and for $i\in[3,d]$, $x_{[i]}=\sigma_{i}\times x_{[1]}$.
$\sigma_{i}\in\\{\pm 1\\}$ uniformly. We also assume realizability:
$y=x_{[1]}^{2}-x_{[2]}^{2}$ for both source and target. For simplicity, we
assume access to infinite _i.i.d._ examples of $P$ ($n_{s}=\infty$) and
$n_{t}$ _i.i.d._ examples of $Q$. Therefore, the empirical loss and the
population loss on the source domain are the same $L_{P}=L_{\widehat{P}}$.

Note that since $x_{[i]}^{2}=x_{[2]}^{2}$ for all $i\in[3,d]$ in the source
domain, $y=x_{[1]}^{2}-x_{[i]}^{2}$ for all $i\in[2,d]$ are solutions to the
source domain but only $y=x_{[1]}^{2}-x_{[2]}^{2}$ works on the target domain.
We visualize the setting when $d=3$ in Figure 4.

####  A.3.2 Algorithms

We compare the baseline algorithms (feature adaptation and self-training) in
Section 2 with the proposed CST. We study the norm-constrained versions of
these algorithms.

Feature Adaptation chooses the source solution minimizing the distance between
source and target feature distributions. We use total variation (TV) distance
[7]:
$d_{\textup{TV}}(h_{\sharp}{\widehat{P}},h_{\sharp}{\widehat{Q}})=\mathop{\sup}_{E\subset\mathcal{Z}}|h_{\sharp}{\widehat{P}}(E)-h_{\sharp}{\widehat{Q}}(E)|$.

$\displaystyle\hat{\theta}_{\textup{FA}},\hat{\phi}_{\textup{FA}}=\mathop{\arg\min}_{\hat{\theta}_{s},\hat{\phi}_{s}}\
d_{\textup{TV}}(h_{\sharp}{\widehat{P}},h_{\sharp}{\widehat{Q}}),$ (45)
$\displaystyle\textup{s.t.}\ \hat{\theta}_{s},\hat{\phi}_{s}$
$\displaystyle=\mathop{\arg\min}_{\theta,\phi}\|\theta\|_{2}^{2}+\|\phi\|_{F}^{2},\
\textup{s.t.}\ L_{P}(\theta,\phi)=0.$

Standard Self-Training first trains a source model,

$\displaystyle\hat{\theta}_{s},\hat{\phi}_{s}=\mathop{\arg\min}_{\theta,\phi}\|\theta\|_{2}^{2}+\|\phi\|_{F}^{2},\
\textup{s.t.}\ L_{P}(\theta,\phi)=0.$ (46)

Then it trains the model on the source and target datasets jointly with source
ground-truths and target pseudo-labels,

$\displaystyle\hat{\theta}_{\textup{ST}},\hat{\phi}_{\textup{ST}}=\mathop{\arg\min}_{\theta,\phi}\|\theta\|_{2}^{2}+\|\phi\|_{F}^{2},$
(47) $\displaystyle\textup{s.t.}\ L_{P}$
$\displaystyle(\theta,\phi)+\mathrm{\mathbb{E}}_{x\sim\widehat{Q}}\ell(f_{\theta,\phi}(x),f_{\hat{\theta}_{s},\hat{\phi}_{s}}(x))=0.$

Cycle Self-Training. Following Section 3.1, we train the source head
$\theta_{s}$, and then train another head $\hat{\theta}_{t}(\phi)$ on the
target dataset $\widehat{Q}$ with pseudo-labels generated by $\theta_{s}$:

$\displaystyle\hat{\theta}_{t}(\phi)=\mathop{\arg\min}_{\theta}\|\theta\|_{2}^{2},\
\text{s.t.}\
\mathrm{\mathbb{E}}_{x\in\widehat{Q}}\ell(f_{\theta,\phi}(x),f_{\theta_{s},\phi}(x))=0.$

Finally we update the feature extractor $\phi$ to enforce consistent
predictions of $\hat{\theta}_{t}(\phi)$ and $\theta_{s}$ on the source
dataset:

$\displaystyle\hat{\theta}_{\textup{CST}},\hat{\phi}_{\textup{CST}}=\mathop{\arg\min}_{\theta_{s},\phi}\|\theta_{s}\|_{2}^{2}+\|\phi\|_{F}^{2},$
(48) $\displaystyle\textup{s.t.}\ L_{P}(\theta_{s}$
$\displaystyle,\phi)+\mathrm{\mathbb{E}}_{x\in
P}\ell(g_{\theta_{s}}(h_{\phi}(x)),g_{\hat{\theta}_{t}(\phi)}(h_{\phi}(x)))=0.$

The following theorems show that both feature adaptation and standard self-
training fail. The intuition is that the _ideal_ solution that works on both
source and target $y=x_{[1]}^{2}-x_{[2]}^{2}$ has larger distance
$d_{\textup{TV}}$ in the feature space than other solutions
$y=x_{[1]}^{2}-x_{[i]}^{2}$, so feature adaptation will not prefer the ideal
solution. Standard self-training also fails because it will choose randomly
among $y=x_{[1]}^{2}-x_{[i]}^{2}$.

######  Theorem 3.

For any $\epsilon\in(0,0.5)$, the following statements are true for feature
adaptation and standard self-training:

  * •

For any failure rate $\xi>0$, and target dataset of size
${n_{t}}>\Theta(\log\frac{1}{\xi})$, with probability at least $1-\xi$ over
the sampling of target data, the source solution
$\hat{\theta}_{\textup{FA}},\hat{\phi}_{\textup{FA}}$ found by feature
adaptation fails on the target domain:

$\displaystyle\textup{Err}_{Q}(\hat{\theta}_{\textup{FA}},\hat{\phi}_{\textup{FA}})\geq\epsilon.$
(49)

  * •

With probability at least $1-\frac{1}{d-1}$ over the training the source
solution, the solution $(\hat{\theta}_{\textup{ST}},\hat{\phi}_{\textup{ST}})$
of standard self-training satisfies

$\displaystyle\textup{Err}_{Q}(\hat{\theta}_{\textup{ST}},\hat{\phi}_{\textup{ST}})\geq\epsilon.$
(50)

In comparison, we show that CST can recover the ground truth with high
probability.

######  Theorem 4.

For any failure rate $\xi>0$, and target dataset of size
${n_{t}}>\Theta(\log\frac{1}{\xi})$, with probability at least $1-\xi$ over
the sampling of target data, the feature extractor $\hat{\phi}_{\textup{CST}}$
found by CST and the head $\hat{\theta}_{\textup{CST}}$ recovers the ground
truth of the target dataset:

$\displaystyle\textup{Err}_{Q}(\hat{\theta}_{\textup{CST}},\hat{\phi}_{\textup{CST}})=0.$
(51)

Intuitively, CST successfully learns the _transferable feature_
$x_{[1]}^{2}-x_{[2]}^{2}$ because it enforces the generalization of the head
$\hat{\theta}_{t}(\phi)$ on the source data.

###  A.4 Proof of Theorem 3

We first describe the insights of the proof. As shown in Lemma 8, every source
solution can be categorized into $d-1$ classes according to the coordinate $l$
of the learned weight $\phi$. Among those $d-1$ classes, only $l=2$ works on
the target domain and $l\in\\{3,\cdots d\\}$ do not work on the target. We
then show that in feature adaptation, $l\in\\{3,\cdots d\\}$ results in
smaller distance between source and target feature distributions as a result
of Lemma 9, thus feature adaptation will choose $l\in\\{3,\cdots d\\}$. On the
other hand, standard self-training with randomly select $l$ in the possible
$d-1$ choices, but only $l=2$ works.

######  Lemma 8.

Under the condition of Section 4, any solution $\theta,\phi$ to the Source
Only problem

$\displaystyle\mathop{\min}_{\theta,\phi}\|\theta\|_{2}^{2}+\|\phi\|_{F}^{2},\
\textup{s.t.}\ L_{P}(\theta,\phi)=0.$ (52)

must have the following form: $\exists i,j\in\\{2,3,\cdots m\\},\
l\in\\{2,3,\cdots d\\},\ \phi_{i}=2^{\frac{1}{6}}e_{1},\
\phi_{j}=2^{\frac{1}{6}}e_{l},\ \phi_{k}=0$ for $k\neq i,j$, and
$\theta_{i}=\theta_{j}=2^{-\frac{1}{3}},\ \theta_{k}=0$ for $k\neq i,j$.

###### Proof of Lemma 8.

Define the symmetric matrix
$A=\sum_{i=1}^{m}\theta_{i}\phi_{i}\phi_{i}^{\top}$, then the networks can be
represented by $A$: $f_{\theta,\phi}(x)=x^{\top}Ax$. We show that $A_{ij}=0$
for $i\neq j$ if $f_{\theta,\phi}$ recovers source ground truth.

First, for $i,j>1$, let $x_{1}=\mathbf{1}$, $x_{2}=\mathbf{1}-2e_{i}-2e_{j}$,
$x_{3}=\mathbf{1}-2e_{i}$, and $x_{4}=\mathbf{1}-2e_{j}$, where $\\{e_{i}\\}$
are the standard bases. Since the source ground truth
$y=x_{[1]}^{2}-x_{[2]}^{2}$, and $x_{[k]}=\pm 1x_{[2]}$ for $k\in\\{3,4,\cdots
d\\}$, $y_{1}=y_{2}=y_{3}=y_{4}$.

$\displaystyle y_{1}+y_{2}+y_{3}-y_{4}=$ $\displaystyle
x_{1}^{\top}Ax_{1}+x_{2}^{\top}Ax_{2}-x_{3}^{\top}Ax_{3}-x_{4}^{\top}Ax_{4}$
(53) $\displaystyle=$ $\displaystyle
2\mathbf{1}^{\top}A\mathbf{1}+4A_{ii}+4A_{jj}-4\mathbf{1}^{\top}Ae_{i}-4\mathbf{1}^{\top}Ae_{j}+8A_{ij}$
(54)
$\displaystyle-(\mathbf{1}^{\top}A\mathbf{1}+4A_{ii}+4A_{jj}-4\mathbf{1}^{\top}Ae_{i}-4\mathbf{1}^{\top}Ae_{j})$
(55) $\displaystyle=$ $\displaystyle 8A_{ij}=0.$ (56)

We then show $A_{1,j}=0$ for $j\in\\{2,3,\cdots d\\}$ using the fact that
$y_{1}=y_{4}$.

$\displaystyle y_{1}-y_{4}=$ $\displaystyle
x_{1}^{\top}Ax_{1}-x_{4}^{\top}Ax_{4}$ (57) $\displaystyle=$
$\displaystyle\mathbf{1}^{\top}A\mathbf{1}-(\mathbf{1}^{\top}A\mathbf{1}-4\mathbf{1}^{\top}Ae_{j}+4A_{jj})$
(58) $\displaystyle=$ $\displaystyle 4\mathbf{1}^{\top}Ae_{j}-4A_{jj}$ (59)
$\displaystyle=$ $\displaystyle 0.$ (60)

From equation 56 we know $A_{ij}=0$ if $i\neq 1$. Then we also have
$A_{1j}=A_{j1}=0$. Therefore we can write $y$ in the following form:
$y=x^{\top}Ax=\sum_{i=1}^{d}A_{ii}x_{[i]}^{2}$ We also have the source ground
truth $y=x_{[1]}^{2}-x_{[2]}^{2}$, and $x_{[k]}=\pm 1x_{[2]}$ for
$k\in\\{3,4,\cdots d\\}$. Then $A$ must satisfy $A_{11}=1$,
$\sum_{i=2}^{d}A_{ii}=-1$, and all other entries of $A$ equals to $0$.

We have found the form of source ground truth matrix $A$. It suffices to show
that the minimal norm solution of $\theta$ and $\phi$ subject to the form of
$A$ must be in the form of Lemma 8.

$\displaystyle\|\theta\|_{2}^{2}+\|\phi\|_{F}^{2}=$
$\displaystyle\sum_{i}^{m}\theta_{i}^{2}+\frac{1}{2}\|\phi_{i}\|_{2}^{2}+\frac{1}{2}\|\phi_{i}\|_{2}^{2}$
(61) $\displaystyle\geq$ $\displaystyle\sum_{i}^{m}3\cdot
2^{\frac{2}{3}}\left(|\theta_{i}|\|\phi_{i}\|_{2}^{2}\right)^{\frac{2}{3}}$
(62) $\displaystyle\geq$ $\displaystyle 3\cdot
2^{\frac{2}{3}}\left(\sum_{i:\theta_{i}>0}\theta_{i}\|\phi_{i}\|_{2}^{2}\right)^{\frac{2}{3}}+3\cdot
2^{\frac{2}{3}}\left(\sum_{i:\theta_{i}\leq
0}-\theta_{i}\|\phi_{i}\|_{2}^{2}\right)^{\frac{2}{3}}$ (63) $\displaystyle=$
$\displaystyle 3\cdot
2^{\frac{2}{3}}\left(\sum_{i:A_{ii}>0}A_{ii}\right)^{\frac{2}{3}}+3\cdot
2^{\frac{2}{3}}\left(\sum_{i:A_{ii}\leq 0}-A_{ii}\right)^{\frac{2}{3}}=3\cdot
2^{\frac{5}{3}}.$ (64)

The first inequality holds due to AM-GM inequality, where it takes equality
iff $\theta_{i}^{2}=\frac{1}{2}\|\phi_{i}\|_{2}^{2}$ for all $i$. The second
inequality holds due to Jensen inequality. The situation where both inequality
take equality is exactly the form of Lemma 8. ∎

######  Lemma 9.

Suppose $\widehat{Q}=\\{x_{i}^{t}\\}_{i=1}^{n_{t}}$ are i.i.d. samples from
target distribution $Q$, then with high probability,
$\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)$ is close to
$0.5$:

$\displaystyle
P\left(\left|\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)-0.5\right|>t\right)\leq
e^{-2n_{t}t^{2}}$ (65)

###### Proof of Lemma 9.

Since each coordinate of $x$ follows $q$, $\mathbb{I}(x_{[l]}=0)-0.5$ is a
sub-Gaussian variable with $\sigma=0.5$. We then apply standard Hoeffding’s
inequality to complete the proof. ∎

###### Proof of Theorem 3.

We have the conclusion of Lemma 8. For simplicity we suppose without loss of
generality that the source solution has the following form: $\exists\
l\in\\{2,3,\cdots d\\},\ \phi_{1}=2^{\frac{1}{6}}e_{1},\
\phi_{2}=2^{\frac{1}{6}}e_{l},\ \phi_{k}=0$ for $k\in\\{3,\cdots m\\}$, and
$\theta_{1}=\theta_{2}=2^{-\frac{1}{3}},\ \theta_{k}=0$ for $k\in\\{3,\cdots
m\\}$. Then these solutions can be categorized into two classes: (1) When
$l=2$, the source solution also works on the target, i.e.
$L_{Q}(\theta,\phi)=0$. (2) When $l\in\\{3,\cdots d\\}$, the source solution
does not work on the target,

$\displaystyle\textup{Err}_{Q}(\theta,\phi)$
$\displaystyle=1-\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(f_{\theta,\phi}(x)=y)$ (66)
$\displaystyle=1-\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(x_{[l]}^{2}=x_{[2]}^{2})$ (67)
$\displaystyle=1-\mathrm{\mathbb{E}}_{(x,y)\sim Q}\mathbb{I}(x_{[l]}=0\
\textup{and}\ x_{[2]}=0)-\mathrm{\mathbb{E}}_{(x,y)\sim
Q}\mathbb{I}(x_{[l]}\neq 0\ \textup{and}\ x_{[2]}\neq 0)$ (68)
$\displaystyle=0.5$ (69)

To prove that feature adaptation learns the solution that does not work on the
target domain, we show that with high probability, the solution belonging to
situation (1) has larger total variation between source and target feature
distributions $h_{\sharp}P$ and $h_{\sharp}\widehat{Q}$. In fact, the
distributions of $h_{\sharp}P$ are the same for solutions in situation (1) and
situation (2):

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim
P}\left(h_{\phi}(x)=(z_{1},z_{2})\right)=\left\\{\begin{array}[]{lr}0.81,&(z_{1},z_{2})=2^{\frac{1}{3}}(0,0)\\\
0.09,&(z_{1},z_{2})=2^{\frac{1}{3}}(0,1)\\\
0.09,&(z_{1},z_{2})=2^{\frac{1}{3}}(1,0)\\\
0.01,&(z_{1},z_{2})=2^{\frac{1}{3}}(1,1)\end{array}\right.$

For the target dataset, the distribution of features is different for
solutions from situation (1) and situation (2). When $l=2$, denote by
$h_{1\sharp}\widehat{Q}$ the feature distribution.

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\left(h_{\phi}(x)=(z_{1},z_{2})\right)=\left\\{\begin{array}[]{lr}\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}^{2}\mathbb{I}(x_{[l]}=0),&(z_{1},z_{2})=2^{\frac{1}{3}}(0,0)\\\
\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}\neq
0),&(z_{1},z_{2})=2^{\frac{1}{3}}(0,1)\\\
\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}\neq
0),&(z_{1},z_{2})=2^{\frac{1}{3}}(1,0)\\\
\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}^{2}\mathbb{I}(x_{[l]}\neq
0),&(z_{1},z_{2})=2^{\frac{1}{3}}(1,1)\end{array}\right.$

When $l\in\\{3,\cdots d\\}$, denote by $h_{2\sharp}\widehat{Q}$ the feature
distribution. since $x_{[l]}=x_{[1]}$ in the target domain, $(z_{1},z_{2})$
can only be $2^{\frac{1}{3}}(0,0)$ or $2^{\frac{1}{3}}(1,1)$,

$\displaystyle\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\left(h_{\phi}(x)=(z_{1},z_{2})\right)=\left\\{\begin{array}[]{lr}\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0),&(z_{1},z_{2})=2^{\frac{1}{3}}(0,0)\\\
\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}\neq
0),&(z_{1},z_{2})=2^{\frac{1}{3}}(1,1)\end{array}\right.$

We then instantiate Lemma 9 with $t=0.14$: With probability at least
$1-\delta$,
$0.36<\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)<0.64$
for any $n_{t}\geq C\textup{log}\left(\frac{1}{\delta}\right)$, where $C>26$
is a constant. Finally, we show that
$d_{\textup{TV}}(h_{\sharp}P,h_{2\sharp}\widehat{Q})<d_{\textup{TV}}(h_{\sharp}P,h_{1\sharp}\widehat{Q})$
as long as
$0.36<\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)<0.64$ to
prove that feature adaptation will select solutions in situation (2).

$\displaystyle d_{\textup{TV}}(h_{\sharp}P,h_{1\sharp}\widehat{Q})=$
$\displaystyle\frac{1}{2}\left|\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}^{2}\mathbb{I}(x_{[l]}=0)-0.81\right|+\frac{1}{2}\left|\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}^{2}\mathbb{I}(x_{[l]}\neq
0)-0.01\right|$ (70)
$\displaystyle+\left|\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}\neq
0)-0.09\right|$ (71) $\displaystyle=$ $\displaystyle
0.81-\mathrm{\mathbb{E}}^{2}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)$ (72)
$\displaystyle>$ $\displaystyle
0.9-\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)$ (73)
$\displaystyle=$
$\displaystyle\frac{1}{2}\left|\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)-0.81\right|+\frac{1}{2}\left|\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}\neq
0)-0.01\right|$ (74) $\displaystyle=$ $\displaystyle
d_{\textup{TV}}(h_{\sharp}P,h_{2\sharp}\widehat{Q}),$ (75)

when
$0.36<\mathrm{\mathbb{E}}_{(x,y)\sim\widehat{Q}}\mathbb{I}(x_{[l]}=0)<0.64$,
which completes the proof of feature adaptation.

In standard self-training, when training the source solution, the probability
of $l$ equalling each value in $\\{2,3,\cdots d\\}$ is the same, but only
$l=2$ is the solution working on the source domain. Then when training on the
source ground truth and target pseudo-labels, the model will make $l$
unchanged. Thus the probability of recovering the target ground truth is only
$\frac{1}{d-1}$. ∎

###  A.5 Proof of Theorem 4

Similar to the proof of Theorem 3, we use the conclusion of Lemma 8 to show
that $l=2$ indicates the source solution that works on the target domain,
while the solutions corresponding to $l\in\\{3,\cdots d\\}$ will have large
error on the target domain. Then we show that only $l=2$ makes the training
objective of cycle self-training $L_{\textup{CST}}=0$. This is due to the fact
that $l=2$ will make the spans of source and target features identical, while
$l\in\\{3,\cdots d\\}$ makes the spans of source and target features different
and thus $\hat{\theta}_{t}(\phi)\neq\theta_{s}$.

###### Proof of Theorem 4.

We still use Lemma 8. To prove that cycle self-training recovers the target
ground truth, it suffices to show that $\mathrm{\mathbb{E}}_{x\in
P}\ell(g_{\theta_{s}}(h_{\phi}(x)),g_{\hat{\theta}_{t}(\phi)}(h_{\phi}(x)))=0$
when $l=2$, and $\mathrm{\mathbb{E}}_{x\in
P}\ell(g_{\theta_{s}}(h_{\phi}(x)),g_{\hat{\theta}_{t}(\phi)}(h_{\phi}(x)))\neq
0$ when $l\in\\{3,\cdots d\\}$.

When $l\in\\{3,\cdots d\\}$, since $x_{[1]}^{2}=x_{[l]}^{2}$ in the target
domain, the target pseudo-labels are all $0$. Then we solve the problem
$\hat{\theta}_{t}(\phi)=\mathop{\arg\min}_{\theta}\|\theta\|_{2}^{2},\
\text{s.t.}\
\mathrm{\mathbb{E}}_{x\in\widehat{Q}}\ell(f_{\theta_{s},\phi}(x),f_{\theta,\phi}(x))$
to get the target classifier $\hat{\theta}_{t}(\phi)$. Since we want the
target solution with minimal norm, $\hat{\theta}_{t}(\phi)=0$, and we can
calculate $L_{\textup{CST}}$ as follows:

$\displaystyle\mathrm{\mathbb{E}}_{x\in
P}\ell(g_{\theta_{s}}(h_{\phi}(x)),g_{\hat{\theta}_{t}(\phi)}(h_{\phi}(x)))=\mathrm{\mathbb{E}}_{(x,y)\sim
P}(y-f_{\hat{\theta}_{t}(\phi),\phi}(x))^{2}=\mathrm{\mathbb{E}}_{(x,y)\sim
P}y^{2}=0.18.$ (76)

When $l=2$, we show that
$2^{\frac{1}{3}}e_{1}+2^{\frac{1}{3}}e_{2},2^{\frac{1}{3}}e_{1},2^{\frac{1}{3}}e_{2}$
and $0$ all appear in the target feature set with high probability. The
probability that the target feature set does not contain each one in
$2^{\frac{1}{3}}e_{1}+2^{\frac{1}{3}}e_{2},2^{\frac{1}{3}}e_{1},2^{\frac{1}{3}}e_{2}$
and $0$ equals to $\left(\frac{3}{4}\right)^{n_{t}}$. Therefore with a union
bound we can show that
$2^{\frac{1}{3}}e_{1}+2^{\frac{1}{3}}e_{2},2^{\frac{1}{3}}e_{1},2^{\frac{1}{3}}e_{2}$
and $0$ all appear in the target feature set with probability at least
$1-4\left(\frac{3}{4}\right)^{n_{t}}$. In this case,
$\hat{\theta}_{t}(\phi)=\mathop{\arg\min}_{\theta}\|\theta\|_{2}^{2},\
\text{s.t.}\
\mathrm{\mathbb{E}}_{x\in\widehat{Q}}\ell(f_{\theta_{s},\phi}(x),f_{\theta,\phi}(x))$
results in $\hat{\theta}_{t}(\phi)=\theta_{s}$, which means if
${n_{t}}>\Theta(\log\frac{1}{\xi})$, with probability at least $1-\xi$ over
the sampling of target data,

$\displaystyle L_{\textup{CST}}=\mathrm{\mathbb{E}}_{x\in
P}\ell(g_{\theta_{s}}(h_{\phi}(x)),g_{\hat{\theta}_{t}(\phi)}(h_{\phi}(x)))=0.$
(77)

∎

##  Appendix B Implementation Details

We use PyTorch [44] and run each experiment with 2080Ti GPUs. CBST, KLD, and
IA results are from their original papers. We use the highest results in the
literature for DANN, MCD, CDAN, and MDD. VAT, FixMatch, MixMatch and DIRT-T
are adapted to our datasets from the official code. We adopt the pre-trained
ResNet models provided in torchvision. For BERT implementation, we use the
official checkpoint and PyTorch code from
https://github.com/huggingface/transformers.

###  B.1 Dataset Details

OfficeHome [64] https://www.hemanthdv.org/officeHomeDataset.html is an object
recognition dataset which contains images from 4 domains. It has about 15500
images organized into 65 categories. The dataset was collected using a python
web-crawler that crawled through several search engines and online image
directories. The authors provided a Fair Use Notice on their website.

VisDA-2017 [45]
https://github.com/VisionLearningGroup/taskcv-2017-public/tree/master/classification
uses synthetic object images rendered from CAD models as the training domain
and real object images cropped from the COCO dataset as the validation domain.
The authors provided a Term of Use on the website.

DomainNet [46] http://ai.bu.edu/M3SDA/#dataset contains images from clipart,
infograph, painting, real, and sketch domains collected by searching a
category name combined with a domain name from searching engines. The authors
provided a Fair Use Notice on their website.

Amazon Review [10] https://www.cs.jhu.edu/~mdredze/datasets/sentiment/
contains product reviews taken from Amazon.com from many product types
(domains). Some domains (books and dvds) have hundreds of thousands of
reviews. Others (musical instruments) have only a few hundred. Reviews contain
star ratings (1 to 5 stars) that can be converted into binary labels if
needed.

###  B.2 Bi-level Optimization

In Section 3.1, we highlight that the optimization of CST involves bi-level
optimization. In the inner loop (equation 4), we train the target classifier
$\theta_{t}(\phi)$ on top of the shared representations $\phi$, thus
$\theta_{t}(\phi)$ is a function of $\phi$. Moreover, the target classifier
$\theta_{t}(\phi)$ is trained with target pseudo-labels $y^{\prime}$, which
are the sharpened version of the outputs of the source classifier $\theta_{s}$
on top of the shared representations $\phi$. In this sense, $\theta_{t}(\phi)$
relies on $\theta_{s}$ and $\phi$ through $y^{\prime}$ implicitly, too. In the
outer loop (equation 5), we update the shared representations $\phi$ and the
source classifier $\theta_{s}$ to make both the source classifier $\theta_{s}$
and the target classifier $\theta_{t}(\phi)$ perform well on the source
domain. Since $\theta_{t}(\phi)$ relies on $\phi$ and $\theta_{s}$, the
objective of equation 5 is a bi-level optimization problem. We can derive the
gradient of the loss w.r.t. $\phi$ and $\theta_{s}$ as follows:

$\displaystyle\nabla_{\phi}[L_{\widehat{P}}(\theta_{s},\phi)$
$\displaystyle+L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)]$ (78)
$\displaystyle=$
$\displaystyle\nabla_{\phi}L_{\widehat{P}}(\theta_{s},\phi)+\frac{\partial
L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)}{\partial\phi}+\frac{\partial
L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)}{\partial\hat{\theta}_{t}(\phi)}\frac{\mathop{}\\!\mathrm{d}\hat{\theta}_{t}(\phi)}{\mathop{}\\!\mathrm{d}\phi}$
$\displaystyle=$
$\displaystyle\nabla_{\phi}L_{\widehat{P}}(\theta_{s},\phi)+\frac{\partial
L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)}{\partial\phi}+\frac{\partial
L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)}{\partial\hat{\theta}_{t}(\phi)}\left[\frac{\partial\hat{\theta}_{t}(\phi)}{\partial\phi}+\frac{\partial\hat{\theta}_{t}(\phi)}{\partial
y^{\prime}}\frac{\partial y^{\prime}}{\partial\phi}\right].$
$\displaystyle\nabla_{\theta_{s}}[L_{\widehat{P}}(\theta_{s},\phi)+L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)]=\nabla_{\theta_{s}}L_{\widehat{P}}(\theta_{s},\phi)+\frac{\partial
L_{\widehat{P}}(\hat{\theta}_{t}(\phi),\phi)}{\partial\hat{\theta}_{t}(\phi)}\frac{\partial\hat{\theta}_{t}(\phi)}{\partial
y^{\prime}}\frac{\partial y^{\prime}}{\partial\theta_{s}}.$ (79)

However, following the standard practice in self-training, we use label-
sharpening to obtain target pseudo-labels $y^{\prime}$, i.e.
$y^{\prime}=\mathop{\arg\max}_{i}\\{f_{\theta_{s},\phi}(x)_{[i]}\\}$. Thus,
$y^{\prime}$ is not differentiable w.r.t. $\theta_{s}$ and $\phi$. We treat
the gradient of $y^{\prime}$ w.r.t. $\theta_{s}$ and $\phi$ as $0$ in equation
78 and equation 79, making optimization easier. This modification leads to
exactly equation 7 and equation 8 in Algorithm 1 together with the Tsallis
entropy loss.

Speeding up bi-level optimization with MSE loss. Standard methods of bi-level
optimization back-propagate through the inner loop algorithm, which requires
computing the second-order derivative (Hessian-vector products) and can be
unstable. We propose to use MSE loss instead of cross entropy in the inner
loop when training the head $\hat{\theta}(\phi)$ to calculate the analytical
solution with least square and directly back-propagate to the outer loop
without calculating second-order derivatives. The framework is as fast as
training the two heads jointly. To adopt MSE loss in multi-class
classification, we use the one-hot embedding as the output and train a multi-
variate regressor following the protocol of Arora et al. [3]. We calculate the
least square solution of $\theta_{t}(\phi)$ based on one minibatch following
the protocol of Bertinetto et al. [9]. We also provide results of varying
batchsize to verify the performance of this approximation in Table 7. Results
indicate that the performance of CST is stable in a wide range of batchsizes.

Table 7: Accuracy (%) on VisDA-2017 with ResNet-50 Method | Accuracy
---|---
CST (batchzize 32) |  79.9 $\pm$ 0.6
CST (batchzize 64) |  79.9 $\pm$ 0.5
CST (batchzize 128) |  79.6 $\pm$ 0.4
CST (batchzize 256) |  79.0 $\pm$ 0.6

###  B.3 Selection of $\alpha$

We can also update $\alpha$ with gradient methods auto-differentiation tools
as we treat $\phi$. However, since $\alpha$ has only one parameter but many
other parameters ($\theta_{s,\alpha}$ and $\theta_{t,\alpha}$) rely on it,
using gradient methods is costly. To ease the computational cost, we choose to
discretize the feasible region of $\alpha\in[1,2]$ with
$\alpha\in\\{1.0,1.1,\cdots 1.9,2.0\\}$, and train ${\theta}_{s,\alpha}$ with
each $\alpha\in\\{1.0,1.1,\cdots 1.9,2.0\\}$ to generate pseudo-labels and
train $\hat{\theta}_{t,\alpha}$ on pseudo-labels corresponding to each value
of $\alpha$. Then we select the $\alpha\in\\{1.0,1.1,\cdots 1.9,2.0\\}$ with
best performance on the source dataset following equation 10. We also update
$\alpha$ at the start of each epoch, since we found more frequent update leads
to no performance gain. Since we only need to select $\alpha$ once at the
start of each epoch, the resulting additional computational cost only relates
to training the linear head on the source and target datasets for additional
11 times per epoch, which is negligible compared to training the backbone.

We plot the change of $\alpha$ throughout training in Figure 6. $\alpha$
converges to smaller value at the end of training, indicating that the
penalization on uncertainty is increasing. Also note that $\alpha$ tends
decrease slower for “heuristically distant” source and target domains. This
corroborates the intuition that we need to penalize uncertain predictions
mildly especially when the domain gap is large.

Figure 6: Change of $\alpha$ during training.

Difference between $\theta_{s}$ and $\theta_{s,\alpha}$. We use $\theta_{s}$
to update the feature extractor $\phi$ and test on the target domain after
training. $\theta_{s,\alpha}$ is only used to search the optimal $\alpha$, and
the gradient does not back-propagate to $\phi$.

##  Appendix C Additional Experiment Details

###  C.1 Additional Details of Section 2.1

In Figure 2 (Left), we use VisDA-2017 with 12 classes. To simulate the i.i.d.,
covariate shift and label shift setup, we resample the original Synthetic
(source) and Real (target) datasets. In the i.i.d. setting, the labeled
dataset consists of $1000$ random samples per class from Real, and the
unlabeled dataset consists of $1000$ random samples (no overlapping with the
labeled dataset) per class from Real. In the covariate shift setting, the
labeled dataset consists of $1000$ random samples per class from Synthetic,
and the unlabeled dataset consists of $1000$ random samples per class from
Real. In the label shift setting, the number of examples is
$[1800,1440,1152,922,737,590,472,377,302,240,193,154]$ for each class of the
labeled dataset and $1000$ for each class of the unlabeled dataset, with both
labeled and unlabeled datasets sampled randomly from Real. We train the model
on labeled data until convergence to generate pseudo-labels for the unlabeled
data. Then we calculate the ratio of classes in pseudo-labels and ground
truth.

In Figure 2 (Middle), we also visualize the change of pseudo-label accuracy
and the distance $d_{\textup{TV}}$ throughout standard self-training on
original Synthetic and Real datasets. Here standard self-training refers to
equation 2 with label-sharpening.

In both Figure 2 (Right) and this subsection, confidence refers to the maximum
soft-max output value, and entropy is defined as
$\sum_{i}-y_{i}\textup{log}(y_{i})$. We change the confidence threshold from
$0$ to $1$ and entropy threshold from $0$ to log(numclasses). Then we plot the
point (False Positive Rate, True Positive Rate) in the plane.

In Section 2.1, we measure the quality of pseudo-labels with the total
variation between pseudo-label distribution and ground-truth distribution. We
show this quantity is upper-bounded by the accuracy of pseudo-labels.
Intuitively, when the pseudo-label distribution and ground-truth distribution
are the same, the output can still be incorrect. (e.g., in a binary problem,
$P(Y=1)=P(Y=0)=0.5$, and $\hat{Y}\sim\textup{uniform}[0,1]$ but is independent
of $X$.) Recall that
$d_{\textup{TV}}(Y,\hat{Y})=\textup{sup}_{E\subset[C]}|P(Y\in E)-P(\hat{Y}\in
E)|$. Suppose the supremum is reached by $\hat{E}$. Without loss of
generality, assume $P(Y=c)>P(\hat{Y}=c)$ for all $c\in\hat{E}$. Then
$P(Y=c)\leq P(\hat{Y}=c)$ for all $c\notin\hat{E}$.

$\displaystyle P(Y\neq\hat{Y})=$ $\displaystyle\sum_{c=1}^{C}P(Y=c,\
\hat{Y}\neq c)$ $\displaystyle=$ $\displaystyle\sum_{c\in\hat{E}}P(Y=c,\
\hat{Y}\neq c)+\sum_{c\notin\hat{E}}P(Y=c,\ \hat{Y}\neq c)$
$\displaystyle\geq$ $\displaystyle\sum_{c\in\hat{E}}P(Y=c)-P(\hat{Y}=c)$
$\displaystyle=$ $\displaystyle d_{\textup{TV}}(Y,\hat{Y}).$

In the equality, we use $P(Y=c)>P(\hat{Y}=c)$ when $c\in\hat{E}$, so $P(Y=c,\
\hat{Y}\neq c)\geq P(Y=c)-P(\hat{Y}=c)$ if $c\in\hat{E}$. Also note that
$P(Y=c,\ \hat{Y}\neq c)\geq 0$ if $c\notin\hat{E}$.

In this subsection, we provide additional results of Section 2.1. We visualize
the distributions of pseudo-labels and ground-truth with ResNet-50 backbones
on Art$\rightarrow$Clipart, Product$\rightarrow$Art, Clipart$\rightarrow$Real
World, Art$\rightarrow$Real World and Real World $\rightarrow$Product tasks
(without resampling) in Figures 7, 8, 9, 10, and 11 respectively. We also
visualize the ROC curve of pseudo-label selection with confidence threshold.
Results on Art$\rightarrow$Clipart, Product$\rightarrow$Art,
Clipart$\rightarrow$Real World, Art$\rightarrow$Real World and Real World
$\rightarrow$Product are similar to VisDA-2017. When the pseudo-labels are
generated from models trained on different distributions, they can become
especially unreliable in that examples of several classes are almost
misclassified into other classes. Domain shift also makes the selection of
correct pseudo-labels more difficult than standard semi-supervised learning.

Figure 7: Analysis of pseudo-labels under domain shift on
Art$\rightarrow$Clipart. Left: Comparison of pseudo-label distributions with
and without domain shift. Right: Comparison of pseudo-label selection with and
without domain shift.

Figure 8: Analysis of pseudo-labels under domain shift on
Product$\rightarrow$Art. Left: Comparison of pseudo-label distributions with
and without domain shift. Right: Comparison of pseudo-label selection with and
without domain shift.

Figure 9: Analysis of pseudo-labels under domain shift on
Clipart$\rightarrow$Real World. Left: Comparison of pseudo-label distributions
with and without domain shift. Right: Comparison of pseudo-label selection
with and without domain shift.

Figure 10: Analysis of pseudo-labels under domain shift on
Art$\rightarrow$Real World. Left: Comparison of pseudo-label distributions
with and without domain shift. Right: Comparison of pseudo-label selection
with and without domain shift.

Figure 11: Analysis of pseudo-labels under domain shift on Real
World$\rightarrow$Product. Left: Comparison of pseudo-label distributions with
and without domain shift. Right: Comparison of pseudo-label selection with and
without domain shift.

###  C.2 Results on digit datasets

We provide results on the digit datasets to test the performance of the
proposed method without using pre-training. We use DTN architecture following
Long et al. [37]. Results in Table 8 indicate that CST achieve comparable
performance to state-of-the-art.

Table 8: Accuracy (%) on digits datasets with DTN Method |  MNIST$\rightarrow$USPS |  SVHN$\rightarrow$MNIST
---|---|---
CDAN |  95.6 $\pm$ 0.2 |  96.9 $\pm$ 0.2
RWOT (CVPR 2020) |  98.5 $\pm$ 0.2 |  97.5 $\pm$ 0.2
CST |  98.5 $\pm$ 0.2 |  98.2 $\pm$ 0.2

###  C.3 Results on DomainNet

We test the performance of the proposed method on the 40-class DomainNet [46]
subset following the protocol of Tan et al. [60]. Results in Table 9 indicate
that CST outperforms MDD by a large margin.

Table 9: Accuracy (%) on DomainNet for unsupervised domain adaptation (ResNet-50). Method | R-C | R-P | R-S | C-R | C-P | C-S | P-R | P-C | P-S | S-R | S-C | S-P | Avg.
---|---|---|---|---|---|---|---|---|---|---|---|---|---
DANN [22] | 63.4 | 73.6 | 72.6 | 86.5 | 65.7 | 70.6 | 86.9 | 73.2 | 70.2 | 85.7 | 75.2 | 70.0 | 74.5
COAL [60] | 73.9 | 75.4 | 70.5 | 89.6 | 70.0 | 71.3 | 89.8 | 68.0 | 70.5 | 88.0 | 73.2 | 70.5 | 75.9
MDD [73] | 77.6 | 75.7 | 74.2 | 89.5 | 74.2 | 75.6 | 90.2 | 76.0 | 74.6 | 86.7 | 72.9 | 73.2 | 78.4
CST | 83.9 | 78.1 | 77.5 | 90.9 | 76.4 | 79.7 | 90.8 | 82.5 | 76.5 | 90.0 | 82.8 | 74.4 | 82.0

###  C.4 Standard deviations of Tables

We visualize the performance of CST and best baselines in Table 3 with
standard deviations. Results indicate that the improvement of CST over
previous methods is significant.

Figure 12: Visualization of standard deviations of CST and baselines. CST
outperforms baselines significantly on all tasks except K$\rightarrow$B.

##  Appendix D Limitations of CST and Future Directions

CST overcomes the drawbacks of standard pseudo-labeling in domain adaptation
by dealing with the domain discrepancy explicitly with the cycle loss.
However, pseudo-labeling is only one main direction of semi-supervised
learning. Consistency regularization [40] and self-ensembling [4] are also
important paradigms in semi-supervised learning. How to apply them to the
setting with distribution shift and achieve consistent performance gain is
still an open question. More recently, Carlini [12] investigated the effect of
adversarial unlabeled data poisoning to self-training. Future works can extend
CST to this setting and extend consistency regularization as a potential way
of defense.

##  Appendix E Broader Impact

This work studies and improves self-training in the unsupervised domain
adaptation setting. When deployed in real-world applications, distribution
shift between labeled and unlabeled data can come in various ways. Although
the quality of labeled datasets can be monitored, enabling the mitigation of
bias in pre-processing, bias in unlabeled datasets can be intractable. Self-