Statistical Undecidability in Linear, Non-Gaussian Causal Models in the Presence of Latent Confounders
Year: 2021

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, non-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-Wilson (2020) refine that result: not only are causal relationships identified, but causal orientation is statistically decidable. That means that for every ε > 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 ε. 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.

heading: 1 Introduction
text: 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 in 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 are independent and non-Gaussian, all causal orientations can be uniquely identified from observational data, even without assuming faithfulness. However, that early result depends on 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 et al., 2008, Salehkaleybar 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).
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 on 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 on 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 not entail the existence of a 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 to determine a priori a sample size at which the chance of identifying the true orientation is at least 1− α, no matter which causal model is generating the data. Unfortunately, it is easy to show that there is no uniformly consistent algorithm for determining the direction of a causal edge, even in unconfounded LiNGAMs (see Example 1 in Genin and Mayo-Wilson [2020]). Although one could strengthen the LiNGAM assumptions to make uniform decidability feasible, these assumptions would probably be implausibly strong .2
Decidability in the limit (elsewhere known as 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 at least 1 − α. Note that this is compatible with all kinds of short-run behavior. For example, Kelly and Mayo-Wilson [2010] show that in the unconfounded 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 X causes Y or vice versa. That means that for any such procedure, it is possible to find a model in which the procedure flips between being highly likely to output the correct causal orientation at a smaller sample size and highly likely to output the incorrect orientation at a larger sample size, with the number of such flips bounded only by the number of variables in the model.
Genin and Mayo-Wilson [2020] introduce a new notion of decidability that is intermediate between uniform decidability and decidability in the limit. Statistical decidability requires that a discovery procedure converge to the true orientation as sample sizes increase and, at every sample size, output an incorrect orientation with probability at most α. Note that statistical decidability rules out flipping behavior, but is consistent with suspending judgement at arbitrarily large sample sizes. Genin and Mayo-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.
2In the linear Gaussian setting, Robins et al. [2003] show that uniform consistency is not feasible under standard assumptions. Zhang and Spirtes [2003] propose a strengthening of these assumptions to ensure uniform decidability, but Uhler et al. [2013] argues that this rules out a 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 1 sums up: if we have a uniform decision procedure we know that the output of the method is 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 a 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 Salehkaleybar 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 is 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.

heading: 2 Technical Preliminaries
text: We first introduce notation for manipulating matrices. Suppose A is an n× p matrix and U, V are subsets of {1, . . . , n}, {1, . . . , p}, respectively. Let A[U ;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(U ;V ) be the result of dropping all rows from A that are in U and all columns that are in V. We write A(i,j) for A({i};{j}) and Aij for A[{i};{j}]. We say A has pairwise linearly independent columns iff no two columns of A are proportional.
LetM be a set of statistical models. We assume there is a function P : M 7→ PM that maps each model inM to a probability measure over a space Ω of observed outcomes, although we often do not distinguish between a 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 ⊆M, let P [A] = {P (M) : M ∈ A}. Let P = P [M]. Let P0 ⊆ P be the probability measures in P absolutely continuous with Lebesgue measure on Ω. Let P0[M] = P0 ∩ P [M]. If A ⊆ Rnd, let ∂A be the boundary of A in the usual topology on Rnd. The weak topology on P is defined by letting a sequence of Borel measures Pn converge weakly to P, written Pn ⇒ P iff Pn(A)→ P (A), for every A such that P (∂A) = 0. A collection of random vectors (Xn) converges in distribution to X iff the probability measures induced by the Xn 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 is 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 a countable union of closed sets. For any natural number k, let P kM be the k-fold product measure of PM with itself. This measure describes the probabilities of events in Rkd when we take k iid samples from PM . If the measures Pn converge weakly to P, the product measures P kn also converge weakly to P k (see Theorem 2.8 in Billingsley [1986]).
We define a question Q to be a countable set of disjoint subsets ofM. The elements of Q are called answers. For all M ∈ ∪Q, let Q(M) denote the unique answer in Q containing M. The answer to question Q is identified iff P (M) ̸= P (M ′) whenever Q(M) ̸= Q(M ′). Given a question Q, we define a method λ = ⟨λn⟩n∈N to be a sequence of measurable functions λn : Ωn → Q ∪ {M}, where λn 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 callM the uninformative answer. We require that ∂λ−1n (A) has Lebesgue measure zero for all n and every answer A in the range of λn.
A method is (pointwise) consistent for Q if for all ϵ > 0 and M ∈ ∪Q, there is n such that P kM (λk = Q(M)) > 1 − ϵ for all k ≥ n. We say that Q is decidable in the limit iff there is a consistent method for Q. 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]). Q is decidable in the limit if {P (A) : A ∈ Q} is disjoint and each P (A) is a countable union of sets closed in the weak topology.
Given some α > 0, say that a method λ is an α-decision procedure for Q if (1) λ is consistent for Q and (2) PnM (M /∈ λn) ≤ α for all M ∈ ∪Q and all sample sizes n. In other words: an α-decision procedure outputs a false hypothesis with probability at most α. A question is statistically decidable (or simply decidable) if there is an α-decision procedure for α > 0. We give a simple necessary condition for statistical decidability. Theorem 2.2. Q is statistically decidable only if P0(A) ∩ clP (B) = ∅ for all A,B ∈ Q.
Proof of Theorem 2.2. Suppose for a contradiction that PM ∈ P (A) ∩ cl(P (B)) is absolutely continuous with Lebesgue measure and λ is an α-decision procedure for Q. Since λ is consistent for Q, there must be n such that PnM (λ −1 n (A)) > 1 − α. Since ∂λ−1n (A) has Lebesgue measure zero and PnM is absolutely continuous with Lebesgue measure on Rnp, PnM (∂λ−1n (A)) = 0.3 Therefore, there are (Mi) in B such that PnMi(A) → P n M (A). But then there is some Mj ∈ B such that PnMj (Mj /∈ λn) > α. Contradiction.
It is worth introducing some intuitive language for questions Q with only one (usually non-exhaustive) answer A ⊆M. We say that A is statistically verifiable iff Q = {A} is decidable. Say that A is statistically refutable iff Q = {M \ A} is decidable. For partial converses of Theorems 2.1 and 2.2, see Genin and Kelly [2017]. Essentially, the converses hold straightforwardly if all distributions are 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 an arbitrary degree of precision the distribution over (X,Y ) generated by a faithful LiNGAM in which X → Y by a sequence of distributions (Xm, Ym) generated by faithful but confounded LiNGAMs in which Xm ← Ym (see Figure 3 and Lemma 6.2). Undecidability follows by appeal to Theorem 2.2.

heading: 3 Acyclic Linear Causal Models
text: An acyclic linear causal model in d variables4 M is a triple ⟨X, e, A⟩, where X = ⟨Xi⟩ is a vector of d random variables, e = ⟨e1, e2, . . . , ed⟩ is a random vector of d exogenous noise terms, and B is a d× d matrix such that
1. Each variable Xi is a linear function of variables earlier in the order, plus an unobserved noise term ei: Xi = ∑ j<i AijXj + ei;
2. the noise terms e1, . . . , ed are mutually independent.
In matrix notation, we have that X = AX+ e. Because no Xi causes itself, A has only zeroes along its diagonal. By virtue of the causal order, A 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 = (I−A)−1. 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 a 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
3It is a basic fact that if µ << ν then µn << νn. 4In the following d refers to the total number of (potentially hidden) variables and p ≤ d to the number of
observed variables.
X, e, A and (I −A)−1, respectively. The relationship between A(M) and B(M) will be made more perspicuous in the following.
Write j →M i as a shorthand for Aij(M) ̸= 0. The relation→M defines a directed acyclic graph G(M) over the vertices {1, . . . , |M |}. A causal path of length m from i to j in G(M) is a sequence of vertices π = (v1, . . . , vm) such that v1 = i, vm = j and vi →M vi+1. Let Πnij(M) be the set of all causal paths of length n from i to j in G(M). Let Πij(M) be the set of all causal paths from i to j in G(M). Let Π(M) be the set of all causal paths in G(M). Write i ⇝M j as a shorthand for Πij(M) ̸= ∅. Write j ◦M i when j ̸⇝M i and j ̸ ⇝M i. If π = (v1, . . . , vn) is a sequence of vertices in {1, . . . , |M |}, let the path product×M π be the product of all causal coefficients along the path π in G(M), i.e.×M π = ∏ni=1 Avi+1,vi(M). Note that if π ∈ π(M) iff×M π ̸= 0. It is easy to verify that
Akij(M) = ∑
π∈Πkji(M)
×Mπ.
In other words, Akij(M) is the sum of all path products for paths of length k from i to j. So A k ij(M) ̸= 0 implies j ⇝M i. The converse is not necessarily true, since non-zero path products may sum to zero. By a result of Carl Neumann’s, B(M) = ∑|M | k=0 A k(M).5 So Bij(M) = ∑
π∈Πji(M)×M π. In other words, Bij(M) is the sum of all path products for paths from i to j. So Bij(M) ̸= 0 implies j ⇝M 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 Xi to Xj is nonzero if there is a causal path from Xi to Xj . In other words: M is faithful if Bij(M) ̸= 0 whenever j ⇝M i. An acyclic linear causal model M is non-Gaussian (a LiNGAM) if in addition to satisfying (1) and (2), each of the noise terms is non-Gaussian. Let LINd be the class of all acyclic linear causal models on d variables, and let LNGd, FLNGd respectively denote the classes of non-Gaussian models and faithful 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 on the maximum size of a coefficient in a LiNGAM model. For example, if c is the number of particles in the universe, let FLNGc be the set {M ∈ FLNG : maxi,j |Bij(M)| < c}. Let FLNGcd be FLNG c ∩ FLNGd.

heading: 4 Parsimonious Models
text: Let O be the set of all probability distributions on Rp. We are interested in when the same vector of observed random variables could have arisen from distinct causal models. Accordingly, say that a random vector O = (O1, . . . , Op) ∈ O admits a LiNGAM model M ∈ LNGd if there is a permutation α of (1, . . . , d) such that Oi = Xα−1(i)(M) for 1 ≤ i ≤ p. In other words: O = (O1, . . . , Op) admits M if there is a way to order the d variables of X(M) such that the first p are identical with O1, . . . , Op. We say that the permutation α embeds O into M. If α embeds O into M, then
O = BO(M)eO(M),
where BO(M) is the first p rows of PαB(M)Pα, eO(M) is Pαe(M) and Pα is the permutation matrix corresponding to α. Extend the causal order over the elements of M to the Oi by setting Oi ⇝M Oj if α−1(i)⇝M α−1(j) and Oi ◦M Oj if α−1(i) ◦M α−1(j). Say that O admits a LiNGAM model if there is d such that O admits M ∈ LNGd. We say that a model M ∈ LNGd is parsimonious for O if O admits M and O admits no M ′ in LNGf with f < d. It is immediate that if O admits a LiNGAM model, it admits some parsimonious LiNGAM model. For A ∈ {LNGd, LNGcd, FLNGd, FLNGcd} Let OA ⊂ O be the set
{O ∈ O : (∃M ∈ A)M is parsimonious for O}. 5The spectral radius ρ(A) of a square matrix A is the largest absolute value of its eigenvalues. Neumann’s
result states that if ρ(A) < 1 then (I − A)−1 exists and is equal to ∑∞
k=0 A k. Since the eigenvalues of a
triangular matrix are exactly its diagonal entries, ρ(B(M)) = 0 for any acylic linear causal model M . By acyclicity, there are no paths longer than |M |, so ∑ k>d A k = 0.
For A ∈ {LNG, LNGc, FLNG, FLNGc} Let OA≤d = ∪j≤d OAj and OA≥d = ∪j≥d OAj . Let OA<d ,OA>d be defined similarly. Finally, let OA = OA≥p .
The following Lemma says that if M is faithful and parsimonious for O then no column of BO(M) is proportional to any other. The proof idea is expressed by Figure 1: by adjusting the edge coefficient from X1 to X2, it is possible to “absorb" L into the noise term of X2 without changing the distribution of (X1, X2) 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 ∈ LNGd and that some column of BO(M) is proportional to another. Then there is M ′ ∈ LNGd−1 such that (i) O admits M ′ and (ii) Oi ⇝M Oj iff Oi ⇝M ′ Oj and (iii) 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 to 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 × s matrices and e = (e1, . . . , er), f = (f1, . . . , fs) are random vectors with independent components. Suppose that no two columns of A are proportional to each other. If the i-th column of A is not proportional to any column of B, then ei is normally distributed.
Theorem 4.3. Suppose that faithful M ∈ LNGd. Then, M is parsimonious for O = (O1, . . . , Op) iff no column of BO(M) is proportional to any other.
Proof of 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, O admits some M ′ ∈ LNGf with f < d. Moreover O = BO(M)eO(M) = BO(M ′)eO(M ′), where BO(M) is an p×d matrix and BO(M ′) is a p × 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 BO(M) that are proportional to the same column of BO(M ′) and, therefore, to each other.
We close this section with an 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 ′ ∈ LNG such that (i) O admits M ′ (ii) M ′ is parsimonious for O and (iii) Oi ⇝M Oj iff Oi ⇝M ′ Oj .
Proof of Corollary 4.4. Suppose O admits faithful M ∈ LNG that is 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 to any other (see Theorem 4.3), or because M ′ ∈ LNGp has no latent variables.

heading: 5 Causal Identifiability
text: The essence of Shimizu et al. [2006] is that if a vector of p observed variables admits a model in p variables, that model is unique. For a simple proof, see Theorem 2.3 in Genin and Mayo-Wilson [2020].
Theorem 5.1. Suppose that = (O1, . . . , Op) admits M,M ′ ∈ LNGp, then M = M ′.
Unfortunately, that is no longer the case when latent variables are present. Of course, if O admits a LiNGAM without latents, it also admits one with latents. Figure 1 yields such an example: in the left-hand model the causal relationship is mediated by L and in the right-hand model the causal relationship is unmediated. That situation is not too worrisome, since the total causal effect X1 on X2 is 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. An example, due to Salehkaleybar et al. [2020], is given in Figure 2. The good news is that if a set of observed variables admits two faithful LiNGAM models, the models must agree on 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 on facts about independent component analysis.
Theorem 5.2. Suppose that O = (O1, . . . , Op) admits faithful M,M ′. Then Oi ⇝M Oj iff Oi ⇝M ′ Oj
Proof of Theorem 5.2. By Corollary 4.4 there are faithful LiNGAMs F, F ′ such that 1. O admits F, F ′; 2. Oi ⇝M Oj iff Oi ⇝F Oj ; 3. Oi ⇝M ′ Oj iff Oi ⇝F ′ Oj and 4. BO(F ) and BO(F ′) both have pairwise linearly independent columns. By (1) and (2), it suffices to prove that Oi ⇝F Oj iff Oi ⇝F ′ Oj . But since the situation is symmetrical, it suffices to prove that Oi ⇝F Oj only if Oi ⇝F ′ Oj .
Suppose for a contradiction that Oi ⇝F Oj but Oi ̸⇝F ′ Oj . Let α be a permutation embedding O in F . Let B,C be BO(F ), BO(F ′), respectively. Let e, f be eO(F ), eO(F ′), respectively. Then
O = Be = Cf .
Since Oi ̸⇝F ′ Oj , Cji = 0. Moreover, Cii = 1 By faithfulness of F , Oi ⇝F Oj implies that Bji ̸= 0. By Theorem 4.2, there must be a column k ̸= i and real number a ̸= 0 such that Bik = aCii ̸= 0 but Bjk = aCji = 0. Since Bik ̸= 0, it follows that α−1(k) ⇝F α−1(i). Since Oi ⇝F Oj by assumption, it follows that α−1(i) ⇝F α−1(j). By transitivity of ⇝F , α−1(k)⇝F α−1(j). However, Bjk = 0. So F is unfaithful. Contradiction.
For A ∈ {LNG, LNGc, LNGcd, FLNG, FLNGc, FLNGcd}, let O i→j A be the set
{O ∈ OA : (∃M ∈ A)O admits M and Oi →M Oj}.
Define Oi⇝jA ,O i◦j A analogously, replacing→M with⇝M and ◦M , respectively. In light of Theorem 5.2, Oi⇝jFLNG, O i ⇝j FLNG and O i◦j FLNG are disjoint.

heading: 6 The Topology of Latent Confounding
text: When O = (O1, . . . , Op) admits a LiNGAM model without latents, Genin and Mayo-Wilson [2020, Theorem 4.1] prove that orientation hypotheses are topologically well-separated:
Lemma 6.1. Oi→jLNGcp ,O i←j LNGcp are open and Oi◦jLNGcp is closed in the weak topology on OLNGcp .
The situation changes when we allow for latent variables.
Lemma 6.2. Oi→jFLNGcp is not disjoint from cl(O i←j FLNGcp+2 ) in the weak topology on OFLNGc . Moreover, there are distributions in the intersection that are absolutely continuous wrt Lebesgue measure.
Proof of Lemma 6.2. Let p = 2. Let U1, U2,W1,W2, Z1, Z2 be mutually independent, absolutely continuous random variables. Suppose that all variables except Z1, Z2 are non-Gaussian. Let V1 = Z1 + Z2 and let V2 = Z1 − Z2. By the Lukacs-King theorem, V1, V2 are independent. Let X = (X1, X2) = (U1 + V1, U1 + U2 + 2Z1). By reference to the lhs model in Figure 3, it is clear that X ∈ OFLNGc2 . Moreover, X is absolutely continuous wrt Lebesgue measure on R 2.
For m > 2, let X1,m = U1 + V1 + 1m (W1 +W2 + U2) and X2,m = U1 + U2 + 2Z1 + 2 mW1. Let Xm = (X1,m, X2,m). It is clear that the Xm converges in probability, and therefore in distribution, to X. It remains to show that the Xm lie in OFLNGc4 , which we do by reference to the rhs model in Figure 3. Let J1,m = Z1 + 1mW1 and J2,m = Z2 + 1 mW2. Then J1,m, J2,m, U1, U2 are independent
and non-Gaussian. Let eTm = (J2,m, U1, J1,m, U2). Let Am = 0 1 −1 −1 + 1 m
0 0 2 1 0 0 0 0 0 0 0 0  and Bm = 1 1 1 1 m
0 1 2 1 0 0 1 0 0 0 0 1  . It is easy to check that Bm = (I−Am)−1. Let Mm = ⟨Bmem, Am, em⟩. By inspection of Bm, Mm is faithful. Since the entries of Am are smaller than c, Mm ∈ FLNGc4. Letting Cm be the first two rows of Bm, it is easy to verify that (X1,m, X2,m)T = Cmem. By Theorem 4.3, since, for m > 2, no column of Cm is proportional to any other, Mm is parsimonious for Xm. Therefore, Xm ∈ OFLNGc4 .
In the following, we will appeal extensively to the following Lemma, given by Kagan et al. [1973].
Lemma 6.3. Suppose the k-dimensional random vectors en have independent components. Consider the sequence of p-dimensional random vectors Xn = Ben, where B is a p × k matrix. If the Xn converge in distribution to X, then X = Be, where e is a k-dimensional random vector with independent components.
The following is a straightforward Corollary of Lemma 6.3.
Corollary 6.4. Suppose the k-dimensional random vectors en have independent components. Consider a sequence of p-dimensional random vectors Xn = Bnen, where the Bn are p× k matrices and Bn → B. If the Xn converge in distribution to X, then X = Be, where e is a k-dimensional random vector with independent components.
Proof of Corollary 6.4. It is a standard fact that if |Xn−Yn| converge in probability to 0 and the Xn converge in distribution to X, then the Yn also converge in distribution to X. Clearly, |Bnen −Ben| converge in probability to 0. By assumption, the Bnen converge in distribution to X. It follows that Ben converge in distribution to X. By Lemma 6.3, X = Be, where e is a k-dimensional random vector with independent components.
Theorem 6.5. For d ≥ p, OFLNGc>d is open in the weak topology on OFLNGc .
Proof of Theorem 6.5. Let e ≤ d < f Suppose for a contradiction that the On ∈ FLNGce converge in distribution to O ∈ FLNGcf . Let M ∈ FLNGcf be parsimonious for O and Mn ∈ FLNGce be parsimonious for On. Let Bn = BOn(Mn) and A = BO(M). Let en = eOn(Mn) and e = eO(M). While B is a p× f matrix, each of the Bn are p× e matrices. By the Bolzano-Weierstrass theorem, since the Bn are uniformly bounded, there is a p×e matrix B and a convergent subsequence Bnm → B. By assumption, Bnmenm 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 ∈ FLNGcf , there is an open set separating O from FLNGce. Since e < f was taken to be arbitrary, there is such an open set Eg separating O from each FLNGcg with p ≤ g < f. Since there are only finitely many of the Eg, the intersection of the Eg is open and separates O from OFLNGc≤d . That shows that for every O ∈ OFLNGc>d , there is an open set EO separating O from OFLNGc≤d . Therefore, OFLNGc>d = ∪O∈OFLNGc>dEO is a union of open sets and, therefore, open in OFLNGc .
As a special case, Theorem 6.5 entails that OFLNGc>p 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 un-confoundedness is statistically testable. On the other hand, the precise hypothesis FLNGcd is neither statistically verifiable nor refutable, even under the background assumption that the distribution O was generated by some model in FLNGc. To see this, note that for d > p, FLNGcd is neither open nor closed, since more parsimonious models can approximate simpler models. Therefore, it is properly locally closed. Although it is neither verifiable nor decidable, it is decidable in the limit by Theorem 2.1.6 We shall see that the same is true for the hypothesis of orientation Oi⇝jFLNGc . 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 ≥ p, Oi⇝jFLNGcd ,O i ⇝j FLNGcd are open and Oi◦jFLNGcd is closed in the weak topology on OFLNGcd .
Proof of Theorem 6.6. Suppose for a contradiction that the On ∈ Oi̸⇝jFLNGcd converge in distribution to O ∈ Oi⇝jFLNGcd . Let M ∈ FLNG c d be parsimonious for O and Mn ∈ FLNGcd be parsimonious for On. Let Bn = BOn(Mn) and A = BO(M). Let en = eOn(Mn) and e = eO(M). By the Bolzano-Weierstrass theorem, since the Bn are uniformly bounded, there is a p × e matrix B and a convergent subsequence Bnm → B. By assumption, Bnmenm converge in distribution to O. By Corollary 6.4, O = Bf where f is a vector of independent components. Therefore O = Ae = Bf . Since (Bn)ji = 0 for all n, Bji = 0. Moreover, Bii = 1. Since A and B have equal dimensions, by Theorem 4.2 there must be a column k such that Ajk = 0 and Aik ̸= 0. But then Ok ⇝M Oi and Oi ⇝M Oj and, therefore, Ok ⇝M Oj . But since Ajk = 0, M must be unfaithful. Contradiction. We have shown that Oi⇝jFLNGcd is open in the weak topology on OFLNGcd . Since the situation is symmetrical, Oi ⇝jFLNGcd is also open. Since O i◦j FLNGcd is the complement of Oi⇝jFLNGcd ∪ O i ⇝j FLNGcd , it is closed in OFLNGcd . 6Recall that, in metrizable spaces such as the weak topology, every locally closed set is a countable union of closed sets.
Corollary 6.7. Oi⇝jFLNGc , O i ⇝j FLNGc ,O i◦j FLNGc are disjoint countable unions of sets closed in OFLNGc .
Proof of Corollary 6.7. In general if A is open/closed in a subspace, it is the intersection of an open/closed set with the subspace. By Theorem 6.5, OFLNGcd is locally closed in OFLNGc . By Theorem 6.6,Oi⇝jFLNGcd ,O i ⇝j FLNGcd ,Oi◦jFLNGcd are either open or closed inOFLNGcd . Therefore,O i⇝j FLNGcd ,Oi ⇝jFLNGcd ,O i◦j FLNGcd are locally closed in OFLNGc . It follows that each of Oi⇝jFLNGc , O i ⇝j FLNGc ,O i◦j FLNGc is a countable union of locally closed sets. In a metrizable space such as the weak topology, each open set, and therefore each locally closed set, is a countable union of closed sets. Therefore, each of Oi⇝jFLNGc , O i ⇝j FLNGc ,O i◦j FLNGc is a countable union of closed sets. They are disjoint by Theorem 5.2.

heading: 7 Main Result and Discussion
text: We are now in position to state and prove the main results. Let M be the set of all pairs ⟨M,α⟩, where M ∈ FLNGc and α is a permutation of {1, . . . , |M |}. Let P (⟨M,α⟩) = (Xα−1(1)(M), . . . ,Xα−1(p)(M)). Let Mi⇝j = {⟨M,α⟩ ∈ M : α−1(i) ⇝M α−1(j)} and Mi◦j = {⟨M,α⟩ ∈ M : α−1(i) ◦M α−1(j)}.
Theorem 7.1. The question Q = {Mi⇝j ,Mi◦j ,Mi ⇝j} is identified and decidable in the limit, but not statistically decidable.
Proof of Theorem 7.1. It is immediate from defintions that P (Mi⇝j) = Oi⇝jFLNGc , P (Mi ⇝j) = Oi ⇝jFLNGc and P (Mi◦j) = O i◦j FLNGc . Since O i⇝j FLNGc , O i ⇝j FLNGc ,O i◦j FLNGc 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 implies that Q is decidable in the limit. By Theorem 2.2 and Lemma 6.2, Q is not decidable.
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 no consistent method can guarantee a finite-sample bound on the probability of orientation errors. In view of the positive results given by Genin and Mayo-Wilson [2020] in the unconfounded setting, this negative result is something of a 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 Z1 and Z2. Assuming that noise terms are bounded away from Gaussianity would preclude this possibility. The third possibility is to require that no error term have a Gaussian component. A random variable X has a Gaussian component if 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 V1 and V2, and therefore U1 + V1 and U2 + V2 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-Gaussianity.
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 a problem is not completely hopeless — it is only the first step in understanding how difficult a 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.
Acknowledgments and Disclosure of Funding
Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC number 2064/1 – Project number 390727645. I am grateful to Conor Mayo-Wilson and the anonymous reviewers for their careful reading and helpful comments and suggestions.

Review summaries:
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. 

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.