Algorithms and Theory for Supervised Gradual Domain Adaptation
Authors: Jing Dong
Shiji Zhou
Baoxiang Wang
Han Zhao
Venue: Accepted by TMLR ()

Abstract: The phenomenon of data distribution evolving over time has been observed in a range of applications, calling the needs of adaptive learning algorithms. We thus study the problem of supervised gradual domain adaptation, where labeled data from shifting distributions are available to the learner along the trajectory, and we aim to learn a classifier on a target data distribution of interest. Under this setting, we provide the first generalization upper bound on the learning error under mild assumptions. Our results are algorithm agnostic, general for a range of loss functions, and only depend linearly on the averaged learning error across the trajectory. This shows significant improvement compared to the previous upper bound for unsupervised gradual domain adaptation, where the learning error on the target domain depends exponentially on the initial error on the source domain. Compared with the offline setting of learning from multiple domains, our results also suggest the potential benefits of the temporal structure among different domains in adapting to the target one. Empirically, our theoretical results imply that learning proper representations across the domains will effectively mitigate the learning errors. Motivated by these theoretical insights, we propose a min-max learning objective to learn the representation and classifier simultaneously. Experimental results on both semi-synthetic and large-scale real datasets corroborate our findings and demonstrate the effectiveness of our objectives. 

Published in Transactions on Machine Learning Research (11/2022)
Algorithms and Theory for Supervised Gradual Domain Adap- tation
Jing Dong The Chinese University of Hong Kong, Shenzhen
jingdong@link.cukk..ee www..:wwkkkkkkkkkeeeoee....
Shiji Zhou
zhoushäj000@gmaii..oo
Tsinghua University
Baoxiang Wang
briannguong@euhk.ett.com
The Chinese University of Hong Kong, Shenzhen
Han Zhao
hanzhao@iliiniis..oom edu
University of Ilinois Urbana- Channaaa
Reviewed on OpenReview: https://openrevieet net/ forum? id- 35y5hv9fbb
Abstract
The phenomenon of data distribution evolving over time has been observed in a range of applications, calling for the need for adaptive learning algorithms. We thus study the problem of supervised gradual domain adaplation, where labeled data from shifting distributions are available to the learner along the trajectory, and we aim to learn a classifier on a target data distribution of interest. Under this setting, we provide the first generalization upper bound on the learning error under mild assumptions. Our results are algorithm agnostic, general for range of loss functions, and only depend linearly the averaged learning error across the trajectory. This shows significant improvement compared to the previous upper bound for unsupervised gradual domain adaptation, where the lcarning error on the target domain depends exponentially on the initial error on the source domain. Compared with the offline setting learning from multiple domains, our results also suggest the potential benefits of the temporal structure among different domains in adapting the target one. Empirically, our theoretical results imply that learning proper representations across the domains will effectively mitigate learning errors. Motivated by these theoretical insights, propose min-max learning objective to learn the representation and classifier simultaneously. Experimental results on both semi-synthetic and large-scale real datasets corroborate our findings and demonstrate the effectiveness of our objectives.
1 Introduction
An essential assumption for the deployment of machine learning models real-world applications is the alignment of training and testing data distributions. Under this condition, models are expected to generalize, yet real-world applications often fail to meet this assumption. Instead, continual distribution shift is widely observed in range of applications. For example, satellite images of buildings and lands change over time due to city development (Christie et al. 2018); self-driving cars receive data with quality degrading towards nightfall (Bobu et al. 2018; Wu et al. 2019bb. Although this problem can be mitigated by collecting training data that covers a wide range of distributions, it is often impossible to obtain such a large volume of labeled data in many scenarios. On the other hand, the negligence of shifts between domains also leads to suboptimal performance. Motivated by this commonly observed phenomenon of gradually shifting distributions, we study supervised gradual domain adaptation in this work. Supervised gradual domain adaptation models the training data sequence of batched data with underlying changing distributions, where the ultimate

---

Published in Transactions on Machine Learning Research (11/2022)
goal of learning is to obtain an effective classifier on the target domain at the last step. This relaxation of data alignment assumption thus equips gradual domain adaptation with applicability in wide range of scenarios. Compared with unsupervised gradual domain adaptation, where only unlabeled data is available along the sequence, in supervised gradual domain adaptation, the lcarner also has access to labeled data from the intermediate domains. Note that this distinction in terms of problem setting is essential, as allows for more flexible model adaptation and algorithm designs in supervised gradual domain adaptation.
The mismatch between training and testing data distributions has long been observed, and it had been addressed with conventional domain adaptation and multiple source domain adaptation (Duan et al. 2012 Hoffman et al.) 2013; 2018b a Zhao et al. 2018 Wen et al. 2020; Mansour et al., 2021 in the literature. Compared with the existing paradigms, supervised gradual domain adaptation poses new challenges for these methods, as it involves more than one training domains and the training domains come in sequence. For example, in the existing setting of multiple-source domain adaptation (Zhao et al. 2018 Hoffman et al., 2018a), the learning algorithms try to adapt to the target domain in a onc-off fashion. Supervised gradual domain adaptation, however, is more realistic, and allows the learner to take advantage of the temporal structure among the gradually changing training domains, which can lead to potentially better generalization due to the smaller distributional shift between cach consocutive pair of domains.
Various empirically successful algorithms have been proposed for gradual domain adaptation (Hofman et al.; Gadermayr et al. 2018 Wulfmeier et al.) 2018 Bobu et al. 2018). Nevertheless, we still lack a theoretical understanding of their limits and strengths. The first algoritim-speccfie theoretical guarantee for unsupervised gradual domain adaptation is provided by Kumar et al. (2020). However, the given upper bound of the learning error the target domain suffers from exponential dependency (in terms of the length of the trajectory) on the initial learning error on the source domain. This is often hard to take in reality and it is left open whether this can be alleviated in supervised gradual domain adaptation.
In this paper, we study the problem of gradual domain adaptation under a supervised setting where labels of training domains are available. We prove that the learning error of the target domain is ouly linearly dependent on the averaged error over training domains, showing a significant improvement compared to the unsupervised case. We show that our results are comparable with the learning bound for multiple source training and can be better under certain cases while relaxing the requirement of access to all training domains upfront simultaneously. Further, our analysis is algorithm and loss function independent. Compared to previous theoretical results on domain adaptation, which used 4 distance (Mansour et al. 2009) or W distance to capture shifts between data distributions (Kumar et al. 2020), our results are obtained under milder assumptions. We use Wp Wasserstein distance to describe the gradual shifts between domains, enabling our results to hold under a wider range of real applications. Our bound features two important ingredients to depict the problem structure: sequential Rademacher complexity (Rakhlin al. 2015) used to characterize the sequential structure of gradual domain adaptation while discrepancy measure (Kuznetsov & Mohri 2017 is used to measure the non-stationarity of the sequence.
Our thcoretical results provide insights into empirical methods for gradual domain adaptation. Specifically, our bound highlights the following two observations: (1) Effective representation where the data drift is "small" helps. Our theoretical results highlight an explicit term showing that representation learning can directly optimize the learning bound. (2) There exists an optimal time horizon (number of training domains) for supervised gradual domain adaptation. Our results highlight a trade-off between the time horizon and the learning bound.
Based on the first observation, we propose a min-max learning objective to learn representations concurrently with the classifier. Optimizing this objective, however, requires simultaneous access to all training domains. In light of this challenge, we relax the requirement. of simultaneous access with temporal models that encode knowledge of past training domains. To verify our observations and the proposed objectives, we conduct experiments on both semi-synthetic datasets with MNIST dataset and large-scale real datasets such as FMOW (Christie et al. 2018). Comprehensive experimental results validate our theoretical findings and confirm the effectiveness of our proposed objective.
2

---

Published in Transactions on Machine Learning Research (11/2022)
2 Related Work
(Multiple source) domain adaptation Learning with shifting distributions appears in many learning problems. Formally referred as domain adaptation, this has boen extensively studied in a variety of scenarios,
inchuding computer vision [Hofmman et al.; Venkateswara et al. 2017 Zhao et al. 2019b), natural language
processing (Blitzer et al. 2006; 2007; Axclrod ct al. [011]; and speech recognition (Sun et al. 2017 Sim et al. 2018). When the data labels of the target domain are available during training, known as supervised
domain adaptation, several parameter regularization- based methods (Yang et al. 2007 Aytar & Zisserman
2011). feature transformations based methods (Saenko et al. 2010 Kulis et al. 2011) and a combination of
the two are proposed (Duan et al. 2012: Hoffman et al., 2013). On the thcoretical side of domain adaptation,
Ben-David et al. (010)) investigated the necessary assumplions for domaii adaptations, which specifies that,
either the domains are needed to be similar, or there exists a classifier in the hypothesis class that can attain low error on both domains. For the restriction on the similarity of domains, [Wu ct al. (2019a) proposed an asymmetrically-relaxed distribution aligument for an alternative requirement. This is more general condition for domain adaptation when compared to those proposed by Ben-David et al. (2010). and holds in more general setting with high-capacity hypothesis classes such as neural networks. Zhao et al. (2019a) then focused on the efficiency of representation learning for domain adaption and characterized a trade-off between learning an invariant representation across domains and achieving small errors on all domains. This is then extended to a more general setting by Zhao et al. (2020), which provides a geometric charactorization of feasible regions in the information plane for invariant representation learning. The problem of adapting with multiple training domains, referred to as multiple source domain adaptation (MDA), is also studied extensively. The first asymptotic learning bound for MDA is studied by Hoffman et al. (2018a). Follow-up work Zhao et al. 2018)) provides the first generalization bounds and proposed efficient adversarial neural networks to demonstrate empirical superiorily. The theoretical results are further explored by [en et al.] (2020) with a generalized notion of distance measure, and by Mansour et al. 2021 when only limited target labeled data are available.
Gradual domain adaptation Many real-world applications involve data that come in sequence and are continuously shifting. This first attempt addresses the setting where data from continuously evolving distribution with novel unsupervised manifold-basee based adaptation method (Hoffman et al.). Following works Gadermayr et al. (2018): Wulfmeier et al. 2018): : Bobu et al. 20188) also proposed unsupervised approaches for this variant of gradual domain adaptation with unsupervised algorithms. The first to study the problem of adapting to an unseen larget domain with shifting training domains is Kunar et al. (2020). Their result. features the first theoretical guarantee for unsupervised gradual domain adaptation with a self-training algorithm and highlights that learning with a gradually shifting domain can be potentially much more beneficial than a Direct Adaptation. The work provides a theoretical understanding of the effectiveness of empirical tricks such as regularization and label sharpening. However, they are obtained under rather stringent assumptions. They assumed that the label distribution remains unchanged while the varying class conditional probability between any two consecutive domains has bounded Wo Wasserstein distance, which only covers a limited number of cases. Moreover, the loss functions are restricted to be the hinge loss and ramp loss while the classifier is restricted to be linear. Under these assumptions, the final learning error is bounded by (T)x)(T)aoo, where T is the horizon length and ag is the initial learning error on the initial domain. This result is later extended by Chen et al. (2020) with linear classifiers and Gaussian spurious features and improved by concurrent. independent work Wang et al. (2022) to O(ag T) in the setting of unsupervised gradual domain adaptation. The theoretical advances
complemented by recent empirical success in gradual domain adaptation. Recent work Chen & Chao (2021) extends the unsupervised gradual domain adaptation problem to the case where intermediate domains are not already available. [Abaa et al. (2021) and Sagawa et al. 22021] provide the first comprehensive benchmark and datasets for both supervised and unsupervised gradual domain adaptation.
3 Preliminaries
The problem of gradual domain adaptation proceeds sequentially through a finite time horizon (1...., ........ TT with evolving data domains. A data distríbution P. E Rdd x RR is realized at each time step with the features
3

---

Published in Transactions on Machine Learning Research (11/2022)
denoted as X Rd and labels as Y E R With a given loss function ((:-)), we are interested in obtaining effective classifier h E H : IR + R that minimizes a given loss function on the target domain Pr, which is also the last domain. With access to only n samples from each intermediate domain PI...., ,r,r we seek to design algorithms that output a classifier at each time step where the final classifier performs well on the target domain.
Following the prior work (Kumar et al. 2020 we assume the shift is gradual. To capture such a gradual shift, we use the Wasserstein distance to measure the change between any two consecutive domains. The Wasserstein distance offers way to include a large range of cases, including the case where the two measures of the data domains are not on the same probability space (Cai & Lim 2020).
Definition 3.1. (Wasserstein distance) The p-th Wasserstein distance, denoted as W, distance, between two probability distribution P. P.Q is defined as W, (P, Q) = (inf I 1| vll'd 1/p where T(P,Q) denotes the set of all joint distribution y over (X, Y) such that X ~ P, ~ Q.
Intuitively, Wasserstein distance measures the minimum cost needed to move one distribution to another. The flexibility of Wasserstein distance enables us to derive light theoretical results for a wider range of practical applications. In comparison, previous results leverage I distance (Mansour et al. 2009) the Wasserstein-infniity Wo distance (Kumar et al. 2020) to capture non-stationarity. In practice, however, this is rarely used and W1 is more commonly employed due to its low computational cost. Moreover, even if pairs of data distributions are close to each other in terms of W1 distance, the Wx distance can be unbounded with a few presences of outlier data. Previous literature hence offers limited insights whereas our results include this more general scenario. We formally describe the assumptions below.
Assumption 3.1. For all StsT-1 and some constant A 0, the p-th Wasserstein distance between two domains is bounded as (X,, P(t, S.
We study the problem without restrictions on the specific form of the loss function, and only assumee that the empirical loss function is bounded and Lipschitz continuous. This covers rich class of loss functions, including the logistic massniiaryy cross-entropy, and hinge loss. Formally, let ly be the loss function, l,- = (((())) y): X' x y + TR. We have the following assumption.
Assumption 3.2. The loss function ly : X x y + R is p-Lipschitz continuous with respect to (z, (2.y), denoted as ||4 Lip I p, and bounded such that ||eA S M.
This assumption is general as it holds when the input data are compact. Moreover, we note that this assumption is mainly for the convenience of technical analysis and is common in the literature (Mansour
et al. 2009 Cortes & Mohri 2011 Kumar et al. 2020
The gradual domain adaptation investigated in this paper is thus defined as follows
Definition 3.2 (Gradual Domain Adaptation). Given a finite time horizon (1...., T,, at each time step t, a data distribution Ps over Rd x R is realized with the features X E Rd and labels Y E RR. The data distributions are gradually evolving subject to Assumption 3.1, With a given loss function E(:,-) that satisfies Assumption 3.2, the goal is to obtain a clossifier h E I - R& that mènimizes the given loss function on the target domain Pr with access to only n samples from each intermediate domain PI....,Pr. Pr-1-
Our first tool is used to help us characterize the structure of sequential domain adaptation. Under the statistical learning scenario with i.i.d. data, Rademacher complexity serves as a well-known complexity notion to capture the richness of the underlying hypothesis space. However, with the sequential dependence, classical notions of complexity are insufficient to provide a description of the problem. To capture the difficulty of sequential domain adaptation, we use the sequential Rademacher complexity, which was originally proposed for online learning where data comes one by one in sequence (Rakhlin et al., 2015).
Definition 3.3 (Z-valued tree Rakhlin et al. (2015)). A Z-value tree is a sequence (21,..., 2T) of T mappings, 21 : [= + Z,t [, A path in the tree is (f,,...,(r-1) (+1)T-1. To simplify the nolations, we wrile 2. (+) 21 21(e1,...,
Definition 3.4 (Sequential Rademacher Complexity Rakhlin et al. 2015 ) For a function class F, the sequential Rademacher complexity is defined as Atp (F) = supp E sup 7 En eat (z((e)) where the
4

---

Published in Transactions on Machine Learning Research (11/2022)
supremum is taken over all Z-valued trees (Definition 3.3. of depth T and (c1....,er) are Rademacher random wariahles.
We next introduce the discrepancy measure, a key ingredient that helps us to characterize the non-stationarity resulting from the shifting data domains. This can be used to bridge the shift in data distribution with the shift in errors incurred by the classifier. To simplify the notation, we let 2 (X, (XY) and use shorthand z for ,i....,yy Zr.
Definition 3.5 (Discrepancy measure Kuznetsov & Mohri 2020
T
diser = sup hEH
(( (XT, Y7) - 7
Σ E (X,, Y2)
(1)
where zi is defined to be the empty set, in which case the expectation is equivalent the unconditional case.
We will later show that the discrepancy measure can be directly upper-bounded when the shift in class conditional distribution gradual. We also note that this notion is general and feasible be estimated from data in practice (Kuznetsov & Mohri 2020). Similar notions have also been used extensively in non-stationary
time series analysis and mixing processes [Kuznetsov & Mohri 2014 2017
4 Theoretical Results
In this section, we provide our theoretical guarantees for the performance of the final classifier learned in the setting described above. Our result is algorithm agnostic and general to loss functions that satisfy Assumption We then discuss the implications of our results and give a proof sketch to illustrate the main ideas.
3.2
The following theorem gives an upper bound of the expected loss of the learned classifier on the last domain in terms of the shift A, sequential Rademacher complexity, etc.
Theorem 4.1. Under Assumptions 3.1 2 with n data points access to each data distribution Pt, t E (1....,77 T}, and loss function e, = ((h(x),)) v) X y + R. the loss on the last distribution incurred by a classifier hr obtained through empérically minimizing the loss on each domains can be upper bounded by
E 1en (x),
7
3M
VCdim (H) + log(2/8)
< E Cno (Xr, Yr)
z -T-11
+
+
8 llog
+0
T
T
T
2n
VnT
Ei
+ 18M / log T T (F) + p4
(2)
Es
(F) is the sequential Rademacher complerity of F, VCdim(H) is the VC dimension of H. and ho = argminnen # ΣT= (h((,)) Yi).
where l F, 29
When ln E F is bounded and convex, the sequential Rademacher complexity term is upper bounded by O(VI/nT) (Rakhlin et al. 2015). For some complicated function classes, such as multi-layer neural networks, they also enjoy a sequential Rademacher complexity of order O( ((TT/TT) (Rakhlin et al. 2015). Before we move to present a proof sketch of Theorem 4.1 first discuss the implications of our theorem.
Remark 4.1. There erists a non-trivial trade-off between E1 + Eg and Es through the length T. When T is larger, all terms except. for the lerms in Eg will be smaller while the lerms in Egg will be larger. Hence, il is not always beneficial to have longer trajectory.
Remark 4.2. All terms in [ except for the last term 3T P are determined regordless of the algorithm. The last term depends on A which measures the closs conditional distance between any two consecutive domains. This distance can potentially be minimized through learning an effective represenlation of data.
5

---

Published in Transactions on Machine Learning Research (11/2022)
Comparison with unsupervised gradual domain adaptation Our result is only linear with respect to the horizon length T and the average loss I. [Eno (Xr, Vr) | - where ho arx + E' +=== (l((),)))) In contrast, the previous upper bound given by Kumar et al. (2020), which is for unsupervised gradual domain adaptation, is (Tex))))an) with on being the initial error on the initial domain. It remains unclear, however, if the exponential cost is unavoidable when labels are missing during training as the result by Kumar et al. (2020) is algorithm specific.
Comparison with multiple source domain adaptation The sctting of multiple source domain adapta- tion neglects the temporal structure between training domains. Our results are comparable while dropping the requirement of simultaneous access to all training domains. Our result suffers from the same order of error with respect to the Rademacher complexity and from the VC inequality with supervised multiple source domain adaptation (MDA) (Wen et al., 2020), which is O ((E,ostaa (X,, Y2) + R(F)), where E, a 1, 0z > 0, Vt and R(F being the Rademacher complexity. Tanplleity.Takingggg... the weights ar 7: the error of classifier h on the target domain similarly relies on the average error of h training domains. We note that in comparison our results scale with the averaged error of the best classifier on the training domains.
While we defer the full proof to the appendix, we now present a sketch of the proof.
Proof Sketch With Assumption 3.1 we first show that when the Wasserstein distance between two consecutive class conditional distributions is bounded, the discrepancy measure is also bounded.
Lemma 4.1. Under Assumption 3.2. the expected loss on two consecutive domains satisfy (x, E. (X', Y'I S pا, where J., v are the probability measure for Pt. Pe+1, (X,Y) ~ Pt, and (X,Y) ~ PL+1.
Then we leverage this result to bound the loss incurred in expectation by the same classifier on two consecutive data distributions. We start by decompasing the discrepancy mcasure with adjustable summation term
T
T
diset S sup NCH
Σ 1+-
E (X,,
Σ
e (X,,
T
+ sup heи
E (XT, Yr)
-
Σ
E [ (X,, Y2) 2
(=T-++1
We show by manipulating this adjustable summation, the discrepancy measure can indeed be directly obtained We now start to bound the learning error in interest by decomposing
through application of Lemma 4.1
1 T-1
EE [ehr (Xr, - - E [eno (Xr, - <20(2)))
+
T Phr (Xe, Xi)
Σ T
lno (XT, Xr)
7 E Hen (X., V.). The term & (Hf) can be upper bounded by Lemina B.1 Kuznetsov & Mohri (020)) and thus it is left to bound the remaining term Ei tno (Xr, Yr). To upper bound this difference of average loss, we first compare the loss incurred by a classifier learned by an optimal online learning algorithu to fo- By classic online learning theory results, the difference is upper bounded by O
where $ (zf) = SuPREM E [e (Xr, Yr)
# ET [laz (X,,Y))
Then we compare the optimal
n online learning classifier to our final classifier by and upper bound the difference through the VC inequality Bousquet ct al. 2004).
Lastly, we leverage Corollary 3 of Kuznetsov & Mohri 2020 with our terms to complete the proof.
5 Insights for Practice
The key insight indicated by Theorem 4.1 and Remark 4.2 is that the bottleneck of supervised gradual domain adaption is not only predetermined through the sctup of the problem but also relies heavily on مL, where A is the upper bound of the Wasserstein class conditional distance between two data domains and p is the Lipschitz constant of the loss function. In practice, the loss function is often chosen beforehand and
6

---

Published in Transactions on Machine Learning Research (11/2022)
remains unchanged throughout the learning process. Therefore, the only term available to be optimized is A, which can be effectively reduced if good representation of data can be learned for ilassification We give a feasible primal-dual objective that learns a mapping function from input to feature space concurrently with the original classification objective
A primal-dual objective formulation Define g to be a mapping that maps X E R to some feature space. We propose the learning objective as learn classifier h simultancously with the mapping function g with the exposure of historical data 7 With the feature g(X) from the target domain, our learning objective is now E (XT),, Yr)) -inff of E [e (g" (Xr), "r) Intuitively, this can be viewed as combination of two optimization problems where both A and the learning loss are minimized.
The objective is hard to evaluate without further assumptions. Thus we restrict our study to the case where both g and h are parametrizable. Specifically, we assume g is parameterized by w and h is parameterized by 0. Then we leverage the Wasserstein-1 distance's dual representation (Equation 3 Kantorovich & Rubinsteen (1958) to derive an objective for learning the representation,
/ ((x))P(()) / (u)d sup (ET(P.))
(), = sup
- -
(3)
*ET(P.Q)
With this, the following primal-dual objective can be used to concurrently find the best-performing classifier and representation mapping,
min max E [Cho.r (XT), | ALp.
(4)
where LD max, Ep, I (Xx)) - E.... l (Xe-)) and À is tunable parameter.
One-step and temporal variants Notice that LD relies on the maximum distance across all domains. It is thus hard to directly evaluate Ln without simultaneous access to all domains. With access only to the current and the past domains, we could optimize the following one-step primal-dual loss at time t instead.
min max [Cho.. (sw X.) Zi] + ALD.,
(5)
where LD, = Es, Iew (X,)) - Er (X
Compared the objective 4 the one-step loss (5) only gives us partial information, and directly optimizing it may often lead to suboptimal performance. While it is inevitable to optimize with some loss of information under the problem setup, we use temporal model (like LSTM) to help preserve historical data information in the process of learning mapping function g. In particular, in the temporal variant, will be using the hidden states of an LSTM to dynamically summarize the features from all the past domains. Then, we shall use the feature distribution computed from the LSTM hidden state to align with the feature distribution at the current time step.
To practically implement these objectives, we can use neural networks learn the representation and the classifier, and another neural network is used a critic to judge the quality of the learned representations. To minimize the distance between representations of different domains, metric. Then the distance of the critic of the representations in different domains is then minimized to encourage the learning of similar representations. We note that the use of W, distance, which is casy to evaluate empirically, to guide representation learning has been practiced before (Shen et al. 2018). We take this approach further to the problem of gradual domain adaption.
use W₁ distance
empirical
6 Empirical Results
In this section, we perform experiments to demonstrate the effectiveness of supervised gradual domain adaptation and compare our algorithm with No Adaptation, Direct Adaptation, and Multiple Source Domain Adaptation (MDA) on different datasets. We also verify the insights we obtained in the previous section by answering the following three questions:

---

Published in Transactions on Machine Learning Research (11/2022)
1. How helpful is representation learning in gradual domain adaptation? Theoretically, elfective representation where the data drift is "small" helps algorithms to gradually adapt to the evolving domains, This corresponds to minimizing the م term in our Theorem 4.1 We show that our algorithm with objective (5) outperforms the objective empirical risk (No Adaptation).
Can the one-step primal-dual loss (5) act as an substitute to optimization objective (4) Inspired by our theoretical results (Theorem 4.1), the primal-dual optimization objective (4) should guide the adaptation process. However, optimization of this objective requires simultaneous access to all data domains. We use temporal encoding (through temporal model such as LSTM) of historical data to demonstrate the importance of the information of past data domains. We compare this to results obtained with a convolutional network (CNN)-based model to verify that optimizing 5 with a temporal model could largely mitigate the information loss.
the one-step loss
Does the length of gradual domain adaptation affect the model's ability to adapt? Our theoretical results suggest that there exists an optimal length for gradual domain adaptation. Our empirical results corroborate this as when the time horizon passes a certain threshold the model performance is saturated.
6.1 Experimental Setting
We conduct our experiments on Rotating MNIST, Portraits, and FMOW, with a detailed description of each dataset in the appendix. We compare the performance of no adaptation, direct adaptation, and multiple source domain adaptations with gradual adaptation. The implementation of each method is also included in the appendix. Each experiment repeated over random seeds and reported with the mean and 1 std.
6.2 Experimental Results
Table Results on rotating MNIST dataset with Gradual Adaptation on domains, Direct Adaptation, and
No Adaptation.
Rotating MNIST with domains
Gradual Adaptation
Direct Adaptation
No Adaptation
CNN
LSTM
CNN
LSTM
CNN
0-30 degree
90.21 + 0.48
94.83 + 0.49
77.97 + 0.99
89.72 + 0.73
79.76 + 3.20
0-60 degree
87.35 1.02
92.52 + 0.25
73.27 + 1.51
88.53 0.76
58.36 + 2.59
0-120 degree
82.38 + 0.57
89.72 + 0.35
62.52 + 1.06
84.30 + 2.60
38.25 + 0.61
Table 2: Results on rotating MNIST dataset (5 domains) with Gradual Adaptation, MDA (MDAN)
Zhao
et al. 2018 and Meta-learning (EAML) (Liu et al. 2020
Rotating MNIST with 5 domains
Gradual Adaptation
MDAN
EAML
Dynamic
CNN
LSTM
Maxmin
Dynamic
with last domains
CNN
0-30 degree
90.21 + 0.48
9.83 = 0.49
93.62 = 0.87
95.79 + 0.33
83.04 + 0.29
79.10 + 6.99
0-60 degree
87.35 + 1.02
92.52 + 0.25
91.99 = 0.51
92.27 + 0.26
61.49 + 0.72
54.64 + 4.08
0-120 degree
82.38 + 0.57
89.72 + 0.35
87.28 + 0.52
88.57 + 0.21
41.14 + 1.77
17.91 + 10.34
8

---

Published in Transactions on Machine Learning Research (11/2022)
Table Results on FMOW with Gradual Adaptation with 3 domains, Direct Adaptation, and No Adaptation.
FMOW
No Adaptation with ERM
Direct Adaptation with CNN
Gradual Adaptation with CNN
Gradual Adaptation with LSTM
30 + 1.94
41.94 = 2.73
36.86 1.91
43.52 1.40
Learning representations further help in gradual adaptation
On rotating MNIST, the performance of the model better in most cases when adaptation is considered (Table D. which demonstrates the benefit of learning proper representations. With a CNN architecture, the only exception is when the shift in the domain is relatively small (0 to 30 degree), where the No Adaptation method achieves higher accuracy than the Direct Adaptation method by 2%. However, when the shift. in domains is relatively large, Adaptation methods are shown to be more successful in this case and this subtle advantage of No Adaptation no longer holds. Furthermore, Gradual Adaptation further enhances this outperformance significantly. This observation shows the advantage of sequential adaptation versus direct. adaptation. We further show that the performance of the algorithm monotonically increases as progress
Table 4: Results on Portraits with Gradual Adaptation for different lengths of horizon T, Direct Adaptation, and No Adaptation.
Portraits
CNN
LSTM
No Adaptation
76.01 + 1.45
N/A
Direct Adaptation
86.86 + 0.84
N/A
Gradual 5 Domains
87.77 + 0.98
87.41 + 0.76
Gradual Domains
89.14 = 1.64
89.15 1.12
Gradual 9 Domains
90.46 = 0.54
89.88 + 0.54
Gradual 11 Domains
90.56 = 1.21
90.93 + 0.75
Gradual - 12 Domains
91.45 - 0.27
90.73 + 0.66
Gradual 13 Domains
90.54 + 0.90
91.13 + 0.35
Gradual - 14 Domains
90.58 = 0.38
90.35 - 0.71
to adapt each domain and learn a cross-domain representation. Figure 1b shows the trend in algorithm performance on rotating MNIST and FMOW.
One-step loss is insufficient as a substitute, but can be improved by temporal model The inefficiency of adaptation without historical information appears with all datasets we have considered, reflected through Table 3 In almost all cases, we observe that learning with temporal model (LSTM) achieves better accuracy than convolutional model (CNN). The gap is especially large on FMOW, the large-scale dataset in our experiments. We suspect that optimizing with only partial information can lead to suboptimal performance on such a complicated task. This is reflected through the better performance achieved by Direct Adaptation with CNN when compared to Gradual Adaptation with CNN and 3 domains (Table 8) In contrast, Gradual Adaptation with LSTM overtakes the performance of Direct Adaptation, suggesting the importance of historical representation. Another evidence is that Figure Ib shows that Gradual Adaptation with a temporal model performs better all indexes of domains rotating MNIST and FMOW.
9

---

Published in Transactions on Machine Learning Research (11/2022)
Accuracy
Accuracy
40
20
(CNN]
Gredual [LS] MI
Grad ual (CNN)
Grad (LSTM)
Direct Adapration
No Adaptation
MDA
MDA (Last 21
Direct Adaptation
1.5
Index of domain
Index of domain
(a) Rotating MNIST
(b) FMOW
PCA projection of learnt representations
PCA projection of learnt representations
Target
Distance between source and Langet representations
Luclidean diserree
Index of domains
(c) PCA projection
(d) Plot of euclidean distance
Figure 1: Figure
1a compares the training curves rotating MNIST with maximum rotation of 120 1b compares the training curves on FMOW. Figure I is the PCA projection plot of Iearned plots the Euclidean distance to the larget domain of the project ions of learned
degroes. Figure
representation and Figure Id
representations.
Existence of optimal time horizon With the Portraits dataset and different lengths of horizon T, verify that then optimal time horizon be reached when model performance saturated in Table The performance of the model increases drastically when the shifts in domains considered, shown by the difference in the performance of No Adaptation, Direct Adaptation, and Gradual Adaptation with 5 and 7 domains. However, this increase in performance becomes relatively negligible when T is large (the performance gain is saturated when the horizon length is 9 - 14). This rate of growth in accuracy implies that there exists an optimal number of domains.
Lastly, we remark on the results (Table and achieved by Gradual Adaptation in comparison with MDA methods (MDAN (Zhao al., 2018)) DARN (Wen et al. 2020 and Fish (Shi et al. 2022 ). On Rotating MNIST, note that Gradual Adaptation outperforms MDA methods when the shift is large (60 and 120 degree rotation) while relaxing the requirement of simultaneous access to all source domains. It is only when the shift is relatively small (30-degree rotation), MDA method DARN achieves a better result than ours. When the MDA method is only presented with the last. two training domains, Gradual Adaptation offers noticeable advantages regardless of the shift in the domains (Table 2 This demonstrates the potential of graduate domain adaptation in real applications that even when the data are simultancously presented is possible to achieve competitive or even better performance. One possible reason for this be illustrated by Figure Td in which we plot the PCA projections and the
Comparison with MDA
10

---

Published in Transactions on Machine Learning Research (11/2022)
Table 5; Results on rotating MNIST dataset with Gradual Adaptation on 5 domains and MDA methods,
Fish (Shi et al. 2022) and DARN (Wen al. 2020)
Fish
DARN
Ours
0-30 degree
95.83 = 0.13
94.20 + 0.27
94.83 0.49
0-60 degree
90.57 + 0.37
89.50 + 0.12
92.52 + 0.25
0-120 degree
83.26 + 1.58
82.28 + 2.42
89.72 + 0.35
Euclidean distance to the target domain of learned representations. From Figure ld gradual domain adaptation method is able to gradually learn an increasingly closer representation of the source domain to the larget domain. This helps our method to make our prediction based on more relevant. features while MDA methods may be hindered by sot-sa-relevant features from multiple domains.
we see that the
Comparison with Meta-learning In addition comparing our method with those achieved by domain adaptation methods, we also compare work with Meta-learning for evolving distributions (FAMI. (Liu ct al. 2020)). In contrast to gradual domain adaptation, these methods instead assume that the testing distribution is gradually evolving and thus the learned classifier is desired to be adaptive to these changing targets. In addition, the learned classifier is also asked to "not forget". Due to the different objectives, we can see that the baseline method (EAML) is suboptimal on a fixed target with changing training distributions, when compared to our method (Table
7 Conclusion
We studied the problem of supervised gradual domain adaplation, which arises naturally in applications with temporal nature. In this setting, we provide the first learning bound of the problem and our results are general to range of loss functions and are algorithm agnostic. Basod on the thcoretical insight offered by our theorem, designed a primal-dual learning objective to learn effective representation across domains while learning a classifier. We analyze the implications of our results through experiments on wide range of datasets.
Acknowledgements
We want to thank the reviewers and the editors for their constructive comments during the review pro- cess. Jing Dong and Baoxiang Wang are partially supported by National Natural Science Foundation of China (62106213, 72150002) and Shenzhen Science and Technology Program (RCBS2001060910433360 JCY11202200221220011009)) Han Zhao would like thank the support from a Facebook research award.
References
Samira Abnar, Rianne van den Berg, Golnaz Ghiasi, Mostafa Dehghani, Nal Kalchbrenner, and Hanie Sedghi. Gradual domain adaptation in the wild: When intermediate distributions are absent. ar preprint arXiv:2106.0600 2021.
Amittai Axelrod, Xiaodong He, and Jianfeng Gao. Domain adaptation via pseudo in-domain data selection. In Conference Empirical Methods in Natural Language Processing, 2011.
Yusuf Aytar and Andrew Zisserman. Tabula rasa: Model transfer for object category detection. In International Conference Computer Vision, 2011.
Shai Ben-David, Tyler Lu, Teresa Luu, and Dávid P&l. Impossibility theorems for domain adaptation. In International Conference on Artificial Intelligence and Statistics, 2010.
John Blitzer, Ryan McDonald, and Fernando Percira. Domain adaptation with structural correspondence learning. In Conference Empirioal Methods in Natural Language Processing, 2006.
11

---

Published in Transactions on Machine Learning Research (11/2022)
John Blitzer, Mark Dredze, and Fernando Pereira. Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification. In Annual meeling of the association of compulational linguistics, 2007.
Andreea Bobu, Eric Tzeng, Judy Hoffman, and Trevor Darrell. Adapting to contimuously shifting domains. In International Conference on Learning Representations Workshop, 2018.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction statistical learning theory. Advanced Lectures Machine Learning, pp. 169-207, 2004.
Yuhang Cai and Lek-Heng Lim. Distances between probability distributions of different dimensions. arXiv preprint weXx::2011.0000 1.00629, 2020.
Hong- You Chen and Wui Chao, Gradual domain adaptation without indexed intermediate domains. Advances in Newral Information Processing Systems, 2021.
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift. Advances in Neural Information Processing Systems, 2020.
Gordon Christic, Neil Fendley, James Wilson, and Ryan Mukherjee. Functional map of the world. In Conference on Compuler Vision and Pollern Recognilion, 2018.
Corinna Cortes and Mchryar Mohri. Domain adaptation in regression. In International Conference Algorilhmic Learning Theory, 2011.
Lixin Duan, Dong Xu, and Ivor Tsang. Learning with augmented features for heterogeneous domain adaptation. In International Conference on Machine Learning, 2012.
Michael Gadermayr, Dennis Eschweiler, Barbara Mara Klinkhammer, Peter Boor, and Dorit Merhof. Gradual domain adaptation for segmenting whole slide images showing pathological variability. In International Conference on Image and Signal Processing, 2018.
Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, and Alexei A Efros. A century of portraïts: visual historical record of american high school yearbooks. In International Conference on Computer Vision Workshops, 2015.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. In International Conference on Neural Information Processing Systems, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference on Compuler Vision and Pullern Recognition, 2016.
Judy Hoffman, Trevor Darrell, and Kate Saenko. Continuous manifold based adaptation for evolving visual domains. In Conference on Computer Vision and Patlern Recognition.
Judy Hoffman, Erik Rodner, Jeff Donahue, Kate Saenko, and Trevor Darrell. Efficient learning of domain- invariant image representations. In International Conference on Learning Representations, 2013.
Judy Hoffman, Mehryar Mohri, and Ningshan Zhang. Algorithms and theory for multiple-source adaptation. In International Conference on Newral Information Processing Systems, 2018a
Judy Hoffman, Eric Tzeng, Taesung Park, Jun Zhu, Phillip Isola, Kate Saenko, Alexei Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In Indernational Conference Machine Learning, 2018b.
Leonid Kantorovich and Gennady S. Rubinstein. On a space of totally additive functions. Vestnik Leningrod. Univ, 13:52-59. 1958.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasuaga,, Richard Lanas Phillips, Irena Gao, et al. Wilds: benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, 2021.
12

---

Published in Transactions on Machine Learning Research (11/2022)
Brian Kulis, Kate Saenko, and Trevor Darrell. What you saw is not what you get: Domain adaptation using asymmetric kernel transforms. In Conference on Computer Vision and Pattern Recognalion, pp. 1785-17922 2011.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In International Conference on Machine Learning, 2020.
Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for time series prediction with non-stationary processes. In International Conference on Algorithmic Learning Theory, 2014.
Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for non-stationary mixing processes. Machine Learning, 106(1):93-117, 2017.
Vitaly Kuznetsov and Mehryar Mohri. Discrepancy-based theory and algorithms for forecasting non-stationary time series. Annals of Mathematics and Artificial Intelligence, 88(4):367-399, 2020.
Hong Liu, Mingshong Long, Jianmin Wang, and Yu Wang. Learning to adapt to evolving domains. Advances in Neural Information Processing Systems, 2020.
Yishay Mansour, Mchryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Conference on Learning Theory, 2009.
Yishay Mansour, Mehryar Mohri, Jae Ro, Ananda Theertha Suresh, and Ke Wu. theory of multiple-source adaptation with limited target labeled data. In International Conference on Artificial Intelligence and Statistics, 2021.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. Journal of Machine Learning Research, 16:155-166, 2015.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European Conference on Computer Vision, 2010.
Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Henrik Marklund, et al. Extending the wilds benchmark for unsupervised adaptation. In Advances in Newral Information Processing Systems Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In AAAI Conference on Artificial Intelligence, 2018.
Yuge Shi et al. Gradient matching for domain generalization. In International Conference on Learning Representations, 2022.
Khe Chai Sim, Arun Narayanan, Ananya Misra, Anshuman Tripathi, Golan Pundak, Tara N Sainath, Parisa Haghani, Bo Li, and Michiel Bacchiani. Domain adaptation using factorized hidden layer for robust automatic speech recognition. In Interspeech, pp. 892-896, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprinl arxiv:14009 1556, 2014.
Sining Sun, Binbin Zhang, Lei Xie, and Yanning Zhang. An unsupervised deep domain adaptation approach for robust speech recognition. Newrocomputing, 257:79 87, 2017.
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Conference on Computer Vision and Pattern Recognition, 2017.
Haoxiang Wang, Bo Li, and Han Zhao. Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. arxiv preprint ar (tl::2244002000 2022.
13

---

Published in Transactions on Machine Learning Research (11/2022)
Junfeng Wen, Russell Greiner, and Dale Schuurmans. Domain aggregation networks for multi-source domain adaptation. In International Conference on Machine Learning, 2020.
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetrically- relaxed distribution alignment. In International Conference on Machine Learning, 2019a.
Zuxuan Wu, Xin Wang, Joseph E. Gonzalez, Tom Goldstein, and Larry S Davis. Ace: Adapting to changing environments for semantic segmentation. In International Conference on Computer Vision, 2019b.
Markus Wulfmeier, Alex Bewley, and Ingmar Posner. Incremental adversarial domain adaptation for continually changing environments. In International Conference on Robotics and Automation, 2018.
Jun Yang, Rong Yan, and Alexander G Hauptmann. Adapting svm classifiers to data with shifted distributions. In International Conference on Data Mining Workshops, 2007.
Han Zhao, Shanghang Zhang, Guanhang Wu, José MF Moura, Joao P Costeira, and Geoffrey J Gordon. Adversarial multiple source domain adaptation. Advonces Neurul Information Processing Systems, 2018.
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, 2019a.
Han Zhao, Chen Dan, Bryon Aragam, Tommi S Jaakkola, Geoffrey J Gordon, and Pradeep Ravikumar. Fundamental limits and tradeoffs in invariant representation learning. arXiv preprint arXi::2012.10713, 2020.
Sicheng Zhao, Bo Li, Xiangyu Yue, Yang Gu, Pengfei Xu, Runbo Tan, Hu, Hua Chai, and Kurt Keutzer. Multi-source domain adaptation for semantic segmentation. In Advances in Neural Information Processing Systems, 2019b.
14


Reviews:
[{"review_id": "07LyxjolNu", "reviewer": "Reviewer_DnNf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Main Review:\n\nPros:\n\n1. This paper is solid and provides insightful theoretical analysis to the field. The proposed setting is practical and can be applied into many real-world scenarios, since the labelled data are available even in the target domains in the real world. Then, the related upper bound is proposed and motivates the proposal of the method, which is meaningful and contains certain contributions to the field of domain adaptation. \n\n2. The whole paper is easy to follow in the view of techniques. The used math notations are clear. The reviewers enjoy reading the math part, which is clear and well descried.\n\n3. Notations are consistent, no much confusing points from theorems or proofs themselves.\n\nCons:\n\n1. There might be missing literature regarding meta-learning. When we address the GDA, certain assumptions are required to ensure that GDA can be addressed well. The meta-learning based domain generalization methods might be good baselines. These methods can be changed to address the GDA problem as well. For example, you can train a good algorithm with MAML, then you can train models for target domains by using the data available in the target domain. \n\n2. Like the first point, the meta-learning-based baselines are required to make the experiments more solid. Currently, the experiments are not solid. More baselines are needed.\n\n3. It’s better to write down the problem setting using a definition, where necessary assumptions should be introduced. \n\n4. CIFAR-10 or CIFAR-100 dataset should be added into the experimental section, for the benchmarking purpose.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Review for TMLR 401\n\nSummary：\nThis paper studied the problem of supervised gradual domain adaptation, which arises naturally in applications with temporal nature. In this setting, the authors provide the first learning bound of the problem and the results are general to a range of loss functions and are algorithm agnostic. Based on the theoretical insight offered by the proposed theorem, this paper designed a primal-dual learning objective to learn an effective representation across domains while learning a classifier. The authors analyze the implications of the results through experiments on a wide range of datasets. In general, this paper makes certain contributions to the field of domain adaptation. \n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Cons:\n\n1. There might be missing literature regarding meta-learning. When we address the GDA, certain assumptions are required to ensure that GDA can be addressed well. The meta-learning based domain generalization methods might be good baselines. These methods can be changed to address the GDA problem as well. For example, you can train a good algorithm with MAML, then you can train models for target domains by using the data available in the target domain. \n\n2. Like the first point, the meta-learning-based baselines are required to make the experiments more solid. Currently, the experiments are not solid. More baselines are needed.\n\n3. It’s better to write down the problem setting using a definition, where necessary assumptions should be introduced. \n\n4. CIFAR-10 or CIFAR-100 dataset should be added into the experimental section, for the benchmarking purpose.\n\n", "broader_impact_concerns": "No concerns here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uz8Wbtc0Hl", "reviewer": "Reviewer_XcAN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The supervised gradual domain adaptation setting is realistic and interesting.\n- The generalization bounds provide insight into the relevant factors for learning in this setting.\n- A specific objective is proposed based on the bounds and its performance evaluated on realistic datasets.\n\nWeaknesses:\n- The relationship to previous generalization bounds is not clearly demonstrated.\n- Clarity of writing and explanation of details could be improved.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on supervised gradual domain adaptation, where the goal is to learn a classifier that performs well on a target domain given labeled data from a sequence of temporally related domains. This paper introduces generalization bounds for the supervised gradual domain adaptation setting. Analysis of these bounds points to the importance of minimizing the distance between sequential class-conditional distributions and the effect of the number of domains. Based on the bounds, a min-max learning objective is proposed and its effectiveness evaluated on the rotating MNIST, portraits, and FMOW datasets.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Requested changes:\n- It would be useful to compare the results of Theorem 4.1 with the bounds of Kumar et al. (2020) for unsupervised gradual domain adaptation and Wen et al. (2020a) for multiple domain adaptation in order to understand the relationships among these settings. Presently these connections are only discussed at a high-level (e.g. exponential vs. linear relationship) but it is difficult to piece this together without seeing the other bounds expressed in similar mathematical terms.\n- Clarify why the $W_\\infty$ distance is too restrictive.\n- Clarify the nature of assumption 3.3. The writing currently implies that all bounded functions are Lipschitz continuous (\"we only assume that the empirical loss function is bounded and is hence Lipschitz continuous\"). Also, the experiments use cross-entropy loss, which if I'm not mistaken, is neither Lipschitz continuous nor bounded.\n- Explain in greater detail the various baselines (e.g. no adaptation, direct adaptation, etc.) and how the training domains are constructed.\n\nMinor comments:\n- Lemma B.1 has a typo in the $\\sqrt{\\cdot}$ expression\n- In Theorem 4.1, it is not clear how the hypothesis $h_T$ is chosen.\n- The definition of $L_D$ under (3) is difficult to parse. Is the minimization performed only over $t$? If so, then the $t+1$ should be removed from the minimization.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eJZ59tcMXU", "reviewer": "Reviewer_ybbK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n====\n\n1. **Practical importance of problem setting**.\nDespite a long history of research on (unsupervised) domain adaptation, they often face the challenge of how to overcome vastly different source and target domains.\nThis challenge is reflected in many well-known domain adaptation error bounds such as Ben-David et al. (2007) and Mansour et al. (2009).\nIndeed, adapting from a source domain vastly different from a target domain is not a well-defined problem and is often too pessimistic.\nThus, it is more natural to consider gradual domain adaptation in real-world scenarios.\nThis paper takes one step further to make it supervised, which is naturally arising in real-world scenarios and benefits a learner to learn in a better way.\nThe authors motivate this perspective well in the introduction.\n\n2. **Improvement of the error bound**.\nAs one of the benefits to consider the supervised problem, the authors show that the domain adaptation error bound they derived depends on the initial domain error linearly.\nAs they claim, this is in stark contrast to the error bound derived by Kumar et al. (2020) in unsupervised gradual domain adaptation, which depends exponentially.\nThis draws an interesting insight to consider the supervised problem.\n(But, I was not fully convinced of this perspective because I could not validate the authors' claim regarding Kumar et al.'s results. See Weaknesses #1.)\n\nWeaknesses\n====\n\n1. **Comparison/review of existing studies may not be sufficient/self-contained.**\nSome parts of the paper regarding the discussion of previous studies are not self-contained so the readers may feel difficult to validate the correctness of the paper.\nThe most significant point is the discussion of Kumar et al. (2020).\nAlthough the authors claim \"the given upper bound of the learning error on the target domain suffers from exponential dependency (in terms of the length of the trajectory) on the initial learning error on the source domain\" in the introduction,\nI did not understand which claim made by Kumar et al. (2020) corresponds to it.\nTheir main theorem (and its corollary) Corollary 3.3 shows the exponential dependency $\\beta^{T+1}$, where $\\beta = \\frac{2}{1-\\rho R}$ ($\\rho$ is a kind of the Lipschitz constant and $R$ is the maximal radius of the hypothesis set).\nThere does not seem to be any exponential dependency on the initial learning error as far as I understood.\nThe authors may clarify this part in the paper to convince the readers of the contribution.\nMoreover, since Kumar et al. (2020) is one of the closely related previous studies, the authors may consider reviewing this work in more detail (by using equations).\n\nIn addition, some other literature reviews can be made more informative.\nI felt the following reviews in Section 2 are insufficient to draw connections to the current work.\n\n- \"The theoretical limits of domain adaptations have also been extensively studied (David et al., 2010; Zhao et al., 2019a; Wu et al., 2019a; Zhao et al., 2020).\"  // What are the theoretical limitations? How do these works differ?\n- \"This result is later ... improved by concurrent independent work Wang et al., (2022).\"  // Even if it is concurrent, it is important to provide a sufficient review to show what is different from the current submission.\n\n2. **(Probably) incorrect arguments regarding monotonicity of the Wasserstein distance**.\nIn Section 3, the authors claim that \"due to the monotonicity of the $W\\_p$ distance, the $W\\_1$ distance leads to tighter upper bounds\", and use the inequality $W\\_1(\\mu, \\nu) \\le W\\_p(\\mu, \\nu)$ in the proof of Lemma 3.1.\nAlthough I did not find a nice proof immediately, I don't think this is correct.\nThe intuition comes from the monotonicity of $\\ell\\_p$ norms: $\\ell\\_p$ norm decreases as $p$ gets larger.\nSince the $p$-Wasserstein distance is defined by using the $\\ell\\_p$ norm as the base metric (although it involves the minimization), the analogy seems to work here.\nI did a simple simulation below, which shows an example that the aforementioned inequality may be incorrect.\n(`ot` is the Python OT package)\n```\nIn [1]: import numpy as np\n   ...: import ot\n   ...: from ot.datasets import make_1D_gauss as gauss\n\nIn [2]: n = 100  # nb bins\n   ...: \n   ...: # bin positions\n   ...: x = np.arange(n, dtype=np.float64)\n   ...: \n   ...: # Gaussian distributions\n   ...: a = gauss(n, m=20, s=5)  # m= mean, s= std\n   ...: b = gauss(n, m=60, s=10)\n   ...: \n   ...: # loss matrix\n   ...: M = ot.dist(x.reshape((n, 1)), x.reshape((n, 1)))\n   ...: M /= M.max()\n\nIn [3]: for p in range(1, 10):\n   ...:     w = ot.wasserstein_1d(a, b, p=p)\n   ...:     print(f\"{p} {w}\")\n   ...: \n1 0.0064531459404555715\n2 0.0001326386522362971\n3 3.716677655553046e-06\n4 1.20986120423101e-07\n5 4.229773302944304e-09\n6 1.531836302744079e-10\n7 5.6554649157605976e-12\n8 2.112946713019602e-13\n9 7.959239997625665e-15\n```\nI suppose that the proof of Lemma 4.1 could be corrected by assuming the Lipschitz continuity of the loss function with respect to the $\\ell\\_p$ norm (instead of $\\ell\\_1$ norm in the current form) and correcting Assumption 3.1 from $W\\_p \\le \\Delta$ to $W\\_p^p \\le \\Delta$, which still requires careful investigations.\nDue to this (probably) inaccurate claim, we may need to rethink the comparison of the assumptions with Kumar et al. (2020).\n\n3. **The provided theory assumes the class-conditional shift, too**.\nAlthough the authors criticize Kumar et al. (2020) by \"They assumed that the label distribution remains unchanged while the varying class conditional probability ... which only covers a limited number of cases.\" in Section 2,\nthe authors eventually assume the same one in Assumption 3.2.\nI think it is okay to assume it for the time being, but this argument may need clarification.\n\n4. **The algorithmic formulation has remained not sufficiently clear**.\nIn Section 5, the authors provide a practical algorithm based on the error bound to learn representation by making $\\Delta$ smaller.\nHowever, the presentation of the algorithm derivation may not be sufficiently clear because of the following points.\n\n- At the beginning of the second paragraph of \"A primal-dual objective formulation\", we see \"the objective (3)\", which has not appeared at the moment of this sentence. Equation (3) appears subsequently, which does not seem to be what is mentioned here in light of the context.\n- The authors mention \"the Wasserstein-1 distance's dual representation\", but it is not clear on which part (in the error bound?) the Kantrovich duality has been applied. Accordingly, equation (3) could not be interpreted.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a supervised version of gradual domain adaptation---which has gathered attention in recent years due to intrinsic limitations of the usual (one-shot) domain adaptation. In this scenario, a learner shall be exposed to training data drawn from a joint probability distribution, which will be drifting over time gradually in the sense that the class-conditional distributions shift without moving too far from the previous distribution in terms of the Wasserstein distance. Under this setup, the authors derive the target error bound (by leveraging the sequential Rademacher complexity and discrepancy measure), which the authors claim improves the previous bound obtained by Kumar et al. (2020) regarding the dependency on the initial error. Inspired by the derived bound, the authors propose a min-max-based representation learning algorithm to minimize the distance between consecutive distributions. Additionally proposed temporal encoding with the LSTM improves the data efficiency, without access to data from the past domains. Finally, the authors confirm that the proposed method experimentally outperforms domain adaptation methods without leveraging multiple domains and multi-source domain adaptation (which discards the temporal structure).", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Major comments\n====\n\nThe followings were mentioned above.\n\n- To make the literature review self-contained, in particular Kumar et al. (2020).\n- To check the monotonicity of the $p$-Wasserstein distance carefully.\n- To make the algorithm derivation clearer.\n\nSome minor comments\n====\n\n- The related work section is usually written in the past tense (or perfect tense). In Section 2, I found several sentences in the present tense.\n- In Assumption 3.1, the initial $1 \\le t \\le T$ seems to be $1 \\le t \\le T - 1$, otherwise the undefined $P_{T+1}$ will appear.\n- In Assumption 3.2, \"through out\" -> \"throughout\".\n- In Assumption 3.3, when you mention the Lipschitz continuity (of the bivariate loss function), it would be better to clearly say \"Lipschitz continuous with respect to $(x,y)$\".\n- Right after Assumption 3.3, \"In the case where the input data fails to be compact, the assumption remains true after the normalization of data\", which I don't think is accurate because the radius of the unbounded real vector space (not compact) is the infinity and hence the normalization makes all points to be the origin.\n- In Definition 2, $\\mathcal{Z}$-valued trees should be defined properly to make them self-contained.\n- In Definition 3, please check the superscript $t-1$ in the condition of the second conditional expectation. If we take the sum from $t=1$ to $T-1$, $Z^0$ will appear, which seems strange.\n- In Theorem 4.1, Assumption 3.2 should be assumed as well.\n- In Theorem 4.1, it is not clear how \"a learned classifier $h\\_T$\" is obtained/defined. I guess this should be \"for any $h\\_T$\".\n- In Lemma 4.1, please remove the period after \"the expected loss on two consecutive domains satisfy\".\n- In the last equation of the page 5, the summation $\\sum\\_{t=1}^T$ is not consistent to the definition of $\\mathrm{disc}\\_T$ in equation (1). Could you check it again?\n- In Section 5, it would be better to cite \"the Wasserstein-1 distance's dual representation\".\n- After equation (4), the second expectation should be $\\mathbb{E}\\_{P\\_{t+1}}$ instead of $\\mathbb{E}\\_{P\\_{t-1}}$.\n- In the last paragraph of Section 5, I don't understand where we need \"to approximate the Wasserstein distance\".\n- In Section 6, to verify research question 2 \"Can the one-step primal-dual loss act as a substitute to optimization objective (3)?\", I would encourage the authors not only to compare the LSTM and CNN but also to compare the original objective (3) by using all past domains.\n- In Table 4, although the performance seems to saturate around $T=9$ or $T=11$, we cannot be sure that they are optimal time horizons. Is it possible to test larger horizons to see if they are indeed optimal?\n- When we look at Figure 1a, the multi-source domain adaptation baseline seems to work very competitively with the proposed method, but this baseline is not tested in Figure 1b and Table 3. Why don't you compare it to see how the baseline performs in these settings?\n- In Appendix A, \"lemma 4.1\" in the section title should be capitalized.\n- In reference, \"David\" should be corrected to \"Ben-David\".", "broader_impact_concerns": "This does not apply to the current submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the supervised gradual domain adaptation problem. Theory and algorithms are provided. More specifically, the authors have proven that the supervised gradual domain adaptation has a smaller upper generalization bound than that of unsupervised gradual domain adaptation. Effective algorithms are inspired by the theory. All reviews appreciate the contribution and we therefore recommend an acceptance.
Decision: Accept (poster)