UNIFIED PRINCIPLES FOR MULTI-SOURCE TRANSFER LEARNING UNDER LABEL SHIFTS
Year: 2020

Abstract:
We study the label shift problem in multi-source transfer learning and derive new generic principles. Our proposed framework unifies the principles of conditional feature alignment, label distribution ratio estimation and domain relation weights estimation. Based on inspired practical principles, we provide unified practical framework for three multi-source label shift transfer scenarios: learning with limited target data, unsupervised domain adaptation and label partial unsupervised domain adaptation. We evaluate the proposed method on these scenarios by extensive experiments and show that our proposed algorithm can significantly outperform the baselines.

heading: 1 INTRODUCTION
text: Transfer learning (Pan & Yang, 2009) is based on the motivation that learning a new task is easier after having learned several similar tasks. By learning the inductive bias from a set of related source domains (S1, . . . ,ST ) and then leveraging the shared knowledge upon learning the target domain T , the prediction performance can be significantly improved. Based on this, transfer learning arises in deep learning applications such as computer vision (Zhang et al., 2019; Tan et al., 2018; Hoffman et al., 2018b), natural language processing (Ruder et al., 2019; Houlsby et al., 2019) and biomedical engineering (Raghu et al., 2019; Lundervold & Lundervold, 2019; Zhang & An, 2017).
To ensure a reliable transfer, it is critical to understand the theoretical assumptions between the domains. One implicit assumption in most transfer learning algorithms is that the label proportions remain unchanged across different domains (Du Plessis & Sugiyama, 2014) (i.e., S(y) = T (y)). However, in many real-world applications, the label distributions can vary markedly (i.e. label shift) (Wen et al., 2014; Lipton et al., 2018; Li et al., 2019b), in which existing approaches cannot guarantee a small target generalization error, which is recently proved by Combes et al. (2020).
Moreover, transfer learning becomes more challenging when transferring knowledge from multiple sources to build a model for the target domain, as this requires an effective selection and leveraging the most useful source domains when label shift occurs. This is not only theoretically interesting but also commonly encountered in real-world applications. For example, in medical diagnostics, the disease distribution changes over countries (Liu et al., 2004; Geiss et al., 2014). Considering the task of diagnosing a disease in a country without sufficient data, how can we leverage the information from different countries with abundant data to help the diagnosing? Obviously, naı̈vely combining all the sources and applying one-to-one single source transfer learning algorithm can lead to undesired results, as it can include low quality or even untrusted data from certain sources, which can severely influence the performance.
In this paper, we study the label shift problem in multi-source transfer learning where St(y) 6= T (y). We propose unified principles that are applicable for three common transfer scenarios: unsupervised Domain Adaptation (DA) (Ben-David et al., 2010), limited target labels (Mansour et al., 2020) and partial unsupervised DA with supp(T (y)) ⊆ supp(St(y)) (Cao et al., 2018), where prior works generally treated them as separate scenario. It should be noted that this work deals with target shift without assuming that semantic conditional distributions are identical (i.e., St(x|y) 6= T (x|y)), which is more realistic for real-world problems. Our contributions in this paper are two-folds:
(I) We propose to use Wasserstein distance (Arjovsky et al., 2017) to develop a new target generalization risk upper bound (Theorem 1), which reveals the importance of label distribution ratio
estimation and provides a principled guideline to learn the domain relation coefficients. Moreover, we provide a theoretical analysis in the context of representation learning (Theorem 2), which guides to learn a feature function that minimizes the conditional Wasserstein distance as well as controls the weighted source risk. We further reveal the relations in the aforementioned three scenarios lie in the different assumptions for estimating label distribution ratio.
(II) Inspired by the theoretical results, we propose Wasserstein Aggregation Domain Network (WADN) for handling label-shift in multi-source transfer learning. We evaluate our algorithm on three benchmark datasets, and the results show that our algorithm can significantly outperform stateof-the-art principled approaches.

heading: 2 RELATED WORK
text: Multi-Source Transfer Learning Theories have been investigated in the previous literature with different principles to aggregate source domains. In the popular unsupervised DA, (Zhao et al., 2018; Peng et al., 2019; Wen et al., 2020; Li et al., 2018b) adoptedH-divergence (Ben-David et al., 2007), discrepancy (Mansour et al., 2009) and Wasserstein distance (Arjovsky et al., 2017) of marginal distribution d(St(x), T (x)) to estimate domain relations and dynamically leveraged different domains. These algorithms generally consists source risk, domain discrepancy and an un-observable term η, the optimal risk on all the domains, which are ignored in these approaches. However, as Combes et al. (2020) pointed out, ignoring the influence of η will be problematic when label distributions between source and target domains are significantly different. Therefore it is necessary to take η into consideration by using a small amount of labelled data is available for the target domain (Wen et al., 2020). Following this line, very recent works (Konstantinov & Lampert, 2019; Wang et al., 2019a; Mansour et al., 2020) started to consider measure the divergence between two domains given label information for the target domain by using Y-discrepancy (Mohri & Medina, 2012). However, we empirically showed these methods are still unable to handle label shift.
Label-Shift Label-Shift (Zhang et al., 2013; Gong et al., 2016) is a common phenomena in the transfer learning with S(y) 6= T (y) and generally ignored by the previous multi-source transfer learning practice. Several theoretical principled approaches have been proposed such as (Azizzadenesheli et al., 2019; Garg et al., 2020). In addition, (Combes et al., 2020; Wu et al., 2019) analyzed the generalized label shift problem in the one-to-one single unsupervised DA problem but did not provide guidelines of levering different sources to ensure a reliable transfer, which is more challenging. (Redko et al., 2019) proposed optimal transport strategy for the multiple unsupervised DA under label shift by assuming identical semantic conditional distribution. However they did not consider representation learning in conjunction with their framework and did not design neural network based approaches. Different from these, we analyzed our problem in the context of representation learning and propose an efficient and principled strategies. Moreover, our theoretical results highlights the importance of label shift problem in a variety of multi-source transfer problem. While the aforementioned work generally focus on the unsupervised DA problem, without considering unified rules for different scenarios (e.g. partial multi-source DA).

heading: 3 THEORETICAL INSIGHTS: TRANSFER RISK UPPER BOUND
text: We assume a scoring hypothesis defined on the input space X and output space Y with h : X ×Y → R, is K-Lipschitz w.r.t. the feature x (given the same label), i.e. for ∀y, ‖h(x1, y) − h(x2, y)‖2 ≤ K‖x1 − x2‖2, and the loss function ` : R × R → R+ is positive, L-Lipschitz and upper bounded by Lmax. We denote the expected risk w.r.t distribution D: RD(h) = E(x,y)∼D`(h(x, y)) and its empirical counterpart (w.r.t. D̂) R̂D(h) = ∑ (x,y)∈D̂ `(h(x, y)). We adopted Wasserstein-1 distance (Arjovsky et al., 2017) as a metric to measure the similarity of the domains. Compared with other divergences, Wasserstein distance has been theoretically proved tighter than TV distance (Gong et al., 2016) or Jensen-Shnannon divergence (Combes et al., 2020).
Based on previous work, the label shift is generally handled by label-distribution ratio weighted loss: RαS(h) = E(x,y)∼Sα(y)`(h(x, y)) with α(y) = T (y)/S(y). We also denote α̂t as its empirical counterpart, estimated from samples. Besides, to measure the task relations, we define a simplex λ with λ[t] ≥ 0, ∑T t=1 λ[t] = 1 as the task relation coefficient vector by assigning high weight to
the similar task. Then we first present Theorem 1, which proposed theoretical insights about how to combine source domains through properly estimating λ.
Theorem 1. Let {Ŝt = {(xi, yi)} NSt i=1 }Tt=1 and T̂ = {(xi, yi)} NT i=1, respectively be T source and target i.i.d. samples. For ∀h ∈ H with H the hypothesis family and ∀λ, with high probability ≥ 1− 4δ, the target risk can be upper bounded by:
RT (h) ≤ ∑ t λ[t]R̂α̂tSt (h) + LK ∑ t λ[t]Ey∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y)) + Lmaxd sup ∞ √√√√ T∑ t=1 λ[t]2 βt √ log(1/δ) 2N
+ Lmax sup t ‖αt − α̂t‖2 + Comp(NS1 , . . . , NST , NT , δ),
where N = ∑T t=1NSt and βt = NSt/N and d sup ∞ = maxt∈[1,T ],y∈[1,Y] αt(y) the maximum true label distribution ratio value. W1(·‖·) is the Wasserstein-1 distance with L2-distance as cost function. Comp(NS1 , . . . , NST , NT , δ) is a function that decreases with larger NS1 , . . . , NT , given a fixed δ and hypothesis familyH. (See Appendix E for details)
Remarks (1) In the first two terms, the relation coefficient λ is controlled by αt-weighted loss R̂α̂tSt (h) and conditional Wasserstein distance Ey∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y)). To minimize the upper bound, we need to assign a higher λ[t] to the source t with a smaller weighted prediction loss and a smaller weighted semantic conditional Wasserstein distance. Intuitively, we tend to leverage the source task which is semantic similar to the target and easier to learn. (2) If each source have equal observations with βt = 1, then the third term will become ‖λ‖2, a L2 norm regularization, which can be viewed as an encouragement of uniformly leveraging all the sources. Combing these three terms, we need to consider the trade-off between assigning a higher λ[t] to the source t that has a smaller weighted prediction loss and conditional Wasserstein distance, and assigning balanced λ[t] for avoiding concentrating on only one source. (3) ‖α̂t − αt‖2 indicates the gap between ground-truth and empirical label ratio. Therefore if we can estimate a good α̂t, these terms can be small. In the practice, If target labels are available, α̂t can be computed from the observed data and α̂t → αt. If target labels are absent (unsupervised DA), we need to design methods and to properly estimate α̂t (Sec. 4). (4) Comp(NS1 , . . . , NST , NT , δ) is a function that reflects the convergence behavior, which decreases with larger observation numbers. If we fixH, δ, N and NT , this term can be viewed as a constant.
Insights in Representation Learning Apart from Theorem 1, we propose a novel theoretical analysis in the context of representation learning, which motivates practical guidelines in the deep learning regime. We define a stochastic feature function g and we denote its conditional distribution w.r.t. latent variable Z (induced by g) as S(z|Y = y) = ∫ x g(z|x)S(x|Y = y)dx. Then we have:
Theorem 2. We assume the settings of loss, the hypothesis are the same with Theorem 1. We further denote the stochastic feature learning function g : X → Z , and the hypothesis h : Z × Y → R. Then ∀λ, the target risk is upper bounded by:
RT (h, g) ≤ ∑ t λ[t]RαtSt (h, g) + LK ∑ t λ[t]Ey∼T (y)W1(St(z|Y = y)‖T (z|Y = y)),
where RT (h, g) = E(x,y)∼T (x,y)Ez∼g(z|x)`(h(z, y)).
Theorem 2 reveal that to control the upper bound, we need to learn g that minimizes the weighted conditional Wasserstein distance and learn (g, h) that minimizes the weighted source risk.
Comparison with previous Theorems. Our theory proposed an alternative prospective to understand transfer learning. The first term is α-weighted loss. And it will recover the typical source loss minimization if there is no label shift with αt(y) ≡ 1 (Li et al., 2019a; Peng et al., 2019; Zhao et al., 2018; Wen et al., 2020). Beside, minimizing the conditional Wasserstein distances has been shown to be advantageous, compared with W1(St(z)‖T (z)) (Long et al., 2018). Moreover, Theorem 2 explicitly proposed the theoretical insights about the representation learning function g, which remains elusive for previous multi-source transfer theories such as (Wang et al., 2019a; Mansour et al., 2020; Konstantinov & Lampert, 2019; Li et al., 2019a; Peng et al., 2019).

heading: 4 UNIFIED PRACTICAL FRAMEWORK IN DEEP LEARNING
text: The theoretical results in Section 3 motivate general principles to follow when designing multisource transfer learning algorithms. We summarize those principles in the following rules.
(I) Learn a g that minimizes the weighted conditional Wasserstein distance as well as learn (g, h) that minimizes the α̂t-weighted source risk (Sec. 4.1).
(II) Properly estimate the label distribution ratio α̂t (Sec. 4.2).
(III) Balance the trade-off between assigning a higher λ[t] to the source t that has a smaller weighted prediction loss and conditional Wasserstein distance, and assigning balanced λ[t]. (Sec. 4.3).
We instantiate these rules with a unified practical framework for solving multi-source transfer learning problems, as shown in Tab 1. We would like to point out that our original theoretical result is based on setting with the available target labels. The proposed algorithm can be applied to unsupervised scenarios under additional assumptions.

heading: 4.1 GUIDELINES IN THE REPRESENTATION LEARNING
text: Motivated by Theorem 2, given a fixed label ratio estimation α̂t and fixed λ, we should find a representation function g : X → Z and a hypothesis function h : Z × Y → R such that:
min g,h ∑ t λ[t]R̂α̂tSt (h, g) + C0 ∑ t λ[t]Ey∼T̂ (y)W1(Ŝt(z|Y = y)‖T̂ (z|Y = y)) (1)
Explicit Conditional Loss When target label information is available, one can explicitly solve the conditional optimal transport problem with g and h for a given Y = y. However, due to the high computational complexity in solving T × |Y| optimal transport problems, the original form is practically intractable. To address this issue, we propose to approximate the conditional distribution on latent space Z as Gaussian distribution with identical Covariance matrix such that Ŝt(z|Y = y) ≈ N (Cyt ,Σ) and T̂ (z|Y = y) ≈ N (Cy,Σ). Then we have W1(Ŝt(z|Y = y)‖T̂ (z|Y = y)) ≤ ‖Cyt −Cy‖2 (see Appendix G for details). Intuitively, the approximation term is equivalent to the well known feature mean matching (Sugiyama & Kawanabe, 2012), which computes the feature centroid of each class (on latent space Z) and aligns them by minimizing their L2 distance.
Implicit Conditional Loss When target label information is not available (e.g. unsupervised DA and partial DA), the explicit matching approach can adopt pseudo-label predicted by the hypothesis h as a surrogate of the true target label. However, in the early stage of the learning process, the pseudo-labels can be unreliable, which can lead to an inaccurate estimate of W1(Ŝ(z|Y = y)‖T̂ (z|Y = y)). To address this, the following Lemma indicates that estimating the conditional Wasserstein distance is equivalent to estimating the Wasserstein adversarial loss weighted by the label-distribution ratio. Lemma 1. The weighted conditional Wasserstein distance can be implicitly expressed as:∑ t λ[t]Ey∼T (y)W1(St(z|Y = y)‖T (z|Y = y)) = max d1,··· ,dT ∑ t λ[t][Ez∼St(z)ᾱt(z)dt(z)−Ez∼T (z)dt(z)],
where ᾱt(z) = 1{(z,y)∼St}αt(Y = y), and d1, . . . , dT : Z → R+ are the 1-Lipschitz domain discriminators (Ganin et al., 2016; Arjovsky et al., 2017).
Lemma 1 reveals that instead of using pseudo-labels to estimate the weighted conditional Wasserstein distance, one can train T domain discriminators with weighted Wasserstein adversarial loss,
which does not require the pseudo-label of each target sample during the matching. On the other hand, ᾱt can be obtained from α̂t, which will be elaborated in Sec. 3.2.
In practice, we adopt a hybrid approach by linearly combining the explicit and implicit matching strategies for all the scenarios, in which empirical results show its effectiveness.
4.2 ESTIMATE LABEL DISTRIBUTION RATIO α̂t
Multi-Source Transfer with target labels When the target labels are available, α̂t can be directly estimated from the data without any assumption and α̂t → αt can be proved from asymptotic statistics.
Unsupervised Multi-Source DA In this scenario, it is impossible to estimate a good α̂t without imposing any additional assumptions. Following (Zhang et al., 2013; Lipton et al., 2018; Azizzadenesheli et al., 2019; Combes et al., 2020), we assume that the conditional distributions are aligned between the target and source domains (i.e., St(z|y) = T (z|y)). Then, we denote S̄t(y), T̄ (y) as the predicted t-source/target label distribution through the hypothesis h, and also define CŜt [y, k] = Ŝt[argmaxy′h(z, y
′) = y, Y = k] is the t-source prediction confusion matrix. We can demonstrate that if the conditional distribution is aligned, we have T̄ (y) = T̄α̂t(y), with T̄α̂t(Y = y) = ∑Y k=1 CŜt [y, k]α̂t(k) the constructed target prediction distribution from the t-source information. (See Appendix I for the proof). Then we can estimate α̂t through matching these two distributions by minimizing DKL(T̄ (y)‖T̄α̂t(y)), which is equivalent to:
min α̂t − |Y|∑ y=1 T̄ (y) log( |Y|∑ k=1 CŜt [y, k]α̂t(k)) s.t ∀y ∈ Y, α̂t(y) ≥ 0, |Y|∑ y=1 α̂t(y)Ŝt(y) = 1 (2)
In the aforementioned part, we have assumed the conditional distribution is aligned, which is a feasible requirement in our algorithm, since the goal of g exactly aims at gradually achieving this. In the experiments, we iteratively estimate α̂t and learn g.
Unsupervised Multi-Source Partial DA When supp(T (y)) ⊆ supp(St(y)), αt is sparse due to the non-overlapped classes. Accordingly, in addition to the assumption of St(z|y) = T (z|y) as in unsupervised DA, we also impose such prior knowledge by adding a regularizer ‖α̂t‖1 to the objective of Eq. (2) to induce sparsity in α̂t (See Appendix J for more details).
In training the neural network, since the non-overlapped classes will be automatically assigned with a small or zero α̂t, (g, h) will be less affected by the classes with small α̂t. Our empirical results effectively validate its capability in detecting non-overlapping classes and show significant improvements over other baselines.
4.3 ESTIMATE TASK RELATION COEFFICIENT λ
Inspired by Theorem 1, given fixed α̂t and (g, h), we estimate λ through optimizing the derived upper bound.
min λ ∑ t λ[t]R̂α̂tSt (h, g) + C0 ∑ t λ[t]Ey∼T̂ (y)W1(T̂ (z|Y = y)‖Ŝ(z|Y = y)) + C1 √√√√ T∑ t=1 λ2[t] βt
s.t ∀t,λ[t] ≥ 0, T∑ t=1 λ[t] = 1
(3)
In practice, R̂α̂tSt (h, g) is the weighted empirical prediction error and Ey∼T̂ (y)W1(T̂ (z|Y = y)‖Ŝ(z|Y = y)) is approximated by the dynamic feature centroid distance ∑ y T̄ (y)‖C y t − Cy‖2 (See Appendix L for details). Thus, solving λ is a standard convex optimization problem.

heading: 4.4 ALGORITHM DESCRIPTION
text: Based on the aforementioned components, we present the description of WADN (Algorithm 1) in the unsupervised scenarios (UDA and Partial DA), which iteratively updates (g, h), α̂t, and λ. When
Algorithm 1 Wasserstein Aggregation Domain Network (unsupervised scenarios, one iteration) Require: Labeled source samples Ŝ1, . . . , ŜT , Target samples T̂ Ensure: Label distribution ratio α̂t, task relation simplex λ. Feature Function g, Classifier h, Do-
main critic function d1, . . . , dT , class centroid for source C y t and target C y (∀t = [1, T ], y ∈ Y).
1: . . . DNN Parameter Training Stage (fixed αt and λ) / / / 2: for mini-batch of samples (xS1 ,yS1) ∼ Ŝ1, . . . , (xST ,yST ) ∼ ŜT , (xT ) ∼ T̂ do 3: Predict target pseudo-label ȳT = argmaxyh(g(xT ), y) 4: Compute source confusion matrix for each batch (un-normalized)
CŜt = #[argmaxy′h(z, y ′) = y, Y = k] (t = 1, . . . , T )
5: Compute the batched class centroid for source Cyt and target C y . 6: Moving Average for update source/target class centroid: ( 1 = 0.7) 7: Update Source class centroid Cyt = 1 ×C y t + (1− 1)× C y t 8: Update Target class centroid Cy = 1 ×Cy + (1− 1)× Cy 9: Updating g, h, d1, . . . , dT (SGD and Gradient Reversal), by solving:
min g,h max d1,...,dT ∑ t λ[t]R̂α̂tSt (h, g)︸ ︷︷ ︸
Classification Loss
+ C0 ∑
t λ[t]Ey∼T̄ (y)‖C y t −C y‖2︸ ︷︷ ︸ Explicit Conditional Loss
+ (1− )C0 ∑
t λ[t][Ez∼Ŝt(z)ᾱt(z)d(z)− Ez∼T̂ (z)d(z)]︸ ︷︷ ︸
Implicit Conditional Loss
10: end for 11: . . . Estimation α̂t and λ / / / 12: Compute the global(normalized) source confusion matrix
CŜt = Ŝt[argmaxy′h(z, y ′) = y, Y = k] (t = 1, . . . , T )
13: Solve αt (denoted as {α′t}Tt=1) by (Sec. 4.2 Unsupervised DA or Partial UDA). 14: Update αt by moving average: αt = 1 × αt + (1− 1)× α′t 15: Compute the weighted loss and weighted centroid distance, then solve λ (denoted as λ′) from
Sec. 4.3. And updating λ by moving average: λ = 1 × λ + (1− 1)× λ′
updating λ and αt, we used package CVXPY to optimize the two standard convex losses after each training epoch, then we updating them by using the moving average. As for WADN under target label information, we did not require pseudo-label and directly compute α̂t, shown in Appendix L.

heading: 5 EXPERIMENTS
text: In this section, we compare proposed approaches with several baselines for the popular tasks. For all the scenarios, the following baselines are evaluated: (I) Source method applied only labelled source data to train the model. (II) DANN (Ganin et al., 2016). We follow the protocol of Wen et al. (2020) to merge all the source dataset as a global source domain. (III) MDAN (Zhao et al., 2018); (IV) MDMN (Li et al., 2018b); (V) M3SDA (Peng et al., 2019) adopted maximizing classifier discrepancy (Saito et al., 2018) and (VI) DARN (Wen et al., 2020). For the conventional multi-source transfer and partial unsupervised multi-source DA, we additionally compare specific baselines. All the baselines are re-implemented in the same network structure for fair comparisons. The detailed network structures, hyper-parameter settings, training details are put in Appendix M.
We evaluate the performance on three different datasets: (I) Amazon Review. (Blitzer et al., 2007) It contains four domains (Books, DVD, Electronics, and Kitchen) with positive and negative product reviews. We follow the common data pre-processing strategies as (Chen et al. (2012)) to form a 5000-dimensional bag-of-words feature. Note that the label distribution in the original dataset is uniform. To enhance the benefits of the proposed approach, we create a label distribution drifted task by randomly dropping 50% negative reviews of all the sources while keeping the target identical. (show in Fig.3 (a)). (II) Digits. It consists four digits recognition datasets including MNIST, USPS (Hull, 1994), SVHN (Netzer et al., 2011) and Synth (Ganin et al., 2016). We also create a slight label distribution drift for the sources by randomly dropping 50% samples on digits 5-9 and keep
target identical. (showed in Fig.(3)(b)). (III) Office-Home Dataset (Venkateswara et al., 2017). It contains 65 classes for four different domains: Art, Clipart, Product and Real-World. We used the ResNet50 (He et al., 2016) pretrained from the ImageNet in PyTorch as the base network for feature learning and put a MLP for the classification. The label distributions in these four domains are different and we did not manually create a label drift (showed in Fig.3 (c)).

heading: 5.1 UNSUPERVISED MULTI-SOURCE DA
text: In the unsupervised multi-source DA, we evaluate the proposed approach on all the three datasets. We use a similar hyper-parameter selection strategy as in DANN (Ganin et al., 2016). All reported results are averaged from five runs. The detailed experimental settings are illustrated in Appendix M. The empirical results are illustrated in Tab. 7, 2 and 3. Since we did not change the target label distribution throughout the whole experiments, then we still use the target accuracy as the metric. We report the means and standard deviations for each approach. The best approaches based on a two-sided Wilcoxon signed-rank test (significance level p = 0.05) are shown in bold.
The empirical results reveal a significantly better performance (≈ 3%) on different datasets. For understanding the working principles of WADN, we evaluate the performance under different levels of source label shift in Amazon Review dataset (Fig.1(a)). The results show strong practical benefits for WADN during a gradual larger label shift. In addition, we visualize the task relations in digits (Fig.1(b)) and demonstrate a non-uniform λ, which highlights the importance of properly choosing the most related source rather than simply merging all the data. E.g. when the target domain is SVHN, WADN mainly leverages the information from SYNTH, since they are more semantically similar and MNIST does not help too much for SVHN (observed by Ganin et al. (2016)). The additional analysis and results can be found in Appendix O.

heading: 5.2 MULTI-SOURCE TRANSFER LEARNING WITH LIMITED TARGET SAMPLES
text: We adopt Amazon Review and Digits in the multi-source transfer learning with limited target samples, which have been widely used. In the experiments, we still use shifted sources. We randomly sample only 10% labeled samples (w.r.t. target dataset in unsupervised DA) as training set and the rest 90% samples as the unseen target test set. (See Appendix M for details). We adopt the same
hyper-parameters and training strategies with unsupervised DA. We specifically add a recent baseline RLUS (Konstantinov & Lampert, 2019) and MME (Saito et al., 2019), which also considered transfer learning with the labeled target.
The results are reported in Tabs. 4, 5, which also indicates strong empirical benefits. To show the effectiveness of WADN, we select various portions of labelled samples (1% ∼ 10%) on the target. The results in Fig.1(c) on USPS dataset shows a consistently better than the baselines, even in the few target samples.

heading: 5.3 PARTIAL UNSUPERVISED MULTI-SOURCE DA
text: In this scenario, we adopt the Office-Home dataset to evaluate our approach, as it contains large (65) classes. We do not change the source domains and we randomly choose 35 classes from the target. We evaluate all the baselines on the same selected classes and repeat 5 times. All reported results are averaged from 3 different sub-class selections (15 runs in total), showing in Tab.6. (See Appendix M for details.) We additionally compare PADA (Cao et al., 2018) approach by merging all the sources and use one-to-one partial DA algorithm. We adopt the same hyper-parameters and training strategies with unsupervised DA scenario.
The reported results are also significantly better than the current multi-source DA or one-to-one partial DA approach, which verifies the benefits of WADN: properly estimating α̂t and assigning proper λ for each source.
Besides, we change the number of selected classes (Fig 2(a)), the proposed WADN still indicates consistent better results by a large margin, which indicates the importance of considering α̂t and λ. In contrast, DANN shows unstable results in less selected classes. (See Appendix P for details) Beside, WADN shows a good estimation of the label distribution ratio (Fig 2(b)) and has correctly detected the non-overlapping classes, which indicates its good explainability.

heading: 6 CONCLUSION
text: In this paper, we proposed a new theoretical principled algorithm WADN (Wasserstein Aggregation Domain Network) to solve the multi-source transfer learning problem under target shift. WADN provides a unified solution for various deep multi-source transfer scenarios: learning with limited target data, unsupervised DA, and partial unsupervised DA. We evaluate the proposed method by extensive experiments and show its strong empirical results.

heading: A ADDITIONAL EMPIRICAL RESULTS

heading: B ADDITIONAL RELATED WORK
text: Multi-source transfer learning Practice has been proposed from various prospective. The key idea is to estimate the importance of different sources and then select the most related ones, to mitigate the influence of negative transfer. In the multi-source unsupervised DA, (Sankaranarayanan et al., 2018; Balaji et al., 2019; Pei et al., 2018; Zhao et al., 2019; Zhu et al., 2019; Zhao et al., 2020; 2019; Stojanov et al., 2019; Li et al., 2019b; Wang et al., 2019b; Lin et al., 2020) proposed different practical strategies in the classification, regression and semantic segmentation problems. In the presence of target labels, Hoffman et al. (2012); Tan et al. (2013); Wei et al. (2017); Yao & Doretto (2010); Konstantinov & Lampert (2019) used generalized linear model to learn the target. Christodoulidis et al. (2016); Li et al. (2019a); Chen et al. (2019) focused on deep learning approaches and Lee et al. (2019) proposed an ad-hoc strategy to combine to sources in the few-shot target domains. These ideas are generally data-driven approaches and do not analyze the why the proposed practice can control the generalization error.
Label-Partial Transfer Learning Label-Partial can be viewed as a special case of the label-shift. 1 Most existing works focus on one-to-one partial transfer learning (Zhang et al., 2018; Chen et al., 2020; Bucci et al., 2019; Cao et al., 2019) by adopting the re-weighting training approach without a formal understanding. In our paper, we first rigorously analyzed this common practice and adopt the label distribution ratio as its weights, which provides a principled approach in this scenario.
B.1 OTHER SCENARIOS RELATED TO MULTI-SOURCE TRANSFER LEARNING
Domain Generalization The domain generalization (DG) resembles multi-source transfer but aims at different goals. A common setting in DG is to learn multiple source but directly predict on the unseen target domain. The conventional DG approaches generally learn a distribution invariant features (Balaji et al., 2018; Saenko et al., 2010; Motiian et al., 2017; Ilse et al., 2019) or conditional distribution invariant features (Li et al., 2018a; Akuzawa et al., 2019). However, our theoretical results reveal that in the presence of label shift (i.e αt(y) 6= 1) and outlier tasks then learning conditional or marginal invariant features can not guarantee a small target risk. Our theoretical result enables a formal understanding about the inherent difficulty in DG problems.
Few-Shot Learning The few-shot learning (Finn et al., 2017; Snell et al., 2017; Sung et al., 2018) can be viewed as a very specific scenario of multi-source transfer learning. We would like to point out the differences between the few-shot learning and our paper. (1) Few-shot learning generally involves a very large set of source domains T 1 and each domain consists a modest number of observations NSt . In our paper, we are interested in the a modest number of source domains T but each source domain including a sufficient large number of observations (NSt 1). (2) In the target domain, the few-shot setting generally used K-samples (K is very small) for each class for the fine-tuning. We would like to point out this setting generally violates our theoretical assumption. In
1Since supp(T (y)) ⊆ supp(St(y)) then we naturally have T (y) 6= St(y).
our paper, we assume the target data is i.i.d. sampled fromD(x, y). It is equivalently viewed that we first i.i.d. sample y ∼ D(y), then i.i.d. sample x ∼ D(x|y). Generally the D(y) is non-uniform, thus few-shot setting are generally not applicable for our theoretical assumptions.
Multi-Task Learning The goal of multi-task learning (Zhang & Yang, 2017) aims to improve the prediction performance of all the tasks. In our paper, we aim at controlling the prediction risk of a specified target domain. We also notice some practical techniques are common such as the shared parameter (Zhang & Yeung, 2012), shared representation (Ruder, 2017), etc.

heading: C ADDITIONAL FIGURES RELATED TO THE MAIN PAPER

heading: D TABLE OF NOTATION

heading: E PROOF OF THEOREM 1
text: Proof idea Theorem 1 consists three steps in the proof: Lemma 2. If the prediction loss is assumed as L-Lipschitz and the hypothesis is K-Lipschitz w.r.t. the feature x (given the same label), i.e. for ∀Y = y, ‖h(x1, y)−h(x2, y)‖2 ≤ K‖x1−x2‖2. Then the target risk can be upper bounded by:
RT (h) ≤ ∑ t λ[t]RαtS (h) + LK ∑ t λ[t]Ey∼T (y)W1(T (x|Y = y)‖S(x|Y = y)) (4)
Proof. The target risk can be expressed as: RT (h(x, y)) = E(x,y)∼T `(h(x, y)) = Ey∼T (y)Ex∼T (x|y)`(h(x, y))
By denoting α(y) = T (y)S(y) , then we have:
Ey∼T (y)Ey∼T (x|y)`(h(x, y)) = Ey∼S(y)α(y)Ex∼T (x|y)`(h(x, y))
Then we aim to upper bound Ex∼T (x|y)`(h(x, y)). For any fixed y, Ex∼T (x|y)`(h(x, y))− Ex∼S(x|y)`(h(x, y)) ≤ | ∫ x∈X `(h(x, y))d(T (x|y)− S(x|y))|
Then according to the Kantorovich-Rubinstein duality, for any distribution coupling γ ∈ Π(T (x|y),S(x|y)), then we have:
= inf γ | ∫ X×X `(h(xp, y))− `(h(xq, y))dγ(xp, xq)|
≤ inf γ ∫ X×X |`(h(xp, y))− `(h(xq, y))|dγ(xp, xq)
≤ L inf γ ∫ X×X |h(xp, y))− h(xq, y)|dγ(xp, xq)
≤ LK inf γ ∫ X×X ‖xp − xq‖2dγ(xp, xq)
= LKW1(T (x|Y = y)‖S(x|Y = y))
The first inequality is obvious; and the second inequality comes from the assumption that ` is LLipschitz; the third inequality comes from the hypothesis is K-Lipschitz w.r.t. the feature x (given the same label), i.e. for ∀Y = y, ‖h(x1, y)− h(x2, y)‖2 ≤ K‖x1 − x2‖2. Then we have:
RT (h) ≤ Ey∼S(y)α(y)[Ex∼S(x|y)`(h(x, y)) + LKW1(T (x|y)‖S(x|y))] = E(x,y)∼Sα(y)`(h(x, y)) + LKEy∼T (y)W1(T (x|Y = y)‖S(x|Y = y)) = RαS(h) + LKEy∼T (y)W1(T (x|Y = y)‖S(x|Y = y))
Supposing each source St we assign the weight λ[t] and label distribution ratio αt(y) = T (y)St(y) , then by combining this T source target pair, we have:
RT (h) ≤ ∑ t λ[t]RαtSt (h) + LK ∑ t λ[t]Ey∼T (y)W1(T (x|Y = y)‖St(x|Y = y))
Then we will prove Theorem 1 from this result, we will derive the non-asymptotic bound, estimated from the finite sample observations. Supposing the empirical label ratio value is α̂t, then for any simplex λ we can prove the high-probability bound.
E.1 BOUNDING THE EMPIRICAL AND EXPECTED PREDICTION RISK
Proof. We first bound the first term, which can be upper bounded as: sup h | ∑ t λ[t]RαtSt (h)− ∑ t λ[t]R̂α̂tSt (h)| ≤ sup h | ∑ t λ[t]RαtSt (h)− ∑ t
λ[t]R̂αtSt (h)|︸ ︷︷ ︸ (I)
+ sup h | ∑ t λ[t]R̂αtSt (h)− ∑ t
λ[t]R̂α̂tSt (h)|︸ ︷︷ ︸ (II)
Bounding term (I) According to the McDiarmid inequality, each item changes at most | 2λ[t]αt(y)`NSt |. Then we have:
P ((I)− E(I) ≥ t) ≤ exp( −2t 2∑T
t=1 4 βtN λ2[t]αt(y)2`2
) = δ
By substituting δ, at high probability 1− δ we have:
(I) ≤ E(I) + Lmaxdsup∞ √√√√ T∑ t=1 λ[t]2 βt √ log(1/δ) 2N
Where Lmax = suph∈H `(h) and N = ∑T t=1NSt the total source observations and βt = NSt N the frequency ratio of each source. And d sup ∞ = maxt=1,...,T d∞(T (y)‖S(y)) = maxt=1,...,T maxy∈[1,Y] αt(y), the maximum true label shift value (constant).
Bounding E sup(I), the expectation term can be upper bounded as the form of Rademacher Complexity:
E(I) ≤ 2EσEŜT1 suph T∑ t=1 λ[t] ∑
(xt,yt)∈Ŝt
1
TN (αt(y)`(h(xt, yt))
≤ 2 ∑ t λ[t]EσEŜT1 suph ∑ (xt,yt)∈Ŝt 1 TN (αt(y)`(h(xt, yt))
≤ 2 sup t EσEŜt sup h ∑ (xt,yt)∈Ŝt 1 TN [αt(y)`(h(xt, yt))]
= sup t
2Rt(`,H) = 2R̄(`,H)
Where R̄(`,H) = suptRt(`,H) = supt suph∼H EŜt,σ ∑ (xt,yt)∈Ŝt 1 TN [αt(y)`(h(xt, yt))], represents the Rademacher complexity w.r.t. the prediction loss `, hypothesis h and true label distribution ratio αt.
Therefore with high probability 1− δ, we have:
sup h | ∑ t λ[t]RαtS (h)− ∑ t λ[t]R̂αtS (h)| ≤ R̄(`, h) + Lmaxd sup ∞ √√√√ T∑ t=1 λ[t]2 βt √ log(1/δ) 2N
Bounding Term (II) For all the hypothesis h, we have:
| ∑ t λ[t]R̂αtSt (h)− ∑ t λ[t]R̂α̂tSt (h)| = | ∑ t λ[t] 1 NSt NSt∑ i (α(y(i))− α̂(y(i)))`(h)|
= ∑ t λ[t] 1 NSt | |Y|∑ y (α(Y = y)− α̂(Y = y))¯̀(Y = y)|
Where ¯̀(Y = y) = ∑NSt i `(h(xi, yi = y)), represents the cumulative error, conditioned on a given label Y = y. According to the Holder inequality, we have:
∑ t λ[t] 1 NSt | |Y|∑ y (αt(Y = y)− α̂t(Y = y))¯̀(Y = y)| ≤ ∑ t λ[t] 1 NSt ‖αt − α̂t‖2‖¯̀(Y = y)‖2
≤ Lmax ∑ t λ[t]‖αt − α̂t‖2
≤ Lmax sup t ‖αt − α̂t‖2
Therefore, ∀h ∈ H, with high probability 1− δ we have: ∑ t λ[t]RαtS (h) ≤ ∑ t λ[t]R̂α̂tS (h)+2R̄(`, h)+Lmaxd sup ∞ √√√√ T∑ t=1 λ[t]2 βt √ log(1/δ) 2N +Lmax sup t ‖αt−α̂t‖2
E.2 BOUNDING EMPIRICAL WASSERSTEIN DISTANCE
Then we need to derive the sample complexity of the empirical and true distributions, which can be decomposed as the following two parts. For any t, we have:
Ey∼T (y)W1(T (x|Y = y)‖St(x|Y = y))− Ey∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y)) ≤ Ey∼T (y)W1(T (x|Y = y)‖St(x|Y = y))− Ey∼T (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))︸ ︷︷ ︸ (I)
+ Ey∼T (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))− Ey∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))︸ ︷︷ ︸ (II)
Bounding (I) We have:
Ey∼T (y)W1(T (x|Y = y)‖St(x|Y = y))− Ey∼T (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y)) = ∑ y T (y) ( W1(T (x|Y = y)‖St(x|Y = y))−W1(T̂ (x|Y = y)‖Ŝt(x|Y = y) ) ≤ | ∑ y T (y)| sup y ( W1(T (x|Y = y)‖St(x|Y = y))−W1(T̂ (x|Y = y)‖Ŝt(x|Y = y)
) = sup
y
( W1(T (x|Y = y)‖St(x|Y = y))−W1(T̂ (x|Y = y)‖Ŝt(x|Y = y) ) ≤ sup
y [W1(St(x|Y = y)‖Ŝt(x|Y = y)) +W1(Ŝt(x|Y = y)‖T̂ (x|Y = y))
+W1(T̂ (x|Y = y)‖T (x|Y = y))−W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))] = sup
y W1(St(x|Y = y)‖Ŝt(x|Y = y)) +W1(T̂ (x|Y = y)‖T (x|Y = y))
The first inequality holds because of the Holder inequality. As for the second inequality, we use the triangle inequality of Wasserstein distance. W1(P‖Q) ≤W1(P‖P1) +W1(P1‖P2) +W1(P2‖Q). According to the convergence behavior of Wasserstein distance (Weed et al., 2019), with high probability ≥ 1− 2δ we have:
W1(St(x|Y = y)‖Ŝt(x|Y = y)) +W1(T̂ (x|Y = y)‖T (x|Y = y)) ≤ κ(δ,NySt , N y T )
Where k(δ,NySt , N y T ) = Ct,y(N y St) −st,y +Cy(N y T ) −sy + √ 1 2 log( 2 δ )( √
1 NySt
+ √
1 Nyt ), where NySt is the number of Y = y in source t and NyT is the number of Y = y in target distribution. Ct,y , Cy st,y > 2, sy > 2 are positive constant in the concentration inequality. This indicates the convergence behavior between empirical and true Wasserstein distance.
If we adopt the union bound (over all the labels) by setting δ ← δ/|Y|, then with high probability ≥ 1− 2δ, we have:
sup y W1(S(x|Y = y)‖Ŝ(x|Y = y)) +W1(T̂ (x|Y = y)‖T (x|Y = y)) ≤ κ(δ,NySt , N y T )
where κ(δ,NySt , N y T ) = Ct,y(N y St) −st,y + Cy(N y T ) −sy + √ 1 2 log( 2|Y| δ )( √ 1 NySt + √ 1 NyT )
Again by adopting the union bound (over all the tasks) by setting δ ← δ/T , with high probability ≥ 1− 2δ, we have:∑ t λ[t]Ey∼T (y)W1(T (x|Y = y)‖S(x|Y = y))− ∑ t λ[t]Ey∼T (y)W1(T̂ (x|Y = y)‖Ŝ(x|Y = y)) ≤ sup t κ(δ,NySt , N y T )
Where κ(δ,NySt , N y T ) = Ct,y(N y St) −st,y + Cy(N y T ) −sy + √ 1 2 log( 2T |Y| δ )( √ 1 NySt + √ 1 NyT ).
Bounding (II) We can bound the second term:
Ey∼T (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))− Ey∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))
≤ sup y W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))| ∑ y T (y)− T̂ (y)|
≤ Ctmax| ∑ y T (y)− T̂ (y)|
Where Ctmax = supyW1(T̂ (x|Y = y)‖Ŝ(x|Y = y)) is a positive and bounded constant. Then we need to bound | ∑ y T (y)−T̂ (y)|, by adopting MicDiarmid’s inequality, we have at high probability 1− δ:
| ∑ y T (y)− T̂ (y)| ≤ ET̂ | ∑ y T (y)− T̂ (y)|+
√ log(1/δ)
2NT
= 2EσET̂ ∑ y σT̂ (y) +
√ log(1/δ)
2NT
Then we bound EσET̂ ∑ y σT̂ (y). We use the properties of Rademacher complexity [Lemma 26.11, (Shalev-Shwartz & Ben-David, 2014)] and notice that T̂ (y) is a probability simplex, then we have:
EσET̂ ∑ y σT̂ (y) ≤
√ 2 log(2|Y|)
NT
Then we have | ∑ y T (y)− T̂ (y)| ≤ √ 2 log(2|Y|) NT + √ log(1/δ) 2NT
Then using the union bound and denoting δ ← δ/T , with high probability ≥ 1 − δ and for any simplex λ, we have:∑ t λ[t]Ey∼T (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y)) ≤ ∑ t λ[t]Ey∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝt(x|Y = y))
Cmax(
√ 2 log(2|Y|)
NT +
√ log(T/δ)
2NT )
where Cmax = supt C t max.
Combining together, we can derive the PAC-Learning bound, which is estimated from the finite samples (with high probability 1− 4δ):
RT (h) ≤ ∑ t λtR̂ α̂t St (h) + LH ∑ t λtEy∼T̂ (y)W1(T̂ (x|Y = y)‖Ŝ(x|Y = y)) + Lmaxd sup ∞ √√√√ T∑ t=1 λ2t βt √ log(1/δ) 2N
+ 2R̄(`, h) + Lmax sup t ‖αt − α̂t‖2 + sup t κ(δ,NySt , N y T ) + Cmax(
√ 2 log(2|Y|)
NT +
√ log(T/δ)
2NT )
Then we denote Comp(NS1 , . . . , NT , δ) = 2R̄(`, h) + supt κ(δ,N y St , N y T ) +Cmax(
√ 2 log(2|Y|)
NT +√
log(T/δ) 2NT ) as the convergence rate function that decreases with larger NS1 , . . . , NT . Bedsides, R̄(`, h) = suptRt(`,H) is the re-weighted Rademacher complexity. Given a fixed hypothesis with finite VC dimension 2, it can be proved R̄(`, h) = minNS1 ,...,NST O( √ 1 NSt
) i.e (Shalev-Shwartz & Ben-David, 2014).
2If the hypothesis is the neural network, the Rademacher complexity can still be bounded analogously.

heading: F PROOF OF THEOREM 2
text: We first recall the stochastic feature representation g such that g : X → Z and scoring hypothesis h h : Z × Y → R and the prediction loss ` with ` : R→ R. 3
Proof. The marginal distribution and conditional distribution w.r.t. latent variableZ that are induced by g, which can be reformulated as:
S(z) = ∫ x g(z|x)S(x)dx S(z|y) = ∫ x g(z|x)S(x|Y = y)dx
In the multi-class classification problem, we additionally define the following distributions:
µk(z) = S(Y = k, z) = S(Y = k)S(z|Y = k) πk(z) = T (Y = k, z) = T (Y = k)T (z|Y = k)
Based on (Nguyen et al., 2009) and g(z|x) is a stochastic representation learning function, the loss conditioned a fixed point (x, y) w.r.t. h and g is Ez∼g(z|x)`(h(z, y)). Then taking the expectation over the S(x, y) we have: 4
RS(h, g) = E(x,y)∼S(x,y)Ez∼g(z|x)`(h(z, y))
= |Y|∑ k=1 S(y = k) ∫ x S(x|Y = k) ∫ z g(z|x)`(h(z, y = k))dzdx
= |Y|∑ k=1 S(y = k) ∫ z [ ∫ x S(x|Y = k)g(z|x)dx]`(h(z, y = k))dz
= |Y|∑ k=1 S(y = k) ∫ z S(z|Y = k)`(h(z, y = k))dz
= |Y|∑ k=1 ∫ z S(z, Y = k)`(h(z, y = k))dz
= |Y|∑ k=1 ∫ z µk(z)`(h(z, y = k))dz
Intuitively, the expected loss w.r.t. the joint distribution S can be decomposed as the expected loss on the label distribution S(y) (weighted by the labels) and conditional distribution S(·|y) (real valued conditional loss).
Then the expected risk on the S and T can be expressed as:
RS(h, g) = |Y|∑ k=1 ∫ z `(h(z, y = k))µk(z)dz
RT (h, g) = |Y|∑ k=1 ∫ z `(h(z, y = k))πk(z)dz
3Note this definition is different from the conventional binary classification with binary output, and it is more suitable in the multi-classification scenario and cross entropy loss (Hoffman et al., 2018a). For example, if we define l = − log(·) and h(z, y) ∈ (0, 1) as a scalar score output. Then `(h(z, y)) can be viewed as the cross-entropy loss for the neural-network.
4An alternative understanding is based on the Markov chain. In this case it is a DAG with Y S(y|x)←−−−− X g−→ Z, X S(y|x)−−−−→ Y h−→ S h←− Z g←− X . (S is the output of the scoring function). Then the ex-
pected loss over the all random variable can be equivalently written as ∫ P(x, y, z, s) `(s) d(x, y, z, s) =∫
P(x)P(y|x)P(z|x)P(s|z, y)`(s) = ∫ P(x, y)P(z|x)P(s|z, y)`(s)d(x, y)d(z)d(s). Since the scoring S is determined by h(x, y), then P(s|y, z) = 1. According to the definition we have P(z|x) = g(z|x), P(x, y) = S(x, y), then the loss can be finally expressed as ES(x,y)Eg(z|x)`(h(z, y))
By denoting α(y) = T (y)S(y) , we have the α-weighted loss: RαS(h, g) =T (Y = 1) ∫ z `(h(z, y = 1))S(z|Y = 1) + T (Y = 2) ∫ z `(h(z, y = 2))S(z|Y = 2)
+ · · ·+ T (Y = k) ∫ z `(h(z, y = k))S(z|Y = k)dz
Then we have: RT (h, g)−RαS(h, g) ≤ ∑ k T (Y = k) ∫ z `(h(z, y = k))d|S(z|Y = k)− T (z|Y = k)|
Under the same assumption, we have the loss function `(h(z, Y = k)) is KL-Lipschitz w.r.t. the cost ‖ · ‖2 (given a fixed k). Therefore by adopting the same proof strategy (Kantorovich-Rubinstein duality) in Lemma 2, we have ≤ KLT (Y = 1)W1(S(z|Y = 1)‖T (z|Y = 1)) + · · ·+KLT (Y = k)W1(S(z|Y = k)‖T (z|Y = k)) = KLEy∼T (y)W1(S(z|Y = y)‖T (z|Y = y))
Therefore, we have: RT (h, g) ≤ RαS(h, g) + LKEy∼T (y)W1(S(z|Y = y)‖T (z|Y = y))
Based on the aforementioned result, we have ∀t = 1, . . . , T and denote S = St and α(y) = αt(y) = T (y)/St(y):
λ[t]RT (h, g) ≤ λ[t]RαtSt (h, g) + LKλ[t]Ey∼T (y)W1(St(z|Y = y)‖T (z|Y = y)) Summing over t = 1, . . . , T , we have:
RT (h, g) ≤ T∑ t=1 λ[t]RαtSt (h, g) + LK T∑ t=1 λ[t]Ey∼T (y)W1(St(z|Y = y)‖T (z|Y = y))

heading: G APPROXIMATION W1 DISTANCE
text: According to Jensen inequality, we have W1(Ŝt(z|Y = y)‖T̂ (z|Y = y)) ≤ √ [W2(Ŝt(z|Y = y)‖T̂ (z|Y = y))]2
Supposing Ŝt(z|Y = y) ≈ N (Cyt ,Σ) and T̂ (z|Y = y) ≈ N (Cy,Σ), then we have: [W2(Ŝt(z|Y = y)‖T̂ (z|Y = y)]2 = ‖Cyt −Cy‖22 + Trace(2Σ− 2(ΣΣ)1/2) = ‖C y t −Cy‖22
We would like to point out that assuming the identical covariance matrix is more computationally efficient during the matching. This is advantageous and reasonable in the deep learning regime: we adopted the mini-batch (ranging from 20-128) for the neural network parameter optimization, in each mini-batch the samples of each class are small, then we compute the empirical covariance/variance matrix will be surely biased to the ground truth variance and induce a much higher complexity to optimize. By the contrary, the empirical mean is unbiased and computationally efficient, we can simply use the moving the moving average to efficiently update the estimated mean value (with a unbiased estimator). The empirical results verify the effectiveness of this idea.

heading: H PROOF OF LEMMA 1
text: For each source St, by introducing the duality of Wasserstein-1 distance, for y ∈ Y , we have: W1(St(z|y)‖T (z|y)) = sup
‖d‖L≤1 Ez∼St(z|y)d(z)− Ez∼T (z|y)d(z)
= sup ‖d‖L≤1 ∑ z St(z|y)d(z)− ∑ z T (z|y)d(z)
= 1
T (y) sup ‖d‖L≤1 T (y) St(y) ∑ z St(z, y)d(z)− ∑ z T (z, y)d(z)
Then by defining ᾱt(z) = 1{(z,y)∼St} T (Y=y) St(Y=y) = 1{(z,y)∼St}αt(Y = y), we can see for each pair observation (z, y) sampled from the same distribution, then ᾱt(Z = z) = αt(Y = y). Then we have:∑
y T (y)W1(St(z|y)‖T (z|y)) = ∑ y sup ‖d‖L≤1 { ∑ z αt(y)St(z, y)d(z)− ∑ z T (z, y)d(z)}
= sup ‖d‖L≤1 ∑ z ᾱt(z)St(z)d(z)− ∑ z T (z)d(z)
= sup ‖d‖L≤1 Ez∼St(z)ᾱt(z)d(z)− Ez∼T (z)d(z)
We propose a simple example to understand ᾱt: supposing three samples in St = {(z1, Y = 1), (z2, Y = 1), (z3, Y = 0)} then ᾱt(z1) = ᾱt(z2) = αt(1) and ᾱt(z3) = αt(0). Therefore, the conditional term is equivalent to the label-weighted Wasserstein adversarial learning. We plug in each source domain as weight λ[t] and domain discriminator as dt, we finally have Lemma 1.

heading: I DERIVE THE LABEL RATIO LOSS
text: We suppose the representation learning aims at matching the conditional distribution such that T (z|y) ≈ St(z|y),∀t, then we suppose the predicted target distribution as T̄ (y). By simplifying the notation, we define f(z) = argmaxyh(z, y) the most possible prediction label output, then we have:
T̄ (y) = Y∑ k=1 T (f(z) = y|Y = k)T (Y = k) = Y∑ k=1 St(f(z) = y|Y = k)T (Y = k)
= Y∑ i=1 St(f(z) = y, Y = k)αt(k) = T̄αt(y)
The first equality comes from the definition of target label prediction distribution, T̄ (y) = ET (z)1{f(z) = y} = T (f(z) = y) = ∑Y k=1 T (f(z) = y, Y = k) = ∑Y k=1 T (f(z) = y|Y = k)T (Y = k). The second equality T (f(z) = y|Y = k) = St(f(z) = y|Y = k) holds since ∀t, T (z|y) ≈ St(z|y), then for the shared hypothesis f , we have T (f(z) = y|Y = k) = St(f(z) = y|Y = k). The term St(f(z) = y, Y = k) is the (expected) source prediction confusion matrix, and we denote its empirical (observed) version as Ŝt(f(z) = y, Y = k). Based on this idea, in practice we want to find a α̂t to match the two predicted distribution T̄ and T̄α̂t . If we adopt the KL-divergence as the metric, we have:
min α̂t DKL(T̄ ‖T̄α̂t) = min α̂t Ey∼T̄ log( T̄ (y) T̄α̂t(y) ) = min α̂t −Ey∼T̄ log(T̄α̂t(y))
= min α̂t − ∑ y T̄ (y) log( Y∑ k=1 St(f(z) = y, Y = k)α̂t(k))
We should notice the nature constraints of label ratio: {α̂t(y) ≥ 0, ∑ y α̂t(y)Ŝt(y) = 1}. Based on this principle, we proposed the optimization problem to estimate each label ratio. We adopt its empirical counterpart, the empirical confusion matrix CŜt [y, k] = Ŝt[f(z) = y, Y = k], then the optimization loss can be expressed as:
min α̂t
− |Y|∑ y=1 T̄ (y) log( |Y|∑ k=1 CŜt [y, k]α̂t(k))
s.t. ∀y ∈ Y, α̂t(y) ≥ 0, ∑ y α̂t(y)Ŝt(y) = 1

heading: J LABEL PARTIAL MULTI-SOURCE UNSUPERVISED DA
text: The key difference between multi-conventional and partial unsupervised DA is the estimation step of α̂t. In fact, we only add a sparse constraint for estimating each α̂t:
min α̂t
− |Y|∑ y=1 T̄ (y) log( |Y|∑ k=1 CŜt [y, k]α̂t(k)) + C2‖α̂t‖1
s.t. ∀y ∈ Y, α̂t(y) ≥ 0, ∑ y α̂t(y)Ŝt(y) = 1 (5)
Where C2 is the hyper-parameter to control the level of target label sparsity, to estimate the target label distribution. In the paper, we denote C2 = 0.1.

heading: K EXPLICIT AND IMPLICIT CONDITIONAL LEARNING
text: Inspired by Theorem 2, we need to learn the function g : X → Z and h : Z ×Y → R to minimize:
min g,h ∑ t λ[t]R̂α̂tSt (h, g) + C0 ∑ t λ[t]Ey∼T̂ (y)W1(Ŝt(z|Y = y)‖T̂ (z|Y = y))
This can be equivalently expressed as:
min g,h ∑ t λ[t]R̂αtSt (h, g) + C0 ∑ t λ[t]Ey∼T̂ (y)W1(Ŝt(z|Y = y)‖T̂ (z|Y = y))
+ (1− )C0 ∑ t λ[t]Ey∼T̂ (y)W1(Ŝt(z|Y = y)‖T̂ (z|Y = y))
Due to the explicit and implicit approximation of conditional distance, we then optimize an alternative form:
min g,h max d1,...,dT ∑ t
λ[t]R̂α̂tSt (h, g)︸ ︷︷ ︸ Classification Loss
+ C0 ∑ t
λ[t]Ey∼T̂ (y)‖C y t −Cy‖2︸ ︷︷ ︸
Explicit Conditional Loss + (1− )C0 ∑ t
λ[t][Ez∼Ŝt(z)ᾱ t(z)d(z)− Ez∼T̂ (z)d(z)]︸ ︷︷ ︸
Implicit Conditional Loss
(6)
Where
• Cyt = ∑ (zt,yt)∼Ŝt 1{yt=y}zt the centroid of label Y = y in source St.
• Cy = ∑
(zt,yp)∼T̂ 1{yp=y}zt the centroid of pseudo-label Y = yp in target St. (If it is the unsupervised DA scenarios). • ᾱt(z) = 1{(z,y)∼St}α̂t(Y = y), namely if each pair observation (z, y) from the distribu-
tion, then ᾱt(Z = z) = α̂t(Y = y). • d1, · · · , dT are domain discriminator (or critic function) restricted within 1-Lipschitz func-
tion. • ∈ [0, 1] is the adjustment parameter in the trade-off of explicit and implicit learning.
Based on the equivalence form, our approach proposed a theoretical principled way to tuning its weights. In the paper, we assume = 0.5.
• T̂ (y) empirical target label distribution. (In the unsupervised DA scenarios, we approximate it by predicted target label distribution T̄ (y).)
Gradient Penalty In order to enforce the Lipschitz property of the statistic critic function, we adopt the gradient penalty term (Gulrajani et al., 2017). More concretely, given two samples zs ∼ St(z) and zt ∼ T (z) we generate an interpolated sample zint = ξzs + (1− ξ)zt with ξ ∼ Unif[0, 1]. Then we add a gradient penalty ‖∇d(zint)‖22 as a regularization term to control the Lipschitz property w.r.t. the discriminator d1, · · · , dT .

heading: L ALGORITHM DESCRIPTIONS
text: We propose a detailed pipeline of the proposed algorithm in the following, shown in Algorithm 2 and 3. As for updating λ and αt, we iteratively solve the convex optimization problem after each training epoch and updating them by using the moving average technique.
For solving the λ and αt, we notice that frequently updating these two parameters in the mini-batch level will lead to an instability result during the training. 5 As a consequence, we compute the accumulated confusion matrix, weighted prediction risk, and conditional Wasserstein distance for the whole training epoch and then solve the optimization problem. We use CVXPY to optimize the two standard convex losses. 6
Comparison with different time and memory complexity. We discuss the time and memory complexity of our approach.
Time complexity: In computing each batch we need to compute T re-weighted loss, T domain adversarial loss and T explicit conditional loss. Then our computational complexity is still (O)(T ) during the mini-batch training, which is comparable with recent SOTA such as MDAN and DARN. In addition, after each training epoch we need to estimate αt and λ, which can have time complexity O(T |Y|) with each epoch. (If we adopt SGD to solve these two convex problems). Therefore, the our proposed algorithm is time complexity O(T |Y|). The extra Y term in time complexity is due to the approach of label shift in the designed algorithm.
Memory Complexity: Our proposed approach requires O(T ) domain discriminator and O(T |Y|) class-feature centroids. By the contrary, MDAN and DARN require O(T ) domain discriminator and M3SDA and MDMN require O(T 2) domain discriminators. Since our class-feature centroids are defined in the latent space (z), then the memory complexity of the class-feature centroids can be much smaller than domain discriminators.
5In the label distribution shift scenarios, the mini-batch datasets are highly labeled imbalanced. If we evaluate αt over the mini-batch, it can be computationally expensive and unstable.
6The optimization problem w.r.t. αt and λ is not large scale, then using the standard convex solver is fast and accurate.
Algorithm 2 Wasserstein Aggregation Domain Network (unsupervised scenarios, one iteration) Require: Labeled source samples Ŝ1, . . . , ŜT , Target samples T̂ Ensure: Label distribution ratio α̂t and task relation simplex λ. Feature Learner g, Classifier h,
Statistic critic function d1, . . . , dT , class centroid for source C y t and target C y (∀t = [1, T ], y ∈ Y).
1: . . . DNN Parameter Training Stage (fixed αt and λ) / / / 2: for mini-batch of samples (xS1 ,yS1) ∼ Ŝ1, . . . , (xST ,yST ) ∼ ŜT , (xT ) ∼ T̂ do 3: Predict target pseudo-label ȳT = argmaxyh(g(xT ), y) 4: Compute source confusion matrix for each batch (un-normalized)
CŜt = #[argmaxy′h(z, y ′) = y, Y = k] (t = 1, . . . , T )
5: Compute the batched class centroid for source Cyt and target C y . 6: Moving Average for update source/target class centroid: (We set 1 = 0.7) 7: Source class centroid update Cyt = 1 ×C y t + (1− 1)× C y t 8: Target class centroid update Cy = 1 ×Cy + (1− 1)× Cy 9: Updating g, h, d1, . . . , dT (SGD and Gradient Reversal), based on Eq.(6)
10: end for 11: . . . Estimation α̂t and λ / / / 12: Compute the global(normalized) source confusion matrix
CŜt = Ŝt[argmaxy′h(z, y ′) = y, Y = k] (t = 1, . . . , T )
13: Solve αt (denoted as {α′t}Tt=1) by Equation (2) (Or Eq.(5)) in the partial scenario). 14: Update αt by moving average: αt = 1 × αt + (1− 1)× α′t 15: Compute the weighted loss and weighted centroid distance, then solve λ (denoted as λ′) from
Sec. 2.3. 16: Updating λ by moving average: λ = 0.8× λ + 0.2× λ′
Algorithm 3 Wasserstein Aggregation Domain Network (Limited Target Data, one iteration) Require: Labeled source samples Ŝ1, . . . , ŜT , Target samples T̂ , Label shift ratio αt Ensure: Task relation simplex λ. Feature Learner g, Classifier h, Statistic critic function
d1, . . . , dT , class centroid for source C y t and target C y (∀t = [1, T ], y ∈ Y). 1: . . . DNN Parameter Training Stage (fixed λ) / / / 2: for mini-batch of samples (xS1 ,yS1) ∼ Ŝ1, . . . , (xST ,yST ) ∼ ŜT , (xT ) ∼ T̂ do 3: Compute the batched class centroid for source Cyt and target C
y . 4: Moving Average for update source/target class centroid: (We set 1 = 0.7) 5: Source class centroid update Cyt = 1 ×C y t + (1− 1)× C y t 6: Target class centroid update Cy = 1 ×Cy + (1− 1)× Cy 7: Updating g, h, d1, . . . , dT (SGD and Gradient Reversal), based on Eq.(6). 8: end for 9: . . . Estimation λ / / /
10: Solve λ by Sec. 2.3. (denoted as λ′) 11: Updating λ by moving average: λ = 1 × λ + (1− 1)× λ′

heading: M DATASET DESCRIPTION AND EXPERIMENTAL DETAILS
text: M.1 AMAZON REVIEW DATASET
We used the amazon review dataset (Blitzer et al., 2007). It contains four domains (Books, DVD, Electronics, and Kitchen) with positive (label ”1”) and negative product reviews (label ”0”). The data size is 6465 (Books), 5586 (DVD), 7681 (Electronics), and 7945 (Kitchen). We follow the common data pre-processing strategies Chen et al. (2012): use the bag-of-words (BOW) features then extract the top-5000 frequent unigram and bigrams of all the reviews.
We also noticed the original data-set are label balanced D(y = 0) = D(y = 1). To enhance the benefits of the proposed approach, we create a new dataset with label distribution drift. Specifically, in the experimental settings, we randomly drop 50% data with label ”0” (negative reviews) for all the source data while keeping the target identical, showing in Fig (5).
We choose the MLP model with
• feature representation function g: [5000, 1000] units • Task prediction and domain discriminator function [1000, 500, 100] units,
We choose the dropout rate as 0.7 in the hidden and input layers. The hyper-parameters are chosen based on cross-validation. The neural network is trained for 50 epochs and the mini-batch size is 20 per domain. The optimizer is Adadelta with a learning rate of 0.5.
Experimental Setting We use the amazon Review dataset for two transfer learning scenarios (limited target labels and unsupervised DA). We first randomly select 2K samples for each domain. Then we create a drifted distribution of each source, making each source ≈ 1500 and target sample still 2K.
In the unsupervised DA, we use these labeled source tasks and unlabelled target task, which aims to predict the labels on the target domain.
In the conventional transfer learning, we random sample only 10% dataset (≈ 200 samples) as the target training set and the rest 90% samples as the target test set.
We select C0 = 0.01 and C1 = 1 for these two transfer scenarios. In both practical settings, we set the maximum training epoch as 50.
M.2 DIGIT RECOGNITION
We follow the same settings of Ganin et al. (2016) and we use four-digit recognition datasets in the experiments MNIST, USPS, SVHN, and Synth. MNIST and USPS are the standard digits recognition task. Street View House Number (SVHN) Ganin et al. (2016) is the digit recognition dataset from house numbers in Google Street View Images. Synthetic Digits (Synth) Ganin et al. (2016) is a synthetic dataset that by various transforming SVHN dataset.
We also visualize the label distribution in these four datasets. The original datasets show an almost uniform label distribution on the MNIST as well as Synth, (showing in Fig. 7 (a)). In our paper, we generate a label distribution drift on the source datasets for each multi-source transfer learning. Concretely, we drop 50% of the data on digits 5-9 of all the sources while we keep the target label distribution unchanged. (Fig. 7 (b) illustrated one example with sources: Mnist, USPS, SVHN, and Target Synth. We drop the labels only on the sources.)
MNIST and USPS images are resized to 32 × 32 and represented as 3-channel color images to match the shape of the other three datasets. Each domain has its own given training and test sets when downloaded. Their respective training sample sizes are 60000, 7219, 73257, 479400, and the respective test sample sizes are 10000, 2017, 26032, 9553.
The model structure is shown in Fig. 6. There is no dropout and the hyperparameters are chosen based on cross-validation. It is trained for 60 epochs and the mini-batch size is 128 per domain. The optimizer is Adadelta with a learning rate of 1.0. We adopted γ = 0.5 for MDAN and γ = 0.1 for DARN in the baseline (Wen et al., 2020).
Experimental Setting We use the Digits dataset for two transfer learning scenarios (limited target labels and unsupervised DA). Notice the USPS data has only 7219 samples and the digits dataset is relatively simple. We first randomly select 7K samples for each domain. We create a drifted distribution of each source, making each source ≈ 5300, and the target sample still 7K. In the unsupervised DA, we use these labeled source tasks and unlabelled target task, which aims to predict the labels on the target domain.
In the transfer learning with limited data, we random sample only 10% dataset (≈ 700 samples) as the target training set and the rest 90% samples as the target test set.
We select C0 = 0.01 and C1 as the maximum prediction loss C1 = maxtRαt(h) as the hyperparameters across these two scenarios. The maximum training epoch is 60.
M.3 OFFICE-HOME DATASET
To show the dataset in the complex scenarios, we use the challenging Office-Home dataset (Venkateswara et al., 2017). It contains images of 65 objects such as a spoon, sink, mug, and
pen from four different domains: Art (paintings, sketches, and/or artistic depictions), Clipart (clipart images), Product (images without background), and Real-World (regular images captured with a camera). One of the four datasets is chosen as an unlabelled target domain and the other three datasets are used as labeled source domains.
The dataset size is 2427 (Art), 4365 (Clipart), 4439 (Product), 4357 (Real-World). We follow the same training/test procedure as (Wen et al., 2020). We additionally visualize the label distribution D(y) in four domains in Fig.9, which illustrated the inherent different label distributions. We did not re-sample the source label distribution to uniform distribution in the data pre-processing step. All the baselines are evaluated under the same setting.
We use the ResNet50 (He et al., 2016) pretrained from the ImageNet in PyTorch as the base network for feature learning and put an MLP with the network structure shown in Fig. 10.
Experimental Settings We use the original Office-Home dataset for two transfer learning scenarios (unsupervised DA and label-partial unsupervised DA). We use SGD optimizer with learning rate 0.005, momentum 0.9 and weight decay value 1e-3. It is trained for 100 epochs and the mini-batch size is 32 per domain. As for the baselines, MDAN use γ = 1.0 while DARN use γ = 0.5. We select C0 = 0.01 and C1 as the maximum prediction loss C1 = maxtRαt(h) as the hyper-parameters across these two scenarios.
In the multi-source unsupervised partial DA, we randomly select 35 classes from the target (by repeating 3 samplings), then at each sampling we run 5 times. The final result is based on these 3× 5 = 15 repetitions.
N ANALYSIS ON THE PSEUDO-LABELS

heading: O ANALYSIS IN UNSUPERVISED DA
text: O.1 ABLATION STUDY: DIFFERENT DROPPING RATE
To show the effectiveness of our proposed approach, we change the drop rate of the source domains, showing in Fig.(12). We observe that in task Book, DVD, Electronic, and Kitchen, the results are significantly better under a large label-shift. In the initialization with almost no label shift, the state-of-the-art DARN illustrates a slightly better (< 1%) result.
O.2 ADDITIONAL ANALYSIS ON AMAZON DATASET
We present two additional results to illustrate the working principles of WADN, showing in Fig. (13) and (14).
We visualize the evolution of λ between DARN and WADN, which both used theoretical principled approach to estimate λ. We observe that in the source shifted data, DARN shows an inconsistent estimator of λ Fig. (13). This is different from the observation of Wen et al. (2020). We think it may in the conditional and label distribution shift problem, using R̂S(h(z)) + Discrepancy(S(z), T (z)) to update λ is unstable. In contrast, WADN illustrates a relative consistent estimator of λ under the source shifted data.
In addition, WARN gradually and correctly estimates the unbalanced source data and assign higher wights αt for label y = 0 (first row of Fig.(14)). These principles in WADN jointly promote significantly better results.
O.3 ADDITIONAL ANALYSIS ON DIGITS DATASET
We show the evolution of α̂t on WADN, which verifies the correctness of our proposed principle. Since we drop digits 5-9 in the source domains, the results in Fig. (15) illustrate a higher α̂t on these digits.

heading: P PARTIAL MULTI-SOURCE UNSUPERVISED DA
text: From Fig. (16), WADN is consistently better than other baselines, given different selected classes.
Besides, when fewer classes are selected, the accuracy in DANN, PADA, and DARN is not drastically dropping but maintaining a relatively stable result. We think the following possible reasons:
• The reported performances are based on the average of different selected sub-classes rather than one sub-class selection. From the statistical perspective, if we take a close look at the variance, the results in DANN are much more unstable (higher std) inducing by the different samplings. Therefore, the conventional domain adversarial training is improper for handling the partial transfer since it is not reliable and negative transfer still occurs. • In multi-source DA, it is equally important to detect the non-overlapping classes and find
the most similar sources. Comparing the baselines that only focus on one or two principles shows the importance of unified principles in multi-source partial DA. • We also observe that in the Real-World dataset, the DANN improves the performance by
a relatively large value. This is due to the inherent difficultly of the learning task itself. In fact, the Real-World domain illustrates a much higher performance compared with other domains. According to the Fano lower bound, a task with smaller classes is generally easy to learn. It is possible the vanilla approach showed improvement but still with a much higher variance.
Fig (17), (18) showed the estimated α̂t with different selected classes. The results validate the correctness of WADN in estimating the label distribution ratio.

Review summaries:
In this paper, the authors focus on the label shift problem in multi-source transfer learning and derive new generic principles to control the target generalization risk. They propose a framework that unifies the principles of conditional feature alignment, label distribution ratio estimation, and domain relation weights estimation. A WADN algorithm is proposed for 3 multi-source label shift transfer scenarios:  learning with limited target data, unsupervised DA, and label partial unsupervised DA. The proposed WADN algorithm is validated on different scenarios on common benchmark datasets (Digits, HomeOffice, Amazon Review), and results indicate that it can outperform related SOTA methods for these scenarios. 

This paper aims to provide a unified principle for multi-source transfer learning under label shifts. Based on this principle, this paper claims that a unified algorithm is proposed for various multi-source label shift transfer scenarios: learning with limited target data, unsupervised domain adaptation and label partial unsupervised domain adaptation. The proposed algorithm is validated on three benchmark datasets. The proof seems correct via combining existing single-domain DA theory and the theory regarding Wasserstein distance. The main theorem (Theorem 1) assumes that we can get the label information in the target domain, which is not realistic in many DA problem settings (e.g., UDA or multi-source UDA in this paper). In many DA problem settings, we have to use pseudo labels to replace with true labels in the target domain, which should be analysed in the proposed theorem. However, this paper does not make any efforts to theoretically analyse the effect of pseudo labels, which results in that this paper has very limited impacts on the DA field. Besides, there are some misleading conclusions in this paper.