Understanding the failure modes of out-of-distribution generalization
Authors: Vaishnavh Nagarajan
Anders Andreassen
Behnam Neyshabur
Venue: ICLR 2021 Poster (2021)
Keywords: out-of-distribution generalization
spurious correlations
empirical risk minimization
theoretical study

Abstract: Empirical studies suggest that machine learning models often rely on features, such as the background, that may be spuriously correlated with the label only during training time, resulting in poor accuracy during test-time. In this work, we identify the fundamental factors that give rise to this behavior, by explaining why models fail this way even in easy-to-learn tasks where one would expect these models to succeed. In particular, through a theoretical study of gradient-descent-trained linear classifiers on some easy-to-learn tasks, we uncover two complementary failure modes. These modes arise from how spurious correlations induce two kinds of skews in the data: one geometric in nature and another, statistical. Finally, we construct natural modifications of image classification datasets to understand when these failure modes can arise in practice. We also design experiments to isolate the two failure modes when training modern neural networks on these datasets.

Published as a conference paper at ICLR 2021
UNDERSTANDING THE FAILURE MODES OF OUT-OF- DISTRIBUTION GENERALIZATION
Vaishnavh Nagarajan"
Anders Andreassen
Camegie Mellon University
Blueshift, Alphabet a a @jandreessee@@ooogoe... com
vaishnavh@es cmu. edu
Behnam Neyshabur Blueshift, Alphabet neyshabur@pooole.comm com
ABSTRACT
Empirical studies suggest that machine learning models often rely on features, such as the background, that may be spuriously correlated with the label only dur- ing training time, resulting poor accuracy during test-time. In this work, we identify the fundamental factors that give rise to this behavior, by explaining why models fail this way even easy-to-learn tasks where one would expect these models succeed. In particular, through a theoretical study of gradient-descent- trained linear classifiers on some easy-to-lcarn tasks, we uncover two complemen- tary failure modes. These modes arise from how spurious correlations induce kinds of skews in the data: one geometric in nature, and another, statistical in na- ture. Finally, we construct natural modifications of image classification datasets to understand when these failure modes can arise in practice. We also design ex- periments to isolate the two failure modes when training modern neural networks on these datasets.'
INTRODUCTION
machine learning model in the wild (e.g., self-driving car) must be prepared make sense of its surroundings in rare conditions that may not have been well-represented in its training set. This could range from conditions such as mild glitches in the camera to strange weather conditions. This out-of-distributio (OoD) generalization problem has been extensively studied within the framework of the domain generalization setting (Blanchard et al., 2011; Muandet et al., 2013). Here, the clas- sifier has access to training data sourced from multiple "domains" distributions, but no data from test domains. By observing the various kinds of shifts exhibited by the training domains, we want the classifier can learn to be robust to such shifts.
The simplest apppoestapproach to domain generalization is based on the Empirical Risk Minimization (ERM) principle (Vapnik, 1998): pool the data from all the training domains (ignoring the "domain label" on each point) and train a classifier by gradient descent to minimize the average loss on this pooled dataset. Alternatively, many recent studies (Ganin et al., 2016; Arjovsky al., 2019; Sagawa al., 2020a) have focused on designing more sophisticated algorithms that do utilize the domain label on the datapoints e.g., by enforcing certain representational invariances across domains.
A basic premise behind pursuing such sophisticated techniques, as emphasized by Arjovsky et al. (2019), is the empirical observation that ERM-based cradient-descente trainenngtt (or for convenience, just ERM) fails in characteristic way. As standard illustration, consider a cow-camel classi- fication task (Beery al., 2018) where the background happens to be spuriously correlated with the label in particular manner only during training say. most cows are found against grassy background and most camels against sandy one. Then, during test-time, the correlation is com- pletely flipped (i.e.. all cows in deserts, and all camels in meadows), one would observe that the
Work performed in part while Vaishnavh Nagarajan was interning at Blueshift, Alphabet. 1 e rewearch/ooo- fai Tures
Code available https: //g /i thub. com goog/

---

Published as a conference paper at ICLR 2021
Sportos
Souglus
Spurioux
Spurious Mesumorgin
Mileon
Majorily
Hajorit
Majoniy
should succeed.
distribution
Training distribution Acc 83
Acouracy $4.6 2
Dooen Grose
Invonont
Pvenent
distribulian Accuracy 72.5 # 7%
Boyes optinnal
Comels
Mojoriy
Mioors
Acourapy 7.5
classller ofr faik.
Yot, classiterss prochie fail.
(a) Earlier work: Partially prodictive invariant feature
(b) This work: Fully predictive
(c)
CIFARIO spuriously colored lines
(d) OoD accuracy drop despite no color-label correlation
invariant feature
Existing theory can explain why classifiers rely on the spurious feature when the invariant feature is in itself not informative enough (Fig 1a). But when invariant features are fully predictive of the label, these cxplanations fall apart. E.g., in the four-point-datasee of Fig 1b, one would expect the max-margin classifier to easily ignore spurious correlations (also Sec 3). Yet, why do classifiers (including the max-margen max-margin) rely on the spurious feature, in so many real-world settings where the shapes are perfectly informative of the object label (e.g., Fig 1c)? We identify two fundamental factors behind this behavior. In doing so, we also identify and explain other kinds of vulnerabilities such the in Fig 1d (see Sec 4).
Figure I: Unexplained OoD failure:
accuracy of ERM drops drastically. Evidently, ERM, in its unrestrained attempt at fitting the data, indiscriminately relies on all kinds of informative features, including unreliable spurious features like the background. However, algorithm that carefully uses domain label information can hope to identify and rely purely on invariant features (or "core" features (Sagawa et al., 2020b)).
While the above narrative is oft- motivation behind developing sophisticated OoD general- ization algorithms, there is little formal explanation as to why ERM fails in this characteristic way. Existing works (Sagawa et al., 2020b; Tsipras et al., 2019; Arjovsky al., 2019; Shah et al., 2020) provide valuable answers to this question through concrete theoretical examples: however, their ex- amples critically rely on certain factors to make the task difficult enough for ERM to rely on the spurious features. For instance, many of these examples have invariant features that are only par- tially predictive of the label (see Fig la). Surprisingly though, ERM relies on spurious features even in much easier-to-lean tasks where these complicating factors are absent such as in tasks with fully predictive invariant features e.g., Fig Ic the Waterbirds/Cellbb examples in Sagawa et al. (2020a) or for that matter, in any real-world situation where the object shape perfectly determines the label. This failure in easy-to-learn tasks, as we argue later, is not straightforward to explain (see Fig 1b for brief idea). This evidently implies that there must exist factors more general and fundamental than those known so far, that cause ERM to fail.
Our goal in this work is to uncover these fundamental factors behind the failure of ERM. The hope is that this will provide a vital foundation for future work to reason about OoD generalization. Indeed, recent empirical work (Gulrajani & Lopez-Paz, 2020) has questioned whether existing alternatives necessarily outperform ERM on OoD tasks; however, due to lack of theory, it is not clear how to hypothesize about when/why one algorithm would outperform another here. Through our theoretical study, future work can hope to be better positioned to precisely identify the key missing components in these algorithms, and bridge these gaps better solve the OoD generalization problem.
Our contributions. To identify the most fundamental factors causing OoD failure, our strategy is to (a) study tasks that are "casy" succeed at, and (b) to demonstrate that ERM relies on spurious features despite how easy the tasks are. More concretely:
1. We formulate set of constraints on how our tasks must be designed so that they are easy to succeed at (e.g., the invariant feature must be fully predictive of the label). Notably, this class of casy-to-learn tasks provides both a theoretical test-bed for reasoning about OoD generalization and also a simplified empirical test-bed. In particular, this class encompasses simplified MNIST and CIFAR 10-baaed classification tasks where we establish empirical failure of ERM.
2. We identify two complementary mechanisms of failure of ERM that arise from how spurious correlations induce two kinds of skews in the data: one that is geometric and the other statistical. In particular, we theoretically isolate these failure modes by studying linear classifiers trained by
2

---

Published as a conference paper at ICLR 2021
gradient descent (on logistic/exponentaal loss) and its infinite-timen time-trained equivalent, the max- margin classifier (Soudry et al., 2018; Ji & Telgarsky, 2018) on the casy-to-leam-- leaal--tassss.........
3. We also show that in any easy-to-learn task that does not have these geometric or statistical skews, these models do not rely on the spurious features. This suggests that these skews are not only a sufficient but also necessary factor for failure of these models in easy-to-learn tasks.
4. To empirically demonstrate the generality of our theoretical insights, we (a) experimentally vali- date these skews in range of MNIST and CIFAR1O- tasks and (b) demonstrate their effects on fully-connected networks (FNNs) and ResNets. We also identify and explain failure in scenar- ios where standard notions of spurious correlations do not apply (see Fig Id). We perform similar experiments on a non-image classification task in App E.
RELATED WORK
Spurious correlations. Empirical work has shown that deep networks find superficial ways to predict the label, such as by relying on the background (Beery al., 2018; Ribeiro al., 2016) or other kinds of shortcuts (McCoy et al., 2019; Geirhos et al., 2020). Such behavior is of practical concern because accuracy can deteriorate under shifts in those features (Rosenfeld al.. 2018; Hendrycks & Dietterich, 2019). It can also lead to unfair biases and poor performance on minority groups (Dixon et al., 2018; Zhao al., 2017; Sagawa et al., 2020b).
Understanding failure of ERM. While the fact that ERM relies on spurious correlations has be- come empirical folk wisdom, only a few studies have made efforts to carefully model this. Broadly, there are two kinds of existing models that explain this phenomenon. One existing model is to imag- ine that both the invariant and the spurious features are only partially predictive of the label (Tsipras et al., 2019; Sagawa et al., 2020b; Arjovsky et al., 2019; Ilyas al., 2019; Khani & Liang, 2020), as a result of which the classifier that maximizes accuracy cannot ignore the spurious feature (see Fig Ia). The other existing model is based on the "simplicity bias" of mudient--esceet based deep network training (Rahaman et al., 2018; Neyshabur et al., 2015; Kalimeris et al., 2019; Arpit et al., 2017: Xu et al., 2019; des Combes et al., 2018). In particular, this model typically assumes that both the invariant and spurious features are fully predictive of the label, but crucially posits that the spurious features are simpler learn (e.g.. more linear) than the invariant features, and therefore gradient descent prefers to use them (Shah et al., 2020; Nar et al., 2019; Hermann & Lampinen, 2020).
While both these models offer simple-to to-understand and useful explanations for why classifiers may use spurious correlations, we provide a more fundamental explanation. In particular, we empirically and theoretically demonstrate how ERM can rely on the spurious feature even in much easier tasks where these explanations would fall apart: these are tasks where unlike in the first model (a) the invariant feature is fully predictive and unlike in the second model, (b) the invariant feature corre- sponds to a simple linear boundary and (c) the spurious feature is not fully predictive of the label. Further, go beyond the max- margin settings analyzed in these works to analyze the dynamics of finite-time gradient-descen trained classifier on logistic loss. We would also like to point the reader to concurrent work of Khani & Liang (2021) that has proposed different model addressing the above points. While their model sheds insight into the role of overparameterization in the context of spurious features (and our results are agnostic to that), their model also requires the spurious feature to be "dependent" on the invariant feature, an assumption we don't 't require (see Sec 3).
Algorithms for OoD generalization. Due to the empirical shortcomings of ERM, a wide range of sophisticated algorithms have been developed for domain generalization. The most popular strat- egy is to learn useful features while constraining them to have similar distributions across domains (Ganin et al., 2016; Li et al., 2018b; Albuquerque et al., 2020). Other works constrain these features in way that one can learn a classifier that is simultaneously optimal across all domains (Peters et al., 2016; Arjovsky et al., 2019; Krueger et al., 2020). As discussed in Guirajani & Lopez-Paz (2020), there are also many other existing non-ERM based methods, including that of meta-learning (Li et al., 2018a), parameter-sharing (Sagawa et al., 2020a) and data augmentation (Zhang et al., 2018). Through their extensive empirical survey of many of the above algorithms, Gulrajani & Lopez-Paz (2020) suggest that ERM may be just competitive as the sfte-offthee-se But we must emphasize that this doesn't 't vindicate ERM of its failures but rather indicates that we may be yet to develop a substantial improvement over ERM.
3

---

Published as a conference paper at ICLR 2021
3 EASY-TO-LEARN DOMAIN GENERALIZATION TASKS
Below, we first set up the basic domain generalization setting and the idea of ERM. Then, in Sec- tion 3.1, we formulate a class of Nomain-generrlizatte tasks that are in many aspects "easy" for the learner (such as fully informative invariant features) what exactly makes task "easy" will be discussed in Section 3.1). This discussion sets the ground for the later sections to show how ERM can fail even in these easy tasks, which will help uncover the fundamental factors behind its failure.
Notations. Consider an input (vector) space X' and label space V E (-1,1). For any distribution D over X' x V, let pD (-) denote its probability density function (PDF). Let H denote class of classifiers h : X - R. Let the error of h on DD be denoted as (p(h) == [xxx))>((((x) < 0).
The domain generalization setting and ERM. In the domain generalization setting, one considers an underlying class D of data distributions over X' x y corresponding to different possible domains. The learner is given training data collected from multiple distributions from DD For ERM-based learner in particular, the training data will be pooled together, so we can model the data as com- ing from a single (pooled) distribution Prrinn which for simplicity, can be assumed to belong to I. Given this data, the learner outputs a hypothesis h E HI that is tested on new distribution Diest picked from D. This can be potentially modeled by assuming that all test and training distributions are drawn from a common hyper-distribution over D. However, this assumption becomes pointless in most practical settings where the training domains are not more than three to four in number (c.g.. PACS (Asadi et al., 2019), VLCS (Fang et al., 2013)), and therefore hardly representative of any hyper-distribution. Here, the problem becomes as hard ensuring good performance on a worst-case test-distribution without any hyper-distribution assumption; this boils down to mini- mizing maXDEn LD (f). Indeed, most works have studied the worst-case setting, both theoretically (Sagawa et al., 2020b) and empirically (Arjovsky et al., 2019; Sagawa et al., 2020a).
Similarly, for this work, we focus on the worst-case setting and define the optimal target function At to be h-- arg min MaxDED LD(h). Then, we define the features that this "robust" classifier uses as invariant features Xm, (e.g., the shape of the object), and the rest as spurious features X.p (e.g., the background). To formalize this, we assume that there exists mapping t Xnw x Xpp + X such that each D E DD is induced by distribution over Xus X Asp (so we can denote any as (Xinv: x.))). With an abuse of notation we will use pD (-) to also denote the PDF of the distribution over Xim x Ky.. Then, the fact that Xyp are features that ht does not rely on, is mathematically stated as: VXmn and V Xap * Xxp. ("D((nn Xxp) = h²( (Xnv. xx))). Finally, we note that, to make this learning problem tractable, one has to impose further restrictions; we 'Ill provide more details on those when we discuss the class of easy-to -t--arm domain generalization tasks in Sec 3.1.
Empirical failure of ERM. To guide us in constructing the easy-to- easy-to-learn tasks, let ground our study in a concrete empirical setup where an ERM-based linear classifier shows OoD failure. Specif- ically, consider the following Binary-MNIS' based task, where the first five digits and the remaining five digits form the two classes. First, we let & be the identity mapping, and so x = (Xinv: X.p) Then, let Xinv be random ReLU features representation of the MNIST digit i.e., if Xraw represents the MNIST image, then X = ReLU(WXXet where W is a matrix with Gaussian entries. We make this representation sufficiently nigh-dimensional so that the data becomes linearly separable. Next, we let the spurious feature take values in {+B, - B} for some B > O, imitating the two possible background colors in the camel-cow dataset. Finally, on Drrain for any y. we pick the image X from the corresponding class and independently set the "background color" Tap so that there is some spurious correlation i.e., Pro... [x'p y > 0) > 0.5. During test time however, we flip this correla- tion around so that Prz... [0 y > 0] = 0.0. In this task, we observe in Fig 2a (shown later under Sec 4) that as we vary the train-time time spurious correlation from none (Pry,,. [Tap y > 0 = 0.5) to its maximum (PrD.m [Zisp y > 0] = 1.0), the OoD accuracy of max-margin classifier progres- sively deteriorates. (We present similar results for a CIFAR1Ó 10 setting, and all experiment details in App C. Our goal is now theoretically demonstrate why ERM fails this way (or equivalently, why it relies on the spurious feature) even in tasks as "casy-to-learn" as these.
3.1 CONSTRAINTS DEFINING EASY-TO-LEARE DOMAIN-GENERALLE GENERALIZATION TASKS.
To formulate a class of easy-to-learn tasks, we enumerate a set of constraints that the tasks must satisfy; notably, this class of tasks will encompass the empirical example described above. The
4

---

Published as a conference paper at ICLR 2021
motivation behind this exercise is that restricting ourselves to the constrained set of tasks yields stronger insights - it prevents us from designing complex examples where ERM is forced to rely on spurious features due to ffresmmmndaa factor. Indeed, each constraint here forbids unique, less fundamental failure mode of ERM from occuring in the easy-to-learn tasks.
Constraint 1. (Fully predictive invariant features.) For all D D. Lp(h") =
Arguably, our most important constraint is that the invariant features (which is what h* purely relies on) are perfectly informative of the label. The motivation is that, when this is not the case (e.g., as in noisy invariant features like Fig Ia or in Sagawa et al. (2020b); Tsipras et al. (2019)), failure can arise from the fact that the spurious features provide vital extra information that the invariant features cannot provide (see App A for more formal argument). However this explanation quickly falls apart when the invariant feature itself is fully predictive of the label.
Constraint 2. (Identical invariant distribution.) Across all D E D. (X is identical. This constraint demands that the (marginal) invariant feature distribution must remain stable across domains (like in our MinAT--MNIST example). While this may appear to be unrealistic, (the exact distribution of the different types of cows and camels could vary across domains), we must empha- size that is easier make ERM fail when the invariant features are not stable (see example in App A Fig 4a).
Constraint 3. (Conditional independence.) For all D E D, Xap 1 Ximlly.
This constraint reflects the fact that in the MNIST example, we chose the class label and then picked the color feature independent of the actual hand- werdtertteen digit picked from that class. This prevents us from designing complex relationships between the background and the object shape to show failure (see example in App A Fig 4b or the failure mode in Khani Liang (2021)).
Constraint 4. (Two-valued spurious features.) We set Xxp = IR and the support of Tap in Diain is {-B, +B}.
This constraint captures the simplicity of the cow-camel example where the background color is limited yellow/green. Notably, this excludes failure borne out of high-dimensional (Tsipraa al., 2019) or features.
continuous-valuee (Sagawa et al., 2020b; Shah et al., 2020) spurious
Constraint 5. (Identity mapping.) & is the identity mapping i.e., x = (Xavv Xap) This final constraint', also implicitly made in Sagawa et al. (2020b); Tsipras al. (2019), prevents ERM from failing because of hard-to-disene dii-eta-disentaglle representation (see example in App A Fig 4c).
Before we connect these constraints to our main goal, it worth mentioning their value beyond that goal. First, as briefly discussed above and elaborated in App A, each of these constraints in itself corresponds to a unique failure mode of ERM, one that is worth exploring in future work. Second, the resulting class of easy-to-learn tasks provides theoretical (and a simplified empirical) test-bed that would help in broadly reasoning about OoD generalization. For example, any algorithm for solving OoD generalization should at the least hope to solve these casy-to-learn tasks well.
Why is it hard to show that ERM relies on the spurious feature in easy-to-learn tasks? Consider the simplest easy-to-learn 2D task. Specifically, during training we set Tinv = y (and Constraint is satisfied) and Top to be BB with probability p E [0.5. 1) and -yB with probability - p (hence satisfying both Constraint 3 and 4). During test-time, the only shifts allowed are the distribution of Tap (to respect Constraint 2). Observe from Fig 1b that this distribution has support of the four points in [11,+1} x {-B, +B} and is hence an abstract form of the cow-camel dataset which also has four groups of points: (a majority of) cows/camels against grass/sand and (a minority of) cows/camels against sand/grass. Fitting max- max-mn classifier on Dusin leads us to a simple yet key observation: owing to the geometry of the four groups of points, the max-margin classifier has no reliance on the spurious feature despite the spurious correlation. In other words, even though this dataset distills what seem to be the core aspects of the cow/camel dataset, we are unable to reproduce the corresponding behavior of ERM. In the next two sections, we will try to resolve this apparent paradox.
Nooe that the discrete-value restriction holds only during training. This is that, in our experiments. we can study two kinds of test-time shifts, one within the support (-B, +B) and one outside of it (the vulnerability to both of which hoils down to the level reliance on Tsp))
'hhe rest our discussion would hold even if & corresponds to any orthogonal transformation of (Niv; Xsp), But for simplicity, we'll work with the identity mapping.
since the algorithms we study
5

---

Published as a conference paper at ICLR 2021
Spurious
Training distribution
1.08
8.88
Minarit
Majorlyy * wetk
Accuracy
0.75
8.86
Accuracy 83.7 %
Invariant
0.58
0.84
8.25
Doas
Test distribution
Dost
Majorly
Minonty
0.00
0.7
0.5
0.00
100
408
1680
6480
Mox-margin
Accuracy 57.6% = 19.5 %
No.
of datapoints
classifer
(a) OOD failure in Soo 3 Binury- MNIST example
(b) lg norm of max-margin
(c) Geometric failure
(d) CIFAR 10 example with sparious
mechanism
Fig 2a demonstrates failure of the max- max-margin classifier in the easy- to-learn Binary-MNIST task of Sec 3. Fig 2b forms the basis for our theory in Sec by showing that the randoo--features--asedd max-margin has norms increasing with the size of the dataset. In Fig 2c, we visualize the failure mechanism arising from the "geometric skew": with respect to the Xav Xav- based classifier, the closest minority point is farther away than the closest majority point, which crucially tilts the max-marginn classifier towards Wssp > 0. Fig 2d, as further discussed in Sec 4, stands an example for how wide range of OoD failures be explained geometrically.
Figure 2: Geometric skews:
4 FAILURE DUE TO GEOMETRIC SKEWS
A pivotal piece in solving this puzzle is particular geometry underlying how the invariant features in real-world distributions are separated. To describe this, consider the random features representa- tion of MNIST (i.e., X and fit max- max-margin classifier on it, i.e., the least-norm Winv that achieves a margin of y (Win- Xinv + b) 2 1 on all data (for some b). Then, we'd observe that as the number of training points increase, the E2 norm of this max-margin classifier grows (see Figure 2b); similar observations also hold for CIFAR10 (see App C.2). This observation (which stems from the geom- etry of the dataset) builds on ones that were originally made in Neyshabur et al. (2017); Nagarajan & Kolttr (2017; 2019) for norms of overparameterized neural networks. Our contribution here is to empirically establish this for a linear overparameterized model and then to theoretically relate this to Ool failure. In the following discussion, we will take this "increasing norms" observation as given"). ), and use it to explain why the max-margin classifier trained on all the features (including (pp) relies on the spurious feature.
Imagine every input Xny to be concatenated with feature Tsp E [B that spuriously corre- lated with the label i.e., Pr[zz.p > 0] > 0.5. The underlying spurious correlation implicitly induces two disjoint groups in the dataset S: majority group Smaj where sspp y > 0 e.g.. cows/camels with green/yellow backgrounds, and minority group Smin where Tep y < e.g., cows/camels with yellow/green backgrounds. Next, let Wall E Xin denote the least-norm vector that (a) lies in the invariant space and (b) classifies of S by a margin of at least 1. Similarly, let W Wmin denote least-norm, purely-invariant vector that classifies all of Smin by margin of at least 1. Cru- cially, since Smin has much fewer points than S, by the "increasing-norm" property, we can say that Wanlll- We informally refer to the gap in these lg norms as geometric skew.
Min
|min|// || <<
Given this skew, we explain why the max margin classifier must use the spurious feature. One way to classify the data is to use only the invariant feature, which would cost an &g norm of ||aall But there another alternative: use the spurious feature as a short-cut to classify the majority of the dataset Smnj (by setting Wsp > 0) and combine it with Wmin to classify the remaining minority Smin- Since ||Wmin|l < [Wanll, the latter strategy requires lesser Eg norm, and is therefore the strategy opted by the max-margin classifier. We illustrate this failure mechanism in 2D dataset in Fig 2c. Here, we have explicitly designed the data to capture the "increasing norms" " property: the distance between aarely-invariant classifier boundary (i.e., vertical separator through the origin) and the closest point in Smaj is smaller than that of the closest point in Smin- In other words, a
classifier
'To clarify, we take the "increasing norms" observation as a given in that we don't 't provide an explanation for why it holds. Intuitively, we suspect that norms increase because we more datapoints, we also sample rarcr/harder training datapoints. We hope future work can understand this explain better.
6

---

Published as a conference paper at ICLR 2021
would require much greater norm classify the majority group by margin of 1 than to classify the minority group. We can then visually see that the max mar-mn classifier would take the orientation of diagonal separator that uses the spurious feature rather than vertical, purely- aurely-invariant one.
The following result formalizes the above failure. In particular, for any arbitrary casy-to-leam task, provide lower and upper bounds on Wap that are larger for smaller values of [|Wiinll// || |- For readability, we state only an informal, version of our theorem below. In App B.1, we present the full, precise result along with the proof.
Theorem 1. (informal) Let Hi be the set of linear classifiers, h(x)) WineXinv + WsppTsp b. Then for any task satisfying all the constraints in Sec 3.1 with B = 1, the max-margin classifier satisfies:
1 1 2 [Wnin|
/ //waall S Wap (Waall/|/wall 1.
A salient aspect of this result is that it explains the varying dynamics between the underlying spu- in the elassifier. First, as the correlation increases (Prr [Tap y > 0j + 1.0), the size of the minority group decreases to zero. Then, we empirically know that |/mmiall /I/ |Wallll progressively shrinks all the way down to O. Then, we can invoke the lower bound which implies that sisp grows to ss 1. This implies serious vulnerability to the test-time shifts: any flip in the sign of the spurious feature can reduce the original margin of by value of 2 Wap ~ 2 (since B 1 here) making the margin negative (implying misclassification) On the other hand, when spurious correlations diminish (PrD.. [Ta y > 0] - 0.5), , the value of || [ grows comparable to Wan and our upper bound suggests that the spurious component must shrink towards O, thereby implying robustness to these shifts.
rious correlation and spurious-feature-rlllaee
Broader empirical implications. While our theorem explains failure in linear, easy-to-learn set- tings, the underlying geometric argument can be used to intuitively understand failure in more gen- eral settings i.e., setting where the classifier is non-linear and/or the task is not easy-to-leam. For illustration, we identify a few such unique non-linear tasks involving the failure of a neural network. The first two tasks below can be informally thought of easy-to easy-to-learn tasks
In Fig Ic, we consider a CIFARIO task where we add line to with its color spuriously correlated with the class only during training. The 2 10% OoD accuracy drop of a ResNet here, we argue (in App 1.3. arises from the fact that it takes greater norms for the ResNet to fit larger proportions CIFARIO.
In Fig 1d, we consider colored Cats vs. Dogs task (Elson et al., 2007), where majority of the datapoints are blue-ish and a minority are green-ish. During testing, we color all datapoints to be green-ish. Crucially, even though there is correlation between the label and the color of the images, the OoD accuracy of an ResNet drops by 2 20%. To explain this, in App. C.3.3, we identify an "implicit", non-visual kind of spurious correlation in this dataset, one between the label and a particular component of the difference between the two channels.
Next, we enumerate two not-easy-to-leane tasks. Here, one of the easy-to-learn constraints is dis- obeyed significantly enough to make the task hard, and this is essential in causing failure. In other words, the failure modes here correspond to ones that were outlined in See 3.1. Nevertheless, we ar- gue in App C.3 that even these modes can be reasoned geometrically as a special case of Theorem The two not-easy-to -o-aa-to- tasks are as follows:
In Fig 2d, we add a line to the last channel of CIFARIO images regardless of the label, and make the line brighter during testing resembling a camera glitch, which results in 2 27% drop in a ResNet's accuracy. We geometrically argue how this failure arises from breaking Constraint 5,
In App C.3.5, we consider MNIST setting inspired by Tsipras et al. (2019), where failure arises (geometrically) due to high-dimensional spurious features (breaking Constraint 4).
We hope that these examples, described in greater detail in App C.3, provide (a) a broader way to think about how spurious correlations manifest, and (b) how a variety of resulting failure modes can be reasoned geometrically.
$ 'Noe that although technically speaking these tasks do break Constraint 4 (as the spurious feature does not take two discrete values) this not essential the failure.
7

---

Published as a conference paper at ICLR 2021
5 FAILURE DUE TO STATISTICAL SKEWS
Having theoretically studied max-margin classifiers, let us now turn our attention to studying linear classifiers trained by gradient descent logistic/exponential loss. Under some conditions, lin- early separable datasets, these classifiers would converge to the max-margin classifier given infinite time (Soudry et al., 2018: Ji & Telgarsky, 2018). So it is reasonable to say that even these classifiers would suffer from the geometric skews, even if stopped in some finite time. However, are there any other failure modes that would arise here?
To answer this, let us dial back to the casiest-to-learn task: the setting with four points {-1,+1} x {-B, +B}, where in the training distribution (say D2-dim), we have Tiav y and Tap to be yB with probability p E [0.5. 1) and -yB with probability 1 -pp Here, even though the max-margin does not rely on upp for any level of spurious correlation p E [0.5, 1) - there are no geometric skews here after all - the story is more complicated when we empirically evaluate via gradient descent stopped in finite time L. Specifically, for various values of p we plot Wir/ // + vs. (here, looking at Wsp alone does not make sense since the weight norm grows unbounded). We observe in Fig 3a that the spurious component appears to stagnate around a value proportional to p. even after sufficiently long training, and even though it is supposed to converge to O. Thus, even though max- max-margin doesn't 't fail in this dataset, finite-time-stoppedd gradient descent fails. Why does this happen?
To explain this behavior, partial clue already exists in Soudry et al. (2018); Ji & Telgarsky (2018): 8): gradient descent can have a frustratingly slow logarithmic rate of convergence to the max- mar-mn ie.. the ratio Wusp Wine| could decay zero as slow as 1/In However, this bound is a distribution- independent one that does not explain why the convergence varies with the spurious correlation. To this end, we build on this result to derive a diistibutioon-speifff convergence bound in terms p. that applies to any easy-to-learn task (where Xnv may be higher dimensional unlike in D2-dim). For con- venience, we focus on continuous- timmu gradient descent under the exponential loss exp(-yh(x)) (the dynamics of which is similar to that of logistic loss as noted in Soudry et al. (201 8)). Then we consider any easy-to-leamd task and informally speaking, any corresponding dataset without geomet- ric skews, so the max-mnrgin wouldn't 't rely on the spurious feature. We then study the convergence B// ".. (f).x.. X.., to 0 i.e., the rate at which the ratio between the output of the spurious com- ponent that of the invariant component converges to its corresponding max- mar-mnarin value. We show that the convergence rate is ( In., crucially scaled by an extra factor that monotonically increases in 10, oo) as function of the spurious correlation, p E [0.5, 1), thus capturing slower convergence for larger spurious correlation. Another notable aspect of our result is that when there is no spurious correlation (p 0.5). both the upper and lower bound reduce to 0, indicating quick convergence. We provide the full statement and proof of this bound in App B.2. For completeness, we also provide a more precise analysis of the dynamics for a 2D setting under both exponential and logistic loss in Theorem 5 and Theorem 6 in App B.2. Theorem 2. (informal) Let H. be the set of linear classifiers h(x) = Winv Xinv + Wpp Then, for any easy-to-learn task, and for any dataset without geometric skews, continuous-ting gradient descent training of Win (t) Xinv + Wsp (t) to minimize the exponential loss, satisfies:
rate (t)(t)
Ω
Vell Int
23
(1)B Wan (f) (()
In 1-
where p == Pre (Tsp y > 0] E [0.5, 1).
The intuition behind this failure mode is that in the initial epochs, when the loss exp (-yw- x) on all points are more or less the same, the updates 1/181-E, -(x.))s yx yx exp(-yw- x) roughly push along the direction, 3/181- E(x.)Es yx. This is the precise (mis)step where gradient descent "absorbs" the spurious correlation, as this step pushes Wap along pB (1 D) = (2p 1)B. While this update would be near-zero when there is only little spurious correlation (p 0.5), it takes larger values for larger levels of spurious correlation (p R 1). Unfortunately, under exponential-type losses, the gradients decay with time, and so the future gradients, even they eventually get rid of this absorbed spurious component, take exponentially long time to do
Broader empirical implications. We now demonstrate the effect of statistical skews in more gen- eral empirical settings consisting of a non-linear easy-to-learn task learned using neural network.
TThe overall accuracy CIFAR10 is low because even though |Sconl 50k and Seap 455k, the number of unique samples here is just 5k. See App C.4.2 for more explanation.
8

---

Published as a conference paper at ICLR 2021
compaNEnt
8.8
P
1.8
0.0
0.6
0.95
Accuracy
9.875
8.75
0.8
9.625
0.3
0.2
Control
Contral
0.6
Experisental
Experimental
0.0
1000
2000
3000
4000
Epoch
Spurious feature scale
Spurious feature scale
(a) Failure gradient-deseent
(b) FCN MNIST
(c) ResNet CIFARIO
Figure: 3: Statistical skews: In Fig 3a, we plot the slow convergence of wi// VVz, tw E [0, under
logistic loss with learning rate 0.001 and training set of 2048 from D2 dim with B = 1. In Fig 3b and Fig 3c, we demonstrate the effect of statistical skews in neural networks. Here, during test-time shift both the scale of the spurious feature (from its original scale of 0.1 as marked by the red triangle) and its correlation. Observe that the network trained on the catistically-skewee Sexp is more vulnerable to these shifts compared to no-skew Scon- 6
Isolating the statistical skew effect is however challenging in practice: any gradient-descent-trainee model is likely to be hurt by both statistical skews and geometric skews, and we' have to some- how disentangle the two effects. We handle this by designing the following experiment. We first create a control dataset Scon where there are no geometric or statistical skews. For this, we take a set of images Sun (with no spurious features), and create two copies of it, Smaj and Smin where add spurious features, positively and negatively aligned with the label, respectively, and define Scon = Smaj U Smin- Next, we create an experimental dataset Seep with statistical skew in it. We do this by taking Sco and duplicating Saaj in it that the ratio |Smag] |Smial becomes 10: 1. Importantly, this dataset has no geometric skews, since merely replicating points does not affect the geometry. Then, if we were to observe that (stochastic) gradient descent Sexp results in greater ppurious-fcatur--rllinnc than Scon. we would have isolated the effect of statistical skews.
Indeed, demonstrate this in easy-to-learn tasks. First, consider Binary-MNIST task learned by an fully-connected network. Here, we concatenate a spurious channel where either all the pixels are "on" or "off". Second, we consider (multiclass) CIFARIO task (where we add spuriously colored line) learned using a ResNet (He et al., 2016). In Fig 3, we demonstrate that training on Seup leads to less robust models than on Soon in both these tasks. In other words, gradient descent on Sexp leads to greater spurious spurious-feature- feature-reliane skews in practice. More details are provided App C.4.
thus validating the effect of statistical
CONCLUSIONS AND FUTURE WORK
We identify that spurious correlations during training can induce two distinct skews in the training set, one geometric and another statistical. These skews result in two complementary ways by which empirical risk minimization (ERM) via gradient descent is guaranteed to rely on those spurious correlations. At the same time, our theoretical results (in particular, the upper bounds on the spurious component of the classifier) show that when these skews do disappear, there is no failure within the considered tasks. This suggests that within the class of easy-to- tasks and for gradient-descent trained linear models, the above discussion likely captures all possible failure modes.
However, when we do venture into the real-worde deep models, many other kinds of failure modes would crop up (such as the ones we enumerate in Sec 3, in addition to the fundamental ones mentioned above). Indeed, the central message of our work is that there is one unique mechanism by which classifiers fail under spurious correlations, even in the simplest of tasks. This turn has a key practical implication: in order to improve our solutions to OoD generalization, it would be valuable figure whether or not unified solution approach is sufficient to tackle all these failure mechanisms. While we outline some solutions in App D, hope that the foundation we have laid in this study helps future work in better tackling out-of-distribution challenges.
face more complicated tasks and use non-line -ineernear,
Acknowledgements. We thank Hanie Sedghi for providing useful feedback the draft.

---

Published as a conference paper at ICLR 2021
REFERENCES
Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H. Falk, and loannis Mitliagkas. Generalizing unseen domains via distribution matching, 2020.
Martín Arjovsky, Léon Bottou, Ishaan Guirajani. and David Lopez-Pazz Invariant risk minimization. 2019. URL http: /awpvv.a/vvvv//////////e..//.avv arg/abs///...ooooo /asas/1900 19779997...0 02893.
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron C. Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Proceedings of Machine Learning Research. PMLR, 2017.
Nader Asadi, Mehrdad Hosseinzadeh, and Mahdi Eftekhari. Towards shape biased unsupervised representation learning for domain generalization. htts/1990.0825.. 2019.
Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Computer Vision ECCV 2018 15th European Conference, Proceedings, Part XVI, 2018.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks new unlabeled sample. In Advances Neural Information Processing Systems 24, 2011.
Remi Tachet des Combes, Mohammad Pezeshki, Samira Shabanian, Aaron C. Courville, and Yoshua Bengio. On the learning dynamics of deep neural networks. 2018, URL UtLattp::/arxxxcco abs/ /1099. 06848.
Lucas Dixon, John Li, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Measuring and miti- gating unintended bias in text classification. In Proceedings of the 2018 AAAI/ACM Conference AI, Ethics, and Society, AIES 2018. ACM, 2018
Jeremy Elson, John (JD) Douceur, Jon Howell, and Jared Saul. Asirra: A captcha that exploits interest-aligned manual image categorization. In Proceedings of 14th ACM Conference on Com- puter and Communications Security (CCS). Association for Computing Machinery, Inc., October 2007. URL https: https://ww.micrroofte wwwsoott wwtp:tt.ooooonoaaeeeeeeeeeeee http:///eeeaaaeeeeeeeee/ee/aaaaa esirra-a-aee www.aaaattaaataaaaaaaa htt.ppppp............eeeaaaaaaaa
Chen Fang, Ye Xu, and Daniel Rockmore. Unbiased metric learning: On the utilization of mul- tiple datasets and web images for softening bias. In IEEE International Conference on Computer Vision, ICCV 2013, 2013.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor S. Lempitsky. Nomain-adversarre training of neural networks. J. Mach. Learn. Res., 2016.
Robert Geirhos, Jöm--enrik Jacobsen, Claudio Michaelis, Richard S. Zemel, Wieland Bren- del, Matthias Bethge, and Felix A. Wichmann. Shortcut learning in deep neural networks. abs/2004.07780, 2020. URL https: www.iii.oog/aabao.ooo tabss20044 07780.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. 2020. URL https: /atas///arxiii org/ abs 2000000000000000 01434.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Dan Hendrycks and Thomas G. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net, 2019.
Katherine L. Hermann and Andrew K. Lampinen. What shapes feature representations? exploring datasets, architectures, and training. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, 2020.
10

---

Published as a conference paper at ICLR 2021
Andrew Hyas, 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 32: Annual Conference on Neural Information Processing Systems 2019, pp- 125-136, 2019.
Ziwei Ji and Matus Telgarsky. abs/1 10300000,77,, 2018.
Risk and parameter convergence of logistic regression.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin L. Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. SGD on neural networks learns functions increasing complex- ity. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, 2019.
Fereshte Khani and Percy Liang. Feature noise induces loss discrepancy across groups. In Pro- ceedings of the 37th International Conference on Machine Learning, ICML. 2020, Proceedings of Machine Learning Research. PMLR, 2020.
Fereshte Khani and Percy Liang. Removing spurious features can hurt accuracy and affect groups disproportionately. In FAcel' 221: 2021 ACM Conference Fairness, Accountability, and Trans- parency. ACM, 2021.
David Krueger, Ethan Caballero, Jörn-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Rémi Le Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex). abs/2003.00688, 2020.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Learning to generalize: Meta- learning for domain generalization. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18). AAAI Press, 2018a.
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In Computer Vision ECCV 2018 15th European Conference, 2018b.
Tom McCoy, Ellie Pavlick, and Tal Linzen. heuristics in natural language inference. In Anna Korhonen, David R. Traum, and Lluís Märquez (eds.), Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019. Association for Computational Linguistics, 2019.
Right for the wrong reasons: Diagnosing syntactic
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, 2013.
Vaishnavh Nagarajan and J. Zico Kolter. Generalization in deep networks: The role of distance from initialization. 2017.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Advances in Neural Information Processing Systems 32, 2019.
Kamil Nar, Orhan Ocal, S. Shankar Sastry, and Kannan Ramchandran. Cross-entropy loss and low-rank features have responsibility for adversarial examples. abs/1901. .0066, 2019. URL http:// /ttp:///axxiii orgo ptgg/bb/// /1/b////0 901 .08360.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In 3rd International Conference on Learning Representations, ICLR 2015, 2015. URL http: //arxaaaavvvv///////a org/ abs 1412. 6614.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring gener- alization in deep learning. 2017.
M. Palechor and A. de la Hoz Manotas. Dataset for estimation of obesity levels based on eating habits and physical condition in individuals from colombia, peru and mexico. 2019.
11

---

Published as a conference paper at ICLR 2021
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant pre- diction: identification and confidence intervals. Journal of the Royal Statistical Society Series B, 2016.
Nasim Rahaman, Devansh Arpit, Aristide Baratin, Felix Draxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron C. Courville. On the spectral bias of deep neural networks. 2018. org/ wwws/100s 08734.
URL wwtpttpptaaaaeee
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22ndACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016.
Amir Rosenfeld, Richard Zemel, and John K. Tsotsos. The elephant in the room. abs/1 0ass/1808.00 808.03305, 2018. URL http: / arxiv orgg abs/ / 11088.8000 03305.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. 2020a.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. 2020b.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. In Advances in Neural Information Processing Systems, volume 33, 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Mach. Learn. Res., 19, 2018.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In 7th International Conference on Learning Repre- sentations, ICLR 2019, 2019.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003-4
Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior of deep neural network in frequency domain. In Tom Gedeon, Kok Wai Wong, and Minho Lee (eds.), Neural Information Processing 26th International Conference, ICONIP 2019, Lecture Notes in Computer Science Springer, 2019.
Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empiri- cal risk minimization. In 6th International Conference on Learning Representations, ICLR 2018, 2018.
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017. Association for Computational Linguistics, 2017.
A CONSTRAINTS AND OTHER FAILURE MODES
Here, we elaborate on how each of the constraints we impose on the easy-to-learn tasks corresponds to eliminating particular complicated kind of failure of ERM from happening. In particular, for each of these constraints, we'll construct a task that betrays that constraint (but obeys all the others) and that causes unique kind of failure of ERM. We hope that laying these out concretely can provide a useful starting point for future work to investigate these various failure modes. Finally, is worth noting that all the failure modes here be explained via a geometric argument, and furthermore the failure modes for Constraint 5 and Constraint can be explained as a special case of the argument in Theorem 1.
Failure due to weakly predictive invariant feature (breaking Constraint 1). We enforced in Constraint that the invariant feature be fully informative of the label. For a setting that breaks this
12

---

Published as a conference paper at ICLR 2021
constraint, consider 2D task with noisy invariant features, where across all domains, we have Gaussian invariant feature of the form Tiny ~ NN,, (mv) this sort of noisy invariant feature was critically used in Tsipras et al. (2019); Sagawa et al. (2020b); Arjovsky et al. (2019) to explain failure of FRM. Now, assume that during training we have a spurious feature Jupp ~ (N,, d (say with relatively larger variance, while positively correlated with y). Then, observe that the Bayes optimal classifier on Drain is sgn (Tin//oinv + Tsp/ i.c., it must rely on the spurious feature.
However, also observe that if one were to eliminate noise in the invariant feature by setting Fine - (thus making the invariant feature perfectly informative of the label like in our MNIST example), the Bayes optimal classifier approaches sgn (Iinv), thus succeeding after all.
Failure due to "unstable" invariant feature (breaking Constraint 2). If during test-time, we push the invariant features closer to the decision boundary (e.g., partially occlude the shape of every camel and cow), test accuracy will naturally deteriorate, and this embodies a unique failure mode.
Concretely, consider domain generalization task where across all domains z'nv 2 -0.5 determines the true boundary (see Fig 4a). Now, assume that in the training domains, we see Tinv 2y or Tiny = 3y. This would result in learning a max-margin classifier of the form Tinv 2 0. Now, during test-time, if one were to provide "harder" examples that are closer to the true boundary in that Tinv = 0.5 + 0.1y, then all the positive examples would end up being misclassified.
Failure due to complex conditional dependencies (breaking Constraint 3). This constraint im- posed Tinv L Esply. Stated more intuitively, given that a particular image is that of camel, this constraint captures the fact that knowing the background color does not tell us too much about the precise shape of the camel. An example where this constraint is broken is one where Tinv and Esp share neat geometric relationship during training, but not during testing, which then results in failure as illustrated below.
Consider the example in Fig 4b where for the positive class we Tins T.p and for the negative class we set Tim + uup = -1, thereby breaking this constraint. Now even though the invariant feature in itself is fully informative of the label, while the spurious feature is not, the max-margin here is parallel to the line Tiny + Tsp and is therefore reliant on the spurious feature.
Failure mode due to high-dimensional spurious features (lack of Constraint 4). Akin to the setting in Tsipras et al. (2019), albeit without noise, consider a task where the spurious feature has D different co-ordinates. Xyp (-1.1)" 1) and the invariant feature just one Xns = {-1, 1, + +1}. Then, assume that the ith spurious feature Tsp. independently the value with probability p; and -y with probability - Pi. where without loss of generality P; > 1/2. Here, with high probability, all datapoints in S can be separated simply by summing up the spurious features (given D is large enough). Then, we argue that the max-margin classifier would provide some non-zero weight to this direction because it helps maximize its margin (see visualization in Fig 4d).
One way to see why this true is by invoking special case of Theorem 1. In particular, if we define Σ spp to be single dimensional spurious feature Zsp, this feature satisfies Tsp y 0 on all training points. In other words, this is an extreme scenario with no minority group. Then, Theorem would yield positive lower bound on the weight given to F.pp. explaining why the classifier relies on the spurious pixels. For the sake of completeness, we formalize all this discussion below:
Proposition Let be constant such that for all i, Pj > + Let D be sufficiently large so that D z 1 22 we where m is the number of training datapoints in S. Then, whh.p. of 8 over 2c the draws of S, the max-margin classifier corresponds is of the form WineTine + Wp where:
W spll
cvD
Winy
Proof. First, we'll show that on S there exists classifier that relies purely on the spurious features to separate the data. In particular, consider w'p where the ith dimension is 1/VD if p; > 1/2, and -1/VD otherwise. By the Hoeffding's inequality, we have that with high probability 1 - 6, on all
the m training datapoints, yw Xap 2 1
vD ((pp 1)
Im
LVD.
13

---

Published as a conference paper at ICLR 2021
Spurious
Spurious
Spurious
Invoriant
Σ Spurious
classifer
test time shift
Invoriont
invariant
Inveriant
Inveriant
'Tuee" classifier
Mos-morgin classilier
margin clossher
marginn clossfer
(a) Breaking Constraint 2: Unstable invariant feature
(b) Breaking Constraint 3: Conditionalyy dependent features
(c) Breaking Constraint 5: Hand-to-diieenaanlle fentures
(d) Breaking Constraint 4:
Nigh-dimensional sparions
features
Figure 4: Other failure modes: We visualize the different (straightforwardd ways in which max- margin classifier can be shown to fail in tasks where one of the Constraints in Sec 3.1 is disobeyed. More discussion in Sec A.
Now, for the max-margin classifier, assume that whn a. Further, assume that the margin con- tributed by Sa + b equals vI - amm for some m. Observe that m must satisfy m 2 VVV (as otherwise, we can replace Wap with vI - azw', to achieve better margin). Now, for the resulting margin be maximized, must satisfy VI
Failure mode due to hard-to-separate features (lack of Constraint 5) Here assumed that the feature space can be orthogonally decomposed into invariant and spurious features. Now let us imagine 2D task, visualized in Fig 4c where this is not respected in that each datapoint is written as (Tine, Tiny + TTp) assuming that Finy of structure is the example in Fig 2d where we add a line the last channel of CIFARIO 10, and then vary the brightness of the line during test-time.
and Tsp E (-0.5, 0.5). A practical example of this sort
To understand why failure occurs in this 2D example, observe that, regardless of the correlation between Tspp and y. we'd have that (Iiny + xsp) > 0. In other words, the second co-ordinate fully informative of the label. The max-margin classifier, due its bias, relies on both the first and the second co-ordinate to maximize its margin i.e., the classifier would be of the form Wi + w2 (Minn + xxp) where W2 > O. (Again, like in our discussion of the failure mode of Constraint 4, we can argue this via Thm by considering Tinv + Tsp itself as spurious feature, and by observing that there's 's no minority group here.) Hence, by assigning a positive weight to the second co-ordinate inadvertently becomes susceptible to the spurious feature that may shift during testing.
B PROOFS
B.
PROOF OF THEOREM 1 ON FAILURE DUE GEOMETRIC SKEWS
Below we provide proof for our result analyzing the failure mode arising from geometric skews in the data.
Recall that given dataset S, where the spurious feature can take only values in {-B, +B), partitioned S into two subsets Smaj and Smin where in Smaj the points satisfy Zsp >> 0 and in Smin the points satisfy zapp y
Next, we define two key notations. First, for any dataset T C S, let v(T) E Xmy denote a least-norm vector (purely the invariant space) that achieves a margin of at least 1 on all datapoints in T (we'll define this formally a few paragraphs below). Similarly, let v(T) E Xmm. denote least-norm vector that achieves a margin of at least 1 on T. and a margin of at least 0 on S (again, full definition will shortly follow). While by definition, [[v( < [T)(]]], we can informally treat these quantities as the same since empirically [|v(T)]| = [T]] We show these plots in Sec C.1 for both MNIST and CIFAR10. But importantly, both these quantities grow with the size of T. Then, by virtue of the small size of the minority group Smin. we can say that ( )I is smaller than both [ and [|v( We refer to this gap geometric skew. When this skew is prominent enough (e.g..
14

---

Published as a conference paper at ICLR 2021
(S Illmmlllllll/llllllllll 0), result below argues that the spurious component in the overall max- margin classifier must be sufficiently large (and positive). On the flip side, we also show that when the skew is negligible enough (e.g.. |/v(smn)l//lvvS[]] = 1), then the spurious component has to be sufficiently small.
To be able to better visualize these bounds, write these bounds [Bwspl (i.e., [Wsp rather than (w Then we can think of a lower bound of the form [Bwspl Z as demonstrating serious failure as shift in the correlation can adversely reduce the original margin of 1.
Before we state the result, for clarity, we state the full mathematical definition of v and v as follows. For any T S:
v(T), b(T) arg min
|/anv 1|2
Wine-ii
s.t.
g(Wine Xinv) + +b)
A (Xp) E ET
((T))(T) arg min Wiss Kiu.
||Winv||
S.t.
y (imm
Xinv) + b) 2
v (op)s ET
y (Wwi
Xinv) + +) 2 0
V ((Xin: Kep) E EST E
Using these notations, we state our full theorem and provide its proof below.
Theorem 3. Let H. be the set of linear classifiers, h(x)) Was Xiv + Wsp + Let the geometric skews in a dataset S be quamtified through the terms K1 = (v(Sm))ll/ (Sv]], K2 [Iv(Smm) \/Iv(Sm))ll and Ri = [1m(m))ll// II/1 ((5)), R2 == (1Sm))l///((smil)) Then for any task satisfying all the construints in Sec 3.1 the max-margin classifier satisfies the inequalities (where for readability, we will use C1 = 1/(21 ((S)11), 02 = 1/c211((S...1188))
Bussp 2 max 1 - 2 R1 + G.
R2 S / if
1/4
Cg. and
|Bwsp] < min
(/Kl - 1, B(((s
if K2 1.
For readability, it helps to think of c₁ and 02 small constants here (also see remark below). Fur- thermore, for readability, one can also imagine that all the x terms are numerically similar to each other.
We make a few remarks below before providing the proof.
Remark 1. For the lower bound on Uss be positive, we need e and 02 be small. This would be true when either B or [[S]] (or [[ is sufficiently large. This is intuitive: after all, if too small (say 0) there is no spurious feature effectively and therefore the max-marg max-margin has no incentive use it; similarly, if (S) is too small (say 0), then the max-margin has incentive to use any feature besides the invariant feature, which is already quite cheap.
The above result not intended to be numerically tight/upper lower bound. In fact, the proof can be tightened in numerous places which we however avoid, to keep the result and the proof simple. The bound is rather meant be instructive of the effect of the geometric skew (i.e., the gap between the max-margin norms on the minority and whole/majority dataset) on the spurious component.
Remark 2.
Proof. We present the proof of lower bound first, followed by the upper bound.
Proof lower bound. First, we will show that there exists classifier of norm I that relies on the spurious feature to create a sufficiently large margin. We'll let this classifier be of the form (SSi))))
aZIap + abmin- By the definition of (Smin), the margin of this classifier Xny + VI a
[V
on any datapoint in Smin is at least [V[S..]]
v1 BBB. Again, by the definition of ((Smin) the margin Smaj least /1 a²B. Let us pick such that these two quantities equal. Such
15

---

Published as a conference paper at ICLR 2021
an would satisfy -í-ब 2| By plugging this back, get that the resulting margin of this classifier on the whole dataset S is at least /1++411(55m.)1F In other words, this also means
B
the least norm classifier w with margin of least 1 on S has its norm upper bounded as:
(1 min) 2B2
[w| S
(1)
B
Now, assume that w (i.e., the least norm classifier with a margin of on S) is of the form WineXinv + WspTap + b. First, we derive lower bound on [appl and after that we'll show that Wsp > 0. For this we'll consider two cases, one where |wapl 2 8 (and so we already have a lower bound) and another case where WPsp < B. In the latter case, we will need the invariant part of the max- max-margin classifier, namely Winy + 6, to have to have margin of at least 1 - |BsppBB the contribution from the spurious component which is at most spp will be unable to bump this margin up to 1. Now, for the invariant part of the mar-mnn classifier to have margin of at least Wip B (a non-negative quantity since /trpp S. 1/B) on S, the norm of the (invariant part of the) classifier must be least (1 Wwp [[)] (which follows from the definition of (S)). This implies,
S; if it were any lesser,
||| 2 (1
|wsp ())(
Combining this with Eq 1, we get (1 |w B [[)]l < V (S Rearranging this gives 1
us the bound that B) Wsspl 1 2
[ [v(()
+ MM5]I Finally note that v(S) is the same as
(S). Hence we can interchange these terms in the final result (which we've done for readability) to arrive at |uspp 2 1 - 2 + cf).
What remains now is to show that Wsp > O. For this we do the same argument as above but with a slight modification. First, if Whp > 1/B, we are done. So, assume that wap I 1/B. Then, can say that the invariant part of the max-margin classifier i.e., Xin +b, must achieve a margin of W (a non-negative quantity since Wap I 1/B) specifically on Smaj. Then, by the definition of v v(Smaj). it follows that the norm of our overall max-margin classifier must be at least (1 W)pBB)llv v[ (Smai
Again, for the overall classifier to be the max max-margn margin classifier, we need (1 Wsp (B] [| (Saa))) Il S
/ (S which when rearranged gives us BWusp 2 1 v //84 ([(() The R.H.S is V(Smiil
B
at least O when I (
[+(mm)] (i.e., v E 2 R2). In other words when
Ro S / eit we have Wap 2 O.
Proof of upper bound. The spurious component of the classifier Win Xime + SspTsp + b posi- tively contributes the margin of one of the groups (i.e., one of Smin and Smay), and negatively contributes to the other group. depending on the sign of Wap On whichever group the spurious component negatively contributes to the margin, the invariant part of the classifier, Winy + b must counter this and achieve a margin of + |wsp|B. B8 To manage this, we'd require || > II). In other words, for the overall max max-marreeeeaeamm margin classifier w, (1 + Jutpp (B) min( (Smin)))))) |l. [[v(Smm)))))
we have:
||||| 2 (1 + |wm)( (B) minn[Iv((a (S Il. (Smmg)))).
(3)
At the same time, we also know from the definition of v(S) that
||w|| S [[]]-
(4)
Combining the above two equations, we can say (1+ Wap up (B) min(IIv(SS (1 < [[][)
Since are given Ra 1, it means that min( ( (Smin) [I, (Smmj)) Il) = [|v(Smin)), I[. this simplifies l| < ||v())]|, which when rearranged reaches the result Buig K1 1.
to (1 Wsp BB) (Smin))
To get the other upper bound here, observe that for Way + Wsp + b to be the overall min-norm classifier, its l2 norm, which is lower bounded by |W must not be larger than the Eg norm of v v(S).
Hence |wsppl < [-
16

---

Published as a conference paper at ICLR 2021
B.2 PROOF OF THEOREM 2 ON FAILURE DUE STATISTICAL SKEWS
Below we state the full form of Theorem 2 and its proof demonstrating the effect of statistical skews in easy-to-learn tasks. After that, we'll present more precise analysis of the same in 2D setting in Theorem 5 (for exponential loss) and in Theorem 6 (for logistic loss).
Our result below focuses on any easy-to-learn task and on corresponding dataset where there are no geometric skews. Specifically, we consider a dataset where the invariant features have the same empirical distribution in both the majority subset (where Txp y > 0) and the minority subset (where Fap y/ < 0). As result, in this setting the max-man max-mnrgin classifier would not rely on the spurious feature. This allows us to focus on a setting where we can isolate and study the effect of statistical skews.
For the sake of convenience, we foeus on the exponential loss and under infinitesimal learning rate, and classifier initialized to the origin.
Theorem 4. (full form of Theorem 2 ) Let H be the set of linear classifiers, h(x) Win - Wpp Consider any task that satisfies all the constraints in Section 3.1. Consider dataset S drawn drownfrom 'D such that the empirical distribution of Xux given Tsp y > 0 is identical to the empirical distribution of Xiw given Tap y < O. Let Wine (t)) + Wsp (t) stp be initialized to the origin, and trained with an infinitesimal rate to minimize the exponential loss dataset S. Then, for any (x. v) E S, we
have:
ctp + pm(lp) Ω
In
(t)
_ In(t II)
MIn(t+1)
Wine (t) Xinv
where:
p denotes the empirical level of spurious correlation, p Eix)es [ y 0] which
without generality assumed satisfy p E [0.5,1),
M denotes the maximum value of the margin of the max-margin classifier on i.e. M maxxes W where W is the max-margin classifier on S.
2(2M-1 1)
B
Proof. Throughout the discussion, we'll denote Wins and Wsp(t) as just Win and Wap for readabil- ity.
Let Smin and Smai denote the subset of datapoints in S where Ttp y < 0 and Zsp y > 0 respectively. Let D.... denote the uniform distribution over Xinv induced by drawing x uniformly from Smin- By the assumption of the theorem, this distribution would be the same if x was drawn uniformly from Smmy. Then, the loss function that is being minimized this setting corresponds to:
L( (Winv, Wap) = pE..
Dim (Wis Xis t (8) + (1 - P))EE Xin D...
(Nar Win -.
where p E [0.5, 1). Here, the first term is the loss on the majority dataset (where Top = yBB and the second term is the loss on the minority dataset (where vigp = -yB).
The update on Wsp can be written as:
sg
E
Xin D'n
WanXaa]]
.B.
(pe- B.,B (1 u
To study the dynamics of this quantity, we first bound the value of Wine Winr(t)xinn.
Bounds on Wine (f)xim The result from Soudry et al. (2018) states that we can write w(t)
w IIn(1 + t) + p(t) where w is the max-margin classifier and is a residual vector that is
bounded as [|((t]]22 (Win: 0) (i.c., only relies on the invariant feature), we can infer from this that Wine (t) Win In(1 t) (t) where again (1)]l2 (InIn))) For sufficiently large can
O(n Since the max-margin classifier here is of the form w
17

---

Published as a conference paper at ICLR 2021
say that In Int < In(1 + t). This would then imply that for all S, |W (t) Xinv in (t) [m + t), Wm (t) In(1 I + t)]- Since the max max-margin classifier has a margin be- tween 1 and M on the training data, this implies that, for sufficiently large t and for all E S:
Wine Xivl E [0.5 In(1 + 1); 2M In(1 + +(]].
Next, we bound the dynamics of Wsp.
Upper bound on Wisp- To upper bound Wep. we first note that पंs = 0 only when Wsp 28 In T Furthermore, risp is decreasing function in Wap. Hence, for any value of Wsp that is less than 2B In Thpp Wap 2 0 and for any that is greater than this value, vi'up I 0. So, we can conclude that when the system is initialized O, it can never cross the point Wsp 28 In 1-pp In other words, for all i, (t) I 2B In P. Combining this with the lower bound on Winv (f), we get the desired result.
Lower bound on Usp- lower bound visp via the upper bound on Wap as:
Wsp
Den
[e Win B
pe pe - p) 1-
p
Xixa
E
Den LiWukir
- p)) B. (pe 1B vp(1-
Xiza
Next, since we have that for all x E S, |Wir Xinl 22M
(1 1)2M B. (pe-wnB vp(1 - p)
Wsp
Rearranging this and integrating, get:
1
/ B (1 1j2m dt,
dwisp 2
pe B vp(1 p)
(Since 2M 2 2, we can integrate the right hand side as below)
In(p - e B Vp(l-p) p)) + In(p - vp(1-p) ByP(1 - p)
(1+ ( (j)--)
1
B/p(1 p)
2M
since for a sufficiently large i, the final paranthesis involving / will at least be half,
/p(1 - 22² 2
In
e
2
2M -1
we can further lower bound the right hand side by applying the inequality x 2 In(x + 1) for positive
T,
1 V p( - 1)
In
2 In
1
e
2 2M -
Taking exponents on both sides and rearranging,
P
8
1+
2
(2M-1)
2(2M
1
+p
Wlpp
In 2(2M
B2
B
Vp(l -
B2
Combining this with the upper bound on Wine (l), we get the lower bound on (1)) //i//wnlll (t).
18

---

Published as a conference paper at ICLR 2021
B.3 PRECISE ANALYSIS STATISTICAL SKEWS FOR A 2D SETTING UNDER EXPONENTIAL LOSS
We now consider the 2D dataset 22.dim considered in the main paper, with the spurious feature scale set as B = 1, and provide a more precise analysis of the dynamics under exponential loss. This analysis provided for the sake of completeness the proof is self-contained and does rely on the result of Soudry et al. (2018); Ji & Telgarsky (2018). In the next section, we perform a similar analysis for logistic loss.
Theorem 5. Under the exponential loss with infinitesimal learning rate, linear classifier Wine Din + sep (t) initialized to the origin and trained on 22 with satisfies:
In (11-2)) (3-22 In [ + mt,
Wsp(t)
In (P/(-p))
where p = Pro Fp y > 0] [0.5,
Winy (t)
In(1 + 2t)
Proof. Throughout the proof, we'll drop the argument from Way (1) and wsp (1) for convenience. The loss function that is being minimized in this setting corresponds to:
[Win, Wsp) = pe Wwpp + (1 - p)e (um (1mp
where p 0.5. Here, the first term is the loss the majority dataset (where Isp yB) and the second term is the loss on the minority dataset (where Tsp = -B)).
Now the updates Whnw and Wsp given by:
Winy pe (10m wip) + (1 p)e -(wie -
ssp pe (10m twsp)
(1 p)e (1i 18pp)
which means:
(way + Wap)
2pe (win twp)))
dt
d( Winn Wap) 2(1 - p)e (wim wpp)
dt
Thus, by rearranging and integrating we get:
Winv + Wsp
In(1 + 2pt)
Winv
W. In(1 + 2(1 pp))
Winv 0.5(In(1 + 2pt) + In(1 + 2(1 -p)t)
W.p 0.5(In(1 2pt) +0(1+2(1 p)t)).
Now let us define 3(1) Wap/ Win::
B(t) : Wsp
In(1 + 2pt) In + 2(1 p)t) In(1 2pl) In(1 2(1 p)()
(5)
Wine
To bound this quantity, we'll consider two cases, 2 and < First let consider > 1. We begin by noting that the numerator (t)(t) is increasing with time t. This is because.
1 2pt
Wsp (t) = In
+ 2(1 p)t
19

---

Published as a conference paper at ICLR 2021
1)t
1 1 2(1 - pp)
2(2p- 2(2p-1)
11 1 + 2(1
Here, the term 2(2p-1) is increasing with / due to the fact that the numerator is non-negative (p 2 0.5) and the denominator is decreasing with t. So, given that wsp(t) is increasing, we can say that for all & 2 1:
++2(1-p)
In 1+2p 3 2p
In 1+2p
B(t)
Wsp(1)
3 3-2p
Winw (t)
In(1 + 2(1 - p)t) + 1n(1 + 2pt)
In + 3t)
Here we have used the fact that the denominator can be upper bounded as (n(1+2(1 - -p)() + +I((1 + 2pt) S (n(1 + 2/ 4(1 p)pt) s In(1 + 3t).
In 2p
In
1+2e 3-2p
Now, for any t < 1, we can show that 3(t) 2 B(1) = 1m 1P---)--"))
This follows if we
can show that (()) is decreasing for t 2 0. Taking its derivative with respect to time, we get:
3 (In(1 + 2pt) + In(1 + 2(1 p)())
2p
2(1-p)
142pt (1+2(1-p)1)
(In(1 + 2p() + 1n + 2(1 p){)}²
(In(1+ 2pt) - Im 2(1 p)t)
[I+2pt]
2p
+
1+2 p11
2(1 pp)
(In + 2pt) + 1n(1 + 2(1 p)t))
In(1 ( (1(1+2(1-3)) (601-p):- p) I+2pr
2p In(1 2pt) I+2(1-p)
2(1-p)
-2.
(In(1 + 2pt)
+ In 2(1 p)
In(1 + 2(1 1el1-pp.. p)t)
1
- In( + 2pt)
-2. (In(1 + 2pt) + In(1 + 2(1 - p){))²
2
2(1-p)
The sign of the above quantity is equal to the sign of:
1
1
In(1 + + p)t)
+1) IIn(1 + 2pt)
2p +t
2(1 p)
1
In
+t
+t
Im
p)
)
+t
2(1 p)
2(1 -
2(1 p)
2(1 p)
:=f
In
+
+1
- In
+
2p
2p
2p
2p
==
Now, we show that f(x) = (a In + t) function:
(n) (x+t)ln (1+ 4) is a non-increasing
f((x) in (1+
x +1
1 1+
20

---

Published as a conference paper at ICLR 2021
In
1+
1
t
S 0.
Now since p 2 0.5, and f is non-increasing. /
(x-ー)) -
Subsequently, 3 S 0.
Therefore, ((1) B(1) for any / E [0.
Upper bound. For an upper bound on ((), we note that since Wss(1) is always increasing Wap S lim;-roc (ts(() = } On the other hand Wins (1) = In(1 + 2/ + 4p(1 - p){²) 2 In(1 + 21).
Combining these inequalities, we get:
In (2 1 B(t) - In + 2t)
B.4 ANALYSIS OF STATISTICAL SKEWS FOR A 2D SETTING UNDER LOGISTIC LOSS
While the Theorem and Theorem were concerned with the exponential losses, as noted in Soudry al. (2018), the dynamics under logistic loss are similar (although harder to analyze). For the sake of completeness, we show similar results for logistic loss in the same 2D setting as Theorem 5.
Theorem 6. Under the logistic loss with infinitesimal learning rate, a linear classifier Way (f) + (sp(t) initialized to the origin and trained on D2-dim with B satisfies for sufficiently large t (where p == Presa [xs y > 0] E [0.5, 1}):
min (,,
( In(t +
2 In 2
3-2p
Wis (1)
Y In In In(0.5t + 1)
P
Wine
Proof. Here, the loss function is of the form:
WWine Wssp p log((1 + (wp) (1 log(1 (wi map)
where p 2 0.5. Now the updates on Winv and Wepp are:
WWpp
6 (Wir
thnn + e (Wie twpg)
+ (1 p)
+ e (Miee - Wig
(w)))))p
6 (Wier Mo
Wsp
(1 p)
+ e (Wir + twlg))
+ e (Ulier - Wiy
which means:
d( Win + Wsp)
e (Wam+
1 2p
2p + f(
dt
(1 wwp)
d( Win Wop)
(W mlp))
2(1 p)
1 + (W wap) =2(1 p)
dt
1 + c( wag
Solving for this, we get:
Winy Wap + Ww
2pt +
21

---

Published as a conference paper at ICLR 2021
Winv
Wspp + "im = - p)t + 1.
We first derive useful inequalities. First, we argue that forall 6,
Wep(1) 2 0.
(8)
This is because the point where (sp(t) 0, uisp(t) 2 system can never reach values of Wap < 0.
2p-1 1 "mn
2 0 (since 0.5). Hence, the
Next, we have for all 6,
Wine (1) E [0, In(1 +1].
(9)
We can show this by summing up Eq 6 and 7
2winv + e Wan conntug twp + E Whn ewin-Wy Wiy = 2t +
2winn + 2V
6 -w < 2t + 2
210an + 2e u' < 21 + 2
and since tinnv 2 0, and Wine (t) O, Wime (t) 2 O.
2m < +2
Next, we show:
Wsp (t) - 2(1 p)t + 1
(1 - p)
S 2
(10)
2pt + 1
To show this, divide Eq 6 by Eq 7, get:
Winv + Wap + Min
2(1 - p)t +
Wine Wsp + e Mia - Wip
2pl +
(2(2p- - 1)t) + (2(2p-
1) + (2pt + 1)e ux = e u 12 ([(1-))++]]ug
since by p 2 0.5, Eq and Eq 9 the first two terms are positive,
(2pt + 1)e wmm u6 - (2(1 p)t + 1)e Wim Whp
200 < 2(1 - p)t +
2pt +
This proves the first inequality. The second inequality follows from the fact that 2(1-p)t41 in- creasing with t so applying lim + oo gives us an upper bound.
2pt+1
Finally, rewrite Equation and Equation 7 to get:
Whnv
Wsp (2 + 1 (Win + Wap))
(11)
Winy Wap = In(2(1 - p)6 + 1 (Winy Wap).
(12)
Adding and subtracting these, we get different form for the dynamics of these quantities:
Winv = (2pt (Winy + Wsp)) + In(2(1 - p)t + (Wim. wisp)) ))
(13)
Wap (2p() (Win Wsp)) 1n(2(1 p)t (Winn WWis))
(14)
22

---

Published as a conference paper at ICLR 2021
Lower bound. To prove a lower bound on Wsp (st/ (t), we'll first lower bound Wspp. Observe that:
2pt + (Winy + Wsp
(1p(1) = 2 2(1 p)t + (Wins Wssp
In
1 In 1 2(1 - p)t + (Winv Wsp)
2(2p 1)1 211lpp
2
Now, since Wsp upper bounded by a constant (Eq 10), for sufficiently large I, the numerator of the second term inside the In will be positive, and can be lower bounded by (2p 1)t. Then, let us consider two scenarios. Either that Wep > Wine in which case we already have lower bound on (t)), or that Wep Winv- In the latter case, we can lower bound the above as:
(2p 1)
Wsp (t) In 1
2(1 +
Since the right hand side is an increasing in t, we can say that for sufficiently large t 2 1,
(2p 1)
Wap (t)
2 2
In
+
2(1 p) +
2
In
3 2p
Combining this with Eq 9 we get for sufficiently large i, either
2 In 2p
Wspp
Wine (t)
In + 1)
Wip (t) or
1.
Upper bound. To upper bound Wip (ts(t)/ (m) (t), we'll lower bound Wine (t):
Wine 0.5(In(2pl + (Wime + Wsp)) + In(2(1 p)) + 1 (Winy Wsp))
Since by Eq Wine (t) E [o, In(t + 1)] and by Eq 10, (sp(() E [o, In 1-2), for sufficiently large t, linear terms within the terms dominate and so, for large
Wha 2 (In(0.5 2pt
ln.0. +
Combining this with Eq 10, we get, for large
In Le
Wep (t)
p
Winn (t)
In(0.5t + 1)
C MORE ON EXPERIMENTS
Common details: In all our MNIST-based experiments, we consider the Binary- classifica- tion task (Arjovsky et al., 2019) where the first five digits (0 4) need to be separated from the rest
23

---

Published as a conference paper at ICLR 2021
(5 to 9). Unless specified otherwise, for this we train a fully-connected three-layered ReLU network with a width of 400 and using SGD with learning rate 0.1 for 50 epochs. In all our CIFARIO baasee experiments, unless stated otherwise, we consider the 10-class classification problem, and train ResNetV1 with a depth of 20 for 200 epochs. All values are averaged at least over fives runs. Finally, when we describe our datasets, we'll adopt the convention that all pixels lie between 0 and 1,
C.I. RANDOM FEATURE EXPERIMENTS FROM SECTION 3.1
For the random features based experiment on Binary MNIST in Section 3.1, consider 50k ran- dom ReLU features i.e., Xivv Rel (WwWW//W) where W is a 50k: x 784 matrix (and so this is well overparameterized for dataset sizes upto 6400). Each entry here is drawn from the normal distribu- tion. We set the spurious feature support to be {-100, 100]. which is about // 1/10th the magnitude of || We also conduct similar experiments on two-class CIFARIO and report similar OoD accuracy drops in Fig 5a. Here, we use the first two classes of CIFARIO, as against grouping five classes together into each of the classes. This is because on the latter dataset, the random features representation has poor in-distribution accuracy to begin with.
C.2 INCREASING NORM EXPERIMENTS FROM SECTION 4
The main premise behind our geometric skews argument is that as we increase the number of data- points, it requires greater norm for the model to fit those points. We verify this for random features models on Binary-MNIST and two-class CIFARIO in Figs 5b, Sc.
While the theory is solely focused on linear classifiers, we can verify this premise intuitively for neural network classifiers. However, for neural networks, the notion of margin not well-defined. Nevertheless, proxy measure, look at how much distance the weights travel from their initialization in order to classify the dataset completely. Such plots have already been considered in Neyshabur et al. (2017); Nagarajan & Kolter (2017; 2019) (although in the completely different context of understanding why deep networks succeed at in-distribution generalization). We present similar plots for completeness.
Fig 5d shows this for Binary-MNIST on an FNN. For CIFARIO, 10, we conduct two experiments. Fig 5f uses ResNet with Adam and decaying learning rate. Here, observe that the norms saturate after a point, which is because of the learning rate decay. Since this does not make a fair comparison between the geometries of larger datasets and smaller datasets, we also plot this for SGD with fixed learning rate in Fig 5e to recover the increasing norms observation. Here, sometimes the model sometimes saturates an accuracy of 99% (rather than 100%); in those cases, we report the value of the weight norm at the final epoch (namely, at the 200th epoch).
C.3 BROADER EXAMPLES OF GEOMETRIC FAILURE
We elaborate on the multiple datasets we showcased in the paper as examples where ERM fails due to geometric skew. We first discuss the two IIFAR10 datasets, and then discuss the cats vs. dogs example, and then discuss two Binary-MNIST datasets, one that is similar to the cats vs. dogs example, and another corresponding to high-dimensional spurious features.
C.3.1 CIFARIO EXAMPLE WITH SPURIOUSLY COLORED LINE
Here we provide more details about the CIFAR- 10 dataset we presented in Sec and in Fig Ic. This dataset can be thought of equivalent of the cow-camel classification tasks but for 10 classes. For this, we use ten different values of the spurious feature, one for each class. We argue that the failure here arises from the fact that the ResNet requires greater norms to fit larger datapoints (see Fig 5c), and so a similar argument as Theorem 1 should explain failure here.
Dataset details. To create the ten-valued spurious feature, we consider a vertical line passing through the middle of each channel, and also additionally the horizontal line through the first chan- nel. Next, we let each of these four lines take constant value of either (0.5 = 0.5B) where
Borrowing the implementation in https: / / thub. examples/cifal farl 0__ resnet. py, without data augmentation.
24

---

Published as a conference paper at ICLR 2021
1.00
8.68-
l!vilz
livll2
Accuracy
0.75
Norm
8.06
Norm
0.88
8.50
0.06
0.64-
0.25
0.00
Dax
8.62
0.02
8.5
0.6
Pr[xyel > 01
8.7
0.8
0.9
1.0
8.00
100
400
1600
6400
0.60
100
400
1600
6400
(Level of spurious correlation)
Training set size
Training set size
(a) OoD uccuracy drop of max-margin two-class CIFAR10
(b) Random leatures max-margin
(c) Random features max-margin two-class CIFAR-10
Binary-MNIST
100
250
Norm
Norm
89
No rm
200
150
1.8k
3.7k
7.5k
15k
30k
50k
1.8k 3.7k 7.5K 15k
30k
50K
1.8k
3.7k
7.5k
15k 30k 50k
Training set
size
Training set size
Training set size
(d) FNN on Binary MNIST
(c) ResiNet on CIFARIO 10 with SGD, fixed learning rate
(i) ResNet on CIFARIO with Adam, (plot saturates due to decaying learning rite)
In Fig 5a, we show the OOD accuracy drop of a random features based max-margin model trained to classify two classes in CIFARÍO. In the next few images, we demonstrate that MNIST and CIFAR10 10 datasets have the property that the more the datapoints in the dataset, the larger the norm required fit them. Specif- ically, in Fig 5b and Fig Sc, we plot the max- margin norms of a random features representation (see App B.1 for the definitions of two plotted lines). Fig 5d, Fig 5e, Fig 5f, we plot the distance from initialization of neural network models (presented for the sake of completeness).
Figure 5: Validating geometric skews in MNIST and CIFARIO:
B [-1,1] denotes "spurious feature scale". Since each of these lines can take two configu- rations, it allows us to instantiate 16 different configurations. We'll however use only 10 of these configurations, and arbitrarily fix a mapping from those configurations to the 10 classes. For con- venience let us call these ten configurations : Xop Then, for any datapoint in class i, we denote the probability of the spurious feature taking the value Xsp.j. conditioned on y, as Pt.j-
To induce a spurious correlation, we set Pt, > 0.1, and set all other Pt, = (1-P1.)/10. Thus, every value of the spurious feature Xsp.j is most likely to occur with its corresponding class j. Finally, note that to incorporate the spurious pixel, we zero out the original pixels in the image, and replace them with the spurious pixels.
For the observation reported in Fig Ic, we use the value of B = 0.5 during training and testing. We set Pi.j = 0.5 for all classes. This means that on 50% of the data the spurious feature aligned with the class (we call this the 'Majority' group). On the remaining 50% data, the spurious feature takes one of the other values at random (we call this the 'Minority' group).
C.3.2 CIFARIO EXAMPLE WITH A LINE IN THE THIRD CHANNEL
Here, elaborate on the discussion regarding the dataset in Fig 2d. In this dataset, we add a line to the last channel of CIFAR 10 (regardless of the label), and vary its brightness during testing. We argue that one way to understand the failure is via the fact that the "linear mapping" Constraint is broken. In particular, if we imagine that each channel contains the same invariant feature Xinv (which almost the case as can be seen in Fig 7), then for simplicity, we can imagine this dataset to be of the form (Xinv Xin + X.p) i.e., Xin and X.p are not orthogonal to each other. In this scenario, the second co-ordinate can still be fully predictive of the label, and therefore the max-margin classifier would rely on both the first and the second co-ordinate to maximize its margins e.g., W Xinv + W2 (Xivv x) + b where W1, W2 + O. Crucially, since the classifier has not quite disentangled Xap from the invariant part of the second channel, this makes the classifier vulnerable to test-time shifts on Xap In Sec A we detail this under the failure mode of Constraint 5, and visualize this failure in Fig 4c, and also connect to Theorem 1.
25

---

Published as a conference paper at ICLR 2021
Majority
Minority
Horizontal
Veriical
8 1.0
B 4.0
8 0.1
0.2
8 0.5
B= 2.0
15 1.0
B 4.0
(a) Images with lines whose colors spuriously correlated with the label.
(b)
Images with lines in the third channel adided regardless label.
Figure 6: Our CIFAR10 examples: In Fig 6a we visualize the dataset discussed in App C.3.1. Each row corresponds to different value of the "scale" of the spurious feature. The left two images correspond to datapoints where the spurious feature maps to the corresponding value for that label. The right two images correspond to datapoints where the spurious feature maps to one of the 9 other values. In Fig 6b, we visualize the dataset discussed in App C.3.2. The left two images correspond to adding a horizontal line to the last channel, and the right corresponds to vertical line.
(a) Chunnels in the non orthogonul dataset
(b) Channels the orthogonal dataset.
Figure 7: The channels in the CIFAR-10 dataset from Section C.3.2: In the top image, is our main dataset, where one can see that the third channel has faint copy of the original "invariant feature" and an extra vertical line added onto it. In the bottom image, is the control dataset where the last channel only contains the vertical line (thus making the spurious feature orthogonal to the invariant features).
Dataset details. In Fig 6b, we visualize this dataset for multiple values of a spurious feature scale parameter, B E [-4, 4]. In particular, we take the last channel of CIFARIO and add B the middle line of the channel. Since this can result in negative pixels, we add value of 4 to all pixels in the third channel, and then divide all those pixels by a value of + that they lie in between 0 and 1. (This normalization is the reason the color of the images differ from the original CIFAR10 dataset; as such this normalization is not crucial our discussion.)
More experimental results. We run two kinds of experiments: one where we add only a vertical line to all images, and another where we add a horizontal line to 50% of the images (essentially simulating data from two different domains). We also run experiments for two different values of B during training, 0.2 and 1.0. As a "control" experiment, we completely fade out the original CIFAR image in the third channel. Then, according to explanation, the model should not fail in this setting as data of the form Xxp) ie.. the two features are orthogonally decomposed. We summarize the key observations from these experiments (plotted in Fig 8) here:
26

---

Published as a conference paper at ICLR 2021
0.05
0.0
Accurag aur
accuracy
lnn-arthogemal
3.89
Nan Man-orttogom
Non crtt:gom Orthegonal
Ortrogonal
0.6
Orthsponal
0.81
Non-orthojonst
Orthogam!
0.5
Spurious feature scale
Spurious feature scale
Spurious feature scale
Spurious feature scale
(a) Only vertical line. during training
(b) Vertical hocizontal lines,
(c) Only vertical line, during training
(d) Vertical borizontal lines,
B 0.2 during training
B 2.0 during training
Figure 8: More experiments on CIFAR10 example from App C.3.2: Here the red triangle corre- sponds to the value of the scale of spurious feature during training. "Non-orthogonal" corresponds to our main setting, and 'Orthogonal' corresponds to the control setting where the original image in the third channel is zeroed out.
1. As predicted, we observe that when trained on the "orthogonal" dataset (where the original CI- FAR10 image is zerod out in the third channel), the Ool performance of the neural network is unaffected. This provides evidence for our explanation of failure the "non-orthogonal" dataset.
2. We observe that training on ERM on the "multidomain dataset" (Figs 8b, 8d) that has both hor- izontal and vertical lines, makes it more robust to test-time shifts compared the dataset with purely vertical lines (Figs 8a, 8c).
3. Remarkably, even though the third channel has only a very faint copy of the image (Fig 7), the classifier still learns a significant enough weight on the channel that makes susceptible to shifts in the middle line.
4. We note that introducing different kind of test-time shift such Gaussian shift, is not powerful enough to cause failure since such a shift does not align with the weights learned, W2. However, shifts such as the line in this case, more likely to be aligned with the classifier's weights, and hence cause a drop in the accuracy.
C.3.3 CATS VS. DOGS EXAMPLE WITH COLORS INDEPENDENT OF LABEL
Recall that the dataset from Fig 1 consists of a scenario where the images of cats vs. dogs (Elson al., 2007) are colored independently of the label. To generate this dataset, we set the first channel to be zero. Then, for particular color, we pick value B [-1, 1). and then set the second channel of every image to be 0.5 (1 - B) times the original first channel image, and the second channel to be 0.5 (1 + B) times the original first channel image. For the blucish images, set B 0.90 and for the greenish images, we set = -0.90 (hence both these kinds of images have non-zero pixels in both the green and blue channels). We visualize these images in Fig 9.
Then, on the training distribution, we randomly select p fraction of the data to be bluish and 1 - fraction to be greenish described above. On the testing distribution, be greenish. Finally, note that we randomly split the original cats vs. dogs dataset into 18000 points for training and use the remaining 5262 datapoints for testing/validation. In Fig 1d, we set 1-p 0.001, so about ~ 20 greenish points must be seen during training. We show more detailed results for 1 p set 0.001, 0.01 and 0.1 in Fig 10. We observe that the OoD failure does diminish when 1 - 0.1.
force all datapoints to
Explaining this failure via an implicit spurious correlation. Peculiarly, even though there is no explicit visual spurious correlation between the color and the label here, we can still identify different kind of non-visee non-visual spurious correlation. To reason about this, first observe that, if the two active channels (the blue and the green one) correspond to (x1, X2), then x + is constant across all domains (and fully informative of the label). Hence X1 + X2 can hence be thought as an invariant feature. On the other hand, consider the feature Xaiff X1 X2. During training time, this feature would correspond to version of the original image scaled by a positive factor of 2B for most datapoints (and scaled by negative factor of - 2B for minority of datapoints). A classifier that relies only on X₁ + X2 to predict the label will work fine on our test distribution; but if it relies on Xai, it is susceptible to fail.
Now, we informally argue why an ERM-based classifier would rely on Xait- If we were to think of say that there must exist weight vector Wait such that
this in terms of linear classifier,
27

---

Published as a conference paper at ICLR 2021
Class I
Class 2
B -0.9
B 0.0
15
0.9
Figure 9: Our cats vs. dogs examples: We present the dataset from App C.3.3 for various values of B which determines how much of the image resides the second channel vs. the third channel.
Spurious
Accurasy
0.7
Accur Accuracy
0.0
0.75
0.77
9.78
6.3
1.0
0.6
--.5
8:5
Maxmargin dossilier
Spurious
Spurious
(a) - pp 0.001
(b) 11ppppp-- 0.01
(0) - 1-1--p=--
(d) Visualization failure
Figure 10: Experiments Cat vs Dogs dataset from App C.3.3: Each of the first three plots above
corresponds to a different value of 1 i.c. the proportion of the minority, greenish datapoints. We plot the OoD accuracy various distributions for varying values of B [-1, The final plot provides a visualization of these failure mode as explained in App C.3.3.
y. (Waiff Xditt) > for the majority of the training datapoints. Then, we can imagine single- dimensional spurious feature that corresponds to the component of the data along this direction i.e., Tap == Wait Xait. Notably, for a majority of the datapoints in the training set we have Isp y and for a minority of the datapoints this feature does not necessarily correlate align with the label let's say Zipp y for convenience. Then, this setting would effectively boil down to the geometric skew setting considered by Theorem 1. In particular, we can say that when the minority group is sufficiently small, the classifier would rely on the spurious feature Tsp to make its classification. We visualize this in Fig 10d.
Thus, even though there is no color-label correlation this dataset, there still a spurious corre- lation, although manifest in way that does not visually stand out. While this is one such novel kind of spurious correlation, the key message here is that we must not limit ourselves to thinking of spurious correlations straightforward co-occurences between the label and spurious object in the image.
Remark 3. It is worth distinguishing this spurious correlation with the one in the Colored MNIST dataset (Arjovsky et al., 2019). Colored MNIST, the color correlated with the label, and one can again think of Xaiff as giving rise to the spurious feature. However, the manner in which this translates to a spurious feature is different. Here, the sign of each co-ordinate in Xai is indicative of the true label (if is positive, it means the image resides in the first channel, and is red, which is correlated with the label). Mathematically, if we define War to be the vector of all ones, then we can think of Wan Xan single-dimensional spurious feature here. In case however, the vector
28

---

Published as a conference paper at ICLR 2021
Wai that yields the single- -ingel-dimeniinall spurious feature is different, and is given by the direction of separation between the two classes.
Remark 4. We observe that in this non-standard spurious correlation setting, we require the minor- ity group to be much smaller than in standard spurious correlation setting (like CMNIST) create similar levels of OoD failure. We argue that this is because the magnitude of the spurious feature [xsp is much smaller in this non-standard setting. Indeed, this effect of the spurious feature mag- nitude is captured in Theorem 3: the lower bound on the spurious component holds only when the minority group is sufficiently small to achieve R2 I v1/4 - 1/2/02/ i.e., when the spurious feature magnitude |zapl is smaller, we need the minority group to be smaller.
To see why |xs differs in magnitude between the standard and non-standard spurious correlation settings, let us To see why [zspl differs in magnitude between the standard and non-standard spurious correlation settings, recall from the previous remark that in our setting, |x |Wan Xair), while in standard spurious correlation settings |.>ppl = Waif' Xai-- Intuitively, Wair Xair corresponds to sep- arating all- possitiveppxel images from all aall-negaiiv--ixee images, which are well well-separated classes. On the other hand, Wair Xaif corresponds to separating images of one real-world class from another, which are harder to separate. Therefore, assuming that both weights vectors are scaled to unit norm, we can see that |Wain Xaitl
<< Wain Xdit!
C.3.4 BINARY-MNIST EXAMPLE WITH COLORS INDEPENDENT OF LABEL
Similar to the cats vs. dogs dataset, we also consider a Binary-MNIST dataset. To construct this, for each domain we pick a value B E [-1, 1]. and then set the first channel of every image to be 0.5 (1 + B) times the original MNIST image, and the second channel to be 0.5 (1 - B) times the original MNIST image. To show greater drops in OoD accuracy, we consider stronger kind of test-time shift: during training time we set B to have different positive values so that the image is concentrated more towards the first channel; during test-time, we flip the mass completely over to the other channel by setting B -11
Here again, we can visualize the dataset in terms of an invariant feature that corresponds to the sum of the two channels, and a spurious feature that corresponds to Waif Xdiff. The exact visualization of failure here is slightly different here since we're rr considering a stronger kind of shift in this setting. In particular, during training we'd d have y- (Wait Xam) > 0 for all the training datapoints in this setting. Thus, we can think of this as a setting with no minority datapoints in the training set (see Fig 12)). Then, as special case of Theorem 1, we can derive a positive lower bound on the component of the classifier along Tsp. However, during training time, since Xaint is no longer a positively scaled version of the MNIST digits, the value of Waiff Xdiff would no longer be informative of the label. This leads to an overall drop in the accuracy.
Experimental results. We conduct two sets of experiments, one where we use only a single domain to train and another with two domains (with two unique positive values of B3). In both variations, we also consider a control setting where the data not skewed: in the single-domain experiment, this means that we set B- = 0 (both channels have the same mass); in the two-domain experiment another. According to our
this means that we set B to be positive in one domain and negative explanation above, in the single-domain control setting Fig 12, since Xinv = 0, the classifier is likely to not rely on this direction and should be robust to test-time shifts in Xaiff. In the two-domain control setting, since the classifier also sees negatively scaled images in Xan, it would be relatively robust to such negative scaling during test-time. Indeed, we observe in Fig 12, that the performance on the non-skewed, control datasets robust. On the other hand, the skewed datasets, we observe greater drops in OoD accuracy when B is flipped, thus validating our hypothesis.
C.3.5 BINARY-MNIST EXAMPLE WITH HIGH- DIMENSIONN SPURIOUS FEATURES
In this dataset, we consider a two-channel MNIST setting where the second channel is a set of spurious pixels, each independently picked to be either 0 or 0. with probability - p and p for positively labeled points and and 1 p for negatively labeled points. During training we set p = 0.55 and p = 0.60 corresponding to two training domains, and during testing, we flip this to p 0.0. We visualize this dataset in Fig 1 11b. In Fig 13, we observe that the classifier drops to 0 accuracy during testing. To explain this failure, we can think of the sum of the pixels in the second channel as spurious feature: since these features are independently picked, with high probability,
29

---

Published as a conference paper at ICLR 2021
Class
Class
Class
Class 2
Majority
Minority
2
7
2
7
2
9
2
B 1.0
0.0
2
/
7
9
2
/
7
9
2
9
2
9
B
p= 0.7
2
7
2
/
7
9
2
9
2
9
B 1.0
1.0
=
identically regardless
(b) pixel second channel independently drawn corelated with label.
(c) All pixels the second channel of the value, correlated label.
Figure 1I: Our Binary-MNIST examples: In Fig 1la we present the dataset from App C.3.4 for various values of B which determines how much of the image resides in the first channel. Fig 11b presents the dataset from App C.3.5 where the second channel pixels are individually picked to align with the label with probability p (the difference is imperceptible because the pixels either 0 or 0. 0. Fig Ilc presents the dataset for App C.4.1, where all pixels in the second channel are either or B.
Spurious is
Accuracy
Accuracy
8.9
8.8
(Dossini) Sen-slmeed + (8.8)
(Dorstnt, Doaxt
ulin
Invorint Chari Chana
0.8
Smn shownd
+ (8.2,9.2)
0.6
Skeved
Shoved
0.7
(1.8)
(1.8.8.5)
Mox-morgin classifier
-1.0
Spurious feature scale
-0.5
0.0
0.5
1.0
-1.0
Spurious feature scale
-0.5
0.0
0.5
1.0
(a) Understanding failure
(b) Single domain
(c) Two domains
Figure 12: Failure on the Binary-MNIST dataset in App C.3.4. In Fig 12a, we visualize the think of the spurious feature as the difference between
failure observed this dataset. Here the two channels (projected along a direction Waifr where they are informative of the label) and the invariant feature the of the two channels. Fig 12b and Fig 12c show the OoD performance under different shifts in the scale of the spurious feature B. During training time this is set to the value given by 'Domainl' and/or 'Domain2'.
1.00
1.00
Accuracy
0.775
Acouracy
0.02
0.0
0.2
0.4
2.5
1.0
0.02
0.0
0.2
0.4
49
2.5
2.0
Pi 0J
Pi 01
[Leeel
spurious correlation)
[Leel
spar Jous correlation)
(a) Single domain
(b) Two domains
Figure 13: Experiments for the high-dimensional spurious features dataset in App C.3.5, The red triangles here denote the values of p used during training.
their sum becomes fully informative of the label. As discussed in Section C.3.4, this boils down to the setting of Theorem when there are no minority datapoints. In Appendix A, we make this argument more formal (see under the diseussion of Constraint 4 in that section).
30

---

Published as a conference paper at ICLR 2021
1.0
Accuracy
Accuracy
Accuracy
Accuracy
0.0
2.0
2.03
2,00
Rojority
Mojarkty Average
Rojerity
Rajority
8.6
Spurious
feature scale
Spurious
feature scale
Spurious feature scale
Spurious feature scale
(a) Statistically skewed, with B = 0.1
(b) No
Statitically skewed, with B 1.0
(d) No skow,
Figure 14: Experiments validating the effect of statistical skews the MNIST dataset in App C.4.1. The red triangle denotes the value of B during training.
C.4 EXPERIMENTS FROM SEC 5 ON STATISTICAL SKEWS
Experiment on Dz-tim- For the plot in Fig 3a, we train a linear model with no bias on the logistic loss with learning rate of 0.001, batch size of 32 and training set size of 2048.
C.4.1 BINARY-MNIST EXPERIMENTS VALIDATING THE EFFECT OF STATISTICAL SKEWS.
For this experiment, we consider a Binary-MNIST dataset where the second channel is set to be either all-0 all-constant pixels. We visualize this dataset in Fig 11c.
To generate our control and experimental datasets, we do the following. First, we sample set of BinATy-MNIST images Sinv and their labels from the original MNIST distribution. Next we create two datasets Smaj and Smin by taking each of these invariant images, and appending spurious feature it. More precisely, we let S Smn {((3rnn Tsp). where Top Bly + 1) S ) and
Smaj = {( zsp). y) where Tsp = B BB(-) + 1) E Smw)
We then define a "control" dataset Scon Smaj U U.Sm which has 1:1 split between the two groups of points. Next, we create an experimental "duplicated" dataset Seup := Smaj U Smin U Saup where Stup is large dataset consisting of datapoints randomly chosen from Smaj. thus creating a spurious correlation between the label and the spurious feature. The motivation in creating datasets this way that neither Scon and Seep have geometric skews; however Sexp does have statistical skews, and so any difference in training on these datasets can be attributed to those skews.
Observations. In our experiments, we let Sin be set of 30k datapoints, and so Scon has 60k: datapoints. We duplicate Smin nine times that Sexp has 330k datapoints and has a 10 : ratio between the two groups. We consider two different settings, one where = 0.1 during training and B = 1.0 during training. During testing, report the accuracy under two kinds of shifts: shifting the value B, and also shifting the correlation completely to one direction (i.e., by concentrating all mass on the minority/majority group). As reported in Fig 14, the statistically skewed dataset does suffer more during test-time when compared to the unskewed dataset.
C.4.2 CIFARIO EXPERIMENTS VALIDATING THE EFFECT OF STATISTICAL SKEWS.
For this experiment, we consider the same CIFAR-10 dataset that we design in Section C.3.1 i.e., we introduce lines in the dataset, that can take 10 different color configurations each corresponding to one of the 10 different classes. Here, the scale B of the spurious feature varies from [-1, (see Section C.3.1 for more details on this).
The way we construct the control and experimental dataset requires bit more care here since we have 10 classes. Specifically, we replicate Sinv ten times, and to each copy, we attach a spurious feature of particular configuration. This creates Scon which has no geometric Also, the has a size of |Seoll = 10 Sivl. Then, we consider the 1/10th fraction of points in Scon where the spurious feature has the correct configuration corresponding to the label. We create large duplicate copy of this subset that is 81 times larger than it (we do this by randomly sampling from that subset). We add this large duplicate set to Swon get Sexp- This gives rise to dataset where for
statistical skews.
31

---

Published as a conference paper at ICLR 2021
0.15
0.35
Accuracy
Accuracy
0.4
Accura Cy
R.
Accura Auuraao
R.
Rajority
Rojaritt
9.45
Rajarity
0.43
Najoraty
6.46
6.46
Spurious
feature scale
Spurious
feature scale
Spurious feature scale
Spurious feature scale
(a) Statiticallyy skewed, with B = 0.1
(b) No
B
Statistccaly skewed, with
(d) No skow,
B 1.0
Figure 15: Experiments validating the effect of statistical skews the MNIST dataset in App C.4.1. The red triangle denotes the value of B during training.
any label, there is 10: 1 ratio between whether the spurious feature matches the label or where takes one of the other nine configurations.
Observations. We run experiments by setting |Smm| During training we try two different values of B, 0.1 and 1 respectively. During testing, in the previous section, we vary both the scale the spurious feature and also its correlation by evaluating individually on the minority dataset (where the spurious features do not match the label) and majority datasets (where the spurious features match the label). Here, again we observe that the model trained on the non-skewed dataset is less robust, evidently due to the statistical skews.
and so |Scontmal 50k and Sexp = 455k.
worth noting that even though there no statistical or geometric skew in the control dataset, observe in Fig 15 (b) that the classifier is not completely robust to shifts in the spurious feature. We suspect that this may point to other causes of failure specific to how neural network models train and learn representations.
D SOLUTIONS TO THE OOD PROBLEM
Our discussion regarding geometric and statistical skews tells about why ERM fails. A natural follow-up is to ask: how do we fix the effect of these skews to learn a good classifier? Below, we outline some natural solutions inspired by our insights.
Solution for geometric skews, Our goal is to learn a margin- classifier that is not biased by geometric skews, and therefore avoids using the spurious feature. Recall that we have a majority subset Smaj of the training set which corresponds to datapoints where Esp >> O and minority subset Smin which corresponds to datapoints where Tup y < 0. Our insight from the geometric skews setting is that the max-margin classifier fails because it is much "harder" (in terms of & norm) to classify the majority dataset Smaj using Xinv when compared to classifying Smin using Ximv- A natural way counter this effect would be to somehow bring the difficulty levels of these datasets closer. In particular, we propose a "balanced" max-margin classifier Wtal that does the following:
What = arg max min ||wal| 1
(Whil x/x E Smajh: {c- What x/x E Smin
margin majority group
downscaled margin minority group
where e is sufficiently small constant. In words, we consider classifier that maximizes "bal- anced" margin on the dataset. The balanced margin is computed by scaling down the margins on the minority datapoints, thereby making that subset artificially harder, and thus diminishing the ge- ometric skew. For an appropriately small choice of c, we can expect the balanced max-margin to minimize its reliance the spurious feature.
'Hrre's the calculation: in Seunal, we have subset of size |Sme| where the spurious feature is aligned with the label and in the remaining 9) Smvl datapoint, the spurious feature is not aligned. So. if we add 81 Sm datapoints with matching spurious features, we'll have dataset where 90) Sm.l datapoints have matching spurious features while S.m| don't i, thus creating the desired 10 ratio.
32

---

Published as a conference paper at ICLR 2021
30
Spurz perrious compunent
Priket 0]
0:75
12 No rm
0.85
20
0.2
0.0
64
256
1024
0
2000
4000
6000
8000
10000
Training set size
Epoch
(a) Evidence of geometric skews
(b) Evidence statistical skews
Figure 16: Experiments validating geometric and statistical skews on the obesity dataset: In Fig 16a, show that the f2 norm required to fit the data in the invariant feature space grows with dataset size. As discussed earlier, this would result in a geometric skew, which explains why max-margin classifier would rely on the spuriously correlated feature. In Fig 16b, show that the spurious component Ws/[[w] of the gradient descent trained classifier converges to zero very slowly depending on the level of statistical skew."
Note that this sort of an algorithm is applicable only in settings like those in faimesss literature where we know which subset of the data corresponds the minority group and which subset corresponds to the majority group.
Solution for statistical skews. One natural way to minimize the effect of statistical skews is to use l weight decay while learning the classifier: weight decay is known to exponentially speed up the convergence rate of gradient descent, leading to the max-margin solution in polynomial time. Note that this doesn't 't require any information about which datapoint belongs to the minority group and which to the majority.
In the setting where we do have such information, we can consider another solution: simply over- sample the minority dataset while rumning gradient descent. This would result a dataset with no statistical skews, and should hence completely nullify the effect of statistical skews. Thus, argument provides a theoretical justification for importance sampling for OoD generalization.
E DEMONSTRATING SKEWS ON A
DATASET
So far, we have demonstrated our insights in the context image classification tasks. However, our theoretical framework is abstract enough for to apply these insights even in non-image classifi- cation tasks. To demonstrate this, we consider an obesity estimation task based on the dataset from Palechor & de la Hoz Manotas (2019).
Dataset details. The dataset consists of 16 features including height, weight, gender and habits of person. The label takes one of six different values corresponding varying levels of obesity. We convert this to a binary classification task by considering the first three levels as one class and the last three levels as another; we ignore any datapoint from the middle level, resulting dataset of 1892 points. We randomly split the data to extract 729 test datapoints. The dataset also has a categorical variable corresponding to the preferred mode of transport of the individual, which convert five binary features (corresponding to automobile, motorbike, bike, public transport and walking). We then scale all the resulting 20 features lie between -1 and 1. For all our experiments, will consider fitting linear classifier directly on these features.
Next, we construct "biased" training set by sampling from the above training set in a way that the public transport feature becomes spuriously correlated with the label. For convenience we denote this feature as Tep and the remaining features as Xiev. Note that the original dataset there is not much correlation between Tep and y. In particular Pr [x.P > 0] ss 0.47 (a value close to 0.5 implies no spurious correlation). Indeed, a max margin classifier w trained on the original dataset does not rely this feature. In particular, "*/[Iw/l is small as 0.008. Furthermore, this classifier achieves perfect accuracy on all of the test dataset. However, as we discuss below, the classifier learned the biased set does rely on the spurious feature.
33

---

Published as a conference paper at ICLR 2021
Geometric skews. We sample a biased training dataset that has 581 datapoints for which Tap y and 10 datapoints for which Esp = -y. We then train a max- max-maagin classifier on this dataset, and observe that its spurious component Ww//|w| is as large the component of the max-margin on the original dataset). But more importantly, the accuracy of this model on the test dataset where Txp y 99.5% while the accuracy on test dataset where Map = -y is only 57 27. In other words, the classifier learned here relies on the spurious feature, and suffers from poor accuracy on datapoints where the spurious feature does not align with the label. Why does this happen? Our theory says that this must be because of the fact that as we increase the number of training datapoints, it requires greater and greater & max-margin norm fit the data using only the invariant feature space (and ignoring the spurious feature). Indeed, we verify that this increase does happen, Fig 16a.
0.12 (about 15 times larger than
Statistical skews. To demonstrate the effect of statistical skews, we take a similar approach as in earlier sections. We consider dataset where we have the same number of unique data in the majority group (where Tap = y) and in the minority group (where Zssp -y). However, the majority group contains many duplicates of its unique points, outnumbering the minority group. In particular, we consider two different datasets of 500 datapoints each, and in one dataset, the majority group forms 0.75 fraction of the data, and in the other forms a 0.85 fraction of the data. Note that in both these datasets, the max-margin classifier does not rely on the spurious feature since there's 's no geometric skew.
To demonstrate the effect of the statistical skew, train linear classifier to minimize the logistic loss using SGD with a learning rate of 0.01 and batch size of 32 for as many as 10k epochs (which is well beyond the number of epochs required to fit the dataset zero error). We then verify in Fig 16b that gradient descent takes a long time to let the spurious component of the classifier get close to its final value which is close to zero. This convergence rate, as we saw in our earlier experiments, is slower when the statistical skew is more prominent.
Important note. We must caution the reader that this demonstration merely intended to showcase that our theoretical insights can help understand the workings of classifier in practically impor- tant, con-image classification dataset. However, we make no recommendations about how to deal with such high-risk tasks in practice. Such tasks require the practitioner to make careful ethical and social considerations which are beyond the scope of this paper. Indeed, empirical benchmarks for evaluating OoD generalization (Gulrajani & Lopez-Paz, 2020) are largely based low-risk image classification tasks as it provides a safe yet reasonable test-bed for developing algorithms.
Remark synthetic vs. natural spurious feature shifts. It would be valuable exercise to validate our insights on datasets with naturally-embeedded spurious features. However, in order to test our insights, it is necessary have datasets where one explicitly quantify and manipulate the spurious features e.g., we need this power to be able to discard the spurious feature and examine the &a norms of the max-margin in the invariant feature space. Currently though, OoD research lacks such datasets: we either have MNIST-like datasets with synthetic but quantifiable spurious features, or realistic datasets like PACS (Asadi al., 2019), VLCS (Fang et al., 2013) where it is not even clear what the spurious feature is. The lack of datasets with natural yet quantifiable spurious features a gap that is beyond the scope of this paper, and is worth being bridged by the OoD community in the future.
34


Reviews:
[{"review_id": "uMBTV_iJV6S", "reviewer": "AnonReviewer4", "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": "This paper investigates the reasons why machine learning models usually fail to generalize out-of-distribution even in easy-to-learn tasks where one would expect these models to succeed. The authors propose two kinds of skews in the data: geometric and statistical, to explain this behavior and theoretically demonstrate it in the linear and easy-to-learn settings. \n\nPros:\n+ The problem studied in this paper has been one of the most important in the community and this work has a meaningful attempt on the theoretical side.\n+ The theoretical results obtained by analyzing the simplest tasks are insightful and could be seemingly drawn on in more general settings. \n+ The experiments are carefully designed based on the constraints, which is well in support of their theoretical claims. \n\nMajor concerns:\n\nI agree with the authors on most of their explanations on the failure modes of OOD generalization from the geometric and statistical perspectives in easy-to-learn tasks. However, the authors claim that these two skews are “not just a sufficient but also a necessary factor for failure of these models in easy-to-learn tasks“, which I think might be overclaimed, even in the easy-to-learn tasks defined in the paper. I do believe that both geometric and statistical skews play a role in the failure of OOD generalization, but they might not be the only reasons. In fact, even if there exist no spurious features, machine learning models might fail to generalize out-of-distribution as well. \n\nHere is the example. Let us consider a comparison task, where we aim to learn a linear classifier to predict which one of any given two values {x_i, x_j} is larger, i.e., it outputs +1 if x_i >= x_j, and otherwise it outputs -1. For simplicity, let us further assume that -1 =< x_i, x_j =< +1 and x_i^2 + x_j^2 =1. In this case, x_inv = (x_i, x_j) and there is no x_sp. It is also easy to check that this task satisfies the five constraints stated in the paper. Given the training dataset in which all data points (x_i, x_j) are satisfying that 0 =< x_i, x_j =< +1 and x_i^2 + x_j^2 =1, it is easy to learn a linear classifier that can be well generalized to the whole domain [-1, +1]. If we represent  (x_i, x_j) in the polar coordinate system, then (x_i, x_j) is converted to (1, \\theta). In this case, we have x_inv = \\theta and no x_sp, which also satisfies the five constraints. Although we still can learn a perfect linear classifier in the training data, it is impossible to generalize to the whole [-\\pi, +\\pi] corresponding to [-1, +1]. The reason is that this task is no longer linearly separable. From the example above, we can see that even without spurious features, some simple transformations only on invariant features would render OOD generalization impossible. This would be another failure mode beyond the geometric and statistical skews. \n\nMinor concerns:\n- The constraint on fully predictive invariant features seemingly simplifies the OOD generalization problem too much, making the theoretical results hard to apply to more general settings. Actually this constraint circumvents two key questions which play a pivotal role in the OOD generalization. One is how to justify whether or not features are fully predictive and invariant across all the domains or environments. This involves the generalization assumption, like Assumption 8 of Arjovsky et al. (2019). The other is how to learn the partially predictive invariant features which, albeit not fully predictive, remains invariant across all the domains. If we want to solve the OOD generalization problem in practice, these two questions have to be answered. \n\n- The example given in Constraint 3.2 is not suitable. The distribution of invariant features must be identical across all domains, otherwise these features should not be treated as “invariant”. The exact distribution of the shapes of cows and camels vary across domains because they are not the true invariant features. \n\n- Constraint 3.5 is too strong as well. It circumvents another key question in the OOD generalization: how to identify x_inv and x_sp. If we can identify them, the OOD generalization would be reduced to a simple ERM problem. \n\nOther comments:\n- The last 6th line before section 3.1 says that Pr_{D_test}[x_sp \\cdot y >0] = 0.0. I believe this is a typo, right?\n- Overall I feel too much content is placed in the appendix and it affects the fluency of reading a bit. I suggest that the authors re-organize the content and put back some stuff to the main text. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rKG488D3hDL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I stand by my initial review that this is a strong submission, and having read through the other reviews and author responses, I am raising my confidence level as well (I think I have a solid grasp of this work's potential import). I disagree with critiques of the paper's novelty and practicality -- I think it provides new insights into OOD problems with substantive theory (not common) and provides actionable insights to boot. Also, the the revised manuscript is much improved. I hope this gets accepted.\n\n-----\n\nThis submission presents a rigorous analysis of a subset of ways in which machine learning models can fail when encountering out-of-distribution (OOD) samples (often referred to as train/test skew or as train/scoring skew in industry). As the paper notes, the topic has received a great deal of attention, particularly under other guises (\"domain adaptation\"). However, much of that attention has aimed at pragmatic or heuristic solutions (various tricks to design or learn \"invariant\" features), while our fundamental understanding of what goes wrong in OOD situations remains incomplete. This paper aims to fill those gaps in understanding by studying simplified settings, and asking the question: why does a statistical model learn to use features susceptible to shift (\"spurious\" features) when the task can be solved using only safe (\"invariant\") features. After formulating five constraints (guaranteed to hold true for easy-to-learn tasks), they go on to show that failures come in two flavors: geometric skew and statistical skew. They analyze and explain each in turn, while also providing illustrative empirical results.\n\nI like this work a lot (though I am more lukewarm on the paper itself, see below), and barring discovery of a fatal flaw during the discussion, I would advocate with some enthusiasm for its inclusion in the conference. The paper's claims are stated at the bottom of page 2 as:\n1. Careful design and articulation of \"easy-to-learn\" settings in which there are few, if any, unmeasured variables that could confound the findings (a weakness in previous work on this topic).\n2. Identification of two (but not the only two) distinct types of OOD failures that occur even in easy-to-learn settings, in the form of necessary and sufficient data \"skews.\"\n3. Experimental evidence to illustrate and support the analyses from (2.), along with enlightening discussion.\n\nI agree with the paper's claims, though I admit that I was not previously familiar with, e.g., Sagawa 2019 or Tsipras 2019, and so cannot confidently situate this work amongst related research. I also feel my understanding may still be somewhat superficial -- I buy its arguments but don't have a particularly strong intuition yet for the two flavors of skew (particularly in non-toy settings).\n\nThis work has a very strong scientific flavor (not always true of machine learning research): I would liken the restriction to carefully designed \"easy-to-learn\" settings to a well-designed laboratory experiment in which there are few, if any, unmeasured variables that could confound the findings. It is very elegant and satisfying to read and think about. I would anticipate that this paper will inspire a lot of follow-up work, in which other researchers adopt the \"easy-to-learn\" and \"skew\" framework and terminology and even utilize the specific experimental designs in this paper. After all, machine learning researchers love adopting intellectual frameworks and benchmarks that they can build upon rapidly.\n\nThe \"easy-to-learn\" constraints articulated in Section 3.1 are sensible and clearly stated, and I am unable to find fault in them thus far. I agree with this statement on page 5: \"any algorithm for solving OoD generalization should at the least hope to solve these easy-to-learn tasks well.\"\n\nThe experiments were thoughtful and well-designed, and their results are presented effectively: each plot, it seems, illustrates a particular point or supports a specific argument in the paper. For example, I like how Figures 2 and 3 serve as visual summaries of the geometric and statistical skew sections, respectively. A reader (particularly a savvy one familiar with the relevant related work) could probably skip Sections 4 and 5 (three pages total!) and still get the high level idea simply by skimming the plots and reading the captions of those two figures.\n\nThe largest weakness I perceive concerns the clarity and accessibility of the writing: for example, the connection drawn in Section 4 to the work on norms in over-parameterized neural nets is very interesting, but I'm not sure the text fully succeeds in further connecting it to OOD settings. In particular, certain details of the ongoing discussion of majority and minority groups aren't entirely clear (to me, at least)...are minority group samples available during training, just in smaller number? In that case, what is the OOD \"shift\" -- the prevalence of the minority group at test time?\n\nLikewise, I'm not sure I really connected with the takeaway in Section 5 -- is it that early in the optimization, the \"spurious\" weights get updated repeatedly by an amount proportional to the spurious correlation, and that it then takes a long time to undo these updates, if at all? The statistical skew section is definitely more abstract and perhaps a little harder to connect to practical settings, vs. geometric skew where the bridge is the previous work on \"norms.\"\n\nMy recommendation is to accept this submission, and at the moment, I am willing to advocate for it. However, it is entirely possible I am missing (or misunderstanding) key details, and so I am eager to discuss with the other reviewers.", "extra_scores": {}, "extra_text": {}}, {"review_id": "aZBUzUlAIFD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper studies generalization under distribution shift, and tries to answer the question: why do ERM-based classifiers learn to rely on \"spurious\" features? They present a class of distributions called \"easy-to-learn\" that rules out several explanations given in recent work and isolates the spurious correlation phenomenon in the simplest possible setting. Even on \"easy-to-learn\" distributions, linear models obtained from ERM use spurious features owing to either the dynamics of gradient descent trained on separable data (very slow convergence to the max-margin classifier) or a certain geometric skew in the data.\n\nPros:\n- The paper address a question of great interest to the ICLR community: generalization under distribution shifts.\n- The \"easy-to-learn\" set of instances seems like a reasonable test-case to understand robustness to distribution shifts before moving to more complex setting.\n- The fact that spurious feature use can arise on the \"easy-to-learn\" instances suggests that previous explanations are underpowered in the sense that they're ruled out by this construction, but the pattern still arises.\n- The \"statistical\" skew shows how the dynamics of gradient descent can introduce brittleness  to distribution shift, albeit in a limited setting.\n\nCons:\n- This paper is written is a way that's confusing and frequently difficult to follow. Rather than focus on explicating the core phenomenon well and supporting it with clear theorems and well-justified experiments, the authors at times take a shotgun approach and mention numerous constructions (often in-line), references to empirical results, descriptions of experiments, that seem to obfuscate rather than clarify the core phenomena they're presenting. For instance, the \"geometric\" skew in Section 4 is never precisely explained.\n- In a similar vein, the paper does not justify the experiments they run in light of the phenomena they seek to \"intuitively understand.\" For instance, in Section 4/5, the paper presents a litany of experiments, without explaining how they fit into the \"easy-to-learn\" framework or relate to a phenomena described by the theorems. It's possible there's a connection, but it's not evident to this reader. \n- The experiments focus on a variety of synthetic distribution shifts. While this may be useful in understanding the constructions in the paper, it's not evident to what extent these 'skews' and the 'spurious/invariant' distinction given here can explain the lack of robustness observed in practice on \"real\" or \"natural\" distribution shifts.\n\n==================\n\nUpdate after rebuttal:\nThank you to the authors for their detailed response. The clarification and updates in the geometric skews section and the more explicit justification and connections between the framework/theoretical results and the experiments improved readability and clarity. I also appreciate putting greater weight on the theoretical contributions and \"easy-to-learn\" task definitions, which provide a simple but non-trivial test case for robustness research. I'm increasing my score accordingly.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7BIVfXBSQaN", "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": "Overview: The authors study the out of distribution generalisation problem in detail wherein a model may incorrectly use spurious correlations in the data to make predictions on data at test time. This is a fundamental problem and very crucial/difficult to tackle across various domains\n\nQuality and Clarity: The paper is fairly well written overall.\n\nOriginality and Significance: OOD detection is a well-studied problem that has proven difficult to date; it's highly relevant across applications in high-stake domains. The approach taken in this paper is to a) study tasks that are easy to succeed on, b) show that OOD failure occurs even in these easy settings. The authors subsequently show that geometric and statistical skews are necessary for failure. As such the approach has limited novelty, since it does not offer a concrete solution to the OOD detection problem but rather examines necessary conditions for OOD failure.\n\nPros: 1) The authors study a highly relevant problem of OOD failures\n2) The authors present a fairly rigorous empirical analysis of geometrical and statistical skews on CIFAR and MNIST\n\nCons: 1) The paper is limited in novelty; while the authors state find that OOD failures result from statistical and geometric skews, they do not provide an adequate solution to overcoming these skews\n\n2) OOD failures are only studied in the context of small theoretical examples or image tasks such as MNIST or CIFAR. However, OOD failures are widespread across various domains and become especially important to study in high risk settings such as in a clinical context etc. I would have liked to have seen some exposition of these problems in a real high-risk setting.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the reasons for failure of trained neural network models on out of distribution tasks. While the reviewers liked the theoretical aspects of the paper, one important concern is about the applicability of these insights to real datasets. The authors added an appendix to the paper showing results on a real dataset that mitigates this concern to an extent. Further, there are interesting insights in the paper to merit acceptance.
Decision: Accept (Poster)