Formulating Robustness Against Unforeseen Attacks
Authors: Sihui Dai
Saeed Mahloujifar
Prateek Mittal
Venue: NeurIPS 2022 Accept (2022)

Abstract: Existing defenses against adversarial examples such as adversarial training typically assume that the adversary will conform to a specific or known threat model, such as $\ell_p$ perturbations within a fixed budget. In this paper, we focus on the scenario where there is a mismatch in the threat model assumed by the defense during training, and the actual capabilities of the adversary at test time. We ask the question: if the learner trains against a specific ``source" threat model, when can we expect robustness to generalize to a stronger unknown ``target" threat model during test-time? Our key contribution is to formally define the problem of learning and generalization with an unforeseen adversary, which helps us reason about the increase in adversarial risk from the conventional perspective of a known adversary. Applying our framework, we derive a generalization bound which relates the generalization gap between source and target threat models to variation of the feature extractor, which measures the expected maximum difference between extracted features across a given threat model. Based on our generalization bound, we propose variation regularization (VR) which reduces variation of the feature extractor across the source threat model during training. We empirically demonstrate that using VR can lead to improved generalization to unforeseen attacks during test-time, and combining VR with perceptual adversarial training (Laidlaw et al., 2021) achieves state-of-the-art robustness on unforeseen attacks. Our code is publicly available at https://github.com/inspire-group/variation-regularization.

Formulating Robustness Against Unforeseen Attacks
Sihui Dai Princeton University s chuieoprinceton... inceton. edu
Saeed Mahloujifar Princeton University of sfarprrinceton. edu
Prateek Mittal Princeton University
pmittal@princeton edu
Abstract
Existing defenses against adversarial examples such as adversarial training typi- cally assume that the adversary will conform to a specific known threat model, such lp perturbations within fixed budget. In this paper, we focus on the scenario where there mismatch in the threat model assumed by the defense during training, and the actual capabilities of the adversary test time. We ask the question: if the learner trains against specific "source" threat model, when can we expect robustness to generalize to stronger unknown "target" threat model during test-time? Our key contribution is to formally define the problem learning and generalization with unforeseen adversary, which helps reason about the increase in adversarial risk from the conventional perspective of a known adversary. Applying our framework, eralization gap between source and target threat models to variation of the feature extractor, which measures the expected maximum difference between extracted fea- tures across given threat model. Based on our generalization bound, we propose variation regularization (VR) which reduces variation of the feature extractor across the source threat model during training. We empirically demonstrate that using VR can lead improved generalization unforeseen attacks during test-time, and combining VR with perceptual adversarial training (Laidlaw et al.) (021)) achieves state-of-the-art robustness on unforeseen attacks, Our code is publicly available ctt.iuui.coomm/iir.eee.. hrg.aaegrrogoaarraaaaiiaaaaarrra
derive generalization bound which relates the gen-
Introduction
Neural networks have impressive performance variety of datasets (LeCun al. 1998 He ctt al., 2015; Krizhevsky et al. 2017 Everingham et al. 2010) but can be fooled by imperceptible perturbations known adversarial examples (Szegedy et al. 2014). The conventional paradigm to mitigate this threat often assumes that the adversary generates these examples using some known threat model, primarily Ep balls of specific radius (Cohen et al. 2019 Zhang et al. 2020b Madry et al. 2018). and evaluates the performance of defenses based on this assumption. This assumption, however, is unrealistic in practice. In general, the learner does not know exactly what perturbations the adversary will apply during test-time.
To bridge the gap between the setting of robustness studied in current adversarial MI. research and robustness practice, we study the problem of learning with an unforeseen adversary. In this problem, the learner has access to adversarial examples from proxy "source" threat model but wants to be robust against a more difficult "target" threat model used by the adversary during test-time. ask the following questions:
1. When can we expect robustness on the source threat model to generalize to the true unknown target threat model used by the adversary?
2. How can we design a learning algorithm that reduces the drop in robustness from source threat model target threat model?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

To address the first question, we introduce wnforeseen adversarial generalizability which provides a framework for reasoning about what types of learning algorithms produce models that generalize well to unforeseen attacks. Based on this framework, we derive generalization bound which relates the difference in adversarial risk across source and target threat models to quantity we call variation: the expected maximum difference between extracted features across given threat model.
Our bound addresses the second question; it suggests that learning algorithms that bias towards models with small variation across the source threat model exhibit smaller drop in robustness to particular unforeseen attacks. Thus, we propose variation regularization (VR) to improve robustness to unforeseen attacks. We then empirically demonstrate that when combined with adversarial training, vR improves generalization to unforeseen attacks during test-time across multiple datasets and architectures. Our contributions are as follows:
We formally define the problem of learning with an unforeseen adversary with respect to adversarial risk. We make the case that one way of learning with an unforeseen adversary is to ensure that the gap between the empirical adversarial risk measured on the source adversary and the expected adversarial risk on the target adversary remains small. To this end, we define unforeseen adversarial generalizability which provides a framework for understanding under what conditions we would expect small generalization gap.
Under framework for generalizability, across threat models. Our bound relates the generalization gap to a quantity we define as variation, the expected maximum difference between extracted features across given threat model. We demonstrate that under certain conditions, we can decrease this upper bound while only using information about the source threat model.
derive generalization bound for generalization
Using our bound, we propose a regularization term which we call variation regularization (VR). We incorporate this regularization term into adversarial training and perceptual adversarial training (Laidlaw et al. 202T), leading to learning algorithm that we call AT-VR and PAT-VR respectively. We find that VR can lead to improved robustness on unforeseen attacks across datasets such as CIFAR- 10, C00, and ImageNette over adversarial training without VR. Additionally, PAT-VI VR achieves state-of-the-art (SOTA) robust accuracy LPIPS- attacks, improving over PAT by 21% and SOTA robust accuracy on a union of loc, f2, spatially transformed (Xiao et al. 2018), and recolor attacks (I (Laidlaw & Feizi 2019).
2 Related Works
Adversarial examples and defenses Previous studies have shown that neural networks can be fooled by perturbations known as adversarial examples, which are imperceptible to humans but cause NNs to predict incorrectly with high confidence (Szegedy et al. 2014). These adversarial examples can be generated by various threat models including l, perturbations, spatial transformations (Xiao et al.) 2018), recoloring (Laddlaw & Feizi] 2019). and broader threat models such as fog and snow distortions (Kang et al., 2019). While many defenses have been proposed, most defenses provide guarantees for specific threat models (Cohen et al. 2019; Zhang et al. 2020b; Croce & Hein 2020a| Yang et al.
2020 Zhang et al. 2020a) or use knowledge of the threat model during training Maddy et al., 2018)]
Zhang et al. [019 Wu et al. 2020a Tramer & Boneh 2019 Maini et al. 2020). Adversarial training
a popular defense framework in which a model trained using adversarial examples generated
by particular threat model, such as l2 or ex attacks (Madry et al., 2018 Zhang et al. 22199] Wu
jet al. (2020a). Prior works have also extended adversarial training to defend against unions of attack
types such as unions of ba-balls (Maini et al. 2020 Tramèr & Boneh 2019) and against stronger adversaries more aligned to human perception (Laidlaw et al.] 20211)
Bounds for Learning with Adversarial Examples An interesting body of work studies generaliza- tion bounds for specific attacks Cullina et al. (2018); Attias al. (2019); Montasser et al. (2019);
Raghunathan et al. (2019;; Chen et al. (2020); Diakonikolas et al. (2019) Yu et al. (2021 Diochnos et allaa.22.0) (2019). In particular, they study generalization in the setting where the learning algorithm minimizes the adversarial risk on the training set and hopes to generalize to same adversary during test-time. MMntasser et al. (202T) provide bounds for the problem of generalizing to an unknown adversary with oracle access to that adversary during training. Our work differs since we study generalization and provide bounds under the setting in the learner only has access to samples from a weaker adversary than present at test-time.
2

---

"Unforeseen" attacks and defenses While several prior works have studied "unforeseen" attacks (Kang et al., 2019] Stutz et al. 2020: Laidlaw al.] 202T; Jin & Rinard, 2020), these works are empirical works, and the term "unforeseen attack" has not been formally defindd. [Kan et al. (2019) first used the term "unforeseen attack" when proposing set of adversarial threat models including Snow, Fog, Gabor, and JPEG to evaluate how well defenses can generalize from fox and &g to broader threat models. Stutz et al. (020)) and Chen et al. (002) propose adversarial training based techniques with mechanism for abstaining stronger attacks including lp attacks of larger norm. Other defenses against "unforeseen attacks" consider them to be attacks that are not used during training, but not necessarily stronger than those used in training. For instance, Laidlaw et al. (022)) propose using LPIPS (Zhang et al. 2018), a perceptually aligned image distance metric, to generate adversarial examples during training. They demonstrate that by training using adversarial examples using this distance metric, they can achieve robustness against variety of adversarial threat models including fac, l2, recoloring, and spatial transformation. However, the LPIPS attack is the strongest out of all threat models tested and contains large portion of those threat models. To resolve these differences in interpretation of "unforeseen attack", we provide a formal definition of learning with an unforeseen adversary.
certain inputs to improve generalization from training on Loc to
Domain Generalization A problem related to generalizing to unforeseen attacks is the problem of domain generalization under covariate shift. In the domain generalization problem, the learner has access to multiple training distributions and has the goal of generalizing to unknown test distribution. (Albuquerque et al. 2019) demonstrate that when the test distribution lies within a convex hull of the training distributions, learning is feasible. (Ye et al. 2021) propose theoretical framework for domain generalization in which they derive a generalization bound in terms of the variation of features across training distributions. We focus the problem of generalizing to unforeseen adversaries and demonstrate that a generalization bound in terms of variation of features across the training threat model exists.
3 Adversarial Learning with an Unforeseen Adversary
Notations We use = (X, y) to denote the data distribution and Dm to denote a dataset formed by m iid samples from D. We use X to denote the support of X. To match learning theory literature, we will refer to the defense as a learning algorithm AA, which takes the adversarial threat model and training data as inputs and outputs the learned classifier (f A(S.. Dm) where S is the threat model). We use denote the function class that A is applied over and A(S, Dm) F. F Go H. denotes a function class where of E F, f g h where g E G. h E H.
In this section, we will define what constitutes unforeseen attack and the learner's goal in the presence of unforeseen attacks. We then introduce unforeseen adversarial generalizability which provides framework for reasoning about what types of learning algorithms give models that generalize well to unforeseen adversaries.
3.1 Formulating Learning with an Unforeseen Adversary
To formulate adversarial learning with an unforeseen adversary, we begin by defining threat model and adversarial risk. We will then use these definitions to explain the goal of the learner in the presence of an unforeseen adversary.
Definition 3.1 (Threat Model). The threat model defined by a neighborhood function N(.) : X (0. 1)x. For any input E X, (z) contains x.
Definition 3.2 (Expected and Empirical Adversarial Risk). We define expected udversarial risk for a model f with respect to threat model N as Lx (f) B(EA))D max ((f(x') y) where & is a loss function. In practice, we generally do not have access to the true data distribution D, but have m iid samples {xx,, 34) We can approximate L (f) with the empirical adversarial risk defined as Lx( T7 Em (a {( vi)
In adversarial learning, the learner's goal is to find function f E F that minimizes Lr where T threat model used by the adversary. We call the target threal model. We call the threat model that the learner has access to during training the source threat model. We divide the adversarial learning problem into cases, learning with a foreseen adversary and learning with an unforeseen adversary. To distinguish between these 2 cases, we first define the subset operation for threat models.
3

---

Definition 3.3 (Threat Model Subset and Superset), We call threat model S subset of another threat model T (and T a superset S) S(x) _ T() almost everywhere in X. We denote this as S S T (or T 2 S). If (ax) C ((x) almost everywhere in X. then we call S a strict subset of 'T (and strict superset of S) and denote this as S c (or 7 C S).
Learning with Foreseen Adversary In learning with a foreseen adversary. the target threat model T is subset of the souree threat model (T' _ S). The learner has access S and dataset Dm of m iid samples from the data distribution D. The learner would like to use learning algorithm AA for which f = A(S, Dm) achieves Lr (f) c for some small > The learner cannot compute (fr, but can compute (f) 2 (f). This setting of learning with a foreseen adversary represents when the adversary is weaker than assumed by the learner and since [s(f) (f)), which means that as long as the learner can achieve (f( < e, then they are guaranteed that LT( <.
Learning with an Unforeseen Adversary In learning with an unforeseen adversary, the target threat model T is a strict superset of the source threat model S (T C S). this setting, we call T an unforeseen adversary. The learner has access to S and dataset Dm of m iid samples from the data distribution D. The learner would like to use a learning algorithm A for which f = A(S, Dm) achieves Lr( < for some small > O. This setting of learning with an unforeseen adversary represents when the adversary is strictly stronger than assumed by the learner. Compared to learning with foreseen adversary, this problem is more difficult since (f) may not be reflective of L1 (f). By construction (f( 2 (f). but is unclear how much larger Ly (f) is. When can we guarantee that Lr(f) ) is close to Ls)))? We will address this question in the Section 3.2 when we define threat model generalizability and Section when we provide a bound for (f) Ls(s).
3.2 Formulating Generalizability with an Unforeseen Adversary
How should we define A that performs well against an unforeseen adversary? One way is to have f - A(S, Dm) achieves small [f( (which can be measured by AA while ensuring that [.s()) is close to (f). This leads us the following definition for generalization gap.
Definition 3.4 (Generalization Gap). For threat models S and T, the generalization gap is defined as
Lr(f) - Lf( We observe that
Lr(f) Ls(f)= Lr(f)-
-r())=
Ls(f) - Ls(
threat model generalization gap
sample generalization gap
We note that in the special case of learning with a foreseen adversary,
- Lss)) S 0. so
Lr(S) - LJ)) s Ls(f) (s()) and bounding the generalization gap be achieved by bounding the sample generalization gap, which has been studied by prior works (Attias et al. 2019 Raghunathan ct al. 2019, Chen et al. 2020 Yu et al. 202T).
We would like to ensure that the generalization gap is small with high probability. We can achieve this by ensuring that both the sample generalization gap and threat model generalization gap are small. This leads us to define robust sample generalizability and threat model generulizability which describe conditions necessary for us to expect the respective generalization gaps to be small. We then combine these generalizability definitions and define unforeseen adversarial generalizability which describes the conditions necessary for a learning algorithm to be able to generalize to unforeseen attacks.
Definition 3.5 (Robust Sample Generalizability). A learning algorithm A robustly (e(-), 8) sammle generalizes across function class F threat model S where e: N + R= if for any distribution DD when running A on m iid samples D. from D, we have
(ALS(A(S, Dm.)) S Ls(A(S, Dm.)) +(mm] 2 1-6
Definition 3.5 implies that any learning algorithm that (e(:), -obbussy sample generalizes across chosen hypothesis class JF with e(m) << 1,8 << 1, we can achieve small sample generalization gap with high probability.
We now define generalizability for the threat model generalization gap.
Definition 3.6 (Threat Model Generalizability). Let S be the source threat model used by the learner. A learning algorithm A (e(::)..))-robusty generalizes to target threat model T' where

---

N + + foot and ó E [0, 1] if for any data distribution D and any training dataset D. c:TxN
with m iid samples from D. we have:
FILT(A(S, Dm)) S Ls(A(S, Dm)) + m(T, 2 8
We note that the (.nnnitioon3.coosiiiiiii
generalization to a given T, which does not fully account for the unknown nature of T, since from the learner's perspective, the learner does not know which threat model wants Lr to be small for. We address this the following definition where we combine Definitions 3.5 a.6 define generalizability to unforeseen adversarial attacks.
Definition 3.7 (Unforeseen Adversarial Generalizability). A learning algorithm on function class FF with source adversary S, (c(-:)). -robuusstlyy generalizes to unforeseen threat models where e: N X + R+ [oo} if there exists c1, 62 with 61 (m) + (T, m) I <(T, m) such that A robustly (ei, (11,6))ssmlll generalizes and (e2, 8) --oobutyy generalizes to any threat model T.
We remark that in Definition 3.7 is function of T, which accounts for differences in difficulty of possible target threat models. Ideally, we would like c(T, m) at sufficiently large m to be small across a set of reasonable threat models T (ie. imperceptible perturbations) and expect it to be large (and possibly infinite) for difficult or unreasonable threat models (ie. unbounded perturbations).
Generalization Bound for Unforeseen Attacks
While prior works have proposed bounds on sample generalization gap (Attias et al. 2019 Raghu nathan et al., 2019: Chen et al., 2020] Yu et al.) (02I), to the best of our knowledge, prior works have not provided bounds on threat model generalization gap. In this section, we demonstrate that we can bound the threat model generalization gap in terms of quantity we define as variation, the expected maximum difference across features learned by the model across the target threat model. We then show that with the existence of an expansion function, which relates source variation to target variation, any learning algorithm which with high probability outputs model with small source variation can achieve small threat model generalization gap.
4.1 Relating generalization gap variation
We now consider function classes of the form F = G o H where Vg EG RR + RK is a top level classifier into K classes and Aı E H, h X IRd is d-dimensional feature extractor. Since the top classifier is fixed for a function S. if i, i E [1...]] fluctuates a lot across the threat model à (xx), then the adversary can manipulate this feature to cause misclassification. The relation between features and robustness has been analyzed by prior works such as (Ilyas et al.) [011 Tsipra al., 2019 Tramér& & Boneh, 2019). We now demonstrate that we can bound the threat model generalization gap in terms of measure of the fluctuation of h across T, which we call variation. Definition 4.1 (Variation). The variation of feature vector h(.)) : X Rdd across threat model N is given by
(h,, N) (e..))DD max
21)2)EN(2) [|M(x)) h(22)112
Theorem 4.2 (Variation- Based Threat Model Generalization Bound). Let S denote the source threat model and 'D denote the data distribution. Let F = G o H where G is a class of Lipschitz classifiers with Lipschitz constant upper bounded by og. Let the loss function be p-Lipschitz. Consider a learning algorithm A over F and denote f = A(S, Dm) ) g h. If with probability 1 1 - over the randomness of D.. V(h, ,, T) 2 <(T, m)) where e: T + R+ U [oo), then A (poge(T, m), 6)- robustly generalizes from S to T.
Theorem shows we can bound the threat model generalization gap between any source S and unforeseen ad adversary T' in terms of variation across T. With regards to Definition 3.6] Theorem 4.2 suggests that any learning algorithm over F that with high probability outputs models with low variation on the target threat model can generalize well to that target.
4.2 Relating source and target variation
Since the learning algorithm A cannot use information from T, it is unclear how to define such A that achieves small (hh, T). We address this problem by introducing the notion of an expansion function, which relates the source variation (which can be computed by the learner) target variation.
5

---

Definition 4.3 (Expansion Function for Variation (Ye et al. 2021)). A function s IR U (0) +
F. U {0, +o0} an expansion function relating variation across source threat model to target threat model 7 if the following properties hold:
1. s()) is monotonically increasing and s(x) 2 I, Vr
2. lim s(z)
s0)
3. For all h that can be modeled by function class F, (V((h,)) 2 V(h,
When expansion function for variation from S to T exists, then we can bound the threat model generalization gap in terms of variation on S. This follows from Theorem 4.2 and Definition 4.3
Corollary 4.4 (Source Variation-Base source threat model and D denote the data distribution. Let F = G H. where G is a class of Lipschitz classifiers with Lipschitz constant upper bounded by ag. Let the loss function be p-Läpschitz. Let T be any unforeseen threat model for which an expansion function 8 from S to T exists. Consider learning algorithm A over F and denote
Threat Model Generalization Bound), Let S denote the
=A(S, Dm) 9 h. If with probability 1 g over the randomness of Dm- s(V(h, 5)) S <(T, where c T N +R+ {o0), then A (Tagge(T, m), r-oouusyyyy generalizes from S T.
Corollary 4.4 allows us to relate generalization across threat models of model f = goh to s( S)) instead of Vh, T)- While this expression is still dependent the target threat model T (since is dependent on T), we can reduce s( (V S)) without knowledge of due to the monotonicity of the expansion function. Thus, provided that expansion function exists, we regularization in order to ensure that our learning algorithm actively chooses models with low source variation. This result leads to the question: when does the expansion function exist?
techniques such as
4.3
When does the expansion function exist?
We now demonstrate a few cases in which the expansion function exists or does not exist. We begin by providing basic examples of source threat models S and target threat models T without constraints on function class.
Proposition 4.5. When S = T, expansion function s exists and is given by s(x) =
Proposition 4.6. Let == {x), and T be a threat model such that S C T. Then, for all feature extractors h, have that V (h, expansion function exists such that s (V,, 2 T),
while Vhh, T) can be greater than O. In this case, no
While we did not consider constrained function class in the previous two settings, the choice of function class can also impact the existence of an expansion function. For instance, in the setting of Proposition 4.6, if we constrain F to only use feature extractors with constant output, then the expansion function s(x) = x is valid. We now consider the case where our function class F uses linear feature extractors and derive expansion functions for E, adversaries.
Theorem 4.7 (Linear feature extractors with l, threat model (p E Nu +oo)).. Let imputs x E RR and corresponding label y E [L...K]. Consider S(z) = {él || - lp S e1 and )2) with p.q q E N PP: > O. Define target threat model T(x) = S(x) (z).. Consider a linear feature extractor with bounded condition number: h (Wx b/W E Rdxn, b Rd
{+l - S
amaee (W)
Oiin (W) S
B < oo). Then, an expansion function exists and is linear.
Theorem 4.7 demonstrates that in the case of linear feature extractor linear expansion function exists for any data distribution from a source É, adversary to a union of l, adversaries. This result suggests that with a function class using linear feature extractors, we can improve generalization to l, balls with larger radii by using a learning algorithm that biases towards models with small Vhh, S). We demonstrate this in Appendix D where we experiment with linear models on Gaussian data. We also provide visualizations of expansion function for nonlinear model (ResNet-18) on CIFAR-10 in Section[5.6
5 Adversarial Training with Variation Regularization
Our generalization bound from Corollary suggests that learning algorithms that bias towards small source variation improve generalization to other threat models when an expansion function exists.

---

In this section, we propose adversarial training with variation regularization (AT-VR) to improve generalization unforeseen adversaries and evaluate the performance of AT-VR on multiple datasets and model architectures.
5.1 Adversarial training with variation regularization
To integrate variation into AT, we consider the following training objective:
min JEFJ=ggh Y
v(((2)) 2' (x()))
max
max af ES(a)
11/(z') ((2")lla]
empirical adversarial risk
empirical variation
where À 2 O is the regularization strength. For the majority of our experiments in the main text, we the objective of PGD-AT (Madry et al.] (018)) as the approximate empirical adversarial risk. We note that this can be replaced with other forms of AT such as TRADES (Zhang et al. 2019). We can approximate empirical variation by using gradient- baddee methods. For example, when (xx) is a lp ball around z, we compute the variation term by using PGD to simultancously optimize over 2 and T2. We discuss methods for computing variation for other source threat models in Appendix E.
5.2 Experimental Setup
We investigate the performance of training neural networks with AT- on image data for a variety of datasets, architectures, source threat models, and target threat models. We also combine VR with perceptual adversarial training (PAT) (Laidlaw et al. 2021) the current state-of-the-art for unforeseen robustness, which uses source threat model based
LPIPS (Zhang al.
2018) metric.
Datasets We train models on CIFAR-IO, CIFAR-I00, Krizhevsky et al.
2009) and ImageNette
(Howard). ImageNette is a 10-class subset of ImageNet Deng et al. 2009).
Model architecture On CIFAR-10 -0,, we train ResNet-18 (He et al. 2016). WideResNee(WRRNN-2) 10 Zagoruyko & Komodakis, 2016), and VGG-16 (Simonyan & Zisserman, 2015) architectures. On ImageNette, we train ResNet-18 (He et al., 2016). For PAT-VR, we use ResNet-50. For all architectures, we consider the feature extractor h to consist of all layers of the NN and the top level classifier g to be the identity function. We include experiments for when we consider h to be composed of all layers before the fully connected layers in Appendix [F]
Source threat models Across experiments with AT-VR, we consider 2 different source threat models: & Loo perturbations with radius 255 and & perturbations with radius 0.5. For PAT-VR, we use LPIPS computed from an AlexNet model (Krizhevsky et al. 2017) trained on CIFAR-IO. We provide additional details about training procedure in Appendix C We also provide results for additional source threat models such as StAdv and Recolor in Appendix
Target threat models We evaluate AT-VR on a variety of target threat models including, & adversaries (foc, f2, and & adversaries), spatially transformed adversary (StAdv) (Xiao et al.) [2018). and Recolor adversary (Laidlaw & Feizi, 2019). For StAdy and Recolor threat models, we use the original bounds from (Xiao et al., 20188 and (Laidlaw & Feizi 2019) respectively. For all other threat models, we specify the bound (e) within the figures in this section. We also provide evaluations on additional adversaries including Wasserstein, JPEG, elastic, and LPIPS based attacks Appendix E.7 for CIFAR-10 10 ResNet-18 18 models.
Baselines We remark that we studying the setting where the learner has already chosen source threat model and during testing the model is evaluated on a strictly larger unknown target. Because of this, for AT VT experiments, we standard PGD-AT (Madry et al.) 2018) (AT-VI VR with X 0) as a baseline. For PAT-VR experiments, we use PAT (PAT-VR with À 0) as a baseline. We note that VR can be combined with other training techniques such TRADES (Zhang et al. 2019) and provide results in Appendix E.9
5.3 Performance of AT-VR across different imperceptible target threat models
We first investigate the impact of AT-VR on robust accuracy across different target threat models that are strictly larger than the source threat model used for training. To enforce this, we evaluate robust accuracy target threat model that is the union of the source with a different threat model. For
7

---

Union with Source
Dataset
Architecture
Source
X
Clean
Source
8oo
P2
StAdv
Re-
Union
acc
acc
200
.22
color
all
CIFAR-I0
R8
E2
0
88,49
66.65
6,44
34.72
0.76
66.52
0.33
CIFAR-I0
ResNec-118
82
85.21
67.38
13.43
40.74
34,40
67.30
11.77
CIFAR-10
ResNer-118
foo
0
82.83
47.47
28.09
24.94
4.38
47.47
2.48
CIFAR-10
R8sNet-18
Eso
0.5
72.91
48.84
33,69
24.38
18.62
48.84
12.59
CIFAR-10
WRN-28- 10
Eoo
0
85.93
49.86
28.73
20.89
2.28
49.86
1.10
WRN-28-10
Eso
0.7
72.73
49.94
35.11
22.30
25.33
49.94
14.72
CIFAR-10
VGG-16
Lso
0
79.67
44.36
26.14
30.82
7.31
44,36
4.35
CIFAR-10
VGG-16
Foo
0.1
77.80
45,42
28.41
32.08
10.57
45.42
6.83
mageNette
R8
82
0
88,94
84,99
0.00
79.08
1.27
72.15
0.00
ImageNette
ResNet-18
82
85.22
83.08
9,53
80.43
18.04
75.26
6,80
ImageNette
RcsNet-18
Roo
0
80.56
49.63
32.38
49.63
34.27
49.63
25.68
ImageNette
ResNet-18
Eso
0.1
78.01
50.80
35,57
50,80
42.37
50,80
31.82
CIFAR-100 100
ResNet-18
E2
0
60.92
36.01
3.98
16.90
1.80
34.87
0.40
CIFAR- 100
R8
82
0.75
$1.53
38.26
11.47
25.65
5.12
36,96
3.11
CIARR 100
R8
2oo
0
54.94
22.74
12.61
14.40
3,99
22.71
2.42
CIFAR- 100
R8
Foo
0.2
48.97
25.04
16.48
15.82
4.96
24.95
3.48
Table 1: Robust accuracy of various models trained at different strengths of VR applied on logits on
various threat models. À = represents the baseline (standard AT). The "source acc" column reports the accuracy on the source attack (f... 203 f2, 0.5). For each individual threat model, we evaluate accuracy on a union with the source threat model. The union all column reports the accuracy on the union across all listed threat models.
8
to and lz attacks, we measure accuracy using AutoAttack (Croce & Hein 2020a). which reports the lowest robust accuracy out of different attacks: APGD-CE, APGD-T, FAB-T, and Square. For 12 and 1 for evaluating unforeseen robustness. 255
lo and & threat models, we use radius We report clean accuracy, source accuracy (robust accuracy on the source threat model), and robust accuracy across various targets in Table We present results with additional strengths of VR in Appendix E.5
AT-VR improves robust accuracy on broader target threat models. We find that overall across datasets, architecture, and source threat model, using AT-VR improves robust accuracy on unforeseen targets but trades off clean accuracy. For instance, we find that on CIFAR-10, 10, our ResNet- 18 model using VR improves robustmess on the union of all attacks from 2.48% 12.59% for loo source and from 0.33% to 11.77% for lg. The largest improvement we observe is a 33.64% increase in robust accuracy for the ResNet-15 18 CIFAR-10 with & source model on the StAdv target.
AT-VR maintains accuracy on the source compared to standard AT, but trades off clean accuracy. We find that AT-VR is able to maintain similar source accuracy in comparson standard PGD AT but consistently trades off clean accuracy. For example, for WRN-28-10 on CIFAR-10, we find that source accuracy increases slightly with VR (from 49.86% 49.9499999 94%), ) but clean accuracy drops from 85.93% to 73.73%. In Appendix E.5 where we provide results on additional values of regularization strength (A), we find that increasing generally trades off clean accuracy but improves union accuracy. We hypothesize that this tradeoff occurs because VR enforces the decision boundary be smooth, which may prevent the model from fitting certain inputs well.
5.4 State-of-the-art performance with PAT-VR
We now combine variation regularization with PAT. We present results in Table 2
Source
Clean acc
foc
8g
StAdy
Re- color
Union
PPGD
LPA
255
0.5
0
86.6
38.8
44.3
5.8
60.8
2.1
16.2
2.2
0.5
0.05
86.9
34.9
40.6
9.4
64.6
3.7
21.9
2.2
0.5
0.1
85.1
31.4
37.1
44,9
80.5
24.9
48.7
29.7
10
0
71.6
28.7
33.3
64.5
67.5
27.8
26.6
9.8
0.05
72.1
29.5
34.8
59.6
69.7
28.2
56.7
18.5
0.1
72.5
29.4
35.1
61.8
70.7
28.8
56.9
30.8
Table 2: Robust accuracy of ResNet-50 models trained using AlexNet-based PAT-VR with e = 0.5
and 1. A = 0 corresponds to standard PAT, The union column reports the accuracy obtained on the union of f. l2, StAdv, and Recolor adversaries. The PPGD and IPA columns report robust accuracy under AlexNet-based PPGD and IPA attacks with < = 0.5.
8

---

PAT-VR achieves state-of-the-art robust accuracy on AlexNet-based LPIPS aftacks (PPGD and LPA), Laidlaw et al. (202T) observed that LPA attacks are the strongest perceptual attacks, and that standard Alexeet-base PAT with source
1 can only achieve 9.8% robust accuracy on LPA attacks with 0.5. comparison, we find that applying variation regularization can significantly improve over performance on LPIPS attacks. In fact, using variation regularization strength À 0.1 while training with = 0.5 can achieve 29.7% robust accuracy on LPA, while training with 0.1 and improves LPA accuracy to 30.8%.
PAT-VR achieves state-of-the-art union accuracy across fac E2, StAdv, and Recolor attacks. We observe that as regularization strength À increases, union accuracy also increases. For source c = 0.5, we find that union accuracy increases from 2.1% without variation regularization to 24.9% with variation regularization at X = 0.1. For source = 1. we observe a 1% increase in union accuracy 0.1. However, this comes at trade-off with accuracy on specific threat models.
from = 0 For example, when training with 0.5, we find that variation regularization at X = 0.1 trades off aceuracy on fe and lg sources (7.4% and 7.2% drop robust accuracy respectively), but improves robust accuracy StAdv attacks from 5.8% to 44.9%. Meanwhile, for = 1, we find that at X = 0.1, variation regularization trades off accuracy on StAdv to improve accuracy across foor E2, and Recolor threat models.
Unlike AT-VR, PAT-VR maintains clean accuracy in comparison PAT. We find that PAT VR generally does not trade off additional clean accuracy in comparison to PAT. In some cases (at source e 1), increasing variation regularization strength can even improve clean accuracy.
5.5 Influence of AT-VR on threat model generalization gap across perturbation size
Target
Target
Target
3
2
0.04
0.0G
0.08
0.5
1.0
1.5
2.0
10
15
20
Target
Target
Target
0.05
Figure 1: Threat model generalization gap of ResNet-18 models on CIFAR-10 trained using AT-VR regularization strength À measured on target Lp. p = {oo, 1} adversarial examples with radius The generalization gap is measured with respect to cross entropy loss. All models are trained with source Lo perturbations of radius 255 generalization gap across c.
We find that increasing VR strength decreases the
In Section 5.3 we observed that AT-VR improves robust accuracy on variety of unforeseen target threat models at the cost of clean accuracy. This suggests that AT-VR VR makes the change in adversarial loss on more difficult threat models increase more gradually. verify this by plotting the gap between source and target losses (measured via cross entropy) across different perturbation strengths e for Ep threat models (p E {oo, 2, 1)) for ResNet-18 models trained on CIFAR- 10. We present results for models using AT-VR with foo source attacks in Figure [ For these experiments, we generate adversarial examples using APGD from AutoAttack (Croce & Hein 2020b). We also provide corresponding plots for &g source attacks in Appendix E.4
this section, we experimentally
We find that AT-VR consistently reduces the gap between source and target losses on Ep attacks across different target perturbation strengths e. We observe that this gap decreases as regularization increases across target threat models. This suggests that VR can reduce the generalization gap across threat models, making the loss measured on the source threat model better reflect the loss measured on the target threat model, which matches our results from Corollary
5.6 Visualizing the expansion function
The effectiveness of AT-VR suggests that an expansion function exists between across the different imperceptible threat models tested. In this section, we visualize the expansion function between toc
Valuess taken from Laidlaw et al. 2021

---

and l2 source and target pairs for ResNet-18 18 models on CIFAR-10. We train total of 15 ResNet- models using PGD-AT with and without VR on &a and fx. source threat models. We evaluate variation on models saved every 10 epochs during training along with the model saved at epoch with best performance, leading to variation computation on a total of 315 models for each source threat model.
We consider 4 cases: (1) Loo source with e 1o
8 to foo target with
255 (2) loo source
255 with = 8 253 to a target consisting of the union of the source with an l2 threat model with ra- dius 0.5, (3) & source with < = 0.5 to a target consisting of the union of the source with an &oo &
Tirget Eo Tare Veation -
Source
Venation
Source
18
10
9.5
threat model with c = 255. and (4) &g source
Varatice
Source Variatio
with = 0.5 to E2 target with = 1. In cases (2) and (3), since the target is the union of Ep balls, we approximate the variation of the union by taking the maximum variation across both Ep balls. We plot the measured source vs target vari- ation along with the minimum linear expansion function in Figure 2
Torget fs
Torget Vatuttos
1.00s
Targee Shamia
2.14
00
2.5
3.0
7.5
0UD
8-
1.0
Source Varitice
Source Vorittio
Figure 2: Plots of minimum linear expansion func- tion s shown in blue computed on 315 adversarially trained ResNet-18 models. Each grey point repre- sents variation measured on the source and target pair. Variation is computed on the logits. The two columns represent the source adversary (foc and lz respectively). The two rows represent the target adversary (foo and & respectively).
We find that in all cases the distribution of source vs target variation is sublinear, and we can upper bound this distribution with a linear expansion function with relatively small slope. Recall our finding in Theorem 4.7 that for linear models there exists a linear expansion function across f norms. We hypothesize that this property also appears for ResNet- 18 models because neural networks are piecewise linear.
6 Discussion, Limitations, and Conclusion
We highlight a limitation in adversarial ML research: the lack of understanding of how robustness degrades when mismatch in source and target threat models occurs. Our work takes steps toward addressing this problem by formulating the problem of learning with an unforeseen adversary and providing framework for reasoning about generalization under this setting. With this framework, we derive a bound for threat model generalization gap in terms of variation and use this bound to design an algorithm, adversarial training with variation regularization (AT-VR), We highlight several limitations of our theoretical results: (1) the bounds provided can be quite loose and may not be good predictors of unforeseen loss, (2) while
show that an expansion function between lp balls exists for linear models, it is unclear if that is the case for neural networks. Additionally, we highlight several limitations of AT-VR: (1) its success depends on the existence of an expansion function, (2) VR trades off additional clean accuracy and increases computational complexity of training. Further research on improving source threat models and the accuracy and efficiency of adversarial training algorithms can improve the performance of AT-VR. Finally, we note that in some applications, such as defending against website fingerprinting (Rahman et al. 2020) and bypassing facial recognition based surveillance (Shan et al., 2020),, adversarial examples are used for good, so improving robustness against adversarial examples may consequently hurt these applications.
Acknowledgments and Disclosure of Funding
We would like to thank Tianle Cai, Peter Ramadge, and Vincent Poor for their feedback on this work. This work was supported in part by the National Science Foundation under grants 155-4153337 and CNS-1704105, the ARL'S Army Artificial Intelligence Innovation Institute (A212), the Office of Naval Research Young Investigator Award, the Army Research Office Young Investigator Prize, Schmidt DataX award, and Princeton E- E-ffiliates Award. This material is also based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-2039656. Any opinions, findings, and conclusions or recommendations expressed this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
10

---

References
Albuquerque, I., Monteiro, J., Darvishi, M., Falk, T. H., and Mitliagkas, I. Generalizing to unseen domains via distribution matching, arXiv preprint arXiv:1911.00804, 2019.
Attias, I., Kontorovich, A., and Mansour, Y. Improved generalization bounds for robust learning. In Algorithmic Learning Theory, pp. 162-183. PMLR, 2019.
Carlini, N. and Wagner, D. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). Pp. 39-57. IEEE, 2017.
Chen, J., Raghuram, J., Choi, J., Wu, X., Liang, Y., and Jha, S. Revisiting adversarial robustness of classifiers with reject option. In The AAAI-22 Workshop on Adversarial Machine Learning and Beyond, 2022. RKLLattps///pppnneieee..ee// wtt.://eooooomm/aurSsrrr
Chen, L., Min, Y., Zhang, M., and Karbasi, A. More data can expand the generalization gap between adversarially robust and standard models. In International Conference on Machine Learning, pp. 1670-1680. PMLR, 2020.
Cohen, J. M., Rosenfeld, E., and Kolter, J. Z. Certified adversarial robustness via randomized smoothing. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp- 1310-1320. PMLR, 2019. URL httpp://proceedings mmr. wwwpp/ere/ccoo//ee.
http://v///cooeceeeeee wtt.:/chhencccc html
Croce, F. and Hein, M. Provable robustness against all adversarial _1_ pS-perturbations for Sp'geg IS. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020a. URL.httts://ppenrvviie net fort/forumm forfmmid-rurrllr fid=rkik YSYPB
Croce, F. and Hein, M. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free frree attacks. In International conference machine learning, pp. 2206-2216. PMLR, 2020b.
Cullina, D., Bhagoji, A. N., and Mittal, P. Pac-learning in the presence of evasion adversarics. arXiv preprint ar 1.Xiv:8806001777 2018
Deng, J., Dong, W., Socher, R., Li, L.-J,, Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and paltern recognition, pp. 248-255. leee, 2009.
Diakonikolas, I., Kane, D. M., and Manurangsi, Nearly tight bounds for robust proper learning of halfspaces with a margin. arXiv preprint arXiv: 0t1119988.333... 11335, 2019.
Diochnos, D. I., Mahloujifar, S., and Mahmoody, M. Lower bounds for adversarially robust pac learning. arXiv preprint arXiv: 19te:::9600000500 05815, 2019.
Everingham, M., Gool, L. V., Williams, C. K. I., Winn, J. M., and Zisserman, A. The pascal visual object classes (VOC) challenge. Int. J. Comput. Vis., 88(2)300--338 2010. doi: 10.1007/ sl 1263-000--2755- URL httphtttp///oo orgo 10. 101010000/11/010 009-025----------0
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In Teh, Y. W. and Titterington, D. M. (eds.), Proceedings the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, volume 9 of JMLR Proceedings, pp. 249-256 JMLR.org, 2010. htL /pprocediiggs.. mlr. ptwss/v9/ wwtp:////oooooooooo/oooogooe html
He, K., Zhang, X., Ren, S., and Sun. J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pp. 1026-1034 IEEE Computer Society, 2015. doi: 10. 101110/C/.22111.1110 123. URL.tttss://aan http://oooooooo////////// / 10. 1109/ 2015. 123
He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.

---

Howard, J. Imagenette. httLhtttp://iiiee http://gh.ggooo//ssaaaaaaaaaaaaa
Hyys, A., Santurkar, S., Engstrom, L., Tran, B., and Madry, A. Adversarial examples are not bugs, they are features. Advances in neural information processing systems, 32, 2019.
Jin, C. and Rinard, M. Manifold regularization for locally stable deep neural networks. arXiv preprint arXiv:2003.04286, 2020.
Kang, D., Sun, Y., Hendrycks, D., Brown, T., and Steinhardt, J. Testing robustness against unforeseen adversaries. arXiv preprint arXiv:1908. 08016, 2019.
Kannan, H., Kurakin, A., and Goodfellow, Adversarial logit pairing. arXiv preprint 2018.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Krizhevsky. A.. Sutskever, I,, and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Commun. ACM, 60(6):84-90, 2017. doi: 10.1145/3065386 URL http:
//doi. acoii.acmorr/100 orooooo///.. 1145/3065386
Laidlaw, C. and Feizi, S. Functional adversarial attacks. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché-Buu, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 10408-10418, 2019. URL hhtppe///procc.iigg..... pewpoceedinngnneurippo. neurips cetuurps.ccpppppeee. wwtpc/pppe////////e/eeeeeee Abstractttatt...e httml
Laidlaw, C., Singla, S., and Feizi, S. Perceptual adversarial robustness: Defense against unseen threat models. In 9th International Conference on Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL.:bttps://opeeeeeveee wttp:/iwwwweeefrrtteeeee forumiidd dFwBosAcJkNi
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(1 1:2278-23222 1998.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttps://openrevieee/ net wtt::/oormmm111-0011111311
Maini, P., Wong, E., and Kolter, J. Z.. Adversarial robustness against the union of multiple perturbation models. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Reseurch, pp. html
PMLR, 2020. htt: htt.ihttp://rroeeedine mlr, www.pseeev///aaaiii...
Montasser, O., Hanneke, S., and Srebro, N. Ve classes are adversarially robustly learnable, but only improperly. In Conference Learning Theory, pp. 2512 2512-2530. PMLR, 2019.
Montasser, O.,, Hanneke, S., and Srebro, N. Adversarially robust learning with unknown perturbation sets. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 3452-3482. PMLR, 2021. URL htlphttt//prcccedinggg mlr wtt.i/gs.m.......eeeeeemm wwlpppee/sviii m134/montasser21a html
Raghunathan, A., Xie, M., Yang, F., Duchi, J. C., and Liang, P. Adversarial training can hurt generalization. arXiv preprint arXiv:1906.0660 2019.
Rahman, M. S., Imani, M., Mathews, N., and Wright, M. Mockingbird: Defending against deep- learning-based based website fingerprinting attacks with adversarial traces. IEEE Transactions on Information Forensics and Security, 16:1594-1609, 2020.
Shan, S., Wenger, E.,, Zhang, J., Li, H., Zheng, H., and Zhao, B. Y. Fawkes: Protecting privacy against unauthorized deep learning models. In 29th USENIX Security Symposium (USENIX Security 20), pp. 1589-1604, 2020.
12

---

Simonyan, K. and Zisserman, A. Very deep convolutional networks for large-scale image recognition. In Bengio, Y. and LeCun, Y. (eds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL
bett:://rriv.... www..os/.a.........o...........o abs/ hetp//149... 1556
Stutz, D., Hein, M., and Schiele, B. confidence-calibratee adversarial training: Generalizing to unseen attacks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 1 19 of Proceedings of Machine Learning Research, pp. PMLR, 2020. URLhttp: httpattppppppppeedinnng mlr. wwtps//v19/sssutaaeeeee
html
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J.. Erhan, D., Goodfellow, I. J., and Fergus, R. Intriguing properties of neural networks. In Bengio, Y. and LeCun, Y. (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL/ttp::/arrxa //wxiv. org/ httg/bb//111.....
1312. 6199
Tramèr, F, and Boneh, D. Adversarial training and robustness for multiple perturbations. In Conference on Neural Information Processing Systems (NeurIPS), 2019. URL https://arxxt orgg/bs//900/ 13000
Tsipras, D., Santurkar, S., Engstrom, L.., Tumner, A., and Madry, A. Robustness may be at odds with accuracy. In International Conference on Learning Representations, number 2019, 2019.
Wu, D., Xia, S., and Wang, Y. Adversarial weight perturbation helps robust generalization. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020a. URL https: https::/ p/roc//ddng/oooggg//eeoo neurips. wwwppper/pppppppteetpp http:/aapr/222000 200/002220///// 1a220//ahh//ne haashh/eff9c21e1 1et.
www.ffff-sttttttratooe html
Wu, K., Wang, A., and Yu, Y. Stronger and faster wasserstein adversarial attacks. In International Conference on Machine Learning, pp. 10377-10387. PMLL 2020b.
Xiao, C., Zhu, J., Li, B., He, W., Liu, M., and Song. D. Spatially transformed adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL hhtps /ppenreview www./eeerrn/.... hett/forum?dd--yyyRRZZ
Yang, G., Duan, T., Hu, J. E., Salman, H., Razenshteyn, I., and Li, Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693-10705. PMLR, 2020.
Ye, H., Xie, C., Cai, T., Li, R., Li, 7.,, and Wang. L. Towards theoretical framework of out-of- distribution generalization. CoRR, abs/2106.04496, 2021. URL httpt:/tt///aatt www./oo//////// 04496.
Yu, Y., Yang. Z., Dobriban, E., Steinbardt, J., and Ma, Y. Understanding gencraliztion in adversarial training via the bias-variance decomposition. arXiv preprint arXiv:2 103.999777 2021.
Zagoruyko, S. and Komodakis, N. Wide residual networks. In Wilson, R. C., Hancock, E. R., and Smith, W. A. P. (eds.), Proceedings of the British Machine Vision Conference 2016, BMVC 2016, York, UK, September 19-22, 2016. BMVA Press, 2016. URL BRRLhttp// http:://www bmva. org/ wrg/bmvc.// html
Zhang, D., Ye, M., Gong, C., Zhu, Z., and Liu, Q. Black-box certification with randomized smoothing: A functional optimization based framework. Advances in Neural Information Processing Systems, 33:2316-2326. 2020a.
Zhang. H., Yu, Y., Jiao, J., Xing. E. P., Ghaoui, L. E.,, and Jordan, M. I. Theoretically principled trade- off between robustness and accuracy. Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Leurning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7482-7482. PMLR, 2019, URL BtLLhtt///ppoceeediii
mlr, www.pppes///ee.. v97/ wttpsss//////haag9pppp html
13

---

Zhang. H., Chen, H., Xiao, C., Gowal, S., Stanforth, R., Li, B.. Boning, D. S., and Hsieh, C. Towards stable and efficient training of verifiably robust neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020b. URL
Zhang, R., Isola, P., Efros, A. A., Shechtman, E., and Wang, O. The unreasonable effective- ness of deep features perceptual metric. In 2018 IEEE Conference Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT. USA. June 18-22, 2018, pp. 586- 595. Computer Vision Foundation / IEEE Computer Society, 2018. doi: 10. 10.1109/CVR..2018 00068. URL. http::/ thecvf com/ poantett_cvppp Carrasoonale__fffectieeeee wwwppeeeeeee___ess__ee_ee 2018 _atp_pppper.._ html
The
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6 for a discussion of limitations.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 6 In some applications, such as evading website fingerprinting. adversarial examples are helpful so improving defenses against them reduces their benefit in these applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are specified in the theorem statements (See Theorem 4.2 and Theorem 4.7)
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
B.2 B.3
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We provide our code in the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C for training details
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [Yes] We provide error bars for ResNet-18 models on CIFAR-10 10 with Lo source in Appendix [ but not on other experiments because of the high computational cost of adversarial training.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use publicly
available datasets such as CIFAR-10, CIFAR-100, and ImageNette as well as existing network architectures. These are cited in Section 5.2
(b) Did you mention the license of the assets? [Yes] See Section 5.2
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
14

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "sdXadK2VwN0", "reviewer": "Reviewer_PVxo", "summary": "This paper seeks to theoretically formulate the problem of learning a classifier which is robust against unseen attacks—that is, a threat model which is not used at training time. The authors define a threat model as a set of allowed perturbations to an input, and distinguish a source threat model used for training versus a target threat model used for evaluation. They characterize the target threat model as \"unseen\" if it is a strict superset of the source threat model for all inputs. Then, the generalization gap between robust error on the training set using the source threat model and robust error on a test set using the target threat model can be decomposed into a standard sample generalization term and a new threat model generalization term. The authors show that the second term can be bounded if there is an \"expansion function\" which controls how much more \"variation\" the classifier exhibits on the target threat model as compared to the source threat model, and give examples of when such an expansion function exists or does not exist. Finally, the authors propose a method AT-VR which explicitly regularizes the variation on the source threat model, which according to their theory should improve generalization to unseen threat models. They show that it does empirically improve unseen threat model accuracy across various attacks and datasets.", "questions": " * Is there any empirical explanation you can give for why the expansion function in practice is linear with low slope, even though your theory doesn't apply directly to neural networks? For instance, suppose you take the linear approximation of a trained network around each test point and apply Theorem 4.7 to get an approximate local expansion function based on the linear approximation, then take the average over the test points. Does this give you something similar to what you observe empirically in, e.g., Figure 2?\n * Can you compute the expansion function slopes for non $\\ell_p$ threat models? For instance, it would be interesting to see what the expansion function looks like for $\\ell_\\infty$ to StAdv or vice versa. This would also potentially be a more compelling case for expansion functions since $\\ell_p$ threat models are somewhat similar already (since one can bound any $\\ell_p$ norm by a multiple of an $\\ell_q$ norm). Instead, looking at two very different threat models like $\\ell_\\infty$ and StAdv or $\\ell_2$ and StAdv would give more evidence that expansion functions exist between many threat models. Another interesting example would be measuring the expansion function between LPIPS-based attacks and $\\ell_p$ or StAdv attacks.\n * What happens if you plug in the expansion function slope calculated empirically into Corollary 4.4? Does this give a reasonable estimate for the adversarial error on the target threat model? If not, what do you think accounts for the gap?\n\nSmall thing: on line 158, I think you can only conclude that $L_T(f) \\geq L_S(f)$, not that it is strictly greater. For instance if $f$ outputs the constant uniform distribution over classes for every input, then $L_T(f) = L_S(f)$ for any $S, T$.", "limitations": "I think there are a couple of limitations that the authors did not discuss. While these limitations don't detract too much from the paper's significance, it would be good to mention and address them:\n * The method AT-VR seems to be much more expensive than regular adversarial training (it should take 3x the computation if I'm understanding correctly since one needs to compute gradients wrt three inputs instead of one for each attack step). I don't think the authors mention this.\n * As I mentioned above, the theoretical bounds on the expansion function are not directly applicable to neural networks. Furthermore, it's unclear if the empirical expansion functions predict empirical performance using the bounds in the paper.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n * The problem addressed—adversarial robustness against unseen threat models—is both difficult and understudied compared to other areas of adversarial robustness. The formulation proposed in this paper seems helpful to concretize the problem and provide directions for further research.\n * I particularly appreciated the formulation of the expansion function, which is empirically measurable and can help practitioners working on this problem to diagnose why their model may not be generalizing across threat models.\n * The empirical results seem strong—the proposed method AT-VR generally helps across many threat models and rarely hurts. I also appreciate the very extensive experiments with other threat models and alternative training methods in the appendix. \n\nWeaknesses:\n * While the theoretical bounds using variation and expansion functions give some intuition, they are probably vacuous for reasonable learning problems. Furthermore, none of the bounds on the expansion function apply to neural networks (at least to my understanding, correct me if I'm wrong).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X9wdrvI0Qm8", "reviewer": "Reviewer_UuTG", "summary": "This paper studies the model robustness extension to unforeseen perturbations. The main contribution of the paper is a generalization bound for unforeseen threat models with the knowledge of a source model. The paper further provides a training method for achieving better unforeseen robustness using the generalization bound.", "questions": "Questions about theorems:\n\n1. I don't fully understand the $\\hat{L}_S(f)$. Is it the AT-VR loss in the paper?\n\n2. How can theorem 4.2 guarantee that both \\pho and \\sigma_G are small enough to make the first term <<1?\n\n3. The paper does not mention too much about the sample generalization gap, and the results are all on the threat model generalization gap. Is it possible that the threat model generalization gap is decreasing while the sample generalization gap is increasing?\n\n4. The existence of the expansion function guarantee seems very weak.\n\nQuestions about experiments:\n\n1. AT-VR seems much more computationally expensive than AT.\n\n2. The paper needs to compare its method with state-of-art robust training. Only comparing to AT (2017) is not enough. \n\n3. The experimental results are weak. For example, the clean acc drops 10% compared to AT. Note that AT itself has a significant clean acc drop. This trade-off is not acceptable.\n\n4. Why VR is applied on logits instead of the input of the fully-connected layers?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Achieving a generalization bound to unforeseen attacks is challenging and interesting. The paper provides both theoretical results and experimental results.\n\nweaknesses: The theorems are not clear; The experimental results are weak; The comparisons are insufficient.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J1Md1tejhFy", "reviewer": "Reviewer_9qwD", "summary": "This paper studies a scenario where the threat model assumed by the defense during training (i.e. source threat model S) is different from the threat model used during test time (i.e. target threat model T). It assumes that the target threat model is unknown and is stronger than the source threat model (i.e. the target threat model T is a strict superset of the source threat model S). It formally defines the problem of learning and generalization with an unforeseen adversary. It derives a generalization bound that relates the generalization gap between source and target threat models to variation of the feature extractor, which measures the expected maximum difference between extracted features across a given threat model. Based on the generalization bound, it proposes adversarial training with variation regularization (AT-VR), which reduces the variation of the feature extractor across the source threat model during training. The experimental results demonstrate that AT-VR can lead to improved generalization to unforeseen attacks during test-time compared to standard adversarial training. ", "questions": "1. Could Theorem 4.7 be extended to non-linear cases? \n\n2. Could the authors add more baselines in Table 1? \n\n3. How to select the hyper-parameter $\\lambda$?\n\n4. Could the authors provide some empirical evidence to support the hypothesis stated in Line 380-381? ", "limitations": "The limitations and potential negative societal impact are properly addressed. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this paper has the following strengths: \n\n1. It studies an important problem: generalizing the robustness to a stronger unknown target threat model during test time. Existing works usually assume that the threat model during test time is the same as the threat model during training time, which is not realistic. This paper makes a key contribution by formally defining the problem of learning and generalization with an unforeseen adversary. \n\n2. Under the framework for generalizability, it derives a generalization bound for generalization across threat models. The bound relates the generalization gap to a quantity defined as the variation. It shows that under certain conditions, this upper bound can be decreased while only using information about the source threat model. Based on the generalization bound, it proposes a learning algorithm AT-VR for unforeseen robustness. Empirically, it demonstrates that this technique can lead to improved robustness on unforeseen attacks across datasets such as CIFAR-10, CIFAR-100, and ImageNette over standard adversarial training. \n\n3. It is well-written and the related works are properly discussed. \n\nHowever, I think this paper has the following weaknesses: \n\n1. The source variation-based threat model generalization bound (corollary 4.4) relies on an assumption: an expansion function s from the source threat model S to the target threat model T exists. This assumption may be too strong. Although Theorem 4.7 shows that in the case of a linear feature extractor, a linear expansion function exists for any data distribution from a source $\\ell_p$ adversary to a union of $\\ell_p$ adversaries, it is unclear if such expansion functions exist for neural networks. The linear feature extractor with bounded condition number is too simple. It can consider a more complex case (e.g. two-layer neural networks) and check if the expansion function exists in such a case. \n\n2. In Table 1, it only considers one baseline standard adversarial training. I think it should add more baselines. For example, it can compare the proposed method AT-VR to the Perceptual Adversarial Training (PAT) (Laidlaw et al. 2021). Also, it can add the baseline of adversarial training against the target threat model as an \"oracle\" baseline. \n\n3. It doesn't discuss how to select the hyper-parameter $\\lambda$. Note that the best hyper-parameters should not be selected using the test data. \n\n4. In Line 380-381, it states that \"we hypothesize that this property also appears for ResNet-18 models because neural networks are piecewise linear\". I think it should provide some empirical evidence to support this hypothesis.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept