Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Update

I have read the author response and the updated version of this paper. I am delighted to see that the authors have incorporated my feedback and I believe this makes the paper stronger than its previous version. I have updated my scores and recommend that the paper be accepted.

------------------------------------------------------------------

This paper proposes Asymmetry Learning, a new learning paradigm to obtain counterfactually invariant classifiers. If the observed covariates are a result of some transformations applied to a hidden variable, and these transformations differ between training and test datasets, a classifier may not generalize to the test set. The authors argue that when these transformations are a result of a collection of equivalence relations, finding OOD-invariant classifier boils down to finding the simplest causal model that defines the causal relationships between the labels and these symmetry transformations. To this end, the authors propose a scoring criterion to identify the simplest DAG in a DAG search space that ensures that the label is invariant of all transformations while maximizing the likelihood of the observed training set. Using their proposed scoring function, the authors employ Greedy Equivalence Search to identify the DAG with the highest score. Experiments on simulated physics tasks suggest that the method works as intended.
main_review: - The paper is well motivated, and examines an important problem of classifiers failing out-of-domain.
- The paper's contributions could be significant to what is an emerging area of research. Other than [1, 2] and [3], I have not seen any other paper that offers a theoretical framing for the relationship between counterfactual invariance and OOD generalization and provides a way to achieve the same. 
- The paper flows smoothly and is easy to understand.
- I wish the paper offered a greater discussion of prior work on counterfactual invariance as it relates to out-of-domain generalization. I hope the authors can address that in a future version. Additionally, while the authors have offered some discussion of [2] and [3], per my reading, [1] seems to offer a contradictory view (from this paper) of whether learning an invariant OOD classifier is solvable via interventional data augmentation or not. It would be great if the authors could share how one relates to the other. I'm not sure I found a convincing argument laid in this paper other than the example in Figure 1(c).
- The experiments in the paper are on simulated tasks with limited number of variables. It is unclear how this method might work in high dimensional spaces, such as text. Though it's not necessarily a concern, I think it would be useful if the authors could comment on the same.

[1] Kaushik, D., Setlur, A., Hovy, E. H., & Lipton, Z. C. Explaining the Efficacy of Counterfactually Augmented Data. ICLR 2021.
[2] Veitch et al. (2021)
[3] Wang and Jordan (2021)

Typos and presentation: 
- Introduction Line 2: "the task is requires" -> "the task requires"
- Break the second sentence of the first paragraph of introduction.
- Layer 3 description of Pearl's causal hierarchy: "X\dagger describe an hidden variable" -> "X\dagger describe a hidden variable"
- Your figures are blurry upon printing the paper. Please increase the font of the text in the figures.
- Section 4.1: "Our next results requires imposing" -> "Our next results require imposing"
- Section 4.1 under Definition 2: "Definition 2 holds for a equivalence relation" -> "Definition 2 holds for an equivalence relation"
- Related Work should either be Section 6 or be Section 2 (right after introduction) and not be in between the theory and empirical results.
- In justifying Assumption 1, can you provide a citation that is more recent considering the science in this area has evolved considerably since 1982?
summary_of_the_review: Overall, I think the paper presents a good contribution but I do have some minor concerns that I would like the authors to address as I have mentioned above.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose an approach for constructing classifiers that achieve out-of-distribution (OOD) generalization using a new learning paradigm they call _asymmetry learning_. They consider OOD tasks where the test input is obtained from the training input by applying a sequence of (random) input transformations. To obtain an invariant OOD classifier that generalizes well to both in-distribution and out-of-distribution samples, the authors introduce the concept of _counterfactual invariant representations over symmetric transformations_. They show how learning the invariant representations can be cast as a causal structure discovery task and propose a score-based (GES-based) algorithm for finding the causal directed acyclic graph (DAG) that best describes the invariances.
main_review: **Update**: After reading the rebuttal and the other reviews, I have decided to bump up my original score to an 8. Thank you to the authors for addressing our concerns in great detail.

**Strengths**:
- The methodology has a strong theoretical basis, and is a result of combining insight from different fields. The idea behind this approach, is in my opinion, quite elegant.
- The paper is well-written and the work is well-placed in the literature, the illustrations are well-thought-out and facilitate understanding the method.

**Weaknesses**:
- The experimental section consists of only two simulated toy examples. While these showcase how the method is supposed to work, it remains unclear how well the method would work in a real-world, uncontrolled environment. How often are the assumptions made about the data generating process expected to hold 'in the wild'?

Other comments:
- The figures and table appear out of place. Table 1 is referenced in the Results section, but is shown two sections before without context. Figure 1 appears a bit too early in the paper (first mentioned in "Illustrative SCM example"), while Figure 2 appears much later (first mentioned before Figure 1, after that mentioned before Theorem 1).
- The caption text for Figure 2a(iii) is clipped out. The subfigure is also way too small to be readable without zooming in.
- Reference to "Accounting for unobserved confounding in domain generalization" appears to be duplicated.
- page 2, Layer 1 - "causal" misspelled as "casual"
- page 3, Symmetry transformations - Sentence starting with "Although" appears incomplete. I would suggest conjoining this sentence and the one before: "... equivalence classes, although ...".
- page 8, Causal structure discovery, third row from the bottom: "between distribution" -> "between **a** distribution"
- page 9, second row: add comma before "under the assumption"
summary_of_the_review: The authors propose an interesting idea for constructing OOD classifiers starting from counterfactual invariance for symmetric transformation, an idea that is well-formulated in this paper. Despite the lack of real-world validation, I think the paper has a strong theoretical basis and is a decent contribution to the literature.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers a class of out of distribution (OOD) problems where at test time there may be new symmetry transformations of the input X (i.e., they don't change the label Y). The authors explain why standard invariances learned by data augmentation may not be OOD invariant. Next, the paper presents a method for learning OOD-invariant representations through causal structure discovery. This hinges on the concept of being counterfactually invariant to the symmetry transformations that could appear at test time but don't affect Y. Next is an algorithm for discovering the structure of a causal DAG which largely revolves around deciding whether or not there is an edge U_i -> Y; this existence question corresponds to whether or not Y is invariant to the transformation U_i (IIUC).

The paper test this approach on tasks in a simple simulated physics environment.
main_review: Strengths:
This paper does a good job of describing an interesting and important problem, invariance to OOD symmetry transformations, and motivates why existing approaches may not work well. The approach novel as far as I'm aware, and clearly describes relevant concepts such as defining what we would want our OOD-transformation invariant representations to satisfy and how learning them is linked to causal structure discovery.

Weaknesses:
- The method appears to identify which of some set of transformations one should be invariant to (and learn correspondingly invariant representations). But we must first have prepared a collection of all possible symmetry transformations, which seems like a limitation of the method. Additionally, is there a trade-off where considering more symmetry transformations makes the method slower?
-  The experiments and comparisons are relatively minimal and are only in a toy environment. From the description of the method I assume there are computational difficulties in practically implementing this method for more "real-world" problems. The papers would be strengthened by either having larger more realistic experimental comparisons, or barring that an explanation of the practical difficulties of applying the method to larger problems and future steps that could resolve them.
summary_of_the_review: Interesting ideas with relatively toy empirical results.
review_title: null

Meta-review: This paper proposes asymmetry learning for learning counterfactual classifiers, i.e. classifiers which are invariant to certain symmetry transformations w.r.t. hidden variables that differ between the training and test sets.

The reviewers universally agreed that the proposed setting, and theoretical contribution, were interesting and novel. They also praised the writing quality, but had some quibbles about the quality of the experiments, and discussion of prior work. Neither of these concerns were considered significant enough to be a barrier to acceptance, but the authors should try to improve them, if possible.
Decision: Accept (Oral)