Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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).

It 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.
strength_and_weaknesses: Strengths:

- The explicit incompatibility between interpolation and robustness in a specific setting is good to have worked out.
- The fact that Algorithm 1 works on one particular problem setting is also good to know.
- 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.

Weaknesses:

- The parts of the main theoretical result that aren't about the algorithm seem to be unsurprising; see below.
- This means Algorithm 1 is relatively more important to the overall quality of the paper. But Algorithm 1 is a little bit underexplored:
  - It's only defined for two environments (though there's an obvious extension to more)
  - It's only theoretically analyzed in one quite-restrictive setting
  - It's only empirically analyzed for:
    - a small number of instances of that restrictive setting,
    - 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).
clarity,_quality,_novelty_and_reproducibility: ## Unsurprising that there exist problems where interpolation and invariance are at odds

Consider, for simplicity, rotating your problem so that $\mu_c = r_c e_1 = (r_c, 0, \dots, 0)$ and $\mu_s = r_s e_2 = (0, r_s, 0, \dots, 0)$.
Then your data distribution is
$$
y \sim \operatorname{Unif}\\{-1, 1\\}
\qquad
x \mid y \sim \mathcal N\left( \begin{bmatrix}y r_c \\\\\ \theta y r_s \\\\ 0 \\\\ \vdots \\\\ 0 \end{bmatrix}, \sigma^2 I_d \right)
\tag{A}
.$$
In the main motivating setup of your paper, you'd like there to exist a large-margin separator for this problem, and moreover for it to exhibit benign overfitting, i.e. to have low generalization error.

In the main motivating setup, you'd also like for there to _not_ be an invariant large-margin separator, which is exactly the question of there not existing a large-margin separator for the $(d-1)$-dimensional problem
$$
y \sim \operatorname{Unif}\\{-1, 1\\}
\qquad
\tilde x \mid y \sim \mathcal N\left( \begin{bmatrix}y r_c \\\\ 0 \\\\ \vdots \\\\ 0 \end{bmatrix}, \sigma^2 I_{d-1} \right)
\tag{B}
.$$

That this situation can occur is a large part of the results of your paper (the other part being everything about Algorithm 1).
Intuitively, though, it's clear when framed like this that this is possible – if (A) is "right on the boundary" of having a separator of a given margin, and $\theta r_s$ isn't too small, then (B) won't.

(I don't know offhand of previous results that establish the achievable margin for (A) or (B), but they're _almost_ addressed by the far more general results of section 6 of the (concurrent) paper [Zhou et al. (2022)](https://arxiv.org/abs/2210.12082), who only study Gaussian $x$ but I believe can be extended to handle $x$ being a mixture of a small number of Gaussians fairly straightforwardly, and then show both a margin bound and conditions for benign overfitting in the squared hinge loss.)

All of this is only about the existence of any high-margin separator. Maybe this was in e.g. Rosenfeld et al. (2020) or Nagarajan et al. (2020) and I don’t remember (in which case you should recap the results here), but it would also be good to understand what particular algorithms – especially the max-margin separator – do in situations like this one: how much weight do they put on $\mu_s$? We'd expect that even when there exist invariant interpolators, the max-margin separator will still put a lot of weight in the "bad" direction $\mu_s$ (since it doesn't know it's bad).

## Experimental results

For the simulations, the experiments are fine and show that your algorithm works in the case it was designed for, although it'd be nice to also see maybe the test accuracy vs $d$ for a value of $\theta$ or two. I'm also especially wondering whether having a $\theta = 0$ environment is very important to the qualitative nature of your results, since it will presumably put very little weight towards $\mu_s$, and then the fair learning step will likely mostly just use that predictor since it's naturally going to be nearly fair. Does something similar happen if you have a $\theta = 1$ and $\theta = 0.5$ environment?

For Waterbirds: these results do indeed show that the test FNR gap is decreased by the regularizer even for high $d$, which is good! The amount of improvement there is fairly small, though, and the problem somewhat contrived. I'd be interested to know if this holds up if there are more than two training environments, if the individual-environment predictors are not themselves linear, and so on.

Also, almost all of the improvement in test FNR gap is achieved by "Ours ($\lambda = 0)$", indicating that the vast majority of the added invariance of your method comes from combining predictors learned on each environment separately. (I'm not aware of this scheme having been used previously in invariant learning, but it's closely related to some schemes in meta-learning-type areas, particularly [CAVIA](https://arxiv.org/abs/1810.03642) if only the "late-layer" parameters are task-specific, and also multiple kernel learning where the kernels are themselves learned on related tasks as in [MetaMKL](https://arxiv.org/abs/2106.07636).) To understand this a little more, it'd be good to also see results for just $v = (1, 0)$ and $v = (0, 1)$, i.e. just using one or the other predictor, for test FNR in both environments, compared to the outcome of the fair learning.

## Miscellaneous small questions

- Why use $\lVert v \rVert_\infty = 1$ as the constraint in the second phase of Algorithm 1? Taking a convex combination of the $w$s might would feel more natural, but it also isn't obvious that any constraint at all is needed, other than I suppose inside the analysis.

## Typos, etc

- There are several uses of \citet that should be \citep, e.g. at the bottom of the first page.
- Section 5.1 setup: "we further fix $r_c =1$ and $r_c = 2$" – presumably the second one should be $r_s$ :)
- Many papers in your bibliography are cited as arXiv papers but were in fact published at conferences, e.g. I noticed Rosenfeld et al. (2020) and Nagarajan et al. (2020) which were both published at ICLR 2021. A tool like [rebiber](https://github.com/yuchenlin/rebiber) could catch all of those for you.
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.

The 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.

The second is more surprising, but somewhat under-evaluated, as described above.

Overall, 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: 
Understanding 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. 

However, 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:

(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. 

(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.  
clarity,_quality,_novelty_and_reproducibility: The work was fairly clear and, from what I am aware, novel.  There were a few points that could use additional clarity/clarification:

(C1) Theorem statement: presumably this should be gamma >, not gamma <, since it says 'lower bound'.  For part 3 of the theorem, presumably this gamma is not the same as the gamma in the theorem statement, since in the subsequent paragraphs you say that the result holds for classifiers with 'arbitrarily small margin gamma'.  I am assuming this refers to *only part 3 of the theorem*, since the theorem statement presumably requires a lower bound for gamma.    I was also confused if gamma was supposed to play a role in part 2 of the theorem -otherwise, it doesn't seem to appear anywhere?  
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.  ~~


==== post discussion with other reviewers ====
I met with other reviewers and the AC to discuss the paper.  

On 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.  

On 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.  

In summary, although I believe this work is borderline, I would be fine if the AC/PC accepts the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strength:
The idea of the paper is neat. The claims are in general well-supported.

Weaknesses: 
1. 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. 
2. 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. 
clarity,_quality,_novelty_and_reproducibility: Clarity and Quality: The paper is relatively easy to understand. However, I think adding a figure illustrating the linear two environments in a picture may help reader understand the problem setting much faster. 

Novelty: I am not very familiar with all relevant literature and to what extent the model setting here is reasonable / too simplified to all the researchers in the field. The paper does seem self-explanatory though. 

Reproducibility: My best guess is that the work should be reproducible. 
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.


strength_and_weaknesses: Strengths: 

This paper points out an interesting trade-off between achieving interpolation and invariance. 

The authors back up their theoretical claims with convincing simulations.

The paper is well-written and has rigorous proof.

Weaknesses:

Theorem 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? 

On the other hand, it is fairly easy to construct algorithms such as Algorithm 1 by utilizing "hidden knowledge" that:
1. In a new test task the corresponding $\theta$ could be negative;
2. $\mu_c$ is "robust" while $\mu_s$ is not;
3. $r_c$ and $r_s$ are different.

Therefore, the significance of the result is questionable. 


clarity,_quality,_novelty_and_reproducibility: The presentation of the paper is clear. The results are original and reproducible.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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.**

The 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)$?

Unfortunately 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.

In summary:

* 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.
* 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. 

On 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.

**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.**

[1] Provable Domain Generalization via Invariant-Feature Subspace Recovery. Wang et al. '22

[2] Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments. Chen et al. '21

clarity,_quality,_novelty_and_reproducibility: Quality: High
Clarity: General writing is great, the proof technique and specific parameterizations in the first theorem could be made much clearer.
Novelty: First half - excellent, Second half - already known
Reproducibility: Good
summary_of_the_review: See above
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This is an interesting paper that is not without notable flaws, as flagged by a majority of the reviewers. It sits at the intersection of two relevant contemporary topics: Benign overfitting and invariant learning. The reviewers consisted of experts on both sides.

On the one hand, the results are not at all surprising. There is no reason to expect interpolating classifiers to be invariant, and benign overfitting is a very specific phenomenon that is not believed to hold widely. In the discussion, reviewers agreed on this point. Moreover, the original title of the paper clearly oversold its contributions, and while the revised title ("Malign Overfitting: Interpolation Can Provably Preclude Invariance") is an improvement, it might be better to avoid the connection with "benign overfitting". Overall, the paper would still benefit from tempering its claims; here are two such examples:

- The results are not "_even_ in the simplest of settings", but in fact in a very specific setting. It is not clear if any of this generalizes, and if it does, this should be formalized.
- The authors do not show that "interpolating models are _fundamentally_ less invariant than non-interpolating ones", but again, only in a very specific setting.

On the other hand, the paper accomplishes two important goals, although they have may not been the originally intended goals: 1) It provides an interesting perspective on two important problems, which will hopefully lead to fruitful dialogue between the communities, and 2) Proposition 1 on the information-theoretic impossibility of interpolators to be invariant seems to be novel and a nice contribution to the literature. Again, reviewers agreed on these points.

Ultimately, although some reviewers expressed valid reservations, after discussion there was a weak consensus to accept this paper. Ideally, the authors will temper their claims and qualify their results with the fact that benign overfitting is not expected to hold universally.
justification_for_why_not_higher_score: Results are not surprising although the framing of the paper suggests otherwise, some overclaiming that should be addressed
justification_for_why_not_lower_score: Consensus amongst reviewers that the problem is interesting and could lead to additional theory and applications down the line
Decision: Accept: poster