Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents parallels between algorithmic fairness and domain generalization literatures. The authors explore a learning setup where the goal is to learn some representation $\Phi(x)$ that is "independent" of some environmental variable $e$. The authors explore cases where $e$ is known or not and come up with some algorithms that draw connections between recent work on domain generalization, specifically invariant risk minimization (Arjovsky et al 2019) and fairness. The authors conclude the paper with three different examples addressing domain generalization and fairness. While the supporting experimental results are not very strong, the connections observed are interesting. I have several points for clarification that I detail below.

**Exposition.** While the introduction of the paper is written nicely and the ideas are communicated nicely, the mathematical exposition and presentation in this paper is not self-contained. For example, it is close to impossible for a reader to follow this paper without having read (Arjovsky et al 2019) and (Liu et al. 2018). I suggest that the authors expand on the mathematical exposition, defining all terms, and explaining different things came from, especially since the paper is supposed to have a broad audience across two communities.

**Convergence of Algorithm.** The proposed algorithm comes with no guarantees and I suspect it will not converge in a variety of situations, especially in cases where $C^{\text{IRM}}$ is nonconvex in (EIIL). Why would you need to run the inner optimization and outer optimizations to convergence each time? Have you tried a GDA version of the algorithm?

**Cost of the Algorithm.** The proposed algorithm is costly because IRM has to be solved multiple times before it converges. Can you please comment on the computational cost of the proposed algorithm as compared to ERM and other baselines in each experimental setup?

**Limitations of generalization-first fairness.** This section is nicely written and much appreciated.

**Choice of $\Phi_{spurious}$.** The algorithm is sensitive to initialization choice of $\phi_{spurious}$  as the authors also find with their Color MNIST experiments. In particular, there is a huge performance gap in Fig 1.b. for $\theta_y \in (0, 0.15)$ that needs to be addressed. On the other hand, the algorithm seems to work well in the severely overfitting regime where ERM can be thought of having learnt $\Phi_{spurious},$ as also discussed by the authors in the second paragraph of Section 3.2. However, the real world is not so black and white and hence this poses a severe limitation. Can you please explain?

**Connection with (Liu et al. 2018).** In the third paragraph of **Fairness** section in Page 4, the authors claim a connection between IRMv1 (btw, IRMv1 is misspelled as IMRv1 there) and (Liu et al. 2018). This connection is not obvious to me. Can the authors make it rigorous?
 
**Continuous $e$.** Can you please comment on how this setup may generalize to continuous $e$? At least can you please comment on the scaling of the algorithm with the cardinality of the set of environments?

**Theorem 1.** Unfortunately, Theorem 1 and entire Section 3.2 is only applicable to a severely unusual and overfitting case (similar to the Color MNIST example) where there is perfect correlation between the environment variable and the label. The fact that the algorithm works well in this situation is not surprising. The real world, however, is not black and white and the limitations of the proposed framework in real-world situations (similar to $\theta_y \in (0, 0.15)$ in Fig 1.b.) remain to be understood.

**Confounded Adult Dataset.** Please make it clear that this is constructed by the authors. I only understood that when started looking for the details in Appendix.

**Typos.** (1) In Eq. (2), $w\circ\Phi$ should be replaced with $w.\Phi$. (2). second paragraph of **Fairness** paragraph on Page 4, the word attribute is missing after "sensitive".

Overall, while the subject area of the paper is exciting, unfortunately, the execution (both empirical and theoretical) is weak. I tend to remain to vote for rejection with encouragement for a more thorough empirical and theoretical investigation of the problem.

---post rebuttal---

After reading the authors' response, the other reviews, and the revision to the paper, I find that my comments are not sufficiently addressed. The author did not even acknowledge the existence of the prior work, REPAIR, in the revised paper. The imprecise mathematical expressions are still in the paper despite feedback from multiple reviewers. From a practical point of view, the developed algorithm is not scalable as it requires to (almost) solve the inner maximization at each iteration (based on the rebuttal), and it only works in the significantly overfitting regime (the authors are yet to show its performance in a more interesting regime). From a theoretical point of view, the applicability of the theory is also extremely limited to the perfectly overfitting regime, which does not capture the real world. In addition, I agree with AnonReviewer4 that the proofs are inscrutable.  I regret to say that despite the fact that the subject area of the paper is exciting, I am adjusting my score to 4 post rebuttal.
review_title: Insightful paper but weak results

final_score: rating: 6: Marginally above acceptance threshold
review_content: The main contribution of the paper is to highlight the similarity between two active areas in ML namely "domain generalization" and "fairness". Further, the paper proposes an approach inspired by recent developments in the fairness literature for domain generalization. The high-level idea is that similarly to the way that fair algorithm are able to improve the worst-case accuracy of predictors across different groups without knowing the sensitive attributes, perhaps we can use these ideas to domain generalization when environment partitions are not known to the algorithm. In some sense, in both of these research areas the goal is to design robust algorithms. Similarly, the paper uses the idea from domain generalization to design fair algorithms w.r.t. a notion called "group sufficiency". The idea is to somehow infer the "worst-case" subgroup (i.e., the one that our algorithm has the worst accuracy on it) and then using a round of auditing improve the performance of the algorithm across all subgroups.

The authors have supported their approach with empirical evaluations. In particular, I find the result on CMNIST quite interesting where the new algorithm as opposed to the standard approach like ERM will not be fooled by the spurious feature and can infer the useful environment.     

While the paper has introduced (to best of my knowledge) a new concept, it seems that are many interesting questions that could show the applicability of the connection better are not yet answered (e.g., bi-level optimization EIIL). This could also help the paper to be supported with more provable guarantees. In general the paper is exploring a new connection between two areas and has shown its efficacy in practice and I believe it can lead to further works on this topic.   


Minor comments:
- define the notion of "group sufficiency" explicitly in the paper. I could not find the definition of the notion in words till in the caption of Figure 2 on page 8 and is formally defined on page 12!
-page 5: poorly. . Consider -> poorly. Consider
-page 6: generalizattion -> generalization
-page 7: graysacle ->grayscale
-page 14: exagerated -> exaggerated
-page 14: orginal -> original
-page 17: implicily -> implicitly
review_title: Interesting connection but could be supported with more theoretical guarantees

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### POST-REVISIONS ###
Thanks for the revisions made to the theoretical results. I still find parts of the discussion in Appendix F to be unclear. 

Firstly, how do you derive eq. (5) from eq. (4)? In eq. (4), the denominators \sum_i q_i are independent of "\Phi(x_i)", but in eq. (5), they have a dependence on \Phi through z_{i,b}. I think the change in normalization important to show the invariance principle holds (as the invariance principle requires a conditioning on each value \Phi takes), but am unable to follow your derivation.

Secondly, I'm not convinced that the maximizing partition for eq (5) assigns all examples with y=1 to one group, and those with y=0 to another group. Wouldn't the maximizing partition also depend on what \hat{y} evaluates to for those examples?

Overall, I'm able to see what the authors are trying to get at with this example, but unfortunately the revisions aren't sufficient to address all of my concerns regarding the theoretical results.
********************

The paper presents an approach for training models that generalize well to out-of-distribution (OOD) samples, particularly when the source of domain shift (e.g. spurious correlations or sensitive groups) is not known before hand. The paper combines ideas from two prior papers from the domain generalization and fairness literature: (i) invariant  risk minimization for OOD generalization (Arjovsky et al.) and (ii) adversarially reweighting for fairness without protected groups (Lahoti et al.). 
At a high level, the proposed approach seeks to minimizes the average classification loss across the worst-case partitioning of the dataset into two groups. Experimental results on datasets with synthetically generated spurious features show that the proposed approach is able to generalize better to OOD samples in the high noise regime, without having knowing aprior which features are spuriously correlated with the labels.

Pros:
- The question tackled is practically important: how one can generalize to OOD samples without knowing the exact source of discrepancy between train and test data. 
- The experimental results look encouraging

Cons:
- The paper lacks a clear theoretical motivation for the specific optimization objective that the authors end up using (eq 3). In particular, do we know (at least in some a simple setting) that maximizing this objective over soft-group memberships "u_i" will identify the partitioning of the data that maximally violates the Invariant Constraint? I elaborate on this next.

Relaxed training objective lacks strong theoretical backing:
The authors directly adapt the training setup of Arjovsky et al., where the goal is to train a model which learns the same conditional label distribution for any given input "x" across a set of known partitioning of the training data, dubbed as the invariance constraint . Each of these partitions, referred to as 'environments', represent a different training distribution, and the goal is to train a model that performs equally well across all of them. Arjovsky et al. show that for the special case of linear invariant predictors, the training problem can be relaxed into an unconstrained objective with a regularization penalty. 

The present paper extends the setup of Arjovsky et al. to problems where the environments are not a prior known, and seeks to minimize the average classification loss over a partitioning of the data that maximally violates the invariance constraint. However, they do not explicitly solve this optimization problem, and instead simply minimize the worst-case value of the "relaxed training objective" of Arjovsky et al. over all (soft) partitioning of the data.

Is the relaxation that Arjovsky et al. employ with known environments still relevant to your problem formulation, where you would like the invariance constraint to hold for all possible partitioning of the data?

At the very least, this requires a discussion. Ideally, it would be nice to see a derivation of the relaxation for some simple special cases: e.g. like Arjovsky et al., can you show that for linear predictors, "finding a partition that maximally violates the invariant constraint" is equivalent to "maximizing the relaxed unconstrained objective in eq. 3 over partitions"?

Other comments:
- Eq 3:  I think "w" is a scalar here (otherwise evaluating the gradient at w = 1.0 doesn't make sense). Please make that explicit and also provide some intuition for why this regularization penalty with a scalar "w" makes sense for your problem set up.
- I am not entirely sold on the general theme of this paper of exchanging lessons between fairness and domain generalization. The authors are definitely correct in crediting a prior fairness paper for the idea of  the idea of adversarially re-weighting examples with a soft groups model, but as they themselves point out this idea has existed in different forms in the domain generalization literature (e.g. DRO). So my reading is that the paper seems to slightly over-emphasize the connection to the fairness literature, but this is a personal take. Having said this, the paper does provide (in Sec 2) a nice literature overview of similar problems tackled by the domain generalization and fairness communities.
- In the color MNIST experiments, you observe "IRM(eEIIL) generalizes better than IRM(eHC) with sufficiently high label noise". If I understand correctly, IRM(eHC) has access to the true environments, whereas IRM(eEIIL) uses environments inferred from data. Wouldn't we expect the former method to have an advantage over the latter?
- Additional baseline: Would it make sense to compare with (a form of) DRO for the color MNIST task (e.g. ones cited in Table 2)?  You do mention in another experiment that Lahoti et al. compare with DRO for their particular fairness application, but do those observations also apply yo the tasks you consider in this paper.
- Iterative training: I think a natural extension of your approach (which you've probably already thought about) is to solve (EIIL) using an iterative technique that alternates between maximizing over "q" and e.g. performing gradient descent updates on "\Phi". Iteratively performing full optimizations over both sets of parameters may not in general have good convergence properties.
- Might be a relevant citation for the use of soft partition assignments for fairness: https://arxiv.org/pdf/2002.09343.pdf
- Fig 1: Would be nice if the plots were color blind friendly :)
- References: Might be good to mention the conference venue wherever available: e.g. Hashimoto et al. appeared in ICML 2018.
review_title: Interesting approach but lacks strong theoretical backing

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: 
This paper studies the connections between algorithmic fairness and domain generalization. As discussed in Section 2, the “environment” in domain generalization plays a similar role as the “group membership” in algorithmic fairness. The paper shows in Table 2 that the methods of each field can apply to the other field. 

The paper develops its own algorithm EIIL which extends the Invariant Risk Minimization (IRM) of domain generalization to work in the situation when the prior knowledge of environments is not available. And this extension is mainly based on the idea from algorithmic fairness literature which considers the worst-case environments and solves a bi-level optimization. 

The paper shows empirically that their algorithm EIIL outperforms IRM with handcrafted environments in terms of test accuracy on CMNIST.

Strength:
(1) The connection between domain generalization and algorithmic fairness shown by the paper is interesting.
(2) The paper demonstrates the performance of EIIL via empirical results.

Weakness:
(1) Other than the high level intuitions and examples, the paper does not provide any theoretical analysis of the performance of the EIIL for domain generalization. What guarantees can EIIL get in terms of the test error and how does it compare to IRM (when making reasonable assumptions about the training and test distributions)?
(2) Similarly, the paper does not provide any theoretical analysis of EIIL for algorithmic fairness.
(3) On top of page 6, after explaining the bi-level optimization, the paper switches to the sequential approach (EIILv1) without much explanation. Why is the bi-level optimization not practical? How well can the proposed sequential approach approximate the bi-level optimization results and how does this affect the performance of EIILv1?

Reasons for score:
Overall I vote for rejection since the weakness outweighs the strength. The lack of theoretical analysis of the algorithm makes the paper incomplete. 

Typo:
Page 5: two periods after word “poorly”.

review_title: ICLR 2021 Conference Paper3730 AnonReviewer2

Meta-review: The paper analyzes connections between algorithmic fairness and domain generalization literatures. The reviewers found the paper interesting but they also raised some important concerns about it.

The applicability of the method presented in the paper is not clear nor well-discussed in the paper.

The papers and the revised version do not not cite important related work.

The mathematical exposition in the paper is a bit hard to read. Even after revision, the reviewers find part of the paper(Appendix F) very hard to read.

Overall, the paper in the current version is below the high acceptance bar of ICLR.
Decision: Reject