summaries: This paper defines a notion of "transferability" between features from different domains, which is different from common distribution discrepancy measures such as total variation and Wasserstein distance. This measure of transferability is measured with labeled samples from both domains, and provides a bound on the target error. The empirically test transferability of the features learned by current domain generalization algorithms, and some don't do that well in this transferability measure. They propose an algorithm based on optimizing the measure of transferability across training domains and test it on some domain generalization datasets, including a satellite dataset. Authors introduced the notion of transferability between pairs of domains (i.e. joint distributions over input x output spaces) along with a discrepancy measure, which can be used to assess how dissimilar are two data sources relative to a given class of predictors. Such a quantity may be useful in either assessing how well is a trained model likely to perform on new data, or as a training signal so that more preference is given to predictors able to generalize out of the training data distribution. The main strength of this work in my opinion is the fact that the proposed transferability measure accounts for the joint distributions over data and labels. However, while I appreciate the depth of the discussion and results in terms of the properties of the proposal, I believe a key missing discussion is the effect that commonly used sets of assumptions have in the proposed transferability measure. Moreover, the evaluation lacks in evidencing the benefits of the proposal relative to current strategies. Please refer to the following for further details. This paper aims at identifying and quantifying transferability in learning algorithms. The paper proposes a new upper bound on the target error. The proposed algorithm is an adversarial optimisation problem that empirically proved to be effective.  This paper aims to provide a formulation of transferability. The main intuition is that any near-optimal source classifier should be also near-optimal on the target domain. So the authors quantify transferability by measuring the relation between near-optimal classifiers in source and target domains and derive genralization bounds based on this. In addition, new algorithm is proposed based on the intuition.
abstractText: Out-of-distribution generalization is one of the key challenges when transferring a model from the lab to the real world. Existing efforts mostly focus on building invariant features among source and target domains. Based on invariant features, a high-performing classifier on source domains could hopefully behave equally well on a target domain. In other words, we hope the invariant features to be transferable. However, in practice, there are no perfectly transferable features, and some algorithms seem to learn “more transferable” features than others. How can we understand and quantify such transferability? In this paper, we formally define transferability that one can quantify and compute in domain generalization. We point out the difference and connection with common discrepancy measures between domains, such as total variation and Wasserstein distance. We then prove that our transferability can be estimated with enough samples and give a new upper bound for the target error based on our transferability. Empirically, we evaluate the transferability of the feature embeddings learned by existing algorithms for domain generalization. Surprisingly, we find that many algorithms are not quite learning transferable features, although few could still survive. In light of this, we propose a new algorithm for learning transferable features and test it over various benchmark datasets, including RotatedMNIST, PACS, Office-Home and WILDS-FMoW. Experimental results show that the proposed algorithm achieves consistent improvement over many state-of-the-art algorithms, corroborating our theoretical findings.1
authors.name: Guojun Zhang
authors.name: Han Zhao
references.authors: Kartik Ahuja Karthikeyan Shanmugam Kush Varshney Amit Dhurandhar
references.title: Invariant risk minimization games
references.venue: In International Conference on Machine Learning,
references.authors: Isabela Albuquerque João Monteiro Mohammad Darvishi Tiago H Falk Ioannis Mitliagkas
references.title: Generalizing to unseen domains via distribution matching
references.authors: Martin Arjovsky Léon Bottou Ishaan Gulrajani David Lopez-Paz
references.title: Invariant risk minimization
references.venue: arXiv preprint arXiv:1907.02893,
references.authors: Sanjeev Arora Rong Ge Yingyu Liang Tengyu Ma Yi Zhang
references.title: Generalization and equilibrium in generative adversarial nets (GANs)
references.venue: In International Conference on Machine Learning,
references.authors: Peter L Bartlett Shahar Mendelson
references.title: Rademacher and gaussian complexities: Risk bounds and structural results
references.venue: Journal of Machine Learning Research,
references.authors: Peter L Bartlett Michael I Jordan Jon D McAuliffe
references.title: Convexity, classification, and risk bounds
references.venue: Journal of the American Statistical Association,
references.authors: Peter L Bartlett Nick Harvey Christopher Liaw Abbas Mehrabian
references.title: Nearly-tight VCdimension and pseudodimension bounds for piecewise linear neural networks
references.venue: J. Mach. Learn. Res.,
references.authors: Shai Ben-David John Blitzer Koby Crammer Fernando Pereira
references.title: Analysis of representations for domain adaptation
references.venue: In Advances in neural information processing systems,
references.authors: Shai Ben-David John Blitzer Koby Crammer Alex Kulesza Fernando Pereira Jennifer Wortman Vaughan
references.title: A theory of learning from different domains
references.venue: Machine learning,
references.authors: Gilles Blanchard Gyemin Lee Clayton Scott
references.title: Generalizing from several related classification tasks to a new unlabeled sample
references.venue: Advances in neural information processing systems,
references.authors: Gilles Blanchard Aniket Anand Deshmukh Urun Dogan Gyemin Lee Clayton Scott
references.title: Domain generalization by marginal transfer learning
references.venue: Journal of Machine Learning Research,
references.authors: John Blitzer Koby Crammer Alex Kulesza Fernando Pereira Jennifer Wortman
references.title: Learning bounds for domain adaptation
references.venue: In Advances in neural information processing systems,
references.authors: Ting Chen Simon Kornblith Mohammad Norouzi Geoffrey Hinton
references.title: A simple framework for contrastive learning of visual representations
references.venue: In Proceedings of the 37th International Conference on Machine Learning,
references.authors: Gordon Christie Neil Fendley James Wilson Ryan Mukherjee
references.title: Functional map of the world
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Jeremy Cohen Elan Rosenfeld Zico Kolter
references.title: Certified adversarial robustness via randomized smoothing
references.venue: In International Conference on Machine Learning,
references.authors: Yaroslav Ganin Victor Lempitsky
references.title: Unsupervised domain adaptation by backpropagation
references.venue: In International conference on machine learning,
references.authors: Yaroslav Ganin Evgeniya Ustinova Hana Ajakan Pascal Germain Hugo Larochelle François Laviolette Mario Marchand Victor Lempitsky
references.title: Domain-adversarial training of neural networks
references.venue: The Journal of Machine Learning Research,
references.authors: Muhammad Ghifary W Bastiaan Kleijn Mengjie Zhang David Balduzzi
references.title: Domain generalization for object recognition with multi-task autoencoders
references.venue: In Proceedings of the IEEE international conference on computer vision,
references.authors: Jean-Bastien Grill Florian Strub Florent Altché Corentin Tallec Pierre H. Richemond Elena Buchatskaya Carl Doersch Bernardo Ávila Pires Zhaohan Guo Mohammad Gheshlaghi Azar Bilal Piot Koray Kavukcuoglu Rémi Munos Michal Valko
references.title: Bootstrap your own latent - a new approach to self-supervised learning
references.venue: NeurIPS,
references.authors: Ishaan Gulrajani David Lopez-Paz
references.title: In search of lost domain generalization
references.venue: arXiv preprint arXiv:2007.01434,
references.authors: Kaiming He Haoqi Fan Yuxin Wu Saining Xie Ross Girshick
references.title: Momentum contrast for unsupervised visual representation learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Zeyi Huang Haohan Wang Eric P. Xing Dong Huang
references.title: Self-challenging improves crossdomain generalization
references.venue: In ECCV,
references.authors: Pang Wei Koh Shiori Sagawa Henrik Marklund Sang Michael Xie Marvin Zhang Akshay Balsubramani Weihua Hu Michihiro Yasunaga Richard Lanas Phillips Irena Gao
references.title: WILDS: A benchmark of in-the-wild distribution shifts
references.venue: arXiv preprint arXiv:2012.07421,
references.authors: Vladimir Koltchinskii
references.title: Rademacher complexities and bounding the excess risk in active learning
references.venue: The Journal of Machine Learning Research,
references.authors: Masanori Koyama Shoichiro Yamaguchi
references.title: When is invariance useful in an out-of-distribution generalization problem
references.authors: David Krueger Ethan Caballero Joern-Henrik Jacobsen Amy Zhang Jonathan Binas Dinghuai Zhang Remi Le Priol Aaron Courville
references.title: Out-of-distribution generalization via risk extrapolation (Rex)
references.authors: Christoph H Lampert Hannes Nickisch Stefan Harmeling
references.title: Learning to detect unseen object classes by between-class attribute transfer
references.venue: IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Da Li Yongxin Yang Yi-Zhe Song Timothy M Hospedales
references.title: Deeper, broader and artier domain generalization
references.venue: In Proceedings of the IEEE international conference on computer vision,
references.authors: Da Li Yongxin Yang Yi-Zhe Song Timothy Hospedales
references.title: Learning to generalize: Metalearning for domain generalization
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Haoliang Li Sinno Jialin Pan Shiqi Wang Alex C Kot
references.title: Domain generalization with adversarial feature learning
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Ya Li Xinmei Tian Mingming Gong Yajing Liu Tongliang Liu Kun Zhang Dacheng Tao
references.title: Deep domain generalization via conditional invariant adversarial networks
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV),
references.authors: Mingsheng Long Han Zhu Jianmin Wang Michael I Jordan
references.title: Deep transfer learning with joint adaptation networks
references.venue: In International conference on machine learning,
references.authors: Aleksander Madry Aleksandar Makelov Ludwig Schmidt Dimitris Tsipras Adrian Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: In International Conference on Learning Representations,
references.authors: Mehryar Mohri Afshin Rostamizadeh Ameet Talwalkar
references.title: Foundations of machine learning
references.venue: MIT press,
references.authors: Krikamol Muandet David Balduzzi Bernhard Schölkopf
references.title: Domain generalization via invariant feature representation
references.venue: In International Conference on Machine Learning,
references.authors: Alfred Müller
references.title: Integral probability metrics and their generating classes of functions
references.venue: Advances in Applied Probability,
references.authors: Hyeonseob Nam HyunJae Lee Jongchan Park Wonjun Yoon Donggeun Yoo
references.title: Reducing domain gap via style-agnostic networks
references.venue: arXiv preprint arXiv:1910.11645,
references.authors: Balas K Natarajan
references.title: On learning sets and functions
references.venue: Machine Learning,
references.authors: Jonas Peters Peter Bühlmann Nicolai Meinshausen
references.title: Causal inference by using invariant prediction: identification and confidence intervals
references.venue: Journal of the Royal Statistical Society. Series B (Statistical Methodology),
references.authors: Mohammad Pezeshki Sékou-Oumar Kaba Yoshua Bengio Aaron Courville Doina Precup Guillaume Lajoie
references.title: Gradient starvation: A learning proclivity in neural networks
references.venue: arXiv preprint arXiv:2011.09468,
references.authors: Elan Rosenfeld Pradeep Kumar Ravikumar Andrej Risteski
references.title: The risks of invariant risk minimization
references.venue: In International Conference on Learning Representations,
references.authors: Walter Rudin
references.title: Real and complex analysis
references.venue: McGraw-Hill Education,
references.authors: Shiori Sagawa Pang Wei Koh Tatsunori B. Hashimoto Percy Liang
references.title: Distributionally robust neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Shai Shalev-Shwartz Shai Ben-David
references.title: Understanding machine learning: From theory to algorithms
references.venue: Cambridge university press,
references.authors: Aman Sinha Hongseok Namkoong Riccardo Volpi John Duchi
references.title: Certifying some distributional robustness with principled adversarial training
references.venue: arXiv preprint arXiv:1710.10571,
references.authors: Bharath K Sriperumbudur Kenji Fukumizu Arthur Gretton Bernhard Schölkopf Gert RG Lanckriet
references.title: On the empirical estimation of integral probability metrics
references.venue: Electronic Journal of Statistics,
references.authors: Baochen Sun Kate Saenko
references.title: Deep CORAL: Correlation alignment for deep domain adaptation
references.venue: In European conference on computer vision,
references.authors: Remi Tachet des Combes Han Zhao Yu-Xiang Wang Geoffrey J Gordon
references.title: Domain adaptation with conditional distribution matching and generalized label shift
references.venue: Advances in Neural Information Processing Systems,
references.authors: Eric Tzeng Judy Hoffman Kate Saenko Trevor Darrell
references.title: Adversarial discriminative domain adaptation
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Vladimir Vapnik
references.title: Principles of risk minimization for learning theory
references.venue: In Advances in neural information processing systems,
references.authors: Hemanth Venkateswara Jose Eusebio Shayok Chakraborty Sethuraman Panchanathan
references.title: Deep hashing network for unsupervised domain adaptation
references.venue: In (IEEE) Conference on Computer Vision and Pattern Recognition
references.authors: Riccardo Volpi Hongseok Namkoong Ozan Sener John C Duchi Vittorio Murino Silvio Savarese
references.title: Generalizing to unseen domains via adversarial data augmentation
references.venue: NeurIPS,
references.authors: Minghao Xu Jian Zhang Bingbing Ni Teng Li Chengjie Wang Qi Tian Wenjun Zhang
references.title: Adversarial domain adaptation with domain mixup
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Shen Yan Huan Song Nanxiang Li Lincan Zou Liu Ren
references.title: Improve unsupervised domain adaptation with mixup training
references.venue: arXiv preprint arXiv:2001.00677,
references.authors: Haotian Ye Chuanlong Xie Tianle Cai Ruichen Li Zhenguo Li Liwei Wang
references.title: Towards a theoretical framework of out-of-distribution generalization, 2021
references.authors: Yu Zhang Qiang Yang
references.title: A survey on multi-task learning
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Yuchen Zhang Tianle Liu Mingsheng Long Michael Jordan
references.title: Bridging theory and algorithm for domain adaptation
references.venue: In International Conference on Machine Learning,
references.authors: Han Zhao Shanghang Zhang Guanhang Wu José MF Moura Joao P Costeira Geoffrey J Gordon
references.title: Adversarial multiple source domain adaptation
references.venue: Advances in neural information processing systems,
references.authors: Han Zhao Remi Tachet Des Combes Kun Zhang Geoffrey Gordon
references.title: On learning invariant representations for domain adaptation
references.venue: In International Conference on Machine Learning,
sections.heading: 1 Introduction
sections.text: One of the cornerstone assumptions underlying the recent success of deep learning models is that the test data should share the same distribution as the training data. However, faced with ubiquitous distribution shifts in various real-world applications, such assumption hardly holds in practice. For example, a self-driving recognition system trained using data collected in the daytime may continually degrade its performance during nightfall. The system may also encounter weather or traffic conditions in a new city that never appear in the training set. In light of these potentially unseen scenarios, it is
  1Code available at https://github.com/Gordon-Guojun-Zhang/Transferability-NeurIPS2021.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  of paramount importance that the trained model can generalize Out-Of-Distribution (OOD): even if the target domain is not exactly the same as the source domain(s), the learned model should hopefully behave robustly under slight distribution shift.
  To this end, one line of works focuses on learning the so-called invariant representations [2, 16, 57, 58]. At a colloquial level, the goal here is to learn feature embeddings that lead to indistinguishable feature distributions from different domains. In practice, both the feature embeddings and the domain discriminators are often parametrized by neural networks, leading to an adversarial game between these two. Furthermore, in order to avoid degenerate solutions, the learned features are required to be informative about the output variable as well. This is enforced by placing a predictor over the features and minimize the corresponding supervised loss simultaneously [17, 32, 48, 49].
  Another line of recent works aims to learn features that can induce invariant predictors, first termed as the invariant risk minimization (IRM) [3, 39] paradigm. Roughly speaking, the goal of IRM is to discover a feature embedding, upon which the optimal predictors, i.e., the Bayes predictor, are invariant across the training domains. Again, at the same time, the features should be informative about the output variable as well. However, the optimization problem of IRM is rather difficult, and several follow-up works have proposed different relaxations to the original formulation [1, 26].
  Despite being extensively studied, both theoretical [41, 59] and empirical [20, 23] works have shown the insufficiency of existing algorithms for domain generalization (DG). Methods based on invariant features ignore the potential shift in the marginal label distributions across domains [59] and the methods based on invariant predictors are not robust to covariate shift [26]. Perhaps surprisingly, empirical works have shown that with proper data augmentation and careful model tuning, the very basic algorithm of empirical risk minimization (ERM) demonstrates superior performance on domain generalization over existing methods on benchmark image datasets [20, 23]. This sharp gap between theory and practice calls for a fundamental understanding of the following question:
  What kind of invariance should we look for, in order to ensure that a good model on source domains also achieves decent accuracy on a related target domain?
  In this work we attempt to answer the above question by proposing a criterion for models to look at, dubbed as transferability, which asks for an invariance of the excess risks of a predictor across domains. Different from existing proposals of invariant features and invariant predictors, which seek to find feature embeddings that respectively induce invariant marginal and conditional distributions, our notion of transferability depends on the excess risk, hence it directly takes into account the joint distribution over both the features and the labels. We show how it can be used to naturally derive a new upper bound for the target error, and then we discuss how to estimate the transferability empirically with enough samples. Our definition also inspires a method that aims to find more transferable features via representation learning using adversarial training.
  Empirically, we perform experiments to measure the transferability of several existing algorithms, on both small and large scale datasets. We show that many algorithms, including ERM, are not quite transferable under the definition (Fig. 1, see more details in §5): when we go away from the optimal classifier (with distance δ in the parameter space), it could happen that the source accuracy remains high but the target accuracy drops significantly. This implies that during the training process, an existing algorithm may find a good source classifier with low target accuracy, hence violating the requirement for invariance of excess risks. In contrast, our algorithm is more transferable, and achieves consistent improvement over existing state-of-the-art algorithms, corroborating our findings.
sections.heading: 2 What is Transferability?
sections.text: In this section we present our definition of transferability in the classification setting. The setup of domain generalization is the following:
  Settings and Notation Given n labeled source domains S1, . . . ,Sn, the problem of domain generalization is to learn a model from these source domains, in the hope that it performs well on an
  unseen target domain T that is “similar” to the source domains. Throughout the paper, we assume that both the source domains and the unseen target domain share the same input and output spaces, denoted as X and Y , respectively. For multi-class classification, the output space Y = [K] is a set of labels for multi-class classification. For binary classification, we consider Y = {−1,+1}. DenoteH as the hypothesis class. We define the classification error of a classifier h ∈ H on a domain D (or S for source domains, or T for target domains) as:2
  D(h) = E(x,y)∼D[`(h(x), y)]. (1)
  For `(h(x), y) = 1(h(x) 6= y), where 1(·) is the usual indicator function, we use 0−1D (h) to denote it is the 0-1 loss.
  In domain generalization, we often have several source domains. For the ease of presentation, we only consider a single source domain in this section, and later extend to the general case in Section 5. Given two domains, the source domain S and the target domain T , the task of domain generalization is to transfer a classifier h that performs well on S to T . We ask: how much of the success of h on S can be transferred to T ? Note that in order to evaluate the transferability from S to T , we need information from the target domain, similar to the test phase in traditional supervised learning. We believe a good criterion of transferability should satisfy the following properties:
  1. Quantifiable: the notion should be quantifiable and can be computed in practice; 2. Any near-optimal source classifier should be near-optimal on the target domain. 3. If the two domains are similar, as measured by e.g., total variation, then they are transferable
  to each other, but the converse may not be true.
  At first glance the second criterion above might seem too strong and restrictive. However, we argue that in the task of domain generalization, we only have labeled source data and there is no clue to distinguish a classifier from another if both of them perform equally well on the source domain. Based on the second property, we first propose the following definition of transferability: Definition 1 (transferability). S is (δS , δT )H-transferable to T if for δS > 0, there exists δT > 0 such that argmin( S , δS)H ⊆ argmin( T , δT )H, where:
  argmin( D, δD)H := {h ∈ H : D(h) ≤ inf h∈H D(h) + δD}.
  In the literature the set argmin( D, δD)H is also known as a δD-minimal set [24] of D, which represents the near-optimal set of classifiers. Note that the δ-minimal set depends on the hypothesis classH. Throughout the paper, we omit the subscriptH in the definition when there is no confusion. Def. 1 says that near-optimal source classifiers are also near-optimal target classifiers. Furthermore, it is easy to verify that our transferability is transitive: if S is (δS , δP)-transferable to P , and P is (δP , δT )-transferable to T , then S is (δS , δT )-transferable to T . Next we define transfer measures, which we will show to be equivalent with Def. 1 in Prop. 5. Definition 2 (quantifiable transfer measures). Given some Γ ⊆ H, ∗S := infh∈Γ S(h) and ∗T := infh∈Γ T (h) we define the one-sided transfer measure, symmetric transfer measure and the realizable transfer measure respectively as:
  TΓ(S‖T ) := sup h∈Γ T (h)− ∗T − ( S(h)− ∗S), (2) TΓ(S, T ) := max{TΓ(S‖T ), TΓ(T ‖S)} = sup h∈Γ | S(h)− ∗S − ( T (h)− ∗T )|, (3)
  TrΓ(S, T ) := sup h∈Γ | S(h)− T (h)|. (4)
  The distinction between Γ andH will become apparent in Prop. 5. Note that the one-sided transfer measure is not symmetric. If we want the two domains S and T to be mutually transferable to each other, we can use the symmetric transfer measure. We call both quantities as transfer measures. Furthermore, the symmetric transfer measure reduces to (4) in the realizable case when ∗S = ∗ T = 0. In statistical learning theory, D(h)− ∗D is often known as an excess risk [24], which is the relative error compared to the optimal classifier. The transfer measures can thus be represented with the difference of excess risks. With Def. 2, we can immediately obtain the following result that upper bounds the target error:
  2Throughout the paper, we will use the terms domain and distribution interchangeably.
  Proposition 3 (target error bound). Given Γ ⊆ H, for any h ∈ Γ, the target error is bounded by: T (h) ≤ S(h) + ∗T − ∗S + TΓ(S‖T ) ≤ S(h) + ∗T − ∗S + TΓ(S, T ). (5)
  The first error bound of such type for a target domain uses H-divergence [8, 9, 12] for binary classification (or more rigorously, the H∆H-divergence). The main difference between ours and H-divergence is that H-divergence only concerns about the marginal input distributions, whereas the transfer measures depend on the joint distributions over both the inputs and the labels. We note that Proposition 3 is general and works in the multi-class case as well. Moreover, even in the binary classification case we can prove that our Proposition 3 is tighter thanH-divergence (see Proposition 27 in the appendix).
  In practice we may not know the optimal errors. In this case, we can use the realizable transfer measure to upper bound the symmetric transfer measure (note that ∗S or ∗ T may not be zero): Proposition 4. For Γ ⊆ H and domains S, T we have: TΓ(S, T ) ≤ 2TrΓ(S, T ).
  Since Def. 1 essentially asks that the excess risks of approximately optimal classifiers on the source domain are comparable between the source and target domains, we can show that Def. 1 and Def. 2 are equivalent if Γ is a δ-minimal set: Proposition 5 (equivalence between transferability and transfer measures). Let δS > 0 and Γ = argmin( S , δS) and suppose infh∈Γ T (h) = infh∈H T (h). If TΓ(S‖T ) ≤ δ or TΓ(S, T ) ≤ δ, then S is (δS , δ + δS)-transferable to T . Furthermore, if S is (δS , δT )-transferable to T , then TΓ(S‖T ) ≤ δT and TΓ(S, T ) ≤ max{δS , δT }.
  In Prop. 5, we do not require Γ = H since it is unnecessary to impose that all classifiers inH have similar excess risks on source and target domains. Instead, we only constrain Γ to be a δ-minimal set, i.e., Γ includes approximately optimal classifiers of S . See also Example 8. An additional assumption is that Γ also includes the optimal classifier of T which can be ensured by controlling δS .
sections.heading: 2.1 Comparison with other discrepancy measures between domains
sections.text: In this subsection, we compare the realizable transfer measure (4) with other discrepancy measures between domains and focus on the 0-1 loss 0−1D . We first note that T r Γ(S, T ) can be written as an integral probability metric (IPM) [36, 46]. The l.h.s. of (4) can be written as:
  TrΓ(S, T ) := dFΓ(S, T ), where dF (S, T ) = sup f∈F ∣∣∣∣∣∑ y ∫ f(x, y)(pS(x, y)− pT (x, y))dx ∣∣∣∣∣ , (6) and FΓ := {(x, y) 7→ 1(h(x) 6= y), h ∈ Γ}. Typical IPMs [46] include MMD, Wasserstein distance, Dudley metric and the Kolmogorov–Smirnov distance (see Appendix B.2 for more details). However, FΓ is fundamentally different from these IPMs since it relies on an underlying function class Γ. Our realizable transfer measure shares some similarity with Arora et al. [4], where a changeable function class is used, but the exact choices of the function class are different.
  Even though the transferability can be written in terms of IPM, it is in fact a pseudo-metric: Proposition 6 (pseudo-metric). For a general loss D as in (1), TrΓ(S, T ) is a pseudo-metric, i.e., for any distributions S, T ,P on the same underlying space, we have TrΓ(S,S) = 0, TrΓ(S, T ) = T rΓ (T ,S) (symmetry), and TrΓ(S, T ) ≤ TrΓ(S,P) + TrΓ(P, T ) (triangle inequality).
  However in general TrΓ(S, T ) is not a metric since TrΓ(S, T ) = 0 even if S 6= T . For instance, taking Γ = {h∗} to be the optimal classifier on both S and T . we have TrΓ(S, T ) = 0, but S and T could differ a lot (see Figure 2). In the next result we discuss the connection between realizable transfer measures and total variation (c.f. Appendix B.2). Proposition 7 (equivalence with total variation). For binary classification with labels {−1, 1}, given the 0-1 loss D = 0−1D , we have T r Γ(S, T ) ≤ dTV(S, T ) for domains S, T and any Γ ⊆ H. DenoteHt to be the set of all binary classifiers. Then we have dTV(S, T ) ≤ 4TrHt(S, T ).
  Prop. 7 tells us that transfer measures (see also Prop. 4) are no stronger than total variation, and in the realizable case, (3) is equivalent to the similarity of domains (as measured by total variation) if Γ is unconstrained. We can moreover show that transfer measures are strictly weaker, if we choose Γ to be some δ-minimal set:
  Example 8 (very dissimilar joint distributions but transferable). We study the distributions described in Figure 2. The joint distributions are very dissimilar, i.e., for any X,Y in the domain, |pS(X,Y )− pT (X,Y )| = 0.8. Define
  hρ(X) = { 1 if − 1 ≤ X < ρ −1 if ρ ≤ X < 1 . (7)
  We choose the hypothesis classH = {hρ, ρ ∈ [−1, 1]} and Γ = {hρ, |ρ| ≤ δ/0.8} (for small δ, say δ < 0.01) to be some neighborhood of the optimal source classifier h∗ = h0. Then TΓ(S, T ) = suph∈Γ | S(h)− T (h)| = δ, and S is (δS , δ+ δS)-transferable to T on Γ for any δS > 0 according to Prop. 5. Note that ∗S = ∗ T = 0.
sections.heading: 3 Computing Transferability
sections.text: In the last section we proposed a new concept called transferability. However, although Def. 1 provides a theoretically sound result for transferability, it is hard to verify it in practice, since we cannot exhaust all approximately good classifiers, especially for rich models such as deep neural networks. Nevertheless, Prop. 3 and Prop. 5 provide a framework to compute transferability through transfer measures, despite their simplicity. In this section we discuss how to compute these quantities by making necessary approximations based on transfer measures. There are two difficulties we need to overcome: (1) In practice we only have finite samples drawn from true distributions; (2) We need a surrogate loss such as cross entropy for training and the 0-1 loss for evaluation. In §3.1 we show that our transfer measures can be estimated with enough samples, and in §3.2 we discuss transferability with a surrogate loss.
  These results will be used in our algorithms in the next section.
sections.heading: 3.1 Estimation of transferability
sections.text: We show how to estimate the transfer measure TΓ(S‖T ) from finite samples. Other versions of transfer measures in Def. 1 follow analogously (see Appendix A for more details).
  Lemma 9 (reduction of estimation error). Given general loss D as in (1), suppose Ŝ and T̂ are i.i.d. sample distributions drawn from distributions of S and T , then for any Γ ⊆ H we have:
  TΓ(S‖T ) ≤ TΓ(Ŝ‖T̂ ) + 2estΓ(S) + 2estΓ(T ), with the estimation errors estΓ(S) = suph∈Γ | S(h)− Ŝ(h)|, estΓ(T ) = suph∈Γ | T (h)− T̂ (h)|.
  This lemma tells us that estimating transferability is no harder than computing the estimation errors of both domains. If the function class Γ has uniform convergence property [44], then we can guarantee efficient estimation of transferability. We first bound the sample complexity through Rademacher complexity, which is a standard tool in bounding estimation errors [5]:
  Theorem 10 (estimation error with Rademacher complexity). Given the 0-1 loss D = 0−1D , suppose Ŝ and T̂ are sample sets with m and k samples drawn i.i.d. from distributions S and T , respectively. For any Γ ⊆ H the following holds with probability 1− δ:
  TΓ(S‖T ) ≤ TΓ(Ŝ‖T̂ ) + 4Rm(FΓ) + 4Rk(FΓ) + 2 √ log(4/δ)
  2m + 2
  √ log(4/δ)
  2k ,
  where FΓ := {(x, y) 7→ 1(h(x) 6= y), h ∈ Γ}. If furthermore, Γ is a set of binary classifiers with labels {−1, 1}, then 2Rm(FΓ) = Rm(Γ), 2Rk(FΓ) = Rk(Γ).
  We also provide estimation error results using Vapnik–Chervonenkis (VC) dimension and Natarajan dimension in Appendix B.3. It is worth mentioning that the VC dimension of piecewise-polynomial neural networks has been upper bounded in Bartlett et al. [7]. Since transfer measures can be estimated, in later sections we do not distinguish the sample sets Ŝ, T̂ and the underlying distributions S, T .
sections.heading: 3.2 Transferability with a surrogate loss
sections.text: Due to the intractability of minimizing the 0-1 loss, we need to use a surrogate loss [6] for training in practice. In this section, we discuss this nuance w.r.t. transferability. We will focus on the most commonly used surrogate loss, cross entropy (CE), although some of the results can be easily adapted to other loss functions. To distinguish a surrogate loss from the 0-1 loss, we use D from now on for a surrogate loss and 0−1D for the 0-1 loss. One of the difficulties is the non-equivalence between δ-minimal sets w.r.t. the 0-1 loss and a surrogate loss, i.e. argmin( D, δD) might be quite different from argmin( 0−1D , δD). Moreover, it is not practical to find all elements in argmin( 0−1 D , δD) since the loss is nonconvex and nonsmooth. In light of these difficulties, we propose a more practical notion of transferability based on surrogate loss D: Proposition 11 (transfer measure with a surrogate loss). Given surrogate loss D ≥ 0−1D on a general domain D. Suppose Γ = argmin( S , δS) and denote ∗T = infh∈Γ T (h), ∗S = infh∈Γ S(h), ( 0−1T ) ∗ = infh∈H 0−1 T (h). If the following holds:
  TΓ(S‖T ) = sup h∈Γ T (h)− ∗T − ( S(h)− ∗S) ≤ δ, (8)
  then we have argmin( S , δS) ⊆ argmin( 0−1 T , δ + δS + ∗ T − ( 0−1 T ) ∗).
  This proposition implies that if the transfer measure is small, then a near-optimal classifier of the surrogate loss in the source domain would be near-optimal in the target domain for the 0-1 loss. It also gives us a practical framework to guarantee transferability, which we will discuss in more depth in Section 4. Assume D : H → R to be Lipschitz continuous and strongly convex, which is satisfied for the cross entropy loss (see Appendix B.4). We are able to translate the δ-minimal set to Lp balls in the function space:
  C1‖h− h∗‖2,D ≤ D(h)− D(h∗) ≤ C2‖h− h∗‖1,D, (9) where C1 and C2 are absolute constants and h∗ is an optimal classifier. The function norms ‖ · ‖1,D and ‖ · ‖2,D are the usual Lp norms over distribution D. Since the classifier h = q(θ, ·) is usually parameterized with, say a neural network, we further upper bound the function norms by the distance of parameters, that is, for 1 ≤ p < ∞, h = q(θ, ·) and h′ = q(θ′, ·), we have ‖h − h′‖p,D ≤ L‖θ − θ′‖2, with L some Lipschitz constant of q (Appendix B.4). Combined with (9), we obtain:
  D(h)− D(h′) ≤ LC2‖θ − θ′‖2. (10) In other words, if the parameters are close enough, then the losses should not differ too much. We denote ‖ · ‖2 as the Euclidean norm, and for later convenience we will omit the subscript in ‖ · ‖2.
sections.heading: 4 Algorithms for Evaluating and Improving Transferability
sections.text: The notion of transferability is defined w.r.t. domains, hence by learning feature embeddings that induce certain feature distributions, one can aim to improve transferability of two given domains. In this section we design algorithms to evaluate and improve transferability by learning such transformations. To start with, let g : X → Z be a feature embedding (a.k.a. featurizer), where Z is understood to be a feature space. By a joint distribution Dg (or Sg, T g) we mean a distribution on g(X )× Y . Formally, we are dealing with push-forwards of distributions:
  Sg := (g, id)#S, T g := (g, id)#T , (11) where (g, id) : (x, y) 7→ (g(x), y) is a function on X × Y . S and T here are joint distributions on X × Y , and here we specify X to be the space of the original signal such as an image. Since S and T cannot be changed, what we are evaluating here is the feature embedding g. The key quantity is transfer measures as in (8):
  TΓ(Sg‖T g) = sup h∈Γ T g (h)− ∗T g − ( Sg (h)− ∗Sg ), Γ = argmin( Sg , δSg ). (12)
  Although Γ is hard to compute, we can use (10) to obtain a lower bound of (12). That is, given a parametrization of the classifier h = q(θ, ·) and the optimal classifier h∗ = q(θ∗, ·), we have:
  TΓ(Sg‖T g) ≥ sup ‖θ−θ∗‖≤δ T g (h)− Sg (h)− ∗T g + ∗Sg
  ≥ sup ‖θ−θ∗‖≤δ T g (h)− Sg (h)− T g (ĥ∗)
  ≈ sup ‖θ−θ̂∗‖≤δ T g (h)− Sg (h)− T g (ĥ∗) (13)
  where δ > 0 depends on Γ and the constant in (10). In the second and the third lines, we approximated the optimal errors ∗T g and ∗ Sg with 0 ≤ ∗Sg ≤ Sg (ĥ∗), 0 ≤ ∗T g ≤ T g (ĥ∗), and we use the learned classifier ĥ∗ = q(θ̂∗, ·) as a surrogate for the optimal classifier. As a result, if the r.h.s. of (13) is large, then Sg is not quite transferable to T g .
  Algorithm 1: Algorithm for evaluating transferability among multiple domains
  Input: learned feature embedding g, learned classifier ĥ∗ = q(θ̂∗, ·), target sample training set T = S0, sample training sets S1, . . . , Sn, ascent optimizer, minimal errors ∗Si ≈ Si(ĥ∗), adversarial radius δ Initialize: a classifier h = q(θ, ·) and θ = θ̂∗, gap = −∞ for t in 1 . . . T do
  Find maxi Si(h ◦ g) and mini Si(h ◦ g) and corresponding indices j and k Run an ascent optimizer on h to maximize gap0 = Sj (h ◦ g)− Sk(h ◦ g) Project θ onto the Euclidean ball ‖θ − θ̂∗‖ ≤ δ if gap0 > gap then
  gap = gap0, save accuracies and losses of each domain
  Output: j, k, h, Sj (h ◦ g)− Sk(h ◦ g), Sj (ĥ∗), Sk(ĥ∗)
  We can thus design an algorithm to evaluate the transferability in Section 4.1. By computing the lower bound in (13), we can disprove the transferability as in Prop. 5 and Prop. 11. Computing the lower bound in (13) can be regarded as an attack method: there is an adversary trying to show that Sg is not transferable to T g . For this attack, we could also design a defence method aiming to minimize the lower bound and learn more transferable features.
sections.heading: 4.1 Algorithm for evaluating transferability
sections.text: In domain generalization we have one target domain and more than one source domains. To ease the presentation, we denote S0 = T (and thus Sg0 = T g) and extend the index set to be {0, 1, · · · , n}. We need to evaluate the transferability (13) between all pairs of Sgi and S g j . Algorithm 1 gives an efficient method to compute the worst-case gap sup‖θ−θ̂∗‖≤δ Sgi (h) − Sgj (h) among all pairs of (i, j). Essentially, it finds the worst pair of (i, j) at each step such that the gap Sgi (h)− Sgj (h) takes the largest value, and then maximize this gap over parameter θ through gradient ascent.
  Note that the computation of (13) also depends on the information from the target domain. This is valid since we are only evaluating but not training over these domains.
sections.heading: 4.2 Algorithm for improving transferability
sections.text: The evaluation sub-procedure provides us a way to pick a pair of non-transferable domains (Sgi ,S g j ), which in turn could be used to improve the transferability among all source domains by updating the feature embedding g such that the gap sup‖θ−θ∗‖≤δ Sgi (h) − Sgj (h) for (i, j) ∈ [n] × [n]. Simultaneously, we also require that the feature embedding g preserves information for the target task of interest. With the parametrization h = q(θ, ·), h′ = q(θ′, ·), the overall optimization problem can be formulated as:
  min g,h max ‖θ′−θ‖≤δ
  1
  n n∑ i=1 Si(h ◦ g) + ( maxi Si(h ′ ◦ g)−mini Si(h ′ ◦ g) ) . (14)
  Intuitively, we want to learn a common feature embedding and a classifier such that all source errors are small and the pairwise transferability between source domains is also small. If the optimization problem is properly solved, then we have the following guarantee:
  Theorem 12 (optimization guarantee). Assume that the function q(·, x) is Lθ Lipschitz continuous for any x. Suppose we have learned a feature embedding g and a classifier h such that the loss functional Sgi : H → R is L` Lipschitz continuous w.r.t. distribution S g i for i ∈ [n] and
  max ‖θ′−θ‖≤δ
  1
  n n∑ i=1 Si(h ◦ g) + ( maxi Si(h ′ ◦ g)−mini Si(h ′ ◦ g) ) ≤ η, (15)
  where θ, θ′ are parameters of h and h′. Then for any h′ ∈ Γ = {q(θ′, ·) : ‖θ − θ′‖ ≤ δ}, we have:
  TrΓ(T g 1 , T g 2 ) ≤ η, Si(h ′ ◦ g) ≤ η + L`Lθδ, T (h′ ◦ g) ≤ 2η + L`Lθδ, (16)
  for any T g1 , T g 2 , T g ∈ conv(S g 1 , . . . ,Sgn) and any i ∈ [n].
  The Lipschitzness assumption for Sgi is mild and can be satisfied for cross entropy loss (c.f. Appendix B.4.1). Here conv(·) denotes the convex hull in the same sense as Albuquerque et al. [2], i.e., each element is a mixture of source distributions. Thm 12 tells us that if we can solve the optimization problem (14) properly, we can guarantee transferability on a neighborhood of the classifier, as an approximation of the δ-minimal set. We thus propose Algorithm 2, which shares similarity with existing frameworks, such as DANN [16] and Distributional Robust Optimization [43, 45], in the sense that they all involve adversarial training and minimax optimization. However, the objective in our case is different and we provide a more detailed comparison with existing methods in Appendix B.5.
  Algorithm 2: Transfer algorithm for domain generalization Input: samples sets of source domains S1, . . . ,Sn, feature embedding g, classifier h = q(θ, ·), adversarial classifier h′ = q(θ′, ·), surrogate loss D, adversarial radius δ, ascent optimizer, descent optimizer, weight parameter λ, number of epochs T for t in 1 . . . T do Compute maxi Si(h ◦ g) and mini Si(h ◦ g) Initialization h′ = h (or θ′ = θ) for k in 1 . . . N do
  Run the ascent optimizer on h′ to maximize maxi Si(h ′ ◦ g)−mini Si(h′ ◦ g) fixing g
  Project θ′ onto the Euclidean ball ‖θ′ − θ‖ ≤ δ Fixing h′, run the descent optimizer on g, h to minimize error = 1n ∑ i Si(h ◦ g) + (maxi Si(h′ ◦ g)−mini Si(h′ ◦ g))
  Output: feature embedding g, classifier h
sections.heading: 5 Experiments
sections.text: Gulrajani and Lopez-Paz [20] did extensive experiments on comparing DG algorithms, using the same neural architecture and data split. Specifically, they show that with data augmentation, ERM perform relatively well among a large array of algorithms. Our experiments are based on their settings. We run Algorithm 1 on standard benchmarks, including RotatedMNIST [18], PACS [28], Office-Home [51] and WILDS-FMoW [23] (c.f. Appendix C.1). Specifically, WILDS-FMoW is a large dataset with nearly half a million images. Detailed experimental settings can be seen at Appendix C.
  Evaluating transferability From Figure 3 it can be seen that at a neighborhood of the learned classifier, there exists a classifier such that the target accuracy is degraded significantly, whereas some source domain still has high accuracy. This poses questions to whether current popular algorithms such as ERM [50], DANN [17] and Mixup [53, 54] are really learning invariant and transferable features. If so, the target accuracy should be high given a high source accuracy. However, for the PACS dataset and Mixup model (the second column of Figure 3), the target accuracy decreases by more than 30% while the source accuracy remains roughly at the same level. We can also, e.g., read from the first column that with a small decrease of the source (test) accuracy by ∼ 2% (at δ = 2), the target accuracy of DANN drops by ∼ 10%.
  From Figure 3 we can also see that Correlation Alignment [CORAL, 47] and Spectral Decomposition [SD, 40] have better transferability that other algorithms. In some sense, they are in fact learning robust classifiers, i.e., all the classifiers on the neighborhood of the learned classifier can achieve good accuracies. With this robust classifier, the target accuracy does not decrease much even if the classifier is perturbed.
  Improving transferability Algorithm 2 has good performance among all four datasets that we tried, comparable to CORAL and SD. Note that CORAL and SD do not always perform well, such as in the Office-Home and WILDS-FMoW datasets, but our Transfer algorithm does. However, in our experiments we find there are two limitations of Algorithm 2: (1) we need a large number of inner maximization steps to compute the gap, which needs more training time. This is similar to adversarial robustness [33] which is slower than usual training. In order to overcome this difficulty we used pretraining from other algorithms in the experiments on Office-Home and WILDS-FMoW; (2) Moderate hyper-parameter tuning is needed. For example, we need to tune N is Algorithm 2, the learning rate (lr) of SGA and the choice of δ. We find that taking N = 20 or 30 is usually a good choice, and δ can be quite large such that the projection step is not taken. We take lr = 0.01 for RotatedMNIST and lr = 0.001 for other datasets.
  Label shift In order to show the difference with the well-knownH-divergence [8], we compute the label shifts in the PACS dataset. As shown in Zhao et al. [59], the optimal joint error S(h∗) + S(h∗) (h∗ is the optimal classifier that minimizes S(h) + T (h)) can be large under the shift of label distributions. We follow [59] and compute the label shift between pairs of domains in the PACS dataset, measured by total variation. From Table 1 we can see that the label shift is large in this case, and thus theH-divergence bound [8] can be quite loose. Comparably, our transfer measure bound Prop. 3 is tighter (c.f. Prop. 27) and therefore still useful in practice.
sections.heading: A 0.0 0.12 0.11 0.3
sections.heading: 6 Related Work
sections.text: Multi-task learning Multi-task learning (MTL) [56] is related to but different from DG. In MTL, there are several tasks, and one hopes to improve the performance of each task by jointly training all the tasks simultaneously, utilizing the relationships between them. This is different from DG in the sense that in DG the target domain is unknown a priori, whereas in MTL the focus is more on better generalization on existing tasks that appear in training. Hence, there is no distribution shift in MTL per se. Furthermore, for MTL, the output spaces of different tasks are not necessarily the same.
  Zero-shot learning / Few-shot learning / Meta-learning DG is different from zero-shot learning [27]. In zero-shot learning, one has labeled training data and the goal is to make predictions on a new unseen label set. However, in DG the label set remains the same for the source and the target domains. On the other hand, the focus of few-shot learning is on fast adaptation, in the sense that the test distribution remains the same as the training distribution, but the learner can only have access to a few labeled samples. Domain generalization also shares similarity with meta-learning. However, in meta-learning, the learner is allowed to fine-tune over the target domain. In other words, the protocol of meta-learning allows access to a small amount of labeled data from future unseen domains. Meta-learning is more or less one specific method that is used to tackle few-shot learning. Because of the similarity, some meta-learning algorithms can be applied to DG [29].
  Self-supervised learning Self-supervised learning (SSL) is a popular unsupervised feature learning approach [13, 19, 21]. The goal of SSL is to learn invariant representations w.r.t. different views of the same image. Although it is a promising feature learning method, it differs from our DG settings in the sense that no labels are used in SSL.
  Domain generalization There have been a lot of old and new algorithms proposed for domain generalization. The simplest one is Empirical Risk Minimization (ERM), where we simply minimize the empirical risk of (the sum of) all source domains. In Blanchard et al. [10], Muandet et al. [35], kernel methods for DG were proposed. Arjovsky et al. [3] proposed Invariant Risk Minimization (IRM) which aims to learn invariant predictors across source domains, and follow-up discussions can be found in [25, 41]. Another approach is called distributional robustness [43, 52], where the model is optimized over a worst-case distribution under the constraint that this distribution is generated from a small perturbation around the source distributions. In Albuquerque et al. [2], a DG scheme based on distribution matching was proposed. Moreover, many domain adaptation algorithms can be directly adapted to the task of domain generalization, such as CORAL [47] and DANN [16]. Last but not least, we mention a concurrent work [55] on the theory of domain generalization, which focuses more on proposing a model selection rule based on accuracy and variation.
  Adversarial robustness Our evaluation and training methods in §4 are reminiscent of the adversarial training method [33] in the literature of adversarial robustness. Perturbing the classifier in our case corresponds to perturbing the input data in adversarial robustness. From this perspective, our Transfer algorithm is parallel to the adversarial training method. It would be interesting to design certified robust feature embeddings, by analogy with certified robust classifiers [15].
sections.heading: 7 Conclusions
sections.text: In this paper we formally define the notion of transferability that we can quantify, estimate and compute. Our transfer measures can be understood as a special class of IPMs. They are weaker than total variation and even very dissimilar distributions could be transferable to each other. Our definition of transferability can also be naturally used to derive a generalization bound for prediction error on the target domain. Based on our theory, we propose algorithms to evaluate and improve the transferability by learning feature representations. Experiments show that, somewhat surprisingly, many existing algorithms are not quite learning transferable features. From this perspective, our transfer measures offer a novel way to evaluate the features learned from different DG algorithms. We hope that our proposal of transferability could draw the community’s attention to further investigate and better understand the fundamental quantity that allows robust models under distribution shifts.
  Broader Impact Reliable domain generalization models are important for practice use. Our work points out the reliability issue of DG algorithms. It is worth mentioning that our evaluation method can only disprove the transferability and survival of our attack method should not be treated as a warranty. Misunderstanding of it could lead to potential harm in practical applications.
  Acknowledgements and Funding Transparency Statement
  We thank the anonymous reviewers for their constructive comments as well as the area chair and the senior area chair for overseeing the review process. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. We thank NSERC and the Canada CIFAR AI Chairs program for funding support. GZ is also supported by David R. Cheriton scholarship and research grant from Vector Institute. HZ is supported by a startup funding from the Department of Computer Science at UIUC. Finally, we thank Vector Institute for providing the GPU cluster.
title: Quantifying and Improving Transferability in Domain Generalization