Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies the problem of learning with spurious correlations whose correlation with labels can change between the training and test distributions. They propose to regularize the algorithm with a new regularizer called Conditional Spurious Variation (CSV) which essentially measures the difference in loss values over different groups. They show that the Out of distribution (OOD) error can be upper bounded by the in distribution error + CSV term. They also show improved performance on many benchmark datasets. 

strength_and_weaknesses: The paper studies an important problem which has gained widespread interest in recent years. I have a few concerns which I mention below.

The invariance assumption of the model being conditionally independent of the spurious attribute given the label, how is it different from Conditional domain adaptation [1] which matches the feature distribution given the labels and the domain. It seems like the same assumption is used here. 

This work lacks important citations and comparisons. They state that they can even estimate their CSV without ground truth group values but there already exists approaches which work without the ground truth labels [2,3,4] but many of these works have either not been cited or compared with . It would be good to have these comparisons included and also say what is different about their approach.

The empirical results are marginal. This algorithm improves the accuracy by a small amount on worst groups but reduces the average weighted performance on all the datasets. Hence, it is not clear if they are actually getting rid of the spurious feature or just trading some of the majority group accuracy with the minority group. 

It is also not clear how different this approach is from the group distributionally robust approaches which also try to reduce the gap between losses across different groups. 

I am also wondering whether the authors needed to regularize their models as well to make this method work because the authors in [5] claim that if there is no regularization, these overparameterized methods fit well on all the groups in the training set and hence, there is no effect of distributionally robust optimization.

[1] Conditional Adversarial Domain Adaptation
[2] No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems
[3] Just Train Twice: Improving Group Robustness without Training Group Information
[4] Environment Inference for Invariant Learning
[5] DISTRIBUTIONALLY ROBUST NEURAL NETWORKS FOR GROUP SHIFTS: ON THE IMPORTANCE OF REGULARIZATION FOR WORST-CASE GENERALIZATION
clarity,_quality,_novelty_and_reproducibility: Some of the writing in the paper could be improved. This work has ideas very close to existing ideas and the differences are not adequately discussed.
summary_of_the_review: 
The paper is missing important comparisons and citations. The empirical performance is also incremental.

****************

I have read the authors' response and they have sufficiently addressed all my concerns regarding comparisons with prior work and empirical contributions. I have also changed my recommendation accordingly.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose an approach to training models that are robust to correlation shifts, where the correlation between a label and a spurious attribute changes between training and test distributions, but the generative model given label and spurious attribute and the label distribution does not change. The authors argue that under such correlation shifts, constraining the predictor to be conditionally independent of the spurious attribute given the class label yields a risk invariant predictor. They propose a regularizers that upper-bound the risk difference between distributions. They argue that independence constraints yield a favorable generalization gap. They show that such an objective can be optimized at a favorable rate.
strength_and_weaknesses: Post-Rebuttal:

I am raising my score to accept, but with some additional suggestions for the authors.

 + The authors did a better job of connecting their problem formulation to previous work in the revisions. I would encourage the authors to also note that the content of the analysis in Makar et al 2021 is very similar to the analytical approach of this paper, including the way that the OOD generalization bound is constructed. I do think that the approach in this paper greatly streamlines those arguments, and relaxes some assumptions.
 - The proof of Theorem 1 still seems unnecessarily complicated, especially given my comment before that (39) is vacuous since the LHS and RHS are symbolically equivalent. Note that if you show $P(f(X), Y) = Q(f(X), Y)$, this implies that $P(Y | f(X)) = Q(Y | f(X))$, so the first half of the proof is unnecessary given the second half.
 - Given the presentation in the rest of the paper, Theorem 3 is still extremely difficult to motivate and parse parse. It is not clear what "conditional independence does not contradict in-distribution generalization" means; is the goal to show that the generalization bound goes to zero as n goes to infinity? Something else? It is also not clear what, say $f_\theta \perp S_Z \mid S_Y$ means, given that $f_\theta$ is trained using $S_Z$. The framework for producing this generalization bound is also not introduced at all. Some framing would be useful here, as simply giving references is not sufficient. However, this theorem does not seem to be particularly crucial to the overall story of the paper. Since I would find the rest of the paper to be rather strong even if this section were deleted, I won't lower my score because of this, but if the authors want to continue to include this result, I would suggest heavy edits.

==========


Strengths:
 + The paper does address an important spurious correlation problem.
 + Some of the risk invariance arguments (once fixed up) could yield more streamlined versions of the arguments made in Makar et al 2021.
 + The CSV penalty seems potentially easier to implement (and has no tuning parameters) compared to the MMD penalties proposed in previous work, although the parallel mini-batching strategy with differing weights could potentially be difficult to implement in standard workflows.
 + Empirical performance on standard benchmarks is compelling.
 + The CSV_U regularizer when no spurious variables are visible is a major contribution.

Weaknesses:
 - The paper's development is extremely similar to [Makar et al 2021, AISTATS](https://proceedings.mlr.press/v151/makar22a.html), which is not cited. There is also additional concurrent work building on Makar et al that makes a more explicit connection to conditional independence regularization [Makar and D'Amour 2022](https://arxiv.org/abs/2209.09423). It would be absolutely necessary to contrast against Makar et al 2021, and show how developments in the current paper go beyond what was shown in Makar et al. For example, the correlation shift is identical, as is the goal to find a predictor with invariant risk, and there is also a similar argument about the generalization gap. There are some aspects of this paper that are new, e.g., the setting is slightly more general in that the risk invariance result does not require the existence of a sufficient statistic, and the CSV penalty here differs from the weighted MMD penalty suggested in Makar et al 2021. **IMO, the paper needs some major reframing in light of these similarities.**
 - Similarly, there needs to be more discussion of the relationship between the CSV penalty and the conditional MMD penalty given here and the conditional MMD penalty suggested in Veitch et al 2021 (cited in the paper).
 - The proof of Theorem 1 does not really make sense. For example, equation (39) is vacuous as written (the final expression is symbolically equivalent to the LHS). There is an obvious way to improve this. You want to show $P(f(X), Y) = Q(f(X), Y)$ under the given assumptions. This follows from $Q(f(X), Y) = P(Y) \int_{\mathcal Z} P(f(X) \mid Y, Z=z) dQ(z | Y) = P(Y)P(f(X) \mid Y) \int_{\mathcal Z} dQ(z | Y)$, where the first equality follows from the correlation shift assumption, and the second equality follows from the $f(X) \perp Z \mid Y$ assumption.
 - Lemma 1 is incorrect. Consider the counter-example: $U = W$, $V = -W$. Then $I(W; U+V) = I(W;0) = 0$ but $I(W; U) = H(W) \geq 0$ (and $I(W; V | U) = 0$). The change of variables from U+V to (U,V) is done incorrectly in the proof; the domain of integration would need to change.
 - I have difficulty parsing Theorem 3. It is not clear what the mutual information term involving $\theta$ means. The proof references a distribution over $\theta$, which does not make sense to me. Similarly, Theorem 3 relies on the incorrect Lemma 1. Also, $M$ is not defined.
 - The prose around Theorem 3 seems to argue that there is no tradeoff between robustness and in-distribution prediction performance, which is not the case in general. In fact, at best, the theorem would indicate that the generalization **gap** between the empirical risk and population risk is small, but says nothing about whether the minimized population risk subject to the conditional independence constraint is small (which is what I might interpret as "generalization capability"). 
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear and high quality, although a number of theorem statements and proofs have issues. The main issue here is novelty, as the problem formulation has been given before. Some aspects of the paper are nice contributions, but probably require major reframing. Experiments and algorithms are described in nice detail, especially in appendices.
summary_of_the_review: Post-Rebuttal: The authors addressed my concerns sufficiently. See comments above in "strengths and weaknesses".

===============

I think the paper needs a major rewrite in light of prior work. Many of the technical results constitute a nice contribution, but the paper would need to be reframed to highlight them.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the case of learning under presence of spurious attributes, which are correlate with labels, and make the train and test distributions different. It begins with a criteria, (3), for measuring independence of prediction function and the spurious attributes. Then replaces with an upper bound as the identity of such spurious will not be known (10). Simulations show improvement wrt. existing OOD baselines.
strength_and_weaknesses: Strength:
1. Overall, the paper is well-written with nice organization.

Weakness:
1. though the motivation, various justifications make sense, I feel the final proposal i..e, (10) is over-restrictive. For e.g., why not perform sparse feature selection etc. to eliminate the spurious features. For resultant predictions, clearly (10) is restrictive, while they will alleviate the issue of spurious correlations?
2. Even in simulations I think simple baselines that perform feature selection are very important for understanding the usefulness of the proposal. Also, since a plethora of diverse methodologies for feature selection exist, this may make the baseline very competitive.

clarity,_quality,_novelty_and_reproducibility: clarity:
overall the paper is well-written and easy to understand

Quality:
While the proposal in observable case is straight-forward (why not use direct ways of measuring conditional independence than via (3)?), the proposal in more pratical case of unoservable suprious correlation seems restrictive making the contribution less strong.

Minor:
Also I prefer avoiding associating spurious features with non-causal features. because one can have anti-causal learning that is not spurious.


summary_of_the_review: In view of the issues desribed above like over-restirctedness of (10) and missing comparisons with feature selection based methods, I tend to recommend a reject. 
]

____
After the rebuttal and discussion, my issues are resolved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the machine learning problems with OOD data (that is, out-of-distribution data). The paper models OOD data by introducing a new variable called spurious attribute, of which the conditional distribution is different across training and testing data. The paper proposes to use CSV (conditional spurious variation) as regularization term, so that the training process prefers stable output function against the change of spurious attribute distribution. Theoretical analysis is provided for different aspects of the CSV regularization.


=====================


After the discussion session, I believe that most of my concerns and the issues raised in other reviews are resolved. I am convinced that this is a solid paper that merits acceptance.
strength_and_weaknesses: Strength:
The idea of CSV-based regularization is promising and innovative.

Weaknesses
Below I list some possible mistakes or typos, most very easy to fix. I feel that "weakness" could be a word too big for these problems.
1. some terms may not be well known. I would suggest adding explanations. This includes: "domain labels"
2. paragraph 3 on page 3: what is the difference between "input's label" and "class label"?
3. I would suggest a comparison of the proposed condition with the condition in this paper:
Smale, Steve; Zhou, Ding-Xuan. Online learning with Markov sampling. Anal. Appl. (Singap.) 7 (2009), no. 1, 87--113.
For example, I see many works in the literature assuming the invariant of conditional distribution of labels instead. I am curious about the difference between this setting, and the setting used in the current paper.
4. Some small typos: "quantify" before Theorem 4 should be "quantifies";
5. Please define the big-O notation in Theorem 4. In particular, what is the limit process?
6. I hope that the author(s) can specify the definition of P, Q, X, Y, and Z, which I believe would greatly help the readers. In particular, I have the following questions directly related to the paper:
(a). Is "P" (and "Q") a distribution of (X,Y) or (X,Y,Z)?
(b). In general, X and Y are not independent. Are X and Z independent? Are Y and Z independent? Are (X,Y) and Z independent?
(c). If Z and Y are not independent, then Z has the prediction power on Y. Would this still fit the definition of "spurious correlation" in this paper?
7. In this paper the label set script-Y is discrete (Assumption 1). For the time being, let me assume the label set is just {0, 1}. Then the loss function script-L just assigns values for the set {(0,0), (0,1), (1, 0), (1,1)}. I think it does not make much sense to assume that L(u,y)=L(y) (the value depending only on y). I think it does not make much sense to assume in Assumption 2, that the parameter set Theta is disconnected and for any x, f_{theta}(x) depends on theta only through the connected component of the parameter set Theta. However, then there exist some x, y, theta1, and theta2 such that: theta1 and theta2 are path connected in the parameter space Theta (we skip the subtleties of path connected and connected spaces), f_{theta1}(x)=1, f_{theta2}=0, and L(1,y)!=L(0,y). But this would violate Assumption 2 because if we let theta travel along the path linking theta1 and theta2, at some stage f_{theta}(x) would jump from 1 to 0. Such a jump violates the Lipschitz continuity in Assumption 2, no matter how large L0 is.
So, Assumption 2 requires that the parameter space Theta is discrete and the distance of every pair of points uniformly bounded away from zero. As this is a very strong assumption for machine learning or statistics community, we suggest that this should be explicitly stated after Assumption 2. As a consequence, the Lipschitz smoothness of L in (6) is no longer necessary and should be removed.
8. Right after Theorem 4, I guess the expression "A decreases with B" is not clear: what is its precise meaning?
9. The definition (11) is confusing. It is obvious that when u runs through Delta_m, the maximum of u dot F is the maximum coordinate of the vector F. Why not directly use max-coordinate but employing Delta_m and writing (11) in the current complicated way?
10. Page 14, right after (17), how does one derive P_{X|Y}=Q_{X|Y} without assuming P_Z=Q_Z? Also in Example 1, all the numbers 0 should be -1.
11. I feel that the loss function in Example 1 is not designed properly. Indeed, L(1, -1)=3 while L(1, 1) = 4 is even larger. Also, the inequality (19) is derived based on the assumption that f(X)=1 almost surely, so the claim that (19) holds for any f is wrong. Even if we would like to cancel E[f(X)] with X|Y ~ Q or P, since the first term is conditioned on Y=1 and the second term is conditioned on Y=0, such cancellation is not doable in general.
12. Proof of Propsition 2: please provide section or page number when citing a book. In this proof however, since script-Y is discrete, one may simply choose A=Script-Y and there is no need to take supremum.
13. Equation (24) is wrong on the treatment of sup_{A in script-Y}.
14. Equation (25) is wrong. For example in the last equation, the left-hand side depends on y, while the right-hand side does not.
15. Proposition 2 is wrong. Obviously, since Q is in script-P, Q_Y=P_Y, so the only function w that achieves the minimum TV is a constant function w(y)=1, which makes the TV equal to zero.
16. In the proof of Proposition 1, the classifier does not fit the framework proposed in this paper. In particular, the first argument of the loss function script-L is defined on script-Y, a discrete space. However, the classifier here outputs a real number. I guess a reasonable solution is to change the definition of the loss function to accept real first argument (at the top of page 3). This change may help to resolve the issue on Assumption 2.
17. I think the first part of the proof of Theorem 1 does not work. We need to prove Q(Y|f(X))=P(Y|f(X)), but the current version of the proof still can not bridge to P(Y|f(X)). Please give explicit calculation that leads to this bridge.
18. I feel confused about the treatment around Equation (40). In particular, the set script-P of distributions only provide Q_{X|Y,Z}=P_{X|Y,Z}, and here it seems to me that one is using Q_{X,Z|Y}=P_{X,Z|Y}. Please provide more details for this proof.
19. My questions on Theorem 3 and its proof: is theta a random vector or a parameter? Seems neither way fits the proof. For the inequality "a", if all script-L stay close to M, then the log expectation term can not be bounded by O(1/n), is that right?
20. There is a general question I feel confused: is Z observed as data? If yes, then Z goes to learning process and we do not have the OOD problem. In the scenarios that the distribution P_{Z|Y} changes from training to testing, the boundary between X and Z may not be easy to specify, and therefore the CSV penalty is still not easy to define. On the other hand, I feel very difficult to imagine a case where Z is not observable but still needs treatment.

Due to the short review window, I have not checked the proofs of Appendix C.2 and later.
clarity,_quality,_novelty_and_reproducibility: This paper is written in a statistics style, and is clear and easy to follow. The proposed analysis and the idea of CSV (Conditional Spurious Variation) are novel and of good quality. Since the algorithm description is clear, I believe that the numerical results are reproducible. But it is clear that the main contribution of this paper is theory.
summary_of_the_review: This paper investigates an important machine learning problem of out-of-distribution data in a theoretical approach. The findings merit a publication. However, there are some mathematical problems -- probably just writing problems. I recommend a revision and would be more than happy to vote for a higher score after the above problem being resolved.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper investigates the problem of learning in the OOD setting in which certain spurious correlations between inputs and labels can change between training and test data. To encourage the predictor to learn the stable, i.e., non-spurious features, the paper proposes a new regularizer called Conditional Spurious Variation (CSV) which constrains the predictor to be conditionally independent of the spurious attribute given the class label. Since the CSV requires knowledge of the spurious features in the data, which is not the case in practice, the paper thus considers an upper bound of such quantity instead. The paper provides competitive empirical results compared to existing methods.

While the proposed idea is natural, intuitive, and coincides with existing work in the literature as pointed out by Reviewer bzT6, there is a consensus among the expert reviewers that this paper provides substantial contributions such that it deserves acceptance. After looking at the paper, reviews, and discussions between reviewers and authors, I mostly agree with the reviewers, but would also highly encourage the authors to incorporate some of the suggestions made by the reviewers into the camera-ready version. 
justification_for_why_not_higher_score: The idea is not totally novel and coincides with some of the existing work. 
justification_for_why_not_lower_score: There is a consensus among the expert reviewers.
Decision: Accept: poster