Learning Robust Models by Countering Spurious Correlations
Authors: Haohan Wang
Zeyi Huang
Eric Xing
Venue:  (2021)
Keywords: robustness
domain adaptation
spurious correlation
dataset bias

Abstract: Machine learning has demonstrated remarkable prediction accuracy over i.i.d data, but the accuracy often drops when tested with data from another distribution. One reason behind this accuracy drop is the reliance of models on the features that are only associated with the label in the training distribution, but not the test distribution. This problem is usually known as spurious correlation, confounding factors, or dataset bias. In this paper, we formally study the generalization error bound for this setup with the knowledge of how the spurious features are associated with the label. We also compare our analysis to the widely-accepted domain adaptation error bound and show that our bound can be tighter, with more assumptions that we consider realistic. Further, our analysis naturally offers a set of solutions for this problem, linked to established solutions in various topics about robustness in general, and these solutions all require some understandings of how the spurious features are associated with the label. Finally, we also briefly discuss a method that does not require such an understanding.

Under review as a conference paper at ICLR 2021
LEARNING ROBUST MODELS BY COUNTERING SPURIOUS CORRELATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Machine learning has demonstrated remarkable prediction accuracy over i.idd data, but the accuracy often drops when tested with data from another distribution. One reason behind this accuracy drop is the reliance of models on the features that are only associated with the label in the training distribution, but not the test distribu- tion. This problem is usually known spurious correlation, confounding factors, or dataset bias. In this paper, we formally study the generalization error bound for this setup with the knowledge of how the spurious features associated with the label. We also compare our analysis to the widely-accepted domain adaptation error bound and show that our bound can be tighter, with more assumptions that we consider realistic. Further, our analysis naturally offers a set of solutions for this problem, linked to established solutions in various topics about robustness general, and these solutions all require some understandings of how the spurious features are associated with the label. Finally, we also briefly discuss method that does not require such an understanding.
INTRODUCTION
Machine learning, especially deep neural networks, has demonstrated remarkable empirical suc- cesses over various benchmarks. One promising next step is to extend such empirical achievements beyond i.id benchmarks. If we train model with data from distribution (i.e., the source dis- tribution), how can we guarantee the error to be small over other unseen, but related distributions (i.e., target distributions). Quantifying the generalization error two arbitrary distributions is not useful, thus, we require the distributions of study similar but different: being similar in the sense that there exists common function that achieve zero over both distributions, while being different in the sense that there exists another different function that can only achieve zero error over the training distribution, but the test distribution.
This problem may not be trivial because the empirical risk minimizer (ERM) may lead the model to learn this second function, topic studied under different terminologies such as spurious correlations [Vienn] 2015), confounding factors (McDonald 2014) or dataset bias (Torralba & Efros 2011). As a result, small empirical error may not mean the model learns what we expect (Geirhos al. [019 Wang et al. 2020), thus the model may not be able to perform consistently over other related data.
In particular, our view of the challenges in this topic illustrated with a toy example in Figure where the model is trained on the source domain data to classify triangle vs. circle and tested on the target domain data. However, the color coincides with the shape on the source domain, so the model may learn either the desired function (relying shape) or the spurious function (relying color). The spurious function will not classify the target domain data correctly while the desired function can, but the ERM cannot differentiate them. As one may expect, whether shape color is considered as desired or spurious is subjective dependent on the task or the data, and in general irrelevant to the statistical nature of the problem. Therefore, spurious function. While this is toy example, this scenario surly exists in real world tasks (e.g., Jo] & Bengio 2017 Geirhos et al. 2019 Wang al. 2020). The contributions of this paper are:
error bound will require the knowledge of the
We analyze the cross distribuito generalization error bound of model when the model is trained with a distribution with spuriously correlated features, which is formalized as the main theorem of this paper.

---

Under review as a conference paper at ICLR 2021
Spave Dveea
desired libeiing faxdio (slasiffe) ofe
Tape
stgge thi flxction will prod the stage comeetly ove oarg domsin
sperious libeling funotion (clesitte) of
the shage becuse color colecides with the shape this dumibrrion, this finenon will just peedet the siaze conecilly ove lages domais dats
Figure 1: toy example of the main problem focused in this paper.
We compare bound to the andely-accepted domain adaptation one (Ben-David al., 2010 and show that our bound can be tighter under assumptions that we consider realistic.
Our main theorem naturally offers principled solutions of this problem, and the solutions are linked to many previous established methods for robustness in broader context.
As the principled solutions all require some knowledge of the task or the data, our main theorem also leads new heuristic absent of the knowledge. This new method may be on a par with the principled solutions, and can outperform the vanilla training empirically.
2 RELATED WORK
There is a rich history of learning robust models. We first discuss works in three topics, all centering around the concept of invariance, where invariance intuitively means the model's prediction pre- serves under certain shift of the data. We then highlight works related to our theoretical discussion.
Cross-domain Generalization This line of works probably originates from domain adaptation (Ben-Daver et al. 2007). which studies the problem of training a model over one distribution and test over another one. Since (Ganin al. 2016), recent advances along this topic mainly center around the concept of invariance: most techniques leverage different regularizers to learn representations that are invariant to the marginals of these two distributions (e.g.. Ghifary al.] 2016 Rozantsev et al. 2018). Further, the community aims beyond the situation that a trained model from domain adaptation may only be applicable to one distribution, and focuses on domain generalization MMuan- det et al.) 2013), which studies the problem of training model over collection of distributions and test with distributions unseen during training. Similarly, most recent methods aim to learn repre- sentations invariant to the marginals of the training distributions (e.g.. Motiian et al., 2017 Li et al.) 2018 Carlucci et al. 2018). Recently, the community extends the study to domain generalization without domain IDs to address the real-world situations that domain IDs are unavailable (Wang et al.) 2019b), which again focuses on learning representations invariant to specifically designed functions.
Adversarially Robust Models The study of robustness against adversarial examples was popular- ized by the empirical observations that small perturbations on image data can significantly alter the model's prediction (Szegedy al. 2013] Goodfellow al., 2015). This observation initiated a line of works building models invariant to such small perturbations (the rigorous definitions of "small perturbations" will not be discussed in details here) (e.g., [ee al. 2017 Akhtar al., 2018) and adversarial training (Madry et al. 2018) is currently the most widely-accepted method in terms of empirical defense. On the other hand, the community also aims to develop methods that are prov- ably robust to predefined perturbations (e.g.. Wong & Kolter 2018 Croce & Hein 2020). which links back to the works of distributional robust models (e.g.. Abadeh et al., 2015 Sagawa" et al., 2020), whose central goal is to train models invariant to a predefined shift of distributions. Recent evidence shows key challenges of learning adversarially robust models are spuriously correlated features Mlyas et al. 2019 Wang et al. 2020), connecting adversarial robustness to the next topic.
Countering Spurious Correlation Works along this line usually connects the robustness of a model to its ability of ignoring the spurious correlation in the data, which was also studied under the terminologies of confounding factors, or dataset bias. With different concrete definitions of the spurious correlation, methods have been developed for various applications, such as image/video
classification (e.g.. Goyal et al.] 2017 Wang et al. 2019a b; Bahng et al.) 2019; Shi et al. 2020
text classification (e.g., [e et al.
2019 Clark al.
2019 Bras al. 2020 Zhou & Bansal
2020
2

---

Under review as a conference paper at ICLR 2021
Ko et al. 2020), medical diagnosis (e.g.. Zech et al. 2018 Chaibub Neto et al. 2019 Larrazabal ct al. 2020) etc. The key concept is, as expected, to be invariant to the spurious correlated features.
Related Theoretical Discussion Out of rich collection of theoretical discussions in learning robust models, we only focus on the ones for unsupervised domain adaptation, as they will be related to our discussions in the sequel. Popularized by (Ben-David al. 2007 2010), these analyses, although
in various forms (Mansour et al. 2009) Germain et al." 2016 Zhang et al. 2019 Dhouib et al.] 2020), mostly involve two additional terms than standard machine learning generalization bound: one term describes the "learnable" nature of the problem and one term quantifies the differences of the two distributions. This second term probably inspired most of the empirical methods forcing invariant representations from distributions. However, the value of invariance is recently challenged (Wu et al., 2019 Zhha et al., 2019). For example, /Zhao et al.) (2019) argued that "invariance not sufficien" by showing counter examples violating the "learnable" nature of the problem and formalized the understanding as that the two distributions have possibly different labeling functions.
Key Difference: However, we find the argument of disparity in labeling functions less intuitive, because human will nonetheless be able to agree on the label of an object whichever distribution the object lies in: in the context of this paper, we argue shared labeling function always exists (in any task reasonable to human), but the ERM model may not have the incentive to learn this function and learns spurious one instead. As in Figure T formalize the problem as learning against spurious functions, and argue that the central problem is still invariance, but instead of invariance to marginals, we urge for invariance the spurious function. Our discussion also applies more than unsupervised domain adaptation and relates to most of the topics discussed in this section.
3 GENERALIZATION UNDERSTANDING WITH SPURIOUS CORRELATION
3.1 NOTATIONS & BACKGROUND
We consider a binary classification problem from feature space X' E R2 to label space y {0, 1)- The distribution over X' is denoted as P. A labeling function f : : + y is a function that maps feature x to its label y. A hypothesis or model 0 X 3/ is also function that maps feature the label. The difference in naming is only because we want to differentiate whether the function is a natural property of the space or distribution (thus called labeling function) or a function to estimate (thus called a hypothesis or model). The hypothesis space is denoted as O. This work concerns with the generalization error across two distributions, namely source and target distribution, denoted as P. and P. respectively. As stated previously, we are only interested when these two distributions are similar but different: being similar means there exists a desired labeling function, fa. that maps any x E X' to its label (thus the label y == fa(x)); being different means there exists spurious labeling function, fp. that for any X ~ P (x(x = fa(x). This "similar but different" property assumption (A2) later. We use yx to denote sample, and use (X, Y)P
will be reiterated to denote a finite dataset the features are drawn from P. We use (f) to denote the expected risk of 0 over distribution P, and use - to denote estimated term (e.g., the empirical risk is (f))) We use I(.,)) )) to denote generic loss function. For a dataset (X, Y)P, if we train a model
i arg min BEe
Σ
1(0(x),y),
(1)
(x.))((XY))
previous generalization study suggests that we can expect the error rate to be bounded as
(p < (0) + n),),,
(2)
where ep (0) and (θ) respectively
Cp i Ex~P [xx) y/ =xxp)((() fa(x)] and 7p(
1 n
Σ (x)))(XXYY)
10(x) y/,
and @( n, 8) is a function of hypothesis space [0), number of samples n, and 8 accounts for the probability when the bound holds. This paper only concerns with this generic form that can subsume many discussions, each with its own assumptions. We refer to these assumptions as A1.
A1: basic assumptions needed to derived formalized with two examples in appendix A.1
3

---

Under review as a conference paper at ICLR 2021
3.2 GENERALIZATION UNDERSTANDING WITH SPURIOUS CORRELATION
Our interest lies in more than the expected performance over samples from the same distribution, but over different distribution that shares the same labeling function. As we argue previously, the key difficulty in learning a robust model is the existence of the extra labeling function for features sampled from P.. More formally, we have our first assumption describing this problem
A2: Existence of Spurious Correlation: For any x E y, == fa(x). We also have a fp that is different from fa. and for Ps. Sa(x) = [z(x).
Thus, 0 that learns either fa or fp will lead to small source error, but only 0 that learns Sa will lead to small target error. Note that fp may not exist for an arbitrary P.. In other words, A2 can be interpreted regulation to Pa so that fp. while being different from fa, exists for any x P..
In this problem. fp and fa are not the same despite fx) = fa(x) for any x ~ Ps. and we consider the differences lie in the features they use. To deseribe this difference, we introduce the notation A(..)) which denotes a set parametrized by the labeling function and the sample, to describe the active sef of features that used by the labeling function. By active set, we refer to the minimum set of features that a labeling function requires to map sample to its label. Formally, we define
A(f.x) (xxx/())/((x)
arg min [ax(z));
where ax (z) {ilzz } is the set of indices by which z and x are the same, and | the cardinality. Although fx( = fa(x), A(pp. x) and A(fa, x) can be different.
measures
Further, we define new function difference given a sample
max (0, =E
8(z) - f())).
(4)
A(
where x xA(xx) denotes the features of indexed by A(f, x). other words, the distance describes: given a sample x, what is the maximum disagreement of the two functions A and f for all the other data z E with a constraint that the features indexed by A(f, x) are the same as those of x. Notice that this difference is not symmetric, as the active set is determined by the second function. By definition, we have dx (0. f) 2 10(x) - fx)]..
We introduce two more assumptions:
A3: Separable Labeling Functions: For any x E X, A(,,(f,, x) 0
A4: Realized Hypothesis: Given a large enough hypothesis space θ for any sample (x,y), for any 0 E O which is not a constant mapping, if ((x) = y, then dx fa)d (0, fp) =
Intuitively, A3 assumes the active sets of the two labeling functions not overlap. A4 assumes a at least learns one labeling function for the sample x if 0 can map the correctly.
Finally, we use the term
((,A(f))) =
max EA ALF
10(x) yyl
(5)
to describe how depends on the active set of f. Notice that r(0, ((f,))) = 1 alone does not mean 0 depends on the active set of f. it only means so when we also have 0(x) y (see formal discussion in Lemma B.I. With all above, we formalize a new generalization bound as follows:
Theorem 3.1 (The Curse of Universal Approximation). With Assumptions A1-A4, with probability as least 1 5, we have
(0) - (0) + c(0) n.
Ex.yEEXXX = 1[0(x) = y)r(0,AAfp..))
where c(0) = n1
1
I[:] is a function that returns the condition holds true, and 0 otherwise. As may learn fp- Cp. (8) can no longer alone indicate (9), thus introduce c(0) to account for the discrepaney. Intuitively, c(f) quantifies the samples that are correctly predicted, but only because the 9 learns fp for that sample. c()) critically depends on the knowledge of fp-
4

---

Under review as a conference paper at ICLR 2021
We name Theorem 3.1 the curse of universal approximation to highlight the fact that the existence of fo is not always obvious, but the models can usually learn it nonetheless. For example, [lyas et al. (2019) suggest the root to the performance drop over adversarial examples are spurious features, and Wang et al. 2020) demonstrate the existence of human-imperceptible high-frequency spurious signals image datasets, which may explain several generalization issues of the models. In other words, even in a well-curated dataset that does not seemingly have spurious correlated features, modern machine learning models may still use some spurious features not understood by human, leading to non-robust behaviors when tested over other datasets that human consider similar. This argument may also align with recent discussions suggesting that reducing the model complexity can improve cross-domain generalization (Chuang et al. 2020).
3.3 IN COMPARISON TO THE VIEW OF DOMAIN ADAPTATION
We further compare Theorem 3.1 with established understandings of domain adaptation. We sum- marize the several domain adaptation understandings in the following form (see details in 2
CP. (0) - Tp. (0) (P P.) + A o' (1(9), n,
where De (P,, Pr) quantifies the differences of the two distributions, and describes the nature of the problem, and usually involves non-estimable terms about the problem or the distributions.
For example, Ben-David et al. 2010 formalize the difference as H-diivergence, and describe the corresponding empirical term (OAO is the set of disagreement between two hypotheses in Q):
De(P.. P.) 1 min #ERA0 x=0(x)=0
_
Σ
(X. 1
Σ
1|x Y)p.))
(8)
x:0(x)=1
where m denotes the number of unlabelled samples in P. and P. each. A = (0*) + (0*), where 6 arg mingee EP, (0) + (0).
In our formalization, as we assume the fa applies to any x E X (according to A2), X = 0 as long as the hypothesis space large enough. Therefore, the difference mainly lies in the comparison between c(f) and De (P..P. P.). To compare them, we need an extra assumption:
A5: Sufficiency of Training Samples for the two finite datasets in the study, i.e., (X, Y)P, and (X, Y),,, for any x E (X, Y)p,, there exists one or many z E (X, Y)P, such that
x (x' E X' and x'A((a.z) = ZA(fa>))
AS intuitively means the finite training dataset needs to be diverse enough to describe the concept that needs to be learned. For example, imagine building a classifier to classify mammals vs. fishes from the distribution of photos to the distribution of sketches, we cannot expect the classifier to do anything good on dolphins if dolphins only appear in the test sketch dataset. A5 intuitively regulates that if dolphins will appear in the test sketch dataset, they must also appear in the training dataset.
Now, in comparison (Bvid al. 2010 have
Theorem 3.2. With Assumptions A2-A5, and if - fa E O, we have
c(0) (P P.)
Σ
11((x) y)r(0,
(10)
(x,))E(X,Y)) Y)P,
1 n
where c(0) - E(x,))(XXY) 1[8(x) = ())((9,A(t)))) x)) and PP PP.,..) is defined as in (8)
The comparison involves extra term, (()) = which intuitively means that 0 learns fp. how many samples can coincidentally predict correctly over the finite target set used to estimate (P P.). For sanity check. if we replace (X, Y)P. with (X, Y)p,, (P e. P.) will be evaluated at 0 as it cannot differentiate two identical datasets, and (9) will be the same c(f). On the other hand, if no samples from (X, Y)P, can be mapped correctly with f (coincidentally). (0) = 0 and c(f) will be a lower bound of (P P.).
; (xxxxxx(XX [[((x) y)r(0, A(fp x)),
The value of Theorem 3.2 lies in the fact that for arbitrary target dataset (X, Y)P., no samples out of which can be predicted correctly by learning fp (a situation likely to occur for arbitrary datasets), c(0) will always be lower bound of (P P,).
5

---

Under review as a conference paper at ICLR 2021
Further, when Assumption A5 does not hold, are unable to derive clear relationship between c(f) and De (P.. Pt). The difference mainly raised as a matter of fact that, intuitively, we are only interested in the problems that are "solvable" (A5, L.e. hypothesis that used to reduce the test error in target distribution can be learned from the finite training samples) but "hard to solve" (A2, ie., another labeling function, namely fp. exists for features sampled from the source distribution only), while De (P... Pt) estimates the divergence of two arbitrary distributions.
Estimation of c(O). Finally, due the limitation of space, we discuss the estimation of c(0) in appendix A.2 In short, in practice, while we do not know fp. we usually know A(fp. x) through intuition or common sense, such texture or background of images. Thus, the estimation to test the whether the model switches its correct prediction when these features are perturbed over the possible space. Also, the search can be terminated once r(0, A(S, x)) is evaluated as As one may be aware of, this process is widely known as adversarial attack (e.g.. Goodfellow et al. 2015).
METHODS TO LEARN ROBUST MODELS
In this section, we will take advantage of analysis to introduce methods that can be used to learn robust models by countering the spurious correlation. First, we discuss the principled solutions that can lead to the error bound Theorem t. be smaller. These methods many previously established methods in robustness in general. Second, as all above methods will require some knowledge of fp A(pp x), we also explore new method that does not require so.
interestingly linked to
4.1 PRINCIPLED SOLUTIONS OF LEARNING ROBUST MODELS
key to learning robust model to reduce c(0). However, for the convenience during training, we can consider its upper bound
According Theorem 3.1
( S
Σ A(0,)(s,.))
1 n
Σ
max
0(x) - y/,
(II)
(x,))((XY)) XA(Iaa) EXAU
(XXY)
which intuitively means that instead of c(0) that concerns with the correct prediction based on only fp- now study any prediction based only fp.
Also, as we introduced in "estimation of c(0)": although we barely know fp in practice, we usually directly know A(fp. x) through the intuition or common sense of the data or the task.
Ad Adversarially robust models (worst-case data augmentation) The most direct approach of learn- ing robust models will be optimizing reduce (11) in addition to the generic loss (i.e., I(f(x), y)) of a model. Further, as [0(x) yl S maxx A(). 10(x) yl. we can drop the generic loss term, and directly train model with
min 8
Σ (x)))(X,Y) XAU EX x))
max 1(8(x),y),
(12)
7
which is one of the most widely used methods in adversarial robust literature: the adversarial training (Madry et al. 2018). as well as worst-case data augmentation (Fawzi et al.) 2016).
Data augmentation Alternatively, we assume
Ex P AUp.))
((x) yl
max
10(x) yl.
(13)
x XA MAATo
where pall denotes the distribution that help remove the correlation between fp related fea- tures and y (e.g., a uniform distribution over X' is sufficient, but P, will not be good enough). The main strategy to train with the samples whose fp related features are randomized, so that the model is expected to learn ignore the pattern. As can usually be sampled by pall, one can drop the generic loss and train a model with
min 0 n
Σ (X)))((X.Y
1(0(x),))
(14)

---

Under review as a conference paper at ICLR 2021
Regularizing hypothesis space We can also consider to find rrggularized that 10(x) - -yl XAifg. 25) x
max
xx(x) y for 0 E regularized:
(15)
which intuitively means that for any 0 E ② regularized: 0 ignores the information from A(pp. x). There is a proliferation of recent developments of this thread, either through intuitive understanding of the task or the data (e.g., Waan et al. 2019a b Bahng et al. 2019) or through theoretical understanding for rigorously defined perturbations (e.g.. Abadeh et al.
2015 Cranko al. 2020
4.2 LEARNING ROBUST MODELS WITH MINIMUM SUPERVISION
While our analysis suggests that we cannot have robust model without the knowledge of fo. we continue ask that what the best we can do without such knowledge. we use denote the set (Ja, Jp} and use i to index its element, we can have the following upper bound to optimize
< S
Σ (X.))(XX.)
r(0,A(fm.)))
E A(FO,((F,x)). (x-Y)
(16)
By optimizing the RHS of [6). we aim to discourage the learning towards functions that only rely on one labelling function for each sample for any labelling functions. Intuitively, the method is to encourage the model's usage in all possible features (either associated with fa or fp). thus the model may be more robust to the changes of features when dealing with perturbations of the data.
model using all the features not expected to be better than a method that only uses the fa associated features. However, all methods in requiiee specific knowledge of fp. we argue this a better practice than vanilla training (I) when there are no side information about either fa or fp-
In practice, as do not have the knowledge of F. we can use the estimated 0 from previous iteration as a substitute, also as the searching for A(f, x) can be computationally expensive, we use the gradient information to guide the selection of the features. In summary, this new method, which we name minimum supervision (MS), has the following three major steps at iteration t:
Use ((+-1) as a substitute of either fa or fp- Identify A(@(t-1), x) with top p fraction of features according the gradient.
Sample ( .x) over Ka(tit-1), and continue to train the model.
Thus, the new method has a hyperparameter p. Due to the limitation of space, we discuss the detailed algorithm and other practical aspects of the method appendix A.3
EXPERIMENTS
The experiments fall into two scenarios: we first use the two binary classification experiments to support Theorem 3.1 and 3.2 (III): then test how the new method we introduced in comparison to previously developed methods explicitly using the knowledge of (45.2).
5.1 THEORY SUPPORTING EXPERIMENT
Synthetic Data with Spurious Correlation We also Figure to data with p features, where p/2 features are related to fa p/4 features are related to fp. and the rest p/4 features are independent on labels. Also, Ja non-linear function, and fp simpler. We test across multiple choices. Overall, the results suggest (I) minimum supervision works better than the vanilla method; (2) c(0) a tighter estimation the test error than (P.... Pt). Details are in appendix C.I
Binary Digit Classification over Transferable Adversarial Examples We also verify the theoret- ical discussion through a binary digit classification experiment, where the train and validation set digits 0 and I from MNIST train and validation dataset. To create the test set, we first estimate a model, and perform adversarial attacks over this model for the test samples with five adversarial attack methods (C&W (Carlini & Wagner 2017). DeepFool (Moosavi-Dezfoolf et al. 2016), FGSM

---

Under review as a conference paper at ICLR 2021
7,.19
7e.00)
CS/N
DeepFooo
FGSM
SaltSPesper
Singlriical
k10
32
0.0
Ven
14
Figure 2: Binary MNIST classification error and estimated bounds. Each panel represents one out- of-domain data generated through attack method. Four methods reported in each panel. For each method, four bars are plotted: from left to right, Ép, (0), εp, (0), Ep, (0) + c(0), and CP, (0) + De. Some bars are not visible because the values small.
Vanilla"
StylisedIN
LearnedMixin
RUBi
ReBias
MS
Standard Accuracy
90.8
88.4
67.9
90.5
91.9
92.1
Weighted Accuracy
88.8
86.6
65.9
88.6
90.5
91.3
ImageNet-A 24.9
24.6
18.8
27.7
29.6
29.3
ImageNet-Sketie
41.1
40.5
36.8
42.3
41.8
42.9
Table 1: Results comparison on super-class ImageNet classification. *Only Vanilla and MS do not leverage any knowledge of the spurious features.
Goodfellow et al. 2015), Pepprr (Rauber et al. 2017). and SinglePixel (Rauber et al. 2017) These adversarially generated examples are considered as the test set from another distribution.
An advantage of this setup is that we can have fp well defined as 1 1 fadu. where the fado is the function each adversarial attack relies on. Thus, we can assess our analysis on image classification.
We train the models with vanilla method, minimum supervision method (MS), adversarial training (AT), and data augmentation (Aug). In addition the training error (i.e., Ep, (0) and test error (i.e., E (0)), we also report fp, (0) + ce0 and εp, (0) + Dg. Our results in Figure 2 agaii align with our analysis: (1) minimum supervision outperforms the vanilla method, but may be inferior to methods using fo explicitly; (2) c(0) is often tighter estimation of the test error than De P:).
5.2 REAL IMAGE CLASSIFICATION
Finally, we conduct real-image classification compare whether our minimum supervision method can be compared to other advanced methods in a more challenging and realistic setting. We follow the setup in (Bahng al.] 2019) and compare the models for super-class ImageNet classification (Ilyas et al. 2019) with class balanced strategies. Also, we follow (Bahng et al.) 2019) to report standard accuracy, weighted accuracy, a scenario where samples with unusual texture are weighted more, and accuracy over ImageNet-A (Hendrycks et al. 2019). collection of failure cases for most ImageNet trained models. Additionally, we also report the performance over ImageNet- Sketch (Wang al. 2019a), an independently collected ImageNet test set with only sketch images.
We report the results in Table [ Our method (MS) outperforms other methods in most situations, which we consider impressive since only MS and vanilla methods are not using any knowledge of f or fa. More details of the experiment setup and competing methods are discussed in appendix C.2
CONCLUSION
In this paper, we formalized the generalization error when the models can use some spurious features in the training set that are not shared in the test set, a problem widely studied under the terminologies of spurious correlation, confounding factors, or dataset bias. We formalized a new generalization error bound, and compared our bound to the well-established domain adaptation one. More impor- tantly, our theorem naturally offers a set of principled solutions for this problem. These principled solutions are linked to many previous methods for robustness in broader context. Since all these principled solutions require some knowledge of the spurious correlated features, we also leveraged theorem to develop new method that does not require such knowledge.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Soroosh Shaficezadeh Abadeh, Peyman Mobajerin Mohajerin Esfahani, and Daniel Kuhn. Distri- butionally robust logistic regression. In Advances Neural Information Processing Systems, pp. 1576-1584, 2015.
Naveed Akhtar, Jian Liu, and Ajmal Mian. Defense against universal adversarial perturbations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3389- 3398, 2018.
Hyojin Bahng, Sanghyuk Chun, Sangdoo Yun, Jaegul Choo, and Scong Joon Oh. Learning de-biased representations with biased representations. arXiv preprint arXiv:1910.02806, 2019.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pp. 137- 137-144, 2007.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):511-775. 2010.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning the- ory. In Summer School on Machine Learning, pp. 169-207. Springer, 2003.
Ronan Le Bras, Swabha Swayamdipta, Chandra Bhagavatula, Rowan Zellers, Matthew Pe- ters, Ashish Sabharwal, and Yejin Choi. Adversarial filters of dataset biases. arXiv preprint arXiv:2002.04108, 2020.
Remi Cadene, Corentin Dancette, Matthieu Cord, Devi Parikh, et al. Rubi: Reducing unimodal biases for visual question answering. In Advances in neural information processing systems, pp- 841-852, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 2017
Fabio M Carlucci, Paolo Russo, Tatiana Tommasi, and Barbara Caputo. Agnostic domain general- ization. arXiv preprint 1oXiv:/808.. 01 /02, 2018.
Elias Chaibub Neto, Abhishek Pratap, Thanneer M Perumal, Meghasyam Tummalacherla, Brian M Bot, Lara Mangravite, and Larsson Omberg. A permutation approach assess confounding in machine learning applications for digital health. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 54 64, 2019.
Ching- Yao Chuang, Antonio Torralba, and Stefanie Jegelka. Estimating generalization under distri- bution shifts via domain-invarian representations. arXiv preprint arXiv:2007.03511 2020.
Christopher Clark, Mark Yatskar, and Luke Zettlemoyer. Don't take the easy way out: Ensemble based methods for avoiding known dataset biases. arXiv preprint arXiv:1909.0368. 2019.
Zac Cranko, Zhan Shi, Xinhua Zhang, Richard Nock, and Simon Korbbiith, Generalised lipschitz regularisation equals distributional robustness. arXiv preprint 2011:27002.04197, 2020.
Francesco Croce and Matthias Hein. Provable robustness against all adversarial pertuuturattions for 1. In International Conference Learning Representations, 2020.
Sofien Dhouib, levgen Redko, and Carole Lartizien. Margin-aware adversarial domain adaptation with optimal transport. In Thirtty-eventhh International Conference on Machine Learning, 2020.
Alhussein Fawzi, Horst Samulowitz, Deepak S. Turaga, and Pascal Frossard. Adaptive data aug- mentation for image classification. 2016 IEFE International Conference on Image Processing, ICIP 2016, Phoenix, AZ, USA, September 25-28, 2016, pp- pp- 3688-3699 IEFF, 2016.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor S. Lempitsky. Nomain-adversaan training of neural networks. J. Mach. Learn. Res., 17:5911-59:35 2016.

---

Under review as a conference paper at ICLR 2021
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A. Wichmann, and Wieland Brendel. Imagenet-tradd trained CNNs are biased towards texture; increasing shape bias im- proves accuracy and robustness. In International Conference on Learning Representations, 2019.
Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. A new pac-bayesian perspective on domain adaptation. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICMI. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 859-868. JMLR.org, 2016.
Muhammad Ghifary, W Bastiaan Kleijn, Mengjie Zhang, David Balduzzi, and Wen Li. Deep recomstuction-caaasficcatoo networks for unsupervised domain adaptation. In European Con- ference on Computer Vision, pp. 597-613, Springer, 2016.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples (2014). In International Conference on Learning Representations, 2015.
Yash Goyal, Tejas Khot, Douglas Summers- Stay, Dhruv Batra, and Devi Parikh. Making the v in vqa
matter: Elevating the role of image understanding in visual question answering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6904-6913, 2017.
He He, Sheng Zha, and Haohan Wang. Unlearn dataset bias in natural language inference by fitting the residual. arXiv preprint arXiv: /908. 10763, 2019.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. arXiv preprint arXiv:/907.07/113 2019.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems, pp. 125 236,136,12 2019.
Jason Jo and Yoshua Bengio. Measuring the tendency of cnns to learn surface statistical regularities. CoRR, abs/1711. 11561, 2017. URL http::httaxtiiiieeeee http://arw...oooaa//////o/ abs/g//bb//11l111/ 11561
Miyoung Ko, Jinhyuk Lee, Hyunjae Kim, Gangwoo Kim, and Jaewoo Kang. Look at the first sentence: Position bias in question answering. arXiv preprint arXiv:2004. 14602, 2020.
Agostina Larrazabal, Nicolás Nieto, Victoria Peterson, Diego H Milone, and Enzo Ferrante. Gen- der imbalance in medical imaging datasets produces biased classifiers for computer-aide aided diag- 2020.
nosis. Proceedings of the National Academy of Sciences, 117(23):12522-133)
Hyeungill Lee, Sungyeob Han, and Jungwoo Lee. Generative adversarial trainer: Defense to adver- sarial perturbations with gan. arXiv preprint arXiv: 2017.
Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex Kot. Domain generalization with adversarial feature learning. In Proc. IEEE Conf. Comput. Vis. Pattern (CCPR) 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Confer- ence Track Proceedings. OpenReview.net, 2018.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
JH McDonald. Confounding variables. Handbook of biological statistics, 3rd edn. Sparky House Publishing, Baltimore, pp. 24-28,77 2014.
Seyed-Mohsen Moosavi-Dezfoollt Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. Proceedings of the IEEE Conference on Com- pufer Vision and Pattern Recognition, pp. 2016.
10

---

Under review as a conference paper at ICLR 2021
Saeid Motiian, Marco Piccirilli, Donald A Adjeroh, and Gianfranco Doretto. Unified deep super- vised domain adaptation and generalization. In The IEEE International Conference on Computer Vision (ICCV), volume 2, pp. 3, 2017.
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning. pp. 10-18, 2013.
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox to benchmark the robustness of machine learning models, 2017.
Artem Rozantsev, Mathieu Salzmann, and Pascal Fua. Beyond sharing weights for deep domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 41(4):801-814, 2018.
Shiori Sagawa*, Pang Wei Koh*, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. International Conference on Learning Representations, 2020.
Baifeng Shi, Dinghuai Zhang. Qi Dai, Zhanxing Zhu, Yadong Mu, and Jingdong Wang. Infor- mative dropout for robust representation learning: A shape-bias perspective. arXiv preprint arXiv:2008. 04254, 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199, 2013.
Antonio Torralba and Alexei A Efros. Unbiased look at dataset bias. In CVPR 2011, pp. 1521-1528. IEEE, 2011.
Tyler Vigen. Spurious correlations. Hachette books, 2015.
Haohan Wang, songwei Ge, Zachary C. Lipton, and Eric P. Xing. Learning robust global repre- sentations by penalizing local predictive power. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pp. 10506-10518, 2019a.
Haohan Wang, Zexue He, Zachary Lipton, and Eric P. Xing. Learning robust representations by projecting superficial statistics out. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019b.
Haohan Wang, Xindi Wu, Zeyi Huang, and Eric P Xing. High-frequency component helps explain the generalization of convolutional neural networks. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 8684-8694, 2020.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295, PMLR, 2018.
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetrically-rrlaxed distribution alignment. In International Conference on Machine Learn ing. pp. 6872-6881, 2019.
John R Zech, Marcus A Badgeley, Manway Liu, Anthony B Costa, Joseph J Titano, and Eric K Oermann. Confounding variables can degrade generalization performance of radiological deep learning models. arXiv preprint arXiv: 00000, 2018.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I. Jordan. Bridging theory and algorithm for domain adaptation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7404- 7413. PMLR, 2019.
11

---

Under review as a conference paper at ICLR 2021
Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon. On learning invariant representations for domain adaptation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp- 7523-7532. PMLR, 2019.
Xiang Zhou and Mohit Bansal. Towards robustifying nli models against lexical dataset biases. arXiv preprint arXiv:2005.044 04732, 2020.
12

---

Under review as a conference paper at ICLR 2021
A SUPPORTING DISCUSSIONS
A.1 CONCRETE EXAMPLES OF GENERIC GENERALIZATION BOUND
when A1 is "O is finite, 1(:-) is a zero-one loss, samples are i.i."" @([)), ([log((@) + log(L/))))2n
when A1 is "samples are iid'' o(()), n, 6) = 2R(C) + V (log 1/8)/2n, where R(C) stands for Rademacher complexity and C {4e 10 θ}, where lo is the loss function corresponding to 0.
For more information textbooks such as (Bousquet et al. 2003).
concrete examples of the generie term, refer to relevant
A.2 ESTIMATION OF c(0)
The estimation of c(0) mainly involves two difficulties: the knowledge of fp and the computational cost of the search over the entire space X. The first difficulty is usually resolved with intuition common sense of the data the task: in practice, A(fp.x), i.e. the spuriously correlated features that fp relies on, such as texture of images. There- fore, the estimation becomes process test the whether the model will switch its correct prediction when these features are perturbed over the possible space. The second difficulty can be alleviated due to the fact that the search can be terminated once r(0, x)) is evaluated as 1. As one may be aware of, this process of searching the entire space with perturbations allowed in predefined scope test the model's worst possible prediction for sample widely known as adversarial attack Goodffllow et al., 2015). These techniques also usually leverage the knowledge of the model's gradient to accelerate the searching process.
usually directly have the knowledge of
While adversarial attack can offer fairly accurate estimation of c(f), it usually requires heavy computational efforts. As an alternative strategy, many other literature have tested the models with some fixed perturbations of the or in other words, taking advantage of the fact that
10(x') - yl S
max SAArr)ninXALA
((x) y = r(0, A(),x)) where XAUAX)) E &A(Ax)- (17)
to test lower bound of c(0). There are many works in this thread, and we only list handful of examples: Jo & Bengio (017)) leveraged Fourier transform to show that models can capture significant amount of texture information, later Geirhos et al. (219)) showed that CNNs trained with ImageNet are also biased towards texture. With a more concrete definition of the texture, WWagg signals from images, which also
et al. (2020) demonstrated the models can capture links the discussion of learning through bias signals to the adversarial vulnerability issue of models [Ilyas et al.) 2019). Similarly, these works mostly depend on a subjective choice of A( x), usually given by the knowledge of the data the task. Although these works did not directly assess c(0), usually switched the prediction for sufficient samples to raise an alarm.
A.3 LEARNING ROBUST MODELS WITH MINIMUM SUPERVISION IN PRACTICE
In practice, do not have the knowledge of either fa or fp (F), the strategy use is to estimate the model first and consider our estimated model as a substitute of the labeling function (either fa or fp). Therefore, at each iteration i, we will use the at the previous iteration to identify the active set for the optimization of (16) (in main manuscript).
Further, another question is that when we have --1, how to identify A(@-11,)) x). as searching for A x) by the definition can be computationally expensive. Our practical strategy is to use the gradient of -1 to guide the selection of the features. Intuitively, argue that the the features with larger absolute values of (10-11 x,y) /00--1 are the features @C-1 relies
13

---

Under review as a conference paper at ICLR 2021
Finally, we consider the features with values greater than threshold T(pg)) are the features that in A(0-11, x). The threshold hold is set as the n quantile of all the calculated gradients for this sample. The algorithm is shown in Algorithm !
Algorithm 1: Learning Robust Models with Minimum Supervision
Result: 8
Input: T.P. P. (X. Y); initialize 00,
1, 7); while ( s T do
for sample yx) do
calculate the gradient g 01(00~111)00000 ,x y)
set the threshold T(p. g) be the nt quantile of lg):
set A(0' sample x' where x A((0- E xx)=
(illg 2 T(p. (p.g));
calculate the gradient g' 01(00-11 000
update the model H = ng
end end
14

---

Under review as a conference paper at ICLR 2021
B PROOFS OF THEORETICAL DISCUSSIONS
B.I LEMMA B.I AND PROOF
Lemma B.1. With sample (x,y) and two labeling functions fi(x) f2(x) y, for estimated
E O, if ix) = y, then with A3 and A4, we have
dx(0, f1) = =
A(fe, x)) =
(18)
xA(xx) E XA(Sx) denotes that the features of x indexed by A(f; x) are searched in the entire space.
Proof. (f) y and dx( fi) = L, according to A4, we have dx (x(0, = O.
First, we consider one direction (0, fi) contradiction.
r(0,A(52, and we prove this by
If the conclusion does not hold, r00, A f2, x)) O, which means
Xx ERAC12 10(x) y =
max
(19)
Together with (2) = O, which means
max x( A(f(2
10(z) y = 0.
(20)
we will have
max XEX
10(x) y| 0,
(21)
which is f(x) y for any x E P.
This contradicts with the premises in A4 (0 is not a constant function).
Second, consider the other direction r(0, A(f2, x))
= (1) and prove
this by showing its contrapositive proposition holds. (Its contrapositive proposition is dx (0, fi) = 0 r(0, A(f2, x)) O, because, by definitions, and d can only be evaluated as 0 or 1).
Because of A3 (A(f1, x) n A(/2,, x) = 0), we have dx (1, 2 A(J2, x)). thus the contrapos- itive proposition be shown trivially.
B.2 THEOREM 3.1 AND PROOF
Theorem. With Assumptions A1-44, with probability as least 1 8, we have
cp, (0) s εp, (0) + c(0) (10)), n,
(22)
1 E(x,)j(XXY)), 1[0(x) = (
where c(0) = --=-
11
Proof.
(0)
= Σ
1
1((x) - f(x)l
(23)
n (xx))((X Y),,
=1
Σ
(1[0(x) f(x)))
(24)
(x)))((XY)))
=1
Σ
(1[((x) ((x))124 = + [[(()) = f(x) = 11)
(x)
(25)
=1
Σ
(1[0(x) (()))(2200, fa) =0] Σ
1[((x) =
=1]
(x)))(XXYYp,,
(xx))(XXYY),,
(26)
-2((0) 1
Σ
[[(x)) [(x))r(0,AA())))
(27)
"
())))((LY)),
15

---

Under review as a conference paper at ICLR 2021
where the last line used Lemma B.1
Thus, we have
Ea(0) =(0) + !
Σ
[[((x) = f(x))
(28)
Ti (x,))E(X, Y)p,
where
=a(0)=1-- E
=
(1[((x) = (ex fa) =0]),
(29)
(x,))E(X.Y)r,
which describes the correctly predicted terms that 9 functions the same as fa and all the wrongly pre- dicted terms. Therefore, conventional generalization analysis through uniform convergence applies, and we have
(0) S (a( + 6(O@), n)
(30)
Thus, we have:
CP. 60),
[[((x) = = A(fp: 6(0)), n.
(31)
n2
(x,))E(X, Y)r,
B.3
THEOREM 3.2 AND PROOF
Theorem. With Assumptions A2-A5, and if - fa E O, we have
D.P....P (x,))E(X,Y)r Y),,
1
Σ
110(x) y)r(0,
(32)
n
where c(0) = - EE 11((x) = (ir(O,AAss x)) and (P,, is defined as in (
Proof. By definition, g(x) E OAA
g(x) = (xx) @ (x(x) for some 0, 0 E O, together with
Lemma 2 and Lemma of Ben-Daviie al. 2010), we have
De P.)
max 6,
Σ
10(x) 8 d'(x)l
Σ
10(x) - 8 (xx]l
(33)
Y),,,
(xx))
Σ
10(x) [2(x)]
Σ
10(x) f2(x)]
(34)
(x)))
(x,))((X
Σ
[[((x) = yl Σ
1[((x) yl
(35)
(xx))E(X.Y)p,
(x,) Y)p
Σ
[0(x) = ()0 11
Σ
[0(xx)
(x)))
(xx))(X)
(36)
+ Σ
10(x) y ((. (x,))((X
Σ
1[(xx) y]1[r(0, A.000 x)) 0
(x,))((X,Y)
(37)
Σ
[0(x) = 30r(0,AAFF)))
Σ
[[((x) = y)r(0, A(Fp x))
Y))
(Y)))
(38)
2c(0)
Σ
[[((x) =
(39)
())
16

---

Under review as a conference paper at ICLR 2021
First line: see Lemma 2 and Lemma of (Ben-Davite et al. 2010).
Second line: 1 - fa E θ and we use fs to denote fa.
Fifth line is result of using that fact that
1[((x) = y][[((0, A(fx: x)) =0 =
Σ
[0(xx) = y00[r(0, =
(xx))E(XXY),,
(),,,
(40)
as result our assumptions. Now we present the details of this argument:
According to A4, if (xx = de (9. fa) (0. fp) = O. Since r(0, A(fp: x)) 0, d- (8, fp) cannot be 0 unless is constant mapping that maps every sample 0 (which will contradicts A4). Thus, we have d, (0, Sa) = 0.
Therefore, we can rewrite the left-hand term following
Σ
1[((x)
= 0J
Σ (x)))
[[((x) (0, =0
(XX))(XXX))))
(41)
and similarly
Σ
[[((x)
=0
E
1[((x) yllld 0] (42)
(x,Y)E(X.Y));
(x)))E(X.Y)p;
We recap the definition of (s)),,), thus (0, fa) 0 means
fa) xEX:mA(f.x) (A((a=)))
max
10(z) - fa(z)) 0
(43)
Therefore d0, fa) = 0 implies ((((x) y), and
[0(z) fa(z)]
BA(fax) xA(fax)
(44)
Therefore, we can continue to rewrite the left-hand term following
[[((x) = ()] fa) =
Σ
1[((z) - Sa(z)] =
E
1(0(x) - fa(x)]
(x,))((X)Y) Y),
(x.)) Y)P.
(x,
(45)
and similarly
Σ
1[((x) y) =0
[[((z) fa(z))
(46)
(x.y) (. Y)p.
(xx))(X,Y)r,
where z denotes any z E and 2A(/2x)) = xA(Jax)-
Further, because of A5, have
[[((2) fa(z)] =
Σ
[[((x) - fa(x)).
(47)
(x,)))(XYY)))
(x,))((X Y)p,
Thus, we showed the (40) holds and conclude our proof.
17

---

Under review as a conference paper at ICLR 2021
C ADDITIONAL EXPERIMENTS
C.I THEORETICAL SUPPORTING EXPERIMENTS
Synthetic Data with Spurious Correlation We extend the setup in Figure thetic dataset to test our methods. We study a binary classification problem over the data with n samples and p features, denoted as X Rnxp, For every training and validation sample we generate feature as following:
I to generate the syn-
10.
Fisjs 3p/4
N(1
and y 1, w.p. P if 3f p, and y O, if w.p.
x
N--1,1)
w.p. P
()
In contrast, testing data are simply sampled with x) N 1).
To generate the label for training, validation, and test data, sample effect size vectors 31 RP/4 and B2 RP// whose each coefficient is sampled from Normal distribution. We then generate two intermediate variables:
c = (9)
1/4
$1 and
2 ( = -X)
1/
Then we transform these continuous intermediate variables into binary intermediate variables via Bernoulli sampling with the outcome of the inverse logit function (g (-)) over current responses, i.e.
Ber( and
r2 (c) BeBr(g (c
Finally, the label for sample i determined as (() = 1(r1 (0)) where ll is the function that returns 1 if the condition holds and 0 otherwise.
Intuitively, we create dataset of features, half of the features are generalizable across train, validation and test datasets through a non-linear decision boundary, one-forth of the features independent of the label, and the remaining features are spuriously correlated features: these features are correlated with the labels in train and validation set, but independent with the label test dataset. There are about en train and validation samples have the correlated features.
Figure 3: Results of Synthetic Data with Spurious Correlation. Each panel represents one setting. Five methods are reported each panel. For each method, four bars are plotted: from left to right, (0), εp, (0), εp, (0) + c(0). and Ep, (0) + De-
Results are reported in Figure 3 where each setup we ran random seeds and report the mean and standard deviation. We train vanilla method, minimum supervision method with different hyperparamter p. and an oracle method that uses data augmentation randomized the previously known spurious features. The results show the advantage of the new method consistently, although still not compared to the method with prior knowledge. We also calculate the c(0) as we perform adversarial attacks over the spuriously correlated feature space, also calculate De defined in S). We compared εp, (8) + c(0) and ēp, (0) + De and the results suggest that clearly c(0) offers a more accurate assessment of the target error than De.
18

---

Under review as a conference paper at ICLR 2021
C.2 REAL IMAGE CLASSIFICATION: MORE DETAILS
The main experiment setup follows the setup of (Bahng et al. 2019). and the setup can be con- veniently replicated by the GitHub repo associated with the paper (Bahng al. 2019). Although results of ImageNet-C are also reporeted by (Bahng et al.] 2019). their github repo does not pro- vide the corresponding replication scripts. so we also skip the information. Additionally, we report another ImageNet level test set that is independently collected, and has only sketch images.
We rename the "bias" and "unbiased" in (Bahng al. 2019) to "standard accuracy" and "weighted accuracy" to align the terms we use in this paper and also help to explain the results. Intuitively, "weighted accuracy" refers to the evaluation mechanism that the test samples with unusual texture will have more weights.
Again, following the setup in (Bahng et al., 2019). the base network is ResNet, and we compare with the vanilla network, and several methods that are designed to reduce the texture bias: including StylisedIN (Geirhos et al. 2019), LearnedMixin (Clark et al. 2019). RUBi (Cadene et al. 2019 and ReBias (Bahng et 20199).
Finally, to get the reported performance, our MS method uses an extra heuristic, such as we only optimize (16) for half of the batch, and optimize the other batch with the vanilla training ( Despite this heuristic used, the main message remains: MS method, as a method that does not use the knowledge of the spurious correlated features, can compete with the methods that use the knowledge explicitly.
19


Reviews:
[{"review_id": "lVMafYBqZF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nQuality: \nPros:\n- The role of spuriously correlated features in causing poor generalization in the target domain is well described.\n\nCons:\n- The derived bound consider unrealistically simple setup and makes strong assumptions that makes the derived bound practically useless.\n- Even if all the assumptions are right the suggested solutions for training a \"robust\" model is very ad-hoc and unlikely to be robust.\n\nClarity:\nThe paper is poorly written and most parts of the paper are difficult to follow.\n\nOriginality/Significance:\nAlthough deriving a generalization bound  as a function of spurious features is original, due to strong assumptions, the derived bound is unlikely to have much practical value and  make a significant impact in the field.\n\n\nDetailed Comments:\nThis work approaches cross-domain generalization from a relatively easier and somewhat unrealistic direction and does not consider the more challenging setup of emerging classes/subclasses in the target domain nor it discusses the effect of class imbalance on generalization. \n\nIt was not clear how invariance to spurious function can be imposed in ERM when the spurious function is not known during training.\n\nA3 is a very strong assumption. Two labeling functions both predicting same labels on the training set yet not sharing even a single feature is not a very practical assumption.\n\nSection 3.2 is hastily written and does not read well.\n\nIt is not clear what was so interesting about this finding \"This argument may also align with recent discussions suggesting that reducing the model complexity can improve cross-domain generalization (Chuang et al., 2020).\" \nIn the context of structural/empirical risk minimization Vapnik has demonstrated (more than 40 years ago) that model complexity can be reduced by reducing VC dimension, which in turn will tighten the VC bound and improve generalizability on test data. This  result is distribution independent and thus would hold nicely for cross-domain generalization setting  considered in this paper as well (no emerging classes in the test data). \n\nIt is not immediately clear what the benefit of the added c(\\theta) term would be. Comparing equation (6) with (2) we now have the test error upper bounded by a term that is larger by c(\\theta), which makes the bound loose compared to equation (2). This is a standard problem for domain-adaptation. So, I don't consider this as a flaw but some insight would have been useful. \n\nA5 (Sufficient of training samples) is also a very strong assumption that can not be easily justified in real-world domain adaptation problems.  Although theorem 3.2 shows that the extra term c(\\theta) is less than or equal to the empirical term in the standard domain adaption error bound, the difference may not be practically significant.\n\nIt is not clear under what conditions r(\\theta;A(fp; x))=1 suggest an adversarial sample. Possibly only when an adversarial feature is generated by perturbing spurious features that don't overlap with nonspurious features? However, an adversarial sample can also be generated by perturbing only a small fraction of non-spurious features. \n\n\"In short, in practice, while we do not know fp, we usually know A(fp; x) through intuition or common sense, such as texture or background of images. Thus, the estimation is to test the whether the model switches its correct prediction when these features are perturbed over the possible space.\"\nFor modern machine learning problems that use semantically rich and high-dimensional features (i.e., ResNet) such a task can quickly become impractical. One cannot easily and uniquely identify the subset of features to perturb as there will be an impractically large number of combinations to try.\n\nIn section 4.2 the solution that was suggested involves learning only with the top \\rho fraction of features ranked according to the gradient. This is somewhat counter-intuitive as this approach will inevitably create sudden spikes in the gradient between different epochs which is expected to make the gradient less useful for feature selection. The loss function being minimized is not the same between different epochs.", "extra_scores": {}, "extra_text": {}}, {"review_id": "a5j2J3Td1g", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the problem that spurious features in the training set can cause accuracy drop in the test phase. They formalize a generalization error bound for this setup and provide two solutions, one principled solution with the knowledge of spurious correlated features and one minimal supervision (MS) method without knowing this information, based on their bound. They also have some experimental results demonstrating the effectiveness of their proposed MS method.\n\nPros:\n\n-The problem of spurious correlations widely exists in real-world machine learning tasks. This paper starts from analyzing the generalization with spurious correlation, comparing with existing results in domain adaptation, and then links to several existing solutions and provides their solution without requiring the spurious features knowledge.\n\nCons:\n\n-The paper seems to interchangeably use spurious correlation, confounding factors and dataset bias. But my feeling is that they have different definitions in specific problem settings. \n\nIn this paper, spurious correlation means there exists another labeling function other than the true mapping function that can achieve zero training error, but cannot generalize well on test data. But the dataset bias may generally mean that the training data (joint) distribution differs from the test data (joint) distribution. So in the latter case, the differences can only lie in labels, for example, noisy training labels. Those differences should be carefully discussed.\n\n-Another concern is that it is hard to verify the correctness of the selected active set defined in Eq 3. In the paper, it is said that those features are usually selected by intuition or common sense. It is still unclear to me how to select them in practice, and how this affects the performance.\n\n-There are some typos in Section 4.2 regarding f_d and f_p, for example, in the first sentence, f_b should be f_p. In my understanding, the proposed method in Eq 16 uses both f_d and f_p associated features, how to guarantee that the model does not learn spurious correlated features only, in the extreme case?\n\nOverall take\n\n-The paper studies an interesting problem and provides some useful analysis, but some unclear parts need to be clarified. And the notations should be carefully checked.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_O-Ua6b7_e", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary:\nThis paper formalizes a new generalization error bound for the problem of spurious correlation (a.k.a. confounding factors or dataset bias) and shows that it is tighter than the well-established domain adaptation one under realistic assumptions. The analysis leads to a set of solutions linking to established solutions. It further proposes a practical solution that does not require explicit knowledge of spurious correlated features as the established ones need. \n\n################################################\n\nReasons for score:\nIn general, I like the flow of the paper. It does a decent job of explaining the proposed new bound, how it is superior to the existing bound, how it is connected to the general formulation and existing methods. The proposed practical method also shows promising results. However, I have some concerns / questions regarding its assumptions. Also, several typos need to be fixed.\n\n################################################\n\nPros:\n\n+mostly well-written and easy to follow\n\n+the proposed bound is tighter than the existing one under reasonable assumptions\n\n+experiment results support the proposed theoretical result as well as the effectiveness of the proposed method.\n\n+the proposed method works surprisingly well\n\nCons:\n\n-some assumptions might be a bit strong and not very clear stated\n\n-not negligible number of typos\n\n\n################################################\n\n\n\n\n1.The x used in the theorems seem to assume the features to be disentangled but this is usually not the case. Features are usually mixed together.\n\n2.The author(s) claim that “in practice, we usually directly have the knowledge of\nA(fp; x), i.e., the spuriously correlated features that fp relies on, such as texture of images.” However, this is usually not the case.\n\n3.In A5 the exact equality seems to be a strong assumption.\n\n4.I have a relatively hard time bridging the proposed method and the theorem. In particular, I think most of the time, the model is a combination of both f_p and f_d rather than either f_p or f_d?\n\n################################################\n\nTypos / Formatting issues:\n-“Thus, the estimation is to test the whether the model”, extra “the”\n\n-sec 4.2 first line, “f_b”, typo; second line, “what the best”, missing “is”\n\n-sec 5.1, “We also Figure 1 to data with p features”??? I did not understand this sentence.\n\n-Figure 3 is too small and the texts on x-axis are barely readable. Besides, there are five different colors used in the figure while there are only four in the legend.\n\n-several equations in the appendix goes beyond the boundary\n\n-eq17 “in”, typo\n\n################################################\n\nquestions:\n\n-Thm3.2 What is the intuition of having the assumption 1-f_s \\in \\Theta?\n\n-What are the details of the attack the paper uses (e.g. number of steps, epsilon, etc.) for the experiment shown in Figure2? I wonder if the attack becomes stronger, will the performance gap become even larger?\n\n-How do you estimate D_\\Theta in practice for the baseline method?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-GLfXdj_e6u", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary:  \nThe paper considers the problem of spurious features affecting robustness of machine learning models. The paper's goal is to show that if we can make assumptions on the knowledge of the spurious features that may exist in the dataset, we can better analyze the error on potential test sets. \n\nStrengths:  \n1. The paper provides a good overview of different approaches within the areas of robustness and the \"spurious features\" phenomena, and the framing makes intuitive sense (albeit restrictive -- the belief that there always exists one labeling function for the source/target domain rules out situations where there is a temporal shift, or there are unobserved variables, yet we would still want a robust model)\n\n2. The experimental results on MS seem promising, given that the method does not use knowledge of the spurious features, although somewhat limiting in terms of the range of experiments/datasets. \n\n\nWeaknesses: \nIn general, I unfortunately found the paper very difficult to follow, with Sections 3 and 4 taking so much space that the experiments in Section 5 were very hastily described. One suggestion I would have would be to ground the analysis in an example -- perhaps that in Figure 1 -- to make it easier to discuss the different variables in the analysis without becoming too abstract and confusing.\n\n1. I found the notation in particular quite difficult to follow through, with many terms introduced and explained in a rather rushed way. Particularly, I think section A2 could be  improved, including a more detailed description of d_x(\\theta, f) and providing more intuition for r(\\theta, A(f,x)). It would also help to break down some of the definitions, such as c(\\theta) in (10)  into English descriptions first to help follow the different components.    \n\n2. There is little justification / explanation for why theta^(t-1) can be considered a good substitute f_d/ f_p?  \n\n3. I found the description of the experiments very limited. For example in the synthetic data experiment, what does it mean that \"f_p is simpler\"? What do the \"multiple choices\" refer to?\n\n4. At times, the authors mix up terms such as confounding factors, spurious correlations, spurious features, dataset bias, etc. but there are subtle differences in how the different works the authors cite define these terms. For example, dataset bias can be due to a lot more factors than spurious features learned by the model, while confounding factors can describe variables not included in the data at all, potentially making learning the right model from the data impossible. I think the authors should characterize the types of features they consider a lot more rigorously.  \n\nRecommendation:  \nI recommend rejection. While the ideas and intuition are definitely promising directions, I believe the paper in its current state needs significant improvement with respect to clarity.\n\nFurther Comments \n- For Figure 2, it might be better to plot 1.0-Error to make it easier to visualize all bars. \n- I was a bit confused by the difference between the P_s/P_t and (X,Y)P_s / (X,Y)P_t notations.  \n \nTypos:  \npg. 1\n\"we require the distributions of study similar but different\" --> \"to be similar but different\"  \n\"this scenario surly exists in real world tasks\" --> surely, it would also be good to describe such examples in the text (and why this is a reasonable assumption to make).    \n\"because human will nonetheless be able to agree\" --> humans \npg. 3 \n\"basic assumptions needed to derived (2)\" --> derive \npg. 6\n\"Thus, the estimation is to test the whether the model\" --> test whether\npg. 7\n\"we then test how the new method we introduced in comparison to previously developed methods\" --> how the new method we introduced performs in comparison to    \n\"We also Figure 1 to data with p features\" --> unclear ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers raised concerns about the paper's clarity (interchangeable use of subtly different terms, notation, typos), and how realistic/practical certain assumptions are. The authors are encouraged to incorporate the reviewers' detailed comments for a future submission.
Decision: Reject