Malign Overfitting: Interpolation and Invariance are Fundamentally at Odds
Authors: Yoav Wald
Gal Yona
Uri Shalit
Yair Carmon
Venue: ICLR 2023 poster (2023)
Keywords: Invariance
Overparameterization
Fairness
Robustness
Benign Overfitting

Abstract: Learned classifiers should often possess certain invariance properties meant to encourage fairness, robustness, or out-of-distribution generalization. 
However, multiple recent works empirically demonstrate that common invariance-inducing regularizers are ineffective in the over-parameterized regime, in which classifiers perfectly fit (i.e. interpolate) the training data. This suggests that the phenomenon of ``benign overfitting," in which models generalize well despite interpolating, might not favorably extend to settings in which robustness or fairness are desirable. 

In this work, we provide a theoretical justification for these observations. We prove that---even in the simplest of settings---any interpolating learning rule (with an arbitrarily small margin) will not satisfy these invariance properties. We then propose and analyze an algorithm that---in the same setting---successfully learns a non-interpolating classifier that is provably invariant. We validate our theoretical observations on simulated data and the Waterbirds dataset.

Published as conference paper ICLR 2023
MALIGN OVERFITTING: INTERPOLATION CAN PROV- ABLY PRECLUDE INVARIANCE
Yoav Wald
Gal Yona
Uri Shalit
Yair Carmon
Johns Hopkins University ywald1 jhu. edu
Weizmann Institute of Science
Technion
Tel Aviv University
ABSTRACT
Learned classifiers should often possess certain invariance properties meant to en- courage fairness, robustncss, or ant-of-distribution gencralization. However, mul- tiple recent works empirically demonstrate that common invariance-inducingg reg- ularizers are ineffective in the over-parametertive regime, in which classifiers per- feetly fit (i.c. interpolate) the training data. This suggests that the phenomenon of "benign overfitting"" in which models generalize well despite interpolating, might not favorably extend to settings which robustness faireess are desirable.
In this work. we provide a theoretical justification for these observations. We prove that that-even in the simplest of settings any interpolating learning rule (with arbitrarily small margin) will satisfy these invariance properties. We then propose and analyze an algorithm that-in the same setting successfully learns non-ine interpolating classifier that is provably invariant. We validate our theoretical observations on simulated data and the Waterbirds dataset.
INTRODUCTION
Modern machine learning applications often call for models which are not only accurate, but which are also robust distribution shifts or satisfy faimess construints. For example, we might wish to avoid using hospital-speette traces in X-ray images (DeGrave et al., 2021; Zech et al., 2018), as they rely on spurious correlations that will not generalize to a new hospital, or we might seek "Equal Opportunity" models attaining similar error rates across protected demographic groups, e.g. in the context of loan applications (Byanjankar et al., 2015; Hardt et al., 2016). A developing paradigm for fulfilling such requirements is learning models that satisfy some notion of invariance (Peters et al., 2016; 2017) across environments sub- poppplpauaiios.. For example, in the X-ray case, spurious correlations can be formalized relationships between feature and a lahel which vary across hospitals (Zech et al., 2018). Equal Opportunity (Hardt et al., 2016) can expressed as a statistical constraint on the outputs of the model. where the false negative rate invariant to membership in protected group. Many techniques for lcarning invariant models have been proposed including penalties that encourage invariance (Arjovsky et al., 2019; Krueger et al., 2021; Veitch et al., 2021: Wald et al., 2021; Puli et al., 2021; Makar ct al., 2022; Rame et al., 2022; Kaur et al., 2022), data re- weighting (Sagawa et al., 2020a; Wang et al.. 2021; Idrissi et al., 2022), causal graph analysis (Subbaswamy et al., 2019; 2022), and more (Ahuja al., 2020).
While the invariance paradigm holds promise for delivering robust and fair models, many current wwarrancc-indducng methods often fail to improve over naive approaches. This is especially notice- able when these methods are used with overparameteriized deep models capable of interpolating, i.e., perfectly fitting the training data (Gulrajani & Lopez-Paz. 2021; Dranker et al., 2021; Guo et al., 2022; Zhou al., 2022; Menon al., 2021; Veldanda al., 2022; Cherepanova et al., 2021). Existing theory explains why overparamcteriiatton hurts invariance for standard interpolating learn- ing rules, such as empirical risk minimization and max-margin classification (Sagawa et al., 2020b; Nagarajan et al., 2021: 1)' Amour et al., 2022), and also why reweighting and some types of dis- tributionally robust optimization face challenges when used with overparameterized models (Byrd & Lipton, 2019; Sagawa et al., 2020a). In contrast, training overparameterrzeed models to inter- polate the training data typically results in good in-distribution generalization, and such "benign overfitting" (Kini et ul. 2021; Wang et al., 2021) is considered key characteristic of modern deep lcarning (Cao al., 2021; Wang & Thrampoulidis, 2021; Shamir, 2022). Consequently, num-

---

Published as conference paper at ICLR 2023
ber of works attempt extend benign overfiuting robust fair generalization by designing new interpolating learning rules (Cao al., 2019; Kini et al., 2021; Wang al., 2021; La al., 2022).
In this paper, demonstrate that such attempts face fundamental obstacle. because all interpo- lating learning rules (and not just maximum-margin classifiers) fail produce invariant models in certain -ige-iiimnnional settings where invariant learning (without interpolation) is possible. This does not occur because there are no invariant models that separate the data, but because interpolating learning rules cannot find them. In other words, beyond identically-distribe is no longer benign. More concretely, we consider linear classification in a basic overparameterized Gaussian mixture model with invariant "core" features as well as enviromment-dependenn "spuri- ous" features, similar to models used in previous work to gain insight into robustness and invariance (Schmidt et al., 2018; Rosenfeld et al., 2021; Sagawa et al., 2020b). We show that any learning rule producing classifier that separates the data with non-zero margin must necessarily rely the spurious features in the data, and therefore cannot be invariant. Moreover, in the same setting analyze a simple two-stage algorithm that can find accurate and nearly invariant linear classifiers, i.e. with almost no dependence on the spurious feature.
test sets, overfitting
Thus, establish separation between the level of invariance attained by interpolating and con-interpolating learning rules. We helieve that learning rules which fail in the simple over- parameterized linear classification setting we consider are not likely to succeed cated, real-world settings. Thereefore our analysis provides useful guidance for future research into robust and fair machine lcarning models, as well as theoretical support for the recent success of non- interpolating robust learning schemes (Rosenfeld et al., 2022; Veldanda et al., 2022; Kirichenko et al., 2022; Menon ct al., 2021; Kumar ct al., 2022; Zhang ct al., 2022; Idrissi et al., 2022; Chatterji et al., 2022).
more compli-
Paper organization. The next section formally states our full result (Theorem 1). In Section 3 we outline the arguments leading to the negative part of Theorem 1. i... the failure of interpolating classifiers to be invariant in our model. In Section 4 we establish the positive part Theorem 1, by providing and analyzing
intererppoll algorithm that, in model, achieves low robust error. We validate our theoretical findings with simulations and experiments the Waterbirds dataset in Section 5, and conclude with discussion of additional related results and directions for future research in Section 6.
2
STATEMENT OF MAIN RESULT
2.1 PRELIMINARIES
Data model. Our analysis focuses on learning linear models over covariates x distributed as mixture of two Gaussian distributions corresponding to the label y.
Definition 1. An environment is a distribution parameterized by (pe.Hs, d, 0) where 0 E [-1, and ph, M. c Rdd satisfy p.. 1 μt. and with samples generated according to:
Po(y)
-1,1)
Po(x)y)) -N(ur y0p,, o2
Our goal is to find a (lincar) classifier that predicts from x and is robust to the value of 8 (we discuss the specific robustness metric below). To do so, the classifier will need to have significant inner product with the "core" signal component μt, and be approximately orthogonal to the "spurious" component p4,, We focus on learning problems where we are given access to samples from two environments that share all their parameters other than we define next. We illustrate our setting with Figure in Appendix A.
Definition 2 (Linear Two Environment Problem), In a Linear Two Environment Problem have datasets S = {x(") (1) (1,, and S2 = {x(2) (2) y1 N of sizes N1, N₂ drawn from Fe. and Ps, respectively. A learning algorithm is a (possibly randomized) mapping from the tuple (Si, to
linear classifier
Rd. We let S (x., y: 1. denote that dataset pooled from Sn and S2 where N N1 N2. Finally let = || and
||l.ll.
We study settings where 0g. O2 are fixed and d is large compared to N, i.c. the overparamcteriized regime. Wc refer to the two distributions Ps. for e E {1,2} as "training environments", following Peters et al. (2016); Arjovsky et al. (2019). In the context of Out-of-Distribuute (OOD) generaliza- tion, environments correspond to different experimental conditions, c.g., collection of medical data
2

---

Published as conference paper ICLR 2023
in two hospitals. In fairness context, we may think of these distributions subpupulations (e-g-- demographic groups). 'While these are different applications that require specialized methods, the underlying formalism of solutions often similar (see, e.g.. Creager et al., 2021, Table 1), where we wish to learn a classifier that in one way or another is invariant to the environment variahle.
Robust performance metric. An advantage of the simple model defined above is that many of the common invariance criteria all boil down the same mathematical constraint: learning classifier that is orthogonal to Jts, which induces a spurious correlation between the environment and the label. These include Equalized Odds (Hardt et al., 2016), conditional distribution matching Li et al. (2018), calibration on multiple subsets of the data (Hébert-Johnson et al., 2018; Wald et al., 2021), Risk Extrapolation (Krueger et al., 2021) and CVaR faimesss (Williamson & Menon, 2019).
In terms of predictive accuracy. the goal of learning a linear model that aligns with μa, (the invariant part of the data generating process for the label) and is orthogonal to μt, coincides with providing guarantees on the robust error, i.c. the error when data is generated with values of 8 that are diffcrent from the 01. 0g used to generate training data.
Definition 3 (Robust error). The robust error of linear classifier Rd
max co(w), where cs(w) == Ex.g--F, (sign( (ww x)) # v).
#E| 1E|-1,1]
Normalized margin. We study is whether algorithms that perfectly fit (i.c. interpolate) their train- ing data can leamn models with low robust error. Ideally, we would like to give result all classifiers that attain training error zemo in terms of the (-1 loss. However, the inherent discontinuity of this loss would make any such statement sensitive to instabilities and pathologies. For instance, if we do not limit the cupacity of models, we turn any classifier into interpolating one hy adding "special cases" for the training points, yet intuitively this is not the type of interpolation that we would like to study. To avoid such issues, we replace the 0-1 loss with common continuous surrogate, the normalize margin, and require to be strictly positive.
Definition 4 (Normalized margin). Let
we say classifier w E B seporates the set S (x..:: LV with normalized margin 7 for every (xc, u) E S
y xx) w|
yoodd.
The Vo2d scaling of 7 is roughly proportional to ||x| under data model in Equation (I), and keeps the value of y compurable across growing values of d.
2.2 MAIN RESULT
Equipped with the necessary definitions, we now state and discuss our main result.
Theorem 1. For any sample sizes N1, N2 > 65, margin lower bound ty TVR. target robust error and coefficients
02 N.Y there exist parameters Ves Tx >> N, and 0 such that the following holds for the Linear Two Environment Problem (Definition 2) with these parameters.
2
1. Invariance is attainable. Algorithm maps (S),Sg) to a linear classifier w such that with probability least Tod (over the draw S), the robust error of w is less than c.
2. Interpolation is attainable. With probability at least 100' the estimator W Wmenn N EIEI V;N; separates S with normalized margin (Definition 4) greater than TV
99
'We note that in some settings. more commonly in the faimnss literature, e is treuted feature given to the classifier as input. Our focus is on cases where this is cither impossible or undesired. For instance, because at test time is unobserved or ill-defined (e.g. we obtain data from new hospital). However, we emphasize that the leaning rudes consider have full knowledge of which environment produced each training example IIn fact, as we show Equation (5) in Section 3. learning a model orthogonal to μl, is also a necessary condition to minimize the robust error. Thus, attaining guarantees the robust error also has consequences on invariance of the model, as defined by these criteria. We discuss this further in section of the appendix.
3

---

Published as conference paper ICLR 2023
3. Interpolation precludes invariance. Given u., uniformly distributed on the sphere of radius Te and st, uniformly distributed on a spkere of radius T, in the subspace orthogonal to Pe: let w be any classifier learned from (S1,S, as per Definition If w separates S with normalized margin "I then with probability at least 99 (over the draw of pes Pa, and the sample), the robust TOD
ervor of w is at least
Thcorem shows that if a learning algorithm for overparameterized linear classifiers always sepa- rates its training data, then there exist natural settings for which the algorithm completely fails to learn a robust classifier, and will therefore fail multiple other invariance and faimess objectives. Furthermore, in the same setting this failure is avoidable, as there exists an algorithm (that neces- sarily does not always separate its training data) which successfully learns an invariant classifier. This result has deep implications for thcoreticians attempting to prove finite-sample invariant learn- ing guarantees: it shows that-in -nn the fundamental setting of linear classification no interpolating algorithm can have guarantees as strong as non-interpolating algorithms such as Algorithm 1.
Importantly, Theorem requires interpolating invariant classifiers to exist- shows that these classifiers are information-thhorrtiialll therreticalrll impossible to learn. In particular, the first part of the theo- rem implies that the Bayes optimal invariant classifier w = 44g has robust test error at most e. There- fore, for all e < 100/ we have that μa, interpolates 5 with probability > 100- Furthermore, a short calculation (see Appendix C.I) shows that (for Te. Tas d and a satisfying Theorem 1) the normalized margin of u. is Q((N + </N//)) $). However, we prove that-due due to the high-dimensional na- ture of the problem- no algorithm can use ($1, S2) to reliably distinguish the invariant interpolator from other interpolators with similar or larger margin. This lcarnability barrier strongly leverages our random choice of ft.. Ms, without which the (fixed) vector μ., would be valid learning output.
99
We establish Theorem with three propositions, each corresponding to an enumerated claim in the thoorem: (1) Proposition 2 (in $4) establishes that invariance is attainable, (2) Proposition 3 (Appendix C) establishes that interpolation is attainable, and (3) Proposition (in $3) establishes that interpolation precludes invariance. We choose to begin with the latter proposition since it is the main conceptual and technical contribution of paper. Conversely, Proposition 3 is an easy byproduct of the developments leading up to Proposition I, and we defer to the appendix.
With Propositions 1, 2 and 3 in hand, the proof of Theorem simply consists of choosing the free parameters in Theorem (re, F., d and based on these propositions such that all the claims in the theorem hold simultanenusly. For convemience we take o² 1/d. Then (ignoring constant factors) we pick r N and r r2/(1 Ni7
vN2) in order satisfy requirements in Propositions and 3. Finally, we take d to be sufficiently large so as to satisfy the remaining requirements, resulting in N (o)) 1
d oc max 222 ş=NTVz Nmanr? N J. where Numin = min(NN, N2) and Q is the Gaussian tail function (see Appendix E for the full proof).
We conclude this section with remarks on the range of parameters under which Theurem holds. The impossibility results in Theorem are strongest when N₂ is smaller than N777². In particular, when N₂ < N //88, our result holds for all 0g E [-1, 1, 1] and moreover the core and spurious signal strengths ye and r. can he chosen to he of the same order. The ratio (2((N?²²) is small either when one group under-represented (i.e., N2 < NN) or when considering large margin classifiers (i.., of the order 1/ I/ Moreover, unlike prior work on barriers to robustness (e.g.. Sagawa et al., 2020b; Nagarajan et al., 2021), our result continue to hold even for balanced data and arbitrarily low margin, provided 0g is close to and the core signal is sufficiently weaker than the spurious signal. Notably, the normalized margin can be arhitrarily small while the maximum achievable margin is always least of the order of VN- Therefore, believe that Theorem essentially precludes any interpolating learning rule from being consistently invariant.
3 INTERPOLATING MODELS CANNOT BE INVARIANT
In this section we prove the third claim in Theorem 1: for essentially any nonzero value of the normalized margin 7, there are instances of the Linear Two Environment Problem (Definition 2) where with high probability, lcarning algorithms that return lincar classifiers attaining normalized margin least y must incur large robust error. The following proposition formalizes the claim; sketch the proof below and provide full derivation in Appendix B.3.
4

---

Published as conference paper ICLR 2023
Proposition 1. For 1/vd, 01 1, there universal constants Cr E (0.1) and Ca, C+ e (1, 0o), such that, for any target normaized 7, G2 > -N17/v288N2, and failure probability E (0, 1). if
Cr max (1 (12.
r Cr
VN2 N17
and
(3)
N re
2 Ci. ?2NPr2
log
then with probobility at least 1- over the drawing of Me: p4, and (S1, as described in Theorem 1, any ve Ied that measurable function of (S1, S2) and separates the data with normalized margin larger than y has robust error at least 0.5.
Proof sketch. We begin by noting that for any fixed 0, the error of linear classifier w is
<o(w) = Q (W.Pte) (ao) + f(w. (s) O(w.Ht)
Q (w. [1+ (w. Maa
(W.pae) (4a)
(5) Consequently, when
о o|wl]
[[[w]]
(w, (w.pe))
where Q(1)
P(V(O;
t) the Gaussian tail function.
(W, (w./(W,H Ma) 2 1 is easy to see that co(w) = 1/2 for some 0 E [-1, and therefore the p.)/ (w, pe) 2 1 indeed holds with high probability under the proposition's 's ussumptions. Our proof has two key parts: (a) restricting the set of classifiers
robust emror is at least 1: we prove that (w.p.)/
to the linear span of the data and (b) lower bounding the minimum value of (w, /.)/(w, mc) for classifier in that linear spun.
For the first part of the proof we use the spherical distribation of μe and μ4, and concentration of measure to show that (with high probability) any component of w chosen outside the linear span of {>x, keeN" will have negligihlc effect on the predictions of the classifier. To explain this fact, let P. denote the projection operator the orthogonal complement of the data, so that P. is the
component of orthogonal the data and (e) = PPP PLppell- Conditional
M.. (St.S2) and the learning rule's random seed, the vector Pit P- is uniformly distributed on a unit sphere dimension d while the vector w is deterministic. Assuming without loss of generality that ||w|| 1, concentration of measure on the sphere implics that Kww, |P_mell is (with high probability) bounded by roughly 1/vd, and therefore ((P w. Mc) is roughly of the order re/Vd. For sufficiently large (as required by the proposition). this inner product would be negligible, meaning that (w, Me) roughly the same ((I P_)w. pe),, and (I P_)w )w is in the span of the data. The same argument applies to μt, as well.
In the second part of the proof, consider classifiers of the form EECIN Sayx, (which parameterizes the linear span of the data) and minimize (w. (4.)/(w: (W.)ae) over 3 E RN subject to the constraint that has normalize margin of at least 7. To do so, first concentration of measure to argue that is sufficient to lower bound , 3 subject the margin constraint and || 2| 1, which is convex in 8-we obtain this lower bound by analyzing the Lagrange dual of the problem minimizing M. (3 subject to these constraints.
Overall, we show a high-prohahility lower bound on (w.j..) that (for sufficiently high dimensions) NiN For parameters satisfying Equation (3) we thus obtain (w.aea) (w.M.))
scales roughly as PVVN. pleting the proof.
2 1, com-
Implication for invariance-inducing algorithms. Our proof implies that any interpolating algo- rithm should fail learning invariant classifiers. This alone does necessarily imply that specific algorithms proposed in the literature for learning invariant classifiers fail, as they may not he in- terpolating. Yet our simulations Section show that several popular algorithms proposed for climinating spurious features are indeed interpolating in the overparameterizzd regime. We also give a formal statement in Appendix G regarding the IRMv1 penalty (Arjovsky et al., 2019), show- ing that it is biased toward large margins when applied to separable datasets. Our results may seem discouraging for the development of invariancc-inducing techniques using overparameterized mod- els. It is natural to ask what type of methods can provably learn such models, which is the topic of the next section.
5

---

Published conference paper ICLR 2023
Algorithm 1 Two Phase Learning of Overparameterized Invariant Classifiers
Input: Datasets (S1, Su) and invariance constraint function family Fl:,))
Output: A classifier fx(x)
Draw subsets of data without replacement Strain C S, for E {1,2) where |Stmin| = NN./2
Stage I: Calculate w. 2N Σ (x.)) 1/x for cach E {1,2)
Define Stine S, \. 1 for e E {1, 23 and Spost = Sfiee U S
Stage 2: Return (x) = (1r W1 + P2 W2,x) x) that solves
maximize
Σ
xx((x)
subject
||v||= =1 and J. E F(stme,
A PROVABLY INVARIANT OVERPARAMETERIZZE ESTIMATOR
We now turn to propose and analyze an algorithm (Algorithm 1) that provably learns an over- parametrized lincar model with good robust accuracy in our setup. Our approach is a two-staged learning procedure that is conceptually similar to some recently proposed methods (Rosenfeld et al.. 2022: Veldanda et al., 2022; Kirichenko al.. 2022; Menon et al.. 2021; Kumar et al., 2022; Zhang et al., 2022). In Section 5 we validate our algorithm simulations and the Waterbirds dataset Sagawa al. (2020a), but we leave thorough empirical evaluation of the techniques described here to future work.
Let deseribe the operation of Algorithm First, evenly" split the data from each environment into the sets Strain Spost for c 21. The two stages of the algurithm operate different splits of the data follows.
1. "Training" stage: We (Strain) to fit overparamettrrized, interpolating classifiers (we) sep- arately each environment (1,
2. "Post-pru sest-processig"" stage: Wc use the second portion of the data (Spost .Sgoat learn invari- ant linear classifier over the first stage. In particular, we learn this classifier by maximizing score (i.e., minimizing an empirical loss), subject to an empirical version of an invariance constraint. For generality denote this constraint by membership in some set of functions F(Sport S
representation, which concatenates the outputs of the classifiers
Crucially, the invariance penalty is only used in the second stage, in which we are no longer in the overparamterized regime since we are only fitting two-dimensional classifier. In this way we overcome the negutive result from Section 3.
While our approach is general and can handle a variety of invariance notions (we discuss some of them in Appendix F), we analyze the algorithm under the Equal Opportunity (EOpp) criterion (Hardt et al., 2016). Namely, for model f Rd IR we write:
F(Sfine Shic) = (f ((() = T2(f). where Po(f) =
Σ
f(x).
(x.))
This is empirical version of the constraint Ep,, [[x)]y = fairness perspective (e.g., thinking a loan application), this constraint ensures that the "qualified" members (i.e., those with y 1) of each group receive similar predictions, on average over entire group.
Er,, [f(x)ly= = 1j. From
We now turn to providing conditions under which Algorithm successfully learns an invariant pre- dictor. The full proof the following proposition can he found in section D.11 the appendix. While we do not consider the following proposition very surprising. the fact that gives a finite sample learning guarantce mcans it does not directly follow from existing work (discussed in $6 below) that mostly assume inifinite sample size.
'The split used here for simplicity of exposition, and full proof does assume practice, allocating more data to the first-stage split would likely perform better.
6

---

Published conference paper ICLR 2023
Accuracy vs.
Training Accuracy vs.
Accuracy vs.
In-Demain Test Accuracy
2.8
1.0
1.a
Robust Accuracy
2.8
VRtx
0.8
IMM
Training
HHD
CENAL
Groupand
8.
Algonihmm
162
102
10a
10a
107
30
100
122 101
Figure Numerical validation of our theoretical claims. Invariance inducing methods improve robust accuracy compared to ERM low values of d, but their ability to do so is diminished as grows (top plot) and they enter the interpolation regime, as seen on the bottom plot for d > 10?. Algorithm I learns robust predictors d grows and does not interpolate.
Proposition 2. Consider the Linear Two Environment Problem (Definition 2). and further sup- pose that 191 82l > 0.1.* There exist universal constants Cp. Ce. C. E (1,00) such that the following holds for every target robust enor e > and failure probability (0,1). If Nuin = min N1. N2) 2 Cogo log(1/)) (/)).ffl for some Cp E (1,)))?
C.ylo
68 08o2
re Coo log max
68
Q 2(0)
(6)
Niiin
Nmin
Nuin
Nuinr? 2
68
and d 2 log
(7)
then, with probability at least 1 over the draw of the training data and the split of the data between the two stages of learning, the robust error of the model returned by Algorithun I does not exceed
Proof sketch. Writing down the error fv = v1 Wi + 1/2 W2 under Po. it can shown that to obtain the desired bound on the robust error of the classifier returned by Algorithm 1, we must upper hound the ratio
(u70, 03 (M,, ii vgfz))
(v) =g)ll (Me, ui m2m2))
when ny is the mean of Gaussian noise vectors, and and vt are the solutions the optimization problem in Stage of Algorithm 1. The terms involving inner-produce with the noise terms zero-mean and can be bounded using standard Gaussian concentration arguments. Therefore, effort the proof is upper bounding
010 mg82
of +
|1.11
To this end, we leverage the EOpp constraint. The population version of this constraint (correspond- ing to infinite N1 and N2) implies that 0;0; + mg = O. For finite sample sizes, we use standard Gaussian concentration and the Hanson-Ve Hanson-Wright inequality to show that the empirical EOpp con- straint implies that 0 0202l goes zero us the sumple sizes increuse. Furthermore, argue that (ut + ut| 10, /2, implying for appropriately large sample sizes the above ratio indeed goes
5 EMPIRICAL VALIDATION
The empirical observations that motivated this work can be found across the literature. We therefore focus simulations validating the thcoretical results in our simplified model. We also evaluate Algorithm the Waterbirds dataset, where the goal is not show state-of-the results, but rather observe whether our claims hold beyond the Lincar Two Environment Problem.
'Intuitively, if (9, 6g] 0 then the two training enviromments are indistinguishahle and we cannot hope to identify that correlation induced n. sparious. Otherwise, expect [0 8gl a quantifiable effect ubility generalize robustly. For simplicity of this exposition assume the gap is bounded from zero; the full result in the Appendix is stated in terms of (9; 0z]. This assumption makes sure have some positive labels in each environment.
7

---

Published as conference paper ICLR 2023
5.1 SIMLUATIONS
Setup. We generate data as described in Theorem with two environments where 0, = 1, 02 = (see Figure in the appendix for results of the same simulation when = = We further fix r. = and re = 2. while N1 = 800 and N₂- = 100. We then take growing values of d, while adjusting o so that (ra/a)² x /d/N. 6 For each value of d we train linear models with IRMv1 (Arjovsky et al., 2019), VREx (Krueger et al., 2021), MMD (Li et al., 2018), CORAL (Sun & Sacnko, 2016), GroupDRO (Sagawa et al., 2020a), implemented in the Domainbed package (Gulrajani & Lopez- Paz. 2021). We also train a classifier with the logistic loss to minimize empirical error (ERM), and apply Algorithm 1 where the wost-processingg stage trains lincar model over the two-dimensional representation using the VREx penalty to induce invariance. We repeat this for 15 random seeds for drawing Me: M, and the training sct.
Evaluation and results. We compare the robust accuracy and the train set accuracy of the learned classifiers as d grows. First, we observe that all methods except for Algorithm I attain perfect ac- curacy for large enough d, i.e., they interpolate. We further note that while invariance-inducing methods give desirable effect in low dimensions (the -on-epeerpolating proving the robust emror over ERM-they become aligned with ERM in terms of robust accuracy as they go deeper into the interpolation regime (indeed, IRM essentially coincides with ERM for larger d). This is an expected outcome considering our findings in section 3, as we set here N1 to be considerably larger than N2.
(ighine)-igniiianntt im-
5.2 WATERBIRDS DATASET
We evaluate Algorithm I on the Waterbirds dataset (Sagawa et al., 2020a), which has been previously used to evaluate the faimess and robustness of deep learning models.
Setup. Waterbirds is a synthetically created dataset contaiming images of water- and land-birds overlaid on water and land background. Most of the waterbirds (landbirds) appear in water (land) backgrounds, with smaller minority of waterbirds (landbirds) uppearing on land (water) back- grounds. Wc set up the prohlem following previous work (Sagawa et al., 2020b; Veldanda et al., 2022), where logistic regression model trained over random features extract from fixed pre- trained ResNct-18 18. Please see Appendix H for details.
Fairness. We use the image background type (water or land) as the sensitive feature, denoted A. and consider the faimess desiderata of Equal Opportunity Hardt al. (2016), ie.. the false negative rate (FNR) should similar for both groups. Towards this, we use the MinDiff penalty term (Prost et al., 2019). The
Evaluation. We compare the following methods: (1) Baseline: Learning linear classifier w by minimizing L.p + X- Las, where Cp the standard hinary cross entropy loss and Las is the MinDiff penalty; (2) Algorithm 1: the first stage, we learn group-specifie linear classifiers wo, Wi by minimizing fp on the examples from A = O and A = 1, respectively. In the second stage we learn IR2 by minimizing Cp + A Lx on examples the entire dataset, where the new representation of the data is X [(w), (w², x> E R2.7
effect of the fairesss penalty. Toward this, for each method we compare both the test error and the test FNR gap when using either = (no regularization) or A= 55 5. The results are summarized in Figure 2. We can see that for the baseline approach, the fairness penalty successfully reduces the FNR gap when the classifier is not interpo- lating. However, as our negative result predicts and as previously reported in Veldanda ct al. (2022), the fairness penalty becomes ineffective in the interpolating regime (d > 1000). On the other hand, for our two-phased algorithm, the addition of the faimess penalty reduces does reduce the FNR gap with an average relative improvement of 20%; crucially, this improvement independent of d.
Results. Our main objective is to understand
"This to keep our parameters within the regime where benign overfitting occurs.
"This is basically Algorithm with the following minor modificutions: (1) The w. are computed via ERM. rather than simply taken to be the mean estimators: (2) Since the FNR gap penalty already computed w.t.t small number of samples, avoid splitting the data and the entire training set for both phases; (3) convert the constrained optiiizaiion problem into an unconstrained prohlem with penalty term.
8

---

Published as conference paper ICLR 2023
1:10
3 com
0:10
3
201 2004
Figure 2: Results for the Waterbirds datasct (Sagawa ct al., 2020a). Top row: Train error (left) and test error (right). The train error is used to identify the interpolation threshold for the buseline method (approximately d 100U). Bottom row: Comparing the FNR gap the test set (left), with zoomed-in in versions on the right.
6 DISCUSSION AND ADDITIONAL RELATED WORK
In terms of formal results, most existing guarantees about invariant learning algorithms rely on the assumption that infinite training data is available (Arjovsky et al., 2019: Wald et al., 2021; Veitch et al., 2021; Puli et al., 2021; Rosenfeld et al., 2021; Diskin et al., 2021). Wang et al. (2022); Chen et al. (2022) analyze algorithms that bear resemblance to Algorithm 1 as they first project the data to a lower dimension and then fit classifier. While these algorithms deal with more general assumptions in terms of the number of environments, number of spurious features, and noise distribution. the fact that their guarantees assume infinite data prevents them from being directly applicable Algorithm 1. A few works with results finite data are Ahuja al. (2021); Parulekar et al. (2022) (and also Efroni al. (2022) who work related problems in the context of sequential decision making) that characterize the sample complexity methods that lear invariant classifiers. However, they do not analyze the overparameterized cases we are concerned with.
Negative results about learning overparameterizee robust classifiers have been shown for methods based importance weighting (Zhai et al., 2022) and max-margin elassifiers (Sagawa ct al., 2020h).. Our result more general, applying to any learning algorithm that separates the data with arbitrarily small margins, instead of focusing on max max- margin classifiers or specific algorithms. While we focus on the linear case, we believe it is instructive, as any reasonable method is expected to succeed in that case. Nonetheless, we believe our results can be extended to non-lincar classifiers, and we leave this to future work.
One take-away from our result is that while low training loss is generally desirable, overfitting to the point of interpolation can significantly hinder invariance-inducing objectives. This means one cannot assume a typical deep learning model with an added invariance penalty will indeed achieve any form of invariance; this fact also motivates using held-out data for imposing invariance, as in our Algorithm as well several other two-stage approaches mentioned above.
Our work focuses theory underlying wide array of algorithms, and there are natural follow-up topics to explore. One is to conduct comprehensive empirical comparison of two-stage methods along with other methods that avoid interpolation. e.g.. by subsampling data (Idrissi al., 2022; Chatterji et al., 2022). Another interesting lopic is whether there are other model properties that are incompatihlc with interpolation. For instance, recent work (Carrell et al., 2022) connects the generalization gap and calibration error on the training distribution. We also note that our focus in this paper was not on types invariance that are satisfiable by using clever data augmentation techniques (e.g. invariance to image translation), or the design of special architectures (e.g. Cohen & Welling (2016); Lee et al. (2019); Maron et al. (2019)). These methods carefully incorporate a-priori known invariances, and their empirical success when applied to large models may suggest that there are lessons to be learned for the type of invariant learning considered in our paper. These connections seem like an exciting avenue for future rescarch.
9

---

Published as conference paper ICLR 2023
REFERENCES
Kartik Ahuja. Karthikeyan Shanmugam, Kush R. Varshney, and Amit Dhurandhar. Invariant risk minimization games. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 145-155. PMLR, 2020. URL http:: http:://proceedings... mlr. www.l.ppres//eeee press/v119/ ahuja20a. htm.l........
Kartik Ahuja, Jun Wang. Amit Dhurandhar, Karthikeyan Shanmugam, and Kush R. Varshney. Em- pirical or invariant risk minimization? A sample complexity perspective. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL http::::/pppepeeeeeeeeee/ wwwriiiw.eee/eee.... formfo wiwummiiiiiie direediddjjssaa idj))xsGAccyyyy.....
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. ArXiv preprint, abs/1907 htss/1907.0283, 2019. URL https: : /tt///axvvv..////////.e////eaevt www.w..ww..../////./. 907. 02893.
Keith Ball et al. An elementary introduction to modern convex geometry. Flavors of geometry, 31 (1-58):26, 1997.
Ajay Byanjankar, Markku Heikkilä, and Jozsef Mezei. Predicting credit risk in peer-to-pese lending: A neural network approach. In 2015 IEEE symposium series computational intelligence, pp. 719-725. IEEE, 2015.
Jonathon Byrd and Zachary Chase Lipton. What is the effect of importance weighting in deep learning? Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings the 36th International Conference on Machine Learning, ICML 2019. 9-15 June 2019, Long Beach. Cal- ifornia, USA, volume 97 of Proceedings of Machine Learning Research, pp. 872-881. PMLR, 2019. URL http:////// /ptpceediccccesseeeeeeeeeeces.ee mlr. wwwss/evsss /byy rel 9a.html.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Aréchiga, and Tengyu Ma. Learning imbalanced datascts with lahcl-distriuution-aaan margin loss. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference
Neural Information Pro- cessing Systems 2019, NewrlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 1565-1576. 2019. URL https:/ httppppeoccengssseeeeeeepp neurips. http:sssss......s..p..eeerpeeeee wctppppppppppcceeccocceeceeeeeep 200paper/219///// 2019//ash// haahh/ 621 90cadffa www.fffaa@@@44c255555555 - html.
Yuan Cao, Quanquan Gu, and Misha Belkin. Risk bounds for over-parameterizzd maximum margin classification on sub-gaussian mixtures. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances Nearal Information Processing Systems. 2021. URL https:// openreview. net corum? woloorumiiidiiiiiii..... iid-Chhylllii war.s/yaayyuuoo...
A. Michael Carrell, Neil Mallinar, James Lucas, and Preetum Nakkiran. The calibration generaliza- tion gap, 2022. URL ht :ps: / www.i.ogggaaa.....aa..a...ooo wwtp/aa/////oooooooo////o/o/.aae abs 220/22211..00 111.1..000 00964.
Niladri S. Chatterji, Saminul Haque, and Tatsunori Hashimoto. Undersampling is minimax optimal robustness intervention in nonparametric classification, 2022. URL https: //arrva.aaa.///aa/eaaeeeeeaaeeea org// abs/2205.. 13094.
Yining Chen, Elan Rosenfeld, Mark Sellke, Tengyu Ma, and Andrej Risteski. Iterative fea- ture matching: Toward provable domain generalization with logarithmic environments. In Al- ice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neu- ral Information Processing Systems, 2022. URL URLhttts: /oppnrevieee.eeeee net forum? idd CF SE1ThuQ8v9G.
Valeriia Cherepanova, Vedant Nanda, Micah Goldblum, John Dickerson, and Tom Goldstein. Technical challenges for training fair neural networks. ArXiv preprint, abs/2102.06764, 2021.
URL bt tps: /ates////aaxii /twpiiiiiii.///////ea/////aae..a org/ /bss////////////// /2102. .2210.66.6....
Taco Cohen and Max Welling. Group equivariant convolutional networks. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICMI. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2990-2999. JMLR,org, 2016. URL http:/ http:://proceed/ ngs. ml presss/ v48 cohencl h.mml.
10

---

Published as conference paper ICLR 2023
Elliot Creuger, Jörn-Herrik Jacobsen, and Richard S. Zemel. Environment inference for in- variant learning. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th Interna- tional Conference on Machine Learning, ICML 2021. 18-24 July 2021, Virtual Event, vol- ume 139 of Proceedings of Machine Learning Research, pp. 2189-2200. PMLR, 2021. URI. http:/ /pwppoeednggs........pppp www.prees//eee /1139/ 3tt.//////eee111//
2tm...l...........mmm.mmm.....mm html.
Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beu- tel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D. Hoffmman, Farhad Hor- mozdiari, Neil Houlsby, Shaobo Hou, Ghassen Jerfel, Alan Karthikesalingam, Mario Lucic, Yian Ma. Cory McLean, Diana Mincu, Akinori Mitani, Andrea Montanari, Zachary Nado, Vivek Natarajan, Christopher Nielson, Thomas F. Osborne, Rajiv Raman, Kim Ramasamy, Rory Sayres, Jessica Schrouff, Martin Seneviratne, Shannon Sequeira, Harini Suresh, Victor Veitch, Max Vladymyrov, Xuezhi Wang. Kellie Webster, Steve Yadlowsky, Taedong Yun, Xi- aohua Zhai, and Sculley. Underspecification presents challenges for credibility mod- em machine learning. Journal of Machine Learning Research, 23(226)11-6,, 2022. URL http: fmlr. hwtgg/papr//vaeee /233// 20- 1335. html.
Alex DeGrave, Joseph Janizek, and Su-In Lec. Ai for radiogruphic covid-19 detection selects shorteuts over signal. Nature Machine Intelligence, 3(7):610-61) 619, 2021.
Tzvi Diskin, Yonina C. Eldar, and Ami Wiesel. Learning to estimate without bias, 2021. URL https: /ttx/aa..vv///.////a//e.//./waa. www.abs/////aaaooooeeo....//.aaa aaaaab///// 2210.100..2 12403.
Yana Dranker, He He, and Yonatan Belinkov. Irm Irm-when it works and when it doesn't: A test case of natural language inference. In M. Ranzato, A. Beygekzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 18212-18224. Curran Associates, Inc., 2021.
Yonathan Efroni, Dylan Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford. Sample-efficient reinforcement learning in the presence of exogenous information. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 5062-5127. PMLR, 2022. URI. https: htttps://prceeeeeeeee prw./ediocee.gssooooooee mlr. prressses////e.ee / www.////ooo//i//eeee/e
html.
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
net forum? www.gdxxxxooo......
Lin Lawrence Guo, Stephen R. Pfohl, Jason Fries, Alistair E. W. Johnson, Jose Posada, Catherine Aftandilian, Nigam Shah, and Lillian Sung. Evaluation of domain generalization and adaptation on improving model robustness to temporal dataset shift in clinical medicine. Scientific Reports, 12(1):2726, 2022.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised lcarning. In Daniel D. Lee, Masashi Sugiyama. Ulrike von Luxburg, Isabelle Guyon, and Roman Gar- nett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3315-3322 2016. URI. https: / httt:pp://procceee /ptp///eoiii.coccocccoooccocc.cc ngs. neurips.ccommm httppps..cppppppee pac//apper/00 6/ hash// 9d2682367c3935deffoll
www.ddbbsttttt....ooeoo..o....ee html.
Úrsula Hiébert-Jhhsoon, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibra- tion: Calibration the campuutationally-ddnnfiinn masses. Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsn, Stockholm, Sweden, Jul 10-15. 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1944-1953. PMLR, 2018. URL http:/ /pwpeediicgg..... mlr. h....pres//vee httpa/ebeejtonsseeeeee Stm....
Badr Youbi Idrissi, Martin Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst-group-accuraacy In Conference on Causal Learning and Reasoning, pp. 336-351. PMIRR, 2022.
11

---

Published as conference paper ICLR 2023
Jivat Neet Kaur, Emre Kiciman, and Amit Sharma. Modeling the data-generating process is nec- essary for out-of-distribation generalization. In ICML. 2022: Workshop Spurious Corre- lations, Invariance and Stability, 2022. URL https:://ppeereeeeee
forum?id=
KfR7QnuseT9.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, Christos Thrampoulidis. Label- imbalanced and sensitvee classification under overparameetriiztion.. Advances in Neural Information Processing Systems, 34, 2021.
Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re-training is suffi- cient for rohustness to spurious correlations, 2022. URL httph: wwwpwiioorg/bba..eo
02937.
David Krueger, Ethan Caballero, Jörn-Henric Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang. Rémi Le Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex). In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Inter- national Conference
Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, vol- ume 139 of Proceedings of Machine Learning Research, pp. 5815 5826. PMLR, 2021. URL http:/ / /ptppeeeeiggg....//. . wells.pres//eee vv1 kww.kereeeeeaaa htmll
Ananya Kumar, Tengyu Ma, Percy Liang, and Aditi Raghunathan. Calibrated ensembles can mit- igate accuracy tradeoffs under distribution shift. James Cussens and Kun Zhang (eds.), Pro- ceedings of the Eiitt- Conference on Uncertainry in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pp. 1041-1051, PMLR, 2022. URL https: / //proceed ngs.ggmmm ml ..ress vv1 80 60/ /'cumar cumar22a. html.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam R. Kosiorek, Scungjin Choi, and Yee Whye Tch. Set transformer: A framework for attention- baaee permutation-invante
neural networks. In Kama- lika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Confer- ence Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, vol- ume 97 of Proceedings of Machine Learning Research, pp. 3744-3753 PMLR, 2019. URL http:/ / proceeedingg mlr. press / Lese 9t.html
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 624-639, 2018.
Yong Lin, Hanze Dong, Hao Wang, and Tong Zhang. Bayesian invariant risk minimization. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16021- 16030, 2022.
Yiping Lu, Wenlong Ji, Zachary Izzo, and Lexing Ying. Importance tempering: Group robustness for overparameteriized models. ArXiv preprint, ahs/2209.08745, 2022. URL htt.thtttt//ttttii org/ orggabs//200 2009 08745.
Maggie Makar, Ben Packer, Dan Moldovan, Davis Blalock, Yoni Halpern, and Alexander D' Amour. Causally motivated shortcut removal using auxiliary labels. In International Conference on Arti- ficial Intelligence and Statistics, pp. 739- 766. PMLR, 2022.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invari- networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Mackine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, Cali- fornia, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4363-4377 PMLR, 2019. URL http: http///rrceeddeeee//e .aag.smmm....
/ /maaaaaaaa ron .t..sla...mm....m.... html..
Aditya Krishna Menon, Ankit Singh Rawat, and Sanjiv Kumar. Overparameterisation and worst- case generalisation: friend or foe? In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:// openrevies net wtt.ooormmiioo indummid-ii wdw.omnidd-phhhoooooo. Jpw..oowe36....
Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of-distribation generalization. In 9th International Conference on Learning Rep- resentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openrev/ ew. net. wwr.mrrrmmimm/mmm i d- FSSTDNENTT b.
12

---

Published as conference paper ICLR 2023
Advait Parulekar, Karthikeyan Shammugam, and Sanjay Shakkottai. Pac generalization via invariant 151 96.
representations, 2022. URL https: :/a http//awww...g.aaa/////
F. Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, Grisel, Blondel, Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, Brucher, M. Perrot, and E. Duchesnay. Scikít-lcam: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Jonas Peters, Peter Bühhmann,, and Nicolai Meinshausen, Causal inference by using invariant pre- diction: identification and confidence intervals. Journal of the Royal Statistical Society. Series B (Staristical Methodology). pp- 947-1012, 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Flavien Prust, Hai Qian, Qiuwen Chen, Ed H Chi, Jilin Chen, and Alex Beutel. Toward better trade- off between performance and fairness with kemel-bbased distribution matching. ArXiv preprint, abs/1990.11 1779, 2019. URL https: / /arxivv.... .rgg abs /1910. 11779.
Aahlad Manas Puli, Lily Zhang, Eric Karl Oermann, and Rujesh Ranganath. Out-of-distribution gencralization the presence of nuisance-induce spurious correlations. International Con- ference on Learning Representations, 2021.
Alexandre Rame, Corentin Dancette, and Matthicu Cord. Fishr: Invariant gradient variances for out- of-distribution generalization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabuto (ods.), Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings Machine Learning Research, pp. 18347-18377. PMLR, 2022. URL https:: http///ooeeeigg.... mlr. www.prree........m.......mmmm..e wrw.srressse..... /aaass/v66.. www.eaa...... hhmml.
Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk min- International Conference on Learning Representations, ICLR 2021, Viruual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:://ppereee .w..teeeieeeeeeeeeeeeeee... forum? BB11--NNN-VVP---5
imization.
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. Domain-adjusted regression or: Erm may already learn features sufficient for out-of-distribution generalization, 2022. URI https:
//arxiv. org/ abs 220.222222222222222 06856.
Saharon Rosset, Ji Zhu, and Trevor Hustie. Margin maximizing loss functions. In Sebus- tian Thrun, Lawrenee K. Saul, and Bemhard Schölkopf (eds.), Advances in Neural Infor- mation Processing Systems 16 [Neural Information Processing Systems, NIPS 2003, De- cember 8-13, 2003, Vancouver and Whistler, British Columbio, Canada), pp. 1237-1244. wwwp::/w...euuurs..c.....o
MIT Press, 2003. URL https:/ 0fe473396244 (22777222222222235255522
Abstraat..
Mark Rudelson and Roman Vershynin. wanson-wright incquality and sub-gaussian concentration. Electronic Communications in Probability. 18:1-9, 2013.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In 8th International Conference on Learning Representations, ICIR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL https: /tttppp:///penrviee. net/forumm? d- FVS...J
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterizatton exacerbates spurious correlations. In Proceedings of the 37th International Conference on Machine Learning, ICML. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 8346-8356. PMLR, 2020b. URL http:// proceedi nga.mlr www.ss/pes//vll 3/sagawa20a.aa... html.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. In Samy Bengio, Hanna M. Wal- lach, Hugo Larochelle, Kristen Grauman, Nicolò cosa-Bianchi, and Roman Gamett (cds.), Ad- vances in Neural Information Processing Systems 31: Annual Conference on Neural Informa- tion Procesing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréol, Canada, pp-
13

---

Published as conference paper ICLR 2023 2023
5019-5031, 2018. URL www.eo44aaaaaaa4aeaaeaa
84 Aea-Abbttratt.html.
Ohad Shamir. The implicit bias of benign overfitting. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference Learning Theery, volume 178 of Proceedings Ma- chine Learning Research, pp. 448-478. PMLR, 2022. URL https: http///oocceeegeeeeeeeeee press/ /v17///111 77 /ws.maaa22222 html.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, and Nathan Srebro. The implicit bias of gra- dient descent on separable data. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: http///ppeeeiiieeeeeeeeeeeeeeeee net
Adarsh Subbaswamy, Peter Schulam, and Suchi Saria. Preventing failures duc datasct shift: Learning predictive models that transport. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference on Artificial Intelligence and Statistics, AISTAIS 2019, 16- 18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Re- search, pp. 3118-3127. PMLR, 2019. URL http:/ httpp/pporeenn...e/eeeep .mw.eeeddinnnm..r.......mmm..m.. mlr. wtt.gss.m..........e.mmm press paress/vene / subbaswamyl 1 html.
Adarsh Subbaswamy, Bryant Chen, and Suchi Saria. A unifying causal framework for analyzing dataset shift-stahle learning algorithms. Journal of Causal Inferenee, 10(1) 10(1):64-99 2022.
Baochen Sun Kate Saenko. Deep coral: Correlation alignment deep domain adaptation. In
European conference on computer vision, pp. 4p.4433-45 443-450. Springer. 2016.
Victor Veitch, Alexander D' Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invari- ance to spurious correlations in text classification. A. Beygelzimer, Y. Duuphin, P. Liang. and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL net watee//frrmm/am forume wtw.ormmmmdddd0000000
Akshaj Kumar Veldanda, Ivan Brugere, Jiahao Chen, Sanghamitra Dutta, Alan Mishler, and Sid- dharth Garg. Fairness via in-processing the over-paraaetterized regime: A cautionary tale. ArXiv preprint, htnn/2206.148553 2022. URU./rtsss///arxxt..o//////e
14853.
Roman Vershynin. Introduction to the non con-asymptotic analysis of random matrices, pp. 210-268.
Cambridge University Press, 2012. doi: 10.1017/CB097805) 0700005111994.000000 006.
Yoav Wald, Amir Feder, Daniel Greenfeld, and Shalit. On calibration and dum-o-- gener- alization. Advances in neural information processing systems, 34:2215-2227, 2021.
Haoxiang Wang, Haozhe Si, Bo L.,, and Han Zhao. Provahle domain generalization via invariant- feature subspace recovery. Kamalika Chaudhuri. Stefanie Jegelka, Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 23018-23033. PMLR, 2022. URL https::/p//.......... / / pwwceedi seceeediingg..
www.mmr.....................mwmm .mw. wtt..mr...p.ss//..mmmmmmmmmm vv 22//wan22xx. html.
Wang and Christos Thrampoulidis. Benign overfitting binary classification of gaussian mix- tures. In ICASSP 2021-202. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4030-4034. IEEE, 2021.
Alexander Wang, Niladri Shekhar Chatterji, Saminul Haque, and Tatsunori Hashimoto. Is importance weighting incompatible with interpolating classifiers? In NewrIPS 2021 Work- shop on Distribution Shifts: Connecting Methods and Applications, 2021. URL https: / //ppenreview..e net / / Eorum? 1d=pEapLxVsd033.
Robert C. Williamson and Aditya Krishna Menon. Fairness risk measures. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6786-6797. PMLR, 2019. URL http: http:////ccceeeee..//// ml v. press//ss/......... / /s 11 amson 9a. h.
14

---

Published conference paper ICLR 2023
John R Zech, Marcus A Badgeley. Manway Liu, Anthony B Costa, Joseph Titano, and Eric Karl Ocrmann. Variahle generalization performance of deep learning model to detect pncumonia in chest radiographs: cross sectional study. PLoS medicine, 15(1 (((1)0e100268, 2018.
Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Understanding why generalized reweighting does not improve over erm. ArXiv preprini, abs/2201.12293, 2022. URL ht https:
//arxiv. orgg http:/aa/22220 2ttp://21..1222221
Jianyu Zhang, David Lopez-Paz, and Leon Bottou. Rich feature construction for the optimization- generalization dilemma. Kamalika Chaudhuri, Stefanie Jegelka, Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (cds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 26397-26411. PMLR, 2022. URL htw.s:ttt////....m. http//pcceee oceed ngs. m1 w.w.sp/////e.. 62/ 2///g2ann222... html..
Xiao Zhou, Yong Lin, Weizhong Zhang, and Tong Zhang. Sparse invariant risk minimization. In International Conference Machine Learning, pp. 27222-27244, PMLR, 2022.
15


Reviews:
[{"review_id": "mBLlh6DL6W", "reviewer": "Reviewer_p2tP", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 paper demonstrates that interpolation and invariance are fundamentally at odds in overparameterized learning via constructing a linear two environment problem. Specifically, the authors demonstrated that in the constructed learning problem, any interpolating linear model with a positive margin cannot robustly have good out-of-distribution generalization. In contrast, the authors can construct an algorithm (to a certain extent, specifically designed according to the nature of the constructed problem) that is guaranteed to produce robust linear classifiers.\n\n", "summary_of_the_review": "By constructing an example problem, this paper introduces an interesting observation about interpolation and invariance in overparameterized linear classification. However, the significance of the result and the impact of the constructed example problem need a further demonstration. ", "strength_and_weaknesses": "Strengths: \n\nThis paper points out an interesting trade-off between achieving interpolation and invariance. \n\nThe authors back up their theoretical claims with convincing simulations.\n\nThe paper is well-written and has rigorous proof.\n\nWeaknesses:\n\nTheorem 1 only proves the existence of certain particular values of $r_c,r_s, d, \\sigma, \\theta_1,\\theta_2$. This makes the result relatively weak. In addition, although the idea introduced in the paper is interesting, the constructed learning problem seems \"unfair\" for standard learning methods. For example, if $\\theta_1,\\theta_2$ are both positive, then when faced with this particular linear two environment problem, any reasonable learning algorithm without additional prior knowledge should try to learn both $\\mu_c$ and $\\mu_s$ -- given only the training data set generated based on positive $\\theta_1,\\theta_2$, who would possibly know that in a new test task the corresponding $\\theta$ could be negative? \n\nOn the other hand, it is fairly easy to construct algorithms such as Algorithm 1 by utilizing \"hidden knowledge\" that:\n1. In a new test task the corresponding $\\theta$ could be negative;\n2. $\\mu_c$ is \"robust\" while $\\mu_s$ is not;\n3. $r_c$ and $r_s$ are different.\n\nTherefore, the significance of the result is questionable. \n\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YZZGBArCrY", "reviewer": "Reviewer_aRur", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the generalization of interpolating models under distribution shift by focusing on a linear classification problem.  They consider a source distribution that can be interpreted as a `two environment' distribution, and define a notion of `robust error' that measures generalization on a (family of) target distribution(s).    They show that there exist learning rules which can achieve good robust error, but any interpolating rule will have bad robust error.  They verify their results with experiments.  However, I believe there are issues with their setup that I am not sure can be fixed easily. ", "summary_of_the_review": "~~I think some of the central claims in the paper are not supported by the evidence provided by their work.  In particular, the theory setup relies upon a mixture of source distributions and the notion of a \"spurious\" feature, but the setup seems to imply that this feature is not spurious but is actually the dominant, useful feature.  If I have mis-understood something, I am happy to reconsider my opinion.  ~~\n\n\n==== post discussion with other reviewers ====\nI met with other reviewers and the AC to discuss the paper.  \n\nOn the one hand, my fundamental criticisms still stand: if one considers a distribution with a large core feature and a small spurious feature, most natural algorithms will fail to be invariant in the sense the authors describe, and it appears previous work has indeed shown that in similar settings natural ERM-based algorithms will fail to be invariant.  Thus, it is not surprising that interpolating models will exhibit the same failure to invariance, and it isn't clear what insight this provides into the phenomenon of interpolation: previous work on benign overfitting (and classical statistical learning theory) has established how brittle interpolating models can be even for within-distribution generalization.  \n\nOn the other hand, it appears some machine learning practitioners may have taken from the 'benign overfitting' results that interpolation is not only something that can be sometimes ok, but is something that should be encouraged.  This work then clearly shows that, in at least the setting of high-dimensional gaussian class-conditional distribution with large  spurious features, interpolation precludes invariance.  \n\nIn summary, although I believe this work is borderline, I would be fine if the AC/PC accepts the paper.", "strength_and_weaknesses": "\nUnderstanding the benefits and pitfalls of interpolation is an important research question.  It is worthwhile to try and develop insights by the study of simpler models, like the linear models considered in this work, and to then translate and verify these intuitions into more complex neural network models.  I quite liked the authors' attempt at studying overparameterization by using ResNet baseline features that are then mapped into a higher-dimensional space via random features.  This provides a novel way of introducing overparameterization that is attractive due to its ease of computation.  I'm unsure if this approach had been introduced before (can the authors comment?), but I liked it. \n\nHowever, I found serious problems with the framing and interpretation of the setup and of the results in the paper.  In particular, the claim that \"interpolation is at odds with invariance\" does not seem to be supported by the theoretical setup they showed.  In the proof, they consider theta_1=1 and theta_2=0, so that the source distribution is a mixture of two components: (1) Gaussian mixture with mean y(mu_c + mu_s), and (2) Gaussian mixture with mean y mu_c.  They assume that ||mu_s|| >> ||mu_c||, and show that an interpolator on the source data will rely more upon mu_s than upon mu_c, and that this causes the \"robust error\" to be large because any reliance upon mu_s increases the \"robust error\".  There are a number of problems with this setup:\n\n(W1) If ||mu_s|| >> ||mu_c||, it isn't clear to me why we should think of mu_s as \"spurious\": it is the dominant feature for data that comes from N( y(mu_c + mu_s), sigma^2 I).  And as the authors mention in the second-to-last paragraph of Section 2, the relationship of ||mu_s|| to ||mu_c|| matters much more than the number of samples from each environment in the overparameterized regime, so large ||mu_s|| really is the determining factor.  Because of this, I don't believe mu_s is really a 'spurious' feature: it is the most important feature for the setting considered. \n\n(W2) The definition of \"robust error\" seems odd in light of point (1).  The error gets worse if the learner relies on mu_s at all, but this doesn't make sense if we think of mu_s as an important feature.  ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SNoaLPFQmD", "reviewer": "Reviewer_8afp", "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 proposes a neat observation for a simple linear overparameterized classifier for a simple \"linear two environment problem\": interpolating classifier and invariance property can not be achieved at the same time. The paper also presents an algorithm that is provably invariant in this simple setting while being a non-interpolating classifier. ", "summary_of_the_review": "I would vote for marginally above the acceptance threshold, given that there are minor issues that need to clarify (see above), and I am not in the best position to comment on the novelty aspect, although I find the paper self-explanatory. ", "strength_and_weaknesses": "Strength:\nThe idea of the paper is neat. The claims are in general well-supported.\n\nWeaknesses: \n1. For Theorem 1, why is the probability over the draw S? while the robust error is a deterministic function of w? I guess the S here refers to the space of possible N samples, not the set of data points, but please clarify. \n2. Please also clarify on the drawing of \\mu_s and \\mu_c in Part 3 of Theorem 1. The paper mentioned that both are uniformly distributed on a sphere, but they also need to be orthogonal -- is \\mu_s drawn from the subspace that is orthogonal to \\mu_c? Also, 65 in Theorem 1 seems to be a strange number, please clarify as well. ", "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": "BoUkc8PUku5", "reviewer": "Reviewer_7Zqk", "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 proves that, in a particular class of two-environment linear models containing both relevant and irrelevant directions, interpolation is incompatible with invariance (having low \"robust error\" as used in out-of-domain generalization, or also corresponding to fairness constraints).\n\nIt also proposes an algorithm, based on learning a fair/robust linear combination of predictors learned independently on each environment, can provably learn a predictor with low robust error, and shows that it works reasonably well both in the setting to which the theoretical bounds apply and also for a linear model on pretrained features for Waterbirds, where – unlike previous approaches – it does (slightly) reduce the FNR gap past the interpolation threshold.", "summary_of_the_review": "This paper has two main contributions: one theoretically establishing a conflict between interpolation and invariance, and one suggesting an algorithm and showing it works in this theoretical setting as well as some very limited empirical results.\n\nThe first contribution is unsurprising; working out the details is valuable, but I'm not sure the way the paper is currently written that casual readers will come away with the right idea about \"how often\" this holds, etc.\n\nThe second is more surprising, but somewhat under-evaluated, as described above.\n\nOverall, I think the point of the paper is important – interpolating settings are major flaws in current approaches to invariant learning, as has been noted before e.g. in the discussion of the IRM paper – but I'm somewhat unhappy with its framing and the thoroughness of its exploration and evaluation. I'm giving the paper a 6 because I think it matters and I think it's above the minimal bar for ICLR, but there's a hypothetical version of this paper with some more work that I would be far more excited about.", "strength_and_weaknesses": "Strengths:\n\n- The explicit incompatibility between interpolation and robustness in a specific setting is good to have worked out.\n- The fact that Algorithm 1 works on one particular problem setting is also good to know.\n- Based on one experiment, the algorithm seems like it might be somewhat effective in (linear) interpolating regimes, where previous invariance approaches such as IRM totally fail.\n\nWeaknesses:\n\n- The parts of the main theoretical result that aren't about the algorithm seem to be unsurprising; see below.\n- This means Algorithm 1 is relatively more important to the overall quality of the paper. But Algorithm 1 is a little bit underexplored:\n  - It's only defined for two environments (though there's an obvious extension to more)\n  - It's only theoretically analyzed in one quite-restrictive setting\n  - It's only empirically analyzed for:\n    - a small number of instances of that restrictive setting,\n    - and one relatively-unrealistic real-data experiment, where empirical results do show some ability to do _something_ in the interpolating regime, but at quite a high cost (see below).", "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": "6zMfCCPryq", "reviewer": "Reviewer_VPKR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 studies a setting with two environments from a specific instance of the model from Rosenfeld et al. and show that overfitting (i.e., interpolation of the training data) and invariance to the spurious features are fundamentally at odds, and that while both are achievable, they cannot be done simultaneously. They then propose an algorithm which learns to make invariant predictions based on these two environments.", "summary_of_the_review": "See above", "strength_and_weaknesses": "**I like this paper, and I think it is well-written. There are some non-insignificant weaknesses, but overall I am in favor of acceptance. But, there are some changes/missing discussion I would like to see.**\n\nThe primary theorem is asking a really interesting question, and I think the result, while not too surprising, is valuable. Actually, what I find more surprising is the fact that the data is linearly separable at all with the chosen parameters (high dimensions are weird! I had to simulate this to convince myself that it was true). Generally, and along the same lines, I think this work would significantly benefit from a high-level description of the proof and giving an overview of the general order of the parameters that are necessary to make the proof work. Seeing \"there exist parameters a, b, c\" without a sense of scale feels extremely unsatisfying and sometimes gives me the impression that the result may not be as interesting **(e.g., we could take $\\mu_c \\to 0$ and the result would be trivial, no?).** It also seems unusual to have the means be separated by a term which varies with N but is constant as a function of the dimension... I would appreciate an indication of how robust this result is to different ranges of the parameters, even if just an intuition. For example, what if we choose $\\theta_2 \\neq 0$? How small would it have to be for the result to still hold? What if $\\theta_1 \\in o(1)$?\n\nUnfortunately I think the second part of the paper is quite a bit weaker. First of all, the model studied here is a specific case of the model from Rosenfeld et al. where the spurious means are collinear. This is pretty unrealistic (I admit this is a bit subjective), but it also immediately suggests a trivial method for invariance: just do PCA on the features to identify the shared spurious subspace, then project it out. However, **this approach has already been suggested and studied for a more general model by two works [1, 2], which both show invariance with only two environments.** So the second half of the paper unfortunately is giving a weaker result than one that is already known. The proposed two-stage algorithm is a reasonable idea, and I appreciate the authors' efforts to acknowledge existing work which does similar things---but it would be helpful to specifically explain how this approach differs rather than just giving a long list of citations.\n\nIn summary:\n\n* The first half of the paper asks an interesting question and gives a very nice result, though it requires a pretty specific parameterization which I think needs to be clarified for an updated draft.\n* The second half of the paper is already known, though the slightly different algorithm and experiments do provide some value showing that this approach is reasonable. \n\nOn the basis of the first half of this work alone I think this paper should be accepted, and I think this work would be much stronger if the results there could be made more general or at least clearer.\n\n**One last note: Given the restricted setting of the theory, I think the title would be much more accurately stated as a possibility, such as \"can/may be/is sometimes fundamentally at odds\". As it is written it feels heavily overclaimed.**\n\n[1] Provable Domain Generalization via Invariant-Feature Subspace Recovery. Wang et al. '22\n\n[2] Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments. Chen et al. '21\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster