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.

summaries: 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.

summaries: 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.

summaries: 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.

authors:
Peter L Bartlett
Shahar Mendelson

title: Rademacher and gaussian complexities: Risk bounds and structural results

venue: Journal of Machine Learning Research,

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Fernando Pereira

title: Analysis of representations for domain adaptation

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: In 2017 ieee symposium on security and privacy (sp),

authors:
Jianbo Chen
Michael I Jordan
Martin J Wainwright

title: Hopskipjumpattack: A query-efficient decision-based attack

venue: In 2020 ieee symposium on security and privacy (sp),

authors:
Jeremy Cohen
Elan Rosenfeld
Zico Kolter

title: Certified adversarial robustness via randomized smoothing

venue: In International Conference on Machine Learning,

authors:
Nicolas Courty
Rémi Flamary
Devis Tuia
Alain Rakotomamonjy

title: Optimal transport for domain adaptation

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Terrance DeVries
Graham W Taylor

title: Dataset augmentation in feature space

venue: arXiv preprint arXiv:1702.05538,

authors:
Logan Engstrom
Andrew Ilyas
Shibani Santurkar
Dimitris Tsipras
Brandon Tran
Aleksander Madry

title: Adversarial robustness as a prior for learned representations

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Alex Hernández-Garcı́a
Peter König

title: Data augmentation instead of explicit regularization

venue: arXiv preprint arXiv:1806.03852,

title: Further advantages of data augmentation on convolutional neural networks

venue: In International Conference on Artificial Neural Networks,

authors:
Judy Hoffman
Daniel A Roberts
Sho Yaida

title: Robust learning with jacobian regularization

venue: arXiv preprint arXiv:1908.02729,

authors:
Haoshuo Huang
Qixing Huang
Philipp Krahenbuhl

title: Domain transfer through deep activation matching

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Lei Huang
Li Liu
Fan Zhu
Diwen Wan
Zehuan Yuan
Bo Li
Ling Shao

title: Controllable orthogonalization in training dnns

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Andrew Ilyas
Shibani Santurkar
Logan Engstrom
Brandon Tran
Aleksander Madry

title: Adversarial examples are not bugs, they are features

title: Rademacher penalties and structural risk minimization

venue: IEEE Transactions on Information Theory,

authors:
Clare Lyle
Marta Kwiatkowksa
Yarin Gal

title: An analysis of the effect of invariance on generalization in neural networks

venue: In International conference on machine learning Workshop on Understanding and Improving Generalization in Deep Learning,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: In International Conference on Learning Representations,

authors:
Takeru Miyato
Shin-ichi Maeda
Masanori Koyama
Shin Ishii

title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning

authors:
Krikamol Muandet
David Balduzzi
Bernhard Schölkopf

title: Domain generalization via invariant feature representation

authors:
Luis Perez
Jason Wang

title: The effectiveness of data augmentation in image classification using deep learning

venue: arXiv preprint arXiv:1712.04621,

authors:
Elan Rosenfeld
Pradeep Ravikumar
Andrej Risteski

title: An online learning approach to interpolation and extrapolation in domain generalization

venue: arXiv preprint arXiv:2102.13128,

authors:
Kevin Roth
Yannic Kilcher
Thomas Hofmann

title: Adversarial training is a form of data-dependent operator norm regularization

venue: arXiv preprint arXiv:1906.01527,

authors:
Hadi Salman
Andrew Ilyas
Logan Engstrom
Ashish Kapoor
Aleksander Madry

title: Do adversarially robust imagenet models transfer better

venue: arXiv preprint arXiv:2007.08489,

authors:
Chun-Chen Tu
Paishun Ting
Pin-Yu Chen
Sijia Liu
Huan Zhang
Jinfeng Yi
Cho-Jui Hsieh
Shin-Ming Cheng

title: Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Sebastien C Wong
Adam Gatt
Victor Stamatescu
Mark D McDonnell

title: Understanding data augmentation for classification: when to warp? In 2016 international conference on digital image computing: techniques and applications (DICTA)

authors:
Kaichao You
Ximei Wang
Mingsheng Long
Michael Jordan

title: Towards accurate model selection in deep unsupervised domain adaptation

authors:
Hongyang Zhang
Yaodong Yu
Jiantao Jiao
Eric Xing
Laurent El Ghaoui
Michael Jordan

title: Theoretically principled trade-off between robustness and accuracy

authors:
Linjun Zhang
Zhun Deng
Kenji Kawaguchi
Amirata Ghorbani
James Zou

title: How does mixup help with robustness and generalization

venue: arXiv preprint arXiv:2010.04819,

authors:
Yuchen Zhang
Tianle Liu
Mingsheng Long
Michael Jordan

title: Bridging theory and algorithm for domain adaptation

authors:
Han Zhao
Remi Tachet Des Combes
Kun Zhang
Geoffrey Gordon

title: On learning invariant representations for domain adaptation

heading: 1 INTRODUCTION

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.

heading: 2 RELATED WORK

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).

heading: 3 SUFFICIENT CONDITIONS FOR DOMAIN TRANSFERABILITY

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.

heading: 3.1 EXAMPLE: ROBUSTNESS AND TRANSFERABILITY ARE INDEPENDENT

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.

heading: 3.2 UPPER BOUND OF THE RELATIVE DOMAIN TRANSFERABILITY

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.

heading: 3.3 GENERALIZATION UPPER BOUND OF THE RELATIVE DOMAIN TRANSFERABILITY

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.

heading: 3.4 WHEN CAN DATA AUGMENTATION BE VIEWED AS REGULARIZATION?

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).

heading: 4 EVALUATION

heading: 4.1 EXPERIMENTAL SETTING

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.

heading: 4.2 RELATIONSHIP BETWEEN ROBUSTNESS AND TRANSFERABILITY UNDER CONTROLLABLE CONDITIONS

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.

heading: 5 CONCLUSIONS

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.

heading: ETHICS STATEMENT

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.

heading: REPRODUCIBILITY STATEMENT

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.

heading: A PROOFS

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.

heading: B DATA AUGMENTATION (DA) AS REGULARIZATION

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.

heading: C ADVERSARIAL TRAINING AS A REGULARIZER

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

heading: Interpretation:

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 .

heading: D EXTRA EXPERIMENT RESULTS

heading: D.1 ABSOLUTE TRANSFERABILITY

text: We show the results with absolute transferability in Figure 7,8,9 and 10 respectively.

heading: D.2 RESULTS OF OTHER MODEL STRUCTURES

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.

heading: D.3 DATA AUGMENTATIONS THAT VIOLATE SUFFICIENT CONDITION

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.

heading: D.4 ROBUSTNESS EVALUATION WITH AUTOATTACK

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.