Year: 2021

Abstract:
Domain generalization aims to learn a predictive model from multiple different but related source tasks that can generalize well to a target task without the need of accessing any target data. Existing domain generalization methods ignore the relation between tasks, implicitly assuming that all the tasks are sampled from a stationary environment. Therefore, they can fail when deployed in an evolving environment. To this end, we formulate and study the progressive domain generalization (PDG) scenario, which exploits not only the source data but also their evolving pattern to generate a model for the unseen task. Our theoretical result reveals the benefits of modeling the relation between two consecutive tasks by learning a globally consistent directional mapping function. In practice, our analysis also suggest solving the PDG problem in a meta-learning manner, which leads to directional prototypical network, the first method for the PDG problem. Empirical evaluation on both synthetic and real-world data sets validates the effectiveness of our approach.

heading: 1 INTRODUCTION
text: Modern machine learning techniques have achieved unprecedented success over the past decades in various areas. However, one fundamental limitation of most existing techniques is that a model trained on one data set cannot generalize well on another data set if it is sampled from a different distribution. Domain generalization (DG) aims to alleviate the prediction gap between the observed source domains and an unseen target domain by leveraging the knowledge extracted from multiple source tasks (Ganin & Lempitsky, 2015; Arjovsky et al., 2019; Li et al., 2018b).
Existing DG methods can be roughly categorized into three groups: data augmentation/generation, disentangled/domain-invariant feature learning, and meta-learning (Wang et al., 2021). One intrinsic problem with these methods is that they treat all the domains equally and ignore the relationship between them, implicitly assuming that they are all sampled from a stationary environment. However, in many real-world applications, the data are usually collected sequentially and the learning tasks can vary in an evolving manner. For example, geological exploration is often carried out periodically and the distribution of data collected can change from year to year due to environmental changes. Medical data are also often collected with age or other indicators as intervals, and there is an evolving trend in the data of different groups. As a more concrete example, Fig. 1(a) shows several instances from the rotated MNIST (RMNIST) data set, a widely used benchmark in the DG literature, where the digit images of each subsequent domain are rotated by 15◦. Fig. 1(b) reports the generalization performances of several state-of-the-art DG algorithms on the data set, from which it can be clearly observed that the performances drop when deploying the models on outer domains (i.e., tasks of 0 and 75 degrees). The results indicate that the algorithms ignore the evolving pattern between the domains properly. As a consequence, they are good at “interpolation” but not at “extrapolation”.
In this paper, we formulate this learning scenario as progressive domain generalization (PDG), which aims to capture and exploit the evolving patterns in the environment. In contrast to most existing DG methods, which produce models that are isotropic with respect to all the domains, PDG can generalize to a target domain along a specific direction by extracting and leveraging the relations between source tasks. Specifically, we develop a novel theoretical analysis that highlights the importance of modeling the relation between two consecutive tasks to extract the evolving pattern of the environment. Moreover, our analysis also suggests learning a globally consistent directional mapping function via meta-learning. Inspired the theoretical results, we slightly modify prototypical
networks (Snell et al., 2017) and propose directional prototypical networks (DPNets), a simple and efficient PDG algorithm that adapts to the environment shift and generalizes well on the evolving target domain. As a comparison, Fig. 1(c) shows the performance improvement of DPNets over the other algorithms on RMNIST data set. It can be observed that the performance gap between DPNets and the other baseline algorithms has widened as the domain distance increases. More details can be found in Section 4.
Here, we would like to emphasize the key difference between PDG and domain adaptation in evolving domains (Liu et al., 2020; Wang et al., 2020; Kim et al., 2020). While both learning paradigms aim to tackle the issue of evolving domain shifts, the latter still requires unlabeled instances from the target domain. In this sense, PDG is more challenging and existing theoretical and algorithmic results cannot be applied to this problem directly.

heading: 2 RELATED WORK
text: Domain Generalization (DG). Domain generalization aims to train a model which generalizes on all domains. Existing DG methods can be classified into three categories. The first and most popular category is representation learning, which focus on learning a common representation across domains. It can be achieved by domain-invariant representation learning (Blanchard et al., 2011; Ghifary et al., 2015; Ganin & Lempitsky, 2015; Arjovsky et al., 2019) and feature disentanglement (Xu et al., 2014; Ilse et al., 2020). The former focuses on aligning latent features across domains, and the later tries to distill domain-shared features. Secondly, data manipulation can also empower the model with generalization capability. Data manipulating techniques include data augmentation (Yue et al., 2019; Shankar et al., 2018b), which usually extend the dataset by applying specific transformations on existing samples, and data generation (Rahman et al., 2019), which often applies neural networks to generate new samples. Nguyen et al. (2021) convert DG to an infinite-dimensional constrained statistical learning problem under a natural model of data generation. The theoretically grounded method proposed in Nguyen et al. (2021) leverages generating model among domains to learn domain-invariant representation. The last part are meta-learning. As a widely applicable method, meta-learning framework (Li et al., 2018b; Balaji et al., 2018; Li et al., 2019) is used to improve the generalizing capability by simulating the shift among domains. Apart from the above three categories, there are some other learning strategies that help to improve the generalization ability of the model. Mancini et al. (2018) tries to ensemble multiple models into a unified one which can generalize across domains. The DRO-based methods (Rahimian & Mehrotra, 2019) which aim to learn a model at worst-case distribution scenario also match the target of DG well. Besides, gradient operation (Huang et al., 2020b), self-supervision (Carlucci et al., 2019) and random forest (Ryu et al., 2019) are also exploited to improve generalizing capability. Different from the existing DG methods that focus on learning one unified model for all domains, our approach tries to train prediction model for the target domain specifically by leveraging the evolving pattern among domains.
Evolving Domain Adaptation (EDA). Many previous work in domain adaptation area notice the evolving pattern of domains and leverage it to improve the performance in different settings. Liu et al. (2020) proposes a meta-adaptation framework which enables the learner to adapt from one single source domain to continually evolving target domains without forgetting. Kim et al. (2020) tries to adapt to multiple target domains sequentially without forgetting, while the most important difference is that there is no assumption about the evolving pattern between these domains. Kumar et al. (2020) focuses on adapting from source domain to the target domain with large shifts by leveraging the unlabeled intermediate samples. Wang et al. (2020) combines the traditional adversarial adaptation strategy with a novel regression discriminator that models the encoding-conditioned domain index distribution. Chen & Chao (2021) investigate how to discover the sequence of intermediate domains without index information then adapt to the final target. The experimental results and theoretical analysis demonstrate the value of leveraging index information when working on evolving domains. These studies fully demonstrate that leveraging evolving pattern between domains is beneficial and worth more exploration. However, there are two significant limitation in previous works. The first one is the requirements for accessing unlabeled data in the target domain. The second one is that all previous theoretical results are base on the assumption that distance between sequential domains is small, which would become vacuous as the environment evolves. This is contrary to the fact that more domains provide more evolving information which can help to improve the performance. In this paper, the evolving information is leveraged without accessing any samples from the target domain. Also, our theoretical results are based on proposed λ-consistency, a intuitive and realistic measurement of evolving level in the environments.

heading: 3 THEORETICAL ANALYSIS AND METHODOLOGY
text: Let {D1(x, y),D2(x, y), ...,Dm(x, y)} be m observed source domains sampled from an environment E where x ∈ X and y ∈ Y are, respectively, the data point and its corresponding label. The goal of DG is to learn a hypothesis h ∈ H so that it can have a low risk on an unseen but related target domain Dt:
RDt(h) , E(x,y)∼Dt [`(h(x), y)]
where ` : Y×Y → R+ is a non-negative loss function, andH is a hypothesis class that mapsX to the set Y . In the setting of traditional DG, as there is no relation exploited between the source domains and the target domain, most existing techniques essentially either “enlarge” the input space X along all possible directions (Volpi et al., 2018; Shankar et al., 2018a; Qiao et al., 2020) or learn a domaininvariant feature representation via domain alignment (Li et al., 2018c; Arjovsky et al., 2019; Zhao et al., 2020). In contrast, the objective of PDG is to generalize the model on Dt along a specific direction when there is underlying evolving pattern between the source domains and Dt = Dm+1.

heading: 3.1 THEORETICAL MOTIVATIONS
text: In order to leverage the evolving pattern in E , it is reasonable to assume that such a pattern can be captured by a globally consistent mapping function g ∈ G : Dgi+1 , g(Di) in a way such that the synthetic domain Dgi+1 is close to Di+1 as much as possible, where G is the class of mapping functions. We first obtain the following bound of the risk on the target domain Dt with respect to Dgt , as shown in Lemma 1. Lemma 1. Let Dgt (h) = g(Dm) be the synthetic target domain, and suppose the loss function ` is bounded within an interval G : G = max(`)−min(`). Then, for any h ∈ H, its target risk RDt(h) can be upper bounded by:
RDt(h) ≤ RDgt (h) + G√
2
√ dJS(Dgt ||Dt),
where dJS(Dgt ||Dt) is the Jensen-Shannon (JS) divergence between D g t and Dt (Fuglede & Topsoe, 2004).
Remark 1. To achieve a low risk on Dt, Lemma 1 suggests (1) learning h and g to minimize the risk over the synthetic domain Dgt and (2) learning g to minimize the JS divergence between D g t and Dt. While in practice RDgt (h) can be approximated by the empirical risk, Lemma 1 still cannot
provide any practical guidelines for learning g since Dt is unavailable. Moreover, note that Dgt can be replaced by g(Di) for any other source domain i in E and the bound still holds. Thus, Lemma 1 does not provide any theoretical insight into how to discover and leverage the evolving pattern in E .
Intuitively, capturing the evolving pattern in E is hopeless if it varies arbitrarily. On the other hand, if the underlying pattern is consistent over domains, it is reasonable to assume that there exists g∗ ∈ G would perform consistently well over all the domain pairs. For example, given numbers 100, 202, 301, one would expect that the numbers increase by around 100 and the next number will be around 400, but it is challenging to guess the number if the first three numbers are −20, 1300, 4. To formulate the this intuition, we first introduce the notion of consistency of an environment E below. Definition 1 (Consistency). Let g∗ = arg ming∈G maxDi∈E dJS(D g i ||Di) be the ideal mapping function in the worst-case domain. Then, an evolving environment E is λ-consistent if the following holds:
|dJS(Dg ∗ i ||Di)− dJS(D g∗ j ||Dj)| ≤ λ, ∀Di,Dj ∈ E .
Note that λ does not characterize how fast E evolves, but if there exists a global mapping function that can model the evolving pattern consistently well in E . Given the definition of consistency, we can bound the target risk in terms of dJS(Dgi ||Di) in the source domains. Theorem 1. Let {D1,D2, ...,Dm} be m observed source domains sampled sequentially from an evolving environment E , and Dt be the next unseen target domain: Dt = Dm+1. Then, if E is λ-consistent, we have
RDt(h) ≤ RDg∗t (h) + G√
2(m− 1) (√√√√ m∑ i=2 dJS(Dg ∗ i ||Di) + √ (m− 1)λ ) .
Remark 2. (1) Theorem 1 highlights the role of the mapping function and λ-consistency in PDG. Given g∗, the target risk RDt(h) can be upper bounded by in terms of loss on the synthetic target domain RDg∗t (h), λ, and the JS divergence between Di and D g∗
i in all observed source domains. When g∗ can properly capture the evolving pattern of E , we can train the classifier h over the synthetic domainDg ∗
t generated fromDm and can still expect a low risk onDt. (2) λ is unobservable and is determined by E and G. Intuitively, a small λ suggests high predictability of E , which indicates that it is easier to predict the target domain Dt. On the other hand, a large λ indicates that there does not exist a global mapping function that captures the evolving pattern consistently well over domains. Consequently, generalization to the target domain could be challenging and we cannot expect to learn a good hypothesis h on Dt. (3) In practice, g∗ is not given, but can be learned by minimizing dJS(Dgi ||Di) in source domains. Besides, aligning D g i and Di is usually achieved by representation learning: that is, learning g : X → Z to minimize dJS(Dgi ||Di),∀z ∈ Z .
In addition, we can decomposeD(x, y) into marginal and conditional distributions to motivate more practical PDG algorithms. For example, when it is decomposed into class prior D(y) and semantic conditional distribution D(x|y), we have the following Corollary. Corollary 1. Following the assumptions of Theorem 1, the target risk can be bounded by
RDt(h) ≤ RDg∗t (h) + G√
2(m− 1) (√√√√ m∑ i=2 dJS(Dg ∗
i (y)||Di(y))︸ ︷︷ ︸ I
+ √ (m− 1)λ
+ √√√√ m∑ i=2 E y∼Dg ∗ i (y) dJS(Dg ∗
i (x|y)||Di(x|y))︸ ︷︷ ︸ II +
√√√√ m∑ i=2 Ey∼Di(y)dJS(D g∗
i (x|y)||Di(x|y))︸ ︷︷ ︸ III
) .
Remark 3. To generalize well to Dt, Corollary 1 suggests that a good mapping function should capture both label shifts (term I) and semantic conditional distribution shifts (terms II & III). If we
further assume that the label distribution does not evolve over domains1, we will have I = 0 and II = III, and the upper bound can be simplified as
RDt(h) ≤ RDg∗t (h) + G√
2(m− 1)
( 2 √√√√ m∑ i=2 Ey∼Di(y)dJS(D g∗ i (x|y)||Di(x|y)) + √ (m− 1)λ ) .
Finally, we note two key theoretical differences between PDG and previous studies of DA in evolving environments (Ben-David et al., 2010; Liu et al., 2020). (1) In DA, the target risk is bounded in terms of source and target domains (e.g., H∆H-divergence), while our analysis relies on the distance between synthetic and real domains. (2) DA theories are built upon the assumption that there exists an ideal joint hypothesis that achieves a low combined error on both domains, while our assumption is the λ-consistency of E . These differences eventually lead to fundamentally different guidelines for PDG, as shown in Section 3.2.

heading: 3.2 PRACTICAL IMPLEMENTATIONS
text: Our analysis reveals several general strategies to follow when designing an algorithm for PDG.
(i) Learning the mapping function g to capture the evolving pattern by minimizing the distance between the distributions of synthetic and real domains.
(ii) Learning g and h to minimize the risk on the synthetic target domain Dgt . (iii) Note that Dgi+1 = g(Di) is produced from Di, but its quality is evaluated on Di+1. Thus,
minimizing dJS(Dgi ||Di) naturally suggests a meta-learning strategy for learning g.
In practice, mapping the samples from Di to Di+1 is not necessarily performed in the original data space since our ultimate goal is making predictions rather than generating instances themselves. Thus, we minimize the distance between Dgi+1 and Di+1 in a representation space. Based on these ideas, we slightly modify prototypical networks (Snell et al., 2017) and propose directional prototypical networks (DPNets) for PDG. Specifically, the mapping function g of DPNets consists of two different embedding functions: fφ for Di and fψ for Di+1, where φ and ψ are learnable parameters. The key idea of DPNets is to learn g = {fφ, fψ} to capture the evolving pattern of E by estimating the prototypes of fψ(Di+1) using fφ(Di). As each prototype can be viewed as the centroid of instances of each class, which is an approximation of the semantic conditional distribution of each class (Xie et al., 2018; Shui et al., 2021a), DPNets essentially minimizes the distance between Dgi+1(x|y) and Di+1(x|y), as suggested by Corollary 1 Remark 3.
Let Si = {(xin, yin)} Ni n=1 be the data set of sizeNi sampled fromDi, and Ski be the subset of Si with class k ∈ {1, ...,K}, where K is the total number of classes. Then, the prototype of domain i is the mean vector of the support instances belonging to Ski :
cki = 1 |Ski | ∑
(xin,y i n)∈Ski
fφ(x i n)
In (Snell et al., 2017), the prototype is used to produce a distribution D(y = k|x) to make a prediction for a query instance x in the context of few-shot learning, and the support and query instances are sampled from the same domain. By contrast, in DPNets, the prototypes are computed from the support set Si through the embedding function fφ, but the query instances are from Si+1 and are passed through another function fψ . Then, the predictive distribution for Di+i is given by
Dφ,ψ(yi+1 = k|xi+1) = exp(−d(fψ(xi+1), cki ))∑K k′=1 exp(−d(fψ(xi+1), ck ′ i ) , (1)
where d : Z × Z → [0,+∞) is a distance function of embedding space, and we adopt squared Euclidean distance in our implementation, as suggested in (Snell et al., 2017). During the training
1When label shifts exist, term I can be minimized by reweighting/resampling the instances according to the class ratios between domains (Shui et al., 2021a).
Algorithm 1 The loss computation for DPNets (one episode) Input: {S1,S2, ...,Sm}: m data sets from consecutive domains. NB : the number of support and query instances for each class. RANDOMSAMPLE(S, N): a set ofN instances sampled uniformly from the set S without replacement. Output: The loss Jφ,ψ for a randomly generated training episode. t← RANDOMSAMPLE({1, ...,m}) for k in {1, ...,K} do
Sk ← RANDOMSAMPLE(Ski , NB) Q← RANDOMSAMPLE(Ski+1, NB) ck = 1|Sk| ∑ (xj ,yj)∈Sk fφ(xj) . Compute prototypes
end for J(φ, ψ)← 0 for k in {1, ...,K} do
for (x, y) in Q do Jφ,ψ ← Jφ,ψ + 1KNB [d(fψ(x), c k) + log ∑ k′ exp(−d(fψ(x), ck)]
end for end for
stage, at each step, we randomly choose the data sets Si,Si+1 from two consecutive domains as support and query sets, respectively. Then, we sample NB samples from each class k in Si, which is used to compute prototype cki for the query data in Si+1 . Model optimization proceeds by minimizing the negative log-probability: Jφ,ψ = − logDφ,ψ(yi+1 = k|xi+1). The pseudocode to compute Jφ,ψ for a training episode is shown in Algorithm 1. In the testing stage, we pass the instances from Sm and St through fφ and fψ respectively as support and query sets, and then make predictions for the instances in Dt using Eq. (1).

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETUP
text: We evaluate our algorithm on an extensive collection of five data sets, including two synthetic data sets (Envolving Circle (Wang et al., 2020) and Rotated Plate and three real-world data sets (RMNIST (Ghifary et al., 2015), Portrait (Kumar et al., 2020; Chen & Chao, 2021), and Cover Type (Kumar et al., 2020)).
(1) Evolving Circle (EvolCircle, Fig. 2) consists of 30 evolving domains, where the instances are generated from 30 2D Gaussian distributions with the same variances but different centers uniformly distributed on a half-circle. (2) Rotated Plate (RPlate, Fig. 3) consists of 30 domains, where the instances of each domain is generated by the same Gaussian distribution but the decision boundary rotates from 0◦ to 348◦ with an interval of 12◦. (3) Rotated MNIST (RMNIST) We randomly select only 2400 instances in raw MNIST dataset and split them into 12 domains equally. Then we apply the rotations with degree of θ = {0◦, 10◦, ..., 110◦} on each domain respectively. The amount of samples in each domain is only 200, which makes this task more challenging. (4) Portrait This task is to classify gender based on the photos of high school seniors across different decades (Ginosar et al., 2015). We divided the dataset into 12 domains by year. (5) Cover Type data set aims to predict cover type (the predominant kind of tree cover) from 54 strictly cartographic variables. To generate evolving domains, we sort the samples by the ascending order of the distance to the water body, as proposed in (Kumar et al., 2020). Then we equally divided the data set into 10 domains by distance. (5) FMoW A large satellite image dataset with target detection and classification tasks (Christie et al., 2018) . We select 5 common classes to compose a classfication task. The dataset is divided into 19 domains by time.
We compared the proposed method with the following baselines: (1) GroupDRO (Sagawa et al., 2019); (2) MLDG (Li et al., 2018a); (3) MMD (Li et al., 2018c); (4) SagNet (Nam et al., 2021); (5) VREx (Krueger et al., 2021); (6) SD (Pezeshki et al., 2020); (7) IRM (Arjovsky et al., 2019); (8) Mixup (Yan et al., 2020); (9) CORAL (Sun & Saenko, 2016); (10) MTL (Blanchard et al., 2021); (11) RSC (Huang et al., 2020a); (12) DIRL (Nguyen et al., 2021); (13) Original Proto-

heading: Algorithm EvolCircle RPlate RMNIST Portrait Cover Type FMoW Average
text: typical Network (Snell et al., 2017); (14) ERM (Vapnik, 1998). All the baselines and experiments were implemented with DomainBed package (Gulrajani & Lopez-Paz, 2020) under the same setting, which guarantees extensive and sufficient comparisons. Specifically, for each algorithm and data set, we conduct a random search (Bergstra and Bengio, 2012) of 20 trials over the hyperparameter distribution, and for each hyperparameter, five independent experiments with different random seeds are repeated to reduce the variances. Other details of hyperparameters and experimental setup are provided in the appendix.

heading: 4.2 RESULTS AND ANALYSIS
text: Overall Evaluation The performances of our proposed method and baselines are reported in Table 4. It can be observed that DPNets consistently outperforms other baselines over all the data sets,
and achieves 89.1% on average which is significantly higher the other algorithms (≈ 8% − 20%). The results indicate that existing DG methods cannot deal with domain shifts well while DPNets can properly capture the evolving patterns in the environments. It is also worth noting that directly employing Prototypical Network on our problem setting does not receive good result (81.5%), which further illustrates the effectiveness of our architectural design.
To further investigate the learning behaviors in evolving environments, we study the synthetic data sets, where the evolving pattern can be manually controlled. Here, we studied two typical evolving scenarios P (X) and P (Y |X), corresponding to the EvolCircle and RPlate data sets respectively. Evolving P (X) (EvolCircle). The decision boundaries on the unseen target domain D30 learned by ERM and DPNets are shown in Fig. 2(c) and Fig. 2(d) respectively. We can observe that DPNets fits the ground truth significantly better than that of ERM. This indicates that our approach can capture the evolving pattern of P (X) according to source domains and then learn a better classifier for the target domain. Furthermore, it can also be observed that the decision boundary learned by ERM achieves better performance on the observed source domains. This is because it focuses on improving generalization ability on all source domains, which leads the poor performance on the outer target domain D30. On the contrary, DPNets can “foresee” the prototypes for the target domain, which guarantees a good generalization performance even though it may not perform well on tge source domains.
Evolving P (Y |X) (RPlate). By visualizing the data sets, we can observe that the predicted boundary of DPNets better approximates the ground-truth, compared with the result of ERM. This indicates that our approach can also capture the P (Y |X) evolving pattern. Existing DG methods perform poorly on this data set because the ground truth labeling function varies. Under the evolving labeling functions, even the same instance can have different labels in different domains. Thus, there does not exist a single model that can perform well across all the domains. For this situation, learning a model specifically for one domain instead of all domains can be a possible solution. DPNets can capture the evolving pattern and produce a model specifically for the target domain.
When to apply DPNets? Existing DG methods assume that the distances among observed and unseen domains does not very large. However, the dissimilarity between domains is a crucial factor which can fundamentally influence the possibility and performance of generalization. To investigate the impact of variances of the environment, we create a series of variations on the raw RMNST data by jointly varying the number of domains (Table 2) and the degree interval (Table 3) between two consecutive domains. The performance improvement of DPNets over the baseline ERM (AccDPNets −AccERM) is shown in Fig. 4. Experimental results indicate that DPNets performs better when the number of domains and the distance between domains increase On one hand, greater number of domains and larger distance between them lead to more significant difference across domains. This makes tradi-
tional DG methods harder to train one model from all domains, but oppositely more domains benefit our DPNets to learn the evolving pattern to achieve better performance. On the other hand, we observed that the DPNets significantly outperforms other baselines when the number of domains and the distance between domains increase.
In Table 2 and Table 3, we respectively analyzed the affect of the domain distance and the number of domains on the generalization ability of different models. We can observe that, with the increasing complexity of source domains, the DPNets benefits a lot from the evolving information and the performance gap between our method and baselines increase. In addition, from Table 2 we can find that the performance of traditional DG methods fluctuates when the number of domains increases. As for the DPNets , its performance continuously improves when the domain number increases, since it easily learns the evolving manners from more domains. Please refer Section more discussion about this. From Table 3, we can see that when the domain distance increases, the performance of DG methods decreases severely while the performance of DPNets drops slightly.
In conclusion, the experimental results imply that it is hard for traditional DG methods to solve the PDG problem when the number of domains and distance between domains increase, while our DPNets can still perform well in such a scenario.
T-SNE visualization over evolving domains. In this part, we investigate the ability of DPNets and DG methods in distilling domain evolving information. Most domain generalization approaches aim to learn an invariant representation across all domains. While in the PDG scenario, we need to leverage the evolving pattern to improve the generalization process. Here, we use t-SNE to visualize, respectively, the representations learned from the second-to-last layer by ERM, DPNets, and original Prototypical Network in Fig. 5. The colors from red to blue correspond to the domains index from 1 to 30. The feature visualizations demonstrate that DPNets can keep the domain evolving even in the last layer of the network, which makes it possible to leverage that knowledge. On the contrary, the evolving pattern learned by Prototypical Network and ERM is less obvious. The results further prove that ERM and original Prototypical Network can not leverage evolving information well.

heading: 5 CONCLUSIONS
text: In this paper, we study the problem of domain generalization in an evolving environment, and propose progressive domain generalization (PDG) as a general framework to address it. Our theoretical analysis highlights the role of learning a mapping function to capture the evolving pattern over domains. Based on our analysis, we propose directional prototypical networks (DPNets), a simple and efficient algorithm for PDG. Experiments on both synthetic and real-world data sets validate the effectiveness of our method.

heading: ETHICS STATEMENT
text: This paper presents an algorithm that can exploit evolving information in a continuously changing environment to improve the performance of the model in target domains where data are not available. the proposed approach may also introduce the potential negative impact: the Portrait dataset we use is only intended to demonstrate algorithm’s superior performance on classification tasks.

heading: A PROOFS

heading: A.1 LEMMA 1
text: We first prove an intermediate lemma: Lemma 2. Let z ∈ Z = X ×Y be the real valued integrable random variable, let P and Q are two distributions on a common space Z such that Q is absolutely continuous w.r.t. P . If for any function f and λ ∈ R such that EP [eλ(f(z)−EP (f(z))] <∞, then we have:
λ(EQf(z)− EP f(z)) ≤ DKL(Q‖P ) + logEP [eλ(f(z)−EP (f(z))],
where DKL(Q‖P ) is the Kullback–Leibler divergence between distribution Q and P , and the equality arrives when f(z) = EP f(z) + 1λ log( dQ dP ).
Proof. We let g be any function such that EP [eg(z)] <∞, then we define a random variableZg(z) = eg(z) EP [eg(z)] , then we can verify that EP (Zg) = 1. We assume another distribution Q such that Q (with distribution density q(z)) is absolutely continuous w.r.t. P (with distribution density p(z)), then we have:
EQ[logZg] = EQ[log q(z)
p(z) + log(Zg
p(z) q(z) )] = DKL(Q‖P ) + EQ[log(Zg p(z) q(z) )]
≤ DKL(Q‖P ) + logEQ[ p(z)
q(z) Zg] = DKL(Q‖P ) + logEP [Zg]
Since EP [Zg] = 1 and according to the definition we have EQ[logZg] = EQ[g(z)] − EQ logEP [eg(z)] = EQ[g(z)]− logEP [eg(z)] (since EP [eg(z)] is a constant w.r.t. Q) and we therefore have: EQ[g(z)] ≤ logEP [eg(z)] +DKL(Q‖P ) (2) Since this inequality holds for any function g with finite moment generation function, then we let g(z) = λ(f(z)−EP f(z)) such that EP [ef(z)−EP f(z)] <∞. Therefore we have ∀λ and f we have:
EQλ(f(z)− EP f(z)) ≤ DKL(Q‖P ) + logEP [eλ(f(z)−EP f(z)]
Since we have EQλ(f(z)−EP f(z)) = λEQ(f(z)−EP f(z))) = λ(EQf(z)−EP f(z)), therefore we have:
λ(EQf(z)− EP f(z)) ≤ DKL(Q‖P ) + logEP [eλ(EQf(z)−EP f(z))]
As for the attainment in the equality of Eq.(2), we can simply set g(z) = log( q(z)p(z) ), then we can compute EP [eg(z)] = 1 and the equality arrives. Therefore in Lemma 1, the equality reaches when λ(f(z)− EP f(z)) = log(dQdP ).
In the classification problem, we define the observation pair z = (x, y). We also define the loss function `(z) = L ◦ h(z) with deterministic hypothesis h and prediction loss function L. Then for abuse of notation, we simply denote the loss function `(z) in this part.
Given Lemma 2, we are ready to prove Lemma 1.
Proof. According to Lemma 2, ∀λ > 0 we have:
EQf(z)− EP f(z) ≤ 1
λ (logEP e[λ(f(z)−EP f(z))] +DKL(Q‖P )) (3)
And ∀λ < 0 we have:
EQf(z)− EP f(z) ≥ 1
λ (logEP e[λ(f(z)−EP f(z))] +DKL(Q‖P )) (4)
Then we introduce an intermediate distribution M(z) = 12 (D(z) + D ′(z)), then supp(D) ⊆ supp(M) and supp(D′) ⊆ supp(M), and let f = `. Since the random variable ` is bounded
through G = max(`) − min(`), then according to Wainwright (2019) (Chapter 2.1.2), ` − EP ` is sub-Gaussian with parameter at most σ = G2 , then we can apply Sub-Gaussian property to bound the log moment generation function:
logEP e[λ(`(z)−EP `(z))] ≤ log e λ2σ2 2 ≤ λ 2G2
8 .
In Eq.(3), we let Q = D′ and P =M, then ∀λ > 0 we have:
ED′ `(z)− EM `(z) ≤ G2λ
8 +
1 λ DKL(D′‖M) (5)
In Eq.(4), we let Q = D and P =M, then ∀λ < 0 we have:
ED `(z)− EM `(z) ≥ G2λ
8 +
1 λ DKL(D‖M) (6)
In Eq.(5), we denote λ = λ0 > 0 and λ = −λ0 < 0 in Eq.(6). Then Eq.(5), Eq.(6) can be reformulated as:
ED′ `(z)− EM `(z) ≤ G2λ0
8 +
1
λ0 DKL(D′‖M)
EM `(z)− ED `(z) ≤ G2λ0
8 +
1
λ0 DKL(D‖M)
(7)
Adding the two inequalities in Eq.(7), we therefore have:
ED′ `(z) ≤ ED `(z) + 1
λ0
( DKL(D‖M) +DKL(D′‖M) ) + λ0 4 G2 (8)
Since the inequality holds for ∀λ0, then by taking λ0 = 2G √ DKL(D‖M) +DKL(D′‖M) we finally have: ED′ `(z) ≤ ED `(z) +
G√ 2
√ DJS(D′‖D) (9)
Let D′ = Dt and D = Dgt , we complete our proof.

heading: A.2 THEOREM 1
text: Proof. According to Definition of λ-consistency, we have:
dJS(Dg ∗ t ||Dt) ≤ dJS(D g∗ 2 ||D2) + |dJS(D g∗ t ||Dt)− dJS(D g∗ 2 ||D2)| ≤ dJS(D g∗ 2 ||D2) + λ
Similarly, we have the followings:
dJS(Dg ∗ t ||Dt) ≤ dJS(D g∗ i ||Di) + |dJS(D g∗ t ||Dt)− dJS(D g∗ i ||Di)| ≤ dJS(D g∗
i ||Di) + λ · · ·
dJS(Dg ∗ t ||Dt) ≤ dJS(Dg ∗ m ||Dm) + |dJS(D g∗ t ||Dt)− dJS(Dg ∗ m ||Dm)| ≤ dJS(Dg ∗
m ||Dm) + λ, which gives us
dJS(Dg ∗ t ||Dt) ≤ 1
m− 1 m∑ i=2 dJS(Dg ∗ i ||Di) + λ
Then, according to Lemma 1, we have
RDt(h) ≤ RDg∗t (h) + G√
2
√ dJS(Dg ∗ t ||Dt)
≤ RDg∗t (h) + G√
2
√√√√ 1 m− 1 m∑ i=2 dJS(Dg ∗ i ||Di) + λ
≤ RDg∗t (h) + G√
2(m− 1) (√√√√ m∑ i=2 dJS(Dg ∗ i ||Di) + √ (m− 1)λ )

heading: A.3 COROLLARY 1
text: We first introduce the upper bound for Jensen Shannon (JS) Divergence decomposition: Lemma 3. Let D(x, y) and D′(x, y) be two distributions over X × Y , D(y) and D′(y) be the corresponding marginal distribution of y, D(x|y) and D′(x|y) be the corresponding conditional distribution given y, then we can get the following bound, dJS(D(x, y)||D′(x, y)) ≤
dJS(D(y)||D′(y)) + Ey∼D(y)dJS(D(x|y)||D′(x|y)) + Ey∼D′(y)dJS(D(x|y)||D′(x|y))
Proof. LetM(x, y) = 12 (D(x, y) +D ′(x, y)), then we have
2 · dJS(D(x, y)||D′(x, y)) = dKL(D(x, y)||M(x, y)) + dKL(D′(x, y)||M(x, y)) = dKL(D(y)||M(y)) + Ey∼D(y)dKL(D(x|y)||M(x|y)) + dKL(D′(y)||M(y)) + Ey∼D′(y)dKL(D(x|y)||M(x|y)) = 2 · dJS(D(y)||D′(y)) + Ey∼D(y)dKL(D(x|y)||M(x|y)) + Ey∼D′(y)dKL(D(x|y)||M(x|y))
To bound the last two terms with JS divergence, we have:
dKL(D(x|y)||M(x|y)) ≤ dKL(D(x|y)||M(x|y)) + dKL(D′(x|y)||M(x|y)) (10) = 2 · dJS(D(x|y)||D′(x|y)).
Also, dKL(D′(x|y)||M(x|y)) ≤ dKL(D(x|y)||M(x|y)) + dKL(D′(x|y)||M(x|y)) (11) = 2 · dJS(D(x|y)||D′(x|y)). Combining (10) and (11) gives us dJS(D(x, y)||D′(x, y)) ≤ dJS(D(y)||D′(y)) + Ey∼D(y)dJS(D(x|y)||D′(x|y)) + Ey∼D′(y)dJS(D(x|y)||D′(x|y)), which concludes the proof.
Given Lemma 3, we are ready to prove Corollary 1.

heading: Proof.
text: RDt(h) ≤ RDg∗t (h) + G√
2(m− 1) √√√√ m∑ i=2 dJS(Dg ∗ i ||Di) +G √ λ 2
≤ RDg∗t (h) +G √ λ 2 + G√ 2(m− 1)
·√√√√ m∑ i=2 dJS(Dg ∗ i (y)||Di(y)) + Ey∼Di(y)dJS(D g∗ i (x|y)||Di(x|y)) + Ey∼Dg∗i (y)dJS(D g∗ i (x|y)||Di(x|y))
≤ RDg∗t (h) + G√
2(m− 1) (√√√√ m∑ i=2 dJS(Dg ∗ i (y)||Di(y)) + √ (m− 1)λ
+ √√√√ m∑ i=2 E y∼Dg ∗ i (y) dJS(Dg ∗ i (x|y)||Di(x|y)) + √√√√ m∑ i=2 Ey∼Di(y)dJS(D g∗ i (x|y)||Di(x|y)) ) .
]

heading: A.4 COMPARISON TO THE ASSUMPTIONS OF EXISTING STUDIES
text: Learning in a non-stationary environment is impossible if no assumption is imposed on the environment. Existing theoretical studies of evolving domain adaptation have made various assumptions on the evolving pattern of the environment to obtain meaningful results. Specifically, Kumar et al. (2020) assumes that ρ(Dt,Dt+1) < , where ρ(·, ·) is some distance measurement of distribution, and the assumption in Liu et al. (2020) is dH∆H(Dt1 ,Dt2) ≤ α|t1 − t2|. In other words, they both assume that the distance between two consecutive domains is small. Although such an assumption seems intuitive and reasonable, there are two fundamental issues:
1. Too restrictive for real-world scenarios. In many problems, the distance between two domains can be much larger than the difference of domain indices. For example, a small angular rotation may result in a large difference of the pixel-level data distribution. Existing assumptions will fail to characterize such a scenario since both ρ and dH∆H can be quite large, but this problem is still learnable in practice.
2. Not taking the algorithm into account. Both ρ and dH∆H are algorithm-independent in the sense that they only characterize the nature of an environment itself but does not involve any specific learning algorithm. Consequently, these assumptions cannot directly motivate any concrete strategies for learning the evolving pattern.
In contrast, our notion of λ-consistency: |dJS(Dg ∗ i ||Di) − dJS(D g∗
j ||Dj)| ≤ λ offers natural solutions to these issues:
1. It reveals that what really matters is not the distance between two consecutive domains but the stability (predictability) of the evolving pattern of an environment. Specifically, if the evolving pattern of an environment is stable (not necessarily slow), there will exist a mapping function such that λ is small. In other words, our notion indicates that generalization performance can still be guaranteed even though the distance between two consecutive domains is large, as long as λ is small.
2. It also highlights the role of the mapping function g. Since g∗ is unknown in practice, one primary objective of a PDG algorithm is essentially to minimize the distance between the real and mapped domains. In our implementation (i.e., DPNets), this objective is realized by estimating the prototypes of the next domain by leveraging the instances from the previous domain. Other realizations are also possible, which opens up avenues for future work.

heading: B ADDITIONAL EXPERIMENTS

heading: B.1 FURTHER INVESTIGATION OF INTERPOLATION AND EXTRAPOLATION
text: In Table 2, we can observe that the performances of ERM are not improved as the number of domains increases, which is counter-intuitive. We speculate that this is due to the “extrapolation” nature of PDG. To further investigate its impact on the generalization performance on the target domain, we compare the following three settings on the RMNIST dataset:
1. DPNets-Evolving (Extrapolation). Same as DPNets in Section 4, where the target domain Dt = Di+1.
2. ERM-Evolving (Extrapolation). Same as ERM in Section 4, where the target domain Dt = Di+1.
3. ERM-Interpolation. The ERM approach using the domain in the middle as the target domain, and the rest domains as the source domains.
Note that (1) and (2) are different algorithms with the same problem setup, and (2) and (3) use the same algorithm but with different problem setups.
We vary the the numbers of domain numbers and domain distances, and the results are reported in Fig. 6, from which we have the following observations:
1. The overall trend of the DPNets is going up as the number of domains increases.
2. The performances of ERM-Evolving do not increase as a function of the number of domain distance, which is consistent with the results in Table 2.
3. The performances of ERM-Interpolation increase as a function of the number of domain distance
4. The improvements of DPNets and ERM-Interpolation are not obvious once having sufficient amount of domains (e.g., # of domains = 7 for ERM-Interpolation). We conjecture that it is because the evolving pattern of RMNIST is relatively simple. Thus, a small number of domains are sufficient to learn such a pattern, and increasing the number of domains may not necessarily improve the performances of DPNets and ERM-Interpolation anymore.
The results indicate for extrapolation, having more domains does not necessarily help learn an invariant representation if we do not leverage the evolving pattern. Intuitively, as the target domain is on the “edge” of the domains, having more domains also indicates that it is further away from the “center” of the source domains, which may even make the generalization even more challenging. On the other hand, if the target domain is “among” the source domains (i.e., when we perform “interpolation”), the source domains may act as augmented data which improve the generalization performance. In other words, if the more source domains will be beneficial for “interpolation” but not necessarily for “extrapolation” if the evolving pattern is not properly exploited.
B.2 INCORPORATING DOMAIN INFORMATION INTO ERM.
The ERM in Section 4 does not leverage the index information of the source domains. In order to make a more fair comparison, we incorporate the index information into ERM. Specifically, we investigate three strategies for incorporating the index information used in the literature: (1) Index Concatenation (Fig. 7a), where the domain index is directly concatenated as a one-dimension feature (Li et al., 2021); (2) One-hot Concatenation (Fig. 7b), where the domain index is first one-hot encoded and then concatenated to the original features (Long et al., 2017); (3) Outer product (Fig. 7c), where flattened the outer product of original features and the one-hot indexes is used as the final input (Shui et al., 2021b).

heading: Strategy EvolCircle RPlate Average
text: We evaluate the algorithms on the EvolCircle and RPlate datasets and the results are reported in Table 4. The experimental results verify the advantage of our algorithm in exploiting evolving information. We can observe that the improvements induced by incorporating domain index is marginal, which indicates that it cannot properly leverage the evolving pattern of the environment.
C IMPLEMENTATION DETAILS
We implement our algorithm based on Gulrajani & Lopez-Paz (2020). To justify algorithm comparison between baselines and our algorithm, we adopted a random search of 20 trials for the hyperparameter distribution. For each parameter combination, 5 repeated experiments are conducted. Then, we report the highest average performance for each algorithm-dataset pair. In this way, all parameters are automatically selected without human intervention, making the comparison of experimental results of different algorithms on different data fair and reliable. Almost all backbone and setting are following Gulrajani & Lopez-Paz (2020) except the followings. In one singe experiment, the model structure of fφ and fψ keeps the same. For EvolCircle and RPlate, we only use one single layer network to make the classifier linear for all algorithms. For other dataset, network are randomly chose based on the random search algorithm.

Review summaries:
Summary:  The paper proposes a new domain generalization paradigm called evolving domain generalization, where the source domains and the target domain are not random but have an evolving pattern.  The paper provides theoretical results on the evolving domain generalization, which bounds the target domain test error with synthetic domains.  The paper proposes a new approach for evolving domain generalization, which learns two embedding functions to derive the synthetic domains and minimize the distances between the synthetic domains and the real domains within the hidden space  The paper conducts experiments on three domain generalization datasets including RMNIST, Portrait, and Cover Type.  

This paper tackles the issue of training a model to generalize to data from unseen domains when there is a natural progression between domain at training and test time (eg. temporal progression). With the assumption that there is a fixed underlying transformation "g" which underlies the evolution of the data distributions, they propose a training algorithm based on progressive net which simultaneously learns g as well as well as a strong classifier. The resulting model can be used on unseen domains at test-time, leveraging the learned transformation to extrapolate to the new domain.

In domain generalization (DG), we normally assume that the target domain is static rather than dynamic. However, we might meet many dynamic target domains in the real world (e.g., domains change over time), which will cause significant prediction errors on such dynamic target domains. To avoid this issue, this paper considers a new problem setting: directional DG (DDG), where target domains will dynamically change over time/rules/directions.   To address this very challenging problem, this paper first analyses the property of DDG and defines the consistency between two near target domains. Based on this new definition, the authors propose a new generalization bound for the target domains. Such consistency definition also uses g* to connect all target domains and make the DDG solvable under some assumptions. Based on this bound, a meta-learning-inspired method is proposed to address DDG: directional prototypical network. Empirical evaluation on both synthetic and real-world data sets validates the effectiveness of the proposed approach.  In general, this paper contributes a novel problem setting and a valid solution to this setting. Although some motivations are unclear, the contributions of this paper are enough.