Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper shows that for linear models with additive non-Gaussian noise components (LiNGAM) in the presence of latent confounders the inference of the direction of causal relations converges in the limit in probability to the correct orientation, but no longer satisfies the criterion for ‘statistical decidability’, this in contrast to unconfounded LiNGAMs. This result could have implications for the interpretation of causal models discovered under the LiNGAM framework.
main_review: High quality paper on a rather technical subject, but relevant to the theoretical foundations of causal inference in LiNGAM models with confounding. The main part of the paper is used to introduce/define various notions of decidability and identifiability, and to discuss existing results for linear additive noise models. The authors then construct a sequence of faithful LiNGAM models with confounding that come arbitrarily close in distribution to unfaithful linear Gaussian models, which we know are not decidable.

The key argument is described in p7, Fig3/Lemma 5.2. This in itself is an interesting example, but I am a bit concerned about the interpretation of the combined ‘convergence in probability’ but at the same time claiming ‘but not quite Gaussian/unfaithful’, even though it obviously gets arbitrarily close to Gaussian/unfaithful. Though perhaps technically correct, this seems more to do with a slight mismatch between the statistical definition of ‘convergence in probability’ and our standard causal concepts of faithfulness and non-Gaussianity, that allows to construct sequences of models that become arbitrarily close to unfaithful / Gaussian (but not quite) whereas they do satisfy the notion of ‘convergence in probability’. 

In other words: to me this is not so much a stark warning or novel insight into differing behaviour / properties between LiNGAM models with and without confounders, as perhaps an argument that our intuitive notion of faithfulness needs to be refined/strengthened a bit to avoid this sort of technical discrepancies in the limit. 

Apart from that I would suggest the authors specify the current result only applies to acyclic LiNGAMs, as cyclic (non-recursive) models also qualify as LiNGAM, but some of the proof steps specifically rely on lower triangular coefficient matrices (although I am sure the result can be extended to the cyclic case as well).

All in all a good paper, though perhaps a bit too niche & technical. I am not entirely sure this would make it a good fit for the conference: perhaps a more statistically oriented venue would be more appropriate, though I’m sure it will find an audience at NeurIPS too. The main conclusion is true, but the impact will be limited as it is primarily a theoretical issue for a very specific case of causal inference, and I do not consider it a crucial new insight or important caveat on the reliability of statistical causal discovery with latent confounders in general. However it could make a case for the need to refine our notion of faithfulness in the limit. 

=> For now: borderline to weak accept, but with medium confidence as I am not an expert in this particular area.

- originality: novel and interesting example that supports the core argument,
- quality: high quality
- clarity: very technical, but well written and still fairly good to follow for a non-insider
- significance: interesting find, but not sure it will have much impact beyond statistical & causal purists

minor comments:
- why no line numbers? 
introduction: ‘causal orientation is often not identified’ => this suggestion is wrong. for sparse graphs typically the (vast) majority are identifiable in the equivalence class, even for large graphs with or without confounding 
p2,top: ‘uniform consistency’ => here a ref. to ‘Uniform Consistency in Causal Inference’ (Robins,Scheines,Spirtes,Wasserman 2003) would be appropriate
p2,mid: ‘locally closed’ : so an open set is still ‘locally closed’ if it can be contained in a closed set?
p3,start sec.2: change to ‘An *acyclic* linear causal model’ (or ‘recursive’)
idem: would the results in this paper change if M is allowed to be non-recursive?
p3, term (1.): what is the role of \omega in this equation?
p5,Lerm/Thm/Cor 3.1: clear and interesting results, though not a fan of overloaded label numbers :)
p6,Fig3: mention the intrinsic noise term \epsilon_1+3 have switched places (I did not notice this at first)
p7,Fig3/Lemma 5.2: interesting example, but see main review
p8,below Thm 5.1: ‘consequences of Lemma 5.1’ => I assume you mean ‘Theorem 5.1’ right?
p9, mid: I feel the conclusions in this section are a bit too negative in the sense that this should not be a fundamental warning on the statistical reliability of causal inference in the presence of confounding, but more a motivation to strengthen / formalise our intuitive notion of faithfulness
limitations_and_societal_impact: No negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the consistency of the causal discovery algorithms especially focusing on the LiNGAM with latent variables. The authors show the direction of any causal edge in a confounded LiNGAM is not statistically decidable. 
main_review: The paper analyzes the statistical consistency of the causal discovery method.   
The paper builds on the decidability of the LiNGAM.  The authors put some effort into relaxing the sufficiency assumption and allowing latent confounders.
The theoretical contributions of this paper are both novel and significant.
 
However, the submitted manuscript does not use the NeurIPS 2021 LaTeX style file and adds the appendix into the main paper.  I tend to reject this paper.
 
 
I might have some misunderstandings about this theme or Formatting rules. So it is very likely that I will change my score if the other reviewers provide some new points.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on the problem of causal discovery in additive linear models with non-Gaussian errors (LINGAM) and latent variables. It asks: are the underlying orientations statistically decidable (controlled error for every n) for any algorithm? Unlike previous work that answered in the affirmative when all variables are observed, the authors demonstrate that the answer is negative when there is latent confounding. While identifiability guarantees exist in this setting (i.e. causal orientations or equivalently partial orderings are identifiable from data), decidability does not hold, developing further insights about the performance of LINGAM. 
main_review: Originality: to the best of my knowledge, the authors ask and answer an original question about statistical decidability of LINGAM with latent variables. While the proof techniques are quite similar to "Statistical Decidability in Linear, Non-Gaussian Model", there is valuable theoretical understanding that this paper offers. 

Quality: After going through some of the main proofs, the technical results appear solid and use neat arguments based on concepts from topology. While I did not understand some of the technical details (see the next paragraph for more discussion on that), I had some potentially naive technical questions for the authors:

-- For uniform consistency, the edge strength should typically be bounded away from zero. Under the same type of assumption, can we obtain statistical decidability in this setting with the latent variables? More generally, would imposing assumptions on the strength of the edges/ number of the latent variables and their effects/DAG structure among observed variables aid with statistical decidability?

--- Lemma 5.2: the argument here is that there is another model with p+2 variables that is also compatible with a LINGAM model. Is the number 2 somehow fundamental? suppose the number of latent variables was only 1. Could a different argument be made to show a similar result? I am sure I am missing some technical understanding here.

-- I recognize that statistical decidability is a desirable attribute and ensures that the "flopping" behavior in causal orientation does not occur. More practically, I wonder how significant this is when $n$ is large where asymptotic consistency kicks in.  In particular, the authors of the paper "Learning Linear Non-Gaussian Causal Models in the Presence of Latent Variables" demonstrate good experimental results of their procedure for identifying causal ordering (While statistical decidability is not satisfied). I just simply wonder, concretely, how relevant this statistical decidability is in practice?  


Clarity: my biggest concern with this paper is the amount of notation that the reader must sift through to understand definitions and high-level proof strategy. As somebody who is not an outsider to causal inference with latent variables, I had a very hard time going through this paper, and I imagine most of the readers would have similar difficulties.  Unfortunately, such impenetrability really hurts the paper in my opinion. As such, I think the authors need to make very substantial changes to the writing to improve clarity and readability. Below I outline some suggestions: 

--- "prove that if, in addition to
the usual LiNGAM assumptions, we assume causal faithfulness, then causal orientation between
observed variables is identified even in the presence of unobserved confounders." -> perhaps to ensure that this is not misleading for readers, best to say that they prove that the causal ordering is identifiable, even if the causal structure is not. This to me is not the same as saying causal orientation is identified cause one still doesn't know whether there is an edge between two observed variables

--- there is label "34th Causal Discovery & Causality-Inspired Machine Learning Workshop at Neural Information Processing
Systems, 2020" at the bottom of page 1. Please remove.

--- "Causal orientation is statistically decidable,
if for any \alpha> 0; there is a consistent procedure that, at every sample size, hypothesizes a false
orientation with chance less than" -> it's good to define what orientation means right in the introduction. I imagine here a false orientation could also be deciding an orientation when no partial order exists between the variables.

--- Table 1: Causal Orientation in LiNGAM models: it would be good to highlight here what the authors contribution is clearly for quicker readability. Further Table 1 is not referenced in the main text. 

--- Since the contribution of this paper is technical, it would be good to state an informal theorem in the introduction and provide a few sentences about the high-level proof technique.

---- "Let Me a set of statistical models. We assume there is a function ....." -> it seems very abrupt to jump into heavy notation without some easing in or at least having a different subsection in the intro.  While i appreciate the precision and careful mathematical definitions, looking at the introduction, it reads as more a mathematics paper than a neurips paper. 

---- Statement of Theorem 1.2: a cleaner way to write this it may be:  "for every A,B, P(A) intersect with cl(P(B)) is empty"?

--- Theorem 1.1 and 1.2 appear in the introduction and are not the main result. This seems a bit off. To me, these two theorem statements somehow guide the high-level proof technique. This really does not come through from the writing but is clear later after one reads further in the paper. 

---- "A linear causal model in d variables M is a triple": the authors use $d$ here and later $p$. At first, I thought $d$ is the number of observed and latent variables and $p$ is the number of observed variables. This however feels potentially wrong since the random variables are named X. It would be good if the authors describe what is observed and latent as soon as they describe the SCM. 

----- The description leading up to the faithful description seems overly complex and unnecessary. I think it would be better to state it that  the model M is faithful if ) The total causal effect from variable X_i
to X_i is nonzero if there is a causal path from X_i to X_j. This translates algebraically to B_ij(M) \neq 0 whenever  j-> i. 

----  The paragraph before section 3 introduces more notations. It's best if to condense these and include in the intro. I think the authors should have a notation section and a section with definitions (e.g. faithful, statistical decidability, question, answers,...)

---- Theorem 4.1: how is this different than standard LINGAM result?

---- "That situation is not too worrisome, since the effect of an ideal
intervention on X1 would be the same in both circumstances. What is more worrisome is that
the vector of observed variables O may admit two LiNGAM models that differ on the effects of
interventions." -> what is the definition of intervention here? seems strange to see intervention all of a sudden. Perhaps authors could rephrase.

--- Perhaps some diagrams would help clarify: for example, the authors could show the proof strategy at the beginning of the paper with diagrams indicating the space of questions/answers and the topological arguments that will be made for their proof.

the same of questions and displaying what is needed for statistical decidability.

Significance: To me, while it is nice to have this negative result, I am not sure about the significance of statistical decidability in practice. Perhaps for low sample settings, this is an important question but is likely insignificant in large sample settings. It would help the paper if some empirical demonstrations highlight the relevance. Further, given the large amount of notations in this paper and the current writing structure, I am not sure if this will have lasting impact unless major revisions are conducted. 
limitations_and_societal_impact: None that I can foresee.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper is about statistical causal inference. More specifically, this paper is about the causal discovery that infers causal graphs. Many methods focus on investigating the identifiability of various models for causal discovery and proposing estimation methods for the identifiable models. This paper points out that the identifiability does not necessarily imply that desirably consistent estimations methods exist. 

There are many types of consistency, including uniform consistency and point-wise consistency. This paper investigates which consistency can be achieved for linear non-Gaussian acyclic models with hidden common causes, confounded LiNGAM (Hoyer et al., 2008). This analysis is based on a consistency concept named statistical decidability proposed in Genin and Mayo-Wilson (2020). 

Their main result is summarized in Table 1. Genin and Mayo-Wilson (2020) showed that LiNGAM with latent confounders (Shimizu et al., 2006) is (statistically) decidable with/without the faithfulness assumption. Faithfulness is a common assumption in causal discovery (Spirtes et al., 1993). The causal ordering of variables, ancestral relationships, of confounded LiNGAM has been shown in identifiable if faithfulness is assumed (Hoyer et al., 2008; Salehkaleybar et al., 2020). If faithfulness is not assumed, it is not decidable. The definitions of decidability are on pages 2 and 3. Theorem 1.1 and 1.2 say how one could check whether such consistency hold. Their very main result is Theorem 6.1 in the final section. All the other sections are written to prepare for giving the theorem.

----
I updated the score and confidence. 

main_review: Originality: The task considered here is fresh in LiNGAM and other identifiable causal discovery methods. For nonparametric methods based on conditional independence, there are some works on this consistency issue as on page 2, e.g., Kelly and Mayo-Wilson (2010) and Zhang and Spirtes (2003): Strong Faithfulness and Uniform Consistency in Causal Inference.

Quality: Most of this paper is devoted to proving Theorem 6.1. This would be necessary. Further, this would be better than putting all the proofs in the supplement. On the other hand, when trying to evaluate the value of this paper, I would like to know more background and practical implications. 

For example, uniform consistency looks very strong property, and I wonder if how many methods would have uniform consistency. Would well-known statistical methods and machine learning estimation methods, e.g., lasso, have the property? If most of the methods do not have uniform consistency, would it be meaningful in practice to require uniform consistency? Perhaps, Genin and Mayo-Wilson proposed statistical decidability because they thought uniform consistency is a too strong requirement, but point-wise consistency is a too weak requirement.

Kelly and Mayo-Wilson said that the PC algorithm does not have the property in the unconfounded linear Gaussian setting. But, Zhang and Spirtes (2003) seem that they added strong faithfulness to prove the uniform consistency. Also, as in footnote 2, Buhlmann et al. (2014) considered additional assumptions to achieve uniformly consistent procedures.

My question is which consistency concept is good enough when users need to judge which estimations methods are reliable enough. I didn’t fully understand what users can compute and cannot compute for each of the consistency concepts. 

In Section 6, they say that it is not possible to construct confidence intervals for causal effects enjoining finite-sample coverage. Does this mean that it is not meaningful to compute confidence intervals for causal effects for other methods than uniformly consistent estimation methods?

In the literature of causal discovery, users often compute bootstrap probabilities of causal orientations, e.g., Komatsu et al. (ICANN2010) and Moneta et al. (2013, Oxford Bulletin of Economics and Statistics). Is this a right procedure for unconfounded LiNGAM but not for confounded LiNGAM?

Other questions are: 
1.	whether this consistency property depends on the choice of estimation algorithms, e.g., ICA-based LiNGAM or some other estimation methods for LiNGAM. 

2.	Do researchers need to find and add more assumptions to achieve uniform consistency or statistical decidability? Or do researchers need to find some better consistency criterion so that most of the methods satisfy the criterion and the criterion is enough practically useful from some practical viewpoint?

3.	Table 1 summarized the differences between different LiNGAM methods. In this paper, they prove the difference. I’m interested in why and/or how this difference arises.

4. I'm not very familiar with this type of mathematical considerations. For example, In the proof of Lemma 5.2, they consider sequences $X_{1,n}$ and $X_{2,n}$. I didn't follow why considering these sequences is going to prove the lemma. n is the sample size. 

Clarity: I felt that the authors did their best to compactly have the relevant theorems and proofs in these eight pages to finally prove the main result, Theorem 6.1. Nevertheless, giving some examples would have helped a lot to better and more quickly understand the content, I think.

Significance: I agree with them that this is the first step in understanding how difficult a problem is, as they stated at the bottom of Section 6. Though most works on causal discovery focus on showing the identifiability conditions and developing efficient algorithms, this type of works would be necessary for users to use causal discovery methods properly.
limitations_and_societal_impact: It seems better if this paper gives more background and practical implications to better place this work in the literature.
review_title: null

Meta-review: A nice summary of this paper from one of the reviews:

"The paper shows that for linear models with additive non-Gaussian noise components (LiNGAM) in the presence of latent confounders the inference of the direction of causal relations converges in the limit in probability to the correct orientation, but no longer satisfies the criterion for ‘statistical decidability’, this in contrast to unconfounded LiNGAMs. This result could have implications for the interpretation of causal models discovered under the LiNGAM framework."

While initially the reviewer opinion was mixed, the discussion with the authors led to an emerging consensus that the paper is novel, interesting, and a worthwhile addition to the NeurIPS proceedings.
Decision: Accept (Poster)