{'fraction_non_alphanumeric': 0.05326432979423429, 'fraction_numerical': 0.016859627594301874, 'mean_word_length': 4.186312488470762, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improved OOD Generalization via Conditional Invariant Regularizer

Recently, generalization on out-of-distribution (OOD) data with correlation shift has attracted great attention. The correlation shift is caused by the spurious attributes that correlate to the class label, as the correlation between them may vary in training and test data. For such a problem, we show that given the class label, the conditionally independent models of spurious attributes are OOD generalizable. Based on this, a metric Conditional Spurious Variation (CSV) which controls OOD generalization error, is proposed to measure such conditional independence. To improve the OOD generalization, we regularize the training process with the proposed CSV. Under mild assumptions, our training objective can be formulated as a nonconvex-concave mini-max problem. An algorithm with provable convergence rate is proposed to solve the problem. Extensive empirical results verify our algorithm's efficacy in improving OOD generalization.


Introduction
The success of standard learning algorithms relies heavily on the independent and identically distributed (i.i.d.) assumption of training and test data. However, in real-world applications, such assumption is often violated due to the varying circumstances, selection bias, and other reasons (Meinshausen and Bühlmann, 2015). Thus, learning a model that generalizes on out-of-distribution (OOD) data has recently attracted great attention. According to (Ye et al., 2021b), the OOD data can be categorized into data with diversity shift (Li et al., 2017) or correlation shift (Arjovsky et al., 2019). Roughly speaking, there is a mismatch of the spectrum and a spurious correlation between training and test distributions for the two shifts, respectively. Compared with diversity shift, correlation shift is less explored (Ye et al., 2021b). However, Geirhos et al. (2018); Beery et al. (2018); Xie et al. (2020); Wald et al. (2021) have shown the misleading spurious correlation that works for training data may no longer hold on test data.
In this paper, we formally characterize the correlation shift as follows. Suppose there exist spurious attributes in the data, e.g., the gender of a celebrity's face for the task of classifying the hair color ( Figure  1). The correlation between the class label and such spurious attributes is the spurious correlation, which may vary from training to test data. Based on a theoretical characterization of the correlation shift, we show that given the class label, the model which conditionally independent of spurious attributes has stable performance across training and OOD test data. Hence, we propose a metric conditional spurious variation (CSV, Definition 1) to measure such conditional independence. With the class label given, the proposed CSV is the conditional variation of a model over spurious attributes. Moreover, we prove the proposed CSV  et al., 2018), and CivilComments (Borkan et al., 2019) involved in this paper. The class labels and spurious attributes are respectively colored with red and blue. Their correlation may vary from training set to test set. More details are shown in Section 6. controls the OOD generalization error. To the best of our knowledge, this property has not been explored by existing metrics related to OOD generalization (Hu et al., 2020;Seo et al., 2022;Mahajan et al., 2021;Heinze-Deml and Meinshausen, 2021;Krueger et al., 2021).
With the defined CSV which controls the OOD generalization error, we propose to regularize the training process to improve the OOD generalization. To this end, we first design an estimator of the CSV with guaranteed approximation error under observable spurious attributes. However, spurious attributes may not be observable in practice. In this case, we estimate the CSV via another estimator independent of spurious attributes, which approximates a sharp upper bound of the CSV. We regularize the training process with one or the other estimator, depending on whether the spurious attributes are observable. In contrast to existing works (Sagawa et al., 2019;Arjovsky et al., 2019;Seo et al., 2022;Krueger et al., 2021), our training objective can be computed without information on the spurious attributes, which makes it more applicable in practice.
Under some mild smoothness assumptions, the regularized training objective can be formulated as a specific non-convex concave minimax problem. Thus we can solve it via standard optimization technique. A stochastic gradient descent based algorithm with a provable convergence rate of order O(T −2/5 ) is proposed to solve the problem, where T is the number of iterations.
Finally, extensive experiments are conducted to empirically verify the effectiveness of our proposed algorithm on the OOD data with spurious correlation. Concretely, we apply our methods on benchmark datasets CelebA (Liu et al., 2015), Waterbirds (Sagawa et al., 2019), MultiNLI (Williams et al., 2018), and CivilComments (Borkan et al., 2019) where the first two and the last two are respectively imageclassification and textual-classification datasets with spurious correlation. Empirical results show that our algorithm consistently improves the model's generalization performance on all the four OOD benchmarks with correlation shifts.
Domain Generalization. Domain generalization based methods are proposed to resolve the OOD generalization problem. These methods devote to extrapolating the model to test data from unseen domains. The problem considered in this paper can be viewed as domain generalization since distributions with different spurious correlations can be regarded as under different domains. The core idea in domain generalization is to learn an invariant model across different domains. To this end, Arjovsky et Seo et al. (2022) regularize the training process with plenty of invariant metrics. However, unlike our CSV, none of these metrics controls the OOD generalization error of the model. Moreover, none of these methods capture the invariance that can handle the correlation shift in this paper (see Section 4.1). This makes us to reconsider the effectiveness of these methods. Finally, in contrast to ours, these methods require observable domain labels and it is usually impractical. The techniques in (Liu et al., 2021b;Devansh Arpit, 2019) are also applicable without domain information, but these methods are built upon strong assumptions, i.e., a mixture of Gaussian class label (Liu et al., 2021b) and linear model (Devansh Arpit, 2019).
Distributional Robustness. The techniques based on distributional robustness (Ben-Tal et al., 2013;Shapiro, 2017) minimize the worst-case loss of model over different groups of data (GroupDRO, Sagawa et al., 2019), (JTT, Liu et al., 2021a). The groups are constructed via different rules, e.g., data with same spurious attributes (Sagawa et al., 2019) or annotated via validation sets with observable spurious attributes. However, Sagawa et al. (2019) finds that directly minimizing the worst-group loss results in unstable training processes. In contrast, our method has a stable training process as it can easily take a balance between accuracy and robustness over spurious attributes (see Section 5).

Problem Setup
We first collect the notations used in this paper. · is the 2 -norm of vectors. O(·) is the order of a number. The sample (X, Y ) ∈ X × Y, where X and Y are respectively input data and its label. The integer set from 1 to K is [K]. The cardinal of a set A is |A|. The loss function is L(·, ·) : X × Y → R + with 0 ≤ L(·, ·) ≤ M for positive M . For any distribution P , let R pop (P, f ) = E P [L(f (X), Y )] and R emp (P, f ) = n −1 n i=1 L(f (x i ), y i ) respectively be the population risk under P and its empirical counterpart. Here {(x i , y i )} n i=1 are n i.i.d. samples from distribution P , and f (·) is the model potentially with parameter space Θ ⊂ R d (f (·) becomes f θ (·)). For random variables V 1 , V 2 with joint distribution P V1,V2 , P V1 and P V2|V1 are the marginal distribution of V 1 and the conditional distribution of V 2 under V 1 . P V1 (v 1 ) and P V2|V1 (v 1 , v 2 ) are the corresponding probability measures.
Suppose training data are sampled from a specific distribution P , while OOD test data are sampled from the distribution Q different from P . There usually exists similarities between P and Q that guarantee the possibility of OOD generalization (Kpotufe and Martinet, 2021;Azizzadenesheli et al., 2018). The similarity we explored is that there only exists a correlation shift in the OOD test data formulated as follows.
For each input X, there exist spurious attributes Z ∈ Z potentially related to class label Y . The correlation between Z and Y (i.e., spurious correlation) can vary from training to test data. Then the spurious correlation in training distribution may become a misleading signal for the model to make predictions on test data. For example, in the celebrity face in Figure 1, if most males in the training set have dark hair, the model may overfit such spurious correlation and make wrong predictions on the male with blond hair. Thus we should learn a model that is independent of such spurious correlation.
Theoretically, given training distribution P , the test distributions set P with correlation shift is (1) The first equality in (1) obviates the mismatch between Q ∈ P caused by label shift which is unrelated to spurious correlation. More discussions of it are left in Appendix A. The second equality in (1) means that the conditional distribution of data is invariant across training and test distributions, given the class label and spurious attributes. The invariance is reasonable as the unstable spurious correlations are all contained in the joint distribution of Y and Z. Finally, since the variety of Q ∈ P only comes from the variety of conditional distributions Q Z|Y .

Generalizing on OOD Data
In this section, we show that misleading spurious correlation can hurt the OOD generalization. Then we give a condition under which the model is OOD generalizable.

Spurious Correlation Misleads Models
The common way to train a model is empirical risk minimization (ERM Vapnik, 1999), i.e., approximating the minimizer of R pop (P, f ) which generalizes well on in-distribution samples via minimizing its empirical counterpart R emp (P, f ). However, the following proposition shows that the minimizer of R pop (P, f ) may not generalize well on the OOD data from the other distributions in P.
Proposition 1. There exists a population risk R pop (P, f ) whose minimizer has nearly perfect performance on the data from P , while it fails to generalize to OOD data drawn from another Q ∈ P.
Similar results are also appeared in (Xie et al., 2020;Krueger et al., 2021), while they are not obtained on the minimizer of population risk. The proof of this proposition is in Appendix B which indicates that the spurious correlation in training data can become a misleading supervision signal that deteriorates the model's performance on OOD data. Hence, it is crucial to learn a model that is independent of such spurious correlation, even if it sometimes can be helpful in the training set (Xie et al., 2020).

Conditional Independence Enables OOD Generalization
Next, we give a sufficient condition proved in Appendix B to make the model OOD generalizable.
Here f (X) ⊥ Z | Y means f (X) is conditionally independent of Z, given the class label Y . The conditional independence eliminates the impact of correlation shift as the variety of distributions in P only originates from the conditional distribution Q Z|Y . The theorem motivates us to train a model that is conditional independent of spurious attributes in the sequel.
Remark 1. If the spurious attributes are domain labels, the conditional independence in Theorem 1 reduces to the conditional independence discussed in (Liu et al., 2015;Hu et al., 2020;Mahajan et al., 2021), while they do not explore its correlation with the OOD generalization. Besides that, the counterexample in (Mahajan et al., 2021) violates our invariant conditional distribution assumption in (1) and hence is not contrary to our theorem.

Learning OOD Generalizable Model
We have shown that the model conditionally independent of spurious attributes is robust against correlation shift. Thus, we propose a metric, Conditional Spurious Variation (CSV), to quantitatively measure such conditional independence. The proposed CSV directly controls the OOD generalization error. Moreover, we use an information-theoretic generalization bound (Xu and Raginsky, 2017) on in-distribution data to show that conditional independence is not contradicted by in-distribution generalization. Finally, two estimators of our CSV are proposed, depending on whether spurious attributes are observable.

Guaranteed OOD Generalization Error
Theorem 1 shows that the conditional independence between the model and spurious attributes guarantees the OOD generalization. We propose the following metric to measure such independence.
Definition 1 (Conditional Spurious Variation). The conditional spurious variation of model f (·) is (3) As can be seen, CSV is a functional of f (·) which measures the intra-class conditional variation of the model over spurious attributes, given the class label Y . It can be computed via training distribution and is invariant across Q ∈ P due to (1). It is worth noting that the model satisfies the conditional independence in Theorem 1 has zero CSV but not vice versa. 1 However, the following theorem proved in Appendix C.1 shows that CSV(f ) is sufficient to control the OOD generalization error.
Theorem 2. For any Q ∈ P, we have Suppose training data are sampled from P , then |R emp (f, P ) − R pop (f, P )| is the in-distribution generalization error, which can be upper bounded via classical tools e.g., VC dimension, Rademacher complexity, or entropy integral (Vershynin, 2018). This theorem shows that the OOD generalization error is bounded by the sum of the in-distribution generalization error and the CSV. Besides our CSV, many metrics are proposed to measure the invariance of a model over spurious attributes. But none of them directly control the OOD generalization error as our CSV (Seo et al., 2022;Hu et al., 2020;Liu et al., 2021b;Heinze-Deml and Meinshausen, 2021;Mahajan et al., 2021;Ben-David et al., 2007, 2010Muandet et al., 2013;Ganin et al., 2016). In addition, these metrics are proposed to obtained the invariance of model over Z, i.e., invariant P f (X),Y |Z or P f (X)|Z over Z. These invariances can not handle correlation shift in this paper. Because, 1): The invariance of P f (X),Y |Z over Z implies that P Y |Z is invariant to Z, which is incompatible with correlation shift, 2): The invariance of P f (X)|Z over Z does not implies stable is not stable), which guarantees OOD generalization.
As our bound (4) involves both CSV and in-distribution generalization error, it motivates us to explore whether the conditional independence is in contradiction with the in-distribution generalization capability of model. The following information-theoretic bound proved in Appendix C.1 presents a positive answer to it. Let I(V 1 , V 2 ) (defined in Appendix C.1) be the mutual information between random variables V 1 , V 2 , which measures the correlation between them, we have the following result.
from distribution P , and the spurious attributes of x i is z i . Then where Our bound improves the classical result E gen (f θ , P ) ≤ M 2 I(S, θ)/4n without conditional independence (Steinke and Zakynthinou, 2020), as g(·) can be taken as a constant function. The bound indicates that the conditional independence is not in contradiction with in-distribution generalization. Thus, due to Theorem 3, the conditional independence can improve the OOD generalization bound.

Estimating CSV with Observable Spurious Attributes
As smaller CSV enables improved OOD generalization, we propose to regularize the training process with it. Suppose we have n i.i.d. {(x i , y i )} n i=1 training samples with spurious attributes {z i } n i=1 from P . Besides that, we need the following two mild assumptions in the sequel.
Assumption 1. The class label and spurious attributes are discrete, i.e., the Y = [K y ] and Z = [K z ] for some positive integers K y , K z . Besides that, the number of observations A kz = {i : Assumption 2. The model is parameterized by θ ∈ Θ ⊂ R d . The loss function L(f θ (x), y) is Lipschitz continuous and smooth w.r.t. θ with coefficient L 0 and L 1 , i.e., for any (x, y) ∈ X × Y, and θ 1 , θ 2 ∈ Θ, In Assumption 1, we require the spurious attributes space is finite. This is explained as Z is a "label" of spurious attributes, e.g., the gender label "male" or "female" in CelebA dataset ( Figure 1) when classifying hair color. Assumption 1 also requires the data with all the possible combinations of the label and spurious attributes are collected in the training set. This is a mild condition since we do not restrict the magnitude of n kz . For example, to satisfy this collection condition, we can synthesize some of the missing data by generative models as in (Wang et al., 2022;Zhu et al., 2017).
,L kz (f θ ) = (1/n kz ) i∈A kz L(f θ (x i ), k), andp k = n k /n with n k = z∈[Kz] n kz . Then the following empirical counterpart of CSV is a natural estimator to CSV. The following theorem quantify its approximation error.
This theorem implies that CSV decreases with CSV(f θ ). As shown in the proof in Appendix C.2, we hide a factor related to covering number (Vershynin, 2018) of the hypothesis space in the numerator of O (log (1/δ)/ √ n) in (8). The hidden factor is of order √ d (Wainwright, 2019). Thus, more samples are required to estimate CSV in high-dimensional space. Besides that, if the condition inf k,z n kz /n k = O(1) does not hold, the order of error is O(1/ min k,z n kz ) (see Appendix C.2 for details).

Estimating CSV with Unobservable Spurious Attributes
Computing the empirical CSV (7) requires observable spurious attributes which may not be available in real-world applications (Liu et al., 2021a). Thus, we need to estimate CSV in the absence of spurious attributes.
Let P kz = P X|Y =k,Z=z be the conditional distributions of X with Y, Z given. The core difficulty of estimating CSV with unobservable spurious attributes is to estimate sup , and we can not specify the data in A k is from which of A kz . To proceed, suppose π kz ≥ c > 0, which is a necessary condition for Assumption 1 to hold. We show in Appendix C.3 that the quantile conditional expectation is an upper bound (which is sharp for Here q P k (·) is the quantile function defined as q P k (s) = inf{p : P k (L(f θ (X), k) ≤ p) ≥ s}. For large n k , we must have π kz ≥ 1/n k = c for each z ∈ [K z ]. Thus by substituting the expectation on P k in (9) with its empirical counterpart for c = 1/n k , we get the the following estimator The subscript "U" means "unobservable spurious attributes". Besides that, the CSV U (f θ ) is an upper bound to the estimator CSV(f θ ), which is another straightfoward way to obtain it.

Regularizing Training with CSV (RCSV)
The previous results have claimed that the model with small CSV generalizes well on OOD data. On the other hand, Theorem 4 and discussion in Section 4.3 have approximated the CSV via CSV(f θ ) and CSV U (f θ ), respectively. Thus we can regularize the training process with one or the other to improve the OOD generalization, depending on whether the spurious attributes are observable.
It is noticeable that both of the regularized training objectives can be formulated as the following minimax problem for positive constants m and λ min θ∈Θ Ky k=1p k Remp(f θ , P )+λ max u∈∆m u F k (θ) . (11) Here ∆ m = {u = (u 1 , . . . , u m ) ∈ R m + : i u i = 1}, F k (θ) ∈ R m , and each dimension of F k (θ) is Lipschitz continuous function with Lipschitz gradient. Under Assumption 1 and 2, the training process of empirical risk minimization regularized with CSV(f θ ) or CSV U (f θ ) can be formulated as the above problem by respectively setting F k (θ) as the vectorization of the two following matrices. The m of CSV(f θ ) and CSV U (f θ ) are respectively K 2 z and |A k | 2 .
Before solving 11, we clarify the difference between regularizing training with CSV and distributional robustness optimization (DRO) based methods which minimize the worst-case expected loss over data with same spurious attributes, e.g., GroupDRO (Sagawa et al., 2019) Theoretically, the OOD generalizable model has perfect in-distribution test accuracy and robustness over different spurious attributes as in (4). Our regularized training objective split such two goals, while DRO based methods mix the two goals into one objective. Though both objectives theoretically upper bound the loss on OOD data, we empirically observe that the two goals are in contradiction with each other (see Section 6). We empirically observe that splitting the two goals (our objective) enables us easily take a balance between them, which results in a stable training process. In contrast, the mixed training objective can be easily dominated by one of the two goals, which results in an unstable training process. Similar phenomena have also been observed in (Sagawa et al., 2019). That is why GroupDRO uses early stopping or large weight decay regularizer to prevent such dominating problem.
The steps of Line 3-6 in Algorithm 1 solve the maximization problem in (13), which has close-formed , where the definition of Softmax(·) function is referred to (Epasto et al., 2020). As the estimatorF k (θ) may have large variance, substituting the F k (θ) withF k (θ) in u * k (t + 1) of Line 8 (the minimization step) will induce a large deviation. Thus we use the moving average correction F k t+1 (Line 4) to estimate F k (θ(t)), which guarantees the convergence result in the following Theorem 5. The convergence rate of Algorithm 1 is evaluated via approximating first-order stationary point, which is standard in non-convex problems (Ghadimi and Lan, 2013;Lin et al., 2020).
This theorem is proved in Appendix D, and it states that the first-order stationary point of the surrogate Φ k ρ (·) is approximated by θ(t) updated by Algorithm 1 in the order of O(T −2/5 ) (the result can be improved to O(T −1/2 ) for small σ 2 = O(T −1/2 ) as in (Lin et al., 2020)). Since the gap between Φ k (·) and Φ k ρ (·) is of order O(ρ), taking ρ small enough yields a small Φ k (θ(T )). We defer the construction of unbiased estimators appeared in this theorem to the next section.

Experiments
In this section, we empirically evaluate the efficacy of the proposed Algorithm 1 in terms of breaking the spurious correlation. More experiments are shown in Appendix E.
Implementation. The Algorithm 1 can be applied to the regularized training process with either CSV(f θ ) (RCSV) or CSV U (f θ ) (RCSV U ) depending on whether spurious attributes are observable. The implementations is clear after estimating R emp (f θ(t) , P ) and F k (θ) in (12).
For RCSV, in each step t, we letR emp (f θ(t) , P ) be the empirical risk over a uniformly drawn batch (size S) of data. Then we randomly sample another batch (size S) of data with replacement. The probability of each data with class label k and spurious attribute z be sampled is 1/(K y K z n kz ). Then theL kz (f θ(t) ) in 12 is estimated as the conditional expected risk over this batch of data.
For RCSV U , in each step t, theR emp (f θ(t) , P ) is as in RCSV. We also randomly sample another mini-batch (batch size S) of data with replacement but the probability of data with label k be sampled is 1/(K y n k ). We estimate F k (θ) in (12) via its empirical counterpart over these sampled data.
As can be seen, all of the resultingR emp (f θ(t) , P ) andF k (θ(t)) are unbiased estimators with variance of order O(1/S) as in Theorem 5. Besides that, our RCSV (resp. RCSV U ) can be implemented with (resp. without) observable spurious attributes. The complete implementation of RCSV and RCSV U are shown in Appendix G.1. When estimating CSV, the data are sampled with weights that are inversely proportional to n kz or n k . The sampling strategy also appears in (Sagawa et al., 2019;Idrissi et al., 2021;Arjovsky et al., 2019) which significantly improves the OOD generalization according to our ablation study in Appendix F.
Data. We use the following benchmark datasets with correlation shift (see details in Appendix G.2).  ). An image classification task to recognize the hair color of a celebrity as "dark" or "blond", which is spuriously correlated with the celebrity's gender ("male" or "female"). The data are categorized into 4 groups via the combination of hair color and gender, e.g., "dark-female" (D-M).
CivilComments (Borkan et al., 2019). A textual classification task to recognize a sentence is toxic or non-toxic with the label spuriously correlated with whether any of 8 certain demographic identities are mentioned. The data are categorized 4 groups, e.g., "non-toxic-identity" (N-I), "toxic-nonidentity" (T-N).
We see the GroupDRO and IRM use the reweighted sampling strategy as in RCSV, while the Correlation uses same one with RCSV U . As these sampling strategies improve the OOD generalization (Idrissi et al., 2021), to make a fair comparison, we also conduct ERMRS with the two sampling strategies. The two ERMRS are respectively denoted as ERMRS Y and ERMRS YZ . The involved 7 methods can be categorized into 2 groups, i.e., conducted with observable spurious attributes (RCSV, IRM, GroupDRO, ERMRS YZ ) and with unobservable spurious attributes (RCSV U , Correlation, ERM Y , Correlation).
Main Results. Our goal is to verify whether all these methods can break the spurious correlation in data. Thus for each dataset, we report the test accuracies on each group of it, as the groups are divided via the combination of class label and spurious attribute. We also report the averaged test accuracies over groups ("Avg"), the test accuracies on the whole test set ("Total", which is in-distribution test accuracy expected for Waterbirds), and the worst test accuracies over groups ("Worst"). The results are in Table  1, 2, 3. The " √ " and "×" for SA (spurious attributes) respectively mean whether the method requires observable spurious attributes. We have the following observations from these tables.
To check the OOD generalization, a direct way is comparing the column of "Avg" and "Worst" to summarize the results in each group. As can be seen, in terms of the two criteria, the proposed RCSV (resp. RCSV U ) consistently achieves better performances, compared to baseline methods with observable (resp. unobservable) spurious attributes. This verifies our methods can improve the OOD generalization. On the other hand, leveraging the observable spurious attributes benefits the OOD generalization since the methods with them consistently exhibits better performances than the ones without them. For example, the discussion in Section 4.3 shows that the estimator of CSV in RCSV with observable spurious attributes is more accurate than the one in RCSV U .
There is a trade-off between the robustness of the model over spurious attributes and the test accuracies on the groups with the same class label, especially for CelebA and Waterbirds, see "D-F" v.s. "D-M" in CelebA for example. The phenomenon illustrates that some spurious correlations are captured for all methods. However, compared to the other methods, our methods have better averaged test accuracies and a smaller gap between the test accuracies over groups with the same spurious attributes. The robustness and test accuracies here respectively correspond to the goals of "robustness" and "in-distribution test accuracy" in Section 5, the improvements support our discussion in Section 5 that splitting the goals of accuracy and robustness enables us easily take a balance between them.

Conclusion
In this paper, we explore the OOD generalization for data with correlation shift. After a formal characterization, we give a sufficient condition to make the model OOD generalizable. The condition is the conditional independence of the model, given the class label. Conditional Spurious Variation, which controls the OOD generalization error, is proposed to measure such independence. Based on this metric, we propose an algorithm with a provable convergence rate to regularize the training process with two estimators of CSV (i.e., RCSV and RCSV U ), depending on whether the spurious attributes are observable. Finally, the experiments conducted on the datasets CelebA, Waterbirds, MultiNLI, CivilComments verify the efficacy of our methods.

A Label Shift
In the sequel, we may omit the subscribe if no obfuscation. Our discussions in the main body of this paper are built upon the assumption that marginal distribution of label Y is invariant i.e., P Y = Q Y . In this section, we explore OOD generalization without such invariant assumption.

A.1 Conditional Independent Does Break Spurious Correlation
Before presenting our discussion, we give the definition of total variation distance.
Definition 2. The total variation distance between two distributions P, Q defined on the same measurable space X is In Theorem 1, we show that the gap between the performances of the model on training and OOD test data disappears if the model satisfies conditional independence such that f (X) ⊥ Z | Y . However, we show by the following example that the gap will not disappear if the marginal distribution of Y also varies across training and test data.
Example 1. Suppose Y, Z ∈ {−1, 1} and a specialized loss function where f (·) is any classifier whose output is in is unrelated to P Z|Y . Then we have P X|Y = Q X|Y . Thus Since P X|Y = Q X|Y , where TV(P Y , Q Y ) is the total variation distance of the marginal distributions P Y , Q Y . This inequality holds for any f (X), and hence the gap can never be removed by representation learning like what we do in Theorem 1.
The example indicates that under shifted label distribution, the conditional independent model can not generalize on OOD data. Thus, we consider the reweighted loss to fix the bias brought by the shifted label distribution. The formal result is stated as follows.
Theorem 6. Let P, Q be two distributions such that P X|Y,Z = Q X|Y,Z but P Y does not necessary equals to where P w Y is the reweighted label distribution defined as P w Y (A) = A w(y)dP Y (y) for any measurable set A ⊂ Y.
Remark 2. The total variation distance TV(P w Y , Q Y ) appears in the upper bound to the gap between the two population risk in (21). Moreover, this terms seems to be inevitable since it also appears in the lower bound in (19).
According to Theorem 6, we have invariance relationship Thus if the label distribution in the test data is available, minimizing the reweighted loss with its weights decided by the ration of two label distributions can guarantee the OOD generalization capability of the model. However, the label distribution of test data are usually unavailable in practical. Thus for unknown test label distribution, we alternatively chose the weight w(·) to minimize the worst-case upper bound given the training distribution P , where the supremum is taken over all distributions Q such that Q X|Y,Z = P X|Y,Z . Then by minimizing the reweighted loss under such weight w(·), we get a model with minimized worst-case risk over different distributions.
Proposition 2. Suppose that Y is a discrete space, then if P Y (Y = y) > 0 for all y ∈ Y and w * (y) = 1 |Y|P Y (Y =y) , we then have where |Y| is the cardinal of Y.
Proof. From (van der Vaart and Wellner, 2000), we know that TV due to w(y)P Y (Y = y) ≥ 0 and E P [w(Y )] = 1. Then, we have The third equality is due to |Y| min y∈Y w(y)P Y (Y = y) ≤ y∈Y w(y)P Y (Y = y) = 1, and the equality is taken when w(·) = w * (·).

B Proofs in Section 3
In this section, we present the proofs of results in Section 3.
Proposition 1. There exists a population risk R pop (P, f ) whose minimizer has nearly perfect performance on the data from P , while it fails to generalize to OOD data drawn from another Q ∈ P.
Proof. Let us consider the following example that where ξ ∼ N (0, I d1+d2 ), Y, Z ∈ {−1, 1} and follow the standard binomial distribution. Denote the training distribution as P . In this example, Z is the spurious attributes. The correlation coefficient between Y and Z is denoted as σ Y Z (Q) for Q ∈ P. One can verify that Let us consider the linear classifier f θ (x) = θ x and its loss on data (X, Y ) is the exponential loss Soudry et al. (2018) L Thus we can compute the population risk Since R pop (P, f θ ) is continuous w.r.t. to σ Y Z (P ) and θ, we have that θ * (P ) = arg min θ R pop (P, f θ ) is continuous to σ Y Z (P ). Since σ Y Z (P ) ∈ [−1, 1], we conclude θ * (P ) is upper bounded. W.o.l.g. we assume θ * (P ) ≤ 1 for any σ Y Z (P ) ∈ [−1, 1], then for any σ Y Z (P ) we know θ * (P ) satisfies the first order optimality condition such that whereμ = (µ , −µ 2 ) . Thus for σ Y Z (P ) = ±1 we have Thus we can take a σ Y Z (P ) → 1 to make θ * (P )−µ ≤ µ for any small where the can be independent of µ.
Now we show that the linear model f θ * (P ) (·) with its prediction on Y as sign(f θ * (P ) (·)) can make correct prediction with high probability. Let us see the error of linear model f θ * (P ) (·) on the data from training distribution P . Simple algebra show that θ * (P )X | Y ∼ N (Y θ * 1 (P )µ 1 + Zθ * 2 (P )µ 2 , θ * 1 (P ) 2 ). Then under condition of Y = Z, we have Thus from the sub-Gaussian property of Gaussian random variable, for any δ > 0 We may take δ = µ 2 /2 + µ 2 , and σ Y Z (P ) → 1, due to θ(σ Y Z (P )) ≤ 1 and for a large enough µ , with a high probability, we have Since → 0 for σ Y Z (P ) → 1, we have proved that the population minimizer θ * (P ) has nearly perfect performance on the data from training distribution.
However, a similar argument of (33) shows that for data drawn from distribution Q ∈ P for any δ > 0. Again, by taking σ Y Z (Q) → −1 we get with high probability. We can take, for example, µ 2 2 > 3+2 1− µ 1 2 for → 0, then under Y = −1, the inequality becomes which shows the prediction given by f θ * (P ) (·) for Y = −1 is incorrect with high probability. A similar argument can be verified for Y = 1. Then we complete our proof.
Proof. The difference of Y | f (X) for any (X, Y ) ∼ Q with Q ∈ P originates from the different spurious correlation i.e., the different Q Z|Y . Thus to obtain our result, it is suffice to prove that the distribution of Y | f (X) is independent of Q Z|Y . To see this, for any measurable sets A, B ⊂ Y, where the second equality is from the independent condition that f (X) ⊥ Z | Y . From the calculation, we figure out that the distribution of Y | f (X) is independent of spurious correlation P Z|Y due to the arbitrariness of A, B ∈ Y. Then we get the first conclusion.
To provide the second result, it is suffice to show that for the union distribution of (f (X), Y ) is invariant w.r.t Q for Q ∈ P. Thus for any sets A, B ⊂ Y and (X, is independent of with spurious correlation Q Z|Y . Then due to the arbitrary of A, B ∈ Y, we summarize that the union distribution of (f (X), Y ) is invariant w.r.t. Q for Q ∈ P. Then the proof is completed.

C Proofs in Section 4
C.1 Proofs in Section 4.1 Theorem 2. For any Q ∈ P, we have Proof. This theorem can be computed via the assumption in (1). We have Due to (1), the first expectation is invariant with P, Q ∈ P, while the second expectation is a function of (Y, z) independent the choice of P . Thus where the last inequality is due to the loss function is non-negative. Then due to we get the theorem.
Next we provide the definitions of KL-divergence, mutual information, and conditional mutual information which are useful to prove Theorem 3.
Definition 3 (KL-Divergence). Let P, Q be two distributions with the same support and P is absolutely continuous w.r.t. Q. Then the KL divergence from Q to P is where dP dQ is the Radon-Nikodym derivative of P w.r.t. Q.
Definition 4 (Mutual Information). For random variables V 1 , V 2 with joint distribution P V1,V2 , the mutual information between them is Definition 5 (Conditional Mutual Information). For three random variables U, V, W , the mutual information between U, V conditional on W is Before presenting the proof of Theorem 3, we need the following lemma.
Lemma 1. Let U, V, W be three random variables then Proof. Without loss of generality, suppose that U, V, W are all taken values in X . From the definition of mutual information Thus the proof is completed. Now we are ready to give the proof of Theorem 3.
from distribution P , and the spurious attributes of x i is z i . Then where Proof. LetS = {(x i ,ỹ i )} be another n samples drawn from P independent of S. W.o.l.g., we assume For any λ > 0 by Donsker-Varadhan's inequality, Then for any θ, λ > 0, and Lebesgue measurable function g(·), where a is due to the definition of mutual information, L(f θ (x i ), y i ) is M 2 -sub Gaussian, b is from Lemma 1, and the last equality is due to the conditional independence of the model. Thus, we conclude that Thus, we complete the proof.

C.2 Proofs in Section 4.2
Let F(Θ) and · L∞ respectively be the parameterized function class and L ∞ -norm on F(Θ) defined as for any f θ1 , f θ2 ∈ F(Θ). To provide the proof of Theorem 4, we need the following definition of covering number.
On the other hand, as We estimate the P (Y = k) with its empirical counterpart n k = Kz z=1 n kz /n. For bounded sub-Gaussian variable 1 {Y =k} , we have holds with probability at least 1 − δ. Plugging this into (56) and combining (55) we get 58) holds with probability at least 1 − δ due to the definition ofp k . Then suppose inf k∈[Ky],z∈ [Kz] n kz /n k ≥ α, we have where the last inequality is due to the Schwarz's inequality. Combining this with (58), we get That completes our proof.

C.3 Proofs in Section 4.3
In this section we aim at proving that the (9) is a sharp estimator to the CSV when we know a lower bound c for π kz . Note that our problem is equivalent to estimate sup and the bound is sharp when K ≥ 3.
Proposition 3. For k = 1, · · · , K and π k ≥ c, suppose P k are absolutely continuous w.r.t. Lebesgue measure, then we have We have the following lemma to state the some continuities.
Lemma 2. Under Assumption 1-2, we have the following conclusions 1. For φ k ρ (θ, u) with any ρ and k we have Proof. Let us proof the conclusions by order. For the first conclusion, we have where e = (1, · · · , 1). Thus, by Schwarz's inequality, one can verify and and Thus we complete the proof to the first conclusion.
For the second conclusion, by the Lagrange's multiplier method or Theorem in (Yi et al., 2021a), we have the unique closed-form solution of u * On the other hand, due to u ∈ ∆ K 2 z we have where A B means that A − B is a semi-positive definite matrix and I is the identity matrix. The similar w.o.l.g. we assume that Lemma 3. Let L 1 + λ L 11 + L 2 12 /ρ =L, if we have the estimation such that Proof. Due to theL-smoothness of Φ k ρ (·) for any k and ρ we have On the other hand, using the fact that E φk Due to Danskin's theorem and (i), (ii) in Lemma 2 we have Finally, we have Plugging the three above inequalities into (86) and taking expectation to the both sides of the equality, we get This completes the proof of our theorem.
Then we proceed to the next lemma to characterize the dynamic of Lemma 4. For the F k t defined in Algorithm 1, and let δ k (t) = E F k (θ(t)) − F k t 2 , and δ(t) = Ky k=1p k δ k (t), by choosing γ ≤ 2/3, we have Proof. W.o.l.g., we fix the k during our proof. According to E F k (θ(t)) = F k (θ(t)) and E F k (θ(t)) − F k (θ(t)) where we use the fact γ < 1. Then due to the update rule of F k t , Young's inequality and the above inequality, On the other hand, due to the L 11 -continuity of F k (·) and (87), (88) we see Plugging this into the above inequality and weighted summing over k (byp k ) we get and γ = T − 2 5 , then Besides that, for any θ(t) and ρ, we have | Ky k=1p k (Φ k ρ (θ(t)) − Φ k (θ(t)))| ≤ λρ(1/me + 2 log m).
Proof. First, note that m = K 2 z , for any θ, Due to the value of η θ ≤ γ 2 √ 6KyL11L12 we have that Thus we have from Lemma 4. Plugging this into (85) in Lemma 3 and summing up it over t = 1, · · · , T , we have It can be verified that t−1 j=0 (1 − γ/3) j ≤ 3/γ, and plugging this into the above inequality we get whereM ρ =L . Finally from (96) and This completes our proof to the first conclusion. We highlight that the value of η θ satisfies To see the last conclusion, similar to (96) we have that where u * k (θ) = arg max{i : Φ k (θ)(i)}. Due to Theorem 1 in (Epasto et al., 2020), we have which implies our conclusion.

E More Experiments
In this section, we conduct more experiments on a synthetic dataset and real-world dataset to further verify the effectiveness of our proposed methods.

E.1 Toy Example
In this section, we apply the proposed RCSV and RCSV U to a constructed toy example with spurious correlation.
Data. The data is constructed as the example in Appendix B. For two 5-dimensional vectors µ 1 , µ 2 , the training data X follows normal distribution N ((Y µ 1 , Zµ 2 ) , I 10 ) where I 10 is a 10 × 10 identity matrix. The label Y and spurious attributes Z take value from {−1, 1} and are all drawn from a standard binomial distribution (i.e., P Y (Y = 1) = P Y (Y = −1) = 0.5). As in (1), the spurious correlation coefficient σ train Y Z between Y and Z vary on different distribution. We generate 1000 (resp. 200) training (resp. test) samples. Concretely, the 1 is fixed as 0.99 for the unique training distribution, while there are 6 constructed test distributions respectively with σ test Y Z in {0.00, −0.20, −0.40, −0.60, −0.80, −0.99}. As can be seen, the spurious correlations in the test sets are opposite to the one in the training set. Thus, over-fitting the spurious correlation will mislead the trained model.

Setup.
We use the linear model f θ (x) = θ x and its prediction on Y is sign(f θ (x)). We compare the proposed methods RCSV and RCSV U with the baseline methods as in the main body of this paper. The domain generalization methods can be applied with observed spurious attributes is because the data can be viewed as from two domains i.e., data drawn under conditions of Y = Z and Y = Z. The loss function L(·, ·) is cross entropy. The hyperparameters of baseline methods follow the ones in original papers. Our methods are trained by SGD with the used hyperparemeters deferred in Appendix G.4. Main Results. In Table 4, we report the test accuracies of trained models evaluated on OOD data to see if all the aforementioned methods can break the spurious correlation. From the results, we have the following observations.
For all methods, the test accuracies are consistently improved with the decrease of the gap between σ train Y Z − σ test Y Z . This is explained as the decreased σ train Y Z − σ test Y Z leads to smaller mismatches between training and test distributions, thus improving accuracy.
The models trained by the proposed two methods and domain generalization methods (IRM and Group-DRO) can break the spurious correlation (generalize on OOD test data), which verifies the effectiveness of our methods. On the other hand, both RCSV and RCSV U beats the domain generalization methods which require the domain label (i.e., the spurious attributes Z in the constructed dataset). Thus, the extra information required by RCSV (resp. RCSV U ) is equivalent (resp. less) compared with domain generalization methods.
On the other hand, let the last 5-dimensional parameters of the linear model be θ 2 . By X ∼ N ((Y µ 1 , Zµ 2 ) , I 10 ), one can verify that the when θ 2 µ 2 ≈ 0, the output of model θ X does not related to Z with high probability. Then the model can break the spurious correlation.
To see this, in Table 5, we present the cosine-similarity θ 2 , µ 2 /( θ 2 µ 2 ) (the cosine-similarity is used to alleviate the interference caused by scales of the two vectors) of the models trained by methods in Table  4. The results show that the models trained by OOD generalizable methods have smaller cosine-similarities.

E.2 Colored-MNIST
In this section, we empirically verify the effectiveness of the proposed methods on a constructed real-world dataset Colored-MNIST.
Data. Our dataset is constructed on the MNIST (LeCun et al., 1998) which consists of 60,000 training data and 10,000 test data. Each data is a grey-scale hand-written digit from ten categories, i.e., 0 to 9. We construct our Colored-MNIST (C-MNIST) by inducing the spurious correlation in the training and test sets. Concretely, for each digit, we assign two colors as spurious attributes respectively for its foreground and background. The spurious correlation can be induced into such dataset by tying the relationship between the label of digits and the two colors.
We pick 20 specific colors, the first and the last 10 colors are respectively used as 10 categories of two Table 6: Test accuracy (%) of convolution neural networks trained on the different mixtures of C-MNIST-F1 and C-MNIST-R. The OOD test data either C-MNIST-R or C-MNIST-F2. spurious attributes, i.e., the colors of foreground and background of a digit. We consider datasets with two kinds of spurious correlations. The first is fixed spurious correlation, which means data from each specific category of digit is assigned two specific colors respectively for its foreground and background. The other is random spurious correlation which means that for each data, two randomly sampled colors are respectively assigned to its foreground and background regardless of its category. We will construct two C-MNIST with different but fixed spurious correlations (abbrev. as C-MNIST-F1 and C-MNIST-F2), and one C-MNIST with random spurious correlation (abbrev. as C-MNIST-R).
Some of the generated datasets are in Figure 2. As can be seen, the three versions of C-MNIST has different spurious correlations between the label of digits and the colors of foreground and background. Besides that, the spurious correlation in C-MNIST-F1 and C-MNIST-F2 are fixed while C-MNIST-R has randomized spurious correlation.
Setup. We construct various training sets based on the original 60,000 training samples of MNIST. Concretely, we choose α ∈ {0.8, 0.85, 0.90, 0.95, 0.99}, then for each α, we construct a training set with 60, 000 × α 2 samples are from C-MNIST-F1 while the other 60, 000 × (1 − α) are constructed as C-MNIST-R. We use two test sets which are respectively the 10,000 test samples constructed as C-MNIST-F2 and C-MNIST-R. Obviously, the data from C-MNIST-R in the training set alleviates the misleading signal from the training set brought by C-MNIST-F1 due to the spurious correlation between color and digit in it, and the existence of these data meets the Assumption 1.
Our model is a five-layer convolution neural network in (Devansh Arpit, 2019). The models are trained over the 5 aforementioned datasets with different α by the methods that appeared in the above section. One can verify that the training set can be viewed as a mixture of data from two domains, i.e., C-MNIST-F1 and C-MNIST-R. Thus the domain generalization based methods IRM and GroupDRO can be applied here. The used loss function L(·, ·) is cross-entropy, and detailed hyperparameters are presented in Appendix G.4.
Main Results. To see if the models trained by these methods can break the induced misleading spurious correlation, we report their test accuracies on the C-MNIST-R and C-MNIST-F2. The results are summarized in Table 6 with the following observations from it.
The test accuracies of all these methods increase with the decreased α. This is a natural result since smaller α corresponds with more training samples from C-MNIST-R which alleviates the misleading signal from the data with spurious correlation in C-MNIST-F1. Thus models trained over the training set with smaller α exhibit improved generalization ability OOD data with correlation shift.
Similar to the results in Section 6, our RCSV (resp. RCSV U ) consistently improve the OOD generalization error, compared with the methods with (resp. without) observed spurious attributes. More surprisingly, RCSV U beats the methods with observed spurious attributes methods IRM and GroupDRO for a large α.   The observations again verify the efficacy of our proposed methods.
The model trained by the most commonly used method ERM on datasets with small α also generalizes on OOD data. Thus a relatively large number of data without spurious correlation in the training set also breaks the spurious correlation brought by other data.
Finally, we observe that the performance of models on C-MNIST-R consistently better than on C-MNIST-F2. This is due to there exist data drawn from C-MNIST-R in the training set, while the data from C-MNIST-F2 does not appear in the training set.

F Ablation Study
We have discussed in Section 6 that the reweighed sampling trick improves the OOD generalization. Thus, we explore the effect of such trick in this section.
We follow the settings in main part of this paper, expected for the reweighted sampling strategy is set as uniformly sampling, thus the methods ERMRS YZ and ERMRS Y become the ERM. The results are summarized in Tables 7, 8, and 9.
As can be seen from these tables, the OOD generalization performance of model drops for all these methods compared with the results in Section 6, especially for CelebA and Waterbirds, see the column of "Mean" and "Worst" in each table. We speculate this is because the reweighted sampling strategy enables the data in each group are equivalently appeared during training, this operation itself can break the spurious correlation in training data. Another evidence to support the degenerated OOD generalization is the improved test accuracies on the groups with similar spurious attributes in training data, e.g., the better performances on the groups D-F, D-M of CelebA and L-L, W-W of Waterbirds.
The other observation is that even without this trick, our methods improve the OOD generalization compared with other baseline methods due to their better mean and worst test accuracies.
Finally, the trade-off between the robustness over spurious attributes and in-distribution test accuracies is more clearly observed in these tables. This is from the comparisons between accuracy gap of data with same spurious attributes and total accuracy, which is in-distribution test accuracy for CelebA, MultiNLI, and CivilComments.

G.1 Implementation of Two Proposed Algorithms
In this section, we present the detailed algorithm flows of the proposed RCSV and R CSV U in the main body of this paper. The critical part is their estimators to the F k (θ) defined in Section 5.

G.2 Dataset
In this section, we give more details on the datasets appeared in the main part of this paper.
CelebA. This is a celebrity face dataset (Liu et al., 2015) with 162770 training samples and 20362 test samples. For each sample, the hair color {Dark, Blond} is class label, while the gender {Female, Male} is spurious attributes. For both training and test datasets, each of them can be divided into 4 groups, i.e., "Dark-Female" (D-F), "Dark-Male" (D-M), "Blond-Female" (B-F), "Blond-Male" (B-M). The numbers of samples in training and test dataset from the 4 groups are respectively {71629, 9767}, {66874, 7535}, {22880, 2880}, {1387, 180}. Our goal is to train a model that correctly recognizes the hair color of celebrities independent of their gender. One can verify that the most difficult group of data to be generalized on is B-M, due to its extremely small proportion in males in the training set.
Waterbirds. This is a synthetic real-world dataset in ( . For each image, its class label is from {Waterbird, Landbird}, and each bird is placed on spurious attributes: background from {Land background, Water background}. As in CelebA, the datasets can be Algorithm 2 Regularize training with CSV (RCSV). Input: Training samples {(x i , y i )} n i=1 , number of labels K y and spurious attributes K z , batch size S, learning rate η θ , training iterations T , model f θ (·) parameterized by θ. Initialized θ 0 , {F k 0 }. Positive regularization constant λ, surrogate constant ρ, and correction constant γ.

6:
Reweighted sample a mini-batch of data {(x t,i , y t,i , z t,i )} with replacement, the probability of data satisfies y t,i = k and z t,i = z is 1/(K y K z n kz ).

13:
θ(t + 1) = θ(t) − η θ Ky k=1p k ∇ θ (R emp (f θ(t) , P ) + λu k (t + 1) F k t+1 ). 14: end for categorized into 4 groups, i.e., "Landbird-Land background" (L-L), "Landbird-Water background" (L-W), "Waterbird-Water background" (W-W), "Waterbird-Land background" (W-L). The training and test datasets are constructed with the numbers of samples in each group are respectively {3498, 2255} (L-L), {184, 2255} (L-W), {56, 642} (W-W), {1057, 642} (W-L). As can be seen, the spurious correlations in the training and test sets are quite different. In the training set, most landbirds are on the land, and most waterbirds are on the water. But in the test set, waterbirds and landbirds are uniformly assigned on the two backgrounds. Thus, we are desired to train a model that breaks the spurious correlation between bird and background. The proportion of 4 groups in the training set informs that the most difficult of them to be generalized on are L-W and W-L.
MultiNLI. This is a dataset for natural language inference (Williams et al., 2018) with 206175 training samples and 123712 test samples. The dataset is consists of pair of sentences, and our goal is to recognize that whether the second sentence is entailed by, neutral with, or contradicts to the first sentence. It was explored in Gururangan et al. (2018) that there exists spurious correlation in the dataset such as the contradiction can be related to the presence of the negation words nobody, no, never, and nothing. Thus we set such presence as spurious attribute and the dataset can be categorized into 6 groups, i.e., "Contradiction-Without Negation" (C-WN), "Contradiction-Negation" (C-N), "Entailment-Without Negation" (E-WN), "Entailment-Negation" (E-N), "Neutrality-Without Negation" (N-WN), "Neutrality-Negation" (N-N). Our goal is learning a model that makes prediction independent with the presence of negation. The numbers of samples in training and test dataset from the 6 groups are respectively CivilComents. This is a dataset consists of collected online comments (Borkan et al., 2019). The dataset has 269038 training data and 133782 test data. Our goal is to recognize whether the comment is toxic or not. The toxicity can be spurious correlated with the annotation attributes such the presence of 8 certain demographic identities includes male, female, White, Black, LGBTQ, Muslim, Christian, and other religion. Thus we set the identity of any aforementioned words as the spurious attributes, and divided the dataset into 4 groups: "Nontoxic-Nonidentity" (N-N), "Nontoxic-Identity" (N-I), "Toxic-Nonidentity"
The loss function L(·, ·) is cross-entropy for all of these methods. The experiments on image datasets are conducted without learning rate decay while the results on textual datasets are obtained with linearly decayed learning decay via optimizer AdamW (Loshchilov and Hutter, 2018).
As we have discussed in Section 5 and observed in Section 6, the goal of "perfect in-distribution test accuracy" and "robustness over different spurious attributes" are empirically contradicts with each other, thus taking a balance between them is critical to break the spurious correlation. Thus, the proposed RCSV and RCSV U require a carefully tuned hyperparemeters λ. Our λ for RCSV and RCSV U are grid searched in {0.05, 0.1, 0.5, 1.0, 5.0}. The other hyperparameters follow the ones in (Sagawa et al., 2019). Detailed hyperparameters of the proposed RCSV and RCSV U on CelebA, Waterbirds, MultiNLI, CivilComments, Toy example and C-MNIST respectively summarized in Table 10, 11, 12, 13, 14, and 15.