Statistical Undecidability in Linear, Non-Gaussian Causal Models in the Presence of Latent Confounders
Authors: Konstantin Genin
Venue: NeurIPS 2021 Poster (2021)
Keywords: causal discovery
linear non-gaussian models
faithfulness
confounding
topology

Abstract: If causal relationships are linear and acyclic and noise terms are independent and Gaussian, causal orientation is not identified from observational data --- even if faithfulness is satisfied (Spirtes et al., 2002). Shimizu et al. (2006) showed that acyclic, linear, {\bf non}-Gaussian (LiNGAM) causal models {\em are} identified from observational data, so long as no latent confounders are present. That holds even when faithfulness fails. Genin and Mayo-Wilson (2020) refine that result:  not only are causal relationships identified, but causal orientation is {\em statistically decidable}. That means that for every $\epsilon>0,$ there is a method that converges in probability to the correct orientation and, at every sample size, outputs an incorrect orientation with probability less than $\epsilon.$ These results naturally raise questions about what happens in the presence of latent confounders. Hoyer et al. (2008) and Salehkaleybar et al. (2020) show that, although the causal model is not uniquely identified, causal orientation among observed variables is identified in the presence of latent confounders, so long as faithfulness is satisfied. This paper refines these results: although it is possible to converge to the right orientation in the limit, causal orientation is no longer statistically decidable---it is not possible to converge to the correct orientation with finite-sample bounds on the probability of orientation errors, even if faithfulness is satisfied. However, that limiting result suggests several adjustments to the LiNGAM model that may recover decidability.

Statistical Undecidability in Linear, Non-Gaussian Causal Models in the Presence of Latent Confounders
Konstantin Genin"
University of Tübingen konstantin geninggmail.comm com
Abstract
If causal relationships are linear and acyclic and noise terms are independent and Gaussian, causal orientation is not identified from observational data even if faithfulness satisfied (Spirtes et al., 2002). Shimizu et al. (2006) showed that acyclic, linear, non nan-Gaussian (LiNGAM) causal models are identified from observational data, so long as no latent confounders are present. That holds even when faithfulness fails. Genin and Mayo- WilooWWlsonn (2020) refine that result: not only are causal relationships identified, but causal orientation is statistically decidable. That means that for every > 0, there is method that converges in probability to the correct orientation and, at every sample size, outputs an incorrect orientation with probability less than These results naturally raise questions about what happens in the presence of latent confounders. Hoyer et al. (2008) and Salehkaleybar al. (2020) show that, although the causal model is not uniquely identified, causal orientation among observed variables is identified in the presence of latent confounders, long as faithfulness is satisfied. This paper refines these results: although it is possible to converge to the right orientation in the limit, causal orientation is no longer statistically decidable- to the correct orientation with -ample bounds on the probability of orientation errors, even faithfulness is satisfied. However, that limiting result suggests several adjustments to the LiNGAM model that may recover decidability.
not possible converge
1 Introduction
Spirtes et al. [2000] develop the elements of causal discovery from observational data in the linear Gaussian setting. They show that when functional relationships between variables are linear and acyclic and noise terms are independent and Gaussian, it is possible to converge to the Markov equivalence class of the graph generating the data. Although some non-trivial causal information can be recovered, causal orientation is in general not identified: two linear Gaussian models may differ causal orientation and nevertheless generate the exact same distribution over the observed variables. Identifiability fails even when causal faithfulness is satisfied and no hidden variables are present. For this reason, it was a significant advance when Shimizu et al. [2006] showed that, when functional relationships between variables are linear and acylic and noise terms independent and non-Gaussian all causal orientations can be uniquely identified from observational data, even without assuming faithfulness. However, that early result depends the absence of unobserved confounders. Since then, the LiNGAM framework, as it came to be called, has been extended to accommodate the presence of hidden variables [Hoyer al., 2008, Salehkaleyhar et al., 2020]. Salehkaleybar et al. [2020] prove that if, in addition to the usual LiNGAM assumptions, we assume causal faithfulness, then causal ancestry relationships between observed variables are identified even in the presence of
Research Group Leader "Ethics and Epistemology of Machine Learning" at the Cluster of Excellence "Machine Learning for Science", University of Tübingen.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Table 1: Three Varicties of Decidability
then the output probably... ... informative after known N
correct and informative after unknown N
correct all N
Uniformly Decidable
When orientation
Decidable
X
Decidable
X
X
V
the limit
i Outputs expressing suspension of judgement are here considered correct.
unobserved confounders. In other words: if two faithful, confounded LiNGAM models generate the same distribution over the observed variables, then for every pair of observed variables X, Y, the models must agree whether X is causally upstream of Y, Y is upstream of X, or neither is upstream of the other. Note that the models do not have to agree on which variables are direct causes of which others, only which variables are ancestors of which others. Moreover, although all models generating the same distribution over the observed variables must agree on the causal ancestry relations between them, they may disagree on the strength of the causal effects (Figure 2).
These identifiability results are exciting theoretical developments. However, identifiability is a weak criterion and on its own does entail the existence of consistent discovery algorithm. Moreover, distinctions ought to be made between degrees of identifiability. For example, uniform decidability (elsewhere known as uniform consistency) requires that one be able determine priori sample size at which the chance of identifying the true orientation is at least - at, no matter which causal model generating the data. Unfortunately, it easy to show that there is no uniformly consistent algorithm for determining the direction of a causal edge, even in unconfounded LiNGAMs (see Example in Genin and Mayo-Wilson [2020]). Although one could strengthen the LiNGAM assumptions make uniform decidability feasible, these assumptions would probably be implausibly strong
Decidability in the limit (elsewhere known pointwise consistency) requires only that for each causal model that might be generating the data, there be some sample size by which the chance of outputting the true orientation is least a. Note that this is compatible with all kinds of short-run behavior. For example, Kelly and Mayo-Wilson linear Gaussian setting, even in situations in which causal orientation is identifiable, it is possible to force any consistent discovery procedure to "flip" its judgement about whether causes Y or vice versa. That means that for any such procedure, is possible to find model in which the procedure flips between being highly likely to output the correct causal orientation at smaller sample size and highly likely output the incorrect orientation a larger sample size, with the number of such flips bounded only by the number of variables in the model.
Wilson [2010] show that in the unconfounded
Genin and Mayo-Wilson Wilson [2020] introduce uniform decidability and decidability in the limit. Statistical decidability requires that a discovery procedure converge the true orientation sample sizes increase and, at every sample size, output an incorrect orientation with probability at most a. Note that statistical decidability rules out flipping behavior, but is consistent with suspending judgement arbitrarily large sample sizes. Genin and Mayo-Wilson Wilson [2020] show that, in the absence of unobserved confounders, causal orientation is decidable in the LiNGAM setting and therefore, flipping can be avoided. That demonstrates that statistical decision procedures may exist even when uniform decision procedures do not.
notion of decidability that is intermediate between
"In the linear Gaussian setting, Robins al. [2003] show that uniform consistency is not feasible under standard assumptions. Zhang and Spirtes [2003] propose strengthening of these assumptions to ensure uniform decidability, but Uhler et al. [2013] argues that this rules out topologically large set of models. Bühlmann et al. [2014] give conditions strong enough the ensure uniform decidability in the general setting of additive structural equation models.

---

Table I sums up: if we have a uniform decision procedure we know that the output of the method probably correct at every sample size and we know a priori how large a sample we need for it to be informative. If we have a decision procedure, we know that the output of the method is probably correct at every sample size, but we do not know a priori how large a sample we need for it to be informative. And if we have only limiting decision procedure, we can never be sure that the output is correct, although we know it will be probably correct eventually.
Crucially, mere identifiability alone does not entail that a problem is decidable in any of the above three senses. Therefore, the results of Salchkaleybar et al. [2020] leave open the possibility that the causal ancestry relationship is not even decidable in the limit. The first main result of this paper is that the ancestry relationship indeed decidable in the limit there exist consistent procedures for learning the causal ancestry relationship between observed variables. Unfortunately, flipping returns in the confounded LiNGAM setting, even when we assume causal faithfulness. Although consistent procedures exist for learning causal orientation, consistent decision procedures do not. Table 2 sums up these results. However, that result suggests several adjustments to the LiNGAM framework that could recover decidability. These are discussed in Section 7.
Table 2: Causal Orientation in LiNGAM models
Unconfounded
Potentially Confounded decidable in the limit
Faithful
decidable
not identified Genin and Mayo-Wilson [2020] prove the results in the first column. The result in the upper-right cell proven in this paper.
Unfaithful decidable
2 Technical Preliminaries
We first introduce notation for manipulating matrices. Suppose A is an n x p matrix and U, V are subsets of (1....,P) n1), {1,-. (1,...:P), P), respectively. Let Agr.v] be the result of dropping all rows from A that are not in U and all columns that are not in V. Let A(D:v) be the result of dropping all rows from A that are in U and all columns that are in V. We write A(t.)) for ((())()))) and Ai for A We say A has pairwise linearly independent columns iff no two columns of A are proportional.
Let M be a set of statistical models. We assume there is a function P M + PM that maps each model in .M to probability measure over a space S2 of observed outcomes. although we often do not distinguish between random vector and the probability measure induced by its distribution function. Henceforth, we assume Ω = RP. We lift
P(.) to sets of models in the obvious way: if A C M, let P[A]= = (P(M): : M E A}. Let P P(M). Let Po C P be the probability measures in P absolutely continuous with Lebesgue measure on Ω. Let Po M. Po n PIM]. If A S Rnd let 0A be the boundary of A in the usual topology on Rdd The weak topology on P is defined by letting a sequence of Borel measures P,, converge weakly to P. written P,, = P iff (A) + P(A), for every A such that P(AA) = 0. A collection of random vectors (X,) converges in distribution to X iff the probability measures induced by the X,, converge weakly to the measure induced by X. We write cl(.) for the closure operator in the weak topology. We say that a set is locally closed iff it the intersection of an open and a closed set. Although every open set and every closed set is also locally closed, the converse is not true: there are properly locally closed sets which are neither open nor closed. In metrizable topologies such as the topology of weak convergence, every open set, and therefore every locally closed set, is countable union of closed sets. For any natural number k, let Ph be the k-fold product measure of PM with itself. This measure describes the probabilities of events in Add when we take k iid samples from PM- If the measures Pa converge weakly to P, the product measures pk also converge weakly to pk (see Theorem 2.8 in Billingsley [1986]).
We define question Q to be a countable set of disjoint subsets of M. The elements of Q are called answers. For all M E U1, let (2M) denote the unique answer in Q containing M. The answer to question Q identified iff P(M) & P(M') whenever (2M A (MM'.. Given a question 12 we define method > = (Am)nEN to be sequence of measurable functions X, S2" + Q U [M}. where Xn maps samples of size n to answers to the question; a method may also take the value M to indicate that the data do no fit any particular answer sufficiently well, and so we call M the uninformative answer. We require that ax,=1 (AA has Lebesgue measure zero for all n and every answer A in the range of An.
3

---

A method is (pointwise) consistent for Q if for all > 0 and M E UD, there is n such that Pk (A; (MM)) 1 for all k 2 n. We say that Q is decidable in the limit iff there is a consistent method for 12. Dembo and Peres [1994] give the following sufficient condition for limiting decidability. For a proof, see their Corollary 2.
Theorem 2.1 (Dembo and Peres [1994]). 2 is decidable in the limit if (P(() A is disjoint and each P(A) is a countable union of sets closed in the weak topology.
Given some O, say that a method À is an a-decision procedure for 12 if (1) À is consistent for Q and (2) PM (M & Xn) S a for all M E UQ and all sample sizes n. In other words: an a-decision procedure outputs a false hypothesis with probability most a. A question statistically decidable (or simply decidable) if there is an a-decision procedure for a > O. We give simple necessary condition for statistical decidability.
Theorem 2.2. Q is statistically decidable only if Po() n CBP = for all A,
Proof of Theorem 2.2. Suppose for a contradiction that Pas E P(A) (cl( is absolutely con- tinuous with Lebesgue measure and À is an a-decision procedure for Q. Since À is consistent for 12, there must be n such that PMr (x, (A)) > - a. Since ²x; (A) has Lebesgue measure zero and Pir is absolutely continuous with Lebesgue measure on RRP, PM
= 0.3 There- fore, there are (M;) in B such that PM, (A) - (A). But then there is some Mj B such that Pit, (M, & Xn) > Contradiction.
is worth introducing some intuitive language for questions 5 with only one (usually non-exhaustive) answer A S M.. We say that A is statistically verifiable iff Q = {.A} is decidable. Say that A is statistically refutable iff a {M \ A} is decidable. For partial converses of Theorems 2.1 and 2.2, see Genin and Kelly [2017]. Essentially, the converses hold straightforwardy if all distributions assumed absolutely continuous with Lebesgue measure.
The fundamental result of this paper is that the question of whether (observed) X is an ancestor of (observed) Y or vice-versa, while decidable in the limit, is not decidable. The former follows from Corollary 6.7 and an appeal to Theorem 2.1. The latter is proven by showing that you can approximate to arbitrary degree of precision the distribution over (X, generated by faithful LiNGAM in which X + Y by a sequence of distributions (Xm, Ym) generated by faithful but confounded LiNGAMs in which X,, Ym (see Figure 3 and Lemma 6.2). Undecidability follows by appeal to Theorem 2.2.
3 Acyelic Linear Causal Models
An acyclic linear causal model in d variables* M is a triple (X, e, A), where X -X,) is vector of d random variables, e = (e1, (e1,e,...., is random vector of d exogenous noise terms, and B is a d matrix such that
1. Each variable X, is a linear function of variables earlier in the order, plus an unobserved noise term e;:
X
Ag + es;
j<i
2. the noise terms e., are mutually independent.
In matrix notation, we have that X = AX - e. Because no X; causes itself, A has only zeroes along its diagonal. By virtue of the causal order, is lower triangular, i.e. all elements above the diagonal are zero. The random vector X also admits a "dual" representation: X = Be, where B = (T A)- To see that B always exists, note that the determinant of triangular matrix is equal to the product of its diagonal entries. Since the inverse of lower triangular matrix is lower triangular, the matrix B is also lower triangular, however its diagonal elements are all equal to one. If M = (X, e, A), let M be equal to the length of the vector X. Moreover, let X(M), e(M), A(M) and B(M) be
'I is basic fact that if μ << y then n² << D². 'In the following d refers to the total number of (potentially hidden) variables and p < d to the number of observed variables.

---

e, and (I - ([-A)-- respectively. The relationship between A(M) and (MM) will be made more perspicuous in the following.
Write j -M i as a shorthand for (M) & 0. The relation -M defines a directed acyclic graph G(M) over the vertices {1,..-, |M])- A causal path of length from i j in G(M) is sequence of vertices ग = (VI,..., Um) such that V1 i, 4m j and 0 -M 2/41- Let 11; (M1) be the set of all causal paths of length n from to j in G(M). Let (MM( be the set of all causal paths from i to j in G(M). Let (T(M) be the set of all causal paths in G(M). Write i ~M j as a shorthand for H1y(M) * Ø. Write j ou i when j Ar i and j x i. If π = (e1..... 2x2) is a sequence of vertices in (1,.... [M]; let the path product XM π be the product of all causal coefficients along
the path in G(M), i.e. XM π
IT= A A (M)). Note that if π E (MM) iff X M x + 0.
It is easy to verify that
(M)
Σ XMT..
(M)),(M)
In other words, At, (M) is the sum of all path products for paths of length & from i to j. So A (M) + 0 implies j ~ Ar v. The converse is not necessarily true, since non-zero path products may sum to zero. By a result of Carl Neumann's ss B(M) = E (M). So (M)(M) = E=Eu, (M) X т. In other words, (M) is the sum of all path products for paths from i j. So (My(M) * implies j ~ i. The converse does not necessarily hold since non-zero path products may sum to zero. We say that model M is faithful if the total causal effect from X₃ X, is nonzero if there is causal path from X; to Xj. In other words: M is faithful if Bi (M) o O whenever j ~* i.
An acyclic linear causal model M is non-Gaussian (a LiNGAM) if in addition to satisfying (1) and (2), each the noise terms non-Gasssian. Let LIN, be the class of all acyelic linear causal models on d variables, and let LNG,, FLNG. respectively denote the classes of non- non-Gaussian models and faithful non- Non-Gaussian models. Similarly, LIN, LNG and FLNG respectively represent the classes of all acyclic linear causal models, all acyclic linear non- Gaussian models, and all faithful acyclic linear non-Gaussian models over some finite number of variables. It is sometimes reasonable to introduce a priori constraints the maximum size of a coefficient in LiNGAM model. For example, if c is the number of particles in the universe, let FLNG be the set (M& E FLNG: max:,; |Be (M) < c}. Let FLNG, be FLNG n FLNG,.
Parsimonious Models
Let O be the set of all probability distributions R., We are interested in when the same vector of observed random variables could have arisen from distinct causal models. Accordingly, say that random vector O (0,, ......... Op) E O admits LiNGAM model M E LNG,, if there is a permutation a of (1,... d) such that O = (o- for 1 S i S In other words: O = (0, (O...... .0p) admits M there is a way to order the d variables of X(M) such that the first p identical with Oz,..., Op- We say that the permutation a embeds O into M. If embeds O into M, then
(M)
where Bo (M) is the first p rows of P. B(MP eo (M) is (ee(M) and P. is the permutation matrix corresponding to a. Extend the causal order over the elements of M to the O by setting O aa O₂ if a (i) M (J) and O оM O, if a -1 (a) oas a -
Say that O admits a LINGAM model if there is such that O admits M e LLNGg. We say that a model M LNGa is parsimonious for O if O admits M and O admits no M' in LNG, with f << d. It is immediate that O admits a LiNGAM model, it admits some parsimonious LiNGAM model. For A E {LNG,, LNGE, FLNGA, FLNG)) Let O C O be the set
(0 O: (3M E A)M is parsimonious for O}.
'The spectral radius p(A) of square matrix A is the largest absolute value of its eigenvalues. Neumann's 's result states that if pl < then (I-A)- A)- exists and is equal Ex= A Since the eigenvalues of triangular matrix are exactly its diagonal entries, p(B(M)) = O for any acylic linear causal model M. By acyclicity, there are paths longer than [M]. so E Sasa+ A 0.
5

---

c2 beg
X1
X2
X1
X2
ab c
0
Figure 1: If M is the left-hand model and O (X1, then Bo
and the
ab +
second and third columiss are proportional. The right-hand model fewer variables and generates the same distribution over O.
For A E {LNG, LNG", FLNG, " Let Ogga = Ussd OA, and OAga = U32d Oa,- Let O Oeaa OAsa be defined similarly. Finally, let OA A22=
The following Lemma says that if M is faithful and parsimonious for O then column of Bo (M) is proportional to any other. The proof idea is expressed by Figure 1: by adjusting the edge coefficient from X2 to X2, it is possible "absorb" L. into the noise term of X₂ without changing the distribution of (X,, or violating the LiNGAM model assumptions. The proof is a relatively straightforward generalization of the example, but since it is rather lengthy we relegate it to the Supplementary Material. A related result is given by Salehkaleybar et al. [2020, Theorem 11].
Lemma 4.1. Suppose that O admits faithful M E LNGs and that some column of (o is proportional to another. Then there is M' E LNGg-1 such that (i) O admits M' and (ii) O₃ m M Oj iff wa O, and (Ai) M' is faithful.
Lemma 4.1 raises a question about the converse: is it also the case that if Bo (M) has no two proportional columns, then M is parsimonious for O? The following Theorem from Kagan et al. [1973] allows us answer the question in the affirmative. We will appeal to this Theorem several times in the following.
Theorem 4.2. Suppose that X Ae Bf, where A and B are p r and p matrices and = (ei...., e. f- (fl....,f.) are random vectors with independent components. Suppose that no two columns of are proportional each other. If the i-th column of not proportional to any column of B, then is normally distributed.
Theorem 4.3. Suppose that faithful M E LNGg, Then, M is parsimonious for O (O1,..., Op) iff no column of (o(M) is proportional to any other.
Proof Theorem 4.3. The left to right implication is immediate from Lemma 4.1. To prove the converse, suppose that M is not parsimonious for O. Then, admits some M' E LNG, with f < d. Bo (MM"))eee (M")eo (M'), where Bo (M) an p matrix and Bo (M')
Moreover O Bo Ro((M .M (M)) is Pap x f matrix. By Theorem 4.2, every column of Bo M) is proportional to some column of Bo (M'). Since the latter has fewer columns, there must be two distinct columns of (M(M) that proportional to the same column of Bo (M') and, therefore, to each other.
We close this section with easy corollary of Lemma 4.1, which we will appeal to in the following. Corollary 4.4. Suppose that O admits faithful M LNG. Then there is faithful M' e LNG such that (i) O admits M' (ii) M' is parsimonious for O and (ii)) O ~M O2 iff O2 ~M Oj.
Proof of Corvllary 4.4. Suppose O admits faithful M E LNG that not parsimonious for O. By repeated appeal to Lemma 4.1, we must eventually arrive at some M' that is parsimonious for O, either because no column of Bo (M) is proportional any other (see Theorem 4.3), or because M' E LNG, has no latent variables.

---

X1
X2
X2
Figure 2: Note that the exogenous noise terms E1, E3 switch places. Although the left and right-hand models generate the same distribution over (X1, X2) they disagree on the total causal effect of X on X2 whenever b + O. When ac bb, the Ihs model is unfaithful and the models disagree, not only on the size of the effect, but on the presence of an edge.
5 Causal Identifiability
The essence of Shimizu al. [2006] is that if vector of p observed variables admits model in p variables, that model is unique. For a simple proof, see Theorem 2.3 Genin and Mayo-Wile Wilson [2020].
Theorem 5.1. Suppose that (O1,.... Op) admits M, M' LNGG, then M = M'.
Unfortunately, that is no longer the case when latent variables are present. Of course, if admits LiNGAM without latents, it also admits one with latents. Figure I yields such an example: in left-hand model the causal relationship is mediated by L and the right-hand model the causal relationship is unmediated. That situation is not too worrisome, since the total causal effect Xı on X2 the same in both circumstances. What more worrisome that the vector of observed variables O may admit two LiNGAM models that differ the effects of interventions. An example, due to Salchkaleybar et al. [2020], given in Figure 2. The good news is that if a set observed variables admits faithful LiNGAM models, the models must agree the ancestor relationship between them. Although this is shown already by Salehkaleybar et al. [2020, Lemma 5], the following is a simple proof that does not rely facts about independent component analysis.
Theorem 5.2. Suppose that O (O1....,O0p Op) admits faithful M, M'. Then O -MM O₂ iff O, arr Oj
Proof of Theorem 5.2. By Corollary 4.4 there are faithful LINGAMs F, F' such that 1. O admits
F, F 2. O₂ ~* O, iff O ~-F O5; 3. O, ~a O2 iff O₂ w'p O, and 4. Bo(F) and Bo (F) both have pairwise linearly independent columns. By (1) and (2), it suffices prove that O ~* wt O iff O map Oj. But since the situation is symmetrical, it suffices to prove that O mpp O, only if O m Oj-
Suppose for contradiction that O; mr Oj but O; frr Oj. Let a be permutation embedding O in F. Let B, C be (F) Bo (F)), respectively. Let f be co (F), (F(F", respectively. Then
O = Be Cf.
Since O, f.r Oj, Cj+ = 0. Moreover, Cj = 1 By faithfulness F, O, ~F O implies that
B₁ + 0. By Theorem 4.2, there must be column * i and real number + 0 such that Bi = aCu * but Byt = aC₁; = 0. Since Bi * 0, it follows that a ((k) ~F a (i). Since O; ~r O; by assumption, it follows that a (i) or (j). By transitivity of ~FF a -kk) map (j). However, Byx = So F is unfaithful. Contradiction.
For A E {LNG, LNG", LNG,, FL,GG, FLNGS, FLNG.), let O' be the set
(O E O (EM e A) O admits M and O, - O2}.
Define Ojmij Ojoj analogously, replacing > with M* and oM respectively. In light of Theorem 5.2, Oire FLNG and Ojoj are disjoint.

---

Jim
Ui Vi
Up Vo
Jam
X1
X2
X1,0
N2
Figure 3: The (X1,m X2.m), which lie in FL.ag. converge in probability to xx, lying in FLNOG. Note that although error terms approach Gaussianity and the model approaches unfaithful- ness, no term in the sequence unfaithful and no noise term is Gaussian. For definitions of error and exogenous terms, see the proof of Lemma 6.2.
The Topology of Latent Confounding
Op) admits a LiNGAM model without latents, Genin and Mayo-Wilson Wilson [2020, Theorem 4. prove that orientation hypotheses are topologically well-separated:
When O
Lemma 6.1. O Oitdg are open and O is closed in the weak topology OLNGE LNog
The situation changes when we allow for latent variables.
Lemma 6.2. FLNec is not disjoint from cl( clO FLNG; in the weak topology on OFNGSE Moreover, there are distributions in the intersection that are absolutely continuous wrt Lebesgue measure.
Proof of Lemma 6.2. Let = 2. Let U1, U2 W1, W2, Z1, Z2 be mutually independent, absolutely continuous random variables. Suppose that all variables except Z1. Z2 are non- non-Gaussian. Let
Vi Z1 + Zo and let 1/2 Z1 Z2. By the Lukacs-King King theorem, Vi, V/2 are independent. Let X (X1, X2) = (U1 + Vi, U1 + U2 + 271). By reference to the lhs model in Figure 3, is clear
that X E OFINGG. Moreover, X is absolutely continuous wrt Lebesgue measure on IR.
For > 2, let X1,m U1 +V LW, + W2 + U2) and X2, +22 22 + W1. Let X = (X1., X2,m). ). clear that the Xm, converges in probability, and therefore in distribution, to X. It remains to show that the X m lie in OLLOaE which we do by reference to the rhs model in
m
Wi and J2,m L2 + W2. Then J J, U1, U2 are independent Figure Let J1.m Zi m
1
1
-1+
m
0
0
2
1
and non-Gaussian. Let o% = (J2,m, U1 J1,, U2). Let Am
and
0
0
0
0
0
0
1
1
0
1
2
B
It easy to check that Bn (I-AA,,)) Am_ Let Mn (Bmem Ams Cm)
0
0
0
0
0
By inspection of By, Mn, faithful. Since the entries of An are smaller than c, M E FLNG. Letting Cm be the first two rows of Bm. it is easy to verify that (Xi. X2,m) )²r Cmem By Theorem 4.3, since, for m > 2, no column Om is proportional to any other, Mm is parsimonious for Xm Therefore, Xm OFLNC.
In the following, will appeal extensively to the following Lemma, given by Kagan al. [1973].
Lemma 6.3. Suppose the k-dimensional random vectors e, have independent components. Consider the sequence of p-dimensional random vectors X,, Ben, where B is a x k matrix. If the X, converge in distribution to X, then X Be, where a k-dimensional random vector with independent components.
The following a straightforward Corollary of Lemma 6.3.
Corollary 6.4. Suppose the k-dimensional random vectors en have independent components. Con- sider sequence of p-dimensional random vectors X,, B,G,. where the Bn, are k matrices and B,, -> B. If the X, converge in distribution to X, then X Be, where e is a k-dimensional random vector with independent components.
8

---

Proof of Corollary 6.4. It is a standard fact that if ,x,, Y,, converge in probability to 0 and the X converge in distribution to X, then the Y, also converge distribution to X. Clearly, e,,,, Be,, converge in probability to O. By assumption, the e, converge in distribution to X. It follows that Ben converge in distribution to X. By Lemma 6.3, X Be, where is a k-dimensional random vector with independent components.
L
Theorem 6.5. For d 2P p. OFLNSS, is open in the weak topology on OFLNGE.
Proof of Theorem 6.5. Lete S d < f Suppose for contradiction that the O₂, E FLLNG, converge in distribution to E FLNGJ. Let M E FLNGÿ be parsimonious for O and Mn E FLNG, be parsimonious for O₂, Let B, Bo., (Mn) and = Bo (M). Let e, = eo., (Mn) and e = eo (M). While B is p X I matrix, each of the B,, are p X matrices. By the Bolzano-Weierstren theorem, since the B, are uniformly bounded, there is a x e matrix B and convergent subsequence BRn.. + B. By assumption, Bnn en. converge in distribution to O. By Corollary 6.4, O Bf where f is a vector of independent components. Therefore O = Ae- = Bf. By 4.2 every column of A must be proportional to some column of B. Since A has strictly more columns than B, two columns of A must be proportional to the same column of B and, therefore, to each other. But then, by Theorem 4.3, M is not parsimonious for O. Contradiction.
We have shown that for every O E FLNGS, there is an open set separating O from FLNG, Since < was taken to be arbitrary, there is such an open set Eg separating O from each FLNG, with p S < f. Since there are only finitely many of the Eg, the intersection of the Eg is open and separates O from OTLNaE That shows that for every O E O there is an open set Eo separating O from OpLNog." Therefore, OpLNOE, = UOEO Eo is a union of open sets and, therefore, open in OFLOSS.
As special case, Theorem 6.5 entails that OFLNaS, is open. By Genin and Kelly [2017, Theorem 4.1], this means that it is statistically verifiable whether an unobserved confounder must be introduced in order to accommodate the distribution of O, at least when all distribution are assumed to be absolutely continuous wrt Lebesgue measure. As expected, the hypothesis of um-confoundedness is statistically testable. On the other hand, the precise hypothesis FLNG; is neither statistically verifiable nor refutable, even under the background assumption that the distribution O was generated by some model in FI.NG.. To see this, note that for d > p. FLNG; is neither open nor closed, since more parsimonious models can approximate simpler models. Therefore, is properly locally closed, Although it is neither verifiable nor decidable, it is decidable in the limit by Theorem 2. We shall see that the same is true for the hypothesis of orientation OpENe The following shows that if we knew exactly how many latent variables were necessary to accommodate the observed distribution. orientation hypotheses would be topologically well-separated.
Theorem 6.6. For d 2 p, FFLNG Ofrd are open and Ofikog is closed in the weak topology on OPLNCS
Proof of Theorem 6.6. Suppose for a contradiction that the O, E &fttee converge in distribution
to O FINGY. Let M E FLNG; be parsimonious for O and M, E FLNG. be parsimonious for On Let Bn = Bo, (Mn) and A (M)) Let e,, = eo., (M,) and e eo By the Bolzano-Weierstrass Weierstrass theorem, since the Bn are uniformly bounded, there is p x e matrix B and a convergent subsequence BR... + B. By assumption. Bn.,, en,, converge in distribution to O. By Corollary 6.4, O Bf where f is a vector of independent components. Therefore O Ac = Bf. Since (Bn) = for all n, B,; = O. Moreover, B, = 1. Since A and B have equal dimensions, by Theorem 4.2 there must be column i such that A₁ = 0 and A * 0. But then O ~ Mr O and O ~ O, and, therefore, O₁ ~* O,, But since A₁ = 0, M must be unfaithful. Contradiction. We have shown that Oiingg is open in the weak topology on OPLNaG- Since the is the complement of jo FLNoG U U f
situation is symmetrical, Ofri is also open. Since Ope FLNog it is closed in OpiNag-
'Recall that, in metrizable spaces such as the weak topology, every locally closed set is countable union of closed sets.

---

Corollary 6.7. FLNG=: O O FLNG= are disjoint countable unions of sets closed in FFLNGE
Proof of Corollary 6.7. In general if A is open/closed in subspace, the intersection of an open/closed set with the subspace. By Theorem 6.5, FLxes is locally closed in OFLNGE By Theorem O 6.6, FLNGE: F FLNe are either open or closed in Orisag- Therefore, FLNag, FLNGg. FLNNg are locally closed in FLNG.. It follows that each of FL FLLNa O is a countable union of locally closed sets. In metrizable space such as the weak topology, each open set, and therefore each locally closed set, is countable union of closed sets. Therefore, each of FLNG": O O a countable union of closed sets. They are disjoint by Theorem 5.2.
FLNG" is
Main Result and Discussion
We are now in position to state and prove the main results. Let M be the set of all pairs (M, where M E FLNG and a is permutation of fl...., [M]] Let P((M,a) (X (M). .....,,X-'0) Xa-) Let M {(M,a) E M a (i) MMM a (i) and M = ((M,a) E M: a a oM a (()..
IMI.
Theorem 7.1. The question Q = {Min), ( , Mimig not statistically decidable.
is identified and decidable in the limit, but
Proof of Theorem 7.1. It immediate from defintions that P(M -prni P(Min))
OPLNgE and P(M = O FLNGE Since OLNGe. FLN FL are disjoint by Theorem 5.2, the question is identified. Since they are each countable unions of closed sets (by Corollary 6.7). Theorem 2.1 implics that Q is decidable in the limit. By Theorem 2.2 and Lemma 6.2, Q is not decidable. 0
Theorem 7.1 shows that learning causal orientation in faithful, but potentially confounded, LINGAM models is a difficult problem. Not so difficult that it is impossible to construct consistent methods, but difficult enough that consistent method can guarantee finite-sample bound the probability of orientation errors. In view of the positive results given by Genin and Mayo-Wilson Wilson [2020] in the unconfounded setting, this negative result is something of disappointment. However, the example in Figure 3 suggests several different adjustments to the LiNGAM framework that may recover decidability. The first is the well-trodden path of strong faithfulness. As m grows, the direct path from U2 to X1.m comes closer and closer to cancelling the path via X2.m Strengthening faithfulness would preclude this possibility. But faithfulness is already a controversial assumption and strengthenings would do nothing to appease its critics. Moreover. Uhler et al. [2013] show that strong versions of faithfullness can rule out a topologically large set of models. The second path of escape is to strengthen the assumption of non-Gaussianity. As m grows, J1.m and J2.m converge to the Gaussians Z, and Zz. Assuming that noise terms are bounded away from Gaussianity would preclude this possibility. The third possibility is to require that no error term have Gaussian component. A random variable X has a Gaussian component it can be expressed as the sum Y Z where Y, Z are independent and Z is Gaussian. It is clear that the error terms in Figure 3 violate this condition indeed properties of the Gaussian are essential to ensuring that Vi and V22 and therefore U, + Vi and U2 + V22 are independent. In light of uniqueness results by Kagan et al. [1973] (see particularly their Theorem 10.3.6) it is likely that requiring that noise terms have no Gaussian component would recover decidability. Moreover, the assumption of no Gaussian components does not strike this author as significantly less plausible than the assumption of non- -aussiaasa.
In recent years, the field of causal discovery has produced many exciting new identifiability results under a variety of modeling assumptions. But demonstrating identifiability proves only that problem is not completely hopeless - it is only the first step in understanding how difficult problem is. Success notions intermediate between uniform decidability and decidability in the limit can help structure the search for "Goldilocks" modeling assumptions: neither so weak as to preclude short-run bounds on error nor so strong as to secure uniform convergence. Moreover, it is the hope of this author that the topological methods exhibited here prove useful in these future investigations.
10

---

Acknowledgments and Disclosure of Funding
Funded by the Deutsche Forschungsgermeinscaatt (DFG, German Research Foundation) under Germany's 's Excellence Strategy EXC number 2064/1 Project number 390727645. am grateful to Conor Mayo-Wilsse and the anonymous reviewers for their careful reading and helpful comments and suggestions.
References
Patrick Billingsley. Probability and measure. John Wiley & Sons, second edition, 1986.
Peter Bühlmann, Jonas Peters, and Jan Ernest. CAM: Causal additive models, high- high-dimensional order search and penalized regression. The Annals of Statistics, 42(6):2526 2556, 2014.
Amir Dembo and Yuval Peres. A topological criterion for hypothesis testing. The Annals of Statistics, 22(1):106-117, 1994.
Konstantin Genin and Kevin T Kelly. The Topology of Statistical Verifiability. In Proceedings of Theoretical Aspects of Rationality and Knowledge (TARK), 2017. URL https: //tr:////xxvv org/
0ttp/17770099770
Konstantin Genin and Conor Mayo-Wilson. Statistical Decidability in Linear, Non-Gaussian Models. In NeurIPS 2020: Workshop on Causal Discovery and Causality-Insiired Machine Learning, 2020.
Patrik O. Hoyer, Shohei Shimizu, Antti J. Kerminen, and Markus Palviainen. Estimation of causal effects using linear Gaussinn causal models with hidden variables. International Journal of Approximate Reasoning, 49(2):362-3 2008.
A. M. Kagan, Y. V. Linnik, and C. R. Rao. Characterization Problems in Mathematical Statistics. John Wiley & Sons, 1973.
Kevin T. Kelly and C. In Proceedings of the Twenty Sixth Conference Uncertainty in Artificial Intelligence (UAI), pages 277-286, 2010.
Causal Conclusions that Flip Repeatedly and Their Justification.
James M Robins, Richard Scheines, Peter Spirtes, and Larry Wasserman. Uniform consistency in causal inference. Biometrika, 90(3):491-515 2003.
Saber Salehkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Learning linear non- gaussian causal models in the presence of latent variables. Journal of Machine Learning Research, 21(39): 1-24, 2020.
Shohei Shimizu, Patrick O. Hoyer, Aapo Hyvarinen, and Antti Kerminen. linear Non-Gaussian acyclic model for causal discovery. The Journal of Machine Learning Research, 7:2003-2033 2030, 2006.
Peter Spirtes, Clark N. Glymour, and Richard Scheines. Causation, Prediction, and Search. The MIT Press, 2000.
Caroline Uhler, Garvesh Raskutti, Peter Bühlmann, and Bin Yu. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics, 41(2):33-4633 2013.
Jiji Zhang and Peter Spirtes. Strong faithfulness and uniform consistency in causal inference. In Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence (UAI), pages 632-6 332-639, 2003.


Reviews:
[{"review_id": "TtAo2UuQ7gq", "reviewer": "Reviewer_YVg9", "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. \n\nThere 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). \n\nTheir 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.\n\n----\nI updated the score and confidence. \n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality: 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. \n\nFor 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.\n\nKelly 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.\n\nMy 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. \n\nIn 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?\n\nIn 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?\n\nOther questions are: \n1.\twhether this consistency property depends on the choice of estimation algorithms, e.g., ICA-based LiNGAM or some other estimation methods for LiNGAM. \n\n2.\tDo 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?\n\n3.\tTable 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.\n\n4. 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. \n\nClarity: 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.\n\nSignificance: 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "ItnS_zXqNIV", "reviewer": "Reviewer_oGNr", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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’. \n\nIn 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. \n\nApart 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).\n\nAll 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. \n\n=> For now: borderline to weak accept, but with medium confidence as I am not an expert in this particular area.\n\n- originality: novel and interesting example that supports the core argument,\n- quality: high quality\n- clarity: very technical, but well written and still fairly good to follow for a non-insider\n- significance: interesting find, but not sure it will have much impact beyond statistical & causal purists\n\nminor comments:\n- why no line numbers? \nintroduction: ‘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 \np2,top: ‘uniform consistency’ => here a ref. to ‘Uniform Consistency in Causal Inference’ (Robins,Scheines,Spirtes,Wasserman 2003) would be appropriate\np2,mid: ‘locally closed’ : so an open set is still ‘locally closed’ if it can be contained in a closed set?\np3,start sec.2: change to ‘An *acyclic* linear causal model’ (or ‘recursive’)\nidem: would the results in this paper change if M is allowed to be non-recursive?\np3, term (1.): what is the role of \\omega in this equation?\np5,Lerm/Thm/Cor 3.1: clear and interesting results, though not a fan of overloaded label numbers :)\np6,Fig3: mention the intrinsic noise term \\epsilon_1+3 have switched places (I did not notice this at first)\np7,Fig3/Lemma 5.2: interesting example, but see main review\np8,below Thm 5.1: ‘consequences of Lemma 5.1’ => I assume you mean ‘Theorem 5.1’ right?\np9, 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", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "GCG-WIr1yJ", "reviewer": "Reviewer_xWiG", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nQuality: 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:\n\n-- 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?\n\n--- 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.\n\n-- 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?  \n\n\nClarity: 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: \n\n--- \"prove that if, in addition to\nthe usual LiNGAM assumptions, we assume causal faithfulness, then causal orientation between\nobserved 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\n\n--- there is label \"34th Causal Discovery & Causality-Inspired Machine Learning Workshop at Neural Information Processing\nSystems, 2020\" at the bottom of page 1. Please remove.\n\n--- \"Causal orientation is statistically decidable,\nif for any \u000b\\alpha> 0; there is a consistent procedure that, at every sample size, hypothesizes a false\norientation 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.\n\n--- 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. \n\n--- 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.\n\n---- \"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. \n\n---- 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\"?\n\n--- 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. \n\n---- \"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. \n\n----- 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\nto 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. \n\n----  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,...)\n\n---- Theorem 4.1: how is this different than standard LINGAM result?\n\n---- \"That situation is not too worrisome, since the effect of an ideal\nintervention on X1 would be the same in both circumstances. What is more worrisome is that\nthe vector of observed variables O may admit two LiNGAM models that differ on the effects of\ninterventions.\" -> what is the definition of intervention here? seems strange to see intervention all of a sudden. Perhaps authors could rephrase.\n\n--- 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.\n\nthe same of questions and displaying what is needed for statistical decidability.\n\nSignificance: 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None that I can foresee.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "C2Rwq3_li4t", "reviewer": "Reviewer_YEWp", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper analyzes the statistical consistency of the causal discovery method.   \nThe paper builds on the decidability of the LiNGAM.  The authors put some effort into relaxing the sufficiency assumption and allowing latent confounders.\nThe theoretical contributions of this paper are both novel and significant.\n \nHowever, 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.\n \n \nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

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)