Gradual Domain Adaptation
without Indexed Intermediate Domains

We consider an unsupervised domain adaptation (UDA) problem, in which a classifier is provided with labeled data from the source domain $\mathcal{S}=\{({\bm{x}}^{\mathcal{S}}_{i},y^{\mathcal{S}}_{i})\}_{i=1}^{|\mathcal{S}|}$ and unlabeled data from the target domain $\mathcal{T}=\{{\bm{x}}^{\mathcal{T}}_{i}\}_{i=1}^{|\mathcal{T}|}$. Both $\mathcal{S}$ and $\mathcal{T}$ are sampled IID from the underlying joint distributions of the source $P_{\mathcal{S}}$ and target $P_{\mathcal{T}}$, respectively. A source model $\bm{\theta}_{\mathcal{S}}$ is typically produced by training on $\mathcal{S}$ directly. The goal of UDA is to learn a target model $\bm{\theta}_{\mathcal{T}}$ such that it can perform well on the target, measured by a loss $\mathcal{L}(\bm{\theta}_{\mathcal{T}},P_{\mathcal{T}})$. We focus on the standard UDA setup that assumes no label shifts [6].

We summarize the theoretical analysis of GDA using self-training by Kumar et al. [35] as follows.

In this paper, we study the case of GDA where the additional unlabeled data $\mathcal{U}$ are not readily divided into domain sequences $\mathcal{U}_{1},\cdots,\mathcal{U}_{M-1}$. In other words, we are provided with a single, gigantic unlabled set that has a wide range of support from the source to the target domain. One naive way to leverage it is to adapt from $\mathcal{S}$ to $\mathcal{U}$¹¹1In [35], the authors investigated sampling $\mathcal{U}_{1},\cdots,\mathcal{U}_{M-1}$ from $\mathcal{U}$ uniformly at random with replacement. and then to $\mathcal{T}$, which however leads to a much larger target error than applying self-training along the properly indexed intermediate domains [35]. We attribute this to the large $\rho(\mathcal{S},\mathcal{U})$ or $\rho(\mathcal{U},\mathcal{T})$ according to Equation 4. To take advantage of $\mathcal{U}$, we must separate it into intermediate domains such that $\rho(P_{m},P_{m+1})$ is small enough for every $m\in\{0,\ldots,M-1\}$.

Given the source data $\mathcal{S}$, the target data $\mathcal{U}_{M}=\mathcal{T}$, and the unlabeled intermediate data $\mathcal{U}=\{{\bm{x}}^{\mathcal{U}}_{i}\}_{i=1}^{{|\mathcal{U}|}}$, we propose the intermediate domain labeler (IDOL), whose goal is to sort intermediate data instances in $\mathcal{U}$ and chunk them into $M-1$ domains $\mathcal{U}_{1},\cdots,\mathcal{U}_{M-1}$ (with equal sizes) for GDA to succeed.

Taking gradual self-training in Equation 3 as an example, IDOL aims to solve the following problem

where the target model $\bm{\theta}_{\mathcal{T}}$ is produced by applying gradual self-training to the domain sequence discovered by IDOL. IDOL accepts the number of intermediate domains $M-1$ as a hyper-parameter.

Solving Equation 5 is hard, as evaluating any output sequence needs running through the entire gradual self-training process, not to mention that we have no labeled target data to estimate $\mathcal{L}(\bm{\theta}_{\mathcal{T}},P_{\mathcal{T}})$. In this paper, we propose to solve Equation 5 approximately via a coarse-to-fine procedure.

In this stage, we assign each ${\bm{x}}^{\mathcal{U}}_{i}\in\mathcal{U}$ a score $q_{i}$, such that higher/lower $q_{i}$ indicates that ${\bm{x}}^{\mathcal{U}}_{i}$ is closer to the source/target domain. We discuss some design choices. For brevity, we omit the superscript ^U.

The domain scores developed in subsection 3.3 can already give each individual example ${\bm{x}}\in\mathcal{U}$ a rough position of which intermediate domain it belongs to. However, for GDA to succeed, we must consider intermediate data in a collective manner. That is, each intermediate domain should preserve sufficient discriminative (e.g., classification) knowledge from the previous one, such that after $M$ rounds of adaptation through GDA, the resulting $\bm{\theta}_{\mathcal{T}}$ in Equation 5 will be able to perform well on $\mathcal{T}$. This is reminiscent of some recent claims in UDA [75, 46]: matching only the marginal distributions between domains (i.e., blind to the class labels) may lead to sub-optimal adaptation results.

But how can we measure the amount of discriminative knowledge preserved by an intermediate domain (or in the target domain) if we do not have its labeled data? To seek for the answer, we revisit Equation 4 and consider the case $M=1$. If the two domains $P_{0}$ and $P_{1}$ are sufficiently close and the initial model $\bm{\theta}_{0}$ is well-trained, the resulting model $\bm{\theta}_{1}$ after self-training will perform well. Reversely, we can treat such a well-performing $\bm{\theta}_{1}$ as the well-trained initial model, and apply self-training again — this time from $P_{1}$ back to $P_{0}$. The resulting model $\bm{\theta}_{0}^{\prime}$, according to the same rationale, should perform well on $P_{0}$. In other words, $\bm{\theta}_{0}^{\prime}$ and $\bm{\theta}_{0}$ should predict similarly on data sampled from $P_{0}$. The similarity between $\bm{\theta}_{0}^{\prime}$ and $\bm{\theta}_{0}$ in terms of their predictions therefore can be used as a proxy to measure how much discriminative knowledge $\bm{\theta}_{1}$, after adapted to $P_{1}$, preserves. It is worth noting that measuring the similarity between $\bm{\theta}_{0}^{\prime}$ and $\bm{\theta}_{0}$ requires no labeled data from $P_{0}$ or $P_{1}$.

Now let us consider a more general case that $M$ is not limited to $1$. Let us set $\bm{\theta}_{0}=\bm{\theta}_{\mathcal{S}}$, where $\bm{\theta}_{\mathcal{S}}$ has been trained with the labeled source data $\mathcal{S}$ till convergence. Based on the concept mentioned above, we propose a novel learning framework to discover the domain sequences,

where $\mathcal{U}_{0}$ is the source data $\mathcal{S}$ with labels removed, and $\mathcal{U}_{M}=\mathcal{T}$ is the target data. $\bm{\theta}_{0}^{\prime}$ is a gradually self-trained model from $\bm{\theta}_{0}$ that undergoes a cycle $\mathcal{U}_{1}\rightarrow,\cdots,\rightarrow\mathcal{U}_{M}\rightarrow,\cdots,\rightarrow\mathcal{U}_{0}$. In other words, Equation 7 aims to find the intermediate domain sequences such that performing gradual self-training along it in a forward and then backward fashion leads to cycle-consistency [76].

Optimization. Solving Equation 7 is still not trivial due to its combinatorial nature. We therefore propose to solve it greedily, starting with discovering $\mathcal{U}_{1}$, and then $\mathcal{U}_{2}$, and then so on. Concretely, we decompose Equation 7 into a series of sub-problems, as illustrated in Figure 2, each is defined as

where $\bm{\theta}_{m}$ is the model already adapted to the current domain $\mathcal{U}_{m}$, and $\mathcal{U}_{\setminus m}=\mathcal{U}\setminus\cup_{j=1}^{m}\mathcal{U}_{j}$ is the remaining data that have not been selected by the $m$ intermediate domains so far. That is, each sub-problem discovers only the next intermediate domain $\mathcal{U}_{m+1}$ via cycle-consistency.

Let $N=|\mathcal{U}_{\setminus m}|$ and $\mathcal{U}_{\setminus m}=\{{\bm{x}}_{i}\}_{i=1}^{N}$, selecting $\mathcal{U}_{m+1}\subset\mathcal{U}_{\setminus m}$ is equivalent to selecting a binary indicator vector $\bm{q}\in\{0,1\}^{N}$, in which $q_{i}=1$²²2Here we use the same notation as the coarse scores defined in subsection 3.3, since later we will initialize these values indeed by the coarse scores. means that ${\bm{x}}_{i}\in\mathcal{U}_{\setminus m}$ is included into $\mathcal{U}_{m+1}$. This representation turns the self-training step $\bm{\theta}_{m+1}=\texttt{ST}(\bm{\theta}_{m},\mathcal{U}_{m+1})$ in Equation 8 into

We choose to solve Equation 8 approximately by relaxing the binary vector $\bm{q}\in\{0,1\}^{N}$ into a real vector $\bm{q}\in\mathbb{R}^{N}$, which fits perfectly into the meta-reweighting framework [55, 29]. Concretely, meta-reweighting treats $\bm{q}\in\mathbb{R}^{N}$ as learnable differentiable parameters associated to training examples (in our case, the data in $\mathcal{U}_{\setminus m}$). Meta-reweighting for Equation 8 can be implemented via the following six steps for multiple iterations.

1. 1.

   Detach: $\bm{\theta}\leftarrow\bm{\theta}_{m}$,

2. 2.

   Forward: $\bm{\theta}(\bm{q})\leftarrow\bm{\theta}-\cfrac{\eta_{\bm{\theta}}}{|\mathcal{U}_{\setminus m}|}\times\cfrac{\partial\sum_{i\in\mathcal{U}_{\setminus m}}q_{i}\times\ell(f({\bm{x}}_{i};\bm{\theta}),\texttt{sharpen}(f({\bm{x}}_{i};\bm{\theta}_{m})))}{\partial\bm{\theta}},$

3. 3.

   Detach: $\bm{\theta}^{\prime}\leftarrow\bm{\theta}(\bm{q})$,

4. 4.

   Backward: $\bm{\theta}(\bm{q})\leftarrow\bm{\theta}(\bm{q})-\cfrac{\eta_{\bm{\theta}}}{|\mathcal{U}_{m}|}\times\cfrac{\partial\sum_{j\in\mathcal{U}_{m}}\ell(f({\bm{x}}_{j};\bm{\theta}(\bm{q})),\texttt{sharpen}(f({\bm{x}}_{j};\bm{\theta}^{\prime})))}{\partial\bm{\theta}(\bm{q})},$

5. 5.

   Update: $\bm{q}\leftarrow\bm{q}-\cfrac{\eta_{\bm{q}}}{|\mathcal{U}_{m}|}\times\cfrac{\partial\sum_{j\in\mathcal{U}_{m}}\ell(f({\bm{x}}_{j};\bm{\theta}(\bm{q})),\texttt{sharpen}(f({\bm{x}}_{j};\bm{\theta}_{m})))}{\partial\bm{q}}$,

6. 6.

   Update: $q_{i}\leftarrow\max\{0,q_{i}\}$.

The aforementioned updating rule gives ${\bm{x}}_{i}$ a higher value of $q_{i}$ if it helps preserve the discriminative knowledge. After obtaining the updated $\bm{q}\in\mathbb{R}^{N}$, we then sort it in the descending order and select the top $\frac{|\mathcal{U}|}{M-1}$ examples to be $\mathcal{U}_{m+1}$ (i.e., every intermediate domain has an equal size).

Discussion. The way we relax the binary-valued vector $\bm{q}\in\{0,1\}^{N}$ by real values is related to the linear programming relaxation of an integer programming problem. It has been widely applied, for example, in discovering sub-domains within a dataset [16]. Theoretically, we should constrain each element of $\bm{q}$ to be within $[0,1]$. Empirically, we found that even without the clipping operation to upper-bound $q_{i}$ (i.e., just performing $\max{\{0,q_{i}\}}$), the values in $q_{i}$ do not explode and the algorithm is quite stable: we see a negligible difference of using upper-bounded $q_{i}$ or not in the resulting accuracy of GDA. This is also consistent with the common practice of using meta-reweighting [29, 55].

Initialization. We initialize $q_{i}$ by the coarse scores defined in subsection 3.3. This is for one important reason: Equation 8 searches for the next intermediate domain $\mathcal{U}_{m+1}$ only based on the current intermediate domain $\mathcal{U}_{m}$. Thus, it is possible that $\mathcal{U}_{m+1}$ will include some data points that help preserve the knowledge in $\mathcal{U}_{m}$ but are distributionally deviated from the gradual transition between $\mathcal{U}_{m}$ and the target domain $\mathcal{T}$. The scores defined in subsection 3.3 thus serve as the guidance; we can also view Equation 8 as a refinement step of the coarse scores. As will be seen in section 4, the qualities of the initialization and the refinement steps both play important roles in IDOL’s success.

We mainly study two benchmark datasets used in [35]. Rotated MNIST [36] is a popular synthetic dataset to study distributional shifts. It gradually rotates the original $50,000$ images in the MNIST [37] dataset with $[0,60]$ degrees uniformly, where $[0,5)$/$[5,55)$/$[55,60]$ degrees are for the source/intermediate/target domains, respectively. However, since original images have no ground truths of the rotation, the rotation annotations are not expected to be perfect. Portraits dataset [14] is a real-world gender classification dataset of a collection of American high school seniors from the year 1905 to 2013. Naturally, the portrait styles change along years (e.g., lip curvature [14], fashion styles). The images are first sorted by the years and split. For both datasets, each domain contains $2000$ images, and $1,000$ images are reserved for both the source and target domains for validation.

We follow the setup in [35]: each model is a convolutional neural network trained for $20$ epochs for each domain consequently (including training on the source data), using Adam optimizer [32] with a learning rate $0.001$, batch size $32$, and weight decay $0.02$. We use this optimizer as the default if not specified. Hyper-parameters of IDOL include $K=2M$ rounds for progressive training and $30$ epochs of refinement per step (with mini-batch $128$), where $M=19$ for the Rotated MNIST and $M=7$ for the Portraits. More details are in the supplementary material.

To study how the intermediate domain sequences affect gradual self-training, we consider baselines including “Source only” and “UDA” that directly self-trains on the target data ($\mathcal{T}$) and all the intermediate data ($\mathcal{U}$). We compare different domain sequences including Pre-defined indexes, e.g., rotations and years. We further consider the challenging setup that all intermediate data are unindexed. Random sequences are by dividing the unlabeled data into $M-1$ domains randomly, with self-training on the target in the end. For our IDOL, different domain scores introduced in subsection 3.3 are adopted for the coarse domain sequences, and we optionally apply cycle-consistency refinement to make them fine-grained.

The main results on Rotated MNIST and Portraits are provided in Table 1. We first verify that without any domain sequences, UDA (on target and intermediate data) and GDA (on random sequences) do not perform well, though they slightly improve over the source model. On the contrary, training with pre-defined indexes that arguably guide the gradual adaptation significantly performs better.

If partial or outlier information of the intermediate domains is given, is IDOL still helpful? We examine the question by three experiments. First, we consider unsorted domains: the data are grouped into $M-1$ domains according to the pre-defined indexes but the domains are unordered. We find that if we sort the domains with the mean domain scores $\frac{1}{|\mathcal{U}_{m}|}\sum_{{\bm{x}}_{i}\in{\mathcal{U}_{m}}}q_{i}$, then we can perfectly recover the pre-defined order. Second, we investigate if we have fewer, coarsely separated pre-defined domains: we double the size of $|\mathcal{U}_{m}|$. We find that on Rotated MNIST (w/ pre-defined indexes), the accuracy degrades by $11\%$. IDOL can recover the accuracy since IDOL outputs a sorted sequence of data points, from which we can construct more, fine-grained intermediate domains. Third, we investigate the addition of outlier domains, in which the starting/end intermediate domains do not match the source/target domains exactly. For example, on Rotated MNIST, the intermediate domains are expanded to cover $[-30,90]$ degrees. GDA on such domain sequence with outlier domains degrades to $77.0\pm 2.0$ accuracy. Refinement can still improve it to $81.3\pm 1.4$.

In practice, the intermediate unlabeled data or the pre-defined domain indexes for them might not be perfect. We consider several realistic cases to show that our method can make GDA more robust to the quality of the intermediate data or the domain sequences. First, we investigate fewer intermediate data: Equation 4 implies that the target error increases if the intermediate data are too sparse. We repeat the experiments in subsection 4.2 but with only $30\%$ intermediate data. Second, we consider noisy indexes: building upon $30\%$ clean indexes, we further add more data with noisy, random indexes.

Figure 5 summarizes the results. We first notice that with only $30\%$ intermediate data, even if the indexes are clean, the accuracy decreases drastically by $14\%$ for MNIST and by $5\%$ for Portraits. For MNIST, adding more noisily-indexed data actually decreases the accuracy. Portraits gains some improvements with the noisily-indexed data, suggesting that the task could benefit from learning with intermediate data (even without accurate indexes). One advantage of IDOL is that we can annotate domain indexes for any unindexed data. On both datasets, IDOL stably improves with more data available, significantly outperforming that without IDOL.

We examine IDOL on a CIFAR10-to-STL [34, 5] UDA task which is known to be challenging due to the small data size [4]. The STL dataset has an additional unlabeled set, whose data are sub-sampled from ImageNet [9]. We use this set as the intermediate data, which contains unknown or outlier domains and classes. Here, we do not aim to compete with the state of the arts on the CIFAR10-to-STL UDA task, but study a more general application scenario for IDOL.

To leverage these data, we use $M=3$ and filter out $80\%$ of them using the classifier confidence. We first train a ResNet-20 [23] source model. In Table 2, we observe that direct UDA using self-training on STL or unlabeled data are inferior to the source model, even if the learning rate is carefully tuned. GDA with IDOL achieves the highest accuracy, demonstrating its robustness and wide applicability.

Another way to understand the coarse-to-fine framework we proposed is from the optimization perspective. In Equation 3 of the main paper, we provide the overall objective of IDOL, which is however intractable due to (a) no labeled target data to evaluate the domain sequence and (b) the combinatory nature of searching for a domain sequence. We deal with (a) by Equation 7 of the main paper. That is, we propose the cycle-consistency loss to measure the quality of the domain sequence, which requires no labeled target data. Since Equation 7 is still hard to solve, we relax it by a greedy approach. We find one domain at a time in sequence, starting from $\mathcal{U}_{1}$ (i.e., the one closest to the source) to $\mathcal{U}_{M-1}$ (i.e., the one closest to the target). Each sub-problem is described in Equation 8 of the main paper. The relaxation may lead to sub-optimal solutions. Concretely, each sub-problem is not aware of other already selected intermediate domains or other future intermediate domains to be selected. To mitigate this issue, we propose to assign each data point a coarse domain score (i.e., subsection 3.3 of the main paper), which serves as the initialization of each sub-problem.

Here we provide the summary of the IDOL algorithm. IDOL learns to sort the unindexed intermediate data to a sequence, partitioned into several intermediate domains. An illustration is provided in Figure 6. As shown in algorithm 1, there are three main steps in the overall procedure: first, we construct the coarse domain sequence by learning to predict the domain score for each example and sorting the examples according to the domain scores. Second, we refine the coarse indexes with cycle-consistency as shown in algorithm 2. The refinement is decomposed into several steps, gradually discovering the next intermediate domain in sequence. Each step is to refine the coarse indexes with meta-reweighting [55, 29] and takes the closest examples to the current domain as the next domain, as shown in algorithm 3. Finally, IDOL outputs a sequence of intermediate data points; it can then be divided into several intermediate domains for gradual domain adaptation.

We run our experiments on one GeForce RTX 2080 Ti GPU with Intel i9-9960X CPUs. In algorithm 3, updating the data parameter $\bm{q}$ requires it to backward on gradients of $\bm{\theta}$, which approximately takes three-time of the computation time of a standard forward-backward pass [55].

We estimated the time consumption on the Portraits dataset experiments. For coarse scores, the confidence is simply by applying the classifier to the input data. Calculating the manifold distance via [50] takes about 20 seconds with Intel i9-9960X CPU. The domain discriminator (both w/ or w/o progressive training) and the fine stage involve GPU computation. Using a GeForce RTX 2080 Ti GPU, training a domain discriminator takes about 4 seconds. Progressive training takes about $M$ times longer, where $M$ is the number of intermediate domains (which is $7$ here). This is because it trains the domain discriminator for $M$ rounds. For the refinement stage proposed in cf. subsection 3.4 based on meta-learning, Discovering one intermediate domain takes about $44$ seconds and we perform it for $M$ rounds.

We provide the full experiments (cf. Table 1 in the main paper) of IDOL refinement on different coarse domain scores in Table 3. We observe the refinement consistently helps on the coarse domain scores, and the quality of the coarse domain scores is important to the final performance.

Next, we design the following experiment to investigate the variations of different trials and the effects of the number of intermediate samples. We apply IDOL (with progressive discriminator and refinement) for $10$ runs with different random seeds, and record the intermediate domain index (from source $=0$ to the target $=M$) to which each sample is assigned. For instance, if a sample is assigned to the second intermediate domain, we record $2$ for this sample. After $10$ runs, each sample will end up with $10$ indices, and we calculate the variance. If a sample is always assigned to the same intermediate domain, the variance will be zero for this sample. We repeat the experiments with $100\%/50\%/25\%$ of intermediate data (dropped randomly). The averaged variance over all samples for both the Rotated MNIST dataset ($M=19$) and Portraits dataset ($M=7$). As shown in Table 4, the domain sequences formed in different trials are pretty consistent since the variances are small. Rotated MNIST has a higher variance than Portraits probably because the number of intermediate domains is larger. Besides, the amount of the intermediate data does not significantly affect the consistency among trials.