Breaking Correlation Shift via Conditional Invariant Regularizer
Authors: Mingyang Yi
Ruoyu Wang
Jiacheng Sun
Zhenguo Li
Zhi-Ming Ma
Venue: ICLR 2023 poster (2023)
Keywords: OOD Generalization
Spurious Correlation
Optimization

Abstract: Recently, generalization on out-of-distribution (OOD) data with correlation shift has attracted great attentions. 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 models that are conditionally independent of spurious attributes are OOD generalizable. Based on this, a metric Conditional Spurious Variation (CSV) which controls the 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 a provable convergence rate is proposed to solve the problem. Extensive empirical results verify our algorithm's efficacy in improving OOD generalization.  

Published as a conference paper at ICLR 2023
BREAKING CORRELATION SHIFT VIA CONDITIONAL INVARIANT REGULARIZER
Mingyang Y2!.2.3 Ruoyu Wang 12, Jiacheng Sun", Zhenguo Li Zhi-Ming Ma 1.
University of Chinese Academy of Sciences
(yimingyangi7, wangruoyul 7 emmalls. ucas edu. en
2 "Academy of Mathematics and Systems Science, Chinese Academy of Sciences ma zazmaant . ac.cn
Huawei Noah's Ark Lab ssunjiachengl. li. zhenguo www.wei.wwww.coom
ABSTRACT
Recently, generalization out-of-distribution (OOD) data with correlation shift has attracted great attentions. 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 models that are conditionally independent of spurious attributes are OOD generalizable. Based on this, a metric Conditional Spurious Variation (CSV) which controls the OOD generalization error, is proposed to measure such conditional independence. To improve the OOD generalization, process with the proposed CSV. Under mild assumptions, our training objective can be formulated as a nonconvex-concavy mini-max problem. An algorithm with a provable convergence rate is proposed to solve the problem. Extensive empirical results verify our algorithm's 's efficacy in improving OOD generalization.
regularize the training
INTRODUCTION
The success of standard learning algorithms rely heavily on the identically distributed assumption of training and test data. However, in real-world, such assumption is often violated due to the varying cireumstances, selection bias, and other reasons (Meinshausen & Bühhmann, 2015). Thus, learning a model that generalizes
-iitr---iittibttioon (OOD) data has attracted great attentions. The OOD data (Ye et al. (022) can be categorized into data with diversity shift or correlation shift. Roughly speaking, there is a mismatch of the spectrum and spurious correlation between training and test distributions under the two shifts, respectively. Compared with diversity shift, correlation shift is less explored (Ye al.) 2022). while the misleading spurious correlation works for training data may deteriorate model's performance on test data (Beery et al. 2018).
The correlation shift says, for the spurious attributes in data, there exists variation of (spurious) correlation between class label and such spurious attributes from training to test data (Figure Based on a theoretical characterization of it, we show that given the class label, the model which is conditionally independent of spurious attributes has stable performance across training and OOD test data. Then, a metric Conditional Spurious Variation (CSV, Definition 2 is proposed to measure such conditional independence. Notably. in contrast to the existing metrics related OOD generalization (Hu et al. 2020 Mahajan et al.] 2021). our CSV can control the OOD generalization error.
To improve OOD generalization.
regularize the training process with estimated CSV. With observable spurious attributes, we propose an estimator to CSV. However, such observable condition may be violated. In this case, we propose another estimator, which approximates sharp upper bound of CSV. We regularize the training process with one of them, depending on whether the spurious attributes are observable. Our method improves the observable condition in (Sagawa et al. 2019).
Under mild smoothness assumptions, the regularized training objective can be formulated as a specific non-convex concave minimax problem. A stochastic gradient descent based algorithm with a provable convergence rate of order (2/5) is proposed to solve it, where T is the number of iterations.

---

Published as a conference paper at ICLR 2023
CelebA
Waterbirds
MultiNLI
CivilComments
SL economry still
haraer
The home lles men can not.
Sh cconorry nover bear
betler.
Contradictin Nogat on
Tox coxceiienttty (male)
S1: How do you know? thi their infor mation again Shith intormation bolonns to ihem
Porfect, sitcom. I can see how desp your intelligenes lios.
Fark-Fernala Blande-Male
Landbinds-
Water Water
Entailiment- Withou. Negattoo
Nontoric Nonidersity
Figure I: Examples of CelebA (Liu et al. 2015), Waterbi rds (Sagawa et al. 2019), Mult INLI
(Williams al., 2018), and Civi WiviCommentss (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
Finally, extensive experiments are conducted empirically verify the effectiveness of our methods on the OOD data with spurious correlation. Concretely, we conduct experiments on benchmark classification datasets Ce ebA (Liu et al. 2015). Waterbi rds (Sagawa et all] 2019), MultiNIL (Williams et al. 2018), and Civil Commentt (Borkan et al. 2019). Empirical results show that our algorithm consistently improves the model's generalization on OOD data with correlation shifts.
2
RELATED WORKS AND PRELIMINARIES
2.1
RELATED WORKS
The appearance of OOD data (Hendrycks & Dietterich, 201 has been widely observed in machine learning community (Recht al. | [Schneider et al. 22000] Salman ct al.
OOD Generalization.
2020 Tu et al. [2000] Lohn 2020). To tackle this, researchers have proposed various algorithms from different perspectives, e.g., distributional robust optimization (Sinha et al. 2018 Volpi et al.
2018 Sagawa et al. 2019; Yi et al. 20216 Levy et al. 2020) or causal inference (Arjovsky et al.
2019 He et al. 2021 Liu al. 202 Mahajan et al. [021] Wang et al., 2022, Ye et al. (2011). Ye ett al. (2022) points out that the OOD data can be categorized into data with diversity shift (e.g., PACS (Li et al.] 2018)) and correlation shift (e.g., Materbi rds (Sagawa et al., ), and we focus on the latter in this paper, as we have clarified that it deteriorates the performance of the model on OOD
test data (Geirhos et al. 2018 Beery et al. 2018 Xie et al. 2020 Wald et al. 202I).
Domain Generalization. To goal of domain generalization is extrapolating model to test data from unseen domains to capture OOD generalization. The problem we explored can be treated by domain generalization methods as data with different spurious attributes can be regarded as from different domains. The core idea in domain generalization is to learn a Nomain-invariin
model. To this end, Arjovsky et al. (2019); Hu et al. (2020); Li et al. (2018); Mahajan et al. (202T); Heinze- Demll & Meinshausen 2021); Krueger al. (2021) Wald et al. (2021); /Soo et al. (2022) propose plenty of invariant metrics as training regularizer. However, unlike our CSV, none of these metrics controls the OOD generalization error. Moreover, none of these methods capture the invariance corresponds to the correlation shift we discussed (see Section 4.1.. This motivates us to reconsider the effectiveness of these methods. Finally, in contrast ours, these methods require observable domain labels, and is usually impractical. The techniques in (Liu et al. 2021b Devansh Arpit 2019: Sohoni et al. 2020 Creager et al. 2021 are also applicable without domain information, but they are built on strong
assumptions (mixture Gaussian data (Liu et al. 2021b) and linear model (Devansh Arpit 2019)) or require: a high-quality spurious attribute classifeer (Sohoni et al., 2020 Creager et al. 2021)
Distributional Robustness. The distributional robustness (Ben-Tal al. 2013) based methods minimize the worst-case loss over different groups of data (Sagawa et al. 2019 Liu et al. 2021a Zhou et al.) [022]. The groups are decided via certain rules, e.g., data with same spurious attributes (Sagaaa et al. | 2019) or annotated via validation sets with observable spurious attributes (Liu et al.) 202 Zhou et al. 2022). However, (Sagawa et al. (2019) finds that directly minimizing the worst- group loss results in unstable training processes. In contrast, our method has stable training process as it balances the objectives of accuracy and robustness over spurious attributes (see Section 5)
2.2 PROBLEM SETUP
We collect the notations in this paper. || || is the l of vectors. O()) is the order of a number. The sample (x, Y) E X x y, where X and Y are respectively input data and its label. The integer set
2

---

Published as a conference paper at ICLR 2023
- R with 0 ((..)) - M for positive K, M. For any distribution P. let Rpop =Ep(c(f(X),)) and Remp f) = - Di=1 (()()))))) 9i) respectively be the population risk under and its empirical counterpart. Here {( y/ ) are n i..d. samples from distribution P. and f(.) X + R the model potentially with parameter space θ IR (f(+) becomes fo())). For random variables V1, V/2 with joint distribution Pv. V2. Pv; and Pvajv; are the marginal distribution of V1 and the conditional distribution of 1/2 under V1. (v1) and Pvanvi (11, 02) are their probability measures.
from 1 to K is [K]. The cardinal of a set A is |A]. The loss function is L(. R x -
Suppose the training and OOD test data are respectively from distributions P and Qx,Y. We may neglect the subscript if there is no obfuscation. There usually exists similarities between P and Q that guarantee the possibility of OOD generalization (Kpotufe & Martinet, (021). 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 exists spurious attributes E 2 that are not causal to predict class label, but Z is potentially related to class label Y. The Z. can be some features of X e.g., gender of celebrity in Figure [ The correlation between Z and Y (i.e., spurious correlation) can vary from training to test data, and the one in training distribution may become misleading signal for the model make predictions on test data. For example, in the celebrity's face in Figure | if most males in the training set have dark hair, the model may overfit such spurious correlation and mispredict the male with blond hair. Thus we should learn a model that is robust to correlation shift defined as follows.
Definition 1. Given training distribution P, the test distribution Q E P has correlation shift, where
[Qx.y. Qy Py, QxIY, 2 Px|r,2}
(1)
Our definition characterizes the distributions with correlation shift. The first equality in (T) obviates the mismatching caused by label shift (i.c., Py * Qy) which is unrelated to spurious correlation. More discussions of it are Appendix [A] The second equality in ( states the invariance of conditional distribution of data, given the class label and spurious attributes, which is reasonable as the unstable spurious correlations are decided by the joint distribution of Y and Z. Finally, since
Qx (2. 4) = (w ())x(())) Qv(x)) / QxIxz(# Iv. =) (3)
(2)
= Pr((v) / Pxixz y, ())dQz(r( |
the two constraints in ① together implies the correlation shift of Q E is from the variety of
conditional distributions Q ZZ which is consistent with intuition. Our definition is different from the
ones (Mahajan et al.) 2021; Makar& & Amour 2022). as they rely on a causal directed acyclic graph and the existence of sufficient statistic such that Y only affects X through it.
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.
3.1 SPURIOUS CORRELATION MISLEADS MODELS
The common way to train model is empirical risk minimization (ERM Vapnik 1999), i.c., ap- proximating the minimizer of Rpoy (P. f) which generalizes well on in-distribution samples via minimizing its empirical counterpart Rempp (P f). However, the following proposition shows that the minimizer of (P, may not generalize well on the OOD data from the other distributions in P.
Proposition 1. There exists a population risk Reop (P.f) whose minimizer has nearly perfect performance on the data from P, while it fails generalize 0OD data drawn from another P.
while they are not obtained on Similar results also appear in (Xi et al. 2020 Krueger al. 202 the minimizer of population risk. The proof of this proposition is in Appendix B which indicates that the spurious correlation in training data become a misleading supervision signal that deteriorates the model's 'ss 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).
3

---

Published as a conference paper at ICLR 2023
3.2 CONDITIONAL INDEPENDENCE ENABLES OOD GENERALIZATION
Next, we give a sufficient condition proved in Appendix B make the model OOD generalizable. The condition is also necessary under some specific data generating structures (Veitch al. 2021).
Theorem 1. For model f()) satisfying f(X) 1 Z Y, the conditional distribution Y | f(X) and population risk Eo(C((()) Y)] are invariant with (X, Y) ~ Qx,y such that Q & P.
Here f(X)_Z) means given Y, f(X) is conditionally independent of Z. Theorem shows conditional independence obviates the impact of correlation shift, as the prediction error (gap between Y and (X),, decided by Y (X)( and population risk of model are invariant over test distributions Q E Thus we propose to obtain a model that is conditional independent of spurious attributes.
If the spurious attributes are domain labels, the conditional independence in Theorem 7 becomes the ones in Liu et al. 2015 Hu et al. 2020 Mahajan et al.) (027), while they do not explore its correlation with the OOD generalization. Besides, the counterexample in Mahajan et al. 2021) violates our conditional invariant assumption in and hence is not contrary our theorem.
Remark 1.
4 LEARNING OOD GENERALIZABLE MODEL
In Theorem we propose a independence condition to break correlation shift. In this section, a metric Conditional Spurious Variation (CSV) is proposed to quantitatively measure the independence. As our CSV can control the OOD generalization error, smaller CSV leads to improved OOD generalization. Finally, two estimators of CSV are proposed, depending on whether spurious attributes are observable.
4.1 GUARANTEED OOD GENERALIZATION ERROR
shows that the conditional independence between the model and spurious attributes Theorem D
guarantees the OOD generalization. We propose the following metric to measure such independence.
Definition 2 (Conditional Spurious Variation). The conditional spurious variation of model f(-) is
CSV(f) Ey sup (Ex (Ex(C(((X) - (X((E((XX)) L=1.22
=
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. can be computed via training distribution and is invariant across Q E P due to (T. It is worth noting that the model satisfies the conditional independence Theorem has zero CSV but not vice versa. [ However, the following theorem proved in Appendix C.I shows that CSV(f) is sufficient to control the OOD generalization error.
Theorem 2. For any Q E P, we have
sup Remp(S,P) QEP
Us Q)1 & [Remp(. Ryop P)I CSV(J)
(4)
The Remmp -pop) (f,P) is in-distribution generalization error, which well explored (Ver shynin 2018). Thus, upper bound the OOD generalization error via the in-distributional one and
CSV. The OOD generalization error is also connected to many other metrics e.g., (Hu et al.) 2020 Ma
hajan et al. 2021 David et al.) 2007; 2010 Muandet et al. 2013 Ganin et al. (016)), but none of them directly control the OOD generalization error. Besides, these metrics are proposed to obtain the invariance over Z condition, i.e., invariant Py(x),y 2 or PY(o) while the invariances can not
handle correlation shift (Definition. []. As, 1): invariant P P(()) / implies invariant Priz which is
incompatible with correlation shift, 2): invariant Pς(x)z = Sy Prxxyzy (f()) 2, yyy)dPrzzl 2) does not imply invariant P P)(xjr,2z which guarantees OOD generalization.
As bound 4 involves both CSV and in-distribution generalization error, it motivates to explore whether the conditional independence is contradicted by the in-distribution generalization.
'Conditional independence is strong sufficient condition to make model OOD generalizable. However, the proof of Theorem I shows the model that is invariant with spurious correlation Q(Z Y) is sufficient to be OOD generalizable, while the invariance can be characterized by both zero CSV and conditional independence.
4

---

Published as a conference paper at ICLR 2023
The following information -theorrttcc bound proved in Appendix C.I presents positive answer. Let I(V. V22 be the mutual information between variables V1, V2. we have the following result.
Theorem 3. Let model fo(-) parameterized by 0 E ② C IR, and is trained on S = { y/
}
from distribution P. with the spurious altributes of x; is 2s. 1he learned model fas 1 Sz S
Egen S) inf
V
M2
(I(S Syi fos Sg(e)) + T(Sy:
(5)
4n
where Egen(fos P) = E Remm S Sm-9(s)
fee: P)] - Rpop (fez: P),, g(-) is any measurable function,
Ii g(2))) li Sy
1// 1--1-
Our bound improves the classical result Egen (foz: P) S VMIISS, (ss)) without conditional in- dependence (Steinke & Zakynthinou, 2020). because taking g() constant function, then applying data processing inequality (Xu & Raginsky 2017) in r.h.s. of (5), it becomes (M²I(8, 0s) 4n. The bound indicates the model Jes (-) that is conditional independent of spurious attribute (we aim to capture) is not in contradiction with in- in-distribution generalization. Thus, due Theorem 2 less conditional independence with spurious attributes of model improves the OOD generalization bound.
4.2 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..dd {(I;, bi));= training samples with spurious attributes {25 } from P. Before our analysis, we need the following two mild assumptions in the sequel.
Assumption! 1. The class label and spurious attributes are discrete, i.e, the y = [Ky] and 2 = [K_]
for some positive integers Ky, Kg. Besides that, the number of observations A&= {i y/ k. 2i 2} from each pair of (k,j) E [Ky] x [K2] is |Auzl = 1kk >> O.
Assumption 2. The model is parameterized by E θ C gd. The loss function ((fo(x), y) is Lipschitz continuous and smooth w.r.t. O with coefficient Lo and L1, for any (æ, v) E X x y, and 0,, 02 E e,
[C(fe, v) (x), 3)1 - La 0|0 021l: Vo (m), - Vo[(fo, w)ll - T.1 0| 02ll
(6)
In Assumption D we require the spurious attributes space is finite. This is explained as Z is "label" of spurious attributes, e.g., the gender label "male" or "female" in CelebA dataset (Figure [ when classifying hair color. Assumption 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 synthetic some of the missing data
restrict the magnitude of Tkzz For example, to satisfy this, by generative models as in (Wang et al. 2022; Zhu et al. 2017).
Let (fo) = E[C(fo(X) k) Y = k. Z = z]. Liz (fo) = (1/nxz) (1/n)=)EEEAL ((fo(z)), k). and Pu = ng/n with n& = Exe ExE[K.] 7k.-- Then the following empirical counterpart of CSV
CS)
sup #1.
(Cis, (fo) LRss (fo) Pr
k=
is natural estimator CSV. The following theorem quantify its approximation error. Theorem 4. Under Assumption 7 and 2 if inf nx=/ Wxz/nz- = O(1), then
log (1/5)
CSV( S CSV +o
(8)
vn
holds with probability at least 8 for any 0 0,8 O.
This theorem implies that CSV upper bounded by CSV (fe). As shown in the proof in Appendix we hide factor related to covering number (Vershynin 2018) of the hypothesis space in the
C.2
numerator of O (log (1/8)/ /n) in (8. The hidden factor is of order v/d (Wainwright) 2019). Thus, more samples are required to estimate CSV in high- dimennioonl space. Besides that, if the condition inf Mikz/Ns. (11) does not hold, the order of error is O(1/ / Tiaa) (see Appendix C.2
for details).
20s is the learned parameters depends training set S. fo. (.) is random element that takes values in functional space (i.e., model space), details can be referred (Shiryaev 2016..
5

---

Published as a conference paper at ICLR 2023
Algorithm I Regularize training with CSV.
Input: Training set {(x,, y/ J=) number of labels K2 and spurious attributes Ke, training steps T, model (o)-) parameterized by 0. Initialized 0o, {Fo). Positive regularization constant X, surrogate
constant p. and correction constant Estimators Remp(Jo, P) to Remp(oo. P), F (0) to F* (0).
1: for t = 0,... ,T' do
2: Solve the maximization problem:
3: for k = 1, ................... K2 do
4: F t-1 (1 (1 + 7 (0(1));
5: un (t 1) Softmax (F p1tp)).
6: end for
7: Minimization step via SGD:
K
8: ( + 1) = (t)) - n1 L De Vo (eem(() P) + (u 1) 1)T Fbk F)41).
9: end for
4.3 ESTIMATING CSV WITH UNOBSERVABLE SPURIOUS ATTRIBUTES
Computing the empirical CSV requires observable spurious attributes which may not be available in practice (Liu et al. 2021a). Thus, we need to estimate CSV in the absence spurious attributes.
Let Pk: P ==, be the conditional distributions of X with Y, Z given. The core difficulty of estimating CSV with unobservable spurious attributes is to estimate sup, Ep,, [A[Jo(X) (X), k)] inf_ E.,,, [((o(()) (x),:) via ni: independent samples ((x,, Jie drawn from mixture dis- tribution Ps= _xe(k.] TkzP Here A& Use[k_] A&z for k [Ky]. Ps Pxjy=k.
Thk = (
k), and we can specify the data in A& is from which of ARa-
To proceed, suppose Thk 2 > 0, which is a necessary condition for Assumption to hold. We show in Appendix [C.3 that the quantile conditional expectation
(9) upper bound (which is sharp for K 2 3) of sup, Er, ((( k)] inf, Ep,,, Er,,, [X),
Er, (r)) ((f((X)
2 qr, - c)] - Er, (C(F((X), R) ((fo(X), b) & 9r, (c)
Here qp, (-) is the quantile function defined as qp, (s) = inf(p Pa( P) 2 s}. For
large n&, must have πı= 2 1/nz= c for each E [K=]. Thus by substituting the expectation on
Pk in (9) with its empirical counterpart for e = 1/ng, we get the the following estimator
CSVu(So)
maxx((f((x.,. k)) min ((S((x)))))) Pk. AE
(10)
AE
The subscript "U" means "unobservable spurious attributes". Besides that, the CSVu(fe) is an upper bound to the estimator (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(fe) and CSV (ff).. 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.
is notable that both of the regularized training objectives can be formulated as the following minimax problem for positive constants m and X
Ky
Remp(fo P}+ max u Fm (0) u uEam
min GCG
Du
(1I)
Here Am = {u (ui...., um,) E RT. Σ, u; 1). F* (0) (0)= E RT and each dimension of F* (e()) Lipschitz continuous function with Lipschitz gradient. Under Assumption T andd] 2 the training

---

Published as a conference paper at ICLR 2023
process of empirical risk minimization regularized with CSV(So) or CSV be formulated as the above problem by respectively setting F² (0) as the vectorization of the two following matrices. The m of CSV (fo) and CSVu(fe) are respectively K² and |Ax (Lueg (Sa) Exeg (So)) =(1())))) (L(fe(a))) ). L(fa (212) 1))
(12)
Before solving I we clarify the difference between regularizing training with CSV and distri- butional 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 minimizes max,,2 E... [C(f((X) k:). 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 them into one objective. Though both objectives theoretically upper bound the loss on OOD data, we empirically observe that the two goals in contradiction with each other (see Section (). We also observe that splitting the two goals (our objective) enables us easily take a balance between them, which guarantees 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 are also observed in (Sagawa et al. (019)). This motivates the early stopping or large weight decay regularizer used in GroupDRO.
5.1
SOLVING THE MINIMAX PROBLEM
Let Φ² (0. 4 = Remp(fe. P) + Au FO) (0) max 0² (0. u). Under Assumption
I and 2 is a nonconvex-coneave minimax problem. As explored in (Lin et al.) (020), the
nonconvex vonconyex-strongly concave minimax problem is much easier than the nonconvex-concave one. Thus we consider the surrogate of (00 u) defined as (0, u) = Ø* (0, u) Ap Σド= u(j) log (mu((j)
for Ap > O, which is strongly concave w.r.t. u. and o² (0, u) is well approximated by it for small p. Next, we consider the following nonconvex-strongle concave problem
min
D&
max (0 u) min du ())), Am
(13)
instead of 111. where T (0) uEA. (0, u). To solve 13 propose the Algorithm 1
In Algorithm lines 3-6 solve the maximization problem in 13 which has close-formed solution
( Softmax(FFF ( (8(t)) YYi et al. 2021a), where Softmaxx() is the softmax function
(0) in the moving average correction Ft (Line 4) to estimate F* (0(t)). which guarantees our convergence result in Theorem The convergence rate of Algorithm]
(Epasto et al. 2020). As the estimator F' (0) may have large variance, substituting the F (t + 1) with it in Line 8 (the minimization step) will induce large deviation. Thus F*(0)
1 is evaluated via approximating first-order stationary point, which is standard in non-convex problems (Ghadimi & Lan 2013 Lin et al. 2020).
and 2 if Remp (fo, P) and F* (0) are all unbiased estimators with bounded variance, ((t) is updated by Algorithu with Th = 0 (T-3 and T 33 then
Theorem 5. Under Assumption
K2 de vot((()))
$ 0 20 (1-
min E ISET
(14)
Besides that, for any (l) and p. we have EK in Φ ( (0(1) t* (0(I)) S Xp(1mme log m).
The theorem is proved in Appendix D and it says the first-order stationary point of the surrogate loss (-) is approximated by ((t) in Algorithm | in the order of ( (can be improved to
1/2- when 0² = ((2-1/2)) As the gap between (*(+) and (-) )) is O(p), taking small yields small &x (0(T)). The unbiased estimators in our theorem constructed in the next section.
6 EXPERIMENTS
In this section, we empirically evaluate the efficacy of the proposed Algorithm I in terms of breaking the spurious correlation. More experiments are shown in Appendix F
7

---

Published as a conference paper at ICLR 2023
Table I: Test accuracy (%) of ResNet50 on each group of Ce Celeba ebb and Waterbirds.
Dataset
Method / Group
D-
D-M
B.F
B-M
Avg
Total
Worst
SA
RCSV
92.1
94.0
92.3
91.8
92.6
92.9
91.8
IRM
92.8
93.1
88.9
89.3
91.0
92.3
88,9
GroupDRO
94.4
94.6
88.9
88.3
91.6
93.7
88.3
ERMRSyz
88.8
94.7
95.8
85.6
91.2
91.9
85.6
CelebA
RCSVu
88.3
97.8
96.1
76.9
89.8
93.3
76,9
Correlation
87.6
96.3
96.8
69.4
87.5
91.9
69,4
X
ERMRSy
91.3
97.5
91.0
62.2
85.5
93.3
62.2
X
Dataset
Method / Group
L-L.
L-W
W-L.
W-W
Avg
Total
Worst
SA
RCSV
93.4
90.8
88.6
89.4
90,5
91.4
88.6
93.1
87.7
87.4
89.7
89.5
90.4
87.4
GroupDRO
92.0
87.8
87.9
90.3
89.5
89.7
87.8
ERMRSyz vz
93.2
88.5
87,9
91.3
90.2
90.6
87,9
RCSVc
98.5
81.2
81.3
95.5
89.1
89.5
81.2
Waterbi rds
Currelation
98.8
74.4
70.9
93.0
84.3
85.5
70.9
ERMRSY
99.3
76.7
68.8
94.9
84.9
86.6
68.8
Table 2: Test accuracy (%) of BERT on each group of Mu 1 t iNLI.
Datasel
Method / Group
C-NN
C-N
E.WN
E-N
N-WN
N-N
Avg
Total
Worst
SA
RCSV
77.1
95.3
83.5
79.5
81.3
78.6
82.6
81.5
78.6
V
IRM
79.7
96.9
80.4
71.7
77.2
71.7
79.6
79.9
71.7
V
GroupDRO
77.4
93.5
82.5
79.7
81.5
77.6
82.0
81.3
77.6
ERMRSyz
74.7
89.5
79.1
72.3
82.0
71.8
78.2
79.3
71.8
McltiNLI
RCSV
79.3
95.5
82.0
74.3
78.1
70.8
80.0
80.6
70.8
X
Correlation
76.2
94.7
76.7
67.9
75.5
67.9
76.5
77.0
67.9
X
ERMRSY
82.7
95.5
79.4
72.6
79.7
67.3
79.5
81.1
67.3
X
The Algorithm can be applied to the regularized training process with either (So( (RCSV) Cf) (RCSVu) depending whether spurious attributes observable. The implementations clear after estimating Remp(Je(e), P) and (*(0) in
Implementation.
For RCSV, in each step t, we let (fot) P) be the empirical risk over uniformly drawn batch (size 5) 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 2 be sampled is 1/(K, m,aa). Then the Laz (Je())
12 is estimated as the conditional expected risk over this batch of data.
For RCSVU. in each step I, the Remp(Seco) P) is as in RCSV. We also randomly sample another mini-batch (batch size 5) of data with replacement but the probability of data with label be sampled is (/(K,n)), We estimate F (0) in (2) via its empirical counterpart over these sampled data.
As can be seen, all of the resulting (emp(fott) P) and F" (0(t)) are unbiased estimators with variance of order O11/S) as in Theorem 5] Besides that, our RCSV (resp. RCSVv) can be implemented with (resp. without) observable spurious attributes. The complete implementation of RCSV and RCSVu are shown in Appendix G. When estimating CSV, the data are sampled with weights that are inversely proportional Tiks or fig. The sampling strategy also appears in (Sagawa et al. 2019: Idrissi et al. 2021 Arjovsky et al., (2099) which significantly improves the OOD generalization according to our ablation study in Appendix
Data. We use the following benchmark datasets with correlation shift (see details in Appendix G.2).
Celeba (Liu et al., 2015). An image classification task to recognize celebrity's hair color ("dark" or "blond"), which is spuriously correlated with the celebrity's 's gender ("male" or "female"). The data categorized as 4 groups via the combination of hair color and gender, e.g., "dark-female" (D-M).
Waterbirds (Sagawa et al. 2019). An image classification task to recognize a bird as "waterbird" or "landbird",, while the bird is spuriously correlated with background "land" or "water". The data are categorized into 4 groups, e.g., "landbird water" (L-W).
MultiNLI (Williams al. 2018). Given sentence-pair, the task aims to recognize the relationship between the two sentences, i.c., "entailment", "neutrality", "contradiction". The relationship is spuriously correlated with the presence of negation words. The data are categorized into 6 groups, (C-N).
e.g., "entailment without negation" " (E-W), "contradiction-negalie
2019 A textual classification task to check whether sentence is CivilCommer (Borkan et al.
toxic or not with the label spuriously correlated with whether any certain demographic identities mentioned. The data have 4 groups, e.g., "nontoxic-identity" (N-I), "toxic-nonidentity" (T-N).
8

---

Published as a conference paper at ICLR 2023
Table 3: Test accuracy (%) of BERT on each group of Civi iivllle Commentts.
Dateset
Method Group
N-N
N-1
T-N
T-1
Avg
Total
Worst
SA
RCSV
93.1
87.7
82.4
71.7
83.7
89.3
71.7
IRM
96.2
88.5
68.0
67.5
80.1
90.3
67.5
GroupDRO
94.5
88.7
76.3
69.4
82.2
90.0
69.4
FRMRSvz
94.3
88.8
79.1
70.0
83.1
90.0
70.0
V
civilComments
RCSV
96.2
89.5
72.6
68.7
81.7
90.9
68.7
X
Correlation
94.1
85.2
65.5
83.5
89.6
65.5
ERMRSy
98.0
94.4
61.0
57.2
77.7
92.3
57.2
X
Setup.
We compare our methods RCSV and RCSVu with four baseline methods (see Appendix for details) i.e. ERM with reweighted sampling (ERMRS) (Idrissi et al., al., (202I), IRM (Arjovsky
G.3
et a1.
2019), Gro (Sagawa et al. 2019), and Correlation (Devansh Arpit 2019).
The GroupDRO and IRM use the reweighted sampling strategy in RCSV. while the Correlation uses same one with RCSVU- As these sampling strategies improve the OOD generalization (Idrssi et al. 2021). D. to make fair comparison, we also conduct ERMRS with the two sampling strategies. The two ERMRS are respectively denoted as ERMRSy and ERMRSyz. The involved methods are categorized as 2 groups, i.e., conducted with observable spurious attributes (RCSV, IRM, GroupDRO, ERMRSyz) and with unobservable spurious attributes (RCSVU. Correlation, ERMRSy. Correlation).
The backbone models of image (CelebA, Waterbi rds) and textual datasets (MultiNLI. Civi WrrilComments s) are respectively ResNet-50 (He ct al. 2016) pre-trained on ImageNet (Deng et al.
2009) and pre-trained BERT (Devlin al. 2019). The hyperparameters are Appendix G.4
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 in-distribution test accuracy expected for Wat Materbi rds), and the worst test accuracies over groups ("Worst")). The results are in Table 2 The "v" and "x" for SA (spurious attributes) respectively mean whether the method requires observable spurious attributes. The observations from these tables are follows.
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 criteria, the proposed RCSV (resp. RCSVc) 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 RCSV
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 Celebà and Wat erbi rds, 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 smaller gap between the test accuracies 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.
groups with the same spurious
7 CONCLUSION
In this paper, we explore the OOD generalization for data with correlation shift. After a formal characterization, we give sufficient condition 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, proposed to measure such independence. Based on this metric, we propose an algorithm with provable convergence rate to regularize the training process with two estimators of CSV (i.e., RCSV and RCSVv), depending on whether the spurious attributes are observable. Finally, the experiments conducted on the datasets CelebA, Waterbirds Mult iNLI, Civi Wovimommentss verify the efficacy of our methods.

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. Preprint arXiv:1907 02880002808 2019.
Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. In European Conference on Computer Vision, 2018.
Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, et al. Analysis of representations for domain adaptation. Advances in Neural Information Processing Systems, 2007.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175, 2010
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):41-337, 2013. 2013.
Pierre Bernhard and Alain Rapaport. On a theorem of danskin with an application to theorem of Von neumann-sion. Nonlinear Analysis: Theory, Methods & Applications, 24(8):1163-1 1995.
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. World Wide Web conference, 2019.
Elliot Creager, Hoen-ke Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference on Machine Learning, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Puttern Recognition, 2009.
Richard Socher Devansh Arpit, Caiming Xiong. Predicting with high correlation features. Preprint arXiv:1910.0016: 2019.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutamova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics, 2019.
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Emmanouil Zampetakis. Optimal approximation-ssmoolee tradcoffs for soft-max functions. Advances in Neural Information Processing Systems, 2020.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François training of neural networks.
Laviolette, Mario Marchand, and Victor Lempitsky. Journal of Machine Learning Research, (7(1):2096222 20300, 2016.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel. Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness. In International Conference Learning Representationss, 2018.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (144):2341-236) 2013.
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2020.
Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A Smith. Annotation artifacts in natural language inference data. In North American Chapter of the Association for Computational Linguistics, 2018
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition, 2016.
10

---

Published as a conference paper at ICLR 2023
Yue He, Zheyan Shen, and Peng Cui. Towards non-iid image classification: A dataset and baselines. Pattern Recognition, 110: 110:107383, 2021.
Christina Heinze-Deml and Nicolai Meinshausen. Conditional variance penalties and domain shift
robustness. Machine Learning, 1002):003-448, 2021.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In International Conference on Learning Representations, 2018.
Shoubo Hu, Kun Zhang, Zhitang Chen, and Laiwan Chan. Domain generalization via multidomain discriminant analysis. In Uncertainty in Artificial Intelligence, 2020.
Badr Youbi Idrissi, Martin Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst-group-accuracy Preprint, 2021.
Samory Kpotufe and Guillaume Martinet. Marginal singularity and the benefits of labels in covariate- shift. The Annals of Statistics, 49(6))3299-3322 2021.
David Krueger, Ethan Caballero, fbern-Henria Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapola- tion (rex). In International Conference on Machine Learning, 2021.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( 36(11):2278-233 1998.
Daniel Levy, Yair Carmon, John Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization, Advances in Neural Information Processing Systems, 2020.
Da Li. Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales. Deeper, broader and artier domain generalization. In IEEE International Conference on Computer Vision, 2017.
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In European Conference Computer Vision, 2018
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems, In International Conference on Machine Learning. 2020.
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. International Conference on Machine Learning. 2021a.
Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. In International Conference Machine Learning, 2021b.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In IEEE International Conference on Computer Vision, 2015.
Andrew Lohn. Estimating the brittleness of ai: safety integrity levels and the need for testing out-of-distribution performance. Preprint arXiv:2009.00800 2020.
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael Jordan. Conditional adversarial domain adaptation. Advances in Neural Information Processing Systems, 2018.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018
Divyat Mahajan, Shruti Tople, and Amit Sharma. Domain generalization using causal matching. In International Conference Machine Learning, 2021.
Maggie Makar and Alexander D' A'mour. Fairness and robustness in anti-causal prediction. Preprint, 2022.
Nicolai Meinshausen and Peter Bühlmann. Maximin effects in inhomogeneous large-scale data. The Annals of Statistics, 43(4): 1811-1800, 2015.
11

---

Published as a conference paper at ICLR 2023
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In Interaational Conference on Machine Learning. 2013.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning. 2019.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. 2019.
Hadi Salman, Andrew Ilyas, Logan Engstrom, Sai Vemprala, Aleksander Madry, and Ashish Kapoor. Unadversarial examples: designing objects for robust vision. Preprint arXiv:2012.12255 2020.
Steffen Schneider, Evgenia Rusak, Luisa Eck, Oliver Bringmann, Wieland Brendel, and Matthias Bethge. Improving robustness against common corruptions by covariate shift adaptation. In Advances in Neural Information Processing Systems, 2020.
Seonguk Seo, Joon- Young Lee, and Bohyung Han. Information- -iformttion-theorttii bias reduction via causal view of spurious correlation. Preprint arXiv:2201 Kiv:2200.00111,, 2022.
Albert Shiryaev. Probability-,, volume 95. Springer, 2016.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
Nimit Sohoni, Jared Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré. No subclass left behind: Fine-grained robustness in coarse-grained classification problems. Advances in Neural Information Processing Systems, 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, 2020.
Lifu Tu, Garima Lalwani, Spandana Gella, and He He. An empirical study on robustness to spurious correlations using pre-trained language models. Transactions of the Association for Computational Linguistics, 8:621-633, 2020.
Aad W. van der Vaart and Jon A. Wellner. Weak convergence and empirical processes. Springer series in statistics. Springer, 2000.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Victor Veitch, Alexander D' Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invariance to spurious correlations: Why and how to pass stress tests. Advances Neural Information Processing Systems, 2021.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation. In Advances in Neural Information Processing Systems, 2018.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. Technical report, 2011.
Martin J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Yoav Wald, Amir Feder, Daniel Greenfeld, and Uri Shalit. On calibration and out-of-dommin generalization. Advances in Neural Information Processing Systems, 2021.
12

---

learning. In International Conference on Published as a conference paper at ICLR 2023
Ruoyu Wang, Mingyang Yi, Zhitang Chen, and Shengyu Zhu. distr--disttibttion generalization with causal invariant transformations. In Conference on Computer Vision and Pattern Recognition, 2022.
Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Conference of the North American Chapter of the Association for Computational Linguistics, 2018.
Sang Michael Xie, Ananya Kumar, Robbie Jones, Fereshte Khani, Tengyu Ma, and Percy Liang. In- n-out: Pre-training and self-training using auxiliary information for out-of-distribution robustness. In International Conference on Learning Representations, 2020.
Aolin Xu and Maxim Raginsky. Information-theoretti analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, 2017.
Haotian Ye, Chuanlong Xie, Tianle Cai, Ruichen Li. Zhenguo Li, and Liwei Wang. Towards theoretical framework of -itor--distiitttion generalization. Advances in Neural Information Processing Systems, 2021.
Nanyang Ye, Kaican Li, Lanqing Hong, Haoyue Bai, Yiting Chen, Fengwei Zhou, and Zhenguo Li. Ood-bench: Benchmarking and understanding out-of-distributicn generalization datasets and algorithms. In Conference on Computer Vision and Pattern Recognition, 2022.
Mingyang Yi, Lu Hou, Lifeng Shang, Xin Jiang, Qun Liu, and Zhi-Ming Ma. Reweighting augmented samples by minimizing the maximal expected loss. In International Conference Learning Representations, 2021a.
Mingyang Yi, Lu Hou, Jiacheng Sun, Lifeng Shang, Xin Jiang, Qun Liu, and Zhi-Ming Ma. Improved ood generalization via adversarial training and pre-training. In International Conference on Machine Learning, b021
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, (0(6):1452-11 2017.
Xiao Zhou, Yong Lin, Renjie Pi, Weizhong Zhang, Renzhe Xu, Peng Cui, and Tong Zhang. Model agnostic sample reweighting for Machine Learning, 2022.
Jun- Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. In IEEE International Conference Computer Vision, 2017.
13

---

Published as a conference paper at ICLR 2023
A LABEL SHIFT
In the sequel, we may omit the subseribe 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.c., Py Qr In this section, we explore OOD generalization without such invariant assumption. Before presenting discussion, give the definition of total variation distance.
Definition 3. The total variation distance between two distributions P, P.Q defined on the same measurable space X is
TV(P,Q)= - 1 [dP(=)
(15)
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) 1. 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 Z E 11,,] and a specialized loss function
(16) where f(-) is any classifier whose output is in {-1, 1]. Let P. Q be two distributions such that Pxjy, Qxly, but Py Qr. We suppose X 1 Z Y, and thus f(X) 1 Z Y. Thus,
((f(X), [(y (5 f(X) (yy--1 (2 f(X)),
Pxiy (w v) = Σ Px.2Ix 1v) = (x I 8) Σ P22r (2r(=11)
(17)
unrelated P2Ix- Then have PxnY Qxlx- Thus [P([[f((X), Y)) Py (Y
Py -
Eo(C(f(X), Y)) Qy (Y 1) -
-1)) (18)
Since Pxiy = Qxl..
Ep X]]
- Ex)
-(Pr(Y ( -
2 2/1-3| (>(((==))) =1)-Q(Y==1)
(19)
=Irr(Y= -yy= 1]]
= -TV(Py,QY).
where TVPY,, Qy) is the total variation distance of the marginal distributions Pr This inequality holds for any f(X), and hence the gap can never be removed by representation learning like what we do in Theorem
The example indicates that under shifted label distribution, the conditional independent model can not generalize on OOD data. Thus, we consider the reweighted loss 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 Pxiy,z QxIY z but Py does necessary equals Qy. w(y): Y.
R is weighting function satisfies Er (Y)] 1. Then if fXX 1 Z
[P(u(())(S(())))) Ex(C(((X)) Y)JI S 2MTV where py is the reweighted label distribution defined as PY (A) SA w(y)dPy (v) for any measur- able set C y
(20)
Proof. Because PxIY,2 = Qxlr.z and f(X) 1 Z Y. as in Appendix C.1
have P(ʃ(X)
Y) Q(f(X) |Y). Thus
EEp (C)))((()(())))))))))))))))))))) Y)) (() Y)JI
1/ (())))
v)dPr - / YEY
Bolc(f(X), = s)dQr(1)
(21)
< S M w(y)dPy dQQy
= (MMV(P",Q')
14

---

Published as a conference paper at ICLR 2023
Remark 2. The total variation distance TVPP Qy) appears in the upper bound to the gap between the two population risk in (Ip. Moreover, this terms seems to inevitable since it also appears in the lower bound in
According to Theorem we have invariance
invariancce relationship [P = Y)I
we can take w(y) dQy (y)/dPy Thus the label distribution the test data 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 usually unavailable in practical. Thus for unknown test label distribution, we alternatively chose the weight wo(-) to minimize the worst-case upper bound
sup (V, = sup / Iool))dy (v) dQy (v)l,
(22)
given the training distribution P, where the supremum is taken over all distributions Q such that Qxly.z PxIy.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 discrete space, then if Py y) 0 for all y y and w* (v) (Y=)(Y= we then have
w (+) arg o [[)p)(()))
sup TV(PV,0r) QEP
(23)
where [ is the cardinal yf
Proof. From Section A.6.2 in (van der Vaart & Wellner
2000 we know that TV(PY, Qr)
supAcy Eyea w(y) Py (Y = y) Qr(y= = D)|- Thus
sup TV(PV,Qv) = sup sup QEP ACY
Σ
wry) = Qr = v)
QEP
yEA
welv (F (Y -r =z) (24)
Σ
sup QEP
=1 - w Py = yey
due to wy = y) 2 and Ep [Y() Then, we have
{ min wy)) (Y = v)
min sup TV(PV,Qv) w())Ep(((()==]@e>>
min x())
yCy
min (s = m) yEy
max wi [()pp(e()]]
(25)
= 1 w (Y =
D
D
The third equality is due to |}] mingey wy = 1) S EvEy w( = y) = 1, and the
equality is taken when w(.) = w.).
L
B PROOFS IN SECTION 3
In this section, we present the proofs of results in Section Proposition 1. There exists a population risk Reop (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 E P.
Proof. Let us consider the following example that
Y 14
X
E,
(26)
Z .
15

---

Published as a conference paper at ICLR 2023
where & ~ (0, Id +d2) 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 (Q) for Q P. One can verify that
(Q) = [ Q(Y = Z) Q(Y + Z) 2Q(Y =Z) - 1.
(27)
Let us consider the linear classifier fo(x) aT x and its loss on data (X, is the exponential loss Soudry et al. (2018)
((fo(X), Y) = -
(28)
Thus we can compute the population risk
Reop fo) Ep lexp( (o())
(-07 14 Y20, 21 0TE)) $)]
= E exp
(-OT 14, -0% 21 0 6) |Y 3 P(Y Z)
exp
+ E
exp
(-0T M4 + 0, 22 + 00 6) Y * 2 P(Y + Z)
(29)
+
(P)
0 14 0 112 + 1012)
exp
2
Tyz
01 14 + ||01 +
exp
- 0 14
2
2
Since Roop PP, {o) is continuous w.r.t. to (P) and 0, we have that (P)
arg ming Roop P. Se) is continuous to z (P)) (P). Since oyz (P) 1-,,1], we conclude 1 (P) is
upper bounded. W.o.lgg we assume ||0 (P)]l < 1 for any zy (P) E [-1, 1]. then for any or
we know 0 (P) satisfies the first order optimality condition such that
+ (P)
(P)(P) 1)) exp
(-0"
0 11 + |
2
(30)
1 (P)
-00 ju + |1013
+
(0'(P) jD) exp
2
where jt =NUT, -1²) -T Thus for 0yz (P) +1 we have
('(P) === 1 1
or 1=11
(īs -0--0" 00 (P)()))) (20 (20Tu²)
(31)
Thus we can take dyz (P) + to make |00 (P) - pll S |||رك| for any small where the can be independent of μ..
Now we show that the linear model for (-) with its prediction on Y as correct prediction with high probability. Let us see the error of linear model for(p)()) on the data from training distribution P. Simple algebra show that 0* (P)X Y N(Y0; (P) Z0, T (P) ||0] (P)] Then under condition of Y Z, we have
can make
0- ('T()X- || = Yo (P) || 0 TT = Y (0) u) # - T (32)
Thus from the sub-Gaussial property of Gaussian random variable, for any >
Pxir
||lul 2
=PxY ( (P) -YIlll? 2 2 = 7)
1 1+ox
2
PXXx (0 ((TT (P))--Y|mm]] 2 28Y # z)
(P2
2
(33)
$ SPx (00 (177 26 8- =cllla |,,Y z)
+ Trz +zzz
(1 (y
+
2
2
(8 (5-c|lul37 [+
Drz
<exp
22
2 +
2
16

---

Published as a conference paper at ICLR 2023
We may take 8 = |/ + c||m] and (P) - 1, due to [|((oyz(P)]] I and for large
enough ||ll with a high probability, we have
|ll -(2 + |all < 0 TP)X S YIlall++ + 22+ |lall )
+
(34)
Since + for zy + 1, we have proved that the population minimizer O'(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
Qxrr (0OT Y( |22 21)
2 51 211)
s exp
(6 -8--epa c||mu19)
( 1 orz
(1)0"
(35)
1 +xx
2
for any 8 > Again, by taking σy zyz(Q) -1 we get
(| (|p2211) (2- -)) (112211 + || - 00 _0'T())
(36)
1
<Y(lu, 111gg1 )
+
+ (1lsa + (1221)
2
with high probability. We can take, for example, || >
3+22c
|| 1| for c + 0, then under
1-c
Y = 1, the inequality becomes
< (3 - || 12 11a=111-22
+ (2+
| 0 S (P)X < (3
|| (1==11((---)) 1l 11?
2 +e)
(37)
which shows the prediction given by Se (p)))) for Y = -1 incorrect with high probability. similar argument can be verified for Y = 1. Then we complete proof.
For model f()) satisfying f(X) 1 Z Y, the conditional distribution Y fX) and population risk (X),( Y)] are invariant with (X,Y) Qx,y such that Q E P.
Theorem 1.
Proof. The difference of Y fX) for any (X ~ Q with Q E P originates from the different spurious correlation i.e., the different QZIY. Thus to obtain our result, it is suffice to prove that the distribution of Y s(X) is independent of QZY. To see this, for any measurable sets A, B C.
Qrix E A f(X) E B)
( A)Q E = (xxr(f(X) ( Y A)Qy E A) Qxxxxx(((()) e BIY & A)Qr & A)
(38)
I+ QUIUUINEEBBYEANYYYYYYY QAIIUURREEBYYEAANYYYYYE
As QY & AY A) is invariant across Q E P. Then for the (f()) B $
A)(2xIy(J(X) E B BIYE E A), we see
Qxir(f(X) E B [ B, Y & A)dz (
[xxxxx(((() E B, Y E A)dz
(39)
(xiv(f(X) B Y A) f Qzly Y & A)dz
Qxir E B Y e A) fe Qzi E A)dz'
where the second equality is from the independent condition that f(X) 1 Z Y. From the calculation, we figure out that the distribution of Y f(X) is independent of spurious correlation
Pziy due to the arbitrariness of A, B V. Then we prove Y S(X) is invariant over Q E P..
To provide the invariance of Eo( Y)], is suffice to show that for the union distribution of (f(X), Y) is invariant w.n.t. Q for Q P. Thus for any sets A, B C y and (X, (X,Y)~ ~ Q E
Qy f(x) B) = Qx (J(X) e B E A)Qr(Y A
= e A) / Qxxiv(((X) E B A)dz
(40)
=Qr(V A)(x)(((XX) B BIYE Q21(22 Y A)ds.
17

---

Published as a conference paper at ICLR 2023
Since f(X) 1 Z YY, figure out the Qx,y (Y E f(X E B) is independent of with spurious correlation Qzr. Then due to the arbitrary of A, B E V we summarize that the union distribution of (f(X),)) invariant w.r.t. Q for Q P. Then the proof completed.
C PROOFS IN SECTION
C. PROOPS IN SECTION
Theorem 2. For any Q E P, we have
Rempps P) Rp Q)1 [Remp[s, P) Ppp P)1 CSV(F) QEP
sup
(4)
Proof. This theorem can be computed via the assumption in 1I We have
EP(C(((X) Ep [E(((((X)))) Y. []
Ey // Ex (x((XX)) () Y, = ==)d==
(41)
Due to (T) the first expectation is invariant with P.Q E P, while the second expectation is function of (Y,2) independent the choice of P. Thus
[E(C(((X)) x)] Eo(C([(X), < sup [X)C Y - |Y, =2
L=1.22
CS)(f),
(42)
where the last inequality is due to the loss function is non-negative. Then due to [fm P)- (f Q)1 Remp (f, P) Roop (f, P)] sup RRop (f, P) Peop (f; Q)1 QEP
sup
QEF
(43)
Remp (f, P)- Ryop (1, P)] CSV(S),
we get the theorem.
Next we provide the definitions of KL-divergence, mutual information, and conditional mutual information which are useful to prove Theorem
Definition 4 (KL-Divergence). Let P, Q be two distributions with the same support and P is absolutely continuous w.r.l. Q. Then the KL divergence from Q to P is
dP DRL Q) = EV-o 1oog
(v)
(44)
aQ
is the Radon-Nikodym derivative of P w.Ell Q. For random variables V1, V2 with joint distribution Pvi,va, the mutual information between them is
where dP 2Q
Definition 5 (Mutual Information).
T(V1; V2) DKL((v,.v || Pv, x Pv2)-
(45)
Definition 6 (Conditional Mutual Information). For three random variables U,V, W, the mutual information between U.V conditional on W is
I(U:V W) = = [T(U W w; V W ww)
(46)
Before presenting the proof of Theorem we need the following lemma.
Lemma 1. Let U, V, W be three random variables such that U and W are independent with each other, then
I(W U + ((W:VV
(47)
Proof. By Data Processing Inequality (Xu & Raginsky 2017). we have
IWW;U +V) < I(W;UVV) = /(W; /W; V U) = I(W:V (U)
(48)
Thus the proof is completed.
n
18

---

Published as a conference paper at ICLR 2023
Now are ready to give the proof of Theorem
Theorem 3. Let model fo(-) parameterized by 0 E θ R and is trained on S { y/s }
from distribution P. with the spurious altributes of a: is zi. If the learned model Jos (.) 1 S=
M2
Egen(Sos: P) S inf
(1(S0- Syi Sos Sg(r) ((Svi
(5)
4n
where Eoen P) = E Re (fes: P]] - Rpop (fs: P)), g(-) any measurable function, sw-)(=) = (xi g(2z) [==)))=>1> Sy {
Proof. Let S (ft ūt)) be another samples drawn from P independent of S. W.o.lg., assume Epx [f (z), v)] = O, otherwise we can replace L( (2:). y1) with L(Jos (m:), 9i) Epxses [C(Sos (2), v)]. For any À > 0 by Donsker-Varadhar 's inequality.
DEL (Psxto || Ps Ptog ) Esxies
Alfo (1i).
log B
exp
[(fos (2:).
(49)
Then for any 0, >>> 0, and Lebesgue measurable function g(-),
AE Remp (oo. P)] S DEL (Psxts || Ps x Pios + log Bsx0s
exp
[ (Z.))
n
X²M²
I(Sm, Syj fos)
8n
(50)
A²
-I(S:: SS₂) + (Syr fog)
8n
X²M2
[(Sa-ata); Sas
Sy Sp(t) I(S
8n
where a is due to the definition of mutual information, [(fe, (æ:), y1) is M sub Gaussian, b is from Lemma and the last equality due to the conditional independence of the model. Thus, we conclude that
M (((S=-ote)ife S + fox))
E [ PJ] < inf
(51)
4n
Thus, we complete the proof.
C.2 PROOFS IN SECTION
Let F(O) and ||- I|x., respectively be the parameterized function class and Loe-nor on F(O) defined as
llfo;
for sup fo, (x) foo foz(() (x))
(52)
for any fe.: fo. E F(O). To provide the proof of Theorem we need the following definition of covering number.
Definition 7. A 6-cover of metric space (c, F(O), || (1x,0) is any point set (J) C F(O) such that for any fo(.) E F(0), there exists 0: satisfies [lfe - fei 1 c. The covering number ((e), 11x.)) the cardinality of the smallest e-cover.
Theorem 4. Under Assumption 7 and ifinfacik,I.EEII..
O(), then
log log (1/8)
CSV(ff) S (S)) + +
(8)
vn
holds with probability at least 5 for any 0,5> 0.
*0s is the learned parameters depends training set S. fo l is random element that takes values in functional space (i.e., model space), details can be referred (Shiryacv) 2016..
19

---

Published as a conference paper at ICLR 2023
Proof. First, for any given 0 + and given Y 2 due to 0 < (() < M, by couua--oeffdiig'ss s inequality (Corollary 2.20 in (Wainwright, 2019)), we know that the with probability least 1 5
log (2/6)
log (2/0)
(xa(fo) My
S (xo(fo) S (xx( + M
(53)
2mbs
2nk=
Then we see
sup (Cez, (fo) Lkzz (fo)) S sup
[C (fo) LRss (fo)) (Crzz(fo) Lazz(fo))]
51.22
31.22
+ sup
(Cezs (So)
Exzz (So)
(54)
=1.22
S M log
K2ō
2
sup
2
2
sup (Lez, (fo) Luzz (Fo)
$1.22
#1.92
holds with probability at least 1-8. Since the function class F(O) bounded by M under || 11,,
has finite covering number N (c))( ll II...). Let fo, (.).. fox (.) E F(() be e-covering of
F(O) with S N (e,F(O), 11 such V/o F(O). By E (1,... . .N), Il -o,lll S e.
Thus combining the above inequality, for any So(.) and its corresponded fo,()) (-). we have
sup (Ckz, (fo) - Luzz (fo)) S sup [(CRz (fo) - Luz, (fo,)) + (Cuaz (fo,) - [fo2 21.22
21.22
+ sup (LNzi (fo,)) - (fo,)fo,))
$1.22
(55)
3 M log K28) + N (F(O),,,, [1mm))
2
sup 21.22
2
2n
+ sup (Cas)(fo) Exaz (fo,)) #1.82
holds with probability at least 1 - ô for any > O. Here the inequality a is due to the definition of -oom on F(O).
On the other hand, as
K2 sup (Lx., (fo) (fo)) P(Y k)) $1.32
CSV(fo) Σ
(56)
We estimate the P(Y k) with its empirical counterpart ny Gaussian variable (Y= we have
Σ K2 1 nkz/n. For bounded sub-
log (1/8) 2n
E [ [ Σ (,==)) = P(Y = k)) Px S
(57)
holds with probability at least - 5. Plugging this into (56) and combining
55
we get
Ky
log (2K,/8)
CSV(fo)
Σ
sup (Caza (fo) Lxzz me Ky $1.22
2n
Ky
log (2K,/5)
Σ
sup k=1 $1.52
(Ren (fo) - (nss(fo)) du - Ko
(58)
2n
+ inf { 2e M log K25
2 + N (F(O), (Lw 1
1
sup
Pa Then suppose
2nk
2m
21.22
holds with probability at least 1 - 8 due to the definition of Pi- infRe(KK),oC(k, Maz/mx 2 a, we have
Ky
Σ sup
1 2 + (V
V2nu
1=1 $1.02
2m
71 RE(
minee(K,))<(kk) Vakss
2
7
(59)
RE kE|Ky]
2K,
am
20

---

Published as a conference paper at ICLR 2023
where the last inequality is due to the Schwarz's inequality. Combining this with (58)
get
CS)(fe) (SV + o N (F(O), e, Il [l log (1/6)
(60)
vn
That completes our proof.
C.3 PROOFS IN SECTION
In this section we aim at proving that the 2 is a sharp estimator to the CSV when we know a lower
bound for Tkz- Note that problem is equivalent estimate supp, Ep, [V] inf p. Ep. [V] via samples {Vi) drawn from mixture distribution P = [ Th Pk with known > W.o.l.g.
suppose E [V] < [V][V] S, ...... S Epx [V], then we show Ep V Z qp - c)] Ep[V
V S [p(c)] is a upper bound to Ex [V] Ep, [V]
and the bound is sharp when K 2 3.
Proposition 3. For k == 1,... K and Ty. 2 c, suppose Ps are absolutely continuous w.r. Lebesgue
measure, then we have
Ep|V IV gp(1 c) EpIV V S (p(c)) 2 Epx - -BA and the equality can be taken taren.form some Ps and Tik (k = k) 33
(61)
Proof. Let pa(v) be the density function of Pk. Then p(-) Ex= T&Px(.) is the density function of P. One can verify that
p(()
qr (-qr(1-c)) (v (v-qr(1
((2aa((1-)) - px 20
(62)
for any v since (v) 2 0 and 0 < << TK. Thus taking integral w.r.t. v we get
Er[V V 2 qr(1 c)] - E [V] [V] /
(1- (u-9r(1- qr(1 -c])
p(())
(v2vp(1-e)) px(()) de 2 0. (63)
We can apply the similar argument to prove Er(V V gr (c)) [v). Combining the two inequalities implies (61)
On the other hand, if K 2 3, we take
TK Ci
1- 2c WK-1 K 2'2
(64)
and
(v()) p(u) 1 (eS9p(0)}
px (v) p(v)
1(120p(1-0)3
(65)
P2(v) -.... (V) = plv) Then it is easy to verify that
1- 2c (0)
Ey [V V 2 gr((1 - c)] [v(V V Er [V] - [v]
(66)
under this distribution.
According to this proposition, we can use the quintile conditional expectation to estimate the proposed CSV as we did in the main body of this paper.
D SOLVING THE PROPOSED MINIMAX PROBLEM
In this section, we provide the convergence of the proposed Algorithm to solve it in the regime of regularize training with CSV( i.e., F*(0) defined in Section m K? in this regime. Let us define
We illustrate
Then we have
4 (0) Remp (Se, P) À max u' T F² F=)(0) pku" T log (K?u) mEAR?
max mEA
00 u):
(67)
4 (0) Remp (So. P) +
max u F (0) - -pxu" log (K?u) max uEAK?
65 u).
uEAK?
We have the following lemma to state the some continuities.
21

---

Published as a conference paper at ICLR 2023
Lemma 2. Under Assumption
have the following conclusions
1. For o (,,00000 u) with any p and l we have
Vool (01. u)
VoD. (02, u)
$ S (11+2KK2)))00 02ll L1i10: 02ll:
Vool (0, u1) VoD (0, u2)
s 222,,Tool uell L12 (12l|11 w2ll:
(68)
Vuot Vu m)
S <22 - 02ll Tualurr u2ll-
2. Let p0. arg mrgmax k3 17, u) and ü (0, arg maggax (0, u)) then
(11100 - (0, s F(0) F(0)|
(69)
3. 40( is + (L11 + L)2/p) smoothness
Proof. Let us proof the conclusions by order. For the first conclusion, we have
Vod u) Vellemp (So, P) + (0) u;
Vn u) = (0) ad (log (Kzu) +e)
(70)
where e = (1, .... 1). Thus, by Schwarz's incquality, one can verify
Vodt u) (02 u) - V V VeHlepp P)l
=1/le J (V)) vor* -o
52
Σ
u(i)n(t) sup (=1
(V (fo.) (fo.) (laz)(oo.)) (v (foz) V V (
[E]KE]JE[K3]
T.] 021
$ (1 + 2AK. L.
11: - 01ll
(71)
and
(00 u.) Vo0i(0, uz) s Allus - uell [o
< 22XK, -22l
(72)
and
V Vu0i u) V (00) m) s (0() { F² (02)
22K, 0211
(73)
Thus we complete the proof to the first conclusion.
For the second conclusion, by the Lagrange's multiplier method or Theorem have the unique closed-form solution of uz p) E K2 that
(Yi al.
2021a we
exp ( 1r (O)()
F*
(0,
Softmax
Σ exp
( (())())())
p
(74)
exp (FF
F* F*
(0
Softmax
Ej= exp 1,F"(0)))
K?
P
On the other hand, due to u E AA? we have
va (0, -
-PAI,
(75)
uii
un( (?)
where A > B means that A - B is semi posiivve definite matrix and is the identity matrix. The similar conclusion holds for dy u)) Thus both (0, u) and 2²,0 u) p-strongly concave w.r.t.
22

---

Published as a conference paper at ICLR 2023
u. Then
(0, 2 (0 (0. + (0, u))
(0. a)(0.
pd
(0, (0.p) (0. p)1
2
(76)
(0, 11 (., p)) s 00 ui (0, p\) + (0, ()) 21(
1ux (0, p) u ( p)1
2
Plugging the two above inequalities, we have that ( ii p)), w p) 00 p) 2 p> (0, - ()
(77)
due to the (V (0, (0, .)). u p) 1 p)) < 0. On the other hand, as (0, (0, p)), ui ( p) -.: p) = 0.
(78)
Plugging this into the above inequality, we get på (0, (. 0)1 < Vu uz (. ui p)), ui(0. -
ui(0,p))
(F"(0) (0) (0)
(0, p) -)(0,p)) p))
(79)
$ A (0) FO) | p) u p)
Thus the conclusion is proofed. Finally, we prove the third conclusion. Similar to the proof of the second conclusion, we have
||uī (02. p)1l |0 - 0zll.
(80)
Since 2x² is convex, bounded, and u (0, p) unique for any 0, by Danskin's Theorem (Bernhard & Rapaport 1995,, we have
(0,) (0))
< VeRemp P) - Mellem
VoF* (0,) ui (0..p) VoF* (02) ui p)
< L1 |0: - 021 + > VoF (0:) (u (01,p) ui (22.
u (02. p) T (VoF" vor*
(81)
< Li 110 - 0.1 + Al7a 100 - -02 + Ahn1 10: 021
Ln + ALia + Nh11
|10 021l
which implies our conclusion.
We present the following lemma state the descent property of the obtained iterates via Algorithm
Let us define
3h (0, u) Remp P) + Xu" pk
(82)
As we have assume that unbiased estimators Remp (so, P) and (²) have bounded variance, then according to
E -
< 2E
(Remp (fe, - Remp P))
(83)
2x² E
8 (0) (0) =0(
w.o.l.g. we assume that
L (3-(0)
| -001 so?
max
(84)
23

---

Published as a conference paper at ICLR 2023
Lemma 3. Let L1 A (L11 122/p) L, we have the estimation such that Elo" (0. u)]
6 u). Bi(0" u) @* (0, (0 S o² then
K
Ky
E
D x (1( (((L+
Σ h=1
pa (0(0))
70 Lije
I
Σ
de v v
2
Ky
LK, Li
(o* + L11) Li230
r² (0 - =r:l (85)
D
P
2p²
Lngo²
Proof. Due to the L-smoothness of (-)()) for any & and p we have
Ky
Kg
Ky
+ i 11[
Pu
(t + 1))
tu Φ (0(t)) +
Pa V (0(t)),
O( 0(t))
Ky
K₂
K
pu (0())) n7
Σ
Pa V
Pa 000 Σ
L.g
+
Σ Pa v Ved Veot (0(1) (i
2
<
tu (0(1)) ni Σ Da vo
k=1
Ky
+ 70
Σ
Pa V (O(1))
Σ m0 (vo)(0())
000
7/
Pk FO
Σ
Pk
Lmjo
+
Pa (00),
(86)
On the other hand, using the fact that E and Young's inequality
@5 u))
()) E
(3)(0, ) so²
E
de V
(0(t). (t)
Ky Vo (0(t), (x (oo)) (()) + E Eoo
E
Σ de
1
(87)
2
Σ tu Voc (0(t), (0()) mz(())
1=1
Ky
Ky
< 22-2 2E
Σ
Da v2*(((())
2B
Σ
(vo)(0(1)) Voo ux) ux
k=1
24

---

Published as a conference paper at ICLR 2023
Due to Danskin's theorem and (i), (ii) in Lemma 2 we have
Ky
Kg
E
Pk (VO)(0())
(o0)) ux))
S EE
Σ
pr L12 (0(1) p) ma(1)ll
Kg
E
P2L12
Fr (²(t)) -Fill
(88)
p
Kg
K Li
F*) [|]
Finally, we have
K2 (O)))
Pe V
(00))((1),u)0000)))) -000)(0(1) Pk
(O()()))) (Voot (V00)(000,, x Voo)(0(1) mxx()))
P&
k=1
Ky
K2
E
Pu V V (0(t))
P
(00))(t)),,(((()).))) voo, 200)))
2 k=
Ky
Ky
$ 2
R
Σ P& (
Σ PA
V F* (0(t))
1
Ky
(0² + I.1)
Tia
Ky
(e(()) - ++11"]
Σ
da - (0(1)
P.B
2
2p²
(89)
Plugging the three above inequalities into we get
86 and taking expectation to the both sides of the equality,
Ky
Ky
Ky
E
Pa t
(0(1
1))
$ E
Σ p
q (0(1))
(0o ind)
E
Σ de
v
4
((())
(90)
Thapeno
(0²
Ln)) Li2710
| |=(()()))
in
D.B
2p²
2
This completes the proof of our theorem.
F² (O(t)) F 1"]
Then we proceed to the next lemma to characterize the dynamic of E
- - F+ ["] and
Lemma For the Fh defined in Algorithm and let 8+(1)
5(t) E K2 1 Pk (t), by choosing 7 2/3, we have
Ano Ii K yp2
2nj0 T
8(t+1) < 1
8(t) + 22 +
o²
(91)
And Li
E
Pu v * (0(t))
Proof. W.o.lgg. we fix the & during our proof. According to E * (0(1)] = F*(((()) and
F* (0()) - F*t (((0)))
s 0² we have
|| - -
B
(92)
25

---

Published as a conference paper at ICLR 2023
where we use the fact y 1. Then due to the update rule of F Young's inequality and the above inequality,
F F² + F² (0(L) - F² (0(1 1//l"
8" + =E
$ + 2 2-27 24 B 1| (((())) + (1+ 2 2- 27
--)
(*((((++)) F² [((()))]]]] (93)
B
< (1 2) (t) + E = - F* (0(1))])
On the other hand, due to the 11 continnit of F* (-) and (87). (88)
we see
B || 1)) - ('(0)))]]]
LiE || + 1) [
K2
Li
Σ
pu Ved (0(), (t)
(94)
Kg
S n 0i + -2na
Σ
po - ((())) (((t)
2n Li K,
Ky
p2o0(() (1).
/²
k=
Plugging this into the above inequality and weighted summing over k (by pa)) we get
Σ P (e+ 11+ s
[ - --
4n Kn
Kx
(1)
22²²+ 2nd o²
7p2
(95)
K2
4n Ano
Σ
Da V x (0(1))
which completes the our proof.
Now we are ready to state the convergence rate of the nonconvex-coneet optimization problem. Theorem Under Assumption and if Remp fo, P) and F² (0) are all unbiased estimators with
bounded variance, (t) updated by Algorithm with rie O T 3 and 7 T 3 then
K2
min ISSS
E
Σ
de ve
I 0 50(1+5 t)
(14)
Besides that, for any Ott) and p. we have
EKKi de ( (0(t)) 4² (0(t))) < Xp(1/me log m).
Proof. First, note that m K2, for any O,
Xp
x0) < M ApK, inl (a log (K?a)) = M +
(96)
K.e
Due to the value of no S
we have that
2 2K,
AngLi K2L
7
51-3
(97)
2
7p2
3
Thus we have
8(t) < (1- -)
4M22 +
22 +
2n 2n0 TR
Σ
(1- 3)
(98)
1-1 Ang
| 7) -ーコー
K
Σ
E
Σ
pu v (0())
7
1=
26

---

Published as a conference paper at ICLR 2023
from Lemma 4
Plugging this into 855
in Lemma 3 and summing up it over 0,... T, we have
T-1
K2
E
Pa (((T))
E
Σ pu
(0(0))
Line
Σ E
Σ
Pe
V
(0
h-1
1=0
+
1M²
LKGLi2n
(o² L11)
Li2n00
T-1
Σ
11
))
3
P
2p
t=
(99)
T'na
[K
(o² L11) Li200
27LLi1
T-11-1
(1- 3) 0²
+
12
Σ
P
2Ø²
t=0 ==
4n Lii
(o² + T111) 132
T-1T-1-t
Σ
Σ
2
E
Σ Ph -ロ
(0()))
P
2p²
3
t=
==
can be verified that for any 1, E/ (1-333) < get
3/7, and plugging this into the above inequality
K
Kx
T-1
Ky
Pa t
(O(())
S
Σ Du ((00)
7o
Σ
Σ
pe
3
1=0
(100)
12 M² 2
Ma
Time
2n² + 2102111
37
+
+
Mr
0²,
2
where M, LK,42a + (o²+L1))43 and use the fact ne s min
Finally
P
2p
12L 12 M,L
from (66 and y = T 3, 170 s
T
we get that
M B
Σ
Ky
Da v
I
3
M k.O)
36M
noT
K.e) 72
181gLn1
187
7/2
3iT-bo to²
- 8 8
M+
P.
+ 36M
M,
+ 187 181 M,,0 + 18T-&Ln1Me
Kze
o (T)
(101)
This completes our proof to the first conclusion. We highlight that the value of m/ satisfies
T
=o (
7/0
12L
T
2 bonKknn
(102)
12 M,Ln
To see the last conclusion, similar to (66 we have that
(0) -0((0)()-- = >xF (u) - u0, p)) - pp) log (Kl
Ap
(103)
- x (0) (0) (0)) +
K,e
where (0) arg mix(i:: $ (0)( Due to Theorem 1 in Epasto et al. 2020), we have
F* F*) (ui wi(0, p)) & 2p log K..
(104)
Thus we can conclude
(00(0) (0) s Ap ( 1 2log K₂
(105)
K.e
which implies conclusion.
27

---

Published as a conference paper at ICLR 2023
Table 4: Test accuracy (%) of linear model on the OOD test data of Toy example. The OOD test data are drawn from distributions with different d7z. The results are the mean of five independent runs.
Method / YYz
0.00
-0.20
-0.40
-0.60
-0.80
-0.99
ERM
88.5
83.0
68.0
53.5
33.5
27.2
IRM
96.0
90.5
91.0
90.5
91.0
90.5
GroupDRO
96.5
94.5
93.0
91.0
90.5
88.0
Correlation
92.5
87.5
79.0
69.0
43.0
39.5
RCSV
99.5
99.0
98.5
97.5
98.0
97.0
RCSVU
98.5
97.0
96.0
95.0
94.5
89.5
Table 5: Cosine-similarity (02, (22) (1122](11)ll)))) of linear models trained on different methods.
Model with smaller cosine-similarity theoretically exhibits better OOD generalization ability.
Methods
ERM
IRM
GroupDRO
Correlation
RCSV
RCSVU
(..p.)
0.95
0.13
0.18
0.89
0.03
0.05
0. 0
E MORE EXPERIMENTS
In this section, we conduct more experiments on synthetic dataset and real-world dataset to further verify the effectiveness of our proposed methods.
E.I Toy EXAMPLE
In this section, we apply the proposed RCSV and RCSV constructed toy example with spurious correlation.
Data. The data is constructed the example in Appendix B For 5-dimensional vectors
Pi M2, the training data X follows normal distribution (((Y f Zuz J J10) where I10 is a 10 10 identity matrix. The label Y and spurious attributes Z take value from { 1, and Pv -1 = 0.5). As in (T). the spurious correlation coefficient oyz between Y and Z vary 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 o in (0.00, - -.20 -0.44 00.40, - -0.60, - -0.80, -0.99}. As can be seen, the spurious correlations in the test sets are opposite the one in the training set. Thus, over-fitting the spurious correlation will mislead the trained model.
all drawn from a standard binomial distribution (i.e.. Py-(Y = =) 1)-
Setup. We use the linear model fo(x: 00 and its prediction Y is sign(fo(x))) We compare the proposed methods RCSV and RCSVc with the baseline methods as in the main body of this paper. The domain generalization methods can be applied with observed spurious attributes 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 -(.-) is cross entropy. The hyperparameters 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. Table 4 we report the test accuracies of trained models evaluated on OOD data to if all the aforementioned methods can break the spurious correlation. From the results, we have the following observations.
For all methods, the test accuracies consistently improved with the decrease of the gap between train o This is explained as the decreased ofiing test 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 GroupDRO) can break the spurious correlation (generalize OOD test data), which verifies the
28

---

Published as a conference paper at ICLR 2023
0
0
D 1
0
O
O
0
O
2
D /
0
O
O
A
D
0
0
0
1
/
/
1
\
/
2
2
2
2 3 4
2 2
2
2
2
2
2
2
2.
2
3
3
3 4
3
3
3
3
3 4
3
3
3
3
4
4
4
4
4
4
4
4 4
4
4
L1
4
4 7
4
41
4
5
5
S
5
5 6
5
5
5 5
5
5
5
5
5
5
5
5
5
5
S
6
6
6
6
6
6
6
6
6 6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7 6
7 8 9
7
7
7
7
7
7
7 8
7
7
7 7
7
7
7
8
8
8
8
8
8
8
8
8
8
8
8
6
8
6
8
2
9
9
9
9
(a) C-MNIST SF
(b) C-MNIST-P2
(c) C-MNIST-R
Figure 2: Images of three C-MNIST datasets with different spurious correlations. The first two have fixed spurious correlation between colors and the label of digits, while the spurious correlation the last one is random.
Table 6: Test accuracy (%) convolution neural networks trained on the different mixtures of C- --MIIST-F1 and C-MNIST R. The OOD test data either C C-MNIST-ER C C-MNIST-F2.
Test set
C--NIST--
C- MMNIST-FP
Method/a
0.80
0.85
0,90
0.95
0.99
0.80
0.85
0.90
0.95
0.99
ERM
96.1
95.4
93.3
87.5
63.8
95.6
95.2
92.8
82.6
52.8
IRM
91.2
90.5
90.4
87.9
76.6
94.3
93.5
91.1
87.2
63.1
GroupDRO
96.6
95.9
93.7
92.1
76.8
95.5
95.3
94.3
91.5
70.2
Correlation
82.6
79.6
79.5
72.6
38.5
82.6
78.4
68.2
35.6
25.2
RCSV
98.0
97.6
96.7
94.3
81.3
96.9
96.3
95.1
90.2
81.3
RCSVU
97.9
97.5
96.5
94.1
77.9
96.8
95.6
93.6
86.9
62.3
effectiveness of our methods. On the other hand, both RCSV and RCSV beats the domain gener- alization methods which require the domain label (i.e., the spurious attributes Z in the constructed dataset). Thus, the extra information required by RCSV (resp. RCSVu) is equivalent (resp. less) compared with domain generalization methods.
On the other hand, let the last 5-dimensional parameters of the linear model be 02. By X ~ ((((HT ] I1)), one can verify that the when 0₂ M4 = O, the output of model X does related to with high probability. Then the model can break the spurious correlation.
To see this, in Table 5] we present the cosine-similarity (02, p2)) ([10)) (211) (the cosine-similarity used to alleviate the interference caused by scales of the two vectors) of the models trained by methods in Table The results show that the models trained by OOD generalizable methods have smaller cosine-similaritic
E.2 COLORED-MNIE
In this section, empirically verify the effectiveness of the proposed methods constructed real-world dataset Colored-MNIS.
Data. Our dataset 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., O to 9. We construct our Colored-MNTST (C-MNIS) ST) by inducing the spurious correlation in the training and test sets. Concretely, for each digit, 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 spurious attributes, i.e., the colors of foreground and background of 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 specific colors respectively for its foreground
29

---

Published as a conference paper at ICLR 2023
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. C-MNIST-R).
Some of the generated datasets are in Figure As can be seen, the three versions of C-MNIS" has different spurious correlations between the label of digits and the colors of foreground and background. Besides that, the spurious correlation in -MMIS-FFF and C-MNIST- F22 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 a E {0.8, 0.85, 0.90, 0.95, 0.99), then for each a, we construct a training set with [60, 000 aJ ] samples constructed as C-MNIST-R, We use two test sets which are respectively the 10,000 test samples constructed 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- C-MNIST-FV due the spurious correlation between color and digit in it, and the existence of these data meets the Assumption
from C-MNIST-F1 while the other [60, 000 x (1 a)]
Our model is 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-FL and C-MNIST-R. Thus the domain generalization based methods IRM and GroupDRO can be applied here. The used loss function [(.,)) is cross-entropy, and detailed hyperparameters are presented in Appendix G.4
Main Results. To see the models trained by these methods can break the induced misleading spurious correlation, report their test accuracies the C-MNI ST-R and C-MNTST-F2. The results are summarized in Table with the following observations from it.
The test accuracies of all these methods increase with the decreased a. This is a natural result since smaller a corresponds with more training samples from C C-MNIST-R which alleviates the misleading signal from the data with spurious correlation in C-MN1ST-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 G our RCSV (resp. RCSV 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 large a. 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 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 MINIST-F2. This is due to there exist data drawn from C-MNIST-R in the training set, while the data from C-MNIST-F does not appear in the training set.
F ABLATION STUDY
We have discussed in Section that the reweighed sampling trick improves the OOD generalization. Thus, we explore the effect of such trick in this section.
We follow the settings main part of this paper, expected for the reweighted sampling strategy is set as uniformly sampling, thus the methods ERMRSyz and ERMRS become the ERM. The results are summarized in Tables 7 and
[IJ] is the floor of numher
30

---

Published as a conference paper at ICLR 2023
Table 7: Test accuracy (%) ResNet50 on each group of Celebà and Waterbirds. The
experiments are conducted without reweighted sampling trick.
Dataset
Method / Group
D-F
D-M
B-F
B-M
Avg
Total
Worst
SA
RCSV
91.1
91.0
92.9
92.2
91.8
91.3
91.0
IRM
90.1
92.3
90.1
86.1
89.7
91.0
86.1
GroupDRO
90.3
93.0
94.3
87.2
91.2
91.8
87.2
CelebA
RCSVu
94.0
98.6
91.1
60.0
85.9
95.1
60.0
Correlation
94.1
99.3
82.1
35.7
77.8
94.0
35.7
X
ERM
95.4
99.5
82.8
41.8
79.9
94.8
41.8
Dataset
Method / Group
L-L
L-W
W-L
W-W
Avg
Total
Worst
SA
RCSV
97.1
86.0
86.4
93.3
90.7
91.2
86.0
IRM
98.6
90.6
79.4
90.8
89.9
92.5
79.4
GroupDRO
98.4
94.4
71.5
85.4
89.9
92.4
71.5
Waterbirds
RCSVu
99.0
81.1
77.3
93.6
87.8
89.0
77.3
Correlation
99.9
88.5
59.0
90.3
84.4
89.9
59.0
X
ERM
99.6
88.5
58.1
92.5
84.7
90.6
58.1
Table Test accuracy (%) of BERT on each group of MultiNLI. The experiments are conducted without reweighted sampling trick.
Dataset
Method Group
C-WN
E-WN
E-N
N-WN
N-N
Avg
Total
Worst
RCSV
79.8
94.4
83.8
76.5
79.2
70.6
80.7
81.6
70.6
IRM
79.2
94.2
83.9
74.2
79.1
67.6
79.7
81.4
67.6
GroupDRO
80.4
94
82.4
76.2
80.8
70.3
80.7
81.8
70,3
V
MultiNLI
RCSV
80.1
94.2
83.6
80.1
78.2
67.4
80.6
81.3
67.4
X
Correlation
73.1
91.2
76.3
64.5
77.9
62.4
74.2
77.8
62.4
X
ERM
80.4
94.8
83.6
81.4
78.6
66.6
80.9
81.5
66.6
X
Table 9: Test accuracy (%) of BERT on each group of CivilCommente conducted without reweighted sampling trick.
The experiments are
Dateset
Method / Group
N-N
N-1
T-N
T-1
Avg
Total
Worst
SA
RCSV
93.1
91.8
72.4
70.6
82.0
90.2
70,6
IRM
93.0
86.3
74.9
67.8
80.5
88.1
67.8
GroupDRO
92.9
88.3
65.1
V
Ci civilComments
RCSV
97.4
94.3
69.0
62.9
80.9
92.7
62.9
X
Correlation
97.1
92.3
66.5
61.7
79.4
91.6
61.7
X
ERM
96.6
92.1
69.4
56.3
78.6
91.1
56.3
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 Wat caterble rds, see the column "Avg" and "Worst" each table. We speculate this 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 Waterba rds.
The other observation that even without this trick, our methods improve the OOD generalization compared with other baseline methods due their better mean and worst test accuracies.
Finally, the trade-off between the robustness over spurious attributes and in-distribution test accuracies 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, Mul 1 i NI.T, and Civi 1 Comment.s.
31

---

Published as a conference paper at ICLR 2023
G SETUP FOR EXPERIMENTS
G.1 IMPLEMENTATION TWO PROPOSED ALGORITIMSS
In this section, present the detailed algorithm flows of the proposed RCSV and RCSV, u in the main body of this paper. The critical part is their estimators to the F*)0) defined in Section
Algorithm 2 Regularize training with CSV (RCSV).
Input: Training samples {< H- number of labels Ky and spurious attributes Kg, batch size S, learning rate 'e.. training iterations T, model fe(-) parameterized by 0. Initialized to. (F Positive regularization constant A, surrogate constant p. and correction constant 7.
1: for = -, 0,..., do
2: Compute the estimator Remp(foc:) (o(e).)))))) P);
3: (emp(fo(t) P) is the empirical risk over uniformly-drawn batch (size S) of data.
4: Compute the estimator F* (0(t)), [Ky]:
5: Initialized K2 Kz-dimensional vector _* 0, k [Ky];
6: Reweighted sample mini- of data {2 Ht,ir (. with replacement, the probability
of data satisfies Yr., and Zt,; = = (K,KKnnz,
7: Update (z) as the empirical risk over { ( st,:)) 0 Ake. [Kyl E [K&]
8: Compute F² (0(t)) K, (1) - (1), - (K.)). k E [Ky]
((K,)-((((k)))
9:
Solve the maximization problem.
F 2+1 (1 - F + (0(1)):
10:
11:
un (t+++1) = (o
12:
Update model parameters O(t) via SGD.
Kg
13:
O(t + 1) 0(1) - ne Σ
Ps (Re P) + lu +1) 1)T F F
end for
Algorithm 3 Regularize training with CSV (RCSVv).
Input: Training samples {x;; y:) number of labels Ky and spurious attributes Kg, batch size S, learning rate 'e, training iterations T, model fe(-) parameterized by 0. Initialized 0g (F.). Positive regularization constant X, surrogate constant p. and correction constant 7.
1: for (= 0, ...., T do
2: Compute the estimator Remp(fe(e) P);
3: Remp(Jou) P) is the empirical risk over uniformly-drawn batch (size S) of data.
4: Compute the estimator F² (O(t)), 1,... Ky;
Initialized A -dimensioonl vector F* (O(t)) = 0, =E [Ky]: 6: Reweighted sample mini-batch of data {(xe, vt,s)} with replacement, the probability of data satisfies ye,; = 1e 1/(
5:
7: Update F' (j) with C(fe (zr, vr.)) a) if (Zr, Vr.i) is the j-th data in Ap. i E [Kyl,j E [Kz].
8: Solve the maximization problem.
9:
Fk t+
7) Ft + (0(t));
un (1 1) SofttmaxFFt11/)
11: Update model parameters Ol)) via SGD.
( 1) 0())
me Σ pr. V Remp (fore) P) + Aug(t 1)" F F.t)).
13: end for
32

---

Published as a conference paper at ICLR 2023
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., (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 be generalized on is B-M, due to its extremely small proportion in males in the training set.
(D-F), "Dark-Male" (D-M), "Blond-Female (B-F), "Blond-Male
Waterbirds. This is a synthetic real-world dataset in (Sagawa et al. 2019) with 4795 training samples and 6993 test samples, which is constructed based combining photograph of bird from the Caltech-UCSD Birds-200-200
(CUB) dataset (Wah et al.) 2011) with image backgrounds from the Places [Zoou al. 2017). 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 categorized into 4 groups, i.e., "Landbird- Land background" (L- L). "Landbird- Water background" (L-W), "Waterbird- Water background" (W-W), "Waterbird-Lane Land background" (W-L). The training and test datasets are constructed with the numbers of samples in each group are respectively (3498, )255) (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. the training set, most landbirds are the land, and most waterbirds waterbirds and landbirds are uniformly assigned on the two backgrounds. Thus, we are desired to train 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.
on the water. But in the test set,
MultiNLI. This is a dataset for natural language inference (Williams et al. 2018) with 20617; 75 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 the contradiction can be related 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-Withod Negation" (C-WN), "ContradictionNeeatiii (E-N), "Neutrality-Wine (N-N). Our goal learning a model that makes prediction
(C-N), "Entailment-We Without Negation" (F-WN), CentailmeentNegattoon Negation" (N-WN), independent with the presence of negation. The numbers of samples in training and test dataset from the 6 groups are respectively (57498, 34597). ( (11158, 6655), (67376, 40496), [1521, 886}. {66630, 39930}, ( (1992, 1146).
Neeutrality-Negatiin
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 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),
CivilComents.
(T-N), "Toxic-Identiry (T-I). The numbers of samples in training and test dataset from the groups are respectively ( (14818) 86, 72373). (90337, 46185), (12731, 6063). {17784, 9161}. As can be seen, there exists spurious correlation between the toxicity and the identity attribute in the training set due to the number of data in each group.
For all these datasets, from the number of data in each group, there exists dominated spuri- ous correlation in CelebA and Waterbirds. But this does not happened in MultiNLI and CivilComments s, especially for MultiNLI as the strong spurious correlation only exists in the group of "C-WN"" v.s. "C-N". Thus for the Mult iNLI and divilConment: s, expected for the spurious feature, the model should extract other features to guarantee good performance.
33

---

Published as a conference paper at ICLR 2023
G.3 BENCHMARK ALGORITTMS
Empirical Risk minimization (ERM, Vapnik, 1999) pools together the data from all the domains and then minimizes the empirical loss train the model.
Empirical Risk minimization with reweighted sampling (ERMRS, [drissi et al. 2021 is similar to empirical risk minimization, but reweight the sampling probability each sample, and the weightes on each data is pre-defined.
Invariant Risk Minimization (IRM, Arjovsky et 2019) learns feature representation such that the optimal classifiers on top of the representation is the same across the domains.
Group Distributionally Robust Optimization (GroupDRO, Sagawa et al. 2019) minimizes the worst- case loss over different domains.
(Correlation, Devansh Arpit 2019) minimizes the intra-variance of data from the same category to break the spurious correlation.
G.4 TRAINING DETAILS
As clarified in Section the backbone models for image datasets (CelebA, Waterbirds and textual datasets (Mult iNLI, Civi 1Comment s) are respectively ResNet-50 (He et al. (2016) pre- trained on ImageNet (Deng et al, 2009) and pre-trained BERT Base model(Devlin et al. 2019).
The loss function -(:-)) is cross-entropy for all of these methods. The experiments 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 & Hutter 2018).
The hyperparameters of baseline methods follow the original one in Gulrajani & Lopez-Par 2020 (Saaaaa et al.] 2019 Devansh Arpit (2019] (Arjovsyy al. 2019 Idrissi al. [022). The hyperparameters of the proposed RCSV and RCSVu on CelebA, Waterbirds, Mu NI I.
Civi 1Comments. s, Toy example and C-MNIST respectively summarized in Table T0
13
14
and
15
Table 10: Hyperparameters on CelebA.
Table 11: Hyperparameters on Waterbirds.
Algorithm
RCSV
RCSVu
Algorithm
RCSV
RCSVU
Optimizer
Adam
Adam
Optimizer
Adam
Adam
Learning Rate
1e-5
le-5
Learning Rate
le-5
le-5
Batch Size
256
256
Batch Size
64
64
Weight Decay
le-4
le-4
Weight Decay
le-4
le-4
Epoch
50
50
Epoch
300
300
X
5
1
X
0.1
0.1
Y 0.9
0.9
0.9
0.9
P
1e-4
le-4
le-4
le-4
Table 12: Hyperparameters MultiNLI.
Table DivilConmentss
13:
Hyperparameters
on
Algorithm
RCSV
RCSV
Algorithm
RCSV
RCSV
Optimizer
AdamW
AdamW
Optimizer
Adam
Adam
Learning Rate
le-5
le-5
Learning Rate
le-5
le-5
Batch Size
32
32
Batch Size
16
Weight Decay
0
0
Weight Decay
0
0
Epoch
3
3
Epoch
3
3
Drop Out
0.1
0.1
Drop Out
0.1
0.1
X
0.1
0.1
0.1
0.1
0.9
0.9
le-4
le-4
?
0.9
0.9
le-4
le-4
34

---

Published as a conference paper at ICLR 2023
Table 14: Hyperparameters on Toy example.
Table 15: Hyperparameters on C-MNIST.
Algorithm
RCSV
RCSV
Algorithm
RCSV
RCSV
Optimizer
SGD
SGD
Optimizer
Adam
Adam
Learning Rate
0.01
0.01
Learning Rate
0.001
0,001
Momentum
0.9
0.9
Momentum
/
/
Batch Size
32
32
Batch Size
128
128
Weight Decay
Weight Decay
le-4
le-4
Epoch
100
100
Epoch
40
40
1.0
1.0
0.05
7
0.9
0,9
0.9
0.9
P
0.01
0.01
0.01
0.01
35


Reviews:
[{"review_id": "srAHHz9ZIm", "reviewer": "Reviewer_M8jr", "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": "This work studies the problem of learning with spurious correlations whose correlation with labels can change between the training and test distributions. They propose to regularize the algorithm with a new regularizer called Conditional Spurious Variation (CSV) which essentially measures the difference in loss values over different groups. They show that the Out of distribution (OOD) error can be upper bounded by the in distribution error + CSV term. They also show improved performance on many benchmark datasets. \n", "summary_of_the_review": "\nThe paper is missing important comparisons and citations. The empirical performance is also incremental.\n\n****************\n\nI have read the authors' response and they have sufficiently addressed all my concerns regarding comparisons with prior work and empirical contributions. I have also changed my recommendation accordingly. ", "strength_and_weaknesses": "The paper studies an important problem which has gained widespread interest in recent years. I have a few concerns which I mention below.\n\nThe invariance assumption of the model being conditionally independent of the spurious attribute given the label, how is it different from Conditional domain adaptation [1] which matches the feature distribution given the labels and the domain. It seems like the same assumption is used here. \n\nThis work lacks important citations and comparisons. They state that they can even estimate their CSV without ground truth group values but there already exists approaches which work without the ground truth labels [2,3,4] but many of these works have either not been cited or compared with . It would be good to have these comparisons included and also say what is different about their approach.\n\nThe empirical results are marginal. This algorithm improves the accuracy by a small amount on worst groups but reduces the average weighted performance on all the datasets. Hence, it is not clear if they are actually getting rid of the spurious feature or just trading some of the majority group accuracy with the minority group. \n\nIt is also not clear how different this approach is from the group distributionally robust approaches which also try to reduce the gap between losses across different groups. \n\nI am also wondering whether the authors needed to regularize their models as well to make this method work because the authors in [5] claim that if there is no regularization, these overparameterized methods fit well on all the groups in the training set and hence, there is no effect of distributionally robust optimization.\n\n[1] Conditional Adversarial Domain Adaptation\n[2] No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems\n[3] Just Train Twice: Improving Group Robustness without Training Group Information\n[4] Environment Inference for Invariant Learning\n[5] DISTRIBUTIONALLY ROBUST NEURAL NETWORKS FOR GROUP SHIFTS: ON THE IMPORTANCE OF REGULARIZATION FOR WORST-CASE GENERALIZATION", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kR04pF_-weK", "reviewer": "Reviewer_bzT6", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The authors propose an approach to training models that are robust to correlation shifts, where the correlation between a label and a spurious attribute changes between training and test distributions, but the generative model given label and spurious attribute and the label distribution does not change. The authors argue that under such correlation shifts, constraining the predictor to be conditionally independent of the spurious attribute given the class label yields a risk invariant predictor. They propose a regularizers that upper-bound the risk difference between distributions. They argue that independence constraints yield a favorable generalization gap. They show that such an objective can be optimized at a favorable rate.", "summary_of_the_review": "Post-Rebuttal: The authors addressed my concerns sufficiently. See comments above in \"strengths and weaknesses\".\n\n===============\n\nI think the paper needs a major rewrite in light of prior work. Many of the technical results constitute a nice contribution, but the paper would need to be reframed to highlight them.", "strength_and_weaknesses": "Post-Rebuttal:\n\nI am raising my score to accept, but with some additional suggestions for the authors.\n\n + The authors did a better job of connecting their problem formulation to previous work in the revisions. I would encourage the authors to also note that the content of the analysis in Makar et al 2021 is very similar to the analytical approach of this paper, including the way that the OOD generalization bound is constructed. I do think that the approach in this paper greatly streamlines those arguments, and relaxes some assumptions.\n - The proof of Theorem 1 still seems unnecessarily complicated, especially given my comment before that (39) is vacuous since the LHS and RHS are symbolically equivalent. Note that if you show $P(f(X), Y) = Q(f(X), Y)$, this implies that $P(Y | f(X)) = Q(Y | f(X))$, so the first half of the proof is unnecessary given the second half.\n - Given the presentation in the rest of the paper, Theorem 3 is still extremely difficult to motivate and parse parse. It is not clear what \"conditional independence does not contradict in-distribution generalization\" means; is the goal to show that the generalization bound goes to zero as n goes to infinity? Something else? It is also not clear what, say $f_\\theta \\perp S_Z \\mid S_Y$ means, given that $f_\\theta$ is trained using $S_Z$. The framework for producing this generalization bound is also not introduced at all. Some framing would be useful here, as simply giving references is not sufficient. However, this theorem does not seem to be particularly crucial to the overall story of the paper. Since I would find the rest of the paper to be rather strong even if this section were deleted, I won't lower my score because of this, but if the authors want to continue to include this result, I would suggest heavy edits.\n\n==========\n\n\nStrengths:\n + The paper does address an important spurious correlation problem.\n + Some of the risk invariance arguments (once fixed up) could yield more streamlined versions of the arguments made in Makar et al 2021.\n + The CSV penalty seems potentially easier to implement (and has no tuning parameters) compared to the MMD penalties proposed in previous work, although the parallel mini-batching strategy with differing weights could potentially be difficult to implement in standard workflows.\n + Empirical performance on standard benchmarks is compelling.\n + The CSV_U regularizer when no spurious variables are visible is a major contribution.\n\nWeaknesses:\n - The paper's development is extremely similar to [Makar et al 2021, AISTATS](https://proceedings.mlr.press/v151/makar22a.html), which is not cited. There is also additional concurrent work building on Makar et al that makes a more explicit connection to conditional independence regularization [Makar and D'Amour 2022](https://arxiv.org/abs/2209.09423). It would be absolutely necessary to contrast against Makar et al 2021, and show how developments in the current paper go beyond what was shown in Makar et al. For example, the correlation shift is identical, as is the goal to find a predictor with invariant risk, and there is also a similar argument about the generalization gap. There are some aspects of this paper that are new, e.g., the setting is slightly more general in that the risk invariance result does not require the existence of a sufficient statistic, and the CSV penalty here differs from the weighted MMD penalty suggested in Makar et al 2021. **IMO, the paper needs some major reframing in light of these similarities.**\n - Similarly, there needs to be more discussion of the relationship between the CSV penalty and the conditional MMD penalty given here and the conditional MMD penalty suggested in Veitch et al 2021 (cited in the paper).\n - The proof of Theorem 1 does not really make sense. For example, equation (39) is vacuous as written (the final expression is symbolically equivalent to the LHS). There is an obvious way to improve this. You want to show $P(f(X), Y) = Q(f(X), Y)$ under the given assumptions. This follows from $Q(f(X), Y) = P(Y) \\int_{\\mathcal Z} P(f(X) \\mid Y, Z=z) dQ(z | Y) = P(Y)P(f(X) \\mid Y) \\int_{\\mathcal Z} dQ(z | Y)$, where the first equality follows from the correlation shift assumption, and the second equality follows from the $f(X) \\perp Z \\mid Y$ assumption.\n - Lemma 1 is incorrect. Consider the counter-example: $U = W$, $V = -W$. Then $I(W; U+V) = I(W;0) = 0$ but $I(W; U) = H(W) \\geq 0$ (and $I(W; V | U) = 0$). The change of variables from U+V to (U,V) is done incorrectly in the proof; the domain of integration would need to change.\n - I have difficulty parsing Theorem 3. It is not clear what the mutual information term involving $\\theta$ means. The proof references a distribution over $\\theta$, which does not make sense to me. Similarly, Theorem 3 relies on the incorrect Lemma 1. Also, $M$ is not defined.\n - The prose around Theorem 3 seems to argue that there is no tradeoff between robustness and in-distribution prediction performance, which is not the case in general. In fact, at best, the theorem would indicate that the generalization **gap** between the empirical risk and population risk is small, but says nothing about whether the minimized population risk subject to the conditional independence constraint is small (which is what I might interpret as \"generalization capability\"). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "h51dEEIBb3j", "reviewer": "Reviewer_fPjQ", "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": "The paper considers the case of learning under presence of spurious attributes, which are correlate with labels, and make the train and test distributions different. It begins with a criteria, (3), for measuring independence of prediction function and the spurious attributes. Then replaces with an upper bound as the identity of such spurious will not be known (10). Simulations show improvement wrt. existing OOD baselines.", "summary_of_the_review": "In view of the issues desribed above like over-restirctedness of (10) and missing comparisons with feature selection based methods, I tend to recommend a reject. \n]\n\n____\nAfter the rebuttal and discussion, my issues are resolved.", "strength_and_weaknesses": "Strength:\n1. Overall, the paper is well-written with nice organization.\n\nWeakness:\n1. though the motivation, various justifications make sense, I feel the final proposal i..e, (10) is over-restrictive. For e.g., why not perform sparse feature selection etc. to eliminate the spurious features. For resultant predictions, clearly (10) is restrictive, while they will alleviate the issue of spurious correlations?\n2. Even in simulations I think simple baselines that perform feature selection are very important for understanding the usefulness of the proposal. Also, since a plethora of diverse methodologies for feature selection exist, this may make the baseline very competitive.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A2yAXD0ISUe", "reviewer": "Reviewer_Lqom", "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": "This paper studies the machine learning problems with OOD data (that is, out-of-distribution data). The paper models OOD data by introducing a new variable called spurious attribute, of which the conditional distribution is different across training and testing data. The paper proposes to use CSV (conditional spurious variation) as regularization term, so that the training process prefers stable output function against the change of spurious attribute distribution. Theoretical analysis is provided for different aspects of the CSV regularization.\n\n\n=====================\n\n\nAfter the discussion session, I believe that most of my concerns and the issues raised in other reviews are resolved. I am convinced that this is a solid paper that merits acceptance.", "summary_of_the_review": "This paper investigates an important machine learning problem of out-of-distribution data in a theoretical approach. The findings merit a publication. However, there are some mathematical problems -- probably just writing problems. I recommend a revision and would be more than happy to vote for a higher score after the above problem being resolved.", "strength_and_weaknesses": "Strength:\nThe idea of CSV-based regularization is promising and innovative.\n\nWeaknesses\nBelow I list some possible mistakes or typos, most very easy to fix. I feel that \"weakness\" could be a word too big for these problems.\n1. some terms may not be well known. I would suggest adding explanations. This includes: \"domain labels\"\n2. paragraph 3 on page 3: what is the difference between \"input's label\" and \"class label\"?\n3. I would suggest a comparison of the proposed condition with the condition in this paper:\nSmale, Steve; Zhou, Ding-Xuan. Online learning with Markov sampling. Anal. Appl. (Singap.) 7 (2009), no. 1, 87--113.\nFor example, I see many works in the literature assuming the invariant of conditional distribution of labels instead. I am curious about the difference between this setting, and the setting used in the current paper.\n4. Some small typos: \"quantify\" before Theorem 4 should be \"quantifies\";\n5. Please define the big-O notation in Theorem 4. In particular, what is the limit process?\n6. I hope that the author(s) can specify the definition of P, Q, X, Y, and Z, which I believe would greatly help the readers. In particular, I have the following questions directly related to the paper:\n(a). Is \"P\" (and \"Q\") a distribution of (X,Y) or (X,Y,Z)?\n(b). In general, X and Y are not independent. Are X and Z independent? Are Y and Z independent? Are (X,Y) and Z independent?\n(c). If Z and Y are not independent, then Z has the prediction power on Y. Would this still fit the definition of \"spurious correlation\" in this paper?\n7. In this paper the label set script-Y is discrete (Assumption 1). For the time being, let me assume the label set is just {0, 1}. Then the loss function script-L just assigns values for the set {(0,0), (0,1), (1, 0), (1,1)}. I think it does not make much sense to assume that L(u,y)=L(y) (the value depending only on y). I think it does not make much sense to assume in Assumption 2, that the parameter set Theta is disconnected and for any x, f_{theta}(x) depends on theta only through the connected component of the parameter set Theta. However, then there exist some x, y, theta1, and theta2 such that: theta1 and theta2 are path connected in the parameter space Theta (we skip the subtleties of path connected and connected spaces), f_{theta1}(x)=1, f_{theta2}=0, and L(1,y)!=L(0,y). But this would violate Assumption 2 because if we let theta travel along the path linking theta1 and theta2, at some stage f_{theta}(x) would jump from 1 to 0. Such a jump violates the Lipschitz continuity in Assumption 2, no matter how large L0 is.\nSo, Assumption 2 requires that the parameter space Theta is discrete and the distance of every pair of points uniformly bounded away from zero. As this is a very strong assumption for machine learning or statistics community, we suggest that this should be explicitly stated after Assumption 2. As a consequence, the Lipschitz smoothness of L in (6) is no longer necessary and should be removed.\n8. Right after Theorem 4, I guess the expression \"A decreases with B\" is not clear: what is its precise meaning?\n9. The definition (11) is confusing. It is obvious that when u runs through Delta_m, the maximum of u dot F is the maximum coordinate of the vector F. Why not directly use max-coordinate but employing Delta_m and writing (11) in the current complicated way?\n10. Page 14, right after (17), how does one derive P_{X|Y}=Q_{X|Y} without assuming P_Z=Q_Z? Also in Example 1, all the numbers 0 should be -1.\n11. I feel that the loss function in Example 1 is not designed properly. Indeed, L(1, -1)=3 while L(1, 1) = 4 is even larger. Also, the inequality (19) is derived based on the assumption that f(X)=1 almost surely, so the claim that (19) holds for any f is wrong. Even if we would like to cancel E[f(X)] with X|Y ~ Q or P, since the first term is conditioned on Y=1 and the second term is conditioned on Y=0, such cancellation is not doable in general.\n12. Proof of Propsition 2: please provide section or page number when citing a book. In this proof however, since script-Y is discrete, one may simply choose A=Script-Y and there is no need to take supremum.\n13. Equation (24) is wrong on the treatment of sup_{A in script-Y}.\n14. Equation (25) is wrong. For example in the last equation, the left-hand side depends on y, while the right-hand side does not.\n15. Proposition 2 is wrong. Obviously, since Q is in script-P, Q_Y=P_Y, so the only function w that achieves the minimum TV is a constant function w(y)=1, which makes the TV equal to zero.\n16. In the proof of Proposition 1, the classifier does not fit the framework proposed in this paper. In particular, the first argument of the loss function script-L is defined on script-Y, a discrete space. However, the classifier here outputs a real number. I guess a reasonable solution is to change the definition of the loss function to accept real first argument (at the top of page 3). This change may help to resolve the issue on Assumption 2.\n17. I think the first part of the proof of Theorem 1 does not work. We need to prove Q(Y|f(X))=P(Y|f(X)), but the current version of the proof still can not bridge to P(Y|f(X)). Please give explicit calculation that leads to this bridge.\n18. I feel confused about the treatment around Equation (40). In particular, the set script-P of distributions only provide Q_{X|Y,Z}=P_{X|Y,Z}, and here it seems to me that one is using Q_{X,Z|Y}=P_{X,Z|Y}. Please provide more details for this proof.\n19. My questions on Theorem 3 and its proof: is theta a random vector or a parameter? Seems neither way fits the proof. For the inequality \"a\", if all script-L stay close to M, then the log expectation term can not be bounded by O(1/n), is that right?\n20. There is a general question I feel confused: is Z observed as data? If yes, then Z goes to learning process and we do not have the OOD problem. In the scenarios that the distribution P_{Z|Y} changes from training to testing, the boundary between X and Z may not be easy to specify, and therefore the CSV penalty is still not easy to define. On the other hand, I feel very difficult to imagine a case where Z is not observable but still needs treatment.\n\nDue to the short review window, I have not checked the proofs of Appendix C.2 and later.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster