summaries: This paper discusses a very interesting question: what is the relationship between adversarial robustness and cross-domain transferability. The previous studies show that a more robust model can transfer better. This paper argues that the true reason for the cross-domain transferability is not the adversarial robustness, but the effect of regularization, which can also be achieved through other methods, such as data augmentation. This paper aims to convey the message that adversarially robust models may not have better transferability in terms of transfer learning in vision tasks. However, this message is unclear due to the mixture of data augmentation, regularization, robustness in the presentation. Some definitions are confusing and the conclusion seems to contradict with existing literature, e.g,  Salman et al arxiv: 2007.08489.  --post rebuttal--  Thanks to the authors for the draft revision and the additional appendix C. Now the paper is clearer to me: the general idea is to say that robustness is a type of regularization, and this regularization is the key to generalization. However, I think the former is not novel as already mentioned in Roth et al NeurIPS 2020. Besides, there are still many presentation issues even after the revision, e.g.: 1) Prop 3.1 mentioned the relative domain transferability, but the formal definition is introduced later in Def 1. 2) The added paragraph is confusing to me. How would you define the input space ${\cal X}$? Is it a compact set? Why would the perturbation go outside ${\cal X}$? Shouldn't $x + \delta$ still be in the domain of $f_c^{{\cal D}_{\cal S}}$ as otherwise it is not well-defined? 3) Def 2 should be compared with existing metrics.  4) In Section 3.4 the authors use the squared loss but in experiments they use cross entropy loss.  Despite the interesting topic, I would keep my current score until a more well-written version is presented.   This paper studies theoretically how adversarially trained models can transfer better, and disentangle the robustness and accuracy on the target domain. They claim that the main reason is more of regularisation rather than robustness. Corresponding examples and theory are presented. This paper aims to investigate the theoretical connection between domain generalization (aka Transferability) and adversarial robustness in some general settings. Authors claim that a thorough theoretical treatment of this problem has not been given yet, and therefore set out to establish a number of fundamental relations.  A simple example has been proposed which shows the existence of cases, where adversarial robustness and transferability can be independent (or even negatively correlated). Also, paper proves that adding more restriction (tighter regularization) on the feature extractor stage of a learning algorithm gives better domain generalization. Additionally, some intrinsic and fundamental measures have been defined to bound the domain generalization error for transferring a learned model from domain S to domain T. In this regard, uniform convergence bounds have been derived to show the gap between empirical and statistical versions of such measures remain small or even converge to zero when sample size asymptotically increases.  Finally, a number of experimental results have been shown to support the above theoretical achievements. I have not gone through the experimental parts nor the proofs, yet.
abstractText: Machine learning (ML) robustness and generalization are fundamentally correlated: they essentially concern about data distribution shift under adversarial and natural settings, respectively. Thus, it is critical to uncover their underlying connections to tackle one based on the other. On one hand, recent studies show that more robust (adversarially trained) models are more generalizable to other domains. On the other hand, there lacks of theoretical understanding of such phenomenon, and it is not clear whether there are counterexamples. In this paper, we aim to provide sufficient conditions for this phenomenon considering different factors that could affect both, such as norm of the last layer, Jacobian norm, and data augmentations (DA). In particular, we propose a general theoretical framework indicating factors that can be reformed as a function class regularization process, which could lead to improvements of domain generalization. Our analysis, for the first time, shows that “robustness” is actually not the causation for domain generalization; rather, robustness induced by adversarial training is a by-product of such function class regularization. We then discuss in details about different properties of DA and we prove that under certain conditions, DA can be viewed as regularization and therefore improve generalization. We conduct extensive experiments to verify our theoretical findings and show several counterexamples where robustness and generalization are negatively correlated when the sufficient conditions are not satisfied.
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: Shai Ben-David John Blitzer Koby Crammer Fernando Pereira
references.title: Analysis of representations for domain adaptation
references.venue: Advances in neural information processing systems,
references.authors: Nicholas Carlini David Wagner
references.title: Towards evaluating the robustness of neural networks
references.venue: In 2017 ieee symposium on security and privacy (sp),
references.authors: Jianbo Chen Michael I Jordan Martin J Wainwright
references.title: Hopskipjumpattack: A query-efficient decision-based attack
references.venue: In 2020 ieee symposium on security and privacy (sp),
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: Nicolas Courty Rémi Flamary Devis Tuia Alain Rakotomamonjy
references.title: Optimal transport for domain adaptation
references.venue: IEEE transactions on pattern analysis and machine intelligence,
references.authors: Terrance DeVries Graham W Taylor
references.title: Dataset augmentation in feature space
references.venue: arXiv preprint arXiv:1702.05538,
references.authors: Logan Engstrom Andrew Ilyas Shibani Santurkar Dimitris Tsipras Brandon Tran Aleksander Madry
references.title: Adversarial robustness as a prior for learned representations
references.authors: Ian J Goodfellow Jonathon Shlens Christian Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: arXiv preprint arXiv:1412.6572,
references.authors: Alex Hernández-Garcı́a Peter König
references.title: Data augmentation instead of explicit regularization
references.venue: arXiv preprint arXiv:1806.03852,
references.authors: Alex Hernández-Garcı́a Peter König
references.title: Further advantages of data augmentation on convolutional neural networks
references.venue: In International Conference on Artificial Neural Networks,
references.authors: Judy Hoffman Daniel A Roberts Sho Yaida
references.title: Robust learning with jacobian regularization
references.venue: arXiv preprint arXiv:1908.02729,
references.authors: Haoshuo Huang Qixing Huang Philipp Krahenbuhl
references.title: Domain transfer through deep activation matching
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV),
references.authors: Lei Huang Li Liu Fan Zhu Diwen Wan Zehuan Yuan Bo Li Ling Shao
references.title: Controllable orthogonalization in training dnns
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Andrew Ilyas Shibani Santurkar Logan Engstrom Brandon Tran Aleksander Madry
references.title: Adversarial examples are not bugs, they are features
references.venue: Advances in neural information processing systems,
references.authors: Vladimir Koltchinskii
references.title: Rademacher penalties and structural risk minimization
references.venue: IEEE Transactions on Information Theory,
references.authors: Clare Lyle Marta Kwiatkowksa Yarin Gal
references.title: An analysis of the effect of invariance on generalization in neural networks
references.venue: In International conference on machine learning Workshop on Understanding and Improving Generalization in Deep 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: Takeru Miyato Shin-ichi Maeda Masanori Koyama Shin Ishii
references.title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning
references.venue: IEEE transactions on pattern analysis and machine intelligence,
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: Luis Perez Jason Wang
references.title: The effectiveness of data augmentation in image classification using deep learning
references.venue: arXiv preprint arXiv:1712.04621,
references.authors: Elan Rosenfeld Pradeep Ravikumar Andrej Risteski
references.title: An online learning approach to interpolation and extrapolation in domain generalization
references.venue: arXiv preprint arXiv:2102.13128,
references.authors: Kevin Roth Yannic Kilcher Thomas Hofmann
references.title: Adversarial training is a form of data-dependent operator norm regularization
references.venue: arXiv preprint arXiv:1906.01527,
references.authors: Hadi Salman Andrew Ilyas Logan Engstrom Ashish Kapoor Aleksander Madry
references.title: Do adversarially robust imagenet models transfer better
references.venue: arXiv preprint arXiv:2007.08489,
references.authors: Chun-Chen Tu Paishun Ting Pin-Yu Chen Sijia Liu Huan Zhang Jinfeng Yi Cho-Jui Hsieh Shin-Ming Cheng
references.title: Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Sebastien C Wong Adam Gatt Victor Stamatescu Mark D McDonnell
references.title: Understanding data augmentation for classification: when to warp? In 2016 international conference on digital image computing: techniques and applications (DICTA)
references.authors: Kaichao You Ximei Wang Mingsheng Long Michael Jordan
references.title: Towards accurate model selection in deep unsupervised domain adaptation
references.venue: In International Conference on Machine Learning,
references.authors: Hongyang Zhang Yaodong Yu Jiantao Jiao Eric Xing Laurent El Ghaoui Michael Jordan
references.title: Theoretically principled trade-off between robustness and accuracy
references.venue: In International Conference on Machine Learning,
references.authors: Linjun Zhang Zhun Deng Kenji Kawaguchi Amirata Ghorbani James Zou
references.title: How does mixup help with robustness and generalization
references.venue: arXiv preprint arXiv:2010.04819,
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 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,
references.authors: DT
references.title: General Settings. For the following discussion we apply a general DA setting of affine transformation (Perez & Wang, 2017), taking the form of x? = W>
sections.heading: 1 INTRODUCTION
sections.text: Domain generalization (or transferability) is the task of training machine learning models with data from one or more source domains that can be adapted to a target domain, often via lowcost fine-tuning. Thus, domain generalization refers to approaches designed to address the natural data distribution shift problem (Muandet et al., 2013; Rosenfeld et al., 2021). A wide array of approaches have been proposed to address domain transferability, including fine-tuning the last layer of DNNs (Huang et al., 2018), invariant feature optimization (Muandet et al., 2013), efficient model selection for fine-tuning (You et al., 2019), and optimal transport based domain adaptation (Courty et al., 2016). Improving domain generalization has emerged as an important task in the machine learning community: for instance, it is among the key technologies to enable an autonomous driving vehicle trained in city scenarios to make correct decisions in the countryside as well.
  On the other hand, robust machine learning aims to tackle the problem of adversarial data distribution shift. Both empirical and certified robust learning approaches have been proposed, such as empirical adversarial training (Madry et al., 2018) and certified defenses based on deterministic and probabilistic approaches (Cohen et al., 2019).
  As domain transferability and robust machine learning tackle different kinds of data distribution shifts, this work seeks to uncover their underlying connections and tradeoffs. For instance, recent studies suggest that adversarially robust models are more domain transferable (Salman et al., 2020), which, in turn, provides new insights on improving domain generalization. However, a theoretical analysis of their relationship is still lacking, and it is unclear whether such positive correlations al-
  ways hold. In this paper, we take the first steps towards formally analyzing the relationship between model robustness and domain transferability to answer the following questions: What are sufficient conditions for domain transferability? Is model robustness the cause of domain transferability? Can robustness and domain transferability be negatively correlated?
  To answer the above questions and uncover the underlying relationship between robustness and domain transferability, we propose a general theoretical framework that characterizes sufficient conditions for domain transferability from the view of function class regularization. Our analysis shows that if the function class of feature extractors is more regularized, the model based on a feature extractor trained from the function class, composed with a fine-tuned last layer, can be more transferable. Formally, we prove that there is a monotone relation between the regularization strength and a tight upper bound on the relative domain transfer loss.
  Under the proposed framework, we analyze several common factors for model training, including the Jacobian norm, the last layer norm, data augmentation, and adversarial training as shown in Fig. 1. In particular, controlling the Jacobian norm and last layer norm can be viewed as functionclass regularization, thus can be analyzed in our framework. We also analyze how other common regularization operations can be mapped to function class regularization. For instance, we consider noise-dependent and independent data augmentation procedures based on feature average and loss average aggregation algorithms.
  We conduct extensive experiments on ImageNet (CIFAR-10 as target domain) and CIFAR-10 (SVHN as target domain) based on different models to verify our analysis. We show that regularization can control domain transferability, and robustness and domain transferability can be negatively correlated, which are counter-examples against Salman et al. (2020). Taken together, this indicates that robustness is not a cause of transferability.
  Technical Contributions. We aim to uncover the underlying relationship between robustness and domain transferability and lay out the sufficient conditions for transferability from the view of regularization. We make both theoretical and empirical contributions.
  • We propose a theoretical framework to analyze the sufficient conditions for domain transferability from the view of function class regularization. We provably show that stronger regularization on the feature extractor implies a decreased tight upper bound on the relative transferability loss; while model robustness could be arbitrary.
  • We prove the tightness of our transferability upper bound, and provide the generalization bound of the relative transferability loss from the view of regularization.
  • We analyze several factors such as different data augmentations (e.g., rotation and Gaussian) under the framework, and show how they can be mapped to function class regularization and therefore affect transferability.
  • We conduct extensive experiments on different datasets and model architectures to verify our theoretical claims. We also show several counterexamples that indicate significant negative correlation between robustness and the relative domain transferability.
sections.heading: 2 RELATED WORK
sections.text: Domain Transferability has been analyzed in different settings. Muandet et al. present a generalization bound for classification task based on the properties of the assumed prior over training environments. Rosenfeld et al. model domain transferability/generalization as an online game and show that generalizing beyond the convex hull of training environments is NP-hard, and Zhang et al. provides a generalization bound for distributions with sufficiently small H-divergence. Given the
  complexity of domain transferability analysis, recent empirical studies show that adversarially robust models transfer better (Salman et al., 2020). In this paper, we aim to relax the assumptions and focus on understanding the domain transferability from the view of regularization and theoretically show whether “robustness” is indeed a causation for transferability or not.
  Model Robustness is an important topic given recent diverse adversarial attacks (Goodfellow et al., 2014; Carlini & Wagner, 2017). These attacks may be launched without access to model parameters (Tu et al., 2019) or even with the model predicted label alone (Chen et al., 2020). Different approaches have been proposed to improve model robustness against adversarial attack. Adversarial training has been shown to be effective empirically (Madry et al., 2018; Zhang et al., 2019a; Miyato et al., 2018). Some studies have shown that robustness is property related to other model characteristics, such as transferability and invertibility (Engstrom et al., 2019).
sections.heading: 3 SUFFICIENT CONDITIONS FOR DOMAIN TRANSFERABILITY
sections.text: In this section, we theoretically analyze the problem of domain transferability from the view of regularization and discuss some sufficient conditions for good transferability. All of the proofs are provided in Section A in the appendix.
  Notations. We denote the input space as X ; the feature space as Z and the output space as Y . Let the fine-tuning function class be g ∈ G. Given a feature extractor f : X → Z and a fine-tuning function g : Z → Y , the full model is g ◦ f : X → Y . We denote PX×Y as the set of distributions on X × Y . The loss function is denoted by ` : Y × Y → R+, and the population loss based on data distribution D ∈ PX×Y and a model g ◦ f is defined as
  `D(g ◦ f) := E(x,y)∼D[`(g ◦ f(x), y)].
  Before diving into the details, we first provide the following example to illustrate why one might investigate domain transferability from the view of regularization.
sections.heading: 3.1 EXAMPLE: ROBUSTNESS AND TRANSFERABILITY ARE INDEPENDENT
sections.text: In this subsection, we construct a simple example where domain transferability depends on regularization, yet domain transferability and robustness are independent. Moreover, this example serves as motivation to consider domain transferability from the view of regularization.
  Given the source and target distributions DS ,DT ∈ PX×Y , we denote their marginal distributions on the input space X as DXS and DXT , respectively. We consider the case that X ⊂ Rm being a low-dimensional manifold in Rm, and Y = Rd. Given an input x ∈ X , the ground truth target for the source domain is yS(x) generated by a function yS : Rm → Rd. Similarly, we define yT for the target domain. In this example, for simplicity, we neglect the fine-tuning process but directly consider learning a function f : Rm → Rd with a norm ‖ · ‖ on Rd. For the source domain we have the population loss:
  `DS (f) = Ex∼DXS [‖f(x)− yS(x)‖].
  A distribution D ∈ PX on the input space X , defines a norm of a function f : Rm → Rd as
  ‖f‖D := Ex∼D[‖f(x)‖],
  where we view two functions f1, f2 as the same if ‖f1 − f2‖D = 0. Therefore, we can define the source domain loss `DS (f) = ‖f − yS‖DXS and the target domain loss `DT (f) = ‖f − yT ‖DXT .
  For the sake of illustration, we consider the simple case where the input distributions DXS ,DXT are the same, and hence we denote D = DXS = DXT . Note that yS and yT are different.
  Denoting a function space F = {f : Rm → Rd | ‖f‖D <∞}, we assume that yS , yT ∈ F and we can compare f, yS , yT in the same space. Therefore, given c > 0 as a regularization parameter, the domain transferability problem can be defined as:
  Learning a source model: fDSc ∈ arg min f∈F `DS (f), s.t. ‖f‖D ≤ c; (1)
  Testing on a target domain: `DT (f DS c ),
  where the minimizer fDSc := yS min{1, c‖yS‖D }, the source domain loss is `DS (f) = ‖f − yS‖D, and the target domain loss is `DT (f) = ‖f − yT ‖D. We prove in Proposition 3.1 that fDSc is indeed a minimizer of (1) and provide an intuitive illustration in Figure 2.
  We show that the robustness can be independent to domain transferability as follows. Consider the adversarial robustness of fDSc on an input x ∈ X (e.g., maxδ:‖δ‖2≤ `(fDSc (x + δ), yS(x))). Since the transferred loss `DT (f DS c ) only evaluates f DS c on X which is a low-dimensional manifold in Rm, an adversarial perturbation δ ∈ Rm could make x + δ ∈ Rm\X when the loss function is sufficiently big outside the manifold X . Therefore, the robustness could be arbitrarily bad without changing the value of `DT (f DS c ), i.e., the performance of the source model on the target domain.
  As we can see, the robustness is independent to domain transferability in this example. On the contrary, if we change the perspective to consider the the regularization parameter c, we have the following interesting finding. An illustration of the finding is shown in Figure 2, and a more formal statement is provided in Proposition 3.1.
  Proposition 3.1. Given the problem defined above, fDSc is a minimizer of equation 1. If c ≥ c′ ≥ 0, then the relative domain transferability loss `DT (f DS c )− `DS (fDSc ) ≥ `DT (f DS c′ )− `DS (f DS c′ ).
  We can see that robustness is not sufficient to characterize domain transferability. However, there is a monotone relation between the regularization strength and the relative transferability loss, where adversarial robustness could be arbitrary. Similar behavior is also observed in our experiments, as we will discuss in Section 4. Naturally, these findings motivate the study of the connections between the regularization of the training process and domain transferability in general, as we consider next.
sections.heading: 3.2 UPPER BOUND OF THE RELATIVE DOMAIN TRANSFERABILITY
sections.text: In this subsection, we consider the general transferability problem with fine-tuning. We prove that there is a monotone relationship between the regularization strength and relative domain transferability loss. We also present a tight upper bound on the relative domain transferability loss. Denote the training algorithm as A that takes a data distribution D and outputs a feature extractor fDA ∈ FA chosen from a function class FA and a fine-tuning function gDA ∈ G. Next we formally define relative domain transferability. Definition 1 (Relative Domain Transferability Loss). Given the training algorithm A and a pair of distributions DS ,DT ∈ PX×Y , the relative domain transferability loss between DS ,DT is defined to be the difference of fine-tuned losses, i.e.,
  τ(A;DS ,DT ) := inf g∈G `DT (g ◦ f DS A )− `DS (g DS A ◦ f DS A ).
  Note that the training algorithm A is not required to be optimal, i.e., it could be the case that `DS (g DS A ◦ f DS A ) > infg∈G,f∈FA `DS (g ◦ f). As we can see, the smaller τ(A;DS ,DT ) is, the better the model’s relative performance becomes on the target domain.
  Another perspective of Definition 1 is that infg∈G `DT (g◦f DS A ) = `DS (g DS A ◦f DS A )+τ(A;DS ,DT ). From this perspective, the transferred loss is the source loss plus an additional term to be upper bounded by a certain distance metric between the source and target distributions – as is common in the literature of domain adaptation (e.g., Ben-David et al. (2007); Zhao et al. (2019)). The key question of the “distance metric” remains unanswered. To this end, we propose the following.
  Definition 2 ((G,F)-pseudometric). Given a fine-tuning function class G, a feature extractor function class F and distributions DS ,DT ∈ PX×Y , the (G,F)-pseudometric between DS ,DT is
  dG,F (DS ,DT ) := sup f∈F | inf g∈G `DS (g ◦ f)− inf g∈G `DT (g ◦ f)|.
  Since the fine-tuning function class is usually simple and fixed, we will use dF as an abbreviation in the context where G is clear.
  It can be easily verified that dG,F is a pseudometric that measures the distance between two distributions, as shown in the following proposition. Proposition 3.2. dG,F (·, ·) : PX×Y × PX×Y → R+ satisfies the following properties; (Symmetry) dG,F (DS ,DT ) = dG,F (DT ,DS); (Triangle Inequality) ∀D′ ∈ PX×Y : dG,F (DS ,DT ) ≤ dG,F (DS ,D′) + dG,F (D′,DT ); (Weak Zero Property) ∀D ∈ PX×Y : dG,F (D,D) = 0.
  In this section, we consider a fixed fine-tuning function class G and feature extractor function class FA given by the training algorithm A. Thus, we denote dG,F as dFA for the remainder of the paper. With the definition of dFA , we can derive the following result. Theorem 3.1. Given a training algorithm A, for ∀DS ,DT ∈ PX×Y we have
  τ(A;DS ,DT ) ≤ dFA(DS ,DT ), or equivalently, inf
  g∈G `DT (g ◦ f DS A ) ≤ `DS (g DS A ◦ f DS A ) + dFA(DS ,DT ).
  Interpretation: As we can see, the above theorem provides sufficient conditions for good domain transferability. There is a monotone relation between the regularization strength and dFA(DS ,DT ), i.e., the upper bound on the relative domain transferability loss τ(A;DS ,DT ). More explicitly, if a training algorithm A′ has FA′ ⊆ FA, then dFA′ (DS ,DT ) ≤ dFA(DS ,DT ). Moreover, small dFA(DS ,DT ) implies good relative domain transferability. From this perspective, we can see that we need both small dFA(DS ,DT ) and small source loss `DS (g DS A ◦ f DS A ) to guarantee good absolute domain transferability. Note that there is a possible trade-off, i.e., with FA being smaller, dFA(DS ,DT ) decreases but possibly `DS (g DS A ◦ f DS A ) increases due to the limited power of FA. On the other hand, there may not be such trade-off if DS and DT are close enough such that dFA(DS ,DT ) is small. To make the upper bound more meaningful, we need to study the tightness of it. Theorem 3.2. Given any source distribution DS ∈ PX×Rd , any fine-tuning function class G where G includes the zero function, and any training algorithm A, denote
  := `DS (g DS A ◦ f DS A )− inf g∈G,f∈FA `DS (g ◦ f).
  We assume some properties of the loss function ` : Rd × Rd → R+: it is differentiable and strictly convex w.r.t. its first argument; `(y, y) = 0 for any y ∈ Rd; and limr→∞ infy:‖y‖2=r `(~0, y) = ∞, where ~0 is the zero vector. Then, for any distribution DX on X , there exist some distributions DT ∈ PX×Rd with its marginal on X being DX such that
  τ(A;DS ,DT ) ≤ dFA(DS ,DT ) ≤ τ(A;DS ,DT ) + , or equivalently dFA(DS ,DT )− ≤ τ(A;DS ,DT ) ≤ dFA(DS ,DT ).
  Interpretation: In the above theorem, we show that given any A,DS , and the marginal DX , there exists some conditional distributions of y|x such that by composing it with the given DX we have a distribution DT to make the bound in Theorem 3.1 -tight. Note that is the difference between the source loss and the its infimum, i.e., with a good enough algorithm A, the could be arbitrarily small.
sections.heading: 3.3 GENERALIZATION UPPER BOUND OF THE RELATIVE DOMAIN TRANSFERABILITY
sections.text: Here we investigate the proposed theory on relative transferability with finite samples. For a distribution D ∈ PX×Y , we denote its empirical distribution with n samples as D̂n. That being said,
  `D̂n(g ◦ f) = E(x,y)∼D̂n [`(g ◦ f(x), y)] = 1
  n n∑ i=1 `(g ◦ f(xi), yi),
  where (xi, yi) are i.i.d. samples from D. Therefore, given two distributions DS ,DT ∈ PX×Y , the empirical (G,F)-pseudometric between them is dG,F (D̂nS , D̂nT ). Note that dG,F is not only a pseudometric of distributions, but also a complexity measure, and we will first connect it with the Rademacher complexity. Definition 3 (Empirical Rademacher Complexity (Bartlett & Mendelson, 2002; Koltchinskii, 2001)). Denote the loss function class induced by G,F as
  LG,F := {hg,f : X × Y → R+ | g ∈ G, f ∈ F}, where hg,f (x, y) := `(g ◦ f(x), y).
  Given an empirical distribution D̂n (i.e., n data samples), the Rademacher complexity of it is
  RadD̂n(LG,F ) := 1
  n Eξ
  [ sup
  h∈LG,F n∑ i=1 ξih(xi, yi)
  ] ,
  where ξ ∈ Rn are Rademacher variables, i.e., each ξi is i.i.d. uniformly distributed on {−1, 1}.
  We can see that if there is a F ′ ⊆ F , then RadD̂n(LG,F ′) ≤ RadD̂n(LG,F ). With the above definitions, we have the following lemma connecting the (G,F)-pseudometric to Rademacher complexity. Lemma 3.1. Assuming the individual loss function ` : Y × Y → [0, c], given any distribution D ∈ PX×Y and ∀δ > 0, with probability ≥ 1− δ we have
  dG,F (D, D̂n) ≤ 2RadD̂n(LG,F ) + 3c √ ln(4/δ)
  2n .
  Therefore, denoting again dFA as dG,FA , the empirical version of Theorem 3.1 is as follows. Theorem 3.3. Assuming the individual loss function ` : Y × Y → [0, c], given ∀DS ,DT ∈ PX×Y , for ∀δ > 0 with probability ≥ 1− δ we have
  τ(A; D̂nS ,DT ) ≤ dFA(D̂nS , D̂nT ) + 2RadD̂nT (LG,FA) + 4RadD̂nS (LG,FA) + 9c √ ln(8/δ) 2n .
  We can see that a smaller feature extractor function class FA implies both a smaller dFA and the Rademacher complexity. Therefore, the monotone relation between the regularization strength and the upper bound on the relative domain transferability loss also holds for the empirical settings.
  Other than direct regularization, empirically we find that the transferability is also related to the use of data augmentation. Can we explain such phenomena from the view of regularization again? We discuss this question next.
sections.heading: 3.4 WHEN CAN DATA AUGMENTATION BE VIEWED AS REGULARIZATION?
sections.text: In this subsection, we discuss the connections between data augmentation (DA) and regularization. We present the results and their interpretation in this subsection, while deferring the detailed discussion to the Section B in the appendix.
  Empirical research has shown evidence of the regularization effect of DA (Hernández-Garcı́a & König, 2018a;b). However, there is a lack of theoretical understanding on when can data augmentation be viewed as regularization in general. In an attempt to address this question, we consider a general DA setting of affine transformation (Perez & Wang, 2017) with parameters (W?, b?) whose distribution represents specific DA.
  General Settings. We consider the fine-tuning function g : Rd → R as a linear layer, which will be concatenated to the feature extractor f : Rm → Rd. Given a model g ◦ f , we use the squared loss `(g ◦ f(x), y) = (g ◦ f(x)− y)2, and accordingly apply second-order Taylor expansion to the objective function to study the effect of data augmentation.
  DA categories. We discuss two categories of DA, feature-level DA and data-level DA. Feature-level DA (Wong et al., 2016; DeVries & Taylor, 2017) requires the transformation to be performed in the learned feature space: given a data sample x ∈ Rm and a feature extractor f , the augmented feature is W?f(x) + b? where W? ∈ Rd×d, b? ∈ Rd are sampled from a distribution. On the other hand,
  data-level DA requires the transformation to be performed in the input space: given a data sample x, the augmented sample is W?x+ b? where W? ∈ Rm×m, b? ∈ Rm are sampled from a distribution. Intuition on sufficient conditions. For either the feature-level or the data-level DA, the intuitions given by our analysis are similar. Our results (Theorem B.1&B.2) suggest that the following conditions indicate the regularization effects of a data augmentation: 1) EW? [W?] = I; 2) Eb? [b?] = ~0; 3) W? and b? are independent, where I is the identity matrix and ~0 is the zero vector; 4) W? is not a constant if it is the feature-level DA; 5) DA is of a small magnitude if it is the data-level DA.
  Empirical verification. Combining with Theorem 3.3, it suggests that DA satisfying the conditions above may improve the relative domain transferability. In fact, it matches the empirical observations in Section 4. Concretely, 1) Gaussian noise satisfies the four conditions, and empirically the Gaussian noise improves domain transferability while robustness decreases a bit (Figure 5); 2) Rotation, which rotates input image with a predefined fixed angle with predefined fixed probability, violates EW? [W?] = I, and empirically the rotation barely affects domain transferability (Figure 14 in Appendix D.3); 3) Translation, which moves the input image for a predefined distance along a pre-selected axis with fixed probability, violates Eb? [b?] = ~0, and empirically the translation distance barely co-relates to the domain transferability (Figure 14 in Appendix D.3).
sections.heading: 4 EVALUATION
sections.heading: 4.1 EXPERIMENTAL SETTING
sections.text: Source model training We train our model on two source domains: CIFAR-10 and ImageNet. Unless specified, we will use the training setting as follows1. For CIFAR-10, we train the model with 200 epochs using the momentum SGD optimizer with momentum 0.9, weight decay 0.0005, an initial learning rate 0.1 which decays by a factor of 10 at the 100-th and 150-th epoch. For ImageNet, we train the model with 90 epochs using the momentum SGD optimizer with momentum 0.9, weight decay 0.0001, an initial learning rate 0.1 which decays by a factor of 10 at the 30-th and 60-th epoch. We use the standard cross entropy loss denote as LCE(hs, x, y), where hs = gs ◦ f is the trained model and x, y are the input and label respectively. To evaluate the robustness on the source domain, we follow the evaluation setting in Ilyas et al. (2019) and perform the PGD attack with 20 steps using = 0.25. We also evaluate the robustness using AutoAttack in Appendix D.4. For both tasks we use ResNet-18 as the model structure. We provide results of other model structures in appendix D.2.
  Domain Transferability We evaluate the transferability from CIFAR-10 to SVHN and from ImageNet to CIFAR-10. For the ImageNet transferability, we focus on CIFAR as the target domain, since it is the domain that is the most positively correlated with robustness as shown in Salman et al. (2020). We evaluate the fixed-feature transfer where only the last fully-connected layer is fine-tuned following our theoretical framework. We fine-tune the last layer with 40 epochs using momentum SGD optimizer with momentum 0.9, weight decay 0.0005, an initial learning rate 0.01 which decays by a factor of 10 at the 20-th and 30-th epoch. To mitigate the impact of benign accuracy, we evaluate the relative domain transfer accuracy (DT Acc) as follows. Let accsrc and acctgt be the accuracy of the a fine-tuned model on source and target domain, and accvsrc and acc v tgt be the accuracy of vanilla model (i.e., models trained with standard setting) on source and target domain, then the relative DT accuracy is defined as:
  DT Acc = (acctgt − accsrc)− (accvtgt − accvsrc) We also provide the results of absolute DT accuracy in Appendix D.1.
sections.heading: 4.2 RELATIONSHIP BETWEEN ROBUSTNESS AND TRANSFERABILITY UNDER CONTROLLABLE CONDITIONS
sections.text: We train the model under different controllable conditions to validate our analysis. In particular, we train the methods by controlling different regularization or data augmentations to evaluate the change of model robustness and transferability.
  1These settings are inherited from the standard training algorithms for CIFAR-10 (https://github. com/kuangliu/pytorch-cifar) and ImageNet (https://github.com/pytorch/examples/ tree/master/imagenet).
  Controlling the norm of last layer As shown in our framework, domain transferability is related with the regularization on the feature extractor. Here we regularize the transferability by controlling the norm of last linear layer gs. Intuitively, when we force the norm of gs to be large during training, the corresponding norm of f will be regularized to be small. We use two approaches to control the last layer norm:
  • Last-layer regularization (LLR): we impose a strong l2-regularizer with parameter λl specifically on the weight of gs and therefore our training loss becomes: LLLR(hs, x, y) = LCE(hs, x, y) + λl · ||gs||F , where ||gs||F is the frobenius norm of the weight matrix of gs.
  • Last-layer orthogonal training (LLOT): we directly control the l2-norm of gs with orthogonal training (Huang et al. (2020)). The orthogonal training will enforce the weight to become a 1- norm matrix and we multiply a constant to obtain the desired norm ||gs||2.
  The result of LLR and LLOT are shown in Figure 3. We observe that when we regularize the norm of last layer to be large (i.e. smaller λ in LLR and larger ||gs||2 in LLOT), the domain transferability will increase while the model robustness will decrease (their negative correlation is significant with Pearson’s coefficient around −0.9). This is because larger last layer norm will produce a feature extractor f with smaller norm, which, according to our analysis, leads to a better domain transferability. On the other hand, the model gs ◦ f will have a larger norm and therefore becomes less robust under adversarial attacks.
  Controlling the norm of feature extractor We directly regularize the feature extractor f and check the impact on domain transferability. We implement two regularization as follows:
  • Jacobian regularization (JR): we follow the approach in Hoffman et al. (2019) to apply JR on the feature extractor. Given model hs = gs ◦ f , the training loss becomes: LJR(hs, x, y) = LCE(hs, x, y) +λj · ||J(f, x)||2F , where J(f, x) denotes the Jacobian matrix of f on x and || · ||F is the frobenius norm.
  • Weight Decay (WD): we impose a strong weight decay with factor λw on the feature extractor f during training. This is equivalent to imposing a strong l2-regularizer with factor λw on the feature extractor (excluding the last layer).
  The results under JR and WD are shown in Figure 4. We observe that with larger regularization on the feature extractor, the model shows higher domain transferability, which matches our analysis. Meanwhile, the robustness decreases significantly with large regularizer. This is because a large regularization will harm the model performance on source domain and lead to low model robustness.
  Data augmentation As shown in Section 3.4, data augmentation can be viewed as a type of regularization during training and thus affects the domain transferability. Here we consider both noise dependent and independent data augmentations.
  Noise-dependent data augmentation We include two noise-dependent augmentations:
  • Gaussian Noise data augmentation (Gauss): we add zero-mean Gaussian noise with variance σ2 to the input image.
  • Posterize (Pos): we truncate each channel of one pixel value into b bits (originally they are 8 bits).
  The results of Gauss and Pos are shown in Figure 5. We observe that the domain transferability of trained model keeps improving with larger data augmentation, which matches our theory. The robustness also benefits from a small data augmentation, but decreases when it becomes large.
  Resolution-related (noise-independent) data augmentation. Specifically, for ImageNet to CIFAR-10 transferability, we consider two resolution-related data augmentations. The intuition is that when the target domain has a lower resolution than the source domain (ImageNet is 224× 224 while CIFAR-10 is 32×32), the data augmentations that down-sample the inputs during the training on source domain will help transferability. We consider the below resolution-related augmentations:
  • Rescale: we rescale the input to bem times smaller (i.e., shape ImageNet as (224/m)×(224/m)) and then rescale them back to the original size.
  • Blur: we apply Gaussian blurring with kernel size k on the input. The Gaussian kernel is created with a standard deviation randomly sampled from [0.1, 2.0].
  We show the results of rescaling and blurring in Figure 6. The experiments are evaluated only for ImageNet to CIFAR-10, and we include the results of both ResNet18 (the default model) and WideResNet50. We can see that these data augmentations help with transferability to target domain, although the robustness on the source domain decreases since these augmentations do not include any robustness-related operations.
sections.heading: 5 CONCLUSIONS
sections.text: In this work, we theoretically analyze the sufficient conditions for domain transferability based on the view of function class regularization. We also conduct experiments to verify our claims and observe some counterexamples that shows a negative correlation between robustness and domain transferability. These results are helpful in the domain generalization of machine learning models.
sections.heading: ETHICS STATEMENT
sections.text: Our work focuses on theoretically and empirically studying the domain transferability of a machine learning model. All the datasets and packages we use are open-sourced. We do not have ethical concerns in our paper.
sections.heading: REPRODUCIBILITY STATEMENT
sections.text: We have tried our best to provide training details to facilitate reproducing our results. In Section 4.1 we provide detailed results on how to train the model and how to transfer the trained model to target domain, as well as how we evaluate our model. We also upload the zip file of our code with the submission. We will open-source our code once accepted.
sections.heading: A PROOFS
sections.text: Proposition A.1 (Proposition 3.1 Restated). Given the problem defined in subsection 3.1, fDSc is a minimizer of equation 1. Moreover, if c ≥ c′ ≥ 0, then the relative domain transfer loss `DT (fDSc )− `DS (f DS c ) ≥ `DT (f DS c′ )− `DS (f DS c′ ).
  Proof. Recall that `DS (f) = ‖f − yS‖D, `DT (f) = ‖f − yT ‖D and fDSc := yS min{1, c‖yS‖D }. First, let’s verify that
  fDSc ∈ arg min f∈F `DS (f), s.t. ‖f‖D ≤ c.
  If c ≥ ‖yS‖D, then fDSc := yS achieves the minimum. If c < ‖yS‖D, then for any f ∈ F : ‖f‖D ≤ c, we have
  `DS (f) = ‖f − yS‖D ≥ ‖yS‖D − ‖f‖D ≥ ‖yS‖D − c = ‖(1− c‖yS‖D )yS‖D = ‖yS − c ‖yS‖D yS‖D = `DS (f DS c ).
  Therefore, fDSc indeed achieves the minimum.
  Now, let’s prove the proposition. For any c ≥ ‖yS‖D, we have `DS (fDSc ) = 0 and `DT (fDSc ) is a constant. Therefore, there is no difference for all c ≥ ‖yS‖D, and the proposition holds for c ≥ c′ ≥ ‖yS‖D. Then, We only need to verify the case for ‖yS‖ ≥ c ≥ c′:
  `DS (f DS c′ )− `DS (f DS c ) = c− c′ = ‖ c‖yS‖D yS − c′
  ‖yS‖D yS‖D = ‖fDSc′ − f DS c ‖D = ‖f DS c′ − yT + yT − f DS c ‖D ≥ |‖fDSc′ − yT ‖D − ‖yT − f DS c ‖D| ≥ ‖fDSc′ − yT ‖D − ‖yT − f DS c ‖D = `DT (f DS c′ )− `DT (f DS c ).
  Rearranging the above inequality gives the proposition.
  Proposition A.2 (Proposition 3.2 Restated). dG,F (·, ·) : PX×Y ×PX×Y → R+ satisfies the following three properties.
  1. (Symmetry) dG,F (DS ,DT ) = dG,F (DT ,DS).
  2. (Triangle Inequality) For ∀D′ ∈ PX×Y : dG,F (DS ,DT ) ≤ dG,F (DS ,D′)+dG,F (D′,DT ).
  3. (Weak Zero Property) For ∀D ∈ PX×Y : dG,F (D,D) = 0.
  Proof. Recall that
  dG,F (DS ,DT ) := sup f∈F | inf g∈G `DS (g ◦ f)− inf g∈G `DT (g ◦ f)|.
  We can see that the symmetry and weak zero property are obvious. For triangle inequality, given ∀D′ ∈ PX×Y : dG,F (DS ,DT ) = sup
  f∈F | inf g∈G `DS (g ◦ f)− inf g∈G `DT (g ◦ f)|
  = sup f∈F | inf g∈G `DS (g ◦ f)− inf g∈G `D′(g ◦ f) + inf g∈G `D′(g ◦ f)− inf g∈G `DT (g ◦ f)|
  ≤ sup f∈F (| inf g∈G `DS (g ◦ f)− inf g∈G `D′(g ◦ f)|+ | inf g∈G `D′(g ◦ f)− inf g∈G `DT (g ◦ f)|)
  ≤ sup f∈F | inf g∈G `DS (g ◦ f)− inf g∈G `D′(g ◦ f)|+ sup f∈F | inf g∈G `D′(g ◦ f)− inf g∈G `DT (g ◦ f)| = dG,F (DS ,D′) + dG,F (D′,DT ).
  Proposition A.3. Denote the function class
  LG,F := {hg,f : X × Y → R+ | g ∈ G, f ∈ F}, where hg,f (x, y) := `(g ◦ f(x), y).
  Let d : X ×Y → R+ be a metric on X ×Y , and assume ∀h ∈ LG,F is L-Lipschitz continuous with respect to the metric d. Then, we have
  dFA(DS ,DT ) ≤ L ·W (DS ,DT ),
  where W (DS ,DT ) is the Wasserstein distance:
  W (DS ,DT ) = sup φ:X×Y→R E(x,y)∼DS [φ(x, y)]− E(x,y)∼DT [φ(x, y)] s.t. φ is 1-Lipschitz.
  Proof. Recall that
  dG,F (DS ,DT ) := sup f∈F | inf g∈G `DS (g ◦ f)− inf g∈G `DT (g ◦ f)|.
  By the definition of inf , for ∀ > 0 there exist gS, , gT, ∈ G such that
  inf g∈G `DS (g ◦ f ) ≥ `DS (gS, ◦ f )−
  inf g∈G `DT (g ◦ f ) ≥ `DT (gT, ◦ f )− .
  By the definition of sup, there exists f ∈ F such that
  dG,F (DS ,DT ) ≤ | inf g∈G `DS (g ◦ f )− inf g∈G `DT (g ◦ f )|+
  = max{ inf g∈G `DS (g ◦ f )− inf g∈G `DT (g ◦ f ), inf g∈G `DT (g ◦ f )− inf g∈G `DS (g ◦ f )}+
  ≤ max{`DS (gT, ◦ f )− inf g∈G `DT (g ◦ f ), `DT (gS, ◦ f )− inf g∈G `DS (g ◦ f )}+
  ≤ max{`DS (gT, ◦ f )− `DT (gT, ◦ f ), `DT (gS, ◦ f )− `DS (gS, ◦ f )}+ 2 . (2)
  Let’s first consider the first term in the max{·, ·} above.
  `DS (gT, ◦ f )− `DT (gT, ◦ f ) = L · ( 1L`DS (gT, ◦ f )− 1 L`DT (gT, ◦ f ))
  = L · (E(x,y)∼DS [ 1L`(gT, ◦ f (x), y)]− E(x,y)∼DT [ 1 L`(gT, ◦ f (x), y)]) ≤ L ·W (DS ,DT ),
  where the inequality is due to that both 1L`(gS, ◦ f (x), y) and 1 L`(gT, ◦ f (x), y) are 1-Lipschitz w.r.t. (x, y) and the metric d.
  Similarly, we also have
  `DT (gS, ◦ f )− `DS (gS, ◦ f ) ≤ L ·W (DS ,DT ).
  Therefore, equation 2 implies
  dG,F (DS ,DT ) ≤ L ·W (DS ,DT ) + 2 .
  Letting → 0 completes the proof.
  Proposition A.4. Consider multi-class classification where Y = [k] for some k ≥ 2. Define the loss function ` as
  `(g ◦ f(x), y) = 1{arg max j∈[k] (g ◦ f(x))j 6= y}
  Let δTV (DS , DT ) denote the total variation distance. Then we have
  dFA(DS ,DT ) ≤ δTV (DS ,DT )
  Proof. Fix f ∈ F . By the definition of inf, there exists gT, such that | inf g∈G `DS (g ◦ f)− inf g∈G `DT (g ◦ f)|
  ≤ | inf g∈G `DS (g ◦ f)− `DT (gT, ◦ f)|+
  ≤ |`DS (gT, ◦ f)− `DT (gT, ◦ f)|+ = |E(x,y)∼DS [`(gT, ◦ f(x), y)]− E(x,y)∼DT [`(gT, ◦ f(x), y)]|+ = |P(x,y)∼DS [1{arg max
  j∈[k] (gT, ◦ f(x))j 6= y}]− P(x,y)∼DT [1{arg max j∈[k] (gT, ◦ f(x))j 6= y}]|+
  (3)
  Let A be the event such that A = {(x, y) : arg maxj∈[k](gT, ◦ f(x))j 6= y}. Then we can write equation 3 as
  (3) = |P(x,y)∼DS [A]− P(x,y)∼DT [A]|+ ≤ sup
  B |P(x,y)∼DS [B]− P(x,y)∼DT [B]|+
  = δTV (DS ,DT ) + Send → 0. Noting that f ∈ F was arbitrary, apply sup to both sides gives us the desired inequality.
  Theorem 3.1 can be proved easily by definition. Theorem A.1 (Theorem 3.1 Restated). Given a training algorithm A, for ∀DS ,DT ∈ PX×Y we have
  τ(A;DS ,DT ) ≤ dFA(DS ,DT ), or equivalently, inf
  g∈G `DT (g ◦ f DS A ) ≤ `DS (g DS A ◦ f DS A ) + dFA(DS ,DT ).
  Proof. By definition,
  τ(A;DS ,DT ) = inf g∈G `DT (g ◦ f DS A )− `DS (g DS A ◦ f DS A )
  ≤ inf g∈G `DT (g ◦ f DS A )− inf g∈G `DS (g ◦ f DS A )
  ≤ | inf g∈G `DT (g ◦ f DS A )− inf g∈G `DS (g ◦ f DS A )|
  ≤ sup f∈FA | inf g∈G `DT (g ◦ f)− inf g∈G `DS (g ◦ f)|
  = dFA(DS ,DT ).
  To prove Theorem 3.2, we first prove the following interesting lemma. Lemma A.1. Let Sd−1r := {y ∈ Rd | ‖y‖2 = r} denotes the (d−1)-dimensional sphere in Rd with radius r > 0. If a function h : Sd−1r → Rd satisfies
  ∀y ∈ Sd−1r : 〈h(y), y〉 < 0, (4) then we have
  ~0 ∈ conv(h(Sd−1r )),
  i.e., ~0 is in the convex hull of {h(y) | y ∈ Sd−1r }.
  Proof. We assume that ~0 /∈ conv(h(Sd−1r )) and prove by contradiction. Since ~0 /∈ conv(h(Sd−1r )), we can find a hyperplane that separates ~0 and the convex set conv(h(Sd−1r )). By the separating hyperplane theorem there exists a nonzero vector v ∈ Rd and c ≥ 0 such that
  ∀z ∈ conv(h(Sd−1r )) : 〈z,v〉 ≥ c ≥ 0. (5)
  We choose y = rv/‖v‖2 and observe that h(y) ∈ conv(h(Sd−1r )). Hence, by equation 5 we have
  〈h(y), y〉 ≥ 0,
  which contradicts to the condition of equation 4. Therefore, it must be that ~0 ∈ conv(h(Sd−1r )).
  Theorem A.2 (Theorem 3.2 Restated). Given any source distributionDS ∈ PX×Rd , any fine-tuning function class G where G includes the zero function, and any training algorithm A, denote
  := `DS (g DS A ◦ f DS A )− inf g∈G,f∈FA `DS (g ◦ f).
  We assume some properties of the sample individual loss function ` : Rd × Rd → R+: it is differentiable and strictly convex w.r.t. its first argument; `(y, y) = 0 for any y ∈ Rd; and limr→∞ infy:‖y‖2=r `(~0, y) = ∞. Then, for any distribution DX on X , there exist some distributions DT ∈ PX×Y with its marginal on X being DX such that
  τ(A;DS ,DT ) ≤ dFA(DS ,DT ) ≤ τ(A;DS ,DT ) + .
  Proof. The τ(A;DS ,DT ) ≤ dFA(DS ,DT ) is proved by Theorem 3.1, we only need to prove that there exists some DT ∈ PX×Y with its marginal on X being DX such that
  dFA(DS ,DT ) ≤ τ(A;DS ,DT ) + = inf g∈G `DT (g ◦ f DS A )− inf g∈G,f∈FA `DS (g ◦ f).
  We begin by observing that limr→∞ infy:‖y‖2=r `(~0, y) =∞, and thus there exists r > 0 such that
  ∀y ∈ Sd−1r : `(~0, y) ≥ `DS (~0) = E(x,y)∼DS [`(~0, y)], (6)
  where Sd−1r := {y ∈ Rd | ‖y‖2 = r} denotes the (d − 1)-dimensional sphere with radius r. Note the we abuse the notion a bit to let ~0 also denotes the zero function (i.e., maps all input to zero). Now, let us define at the following set
  V := {∇1`(~0, y) | y ∈ Sd−1r },
  where ∇1 is taking the gradient w.r.t. the first argument of `(·, ·). By the strict convexity of `(·, y), we have
  `(y, y)− `(~0, y) > 〈∇1`(~0, y), y〉.
  Noting that `(y, y) = 0 is the unique minimum of `(·, y), we have `(~0, y) > 0. Accordingly,
  ∀y ∈ Sd−1r : 0 > −`(~0, y) > 〈∇1`(~0, y), y〉.
  Having the above property, and noting that ∇1`(~0, ·) : Sd−1r → Rd, we can invoke Lemma A.1 to see that
  ~0 ∈ conv(V).
  Therefore, there exists n points {yi}ni=1 ⊂ Sd−1r such that
  ~0 = n∑ i=1 ci∇1`(~0, yi), (7)
  where ci > 0 and ∑n i=1 ci = 1.
  Therefore, we can define the target distribution DT as the following. Given any x ∼ DX , the distribution of y conditioned on x is: y = yi with probability ci. Now we verify the distribution DT indeed makes the bound -tight. Denote a strictly convex function h : Rd → R+ as the following
  h(·) := n∑ i=1 ci`(·, yi).
  Since h is strictly convex and ∇h(~0) = ~0 (equation 7), we can see that h(~0) achieves the unique global minimum of h on Rd.
  Therefore, given the DT , for any ∀f ∈ FA we have inf g∈G `DT (g ◦ f) = inf g∈G E(x,y)∼DT [`(g ◦ f(x), y)]
  = inf g∈G Ex∼DX [ n∑ i=1 ci`(g ◦ f(x), yi) ] = inf g∈G Ex∼DX [h(g ◦ f(x))]
  = h(~0) (G contains the zero function)
  = n∑ i=1 ci`(~0, yi). (8)
  Recall that dFA(DS ,DT ) = supf∈FA | infg∈G `DT (g ◦ f)− infg∈G `DS (g ◦ f)|, we can see that
  dFA(DS ,DT ) = sup f∈FA | n∑ i=1 ci`(~0, yi)− inf g∈G `DS (g ◦ f)| (9)
  By equation 6, for ∀f ∈ FA, we have n∑ i=1 ci`(~0, yi) ≥ `DS (~0) = `DS (~0 ◦ f) ≥ inf g∈G `DS (g ◦ f).
  Hence, we can continue as
  (9) = sup f∈FA ( n∑ i=1 ci`(~0, yi)− inf g∈G `DS (g ◦ f) ) = n∑ i=1 ci`(~0, yi)− inf g∈G,f∈FA `DS (g ◦ f)
  = inf g∈G
  `DT (g ◦ f DS A )− inf g∈G,f∈FA `DS (g ◦ f) (by equation 8)
  = inf g∈G
  `DT (g ◦ f DS A )− `DS (g DS A ◦ f DS A ) + `DS (g DS A ◦ f DS A )− inf g∈G,f∈FA `DS (g ◦ f)
  = τ(A;DS ,DT ) + . Therefore, it holds that dFA(DS ,DT ) ≤ τ(A;DS ,DT ) + , and thus the theorem.
  Lemma A.2 (Lemma 3.1 Restated). Assuming the individual loss function ` : Y×Y → [0, c], given any distribution D ∈ PX×Y and ∀δ > 0, with probability ≥ 1− δ we have
  dG,F (D, D̂n) ≤ 2RadD̂n(LG,F ) + 3c √ ln(4/δ)
  2n .
  Proof. Given any δ > 0, f ∈ F , g ∈ G, D ∈ PX×Y , and taking any hg,f ∈ LG,F (Definition 3), with probability ≥ 1− δ we have
  `D(g ◦ f)− `D̂n(g ◦ f) = E(x,y)∼D[hg,f (x, y)]− 1
  n n∑ i=1 hg,f (xi, yi)
  ≤ 2RadD̂n(LG,F ) + 3c √ ln(2/δ)
  2n , (10)
  where the inequality is by the well-known Rademacher complexity uniform bound. Similarly,
  `D̂n(g ◦ f)− `D(g ◦ f) = E(x,y)∼D[−hg,f (x, y)]− 1
  n n∑ i=1 −hg,f (xi, yi)
  ≤ 2RadD̂n(−LG,F ) + 3c √ ln(2/δ)
  2n = 2RadD̂n(LG,F ) + 3c √ ln(2/δ)
  2n . (11)
  The probability that both events equation 10 and equation 11 happen can be upper bounded by union bound, i.e.,
  Pr((10) ∧ (11)) = 1− Pr((10)c ∨ (11)c) ≥ 1− (Pr((10)c) + Pr((11)c)) ≥ 1− 2δ. Therefore, combining the above with probability ≥ 1− δ we have
  |`D(g ◦ f)− `D̂n(g ◦ f)| ≤ 2RadD̂n(LG,F ) + 3c √ ln(4/δ)
  2n . (12)
  With equation 12, we can prove the lemma as the following. Given ∀ > 0, by the definition of infimum there exists a g ∈ G such that
  `D(g ◦ f) < inf g∈G `D(g ◦ f) + .
  By equation 12, with probability ≥ 1− δ we have `D̂n(g ◦ f) ≤ `D(g ◦ f) + 2RadD̂n(LG,F ) + 3c √ ln(4/δ)
  2n .
  Moreover, by definition
  inf g∈G `D̂n(g ◦ f) ≤ `D̂n(g ◦ f).
  Combining the above three inequalities we have
  inf g∈G `D̂n(g ◦ f) < infg∈G `D(g ◦ f) + + 2RadD̂n(LG,F ) + 3c √ ln(4/δ) 2n .
  Letting → 0, we can see that
  inf g∈G `D̂n(g ◦ f) ≤ infg∈G `D(g ◦ f) + 2RadD̂n(LG,F ) + 3c √ ln(4/δ) 2n .
  Similarly, we can derive the above inequality again but with D and D̂n switched. Therefore,
  | inf g∈G `D̂n(g ◦ f)− infg∈G `D(g ◦ f)| ≤ 2RadD̂n(LG,F ) + 3c √ ln(4/δ) 2n .
  Since the above inequality holds for ∀f ∈ F , taking the supremum over f ∈ F gives the lemma.
  Lemma A.3. Assuming the individual loss function ` : Y × Y → [0, c], given any distributions DS ,DT ∈ PX×Y and ∀δ > 0, with probability ≥ 1− δ we have
  dFA(DS ,DT ) ≤ dFA(D̂nS , D̂nT ) + 2(RadD̂nS (LG,FA) + RadD̂nT (LG,FA)) + 6c √ ln(8/δ) 2n .
  Proof. By Proposition 3.2, we apply the triangle inequality to derive
  dFA(DS ,DT ) ≤ dFA(DS , D̂nT ) + dFA(D̂nT ,DT ) ≤ dFA(D̂nS , D̂nT ) + dFA(D̂nT ,DT ) + dFA(D̂nS ,DS).
  By Lemma 3.1, we can apply the union bound argument (e.g., see the proof of Lemma 3.1) to bound dFA(D̂nT ,DT ) and dFA(D̂nS ,DS). That being said, ∀δ′ > 0 with probability ≥ 1− 2δ′ we have
  dFA(D̂nS ,DS) ≤ 2RadD̂nS (LG,FA) + 3c √ ln(4/δ′)
  2n dFA(D̂nT ,DT ) ≤ 2RadD̂nT (LG,FA) + 3c √ ln(4/δ′) 2n .
  Therefore, dFA(D̂nT ,DT ) + dFA(D̂nS ,DS) ≤ 2(RadD̂nS (LG,FA) + RadD̂nT (LG,FA)) + 6c √ ln(4/δ′) 2n .
  Denoting δ = 2δ′ gives the lemma.
  Theorem A.3 (Theorem 3.3 Restated). Given ∀DS ,DT ∈ PX×Y , for ∀δ > 0 with probability ≥ 1− δ we have
  τ(A; D̂nS ,DT ) ≤ dFA(D̂nS , D̂nT ) + 2RadD̂nT (LG,FA) + 4RadD̂nS (LG,FA) + 9c √ ln(8/δ) 2n .
  Proof. For ∀δ > 0, from the proof of Lemma A.3 we can see that with probability ≥ 1− δ: dFA(D̂nS ,DS) ≤ 2RadD̂nS (LG,FA) + 3c √ ln(8/δ) 2n (13)
  dFA(D̂nT ,DT ) ≤ 2RadD̂nT (LG,FA) + 3c √ ln(8/δ) 2n ,
  and Lemma A.3 holds. Therefore
  τ(A; D̂nS ,DT ) = inf g∈G `DT (g ◦ f D̂nS A )− `D̂nS (g D̂nS A ◦ f D̂nS A )
  ≤ inf g∈G
  `DT (g ◦ f D̂nS A )− inf
  g∈G `D̂nS
  (g ◦ f D̂ n S
  A )
  = inf g∈G
  `DT (g ◦ f D̂nS A )− inf
  g∈G `DS (g ◦ f
  D̂nS A ) + inf
  g∈G `DS (g ◦ f
  D̂nS A )− inf
  g∈G `D̂nS
  (g ◦ f D̂ n S
  A )
  ≤ dFA(DS ,DT ) + dFA(D̂nS ,DS) ≤ dFA(DS ,DT ) + 2RadD̂nS (LG,FA) + 3c √ ln(8/δ)
  2n ≤ dFA(D̂nS , D̂nT ) + 2RadD̂nT (LG,FA) + 4RadD̂nS (LG,FA) + 9c √ ln(8/δ) 2n ,
  where the first inequality is by definition of infimum, the second inequality is by the Definition 2, the third inequality is by equation 13 and the last inequality is by Lemma A.3.
sections.heading: B DATA AUGMENTATION (DA) AS REGULARIZATION
sections.text: In this section, we discuss data augmentation (DA) as a concrete example of regularization for training feature extractor fDSA , and explore its impact on the function class FA discussed in Section 3. Empirical research has shown evidence of the regularization effect of DA (Hernández-Garcı́a & König, 2018a;b). However, there is a lack of theoretical analysis, and thus we aim to construct a theoretical framework to understand under what sufficient conditions DA can be viewed as regularization on the feature extractor function class FA. We categorize DA into feature-level DA and data-level DA, and for each category, we analyze different DA algorithms to characterize the sufficient conditions under which DA regularizes the function class FA. Combined with analysis in Theorem 3.3, we also provide concrete sufficient conditions to tighten the upper bound of relative transferability τ(A; D̂n,DT ). General Settings. For the following discussion we apply a general DA setting of affine transformation (Perez & Wang, 2017), taking the form of x? = W>? x + b?, where (x, x?) is a pair of the original and augmented samples, (W?, b?) are parameters representing specific DA policies. We set g : Rd → R as the linear layer corresponding to the weight matrixWg , which will be composed with the feature extractor f : Rm → Rd. We use squared loss for ` : R × R → R, and let `D̂n,A(g ◦ f) be the objective function given by training algorithm A from Theorem 3.3.
  B.1 FEATURE-LEVEL DA (AFL)
  Feature-level DA (Wong et al., 2016; DeVries & Taylor, 2017) requires the transformation to be performed in the learned feature space, which gives us an augmented feature W?f(x) + b?. We use Loss-Averaging algorithm where we take an average of the loss over augmented features for
  training. Denote the training algorithm based on feature-level DA as AFL, the objective function is as below.
  `D̂n,AFL(g ◦ f) = 1
  n n∑ i=1 EW?,b?` ( g ◦ ( W?f(xi) + b? ) , yi ) .
  Theorem B.1. Apply feature-level DA with affine transformation parameters (W?, b?) s.t. 1) EW? [W?] = Im; 2) W? 6≡ Im (i.e., W? is not an identity matrix); 3) Eb? [b?] = ~0m; 4) W? and b? are independent. Set ` : R× R→ R as squared loss; Define ∆W? := W? − Im, then we have
  `D̂n,AFL(g ◦ f) = `D̂n,A(g ◦ f) + ΩAFL ,
  where ΩAFL = 1n ∑n i=1 EW? [∥∥f(xi)>∆W?Wg∥∥22]+ Eb?[∥∥b>?Wg∥∥22]. Proof. `′′(W>g ◦ f(xi)) = 2 for ` as squared loss. Apply Taylor expansion to ` ( g ◦ ( W?f(xi) +
  b? ) , yi ) around f(xi), all higher-than-two order terms will vanish:
  EW?,b? [ ` ( g ◦ ( W?f(xi) + b? ) , yi )] =EW?,b? [ ` ( W>g ◦ f(xi), yi ) +W>g (∆W?f(xi) + b?)` ′(W>g ◦ f(xi), yi)+
  1 2 W>g (∆W?f(xi) + b?)(∆W?f(xi) + b?)
  >`′′(W>g ◦ f(xi), yi)Wg ]
  =` ( W>g ◦ f(xi), yi ) + EW?,b? [ W>g (∆W?f(xi) + b?)(∆W?f(xi) + b?) >Wg ] =` ( W>g ◦ f(xi), yi ) + EW?
  [∥∥f(xi)>∆W?Wg∥∥22]+ Eb?[∥∥b>?Wg∥∥22]; The second equality holds since E∆W? = EW? [W? − Im] = 0(m,m) and Eb? = ~0m; The third
  equality holds sinceWi and bi are independent. Therefore, `D̂n,AFL(g◦f) := 1 n ∑n i=1 [ EW?,b?` ( g◦(
  W?f(xi) + b? ) , yi )] = `D̂n,A(g ◦ f) + ΩAFL .
  Interpretation. ΩAFL is composed of two segments: 1) l2 regularization to an f -dependent scalar averaged over W? and xi; 2) l2 regularization to an f -independent scalar averaged over b?. Due to the regularization effect on f from the first segment of ΩAFL , we can reasonably expect the function class FA′ enabled by AFL to be a subset of that enabled by a general training algorithm A. Sufficient conditions. Combined with Theorem 3.3, the sufficient conditions to tighten the upper bound dFA(D̂nS , D̂nT ) for the relative transferability τ(A; D̂S ,DT ) are: feature-level DA (AFL) with parameters satisfying: 1) EW? [W?] = Im; 2) W? 6≡ Im; 3) Eb? [b?] = ~0m; 4) W? and b? are independent.
  B.2 DATA-LEVEL DA (ADL)
  Data-level DA requires that the transformation to be performed in the input space to generate augmented samples W?x + b?. We cover analysis on two ubiquitous algorithms for data-level DA training: Prediction-Averaging (ADLP ) (Lyle et al., 2019) and Loss-Averaging (A DL L ) (Wong et al., 2016). The difference between ADLP and A DL L lies in whether we take the average of the prediction or the losses:
  `D̂n,ADLP (g ◦ f) := 1
  n n∑ i=1 ` ( EW?,b? [ g ◦ f(W?xi + b?) ] , yi ) ; (14)
  `D̂n,ADLL (g ◦ f) := 1
  n n∑ i=1 EW?,b? [ ` ( g ◦ f(W?xi + b?), yi )] .
  Theorem B.2. Define the data-level deviation caused by data-level DA ADL ∈ {ADLP , ADLL } with parameters (W?, b?) from the original data sample as ∆xi := (W?− Im)xi + b?, and define ∆3x := Exi,W?,b? [∥∥∆xi∥∥32]. Suppose we apply data-level DA s.t. 1) EW? [W?] = Im; 2) Eb? [b?] = ~0m; 3) O(∆jx) ≈ 0,∀j ∈ N+, j ≥ 3; 4) W? and b? are independent. Define ∆W? := W? − Im ∈ Rm×m, ∆ŷi := W > g f(xi)− yi ∈ R. Let W (k) g ∈ R be the kth dimension component of Wg and then define wi,(k) := W (k) g ∆ŷi ∈ R; Denote the Hessian matrix of the kth dimension component in f(xi) as H(k),if ; Let ∇f be the Jacobian matrix of f , then we have
  `D̂n,ADL(g ◦ f) = `D̂n,A(g ◦ f) + ΩADL +O(∆ 3 x),
  where ΩADLP = 1 n ∑n i=1 ∑d k=1 wi,(k) [ tr ( EW? [∆xi∆>xi ]H (k),i f )] , where ∆xi = (W?− I)>xi+b?;
  ΩADLL = ΩADLP + 1 n ∑n i=1 [ EW? ∥∥x>i ∆W?∇f(xi)Wg∥∥22 + Eb?∥∥b>? ∇f(xi)Wg∥∥22]. Proof. Let ∆fi,ADLP := EW?,b?f(W > ? xi + b?)− f(xi), then
  ∆fi,ADLP :=EW?,b?f(W > ? xi + b?)− f(xi) =EW?,b? [ ∇f(xi)>(∆xi) ] + 1
  2 EW?,b?
  [ ∆>xiH (k),i f (xi)∆xi ] d +O(EW?,b?‖∆xi‖32)
  = 1
  2 EW?,b?
  [ ∆>xiH (k),i f (xi)∆xi ] d +O(EW?,b?‖∆xi‖32), (15)
  where [·(k)]d denotes a d-dimensional vector and k denotes the kth dimension element. Since ` is squared loss, the third-and-higher derivative are 0, therefore, the third-and-higher order terms in Taylor expansion to ` ( EW?,b? [ g ◦ f(W?xi + b?) ] , yi ) around f(xi) will vanish:
  ` ( EW?,b? [ g ◦ f(W?xi + b?) ] , yi )
  =` ( g ◦ f(xi), yi ) +W>g (∆fi,ADLP )` ′(g ◦ f(xi), yi)+ 1
  2 W>g (∆fi,ADLP )(∆fi,ADLP )
  >Wg` ′′(g ◦ f(xi), yi)
  =` ( g ◦ f(xi), yi ) +W>g (∆fi,ADLP )` ′(g ◦ f(xi), yi)+O(EW?,b?‖∆xi‖42) (16) Substitute Eq. (15) into the first-order term in Eq. (16), we have
  W>g (∆fi,ADLP )` ′(g ◦ f(xi), yi) =W>g EW?,b?[∆>xiH(k),if ∆xi] d ∆ŷi +O(EW?,b?‖∆xi‖32)
  =∆ŷi d∑ k=1 W (k)g EW?,b? [ ∆>xiH (k),i f ∆xi ] +O(EW?,b?‖∆xi‖32)
  = d∑ k=1 wi,(k)tr ( EW?,b? [∆xi∆>xi ]H (k),i f ) +O(EW?,b?‖∆xi‖32).
  (17)
  Substitute Eq. (17) into Eq. (16), we have
  ` ( EW?,b? [ g ◦ f(W?xi + b?) ] , yi ) =` ( g ◦ f(xi), yi ) + d∑ k=1 wi,(k)tr ( EW?,b? [∆xi∆>xi ]H (k),i f ) +
  O(EW?,b?‖∆xi‖32). (18)
  Substitute Eq. (18) into Eq. (14) which is the definition of `D̂n,ADLP (g ◦ f), and recall that ∆ 3 x := Exi,W?,b? [∥∥∆xi∥∥32], we have
  `D̂n,ADLP (g ◦ f) := 1
  n n∑ i=1 ` ( EW?,b? [ g ◦ f(W?xi + b?) ] , yi ) = `D̂n,A(g ◦ f) + ΩADLP +O(∆ 3 x).
  (19)
  Let ∆fi,ADLL := f(W > ? xi + b?)− f(xi) = ∇f(xi)>(∆W?xi + b?) +O(‖∆xi‖22). Applying Taylor expansion to EW?,b? [ ` ( g ◦ f(W?xi + b?), yi )] around f(xi) will give us
  EW?,b? [ ` ( g ◦ f(W?xi + b?), yi )] =` ( g ◦ f(xi), yi ) +W>g EW?,b? [ ∆fi,ADLL ] `′ ( g ◦ f(xi), yi ) +
  1 2 W>g EW?,b? [ (∆fi,ADLL )(∆fi,ADLL ) >]Wg`′′(g ◦ f(xi), yi) (20)
  Since EW?,b?∆fi,ADLL = ∆fi,ADLP , the first-order term in Eq. (20) is exactly Eq. (17): W>g EW?,b? [ ∆fi,ADLL ] `′ ( g ◦ f(xi), yi ) =W>g ∆fi,ADLP `
  ′(g ◦ f(xi), yi) =
  d∑ k=1 wi,(k)tr ( EW?,b? [∆xi∆>xi ]H (k),i f ) +O(EW?,b?‖∆xi‖32) (21)
  The second-order term in Eq. (20) is 1
  2 W>g EW?,b? [ (∆fi,ADLL )(∆fi,ADLL ) >]Wg`′′(g ◦ f(xi), yi) =W>g EW?,b? [ (∇f(xi)>(∆W?xi + b?)(∆W?xi + b?)>∇f(xi) ] Wg +O(EW?,b?‖∆xi‖42)
  =EW? ∥∥x>i ∆>W?∇f(xi)Wg∥∥22 + Eb?∥∥b>? ∇f(xi)Wg∥∥22 +O(EW?,b?‖∆xi‖42) (22)
  Substituting Eq. (21) and Eq. (22) into Eq. (20), we have EW?,b? [ ` ( g ◦ f(W?xi + b?), yi )] =` ( g ◦ f(xi), yi ) +
  d∑ k=1 wi,(k)tr ( EW?,b? [∆xi∆>xi ]H (k),i f ) +
  EW? ∥∥x>i ∆W?∇f(xi)Wg∥∥22 + Eb?∥∥b>? ∇f(xi)Wg∥∥22 +O(EW?,b?‖∆xi‖42) (23)
  Substitute Eq. (23) into the definition of `D̂n,ADLL (g ◦ f), then
  `D̂n,ADLL (g ◦ f) := 1
  n n∑ i=1 EW?,b? [ ` ( g ◦ f(W?xi + b?), yi )] = `D̂n,A(g ◦ f) + ΩADLL +O(∆ 3 x)
  (24)
  The proof is complete by Eq. (19) and Eq. (24).
  Interpretation. ΩADLP and ΩADLL turn out to be: 1) ΩADLP is a weighted trace expectation dependent on the Hessian matrix of f ; 2) ΩADLL is equivalent to ΩADLP together with the summation of two norm expectations dependent on ∇f . Therefore, the data-level DA algorithms ADLP and ADLL are expected to regularize f so that the f function class FDLA enabled by ADL ∈ {ADLP , ADLL } would be reasonably expected as a subset of FA enabled by general training algorithm A. Sufficient conditions. Combined with Theorem 3.3, the sufficient conditions indicated here to tighten the upper bound dFA(D̂nS , D̂nT ) of the relative transferability τ(A; D̂S ,DT ) are: datalevel DA (ADL) with DA parameters satisfying that 1) EW? [W?] = Im; 2) Eb? [b?] = ~0m; 3) O(∆jx) ≈ 0,∀j ∈ N+, j ≥ 3; 4) W? and b? are independent. Empirical verification. We further provide empirical verification in Section 4 for the sufficient conditions above, investigating the concrete cases of DA methods: 1) Gaussian noise satisfies the sufficient conditions, then we empirically show that Gaussian noise improves domain transferability while robustness decreases a bit (Figure 5); 2) Rotation, which rotates input image with a predefined fixed angle with predefined fixed probability, violates EW? [W?] = Im, and we empirically show that rotation barely affect domain transferability (Figure 14 in Appendix D.3); Translation, which moves the input image for a predefined distance along a pre-selected axis with fixed probability, violates Eb? [b?] = ~0m (Figure 14 in Appendix D.3).
  Corollary B.2.1. If the neural network in Theorem B.2 is activated by Relu or Max-pooling, then Theorem B.2 becomes
  `D̂n,ADL(g ◦ f) = `D̂n,A(g ◦ f) + ΩADL +O(∆ 3 x),
  where ΩADLP = 0; ΩADLL = 1 n ∑n i=1 [ EW? ∥∥x>i ∆W?∇f(xi)Wg∥∥22 + Eb?∥∥b>? ∇f(xi)Wg∥∥22]. Proof. Denote an L−layer NN g ◦ f(x) := W>g · z[L−1], where z[l] := σ[l−1](W>[l−1] · z
  [l−1]), l = 1, 2, 3, ..., L− 1; Define that σ[0](W>[0] · z [0]) := x, then∇2 ( g ◦ f(x) ) = 0 (B.2 of Zhang et al.
  (2020)). Since∇2 ( g ◦ f(x) ) = W>g · ∇2f(x), we have∇2f(x) = 0.
  Combine this with Theorem B.2, we have
  ΩADLP = 1
  n n∑ i=1 d∑ k=1 wi,(k) [ tr ( EW? [∆xi∆>xi ]H (k),i f )] = 0;
  ΩADLL = ΩADLP + 1
  n n∑ i=1 [ EW? ∥∥x>i ∆W?∇f(xi)Wg∥∥22 + Eb?∥∥b>? ∇f(xi)Wg∥∥22] = 1
  n n∑ i=1 [ EW? ∥∥x>i ∆W?∇f(xi)Wg∥∥22 + Eb?∥∥b>? ∇f(xi)Wg∥∥22].
  Remark. Corollary B.2.1 analyzes special cases (Relu/ Max-pooling activation) of Theorem B.2, giving notably different regularization effect: in these cases theADLP (average the prediction) fails as a regularizer, therefore, doesn’t fulfill our sufficient conditions for improving domain transferability (Theorem 3.3); ADLL (average the loss) only reserves the regularization on ∇f -dependent norms, but no longer regularizes Hf (x). Since ADLL still induces regularization, the induced sufficient conditions analyzed after Theorem B.2 for promoting domain transferability won’t be affected.
sections.heading: C ADVERSARIAL TRAINING AS A REGULARIZER
sections.text: In this section, we show, under certain conditions, why adversarial training may improve domain generalization by viewing adversarial training as a function class regularizer.
  We first provide some notation. Let
  F = {fθ(·) = WLφL−1(WL−1φL−2(. . . ) + bL−1) + bL} where φj are activations, W j , bj are weight matrix and bias vector, θ is the collection of parameters (i.e. θ = (W 1, b1, . . . ,WL, bL). For the rest of the article, assume that φj are just ReLUs.
  Now fix x ∈ X . Define the preactivation as x̃1 := W 1x+ b1
  x̃j := W jφj−1(x̃j−1) + bj , j ≥ 2
  Define the activation pattern φx := (φ1x, . . . , φ L−1 x ) ∈ {0, 1}m such that for each j ∈ [L− 1]
  φjx = 1(x̃ j > 0)
  where 1 is applied elementwise.
  Now, given an activation pattern φ ∈ {0, 1}m, we define the preimage X(φ) := {x ∈ Rd : φx = φ} Theorem C.1. (In the proof of theorem 1 in (Roth et al., 2020))
  Let > 0 s.t. Bp (x) ⊂ X(φx) where Bp (x) denotes the lp ball centered at x with radius . Let p = {1, 2,∞} and q be the Holder conjugate of p (i.e. 1p + 1 q = 1). Then
  E(x,y)∼P [l(y, f(x)) + λ max x∗∈Bp (x) ‖f(x)− f(x∗)‖q] = E(x,y)∼P [l(y, f(x)) + λ · max v∗ : ‖v∗‖p≤1
  ∥∥Jf(x)v∥∥q]
  Interpretation: This theorem provides an equivalence between the objective functions for adversarial training (left term) and jacobian regularization (right term). We give some intuition on the size of . Let us first consider a shallow 2 layer network f(x) = W 2φ(W 1x+b1). SupposeW 2 ∈ Rm2×m1 and W 1 ∈ Rm1×d. Given a matrix M, let Mj denote the jth row of M . We study the activation pattern φx which equals
  φx = (φ 1 x) =  1{W 1 1 x+ b 1 1}
  ... 1{W 1m1x+ b 1 m1}  We wish to compute the largest radius such that the activation pattern φx is constant within B2 (x). This is simply the distance from x to the closest hyperplane of the form HW 1j ,b1j = {x ∈ R d : W 1j x+ b 1 j = 0} where j = 0, . . . ,m1 (i.e. = minj dist(x,HW 1j ,b1j )). In particular, if W 1 = Id×d and b1 = 0, = minj∈d|xj |. Furthermore, we note that is nondecreasing as a function of the number of layers. However, it has been observed empirically in (Roth et al., 2020) that approximate correspondence holds in a much larger ball. Definition 4. (source and target function class) Let GS ,GT be fine tuning function classes for source and target domains, respectively. We define the class of source models as
  HS = GS ◦ F = {gS ◦ fθ : gS ∈ GS , fθ ∈ F}
  and the class of target models as
  HT = GT ◦ F = {gT ◦ fθ : gT ∈ GT , fθ ∈ F}
  Definition 5. (empirical training objective with jacobian regularization) Let λ, > 0. Take any hypothesis hθ = gS ◦ fθ ∈ HS . Let R̂(hθ) = 1n ∑n i=1 `(hθ(xi), yi) denote the empirical risk where l(ŷ, y) = ‖ŷ − y‖2. We define the empirical training objective with jacobian regularization as
  ObjAλ (hθ) = R̂(hθ) + λ · n n∑ i=1 ‖Jhθ (xi)‖2
  Theorem C.2. Fix regularization strength λ > 0. Define
  FAλ = {fAθ ∈ F : ∃gS ∈ GS s.t. Obj A λ (g S ◦ fAθ ) ≤ Obj A λ (0)}
  where 0 denotes the zero function (i.e. the class of feature extractors that outperform the zero function). Suppose (x, y) ∈ X × Y is bounded such that max (‖x‖∞ , ‖y‖2) ≤ R. Fix δ > 0. Suppose we additionally restrict our fine tuning class models to linear models where
  GS = {W : W ∈ Rd×n, n ≥ 1,min j ‖Wj‖2 ≥ δ}
  (where Wj is the jth column of W ) and
  GT = {W : W ∈ Rd×n, n ≥ 1}
  (Here we are abusing notation to let gS ∈ GS to denote the last linear layer as well as the fine tuning function).
  Then for 0 ≤ λ1 < λ2 FAλ2 ( F A λ1 ( F
  (where ( denotes proper subset). In particular, if HA,Tλ = GT ◦ FAλ , we have
  HA,Tλ2 ( H A,T λ1 ( HT
sections.heading: Interpretation:
sections.text: At the high level, this theorem captures the idea that minimizing the empirical risk with jacobian regularization puts a constraint on the set of feature extractors. In particular, FAλ1 represents the potential class of feature extractors we select after training with jacobian regularization. Therefore,
  the class of fine tuned models HA,Tλ1 with feature extractors trained with jacobian regularization for the target domain is smaller than the class of fine tuned models H with feature extractors trained without any regularization. Furthermore, we show that the space of feature extractors shrinks as we increase the regularization stength λ. Since we showed in section 3.3 that smaller function classes have smaller dFA , this theorem shows that jacobian regularization reduces dFA . To connect back to adversarial training, if satisfies the hypothesis in theorem C.1, we have that E(x,y)∼P [l(y, f(x)) + λ max
  x∗∈Bp (x) ‖f(x)− f(x∗)‖q] = E(x,y)∼P [l(y, f(x)) + λ · max
  v∗ : ‖v∗‖p≤1 ∥∥Jf(x)v∥∥q] Therefore, minimizing the training objective with jacobian regularization is equivalent to minimizing the adversarial training objective. Using this connection, this theorem essentially shows that, given sufficient number of samples, adversarial training reduces the class of feature extractors which in turn reduces dFA .
  Finally, we comment on the assumption that ∥∥gS∥∥ > δ. Since δ > 0 is arbitrary, we can make it as small as we like and thus we are essentially excluding the 0 last layer which is hardly a constraint on the function class. This assumption is necessary as we are considering regularization on the whole model g◦f as opposed to regularization on just the feature extractor. Thus, this assumption prevents the scenario where only the last linear layer is regularized.
  Proof. We first show that if 0 ≤ λ1 < λ2, we have that FAλ2 ( F A λ1 ( F
  We first prove the following lemma
  Lemma C.1. Suppose the conditions of theorem C.2 are satisfied. Suppose additionally we have that y := 1n ∑d i=1 yi 6= 0 (note this occurs with probability 1 if marginal distribution over Y is continuous). Then for every λ ≥ 0, there exists a function fθ ∈ FAλ and a fine tuning layer g∗ ∈ GS such that
  ObjAλ (g ∗ ◦ fθ) = inf g∈GS ObjAλ (g ◦ fθ) = Obj A λ (0)
  Choose another λ′ ≥ 0 (can equal λ). Then there exists a g∗′ ∈ GS be the fine tuning layer such that infg∈GS Obj A λ′(g ◦ fθ) = Obj A λ′(g ∗′ ◦ fθ) and
  1
  n n∑ i=1 ‖Jg∗′◦fθ (xi)‖2 > 0
  Proof. Fix α ≥ 0 and c > α ·R. Set biases
  b1 =  c 0 ... 0  bj = 0 , j ≥ 2 and weights
  W 1 =  α 0 . . . 0 0 0 . . . 0 ... ... ...
  ... 0 . . . . . . 0
   W j =  1 0 . . . 0 0 0 . . . 0 ... ... ...
  ... 0 . . . . . . 0  , j ≥ 2 Define xi,j be the jth entry of the data point xi. Define
  αi := α · xi,1
  α := 1
  n d∑ i=1 αi
  y := 1
  n d∑ i=1 yi
  Now we observe that for a fixed λ ≥ 0 and any g ∈ GS , we have that
  ObjAλ (g ◦ fθ) = R̂(g ◦ fθ) + λ · 1
  n n∑ i=1 ‖Jg◦fθ (xi)‖2
  = 1
  n n∑ i=1 ∥∥∥∥∥∥∥(αxi,1 + c) g11... gd1 − yi ∥∥∥∥∥∥∥ 2
  2
  + λ · 1 n n∑ i=1 ∥∥∥∥∥∥∥∥g  α 0 . . . 0 0 0 . . . 0 ... ... ... ... 0 . . . . . . 0  ∥∥∥∥∥∥∥∥
  2
  = 1
  n n∑ i=1 ‖(αi + c)g1 − yi‖22 + λ · 1 n n∑ i=1 α ‖g1‖2
  = 1
  n n∑ i=1 ‖(αi + c)g1 − yi‖22 + λ · α ‖g1‖2
  Therefore,
  inf g∈GS
  ObjAλ (g ◦ fθ)
  is equivalent to solving
  inf w∈Rd : ‖w‖2≥δ
  1
  n n∑ i=1 ‖(αi + c)w − yi‖22 + λ · α ‖w‖2 (25)
  Utilizing lagrange multipliers, we find the minimizer is
  w = δ · y ‖y‖
  (26)
  when c ≥ ‖y‖2δ . Now consider the function
  S(c, α) = 1
  n n∑ i=1 ‖(α · xi,1 + c)g1 − yi‖22 + λ · α ‖g1‖2
  Note that this function is continuous with respect to the input (c, α). Now fix α = 0, c = ‖y‖2δ . Set w = δ · y‖y‖ . Then we have that
  S( ‖y‖2 δ , 0) = 1 n n∑ i=1 ‖y − yi‖22 < 1 n n∑ i=1 ‖yi‖22 = Obj A λ (0)
  The inequality comes from the fact that we assumed y 6= 0 and noting that y is the minimizer of the function p(z) = 1n ‖z − yi‖ 2 2. Continuity of S ensures that there exists α0 > 0 such that
  S( ‖y‖2 δ , α0) < 1 n n∑ i=1 ‖yi‖22 = Obj A λ (0)
  Now consider U(t) = S((1 + t)‖y‖2δ , (1 + t)α0) for t ≥ 0. Note that U is continuous with respect to t. Furthermore, we note that t → ∞ implies U(t) → ∞ which implies there exists some time t = Tf such that U(Tf ) > ObjAλ (0). Therefore, by the intermediate value theorem, there exists a time t = T such that U(T ) = ObjAλ (0). Finally, set c = (T + 1) ‖y‖2 δ , α = (T + 1)α0, and g
  ∗ as the matrix where g∗1 = δ · y ‖y‖ and 0 for the other columns. By equation 25 and equation 26 we have
  ObjAλ (g ∗ ◦ fθ) = inf g∈GS ObjAλ (g ◦ fθ) = U(T ) = Obj A λ (0)
  Furthermore, if we choose another λ′ ≥ 0, since c = (T + 1)‖y‖2δ > ‖y‖2 δ by equation 26, we have that
  ObjAλ′(g ∗′ ◦ fθ) = inf g∈GS ObjAλ′(g ◦ fθ)
  and
  1
  n n∑ i=1 ‖Jg∗′◦fθ (xi)‖2 = α ∥∥g∗′∥∥ 2 = αδ
  which is nonzero as δ > 0 and α = (T + 1)α0 > 0.
  Clearly, we have FAλ2 ⊂ F A λ1 . If we can show that fθ1 6∈ FAλ2 then we have F A λ2 ( FAλ1 .
  Using lemma C.1 we can find fθ1 ∈ FAλ1 such that
  inf g∈GS
  ObjAλ1(g ◦ fθ1) = Obj A λ1(0)
  In addition lemma C.1 guarantees minimizers g∗1 and g ∗ 2 such that
  ObjAλ1(g ∗ 1 ◦ fθ1) = inf g∈GS ObjAλ1(g ◦ fθ1) and
  1
  n n∑ i=1 ∥∥Jg∗1◦fθ (xi)∥∥2 > 0 ObjAλ2(g ∗ 2 ◦ fθ1) = inf
  g∈GS ObjAλ2(g ◦ fθ1) and
  1
  n n∑ i=1 ∥∥Jg∗2◦fθ1 (xi)∥∥2 > 0 Thus, we have that
  ObjAλ1(g ∗ 2 ◦ fθ1) = R̂(g∗2 ◦ fθ1) + λ2 ·
  1
  n n∑ i=1 ∥∥Jg∗2◦fθ1 (xi)∥∥2 > R̂(g∗2 ◦ fθ1) + λ1 · 1
  n n∑ i=1 ∥∥Jg∗2◦fθ1 (xi)∥∥2 since λ2 > λ1 ≥ R̂(g∗1 ◦ fθ1) + λ1 · 1
  n n∑ i=1 ∥∥Jg∗1◦fθ1 (xi)∥∥2 def of g∗1 = ObjAλ1(0) lemma C.1
  Thus fθ1 6∈ FAλ2 which implies F A λ2 ( FAλ1 . It remains to show for λ1 ≥ 0, we have that F A λ1 ( F .
  Consider any g ∈ GS . For j ∈ [L], define W j as the weight matrix where W j = Id×d (identity matrix) for j ∈ [L − 1] and let the final weight WL = B · Id×d for some constant B > 0. Set the bias vectors bj = 0 for j ≥ 2. Let the first bias equal b1 = R · 1 where 1 is the vector of all 1’s and R is the upper bound such that ‖x‖∞ ≤ R. Set θ = (W 1, b1, . . . ,WL, bL) and let hθ = g ◦ fθ We compute
  ObjAλ1(hθ) = R̂(hθ) + λ1 · 1
  n n∑ i=1 ‖Jhθ (xi)‖2
  = 1
  n n∑ i=1 ‖B(xi +R1)− yi‖2 + 1 n n∑ i=1 ‖Jhθ (xi)‖2
  = 1
  n n∑ i=1 ‖B(xi +R1)− yi‖2 +B ‖g‖2
  ≥ 1 n n∑ i=1 ‖B(xi +R1)− yi‖2 +Bδ
  We note that sending B → ∞ we get ObjAλ1(hθ) → ∞ which implies that there exists a B = B ′ such that ObjAλ1(hθ) > Obj A λ1(0). Setting B = B ′ implies fθ 6∈ FAλ1 .
sections.heading: D EXTRA EXPERIMENT RESULTS
sections.heading: D.1 ABSOLUTE TRANSFERABILITY
sections.text: We show the results with absolute transferability in Figure 7,8,9 and 10 respectively.
sections.heading: D.2 RESULTS OF OTHER MODEL STRUCTURES
sections.text: To further validate our evaluation results, we evaluate the experiments on another model structure. We use a simpler CNN model for CIFAR-10 to SVHN and a more complicated WideResNet-50 for ImageNet to CIFAR-10. The CNN model consists of four convolutional layer with 3×3 kernels and 32,32,64,64 channels respectively, followed by two hidden layer with size 256. A 2×2 max pooling is calculated after the second and fourth layer. Other settings are the same as in the main text. Note that in some settings the new model cannot converge, and therefore we will omit the result. In addition, Jacobian regularization cannot be applied on WideResNet-50 because of the large memory cost, so we do not include it in the figures. The results are shown in Figure 11, 12 and 13.
sections.heading: D.3 DATA AUGMENTATIONS THAT VIOLATE SUFFICIENT CONDITION
sections.text: We study rotation and translation, the two data augmentations that violate the sufficient condition for regularization. The result is shown in Figure 14. We observe that these augmentations do not have an obvious impact on domain transferability.
sections.heading: D.4 ROBUSTNESS EVALUATION WITH AUTOATTACK
sections.text: Besides PGD attack, we also evaluate the model robustness using the stronger AutoAttack. We use APGD-CE, APGD-T and FAB-T as the sub-attacks in AutoAttack with 100 steps. Since the accuracy will decrease after the stronger attack, we use a slightly smaller = 0.2 to better visualize the trend. The results are shown in Fig. 15. We can observe that the trend is similar with what we observed before when we used the PGD attack - domain generalization is an effect of regularization and data augmentation, and it is sometimes negatively correlated with model robustness. Also,
  augmentations like rotation and translation, which violates the sufficient condition, do not improve the domain generalization.